Favorable Trail Detection using ACO-Bellman Algorithm in VANETs

Published Online January 2016 in MECS DOI: 10.5815/ijmecs.2016.01.05

Vehicular Ad-hoc Networks (VANET) is special type of Mobile Ad-hoc Networks (MANET). In MANETs, nodes are not fixed and data/information is transferred directly to base station, due to which traffic overhead increases. MANETs have limited energy and limited bandwidth [1]. Vehicular Ad-hoc Networks uses nodes as vehicles. VANETs configure and organize networks itself for communication by using moving vehicles. To create highly mobile networks vehicles provide a vigorous infrastructure [2]. The purpose of VANETs is to make communication networks for transfer data cost efficiently and fast for assists of passenger’s safety [3]. In VANET vehicles can communicates with each other (V2V) and also to infrastructure (V2I) [4]. VANETs have boundless power supply due to recharging of batteries and highspeed movement of vehicles makes network dynamic [5].

The WAVE Standardization process of IEEE 802.11p has emerged from the dedicated Short Range Communications (DSRC) spectrum band in the United States. Vehicle-to-vehicle and infrastructure-to-vehicle communication had been specified 75MHz of DSRC spectrum at 5.9 GHz solely. The main goal of this is to ensure safety application that helps to save the lives of people and improvement of traffic flow [6]. Spectrum band is divided into seven 10 MHz channels. Channel 178 “control channel’ is for beacon messages, event driven emergency messages. Other six channels are service channels, which used for non-safety application [6].

Fig.1. VANET Architecture.

• A. Routing Protocols

Routing is communication between one end to another end. Main goal of routing is to search out and preserve routes between two ends. Protocol is set of rule that allow end points to communicate each other and interchange data. Routing protocols are classified into two categories unicast routing protocols and multicast routing protocols [7].

Unicast routing protocols transfer data from one source to one destination. There are many unicast routing protocols, which, may be proactive routing protocols or reactive routing protocols.

Proactive routing protocols are those in which data packets are broadcasted among nodes whether the paths are used or not and every node have to preserve information about next neighborhood node that indicates the destination. Disadvantage of this protocol is, it provides low latency for real time application, and also leads to the maintenance of unused data paths, which causes the reduction in the available bandwidth [8].

Reactive routing protocols are those in which communication among nodes occur only when needed and only current route has been maintained, which reduces the overhead of the network. Various reactive routing protocols are Ad-hoc On Demand Distance Vector (AODV), Dynamic Source Routing (DSR) [7].

Multicast routing protocols transfer same data from one source to multiple destinations.

Table 1. Comparison between Reactive Routing Protocols

PARAMETERS	AODV	DSR
MOBILITY	High	Low
PACKET FLOW	Flooding	Route Discovery and Maintenance
NETWORK TYPE	Large Scale	Dense
BANDWIDTH	Low	High
ROUTING TABLE	Large Information	Only Needed
CACHE MAINTAINED	No	Yes

• II.    Literature Survey

In [6] author evaluated that group of new demands has been implemented in communication system by wireless access in vehicular environment. WAVE operating mode and WAVE BSS are introduced by these demands in IEEE 802.11p. The authors had analyzed that there was no need to join a BSS if stations operating WAVE mode. Stations could exchange data by utilizing the BSSID that was available at all time. The connection setup overhead and safety application have been reduced self-actingly for vehicles. In [8] researchers had performed a survey of routing protocols in vehicular/ ad hoc networks. The pros and cons of routing protocols had been discussed, propels behind their design were diagnosed of routing protocols. Routing protocols had been divided into 2 categories; Topology based routing protocols and geographic routing protocols. Comparison and characteristics of different protocols had been discussed. In [10] authors had introduced that Ant colony algorithms (ACO) are class of swarm intelligence. It had been concluded that ants had ability to solve the major problems and this routing protocol is adaptive, scalable, and efficient. The optimal path had been discovered by Ant colony algorithm with minimum overhead. Route maintenance had also done by ACO to hold back optimal path. In [11] authors had analyzed that rather than using the static algorithms for shortest path a bio inspired system Ant-based vehicle congestion avoidance system (AVCAS). To find out the least congested shortest path this system uses the average travel speed prediction. This also helps to reduce traffic congestion. Efficiency of AVCAS had been evaluated in terms of average travel speed; time which was better than compared to all other algorithms as dijkstra, HRS, PACO.AVCAS presented multi-objective ant based vehicle congestion avoidance by using real time traffic information. In [7] authors had analyzed the performance of unicast and multicast routing protocols had been examined in VANETs. The performance of had been diagnosed using multiple Qualities of services (QoS) metrics (packet delivery ratio, average delay, routing overhead). AODV and DSR protocol still could implement in VANET. Both AODV and DSR are reactive protocol. But acc. to the simulation result they had concluded that packet delivery ratio of DSR protocol is better than AODV, and average delay of DSR is less than the average delay of AODV. In [12] authors had presented a on demand routing protocol for MANETs, which is combination of Ad-hoc On Demand Distance Vector and Ant Colonization and find the multiple route among source to destination. The performance of AODV and purposed algorithm had been compared in terms of end to end delay, network load, number of dropped data packets, which analyzed that the performance of proposed algorithm was better than AODV. But as of reactive routing protocol AODV also create overhead which proceed to network congestion. In [13] researches had proposed a algorithm which aid to search out shortest path from food to source. DYMO had been purposed from conflate characteristics of Dynamic MANET on demand routing protocol and MANET routing protocol. Result of various parameter had been compared among both DYMO and ANT/DYMO and analyzed that ANT/DYMO performed more effective than DYMO, however ANT/DYMO performed well but end to end path reliability is not good due link breakage.

• III.    Problem Formulation

Owing to the dynamic behavior of the Vehicular Ad-hoc Networks (VANET), routing in VANETs becomes the disputing task. Routing is communication between one end to another end. It has been very tough to transmit data among moving vehicles especially when Quality of Services (QoS) requirements like maximum packet delivery, low end-to-end delay, low routing overhead are to be satisfied. Dramatically increased in population of vehicles leads to heavy traffic problem, which can be termed as congestion. Congestion creates difficulty for vehicle to find out the route and further leads to collisions. There should be a means to control congestion and avoid collisions in vehicular networks.

The best optimal route can be found using Swarm Intelligence algorithms and Bellman Ford algorithm. Swarm algorithms analyze the behavior of different animals like ant, bee, and fish to simulate and have ability to solve the complex problem by cooperation and Bellman Ford algorithm helps to find out the favorable path given by ACO.

• IV.    Proposed Solution

Vehicular ad-hoc networks are dynamic in nature. Vehicles move from one position to another position to achieve a desirable path. Various routing protocols and algorithms used to search a best route in terms of cost, bandwidth, and end-to-end delay. As VANETs are not steady in nature, link failure is major issue, so to find out a optimal route purposed solution is swarm intelligence based algorithm i.e. Ant colonization algorithm. Swarm intelligence provides a framework to designing an algorithm to solve a problem in simple manner [10]. These algorithms have been reported best algorithm to solve the congestion problem and traffic management [11].

• A.    Ant Colonization

Ant colonization is bio-inspired algorithm in which agents simulates the behavior of ants and solve the major problem with cooperation among themselves. Ant colonies have a high organization degree capable of selforganizing into groups and develop complex tasks [5]. Ant colonization determined ant’s behavior that ants able to search food from source end in minimum time and shortest path [21]. There are multiple paths from source to food, so initially ants do random walk. Ants have to follow a trail mark which is a chemical substance called pheromone that released by ants during their path finding [14]. Other ants follow the path having maximum value of pheromone [22]. If ants reach intersection of food then decide to take left or right. Some ants take right and other take left, and new pheromone evaporation trail is formed along the shorter path and value of pheromone is denser and evaporates when route is change [15]. Figures below have described the behavior of ants.

Fig.2. Ants follow pheromone trails form.

Fig.2.1. An obstacle on the trail source to destination

Fig.2.2. Ants gets two paths.

Fig.2.3. Ants follow the shortest path according to Pheromones value.

• B.    Proposed ACO-Bellman Algorithm

Steps for algorithm:

Step 1. Initialize data: data means nodes or vehicle. First have to initialize the vehicles and form that one becomes the source/ base station having all the information about source address, destination address, and hop count, distance.

Step 2. Read Instance: instance is vehicle, to check the proper position of vehicles that are speared initially. Check the X, Y positions of vehicles.

Step 3.  Initialize parameters: to find out the route various   parameter are necessary. Like pheromone, cost, distance between vehicles etc.

Step 4. Compute Distance: distance from source to destination measures by the value of pheromone that is hop count, communication, and steps covered by vehicles. Lesser the value of hop counts more the value of pheromones.

Step 5. Compute Nearest Neighbor List: ACO gives multiple paths according to the pheromones value, but have to select the optimal path.

Step 6. Compute Choice Information: optimal path selected from the multiple that compute from nearest neighbor list using bellman ford algorithm, which works on negative weight. In our purposed work negative weight is cost. By computing the cost, route having minimum cost is optimal path.

Proposed ACO-Bellman Algorithm for k = 1 to m do          //k initialize as vehicles fori = 1 to n do            // I initialize as roads ant[k].visited[i] ← false end-for end-for step ← 1

for k = 1 to m do r ← random{1, . . . , n} // random is any variable which measure the pheromone value ant[k].tour [step] ← r ant[k].visited[r ] ← true // update pheromone value end-for while (step < n) do step ← step + 1

for k = 1 to m do

Neighbor List As Decision Rule (k, step) end-for end-while for k = 1 to m do ant[k].tour [n + 1 ] ← ant[k].tour [1 ]

ant[k].tour length ← Compute Tour Length(k) //tour length computed by Bellman algorithm end-for end-procedure

Fig.3. Proposed ACO-Bellman Algorithm

This proposed algorithm is to finding the optimal path. Route discovery is to search out the path using various parameters to send the information to neighbor nodes or destination end, when the destination end finds information pass to destination end.

• C.    Dynamic Source Routing

Dynamic Source Routing (DSR) is On Demand Routing protocol in which Information is interchanged only when necessary. DSR preserves cache of route information, and cache updated when a new route is found to source. Source node can find out any destination, which is permitted by DSR. Nodes pass the route information to another by updating the routing table.

There are two phase of DSR are Route Discovery and Route maintenance [8].

Route discovery

Route discovery is done to search out the route from particular one end to another end. Before sending the Route Request (RREQ) packet to another nodes cache has been checked for existing node. If it doesn’t exist in the cache, then Route Request (RREQ) packet is broadcasted to all the nodes [17] as shown in fig 4.2. Packet contains unique ID, destination node, source node [16]. Node checks the packet information. If node finds itself to destination then Route Reply packet (RREP) send back to route, if not, then packet is forwarded to another node by updating route table and this phenomenal repeats till destination node not receives a RREQ. When RREQ packet has been received by destination then RREP packet has been send back to source as shown in Fig 4.3. Source stores the route into cache and for data delivery a shortest path has been chosen [16].

Fig.4.2. Node B, C, D, E, F, G and H are Forwarding RREQ Packet in Same Manner as Source Forward

Fig.4.3. Destination Nodes Sending RREP Packet to the Source Node with Discoverable Path

Fig.4. Ad-hoc Network Node a Is Source an Node I is Destination

Fig.4.1. Source Sending RREQ Packets to Nodes

Route Maintenance

If a node becomes flunk to communicate, then discovery of new route is must. A RERR packet is sent to source from nearest node to source, which acknowledges the link failure. Source resends RERR packet with RREQ packet to all the nodes to acknowledge about link failure. In DSR, the source preserves numerous routes information from source to destination, which may be used at the time of link breakage [18].

• D.    Bellman Ford Algorithm

Bellman ford algorithm is known as single source shortest path algorithm. This algorithm calculates the possible shortest path from a single source to all other nodes in network. This algorithm is versatile, because algorithm is efficient to managing the negative weight in the network. This algorithm is simpler than dijkstra and compatible to distributed systems [19]. It calculates the shortest path by calculating the distance between each node to source. If there is any negative weight in network then only negative weights is reported to find out shortest path. If negative path is found in network then instead of paying extra cost, negative path may provide advantage [20].

• V.    Results and Discussion

Vehicular Ad-hoc Networks are specially worked using IEEE 802.11p standard. The simulation for proposed work has been performed using NS-2.35 simulator. A grid structure scenario with 26 nodes, 15 traffic lights and one base station have been deployed in 1200*1200 m2 area as shown in fig 5 below. Vehicles are represented in green color, traffic lights in red color initially and base station in blue color. Traffic lights in the simulation work as real traffic lights system. Simulation is run for 40 sec with mobile vehicles having different velocities and densities.

Fig.5. Scenario Presentation

Speed of vehicles change according to the congestion and traffic lights. Vehicular traffic flows in both the directions. Vehicles communicate with each other and also with base station to deliver the information to other vehicles and to destination end. The nodes travel from source to destination on the favorable Trail detected by the ACO-Bellman algorithm.

Important parameters that are configured in simulation are described in table 2.

Table 2. Configuration of Parameters.

PARAMETERS	VALUES
Simulation Area Simulation Time Vehicles speed Transmission Range Distance between Nodes MAC/PHY Size of Packets	1200*1200m2 40 Sec 0-100 m/s 250 m 50-250 m IEEE 802.11p 512 bytes

To analyze the effectiveness and efficiency of routing algorithm we use different parameter:

Throughput

Throughput is amount of data transferred from one place to another or processed in a specified amount of time. According to proposed work throughput is number of packets deliver or receive from source to destination end per second. Throughput is measured in terms of bits/sec or bytes/sec. Better result of throughput means better performance of network. Throughput of proposed ACO-Bellman algorithm and Simple DSR routing algorithm has been compared in fig 6 below. It’s clearly shows 66bits/sec throughput in case of simple DSR routing algorithm and 96bits/sec in proposed work. Because proposed ACO-Bellman algorithm use the ACO algorithm with DSR routing protocol, which decrease the time delay to sending or receiving packets/information to other end because of its bio-inspired nature. Secondly Bellman ford algorithm, which helps to find out shortest and favorable path given by ACO.

Packet Delivery Ratio

Packet Delivery Ratio is ratio of number of successfully received data packet by the destination as compared to the number of data packets sent by the sender. As the value of packet delivery ratio increases it refer better performance of protocol. In VANETs Packet delivery ratio is measured in terms of total packets send over the total packets received per second. Packet Delivery ratio of both proposed ACO-Bellman algorithm and simple DSR routing algorithm have been represented in Fig 7. The ratio of proposed ACO-Bellman algorithm shows higher packet delivery value 178 packets as compared to simple DSR routing algorithm 88 packets because packet/information transferred in the proposed ACO-Bellman is based on the pheromone value that is used by the vehicles. ACO algorithms provide the more connectivity among the nodes due the pheromone values, which connect the nodes and give greater packet delivery ratio.

Fig.6. Throughput Comparison

Fig.7. Packet Delivery Ratio Comparison

• VI.    Conclusion

The purpose of VANETs is to provide communication networks to transfer information regarding traffic, roads side units, and other vehicles cost efficiently and fast. These networks act as traffic and route guide to assist passengers. These networks have been practically realized in many countries like JAPAN, owing to these features. Efficient and scalable information transfer to V2V and V2I is challenging due to dynamic behavior of VANETs, which leads to congestion. In this paper a swarm based routing algorithm has been proposed in which agents calculate the optimal path by simulating the behavior of bio inspired animals like ant, bee and fish etc. for their food search. Bellman Ford algorithm has been used to find out the shortest path from the path given by ant colonization. This proposed solution has helped in traffic control and congestion control. Testing based result have been compared the throughput and energy consumption parameters between the simple DSR algorithm to proposed ACO algorithm. The simulation result of proposed algorithm yielded the better performance than simple DSR algorithm.

Acknowledgment

I would like to pay special thanks, warmth and appreciation to my guide Dr. Parminder Singh, who made my research successful and assisted me at every point to appreciate my goal.