ETH Library Vehicular ad hoc networks (VANET) (engineering and simulation of mobile ad hoc routing protocols for VANET on highways and in cities) Master Thesis Author(s): Baumann, Rainer Publication date: 2004 Permanent link: https://doi.org/10.3929/ethz-a-004778905 Rights / license: In Copyright - Non-Commercial Use Permitted This page was generated automatically upon download from the ETH Zurich Research Collection. For more information, please consult the Terms of use. Vehicular Ad hoc Networks (VANET) (Engineering and simulation of mobile ad hoc routing protocols for VANET on highways and in cities) Master’s Thesis in Computer Science Rainer Baumann, ETH Zurich 2004 [email protected], http://hypert.net/education Contents 1. Abstract ..............................................................................................6 1.1. Structure of this thesis...................................................................6 2. Introduction.........................................................................................7 3. Wireless technology ..............................................................................8 3.1. The IEEE 802 family.......................................................................8 3.2. The IEEE 802.11............................................................................9 3.3. The Mac Layer..............................................................................10 3.4. The PHY Layer..............................................................................16 3.5. Antennas.....................................................................................18 3.6. Propagation, reflection, and transmission losses through common building materials (2.4 GHz versus 5 GHz)..........................18 3.7. Which to take, 802.11a or 802.11g.................................................19 3.8. Characteristics of available hardware ..............................................20 3.9. IEEE 802.11 Security ....................................................................21 4. Ad hoc On demand Distance Vector routing protocol (AODV).....................22 4.1. Mobile ad hoc routing protocols......................................................22 4.2. Introduction.................................................................................22 4.3. Unicast routing.............................................................................23 4.4. Multicast routing...........................................................................25 4.5. Security.......................................................................................26 4.6. Implementations ..........................................................................26 5. Network Simulator – NS-2 ....................................................................27 5.1. About NS-2..................................................................................27 5.2. NS-2, implementing languages.......................................................27 5.3. Architecture of ns-2......................................................................28 5.4. Usage of ns-2...............................................................................31 5.5. TCL simulation scripts ...................................................................32 5.6. Wireless simulations based on 802.11.............................................33 5.7. Trace files....................................................................................38 5.8. Limitations of ns-2........................................................................42 5.9. Extensions to ns-2........................................................................42 5.10. Utilities........................................................................................43 5.11. Used machine for simulations.........................................................44 6. Car traffic simulator.............................................................................45 6.1. Multi-agent traffic simulator...........................................................46 7. Connectivity in vehicular ad hoc networks...............................................48 7.1. Simulation setup ..........................................................................48 7.2. Metrics........................................................................................51 7.3. Results........................................................................................51 7.4. Conclusions..................................................................................53 7.5. Summary ....................................................................................54 8. Secure ring broadcasting ......................................................................55 8.1. Broadcasting in ad hoc networks ....................................................55 8.2. Secure Ring Broadcasting (SRB).....................................................56 8.3. Metrics........................................................................................61 8.4. Simulation setup ..........................................................................61 8.5. Results........................................................................................62 8.6. Conclusions..................................................................................65 8.7. Verification under random interference............................................66 8.8. Summary ....................................................................................67 Rainer Baumann, ETH Zurich 2004 Master’s Thesis Vehicular Ad hoc Networks (VANET) [email protected] 3/128 9. Directed route node selection................................................................68 9.1. Directed Route Node Selection (DRNS)............................................69 9.2. Metrics........................................................................................69 9.3. Simulation setup ..........................................................................69 9.4. Results........................................................................................70 9.5. Conclusions..................................................................................71 9.6. Summary ....................................................................................72 9.7. Comparison and combination of SRB and DRNS................................72 10. Hybrid internet access..........................................................................76 10.1. Hybrid ad hoc networks.................................................................76 10.2. The Hybrid Internet Access extension (HIA).....................................76 10.3. Simulation setup ..........................................................................82 10.4. Metrics........................................................................................84 10.5. Results........................................................................................84 10.6. Conclusions..................................................................................86 10.7. Summary ....................................................................................87 11. ARP, a relict ?.....................................................................................88 11.1. The address resolution protocol (ARP).............................................88 11.2. Why ARP ?...................................................................................88 11.3. Simulation setup ..........................................................................89 11.4. Metrics........................................................................................89 11.5. Results........................................................................................89 11.6. Conclusion...................................................................................91 11.7. Summary ....................................................................................91 Appendix A - Master's thesis description .......................................................92 A.1. Introduction.................................................................................92 A.2. Tasks..........................................................................................92 A.3. Remarks......................................................................................93 Appendix B - List of figures .........................................................................94 Appendix C - List of tables ..........................................................................95 Appendix D - List of equations.....................................................................97 Appendix E - References.............................................................................98 E.1. Books..........................................................................................98 E.2. Papers.........................................................................................98 E.3. Company publications...................................................................99 E.4. Standards and drafts...................................................................100 E.5. Lecture Notes.............................................................................100 E.6. Talks.........................................................................................100 E.7. Websites ...................................................................................100 Appendix F - Source codes........................................................................102 F.1. Used TCL script ..........................................................................102 Appendix G - Detailed results....................................................................106 G.1. Connectivity in vehicle ad hoc networks (Chapter 7) .......................106 G.2. Secure ring broadcasting (Chapter 8)............................................109 G.3. SRB verification under random interference ...................................115 G.4. Directed route node selection (Chapter 9)......................................118 G.5. SRB-DRNS combination...............................................................122 G.6. Hybrid Internet Access (Chapter 10).............................................125 G.7. ARP a relict? (Chapter 11) ...........................................................127 Rainer Baumann, ETH Zurich 2004 Master’s Thesis Vehicular Ad hoc Networks (VANET) [email protected] 4/128 Preface This paper originates from my master’s thesis at the Swiss Federal Institute of Technology Zurich ETH (www.ethz.ch), Department of Computer Science (www.inf.ethz.ch), Computer Systems Institute (www.cs.inf.ethz.ch), Laboratory for Software Technology (www.lst.inf.ethz.ch) Prof. Dr. Thomas Gross. I would like to thank very much my adviser Valery Naumov for his great support and my professor Thomas Gross for his input and giving me the opportunity to write this thesis. I would also like to say thank you to the group of Prof. Kai Nagel for generating the traffic files for my simulations and to my fellow students Patrick Leuthold, Sibylle Aregger, Arianne Ibig and Antonia Schmidig for their support and interesting discussions. © Rainer Baumann, [email protected], ETH Zurich 2004 Rainer Baumann, ETH Zurich 2004 Master’s Thesis Vehicular Ad hoc Networks (VANET) [email protected] 5/128 1. Abstract In this thesis the performance and usability of wireless Vehicular Ad hoc Networks (VANET) are studied. For investigation we use the network simulator ns-2 with a car traffic movement file of the larger region of the canton of Zurich, simulating the current WLAN hardware with the Ad hoc On Demand Distance Vector routing protocol (AODV). The connectivity tests have shown that it is a realistic option to use ad hoc networks for vehicular communication. But our simulations also have drawn out that several protocol improvements and extensions would lead to much better performance, especially for broadcasting. In this thesis we propose two new broadcasting mechanisms that try to minimize the number of broadcasting messages and to get more stable routes: the Secure Ring Broadcasting (SRB) and the Directed Route Node Selection (DRNS). SRB establishes routes over intermediate nodes that have a preferred distance between each other. This is beneficial for fast moving nodes with high density as in city scenarios during rush hours. DRNS has been developed for highway scenarios. It takes in account that nodes driving in opposite directions are a bad choice to be intermediate nodes in a route. Since the Internet is becoming more and more popular, we also have a look at the possibility of offering access to it. For this purpose, a multi hop hybrid internet access protocol based on AODV has been developed. Finally a study on the influences of the Address Resolution Protocol (ARP) on the performance of ad hoc networks is presented. 1.1. Structure of this thesis This thesis is mainly divided into three parts. In the first chapters (2-6) an overview over the used technologies and standards is given. In the following chapters (7-11) some protocol improvements and extensions are discussed. Finally, in appendix some additional information can be found. In chapter three the current wireless technologies are presented, continued by an introduction to AODV and the network simulator ns-2. From chapter seven on, we have a look at some protocol improvements and extensions. First of all an analysis about the connectivity of vehicular ad hoc networks was done. Based on this a new broadcasting system called Secure Ring Broadcasting (SRB – chapter 8) was developed. We also propose an improvement for fast moving nodes (Directed Route Node Selection DRNS – chapter 9). A multi hop ad hoc on demand internet access protocol based on AODV is presented in chapter 10. Some thoughts and tests concerning ARP can be found in chapter 11. Rainer Baumann, ETH Zurich 2004 Master’s Thesis Vehicular Ad hoc Networks (VANET) [email protected] 6/128 2. Introduction Driving means changing constantly location. This means a constant demand for information on the current location and specifically for data on the surrounding traffic, routes and much more. This information can be grouped together in several categories. A very important category is driver assistance and car safety. This includes many different things mostly based on sensor data from other cars. One could think of brake warning sent from preceding car, tailgate and collision warning, information about road condition and maintenance, detailed regional weather forecast, premonition of traffic jams, caution to an accident behind the next bend, detailed information about an accident for the rescue team and many other things. One could also think of local updates of the cars navigation systems or an assistant that helps to follow a friend’s car. Another category is infotainment for passengers. For example internet access, chatting and interactive games between cars close to each other. The kids will love it. Next category is local information as next free parking space (perhaps with a reservation system), detailed information about fuel prices and services offered by the next service station or just tourist information about sights. A possible other category is car maintenance. For example online help from your car mechanic when your car breaks down or just simply service information. So far no inter-vehicle communication system for data exchange between vehicles and between roadside and vehicles has been put into operation. But there are several different research projects going on [39] [40]. Rainer Baumann, ETH Zurich 2004 Master’s Thesis Vehicular Ad hoc Networks (VANET) [email protected] 7/128 3. Wireless technology Over the last years, the technology for wireless communications has made tremendous advantages. It allows very high mobility, efficient working and is almost extreme economical. Today we divide wireless technologies into two main groups. On one side we have large area technologies as GSM, GPRS or UMTS, which have moderate bandwidth. On the other side we have the local area technologies as WLAN (Wireless Local Area Network) with much higher bandwidth. In this thesis we will focus on the second one, the WLAN. There exist two different standards for Wireless LAN: HIPERLAN from European Telecommunications Standards Institute (ETSI) and 802.11 from Institute of Electrical and Electronics Engineers (IEEE). Nowadays the 802.11 standard totally dominates the market and the implementing hardware is well engineered. So it is adjacency to concentrate on this one. 3.1. The IEEE 802 family The IEEE 802.11 WLAN protocols [30] are part of the 802 family that standardizes Local Area Networks (LAN) and metropolitan area networks (MAN). The 802 family has a common Logical Link Control layer (LLC), which is standardized in 802.2. On top of the LLC lies the network layer usually the Internet Protocol (IP) with its routing protocols, e.g. AODV or DSR for mobile ad hoc networks (Figure 3-1). IISSOO//OOSSII NNeettwwoorrkk LLaayyeerrss Application Presentation IP Routing Protocolls as Session AODV, DSR, ... Transport LLC 802.2 Network MAC Data Link PHY Physical Figure 3-1: ISO/OSI layer model Below the LLC, the Media Access Control layer (MAC) and the corresponding physical layer (PHY) are packed together in the same standard subgroup. Many such standard subgroups exist as for Ethernet and wireless LAN that is specified in 802.11 (Figure 3-2). Rainer Baumann, ETH Zurich 2004 Master’s Thesis Vehicular Ad hoc Networks (VANET) [email protected] 8/128 802.2 Logical Link Control (LLC) 802.3 802.4 802.5 ... 802.11 ... MAC MAC MAC MAC 802.3 802.4 802.5 802.11 PHY PHY PHY ... PHY ... CSMA/CD Token Bus Token Ring WLAN Figure 3-2: 802 LLC, MAC and PHY 3.2. The IEEE 802.11 The IEEE 802.11 standard places the specifications for both the physical layer and for the medium access control layer. Many extensions have already been added to 802.11 either enhancing the MAC or PHY Layer. The MAC extensions are mainly thought to improve security or quality of service (QoS). The physical layer extensions mostly redefine the way in which the physical layer works. In reality, they are rather substitutions than extensions. A structured overview of 802.11 is given in the figure below and a list of the present extensions can be found in section 3.2.1. 802.11 Media Access Control (MAC) SME / MLME Segmentation Reassembly MAC Control Packet Transfer Procedure Module Co-ordination function (PCF, DCF) (Sync, Power Save, SIFS, PIFS, DIFS, EIFS Beacon) CSMA/CA 802.11i – Security Engine 802.11e – QoS Engine 802.11 Physical Layer (PHY) PLME 802.11 lega cy – 2 Mbps / 2.4 GHz 802.11a – 54 Mbps / 5 GHz 802.11b – 11 Mbps / 2.4 GHz 802.11g – 11 Mbps / 2.4 GHz Figure 3-3: 802.11 MAC and PHY layer Rainer Baumann, ETH Zurich 2004 Master’s Thesis Vehicular Ad hoc Networks (VANET) [email protected] 9/128