King's Graph Based Neighbor Vehicle Localization Framework

Abstract

Vehicle localization algorithm is one of the key components in Intelligent Transportation Systems applications. Localization algorithms in vehicular ad hoc networks aim to provide an accurate location estimation of neighbor vehicles for location specific message delivery in intelligent autonomous vehicles. For the initial location estimation, localization algorithms use either Global Positioning System, radio based lateration techniques, or both. These techniques suffer from three major issues, namely, flip ambiguities, location information exchange (beacon) overhead, and forged relative location information. The accuracy of vehicle localization algorithms at the early iterations is primarily affected by flip ambiguities, which in turn result in erroneous initial location estimates. The errors from flip ambiguities are a monotonically increasing function of time and propagated to the subsequent iterations to build an erroneous neighbor vehicle map. Rapid topology changes in highly mobile vehicular environments consume large amount of network bandwidth for location information exchange messages (beacons) among neighboring vehicles. This result in lack of bandwidth and causes serious concerns for time critical applications in autonomous vehicles. Forged relative location information that are generated by fake GPS signals and malicious attacks such as Sybil and Wormholes from vehicle ad hoc network attackers create hostile environment for autonomous driving. In this dissertation, a novel GPS free neighbor-vehicle localization framework is proposed based on Kings graph theory for efficient management of neighbour vehicle information. First, in Chapter 2, a basic framework is developed by representing a vehicles neighborhood region and neighborhood topology using the Moore neighborhood and Kings graph, respectively. Kings graph based neighborhood information overlap measure algorithm is introduced for neighbor mapping by exploiting the perspective symmetric properties of the Moore neighborhood. Performance analysis and simulation results show that the proposed algorithm builds an accurate relative neighbour vehicle map and outperforms trilateration and multilateration based methods in mitigating flip ambiguities and location information exchange overhead. Second, in Chapter 3, the proposed framework is extended to support cooperative collision warning system for vehicle clusters by studying perspective geometric structures formed among one hop neighbors. From simulation results, the variations in link weights of Kings graph of perspective geometric structures formed by one hop neighbors are analyzed and shown that the usage of link weights in identifying potential collision situations holistically for neighbor clusters. Last, in Chapter 4, the flipping errors generated by the proposed information overlap measure algorithm are investigated. One of the major causes of the flipping errors is due to the inability in handling the presence of more than one target vehicle in the corner regions of the host vehicles Moore neighborhood. A new information overlap measure algorithm is introduced by shifting information among Moore neighborhood cells. The new algorithm reduces the flip errors by 50%.