학위논문 (박사)-- 서울대학교 대학원 : 전기·컴퓨터공학부, 2014. 8. Seung-Woo Seo. ; 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 King’s graph theory for efficient management of neighbour vehicle information. First, in Chapter 2, a basic framework is developed by representing a vehicle’s neighborhood region and neighborhood topology using the Moore neighborhood and King’s graph, respectively. King’s 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 King’s 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 vehicle’s 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%. ; 1 Introduction 8 1.1 Background and Motivations 8 1.2 Contributions and Outline of the Dissertation . . . . . . . . . 13 1.2.1 Kings graph based Neighbor-Vehicle Mapping Framework 13 1.2.2 Perspective Location Grid based Cooperative Collision Warning Framework for Vehicle Clusters . . . . . . . . 14 1.2.3 Extended Information Overlap Measure Algorithm . . 15 2 Kings Graph Based Neighbor-Vehicle Mapping Framework 17 2.1 Introduction 17 2.1.1 Assumptions . 22 2.1.2 Contribution . 23 2.1.3 Chapter Organisation 25 2.2 Related Work. 26 2.3 Kings Graph based Neighborhood Representation . . . . . . 29 2.3.1 Problem Definition 29 2.3.2 Topology Representation: Kings Graph Topology . . 30 2.3.3 Information Representation: Perspective Location Grid Information 35 2.3.4 Information Generation: Perspective Location Grid Measurements. 36 2.4 Kings Graph based Neighbor Vehicle Mapping algorithm . . 42 2.4.1 Generic Information Overlap Algorithm (GIOM) . . . 42 2.5 Neighbor Mapping with Minimum Information using Information Overlap Measure 48 2.5.1 Vehicle presence feature . 49 2.5.2 Methods for bigger cluster mapping using vehicle presence feature 52 2.6 Performance Analysis. 56 2.6.1 Overlapping limitation in subordinate subsections . . . 56 2.6.2 Simulation. 60 2.6.3 Performance metric 63 2.7 Summary . 72 3 Perspective Location Grid based Cooperative Collision Warning Framework for Vehicle Clusters 74 3.1 Introduction 74 3.1.1 Assumptions . 78 3.1.2 Contribution . 79 3.1.3 Chapter Organisation 79 3.2 Related Work. 80 3.3 Pre crash Scenarios and Perspective Geometric Structure . . . 81 3.4 System Model. 85 3.4.1 Basic Framework. 85 3.4.2 Perspective Geometric Shape in PLG. . . . . . . . . . 88 3.4.3 Kings Graph Construction with unit link weight . . . 88 3.4.4 Algorithm. 89 3.5 Simulation Results 91 3.5.1 Simulation environment and approach . . . . . . . . . 91 3.6 Summary . 94 4 Extended Information Overlap Measure Algorithm for Neighbor Vehicle Localization 4.1 Introduction .96 4.1.1 Assumptions .98 4.1.2 Chapter Organisation .99 4.2 Extended Information Overlap Measure Algorithm . . . . . . 99 4.2.1 Limitations of existing IOM algorithm . . . . . . . . . 99 4.2.2 Information overlap measure by information shifting . 101 4.3 Performance Evaluation .102 4.3.1 Simulation results and analysis . . . . . . . . . . . . . 104 4.4 Summary . 105 5 Conclusion 106 5.1 Limitations and Scope for FutureWork . . . . . . . . . . . . 107 A Moore neighborhood - Kings graph Correspondence 110 A.1 Kings Graph .110 A.2 Basic Definitions .111 A.3 Kings Graph Neighborhood.113 A.4 Clustering Coefficient of K33 Kings Graph . . . . . . . . . . 113 A.5 GTOM for K33 .114 A.6 K33 Kings Graph Correspondence to Moore Neighborhood . 115 ; Doctor


    Access

    Download


    Export, share and cite



    Title :

    King's Graph Based Neighbor Vehicle Localization Framework ; 킹스 그래프 기반 인접 차량 측위 프레임워크



    Publication date :

    2014-01-01


    Type of media :

    Theses


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    629



    King's Graph-Based Neighbor-Vehicle Mapping Framework

    Punithan, M X | Online Contents | 2013


    King's Graph-Based Neighbor-Vehicle Mapping Framework

    Punithan, M. Xavier / Seo, Seung-Woo | IEEE | 2013


    그리드 프레임워크 구조물

    COGLEY WILL / NOAR BENJAMIN ARTHUR PORTNOY / MILLWARD STEPHEN et al. | European Patent Office | 2023

    Free access

    격자 프레임워크 구조물

    INGRAM TEDD ANDREW / MILLWARD STEPHEN | European Patent Office | 2023

    Free access

    그리드 프레임워크 구조물

    NOAR BENJAMIN ARTHUR PORTNOY / KAROLINCZAK PAWEL / INGRAM TEDD ANDREW et al. | European Patent Office | 2023

    Free access