# Switching Algorithm with Prediction Strategy for Maximizing Lifetime in Wireless Sensor Network

Authors: Chuan-Jun Yi; Geng Yang; Hua Dai; Liang Liu; Ning Li
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

In wireless sensor networks (WSNs), the sensed data of each node are usually gathered through a data collection tree rooted at the sink node. The data collection tree generated randomly usually does not have the longest network lifetime. How to prolong the network lifetime is one of the main challenges in WSNs. In this paper, we propose a switching algorithm with prediction strategy (SAPS) to enhance the lifetime of WSNs through reducing the load of the node with the highest load by switching its descendants. In SAPS, the shortest path to the sink is chosen for each switched node to ensure that the routing tree is shortest, thus reducing the delay and energy expenditure of data collection. Furthermore, a prediction strategy which ensures that the highest load in the network decreases in each switching is developed to guarantee high efficiency and fast convergence of the algorithm. A distributed version of our algorithm, called DSAPS, is also designed. Simulation results demonstrate that our algorithms outperform existing methods in terms of network lifetime, maximum level of the routing tree, energy expenditure of switching, energy expenditure of data collection in each round, and rate of convergence.


---

## Body

## 1. Introduction

With the rapid development of electronics and computer technology, wireless sensor networks (WSNs) have been widely used in various applications, such as industrial prognostics and health management [1], agricultural activities [2], traffic lights management [3], urban search and rescue activities [4], and public safety and military systems [5]. In such applications, a number of sensors are deployed in the monitoring field to collect the needed information and transmit the sensed data to the sink node periodically. In most scenarios, the sensor nodes are organized into a data collection tree rooted at the sink node, and the sensed data are routed through the data collection tree to the sink by multihops.In WSNs, sensors are usually powered by energy-limited batteries, and it may be cost prohibitive to replace exhausted batteries or even impossible in harsh environment such as active volcanoes, battlefields, or nuclear polluted regions [5, 6]. Therefore, maximizing network lifetime has become an important target in protocol design for data collection. Extensive researches have been proposed on this topic, and many popular energy conservation techniques are proposed such as efficient duty-cycling [7–10], sink mobility [11–14], topology control for redundant nodes [15–17], and load balancing [6, 10, 18, 19], among others.During the process of data collection, power of each sensor node is consumed mainly by transmitting and receiving data packets, while the power of sensing and computation is negligible. The 1-hop nodes, which are the children of the sink, are usually the bottleneck nodes of the network because replaying more packets will deplete their energy quickly. Many of the existing load balancing-based methods prolonged the network lifetime by reducing the load of the bottleneck nodes. However, the rates of convergence of these approaches are slow and their lifetimes can be improved further. The algorithms we propose in this paper can efficiently solve the above problems.The major contributions of this paper are as follows:(1)
We propose a switching algorithm with prediction strategy (called SAPS) which minimizes the load of the bottleneck node for maximizing network lifetime. The routing tree is kept shortest during the process of switching, thus minimizing delays and energy consumption of data collection.(2)
Whether a node is switchable is determined by the prediction strategy which ensures every switching lowers the highest load in the network to achieve fast convergence. As far as we know, our algorithm is the fastest approach for maximizing network lifetime. The simulation results show that SAPS is converged after several iterations while maximizing network lifetime.(3)
We also provide distributed implementation of the proposed algorithm, called DSAPS. The simulation results demonstrate that DSAPS outperforms existing approach in the literature [19] in terms of lifetime, rate of convergence, and energy expenditure.The rest of the paper is organized as follows. Section2 presents the related works. The definitions and analyses of the problem are introduced in Section 3. The proposed algorithms are detailed and analyzed in Section 4 and the simulation results are presented in Section 5. Finally, we give some concluding remarks in Section 6.


## 2. Related Work

The problem of network lifetime maximization of WSNs has been extensively investigated in recent years. Many researchers prolong network lifetime by using energy-efficient techniques, such as efficient duty-cycling [7–10], sink mobility [11–14], topology control for redundant nodes [15–17], and load balancing [6, 10, 18, 19], among others.MAC-based solutions which exploit the possibility to tune the duty-cycle have been used for energy saving in WSNs. In [7], a low duty-cycle data gathering protocol, called BailighPulse, was presented for mostly off WSN applications. BailighPulse incorporated a novel multihop wake-up scheme that allowed for energy-efficient recovery of network synchronization, with which the radio duty-cycles were reduced efficiently and the energy consumption during wake-up was minimized. In [8], the accurate models for determining the neighbor discovery time were proposed for the main asynchronous schedule-based duty-cycle mechanisms, which considered message loss probability and yielded more precise estimations than the traditional models. In [9], an energy-efficient cross-layer MAC protocol based on the integrated use of a scheduling schema and a switched-beam antenna was presented and validated, in which the MAC scheduler managed the activation of the antenna sectors based on information coming from both MAC and network layers. In [10], a holistic approach was proposed to prolong the network lifetime, which integrated intraroute coordination (at MAC layer) and interroute coordination (at network layer).In [11–14], sink mobility was considered for maximizing network lifetime. Linear programming and column generation approaches were described in [11]. However, these algorithms cannot be easily extended into distributed versions. The optimal sink scheduling problem in WSNs was investigated in [12]. A novel notation placement pattern was developed to bound time varying routes with the placement of sinks which transformed the problem from time domain into pattern domain and thus significantly decreased the problem complexity. In [13], a cluster-based mobile sink exploration scheme was presented to guide data packets efficiently to mobile sinks, in which a source node could identify the sink location without knowledge of node locations, and multiple routing paths were established from a sensor to the sink to enhance network lifetime. In [14], optimal sensor deployment, activity scheduling, and data routing were taken into consideration for maximizing network lifetime, as well as sink mobility.Some scholars exploit node redundancy to enhance network lifetime. In [15], a distributed self-stabilizing and wear-out-aware algorithm was presented to achieve resiliency by maintaining a necessary set of working nodes and replacing failed ones when needed. The algorithm in [16] exploited the redundancy in the sensor network to prolong the network lifetime while guaranteeing the coverage requirement. The authors in [17] explored a scheme for generating random sensor networks by deploying a minimum number of active nodes required to achieve a fully connected network topology and essentially full area coverage, while increasing the network lifetime. Several graph metric properties of the networks were also explored for getting further optimized networks.Recently, load balancing is also used to maximize the lifetime of WSNs. The main idea is to route packets through nodes with lower loads such that nodes with higher loads can participate less in data transmission. As a result, the minimum nodal lifetime in the network may be extended and the network lifetime may be prolonged.A distributed top-down algorithm was presented in [6], which constructed the load balanced routing tree layer by layer such that each layer was optimally extended, using a network flow model. The major contribution is to address the need for time sensitive data gathering to guarantee minimum delay when maximizing network lifetime, whereas the residual energy of sensor nodes is not taken into consideration when establishing routing paths.In [18], it was assumed that the bottleneck nodes of a data collection tree were 1-hop nodes, and the load balance and energy efficiency of 1-hop nodes were taken into account. The descendants or the loads of 1-hop nodes were allocated in a balanced way according to the predicted residual energy of each node, whereas this algorithm is a centralized solution, and the assumption that the bottleneck nodes were 1-hop nodes is not always realistic.I
2
C scheme in [10] extended the network lifetime via dynamic adjustment of the data collection tree. Each sensor node periodically selected the best neighbor as its parent, which maximized the minimal nodal lifetime between the node, its current parent, and the new parent, and thus the nodal lifetimes might be balanced gradually across the entire network. Yet, the best new parent of a node was selected according to the loads of its neighbors, without consideration of the path loads (path load of a node means the highest load in the path from the node to the sink), which influences the efficiency of load balancing.Path load was taken into account when selecting a new parent in [19], and a randomized switching algorithm (called RaSMaLai) was proposed to maximize the network lifetime based on the concept of bounded balanced trees. Distributed implementation called D-RaSMaLai was also provided. However, the optimal bounded balanced tree constructed by RaSMaLai or D-RaSMaLai is not always the tree with the maximum lifetime, and the level of the data collection tree after switching may increase, which will result in higher delays and more energy consumption for forwarding packets. Furthermore, the randomized switching strategy may lead to more iterations and slower convergence.To address the issues concerned, we present an efficient switching algorithm with prediction strategy (called SAPS) and its distributed version (called DSAPS), which achieve the converged state much faster while maximizing network lifetime.


## 3. System Model and Problem Statement

### 3.1. Network Model

In this paper, we consider a wireless sensor network withn sensor nodes v1,…,vn and a sink node S, randomly placed within a square area of Q×Q. We model the topology of the WSN by an undirected graph G=(V,E), where V={S,v1,…,vn} and E is the set of edges representing the radio communication links between sensors. We assume that sensors are placed densely enough to ensure that the graph G is connected and the sensors as well as the sink are static.A data collection treeT rooted at the sink node S is constructed for data collection. The random shortest path tree is constructed as follows: The root S broadcasts a routing message including its own ID and its level LS (LS=0), asking sensor nodes to organize into a routing tree. After a node vi without an assigned level hears this message, it assigns its own level Li to be the level in the message plus one and chooses the sender of the message as its parent. Then, vi rebroadcasts the routing message with its own ID and Li. The routing message floods down the tree until all nodes have been assigned a level and a parent. When a node needs to send a message to the sink, it transmits the message to its parent, which in turn forwards the message onto its parent, and so on, eventually reaching the sink.A nodevi can hear any message transmitted by the nodes within its hearing distance, irrespective of whether or not vi is the intended recipient. Then, vi will drop messages not addressed to it. The nodes within the hearing distance of vi can be classified into three categories: the parent of vi, the children of vi, denoted by Ci (Ci=ϕ, when vi is a leaf node), and the neighbors of vi, denoted by Ni.


### 3.2. Problem Statement

We assume that the sink has infinite power supply, while every sensor is energy limited. A sensor will be a failure node if it runs out of its energy. In this paper, we concentrate on extending the lifetime of the bottleneck node in WSNs to prolong the network lifetime. To simplify the descriptions of the issue, a few definitions are introduced as follows.Definition 1 (round).
A round of data collection denotes the process when the sink broadcasts a collecting message till the data of each sensor reaches the sink.Definition 2 (lifetime of a node).
The lifetime of a node is the number of data collection rounds in which it can participate before running out of its energy.
LetT(vi) denote the subtree rooted at vi and let ni denote the number of nodes in T(vi); then we have ni=∑vk∈Cink+1. We assume that every sensor generates m-bit message in each data collection round. Ideally, the amount of data received by vi from its ni-1 descendants will be Rir=m×(ni-1) bits, and vi will transmit Rit=m×ni bits to its parent. Let Et and Er denote the energy used to transmit and receive 1 bit of data in wireless communication, respectively. Therefore, the energy consumption of vi in each data collection round is given by(1)ri=Rir×Er+Rit×Et=m×ni-1×Er+m×ni×Et.
The current residual energy ofvi is denoted by ei, and the lifetime of vi is defined as (2)ti=eiri,where the unit of ti is round.Definition 3 (lifetime of a tree).
The lifetime of a data collection treeT is the lifetime of the node that runs out of its energy first; in other words, it is the minimum lifetime of all nodes in the tree. Formally,(3)tT=min⁡ti∣i=1,…,n.
The network lifetime of a tree-based WSN is just the lifetime of the data collection treeT in the network.Definition 4 (load of a node).
The loadγi of a node vi is defined as the reciprocal of ti; that is,(4)γi=1ti=riei.
Obviously, the node with the highest load must be the one with the minimum lifetime, which is called the bottleneck node.Definition 5 (path load).
In a given data collection treeT, the path from a node vi to the sink is denoted by Pi. The path load σi of vi is the highest load of all nodes along the path Pi. Formally, σi=max⁡γi∣vj∈Pi (specifically, the load of the sink is zero).
Ifvj is the parent of vi on Pi, then the path load σi of vi can be recursively defined as(5)σi=max⁡σj,γi.Definition 6 (lifetime maximization problem, LMP).
The lifetime maximization problem in tree-based WSN is to maximize the lifetime of the bottleneck node with the minimum lifetime in the data collection treeT. Formally,(6)max⁡tT=max⁡min⁡ti∣i=1,…,n.
Substituting formula (4) into formula (6),(7)max⁡tT=min⁡max⁡γi∣i=1,…,n.
It can be seen that the lifetime maximization problem can be converted to minimizing the highest load among all nodes in the network. But in the RaSMaLai algorithm, the lifetime maximization problem was resolved into the bounded load balanced tree problem, which considered that the optimalδ-bounded balanced tree with the minimum δ would be the tree with the maximum lifetime, where δ was defined as the highest path load of all leaf nodes minus the lowest path load of all leaf nodes. However, we find that this consideration does not work in all situations. The following example will illustrate this problem.Figure1 depicts two different data collection trees T1 and T2 produced by RaSMaLai in a connected graph G. In this figure, node vi is represented by a circle with label i. For simplicity, we assume that each node produces 1 unit of data in each data collection round, with transmission and reception costs of 1 unit. Another assumption is also made that the energy budget is e4=7/13 for node v4 and e5=0.5 for node v5, and for all other nodes it is 1. The solid lines indicate the edges used in the current tree, while the dotted lines represent potential edges that can be used to transform the current tree. We mark node vi with (γi, σi) to denote its load and path load. As shown in Figure 1(a), we can get δ1=13-3=10, and v4 drawn with a red background is the one with the highest load in T1; hence, its lifetime is right the network lifetime t(T1)=t4=1/13. According to the RaSMaLai algorithm, v6 is considered for switching. Suppose that v6 is decided to switch to v5; a new tree T2 after switching is obtained as shown in Figure 1(b). We can find that δ2=14-5=9, and v5 is the one with the highest load in T2, so we have t(T2)=t5=1/14. Now we can see that although δ2<δ1 after switching of v6, it results in t(T2)<t(T1), which shows that T2 is more load balanced than T1 but has a shorter lifetime.Figure 1
Example ofδ-bounded balanced trees T1 and T2.
(a)
Data collection treeT1
(b)
Data collection treeT2We can conclude that the optimalδ-bounded balanced tree constructed by RaSMaLai is not always the tree with the maximum lifetime. For maximizing the network lifetime, the highest load among all nodes in the data collection tree should be minimized, as presented in formula (7).


## 3.1. Network Model

In this paper, we consider a wireless sensor network withn sensor nodes v1,…,vn and a sink node S, randomly placed within a square area of Q×Q. We model the topology of the WSN by an undirected graph G=(V,E), where V={S,v1,…,vn} and E is the set of edges representing the radio communication links between sensors. We assume that sensors are placed densely enough to ensure that the graph G is connected and the sensors as well as the sink are static.A data collection treeT rooted at the sink node S is constructed for data collection. The random shortest path tree is constructed as follows: The root S broadcasts a routing message including its own ID and its level LS (LS=0), asking sensor nodes to organize into a routing tree. After a node vi without an assigned level hears this message, it assigns its own level Li to be the level in the message plus one and chooses the sender of the message as its parent. Then, vi rebroadcasts the routing message with its own ID and Li. The routing message floods down the tree until all nodes have been assigned a level and a parent. When a node needs to send a message to the sink, it transmits the message to its parent, which in turn forwards the message onto its parent, and so on, eventually reaching the sink.A nodevi can hear any message transmitted by the nodes within its hearing distance, irrespective of whether or not vi is the intended recipient. Then, vi will drop messages not addressed to it. The nodes within the hearing distance of vi can be classified into three categories: the parent of vi, the children of vi, denoted by Ci (Ci=ϕ, when vi is a leaf node), and the neighbors of vi, denoted by Ni.


## 3.2. Problem Statement

We assume that the sink has infinite power supply, while every sensor is energy limited. A sensor will be a failure node if it runs out of its energy. In this paper, we concentrate on extending the lifetime of the bottleneck node in WSNs to prolong the network lifetime. To simplify the descriptions of the issue, a few definitions are introduced as follows.Definition 1 (round).
A round of data collection denotes the process when the sink broadcasts a collecting message till the data of each sensor reaches the sink.Definition 2 (lifetime of a node).
The lifetime of a node is the number of data collection rounds in which it can participate before running out of its energy.
LetT(vi) denote the subtree rooted at vi and let ni denote the number of nodes in T(vi); then we have ni=∑vk∈Cink+1. We assume that every sensor generates m-bit message in each data collection round. Ideally, the amount of data received by vi from its ni-1 descendants will be Rir=m×(ni-1) bits, and vi will transmit Rit=m×ni bits to its parent. Let Et and Er denote the energy used to transmit and receive 1 bit of data in wireless communication, respectively. Therefore, the energy consumption of vi in each data collection round is given by(1)ri=Rir×Er+Rit×Et=m×ni-1×Er+m×ni×Et.
The current residual energy ofvi is denoted by ei, and the lifetime of vi is defined as (2)ti=eiri,where the unit of ti is round.Definition 3 (lifetime of a tree).
The lifetime of a data collection treeT is the lifetime of the node that runs out of its energy first; in other words, it is the minimum lifetime of all nodes in the tree. Formally,(3)tT=min⁡ti∣i=1,…,n.
The network lifetime of a tree-based WSN is just the lifetime of the data collection treeT in the network.Definition 4 (load of a node).
The loadγi of a node vi is defined as the reciprocal of ti; that is,(4)γi=1ti=riei.
Obviously, the node with the highest load must be the one with the minimum lifetime, which is called the bottleneck node.Definition 5 (path load).
In a given data collection treeT, the path from a node vi to the sink is denoted by Pi. The path load σi of vi is the highest load of all nodes along the path Pi. Formally, σi=max⁡γi∣vj∈Pi (specifically, the load of the sink is zero).
Ifvj is the parent of vi on Pi, then the path load σi of vi can be recursively defined as(5)σi=max⁡σj,γi.Definition 6 (lifetime maximization problem, LMP).
The lifetime maximization problem in tree-based WSN is to maximize the lifetime of the bottleneck node with the minimum lifetime in the data collection treeT. Formally,(6)max⁡tT=max⁡min⁡ti∣i=1,…,n.
Substituting formula (4) into formula (6),(7)max⁡tT=min⁡max⁡γi∣i=1,…,n.
It can be seen that the lifetime maximization problem can be converted to minimizing the highest load among all nodes in the network. But in the RaSMaLai algorithm, the lifetime maximization problem was resolved into the bounded load balanced tree problem, which considered that the optimalδ-bounded balanced tree with the minimum δ would be the tree with the maximum lifetime, where δ was defined as the highest path load of all leaf nodes minus the lowest path load of all leaf nodes. However, we find that this consideration does not work in all situations. The following example will illustrate this problem.Figure1 depicts two different data collection trees T1 and T2 produced by RaSMaLai in a connected graph G. In this figure, node vi is represented by a circle with label i. For simplicity, we assume that each node produces 1 unit of data in each data collection round, with transmission and reception costs of 1 unit. Another assumption is also made that the energy budget is e4=7/13 for node v4 and e5=0.5 for node v5, and for all other nodes it is 1. The solid lines indicate the edges used in the current tree, while the dotted lines represent potential edges that can be used to transform the current tree. We mark node vi with (γi, σi) to denote its load and path load. As shown in Figure 1(a), we can get δ1=13-3=10, and v4 drawn with a red background is the one with the highest load in T1; hence, its lifetime is right the network lifetime t(T1)=t4=1/13. According to the RaSMaLai algorithm, v6 is considered for switching. Suppose that v6 is decided to switch to v5; a new tree T2 after switching is obtained as shown in Figure 1(b). We can find that δ2=14-5=9, and v5 is the one with the highest load in T2, so we have t(T2)=t5=1/14. Now we can see that although δ2<δ1 after switching of v6, it results in t(T2)<t(T1), which shows that T2 is more load balanced than T1 but has a shorter lifetime.Figure 1
Example ofδ-bounded balanced trees T1 and T2.
(a)
Data collection treeT1
(b)
Data collection treeT2We can conclude that the optimalδ-bounded balanced tree constructed by RaSMaLai is not always the tree with the maximum lifetime. For maximizing the network lifetime, the highest load among all nodes in the data collection tree should be minimized, as presented in formula (7).


## 4. The Proposed Algorithms

### 4.1. Design of the SAPS Algorithm

As mentioned in the last section, our goal is to minimize the highest load among all nodes, that is, to minimize the loadγm of the bottleneck node vm. According to formulae (1) and (4), we have(8)γm=rmem=m×nm-1×Er+m×nm×Etem=m×nm×Er+Et-m×Erem.It can be seen that the loadγm of the bottleneck node vm is proportional to the number of the nodes nm in the subtree rooted at vm, with given m, Er, Et, and em. Switching the descendants of vm to other subtrees can reduce nm, which decreases γm in turn.If nodevj is considered for switching in RaSMaLai, the potential parent list of vj is constructed as Wj=vi∣vi∈Nj,σj-σi>δ. If vj is decided to switch, a node is chosen randomly with uniform probability from Wj to be the new parent for vj, without considering the level of the new parent in the tree. Thus, a node whose level is greater than that of vj may be chosen as the new parent of vj, which may increase the level of the data collection tree. And the number of hops from some of the nodes to the sink will be increased, which will result in higher delay and more energy consumption in each data collection round.Furthermore, after switchingvj from the old parent vd to the new parent vx in RaSMaLai, the highest load on the path Pd decreases indeed, but the highest load on Px will increase, sometimes even exceeding that on Pd before switching. Thus, the highest load in the tree may be higher than before, which is not helpful for enhancing the network lifetime. All in all, some switching is counterproductive which leads to more iterations and slower convergence.To overcome these problems, the level of the data collection tree is taken into account in our SAPS algorithm. Whenvj is considered for switching, only the neighbors whose level is less than that of vj will be added to the potential parent list Wj (Wj=vi∣Li<Lj,vi∈Nj). Thus, the level of the tree will not increase after switching. Then, the node vx with the minimum path load in Wj will be chosen as the new parent of vj. Thus, the highest load on Px after switching vj to vx may not exceed that on Pd before switching vj from vd in most cases.In some particular cases, the highest load onPx after switching will be higher than that on Pd before switching. To overcome this problem, SAPS estimates the path load σx′ on Px assuming vj has been switched from vd to vx, which is σx′=max⁡γx′∣vi∈Px. If σx′≥σd, vj is not switched to vx because the highest load on Px after switching will exceed that on Pd before switching, which is not conducive to decreasing the maximum load in the network. Otherwise, vj will be switched to vx. Such prediction strategy ensures that every switching will lower the highest load in the network, which makes SAPS converge faster than other existing schemes.In addition, no parameter is needed to control the maximum number of iterations in SAPS, which is different from RaSMaLai. SAPS terminates automatically when there is no node switched, which means the algorithm is converged.


### 4.2. Details of the SAPS Algorithm

SAPS starts with a random shortest path tree, and the pseudocode is shown in Algorithm1. All the major symbols used in the algorithm are given as follows:V: the set of all nodes in a WSN.Lj: the level of vj.Cj: the set of children of vj.Nj: the set of neighbors of vj.T(vj): the subtree rooted at vj.γi: the load of vi.Px: the path from vx to the sink.σi: the path load of vi.Wj: the potential parent list of vj.γi′: the estimated load of vi on Px assuming some node has been switched to vx.σx′: the estimated path load of vx assuming some node has been switched to vx.Algorithm 1:SAPS.
(1)    Calculate γi and σi for each node vi∈V;
(2)    Select the node vm with the highest load;
(3)    while (true)
(4)     flg←0;
(5)       queue α←Cm;
(6)       while (α≠ϕ)
(7)      Remove node vj from the head of the queue α;
(8)        Wj ← any node in Nj whose level is less than Lj;
(9)        if (Wj=ϕ) α←Cj;
(10)     else
(11)      Select the node vx with the lowest path load from Wj;
(12)      Estimate the path load σx′ on Px assuming vj has been switched from vd to vx;
(13)      if (σx′≥σd) α←Cj;
(14)      else
(15)       Switch vj to vx;
(16)       If Lj is changed, then update the level of each node in T(vj);
(17)       Update γi and σi for each node vi∈V;
(18)       flg←1;
(19)
(20)
(21)
(22)  if (flg  ==  0) return;
(23)  else  Select the node vm with the highest load again;
(24)The details of the SAPS algorithm are described as follows.Step 1.
First, the loadγi for each node vi in the tree is initialized from bottom to top. Then, the path load σi for each node is initialized from top to bottom (line 1). After that, the bottleneck node vm with the highest load is selected (line 2).Step 2.
The flag variableflg is zero-initialized, which means that no descendant of vm has been switched (line 4). Then, the children of vm are inserted into the queue α (line 5).Step 3.
Ifα≠ϕ, a node vj is removed from α in FIFO order and its potential parent list Wj=vi∣Li<Lj,vi∈Nj is constructed (lines 7-8). If vj has no potential parent, that is, Wj=ϕ, then the children of vj are added to α and considered for switching later (line 9). Otherwise, the node vx with the lowest path load is selected from Wj, and the path load σx′ on Px is estimated, σx′=max⁡γi′∣vi∈Px (lines 11-12). If σx′≥σd, vj is not switched to vx and the children of vj are added to α for subsequent consideration (line 13). Otherwise, vj will be switched to vx (line 15). If Lj is changed after switching, the level of each node in T(vj) is updated (line 16). Afterwards, γi and σi for each node are updated and flg is set to 1, which means that at least one descendant of vm has been switched (lines 17-18). Step  3 repeats until α is empty.Step 4.
Whenα becomes empty, the switching of the descendants of the bottleneck node vm is completed. If flg=0, there are no nodes switched, and SPAS terminates (line 22). Otherwise, the node vm with the highest load is selected again (line 23) for the next iteration.


### 4.3. DSAPS: A Distributed Version of SAPS

A distributed version of SAPS, called DSAPS, is developed in this section.SAPS terminates automatically when there is no node switched. However, in the distributed algorithm, transmitting and receiving the control messages may consume the energy of a node continually during the switching process. Thus, the load of a node will still increase continually while keeping the number of its descendants constant, which is not conducive for convergence of our algorithm. In order to improve the speed of convergence, a parameterDmax is used to control the number of iterations in DSAPS. Then, DSAPS terminates when there is no node switched or the number of iterations exceeds Dmax.In the distributed algorithm, downward path load is calculated at each node and forwarded to the sink; thus, the sink can pick out the maximum load in the network. The definition of downward path load is as follows.Definition 7 (downward path load).
The downward path load of a nodevj is the maximum load in T(vj) and can be denoted by σ^j. When vj is a leaf node, one has σ^j=γj. Otherwise, σ^j=max⁡γj,max⁡σ^k, where vk∈Cj.Similar to SAPS, DSAPS also starts with a random tree, which then proceeds with the following phases.Phase 1.
Each nodevi calculates its ni and σ^i from bottom to top. When vk is a leaf node, we have nk=1 and σ^k=γk. Then, vk transmits nk and σ^k to its parent vj in a DPLCollect message. After receiving these values from vk, vj stores them, and after receiving the DPLCollect messages from all of its children, vj computes its own nj, γj, and σ^j. Then, vj transmits a DPLCollect message embedded with nj and σ^j to its parent. This phase starts from the leaf nodes and ends in the sink.Phase 2.
Each node calculates its path load from top to bottom. The sink first broadcasts a PathLoadUpdate message to its children with its path loadσS (σS=0) embedded in it. When a node vj receives a PathLoadUpdate message from its parent vd, it stores σd and computes its own path load σj=max⁡γj,σd. Then, vj broadcasts a PathLoadUpdate message to its children with σj embedded in it. When a leaf node vl updates its path load, it sends an Ack message to its parent to confirm its completion of update. After receiving the Ack messages from all the children, vi sends an Ack message to its parent. The path loads of the entire tree have been updated when the sink receives the Ack messages from all its children.Phase 3.
The task of Phase3 is to find the bottleneck node with the highest load. First, the sink sends a Find message to its child va with the maximum downward path load σ^max. Then, va looks up its own load γa. If γa=σ^max, va is the bottleneck node. Otherwise, va finds the node vb with σ^b=σ^max in its downward path load table and sends the Find message to vb. The Find message will be routed repeatedly until the bottleneck node vm with γm=σ^max is found.Phase 4.
The task of this phase is to switch the descendants of the bottleneck node to the other subtrees for lowering the maximum load in the tree.Step 1.
The current node (initialized withvm) broadcasts a Switch message to its children. After a node vj receives the Switch message, it broadcasts a Request message embedded with its level Lj to its neighbors. If a neighbor vh satisfies Lh<Lj, it replies with a ReqAccept message with σh embedded in it. Otherwise, it replies with a ReqDeny message. Node vj adds the node that replies with a ReqAccept message to Wj, which will be established after vj receives messages from all its neighbors.Step 2.
IfWj=ϕ, vj does not switch, and it is elected as the current node to repeat Step  1. Otherwise, vj selects the node vx with the minimum path load from Wj and transmits a FindMXL message embedded with nj to it. This message is used to inform vx to estimate the path load σx′ on Px assuming vj has switched from its current parent vd to vx. After receiving the FindMXL message, vx estimates its own load γx′ and transmits the FindMXL message embedded with nj to its parent, and so on. When the level 1 node ve on Px receives the FindMXL message, it estimates γe′ and sets its estimated path load σe′=γe′. Then, ve transmits a FindMXLAck message embedded with σe′ to its child vc that transmits the FindMXL message to it. Then, vc calculates σc′=max{γc′,σe′} and forwards the FindMXLAck message down the tree. After receiving the FindMXLAck message, vx calculates σx′ and transmits it to vj. Then, vj compares σx′ with σd. If σx′≥σd, vj does not switch to vx and Step  1 is repeated starting with vj. Otherwise, vj switches to vx.Step 3.
The following operations should be done for switchingvj from vd to vx:(1)
Nodevj adds vd to the neighbor table and denotes vx as the new parent while deleting it from the neighbor table.(2)
Nodevj transmits a Join message to vx with nj and σ^j embedded in it. Then, vx moves vj from the neighbor table to the children table, stores σ^j and recomputes nx (nx+=nj), γx, and σ^x, and then transmits IDPLUpdate message to its parent vg with nj and σ^x embedded in it. When vg receives the IDPLUpdate message, it updates σ^x in the downward path load table and recomputes ng (ng+=nj), γg, and σ^g and then transmits nj and σ^g to its parent. This process repeats until the sink receives the IDPLUpdate message from a node vt at level 1. After updating σ^t in the downward path load table, the sink broadcasts LPLUpdate message down the subtree T(vt) for updating the path load and the level of each node in T(vt). The LPLUpdate message includes the path load and the level of the node that transmits it.(3)
Nodevj transmits a Leave message embedded with nj to vd. Then, vd moves vj from the children table to the neighbor table, deletes σ^j from the downward path load table and recomputes nd (nd-=nj), γd, and σ^d, and then transmits a DDPLUpdate message embedded with nj and σ^d to its parent vf. When receiving the DDPLUpdate message, vf updates σ^d in the downward path load table and recomputes nf (nf-=nj), γf, and σ^f and then transmits nj and σ^f to its parent. This process repeats until the sink receives the DDPLUpdate message from a node vp at level 1. After the sink updates σ^p, it broadcasts a PathLoadUpdate message down the subtree T(vp) for updating the path load of each node in T(vp). Note that a node transmits the PathLoadUpdate message to its children only when its path load changes.Step 4.
If a nodevn has switched, it will not transmit the Switch message to its children but will transmit a SwitchAck message to its parent with the value of its flag variable flg (flg=1) embedded in it. If vn has not switched, it transmits the SwitchAck message embedded with its flg to its parent after receiving the SwitchAck messages from all the children (if any node in T(vn) has switched, then vn has flg=1; else, vn has flg=0). When the bottleneck node vm receives the SwitchAck messages from all its children, it routs its SwitchAck messages upward to the sink.Phase 5.
When the sink receives the SwitchAck message, the switching of the descendants ofvm is completed. If flg received is 0, DSAPS terminates. Otherwise, the sink increases the variable count by 1 (count is zero-initialized). If count≤Dmax, Phase 3 is repeated. Otherwise, DSAPS terminates.


## 4.1. Design of the SAPS Algorithm

As mentioned in the last section, our goal is to minimize the highest load among all nodes, that is, to minimize the loadγm of the bottleneck node vm. According to formulae (1) and (4), we have(8)γm=rmem=m×nm-1×Er+m×nm×Etem=m×nm×Er+Et-m×Erem.It can be seen that the loadγm of the bottleneck node vm is proportional to the number of the nodes nm in the subtree rooted at vm, with given m, Er, Et, and em. Switching the descendants of vm to other subtrees can reduce nm, which decreases γm in turn.If nodevj is considered for switching in RaSMaLai, the potential parent list of vj is constructed as Wj=vi∣vi∈Nj,σj-σi>δ. If vj is decided to switch, a node is chosen randomly with uniform probability from Wj to be the new parent for vj, without considering the level of the new parent in the tree. Thus, a node whose level is greater than that of vj may be chosen as the new parent of vj, which may increase the level of the data collection tree. And the number of hops from some of the nodes to the sink will be increased, which will result in higher delay and more energy consumption in each data collection round.Furthermore, after switchingvj from the old parent vd to the new parent vx in RaSMaLai, the highest load on the path Pd decreases indeed, but the highest load on Px will increase, sometimes even exceeding that on Pd before switching. Thus, the highest load in the tree may be higher than before, which is not helpful for enhancing the network lifetime. All in all, some switching is counterproductive which leads to more iterations and slower convergence.To overcome these problems, the level of the data collection tree is taken into account in our SAPS algorithm. Whenvj is considered for switching, only the neighbors whose level is less than that of vj will be added to the potential parent list Wj (Wj=vi∣Li<Lj,vi∈Nj). Thus, the level of the tree will not increase after switching. Then, the node vx with the minimum path load in Wj will be chosen as the new parent of vj. Thus, the highest load on Px after switching vj to vx may not exceed that on Pd before switching vj from vd in most cases.In some particular cases, the highest load onPx after switching will be higher than that on Pd before switching. To overcome this problem, SAPS estimates the path load σx′ on Px assuming vj has been switched from vd to vx, which is σx′=max⁡γx′∣vi∈Px. If σx′≥σd, vj is not switched to vx because the highest load on Px after switching will exceed that on Pd before switching, which is not conducive to decreasing the maximum load in the network. Otherwise, vj will be switched to vx. Such prediction strategy ensures that every switching will lower the highest load in the network, which makes SAPS converge faster than other existing schemes.In addition, no parameter is needed to control the maximum number of iterations in SAPS, which is different from RaSMaLai. SAPS terminates automatically when there is no node switched, which means the algorithm is converged.


## 4.2. Details of the SAPS Algorithm

SAPS starts with a random shortest path tree, and the pseudocode is shown in Algorithm1. All the major symbols used in the algorithm are given as follows:V: the set of all nodes in a WSN.Lj: the level of vj.Cj: the set of children of vj.Nj: the set of neighbors of vj.T(vj): the subtree rooted at vj.γi: the load of vi.Px: the path from vx to the sink.σi: the path load of vi.Wj: the potential parent list of vj.γi′: the estimated load of vi on Px assuming some node has been switched to vx.σx′: the estimated path load of vx assuming some node has been switched to vx.Algorithm 1:SAPS.
(1)    Calculate γi and σi for each node vi∈V;
(2)    Select the node vm with the highest load;
(3)    while (true)
(4)     flg←0;
(5)       queue α←Cm;
(6)       while (α≠ϕ)
(7)      Remove node vj from the head of the queue α;
(8)        Wj ← any node in Nj whose level is less than Lj;
(9)        if (Wj=ϕ) α←Cj;
(10)     else
(11)      Select the node vx with the lowest path load from Wj;
(12)      Estimate the path load σx′ on Px assuming vj has been switched from vd to vx;
(13)      if (σx′≥σd) α←Cj;
(14)      else
(15)       Switch vj to vx;
(16)       If Lj is changed, then update the level of each node in T(vj);
(17)       Update γi and σi for each node vi∈V;
(18)       flg←1;
(19)
(20)
(21)
(22)  if (flg  ==  0) return;
(23)  else  Select the node vm with the highest load again;
(24)The details of the SAPS algorithm are described as follows.Step 1.
First, the loadγi for each node vi in the tree is initialized from bottom to top. Then, the path load σi for each node is initialized from top to bottom (line 1). After that, the bottleneck node vm with the highest load is selected (line 2).Step 2.
The flag variableflg is zero-initialized, which means that no descendant of vm has been switched (line 4). Then, the children of vm are inserted into the queue α (line 5).Step 3.
Ifα≠ϕ, a node vj is removed from α in FIFO order and its potential parent list Wj=vi∣Li<Lj,vi∈Nj is constructed (lines 7-8). If vj has no potential parent, that is, Wj=ϕ, then the children of vj are added to α and considered for switching later (line 9). Otherwise, the node vx with the lowest path load is selected from Wj, and the path load σx′ on Px is estimated, σx′=max⁡γi′∣vi∈Px (lines 11-12). If σx′≥σd, vj is not switched to vx and the children of vj are added to α for subsequent consideration (line 13). Otherwise, vj will be switched to vx (line 15). If Lj is changed after switching, the level of each node in T(vj) is updated (line 16). Afterwards, γi and σi for each node are updated and flg is set to 1, which means that at least one descendant of vm has been switched (lines 17-18). Step  3 repeats until α is empty.Step 4.
Whenα becomes empty, the switching of the descendants of the bottleneck node vm is completed. If flg=0, there are no nodes switched, and SPAS terminates (line 22). Otherwise, the node vm with the highest load is selected again (line 23) for the next iteration.


## 4.3. DSAPS: A Distributed Version of SAPS

A distributed version of SAPS, called DSAPS, is developed in this section.SAPS terminates automatically when there is no node switched. However, in the distributed algorithm, transmitting and receiving the control messages may consume the energy of a node continually during the switching process. Thus, the load of a node will still increase continually while keeping the number of its descendants constant, which is not conducive for convergence of our algorithm. In order to improve the speed of convergence, a parameterDmax is used to control the number of iterations in DSAPS. Then, DSAPS terminates when there is no node switched or the number of iterations exceeds Dmax.In the distributed algorithm, downward path load is calculated at each node and forwarded to the sink; thus, the sink can pick out the maximum load in the network. The definition of downward path load is as follows.Definition 7 (downward path load).
The downward path load of a nodevj is the maximum load in T(vj) and can be denoted by σ^j. When vj is a leaf node, one has σ^j=γj. Otherwise, σ^j=max⁡γj,max⁡σ^k, where vk∈Cj.Similar to SAPS, DSAPS also starts with a random tree, which then proceeds with the following phases.Phase 1.
Each nodevi calculates its ni and σ^i from bottom to top. When vk is a leaf node, we have nk=1 and σ^k=γk. Then, vk transmits nk and σ^k to its parent vj in a DPLCollect message. After receiving these values from vk, vj stores them, and after receiving the DPLCollect messages from all of its children, vj computes its own nj, γj, and σ^j. Then, vj transmits a DPLCollect message embedded with nj and σ^j to its parent. This phase starts from the leaf nodes and ends in the sink.Phase 2.
Each node calculates its path load from top to bottom. The sink first broadcasts a PathLoadUpdate message to its children with its path loadσS (σS=0) embedded in it. When a node vj receives a PathLoadUpdate message from its parent vd, it stores σd and computes its own path load σj=max⁡γj,σd. Then, vj broadcasts a PathLoadUpdate message to its children with σj embedded in it. When a leaf node vl updates its path load, it sends an Ack message to its parent to confirm its completion of update. After receiving the Ack messages from all the children, vi sends an Ack message to its parent. The path loads of the entire tree have been updated when the sink receives the Ack messages from all its children.Phase 3.
The task of Phase3 is to find the bottleneck node with the highest load. First, the sink sends a Find message to its child va with the maximum downward path load σ^max. Then, va looks up its own load γa. If γa=σ^max, va is the bottleneck node. Otherwise, va finds the node vb with σ^b=σ^max in its downward path load table and sends the Find message to vb. The Find message will be routed repeatedly until the bottleneck node vm with γm=σ^max is found.Phase 4.
The task of this phase is to switch the descendants of the bottleneck node to the other subtrees for lowering the maximum load in the tree.Step 1.
The current node (initialized withvm) broadcasts a Switch message to its children. After a node vj receives the Switch message, it broadcasts a Request message embedded with its level Lj to its neighbors. If a neighbor vh satisfies Lh<Lj, it replies with a ReqAccept message with σh embedded in it. Otherwise, it replies with a ReqDeny message. Node vj adds the node that replies with a ReqAccept message to Wj, which will be established after vj receives messages from all its neighbors.Step 2.
IfWj=ϕ, vj does not switch, and it is elected as the current node to repeat Step  1. Otherwise, vj selects the node vx with the minimum path load from Wj and transmits a FindMXL message embedded with nj to it. This message is used to inform vx to estimate the path load σx′ on Px assuming vj has switched from its current parent vd to vx. After receiving the FindMXL message, vx estimates its own load γx′ and transmits the FindMXL message embedded with nj to its parent, and so on. When the level 1 node ve on Px receives the FindMXL message, it estimates γe′ and sets its estimated path load σe′=γe′. Then, ve transmits a FindMXLAck message embedded with σe′ to its child vc that transmits the FindMXL message to it. Then, vc calculates σc′=max{γc′,σe′} and forwards the FindMXLAck message down the tree. After receiving the FindMXLAck message, vx calculates σx′ and transmits it to vj. Then, vj compares σx′ with σd. If σx′≥σd, vj does not switch to vx and Step  1 is repeated starting with vj. Otherwise, vj switches to vx.Step 3.
The following operations should be done for switchingvj from vd to vx:(1)
Nodevj adds vd to the neighbor table and denotes vx as the new parent while deleting it from the neighbor table.(2)
Nodevj transmits a Join message to vx with nj and σ^j embedded in it. Then, vx moves vj from the neighbor table to the children table, stores σ^j and recomputes nx (nx+=nj), γx, and σ^x, and then transmits IDPLUpdate message to its parent vg with nj and σ^x embedded in it. When vg receives the IDPLUpdate message, it updates σ^x in the downward path load table and recomputes ng (ng+=nj), γg, and σ^g and then transmits nj and σ^g to its parent. This process repeats until the sink receives the IDPLUpdate message from a node vt at level 1. After updating σ^t in the downward path load table, the sink broadcasts LPLUpdate message down the subtree T(vt) for updating the path load and the level of each node in T(vt). The LPLUpdate message includes the path load and the level of the node that transmits it.(3)
Nodevj transmits a Leave message embedded with nj to vd. Then, vd moves vj from the children table to the neighbor table, deletes σ^j from the downward path load table and recomputes nd (nd-=nj), γd, and σ^d, and then transmits a DDPLUpdate message embedded with nj and σ^d to its parent vf. When receiving the DDPLUpdate message, vf updates σ^d in the downward path load table and recomputes nf (nf-=nj), γf, and σ^f and then transmits nj and σ^f to its parent. This process repeats until the sink receives the DDPLUpdate message from a node vp at level 1. After the sink updates σ^p, it broadcasts a PathLoadUpdate message down the subtree T(vp) for updating the path load of each node in T(vp). Note that a node transmits the PathLoadUpdate message to its children only when its path load changes.Step 4.
If a nodevn has switched, it will not transmit the Switch message to its children but will transmit a SwitchAck message to its parent with the value of its flag variable flg (flg=1) embedded in it. If vn has not switched, it transmits the SwitchAck message embedded with its flg to its parent after receiving the SwitchAck messages from all the children (if any node in T(vn) has switched, then vn has flg=1; else, vn has flg=0). When the bottleneck node vm receives the SwitchAck messages from all its children, it routs its SwitchAck messages upward to the sink.Phase 5.
When the sink receives the SwitchAck message, the switching of the descendants ofvm is completed. If flg received is 0, DSAPS terminates. Otherwise, the sink increases the variable count by 1 (count is zero-initialized). If count≤Dmax, Phase 3 is repeated. Otherwise, DSAPS terminates.


## 5. Performance Evaluation

For comparing the performances of SAPS, DSAPS, RaSMaLai, and D-RaSMaLai, we conducted extensive simulations of these algorithms based on the WSN simulator in [20]. The sensor nodes were randomly placed in a square area of 100m×100m, and the number of sensors was varied from 100 to 400 with the step size of 50. The radio transmission range was set to 25 m and the initial energy of each node was randomly generated between 0.5 and 1 joule (J). The energy loss of receiving a message was set to Er=50 nJ/bit and the energy loss of transmitting a message was set to Et=100 nJ/bit. We assumed that the size of data messages generated by each node in each round was 16 bytes, and the size of control messages was 10 bytes. Each data point of simulation was averaged over 200 runs.We carried out our simulations in two different scenarios. In Scenario 1, the sink was placed at the center of the field with coordinate (50 m, 50 m). In Scenario 2, the sink was placed at the edge with coordinate (100 m, 50 m). We then evaluated the following metrics:(i)
Lifetime, measured as the number of data collection rounds until the first node runs out of energy.(ii)
Number of iterations required for convergence.(iii)
Maximum level of the data collection tree after switching.(iv)
Energy expenditure for data collection in each round.(v)
Energy expenditure for switching, measured as the amount of energy spent to transmit and receive the control messages in DSAPS and D-RaSMaLai. Note that a node receives messages within its hearing distance even if it is not the intended recipient, which also causes energy loss for receiving these irrelevant messages.


### 5.1. Setup of Control Parameters

SAPS does not have any control parameters, while DSAPS has a parameterDmax which denotes the maximum number of iterations. To explore the impact of Dmax on the performance of DSAPS, we carried out multiple simulation experiments on different networks in Scenarios 1 and 2 for DSAPS. In each experiment, Dmax varied from 10 to 490 with the step size of 40. Through these experiments, we find that DSAPS achieves better results when Dmax=50. Figure 2 shows the averaged experimental results of DSAPS in 200 networks of 100 nodes in Scenario 1, including lifetime, number of iterations, and energy expenditure for switching. Since the experimental results of maximum level of the routing tree and energy expenditure for data collection in each round are the same when Dmax varied from 10 to 490, they are not shown in this figure. In order to make the data points nonoverlapping in Figure 2, after being scaled between 0 and 1, the data points of lifetime were moved 2 units up along the vertical axis while the data points of iterations were moved 1 unit up. We observe that, for Dmax=50, the number of iterations and energy expenditure for switching are higher than those for Dmax=10, but the lifetime is also higher. However, bigger Dmax does not necessarily mean higher lifetime, because as Dmax increases, the number of iterations increases too, which results in the increase of the energy expenditure for transmitting and receiving the control messages; thus the nodal lifetime decreases. When Dmax>50, the lifetime is a few rounds less than that for Dmax=50 while the other experimental results are also worse, as shown in Figure 2. We will not show the experimental results for Scenario 2, due to lack of space. Finally, we set Dmax=50 for DSAPS in both scenarios.Figure 2
Impact ofDmax.RaSMaLai has two control parameters which dominate the performance of RaSMaLai:δ, the maximum allowable difference among the path loads of leaf nodes, and βmax, the maximum number of times an individual node can be selected for switching. D-RaSMaLai also has two control parameters. One is δ, the same as δ in RaSMaLai, and the other is the maximum number of times the sink can send the Find messages, which is denoted by dβmax here to differentiate from βmax in RaSMaLai.For different networks, the optimum values ofδ, βmax, and dβmax for achieving maximum lifetime should be different. In order to make RaSMaLai and D-RaSMaLai achieve the optimal experimental results, we conducted many simulation experiments, in which δ was varied in the ranges 3–7 and 9–25 for Scenarios 1 and 2, respectively, with the step size of 0.5, and βmax and dβmax were varied in the ranges 50–2050 and 50–950, respectively, for both Scenarios, with the step size of 100. The parameter values that made RaSMaLai and D-RaSMaLai achieve the average maximum lifetime in the simulation are shown in Table 1. We observe that the value of dβmax is much smaller than that of βmax. This is because, for D-RaSMaLai, the greater the value of dβmax, the more the iterations, the higher the energy expenditure for transmitting and receiving the control messages, and the lower the lifetime. So it is better to choose a smaller value for dβmax.Table 1
Parameter settings for RaSMaLai and D-RaSMaLai.
Scenario
Algorithm
Parameter
Number of nodes
100
150
200
250
300
350
400
1
RaSMaLai
β
m
a
x
1450
1350
1650
1950
1450
1450
1350
δ
3
3.5
4
4
4
4.5
4.5
D-RaSMaLai
d
β
m
a
x
250
150
350
250
250
250
250
δ
3.5
5
5
5.5
6
6.5
7
2
RaSMaLai
β
m
a
x
1650
1850
1650
1550
1650
1650
1350
δ
8.5
8.5
9.5
11
12.5
13.5
12.5
D-RaSMaLai
d
β
m
a
x
150
250
250
250
150
150
150
δ
10.5
12
13.5
15.5
19
22.5
21


### 5.2. Performance Analysis and Discussions

The experimental results discussed in this subsection were obtained using the parameters in Section5.1.


#### 5.2.1. Network Lifetime

The experimental results on the lifetime are shown in Figures3(a) and 3(b) for Scenarios 1 and 2, respectively. We observe that SAPS has the highest lifetime in both scenarios. The lifetime of DSAPS is slightly less than that of SAPS because of the energy expenditure for switching but is greater than that of RaSMaLai, and D-RaSMaLai achieves the minimum lifetime.Figure 3
(a) Lifetime in Scenario 1. (b) Lifetime in Scenario 2.
(a)
(b)As shown in Figure3, the lifetimes of SAPS, DSAPS, and RaSMaLai tend to increase in Scenario 1 as the network size increases, which is opposite to the trend in Scenario 2. This is because in Scenario 1 in which the sink is placed at the center of the field, as the network size increases, the distribution of nodes in the network becomes more uniform, which is conducive to load balance. Thus, the lifetime increases efficiently after switching, which is even higher than that of the smaller network. But this is not the case in Scenario 2 in which the sink is on the border. This is because, as the network size increases, the loads of the nodes near the sink become higher even after switching, although the distribution of nodes in the network becomes more uniform. Thus, the lifetime decreases. Figure 3 also shows that the lifetime of D-RaSMaLai tends to decrease in both scenarios as the network size increases. This is because, as the network size increases, D-RaSMaLai tries to save the energy expenditure for switching by reducing the number of iterations or increasing the value of δ, both of which reduce the effect of load balance. Thus, the lifetime decreases.


#### 5.2.2. Number of Iterations

The experimental results on the number of iterations are shown in Table2 for both scenarios. We can see that the numbers of iterations of SAPS and DSAPS are much less than those of RaSMaLai and D-RaSMaLai. With fewer iterations, the lifetimes of the routing trees produced by RaSMaLai and D-RaSMaLai are lower. Figures 4(a) and 4(b) show the results on the lifetime of the routing trees produced after 5 iterations and 10 iterations, respectively, for Scenario 2. We observe that, under the condition of the same number of iterations, the lifetimes of SAPS and DSAPS are about 30 to 180 percent higher than those of RaSMaLai and D-RaSMaLai. Similar results were obtained also for Scenario 1, but we do not report them here due to lack of space. In conclusion, RaSMaLai and D-RaSMaLai need more iterations to achieve higher lifetime. However, SAPS and DSAPS can achieve maximum lifetime just after several iterations.Table 2
Iterations of each algorithm.
Scenario
Algorithm
Number of nodes
100
150
200
250
300
350
400
1
SAPS
8.7
12.4
15.1
18.0
19.8
22.9
24.9
DSAPS
9.9
12.4
15.2
18.0
19.9
22.6
25.1
RaSMaLai
1924.3
2536.8
2978.5
4834.6
5678.7
3796.5
4519.6
D-RaSMaLai
247.7
150
350
250
250
250
250
2
SAPS
7.0
10.8
13.3
16.2
19.0
20.4
21.7
DSAPS
15.8
16.2
17.7
21.6
23.4
24.2
27.1
RaSMaLai
1832.8
2890.0
3131.9
2923.2
2969.4
3063.7
4727.9
D-RaSMaLai
134.5
238.9
246.6
249.0
149.3
149.5
150Figure 4
Lifetime in Scenario 2: (a) after 5 iterations and (b) after 10 iterations.
(a)
(b)


#### 5.2.3. Maximum Level of the Routing Tree after Switching

Figures5(a) and 5(b) show the results on the maximum level of the routing tree after switching for Scenarios 1 and 2, respectively. The maximum levels of the routing trees produced by SAPS and DSAPS are the same as that of the random shortest path tree before switching in both scenarios. However, the maximum levels of the routing trees produced by RaSMaLai and D-RaSMaLai are increased obviously and are over 2 times greater than those of SAPS and DSAPS in most cases, which result in longer delays and more energy expenditure for data collection in each round.Figure 5
(a) Maximum level in Scenario 1. (b) Maximum level in Scenario 2.
(a)
(b)


#### 5.2.4. Energy Expenditure for Switching

In DSAPS and D-RaSMaLai, the energy of each node is spent continually for transmitting and receiving the control messages during the switching process. The results on the energy expenditure for switching of DSAPS and D-RaSMaLai are shown in Figure6. We observe that, as the number of nodes increases, the energy expenditure for switching of DSAPS does not increase as much as that of D-RaSMaLai in both scenarios, and DSAPS achieves lower energy expenditure for switching than D-RaSMaLai, which benefits from fewer iterations and shorter routing trees. Figure 6 also shows that the energy expenditure for switching in Scenario 1 is lower than that in Scenario 2 for both DSAPS and D-RaSMaLai. This is because the sink is on the border in Scenario 2 which results in higher routing tree (as shown in Figure 5); thus, some control messages are relayed by more hops.Figure 6
Energy expenditure for switching in the two scenarios.


#### 5.2.5. Energy Expenditure for Data Collection in Each Round

The results on the energy expenditure for data collection in each round are shown in Figures7(a) and 7(b) for Scenarios 1 and 2, respectively. We observe that, in both scenarios, as the number of nodes increases, the energy expenditure values in each round of SAPS and DSAPS do not increase as much as those of RaSMaLai and D-RaSMaLai. Figure 6 also shows that the energy expenditure value of SAPS is equal to that of DSAPS and less than those of RaSMaLai and D-RaSMaLai in both scenarios. RaSMaLai has the highest energy expenditure in each round for both scenarios because the routing tree produced by RaSMaLai is the highest (as shown in Figure 5).Figure 7
Energy expenditure for data collection in each round: (a) in Scenario 1 and (b) in Scenario 2.
(a)
(b)


## 5.1. Setup of Control Parameters

SAPS does not have any control parameters, while DSAPS has a parameterDmax which denotes the maximum number of iterations. To explore the impact of Dmax on the performance of DSAPS, we carried out multiple simulation experiments on different networks in Scenarios 1 and 2 for DSAPS. In each experiment, Dmax varied from 10 to 490 with the step size of 40. Through these experiments, we find that DSAPS achieves better results when Dmax=50. Figure 2 shows the averaged experimental results of DSAPS in 200 networks of 100 nodes in Scenario 1, including lifetime, number of iterations, and energy expenditure for switching. Since the experimental results of maximum level of the routing tree and energy expenditure for data collection in each round are the same when Dmax varied from 10 to 490, they are not shown in this figure. In order to make the data points nonoverlapping in Figure 2, after being scaled between 0 and 1, the data points of lifetime were moved 2 units up along the vertical axis while the data points of iterations were moved 1 unit up. We observe that, for Dmax=50, the number of iterations and energy expenditure for switching are higher than those for Dmax=10, but the lifetime is also higher. However, bigger Dmax does not necessarily mean higher lifetime, because as Dmax increases, the number of iterations increases too, which results in the increase of the energy expenditure for transmitting and receiving the control messages; thus the nodal lifetime decreases. When Dmax>50, the lifetime is a few rounds less than that for Dmax=50 while the other experimental results are also worse, as shown in Figure 2. We will not show the experimental results for Scenario 2, due to lack of space. Finally, we set Dmax=50 for DSAPS in both scenarios.Figure 2
Impact ofDmax.RaSMaLai has two control parameters which dominate the performance of RaSMaLai:δ, the maximum allowable difference among the path loads of leaf nodes, and βmax, the maximum number of times an individual node can be selected for switching. D-RaSMaLai also has two control parameters. One is δ, the same as δ in RaSMaLai, and the other is the maximum number of times the sink can send the Find messages, which is denoted by dβmax here to differentiate from βmax in RaSMaLai.For different networks, the optimum values ofδ, βmax, and dβmax for achieving maximum lifetime should be different. In order to make RaSMaLai and D-RaSMaLai achieve the optimal experimental results, we conducted many simulation experiments, in which δ was varied in the ranges 3–7 and 9–25 for Scenarios 1 and 2, respectively, with the step size of 0.5, and βmax and dβmax were varied in the ranges 50–2050 and 50–950, respectively, for both Scenarios, with the step size of 100. The parameter values that made RaSMaLai and D-RaSMaLai achieve the average maximum lifetime in the simulation are shown in Table 1. We observe that the value of dβmax is much smaller than that of βmax. This is because, for D-RaSMaLai, the greater the value of dβmax, the more the iterations, the higher the energy expenditure for transmitting and receiving the control messages, and the lower the lifetime. So it is better to choose a smaller value for dβmax.Table 1
Parameter settings for RaSMaLai and D-RaSMaLai.
Scenario
Algorithm
Parameter
Number of nodes
100
150
200
250
300
350
400
1
RaSMaLai
β
m
a
x
1450
1350
1650
1950
1450
1450
1350
δ
3
3.5
4
4
4
4.5
4.5
D-RaSMaLai
d
β
m
a
x
250
150
350
250
250
250
250
δ
3.5
5
5
5.5
6
6.5
7
2
RaSMaLai
β
m
a
x
1650
1850
1650
1550
1650
1650
1350
δ
8.5
8.5
9.5
11
12.5
13.5
12.5
D-RaSMaLai
d
β
m
a
x
150
250
250
250
150
150
150
δ
10.5
12
13.5
15.5
19
22.5
21


## 5.2. Performance Analysis and Discussions

The experimental results discussed in this subsection were obtained using the parameters in Section5.1.


### 5.2.1. Network Lifetime

The experimental results on the lifetime are shown in Figures3(a) and 3(b) for Scenarios 1 and 2, respectively. We observe that SAPS has the highest lifetime in both scenarios. The lifetime of DSAPS is slightly less than that of SAPS because of the energy expenditure for switching but is greater than that of RaSMaLai, and D-RaSMaLai achieves the minimum lifetime.Figure 3
(a) Lifetime in Scenario 1. (b) Lifetime in Scenario 2.
(a)
(b)As shown in Figure3, the lifetimes of SAPS, DSAPS, and RaSMaLai tend to increase in Scenario 1 as the network size increases, which is opposite to the trend in Scenario 2. This is because in Scenario 1 in which the sink is placed at the center of the field, as the network size increases, the distribution of nodes in the network becomes more uniform, which is conducive to load balance. Thus, the lifetime increases efficiently after switching, which is even higher than that of the smaller network. But this is not the case in Scenario 2 in which the sink is on the border. This is because, as the network size increases, the loads of the nodes near the sink become higher even after switching, although the distribution of nodes in the network becomes more uniform. Thus, the lifetime decreases. Figure 3 also shows that the lifetime of D-RaSMaLai tends to decrease in both scenarios as the network size increases. This is because, as the network size increases, D-RaSMaLai tries to save the energy expenditure for switching by reducing the number of iterations or increasing the value of δ, both of which reduce the effect of load balance. Thus, the lifetime decreases.


### 5.2.2. Number of Iterations

The experimental results on the number of iterations are shown in Table2 for both scenarios. We can see that the numbers of iterations of SAPS and DSAPS are much less than those of RaSMaLai and D-RaSMaLai. With fewer iterations, the lifetimes of the routing trees produced by RaSMaLai and D-RaSMaLai are lower. Figures 4(a) and 4(b) show the results on the lifetime of the routing trees produced after 5 iterations and 10 iterations, respectively, for Scenario 2. We observe that, under the condition of the same number of iterations, the lifetimes of SAPS and DSAPS are about 30 to 180 percent higher than those of RaSMaLai and D-RaSMaLai. Similar results were obtained also for Scenario 1, but we do not report them here due to lack of space. In conclusion, RaSMaLai and D-RaSMaLai need more iterations to achieve higher lifetime. However, SAPS and DSAPS can achieve maximum lifetime just after several iterations.Table 2
Iterations of each algorithm.
Scenario
Algorithm
Number of nodes
100
150
200
250
300
350
400
1
SAPS
8.7
12.4
15.1
18.0
19.8
22.9
24.9
DSAPS
9.9
12.4
15.2
18.0
19.9
22.6
25.1
RaSMaLai
1924.3
2536.8
2978.5
4834.6
5678.7
3796.5
4519.6
D-RaSMaLai
247.7
150
350
250
250
250
250
2
SAPS
7.0
10.8
13.3
16.2
19.0
20.4
21.7
DSAPS
15.8
16.2
17.7
21.6
23.4
24.2
27.1
RaSMaLai
1832.8
2890.0
3131.9
2923.2
2969.4
3063.7
4727.9
D-RaSMaLai
134.5
238.9
246.6
249.0
149.3
149.5
150Figure 4
Lifetime in Scenario 2: (a) after 5 iterations and (b) after 10 iterations.
(a)
(b)


### 5.2.3. Maximum Level of the Routing Tree after Switching

Figures5(a) and 5(b) show the results on the maximum level of the routing tree after switching for Scenarios 1 and 2, respectively. The maximum levels of the routing trees produced by SAPS and DSAPS are the same as that of the random shortest path tree before switching in both scenarios. However, the maximum levels of the routing trees produced by RaSMaLai and D-RaSMaLai are increased obviously and are over 2 times greater than those of SAPS and DSAPS in most cases, which result in longer delays and more energy expenditure for data collection in each round.Figure 5
(a) Maximum level in Scenario 1. (b) Maximum level in Scenario 2.
(a)
(b)


### 5.2.4. Energy Expenditure for Switching

In DSAPS and D-RaSMaLai, the energy of each node is spent continually for transmitting and receiving the control messages during the switching process. The results on the energy expenditure for switching of DSAPS and D-RaSMaLai are shown in Figure6. We observe that, as the number of nodes increases, the energy expenditure for switching of DSAPS does not increase as much as that of D-RaSMaLai in both scenarios, and DSAPS achieves lower energy expenditure for switching than D-RaSMaLai, which benefits from fewer iterations and shorter routing trees. Figure 6 also shows that the energy expenditure for switching in Scenario 1 is lower than that in Scenario 2 for both DSAPS and D-RaSMaLai. This is because the sink is on the border in Scenario 2 which results in higher routing tree (as shown in Figure 5); thus, some control messages are relayed by more hops.Figure 6
Energy expenditure for switching in the two scenarios.


### 5.2.5. Energy Expenditure for Data Collection in Each Round

The results on the energy expenditure for data collection in each round are shown in Figures7(a) and 7(b) for Scenarios 1 and 2, respectively. We observe that, in both scenarios, as the number of nodes increases, the energy expenditure values in each round of SAPS and DSAPS do not increase as much as those of RaSMaLai and D-RaSMaLai. Figure 6 also shows that the energy expenditure value of SAPS is equal to that of DSAPS and less than those of RaSMaLai and D-RaSMaLai in both scenarios. RaSMaLai has the highest energy expenditure in each round for both scenarios because the routing tree produced by RaSMaLai is the highest (as shown in Figure 5).Figure 7
Energy expenditure for data collection in each round: (a) in Scenario 1 and (b) in Scenario 2.
(a)
(b)


## 5.2.1. Network Lifetime

The experimental results on the lifetime are shown in Figures3(a) and 3(b) for Scenarios 1 and 2, respectively. We observe that SAPS has the highest lifetime in both scenarios. The lifetime of DSAPS is slightly less than that of SAPS because of the energy expenditure for switching but is greater than that of RaSMaLai, and D-RaSMaLai achieves the minimum lifetime.Figure 3
(a) Lifetime in Scenario 1. (b) Lifetime in Scenario 2.
(a)
(b)As shown in Figure3, the lifetimes of SAPS, DSAPS, and RaSMaLai tend to increase in Scenario 1 as the network size increases, which is opposite to the trend in Scenario 2. This is because in Scenario 1 in which the sink is placed at the center of the field, as the network size increases, the distribution of nodes in the network becomes more uniform, which is conducive to load balance. Thus, the lifetime increases efficiently after switching, which is even higher than that of the smaller network. But this is not the case in Scenario 2 in which the sink is on the border. This is because, as the network size increases, the loads of the nodes near the sink become higher even after switching, although the distribution of nodes in the network becomes more uniform. Thus, the lifetime decreases. Figure 3 also shows that the lifetime of D-RaSMaLai tends to decrease in both scenarios as the network size increases. This is because, as the network size increases, D-RaSMaLai tries to save the energy expenditure for switching by reducing the number of iterations or increasing the value of δ, both of which reduce the effect of load balance. Thus, the lifetime decreases.


## 5.2.2. Number of Iterations

The experimental results on the number of iterations are shown in Table2 for both scenarios. We can see that the numbers of iterations of SAPS and DSAPS are much less than those of RaSMaLai and D-RaSMaLai. With fewer iterations, the lifetimes of the routing trees produced by RaSMaLai and D-RaSMaLai are lower. Figures 4(a) and 4(b) show the results on the lifetime of the routing trees produced after 5 iterations and 10 iterations, respectively, for Scenario 2. We observe that, under the condition of the same number of iterations, the lifetimes of SAPS and DSAPS are about 30 to 180 percent higher than those of RaSMaLai and D-RaSMaLai. Similar results were obtained also for Scenario 1, but we do not report them here due to lack of space. In conclusion, RaSMaLai and D-RaSMaLai need more iterations to achieve higher lifetime. However, SAPS and DSAPS can achieve maximum lifetime just after several iterations.Table 2
Iterations of each algorithm.
Scenario
Algorithm
Number of nodes
100
150
200
250
300
350
400
1
SAPS
8.7
12.4
15.1
18.0
19.8
22.9
24.9
DSAPS
9.9
12.4
15.2
18.0
19.9
22.6
25.1
RaSMaLai
1924.3
2536.8
2978.5
4834.6
5678.7
3796.5
4519.6
D-RaSMaLai
247.7
150
350
250
250
250
250
2
SAPS
7.0
10.8
13.3
16.2
19.0
20.4
21.7
DSAPS
15.8
16.2
17.7
21.6
23.4
24.2
27.1
RaSMaLai
1832.8
2890.0
3131.9
2923.2
2969.4
3063.7
4727.9
D-RaSMaLai
134.5
238.9
246.6
249.0
149.3
149.5
150Figure 4
Lifetime in Scenario 2: (a) after 5 iterations and (b) after 10 iterations.
(a)
(b)


## 5.2.3. Maximum Level of the Routing Tree after Switching

Figures5(a) and 5(b) show the results on the maximum level of the routing tree after switching for Scenarios 1 and 2, respectively. The maximum levels of the routing trees produced by SAPS and DSAPS are the same as that of the random shortest path tree before switching in both scenarios. However, the maximum levels of the routing trees produced by RaSMaLai and D-RaSMaLai are increased obviously and are over 2 times greater than those of SAPS and DSAPS in most cases, which result in longer delays and more energy expenditure for data collection in each round.Figure 5
(a) Maximum level in Scenario 1. (b) Maximum level in Scenario 2.
(a)
(b)


## 5.2.4. Energy Expenditure for Switching

In DSAPS and D-RaSMaLai, the energy of each node is spent continually for transmitting and receiving the control messages during the switching process. The results on the energy expenditure for switching of DSAPS and D-RaSMaLai are shown in Figure6. We observe that, as the number of nodes increases, the energy expenditure for switching of DSAPS does not increase as much as that of D-RaSMaLai in both scenarios, and DSAPS achieves lower energy expenditure for switching than D-RaSMaLai, which benefits from fewer iterations and shorter routing trees. Figure 6 also shows that the energy expenditure for switching in Scenario 1 is lower than that in Scenario 2 for both DSAPS and D-RaSMaLai. This is because the sink is on the border in Scenario 2 which results in higher routing tree (as shown in Figure 5); thus, some control messages are relayed by more hops.Figure 6
Energy expenditure for switching in the two scenarios.


## 5.2.5. Energy Expenditure for Data Collection in Each Round

The results on the energy expenditure for data collection in each round are shown in Figures7(a) and 7(b) for Scenarios 1 and 2, respectively. We observe that, in both scenarios, as the number of nodes increases, the energy expenditure values in each round of SAPS and DSAPS do not increase as much as those of RaSMaLai and D-RaSMaLai. Figure 6 also shows that the energy expenditure value of SAPS is equal to that of DSAPS and less than those of RaSMaLai and D-RaSMaLai in both scenarios. RaSMaLai has the highest energy expenditure in each round for both scenarios because the routing tree produced by RaSMaLai is the highest (as shown in Figure 5).Figure 7
Energy expenditure for data collection in each round: (a) in Scenario 1 and (b) in Scenario 2.
(a)
(b)


## 6. Conclusion

In this paper, we presented an efficient switching algorithm with prediction strategy, called SAPS, which maximizes the network lifetime by means of load balancing. When a node is considered for switching, the neighbor with lower level and minimum path load is chosen as the new parent. A prediction strategy is then provided to make sure that each switching lowers the maximum load in the tree, which results in faster convergence of the algorithm. A distributed version of SAPS is also implemented, called DSAPS. The simulation results indicate that our approaches can produce the shortest path trees with higher lifetime after fewer iterations, and they consume less energy for switching and data collection in each round.



---

*Source: 592093-2015-11-10.xml*