10 Autonomic Computing and VANETs: Simulation of a QoS-based Communication Model – Networking Simulation for Intelligent Transportation Systems

10
Autonomic Computing and VANETs: Simulation of a QoS-based Communication Model

10.1. Introduction

The complexity of intelligent transportation systems (ITSs) management is growing. This is emphasized by the use of heterogeneous technologies, which enables different kinds of communications. Adapting the Autonomic Computing paradigm to ITSs and in particular to vehicular ad hoc networks (VANETs) in order to enhance the performance of communications in such changing environments is a challenging task. This approach can be applied to improve the performance of communication protocols, such as broadcasting methods. The broadcasting communication mode is widely used in VANETs for sending emergency messages and road-traffic information or to help routing protocols to determine routes. This communication mode is known to be difficult to achieve efficiently, as it depends on the network density. Indeed, broadcasting methods may cause network congestion if they are not well designed. This chapter introduces the application of Autonomic Computing principles within VANETs’ environments in order to enhance the performance of QoS-based communications thanks to the self-management concept. In such environments, the design of a QoS-based broadcasting protocol is presented as a usage case. A state of the art concerning the Autonomic Computing paradigm and its application in VANETs is first presented in section 10.2. Then, section 10.3 describes the existing broadcasting methods and protocols in wireless ad hoc networks and especially in VANETs. This state of the art helps introduce in section 10.4 the design of a QoS-based autonomic broadcasting protocol in VANETs in order to deliver messages in accordance with the given message classes and network density levels. This approach allows each vehicle to dynamically adapt its broadcasting strategy not only with respect to the network density but also according to the class of the message to be sent: emergency (high-priority), road-traffic (medium-priority) or comfort message (low-priority). Finally, in section 10.5, we present the simulation details of a QoS-based communication model in autonomic VANETs as well as the design and evaluation of a self-managed broadcasting protocol called ADM (autonomic dissemination method), which serves as an example of an autonomic broadcasting approach.

10.2. Autonomic Computing within VANETs

10.2.1. Autonomic Computing

Traditionally, networks and systems management is a manually controlled process. Thus, it is necessary to have a human intervention of one or several operators in order to manage all the aspects concerning the dynamic evolution of a system or a network. The creation of self-management systems with limited human interventions was the vision behind introducing autonomy within the IT environment in order to cope with the increasing complexity and excessive maintenance costs [GRO 02]. Such autonomic systems are able to be self-organized. Thus, networks become a collection of interconnected self-governed entities, where human intervention is limited to high-level directives, and system management details are transparent for the administrators.

The first initiative dealing with this paradigm is inspired by biological systems and, in particular, the autonomic nervous system. Indeed, the term Autonomic Computing is partly owed to the autonomic nervous system [HOR 01]. This management concept is based on a holistic approach, where all research fields are implicated in contributing to the evolution of a global autonomy in networks.

Although the objectives list of the self-management concept was extended after 2001 (year of birth of this new paradigm), the main objectives for autonomic systems are self-configuring, self-healing, self-optimizing and self-protecting [GAN 03]. To achieve these objectives, autonomic systems have a detailed knowledge of their internal state as well as their environment [STE 03], using a continuous monitoring approach to detect eventual changes that could affect their components. Detecting changes induces the autonomic system to adjust its resources, and the monitoring continues to determine if the new measures satisfy the desired performance. That is the closed control loop of self-management systems. It enables autonomic systems to make adequate decisions while conforming to global objectives without human intervention, thanks to measurement data collected from its resources. This closed control loop is implemented by autonomic managers, which control managed resources using the manageability interfaces of sensors and effectors [IBM 05].

10.2.2. Autonomic vehicular communications

Adapting the Autonomic Computing paradigm to transportation systems and in particular to VANET networks in order to enhance the performance of communications within such a changing environment is a challenging task. In Hsu et al. [HSU 10] and Li et al. [LI 12], the authors describe the corresponding challenges, approaches and solutions in ITS. Indeed, they introduce the cooperative communication concept in vehicular networks. These networks should be self-managed thanks to a self-configuration function using decision elements and control loops. Monitoring and policing information will be used within cooperative VANET communications in conformance with the Autonomic Computing concepts in order to enhance vehicle safety.

The research work presented in Wodczak [WOD 12] describes the self-management capability of vehicles in order to perform autonomic cooperative communications and routing within VANETs. The author presents the architecture of an autonomic cooperative node (i.e. vehicle) on the basis of the Generic Autonomic Network Architecture (GANA). This autonomic node includes different decision elements (DE) controlling a managed entity (ME) in order to enhance the performance of Vehicle-to-Vehicle (V2V) communications.

Research challenges concerning inter-vehicular communication (IVC) are presented by Dressler [DRE 11] in four areas. The area dealing with IVC communication principles and patterns discusses the emerging IVC applications such as safety traffic and describes how V2V communications could be used for self-organized traffic control. Insaurralde [INS 12] introduces the autonomic management of autonomous underwater vehicles (AUVs) in order to provide these vehicles with self-maintenance during their missions. An autonomic AUV control architecture is proposed. The objective of this architecture is to achieve the self-management capabilities described by the Autonomic Computing paradigm.

10.3. Broadcasting protocols for VANETs

Broadcasting consists of sending a message from one node to all other nodes within a network. In wireless networks, the coverage area limits of each node restrict the propagation of the radio signal to the nodes located within the transmitter coverage area. In VANETs, wide dissemination of messages can only be ensured if some nodes relay the packets they receive. Moreover, the fact that nodes share the radio channel requires designing broadcasting strategies that minimize the risk of interference. This can be achieved by reducing the number of relays in high-density networks. This reduction should not lead to the interruption of message propagation. Findings a good broadcasting strategy is complex in VANETs (in wireless adhoc networks in general) because the decision of whether or not to relay each message is taken in a decentralized way. This means that none of the nodes have information on the overall network topology. Each decision is taken according to local information.

In the literature, there exist several classifications of broadcasting methods for wireless ad hoc networks [WIL 02, WU 03, STO 04]. Williams and Camp [WIL 02] classify broadcasting methods according to the information used for decision-making (probability, number of redundant copies, neighbor list). Wu and Lou [WU 03] proposed two taxonomies. The first one is based on the type of algorithm used: probabilistic or deterministic. The second classification is based on the amount of state information used in the algorithm: global, quasi-global, quasi-local and local. According to Stojmenovic and Wu [STO 04], broadcasting schemes can be classified using a taxnomy that consists of five categories: determinism, network information, reliability, Hello message content and broadcast message content. In this chapter, the classification of Williams and Camp is used. The broadcasting families are grouped in two main categories: deterministic and stochastic methods (see Figure 10.1).

Figure 10.1. Classification of broadcasting methods

10.3.1. Deterministic methods

A broadcasting method is deterministic if its process is predictable. This group includes simple flooding and neighbor knowledge-based methods.

10.3.1.1. Simple flooding

Simple flooding is the simplest broadcasting method. Every packet is relayed exactly once by each node. Any redundant copy of the packet received later is ignored. Thus, in a network consisting of n nodes, n copies of the packet will be sent. The drawback of this method is that it does not take into account the network density. In high-density networks, the Simple flooding algorithm would generate many redundant copies of broadcasted packets, leading to the overuse of the radio resources.

10.3.1.2. Neighbor knowledge-based methods

Neighbor knowledge-based methods compare neighbor lists before relaying packets. Nodes exchange Hello packets in order to discover the local network topology and to build up their neighbor lists.

Flooding with Self-Pruning [LIM 00] uses a one-hop neighbor list. This list is inserted into the broadcast packets. This allows each receiver to compare its own list to the one included in this packet. If the lists are identical, the packet is dropped, otherwise the packet is relayed. Other methods such as Distributed Vehicular Broadcast (DV-CAST) [TON 10] and least common neighbor (LCN) [YU 06] also rely on one-hop neighbor lists.

The multi-point relay (MPR) technique [NGU 07] is a neighbor knowledge-based broadcasting method. To reduce the number of redundant packets in the network, each node chooses several nodes among its neighbors that will relay its communications. The selected nodes are called MPRs. The MPRs are selected among the one-hop neighbors so that they enable reaching all two-hop neighbors. The goal is to have the smallest list of MPRs in the network, which optimizes communications. This method requires a bidirectional link. When a node sends a packet, all of its neighbors receive it, but only the MPRs of the source node will relay the message. Thus, each node will have a list of all the nodes that have chosen it as a relay (MPRs selectors’ list).

Scalable Broadcast Algorithm (SBA) [PEN 00] uses topology information within two hops. When a node, which runs SBA, receives a broadcast packet, it uses the source identifier (the node that originates the packet or the last relay node) and its neighbor list to determine all additional nodes (N) in its neighborhood that would receive the packet if it is relayed. If N is empty, the packet is dropped. Otherwise, the node sets a timeout called RAD (Random Assessment Delay). If it receives another copy of the same packet, N is recalculated. On expiry of the RAD timer, the packet is relayed if N is not empty. To optimize this algorithm, the authors advise calculating the waiting time (t) so that nodes with many neighbors are prioritized (see equation 10.1):

where n is the number of neighbors of the receiver and Nmax is the maximum “n” of the receiver’s neighbors.

For static or low mobility networks, neighbor knowledge-based methods can achieve good performance. However, in high-mobility networks, like VANETs, information about the neighbors becomes inaccurate rapidly. Thus, this family of methods is hardly applicable for vehicular networks.

10.3.2. Stochastic methods

The stochastic methods statistically assess the gain that could be obtained if the packets are relayed by a given node. They include probabilistic scheme, counter-based and location-based methods.

10.3.2.1. Probabilistic methods

To avoid the broadcast storm problem [NI 99] and adjust broadcasting strategies depending on the network density, probabilistic methods mainly use a parameter that serves to relay (or not relay) each received packet. In fact, for a given network density, there exists ps, a probability threshold value (0 ≤ ps1), which would allow all nodes to receive the packets, reducing the number of unnecessary repetitions and leading to few collisions. Any other value p > ps would not lead to better coverage, but may downgrade the quality of the communication. As ps varies locally in the network, the main challenge of the probabilistic methods is to determine its correct value. Some approaches to dynamically assign value to ps are proposed in the literature. They combine probabilistic methods with some other techniques for assessing the network density (e.g. counter-based or distance-based methods).

Optimistic Adaptive Probabilistic Broadcast (OAPB) [ALS 05] adapts the probability of each vehicle according to its number of neighbors within two hops. This allows the protocol to adjust the broadcasting strategies to local densities. The neighborhood of each vehicle is discovered thanks to Hello packets. Smart-flooding [ABD 12a] also aims to adapt the broadcasting probability to the local density. In addition to the probability, this protocol introduces several other parameters such as the number of retransmissions for each packet and the delay between successive retransmissions. To achieve good tuning of these parameters for various density levels, the authors have used a genetic algorithm. It is important to note that Smart-flooding does not use Hello packets to evaluate the local density. It takes advantage of traditional exchanges between nodes to estimate the number of neighbors for each node.

10.3.2.2. Counter-based methods

The principle of the counter-based methods is simple: the more copies of the same packet a node receives, the less likely that it is useful to relay this packet. Upon reception of the first copy, the node initializes a counter C to 1 and sets a timeout RAD (Random Access Delay). During the waiting period, C is incremented upon reception of a new copy of the packet. When the RAD expires, C is compared to a threshold value, Ct. If C < Ct, the packet is broadcast, otherwise it is dropped. Like probabilistic methods, one challenge is to find an appropriate value for Ct. Ni et al. [NI 99] demonstrated that the additional area covered by the broadcasting process decreases significantly when the number of redundant copies increases.

Bani Yassein et al. [BAN 07] proposed the Smart Counter-Based Broadcast Algorithm that adapts Ct according to the network density. Thanks to Hello packets, the nodes build neighbor lists. The size of these lists allows dynamically adjusting Ct. Karthikeyan et al. [KAR 10] introduced a method named Density-Based Flooding Algorithm. This method defines two categories of nodes according to their number of neighbors with respect to a given threshold, τ. Each node decides to relay each packet depending on its own category and the one of the packet’s last hop.

10.3.2.3. Location-based methods

Before relaying a message in the context of location-based methods, the node evaluates the additional coverage area that will result from this retransmission. These methods do not consider whether nodes exist within that additional area or not. AckPBSM [ROS 09] and POCA [NAN 10] use this approach and set lower RAD to nodes that are far from the source node (or last-hop relay node). To evaluate the extra coverage area, the node can use the distance between itself and each node that has previously relayed the message (distance-based scheme) or the geographical coordinates (location-based scheme). In both distance-based and location-based schemes, a RAD timeout is set, and the message is relayed if the additional coverage area is higher than a fixed threshold.

10.4. Autonomic broadcasting within VANETs

After a description of the Autonomic Computing paradigm and some applications of its concepts within VANETs, we detailed the state of the art concerning the use of broadcasting protocols within VANETs. In the following sections, we present a study concerning the application of Autonomic Computing concepts to an example of these broadcasting protocols within VANETs. Thus, a self-management architecture is specified to enable QoS-based autonomic broadcasting while demonstrating that such kind of broadcasting is an optimization problem in VANETs’ environment.

10.4.1. Optimization of broadcasting protocols in VANETs

Designing an efficient broadcasting protocol requires meeting several objectives that could be antagonistic: for instance, transmitting messages to the maximum of nodes while avoiding the overuse of the radio channel and delivering packets as quickly as possible, knowing that this speed may cause radio interferences. In a nutshell, this is clearly a multi-objective optimization problem for which each solution is a set of parameters that defines a broadcasting strategy. Depending on the protocol to optimize, the parameters could be a probability, the boundaries of the RAD, some thresholds, etc.

In [ABD 12a], the authors define a broadcasting strategy as a set of four parameters:

  1. – the probability of relaying a packet (P). It is inherited from the classical probabilistic methods. When a node receives the first copy of a broadcast packet, it decides to relay it or not, depending on the value of P. The following three parameters are applicable only if the node decides to relay the packet.
  2. – the number of repetitions (Nr). In low-density networks, when a node broadcasts a packet, it is not unusual that it has no neighbor in its coverage area that will receive the message and relay it. Sending the packet several times, particularly in a context of mobility, the node increases the chance that the packet will be received and relayed. Nr is also useful when the first transmitted packet is lost due to a collision or poor radio propagation quality.
  3. – the delay between two successive repetitions (Dr). When a node transmits the same packet several times (Nr > 1), it is important to determine the frequency with which the copies of the same packet will be transmitted. A very short delay could result in many collisions, whereas a very long delay may slow down the broadcast.
  4. – the packet’s lifetime. It allows a limited spread of packets within the network and/or for a long period of time. The maximum number of hops allowed for each packet, TTL (Time To Live), could be used in the context of broadcasting protocols. Geographical coordinates or transmission time can replace this parameter.

These parameters allowed the authors to tune their protocol named Smart-flooding. The optimization process of the broadcasting strategies defined by these parameters (P, Nr, Dr and TTL) was carried out using four criteria:

  1. – the average Number of Collisions (NC);
  2. – the Propagation Time (PT). This is the time between the transmission of a packet and its reception by all nodes of the studied area;
  3. – the total number of Retransmissions during the simulation (R);
  4. – the Full Reception ratio (FR). This refers to the guarantee that the broadcast packets will be received by all nodes (the reachability). A simulation in which all nodes receive the packet is considered successful. On the contrary, if the network conditions (propagation or topology) do not allow the reception of the packet by all nodes, the simulation is considered as a failure. FR is the ratio of the number of successes on the total number of repetitions of each scenario executions.

The first three criteria are to be minimized, while FR is to be maximized. NC and R enable measuring the radio channel usage: high values indicate that the evaluated strategy is likely to interfere with other communications in the network. The calculation of NC, PT and R takes into account successful simulations only.

10.4.2. Self-management architecture

To be efficient, broadcasting protocols in VANETs should adapt their communication strategies according to not only the network density but also the priority level of the message that has to be disseminated. Such protocols can be specified using the closed control loop implemented by an autonomic manager within a mobile node (vehicle). The latter is considered a managed resource according to Autonomic Computing concepts presented in section 10.2.1. The resulting architecture, enabling broadcasting strategy optimization according to VANETs’ environment characteristics and change occurrence, is detailed below.

A self-management approach of radio communications ensures the robustness of a broadcasting protocol. Indeed, each node (i.e. vehicle) is considered to be an autonomic element thanks to an autonomic manager that enables broadcasting decision-making according to the message priority level and takes into account environment changes in terms of density level (an example is given in section 10.5.1). To achieve those goals, the autonomic manager implements the MAPE-K closed control loop (see Figure 10.2) and communicates with the Managed Element mobile node using Sensors and Effectors manageability interfaces.

Figure 10.2. Autonomic manager closed control loop

Each autonomic node within a VANET continuously monitors its environment and network traffic by listening to the radio channel and provides the Monitor function (M) of the Autonomic Manager with network traffic information thanks to the Sensors manageability interface. In the self-management architecture presented in Figure 10.2, the Knowledge base should contain efficient parameters in order to enable the corresponding broadcasting strategies.

In the context of a broadcasting protocol, the Monitor determines if the received packet is a broadcasting one thanks to its destination address. In the case of a broadcasting message, the Monitor provides the Analyze function (A) with this information to follow the control loop process.

The Analyze function determines not only the priority level of the message according to the packet header information but also the current density level of the node environment (which can be evaluated using Hello packets or data packet as in the case of Smart-flooding). This information could be stored in the Knowledge base (K) of an autonomic manager.

After the evaluation of the density level, the Plan function (P) will use the density and priority values provided by the Analyze function to retrieve the adequate broadcasting strategy from the Knowledge base (K) thanks to the strategy table created by the optimization offline phase (see section 10.5.1.3). Then, the Plan function will provide the Execute function (E) with the broadcasting parameters (P, Nr, Dr and TTL in case of Smart-flooding or ADM described in section 10.5.1) in order to change the behavior of the mobile node-managed resource by executing the corresponding actions of broadcasting strategy thanks to the Effectors manageability interface.

The self-management architecture enables the Autonomic Manager to determine how to adapt the broadcasting strategy based on the information reported by the Sensors manageability interface. Each of the four functions (MAPE) corresponding to the Autonomic Manager has a specific role; however, all share the same Knowledge base. The latter contains a set of broadcasting strategies optimized for various contexts corresponding to different density and priority levels that we describe in the following section dealing with QoS-based broadcasting.

10.4.3. QoS-based broadcasting

Several recent research works in VANETs and their applications highlight the need to classify messages into several classes [VEG 13, KAM 10, SUT 07]. Processing these messages depends on many criteria, such as their emergency level, their impact on the road-traffic management or the desired reachability.

In this context, three message classes can be defined for broadcast operations in VANETs (corresponding to three priority levels). Each class should satisfy a broadcast policy. These classes may be based on a single or a dual objective and may also consider other broadcast characteristics, that is, the covered nodes ratio evolution over time. These policies mainly illustrate the adaptability of a broadcasting protocol to the message contents and hence can be easily redefined or extended with additional classes.

High-level priority messages (HL for short) correspond to emergency messages, for example, safety message or accident detection. They have to be delivered as quickly as possible as they may require a prompt reaction from the driver. For these messages, a broadcasting protocol tries to minimize the required propagation time so that vehicles that are close to the broadcast source may receive the message with a very short delay. Indeed, safety messaging is a near-space application where vehicles in close proximity exchange information to increase safety awareness [VEG 13]. These applications have strict latency constraints. In addition to the reduction of the propagation, the autonomic broadcasting method will try to maximize the full reception ratio.

Medium-level priority messages (ML) correspond to road-traffic messages, for example, traffic jam report. They suppose less critical information, where driving reflexes are not part of the equation and only attention is required. These messages should cover a high ratio of nodes, while the broadcast operation requires reducing the number of radio interferences. According to [VEG 13], traffic monitoring applications require gathering information from vehicles that span multiple kilometers.

Low-level priority messages (LL) correspond to comfort messages, for example, weather information, tourist attraction or points of interest. They are optional messages whose delivery must not alter the dissemination of emergency and alert messages. The use of the radio resources has to be optimized, by reducing the number of collisions as well as the number of retransmissions, for an acceptable node coverage ratio.

Table 10.1 summarizes the classes considered in this study.

Table 10.1. Message priority levels

10.5. Simulation of a QoS-based communication model

In this section, we first introduce a broadcasting protocol that is inspired from Autonomic Computing paradigm. Thereafter, we present the results of that protocol.

10.5.1. ADM: autonomic dissemination method

10.5.1.1. Overview

The ADM is an extension of the Smart-flooding protocol [ABD 12a]. ADM is an autonomic robust broadcasting method, which adapts its broadcasting strategies with respect to the network density and message priority level. Its architecture is described in Figure 10.3.

Figure 10.3. Global flowchart of ADM. For a color version of this figure, see www.iste.co.uk/hilt/transportation.zip

ADM relies on an offline optimization process that aims to supply the autonomic manager’s Knowledge base module with good broadcasting strategies. Indeed, we optimize the parameters P, Nr, Dr and TTL using an approach that combines an optimizer, a network simulator and a trace analyzer. Figure 10.3 illustrates the interaction of these three modules. P, Nr, Dr and TTL are optimized using HOPES (Hybrid Optimization Platform using Evolutionary Algorithms and Simulations) [ABD 12a]. HOPES combines an optimizer, a network simulator and a trace analyzer.

The optimizer used is our proposed genetic algorithm aGAME [ABD 12b]. The decision variables of the problem are P, Nr, Dr and TTL. They are the different genes defining a solution (a broadcast strategy). The genetic algorithm is used to traverse the search space effectively. The optimization process starts with the random generation of the initial population (P0). The evaluation stage is split into two steps: the first one performed by the network simulator and the second one by the genetic algorithm.

Broadcast parameters (P, Nr, Dr and TTL) are transmitted to the network simulator, which integrates them with other parameters in order to better reproduce the conditions of the evaluated network. The trace files generated during the simulation are then transmitted to the analyzer module. It parses the files in order to extract the evaluation criteria values (NC, PT, R and FR) and presents the obtained results according to the required format of the genetic algorithm.

When the genetic algorithm receives the results of the trace analyzer module, it proceeds to the second step of the evaluation in order to classify solutions and assign values of fitness. To penalize solutions, which do not guarantee the full reception of transmitted packets, a constraint is associated with the problem: FR must be greater than or equal to a reachability threshold (FRs).

The remaining operations of the genetic algorithm are performed independently of the problem. At each iteration, the three modules are involved in the evaluation task. The second test of the optimization module denoted by “P0?” checks whether the current population is the initial population. The overall optimization process leads to a set of non-dominated solutions corresponding to dissemination strategies adapted to the considered network density. This study is repeated for several densities by changing the corresponding parameter in the simulation module.

From the results of this offline optimization phase, a broadcasting protocol such as ADM builds a knowledge base that establishes a correspondence between density levels and broadcasting strategies. Density levels are represented by the number of neighboring intervals. Each node can therefore choose, depending on the density of the network in which it is located, the appropriate dissemination strategy. Then, depending on the probability of retransmission associated with the chosen strategy, the node decides whether or not to relay the packet. If the decision is to relay the communication, it applies the other corresponding parameters (Nr, Dr and TTL).

10.5.1.2. Density evaluation

In classical approaches, the density around a node i is often calculated by counting the number of nodes (Ni) located within the coverage area of i. These methods are based on the assumption that all nodes have uniform and identical coverage areas. This is usually the case when the radio propagation model is deterministic, such as free-space or two-ray ground reflection. However, for a more realistic model, where packet losses are distributed according to the distance between the transmitter and receiver, this definition is impractical. ADM evaluates the local density for each autonomic node on the basis of the number of active neighbors from which it received the packets. During communication, each node builds a view of its neighborhood. This view depends on the neighbor list having transmitted or relayed packets. Each autonomic node maintains a history in which it associates with each received packet a list of nodes having sent or relayed it. Upon reception the first copy of a packet, its identifier and the source/relay address are recorded within the autonomic manager Knowledge base in a table called local view. When a redundant copy is received, the address of the new relay is appended to the local view table list of addresses (L) corresponding to the packet. Each address is recorded only once for each packet; hence, receiving multiple copies issued by one neighbor does not lengthen the list of addresses for the concerned packet. When the table is full, the oldest information is replaced by the new one according to the FIFO (First In, First Out) principle. The current number of neighbors (Ni) for each autonomic node i is equal to the average number of transmitters for all the packets stored in L (see equation 10.2):

where n is the total number of packets in the local view table and |L(j)| is the number of nodes that issued/relayed the jth packet in the table.

10.5.1.3. Calibration

We run the optimization process in order to find good broadcasting strategies that will be used by ADM for various network density levels. In this section, we show values for four density levels. We consider as a topology model a convoy of vehicles lined up for 10 km. To illustrate different density levels, we varied the inter-vehicle distance. Table 10.2 shows the parameters of the topology used for different density levels.

As in most multi-objective problems, the optimization process returns as a result of several potential solutions that offer a compromise between the different objective functions (NC, PT, R, FR). To refine the obtained results, we used a multiple-criteria decision-making approach based on preferences.

Table 10.2. Topology parameters for different network density levels

For sending high-priority messages, we select the solution that allows delivering packets as quickly as possible while covering the largest number of nodes in the network. For medium-priority messages, the first criterion taken into account is reachability (FR). Then, among the solutions that have an FR value almost equal to 1 (the maximum), we select the one which causes the least collision. Finally, for low-priority messages, the goal is to send packets while slightly using the wireless channel. The first and second criteria are, respectively, NC and R. The broadcasting parameters for the three priority levels and the objective functions values corresponding to various density levels are presented in Tables 10.310.6, respectively, for high-, medium-, low- and very low-density networks. For each scenario, we use one source node located at the end of the convoy of vehicles. Scenarios with multiple source nodes are discussed in section 10.5.3.

Table 10.3. ADM’s parameters and performance results for a high-density network

Table 10.4. ADM’s parameters and performance results for a medium-density network

In high-density networks, the probability of relaying the packets is low (see Table 10.3). When Nr = 1, the Dr cell (the delay between successive repetitions) has been shaded, as this parameter is only applicable when Nr > 1. For high-priority messages (in a high-density network), relaying each packet only once, a probability of about 0.3, allows rapid dissemination of the message. However, this probability value generates a large number of collisions. This drawback is mended for medium-priority messages. To reduce the number of collisions and increase the reachability (FR), we selected a solution with a lower probability and number of repetitions equal to 2. Moreover, as the repetitions are not made in burst, the risk of interference is reduced.

For low-priority messages, it is worth noting that the results only concern the packets that have been received by all vehicles. In other words, 86.8% of packets that are received spread quickly (due to low competition in the access to the radio channel), but 13.2% of them are not completely delivered.

Following the same reasoning, we obtain the broadcasting parameters for suburban and highway scenarios (Tables 10.4 and 10.5, respectively).

For the scenario of the rural area, the low-density level of the network implies the need to retransmit each packet many times (see Table 10.6). Indeed, in this scenario, VANETs behave like delay tolerant networks (DTNs) [PAR 12]. In such a context, since the radio channel is rarely used, even if ADM is able to differentiate broadcasting strategies according to the message class, in practice, these classes scarcely impact the communication process. The main constraints that must be met are: obtaining a probability (P) close to 1 and a high number of repetitions (Nr).

Table 10.5. ADM’s parameters and performance results for a low-density network

Table 10.6. ADM’s parameters and performance results for a very low-density network

10.5.2. Simulation environment

This section describes the simulation parameters that are used to compare ADM with some broadcasting methods in the literature.

The simulations were carried out using the ns-2 network simulator (2.34 version) with the Shadowing Pattern propagation model [DHO 06]. It is a realistic and probabilistic propagation model, which can produce distributions of statistical errors, such as slow and fast fading, while being easy enough to be carried out on medium to large simulations.

Figure 10.4 shows the simulated network topology, which consists of three main areas. The first zone is the main road where the average speed is 130 km/h. In the second area, the average speed is 90 km/h. Finally, the third area tallies with an urban network, where the average speed is 50 km/h. These speeds correspond to the maximum speed in France, respectively, on highways, on back roads and in urban areas. We used a mobility model that redirects vehicles at every intersection to maintain the average density (average number of neighbors) required in each area (see Figure 10.4). In addition, the low velocity within the third zone leads to an increase in the density in this part of the network.

Figure 10.4. Network topology. For a color version of this figure, see www.iste.co.uk/hilt/transportation.zip

For these experiments, we simulated a network consisting of 600 vehicles. The simulation duration is set to 10 min. This duration allows each vehicle to move across areas and therefore to change density levels.

Packets are sent every 5 s. This allows evaluating the robustness of ADM with respect to the network traffic. At each sending phase, there is a concurrent access to the radio channel because there are several source vehicles (between 3 and 30 sources, depending on the scenario).

10.5.3. Performance evaluation

We evaluate the performance of ADM in a network where the density varies according to geographical locations. The aim is to assess the ability of the ADM to adapt to density changes thanks to different broadcast strategies provided by the Knowledge base of the corresponding Autonomic Manager (see Figure 10.3).

Figure 10.5. Propagation time. For a color version of this figure, see www.iste.co.uk/hilt/transportation.zip

The performances of communication protocols in mobile and heterogeneous density networks depend on their ability to dynamically adapt to changes in their environment. The results in Figures 10.510.7 clearly show that the lack of an adaptation mechanism to the density level leads to a poor performance of the Simple flooding method. Its propagation time when there are more than 18 simultaneous source nodes is at least 1 s (see Figure 10.5). This delay can be detrimental for emergency messages. Moreover, we can observe that in case of concurrent access to the radio channel, Simple flooding is struggling to deliver packets across the network (see Figure 10.6). This low reachability ratio is due to the collisions caused by redundant packets, especially in high-density areas (see Figure 10.7).

Regarding the two protocols that are able to adapt to the density, we observe that ADM has better performance results than Smart-flooding. These differences are due to the fact that Smart-flooding underestimates the network density by using a theoretical approach. ADM is not only based on this theory, but also uses experimental results.

In general, ADM delivers emergency packets in less than 700 ms in a relatively large area (even with 30 source nodes). This allows being in conformance with the limits of drivers’ reaction upon alerts. Besides, for medium-priority messages (for instance, road-traffic regulation), which should be received by a maximum of nodes, ADM has a reachability ratio of almost 75%, while Smart-flooding has 66% and Simple flooding 53% in the scenario with 30 sources.

Figure 10.6. Delivery ratio. For a color version of this figure, see www.iste.co.uk/hilt/transportation.zip

Figure 10.7. Collisions. For a color version of this figure, see www.iste.co.uk/hilt/transportation.zip

10.6. Conclusion

This chapter presented an application of the Autonomic Computing paradigm in VANET’s communication. This approach allows building robust protocols. In this context, the design of ADM is detailed as a usage case of self-management concepts in VANETs’ environment thanks to the adaptation of this method and the specification of an autonomic QoS-based broadcasting protocol.

ADM uses the obtained pre-computed broadcasting strategies thanks to an evolutionary algorithm. Each node is able to dynamically adapt its own broadcast parameters to the network density and to the message class corresponding to a priority level. The results of the simulations carried out on both homogeneous and heterogeneous density-level networks show that ADM outperforms two other broadcasting methods: the Smart-flooding protocol and the Simple flooding method. These results also reveal the scalability of ADM when the number of simultaneous transmissions significantly increases while using different message classes. Despite only considering three message classes, ADM can be easily adapted to include other message classes. These new classes will enable different features and characteristics to take into account other VANETs communication usage and interactions with the infrastructure.

10.7. Bibliography

[ABD 12a] ABDOU W., BLOCH C., CHARLET D. et al., “Designing smart adaptive flooding in MANET using evolutionary algorithm”, Mobile Wireless Middleware, Operating Systems, and Applications: 4th International ICST Conference, pp. 71–84, 2012.

[ABD 12b] ABDOU W., BLOCH C., CHARLET D. et al., “Adaptive multi-objective genetic algorithm using multi-paretoranking”, 14th International Genetic and Evolutionary Computation Conference, Philadelphia, PA, pp. 449–456, 2012.

[ALS 05] ALSHAER H., HORLAIT E., “An optimized adaptive broadcast scheme for inter-vehicle communication”, 2005 IEEE 61st Vehicular Technology Conference, vol. 5, pp. 2840–2844, 2005.

[BAN 07] BANI YASSEIN M., AL-HUMOUD S., OULD KHAOUA M. et al., “New Counter Based Broadcast Scheme Using Local Neighborhood Information in MANETs”, University of Glasgow, Department of Computing Science, 2007.

[DHO 06] DHOUTAUT D., REGIS A., SPIES F., “Impact of radio propagation models in vehicular ad hoc networks simulations”, VANET ‘06 Proceedings of the 3rd International Workshop on Vehicular ad hoc Networks, pp. 40–49, 2006.

[DRE 11] DRESSLER F., KARGL F., OTT J. et al., “Research challenges in intervehicular communication: lessons of the 2010 Dagstuhl seminar”, IEEE Communications Magazine, vol. 49, no. 5, pp. 158–164, 2011.

[GAN 03] GANEK A.G., CORBI T.A., “The dawning of the autonomic computing era”, IBM System Journal, vol. 42, no. 1, pp. 5–18, 2003.

[GRO 02] GROUP Y., How Much is an Hour of Downtime Worth to You?, Must-know Business Continuity Strategies, pp. 178–187, 2002.

[HOR 01] HORN P., Autonomic Computing: IBM’s Perspective on the State of Information Technology, IBM Corporation, 2001.

[HSU 10] HSU I.Y.-Y., WÓDCZAK M., WHITE R.G. et al., “Challenges, approaches, and solutions in intelligent transportation systems”, 2010 Second International Conference on Ubiquitous and Future Networks (ICUFN), Jeju island, pp. 366–371, 2010.

[IBM 05] IBM, An architectural blueprint for autonomic computing, Technical report 3rd ed., IBM, Hawthorne, available at: http://www03.ibm.com/autonomic/pdfs/ACBlueprintWhitePaperV7.Pdf, 2005.

[INS 12] INSAURRALDE C., “Autonomic management for the next generation of autonomous underwater vehicles”, IEEE/OES Autonomous Underwater Vehicles (AUV), Southampton, pp. 1–8, 2012.

[JAF 12] JAFFAR S., SUBRAMANYM M.V., “Broadcasting methods in mobile ad hoc networks: taxonomy and current state of the art”, Global Journal of Computer Science and Technology, vol. 12, no. 1, pp. 59–65, 2012.

[KAM 10] KAMINI R.K., “Vanet parameters and applications: a review”, Global Journal of Computer Science and Technology, vol. 10, pp. 72–77, 2010.

[KAR 10] KARTHIKEYAN N., PALANISAMY V., DURAISWAMY K., “Optimum density based model for probabilistic flooding protocol in mobile ad hoc network”, European Journal of Scientific Research, vol. 39, no. 4, pp. 577–588, 2010.

[LI 12] LI J., WÓDCZAK M., WU X. et al., “Vehicular networks and applications: challenges, requirements and service opportunities”, International Conference on Computing, Networking and Communications (ICNC), Maui, Hawaii, pp. 660–664, 2012.

[LIM 00] LIM H., KIM, C., “Multicast tree construction and flooding in wireless ad hoc networks”, Proceedings of the 3rd ACM International Workshop on Modeling, analysis and Simulation of Wireless and Mobile Systems, pp. 61–68, 2000.

[NAN 10] NA NAKORN N., ROJVIBOONCHAI K., “POCA: position-aware reliable broadcasting in VANET”, 2nd Asia-Pacific Conference of Information Processing (APCIP), pp. 17–18, 2010.

[NGU 07] NGUYEN D., MINET P., “Analysis of MPR selection in the OLSR protocol”, International Conference on Advanced Information Networking and Applications Workshops, vol. 2, pp. 887–892, 2007.

[NI 99] NI S.-Y., TSENG Y.-C., CHEN Y.-S. et al., “The broadcast storm problem in a mobile ad hoc network”, MobiCom ‘99: Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking, pp. 151–162, 1999.

[PAR 12] PARIDEL K., BALEN J., BERBERS Y. et al., “VVID: a delay tolerant data dissemination architecture for VANETs using V2V and V2I communication”, The Second International Conference on Mobile Services, Resources, and Users, MOBILITY 2012, pp. 151–156, 2012.

[PEN 00] PENG W., LU X.-C., “On the reduction of broadcast redundancy in mobile ad hoc networks”, Proceedings of the 1st ACM International Symposium on Mobile ad hoc Networking & Computing (MobiHoc’00), pp. 129–130, 2000.

[ROS 09] ROS F.J., RUIZ P.M., STOJMENOVIC I., “Optimum density based model for probabilistic flooding protocol in mobile ad hoc network”, 69th IEEE Vehicular Technology Conference (VTC Spring 2009), pp. 1–5, 2009.

[STE 03] STERRITT R., BUSTARD D.W., “Towards an autonomic computing environment”, DEXA Workshops, Prague, Czech Republic, pp. 699–703, 2003.

[STO 04] STOJMENOVIC T., WU J., “Broadcasting and activity-scheduling in ad hoc networks”, in STOJMENOVIC I. (ed.), Ad Hoc Networking, IEEE Press, 2004.

[SUT 07] SUTHAPUTCHAKUN C., GANZ A., “Priority Based Intervehicle Communication in Vehicular Ad-hoc Networks Using IEEE 802.11e”, IEEE VTC Spring, pp. 2595–2599, 2007.

[TON 10] TONGUZ O.K., WISITPONGPHAN N., BAI F., “DV-CAST: a distributed vehicular broadcast protocol for vehicular ad hoc networks”, IEEE Wireless Communications, vol. 17, no. 2, pp. 47–57, 2010.

[VEG 13] VEGNI A.M., BIAGI M., CUSANI R., “Smart vehicles, technologies and main applications in vehicular ad hoc networks”, available at: http://www.intechopen.com/books/export/citation/BibTex/vehiculartechnologies-deployment-and-applications/smartvehiclestechnologies-and-main-applications-in-vehicular-ad-hoc-networks, 2013.

[WIL 02] WILLIAMS B., CAMP T., “Comparison of broadcasting techniques for mobile ad hoc networks”, Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), pp. 194–205, 2002.

[WOD 12] WODCZAK M., “Autonomic cooperative networking for vehicular communications”, 11th International Conference on Ad-Hoc, Mobile, and Wireless Networks Service, ADHOC-NOW’12, pp. 112–125, 2012.

[WU 03] WU J., LOU W., “Forward-node-set-based broadcast in clustered mobile ad hoc networks”, Wireless Communication and Mobile Computing, vol. 3, pp. 155–173, 2003.

[YU 06] YU S., CHO G., “A selective flooding method for propagating emergency messages in vehicle safety communications”, 2006 International Conference on Hybrid Information Technology, pp. 556–561, 2006.

Chapter written by Nader MBAREK, Wahabou ABDOU and Benoît DARTIES.