Design and Evaluation of Ad Hoc Routing Protocol

Martine Wahl is a research fellow at the Université Gustave Eiffel, France. She holds an engineering degree from the Université Paris-Sud Orsay and a doctorate from Grenoble INP. Patrick Sondi is a professor at IMT Nord Europe, France. After studying prepolytechnics at the Université de Kinshasa, Democratic Republic of the Congo, he obtained a doctorate in computer science at the Université de Valenciennes, France, then a qualification for research supervision at the Université du Littoral, France.

Preface ix

Chapter 1. Challenges Involving Ad Hoc Communications on the Road 1

1.1. Introduction 1

1.2. The railway experience in the vehicular networks of the future 2

1.3. The contribution of ad hoc communications to vehicular networks 4

1.3.1. Maintaining connectivity and service continuity 5

1.3.2. Cooperation and performance improvement 6

1.3.3. Communications security and auditing 7

1.3.4. Technological evolution and depreciation 9

1.3.5. European harmonization 9

1.4. Conclusion 10

1.5. References 10

Chapter 2. Functional Approach to Protocol Design 11

2.1. Introduction 11

2.2. Ad hoc routing protocol basics 13

2.2.1. Routing definition 13

2.2.2. Destination node identification 14

2.2.3. Route discovery and selection 15

2.2.4. Network topology discovery 19

2.3. A few strategies adopted by ad hoc routing protocols 21

2.3.1. Protocol strategies for establishing links 21

2.3.2. Protocol strategies in request dissemination 25

2.4. Ad hoc routing protocols for road traffic 29

2.4.1. Transposition of protocols from mobile ad hoc networks 29

2.4.2. Strategies and considerations for the road environment 30

2.4.3. Routing policies and quality of service metrics 39

2.5. Functional design approach: concepts and case study 42

2.5.1. Idea and approach 42

2.5.2. Overview of the case study protocol: Chain-Branch-Leaf 46

2.5.3. Modeling CBL in OLSR: CBL-OLSR 55

2.6. Conclusion 59

2.7. References 61

Chapter 3. Models and Simulations for Performance Analysis 71

3.1. Introduction 71

3.2. Choice of road context and radio technology 75

3.3. Modeling and simulation tools for VANETs 78

3.3.1. Radio wave propagation model 80

3.3.2. Models for obtaining vehicle traces 85

3.3.3. Mobility simulators 89

3.3.4. Communication network simulators 91

3.3.5. VANET simulators 94

3.4. Choice of modeling and simulation tools 96

3.5. Definition of mobility scenarios in a highway context: example of the construction of mobility models 97

3.5.1. Mobility modeling with OPNET Riverbed Modeler 106

3.6. Transmission modeling 119

3.6.1. Choice of technology for frame transmission 119

3.6.2. Parametrization of an 802.11p node under OPNET Riverbed Modeler 122

3.6.3. Modeling the propagation channel 122

3.6.4. Modeling the CBL-OLSR protocol in 802.11p nodes 125

3.7. Conclusion 126

3.8. References 127

Chapter 4. Performance Evaluation of the Protocol for Collaborative Applications 139

4.1. Study background 139

4.2. Configuration of the mobile nodes 143

4.3. Validation of the CBL-OLSR implementation in OPNET Riverbed Modeler 147

4.3.1. Structural verification 147

4.3.2. Analysis of routing traffic generated by CBL-OLSR versus OLSR 150

4.3.3. Sensitivity to the propagation model 154

4.4. CBL-OLSR system performance analysis with transfer of application data 156

4.4.1. Introduction to collaborative perception and ego-localization applications 156

4.4.2. Comparative analysis of CBL-OLSR with OLSR and AODV for unicast mode data transmission 159

4.4.3. Performance evaluation of an extended perception application 176

4.4.4. Multiple applications: extended perception and collaborative istributed localization 181

4.5. Conclusion 187

4.6. References 189

Chapter 5. Formal Model for the Analysis of the Properties of the Protocol 193

5.1. Introduction 193

5.2. The contribution of formal methods to protocol engineering 194

5.3. The Event-B method 195

5.3.1. Mathematical concepts and notations of the Event-B method 195

5.3.2. Event-B model structure 196

5.3.3. Refinement concept 197

5.3.4. Event-B model correction 197

5.4. Formal approach applied to the protocol of the case study 198

5.4.1. Formal description of the organization by CBL in a VANET 199

5.4.2. CBL rules and properties in a VANET 202

5.5. A correct-by-construction model of CBL with Event-B 204

5.5.1. Level 1: basic model for any routing protocol 204

5.5.2. Level 2: mobility and communications modeling 207

5.5.3. Level 3: CBL rules and properties modeling 212

5.6. Model validation 218

5.6.1. Model validation by animation 218

5.6.2. Model correction by offloading proof obligations 220

5.7. Conclusion 223

5.8. References 224

Chapter 6. Integration of Ad Hoc Components in a Global Infrastructure 227

6.1. Introduction 227

6.2. Ensuring connectivity and services 227

6.3. Cooperation and performance improvement 229

6.4. Evolution of design and evaluation methods 231

6.5. Conclusion 238

6.6. References 239

List of Authors 241

Index 243