Bio-inspired Routing Protocols for Vehicular Ad-Hoc Networks (E-Book) von Salim Bitam

PREFACE ix

INTRODUCTION xi

ACRONYMS AND NOTATIONS xv

CHAPTER 1. VEHICULAR AD HOC NETWORKS 1

1.1. VANET definition, characteristics and applications1

1.1.1. Definition of vehicular ad hoc network1

1.1.2. Characteristics of vehicular ad hoc networks 2

1.1.3. Applications of vehicular ad hoc networks 5

1.2. VANET architectures 7

1.2.1. Vehicular WLAN/cellular architecture 7

1.2.2. Pure ad hoc architecture 8

1.2.3. Hybrid architecture 9

1.3. Mobility models 9

1.3.1. Random-based mobility models 10

1.3.2. Geographic map-based mobility models 12

1.3.3. Group-based mobility 14

1.3.4. Prediction-based mobility models 17

1.3.5. Software-tools-based mobility models 20

1.4. VANET challenges and issues 21

1.4.1. VANET routing 21

1.4.2. Vehicular network scalability 22

1.4.3. Computational complexity in VANET networking 22

1.4.4. Routing robustness and self-organization in vehicular networks 23

1.4.5. Vehicular network security 23

1.5. Bibliography 23

CHAPTER 2. ROUTING FOR VEHICULAR AD HOC NETWORKS 29

2.1. Basic concepts 29

2.1.1. Single-hop versus multi-hop beaconing in VANETs 29

2.1.2. Routing classification of VANETs 31

2.2. Quality-of-service of VANET routing 35

2.2.1. Quality-of-service definition 35

2.2.2. Quality-of-service criteria 36

2.3. VANET routing standards 37

2.3.1. Dedicated short range communication 38

2.3.2. Standards for wireless access in vehicular environments (WAVE) 40

2.3.3. VANET standards related to routing layers 42

2.3.4. Other VANET routing standards 44

2.4. VANET routing challenges and issues 45

2.4.1. Dynamics nature of VANETs (mobility pattern and vehicles velocity) 45

2.4.2. Vehicular network density and scalability 46

2.4.3. Safety improvement and quality-of-service 46

2.5. Bibliography 47

CHAPTER 3. CONVENTIONAL ROUTING PROTOCOLS FOR VANETS 51

3.1. Topology-based routing 51

3.1.1. Reactive routing protocols 52

3.1.2. Proactive routing protocols 55

3.1.3. Hybrid routing protocols 57

3.1.4. Critics of topology-based routing 58

3.2. Geography-based routing 59

3.2.1. Geography-based routing principle 59

3.2.2. Geography-based routing protocols 59

3.2.3. Critics of geography-based routing 67

3.3. Cluster-based routing 68

3.3.1. Cluster-based routing principle 68

3.3.2. Cluster-based routing protocols 69

3.3.3. Critics of cluster-based routing 73

3.4. Bibliography 73

CHAPTER 4. BIO-INSPIRED ROUTING PROTOCOLS FOR VANETS 79

4.1. Motivations for using bio-inspired approaches in VANET routing 80

4.1.1. Network scalability 80

4.1.2. Computational complexity 80

4.1.3. Self-organization and adaptability 81

4.1.4. Routing robustness 81

4.2. Fundamental concepts and operations of bio-inspired VANET routing 82

4.2.1. Optimization problem definition 82

4.2.2. Search space (SSp) 83

4.2.3. Objective function 83

4.2.4. Population 84

4.2.5. Individual encoding 84

4.2.6. Initialization 84

4.2.7. Stopping criterion 85

4.3. Basic bio-inspired algorithms used in VANET routing literature 85

4.3.1. Genetic algorithm 86

4.3.2. Ant colony optimization 89

4.3.3. Particle swarm optimization 90

4.3.4. Bees life algorithm 92

4.3.5. Bacterial foraging optimization 93

4.4. Evolutionary algorithms for VANET routing 95

4.4.1. Sequential genetic algorithms for VANET routing 95

4.4.2. Parallel genetic algorithms for VANET routing 100

4.5. Swarm intelligence for VANET routing 101

4.5.1. Ant colony optimization for VANET routing 102

4.5.2. Particle swarm optimization for VANET routing 106

4.5.3. Bee colony optimization for VANET routing 108

4.5.4. Bacterial foraging optimization for VANET routing 110

4.6. Another bio-inspired approach for VANET routing 112

4.7. Bibliography 113

CONCLUSION 121

INDEX 125

Vehicular Ad-Hoc Networks (VANETs) play a key role to develop Intelligent Transportation Systems (ITS) aiming to achieve road safety and to guaranty needs of drivers and passengers, in addition to improve the transportation productivity. One of the most important challenges of this kind of networks is the data routing between VANET nodes which should be routed with high level of Quality of Service (QoS) to ensure receiving messages in the time. Then, the driver can take the appropriate decision to improve the road safety. In the literature, there are several routing protocols for VANETs which are more or less reliable to reach safety requirements. In this book, we start by describing all VANET basic concepts such as VANET definition, VANET versus Mobile ad-Hoc Network (MANET), architectures, routing definition and steps, Quality of Service (QoS) for VANET Routing, Metrics of evaluation, Experimentation, and simulation of VANETs, mobility patterns of VANET etc. Moreover, different routing protocols for routing in VANETs will be described. We propose two main categories to be presented: classical routing and bio-inspired routing. Concerning classical VANET, main principles and all phases will be overviewed, as well as, their two sub-categories which are topological and geographical protocols. After that, we propose a new category called bio-inspired routing which is inspired by natural phenomenon such as Ant colony, Bee life, Genetic operators etc. We present also, some referential protocols as example of each category.

In this book, we focus on the idea of how to apply bio-inspired principle into VANET routing to improve road safety, and to ensure QoS of vehicular applications.

Salim BITAM is an Associate Professor, Head (2003-2009) of Computer Science for Management Department of Biskra University, Algeria, he is senior member of LESIA Laboratory (University of Biskra, Algeria), and Associate Member of LiSSi Laboratory (Paris-Est University -UPEC-, France). He received the Ing. Diploma in Computer Science from Mentouri University, Constantine, Algeria, in 1999 and the Magister and PhD diplomas in Computer Science from University of Biskra, Algeria, in 2002 and 2011, respectively. In December 2002, he has been an assistant professor and since January 2011 he is an associate professor in Computer Science Department in University of Biskra. Dr. Bitam main research interests are vehicular ad-hoc networks, mobile ad-hoc networks, wireless sensor networks, cloud computing, and bio-inspired methods for routing and optimization. Dr. Salim Bitam has served as a reviewer of several journals such as IEEE, Elsevier and Springer and on the program committees of several international conferences.

Abdelhamid MELLOUK (IEEE Senior Member) is a full professor at University of Paris-Est (UPEC), Networks& Telecommunications (N&T) Department and LiSSi Laboratory, France. He graduated in computer network engineering from the Computer Science High Eng. School, University of Paris Sud XI Orsay, received his Ph.D. in informatics from the same university, and a Doctorate of Sciences (Habilitation) diploma from  UPEC. Founder of the Network Control Research activity with extensive international academic and industrial collaborations, his general area of research is in adaptive real-time control for high-speed new generation dynamic wired/wireless networking in order to maintain acceptable quality of service/experience for added value services. He is an active member of the IEEE Communications Society and held several offices including leadership positions in IEEE Communications Society Technical Committees (Chair of The Technical Committee on Communications Software, Leader Officer of The Technical Committee on Switching and Routing). He has published/coordinated five books and several refereed international publications in journals, conferences, and books, in addition to numerous keynotes and plenary talks in flagship venues. He serves on the Editorial Boards or as Associate Editor for several journals, and he is chairing or has chaired (or co-chaired) some of the top international conferences and symposia (includling IEEE ICC and IEEE GlobeCom).