An Energy-Saving Hybrid-Optimization Scheduling Algorithm Based on Fat Tree in WSN

1. Introduction

Wireless sensor networks (WSNs) exhibit the feature of self-organization and the capability of fault tolerance, which are considerably suitable for the application in special environments. But energy supply is an important constraint for WSN, especially in harsh outdoor environments. Due to the fact that nodes must be powered by batteries, it is difficult to replenish the energy to nodes after energy depletion, which leads to the node death and ultimately results in the failure of the entire WSN. In the research, the WSN lifecycle generally refers to the span from starting working of the network to the first emergence of dead nodes. Li and Mohapatra [1] have drawn a conclusion that when the first node dies, there exists still 90% residual energy in network. Therefore, it is important to improve the WSN lifecycle while ensuring the node data transmission reliability, which is one of the main research issues in the further practical application and development of WSN [2-4].

The most immediate method to improve the WSN lifecycle is through the innovation of hardware technology, such as new low-energy sensor nodes, new large-capacity and small-volume batteries and the like. But this is limited by technologies of other fields and the breakthrough is difficult to achieve [5]. Hence, researchers need to explore the improvement of the WSN lifecycle through the innovation of network and software technologies. The research is less restricted, is easy to implement and has more optimization space. More importantly, it promotes the exploration of new theories and technologies and expands the application scope.

By analyzing the WSN lifecycle, we acquire the approaches to boost the WSN lifecycle, which includes two aspects: reducing its energy consumption for each node and balancing their energy consumption for all the nodes in network. Thereby, we propose an energy-saving hybrid-optimization scheduling algorithm based on fat tree (FT) in WSN. The novelty of the algorithm is presented as follows. First and foremost, we introduce the FT structure into the domain of WSN to resolve the problem of the energy consumption. Secondly, the FT is the set of all the shortest path trees and the FT can flexibly generate the fusion tree, and accordingly many energy efficiency methods can be organically synthesized and coordinated to reduce energy consumption in data fusion scheduling and boost the WSN lifecycle.

According to the problem-solving process mentioned above, the main contributions of our research are summarized as follows:

· We introduce the FT structure to optimize the fusion tree and the scheduling process.

· We design the load balancing mechanism and rotation mechanism of the fusion nodes to balance the network energy consumption.

· We propose a hybrid algorithm to improve the WSN lifecycle.

The remainder of the paper is organized as follows. Section 2 reviews the previous works. In Section 3, the hybrid-optimization scheduling algorithm of node data for energy consumption reduction based on FT is illustrated in detail, including the system model of the research problem, the algorithm of FT construction, the generation of fusion tree, the rotation mechanism and the sleep mechanism of fusion nodes. In Section 4, the performance of the proposed algorithm is evaluated by simulation experiments. Section 5 concludes the research and its future work.

2. Previous Works

Reviewing the existing researches, the main methods of WSN to reduce the network energy consumption and improve the network lifecycle are illustrated as follows:

(1) Optimizing and reducing the energy consumption of nodes in the monitoring and idle states. Authors of [6] proposed the adaptive threshold of remaining energy based ant colony routing algorithm (ATRE-ARA), which introduced the search angle correction pheromone heuristic function to limit the search path, reduce the node energy cost and balance the residual energy of nodes in WSN. In [7], the LIAA scheme was proposed to adjust the listen interval to improve network lifecycle. The key ideology was to fully utilize the energy consumption imbalance in network, allowing nodes far from the convergence point to use their remaining energy to increase the listening interval.

(2) The energy-efficient network topology and the communication protocol are selected to reduce data transmission. In [8], an energy-efficient routing algorithm was proposed. Time slot allocation was used in the specific way of network topology in one-dimensional queue WSN. In [9], network lifecycle was improved by fuzzy firebug swarm optimization algorithm, in which faulty nodes were declined and an efficient path between base station and source node was accordingly created. In [10], an algorithm based on ant colony optimization was proposed to construct the shortest path for mobile sink node to cross the selected sink node. The experimental evaluation verified that compared with several routing strategies in literature, the proposed strategy significantly improved the cluster head selection, balanced the cluster members, increased the network lifetime by 54%, reduced the transmission delay by 63%, and decreased the energy consumption by 47%.

(3) The amount of communication data is reduced through data aggregation and compression. In [11], the ARM architecture-based WSN data aggregation node (A-WDAN) was proposed, which was based on the ARM framework and could better aggregate and transmit data. In [12], the load-balanced clustering conjunction with coyote optimization with fuzzy logic (LBC-COFL) algorithm was proposed to reduce the load to improve the network lifecycle. The ultimate aim was to prolong the life circle through keeping the balance between the gateways without more energy load. In [13], FC-SEEDA, a secure and energy-saving data aggregation scheme for medical Internet of Things based on fog computing, was put forward. By taking advantage of fog computing’s distributed characteristics and other extended functions, the main goal of this scheme was to reduce the communication overhead and the energy consumption, while maintaining the secure aggregation of medical data between medical sensors and cloud servers.

(4) According to the application scenario, the working mode and sleep timing of nodes are adjusted. In [14], the modified approach to sleep scheduling mechanism with particle swarm optimization (MSSM-PSO) was proposed to put redundant nodes into sleep mode. By network coverage calculation, the redundant nodes were determined, and then these nodes were scheduled into the hibernation state. In [15], the collection node and the sending node were separated, and sleep nodes were reasonably scheduled to improve network lifecycle, in which the network life time was effectively prolonged by the intermediate node division. The nodes were divided into two categories, namely the nodes that only took charge of data collection and the nodes that only took charge of data sending. The redundant nodes were directly kept in sleep mode after the network layout completion, and then dormant nodes were scheduled effectively. In [16], a self-adaptive active sleep energy-saving method (AASEEM) for WSN was proposed. The method took into account the heterogeneity of network, improved some problems including network stability and cluster head selection procedures, and provided the principle of detailed pairing between sensor nodes to maximize energy utilization. In [17], PEFTOSPRO was a protocol suitable for solving the permutation routing problem in the multi-hop environment of WSN. In the process of data routing, wake-up and sleep technology and fault tolerance were adopted to save the energy of sensors, thus prolonging the life of WSN.

These methods have improved the energy efficiency of WSN to some extent, but they also face some difficulties, such as complexity and cost of clustering algorithms and routing protocols, the information loss caused by data aggregation, and the single optimization algorithm still has great space for improvement. It can be analyzed from the recent literature that the hybrid-optimization algorithm is fairly effective, which is superior to the single energy efficiency optimization algorithm and is widely used. Nevertheless, the hybrid-optimization algorithm is faced with a great challenge, that is, the lack of effective combination and coordination among various energy-saving methods, thus limiting the overall energy-saving potential. Therefore, the research goal of the paper is to explore more efficient and feasible energy-saving strategies and mechanisms for WSN. On the basis of introducing the FT structure, we organically synthesize the multiple simple and effective methods and ingeniously propose a new hybrid energy-saving method for WSN.

3. Methodology

3.1 Kernel Thoughts

Our kernel thoughts are to introduce the FT structure to resolve the problem by the fact that FT is the set of all the shortest path trees and FT can flexibly generate fusion trees. First of all, for reducing the energy consumption of each node, a hybrid energy-saving algorithm is adopted, combining transmission path shortening, data fusion and sleep mechanism.

- Transmission path shortening: FT is used to generate the fusion tree, which is the shortest path tree, so that as few nodes as possible consume energy.

- Data fusion: the data collected by nodes are fused at fusion nodes (non-leaf nodes), and the amount of data after the fusion is reduced, which reduces the energy expended by receiving and sending nodes accordingly.

- Sleep mechanism: the energy consumption ratio for sending, receiving, monitoring, and sleeping states is 4:3:3:0.006, respectively [18], which keeps non-sending and non-receiving nodes in sleep state as much as possible, instead of monitoring state, which greatly reduces the energy consumption. Moreover, for balancing the energy consumption of all the nodes, in order to prevent certain nodes in network from dying prematurely due to the heavy transmission burden, a hybrid energy-saving scheme is adopted combining the load balance mechanism and the rotation mechanism of nodes.

- The load balance mechanism of fusion nodes: in the process of generating the fusion tree by using FT, the number of immediate child nodes linked by fusion nodes at the same level can be balanced. Fusion node rotation mechanism: leaf nodes are the nodes with the least energy consumption in network. Therefore, fusion nodes are linked to leaf nodes as much as possible, and fusion nodes and leaf nodes (direct child nodes) can be rotated.

3.2 System Model

N nodes are randomly placed in the area of L×L. There is one single Sink node, all the nodes can send and receive data, and the transmission radius is r. The specific settings are as follows:

(1) The nodes have completed the data-sensing task.

(2) The nodes have the same structure and initial energy.

(3) All the nodes in network complete transmission within 1 hop and with equal time slots.

(4) Data fusion in network is the complete fusion.

3.3 Fat Tree Construction

Three basic structures of FT are shown in Fig. 1. The FT of the paper is constructed with the structure of Fig. 1(a).

In the node set, the flow of FT is constructed, as shown in Fig. 2. In Fig. 3, the nodes are randomly distributed, with r as the communication radius. And the child nodes are found layer by layer. The constructed FT is illustrated in Fig. 4.

3.4 Generating Fusion Tree

Certain nodes in FT have multiple parent nodes. We need to select a node as the authentic parent node and preserve its parent-child relationship. And the parent-child relationship of other pseudo parent nodes needs to be deleted. In this way, a fusion tree is generated through FT.

The principle of the authentic parent node selection is the doctrine of balance. For node N, after selecting the authentic parent node, the number of children of its authentic parent node and all the pseudoparent nodes should be the same or the closest. Thus, for all the parent nodes of node N, the energy consumption can be consistent or the closest.

An example of node 1 selected as the authentic parent node is indicated in Fig. 5.

In Fig. 5, node 1 receives data from nodes 3 and 4, and node 2 receives data from nodes 4, 5, 6 and 7, respectively. Node 4 in FT has two parent nodes, namely nodes 1 and 2; if node 1 is selected as the true parent node of node 4, then the relationship between node 4 and its pseudo-parent node 2 will be deleted. At this time, the number of children of the true parent node 1 of node 4 is 2, and the number of children of the pseudo-parent node 2 of node 4 is 3, that is, the difference between the number of children of the true parent node and that of the pseudo parent node of node 4 is expressed as [TeX:] $$|2-3|=1$$. If node 2 is selected as the true parent node of node 4, the difference between the number of children of the true parent node and that of the pseudo parent node of node 4 is expressed as [TeX:] $$|1-4|=3$$. To sum up, in the example, node 1 is selected as the true parent node of node 4, so that the energy consumption of node 1 and that of node 2 are the closest.

Selecting the authentic parent node is to seek the parent ones with the least number of children, as shown in formula (1):

where, [TeX:] $$\text { Node }_{\text {truep }}$$ is the selected authentic parent node and [TeX:] $$\left\{\text { ChildN }_i, \text { ChildN }_{i+1}, \ldots\right\}$$ is the set of the number of child nodes of all the parent nodes.

3.5 Fusion Node Rotation Mechanism

After the fusion tree is generated, although the load of each node is statically balanced, certain nodes in the fusion tree consume more energy than others because the nodes are randomly deployed and the frequency of perceiving data is different. For prolonging the lifecycle of the whole WSN, partial network structures are dynamically adjusted during the network runs, so that the energy of nodes with more energy consumption and that of the nodes with less energy consumption tend to be balanced, which is named as the converged node rotation mechanism.

The concrete thoughts of this rotation mechanism are that the rotation mechanism is commenced when the energy of non-leaf node N consumes 1-s%. Node N keeps a child node K, which is the node with the highest energy among all the children nodes of node N. Other child nodes of node N are linked to node K in one hop and stop the communication with node N; if the node cannot be linked to K within one hop, then it is linked to the brother node with the highest energy within one hop (including brothers and cousins) and stops the communication with node N; if the above process cannot be achieved, the parentchild relationship with node N will be maintained. When the energy consumption of certain node M is 1- c%, the rotation mechanism of the whole network is closed.

An example of the fusion node rotation mechanism is illustrated in Fig. 6, where node 2 performs the node rotation, and nodes 5, 6 and 7 are adjusted. Among them, the dotted line is the parent-child relationship before the rotation, and the solid line is the parent-child relationship after the rotation.

According to the thoughts of rotation mechanism, three key problems that need to be solved specifically are as follows:

(1) The critical problem is how to determine the energy of each node. The randomly deployed nodes are all 100% energy. In the construction process of FT in Section 3.3, the information such as the energy and the number of children of node N is stored. At the end of each fusion period, node N can get the residual energy values of other nodes through the simple calculation.

(2) The second problem is how to determine the s% and c% that control the start and close of rotation mechanism. The values of residual energy s% and c% of nodes are related to the fusion tree structure. Since the nodes in network are randomly deployed, the generated fusion tree structure is random as well. Thus, it is impossible to accurately calculate the optimal values of s% and c%. It is easily analyzed that the residual energy of a node correlate with the number of children of this node. The values of s% and c% are estimated by the density of nodes in network accordingly.

(3) The third problem is how to realize the rotation mechanism. The characteristics of FT and its construction method make the concrete realization of fusion node rotation easier and more efficient. When constructing FT, a node can record and store its parent node sequence, its brother node sequence as well as its cousin node sequence. When the fusion nodes rotate, only the nodes in these sequences need to be retrieved and compared, and it is unnecessary to retrieve all the nodes of the whole network. Hence, the category of network has less overhead and high efficiency.

3.6 Sleep Mechanism

In practical applications, the energy consumption ratio of each working state of sensor nodes varies considerably. According to the actual measurement of node energy consumption by Wu et al. [18], the measurement demonstrates that the energy consumption in the four states of receiving, sending, monitoring, and sleeping was 4:3:3:0.006, respectively. Therefore, introducing the sleep mechanism to keep nodes in sleep state as much as possible can effectively improve the WSN lifecycle.

There exist two difficulties involved when the sleep mechanism is applied: node state transition and sleep node awakening. Node state transition is a process of adopting the sleep mechanism, which directly affects the network energy efficiency. For the FTEBHSA algorithm proposed in this paper, the listening state is replaced by the sleep state. In the same period, the child node sends data and its parent node receives data; in the same period, the parent node sends data and its child node sleeps; in other periods of the whole fusion cycle, both the child node and the parent node are in the sleep state. Sleep-node awakening means that the node changes from the sleep state to the receiving or sending state, and if the node is not awakened in time, the data loss will be caused. For the FTEBHSA algorithm, the system model limits all the nodes in network to complete transmission within 1 hop and with equal time slots. By waking up the sleeping nodes at a fixed time slot interval, the data loss can be avoided. Certainly, in an unequal time slot system, the wake-up of the sleep nodes needs the further research.

3.7 Energy Consumption Calculation

In the periodic convergence, the nodes are in monitoring state for most of time, so the most immediate and effective energy-saving method is to make the nodes sleep as much as possible during the monitoring period. The energy consumption can be calculated according to formula (2):

where n is the number of nodes, [TeX:] $$w_t, w_r \text { and } w_s$$ denote the energy consumption of node in the sending, receiving and sleeping states, respectively, and [TeX:] $$t_i, r_i \text { and } s_i$$ are the time that the node has experienced in the corresponding three states. Apparently, if the fusion period is T, then [TeX:] $$T=t_i+r_i+s_i .$$

In formula (2), it is not conducive to reflecting the overall performance of the network, so the network energy consumption formula is rewritten as formula (3):

where the fusion period is T, and there are m times of information transmission in the period. The network energy consumption W has a linear relationship with the number of information transfers m and the convergence period T. And the more communication times are, the longer the convergence delay is, and the higher the network energy consumption is.

4. Simulation Experiments and Result Analysis

4.1 Experimental Settings

We design three categories of simulation experiments to verify the performance of the FTEBHSA algorithm: comparative experiment of network energy consumption under different fusion trees, comparative experiment of network energy consumption under different strategies, and comparative experiment of network lifecycle under different algorithms. And parameters are illustrated in Table 1.

4.2 Comparative Experiment of Network Energy Consumption under Different Fusion Trees

The performance of different fusion trees is quite different in energy consumption. Therefore, firstly, the energy consumption of fusion scheduling under different fusion tree structures is simulated and compared, including greedy incremental tree (GIT) algorithm, shortest path tree (SPT) algorithm, center at nearest source (CNS) algorithm, min dominating set tree (MDST) algorithm, and fusion tree based on FT (FTFT) algorithm in this paper.

So as to calculate the energy consumption easily, it is assumed that each node sends data only once. That is, the number of transmissions is equal to the number of nodes. According to formula (3), the network energy consumption can be calculated as follows: [TeX:] $$W=104.82 n+0.09 n T.$$

The experimental results of network energy consumption comparison experiments under different fusion trees are illustrated in Fig. 7.

In Fig. 7, as the number of nodes increases, the network energy consumption under different fusion trees accordingly increases. When the number of nodes is the same, the network energy consumption under different fusion trees varies, but the difference is small. But the difference increases with the increase of the number of nodes.

In formula (3), W is linearly proportional to m and T, and the transmission amount of the experiment is equal to the node amount, so energy consumption W is linearly proportional to n. On the other hand, for the energy of the node in sleep state can almost be ignored, the impact of the fusion period T is weakened. As a result, although there are differences in the fusion periods of different fusion tree structures, they are still in the same magnitude order. However, the FTFT structure of the paper is more favorable in energy consumption, because in the process of FTFT construction, the node balance operation is carried out, which reduces the network delay, thus shortening the convergence period and reducing the network energy consumption.

4.3 Comparative Experiment of Network Energy Consumption under Different Strategies

In this paper, a combination of data fusion, sleep mechanism, load balance and node rotation is adopted to reduce the energy consumption and improve the WSN lifecycle. For comparing the energy consumption under different strategies, FTEBHSA algorithm without sleep mechanism, FTEBHSA algorithm without fusion mechanism, FTEBHSA algorithm without rotation mechanism, and FTEBHSA algorithm are selected and carried out the comparative simulation experiments. The simulation experiment is referred to as the ablation experiment of FTEBHSA algorithm. The simulation experiment area is 200×200 m². The number of nodes varies from 100 to 500. And it is assumed that each node sends data only once.

The comparative experimental results of the energy consumption under different strategies are illustrated in Fig. 8.

In Fig. 8, it is observed that the energy consumption under different strategies increases with the increase of the number of nodes. Among the factors affecting the energy consumption, sleep mechanism has the most significant impact on the network energy consumption, followed by the data fusion strategy, and the rotation mechanism has the least impact. For example, when the amount of nodes is 500, the network energy consumption of FTEBHSA without rotation mechanism is 3 times much higher than that of FTEBHSA, the network energy consumption of FTEBHSA without fusion mechanism is 8 times much higher than that of FTEBHSA, while the network energy consumption of FTEBHSA without sleep mechanism is nearly 50 times higher than that of FTEBHSA. As the density of nodes in network increases, the proportion of energy consumption continues to expand.

4.4 Comparative Experiment of Network Lifecycle under Different Algorithms

For verifying the superiority of the algorithm in network lifecycle, the scheduling algorithm based on local tree reconfiguration (LTRBSA), the scheduling algorithm based on shortest path tree (SPTBSA) and the algorithm of this paper are adopted for the comparative experiments in network lifecycle. Since the sleep mechanism is not used for LTRBSA and SPTBSA, the FTEBHSA is presented as FTEBHSA without sleep mechanism and FTEBHSA with sleep mechanism. These four algorithms are compared through the simulation experiments.

The simulation experiment area is 200×200 m². The number of nodes varies from 100 to 500. The sum of fusion cycles is used to represent the network lifecycle, and the initial energy of any node is 150 W (sending data 2,500 times). The results of experiments are presented in Fig. 9.

In Fig. 9, the node amount is between 100 and 500, and the lifecycle decreases with the increase of the node amount.

FTEBHSA with sleep mechanism exhibits the longest network lifecycle, which is nearly twice as much as other algorithms. It can be observed that the sleep mechanism is crucial for comprehensive energy consumption reduction. Although SPTBSA has global information, FTEBHSA without sleep mechanism and LTRBSA, both have much longer lifespan than SPTBSA, because the fusion node rotation mechanism of FTEBHSA without sleep and the second step and third step of LTRBSA both prolong the lifecycle of bottleneck nodes.

It is noted that the lifecycle of FTEBHSA without sleep is not fairly different from that of LTRBSA, since algorithms both use effective methods to prolong the lifespan of bottleneck nodes. Therefore, the comprehensive performance of the multiple experiments is not much different.

In addition, the more sensor nodes are, the shorter the lifecycle is, which is because there are more nodes in network to collect data and more data must be transmitted and aggregated. Therefore, the bottleneck node must consume more energy to some extent.

At the same time, the statistical tests on the experimental results are conducted. Because the data of experimental results is not in normal distribution, the Friedman test is carried out by SPSS. The statistical tests show P < 0.05, which is statistically significant.

5. Conclusion

For reducing the network energy consumption, the FTEBHSA algorithm is put forward, and the FT structure is introduced to organically integrate various methods, including SPT optimization, the load balance of fusion tree, the fusion node rotation mechanism and the node sleep mechanism monitoring. Through the simulation experiments, it is verified that the network size is directly proportional to the total energy consumption of the network and inversely proportional to the network lifecycle; the sleep mechanism has the greatest impact on the network energy consumption; the proposed algorithm of the paper performs optimally in various comparative experiments. Besides, the proposed algorithm is researched under the condition that the initial nodes have the equal energy. In the future, the researches on the unbalanced energy and node load balance need the further exploration for WSN, which will be the huge challenges as well as the research direction.

Conflict of Interest

The authors declare that they have no competing interests.

Funding

None.