Energy optimization of ant colony algorithm in wireless sensor network

Abstract

An energy consumption optimization algorithm based on ant colony algorithm is proposed for wireless sensor network. The proposed algorithm allows each node in wireless sensor network to save the distance and residual energy of neighbor nodes. Furthermore, in terms of probability selection of the nodes and the pheromone update, this algorithm focuses on the next hop node through the comparison of distance between the nodes and the residual energy, which ensures less possibility of nodes with low energy selected as the next hop. Therefore, the proposed algorithm improves energy load balancing, stability of wireless sensor network and, eventually, extends the life span of the wireless sensor network. The simulation results show that the improved ant colony algorithm avoids too much energy consumption of a certain local node resulting in more uniform energy consumption for each node.

Introduction

A wireless sensor network (WSN) is composed of many nodes with low computing and data processing capabilities. In recent years, it has been widely used in military, medical, and other fields. However, the node’s data processing capability is relatively low and its energy is limited. Meanwhile, the energy of the node is also related to the life span of WSN. The working principle of WSN is the monitoring environment of spatially distributed autonomous sensors. The source node transmits the data to the base station through a range of nodes. Sending and receiving data account for most of the energy consumption. Meanwhile, the consumption of energy is related to the length of the path, which means that short transmission distance of node corresponding to low consumption of energy. Thus, selection of a shortest path for data transmission plays an important role in reducing the energy consumption of the nodes and improving the stability of the WSN.

Currently, the ant colony algorithm is widely used in WSN. The algorithm not only can help the nodes in quickly and effectively finding the shortest path to the sink node but can also improve the work efficiency of the WSN. In the protocol proposed by low-energy adaptive clustering hierarchy (LEACH), ¹ each cluster node sends data to sink node through the cluster heads resulting in high energy consumption by the cluster heads. The ant colony algorithm can help each cluster head to find the shortest path to the sink node. Hence, it reduces the energy consumption of transmission data packet of cluster head and also reduces the burden of the cluster head.

The ant colony algorithm was initially proposed by Dorigo ² in accordance with the ants’ natural ability to find the shortest path between the nest and the food. When the ants find the food, they leave a certain amount of pheromone while returning to the nest. The shortest path has higher pheromone concentration and other ants select the path according to pheromone concentration. As a result, most ants are able to obtain food through the shortest path. In WSN, data packets are just like ants. Each data packet searches for its next hop node according to the pheromone concentration or the distances between the nodes. This avoids the large consumption of local node energy and interferes the balance of nodes’ energy consumption. Thus, this article proposes the energy consumption optimization algorithm based on the ant colony algorithm Improved Ant Colony Algorithm Energy Optimization (IACAEO). The proposed algorithm not only eases the huge consumption of nodes in search of the best path but also balances the WSN node energy consumption.

Related work

In recent years, the ant colony algorithm has been widely used in the WSN. The research on this algorithm has focused on the energy consumption, routing research of WSN, and has combined it with some classic algorithms, such as the genetic algorithm, the step diffusion algorithm, and so on. Camilo et al. ³ improved the ant colony algorithm and proposed an energy-saving routing algorithm (energy-efficient ant based routing (EEABR)). The main role of this algorithm is to reduce the nodes’ memory. In the beginning, the ants had no fixed sink, and they were sent through broadcasting. This made each node’s routing table to contain identification number and corresponding path pheromone of all nodes that required a lot of memory. Thus, the energy consumption of nodes was increased. The EEABR algorithm proposed that the node only needed to save the information of neighbor node in the sink direction and the path corresponding to the pheromone. As a result, the memory was reduced and the WSN was more stable. However, most of the work was concentrated in reducing the ants’ memory but did not focus on reducing the energy consumption of transmitting data.

Liu et al. ⁴ focused on the efficient data query in Intermittently Connected Mobile Ad Hoc Social Networks. A disadvantage of ant colony algorithm has been presented in Dominguez and Cruz-Cortés. ⁵ While selecting the next hop node, the random selection scheduling resulted in selecting the wrong nodes or arriving at the sink node through a long path. In case of the excessive use of node, it compared the residual energy of nodes, and the nodes with low residual energy had less probability to be selected.

Liu et al. ⁶ introduced the mobile opportunistic network which is a self-organizing network that does not require a complete path between the source node and the destination node. A routing algorithm of WSN based on LEACH protocol ant colony algorithm has been proposed in El Ghazi et al. ⁷ for energy prediction. When the ant colony algorithm selects the next hop node, the routing algorithm predicts energy for each candidate node. It predicts the energy of nodes according to the energy consumption of data transmission, the transmission distance, and the times that the rest of the ants are selected.

Ming-Hua et al. ⁸ proposed an algorithm based on the ant colony algorithm and fuzzy system Fuzzing Ant Colony Optimization Algorithm (FACOA). It computed the pheromone and residual energy through three steps: fuzzing, inference, and de-fuzzing. Finally, the ants select the next hop according to the result of fuzzy selection, and Xiao et al. ⁹ introduced the delay tolerant network and proposed the data transmission scheme.

Another algorithm based on step diffusion method and ant colony algorithm has been proposed in a study by Amiri et al. ¹⁰ Its principle is to provide each node with gradient values to determine the path between the nodes and the hops. Then, it calculates the probability of the next hop node. The data authentication architecture in homogeneous networks has been proposed in the works by Xie and Wang ¹¹ and Guo et al. ¹²

Sun and Tian ¹³ focused on the path optimization in WSN based on the genetic algorithm and the traditional ant colony algorithm. However, the problem of energy consumption is ignored. Begum et al. ¹⁴ pointed out the slow convergence rate and the long initialization time of the traditional ant colony algorithm based on genetic algorithm and proposed a method of dividing the ants into two groups in the opposite direction during the path searching process. As a result, the convergence rate was improved.

Shen et al. ¹⁵ proposed a new type of networks has appeared in the daily life which is named underwater sensor networks. And it improved the routing protocols in UWSNs to ensure the reliability of message transmission, which provides a new application scenario for our article.

Orojloo et al., ¹⁶ Tong et al., ¹⁷ and Sharma and Grover ¹⁸ improved the traditional ant colony algorithm from the point of view of energy optimization, but the complexity of the algorithm is high, and a lot of unnecessary calculations are carried out.

Overall, the above-mentioned studies have the same problems. Comparing to all neighbor nodes in a WSN contributes to large energy and memory consumption that reduces the work efficiency. In order to solve this problem, this article presents a method to narrow the search to the next hop node. In the proposed method, the distance between the nodes and the residual energy of nodes are considered for selecting the next hop node. The energy consumption and the pheromone concentration are given a certain weight. In case the residual energy of a node is relatively small, the weight of residual energy of this node increases in the choice of probability, which highlights the importance of the residual energy of nodes. In this way, the nodes with low energy have smaller probability to be selected that narrows the range of candidate nodes and reduces the energy consumption of nodes.

Traditional ant colony algorithm

In the ant colony algorithm, each node maintains a neighbor table and a routing table. The neighbor table records the basic information of its neighbor nodes, such as the distance between the nodes and the node’s residual energy. The routing table is stored with the pheromone in the path. In the initialization of algorithm, each link is given certain concentration of pheromone. In WSN, each ant is equivalent to the encapsulated packets and the ant selects the next hop node according to the pheromone on each path. The source node periodically sends a forward ant and the ant selects the next hop node according to the concentration of pheromone. All the nodes in the path are recorded until the final destination is reached. Ants at node i select the next hop node j according to the probability that is computed by the formula (1) ¹

$$P_{ij}=\frac{{[{\tau }_{ij}]}^{\alpha }\ast {[{\delta }_{ij}]}^{\beta }}{{\displaystyle \sum _{n\in N_i}{[{\tau }_{in}]}^{\alpha }\ast {\left[{\delta }_{in}\right]}^{\beta }}}j\in N_i$$

(1)

where $P_{\mathrm{ij}}$ is the probability of ants selecting the next hop node j from node i. ${\tau }_{\mathrm{ij}}$ is the concentration of pheromone in the path (i, j). N_i indicates the next hop set that the ants can select, in which the neighbor nodes of i are stored excluding the passed nodes. α indicates the weight of controlling the pheromone concentration. β indicates the weight of inspiration energy. The probability of selecting a path (i, j) is the trade-off between the pheromone and the heuristic energy value. Specifically, when the pheromone concentration is large, there is a high probability of selecting the current link. The pheromone concentration between each node is initialized in the same way. The pheromone initialization between node i and node j is shown in equation (2) ³

$${\tau }_{ij}=\frac{1}{d_{ij}}$$

(2)

where $d_{\mathrm{ij}}$ is the distance between node i and node j. Heuristic energy from node i to node j is described in equation (3) ¹

$${\delta }_{ij}=\frac{y}{{\displaystyle \sum _{n\in N_i}{E}_n}}$$

(3)

where $E_j$ is the current energy of the node j and $\sum _{n\in N_i}{E}_n$ is the total energy of the node set. The node j is more likely to be selected if it has more residual energy.

Each forward ant maintains a memory, recording all of the nodes in accordance with the passed path. This record helps the ant in coming back to the source node along the original path and in updating the pheromone concentration of each path. In order to avoid more and more pheromone concentration on the path, the author introduces the pheromone evaporation mechanism that contributes to decrease the pheromone concentration of the path between the current node and its unselected neighbor nodes. The operation ² is shown in equation (4)

$${\tau }_{ij}=\left(1-\rho \right)\ast {\tau }_{ij}$$

(4)

where $\rho$ is the pheromone evaporation rate $(0\le \rho \le 1)$ . After the pheromone evaporation step, backward ants release a certain amount of pheromone ² in the path (i, j), as shown in equation (5)

$$\mathrm{\Delta }{\tau }_{ij}=\frac{w}{c_i^d}$$

(5)

The pheromone which is released in the path is shown in equation (6) ²

$${\tau }_{ij}={\tau }_{ij}+\mathrm{\Delta }{\tau }_{ij}$$

(6)

where w is the weight, which is used to control pheromone concentration. $c_i^d$ is the cost of link from node i to the next node.

In this way, the packet can find the shortest path for transmission after a period of time and the energy consumption during the transmission is reduced. However, the ant prefers to select a path with high level of pheromone over time, which can easily lead to the local optimal path rather than the global optimal path in the end. Meanwhile, the frequent use of path with high concentration leads to the node of the path to consume too much energy and results in load imbalance in the WSN.

Energy optimization of ant colony algorithm

In the ant colony algorithm, the current node finds the next node according to the pheromone concentration of the path and the node’s energy. The pheromone concentration of a certain path increases significantly with more ants passing this path. However, when the pheromone is at a high level, the energy of the node in the path will decrease rapidly. Suppose that there are two paths, one with high pheromone concentration and low residual energy of node, while the second one with low pheromone concentration and high residual energy, according to the traditional ant colony algorithm, ants will continue choosing the path with high pheromone concentration, and the energy of the node on the path will become very low. However, in the IACAEO algorithm, the ants will choose the path with high node residual energy even if the pheromone concentration of that path is relatively low. Therefore, this is not only conducive to ensure the stability of the WSN but also guarantees the energy consumption equilibrium of the node in the WSN. The author proposes that when the node energy decreases to a certain value, the pheromone volatilization rate of the current path should be increased. When other ants pass this path, the pheromone concentration will increase. Additionally, the node notifies its neighbor node of its residual energy when it is lower than a threshold. So, this node has no chance to be selected by its neighbor nodes as the next hop node.

Forward ant packet format

The forward ants save the ID of node that has been visited in the “visit node” field. This helps the backward ant to come back according to the original path, but the nodes that have already visited are not able to be visited again. The forward ant packet format is shown in Table 1. In the table, “Type” is the type of ant that is divided into front and backward ant type, and “Seqnumber” is the serial number of ants. The node determines whether it receives the same ants according to the value of the “Seqnumber,” if so, the ants are discarded. When the source node sends an ant, “Time” begins to record the time.

Table 1.

The forward ant packet format.

Type

Visit node

Seqnumber

Time

In the beginning, the default value of “Type” is “front.” When the ant arrives at the destination, it becomes a backward ant and the field “Type” is changed into “backward.” Then, the backward ant returns in reverse order according to the “Visit node” field. Furthermore, the backward ant that does not reach the resource node may be discarded. When backward ants pass a node, the pheromone of the current path is updated. At the same time, the pheromone of the path volatilizes in a certain rate. Each sensor node maintains a neighbor information table that records relevant information of neighbor nodes. The neighbor information table format is shown in Table 2.

Table 2.

The table structure of neighbor node.

ID

Neighbor_ID

Distance

Residual_energy

Pheromone

The “ID” and the “Neighbor_ID” fields record the node’s ID and all the IDs of neighbor nodes, respectively. Moreover, the “Distance” field records the distance between the two nodes, the “Residual_energy” field records the residual energy of neighbor nodes, and the “Pheromone” field records the pheromone concentration between the two nodes.

Once the node receives the forward ant, the next node is selected according to the information in Table 2. However, the node needs to update the pheromone and the residual energy of the path when it receives the backward ant.

Optimization of probability selection

In case of selecting the next hop node, one of the neighbor nodes is selected as the next hop node based on the traditional ant colony algorithm. For large-scale WSN, this selecting process increases the selecting time and the energy consumption of nodes. Thus, the set of candidate node j for node i is defined as follows

$$List\left(j\right)=\{j\in N(i),d_{jb}<d_{ib}\}$$

(7)

where $d_{\mathrm{jb}}$ is the distance between the candidate node j and the destination node b, and d_ib is the distance between the node i and the destination node b. This method narrows the search range of the node and reduces the time and the energy consumption. The energy consumption of nodes is shown in formula. ⁹ While the node sends l bits data by distance d, the energy consumption is divided into circuit loss and power amplification loss

$$E_{Tx\left(l,d\right)}\{\begin{array}{c}l\ast E_{elec}+l\ast {\epsilon }_{fs}\ast d^2,d<d_0\\ l\ast E_{elec}+l\ast {\epsilon }_{amp}\ast d^4,d\ge d_0\end{array}$$

(8)

where $E_{\mathrm{elec}}$ denotes the energy loss of the circuit. ε_fs and ε_amp are the amplifier coefficients of Free Space (FS) model and Amplifier Multi-Path fading (AMP) model, respectively. The FS model is selected if the transmission distance is less than the threshold d₀. In this case, the energy is proportional to the square of the distance. Otherwise, the AMP model is selected in which the energy is proportional to the fourth power of distance. Especially, ε_fs = 10 pJ/bit/m² and ε_amp = 0.0013 pJ/bit/m⁴.

The energy consumption of the node when receiving l bits data is as follows

$$E_{Rx}\left(l\right)=l\ast E_{elec}$$

(9)

From the energy consumption of node above, it is found that the energy consumption is associated with the distance between the nodes. Specifically, the energy consumption of sending nodes becomes greater if the distance between the nodes gets farther. As a result, the distance between the nodes plays a significant role that cannot be ignored in the selection of the next hop node.

Now, we set $C_i$ as the collection of node $i$ , and we can get it

$$\begin{array}{l}\mathrm{Target}:\max \left(P_{ij}\right)\\ \mathrm{Constraint\; conditions}:i\in C_{i}j\in List\left(j\right)\end{array}$$

(10)

Probability of selecting next hop node j is shown in equation (11)

$$P_{ij}=\left(1-\mu \right)\ast \frac{{[{\tau }_{ij}]}^{\alpha }\ast {[{\delta }_{ij}]}^{\beta }}{{\displaystyle \sum _{n\in N_i}{[{\tau }_{in}]}^{\alpha }}\ast {[{\delta }_{in}]}^{\beta }}+\mu \ast \frac{E_j}{E_{init}}$$

(11)

where ${\tau }_{\mathrm{ij}}$ is the value of the pheromone on path (i, j), $\sum _{n\in N_i}{[{\tau }_{\mathrm{in}}]}^{\alpha }$ indicates the sum of pheromone on the path between the node and its neighbors, and ${\delta }_{\mathrm{ij}}$ is the reciprocal of the distance between the node i and the node j, namely, ${\delta }_{\mathrm{ij}}=1/d_{\mathrm{ij}}$ ; $\sum _{n\in N_i}{\delta }_{\mathrm{in}}=\sum 1/d_{\mathrm{in}}$ show the sum of reciprocal of the $E_j$ distance between the node i and its neighbors; $E_j$ says and $E_{\mathrm{init}}$ indicate the residual energy and the initial energy of node j, respectively, $\mu$ is the weight, $\alpha$ and $\beta$ are the weights of the pheromone and the distance between the nodes, respectively. $\alpha >0$ , $\beta >0$ .

When $E_j/E_{\mathrm{init}}>0.3$ , it shows that the residual energy of node j is 30% greater than the initial energy. The value of $\mu$ is set to 0.2. At this time, the pheromone concentration of the path between the nodes and the distance between the nodes are the main distinguishing factors for node i in the selection process of next hop node j.

Furthermore, when $E_j/E_{\mathrm{init}}>0.3$ , the residual energy of node j is less than 30% of the initial energy. In case of packet losing due to insufficient energy, the value of $\mu$ is set to 0.8. The threshold value is set to about 10% of the initial energy. When $E_j/E_{\mathrm{init}}>0.1$ , it means that the residual energy of node j is less than 10% of the initial energy. In this case, the node j must be excluded from the candidate nodes and should not be selected because low energy may result in packet loss.

Rules of updating pheromone

When the forward ant reaches the destination, it becomes backward ant and returns back in original path. The pheromone information is updated during this process. But, the energy of node cannot be ignored. When the node is locally optimized and is short of energy, it should not be selected as the next hop node. The author proposes that even if a large number of ants pass the path, the increase in the pheromone of this path should be less than its previous value if the current energy is less than 20% of its total energy. Additionally, the pheromone evaporation rate should increase when the ants do not pass this path.

The pheromone updating formula is shown in equations (11) and (12)

$${\tau }_{ij}=\left(1-\rho \right)\ast {\tau }_{ij}+\mathrm{\Delta }{\tau }_{ij}(0<\rho <1)$$

(12)

$$\mathrm{\Delta }{\tau }_{\mathrm{ij}}=\frac{E_j}{E_{\mathrm{init}}}*\frac{w}{d_{\mathrm{jb}}*H}$$

(13)

where $\rho$ and $\mathrm{\Delta }{\tau }_{\mathrm{ij}}$ are the evaporation rate and the increment of the pheromone, respectively, and w is the weight. H is the number of nodes that node i has passed. $d_{\mathrm{ib}}$ is the distance from node j to the destination node b and $E_j/E_{\mathrm{init}}$ is the ratio of the residual energy and the initial energy of node j.

The path pheromone evaporation rate is improved if the node energy is less than 20% of the initial energy. As a result, the increase in the concentration of pheromone less if the node lacks of energy. It also reduces the probability of the node to be selected as the next node, which is beneficial for energy balancing in the WSN. The algorithm flow chart is shown in Figure 1.

Figure 1.

Algorithm flow chart.

Simulation

In this section, the experiment is simulated by MATLAB 7. The simulation of the algorithm focuses on the residual energy of the node and on the influence of different numbers of nodes on the node energy. The simulation parameters are as follows: the initial energy of each node is 10 J. A total of 30 nodes are randomly distributed in packet size of 500 bit. The energy consumption formula is shown in equation (8), ε_fs = 10 pJ/bit/m², ε_amp = 0.0013 pJ/bit/m⁴, E_elec = 50 nJ/bit, α = 1.5, β = 1.5, and ρ = 0.5.The simulation parameters are shown in Table 3.

Table 3.

Simulation parameter table.

Parameter	Value
Area	100 m*100 m
Size of the packet	500 bit
Initial energy of node	10 J
Location of source node	(0, 0)
Eelec	50 nJ/bit
εamp	0.0013 pJ/bit/m4
εfs	10 pJ/bit/m2
A	1.5
B	1.5
P	0.5
d 0	25

Node energy consumption at different thresholds

Since the threshold is set to 0.3 in this article, some simulations are performed to verify that 0.3 is an appropriate value.

It is assumed that there are 25 nodes in which No. 0 is the source node with large initial energy and No. 25 is the destination node. The initial energy of No. 1–No. 24 is 2 J. Now, the residual energy of each node is compared under three different thresholds: 0.3, 0.25, and 0.2.

The comparison of residual energy of each with three different thresholds is shown in Figure 2. The lines with triangular-shaped dots, round dots, and dot-like stars indicate the thresholds 0.3, 0.25, and 0.2, respectively.

Figure 2.

Comparison of residual energy of each node under different thresholds.

According to the fluctuation degree of three lines, it can be seen that the line with triangular-shaped dots seems more balanced than the other two lines, which means that 0.3 is an appropriate threshold value.

As shown in Figure 3, the line with round dots represents the energy consumption after the source node sends many ants based on the traditional ant colony algorithm. The difference of the node residual energy reaches a maximum of 8.8 J indicating that some nodes are used frequently, while others have not been used. Finally, the residual energy of some nodes became 0, such as No. 1, No. 5, No. 6, and No. 11. Since no energy is left, these nodes are broken down. The line with triangular-shaped dots represents the results based on the IACAEO. The difference of the node residual energy reaches a maximum of 2 J indicating that all the nodes maintain a stable energy. As a result, the energy load of nodes in WSN is balanced and the life span of WSN is prolonged.

Figure 3.

Energy consumption of node.

Conclusion

In this article, a new energy optimization method for the ant colony algorithm is proposed. The proposed method utilizes the distance between the nodes and the residual energy of the nodes in order to select the next hop node and assigns certain weights to the energy consumption and the pheromone concentration. Additionally, if the residual energy of the node is less than 20% of the initial energy, the weight of the residual energy of the node increases in the selection probability highlighting the importance of the residual energy of the nodes. In this way, the nodes with low energy have smaller probability to be selected. Furthermore, the pheromone evaporation rate is improved resulting further reduction in the possibility of the node to be selected as the next hop node. Meanwhile, the node is excluded from the candidate node set when its residual energy is less than 10% of the initial energy. The simulation experiments demonstrate that the energy consumption of the node is more averaged than original, which improves the load balancing and prolongs the life span of the WSN.

Additionally, with the continuous development of opportunistic networks, applying the ant colony network to a new scenario will be the future direction of authors’ work.