Bio-inspired Routing Protocols for Vehicular Ad-Hoc Networks E-Book

Salim Bitam

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Serie: ISTE Focus
• Sprache: Englisch

Seitenzahl: 211

Veröffentlichungsjahr: 2014

Beschreibung

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.

Leseprobe

Contents

1 Vehicular Ad Hoc Networks

1.1. VANET definition, characteristics and applications

1.2. VANET architectures

1.3. Mobility models

1.4. VANET challenges and issues

1.5. Bibliography

2 Routing for Vehicular Ad Hoc Networks

2.1. Basic concepts

2.2. Quality-of-service of VANET routing

2.3. VANET routing standards

2.4. VANET routing challenges and issues

2.5. Bibliography

3 Conventional Routing Protocols for VANETs

3.1. Topology-based routing

3.2. Geography-based routing

3.3. Cluster-based routing

3.4. Bibliography

4 Bio-inspired Routing Protocols for VANETs

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

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

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

4.4. Evolutionary algorithms for VANET routing

4.5. Swarm intelligence for VANET routing

4.6. Another bio-inspired approach for VANET routing

4.7. Bibliography

Conclusion

C.1. Summary

C.2. Opportunities and future trends

First published 2014in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd

27-37 St George’s Road

London SW19 4EU

UK

www.iste.co.uk

John Wiley & Sons, Inc.

111 River Street

Hoboken, NJ 07030

USA

www.wiley.com

© ISTE Ltd 2014

The rights of Salim Bitam and Abdelhamid Mellouk to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Control Number: 2014945528

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISSN 2051-2481 (Print)

ISSN 2051-249X (Online)

ISBN 978-1-84821-663-1

Preface

It will be fascinating to look back in the years ahead and note the growing interest of bio-inspired computing, short for biologically inspired computing, that has been deployed to solve various computational problems in several disciplines such as networks and telecommunications, imagery, artificial intelligence and decision support systems.

Due to the emergence of different kinds of communication and networking technologies and the foreseen proliferation of different and specific types of services supported by these technologies, the use of bio-inspired techniques seems to be a real challenge, taking into account all the computational complexities.

However, the use of artificial intelligence tools together with biologically inspired techniques is needed to control network behavior in real-time so as to provide users with the quality of service that they request.

The book focuses on the use of these techniques in intelligent transportation systems (ITSs). The latter is considered as one of the most recently studied domains where bio-inspired approaches are successfully applied. ITS design and development play a major role in improving road safety, traffic monitoring and passengers’ comfort in order to avoid accidents and traffic congestion on the one hand, and to serve and satisfy digital needs of vehicle drivers and passengers on the other. To achieve these goals, ITSs need to support traffic information delivery, accurately and timely, to vehicle drivers and transport authorities. This transmission is ensured through a reliable vehicular wireless and mobile network known as a Vehicular Ad hoc NETwork (VANET).

Over the years, the continuous technological evolution and the development of new applications and services have steered networking research toward new problems, which have emerged as the network evolves with new features toward what is usually referred to as the next generation networks, which has become one of the basic infrastructures that supports the world economy nowadays.

This book focuses on the current state-of-the-art research results and experience reports in the area of bio-inspired techniques dedicated to ITSs. It shows that the bio-inspired field is a very dynamic area in terms of theory and application.

To give a complete bibliography and a historical account of the research that led to the present form of the subject would have been impossible. Thus, it is inevitable that some topics have been treated in less detail than others. The choices made reflect, in part, personal taste and expertise and, in part, a preference for very promising research and recent developments in the field of ITS-based bio-inspired techniques.

This book is a start, but also leaves many questions unanswered. I hope that it will inspire a new generation of investigators and investigations.

The authors hope that you will enjoy reading this book and receive many helpful ideas and revelations for your own study.

Abdelhamid MelloukJuly 2014

Introduction

Over the last decade, we have witnessed the emergence of bio-inspired computing, short for biologically inspired computing, that has been deployed to solve various computational problems in several disciplines such as networks and telecommunications, imagery, artificial intelligence and decision support systems.

A bio-inspired technique is defined as a field of study of natural behaviors and biological species aiming to propose new solutions to computational problems such as modeling, optimization and simulation. The basic principle used by these approaches is the imitation of natural behaviors of living creatures such as humans, insects and animals when they try to find solutions to their natural needs such as food or nest searching, reproduction, defense and traveling. The Intelligent Transportation System (ITS) is considered as one of the most recently studied domains where bio-inspired approaches are successfully applied and have given better results compared to conventional approaches which are not biologically inspired.

ITS’s design and development play a major role in improving road safety, traffic monitoring and passengers’ comfort in order to avoid accidents and traffic congestion on one side, and to serve and satisfy digital needs of vehicle drivers and passengers. To achieve these goals, ITSs need to support traffic information delivery accurately and timely to vehicle drivers and transport authorities. This transmission is ensured through a reliable vehicular wireless and mobile network known as a Vehicular Ad hoc NETwork (VANET).

VANET is considered as a specific kind of Mobile Ad hoc NETwork (MANET) which consists of a set of mobile nodes (vehicles) and fixed nodes known as roadside units (RSUs). A VANET provides digital data communication between vehicles through inter-vehicle communication (IVC), and between vehicles and RSUs through vehicle-to-roadside communication (VRC). Due to their restricted range of motion in terms of directions and speeds, VANET vehicles move according to an organized and restricted mobility model with some distinctions between highways, urban or rural areas. Moreover, a vehicle is equipped with some sort of radio interface called on-board unit (OBU) that enables short-range wireless IVCs and/or VRCs along with a Global Positioning System (GPS) integrated into vehicles to facilitate location-based services.

VANETs can support different types of services such as vehicle safety, automated toll payment, traffic management, enhanced navigation, location-based services (e.g. finding the closest fuel station, restaurant or hotel) and infotainment applications, such as Internet-based services.

This book studies different bio-inspired approaches proposed up to the present which are applied to routing problems for VANETs. The main motivation behind the deployment of bio-inspired techniques for VANET routing arises from the strong similarity between communication scenarios in data packet routing and the natural communication of species. Network scalability is another reason to apply bio-inspired routing against traditional routing which is less efficient for dense VANETs. Moreover, these approaches have proved their effectiveness in solving such problems with high adaptability and robustness in terms of accuracy of results compared to other VANET routing schemes. In fact, the accurate forwarding of data packets is very crucial and important in vehicular networks, since delivering data to its destination in time can help vehicle drivers to react in opportune time, therefore, undesirable situations are avoided and road safety is improved.

This book is divided into five chapters. Chapter 1 contains an introduction and includes bio-inspiration’s purpose, motivations and an overview of the book. Chapter 2 reviews a background of VANETs including definition, characteristics and applications. Also, Chapter 2 presents different VANET architectures and their mobility models, which is concluded by the essential challenges and issues of VANETs.

Chapter 3 is devoted to VANET routing concepts and mechanisms. To achieve this, Chapter 3 highlights basic transmission processes and proposes a classification of proposed routing protocols for VANETs into three categories: topology-based routing, geography-based routing and cluster-based routing. Quality of Service and VANET routing standards are also outlined; then, major issues and challenges facing VANET routing are presented.

The fourth chapter deals with details of conventional routing protocols conceived for VANETs. For each category (i.e. topology-based, geography-based and cluster-based routing) the main principles as well as advantages and weaknesses are explained. In addition, the main protocol of each category is illustrated in detail by schemes and examples.

Chapter 5 provides a detailed knowledge concerning biologically inspired approaches applied for vehicular Ad hoc networks. It starts with motivations for using such methods in VANET routing and describes different basic concepts and operations used by bio-inspired protocols in this context. Afterward, basic bio-inspired algorithms used in VANET routing literature are explained in depth. This part concerns genetic algorithm, ant colony optimization, particle swarm optimization, bee colony optimization and bacterial foraging optimization. Some examples in the VANET area and illustrative schemes are depicted. Moreover, this chapter surveys bio-inspired protocols for VANET routing classified into three categories, namely evolutionary algorithms, swarm intelligence and another bio-inspired source. For each category, a state of the art including proposed protocols, their main principles and discussions are presented.

Finally, this book is concluded with some rough opportunities and future tends of bio-inspired methods for routing in VANETs.

Acronyms and Notations

ACAR

Adaptive Connectivity Aware Routing

ACO

Ant Colony Optimization

AMR

Adaptive Message Routing

AODV

Ad hoc on-demand Distance Vector

BLA

Bees Life Algorithm

CAN

Controller Area Network

CAR

Connectivity-Aware Routing

CBRP

Cluster-based Routing Protocol

CMGR

Connectivity-aware Minimum-delay Geographic Routing

COIN

Clustering algorithm for Open Inter-vehicle Networks

DREAM

Distance Routing Effect Algorithm for Mobility

DSRC

Dedicated Short Range Communications

DYMO

Dynamic MANET On-demand

FAST

Fuzzy-Assisted Social-based rouTing

GA

Genetic Algorithm

GPCR

Greedy Perimeter Coordinator Routing

GPS

Global Positioning System

GPSR

Greedy Perimeter Stateless Routing

HLAR

Hybrid Location-based Ad hoc Routing

HyBR

Hybrid Bee swarm Routing

IEEE 1609

Family of Standards for wireless access in vehicular environments (WAVE)

IEEE 802.11

Set of media access control (MAC) and physical layer (PHY) specifications for implementing wireless local area network

IEEE 802.11a

An amendment to the IEEE 802.11 defining requirements for an orthogonal frequency division multiplexing (OFDM) communication system

IEEE 802.11p

An amendment to the IEEE 802.11 to add wireless access in vehicular environments

IGRP

Intersection-based Geographical Routing Protocol

IP

Internet Protocol

ISO

International Organization for Standardization

ITS

Intelligent Transportation System

IVC

Inter-Vehicle Communication

LIN

Local Interconnect Network

LocVSDP

Location-based Vehicular Service Discovery Protocol

LTE

Long Term Evolution

MAC

Medium Access Control

MANET

Mobile Ad hoc NETwork

MAR-DYMO

Mobility-aware Ant colony optimization Routing DYMO

MAV-AODV

Multicast with Ant Colony Optimization for VANET

MURU

MUlti-hop Routing protocol for Urban

ns-2

Network Simulator

OBU

On-Board Unit

OFDM

Orthogonal Frequency Division Multiplexing

OLSR

Optimized Link State Routing

PassCAR

Passive Clustering Aided Routing

PBR

Prediction Based Routing

PLCP

Physical Layer Convergence Procedure

PMD

Physical Medium Dependent

PSO

Particle Swarm Optimization

QoS

Quality of Service

QoSBeeVANET

Quality of Service Bee Swarm routing protocol for VANET

RBVT-P

Road-Based using Vehicular Traffic Proactive

RIVER

Reliable Inter-VEhicular Routing

ROMSGP

Receive on Most Stable Group-Path

RSU

Roadside Unit

SLAB

Statistical Location-Assisted Broadcast

SUMO

Simulation of Urban MObility

TACR

Trust dependent Ant Colony Routing

VADD

Vehicle-Assisted Data Delivery

VANET

Vehicular Ad hoc NETwork

VCN

Vehicular Cellular Network

VRC

Vehicle-to-Roadside Communication

V-WLAN

Vehicular Wireless Local Area Network

WAVE

Wireless Access in Vehicular Environment

Wi-Fi

Wireless Fidelity

WiMAX

Worldwide Interoperability for Microwave Access

WSM

WAVE Short Message

WSMP

WAVE Short Message Protocol

1

Vehicular Ad Hoc Networks

In the last decade, we witnessed an increasing interest in the transportation sector and the research community to improve road safety and supply commercial services by providing timely and accurate information to vehicular drivers and transport authorities. One way to achieve these goals is by sharing road traffic information through wireless and mobile networks with little or no infrastructure, known as Vehicular Ad hoc NETworks (VANETs). This chapter reviews an overview on VANETs, starting with a general VANET definition of VANET and its main characteristics which distinguish VANETs from the other wireless networks. This chapter also highlights VANET fundamental applications proposed to increase utilities of Intelligent Transportation Systems (ITS). Moreover, VANET architectures and mobility models are presented in this chapter, in addition to the most used vehicular network simulators applied to evaluated VANET performances. Finally, this chapter outlines the main VANET challenges and issues, like data routing, VANET scalability, routing robustness and self-organization, and security.

1.1. VANET definition, characteristics and applications

1.1.1. Definition of vehicular ad hoc network

VANETs are seen as a specific type of mobile ad hoc network (MANET), which provides data communication in vehicular areas using a wireless transmission. VANETs are conceived to enhance wireless communication initially provided by vehicular cellular networks either in urban or rural areas. Two kinds of VANET nodes exchange data messages in multi-hop mode, namely mobile nodes (i.e. vehicles) and stationary nodes known as roadside units (RSUs) which are installed on roadsides. All nodes forward data messages from the first sender called the source node to the final receiver known as the destination node. As a result, several types of transportation applications are performed to the benefit of passengers or transport authorities such as Freeway Management, Crash Prevention and Safety, Road Weather Management, Collision Avoidance, Driver Assistance [RIT 14].

Several academic definitions of VANETs were proposed in the literature. We propose a general definition of VANET, taking into account all vehicular network functionalities and its largest infrastructure, as follows:

VANET can be defined as a set of mobile nodes consisting of vehicles, as well as fixed nodes known as RSUs deployed at critical locations such as slippery roads, service stations, authority buildings, dangerous intersections or places well known for hazardous weather conditions [BIT 11]. VANET provides digital data communication in wireless and multi-hop manner between vehicles through intervehicle communication (IVC), and between vehicles and RSUs through vehicle-to-roadside communication (VRC), as shown in Figure 1.1.

Vehicles are equipped with some sort of radio interface, called an On-Board Unit (OBU), that enables short-range wireless IVCs and/or VRCs along with a Global Positioning System (GPS) integrated into vehicles to facilitate location-based services.

Contrary to MANET nodes, VANET vehicles do not move around arbitrarily, due to their restricted range of motion in terms of directions and speeds. In fact, vehicles move according to an organized pattern, called a mobility model, based on predefined roads, buildings, junctions and other traffic entities, in an urban or a rural area.

1.1.2. Characteristics of vehicular ad hoc networks

VANETs are special mobile and wireless networks, characterized by a set of particular properties which make them very distinct, and call for more requirements to develop networking vehicular applications. This section reviews the main properties of vehicular networks and shows the influence of these properties on the vehicular applications.

Figure 1.1. Vehicular ad hoc network. For a color version of this figure, seewww.iste.co.uk/bitam/bio-inspired.zip

1.1.2.1. Vehicle velocity

In VANETs, vehicle velocity is the rate of change of the position of mobile node versus time. Vehicle velocity may range from zero when vehicles are stuck in traffic jam, to over 200 km/h on highways [SCH 08]. Vehicle velocity has an important potential on the vehicular network applications in the two extremes vehicle velocities. In the case of very high velocity, for example on highways, the period when transmitter and receiver are connected is very short (i.e. time of stable connection between transmitter and receiver). Therefore, the routing process should be frequently relaunched to find new routes and to ensure long period transmission. This frequent route discovery implies a considerable delay to transmit data packets, in addition to a significant packet loss due to the eventual use of expired routes. However, when vehicles move slowly, the network will be very dense in terms of nodes number. Consequently, high interference could occur, and then medium access solutions are required.

1.1.2.2. VANET density

VANET density is considered as a particular property which can make a basic distinction between vehicular network and other wireless networks. In fact, the deployment area of VANET nodes can contain a very high number of nodes which can exceed 250 nodes in the transmission range of one node. This situation can occur if the vehicular traffic is very congested due to various reasons such as traffic jams and accidents, which is the case for the very high density. Consequently, many undesirable networking effects can occur, such as network fragmentation during the routing process, use of a long multi-hop path to transmit messages and high interference. However, a VANET can be considered low density if it contains a low number of nodes, scattered in vehicles’ environment, particularly in rural areas or at off-peak traffic hours. In such cases, several forwarded messages can be dropped due to the absence of an intermediate node between the source node and the destination. Hence, several copies of messages should be stored and be present upon multiple times by the same transmitter causing an important delay of packet dissemination.

1.1.2.3. Node heterogeneity

The third key property of VANETs is the node heterogeneity which means a considerable diversity in the network nodes. Two aspects can be distinguished to explain node heterogeneity in such networks: the structural aspect and the functional aspect. The former concerns structure of VANET nodes, two major types of nodes can be cited: vehicles and RSUs. Vehicles are mobile nodes, with limited and different transmission range, equipped by OBUs as wireless transmission interfaces, as well as heterogeneous digital devices to perform computational applications, such as processor (CPU), memory. Also, vehicles can connect directly to other VANET nodes (vehicles or RSUs) through wireless waves that form a no-infrastructure subnetwork. This non-uniformity of vehicle devices requires more studies to ensure a continuous functionality of the entire network. The second component type of a VANET is RSU, defined as immobile nodes installed at a fixed location along the roadside aiming to help vehicles to connect to the global network or to the Internet as gateways. RSUs are in wired connection with other RSUs to form permanent infrastructure of VANETs. Due to its immobilities and wired links, RSUs’ placement in vehicular area is a considerable issue.

From the point of view of VANET functions, vehicular network nodes can be categorized according to various types of vehicular applications, namely control applications installed on authority vehicles or on RSUs, fixed sensing applications ensured by RSUs, emergency and ad hoc applications performed by private and authority vehicles and warning and maintenance applications executed by emergency vehicles. Consequently, a certain level of distinction is required during implementation and management of applications such as ensuring access control, privacy and priority.

1.1.2.4. Mobility model

Due to the vehicular environment, consisting of roads, buildings, junctions and traffic regulations, VANET vehicles move around in a regular and restricted mobility model [PLÖ 08]. This regularity of nodes’ movement does not occur on the other kind of ad hoc networks. Hence, VANET studies should be based on strict and realistic mobility model to obtain more significant results and realistic conclusions.

Three main submodels of mobility can be mentioned: highway, rural and urban submodels. The highway is a mobility submodel located usually outside cities, and characterized by low density. It consists of two main roads in two different directions. Each road is formed by three or more lanes, in which vehicles can move with very high speed. However, the rural submodel consists of a set of more or less organized streets, where vehicles move with low speed. Vehicles in rural area form a low dense network. The third submodel is the urban submodel. It represents city road network which is very dense and consists of lots of small or big roads, many junctions usually equipped with traffic lights and signals, as well as buildings which limit wireless communication. In the urban network, vehicles can move with low speed, but on some roads they can move with relatively high speeds. Vehicles’ movement in each of these submobility models is constrained by vehicle speeds, directions and densities that represent challenges to be taken up in VANET studies.

1.1.3. Applications of vehicular ad hoc networks

Different types of application can be supported by vehicular networks such as vehicle safety, automated toll payment, traffic management, enhanced navigation, location-based applications (e.g. finding the closest fuel station, restaurant or hotel), and infotainment applications through Internet-based services [BIT 13b]. In this section, the main applications provided by VANETs are outlined.

1.1.3.1. Road safety applications

It is widely accepted that road safety applications are the most sensitive services in VANETs because of the significant impact they can have on human lives. The main goal of safety applications relies on the aggregation and sharing of VANET information through safety messages, which are transmitted by each VANET node (i.e. vehicle and RSU). These safety messages gather vehicular information including vehicle and traffic states. The carried information is vehicle location, velocity, acceleration, brake state, traffic lights states, pedestrian numbers, etc. On the basis of timely delivery and processing of safety vehicular information, vehicles drivers can react appropriately and avoid dangerous and undesirable situations such as accidents and collisions.

1.1.3.2. Vehicular authority services

Vehicular ad hoc networks are also designed to help and expedite traffic tasks of transport authorities such as police and emergency recovery units. More specifically, authority applications can contribute to road safety and traffic improvement by transmitting warning and emergency messages from authority vehicles to other vehicles in order to inform approaching emergency vehicles using virtual sirens, or to preempt vehicle priorities which help authority vehicles to reach their destination rapidly. This kind of service is known as “emergency response”. Moreover, VANETs are also intended to support another kind of authority service called “traffic surveillance”. In fact, nodes of VANET can sense and send information to authority centers using surveillance applications such as stolen vehicle tracking, vehicle safety inspection, electronic license plate verification and electronic drivers’ license checking. It is worth noting that this type of application must not be abused by anyone, which clearly underlines security requirements and the need for a discussion of legal aspects of vehicular communication [SCH 08].

1.1.3.3. Enhanced driving

Enhancing driving is another category of applications supported by VANETs. This category improves driving by providing local traffic information as well as information concerning the global vehicular environment. Local traffic information is data sent by other vehicles or RSUs which helps drivers to improve their driving. For example, a climatic condition may be sensed by VANET nodes and disseminated in the local area to suggest some beneficial actions, such as running the vehicle air conditioner in a polluted or congested area, or lighting up headlights in the underground passage. However, global traffic information is data which concern the entire network and can be sent by distant nodes to all network nodes to indicate a network state or useful information that helps drivers to make the appropriate decision against a critical situation. We can mention the case of traffic congestion which could be reported in the entire network, so distant drivers can take another road which is much faster. Furthermore, there are also various comfort applications which improve drivers’ and passengers’ traveling and provide informative services such as fuel station locations, global weather information and emergency and breakdown services.

1.1.3.4. Business and entertainment services

Vehicular networks can improve comfort of drivers and passengers by providing commercial services through the Internet or other private networks. These business services ensure delivering digital products to road consumers, such as parking payment and road usage payment. Note that vehicular businesses should warrant all conventional digital business requirements such as transaction security and privacy, and secured payment. Moreover, entertainment and interactive multimedia services are also delivered by VANETs, such as downloading movies and music, and playing online games.

1.2. VANET architectures

Following on from different types of communication devices and network infrastructures, VANETs can be organized within three categories of architecture: vehicular WLAN/cellular, pure ad hoc and hybrid architecture.

Figure 1.2.Various VANET architectures; a) vehicular WLAN/cellular; b) pure ad hoc; c) hybrid. For a color version of this figure, see www.iste.co.uk/bitam/bio-inspired.zip

1.2.1. Vehicular WLAN/cellular architecture

In this category, vehicular network consists of vehicles as wireless and moving nodes, as well as a fixed infrastructure used to link vehicles to a wider network such as the Internet, as shown in Figure 1.2(a). Two kinds of fixed infrastructure can be cited: Vehicular Wireless Local Area Networks (V-WLAN) and Vehicular Cellular Network (VCN).