# Designing Constrained Trajectory Based on Maximizing Energy Reduction in Large-Scale Wireless Sensor Networks

Authors: Jia Xu; Chuan Ping Wang; Hua Dai; Da Qiang Zhang; Jing Jie Yu
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

TheMobile Sink based data collection in wireless sensor network can reduce energy consumption efficiently and has been a new data collection paradigm. In this paper, we focus on exploring polynomial algorithm to compute the constrained trajectory of the Mobile Sink for data collection. We first present a universal system model for designing constrained trajectory in large-scale wireless sensor networks and formulate the problem as the Maximizing Energy Reduction for Constrained Trajectory (MERC) problem. We show that the MERC problem is NP-hard and design an approximation algorithm (CTMER), which follows the greedy approach to design the movement trajectory of the Mobile Sink by maximizing the effective average energy reduction. Through both rigid theoretical analysis and extensive simulations, we demonstrate that our algorithm achieves high computation efficiency and is superior to other Mobile Sink based data collection methods in aspects of energy consumption and network lifetime.


---

## Body

## 1. Introduction

With the development of digital electronics, wireless communications, and network technology, the applications of wireless sensor networks [1, 2] (referred to as WSNs) are becoming more widespread, including monitoring, event detection, and target tracking. In these applications, the sensor nodes mainly perform three aspects of the jobs: (1) collecting the required data from the environment sensing; (2) the data store or process; and (3) sending or forwarding data from other nodes to the data collection node ultimately, for example, sink node or base station.In the traditional static wireless sensor network topology, the position of sink node is fixed; thus, the sink node and its surrounding sensor nodes need to transmit a larger amount of data and are likely to die prematurely due to energy exhaustion, which will be the energy bottleneck of large-scale WSNs [3]. In the static network topology, dealing with the energy problem is intractable in sensor network. In recent years, the data collection mode based on theMobile Sinks has been proposed, in which one or moreMobile Sinks moved along a specific path in order to reduce the amount of forwarding. This is an efficient way to reduce the energy consumption of the sensor node itself and to make the energy consumption more evenly in large-scale network. In large-scale wireless sensor network, most nodes need to forward data through multihop; thus, the problem of how to reduce the number of forwarding hops in order to reduce the energy consumption has become a key issue. In the extreme case, theMobile Sink can visit each node in WSNs (called flat collection), and the distance between each node and theMobile Sink is only one hop. Obviously, the sensor nodes have the minimum energy consumption in this case; however, the delay of data collection will be the maximum; thus, the flat collection is not suitable for large-scale sensor networks. There is a possible solution which tolerates a certain delay to reduce the energy consumption. Many efforts [4–13] have been made to design the trajectory of theMobile Sink. However, few of them focus on maximizing energy reduction.In this paper, we design a data collection method based on theMobile Sink to maximize the energy reduction in large-scale WSNs, in which the set of sensor nodes is divided into the sets ofcollection trees. The roots of thecollection tree are calledcollection node, and the remaining sensor nodes forward the data to the correspondingcollection node. TheMobile Sink visits allcollection nodes to obtain data from the whole network eventually.The key contributions of our work are summarized in the following:(i)
We present the system model for data collection in large-scale wireless sensor networks and formulate the movement trajectory design problem asMaximizing Energy Reduction for Constrained Trajectory (MERC) problem.(ii)
We show theMERC problem is NP-hard and develop an approximation algorithm,Constrained Trajectory based on Maximizing Energy Reduction (CTMER), which follows a greedy approach with polynomial time.(iii)
We conduct thorough simulations to investigate the performance of CTMER. The simulation results show that CTMER is superior to other hierarchical data collection methods in aspects of energy consumption and network lifetime.


## 2. Related Work

The data collection methods based on the mobile infrastructure have been widely studied in recent years. Shah proposed a protocol using Data Mule [14] to collect sensor data in the sparse WSNs. In the scenario of Data Mule, any moving object with the communication function can be used as the mobile infrastructure, such as human, animal, or vehicle with the communication device. As the mobile infrastructures need to collect the data from all the sensors, they should have more energy and larger storage space.Some universities and research institutions designed the mobile machines or collection vehicles for the data collection in WSNs. University of Southern California designed the mobile node Robomote [15], and Yale University designed the mobile node XYZ [16]. In addition, UCLA designed Packbot [17], and Richard et al. designed NIMS [18]. Zhang et al. designed the MDC—DataTruck [19]. These nodes can be used as theMobile Sinks.Paper [4] first proposed the concept of predicting the mobility of theMobile Sink to improve performance of the sensor network. The sink nodes are placed on the bus cycle operation, and the sensor nodes are randomly distributed in the sides of the bus operation route. Due to the limit of the movement trajectory of the sink node and the effective communication distance, not all of the sensor nodes can communicate with the sink node directly in the practical applications.Paper [5] described a road monitoring application and analyzed the trade-off between the data collection and energy in the sparse sensor networks. But it also adopts the single-hop communication as the data transfer mode of nodes.Paper [6] proposed a data collection method, MASP, which generates the shortest path with the maximum amount of data. MASP focuses on optimization of the relationship between the members of the nodes in the network and theMobile Sink and adopts the 0-1 linear programming to formalize the MASP problem. The authors proposed a genetic algorithm based on two-dimensional chromosome encoding and designed the corresponding data communication protocol. However, it ignores the movement trajectory of theMobile Sink. Moreover, the time complexity can be very high.Paper [7] proposed a learning based time-domain routing algorithm (HLETDR). The algorithm emphasized that theMobile Sink accesses the fixed sensor nodes (moles) periodically, and the probability of theMobile Sink at the current time domain is predicted in the moles. However, HLETDR did not give the solution to deal with latency problem of the data collection.RD-VT [8] is an approach to design base station (BS) tour through constructing MST (Minimum Spanning Tree) and SMT (Steiner Minimum Tree). The objective of RD-VT is to find a tour of the BS that visits a set of nodes referred to asrendezvous points (RPs) with constrained length of BS tour while minimizing the total Euclidean distance of edges in the routing trees.The Line-Based Data Dissemination (LBDD) [9] supposes that there are multiple sinks moving randomly in the sensor field and defines a vertical line or strip, which divides the sensor field into two equal parts. The nodes within the boundary of this wide line are calledinline-nodes. This line acts as a rendezvous area for data storage and lookup. When a sensor detects a new event, it transmits a data report towards the virtual line. This data is stored on the firstinline-node encountered. To collect the generated data reports, the sink sends its query towards the rendezvous area. The query is then propagated along the virtual line until arriving to theinline-node that owns the requested data. However, LBDD is unsuitable for periodic data collection scenarios due to the communication cost.In Quad tree-based Data Dissemination (QDD) [10] protocol, a common hierarchy of data forwarding nodes is created by the data forwarding nodes using quad tree-based partitioning of the physical network into successive quadrants. In this approach, when a source node detects a new event, it calculates a set ofrendezvous points by successively partitioning the sensor field into four equally logical quadrants. And the data reports are sent to the nodes which are closer to the centroid of each successive partition. TheMobile Sink follows the same strategy for the query packet transmission. The main drawback of this approach is that therendezvous points in high lever will suffer high overhead, and the related hot spot problem may decrease the network lifetime and reliability. Moreover, there is no length limit of theMobile Sink trajectory or deadline of data collection. This assumption may be not reasonable in practice.In paper [13], the Combine-Skip-Substitute (CSS) scheme is proposed to minimize the tour length of mobile elements. In CSS, all sensor nodes are covered by the tour within a distance of d. However, CSS does not take the length constraint of tour into account and thus cannot be applied to delay sensitivity scenarios.The Mobility assisted Energy efficient Georouting in energy harvesting Actuator and sensor Networks (MEGAN) [20] is a geographical routing, which reduces energy consumption through moving the sensor nodes toward the positions in the forward direction. However, not all movements of sensor nodes can be controlled in practice.Paper [21] studies the problem of controlling sink mobility in deadline-based and event-driven applications to achieve maximum network lifetime and proposes an algorithm based on a decision tree and dynamic programming to approximately determine an optimal deadline-based trajectory (ODT). The algorithm assumes that each sensor node can adjust its transmission range; however, this assumption may be invalid in many applications.


## 3. System Model and Problem Formulation

### 3.1. System Model

We consider a set of static sensor nodesV=v1,v2,v3,…,vn randomly distributed in m×m area densely. Each sensor nodevi,i={1,…,n}, can obtain its position information. There is aMobile Sink in the network. TheMobile Sink collects data along a specific trajectory M and moves with a constant speed C, which is significantly slower than the data transmission speed. The more detailed descriptions about the value of C can be found inRobomote [15],NIMs [18], andPackbot [17]. In every time period T, each sensor node will produce q bit data, which must be forwarded to theMobile Sink, and then theMobile Sink returns to the original position within the T. To reduce the energy consumption and increase the network scalability, a set ofcollection nodes, VS={vS1,vS2,…,vSVS}, are selected from the sensor node set V in the network. The remaining set of sensor nodes is callednormal node set: VR={vR1,vR2,…,vR|VR|}, V=VS∪VR. Anynormal nodevRi∈VR needs to send data to the correspondingcollection nodeS(vRi)∈VS. Specifically, S(vSi)=vSi, and, for all vi, only onecollection node corresponds to vi. The trajectory M of theMobile Sink is composed of all nodes in VS with the particular sequence. Figure 1 shows an example ofMobile Sink based data collection in large-scale wireless sensor networks.Figure 1
TheMobile Sink based data collection in large-scale wireless sensor networks.This paper does not consider the issue of power control and assumes that all sensor nodes adopt the fixed transmitted power and received power; thus, the energy consumption is not related to the length between nodes. We adopt the energy consumption model described in [11, 22]. Within the single time period T, the energy consumption of any sensor nodesvi is Ei≈a(pri+pti), where pri presents the amount of received data and pti presents the amount of data sent by vi, and a is a constant, which presents the energy consumption for sending or receiving one bit of data. In the energy consumption model, the following relation holds: pti=pri+q, where q presents the total amount of the data generated in any node vi within T. The amount of received data for all sensor nodes in the network within T is ∑i=1npri=∑i=1nhi·q, where hi presents the number of hops from thenormal nodevi to S(vi). Then the total energy within the single time period T is(1)Etotal=∑i=1nEi=∑i=1na2hi+1·q.


### 3.2. Problem Formulation

According to formula (1), we can reduce energy consumption by reducing the hops from thenormal nodes to the correspondingcollection nodes. We choose an ordered set ofcollection nodesVS from the network and make each vSi,i∈{1,2,…,|VS|}, to be the root of thecollection tree in order to reduce the total energy consumption of the network. Consider that Qi=Etotal-Etotal′>0 is energy reduction if we choose node vi as thecollection node within the single time period T, where Etotal′ is the total energy consumption within the single time period if we choose node vi as thecollection node. When putting vi into VS, Qj may be changed for each node vj∈V∖VS, where V∖VS is the set of sensor nodes that are out of VS.Our objective is to design the trajectoryM of theMobile Sink to complete data collection for all sensor nodes and return back to the original position within the time period T with maximum total energy reduction. We call this problemMaximizing Energy Reduction for Constrained Trajectory (MERC), which can be formalized as follows:decision variables:(2)xij=1,vi,vjis  on  theM,0,Otherwise,i,j=1,…,n,objective function:(3)max∑i=1n-1∑j=2nQjxij,constraints:(4)∑j=2nx1j=∑i=2n-1xi1=1,(5)∑i=1n-1xik=∑j=2nxkj≤1;∀k=2,…,n-1,(6)∑i=1n-1∑j=2nlijxij≤C·T,where (vi,vj) is the path from vi to vj and lij is the corresponding Euclidean distance.The objective function (3) makes M to maximize the energy reduction. Constraint (4) presents that theMobile Sink moves from the original position and returns to the original position finally. Constraint (5) presents that there is connectivity among the sensor nodes and each sensor node can only be accessed once in T. Constraint (6) presents the length constraint of M.


## 3.1. System Model

We consider a set of static sensor nodesV=v1,v2,v3,…,vn randomly distributed in m×m area densely. Each sensor nodevi,i={1,…,n}, can obtain its position information. There is aMobile Sink in the network. TheMobile Sink collects data along a specific trajectory M and moves with a constant speed C, which is significantly slower than the data transmission speed. The more detailed descriptions about the value of C can be found inRobomote [15],NIMs [18], andPackbot [17]. In every time period T, each sensor node will produce q bit data, which must be forwarded to theMobile Sink, and then theMobile Sink returns to the original position within the T. To reduce the energy consumption and increase the network scalability, a set ofcollection nodes, VS={vS1,vS2,…,vSVS}, are selected from the sensor node set V in the network. The remaining set of sensor nodes is callednormal node set: VR={vR1,vR2,…,vR|VR|}, V=VS∪VR. Anynormal nodevRi∈VR needs to send data to the correspondingcollection nodeS(vRi)∈VS. Specifically, S(vSi)=vSi, and, for all vi, only onecollection node corresponds to vi. The trajectory M of theMobile Sink is composed of all nodes in VS with the particular sequence. Figure 1 shows an example ofMobile Sink based data collection in large-scale wireless sensor networks.Figure 1
TheMobile Sink based data collection in large-scale wireless sensor networks.This paper does not consider the issue of power control and assumes that all sensor nodes adopt the fixed transmitted power and received power; thus, the energy consumption is not related to the length between nodes. We adopt the energy consumption model described in [11, 22]. Within the single time period T, the energy consumption of any sensor nodesvi is Ei≈a(pri+pti), where pri presents the amount of received data and pti presents the amount of data sent by vi, and a is a constant, which presents the energy consumption for sending or receiving one bit of data. In the energy consumption model, the following relation holds: pti=pri+q, where q presents the total amount of the data generated in any node vi within T. The amount of received data for all sensor nodes in the network within T is ∑i=1npri=∑i=1nhi·q, where hi presents the number of hops from thenormal nodevi to S(vi). Then the total energy within the single time period T is(1)Etotal=∑i=1nEi=∑i=1na2hi+1·q.


## 3.2. Problem Formulation

According to formula (1), we can reduce energy consumption by reducing the hops from thenormal nodes to the correspondingcollection nodes. We choose an ordered set ofcollection nodesVS from the network and make each vSi,i∈{1,2,…,|VS|}, to be the root of thecollection tree in order to reduce the total energy consumption of the network. Consider that Qi=Etotal-Etotal′>0 is energy reduction if we choose node vi as thecollection node within the single time period T, where Etotal′ is the total energy consumption within the single time period if we choose node vi as thecollection node. When putting vi into VS, Qj may be changed for each node vj∈V∖VS, where V∖VS is the set of sensor nodes that are out of VS.Our objective is to design the trajectoryM of theMobile Sink to complete data collection for all sensor nodes and return back to the original position within the time period T with maximum total energy reduction. We call this problemMaximizing Energy Reduction for Constrained Trajectory (MERC), which can be formalized as follows:decision variables:(2)xij=1,vi,vjis  on  theM,0,Otherwise,i,j=1,…,n,objective function:(3)max∑i=1n-1∑j=2nQjxij,constraints:(4)∑j=2nx1j=∑i=2n-1xi1=1,(5)∑i=1n-1xik=∑j=2nxkj≤1;∀k=2,…,n-1,(6)∑i=1n-1∑j=2nlijxij≤C·T,where (vi,vj) is the path from vi to vj and lij is the corresponding Euclidean distance.The objective function (3) makes M to maximize the energy reduction. Constraint (4) presents that theMobile Sink moves from the original position and returns to the original position finally. Constraint (5) presents that there is connectivity among the sensor nodes and each sensor node can only be accessed once in T. Constraint (6) presents the length constraint of M.


## 4. Constrained Trajectory Based on Maximizing Energy Reduction

### 4.1. Complexity Analysis of MERC Problem

First of all, we attempt to find a computable feasible algorithm for theMERC problem. Unfortunately, as the following lemma shows, it is NP-hard to find the optimal solution even Qi for each node vi is a constant, called staticMERC conveniently.Lemma 1.
The static MERC problem is NP-hard.Proof.
We demonstrate that static MERC belongs to NP firstly. Given an instance of static MERC, we can check whether the length ofM is no more than C·T and check whether the total reduction of energy is no less than k. This process can be ended up in polynomial time.
Next, we prove static MERC is NP-hard by giving a polynomial time reduction from the NP-hard Orienteering Problem [12], OP.
Instance of OP (denoted byA): for a graph G=(V,A), where V={v1,…,vn} is the vertex set and A is the arc set. The nonnegative score Si is associated with each vertex vi∈V and the travel time tij is associated with each arc aij∈A. For a positive real k, the question is whether Hamiltonian path G′(⊂G) exists over a subset of V, such that the sum of score for each vertex in G′ is no less than k, including preset start (v1) and end (v1) vertex with total travel time no more than Tmax.
We consider a corresponding instance of static MERC (denoted byB): for a graph G=(V,A), where V={v1,…,vn} is the sensor node set and A is the arc set. The nonnegative reduction of energy Qi is associated with each sensor node vi∈V and the Euclidean distance lij is associated with each arc aij∈A. For positive real k, C, and T, the question is whether Hamiltonian path (trajectory) G′(⊂G) exists over a subset of V, such that the sum of reduction of energy for all sensor nodes in G′ is no less than k, including preset start (v1) and end (v1) vertex with path length no more than C·T.
This reduction fromA to B ends in polynomial time. We can simply see that r is a solution of A if and only if r is a solution of B.It is obvious that the MERC problem with dynamicQi is not easier than the static MERC problem. Thus, we have the following theorem.Theorem 2.
The MERC problem is NP-hard.


### 4.2. CTMER Design

Since theMERC problem is NP-hard, we turn our attention to develop an approximation algorithm. Given the time period T, the movement speed of theMobile SinkC, the set of sensor nodes V, and a position vector pos=(pos0,pos1,…,posn), in which pos0 is the original position ofMobile Sink, and posi,i∈{1,…,n}, are position of sensor node vi, the algorithm R(C,T,V,pos) returns an ordered set VS, which contains all selectedcollection nodes, and the length of trajectory L=|M|.The design rationale is that CTMER first generates originalcollection trees based on the original position of theMobile Sink, and the roots of the originalcollection trees are the initialcollection nodes. And then CTMER iteratively selects the nodes withmaximum effective average energy reduction in current topology state as thecollection nodes. As illustrated in Algorithm 1, CTMER follows a greedy approach to solveMERC problem and designs the movement trajectory of theMobile Sink before running.Algorithm 1:CTMER.
Input: time period T, movement speed of Mobile SinkC, the set of sensor nodes V, and position vector pos
Output: ordered set VS, L
(1)VS←⌀, L←0
(2)Initialize(V, pos0);
(3)while  L<C⋅T  do
(4)foreach node vi in V∖VS  do  ΔLi=TSPVS∪i-TSPVS;
(5)j=arg⁡maxi∈V∖VS⁡numi⋅hi/ΔLi;
(6)L←L+ΔLj;
(7)if  L≤C⋅T  then
(8)VS←VS∪vj;
(9)Cut(V, vj);
(10)else
(11)L←L-ΔLj;
(12)end if
(13)end while
(14)return (VS, L);CTMER uses the functionInitialize to generate the original topology of the sensor network. As illustrated in Algorithm 2, the functionInitialize will construct originalcollection trees, whose roots are located in the one hop range from theMobile Sink at position pos0. Many methods can constructcollection trees, and we will give an instance in Section 4.3.Algorithm 2:
Initialize.
Input: the set of sensor nodes V, the start position of the Mobile Sinkpos0
Output: num, h
(1) Initialize collection trees based onpos0;
(2)foreach node vi in V  do
(3)hi ← hop count from Svi to vi;
(4)numi ← the number of nodes in Treevi;
(5)end for
(6)return (num, h);Considering each nodevi∈V with energy reduction, Qi, if theMobile Sink visits vi, vi would be a newcollection node, and the correspondingcollection treeTree(vi) with root vi can be structured. We call this operation asCut for briefness. Obviously, when performing theCut operation in position vi, we have Qi=numi·hi, where numi is the number of nodes in thecollection treeTree(vi) and hi is the hop count from vi to (vi) beforeCut operation. CTMER puts the node vi into ordered set VS iteratively based oneffective average energy reduction, Qi/ΔLi, until the nextCut operation will make L>C·T. ΔLi is the increased length of M, that is, the increased length ofTSP circuit when theMobile Sink visits vi.When performing aCut operation, a newcollection tree is structured, and the topology changed correspondingly. Without loss of generality, considering that vj is selected as a newcollection node, the impact of thisCut operation is restricted to the nodes located in the path from Svjtovj and the nodes located in Tree (vj). TheCut operation is illustrated in Algorithm 3.Algorithm 3:
Cut.
Input: the set of sensor nodes V, the sensor node vj
Output: num, h
(1)foreach node vi in the path from Svj to vj  do  numi←numi-numj;
(2)foreach node vi in Tree(vj) with nondecreasing order of numi  do  hi←hi-hj;
(3)return (num, h);


### 4.3. An Instance of Collection Tree Construction

To design the movement trajectory ofMobile Sink, it is necessary to generate the original topology of the sensor network, which can be generated through many different methods. Even so, we give an instance ofcollection tree construction, which performs in Algorithm 2 (Line 1).We consider theMobile Sink is in arbitrary position pos0 and use the example in Figure 2 to illustrate how the instance works. There are 22 sensor nodes and oneMobile Sink, and all sensor nodes have the same transmission range, which are presented as dashed annulus. TheMobile Sink sends a message to the neighbor sensor nodes (within one hop distance), and each node, which received the message, forwards the message to its neighbors again and sends an acknowledgement to theMobile Sink by the reverse path. This process continues until theMobile Sink received all nodes’ acknowledgements. Finally, the originalcollection trees can be constructed, and the nodes within theMobile Sink’s one hop distance are initialized as thecollection nodes. Figure 3 shows thecollection trees in this instance. By the above interactive process, it is not different to get numi, hi, and Qi, which have been listed in Table 1, for each node vi in network.Table 1
num
i, hi, and Qi for each node vi in the example.
i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
num
i
2
4
1
1
2
1
4
1
2
1
4
1
2
1
7
4
2
2
1
1
1
7
h
i
1
1
2
2
2
3
0
1
1
2
0
1
1
2
0
1
1
2
3
2
2
0
Q
i
2
4
2
2
4
3
0
1
2
2
0
1
2
2
0
4
2
4
3
2
2
0Figure 2
An instance of sensor network with oneMobile Sink and 22 sensor nodes.Figure 3
The collection trees initialized in our instance.


### 4.4. Computational Efficiency of CTMER

The computational efficiency of trajectory design algorithm is important in large-scale wireless sensor networks. We have the following theorem about the computational efficiency of CTMER.Theorem 3.
CTMER is computationally efficient.Proof.
The functionInitialize (Line 2) takes O(n2) time. Since CTMER performs cut operation for each node in V at most once, the while-loop (Lines 3–13) takes O(n) time. CTMER calculates the TSP circuit for each node in V∖VS. Since we use the Euclidean distance, theTSP circuit can be achieved in O(n2) within 2 approximations. Thus, the for-loop (Line 4) takes O(n3) time. Finding the maximum effective average energy reduction (Line 5) takes O(n) time. TheCut operation (Line 9) takes O(n) time. Hence, the running time of the whole CTMER is bounded by O(n4).Note that the running time of CTMER,O(n4), is very conservative since the number ofcollection nodes is much less than n in practice. Moreover, the accurate complexity of the for-loop (Line 4) is ∑i=0ni2=nn+1(2n+1)/6 since CTMER only calculates theTSP circuit containing VS∪i for the nodes in V∖VS.


## 4.1. Complexity Analysis of MERC Problem

First of all, we attempt to find a computable feasible algorithm for theMERC problem. Unfortunately, as the following lemma shows, it is NP-hard to find the optimal solution even Qi for each node vi is a constant, called staticMERC conveniently.Lemma 1.
The static MERC problem is NP-hard.Proof.
We demonstrate that static MERC belongs to NP firstly. Given an instance of static MERC, we can check whether the length ofM is no more than C·T and check whether the total reduction of energy is no less than k. This process can be ended up in polynomial time.
Next, we prove static MERC is NP-hard by giving a polynomial time reduction from the NP-hard Orienteering Problem [12], OP.
Instance of OP (denoted byA): for a graph G=(V,A), where V={v1,…,vn} is the vertex set and A is the arc set. The nonnegative score Si is associated with each vertex vi∈V and the travel time tij is associated with each arc aij∈A. For a positive real k, the question is whether Hamiltonian path G′(⊂G) exists over a subset of V, such that the sum of score for each vertex in G′ is no less than k, including preset start (v1) and end (v1) vertex with total travel time no more than Tmax.
We consider a corresponding instance of static MERC (denoted byB): for a graph G=(V,A), where V={v1,…,vn} is the sensor node set and A is the arc set. The nonnegative reduction of energy Qi is associated with each sensor node vi∈V and the Euclidean distance lij is associated with each arc aij∈A. For positive real k, C, and T, the question is whether Hamiltonian path (trajectory) G′(⊂G) exists over a subset of V, such that the sum of reduction of energy for all sensor nodes in G′ is no less than k, including preset start (v1) and end (v1) vertex with path length no more than C·T.
This reduction fromA to B ends in polynomial time. We can simply see that r is a solution of A if and only if r is a solution of B.It is obvious that the MERC problem with dynamicQi is not easier than the static MERC problem. Thus, we have the following theorem.Theorem 2.
The MERC problem is NP-hard.


## 4.2. CTMER Design

Since theMERC problem is NP-hard, we turn our attention to develop an approximation algorithm. Given the time period T, the movement speed of theMobile SinkC, the set of sensor nodes V, and a position vector pos=(pos0,pos1,…,posn), in which pos0 is the original position ofMobile Sink, and posi,i∈{1,…,n}, are position of sensor node vi, the algorithm R(C,T,V,pos) returns an ordered set VS, which contains all selectedcollection nodes, and the length of trajectory L=|M|.The design rationale is that CTMER first generates originalcollection trees based on the original position of theMobile Sink, and the roots of the originalcollection trees are the initialcollection nodes. And then CTMER iteratively selects the nodes withmaximum effective average energy reduction in current topology state as thecollection nodes. As illustrated in Algorithm 1, CTMER follows a greedy approach to solveMERC problem and designs the movement trajectory of theMobile Sink before running.Algorithm 1:CTMER.
Input: time period T, movement speed of Mobile SinkC, the set of sensor nodes V, and position vector pos
Output: ordered set VS, L
(1)VS←⌀, L←0
(2)Initialize(V, pos0);
(3)while  L<C⋅T  do
(4)foreach node vi in V∖VS  do  ΔLi=TSPVS∪i-TSPVS;
(5)j=arg⁡maxi∈V∖VS⁡numi⋅hi/ΔLi;
(6)L←L+ΔLj;
(7)if  L≤C⋅T  then
(8)VS←VS∪vj;
(9)Cut(V, vj);
(10)else
(11)L←L-ΔLj;
(12)end if
(13)end while
(14)return (VS, L);CTMER uses the functionInitialize to generate the original topology of the sensor network. As illustrated in Algorithm 2, the functionInitialize will construct originalcollection trees, whose roots are located in the one hop range from theMobile Sink at position pos0. Many methods can constructcollection trees, and we will give an instance in Section 4.3.Algorithm 2:
Initialize.
Input: the set of sensor nodes V, the start position of the Mobile Sinkpos0
Output: num, h
(1) Initialize collection trees based onpos0;
(2)foreach node vi in V  do
(3)hi ← hop count from Svi to vi;
(4)numi ← the number of nodes in Treevi;
(5)end for
(6)return (num, h);Considering each nodevi∈V with energy reduction, Qi, if theMobile Sink visits vi, vi would be a newcollection node, and the correspondingcollection treeTree(vi) with root vi can be structured. We call this operation asCut for briefness. Obviously, when performing theCut operation in position vi, we have Qi=numi·hi, where numi is the number of nodes in thecollection treeTree(vi) and hi is the hop count from vi to (vi) beforeCut operation. CTMER puts the node vi into ordered set VS iteratively based oneffective average energy reduction, Qi/ΔLi, until the nextCut operation will make L>C·T. ΔLi is the increased length of M, that is, the increased length ofTSP circuit when theMobile Sink visits vi.When performing aCut operation, a newcollection tree is structured, and the topology changed correspondingly. Without loss of generality, considering that vj is selected as a newcollection node, the impact of thisCut operation is restricted to the nodes located in the path from Svjtovj and the nodes located in Tree (vj). TheCut operation is illustrated in Algorithm 3.Algorithm 3:
Cut.
Input: the set of sensor nodes V, the sensor node vj
Output: num, h
(1)foreach node vi in the path from Svj to vj  do  numi←numi-numj;
(2)foreach node vi in Tree(vj) with nondecreasing order of numi  do  hi←hi-hj;
(3)return (num, h);


## 4.3. An Instance of Collection Tree Construction

To design the movement trajectory ofMobile Sink, it is necessary to generate the original topology of the sensor network, which can be generated through many different methods. Even so, we give an instance ofcollection tree construction, which performs in Algorithm 2 (Line 1).We consider theMobile Sink is in arbitrary position pos0 and use the example in Figure 2 to illustrate how the instance works. There are 22 sensor nodes and oneMobile Sink, and all sensor nodes have the same transmission range, which are presented as dashed annulus. TheMobile Sink sends a message to the neighbor sensor nodes (within one hop distance), and each node, which received the message, forwards the message to its neighbors again and sends an acknowledgement to theMobile Sink by the reverse path. This process continues until theMobile Sink received all nodes’ acknowledgements. Finally, the originalcollection trees can be constructed, and the nodes within theMobile Sink’s one hop distance are initialized as thecollection nodes. Figure 3 shows thecollection trees in this instance. By the above interactive process, it is not different to get numi, hi, and Qi, which have been listed in Table 1, for each node vi in network.Table 1
num
i, hi, and Qi for each node vi in the example.
i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
num
i
2
4
1
1
2
1
4
1
2
1
4
1
2
1
7
4
2
2
1
1
1
7
h
i
1
1
2
2
2
3
0
1
1
2
0
1
1
2
0
1
1
2
3
2
2
0
Q
i
2
4
2
2
4
3
0
1
2
2
0
1
2
2
0
4
2
4
3
2
2
0Figure 2
An instance of sensor network with oneMobile Sink and 22 sensor nodes.Figure 3
The collection trees initialized in our instance.


## 4.4. Computational Efficiency of CTMER

The computational efficiency of trajectory design algorithm is important in large-scale wireless sensor networks. We have the following theorem about the computational efficiency of CTMER.Theorem 3.
CTMER is computationally efficient.Proof.
The functionInitialize (Line 2) takes O(n2) time. Since CTMER performs cut operation for each node in V at most once, the while-loop (Lines 3–13) takes O(n) time. CTMER calculates the TSP circuit for each node in V∖VS. Since we use the Euclidean distance, theTSP circuit can be achieved in O(n2) within 2 approximations. Thus, the for-loop (Line 4) takes O(n3) time. Finding the maximum effective average energy reduction (Line 5) takes O(n) time. TheCut operation (Line 9) takes O(n) time. Hence, the running time of the whole CTMER is bounded by O(n4).Note that the running time of CTMER,O(n4), is very conservative since the number ofcollection nodes is much less than n in practice. Moreover, the accurate complexity of the for-loop (Line 4) is ∑i=0ni2=nn+1(2n+1)/6 since CTMER only calculates theTSP circuit containing VS∪i for the nodes in V∖VS.


## 5. Performance Evaluation

### 5.1. Simulation Setup

We implement CTMER on the MATLAB platform and compare our protocol to RD-VT (with a variable BS track), QDD (with oneMobile Sink), and LBDD (with oneMobile Sink using the progressive-footprint-chaining strategy) in order to investigate the performance of CTMER. We list the default parameter setting in Table 2. Each measurement is averaged over 200 instances.Table 2
Simulation parameters.
Parameter
Value
Network size (m2)
500 × 500
Number of sensor nodes
1000
Initial energy of each sensor node (J)
2
Initial energy of theMobile Sink(J)
1 × 106
Unit energy consumption (J/bit)
5 × 10−6
Single time period (s)
600
Communication radius (m)
50
Speed of theMobile Sink (m/s)
2
Packet size (bit)
500
Packet generation ratio (packet/minute)
1
Original position of theMobile Sink
(100, 100)Since the object of CTMER is maximizing the total energy reduction, we focus on the following four aspects, which are key metrics in large-scale WSNs:(1)
Energy consumption: this represents the sum of the energy consumption of all sensor nodes in wireless sensor network within first 600 s with fixed message generation ratio. We use the energy consumption model described in Section3 and investigate the performance with different number of sensor nodes and different speed of theMobile Sink. The LBDD and QDD follow query mode other than collecting data periodically; thus, we set the number of queries as the number of sensor nodes. This means that theMobile Sink queries data once for each sensor node within first 600 s.(2)
Network lifetime: this represents the elapsed time from the start to the end of the first node energy depletion.(3)
Total path length: this represents the total hops for all sensor nodes to forward the data to theMobile Sink. We do not test the total path length of LBDD and QDD, since there is no actual routing tree in these two protocols.(4)
Numbers of Cut operations: this represents the number of Cut operations when we use CTMER algorithm to optimize the energy. We vary the speed of theMobile Sink to investigate the impact on the number of Cut operations.


### 5.2. Analysis of Results

We first investigate the impact on the energy consumption of the sensor network with the increasing number of sensor nodes. As can be seen from Figure4, the energy consumption is increasing with the increasing number of nodes for all four protocols. RD-VT minimizes the total Euclidean distance of edges in the routing trees other than the total hop count fromsensor nodes tocollection nodes; thus, it does not perform good enough comparing with CTMER. The energy consumption of QDD and LBDD is higher than both CTMER and RD-VT because a large number of queries from theMobile Sink and data fromrendezvous points need multiple hop forwarding. For LBDD, the sources need to forward the data to the first inline-node, which may be far away from the sources. CTMER uses the Cut operations to optimize the total path length of the collection trees, which makes significant impact on energy consumption in our energy consumption model, and performs best in all compared protocols.Figure 4
Energy consumption with different number of sensor nodes.Figure5 shows the impact on the energy consumption with increasing speed of theMobile Sink. In CTMER, the increasing moving speed means the increasing length of the trajectory when the single time period is fixed and incurs more Cut operations; thus, the energy consumption of CTMER reduces gradually. With the similar reason, RD-VT can choose morerendezvous points in the Steiner Minimum Tree. However, the number ofrendezvous points or inline-nodes is independent with the speed of theMobile Sink in LBDD and QDD; thus, the energy consumption of them has no distinct change.Figure 5
Energy consumption with different speed of theMobile Sink.We then test the network lifetime of the protocols. We can see from Figure6 that the network lifetime of all protocols decreases with the increasing number of sensor nodes. In hierarchical structure based method, the network lifetime is significantly relevant to the overhead of thecollection nodes. In CTMER and RD-VT, the overhead ofcollection nodes is determined by the number of sensor nodes incollection trees since the packet generation ratio is fixed. With the increasing sensor nodes, there are more sensor nodes incollection trees in average, and the overhead ofcollection nodes increases accordingly in both CTMER and RD-VT. The performance of CTMER and RD-VT is very closed in aspect of network lifetime. However, the overhead ofrendezvous points in high lever will increase significantly in QDD, and the network lifetime decreases dramatically with the increasing scale of network.Figure 6
Network lifetime with different number of sensor nodes.Figure7 shows the impact on the network lifetime with the increasing speeds of theMobile Sink. As thecollection tree based protocols, the network lifetime of both CTMER and RD-VT increases dramatically because there are morecollection nodes to share the overhead. On the contrary, there is almost no influence on QDD and LBDD. This is because therendezvous points in QDD and LBDD are selected based on the structure and scale of network and are irrelevant to the speed of theMobile Sink.Figure 7
Network lifetime with different speed of theMobile Sink.Figure8 shows the total path length of CTMER and RD-VT with the increasing sensor nodes. Recall that the total path length is the total hop count from all sensor nodes to the correspondingcollection nodes, and it determines the total energy consumption in single time period based on the energy consumption model used in this paper. The total path length of both CTMER and RD-VT increases with the increasing network scale. We can see that CTMER is superior to RD-VT in aspect of total path length. This is because CTMER and RD-VT use different method to choose thecollection nodes to achieve the different objectives. CTMER aims to optimize the total hop count while RD-VT minimizes the total Euclidean distance of edges in the routing trees.Figure 8
Total path length with different number of sensor nodes.CTMER chooses thecollection nodes iteratively until the trajectory length of theMobile Sink does not meet the constraint. Thus, CTMER can do more Cut operations when the limit length of trajectory becomes longer. We can see from Figure 9 that the number of Cut operations increases dramatically from 5.1 to 26.2 with the speed of theMobile Sink since theMobile Sink can move far away in single time period.Figure 9
Number of Cut operations with different speed of theMobile Sink.


## 5.1. Simulation Setup

We implement CTMER on the MATLAB platform and compare our protocol to RD-VT (with a variable BS track), QDD (with oneMobile Sink), and LBDD (with oneMobile Sink using the progressive-footprint-chaining strategy) in order to investigate the performance of CTMER. We list the default parameter setting in Table 2. Each measurement is averaged over 200 instances.Table 2
Simulation parameters.
Parameter
Value
Network size (m2)
500 × 500
Number of sensor nodes
1000
Initial energy of each sensor node (J)
2
Initial energy of theMobile Sink(J)
1 × 106
Unit energy consumption (J/bit)
5 × 10−6
Single time period (s)
600
Communication radius (m)
50
Speed of theMobile Sink (m/s)
2
Packet size (bit)
500
Packet generation ratio (packet/minute)
1
Original position of theMobile Sink
(100, 100)Since the object of CTMER is maximizing the total energy reduction, we focus on the following four aspects, which are key metrics in large-scale WSNs:(1)
Energy consumption: this represents the sum of the energy consumption of all sensor nodes in wireless sensor network within first 600 s with fixed message generation ratio. We use the energy consumption model described in Section3 and investigate the performance with different number of sensor nodes and different speed of theMobile Sink. The LBDD and QDD follow query mode other than collecting data periodically; thus, we set the number of queries as the number of sensor nodes. This means that theMobile Sink queries data once for each sensor node within first 600 s.(2)
Network lifetime: this represents the elapsed time from the start to the end of the first node energy depletion.(3)
Total path length: this represents the total hops for all sensor nodes to forward the data to theMobile Sink. We do not test the total path length of LBDD and QDD, since there is no actual routing tree in these two protocols.(4)
Numbers of Cut operations: this represents the number of Cut operations when we use CTMER algorithm to optimize the energy. We vary the speed of theMobile Sink to investigate the impact on the number of Cut operations.


## 5.2. Analysis of Results

We first investigate the impact on the energy consumption of the sensor network with the increasing number of sensor nodes. As can be seen from Figure4, the energy consumption is increasing with the increasing number of nodes for all four protocols. RD-VT minimizes the total Euclidean distance of edges in the routing trees other than the total hop count fromsensor nodes tocollection nodes; thus, it does not perform good enough comparing with CTMER. The energy consumption of QDD and LBDD is higher than both CTMER and RD-VT because a large number of queries from theMobile Sink and data fromrendezvous points need multiple hop forwarding. For LBDD, the sources need to forward the data to the first inline-node, which may be far away from the sources. CTMER uses the Cut operations to optimize the total path length of the collection trees, which makes significant impact on energy consumption in our energy consumption model, and performs best in all compared protocols.Figure 4
Energy consumption with different number of sensor nodes.Figure5 shows the impact on the energy consumption with increasing speed of theMobile Sink. In CTMER, the increasing moving speed means the increasing length of the trajectory when the single time period is fixed and incurs more Cut operations; thus, the energy consumption of CTMER reduces gradually. With the similar reason, RD-VT can choose morerendezvous points in the Steiner Minimum Tree. However, the number ofrendezvous points or inline-nodes is independent with the speed of theMobile Sink in LBDD and QDD; thus, the energy consumption of them has no distinct change.Figure 5
Energy consumption with different speed of theMobile Sink.We then test the network lifetime of the protocols. We can see from Figure6 that the network lifetime of all protocols decreases with the increasing number of sensor nodes. In hierarchical structure based method, the network lifetime is significantly relevant to the overhead of thecollection nodes. In CTMER and RD-VT, the overhead ofcollection nodes is determined by the number of sensor nodes incollection trees since the packet generation ratio is fixed. With the increasing sensor nodes, there are more sensor nodes incollection trees in average, and the overhead ofcollection nodes increases accordingly in both CTMER and RD-VT. The performance of CTMER and RD-VT is very closed in aspect of network lifetime. However, the overhead ofrendezvous points in high lever will increase significantly in QDD, and the network lifetime decreases dramatically with the increasing scale of network.Figure 6
Network lifetime with different number of sensor nodes.Figure7 shows the impact on the network lifetime with the increasing speeds of theMobile Sink. As thecollection tree based protocols, the network lifetime of both CTMER and RD-VT increases dramatically because there are morecollection nodes to share the overhead. On the contrary, there is almost no influence on QDD and LBDD. This is because therendezvous points in QDD and LBDD are selected based on the structure and scale of network and are irrelevant to the speed of theMobile Sink.Figure 7
Network lifetime with different speed of theMobile Sink.Figure8 shows the total path length of CTMER and RD-VT with the increasing sensor nodes. Recall that the total path length is the total hop count from all sensor nodes to the correspondingcollection nodes, and it determines the total energy consumption in single time period based on the energy consumption model used in this paper. The total path length of both CTMER and RD-VT increases with the increasing network scale. We can see that CTMER is superior to RD-VT in aspect of total path length. This is because CTMER and RD-VT use different method to choose thecollection nodes to achieve the different objectives. CTMER aims to optimize the total hop count while RD-VT minimizes the total Euclidean distance of edges in the routing trees.Figure 8
Total path length with different number of sensor nodes.CTMER chooses thecollection nodes iteratively until the trajectory length of theMobile Sink does not meet the constraint. Thus, CTMER can do more Cut operations when the limit length of trajectory becomes longer. We can see from Figure 9 that the number of Cut operations increases dramatically from 5.1 to 26.2 with the speed of theMobile Sink since theMobile Sink can move far away in single time period.Figure 9
Number of Cut operations with different speed of theMobile Sink.


## 6. Conclusion

In this paper, we have presented the system model for designing constrained trajectory in large-scale wireless sensor networks under our energy consumption model and formulated the problem as the MERC problem. We designed an approximation algorithm (CTMER), which follows the greedy approach to design the movement trajectory of theMobile Sink through maximizing theeffective average energy reduction. CTMER uses Cut operations to choose thecollection nodes iteratively until the trajectory length of theMobile Sink does not meet the constraint. Through both rigid theoretical analysis and extensive simulations, we demonstrated that our algorithm achieves high computation efficiency and is superior to otherMobile Sink based data collection methods in aspects of energy consumption and network lifetime.



---

*Source: 801831-2015-10-19.xml*