An Energy-Efficient Multipath Routing Algorithm Based on Ant Colony Optimization for Wireless Sensor Networks

Abstract

An energy-efficient ACO-based multipath routing algorithm (EAMR) is proposed for energy-constrained wireless sensor networks. EAMR is a hybrid multipath algorithm, which is reactive in path discovery and proactive in route maintenance. EAMR has improvement and innovation in the ant packet structure, pheromone update formula, pheromone update mode, and the mechanism of multipath. Average energy consumption and congestion of path make pheromone update formula more reasonable. Incremental pheromone update mode may easily lead to local optimum. The pheromone will be thoroughly updated when a node receives a backward ant. EAMR makes an innovation in multipath mechanism which becomes more reasonable to multipath between source node and destination node. Probabilistic routing mechanism is designed to make stream flow into network more balanced. The simulation results show that the proposed algorithm achieves an improvement in energy efficiency, packet delivery ratio, and end-to-end delay.

1. Introduction

Wireless sensor network (WSN) [1–4] is a new generation of sensor networks, integrating sensors and wireless network technology. It has very broad application prospects and will have a tremendous impact on human life. Wireless sensor network typically has a large number of nodes, which are energy limited and cannot be replenished. Saving and balancing energy consumption of nodes, extending the network lifetime, is one of the primary design goals of wireless sensor networks [5]. Data transmission between two nodes is typically done with conventional multipath routing algorithms such as AOMDV through one same path all the time. It will lead to energy exhaustion of some nodes in the path, causing node failure and network partitioning, which seriously affects the network lifetime. To achieve better load balancing throughout the network, packet forwarding should be based on the current situation of the network. Routing algorithms based on ant colony optimization (ACO), which use control packets called ants to inform each node of the current situation of the network and select next hop according to the probability formula, are ideal for the design of load-balancing multipath routing protocols. ACO-based routing algorithms are one of the hotspots in the present study. On the basis of the analysis of various types of multipath routing protocols, this paper proposes an energy-efficient ACO-based multipath routing algorithm (EAMR) and presents a series of simulations that are conducted to evaluate the performance of EAMR. ACAD (Automatic Clustering inspired by Ant Dynamics) is a simple heuristic algorithm that can automatically detect any number of well separated clusters, which may be any shape, for example, convex and/or nonconvex. Inspired by the dynamics of ants, the algorithm iteratively partitions the dataset based on its proximity matrix. It is different from the existing ant colony based clustering techniques. NISR (a Nature Inspired Scalable Routing protocol for MANETs) protocol is inspired by bees and ant colonies. Ants and bees help each other to find food sources, update quality of paths to these food sources continually, and determine pheromone of paths. PACONET (an improvised ant colony optimization algorithm for MANETs) uses two kinds of mobile agents, FANTs and BANTs. FANTs are transmitted in a controlled broadcast manner to determine new routes. BANTs establish the path based on the information gathered by FANTs. These mobile agents leave certain amounts of pheromones at the time they depart from the node.

2. ACO and ACO-Based Routing Algorithms

Ant colony optimization [6] sources from the optimization mode of ant foraging. Ant colony system (ACS) is a distributed biological system. By collaboration, the ants can complete the arduous task that a single individual is incapable of completing, which is the manifestation of biological swarm intelligence. When ants leave the residence to find food, they release the chemicals called pheromones on the path. The pheromone is volatile. Shorter paths can be completed quicker and more frequently by the ants and will therefore be marked with higher pheromone intensity. These paths will then attract more ants, which will in turn increase the pheromone level, until there is convergence of the majority of the ants onto the shortest path. Ultimately, ants can find the optimal path through the cooperation. Routing in wireless sensor networks follows the same principle. The node which needs to send data packets releases the ant-like packets to the destination node, and the ant-like packets are returned from the destination node, forming a path to the final destination node [7–9].

AntNet [10] is developed according to the principles of ACO. It is also one of the most successful ACO-based routing protocols by far. In AntNet, the concepts of the forward ants and the backward ants are presented. The forward ants choose the next hop randomly according to the heuristic information values in the routing tables. And the ID of the node passed will be appended to the head of the ant. All the forward ants are converted to the backward ants as soon as they arrive at the final destination. The backward ant travels back to the source node through the reverse route and releases pheromones on each link passed by.

ARA [11] is the earliest on-demand multipath algorithm that applies ant colony algorithm to ad hoc wireless networks. Routing discovery relies on forward ants and backward ants. In routing discovery, ARA broadcasts forward ants which only carry a unique sequence number. If a node receives a forward ant that it has never got, it sets up a reverse path and rebroadcasts the ant to the neighbors. On the contrary, if the node has received a duplicate ant, it will drop the ant. By this way, only one path can be formed to the destination. When a forward ant reaches the destination node, it is converted to a backward ant and returns following the reverse path. If an intermediate node receives the backward ant, it creates a path to the destination node (including next hop, destination, and pheromone) and then continues transmitting along the reverse path. Intermediate nodes set up the corresponding routing tables instead of dropping same backward ants. The multipath to the destination node can be formed. The updating of the pheromone relies on data packet and time-setting volatilization. No other types of packets are required; thus overhead is reduced.

In ARAMA [12], when a node needs to establish or maintain a path to the destination node, it sends a forward ant to a neighbor node rather than flooding. Intermediate nodes’ IDs are appended to the forward ant. What is more, path information of the forward ant (such as hops, remaining energy, bandwidth, and queue length) is also appended or changed. ARAMA defines the concept of the grade. The value is calculated by the backward ant and saved in nodes. The formula of the grade relies on the link information such as energy. When an intermediate node receives a backward ant, the pheromone is updated according to the path gradient of the ant. Pheromone of link which is passed by the backward ants is increased, and the other link pheromone volatilizes. The purpose of volatilization is to make nodes forget the old path quicker. The backward ants are deleted when they reach the source node. The data transmits along the best path. When the best path is destroyed, another path can be used to send data packets immediately.

Di Caro et al. proposed AntHocNet protocol [13]. AntHocNet is an ACO-based multipath hybrid routing protocol. The protocol is reactive in path discovery and proactive in route maintenance. The routing algorithm has four major phases: reactive route establishment, random data routing, proactive path maintenance and exploration, and link failure handling.

When a node which does not have route information to the destination node needs to communicate, it broadcasts a forward ant with all its neighbors for path discovery. Each node's routing table has a pheromone table. If the table has pheromone information to the destination node, the forward ant chooses the next hop based on pheromone information in the tables.

The forward ant carries a list which saves the nodes that it has passed. The forward ant changes into a backward ant when it arrives at the destination node. Then the backward ant returns to the source node following the path the forward ant has passed. During the process of returning, the backward ant updates the pheromone table and routing table of the nodes that it passes, including delay, hops, and other information in the tables.

Data packet begins to be sent after the path has been built from the source to the destination. When an intermediate node has multiple routes to the destination node, it stochastically gets the next hop according to the values in phenomenon table.

The advantage of AntHocNet is that it finds multipath in path discovery so that it can reduce frequency of path discovery. And the phase of route maintenance requires a lot of ants. In addition, each node holds a routing table which records all the destination nodes that the node can reach. It is not suitable for large scale networks like AntHocNet.

Rosati et al. [14] proposed the DAR (Distributed Ant Routing) protocol. DAR is a reactive ACO-based routing protocol. Unlike proactive routing, reactive routing protocol need not send the forward ant regularly. When there is no data to transmit, it can reduce cost and the energy consumption of nodes. In the DAR protocol, the forward ants only care about the nodes in cross and choose next hop by only using the pheromone information. The backward ants only release a constant value of flavor in the return link. Nodes stochastically choose the next hop according to the phenomenon when it sends data packets. In the DAR protocol, ants save all the passed nodes’ IDs, so it is suitable for small networks. The network's convergence is slow and sometimes also leads to local optimum.

Wang et al. [15] proposed HOPNET protocol which is a hybrid routing protocol. This protocol divides the network into a plurality of regions and adopts proactive routing in regions and reactive routing between regions. Because the area of every region is not large, the cost of internal proactive routing is not great. HOPNET has more advantages in large networks.

In [16], Misra et al. proposed EAAR protocol based on AntHocNet. Minimum hops count and energy path are taken into account in pheromone update formula. The study of Ducatelle et al. [17] indicates that pheromone update formula is not rational by only considering hops, because fewer hops may cause the longer distance between nodes, and signal intensity may be too low. The connection may be loose and easily leads to network partition. In addition, the farther distance between the nodes can also cause more energy consumption during the data transmission [18].

In [18], it proposes a pheromone diffusion mode of the ant colony algorithm based on routing protocol DBACRA. The protocol is divided into two types, the actual and virtual pheromones, which guide the ant packet and data packet to the path search, when the actual pheromones of the backward ants are from the destination node, releasing the link of the pheromone. Data transmission also needs the actual pheromone to be completed. Virtual pheromones are spread by the destination node; the whole network forms the preliminary virtual pheromones by the certain amount of time. They can guide the forward ants to reach the destination node. The forward ant can guide the actual and virtual pheromones to reach the destination node. As a result of the virtual pheromones being propagated by the diffusion method, in a mobile or relatively large network, the virtual pheromones are also very easy to fall into the loop.

Camilo et al. [19] proposed EEABR (energy-efficient ACO-based routing) protocol. EEABR is an energy-efficient ACO-based routing algorithm. The forward ant's head of the EEABR protocol can save nodes’ IDs with the two recent hops which reduces the length of the forward ant packet, saves the energy consumption of nodes, and prolongs the life of wireless sensor networks. But the EEABR uses the same packet structure of the forward ant and the backward ant which increases the unnecessary energy cost. EEABR regularly sends forward ants in proactive routing mode. In the absence of the data source mode, it reduces the energy consumption of the whole network. At the time of routing maintenance, EEABR not only sends the forward ant by the regular method, but also makes the extra overhead of the protocol. What is more, more packets are forwarded to the path, causing the network energy consumption imbalance and reducing the life-span of the network. In the EEABR protocol, the intermediate nodes discard the ants similar to the forwarded ants, so it cannot form effective multiple paths.

Some of the multipath routing protocols mentioned before do not consider the energy of network. If we follow the traditional ant colony algorithm to find the optimal path, all traffic will be almost focused on a path and it will lead the nodes on this path to die soon. So this type of protocols cannot be directly applied to WSNs. Some protocols, although taking into account the remaining energy on each path, do not consider the rate of the energy consumption. Other protocols do not take into account the network congestion. Considering factors mentioned before and combined with ACO, an energy-efficient ACO-based multipath routing algorithm (EAMR) is proposed. EAMR has improvement and innovation in pheromone update formulas, pheromone update mode, and the mechanism of multipath establishment.

3. Energy-Efficient ACO-Based Multipath Routing Algorithm

Based on the limited energy characteristic of WSN, an ACO-based multipath routing algorithm is proposed in this paper. EAMR uses a new multipath mechanism. In the pheromone update formulas, EAMR takes into account the energy consumption rate of path, the remaining minimum energy of path, the hops from sink, and the congestion status of path. When a source node which does not have routing information to the destination node needs to send data packets, it broadcasts forward ants to the destination sink node. Sink node generates corresponding backward ants, which will travel along the forward path back to the source node. Backward ants release pheromones on the path when they move back to the source node. In traditional way of pheromone updating, pheromone is more and more accumulated on a path so that more and more data packets will be sent on this path. As a result, network cannot automatically balance load. Different from the traditional incremental pheromone update mode, however, pheromone will be thoroughly updated when a node receives a backward ant in EAMR. When a node has multiple paths to the destination node, it will stochastically select one of them in accordance with pheromone to the sink node. The probabilistic routing strategy leads to data load spreading according to the estimated quality of the paths. If the probabilities are kept up-to-date, this will lead to automatic routing load balancing.

3.1. Path Discovery

EAMR is a mixed multipath routing algorithm. It is reactive in the route establishment phase. After route establishment, EAMR is a proactive routing algorithm. When a source node, s, needs to communicate with the destination node, d, and it does not have routing information about d, it broadcasts a reactive forward ant, say $F_s^d$ (here an ant is representative of a control packet). Due to the initial broadcasting, each neighbor of s receives a replica of $F_s^d$ , say $F_s^d·k$ (the notation “k” refers to indexing; the k replica of a single broadcast is represented as $F_s^d·k$ ). After the next hop, the next neighboring node will receive $F_s^d·k·l$ ( $k,l,\dots$ are integers). As these broadcast ants come from the same source node and generate at the same moment, we call them similar ants. Similar ants have the same source node address and sequence. The task of each ant $F_s^d·k·l·m·n\dots$   is to find a path connecting s and d. At each node, an ant is either unicast or broadcast, according to whether or not the current node has routing information for d. If current node does not have routing information for d, it broadcasts a forward ant. Otherwise, if routing information is available, the forward ant will choose its next hop j with the probability $P_{jd}^i$ :

$$\begin{array}{cc}& P_{jd}^i=\frac{{{\eta }_{jd}^i}^{{\beta }_{\mathrm{1}}}}{{\sum }_{k\in N_i}{{\eta }_{kd}^i}^{\beta \mathrm{1}}},\end{array}$$

(1)

where ${\eta }_{jd}^i$ is the pheromone of link ( $i,j$ ) in the routing tables whose destination node is d. ${\eta }_{jd}^i$ will be described in detail later in this section. $N_i$ is the set of neighbors on node i in routing tables, through which node i can reach the destination node. ${\beta }_{\mathrm{1}}$ is a factor which is used to adjust the importance of pheromone to forward ants choosing next hop, which is greater than or equal to 1.

When a node receives the first forward ant, it forwards the ant and saves some information about the ant in the access-list (access-list structure in Section 3.4). If the ant received is not one of the similar ants of the first forward ant, the node could receive the ant and forward it. As a special case, if the node is a neighbor of the source node, it only accepts the forward ants that are directly from the source node and rejects any other ants. Therefore, when the node receives a similar ant, it has to carry out the loop detection at first, that is to say, the current node looks into ant's head and searches the identification of itself. If there is a loop, the node drops this ant directly; otherwise the similar ant should follow the multipath mechanism to establish multipath between the source node and the destination node. Steps are elaborated as follows.

First, make a judgment for whether the first hop of received similar ant and the existing similar ant in access-list is same. First hop is the first node the ant arrived at after leaving source node. If it has no similar first hop, current node should compare newly received ant's delay $d_{\mathrm{n}\mathrm{e}\mathrm{w}}$ and hops $h_{\mathrm{n}\mathrm{e}\mathrm{w}}$ with similar ant's delay $d_{\mathrm{s}\mathrm{i}\mathrm{m}}$ and hops $h_{\mathrm{s}\mathrm{i}\mathrm{m}}$ in access-list. If $d_{\mathrm{n}\mathrm{e}\mathrm{w}}<{\lambda }_d\ast d_{\mathrm{s}\mathrm{i}\mathrm{m}}$ and $h_{\mathrm{n}\mathrm{e}\mathrm{w}}<{\lambda }_h\ast h_{\mathrm{s}\mathrm{i}\mathrm{m}}$ , accept the new forward ant. In this paper, ${\lambda }_h$ is set to 1.5 and ${\lambda }_d$ is set to 2.5. The arguments can be adjusted according to different network environments.

Second, if it has similar first hop, EAMR makes a judgment for whether the last hop of received ant and the existing similar ant in access-list are the same. If it has no similar last hop, as soon as $d_{\mathrm{n}\mathrm{e}\mathrm{w}}<{\lambda }_d\ast d_{\mathrm{s}\mathrm{i}\mathrm{m}}$ and $h_{\mathrm{n}\mathrm{e}\mathrm{w}}<{\lambda }_h\ast h_{\mathrm{s}\mathrm{i}\mathrm{m}}$ , EAMR accepts the new forward ant. In this paper, ${\lambda }_h$ is set to 1.5 and ${\lambda }_d$ is set to 2.5. The arguments can be adjusted according to different network environments.

Third, if both first hop and last hop of newly received ant are the same as the similar ant saved in access-list, EAMR accepts the new forward ant only when $h_{\mathrm{n}\mathrm{e}\mathrm{w}}<h_{\mathrm{s}\mathrm{i}\mathrm{m}}$ .

Through this method, multiple paths can be obtained. If a path fails, another path can be used. Multipath contributes to energy and load balancing of the network. Through this method, the forward ant can arrive at the destination node. WSN environment is complex due to network congestion and delay issues. In order to reduce the unnecessary cost, some ants that reach the destination node “too late” will be dropped, and the destination node does not send backward ants accordingly. When the destination node receives a forward ant and has never received its similar ants before, the destination node starts a waiting timer. Those ants who arrive after waiting timer timeout will be dropped and do nothing. Waiting timer timeout interval is calculated by (2). We can see in Section 3.4 that the structure of forward ants contains the Src_time field, which records the time when ants leave the source node, so that the end-to-end delay $T_{s-d}$ will be very easy to get. $C_d$ is a parameter which can be adjusted appropriately according to the network environment:

$$\begin{array}{cc}& T_d=C_d\times T_{s-d}.\end{array}$$

(2)

During the $T_d$ time interval, as shown in Figure 1, when the destination node receives a forward ant, it will convert the ant into the corresponding backward ant, which will go back to the source node through the route the same as the forward one did. If an exception occurs with the next hop of the backward ant, such as change of the location of the node, then the ant will be killed. When a backward ant from node j moves to node i, the pheromone of node i needs to be updated; node i should update or create routing information to the destination node, according to the following rule:

$$\begin{array}{cc}& {\eta }_{j,d}^i=\frac{{\text{Min}}^{k_{\mathrm{1}}}}{\left({\mathrm{E}\mathrm{T}\mathrm{X}}^{k_{\mathrm{2}}}\ast T_{s-i}^{k_{\mathrm{3}}}\ast E_{\mathrm{a}\mathrm{v}\mathrm{g}}^{k_{\mathrm{4}}}\right)},\end{array}$$

(3)

where ETX [20] (the expected transmission count metric) of a link is the minimum expected pathway which the total number of data transmissions (including retransmissions) required to successfully send a data packet to the destination. ETX which incorporates the effects of link loss ratios, asymmetry in the loss ratios between the two directions of each link, and interference among the successive links of a path is based on packet delivery ratios, which finds high throughput of multihop paths. The ETX of a path is estimated as the accumulation of ETX values over all links constituting the path, which minimizes the transmission cost. Updating of the routing ETX is compared with other routing, which chooses the value of ETX to be the least as the best route, sends the information to the routing module, and is recorded in the routing table. The ETX can decrease the energy consumed per packet. $T_{s-i}$ is the delay from the forward ant leaving source node to the backward ant arriving at the current node. $E_{\mathrm{a}\mathrm{v}\mathrm{g}}$ is the average energy consumption on a path from the source node s to the destination node and can be obtained from the backward ant packet. Min is the energy value of the minimum energy node on the path that backward ant passes. $E_{\mathrm{a}\mathrm{v}\mathrm{g}}$ shows the energy consumption conditions on the path. The larger value of $E_{\mathrm{a}\mathrm{v}\mathrm{g}}$ indicates that more energy has been consumed on the link and more data packets have been transmitted on the path. Hence the nodes on the path should be distributed less load traffic in future data transmission. Min indicates the energy bottleneck of a path. Paths that have energy bottleneck should be also distributed less load traffic in future data transmission. This helps extend the life of the nodes and the network. Sometimes a node's death will lead to the segmentation of the entire network, especially in the case of mobile nodes, where a node may move to the junction of two parts of the network and die early, leading to the segmentation of the network. ETX value of a route which is the sum of the ETX for each link is the link count which the successful transmission (including data retransmission) of a packet required from current node i to the destination node d. According to the feedback mechanism through the MAC layer, if the data gets ACK response information, it will successfully deliver to the destination node. Otherwise the source node has to resend the data packets. When the retransmission reaches a certain threshold, it will discard the packet and the MAC layer will inform the upper network layer that the error occurred in the process of transmitting the data packets. It is a metric based on link capacity; this parameter can not only consider the length of the path, but also consider the packet loss rate. Packets should reach the destination node along the path with the ETX of a link as small as possible. The fewer the ETX of the link counts are, the more pheromones will be released on the link, and packets are more likely to choose this link. What is more, it will shorten the time delay of the data transmission. If the next hop chooses the ETX value which is smaller than itself, so as not to form a loop, $T_{s-i}$ is obtained by current time minus Src_time in the backward ant packet (Src_time will be described in Section 3.4). In general, the path with small transmission delay is better than the big delay path which may be at the congestion state because of relatively large load. According to (3), pheromone is released less in longer delay link. $k_1,k_2,k_3$ , and $k_4$ are coefficients that can be adjusted appropriately according to the network environment.

Figure 1

The paths of forward ant (a) and backward ant (b).

3.2. Data Session

Each node establishes the routing information by ants. Once backward ant returns, the data stored in the buffer can be sent out. The node that needs to send data packets should choose the next hop from a set of neighbors with the probabilistic routing strategy. The probability formula is defined as

$$\begin{array}{cc}& P_{jd}^i=\frac{{{\eta }_{jd}^i}^{{\beta }_{\mathrm{2}}}}{{\sum }_{k\in N_i}{{\eta }_{kd}^i}^{{\beta }_{\mathrm{2}}}},\end{array}$$

(4)

where ${\beta }_{\mathrm{2}}$ is a factor which can adjust pheromones on probabilistic routing selection. The greater the value of ${\beta }_{\mathrm{2}}$ is, the more likely it is to choose the link which has more pheromones as next hop. It can be adjusted appropriately according to the network environment. In this paper, ${\beta }_{\mathrm{2}}$ is an integer value not smaller than 1. The paths that have more load transmission tend to have longer delay and less remaining energy, and through the automatic updates of pheromones, data packets will automatically be sent to the path which has more energy and no congestion. Finally, the entire network is load balanced.

Pheromone evaporation occurs periodically. For every τ time period, nodes evaporate the pheromone value automatically. Equation (5) is the pheromone evaporation formula:

$$\begin{array}{cc}& {\eta }_{j,d}^i={\eta }_{j,d}^i\times \left(\mathrm{1}-\rho \right),\end{array}$$

(5)

where ρ lies between 0 and 0.05.

3.3. Route Maintenance and Link Failures

Each node needs routing maintenance during the data transmission. EAMR uses the way to send forward ant regularly for routing maintenance. When a node begins to send data packets, it produces the forward ant regularly. The interval of sending forward ant is based on the speed of the node movement and network condition. In this paper, interval is set for 5 seconds. But whether to send the forward ant needs to take into account the pheromones in each link of the routing tables and the length of access-list. If the maximum pheromone of all links is less than a threshold and the length of access-list is less than limit value, forward ants could be sent. It can guarantee that forward ants are asynchronously sent in the network. Similarly, when source node receives a backward ant, it can also decide whether to send forward ant according to the above method. If the maximum pheromone exceeds the threshold or the length of access-list is greater than upper limit, it should reset send timer. In this paper, pheromone threshold is set to 30% of original value. The length of access-list upper limit can be set based on network scale and nodes memory size. Upper limit is set to the 20% of total number of nodes in the experiment of this paper.

In order to avoid nodes in the same path sending duplicate forwarding ants, when a node receives a forward ant, it needs to reset the forward ant send timer. As a result, the node which is transmitting data between source node and destination node forwards the ant it received and delays sending the forward ant which is produced by itself. By this way, the node can reduce the number of data packets it sends, thus reduces the cost of network.

Forward ants have two ways for sending, unicasting, and broadcasting, during route maintenance. Unicasting a forward ant whose next hop is decided by (1) only updates the pheromone of the existing path. There is 10% probability to broadcast forward ant. There are two reasons why EAMR has to send broadcast ants: on the one hand, if a unicast packet was sent, it only updates the pheromones which already exists but does not explore new paths (especially under the condition that the nodes had moved or the energy was consumed), this may cause the original routing fail to work. On the other hand, broadcasting ants can explore new paths and avoid falling into local optimum. When a broadcasting ant reaches the neighborhood and the neighbor may have no routing information at the moment, then the neighbor node will continue to broadcast the ant. It will soon cause the flood in the entire network and it is costly. So we are limited to the broadcasting ants. TTL of broadcasting ant is set to 2 (this value can be changed according to the environment) in this paper. That is to say, if the ant does not find a new path after two hops, it will be killed. Because of taking into account the fact that the new path is near the current path, EAMR uses this hop restriction mechanism.

The environment of WSN is complex, so the node in the data transmission process may lose connection with neighbor and cause link failure. Like many other protocols, EAMR protocol also adopts the Hello mechanism, sending Hello message to neighbors regularly. It is easy to find whether the neighbor is reachable and judge whether the link to this neighbor has failed. Of course, it is necessary to inform the neighbor initiatively when the node itself has a fault and makes neighbor nodes find the link failure in time.

When the node finds a link to a neighbor node that has fault, the node should delete the neighbor's information from its neighbor table and routing table. Before deleting, the node should judge whether the removed neighbor is the only next hop node to the destination. If it is the only next hop, the node should send link failure notification to other neighbors. Even though the neighbor node is not the only next hop to the destination node, the route is the best route by viewing the pheromones. The node should also send link failure notification to other neighbors. During the forward ant transmission, the current node needs to save “last hop,” by which the ant sends to current node. If node needs to send link failure notification, it only sends back to the “last hop” without broadcast. It can reduce the cost. The node receiving the link failure notification processes as the same method.

When a node knows the link failure by sending packet failure and there is no other path used to send data packets, the node should start to repair route by sending repairing ants. The mechanism is similar to AODV and the distinction is that, in order to reduce the energy consumption, the repairing ants are not broadcast but sending several repairing ants according to the number of neighbors. Repairing ants have maximum hops limit (hop limit is 3 in this paper). The node starts timer at the time of sending the first repairing ant. If it does not receive the backward repairing ants at the end of the timer, it is obvious that there are no paths to the destination node. As a result, the node has to discard cache data and send link failure notification to its “last hop.”

3.4. Packet Structure of EAMR

In the packet structure of EAMR, the forward ant needs to save all the nodes’ IDs which it has visited in Visitednode list. The list acts as a blacklist when selecting next hop by using probability formula in neighbor table. That is to say, only the nodes which exist in neighbor table and do not exist in the Visitednode have the opportunity to become the next hop. The Visitednode field increases the packet length of the forward ant but avoids a loop. The backward ant also followed the nodes in Visitednode list to return to the source node.

Figure 2 is the packet structure of the forward ant. Type represents the type of packet. Src_address is the source node's address which produces the forward ant. Seqno is the sequence when the source node generates the forward ant. Every forward ant has a unique sequence number. The node which receives the forward ant can use flag $〈\mathrm{S}\mathrm{r}\mathrm{c}\_\mathrm{a}\mathrm{d}\mathrm{d}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{s},\hspace{0.17em}\hspace{0.17em}\mathrm{s}\mathrm{e}\mathrm{q}\mathrm{n}\mathrm{o}〉$ to determine whether it receives a similar ant. Esum is the sum of energy consumption of the Visitednode by the ant. Esum is used for pheromone update. The Src_time field records the time when ants leave the source node. TTL reflects ants’ life-span in the network. It has two main functions; first, it can limit the range of ant search; second, it prevents ants unrestricted in the network circles from wasting source of network. The Visitednode field is used to save all the nodes’ IDs which the forward ant has visited.

Figure 2

Packet structure of forward ant.

Forward ants die out after reaching the destination node, and those which meet the requirements can be transformed into a corresponding backward ant. Figure 3 suggests the packet structure of backward ant. Eavg is average energy consumption in a path from the source node s to the destination node. Esum is divided by the node count of Visitednode to get the Eavg which is calculated by destination node. Eavg is used for pheromone update in (3). Emin is energy value of the minimum energy node on the path that backward ant passes. Src_time is the time when corresponding forward ant leaves the source node. Visitednode is the path which the forward ant passes and gets from the forward ant. Backward ants will go back to the source node through the path the same as the forward one did and update pheromone according to formula (3) in link. There are differences between backward ants and forward ants that the backward ants have no TTL field, because the backward ants have already carried the path information Visitednode. If backward ants’ next hop is unreachable, the backward ants will be dropped. ETX of a path is estimated as the accumulation of ETX values over all links constituting the path. Using ETX for path selection minimizes the transmission cost and achieves a high throughput.

Figure 3

Packet structure of backward ant.

If an intermediate node receives a forward ant which meets the requirement of forwarding, it should save the ant in access-list. Figure 4 is the element table structure of access-list. Each element table corresponds to an ant. The combination of marker $〈\mathrm{S}\mathrm{r}\mathrm{c}\_\mathrm{a}\mathrm{d}\mathrm{d}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{s},\hspace{0.17em}\hspace{0.17em}\mathrm{S}\mathrm{e}\mathrm{q}\mathrm{n}\mathrm{o}〉$ is used to determine whether packet is the similar ants. F_hop is the first hop from source node to current node. L_hop is the last hop from source node to current node. The two marks are mainly used for multipath rule of similar ants. Access-list does not save the whole Visitednode of the forward ant; it can save limited resources of sensor nodes. Hops are the hop count of the source node to the current node. Src_time's meaning is similar with that of the structure of forward ants, which recorded the time when the ant leaves the source node. Hops and Src_time are all used for multipath rule of similar ants. TTL is the survival time of the element table. When an element table is timeout, it will be deleted.

Figure 4

Structure of access-list element table.

Figure 5 is the structure of neighbor table which saves the neighbor's information and pheromone to the destination node. Nei_addr is the address of neighbor. Nei_energy is neighbor's current energy. Hops are the distance of destination node to the neighbor node and hop is the unit. Hops’ initial value is a constant BIGGEST_HOPS when neighbor table is initialized in this paper. The value is set to 9999 which means the neighbor cannot be used as the next hop for packet forwarding. When the node receives a backward ant, the node updates the value of hops and releases the pheromone according to formula (3) on the link. Releasing pheromone means updating the pheromone in Figure 5. Pheromone is to vaporize at regular intervals. The initial value of the pheromone is zero. If it finds there are no pheromones in all the links when a node receives a forward ant, it will broadcast the forward ant. Last_update_time is the time that updates the neighbor node table recently.

Figure 5

Structure of the neighbor table.

Figure 6 is the structure of Hello packet. Src_addr is the address of neighbor that sends Hello packet. Node_energy is the current energy of neighbor. Nodes maintain the neighbor table by sending Hello packet periodically to each other. Hello's sending interval can be different according to the different scenes. Hello interval can be smaller if the mobile node moves fast. In this paper, Hello interval is set to 2 seconds. If it does not receive the neighbor Hello packet more than 6 seconds, the neighbor information should be removed from the neighbor table.

Figure 6

Structure of Hello packet.

3.5. Algorithm of EAMR

See Algorithm 1.

Algorithm 1: EAMR algorithm.

Input:

The following blank tables of all nodes are input:

  ( $$\mathit{1}$$ ) The neighbor table: A table containing all nodes in the neighborhood of a node.

  ( $$\mathit{2}$$ ) Routing table: A table containing the next hop to transfer packets.

  ( $$\mathit{3}$$ ) Access-list: A table containing all distinct paths initialized by source node.

  Initial pheromone for all nodes = 0.

Output:

  Update tables with all the values required to transmit data.

  Pheromone value which takes into account the energy consumption rate of path, the remaining minimum energy path,

the hops from sink and the congestion status of path for selected nodes.

Steps:

  ( $$\mathit{1}$$ ) At its initial stage, nodes should create a connection with their neighbors through broadcasting of Hello packet.

Initialize the access-list of every node as NULL.

  ( $$\mathit{2}$$ ) a source node which needs to transfer data checks in the routing table:

      if the source node exists which there is routing information to destination node:

       the forward ant is sent to next step according to the routing information.

      else

       rebroadcast the forward ant and add the sent forward ant into the access-list.

  ( $$\mathit{3}$$ ) if an intermediate node is the neighboring one of source node:

      accept the forward ant which sends form the node.

      if the intermediate node receives a forward ant which the value of TTL is 1:

       discard it.

      if what the node received is not a similar ant:

       add the ant into the access-list.

       if the ant exists which there is routing information to destination node:

        choose the next step according to the formula (1).

       else

        broadcast a forward ant.

      else

       if the ant which creates a loop:

        discard it.

       else

        follow the multipath mechanism in Section 3.1.

  ( $$\mathit{4}$$ ) if the destination node received forward ant for the first time:

       discard it, create the backward ant which will go back to the source node through the route as same as the

       forward one did and the destination node starts a wait timer.

        if the ants arrive within the time:

         change into backward ants and be back.

        else

         discard them.

  ( $$\mathit{5}$$ ) if the intermediate nodes receive a backward ant:

        delete the comparative ant information which it saved in access-list.

      if the intermediate node is not the neighboring one of destination node:

       calculate the value of pheromone based on formula (3) and release it on link.

      else

       send packet to the destination node and needn't to release pheromone.

  ( $$\mathit{6}$$ ) When the source node receives the first backward ant, the pheromone should be released on link right away. And also

the routing table to destination node should be created. What's more, the source deletes the forward ant information it saved in

access-list. Meanwhile, Data transmission is initiated with each packet. the data saved in cache is sent out. The data packet will

be chosen next hop based on formula (4). If the nodes are the neighboring ones of destination node, it's unnecessary to choose

by formula, it could send packets to the destination node directly.

  ( $$\mathit{7}$$ ) On link failure, Step ( $$\mathit{1}$$ ) is repeated from the node that has't route to send data packet.

4. Simulation Results and Discussion

In order to test the effect of algorithm applied to WSN, this experiment made a comparative analysis of EEABR, EAMR, AOMDV [21], and AntHocNet. NS2 is open source software and an effective simulation tool; it is the mostly used simulation for studies on network. In the simulation environment, all levels can be controlled by the experimenter in the network structure. Users only need to concentrate on the basic element in the experiment, for the rest of the part can be “transparent.” Result can be achieved by configuring the environment parameters of the ideal network environment and can be real-time tracking and record the key nodes of important information. In order to get real-time information about network performance evaluation, experiment follows the reproduction of some special circumstances. It is difficult to do it in the real network. NAM tool in NS2 can demonstrate the operation of the network animation; users can visually see the network protocol, can understand all kinds of environments or other factors on the shadow of the network, and also can be compared to demonstrate the advantages and disadvantages of various methods. The trace of NS2 object in the process of communication can be recorded in the specific event at the trace files; users can use the data processing tools in NS2 gawk to statistical data trace files, analysis throughput, time delay, packet loss rate, and other parameters. The simulation platform is ubuntu 10.04 + NS2.34. We completed the EAMR source codes which match to integrate the NS2, including EAMR packet structures and EAMR agent class, and added the EAMR source codes into the NS2 simulation software. In accordance with the AntHocNet protocol functions, we also realized this protocol for NS2 to make a comparison with EAMR performance.

4.1. Simulation Scene and Factor Setting

The mobile scene file is created by the CMU tool set, sink node on the central location of network. The factor setting of mobile scene is shown in Table 1. CBR is selected to be the scenario of Data flow, which is created by the CMU tool cbrgen.tcl. The factor setting of data stream is shown in Table 2.

Table 1

Factor setting of mobile scene.

Factor	Value
Nodes number of network	100
Range of movement	1500 m ∗ 1500 m
Node communication range	250 m
Node moving speed	10, 20, 30, 40, 50 m/s
Maximum pause time	0 s
Simulation time	100 s

Table 2

Factor setting of data stream.

Factor	Value
Bandwidth	2 Mbps
Type	CBR
Number of CBR sources	20
Packet sending rate	10 packets/s (40 Kbps)
Data packet size	512 byte

In order to facilitate study of the protocol improvement in energy consumption, in this paper, the first-order ratio model [22] is selected for the energy transfer model. The factor setting of sensor nodes is shown in Table 3. The factor setting of EAMR algorithm is shown in Table 4.

Table 3

Factor setting of sensor nodes.

Factor	Value
Type of channel	Channel/wireless channel
MAC type	Mac/802_11
Network interface type	Phy/WirelessPhy
Interface queue model	Queue/drop tail/Pri queue
Transmission of radio	Propagation/two-ray ground
Energy model	Energy model
Routing protocol	AOMDV, EEABR, EAMR, and AntHocNet
Antenna type	Antenna/omniantenna
Node initial energy	2 J
Sink node energy	100 J
Length of the network interface queue	50

Table 4

Factor setting of EAMR.

Factor	Value
β1	1
$$C_d$$	2
$$k_{\mathit{1}}$$	1
$$k_{\mathit{2}}$$	1
$$k_{\mathit{3}}$$	1
$$k_{\mathit{4}}$$	1
β2	1
τ	10
ρ	0.05

4.2. Performance Analysis

The following performance metrics were used for the sake of comparison of our proposed protocol, EAMR, with the benchmark protocols discussed earlier: delivery ratio, delay, routing overhead, and energy efficiency. Several simulation experiments were performed. Some of the key results obtained are reported below.

The relationship between the packet delivery ratio of four kinds of protocol and maximum movement velocity of nodes is shown in Figure 7. Besides AOMDV, the other three protocols for data transmission use the mechanism of multipath probabilistic routing, and the delivery ratio of the three protocols is higher than AOMDV. EEABR performs better than AOMDV, which is designed for the packet delivery ratio. As we introduce mobility in the environment, the performance of these protocols decreases substantially. AntHocNet uses the mechanism of multipath probabilistic routing, but the packets will be more likely to send to the link which has more pheromones. With data packets sent, pheromones will be increased on the link and then a “good” path will come to many load streams. Thus, it will cause local link busy and increase packet loss probability. So AntHocNet is not as good as the EAMR in the slowly moving scene. EAMR uses a better multipath mechanism; pheromone will adjust with current energy and load condition of the path in time, and the data will be more balanced injected into each path of the network. It leads to automatic load balance in network at last. It will be more reasonable for EAMR when the data flow is busy and node movement speed is fast. In addition, the mechanism of link failure recovery of the EAMR is more reasonable. As a result, EAMR outperforms the other three protocols when the routing problems arise. In the moving scene, EAMR protocol shows a better performance in packet delivery than the other three protocols.

Figure 7

Packet delivery ratio.

Figure 8 shows the relationship between the average delays on end-to-end with nodes’ maximum moving speed in four protocols. Obviously, in the aspect of average delay, EEABR, AntHocNet, and EAMR are much better than AOMDV. AntHocNet is more likely to send data packets to delay link of the minimum. AntHocNet has better final results compared to the other two protocols when packet sending rate is slow. When the node moves faster, EAMR presents the better results. On the one hand, the multipath mechanism of EAMR has completed more paths to the destination node than the other two protocols. Pheromone in each link will adjust with current energy and load condition in time, resulting in load balancing. On the other hand, the EAMR will use a mechanism of link failure recovery. When the routing problems arise, it can quickly resume routing and reduce the packet sending blindly and reduce the time delay correspondingly. When a node moves faster, unreachable possibilities of the next hop will increase, and the data packets dropout and routing reconstructs will be increased. In this case, the delay of all the four protocols has tendency to increase.

Figure 8

End-to-end average delay.

ACO-based routing protocols show a good performance in terms of delivery ratio and delay, but such a good performance is increased overhead for the price. In order to adapt to the constant moving and location changing of nodes, EAMR sends the forward ant regularly in route maintenance, through the backward ant update pheromone on paths. What can be seen from the preceding simulation results is that EAMR improves data delivery ratio and reduces the transmission delay, but the regular ant transmission also increases routing overhead. Both AntHocNet and EEABR also regularly send ant package in route maintenance. In many aspects, the routing overhead of EAMR is less than AntHocNet. These aspects include the method of forward ant send in route maintenance, multipath mechanism, pheromone update mechanism based on energy, and improved link maintenance mechanism. As Figure 9 shows, the routing overhead of AOMDV outperforms other protocols.

Figure 9

Routing overhead.

As Figure 10 shows, the definition of average energy consumption is that the average energy is consumed when the final destination node accepts a packet. The smaller the average energy is consumed, the higher the energy efficiency of the network will be. EEABR takes into account the various factors such as the power consumed in transmitting a packet. EEABR, being a multipath energy-aware routing protocol, shows the better performance compared to the past ACO-based existing protocols. The multipath mechanism and the mechanism of link failure recovery of EAMR show the better performance followed by AntHocNet. What is more, EAMR route maintenance mechanism also makes EAMR send less forward ants, which reduces the average energy consumption. The average energy consumption of network is minimal in EAMR. As nodes move faster, the data packets drop and routing request also has sharp increase. It is clear that in the cases with high mobility the results show a higher variation, which decreases with less mobility.

Figure 10

Average energy consumption of network.

5. Conclusions

In this paper, we studied the existing ACO-based routing protocols and proposed EAMR. In the EAMR, the ant packet structure, pheromone update formulas, pheromone update mode, and the mechanism of multipath established are all improved.

In the pheromone update formulas, EAMR takes into account the energy consumption rate of path, the remaining minimum energy path, the hops to the sink, and the congestion of path. Different from traditional incremental pheromone update mode, the pheromone will be thoroughly updated when the node receives a backward ant. With a new multipath mechanism, EAMR can be more reasonable to establish multiple paths between the source node and the final destination node. Probabilistic routing mechanism is designed to make data flow into network more balanced.

In particular, we can make conclusions from the performance of EAMR, EEABR, AOMDV, and AntHocNet. From the simulation results, it is clear that EAMR achieves an improvement in energy efficiency, packets delivery ratio, and end-to-end delay.