# Maximizing the Lifetime of Wireless Sensor Networks Using Multiple Sets of Rendezvous

Authors: Bo Li; Sungkwon Park
Journal: Mobile Information Systems
 (2015)

---

## Abstract

In wireless sensor networks (WSNs), there is a “crowded center effect” where the energy of nodes located near a data sink drains much faster than other nodes resulting in a short network lifetime. To mitigate the “crowded center effect,” rendezvous points (RPs) are used to gather data from other nodes. In order to prolong  the lifetime of WSN further, we propose using multiple sets of RPs in turn to average the energy consumption of the RPs. The problem is how to select the multiple sets of RPs and how long to use each set of RPs. An optimal algorithm and a heuristic algorithm are proposed to address this problem. The optimal algorithm is highly complex and only suitable for small scale WSN. The performance of the proposed algorithms is evaluated through simulations. The simulation results indicate that the heuristic algorithm approaches the optimal one and that using multiple RP sets can significantly prolong network lifetime.


---

## Body

## 1. Introduction

A wireless sensor network (WSN) is composed of spatially distributed autonomous sensor nodes that monitor physical or environmental conditions. WSN has a wide field of applications such as intelligent transportation [1], health monitoring [2], military information integration [3], and forest fire detection [4]. In a WSN, sensor nodes generate sensory data which are then delivered to one or more data sinks using multihop forwarding. All sensory data from the entire network ultimately pass through sensor nodes situated at one-hop distance from a sink node. That is, those nodes within one-hop distance to a sink node must transmit all data generated from the entire network. These sensor nodes consume significant energy for data transmission causing rapid energy depletion. Once all available energy of them is depleted, sensory data from the whole network is unable to reach the data sink rendering the network inoperative. This phenomenon is called the “crowded center effect” [5]. In order to mitigate this problem, rendezvous-based approaches are proposed [6–13].In rendezvous-based approaches, some nodes are selected as rendezvous points (RPs) to gather data from other nodes. Each RP is visited by a mobile device, referred to as a mobile element (ME), which collects the gathered data. A RP transmits this data when the ME passes by and the ME carries the collected data back to the sink. Utilizing this approach, network traffic is distributed to RPs. Designating additional RPs increases the dispersion of network traffic, thereby increasing network lifetime as well. However, nodes cannot be arbitrarily designated as RPs as the ME must visit each RP to collect data and transmit the data to the sink within a delay constraint. If there are too many RPs, the travel time of the ME will exceed the delay constraint.In a rendezvous-based method, typically a single set of nodes is selected as RPs. Consequently, the selected RPs are constantly subjected to the “crowded center effect” and their energy depletes at a faster rate than regular nodes. In order to further balance energy consumption, we propose implementingmultiple sets of RPs in turn to gather data. As shown in Figure 1, assume that in a WSN RP sets {1,3} and {2,4} are both feasible. Suppose that we only use RP set {1,3} and allow nodes 2 and 4 to forward their data to nodes 1 and 3, respectively, as shown in Figure 1(a). As a result, nodes 1 and 3 will consume their available energy sooner than nodes 2 and 4. When nodes 1 and 3 expire, the network becomes inoperative despite nodes 2 and 4 having available energy. However, if we set nodes 1 and 3 as RPs as shown in Figure 1(a) only for a portion of the time and then designate nodes 2 and 4 as RPs for the remainder of the time as shown in Figure 1(b), then the average energy consumption of nodes 1 and 3 is reduced and the lifetime of the network is extended. The primary goal is to utilize multiple RPs at different times to average their energy consumption. The problem is how to select the different RP sets and how long to utilize each RP set in order to maximize network lifetime. We first propose an optimal algorithm to address this problem, which identifies all feasible RP sets and selects the optimal time fraction to use each RP set by solving linear programming problems. If there are too many feasible RP sets, the computation complexity of finding the best solution is extremely high. Therefore, we also propose a heuristic algorithm for this situation.Figure 1
Use multiple sets of RPs in turn to prolong lifetime of WSN further.
(a)
(b)The contributions of this paper are summarized as follows: (1) We formulate the problem of using multiple sets of RPs to maximize the lifetime of WSN; (2) we propose an optimal algorithm for this problem; (3) we propose a heuristic algorithm for large scale WSN with low complexity. The remainder of this paper is organized as follows: Related rendezvous-based energy saving methods for WSN are reviewed in Section 2. Section 3 formally states the problem we studied in this paper. Section 4 presents the proposed algorithms. In Section 5, we evaluate the performance of the proposed algorithms. Finally, conclusions are presented in Section 6.


## 2. Related Work

In WSNs, the mobile element (ME) has been implemented to reduce the energy consumption of sensor nodes. The related approaches can be classified into two types: (1)one-hop and (2)rendezvous-based. In one-hop approaches, the ME visits each sensor node, and a sensor node only needs to transmit its data to the ME via one hop. Consequently, the energy consumption of sensor nodes is reduced significantly. Initially, researchers proposed using MEs with random mobility such as animals [14], an access point mounted on a bus [15], or a flying mobile agent [16] to collect data from sensor nodes. Although these methods can be implemented with relative ease, random mobility uses time inefficiently for data collection. To address this, controlled mobility approaches were subsequently proposed. Nesamony et al. studied the problem of finding the minimum length path for a ME to visit each sensor node for data collection [17]. The problem is essentially the well-known traveling salesman problem (TSP) [18] which is NP-hard. Therefore, several heuristic algorithms were proposed for the ME path selection [19–25].Although one-hop approaches can minimize energy consumption of sensor nodes by avoiding multihop transmission, this causes high latency when collecting data from a large number of sensor nodes. In order to reduce data delivery delay, rendezvous-based approaches were proposed. In these approaches, a subset of sensor nodes are selected as RPs to gather data from other nodes via multihop transmission. A ME only visits RPs to collect data, and the data collection time cannot exceed a delay constraint. The problem studied in this paper falls into rendezvous-based approaches.The rendezvous-based model mentioned above was first implemented in [7, 8]. The authors proved that the problem of selecting a single set of RPs is NP-hard and instead proposed RP-CP and RP-UG algorithms. RP-CP is the optimal algorithm for a special case where the ME only moves along a routing tree which is rooted at the sink. RP-UG, on the other hand, is a heuristic algorithm for the general case. A cluster-based algorithm for rendezvous planning was proposed in [9]. The algorithm iteratively divides sensor nodes into clusters and designates a RP in each cluster. In each iteration, if the length of the shortest tour which covers all RPs is less than the length limit, the algorithm will select additional clusters in the next iteration until the longest feasible ME tour is found. Another algorithm called “rendezvous points selection with load balancing” (RPS-LB) [10] was proposed to jointly optimize path planning for the ME and load balancing for the network. It assumes that a routing tree has been built in the network. From the median of the tree, it traverses the heaviest subtree to construct a tour for the ME. If the tour length is less than the limit, it continues to traverse the second heaviest subtree. This procedure repeats until the tour length reaches the limit which leads to the final solution.In [11], a greedy method called weighted rendezvous planning (WRP) was proposed to select RPs iteratively. In this method, each node is assigned with a weight equal to the number of packets it must forward per period multiplied by its hop distance from the nearest RP. Initially, only the sink is selected as a RP. In each iteration, the node with the highest weight will be selected as RP and the weight of the remaining nodes is updated accordingly. When the length of the tour which covers the selected RPs exceeds the limit, the procedure ends. Konstantopoulos et al. proposed a clustering method for RP selection based on the watershed transform which is used in image segmentation [12]. The authors enhanced their work by adding an algorithm to periodically reselect a new set of RPs and rebuild the data gathering structure [13]. To the best of our knowledge, this work is the most similar to the methods discussed in this paper.Other works [26–31] also considered using multiple MEs to collect data from sensor nodes. Authors in [27–29, 31] investigated the problem of designing tours for multiple MEs to gather data with the same deadline, while authors in [27, 29] considered scheduling multiple MEs to harvest sensed data with different deadlines.


## 3. System Model and Problem Statement

In this paper, we consider a WSN with randomly distributed sensor nodes and a single sink node. In order to prolong the lifetime of the WSN, we selectmultiple sets of rendezvous points (RPs) and use themin turn to gather data from other sensor nodes. A mobile element (ME) visits currently selected RPs to collect gathered data. Some assumptions about this system are as follows:(1)
The locations of sensor nodes and the sink node are known.(2)
Each sensor node generates one chunk of sensory data with the same size synchronously in every period ofD.(3)
Each sensor node has an omnidirectional antenna to forward sensory data, and each node has at least one neighbor within its transmission range.(4)
The sensory data generated in each period must be delivered to the sink withinD seconds.(5)
The initial energy of all sensor nodes is the same.(6)
A sensor node has enough memory to buffer the data forwarded from its descendants.For different set of RPs, we need different data forwarding patterns to gather data. For example, Figures2(a) and 2(b) show the different data forwarding patterns when {node1,node2} and {node3,node4} are selected as RPs, respectively. In a data forwarding pattern, each RP is a root of a data forwarding tree. If in a data forwarding tree node, data from node A will be forwarded through node B, then we say that node A is a descendant of node B. With different data forwarding patterns, the number of descendants of a node is different. For a given set of RPs, we can let sensor nodes deliver their data to these RPs following different data forwarding patterns. Suppose that there are M possible data forwarding routing patterns in total for all possible RP sets. We denote the number of descendants of node i under mth data forwarding pattern by ni,m. Consider the data generated by one sensor node during every D seconds as one unit of data. Assume that the energy consumption incurred for transmitting and receiving one unit of data is ETX and ERX, respectively. Under mth data forwarding pattern, the energy consumption of node i for data reception in a period is ERXni,m. Node i has to forward the received data and the data generated by itself to its parent node; thus its energy consumption for data transmission in a period is ETX(ni,m+1). The energy consumption of node i in data communication during a period under mth data forwarding pattern, denoted by Ei,m, can be calculated by (1)Ei,m=ERXni,m+ETXni,m+1.We normalize the network lifetime as 1 and denote the fraction of time that mth data forwarding pattern is used by θm, where θm≥0 and ∑m=1Mθm=1. We only use a part of all possible data forwarding patterns. If θm= 0, then mth data forwarding pattern is not used. The average energy consumption of node i in data communication during every D seconds is(2)Ei=∑m=1MθmEi,m.In WSN, most of the energy is consumed by data communication. We consider Ei as the total energy consumption of node i per period. The network lifetime is equal to the lifetime of the node with the highest energy consumption rate. Thus, our goal is to minimize maxi⁡Ei. The main notations in this paper are listed in “Notation” section.Figure 2
Different data forwarding patterns when different RPs are selected.
(a)
(b)The constraint of the problem is that the sensory data must be delivered to the sink node withinD seconds. Suppose that the average velocity of the ME is v. The maximum path length of the ME, denoted by Lmax, can be calculated as(3)Lmax⁡=Dv.Periodically, the ME starts from the sink node to collect data from all RPs and then returns to the sink node. For a set of RPs, we can find the shortest path for the ME to collect data from RPs by a TSP solver [18]. We denote this shortest path length of a RP set S by PL(S), giving us the constraint PL(S)≤Lmax. The distance between any node in S and the sink must be less than Lmax/2; otherwise PL(S) is longer than Lmax. Any node adjacent to the sink should not be included in a RP set S because it can transmit data to the sink directly and using the ME to collect data from it is an unnecessary energy cost. We set nodes not adjacent to the sink node and with a distance of less than Lmax/2 from the sink as candidates for RPs. For example, as shown in Figure 2, the candidate RPs are nodes 1, 2, 3, and 4. Denoting the set of candidate RPs as C, we can choose any subset S of C as RPs at the same time if PL(S)≤Lmax.Suppose that there areM possible data forwarding patterns for all feasible subsets of C. For each data forwarding pattern, we can calculate Ei,m according to (1). Let vector ei=Ei,1,Ei,2,…,Ei,MT and θ=θ1,θ2,…,θMT. Then, the problem can be formulated as a linear min-max problem:PImin⁡θmaxi⁡eiTθ,s.t.∑m=1Mθm=1,θm≥0,1≤m≤M.This problem can be transformed to a set of linear programming problems. We explain this in detail in the next section.


## 4. Proposed Algorithms

In this section, we first propose the optimal algorithm for the problem stated in the previous section. The optimal algorithm has a very high complexity and is only suitable for a small scale WSN. For large scale WSNs, we also propose a heuristic algorithm with a much lower complexity. The heuristic algorithm is more suitable for practical implementations, and we will mainly focus on the heuristic algorithm.


### 4.1.  The Optimal Algorithm

The optimal solution for problemPI can be found by solving a set of linear programming problems. Consider a problem set PII which includes N linear programming problems as follows:PIImin⁡θekTθ,s.t.ekTθ≥eiTθ,i≠k,∑m=1Mθm=1,θm≥0,1≤m≤M,k=1,2,…,N.Referring to kth problem in PII as (PIIk), we have the following two theorems.Theorem 1.
If(PIIk), k=1,2,…,N, has the optimal solution θk∗ and epTθp∗=min1≤k≤N⁡ekTθk∗, then θp∗ is the optimal solution of PI.Proof.
See AppendixA.Theorem 2.
Assume thatθk∗ is the optimal solution of (PIIk); let W=W(θk∗)={i∣ekTθk∗=eiTθk∗,i≠k}; then (1)
ifW=∅, θk∗ is the optimal solution of PI;(2)
ifW≠∅ and, for any i∈WeiTθi∗≥ekTθk∗, then θk∗ is the optimal solution of PI.Proof.
See AppendixB.Based on these two theorems, we give the optimal algorithm for the problem as follows:(1)
Find all feasible RP sets and all possible data routing patterns for each RP set.(2)
For each routing patternm, calculate Ei,m, 1≤i≤N.(3)
Fork, 1≤i≤N, find the optimal solution θk∗ of problem (PIIk).(4)
Find outW=W(θk∗)={i∣ekTθk∗=eiTθk∗,i≠k}.(5)
IfW is empty, return θk∗; otherwise for each i∈W find the optimal solution θi∗ of problem (PIIi). If eiTθi∗<ekTθk∗, set k=i and go to step (4). If for any i∈WeiTθi∗≥ekTθk∗, return θk∗.Because each candidate RP can be either selected or not in a RP set, given N candidate RPs, there are 2N-1 possible combinations of the them. We check each possible combination to ascertain all feasible RP sets. Also, for each feasible RP set, we must find all possible corresponding routing patterns. If N is large, the computation complexity is extremely high. Therefore, we propose a low complexity heuristic algorithm in the next subsection.


### 4.2.  The Heuristic Algorithm

In order to reduce the complexity of the algorithm, we build a routing treeT rooted at the sink node, and each time we select a set of RPs only from nodes at the same level of T. Consequently, the search space is significantly reduced. Also, for each set of RPs, we only set one corresponding data forwarding pattern. We construct the routing tree T as follows. We set nodes near the sink node as its children; and for each child of the sink node, we again designate its adjacent nodes as its children. If a node is close to multiple upper level nodes, we set it as a child of the upper level node which has the least children in order to maintain the balance of the tree. This procedure repeats and, ultimately, we build the tree T which covers all sensor nodes. Next, we explain how to select RP sets at each level of T. The detailed algorithm is shown in Algorithm 1.Algorithm 1:The algorithm for finding RPs at different levels of T.
Algorithm to find RPs at different levels of  T
Input:
T, locations of sensor nodes, Lmax⁡
Output: S1, S2, …
(1)x←number of nodes at level 2, k←1
(2)for  h=2  to  hmax⁡  do
(3)y←number of nodes at level h
(4)  order nodes in clockwise direction
(5)for  i=1  to  y/x  do
(6)S←i,i+y/x,i+2y/x,…,i+(x-1)y/x
(7)if PL(S) ≤ Lmax⁡  then
(8)Sk←S, k++
(9)end if
(10) end for
(11)  if no feasible RP set exists then
(12)  x←x-1
(13)  gotoline (4)
(14) end if
(15)end forAs mentioned before, we do not set nodes near the sink node as RPs. Also, a candidate RP must have a distance of less thanLmax/2 from the sink node. Denote the level of the candidate RP which has the longest distance from the sink node as hmax. We find feasible sets of RPs from level 2 to hmax of tree T. The more nodes in a RP set the better. Assume that there are z nodes at level 2. We first try to set all these z nodes as RPs at the same time. If the resulting path length is longer than Lmax, then we try to select z-1 nodes as RPs. If a feasible set of z-1 RPs cannot be found, we try to find sets of RPs with z-2 nodes and so on. Assume that we can find at least one feasible set of RPs and the number of nodes in the feasible RP set is z′. Then, we stop and move to level 3. At level 3, the nodes are farther away from the sink compared to those at level 2. We are unlikely to find a feasible RP set with more nodes than the RP sets found at level 2. In order to reduce complexity, at level 3, we begin to search sets of RPs with z′ nodes. Following the same procedure, we can find all feasible RPs at each level.Assuming that in an iteration we try to find a set ofx RPs from y nodes at a level, the detailed method is as follows. As shown in Figure 3, we order the nodes in a clockwise direction. In order to balance the load of RPs, the RPs should be equally spaced so that they will have approximately the same number of descendants. Thus, we always select RPs at regular intervals. Explicitly, as shown from line 4 to line 9 in the algorithm, for each 1≤i≤y/x, we select a set of nodes S={i,i+y/x,i+2y/x,…,i+(x-1)y/x}. If a set of nodes S satisfies the constraint PL(S)≤Lmax, then we set it as a RP set.Figure 3
Select one RP in everyy/x nodes.For each found RP set at a levelh, the corresponding data forwarding pattern is set as follows. For nodes not at level h, they simply forward their data along the path of the routing tree T. For nodes at level h, we let them forward their data to the nearest RP rather than to their parents in tree T. For example, as shown in Figure 4, assume that nodes 3 and 4 are selected as RPs. Suppose that node 3 is near to nodes 1 and 2 and node 4 is near to node 5. Then, the data forwarding route is 1→2→3 and 5→4.Figure 4
Data forwarding pattern for a RP set at levelh.After all RP sets are found, finally we solve linear programming problems to set the time fraction for each RP set as in the proposed optimal algorithm. The computation complexity for solving a linear programming problem in problemPII is very high if the problem size is large. For example, the algorithm for linear programming in [32] has a time complexity of O(M(log⁡M)N2), where M is the number of found RP sets (the number of data forwarding patterns equals the number of RP sets because each RP set has only one corresponding data forwarding pattern) and N is the number of candidate RPs. In order to reduce the complexity, we only choose kmax RP sets from M found ones to solve for the final solution where kmax≤M. The method to decide the value of kmax will be described in the next subsection, and the way to choose kmax RP sets is as follows. For each selected RP set m, 1≤m≤M, we calculate Ei,m, 1≤i≤N, according to (1). Let Emmax=max1≤k≤N⁡Ek,m; we sort M RP sets according to Emmax in ascending order and choose the first kmax RP sets to solve the time fraction θ for them. Finally, we use this kmax RP sets in turn according to the time fraction allocated to them to prolong the network lifetime.


### 4.3. Deciding the Value ofkmax

k
m
a
x controls the tradeoff between the complexity and performance of the heuristic algorithm. In the heuristic algorithm, solving the linear programming problems to obtain the time fraction θ is the dominant time-consuming component. As mentioned before, the time complexity of solving the linear programming problems with M RP sets is O(M(log⁡M)N2), where N is the number of candidate RPs. We choose kmax RP sets. Thus, the complexity of the heuristic algorithm is O(kmax(log⁡kmax)N2). As kmax increases, the complexity of the heuristic algorithm also increases. However, the larger kmax is, the more RP sets will be chosen in the final solution and the more closely the heuristic algorithm approaches the optimal one. The value of kmax should be decided carefully in order to balance the computational complexity and the performance. The algorithm for finding the proper kmax is as follows.We first setkmax to 1 and then increase it by increments of 1 and estimate the resulting network lifetime. First, we only consider the time fraction allocation for the first two RP sets. Assume Ei,1=max1≤k≤N⁡Ek,1 and Ej,2=max1≤k≤N⁡Ek,2; that is, node i and node j have the highest energy consumption in the first and second RP sets, respectively. For node i, we should set θ1 as small as possible. While, for node j, we should set θ2 as small as possible. We have θ1+θ2=1. Thus, we can find the equilibrium between nodes i and j by solving θ1 and θ2 in (4)θ1Ei,1+θ2Ei,2=θ1Ej,1+θ2Ej,2,θ1+θ2=1.Then we can calculate E(1)=θ1Ei,1+θ2Ei,2. Assume, for the third RP set, Ep,3=max1≤k≤N⁡Ek,3. We solve equation θ′θ1Ei,1+θ2Ei,2+θ3Ei,3=θ′θ1Ep,1+θ2Ep,2+θ3Ep,3, where θ′+θ3=1, and calculate E(2)=θ′θ1Ei,1+θ2Ei,2+θ3Ei,3. This step is repeated iteratively, and, at each iteration k, E(k) is an approximation of the optimal average energy consumption with k+1 RP sets. As k increases, E(k) approaches the optimal solution. If E(k)-Ek-1<σ, where σ is a predefined threshold, then we stop and kmax is set to k+1.


## 4.1.  The Optimal Algorithm

The optimal solution for problemPI can be found by solving a set of linear programming problems. Consider a problem set PII which includes N linear programming problems as follows:PIImin⁡θekTθ,s.t.ekTθ≥eiTθ,i≠k,∑m=1Mθm=1,θm≥0,1≤m≤M,k=1,2,…,N.Referring to kth problem in PII as (PIIk), we have the following two theorems.Theorem 1.
If(PIIk), k=1,2,…,N, has the optimal solution θk∗ and epTθp∗=min1≤k≤N⁡ekTθk∗, then θp∗ is the optimal solution of PI.Proof.
See AppendixA.Theorem 2.
Assume thatθk∗ is the optimal solution of (PIIk); let W=W(θk∗)={i∣ekTθk∗=eiTθk∗,i≠k}; then (1)
ifW=∅, θk∗ is the optimal solution of PI;(2)
ifW≠∅ and, for any i∈WeiTθi∗≥ekTθk∗, then θk∗ is the optimal solution of PI.Proof.
See AppendixB.Based on these two theorems, we give the optimal algorithm for the problem as follows:(1)
Find all feasible RP sets and all possible data routing patterns for each RP set.(2)
For each routing patternm, calculate Ei,m, 1≤i≤N.(3)
Fork, 1≤i≤N, find the optimal solution θk∗ of problem (PIIk).(4)
Find outW=W(θk∗)={i∣ekTθk∗=eiTθk∗,i≠k}.(5)
IfW is empty, return θk∗; otherwise for each i∈W find the optimal solution θi∗ of problem (PIIi). If eiTθi∗<ekTθk∗, set k=i and go to step (4). If for any i∈WeiTθi∗≥ekTθk∗, return θk∗.Because each candidate RP can be either selected or not in a RP set, given N candidate RPs, there are 2N-1 possible combinations of the them. We check each possible combination to ascertain all feasible RP sets. Also, for each feasible RP set, we must find all possible corresponding routing patterns. If N is large, the computation complexity is extremely high. Therefore, we propose a low complexity heuristic algorithm in the next subsection.


## 4.2.  The Heuristic Algorithm

In order to reduce the complexity of the algorithm, we build a routing treeT rooted at the sink node, and each time we select a set of RPs only from nodes at the same level of T. Consequently, the search space is significantly reduced. Also, for each set of RPs, we only set one corresponding data forwarding pattern. We construct the routing tree T as follows. We set nodes near the sink node as its children; and for each child of the sink node, we again designate its adjacent nodes as its children. If a node is close to multiple upper level nodes, we set it as a child of the upper level node which has the least children in order to maintain the balance of the tree. This procedure repeats and, ultimately, we build the tree T which covers all sensor nodes. Next, we explain how to select RP sets at each level of T. The detailed algorithm is shown in Algorithm 1.Algorithm 1:The algorithm for finding RPs at different levels of T.
Algorithm to find RPs at different levels of  T
Input:
T, locations of sensor nodes, Lmax⁡
Output: S1, S2, …
(1)x←number of nodes at level 2, k←1
(2)for  h=2  to  hmax⁡  do
(3)y←number of nodes at level h
(4)  order nodes in clockwise direction
(5)for  i=1  to  y/x  do
(6)S←i,i+y/x,i+2y/x,…,i+(x-1)y/x
(7)if PL(S) ≤ Lmax⁡  then
(8)Sk←S, k++
(9)end if
(10) end for
(11)  if no feasible RP set exists then
(12)  x←x-1
(13)  gotoline (4)
(14) end if
(15)end forAs mentioned before, we do not set nodes near the sink node as RPs. Also, a candidate RP must have a distance of less thanLmax/2 from the sink node. Denote the level of the candidate RP which has the longest distance from the sink node as hmax. We find feasible sets of RPs from level 2 to hmax of tree T. The more nodes in a RP set the better. Assume that there are z nodes at level 2. We first try to set all these z nodes as RPs at the same time. If the resulting path length is longer than Lmax, then we try to select z-1 nodes as RPs. If a feasible set of z-1 RPs cannot be found, we try to find sets of RPs with z-2 nodes and so on. Assume that we can find at least one feasible set of RPs and the number of nodes in the feasible RP set is z′. Then, we stop and move to level 3. At level 3, the nodes are farther away from the sink compared to those at level 2. We are unlikely to find a feasible RP set with more nodes than the RP sets found at level 2. In order to reduce complexity, at level 3, we begin to search sets of RPs with z′ nodes. Following the same procedure, we can find all feasible RPs at each level.Assuming that in an iteration we try to find a set ofx RPs from y nodes at a level, the detailed method is as follows. As shown in Figure 3, we order the nodes in a clockwise direction. In order to balance the load of RPs, the RPs should be equally spaced so that they will have approximately the same number of descendants. Thus, we always select RPs at regular intervals. Explicitly, as shown from line 4 to line 9 in the algorithm, for each 1≤i≤y/x, we select a set of nodes S={i,i+y/x,i+2y/x,…,i+(x-1)y/x}. If a set of nodes S satisfies the constraint PL(S)≤Lmax, then we set it as a RP set.Figure 3
Select one RP in everyy/x nodes.For each found RP set at a levelh, the corresponding data forwarding pattern is set as follows. For nodes not at level h, they simply forward their data along the path of the routing tree T. For nodes at level h, we let them forward their data to the nearest RP rather than to their parents in tree T. For example, as shown in Figure 4, assume that nodes 3 and 4 are selected as RPs. Suppose that node 3 is near to nodes 1 and 2 and node 4 is near to node 5. Then, the data forwarding route is 1→2→3 and 5→4.Figure 4
Data forwarding pattern for a RP set at levelh.After all RP sets are found, finally we solve linear programming problems to set the time fraction for each RP set as in the proposed optimal algorithm. The computation complexity for solving a linear programming problem in problemPII is very high if the problem size is large. For example, the algorithm for linear programming in [32] has a time complexity of O(M(log⁡M)N2), where M is the number of found RP sets (the number of data forwarding patterns equals the number of RP sets because each RP set has only one corresponding data forwarding pattern) and N is the number of candidate RPs. In order to reduce the complexity, we only choose kmax RP sets from M found ones to solve for the final solution where kmax≤M. The method to decide the value of kmax will be described in the next subsection, and the way to choose kmax RP sets is as follows. For each selected RP set m, 1≤m≤M, we calculate Ei,m, 1≤i≤N, according to (1). Let Emmax=max1≤k≤N⁡Ek,m; we sort M RP sets according to Emmax in ascending order and choose the first kmax RP sets to solve the time fraction θ for them. Finally, we use this kmax RP sets in turn according to the time fraction allocated to them to prolong the network lifetime.


## 4.3. Deciding the Value ofkmax

k
m
a
x controls the tradeoff between the complexity and performance of the heuristic algorithm. In the heuristic algorithm, solving the linear programming problems to obtain the time fraction θ is the dominant time-consuming component. As mentioned before, the time complexity of solving the linear programming problems with M RP sets is O(M(log⁡M)N2), where N is the number of candidate RPs. We choose kmax RP sets. Thus, the complexity of the heuristic algorithm is O(kmax(log⁡kmax)N2). As kmax increases, the complexity of the heuristic algorithm also increases. However, the larger kmax is, the more RP sets will be chosen in the final solution and the more closely the heuristic algorithm approaches the optimal one. The value of kmax should be decided carefully in order to balance the computational complexity and the performance. The algorithm for finding the proper kmax is as follows.We first setkmax to 1 and then increase it by increments of 1 and estimate the resulting network lifetime. First, we only consider the time fraction allocation for the first two RP sets. Assume Ei,1=max1≤k≤N⁡Ek,1 and Ej,2=max1≤k≤N⁡Ek,2; that is, node i and node j have the highest energy consumption in the first and second RP sets, respectively. For node i, we should set θ1 as small as possible. While, for node j, we should set θ2 as small as possible. We have θ1+θ2=1. Thus, we can find the equilibrium between nodes i and j by solving θ1 and θ2 in (4)θ1Ei,1+θ2Ei,2=θ1Ej,1+θ2Ej,2,θ1+θ2=1.Then we can calculate E(1)=θ1Ei,1+θ2Ei,2. Assume, for the third RP set, Ep,3=max1≤k≤N⁡Ek,3. We solve equation θ′θ1Ei,1+θ2Ei,2+θ3Ei,3=θ′θ1Ep,1+θ2Ep,2+θ3Ep,3, where θ′+θ3=1, and calculate E(2)=θ′θ1Ei,1+θ2Ei,2+θ3Ei,3. This step is repeated iteratively, and, at each iteration k, E(k) is an approximation of the optimal average energy consumption with k+1 RP sets. As k increases, E(k) approaches the optimal solution. If E(k)-Ek-1<σ, where σ is a predefined threshold, then we stop and kmax is set to k+1.


## 5. Performance Evaluation

In this section we evaluate the performance of the proposed algorithms through simulations implemented by MATLAB. The proposed optimal and heuristic algorithms are first compared to see how closely the heuristic algorithm can approach the optimal one. The performance of the proposed heuristic algorithm is also compared against two existing methods. One method is proposed by Konstantopoulos et al. in [13] which also dynamically changes RPs. The other method is called WRP [11] in which RPs do not change. In the simulations, we consider a WSN where sensor nodes are randomly distributed in 100 × 100 m2 field and the location of the sink node is also randomly chosen. Each simulation was run under 100 different topologies, and we show the average results. In each simulation, the speed of the ME was set to 1 m/s according to the practical experience in packBot system [33], and parameters of sensor nodes were set according to the data sheet of the CC1000 radio on MICA2 motes [34]. Each sensor node generates 2 bytes of sensory data per second, and the transmission rate of it is 40 kb/s. The transmission range of a sensor node was set to 20 m. We assume that the initial energy of all nodes is 100 J, and the energy consumption of the transmitter and receiver circuit of a node is 40 mW and 25 mW, respectively. The parameters are summarized in Table 1. In the simulations, a local-search-based heuristic TSP solver [35] was used.Table 1
Simulation parameters.
Parameter
Value
ME speed
1 m/s
Sensor node transmission range
20 m
Sensor node data sampling rate
2 B/s
Sensor node transmission rate
40 kb/s
Energy consumption of transmitter
40 mW
Energy consumption of receiver
25 mW
Initial energy of sensor nodes
100


### 5.1. Comparison of the Proposed Optimal and Heuristic Algorithms

First, the performance of the proposed optimal and heuristic algorithms was compared. Since the computation complexity of the optimal algorithm is very high, we evaluated the performance in a small scale WSN. In this simulation, packet delivery delayD is 100 s and the number of sensor nodes is 50. We set the threshold σ to different values to measure its impact on the performance and complexity of the heuristic algorithm and find a proper value for σ. The simulation results are shown in Figures 5 and 6.Figure 5
The optimal algorithm versus the heuristic algorithm with differentσ.Figure 6
k
m
a
x with different σ.In Figure5, we can see that as the threshold σ decreases the performance of the heuristic algorithm approaches the optimal one. When σ decreases from 10−3 to 10−4, there is almost no performance improvement. However, as we can see in Figure 6, the corresponding value of kmax increases sharply as σ decreases from 10−3 to 10−4; and when σ reaches 10−4, kmax no longer increases because kmax already equals the number of all found RP sets. Consequently, setting σ to 10−4 will result in an excess of computation and 10−3 is a proper value for σ. We suggest setting the threshold σ to 10−3 in real implementations.


### 5.2. Comparison of the Proposed Heuristic Algorithm and Existing Algorithms

Next, we compare the proposed heuristic algorithm with WRP [11] and the algorithm proposed by Konstantopoulos et al. [13] in a larger scale WSN. The algorithm proposed by Konstantopoulos et al. reselects RPs periodically. We set this period to 5000 seconds. The value of σ and the maximum packet delivery delay were set to 10−3 and 100 s, respectively. First we evaluate the performance with different numbers of sensor nodes. As shown in Figure 7, the simulation result shows that the performance of the proposed heuristic algorithm is better than that of the two existing ones. On average, the network lifetime achieved by our algorithm is about 3 times of that of WRP and about 10% longer than that of the algorithm of Konstantopoulos et al. [13].Figure 7
Impact of the number of sensor nodes.We fixed the number of sensor nodes to 200 and ran the simulation again with different values for the packet delivery delay limitD to see its impact. The simulation result is shown in Figure 8. When D is too low (less than 40 s in the simulation) for the ME to visit a node at level 2, only nodes at level 1 can be set as RPs, which serves no purpose since they can transmit data to the sink directly. As D increases, nodes farther away from the sink can be set as RPs and more RPs can share the traffic at the same time. As a result, the energy consumption of RPs decreases and the network lifetime is extended. With a longer D, the benefit of using multiple sets of RPs is more apparent. This is because we can find more feasible RP sets to average the energy consumption of RPs. As we can see, when D is from 120 s to 200 s, the network lifetime of the proposed heuristic algorithm is about 2 times of that of WRP and the performance gain is about threefold when D is from 200 s to 280 s. The performance of our algorithm is also about 10% higher than that of the algorithm proposed by Konstantopoulos et al. [13].Figure 8
Impact of the packet delivery delay limit.


## 5.1. Comparison of the Proposed Optimal and Heuristic Algorithms

First, the performance of the proposed optimal and heuristic algorithms was compared. Since the computation complexity of the optimal algorithm is very high, we evaluated the performance in a small scale WSN. In this simulation, packet delivery delayD is 100 s and the number of sensor nodes is 50. We set the threshold σ to different values to measure its impact on the performance and complexity of the heuristic algorithm and find a proper value for σ. The simulation results are shown in Figures 5 and 6.Figure 5
The optimal algorithm versus the heuristic algorithm with differentσ.Figure 6
k
m
a
x with different σ.In Figure5, we can see that as the threshold σ decreases the performance of the heuristic algorithm approaches the optimal one. When σ decreases from 10−3 to 10−4, there is almost no performance improvement. However, as we can see in Figure 6, the corresponding value of kmax increases sharply as σ decreases from 10−3 to 10−4; and when σ reaches 10−4, kmax no longer increases because kmax already equals the number of all found RP sets. Consequently, setting σ to 10−4 will result in an excess of computation and 10−3 is a proper value for σ. We suggest setting the threshold σ to 10−3 in real implementations.


## 5.2. Comparison of the Proposed Heuristic Algorithm and Existing Algorithms

Next, we compare the proposed heuristic algorithm with WRP [11] and the algorithm proposed by Konstantopoulos et al. [13] in a larger scale WSN. The algorithm proposed by Konstantopoulos et al. reselects RPs periodically. We set this period to 5000 seconds. The value of σ and the maximum packet delivery delay were set to 10−3 and 100 s, respectively. First we evaluate the performance with different numbers of sensor nodes. As shown in Figure 7, the simulation result shows that the performance of the proposed heuristic algorithm is better than that of the two existing ones. On average, the network lifetime achieved by our algorithm is about 3 times of that of WRP and about 10% longer than that of the algorithm of Konstantopoulos et al. [13].Figure 7
Impact of the number of sensor nodes.We fixed the number of sensor nodes to 200 and ran the simulation again with different values for the packet delivery delay limitD to see its impact. The simulation result is shown in Figure 8. When D is too low (less than 40 s in the simulation) for the ME to visit a node at level 2, only nodes at level 1 can be set as RPs, which serves no purpose since they can transmit data to the sink directly. As D increases, nodes farther away from the sink can be set as RPs and more RPs can share the traffic at the same time. As a result, the energy consumption of RPs decreases and the network lifetime is extended. With a longer D, the benefit of using multiple sets of RPs is more apparent. This is because we can find more feasible RP sets to average the energy consumption of RPs. As we can see, when D is from 120 s to 200 s, the network lifetime of the proposed heuristic algorithm is about 2 times of that of WRP and the performance gain is about threefold when D is from 200 s to 280 s. The performance of our algorithm is also about 10% higher than that of the algorithm proposed by Konstantopoulos et al. [13].Figure 8
Impact of the packet delivery delay limit.


## 6. Conclusion

In this paper, we studied the problem of using multiple sets of RPs in turn to maximize the lifetime of WSN. We proposed an optimal algorithm and a heuristic algorithm for this problem. The computation complexity of the optimal algorithm is very high and is only suitable for small scale WSN. The heuristic algorithm can approach the optimal performance with much lower complexity in a large scale WSN, and we can adjust the thresholdσ to balance its complexity and performance. The threshold σ, the number of sensor nodes, and the packet delivery delay D have a strong impact on the performance of the proposed algorithms. Simulation results show that 10−3 is a proper value for the threshold σ. Additionally, the heuristic algorithm approaches the optimal one and can achieve a longer network lifetime than WRP as well as the algorithm proposed by Konstantopoulos et al. [13]. When the number of sensor nodes is 200 and D is from 200 s to 280 s, the network lifetime of the heuristic algorithm is about 3 times that of WRP and about 10% longer than that of Konstantopoulos et al.



---

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