Utilizing Colored Pheromones and Helping Ants for Wireless Mesh Networks Routing ()
1. Introduction
A safe routing in the network will lead to appropriate transfer of data from the source to the destination. This has got a high impact on performance of the network in terms of lower delay and jitter as well as higher throughput. In WMNs (Wireless Mesh Networks), nodes are comprised of mesh routers and mesh clients. Each node operates not only as a host but also as a router, forwarding packets on behalf of other nodes that may not be within direct wireless transmission range of their destinations. For more information about routing in WMNs refer to [1-19].
After a generation of the routing algorithms that used to search the shortest route in order to reach convergence, and in them there was a need for updates in the routing tables, a new generation of algorithms were introduced that operated based on multi agent systems.
In the computer network routing applications, most of the agent-based algorithms have been inspired by the life of the ants because of the distributed environment information. By the help of chemical called pheromones, real ants find the shortest path between the food source and their nest. Schonderwoerd et al. [20] used agents that are similar to ants. In this algorithm each node sends an ant toward random destination d at regular intervals. When the ant reaches node i, the next node selects the next hop j through routing table for node i and after updating the routing table of the node i it will go to node j. In order to updating the routing table, the probability for selecting j as the next node for destination d should be increased and the probability for selecting other nodes neighboring i should be decreased. Caro and Dorigo [21,22] introduced AntNet algorithm based on the ants routing method. In this algorithm, there are two ant-like agents called forward and backward ants and Like Schonderwoerd’s algorithm, each node sends a forward ant toward a specified destination at regular intervals. But unlike the previous algorithm, this ant is only assigned to move toward the concerned destination and obtain information about the path. When arriving at its destination, the forward ant generates another ant, called backward ant and transfers its data to this ant, before dying. The backward ant travels back from the same path as taken by the forward ant and updates the routing table when it gets to each node (with information about the whole path, the backward ant updates the table of nodes, so making better changes in the tables). Camara and Loureiro [23] recommended a routing algorithm called GPSAL (GPS/ ant-like routing algorithm) which is based on GPS (Global Positioning System) and mobile software agents that modeled on ants for routing in ad hoc networks. Soltani et al. [24] added helping ants to the standard AntNet algorithm in the intermediate nodes to update the routing tables, which enhanced the speed of convergence.
But the problem with ants colony based algorithms is that they only use one color (or dimension) of pheromone. Colored Ant System (CAS) [25] introduces “multi-colored pheromones” for solving the issue of graph coloring and distributes agents to the node clusters. The multiple ant colony optimization (MACO) [26] uses multiple ant colonies, each trying to alleviate the inactivity problems and increase the algorithm consistency with the use of specific pheromone colors, but this method does not use the traffic classes. The ARAMA [10] algorithm also tries to justify different aspects of “goodness”, but certainly the needs are not classified in it and different sections are not distributed separately and only one pheromone is used. Labella and Dressler [11] applied the colored pheromones to distribute the work among the nodes in the sensor/actuator networks (SANET). Also Umlauft and Elmenreich [27] introduced an algorithm called CPANT, in which the traffic is distributed into different classes by using colored pheromones.
In this present paper we introduce a hybrid algorithm based on the AntNet algorithm that increases not only speed of convergence, but also the quality of the bandwidth service in the network. We suggest the use of two features:
1) Use of a third agent (updating ants of the neighboring nodes) that increases the cooperation among the nodes and reduces delay rate in data transmission.
In order to reach this goal, besides the forward and backward ants, we use updating ants. When a backward ant arrives to a node, and finds path is a good one, it generates updating ants and sends them to one of the neighbors in order to make them informed about the path. Upon arriving at the destination, the updating ant modifies the node and dies (they are not propagated). Adding this type of new ant helps the neighboring nodes to utilize the information and experiences of their neighbors, as nodes have more information to make decisions [24].
2) Use of colored pheromone for classification of traffic. Using this feature, instead of considering a single goodness criterion, several criteria are considered and the data is transmitted according to the color of the pheromone in the concerned path. In this method, according to path features include bandwidth, delay and jitter, a certain path is selected and ants mark paths throughout the network by depositing pheromones with different colors depending on the suitability of the path for the corresponding traffic classes [27].
The structure of the reminder of this Paper is as follows: first in Section 2 we describe standard AntNet algorithm. Our proposed method is introduced in Section 3. Section 4 explains the simulation results and compares them with the standard AntNet algorithm and CPANT algorithm. Finally, in Section 5 we highlight the conclusions of the paper.
2. AntNet Algorithm
Ants colony algorithm is based on colony of ants in nature. Ants are able to find their way between their nest and the food source by propagation of pheromone. By propagating pheromone on the path, ants actually inform other ants. Suppose ants get to a point where they should make decision to turn right or left and since they don’t know which route is the shortest, they turn left or right by chance (let’s assume 50% choose to turn left and 50% choose to turn right). The shortest path is taken by a larger number of ants because the propagated pheromone is more on that path. After a short period of time, the difference of the volume of pheromone existing on the path will increase so that in the next turns, ants choose the route with larger volume of pheromone and higher probability.
By using mobile agents, AntNet in a way simulates the ants work. The pheromone chemical in AntNet algorithm has been simulated with the probabilities existing in the routing tables. When an ant passes through a path, with the use of specified formulas, the possibility of taking the mentioned path will increase and the possibility of taking other routes will decrease.
In this algorithm, ants are divided into two groups of forward and backward ants. The backward ants utilize the information collected by forward ants during their travel from the source to the destination, therefore no node is updated by forward ants, but they report the conditions of network delay to backward ants. This information is the travel time taken between each node of the network. Backward ants use this information in order to update the node routing tables. Table 1 shows a type of routing table. The items in this routing table are the probabilities and the sum of each row will be equal to one. Ants use these figures to make decision for selecting the next hop [26].
Each node k has got two data structures, which can be updated by agents (N is the total number of the nodes in the network and Nk is the number of neighbors of node k).
The routing table Pk has N rows and Nk columns. In this table, for each pair of nodes (d, n) the probability Pd,n is kept, which is the probability of the goodness of the node n selected as the next node for destination d. Clearly we have
The vector 
keeps
Table 1. An example of routing table, used by ants.
, 
, 
for node k per each node j, where they are average, variance and the shortest Time spent by agents in order to travel from k to j, respectively.
Different Stages of AntNet Algorithm is as follows:
1) Each node of the network sends forward ants to the selected destinations at regular intervals. Based on the local traffic load, the probability of sending forward ant from node s to destination d is obtained with the following formula
where 
is the volume of the data (the number of bits or packages) that is transferred from node s to d.
2) The forward ants choose a route based on the current routing tables. Each neighbor is selected as the next node with the probability of
, where 
is calculated as follow
where 
(Neighbors readiness parameter) is a normalized range between [0, 1] which depends on 
Here, 
is the length of the queue of the packages that are sent from node k to its neighbor n and 
is the weight of 
in calculation of 
that has been obtained experimentally.
If one loop is diagnosed, the ant takes out the nodes existing in the loop from stack and selects another node for moving.
3) The forward ants create a stack and place the travel time to each node inside it.
4) When the forward ants reach destination, they give their stack to backward ants and they die.
5) The backward ants take out the data items from the stack and take the route back toward the starting node.
6) The routing table of each visited node is updated [8, 28-32].
7) After getting to the destination, the backward ant also dies.
3. Methodology
In this section, we describe our hybrid method explicitly. In the presented algorithm, like CPANT algorithm [27], we assume that the traffic is classified into 4 categories Shown in Table 2.
Conversational: such as VOIP or video conference traffic (video conference).
Streaming: where a play-out memory (buffer) can mitigate the effects of jitter and where no interaction (action and reaction) takes place; e.g. watching a video stream or listening to a pod-cast.
Interactive: (active and reactive), with lower bandwidth requirements such as Web surfing and Web applications.
Background: such as Email and large File transfers e.g. FTP (file transfer protocol) or P2P-(Pair to Pair) File sharing.
We introduce these four classes with the notion of color, including Red, Blue, Green and Black.
We use 3 approaches in our method:
1) The ants mark paths throughout the network by depositing pheromones with different colors depending on the suitability of the path for the corresponding traffic classes. For example a path with high bandwidth, low jitter, and low delay is suitable for traffic in the conversational class and would therefore be marked with pheromones of the “Red” color.
2) On the condition that the traffic should be preferably routed with its major color, it can further use paths marked with a color other than its own if no path of appropriate color can be found. For example if all paths are of such high quality that they are all marked with color “Red”, then traffic of classes 2, 3, and 4 can also use these “Red-path” (Figure 1) [27].
3) Traffic is always sent through the best color path, but when the load of the route increases, its pheromone value is reduced over the time and when it becomes worse than grade two path, traffic automatically move to grade two path.
In the proposed algorithm, we use three types of ants: forward ants, backward ants, and updating ants [24] that play the role of creating cooperation between the neigh-
Table 2. The traffic classes and their differing critical and uncritical requirements.
Figure 1. Mapping of different traffic classes and alternative paths for each class.
bors as well as transferring of information. The data structure of this algorithm is similar to AntNet (Routing table Pk and Table Mk).
The stages of hybrid algorithm are as follows:
1) In regular intervals, each node s generates a forward ant and sends it to the destination d. The forward ants mark paths throughout the network by depositing pheromones with different colors depending on the suitability of the path for the corresponding traffic classes.
2) According to AntNet algorithm, the forward ant finds a path to destination d, with an approach to prevent forming of loops and arrives at destination. The forward ant maintains in its memory the particulars and the time required to reach the nodes existing on the path.
3) Upon arriving at the destination, the forward ant transfers its memory to the backward ant and dies. The path is also graded and the grade of the route is added to the backward ant.
The color vector for the current link taken. The color values a, b, c, and d are in the interval [0, 1] and are calculated using thresholds which map link attribute values to percentage values of the color. This mapping can be implemented using a simple lookup table in the routing nodes. The ant keeps an ordered list 
, of the color vectors 
encountered along the way. When the ant reaches to the destination node, the path is graded for all colors by calculating the path grade [27]:
4) The backward ant travels back from the same path that taken by the forward ant and updates the table.
5) If the forward ant has taken the distance between node k to destination d in 
and the backward ant in the node k decides that this is a suitable path, i.e.
, the updating ants are generated at the number of neighbors of K and places the ID of node K and 
and Tk (current time in node k) within their memory and send them to node k’s neighbors (ni’s).
6) When the updating ant enters into the node i from the node k, it would calculate the
,
where Ti is the current time in node i. If we assume that
, we can estimate the time 
required to travel from i to d through the node k by [24]:
Now if
, i will change its routing table for the destination d. Here, the net time spent, is 
and the next node will be k. So, in the routing table i, for the destination d, the possibility of Pkd (possibility of selecting k as the next node for traveling to d) increases and the possibility of selecting other neighbors of node i 
decreases [27]:
Here 
denotes that element of the path grade vector that matches the color of the pheromone being updated. 
denotes the evaporation function and 
represents the enforcement function and 
denoting “the last value”. 
are always used with identical values for
; for example in order to calculate 
value of 
is used.
For all other links that are not placed on the path (meaning an 
hop, provided 
is contrary to
), the value of pheromone will reduce [27]:
Examples of such functions can be in the form of 
and 
that lead to
and 
for
.
4. Experiments and Results
We call our method Modified Colored Pheromones Ant Routing (MCPANT). MCPANT has been simulated by Glomosim 2.03. Considering the randomicity in our simulations, each datum is the mean value of 20 times independent calculations. In this section we want to compare MCPANT with standard AntNet and CPANT Algorithms.
In this simulation, a network topology model with 12 nodes and 17 bidirectional links are used (see Figure 2). Every link has three specifications: delay (ms), jitter (ms), bandwidth (mbps). Nodes 0, 1, 2 and 3 are sources of packet traffic generations. The traffic sources are constant bit rate (CBR), each packet length is 512 bytes and the total simulation time is 500 seconds. Each node has an incoming packet buffer with a maximum capacity of 1024. A traffic route should be determined before a traffic flow is going to be sent off at its generating node, and
Figure 2. Simulation topology with certain bandwidth, delay and Jitter for each link.
the route will be determined according to the routing tables of nodes. The total number of packets generated from different sources for distinctive destinations are 2000 packets. For more details, see Table 3.
4.1. Topology
In the simulation process, we have used the topology proposed in [27] and Shown in Figure 2.
We have defined 4 traffic classes as hereunder:
1) Conversational traffic (red color) with a bandwidth of 20 Mbps and delay of 1 ms and jitters of 1 ms.
2) Streaming traffic (blue color) with a bandwidth of 20 Mbps and delay of 40 ms and jitters of 8 ms.
3) Interactive (web) traffic (green color) with a bandwidth of 8 Mbps and delay of 1 ms and jitters of 16 ms.
4) Background (data) traffic (black color) with a bandwidth of 4 Mbps and delay of 80 ms and jitters of 32 ms.
In each link, based on the features of the link (bandwidth, delay and jitters in the link), the highest color is chosen from among four traffic classes, while in the standard AntNet, there was only one color of pheromone due to non classification of the traffic.
The delay D, for the path R, has been obtained by
Also the jitter J, for the path R, is calculated as follow:
4.2. Metrics of Performance Evaluation
Simulation results of our method are compared with standard AntNet and CPANT based on following criteria.
4.2.1. End to End Delay
End to End Delay is the time required for the information packet to travel from the source to final destination.
Table 3. Parameters of the simulation.
While the algorithm finds the optimum path, this delay be is kept to minimum. When a change or an error is occurred in the network, the quick convergence of the algorithm through the help of quality of the bandwidth will play a crucial role in mitigating the delay. The delay index will therefore be suitable to compare the speed of convergence of algorithms.
4.2.2. Jitter
For some services, the jitters are much more important than the delay itself. In case the algorithm has been delayed for convergence or in case of interference, the jitters will also increase. This index has also been used in comparisons.
4.3. Experiments
Reaching convergence will make the routing tables to be quantified with optimum paths and as a result mitigating the delay and jitters. Hence, if upon the start of each simulation, the data traffic is transmitted throughout the network, we can distinguish through the comparison of the above criteria that which algorithm has reached convergence sooner.
The Cumulative Distribution Function (CDF)
Let 
be a random variable the Cumulative Distribution Function 
is an ascending non-zero and conforming function with a interval range of [0, 1]. This Function shows the possibility that X has got smaller quantity than x, this means:
In Figure 3, the results of delay of standard AntNet algorithm were compared with those of the hybrid algorithm and as you can see the results show that the delay in conversational, streaming and interactive classes is less than in standard AntNet and in the background class, the more time goes ahead, the lower the delay will be than standard AntNet.
Figure 4 shows a comparison of the results of delay in CPANT algorithm and the hybrid algorithm, and due to the existence of updating ants in the intermediate nodes, the speed of convergence has increased and the results of delay have improved in comparison to CPANT algorithm. The overall delay average of the network is decreased 5.23% in comparison to CPANT algorithm because of existence of updating ants.
In figure 5, a comparison has been made between the results of the jitter in standard AntNet algorithm and hybrid algorithm; the results obtained from hybrid algorithm are better than the standard AntNet algorithm and in comparison of the traffic classes, it is also observed that taking the features of the classes into consideration, Class conversational has got the lowest changes and Classes streaming, web and data stand in the next ranks. In figure 6, considering the cumulative distribution
Figure 3. Comparison of the delay in standard AntNet algorithm and hybrid algorithm (MCPANT).
Figure 4. Comparison of the delay in CPANT algorithm and hybrid algorithm (MCPANT).
Figure 5. Comparison of the jitter in standard AntNet algorithm and hybrid algorithm (MCPANT).
Figure 6. Comparison of the jitter in CPANT Algorithm and hybrid Algorithm (MCPANT).
Table 4. Experimental results obtained from 20 simulations of the four competing algorithms.
function (CDF), the results of jitter of CPANT algorithm and the hybrid algorithm have been compared and taking the jitter in alternative classes into consideration and although there are updating ants in the intermediate nodes, the results of the jitter 5/8% have improved compared to CPANT algorithm. As an example, jitter of blue class is decreased from 19.7 ms in CPANT algorithm to 18.715 ms in the hybrid algorithm.
The experimental results for twenty different simulations of these four algorithms are summarized in Table 4.
5. Conclusion and Future Research
In this paper, a hybrid method is presented that uses helping ants for updating the routing tables for speeding up the convergence. In the proposed method, for categorizing the needs traffic classification by the help of colored pheromones.
The simulation of different status of the network and its comparison with the standard AntNet algorithm and CPANT algorithm reveals that the use of hybrid method has both made the convergence speed faster and mitigated the delay and jitter. This is while even with reducing the generation of agents, the hybrid algorithm with a less overload has got a better performance than the compared algorithms. In future we will design and simulate the existing algorithms in a fuzzy state in order to increase the flexibility of the algorithm.