Improved Multi Constraints and Multicast Routing Optimization for VANETs Based Bee Life Algorithm

Improved Multi Constraints and Multicast Routing Optimization for VANETs Based Bee Life Algorithm

Kalaivanan. S

Assistant Professor, Information technology, Kongunadu College of Engineering and Technology, Trichy,

Thottiam, Tamilnadu, India.

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 road side base stations as fixed infrastructures. The applications of this sensitive field, it is very essential to transmit correct data any where and at anytime Consequently, the VANET routing protocols should be adapted appropriely and meet effectively the quality of service (QoS) requirements in an optimized multicast routing. To propose a novel bee colony optimization algorithm called bees life algorithm (BLA) applied to solve the quality of service multi cast 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 colony. It follows the two important behaviors in the nature of bees which are the reproduction and 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. the Comparisons of the experimental results show that the proposed algorithm outperformed in a efficient way genetic algorithm (GA),bees algorithm(BA) and marriage in honey bees optimization(MBO) algorithm.

Index Terms Vehicular ad hoc networks, Bees life algorithm, multicast routing problem, Quality of service, Multi- objective, Swarm bee optimization

I.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 [13]. 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 [1] and will be deployed at critical locations like slip roads, service stations, dangerous intersections or places well- known for hazardous weather conditions [15]. 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 [9]. The principle VANETs 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. 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 con- currently [5]. 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.

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.

1. SYSTEM DESIGN

   Bees life algorithm presented in Fig.2.1, starts with bee population initialization step which contains N bees (individuals) chosen at a random in the search space. The population fitness is evaluated in the second Step. A bee population contains 1queen, D drones and W workers in which the fittest bee represents the queen, the D fittest following bees represent the drones and the remaining bees are the workers. Consequently, the sum of the different bee individuals(1, D and W) equal to the population size

   (N). D and W are considered as a two user-defined parameters. Each cycle of a bee population life consists of two bee behaviors: reproduction and food foraging, respectively.

   The reproduction behaviors is started in the space by mating-fight between the queen and the drones using crossover and mutation operators. Next, queen starts breeding N broods in step 4.then the evaluation of the brood fitness is performed step 5.if the fittest brood is fitter than the queen,it will be considered as the new queen for the next population.Moreever, D fittest following broods and the current population to form the drones of the next population.

   After that,W best bee individual search among the W fittest remaining broods and the workers of the current population to ensure the food forging. In step 9,the W workers search food source in W regions of flowers. to consider that each worker represents one region and there are other bees for each region. They are

   recruited and employed to search the best food source among the

   population.

   Figure 2.1 Flow chart for the BLA.

   The evaluation of the new population fitness is executed in step12.If the stopping criterion is not satisfied, a new bee life cycle is performed then, we rerun the third step and so on. Figure 2.1 shows the flowchart for the BLA.

2. SYSTEM DEVELOPMENT

   1. Individual And Population Representation

      This phase represents the first step in the algorithm. Starting with the studied network, the individual is represented as single solution which is multicast tree contains the different paths from source node to each multicast group members (destinations)via set of intermediate nodes. Path is encoded using string expressed by order on node path numbers [3]. An individual is represented by tree structure contains its different paths. In Fig. 3.1 as example, the rear twenty (20)vehicles(nodes)in the VANET. The nodes are represented by circles and their links ae shown using a line between two nodes. For example, there is link between node 0 and node1 with link cost=220, delay=124 ms, jitter=1.8 ms and bandwidth=797.54kbit/s.Note that cost is functions of the link distance measured in meter which a reconsidered equal in the experimentation.

      Figure 3.1 Explanatory and theoretical VANET.

      If we consider the source node s is node0,and the multicast group members(destination nodes)are nodes¼{4,9,14,19}then, the individual can be chosen as the tree shown in Fig. 4.1 This tree contains four paths each one is string of nodes, from the source s (node:0)to one of each destination (nodes:4,9,14,19).The four paths are: (0-1-2-4), (0-

      1-2-4-5-7-8-9), (01-2-4-5-7-8-10-11-14), (0-1- 2-4-5-6-18-

      19). Note that the population collect a set of individuals where their number is a user parameter.

   2. Initialization And Reproduction

      Vehicular ad hoc network could be represented by its different topology data such as nodes number

      ,their locations and their locations and their different links. Besides, cost, delay, jitter and bandwidth between

      two adjacent nodes specify each link. They define the search space of the QoS MRP problem from which N individuals (solutions)are randomly generated to construct the initial population.

      Eachindividual is represented bytree which contains M paths from source node to M destinations. Note that M is the number of multicast group and the source node is the root of

      he tree representing the individual To evaluate the individual, the weighted aggregation(WA) method [11]is applied. It is an intuitive way for multi objective optimization carried out especially when only one solution should be obtained as the casein QoS MRP Problem. More adequate in this context than Pare to approach. In the WA approach, different objectives are weighted and summed up to a single objective which is the fitness function. The population fitness is the sum of the individuals fitness.

      1. Bee Life Algorithm

         1. Initialize population (N bees) at random

         2. Evaluate fitness of population (fittest bee is the queen, D fittest following bees are drones, W fittest remaining bees are workers)

         3. While stopping criteria are not satisfied (Forming new population)

            /*reproduction behavior*/

         4. Generate N broods by crossover and mutation

         5. Evaluate fitness of broods

         6. If the fittest brood is fitter than the queen then replace the queen for the next generation

         7. Choose D best bees among D fittest following broods and drones of current population (Forming next generation drones)

         8. Choose W best bees among W fittest remaining broods and workers of current population (to ensure food foraging)

            /*food foraging behavior*/

         9. Search of food source in W regions by W workers

         10. Recruit bees for each region for neighborhood search

             (more bees for the best B regions)

         11. Select the fittest bee from each region

         12. Evaluate fitness of population (fittest bee is the queen, D fittest following bees are drones, W fittest remaining bees are workers)

         13. End while

         In the reproduction part of the BLA, two major operators are applied: crossover and mutation. However, in the foraging part, neighborhood search approach is executed. In this subsection, we explain their application to generate new individuals.

         1. Crossover

            It is a binary operator in which the queen is selected and one drone is randomly chosen to generate two new individuals. This process is repeated until reaching N individuals with crossover probability of pc. We propose the following crossover operator for this tree representation as two-point crossover. For both parents, two paths for two destinations randomly chosen are selected (crossover2-points).They will be replaced by the towpaths towards the same destinations for the second parent and vice versa.

         2. Mutation

            It is a unitary operator in which the offspring has the chance to be mutated according to the mutation probability of pm. We propose the following mutation operator. To mutate an offspring, two paths towards two destinations randomly chosen are selected. For the former, we selected randomly an intermediate node and we search the same node in the Second path. If the same node is found in the second paths (mutation2- points),the second part of the second path is added to the first part of the first path and vice versa .If the chosen intermediate node is not found, this process is repeated until success.

         3. Neighborhood Search Approach

         Neighborhood search in the foraging part of BLA is used to reach neighbor individual from the original individual. We propose to use a greedy approach to generate neighbor individual. In this approach, one individual path is randomly selected and replaced by another path towards the same destination as the first one. It should contain at least one common intermediate node.

   3. Stopping Criterion

   To chose to apply a dynamic stopping criterion. The BLA iterations are carried out and stopped only when the population fitness does not change MinIT times; it is the stagnation state. We note that the iterations number is constrained by a maximum threshold MaxIT of iterations. The numbers MinIT and MaxIT are user parameters.

3. RESULTS AND DISCUSSION

   1. PERFORMANCE ANALYSIS

      To demonstrate the performance of BLA compared to the other algorithms (GA, BA and MBO),the average rounded values of ten (10) best fitness obtained in each test for different algorithms are calculated and listed in Table 3. From Table 4.1 and Fig. 9, were mark that the best fitness is the fitness obtained by BLA (18,825.9687). It is better than other.

      Table: 4.1

      To compare the complexity of BLA in contrast to other approaches (GA, BA and MBO), we summarize time computing in Fig. 11 and Table 4. This figure illustrates the stagnation of the best solution fitness for each population with time consumed by each algorithm. One can note that BLA algorithm reached the best fitness (18,825.96) in the earliest generation (13th generation). This proved its low time complexity compared to the others approaches. For example, MBO algorithm reached its stagnation state at the 16th generation. We note also that the stagnation generation of BA algorithm is obtained at the 7th generation but with bad value (20,186.64). In this case, BA dropped in a local optima value in an early time. Moreover, GA stagnated in the 16th generation. This practical analysis showed that BLA converge to the optimal solution better than GA, BA or MBO with the least generation times. They confirm the reliability and efficiency of BLA to solve the QoS-MRP with a minimum time compared to other approaches. In fact, performances of BLA are due to the generalization of the proposed algorithm in terms of the optimization principles. It collects the global search using the crossover operator which guarantees the diversity of the solution. Also, it ensures the local optima escape. Furthermore, BLA carries out a local search in the mutation operator and also in the neighbor- hood search approach.

      Table

      : 4.2

      Figure 4.1 Fitness of the best found solutions

      Figure 4.2 Best solutions in fitness iterations

4. CONCLUSION AND FUTURE WORK

To 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: trans- mission 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 that includes the implemented BLA. The simulation is realized accrding to mobility model of VANET which helps to obtain realistic metric values such as cost, delay, jitter and bandwidth. The obtained results of BLA compared to GA, BA and MBO as conventional algorithms prove the efficiency and the performance of the proposed algorithm in terms of the solution

quality and complexity for this problem. We conclude that

BLA outperformed GA, BA and MBO.

VANETs are fundamentally different to MANETs, such as the special mobility pattern and rapid changed topology. This paper proposes a solution for Multicast routing Protocols, where the future work can be extended to support geocast routing protocols also. Geocast routing is to deliver a geocast packet to a specific geographic region. Vehicles located in this specific geographic region should receive and forward the geocast packet; otherwise, the packet is dropped.

REFERENCES

1. Abbass, HA,A single queen single worker honey-bees approachto3- SAT,The Genetic and Evolutionary Computation Conference GECCO2001,San Francisco, USA, 2001.

2. Bitam,S, Mellouk,A, QoS swarm bee routing protocol lfor vehicular ad hoc networks,IEEE International Conference on Communications ICC2011, Kyoto, Japan, 2011.

3. Bitam, S,Batouche,M,Talbi,E

   G,Asurveyonbeecolonyalgorithms,24thIEEE International Parallel and Distributed Processing Symposium, NIDISC Work- shop, Atlanta,Georgia,USA,2010,pp.18.

4. Forsati R, HaghighatAT, MahdaviM .Harmony search based algorithms for bandwidth-delay-constrained least-cost. Computer Communications, Elsevier 2008;31:250519.

5. Huang J,LiuY,MOEAQA.QoS-aware multicast routing algorithm for MANET. Expert SystemswithApplications2010;37:13919.

6. Hag high at AT, FaezK, DehghanM, MowlaeiA, GhahremaniY. GA-based heuristic algorithms for QoS based multicast routing. Knowledge-Based System 2003;16:30512.

7. Huang C-J, Chuang Y-T, HuaK-W.Using particle swam optimization for QoS in ad hoc multicast.EngineeringApplicationsofArtificialIntelligence2009;22

   : 118893.

8. Kumar BPV, VenkataramP. Reliable multicast routing in mobile networks: a neural-network approach.CommunicationsIEEProceedings2003;150: 37784

9. Ledy,J,Boeglen,H,Hilt,B,Abouaissa,A,Vauzelle,R,Anenhanced AODV protocol for VANETs with realistic radio propagation model validation,9thInternational Conference on Intelligent Transport Telecommunications, Lille,France, 2009, pp.398402.

10. Liu Y, WuJ-P.A delay-constrained multi cast routing algorithm based on heuristic genetic algorithm.JournalofComputerResearchandDevelopment2003;40( 3): 3816.

11. Miettinen K.NonlinearMulti-objectiveOptimization.Kluwer;1999.

12. Nagib G,AliWG. Network routing protocol using genetic algorithms. International Journal of Electrical and Computer Sciences 2010;10(2):404.

13. K, Federrath H. A privacy aware and efficient security infrastructure for vehicular ad hoc networks. Computer Standard sand Interfaces2008;30 (6):

    3907.

14. Pham, DT,Kog, E,Ghanbarzadeh, A,Otri, S,Rahim,S, and Zaidi, M, The bees algorithm Anoveltoolforcomplexoptimisationproblems,2ndInternation al Virtual Conference on Intelligent PROduction Machines and Systems IPROMS 2006, Oxford,Elsevier,2006.

15. K, Federrath, H, Preventing profile generation in vehicular networks, IEEE International Conference on Wireless and Mobile Computing, Networking andCommunication,2008,pp.520525.

16. Bitam S, Mellouk A. Bee life-based multi constraints multicast routing optimization for vehicular ad hoc networks. Journal of Network and Computer Applications (2012).