Shortest Path using Ant Colony Optimization in VANET

Shortest Path using Ant Colony Optimization in VANET

N. Jayachithra

Research Scholar Dept. of Computer Science Periyar University, Salem

1. Sivakumar

   Research Scholar Dept. of Computer Science Periyar University, Salem

   Dr. C. Chandrasekar

   Professor

   Dept. of Computer Science Periyar University, Salem

   Abstract:- VANET is a form of mobile ad-hoc networks (MANET) to provide connections between near vehicles and near fixed equipment. Today VANET used largely function for the public safety, the calm, Travelers Information, Traffic Management, Traffic co-ordination and Assistance, etc. The traffic congestion can happen anytime, anywhere in the traffic. Its condition where the traffic controls fail and may occur accidents, road maintenance, and rule breaking, etc. therefore, to avoid the traffic congestion. Vehicle traffic congestion leads to air pollution, driver irritation, and costs billions of dollars annually in fuel consumption. Finding a proper solution to vehicle congestion is a great challenge due to the dynamic and unpredictable nature of the network topology of vehicular environments, especially in urban areas. Ant algorithms simulate the cooperative behavior of real ants one of the good ways of traffic congestion. It combines the average travel speed predictor of traffic on roads with map segmentation to reduce congestion as much as possible by finding the least congested shortest paths in order on the road to avoid congestion instead of recovering from it. ACO collects real-time traffic data from vehicles and roadside units to predict the average travel speed of road traffic. It utilizes this information to execute an ant-based algorithm on a segmented map resulting in avoidance of congestion. The outcome shows that when the road is congested, path algorithm for active traffic network can be more appropriate for travelers to find the path. The simulation result analysis is NS2 and this analysis is provided in terms of performance metrics, such as a packet delivery ratio, the average end-to-end delay, and throughput. Simulation result shows that the ant colony optimization finding the best path to a nest into food in the model area.

   Keywords:- VANET, ACO, NS2, vehicle traffic congestion, SUMO.

   1. INTRODUCTION

      For the past 10 years, numbers of Vehicular is increase day by day all over the world, which also increasing more traffics. This large number of vehicles leads to heavy traffic congestion, air pollution, high fuel consumption and following economic issues (Narzt et al. (2010)). New building, high- capacity streets and highways can ease some of the aforementioned problems. However, this solution is very costly, time consuming and in most cases, impossible because of space limitations. On the other hand, optimal usage of the existing roads and streets capacity can lessen the congestion problem in large cities at a lower cost [1].

      Intelligent Transportation System (ITS) is a newly emerged system which collects real-time data for congestion monitoring using road side units (e.g. video cameras, radio-

      frequency identification (RFID) readers and induction loops) and vehicles as mobile sensors (i.e. in-vehicle technologies or smart phones). These data are used by car navigation systems (CNS) to find the shortest path or optimal path from a source to a destination. Other key factors include congestion, number of traffic lights, number of route lines, accident risk and travel time [1].

      This traffic information was provided by existing infrastructures (e.g. Road Side Units) in order to propose a traffic-aware shortest path for users and drivers. Therefore, this information is not only based on the current traffic information but is also based on other metrics such as weather and historical traffic information. It is value noting that their system is reactive and avoids vehicle congestion implicitly, which is still not enough, due to non-recurring congestion. These types of congestion include more than 50% of all vehicle congestion (Coifman mallika (2007)). Moreover, the same path is suggested to users by this system and similar to static algorithms, congestion will be switched from one route to another if a significant number of drivers utilize this system [1].

      Swarm intelligence algorithms are newly emerged algorithms which simulate the behavior of different animals in nature such as ants, bees, fish and birds, (Merkle and Blum (2008); Ahmed and Glasgow (2012); Yang et al (2013)). These algorithms are able to produce fast, multi-criteria, low cost and robust solutions for various problems such as routing, scheduling and assignment (Merkle and Blum (2008); Panigrahi et al (2011)). Among these heuristic algorithms, the use of ant colony optimization algorithms has been reported as promising and is one of the best approaches for congestion control and traffic management. Their behavior for survival is the best way of finding shortest path. The goal of Ant Traffic Control System algorithm is to dynamically control the traffic network balance such that traffic flow in the network is optimized. In case one route is blocked or delayed, car drivers should be informed about alternative routes. This paper has proposed the algorithm for the shortest path selecting in dynamic traffic network, based ant algorithm. This measure can help travelers find the route and save time in the countryside of congestion [1].

   2. VEHICLE AD-HOC NETWORK

      VANET (Vehicular Ad Hoc Network) is a subgroup of MANET (Mobile Ad Hoc Network) in this type of

      communication networks each vehicle represents a node of the network and the communication can occur in two ways [9]:

      1. V2V (vehicle-to-vehicle), when the communication is between two or more vehicles,

      2. V2I (vehicle-to-infrastructure) when the communication is between a vehicle and a device in the highway.

         In this type of network, vehicles may be a router or a simple node. Figure 1 shows a diagram with the main VANET network elements, and the features of VANET networks are shown below [10]:

         • Dynamic topology: the nodes (vehicles) can reach high speeds, however, unlike MANET networks, these movements are accomplished towards well- defined directions, following paths limited by streets and highways;

         • Network without infrastructure: vehicular communication is based on Ad Hoc architecture, that is, without a main access point;

         • Discontinuous network: as a consequence of the dynamic topology of the network, a node can easily disconnect from the network;

         • Unlimited battery: knowing that the vehicle battery is recharged when it is running, the energy of a node can be considered unlimited.

           This type of network enables the development of several applications. Vehicular communication is considered the key for increasing traffic safety and a booster in the development of the transportation sector. The VANETs networks applications can be divided into three main groups [9]:

         • Safety:

           The preventing collision and accident reporting.

         • Information:

           Notification of traffic congestion.

           Fig.1. Main VANET elements

         • Entertainment:

           Video streaming and internet access.

           In a real VANET network, it is possible to have obstacles between two or more vehicles. These obstacles fade the signal transmitted and delay the communication. Therefore, it is required to find alternative routes of communication for the

           vehicles in these conditions. This paper proposed Ant Colony Optimization (ACO), a nature-inspired algorithm with fast response time, low computational effort, and that is particularly useful for routing problems and find the good path [9].

           1. Characteristics of VANET

      VANET is an application of MANET but it has its own distinct characteristics which can be summarized as [11]:

      1. High Mobility:

         The nodes in VANETs usually are moving at high speed. This makes harder to predict a nodes position and making protection of node privacy [12].

      2. Network topology:

         Due to high node mobility and random speed of vehicles, the position of node changes frequently.

      3. Unbounded network size:

         VANET can be implemented for one city, several cities or for countries.

      4. Frequent exchange of information:

         The ad hoc nature of VANET motivates the nodes to gather information from the other vehicles and road side units.

      5. Wireless Communication:

         VANET is designed for the wireless environment. Nodes are connected and exchange their information via wireless.

      6. Sufficient Energy:

         The VANET nodes have no issue of energy and computation resources. This allows VANET usage of demanding techniques such as RSA, ECDSA implementation and also provides unlimited transmission power.

      7. Protection:

      The VANET nodes are physically better protected. Thus, VANET nodes are more difficult to compromise physically and reduce the effect of infrastructure attack.

   3. ANT COLONY OPTIMIZATION

      Ant Colony Optimization, it is a Swarm based optimization algorithm and was proposed by Marco Dorigo in 1992. It is basically dependent on how the ants search the food source even though they are blind and carry the food to their nest. The deposition of the chemical substance called as pheromone by the ants on the path they travel and the evaporation of this pheromone over certain duration of time, these are the two most essential terms in Ant colony optimization. With the help of pheromone, ants decide which path to follow; this process is the stigmergic communication [14]. As shown in figure 2, initially all ants move in an unplanned manner to discover the food. When they find food, they carry the food and come to the colony in reverse path by depositing the pheromone along the traveled path [13].

      Fig.2. Ants deposition of pheromone from the food source to the nest

      Now the nest ants which are coming out from the nest will first check for the amount of pheromone on all the available paths and it will choose the path on which the pheromone concentration is highest. As the time passes more ants will travel on the particular path, which is the shortest path having highest amount of pheromone deposited [13].

      1. ACO in Traffic Application

         Due to its widespread occurrence, traffic congestion is a popular topic of study for the application of Artificial Intelligence. Some of the methods proposed to address the dynamic behavior of traffic congestion using the ACO algorithm. ACO application in traffic network replaces the pheromone with the congestion factor to determine the optimum path. Its application in traffic management involves the determination of the optimum path for a driver to get from one location to another [15].

         The advantage of using ACO algorithm in determining the path is that it gives the agents the ability to predict and avoid traffic congestion. After, traffic congestion will be reduced once new traffic entering the network is discouraged from entering a congested route [16]. Each driver, equipped with a device that is connected to the Global Positioning System (GPS) network, will update their locations consistently to the database where the congestion factor of the road will be calculated based on the number of cars occupying the road and the road capacity.

         Fig. 3 shows the current traffic system which transmits traffic information through television or radio which is usually not available in real time to the drivers on the road. The same figure suggests the usage of cell phones built in with GPS to create another layer of connection between traffic system updates and the current, ongoing traffic. The database will store all the values of the roads congestion factors, the current location and destination of each agent, and ultimately ad hoc situations such as road closures, accidents, and vehicle breakdowns that can cause unusual traffic interference [15].

         Fig.3. Different layers of communication within a traffic system

      2. Algorithm

      An algorithm based on the ACO has been designed and modeled in the network simulator. A virtual traffic network has been created and modeled which runs in real time for visual observation. The method used in determining the optimum path is shown in Fig. 4. Important factors such as agents total travelling time, agents speed, and congestion factor of each road have to be considered in designing the algorithm. The algorithm chooses the two best paths in terms of total distance before determining the optimum path by calculating total travelling time [15].

      Fig.4. Flowchart for determining the optimum path using the ACO algorithm

   4. SIMULATION RESULT AND WORK

      We have used Network simulator 2, having version NS-2.35 to evaluate the different data forwarding protocols. In 1995 network simulator in its Version 1 and in 1996 version 2 network simulators was introduced. To run the simulation in NS-2, Tcl script is required to feed. During the simulation, all the information related to the data packets is stored in the trace files. After the completion of the simulation, the AWK program is used in order analysis the text based trace file and

      NAM program is to use to analysis the information in terms of animation [13].

      A. SIMULATION WORK:

      Road Capacity=Road Length – No of Vehicles Length + Distance between Vehicles

      In this paper calculate the traffic using No. of vehicle near in the coverage area. More than vehicle present in road capacity, and then assume the place will be traffic accord. Then we will choose an alternate path to the destination using ACO method. The ACO method has helped to identify the alternate path to quickly reach the destination. Then road capacity calculates the following formula:

      Parameter Type	Value
      Network Simulator	NS-2.35
      Routing Protocol	AODV,DSDV,DSR
      Simulation Time	499.00
      Simulation Area	1000*1000m
      Number of Nodes	100
      DATA TYPE	FTP
      Packets Generation Rate	80 kb
      Packet Size	160 bytes
      MAC Protocol	IEEE 802.11
      Channel Type	Wireless Channel
      Antenna Type	Omni Antenna

      TABLE I. SIMULATION PARAMETERS

      Fig.5. SUMO tool graphical view for road-side 1

      Fig.6. SUMO tool graphical view for road-side-2

      c

      Fig.8. SUMO Zoom view for traffic signal using sumo tool-2

      Fig.9. Finding alternative path using ACO

   5. PERFORMANCE EVALUATION

      The performances parameters that can be obtained through the NS2 Trace Analyzer are as follows, which are the main parameters are:

      • Throughput

      • Packet Delivery Ratio

      • End to End Delay

      1. Throughput:

         Throughput is the rate at which a network sends receives data. It is a good channel capacity of net connections and rated in terms bits per second (bit/s).

         Throughput = Received data * 8 / Data Transmission Period (bps)

      2. Packet Delivery Ratio (PDR):

         It is a proportion of packets received to packets sent during certain simulation period, it is given by

         PDR Number of packet receive / Number of packet send * 100

      3. End-to-End Delay:

      End-to-end delay refers to the time taken for a packet to be transmitted across a network from source to destination.

      Dend-end=N [dtrans+dprop+dproc]

      Where

      Fig.7. SUMO Zoom view for traffic signal using sumo tool-1

      Dend-end=end-to-end delay, Dproc=procedure delay Dtrans=transmission delay, Dprop=propagation delay Dqueue=queue delay

      N= number of links (Number of routers + 1)

      Note: we have neglected queuing delays.

      Each router will have its own dtrans, dprop, dproc hence this formula gives a rough estimate.

      TABLE II. THROUGHPUT FOR SIMULATION WORK

      Parameter	Aodv	Dsdv	Dsr
      Throughput	249.96	201.92	664.29

      Throughput

      700

      600

      500

      400

      300

      200

      100

      0

      Throughput

      Fig.10. Performance Analysis of Throughput

      TABLE III. PACKET DELIVERY RATIO FOR SIMULATION WORK

      Parameter	Aodv	Dsdv	Dsr
      Pdr	99.33	99.32	99.38

      PDR

      99.38

      99.36

      99.34

      99.32

      99.3

      99.28

      PDR

      Fig.11. Performance Analysis of PDR TABLE IV. DELAY FOR SIMULATION WORK

      Parameter	Aodv	Dsdv	Dsr
      Delay	264.45	243.28	132.31

      Delay

      300

      200

      100

      0

      Delay

      Fig.12. Performance Analysis of Delay

      TABLE V. PERFORMANCE VALUE OF AODV, DSDV AND DSR

      Protocols	Aodv	Dsdv	Dsr
      Throughput	249.96	201.92	664.29
      Pdr	99.33	99.32	99.38
      Delay	264.45	243.28	132.31

      700

      600

      500

      400

      300

      200

      100

      0

      Throughput

      Pdr Delay

      Fig.13. Performance Analysis of AODV, DSDV, DSR protocols

   6. CONCLUSION

The beginning simulation result shows that the ACO algorithm is capable of providing the shortest travelling time for an agent moving in a simulated traffic network. After, the algorithm has established to have the ability to create an optimal traffic distribution in a congested traffic network by suggesting the path which is less congested. The results also show that the algorithm performs better in a highly congested traffic situation system.

The results are achieved by analyzing the ability of the algorithm to avoid congested paths and at the same time reducing their total travelling time in the network. The final results show that the ACO algorithm is capable of reducing the travelling time between 21.13% and 38.99%. As a conclusion, the simulation model of the traffic network is optimized by the implementation of the ACO algorithm for path finding, and is best utilized in a highly congested traffic network.

In this paper, we have proposed, two ACO based routing protocols AODV, DSDV and DSR. The result of the Ant colony optimizes process shows that AODV, DSDV and DSR performs well for Vehicular Ad hoc Networks. This protocol shows good results of parameters such as Throughput, Packet Delivery Ratio, and End-to-End Delay.

REFERENCES

1. Mohammad Reza Jabbarpoura, Ali Jalooli et al Ant-based Vehicle Congestion Avoidance System using Vehicular Networks July 2014.

2. Narzt, W., Wilingseder, U., Pomberger, G., Kolb, D., Hortner, H., 2010. Selforganising congestion evasion strategies using ant-based pheromones. Intelligent Transport Systems, IET 4, 93-102.

3. Pan, J., Khan, M.A., Sandu Popa, I., Zeitouni, K., Borcea, C., 2012. Proactive vehicle re-routing strategies for congestion avoidance, in:

   Distributed Computing in Sensor Systems (DCOSS), 2012 IEEE 8th International Conference on, IEEE. pp. 265-272.

4. Coifman, B.A., Mallika, R., 2007. Distributed surveillance on freeways emphasizing incident detection and veri_cation. Transportation research part A:policy and practice 41, 750-767.

5. Merkle, D., Blum, C., 2008. Swarm intelligence: Introduction and applications.

6. Blum, C., 2005. Ant colony optimization: Introduction and recent trends. Physics of Life reviews 2, 353-373.

7. Yang, X.S., Cui, Z., Xiao, R., Gandomi, A.H., Karamanoglu, M., 2013. Swarm intelligence and bio-inspired computation: Theory and applications. Newnes.

8. Panigrahi, B.K., Shi, Y., Lim, M.H., 2011. Handbook of Swarm Intelligence.Springer.

9. Rodrigo Silva et al A Heuristic Algorithm Based on Ant Colony Optimization for Multi-objective Routing in Vehicle Ad Hoc Networks sept 2013.

10. R. Michoud, A. M. Orozco, and G. Llano, Mobile ad-hoc routing protocols survey for the design of VANET applications, in IEEE Colombian Intelligent Transportation Systems Symposium, 2012, pp. 1- 6.

11. Jyoti Jain, Nidhi Chahal A REVIEW ON VANET, TYPES, CHARACTERISTICS AND VARIOUS APPROACHES sept 2016.

12. Kalkundri Ravi AODV Routing in VANET for Message Authentication Using ECDSA IEEE Conf. on Communications and Signal Processing (ICCSP), 2014, pp 1389 1393.

13. Snehal K. Gaikwad et al An Ant Colony Optimization based Routing Techniques for VANET April 2016.

14. V. A. Gajbhiye, R. W.Jasutkar,Biologically Inspired Routing Protocol for Vehicular Ad hoc Network 6 International Conference on Advanced Infocom Technology (ICAIT), 2013, IEEE Publications.

15. Shahrizul Anuar Abu Nahar and Fazida Hanim Hashim Modelling and Analysis of an Efficient Traffic Network Using Ant Colony Optimization Algorithm July 2011.

16. D. Alves, J. van Ast, Z. Cong, B. De Schutter, and R. Babuska, Ant Colony Optimization for Traffic Dispersion Routing Journal of Annual Conference on Intelligent Transportation Systems Madeira Island, Portugal, 2010.