# A Robust Self-Organizing Tree-Based Routing Protocol for Wireless Sensor Networks

Authors: Qinbin He; Jinping Mou; Bin Lin
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

For a wireless sensor network (WSN), routing protocols not only affect the reliability and real-time data transmission but also affect the energy consumption of communication and the survival time of the entire network. In this paper, a routing protocol is proposed that combines virtual potential energy with local density of nodes and sleep-wake-up mechanism. The proposed routing protocol is self-organizing and robust. The routing protocol allows nodes to dynamically join or leave the network and enables nodes to automatically transmit information along the shortest path to reach a corresponding sink. The protocol can be applied in scenarios of single sink, multiple sinks, and three-dimensional WSNs. At the same time, the protocol takes a sleep-wake-up mechanism into account, makes a significant decrease in total network traffic, and achieves energy-saving as much as possible. Examples are given in detail to illustrate the effectiveness of the proposed routing protocol.


---

## Body

## 1. Introduction

Wireless sensor network (WSN) routing protocol is responsible for transmitting data from the source node to the destination node. Major research of routing protocol is to find an optimal path from the source node to destination node and how to send the data along the optimal path correctly. Routing protocols affect not only the reliability and real-time data transmission but also the energy consumption of communications and the survival time of the entire network. The research of routing protocol of the wireless sensor network is focused on how to reduce the energy consumption of nodes and prolong the survival time of the network.There are typical flat routing protocols: Sequential Assignment Routing (SAR) [1], Sensor Protocol for Information Negotiation (SPIN) [2], and Directed Diffusion (DD) [3]. Flat routing protocols have some shortages such as without management nodes, the lack of optimized resource management, and self-organized complexity of nodes to work together. In addition, its response to dynamic changes of the network is too slow and requires the maintenance of large routing tables. It is inappropriate for large-scale wireless sensor networks.In order to prolong the survival time of the nodes and improve routing performance, some researchers put forward the idea of hierarchical routing protocols. Hierarchical routing protocols mainly can be divided into two categories: cluster-based routing protocols and tree-based routing protocols.There are typical cluster-based routing protocols: Low-Energy Adaptive Clustering Hierarchy routing (LEACH) [4], Threshold-Sensitive Energy-Efficient Sensor Network Protocol (TEEN) [5], and Power Efficient Gathering in Sensor Information Systems (PEGASIS) [6].Tree-based routing protocol constructs a tree structure with a sink as root. Generally speaking, tree-based routing protocols have a stronger self-organized and more effective energy-saving than cluster-based routing protocol. Literature of investigated tree-based routing protocols include [7, 8].In addition, it is necessary to discuss the multisink or mobile sink cases in large-scale WSNs. The main reason is that, for example, sinks often become targets of attack in the military. When the sink is attacked in a single-sink WSN, the whole network will be paralyzed. However, in the multisink or mobile sink network, it will greatly reduce the possibility of network paralysis. In addition, if the network which allows multiple sinks exists, the information transmission path will be greatly reduced; thus, the whole network will be more energy efficient. Some of the literature also discussed the multisink or mobile sink cases in WSNs, such as [9–13]. Similarly, to avoid attacks, it is necessary to provide a certain level of protection to each sensor. A network self-protection algorithm is proposed for wireless sensor networks [17]. In order to save energy and extend the lifetime of the network, various other algorithms have also been proposed, such as the Propagation-Based Self-Adaptive Clustering Method [15] and PSO-based energy efficient coverage control algorithm [16].Our main contributions in this paper are as follows: Firstly, we introduce the concept of virtual potential energy which is proposed by considering the residual energy and the local density of sensor nodes. Secondly, we give a sleep-wake-up mechanism. Lastly, we proposed a routing protocol that combines virtual potential energy and sleep-wake-up mechanism. The proposed protocol is self-organized, robust, and makes nodes to transmit information along the shortest path to reach the corresponding sink, thus saving energy and maintaining the survival time as long as possible.The rest of the paper is organized as follows. In Section2, we discuss the related concepts and issues for WSNs. In Section 3, we give the Robust Self-organizing Tree-based Routing Protocol (RSTR) for WSNs. In Section 4, we give experimental results and analysis. In Section 5, we give the conclusions about RSTR and some thoughts about future works.


## 2. Discussion of Relevant Concepts and Issues for WSNs

In this paper, we assume that nodes of WSNs are distributed in a corresponding region randomly, and nodes detect environment and communicate with the other nodes periodically.


### 2.1. Evaluation of Routing Protocols

Evaluation of the WSN network should be based on network connectivity as a precondition. The reason is that the information cannot be effectively transmitted when a network is broken into several isolated parts. In addition, the average residual energy of networks also cannot completely reflect whether the routing protocol is good or bad. The average residual energy network routing protocol is not lower, the better. It is not comprehensive to assess routing protocol only by using the average residual energy of the network. In order to get survival time as long as possible, we should try to make each node survive as long as possible. The reason is that the death of a node will increase the transmission path of the other nodes in the network. The key factor of WSN’s largest survival time is the consumption of energy balance in the same layer nodes. Here, we give some principles on evaluation of a routing protocol.For an identified WSN, a routing protocol should be based on the following principles:(1)
As a prerequisite, the network must remain connected.(2)
The survival time of the network should be as long as possible. Correspondingly, the communication rounds of network should be as large as possible.(3)
Before the network is not connected, the average residual energy of the network should be as large as possible.(4)
To transmit the same amount of information, the energy consumption should be as little as possible.


### 2.2. Energy Model

Wireless communication energy consumption is the main energy consumption part of the WSN. We adopt the simple energy model given in [4, 14]. Energy consumption consists of two parts: a transmitter consumption and power amplification consumption. The energy consumption for sending l−bit data with distance d is ETxl,d. The energy model can be expressed as follows (where ETx_elec is the circuitry power consumption and εamp is the coefficient of power amplification consumption):(1)ETxl,d=ETx_elecl+ETx_ampl,d=lEelec+lεampd2.The energy consumption for receivingl−bit data is ERxl, and we represent it as follows:(2)ERxl=ERx_elecl=lEelec.Energy consumption ofl−bit data fusion is EDAl, shown as follows (where EDA is the unit bit energy consumption of data fusion):(3)EDAl=lEDA.Values of specific parameters are shown as follows (all examples of this paper are adopted those parameters):(4)ETx_elec=ERx_elec=Eelec=50nJbit,εamp=10pJ/bitm2,EDA=5nJbit.


## 2.1. Evaluation of Routing Protocols

Evaluation of the WSN network should be based on network connectivity as a precondition. The reason is that the information cannot be effectively transmitted when a network is broken into several isolated parts. In addition, the average residual energy of networks also cannot completely reflect whether the routing protocol is good or bad. The average residual energy network routing protocol is not lower, the better. It is not comprehensive to assess routing protocol only by using the average residual energy of the network. In order to get survival time as long as possible, we should try to make each node survive as long as possible. The reason is that the death of a node will increase the transmission path of the other nodes in the network. The key factor of WSN’s largest survival time is the consumption of energy balance in the same layer nodes. Here, we give some principles on evaluation of a routing protocol.For an identified WSN, a routing protocol should be based on the following principles:(1)
As a prerequisite, the network must remain connected.(2)
The survival time of the network should be as long as possible. Correspondingly, the communication rounds of network should be as large as possible.(3)
Before the network is not connected, the average residual energy of the network should be as large as possible.(4)
To transmit the same amount of information, the energy consumption should be as little as possible.


## 2.2. Energy Model

Wireless communication energy consumption is the main energy consumption part of the WSN. We adopt the simple energy model given in [4, 14]. Energy consumption consists of two parts: a transmitter consumption and power amplification consumption. The energy consumption for sending l−bit data with distance d is ETxl,d. The energy model can be expressed as follows (where ETx_elec is the circuitry power consumption and εamp is the coefficient of power amplification consumption):(1)ETxl,d=ETx_elecl+ETx_ampl,d=lEelec+lεampd2.The energy consumption for receivingl−bit data is ERxl, and we represent it as follows:(2)ERxl=ERx_elecl=lEelec.Energy consumption ofl−bit data fusion is EDAl, shown as follows (where EDA is the unit bit energy consumption of data fusion):(3)EDAl=lEDA.Values of specific parameters are shown as follows (all examples of this paper are adopted those parameters):(4)ETx_elec=ERx_elec=Eelec=50nJbit,εamp=10pJ/bitm2,EDA=5nJbit.


## 3. Robust Self-Organizing Tree-Based Routing Protocol (RSTR)

### 3.1. The Concept of the Virtual Potential Energy

Suppose the node number of a WSN isn, and hardware ID of nodes is 0,1,2,…,n−1, respectively.Generally speaking, nodes in WSNs can be divided into two categories: In the first category, the nodes do not participate in communications or does not participate in network communications temporarily, such as failure nodes, energy depleted nodes, and sleep nodes. The other category is normal nodes which participate in communications in WSNs.Some definitions are given as follows:(i)
Definition 1: in a WSN, the node participating in communications normally is called a normal node.(ii)
Definition 2: the layer label of sinks is 0. The minimum layer label (exclusion layer label −1) of all neighbor nodes plus 1 is called the layer label of the node.(iii)
Definition 3: for a WSN, after sinks received all the data from normal nodes, a round is finished.(iv)
Definition 4: in an n-node WSN, the sum residual energy of all nodes divided byn is called the average residual energy.(v)
Definition 5: the hardware ID of the neighboring node, which the node transmits information to, is called the information-flow direction of the node.Here, we present the concept of the virtual potential energy. Here, to make the network more balanced energy consumption, comprised with the residual energy of sensor nodes and the local node density, we introduce the concept of the virtual potential energy.Denoted the virtual potential energy ofnodei by Wi,(5)Wi=Ei1+∑j∈NiNoj≠Noi+1NojNoi,Noi≠0…∗.WhereEi is the residual energy the nodei. Ni is the set of neighbor hardware ID of the nodei. If the layer label of nodei is k, we denoted by Noi=k. When Noi=0, namely, nodei is a sink node, and supposedly, its energy is not reduced in all the time. If nodei is a sink, we denote Wi=Ei.There are two reasons for the introduction of virtual potential energy. The first reason is that we should maintain nodes’ survival as far as possible. The second reason is that we should make the networks carry out self-organization and automatically determine the information-flow direction. The illustration is shown in Figure1.Figure 1
The different situations of information-flow direction (the numbers are layer label, and the numbers inside the circles are the layer label of neighbor nodes ofnodeij(j = 1, 2)). (a) The information-flow direction of node i3, when Wi1>Wi2. (b) The information-flow direction of node i3, when Wi1>Wi2.
(a)(b)Nodes inside the circle are neighbor nodes of the corresponding node. The upper layer ofnodei1,nodei2 is nodei3, as in Figures 1(a) and 1(b). The nodei1 has 3 nodes with layer label 2 and 1 node with layer label 1, and there may be several nodes whose layer label is 3, as in Figure 1(a).To compute the virtual potential energy of nodes, we only need to consider the neighbor node information of same layer and the lower layer.In Figure1(a), the layer label of nodei1 and nodei2 is 2. Denote Noi1=2,Noi2=2, respectively. The layer label of nodei3 is 3. We denote Noi3=3.Here, the virtual potential energy can be expressed as(6)Wi1=Ei11+∑j∈Ni1Noj≠Noi1+1NojNoi1=Ei11+2+2+2+12=4.5Ei1,Wi2=Ei21+∑j∈Ni2Noj≠Noi2+1NojNoi2=Ei21+2+2+1+12=4Ei2.In Figure1(b), the virtual potential energy can be expressed as(7)Wi1=Ei11+∑j∈Ni1Noj≠Noi1+1NojNoi1=Ei11+2+2+1+1+12=4.5Ei1,Wi2=Ei21+∑j∈Ni2Noj≠Noi2+1NojNoi2=Ei21+2+2+1+12=4Ei2.In Figure1(a), we suppose the residual energy of nodei1 and nodei2 to meet Ei1/Ei2>4/4.5, i.e., Wi1>Wi2; then, virtual potential energy Wi1=4.5Ei1>Wi2=4Ei2. Therefore, the information-flow direction of nodei3 points to the nodei1.If the residual energy ofnodei1 and nodei2 to meet Ei1/Ei2>4/4.5, then the information-flow direction of nodei3 points to the nodei2.Similar to the abovementioned analysis, we can get the corresponding results from Figure1(b).


### 3.2. Robust Self-Organizing Tree-Based Routing Protocol

The routing protocol presented here is based on the shortest distance and energy-saving mechanism. This protocol does not require flooding. Bonding the virtual potential energy of the node and information-flow direction, the protocol makes each node to transmit its information along the shortest path to a corresponding sink.Robust Self-organizing Tree-based Routing Protocol:(1)
initialize layer label of each node by −1, and the layer label of a sink is defined as the 0-layer label.(2)
Each node is to create or update neighbor node information, save a neighbor node hardware ID, layer label, and residual energy, calculate and record the corresponding communication power with neighbor nodes, and find the smallest layer label in its neighbor nodes (exclusion layer label −1).(3)
Each node denotes its own layer label by the smallest level label (achieved by (2)) plus 1 and calculates its own virtual potential energy.(4)
Each node finds the neighbor node with the maximum virtual potential energy in its next layer and records the node’s residual energy, hardware ID.(5)
Each node takes the current record of hardware ID with the previous record for comparison. If it is the same as the current node hardware ID, we then compare the residual energy difference (energy difference of the current and the saved residual energy of its contacted node).(6)
If the residual energy difference of its contacted node is less than a given percentage of the initial energy (in this paper, we take 1% of the original maximum energy of its contacted node), we then keep the last information-flow direction and return to (5).(7)
Otherwise, return to (2).(8)
In case a new node joins or a node sleeps or dies, we return to (2).After steps (1)–(4), the network has been layered. In some very short intervals of communications, the layer label of nodes may not be equal to the corresponding minimum number of hops to the sink, but soon will automatically adjust to the correct value. First, the wireless sensor network performs layered processing by (1)–(4) of RSTR protocol. After layering, the information of any node can only be transmitted to its upper neighbor nodes. This ensures that the information can be transmitted to the sink node in the shortest distance. In steps 5 and 6, by comparing the residual energy difference of nodes, the purpose is to balance the energy consumption of the network as much as possible, so as to extend the survival time of the network as much as possible.RSTR is an algorithm based on the shortest path and energy saving. RSTR protocol has good dynamic network scalability and robustness. This communication mechanism is more reliable and simple. When a new node joins the network, firstly, it determines its own neighbor nodes and adjusts the transmission power to determine between neighbor nodes and, then, records the transmitting power with the corresponding nodes. In addition, the neighbor nodes also updated information of their own.It is easy to obtain the following two properties.Property 1: according to RSTR protocol, assuming that the largest layer label isk, each node to exchange information with the neighbor nodes does not exceed k times, and then, the layer label of all nodes can be achieved.Property 2: according to RSTR protocol, the information of nodes is transmitted along the shortest path to reach a corresponding sink. Namely, the node-to-sink hop is minimal, and its value will be the layer label of nodes.RSTR protocol does not need calculate the network layer label firstly, but calculates network layer label and information-flow direction simultaneously. The calculation is very quick.


### 3.3. Sleep-Wake-Up Mechanism of RSTR

In a large-scale WSN network, there is a large number of sleep nodes. At the same time, the network also needs to constantly add new nodes to maintain network operation. Especially, for the node near a sink, its energy consumption is very fast. So, the sleep-wake-up mechanism is very important, and it is directly related to the network of energy-saving and network lifetime.Here, we introduce the sleep-wake-up mechanism for RSTR as follows:The sleep-wake-up mechanism of RSTR:(1)
When the node finds that there is no node that can be contacted by itself around, it will sleep.(2)
When the node finds that there are two normal nodes ini% of the maximum communication radius by itself (in this paper, we take i=5), it will sleep. When the sleep node finds that the number of normal nodes is less than j (in this paper, we take j=3) by itself around, it will wake up.(3)
Before the death of a node (for example, when its residual energy is less than 5% of its initial energy), it must wake up a neighbor sleep node and has the right to wake-up only one neighbor sleep node in its lifetime. Furthermore, the awakened-up node cannot sleep again in its remaining lifetime.The sleep-wake-up mechanism (3) is also called residual-energy-wake-up mechanism (REWUM). Here, we assume that sleep nodes can be awakened up by other nodes. If a node has to awaken a sleeping node, firstly, it sends a wake-up command. When the sleep node receives a wake-up command within a certain time interval, it also opens a communication module and sends a confirmation message which contains its own ID. If sleep node receives the reconfirmation message, the wake-up is success; otherwise, it continues to sleep. This mechanism can ensure that the normal node can wake up only one sleep node. When a node cannot be woken up due to a hardware failure, it is actually equivalent to the fact that there is no such node in the wireless sensor network or the node is dead.The routing protocol is robust. When a new node is added, the node and its neighbor nodes will automatically adjust their layer labels and information-flow directions. The whole network nodes will automatically calculate their layer labels, the virtual potential energy, and information-flow directions, and nodes automatically form a network without flooding sent by the sink.


### 3.4. Interpretation for the RSTR

The process of calculation of the network layer label and information-flow direction by RSTR protocol for the 20-node network is shown as follows.The original network connection of a 20-node WSN is shown in Figure2. Here, the numbers denote the ID of nodes, and node0 is a sink. At the beginning, the virtual potential energy, layer label, and information-flow direction of nodes are as shown in Figure 3. The numbers (outside the circles) denote virtual potential energy of nodes, and numbers (inside the circles) denote the layer label of nodes. After some time, the virtual potential energy, layer label, and information-flow direction of nodes are shown in Figure 4. The thick arrows are the changes of information-flow directions contrasting with Figure 3. Also, after some time, the virtual potential energy, layer label, and information-flow direction of nodes are as shown in Figure 5.Figure 2
The original network.Figure 3
The beginning virtual potential energy, layer label, and information-flow direction of nodes.Figure 4
After some time, the virtual potential energy, the layer label, and information-flow direction of nodes.Figure 5
After some time, the virtual potential energy, the layer label, and information-flow direction of nodes.To evaluate the performance of RSTR protocol, simulation is compiled by MS VC++. We try to visually dynamic and real-time reflect the energy changes, network connectivity, clustering, and hierarchical situation of a large-scale WSN network. In order to simplify calculations, here, we do not consider the parameters of delivery ratio and the latency. The layer label of 0-energy nodes or sleep nodes or just been initialized nodes is denoted by −1 in figures. The bars on the left side of numbers are the energy bars of nodes. When the nodes slowly consume energy, the energy bars will gradually change from red to yellow. The numbers denote the current layer labels of nodes (or the node ID in the original WSNs), and the lines denote the information-flow directions. From these signs, we can easily know the current general information of networks.


## 3.1. The Concept of the Virtual Potential Energy

Suppose the node number of a WSN isn, and hardware ID of nodes is 0,1,2,…,n−1, respectively.Generally speaking, nodes in WSNs can be divided into two categories: In the first category, the nodes do not participate in communications or does not participate in network communications temporarily, such as failure nodes, energy depleted nodes, and sleep nodes. The other category is normal nodes which participate in communications in WSNs.Some definitions are given as follows:(i)
Definition 1: in a WSN, the node participating in communications normally is called a normal node.(ii)
Definition 2: the layer label of sinks is 0. The minimum layer label (exclusion layer label −1) of all neighbor nodes plus 1 is called the layer label of the node.(iii)
Definition 3: for a WSN, after sinks received all the data from normal nodes, a round is finished.(iv)
Definition 4: in an n-node WSN, the sum residual energy of all nodes divided byn is called the average residual energy.(v)
Definition 5: the hardware ID of the neighboring node, which the node transmits information to, is called the information-flow direction of the node.Here, we present the concept of the virtual potential energy. Here, to make the network more balanced energy consumption, comprised with the residual energy of sensor nodes and the local node density, we introduce the concept of the virtual potential energy.Denoted the virtual potential energy ofnodei by Wi,(5)Wi=Ei1+∑j∈NiNoj≠Noi+1NojNoi,Noi≠0…∗.WhereEi is the residual energy the nodei. Ni is the set of neighbor hardware ID of the nodei. If the layer label of nodei is k, we denoted by Noi=k. When Noi=0, namely, nodei is a sink node, and supposedly, its energy is not reduced in all the time. If nodei is a sink, we denote Wi=Ei.There are two reasons for the introduction of virtual potential energy. The first reason is that we should maintain nodes’ survival as far as possible. The second reason is that we should make the networks carry out self-organization and automatically determine the information-flow direction. The illustration is shown in Figure1.Figure 1
The different situations of information-flow direction (the numbers are layer label, and the numbers inside the circles are the layer label of neighbor nodes ofnodeij(j = 1, 2)). (a) The information-flow direction of node i3, when Wi1>Wi2. (b) The information-flow direction of node i3, when Wi1>Wi2.
(a)(b)Nodes inside the circle are neighbor nodes of the corresponding node. The upper layer ofnodei1,nodei2 is nodei3, as in Figures 1(a) and 1(b). The nodei1 has 3 nodes with layer label 2 and 1 node with layer label 1, and there may be several nodes whose layer label is 3, as in Figure 1(a).To compute the virtual potential energy of nodes, we only need to consider the neighbor node information of same layer and the lower layer.In Figure1(a), the layer label of nodei1 and nodei2 is 2. Denote Noi1=2,Noi2=2, respectively. The layer label of nodei3 is 3. We denote Noi3=3.Here, the virtual potential energy can be expressed as(6)Wi1=Ei11+∑j∈Ni1Noj≠Noi1+1NojNoi1=Ei11+2+2+2+12=4.5Ei1,Wi2=Ei21+∑j∈Ni2Noj≠Noi2+1NojNoi2=Ei21+2+2+1+12=4Ei2.In Figure1(b), the virtual potential energy can be expressed as(7)Wi1=Ei11+∑j∈Ni1Noj≠Noi1+1NojNoi1=Ei11+2+2+1+1+12=4.5Ei1,Wi2=Ei21+∑j∈Ni2Noj≠Noi2+1NojNoi2=Ei21+2+2+1+12=4Ei2.In Figure1(a), we suppose the residual energy of nodei1 and nodei2 to meet Ei1/Ei2>4/4.5, i.e., Wi1>Wi2; then, virtual potential energy Wi1=4.5Ei1>Wi2=4Ei2. Therefore, the information-flow direction of nodei3 points to the nodei1.If the residual energy ofnodei1 and nodei2 to meet Ei1/Ei2>4/4.5, then the information-flow direction of nodei3 points to the nodei2.Similar to the abovementioned analysis, we can get the corresponding results from Figure1(b).


## 3.2. Robust Self-Organizing Tree-Based Routing Protocol

The routing protocol presented here is based on the shortest distance and energy-saving mechanism. This protocol does not require flooding. Bonding the virtual potential energy of the node and information-flow direction, the protocol makes each node to transmit its information along the shortest path to a corresponding sink.Robust Self-organizing Tree-based Routing Protocol:(1)
initialize layer label of each node by −1, and the layer label of a sink is defined as the 0-layer label.(2)
Each node is to create or update neighbor node information, save a neighbor node hardware ID, layer label, and residual energy, calculate and record the corresponding communication power with neighbor nodes, and find the smallest layer label in its neighbor nodes (exclusion layer label −1).(3)
Each node denotes its own layer label by the smallest level label (achieved by (2)) plus 1 and calculates its own virtual potential energy.(4)
Each node finds the neighbor node with the maximum virtual potential energy in its next layer and records the node’s residual energy, hardware ID.(5)
Each node takes the current record of hardware ID with the previous record for comparison. If it is the same as the current node hardware ID, we then compare the residual energy difference (energy difference of the current and the saved residual energy of its contacted node).(6)
If the residual energy difference of its contacted node is less than a given percentage of the initial energy (in this paper, we take 1% of the original maximum energy of its contacted node), we then keep the last information-flow direction and return to (5).(7)
Otherwise, return to (2).(8)
In case a new node joins or a node sleeps or dies, we return to (2).After steps (1)–(4), the network has been layered. In some very short intervals of communications, the layer label of nodes may not be equal to the corresponding minimum number of hops to the sink, but soon will automatically adjust to the correct value. First, the wireless sensor network performs layered processing by (1)–(4) of RSTR protocol. After layering, the information of any node can only be transmitted to its upper neighbor nodes. This ensures that the information can be transmitted to the sink node in the shortest distance. In steps 5 and 6, by comparing the residual energy difference of nodes, the purpose is to balance the energy consumption of the network as much as possible, so as to extend the survival time of the network as much as possible.RSTR is an algorithm based on the shortest path and energy saving. RSTR protocol has good dynamic network scalability and robustness. This communication mechanism is more reliable and simple. When a new node joins the network, firstly, it determines its own neighbor nodes and adjusts the transmission power to determine between neighbor nodes and, then, records the transmitting power with the corresponding nodes. In addition, the neighbor nodes also updated information of their own.It is easy to obtain the following two properties.Property 1: according to RSTR protocol, assuming that the largest layer label isk, each node to exchange information with the neighbor nodes does not exceed k times, and then, the layer label of all nodes can be achieved.Property 2: according to RSTR protocol, the information of nodes is transmitted along the shortest path to reach a corresponding sink. Namely, the node-to-sink hop is minimal, and its value will be the layer label of nodes.RSTR protocol does not need calculate the network layer label firstly, but calculates network layer label and information-flow direction simultaneously. The calculation is very quick.


## 3.3. Sleep-Wake-Up Mechanism of RSTR

In a large-scale WSN network, there is a large number of sleep nodes. At the same time, the network also needs to constantly add new nodes to maintain network operation. Especially, for the node near a sink, its energy consumption is very fast. So, the sleep-wake-up mechanism is very important, and it is directly related to the network of energy-saving and network lifetime.Here, we introduce the sleep-wake-up mechanism for RSTR as follows:The sleep-wake-up mechanism of RSTR:(1)
When the node finds that there is no node that can be contacted by itself around, it will sleep.(2)
When the node finds that there are two normal nodes ini% of the maximum communication radius by itself (in this paper, we take i=5), it will sleep. When the sleep node finds that the number of normal nodes is less than j (in this paper, we take j=3) by itself around, it will wake up.(3)
Before the death of a node (for example, when its residual energy is less than 5% of its initial energy), it must wake up a neighbor sleep node and has the right to wake-up only one neighbor sleep node in its lifetime. Furthermore, the awakened-up node cannot sleep again in its remaining lifetime.The sleep-wake-up mechanism (3) is also called residual-energy-wake-up mechanism (REWUM). Here, we assume that sleep nodes can be awakened up by other nodes. If a node has to awaken a sleeping node, firstly, it sends a wake-up command. When the sleep node receives a wake-up command within a certain time interval, it also opens a communication module and sends a confirmation message which contains its own ID. If sleep node receives the reconfirmation message, the wake-up is success; otherwise, it continues to sleep. This mechanism can ensure that the normal node can wake up only one sleep node. When a node cannot be woken up due to a hardware failure, it is actually equivalent to the fact that there is no such node in the wireless sensor network or the node is dead.The routing protocol is robust. When a new node is added, the node and its neighbor nodes will automatically adjust their layer labels and information-flow directions. The whole network nodes will automatically calculate their layer labels, the virtual potential energy, and information-flow directions, and nodes automatically form a network without flooding sent by the sink.


## 3.4. Interpretation for the RSTR

The process of calculation of the network layer label and information-flow direction by RSTR protocol for the 20-node network is shown as follows.The original network connection of a 20-node WSN is shown in Figure2. Here, the numbers denote the ID of nodes, and node0 is a sink. At the beginning, the virtual potential energy, layer label, and information-flow direction of nodes are as shown in Figure 3. The numbers (outside the circles) denote virtual potential energy of nodes, and numbers (inside the circles) denote the layer label of nodes. After some time, the virtual potential energy, layer label, and information-flow direction of nodes are shown in Figure 4. The thick arrows are the changes of information-flow directions contrasting with Figure 3. Also, after some time, the virtual potential energy, layer label, and information-flow direction of nodes are as shown in Figure 5.Figure 2
The original network.Figure 3
The beginning virtual potential energy, layer label, and information-flow direction of nodes.Figure 4
After some time, the virtual potential energy, the layer label, and information-flow direction of nodes.Figure 5
After some time, the virtual potential energy, the layer label, and information-flow direction of nodes.To evaluate the performance of RSTR protocol, simulation is compiled by MS VC++. We try to visually dynamic and real-time reflect the energy changes, network connectivity, clustering, and hierarchical situation of a large-scale WSN network. In order to simplify calculations, here, we do not consider the parameters of delivery ratio and the latency. The layer label of 0-energy nodes or sleep nodes or just been initialized nodes is denoted by −1 in figures. The bars on the left side of numbers are the energy bars of nodes. When the nodes slowly consume energy, the energy bars will gradually change from red to yellow. The numbers denote the current layer labels of nodes (or the node ID in the original WSNs), and the lines denote the information-flow directions. From these signs, we can easily know the current general information of networks.


## 4. Experimental Results and Analysis

### 4.1. The Simulation of RSTR Protocol

In this paper, all examples adopted the following mechanisms unless otherwise indicated.Nodes of WSNs are distributed in a corresponding region randomly. We supposed that sinks does not consider energy loss, all node’s initial energy2J, and each information packet 1000 bit. To simplify the simulation, we assume that all nodes periodically send data without considering the competition channel and network delay. If the network is not connected, the simulation will be terminated.Example 1.
The case of a two-dimensional WSN.
There is a simulation of a 120-node WSN in 400 × 200m2 with a maximum link radius 80 m, the network average degree D = 8, and sleep nodes accounted for 36.6667%. The calculation process of RSTR is shown in Figure 6.
When the network is disconnected, there are 4922 rounds, and the simulation is terminated. For detailed processing by RSTR, see Figures7–12.Figure 6
The calculation process of the two-dimensional WSN by RSTR.Figure 7
The connect network of the original WSN: Here, the number is node ID. The green numbers represent normal nodes, and the gray numbers represent sleep nodes.Figure 8
The program is initialized: We set the node 74 as a sink. The network is automatically organized and automatically layered. The numbers represent layer labels of the network (the nodes shown by –1 represent sleep nodes or energy of used-up nodes). The bar on the left of the number represents the node energy.Figure 9
The calculation process of the simulation: The gray line indicates that the energy of the node is used up.Figure 10
The calculation process of the simulation.Figure 11
The calculation process of the simulation.Figure 12
The network is disconnected, and the program is terminated.Example 2.
The case of a three-dimensional WSN.
There is a simulation of a 120-node WSN in 400 × 200 × 200m3, maximum link radius 100 m, the network average degree D = 13, and sleep nodes accounted for 23/120 = 19.1667%. The calculation process of RSTR is shown in Figure 13.
When the network is disconnected, there are 3568 rounds, and the simulation is terminated.Figure 13
The calculation process of the three-dimensional WSN by RSTR.Example 3.
The case of a multisink WSN.
There is a simulation of an original 4-sink 1000-node WSN in 1600 × 800m2 with a maximum link radius 100 m, the network average degree D = 8, and sleep nodes accounted for 356/1000 = 35.6%. The calculation process of RSTR is shown in Figure 14.
When the network is disconnected, there are 2526 rounds, and the simulation is terminated.
For the case of multisink routing, the node does not need to know which sink to contact with. The transmission of messages to the corresponding sink is assigned the RSTR automatically.Figure 14
The calculation process of the multi-sink WSN by RSTR.Example 4.
The case of a mobile sinks WSN.
In the following example, there is only a sink moving along designated routes in the 200-node WSN in 400 × 200m2 with a maximum link radius 50 m, the network average degree D = 7, and sleep nodes accounted for 62/200 = 31%. The calculation process of RSTR is shown in Figure 15.
When the network is disconnected, there are 3512 rounds, and the simulation is terminated. The RSTR protocol also can be applied to the mobile multisink situation.Figure 15
The calculation process of the mobile sinks WSN by RSTR.


### 4.2. Analysis and Discussion of RSTR Protocol

RSTR does not require flooding to calculate the information-flow direction and construct tree. It allows that the node maintains contact with its contacted node until reduction of certain energy of its contacted node (for example, we take 1% of the original energy of its contacted node) and then recalculates its information-flow direction. RSTR avoids energy consumption which is caused by unnecessary frequently updating of information and calculating the maximum potential energy of its neighbor nodes. The consumed energy of recalculation of the information-flow direction, compared to a given percentage of the original maximum energy of the node, can be negligible. In this way, it is more organized as the features of cluster-based routing, which enables the further integration of data and reduces network data traffic. In addition, the cluster of nodes is not too large and can reduce the traffic conflict.


#### 4.2.1. Discussion of the Various Cases of REWUM

In this paper, a routing protocol is proposed that combines virtual potential energy with local density of nodes and sleep-wake-up mechanism. The proposed routing protocol is self-organizing and robust. The routing protocol allows nodes to dynamically join or leave the network and enables nodes to automatically transmit information along the shortest path to reach a corresponding sink. The protocol can be applied in scenarios of single sink, multiple sinks, and three-dimensional WSNs. At the same time, the protocol takes a sleep-wake-up mechanism into account, makes a significant decrease in total network traffic, and achieves energy-saving as much as possible. However, multihop data transmission of WSNs, due to the high packet loss and energy efficiency, requires reliable links for end-to-end data delivery. A distributed learning automaton- (DLA-) based algorithm was proposed to find a small number of nodes with highly reliable links between them to transfer the data [18]. In this article, assuming that the communication is ideal, there is no further discussion about the packet loss problem.The statistics of rounds and residual energy, using a variety of cases of REWUM, are shown in Figures16 and 17.Figure 16
The rounds of various cases of REWUM in 5 different WSNs.Figure 17
The residual energy of various cases of REWUM in 5 different WSNs.Statistics are shown in Figures16 and 17 for 5 different WSN networks (respectively, a 200-node WSN in 400 × 200 m2, maximum link radius 50 m, the network average degree D = 8, and sleep nodes accounted for 30.50 %; a 300-node WSN in 400 × 200 m2, maximum link radius 40 m, the network average degree D = 7, and sleep nodes accounted for 31.33%; a 400-node WSN in 400 × 200 m2, maximum link radius 35 m, the network average degree D = 8, and sleep nodes accounted for 29.25%; a 500-node WSN in 400 × 200 m2, maximum link radius 30 m, the network average degree D = 8, and sleep nodes accounted for 34%; and a 500-node WSN in 400 × 200 m2, maximum link radius 25 m, the network average degree D = 8, and sleep nodes accounted for 30.50%).Cases of rounds and residual energy, using a variety of mechanisms of REWUM:0%,1%,5%,10%,20%,30%/Noi,50%/Noi, are shown in Figures 16 and 17.Here, theNoi is the layer label of nodei. In the 0% REWUM, namely, we do not use REWUM. As in Figures 16 and 17, by comparison using REWUM with no using REWUM, the survival time of network increases by 50%−100%. Therefore, REWUM is necessary (this paper uses the mechanism of 5% REWUM).Here, we illustrate the reasons why the REWUM is effective.Figure18(a) is the original link network of the 6-node WSN in 200 × 200 m2 with maximum link radius 200 m. The node3 is a sleep node. We take node0 as a sink. If node3 wakes up, it can communicate with all nodes in the WSN. Figure 18(b) is the figure of at the beginning of the layer label and information-flow direction. If we use the sleep-wake-up mechanism of RSTR without the condition (3), the sleep node3 will never be awakened because there are, at least, four normal nodes around it. However, if the energy of node1 is used up, the network will be disconnected. If we use REWUM, the sleep node3 will be awakened. In the simulation of the former case, the number of rounds is 1449 and average residual energy is 77.02%. Otherwise, in the simulation of the later case, the number of rounds is 4090 and average residual energy is 40.31%. This REWUM is an active wake-up mechanism with more intelligent features. The REWUM is effective and can significantly prolong the survival time of WSNs.Figure 18
Analyzing why the REWUM is effective. (a) The original link network of the 6-node WSN. (b) At the beginning, the structure of layer label and information-flow direction.
(a)(b)


## 4.1. The Simulation of RSTR Protocol

In this paper, all examples adopted the following mechanisms unless otherwise indicated.Nodes of WSNs are distributed in a corresponding region randomly. We supposed that sinks does not consider energy loss, all node’s initial energy2J, and each information packet 1000 bit. To simplify the simulation, we assume that all nodes periodically send data without considering the competition channel and network delay. If the network is not connected, the simulation will be terminated.Example 1.
The case of a two-dimensional WSN.
There is a simulation of a 120-node WSN in 400 × 200m2 with a maximum link radius 80 m, the network average degree D = 8, and sleep nodes accounted for 36.6667%. The calculation process of RSTR is shown in Figure 6.
When the network is disconnected, there are 4922 rounds, and the simulation is terminated. For detailed processing by RSTR, see Figures7–12.Figure 6
The calculation process of the two-dimensional WSN by RSTR.Figure 7
The connect network of the original WSN: Here, the number is node ID. The green numbers represent normal nodes, and the gray numbers represent sleep nodes.Figure 8
The program is initialized: We set the node 74 as a sink. The network is automatically organized and automatically layered. The numbers represent layer labels of the network (the nodes shown by –1 represent sleep nodes or energy of used-up nodes). The bar on the left of the number represents the node energy.Figure 9
The calculation process of the simulation: The gray line indicates that the energy of the node is used up.Figure 10
The calculation process of the simulation.Figure 11
The calculation process of the simulation.Figure 12
The network is disconnected, and the program is terminated.Example 2.
The case of a three-dimensional WSN.
There is a simulation of a 120-node WSN in 400 × 200 × 200m3, maximum link radius 100 m, the network average degree D = 13, and sleep nodes accounted for 23/120 = 19.1667%. The calculation process of RSTR is shown in Figure 13.
When the network is disconnected, there are 3568 rounds, and the simulation is terminated.Figure 13
The calculation process of the three-dimensional WSN by RSTR.Example 3.
The case of a multisink WSN.
There is a simulation of an original 4-sink 1000-node WSN in 1600 × 800m2 with a maximum link radius 100 m, the network average degree D = 8, and sleep nodes accounted for 356/1000 = 35.6%. The calculation process of RSTR is shown in Figure 14.
When the network is disconnected, there are 2526 rounds, and the simulation is terminated.
For the case of multisink routing, the node does not need to know which sink to contact with. The transmission of messages to the corresponding sink is assigned the RSTR automatically.Figure 14
The calculation process of the multi-sink WSN by RSTR.Example 4.
The case of a mobile sinks WSN.
In the following example, there is only a sink moving along designated routes in the 200-node WSN in 400 × 200m2 with a maximum link radius 50 m, the network average degree D = 7, and sleep nodes accounted for 62/200 = 31%. The calculation process of RSTR is shown in Figure 15.
When the network is disconnected, there are 3512 rounds, and the simulation is terminated. The RSTR protocol also can be applied to the mobile multisink situation.Figure 15
The calculation process of the mobile sinks WSN by RSTR.


## 4.2. Analysis and Discussion of RSTR Protocol

RSTR does not require flooding to calculate the information-flow direction and construct tree. It allows that the node maintains contact with its contacted node until reduction of certain energy of its contacted node (for example, we take 1% of the original energy of its contacted node) and then recalculates its information-flow direction. RSTR avoids energy consumption which is caused by unnecessary frequently updating of information and calculating the maximum potential energy of its neighbor nodes. The consumed energy of recalculation of the information-flow direction, compared to a given percentage of the original maximum energy of the node, can be negligible. In this way, it is more organized as the features of cluster-based routing, which enables the further integration of data and reduces network data traffic. In addition, the cluster of nodes is not too large and can reduce the traffic conflict.


### 4.2.1. Discussion of the Various Cases of REWUM

In this paper, a routing protocol is proposed that combines virtual potential energy with local density of nodes and sleep-wake-up mechanism. The proposed routing protocol is self-organizing and robust. The routing protocol allows nodes to dynamically join or leave the network and enables nodes to automatically transmit information along the shortest path to reach a corresponding sink. The protocol can be applied in scenarios of single sink, multiple sinks, and three-dimensional WSNs. At the same time, the protocol takes a sleep-wake-up mechanism into account, makes a significant decrease in total network traffic, and achieves energy-saving as much as possible. However, multihop data transmission of WSNs, due to the high packet loss and energy efficiency, requires reliable links for end-to-end data delivery. A distributed learning automaton- (DLA-) based algorithm was proposed to find a small number of nodes with highly reliable links between them to transfer the data [18]. In this article, assuming that the communication is ideal, there is no further discussion about the packet loss problem.The statistics of rounds and residual energy, using a variety of cases of REWUM, are shown in Figures16 and 17.Figure 16
The rounds of various cases of REWUM in 5 different WSNs.Figure 17
The residual energy of various cases of REWUM in 5 different WSNs.Statistics are shown in Figures16 and 17 for 5 different WSN networks (respectively, a 200-node WSN in 400 × 200 m2, maximum link radius 50 m, the network average degree D = 8, and sleep nodes accounted for 30.50 %; a 300-node WSN in 400 × 200 m2, maximum link radius 40 m, the network average degree D = 7, and sleep nodes accounted for 31.33%; a 400-node WSN in 400 × 200 m2, maximum link radius 35 m, the network average degree D = 8, and sleep nodes accounted for 29.25%; a 500-node WSN in 400 × 200 m2, maximum link radius 30 m, the network average degree D = 8, and sleep nodes accounted for 34%; and a 500-node WSN in 400 × 200 m2, maximum link radius 25 m, the network average degree D = 8, and sleep nodes accounted for 30.50%).Cases of rounds and residual energy, using a variety of mechanisms of REWUM:0%,1%,5%,10%,20%,30%/Noi,50%/Noi, are shown in Figures 16 and 17.Here, theNoi is the layer label of nodei. In the 0% REWUM, namely, we do not use REWUM. As in Figures 16 and 17, by comparison using REWUM with no using REWUM, the survival time of network increases by 50%−100%. Therefore, REWUM is necessary (this paper uses the mechanism of 5% REWUM).Here, we illustrate the reasons why the REWUM is effective.Figure18(a) is the original link network of the 6-node WSN in 200 × 200 m2 with maximum link radius 200 m. The node3 is a sleep node. We take node0 as a sink. If node3 wakes up, it can communicate with all nodes in the WSN. Figure 18(b) is the figure of at the beginning of the layer label and information-flow direction. If we use the sleep-wake-up mechanism of RSTR without the condition (3), the sleep node3 will never be awakened because there are, at least, four normal nodes around it. However, if the energy of node1 is used up, the network will be disconnected. If we use REWUM, the sleep node3 will be awakened. In the simulation of the former case, the number of rounds is 1449 and average residual energy is 77.02%. Otherwise, in the simulation of the later case, the number of rounds is 4090 and average residual energy is 40.31%. This REWUM is an active wake-up mechanism with more intelligent features. The REWUM is effective and can significantly prolong the survival time of WSNs.Figure 18
Analyzing why the REWUM is effective. (a) The original link network of the 6-node WSN. (b) At the beginning, the structure of layer label and information-flow direction.
(a)(b)


## 4.2.1. Discussion of the Various Cases of REWUM

In this paper, a routing protocol is proposed that combines virtual potential energy with local density of nodes and sleep-wake-up mechanism. The proposed routing protocol is self-organizing and robust. The routing protocol allows nodes to dynamically join or leave the network and enables nodes to automatically transmit information along the shortest path to reach a corresponding sink. The protocol can be applied in scenarios of single sink, multiple sinks, and three-dimensional WSNs. At the same time, the protocol takes a sleep-wake-up mechanism into account, makes a significant decrease in total network traffic, and achieves energy-saving as much as possible. However, multihop data transmission of WSNs, due to the high packet loss and energy efficiency, requires reliable links for end-to-end data delivery. A distributed learning automaton- (DLA-) based algorithm was proposed to find a small number of nodes with highly reliable links between them to transfer the data [18]. In this article, assuming that the communication is ideal, there is no further discussion about the packet loss problem.The statistics of rounds and residual energy, using a variety of cases of REWUM, are shown in Figures16 and 17.Figure 16
The rounds of various cases of REWUM in 5 different WSNs.Figure 17
The residual energy of various cases of REWUM in 5 different WSNs.Statistics are shown in Figures16 and 17 for 5 different WSN networks (respectively, a 200-node WSN in 400 × 200 m2, maximum link radius 50 m, the network average degree D = 8, and sleep nodes accounted for 30.50 %; a 300-node WSN in 400 × 200 m2, maximum link radius 40 m, the network average degree D = 7, and sleep nodes accounted for 31.33%; a 400-node WSN in 400 × 200 m2, maximum link radius 35 m, the network average degree D = 8, and sleep nodes accounted for 29.25%; a 500-node WSN in 400 × 200 m2, maximum link radius 30 m, the network average degree D = 8, and sleep nodes accounted for 34%; and a 500-node WSN in 400 × 200 m2, maximum link radius 25 m, the network average degree D = 8, and sleep nodes accounted for 30.50%).Cases of rounds and residual energy, using a variety of mechanisms of REWUM:0%,1%,5%,10%,20%,30%/Noi,50%/Noi, are shown in Figures 16 and 17.Here, theNoi is the layer label of nodei. In the 0% REWUM, namely, we do not use REWUM. As in Figures 16 and 17, by comparison using REWUM with no using REWUM, the survival time of network increases by 50%−100%. Therefore, REWUM is necessary (this paper uses the mechanism of 5% REWUM).Here, we illustrate the reasons why the REWUM is effective.Figure18(a) is the original link network of the 6-node WSN in 200 × 200 m2 with maximum link radius 200 m. The node3 is a sleep node. We take node0 as a sink. If node3 wakes up, it can communicate with all nodes in the WSN. Figure 18(b) is the figure of at the beginning of the layer label and information-flow direction. If we use the sleep-wake-up mechanism of RSTR without the condition (3), the sleep node3 will never be awakened because there are, at least, four normal nodes around it. However, if the energy of node1 is used up, the network will be disconnected. If we use REWUM, the sleep node3 will be awakened. In the simulation of the former case, the number of rounds is 1449 and average residual energy is 77.02%. Otherwise, in the simulation of the later case, the number of rounds is 4090 and average residual energy is 40.31%. This REWUM is an active wake-up mechanism with more intelligent features. The REWUM is effective and can significantly prolong the survival time of WSNs.Figure 18
Analyzing why the REWUM is effective. (a) The original link network of the 6-node WSN. (b) At the beginning, the structure of layer label and information-flow direction.
(a)(b)


## 5. Conclusions and Future Works

This paper takes the network connectivity as a prerequisite to discuss WSN routing protocols and proposes the Robust Self-organizing Tree-based Routing (RSTR). The routing protocol through establishment of layer label, minimum spanning tree, makes the nodes transmit information automatically along the shortest path to reach a corresponding sink. At the same time, this paper introduces the concept of virtual potential energy by considering residual energy and the local density of nodes. Using the node virtual potential energy to establish the information-flow direction of nodes, our algorithm makes the whole network energy to balancing consumption more, thus prolonging the survival time of the network significantly. RSTR does not require flooding to calculate the information-flow direction and construct tree. It allows that the node maintains communications with its contacted node until reduction of certain energy of its contacted node. RSTR avoids energy consumption which is caused by unnecessaryly frequently updating information and calculating the maximum potential energy of its neighbor nodes. As a large-scale WSN network, there is a large number of sleep nodes, and the network also needs to constantly add new nodes to maintain network operation. This paper introduces the sleep-wake-up mechanism for RSTR. Especially, the paper introduces the mechanism of REWUM. REWUM is an active wake-up mechanism with more intelligent features. The REWUM is effective and can significantly prolong the survival time of WSNs.For a large-scale WSN, the node near a sink, its energy consumption will be faster. In order to make the network function properly, we must constantly add nodes near sinks. In addition, single sink mechanism is not suitable for a large-scale WSN. For a large-scale WSN, the mechanism of multiple sinks or mobile sink would be an appropriate mechanism. In addition, if we do not continually add nodes near sinks, the initial WSN network should not be a random network. Correspondingly, there is a question that what kind of distribution of nodes and sleep-wake-up mechanism should be taken for WSNs and can the entire network obtain the longest survival time and achieve the most effective energy consumption. In addition, RSTR can be used in dynamic network of WSNs. Dynamic wireless sensor networks are more complex than static networks. More works should be conducted in the future about the nonrandom distribution of nodes and dynamic network of WSNs.



---

*Source: 5932347-2021-01-12.xml*