Adaptive Connectivity Aware Routing Protocol for Wireless Vehicular Networks by Qing Yang A dissertation submitted to the Graduate Faculty of Auburn University in partial fulfillment of the requirements for the Degree of Doctor of Philosophy Auburn, Alabama May 9, 2011 Keywords: Network Connectivity Model, Vehicular Networks, Vehicle to Vehicle Communications, Connectivity-Aware Routing, Location Privacy Protection Copyright 2011 by Qing Yang Approved by Alvin Lim, Chair, Associate Professor, Computer Science and Software Engineering David Umphress, Associate Professor, Computer Science and Software Engineering Xiao Qin, Associate Professor, Computer Science and Software Engineering Wei-Shinn Ku, Assistant Professor, Computer Science and Software Engineering Abstract Multi-hop vehicle-to-vehicle communication is useful for supporting many vehicular appli- cations that provide drivers with safety and convenience. Developing multi-hop communication in vehicular ad hoc networks (VANETs) is a challenging problem due to the rapidly changing topology and frequent network disconnections, which cause failure or inefficiency in traditional ad hoc routing protocols. We propose an adaptive connectivity aware routing (ACAR) proto- col that addresses these problems by adaptively selecting an optimal route with the best network connectivity-quality (CQ) based on statistical and real-time density data that are gathered through an on-the-fly density collection process. The CQ metric models the joint probability that a network is connected and a packet is successfully delivered in this network. The protocol consists of two parts: 1) select an optimal route, consisting of road segments, with the best CQ, and 2) in each road segment of the chosen route, select the most efficient multi-hop path that will improve the deliv- ery ratio and throughput. The optimal route is selected using our connectivity-quality metric that takes into account vehicles densities and traffic light periods to estimate the probability of network connectivity and data delivery ratio for transmitting packets. Our simulation results show that the proposed ACAR protocol outperforms existing VANETs routing protocols, e.g. the delivery ratio of ACAR is 19% higher than VADD, the second best protocol. ACAR is built upon geographic routing which requires every vehicle to broadcast its location information to its neighbors, and this process will compromise user?s location privacy. To address this issue, we proposed a dummy-based location privacy protection (DBLPP) protocol in VANETs. In DBLPP, routing decision is made based upon the dummy distance to destination (DOD), instead of user?s true location. In this scheme, a user?s true location and identification information are preserved, so the user?s location privacy is protected. Simulation results show that the DBLPP provides similar network performances as other routing protocols, and achieves a higher level of ii location privacy protection on vehicles in networks. This location privacy protection scheme can be easily added to other geographic routing protocols. iii Acknowledgments I am heartily thankful to my supervisor, Dr. Alvin S. Lim, for his academic guidance, gener- ous advice, his sharp comments and support, during our many discussions. I am very appreciative of his encouragement and patience when things seemed fuzzy. Without his support, this thesis would not have been completed. It has been a privilege working with him. I would like to thank to my committee members: Dr. David Umphress, Dr. Xiao Qin, Dr. Wei-shin Ku for their time, patience and suggestions that led to me improving this work. I owe my deepest gratitude to Dr. Kai Chang and Dr. Qin for supporting me attending conferences, to Dr. Umphress and Dr. Ku for helping me in my job hunting. Special thanks to Dr. Prathima Agrawal for the knowledge I have gained through the Wireless Seminars and years of research we had started. I thank her for her continuous support since I came to Auburn University, her kindness, time, and collaboration. It is Dr. Prathima Agrawal who directed me to study the area of wireless vehicular networks at the time when I started my Ph.D program. I am deeply indebted to my family, who has always supported me, and especially to my parents and my sister Liu Yang for their love, guidance and vision. I believe I have been blessed by the God for granting me such wonderful and supportive family. Finally, special thanks to my beloved wife Tiantian Wang. It is her love and support that makes this dissertation possible. iv Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x List of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Background and Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1 Wireless Vehicular Ad Hoc Network . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Applications of VANETs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3 Characteristics of VANETs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.4 Technical Challenges in VANET . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3 Problem Statement and Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1 Problem Statement of Routing in VANETs . . . . . . . . . . . . . . . . . . . . . . 11 3.2 Issues of Existing Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.3 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.1 Routing Protocols in Connected Networks . . . . . . . . . . . . . . . . . . . . . . 19 4.2 Routing Protocols in Intermittent Connected Networks . . . . . . . . . . . . . . . 20 4.3 Network Connectivity Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.4 Location Privacy Protection in VANET . . . . . . . . . . . . . . . . . . . . . . . . 24 5 Connectivity-Quality Model in VANETs . . . . . . . . . . . . . . . . . . . . . . . . . 26 5.1 Cell Based Connectivity Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5.1.1 Empty-Cell Probability P1 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 v 5.1.2 Successive Empty-Cell Probability P2 . . . . . . . . . . . . . . . . . . . . 29 5.2 Cluster Based Connectivity Model . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.3 Integrated Connectivity Model of Road Segment . . . . . . . . . . . . . . . . . . 33 5.4 Connectivity Model of Route . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.4.1 Vehicle?s Distribution around Intersections . . . . . . . . . . . . . . . . . 36 5.4.2 Connectivity Probability Without Stopped Vehicles P3 . . . . . . . . . . . 38 5.4.3 Connectivity Probability With Stopped Vehicles P4 . . . . . . . . . . . . . 40 5.5 Connectivity-Quality of Route . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.5.1 Date Delivery Ratio of Road Segment . . . . . . . . . . . . . . . . . . . . 42 5.5.2 Connectivity-Quality Metric . . . . . . . . . . . . . . . . . . . . . . . . . 46 6 Adaptive Connectivity Aware Routing Algorithm . . . . . . . . . . . . . . . . . . . . 48 6.1 Selection of Route with the Highest Connectivity-Quality . . . . . . . . . . . . . . 48 6.2 Velocity Compensated Neighbor Location Prediction . . . . . . . . . . . . . . . . 51 6.3 Adaptive Route Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 6.4 On-The-Fly Density Collection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 6.5 Next Hop Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 7 Simulations and Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 7.1 Mobility of Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 7.2 Digital Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 7.3 Networking Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 7.4 Data Delivery Ratio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 7.5 Reasons of Packet Loss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 7.5.1 Expired Packets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 7.5.2 Wireless Transmission Loss . . . . . . . . . . . . . . . . . . . . . . . . . 65 7.5.3 Buffer Overflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 7.6 End-to-End Delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 7.7 Network Throughput . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 vi 7.8 Impact of Network Density . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 7.8.1 Data Delivery Ratio with Different Network Densities . . . . . . . . . . . 72 7.8.2 Network Delay with Different Network Densities . . . . . . . . . . . . . . 73 7.8.3 Delay Distributions of Different Protocols . . . . . . . . . . . . . . . . . . 74 7.9 Impact of Velocity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 7.10 Networking Overhead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 8 Location Privacy Protection in VANET . . . . . . . . . . . . . . . . . . . . . . . . . . 80 8.1 Introduction of Location Privacy Issues in VANET . . . . . . . . . . . . . . . . . 80 8.2 Threat Model and Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . 82 8.2.1 Threat Model in VANET . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 8.2.2 Greedy Forwarding Model . . . . . . . . . . . . . . . . . . . . . . . . . . 83 8.2.3 Problem Statement of Location Privacy Protection in Greedy Forwarding . 83 8.3 Details of DBLPP Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 8.3.1 Control Messages Exchange in DBLPP . . . . . . . . . . . . . . . . . . . 85 8.3.2 Duplicated Responses and Location Privacy Protection . . . . . . . . . . . 88 8.4 Entropy Based Privacy Protection Measure . . . . . . . . . . . . . . . . . . . . . 92 8.5 Simulations of DBLPP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 8.5.1 Data Delivery Ratio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 8.5.2 End-to-end Delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 8.5.3 Network Throughput . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 8.5.4 Location Privacy Protection . . . . . . . . . . . . . . . . . . . . . . . . . 101 9 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 vii List of Figures 3.1 Illustration of the Issues in Existing Routing Protocols in VANETs . . . . . . . . . . . 15 5.1 Illustration of Traffic Lights Affecting the Connectivity Model . . . . . . . . . . . . . 31 5.2 Network Connectivity around Intersections with Stopped Vehicles . . . . . . . . . . . 37 5.3 Network Connectivity around Intersections without Stopped Vehicles . . . . . . . . . 38 5.4 Network Disconnection around Intersections with a Uniform Node Distribution . . . . 39 5.5 All Stopped Vehicles Move Away from Intersection . . . . . . . . . . . . . . . . . . . 40 5.6 Illustration of the Number of Potential Interfering Nodes . . . . . . . . . . . . . . . . 44 6.1 Illustration of Route Selection Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 50 6.2 On-the-fly Density Collection Mechanism . . . . . . . . . . . . . . . . . . . . . . . . 53 7.1 A VanetMobiSim Snapshot of Connectivity Model Validations . . . . . . . . . . . . . 57 7.2 Validation of Connectivity Model with Road = 1000m, Velocity = 5m/s and Traffic light = 120s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 7.3 Validation of Connectivity Model with Road = 1000m, Velocity = 7.5m/s and Traffic Light = 60s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 7.4 Validation of Connectivity Model with Road = 1000m, Velocity = 7.5m/s and Traffic Light = 120s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 7.5 Validation of Connectivity Model with Road = 1800m, Velocity = 10m/s and Traffic Light = 60s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 7.6 Validation of Connectivity Model with Road = 1800m, Velocity = 7.5m/s and Traffic Light = 60s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 7.7 Validation of Connectivity Model with Road = 1800m, Velocity = 10m/s and Traffic Light = 120s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 7.8 Street Layout of the Area Centered at (35162102,?84877562) in the Tennessee State . 61 viii 7.9 Data Delivery Ratio in the Scenario I . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 7.10 Fraction of Packets Still in Buffers After Terminating Simulations . . . . . . . . . . . 65 7.11 Fraction of Dropped Packets Due to Weak Wireless Links . . . . . . . . . . . . . . . 66 7.12 Fraction of Dropped Packets Due to Buffer Overflow . . . . . . . . . . . . . . . . . . 67 7.13 End-to-end Network Delay in the Scenario I . . . . . . . . . . . . . . . . . . . . . . . 68 7.14 Network Throughput in the Scenario I . . . . . . . . . . . . . . . . . . . . . . . . . . 70 7.15 Data Delivery Ratio vs Number of Nodes in the Scenario II . . . . . . . . . . . . . . . 71 7.16 End-to-end Delay vs Number of Nodes in the Scenario II . . . . . . . . . . . . . . . . 72 7.17 Delay Distribution of Received Packets with 40 Nodes in the Networks . . . . . . . . 74 7.18 Delay Distribution of Received Packets with 100 Nodes in the Networks . . . . . . . . 75 7.19 Data Delivery Ratio vs Different Velocities with 100 Nodes in the Networks . . . . . . 76 7.20 End-to-end Delay vs Different Velocities with 100 Nodes in the Networks . . . . . . . 77 7.21 Number of Packets Sent in Networks Per Delivered Packet with 100 Nodes in the Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 7.22 Size of Packets Sent in Networks Per Delivered Packet with 100 Nodes in the Networks 79 8.1 Dummy Based RTF/CTF Exchange Among Vehicles . . . . . . . . . . . . . . . . . . 86 8.2 State Machine Of Nodes in DBLPP . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 8.3 Duplicated Responses and Duplication Area . . . . . . . . . . . . . . . . . . . . . . . 90 8.4 Dummy DOD Selection On Packet Forwarder . . . . . . . . . . . . . . . . . . . . . . 91 8.5 Matrix Recording Possible Node Identifications And Locations . . . . . . . . . . . . . 93 8.6 Data Delivery Ratio Vs Data Sending Rate for DBLPP . . . . . . . . . . . . . . . . . 98 8.7 End-to-end Delay Vs Data Sending Rate for DBLPP . . . . . . . . . . . . . . . . . . 99 8.8 Network Throughput Vs Data Sending Rate for DBLPP . . . . . . . . . . . . . . . . . 100 8.9 Average Entropy of Location Privacy Protection . . . . . . . . . . . . . . . . . . . . . 101 ix List of Tables 4.1 Summary of Unicast Routing Protocols Assuming Connected VANETs . . . . . . . . 20 4.2 Summary of VANET Unicast Routing Protocols for Intermittent Connected Networks . 22 7.1 Simulation Set-Up Parameters for ACAR . . . . . . . . . . . . . . . . . . . . . . . . 62 8.1 Simulation Set-Up Parameters for DBLPP . . . . . . . . . . . . . . . . . . . . . . . . 97 x List of Abbreviations A-STAR Anchor-based Street and Traffic Aware Routing ACAR Adaptive Connectivity Aware Routing AODV Ad hoc On Demand Distance Vector ASTM American Society for Testing And Materials ASV Advanced Safety Vehicle BER Bit Error Rate BPSK Binary Phase Shift Keying CAR Connectivity Aware Routing CBF Contention Based Forwarding CBF-AS Contention Based Forwarding - Active Selection CQ Connectivity-Quality CSM Constant Speed Motion CTF Clear To Forward CTS Clear To Send DBLPP Dummy Based Location Privacy Protection DOD Distance To Destination DSR Dynamic Source Routing DSRC Dedicated Short Range Communications EDD Expected Disconnection Degree ETX Expected Transmission Count FCC Federal Communications Commission FER Frame Error Rate xi FTM Fluid Traffic Motion GeOpps Geographical Opportunistic Routing GPS Global Positioning Systems GPSR Greedy Perimeter Stateless Routing GSR Geographic Source Routing IDM Intelligent Driver Model IDM-IM Intelligent Driver Model with Intersection Management IDM-LC Intelligent Driver Model with Lane Changing LOS Line Of Sight MAC Multiple Access Control MANET Mobile Ad hoc Networks MDDV Mobility-Centric Data Dissemination Algorithm for Vehicular Networks MOVE Motion Vector MURU Multi-hop Routing for Urban VANET NLOS Non Line Of Sight NLP Neighbor Location Prediction OEM Original Equipment Manufacturer OFDM Orthogonal Frequency-Division Multiplexing OPERA Opportunistic Packet Relaying Protocol PATH California Partners for Advanced Transit and Highways PER Packet Error Rate PHY Physical Layer RREQ Route Request RTF Request To Foward RTS Request To Send xii SADV Static Node Assisted Adaptive Routing SINR Signal to Interference plus Noise Ratio SKVR Scalable Knowledge Based Routing TIGER topologically Integrated Geographic Encoding and Referencing TSIS-CORSIM Traffic Software Integrated System - Corridor Simulation V2I Vehicle To Infrastructure V2V Vehicle To Vehicle VADD Vehicle Assisted Data Delivery VANET Vehicular Ad Hoc Networks VanetMobiSim VANET Mobility Simulator WAVE Wireless Access in Vehicular Environments WiMAX Worldwide Interoperability for Microwave Access WLAN Wireless Local Area Network xiii Chapter 1 Introduction Wireless communication among moving vehicles is increasingly the focus of research in both of the academic community and automobile industry, driven by the vision that exchange of infor- mation among vehicles can be exploited to improve the safety and comfort of drivers and passen- gers [1?4]. Some automobile manufacturers have equipped their new vehicles with global position- ing systems (GPS), digital maps and even wireless interfaces, e.g. Honda-ASV3. In addition, the federal communications commission (FCC) has allocated 75MHz of spectrum in the 5.9GHz band for vehicle-vehicle and vehicle-roadside communication, called dedicated short range communi- cations (DSRC). IEEE is also working on the IEEE 1609 family of standards for wireless access in vehicular environments (WAVE), which define an architecture and a complementary, standardized set of services and interfaces that collectively enable secure vehicle-to-vehicle (V2V) and vehicle- to-infrastructure (V2I) wireless communications. Although IEEE 1609.3 considers the networking layer and provides an alternative for IPv6, it does not define the ad hoc routing protocol between vehicles, and has left this issue open. Though several technical problems need to be solved before installing vehicular networks; in the near future, large scale vehicular networks will be available to provide people with more conveniences in their driving experience. For example, through such networks, people can query the price and services provided by gas stations in a certain region, or remotely control their smart- houses [5] while driving home. Drivers can even download a real-time traffic image from a traffic camera located at a certain point, or connect to access points of parking lots to inquire the number of available parking slots. These types of applications could tolerate some delay, e.g. a few min- utes. If the information could be successfully retrieved from the remote server, it would be very helpful and desirable to drivers. 1 To realize this vision, we must first select the most appropriate architecture. There are three broad categories of network architectures: infrastructure-based, ad hoc networks and hybrid. The infrastructure-based architecture takes advantage of the roadside infrastructure or existing cellular networks. However, a big issue of such networking is the high operation cost. Moreover, the cellu- lar networks have other drawbacks such as the limited bandwidth and symmetric channel allocation for up-link and down-link. Ad hoc networks do not need infrastructure, so the cost of building such network will be very low and it can even operate in the event of disasters. The hybrid architecture is more practical which combines these two architectures by considering vehicles as data relays between roadside base-stations [6, 7]. This architecture also requires the function of multi-hop communication between vehicles, which is the essential part of ad hoc network architecture. This work focuses on the vehicular ad hoc network (VANET) architecture with the flexible deployment and self-organizing capabilities. Due to special characteristics of VANETs, traditional routing protocols in wireless ad hoc networks may not be suitable for vehicular communications. For example, DSR [8] and AODV [9] are not suitable for VANETs because of the large route maintenance overhead. Therefore, some variants of stateless geographic routing protocols, such as [10,11], may be better choices. However, even with geographic routing, many of the following challenges still need to be addressed: 1. Dynamic and rapidly changing topologies of vehicular networks can cause frequent commu- nication disconnections among vehicles. As revealed in [12], the frequent network discon- nection is the most important issue in designing protocols for VANETs. 2. Geographic forwarding protocols select the shortest route (minimal number of hops) that may suffer from a higher packet error rate due to the poor link quality of each hop. 3. The uneven distribution of vehicles on the roads makes route selection more complex, e.g. the shortest path in terms of geographic distance may experience more frequent network disconnections. 2 4. Some protocols [13,14] make use of the density information on roads to select routes but the inaccuracy of statistical data may cause routes to be incorrectly computed. 5. Because of obstacles to wireless signal by large objects, e.g. skyscrapers in cities, commu- nication between vehicles must have line-of-sight. To address these problems, we propose a new routing protocol called adaptive connectivity aware routing (ACAR). There are three main contributions in this work. First, based on the sta- tistical information on the road, we propose a connectivity model that provides the probability of network connectivity on a road segment. This connectivity model also takes into account the phenomena that (red) traffic lights can block approaching vehicles and those nodes will move as a platoon in the next road segment. Second, we introduced a novel metric, connectivity-quality (CQ), which combines the network connectivity probability and data delivery ratio of packets be- ing forwarded along a road segment. Third, as the statistical data may not be accurate, an on-the-fly information collection algorithm is developed to help ACAR adaptively select the best route. Geographic routing provides superior scalability and thus is widely used in VANETs. How- ever, it requires every vehicle to broadcast its location information to its neighboring nodes, and this process will compromise user?s location privacy. To address this issue, we proposed a dummy- based location privacy protection (DBLPP) routing protocol, in which routing decision is made based upon the dummy distance to the destination (DOD), instead of users? true locations. In this scheme, users? true locations and identification information are preserved, so the user?s location privacy is protected. This dissertation is organized as follows: It presents the background and motivations for ve- hicular networks in Chapter 2 and proposes the problem statement and objectives to be achieved in Chapter 3. Chapter 4 reviews existing routing protocols for VANETs. In Chapter 5, the net- work connectivity in VANETs is fully investigated and an integrated connectivity model for a path that is composed of multiple road segments is proposed. Chapter 6 shows in detail how the proposed routing protocol are designed and implemented. The evaluation and analysis of the pro- posed protocol are explored in Chapter 7. To further investigate the location privacy protection 3 in geographic routing, a dummy based location privacy preservation mechanism is proposed and evaluated in Chapter 8. The integration of ACAR and DBLPP is considered as our future work which is described in Chapter 9. Finally, Chapter 10 concludes this dissertation. 4 Chapter 2 Background and Motivations 2.1 Wireless Vehicular Ad Hoc Network Wireless vehicular ad hoc network is a novel wireless network that emerges because of the advances in wireless technologies and the automotive industry. VANETs are spontaneously formed between moving vehicles equipped with wireless interfaces that could be of homogeneous or het- erogeneous technologies. VANETs are considered as one real-life application of mobile ad hoc network which enables communications among nearby vehicles as well as between vehicles and roadside infrastructures. Vehicles can be either private (e.g. individuals cars) or from public transportation (e.g., buses and police car). The history of using radio and infrared communications between vehicles and infrastructures is strongly tied to the evolution of intelligent transportation systems. In 1939?s World Fair, the use of communication and control techniques to make road traffic safe, efficient and environmentally friendly were first exhibited by the General Motors. From then, the interest in vehicle-to-vehicle communication continued in Japan, USA and Europe, but there were not many successful projects during this time period. Until the second half of the 1990s, many impressive projects on vehicular networks occurred because of the rapid development of wireless technology. For example, the California partners for advanced transit and highways (PATH) in 1997, the advanced safety vehicle (ASV) in 2000 in Japan, and the CarTalk and FleetNet projects investigated in Europe. The concept of VANET was dramatically impacted by the advances in wireless technology and standardization since the late 1990s. The ?game changer? occurred when the US Federal Communication Commission allocated 75 MHz bandwidth of the 5.9 GHz band for vehicle-to-vehicle and vehicle-to-infrastructure wireless 5 communication in 1999. The commission then established the service and license rules for DSRC Service which defines the communication service working on the 5.850-5.925 GHz band for the public safety and private applications in vehicular networks. In 2001, the ASTM International se- lected IEEE 802.11a as the underlying radio technology of DSRC. The pressure to make use of the assigned channels and the availability of the IEEE 802.11a technology and standard significantly increased research and development activities. In 2004, the IEEE started the work on the 802.11p amendment and wireless access in vehicular environments (WAVE) standards based on the ASTM standard. From 2004 until now, wireless communication among moving vehicles becomes the focus of researches in both of the academic research community and automobile industry. 2.2 Applications of VANETs Vehicular network applications range from road safety oriented applications for vehicles or drivers, to entertainment and commercial applications for passengers, making use of a plethora of cooperating technologies. The primary vision of vehicular networks includes real-time and safety applications for drivers and passengers, providing safety for the latter and giving essential tools to decide the best path along the way. These applications thus aim to minimize accidents and improve traffic conditions by providing drivers and passengers with useful information including collision warnings, road sign alarms, and in-place traffic view. Nowadays, vehicular networks are promising in a number of useful driver- and passenger- oriented services, which include Internet connections facility exploiting an available infrastructure in an on-demand fashion, electronic tolling system, and a variety of multimedia services. Fur- thermore, a variety of communication networks, such as 2-3G, WLANs IEEE 802.11a/b/g, and WiMAX, can be exploited to enable new services designed for passengers apart from the safety applications, such as info-mobility and entertainment applications, which can rely on the vehicular network itself. 6 Regarding the discussed applications? potential, vehicular networks open new business op- portunities for car manufacturers, automotive OEMs, network operators, service providers, and integrated operators in terms of infrastructure deployment as well as service provision and com- mercialization. For safety-related applications, the network operator can assure the authentication of each participant through playing the role of a trusted third party that authenticates the participating nodes, or even having the role of a certification authority issuing a certificate to each participant in order to prove their authenticity later during the communication. On the other hand, in non-safety related applications, network operators and/or service providers, besides network access and service provision, can have the role of authorizing service access and billing users for the consumed services. However, one should notice that ad hoc systems still require a certain level of penetration and necessitate high vehicle density for more reliable com- munication. The investment cost for new communication infrastructure for vehicular networks will be rel- atively high. On the other hand, cellular communication systems offer a high coverage along roads and have a reliable authentication and security mechanism. Consequently, number of technical challenges needs to be resolved in order to help the evolution of vehicular networks for wide-scale deployment. 2.3 Characteristics of VANETs Vehicular ad hoc networks share many common characteristics with general mobile ad hoc networks (MANET). Both VANET and MANET are self-organizing wireless ad hoc networks that are composed of mobile nodes. However, they are different in several ways. For example, vehicles can recharge their batteries frequently which usually can last much longer than batteries in regular mobile devices. However, vehicles? movements can be constrained by the road topology and traffic rules. In MANET, nodes cannot recharge their power and the energy efficiency is also critical in such networks. In addition, the nodes? movements in MANET are assumed to follow unrestricted 7 patterns of movements. In comparison to other communication networks, vehicular networks come with unique beneficial features, as follows: 1. Unlimited transmission power: The power issue of mobile devices is usually not a significant one in VANET as that in the classical ad hoc or sensor networks. Vehicle itself can provide continuous power to computing and communication devices. Usually, the car battery can last much longer compared to those for hand-held mobile devices. 2. Higher computational capability: Vehicles can be installed with significant computing, com- munication, and sensing capabilities which can be even more powerful than regular desktops. 3. Predictable mobility: Unlike conventional mobile ad hoc networks in which node mobility is hard to predict, vehicles in VANETs tend to move in a predictable way that is (usually) lim- ited to street topology. Roadway information is often available from navigation systems and map-based technologies such as GPS. Given the average number of nodes, average speed, number of lanes, the future position of a vehicle may be predicted. However, to bring its potency to fruition, vehicular networks have to cope with some chal- lenging characteristics including: 1. Potentially large scale: Unlike most ad hoc networks studied in the literature that usually assume a limited network size, vehicular networks can in principle extend over the entire road network and so include many participants. 2. High mobility: The environment in which vehicular networks operate is extremely dynamic, and includes extreme configurations: on highways, relative speeds of up to 300 km/h may occur, while density of nodes may be 1-2 vehicles per kilometers on less busy roads. On the other hand, in the city, relative speeds can reach up to 60 km/h and network density can be very high, especially during rush hours. 8 3. Partitioned network: Vehicular networks will be frequently partitioned. The dynamic nature of traffic may result in large inter-vehicle gaps in sparsely populated scenarios, and hence in several isolated clusters of nodes. 4. Network topology and connectivity: Vehicular network scenarios are very different from classic ad hoc networks. Since vehicles are moving and changing their position constantly, scenarios are very dynamic. Therefore the network topology changes frequently as the links between nodes connect and disconnect very often. Indeed, the degree to which the network is connected is highly dependent on two factors: the range of wireless links and the fraction of participant vehicles, where only a fraction of vehicles on the road could be equipped with wireless interfaces. 2.4 Technical Challenges in VANET VANET has special behavior and characteristics, so there are several challenges for vehicular communication which greatly impact the future deployments of such networks. Many challenges need to be resolved in order to deploy vehicular networks in our real lives such as information dissemination, security and privacy, and Internet integration. Generally speaking, efficient wireless communication is an important issue, so the employed protocols and mechanisms should be robust, reliable and scalable to numerous vehicles. VANET differs from conventional ad hoc networks by not only experiencing rapid changes in wireless links, but also having to deal with different network densities. For instance, vehicular networks in urban areas are more likely to form highly dense networks during rush hour traf- fic. However, vehicular networks are expected to experience frequent network disconnections in sparsely populated rural highways or during late night hours. Moreover, VANET is expected to handle a wide range of applications ranging from safety to leisure. Consequently, routing algorithms should be efficient and cope to vehicular network characteristics and applications. Until now, most of research has focused on analyzing routing 9 algorithms in highly dense networks with the assumption that a typical vehicular network is well- connected in nature. Actually, the penetration of vehicles with wireless communication capacity is somewhat weak. Therefore, a VANET should rely on existing infrastructure supports for wide- scale deployment. However, VANET are expected in the future to observe high penetration with lesser infrastructures, and hence it is important to consider the disconnected network problem. Network disconnection in VANET is a crucial research challenge for developing a reliable and efficient routing protocol. 10 Chapter 3 Problem Statement and Assumptions Vehicular network is a dynamic mobile network in which network disconnection occurs very often, which causes most traditional routing protocols to fail in delivering packets. To address this issue, buffer is used on each vehicle so that packets can be stored when network disconnection occurs and delivered if the network re-connects. However, one drawback of using buffer is that it will cause huge network delay. Therefore, how to reduce such delay and achieve and higher network throughput is a non-trivial issue. 3.1 Problem Statement of Routing in VANETs A vehicular ad hoc network can be modeled as a graph G = {V,E}, where V is the set of vehicles (nodes) and E is the set of edges that represent wireless links. The set E will change from time to time due to vehicles? movements. According to [15], we can define a set of time intervals ?E, in which intervals are numbered as I1,???,Iq,???,Ih. Further, by construction Iq = [tq?1,tq) (and tq?1 < tq), we can define a set of time sequence. Therefore, the set ?E partitions the interval [t0,th) into h pieces. For an interval I = [a,b) and r ? R+, we let I?r denote the (shifted) interval [a + r,b + r). Then, we further define a few other variables. ? c : E?R+ ?R+, where ce,t is the capacity of the edge e?E at time t ? d : E?R+ ?R+, where de,t is the transmission delay of the edge e at time t ? bv is the storage capacity of the node v?V ? Iv is the set of edges whose destination node is v (incoming edges) ? Ov is the set of edges whose source node is v (outgoing edges) 11 Because a buffer is needed to store packet when network disconnection occurs in VANETs, we need to define the buffer capacity bv. We also define K as a set of messages injected into the network from a source to a destination. For a certain message k ? K, it can be denoted as a tuple (u,v,t) where (u,v) denotes the current and next-hop nodes, t is the time instance when the message is sent from u to v. The functions s(K), d(K), ?(K), m(K) are used to retrieve the source node, the destination node, the start time, and the number of messages in K, respectively. Moreover, the following definitions capture the states and transitions in the network. ? NKv,t is the number of messages (in K) occupying the buffer at node v at time t??E ? XKe,I is the number of messages transmitted (at the tail of the edge) over edge e during I??E ? RKe,I is the number of messages received (at the destination of the edge) over edge e during I??E ? Kv ={k|k?K,d(k) = v}is the set of messages whose destination node is v The transmission variables (denoted by X) and the reception variables (denoted by R) are used together to model the transmission delay encountered in sending messages. The natural ob- jective is to maximize the probability of message delivery. However, since a buffer is used to store messages while network disconnection occurs, the messages will eventually be delivered unless the buffer overflows. Moreover, because of packets being buffered instead of transmitted immedi- ately, network delay is a big issue in VANETs. In this work, we focus on minimizing the delay of a message. So the objective function is to minimize the average delay, which can be realized by minimizing the sum of the delays for all messages. min summationdisplay v?V summationdisplay K?Kv summationdisplay Iq??E (tq?1??(K))?(summationdisplay e?Iv RKe,Iq? summationdisplay e?Ov XKe,Iq) (3.1) The summation summationtext e?Iv RKe,Iq represents the number of messages in K that are coming into the node v in the interval Iq. These messages could be forwarded from other nodes or generated by the current node which is the source of the messages During the time interval Iq, a portion of messages 12 may be transmitted to other nodes. This is accounted for by subtracting the term summationtext e?Ov XKe,Iq. The above difference is then multiplied by the delay of these messages (i.e. tq?1??(K)) to get the total delay suffered by that fraction of messages that arrived in the interval Iq at node v. Finally, we sum over all the possible intervals for all messages and all nodes. The objective function should be subject to: summationdisplay e?Iv RKe,Iq? summationdisplay e?Ov XKe,Iq = ? ??? ??? NKv,tq ?NKv,tq?1 + m(K) if s(K) = v,?(K) = tq NKv,tq ?NKv,tq?1 otherwise (3.2) RKe,Iq?de,t q?1 = XKe,Iq (3.3) NKv,tq?1 ?bv (3.4) XKe,Iq ?ce,tq?1 ?|Iq| (3.5) NKv,t0 = ? ??? ??? m(K) if v = s(K),t0 = ?(K) 0 otherwise (3.6) NKv,th = ? ??? ??? m(K) if v = d(K) 0 otherwise (3.7) Equation 3.2 gives the flow constraints, i.e. the number of messages outgoing from node v plus those staying in the buffer should be equal to the number of messages incoming to node v. During a certain time period, if node v generates a new message, this message needs to be added to the buffer too. 13 Equation 3.3 relates the variables X and R by stating that the traffic transmitted at the initial point of e during Iq is equal to the traffic received at the end point of e during the time interval Iq?de,tq?1 (i.e. after the edge delay). Constraints are also needed to ensure that the number of messages that are stored at any node?s buffer does not exceed the specified limit, and the data sent over a link is limited by the edge capacity over that time interval. These are captured by Equation 3.4 and Equation 3.5. Finally, Equations 3.6 and 3.7 are the initial and the final conditions regarding the storage. Equation 3.6 says that in the beginning, only nodes that have messages to send have occupied buffers. Equation 3.7 states that at the end, only nodes that are destinations for messages have occupied buffers. We have modeled the routing problem in VANETs as a linear programming problem which can be solved mathematically given the value of all defined variables. However, it is impossible to obtain real-time global information of a VANET such as vehicles? positions, network links, and link capacities. Therefore, an approximate routing protocol is required. Therefore, how to design a routing protocol to maximize the probability of message delivery and minimize the network delay is the major concern of this work. 3.2 Issues of Existing Solutions The topology of VANETs has a unique characteristic ? it consists of one or more sub-graphs (one sub-graph if the network is fully connected) of the road map topology. Previous researches in wireless ad hoc networks often make an unrealistic assumption on nodes mobility. For example, with the most popular Random Way Point model, nodes can freely move within a certain area with randomly chosen velocities. However, nodes in VANETs do not have the ability to roam freely without regards to obstacles and traffic regulations, i.e. road segments containing vehicles construct the network topology of a VANET. Therefore, the problem of efficient routing of packets in VANETs can be transformed into selecting a route with the highest network throughput from the road map. A critical reason causing 14 Figure 3.1: Illustration of the Issues in Existing Routing Protocols in VANETs low network throughput is the network disconnection which occurs extremely often in VANETs. When network partition occurs, most existing routing protocols for vehicular networks will drop packets such as GPSR [10] and GSR [11]. Although VADD [13] uses carry-and-forward scheme to buffer packets if network is disconnected, the network connectivity information is not fully investigated. We note that network connectivity is the most important information for routing in VANETs, and then propose a connectivity aware routing protocol for VANETs. Consider the network situation shown in Fig. 3.1, where the source node at the bottom left corner is trying to send packets to the destination at the top right corner. In this figure, the lengths of road segment IAIBIC, IAIC, IAID and ICID are 1200m, 1000m, 707m and 707m, respectively. The numbers of nodes deployed on each above-mentioned road segment are 22, 9, 5 and 2, respectively. All vehicles move with the average velocity of 10m/s. 15 With the GPSR protocol, packets will be forwarded through a multi-hop route. An example route is depicted as dashed lines with arrows in this figure. Because the network density on road segment IAIC is very low, disconnections may occur frequently. For example, node n1 in Fig. 3.1 fails to communicate with node n2 as they are out of communication range. In this case, GPSR enters the perimeter mode and selects nodes on road segment IAID to forward packets. However, since network partitions are very common in VANETs, GPSR may face other network disconnec- tions again. For instance, because wireless signal may be blocked by objects, e.g. skyscraper in the city, the communication between node n3 and n4 may be impossible due to the absence of line-of-sight. That implies the GPSR protocol may take many detours to find connected route, e.g. on segment IAIBIC, after many perimeter mode searches. If there is no such connected route in networks, GPSR may search through the entire networks and finally fail to find a route. To make use of road map information, the geographic source routing (GSR) protocol [11] was proposed for VANETs. With this approach, road segment IAIC will be selected to forward the packets. Because the assumption of connected networks does not always hold, the GSR may fail to deliver packets when network partitions occur. If the carry-and-forward scheme [16] is added into GSR, packets can finally reach the destination. However, the delay of forwarding packets on this road segment will be higher than routing packets along IAIBIC. According to measurements in our simulations, the network connectivity probabilities of road IAIC and IAIBIC are .29 and .84, respectively. The .29 connectivity probability can be interpreted as the network is disconnected 71% of the time, so the network delay can be simply calculated as .71?(1000/v)+.29?(1000/c) where v is the average velocity of vehicles on road IAIC and c is the wireless transmission speed. As v ? c, the delay of forwarding packets along IAIC is delayAC ? (710/v). Similarly, the delay of forwarding packets on IAIBIC is .16?(1200/v)+.84?(1200/c)?(192/v). Therefore, routing packets along IAIBIC generates a much smaller delay than that of IAIC. In the motion vector (MOVE) [17] protocol, the packet carrier will select the next hop that is currently or will be closest to the destination; otherwise, it will carry (buffer) the packet until a next hop is available. It provides nine rules for current node to select the next hop, and one of 16 them states that if the current packet carrier is in AWAY state and one neighbor is in TOWARDS state, packets must be forwarded to this neighbor. For instance, as shown in Fig. 3.1, node n5 (moving away from the destination) will forward packets to n6 as it move toward the destination. However, if n6 moves over the vertical dashed line, it enters the AWAY state and will forward packets back to following vehicles that are in the TOWARDS state. This situation is so-called Ping-Pong effect which will not occur if no more following vehicles become available. However, this problem becomes worse when the network density is higher. To select a route with the minimal transmission delay, the vehicle-assisted data delivery (VADD) protocol is proposed for VANETs [13]. According to the protocol, since the network density on road IAIC is equal to 1/R, the delay of forwarding packets on IAIC is dAC = ??lAC where lAC = 1000m is the length of road IAIC and ? is a constant. Similarly, dAB = ??1000, so we have dAB = dAC. As stated in VADD, if the packet carrier (vehicle) at intersection IA chooses to deliver packets on road IAIB, the expected packet delivery delay from the intersection IA to the destination is: DAB = 11?P AB?PBA ?(dAB + PBA?dBA + PBA?PAC?dAC + PBC?dBC) (3.8) where PAB is the probability that the packet is forwarded through IAIB at intersection IA, which is smaller than 1. Since PAB?PBA < 1, we have DAB > (dAB +PBA?dBA + PBA?PAC?dAC + PBC?dBC), so DAB > dAB. On the other hand, since DAC = dAC = dAB, we obtain DAB > DAC. Therefore, road IAIC will be chosen by VADD to forward packets as it has the smallest expected delivery delay. However, the delay of sending packets along road IAIBIC is actually the lowest. In summary, to select the best route in VANETs, a proper model of the network connectivity is very important and it is determined by several factors such as network density, road length and number of lanes on roads. For a certain road segment, its network connectivity will be affected by many factors including network density, road segment length, average vehicle velocity, number of lanes and traffic light periods. Even if the probability of network connectivity of a road segment 17 is modeled, the network connectivity of a route that consists of several road segments is still a challenging problem. We cannot simply use the product of the probabilities of all road segments on the route because these probabilities are not independent of each others. In this work, we first model the network connectivity and then propose an approach to select the optimal route that can achieve the highest network throughput. 3.3 Assumptions As GPS and navigation systems are becoming standard equipment in vehicles, we assume every vehicle obtains its current location. We also assume vehicles are installed with a pre-loaded digital map, such as the commercial map provided by MapMechanics, which not only describes the land attribute such as road topology and traffic light period but also is accompanied by traffic statistics such as traffic density and average velocity at a certain time of the day. These digital maps with statistical data are derived from billions of GPS sampled points from vehicles on the move. Similar digital maps can also be found from the Internet, e.g. yahoo.com. We expect more accurate and detailed digital maps to be invented and equipped on vehicles in the future. We also assume the vehicles are of similar sizes and each vehicle is equipped with an 802.11 wireless interface. 18 Chapter 4 Related Work There exist several routing protocols that can be applied to vehicular ad hoc networks as sum- marized in [18?20]. They can be grouped into two categories: 1) those that assume the networks are always connected and 2) those that focus on intermittently connected networks. 4.1 Routing Protocols in Connected Networks Protocols in the first category are suitable for the urban rush hour scenarios, where vehicles are densely packed and locating a node for forwarding a message is typically not an issue. However, traditional ad hoc routing protocols (e.g., AODV [9] and DSR [8]) provide poor route convergence and low communication throughput because they are adversely affected by the highly dynamic nature of node mobility as shown by the results in [21]. Since GPS devices will be standard components in future vehicles, more position-based rout- ing protocols have been proposed for VANETs [10, 11, 22?26]. Position-based approaches use geographic coordinates information or relative positions of nodes to generate an efficient route through the network. For example, the greedy perimeter stateless routing (GPSR) [10] protocol may be a good choice because it is stateless and performs well despite high mobility in VANETs. However, GPSR may encounter the problems of selecting incorrect next hops due to out-of-date neighbor?s information, routing loop and too many (detour) hops as stated in [11]. In [11], packets are forwarded along the Dijkstra shortest path as calculated from road maps. Similarly, in MDDV [24], the forwarding trajectory of a message is determined as the tra- jectory that minimizes the sum of weights on that graph between the source and a vertex in the destination region. Moreover, the authors [25] developed protocols that disseminate information to a set of target zones, rather than specific destination nodes. They utilize a propagation function 19 Table 4.1: Summary of Unicast Routing Protocols Assuming Connected VANETs Characteristics GPSR GSR A-STAR MDDV MURU CAR Position Based ? ? ? ? ? ? Greedy Forwarding ? ? ? ? ? Predictive ? ? ? Buffering (Carry-and-forward) ? ? ? Street Aware ? ? ? ? ? Traffic Aware (Probabilistic) ? ? Traffic Aware (Real-Time) ? whose value is minimized over the target zones. Unlike other greedy position-based unicast rout- ing protocols, anchor-based street and traffic aware routing (A-STAR) [26] utilizes city bus routes as a strategy to find routes with a high probability for delivery. All the above protocols omit the problem of network disconnection. The authors in [22] introduced a new metric, expected disconnection degree (EDD), to evaluate the probability that a candidate route would be broken. By broadcasting the RREQ message, the path with the smallest EDD will be selected as the route. To handle the problem of mobile end nodes (source or sink), CAR [23] adopts the idea of guards which automatically adjust the connectivity path when end nodes change their speeds and/or directions. However, it first needs to broadcast the route discovery request to the entire network to find a proper route, causing excessive networking overhead even with some optimization schemes. In summary, all these approaches basically require networks to be fully connected; otherwise, the route discovery phase will fail, rendering the subsequent routing strategy useless. A summary of those protocols in terms of different features is listed in Table 4.1. 4.2 Routing Protocols in Intermittent Connected Networks As concluded in [12], network partitions in VANETs are very frequent. Therefore, it is bet- ter to consider a VANET is not always connected. With this assumption another group of routing 20 protocols are proposed in the literature [7,13,14,17,27?29]. These routing protocols can be consid- ered as the delay tolerant protocols and the carry-and-forward [16] scheme is used when network disconnection occurs. Network disconnections occur frequently in rural highway situations and in cities at night where fewer vehicles are running, making establishing end-to-end routes impossible. Even in densely-populated urban scenarios, sparse sub-networks can also be prevalent. To route a message from a vehicle to a roadside unit, the motion vector (MOVE) routing algorithm [17] uses knowledge of neighboring vehicles velocities and trajectories to predict which vehicle will physically travel closest to the fixed destination. Another knowledge-based scheme, scalable knowledge-based routing (SKVR) algorithm [27] utilizes the relatively predictable nature of public transport routes and schedules. The SKVR works in two levels: the top level is inter- domain routing, where a source and destination are on different bus routes, while the bottom level consists of intra-domain routing within the same bus route. Another algorithm in the delay-tolerant network category, MaxProp [30] utilizes carry-and- forward and packet prioritization techniques to maximize message delivery in a network with lim- ited transfer opportunities between nodes. MaxProp is implemented in a real network where it is deployed on buses, allowing each bus to communicate its location and performance information to wireless access points or other buses as they are encountered. When network infrastructures are available at intersections, a static node assisted adaptive routing protocol (SADV) has been proposed [7] for vehicular networks. When disconnected, each static node has the capability to store a message until it can forward the message to a node traveling on the optimal path. Optimal paths are determined based on a graph abstracted from a static road map and weighted with expected path forwarding delays from a delay matrix. Similar to other routing algorithms designed for delay-tolerant networks, the geographical opportunistic routing protocol (GeOpps) [28] uses navigational information to route packets effi- ciently. GeOpps assumes that each vehicle has a navigation system that provides a suggested route to a destination. Each neighbor vehicle will use a utility function built into the navigation system 21 Table 4.2: Summary of VANET Unicast Routing Protocols for Intermittent Connected Networks Characteristics MOVE MaxProp SKVR SADV GeOpps VADD Position Based ? ? ? ? ? Greedy Forwarding ? ? ? Predictive ? ? ? ? Buffering (Carry-and-forward) ? ? ? ? ? ? Street Aware ? ? ? Traffic Aware (Probabilistic) ? ? Traffic Aware (Real-Time) ? to calculate the amount of time required to reach the next interest point. The vehicle that can de- liver the packet fastest or closest to the destination will be chosen as the next hop for the message. Those protocols either require infrastructure at intersections or vehicles following the navigation system, but these assumptions may not be true in reality. Assuming a pure vehicular ad hoc network architecture, the VADD [13] protocol is proposed. When wireless connectivity is not available, the carry-and-forward strategy is used to transfer packets along vehicles on the fastest roads available. Since vehicles may deviate from predicted paths, the routing path should be recomputed continuously during the forwarding process. To aid in this process, VADD uses a street graph weighted with expected packet delivery delays. However, a drawback is that when the average distance between vehicles is close to the communication range, the transmission delay will be much longer than the expected one used in VADD. Unlike VADD, a delay-bounded routing protocol [29] is introduced for VANETs. The goal of this routing algorithm is to select an optimal path that not only has the least transmission cost but also meet the delay requirement given by the application. However, the delay model used in [29] still has a similar problem as VADD. Table 4.2 summarizes the differences of all above-mentioned routing protocols with the carry-and-forward mechanism. 22 4.3 Network Connectivity Models Existing VANETs routing protocols omit the connectivity information in highly dynamic net- works, though mobility can increase the capacity of ad hoc wireless networks [31]. Obviously, mobility is the distinguishing feature of vehicular networks, affecting the evolution of network connectivity over space and time in a unique way. The mathematical connectivity model in ad hoc networks has been studied in [32,33] with the assumption that nodes follow the Poisson distribution. However, node movement in VANETs can be affected by multiple factors such as the traffic lights, other vehicles in the vicinity and speed limits. Therefore, instead of using traditional mobility models, researchers proposed several mo- bility models for VANETs [34, 35]. Observing the clustering phenomena in a highway vehicle network, the network connectivity of highway VANET is modeled in [34] and then the opportunis- tic packet relaying protocol (OPERA) is proposed. This model also assumes a Poisson distribution of vehicles and do not consider VANETs in a city scenario where vehicles? distribution can be significantly affected by traffic light, number of lanes and vehicle velocity. With the Percolation theory, a critical phase of connectivity in wireless network is investigated in [35]. The authors claim that an ad hoc network is fully connected after a certain network density is reached. However, this model can only be applied on a static network with the assumption of Poisson distributions of nodes. The above mentioned models look at network connectivity from a macroscopic level. There are also several models that address the problem at a microscopic view such as [36?39]. In the constant speed motion (CSM) model [37], a generic vehicle i?s movement is constrained on a given road topology, and its speed is set to vi = vmin + (vmax?vmin)?? where ? is a uniformly distributed random variable in [0, 1]. The fluid traffic motion (FTM) model [36] adopts a traffic stream approach on a microscopic level. It describes speed as a monotonically decreasing function of vehicular density, forcing a lower bound on speed when the traffic congestion reaches a critical state. 23 Then based on the intelligent driver model (IDM) [38], IDM with intersection management (IDM-IM) and IDM with lane changing (IDM-LC) models were proposed in [39]. The IDM-IM is a flows-interaction model which adds intersection handling to the car-to-car interaction description provided by IDM; the IDM-LC further extends the flows-interaction description of IDM-IM, by adding overtaking capability to vehicles. To the best of our knowledge, the IDM-based mobility models are the most accurate ones for VANETs. A detailed analysis of those IDM-based models is described in [40], and a simulator, VanetMobiSim [41], based on these models is developed by the authors. Although there exist some efforts to create accurate mobility models, such as the IDM with lane changing model [39], most of these models are too complicated to be used in the networking protocol design. Instead of microscopic mobility models, we look at VANETs in a macroscopic way and try to reveal the statistical property of network connectivity. In the design of the ACAR protocol, this information is used to select the route with the highest probability of connection and thus the network throughput is increased. 4.4 Location Privacy Protection in VANET Geographic routing has been widely used in vehicular ad hoc networks (VANETs) to achieve vehicle-to-vehicle and vehicle-to-roadside communications [11, 13, 14, 22, 24, 42]. By exploiting location information, geographic ad hoc routing provides superior scalability compared to tradi- tional reactive routing protocols. However, location security becomes an important issue in achiev- ing high network performance [43?45]. Even though location security can be protected, location information exchange among neighbors compromise location privacy as well. The location privacy issue in MANETs is first addressed in [46], in which the authors de- fined the location privacy problem, threat model and application framework. In VANETs system, vehicle?s location privacy issue is addressed in [47?49]. Location privacy issue can be solved in two different ways: hiding the information of who send the data and the information of where this data come from. For the first methods, although 24 node?s location information is released, the adversary cannot link the location to a certain user, thus protecting user?s location privacy [46, 47, 50, 51]. Those approaches usually require periodically changing user?s ID and such schedule is initialized or maintained by a third-party trustworthy infrastructure. The potential threat of this framework is that, the infrastructure component may not always be available and itself may be subject to security or privacy problems. Moreover, changing identifiers has detrimental effects on routing efficiency and increases packet loss as shown in [52]. In the second method, packet forwarders will send out a set of dummy locations which hides the true locations. For instance, a node will send packets in a rectangle or circular area in which there exist at least other k?1 nodes [53]. Thus, k-anonymity is achieved since an adversary can only identify a user?s location with the probability of no higher than 1/k. Unlike the k-anonymity methods, dummy-based location privacy-protection algorithms were proposed [54, 55]. In [54], the network user generates several false position data (with one that contains the true position information) sent to the service provider. Because the service provider cannot distinguish the true position data from the dummies, the user?s location privacy is protected. Similarly, authors in [55] hid user?s real location by sending a set of dummy positions which are deliberately generated according to either a virtual grid or circle. In the above-mentioned methods, user?s true location information is fully hidden within either an area or a set of dummies, so traditional geographic routing protocols will have a big problem in making routing decision as location information is not available. Unlike previous works, we investigate user?s location privacy issue through 1) replacing user?s location information by dummy distance to destination (DOD) during routing and 2) generating pseudonyms to preserve user?s identification information. Despite these changes, the geographic routing protocol will still work, with a slight modification. Both identification and location infor- mation of users is preserved in our dummy based location privacy protection (DBLPP) protocols, so it can achieve a higher level of location privacy protection in VANETs. 25 Chapter 5 Connectivity-Quality Model in VANETs The connectivity-quality models of road segment, intersection and route that is consists of multiple road segments and intersections are investigated in this chapter. We first propose the cell based connectivity model in Section 5.1 for vehicles moving within road segments, and the cluster based connectivity model in Section 5.2 for vehicles around intersections. Then, an integrated connectivity model and the connectivity model of route are introduced in Section 5.3 and 5.4, respectively. Considering the transmission quality of a route in a connected network, we propose a novel metric connectivity-quality (CQ) in Section 5.5 which models both network connectivity and quality information. 5.1 Cell Based Connectivity Model We first consider the model for the one-lane case and later generalize it to multiple lanes. In the one-lane scenario, we divide the road segment equally into m cells so that each cell can contain at most one vehicle and each vehicle can occupy only one cell. The length of cell d can be set as the average length of vehicles, e.g. 5m. It will be fairly common that a vehicle partially occupies two adjacent cells. In this case, the cell containing the majority part of this vehicle is considered occupied. Since the distance between occupied cells will be used to compute the distance between vehicles in these cells, we found that there would be an error (at most 5m) in the distance compu- tation. However, compared to the large wireless communication range, e.g. 250m in 802.11b and 1000m in DSRC, this error can be ignored. Therefore, the problem statement of finding probability of connectivity of networks can be formulated as follows: Sub-problem Statement 1: If there are n vehicles (also called nodes) on a road segment, what 26 is the probability that the distance of any two neighboring nodes is less than the communica- tion range R = n0?d, i.e. there are no more than n0 successive empty cells on the road. In one-lane scenarios, the number of empty cells is always m?n; but in the case of multiple lanes, the number of empty cells will range from m?n to m??n/n??where n? is the number of lanes. For multiple lanes, each cell in the road may contain any number of nodes within [0,n?]. So in the extreme case, if every occupied cell contains only one node, the number of empty cells is m?n. On the other hand, if each occupied cell has n? nodes, the number will become m??n/n??. For instance, suppose 5 vehicles are deployed into a road with 5 cells and 3 lanes. Let cells be ordered geographically such that cell c0 is at the leftmost and c4 is at the rightmost position. It may occur that 3 vehicles are located in cell c0 and the other two in cell c4. So the number of empty cells in this case is 3. Intuitively, if the number of empty cells k is equal or less than n0, then the network must be connected. If k > n0, the network may be connected or disconnected depending on how the empty cells are distributed. We denote Pdis and Pcon = 1?Pdis as the probability of network being disconnected and connected, respectively. Since it is not easy to compute Pcon, we first calculate Pdis. To obtain this probability, two other probabilities are required: 1) probability P1 that there exist exactly k empty cells if n nodes were deployed into m cells, denoted as P1 = P{?(n,m) = k}, and 2) probability P2 that there exist more than n0 successive empty cells given exactly k empty cells on the road segment, which is denoted as P2 = P{?(m,k) > n0}. Then the probability that the network is disconnected becomes: Pdis = max(m??n/n??,n0)summationdisplay k=max(m?n,n0) P{?(n,m) = k}?P{?(m,k) > n0} (5.1) 5.1.1 Empty-Cell Probability P1 To drive safely on roads (with one lane), a driver need to keep a certain distance from the front or rear vehicles, thus the occupancy of one cell is dependent on the adjacent cells. Considering 27 multiple lanes cases, since traffic flows on different lanes are independent of each other, the depen- dency of occupied cells is broken. If vehicles move in two directions on a road, the occupied cells will be more randomly distributed. Therefore, we first assume that vehicles are uniformly deployed on roads. Then, we adjust our model to take into account the clustering (platoon) phenomena of vehicles. Assuming uniform node distribution, we investigate the probability that there exist exactly k empty cells on the road. Suppose there are n nodes deployed on the road with m cells. Let Ai be the event that the ith cell is empty, and let Ai be the event complementary to Ai (ith cell is occupied). Then we have: P{?(n,m) = k}= summationdisplay 1?i1 0}= P parenleftBigg muniondisplay i=1 Ai parenrightBigg = summationdisplay i P(Ai)?summationdisplay i n0} denotes the probability that there exist more than n0 successive empty cells on the road given that there were exactly k empty cells. Since the number of occupied cells is m?k, we are able to formulate this problem as: Sub-problem Statement 2: Consider throwing k items into N = m?k+1 bags and each bag can contain any number of items 0,1,???,k, then what is the probability that at least one bag contains at least (n0 + 1) items. Since it is hard to directly compute this probability, we first examine the case where all bags satisfy the condition: C1: Every bag contains at most n0 items. We denote Num(k,N) as the number of possible deployments that satisfy C1. Then it can be rewritten as: Num(k,N) = Num(k,N?1)+Num(k?1,N?1)+Num(k?2,N?1)+???+Num(n0,N?1) (5.7) The proof of Equation 5.7 is stated as follows. Let us consider a certain bag, bi, that may contain 0,1,???,n0 items. Suppose it contains j items, then the number of deployment that satisfy C1 is Num(k?j,N?1). By summing up all the possible j, we obtain: Num(k,N) = k?n0summationdisplay j=0 Num(k?j,N?1) (5.8) 29 Each term in the right part of Equation 5.8 can be expanded as Num(k?j,N?1) = k?j?n0summationdisplay l=0 Num(k?j?l,N?2) (5.9) After expanding each term, Equation 5.8 becomes: c[0]N?1?Num(k,1) + c[1]N?1?Num(k?1,1) +???+ c[k]N?1?Num(0,1) (5.10) where Num(x,1) refers to the number of possible deployments of putting x items into one bag. Num(x,1) = ? ??? ??? 0, x > n0 or x < max{0,k?n0?(N?1)} 1, max{0,k?n0?(N?1)}?x?n0 (5.11) This number will be 0 if x > n0 or x < k?n0?(N?1), since C1 does not hold in these cases. If x < 0, it means putting negative number of items into bags, so Num(x,1) is also 0; otherwise, Num(x,1) = 1. Then the number of deployments meeting C1 will be the sum of coefficients of all terms whose value are 1, i.e. min{k,(N?1)?n0}summationdisplay i=k?n0 c[i]N?1, c[i]t+1 = min{i,t?n0}summationdisplay j=max{0,i?n0} c[j]t (5.12) where c[i]1 = 1 (i = 0,1,???,n0). Since the total number of all possible deployments is CkN+k?1 = Ckm, the probability P2 is: P{?(m,k) > n0}= 1? min{k,(m?k)?n0}summationtext i=k?n0 c[i]m?k Ckm (5.13) Substituting Equation 5.4 and 5.13 into Equation 5.1, we can calculate the probability of the net- work being disconnected or connected on a certain road, if the network density information is known. 30 Figure 5.1: Illustration of Traffic Lights Affecting the Connectivity Model 5.2 Cluster Based Connectivity Model Since traffic lights (red signal) can block approaching vehicles, these vehicles will form a cluster (or convoy) on the road. Therefore, the proposed connectivity model that assumes uniform node distribution needs to be modified by adjusting the network density information. As shown in Fig. 5.1, suppose on road segment A, there are nA nodes moving toward the intersection. Assume the length of A is lA, the average velocity of vehicles moving on A is va and time period of red traffic light is tA. Then the expected number of vehicles stopped by every red light on road A is: ?nA = ? ??? ??? nA?vA?tA lA , (vA?tA) < lA nA, otherwise (5.14) If (vA?tA)?lA, then the red signal period tA is long enough so that all vehicles on A are blocked. When the light turns green, stopped vehicles will resume moving and those moving in the same direction will be very close to each other since usually drivers prefer to follow the traffic flow. As a result, we can assume those vehicles move as a cluster in which the networks are connected. Therefore, the number of nodes on the road needs to be modified because the clustered nodes will be considered as one node. 31 Since those nodes in the same cluster cannot be fitted into one cell, they may spread over several cells. For example, suppose there are ?n nodes in a cluster and they are uniformly distributed on each lane of a road. Then the total number of cells on this road will be reduced from m to m???n/n???(ds/d), where ds is the safety distance between vehicles, d is the length of cell and n? is the number of lanes. If nodes are uniformly deployed on each lane,??n/n??will be the maximal number of nodes on each lane, and??n/n???(ds/d) the maximal number of cells occupied by this cluster. The safety distance between vehicles can be simply calculated by: ds = v?tr + v2/(2b) + d (5.15) where v is the average velocity of vehicles, tr is the reaction time and b is the deceleration value of comfortable braking. Next, we investigate how to compute the number of nodes in each cluster. Suppose the num- bers of nodes moving toward the intersection on each road segment A, B, C and D are nA, nB, nC and nD, respectively. Then for each vehicle on A, the probability that it moves to D will be: PAD = nDn B + nC + nD (5.16) Suppose at a certain time t, there are ?ntA nodes blocked on road A, then the expected number of nodes moving from road A to D is: ?ntAD = ?n t A?nD nB + nC + nD (5.17) In the same way, we can get ?ntBD and ?ntCD. If the traffic light controlling the north-south traffic turns green, as shown in Fig.5.1(a), it will generate ?ntAD + ?ntBD nodes moving as a cluster on road D. If the traffic light controlling the east-west traffic turns green, as shown in Fig.5.1(b), there will be a cluster of ?ntCD nodes moving on road D. During each period of traffic light, two 32 clusters will be produced. Therefore, the number of clusters on road D is: ND = ?? ?? ?? ceilingleftBig 2?l D vD?T ceilingrightBig , lD > (T?vD) 1, otherwise (5.18) where T is the period of traffic light at this intersection. When lD > (T?vD), it means before the first cluster moves out of road D, more clusters will be generated. Then the number of clusters is ceilingleftBig 2?l D vD?T ceilingrightBig that is the upper bound of the actual number of clusters on road D. Therefore, the number of nodes on road D will be reduced to: nD?NDsummationtext t=1 (?ntAD + ?ntBD + ?ntCD?2) = nD?NDsummationtext t=1 ?ntAD?NDsummationtext t=1 ?ntBD?NDsummationtext t=1 ?ntCD + 2ND ?nD?ND?(?nAD + ?nBD + ?nCD + 2) (5.19) where ?nAD, ?nBD and ?nCD can be obtained from Equation 5.14 and 5.17. If there are two moving directions on road D, a similar modification needs to be done for the other direction as well. By combining this new method for determining the number of nodes with the connectivity model proposed in Section 5.1, we can compute the probability of connectivity of each road segment. By adjusting the number of clusters, the proposed connectivity model can also be used for one-way roads or roads with only one traffic light at the end. 5.3 Integrated Connectivity Model of Road Segment We have proposed the cell-based connectivity model where nodes move on roads without clustering and the cluster-based connectivity model in which traffic lights block vehicles to form clusters around intersections. Now, we describe how to integrate those two models to compute the connectivity of road segment. Vehicles form a cluster when they are blocked by the traffic light in an intersection. However, the cluster will exist only for a period of time. After that, these vehicles will merge into the traffic 33 flow of roads they are moving on. In other words, vehicles deployment on a road segment changes periodically between cluster-based and cell-based modes. Suppose there is only one cluster on a road segment, e.g. the road segment A as shown in Fig. 5.1. Nodes in this cluster are geographically labeled as 1,2,???, ?n, where node 1 is the closest one to the intersection and ?n is the furthest one. Therefore, the size of this cluster is ?n. Assume these nodes will move into another road, and the density and velocity of this road are d and ?v, respectively. We define tbi as the time for a node i (i?[1,?n]) to move out of the cluster, i.e. after tbi seconds, node i will merge into the traffic flow of a road segment (e.g. D in Fig. 5.1). To compute the time tbi of node i, we first investigate the one-lane one-cluster case, and then generalize it to multiple-lane multiple-cluster cases. Within one lane, a vehicle cannot accelerate freely as its movement is restricted by many factors: the distance to the preceding vehicle, ve- locities of the preceding vehicle and itself. This phenomena is represented by the car following model [38], in which the acceleration rate of node i at time instance t is: ati = dv t i dt = a ? ?1? parenleftBiggvt i v0 parenrightBigg4 ? parenleftBiggs? i sti parenrightBigg2? ? (5.20) where vti is the velocity of node i at time t, a is the maximum acceleration rate and sti is the distance between node i and its preceding node. v0 is the desired speed, which is equal to ?v in this case. Distance s?i is called desired dynamical distance [38] and is computed by: s?i = s0 + parenleftBigg vti? + v t i??v t i 2?ab parenrightBigg (5.21) It is a function of the minimum bumper-to-bumper distance s0, the minimum safe time head- way ?, the velocity difference with respect to front vehicle ?vti = (vti ?vti?1) and the maximum acceleration and deceleration values a and b. For node 1 in the cluster, its distance to the preceding node is s1 = 1/d; because in the cell-based model, vehicles are assumed to be evenly distributed on road segments. The distance node i drives from time 0 to t is lti = tintegraltext 0 1 2?a t i?t 2dt, so the value of sti will be (lti?1?lti). 34 Therefore, we obtain the time tbi that node i needs to reach the speed of ?v. It is computed by solving the integral equation: t=tbiintegraldisplay t=0 ati?tdt = ?v (5.22) During time period [tbi?1,tbi], there are only (?n?i + 1) nodes remaining in the cluster. Ac- cording to Section 5.2, we can compute the new number of cells and the connectivity probability during time period of [tbi?1,tbi]. Then, the overall connectivity probability of the road segment can be computed as: Pcell?T?max{t b i} T + i=?nsummationdisplay i=1 Pcluster(?n?i + 1)?t b i ?t b i?1 T (5.23) where tb0 = 0, T = l/?v is the time a vehicle needs to move from one end to the other end of the road segment. Pcell is the probability of connectivity computed by the cell-based model, and Pcluster(?n?i+1) is the probability of connectivity obtained through the cluster-based model with a cluster of (?n?i+1) nodes. If there are Nc clusters and the size of each cluster is ?nj,j?[1,Nc], the connectivity probability of road segment is: j=Ncsummationdisplay j=1 Pcell?T?max{t j i} T + j=Ncsummationdisplay j=1 i=?njsummationdisplay i=1 Pcluster(?nj?i + 1)?t j i ?t j i?1 T (5.24) where tji is the time tbi that node i needs to move out of the jth cluster. In multiple lane cases, we assume clustered vehicles are evenly distributed on each lane be- cause it is natural for drivers to change lanes if the current one is too congested. We apply the calculation of the single lane case to each lane and can compute the value of tji for every i?[1,?nj] and j?[1,Nc]. Note that, the value of each tji will change, and so does (tji?tji?1). However, with Equation 5.24, we can compute the probability of connectivity of road segment for multiple lane and multiple cluster cases. 35 5.4 Connectivity Model of Route So far, we modeled the network connectivity of a road segment based on the information of road length, number of vehicles, period of traffic light, and average velocity. In this section, we investigate the network connectivity of a route (path) that consists of multiple road segments. In other words, we will compute the probability that there exists a connected network on a certain route. Suppose there is a route that consists of n road segments which are sequentially numbered as 1,2,???,n. We denote the connectivity probability of each segment as Pi (i = 1,2,???,n). Then, the connectivity of a route will be nproducttext i=1 (Pi?Pij) where j = i + 1 and Pij = 1 when i = n. Pij is the network connectivity of the intersection between road segment i and j. To address the dependency issue of connectivity probabilities of adjacent road segments, we need to understand the movement of vehicles around intersections. Due to the traffic light at a intersection, vehicles may be stopped by the red signal. Therefore, the connectivity of network around the intersection will be higher than other parts of the road. In this section, we will investi- gate the connectivity probabilities of two types of networks. First, we look at the network with cars stopped around intersection areas by traffic lights. Second, we consider the case where no car is stopped by traffic lights. Finally, the expected network connectivity probability of an intersection is computed. 5.4.1 Vehicle?s Distribution around Intersections As shown in Fig. 5.2, when the traffic light turns to red for east-west direction, there may be several approaching cars, such as n0 and n3, stopped by the red signal. Therefore, the uniform distribution of vehicles on road segment C is broken. In other words, more cars are being blocked in front of the traffic light, so less vehicles will be moving on road segment C. On the other hand, because the traffic signal for road segments A and B are green, vehicles on these two roads follow uniform distribution. In this case, the network connectivity of road C is lower but the connectivity probability of road B is higher than normal. If the traffic light becomes green for 36 Figure 5.2: Network Connectivity around Intersections with Stopped Vehicles east-west direction, the network connectivity of B will be lower but that of C is higher. Therefore, we note that the connectivity probabilities of two adjacent road segments are not independent due to traffic lights. Now, we investigate the network connectivity of the intersection between road C and B. We first define P3 as the probability that no car is stopped by the traffic light. P4 = 1?P3 denotes the probability that at least one car is stopped by the traffic light. When cars are blocked by the traffic light, there are two possibilities of their future movements: 1) stop at the intersection, or 2) move (right turn) to another road segment. Considering these two cases, we further define P4? as the probability that all stopped cars move away from the intersection. This probability is usually very small because even if there is only one car stopped at the intersection, all approaching cars has to stop and stay at the intersection too. Complementary to P4?, we denote P4? = P4?P4? as the probability that at least one car stopped at the intersection. 37 Figure 5.3: Network Connectivity around Intersections without Stopped Vehicles 5.4.2 Connectivity Probability Without Stopped Vehicles P3 Even though there is a traffic light in an intersection, it is possible that the red signal does not stop any approaching vehicles which are too far away from the traffic light. As shown in Fig. 5.3, cars are moving towards the traffic light on road C and before they reach the intersection, the signal turns to green from red. This case occurs with the probability of P3: P3 = CnBm? B CnBmB , parenleftbigg m?B = mB?vB?tl parenrightbigg (5.25) where vB, nB and mB are the average vehicle velocity, number of vehicles and number of cells on road segment B, respectively. l and t are the size of cell and the period of red signal. The above equation models the probability that no car is stopped by the red signal. Because the north-south traffic is not affected by the traffic light, we can consider uniform distributions of vehicles on road C and B. In this case, the network disconnects only if there is no car on road B and C around the intersection area. As shown in Fig. 5.4, we are interested in the areas of x and y on road segment 38 Figure 5.4: Network Disconnection around Intersections with a Uniform Node Distribution C and B, respectively. The value of x and y must satisfy the following condition R2 = x2 + y2 where R is the communication range. The value of x, number of empty cells, will be ranging from 0 to min{n0,(mC?nC)}, where n0, nC and mC are the communication range (in number of cells), and number of nodes and number of cells on road segment C. The value of x must be smaller or equal to n0 because of the equation R2 = x2 +y2. On the other hand, it has to be smaller than (mC?nC). Otherwise, there must be at least one car being deployed in the area of x due to the pigeonhole principle. Similarly, the value of y is within [0,min{n0,(mB?nB)}] where nB and mB are the number of nodes and number of cells on road segment B. If there is no car in the areas of x and y, the network disconnects around the intersection. We denote the probability of this event occurring as ?PBC which can be computed by: ?PBC = C nC (mC?x) CnCmC ? CnB(mB?y) CnBmB (5.26) Since the value range of x and y are known, we can easily compute expected value E( ?PBC). This value is considered as the probability of network disconnection with uniform distribution of nodes on road B and C. Therefore, the network connectivity probability in this case is: P3?[1?E( ?PBC)] (5.27) 39 Figure 5.5: All Stopped Vehicles Move Away from Intersection 5.4.3 Connectivity Probability With Stopped Vehicles P4 Complementary to P3, we can compute the probability of P4 = 1?P3. In this case, there is at least one car stopped in front of the intersection due to the traffic light. According to the Equation 5.14, we can compute the number of vehicles stopped on road C. We denote this value as ?nC. For those stopped vehicles, the probability of each one moving from road C to A can be obtained by Equation 5.16. We denote this probability as PCA. We first look at the probability (P4?) that all stopped vehicles move away from road C to A: P4? = (PCA)?nC (5.28) Since all stopped vehicles on road C move to road A, the nodes on road C follow uniform distribution. As shown in Fig. 5.5, there may be some vehicles moving to road C from other road segments, such as n4 from A and n5 from B. However, they will not break the uniform distribution of nodes on road C. Then, the number of nodes on C change to nC ??nC + ?nBC + ?nAC where ?nBC and ?nAC denote the number of nodes moving to road C from B and A. According to the 40 Equation 5.26, we can compute the probability of network disconnection as ?PBC with the new number of nodes on road C and B. Therefore, the probability of existing connected network in this case will be: P4??[1?E( ?PBC)] (5.29) Finally, we look at the case where there is at least one stopped vehicle at the intersection. The probability P4? can be obtained by P4?P4?. As we defined previously, the network connectivity of a road segment is considered as the probability that there exists a connected network from one end to the other end of the road segment. If there is a car stopped in front of the intersection, we can consider there is always a node at the eastern end of road C, which satisfies the definition of network connectivity of a road segment. In other words, the network around intersection area is always connected in this case. Therefore, the network connectivity of the intersection between road B and C can be com- puted as: P3?[1?E( ?PBC)] + P4??[1?E( ?PBC)] + P4? (5.30) Until now, we have modeled the connectivities of networks on road segments and around intersec- tions. Then, the connectivity probability of a path (that is composed of multiple road segments) can be computed as the product of probabilities of those road segments and adjacent intersections. For a given path starting from road segment s and ending at e, we denote i and j as two adjacent road segments, Pi as the connectivity probability of road segment i, and Pij as the connectivity probability of the intersection between road segment i and j. Thus, the connectivity probability of this path can be obtained from the following equation: P(s,e) = eproductdisplay i=s (Pi?Pij), (j = i + 1) (5.31) where Pij = 1 when i = e. The above equation can be used to compute the connectivity probability of a given route that consists of several road segments. 41 5.5 Connectivity-Quality of Route For two road segments with similar network connectivity probabilities, their transmission qualities may be quite different. In other words, the proposed connectivity probability model needs to be adjusted by considering the transmission quality of a route. To meet this goal, we propose a novel metric, called connectivity-quality, which combines the information of both network con- nectivity and transmission quality of a route. For a route that is consists of several road segments, its CQ can be computed as producttext(CQi?CQij) where i and j are adjacent road segments. 5.5.1 Date Delivery Ratio of Road Segment Considering a road segment with connected networks, we first model the packet error rate (PER) of a single hop. Then, we model the PER of a multi-hop route. Finally, the average PER of all possible routes within a road segment is used to compute the data delivery ratio of this road segment. To model the path loss of a single hop between any two nodes, two cases need to be consid- ered: the line-of-sight (LOS) and non-line-of-sight (NLOS) where there is at least one neighbor between these two nodes. Because of the popularity and lower price of IEEE 802.11 devices, the physical layer in VANETs (the DSRC/IEEE 802.11p PHY) will be a variation of the orthogonal frequency-division multiplexing (OFDM) based on the IEEE 802.11a standard. So the channel fading model of determining the received signal power level in the case of LOS is [56]: Pr = Pt(4pi) 2 parenleftBigd ? parenrightBig? bracketleftBigg 1 + ?2 + 2?cos parenleftBigg4pih2 d? parenrightBiggbracketrightBigg (5.32) where Pt is the transmit power, d is the distance between the transmitter and receiver, ? is the wavelength of propagating signal, ? is the reflection coefficient of the ground surface, ? is the path 42 loss factor and h is the antenna height. The model of NLOS is expressed as: Pr = ?? ?? ?? PtGtGr parenleftBig ? 4pi parenrightBig2 (d?1m) PtGtGr parenleftBig ? 4pi parenrightBig2 ? 1d? (d > 1m) (5.33) Taking into account the effect introduced by the cyclical prefix attached to each OFDM sym- bol, the signal to interference plus noise ratio (SINR) should be reduced by a factor of ?: SINR = ??10log10 ? ?? ?? Pr P0 + NINTsummationtext i=1 PiINT ? ?? ?? (5.34) where ? is 0.8 according to [56], P0 is the background noise, and PiINT is the interference from neighbor ni. Suppose on a certain road segment, as shown in Fig. 5.6, node na is sending packets to nb and the distance between them is dab. From the perspective of nb, there will be den?(RINT ? 2R?dab) potential interfering nodes around it. In which, R and RINT are the communication and interference ranges of nb, and den is the network density of this road. In the IEEE 802.11 protocols, before each communication the RTS/CTS (request to send/clear to send) packets need to be transmitted between sender and receiver to reduce frame collisions introduced by the hidden terminal problem. After that, during the communication between na and nb, nodes within their communication ranges are not allowed to transmit packets. Thus, the potential interfering nodes must be in the area that is outside the communication ranges of na and nb but inside their interference ranges. Within these areas, for a circle with a radius of R, there is at most one transmission that can interfere with the packet receptions at nb. Therefore, there are at most bracketleftBigceilingleftBigR INT?R 2R ceilingrightBig + ceilingleftBigR INT?R?dab 2R ceilingrightBigbracketrightBig transmissions that interfere with node nb simultaneously. The receive power PiINT of each interference transmission can be computed through Equa- tion 5.32 or 5.33 where d is the distance between nb and the center of each segment labeled as 2R in Fig. 5.6. For cases with (da < 2R) and (db < 2R), (3R + db/2) and (3R + dab + da/2) are the 43 Figure 5.6: Illustration of the Number of Potential Interfering Nodes distances of interference transmissions in db and da, respectively. If node nb is in a nearby inter- section area, there will be more potential for interfering nodes. Similarly, for roads with different network densities joined at an intersection, we can calculate the number NINT. In Equation 5.34, we use the maximum number of interfering transmissions with the commu- nication between na and nb, thus the worst case of SINR for nb is obtained. In simulations, we found this lower bound value was very close to the real one; thus, we use it to further calculate the bit error rate and packet error rate of a single hop transmission. Suppose the binary phase shift keying (BPSK) scheme is used to modulate the signal, the bit error rate (BER) is: BER = Q parenleftBig? 2?SINR parenrightBig (5.35) where Q(x) = 0.5?0.5?erf( x?2) and erf(?) is the error function. Because of retransmissions in the link layer, the frame error rate (FER) can be computed as: FERlink = 1? Nsummationdisplay i=0 (1?FER)FERi (5.36) where FER = 1?(1?BER)L, L is the length in bits of each frame and N is the number of retransmission times. Suppose every packet is composed of t frames, the PER is computed by: PER = 1?(1?FERlink)t (5.37) 44 Given the communication distance and number of neighbors, we can model the PER of a single hop. Therefore, if the node deployment of a network is known, it is possible to compute the PER of every hop. Next, we discuss how to model the PER of a certain road segment (denoted as PERrs). On a certain road segment, suppose there is a route routej that is composed of h hops with PER at every hop of PERl (l = 1,2,???,h), then the PER of forwarding packets along this route routej can be computed as: PERroutej = 1? hproductdisplay l=1 (1?PERl) (5.38) This equation is valid only if the PER is independent from one hop to the next; but due to the wireless communication environment there could be interference which violates this assumption. However, in this work, we use this equation as the first-order approximation of the PER of for- warding packets on a certain route. Since different routes (that are composed of different hops) give different PERs, we consider a routing algorithm that minimizes PER, so the problem is to determine the minimal expected PER. If there are n nodes and k? empty cells on the road, for a certain distribution of these empty cells, the minimal PER of this road segment is denoted as min{PERroutej}. To compute this value, we need to know how the nodes (and empty cells) are deployed in the network. However, it is impossible to obtain such information because vehicles are always moving. To address this issue, we average these minimal PERs and obtain the PER of this road segment as PERik? = E[min{PERroutej}]. This value can be easily determined because we can compute the PER of every route. There- fore, the expected value of PERrs can be calculated as: E bracketleftBig PERik? bracketrightBig = Ek bracketleftBig E bracketleftBig PERik?|k? = k bracketrightBigbracketrightBig (5.39) which can further be rewritten as: PERrs = m??n/n??summationdisplay k=m?n Ckmsummationdisplay i=1 1 Ckm ?PER i k?P{?(n,m) = k} (5.40) 45 where m and n? are the number of cells and number of lanes on this road segment, respectively. Thus we use Drs = 1?PERrs to model the data delivery ratio (transmission quality) of a certain road segment. 5.5.2 Connectivity-Quality Metric Data delivery ratio and packet error rate (PER) are usually used to evaluate the transmission quality of a route in networks. When we use these two metrics, we always assume that the network is fully connected because otherwise the delivery ratio will be zero. Therefore, delivery ratio is considered a useful metric with the condition that networks are connected. In the previous section, we model the PER and data delivery ratio of a road segment. However, that data delivery ratio Drs is actually the probability P(D|C) where the event D means a packet is successfully delivered and C denotes the event of network being connected. Therefore, P(D|C) gives the probability of a packet being successfully delivered with the condition that networks are connected. If we multiply P(D|C) by the network connectivity probability P(C), we will have the following equation: P(D,C) = P(D|C)?P(C) (5.41) In other words, P(D,C) gives the joint probability that a packet is successfully delivered in a connected network. If we apply this probability to a road segment, it will become the connectivity- quality (CQ) metric which will be introduced later. According to our connectivity model, the larger the network density, the higher the network connectivity probability will be. However, higher densities can cause larger interferences (more nodes in interference ranges), and thus reduce the packet delivery ratio. On the other hand, it is possible that a road segment has a low network connectivity probability. However, if the network on it becomes connected, the delivery ratio may be very high (due to low interferences). Therefore, both network connectivity and data delivery ratio are important in selecting routes. If we investigate the probability P(D,C), it contains two probabilities P(D|C) and P(C). For a certain road segment, these two probabilities can be re-written as Drs and Prs, respectively. 46 Therefore, we define a novel metric, connectivity-quality (CQ), in this way: CQrs = Drs?Prs (5.42) We can interpret the Equation 5.42 as a weighted connectivity probability of a road segment. The weight is the data delivery ratio of this road segment (with connected networks). The CQ metric is not only useful for VANETs but any other intermittent-connected networks because it models both network transmission quality and network connectivity in a mobile network with frequent network disconnections. As in the computation of CQrs, it is easy to compute the CQ of networks around an inter- section. The network connectivity of an intersection has been discussed previously. To compute the data delivery ratio of networks around an intersection area, we can still use the PER models proposed in Section 5.5.1. The only difference is that there will be only single hop communication around intersection areas, so computing CQ for an intersection should be easier than that for a road segment. For a given path starting from road segment s and ending at e, we denote i and j as two adjacent road segments, CQi as the CQ of road segment i, and CQij as the CQ of the intersection between road segment i and j. Then, the CQ value of the entire path is obtained from the following equation: CQ(s,e) = eproductdisplay i=s (CQi?CQij), (j = i + 1) (5.43) where CQij = 1 when i = e. As it will be shown in Chapter 7, since the ACAR protocol chooses routes with the highest connectivity-qualities, the data delivery ratio and network throughput of ACAR are drastically increased compared to other protocols. 47 Chapter 6 Adaptive Connectivity Aware Routing Algorithm The ACAR protocol includes two essential elements: 1) correctly selecting an optimal route that consists of road segments with the best connectivity-quality, and 2) efficiently forwarding packets hop-by-hop through each road segment in the selected route. To eliminate the impact of inaccurate statistical density data, we developed an adaptive route selection algorithm that collects real-time density information on-the-fly while forwarding packets. In each road segment in the selected route, the next hop is selected using a metric that minimizes the packet error rate (PER) of the entire route based on measured PERs at each node. In addition, carry-and-forward [16] mechanism is adopted to handle frequent network partitions in VANETs. 6.1 Selection of Route with the Highest Connectivity-Quality According to the proposed connectivity model and CQ metric, a node can compute a route with the best connectivity-quality. We consider this as the optimal route which will be used to forward packets. Required information includes network densities, road segment lengths, average velocities, number of lanes and traffic light periods which are provided in pre-installed digital maps. Therefore, every packet forwarder (vehicle) can locally compute and find the optimal route to deliver packets. Based on the classic Dijkstra algorithm, we propose an algorithm to find the optimal route with the best connectivity-quality. As shown in Algorithm 1, the inputs of the FIND() function include: the road topology map G, the source s and destination d. In the map G, vertices are intersections and edge are road segments between intersections. Given the location of source and destination nodes, the output of the FIND() function is a sequence of intersections that are used to construct the final route. 48 Algorithm 1 FIND (G, s, d) 1: Add s and d as vertices into graph G 2: G??s 3: G?G?s 4: while G is not empty do 5: m?0 6: for each vertex u?G? do 7: for every u?s neighbor v?G do 8: if max{CQ(s,v)}> m then 9: m?CQ(s,v) 10: v??v 11: u??u 12: end if 13: end for 14: end for 15: pre[v?]?u? 16: if v? = d then 17: return pre[] 18: end if 19: G??G? + v? 20: G?G?v? 21: end while For each vertex v?G, if it is on the optimal route, its parent node (also on the route) is stored in pre[v]. If v is not on the route, its pre[v] = NULL. Therefore, from the destination d, we can trace backward to the source s and construct the route. The graph G?, which is a tree that saves the optimal path from the source to the destination. For every node u?G?, we will check all its neighbors v in graph G. Therefore, lines 8?12 will find a new node v?G which is the neighbor of u?G? where the following property holds. Property 1: If a new node v is added to G?, the connectivity-quality from s to v is the largest compared with any other remaining nodes in G. In line 8, max{CQ(s,v)}denotes the highest connectivity-quality of a route from s to v in graph G?. It is possible there are more than one path from s to v in graph G?, so we need to compute every CQ(s,v) and select the path with the highest CQ. To obtain each CQ(s,v), we need to use equations in Section 5.5. Based on the above description, we have the second property: 49 Figure 6.1: Illustration of Route Selection Algorithm Property 2: For every node v ? G, only the path from s to v with the largest connectivity- quality will be added into G?. Due to these two properties, we could easily proof the proposed algorithm satisfies the prop- erty of optimality. Now, we will use an example to illustrate how this algorithm works. As shown in Fig. 6.1(a). The lengths of road segments rs1, r12, r2d and rsd are 1000m, 800m, 1000m and 800m, respectively. There are 20, 16, 20 and 8 nodes on road segments rs1, r12, r2d and rsd, respec- tively. Then, we can compute the CQs of rs1, r12, r2d and rsd as .85, .90, .85 and .57, respectively. According to our FIND() algorithm, node s is first moved to G?. Then, as shown in Fig. 6.1(b), node 1 will be added to G? as it provides a higher connectivity-quality than that of node d. Since the connectivity-quality CQs12 = .78, node 2 is moved to G? as shown in Fig. 6.1(c). Finally, as shown in Fig. 6.1(d), node d was added to G? with the connectivity-quality CQs12d = .69 which is still larger than CQsd = .57. Therefore, the route rs12d will be considered as the optimal route for forwarding packets. 50 After receiving a packet, a node calculates the optimal route and selects the next hop which is closer to the next intersection. For the example shown in Fig. 6.1, vehicles on road segments rs1 or r12 can compute the same route rs12d to forward packets. When packets are routed around an intersection, the chosen next hop will be the one which is closest to the next intersection along the optimal route. Routing policies such as location first, di- rection first and hybrid probes in [13] can be adopted in ACAR to further improve its performance, which are considered as our future works. 6.2 Velocity Compensated Neighbor Location Prediction In geographic routing, every vehicle periodically broadcasts (beacons) its current location in- formation to its neighbors. However, since the broadcast period cannot be too small, the neighbor?s information may be out-of-date and thus affects the next hop selection in geographic routings. To address the issue of out-of-date neighbors, many neighbor location prediction (NLP) al- gorithm are proposed [11, 21, 57, 58]. The basic idea is that, before selecting the next hop, a node needs to predict all its neighbors? locations based on their position and velocity information broad- casted in the last time interval. In the ACAR protocol, we simply adopt the NLP scheme used in [58]. After predicting neighbors? locations, node i selects the next hop only through those still within the communication range. Although the NLP algorithm used in ACAR is very simple, it does help improve the network performance as shown in our simulation results. In some cases, a node cannot find another neighbor to forward packets (in the event of network partition), then these packets will be saved into its buffer and carried [16] with the vehicle as it moves towards a next node to which it can forward the packet again. 6.3 Adaptive Route Selection If the density information on each road segment is correct, the optimal route will be the one with the highest connectivity-quality. However, in reality, there may be some errors in the statistical 51 density data. For example, suppose on road A there are 100 nodes (on average) in the afternoon, then it is possible that the network density between 2:00pm-4:00pm is 50 and from 4:00pm to 6:00pm is 150. One possible solution to this problem is to flood the entire network to collect the real-time density information. However, even with directional and efficient flooding, this approach could still cause too much broadcast overhead. Therefore, we propose an adaptive path selection approach that collects real-time density data when packets are being forwarded into the network. ACAR first computes a route based on statistical density data from the pre-loaded map. It then puts the route information into packet headers and transmits packets along this selected route. While the packets are being forwarded to the destination, network densities of all road segments along this path are collected simultaneously. This process, called on-the-fly density collection, is described in the next section. After a pre-defined number of on-the-fly density collections (e.g. 10), the density information on road segments in the route can be obtained at the destination. If the error rates of some road segments density exceed the threshold, e.g. 30%, the sink node sends an acknowledge message to notify the source about the updated density of that road. Next, the source node re-computes a new route based on the recently received and more accurate density data. Eventually, the selected route will converge to an optimal route. 6.4 On-The-Fly Density Collection As stated above, the on-the-fly density collection process is done while data packets are being forwarded. Before transmitting data packets, every forwarder adds into the packets its local density information, which is obtained through collecting beaconing messages. Then, the total density of a road segment can be obtained at the end of it. When packets reach the destination, the density data for all road segments along the path are collected. As shown in Fig. 6.2, the data packet is composed of two parts: packet header and data payload. At the beginning of data payload, there are some reserved fields (bytes) for on-the-fly density collections. The first byte records how many road segments (e.g. Nr) on selected route, 52 Figure 6.2: On-the-fly Density Collection Mechanism and subsequent Nr bytes record the density information of every road segment on the route. The initial values of these fields are 0. Since the source node is able to compute entire route based on historical density data from digital maps, it is easy to get the number of road segments on the route. We now state how a packet forwarder collects its local density information and updates the corresponding byte in data packets. Since every node periodically beacons its location, velocity and id to its neighbors, a node obtains the number of its one-hop neighbors. In addition, with the neighbor?s location information, a node can determine whether a neighbor is in front of or behind it. For example, node n2 in Fig. 6.2 infers that 4 nodes (including n1) are in front of it and 5 nodes behind. Suppose node n1 is the current packet forwarder which is at the beginning of road segment 1, and n2 is the next hop. Before n1 sends data packets, it adds the number of nodes between itself and n2 (including itself) to the field RS1 and forwards them to n2. Then, n2 follows the same strategy and sends packets to n3. Node n3 modifies RS1 again by add its collected local density information, and sends out packets. Finally, packets reach the end of this road segment at node n4. Node n4 needs to decide if its next hop is still on the same road segment. If so, it continues the procedure as node n3 did. Otherwise, it adds 1 to RS1 because itself is also on the road segment 1, 53 and forward packets to its next hop, e.g. n5 in Fig. 6.2. Consequently, node n5 adds 6 to RS2 and forward packets to n6. In the same way, when packets reach the destination, density of every road segment on the route is collected. After the on-the-fly density collection, the destination node needs to notify the source if there are significant discrepancies between statistical and real-time density data. If so, source node recalculates routes with newly collected density information; otherwise, the same route will be used for delivering future packets. 6.5 Next Hop Selection On each road segment in the selected route, packets may be forwarded through multiple hops from the beginning to the end of the road segment. The next hop will be selected using a metric that minimizes the PER of route on each road segment. The PER of a link between two nodes can be calculated by counting the number of successfully delivered packets and dropped ones. This is calculated during the beaconing period and thus does not incur additional network overhead. The original geographic routing protocols [10, 11] choose the farthest node as the next hop, since this selection can minimize the total number of hops to the destination. However, the link quality to the farthest node is usually weak because PER increases as the transmission distance increases. However, selecting next hop with a shorter distance will increase the number of hops. As proven in [59], the data delivery ratio will decrease as the hop number increases. So there is a trade-off between shorter transmission distance and smaller number of hops. To address this issue, every node needs to measure the packet error rate of all its neigh- bors. Suppose on a road segment there are two neighboring node na and nb, and they periodically send their locations to each other. By counting the number of packets successfully delivered and dropped, the expected transmission count (ETX) can be calculated using the approach in [60]. Then the PER from na to nb is obtained as: PERab = 1? 1ETX ab (6.1) 54 where ETXab is the expected transmission count from node na to nb. In the same way, PERba can be computed. Since the route is already known (stored in the packet header), node na then computes the remaining distance (denoted as Dis) from itself to the next intersection. Suppose the distance between node na and nb is d, then the PER of the remaining route on this road segment can be estimated by: PER = 1?(1?PERab)[Disd ] (6.2) We assume different parts of the same road segment have the similar communication environment, thus the distance between nodes will be the dominant factor that affects the data delivery ratio. So among its neighbors, node na selects the one that minimizes the PER of the remaining path as the next hop. The same next hop selection will be done on all following road segments aiming to achieve the highest data delivery ratio along the whole route. However, due to frequent network partitions in VANETs, a data forwarder may have no neighbors in the forward direction. In these cases, we adopt the carry and forward scheme [16] that buffers packets and waits until there exists an available next hop. Then the packet will be fetched from the buffer and forwarded again. 55 Chapter 7 Simulations and Results 7.1 Mobility of Nodes Since modeling of complex vehicle movement is important for accurately evaluating proto- cols, we generated the movement of nodes using VanetMobiSim [41] whose mobility patterns have been validated against TSIS-CORSIM, a well-known and validated traffic generator. The Vanet- MobiSim features new realistic automotive motion models at both macroscopic and microscopic levels, and also supports traffic lights, lane changes and speed regulations. We compared the network connectivity model with data collected through VanetMobiSim simulations for a set of parameters: length of road segment, average vehicle velocity and traffic light period. Specifically, as shown in Fig.7.1, there are 7 road segments (each is 1000m) in the map, the average velocity of vehicles is 10m/s and the traffic light period is 120 seconds. Those small squares denote vehicles moving on the road, the number besides them are the node IDs. Our goal is to collect the network connectivity and density information on the middle road segment ending with two traffic lights. The simulation time is 2000 seconds and we check every second if the network is connected. The number of times that networks are connected is denoted as tc and the probability of network connectivity can be calculated as tc/2000. Similarly, the average network density can be collected, though it may not be an integer. We repeated the same scenario 10 times with 10 different random seeds to achieve a high confidence level. As shown in Fig.7.2-Fig.7.7, with different road lengths, velocities and traffic light periods, the connectivity model matches the value obtained from VanetMobiSim very well (confidence level is 95%). In the above simulations, there is only one road segment containing two lanes in each driving direction. We also verified the connectivity model in the cases of more lanes (e.g. 3-5 lanes), one traffic light at the end of a road segment and routes that consist of multiple road segments. The 56 Figure 7.1: A VanetMobiSim Snapshot of Connectivity Model Validations 0 5 10 15 20 25 30 350 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Number of nodes Probability of connectivity Connectivity Model Data from Simulations Confidence Bounds Figure 7.2: Validation of Connectivity Model with Road = 1000m, Velocity = 5m/s and Traffic light = 120s results showed our connectivity model matched the simulation results very well. However, due to space limitation those results are omitted in this work. 57 0 5 10 15 20 25 30 35 400 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Number of nodes Probability of connectivity Connectivity Model Data from Simulations Confidence Bounds Figure 7.3: Validation of Connectivity Model with Road = 1000m, Velocity = 7.5m/s and Traffic Light = 60s 0 5 10 15 20 25 30 350 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Number of nodes Probability of connectivity Connectivity Model Data from Simulations Confidence Bounds Figure 7.4: Validation of Connectivity Model with Road = 1000m, Velocity = 7.5m/s and Traffic Light = 120s 7.2 Digital Maps We used two maps in simulations to show the high performance of ACAR, and how different network densities and vehicles velocities affect this protocol. 58 0 10 20 30 40 50 60 700 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Number of nodes Probability of connectivity Connectivity Model Data from Simulations Confidence Bounds Figure 7.5: Validation of Connectivity Model with Road = 1800m, Velocity = 10m/s and Traffic Light = 60s 0 10 20 30 40 50 60 700 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Number of nodes Probability of connectivity Connectivity Model Data from Simulations Confidence Bounds Figure 7.6: Validation of Connectivity Model with Road = 1800m, Velocity = 7.5m/s and Traffic Light = 60s One map is illustrated in Fig 3.1, which contains 5 major road segments: IAIB, IAIC, IAID, IBIC and ICID. The length of each road segment and number of nodes deployed on them are the 59 0 10 20 30 40 50 60 70 800 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Number of nodes Probability of connectivity Connectivity Model Data from Simulations Confidence Bounds Figure 7.7: Validation of Connectivity Model with Road = 1800m, Velocity = 10m/s and Traffic Light = 120s same as we described in Chapter 3. This map is used in Scenario I in which we evaluate the basic network performance of ACAR such as: data delivery ratio, end-to-end delay and throughput. In the Scenario II, we load a real map topology from the from the topologically integrated geographic encoding and referencing (TIGER) database, which is used by the United States census bureau to describe land attributes of U.S.. Within a 1000m?1000m area, street layout is from a city in Tennessee, centered at latitude 35162102 and longitude?84877562, has 15 intersections and 38 road segments as shown in Fig.7.8. To evaluate how different network densities affect network performance, we double the network density of several roads which are marked with bold black lines in Fig.7.8. We also adjust the velocity of vehicles in the network and evaluate how network mobility affects the routing performance. 60 Figure 7.8: Street Layout of the Area Centered at (35162102,?84877562) in the Tennessee State 7.3 Networking Simulation We simulated the ACAR protocol in NS2 (ns-2.33) and compared it with VADD [13], MOVE [17], GPSR* and GSR*. The original GPSR [10] and GSR [11] simply drop packets when network dis- connections occur, so we add carry-and-forward schemes in them and named them as GPSR* and GSR*, respectively. To make fair comparisons between ACAR and other trajectory based routing protocols, we also implemented the neighbor location predication scheme on VADD and GSR*. Because the proper PHY/MAC modules for vehicular communications are still under devel- opment and not available for NS2, we adopt the channel fading model proposed in [56] and IEEE 802.11a as the MAC/PHY protocol. Since we are interested in network performances of different protocols, we omit the exact simulation of lower layers but consider it in our future work when IEEE standards for vehicular communication are finalized. Details of simulation parameters are listed in Table 7.1. We first simulated the Scenario I in which the basic network performances are evaluated such as the data delivery ratio, end-to-end delay and network throughput. Then, we simulated 61 Table 7.1: Simulation Set-Up Parameters for ACAR Parameter Value Number of lanes 2 lanes per direction Number of nodes 40-200 Velocity 10-90 miles/hour Period of traffic lights 60 seconds Communication range 250 m Beacon interval 1.0 second Buffer size 64 KB Packet size 512 Bytes the Scenario II with different network densities and vehicles? velocities and evaluated the network performances and network overheads of the proposed protocol. In each scenario, different data sending rates (1 to 10 pkts/s) were used. A source node is randomly selected to communicate with a fixed destination. Given a real-time location service, ACAR works well if the destination is mobile. However, we considered a fixed destination to model applications described in Chapter 1. The simulation time is 2000 seconds and each scenario is repeated 20 times to achieve results with a high level of confidence. 7.4 Data Delivery Ratio Data delivery ratio is the number of received packets at the destination divided by the total number of packets sent into networks. As shown in Fig. 7.9, ACAR achieves the highest data delivery ratio (above 90%). This is because ACAR forwards packets along route on road IAIBIC with the highest connectivity-quality. As shown in Fig. 7.9, GPSR* and GPSR give the second and third highest data delivery ratios, respectively. When network partitions occur, GPSR and GPSR* utilize perimeter mode searches to find routes, so packets may finally delivered on road IAIBIC which has the highest connectivity-quality. However, GPSR* only successfully delivered about half of packets compared to the performance of ACAR. This is because, after packets are forwarded on road IAIC or IAID, 62 1 2 3 4 5 6 7 8 9 100 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Data sending rate (pkts/second) Data delivery ratio ACAR GPSR* GPSR VADD GSR* GSR MOVE Figure 7.9: Data Delivery Ratio in the Scenario I it is possible that there are no connected links back to road IAIB. So these packets are buffered and carried by nodes moving on road IAIC or IAID. On the other hand, wireless transmission qualities of these two roads are very bad, so the data delivery ratio of GPSR* forwarding packets along them is very low. Since we implemented the carry-and-forward scheme on GSPR*, it delivered 10?20% more packets than GPSR. So we conclude that the carry-and-forward scheme is very helpful for routing protocols in VANET to achieve high data delivery ratios. GSR* selects road IAIC to forward packets, as it is the geographic shortest path to the des- tination. According to the connectivity model in VADD, path IAIC provides the shortest delivery delay, so it is chosen to route packets. However, the connectivity probability of this road is just .29, and the wireless transmission quality is even lower. Therefore, the overall data delivery ratio of packets being routed on this road is very low. Since GSR* and VADD choose the same path for routing, they generate very similar data delivery ratio results. The original GSR protocol gives a lower data delivery ratio (only .02), compared to the ex- tended version GSR*. This is because on GSR*, we implemented NLP and carry-and-forward 63 mechanisms. The NLP scheme can help nodes to correctly select the next hop and the carry-and- forward scheme can avoid packet loss due to network partitions. The data delivery ratio of GSR* is about 5?10 times that of GSR. Therefore, we conclude the NLP mechanism is also necessary for VANET routing protocols to achieve high data delivery ratios. MOVE protocol delivered the least number of packets in our simulations. In MOVE, there are seven forwarding rules being used to select the next hop. If none of neighbors satisfies these forwarding rules, packets will be carried by current node. So packets are more likely to be buffered and carried by vehicles instead of being greedily sent out. As we will describe later, these packets may be dropped due to packets expiration, weak wireless links to next hops and buffer overflows. The number of packet loss due to these reasons is very high for MOVE, so it gives the lowest data delivery ratio compared to others. 7.5 Reasons of Packet Loss There are mainly three reasons of packet loss for all VANET protocols: packets expired, weak wireless links and buffer overflow. We measured the number of lost packets due to each reason, and then find the major cause of packet loss for each protocol. 7.5.1 Expired Packets Since we cannot run simulations an infinite number of times, when simulations are terminated, there might be some packets, called expired packets, still in buffers and these packets will be dropped due to their huge delays. As shown in Fig. 7.10, the fraction of expired packets of MOVE is almost 5-6 times that of the others. However, ACAR, VADD, GSR* and GPSR* have the similar number of expired packets. The reason is that, in ACAR, VADD, GSR* and GPSR* protocols, packets are greedily forwarded to the next hop; but in MOVE, if the neighbor satisfying none of the forwarding rules (totally 7 rules), packets will be carried by the current node. Therefore, packets will be more likely buffered in MOVE than the others. However, due to the small number of expired packets, we conclude that packet expiration is not the dominant reason for packet loss. 64 0 2 4 6 8 10 120 0.01 0.02 0.03 0.04 0.05 0.06 0.07 Data sending rate (pkts/second) Percentage of packets remaining in buffers ACAR VADD GSR* GPSR* MOVE Figure 7.10: Fraction of Packets Still in Buffers After Terminating Simulations 7.5.2 Wireless Transmission Loss Packet loss can also be caused by weak wireless links to next-hop nodes, e.g. the next hop is too far away or even out of the communication range of current packet forwarder. As shown in Fig. 7.11, the number of this type of packet loss is much higher than that of expired packets. In Fig. 7.11, we note the original GSR has about 95% packets dropped due to this reason. GSR chose nodes on road IAIC to forward packets, but the probability of network connectivity on this road was so low that most packets were dropped because there were no available next hops. The original GPSR also suffers this problem because not all packets can be routed along road IAIBIC, i.e. some packets were dropped on road IAIC or IAID before they were forwarded back to IAIBIC through perimeter searches. However, GPSR* can reduce this kind of packet loss. Because if there is no available next hop, packets are not simply dropped but buffered and sent until another next hop occurs. Since GPSR* does not have the NLP mechanism, most packets dropping in GPSR* is caused by the problem of out-of-date neighbors. 65 1 2 3 4 5 6 7 8 9 100 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Data sending rate (pkts/second) Percentage of lost packets due to weak wireless links GSR GPSR GPSR* MOVE ACAR GSR* VADD Figure 7.11: Fraction of Dropped Packets Due to Weak Wireless Links MOVE gives a fewer packet losses in this case because most packets are buffered instead of being greedily sent out. Since NLP mechanism is implemented on both VADD and GSR*, they have fewer packets dropped for this reason. For ACAR, besides NLP, it will carefully select every next hop; therefore, compared with others, it gives the lowest packet loss due to weak wireless links. In summary, we can conclude that weak wireless link is the major reason of packet loss for GSR, GPSR and GPSR*. 7.5.3 Buffer Overflow Another reason of packet loss in networks is: the buffer may be overflowed so that all in- coming packets have to be dumbed as there is no more space for them. Fig. 7.12 presents the percentage of lost packets due to this problem. As shown in the figure, VADD and GSR dropped more than 70% packets due to this reason. Therefore, if the size of buffer is large enough so that all packets can be buffered and carried by vehicles, VADD and GSR can give a similar data delivery 66 1 2 3 4 5 6 7 8 9 100 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Data sending rate (pkts/second) Percentage of dropped packets due to buffer overflow VADD GSR* MOVE GPSR* ACAR Figure 7.12: Fraction of Dropped Packets Due to Buffer Overflow ratio as that of ACAR. In other words, ACAR has a lower requirement of the capacity of buffer on vehicles to achieve a high data delivery ratio. As we mentioned before, because of the 7 rules of selecting next hop, most packets will be buffered by MOVE. So we can see from Fig. 7.12, more than 60% packets were dropped in MOVE because it has already buffered too many packets and had no space in buffer for those packets. Comparing with the packet loss caused by weak wireless link, buffer overflow problem is not a significant issue for GPSR*; but is a significant one for ACAR. Therefore, we conclude buffer overflow is the major reason of packet loss for GSR*, VADD, MOVE and ACAR. 7.6 End-to-End Delay The end-to-end delay is defined as the average time taken for a packet to be transmitted across networks from source to destination. As shown in Fig. 7.13, MOVE gives the largest end-to-end delay, which is mainly because of the long time vehicles carry packets. There are 7 forwarding rules in MOVE which determine if packets are transmitted from current node to the next hop. 67 1 2 3 4 5 6 7 8 9 100 100 200 300 400 500 600 700 Data sending rate (pkts/second) End to end data delivery delay (seconds) MOVE VADD GSR* GPSR* ACAR Figure 7.13: End-to-end Network Delay in the Scenario I Even though a neighbor is closer to the destination, it may not satisfy the forwarding rules and thus cannot relay packets. Therefore, more packets will be put into the buffers and that results in a larger delivery delay since the velocity of vehicles is much lower than the wireless transmission speed. VADD and GSR* give a similar end-to-end delay because they select the same road segment IAIC (in Fig. 3.1) to forward packets. However, the probability of network connectivity on this road is very low; thus, most packets are buffered as there is no next hop available. Since the velocity of vehicles is much slower than the speed of wireless transmission, VADD and GSR* generate a larger delay compared to ACAR and GPSR* which use connected routes on IAIBIC to forward packets. An interesting observation is that when the data sending rate increases from 1 to 10 pkts/s, the end-to-end delay of MOVE decreases from about 700 to 260 seconds, and VADD or GSR* decreases from about 400 to 100 seconds. The reason of this huge reduction is: when the data sending rate is increased, more packets will be forwarded without being buffered. For example, 68 suppose the network on IAIC is disconnected during [0.0,.5) seconds and connected within [.5,1.0] seconds. When the sending rate is 1 pkt/s, the first packet will be buffered. However, if the sending rate is 10 pkts/s, the last 5 packets are delivered without being buffered. Therefore, the average end-to-end delay of 10 pkts/s sending rate will be lower than that of 1 pkt/s case. ACAR gives the lowest end-to-end delay, since packets are forwarded along the path IAIBIC. There are 22 nodes on this road segment, so the probability its network connectivity is very high (.84). That also means most packets are delivered to the destination without being buffered, and thus ACAR saves the total time of delivering packets from the source to destination. GPSR* generates a higher end-to-end delay than that of ACAR because some packets are forwarded to road IAIC and IAID, then they are detoured to road IAIBIC by perimeter searches. So the longer delay of GPSR* is caused by the longer route. However, it still gives a lower delay compared to VADD, GSR* and MOVE. Unlike VADD, GSR* and MOVE, the end-to-end delay of ACAR and GPSR* increases as the data sending rate increases, due to two reasons. Firstly, when more packets are injected into the networks, the probability of packet collision is larger and thus the transmission delay increases. Secondly, higher network traffic increases the queuing time on each forwarder (vehicle) and also the end-to-end delay. 7.7 Network Throughput We compared the throughput of MOVE, GPSR*, GSR*, VADD and ACAR in the network shown in Fig. 3.1. Results in Fig. 7.14 show that ACAR outperforms all the other protocols, i.e. it achieves the highest network throughput of 84 kb/s. This value is about three times that of GPSR* which is second best protocol. Since packets are forwarded along routes with the highest connectivity-qualities in ACAR, link quality per hop is higher than that of others. Therefore, the data delivery ratio and end-to-end delay can be improved. We also note the shapes of GPSR and GPSR* results are very similar to that of ACAR because both GPSR and GPSR* delivered most packets along the route on IAIBIC, which is the route chosen by ACAR too. 69 0 200 400 600 800 1000 12000 10 20 30 40 50 60 70 80 90 Data sending rate (kb/s) Network throughput (kb/s) ACAR GPSR* GPSR VADD GSR* GSR MOVE Figure 7.14: Network Throughput in the Scenario I VADD and GSR* give the similar throughput as the data sending rate increases because they all chosen routes on the same road segment (IAIC) to deliver packets. Since the probability of connectivity of road IAIC is low, the throughput of VADD and GSR* is lower than that of ACAR, GPSR* and GPSR. An interesting observation of VADD and GSR* is that their throughput increase when the data sending rate increases from 1 kb/s to 500 kb/s and become stable after that. This is quite different from ACAR and GPSR*, whose throughput decrease after reaching the peak values. As mentioned previously, when the data sending rate increases, the chance of packets being delivered increases and so does the network throughput. However, if the data sending rate is so high that buffer overflows occur on nodes, the larger data sending rate is not helpful for network throughput. At this point, every node will periodically send out one packet from its buffer when a next hop is available. Since the time interval for periodic buffer checking is a fixed value, the network throughput becomes stable in this situation. 70 40 60 80 100 120 140 160 180 200 0.4 0.5 0.6 0.7 0.8 0.9 1 Number of nodes in networks Data delivery ratio ACAR VADD GSR* MOVE GPSR* Figure 7.15: Data Delivery Ratio vs Number of Nodes in the Scenario II GSR gives the second lowest throughput performance because packets will be simply dropped when it faces network disconnections which is very common on road IAIC. MOVE will choose nodes on IAID and ICID to forward packets, so the overall network throughput will be very low due to low network connectivity and longer delivery path. 7.8 Impact of Network Density To evaluate the network performance of ACAR in a more general case, we simulated networks in the second map with data from the U.S. TIGER database. We evaluate how different network densities affect the network performance, in terms of data delivery ratio and end-to-end delay. In reality, vehicles are not evenly distributed on roads, so we manually deploy more vehicles (70% of the total number) on certain roads which are highlighted by bold lines in Fig. 7.8, and fewer nodes (30%) on the others. The total number of nodes in networks varies from 40 to 200. 71 40 60 80 100 120 140 160 180 2000 50 100 150 200 250 300 Number of nodes in networks End?to?end delay (seconds) MOVE GSR* VADD ACAR GPSR* Figure 7.16: End-to-end Delay vs Number of Nodes in the Scenario II Since vehicles can only move on roads instead of the entire simulation area, we define network density as the ratio between number of nodes and the total length of all road segments. The total length of roads in the map is 7878m, so the network density varies from 1/197 to 1/40 nodes per meter. 7.8.1 Data Delivery Ratio with Different Network Densities As shown in Fig. 7.15, except for VADD and MOVE, all protocols deliver more packets as the network density increases. This is because when the number of nodes increases, the expected network connectivity probability increases too and so does the data delivery ratio. From Fig. 7.15, we note that when the network density is low, 40 to 120 nodes, GPSR* and GSR* give similar data delivery ratios. That means the perimeter search in GPSR* cannot drastically improve the data delivery ratio when network density is low, but it does help to reduce the end-to-end delay as shown in Fig. 7.16. However, when the number of nodes is larger than 120, the network con- nectivity probability increases. Then, it is more likely for GPSR* to find a connected path instead 72 of forwarding packets on the geographic shortest path. Therefore, it delivered more packets than GSR* which still forwards packets on the geographic shortest road segments. In the MOVE protocol, the larger the network density, the higher the probability of Ping-Pong situation occurring (as described in Chapter 3). So the delivery ratio of MOVE is reduced. For VADD, its data delivery ratio increases when network density is low (40?80 nodes), decreases when network density is medium (80?140 nodes), and slightly increases when network density is large (140?200 nodes). When the network density is low, VADD considers no connected network on most road segments, and will forward packets along the path with higher probability of connectivity, e.g. roads marked by bold lines in Fig. 7.8. Thus, the delivery ratio will increase when more nodes are deployed in networks. However, when the network density becomes larger, VADD may find there are some connected networks on other roads which are closer to the destination. Then, VADD will forward packets along those roads. Due to the limitation of connectivity model in VADD, probabilities of connectivity of these roads are actually very low. So the data delivery ratio decreases until these roads are really connected (140 nodes). After that, the data delivery ratio of VADD is similar to that of GSR* because both of them will choose the geographic shortest path to forward packets. The delivery ratio slightly increases when more nodes are deployed on the shortest path. 7.8.2 Network Delay with Different Network Densities The end-to-end delay of all protocols, except for VADD, drops when network density in- creases. This is because network connectivity probability increases when more nodes are de- ployed in networks. As shown in Fig. 7.16, ACAR and GPSR* give the lowest and second low- est end-to-end delay, respectively. Since ACAR forwards packets along routes with the highest connectivity-qualities, the number of buffered packets (during network disconnections) is less than that of GPSR*, resulting in a lower delay. On the other hand, when network disconnections oc- cur, GPSR* in the perimeter mode can search for another connected path (e.g. the path used by ACAR), so it also generates a small delay compared to others. 73 0 200 400 600 800 1000 1200 1400 1600 18000 100 200 300 400 500 600 700 800 Index of received packets End?to?end delay (seconds) ACAR GSR* MOVE GPSR* VADD Figure 7.17: Delay Distribution of Received Packets with 40 Nodes in the Networks GSR* only forwards packets along pre-defined routes, i.e. the geographic shortest path, so it has no opportunity to find a better connected path as GPSR* does. Therefore, it gives a much higher end-to-end delay. As mentioned above, in MOVE, nodes will carry more packets in their buffers and this will reduce the data delivery rate. Thus, MOVE gives a very high end-to-end delay. An interesting observation of VADD?s end-to-end delay is: it decreases from 40 to 80 nodes, and increases from 80 to 140 nodes, and decreases again from 140 to 200 nodes. The reason is similar to that of the delivery ratio results: with the connectivity model used in VADD, some disconnected paths are considered connected and selected as routes to forward packets. Along those frequently-disconnected paths, packets are frequently buffered so the average end-to-end delay of VADD is higher than GPSR* and ACAR. 7.8.3 Delay Distributions of Different Protocols As the end-to-end delays of ACAR and GPSR* are very similar, we further investigate the de- lay distribution of delivered packets. For example, when there are 40 nodes in networks, the delay 74 0 200 400 600 800 1000 1200 1400 1600 18000 100 200 300 400 500 600 700 800 Index of received packets End to end data delivery delay (seconds) MOVE GPSR* GSR* VADD ACAR Figure 7.18: Delay Distribution of Received Packets with 100 Nodes in the Networks distribution of received packets for all protocols is shown in Fig. 7.17. The x-axis denotes indices of the received packets, and y-axis for end-to-end delays which are measured in seconds. We order received packets by their end-to-end delays. Dots denote the end-to-end delays of corresponding packets. As we can see, ACAR delivers most packets with smaller delays; while in GPSR*, some delivered packets have very large delays (a few hundred seconds). In addition, although GPSR* and GSR* deliver similar numbers of packets, GPSR* definitely routes packets along faster but longer paths than those used by GSR*. Some packets (1st to 600th) in GPSR* are delivered successfully along connected paths, while others (after 600th) are buffered and carried by vehicles. Since paths selected by GPSR* are longer, delays of some packets circled in Fig. 7.17 are even larger than those of GSR*. However, this situation changed when the network density is increased to 100 nodes, as shown in Figure 7.18. With larger network density, GPSR* can deliver more packets with large delay to the destina- tion. However, no matter what the network density is, given a certain delay value, ACAR delivered 75 5 10 15 20 25 30 35 400.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Average velocity of vehicles (m/s) Data delivery ratio ACAR VADD GSR* MOVE GPSR* Figure 7.19: Data Delivery Ratio vs Different Velocities with 100 Nodes in the Networks more packets than any of the others. In summary, we conclude that ACAR not only gives the lowest average delay but also delivers more packets with smaller delays compared to other protocols. 7.9 Impact of Velocity Since mobility of nodes may affect the performance of protocols, we simulated networks with 100 nodes moving with different velocities. As shown in Fig. 7.19, when networks become more dynamic, the data delivery ratio decreases for all protocols. However, ACAR is only slightly affected (reduced by 1%) by the change of node mobility. This is because higher velocity does not affect our connectivity model but only the choice of each next hop. In fact, the larger the velocity, the lower the accuracy of predicting neighbors positions. Since we implemented NLP on VADD and GSR*, their data delivery ratios drop more slowly than GPSR* and MOVE. For GPSR*, as no NLP algorithm is available, it may select next hops which are already out of the communication range due to the high speed of its neighbors. The 76 5 10 15 20 25 30 35 400 50 100 150 200 250 Average velocity of vehicles (m/s) End?to?end delay (seconds) ACAR VADD GSR* GPSR* MOVE Figure 7.20: End-to-end Delay vs Different Velocities with 100 Nodes in the Networks situation is even worse for MOVE protocol. Unlike other protocols in which packets are routed on either geographic shortest paths or high connectivity paths, MOVE forwards packets to nodes moving towards the destination. However, this node may move away from the destination a few seconds later. If no next hop is available, which is very common for MOVE, current forwarder (carrying packets) will move away from the destination very fast and so extends the total routing path. The longer the route, the higher is the chance of wrongly selecting next hops. So the delivery ratio of MOVE drops very fast when the velocity increases. As shown in Fig. 7.20, the end-to-end delay of ACAR is very low because ACAR forwards packets on routes with the highest connectivity-qualities. So the delay of ACAR is mainly com- posed of wireless transmission and protocol queuing delays, which are very small. Since GPSR* utilizes the perimeter mode to find connected paths, its delay is also very low. However, end-to-end delays of VADD, GSR* and MOVE are much higher and drop when the velocity increases. Be- cause VADD, GSR* and MOVE have no mechanisms for selecting connected paths, their delays 77 1 2 3 4 5 6 7 8 9 100 50 100 150 200 250 300 Data sending rate in networks of 100 nodes Number of sent pkts per received pkt ACAR VADD GSR* GPSR* MOVE Figure 7.21: Number of Packets Sent in Networks Per Delivered Packet with 100 Nodes in the Networks are higher due to more packets being buffered. In addition, when the velocity increases, packet carriers can move faster to the destination and thus decrease the average end-to-end delay. 7.10 Networking Overhead Networking overhead is defined as the number of packets sent into networks for every deliv- ered packet. In other words, it is the ratio between the number of sent packets (beacon and data messages) and the number of received packets. As every node sends beacon messages periodically, e.g. every one second, this kind of packets make up the majority of networking overhead. When the data sending rate increases, more packets will be delivered to the destination, so the overall networking overhead decreases. The total number of sent packets for all protocols are similar, so the networking overhead of ACAR is the lowest as it delivers more packets than others (Fig. 7.21). In ACAR, there is an on-the-fly density collection scheme which will increase the size of every forwarded packet. So we further evaluate the networking overhead by investigating the total size of packets sent into networks per delivered packet. As the periodic beacon scheme is the same 78 1 2 3 4 5 6 7 8 9 100.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 x 10 4 Data sending rate in networks of 100 nodes Aggregated size of pkts sent per received pkt ACAR VADD GSR* GPSR* MOVE Figure 7.22: Size of Packets Sent in Networks Per Delivered Packet with 100 Nodes in the Net- works for all protocols, we only consider the size of data packets here. As shown in Fig. 7.22, ACAR gives the lowest networking overhead in terms of the average size of data messages per delivered packet. The major reason is that ACAR delivers more packets than others, so reduces the overall networking overhead. 79 Chapter 8 Location Privacy Protection in VANET In previous sections, we proposed and discussed in detail the adaptive connectivity aware routing protocol which is built upon the fundamental geographic routing. However, geographic routing requires every vehicle to broadcast its location information to its neighboring nodes, and this process will compromise user?s location privacy. Existing solutions to this problem can be categorized into two groups: 1) hiding user?s location or 2) preserving user?s identification infor- mation in routing protocols, which drastically reduce network performances. To address this issue, we proposed a dummy-based location privacy protection (DBLPP) routing protocol, in which rout- ing decision is made based upon the dummy distance to the destination (DOD), instead of users? true locations. In this scheme, users? true locations and identification information are preserved, so the user?s location privacy is protected. Our protocol is compared to existing solutions by sim- ulations, results show that the DBLPP provides similar network performances as other routing protocols, and achieves a higher level of location privacy protection on vehicles in networks. 8.1 Introduction of Location Privacy Issues in VANET To support geographic routing in VANETs, most routing protocols require location informa- tion of vehicles being periodically exchanged among one-hop neighbors. This broadcasting pro- cess will release a user?s location and identification information to its neighbors in which malicious nodes may exist. For example, by passively overhearing these beacon messages, an adversary can easily identify the locations visited by a certain vehicle and then breach the privacy of this user. Location privacy protection of geographic routing can be defined as: without losing the ben- efits of geographic routing, a routing protocol should not reveal any user?s current and historical 80 locations to unauthorized nodes. The unauthorized nodes may be malicious infrastructures (e.g WiFi access points), laptops with wireless interfaces, or vehicles moving on roads. There are several previous works on protecting user?s location privacy. They can be cat- egorized into two groups: preservation of node identity (ID) [47, 50, 51] and geographic loca- tion [53?55]. If a user?s identity is hidden, even though the adversary eavesdrops this user?s loca- tions, it cannot link those locations to the user [46]. However, it is almost impossible to completely eliminate a vehicle?s identity because ID information is critical for routing, security and billing purposes. Therefore, randomly-changing pseudonyms are used on vehicles to replace the perma- nent ID in VANETs [47,50,51]. However, when pseudonyms are applied on vehicles, the network performance can be drastically affected as it was shown in [52]. Another approach is hiding vehicle?s location information [53?55] so that the adversary can only detect an area (where a node is located) but not the node?s true location. Since location information is the foundation of geographic routing protocols [10, 11, 13, 42], geographic routing will fail if such information is not provided. To avoid periodically broadcasting location information, another type of geographic routing ? contention based forwarding (CBF) [61] is proposed. In CBF, only nodes participating in routing reveal their locations. Therefore, the location privacies of other nodes are preserved because they keep silent in the routing process. To further preserve the location privacies of nodes involved in routing, we propose a dummy-based location privacy protection (DBLPP) protocol. Unlike sending its real locations in CBF, a packet forwarder (vehicle) first sends a dummy distance to destination (DOD) to its neighbors. After receiving the dummy DOD information, receivers com- pete to each other and the one which is the closest to the destination will be elected as the next hop. Packets are then sent to this node, and it will route the packets just as its last-hop node did. The dummy DOD has to be carefully chosen so that not only the adversary is not able to infer the forwarder?s true location, but also the geographic routing goals are achieved. 81 To measure how well a protocol protects user?s location privacy, we proposed a novel entropy based location privacy protection metric. This metric models the entropy (in the unit of bits) re- quired for the adversary to attach user?s location privacy. The network performance of DBLPP protocol is compared with existing solutions by simulations. Results show that DBLPP can pro- vide similar network performances as those of other protocols. In addition, with the new privacy protection metric, we also discovery DBLPP achieves a higher level of location privacy protection comparing to others. 8.2 Threat Model and Problem Statement 8.2.1 Threat Model in VANET Geographic routing in VANETs can significantly facilitate the tracking of vehicles. Because location information is shared among neighbors in geographic routing protocols such as [10,61,62], attackers can easily eavesdrops on vehicle?s and location. This may cause the leakage of a driver?s privacy, e.g. a patient at an AIDS testing clinic might not want his or her movements (or even evidence of a visit) revealed to others. The adversary can be external, which installs its own wireless receivers along roads and pas- sively eavesdrops on vehicle?s communication messages. As stated in [51, 63], by exploiting al- ready deployed 802.11a/b/g infrastructures, it is possible to build a global adversary which eaves- drops on the entire networks. The attackers can also be internal, which utilize devices that are legitimate members in VANETs. Such type of malicious nodes may passively collect data transmitted among neighboring nodes by the pre-installed IEEE 802.11 receiver. In our work, we assume both internal and external mali- cious nodes exist in the networks. 82 8.2.2 Greedy Forwarding Model A vehicular ad hoc networking can be represented as a directed graph G = (V,E), where V is the set of nodes (vehicles) and E is the set of wireless links, such that packets can be sent from node i to j for all (i,j) ? E. Node i and j are called the origin and destination of link (i,j), respectively,. The origin and destination of a link l ? E are denoted o(l) and d(l), respectively. We assume o(l) negationslash= d(l) for?l ?E. For each node i, we assume it has the same communication range R as others. If node i is located at (xi,yi), we define its communication area as Ai which is a circle centered at i with radius of R. As shown in Fig. 8.1, suppose the current packet forwarder is node i, its neighbor set Ni can be represented as follows. Ni ={k : d(l) = k?o(l) = i,?l?E} (8.1) If we track all the outgoing links l?E from node i, i.e. o(l) = i, we can find a set of nodes k on the other sides of these links. These node denoted by k are actually the neighbors of node i. The purpose of greedy geographic routing is to select the neighbor which is the closest to the destination as the next hop. Therefore, the next hop should be: arg ?k?Ni maxP(i,k,d) = braceleftBigg 0, dis(i,d)?dis(k,d)R bracerightBigg (8.2) where function dis(k,d) provides the distance between node k and the destination d. As VANET is a dynamic mobile network, the graph G may be different from time to time. However, for a certain time instance t, we consider it as a static graph, i.e., G = Gt at time instance t. 8.2.3 Problem Statement of Location Privacy Protection in Greedy Forwarding Greedy forwarding is widely used in geographic routing protocols, such as GPSR and CBF. In GPSR, every node in networks periodically beacons its ID and location to its neighbors and 83 thus cause a significant privacy issue. However, in CBF, only those nodes participating in routing share their location information. The problem we are solving is to check if the ID and location information are necessary to achieve greedy forwarding. If not, we investigate how to preserve those information so that the network performance is not significantly affected. In CBF, node i first broadcasts a request message to its neighbors and waits for replies. When a neighbor k ? Ni receives this packet, it sets up a timer with the interval of T(1?P(i,k,d)) where T is the maximum one-hop forwarding delay. Let Ad denote the circle centered at the destination with radius of dis(i,d), then nodes within the area of (Ai?Ad) do not set up timers since they are farther to the destination compared to the node i. Then, the node which is the closest to the destination, e.g. j, will first time out and reply to the sender i because of the shortest timer interval. This reply also serves as a suppression message to other neighbors. That means nodes in {k : o(l) = j?d(l) = k,?k?(Ai?Ad)}will cancel their timers. From the above analysis, location information seems to be critical for geographic routing. If there is a global adversary or some passive malicious nodes in networks, the driver?s location privacy cannot be protected. Therefore, the challenging problem we exploited is to develop tech- niques that let a user benefits from location-based geographic routing, at the same time, retains its location privacy. The proposed protocol must satisfy the following conditions: ? User?s location information should be protected ? Greedy forwarding should be achieved, i.e., every selected next hop must be the one which is closest to the destination ? Not too much overhead is added to existing routing protocols ? Network performance should be similar as that of original ones 8.3 Details of DBLPP Protocol In DBLPP, before a data packet is transmitted, a packet forwarder first sends a request to forward (RTF) message. In such RTF message, the sender will provide a dummy DOD, instead of 84 its real location. Then, the elected next hop sends pseudonyms instead of its true ID in the clear to forward (CTF) message to reply the sender. Finally, the data packet will be transmitted from the sender to the next hop. This process is different from the active selection in the contention based forwarding with active selection (so-called CBF-AS) because the DBLPP does not release forwarder?s location or next hop?s identification. 8.3.1 Control Messages Exchange in DBLPP In this section, we will describe how a next hop is chosen in DBLPP. As shown in Fig. 8.1, suppose the current packet forwarder is node i which received a packet with the sequence number of seq# from node m. This packet will be delivered to the destination located at (xd,yd). In the figure, we note node j should be the next hop as it is closer to the destination comparing to other neighbors. Before forwarding this data packet, node i first broadcasts a RTF message including the seq# and (xd,yd). To illustrate the basic idea of greedy forwarding in DBLPP, we currently do not use the dummy DOD which will be introduced later. When a neighbor (e.g. node k) receives this RTF, it first checks if the packet was received before by comparing the sequence number in the RFT to those of buffered packets. If there is a cache hit, node k will simply drop the RTF because it received this RTF before. If the RTF is a brand new message, node k saves this RTF into its buffer and then sets up a timer with the runtime of: t(rk) = f(1?1/rk) (8.3) where rk is the DOD of node k. According to the above equation, the runtime of timer on each node is proportional to its DOD. Therefore, the one which is the closest to the destination will first time out. As shown in Fig. 8.1, node j first times out and sends the CTF message including the seq# and a set of pseudonyms denoted as < IDl >. These l pseudonyms in < IDl > are randomly chosen from a set of L pseudonyms which are pre-installed in each vehicle. Given a relatively large 85 Figure 8.1: Dummy Based RTF/CTF Exchange Among Vehicles value of L and l, the probability of choosing the same pseudonym in two different CTF messages will be extremely low. This CTF message also serves as a suppression message for all j?s neighbors. When these nodes (neighbors of node j and i) receive this CTF message, they will immediately cancel their timers because there is a better next hop selected. Since the CTF from j can only suppress its neighbors, those nodes which are neighbors of node i but not node j may send duplicated CTF messages. That means multiple CTFs may be received at the sender i. After receiving the first CTF sent from j, node i immediately sends the data packet including the pseudonyms < IDl > of previously received CTF from node j. If node i sends the data packet before the second CTF is received, all its neighbors are suppressed by the data message. If a duplicated CTF message is received before the data packet is sent, node i simply omits this CTF because a better next hop is already chosen. 86 Figure 8.2: State Machine Of Nodes in DBLPP When a neighbor of node i receives the data packet, if it did not send any CTF message, it drops the data message. Otherwise, it checks whether the < IDl > in the data packet are the same as what it sent out previously. If so, the packet are delivered; otherwise, the packet is dropped. By exchanging one pair of RTF and CTF messages, geographic greedy forwarding is achieved between node i and j. The whole process of such control message exchange will be better ex- plained by using state machine transition diagram. As shown in Fig. 8.2, when the system starts, all nodes are in the IDLE mode. Depending on what type of message is received, a node will change its mode as follows. 1. A node changes its mode from IDLE to SEND only if it intends to send data packets to another node (destination) in the networks. To successfully send out a data packet, this node (sender) first sends a RTF message to its neighbors. 2. When the sender?s neighbors receive this RTF message, they come into the TIMER mode in which timers are set up according to the neighbors? DODs. 87 3. The node which is the closest to the destination will first time out and fire the CTF message. That means it is elected as the next hop of the sender. After it sends out CTF, it goes into the RECV mode which indicates it is ready to receive data packets. 4. When the sender receives this CTF message, it unicasts data to the next hop and returns to IDLE mode. 5. If the next hop is not the destination, it will come to the SEND mode to keep forwarding the data packet. 6. If it is the destination, it delivers the message and comes to IDLE. 7. It is possible that the next hop receives a duplicated CTF from another node as we will discuss in Section 8.3.2. It will simply dump this duplicated CTF message. 8. Other neighbors of the sender also receive the RTF message and set up timers as shown in step 2. When they receive a CTF or data packet before their timers expire, they will cancel the timers because there is a better next hop selected. In those cases, they return to IDLE from TIMER mode. 9. When a node is in IDLE mode and receives a CTF or data packet, it will ignore those mes- sages and keep in IDLE mode. Because it was not involved in any network activities, it needs to be silent. 8.3.2 Duplicated Responses and Location Privacy Protection In the previous section, we notice that there may be multiple duplicated CTFs in the net- works. These duplicated CTFs are useless for forwarding data packets but harmful for network performance. On the other, from the length of a timer, the adversary can easily infer the DODs of corresponding nodes. Then, it can comprise the user?s location privacy. Therefore, it is important to set up a proper timer so that the location privacies of receivers and senders are preserved and 88 the number of duplication CTFs is minimized. In this section, we will investigate how to set up a timer to achieve those two goals. According to Equation 8.3, when the timer of a node expires depends only on the node?s DOD. Therefore, a simple way to set up a timer of a node with DOD as r will be: t(r) = T?(1?1/r) (8.4) where T is the maximal one-hop forwarding delay. If timers are set up in this way, duplicated responses may be generated by receivers in a certain area, called duplication area. As shown in Fig. 8.3, suppose the best next hop is located at r1 away from the destination. Assume there is another node with the DOD of r such that t(r)?t(r1) < ?, where ? is the minimal time interval required for successful suppression. Then, this node will send a duplication response before the CTF from the best suited node can successfully suppress its timer. Obviously, the larger the width of the duplication area, the more duplicated responses will be generated. Following Equation 8.4, the value of T needs to be very large to achieve a reasonable small duplication area. For example, according to Equation 8.4, the timer?s interval on the best suited node should be t(r1) = T ?(1?1/r1). Duplicated messages can be generated from another node with the DOD of r satisfying the following condition: t(r1) < t(r) < t(r1) + ? = T(1? 1r 1 ) + ? (8.5) To avoid generating duplicated messages, the node needs to set up a timer with runtime greater than: t(r) = T parenleftbigg 1? 1r 1 parenrightbigg + ? = T ? ?1? 1r 1T T??r1 ? ? (8.6) The width of duplication area can be computed as: r1T T??r1 ?r1 = ?r21 T??r1 (8.7) 89 Figure 8.3: Duplicated Responses and Duplication Area Since ? is a fixed value, we can rewrite the maximal one-hop forwarding delay T as k??. To achieve an acceptable duplication area with the width of ?, the following equation must hold: ?r21 T??r1 = r21 k?r1 < ? (8.8) In other words, the delay T will be: T = r 2 1 + r1? ? ?? (8.9) From the above equation, we find that the longer the DOD of a node, the larger the value of T will be. However, the value of T must be very small to avoid large networking delays. To address this issue, we modify the Equation 8.4 by considering the dummy DOD information obtained from the last-hop node. Suppose a node (current packet forwarder) sends a RTF packet, all receivers will set timers according to the following equation: 90 Figure 8.4: Dummy DOD Selection On Packet Forwarder t(r) = T? parenleftbiggr??r f 3R parenrightbigg (8.10) where r is the DOD of a receiver and ?rf is the dummy DOD information from the received RTF. The value of ?rf is randomly chosen, so the real location of last hop node is preserved. The selection of dummy DOD ?rf is shown in Fig. 8.4. We first randomly choose a point on the line between current packet forwarder and the destination. This point must be R away but within 2R from the packet forwarder, where R is the wireless communication range. The value of ?rf can be computed as: ?rf = rf ?(1 + ?)?R (8.11) where rf is the real DOD of the forwarder, and ? is a real number randomly chosen from (0,1). Since the value of ? ranges from 0 to 1, the forwarder?s real location is hidden within a range of R. That means the difference|rf ??rf|between the real and dummy DODs is within [R,2R]. By using the random variable ?, the forwarder?s location is protected. 91 We also know that r??rf is equal to r?rf +(1+?)?R. Since the forwarder and the receiver are neighbors, the value of r?rf must be within [?R,R]. Therefore, the value of r??rf is within [0,3R]. According to Equation 8.10, the runtime of the timer on this node will be within [0,T]. Therefore, the value of T is independent upon a node?s DOD and it does not need to be very large to reduce the number of duplicated CTFs. With these equations, we calculate the width of duplication area as 3R??/T. If T = k??, to achieve an acceptable duplication area, we must have: T = 3R???? (8.12) We note that the one-hop maximal delay in the above equation is a fixed value. This delay is much smaller than what is computed from Equation 8.9, and is acceptable in VANETs. Since dummy DODs and pseudonyms can preserve the locations and identifications of ve- hicles, the DBLPP provides a higher level of location privacy protection on vehicles in VANETs. Meanwhile, with the active selection of every next hop, geographic routing is achieved in networks as well. In addition, the number of duplication responses and average one-hop delay are reduced in DBLPP comparing to the original CBF-AS. 8.4 Entropy Based Privacy Protection Measure To evaluate a location privacy protection scheme, we need to measure the hardness of an ad- versary node attacking a user?s location privacy. Therefore, we propose an entropy based location privacy protection metric. As we described in previous sections, the location privacy of vehicles in VANETs includes two types of information: node?s identification and location. Previous works on location privacy protection either focus on the preservation of node?s location or node identification. We claimed that preservations of both ID and location are necessary because it is possible for the adversary node to detect the node ID or location. For example, the IEEE 802.11 MAC address or IP address 92 Figure 8.5: Matrix Recording Possible Node Identifications And Locations of a vehicle can be easily captured by wireless network sniffer software. On the other hand, there are many available wireless localization technologies which can be utilized by the adversary node to track user?s locations. In our work, we assume it is impossible or costly expensive for the adversary detecting both node?s ID and location. We first model the probability of the adversary node being able to predict a user?s ID and location information in VANETs. Because this probability is usually very small, it is difficult to distinguish the difference between different privacy location protection schemes. Therefore, we use entropy to model the overall hardness of location privacy attack on the adversary node. We define two matrices and denote them as IM(s,p) and LM(s,p), respectively. Each matrix contains two dimensions: node IDs and locations. As shown in Fig. 8.5, the dimension denoted as I = I1,I2,???,In records all nodes IDs in networks. The other dimension denoted as L = L1,L2,???,Ln is used to record node?s locations information. The initial value of IM(s,p) and LM(s,p) is 0. It will be updated by adding 1 if the adversary node receives a message indicating node Ii is probably located at Lj. 93 At a certain time instance t, there will be several communications occurring between nodes. Let?s look at the communication link between node i and j, as shown in Fig. 8.1. Node i first sends out a RTF including its dummy DOD to its neighbors. Then, node j sends a CTF contain- ing pseudonyms to node i. Finally, data packets are delivered from i to j with the pseudonyms previously received from j. In the first step, node i releases its rough location to the networks by providing a dummy DOD. Since the dummy DOD is randomly chosen, there may be other nearby nodes providing the same DOD and those nodes can be presented as: ?i ={k : dis(k,d) > [dis(i,d)?R]?dis(k,d) < [dis(i,d) + R]} (8.13) where dis(k,d) and dis(i,d) are the DODs of node k and i, respectively. In this case, the adversary node updates LM(s,p) to LM(s,p) + 1 where p = Lk(k??i) because any node k??i can give the same dummy DOD. Therefore, from this dummy DOD of node i, the adversary node can only predict this message was from ?i but not sure which node in the set. For example, suppose node n1 and n2 are in the set of ?i. The adversary node only knows there is a message from location L1, L2 or Li, but has no idea about who sent this RTF. Therefore, as shown in Fig. 8.5, the adversary node updates LM(s,p) = LM(s,p) + 1 where s = I1,I2,???,In,p = L1,L2,Li. Similarly, if the CBF protocol is used, we need to update LM(s,p) = LM(s,p) + 1 where s = I1,I2,???,In,p = Li. For the second step, node j sends a set of randomly chosen pseudonyms in its CTF mes- sage. Because every node can send the same pseudonyms, the adversary node leans nothing about sender?s ID information from this message. In this case, it updates the matrix by changing IM(s,p) to IM(s,p) + 1 for all s = I1,I2,???,In and p = L1,L2,???,Ln. For the third step, since there is no more new information (identification or location) revealed in packets, we simply omit this step in the privacy protection measurement. If we look at the CBF-AS protocol, a packet forwarder i sends out RTF along with its location. The next hop j sends CTF along with its ID to the previous packet sender. In the first step, we set LM(s,p) = LM(s,p) + 1, where p = Li, for every s = I1,I2,???,In. In this case, the 94 adversary node only needs to predict from which node this message is sent. In the second step, we set IM(s,p) = IM(s,p) + 1, where s = Ij, for every p = L1,L2,???,Ln. This is because the adversary node only needs to predict where node j is. For a matrix M (either IM or LM), the value of M(s,p) records the number of times that node s probably appear at location p. The entries of M are proportional to the joint probabilities, which we obtain by normalization: P(s = I0,p = L0) = M(I0,L0)summationtext s,p M(s,p) (8.14) This equation models the probability of the adversary node being able to predict that node I0 is at location L0. For example, if the adversary node receives a RTF from node I0, the probability of the adversary node being able to predict node I0 is located at L0 will be 1/n. If the adversary node receives one CTF, the pseudonyms provide nothing useful about node identifications. Therefore, the probability will be 1/n2 because this message can be sent from any node at any location. If the adversary node can spoof node?s ID, the conditional probability of the node I0 being located at L0 will be: P(p = L0|s = I0) = M(I0,L0)summationtext p M(I0,p) (8.15) Therefore, the Shannon?s entropy required by the adversary node to correctly predict that node I0 is located at L0 will be: HLI0 = summationdisplay p P(p|s = I0)?log 1P(p|s = I 0) (8.16) Similarly, if the adversary node can detect a node?s location, the conditional probability that at location L0, the node must be I0 is: P(s = I0|p = L0) = M(I0,L0)summationtext s M(s,L0) (8.17) 95 So we can compute the entropy of predicting that at location L0, the node must be I0: HIL0 = summationdisplay s P(s|p = L0)?log 1P(s|p = L 0) (8.18) If the adversary node can localize node?s locations easily, the uncertainty of predicting IDs of all nodes will be cumulative entropy: EI = summationdisplay s HIp,p = L1,L2,???,Ln (8.19) where we assume the network events (e.g. sending RTF message) are independent to each other. Therefore, cumulative entropy models the hardness of the adversary node to predict all nodes IDs. If these events are dependent to each other, we can use the average entropy to model the hardness of predicting only one node?s ID. This average entropy can be computed as ?EI = EI/n. If the adversary node can detect node?s IDs easily, the uncertainty of predicting locations of all nodes can be modeled as cumulative entropy: EL = summationdisplay s HLs ,s = I1,I2,???,In (8.20) where we also assume network events are independent to each other. Similarly, when these events are dependent to each other, the average entropy ?EL = EL/n can be used. Suppose the costs of enabling identification spoofing and localization at the adversary node are cI and cL, respectively. Then, we obtain the balanced cumulative entropy as: H(M) = wI?EL + wL?EI (8.21) where wI = cI/(cI + cL) and wL = cL/(cI + cL). The two matrices IM and LM record events of sending RTF and CTF messages, respectively. Therefore, the cumulative entropy required by the adversary node will be H = H(IM) + H(LM). H(IM) is the entropy of predicting a node?s 96 Table 8.1: Simulation Set-Up Parameters for DBLPP Parameter Value Number of lanes 2 lanes per direction Number of nodes 100 Communication range 250 m Max. one-hop delay T 0.1 ms Size of pseudonyms pool 1000 Number of pseudonyms in CTF 5 locations if the ID information is given. The second H(LM) is the entropy of predicting a node?s ID if location data are given. From the Equation 8.21, we note that the higher the cumulative entropy, the harder it will be for the adversary attacking user?s location privacy. In the same way, we obtain the average entropy as: ?H(M) = wI? ?EL + wL? ?EI (8.22) Accumulate or average entropy will be used to measure how well a location privacy protection scheme works. We will use them in our simulations to quantify the location privacy protection measurement of DBLPP and other methods. 8.5 Simulations of DBLPP We implement the DBLPP protocol in ns-2.29 and compare its network performance to other two geographic routing protocols: GPSR and CBF-AS. To evaluate the location privacy protection in DBLPP, we implement the periodic changing-pseudonym scheme which is widely used in pre- vious works [47, 50, 51]. Therefore, by extending the GPSR and CBF-AS, we have another two protocols with the periodic changing-pseudonym scheme: CBF-AS-ID and GPSR-ID. Details of the simulation setup parameters are listed in Table 8.1. The movement of vehicles in the networks is generated by VanetMobiSim [41]. 97 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Data sending rate (pkts/s) Data delivery ratio DBLPP CBF?AS CBF?AS?ID GPSR?ID GPSR Figure 8.6: Data Delivery Ratio Vs Data Sending Rate for DBLPP 8.5.1 Data Delivery Ratio Data delivery ratio is defined as the number of received packets at the destination divided by the number of sent packets from the source. As shown in Fig. 8.6, DBLPP, CBF-AS, CBF-AS-ID and GPSR achieve similar data delivery ratios. GPSR-ID gives the lowest data delivery ratio because chosen next hops often change their IDs so that it cannot receive packets which supposed to be delivered to them. In GPSR, every node selects the next hop based on the stored neighbor?s location information. Since neighbor?s location information is updated periodically, it is possible that out-of-date neighbors exist in one?s neighbor list. In this case, packets may be dropped because the selected next hop may be out of communication range. In DBLPP, the next hop will be elected through competitions and only the winner response to the packet forwarder. Packets will then be immediately sent to this elected next hop. So the chance 98 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 Data sending rate (pkts/s) End?to?end delay (s) DBLPP CBF?AS CBF?AS?ID GPSR?ID GPSR Figure 8.7: End-to-end Delay Vs Data Sending Rate for DBLPP of forwarding packets to an out-of-date neighbor in DBLPP is very low. This is why DBLPP delivers more packets than GPSR. Because the contention based forwarding scheme is used in DBLPP and CBF-AS, the data delivery ratios of these two protocols are similar. Although periodic changing ID is applied on CBF-AS-ID, its data delivery ratio is slightly worse than those of DBLPP and CBF-AS. This is because after a next hop sends its ID in a CTF message, the sender immediately delivers data packets, the time difference between those two events is too small to allow the next hop change its ID. 8.5.2 End-to-end Delay The end-to-end delay is defined as the average time taken for a packet being transmitted from source to destination in the networks. As shown in Fig. 8.7, GPSR and GPSR-ID provide smaller end-to-end delays compared to other protocols because GPSR and GPSR-ID do not need to set up timer to select next hops. However, in DBLPP, CBF-AS and CBF-AS-ID, timers are used in every 99 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 110 1 102 103 Data sending rate (pkts/s) Network throughput (pkts/s) DBLPP CBF?AS CBF?AS?ID GPSR?ID GPSR Figure 8.8: Network Throughput Vs Data Sending Rate for DBLPP next hop selection. Therefore, the end-to-end delays of CBF-AS, CBF-AS-ID and DBLPP become large. However, with the same contention based forwarding scheme, DBLPP generates a larger end-to-end delay comparing to CBF-AS and CBF-AS-ID. The reason is that DBLPP generates more duplicated responses which cause networks become more congested and thus the end-to-end delay increases. This delay can be further reduced by using a smaller maximal-runtime of timers, which will be our future work. Since frequent network disconnections occur in VANETs, carry-and-forward based geographic routing protocols [13,14,42] are widely used in VANETs. Comparing to the huge delay caused by carry-and-forward scheme, these generated by DBLPP can be ignored. 8.5.3 Network Throughput Network throughput is defined as the number of packet delivered to the destination per second. As shown in Fig. 8.8, besides GPSR-ID, all protocols give similar network throughput which 100 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10 2 4 6 8 10 12 14 Data sending rate (pkts/s) Average entropy(bits) DBLPP CBF?AS?ID CBF?AS GPSR?ID GPSR Figure 8.9: Average Entropy of Location Privacy Protection increases as the data sending rate increases. Because the link quality of every hop in DBLPP is better than that of GPSR, DBLPP achieves a slightly larger network throughput than GPSR. 8.5.4 Location Privacy Protection Entropy was first introduced in Information Theory to quantify the uncertainty of a system. In our work, the higher the privacy entropy value is, the more difficult it will be for attackers predicting user?s location. In the simulations, we tracked all communication events (RTF, CTF and data packets) and computed the probability of predicting the location and identification information of a node involved in routing. Based on the definition of entropy, we then calculate the average entropy required for the adversary to predict a user?s location and identification. As shown in Fig. 8.9, in order to attack a vehicle?s location privacy, more bits are required in DBLPP compared to others. In GPSR, every node periodically beacons its location and ID to neighbors, so the entropy of computing every vehicle?s location is zero. In CBF-AS, every packet forwarder sends its location (not ID) in RTF messages to its neighbors. When the self-elected next 101 hop sends a CTF message, its ID (not location) is put into the packet. Because either ID or location information is protected in CBF-AS, it provides a higher entropy value. In DBLPP, dummy DODs and pseudonyms are used, so it requires more bits for the adversary to attack even one node?s lo- cation. Although the CBF-AS-ID and GPSR-ID can provide a certain degree of location privacy protection, they are not as good as DBLPP. It is because DBLPP preserves both identification and location information while the random changing-pseudonym scheme only protects user?s identifi- cation data. In summary, the location privacy protection in DBLPP is much better than others. 102 Chapter 9 Future Work In the previous chapters, we proposed and evaluated the ACAR and DBLPP protocols for efficient and privacy-protection communications in VANETs. However, it is not straightforward to integrate those two protocols. Although ACAR is built upon regular greedy geographic routing, it uses a unique method to select every next hop in the routing process. There are basically three differences between ACAR and DBLPP in forwarding packets in networks. First, ACAR requires every node to broadcast periodically its location and ID information in the network. However, to preserve user?s location privacy, such broadcasting procedure is not needed in DBLPP. Second, DBLPP selects a next hop based on how much distance advance a neighbor can provides, i.e. the next hop must gives the maximal distance advance. While when ACAR selects a next hop, the maximal distance advance is not the determining factor. It also considers the EXT information which models a link?s quality. Third, ACAR is a trajectory based routing protocol which means packets are forwarded along a computed path (that is composed of several road segments). The DBLPP is a location based protocol, so it does not consider any road topology information in its routing process. To successfully integrate ACAR and DBLPP, those three differences has to be considered. For the first difference, as we discussed in previous chapters, broadcasting location and ID informa- tion is not necessary for geographic routing. For the second difference, since a node obtains and maintains EXT information from its neighbor?s beacon message, broadcasting seems necessary for ACAR. There are two possible solutions for this issue: 1) adding broadcasting to DBLPP, and 2) modeling link quality without broadcasting. If a broadcasting scheme is added to DBLPP, only pseudonyms are sent in beacon messages to preserver user?s location privacy. In this way, a node can easily record the qualities of links to its neighbors without revealing its own true ID. On the 103 other hand, ETX is only one metric modeling link?s quality, many other metrics may be applied as well. In this case, broadcasting is not essential for ACAR?s next hop selection. The third difference is related to the second one, if ETX is replaced by other metrics, a new next hop selection algo- rithm is needed for ACAR. Because DBLPP uses contention based forwarding, this new algorithm must be able to properly set up timers so that the next hop (with the best link quality and distance advance) will first time out and then is elected from other neighbors. Current active selection of next hop in DBLPP generates too much network overhead. To reduce such overhead, the DBLPP protocol can also be implemented in the RTS/CTS exchange of 802.11 protocols. Besides the regular data in RTS and CTS packets, we will add a few more information e.g. packet sequence number, destination location, pseudonyms. Such modification can be easily implemented in current MAC protocol stack. Therefore, the new RTS/CTS design can be programmed as a software library which is integrated to current 802.11 protocol stacks. Moreover, as greedy geographic forwarding is widely used in date communication for mobile devices, such as smart phones, PDAs and iPhones, the DBLPP protocol can be also applied to pervasive computing to achieve a high level protection of user?s location privacy. 104 Chapter 10 Conclusion We have presented a protocol for adaptively selecting routes based on statistical and real- time network information to avoid the influence of inaccurate statistical data. This protocol uses a novel model of network connectivity, which combines the cell-based and cluster-based connec- tivity models to capture the probabilistic property of network connectivity on road segments. The connectivity model considers the uniform (cell-based) and clustered (cluster-based) movements of vehicles, and provides a scheme to combine those two phenomena and computes network connec- tivity. Although the model requires historical data (e.g. road length, network density and traffic light period) from digital maps, connectivity information can be computed by every vehicle in a distributed manner. Because the selected path provides the best connectivity-quality, ACAR achieves a higher data delivery ratio and lower end-to-end delay compared to other protocols. Moreover, since the route length can be calculated before forwarding packets, every next hop is selected by minimizing the packet error rate of the entire path. Our simulation results show that ACAR is much more suitable for VANET than other protocols because of its higher data delivery ratio, throughput and lower networking delay. In addition, it works very well even when the statistical data of road density is not accurate. Since computations are performed on each vehicle, there is no additional network overhead in ACAR compared to other protocols. Every vehicle in the network only maintains its one-hop neighbors? information, so ACAR is a stateless routing protocol. Because every packet forwarder computes the best route and selects next hops individually, the implementation of ACAR algo- rithm is distributed and scalable. In summary, due to the smaller network overhead, stateless and distributed features, ACAR is a practical and efficient routing protocol for VANETs. 105 We also designed and implemented a dummy-based location privacy protection mechanism on geographic routing, which can be easily added to greedy geographic routing protocols. Location information exchange among vehicles is required by all kinds of geographic routing protocols. However, the proposed DBLPP does not need vehicles to exchange their true locations but only dummy DODs. In addition, elected next hops respond to forwarders with a group of pseudonyms, so the ID of a next hop is hidden as well. Simulation results show that DBLPP not only protects user?s location privacy but also achieves similar network performances as other protocols. 106 Bibliography [1] Jedrzej Rybicki, Bj?orn Scheuermann, Wolfgang Kiess, Christian Lochert, Pezhman Fallahi, and Martin Mauve. Challenge: peers on wheels - a road to new traffic information systems. In Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking, pages 215?221, 2007. [2] Jakob Eriksson, Hari Balakrishnan, and Samuel Madden. Cabernet: Vehicular content de- livery using WiFi. In Proceedings of the 14th ACM International Conference on Mobile Computing and Networking, pages 199?210, 2008. [3] Aruna Balasubramanian, Ratul Mahajan, Arun Venkataramani, Brian Neil Levine, and John Zahorjan. Interactive wifi connectivity for moving vehicles. SIGCOMM Computer Commu- nication Review, 38(4):427?438, 2008. [4] Seung-Hoon Lee, Uichin Lee, Kang-Won Lee, and M. Gerla. Content distribution in VANETs using network coding: The effect of disk I/O and processing O/H. In Proceedings of the 5th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communi- cations and Networks, pages 117?125, 2008. [5] S. Helal, W. Mann, H. El-Zabadani, J. King, Y. Kaddoura, and E. Jansen. The gator tech smart house: a programmable pervasive space. Computer, 38(3):50?60, 2005. [6] Yang Zhang, Jing Zhao, and Guohong Cao. On scheduling vehicle-roadside data access. In Proceedings of the 4th ACM International Workshop on Vehicular Ad Hoc Networks, pages 9?18, 2007. [7] Yong Ding, Chen Wang, and Li Xiao. A static-node assisted adaptive routing protocol in vehicular networks. In Proceedings of the 4th ACM International Workshop on Vehicular Ad Hoc Networks, pages 59?68, 2007. [8] David B. Johnson and David A. Maltz. Dynamic source routing in ad hoc wireless networks. In Mobile Computing, volume 353. 1996. [9] C.E. Perkins and E.M. Royer. Ad-hoc on-demand distance vector routing. In Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, pages 90?100, 1999. [10] Brad Karp and H. T. Kung. GPSR: Greedy perimeter stateless routing for wireless networks. In Proceedings of the 6th Annual International Conference on Mobile Computing and Net- working, pages 243?254, 2000. 107 [11] Christian Lochert, Martin Mauve, Holger F?ussler, and Hannes Hartenstein. Geographic rout- ing in city scenarios. Mobile Computing and Communications Review, 9(1):69?72, 2005. [12] N. Wisitpongphan, Fan Bai, P. Mudalige, and O.K. Tonguz. On the routing problem in disconnected vehicular ad-hoc networks. In Proceedings of the 26th IEEE International Conference on Computer Communications, pages 2291?2295, 2007. [13] J. Zhao and G. Cao. VADD: Vehicle-assisted data delivery in vehicular ad hoc networks. In Proceedings of the 25th IEEE International Conference on Computer Communications, pages 1?12, 2006. [14] Qing Yang, Alvin Lim, and Prathima Agrawal. Connectivity aware routing in vehicular networks. In Proceedings of the IEEE Wireless Communications and Networking Conference, pages 2218?2223, 2008. [15] Sushant Jain, Kevin Fall, and Rabin Patra. Routing in a delay tolerant network. In Pro- ceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pages 145?158, 2004. [16] Zong Da Chen, H.T. Kung, and Dario Vlah. Ad hoc relay wireless networks over moving vehicles on highways. In Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking and Computing, pages 247?250, 2001. [17] J. LeBrun, Chen-Nee Chuah, D. Ghosal, and M. Zhang. Knowledge-based opportunistic forwarding in vehicular wireless ad hoc networks. In Proceedings of the IEEE 61st Vehicular Technology Conference, pages 2289?2293, 2005. [18] James Bernsen and D. Manivannan. Unicast routing protocols for vehicular ad hoc networks: A critical comparison and classification. Pervasive and Mobile Computing, 5(1):1?18, 2009. [19] Yao H. Ho, Ai H. Ho, and Kien A. Hua. Routing protocols for inter-vehicular networks: A comparative study in high-mobility and large obstacles environments. Computer Communi- cations, 31(12):2767?2780, 2007. [20] Fan Li and Yu Wang. Routing in vehicular ad hoc networks: A survey. IEEE Vehicular Technology Magazine, 2(2):12?22, 2007. [21] Valery Naumov, Rainer Baumann, and Thomas Gross. An evaluation of inter-vehicle ad hoc networks based on realistic vehicular traces. In Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing, pages 108?119, 2006. [22] Zhaomin Mo, Hao Zhu, Kia Makki, and N. Pissinou. MURU: A multi-hop routing proto- col for urban vehicular ad hoc networks. In Proceedings of the 3rd Annual International Conference on Mobile and Ubiquitous Systems, pages 1?8, 2006. [23] V. Naumov and T.R. Gross. Connectivity-aware routing (CAR) in vehicular ad-hoc networks. In Proceedings of the 26th IEEE International Conference on Computer Communications, pages 1919?1927, 2007. 108 [24] Hao Wu, Richard Fujimoto, Randall Guensler, and Michael Hunter. MDDV: A mobility- centric data dissemination algorithm for vehicular networks. In Proceedings of the 1st ACM International Workshop on Vehicular Ad Hoc Networks, pages 47?56, 2004. [25] Paolo Costa, Davide Frey, Matteo Migliavacca, and Luca Mottola. Towards lightweight in- formation dissemination in inter-vehicular networks. In Proceedings of the 3rd International Workshop on Vehicular Ad Hoc Networks, pages 20?29, 2006. [26] Genping Liu, Busung Lee, Boonchong Seet, Chuanheng Foh, and Keokkee Lee. A rout- ing strategy for metropolis vehicular communications. In Proceedings of The International Conference on Information, pages 533?542, 2004. [27] Shabbir Ahmed and Salil S. Kanere. SKVR: Scalable knowledge-based routing architecture for public transport networks. In Proceedings of the 3rd International Workshop on Vehicular Ad Hoc Networks, pages 92?93, 2006. [28] Ilias Leontiadis and Cecilia Mascolo. GeOpps: Geographical opportunistic routing for vehic- ular networks. In Proceedings of the IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks, pages 1?6, 2007. [29] Antonios Skordylis and Niki Trigoni. Delay-bounded routing in vehicular ad-hoc networks. In Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing, pages 341?350, 2008. [30] J. Burgess, B. Gallagher, D. Jensen, and B. N. Levine. MaxProp: Routing for vehicle-based disruption-tolerant networks. In Proceedings of the 25th IEEE International Conference on Computer Communications, pages 1?11, 2006. [31] M. Grossglauser and D.N.C. Tse. Mobility increases the capacity of ad hoc wireless net- works. IEEE/ACM Transactions on Networking, 10(4):477?486, 2002. [32] P. Santi and D.M. Blough. The critical transmitting range for connectivity in sparse wireless ad hoc networks. IEEE Transactions on Mobile Computing, 2(1):25?39, 2003. [33] O. Dousse, P. Thiran, and M. Hasler. Connectivity in ad-hoc and hybrid networks. In Pro- ceedings of the 21st IEEE International Conference on Computer Communications, pages 1079?1088, 2002. [34] M. Abuelela, S. Olariu, and I. Stojmenovic. OPERA: Opportunistic packet relaying in discon- nected vehicular ad hoc networks. In Proceedings of the 5th IEEE International Conference on Mobile Ad Hoc and Sensor Systems, pages 285?294, 2008. [35] Bo Gu and Xiaoyan Hong. Critical phase of connectivity in wireless network expansion. In Proceedings of the IEEE Global Telecommunications Conference, pages 1?5, 2010. [36] I. Seskar, S.V. Maric, J. Holtzman, and J. Wasserman. Rate of location area updates in cellular systems. In Proceedings of the 42nd IEEE Vehicular Technology Conference, pages 694?697, 1992. 109 [37] I. Stepanov, J. Hahner, C. Becker, Jing Tian, and K. Rothermel. A meta-model and frame- work for user mobility in mobile networks. In Proceedings of the 11th IEEE International Conference on Networks, pages 231?238, 2003. [38] Martin Treiber, Ansgar Hennecke, and Dirk Helbing. Congested traffic states in empirical observations and microscopic simulations. Physical Review E, 62(2):1805?1824, 2000. [39] M. Fiore, J. Harri, F. Filali, and C. Bonnet. Vehicular mobility simulation for VANETs. In Proceedings of the 40th Annual Simulation Symposium, pages 301?309, 2007. [40] Marco Fiore and J?er?ome H?arri. The networking shape of vehicular mobility. In Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing, pages 261?272, 2008. [41] J. H?arri, F. Filali, C. Bonnet, and Marco Fiore. VanetMobiSim: Generating realistic mobility patterns for vanets. In Proceedings of the 3rd International Workshop on Vehicular Ad Hoc Networks, pages 96?97, 2006. [42] Qing Yang, Alvin Lim, Shuang Li, Jian Fang, and Prathima Agrawal. ACAR: Adaptive connectivity aware routing for vehicular ad hoc networks in city scenarios. Mobile Networks and Applications, 15(1):36?60, 2010. [43] Ziwei Ren, Wenfan Li, and Qing Yang. Location verification for vanets routing. In Proceed- ings of the IEEE International Conference on Wireless and Mobile Computing, Networking and Communications, pages 141?146, 2009. [44] Ziwei Ren, Wenfan Li, Qing Yang, Shaoen Wu, and Lei Chen. Location security in geo- graphic ad hoc routing for vanets. In Proceedings of the International Conference on Ultra Modern Telecommunications Workshops, pages 1?6, 2009. [45] Qing Yang, Alvin Lim, and Prathima Agrawal. GPSFR: GPS-free routing protocol for ve- hicular networks with directional antennas. International Journal of Wireless & Mobile Net- works, 1(2):64?78, 2009. [46] A.R. Beresford and F. Stajano. Location privacy in pervasive computing. IEEE Pervasive Computing, 2(1):46?55, 2003. [47] K. Sampigethaya, Mingyan Li, Leping Huang, and R. Poovendran. AMOEBA: Robust lo- cation privacy scheme for VANET. IEEE Journal on Selected Areas in Communications, 25(8):1569?1589, 2007. [48] Florian D?otzer. Privacy issues in vehicular ad hoc networks. In Proceedings of the Workshop on Privacy Enhancing Technologies, pages 197?209, 2005. [49] Rongxing Lu, Xiaodong Lin, Haojin Zhu, Pin-Han Ho, and Xuemin Shen. ECPP: Efficient conditional privacy preservation protocol for secure vehicular communications. In Proceed- ings of the 27th IEEE Conference on Computer Communications, pages 1229?1237, 2008. 110 [50] Krishna Sampigethaya, Leping Huang, Mingyan Li, Radha Poovendran, Kanta Matsuura, and Kaoru Sezaki. CARAVAN: Providing location privacy for VANET. In Proceedings of the 3rd Workshop on Embedded Security in Cars (ESCAR), 2005. [51] Alastair R. Beresford and Frank Stajano. Mix zones: User privacy in location-aware services. In Proceedings of the 2nd IEEE Annual Conference on Pervasive Computing and Communi- cations Workshops, pages 127?132, 2004. [52] Elmar Schoch, Frank Kargl, Tim Leinmuller, Stefan Schlott, and Panagiotis Papadimitratos. Impact of Pseudonym Changes on Geographic Routing in VANETs. In Proceedings of the 3rd European Workshop on Security and Privacy in Ad hoc and Sensor Networks, pages 43?57, 2006. [53] Latanya Sweeney. k-Anonymity: A model for protecting privacy. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 10(5):557?570, 2002. [54] H. Kido, Y. Yanagisawa, and T. Satoh. Protection of location privacy using dummies for location-based services. In Proceedings of the 21st International Conference on Data Engi- neering Workshops, pages 1248?1248, 2005. [55] Hua Lu, Christian Sndergaard Jensen, and Man Lung Yiu. PAD: Privacy-area aware, dummy- based location privacy in mobile services. In Proceedings of the 7th International ACM Workshop on Data Engineering for Wireless and Mobile Access, pages 16?23, 2008. [56] Yunpeng Zang, Lothar Stibor, Georgios Orfanos, Shumin Guo, and Hans-Juergen Reumer- man. An error model for inter-vehicle communications in highway scenarios at 5.9GHz. In Proceedings of the 2nd ACM International Workshop on Performance evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks, pages 49?56, 2005. [57] Ivan Stojmenovic, Mark Russell, and Bosko Vukojevic. Depth first search and location based localized routing and qos routing in wireless networks. In Proceedings of the 2000 Interna- tional Conference on Parallel Processing, pages 173?185, 2000. [58] Dongjin Son, A. Helmy, and B. Krishnamachari. The effect of mobility-induced location errors on geographic routing in ad hoc networks: analysis and improvement using mobility prediction. 3(3):233?245, 2004. [59] P. Gupta and P.R. Kumar. The capacity of wireless networks. IEEE Transactions on Infor- mation Theory, 46(2):388?404, Mar 2000. [60] Douglas S. J. De Couto, Daniel Aguayo, John Bicket, and Robert Morris. A high-throughput path metric for multi-hop wireless routing. Wireless Networks, 11(4):419?434, 2005. [61] Holger Fler, Jrg Widmer, Michael Ksemann, Martin Mauve, and Hannes Hartenstein. Contention-based forwarding for mobile ad hoc networks. Ad Hoc Networks, 1(4):351?369, 2003. 111 [62] Qing Yang, Alvin Lim, Shuang Li, Jian Fang, and Prathima Agrawal. ACAR: Adaptive connectivity aware routing protocol for vehicular ad hoc networks. In Proceedings of 17th International Conference on Computer Communications and Networks, pages 1?6, 2008. [63] K. Mehta, Donggang Liu, and M. Wright. Location privacy in sensor networks against a global eavesdropper. In Proceedings of the IEEE International Conference on Network Pro- tocols, pages 314?323, 2007. 112