# An Improved Ant Colony Routing Algorithm for WSNs

Authors: Tan Zhi; Zhang Hui
Journal: Journal of Sensors
 (2015)

---

## Abstract

Ant colony algorithm is a classical routing algorithm. And it are used in a variety of application because it is economic and self-organized. However, the routing algorithm will expend huge amounts of energy at the beginning. In the paper, based on the idea of  Dijkstra algorithm, the improved ant colony algorithm was proposed to balance the energy consumption of networks. Through simulation and comparison with basic ant colony algorithms, it is obvious that improved algorithm can effectively balance energy consumption and extend the lifetime of WSNs.


---

## Body

## 1. Introduction

Ant colony algorithms that emerged by M. Dorigo et al. [1, 2] observe the behaviors of ants foraging for food. It has been quite popular for a wide variety of discrete optimization problems such as the traveling salesman problem, quadratic assignment problem, and job-shop scheduling [3]. Due to the characteristics of self-organization, autooptimizing, and dynamic topology, an ant colony algorithm is applied to the Ad Hoc network, wireless sensor network, and so on. Ant colony based routing algorithm is improved continuously. Kassabalidis et al. [4] proposed Ant-Net algorithm which realizes routing optimization through the forward ants and return ants (forward ants collect node information; return ants use this information update routing table). And ABC algorithm [5] (ant based control algorithm) is based on probability of mode selection and updates the path. This algorithm is only one kind of ants released from source nodes and these ants arrived at destination node after death. The node’s routing table will be updated, when the ant arrives at the destination node.In the paper, we propose improved ant colony algorithm to acquire the optimal path by routing optimization. We try to save the energy consumption and prolong network life under the condition that the path meets the needs.


## 2. Dijkstra Algorithm

### 2.1.  Dijkstra Algorithm

Dijkstra algorithm is proposed by Dutch computer scientist Edsger Wybe Dijkstra to solve problem about the shortest path from an original point to other points in the directed graph.Every point updates the shortest path information from the original point. It is usually defined as follows.SupposeV and T are two sets that represent original point and other points.At the initial moment,O is subsets and coverage of V and t1,t2,…,tm are subsets and coverage of T.Step  1. The distance D(ti) is the shortest distance from original point O to other points except to ti. Calculating D(ti), we could get point x which is the closest point to point O in the set T.Step  2. Stop if the set T is null; otherwise return to Step 1, where S=S∪{x}, T=T-{x}.


## 2.1.  Dijkstra Algorithm

Dijkstra algorithm is proposed by Dutch computer scientist Edsger Wybe Dijkstra to solve problem about the shortest path from an original point to other points in the directed graph.Every point updates the shortest path information from the original point. It is usually defined as follows.SupposeV and T are two sets that represent original point and other points.At the initial moment,O is subsets and coverage of V and t1,t2,…,tm are subsets and coverage of T.Step  1. The distance D(ti) is the shortest distance from original point O to other points except to ti. Calculating D(ti), we could get point x which is the closest point to point O in the set T.Step  2. Stop if the set T is null; otherwise return to Step 1, where S=S∪{x}, T=T-{x}.


## 3. Improved Ant Colony Routing Algorithm

In the ant colony algorithm model, wireless sensor network could be described as an undirected graph. At the beginning, the lack of initial pheromone leads to low solving speed and high consumption, which has affected the overall performance of ant colony algorithm [6, 7]. In order to solve the problem, the improved ant colony algorithm based on Genetic-Ant Colony algorithm [8] is presented. However, it might cause an increase of the break in data transmission after crossover and mutation. In the paper, the idea have been proposed about Dijstra algorithm to improved ant colony algorithm distributing the nodes into the directed graph. It could increase the initial efficiency of algorithm and ensures the stability.


### 3.1. Pheromone Initial Optimization

Node numberm and communication radius R are determined. Let Vi=Φ, i=1,2,…,m, be the set recording the previous node number and Pi=0 the node coefficient. Let dij be the traffic demand between the node i and the node j.Step  1. End point communicates with adjacent nodes. The adjacent nodes P(k=1,2...,m) record the number of termination point and update node coefficient.Ifdo2k is less than the R, the Pk is set as one and O2 is put into the set Vk.Step  2. Get the number S of nodes which could direct communication with start point. The initial value of S is zero, and the value plus one when do1k is less than the R.Step  3. Node j communicates with adjacent node k. When Pj<Pk or Pk=0, the node k updates p and records number of node j until start point gets number of its adjacent nodes j=1,2...,m.Through the operation, the node gets the information about routes from the node to the end point. The routes have no back haul.


### 3.2. Path Choices

Simulated with the search food process of ant colony, the model for basic ant colony algorithm is as follows.SupposeS is a set and s1,s2,…,sm are subsets and coverage of S and, at the initial moment, they are selected; ant will be randomly placed on the m-subsets, assuming that the initial information of each subset τij0=C. The probability of ant k transfer from the subset i to subset j is [9](1)pijk=τijtαηijβ∑t∈allowedtτitαηitβ,j∈allowedt0,otherwise.Among them, t is the iteration number, k is ID (k=1,2,…,m) for ants, and t is the iteration number; allowed t is the next subset selected from ant k; τijt is the pheromone strength from subset i to subset j; ηij is the inspired degree of ant k shifted from subset i to the subset j. These two parameters α and β are accumulation of information and inspired information in the process of ant’s sports, reflecting the relative importance of ants to choose the next subset.In order to balance the energy consumption of nodes, improved ant colony algorithm entered the energy factor based on the basic ant colony routing algorithm to find shorter and high energy path. Then, the improved probability from nodei to node j is defined as follows: (2)pijk=τijtαηijβξijχ∑t∈allowedtτitαηitβξitχ,j∈allowedt0,otherwise.Using the relative factor represents normalization of method, where ξ is relative energy factor which equals residual energy of node j divided by the initial node energy and multiplied by 1.2. The parameters χ are accumulation of information and inspired information in the process of ant’s sports, it reflects the relative energy consumption of ants to choose the next subset.


### 3.3. Pheromone Update

Subsetp is determined, and ant will stop when elements that selected subset contained target node; this will mark the end of the cycle. After all the ants have completed a cycle, the pheromone of subsets is adjusted according to the following equations:(3)τijt+1=1-ρ·τijt+∑k=1mΔτijk,Δτijk=QLk,ifj∈solutionofantk0,otherwise.Among them, 1-ρ is the attenuation coefficient of the pheromone; usually ρ∈[0,1] to avoid unlimited accumulation of informational on subset; Lk is the number of subsets and k selected in this cycle; Q is the pheromone strength; it affected the convergence speed of algorithm to a certain extent.


## 3.1. Pheromone Initial Optimization

Node numberm and communication radius R are determined. Let Vi=Φ, i=1,2,…,m, be the set recording the previous node number and Pi=0 the node coefficient. Let dij be the traffic demand between the node i and the node j.Step  1. End point communicates with adjacent nodes. The adjacent nodes P(k=1,2...,m) record the number of termination point and update node coefficient.Ifdo2k is less than the R, the Pk is set as one and O2 is put into the set Vk.Step  2. Get the number S of nodes which could direct communication with start point. The initial value of S is zero, and the value plus one when do1k is less than the R.Step  3. Node j communicates with adjacent node k. When Pj<Pk or Pk=0, the node k updates p and records number of node j until start point gets number of its adjacent nodes j=1,2...,m.Through the operation, the node gets the information about routes from the node to the end point. The routes have no back haul.


## 3.2. Path Choices

Simulated with the search food process of ant colony, the model for basic ant colony algorithm is as follows.SupposeS is a set and s1,s2,…,sm are subsets and coverage of S and, at the initial moment, they are selected; ant will be randomly placed on the m-subsets, assuming that the initial information of each subset τij0=C. The probability of ant k transfer from the subset i to subset j is [9](1)pijk=τijtαηijβ∑t∈allowedtτitαηitβ,j∈allowedt0,otherwise.Among them, t is the iteration number, k is ID (k=1,2,…,m) for ants, and t is the iteration number; allowed t is the next subset selected from ant k; τijt is the pheromone strength from subset i to subset j; ηij is the inspired degree of ant k shifted from subset i to the subset j. These two parameters α and β are accumulation of information and inspired information in the process of ant’s sports, reflecting the relative importance of ants to choose the next subset.In order to balance the energy consumption of nodes, improved ant colony algorithm entered the energy factor based on the basic ant colony routing algorithm to find shorter and high energy path. Then, the improved probability from nodei to node j is defined as follows: (2)pijk=τijtαηijβξijχ∑t∈allowedtτitαηitβξitχ,j∈allowedt0,otherwise.Using the relative factor represents normalization of method, where ξ is relative energy factor which equals residual energy of node j divided by the initial node energy and multiplied by 1.2. The parameters χ are accumulation of information and inspired information in the process of ant’s sports, it reflects the relative energy consumption of ants to choose the next subset.


## 3.3. Pheromone Update

Subsetp is determined, and ant will stop when elements that selected subset contained target node; this will mark the end of the cycle. After all the ants have completed a cycle, the pheromone of subsets is adjusted according to the following equations:(3)τijt+1=1-ρ·τijt+∑k=1mΔτijk,Δτijk=QLk,ifj∈solutionofantk0,otherwise.Among them, 1-ρ is the attenuation coefficient of the pheromone; usually ρ∈[0,1] to avoid unlimited accumulation of informational on subset; Lk is the number of subsets and k selected in this cycle; Q is the pheromone strength; it affected the convergence speed of algorithm to a certain extent.


## 4. Simulation Result

Computation on simulation examples and comparison with basic ant colony routing algorithm show that improved ant colony routing algorithm is effective. As shown in Figure1, we simulate a stationary network with 48 sensor nodes deployed in the target region of 80m×80m square region. We also initialize that battery energy of each sensor is 1 J and the sensing radius R of each node is 30 m. The default value of ant colony algorithm parameters is set to α=1, β=2, χ=2, ρ=0.7, Q=100, and τint=0.Figure 1
Node distribution.Comparing the life cycle of two algorithms, we suppose energy consumed is 0.1 J by receiving and sending information. As is shown in Figure2, the solid lines signify that improved ant colony routing algorithm and the dotted line represent the basic ant colony routing algorithm. The total energy of the algorithms is the same at the beginning. As time moved on, the improved ant colony routing algorithm has longer running times. After many time tests, as is shown in Figure 3, improved ant colony routing algorithm has longer life cycle, and it is a good way to save resources.Figure 2
Comparison of the duration of the energy consumption in two algorithms.Figure 3
Comparison of life cycle in two algorithms.On the other hand, Table1 shows the comparison with the average routing path of the two algorithms. The average routing path of improved ant colony algorithm has reduced to about a third of basic ant colony algorithm. The improvement measures make the routing reduce. At the same time, the improved algorithm also reduces the energy consumption. We can see that the improved ant colony routing algorithm has more optimum routing path to guarantee the message fluency.Table 1
Average routing distance comparison.
Algorithm
Improved ant colony routing algorithm
Basic ant colony routing algorithm
1
114.354
304.503
2
114.518
269.581
3
114.700
267.072
4
114.261
319.672
5
114.559
339.222
6
113.953
266.705
7
113.710
301.923


## 5. Conclusions

The wireless sensor network has distinguishing characteristics such as weak node calculation ability and energy limited node, so we should make it efficiency and save sources in the design of wireless sensor network routing algorithm. Ant colony algorithm is a new heuristic searching algorithm, which has many advantages in route optimization but wastes some time and energy due to pheromone deficiency. Therefore, this paper puts forward improved ant colony routing algorithm, which is inspired by the Dijkstra algorithm changing the wireless sensor network undirected graph to directed graph and energy equilibrium consumption ideas to improve the ant colony algorithm.Compared with basic ant colony routing algorithm, improved ant colony routing algorithm is an algorithm with low energy and has high performance.



---

*Source: 438290-2015-06-01.xml*