POLITECNICO DI TORINO III Facoltà di Ingegneria dell’Informazione Corso di Laurea Magistrale in Ingegneria Telematica Tesi di Laurea Magistrale Data downloading in Vehicular networks Relatori: prof. Claudio Casetti Candidato: Hong-Nam Hoang Anno accademico 2011-2012 Summary Vehicular networks is invested and developed to provide not only the convenience to drivers and passengers, but also the benefit to automotive companies. Although vehicular networks is the class of wireless network, its special characteristics chal- lenge the research community to bring the high performance on this kind of network. The Signalling and Information Exchange Protocol is developed to support the ef- ficiency of data downloading over vehicular networks with centralized control and management at CC, the Central Controller.
In this thesis, we continue to improve this protocol by predicting the vehicle mobility and estimating the amount of data transferred to vehicles under the packet sharing model. The implementation is done in the environment of network simulator ns2, which helps us to reduce costs and save time if there is any errors during the process of implementation. The improvements of protocol are evaluated with the variation of vehicle speed on different maps and vehicle density. iii Acknowledgements This dissertation would not have been possible without the guidance and the help of several individuals who in one way or another contributed and extended their valuable assistance in the preparation and completion of this study.
I would like to express my deepest gratitude to my advisor, Prof. Carla-Fabiana Chiasserini, for her excellent guidance, patience, and providing me with an excellent atmosphere for doing research. I am most grateful to Carlo Borgiattino for providing me good advice, support and friendship. Without his help, I could not continue my work with the bad conditional hard driver.
I would like to acknowledge the financial, academic and technical support of the Erasmus EuroAsia project, University Politecnico di Torino, and especially Dr. An- drea Carena. Without you, I could not have opportunity to study at one of the best university in Italy. My vision and knowledge are broaden during the beautiful time staying here.
I would also like to thank my family for encouraging me with their best wishes and giving me the strength to plod on despite my constitution wanting to give up and throw in the towel. Finally, I would like to thank my lovely wife, Mai Dung. She was always there cheering me up and stood by me through the good times and bad. Thank you so much.
iv Contents Summary iii Acknowledgements iv 1 Introduction 3 2 Vehicular networks 5 2.1 Standardization and Services. 10 3 Signalling and Information Exchange Protocol 13 3.1 Processing one request at OBU .2 Processing one request at CC .3 Processing one request at AP .4 Signalling packet format .6 Vehicle Data ACK. 26 4 Algorithms for Improving the Information Exchange Efficiency 27 4.1 Cell, direction and road state at an AP .2 Algorithm of collecting grid map information at CC .3 Algorithm of vehicle mobility prediction .4 Maximum throughput at vehicular application .5 The effective throughput and duration of a road state .6 The pre-caching time and estimation of downloading time .7 Algorithm of estimating amount of data cached in AP .8 Algorithm of AP selection .9 Algorithm of chunk transmission at AP and CC. 42 5 Implementation and Simulation Set-up 45 5.1 Network simulator - ns2 .4 Quick guide of running simulation .1 Test 1: One AP and one vehicle .2 Test 2: Two APs and four vehicles .3 Test 3: Five APs with different number of vehicles.
62 7 Conclusion 67 Bibliography 71 vi List of Tables 3.1 Packet types in communication among CC, AP and OBU.1 Theoretical throughput of the vehicular application using the IEEE 802.1 Simulation result of Test 1 with constant velocity .2 Simulation result of Test 1 with random velocity (uniform distribution) 58 6.3 Simulation result of test 2.4 Simulation result of test 3 with 20 vehicles.5 Simulation result of test 3 with 40 vehicles.6 Simulation result of test 3 with 80 vehicles.1 Problems and their countermeasures in estimating number of chunks. 68 vii List of Figures 2.1 The vehicular network architecture .2 WAVE communication stack (referred to Figure 2 in [9]) .3 WAVE channel access .4 Classification of application from perspective of network design (re- ferred from Figure 1.1 The protocol packet sequence .2 Operations of processing one request at OBU .3 Operations of processing one request at CC.4 Operations of processing one request at AP.1 An example of grid map of an AP with different data rates for each cells .2 An example of representation of cell, e. e2, in a grid map of an AP (based on the mobility of vehicles in Figure 4.3 The last four passed cells in vehicle’s motion.4 The pattern of three (a) and four (b) passed cells.5 Example of mobility prediction .6 Grid map table for example in Figure 4.7 Vehicle runs through different data rates when downloading data at an AP .2 Data flows of sending and receiving messages through networking layers in ns2 .3 Modules implementing signalling and information exchange protocol .4 Construction of CC node in the ns2 simulation .1 Testing scenario 1: Grid of cells, data rate and vehicle mobility .2 Test 1: Estimation and progress of downloading chunks with speed 8 m/s.3 Test 2: Positions of APs in the map 1000 x 1000 (m2 ).4 Cell data rates assigned for AP0 and AP1.5 Test 2: Trace of vehicle movement and downloading cells for each vehicles.6 Test 2: Throughput measured for each vehicles at AP0 and AP1 over time.7 Test 3: Positions of APs and CC in the map 2000 x 2000 (m2 ).8 Test 3: The average throughput for each vehicles at APs with three configurations: 20, 40 and 80 vehicles.9 Test 3: The average data normalized with the average throughput at each APs in the configuration of 20 vehicles.10 Test 3: The average data normalized with the average throughput at each APs in the configuration of 40 vehicles.11 Test 3: The average data normalized with the average throughput at each APs in the configuration of 80 vehicles. 66 ix List of Abbreviations AP Access Point ACK Acknowledgement message CC Central Controller CI Confidence Interval DES Discrete Event Simulation DoS Denial of Service attack DSRC Dedicated Short-Range Communication FSM Finite State Machine GOC Group of Chunks LLC Logical Link Control MAC Media Access Control OBU On-board Unit OSI Open Systems Interconnection RSU Roadside Unit STDEV Standard Deviation VEH Vehicle WAVE Wireless Access in Vehicular Environments 1 Chapter 1 Introduction Vehicular networks are the class of wireless networks, emerging wireless technolo- gies and automotive industry, to bring diverse assistant services orienting drivers and passengers.
Coming from problems of traffic congestion, they are becoming increas- ingly popular, supported by many researchers and industrial companies. We could list here applications that are attracting many interests in: safety and efficient nav- igation, vehicle monitoring, social networking, entertainment, emergency, etc. Since Internet is the very successful wired network, people always want to access the huge information and knowledge in it, not only by traditional cables, but also via wire- less networks. The requirement of content downloading rises in vehicular networks as the essential demand to satisfy that desire.
We need a protocol to work at high performance and stability under the particular characteristics of vehicular networks: high but predictable mobility, low connectivity, and highly dynamic topology. Our work is to continue developing The Signalling and Information Exchange Pro- tocol, first introduced last year and focused on content downloading with latency- tolerant content type in vehicular networks. This protocol assumes that each nodes could support at least two radio interfaces in order to achieve high performance. Each interfaces work in different channels to avoid the interfering.
Since this as- sumption could not easily achieve under the current technologies and large-network deployment, the protocol is implemented and tested under ns2 - the pervasive net- work simulator tool. When running on road and receiving data from Access Points, vehicles do not gain the same throughput over time. With this idea in mind, we focus on solutions of downloading data to achieve high performance and efficiency. The content is organized as following.
An overview of the topic and previous works are presented in Chapter 2. The behaviour and packet formats in Signalling and Information Exchange Protocol is shown in Chapter 3. In Chapter 4, this protocol is described in details of implementation, focusing on algorithms used in it. Although 3 1 – Introduction we implemented it in ns2, we try to separate the algorithms and ns2-related parts.
The introduction of ns2 and components of our simulation program is introduced in Chapter 5. All the experiments and results are put in Chapter 6. The last chapter concludes our work, discusses some weak points and future works. 4 Chapter 2 Vehicular networks In this part, overview of vehicular networks is presented with the architectures, stan- dardization and applications.
The research works, related to content downloading, are also described.1 Standardization and Services Architecture In vehicular networks, there are two main types of unit: On Board Unit (OBU) and Road Side Unit (RSU). An OBU is a device attaching in vehicle to provide the capabilities of communication, while a RSU is a stationary along the road. Based on our need, a RSU can connect to an infrastructure network, which in turn could access to the Internet. An OBU can communicate with both RSU (V2I) or another OBU (V2V) in the network.
V2I communication is usually a short-time but high-data-rate connection while V2V communication is a low-cost communication and suitable for safety application.1 illustrates the architecture of vehicular networks. Standardization In 1999, United States Federal Communications Commission granted 75 MHz of dedicated short-range communication (DSRC) spectrum at 5.925 GHz) to be used for V2I and V2V communications. Starting from 2002, DSRC standards have been developed and publicized. These standards addresses different layers in OSI model: Physical layer, Data link layer and Appli- cation layer.
Today, DSRC is emerged in IEEE 802.x with the new name: Wireless Access in Vehicular Environments (WAVE). The IEEE 1609 family defines the architecture, communications model, management structure, se- curity mechanisms and physical access for high speed (up to 27 Mb/s) short range (up to 1000m) low latency wireless communications in the vehicular environment.2 shows WAVE communication stack with the standards covering each 5 2 – Vehicular networks Internet Access network RSU RSU V2V OBU OBU Figure 2. The vehicular network architecture set of layers. WAVE supports two stacks, the traditional Internet Protocol version six (IPv6) and WAVE Short-Message Protocol (WSMP), to serve not only normal data exchanges (e.g UDP or TCP/IP transactions) but also the quick and reliable exchange of short messages in highly dynamic conditions, like alarm messages.
Resource Manager (IEEE 1609.1) UDP/TCP WSMP IPv6 Security LLC services WME IEEE 1609.2 Multichannel operation MLME extension IEEE 1609.3 WAVE lower MAC MLME IEEE 1609.4 WAVE PHY PLME IEEE 802.11p Data plane Management plane Figure 2. WAVE communication stack (referred to Figure 2 in [9]) 6 2.1 – Standardization and Services WAVE PHY and MAC layers are based on 802.11a because it is the stable stan- dard, validated by experts in wireless network community. However, WAVE requires a new standard to meet particular characteristics in vehicular networks, such as long range of operation (about 1000 m), high speed of vehicles, extreme multipath en- vironments. It still uses orthogonal frequency division multiplexing (OFDM) as in 802.11a but all time parameters are doubled to against the problem of delay spread (multipath) and Doppler effect.
WAVE PHY supports seven 10 MHz-wide channels in the 5.9 GHz frequency band, Figure 2.3, in which six channels are for non-safety data (Serivce Channels - SCHs), and one channel is for high priority messages (Con- trol Channel - CCH). Frequency (GHz) No Tx allowed 5.925 Tx allowed SCH SCH 5.855 CCH interval 50 SCH interval 100 Time (ms) Figure 2.