Keywords

1 Introduction

Wireless Sensor Network (WSN) is a new kind of network composed of a large number of sensors working in uncontrolled areas [1]. Many physical parameters like temperature, humidity, acoustic vibration, pressure, and electromagnetism can be detected by different kinds of sensor nodes [2]. For those various nodes and their communication abilities, WSN can be used for many applications such as disaster relief, environmental control, precision agriculture, medicine and health care [3]. This new technology is receiving increased interest, due to its advantages. Its easy deployment reduces installation cost. It can be distributed over a wide region and has capacity of self-organization. Nonetheless there are some intrinsic limitations for sensors like low processing capacity, low power, and limited lifetime [4]. Hence, new theoretical problems and challenges appear in operations research and optimization field. Some basic optimization problems are related to coverage, topology control, scheduling, mobility and routing [5, 6] But, many researches have tended to focus on routing problems rather than all the previously mentioned problems.

Routing in WSN is very challenging, as it has more different characteristics than that in traditional communication networks [7]. It’s qualified as an NP-hard optimization problem [5]. That means we need robust and efficient techniques to solve this kind of problems, such as metaheuristics [8]. Metaheuristics use search strategies to explore the solution space. These methods begin with a set of initial solutions or an initial population, and then they examine step by step a sequence of solutions to reach or hope to approach the optimal solution of the problem of the interest.

Many metaheuristics, such as Genetic Algorithms (GA) [9], Artificial Bee Colony (ABC) [10], Particle Swarm Optimization (PSO) [11] and Ant Colony Optimization (ACO) [12] are used to solve routing problems [13]. The ACO metaheuristic has been successfully applied to solve routing problem in WSN [12, 14, 15]. Its optimization procedure can be easily adapted to implement an ant based routing algorithm for WSNs. To date, various methods have been developed to solve WSN routing problem, such as Sensor-driven Cost-aware Ant Routing (SC), the Flooded Forward Ant Routing (FF) algorithm, and the Flooded Piggybacked Ant Routing (FP) algorithm [14], Adaptive ant-based Dynamic Routing (ADR) [16], Adaptive Routing (AR) and Improved Adaptive Routing (IAR) algorithm [17], and E&D ANTS [18].

We studied an approach based on ACO for WSN routing problem, proposed by S. Okdem and D. Karaboga [15]. In addition to its safety and efficacy, this approach can be enhanced. So, we proposed an improved one by adding a new kind of ants’ communication, to supply prior information to the other ants.

The remaining of this paper is organized as follows: Sect. 2 gives the WSN routing problem statement. Section 3 introduces Ant Colony Optimization (ACO). Section 4 presents our ACO-based algorithm for the routing problem. Section 5 shows the performance evaluation of our results. Finally, Sect. 6 concludes our work.

2 Routing Problem in Wireless Sensor Networks

Routing is forwarding data from source to destination. The route between both extremities is determined by many techniques relatively to the application field. Routing in wireless sensor networks differs from routing in classical networks. In the case of WSNs we can talk about unreliable links, energy requirements and no infrastructure. Many routing algorithms developed for wireless sensor networks depend on mobility of sensors or sinks, application field and network topology. Overall, the routing techniques are classified according to network structure or protocol operation (routing criteria) [7].

Fig. 1.
figure 1

Routing protocols in WSN: taxonomy [7]

Full size image

Figure 1 shows that in WSN routing protocols, based on network structure, are classified into three categories based on: flat, hierarchical networks, and location based routing. Moreover, these protocols can be classified into multipath, query, negotiation, QoS, and coherent, by considering protocol operation [7]. The studied protocol ranked among flat networks. Routing problem consists on stable sensors and sink. The purpose is to find the best paths that minimize energy consumption, guarantee links reliability (by using acknowledgement signals) and manage bandwidth [15]. All these requirements are considered in the conception of the ACO routing protocol, which described in the following sections.

3 Ant Colony Optimization

Ant colony is considered among the colonies of insects that have a very high capacity to explore and exploit their environment despite their displacement way which is very limited (walking) compared to other species (flying). This moving inconvenience is offset by skills in manipulating and using environment. They use their environment as a medium of storage, processing and sharing information between all the ants in the colony. Inspired from this behavior, M. Dorigo and G. Di Caro have developed in 1999 ant colony optimization algorithms [19]. ACO basic steps are summarized in the Algorithm 1 [20].

figure a

This algorithm discusses two interesting points: The first one is related to the probability of choosing routes, which is used basically in ACO (Eq. 1) to let node \(s\) make a choice by calculating the probability of any node in its coverage area, and then choosing the node \(r\) with the highest probability value. The second one depends on pheromone. At the start ants take routes randomly and left an amount of pheromone \(\tau \) in these routes. This quantity of pheromone is not stable. On one hand it can be decreased by environmental factors (wind, sun, ...), where those factors are presented by the pheromone evaporation rate parameter \(\rho \). On the other hand it increases because all the other ants, when they choose the route, they leave an amount of pheromone \(\delta \tau \).

4 Routing-Based Ant Colony Optimization

S. Okdem and D. Karaboga [15], present a new kind of routing protocol based on ACO where they try to maximize WSN lifetime and minimize energy consumption of sensors. After detecting an event, source node splits data to N parts, every part is transmitted to the next destination by an ant. Ants choose next hop by using two heuristic functions. The first one is related to the quantity of the pheromone, and the second depends on energy. These values appear, where ant \(k\) moving from node \(s\) to node \(r\), in the following probabilistic decision rule (Eq. 1):

$$\begin{aligned} P_k(r,s)= \left\{ {\begin{array}{rl} \frac{ [\tau (r,s)]^\alpha . [\eta (r,s)] ^\beta }{\sum _{r \in R_{s}} [\tau (r,s)] ^\alpha . [\eta (r,s)] ^\beta } &{} \text{ if } \text{ k } \notin tabu^{r} \\ \\ 0 &{} \text{ otherwise } \end{array}}\right. \end{aligned}$$
(1)

Where \(\tau (r, s)\) is a function that returns the pheromone value between node \(s\) and \(r\), \(\eta \) is the first heuristic value related to nodes’ energy level, \(R_s\) are receiver nodes, \(\alpha \) and \(\beta \) are two parameters that control the relative influence of the pheromone trail and the heuristic information, and \(tabu^r\) is the list of packet identities already received by node \(r\) [15]. Pheromone trails are connected to each \(arc (r,s)\) which has a trail value \(\tau \) \( \in \) [0,1]. The heuristic value \(\tau \) of the node \(r\) is expressed by Eq. 2:

$$\begin{aligned} \tau (r,s)={\frac{ (I-e_{s}) ^{-1}}{\sum _{r \in R_{s}}(I-e_{r}) ^{-1}}} \end{aligned}$$
(2)

Where \(I\) is the initial energy, and \(e_r\) is the current energy level of receiver node \(r\). According to this rule, node having information chooses a node destination to forward this information, and so on until sink. This approach gives good results, relatively to routing protocol EEABR proposed by T. Camilo et al. [21]. But these results can be improved, by adding more accuracy to make a choice especially when probabilities are equal. In its decision a node chooses randomly the following node, so it may make wrong choice and loses data in uncovered area, or packets travel a long path to the sink. Therefore many nodes lose power (just because choice was bad), delay of delivery and lifetime decreases. To reduce the number of wrong choices, we improved this approach [15]. we kept the same ACO solution modeling as in [15] but we made decision rule more precise by adding a new heuristic value \(\delta \). So, the new probabilistic decision rule is as follows (Eq. 3):

$$\begin{aligned} P_k(r,s)= \left\{ \begin{array}{rcl} \frac{ [\tau (r,s)]^\alpha . [\eta (r,s)]^\beta . [\delta (r,s)]^\gamma }{\sum _{r \in R_{s}} [\tau (r,s)]^\alpha . [\eta (r,s)]^\beta . [\delta (r,s)]^\gamma } &{} \text{ if } \text{ k } \notin tabu^{r}\\ \\ 0 &{} \text{ otherwise } \end{array}\right. \end{aligned}$$
(3)

The heuristic value \( \delta \) (Eq. 4) is used to distinguish the best neighbor, avoiding the use of the wrong nodes, so do not exhausting it. \(\delta \) is related to sensors field \(R_c\). According to Dorigo experimentation [19], the control parameters values are: \(\alpha = 1\), \(\beta = 5\). After many tests, we conclude that the best value of \(\gamma \) is 1. By using this heuristic value \( \delta \), sensors transmit information about sink.

$$\begin{aligned} \delta (r,s)=\left\{ \begin{array}{rl} \frac{E_{s} }{ \sum _{r \in R_{s}}E_{r}} &{} \text{ if } \text{ Sink } \in R_{c}\\ \\ v &{} \text{ otherwise } \end{array} \right. \end{aligned}$$
(4)

Where \(E_r\) is the residual energy of node \(r\) (residual energy is the energy of node at the end of simulation) and \(v\) is a constant that depends on the simulation environment. Node \(r\) having sink in its collection field, must inform neighboring nodes about this detail, to have more chances to be chosen, because packets will attain sink definitely. When sink is not in the \(r\) field, only energy and pheromone are considered in the probabilistic rule. This information allows to take the right choice, and then get a new approach which gives a good result, mainly in energy consumption, WSN lifetime, reliability and packet delivery ratio (PDR) .

5 Simulation and Results

In order to show the performance of our proposal, we simulate the both approaches, improved and original one, in same conditions, using basically MATLAB for implementation. We used a model of sensors based on “First Order Radio Model” of Heinzelman et al. [22] (see Fig. 2). To send and receive a message, power requirements are formulated as follows:

  • To send \(k\) bits to a remote receiver by \(d\) meters, transmitter consumes: \(E_{Tx}(k,d) = (E_{elec} \times k) + ({\epsilon _{amp}} \times k \times d^2) \)

  • To receive \(k\) bits, receiver consumes: \(E_{Rx} (k)= E_{elec}\times k \)

Where \(E_{elec}= 50\,\mathrm{{nJ}}/\mathrm{{bit}}\) and \(\epsilon _{amp}=100\,\mathrm{{nJ}}/\mathrm{{bit}}/\mathrm{{m}}^2\) are respectively energy of electronic transmission and amplification.

Fig. 2.
figure 2

First Order Radio Model [22]

Full size image

Aiming to test several situations, we apply routing protocol on several WSNs with different densities. We deploy randomly a number of sensors varied according to coverage area. We distribute 10 nodes over \(200 \times 200\,\mathrm{{m}}^2\), 20 nodes over \(300 \times 300\,\mathrm{{m}}^2\), 30 nodes over \(400 \times 400\,\mathrm{{m}}^2\), 40 nodes over \(500 \times 500\,\mathrm{{m}}^2\) and finally for \(600 \times 600\,\mathrm{{m}}^2\) we deploy different WSNs, composed by 50, 60, 70, 80 and 100 sensor nodes. The main task of this deployment is to monitor a static phenomenon, and transmit all collected data to the sink, which has an unknown location. In the same setting, related to the original protocol, and using the same metrics (average residual energy) we perform simulation of improved protocol for the purpose of comparing results and confirming their efficiency.

Fig. 3.
figure 3figure 3

Simulation results for different WSNs

Full size image

By performing many simulations we prove that the improved protocol is better than the original one. Figure 3 shows that our improved approach is higher than original approach by considering the average residual energy of 15 runs. Thus, the power consumption is minimized, and the WSN lifetime is maximized especially when densities are high. In order to confirm the efficiency of our proposal, we simulated the transmission of 256 packets in different coverage areas where it deployed randomly a number of nodes (from 10 to 100 nodes). The shown results in Fig. 4 represent the average residual energy of 15 runs.

Fig. 4.
figure 4

Residual energy for different WSNs

Full size image

Figure 4 presents residual energy normalized (all values between 0 and 1) after reception of 256 packets by Sink, for many WSNs with diverse number of nodes. Packet Delivery Ratio (PDR) is the ratio of the correctly received packets at the receiver to the total number of packets sent by the sender. A straightforward method to calculate PDR is to send a number of packets in a period of time. The receiver counts the successful received packets and calculates the PDR  [23]. According to this definition, the PDR can be calculated as in Eq. 5.

$$\begin{aligned} PDR= {\frac{ \text{ Number } \text{ of } \text{ received } \text{ packets } }{ \text{ Number } \text{ of } \text{ transmitted } \text{ packets }}} \end{aligned}$$
(5)

This metric allows knowing if a protocol is able to ship all sent packages. In order to compare PDR of studied and improved approaches, we simulate sending 256 packets, using various WSNs (changing number of nodes). Our approach reduces energy consumption, since the number of lost packets is minimal (Fig. 5). Packets are lost because of many reasons such as dead of nodes in the path, or the lack of the active neighbour nodes.

Fig. 5.
figure 5

Packet Delivery Ratio for different WSNs

Full size image

Figure 5 presents a PDR (%) after reception of 256 packets by Sink for many WSNs with diverse numbers of nodes.

6 Conclusion

This paper presents an improved protocol for WSN routing. The protocol is achieved by using an enhanced ant colony algorithm to optimize the node power consumption and increase network lifetime as long as possible, while data transmission is attained efficiently. To evaluate the performance of our protocol, we implemented in the same conditions, both approaches original and improved one. From the comparison it is concluded that overall performance of our proposal is better than Okdem and Karaboga approach [15], in terms of energy consumption, network lifetime and packet delivery ratio. The future work could be investigate other methods and compare the ant-based algorithm for other proactive and reactive routing protocols.