Repositorio Institucional de Documentos

2012 91 Manuel Fogué Cortés Design and Evaluation of a Traffic Safety System based on Vehicula r Networks for the Next Generation of Intelligent Vehicles Departamento Director/es Informática e Ingeniería de Sistemas Martínez Domínguez, Francisco José Garrido Picazo, Piedad Manuel Fogué Cortés DESIGN AND EVALUATION OF A TRAFFIC SAFETY SYSTEM BASED ON VEHICULAR NETWORKS FOR THE NEXT GENERATION OF INTELLIGENT VEHICLES Director/es Informática e Ingeniería de Sistemas Martínez Domínguez, Francisco José Garrido Picazo, Piedad Tesis Doctoral Autor 2012 Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA UNIVERSITY OF ZARAGOZA COMPUTER SCIENCE AND SYSTEM ENGINEERING DEPARTMENT Design and Evaluation of a Traffic Safety System based on Vehicular Networks for the Next Generation of Intelligent Vehicles Thesis submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Computer Science Manuel Fogu´e Cort´es Ph.D. Advisors: Dr. Francisco J. Mart´ınez Dom´ınguez Dr. Piedad Garrido Picazo Teruel, September 2012 To my family and my girlfriend, for their patience and support. Acknowledgments I have traveled a long way until I arrived where I am today. I have been in different places, at different times, with different people. And finally, I came back to the place where everything started. Even if it could be hard to believe, Teruel still exists and offers lots of things, more than it could seem at first sight. The situation was not easy when I finished my Computer Science Degree. The economy had just started to fall into recession, and finding a job would not be as simple as I initially thought. So, why not trying in the place where my academic life started? I decided to talk with Dr. Francisco J. Mart´ınez about the possibility to work at the Escuela Universitaria Polit´ecnica de Teruel at that moment. Then, Dr. Mart´ınez and his wife, Dr. Piedad Garrido, accepted to be my advisors as a Ph.D. student. There were lots of doubts, and we were not sure about almost anything, but there was potential. I knew we could do something good, and nearly three years after that, I am finishing my Thesis and I am very proud of all the process followed. My advisors have helped so much during this time, it is difficult to think I could have reached so far without their invaluable support. I cannot forget the wonderful people from the Grupo de Redes de Computadores (GRC) of the Universitat Polit`ecnica de Val`encia. They have been advisors, critics, friends, and an example of what you can obtain with hard work. Thanks to Dr. Juan Carlos Cano, Dr. Carlos Tavares Calafate, and Dr. Pietro Manzoni for their advice, guiding me through all this process, and giving me some ideas that were crucial for my work. I know that many of the achievements during these years would not have happened without them, and I hope we achieve many more in the future. I am also very thankful to all my partners at the “zulo”, where all the magic was produced. I remember the time I spent there alone and how difficult it is to get focused sometimes, so I have to thank Alberto, Ricardo, Javi, ´ Angel, Jorge, Vicente, Julio, Jes´us Fuentes, Jes´us Ib´a˜nez, Manuel (our DJ), Nava, I really hope I do not miss anyone! You were one of the most important parts of the creation process, and we have spent too much time together; it is difficult to forget all those days there. In addition, the hard work allowed us creating the Intelligent Networks and Information Technologies (INIT) research group with Dr. Francisco J. Mart´ınez, and it has become now like a second family for most of us. The Gobierno de Arag´on, under grant “subvenciones destinadas a la formaci´on y contrataci´on de personal investigador”’, and the Fundaci´on Antonio Gargallo partially supported this work during the first months, when I was just beginning v my journey. Thanks to their support, I have been able to spend my time working on my Thesis without worrying about economical issues, so a really big part of this work belongs to them. I need to thank the EduQTech group too, since they allowed me obtaining the grant. Our contact at Applus+ IDIADA, Jos´e Manuel Barrios, also deserves to be here. The evaluation of our prototypes would not have been possible without their facilities, and many of the contributions of this thesis would be useless without it. I am indebted to thank Dr. Carla-Fabiana Chiasserini for their support during my stay in the Politecnico di Torino. And I don’t forget about the rest of the guys that made my stay almost like home: Massimo, Carlo, Stefano, Marco... Thanks for adopting a Spanish boy just like if he was born in the Piemonte. And of course, I cannot forget all my family that supported me and gave me the opportunity to continue my studies: my father Manuel, my mother Ma ¯Consuelo, and my brother Rub´en. Sorry for being so many hours working at the university!! I also thank my wonderful girlfriend Laura, who was always there when I was having problems and I needed a shoulder to rest my head. My friends from Teruel and Castell´on, thank you for not forgetting me even when I was almost missing during all these months, you are amazing. Finally, I am really grateful to all the people that helped me in a way or another during these years. I will not be ever able to compensate all you did. Manuel Fogu´e Cort´es Teruel, September 2012 vi CONTENTS 5.5.7 Overall result analysis . . . . . . . . . . . . . . . . . . . . . 101 5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 6 Enhancing Warning Message Dissemination in VANETs through roadmap profiling 105 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 6.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 6.3 City profile classification . . . . . . . . . . . . . . . . . . . . . . . . 107 6.3.1 Importance of the roadmap in VANET simulation . . . . . 107 6.3.2 Roadmap layout clustering . . . . . . . . . . . . . . . . . . 110 6.4 The Profile-driven Adaptive Warning Dissemination System (PAWDS)113 6.5 Simulation Environment . . . . . . . . . . . . . . . . . . . . . . . . 115 6.6 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 6.6.1 Evaluating the Impact of the Roadmap and Vehicle Density 118 6.6.2 Performance Testing . . . . . . . . . . . . . . . . . . . . . . 122 6.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 7 Improving Automatic Accident Detection and Assistance through Vehicular Networks 129 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 7.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 7.3 Related Projects . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 7.4 e-NOTIFY System: Architecture Overview . . . . . . . . . . . . . 133 7.5 On-Board Unit (OBU) Design . . . . . . . . . . . . . . . . . . . . . 134 7.5.1 OBU Internal Structure . . . . . . . . . . . . . . . . . . . . 135 7.5.2 Accident Detection Algorithm . . . . . . . . . . . . . . . . . 136 7.5.3 OBU Design under the OSGi Environment . . . . . . . . . 137 7.5.4 Warning message structure . . . . . . . . . . . . . . . . . . 138 7.6 Control Unit (CU) Design . . . . . . . . . . . . . . . . . . . . . . . 140 7.6.1 CU Internal Structure . . . . . . . . . . . . . . . . . . . . . 140 7.6.2 Accident Severity Estimation . . . . . . . . . . . . . . . . . 142 7.7 Prototype Implementation and Validation . . . . . . . . . . . . . . 143 7.7.1 OBU Prototype . . . . . . . . . . . . . . . . . . . . . . . . . 143 7.7.2 CU Prototype . . . . . . . . . . . . . . . . . . . . . . . . . . 146 7.7.3 Prototype Validation . . . . . . . . . . . . . . . . . . . . . . 146 7.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 8 Improving Accident severity estimation through Knowledge Discovery in Databases 153 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 8.2 Previous Approaches towards Accident Severity Estimation using Data Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 8.3 Our Proposal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 8.3.1 Estimating Traffic Accidents Severity using a KDD-based approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 8.3.2 Data acquisition, Selection and Preprocessing Phases . . . . 157 8.3.3 Transformation Phase . . . . . . . . . . . . . . . . . . . . . 158 xiii CONTENTS 8.3.4 Data Mining and Interpretation/Evaluation Phases . . . . . 160 8.3.4.1 Results of the classification . . . . . . . . . . . . . 164 8.3.4.2 Bayesian models for accident severity estimation . 164 8.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 9 Improving Traffic accidents sanitary resource allocation based on Multi-Objective Genetic Algorithms 169 9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 9.2 Sanitary resources required in a traffic accident . . . . . . . . . . . 170 9.2.1 Features of the different sanitary vehicles . . . . . . . . . . 171 9.2.1.1 Severity of injuries supported . . . . . . . . . . . . 173 9.2.1.2 Passenger capacity . . . . . . . . . . . . . . . . . . 173 9.2.1.3 Accessible areas . . . . . . . . . . . . . . . . . . . 174 9.2.1.4 Average speed . . . . . . . . . . . . . . . . . . . . 174 9.2.1.5 Cost of service . . . . . . . . . . . . . . . . . . . . 174 9.2.2 Sanitary vehicles allocation policy . . . . . . . . . . . . . . 174 9.2.3 Objectives of the resource allocation . . . . . . . . . . . . . 176 9.3 Multi-objective Optimization: Search through Genetic Algorithms 177 9.3.1 Multi-objective Optimization . . . . . . . . . . . . . . . . . 178 9.3.2 Evolutionary algorithms . . . . . . . . . . . . . . . . . . . . 179 9.3.3 Multi-objective Optimization based on Evolutionary Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 9.3.4 Hybridization with other techniques: Memetic Algorithms. 181 9.4 Genetic algorithm for sanitary resource allocation . . . . . . . . . . 182 9.4.1 Parameter Definition for the Genetic Algorithm . . . . . . . 183 9.4.2 Constraint handling . . . . . . . . . . . . . . . . . . . . . . 187 9.4.3 Hybridization of the NSGA-II Algorithm in GATARA . . . 188 9.5 Algorithm evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 188 9.5.1 Definition of the evaluation problem . . . . . . . . . . . . . 188 9.5.2 Drawbacks of the simple a priori approach . . . . . . . . . 189 9.5.3 Comparison between GATARA and other algorithms approximating the Pareto front . . . . . . . . . . . . . . . . . 192 9.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 10 Conclusions, Publications and Future Work 199 10.1 Publications Related to the Thesis . . . . . . . . . . . . . . . . . . 200 10.1.1 Journals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 10.1.2 Indexed Conferences . . . . . . . . . . . . . . . . . . . . . . 204 10.1.3 International Conferences . . . . . . . . . . . . . . . . . . . 206 10.1.4 National Conferences . . . . . . . . . . . . . . . . . . . . . . 208 10.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 xiv List of Algorithms 1 eMDR Send() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 2 eMDR OnRecv() . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 3 PAWDS() pseudo-code . . . . . . . . . . . . . . . . . . . . . . . . . 114 4 General scheme for an evolutionary algorithm . . . . . . . . . . . . 180 5 Pseudo-code representing the calculation of the assistance quality penalty for transport resources. . . . . . . . . . . . . . . . . . . . . 184 6 Pseudo-code representing the calculation of the assistance quality penalty for support resources. . . . . . . . . . . . . . . . . . . . . . 185 xv List of Figures 2.1 Golden hour in a car accident. . . . . . . . . . . . . . . . . . . . . 18 2.2 Old method of rescue using a cellular phone when an accident occurred. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3 Current method of rescue when an accident occurs (e.g. eCall and OnStar). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.4 Future emergency rescue architecture combining V2I and V2V communications, combining localized alerts and warnings, special control information transmission, intelligent databases, and a Control Unit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.5 Example of a VANET. . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.6 Traffic safety applications of VANETs. . . . . . . . . . . . . . . . . 28 2.7 Comfort and commercial applications of VANETs. . . . . . . . . . 29 3.1 Downtown definition (Step 2 out of 5 of the C4R wizard). . . . . . 34 3.2 Simulated scenario of San Francisco, USA. . . . . . . . . . . . . . . 39 3.3 Cumulative histogram for the time evolution of disseminated warning messages using different mobility generators. . . . . . . . . . . 40 3.4 Warning notification time when varying the attenuation scheme. . 46 4.1 RAV visibility scheme: example scenario. . . . . . . . . . . . . . . 60 4.2 Scenarios used in our simulations as street graphs in SUMO: (a) fragment of the city of New York (USA), (b) fragment of the city of Rome (Italy), and (c) fragment of the city of San Francisco. . . 62 4.3 Cumulative histogram for the time evolution of disseminated warning messages when varying the RPM used. . . . . . . . . . . . . . . 66 4.4 Evolution of the warning message dissemination process in the Rome scenario after 20 seconds, when using (a) the TwoRay Ground and (b) the RAV model. . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.5 Warning notification time when varying the density of vehicles. . . 68 4.6 Evolution of the warning message dissemination process in the Rome scenario after 20 seconds, when simulating (a) 100 and (b) 400 vehicles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.7 Warning notification time when varying the roadmap. . . . . . . . 70 xvii LIST OF FIGURES 4.8 Evolution of the warning message dissemination process after 20 seconds, when simulating (a) New York, (b) San Francisco, and (c) Rome scenarios. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.1 Example of wireless signal propagation in an urban scenario extracted from Google Maps. The lightest area represents the transmission range in a obstacle free environment, and the darkest area indicates the zone where the signal would not be propagated due to blocking by the nearby building. . . . . . . . . . . . . . . . . . . . 77 5.2 The enhanced Message Dissemination based on Roadmaps scheme: example scenario taken from the city of Valencia in Spain. . . . . . 81 5.3 eMDR algorithm flow chart. . . . . . . . . . . . . . . . . . . . . . . 82 5.4 Scenarios used in our simulations as street graphs in SUMO: (a) fragment of the city of New York (USA), (b) fragment of the city of Madrid (Spain), and (c) fragment of the city of Rome (Italy). . 86 5.5 Average notification time and percentage of vehicles informed obtained when simulating 200 vehicles and varying the simulation scenario: (a) New York, (b) Madrid, and (c) Rome. . . . . . . . . . . 89 5.6 Average notification time and percentage of vehicles informed obtained in the Rome scenario and simulating: (a) 100 vehicles, (b) 200 vehicles, (c) 300 vehicles, and (d) 400 vehicles. . . . . . . . . . 91 5.7 Average number of messages received per vehicle in the different scenarios: (a) New York, (b) Madrid, and (c) Rome. . . . . . . . . 92 5.8 Average reception overhead in the different scenarios: (a) New York, (b) Madrid, and (c) Rome. . . . . . . . . . . . . . . . . . . . . . . 94 5.9 Average notification time and percentage of vehicles informed obtained when simulating 200 vehicles under different levels of GPS inaccuracy and varying the simulation scenario: (a) New York, (b) Madrid, and (c) Rome. . . . . . . . . . . . . . . . . . . . . . . . . . 96 5.10 Average notification time and percentage of vehicles informed obtained when simulating 400 vehicles in the Madrid scenario under different levels of background traffic: (a) only warning message dissemination, (b) additional 1 MB/s broadcast by each vehicle, and (c) additional 2 MB/s broadcast by each vehicle. . . . . . . . . . . 98 5.11 Evolution of the warning message dissemination process in the Madrid scenario simulating 100 vehicles and using a location-based scheme after (a) 5 seconds and (b) 15 seconds. . . . . . . . . . . . . . . . . 99 5.12 Differences in number of messages with respect to the locationbased scheme simulating 100 vehicles in the Madrid scenario; using a distance-based scheme after (a) 5 seconds and (b) 15 seconds, and our proposed eMDR after (c) 5 seconds and (d) 15 seconds. . . . . 100 5.13 Evolution of the warning message dissemination process in the Madrid scenario simulating 400 vehicles and using a location-based scheme after (a) 5 seconds and (b) 15 seconds. . . . . . . . . . . . . . . . . 101 xviii LIST OF FIGURES 5.14 Differences in number of messages with respect to the locationbased scheme simulating 400 vehicles in the Madrid scenario; using a distance-based scheme after (a) 5 seconds and (b) 15 seconds, and our proposed eMDR after (c) 5 seconds and (d) 15 seconds. . . . . 102 6.1 Scenarios used in prior simulations as street graphs in SUMO: (a) fragment of the city of New York (USA), (b) fragment of the city of San Francisco (USA), and (c) fragment of the city of Rome (Italy).108 6.2 Warning notification time when varying the roadmap under the same simulation configuration. . . . . . . . . . . . . . . . . . . . . 109 6.3 Evolution of the warning message dissemination process after 20 seconds, when simulating (a) New York, (b) San Francisco, and (c) Rome scenarios. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 6.4 Classification of different cities based on the density of streets and junctions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 6.5 Additional scenarios used in our simulations as street graphs in SUMO: (a) fragment of the city of Los Angeles (USA), (b) fragment of the city of Madrid (Spain), and (c) fragment of the city of London (UK). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 6.6 Warning notification time in different scenarios simulating (a) 100 vehicles (25 vehicles/km2) and (b) 400 vehicles (100 vehicles/km2). 120 6.7 Number of messages received per vehicle simulating (a) the formerly presented scenarios, and (b) the additional street maps, under different vehicle densities. . . . . . . . . . . . . . . . . . . . . . . . . . 121 6.8 Warning notification time with the different PAWDS working modes compared to an ideal dissemination scheme without collisions in different cities: Los Angeles with (a) 100 and (b) 400 vehicles, Madrid with (c) 100 and (d) 400 vehicles, and London with (e) 100 and (f) 400 vehicles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 6.9 Number of messages received per vehicle with the different PAWDS working modes simulating (a) 100 and (b) 400 vehicles. . . . . . . 124 6.10 Average simulation results after 30 runs in: Los Angeles with (a) 100 and (b) 400 vehicles, Madrid with (c) 100 and (d) 400 vehicles, and London with (e) 100 and (f) 400 vehicles. The working modes selected by our algorithm are represented using solid lines. . . . . . 126 7.1 Impact of the year of manufacture of the vehicle in the rescue speed [All12]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 7.2 Main rescue problems at the accident site [All12]. . . . . . . . . . . 132 7.3 e-NOTIFY architecture based on the combination of V2V and V2I communications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 7.4 OBU structure diagram. . . . . . . . . . . . . . . . . . . . . . . . . 135 7.5 Acceleration pulses for different front crash ratings. Data provided by Applus+ IDIADA Corporation [IDI12]. . . . . . . . . . . . . . . 137 7.6 OSGi architecture. . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 7.7 Warning packet format for the proposed system. . . . . . . . . . . 139 7.8 Control Unit in the e-NOTIFY system. . . . . . . . . . . . . . . . 140 xix LIST OF FIGURES 7.9 Control Unit modular structure. . . . . . . . . . . . . . . . . . . . 141 7.10 Example of standard rescue sheet. . . . . . . . . . . . . . . . . . . 142 7.11 Data Acquisition Unit prototype. . . . . . . . . . . . . . . . . . . . 144 7.12 Logical design of the circuit in charge of reading the data from the in-vehicle sensors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 7.13 Format of the packet sent by the DAU prototype. . . . . . . . . . . 145 7.14 Web interface screenshots with information about notified accidents. 147 7.15 Sled with the e-NOTIFY prototype installed before a crash detection test. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 7.16 Acceleration pulses collected by Applus+ IDIADA compared to the samples obtained by the e-NOTIFY system in the same experiments: (a) front minor accident (top), and (b) front severe accident (bottom). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 7.17 Images of the crash test results: (a) Accident pulse recorded by the OBU (top), and (b) the same accident notified and received by the CU (bottom). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 8.1 Influence of the speed of the vehicle on the distribution of the severity of the passengers’ injuries in (a) front, (b) side, and (c) rear-end impacts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 8.2 Influence of the speed limit on the distribution of the severity of the passengers’ injuries in (a) front, (b) side, and (c) rear-end impacts. 162 8.3 Comparison of different data mining classification algorithms in the estimation of the damage on the vehicle due to the accident: (a) using the TP Rate metric, and (b) using the AUC metric. . . . . . 165 8.4 Comparison of different data mining classification algorithms in the estimation of the injuries of the passengers in the vehicle: (a) using the TP Rate metric, and (b) using the AUC metric. . . . . . . . . 166 9.1 Classification of sanitary vehicles needed in a traffic accident: (a) Non-assistance ambulance, (b) BLS ambulance, (c) ALS ambulance, (d) FIV vehicle, and (e) HEH helicopter. . . . . . . . . . . . . . . . 172 9.2 Representation of individuals in the genetic algorithm for resource allocation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 9.3 Example of crossover operator using two cutoff points. . . . . . . . 187 9.4 Example scenarios for a traffic accident resource allocation in a 100 km ×100 km area with (a) 10 suppliers, and (b) 20 suppliers. . . . 190 9.5 Different solutions obtained using different weight sets for the a priori approach in the (a) 10 suppliers scenario, and (b) 20 suppliers scenario. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 9.6 Evolution of the mean value of the objective functions for the individuals in the population when varying the genetic algorithm in the 10 suppliers scenario. . . . . . . . . . . . . . . . . . . . . . . . 194 9.7 Pareto front obtained when varying the genetic algorithm in the 10 suppliers scenario: (a) VEGA, (b) MOGA, (c) NSGA-II, and (d) GATARA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 xx LIST OF FIGURES 9.8 Evolution of the mean value of the objective functions for the individuals in the population when varying the genetic algorithm in the 20 suppliers scenario. . . . . . . . . . . . . . . . . . . . . . . . 196 9.9 Pareto front obtained when varying the genetic algorithm in the 20 suppliers scenario: (a) VEGA, (b) MOGA, (c) NSGA-II, and (d) GATARA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 xxi Chapter 2 Vehicular Networks Over the years, we have harnessed the power of computing to improve the speed of operations and increase in productivity. Also, we have witnessed the merging of computing and telecommunications. This excellent combination of two important fields has propelled our capabilities even further, allowing us to communicate anytime and anywhere, improving our work flow and increasing our life quality tremendously. The next wave of evolution we foresee is the convergence of telecommunications, computing, wireless, and transportation technologies. Once this happens, our roads and highways will be both our communications and transportation platforms, which will completely revolutionize when and how we access services and entertainment, how we communicate, commute, navigate, in the coming future. This chapter presents an overview of the current state-of-the-art, discusses current projects, their goals, and finally highlights how emergency services and road safety will evolve with the blending of vehicular communication networks and road transportation. 2.1 Introduction The population of the world has been increasing, with China and India being the two most densely populated countries. Road traffic has also been getting more and more congested, as a higher population and increased business activities result in greater demand for cars and vehicles for transportation. While careful city planning can help to alleviate transportation problems, such planning does not usually scale well over time with unexpected growth in population and road usage. Modernization, migration, and globalization have also taken great tolls on road usage. Inadequacy in transportation infrastructures can cripple a nation’s progress, social well-being, and economy. It can also make a country less appealing to foreign investors and can cause more pollution as vehicles spend a longer time waiting on congested roads. Increased delays can also result in road rage, which gives rise to more social problems, which are undesirable. With fuel price 5 CHAPTER 2. VEHICULAR NETWORKS soaring and potential threats of fuel shortage, we are now faced with greater challenges in the field of transportation systems. In addition to this trend, technology has also impacted transportation, giving it a different outlook. In the past, people were focused on how to build efficient highways and roads. Over time, focus shifted to mechanical and automotive engineering, in the pursuit of building faster cars to surmount greater distances. Later on, electronics technology impacted the construction of cars, embedding them with sensors and advanced electronics, making cars more intelligent, sensitive and safe to drive on. Now, innovations made so far in wireless mobile communications and networking technologies are starting to impact cars, roads, and highways. This impact will drastically change the way we view transportation systems of the next generation and the way we drive in the future. It will create major economic, social, and global impact through a transformation taking place over the next 10-15 years. Hence, technologies in the various fields have now found common grounds in the broad spectrum of the Next Generation Intelligent Transportation Systems (ITS). In this chapter we examine the impact of future ITS technologies on road safety and emergency services. This chapter is organized as follows: Section 2.2 introduces the current advances and world trends regarding road safety, vehicular communication networks, and telematics. Section 2.3 presents the motivation of using wireless networks in vehicular environments. Section 2.4 discusses the problems related to road safety and the emergency services. The evolution of communications in emergency services when an accident occurs is described in Section 2.5. Section 2.6 presents the different issues regarding ITS and vehicular communications that we envision. In Section 2.7 we make an introduction to Vehicular Ad Hoc Networks (VANETs), showing their main characteristics and applications. Finally, Section 2.8 concludes this chapter. 2.2 Advances and Trends in Vehicular Network Technologies Recently, there have been several projects and research efforts conducted globally to address road safety, vehicular communication networks, and telematics. IN KOREA - The Korean Telematics Business Association was established in 2003 with the aim of boosting the telematics industry and to standardize telematic technologies and services. Its members are primarily automakers, telecommunication companies, terminal manufacturers, and content providers. Its core functions include: (a) coordinating Korean government projects related to telematics, (b) market promotion, (c) standardization efforts, and (d) international collaboration in conferences, road shows, etc. IN JAPAN - The topics on ITS have been actively addressed by Japanese researchers and Japanese government agencies over the years. Specifically, the Japanese Ministry of Land, Infrastructure and Transport (MLIT) is the bureau of the Japanese government that decides on policies in ITS. In Japan, ITS are viewed as a new transport system that comprises an advanced information and telecommunications network for users, roads, and vehicles. Specifically, nine de6 2.2. ADVANCES AND TRENDS IN VEHICULAR NETWORK TECHNOLOGIES Table 2.1: ITS projects in Japan Japan ITS Remarks Funded Projects AHS [mli03] Advanced Cruise-Assist Highway Systems It aims at reducing traffic accidents, enhancing safety, improving transportation efficiency, as well as reducing the operational work of drivers. AHS research is being carried out in the following fields: - AHS-”i” (information) focusing on providing information. - AHS-”c” (control): vehicle control assistance. - AHS-”a” (automated cruise): fully automated driving. Its applications include obstacle detection and avoidance, speed control, driving control and man-machine interfaces. ASV [mli03] Advanced Safety Vehicle It was launched in order to transfer advanced technologies to vehicles for their greater safety. In the second phase, the extent of research has been expanded to include trucks, buses and motorcycles. Automated driving technology and basic vehicular technology areas have been added to the major safety technology field. Also, research and development will be promoted in connection with infrastructures, using two systems: autonomous type and infrastructure-employed type. This will make it possible to combine ASV with AHS. velopments areas have been identified: (a) navigation systems, (b) electronic toll collection (ETC) systems, (c) assistance for safe driving, (d) optimization of traffic management, (e) efficiency in road management, (f) support for public transport, (g) efficiency in commercial vehicles, (h) support for pedestrians, and (i) support for emergency vehicle operations. Table 2.1 shows the most important ITS projects funded by the Japanese MLIT. Both projects aim to enhance safety and reduce traffic accidents while improving transportation efficiency. IN THE USA - There are two major programs sponsored by the US DoT (Department of Transportation). The first one is the Vehicle Safety Communication (VSC) project. The second one is related to Vehicle Infrastructure Integration (VII). A VII consortium has been formed to engage key industrial players, state and local governments, as well as other partners to work on an information infrastructure for real-time communications between vehicles. The motivations for a VII program in the USA are well justified. American roadways indeed have a safety and congestion problem. In fact, in 2006, there were 6 million traffic crashes in the USA alone, injuring about 2.6 million people. Also, it was observed that a crash occurred every 5 seconds, with someone sustaining a traffic-related injury every 12 seconds. Worse, someone died in a traffic crash every 12 minutes. This death toll is major and astonishing. In addition, road congestion problems have resulted in 4.2 billion hours of travel delay, 2.9 billion gallons of gasoline fuel wasted, and a net urban congestion cost of about $80 billion (according to a 2007 report by the 7 CHAPTER 2. VEHICULAR NETWORKS Table 2.2: ITS projects in the USA USA ITS Remarks Funded Projects VSC [vsc11] Vehicle Safety Communication The main objectives of the VSC project are: - Estimate the potential safety benefits of vehicle safety applications. Define preliminary communications requirements for the high-priority vehicle safety applications. - Evaluate proposed DSRC standards, identify specific technical issues, present vehicle safety requirements, and secure DSRC for safety applications at real intersections. - Identify channel capacity in stressing traffic environments as a large scale deployment issue, determining that the 5.9 GHz DSRC wireless technology is potentially best able to support the communications requirements. VII [vii11] Vehicle Infrastructure Integration VII will enable safety, mobility, and commercial vehicular services and applications. It will exploit innovations in wireless communications and networking technologies, along with sensing and advanced user interfaces. When deployed, the VII network will allow drivers and travelers to access traffic conditions and routing information, receive warnings about existing or upcoming hazards, and conduct wireless commercial transactions while on-the-move. 8 2.3. VEHICULAR NETWORKS: RATIONALE & MOTIVATION Texas Transportation Institute). Table 2.2 shows the most important USA ITS projects. IN EUROPE - There are a lot of integrated projects funded by the European Commission under the EU IST 6th Framework (FP6) (2002-2006), and the EU 7th Framework (FP7) extends the program further till 2013. The White Paper on EU Transport Policy for 2010 states a key objective, i.e., 50% reduction of casualties due to road accidents by the end of 2010. Improvements on road safety are achievable by increasing the EU market penetration of Advanced Driver Assistance Systems (ADAS), currently limited by the performance and cost of sensor technologies. This is the prime focus of the European ITS research program. Tables 2.3, 2.4, 2.5, and 2.6 describe some of the most relevant ITS projects funded by the European Union. These projects cover a wide spectrum of research areas, including driver-vehicle interfaces, emergency rescue, preventive road safety, onboard sensors, pedestrian detection, intersection safety, cooperative systems and cooperative networks, maps and geographical technologies, and vehicle-to-vehicle (V2V) communications. In this chapter, we focus on how vehicular communication networks have impacted road safety, and how emergency services will evolve in the future. 2.3 Vehicular Networks: Rationale & Motivation In the past, the automotive industry built powerful and safer cars by embedding advanced materials and sensors. With the advent of wireless communication technologies, cars are being equipped with wireless communication devices, enabling them to communicate with other cars. Such communications are not plainly restricted to data transfers (such as emails, etc.), but also create new opportunities for enhancing road safety. Some applications only require communication among vehicles, while other applications require the coordination between vehicles and the road-side infrastructure. The applications and advantages of using vehicular communication networks for enhancing road safety and driving efficiency are diverse, which explains why research in this area has recently emerged. Vehicular communications, however, need the support of reliable link and channel access protocols. The IEEE 802.11p wireless access in vehicular environments (WAVE) [IEE10] is a standardization effort that provides a protocol suite to support vehicular communications in the 5.9 GHz licensed frequency band (5.85-5.925 GHz). WAVE supports both vehicle-to-infrastructure (V2I) and vehicle-to-vehicle (V2V) communications. Also, WAVE can enhance road safety and driving efficiency since it offers the required support to provide faster rescue operations, generate localized warnings of potential danger, and convey real-time accident warnings. WAVE complements satellite, WiMax, 3G, and other communications protocols by providing high data transfer rates (3-54 Mbps) in circumstances where the latency in the communication link is too high, and where isolating relatively small communication zones is important. Details about radio frequencies, modulation, link control protocols and media access can be found in [UDSAM09]. Concerning safety using vehicular networks, in [Toh07], cars can act as com9 CHAPTER 2. VEHICULAR NETWORKS Table 2.3: ITS projects in EU EU ITS Funded Remarks Projects AIDE [aid11b] Adaptive Integrated Driver-vehicle Interface The general objective is to generate knowledge and develop methodologies and human-machine interface technologies required for safe and efficient integration of ADAS (Advanced Driver Assist Systems), IVIS (In-Vehicle Information Systems) and nomad devices into the driving environment. The aims of AIDE are: - to maximize the efficiency, and hence the safety benefits, of advanced driver assistance systems - to minimize the level of workload and distraction imposed by in-vehicle information systems and nomad devices - to enable the potential benefits of new in-vehicle technologies and nomad devices in terms of mobility and comfort AIDER [aid11a] Accident Information and Driver Emergency Rescue The AIDER project’s main objective is the reduction of road accident consequences by optimizing the rescue management in terms of operative time and effectiveness. AIDER vehicles will be equipped with a detection system to monitor the on-board preand post-crash environment. The project envisaged a kind of automotive ”black box”, which would continually assess a car’s environment, including speed, terrain and many other factors. Should there be an accident, the box would perform a quick calculation, comparing the state of the vehicle before and after impact. This would yield important information about where the car was hit, how quickly the car stopped, and therefore how severe the accident was. The box would then alert a call center with essential details about the nature of the crash, which could be reconstructed. Since the emergency services would be contacted immediately and provided with details about the accident, they would arrive more quickly and be better prepared for specific injuries. ATLANTIC A Thematic Long-term Approach to Networking for the [atl11] Telematics & ITS Community The ATLANTIC Thematic network will operate as an Electronic Forum organized and coordinated through three geographically based network coordinators, one for each of Europe, Canada and USA. The ATLANTIC project has three parts: (1) Operation of an ITS Forum based on e-mail groups, involving key individuals in the field of Transport Telematics and Intelligent Transport Systems (ITS). The Forum sub-groups will be benchmarking the coverage, content and results of the European ITS programs against similar activities in the USA and Canada. (2) International meetings with American and Canadian partners in the project, which are self-funded. (3) Development of good practice and policy on telematics-based travel information services for cities and regions. 10 2.3. VEHICULAR NETWORKS: RATIONALE & MOTIVATION Table 2.4: ITS projects in EU (Cont.) EU ITS Funded Remarks Projects PREVENT [pre11] Preventive and Active Safety Applications Contribute to the Road Safety Goals on European Roads In PReVENT, a number of subprojects are proposed within clearly complementary function fields: Safe Speed and Safe Following, Lateral Support and Driver Monitoring, Intersection Safety, and Vulnerable Road Users and Collision Mitigation. The goal of Integrated Project PReVENT is to contribute to the: - Road safety goal of 50% fewer accidents by 2010 - as specified in the key action eSafety for Road and Air Transport from the European Union. - Competitiveness of the European automotive industry. - European scientific knowledge community on road transport safety. - Congregation and cooperation of European and national organizations and their road transport safety initiatives. ADOSE [ado11] Reliable Application Specific Detection of Road Users with Vehicle On-board Sensors ADOSE addresses research challenges in the area of ”accident prevention through improved-sensing including sensor fusion and sensor networks”. Focus is also on ”increased performance, reliable and secure operation” for ”new generation advanced driver assistance systems”. The project is focused mainly on sensing elements and their pre-processing hardware, as a complementary project to PReVENT. Novel concepts and sensory systems will be developed based on Far Infrared cameras, CMOS vision sensors, 3D packaging technologies, ranging techniques, bio-inspired silicon retina sensors, harmonic microwave radar and tags. INTERSAFE-2 Cooperative Intersection Safety [int11] The INTERSAFE-2 project aims to develop and demonstrate a Cooperative Intersection Safety System (CISS) that is able to significantly reduce injury and fatal accidents at intersections. The novel CISS combines warning and intervention functions based on novel cooperative scenario interpretation and risk assessment algorithms. The cooperative sensor data fusion is based on advanced on-board sensors for object recognition, a standard navigation map, and information supplied over a communications link from other road users via V2V and infrastructure sensors and traffic lights via V2I. SAFERIDER Advanced Telematics for Enhancing the Safety and Comfort [saf11a] of Motorcycle Riders SAFERIDER aims to study the potential of ADAS/IVIS integration on motorcycles for the most crucial functionalities, and develop efficient and rider-friendly interfaces and interaction elements for riders’ comfort and safety. SAFERIDER aims to enhance riders’ safety by introducing four ADAS applications: (a) speed alert, (b) curve speed warning, (c) frontal collision warning, and (d) intersection support. 11 CHAPTER 2. VEHICULAR NETWORKS Table 2.5: ITS projects in EU (Cont.) EU ITS Funded Remarks Projects SafeSpot Cooperative vehicles and road infrastructure for road safety [saf11b] The objective of the project is to understand how intelligent vehicles and intelligent roads can cooperate to increase road safety. SafeSpot seeks to: - Use the infrastructure and the vehicles as sources and destinations of safety-related information and develop an open, flexible and modular architecture and communications platform. - Develop the key enabling technologies: ad-hoc dynamic network, accurate relative localization, dynamic local traffic maps. - Develop and test scenario-based applications to evaluate the impacts on road safety. - Define a sustainable deployment strategy for cooperative systems for road safety, evaluating also related liability, regulations and standardization aspects. I-WAY [iwa11] Intelligent Cooperative Systems in Car for Road Safety The goal of I-WAY is to develop a multi-sensorial system that can ubiquitously monitor and recognize the psychological condition of drivers as well as special conditions prevailing in the road environment. The I-WAY platform targets mainly road users, but it is a highly modular system that can be easily adapted or break up in standalone modules in order to accommodate a wide variety of applications and services in several fields of transport, thanks to its interoperability and scalable system architecture. The I-Way project is strongly committed to achieve the two strategic objectives of (a) increasing road safety, and (b) bettering transport efficiency. COMeSafety Communications for eSafety [com11] The COMeSafety Project supports the eSafety Forum with respect to all issues related to V2V and V2I communications as the basis for cooperative intelligent road transport systems. COMeSafety provides an open and integrating platform, aiming at representing the interests of all public and private stakeholders. COMeSafety acts as a broker for the consolidation and following standardization of research project results, work of the C2C-CC and the eSafety Forum. Its aims are: - Coordination and consolidation of research results and their implementation. - eSafety Forum support in case of Standardization and Frequency Allocation. - Worldwide harmonization (Japan/US/Europe). - Support the frequency allocation process. - Dissemination of the results. 12 2.3. VEHICULAR NETWORKS: RATIONALE & MOTIVATION Table 2.6: ITS projects in EU (Cont.) EU ITS Funded Remarks Projects HIGHWAY Breakthrough Intelligent Maps and Geographic Tools for the [hig11] context-aware-delivery of E-safety and added value services HIGHWAY combines smart real-time maps, UMTS 3G mobile technology, positioning systems and intelligent agent technology, 2D/3D spatial tools, and speech synthesis/voice recognition interfaces to provide European car drivers and pedestrians with eSafety services and interaction with multimedia (text, audio, images, real-time video, voice/graphics) and value-added-location-based services. HIGHWAY maps will help drivers facing critical driving situations. CarTALK2000 Advanced driver support system based on V2V communication [car11] technologies CarTALK2000 was established within the EU’s ADASE2 (Advanced Driver Assistance Systems Europe) ITS project. Its main objectives were the development of cooperative driver assistance systems and a self-organizing ad hoc radio network as the basis for communication with the aim of preparing a future standard. It incorporated three applications: a warning system that relays information about accidents ahead, break-downs and congestion; a longitudinal control system; and a cooperative driving assistance system that supports merging and weaving. COOPERS Cooperative Networks for Intelligent Road Safety [coo11] COOPERS focuses on the development of innovative telematic applications on the road infrastructure with the long term goal of a Cooperative Traffic Management between vehicle and infrastructure, thus reducing the self opening gap on telematic application development between car industry and infrastructure operators. The goal of the project is the enhancement of road safety by direct and up-to-date traffic information based on wireless communication between infrastructure and motorized vehicles on a motorway section. CVIS [cvi11] Cooperative Vehicle-Infrastructure Systems Contrarily to SafeSpot, this European project focuses on vehicle-toinfrastructure communications alone. The goals set are: - To create a unified technical solution allowing all vehicles and infrastructure elements to communicate with each other in a continuous and transparent way using a variety of media with enhanced localization. - To define and validate an open architecture and system concept for a number of cooperative system applications, and develop common core components to support cooperation models in real-life applications and services for drivers, operators, industry and other key stakeholders. - To address issues such as user acceptance, data privacy and security, system openness and interoperability, risk and liability, public policy needs, cost/benefit and business models, and roll-out plans for implementation. 13 CHAPTER 2. VEHICULAR NETWORKS munication relays (routers) to form ad hoc vehicular networks via wireless communication links. Cars are restricted by the physical boundaries of the road and highways. For example, cars on one lane all travel in the same direction, keeping ample safe distance from one to another. The ability of neighboring cars to communicate wirelessly allows them to warn each other about any abnormalities or potential dangers. This, in contrast to the old way of ”signaling” using visual lights, is far superior, especially when visibility is poor due to bad weather conditions. Another scenario is the ability of cars to convey accident information to other neighboring cars via V2V communications so that they can slow down and be aware of the potential danger ahead. Also, in times of road congestion, V2V communications can allow other cars further down the road to make plans to exit the highway or to seek alternate routes to their destinations, hence avoiding further congestions. V2V communications have the following advantages: (i) allow short and medium range communications, (ii) present lower deployment costs, (iii) support short messages delivery, and (iv) minimize latency in the communication link. Nevertheless, V2V communications present the following shortcomings: (i) frequent topology partitioning due to high mobility, (ii) problems in long range communications, (iii) problems using traditional routing protocols, and (iv) broadcast storm problems [TNCS02] in high density scenarios. Currently, there are several projects that address V2V communication issues. Wisitpongphan et al. [WTP+07] quantified the impact of broadcast storms in VANETs in terms of message delay and packet loss rate, in addition to conventional metrics such as message reachability and overhead. They proposed three probabilistic and timer-based broadcast suppression techniques: (i) the weighted ppersistence, (ii) the slotted 1-persistence, and (iii) the slotted p-persistence scheme. The authors also studied the routing problem in sparse VANETs [WBM+07]. In [TWB07], they proposed a new Distributed Vehicular Broadcasting protocol (DV-CAST) to support safety and transport efficiency applications in VANETs. Results showed that broadcasting in VANET is very different from routing in mobile ad hoc networks (MANET) due to several reasons such as network topology, mobility patterns, demographics, and traffic patterns at different times of the day. These differences imply that conventional ad hoc routing protocols will not be appropriate in VANETs for most vehicular broadcast applications. The designed protocol addressed how to deal with extreme situations such as dense traffic conditions during rush hours, sparse traffic during certain hours of the day (e.g., midnight to 4 am in the morning), and low market penetration rate of cars using DSRC technology. Table 2.7 shows some of the major testbeds related to ITS/VANET developed by National Labs and Universities that have been used to test and evaluate vehicular network solutions. Concerning V2I, current research efforts include: (a) information dissemination for VANETs, especially using advanced antennas [KRS+07], (b) VANET/Cellular interoperability [SRS+08], and (c) WiMAX penetration in vehicular scenarios [YOCH07]. The integration of Worldwide Interoperability for Microwave Access (WiMAX) and Wireless fidelity (WiFi) technologies seems to be a feasible option for better and cheaper wireless coverage extension in vehicular networks. WiFi, 14 2.4. ROAD SAFETY AND EMERGENCY SERVICES Table 2.10: Pre-Crash developed systems by car automakers (Cont.) Brand Remarks Toyota - Pre-Collision System is the very first radar-based pre-crash system which uses a forward facing millimeter-wave radar system. When the system determines a frontal collision is unavoidable, it preemptively tightens the seat belts removing any slack and pre-charges the brakes. The advanced Pre-Collision System added a twin-lens stereo camera located on the windshield and a more sensitive radar to detect for the first time smaller ”soft” objects such as animals and pedestrians. A near-infrared projector located in the headlights allows the system to work at night. - In 2007, the world’s first Driver Monitoring System was introduced on the Lexus LS, using a CCD camera on the steering column; this system monitors the driver’s face to determine where the driver is looking at. If the driver’s head turns away from the road and a frontal obstacle is detected, the system will alert the driver using a buzzer and if necessary pre-charge the brakes and tighten the safety belts. - In 2008, the Toyota Crown monitors the driver’s eyes to detect the driver’s level of wakefulness. This system is designed to work even if the driver is wearing sunglasses. Toyota added a pedestrian detection feature which highlights pedestrians and presents them on an LCD display located in front of the driver. The latest Crown also uses a GPS-navigation linked brake assist function. The system is designed to determine if the driver is late in decelerating at an approaching stop sign, it will then sound an alert and can also precharge the brakes to provide optimum braking force if deemed necessary. This system works in certain Japanese cities and requires Japan specific road markings which are detected by a camera. - In March 2009 the redesigned Crown Majesta, further advanced the Pre-Collision System by adding a front-side millimeter-wave radar to detect potential side collisions primarily at intersections and when another vehicle crosses the center line. The latest version slides the rear seat upward, thus placing the passenger in a more ideal crash position if it detects a front or rear impact. Volvo - Volvo’s Collision Warning with Brake Support was introduced on the 2006 Volvo S80. This system provides a warning through a Head Up Display that visually resembles brake lamps. If the driver does not react, the system pre-charges the brakes and increases the brake assist sensitivity to maximize driver braking performance. - Collision Warning with Brake Assist was introduced on the 2007 Volvo S80, V70 and XC70. The system provides the same function as Collision Warning with Brake Support, but in addition, provides autonomously partial braking if the driver does not react to the brake assist functions. 21 CHAPTER 2. VEHICULAR NETWORKS equipped with a kind of black-box that automatically detects the accident when it occurs, records data obtained by in-car sensors, and sends them to the next Public Safety Answering Point (PSAP), in order to ask for help. These systems can also be used to determine the cause of the accident or to inform insurance companies. Modern black-box systems also include a built-in camera to make all the recorded information more precise and intuitive. Moreover, most systems record video for a few seconds just before and after a crash. The National Highway Traffic Safety Administration (NHTSA) estimates that 85% of new cars will have an EDR (black box system) by 2010 [nth11]. 2.5 Trends in Emergency Services: From Cellular to VANET-based The demand for emergency road services has risen around the world. Moreover, changes in the role of emergency crews have occurred - from essentially transporting injured persons (to the hospital) to delivering basic treatment or even advanced life support to patients before they arrive at the hospital. In addition, advances in science and technologies are changing the way emergency rescue operates. In times of road emergency, appropriately skilled staffs and ambulances should be dispatched to the scene without delay. Efficient roadside emergency services demand the knowledge of accurate information about the patient (adult, child, etc), their conditions (bleeding, conscious or unconscious, etc), and clinical needs. In order to improve the chances of survival for passengers involved in car accidents, it is desirable to reduce the response time of rescue teams and to optimize the medical and rescue resources needed. A faster and more efficient rescue will increase the chances of survival and recovery for injured victims. Thus, once the accident has occurred, it is crucial to efficiently and quickly manage the emergency rescue and resources. An Automatic Crash Notification system will automatically notify the nearest emergency call center when a vehicle crashes. These call centers will determine the nature of the call and, if it is an emergency, data from vehicular sensors will allow the call center to evaluate if the vehicle has been involved in a collision. Vehicular sensors may indicate that an airbag was triggered, the mechanical impact on the vehicle, whether the vehicle did roll-over, the deceleration history and status, the number of passengers in the car, etc. Knowing the severity of emergencies and their precise locations can save lives readily while utilizing rescue resources efficiently. The method for seeking help when an accident occurs has changed over the years. Figure 2.2 shows the old method of accident notification, where a witness of the car accident calls the police for help. Basically, the witness gives information about the location of the accident and the fatalities involved. Once the police is notified, they coordinate the rescue effort by alerting the fire department and medical services, summoning for an ambulance to the accident site quickly. Figure 2.3 shows the current method of accident notification. When an accident occurs, a call is made to an ”answering point” in order to send information about the accident and to ask for help. 22 2.5. TRENDS IN EMERGENCY SERVICES: FROM CELLULAR TO VANET-BASED Figure 2.2: Old method of rescue using a cellular phone when an accident occurred. Figure 2.3: Current method of rescue when an accident occurs (e.g. eCall and OnStar). 23 CHAPTER 2. VEHICULAR NETWORKS eCall [ece02] is one of the most important road safety efforts made under the European Union’s eSafety initiative. eSafety seeks to improve road safety by fitting intelligent safety systems based on advanced electronic technologies into road vehicles. In the event of an emergency, the single European emergency number 112 can be called from all the European Union countries. eCalls are made free of charge from fixed-line or mobile phones. eCall builds on E112 [Eur09], a location-enhanced version of 112. The telecom operator transmits the location information to the Public Safety Answering Point (PSAP), which in return must be adequately equipped with a voice-band modem detector, Minimum Set of Data (MSD) decoding capabilities, and trained operators to process this data. PSAP and emergency service chains must be capable of dealing with calls coming from an in-vehicle eCall device. They must also be able to process the MSD, including location data, which is automatically transmitted by the eCall system, even when voice communication is not possible. The content of the MSD includes: (a) control information, (b) VIN (Vehicle Identification Number), (c) time, (d) latitude, (e) longitude, and (f) direction. The recommended transmission of the MSD between the OBU in the car and the PSAP requires a parallel data transmission with voice. Whether the call is made manually or automatically, there will always be a voice connection between the vehicle and the rescue center. In this way, any car occupants capable of answering questions can provide additional details about the accident. For eCall to work, several requirements [Eur09] must be met: Firstly, all newly manufactured cars will have to be equipped with eCall devices. In 2005, the European Commission and the automotive industry association agreed to schedule full-scale deployment of eCall service for 2009. eCall devices were made available as an option for all new cars, on September 2009. Secondly, there is a need for the single European emergency number 112 to be operational for both fixed and mobile calls throughout the European Union. Unfortunately, not all EU member states are able to support the full 112 emergency services. Presently, the eCall system is working in 12 out of 27 EU member states. Thirdly, emergency centers and all rescue services must be capable of processing the accident location data transmitted by eCalls. For example, ambulances must be adequately capable of receiving and processing these data. Rescue centers must be able to forward all the information to the fire brigade, hospital emergency rooms, etc. In addition, to take full advantage of the voice link to the crashed vehicle, rescue center personnel must be properly trained so as to gather critical information in several languages. Essentially, by knowing the exact location of the crash site, response time of emergency services can be reduced by 50% in rural and 40% in urban areas. Due to this time reduction, eCall is expected to save up to 2,500 lives in the EU each year, while at the same time mitigating the severity of tens of thousands of injuries. Since eCall can also accelerate the treatment of injured people, there will be better recovery prospects for accident victims. In addition, earlier arrival at the accident scene will also translate into faster clearance of the crash site, which helps to reduce road congestion, fuel waste, and CO2 emissions. Overall, it aids in our quest for a greener and safer environment. 24 2.6. A VIEW ON FUTURE EMERGENCY SERVICES Table 2.11: eCall VS. OnStar 2.5.1 Comparison of eCall and OnStar OnStar [OnS12] is an in-vehicle safety and security system created by General Motors (GM) for on-road assistance. Both eCall and OnStar systems are, in fact, very similar. A vehicle collision activates on-vehicle sensors, causing an emergency voice call to be initiated. Also, key information about the accident is transmitted. Unlike eCall, OnStar provides an on-road navigation system and assistance in case the vehicle is stolen; it can also remotely unlock vehicles. Nevertheless, eCall is more ambitious since it is expected to support all brands of vehicles in the European Union region, while OnStar is only supported by GM vehicles in the US. Table 2.11 outlines the most important differences between eCall and OnStar. Future accident notification systems will be more ambitious; intelligent systems will automatically adapt the required rescue resources, allowing the rescue staff to work more efficiently, and reducing the time associated with their tasks. 2.6 A View on Future Emergency Services In the future, our current accident notification paradigm will change with the introduction of vehicular networks. By combining V2V and V2I communications, new Intelligent Transportation Systems will emerge, capable of improving the timeliness and responsiveness of roadside emergency services. As shown in Figure 2.4, the accident information gathered can be delivered to a Control Unit (CU) that automatically estimates: (a) the severity of an accident, and (b) the appropriate rescue resources before summoning for emergency services. Future emergency rescue architectures will exploit various communication technologies, such as DSRC, UMTS/HSDPA, and WAVE, empowering road users with both localized (via VANETs) and long haul (via cellular or wide area wireless data) wireless communications. By using vehicular communications, cars involved in an accident can send alerts and other important information about the accident to near-by vehicles and to the nearest wireless base station. Thereafter, an intelli25 CHAPTER 2. VEHICULAR NETWORKS Figure 2.4: Future emergency rescue architecture combining V2I and V2V communications, combining localized alerts and warnings, special control information transmission, intelligent databases, and a Control Unit. gent PSAP will gather this information, and channel the most critical data to the appropriate emergency services. Vehicular networks can allow faster notification of any accident occurring on the road (since sensing and propagation of incident information is done on-the-spot in real-time via multi-hop V2V communications). Surrounding vehicles will be immediately notified of the hazard, and such alerts can be further propagated via radio base stations to the core network. Concerning technology, for any proposal to be successful, it should be compatible with the signaling protocol and air interfaces of existing implementations or standardizations. So, V2V communications should be compatible with the future 802.11p standard, while the V2I counterpart might use any of the 3/4G cellular technologies currently available. The usage of hybrid multi-wireless platforms adds robustness and reliability to the call for emergency help and rescue. In the near future, a community-based effort involving the state departments, public organizations and industry is needed to deploy the required technology and infrastructure to connect all the vehicles on the road and the emergency services. 2.7 Vehicular ad hoc networks (VANETs) Mobile ad hoc networks (MANETs) are a type of wireless network that does not require any fixed infrastructure. MANETs are attractive for situations where communication is required, but deploying a fixed infrastructure is impossible. Vehicular ad hoc networks (VANETs) are a subset of MANETs, and represent a rapidly emerging research field considered essential for cooperative driving 26 2.7. VEHICULAR AD HOC NETWORKS (VANETS) Figure 2.5: Example of a VANET. among communicating vehicles. Vehicles function as communication nodes and relays, forming dynamic networks with other near-by vehicles on the road and highways. While Mobile ad hoc Networks (MANETs) are mainly concerned with mobile laptops or wireless handheld devices, VANETs are concerned with vehicles (such as cars, vans, trucks, etc). Figure 2.5 shows and example of a VANET in a urban scenario, where cars communicate in a multi-hop fashion. Wireless technologies such as Dedicated Short Range Communication (DSRC) [QRTJ04] and the IEEE 802.11p Wireless Access for Vehicular Environment (WAVE) [Eic07] enable peer-to-peer mobile communication among vehicles (V2V) and communication between vehicles and the infrastructure (V2I), and are expected to be widely adopted by the car industry in the next years. To date, many solutions regarding VANETs have been proposed and evaluated via simulation. Nevertheless, the simulation environments used to be very simplistic, so utilizing more realistic simulation environments is required. 2.7.1 Characteristics and Applications of VANETs VANETs are characterized by: (a) trajectory-based movements with prediction locations and time-varying topology, (b) variable number of vehicles with independent or correlated speeds, (c) fast time-varying channel conditions (e.g., signal transmissions can be blocked by buildings), (d) lane-constrained mobility patterns (e.g., frequent topology partitioning due to high mobility), and (e) reduced power consumption requirements. So far, the development of VANETs is backed by strong economical interests since vehicle-to-vehicle (V2V) communication allows using wireless channels for collision avoidance (improving traffic safety), improved route planning, and better control of traffic congestion [BFW03]. 27 CHAPTER 2. VEHICULAR NETWORKS Figure 2.6: Traffic safety applications of VANETs. The specific characteristics of Vehicular networks favor the development of attractive and challenging services and applications. These applications can be grouped together into two main different categories: •Safety applications (see Figure 2.6), that look for increasing safety of passengers by exchanging relevant safety information via V2V and V2I communications, in which the information is either presented to the driver, or used to trigger active safety systems. These applications will only be possible if the penetration rate of VANET-enabled cars is high enough. In this thesis, we will focus in safety applications in order to reduce the number of fatalities while significantly improving the response time and the use of rescue resources. •Comfort and Commercial applications (see Figure 2.7) that improve passenger comfort and traffic efficiency, optimize the route to a destination, and provide support for commercial transactions. Comfort and commercial applications must not interfere with safety applications [JK08]. 2.8 Summary Several research projects led by research institutes and car manufacturers around the world have positively impacted the future of Inter-Vehicle Communication (IVC) systems. Technologies have clearly contributed to the change in the course of actions to follow after an accident occurs, moving from a simple cellular phone 28 2.8. SUMMARY Figure 2.7: Comfort and commercial applications of VANETs. call made by a witness, to the current eCall accident notification system provided in EU. In the near future, accident notification systems will be specially designed for post-collision rescue services. Combining V2V and V2I communications, new Intelligent Transportation Systems will emerge with the capability of improving the responsiveness of roadside emergency services, and allowing: (a) direct communication among the vehicles involved in the accident, (b) automatic delivery of accident related data to the Control Unit, and (c) an automatic and preliminary assessment of damages based on communication and information processing. Future ITS-based emergency services aim at achieving a low level of fatalities while significantly improving the response time and efficient use of resources. In this chapter, we examine the impact of future ITS technologies on road safety and emergency services, and we propose the essential information which will be disseminated by vehicles after an accident. We also presented an overview of the current state-of-the-art of the vehicular wireless technologies that will be widely adopted by industry in the next few years, and the different IEEE standards included in the WAVE architecture. Although more work is required, the foundations are laid to deploy V2I and V2V communication systems. There are clear evidences that it will be possible for our vehicles to communicate among them, or with traffic signs, very soon. This will put at drivers’ disposal a number of services that will improve traffic safety, infotainment, and reduce road congestion, wastage of fuel and CO2 emissions. 29 3.3. C4R: CITYMOB FOR ROADMAPS •Phi. This parameter is only used in the Kerner model, and defines the flow rate measured in vehicles per time interval. •Headway, which sets the desired time headway to the vehicle in front. This parameter is only used in the IDM model. By default, it is set to 1.5 s. •MinGap, which expresses the minimum net distance that is kept even at a complete stand-still in a traffic jam. This parameter is only used in the IDM model. By default, it is set to 2 m. 3.3.3 Qualitative Comparison of Mobility Generators Table 3.2 presents a summary of some of the most widely used vehicular mobility generators focusing on their main characteristics. We have grouped the comparison parameters into five different categories: (a) Software characteristics, (b) Map types, (c) Mobility models supported, (d) Traffic models implemented, and (e) Trace formats supported. As shown, Freesim exhibits good software characteristics but it is limited in other functions. VanetMobiSim, SUMO, CityMob, STRAW and C4R all have good software features and traffic model support. However, only VanetMobiSim provides excellent trace file support. C4R is excellent in software features, mobility, and traffic model support. Regarding map types and traces, C4R is clearly oriented to simulate real maps in the ns-2 simulator. Its most important feature is allowing to generate realistic mobility traces graphically (using real maps), easily (by means of the wizard), and quickly (in only a few minutes). 3.3.4 Quantitative Comparison of Mobility Generators To evaluate the realism and effectiveness of existing VANET mobility generators, we performed the simulation of a generic Warning Message Dissemination (WMD) protocol on ns-2 over SUMO, VanetMobiSim, and C4R traces. WMD protocols are useful when an accident occurs since they can help to prevent new accidents (by warning other vehicles about the accident), and alleviate congestion [MCC+09]. Figure 3.2 shows the simulated topology for the map layout, and Table 3.3 shows the simulation parameters used. As shown, C4R is the only mobility generator which includes the Downtown mobility model; it considers that there is an area where the density of vehicles is slightly higher (as the downtown in the cities usually presents higher traffic densities). SUMO and VanetMobiSim use the Krauss model, and the IDM with Lane Changes, respectively. The rest of parameters are the same for the three mobility generators. The performance metrics we measured include: (i) the percentage of vehicles receiving the warning messages, (ii) the warning notification time, which is the time required by vehicles to receive the warning messages, and (iii) the number of packets received per vehicle. Each simulation run lasted for 450 seconds. In order to achieve a stable state, we only collect data after the first 60 seconds. Since the performance results are highly related to the scenarios, and due to the 37 CHAPTER 3. A REALISTIC SIMULATION FRAMEWORK FOR VEHICULAR NETWORKS Table 3.2: A comparison of the studied mobility generators VanetMobiSim SUMO FreeSim CityMob STRAW C4R Opensource Console - GUI Available examples - Continuous development - Wizard Real User defined - Random Manhattan Voronoi Random WayPoint STRAW Manhattan Downtown Krauss model Wagner model Kerner IDM Multilane roads - Lane changing - Separate directional flows - Speed constraints Traffic signs - Intersections management - - Large road networks - - Collision free movement - - - Different vehicle types - Hierarchy of junction types - Route calculation Ns-2 trace support GloMoSim support Qualnet support SWANS support XML-based support 38 3.3. C4R: CITYMOB FOR ROADMAPS Figure 3.2: Simulated scenario of San Francisco, USA. Table 3.3: Parameters used for performance simulation of different VANET mobility generators VANET mobility generator SUMO VanetMobiSim C4R network simulator ns-2.31 number of vehicles 300 map area size 2000m×2000m downtown size - - 1000m×1000m downtown probability - - 0.6 number of warning mode vehicles 3 warning packet size 256B normal packet size 512B packets sent by nodes 1 per second warning message priority AC3 normal message priority AC1 MAC/PHY 802.11p maximum transmission range 400m mobility models Krauss IDM with Lane Changes Krauss and Downtown 39 CHAPTER 3. A REALISTIC SIMULATION FRAMEWORK FOR VEHICULAR NETWORKS 0 20 40 60 80 100 0 5 10 15 20 25 30 % of vehicles receiving the warning messages Warning notification time (s) C4R SUMO VanetMobiSim Figure 3.3: Cumulative histogram for the time evolution of disseminated warning messages using different mobility generators. random nature of the mobility models used, we repeated the simulations to obtain reasonable confidence intervals. As shown in Figure 3.3 and Table 3.4, the shortest warning notification time2is achieved when using C4R traces, followed by SUMO and VanetMobiSim. In terms of percentage of vehicles informed, using C4R traces resulted in the largest percentage of vehicles receiving the warning messages. Finally, in terms of number of packets received, experiments using C4R show a higher packet delivery rate, being the lowest results achieved with SUMO. Results show that the effect of the Downtown concept included in our C4R mobility generator is crucial, since the higher density of vehicles, the easier becomes the warning message dissemination process. We consider that SUMO, and VanetMobiSim in particular, underestimate the performance of the WMD protocol in urban scenarios. Overall, our investigation shows that, when simulating the same WMD protocol with the same network simulator over different VANET mobility generators, different performance results may be obtained. 3.4 Limitations of the ns-2 simulator We now address the problem of improving the radio propagation models provided by one of the most used network simulator, i.e. the ns-2. In particular, we developed some improved models dealing with the 802.11p standard as well as the effect of obstacles in the radio signal propagation. 2The data presented for warning notification time, is the time needed to inform at least 40% of the vehicles. 40 3.4. LIMITATIONS OF THE NS-2 SIMULATOR Table 3.4: Performance of the WMD protocol under the different mobility generators Performance SUMO VMobiSim C4R Warning notification time (s) 0.80 1.90 0.50 % of vehicles informed 56.51 39.12 86.75 Number of packets received 309.03 685.73 1153.50 Ns-2 is a discrete event simulator targeted at networking research which has become a widely used tool to simulate the behavior of wired and wireless networks. When simulating radio signal transmission, we use a mathematical formulation of the radio wave propagation as a function of parameters such as distance between vehicles and radio frequency. This formulation is called Radio Propagation Model (RPM). The ns-2 simulator offers some RPMs to account for wireless signal strength. These models assume a flat surface, where the simulation environment contains no objects that could block the signal (mostly buildings in urban environments), and thereby they do not accurately simulate the radio propagation process in vehicular environments. The RPMs included in ns-2 v2.35 are: 1. Free Space model: The received power is only dependent on the transmitted power, the antenna gains, and on the distance between sender and receiver. Obstacles are not modeled. 2. Two-ray Ground (TRG) model: Assumes that the received signal energy is the sum of the direct line-of-sight path and the reflected path from the ground. It does not account for obstacles, and sender and receiver have to be on the same plane. 3. Rayleigh and the Ricean fading models: Both models describe the time-correlation of the received signal power. The Rayleigh model considers indirect paths between the sender and the receiver, while the Ricean fading model applies when there is one dominant path and multiple indirect signals. 4. Nakagami fading model: Signal reception power is determined using a probability distribution dependent on distance. Configuration parameters are used to simulate different levels of fading. This model can be interpreted as a generalization of the Rayleigh distribution. 5. Shadowing model: usually defined as a log-normal shadowing model, it consists of two parts: the first one is known as the path loss model, which predicts the mean received power at a distance din different environments, and the second one adopts a Gaussian random variable to reflect the variation of the received power at a certain distance. Although the latest version of ns-2 (version 2.35) provides some changes to include the 802.11p standard [CSEJ+07], existing RPMs found in ns-2 do not support obstacle modeling within the network. In fact, for the Free Space and 41 CHAPTER 3. A REALISTIC SIMULATION FRAMEWORK FOR VEHICULAR NETWORKS the Two-ray Ground models, only the power level is taken into account. Hence, determining whether a packet reaches its destination or not is a deterministic process. The other three models included are based on probabilistic distributions that do not use information about the specific scenario. Therefore, situations where two vehicles are in line-of-sight are handled exactly in the same way as situations where there are obstacles between them, which cannot be considered realistic. 3.5 Enhancements to the ns-2 simulator Our efforts to improve the realism of Vehicular Network (VN) simulations using ns-2 derived in two parts: (i) improving the models to represent the features of the 802.11p standard in terms of frequency, data rate, etc., and (ii) developing new Radio Propagation Models to model Packet Error Rate and fading due to obstacles in a realistic manner. 3.5.1 IEEE 802.11p MAC/PHY layers We modified the simulator to follow the upcoming WAVE standard closely. Achieving this requires extending the ns-2 simulator to implement the IEEE 802.11p. In terms of the physical layer, the data rate used for packet broadcasting was fixed at 6 Mbit/s, i.e., the maximum rate for broadcasting in 802.11p when using 20 MHz channels. The MAC layer is based on the IEEE 802.11e Enhanced Distributed Channel Access (EDCA) Quality of Service (QoS) extensions [WH03]. Therefore, application messages are categorized into different Access Categories (ACs), where AC0 has the lowest and AC3 the highest priority. The contention parameters used for the Control Channel (CCH) are shown in [Eic07]. Authors in [Eic07] and [CSEJ+07] use a theoretical maximum transmission range of 250 m for 802.11p in their experiments. However, our own real experimental results using 802.11a devices (which employs almost the same PHY layer as 802.11p, with extended sampling rate and clock rate) showed a maximum transmission range of 400 m in an obstacle-free environment, and also demonstrated the high impact of obstacles in radio signal propagation. Other published works regarding 802.11p-based real testbeds obtained very similar results [BLJL10, MBS+10, SEGD11]. Hence, we modified the PHY layer configuration used in ns-2 to represent this behavior. Table 3.5 contains part of the ns-2 Tcl configuration file that provides the IEEE 802.11p configuration parameters. 3.5.2 Enhanced Radio Propagation Models proposed for the ns-2 simulator We also modified the ns-2 simulator to include four additional RPMs that increase the level of realism in simulations, thereby allowing us to obtain more accurate and meaningful results. Three of these RPMs are designed to be used in synthetic Manhattan-style grid scenarios: (i) the Distance Attenuation Model (DAM), (ii) the Building Model (BM), and (iii) the Building and Distance Attenuation Model 42 3.5. ENHANCEMENTS TO THE NS-2 SIMULATOR Table 3.5: NS-2 Tcl file for the IEEE 802.11p #Configuration for 802.11p PHY layer Phy/WirelessPhy set CPThresh_ 10.0 Phy/WirelessPhy set CSThresh_ 1.559e-11 Phy/WirelessPhy set RXThresh_ 3.652e-10 Phy/WirelessPhy set Rb_ 2*e6 Phy/WirelessPhy set Pt_ 3.57382 ;# Maximum tx range = 400 meters Phy/WirelessPhy set freq_ 5.9e9 ;# 5.9 GHz Phy/WirelessPhy set L_ 1.0 Phy/WirelessPhy set bandwidth_ 54e6 #Configuration for 802.11p MAC layer (based on 802.11e MAC layer) Mac/802_11p set CWMin_ 15 Mac/802_11p set CWMax_ 1023 Mac/802_11p set SlotTime_ 0.000009 ;# 9 us Mac/802_11p set SIFS_ 0.000016 ;# 16 us Mac/802_11p set PreambleLength_ 96 ;# 96 bit Mac/802_11p set PLCPHeaderLength_ 40 ;# 40 bits Mac/802_11p set PLCPDataRate_ 6.0e6 ;# 6 Mbps Mac/802_11p set RTSThreshold_ 3000 ;# 3 Kbytes Mac/802_11p set ShortRetryLimit_ 7 ;# retransmissions Mac/802_11p set LongRetryLimit_ 4 ;# retransmissions Mac/802_11p set basicRate_ 6e6 ;# 6 Mbps Mac/802_11p set dataRate_ 6e6 43 CHAPTER 3. A REALISTIC SIMULATION FRAMEWORK FOR VEHICULAR NETWORKS (BDAM). The fourth one, the Real Attenuation and Visibility Model (RAV), is designed to be used in real map scenarios. 3.5.2.1 Distance Attenuation Model The Distance Attenuation Model (DAM) considers the impact of signal attenuation due to the distance between the vehicles on packet loss. To estimate such impact we relate the BER (bit error rate) or PER (packet error rate) to distance under specific channel conditions. It allows us to simplify calculations and thus significantly reduce simulation run-time. 3.5.2.2 Building Model The Building Model (BM) takes into consideration that, at a frequency of 5.9 GHz (i.e., the frequency band of the 802.11p standard), the signal is highly directional and will experience a very low depth of penetration. Hence, in most cases, buildings will absorb radio waves at this frequency, making communication only possible when the vehicles are in line-of-sight. Other previous works [BLJL10, MBS+10, SEGD11] also consider these premises. 3.5.2.3 Building and Distance Attenuation Model The Building and Distance Attenuation Model (BDAM) combines both DAM and BM models. Communication will only be possible, in most cases, when the received signal is strong enough and vehicles are within line-of-sight. BDAM can be considered more realistic than both DAM and BM, but it still has lack of realism since it is designed for Manhattan-based scenarios alone. The Real Attenuation and Visibility model, presented in the next subsection, solves this problem. 3.5.2.4 Real Attenuation and Visibility model for real roadmap scenarios A wireless signal propagation model can be characterized by: (a) attenuation schemes (signal power loss due to distance), and (b) visibility schemes (presence of obstacles interfering with signal propagation). The combination of these schemes makes up our Radio propagation model, called Realistic Attenuation and Visibility (RAV) model. Our model implements signal attenuation due to the distance between vehicles as closely to reality as possible. In general, ns-2 offers deterministic RPMs, i.e., the selected function determines the maximum distance a packet could reach. If the receiver is within this range, the packet will be successfully received; on the contrary, if the distance is greater, it will be lost. In order to increase realism, we use a probabilistic approach to model packet losses due to channel noise and other situations. We use a probability density function to determine the probability of a packet being successfully received at any given distance. 44 3.5. ENHANCEMENTS TO THE NS-2 SIMULATOR With respect to other attenuation schemes, such as Two-Ray Ground and Nakagami, our scheme, instead of being theoretical, is obtained directly from experimental data. Regarding visibility, the main objective that a realistic visibility scheme should accomplish is to determine if there are obstacles between the sender and the receiver which interfere with the radio signal. In most cases, when using the 5.9 GHz frequency band (used by the 802.11p standard), buildings absorb radio waves, and so communication is not possible. As previously mentioned, the Building and Distance Attenuation Model (BDAM) was designed to work in Manhattan-style grid layouts, where simple calculations were used to determine if two vehicles were in line-of-sight. RAV goes one step forward by adapting the algorithm to support more complex and realistic layouts. Given a real reference map containing the street layout, our proposal determines whether two different vehicles can communicate using the following strategy: •Two vehicles in the same street are always in line-of-sight. We consider that a vehicle is in a street (s) when the minimum distance (dmin) between its position (P(x, y)) and the line (r) formed as a extension of the street is less than a threshold (ths). •When a vehicle is at a junction (j), we consider that this vehicle may potentially communicate with all the vehicles present in the streets which start from the junction j, i.e., the vehicle is considered to be at all the neighbor streets simultaneously. A threshold distance (thj) is used to determine if a vehicle is close enough to a junction for this rule to apply. •Two vehicles in adjacent streets (labeled iand j) can communicate if the angular difference (α) between their streets is below a threshold tha. This property can be extended if there is a series of linked streets between vehicles, and, for every street in the chain, the angular difference with the rest of streets is less than tha. We consider this, since the electromagnetic waves forming the wireless signal can experience the effects of reflection, refraction and diffraction due to the presence of solid obstacles in urban scenarios. Hence, some situations where vehicles are not in line-of-sight can still result in effective communication between them. 3.5.3 Quantitative Comparison of the RPMs In this section, we evaluate the impact of some of the presented RPMs on the performance of a Warning Message Dissemination application, typically used in VANETs. Specifically, we compared the performance of TRG, Nakagami, and our RAV proposal. Our intention is to evaluate the effect that the different radio propagation schemes have over the network performance, and measure the differences appearing when we increase the level of realism of the simulations. Results in Figure 3.4 are obtained using a real map from San Francisco as the simulation topology (see Figure 3.2). As shown, when using TRG and Nakagami 45 CHAPTER 3. A REALISTIC SIMULATION FRAMEWORK FOR VEHICULAR NETWORKS 0 20 40 60 80 100 0 5 10 15 20 25 30 % of vehicles receiving the warning messages Warning notification time (s) Two-Ray Ground (w/o obstacles) Nakagami (w/o obstacles) RAV Two-Ray Ground (w/ obstacles) Nakagami (w/ obstacles) Figure 3.4: Warning notification time when varying the attenuation scheme. RPMs, and when obstacles are not accounted for (as in the majority of VANET simulators), information reaches more vehicles (98.26% and 94.37%, respectively). However, the same models only achieved 63.24% and 55.37% of the vehicles being informed when the effect of obstacles in signal transmission is considered. Our RAV model, although accounting for the effect of obstacles, still considers that 86.75% of the vehicles are aware of the dangerous situation. Table 3.6 presents a summary of the average performance results obtained when simulating the different attenuation schemes. As shown, the effect of obstacles can also be observed in the warning notification time, since the protocol requires more time to warn the same percentage of vehicles (e.g. TRG and Nakagami required much more time to inform 40% of the vehicles when accounting for the presence of obstacles). Regarding the number of packets received per vehicle, when ignoring obstacles, TRG considers that more messages are received compared to Nakagami. When obstacles are present, results show that RAV considers that vehicles receive more packets compared to the TRG and Nakagami RPMs since the maximum transmission range is higher and communication effectiveness improves. 3.6 Similar Simulation Tools In this section, we present some other similar VANET simulation tools. VERGILIUS [GSPG10] is a VANET simulation tool which uses the Tiger digital maps to generate highly tunable city-based scenarios for both SUMO and Corsim microscopicmobility simulators. In addition, the VERGILIUS propagation tool computes the attenuation-matrix using the city-block and road map information extracted from the Tiger digital map database by using the CORNER algorithm [GFPG10]. The 46 4.3. THE 2KFACTORIAL ANALYSIS different WSNs can cooperate in order to reduce the total energy consumption. Simulation results revealed that different densities and data collecting rates among WSNs, the routing algorithm, and the path loss exponent had a major impact in the establishment of cooperation. The initial assessment of the impact of these factors was made through a 2kfactorial experimental analysis. Perkins et al. [PHO02] studied and quantified the effects of various factors and their two-way interactions on the overall performance of MANETs. Using 2kfactorial experimental design, they isolated and quantified the effects of five factors: (i) node speed, (ii) pause-time, (iii) network size, (iv) number of traffic sources, and (v) type of routing. They evaluated the impact that these factors have over the throughput, routing overhead, and power consumption. In [PH02], they investigated the impact of some characteristics on the performance of TCP in MANETs. Moreover, a factorial design experiment was conducted to quantify the effects and interactions that node speed and node pause time have over the TCP throughput. Buchegger and Le Boudec [BLB02] proposed a protocol, called CONFIDANT, based on selective detection and isolation of misbehaving nodes. They presented a performance analysis of DSR fortified by CONFIDANT, and compared it to a regular defenseless DSR scheme. A 2kfactorial design was performed to find out which factors affect performance. McClary et al. [MSL08] designed a transport protocol that uses Artificial Neural Networks (ANNs) to adapt the audio transmission rate to changing conditions in a MANET. The response variables of throughput, end-to-end delay, and jitter were examined. Although the use of standard statistical approaches such as the 2kfactorial analysis is found in many other fields, it is not so frequently used in ad hoc network communications. Moreover, to the best of our knowledge, this sort of statistical analysis has not been used in VANET research. 4.3 The 2kfactorial analysis VANET simulations often involve large and heterogeneous scenarios. The number of possible factors and their values, or levels, can be very large. In this section, we will explain how the 2kfactorial analysis [Jai91] can be used to determine the most relevant factors that govern a system’s performance. The use of 2kfactorial is important for several reasons: (i) to reduce the overall number of simulations needed, (ii) to evaluate the relationship between different factors, and (iii) to reduce the amount of simulation time required. The basic approach of this method is based on selecting a set of kparameters and determining 2 extreme levels (tagged with −1 and 1). An experiment is run for all the 2kpossible combinations of the parameters. From each experiment, we can also extract the k 2two-factor interactions, the k 3three-factor interactions, and so on. For example, suppose that we have proposed a Warning Message Dissemination system, and that we want to study the impact of the density of vehicles (factor A) and the speed of these vehicles (factor B) in the warning notification time, i.e., the time required by normal vehicles to receive a warning message sent by a warning mode vehicle. 53 CHAPTER 4. IDENTIFYING THE KEY FACTORS AFFECTING WARNING MESSAGE DISSEMINATION IN VANETS Table 4.1: Experiments defined by a 22design Experiment A B y 1 -1 -1 y1 2 1 -1 y2 3 -1 1 y3 4 1 1 y4 Table 4.2: Example of results obtained in terms of warning notification time varying two factors Density of vehicles Speed 10 km/h Speed 80 km/h 25 veh./km21second 0.8seconds 150 veh./km20.5seconds 0.4seconds If we make a 22factorial analysis, we can find out the impact of each factor (density of vehicles and speed), and their combination, in the studied metric (warning notification time). Table 4.1 shows the different experiments defined by the 22design, and Table 4.2 shows the results obtained after the simulations. Let us define two variables xAand xBas presented in Equations 4.1 and 4.2: xA=−1 if density of vehicles = 25 1 if density of vehicles = 150(4.1) xB=−1 if speed = 10 km/h 1 if speed = 80 km/h(4.2) The warning notification time (y) can be regressed on xAand xBusing a non linear regression model of the form: y=q0+qAxA+qBxB+qABxAxB(4.3) Substituting the four observations in the model, we get the following four equations: 1 = q0−qA−qB+qAB (4.4) 0.5 = q0+qA−qB−qAB (4.5) 0.8 = q0−qA+qB+qAB (4.6) 0.4 = q0+qA+qB+qAB (4.7) 54 4.3. THE 2KFACTORIAL ANALYSIS Table 4.3: Sign table method of calculating the effects of the factors in a 22design I A B AB y 1 -1 -1 1 1 second 1 1 -1 -1 0.5seconds 1 -1 1 -1 0.8seconds 1 1 1 1 0.4seconds 2.7 -0.9 -0.3 0.1 Total 0.675 -0.225 -0.075 0.025 Total/4 These equations can be solved uniquely for the four unknowns. The regression equation is: y= 0.675 −0.225xA−0.075xB+ 0.025xAxB(4.8) The result is interpreted as follows: the mean warning notification time is 0.675 seconds, the effect of the density of vehicles is -0.225 seconds, the effect of the speed of the vehicles is -0.075 seconds, and the interaction between speed and density of vehicles accounts for 0.025 seconds. 4.3.1 Calculating the Effects of the Factors In a 2kfactorial analysis, by using the sign table method, we can get the results and detect variations which depend on the combination of factors. For a 22design, the effects can be computed easily by preparing a 4 ×4 sign matrix as shown in Table 4.3. The first column of the matrix is labeled I, and it consists of all 1’s. The next two columns, titled Aand B, contain basically all possible combinations of −1 and 1. The fourth column, labeled AB, is the product of the entries in columns Aand B. The four observations are listed in a column vector next to this matrix. The column vector is labeled yand consists of the results corresponding to the factor levels listed under columns Aand B. The next step is to multiply the entries in column Iby those in column yand put their sum under column I. The entries in column Aare now multiplied by those in column yand the sum is entered under column A. This operation of column multiplication is repeated for the remaining two columns of the matrix. The sums under each column are divided by 4 to give the corresponding coefficients of the regression model. The importance of a factor depends on the proportion of the metric total variation explained by the factor. The total variation of yis also known as Sum of Squares Total (SST), which can be calculated as follows: T otal variation of y =SST = 22 X i=1 (yi−y)2(4.9) where ydenotes the mean of the responses from all four experiments. For a 22 design, the variation can be divided into three parts: SST = 22q2 A+ 22q2 B+ 22q2 AB (4.10) 55 CHAPTER 4. IDENTIFYING THE KEY FACTORS AFFECTING WARNING MESSAGE DISSEMINATION IN VANETS These parts can be expressed as a fraction; for example: Fraction of variation explained by A =SSA SST =22q2 A SST (4.11) Hence, we can indicate the percentage of variation of each studied metric explained by each factor. The more percentage of variation, the more impact this factor has in the measured metric. In our example, we found that the density of vehicles accounts for 89.01% (i.e. 22·−0.2252 0.2275 ) of the total variation of the warning notification time, the speed of the vehicles accounts for 9.89% (i.e. 22·−0.0752 0.2275 ), and their combination accounts for the remaining 1.10% (i.e. 22·0.0252 0.2275 ). Therefore, in our selected example the density of vehicles is the most important factor which affects the warning notification time. The outcome of the 2kfactorial analysis allows us in sorting out factors in the order of impact. At the beginning of any performance study, the number of factors and their levels could usually be large. A full factorial design with such a large number of factors and levels may not be the best use of available effort. The first step should be to reduce the number of factors and to choose those factors that have a significant impact on performance. 4.4 Factors to Study in VANETs Some previous works have studied the most important factors in MANETs. Nevertheless, VANETs have special characteristics that make them different from MANETs. Hence, more research is required in order to identify the key factors that impact their performance. In this section we identify and describe the most important factors associated with VANET Warning Message Dissemination. 4.4.1 Number of Warning Vehicles In traffic safety applications, vehicles may send safety messages to other vehicles in order to prevent collisions or to ask for emergency services. We consider that vehicles may operate in warning or normal mode. Warning mode vehicles inform other vehicles about their abnormal status by sending warning messages periodically. Normal mode vehicles participate in the diffusion of these warning packets and, periodically, they also send beacons with information about themselves, such as their position and speed. This factor is important since the more vehicles in the warning mode are there in a scenario, the more network traffic there will be, thus increasing redundant rebroadcasts which provoke heavy contention and long-lasting collisions. 4.4.2 Density of Vehicles In VANETs, the density of vehicles can be particularly high, which usually causes that VANET simulations require quite a long time to finish. Moreover, many network simulators do not scale well, and so simulating VANETs with high density of vehicles consumes a significant amount of time and resources. 56 4.4. FACTORS TO STUDY IN VANETS As shown in previous works [MTC+09, MCC+09, MTC+11a], this factor seems to be important to measure Warning Message Dissemination performance in VANET scenarios. In fact, some authors have defined new compound factors derived from the density of vehicles (e.g. Jiang et al. [JCD07] defined the concept of communication density as the product of vehicle density, messaging rate and transmission range). 4.4.3 Channel Bandwidth In radio communications, bandwidth is the width of the frequency band used to transmit the data. Channel spacing is a term used in radio frequency planning that describes the frequency difference between adjacent allocations in a frequency plan. The 802.11p standard supports 10MHz and 20Mhz bandwidths. Using a 10Mhz bandwidth, the supported data rates are 3, 4.5, 6, 9, 12, 18, 24, and 27 Mbps, depending on the modulation and coding scheme considered. In vehicular safety communications the efficiency of channel usage is important in managing the broadcast transmissions. The efficient channel usage helps to reduce the overall interference level and in turn impacts on the broadcast reception performance [JCD08]. Since vehicular information delivery systems support applications such as cooperative driving among cars on the road, traffic safety, or infotainment applications, we think that channel bandwidth requirements could change based on the selected application. For the specific case of Warning Message Dissemination mechanisms, the overall capacity of the channel can affect the effectiveness of warning dissemination schemes if the density of potential transmitters is high. 4.4.4 Broadcast Scheme Another important factor in Warning Message Dissemination in VANETs is the selected broadcast scheme [LC12]. In VANETs, intermediate vehicles act as relays to support end-to-end vehicular communications. For applications such as route planning, traffic congestion control, and traffic safety, flooding of broadcast messages commonly occurs. However, flooding results in many redundant rebroadcasts, heavy channel contention, and long-lasting message collisions (usually known as the broadcast storm problem). Over the years, several schemes have been proposed to address the broadcast storm problem in wireless networks. In [TNCS02] we can find some of the most interesting approaches, which are the following: (i) the counter-based scheme, which uses a counter to keep track of the number of times the broadcast message is received in order to decide whether to inhibit the rebroadcast, (ii) the distance-based scheme, in which the relative distance between vehicles is used to decide whether to rebroadcast or not, (iii) the location-based scheme, which is very similar to the distance-based scheme, though requiring more precise locations for the broadcasting vehicles to achieve an accurate geometrical estimation of the additional coverage of a rebroadcast, and (iv) the cluster-based scheme, where vehicles are grouped in clusters, and only one member of each cluster (the cluster 57 CHAPTER 4. IDENTIFYING THE KEY FACTORS AFFECTING WARNING MESSAGE DISSEMINATION IN VANETS head) can rebroadcast the warning messages. The weighted p-persistence, the slotted 1-persistence, and the slotted p-persistence techniques presented in [WTP+07] are some of the few rebroadcast schemes proposed for VANETs. These three probabilistic and timer-based broadcast suppression techniques can mitigate the severity of the broadcast storms by allowing nodes with higher priority to access the channel as quickly as possible, but their ability to avoid storms is limited, since they are specifically designed for being used in highway scenarios. The Last One (TLO) scheme [SP08] tries to reduce the broadcast storm problem by finding the most distant vehicle from the warning message sender, so that this vehicle will be the only one allowed to retransmit the message. This scheme does not take into account the effect of obstacles (e.g., buildings) in urban radio signal propagation. More recently, we proposed a scheme called enhanced Street Broadcast Reduction (eSBR) [MFC+10a], which uses location and roadmap information to facilitate an efficient dissemination of warning messages in 802.11p-based VANETs. It is easily noticeable that most existing solutions to the broadcast storm problem were only evaluated in obstacle-free environments, which are not comparable to real urban scenarios where plenty of obstacles can interfere with the signal, creating blind areas where vehicles will not receive the warning message unless intermediate forwarding nodes help to overpass the obstacle. In our experiments we use both the location-based scheme and our eSBR scheme to assess the relevance of the broadcast scheme adopted. 4.4.5 Message Priority Wireless technologies such as the IEEE 802.11p Wireless Access for Vehicular Environment (WAVE) [Eic07] enable peer-to-peer mobile communication among vehicles (V2V) and communication between vehicles and the infrastructure (V2I), and are expected to be widely adopted by the car industry in the next years. The 802.11p MAC layer is based on the IEEE 802.11e Enhanced Distributed Channel Access (EDCA), and Quality of Service (QoS) extensions. Therefore, application messages are categorized into different Access Classes (ACs), where AC0 has the lowest and AC3 the highest priority. In our experiments, warning messages (which contain information about abnormal situations such as accidents) have always the highest priority (AC3) at the MAC layer, while beacons (containing information such as vehicles’ positions and speeds), which are not propagated by other vehicles, change their priority from the lowest (AC0) to the highest (AC3) priority in the 2kfactorial analysis. 4.4.6 Message Periodicity As mentioned previously, warning mode vehicles inform other vehicles about their status by sending warning messages periodically. Normal mode vehicles participate in the diffusion of these warning packets and, moreover, they also send periodic beacons with information such as their positions, speed, etc. Similarly to the number of warning vehicles, the more warning messages are sent at the same time, the more redundant rebroadcasts, channel contention, and 58 4.4. FACTORS TO STUDY IN VANETS message collisions there will be. Thus, message periodicity seems to be an important factor that offers a trade-off between performance and overhead. 4.4.7 Mobility Model One of the challenges posed by the study of VANETs is the definition of a vehicular mobility model [AZ12] providing an accurate and realistic vehicular mobility description at both macroscopic and microscopic levels [HFB09]. To perform realistic simulations, it is especially important that the chosen mobility generator is able to obtain a detailed microscopic traffic simulation by importing network topologies from real maps. Our mobility simulations are performed with SUMO [KR07], an open source traffic simulation package which has interesting microscopic traffic capabilities such as: collision free vehicle movement, multi-lane streets with lane changing, junction-based right-of-way rules, traffic lights, etc. SUMO can also import roadmaps directly from map databases such as OpenStreetMap [osm09] and TIGER [tig09]. Our mobility simulations account for areas with different vehicle densities. In a real town, traffic is not uniformly distributed; there are downtowns or points of interest that may attract vehicles. Hence, we include the ideas presented in the Downtown Model [MCCM08] to add points of attraction in realistic roadmaps. To generate the movements for the simulated vehicles, we used two different mobility models available in SUMO: (i) the Krauss mobility model [KWG97] with some modifications to allow multi-lane behavior [KHRW02], and (ii) the Wagner mobility model [Wag06]. The Krauss model is based on collision avoidance among vehicles by adjusting the speed of a vehicle to the speed of its predecessor using the following formula: v(t+ 1) = v1(t) + g(t)−v1(t)τ τ+ 1 +η(t),(4.12) where vrepresents the speed of the vehicle in m/s,trepresents the period of time in seconds, v1is the speed of the leading vehicle in m/s,gis the gap to the leading vehicle in meters, τis the driver’s reaction time (set to 1 second in our simulations) and ηis a random numeric variable with a value between 0 and 1. The Wagner model, unlike most driving models which assume an instantaneous or even delayed reaction of the driver to the surrounding situation, considers two important features of human driving and of human actions in general. Firstly, humans usually plan ahead, and secondly, the type of control that humans apply is not continuous, but discrete in time: they act only at certain moments in time. These specific moments are known as action-points. 4.4.8 Radio Propagation Model We observe that the most widely used simulators, such as ns-2, Glomosim, QualNet and OPNET do not include a Radio Propagation Model (RPM) that offers enough accuracy for vehicular environments [MTC+09]. In particular, the physical obstacles present in urban environments (mostly buildings) are not taken into account, which is overly optimistic. For example, the commonly used Two Ray 59 CHAPTER 4. IDENTIFYING THE KEY FACTORS AFFECTING WARNING MESSAGE DISSEMINATION IN VANETS Figure 4.1: RAV visibility scheme: example scenario. Ground (TRG) radio propagation model ignores effects such as Radio Frequency (RF) attenuation due to buildings and other obstacles, meaning that an alternative model must be introduced. However, for 802.11p-based VANETs, the received signal will largely depend on both the distance between the sender and the receiver, and the presence of obstacles. In the 2kfactorial analysis, we use both the well-known deterministic TRG and the probabilistic Real Attenuation and Visibility Model (RAV) [MFC+10b], a realistic RPM specifically designed for IEEE 802.11p-based VANETs that increases the level of realism of phenomena occurring at the physical layer, thereby allowing researchers to obtain more accurate and meaningful results [MTC+09]. Figure 4.1 shows an example of the visibility scheme used in RAV, where vehicle (A) is trying to disseminate a message. In that case, and assuming that any vehicle receiving a message will rebroadcast it the first time, the result will be that some vehicles (B, C, D, F, G, and I) receive the message, while the others (E, H, and J) will never be reached by such message. 4.4.9 Roadmap The roadmap (road topology) is an important factor accounting for mobility in simulations, since the topology constrains cars’ movements. Roughly described, an urban topology is a graph where vertices and edges represent, respectively, junction and road elements. Simulated road topologies can be generated ad hoc by users, randomly by applications, or obtained from real roadmap databases. Using complex layouts implies more computational time, but the results obtained are closer to the real ones [MFC+10a]. Typical simulation topologies used are 60 4.5. SIMULATION RESULTS highway scenarios (the simplest layout, without junctions) and Manhattan-style street grids (with streets arranged orthogonally). These approaches are simple and easy to implement in a simulator. However, layouts obtained from real urban scenarios are rarely used, although they should be chosen to ensure that the results obtained are likely to be similar in realistic environments. Our simulation scenarios used in the 2kfactorial analysis are based on two different real roadmaps, which were obtained from real cities using OpenStreetMap. The two locations represent environments with different street densities and average street lengths. The chosen scenarios were the South part of the Manhattan Island from the city of New York (USA), and the area located at the North of the Colosseum in the city of Rome (Italy). The fragments selected have an extension of 4 km2(2 km ×2 km). Figure 4.2 depicts the street layouts used. As shown, the fragment from New York presents the longest streets, arranged in a Manhattangrid style. The city of Rome represents the opposite situation, with short streets in a highly irregular layout. The third fragment was extracted from the city of San Francisco, and the results of its simulation are presented in Section 4.5.4. 4.5 Simulation Results Simulation results presented in this chapter were obtained using the ns-2 simulator [FV00]. We modified the simulator to follow the upcoming WAVE standard closely1, extending it to implement IEEE 802.11p [IEE10]. Mobility is performed with CityMob for Roadmaps (C4R) [FGM+12b], a mobility generator which can import maps directly from OpenStreetMap. In our study, each simulation lasted for 120 seconds. In order to achieve a stable state before gathering data traffic, we only started to collect data after the first 60 seconds. All results represent an average over thirty executions with different random scenarios, presenting all of them a maximum error of 10% with a degree of confidence of 90%. We evaluated the following performance metrics: (i) the warning notification time, (ii) the percentage of blind vehicles, and (iii) the number of packets received per vehicle. The warning notification time is the time required by normal vehicles to receive a warning message sent by a warning mode vehicle. The percentage of blind vehicles is the percentage of vehicles that does not receive the warning messages sent by the warning mode vehicles. These vehicles can remain blind because of their positions, due to collisions, or due to signal propagation limitations. Table 4.4 shows the parameters used for the simulations. The downtown probability and the downtown attraction are the probability that a vehicle is within the downtown, and the probability that a vehicle travels into the downtown area, respectively. 4.5.1 Results of the 2kFactorial Analysis In this section, we use the 2kfactorial analysis [Jai91] to determine the most relevant factors that govern Warning Message Dissemination performance. We 1All these improvements and modifications of the simulator are publicly available at http://www.grc.upv.es/software/ 61 CHAPTER 4. IDENTIFYING THE KEY FACTORS AFFECTING WARNING MESSAGE DISSEMINATION IN VANETS (a) (b) (c) Figure 4.2: Scenarios used in our simulations as street graphs in SUMO: (a) fragment of the city of New York (USA), (b) fragment of the city of Rome (Italy), and (c) fragment of the city of San Francisco. 62 4.5. SIMULATION RESULTS 100 vehicles after 20s 0 0.4 0.8 1.2 1.6 Scenario width (km) 0 0.4 0.8 1.2 1.6 Scenario length (km) 0 1 2 3 4 5 Warning messages received (a) 400 vehicles after 20s 0 0.4 0.8 1.2 1.6 Scenario width (km) 0 0.4 0.8 1.2 1.6 Scenario length (km) 0 1 2 3 4 5 Warning messages received (b) Figure 4.6: Evolution of the warning message dissemination process in the Rome scenario after 20 seconds, when simulating (a) 100 and (b) 400 vehicles. Table 4.9: Main features of the selected maps Selected city map New York (USA) San Francisco (USA) Rome (Italy) Streets/km2175 428 695 Junctions/km2125 205 298 Avg. street length 122.55m72.71m45.89m Avg. lanes/street 1.57 1.17 1.06 69 CHAPTER 4. IDENTIFYING THE KEY FACTORS AFFECTING WARNING MESSAGE DISSEMINATION IN VANETS 0 20 40 60 80 100 0 5 10 15 20 % of vehicles receiving the warning messages Warning notification time (s) New York San Francisco Rome Figure 4.7: Warning notification time when varying the roadmap. priority is AC0, the broadcast scheme applied is eSBR, and the channel bandwidth is 6 Mbps. As shown, the warning notification time is lower when simulating the New York map (see Figure 4.7). Information reaches about 60% of the vehicles in less than 0.8 seconds, and propagation is completed in 5 seconds. When simulating the map of San Francisco, information needs more time (1.4 seconds) to reach the same percentage of vehicles. As for Rome, the propagation process was completed in only 2.4 seconds, but less than 40% of the vehicles are informed. The behavior in terms of percentage of blind vehicles and the number of packets received also highly depends on this factor (see Table 4.10). In fact, when simulating New York, the percentage of blind vehicles is almost negligible, while we find 60.92% of blind vehicles when simulating Rome. So, when the simulated layout is more complex, the percentage of blind vehicles increases, and more time is needed to reach the same percentage of vehicles. This occurs mainly because the signal propagation is blocked by buildings. Moreover, the average number of packets received per vehicle highly differs depending on the map. Compared to New York, the number of packets received decreases considerably for San Francisco and even more for Rome since signal propagation encounters more restrictions. Figure 4.8 shows the number of warning messages received in each area when simulating New York, San Francisco, and Rome, respectively. As mentioned before, when simulating the New York scenario the dissemination process is able to reach a wider area since streets are longer and wider, and there are fewer junctions, so messages can be disseminated more easily. 70 4.5. SIMULATION RESULTS New York after 20s 0 0.4 0.8 1.2 1.6 Scenario width (km) 0 0.4 0.8 1.2 1.6 Scenario length (km) 0 1 2 3 4 5 Messages received (a) San Francisco after 20s 0 0.4 0.8 1.2 1.6 Scenario width (km) 0 0.4 0.8 1.2 1.6 Scenario length (km) 0 1 2 3 4 5 Messages received (b) Rome after 20s 0 0.4 0.8 1.2 1.6 Scenario width (km) 0 0.4 0.8 1.2 1.6 Scenario length (km) 0 1 2 3 4 5 Messages received (c) Figure 4.8: Evolution of the warning message dissemination process after 20 seconds, when simulating (a) New York, (b) San Francisco, and (c) Rome scenarios. 71 CHAPTER 4. IDENTIFYING THE KEY FACTORS AFFECTING WARNING MESSAGE DISSEMINATION IN VANETS Table 4.10: Blind vehicles and packets received per vehicle when varying the roadmap Roadmap % of blind vehicles packets received New York 2.92% 1542.07 San Francisco 20.55% 885.13 Rome 60.92% 229.07 4.5.5 Lessons Learnt and Guidelines for Future Research The 2kfactorial analysis has shown that the key factors to take into account when simulating VANETs are: (i) the radio propagation model, (ii) the density of vehicles, and (iii) the roadmap used. By evaluating the impact of each factor one by one, we confirmed the outcome of the 2kfactorial analysis. We observed that the results obtained are highly affected by the selected radio propagation model, the roadmap and the density of vehicles. The propagation of warning messages works better with simpler layouts and higher vehicle densities. Results also showed that other important factors, such as the broadcast scheme used, the channel bandwidth, and the priority and the periodicity of messages, have little impact in the warning message delivery process. Nevertheless, we believe that these parameters could be important factors in other VANET scenarios and applications, such as live video streaming services to vehicles. 4.6 Summary In this chapter, we identified and described the different factors to be taken into account when simulating VANETs. Since the number of possible factors can be very large, we identified the representative factors by using the 2kfactorial analysis. The purpose is to reduce the required simulation time in future research works. The key factors affecting the delivery of warning messages were found to be the radio propagation model, the density of vehicles, and the roadmap used. Some other factors, such as the broadcast scheme used, the channel bandwidth, and the priority and the periodicity of messages, did not have a significant impact on the metrics considered in our study. We believe that the results of our analysis can save researchers’ time by discarding unnecessary factors when performing simulations for VANET-related research. Results obtained from our simulations confirmed that the selected roadmap is a crucial factor. In fact, performance parameters such as warning notification time, the percentage of blind vehicles, and the number of packets received per vehicle highly depend on it. To further reduce the scope of warning message dissemination tests made in real cities, we consider that researchers must carefully determine the scenarios to assess their proposals, ideally picking several scenarios with different street layout to validate their proposals. 72 Chapter 5 Improving message dissemination in Vehicular Networks In traffic safety applications for Vehicular Networks (VNs), some warning messages have to be urgently disseminated in order to increase the number of vehicles receiving the traffic warning information. In those cases, redundancy, contention, and packet collisions due to simultaneous forwarding (usually known as the broadcast storm problem) are prone to occur. In the past, several approaches have been proposed to solve the broadcast storm problem in multi-hop wireless networks such as Mobile ad hoc Networks (MANETs). Among them we can find counter-based, distance-based, locationbased, cluster-based, and probabilistic schemes, which have been mainly tested in non-realistic simulation environments. In this chapter, we present the enhanced Message Dissemination based on Roadmaps (eMDR), a novel scheme specially designed to increase the percentage of informed vehicles and reduce the notification time; at the same time, it mitigates the broadcast storm problem in real urban scenarios. We evaluate the impact that our scheme has on performance when applied to VANET scenarios based on real city maps, and the results show that it outperforms previous schemes in all situations. 5.1 Introduction Many possible applications, ranging from inter-vehicle communication and file sharing, to obtaining real-time traffic information (such as jams and blocked streets), can benefit of the use of VANETs. In this chapter, we focus on traffic safety and efficient warning message dissemination applications, where the objective is to reduce the latency and to increase the accuracy of the information received by nearby vehicles when a dangerous situation occurs, e.g., an accident, a traffic jam, etc. In dense wireless vehicular environments (e.g., urban scenarios), an accident may cause many vehicles to send warning messages, and using a simple blind 73 CHAPTER 5. IMPROVING MESSAGE DISSEMINATION IN VEHICULAR NETWORKS broadcast protocol will cause all vehicles within the transmission range, receiving the broadcast transmissions, to rebroadcast those messages. Hence, a broadcast storm [TNCS02] may occur and any useful algorithm for information dissemination should incorporate mechanisms to avoid redundancy, contention and massive packet collisions due to simultaneous forwarding. In the past, several schemes have been proposed to avoid or alleviate the broadcast storm problem. However, they have been specifically proposed for MANETs and have only been validated using simple scenarios such as a highway (several lanes, without junctions) [SP08, SPC09], or a Manhattan-style grid scenario [KEOO04]. In this work, we propose a novel scheme called enhanced Message Dissemination based on Roadmaps (eMDR), which uses location and street map information to facilitate an efficient dissemination of warning messages in 802.11p [Tas06] based VANETs. We evaluate the performance of our eMDR proposal in a realistic urban scenario, that is, obtained from real maps of existing cities, and demonstrate how our approach could benefit drivers on the road. This chapter is organized as follows: Section 5.2 reviews the related work on the broadcast storm problem in wireless ad hoc networks and delay-tolerant strategies proposed to improve message dissemination in intermittently connected networks. Section 5.3 describes our eMDR scheme and details its functionality using a real map scenario; for the sake of clarity, we also provide a formal definition of our proposal using set theory. Section 5.4 presents the simulation environment. Simulation results are then discussed in Section 5.5. Finally, Section 5.6 concludes this chapter. 5.2 Related Work 5.2.1 On the broadcast storm problem in wireless networks In VANETs, intermediate vehicles act as message relays to support end-to-end vehicular communications. For applications such as route planning, traffic congestion control, and traffic safety, the flooding of broadcast messages might be considered a straightforward approach to achieve a wide-spread dissemination. However, if flooding is done blindly, broadcast storms may arise, with several disadvantages to the dissemination process [TNCS02]: •Many redundant rebroadcasts: a physical location may be covered by the transmission ranges of several hosts, making subsequent rebroadcasts unnecessary. •Heavy channel contention: in dense networks, after a vehicle broadcasts a message and many of its neighbors decide to rebroadcast it, these transmissions will contend with each other since all neighbors are located near the sender. •Long-lasting message collisions: in a CSMA/CA network (like the one studied), not using specific collision detection mechanisms causes collisions to be more likely to occur and cause more damage. 74 5.2. RELATED WORK Over the years, several schemes have been proposed to address the broadcast storm problem in wireless networks. In [TNCS02] we can find some of the most interesting approaches, which are the following: 1. The Counter-based scheme. To mitigate broadcast storms, this scheme uses a threshold Cand a counter cto keep track of the number of times the broadcast message is received. Whenever c≥C, rebroadcast is inhibited. 2. The Distance-based scheme. In this scheme, authors use the relative distance dbetween vehicles to decide whether to rebroadcast a message or not. It is demonstrated that, when the distance dbetween two vehicles is short, the additional coverage (AC) of the new rebroadcast is lower, and so rebroadcasting the warning message is not recommended. If dis larger, the additional coverage will also be larger. 3. The Location-based scheme is similar to the distance-based scheme, though requiring more precise locations for the broadcasting vehicles to achieve an accurate geometrical estimation (with convex polygons) of the AC of a warning message. Since vehicles usually have GPS systems on-board, it is possible to estimate the additional coverage more precisely. The main drawback of this scheme is the high computational cost of calculating the AC, which is related to calculating many intersection areas among several circles. Note that all these previous schemes alleviate the broadcast storm problem by inhibiting certain vehicles from rebroadcasting, reducing message redundancy, channel contention, and message collisions. In particular, they inhibit vehicles from rebroadcasting when the additional coverage (AC) area is very low. Overall, [TNCS02] demonstrated that a rebroadcast can only provide up to 61% additional coverage over that area already covered by the previous transmission in the best case (on average, the additional area is of 41%). Additional efforts to find efficient solutions to the broadcast storm problem can be found in the following works: 1. The weighted p-persistence, the slotted 1-persistence, and the slotted p-persistence techniques presented in [WTP+07] are some of the few rebroadcast schemes proposed for VANETs. These three probabilistic and timer-based broadcast suppression techniques can mitigate the severity of the broadcast storms by allowing nodes with higher priority to access the channel as quickly as possible, but their ability to avoid storms is limited. These schemes are specifically designed for use in highway scenarios. 2. The Last One (TLO) scheme [SP08] tries to reduce the broadcast storm problem by finding the most distant vehicle from the warning message sender, so that this vehicle will be the only one allowed to retransmit the message. This method uses GPS information from the sender vehicle and the possible receivers to calculate the distance. Although it brings a better performance than simple broadcast, this scheme is only effective in a highway scenario because it does not take into account the effect of obstacles (e.g., buildings) 75 CHAPTER 5. IMPROVING MESSAGE DISSEMINATION IN VEHICULAR NETWORKS in urban radio signal propagation. Moreover, the scheme does not clearly state how a node knows the position of nearby vehicles at any given time. 3. The TLO scheme was extended using a protocol named Adaptive Probability Alert Protocol (APAL), which uses adaptive wait-windows and adaptive probability to transmit [SPC09]. This scheme shows even better performance than the TLO scheme, but it is also only validated in highway scenarios. 4. A stochastic broadcast scheme is proposed by [SM10] to achieve an anonymous and scalable protocol where relay nodes rebroadcast messages according to a retransmission probability. The performance of the system depends on the vehicle density, and the probabilities must be tuned to adapt to different scenarios. However, the authors only test this scheme in an obstacle-free environment, thus not considering urban scenarios where the presence of buildings could interfere with the radio signal. 5. The Cross Layer Broadcast Protocol (CLBP) [BCSZ10] uses a metric based on channel condition, geographical locations and velocities of vehicles to select an appropriate relaying vehicle. This scheme also supports reliable transmissions exchanging Broadcast Request To Send (BRTS) and Broadcast Clear To Send (BCTS) frames. CLBP reduces the transmission delay but it is only conceived for single-direction environments (like highway scenarios), and its performance in urban environments has not been tested. It is easily noticeable that most existing solutions to the broadcast storm problem were only evaluated in obstacle-free environments, which are not comparable to real urban scenarios where plenty of obstacles can interfere with the signal, creating blind areas where vehicles will not receive the warning message unless intermediate forwarding nodes help to overpass the obstacle. This effect is shown in Figure 5.1, which includes an example of wireless signal propagation in a real city scenario obtained from Google Maps. If vehicle Ais trying to broadcast a warning message, a basic radio propagation model will consider that all vehicles within its transmission range (vehicles Band C) would receive it. However, if we account for buildings as obstacles, there will be a blind area (dark area in the figure) that will impede vehicle Cfrom receiving the message if vehicle Bdecides not to rebroadcast it. The effect of obstacles in warning message dissemination has been addressed by other proposed schemes, specifically designed for information propagation in urban areas. Some of the most interesting pieces of work in this area are the following: 1. Costa et al. [CFMM06] presented an approach where a message propagation function encodes information about target areas and preferred routes for the message dissemination. Selecting different functions produces different routing protocols accounting for connected and disconnected situations between vehicles. These protocols show a remarkable performance in simple grid-like scenarios with low and high density of vehicles, but real maps are not used 76 5.2. RELATED WORK Figure 5.1: Example of wireless signal propagation in an urban scenario extracted from Google Maps. The lightest area represents the transmission range in a obstacle free environment, and the darkest area indicates the zone where the signal would not be propagated due to blocking by the nearby building. in their simulations. Moreover, this scheme requires to define target zones for the messages to obtain optimal results, which is not always possible. 2. The UV-CAST (Urban Vehicular broadCAST) protocol [VBT10] allows reducing the broadcast storm problem while solving disconnected network problems in urban VANETs. It defines a region of interest for each VANET application, and the propagation is adapted to maximize the number of informed vehicles in this region. Despite showing good results in a scenario obtained from the city of Pittsburgh, this scheme is not compared with other protocols that could produce similar results. In addition, the density of vehicles studied is relatively low and the authors do not study its performance when there are more than 50 vehicles/km2. 3. The RPB-MD protocol [LC12] is a message dissemination (MD) approach with a relative position based (RPB) addressing model that allows defining the intended receivers in the zone of relevance. Simulation results show high delivery ratio and low data overhead; however, the scenario used is a single bidirectional highway, and the Radio Propagation Model selected is the deterministic Two-Ray Ground. Hence, we consider that this proposal should be revised to ensure that results are comparable to real ones obtained from existing urban scenarios. 77 CHAPTER 5. IMPROVING MESSAGE DISSEMINATION IN VEHICULAR NETWORKS Overall we find that, even if the utility of these schemes is proven, none of them is designed to improve the dissemination and reduce the warning notification time by making use of the topology of the area where the propagation takes place, since they only use basic metrics such as the distance or the relative angles between vehicles. Our work includes additional knowledge about the roadmap to determine the optimal set of relaying vehicles. 5.2.2 VANETs as Delay-Tolerant Networks (DTN) The vehicles in a VANET are, typically, sparsely spread across the roadmap, forming time-varying clusters of nodes due to the distance between vehicles and the effect of building blocking the wireless signal. This environment is subject to disruption, disconnection and long delay. Hence, there is not always a complete path of forwarding nodes from the source to every possible destination. Hence, VANETs can be considered a Delay-Tolerant Network (DTN) where routes must be found over intermittently-connected hops. Routing strategies for DTNs can be divided into two main groups: flooding strategies and forwarding strategies. In the flooding family, each node delivers multiple copies of each message to other nodes, which act as relays, without using prior information about the network structure. [JW06] present some examples of these protocols, such as Direct Contact (data transmitted in one hop), Two-Hop Relay, and Tree-Based Flooding (more than two hops). In epidemic routing [VB00], all nodes will eventually receive all messages, obtaining a maximum delivery ratio at the cost of consuming network resources (channel, buffer, etc.) heavily. Algorithms in the forwarding family require to add some knowledge about the network that is used to select the best path from the source to the destination. The simplest approach is using a distance metric to estimate the cost of delivering messages between nodes (Location-Based Routing). Other more sophisticated schemes such as the Per-Hop Routing, where the forwarding decision is made by the intermediary node which determines the next hop, and the Per-Contact Routing, where the routing table is recomputed each time a contact is available, are presented in [JLW05]. Again, all the existing DTN schemes have been only tested in simple scenarios, where all the nodes are in line-of-sight, and the decision whether to transmit a message or not is taken only based solely on the presence of other nodes, not on the specific layout. Including information about the scenario could help at improving the warning dissemination process, especially when integrated maps are available in the vehicles. In addition, the amount of resources needed to implement these strategies are not necessary in our proposal, since it does not store any message in queues or buffers for future relays. Finally, our work is mainly focused on improving traffic safety by rapidly informing as many vehicles as possible. A high delay between the time when a dangerous situation takes place and its notification time makes the system become useless; thus, typical delay-tolerant schemes do not fulfill our requirements. 78 5.4. SIMULATION ENVIRONMENT is a draft amendment to the IEEE 802.11 standard that defines enhancements to support Intelligent Transportation Systems (ITS) applications. In terms of the physical layer, the data rate used for packet broadcasting was fixed at 6 Mbit/s, i.e., the maximum rate for broadcasting in 802.11p when assuming a 20 MHz channel. The MAC layer is based on the IEEE 802.11e Enhanced Distributed Channel Access (EDCA) Quality of Service (QoS) extensions. Therefore, application messages are categorized into different Access Categories (ACs), where AC0 has the lowest, and AC3 the highest priority. The contention parameters used for the Control Channel (CCH) are shown in [Eic07]. In our proposed eMDR scheme, warning messages have the highest priority (AC3) at the MAC layer, while beacons have lower priority (AC1). Moreover, since we are simulating real city maps with buildings, we have modified the ns-2 simulator to model the impact of distance and obstacles in signal propagation. The Radio Propagation Model selected was the Real Attenuation and Visibility Model (RAV) [MFC+10b], a model which proved to increase the level of realism in VANET simulations using real urban roadmaps as scenarios where buildings act as obstacles. RAV implements the signal attenuation due to the distance between vehicles based on real data obtained from experiments in different streets of the cities of Valencia and Teruel (Spain). The test were performed using D-Link DWL-AG132 [D-L11] wireless adapters, configured to use the IEEE 802.11a standard in the 5.9 GHz frequency band (the same band as 802.11p), obtaining a maximum transmission range of 400 meters. This model also accounts for the presence of buildings to determine if two vehicles are in line-of-sight, and otherwise the angular difference between the streets and the proximity to a junction are computed to approximate the effects of diffraction and reflection of the signal from the buildings. The RAV model is an improvement over models based on path loss with stochastic fading. RAV approximates the effects of diffraction and reflection on urban junctions by using thresholds associated to each junction, considering only the vehicles close to a junction as potential receivers. The vehicles in the scenarios are also potential obstacles for wireless signals if they are large enough to block the line of sight. Nevertheless, the RAV model does not include the impact that other vehicles in the road have on the signal propagation, since simulations become too computationally expensive. Moreover, the random traffic makes it harder to find representative scenarios when so many factors are taken into account. To perform realistic simulations, it is specially important that the chosen mobility generator could obtain a detailed microscopic traffic simulation importing network topologies from real maps. Our mobility simulations are performed with SUMO [KR07], an open source traffic simulation package which has microscopic traffic capabilities such as: collision free vehicle movement, multi-lane streets with lane changing, junction-based right-of-way rules and traffic lights. SUMO can also import maps directly from map databases such as [osm09] and [tig09]. Our simulation scenarios are based on three different roadmaps, which were obtained from real cities using OpenStreetMap. The three selected locations represent real scenarios having different streets densities and average street lengths. The chosen scenarios were the South part of the Manhattan Island from the city 85 CHAPTER 5. IMPROVING MESSAGE DISSEMINATION IN VEHICULAR NETWORKS (a) (b) (c) Figure 5.4: Scenarios used in our simulations as street graphs in SUMO: (a) fragment of the city of New York (USA), (b) fragment of the city of Madrid (Spain), and (c) fragment of the city of Rome (Italy). 86 5.5. SIMULATION RESULTS Table 5.1: Main features of the selected maps Selected city map New York (USA) Madrid (Spain) Rome (Italy) Total streets 700 1387 2780 Total junctions 500 715 1193 Avg. street length 122.54m83.08m45.88m Avg. lanes/street 1.57 1.27 1.06 of New York (USA), the area around Paseo de la Castellana in the city of Madrid (Spain), and the area located at the North of the Colosseum in the city of Rome (Italy). All the selected maps have an extension of 4 km2(2 km ×2 km). Figure 5.4 depicts the street layouts used in SUMO to represent the selected scenarios, and Table 5.1 includes the main features of the chosen areas of the cities. As we can see, the New York map presents the longest streets, arranged in a Manhattan-grid style. The city of Rome represents the opposite situation, with short streets in a highly irregular layout, and the city of Madrid shows an intermediate layout, with a medium density of streets in a less irregular arrangement compared to Rome. To generate the movements for the simulated vehicles, we used the Krauss mobility model [KWG97] available in SUMO with some modifications to allow multi-lane behavior [KHRW02]. This model is based on collision avoidance among vehicles by adjusting the speed of a vehicle to the speed of its predecessor using the following formula: v(t+ 1) = v1(t) + g(t)−v1(t)τ τ+ 1 +η(t),(5.6) where vrepresents the speed of the vehicle in m/s,trepresents the period of time in seconds, v1is the speed of the leading vehicle in m/s,gis the gap to the leading vehicle in meters, τis the driver’s reaction time (set to 1 second in our simulations) and ηis a random numeric variable with a value between 0 and 1. Our mobility simulations also account for areas with different vehicle densities. In a real town, traffic is not uniformly distributed; there are downtowns or points of interest that may attract vehicles. Hence, we include the ideas presented in the Downtown Model [MCCM08] to add points of attraction in realistic roadmaps. The simulated scenarios include a square area of 1 km2in the center of the map where the probability to attract vehicles is 50%. This means that about 50% of the vehicles will be moving around this area on average, while the other 50% will be spread over the remaining 3 km2area. 5.5 Simulation Results In this section, we perform a detailed analysis to evaluate the impact of the proposed eMDR scheme on the overall system performance. Since performance results highly depend on the selected scenarios, and due to the random nature of the mobility model, we performed thirty simulations to obtain reasonable confidence intervals. All the results shown here have a 90% confidence interval. Each 87 CHAPTER 5. IMPROVING MESSAGE DISSEMINATION IN VEHICULAR NETWORKS Table 5.2: Parameter values for the simulations Parameter Value number of vehicles 100,200,300,400 map area size 2000m×2000m number of warning mode vehicles 3 warning packet size 256bytes normal packet size 512bytes interval between consecutive messages 2 seconds warning message priority AC3 normal message priority AC1 MAC/PHY 802.11p Radio Propagation Model RAV maximum transmission range 400m eMDR distance threshold (D) 200m simulation lasted for 450 seconds, and in order to achieve a stable state, we only started to collect data after the first 60 seconds. We evaluated the following performance metrics: (a) percentage of vehicles informed, (b) warning notification time, (c) number of packets received per vehicle, and (d) reception overhead. The percentage of vehicles informed is the percentage of vehicles receiving the warning messages sent by warning mode vehicles. The warning notification time is the time required by normal vehicles to receive a warning message sent by a warning mode vehicle (a vehicle that broadcasts warning messages). The reception overhead measures the average number of duplicate warning messages received at any vehicle. Table 5.2 shows the simulation parameters used. For comparison purposes, we evaluated the performance of our eMDR proposed scheme with respect to several existing proposals. We chose a location-based scheme and a distance-based scheme from [TNCS02], which are proven to provide reasonable performance in obstacle-free environments, but their results on urban environments were not tested by the authors. From [CFMM06], we selected the Function Driven Probabilistic Diffusion (FDPD) algorithm, a probabilistic scheme that uses the distance between sender and receiver to determine the forwarding vehicles and reduce the broadcast storm problem. Finally, we also compared our approach with respect to the more recent UV-CAST algorithm [VBT10], especially designed for disconnected networks but with the additional cost of using more memory structures to implement a Store-Carry-Forward (SCF) approach. Despite some of these schemes were designed for urban environments, none of them use the information of the topology map to improve message dissemination, like our proposed eMDR algorithm. In our study, we also vary the density of vehicles ranging from 100 vehicles (25 vehicles/km2) to 400 vehicles (100 vehicles/km2). The impact of other parameters affecting warning message dissemination, such as the density of vehicles and the priority and periodicity of messages, was previously studied in [MCCM09]. 88 5.5. SIMULATION RESULTS 0 20 40 60 80 100 0 5 10 15 20 25 30 % of vehicles receiving the warning messages Warning notification time (s) eMDR FDPD UV-CAST distance location (a) 0 20 40 60 80 100 0 5 10 15 20 25 30 % of vehicles receiving the warning messages Warning notification time (s) eMDR FDPD UV-CAST distance location (b) 0 20 40 60 80 100 0 5 10 15 20 25 30 % of vehicles receiving the warning messages Warning notification time (s) eMDR FDPD UV-CAST distance location (c) Figure 5.5: Average notification time and percentage of vehicles informed obtained when simulating 200 vehicles and varying the simulation scenario: (a) New York, (b) Madrid, and (c) Rome. 5.5.1 Warning notification time and percentage of vehicles informed Figure 5.5 shows the impact that the selected scenario has over the warning notification time (vehicle density is 50 vehicles/km2). The first noticeable conclusion about the results is that our proposed eMDR scheme outperforms the other four dissemination schemes in terms of both percentage of vehicles informed and warning notification time. In addition, when the eMDR scheme is used we obtain more stable results. Tseng et al. [TNCS02] demonstrated that the location-based scheme was more efficient than the distance-based scheme, since it reduces redundancy without compromising the number of vehicles receiving the warning message. The main drawback of using the location-based scheme is the high computational cost involved in evaluating the additional coverage. However, although its effectiveness is proved in obstacle-free environments, our simulations show that the location-based scheme is too restrictive in urban scenarios. Many of the vehicles which could rebroadcast the message to reach new streets of the roadmap 89 CHAPTER 5. IMPROVING MESSAGE DISSEMINATION IN VEHICULAR NETWORKS will in fact refrain from doing so in most cases. The UV-CAST algorithm obtains similar results to the location-based dissemination, increasing at the same time the computational complexity and the amount of memory required. The FDPD scheme is the closest one to our eMDR in terms of warning notification time, although it is not able to outperform our proposal in any of the tested scenarios. Another important effect that may be observed is that the percentage of vehicles informed is highly dependent on the specific selected scenario. In scenarios with long streets arranged orthogonally, like New York, our proposal is able to inform more than 95% of the vehicles, while in scenarios with high density of short streets only about 70% of vehicles can be informed. Using the eMDR scheme notably increases the percentage of vehicles informed, presenting a similar behavior in all scenarios where eMDR allows informing at any moment of time about 10-15% more vehicles compared to the distance-based scheme, and about 15-20% compared to the location-based and UV-CAST algorithms. The message propagation speed is also higher for eMDR, mainly during the first seconds of the dissemination process. Figure 5.6 evaluates the impact that the network density has on the performance metrics. We vary the vehicle density from 100 to 400 vehicles, and the selected scenario is Rome. The trend is similar independently of the vehicle density, i.e., by using eMDR there is a higher number of informed vehicles, while the location-based and the UV-CAST schemes are not able to find suitable rebroadcast nodes in the selected environment. As the number of vehicles in the scenario grows, the advantage of our eMDR scheme remains evident, and so the warning notification time is reduced while the percentage of informed vehicles increases. When we select 300 vehicles, the location-based, distance-based, and UV-CAST algorithms need about 10 seconds on average to reach 60% of the simulated vehicles, the FDPD scheme requires more than 7 seconds, and the eMDR scheme only needs 6 seconds. If the number of vehicles raises to 400, it takes 4 seconds for the location-based, distance-based, and UV-CAST schemes to inform 60% of vehicles, whereas eMDR and FDPD are able to reach the same percentage in only 2.5 seconds. 5.5.2 Messages received per vehicle The results achieved in terms of number of messages (including beacons) received per vehicle appear in Figure 5.7. As shown, scenarios like New York, with long streets arranged in a regular way, are prone to increase the number of messages received, mainly when the vehicle density is high since many of the vehicles in the roadmap are in line-of-sight. The differences between the five schemes are not very remarkable in this scenario when the vehicle density is not very high, with 5-10% more messages received using eMDR compared to the distance-based and UV-CAST schemes, and about 10-15% compared to the location-based scheme. The number of messages received using the eMDR scheme slightly increases due to the higher probability for a vehicle to rebroadcast a message when they are close to a junction. However, these vehicles are forwarding nodes since they are the most suitable ones to increase the percentage of informed vehicles, reducing the warning notification time without notably increasing the number of messages. 90 5.5. SIMULATION RESULTS 0 20 40 60 80 100 0 5 10 15 20 25 30 % of vehicles receiving the warning messages Warning notification time (s) eMDR FDPD UV-CAST distance location (a) 0 20 40 60 80 100 0 5 10 15 20 25 30 % of vehicles receiving the warning messages Warning notification time (s) eMDR FDPD UV-CAST distance location (b) 0 20 40 60 80 100 0 5 10 15 20 25 30 % of vehicles receiving the warning messages Warning notification time (s) eMDR FDPD UV-CAST distance location (c) 0 20 40 60 80 100 0 5 10 15 20 25 30 % of vehicles receiving the warning messages Warning notification time (s) eMDR FDPD UV-CAST distance location (d) Figure 5.6: Average notification time and percentage of vehicles informed obtained in the Rome scenario and simulating: (a) 100 vehicles, (b) 200 vehicles, (c) 300 vehicles, and (d) 400 vehicles. 91 CHAPTER 5. IMPROVING MESSAGE DISSEMINATION IN VEHICULAR NETWORKS 0 500 1000 1500 2000 2500 3000 3500 400 vehicles 300 vehicles 200 vehicles 100 vehicles Total number of packets received per vehicle location distance FDPD UV-CAST eMDR (a) 0 500 1000 1500 2000 2500 3000 3500 400 vehicles 300 vehicles 200 vehicles 100 vehicles Total number of packets received per vehicle location distance FDPD UV-CAST eMDR (b) 0 500 1000 1500 2000 2500 3000 3500 400 vehicles 300 vehicles 200 vehicles 100 vehicles Total number of packets received per vehicle location distance FDPD UV-CAST eMDR (c) Figure 5.7: Average number of messages received per vehicle in the different scenarios: (a) New York, (b) Madrid, and (c) Rome. 92 5.5. SIMULATION RESULTS The FDPD algorithm introduces the highest amount of messages in the system, (up to 25% more messages than eMDR) increasing the risk of broadcast storms. When Simulating scenarios like Madrid, the number of messages is reduced by 20-40% in all cases, and the decrement is even more noticeable in the Rome scenario where the dissemination process only produces less than half of the messages obtained in the New York scenario. The reduction of the number of messages also decreases the differences between the five schemes, and thus the eMDR scheme is specially suitable in environments with medium and high density of streets, where the amount of messages received is low and a slight increase of the number of messages is not likely to produce broadcast storms. These results also lead to a significant conclusion: our proposed eMDR scheme is specially suitable for situations where the density of vehicles is not too high, mostly due to its ability to inform as many vehicles as possible without notably increasing the number of messages. This situation is likely to occur during the first steps of the mass implantation of wireless devices in vehicles, when the market penetration rate will be low, and only a reduced number of vehicles will be able to communicate with each other. 5.5.3 Reception overhead The reception overhead is a measure of the average number of duplicate messages received by any vehicle involved in our simulations. This metric is useful to determine if a protocol can effectively solve or mitigate the broadcast storm problem. Duplicate messages also represent an ineffective use of the channel bandwidth, so they must be avoided whenever possible. We include both warning messages and control beacons in our results. Figure 5.8 shows the reception overhead measured for the different tested dissemination algorithms in a scenario with 200 vehicles (50 vehicles/km2). As can be seen, the obtained results are again highly dependent on selected roadmap: maps with long and regular streets (e.g., New York) are prone to produce broadcast storm problems even in situations with low density of vehicles, thus producing a higher level of reception overhead. Irregular scenarios like Rome reduce the number of duplicate messages received by the vehicles since the wireless signal finds more obstacles during its propagation. Concerning the dissemination algorithms, the FDPD scheme obtains the worst results in all simulated scenarios, and the differences increase in maps like New York. As previously shown, this algorithm presented the closest results to eMDR in terms of warning notification time. However, Figure 5.8 demonstrates that the FDPD scheme provokes a noticeable increase in the number of duplicate messages present in the network. The schemes that reduce the reception overhead in a higher degree are the location-based and the UV-CAST algorithms. Our proposed eMDR algorithm produces more reception overhead than these schemes, but this is only noticeable in the New York roadmap (where the increase is about 15%), whereas the differences are almost negligible in the other scenarios. Therefore, the eMDR scheme introduces little overhead compared to other more restrictive schemes, which is compensated by the improvement in terms of warning notification time and vehicles informed. 93 CHAPTER 5. IMPROVING MESSAGE DISSEMINATION IN VEHICULAR NETWORKS 0 5 10 15 20 25 20 30 40 50 60 70 80 90 100 Reception overhead (msg./veh.) Density of vehicles (veh./km2) eMDR FDPD UV-CAST distance location (a) 0 5 10 15 20 25 20 30 40 50 60 70 80 90 100 Reception overhead (msg./veh.) Density of vehicles (veh./km2) eMDR FDPD UV-CAST distance location (b) 0 5 10 15 20 25 20 30 40 50 60 70 80 90 100 Reception overhead (msg./veh.) Density of vehicles (veh./km2) eMDR FDPD UV-CAST distance location (c) Figure 5.8: Average reception overhead in the different scenarios: (a) New York, (b) Madrid, and (c) Rome. 94 5.5. SIMULATION RESULTS Location-based scheme after 5s 0 0.4 0.8 1.2 1.6 Scenario width (km) 0 0.4 0.8 1.2 1.6 Scenario length (km) 0 5 10 15 20 25 30 Messages received (a) Location-based scheme after 15s 0 0.4 0.8 1.2 1.6 Scenario width (km) 0 0.4 0.8 1.2 1.6 Scenario length (m) 0 5 10 15 20 25 30 Messages received (b) Figure 5.13: Evolution of the warning message dissemination process in the Madrid scenario simulating 400 vehicles and using a location-based scheme after (a) 5 seconds and (b) 15 seconds. location-based and distance-based schemes when the density of nodes is high become less significant after the initial period of the simulation. However, the eMDR scheme works more efficiently from the beginning of the dissemination process, and thus this effect could be interesting to spread critical messages to neighbor vehicles as soon as possible without the risk of generating broadcast storms. 5.5.7 Overall result analysis Our obtained results show how our proposed eMDR is able to outperform other existing dissemination schemes in different scenarios and under different vehicle densities. The closest approach to eMDR, in terms of warning notification time, is FDPD; however, the amount of messages generated using this algorithm is far greater than those generated with eMDR, increasing the probability of channel contention. The rest of studied algorithms are more restrictive than eMDR, reducing the dissemination efficiency especially in low vehicle density scenarios, since eMDR selects more appropriate forwarding nodes. The eMDR scheme uses GPS information in the selection of forwarding nodes, but we showed how it supports positioning errors of up to 25 meters without relevant performance degradation. Background traffic also affects the performance of the dissemination process, since additional traffic generated by other simultaneous applications will slow down the propagation of warning messages and it will increase the percentage of blind nodes. The eMDR outperforms the other selected schemes for traffic up to 1 MB/s produced per vehicle, although higher amounts of traffic benefit more restrictive schemes. 101 CHAPTER 5. IMPROVING MESSAGE DISSEMINATION IN VEHICULAR NETWORKS Difference between location-based and distance-based schemes after 5s 0 0.4 0.8 1.2 1.6 Scenario width (km) 0 0.4 0.8 1.2 1.6 Scenario length (km) -4 -2 0 2 4 Diff. on messages received (a) Difference between location-based and distance-based schemes after 15s 0 0.4 0.8 1.2 1.6 Scenario width (km) 0 0.4 0.8 1.2 1.6 Scenario length (km) -4 -2 0 2 4 Diff. on messages received (b) Difference between location-based and eMDR schemes after 5s 0 0.4 0.8 1.2 1.6 Scenario width (km) 0 0.4 0.8 1.2 1.6 Scenario length (km) -4 -2 0 2 4 Diff. on messages received (c) Difference between location-based and eMDR schemes after 15s 0 0.4 0.8 1.2 1.6 Scenario width (km) 0 0.4 0.8 1.2 1.6 Scenario length (km) -4 -2 0 2 4 Diff. on messages received (d) Figure 5.14: Differences in number of messages with respect to the location-based scheme simulating 400 vehicles in the Madrid scenario; using a distance-based scheme after (a) 5 seconds and (b) 15 seconds, and our proposed eMDR after (c) 5 seconds and (d) 15 seconds. 102 5.6. SUMMARY 5.6 Summary Achieving efficient message dissemination is of utmost importance in vehicular networks to warn drivers about critical road conditions. However, the broadcasting of warning messages in VANETs can result in increased channel contention and packet collisions due to simultaneous message transmissions. In this chapter, we introduce the enhanced Message Dissemination based on Roadmaps (eMDR) scheme to improve the performance of the warning message dissemination process in real map urban scenarios. Simulation results show that eMDR outperforms other schemes in all scenarios, yielding a higher percentage of vehicles informed, and a reduced warning notification time while not introducing broadcast storm problems; thus, we consider it suitable for real scenarios. We find that using scenarios with different values for the density of streets and junctions, or average street length, may affect notably the results in terms of informed vehicles and messages received per vehicle. Roadmaps with irregular, short streets need a higher vehicle density for the dissemination to be effective, while using nearly orthogonal topology scenarios provides good results with very low vehicle densities. Hence, the dissemination system could be tuned to use a more or less restrictive broadcast scheme, depending on the features of the current scenario, to maximize performance. The proposed eMDR scheme is specially suitable in situations where there are few vehicles able to forward messages, which can be due to either the low vehicle density or the low market penetration rate of wireless devices. Thus, the eMDR scheme may be successfully used during the first steps of the mass implantation of 802.11p compliant devices on vehicles. Moreover, by studying the time evolution of the message propagation process, we find that our proposal can be useful to transmit critical messages that should be spread out as soon as possible; in particular, we show that eMDR clearly outperforms all the studied proposals, i.e., the distance-based and location-based schemes, the Function Driven Probabilistic Diffusion algorithm, and the UV-CAST protocol in terms of warning notification time and percentage of informed vehicles, while exhibiting a reduced overhead. 103 Chapter 6 Enhancing Warning Message Dissemination in VANETs through roadmap profiling In recent years, new applications, architectures and technologies have been proposed for Vehicular Ad hoc Networks (VANETs). Regarding traffic safety applications for VANETs, warning messages have to be quickly and smartly disseminated in order to reduce the required dissemination time and to increase the number of vehicles receiving the traffic warning information. In the past, several approaches have been proposed to improve the alert dissemination process in multi-hop wireless networks, but none of them was tested in real urban scenarios, adapting its behavior to the propagation features of the scenario. In this chapter, we present the Profile-driven Adaptive Warning Dissemination Scheme (PAWDS) designed to improve the warning message dissemination process. With respect to previous proposals, our proposed scheme uses a mapping technique based on adapting the dissemination strategy according to both the characteristics of the street area where the vehicles are moving, and the density of vehicles in the target scenario. Our algorithm reported a noticeable improvement in the performance of alert dissemination processes in scenarios based on real city maps. 6.1 Introduction In the last chapter, we proved how the roadmap can be used to improve warning message dissemination by an adequate selection of forwarding nodes, which allows a faster notification of the warning messages while maintaining a low amount of traffic generated, thus minimizing broadcast storms. However, the proposed eMDR scheme is only designed to select nodes independently of the features of the street map. A step forward efficient dissemination would also use the shape and configuration of the roadmap to adapt the dissemination scheme. Results in Chapter 4 showed how the roadmap was one of the most influential factors affecting the performance of a warning message dissemination scheme in an urban scenario. Therefore, adapting to the specific environment where the vehicles 105 CHAPTER 6. ENHANCING WARNING MESSAGE DISSEMINATION IN VANETS THROUGH ROADMAP PROFILING are located can be beneficial in order to reduce broadcast storm related problems, and also to increase the efficiency of the warning message dissemination process. Existing adaptive techniques for VANETs only make use of the vehicle density to adapt the process; however, this information in not enough in many situations to determine the most effective configuration. In this chapter we propose PAWDS, aProfile-driven Adaptive Warning Dissemination System that dynamically modifies some of the key parameters of the propagation process, such as the interval between notifications and the selected broadcast scheme, to achieve an optimal performance depending on the features of the roadmap in which the propagation takes place. Our proposal is combined with the enhanced Street Broadcast Reduction (eSBR) [MFC+10a], to improve performance when the dissemination process takes places in real urban scenarios where the signal can be seriously affected by nearby buildings. The rest of the chapter is organized as follows: Section 6.2 reviews the related work on the broadcast storm problem and adaptive schemes in VANETs. Section 6.3 justifies the importance of the specific roadmap in VANET simulations and shows a classification of real urban environments depending on their density of streets and junctions. Section 6.4 presents our proposed adaptive scheme. Section 6.5 shows the simulation environment used to validate our proposal. Section 6.6 presents and discusses the obtained results. Finally, Section 6.7 concludes this chapter. 6.2 Related Work Not much research can be found in the literature about adaptive schemes for message dissemination in VANETs. In Chapter 5, we cited some of the most representative techniques for message dissemination and broadcast storm reduction. All these approaches are mainly static, and they do not use the information about the environment to increase the efficiency of the process. However, there are some remarkable attempts to adapt the dissemination strategy depending on the conditions of the environment. Mariyasagayam et al. [MML09] proposed an adaptive forwarding mechanism to improve message dissemination in VANETs. Vehicles compute the density of neighbor nodes to calculate a forwarding sector in which vehicles are not allowed to rebroadcast the message. The Adaptive-ADHOC (A-ADHOC) protocol [MRLL09] uses a variable frame length to increase channel utilization and to reduce response time. Another adaptive algorithm is the Junction-based Adaptive Reactive Routing (JARR) [TL09], a reactive position-based routing protocol that estimates the vehicle density of the available paths to be taken to send a message, also accounting for the direction and speed of traveling nodes in order to choose the optimal path. Existing VANET adaptive systems only consider features related to the vehicles in the scenario such as density, speed and position to adapt the performance of the dissemination process. Moreover, most authors only evaluate their schemes using very simple scenarios and topologies that are not constrained by any obstacles, and where all the vehicles are in line-of-sight with each other. Unlike our proposal, 106 6.3. CITY PROFILE CLASSIFICATION these scenarios are not realistic enough to conclude that the proposed protocols and schemes could work efficiently in real VANET scenarios. 6.3 City profile classification In previous works, we identified the most representative factors to be taken into account in VANET simulation using the 2kfactorial analysis [FGM+11b]. We showed that the roadmap, which serves as scenario for the warning dissemination, has an important influence in the effectiveness of the process. So, next we demonstrate the impact that the roadmap will have over the performance of dissemination processes in VANETs. 6.3.1 Importance of the roadmap in VANET simulation The roadmap (road topology) is an important factor accounting for mobility in simulations, since the topology constrains cars’ movements. Roughly described, an urban topology is a graph where vertices and edges represent, respectively, junction and road elements. Simulated road topologies can be generated ad hoc by users, randomly by applications, or obtained from real roadmap databases. Using complex layouts implies more computational time, but the results obtained are closer to the real ones. Typical simulation topologies used are highway scenarios (the simplest layout, without junctions) and Manhattan-style street grids (with streets arranged orthogonally). These approaches are simple and easy to implement in a simulator. However, layouts obtained from real urban scenarios are rarely used, although they should be chosen to ensure that the results obtained are likely to be similar in realistic environments. To prove how the results in VANET simulations depends on the chosen scenarios, we selected three different roadmaps from real cities using OpenStreetMap [osm09], representing environments with different street densities and average street lengths. The chosen scenarios were the South part of the Manhattan Island from the city of New York (USA), the streets around Market Street in the city of San Francisco (USA), and the area located at the North of the Colosseum in the city of Rome (Italy). The fragments selected have an extension of 4 km2 (2 km ×2 km). Figure 6.1 depicts the street layouts used, and Table 6.1 includes the main features of the chosen fragments of the cities. As shown, the fragment from New York presents the longest streets, arranged in a Manhattan-grid style. The city of Rome represents the opposite situation, with short streets in a highly irregular layout. The city of San Francisco shows an intermediate layout between these two in terms of regularity and average street length. We also consider the presence of open areas, such as gardens, squares, etc., to ensure that simulations produce realistic results for each individual roadmap even if not all the space between streets is filled with buildings. We simulate the three selected scenarios using the same configuration: 200 vehicles are simulated, there are 3 warning mode vehicles, the radio propagation model used is RAV [MFC+10b], the channel bandwidth is 6 Mbps, warning mode vehicles send 1 message per second, the broadcast scheme applied is eSBR [MFC+10a], and vehicles follow the Krauss mobility model [KWG97] (further information about 107 CHAPTER 6. ENHANCING WARNING MESSAGE DISSEMINATION IN VANETS THROUGH ROADMAP PROFILING (a) (b) (c) Figure 6.1: Scenarios used in prior simulations as street graphs in SUMO: (a) fragment of the city of New York (USA), (b) fragment of the city of San Francisco (USA), and (c) fragment of the city of Rome (Italy). 108 6.3. CITY PROFILE CLASSIFICATION Table 6.1: Main features of the selected maps Selected city map New York (USA) San Francisco (USA) Rome (Italy) Streets/km2175 428 695 Junctions/km2125 205 298 Avg. street length 122.55m72.71m45.89m Avg. lanes/street 1.57 1.17 1.06 0 20 40 60 80 100 0 5 10 15 20 % of vehicles receiving the warning messages Warning notification time (s) New York San Francisco Rome Figure 6.2: Warning notification time when varying the roadmap under the same simulation configuration. our simulation parameters can be found in Section 6.5). Figure 6.2 shows that the warning notification time is lower when simulating the New York map. Information reaches about 60% of the vehicles in less than 0.8 seconds, and propagation is completed in 5 seconds. When simulating the map of San Francisco, information needs more time (1.4 seconds) to reach the same percentage of vehicles. As for Rome, the propagation process was completed in only 2.4 seconds, but less than 40% of the vehicles are informed. The behavior in terms of percentage of blind vehicles, i.e., not receiving warning messages, and the number of packets received also highly depends on this factor (see Table 6.2). In fact, when simulating New York, the percentage of blind vehicles is almost negligible, while we find 60.92% of blind vehicles when simulating Rome. So, when the simulated layout is more complex, the percentage of blind vehicles increases, and more time is needed to reach the same percentage of vehicles. This occurs mainly because the signal propagation is blocked by buildings. Moreover, the average number of packets received per vehicle highly differs depending on the city map. Compared to New York, the number of packets received decreases 109 CHAPTER 6. ENHANCING WARNING MESSAGE DISSEMINATION IN VANETS THROUGH ROADMAP PROFILING Table 6.2: Blind vehicles and packets received per vehicle when varying the roadmap Roadmap % of blind vehicles packets received New York 2.92% 1542.07 San Francisco 20.55% 885.13 Rome 60.92% 229.07 considerably for San Francisco and even more for Rome since signal propagation encounters more restrictions. Figure 6.3 shows the number of warning messages received in each area when simulating New York, San Francisco, and Rome, respectively. As mentioned before, when simulating the New York scenario the dissemination process is able to reach a wider area since streets are longer and wider, and there are fewer junctions, so messages can be disseminated more easily. 6.3.2 Roadmap layout clustering We can easily deduce from the previously presented results that the selected topology has a great influence on the obtained results in a VANET simulation. Hence, aiming at using the specific features of the scenarios to improve performance, a wide set of maps from several existing cities have been tested to obtain a classification that allows warning dissemination to dynamically adapt its parameters based on the scenario type. The chosen area tries to represent the overall layout of the streets in each city, and is usually taken from the downtown area. We selected cities from Europe (Berlin, Lisbon, London, Milan, Moscow, Munich, Paris, Rome, Seville, Teruel, Valencia), Asia (Beijing, Hong Kong, Istanbul, Kuala Lumpur, New Delhi, Seoul, Shanghai, Taipei, Tokyo), North America (Boston, Chicago, Los Angeles, Manhattan, Mexico City, New York, San Francisco, Washington DC), South America (Bogot´a, Buenos Aires, Montevideo, Rio de Janeiro), and Africa (Cape Town, Casablanca, Cairo, Kinshasa, Rabat). Figure 6.4 shows the number of streets and junctions present in a 4 km2square area in these cities. As shown, the relationship between the number of streets and the number of junctions is almost linear, in an approximate ratio of 2 streets per junction. Since three different groups of cities can be distinguished in the figure, the well-known k-means clustering algorithm [Mac67] was used with a number of clusters k= 3 to obtain a precise classification of the cities. By using the results of the clustering process in Figure 6.4, we can classify a new city according to the cluster whose centroid is the nearest (using the Euclidean distance as a measure). We can classify existing cities by their street profiles into: •Simple layouts: maps with low density of streets and junctions that are usually arranged orthogonally like a Manhattan style grid. Examples of these cities are New York (USA), Rio de Janeiro (Brazil) and Seoul (South Korea). 110 6.5. SIMULATION ENVIRONMENT extremely high density of streets and junctions, and therefore it belongs to the Complex topologies cluster. We will study warning message dissemination efficiency in these scenarios and we will compare the results with those obtained with the formerly presented roadmaps. Simulations to test our experiments were done using the ns-2 simulator [FV00], modified to include the IEEE 802.11p [IEE10] standard so as to follow the upcoming WAVE standard closely. In terms of the physical layer, the data rate used for packet broadcasting is of 6 Mbit/s, as this is the maximum rate for broadcasting in 802.11p. The MAC layer was also extended to include four different priorities for channel access. Therefore, application messages are categorized into four different Access Categories (ACs), where AC0 has the lowest and AC3 the highest priority. The simulator was also modified to make use of our Real Attenuation and Visibility (RAV) scheme [MFC+10b], which proved to increase the level of realism in VANET simulations using real urban roadmaps in presence of obstacles. In order to mitigate the broadcast storm problem, our simulations use: (a) the counterbased scheme [TNCS02], (b) the distance-based scheme [TNCS02], and (c) the enhanced Street Broadcast Reduction (eSBR) scheme [MFC+10a], which employs a minimum distance under which vehicles are refrained from forwarding, except if they are close enough to a junction. With regard to data traffic, vehicles operate in two modes: (a) warning mode, and (b) normal mode. Warning mode vehicles inform other vehicles about their status by sending warning messages periodically with the highest priority at the MAC layer; each vehicle is only allowed to propagate them once for each sequence number. Normal mode vehicles enable the diffusion of these warning packets and, periodically, they also send beacons with information such as their positions, speed, etc. These periodic messages have lower priority than warning messages and are not propagated by other vehicles. Mobility is performed with CityMob for Roadmaps (C4R)1, a mobility generator which can import maps directly from OpenStreetMap. C4R is based on SUMO [KR07], an open source traffic simulation package. Our mobility simulations account for areas with different vehicle densities. In a realistic town setting, traffic is not uniformly distributed; there are downtowns or points of interest that may attract vehicles. Hence, we include the ideas presented in the Downtown Model [MCCM09] to add points of attraction in roadmaps. Hence, we include points of attraction in the roadmaps used in our simulations. To generate the movements for the simulated vehicles, we used the Krauss mobility model [KWG97] (with some modifications to allow multi-lane behavior [KHRW02]) found in SUMO. The Krauss model is based on collision avoidance among vehicles by adjusting the speed of a vehicle to the speed of its predecessor using the following formula: v(t+ 1) = v1(t) + g(t)−v1(t)τ τ+ 1 +η(t),(6.1) where vrepresents the speed of the vehicle in m/s,trepresents the period of time in seconds, v1is the speed of the leading vehicle in m/s,gis the gap to the 1C4R is available at http://www.grc.upv.es/software/ 117 CHAPTER 6. ENHANCING WARNING MESSAGE DISSEMINATION IN VANETS THROUGH ROADMAP PROFILING Table 6.6: Parameter Values Used for the Simulations Parameter Value number of vehicles 100,400 simulated area 2000m×2000m number of warning mode vehicles 3 warning message size 256B normal message size 512B warning message priority AC3 normal message priority AC1 MAC/PHY 802.11p maximum transmission range 400m mobility generator C4R mobility models Krauss [KHRW02] and Downtown model [MCCM09] maximum speed of vehicles 23 m/s ≈83 km/h maximum acceleration of vehicles 1.4m/s2 maximum deceleration of vehicles 2.0m/s2 driver reaction time (τ) 1 s leading vehicle in meters, τis the driver’s reaction time (set to 1 second in our simulations) and ηis a random numeric variable with a value between 0 and 1. All results represent an average over several executions with different random scenarios, presenting all of them a degree of confidence of 90%. Each simulation run lasted for 450 seconds, and we only collect data after the first 60 seconds in order to achieve a stable state. We are interested in the following performance metrics: (a) warning notification time, (b) percentage of blind vehicles, and (c) number of packets received per vehicle. The warning notification time is the time required by normal vehicles to receive a warning message sent by a warning mode vehicle. The percentage of blind vehicles is the percentage of vehicles that do not receive the warning messages sent by warning mode vehicles. The number of packets received per vehicle (including beacons and warning messages) gives an estimation of channel contention. Table 6.6 summarizes the parameter values used in our simulations. 6.6 Simulation Results In this section, we first present the impact of the roadmap and vehicle density in warning message dissemination performance and, afterwards, we evaluate and demonstrate the benefits of using our proposed adaptive scheme. 6.6.1 Evaluating the Impact of the Roadmap and Vehicle Density Results in this section are obtained using the maps of New York, San Francisco and Rome from Figure 6.1, and also the roadmaps from Los Angeles, Madrid and London from Figure 6.5. There is a city from each defined cluster in these two sets of roadmaps, and we will compare warning message dissemination using these different topologies. Figures 6.6 and 6.7 show the differences in terms of both 118 6.6. SIMULATION RESULTS warning notification time and messages received per vehicle when varying the density of vehicles in the aforementioned city scenarios. In all these simulations we used the same base configuration: 2 seconds between messages, 200 meters for minimum rebroadcast distance, and the broadcast scheme used was eSBR. Results in Figure 6.6 show that the selected scenario notably affects the efficiency of the dissemination process, especially in scenarios with low vehicle density. As the density of vehicles grows, the differences become smaller but they are still noticeable. In addition, roadmaps from the same cluster present a very similar behavior in both low and high vehicle density scenarios. Topologies from the Simple layout cluster obtains the best performance in warning notification time and percentage of blind vehicles in all scenarios, since the wireless signal propagates more easily in environments with few long streets. As the layout becomes more irregular and the density of streets and junctions grows, the dissemination process develops more slowly and the number of uninformed vehicles increases. In the six scenarios, increasing the density of vehicles yields better performance in terms of both warning notification time and percentage of blind vehicles (i.e. not receiving warning messages), especially in roadmaps like Rome and London where the streets are the shortest and the most irregular, producing very poor results when there are few vehicles in the simulated scenario. Complex layout scenarios need higher vehicle densities to obtain satisfactory results in terms of warning notification time and blind vehicles. As shown in Figure 6.7, topologies from the same cluster also produce a similar number of messages. For Simple roadmaps there is a sudden increment in the amout of received messages when the vehicle density grows more than 25 vehicles/km2, whereas Regular ones support up to 50 vehicles/km2and Complex roadmaps obtain sustainable results up to 75 vehicles/km2, with complete coherence with respect to Algorithm 3. Urban scenarios with low density of streets and junctions greatly increase the number of messages received per vehicle because of the higher number of vehicles reached by the wireless signal, thanks to the long streets forming the layout that make easier to find vehicles in line-of-sight. This substantial increment of the amount of produced messages could produce broadcast storms even in scenarios with relatively low presence of vehicles relaying warning messages. We conclude that, in these environments, the dissemination process should be tuned to use operation modes with low message generation rates. On the contrary, topologies with higher density of streets and junctions allow using less restrictive dissemination schemes since the number of messages received per node remains low even for high density scenarios, reducing the probability of broadcast storms. This is especially important in Complex roadmaps, where more vehicles are needed to increase dissemination efficacy and the Full dissemination mode could reduce this problem. To sum up, it is very important to reduce the amount of messages generated when the density of vehicles is high, but with low densities it is a good idea to produce enough messages to reach as many vehicles as possible, as the probability of broadcast storms becomes small. 119 CHAPTER 6. ENHANCING WARNING MESSAGE DISSEMINATION IN VANETS THROUGH ROADMAP PROFILING 0 20 40 60 80 100 0 5 10 15 20 % of vehicles receiving the warning messages Warning notification time (s) New York (Simple) Los Angeles (Simple) San Francisco (Regular) Madrid (Regular) Rome (Complex) London (Complex) (a) 0 20 40 60 80 100 0 5 10 15 20 % of vehicles receiving the warning messages Warning notification time (s) New York (Simple) Los Angeles (Simple) San Francisco (Regular) Madrid (Regular) Rome (Complex) London (Complex) (b) Figure 6.6: Warning notification time in different scenarios simulating (a) 100 vehicles (25 vehicles/km2) and (b) 400 vehicles (100 vehicles/km2). 120 6.6. SIMULATION RESULTS 0 500 1000 1500 2000 2500 Rome (Complex) San Francisco (Regular) New York (Simple) Total number of packets received per vehicle 100 vehicles 200 vehicles 300 vehicles 400 vehicles (a) 0 500 1000 1500 2000 2500 London (Complex) Madrid (Regular) Los Angeles (Simple) Total number of packets received per vehicle 100 vehicles 200 vehicles 300 vehicles 400 vehicles (b) Figure 6.7: Number of messages received per vehicle simulating (a) the formerly presented scenarios, and (b) the additional street maps, under different vehicle densities. 121 CHAPTER 6. ENHANCING WARNING MESSAGE DISSEMINATION IN VANETS THROUGH ROADMAP PROFILING Table 6.7: Average simulation results after 30 runs. The working modes selected by PAWDS are in boldface. Working Mode Map Veh. density Full diss. Standard diss. Reduced diss. Los Angeles (Simple profile) Low (25 veh./km2) WNT(50%): 1.93 s WNT(50%): 3.14 s WNT(50%): 4.81 s BV: 24.57% BV: 25.50% BV: 34.47% MR: 721.53 MR: 283.30 MR: 176.83 High (100 veh./km2) WNT(50%): 1.15 s WNT(50%): 2.86 s WNT(50%): 2.62 s BV: 1.60% BV: 1.87% BV: 1.97% MR: 2463.07 MR: 1083.07 MR: 715.43 Madrid (Regular profile) Low (25 veh./km2) WNT(30%): 1.37 s WNT(30%): 3.49 s WNT(30%): 6.36 s BV: 50.93% BV: 56.17% BV: 65.93% MR: 266.43 MR: 166.70 MR: 105.47 High (100 veh./km2) WNT(50%): 1.48 s WNT(50%): 3.29 s WNT(50%): 3.54 s BV: 22.62% BV: 23.24% BV: 33.00% MR: 1559.33 MR: 678.77 MR: 516.53 London (Complex profile) Low (25 veh./km2) WNT(15%): 1.36 s WNT(15%): 3.05 s WNT(15%): 5.93 s BV: 75.57% BV: 80.57% BV: 80.93% MR: 168.33 MR: 98.17 MR: 72.87 High (100 veh./km2) WNT(50%): 2.18 s WNT(50%): 4.47 s WNT(50%): 6.34 s BV: 32.77% BV: 33.13% BV: 44.23% MR: 873.17 MR: 387.60 MR: 229.03 6.6.2 Performance Testing In this subsection we show the result of a wide set of experiments whose goal is to prove the effectiveness of our proposed adaptive algorithm when disseminating warning messages. The proposed technique consists of determining the adequate selection of working modes in every possible situation. The maps used in this case are taken from the cities of Los Angeles, Madrid and London (Figure 6.5), representing Simple, Regular and Complex topologies, respectively. Figure 6.8 shows the warning notification time using the three configurations in diverse scenarios, and Figure 6.9 depicts the average number of messages received per vehicle. The different configurations are compared in Figure 6.8 with an ideal situation, representing a scenario with a perfect channel where there are no collisions between wireless messages. Comparing our working modes to this ideal situation allows determining whether the available resources are efficiently used to maximize performance. Focusing on Simple profile cities like Los Angeles, the Full dissemination mode produces a very high number of messages both in low and high vehicle density scenarios, thus being unsuitable for this environment. When the density of vehicles is low, the Reduced dissemination mode allows reducing the total amount of messages disseminated; however, the notification time and the percentage of blind vehicles is far greater than for the Standard dissemination mode, which is more balanced and more suitable for this situation. Thereby, this is the selected mode in low vehicle density scenarios. In high density scenarios, the differences in performance between these two modes diminish: the Standard mode only informs about 5% more vehicles, while the number of messages involved is reduced by a third part with the Reduced dissemination mode. This effect confirms its selection as the most suitable mode for this environment. In Regular cities (e.g. Madrid), the Reduced dissemination mode does not ob122 6.6. SIMULATION RESULTS 0 20 40 60 80 100 0 5 10 15 20 % of vehicles receiving the warning messages Warning notification time (s) Ideal Full diss. Standard diss. (PAWDS) Reduced diss. (a) 0 20 40 60 80 100 0 5 10 15 20 % of vehicles receiving the warning messages Warning notification time (s) Ideal Full diss. Standard diss. Reduced diss. (PAWDS) (b) 0 20 40 60 80 100 0 5 10 15 20 % of vehicles receiving the warning messages Warning notification time (s) Ideal Full diss. (PAWDS) Standard diss. Reduced diss. (c) 0 20 40 60 80 100 0 5 10 15 20 % of vehicles receiving the warning messages Warning notification time (s) Ideal Full diss. Standard diss. (PAWDS) Reduced diss. (d) 0 20 40 60 80 100 0 5 10 15 20 % of vehicles receiving the warning messages Warning notification time (s) Ideal Full diss. (PAWDS) Standard diss. Reduced diss. (e) 0 20 40 60 80 100 0 5 10 15 20 % of vehicles receiving the warning messages Warning notification time (s) Ideal Full diss. Standard diss. (PAWDS) Reduced diss. (f) Figure 6.8: Warning notification time with the different PAWDS working modes compared to an ideal dissemination scheme without collisions in different cities: Los Angeles with (a) 100 and (b) 400 vehicles, Madrid with (c) 100 and (d) 400 vehicles, and London with (e) 100 and (f) 400 vehicles. 123 CHAPTER 6. ENHANCING WARNING MESSAGE DISSEMINATION IN VANETS THROUGH ROADMAP PROFILING 0 500 1000 1500 2000 2500 London (Complex) Madrid (Regular) Los Angeles (Simple) Total number of packets received per vehicle Full diss. Standard diss. Reduced diss. (a) 0 500 1000 1500 2000 2500 London (Complex) Madrid (Regular) Los Angeles (Simple) Total number of packets received per vehicle Full perf. Standard perf. Reduced perf. (b) Figure 6.9: Number of messages received per vehicle with the different PAWDS working modes simulating (a) 100 and (b) 400 vehicles. 124 6.7. SUMMARY tain a good performance in terms of notification time and blind vehicles (about 30%-40% more blind nodes with respect to the rest of modes). In low vehicle density scenarios, using the Full dissemination mode yields a notable reduction of notification time and blind vehicles, without requiring a large amount of messages. Nevertheless, if the vehicular density is high, the number of messages grows excessively, and using the Standard dissemination mode allows reducing them by more than half with similar values for the percentage of blind nodes, and an affordable increment of the warning notification time. Hence, the most appropriate scheme would use the Full dissemination mode when there are few vehicles, and the Standard mode when their density increases. Finally, in Complex profile cities (e.g. London), the Full dissemination mode selected by the PAWDS algorithm clearly outperforms the rest of the modes in terms of blind vehicles and warning notification time when only 100 vehicles are involved. In addition, the number of messages received is not very high (below 200 messages per vehicle), meaning that this mode would indeed be suitable for this environment. When the number of vehicles increases to 400, the Reduced dissemination mode remains unsuitable as it slows down the dissemination process and increases the percentage of blind nodes with respect to the other schemes in more than 30%. The Full and Standard modes present a similar behavior in percentage of blind vehicles, but the Full dissemination mode produces more than 850 messages per vehicle, which could yield broadcast storms. The Standard mode is slower during the first 5 seconds of the propagation process, but after this initial time the two schemes present very similar results, with less than half messages produced by the Standard dissemination scheme. Hence, in high vehicles density scenarios, this mode is the most appropriate when the roadmap profile is Complex. Table 6.7 summarizes the average results after 30 runs and presents: (i) the warning notification time (WNT), (ii) the percentage of blind vehicles (BV), and (iii) the number of messages received (MR) per vehicle in the different studied situations. When the warning notification time is shown, the percentage in brackets represent how many vehicles were informed at that time, since some of the studied configurations produce very poor results and using a common basic percentage (for example, 50%) for all scenarios is very difficult. In Figure 6.10, all the results are normalized, i.e., divided by the highest value for each metric in each scenario, and thus the presented results vary between 0 and 1. The most balanced configurations are highlighted, matching with the specific operation mode used in our proposed scheme. When the vehicle density is low, the number of received messages is not critical (Figures 6.10c and 6.10e), whereas in high density scenarios the scheme tends to reduce messages by slightly increasing the other metrics. 6.7 Summary In this chapter we introduced PAWDS, a new adaptive approach that allows increasing the efficiency of warning message dissemination processes using the information about the urban environment where the vehicles are moving. Our solution requires vehicles to make use of the information contained in their integrated maps to determine the profile type. Additionally, the beacons exchanged with neighbors 125 CHAPTER 6. ENHANCING WARNING MESSAGE DISSEMINATION IN VANETS THROUGH ROADMAP PROFILING (a) (b) (c) (d) (e) (f) Figure 6.10: Average simulation results after 30 runs in: Los Angeles with (a) 100 and (b) 400 vehicles, Madrid with (c) 100 and (d) 400 vehicles, and London with (e) 100 and (f) 400 vehicles. The working modes selected by our algorithm are represented using solid lines. 126 BIBLIOGRAPHY [TMJH04] M. Torrent-Moreno, D. Jiang, and H. Hartenstein. Broadcast reception rates and effects of priority access in 802.11-based vehicular ad-hoc networks. In Proceedings of the 1st ACM international workshop on Vehicular ad hoc networks, VANET ’04, pages 10–18, New York, NY, USA, 2004. ACM. [TNCS02] Y.-C. Tseng, S.-Y. Ni, Y.-S. Chen, and J.-P. Sheu. The broadcast storm problem in a mobile ad hoc network. Wireless Networks, 8:153–167, 2002. [Toh07] C.-K. Toh. Future Application Scenarios for MANET-Based Intelligent Transportation Systems. In Future Generation Communication and Networking (FGNC’07), pages 414–417, 2007. [TWB07] O.K. Tonguz, N. Wisitpongphan, and F. Bai. Broadcasting in VANET. In INFOCOM MOVE Workshop, Anchorage, Alaska, pages 7–12, May 2007. [UDSAM09] R. A. Uzcategui, A. J. De Sucre, and G. Acosta-Marum. WAVE: a tutorial - [topics in automotive networking]. IEEE Communications Magazine, 47(5):126–133, May 2009. Available at http: //dx.doi.org/10.1109/MCOM.2009.4939288. [UFG09] S. Utyuzhnikov, P. Fantini, and M. Guenov. A method for generating a well-distributed pareto set in nonlinear multiobjective optimization. Journal of Computational and Applied Mathematics, 223(2):820–841, 2009. [VB00] A. Vahdat and D. Becker. Epidemic routing for partiallyconnected ad hoc networks. Technical report, Duke University, July 2000. [VBT10] W. Viriyasitavat, F. Bai, and O.K. Tonguz. UV-CAST: An urban vehicular broadcast protocol. In IEEE Vehicular Networking Conference (VNC), pages 25–32, Amsterdam, The Netherlands, December 2010. [VdMdCA+08] P. O. S. Vaz de Melo, F. D. da Cunha, J. M. Almeida, A. A. F. Loureiro, and R. A. F. Mini. The problem of cooperation among different wireless sensor networks. In MSWiM ’08: Proceedings of the 11th international symposium on Modeling, analysis and simulation of wireless and mobile systems, pages 86–91, New York, NY, USA, 2008. ACM. Available at http://doi.acm.org/10. 1145/1454503.1454521. [vii11] Vehicle Infrastructure Integration, 2011. Available at http://www.nhtsa.dot.gov/staticfiles/DOT/NHTSA/NRD/ Multi-media/PDFs/Public%20Paper/SAE/2006/Carter_ Vehicle_Infra-structure_Integration.pdf. 229 BIBLIOGRAPHY [vol11] Volvo S60 Concept drives itself in stop-start traffic, 2011. Available at http://www.gizmag.com/ volvo-s60-concept-drives-itself-in-stop-start-traffic/ 10582/. [vsc11] Vehicle Safety Communications - Applications VSC-A, 2011. Available at http://www.nhtsa.dot.gov/staticfiles/DOT/ NHTSA/NRD/Multi-media/PDFs/Crash%20Avoidance/2009/ 811073.pdf. [Wag06] P. Wagner. How human drivers control their vehicle. The European Physical Journal B - Condensed Matter and Complex Systems, 52:427–431, 2006. Available at http://dx.doi.org/10. 1140/epjb/e2006-00300-1. [WBM+07] N. Wisitpongphan, F. Bai, P. Mudalige, V. Sadekar, and O.K. Tonguz. Routing in sparse vehicular ad hoc networks. IEEE Journal on Selected Areas in Communications, 25(8):1538–1556, October 2007. [WH03] S. Wietholter and C. Hoene. Design and Verification of an IEEE 802.11e EDCF Simulation Model in ns-2.26. Technical report, Technical Report TKN-03-019, Telecommunication Networks Group, Technische Universitat Berlin, November 2003. [WTP+07] N. Wisitpongphan, O.K. Tonguz, J.S. Parikh, P. Mudalige, F. Bai, and V. Sadekar. Broadcast storm mitigation techniques in vehicular ad hoc networks. IEEE Wireless Communications, 14:84–94, 2007. [YOCH07] K. Yang, S. Ou, H.-H. Chen, and J. He. A Multihop PeerCommunication Protocol With Fairness Guarantee for IEEE 802.16-Based Vehicular Networks. IEEE Transactions on Vehicular Technology, 56(6):3358–3370, 2007. [YOW09] G. Yan, S. Olariu, and M.C Weigle. Providing VANET security through active position detection. Computer Communications, 31(12):2883–2897, July 2009. [ZDT00] E. Zitzler, K. Deb, and L. Thiele. Comparison of multiobjective evolutionary algorithms: empirical results. IEEE Transactions on Evolutionary Computing, 8(2):173–195, 2000. [ZWLZ10] J. Zuo, Y. Wang, Y. Liu, and Y. Zhang. Performance evaluation of routing protocol in vanet with vehicle-node density. In 6th International Conference on Wireless Communications Networking and Mobile Computing (WiCOM), pages 1–4, Sept. 2010. Available at http://dx.doi.org/10.1109/WICOM.2010.5600844. 230