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

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.

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. Section 2 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 graph $G=(V\cup \mathrm{M}\mathrm{S},E)$ , where V is the set of n stationary, homogeneous sensor nodes randomly deployed in a monitoring region, $\mathrm{M}\mathrm{S}$ 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 as their 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

Suppose $G^{\prime }=(V,E^{\prime })$ is a subnetwork of a wireless sensor network $G=(V\cup \mathrm{M}\mathrm{S},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^{\prime }$ 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 $\mathrm{M}{\mathrm{S}}_{\mathrm{1}},\mathrm{M}{\mathrm{S}}_{\mathrm{2}},\dots ,\mathrm{M}{\mathrm{S}}_k$ , $(k\ge \mathrm{2})$ . Let $R=(V_r,E_r)$ be the road map in the monitoring region, where each vertex in $V_r$ is a road intersection set and each edge in $E_r$ is a road. k mobile sinks are constrained to map R and each of them has an energy capacity $e_M$ . The energy consumption of each mobile sink is mainly used for traveling, data transmission, and reception. Let $e_{\lambda }$ be the sink energy consumption for unit length travel and let $e_{\mu }$ 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 the k 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 cycle C 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_{\mathrm{0}}$ denotes the set of all odd vertices on the map.

Step 2.

Calculate the distance $d(u,v)$ between each pair of vertices u and v of $V_{\mathrm{0}}$ 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 graph $K_{\left|V_{\mathrm{0}}\right|}$ , $V(K_{\left|V_0\right|})=V_{\mathrm{0}}$ , 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)\in M$ , replace the undirected edge $(u,v)$ with the shortest path $p(u,v)$ .

Step 5.

Find Euler circuit C with Fleury's algorithm [11].

We now construct k 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(L_i)\mid i=\mathrm{1,2},\dots ,k\}$ . We describe the closed tour $L_i$ as follows: (i) $V(L_i)$ , the set of road intersections; (ii) $E(L_i)$ , the set of roads; and (iii) $w(L_i)$ , 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(L_i)\mid i=\mathrm{1,2},\dots ,k\}$ . Specifically, the algorithm proceeds as follows.

We show how to partition the cycle C 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 $v_{\mathrm{1}},v_{\mathrm{2}},\dots ,v_n$ in the chain with each having weight $w(v_i)$ . 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 $v_{\mathrm{1}}$ and ends at $v_n$ . 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

$$\begin{array}{cc}& OPT\ge \underset{\mathrm{1}\le i\le n}{\max }\left\{w\left(v_i\right),\frac{{\sum }_{i=\mathrm{1}}^{n}w\left(v_i\right)}{k}\right\}.\end{array}$$

(1)

Clearly, Lemma 1 is obvious. Let

$$\begin{array}{cc}& a_{\mathrm{m}\mathrm{a}\mathrm{x}}=\underset{\mathrm{1}\le i\le n}{\max }\left\{w\left(v_i\right)\right\}.\end{array}$$

(2)

We proceed the chain partitions as in Algorithm 1.

Algorithm 1: Chain_partition ( $w(v_i)$ , k).

Input: k   $w(V_i)$

Output: the length of the longer segments among the k segments is minimized

$$M⟵\underset{\mathrm{1}\le i\le n}{\mathrm{m}\mathrm{a}\mathrm{x}}\left\{w\left(v_i\right),\frac{{\sum }_{i=\mathrm{1}}^{n}w\left(v_i\right)}{k}\right\}$$

if $a_{\mathrm{m}\mathrm{a}\mathrm{x}}\ge \left({{\displaystyle \sum }}_{i=\mathrm{1}}^{n}w(v_i)\right)/k$

then Construct the k segments $L_{\mathrm{1}},L_{\mathrm{2}},\dots ,L_k$ such that $a_{\mathrm{m}\mathrm{a}\mathrm{x}}\le w(L_i)\le \mathrm{2}{a}_{\mathrm{m}\mathrm{a}\mathrm{x}}$ for all $\mathrm{1}\le i\le k$

else

    $M_{\mathrm{1}}⟵M$

   Partition the chain into k segments such that the maximum one is no more than $M_{\mathrm{1}}$

   if there is no such a partition

      then $M_{\mathrm{1}}\leftarrow \mathrm{2}M$ / ${}^{\ast }$ double the value ${}^{\ast }$ /;

      Partition the chain into k segments such that the maximum one is no

      more than $M_{\mathrm{1}}$

   end if

end if

3.3. Sojourn Locations and Times of a Mobile Sink in a Closed Tour C

What followed is to determine the sojourn locations of a mobile sink on closed tour $C_i$ and to calculate the sojourn time at each sojourn location. The sojourn time of a mobile sink at a location is measured by 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 tour L in $R_E^{\prime }$ . 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 $r_{\mathrm{0}}$ , where $r_{\mathrm{0}}$ is its transmission radius; that is, $r_{\mathrm{0}}=r$ . Let $S=\{s_{\mathrm{1}},s_{\mathrm{2}},\dots ,s_n\}$ be the set of sojourn locations and $V_L=\{v_{\mathrm{1}},v_{\mathrm{2}},\dots ,v_m\}$ the set of neighbors of the mobile sink at location $s_i$ . Furthermore, assume that the mobile sink records the lengths $l(s_{\mathrm{1}}),l(s_{\mathrm{2}}),\dots ,l(s_n)$ between itself and each sojourn location. The family of the sets consists of all neighbor sets of sojourn locations of the mobile sink; thus $\mathbb{S}=\{S_{\mathrm{1}},S_{\mathrm{2}},\dots ,S_n\}$ , where $S_i$ is the neighbor set of sojourn location $s_i$ .

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 $s_i$ be a sojourn location of a mobile sink, the neighbor set of $s_i$ is $S_i=\{v_{\mathrm{1}}^{\prime },v_{\mathrm{2}}^{\prime },\dots ,v_{\left|S_i\right|}^{\prime }\}$ , $\left|S_i\right|$ is the number of nodes in set $S_i$ , and the residual energy of $v_{\mathrm{1}}^{\prime }$ , $v_{\mathrm{2}}^{\prime }$ , and $v_{\left|S_i\right|}^{\prime }$ at this moment is $e(v_{\mathrm{1}}^{\prime }),e(v_{\mathrm{2}}^{\prime }),\dots ,e(v_{\left|S_i\right|}^{\prime })$ , respectively. In order to balance the energy consumption among the sensor nodes in $S_i$ , we construct a tree rooted at the mobile sink located at $s_i$ . The first layer nodes in the tree are $v_{\mathrm{1}}^{\prime },v_{\mathrm{2}}^{\prime },\dots ,v_{\left|S_i\right|}^{\prime }$ . There are $\left|S_i\right|$ subrouting trees rooted at nodes $v_j^{\prime }$ with $\mathrm{1}\le j\le \left|S_i\right|$ . 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^{\prime })$ 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 $s_i$ . A node $v^{\prime }$ in the network is added to a subrouting tree of the first layer node with probability $p(v^{\prime })$ :

$$\begin{array}{cc}& p\left(v^{\prime }\right)=\frac{e\left(v^{\prime }\right)}{{\sum }_{j=\mathrm{1}}^{\left|S_i\right|}e\left(v_j^{\prime }\right)},\hspace{1em}{v}^{\prime }\in S_i.\end{array}$$

(3)

The more residual energy a first layer node has, the more likely the rest nodes join. There are $\left|S_i\right|$ 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(s_i)$ of the mobile sink at a sojourn location $s_i$ , $\mathrm{1}\le i\le n$ , thus must meet the following requirements:

• (1)

There is a direct correlation between the sojourn time $T(s_i)$ and the residual energy ${\sum }_{\text{num}=\mathrm{1}}^{\left|S_i\right|}e(v_{\text{num}}^{\prime })$ of the neighbor set of the mobile sink at its sojourn location $s_i$ . 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 $s_i$ is $\left|S_i\right|·Q$ , and the total energy consumption of nodes in the set is ${\sum }_{\text{num}=\mathrm{1}}^{\left|S_i\right|}[Q-e(v_{\text{num}}^{\prime })]$ .

(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 consumption $M\mu$ : $M\mu =({\sum }_{\text{num}=\mathrm{1}}^{\left|S_i\right|}[Q-e(v_{\text{num}}^{\prime })])/(|S_i|\ast 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 duration $T(s_i)$ 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(\mu )=e^{-\lambda ·\mu }$ , where λ is the index parameter with $\lambda >\mathrm{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(s_i)=\left|S_i\right|·t_{\mathrm{0}}·f(\mu )$ , where $t_{\mathrm{0}}$ is the time unit. $T(s_i)$ thus is as follows:

$$\begin{array}{cc}& T\left(s_i\right)=\left|S_i\right|·t_{\mathrm{0}}·\exp \left\{\frac{-\lambda \ast {\sum }_{\text{num}=\mathrm{1}}^{\left|S_i\right|}\left[Q-e\left(v_{\text{num}}^{\prime }\right)\right]}{\left|S_i\right|\ast Q}\right\}\frac{n!}{r!\left(n-r\right)!}.\end{array}$$

(4)

When the residual energy becomes zero, $T(s_i)=\left|S_i\right|·t_{\mathrm{0}}·e^{-\lambda }\lambda$ . 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(s_i)=\left|S_i\right|·t_{\mathrm{0}}$ , 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 set $e(v_{\mathrm{1}}),e(v_{\mathrm{2}}),\dots ,e(v_m)$ .

(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 location $e(S_{\mathrm{1}}),e(S_{\mathrm{2}}),\dots ,e(S_n)$ .

(3)

The sink selects a sojourn location at which the residual energy is largest as its next sojourn location. If $e(S_k)=\max \{e(S_i)\mid \mathrm{1}\le i\le n\}$ , $s_k$ is the next sojourn location.

(4)

The mobile sink moves to $s_k$ and proceeds data collection and transmission stage.

In summary, the proposed algorithm is described as in Algorithms 2 and 3.

Algorithm 2: Subloops balance.

Input: The road map $R=(V_r,E_r)$ , the number of mobile sinks k, $k\in N$ .

Output: an approximate solution of k balanced sub-loops.

Begin

/ ${}^{\ast }$ calculate the shortest path between vertices ${}^{\ast }$ /

(1) for $i\leftarrow 0$ to $|V_r|$ , $j\leftarrow 0$ to $|V_r|$ do

    $\mathrm{v}\mathrm{e}\mathrm{x}\mathrm{s}[i,j]\leftarrow \mathrm{S}\mathrm{h}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{e}\mathrm{s}\mathrm{t}\mathrm{P}\mathrm{a}\mathrm{t}\mathrm{h}[i,j]$ ;

  / ${}^{\ast }$ find a Euler circuit in graph by the Fleury algorithm ${}^{\ast }$ /

(2) C← Fleury(G) [11];

  / ${}^{\ast }$ find all combinations of k vertices from all vertices in $G^{\ast }$ /

(3) we partition the cycle C into chain by $|V_r|$ times then calling Chain_partition ( $w(v_i)$ , k);

  / ${}^{\ast }$ partition the cycle C into k segments such that the length of the longer segments among the k segments is minimized. ${}^{\ast }$ /

End

Algorithm 3: Sinks moving control.

Input: A sub-loop L, the sojourn location set $S=\left\{s_{\mathrm{1}},s_{\mathrm{2}},\dots ,s_n\right\}$ , the nodes set neighbor loop $V_L=\left\{v_{\mathrm{1}},v_{\mathrm{2}},\dots ,v_m\right\}$ ,

the energy of node neighbor loop $e(v_i)$ , $v_i\in V_L$ .

Output: the next sojourn location and the duration

Begin

/ ${}^{\ast }$ count the total energy of sojourn location ${}^{\ast }$ /

(1) for $i\leftarrow 1$ to m do

  if $v_i\in S_j$  then

     $e(S_j)=e(S_j)+e(v_i)$ ;

  end if

/ ${}^{\ast }$ select the sojourn location of which the residual energy is most as the next sojourn location ${}^{\ast }$ /

(2) for $j\leftarrow 1$ to n do

     $\mathrm{m}\mathrm{a}\mathrm{x}\leftarrow e(S_{\mathrm{1}})$

    if $e(S_{\mathrm{1}})>\mathrm{m}\mathrm{a}\mathrm{x}$  then

      $\mathrm{m}\mathrm{a}\mathrm{x}\leftarrow e(S_1)$ , $\mathrm{n}\mathrm{e}\mathrm{x}\mathrm{t}\leftarrow j$

    end if

(3) $T(s_{\mathrm{n}\mathrm{e}\mathrm{x}\mathrm{t}})=\left|S_{\mathrm{n}\mathrm{e}\mathrm{x}\mathrm{t}}\right|\cdot t_{\mathrm{0}}\cdot \exp \left\{\left(-\lambda \ast {{\displaystyle \sum }}_{\mathrm{n}\mathrm{u}\mathrm{m}=\mathrm{1}}^{|S_i|}[Q-e(v_{\mathrm{n}\mathrm{u}\mathrm{m}}^{\prime })]\right)/\left(|S_{\mathrm{n}\mathrm{e}\mathrm{x}\mathrm{t}}|\ast Q\right)\right\}$

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 for K segment partitioning of a cycle delivers a feasible solution with the approximation ratio of 2.

Proof.

We show this by two cases.

Case 1 ( $OPT\le a_{\mathrm{m}\mathrm{a}\mathrm{x}}$ ; then $OPT=a_{\mathrm{m}\mathrm{a}\mathrm{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 ( $OPT>a_{\mathrm{m}\mathrm{a}\mathrm{x}}$ ). We claim that the feasible solution is no more than $\mathrm{2}\ast \text{OPT}$ . Following the construction of the segments $L_{\mathrm{1}},L_{\mathrm{2}},\dots ,L_k$ , the weighted sum of each segment is no less than ${\sum }_{i=\mathrm{1}}^n(w(v_i)/k)$ . We show this case by contradiction. Assume that the maximum one in the feasible solution is larger than $\mathrm{2}\ast (({\sum }_{i=\mathrm{1}}^{n}w(v_i))/k)$ ; then we have that the weighted sum of the chain is ${\sum }_{k^{\prime }=\mathrm{1}}^k{L}_i>{\sum }_{k^{\prime }=\mathrm{1}}^k{\sum }_{i=\mathrm{1}}^n(w(v_i)/k)\ge k\ast {\sum }_{i=\mathrm{1}}^n(w(v_i)/k)={\sum }_{i=\mathrm{1}}^{n}w(v_i)$ .

It leads to the contradiction. Thus, the weighted sum of each segment $L_i$ is ${\sum }_{i=\mathrm{1}}^n(w(v_i)/k)+w(v_{ij})\le \mathrm{O}\mathrm{P}\mathrm{T}+\mathrm{O}\mathrm{P}\mathrm{T}=\mathrm{2}\ast \mathrm{O}\mathrm{P}\mathrm{T}$ .

Lemma 3.

Given a WSN $G(V,E)$ with a map $R(V_r,E_r)$ and k mobile sinks, the time complexity for MMEM is $O({\left|V_r\right|}^{\mathrm{3}}+{\left|E_r\right|}^{\mathrm{2}}+k\ast (\left|V\right|+N^{\mathrm{2}}))$ , N is the number of neighbor nodes, and $\left|V\right|$ is the number of nodes in the WSN.

Proof.

We find optimally the cycle C on map R by invoking the Chinese postman. (i) We find the set of all odd vertices $V_{\text{odd}}$ ; it takes time $O(\left|V_r\right|)$ . (ii) We calculate the shortest distance of each pair of vertices in the $V_{\text{odd}}$ by Dijkstra's algorithm; it takes time $O({\left|V_r\right|}^{\mathrm{3}})$ . (iii) It constructs a weighted complete graph $K_{\left|V_{\mathrm{0}}\right|}$ , which takes time $O({\left|V_{\text{odd}}\right|}^{\mathrm{2}})$ . (iv) For a given $K_{\left|V_{\mathrm{0}}\right|}$ , we calculate the minimum weight perfect matching M by the Hungarian algorithm [11]; it takes time $O({\left|V_{\text{odd}}\right|}^{\mathrm{3}})$ . If $(u,v)\in M$ , we augment undirected edge with the weight as before in $p(u,v)$ ; it takes time $O({\left|V_r\right|}^{\mathrm{2}}\ast \left|V_{\text{odd}}\right|)$ . (v) We find Euler circuit C with the Fleury algorithm [11]. It takes time complexity $O(\left|E_r\right|)$ .

We then partition cycle C into k segments by calling Algorithm 1   $\mathrm{C}\mathrm{h}\mathrm{a}\mathrm{i}\mathrm{n}\_\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}(w(v_i),k$ ), $\left|V_r\right|$ times. $\mathrm{C}\mathrm{h}\mathrm{a}\mathrm{i}\mathrm{n}\_\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}(w(v_i)$ , k) has time complexity no larger than $O(|V_r|+k^{\mathrm{1}+\epsilon })$ for any small $\epsilon >\mathrm{0}$ . Thus, the time complexity is $O({\left|V_r\right|}^{\mathrm{2}}+\left|V_r\right|\ast k^{\mathrm{1}+\epsilon })$ .

We make conclusion that the time complexity of Algorithm 2 subloops balance is $O({\left|V_r\right|}^{\mathrm{3}}+{\left|E_r\right|}^{\mathrm{2}})$ .

In Algorithm 3, 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(N^{\mathrm{2}})$ , so the time for the control algorithm of mobile station is $O(|V|+N^2)$ . There are k closed routes, so the time is $O(k\ast (\left|V\right|+N^{\mathrm{2}}))$ .

As the above analysis, the time complexity is $O((k\ast \left|V\right|+N^2)+|V_r{|}^3+|E_r{|}^2)$ .

Theorem 4.

In a WSN G, 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

$$\begin{array}{cc}& \frac{e\left(v_{\mathrm{1}}\right)}{N\left(v_{\mathrm{1}}\right)}=\frac{e\left(v_{\mathrm{2}}\right)}{N\left(v_{\mathrm{2}}\right)}=\cdots =\frac{e\left(v_k\right)}{N\left(v_k\right)}=c_{\mathrm{1}}.\end{array}$$

(5)

And the node energy consumption rate is proportional to the number of nodes:

$$\begin{array}{cc}& \frac{\mu \left(v_1\right)}{N\left(v_1\right)}=\frac{\mu \left(v_2\right)}{N\left(v_2\right)}=\cdots =\frac{\mu \left(v_k\right)}{N\left(v_k\right)}=c_{\mathrm{2}}.\end{array}$$

(6)

Then,

$$\begin{array}{cc}& \frac{e\left(v_1\right)}{\mu \left(v_1\right)}=\frac{e\left(v_2\right)}{\mu \left(v_2\right)}=\cdots =\frac{e\left(v_k\right)}{\mu \left(v_k\right)}=c.\end{array}$$

(7)

k is the number of $s_i$ ; $N(v_j)$ is the descendant of $v_j$ , $\mathrm{1}\le j\le k$ . c, $c_{\mathrm{1}}$ , and $c_{\mathrm{2}}$ are constant for a constructed tree. Assuming that one of the neighbor nodes of the sojourn point $s_i$ exhausts energy, so the time complexity is $t=(e(v_j)/\mu (V_j))$ . 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

$$\begin{array}{cc}& t\left(s_i\right)⟶k\ast t_0\ast e^{-\lambda },\\ T=k\ast t_0\ast e^{-\lambda }+\sigma ,\hspace{1em}\sigma ⟶0^{+}.\end{array}$$

(8)

According to (4),

$$\begin{array}{cc}& T=k·t_{\mathrm{0}}·\exp \left\{-\lambda \ast \frac{{\sum }_{j=\mathrm{1}}^k\left[Q-e\left(v_j\right)\right]}{k\ast Q}\right\},\\ {\displaystyle \sum }_{j=\mathrm{1}}^k\left[Q-e\left(v_j\right)\right]=-\frac{k\ast Q}{\lambda }\ast \ln \frac{T}{k\ast t_{\mathrm{0}}}=-\frac{k\ast Q}{\lambda }\ast \ln \frac{k\ast t_{\mathrm{0}}\ast e^{-\lambda }+\sigma }{k\ast t_{\mathrm{0}}}=-\frac{k\ast Q}{\lambda }\ast \ln \left(e^{-\lambda }+\frac{\sigma }{k\ast t_{\mathrm{0}}}\right)\approx k\ast Q,\end{array}$$

(9)

$\lambda \to \mathrm{0}$ , and the other is constant, so we can conclude that $\sigma /(k\ast t_{\mathrm{0}})<\mathrm{1}$ ; then $\mathrm{l}\mathrm{n}(e^{-\lambda }+\sigma /\left(k\ast t_{\mathrm{0}}\right))\approx \ln e^{-\lambda }=-\lambda \Rightarrow {\sum }_{j=\mathrm{1}}^k[Q-e(v_j)]\approx k\ast 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 WSN G, for a map R and k mobile stations MSs, MMEM guarantees that the energies of neighbor nodes exhaust almost at the same time.

There are k 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 is $\mathrm{5}\times \mathrm{1}{\mathrm{0}}^{-\mathrm{5}}\hspace{0.17em}(\mathrm{J}/\mathrm{b}\mathrm{i}\mathrm{t})$ . 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

Figure 1(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.

Figure 1(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

Figure 2 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

Figure 3(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.

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.