Bee life-based multi constraints multicast routing optimization for vehicular ad hoc networks

https://doi.org/10.1016/j.jnca.2012.01.023Get rights and content

Abstract

A vehicular ad hoc network (VANET) is a subclass of mobile ad hoc networks, considered as one of the most important approach of intelligent transportation systems (ITS). It allows inter-vehicle communication in which their movement is restricted by a VANET mobility model and supported by some roadside base stations as fixed infrastructures. Multicasting provides different traffic information to a limited number of vehicle drivers by a parallel transmission. However, it represents a very important challenge in the application of vehicular ad hoc networks especially, in the case of the network scalability. In the applications of this sensitive field, it is very essential to transmit correct data anywhere and at any time. Consequently, the VANET routing protocols should be adapted appropriately and meet effectively the quality of service (QoS) requirements in an optimized multicast routing. In this paper, we propose a novel bee colony optimization algorithm called bees life algorithm (BLA) applied to solve the quality of service multicast routing problem (QoS-MRP) for vehicular ad hoc networks as NP-Complete problem with multiple constraints. It is considered as swarm-based algorithm which imitates closely the life of the colony. It follows the two important behaviors in the nature of bees which are the reproduction and the food foraging. BLA is applied to solve QoS-MRP with four objectives which are cost, delay, jitter, and bandwidth. It is also submitted to three constraints which are maximum allowed delay, maximum allowed jitter and minimum requested bandwidth. In order to evaluate the performance and the effectiveness of this realized proposal using C++ and integrated at the routing protocol level, a simulation study has been performed using the network simulator (NS2) based on a mobility model of VANET. The comparisons of the experimental results show that the proposed algorithm outperformed in an efficient way genetic algorithm (GA), bees algorithm (BA) and marriage in honey bees optimization (MBO) algorithm as state-of-the-art conventional metaheuristics applied to QoS-MRP problem with the same simulation parameters.

Introduction

Many research and technologies are increasingly very interested to design new intelligent transportation systems for the improvement of safety road. One of the most important intelligent transportation systems is the vehicular ad hoc networks (VANETs). It is a special kind of mobile ad hoc networks (MANETs) with the distinction property that the nodes are vehicles which move according to a restricted mobility pattern based on many factors like road course, encompassing traffic and traffic regulations (Plößl and Federrath, 2008). VANET aims to provide communications among vehicles via Inter-Vehicle Communication (IVC) and between vehicles and fixed equipments described as roadside base stations via Roadside-to-Vehicle Communication (RVC) which can be found along the road (Bitam and Mellouk, 2011) and will be deployed at critical locations like slip roads, service stations, dangerous intersections or places well-known for hazardous weather conditions (Scheuer et al., 2008). It is characterized by a very high mobility and an important speed variation of vehicles which lead to a very fast and frequent network topology changes (Ledy et al., 2009).

The principle VANET’s purpose is to ensure the road safety and applications to provide comfort for vehicle drivers. In this way, the vehicles act as communication nodes which exchange data to ensure the collision prevention and accident warning, services providing as traffic information, breakdown and fuel services, office locations etc. Therefore, the integration of multimedia services and real time applications are mandatory in vehicular ad hoc network nodes. Because of their sensibilities and vitalities, these applications require in one hand, transmissions with high level of quality of service. The most important QoS requirements are the cost, delay, jitter and bandwidth. In the other hand, vehicles can work in group which is formed dynamically to perform a shared task, such as driving strategy. This kind of data transmission is known as multicast routing, since it enables a source node to send data packets to multiple destinations concurrently (Huang et al., 2010). It sends the packet only once and then it is duplicated and sent to different multicast group members. The multicast routing reduces the communication cost and exploits strongly the bandwidth and network resources, since the data packets can be transmitted to all destinations (multicast group members) towards a single transmission, while the unicast routing in which the source transmits sequentially the same packet several times to different destinations.

In this paper, the multicast routing problem with quality of service (QoS-MRP) for vehicular ad hoc networks is studied as combinatorial optimization belongs to the NP-Complete class.

The main goal is to find the optimal tree called multicast tree from the source to the destinations (multicast group nodes) with the minimum cost, the reduced delay, the decreased jitter and the maximum bandwidth as four objectives. Besides, the expected tree should respect three QoS constraints requested by the transmission applications which are an allowed delay and jitter and a minimum of bandwidth.

To solve this problem, a new metaheuristic called Bees Life Algorithm (BLA) is proposed. As a one of the specie colony optimization, BLA is considered as a swarm intelligence algorithm and an approximate optimization method which performs according to collaborative individual behaviors in the population. It imitates closely the life of the colony and follows the two important behaviors in the nature of bees which are the reproduction and the food foraging.

As QoS-MRP is a NP-complete problem, several metaheuristic methods have been employed to solve this problem which can be classified into five categories of optimization methods: Genetic Algorithm (GA), Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO), Artificial Neural Networks (ANN) and Tabu Search (TS) research activities. GA is the most used in this context. We mention the work proposed in Haghighat et al. (2003) which proposed a novel QoS-based multicast routing algorithm based on the genetic algorithms. Authors proposed connectivity matrix of edges for representation of the Steiner trees and they considered a fitness function based on the total cost, the total delay and the minimum bandwidth of a path using the penalty technique. The paper results were compared with others obtained by previous GA-based algorithms and showed the superiority of this proposal. Wang et al. (2006) investigated QoS-Multiple constrained optimization problem for mobile networks in multimedia group communications. Authors developed a unified framework for achieving QoS multicast trees using intelligent computational methods and proposed three algorithms based on Genetic Algorithm, Simulated Annealing and Tabu Search metaheuristics. Only two constraints are considered in this works: the network resource requirements and the end-to-end delay model for multimedia. The obtained results showed that GA provides the best performance in terms of the solution quality. In the literature, a multiple constraints QoS multicast routing optimization algorithm in MANET based on GA applied to MANET can be found (Sun et al., 2008). It optimizes the maximum link utilization, the cost of the multicast tree, the selection of the long-life path, and the average delay and the maximum end-to-end delay. Although the performance evaluation of this algorithm demonstrated its accuracy and efficiency for the route stability in MANETs, further elaboration is required which will study the QoS requirements like cost, delay, jitter and bandwidth. To improve the computing performance for the QoS multicast routing in terms of cost, Zhang et al. (2009) described a genetic algorithm and simulated annealing combined algorithm. The multicast tree chromosomes are represented by a tree structure which is used in a novel initialization method to prevent tree loops. Authors considered in the objective function the cost, delay, delay-jitter and bandwidth metrics and they showed that the proposed algorithm possesses fast convergence and excellent cost performance against genetic immune algorithm (GIA) and genetic simulated annealing algorithm with integral sequence encoding method (ISGSA). Yen et al., (2011) proposed a multi-constrained QoS multicast routing method using the genetic algorithm for mobile ad hoc networks. It is flooding-limited using the available resources and minimum computation time in a dynamic environment. Simulation results indicated the better performances of this proposal compared to E2MRP and ODMRP protocols. QoS-Multiple constrained optimization problem has been solved using Ant Colony Optimization (ACO) algorithm. Tseng et al., (2008) examined the degree and delay-constrained broadcasting problem with minimum-cost by an ant colony-based algorithm. After simulations and comparisons with previous Ant algorithm TCA, and to two GA-based algorithms (WGA) and (CGA), the obtained results exhibited the best cost but with too long computation time. Another ACO-based algorithm to solve the QoS multicast routing as non-linear combinatorial optimization problem has been proposed in Wang et al. (2011). It aimed at finding a multicast routing tree with minimal cost that can satisfy bandwidth, delay, and delay-jitter constraints. It generates a multicast tree which is controlled by an ACO algorithm. Although the simulation results showed that the proposed algorithm performs well in searching, converging speed and adaptability scale against other approaches such as GA and TS but it considered only the cost in its function objective. Particle Swarm Optimization (PSO) is also applied to solve QoS-MRP (Huang et al., 2009, Sun et al., 2011). The purpose of Huang et al. (2009) is to attempt to satisfy the QoS requirements in many multimedia applications and to find the appropriate proxy core node in order to reduce control overhead based on the computation result of PSO. A priority scheduler is also incorporated in this work. On the basis of the packet delivery ratio, the end-to-end delay and the overhead, the proposed approach has been compared successfully with ODMRP, DCMP, and MPSP protocols. This study can be extended to take into account other important parameters such as the cost, jitter and bandwidth. Sun et al. (2011) proposed a modified quantum-behaved particle swarm optimization method for QoS multicast routing in MANETs. This method, along with PSO and GA, is tested on randomly generated network topologies and demonstrated its superiority. However, the provided results are based on non strict constraints. As the artificial neural network (ANN) is an important optimization technique, it has been investigated in Kumar and Venkataram (2003) to deal with the constrained multicast routing optimization problem in a mobile network. This approach computes a reliable multicast route (tree), and selects a reliable route whenever there is a change in location of group members due to mobility. Simulation results demonstrated the computational time performance of this method especially in the node mobility case. The authors can also cited (Forsati et al., 2008) as QoS based multicast routing problem resolution founded on Tabu search algorithm. It considered two important QoS constraints: the bandwidth and the end-to-end delay in addition to the minimum cost of the multicast tree which determine the evaluation function. Here, the authors had modified the Prüfer numbers to propose a new solution representation appropriated for multicast trees and then described harmony operator’s accord to this representation that offer strong locality and heritability. Simulation results on randomly generated networks and real topologies indicated the proposal performance.

In order to evaluate our proposal, a series of experimental tests are carried out and compared with genetic algorithm (GA), bees algorithm (BA) and marriage in honey bees optimization (MBO) algorithm due to their efficiency and effectiveness in the context. GA is considered as population-based metaheuristic, based on the biological genetic concepts of chromosomes and genes to represent solutions in search space. It starts with a random population of chromosomes which are seen as solutions. After that, peers of parents are selected to product descendants by the application of two genetic operators which are crossover and mutation. These operators are submitted to crossover and mutation probability values, respectively. Based on the fitness function, the old and the new generations are compared then; the best ones are selected to form the next generation. This iteration is executed until the satisfaction of stopping criterion (Liu and Wu, 2003).

Another population-based metaheuristic inspired by the natural foraging behavior of honey bees called Bees Algorithm. It starts with a number of scout bees being placed randomly in the search space. The best sites visited in point of view fitness are chosen as selected bees which will be foraged their close sites to carry out a neighborhood search. BA assigns more bees to search near to the best sites which can contain more promising. Thus, only the bee with the highest fitness will be selected to form the next bee population. The remaining bees in the population are assigned randomly around the search space scouting for new potential solutions (Pham et al., 2006).

Also, the reproduction behavior principle in the bee colony has been used as an inspiration source to propose marriage in honey bees optimization algorithm. It starts with initializing the queen’s genotype at random and then a heuristic is applied to improve the queen’s genotype, therefore preserving the assumption that a queen is usually a good bee. Next, a set of mating-flights is undertaken relatively to the queen’s energy and speed. The queen then moves between different states (solutions) in the space and mates with the encountered drones according to probability criterion. Afterwards, the drone sperm is added to the queen’s spermatheca as a list of partial solutions. At the end of the mating-flight, the queen returns to the nest and starts breeding by selecting a sperm from her spermatheca at random followed by crossover and mutation operations. Finally, the queen is replaced with the fittest brood and so on (Abbass, 2001).

The rest of the paper is organized as follows. In Section 2, the vehicular ad hoc network representation is outlined as well as the (QoS-MRP) problem statement and formulation as multi-objective optimization problem with constraints. Section 3 presents the bees life algorithm after reviewing the bees in nature as inspiration source. In Section 4, the BLA applied to the QoS-MRP is discussed with its different steps: representation, fitness function, operators, stopping criterion and BLA complexity analysis. Therefore, the experimental study is devoted in Section 5 which contains the simulation scenario, results, comparisons and discussion. Finally, Section 6 concludes the paper and accentuates some perspectives for future work.

Section snippets

Vehicular ad hoc network representation

VANET is represented by a weighted graph G=(V, E) where V denotes the set of nodes and E denotes the set of links connecting these nodes. Each link can be measured by four QoS items: cost, delay, jitter and bandwidth. They represent the link transmission cost, the real delay during the link transmission, the real link transmission delay variation (jitter) and the estimated link bandwidth, respectively.

QoS-MRP formulation

We denote by s (sV) the source node of the multicast tree, and M⊆{V–{s}} is the set of

Bees life algorithm

In this section, our proposal is presented. First, the life of bees in nature is overviewed as an inspiration source of this algorithm. It will be followed by the detailed description of the BLA, its pseudo code and flowchart.

BLA for QoS-MRP

In this section, the application of BLA to the QoS-MRP is presented. First, the individual and population representations are introduced. Second, BLA initialization and fitness function are initiated and explained. It is used to evalute the individual and/or the population. Moreover, the various operators used in BLA are explained too. There are the crossover, the mutation and the neighborhood searching. Next, we present the iterations stopping criterion and finally a complexity analysis of BLA

Experimental study

We remind that the BLA goal is to find multicast tree of paths from source to destinations. This tree should offer minimization value of the aggregation between the optimization metrics which are cost, delay, jitter and bandwidth calculated by the formula 5. In addition, the requested tree should respect delay, jitter and bandwidth constraints aforementioned in formulas 7, 8 and 9, respectively.

To evaluate the performance and the effectiveness of BLA, a series of tests based on VANET simulation

Conclusion

In this paper the quality of service multicast routing problem for vehicular ad hoc networks has been studied as multi-objective optimization problem with constraints. The objectives are: transmission cost, delay, jitter and bandwidth. To solve this problem, a novel algorithm inspired by the bee life is proposed. It is called Bees Life Algorithm. In order to prove the reliability and the efficiency of this proposal, a VANET simulation has been carried out which is based on the routing protocol

References (23)

Cited by (60)

  • Swarm intelligence inspired meta-heuristics for solving multi-constraint QoS path problem in vehicular ad hoc networks

    2021, Ad Hoc Networks
    Citation Excerpt :

    Vehicles, on the basis of designation and adopted strategy try to find a route that satisfies QoS constraints. A multi-objective routing algorithm entitle Bee Life Algorithm (BLA) [24] was proposed to find paths for multicasting in VANETs. The main aim is to construct optimal tree from the source to multiple destinations considering parameters, like jitters and bandwidth.

  • GeoUAVs: A new geocast routing protocol for fleet of UAVs

    2020, Computer Communications
    Citation Excerpt :

    The process of BCO is listed as follows [27,52]: In the research literature, many strategies of BCO are presented in MANET and VANET [69–74]. However, the analysis of routing protocols of FANET based on BCO is done by the following works [25–27].

  • Quality of service aware multicasting in heterogeneous vehicular networks

    2018, Vehicular Communications
    Citation Excerpt :

    The constructed multicast tree may involve excessive number of street segments compared to the optimum multicast tree; thus, it may cause excessive congestion in VANET (see Section 3.2). Bitam et al. [41] proposed Bee Life Algorithm (BLA) to solve the Quality of Service Multicast Routing Problem (QoS-MRP) for VANETs. BLA imitates the life of bee colony to build a multicast tree between a source and a set of destination nodes.

  • Lagrangian relaxation for maximum service in multicast routing with QoS constraints

    2024, International Transactions in Operational Research
View all citing articles on Scopus
View full text