An Ant Colony Algorithm Based Congestion Elusion Routing Strategy for Mobile Ad Hoc Networks

Dan-Yang Qin，Hong-Wei Li，Lin Ma，Hong-Bin Ma，Qun Ding

(1.Electronic Science and Technology Post-Doctoral Research Center，Heilongjiang University，Harbin 150001，China;2.Harbin Research Institute of Electrical Instruments，Harbin 150081，China;3.Communication Research Center，Harbin Institute of Technology，Harbin 150001，China)

1 Introduction

Mobile ad hoc networks consist of peer-to-peer wireless mobile nodes which are capable of communication with each other without any fixed infrastructures［1］.The intermediate nodes often change dynamically and arbitrarily.If a sender wants to communicate with another one which lies outside the radio communication covering range，it has to follow the routing protocol to discover an information pipeline path，so the intermediate nodes will act as routers forwarding data packets to the destination node.This kind of self-organizing form of the networks with multihop can sever the search and rescue，digital battle field，disaster area rebuilt，satellite，aircraft communications and so on［2－3］.

Edging toward the wide deployment，a critical challenge that mobile ad hoc networks have to face is the design and development of routing protocols which can simultaneously guarantee the high bandwidth utilization and fairness across multiple users［4］.The unique characteristics underlying such networks are essentially two-fold，which are the potentially high bandwidth and large number of data flows，and the time varying link capacities over the multi-hop environment.A critical challenge for mobile ad hoc networks is the design of efficient routing protocols which are able to provide high bandwidth utilization and desired fairness in wireless environment without any fixed communication establishments［5］.Extensive efforts have been devoted to providing optimization based，distributed congestion elusion strategies for not only efficient bandwidth utilization and fair allocation as well in both wired and wireless networks，a common assumption therein is the fixed link capacities，which will unfortunately limit the application scope badly in mobile ad hoc networks where the channels keep changing［6］.

The open shortest routing precedence is a prevalent protocol in networks.It adopts the optimal link state routing(OLSR)algorithm which only possesses the function of routing discovery without any congestion response mechanism［7］.When the congestion is to happen，or has already happened，the data packets will only be thrown away which will limit the networking resource being used adequately.In this paper，an effective congestion elusion strategy is presented explicitly based on the ant colony algorithm for mobile ad hoc networks，which will explore the optimal route between two nodes promptly;meanwhile forecast the congestion state of the link.Accordingly，a new path will be found rapidly to have the float spread around to relieve the congestion state.Compared with OLSR，the strategy proposed in this paper will reduce the packet loss ratio and the average end-to-end delay at the same time，which illustrate that it will make use of networking resource effectively.

2 Ant Colony Algorithm

Enlightened by the ants routing mechanism，Saleem et al.［8］presented an ant routing algorithm.Each node in the network will not maintain a routing table，but a probability table instead，which is known as the pheromone table，for the value of probability corresponds to the pheromone intensity.Pndrepresents the probability of the neighbor node n being selected as the next hop of the destination node d in the pheromone table.When the data packets need to be transmitted，it is always the neighbor node with the maximum probability that will be selected as next hop based on the record corresponding with the destination address of data packets in the table.

The ant colony algorithm(ACA)，depending on probability update in pheromone table，simulates the behavior of ants leaving pheromone［9－10］.Every node sends out a packet to select the information of node and the link state periodically.The object of exploring ants is selected randomly，and once arriving at certain node，the ants will change the object address in pheromone table of the current node to be the probability in homologous record of the source node.For every object node，the probability of all neighbor nodes selected，when initializing，is equality in pheromone table.During ants’traveling，the path is always fixed according to the probability value recorded in this table.The raise of probability can be calculated as Eq.(1).

The decrease of the probability can be calculated as Eq.(2).

In Eq.(2)，there is 0≤ Δp≤1，and the exact value is in inverse proportion to the delay of the ants coming through，which has a close relationship with the congestion state.When the congestion appears in a link，the ants undergoing delay will increase，and the probability of this path to be chosen will reduce at the same time［11］.In mobile ad hoc networks，every node has to limit the packet sending frequency to avoid too much overhead;however，it is obvious too slow to respond link congestion state depending on sending packet periodically.So it is not able to relieve the link congestion state rapidly for mobile ad hoc networks.

3 ACA Based Congestion Elusion Algorithm

The purpose to present this algorithm is to speed up the exploration for the optimal route according to the restraint conditions and response to link congestion.The former one can be realized by ants flooding technology and a new probability updating calculation，while the latter will rely on the effect of the former one.The more quickly a new path will be obtained，the easier the information flow will be spread around，so as to realize the congestion elusion.

3.1 Ants Flooding

A way to explore the optimal route between two nodes in the network is to compare all the possible paths between them at the same time.The ants flooding means that a source node sends the packets to all its neighbors simultaneously once it is necessary.The neighbor nodes will copy the packets on all the links but only one information packet will be received.To avoid the number of ants growing infinitely，there is the same identification code for ants which is sent by the source node.The ants with the same ID code belong to the same group.When an ant of a group has been received，its ID code will be recorded，and its copies will be sent on all other links.While another ant of the same group has been got，it will not be necessary to be copied.Each node will receive ant according this kind of ants flooding，and the ants arrive at the same destination where must be along different paths.

3.2 Probability in Pheromone Table to Update

A novel probability updating calculation is proposed in this paper aimed at the ants flooding mechanism for mobile ad hoc networks，which will not only embody the routing selection rule(the shortest path and the maximum bandwidth)but make the probability of selecting the optimal route increase most or reduce least，when many ants from the same source node get to the destination through different paths，so as to impel the optimal route highlight as soon as possible.The new probability raise in the pheromone table is as shown in Eq.(3)，and the probability decrease is as shown in Eq.(4).andin Eqs.(3)and(4)present the probability of node i before and after the update process respectively;Δp(0.5≤p＜1)is a parameter，the value of which depends on the required routing selection strategy and the information of ants carried back.The curves about Eqs.(3)and(4)are shown in Fig.1，from which it can be seen that probability changing range has a close relationship with the value of Δp.

The bigger Δp is set，the larger probability changing range will be obtained.Consequently， Δp can be used in response to the routing selection strategy.

Fig.1 Curves of probability calculation

Eq.(5)is available when what we need is the shortest path or the one with the maximum bandwidth.

hopin Eq.(5)is number of hops from source node to the current one，and f(hop)is increasing function of hop;Bpathis the minimum bandwidth of all links ants which have gone through;Bmaxis the maximum bandwidth of all connected links with the current node;parametersαandβpresent the relative importance to Δp of the distance and bandwidth respectively.

The curves of Eqs.(3)and(4)are symmetries about the line，which will make sure that the probability of selecting the optimal route is always with the most increase or the least decrease when many ants from the same source node reach the same destination along different paths.Fig.2 shows the network structure of two ants setting out from node 3 to 1.

Fig.2 Two ant setting from node 3 move to node 1

In Fig.2，two ants setting from node 3 follow different paths.Since path 3→1 is shorter than path 3→2→1，there is Δp1＞ Δp2.Considering about the changing process of P33when node 1 take route 3→1 as its path to node 3，calculated by Eqs.(3)and(4)，the value of P33will always increase no matter what orders these two ants arrive or how the initialized P33is，which can be seen in Fig.3(a).While calculated by Eqs.(1)and(2)，P33is related to which ant arrives firstly.Fig.3(b)shows a condition that P33reduces，which fails to satisfy the expectation.Only once ants flooding has to be performed，other nodes will calculate to obtain the optimal route adopting ants flooding mechanism and the new probability algorithm.

Fig.3 Changing process of P33

3.3 Congestion Elusion Routing Strategy

The similar way with RED［12］is taken to judge the link congestion state，which is to calculate average length of queue and to compare with the upper limit and floor level.When a congestion node predicts that a certain connected link is to be congested，it will send the congestion notice information to all the destinations which will pass this congesting link to require exploring a new route.Once receiving the notice，object destinations will send congestion reply ants to the congestion node.Congestion reply ants will update all the pheromone tables of nodes being passed through as how exploring ants work，so the congestion ants will keep away from congesting links.It is when the congestion reply ants get to the congestion node that a new non-congesting route will have already been constructed.The congestion node will switch to this newer route at once，which will spread flow around to relieve the congestion state.For mobile ad hoc networks，the former route should not be thrown away but be kept until the congestion node turns to be idle then be switched to，so as to get a stable route for the communication.

4 Realization of CERS

Generally speaking，there are four metrics［13－14］to estimate a routing algorithm:throughput，average endto-end delay，overhead and data packets loss ratio，which is a good beginning point to analyze the evaluation index effectively.Eq.(6)can be used to describe the relationship between throughput and delay，which is called Power in mobile ad hoc networks.

However，Eq.(6)cannot estimate whether the resource allocation is effective or not.It is supposed that the lengths of all packets obey the same distribution，andλirepresents the reaching rate of group i;means average delay in the queue of i;and λis the average reaching rate of the entire system.Then the proffer from i to system average delay isThus the average end-to-end delay in mobile ad hoc networks can be calculated as Eq.(7).

And the former Power will be

Here the throughput can be estimated by the average end-to-end delay［15］based on Eq.(8).Thus in simulation part we only need to consider three metrics to statistic.The packet loss ratio(PLR)can be calculated as Eq.(9).

where n(loss)means the number of packets dropped by network，and n(all)represents the total number of packets entering mobile ad hoc networks.Obviously，n(loss)is the result of congestion.We propose to characterize the performances of mobile ad hoc networks with ant colony algorithm based congestion elusion routing strategy(CERS)on NS2［16］with UDP(User Datagram Protocol)in transport layer and use CBR(Constant Bit Rate)dataflow to generate data.The simulation structure is shown in Fig.4.

Fig.4 Simulating network structure

Transmitting delay is 10 ms.Nodes 8 and 9 has a data source each which obeys the negative exponential switch distribution，and the destination is Node 7.During data transmitting，UDP packets will be sent with the speed of R.Congestion will be produced by overhead accumulated when sending rate R is increased ceaselessly.It is necessary to compare the performance of the link state routing algorithm in different networking overhead and the ant colony algorithm based congestion elusion routing strategy.The overhead of the network can be defined as

whereλis the dataflow average arriving rate，which is the sum of two average rates in simulation;μis the network average service rate，which is 6 Mb/s from Nodes 8 and 9 to Node 7.During the simulation，rate R from Nodes 8 and 9 are the same，which is increasing by 500 kb/s for each step from 2 Mb/s，and the average duration is 100 ms.The upper limit threshold to judge the congestion of every links is 0.6，while the floor level threshold is 0.3.The simulation results are shown in Figs.5 and 6，in which CERS means that taking ant colony algorithm based congestion elusion routing strategy and OLSR is short for optimal state link routing protocol.

Fig.5 Comparisons of PLR with different overhead

Fig.6 Comparison of average delay with different overhead

In Fig.5，the ant colony algorithm based congestion elusion routing strategy(CERS)will greatly reduce PLR for mobile ad hoc networks due to the congestion elusion mechanism.It decreases the average delay between Node 8 and Node 7 but increases that between Node 9 and Node 7 on the other hand，while the delays of all data packets passing through tend to be more consistent，as shown in Fig.6.The delay statistics of the data packets have been made when the overhead in mobile ad hoc network simulating scene is 0.75 to illuminate this character better.Fig.7 shows the probability distribution characteristic of average end-to-end delay for all packets with OLSR and CERS.

In Fig.7，the average end-to-end delay of all data packets is 0.1171 s with congestion elusion routing strategy，while 0.1526 s with the optimal link state routing algorithm.It is obvious that there are more delays of data packets distributing in the region around the mean value with CERS，while with OLSR most of those are near two ends away from the mean value，it is to say，the delay variance with CERS is smaller than that with OLSR.In the view of proportion of data packets do not exceed the upper limit threshold of some delay，congestion elusion routing strategy proposed in this paper excels OLSR for mobile ad hoc networks in performance.

Fig.7 Histogram of data packets transmitting delay when overhead is 0.75

5 Conclusions

Mobile ad hoc network is a complex distributed network system，which consists of many wireless mobile nodes.The characteristics of self-organized，self-healing and all nodes can form a provisional topology freely to allow people and equipments connecting and communication with each other when no fixed communication establishments exist，such as disaster construction and so on.A critical challenge for mobile ad hoc networks is the design of efficient routing protocols which are able to provide high bandwidth utilization and desired fairness，while extensive efforts have been devoted to providing optimization based，distributed congestion elusion strategy for efficient bandwidth utilization and fair allocation in both wired and wireless networks，a common assumption therein is the fixed link capacities，which will unfortunately limit the application scope for mobile ad hoc networks where channels keep changing.In this paper，an effective congestion elusion routing strategy is presented explicitly based on the ant colony algorithm for mobile ad hoc networks，which will explore the optimal route between two nodes promptly，meanwhile forecast the link congestion state.Accordingly，a new path will be found rapidly to have the flow spread around to relieve the congestion state.Compared with OLSR by simulation on NS-2，the scheme CERS proposed in this paper will reduce the packet loss ratio and the average end-to-end delay at the same time，which illustrate thatit will make use of networking resource effectively.

［1］Mahmood T，Nawaz T，Ashrafs R，et al.Gossip based routing protocol design for Ad Hoc networks.International Journal of Computer Science Issues，2012，9(1):177－180.

［2］Li L Q，Li S，Sheng X M，et al.Analysis on topology control boundary conditions in delay tolerant wireless sensor networks.Journal of Harbin Institute of Technology(New Series)，2012，19(3):43－48.

［3］Raw R S，Das S.Performance analysis of P-GEDIR protocol for vehicular ad hoc network in urban traffic environments.Wireless Personal Communications，2013，68(1):65－78.

［4］Huang K B.Spatial interference cancellation for multiantenna mobile ad hoc networks.IEEE Transactions on Information Theory，2012，58(3):1660－1676.

［5］Anantapalli M K，Li W.Multipath multihop routing analysis in mobile ad hoc networks.Wireless Networks，2010，16(2):573－575.

［6］Hall R J.An improved geocast for mobile ad hoc networks.IEEE Transactions on Mobile Computing，2011，10(2):254－266.

［7］Rousseau S，Benbadis F，Lavaux D，et al.Overview and optimization of flooding techniques in OLSR.IEEE International Symposium on a Workd of Wireless，Mobile and Multimedia Networks.Piscataway:IEEE，2011.1－7.

［8］Saleem K，Fisal N，Hafizah S，et al.A self-optimaized multipath routing protocol for wireless sensor networks.International Journal of Recent Trends in Engineering，2009，2(1):93－96.

［9］Chang W，Liu C X，Lin X Q，et al.Balanced energy consuption route protocol based on polymorphic ant colony algorithm for WSN.Computer Engineering，2012，7(1):48－53.

［10］Wei X M.Research on ant colony algorithm in vehicle operation adjustement based on IOT.Journal of Harbin Institute of Technology(New Series)，2013，20(2):17－21.

［11］Abkenar G S，Dana A，Shokouhifar M.Weighted probability ant-based routing in mobile ad hoc networks.Proceedings of the 24th Canadian Conference on Electrical and Computer Engineering.2011.1－4.

［12］Zheng F，Fan X L，Jia Y K.Improved algorithm for adaptive RED.Computer Engineering and Applications，2011，47(11):102－105.

［13］Niazi M，Hussain A.Agent-based tools for modeling and simulation of self-organization in peer-to-peer，ad hoc，and other complex networks.IEEE Communicaitons Magazine，2011，47(3):166－173.

［14］Shah S，Khandre A，Shirole M，et al.Performance evaluation of ad hoc routing protocols using NS2 simulation.Mobile and Pervasive Computing，2008，3(1):167－174.

［15］Upadhyay S，Joshi P K，Gandotra N，et al.Comparison and performance analysis of reactive type DSR，AODV and proactive type DSDV routing protocol for wireless mobile ad hoc network using NS-2 simulator.Journal of Engineering and Computer Innovations，2012，2(10):36－47.

［16］Malik A，Rastogi S，Kumar S.Performance analysis of routing protocol in mobile ad hoc network using NS-2.MIT International Journal of Computer Science＆Information Technology，2011，1(1):47－51.