# An Efficient Algorithm for Energy Management in Wireless Sensor Networks via Employing Multiple Mobile Sinks

Authors: Jiugen Shi; Xing Wei; Wei Zhu
Journal: International Journal of Distributed Sensor Networks
 (2016)

---

## Abstract

Energy saving in wireless sensor networks is a fundamental issue as most sensor nodes are powered by batteries. The deployment of mobile sinks can alleviate the imbalance of energy consumption among sensor nodes, thereby prolonging the network lifetime. In this paper, we study the energy management problem in sensor networks, using multiple mobile sinks. We first formulate the problem as a novel data collection problem and then propose an efficient algorithm for it. The key challenge in the design of the proposed algorithm is how to balance the workload among mobile sinks and the energy consumption among sensor nodes through the control of the movement of mobile sinks. We finally evaluate the performance of the proposed algorithm through experimental simulation. Experimental results show that the proposed algorithm is very promising, which can improve the energy efficiency and the quality of data transmission in the sensor network significantly.


---

## Body

## 1. Introduction

The rapid development of micro-electro mechanical systems, system on chip, wireless communication technology, and low power embedded systems makes it possible to deploy wireless sensor networks (WSNs) for various applications. The characteristics of WSNs such as low power consumption, low operational cost, distribution, and self-organization have brought about a revolution in information perception. A WSN is a multihop ad hoc network, which is composed of large number of cheap microsensor nodes deployed in a monitoring region. WSNs have been widely used in environmental monitoring, health care, military surveillance, and so forth. WSNs have received extensive attentions in the past few years. One of their applications is to monitor harsh environments or places which are hard to reach by a human being, such as nature conservation areas, primitive forest, and nuclear pollution sites, where it is very difficult to replace or recharge batteries. Therefore, a fundamental problem to prolong the network lifetime of WSNs is the efficient utilization of sensors’ energy.The use of mobile sinks compared to static sinks can greatly improve the energy efficiency of sensors in WSNs. Several studies of deploying mobile sinks for data collection in literature have been conducted in the past. For example, [1] aims to construct a routing tree such that the network lifetime is maximized while keeping the routing path from each sensor to the sink is minimized. A generic cost model of energy consumption for data gathering is proposed, and a routing tree is used for the query evaluation [2]. The work in [3] aims to find an optimal trajectory for each mobile sink and to determine the sojourn time of each mobile sink at each sojourn location in the trajectory such that the network lifetime is maximized. The use of a single mobile sink to prolong the network lifetime has also been explored in [4]. The work in [5] proposes the route of mobile base station and balances the network load to prolong network lifetime. Similarly [5–7] propose the maximum residual energy of greedy algorithm to control the mobile base station. In the case of limited base station stationary point, joint mobility and routing of base station are proposed [8–10]. However, the usage of mobile sinks has many limitations in practical applications. On one hand, a WSN is usually deployed in traffic inconvenience regions, so the movable area in the regions by the mobile sinks is limited. On the other hand, the mobile sinks are usually installed on mobile tools such as unmanned vehicles; the speeds of these mobile vehicles are constrained by many factors such as road conditions and mobile tools, where the mobile tools also have energy limit, so their maximum moving distance per tour is limited, too. Thus, when dealing with routing protocol design under this scenario, we must take these constraints on mobile sinks into account, in order to prolong the network lifetime efficiently and effectively.Most existing algorithms for balancing the energy consumption of sensors are too difficult to be implemented in practice due to multiple limitations imposed on WSNs for different applications. In many practical applications, these limitations seriously influence the performance of existing algorithms. In this paper, assume that a sensor network with multiple mobile sinks is to be deployed for monitoring a remote region, and there is a local connected road map for the mobile sinks in the monitored region. The problem of concern is how to schedule these mobile sinks to collect as much data from sensors as possible so as to prolong the network lifetime.The main contributions of this paper are as follows. We first formulate a novel constrained optimization problem, the energy management optimization problem of energy-constrained multiple mobile sinks for wireless sensor networks. We then propose an efficient algorithm, referred to as the Energy Management algorithm in a WSN with Multiple Sinks (EMMS), for the problem, which balances not only the workload among the mobile sinks but also the energy consumption among the sensor nodes. We finally conduct experiments through simulation to evaluate the performance of the proposed algorithm. Experimental results show that the proposed algorithm is very promising, which can improve the energy efficiency and the quality of data transmission of the sensor network significantly.The rest of this paper is organized as follows. Section2 introduces the system model and problem definition. Section 3 proposes an efficient algorithm for the problem of concern. Section 4 evaluates the performance of the proposed algorithm through simulations, and Section 5 concludes the paper.


## 2. Preliminaries

In this section, we first introduce the system model of wireless sensor networks, and then we define the problem precisely.


### 2.1. System Model

A wireless sensor network can be modeled as an undirected graphG=(V∪MS,E), where V is the set of n stationary, homogeneous sensor nodes randomly deployed in a monitoring region, MS is the set of k mobile sinks, and E is the set of links between sensors and sinks. There is a link between two sensors u and v if they are within the transmission range of each other. For ease of presentation, we here do not distinguish a node in graph G and the corresponding sensor of the node. We treat the mobile sinks as special sensors that can receive sensed data from sensor nodes and transfer their collected sensory data to a remote monitor center for remote monitoring. We assume that every sensor node has a unique identification with limited initial energy capacity Q, while each mobile sink has an energy capacity with unlimited energy supply at the depot. Two wireless transmission interfaces are installed on each mobile sink: (i) a low power wireless interface used for the communication with sensor nodes in the sensor network and (ii) a high bandwidth wireless interface that is used for communicating with a third party network for remote data transfer.We assume that the monitoring region by the sensor network has a road map that consists of connected roads on which the mobile sinks can travel. The road map contains all roads and their intersections. Each mobile sink will travel along the roads in the map at a constant speed and can stop at any point on the roads for data collection. We refer to these stop points of mobile sinks astheir sojourn locations. Each mobile sink must return to its depot when it runs out of energy or completes its tour of data collection per round. Each sensor node collects its environmental information periodically and then transmits the collected data to its parent sensor in a routing tree rooted at a mobile sink through multihop relays. The mobile sinks compress their received sensory data and transmit the compressed data to the remote data monitoring center via the third party communication network.


### 2.2. Problem Definition

SupposeG′=(V,E′) is a subnetwork of a wireless sensor network G=(V∪MS,E) whose sensors are densely and randomly deployed in a 2D monitoring region, where V is the set of sensors; there is a link in E′ between two sensor nodes if the Euclidean distance between them is not greater than their transmission radius r. We assume that there are k mobile sinks MS1,MS2,…,MSk, (k≥2). Let R=(Vr,Er) be the road map in the monitoring region, where each vertex in Vr is a road intersection set and each edge in Er is a road. k mobile sinks are constrained to map R and each of them has an energy capacity eM. The energy consumption of each mobile sink is mainly used for traveling, data transmission, and reception. Let eλ be the sink energy consumption for unit length travel and let eμ be the sink energy consumption for data transmission or reception in unit time at its sojourn locations. In general, sensor nodes consume most of their energy for wireless communication, namely, transmission and reception energy consumption, and the other energy consumption such as sensing and computing energy consumption is negligible.We further assume that mobile sinks travel only along the roads in the map at a constant speed and can stay in any sojourn locations in their tours. They must return to their depot when they run out of energy. Each sensor node senses its vicinity information periodically and transmits the sensed data to its nearest mobile sink through multihop relays, where the sensor node is a node in the routing tree rooted at the mobile sink. The Energy Management in a WSN with Multiple Sinks (EMMS) is to find a closed tour for each of thek mobile sinks and calculate duration on the found tour per round so that the network lifetime can be maximized.


## 2.1. System Model

A wireless sensor network can be modeled as an undirected graphG=(V∪MS,E), where V is the set of n stationary, homogeneous sensor nodes randomly deployed in a monitoring region, MS is the set of k mobile sinks, and E is the set of links between sensors and sinks. There is a link between two sensors u and v if they are within the transmission range of each other. For ease of presentation, we here do not distinguish a node in graph G and the corresponding sensor of the node. We treat the mobile sinks as special sensors that can receive sensed data from sensor nodes and transfer their collected sensory data to a remote monitor center for remote monitoring. We assume that every sensor node has a unique identification with limited initial energy capacity Q, while each mobile sink has an energy capacity with unlimited energy supply at the depot. Two wireless transmission interfaces are installed on each mobile sink: (i) a low power wireless interface used for the communication with sensor nodes in the sensor network and (ii) a high bandwidth wireless interface that is used for communicating with a third party network for remote data transfer.We assume that the monitoring region by the sensor network has a road map that consists of connected roads on which the mobile sinks can travel. The road map contains all roads and their intersections. Each mobile sink will travel along the roads in the map at a constant speed and can stop at any point on the roads for data collection. We refer to these stop points of mobile sinks astheir sojourn locations. Each mobile sink must return to its depot when it runs out of energy or completes its tour of data collection per round. Each sensor node collects its environmental information periodically and then transmits the collected data to its parent sensor in a routing tree rooted at a mobile sink through multihop relays. The mobile sinks compress their received sensory data and transmit the compressed data to the remote data monitoring center via the third party communication network.


## 2.2. Problem Definition

SupposeG′=(V,E′) is a subnetwork of a wireless sensor network G=(V∪MS,E) whose sensors are densely and randomly deployed in a 2D monitoring region, where V is the set of sensors; there is a link in E′ between two sensor nodes if the Euclidean distance between them is not greater than their transmission radius r. We assume that there are k mobile sinks MS1,MS2,…,MSk, (k≥2). Let R=(Vr,Er) be the road map in the monitoring region, where each vertex in Vr is a road intersection set and each edge in Er is a road. k mobile sinks are constrained to map R and each of them has an energy capacity eM. The energy consumption of each mobile sink is mainly used for traveling, data transmission, and reception. Let eλ be the sink energy consumption for unit length travel and let eμ be the sink energy consumption for data transmission or reception in unit time at its sojourn locations. In general, sensor nodes consume most of their energy for wireless communication, namely, transmission and reception energy consumption, and the other energy consumption such as sensing and computing energy consumption is negligible.We further assume that mobile sinks travel only along the roads in the map at a constant speed and can stay in any sojourn locations in their tours. They must return to their depot when they run out of energy. Each sensor node senses its vicinity information periodically and transmits the sensed data to its nearest mobile sink through multihop relays, where the sensor node is a node in the routing tree rooted at the mobile sink. The Energy Management in a WSN with Multiple Sinks (EMMS) is to find a closed tour for each of thek mobile sinks and calculate duration on the found tour per round so that the network lifetime can be maximized.


## 3. The EMMS Algorithm

In this section we deal with the EMMS problem by devising a novel algorithm for it. Firstly, we start by giving an overview of the algorithm, secondly, we provide the details of the proposed algorithm, and, lastly, we analyze the time complexity of the proposed algorithm.


### 3.1. Overview of the Proposed Algorithm

The trajectory of each mobile sink for data collection in the network is a closed tour that consists of one or multiple roads in the map. The proposed algorithm for Energy Management in a WSN with Multiple Sinks (EMMS) consists of two stages. The first stage is to find a closed tour for each mobile sink such that the length of the closed tour of each mobile sink is roughly equal, and the second stage is to determine the sojourn locations of each mobile sink on the found closed tour and to build a routing tree rooted at each sojourn location as well as the sojourn time at the location for the mobile sink. The rest of this section will detail the two stages of the algorithm.


### 3.2. Finding a Closed Tour for Each Mobile Sink

To find a closed tour for each mobile such that the length of the closed tour is roughly equal is essential to balance the workload among the mobile sinks. To this end, the solution delivered by the proposed algorithm should meet the following requirements:(1)
The tour length of each sink should be about the same.(2)
The tour of each mobile sink is a closed tour so that the mobile sink can stop at any points (sojourn locations) in the tour.(3)
The starting and ending points of each mobile sink are the same, which are its depot.(4)
The overlapping among the closed tours should be as few as possible.(5)
Each road on the map must be accessed by at least one of the mobile sinks.We find an optimal cycleC on map R that mobile sink must travel each edge at least once such that the total distance traveled by the sink is as short as possible. This problem is the Chinese postman [11]; the algorithm’s details are described as follows.Step 1.
V
0 denotes the set of all odd vertices on the map.Step 2.
Calculate the distanced(u,v) between each pair of vertices u and v of V0 on the map R and calculate the shortest path p(u,v) between u and v by Dijkstra’s algorithm.Step 3.
Construct a weighted complete graphKV0, V(KV0)=V0, and the weight of edge uv is d(u,v); then calculate the minimum weight perfect matching M in the complete graph.Step 4.
If(u,v)∈M, replace the undirected edge (u,v) with the shortest path p(u,v).Step 5.
Find Euler circuitC with Fleury’s algorithm [11].We now constructk closed tours on cycle C for k mobiles sinks, such that every closed tour will be accessed by one of the mobile sinks. Then, the length of the longest closed tour is max⁡{w(Li)∣i=1,2,…,k}. We describe the closed tour Li as follows: (i) V(Li), the set of road intersections; (ii) E(Li), the set of roads; and (iii) w(Li), the weighted sum of lengths of roads. Our objective is to minimize the length of the longest closed tour of k tours; that is, we aim to minimize max⁡{w(Li)∣i=1,2,…,k}. Specifically, the algorithm proceeds as follows.We show how to partition the cycleC into k segments such that the length of the longer segments among the k segments is minimized. To this end, we instead consider a chain containing n nodes v1,v2,…,vn in the chain with each having weight w(vi). We partition the chain into k segments such that the weighted sum of the largest segment is minimized. Thus, the original problem of partitioning k segments of a cycle C can be solved by calling this routine n times by removing a link of the cycle consisting of n edges at each time such that the resulting graph is a chain. Then, the minimum one among the n chains is the solution to the original problem [12]. In the following, we focus on the chain partition. We consider a chain that starts with v1 and ends at vn. When a chain starts from the other node, the processing is almost similar, omitted. Let OPT be the value of the optimal solution; then we have the following lemma.Lemma 1.
One has(1)OPT≥max1≤i≤n⁡wvi,∑i=1nwvik.Clearly, Lemma 1 is obvious. Let (2)amax=max1≤i≤n⁡wvi.We proceed the chain partitions as in Algorithm 1.Algorithm 1:Chain_partition (w(vi), k).
Input:k  w(Vi)
Output: the length of the longer segments among thek segments is minimized
M
⟵
m
a
x
1
≤
i
≤
n
w
v
i
,
∑
i
=
1
n
w
v
i
k
ifamax≥∑i=1nw(vi)/k
then Construct thek segments L1,L2,…,Lk such that amax≤w(Li)≤2amax for all 1≤i≤k
else
M1⟵M
Partition the chain intok segments such that the maximum one is no more than M1
if there is no such a partition
then M1←2M /∗double the value∗/;
Partition the chain into k segments such that the maximum one is no
more than M1
end if
end if


### 3.3. Sojourn Locations and Times of a Mobile Sink in a Closed TourC

What followed is to determine the sojourn locations of a mobile sink on closed tourCi and to calculatethe sojourn time at each sojourn location. The sojourn time of a mobile sink at a location is measuredby the number of rounds like LEACH protocol [13], where each round consists of the duration at that location for data collection and the travel time spent to reach the next sojourn location.


#### 3.3.1. The Sojourn Location Identifications

We assume that there is a closed tourL in RE′. A mobile sink traverses along L and will determine its next sojourn location. The mobile sink starts from its depot and marks a sojourn location at every distance r0, where r0 is its transmission radius; that is, r0=r. Let S={s1,s2,…,sn} be the set of sojourn locations and VL={v1,v2,…,vm} the set of neighbors of the mobile sink at location si. Furthermore, assume that the mobile sink records the lengths l(s1),l(s2),…,l(sn) between itself and each sojourn location. The family of the sets consists of all neighbor sets of sojourn locations of the mobile sink; thus S={S1,S2,…,Sn}, where Si is the neighbor set of sojourn location si.


#### 3.3.2. Data Collection

In the following we deal with the routing tree construction and the sojourn time at each of the routing trees.(A) The Routing Tree Construction. Each mobile sink receives and transmits data by a routing tree at its sojourn locations. We illustrate the routing tree structure by an example. Let si be a sojourn location of a mobile sink, the neighbor set of si is Si={v1′,v2′,…,vSi′}, |Si| is the number of nodes in set Si, and the residual energy of v1′, v2′, and vSi′ at this moment is e(v1′),e(v2′),…,e(v|Si|′), respectively. In order to balance the energy consumption among the sensor nodes in Si, we construct a tree rooted at the mobile sink located at si. The first layer nodes in the tree are v1′,v2′,…,v|Si|′. There are |Si| subrouting trees rooted at nodes vj′ with 1≤j≤Si. For the routing tree i, in order to balance the energy consumption among the sensor nodes, the number of children of each first layer node is proportional to its residual energy. In the network, we assume that p(v′) is the probability of a node joining in a subrouting tree, which is the ratio of the first layer node’s residual energy to the total residual energy of nodes in the neighbor set of the mobile sink at the sojourn location si. A node v′ in the network is added to a subrouting tree of the first layer node with probability p(v′):(3)pv′=ev′∑j=1Sievj′,v′∈Si.The more residual energy a first layer node has, the more likely the rest nodes join. There are|Si| subrouting trees, of which the first layer node’s residual energy is proportional to the number of descendant nodes so that we can balance the workload among the first layer nodes.(B) The Sojourn Time Calculation at Each Sojourn Location. Assume that the routing tree for each mobile sink at each sojourn location has been constructed. As time goes by, the residual energy of each sensor node becomes less and less; now, we consider the duration of data collection of the mobile sink at one sojourn location. In order to balance the energy consumption among sensor nodes in the sojourn location’s neighbor set, we should reduce the duration of the mobile sink at a sojourn location per round. The duration T(si) of the mobile sink at a sojourn location si, 1≤i≤n, thus must meet the following requirements:(1)
There is a direct correlation between the sojourn timeT(si) and the residual energy ∑num=1|Si|e(vnum′) of the neighbor set of the mobile sink at its sojourn location si. The less the residual energy is, the shorter the sojourn time will be. As the initial energy of each sensor node is Q, the initial energy sum of the neighbor set of the mobile sink at location si is |Si|·Q, and the total energy consumption of nodes in the set is ∑num=1|Si|[Q-e(vnum′)].(2)
When the energy consumption in the neighbor set is high, the sojourn time should be reduced. We denote the ratio of the energy consumption to the initial energy capacity of sensor nodes as the level of energy consumptionMμ: Mμ=(∑num=1|Si|[Q-e(vnum′)])/(|Si|∗Q).(3)
In order to reduce the movement of mobile sinks, we need to ensure the shortest duration for the practicability of network when the residual energy of nodes in the neighbor set is reduced. The durationT(si) changes with the level of energy consumption in the neighbor set of the mobile sink at its sojourn location, and the change function is f(μ)=e-λ·μ, where λ is the index parameter with λ>0.(4)
The more the number of nodes in the neighbor set of the mobile sink at a sojourn location, the longer the duration will be. That is,T(si)=|Si|·t0·f(μ), where t0 is the time unit. T(si) thus is as follows:(4)Tsi=Si·t0·exp⁡-λ∗∑num=1SiQ-evnum′Si∗Qn!r!n-r!.When the residual energy becomes zero,T(si)=Si·t0·e-λλ. We can set the shortest duration of the mobile sink at its current sojourn location by adjusting λ. When the residual energy is Q, with T(si)=Si·t0, the sojourn time is longest.(C) Data Collection and Sensing Data Transmission. The mobile sinks receive sensory data from their routing trees and transmit the sensory data to the remote monitoring center. In the last stage of data transmission stages, they collect the residual energy information from nodes in the neighbor set and travel to its next sojourn location.


#### 3.3.3. Sojourn Location Search Stage

(1)
At the beginning of each round, the mobile sinks collect all residual energy information of nodes sete(v1),e(v2),…,e(vm).
(2)
They calculate the residual energy of each set in the set family and get the residual energy of nodes in the neighbor set of each sojourn locatione(S1),e(S2),…,e(Sn).
(3)
The sink selects a sojourn location at which the residual energy is largest as its next sojourn location. Ife(Sk)=max⁡{e(Si)∣1≤i≤n}, sk is the next sojourn location.
(4)
The mobile sink moves tosk and proceeds data collection and transmission stage.In summary, the proposed algorithm is described as in Algorithms2 and 3.Algorithm 2:Subloops balance.
Input: The road mapR=(Vr,Er), the number of mobile sinks k, k∈N.
Output: an approximate solution ofk balanced sub-loops.
Begin
/∗calculate the shortest path between vertices∗/
(1) fori←0 to |Vr|, j←0 to |Vr| do
vexs[i,j]←ShortestPath[i,j];
/∗find a Euler circuit in graph by the Fleury algorithm∗/
(2)C← Fleury(G) [11];
/∗find all combinations of k vertices from all vertices in G∗/
(3) we partition the cycleC into chain by |Vr| times then calling Chain_partition (w(vi), k);
/∗partition the cycle C into k segments such that the length of the longer segments among the k segments is minimized.∗/
EndAlgorithm 3:Sinks moving control.
Input: A sub-loopL, the sojourn location set S=s1,s2,…,sn, the nodes set neighbor loop VL=v1,v2,…,vm,
the energy of node neighbor loope(vi), vi∈VL.
Output: the next sojourn location and the duration
Begin
/∗count the total energy of sojourn location∗/
(1) fori←1 to m do
ifvi∈Sj then
e(Sj)=e(Sj)+e(vi);
end if
/∗ select the sojourn location of which the residual energy is most as the next sojourn location ∗/
(2) forj←1 to n do
max←e(S1)
ife(S1)>max then
max←e(S1), next←j
end if
(3)T(snext)=Snext⋅t0⋅exp⁡-λ∗∑num=1|Si|[Q-e(vnum′)]/|Snext|∗Q
End


### 3.4. Algorithm Analysis

In this section we analyze the approximation ratio of the proposed partition algorithm by the following theorem.Theorem 2.
The algorithm forK segment partitioning of a cycle delivers a feasible solution with the approximation ratio of 2.Proof.
We show this by two cases.
Case 1 (
O
P
T
≤
a
m
a
x
; then
O
P
T
=
a
m
a
x
). Thus, we can partition the chain into k segments such that each segment has a weight that is no more than the optimal one plus the last node (in the segment 3.2). Thus, the weighted sum of the segment is no more than twice the optimal one.
Case 2 (
O
P
T
>
a
m
a
x
). We claim that the feasible solution is no more than 2∗OPT. Following the construction of the segments L1,L2,…,Lk, the weighted sum of each segment is no less than ∑i=1n(w(vi)/k). We show this case by contradiction. Assume that the maximum one in the feasible solution is larger than 2∗((∑i=1nw(vi))/k); then we have that the weighted sum of the chain is ∑k′=1kLi>∑k′=1k∑i=1n(w(vi)/k)≥k∗∑i=1n(w(vi)/k)=∑i=1nw(vi).
It leads to the contradiction. Thus, the weighted sum of each segmentLi is ∑i=1n(w(vi)/k)+w(vij)≤OPT+OPT=2∗OPT.Lemma 3.
Given a WSNG(V,E) with a map R(Vr,Er) and k mobile sinks, the time complexity for MMEM is O(Vr3+Er2+k∗(V+N2)), N is the number of neighbor nodes, and |V| is the number of nodes in the WSN.Proof.
We find optimally the cycleC on map R by invoking the Chinese postman. (i) We find the set of all odd vertices Vodd; it takes time O(Vr). (ii) We calculate the shortest distance of each pair of vertices in the Vodd by Dijkstra’s algorithm; it takes time O(Vr3). (iii) It constructs a weighted complete graph K|V0|, which takes time O(Vodd2). (iv) For a given K|V0|, we calculate the minimum weight perfect matching M by the Hungarian algorithm [11]; it takes time O(Vodd3). If (u,v)∈M, we augment undirected edge with the weight as before in p(u,v); it takes time O(Vr2∗Vodd). (v) We find Euler circuit C with the Fleury algorithm [11]. It takes time complexity O(Er).
We then partition cycleC into k segments by calling Algorithm 1  Chain_partition(w(vi),k), Vr times. Chain_partition(w(vi), k) has time complexity no larger than O(|Vr|+k1+ε) for any small ε>0. Thus, the time complexity is O(Vr2+Vr∗k1+ε).
We make conclusion that the time complexity of Algorithm2 subloops balance is O(Vr3+Er2).
In Algorithm3, sinks need to move and to be controlled during the data collection; we thus need to construct routing tree and calculate sojourn time. These need time O(|V|+N), and to find next sojourn we need to compare the rest energy; this needs time O(N2), so the time for the control algorithm of mobile station is O(|V|+N2). There are k closed routes, so the time is O(k∗(V+N2)).
As the above analysis, the time complexity isO((k∗|V|+N2)+|Vr|3+|Er|2).Theorem 4.
In a WSNG, given a closed tour L and a mobile station MS, the control algorithm of mobile sink can guarantee that the nodes closed to the closed tour run out of energy almost at the same time.Proof.
Firstly, we prove that the energies of neighbor nodes with the same sojourn point exhaust almost at the same time. We assume that the energy consumption is used for data transmission or reception. The ratio of the residual energy of neighbor nodes is equal to the ratio of the number of descendent nodes. Consider(5)ev1Nv1=ev2Nv2=⋯=evkNvk=c1.And the node energy consumption rate is proportional to the number of nodes: (6)μv1Nv1=μv2Nv2=⋯=μvkNvk=c2.Then, (7)ev1μv1=ev2μv2=⋯=evkμvk=c.k is the number of si; N(vj) is the descendant of vj, 1≤j≤k. c, c1, and c2 are constant for a constructed tree. Assuming that one of the neighbor nodes of the sojourn point si exhausts energy, so the time complexity is t=(e(vj)/μ(Vj)). According to formula (7), the other neighbor nodes of the sojourn point will exhaust their energy almost at the same time.
Secondly, we prove that the energy of the nodes closed to the sojourn points of the same route use almost the same time. Thus, we prove that when one of the neighbor nodes of the same routing runs out of its energy, the remaining nodes do, too. According to (4), the duration for one round which will run out of its energy tends to be(8)tsi⟶k∗t0∗e-λ,T=k∗t0∗e-λ+σ,σ⟶0+.According to (4),(9)T=k·t0·exp⁡-λ∗∑j=1kQ-evjk∗Q,∑j=1kQ-evj=-k∗Qλ∗ln⁡Tk∗t0=-k∗Qλ∗ln⁡k∗t0∗e-λ+σk∗t0=-k∗Qλ∗ln⁡e-λ+σk∗t0≈k∗Q,λ→0, and the other is constant, so we can conclude that σ/(k∗t0)<1; then ln(e-λ+σ/k∗t0)≈ln⁡e-λ=-λ⇒∑j=1k[Q-e(vj)]≈k∗Q.
The energy dissipation of the sojourn point neighbor node set is almost equal to its initial energy. We make conclusion that the energies of neighbor nodes of other sojourns almost run out at the same time.
In a WSNG, for a map R and k mobile stations MSs, MMEM guarantees that the energies of neighbor nodes exhaust almost at the same time.
There arek segments, from which k closed tours will be derived. k mobile stations then travel on the closed tours. We thus conclude that MMEM guarantees that the energies of neighbor nodes exhaust almost at the same time.


## 3.1. Overview of the Proposed Algorithm

The trajectory of each mobile sink for data collection in the network is a closed tour that consists of one or multiple roads in the map. The proposed algorithm for Energy Management in a WSN with Multiple Sinks (EMMS) consists of two stages. The first stage is to find a closed tour for each mobile sink such that the length of the closed tour of each mobile sink is roughly equal, and the second stage is to determine the sojourn locations of each mobile sink on the found closed tour and to build a routing tree rooted at each sojourn location as well as the sojourn time at the location for the mobile sink. The rest of this section will detail the two stages of the algorithm.


## 3.2. Finding a Closed Tour for Each Mobile Sink

To find a closed tour for each mobile such that the length of the closed tour is roughly equal is essential to balance the workload among the mobile sinks. To this end, the solution delivered by the proposed algorithm should meet the following requirements:(1)
The tour length of each sink should be about the same.(2)
The tour of each mobile sink is a closed tour so that the mobile sink can stop at any points (sojourn locations) in the tour.(3)
The starting and ending points of each mobile sink are the same, which are its depot.(4)
The overlapping among the closed tours should be as few as possible.(5)
Each road on the map must be accessed by at least one of the mobile sinks.We find an optimal cycleC on map R that mobile sink must travel each edge at least once such that the total distance traveled by the sink is as short as possible. This problem is the Chinese postman [11]; the algorithm’s details are described as follows.Step 1.
V
0 denotes the set of all odd vertices on the map.Step 2.
Calculate the distanced(u,v) between each pair of vertices u and v of V0 on the map R and calculate the shortest path p(u,v) between u and v by Dijkstra’s algorithm.Step 3.
Construct a weighted complete graphKV0, V(KV0)=V0, and the weight of edge uv is d(u,v); then calculate the minimum weight perfect matching M in the complete graph.Step 4.
If(u,v)∈M, replace the undirected edge (u,v) with the shortest path p(u,v).Step 5.
Find Euler circuitC with Fleury’s algorithm [11].We now constructk closed tours on cycle C for k mobiles sinks, such that every closed tour will be accessed by one of the mobile sinks. Then, the length of the longest closed tour is max⁡{w(Li)∣i=1,2,…,k}. We describe the closed tour Li as follows: (i) V(Li), the set of road intersections; (ii) E(Li), the set of roads; and (iii) w(Li), the weighted sum of lengths of roads. Our objective is to minimize the length of the longest closed tour of k tours; that is, we aim to minimize max⁡{w(Li)∣i=1,2,…,k}. Specifically, the algorithm proceeds as follows.We show how to partition the cycleC into k segments such that the length of the longer segments among the k segments is minimized. To this end, we instead consider a chain containing n nodes v1,v2,…,vn in the chain with each having weight w(vi). We partition the chain into k segments such that the weighted sum of the largest segment is minimized. Thus, the original problem of partitioning k segments of a cycle C can be solved by calling this routine n times by removing a link of the cycle consisting of n edges at each time such that the resulting graph is a chain. Then, the minimum one among the n chains is the solution to the original problem [12]. In the following, we focus on the chain partition. We consider a chain that starts with v1 and ends at vn. When a chain starts from the other node, the processing is almost similar, omitted. Let OPT be the value of the optimal solution; then we have the following lemma.Lemma 1.
One has(1)OPT≥max1≤i≤n⁡wvi,∑i=1nwvik.Clearly, Lemma 1 is obvious. Let (2)amax=max1≤i≤n⁡wvi.We proceed the chain partitions as in Algorithm 1.Algorithm 1:Chain_partition (w(vi), k).
Input:k  w(Vi)
Output: the length of the longer segments among thek segments is minimized
M
⟵
m
a
x
1
≤
i
≤
n
w
v
i
,
∑
i
=
1
n
w
v
i
k
ifamax≥∑i=1nw(vi)/k
then Construct thek segments L1,L2,…,Lk such that amax≤w(Li)≤2amax for all 1≤i≤k
else
M1⟵M
Partition the chain intok segments such that the maximum one is no more than M1
if there is no such a partition
then M1←2M /∗double the value∗/;
Partition the chain into k segments such that the maximum one is no
more than M1
end if
end if


## 3.3. Sojourn Locations and Times of a Mobile Sink in a Closed TourC

What followed is to determine the sojourn locations of a mobile sink on closed tourCi and to calculatethe sojourn time at each sojourn location. The sojourn time of a mobile sink at a location is measuredby the number of rounds like LEACH protocol [13], where each round consists of the duration at that location for data collection and the travel time spent to reach the next sojourn location.


### 3.3.1. The Sojourn Location Identifications

We assume that there is a closed tourL in RE′. A mobile sink traverses along L and will determine its next sojourn location. The mobile sink starts from its depot and marks a sojourn location at every distance r0, where r0 is its transmission radius; that is, r0=r. Let S={s1,s2,…,sn} be the set of sojourn locations and VL={v1,v2,…,vm} the set of neighbors of the mobile sink at location si. Furthermore, assume that the mobile sink records the lengths l(s1),l(s2),…,l(sn) between itself and each sojourn location. The family of the sets consists of all neighbor sets of sojourn locations of the mobile sink; thus S={S1,S2,…,Sn}, where Si is the neighbor set of sojourn location si.


### 3.3.2. Data Collection

In the following we deal with the routing tree construction and the sojourn time at each of the routing trees.(A) The Routing Tree Construction. Each mobile sink receives and transmits data by a routing tree at its sojourn locations. We illustrate the routing tree structure by an example. Let si be a sojourn location of a mobile sink, the neighbor set of si is Si={v1′,v2′,…,vSi′}, |Si| is the number of nodes in set Si, and the residual energy of v1′, v2′, and vSi′ at this moment is e(v1′),e(v2′),…,e(v|Si|′), respectively. In order to balance the energy consumption among the sensor nodes in Si, we construct a tree rooted at the mobile sink located at si. The first layer nodes in the tree are v1′,v2′,…,v|Si|′. There are |Si| subrouting trees rooted at nodes vj′ with 1≤j≤Si. For the routing tree i, in order to balance the energy consumption among the sensor nodes, the number of children of each first layer node is proportional to its residual energy. In the network, we assume that p(v′) is the probability of a node joining in a subrouting tree, which is the ratio of the first layer node’s residual energy to the total residual energy of nodes in the neighbor set of the mobile sink at the sojourn location si. A node v′ in the network is added to a subrouting tree of the first layer node with probability p(v′):(3)pv′=ev′∑j=1Sievj′,v′∈Si.The more residual energy a first layer node has, the more likely the rest nodes join. There are|Si| subrouting trees, of which the first layer node’s residual energy is proportional to the number of descendant nodes so that we can balance the workload among the first layer nodes.(B) The Sojourn Time Calculation at Each Sojourn Location. Assume that the routing tree for each mobile sink at each sojourn location has been constructed. As time goes by, the residual energy of each sensor node becomes less and less; now, we consider the duration of data collection of the mobile sink at one sojourn location. In order to balance the energy consumption among sensor nodes in the sojourn location’s neighbor set, we should reduce the duration of the mobile sink at a sojourn location per round. The duration T(si) of the mobile sink at a sojourn location si, 1≤i≤n, thus must meet the following requirements:(1)
There is a direct correlation between the sojourn timeT(si) and the residual energy ∑num=1|Si|e(vnum′) of the neighbor set of the mobile sink at its sojourn location si. The less the residual energy is, the shorter the sojourn time will be. As the initial energy of each sensor node is Q, the initial energy sum of the neighbor set of the mobile sink at location si is |Si|·Q, and the total energy consumption of nodes in the set is ∑num=1|Si|[Q-e(vnum′)].(2)
When the energy consumption in the neighbor set is high, the sojourn time should be reduced. We denote the ratio of the energy consumption to the initial energy capacity of sensor nodes as the level of energy consumptionMμ: Mμ=(∑num=1|Si|[Q-e(vnum′)])/(|Si|∗Q).(3)
In order to reduce the movement of mobile sinks, we need to ensure the shortest duration for the practicability of network when the residual energy of nodes in the neighbor set is reduced. The durationT(si) changes with the level of energy consumption in the neighbor set of the mobile sink at its sojourn location, and the change function is f(μ)=e-λ·μ, where λ is the index parameter with λ>0.(4)
The more the number of nodes in the neighbor set of the mobile sink at a sojourn location, the longer the duration will be. That is,T(si)=|Si|·t0·f(μ), where t0 is the time unit. T(si) thus is as follows:(4)Tsi=Si·t0·exp⁡-λ∗∑num=1SiQ-evnum′Si∗Qn!r!n-r!.When the residual energy becomes zero,T(si)=Si·t0·e-λλ. We can set the shortest duration of the mobile sink at its current sojourn location by adjusting λ. When the residual energy is Q, with T(si)=Si·t0, the sojourn time is longest.(C) Data Collection and Sensing Data Transmission. The mobile sinks receive sensory data from their routing trees and transmit the sensory data to the remote monitoring center. In the last stage of data transmission stages, they collect the residual energy information from nodes in the neighbor set and travel to its next sojourn location.


### 3.3.3. Sojourn Location Search Stage

(1)
At the beginning of each round, the mobile sinks collect all residual energy information of nodes sete(v1),e(v2),…,e(vm).
(2)
They calculate the residual energy of each set in the set family and get the residual energy of nodes in the neighbor set of each sojourn locatione(S1),e(S2),…,e(Sn).
(3)
The sink selects a sojourn location at which the residual energy is largest as its next sojourn location. Ife(Sk)=max⁡{e(Si)∣1≤i≤n}, sk is the next sojourn location.
(4)
The mobile sink moves tosk and proceeds data collection and transmission stage.In summary, the proposed algorithm is described as in Algorithms2 and 3.Algorithm 2:Subloops balance.
Input: The road mapR=(Vr,Er), the number of mobile sinks k, k∈N.
Output: an approximate solution ofk balanced sub-loops.
Begin
/∗calculate the shortest path between vertices∗/
(1) fori←0 to |Vr|, j←0 to |Vr| do
vexs[i,j]←ShortestPath[i,j];
/∗find a Euler circuit in graph by the Fleury algorithm∗/
(2)C← Fleury(G) [11];
/∗find all combinations of k vertices from all vertices in G∗/
(3) we partition the cycleC into chain by |Vr| times then calling Chain_partition (w(vi), k);
/∗partition the cycle C into k segments such that the length of the longer segments among the k segments is minimized.∗/
EndAlgorithm 3:Sinks moving control.
Input: A sub-loopL, the sojourn location set S=s1,s2,…,sn, the nodes set neighbor loop VL=v1,v2,…,vm,
the energy of node neighbor loope(vi), vi∈VL.
Output: the next sojourn location and the duration
Begin
/∗count the total energy of sojourn location∗/
(1) fori←1 to m do
ifvi∈Sj then
e(Sj)=e(Sj)+e(vi);
end if
/∗ select the sojourn location of which the residual energy is most as the next sojourn location ∗/
(2) forj←1 to n do
max←e(S1)
ife(S1)>max then
max←e(S1), next←j
end if
(3)T(snext)=Snext⋅t0⋅exp⁡-λ∗∑num=1|Si|[Q-e(vnum′)]/|Snext|∗Q
End


## 3.3.1. The Sojourn Location Identifications

We assume that there is a closed tourL in RE′. A mobile sink traverses along L and will determine its next sojourn location. The mobile sink starts from its depot and marks a sojourn location at every distance r0, where r0 is its transmission radius; that is, r0=r. Let S={s1,s2,…,sn} be the set of sojourn locations and VL={v1,v2,…,vm} the set of neighbors of the mobile sink at location si. Furthermore, assume that the mobile sink records the lengths l(s1),l(s2),…,l(sn) between itself and each sojourn location. The family of the sets consists of all neighbor sets of sojourn locations of the mobile sink; thus S={S1,S2,…,Sn}, where Si is the neighbor set of sojourn location si.


## 3.3.2. Data Collection

In the following we deal with the routing tree construction and the sojourn time at each of the routing trees.(A) The Routing Tree Construction. Each mobile sink receives and transmits data by a routing tree at its sojourn locations. We illustrate the routing tree structure by an example. Let si be a sojourn location of a mobile sink, the neighbor set of si is Si={v1′,v2′,…,vSi′}, |Si| is the number of nodes in set Si, and the residual energy of v1′, v2′, and vSi′ at this moment is e(v1′),e(v2′),…,e(v|Si|′), respectively. In order to balance the energy consumption among the sensor nodes in Si, we construct a tree rooted at the mobile sink located at si. The first layer nodes in the tree are v1′,v2′,…,v|Si|′. There are |Si| subrouting trees rooted at nodes vj′ with 1≤j≤Si. For the routing tree i, in order to balance the energy consumption among the sensor nodes, the number of children of each first layer node is proportional to its residual energy. In the network, we assume that p(v′) is the probability of a node joining in a subrouting tree, which is the ratio of the first layer node’s residual energy to the total residual energy of nodes in the neighbor set of the mobile sink at the sojourn location si. A node v′ in the network is added to a subrouting tree of the first layer node with probability p(v′):(3)pv′=ev′∑j=1Sievj′,v′∈Si.The more residual energy a first layer node has, the more likely the rest nodes join. There are|Si| subrouting trees, of which the first layer node’s residual energy is proportional to the number of descendant nodes so that we can balance the workload among the first layer nodes.(B) The Sojourn Time Calculation at Each Sojourn Location. Assume that the routing tree for each mobile sink at each sojourn location has been constructed. As time goes by, the residual energy of each sensor node becomes less and less; now, we consider the duration of data collection of the mobile sink at one sojourn location. In order to balance the energy consumption among sensor nodes in the sojourn location’s neighbor set, we should reduce the duration of the mobile sink at a sojourn location per round. The duration T(si) of the mobile sink at a sojourn location si, 1≤i≤n, thus must meet the following requirements:(1)
There is a direct correlation between the sojourn timeT(si) and the residual energy ∑num=1|Si|e(vnum′) of the neighbor set of the mobile sink at its sojourn location si. The less the residual energy is, the shorter the sojourn time will be. As the initial energy of each sensor node is Q, the initial energy sum of the neighbor set of the mobile sink at location si is |Si|·Q, and the total energy consumption of nodes in the set is ∑num=1|Si|[Q-e(vnum′)].(2)
When the energy consumption in the neighbor set is high, the sojourn time should be reduced. We denote the ratio of the energy consumption to the initial energy capacity of sensor nodes as the level of energy consumptionMμ: Mμ=(∑num=1|Si|[Q-e(vnum′)])/(|Si|∗Q).(3)
In order to reduce the movement of mobile sinks, we need to ensure the shortest duration for the practicability of network when the residual energy of nodes in the neighbor set is reduced. The durationT(si) changes with the level of energy consumption in the neighbor set of the mobile sink at its sojourn location, and the change function is f(μ)=e-λ·μ, where λ is the index parameter with λ>0.(4)
The more the number of nodes in the neighbor set of the mobile sink at a sojourn location, the longer the duration will be. That is,T(si)=|Si|·t0·f(μ), where t0 is the time unit. T(si) thus is as follows:(4)Tsi=Si·t0·exp⁡-λ∗∑num=1SiQ-evnum′Si∗Qn!r!n-r!.When the residual energy becomes zero,T(si)=Si·t0·e-λλ. We can set the shortest duration of the mobile sink at its current sojourn location by adjusting λ. When the residual energy is Q, with T(si)=Si·t0, the sojourn time is longest.(C) Data Collection and Sensing Data Transmission. The mobile sinks receive sensory data from their routing trees and transmit the sensory data to the remote monitoring center. In the last stage of data transmission stages, they collect the residual energy information from nodes in the neighbor set and travel to its next sojourn location.


## 3.3.3. Sojourn Location Search Stage

(1)
At the beginning of each round, the mobile sinks collect all residual energy information of nodes sete(v1),e(v2),…,e(vm).
(2)
They calculate the residual energy of each set in the set family and get the residual energy of nodes in the neighbor set of each sojourn locatione(S1),e(S2),…,e(Sn).
(3)
The sink selects a sojourn location at which the residual energy is largest as its next sojourn location. Ife(Sk)=max⁡{e(Si)∣1≤i≤n}, sk is the next sojourn location.
(4)
The mobile sink moves tosk and proceeds data collection and transmission stage.In summary, the proposed algorithm is described as in Algorithms2 and 3.Algorithm 2:Subloops balance.
Input: The road mapR=(Vr,Er), the number of mobile sinks k, k∈N.
Output: an approximate solution ofk balanced sub-loops.
Begin
/∗calculate the shortest path between vertices∗/
(1) fori←0 to |Vr|, j←0 to |Vr| do
vexs[i,j]←ShortestPath[i,j];
/∗find a Euler circuit in graph by the Fleury algorithm∗/
(2)C← Fleury(G) [11];
/∗find all combinations of k vertices from all vertices in G∗/
(3) we partition the cycleC into chain by |Vr| times then calling Chain_partition (w(vi), k);
/∗partition the cycle C into k segments such that the length of the longer segments among the k segments is minimized.∗/
EndAlgorithm 3:Sinks moving control.
Input: A sub-loopL, the sojourn location set S=s1,s2,…,sn, the nodes set neighbor loop VL=v1,v2,…,vm,
the energy of node neighbor loope(vi), vi∈VL.
Output: the next sojourn location and the duration
Begin
/∗count the total energy of sojourn location∗/
(1) fori←1 to m do
ifvi∈Sj then
e(Sj)=e(Sj)+e(vi);
end if
/∗ select the sojourn location of which the residual energy is most as the next sojourn location ∗/
(2) forj←1 to n do
max←e(S1)
ife(S1)>max then
max←e(S1), next←j
end if
(3)T(snext)=Snext⋅t0⋅exp⁡-λ∗∑num=1|Si|[Q-e(vnum′)]/|Snext|∗Q
End


## 3.4. Algorithm Analysis

In this section we analyze the approximation ratio of the proposed partition algorithm by the following theorem.Theorem 2.
The algorithm forK segment partitioning of a cycle delivers a feasible solution with the approximation ratio of 2.Proof.
We show this by two cases.
Case 1 (
O
P
T
≤
a
m
a
x
; then
O
P
T
=
a
m
a
x
). Thus, we can partition the chain into k segments such that each segment has a weight that is no more than the optimal one plus the last node (in the segment 3.2). Thus, the weighted sum of the segment is no more than twice the optimal one.
Case 2 (
O
P
T
>
a
m
a
x
). We claim that the feasible solution is no more than 2∗OPT. Following the construction of the segments L1,L2,…,Lk, the weighted sum of each segment is no less than ∑i=1n(w(vi)/k). We show this case by contradiction. Assume that the maximum one in the feasible solution is larger than 2∗((∑i=1nw(vi))/k); then we have that the weighted sum of the chain is ∑k′=1kLi>∑k′=1k∑i=1n(w(vi)/k)≥k∗∑i=1n(w(vi)/k)=∑i=1nw(vi).
It leads to the contradiction. Thus, the weighted sum of each segmentLi is ∑i=1n(w(vi)/k)+w(vij)≤OPT+OPT=2∗OPT.Lemma 3.
Given a WSNG(V,E) with a map R(Vr,Er) and k mobile sinks, the time complexity for MMEM is O(Vr3+Er2+k∗(V+N2)), N is the number of neighbor nodes, and |V| is the number of nodes in the WSN.Proof.
We find optimally the cycleC on map R by invoking the Chinese postman. (i) We find the set of all odd vertices Vodd; it takes time O(Vr). (ii) We calculate the shortest distance of each pair of vertices in the Vodd by Dijkstra’s algorithm; it takes time O(Vr3). (iii) It constructs a weighted complete graph K|V0|, which takes time O(Vodd2). (iv) For a given K|V0|, we calculate the minimum weight perfect matching M by the Hungarian algorithm [11]; it takes time O(Vodd3). If (u,v)∈M, we augment undirected edge with the weight as before in p(u,v); it takes time O(Vr2∗Vodd). (v) We find Euler circuit C with the Fleury algorithm [11]. It takes time complexity O(Er).
We then partition cycleC into k segments by calling Algorithm 1  Chain_partition(w(vi),k), Vr times. Chain_partition(w(vi), k) has time complexity no larger than O(|Vr|+k1+ε) for any small ε>0. Thus, the time complexity is O(Vr2+Vr∗k1+ε).
We make conclusion that the time complexity of Algorithm2 subloops balance is O(Vr3+Er2).
In Algorithm3, sinks need to move and to be controlled during the data collection; we thus need to construct routing tree and calculate sojourn time. These need time O(|V|+N), and to find next sojourn we need to compare the rest energy; this needs time O(N2), so the time for the control algorithm of mobile station is O(|V|+N2). There are k closed routes, so the time is O(k∗(V+N2)).
As the above analysis, the time complexity isO((k∗|V|+N2)+|Vr|3+|Er|2).Theorem 4.
In a WSNG, given a closed tour L and a mobile station MS, the control algorithm of mobile sink can guarantee that the nodes closed to the closed tour run out of energy almost at the same time.Proof.
Firstly, we prove that the energies of neighbor nodes with the same sojourn point exhaust almost at the same time. We assume that the energy consumption is used for data transmission or reception. The ratio of the residual energy of neighbor nodes is equal to the ratio of the number of descendent nodes. Consider(5)ev1Nv1=ev2Nv2=⋯=evkNvk=c1.And the node energy consumption rate is proportional to the number of nodes: (6)μv1Nv1=μv2Nv2=⋯=μvkNvk=c2.Then, (7)ev1μv1=ev2μv2=⋯=evkμvk=c.k is the number of si; N(vj) is the descendant of vj, 1≤j≤k. c, c1, and c2 are constant for a constructed tree. Assuming that one of the neighbor nodes of the sojourn point si exhausts energy, so the time complexity is t=(e(vj)/μ(Vj)). According to formula (7), the other neighbor nodes of the sojourn point will exhaust their energy almost at the same time.
Secondly, we prove that the energy of the nodes closed to the sojourn points of the same route use almost the same time. Thus, we prove that when one of the neighbor nodes of the same routing runs out of its energy, the remaining nodes do, too. According to (4), the duration for one round which will run out of its energy tends to be(8)tsi⟶k∗t0∗e-λ,T=k∗t0∗e-λ+σ,σ⟶0+.According to (4),(9)T=k·t0·exp⁡-λ∗∑j=1kQ-evjk∗Q,∑j=1kQ-evj=-k∗Qλ∗ln⁡Tk∗t0=-k∗Qλ∗ln⁡k∗t0∗e-λ+σk∗t0=-k∗Qλ∗ln⁡e-λ+σk∗t0≈k∗Q,λ→0, and the other is constant, so we can conclude that σ/(k∗t0)<1; then ln(e-λ+σ/k∗t0)≈ln⁡e-λ=-λ⇒∑j=1k[Q-e(vj)]≈k∗Q.
The energy dissipation of the sojourn point neighbor node set is almost equal to its initial energy. We make conclusion that the energies of neighbor nodes of other sojourns almost run out at the same time.
In a WSNG, for a map R and k mobile stations MSs, MMEM guarantees that the energies of neighbor nodes exhaust almost at the same time.
There arek segments, from which k closed tours will be derived. k mobile stations then travel on the closed tours. We thus conclude that MMEM guarantees that the energies of neighbor nodes exhaust almost at the same time.


## 4. Performance Evaluation

In this section we evaluate the performance of the proposed algorithm, EMMS, against other existing algorithms. We also investigate the impact of several parameters, the number of sensors per unit area, the road length of each mobile sink, and the number of sensors, on the performance of the proposed algorithm through simulations.


### 4.1. Experimental Environment Setting

We consider a wireless sensor network consisting of 100 to 400 sensors deployed in a 100 m × 100 m rectangle region. The transmission range of each sensor is 40 meters and its initial energy capacity is 0.5 J. Energy consuming rate of a sensor node of transmitting and receiving data is5×10-5(J/bit). The total travel length of each mobile sink per tour is 400 m. Each value in each figure is the mean of the results delivered by the same algorithm applied to 20 different topologies.To evaluate the effectiveness and efficiency of the proposed algorithm, we make use of two existing algorithms, SDMA [14] and DAWN [4], as our benchmarks. We define the lifetime T of the wireless network to the number of periodic data readings from sensors until the first sensor is drained of its energy.


### 4.2. Impact of the Number of Sensors on Network Lifetime

Figure1(a) shows a wireless sensor network consisting of 100 sensors deployed in a 100 m × 100 m rectangle region. The lifetimes delivered by algorisms SDMA, DAWN, and MMEM in the wireless network are 1,000 rounds, 1,250 rounds, and 1,400 rounds, respectively.Figure 1
Impact of the number of sensors on the network lifetime.
(a)
100 sensors in the100∗100 areas
(b)
400 sensors in the200∗200 areasFigure1(b) shows a wireless sensor network consisting of 400 sensors deployed in a 200 m × 200 m rectangle region. The lifetimes of wireless network delivered by algorithms SDMA, DAWN, and MMEM are 1,000 rounds, 1,010 rounds, and 1,750 rounds, respectively. As shown in Figure 1, the lifetime under the scheduling of MMEM is always significantly better than that under DAWN and SDMA.


### 4.3. Impact of the Length of Closed Tours on the Network Lifetime

Figure2 plots the network lifetime of a sensor network when the number of sensors is fixed at 400 deployed in a 200 m × 200 m rectangle region, while the length of closed tours ranged from 400 m to 800 m with an increment of 100 m. The longer the length of closed tours the longer the network lifetime. In this simulation, the sensor nodes are distributed along the closed tour. The lifetime is 1750 rounds when the length of closed tour is limited to 400 m. With the increase of the length of closed tour and sojourn locations, the lifetime of network increases. The length of closed tour is longer and the number of sensors near the closed tour is larger.Figure 2
Impact of the length of closed tours on the network lifetime.


### 4.4. Data Transmission Quantity

Figure3(a) shows a wireless sensor network consisting of 100 sensors deployed in a 100 m × 100 m rectangle region. When the number of rounds is set at 1,000, SDMA, DAWN, and MMEM of the data transmission quantity are 5,000 bits, 30,000 bits, and 48,000 bits, respectively. Figure 3(b) demonstrates a wireless sensor network consisting of 400 sensors deployed in a 200 m × 200 m rectangle region. When the number of rounds is set at 1,000, SDMA, DAWN, and MMEM of the data transmission quantity are 30,000 bits, 40,000 bits, and 220,000 bits, respectively. As can be seen that no nodes expired and the duration is guaranteed, the quality of the network lifetime and data transmission is significantly improved. As shown in Figure 3, the data transmission under the scheduling of MMEM outperforms both DAWN and SDMA.Figure 3
The data transmission quantity of the proposed algorithm, EMMS.
(a)
100 sensors in the100∗100 areas
(b)
400 sensors in the200∗200 areas


## 4.1. Experimental Environment Setting

We consider a wireless sensor network consisting of 100 to 400 sensors deployed in a 100 m × 100 m rectangle region. The transmission range of each sensor is 40 meters and its initial energy capacity is 0.5 J. Energy consuming rate of a sensor node of transmitting and receiving data is5×10-5(J/bit). The total travel length of each mobile sink per tour is 400 m. Each value in each figure is the mean of the results delivered by the same algorithm applied to 20 different topologies.To evaluate the effectiveness and efficiency of the proposed algorithm, we make use of two existing algorithms, SDMA [14] and DAWN [4], as our benchmarks. We define the lifetime T of the wireless network to the number of periodic data readings from sensors until the first sensor is drained of its energy.


## 4.2. Impact of the Number of Sensors on Network Lifetime

Figure1(a) shows a wireless sensor network consisting of 100 sensors deployed in a 100 m × 100 m rectangle region. The lifetimes delivered by algorisms SDMA, DAWN, and MMEM in the wireless network are 1,000 rounds, 1,250 rounds, and 1,400 rounds, respectively.Figure 1
Impact of the number of sensors on the network lifetime.
(a)
100 sensors in the100∗100 areas
(b)
400 sensors in the200∗200 areasFigure1(b) shows a wireless sensor network consisting of 400 sensors deployed in a 200 m × 200 m rectangle region. The lifetimes of wireless network delivered by algorithms SDMA, DAWN, and MMEM are 1,000 rounds, 1,010 rounds, and 1,750 rounds, respectively. As shown in Figure 1, the lifetime under the scheduling of MMEM is always significantly better than that under DAWN and SDMA.


## 4.3. Impact of the Length of Closed Tours on the Network Lifetime

Figure2 plots the network lifetime of a sensor network when the number of sensors is fixed at 400 deployed in a 200 m × 200 m rectangle region, while the length of closed tours ranged from 400 m to 800 m with an increment of 100 m. The longer the length of closed tours the longer the network lifetime. In this simulation, the sensor nodes are distributed along the closed tour. The lifetime is 1750 rounds when the length of closed tour is limited to 400 m. With the increase of the length of closed tour and sojourn locations, the lifetime of network increases. The length of closed tour is longer and the number of sensors near the closed tour is larger.Figure 2
Impact of the length of closed tours on the network lifetime.


## 4.4. Data Transmission Quantity

Figure3(a) shows a wireless sensor network consisting of 100 sensors deployed in a 100 m × 100 m rectangle region. When the number of rounds is set at 1,000, SDMA, DAWN, and MMEM of the data transmission quantity are 5,000 bits, 30,000 bits, and 48,000 bits, respectively. Figure 3(b) demonstrates a wireless sensor network consisting of 400 sensors deployed in a 200 m × 200 m rectangle region. When the number of rounds is set at 1,000, SDMA, DAWN, and MMEM of the data transmission quantity are 30,000 bits, 40,000 bits, and 220,000 bits, respectively. As can be seen that no nodes expired and the duration is guaranteed, the quality of the network lifetime and data transmission is significantly improved. As shown in Figure 3, the data transmission under the scheduling of MMEM outperforms both DAWN and SDMA.Figure 3
The data transmission quantity of the proposed algorithm, EMMS.
(a)
100 sensors in the100∗100 areas
(b)
400 sensors in the200∗200 areas


## 5. Conclusion

In this paper, we studied the data collection in a wireless sensor network via employing multiple mobile sinks and formulated it as a constrained optimization problem. We proposed an EMMS algorithm for the problem and evaluated the performance of the proposed algorithm through simulations. Simulation results demonstrate that the proposed algorithm can improve the energy efficiency and data transmission quantity within the network significantly.



---

*Source: 3179587-2016-01-18.xml*