King's Graph-Based Neighbor-Vehicle Mapping Framework

Vehicle localization algorithms aim to provide an accurate location estimation of neighbor vehicles for critical applications in intelligent vehicles. For the initial location estimation, localization algorithms use either Global Positioning System (GPS), 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 these 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. In this paper, we propose a novel GPS-free neighbor-vehicle mapping framework that provides reliable initial relative position estimates of neighbor vehicles and mitigates aforementioned issues. This framework uses presence/absence status information of neighbor vehicles in binary form from a vision-based environment sensor system to associate each vehicle's cardinal location with its identification information, such as media access control (MAC)/Internet Protocol addresses. We represent a vehicle's neighborhood region and neighborhood topology using the Moore neighborhood (MN) and King's graph (KG), respectively, by analyzing a typical vehicle formation in a multilane roadway. We also introduce a KG-based neighborhood information overlap measure (IOM) algorithm for neighbor mapping by exploiting the perspective symmetric properties of the MN. Performance analysis and simulation results show that the proposed algorithm builds an accurate relative neighbor-vehicle map and outperforms trilateration- and multilateration-based methods in mitigating flip ambiguities and location information exchange overhead.