Sage Journals: Discover world-class research

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.

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. Section 2 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 with n sensor nodes $v_{1}, \dots, v_{n}$ and a sink node S, randomly placed within a square area of $Q \times Q$ . We model the topology of the WSN by an undirected graph $G = (V, E)$ , where $V = {S, v_{1}, \dots, v_{n}}$ 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 tree T 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 $L_{S}$ ( $L_{S} = 0$ ), asking sensor nodes to organize into a routing tree. After a node $v_{i}$ without an assigned level hears this message, it assigns its own level $L_{i}$ to be the level in the message plus one and chooses the sender of the message as its parent. Then, $v_{i}$ rebroadcasts the routing message with its own ID and $L_{i}$ . 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 node $v_{i}$ can hear any message transmitted by the nodes within its hearing distance, irrespective of whether or not $v_{i}$ is the intended recipient. Then, $v_{i}$ will drop messages not addressed to it. The nodes within the hearing distance of $v_{i}$ can be classified into three categories: the parent of $v_{i}$ , the children of $v_{i}$ , denoted by $C_{i}$ ( $C_{i} = ϕ$ , when $v_{i}$ is a leaf node), and the neighbors of $v_{i}$ , denoted by $N_{i}$ .

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.

Let $T (v_{i})$ denote the subtree rooted at $v_{i}$ and let $n_{i}$ denote the number of nodes in $T (v_{i})$ ; then we have $n_{i} = \sum_{v_{k} \in C_{i}} n_{k} + 1$ . We assume that every sensor generates m-bit message in each data collection round. Ideally, the amount of data received by $v_{i}$ from its $n_{i} - 1$ descendants will be $R_{i}^{r} = m \times (n_{i} - 1)$ bits, and $v_{i}$ will transmit $R_{i}^{t} = m \times n_{i}$ bits to its parent. Let $E_{t}$ and $E_{r}$ denote the energy used to transmit and receive 1 bit of data in wireless communication, respectively. Therefore, the energy consumption of $v_{i}$ in each data collection round is given by

\begin{matrix} r_{i} = R_{i}^{r} \times E_{r} + R_{i}^{t} \times E_{t} = m \times (n_{i} - 1) \times E_{r} + m \times n_{i} \times E_{t} . \end{matrix}

(1)

The current residual energy of $v_{i}$ is denoted by $e_{i}$ , and the lifetime of $v_{i}$ is defined as

\begin{matrix} t_{i} = \frac{e_{i}}{r_{i}}, \end{matrix}

(2)

where the unit of

t_{i}

is round.

Definition 3 (lifetime of a tree).

The lifetime of a data collection tree T 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,

\begin{matrix} t (T) = \min \{t_{i} | i = 1, \dots, n\} . \end{matrix}

(3)

The network lifetime of a tree-based WSN is just the lifetime of the data collection tree T in the network.

Definition 4 (load of a node).

The load $γ_{i}$ of a node $v_{i}$ is defined as the reciprocal of $t_{i}$ ; that is,

\begin{matrix} γ_{i} = \frac{1}{t_{i}} = \frac{r_{i}}{e_{i}} . \end{matrix}

(4)

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 tree T, the path from a node $v_{i}$ to the sink is denoted by $P_{i}$ . The path load $σ_{i}$ of $v_{i}$ is the highest load of all nodes along the path $P_{i}$ . Formally, $σ_{i} = \max \{γ_{i} | v_{j} \in P_{i}\}$ (specifically, the load of the sink is zero).

If $v_{j}$ is the parent of $v_{i}$ on $P_{i}$ , then the path load $σ_{i}$ of $v_{i}$ can be recursively defined as

\begin{matrix} σ_{i} = \max \{σ_{j}, γ_{i}\} . \end{matrix}

(5)

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 tree T. Formally,

\begin{matrix} \max t (T) = \max \min \{t_{i} | i = 1, \dots, n\} . \end{matrix}

(6)

Substituting formula (4) into formula (6),

\begin{matrix} \max t (T) = \min \max \{γ_{i} | i = 1, \dots, n\} . \end{matrix}

(7)

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.

Figure 1 depicts two different data collection trees $T^{1}$ and $T^{2}$ produced by RaSMaLai in a connected graph G. In this figure, node $v_{i}$ 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 $e_{4} = 7 / 13$ for node $v_{4}$ and $e_{5} = 0.5$ for node $v_{5}$ , 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 $v_{i}$ with ( $γ_{i}$ , $σ_{i}$ ) to denote its load and path load. As shown in Figure 1(a), we can get $δ_{1} = 13 - 3 = 10$ , and $v_{4}$ drawn with a red background is the one with the highest load in $T^{1}$ ; hence, its lifetime is right the network lifetime $t (T^{1}) = t_{4} = 1 / 13$ . According to the RaSMaLai algorithm, $v_{6}$ is considered for switching. Suppose that $v_{6}$ is decided to switch to $v_{5}$ ; a new tree $T^{2}$ after switching is obtained as shown in Figure 1(b). We can find that $δ_{2} = 14 - 5 = 9$ , and $v_{5}$ is the one with the highest load in $T^{2}$ , so we have $t (T^{2}) = t_{5} = 1 / 14$ . Now we can see that although $δ_{2} < δ_{1}$ after switching of $v_{6}$ , it results in $t (T^{2}) < t (T^{1})$ , which shows that $T^{2}$ is more load balanced than $T^{1}$ but has a shorter lifetime.

Figure 1

Example of δ-bounded balanced trees $T^{1}$ and $T^{2}$ .

We 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 $v_{m}$ . According to formulae (1) and (4), we have

\begin{matrix} γ_{m} = \frac{r_{m}}{e_{m}} = \frac{m \times (n_{m} - 1) \times E_{r} + m \times n_{m} \times E_{t}}{e_{m}} = \frac{m \times n_{m} \times (E_{r} + E_{t}) - m \times E_{r}}{e_{m}} . \end{matrix}

(8)

It can be seen that the load $γ_{m}$ of the bottleneck node $v_{m}$ is proportional to the number of the nodes $n_{m}$ in the subtree rooted at $v_{m}$ , with given m, $E_{r}$ , $E_{t}$ , and $e_{m}$ . Switching the descendants of $v_{m}$ to other subtrees can reduce $n_{m}$ , which decreases $γ_{m}$ in turn.

If node $v_{j}$ is considered for switching in RaSMaLai, the potential parent list of $v_{j}$ is constructed as $W_{j} = \{v_{i} | v_{i} \in N_{j}, σ_{j} - σ_{i} > δ\}$ . If $v_{j}$ is decided to switch, a node is chosen randomly with uniform probability from $W_{j}$ to be the new parent for $v_{j}$ , without considering the level of the new parent in the tree. Thus, a node whose level is greater than that of $v_{j}$ may be chosen as the new parent of $v_{j}$ , 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 switching $v_{j}$ from the old parent $v_{d}$ to the new parent $v_{x}$ in RaSMaLai, the highest load on the path $P_{d}^{}$ decreases indeed, but the highest load on $P_{x}^{}$ will increase, sometimes even exceeding that on $P_{d}^{}$ 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. When $v_{j}$ is considered for switching, only the neighbors whose level is less than that of $v_{j}$ will be added to the potential parent list $W_{j}$ ( $W_{j} = \{v_{i} | L_{i} < L_{j}, v_{i} \in N_{j}\}$ ). Thus, the level of the tree will not increase after switching. Then, the node $v_{x}$ with the minimum path load in $W_{j}$ will be chosen as the new parent of $v_{j}$ . Thus, the highest load on $P_{x}$ after switching $v_{j}$ to $v_{x}$ may not exceed that on $P_{d}$ before switching $v_{j}$ from $v_{d}$ in most cases.

In some particular cases, the highest load on $P_{x}$ after switching will be higher than that on $P_{d}$ before switching. To overcome this problem, SAPS estimates the path load $σ_{x}^{'}$ on $P_{x}$ assuming $v_{j}$ has been switched from $v_{d}$ to $v_{x}$ , which is $σ_{x}^{'} = \max \{γ_{x}^{'} | v_{i} \in P_{x}\}$ . If $σ_{x}^{'} \geq σ_{d}$ , $v_{j}$ is not switched to $v_{x}$ because the highest load on $P_{x}$ after switching will exceed that on $P_{d}$ before switching, which is not conducive to decreasing the maximum load in the network. Otherwise, $v_{j}$ will be switched to $v_{x}$ . 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 Algorithm 1. All the major symbols used in the algorithm are given as follows:

V: the set of all nodes in a WSN.

$L_{j}$ : the level of $v_{j}$ .

$C_{j}$ : the set of children of $v_{j}$ .

$N_{j}$ : the set of neighbors of $v_{j}$ .

$T (v_{j})$ : the subtree rooted at $v_{j}$ .

$γ_{i}$ : the load of $v_{i}$ .

$P_{x}$ : the path from $v_{x}$ to the sink.

$σ_{i}$ : the path load of $v_{i}$ .

$W_{j}$ : the potential parent list of $v_{j}$ .

$γ_{i}^{'}$ : the estimated load of $v_{i}$ on $P_{x}$ assuming some node has been switched to $v_{x}$ .

$σ_{x}^{'}$ : the estimated path load of $v_{x}$ assuming some node has been switched to $v_{x}$ .

Algorithm 1: SAPS.

(1) Calculate $γ_{i}$ and $σ_{i}$ for each node $v_{i} \in V$ ;

(2) Select the node $v_{m}$ with the highest load;

(3) while (true)

(4) { $f l g \leftarrow 0$ ;

(5) queue $α \leftarrow C_{m}$ ;

(6) while ( $α \neq ϕ$ )

(7) { Remove node $v_{j}$ from the head of the queue α;

(8) $W_{j}$ ← any node in $N_{j}$ whose level is less than $L_{j}$ ;

(9) if ( $W_{j} = ϕ$ ) $α \leftarrow C_{j}$ ;

(10) else

(11) { Select the node $v_{x}$ with the lowest path load from $W_{j}$ ;

(12) Estimate the path load $σ_{x}^{'}$ on $P_{x}^{}$ assuming $v_{j}$ has been switched from $v_{d}$ to $v_{x}$ ;

(13) if ( $σ_{x}^{'} \geq σ_{d}$ ) $α \leftarrow C_{j}$ ;

(14) else

(15) { Switch $v_{j}$ to $v_{x}$ ;

(16) If $L_{j}$ is changed, then update the level of each node in $T (v_{j})$ ;

(17) Update $γ_{i}$ and $σ_{i}$ for each node $v_{i} \in V$ ;

(18) $f l g \leftarrow 1$ ;

(19) }

(20) }

(21) }

(22) if ( $f l g$ == 0) return;

(23) else Select the node $v_{m}$ 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 $v_{i}$ 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 $v_{m}$ with the highest load is selected (line 2).

Step 2.

The flag variable $f l g$ is zero-initialized, which means that no descendant of $v_{m}$ has been switched (line 4). Then, the children of $v_{m}$ are inserted into the queue α (line 5).

Step 3.

If $α \neq ϕ$ , a node $v_{j}$ is removed from α in FIFO order and its potential parent list $W_{j} = \{v_{i} | L_{i} < L_{j}, v_{i} \in N_{j}\}$ is constructed (lines 7-8). If $v_{j}$ has no potential parent, that is, $W_{j} = ϕ$ , then the children of $v_{j}$ are added to α and considered for switching later (line 9). Otherwise, the node $v_{x}$ with the lowest path load is selected from $W_{j}$ , and the path load $σ_{x}^{'}$ on $P_{x}$ is estimated, $σ_{x}^{'} = \max \{γ_{i}^{'} | v_{i} \in P_{x}\}$ (lines 11-12). If $σ_{x}^{'} \geq σ_{d}$ , $v_{j}$ is not switched to $v_{x}$ and the children of $v_{j}$ are added to α for subsequent consideration (line 13). Otherwise, $v_{j}$ will be switched to $v_{x}$ (line 15). If $L_{j}$ is changed after switching, the level of each node in $T (v_{j})$ is updated (line 16). Afterwards, $γ_{i}$ and $σ_{i}$ for each node are updated and $f l g$ is set to 1, which means that at least one descendant of $v_{m}$ 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 $v_{m}$ is completed. If $f l g = 0$ , there are no nodes switched, and SPAS terminates (line 22). Otherwise, the node $v_{m}$ 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 parameter $D_{m a x}$ 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 $D_{m a x}$ .

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 node $v_{j}$ is the maximum load in $T (v_{j})$ and can be denoted by ${\hat{σ}}_{j}$ . When $v_{j}$ is a leaf node, one has ${\hat{σ}}_{j} = γ_{j}$ . Otherwise, ${\hat{σ}}_{j} = \max \{γ_{j}, \max \{{\hat{σ}}_{k}\}\}$ , where $v_{k} \in C_{j}$ .

Similar to SAPS, DSAPS also starts with a random tree, which then proceeds with the following phases.

Phase 1.

Each node $v_{i}$ calculates its $n_{i}$ and ${\hat{σ}}_{i}$ from bottom to top. When $v_{k}$ is a leaf node, we have $n_{k} = 1$ and ${\hat{σ}}_{k} = γ_{k}$ . Then, $v_{k}$ transmits $n_{k}$ and ${\hat{σ}}_{k}$ to its parent $v_{j}$ in a DPLCollect message. After receiving these values from $v_{k}$ , $v_{j}$ stores them, and after receiving the DPLCollect messages from all of its children, $v_{j}$ computes its own $n_{j}$ , $γ_{j}$ , and ${\hat{σ}}_{j}$ . Then, $v_{j}$ transmits a DPLCollect message embedded with $n_{j}$ and ${\hat{σ}}_{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 $v_{j}$ receives a PathLoadUpdate message from its parent $v_{d}$ , it stores $σ_{d}$ and computes its own path load $σ_{j} = \max \{γ_{j}, σ_{d}\}$ . Then, $v_{j}$ broadcasts a PathLoadUpdate message to its children with $σ_{j}$ embedded in it. When a leaf node $v_{l}$ 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, $v_{i}$ 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 Phase 3 is to find the bottleneck node with the highest load. First, the sink sends a Find message to its child $v_{a}$ with the maximum downward path load ${\hat{σ}}_{m a x}$ . Then, $v_{a}$ looks up its own load $γ_{a}$ . If $γ_{a} = {\hat{σ}}_{m a x}$ , $v_{a}$ is the bottleneck node. Otherwise, $v_{a}$ finds the node $v_{b}$ with ${\hat{σ}}_{b} = {\hat{σ}}_{m a x}$ in its downward path load table and sends the Find message to $v_{b}$ . The Find message will be routed repeatedly until the bottleneck node $v_{m}$ with $γ_{m} = {\hat{σ}}_{m a x}$ 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 with $v_{m}$ ) broadcasts a Switch message to its children. After a node $v_{j}$ receives the Switch message, it broadcasts a Request message embedded with its level $L_{j}$ to its neighbors. If a neighbor $v_{h}$ satisfies $L_{h} < L_{j}$ , it replies with a ReqAccept message with $σ_{h}$ embedded in it. Otherwise, it replies with a ReqDeny message. Node $v_{j}$ adds the node that replies with a ReqAccept message to $W_{j}$ , which will be established after $v_{j}$ receives messages from all its neighbors.

Step 2.

If $W_{j} = ϕ$ , $v_{j}$ does not switch, and it is elected as the current node to repeat Step 1. Otherwise, $v_{j}$ selects the node $v_{x}$ with the minimum path load from $W_{j}$ and transmits a FindMXL message embedded with $n_{j}$ to it. This message is used to inform $v_{x}$ to estimate the path load $σ_{x}^{'}$ on $P_{x}$ assuming $v_{j}$ has switched from its current parent $v_{d}$ to $v_{x}$ . After receiving the FindMXL message, $v_{x}$ estimates its own load $γ_{x}^{'}$ and transmits the FindMXL message embedded with $n_{j}$ to its parent, and so on. When the level 1 node $v_{e}$ on $P_{x}$ receives the FindMXL message, it estimates $γ_{e}^{'}$ and sets its estimated path load $σ_{e}^{'} = γ_{e}^{'}$ . Then, $v_{e}$ transmits a FindMXLAck message embedded with $σ_{e}^{'}$ to its child $v_{c}$ that transmits the FindMXL message to it. Then, $v_{c}$ calculates $σ_{c}^{'} = m a x {γ_{c}^{'}, σ_{e}^{'}}$ and forwards the FindMXLAck message down the tree. After receiving the FindMXLAck message, $v_{x}$ calculates $σ_{x}^{'}$ and transmits it to $v_{j}$ . Then, $v_{j}$ compares $σ_{x}^{'}$ with $σ_{d}$ . If $σ_{x}^{'} \geq σ_{d}$ , $v_{j}$ does not switch to $v_{x}$ and Step 1 is repeated starting with $v_{j}$ . Otherwise, $v_{j}$ switches to $v_{x}$ .

Step 3.

The following operations should be done for switching $v_{j}$ from $v_{d}$ to $v_{x}$ : (1)

Node $v_{j}$ adds $v_{d}$ to the neighbor table and denotes $v_{x}$ as the new parent while deleting it from the neighbor table.

(2)

Node $v_{j}$ transmits a Join message to $v_{x}$ with $n_{j}$ and ${\hat{σ}}_{j}$ embedded in it. Then, $v_{x}$ moves $v_{j}$ from the neighbor table to the children table, stores ${\hat{σ}}_{j}$ and recomputes $n_{x}$ ( $n_{x} + = n_{j}$ ), $γ_{x}$ , and ${\hat{σ}}_{x}$ , and then transmits IDPLUpdate message to its parent $v_{g}$ with $n_{j}$ and ${\hat{σ}}_{x}$ embedded in it. When $v_{g}$ receives the IDPLUpdate message, it updates ${\hat{σ}}_{x}$ in the downward path load table and recomputes $n_{g}$ ( $n_{g} + = n_{j}$ ), $γ_{g}$ , and ${\hat{σ}}_{g}$ and then transmits $n_{j}$ and ${\hat{σ}}_{g}$ to its parent. This process repeats until the sink receives the IDPLUpdate message from a node $v_{t}$ at level 1. After updating ${\hat{σ}}_{t}$ in the downward path load table, the sink broadcasts LPLUpdate message down the subtree $T (v_{t})$ for updating the path load and the level of each node in $T (v_{t})$ . The LPLUpdate message includes the path load and the level of the node that transmits it.

(3)

Node $v_{j}$ transmits a Leave message embedded with $n_{j}$ to $v_{d}$ . Then, $v_{d}$ moves $v_{j}$ from the children table to the neighbor table, deletes ${\hat{σ}}_{j}$ from the downward path load table and recomputes $n_{d}$ ( $n_{d} - = n_{j}$ ), $γ_{d}$ , and ${\hat{σ}}_{d}$ , and then transmits a DDPLUpdate message embedded with $n_{j}$ and ${\hat{σ}}_{d}$ to its parent $v_{f}$ . When receiving the DDPLUpdate message, $v_{f}$ updates ${\hat{σ}}_{d}$ in the downward path load table and recomputes $n_{f}$ ( $n_{f} - = n_{j}$ ), $γ_{f}$ , and ${\hat{σ}}_{f}$ and then transmits $n_{j}$ and ${\hat{σ}}_{f}$ to its parent. This process repeats until the sink receives the DDPLUpdate message from a node $v_{p}$ at level 1. After the sink updates ${\hat{σ}}_{p}$ , it broadcasts a PathLoadUpdate message down the subtree $T (v_{p})$ for updating the path load of each node in $T (v_{p})$ . Note that a node transmits the PathLoadUpdate message to its children only when its path load changes.

Step 4.

If a node $v_{n}$ 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 $f l g$ ( $f l g = 1$ ) embedded in it. If $v_{n}$ has not switched, it transmits the SwitchAck message embedded with its $f l g$ to its parent after receiving the SwitchAck messages from all the children (if any node in $T (v_{n})$ has switched, then $v_{n}$ has $f l g = 1$ ; else, $v_{n}$ has $f l g = 0$ ). When the bottleneck node $v_{m}$ 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 of $v_{m}$ is completed. If $f l g$ received is 0, DSAPS terminates. Otherwise, the sink increases the variable $c o u n t$ by 1 ( $c o u n t$ is zero-initialized). If $c o u n t \leq D_{m a x}$ , 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 $100 m \times 100 m$ , 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 $E_{r} = 50$ nJ/bit and the energy loss of transmitting a message was set to $E_{t} = 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 parameter $D_{m a x}$ which denotes the maximum number of iterations. To explore the impact of $D_{m a x}$ on the performance of DSAPS, we carried out multiple simulation experiments on different networks in Scenarios 1 and 2 for DSAPS. In each experiment, $D_{m a x}$ varied from 10 to 490 with the step size of 40. Through these experiments, we find that DSAPS achieves better results when $D_{m a x} = 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 $D_{m a x}$ 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 $D_{m a x} = 50$ , the number of iterations and energy expenditure for switching are higher than those for $D_{m a x} = 10$ , but the lifetime is also higher. However, bigger $D_{m a x}$ does not necessarily mean higher lifetime, because as $D_{m a x}$ 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 $D_{m a x} > 50$ , the lifetime is a few rounds less than that for $D_{m a x} = 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 $D_{m a x} = 50$ for DSAPS in both scenarios.

Figure 2

Impact of $D_{m a x}$ .

RaSMaLai has two control parameters which dominate the performance of RaSMaLai: δ, the maximum allowable difference among the path loads of leaf nodes, and $β_{m a x}$ , 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 β_{m a x}$ here to differentiate from $β_{m a x}$ in RaSMaLai.

For different networks, the optimum values of δ, $β_{m a x}$ , and $d β_{m a x}$ 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 $β_{m a x}$ and $d β_{m a x}$ 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 β_{m a x}$ is much smaller than that of $β_{m a x}$ . This is because, for D-RaSMaLai, the greater the value of $d β_{m a x}$ , 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 β_{m a x}$ .

Table 1

Parameter settings for RaSMaLai and D-RaSMaLai.

Scenario	Algorithm	Parameter	Number of nodes
Scenario	Algorithm	Parameter	100	150	200	250	300	350	400
1	RaSMaLai	$β_{m a x}$	1450	1350	1650	1950	1450	1450	1350
	RaSMaLai	δ	3	3.5	4	4	4	4.5	4.5
	D-RaSMaLai	$d β_{m a x}$	250	150	350	250	250	250	250
	D-RaSMaLai	δ	3.5	5	5	5.5	6	6.5	7

2	RaSMaLai	$β_{m a x}$	1650	1850	1650	1550	1650	1650	1350
	RaSMaLai	δ	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
	D-RaSMaLai	δ	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 Section 5.1.

5.2.1. Network Lifetime

The experimental results on the lifetime are shown in Figures 3(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.

As shown in Figure 3, 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 Table 2 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
Scenario	Algorithm	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	150

Figure 4

Lifetime in Scenario 2: (a) after 5 iterations and (b) after 10 iterations.

5.2.3. Maximum Level of the Routing Tree after Switching

Figures 5(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.

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 Figure 6. 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 Figures 7(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.

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.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

This work is supported by the National Natural Science Foundation of China (61272084, 61572263, 61300240, 61373015, and 41301407), the Key Project of Natural Science Research of Jiangsu University (14KJB520027), the National Natural Science Foundation of Jiangsu Province (BK20130819, BK20151511), the National Natural Science Cultivation Foundation of China (NS2012023), the Postdoctoral Science Foundation of China (2013M540447, 2013M541703), and the Postdoctoral Science Foundation of Jiangsu (1301020C, 1301042B).

References

Elghazel

Bahi

Guyeux

Hakem

Medjaher

Zerhouni

Dependability of wireless sensor networks for industrial prognostics and health management

Computers in Industry 2015 68 1 15

10.1016/j.compind.2014.10.004

Nikolidakis

S. A.

Kandris

Vergados

D. D.

Douligeris

Energy efficient automated control of irrigation in agriculture by using wireless sensor networks

Computers and Electronics in Agriculture 2015 113 154 163

10.1016/j.compag.2015.02.004

Collotta

Lo Bello

Pau

A novel approach for dynamic traffic lights management based on Wireless Sensor Networks and multiple fuzzy logic controllers

Expert Systems with Applications 2015 42 13 5403 5415

10.1016/j.eswa.2015.02.011

Ochoa

S. F.

Santos

Human-centric wireless sensor networks to improve information availability during urban search and rescue activities

Information Fusion 2015 22 71 84

10.1016/j.inffus.2013.05.009

2-s2.0-84907599189

Rault

Bouabdallah

Challal

Energy efficiency in wireless sensor networks: a top-down survey

Computer Networks 2014 67 104 122

10.1016/j.comnet.2014.03.027

2-s2.0-84899560578

Shan

Liang

Luo

Shen

Network lifetime maximization for time-sensitive data gathering in wireless sensor networks

Computer Networks 2013 57 5 1063 1077

10.1016/j.comnet.2012.12.005

2-s2.0-84875724841

Bober

Bleakley

C. J.

BailighPulse: a low duty cycle data gathering protocol for mostly-off Wireless Sensor Networks

Computer Networks 2014 69 51 65

10.1016/j.comnet.2014.04.018

2-s2.0-84901267638

Carrano

R. C.

Passos

Magalhães

L. C. S.

Albuquerque

C. V. N.

A comprehensive analysis on the use of schedule-based asynchronous duty cycling in wireless sensor networks

Ad Hoc Networks 2014 16 142 164

10.1016/j.adhoc.2013.12.009

2-s2.0-84894476434

Mainetti

Mighali

Patrono

HEC-MAC: a hybrid energy-aware cross-layer MAC protocol for wireless sensor networks

International Journal of Distributed Sensor Networks 2015 2015 12

536794

10.1155/2015/536794

10.

Peng

Qiao

I²C: a holistic approach to prolong the sensor network lifetime

Proceedings of the IEEE Conference on Computer Communications (INFOCOM '13)

April 2013

Turin, Italy

IEEE

2670 2678

10.1109/INFCOM.2013.6567075

11.

Behdani

Yun

Y. S.

Cole Smith

Xia

Decomposition algorithms for maximizing the lifetime of wireless sensor networks with mobile sinks

Computers & Operations Research 2012 39 5 1054 1061

10.1016/j.cor.2011.06.013

2-s2.0-80052262771

12.

Y. S.

Ren

Zhao

EMS: efficient mobile sink scheduling in wireless sensor networks

Ad Hoc Networks 2013 11 5 1556 1570

10.1016/j.adhoc.2012.11.010

2-s2.0-84878011581

13.

Chu

W.-C.

Ssu

K.-F.

Sink discovery in location-free and mobile-sink wireless sensor networks

Computer Networks 2014 67 123 140

10.1016/j.comnet.2014.03.028

2-s2.0-84899577789

14.

Keskin

M. E.

Altinel

I. K.

Aras

Ersoy

Wireless sensor network lifetime maximization by optimal sensor deployment, activity scheduling, data routing and sink mobility

Ad Hoc Networks 2014 17 18 36

10.1016/j.adhoc.2014.01.003

2-s2.0-84896697093

15.

Bahi

Haddad

Hakem

Kheddouci

Efficient distributed lifetime optimization algorithm for sensor networks

Ad Hoc Networks 2014 16 1 12

10.1016/j.adhoc.2013.11.010

2-s2.0-84894504472

16.

Luo

Wang

Guo

Chen

Parameterized complexity of Max-lifetime Target Coverage in wireless sensor networks

Theoretical Computer Science 2014 518 32 41

10.1016/j.tcs.2013.06.008

ZBL06244493

2-s2.0-84891743383

17.

Wang

Roman

H. E.

Yuan

Huang

Wang

Connectivity, coverage and power consumption in large-scale wireless sensor networks

Computer Networks 2014 75 212 225

10.1016/j.comnet.2014.10.008

2-s2.0-84918833508

18.

Peng

Wang

Zhang

Jiang

Lifetime optimization by load-balanced and energy efficient tree in wireless sensor networks

Mobile Networks and Applications 2013 18 4 488 499

10.1007/s11036-012-0428-5

2-s2.0-84880506022

19.

Imon

S. K. A.

Khan

Di Francesco

Das

S. K.

RaSMaLai: a randomized switching algorithm for maximizing lifetime in tree-based wireless sensor networks

Proceedings of the 32nd IEEE Conference on Computer Communications (INFOCOM '13)

April 2013

Turin, Italy

IEEE

2913 2921

10.1109/infcom.2013.6567102

2-s2.0-84883096111

20.

Coman

Nascimento

M. A.

Sander

A framework for spatio-temporal query processing over wireless sensor networks

Proceedings of the 1st International Workshop on Data Management for Sensor Networks: In Conjunction with VLDB 2004 (DMSN '04)

August 2004

Toronto, Canada

ACM

104 110

10.1145/1052199.1052217

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

Abstract

1. Introduction

2. Related Work

3. System Model and Problem Statement

3.1. Network Model

3.2. Problem Statement

Definition 1 (round).

Definition 2 (lifetime of a node).

Definition 3 (lifetime of a tree).

Definition 4 (load of a node).

Definition 5 (path load).

Definition 6 (lifetime maximization problem, LMP).

4. The Proposed Algorithms

4.1. Design of the SAPS Algorithm

4.2. Details of the SAPS Algorithm

Algorithm 1: SAPS.

Step 1.

Step 2.

Step 3.

Step 4.

4.3. DSAPS: A Distributed Version of SAPS

Definition 7 (downward path load).

Phase 1.

Phase 2.

Phase 3.

Phase 4.

Step 1.

Step 2.

Step 3.

Step 4.

Phase 5.

5. Performance Evaluation

5.1. Setup of Control Parameters

5.2. Performance Analysis and Discussions

5.2.1. Network Lifetime

5.2.2. Number of Iterations

5.2.3. Maximum Level of the Routing Tree after Switching

5.2.4. Energy Expenditure for Switching

5.2.5. Energy Expenditure for Data Collection in Each Round

6. Conclusion

Footnotes

Conflict of Interests

Acknowledgments

References