# Trail-Using Ant Behavior Based Energy-Efficient Routing Protocol in Wireless Sensor Networks

Authors: Soon-gyo Jung; Byungseok Kang; Sanggil Yeoum; Hyunseung Choo
Journal: International Journal of Distributed Sensor Networks
 (2016)

---

## Abstract

Swarm Intelligence (SI) observes the collective behavior of social insects and other animal societies. Ant Colony Optimization (ACO) algorithm is one of the popular algorithms in SI. In the last decade, several routing protocols based on ACO algorithm have been developed for Wireless Sensor Networks (WSNs). Such routing protocols are very flexible in distributed system but generate a lot of additional traffic and thus increase communication overhead. This paper proposes a new routing protocol reducing the overhead to provide energy efficiency. The proposed protocol adopts not only the foraging behavior of ant colony but also the trail-using behavior which has never been adopted in routing. By employing the behaviors, the protocol establishes and manages the routing trails energy efficiently in the whole network. Simulation results show that the proposed protocol has low communication overhead and reduces up to 55% energy consumption compared to the existing ACO algorithm.


---

## Body

## 1. Introduction

Swarm Intelligence (SI) is one of the Artificial Intelligence (AI) techniques and is a relatively novel field [1–3]. It is studied based on the observation of the collective behavior in biological activities such as ant/bee foraging, division of labor, larval sorting, nest building, and cooperative transport. Ant Colony Optimization (ACO) algorithm is a well-known algorithm in SI [4]. This algorithm is inspired by the actual behavior of ants in which the ants communicate with each other by a mediator called pheromone. Regarding the ACO algorithm, a number of studies have been done on the practical problems such as adaptive routing, resource allocation, and collaborative robotics. Moreover, ACO algorithm has already been applied to solve the routing problem in mobile ad hoc networks and Wireless Sensor Networks (WSNs) [1–3, 5–10].Existing routing protocols based on ACO algorithm for WSNs use specific packet calledants. The packet is to find destination node from every node at regular intervals. The destination can be found using the ants, but it generates a lot of additional traffic and consumes considerable energy [2, 3]. Moreover, the energy consumption by ants noticeably increases when the number of nodes increases. WSNs, typically, consist of resource constrained sensor nodes, and the sensor nodes are with limited energy resource. So, the most important feature of a routing protocol is the energy consumption and the extension of the network’s lifetime. During the recent years, there are ACO-based energy-efficient routing protocols proposed for WSNs [7–10]. The protocols relieve the additional traffic but still consume considerable energy.The main goal of this research is to reduce the additional energy consumption which can be observed in the ACO-based routing protocols and to prolong the network lifetime. The routing protocol proposed in this paper adopts thetrail-using ants behavior, which forms a large network of foraging trails and engages the trails in leaf transport. By adopting the behavior, a routing trail can be formed in an energy-efficient way and reduce the energy consumption for routing. In addition, the network lifetime can be prolonged with trail reestablishment. Simulation results show that the proposed protocol saves up to 55% energy for routing compared to existing routing protocols based on ACO algorithm.The key contributions are as follows:(i)
We propose a novel energy-efficient routing protocol for WSNs.(ii)
The protocol adopts the trail-using ants behavior, which reduces up to 55% energy consumption.(iii)
An extensive simulation is conducted to demonstrate the improvement of the proposed protocol.The rest of this paper is organized as follows. In Section2, we review the basic concept of ACO algorithm and several routing protocols based on ACO algorithm. Section 3 presents a network energy model and assumptions. In Section 4, the details of proposed routing protocol with a novel ant behavior are described. Section 5 explains the performance evaluation environment and shows the results. Finally, we conclude our work in Section 6.


## 2. Related Work

ACO algorithm [4] originates from the actual behavior of ants in which ants communicate indirectly using pheromone. Ants lay pheromone on the ground, and moving direction is determined according to the strength of pheromone. Once the shortest path is found, it will receive more pheromone with higher rate than longer one. It seems that this mechanism only gets a local shortest path, but, in fact, it approaches the global shortest path [3]. ACO algorithm has been studied to address the problems such as asymmetric traveling salesman, vehicle routing, and WSNs routing [1–3, 5]. In particular, a number of studies for routing have been done in WSNs [6–10].AntNet [6] proposed by Di Caro and Dorigo in 1998 is a routing technique inspired by the foraging behavior of ants and is applied for wired networks. The aim of this routing technique is for optimizing the performance of the entire network. AntNet is based on a greedy stochastic policy according to the following rules: (1) forward ants randomly search for destination; (2) after arriving at the destination, the ants travel backwards on the path they used before; (3) all visited nodes are updated with the most adjective information for the destination. Since the goodness of a path is influenced by the travel time of forwards ants, the selections probabilities of path updated by backward ants can influence ants travelling in the forward rather than backward direction.Sensor-Driven Cost-Aware Ant Routing (SC), Flooded Forward Ant Routing (FF), and Flooded Piggybacked Ant Routing (FP) [7] presented by Zhang et al. in 2004 are three ant-based routing algorithms derived from AntNet for WSNs. The authors lead a good start-up of network using the initial pheromone settings. In SC, ants are launched from the sensor nodes to sense the best direction to go. Each sensor node has a routing table and stores the probability distribution of links and the estimated cost to the destination from each neighbor in the table. In FF, forward ants are flooded to the destination. Once forward ants arrive at the destination, backward ants are created and traverse back to the source. The flooding stops if the probability distribution is good enough for the destination. When a shortest path is found, the rate of ants launched is decreased. FP also uses flooding mechanism to launch ants. But the difference is that it combines forward ants with data ants.Energy-Efficient Ant-Based Routing (EEABR) algorithm [8] is proposed by Camilo et al. in 2006. This algorithm is for maximizing the network lifetime of WSNs which is based on ant behaviors. EEABR algorithm aims to reduce the energy consumption related to the ants. In addition, it takes into account the size of ant packet to update the pheromone trail. In the typical ant-based algorithm, each ant carries the information of all the visited nodes. Then, in a network with a number of sensor nodes, the size of information would be so big that it consumes considerable energy to send ants through the network. To solve such a problem, each ant in EEABR algorithm carries only the last visited nodes’ information. Each node keeps the information of the received and sent ants in its memory. Each memory record contains the previous node, the forward node, the ant’s identification, and a timeout value. When a forward ant arrived, a node looks up in its memory. If there is no record, the node records the information, restarts the timer, and forwards the ant to next hop node. Otherwise, the ant is eliminated. Once a node receives a backward ant, it sends the ant to the next node to where the ant must be sent.E-D ANTS [9] proposed by Wen et al. in 2008 is designed to minimize the time delay in packet transfer for the energy constrained Wireless Sensor Networks. This protocol adopts the energy × delay model based on ACO algorithm. The protocol aims at maximizing network lifetime and real time data transmission service. E-D ANTS is proactive and uses unicast transmission of multiple forward ants to discover the minimum energy consumption and delay paths. Each ant carries the residual energy and the hop delay experienced while hopping from node to node.Ladder Diffusion algorithm [10] is presented by Ho et al. in 2012 to address the energy consumption and routing problem in WSNs. The algorithm focuses on reducing the energy consumption and processing time to build the routing table and avoiding the route loop. This algorithm has two phases. In the first phase called Ladder Diffusion phase, each node records hop distance of neighbors in its routing table to avoid the additional traffic of ACO algorithm. After that, the second phase is called route-choosing phase, in which the algorithm selects the routes from sensor nodes to the sink node using the routing table created during the first phase. The path decision is based on the estimated energy consumption of path and the pheromone.In WSNs, energy efficiency is important because of the energy constrained sensor nodes. The aforementioned related works use the ants packet which is periodically sent with the mission to find a path until the destination. When the ants reach the destination, the ants return to their source to update the pheromone. This method creates additional traffic and increases energy consumption. Moreover, there is no specific finish time of the iteration.


## 3. Network Model

In this paper, the radio model is the same as described in [11–13]. In this model, both the free space and multipath fading channels are used. When the distance is less than d0, the free space (fs) model is applied. Otherwise, the multipath (mp) model is used. Eelec is the energy consumed by the electronics circuit per bit. εfs and εmp are the energy consumed by the amplifier in free space and multipath model, respectively. Then, the energy consumed by the radio to transmit an l-bit message over a distance d is given as follows:(1)ETl,d=lEelec+lεfsd2ford<d0lEelec+lεmpd4ford≥d0.The energy consumed by the radio to receive an l-bit message is given as follows:(2)ERl=lEelec.In these models, a radio dissipates Eelec=50 nJ/bit, εfs=10 pJ/bit/m2, and εmp=0.0013 pJ/bit/m4 for the transmitter amplifier. For simplicity of calculation, we only use the free space model εfs.In this paper, we consider WSNs with a number of sensor nodes distributed randomly. Our assumption is as follows:(i)
All nodes are stationary.(ii)
All links are symmetric.(iii)
All nodes can measure the distance between nodes using RSSI [14, 15].(iv)
All nodes are identical in terms of battery capacity, processing, and communication capability.(v)
All nodes are left unattended after deployment and battery recharging is not available.(vi)
There is only one sink node in the entire network.


## 4. Ant-Based Routing Trail Protocol

Since the sensor nodes in WSNs have constrained energy resource, energy efficiency must be considered in the design of routing protocol [16–18]. As we introduced in Section 2, EEABR algorithm considers energy consumption, but it still uses the agent of forward and backward ants, so it generates additional traffic for finding a path to destination [2]. In addition, Ladder Diffusion algorithm still consumes excessive energy because the routing table building requires a large number of messages. The study in [19] shows that trail-using ants form a large network of foraging trails and maintain the trails network connectivity. In the society of trail-using ants, the special worker makes frequent U-turns while marking pheromone trails intensively. Using the marked pheromone, the other workers transport food to their nest. Inspired by the behavior of trail-using ants, we use the concept of relay nodes [17]. With the behaviors and concept, the relay nodes correspond to the marked pheromones and the links of relay nodes represent the pheromone trails.In the proposed protocol, sensor nodes are one of the three types:(i)
Sink. A node that is interested in receiving data packet from a set of relay nodes.(ii)
Ordinary. A node that detects an event and sends the generated data to a relay node.(iii)
Relay. A node that detects an event and is responsible for forwarding the data packet toward sink node.The protocol consists of three phases as follows:(i)
Trail Establishing Phase. The hop distance from the sink node to each node is computed, and the routing trails are established by selecting several relay nodes in a stochastic manner.(ii)
Foraging Phase. The node detecting an event sends the generated data packet to its relay node; then, the data packet is relayed by some relay nodes toward to sink node.(iii)
Trail Reestablishing Phase. When sensor node could not forward its data packet to its relay node, the trail within one hop is reestablished by selecting new relay nodes.


### 4.1. Trail Establishing Phase

In this phase, routing trails are established in the entire network for direction and routes to the sink node. The direction is determined by the hop distance calculated from the sink node, and routes can consist of the relay nodes which are selected in a stochastic manner. This phase involves forming the hop distance from the sink node, broadcasting the trail establishing (ESTA) message, and making the decision of node which received the ESTA message. Figure1(a) shows the initial topology and Figure 1(b) demonstrates the routing trail formed by this phase.Figure 1
The example of topologies.
(a) (b)At the beginning, all nodes initialize the hop distance as infinity, and the sink node sets its hop distance as zero. This phase starts from sink node. Sink node declares its role as a first relay node. The new relay node creates a new ESTA message and broadcasts the message to its neighbors. The ESTA message of relay nodei contains two fields: ID: i, Hop distance: Hop distance of relay node i + 1. Upon receiving the message, the neighbors become candidate relay nodes, set their waiting timer, and wait for the expiration of the timer. Because the trail-using ants randomly make U-turns and intensively deposit their pheromone, the waiting timer is based on probability. The waiting timer could be computed as follows. We refer to [20, 21] for this equation:(3)WTi=randTmin+Tmax-Tmin·2·dijdTX-0.5·HDi,where WTi is the waiting timer of the candidate relay node i. The function rand(x) returns a random value between 0 and x. Tmin and Tmax are the minimum time and the maximum time, respectively. dij is the distance from the candidate relay node i to the sender node j and dTX is the transmission range of a node. Since the distance estimated by RSSI usually introduces error, the normalized value of distance is subtracted by 0.5. Thus, the nodes in the middle of the transmission range of sender node j would have a small waiting time to the candidate relay nodes. This subtracted value can be set by its environment. HDi is hop distance of the candidate relay node i. A node with higher HD value would have longer waiting time. By considering the HD in this calculation, the nodes having smaller hop distance would have smaller waiting timer and the hop distances would be well distributed on the entire network.The candidate relay node whose timer expires first becomes a new relay node among the others. The new relay node initializes its pheromone and broadcasts a new ESTA message. Depending on the status of nodes which received the new ESTA message, there are three reactions: (1) the node which determined its role as an ordinary node just records the information of the new relay node in its routing table; (2) the node, which is waiting for its waiting timer to expire, cancels its timer and decides its role as an ordinary node; and (3) the node that has never received the ESTA message calculates and sets its timer. The steps described above occur repeatedly until every node declares its role and stop after expiration of trail establishment timer.Relay nodes’ placement and connectivity are important in the network performance [17]. If the connectivity is not guaranteed, the circle route might appear. Furthermore, the energy balance between relay nodes can be destroyed when there are no enough relay nodes to forward data packets. We suggest the following mechanism for providing the connectivity. In the first instance, the transmission range is divided into two zones on the basis of middle, inside, and outside. In our proposed protocol, the candidate relay nodes typically cancel their waiting timer upon receiving the new ESTA message. If the candidate node is in the outside zones of two or more relay nodes, the node just waits until its timer expires. By adopting this mechanism, it guarantees the connectivity between relay nodes.Every node updates its hop distance upon receiving the ESTA messages by comparing with its hop distance. If the hop distance included in the message is lower than that the node itself has, the node employs the hop distance. Simultaneously, the hop distance and ID in the message are recorded in the routing table. The routing table is used in the next phase for routing trail selection. In the next phase, the information of relay node is shared by periodical HELLO messages.Figure2 represents the status after broadcasting the new ESTA message from relay node A. Figure 2(a) shows the shift after broadcasting the new ESTA message from relay node C which has determined its role by the ESTA message of relay node A. Node B sets its hop distance as three by comparing with the hop distance which is the same as the message relay node A received. Node E sets its hop distance as four because the message is the same as the message relay node C received. Nodes F and G set their hop distance as five and wait for their waiting timer to expire. Figure 2(b) demonstrates the variation of nodes’ status after broadcasting the new ESTA message from relay node D. Node F located in the outside zone of relay node and inside zone of D cancels its waiting timer. Node G located in the two outside zones is waiting for its waiting timer to expire.Figure 2
The example of trail establishing phase.
(a) (b)


### 4.2. Foraging Phase

When an event is detected by a node, the node generates a data packet and forwards it to its relay node. Each node manages the information of its neighbor relay nodes in their routing table. The relay node periodically broadcasts a HELLO message including its hop distance, pheromone, and residual energy. The nodes receiving the message record the information in their routing table. Furthermore, if the hop distance included in the message is lower than that of the receiver node, the receiver node uses the hop distance as a new one.The node having a data packet to be sent to the sink node selects the next hop relay node referring to its routing table. The set of relay nodes to be selected is only the relay nodes which have lower hop distance than the node having the data packet. Using the information in routing table, the node having higher selection probability can be selected. The selection probability to choose next hop relay node can be calculated using the following equation [1–10, 22]:(4)Pij=τjαηijβφjγ∑l∈Riτlαηilβφlγ.Here, Pij is the selection probability which node i chooses to forward its data packet to relay node j. Ri is a set of the relay nodes having lower hop distance than node i. τj is a pheromone of relay node j, and ηij is the normalized distance between node i and relay node j. φj is the residual energy of the relay node j and it can be calculated using the following equation. α,β, and γ are weight values:(5)φj=1C-ej,where C is the initial energy of the nodes and ej is the residual energy of the relay node j.After calculation of the selection probabilities for the particular nodes, the node having a data packet chooses the relay node, which has the highest selection probability among the nodes, as a next hop relay node. The data packet is sent to the selected relay node and is relayed towards the sink node. Upon sending a data packet to a next hop relay node or the sink node, the relay nodes update their pheromone value using given equation as follows [1–10, 22]:(6)τit=τit-Δt+Δτ,where t is the current time. Δt is the gap of the last updated time. Δτ is the amount of pheromone to be accumulated:(7)τit=e-t-t1·ρ·τit1.Equation (7) is used to update the pheromone of node i, where ρ is the evaporation rate of pheromone and t1 is the last updated time.The procedure finishes once the data packet reaches the sink node.Figure3 represents the multiple paths formed by several relay nodes. Ordinary node A can use one of the paths. In this figure, it is expected that there are many paths to select.Figure 3
The multiple paths in routing trail.


### 4.3. Trail Reestablishing Phase

In this phase, the one hop trail is reestablished when the node has a data packet and is not available to select the next hop relay node. This phase is similar to the trail establishing phase, but this phase just only concerned one hop area toward the sink node.The node, which has a data packet and no relay node to select, becomes a trigger node and initializes this phase. The trigger node broadcasts a trail reestablishment (RESTA) message to its neighbors. RESTA message contains two fields, the same as ESTA message. The nodes having lower hop distance than that one in the message respond to the message. If the receiver node is a relay node, the relay node immediately replies to a trail reestablishment complete (CMP-RESTA) message. If the receiver nodes are ordinary nodes, they set their waiting timer and wait for its expiration. When the waiting timer is expired, the node becomes a new relay node and replies the CMP-RESTA message. Upon receiving the CMP-RESTA message, the trigger node and other nodes record the information in the message. In case that the node is not the trigger node, the node cancels its waiting timer.Trigger node sets its reestablishing timer and waits for CMP-RESTA messages until the expiration of the timer. As the timer expires, trigger node updates its hop distance to the lower one among the values which are in the CMP-RESTA messages. If there is no CMP-RESTA message, the trigger node updates its hop distance increase by 1 and returns back its foraging phase. In case of no relay node to select, this phase is triggered again. These steps are repeated until the relay nodes are founded. From the aforementioned phase, we can say that it is available to rearrange the hop distances in the whole network with dynamic.Figure4 demonstrates an example of this phase. In Figure 4(a), node A is a trigger node, and node B is a new relay node recently determined. Relay node B notifies its role to other nodes with CMP-RESTA message. Figure 4(b) shows the situation that some nodes deplete their energy and cannot be a new relay node. Thus, trigger node B could not receive the CMP-RESTA messages from new relay nodes after broadcasting the first RESTA message. So, the hop distance of node B has been increased. Node A notifies its decision to be a new relay node using a CMP-RESTA message. At this moment, node C cannot receive the message from node C, so the node should be a trigger node and initialize this phase when it is needed. From these two examples, we can say that our proposed protocol is robust and adaptive in the dynamic situation.Figure 4
The example for trail reestablishing phase.
(a) (b)


## 4.1. Trail Establishing Phase

In this phase, routing trails are established in the entire network for direction and routes to the sink node. The direction is determined by the hop distance calculated from the sink node, and routes can consist of the relay nodes which are selected in a stochastic manner. This phase involves forming the hop distance from the sink node, broadcasting the trail establishing (ESTA) message, and making the decision of node which received the ESTA message. Figure1(a) shows the initial topology and Figure 1(b) demonstrates the routing trail formed by this phase.Figure 1
The example of topologies.
(a) (b)At the beginning, all nodes initialize the hop distance as infinity, and the sink node sets its hop distance as zero. This phase starts from sink node. Sink node declares its role as a first relay node. The new relay node creates a new ESTA message and broadcasts the message to its neighbors. The ESTA message of relay nodei contains two fields: ID: i, Hop distance: Hop distance of relay node i + 1. Upon receiving the message, the neighbors become candidate relay nodes, set their waiting timer, and wait for the expiration of the timer. Because the trail-using ants randomly make U-turns and intensively deposit their pheromone, the waiting timer is based on probability. The waiting timer could be computed as follows. We refer to [20, 21] for this equation:(3)WTi=randTmin+Tmax-Tmin·2·dijdTX-0.5·HDi,where WTi is the waiting timer of the candidate relay node i. The function rand(x) returns a random value between 0 and x. Tmin and Tmax are the minimum time and the maximum time, respectively. dij is the distance from the candidate relay node i to the sender node j and dTX is the transmission range of a node. Since the distance estimated by RSSI usually introduces error, the normalized value of distance is subtracted by 0.5. Thus, the nodes in the middle of the transmission range of sender node j would have a small waiting time to the candidate relay nodes. This subtracted value can be set by its environment. HDi is hop distance of the candidate relay node i. A node with higher HD value would have longer waiting time. By considering the HD in this calculation, the nodes having smaller hop distance would have smaller waiting timer and the hop distances would be well distributed on the entire network.The candidate relay node whose timer expires first becomes a new relay node among the others. The new relay node initializes its pheromone and broadcasts a new ESTA message. Depending on the status of nodes which received the new ESTA message, there are three reactions: (1) the node which determined its role as an ordinary node just records the information of the new relay node in its routing table; (2) the node, which is waiting for its waiting timer to expire, cancels its timer and decides its role as an ordinary node; and (3) the node that has never received the ESTA message calculates and sets its timer. The steps described above occur repeatedly until every node declares its role and stop after expiration of trail establishment timer.Relay nodes’ placement and connectivity are important in the network performance [17]. If the connectivity is not guaranteed, the circle route might appear. Furthermore, the energy balance between relay nodes can be destroyed when there are no enough relay nodes to forward data packets. We suggest the following mechanism for providing the connectivity. In the first instance, the transmission range is divided into two zones on the basis of middle, inside, and outside. In our proposed protocol, the candidate relay nodes typically cancel their waiting timer upon receiving the new ESTA message. If the candidate node is in the outside zones of two or more relay nodes, the node just waits until its timer expires. By adopting this mechanism, it guarantees the connectivity between relay nodes.Every node updates its hop distance upon receiving the ESTA messages by comparing with its hop distance. If the hop distance included in the message is lower than that the node itself has, the node employs the hop distance. Simultaneously, the hop distance and ID in the message are recorded in the routing table. The routing table is used in the next phase for routing trail selection. In the next phase, the information of relay node is shared by periodical HELLO messages.Figure2 represents the status after broadcasting the new ESTA message from relay node A. Figure 2(a) shows the shift after broadcasting the new ESTA message from relay node C which has determined its role by the ESTA message of relay node A. Node B sets its hop distance as three by comparing with the hop distance which is the same as the message relay node A received. Node E sets its hop distance as four because the message is the same as the message relay node C received. Nodes F and G set their hop distance as five and wait for their waiting timer to expire. Figure 2(b) demonstrates the variation of nodes’ status after broadcasting the new ESTA message from relay node D. Node F located in the outside zone of relay node and inside zone of D cancels its waiting timer. Node G located in the two outside zones is waiting for its waiting timer to expire.Figure 2
The example of trail establishing phase.
(a) (b)


## 4.2. Foraging Phase

When an event is detected by a node, the node generates a data packet and forwards it to its relay node. Each node manages the information of its neighbor relay nodes in their routing table. The relay node periodically broadcasts a HELLO message including its hop distance, pheromone, and residual energy. The nodes receiving the message record the information in their routing table. Furthermore, if the hop distance included in the message is lower than that of the receiver node, the receiver node uses the hop distance as a new one.The node having a data packet to be sent to the sink node selects the next hop relay node referring to its routing table. The set of relay nodes to be selected is only the relay nodes which have lower hop distance than the node having the data packet. Using the information in routing table, the node having higher selection probability can be selected. The selection probability to choose next hop relay node can be calculated using the following equation [1–10, 22]:(4)Pij=τjαηijβφjγ∑l∈Riτlαηilβφlγ.Here, Pij is the selection probability which node i chooses to forward its data packet to relay node j. Ri is a set of the relay nodes having lower hop distance than node i. τj is a pheromone of relay node j, and ηij is the normalized distance between node i and relay node j. φj is the residual energy of the relay node j and it can be calculated using the following equation. α,β, and γ are weight values:(5)φj=1C-ej,where C is the initial energy of the nodes and ej is the residual energy of the relay node j.After calculation of the selection probabilities for the particular nodes, the node having a data packet chooses the relay node, which has the highest selection probability among the nodes, as a next hop relay node. The data packet is sent to the selected relay node and is relayed towards the sink node. Upon sending a data packet to a next hop relay node or the sink node, the relay nodes update their pheromone value using given equation as follows [1–10, 22]:(6)τit=τit-Δt+Δτ,where t is the current time. Δt is the gap of the last updated time. Δτ is the amount of pheromone to be accumulated:(7)τit=e-t-t1·ρ·τit1.Equation (7) is used to update the pheromone of node i, where ρ is the evaporation rate of pheromone and t1 is the last updated time.The procedure finishes once the data packet reaches the sink node.Figure3 represents the multiple paths formed by several relay nodes. Ordinary node A can use one of the paths. In this figure, it is expected that there are many paths to select.Figure 3
The multiple paths in routing trail.


## 4.3. Trail Reestablishing Phase

In this phase, the one hop trail is reestablished when the node has a data packet and is not available to select the next hop relay node. This phase is similar to the trail establishing phase, but this phase just only concerned one hop area toward the sink node.The node, which has a data packet and no relay node to select, becomes a trigger node and initializes this phase. The trigger node broadcasts a trail reestablishment (RESTA) message to its neighbors. RESTA message contains two fields, the same as ESTA message. The nodes having lower hop distance than that one in the message respond to the message. If the receiver node is a relay node, the relay node immediately replies to a trail reestablishment complete (CMP-RESTA) message. If the receiver nodes are ordinary nodes, they set their waiting timer and wait for its expiration. When the waiting timer is expired, the node becomes a new relay node and replies the CMP-RESTA message. Upon receiving the CMP-RESTA message, the trigger node and other nodes record the information in the message. In case that the node is not the trigger node, the node cancels its waiting timer.Trigger node sets its reestablishing timer and waits for CMP-RESTA messages until the expiration of the timer. As the timer expires, trigger node updates its hop distance to the lower one among the values which are in the CMP-RESTA messages. If there is no CMP-RESTA message, the trigger node updates its hop distance increase by 1 and returns back its foraging phase. In case of no relay node to select, this phase is triggered again. These steps are repeated until the relay nodes are founded. From the aforementioned phase, we can say that it is available to rearrange the hop distances in the whole network with dynamic.Figure4 demonstrates an example of this phase. In Figure 4(a), node A is a trigger node, and node B is a new relay node recently determined. Relay node B notifies its role to other nodes with CMP-RESTA message. Figure 4(b) shows the situation that some nodes deplete their energy and cannot be a new relay node. Thus, trigger node B could not receive the CMP-RESTA messages from new relay nodes after broadcasting the first RESTA message. So, the hop distance of node B has been increased. Node A notifies its decision to be a new relay node using a CMP-RESTA message. At this moment, node C cannot receive the message from node C, so the node should be a trigger node and initialize this phase when it is needed. From these two examples, we can say that our proposed protocol is robust and adaptive in the dynamic situation.Figure 4
The example for trail reestablishing phase.
(a) (b)


## 5. Performance Evaluation

In this section, we evaluate the proposed protocol and compare its performance to two other routing protocols based on ACO algorithm: the EEABR and Ladder Diffusion. The EEABR is well-known routing protocol for energy efficiency. Ladder Diffusion is similar to our proposed protocol. These two protocols are proactive and aim at the energy efficiency for WSNs. Table1 summarizes the comparison of three routing protocols. We used the following metrics to evaluate the performance:(i)
Total energy consumption: the total consumed energy of all sensors.(ii)
Average energy: the average of energy of all sensor nodes.(iii)
Average hop distance: the average hop distance of all data packets passed from a source node randomly chosen to the sink node in the simulation.(iv)
Energy efficiency: the ratio between total consumed energy and the number of packets received by the sink node.Table 1
Comparison of three routing protocols.
EEABR Ladder Diffusion Proposed idea Route selection Proactive Proactive Proactive  Additional traffic HighPeriodically HighInitially and periodically Very lowInitially  Ant behavior Foraging Foraging Exploring and foraging  Characteristics (i) Forward ants (a) Iterative (periodically) (b) Finding the destination(ii) Backward ants (a) Depositing pheromone (b) Returning to the source(iii) Pheromone (a) On the links  (b) Updating with backward ants (i) Ladder table (a) Hop distance from sink (ii) Artificial ants (a) Iterative (periodically) (b) Finding the destination using ladder table(iii) Pheromone (a) On the links (b) Updating with artificial ants (i) Relay node (a) Hop distance from sink (ii) Pheromone (b) On the relay nodes  (c) Updating with data packet


### 5.1. Simulation Environment

The performance evaluation is achieved through simulations using the well-known simulator NS-3 version 3.23. In the simulation, sensor nodes are randomly deployed. The sensor-deployed area is 1,000 m × 1,000 m. The number of nodes varies from 100 to 1,000 with a fixed node number 100. For each case, simulation is run 100 times and we average them to get the mean value. 1,500 data packets are generated by randomly chosen sensor nodes and sent to the sink node. The data packet size is 512 bytes. As we introduced in Section3, we used the same energy model as in [11–13]. Table 2 summarizes the parameters in the simulation.Table 2
Simulation parameters.
Parameter Parameter value Area size 1,000 m × 1,000 m Number of sink nodes 1, center of target area Number of nodes 100 to 1,000 with 100 increments Node distribution Randomly distributed Data packet size 512 bytes Number of data packets 1,500 Transmission range (dTX) 50 m Weight parameters (α, β, γ) (0.33, 0.33, 0.33) Amount of pheromone (Δτ) 1 Pheromone decay rate (ρ) 0.5 Minimum waiting time (Tmin) 30 ms Maximum waiting time (Tmax) 300 ms [21] Initial energy of node (C) 2.0 J [12] Electronics energy (Eelec) 50 nJ/bit [11–13] Amplifier factor for free-space model (εfs) 10 pJ/bit/m2 [11–13] Iteration time of ants (EEABR and Ladder Diffusion) 15 Ant packet size 32 bytes


### 5.2. Simulation Results

The results illustrated in Figure5 are the total energy consumption of all nodes in the simulation. Our proposed protocol saves up to 55% energy compared to EEABR. The Ladder Diffusion adopted the concept of hop count to reduce the additional traffic of ants. EEABR algorithm considered the length of forward ant packet to address the energy consumption problem. Even though the authors proposed Ladder Diffusion and EEABR and introduced their solution, the additional energy consumption still occurred. Lower energy consumption of Ladder Diffusion in the network with 100 nodes is due to the hop count based routing. But after then, the energy consumption increases more than proposed protocol because of the ant packets. As shown in the results, it can be found that the additional traffics are increased by the number of nodes simultaneously.Figure 5
Total energy consumption.As depicted in Figure6, the sensor nodes in our proposed protocol keep more energy compared to the other protocols. In Ladder Diffusion and EEABR, every node generates additional traffic to find path toward sink node. Our protocol did not employ the forward/backward ants mechanism but employed the concept of relay node to avoid the additional traffic. Adopting the concept of relay node, our proposed protocol can keep the energy consumption more balanced than Ladder Diffusion and EEABR. The energy consumption increases by the number of sensor nodes due to the nodes which participate in the data packet relay and generate ants packet. From this result, our proposed protocol reduced the additional traffic in Ladder Diffusion and EEABR. Moreover, it is expected that the network lifetime can be prolonged in our protocol than others.Figure 6
Average residual energy.The results illustrated in Figure7 correspond to the average hop distance required to reach the sink node. The hop distance is calculated by the nodes relaying the data packet which is randomly generated in the random nodes. Ladder Diffusion provides the direction to the sink node by adopting hop count calculation, so the average hop distance is lower than others. In the case of EEABR, the reason why the hop distance of EEABR algorithm is longer than others is that the protocol just considers energy and pheromone. Because of the relay node’s selection in stochastic manner, the hop distance depends on the selected relay nodes. So the hop distance is a little higher than Ladder Diffusion. Thus, the proposed protocol is good in the energy efficiency because there is no additional traffic for finding the path toward sink node.Figure 7
Average hop distance.Figure8 shows the energy efficiency of the three protocols under different network sizes. Proposed protocol is the best at all network size except the first network size, while EEABR is the worst. Ladder Diffusion, in the network size with 100 nodes, has good performance due to the hop distance. The energy efficiency of the three protocols decreases when the network size grows because the hop distance increases.Figure 8
Energy efficiency.


## 5.1. Simulation Environment

The performance evaluation is achieved through simulations using the well-known simulator NS-3 version 3.23. In the simulation, sensor nodes are randomly deployed. The sensor-deployed area is 1,000 m × 1,000 m. The number of nodes varies from 100 to 1,000 with a fixed node number 100. For each case, simulation is run 100 times and we average them to get the mean value. 1,500 data packets are generated by randomly chosen sensor nodes and sent to the sink node. The data packet size is 512 bytes. As we introduced in Section3, we used the same energy model as in [11–13]. Table 2 summarizes the parameters in the simulation.Table 2
Simulation parameters.
Parameter Parameter value Area size 1,000 m × 1,000 m Number of sink nodes 1, center of target area Number of nodes 100 to 1,000 with 100 increments Node distribution Randomly distributed Data packet size 512 bytes Number of data packets 1,500 Transmission range (dTX) 50 m Weight parameters (α, β, γ) (0.33, 0.33, 0.33) Amount of pheromone (Δτ) 1 Pheromone decay rate (ρ) 0.5 Minimum waiting time (Tmin) 30 ms Maximum waiting time (Tmax) 300 ms [21] Initial energy of node (C) 2.0 J [12] Electronics energy (Eelec) 50 nJ/bit [11–13] Amplifier factor for free-space model (εfs) 10 pJ/bit/m2 [11–13] Iteration time of ants (EEABR and Ladder Diffusion) 15 Ant packet size 32 bytes


## 5.2. Simulation Results

The results illustrated in Figure5 are the total energy consumption of all nodes in the simulation. Our proposed protocol saves up to 55% energy compared to EEABR. The Ladder Diffusion adopted the concept of hop count to reduce the additional traffic of ants. EEABR algorithm considered the length of forward ant packet to address the energy consumption problem. Even though the authors proposed Ladder Diffusion and EEABR and introduced their solution, the additional energy consumption still occurred. Lower energy consumption of Ladder Diffusion in the network with 100 nodes is due to the hop count based routing. But after then, the energy consumption increases more than proposed protocol because of the ant packets. As shown in the results, it can be found that the additional traffics are increased by the number of nodes simultaneously.Figure 5
Total energy consumption.As depicted in Figure6, the sensor nodes in our proposed protocol keep more energy compared to the other protocols. In Ladder Diffusion and EEABR, every node generates additional traffic to find path toward sink node. Our protocol did not employ the forward/backward ants mechanism but employed the concept of relay node to avoid the additional traffic. Adopting the concept of relay node, our proposed protocol can keep the energy consumption more balanced than Ladder Diffusion and EEABR. The energy consumption increases by the number of sensor nodes due to the nodes which participate in the data packet relay and generate ants packet. From this result, our proposed protocol reduced the additional traffic in Ladder Diffusion and EEABR. Moreover, it is expected that the network lifetime can be prolonged in our protocol than others.Figure 6
Average residual energy.The results illustrated in Figure7 correspond to the average hop distance required to reach the sink node. The hop distance is calculated by the nodes relaying the data packet which is randomly generated in the random nodes. Ladder Diffusion provides the direction to the sink node by adopting hop count calculation, so the average hop distance is lower than others. In the case of EEABR, the reason why the hop distance of EEABR algorithm is longer than others is that the protocol just considers energy and pheromone. Because of the relay node’s selection in stochastic manner, the hop distance depends on the selected relay nodes. So the hop distance is a little higher than Ladder Diffusion. Thus, the proposed protocol is good in the energy efficiency because there is no additional traffic for finding the path toward sink node.Figure 7
Average hop distance.Figure8 shows the energy efficiency of the three protocols under different network sizes. Proposed protocol is the best at all network size except the first network size, while EEABR is the worst. Ladder Diffusion, in the network size with 100 nodes, has good performance due to the hop distance. The energy efficiency of the three protocols decreases when the network size grows because the hop distance increases.Figure 8
Energy efficiency.


## 6. Conclusion

In this paper, we presented the energy-efficient routing protocol based on the novel behavior of ants, which has never been adopted in routing. The proposed protocol aims at solving the additional traffic problem in the routing protocols based on ant behavior and making routing with energy efficient. For solving the problem, we studied the novel ants behavior and employed the concept of relay node and form the routing trail with several relay nodes selected in stochastic manner inspired by the behavior. Thereafter, the additional traffic that occurred in the ACO algorithm based routing protocols could be reduced. The simulation showed that our proposed protocol not only decreases the total energy consumption up to 55% for routing but also guarantees the maximization of network lifetime.



---

*Source: 7350427-2016-04-06.xml*