A dynamic heuristic for WSNs routing

Abstract

One of the most important issues in the wireless sensor networks (WSNs) is nodes energy. The routing protocols as well as nodes management are considered as the key elements to improve a network’s lifetime. In this research, we have suggested a dynamic heuristic for new nodes selection that manages efficiently the active nodes using a Tabu Node Selection coupled with minimum spanning tree routing protocol (TNS). Minimizing the total energy consumption in WSN, is not enough alone, since some nodes drain their energy faster than others, and may cause network failure. To balance the energy consumption, our strategy is to identify nodes with high-energy depletion and balance data routing on their neighbours. This approach performs nodes energy balancing, by creating lists of Tabu nodes (periodically inactive nodes). Such a scheme will prevent the most used nodes, such as nodes close to the base station to see their energy drain. The nodes in the Tabu lists will dynamically be active according to the energy level of nodes surrounding them. Our new dynamic heuristic has proven to outperform other nodes management approach which does not use Tabu search. The experiments show that Tabu list combined with Minimum Spanning Tree routing protocol extend drastically the network lifetime by balancing optimally the nodes energy.

Keywords:

• WSNs
• tabu heuristic
• residual energy
• minimum spanning tree
• network lifetime

PUBLIC INTEREST STATEMENT

Wireless sensor networks (WSNs) are a recent technology deployed for several applications: environment monitoring, security, weather observations and more. A WSN consists of a set of sensors with a wireless communication capability and limited energy capacity. They are deployed in different areas to guarantee maximum sensing coverage. Due to their limited energy, one of the main challenges is how to increase the network lifetime. The lifetime of the WSN is defined as the time period until the first node runs out of battery. Our strategy is to identify nodes with high-energy depletion and balance data routing on their neighbours. In this approach, we create lists of tabu nodes (temporarily inactive nodes). Such a scheme will prevent the most used nodes to see their energy drain. The nodes will dynamically be active according to the energy level of surrounding nodes. The experiments show that tabu list combined with Minimum Spanning Tree routing protocol extend drastically the network lifetime.

1. Introduction

Wireless sensor networks (WSNs) are a recent technology deployed for several applications: environment monitoring, security, weather/climate observations … etc. A WSN consists of a set of sensors, named nodes with a wireless communication capability and limited energy capacity. The Wireless Sensor Networks may consist of hundreds of sensors/nodes. The nodes have the sensing capability and wireless communication ability to send data to other sensors or base station/sink. The base station or sink is a special sensor, which has more power capacity and high computation capability. Each sensor has a predefined task and small power capacity. The sensors are deployed in different areas, so as to cover the intended targets and guarantee maximum sensing coverage. All sensors can route data or collect it from their environment. There are several real-life applications for WSNs, such as fire detection, military surveillance, monitoring, and physiological monitoring of patient, wild fires surveillance, grid monitoring, water distribution monitoring and much more (Jing, 2017; Mahlous & Tounsi, 2017; Le Nguyen et al., 2019; Sharma & Ghose, 2010; Thakkar & Kotecha, 2014). Due to their limited capacity, one of the main challenges to WSNs is how to increase the network lifetime by performing data routing that consume less energy. Different issues related to WSNs are: nodes deployment, data routing, and optimizing energy consumption, ensuring QoS with Node/Link Heterogeneity, increase scalability, maximizing the network coverage and improving the data aggregation. In fact, due to the sensors limited energy capacity, the development of WSNs faces numerous constraints: thus reiterating the puzzles of how to increase network lifetime with limited capacity? How to effectively route data? How to guarantee maximum network coverage? The lifetime of the sensors network is defined as the time period until the first node runs out of battery (minimum individual node lifetime), as in (Boukerche & Sun, 2018; Yang et al., 2010), or a certain percentage of the network nodes go flat (nth minimum individual node lifetime), as in (Blough & Santi, 2002). Increasing the network lifetime is a huge challenge. Many approaches have been applied in this regard which use Tabu search formalism. In fact, Jaffres-Runser & Gorce (2009) provide a detailed formalism to use Tabu search for solving multi-objective optimization problems in WLAN. The authors use Tabu search to find multiple paths in routing under several objectives. In this research, we have proposed Tabu-based approach for nodes selection coupled with minimum spanning tree routing algorithm; it is a dynamic heuristic which maintain a tabu list of nodes to increase residual energy and network lifetime. The proposed model is used to create Tabu lists, a kind of rest lists where the nodes in these lists will be idle for certain rounds. TNS consists of a fine-tuning nodes based on their energy consumption. The Tabu heuristic along with minimum spanning tree has been used to solve different problems (Öncan et al., 2008). In (Katagiri et al., 2008) the authors suggested the use of tabu search coupled with minimum spanning tree algorithms to solve the nonlinear minimum spanning tree problems. (Kasperski et al., 2012) an algorithm based on tabu search with have been used to solve the NP-hard problem of minmax regret spanning tree, where the edges costs are not precisely known. The hybrid proposed algorithms provided optimal results for smaller instances and good solutions for large instances.

The Tabu nodes selection TNS is then coupled with a minimum spanning tree routing protocol to optimize the routing in the WSNs. One of the main components of Tabu search is its use of adaptive list, which creates a more dynamic list that improves the ability to select best nodes for routing. The Tabu search is a metaheuristic designed by Glover (Glover, 1989) for optimization problems to escape from local minimum. It has been shown in different applications that Tabu search and Tabu concept provides a huge benefit in solving real-life problems.

2. Related works

The wireless sensor network–related problems are: saving residual energy, increasing network lifetime, achieving maximum throughput with high quality of service. Some inherent problems are also related to WSNs, such as nodes and base station deployment and finding the cluster heads. In (Sharma & Ghose, 2010), the authors addressed the problem of clustering using a hyper-graph partitioning and the Tabu search approach to perform better clustering. The Tabu heuristic solves clustering problems where the number of clusters and cluster heads are unknown beforehand. In the latter work, the authors suggested a variant of Tabu search consisting of different types of moves to reallocate nodes to clusters, selecting cluster heads, and removing existing clusters. Similarly, in (Orojloo & Haghighat, 2016; Pierre & Rhazi, 2009), the authors used a Tabu search-based routing algorithm to find the optimal path from a source to a destination in wireless sensor networks. The approach had improved the design of nodes clusters and network connectivity. In fact, they used the Tabu search method for routing in WSNs to find the near optimal path. In (Ang, 2012) the authors proposed a routing optimization algorithm to determine an optimal path from a source to a destination in mobile ad-hoc networks. The proposed algorithm is designed by using a Tabu search, where two moves are used to find the neighbourhood nodes to determine an optimal path with minimal cost. Authors in (Goss et al., 1975) presented a routing algorithm to improve network lifetime and reliability. The proposed algorithm combines a Tabu concept along with a multi-criteria algorithm. The selection of nodes for routing is based on multi-criteria model. Nodes are disallowed for the path if they cannot satisfy the multi-criteria model. In (Praveen et al., 2018) the authors dealt with QoS multicast routing problem. An effective Tabu-based algorithm has been proposed to solve the bandwidth-delay constrained least-cost multicast routing problem using a dynamic Tabu list model. In (Lokesh & Bhajantri1, 2014) the authors proposed a cluster-based optimization of routing by employing a Bayesian network (BN) combined with Tabu search approach. They optimized the routing through cluster head nodes by using Tabu search heuristic. On the other hand, in (Aitsaadi et al., 2009) the authors addressed the deployment issue in WSN. They modelled the WSN deployment problem as a multi-objectives optimization problem, which seeks to reduce the gap between the generated events detection probabilities and the required thresholds while minimizing the number of deployed sensors using a Tabu Search heuristic. In (Mohammadi1 & Noghabi, 2016) the authors suggested a simulated annealing-based routing algorithm to determine an optimal path from the source to a destination in wireless sensor networks while using a Tabu search to create different neighbour paths.

In (Kaur1 & Gangwar, 2015) the authors used a Tabu approach in order to aggregate data and improve the sensing capabilities of the active nodes. Similarly, in (Qiu et al., 2018) a Tabu search routing protocol was suggested to route the data from the sensor to the base station with notable results. In (Jang, 2015) the authors suggested a Tabu search algorithm to deploy the sensor nodes in order to maximize sensing coverage in wireless sensor networks. The authors tackled the computation problem in highly dense WSN using a Tabu search with efficient neighbourhood generation. A clustered architecture for energy-efficient routing Tabu Swarm Optimization was proposed in (Qingjian et al., 2017). The results showed an increase in efficiency in minimizing the energy consumption.

While in (AbuBakr & Lilien, 2014) the nodes are clustered using a Tabu search approach to collect data and reduce energy consumption, using a clustering detection model. The Tabu search consists of defining three types of moves that allow reallocating nodes to clusters. The routing algorithms provide a set of step-by-step operations used to direct data traffic efficiently. When a packet of data leaves its source, there are many different paths it can take to its destination. The routing algorithm is used to determine mathematically the best path to take. In (Dilo et al., 2011)(Mahlous & Tounsi, 2017) the authors showed that the use of shortest path tree in routing is the most common technique used for routing within WSNs. Hence, they exhibited the issues with shortest path tree, which is the unbalanced load between the sensors and the disparity in the energy used by such nodes. In (Liaqat et al., 2016), the authors suggested a distance-based and low-energy adaptive clustering protocol to enhance network performance in WSNs. In (Kang et al., 2018), the authors designed an E-LEACH, which forms clustering and employs the distributed algorithm to pass the packet. The drawback in this work, is extra tuning of several parameters are needed to choose the best cluster head. Kaur & Mahajan (2018) suggested to use ACO-PSO, a hybrid heuristics algorithm to provide efficient data transmission. This work increases the energy consumption of the network. While in (Liu et al., 2017), the researchers suggested an algorithm to find the optimal path to transmit the data packet. Whereas the distance between the source and destination node is not considered which increases latency. In (Kozłowski & Sosnowski, 2019) the EEDC algorithm provides a cycling transmitting and receiving process. The suggested process augments the delay of packet data, which inclines to loss data. In (Sinde et al., 2020) the authors used reinforcement learning to an Energy-Efficient Scheduling using the Deep Reinforcement Learning named E2S-DRL. The suggested algorithm is meant to reduce network delay and increase network lifetime. The algorithm uses particle swam optimization to reduce the energy consumption in one of its phase.

In our research, we used the minimum spanning tree algorithm for routing. In fact, we used PRIM’s algorithm to route the data combined with our Tabu nodes selection approach. We employed a minimum spanning tree (MST) of an edge weighted graph which is a spanning tree whose weight (i.e. the total sum of the weights of its edges) is no larger than the weight of any other spanning tree.

3. Proposed approach

In our approach, we will use the PRIM’s algorithm for routing data. Thus, PRIM’s algorithm (Figure 2) provides the minimum spanning tree of a graph. Assume an undirected connected graph. A spanning tree of that graph would be a subgraph that connects all the vertices of that tree. A single graph can have many spanning trees. If some weights (energy in our case) are assigned to each edge, then the MST is the spanning tree with weight less than any other spanning tree of that graph. A graph is shown in Figure 1, weights are assigned to each of its branches. As can be seen, the highlighted tree is known as the spanning tree. Many other spanning trees can also be built by connecting the vertices of the given figure in different ways. The routing algorithm in our approach can be described as follows: We consider a weighted connected graph G with n vertices. Prim’s algorithm finds a minimum spanning tree of G.

Figure 1. Weighted graph and its minimum spanning tree

Figure 2. PRIM’s algorithm

In our approach, the targets are covered by at least 1 sensor. We always search for nodes which are the most used in one routing, for these are the nodes that drain the most quickly. Therefore, we put these nodes in a Tabu list which represent inactive nodes for a certain period of time. In fact, we build a set of lists that represent the nodes covering a target. When a certain node reaches a certain level of energy, it will be added to the Tabu list. Such node sensor remains on the Tabu list until all the nodes covering the same target reach their energy level. The node will be released from the Tabu list and then, we re-compute the selected nodes that should be put in such Tabu list. In the above approach, we are sure to avoid the nodes that die quickly because once their energy levels have decreased more than others, they will be put “on hold” within the Tabu list for the coming rounds of routing. Because some nodes will “disconnect” from the network, we consider different types of nodes: nodes connected to the base station and nodes that are not connected directly to base station as shown in Figure 3.

Figure 3. Nodes coverage in WSN

The base station is represented by the large dot. Every circle represents the coverage of each sensor. Sensors S1,S2,S3 do not “cover” the base station, while nodes S4, S5 do. This segmentation is important to consider differentiation in the algorithm. We cannot put a node in a Tabu list if it is the only one which is connected to the base station; thus, the algorithm will prevent the network from being disconnected. Accordingly, for each target t_i, a set of nodes lti contains all nodes covering the target t_i. Hence, for each target, we have a Tabu list names: Tabui. As a result, we will have a list of Tabu lists, which represent nodes that could be inactive for a certain period of time according to their energy level.

The routing will occur only on the active nodes. In this scheme, the nodes will not get drained fast as we control and balance the routing on all nodes in the network. A pseudo-code of the proposed algorithm is shown Figure 4 below.

Figure 4. Tabu Node Selection Algorithm (TNS)

We consider different levels of energy in which the energy value of the node varies. For instance, if a node’s energy level loses 50% from its initial value, the node is added to the Tabu list corresponding to its target. Once the entire set of nodes in the same target node list reaches the same energy level a 50% energy loss, at this moment, all nodes will be active and removed from the respective Tabu list. In this manner, we guarantee that the nodes will have their energy level decreased in a balanced way.

4. Experiments and discussion

To assess our model, we used a variety of sizes of region areas ranging from 100 × 100 to 400 × 400 m with different node densities in which N nodes are uniformly placed as shown in Figure 5. The number of nodes in our experiments varies from 100 to 400, and the number of rounds varies from 5000 to 20,000. The targets are randomly covered by at least one node. We have tested our algorithm on several instances by varying the network density and the size of the network. A comparison has been made without using the Tabu Node Selection. Furthermore, we compared the performance of our proposed approach with the E2S-DL algorithm (Sinde et al., 2020). The E2S-DL uses cyclic phases to reduce network delay and increase network lifetime using a clustering and routing phases. The algorithm uses a meta-heuristics to optimize the clustering and transmission (particle swarm optimization and Ant-Colony).

Figure 5. Nodes positions with 100 × 100 grid

The metrics used for evaluating the performance of our approach are: network size, network lifetime, the number of dead nodes and the average residual energy. The tests were performed on 17 instances families, represented as Ix and coupled with the different WSN areas, such as 100x100, 200 × 200 and 400 × 400. The network density, denoted by Nd, represents different small scale and dense WSNs as shown in Table 1.

Table 1. WNS benchmarks

#	N	Area	Nd
I1	100	100x100	0.01
I2	100	200x200	0.0025
I3	100	300x300	0.0011
I4	100	400x400	0.00625
I5	200	100x100	0.02
I6	200	200x200	0.005
I7	200	300x300	0.0024
I8	200	400x400	0.00125
I9	300	100x100	0.03
I10	300	200x200	0.075
I11	300	300x300	0.0033
I12	300	400x400	0.0018
I13	400	100x100	0.02
I14	400	200x200	0.01
I15	400	300x300	0.004
I16	400	400x400	0.025
I17	100	1000x1000	0.0001

We simulated our proposed model using a random sensor nodes distribution. The base station is placed at the centre or close to the centre of the network field. The corresponding simulation parameters are shown in Table 2.

Table 2. Simulation parameters

Parameters	Value
Initial energy E0	200 J
Transmitting and receiving energy Eelec	5 nJ/bit
Amplification energy for short distance Ef	10 Pj/bit/m^2
Amplification energy for long distance Eamp	0.013 pJ/bit/m^4
Packet size	200 bits
Operating frequency	2.4 GHz
Transmit power	32 mW
Reference distance	3 m
Path loss exponent	4
SNR	2 dB

The computations were made to evaluate our dynamic heuristic. To assess the network lifetime, residual energy as well as throughput, the Tabu-based model performs fine-tuning to balance energy among nodes and puts some nodes in the idle state based on their energy level. Figures 3–5 depict the WSN behaviour for instance, I1 with 5000 rounds.

In our experiments, we wanted to explore the Tabu list content for two cases:

i.Base station nodes BS-list(): only consider nodes that are connected to the base station which can be added to the Tabu list, while all the remaining nodes are not.

ii.All network nodes Network-list(): all network nodes that belong to the Tabu list.

iii.No Tabu list: No-list(): only MST() algorithm to route and manage the nodes.

BS-list(): We created Tabu lists only for nodes which cover the base station. We performed energy balancing among them using the TNS algorithm. All other nodes are not added to the Tabu list and their management is done by the MST routing algorithm.

Network-list(): All nodes can belong to Tabu lists corresponding to their target sets. Hence, it is a generalization of the previous model (BS-list())

No-list(): We use only an MST routing algorithm without considering any Tabu list. The nodes management is performed using MST routing algorithm.

We wanted first to investigate the effect on preventing only the nodes close to the base station from dying first. As they are the most solicited during the routing, and get drained the most quickly. While the second option was to check when all nodes are relegated to the Tabu list and then preventing other nodes in the network to get drained, because they can be in the unique routing path. The experiments were made for all three situations represented by: BS-list() for option i) and Network-list () for option ii) and No-list() for option iii). In the TNS algorithm, the Tabu list parameters are dynamically updated according to the energy level of the nodes. Hence, we reason that, when a node is depleted a certain level of energy, it “drains” more quickly than its neighbours; hence, this node is a good candidate of Tabu list. Thus, such a node becomes inactive. The energy levels of nodes vary from 10% to 50%. We want to determine which energy level is the best to put nodes into a Tabu list and perform the energy balancing. In our experiments, the energy level of each node is checked for reaching a descending numbers of levels—for example, 70%, 60%, 50%… Once a node reach that level, then it is added to the Tabu list according to the TNS algorithm. Figures shown below depict the results of our algorithm on the three variants: BS-list(), Network-list() and No-list() for different energy level. Figures 6–8 represent the experiments of TNS when the energy level of a node reaches 10%, it is added to the Tabu list. We can notice that the residual energy is higher for the Network-list() variant of our algorithm. This tells us that it is more efficient to add nodes to the Tabu list when their energy reach 10%, than considering adding only base station’s neighbour nodes. This confirms that the network topology makes the BS-list() a sub-case of Network-list().

Figure 6. Residual energy for energy level 10%

Figure 7. Throughput for energy level 10%

Figure 8. Network lifetime for energy level 10%

Similarly for the throughput, we notice that for a level of 10%, all the three variants provide similar level for higher rounds. For the network lifetime, we notice that the Network-list() variant outperforms other algorithms, more than a double against BS-list() and much more if it is used without any node management, relying only on the MST routing algorithm. This can be justified by the fact, that all nodes can belong to the Tabu list, which avoid the energy depletion. Most of the nodes will rest for a certain number of rounds to avoid to be drained.

Figures 9–11 represent the experiments of TNS when the energy level to be reached by nodes is 30% in order to be added to the Tabu list. The throughput for the Network-list() lay in between the others variants. In fact for the BS-list() variant, the nodes disconnect more quickly than other nodes which will affect the throughput of the network. While in the Network-list(), it seems that 30% level energy allow the nodes to enter quickly into the Tabu list and may affect the throughput. More investigations are done for higher energy levels to assess this finding. For the network lifetime, we notice that the Network-list() variant outperforms other algorithms as for 10%. This confirms our perception that the residual energy will increase since we perform a pseudo-optimal nodes selection for energy balancing.

Figure 9. Throughput for energy level 30%

Figure 10. Network lifetime for energy level 30%

Figure 11. Residual energy for energy level 30%

Likewise, the residual energy is higher for the Network-list() variant of our algorithm. This tells us that it is more efficient to add nodes to the Tabu list when their energy reach 30%, than considering adding only base station’s neighbour nodes. We observe too, that for energy level 40% and 50%, the residual energy is much higher compared to the other algorithms (Figures 12 and 15) for the Network-list() algorithm. Similarly for network lifetime (Figures 13, 14 and 17), we noticed that the throughput decreased with a larger energy level values. This can be justified by the fact that the nodes will be added to the Tabu list quickly, when their energy reaches these levels. More nodes are placed into the Tabu lists, which prevent the increase of the throughput. One of the findings would be to set the energy level not more than 30% in the TNS algorithm.

Figure 12. Residual for energy level 40%

Figure 13. Throughput for energy level 40%

Figure 14. Network lifetime for energy level 40%

Figure 15. Residual energy for energy level 50%

Figure 16. Throughput for energy level 50%

Figure 17. Network lifetime for energy level 50%

To find the best energy level which represents the threshold for nodes to belong to the Tabu list, we have run experiments with continuous values of energy levels ranging from 1 to 50%. As shown in Figures 16 and 17, the best value appears to be 30%. This validates our previous findings on the range of the energy level. In other parts, the Table 3 presents a comparison with the (E2S-DL algorithm [35)] on a low-density WSN network. As presented, our dynamic heuristic performs well on low-density network, where the residual energy is 7% higher than nodes scheduling algorithm using the deep reinforcement learning. A raison is that our algorithm focuses on energy consummation in routing, while the E2S-DL algorithm focuses on reducing the delay beside the network lifetime. It appears clearly that the Tabu node selection algorithm provides a tremendous improvement in terms of residual energy and network lifetime. The energy balancing among the sensors using the Tabu approach have confirmed the novelty of our approach coupled with the minimum spanning tree algorithm.

Table 3. Comparison with E2S-DL (Sinde et al., 2020)

Energy Level	parameter	Tabu-MST Algorithm	E2S-DRL
50%	Througput	88%	92%
	Residual Energy	37%	30%
	Network lifetime	6345 rounds	6450 rounds

5. Conclusion

In the Wireless Sensors Networks, the management of nodes energy is crucial to improve the network lifetime. In fact, having efficient routing protocol coupled with a node management strategy will impact positively the network lifetime. In our approach, we have suggested a dynamic heuristic based on Tabu mechanism in order to perform energy balancing among the nodes. The nodes are made inactive if their energy reaches a certain level. This level ensures that the node will not get its energy drained until its entire neighbour nodes reach the same energy level. Therefore, the network lifetime will increase since we prevent the nodes with high data transit to die quickly. The experiments showed that Tabu-based approach coupled with Minimum Spanning Tree routing increased significantly network lifetime by an average of 45%. These confirm our intuition that performing energy balancing at the level of nodes will affect positively the network lifetime and increase residual energy.

Acknowledgements

The researcher thanks Prince Sultan University for supporting this research project through the Advanced Operations and Analytics Research Group.

Additional information

Funding

The author received no direct funding for this research.

Notes on contributors

Mohamed Tounsi

Dr. Mohamed Tounsi is an associate professor in computer science at Prince Sultan University. He received a PhD in Artificial Intelligence in Ecole des Mines de Nantes (France) in 2002. He received a Msc in operational research from Dauphine University, Paris IX (France). His research intresets focus on algorithm design using meta-heuritics, algorithms optimization for machine learning, building efficient intelligent systems.