# Maximizing Lifetime of Wireless Sensor Networks with Mobile Sink Nodes

Authors: Yourong Chen; Zhangquan Wang; Tiaojuan Ren; Yaolin Liu; Hexin Lv
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

In order to maximize network lifetime and balance energy consumption when sink nodes can move, maximizing lifetime of wireless sensor networks with mobile sink nodes (MLMS) is researched. The movement path selection method of sink nodes is proposed. Modified subtractive clustering method, k-means method, and nearest neighbor interpolation method are used to obtain the movement paths. The lifetime optimization model is established under flow constraint, energy consumption constraint, link transmission constraint, and other constraints. The model is solved from the perspective of static and mobile data gathering of sink nodes. Subgradient method is used to solve the lifetime optimization model when one sink node stays at one anchor location. Geometric method is used to evaluate the amount of gathering data when sink nodes are moving. Finally, all sensor nodes transmit data according to the optimal data transmission scheme. Sink nodes gather the data along the shortest movement paths. Simulation results show that MLMS can prolong network lifetime, balance node energy consumption, and reduce data gathering latency under appropriate parameters. Under certain conditions, it outperforms Ratio_w, TPGF, RCC, and GRND.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) usually have a large number of sensor nodes. The sensor nodes gather data in the monitoring area and transmit the data to sink node for further processing. They are usually applied to monitor the indoor and outdoor environment, factory and process automation, earthquake, and so forth. They are also applied to trace animals, humans, vehicles, and other targets. WSNs have received more and more attention from industry and academia. They have great potentiality in enhancing and changing people’s interaction with the world [1].In WSNs, sensor nodes are distributed densely in unattended or even harsh environment and have large quantity. The batteries of sensor nodes are not available to recharge or replace battery [2]. Basic function realization of data gathering and transmission and other function realizations of safety, multimedia, and QoS security in wired and wireless networks are based on network normal operation and sufficient node energy. Therefore, network lifetime is the most important indicator of network performance. The algorithms of WSNs should consider energy saving and maximize the network lifetime. It can cut down the enormous spending of WSNs redeployment.In static terrestrial WSNs (all node locations are fixed), the sensor nodes which are located around sink node consume more energy than others and become disabled quickly. The uneven energy consumption causes energy hole problem. The problem will split the network and block the data transmission to sink nodes [3]. In underwater WSNs, DGs (designated gateways) real-timely gather data of underwater sensor nodes. However, underwater WSNs also have energy hole problem [4].To overcome the problems such as energy hole and lifetime optimization in static terrestrial WSNs and underwater WSNs, [5–7] research into lifetime optimization algorithms. Those algorithms assume that the node locations are fixed. Sensor nodes which locate around the sink node are easy to be hub nodes and lead to consuming a lot of energy. It is inevitable to cause the unbalanced distribution of node energy consumption and energy hole problem. The problem can be overcome by sink nodes’ movement. When sink node moves to locations at which nodes are distributed intensively or other key locations, it can balance nodes energy consumption and make all nodes’ residual energy tend to 0.Reference [8] proposes range constrained clustering (RCC) method. In RCC, all nodes in the monitoring area are divided into several clusters. Concorde TSP (traveling salesman problem) solver is used to obtain the optimal movement path of sink node which traverses all cluster centers. References [9–13] research into the network lifetime maximization problem, establish network lifetime optimization models with single or multiple mobile sink nodes, and use optimization methods to solve the models and obtain optimal scheme. References [9–11] consider the sink node’s movement to be discrete movement. The movement of sink node contains several anchors and sojourn time. They establish network lifetime optimization model under energy consumption constraint, flow balance constraint, and transmission power constraint. Reference [12] proposes a linear program (LP) whose solution provides a provable upper bound on the maximum lifetime possible for any given number of sinks. The centralized heuristic and distributed heuristic are proposed to solve the LP and obtain the network lifetime which is close to the optimal value. Reference [13] considers energy consumption constraint and flow balance constraint and researches into lifetime maximization problem under two different situations. The situations are fixed sojourn time and variable sojourn time.In summary, some algorithms focus on searching the movement paths, but whether optimal solution can be obtained still needs theoretical analysis and derivation. Some algorithms focus on establishing and solving the lifetime optimization models but assume that the movement paths of sink nodes are already known, while most of the above algorithms only consider single sink node. The data gathering latency is long. Therefore, based on the above references, maximizing lifetime of wireless sensor networks with mobile sink nodes (MLMS) is researched. In MLMS, the movement path selection and lifetime optimization are considered. The modified subtractive clustering method,k-means method, and nearest neighbor interpolation method are used to find the movement paths and get approximate solution of the shortest movement paths. Network lifetime optimization model with known movement paths is established. The mobile gathering and static gathering are considered. Subgradient algorithm and geometric method are used to solve the lifetime optimization model and obtain the data transmission scheme. Finally, sink nodes gather the data along the shortest movement paths. All sensor nodes transmit data according to the data transmission scheme. The simulation results clearly show that MLMS can prolong network lifetime, balance node energy consumption, and reduce data gathering latency.The remaining parts of paper are organized as follows. In Section2, the movement path selection method of sink nodes and lifetime optimization model are proposed. In Section 3, the solution of model is proposed. In Section 4, algorithm realization is proposed. In Section 5, the simulation results are presented. In Section 6, the paper is concluded.


## 2. Model Establishment

### 2.1. Algorithm Assumptions

(1)
All sensor nodes are randomly distributed in 2D monitoring area. The sensor node locations are fixed. Sink nodes can move.
(2)
In WSNs, when sink nodes are moving, they gather data. Thus, it is necessary to consider mobile gathering and static gathering of sink nodes.
(3)
When sensor nodes are not in the data gathering range of sink nodes, they store all sensing data in cache and basically are in sleep state. When sensor nodes are in the data gathering range of sink nodes, they are in work state and transmit data to one sink node by direct or multihop way.
(4)
All sensor nodes can obtain their own location coordinates by installing GPS module or using other location methods.
(5)
All sensor nodes have the same performance (such as sensing rate, maximum communication radius, initial energy, and energy consumption parameter) and use the same energy consumption model.
(6)
Energy of sensor nodes is limited and unrenewable. Energy of sink nodes is limited and renewable.
(7)
Each sink node gathers sensor nodes’ data in multihop range. But the maximum hop is a fixed number and not infinitely large.


### 2.2. Movement Path Selection

Many references consider that sink node stays at one node location, gathers data, and takes its responsibilities to sense. It basically limits the mobile location selection of sink node and does not consider other locations where sensor nodes are never distributed. Thus, their algorithms obtain local optimal solutions and have certain limitations.It is difficult to determine the optimal location coordinates directly by location information of sensor nodes. As is shown in Figure1, the monitoring area is divided into several grids of the same size and each grid is numbered. The sink node can stay at each grid center to gather data. The method enlarges the selection range of sojourn locations for sink nodes. But it is also difficult to determine the movement paths of sink nodes. Therefore, modified subtractive clustering method is used and some anchors for sink nodes based on the node distribution and residual energy are determined [14].Figure 1
Grids in the monitoring area.The potential value of each grid is(1)P(v)=x1∑j∈N(v)exp⁡⁡(-α1dvjdmax⁡)+x2∑j∈N(v)exp⁡(-α2EinitialRe(j)),
where P(v) represents potential value of gridv. gridv represents the center of grid v. dvj represents the distance from sensor node j to gridv. N(v) represents the set of sensor nodes from which the distance to grid center is not longer than maximum communication distance dmax⁡. Re(j) represents the residual energy of node j. α1 represents distance potential factor. α2 represents residual energy potential factor. x1 represents distance weight factor. x2 represents residual energy weight factor, and x1+x2=1. Around the center of grid which has large potential value, node density is high, number of nodes is large, and node residual energy is large. Sink node staying at the location of grid center is helpful to reduce node energy consumption of data transmission in the area. The modified subtractive clustering method is as follows.Step 1.
Each grid’s potential valueP(v) and the number of anchors Na=1 are initialized.Step 2.
The grid of maximum potential value is found. Its grid center as anchor point is selected.P*(Na) represents its potential value.Step 3.
The grid center is aggregation point. The sensor nodes whose minimum transmission hops to aggregation point do not exceedk are determined. Potential values of the grids in the maximum communication coverage region of those sensor nodes are subtracted:
(2)P(v)=P(v)-P*(Na).Step 4.
If the following inequality (3) holds, go to Step 5; else Na=Na+1 and go to Step 2:
(3)max⁡vP(v)≤εP*(1),
where ε represents judgment factor.Step 5.
According to the anchor locations, minimum transmission hops of sensor nodes are calculated. If minimum transmission hops of some sensor nodes are greater thank, then the sensor nodes are isolated nodes; go to Step 6; else end the method.Step 6.
Each grid’s potential value is calculated by only considering isolated nodes. The grid of maximum potential value is found. Its grid center as anchor point is selected. ConsiderNa=Na+1; go to Step 5.Circulating the above steps,Na number of anchors is obtained. In Steps 1–4, the sensor nodes whose minimum transmission hops to aggregation point do not exceed k are determined. Subtraction is used for the potential values of grids which are in the maximum communication coverage region of those sensor nodes. It has no effect on other potential values of grids. In Steps 5-6, network coverage is considered. The isolated nodes are processed. Therefore, the determined anchors in the monitoring area are distributed in the subregion around where node density is high and residual energy is large and in the subregion near the isolated nodes.When the anchors are determined, sink nodes stay at one anchor location for some time and then they move to the next anchor location. After several times, sink nodes finally move back to initial location. There are several sink nodes in network. Each sink node is located in separate subregion. Before planning the movement paths of sink nodes, it is necessary to consider that the anchors appear in which movement paths of sink nodes.k-means method [15] is used to cluster all anchors and get M (the number of sink nodes) clusters and corresponding cluster anchors. According to information of each cluster, one sink node is assigned to traverse the cluster anchors, and the movement path selection problem of multiple sink nodes is converted into several path selection problem of single sink node.In the path selection problem of single sink node, because of the complicated wireless environment, the mobile gathering efficiency of sink node is far lower than static gathering efficiency. And the too long movement distance increases the data gathering latency. It is not conducive to data cache of sensor nodes. Thus, the path selection problem is TSP. Its target is to find the path of the shortest movement distance. Because the number of anchors is not large, nearest neighbor interpolation method [16] is used to find the approximate solution of the shortest path. The steps are as follows.Step 1.
The location of sink node is initialized andi=0. The anchor v0 is the starting point. The initial closed path is v0v0.Step 2.
InV-{v0,v1,…,vi}, anchor vi+1 is found which has the nearest distance to any anchor in {v0,v1,…,vi} set, where V is a nonempty set of all sensor nodes.Step 3.
The anchorvi+1 is inserted into the closed path v0v1⋯viv0. The paths v0vi+1v1⋯viv0,v0v1vi+1⋯viv0,…,v0v1⋯vivi+1v0 are obtained. The shortest path is selected as the new shortest closed path.Step 4.
Ifi<(Nm+1), where Nm represents the number of cluster anchors for mth sink node, then go to Step 2; else obtain the approximate solution, and go to Step 5.Step 5.
According to the approximate solution, the shortest movement grid path from one anchor to another is calculated. The method is that firstly the grid centers are selected along the vertical direction. When their ordinates are the same, the grid centers are selected along the horizontal direction. The selected grid centers and anchors constitute the movement path.


### 2.3. Lifetime Optimization Model

The network lifetime is defined as the working time when network starts to run until one node runs out of energy. When the movement paths of sink nodes are determined, the optimization model of network lifetime can be transformed to the following model:(4a)max⁡min⁡i(∑mTim)(4b)s.t.:hh∑j∈N(i)fijm=Si+∑j∈N(i)fjim,∀i∈V,∀m(4c)s.t.:hh∑mTim(∑j∈N(i)fjimEelec+∑j∈N(i)fijm(Eelec+εfsdij2))s.t.:hh≤Einitial,∀i∈V,∀m(4d)s.t.:hhfijm+fjim≤Rmax⁡,L(i,j)∈L,j>i,∀m(4e)s.t.:hhfijm≥0,∀i,j∈V,∀m,where Tim represents the work time of node i when mth sink node stays at one anchor, Si represents data sensing rate of node i, and fijm represents the data transmission rate from node i to node j when the data of node i aggregate to mth sink node. Einitial represents the initial energy of sensor nodes. dij represents the transmission distance from node i to node j, εfs represents electronic energy consumption of amplifying unit signal, and Eelec represents electric energy consumption of receiving or transmitting unit data. L(i,j) represents the link from node i to node j, L represents a set of all wireless links (edges), and Rmax⁡ represents the maximum transmission rates of nodes.The constraint (4b) is flow constraint. It ensures that the transmission data are composed of sensing data and received data from neighbor nodes. The constraint (4c) is energy consumption constraint. It ensures that, during the lifetime of node, the node energy consumption which includes energy consumption of receiving data from neighbor nodes and energy consumption of transmitting data is not larger than its initial energy. The constraint (4d) is link transmission constraint. Because link bandwidth resource is limited, the total amount of link transmission data needs to be limited.


## 2.1. Algorithm Assumptions

(1)
All sensor nodes are randomly distributed in 2D monitoring area. The sensor node locations are fixed. Sink nodes can move.
(2)
In WSNs, when sink nodes are moving, they gather data. Thus, it is necessary to consider mobile gathering and static gathering of sink nodes.
(3)
When sensor nodes are not in the data gathering range of sink nodes, they store all sensing data in cache and basically are in sleep state. When sensor nodes are in the data gathering range of sink nodes, they are in work state and transmit data to one sink node by direct or multihop way.
(4)
All sensor nodes can obtain their own location coordinates by installing GPS module or using other location methods.
(5)
All sensor nodes have the same performance (such as sensing rate, maximum communication radius, initial energy, and energy consumption parameter) and use the same energy consumption model.
(6)
Energy of sensor nodes is limited and unrenewable. Energy of sink nodes is limited and renewable.
(7)
Each sink node gathers sensor nodes’ data in multihop range. But the maximum hop is a fixed number and not infinitely large.


## 2.2. Movement Path Selection

Many references consider that sink node stays at one node location, gathers data, and takes its responsibilities to sense. It basically limits the mobile location selection of sink node and does not consider other locations where sensor nodes are never distributed. Thus, their algorithms obtain local optimal solutions and have certain limitations.It is difficult to determine the optimal location coordinates directly by location information of sensor nodes. As is shown in Figure1, the monitoring area is divided into several grids of the same size and each grid is numbered. The sink node can stay at each grid center to gather data. The method enlarges the selection range of sojourn locations for sink nodes. But it is also difficult to determine the movement paths of sink nodes. Therefore, modified subtractive clustering method is used and some anchors for sink nodes based on the node distribution and residual energy are determined [14].Figure 1
Grids in the monitoring area.The potential value of each grid is(1)P(v)=x1∑j∈N(v)exp⁡⁡(-α1dvjdmax⁡)+x2∑j∈N(v)exp⁡(-α2EinitialRe(j)),
where P(v) represents potential value of gridv. gridv represents the center of grid v. dvj represents the distance from sensor node j to gridv. N(v) represents the set of sensor nodes from which the distance to grid center is not longer than maximum communication distance dmax⁡. Re(j) represents the residual energy of node j. α1 represents distance potential factor. α2 represents residual energy potential factor. x1 represents distance weight factor. x2 represents residual energy weight factor, and x1+x2=1. Around the center of grid which has large potential value, node density is high, number of nodes is large, and node residual energy is large. Sink node staying at the location of grid center is helpful to reduce node energy consumption of data transmission in the area. The modified subtractive clustering method is as follows.Step 1.
Each grid’s potential valueP(v) and the number of anchors Na=1 are initialized.Step 2.
The grid of maximum potential value is found. Its grid center as anchor point is selected.P*(Na) represents its potential value.Step 3.
The grid center is aggregation point. The sensor nodes whose minimum transmission hops to aggregation point do not exceedk are determined. Potential values of the grids in the maximum communication coverage region of those sensor nodes are subtracted:
(2)P(v)=P(v)-P*(Na).Step 4.
If the following inequality (3) holds, go to Step 5; else Na=Na+1 and go to Step 2:
(3)max⁡vP(v)≤εP*(1),
where ε represents judgment factor.Step 5.
According to the anchor locations, minimum transmission hops of sensor nodes are calculated. If minimum transmission hops of some sensor nodes are greater thank, then the sensor nodes are isolated nodes; go to Step 6; else end the method.Step 6.
Each grid’s potential value is calculated by only considering isolated nodes. The grid of maximum potential value is found. Its grid center as anchor point is selected. ConsiderNa=Na+1; go to Step 5.Circulating the above steps,Na number of anchors is obtained. In Steps 1–4, the sensor nodes whose minimum transmission hops to aggregation point do not exceed k are determined. Subtraction is used for the potential values of grids which are in the maximum communication coverage region of those sensor nodes. It has no effect on other potential values of grids. In Steps 5-6, network coverage is considered. The isolated nodes are processed. Therefore, the determined anchors in the monitoring area are distributed in the subregion around where node density is high and residual energy is large and in the subregion near the isolated nodes.When the anchors are determined, sink nodes stay at one anchor location for some time and then they move to the next anchor location. After several times, sink nodes finally move back to initial location. There are several sink nodes in network. Each sink node is located in separate subregion. Before planning the movement paths of sink nodes, it is necessary to consider that the anchors appear in which movement paths of sink nodes.k-means method [15] is used to cluster all anchors and get M (the number of sink nodes) clusters and corresponding cluster anchors. According to information of each cluster, one sink node is assigned to traverse the cluster anchors, and the movement path selection problem of multiple sink nodes is converted into several path selection problem of single sink node.In the path selection problem of single sink node, because of the complicated wireless environment, the mobile gathering efficiency of sink node is far lower than static gathering efficiency. And the too long movement distance increases the data gathering latency. It is not conducive to data cache of sensor nodes. Thus, the path selection problem is TSP. Its target is to find the path of the shortest movement distance. Because the number of anchors is not large, nearest neighbor interpolation method [16] is used to find the approximate solution of the shortest path. The steps are as follows.Step 1.
The location of sink node is initialized andi=0. The anchor v0 is the starting point. The initial closed path is v0v0.Step 2.
InV-{v0,v1,…,vi}, anchor vi+1 is found which has the nearest distance to any anchor in {v0,v1,…,vi} set, where V is a nonempty set of all sensor nodes.Step 3.
The anchorvi+1 is inserted into the closed path v0v1⋯viv0. The paths v0vi+1v1⋯viv0,v0v1vi+1⋯viv0,…,v0v1⋯vivi+1v0 are obtained. The shortest path is selected as the new shortest closed path.Step 4.
Ifi<(Nm+1), where Nm represents the number of cluster anchors for mth sink node, then go to Step 2; else obtain the approximate solution, and go to Step 5.Step 5.
According to the approximate solution, the shortest movement grid path from one anchor to another is calculated. The method is that firstly the grid centers are selected along the vertical direction. When their ordinates are the same, the grid centers are selected along the horizontal direction. The selected grid centers and anchors constitute the movement path.


## 2.3. Lifetime Optimization Model

The network lifetime is defined as the working time when network starts to run until one node runs out of energy. When the movement paths of sink nodes are determined, the optimization model of network lifetime can be transformed to the following model:(4a)max⁡min⁡i(∑mTim)(4b)s.t.:hh∑j∈N(i)fijm=Si+∑j∈N(i)fjim,∀i∈V,∀m(4c)s.t.:hh∑mTim(∑j∈N(i)fjimEelec+∑j∈N(i)fijm(Eelec+εfsdij2))s.t.:hh≤Einitial,∀i∈V,∀m(4d)s.t.:hhfijm+fjim≤Rmax⁡,L(i,j)∈L,j>i,∀m(4e)s.t.:hhfijm≥0,∀i,j∈V,∀m,where Tim represents the work time of node i when mth sink node stays at one anchor, Si represents data sensing rate of node i, and fijm represents the data transmission rate from node i to node j when the data of node i aggregate to mth sink node. Einitial represents the initial energy of sensor nodes. dij represents the transmission distance from node i to node j, εfs represents electronic energy consumption of amplifying unit signal, and Eelec represents electric energy consumption of receiving or transmitting unit data. L(i,j) represents the link from node i to node j, L represents a set of all wireless links (edges), and Rmax⁡ represents the maximum transmission rates of nodes.The constraint (4b) is flow constraint. It ensures that the transmission data are composed of sensing data and received data from neighbor nodes. The constraint (4c) is energy consumption constraint. It ensures that, during the lifetime of node, the node energy consumption which includes energy consumption of receiving data from neighbor nodes and energy consumption of transmitting data is not larger than its initial energy. The constraint (4d) is link transmission constraint. Because link bandwidth resource is limited, the total amount of link transmission data needs to be limited.


## 3. Solution of Model

The model (4a) has too many parameters and direct solution is overwhelmingly complicated; therefore solution of the model (4a) is researched from the perspective of static and mobile data gathering of sink nodes. As is shown in Figure 2, data gathering method can be divided into static gathering and mobile gathering. Static gathering is to gather data in the k-hop range when sink node stays at one anchor location (five-pointed star in Figure 2). Mobile gathering is to dynamically gather data in the k-hop range when sink node is moving from one anchor location to another. Neighbor nodes of sink node during its movement are defined as DGs. The movement rate of sink node is fast and the time of mobile gathering is relatively short. In order to evaluate the data amount of mobile gathering, assume that once DGs are in the communication range of sink node, they begin to gather data in the k-1 hop range and transmit data directly to sink node.Figure 2
Data gathering method.


### 3.1. Static Gathering

According to the above analysis, the circle movement of sink node in the path consists of several discrete events. In static gathering, network lifetime maximization problem is transformed to several optimization models of network lifetime in which the sink node stays at different anchor location. Whenmth sink node stays at location Pk, the optimization model of network lifetime is(5a)max⁡Tp(5b)s.t.:hh∑j∈VPkfijPk,m=Si+∑j∈VPkfjiPk,m,∀i∈VPk(5c)s.t.:hh(∑j∈VPkfjiPk,mEelec+∑j∈VPkfijPk,m(Eelec+εfsdij2))s.t.:hhhhh≤EinitialTp,∀i∈VPk(5d)s.t.:hhfijPk,m+fjiPk,m≤Rmax⁡,L(i,j)∈LPk,j>i(5e)s.t.:hhfjiPk,m≥0,∀i,j∈V,where Tp represents the network lifetime when mth sink node stays at location Pk and fijPk,m represents the data transmission rate from node i to node j when the data of node i aggregate to mth sink node and mth sink node stays at location Pk. VPk represents the set of sensor nodes whose minimum transmission hops to mth sink node do not exceed k when mth sink node stays at location Pk. LPk represents a set of wireless links among all sensor nodes in VPk. If node j is not the neighbor node of node i, fijPk,m=0.Letqp=1/Tp; network lifetime maximization problem (5a) is transformed to the minimization problem min⁡(qp). According to all independent variables qp and fijPk,m, the target function min⁡(qp) is not a convex function. The quadratic regularization term of node transmission rate fijPk,m is introduced. The strict convex function is qp2+∑i∈VPk∑j∈VPkψ(fijPk,m)2, where ψ (ψ≥0) is regularization factor.Optimization model (5a) of network lifetime is transformed to the optimization model as follows:(6a)min⁡(qp2+∑i∈VPk∑j∈VPkψ(fijPk,m)2)s.t.:Constraints(5b),(5d),(5e)(6b)hhh(∑j∈VPkfjiPk,mEelec+∑j∈VPkfijPk,m(Eelec+εfsdij2))hhh≤qpEinitial,∀i∈VPk.Whenψ tends to 0, the optimal solution of model (6a) tends to the optimal solution of model (5a) [17]. In order to process constraints, Lagrange multipliers are used to get the following Lagrange equation:
(7)La(qp,fijPk,m,λ,ν,μ)=qp2+∑i∈VPk∑j∈VPkψ(fijPk,m)2+∑i∈VPkλi(∑j∈VPkfijPk,m-Si-∑j∈VPkfjiPk,m)+∑i∈VPk∑j∈VPkνij(fijPk,m+fjiPk,m-Rmax⁡)+∑i∈VPkμi(∑j∈VPkfjiPk,mEelechhhhhhhhhhhhi+∑j∈VPkfijPk,m(Eelec+εfsdij2)-qpEinitial)=qp2-qpEinitial∑i∈VPkμi+∑i∈VPk∑j∈VPkψ(fijPk,m)2+∑i∈VPkλi(∑j∈VPkfijPk,m-∑j∈VPkfjiPk,m)+∑i∈VPk∑j∈VPkνij(fijPk,m+fjiPk,m)+∑i∈VPkμi(∑j∈VPkfjiPk,mEelec+∑j∈VPkfijPk,m(Eelec+εfsdij2))-∑i∈VPkλiSi-Rmax⁡∑i∈VPk∑j∈VPkνij=-∑i∈VPkλiSi-Rmax⁡∑i∈VPk∑j∈VPkνij+qp2-qpEinitial∑i∈VPk(μi)+∑i∈VPk∑j∈VPk(ψ(fijPk,m)2hhhhhhhhhhhhhh+fijPk,m(Eelecμj+μi(Eelec+εfsdij2)hhhhhhhhhhhhhhiihhhhh+λi-λj+νij+νji)ψ(fijPk,m)2).Let(8)Ga(λ,ν,μ)=min⁡(qp,fijPk,m){La(qp,fijPk,m,λ,ν,μ)}.The model (6a) is transformed to the dual model
(9)max⁡(λ,ν,μ)Ga(λ,ν,μ)s.t.hiνij≥0∀i,j∈VPkhhμi≥0∀i∈VPk.Because the target function of dual model (9) is concave differentiable function, subgradient method is used to solve it.The step length ofkth iteration φ(k)(k>0) meets the nonsummable descending rule:
(10)lim⁡k→∞φ(k)=0,∑k=1∞φ(k)=∞.When the iteration goes on, the solution of model (6a) converges to optimal value. The update formulae of dual variables in (k+1)th iteration are as follows:
(11)λi(k+1)=λi(k)-φ(k)(Si+∑j∈VPkfjiPk,m-∑j∈VPkfijPk,m),hhhhhhhhhhhhhhhihhhhhhhhhhhhhhhh∀i∈VPkνij(k+1)=max⁡{0,νij(k)-φ(k)(Rmax⁡-fijPk,m-fjiPk,m)},hhhhhhhhhhhhhhihhhhhhhhhhhhhhhh∀i,j∈VPkμi(k+1)=max⁡{0,μi(k)-φ(k)(qpEinitial-∑j∈VPkfjiPk,mEelechhhhhhhhhhhhhhhhh-∑j∈VPkfijPk,m(Eelec+εfsdij2))},hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh∀i∈VPk,
where φ(k)=w/k, w>0, and it meets nonsummable descending rule (10). The update formulae of variables qp(k+1) and (fijPk,m)(k+1) in (k+1)th iteration are as follows:
(12)qp(k+1)=argmin⁡(qp≥0)(qp2-qpEinitial∑i∈VPkμi)(fijPk,m)(k+1)=ψ(fijPk,m)2+fijPk,m(Eelecμj+μi(Eelec+εfsdij2)hhhhhhh+λi-λj+νij+νji).Subgradient method is used to solve the model (6a). The optimal network lifetime Tpmax⁡ and the corresponding data transmission scheme when the sink node stays at one anchor location are obtained.


### 3.2. Mobile Gathering

Because the anchors can cover all sensor nodes in the network, as is shown in Figure3, the path between two anchors has two cases during movement of sink nodes. One is that the movement path between two anchors appears in the communication range of node A. The other one is that part of the path is in the communication range of node A.Figure 3
Two cases of the path between two anchors.d
1 represents the distance between node A to anchor 1. d2 represents the distance between node A to anchor 2. d3 represents the distance between two anchors. da represents the total communication distance of node A when sink node is moving. If d1≤dmax⁡ and d2≤dmax⁡, the movement path between the anchors appears in the communication range of node A and da=da+d3. If d1>dmax⁡ and d2≤dmax⁡, the sink node enters into the communication range of node A. If d1≤dmax⁡ and d2>dmax⁡, the sink node leaves the communication range of node A. The coordinates of node A are (xA,yA). Sink node moves from anchor (x1,y1) to anchor (x2,y2). The line slope is z1=(y2-y1)/(x2-x1). The distance and abscissa of foot from point A to the line y-z1(x-x1)-y1=0 are
(13)d4=|yA-z1xA+z1x1-y1|1+(z1)22,x3=|xA+z1yA+z1(z1x1-y1)|1+(z1)2.When sink node enters into or leaves the communication range of nodeA, the communication distance is
(14)da={da+(dmax⁡)2-(d4)2+(d1)2-(d4)2,x2≤x3≤x1da+(dmax⁡)2-(d4)2-(d1)2-(d4)2,x3>x2,x3>x1da+(dmax⁡)2-(d4)2-(d1)2-(d4)2.x3<x2,x3<x1.The communication time between sink node and nodeA is
(15)tA=dau,
where u represents the movement speed of sink node.The topology changes frequently when sink node is moving. To facilitate the evaluation of gathering data amount, according to the topology of static gathering and communication time of sensor nodes which are in the 1-hop range of sink node, evaluate communication time of each link, and get the amount of node data transmission when sink node is moving.


## 3.1. Static Gathering

According to the above analysis, the circle movement of sink node in the path consists of several discrete events. In static gathering, network lifetime maximization problem is transformed to several optimization models of network lifetime in which the sink node stays at different anchor location. Whenmth sink node stays at location Pk, the optimization model of network lifetime is(5a)max⁡Tp(5b)s.t.:hh∑j∈VPkfijPk,m=Si+∑j∈VPkfjiPk,m,∀i∈VPk(5c)s.t.:hh(∑j∈VPkfjiPk,mEelec+∑j∈VPkfijPk,m(Eelec+εfsdij2))s.t.:hhhhh≤EinitialTp,∀i∈VPk(5d)s.t.:hhfijPk,m+fjiPk,m≤Rmax⁡,L(i,j)∈LPk,j>i(5e)s.t.:hhfjiPk,m≥0,∀i,j∈V,where Tp represents the network lifetime when mth sink node stays at location Pk and fijPk,m represents the data transmission rate from node i to node j when the data of node i aggregate to mth sink node and mth sink node stays at location Pk. VPk represents the set of sensor nodes whose minimum transmission hops to mth sink node do not exceed k when mth sink node stays at location Pk. LPk represents a set of wireless links among all sensor nodes in VPk. If node j is not the neighbor node of node i, fijPk,m=0.Letqp=1/Tp; network lifetime maximization problem (5a) is transformed to the minimization problem min⁡(qp). According to all independent variables qp and fijPk,m, the target function min⁡(qp) is not a convex function. The quadratic regularization term of node transmission rate fijPk,m is introduced. The strict convex function is qp2+∑i∈VPk∑j∈VPkψ(fijPk,m)2, where ψ (ψ≥0) is regularization factor.Optimization model (5a) of network lifetime is transformed to the optimization model as follows:(6a)min⁡(qp2+∑i∈VPk∑j∈VPkψ(fijPk,m)2)s.t.:Constraints(5b),(5d),(5e)(6b)hhh(∑j∈VPkfjiPk,mEelec+∑j∈VPkfijPk,m(Eelec+εfsdij2))hhh≤qpEinitial,∀i∈VPk.Whenψ tends to 0, the optimal solution of model (6a) tends to the optimal solution of model (5a) [17]. In order to process constraints, Lagrange multipliers are used to get the following Lagrange equation:
(7)La(qp,fijPk,m,λ,ν,μ)=qp2+∑i∈VPk∑j∈VPkψ(fijPk,m)2+∑i∈VPkλi(∑j∈VPkfijPk,m-Si-∑j∈VPkfjiPk,m)+∑i∈VPk∑j∈VPkνij(fijPk,m+fjiPk,m-Rmax⁡)+∑i∈VPkμi(∑j∈VPkfjiPk,mEelechhhhhhhhhhhhi+∑j∈VPkfijPk,m(Eelec+εfsdij2)-qpEinitial)=qp2-qpEinitial∑i∈VPkμi+∑i∈VPk∑j∈VPkψ(fijPk,m)2+∑i∈VPkλi(∑j∈VPkfijPk,m-∑j∈VPkfjiPk,m)+∑i∈VPk∑j∈VPkνij(fijPk,m+fjiPk,m)+∑i∈VPkμi(∑j∈VPkfjiPk,mEelec+∑j∈VPkfijPk,m(Eelec+εfsdij2))-∑i∈VPkλiSi-Rmax⁡∑i∈VPk∑j∈VPkνij=-∑i∈VPkλiSi-Rmax⁡∑i∈VPk∑j∈VPkνij+qp2-qpEinitial∑i∈VPk(μi)+∑i∈VPk∑j∈VPk(ψ(fijPk,m)2hhhhhhhhhhhhhh+fijPk,m(Eelecμj+μi(Eelec+εfsdij2)hhhhhhhhhhhhhhiihhhhh+λi-λj+νij+νji)ψ(fijPk,m)2).Let(8)Ga(λ,ν,μ)=min⁡(qp,fijPk,m){La(qp,fijPk,m,λ,ν,μ)}.The model (6a) is transformed to the dual model
(9)max⁡(λ,ν,μ)Ga(λ,ν,μ)s.t.hiνij≥0∀i,j∈VPkhhμi≥0∀i∈VPk.Because the target function of dual model (9) is concave differentiable function, subgradient method is used to solve it.The step length ofkth iteration φ(k)(k>0) meets the nonsummable descending rule:
(10)lim⁡k→∞φ(k)=0,∑k=1∞φ(k)=∞.When the iteration goes on, the solution of model (6a) converges to optimal value. The update formulae of dual variables in (k+1)th iteration are as follows:
(11)λi(k+1)=λi(k)-φ(k)(Si+∑j∈VPkfjiPk,m-∑j∈VPkfijPk,m),hhhhhhhhhhhhhhhihhhhhhhhhhhhhhhh∀i∈VPkνij(k+1)=max⁡{0,νij(k)-φ(k)(Rmax⁡-fijPk,m-fjiPk,m)},hhhhhhhhhhhhhhihhhhhhhhhhhhhhhh∀i,j∈VPkμi(k+1)=max⁡{0,μi(k)-φ(k)(qpEinitial-∑j∈VPkfjiPk,mEelechhhhhhhhhhhhhhhhh-∑j∈VPkfijPk,m(Eelec+εfsdij2))},hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh∀i∈VPk,
where φ(k)=w/k, w>0, and it meets nonsummable descending rule (10). The update formulae of variables qp(k+1) and (fijPk,m)(k+1) in (k+1)th iteration are as follows:
(12)qp(k+1)=argmin⁡(qp≥0)(qp2-qpEinitial∑i∈VPkμi)(fijPk,m)(k+1)=ψ(fijPk,m)2+fijPk,m(Eelecμj+μi(Eelec+εfsdij2)hhhhhhh+λi-λj+νij+νji).Subgradient method is used to solve the model (6a). The optimal network lifetime Tpmax⁡ and the corresponding data transmission scheme when the sink node stays at one anchor location are obtained.


## 3.2. Mobile Gathering

Because the anchors can cover all sensor nodes in the network, as is shown in Figure3, the path between two anchors has two cases during movement of sink nodes. One is that the movement path between two anchors appears in the communication range of node A. The other one is that part of the path is in the communication range of node A.Figure 3
Two cases of the path between two anchors.d
1 represents the distance between node A to anchor 1. d2 represents the distance between node A to anchor 2. d3 represents the distance between two anchors. da represents the total communication distance of node A when sink node is moving. If d1≤dmax⁡ and d2≤dmax⁡, the movement path between the anchors appears in the communication range of node A and da=da+d3. If d1>dmax⁡ and d2≤dmax⁡, the sink node enters into the communication range of node A. If d1≤dmax⁡ and d2>dmax⁡, the sink node leaves the communication range of node A. The coordinates of node A are (xA,yA). Sink node moves from anchor (x1,y1) to anchor (x2,y2). The line slope is z1=(y2-y1)/(x2-x1). The distance and abscissa of foot from point A to the line y-z1(x-x1)-y1=0 are
(13)d4=|yA-z1xA+z1x1-y1|1+(z1)22,x3=|xA+z1yA+z1(z1x1-y1)|1+(z1)2.When sink node enters into or leaves the communication range of nodeA, the communication distance is
(14)da={da+(dmax⁡)2-(d4)2+(d1)2-(d4)2,x2≤x3≤x1da+(dmax⁡)2-(d4)2-(d1)2-(d4)2,x3>x2,x3>x1da+(dmax⁡)2-(d4)2-(d1)2-(d4)2.x3<x2,x3<x1.The communication time between sink node and nodeA is
(15)tA=dau,
where u represents the movement speed of sink node.The topology changes frequently when sink node is moving. To facilitate the evaluation of gathering data amount, according to the topology of static gathering and communication time of sensor nodes which are in the 1-hop range of sink node, evaluate communication time of each link, and get the amount of node data transmission when sink node is moving.


## 4. Algorithm Realization

The process in which one sink node starts at initial position, traverses the anchors, and moves back to initial position is defined as one data gathering period. Algorithm of MLMS is Algorithm1.Algorithm 1
(1)      gather the information of all sensor nodes, and initialize all parameters, such asP(i), Na=1, etc;
(2)     While   (eachE(i)>0)
(3)      {
(4)     do {
(5)       calculateP(v);
(6)       find the grid of maximum potential value, and select its grid center as anchor;
(7)       calculateP(v)=P(v)-P*(Na);
(8)Na=Na+1;
(9)      }while (maxv⁡P(v)>εP*(1));
(10)    process the isolated nodes;
(11)    usek-means to obtain the M cluster;
(12)nc=0;
(13)    while    (nc≤M) {
(14)     use nearest neighbor interpolation method to find the optimal movement path;
(15)ns=0;
(16)      while    (ns≤Nm) {
(17)       initialize all parameters of sub-gradient method;k=1;
(18)       while (k<K) {
(19)       update parameters of neighbor nodes;
(20)           determine step lengthφ(k)=w/k;
(21)       solveqp(k+1) and (fijPk,m)(k+1);
(22)       update(λ,ν,μ)k+1;
(23)k=k+1;
(24)      }
(25)ns=ns+1;
(26)       }
(27)nc=nc+1;
(28)     }
(29)    inform the sink nodes to move under the optimal movement scheme;
(30)   inform all sensor nodes to transmit their data and residual energy under the optimal data transmission scheme;
(31)     gather data during certain time;
(32)    }The time complexity of MLMS is analyzed. It mainly consists of time complexity of anchor determination, clustering method, movement path determination, and data gathering method. Anchor determination needs to iteratively calculate the potential values of grid when each anchor is selected. Namely, its time complexity isΘ(n2*Na), where n represents the number of each row or column grids. Clustering method cyclically executes the division of relative anchors and calculation of new cluster centers. Namely, its time complexity is Θ(IcMNa), where Ic represents iteration number and M represents the number of clusters in network. Movement path determination uses M number of nearest neighbor interpolation method. Nearest neighbor interpolation method calculates all possibilities when one anchor is added. Namely, its time complexity is Θ(N12+⋯+Nm2+⋯+NM2). Data gathering method uses Na subgradient algorithm. Subgradient algorithm mainly executes K times of formulae (11)-(12); namely, its time complexity is Θ(K|V|2Na).


## 5. Simulation Realization and Analysis

### 5.1. Simulation Parameters

In the simulation, the energy consumption of calculation, data fusion, information inquiry packet transmission, timeout retransmission, and debugging are not considered. Only the energy consumption of data wireless communication is considered.Eelec is 50 nJ/bit, εfs is 100 pJ/bit/m2, dmax⁡ is 200 m, edge length of simulation area is 1000 m, Einitial is 1000 J, ε is 0.4, Si is 1 Mbit/h, Rmax⁡ is 5 Mbit/h, w is 5*10-8, ψ is 1*10-4, number of iterations K in the subgradient method is 2000, and u is 5.5 m/s.The network lifetime is defined as the number of data gathering cycles (DGC) sink nodes complete in the time when network starts to run until one node runs out of energy. DGC is the working time (does not include the sleep time) in which all sensor nodes successfully transmit 1 Mbit data to sink node.Average node energy consumption = total energy consumption of all sensor nodes when one node runs out of energy/(number of nodes* number of DGC).Residual energy variance is the residual energy variance of all sensor nodes when one node runs out of energy.The network data gathering latency of multiple sink nodes is(16)tdelay=(∑mtdm)M,
where tdm represents data gathering latency of mth sink node. The data gathering latency of mth sink node is the half of data gathering period [18]:
(17)tdm=tcm2=(∑ptpm+Pathm/u)2,
where tcm represents data gathering period of mth sink node and tpm represents the sojourn time of mth sink node at anchor p. Pathm represents the movement path distance of mth sink node.


### 5.2. Simulation Result Analysis

The movement paths of sink nodes are analyzed when the nodes are uniformly distributed. Figure4 is obtained when the number of nodes is 100, x1=0.5, α1=1, α2=2, the number of grids is 30*30, the gathering hop is 2, and the number of sink nodes is 2. As is shown in Figure 4, the 1000 m * 1000 m monitoring area is divided into 30*30 number of grids. All 100 sensor nodes (hollow circle) are uniformly distributed. There are five anchors (five-pointed star) which are divided into two clusters. Each sink node selects the cluster anchors and has the grid movement path.Figure 4
Grid movement paths of sink nodes.The solution convergence of static gathering model is researched and Figure5 is obtained with the same parameters in Figure 4. As shown in Figure 5, when the number of iterations increases, the value of network lifetime when sink node stays at one anchor location can converge to optimal value. The solution method of static gathering model is convergent.Figure 5
Value of network lifetime when sink node stays at one anchor location.In order to verify the effectiveness of MLMS, Ratio_w [6], TPGF [7], RCC [8], GRND (grid random scheme) [12], and MLMS are compared. In Ratio_w and TPGF, sink node is static. In RCC, GRND, and MLMS, sink nodes are mobile. In RCC, the grid center which is the closest to one cluster center is selected as anchor and the optimization method in MLMS is used for data gathering. In GRND, the anchors are randomly selected and the optimization method in MLMS is used for data gathering. The location coordinates of 60, 80, 100, 120, 140, 160, and 180 sensor nodes are uniformly generated in the area. For each fixed number of sensor nodes, 10 different network topologies are generated. Their mean values of network lifetime, residual energy variance, and data gathering latency are calculated to evaluate the algorithm’s performance.Figure6 compares the network lifetime. As is shown in Figure 6, the network lifetime of MLMS is optimal. The network lifetime of algorithms with mobile sink node is longer than the network lifetime of algorithms with static sink node. The reason is that MLMS comprehensively analyzes the node density, residual energy, and network coverage, uses the movement path selection method to find the movement path scheme, and uses subgradient method to maximize the network lifetime and obtain the optimal data transmission scheme. All of those methods balance the node energy consumption of communication and prolong network lifetime. Ratio_w and TPGF are for static WSNs and do not consider the mobility of sink nodes. The two algorithms easily cause energy hole problem, so the network lifetimes are short.Figure 6
Network lifetime comparison.Because, in TPGF and Ratio_w, only hub nodes consume a lot of energy, other nodes have much residual energy, so they have greater residual energy variances than RCC, GRND, and MLMS. In order to conveniently display the simulation result, Figure7 only shows the residual energy variance of RCC, GRND, and MLMS when one sensor node runs out of energy. As is shown in Figure 7, MLMS has the lowest residual energy variance. RCC has the largest residual energy variance. The reason is that MLMS obtains the anchor distribution considering node density, residual energy, and network coverage. All sensor nodes have the opportunity to transmit data near the sink nodes. It balances the node energy consumption. Therefore, all sensor nodes basically exhaust the energy and the residual energy variance is the lowest.Figure 7
Residual energy variance comparison.Ratio_w and TPGF are real-time data gathering algorithms. RCC, GRND, and MLMS are mobile data gathering algorithms. When sensor nodes are not in the data gathering range of sink nodes, they are basically in the sleep state. The two types of data gathering latency are bad comparison. Therefore, Figure8 compares the data gathering latency of RCC, GRND, and MLMS. As is shown in Figure 8, MLMS has the lowest data gathering latency. RCC has the largest data gathering latency. The reason is that MLMS finds the best movement path scheme of sink nodes. Sink nodes gather data along the shorter movement path and the data gathering latency is lower.Figure 8
Data gathering latency comparison.In summary, compared with Ratio_w, TPGF, RCC, and GRND, MLMS makes full use of node energy to prolong network lifetime, balance node energy consumption, and reduce data gathering latency.


### 5.3. Key Parameters Analysis

In MLMS, number of grids, parameters in modified subtractive clustering method, gathering hop, and number of sink nodes affect the network lifetime, node energy consumption, and data gathering latency. Then 10 different network topologies in which nodes are randomly distributed are generated. In the simulation, exhaustive method is used to obtain the simulation data. Some possible key parameters are selected and calculated with loops and the simulation results are obtained. For convenience of explanation, the calculated simulation data when one parameter changes and other parameters are fixed are analyzed as an example.


#### 5.3.1. Number Selection of Grids

The simulation data are analyzed (e.g., the number of nodes is 100, the gathering hop is 2, the number of sink nodes is 2, and the numbers of grids are10*10, 20*20, 30*30, 40*40, 50*50, and 60*60, resp.). As is shown in Figures 9 and 10, when the number of grids is 30*30, the mean value of network lifetime (the red line) is maximum and the mean value of average node energy consumption is minimum. The reason is that when the number of grids is small, the side length of grid is large and the optional movement locations of sink nodes are less. The anchor locations have not met the optimal solution; therefore, the network lifetime is smaller and average node energy consumption is larger when the number of grids is 10*10 or 20*20. When the number of grids increases, the optional movement locations of sink nodes increase and the selected anchors are relatively close to the optimal locations, so the network lifetime increases. When the number of grids reaches certain number, it slightly affects the performance of MLMS. But, when the number of grids increases, the coordinates of anchors have some change. It affects the mobile gathering of sink nodes, so the network lifetime and average node energy consumption fluctuate around optimal values when the numbers of grids are 40*40, 50*50, and 60*60.Figure 9
The effect on network lifetime under different number of grids.Figure 10
The effect on average node energy consumption under different number of grids.In summary, when the number of grids reaches certain number, it slightly affects network lifetime but increases the computation amount of algorithm.


#### 5.3.2. Parameter Selection in Modified Subtractive Clustering Method

There are multiple parametersx1, x2, α1, and α2 in formula (1). The set of x1 is {0.1,0.3,0.5,0.7,0.9,1}; the set of α1 and α2 is {1,2,3,4,5,6}. The values of x1, α1, and α2 are selected in their sets, respectively.The simulation data are analyzed (e.g.,x1=0.5, x2=0.5, the number of nodes is 100, the gathering hop is 2, the number of sink nodes is 2, and the number of grids is 30*30). As is shown in Figures 11 and 12, when α1 is the small value (1,2,3), the network lifetime is comparatively long and the average node energy consumption is comparatively small. Network lifetime has the maximum value and average node energy consumption has the minimum value when α2=2. When α1 is the large value (4,5,6), with the α2 increases, the network lifetime becomes shorter and the average node energy consumption becomes larger. The reason is that when α1 is the small value (1,2,3), according to formula (1), the distance between node and grid center has great effect on the potential values of grids. The anchors are the locations around where node dense is high, so the network lifetime is longer and the average node energy consumption is smaller than that when α1 is the large value. When α2=2, the residual energy plays its effect on the potential values and the selected anchors are fit for the network topology. So network lifetime has the maximum value and average node energy consumption has the minimum value. When α1 is the large value (4,5,6), the effect of the distance between node and grid center on the potential values of grids weakens. With the α2 decreases, the effect of residual energy enhances; thus, the network lifetime increases and the average node energy consumption reduces.Figure 11
The effect on network lifetime under differentα1 and α2.Figure 12
The effect on average node energy consumption under differentα1 and α2.In summary, in MLMS, the smallα1 and α2 can prolong the network lifetime.The simulation data are analyzed (e.g.,α1=1, α2=2, the number of nodes is 100, the gathering hop is 2, the number of sink nodes is 2, and the number of grids is 30*30). As is shown in Figures 13 and 14, when x1=0.5, the mean value of network lifetime (the red line) is maximum and the mean value of average node energy consumption is minimum. The reason is that if x1 is 0.1 or 0.3, the effect of node residual energy on potential values of grids is prominent. Some anchors are the grid centers around where the node residual energy is large but the communication distance is also long. It increases the energy consumption of communication and reduces network lifetime. When x1 is 0.7, 0.9, or 1, the effect of the communication distance on potential values of grid network node is prominent. Some anchors are the grid centers around where the communication distance is small but the residual energy is also small. It increases the relay burden of low residual energy nodes, improves their energy consumption of data forwarding, and reduces the network lifetime.Figure 13
The effect on network lifetime under differentx1.Figure 14
The effect on average node energy consumption under differentx1.In summary, in MLMS, too large or too smallx1 and x2 affect the performance of MLMS.


#### 5.3.3. Gathering Hop Selection

The simulation data are analyzed (e.g., the gathering hopsk are 1, 2, 3, resp., the number of sink nodes is 2, and the number of grids is 30*30). As is shown in Figures 15 and 16, when the gathering hop increases, the network lifetime is shorter and data gathering latency is lower. The reason is that when the gathering hop is 1, sink nodes only gather the data of neighbor nodes. The communication distance is short and sensor nodes do not forward other data. Therefore, it reduces the node energy consumption and prolongs the network lifetime. However, in order to ensure network coverage, sink node needs to gather data near all sensor nodes. It greatly increases the movement distance and data gathering latency. When the gathering hop of sink nodes increases, their gathering range increases. The sensor nodes near sink nodes not only transmit their own data, but also take the task of forwarding other data. It consumes much energy. The larger the gathering hop is, the more the data transmission amount is, the greater the node energy consumption is, and the shorter the network lifetime is. However, with the gathering hop increases, the movement distance in one date gathering period reduces, and the data gathering latency greatly reduces.Figure 15
The effect on network lifetime under different gathering hop.Figure 16
The effect on data gathering latency under different gathering hop.In summary, in MLMS, the gathering hop selection needs to be tradeoff between network lifetime and data gathering latency.


#### 5.3.4. The Number Selection of Sink Nodes

The simulation data are analyzed (e.g., the gathering hop is 2, the numbers of sink nodes are 1, 2, 3, resp., and the number of grids is30*30). The data of one sink node represents the data of lifetime optimization algorithm with single mobile sink node. In the algorithm, only single sink node moves to gather data and k-means algorithm is not used to cluster, and the data gathering is the same as data gathering in MLMS. As is shown in Figures 17 and 18, when the number of sink node increases, network lifetime changes a little, but the data gathering latency is significantly smaller. The reason is that when the number of sink nodes is 1, sink node needs to traverse all the anchors and gather the data in k-hop range. When the number of sink nodes increases, more sink nodes are involved in data gathering. Each sink node only needs to move through some anchors. It greatly reduces the data gathering latency. But no matter how much the number of sink nodes is, the network topology and the selected anchors do not change. The energy consumption of static gathering is the same. There are some differences in the movement paths and the mobile gathering has some effect on the energy consumption. Therefore, when the number of sink nodes increases, the network lifetime changes a little.Figure 17
The effect on network lifetime under different number of sink nodes.Figure 18
The effect on data gathering latency under different number of sink nodes.In summary, in MLMS, the number of sink nodes affects the data gathering latency but slightly affects the network lifetime. Compared with lifetime optimization algorithm with single sink node, MLMS greatly reduces the data gathering latency.


## 5.1. Simulation Parameters

In the simulation, the energy consumption of calculation, data fusion, information inquiry packet transmission, timeout retransmission, and debugging are not considered. Only the energy consumption of data wireless communication is considered.Eelec is 50 nJ/bit, εfs is 100 pJ/bit/m2, dmax⁡ is 200 m, edge length of simulation area is 1000 m, Einitial is 1000 J, ε is 0.4, Si is 1 Mbit/h, Rmax⁡ is 5 Mbit/h, w is 5*10-8, ψ is 1*10-4, number of iterations K in the subgradient method is 2000, and u is 5.5 m/s.The network lifetime is defined as the number of data gathering cycles (DGC) sink nodes complete in the time when network starts to run until one node runs out of energy. DGC is the working time (does not include the sleep time) in which all sensor nodes successfully transmit 1 Mbit data to sink node.Average node energy consumption = total energy consumption of all sensor nodes when one node runs out of energy/(number of nodes* number of DGC).Residual energy variance is the residual energy variance of all sensor nodes when one node runs out of energy.The network data gathering latency of multiple sink nodes is(16)tdelay=(∑mtdm)M,
where tdm represents data gathering latency of mth sink node. The data gathering latency of mth sink node is the half of data gathering period [18]:
(17)tdm=tcm2=(∑ptpm+Pathm/u)2,
where tcm represents data gathering period of mth sink node and tpm represents the sojourn time of mth sink node at anchor p. Pathm represents the movement path distance of mth sink node.


## 5.2. Simulation Result Analysis

The movement paths of sink nodes are analyzed when the nodes are uniformly distributed. Figure4 is obtained when the number of nodes is 100, x1=0.5, α1=1, α2=2, the number of grids is 30*30, the gathering hop is 2, and the number of sink nodes is 2. As is shown in Figure 4, the 1000 m * 1000 m monitoring area is divided into 30*30 number of grids. All 100 sensor nodes (hollow circle) are uniformly distributed. There are five anchors (five-pointed star) which are divided into two clusters. Each sink node selects the cluster anchors and has the grid movement path.Figure 4
Grid movement paths of sink nodes.The solution convergence of static gathering model is researched and Figure5 is obtained with the same parameters in Figure 4. As shown in Figure 5, when the number of iterations increases, the value of network lifetime when sink node stays at one anchor location can converge to optimal value. The solution method of static gathering model is convergent.Figure 5
Value of network lifetime when sink node stays at one anchor location.In order to verify the effectiveness of MLMS, Ratio_w [6], TPGF [7], RCC [8], GRND (grid random scheme) [12], and MLMS are compared. In Ratio_w and TPGF, sink node is static. In RCC, GRND, and MLMS, sink nodes are mobile. In RCC, the grid center which is the closest to one cluster center is selected as anchor and the optimization method in MLMS is used for data gathering. In GRND, the anchors are randomly selected and the optimization method in MLMS is used for data gathering. The location coordinates of 60, 80, 100, 120, 140, 160, and 180 sensor nodes are uniformly generated in the area. For each fixed number of sensor nodes, 10 different network topologies are generated. Their mean values of network lifetime, residual energy variance, and data gathering latency are calculated to evaluate the algorithm’s performance.Figure6 compares the network lifetime. As is shown in Figure 6, the network lifetime of MLMS is optimal. The network lifetime of algorithms with mobile sink node is longer than the network lifetime of algorithms with static sink node. The reason is that MLMS comprehensively analyzes the node density, residual energy, and network coverage, uses the movement path selection method to find the movement path scheme, and uses subgradient method to maximize the network lifetime and obtain the optimal data transmission scheme. All of those methods balance the node energy consumption of communication and prolong network lifetime. Ratio_w and TPGF are for static WSNs and do not consider the mobility of sink nodes. The two algorithms easily cause energy hole problem, so the network lifetimes are short.Figure 6
Network lifetime comparison.Because, in TPGF and Ratio_w, only hub nodes consume a lot of energy, other nodes have much residual energy, so they have greater residual energy variances than RCC, GRND, and MLMS. In order to conveniently display the simulation result, Figure7 only shows the residual energy variance of RCC, GRND, and MLMS when one sensor node runs out of energy. As is shown in Figure 7, MLMS has the lowest residual energy variance. RCC has the largest residual energy variance. The reason is that MLMS obtains the anchor distribution considering node density, residual energy, and network coverage. All sensor nodes have the opportunity to transmit data near the sink nodes. It balances the node energy consumption. Therefore, all sensor nodes basically exhaust the energy and the residual energy variance is the lowest.Figure 7
Residual energy variance comparison.Ratio_w and TPGF are real-time data gathering algorithms. RCC, GRND, and MLMS are mobile data gathering algorithms. When sensor nodes are not in the data gathering range of sink nodes, they are basically in the sleep state. The two types of data gathering latency are bad comparison. Therefore, Figure8 compares the data gathering latency of RCC, GRND, and MLMS. As is shown in Figure 8, MLMS has the lowest data gathering latency. RCC has the largest data gathering latency. The reason is that MLMS finds the best movement path scheme of sink nodes. Sink nodes gather data along the shorter movement path and the data gathering latency is lower.Figure 8
Data gathering latency comparison.In summary, compared with Ratio_w, TPGF, RCC, and GRND, MLMS makes full use of node energy to prolong network lifetime, balance node energy consumption, and reduce data gathering latency.


## 5.3. Key Parameters Analysis

In MLMS, number of grids, parameters in modified subtractive clustering method, gathering hop, and number of sink nodes affect the network lifetime, node energy consumption, and data gathering latency. Then 10 different network topologies in which nodes are randomly distributed are generated. In the simulation, exhaustive method is used to obtain the simulation data. Some possible key parameters are selected and calculated with loops and the simulation results are obtained. For convenience of explanation, the calculated simulation data when one parameter changes and other parameters are fixed are analyzed as an example.


### 5.3.1. Number Selection of Grids

The simulation data are analyzed (e.g., the number of nodes is 100, the gathering hop is 2, the number of sink nodes is 2, and the numbers of grids are10*10, 20*20, 30*30, 40*40, 50*50, and 60*60, resp.). As is shown in Figures 9 and 10, when the number of grids is 30*30, the mean value of network lifetime (the red line) is maximum and the mean value of average node energy consumption is minimum. The reason is that when the number of grids is small, the side length of grid is large and the optional movement locations of sink nodes are less. The anchor locations have not met the optimal solution; therefore, the network lifetime is smaller and average node energy consumption is larger when the number of grids is 10*10 or 20*20. When the number of grids increases, the optional movement locations of sink nodes increase and the selected anchors are relatively close to the optimal locations, so the network lifetime increases. When the number of grids reaches certain number, it slightly affects the performance of MLMS. But, when the number of grids increases, the coordinates of anchors have some change. It affects the mobile gathering of sink nodes, so the network lifetime and average node energy consumption fluctuate around optimal values when the numbers of grids are 40*40, 50*50, and 60*60.Figure 9
The effect on network lifetime under different number of grids.Figure 10
The effect on average node energy consumption under different number of grids.In summary, when the number of grids reaches certain number, it slightly affects network lifetime but increases the computation amount of algorithm.


### 5.3.2. Parameter Selection in Modified Subtractive Clustering Method

There are multiple parametersx1, x2, α1, and α2 in formula (1). The set of x1 is {0.1,0.3,0.5,0.7,0.9,1}; the set of α1 and α2 is {1,2,3,4,5,6}. The values of x1, α1, and α2 are selected in their sets, respectively.The simulation data are analyzed (e.g.,x1=0.5, x2=0.5, the number of nodes is 100, the gathering hop is 2, the number of sink nodes is 2, and the number of grids is 30*30). As is shown in Figures 11 and 12, when α1 is the small value (1,2,3), the network lifetime is comparatively long and the average node energy consumption is comparatively small. Network lifetime has the maximum value and average node energy consumption has the minimum value when α2=2. When α1 is the large value (4,5,6), with the α2 increases, the network lifetime becomes shorter and the average node energy consumption becomes larger. The reason is that when α1 is the small value (1,2,3), according to formula (1), the distance between node and grid center has great effect on the potential values of grids. The anchors are the locations around where node dense is high, so the network lifetime is longer and the average node energy consumption is smaller than that when α1 is the large value. When α2=2, the residual energy plays its effect on the potential values and the selected anchors are fit for the network topology. So network lifetime has the maximum value and average node energy consumption has the minimum value. When α1 is the large value (4,5,6), the effect of the distance between node and grid center on the potential values of grids weakens. With the α2 decreases, the effect of residual energy enhances; thus, the network lifetime increases and the average node energy consumption reduces.Figure 11
The effect on network lifetime under differentα1 and α2.Figure 12
The effect on average node energy consumption under differentα1 and α2.In summary, in MLMS, the smallα1 and α2 can prolong the network lifetime.The simulation data are analyzed (e.g.,α1=1, α2=2, the number of nodes is 100, the gathering hop is 2, the number of sink nodes is 2, and the number of grids is 30*30). As is shown in Figures 13 and 14, when x1=0.5, the mean value of network lifetime (the red line) is maximum and the mean value of average node energy consumption is minimum. The reason is that if x1 is 0.1 or 0.3, the effect of node residual energy on potential values of grids is prominent. Some anchors are the grid centers around where the node residual energy is large but the communication distance is also long. It increases the energy consumption of communication and reduces network lifetime. When x1 is 0.7, 0.9, or 1, the effect of the communication distance on potential values of grid network node is prominent. Some anchors are the grid centers around where the communication distance is small but the residual energy is also small. It increases the relay burden of low residual energy nodes, improves their energy consumption of data forwarding, and reduces the network lifetime.Figure 13
The effect on network lifetime under differentx1.Figure 14
The effect on average node energy consumption under differentx1.In summary, in MLMS, too large or too smallx1 and x2 affect the performance of MLMS.


### 5.3.3. Gathering Hop Selection

The simulation data are analyzed (e.g., the gathering hopsk are 1, 2, 3, resp., the number of sink nodes is 2, and the number of grids is 30*30). As is shown in Figures 15 and 16, when the gathering hop increases, the network lifetime is shorter and data gathering latency is lower. The reason is that when the gathering hop is 1, sink nodes only gather the data of neighbor nodes. The communication distance is short and sensor nodes do not forward other data. Therefore, it reduces the node energy consumption and prolongs the network lifetime. However, in order to ensure network coverage, sink node needs to gather data near all sensor nodes. It greatly increases the movement distance and data gathering latency. When the gathering hop of sink nodes increases, their gathering range increases. The sensor nodes near sink nodes not only transmit their own data, but also take the task of forwarding other data. It consumes much energy. The larger the gathering hop is, the more the data transmission amount is, the greater the node energy consumption is, and the shorter the network lifetime is. However, with the gathering hop increases, the movement distance in one date gathering period reduces, and the data gathering latency greatly reduces.Figure 15
The effect on network lifetime under different gathering hop.Figure 16
The effect on data gathering latency under different gathering hop.In summary, in MLMS, the gathering hop selection needs to be tradeoff between network lifetime and data gathering latency.


### 5.3.4. The Number Selection of Sink Nodes

The simulation data are analyzed (e.g., the gathering hop is 2, the numbers of sink nodes are 1, 2, 3, resp., and the number of grids is30*30). The data of one sink node represents the data of lifetime optimization algorithm with single mobile sink node. In the algorithm, only single sink node moves to gather data and k-means algorithm is not used to cluster, and the data gathering is the same as data gathering in MLMS. As is shown in Figures 17 and 18, when the number of sink node increases, network lifetime changes a little, but the data gathering latency is significantly smaller. The reason is that when the number of sink nodes is 1, sink node needs to traverse all the anchors and gather the data in k-hop range. When the number of sink nodes increases, more sink nodes are involved in data gathering. Each sink node only needs to move through some anchors. It greatly reduces the data gathering latency. But no matter how much the number of sink nodes is, the network topology and the selected anchors do not change. The energy consumption of static gathering is the same. There are some differences in the movement paths and the mobile gathering has some effect on the energy consumption. Therefore, when the number of sink nodes increases, the network lifetime changes a little.Figure 17
The effect on network lifetime under different number of sink nodes.Figure 18
The effect on data gathering latency under different number of sink nodes.In summary, in MLMS, the number of sink nodes affects the data gathering latency but slightly affects the network lifetime. Compared with lifetime optimization algorithm with single sink node, MLMS greatly reduces the data gathering latency.


## 5.3.1. Number Selection of Grids

The simulation data are analyzed (e.g., the number of nodes is 100, the gathering hop is 2, the number of sink nodes is 2, and the numbers of grids are10*10, 20*20, 30*30, 40*40, 50*50, and 60*60, resp.). As is shown in Figures 9 and 10, when the number of grids is 30*30, the mean value of network lifetime (the red line) is maximum and the mean value of average node energy consumption is minimum. The reason is that when the number of grids is small, the side length of grid is large and the optional movement locations of sink nodes are less. The anchor locations have not met the optimal solution; therefore, the network lifetime is smaller and average node energy consumption is larger when the number of grids is 10*10 or 20*20. When the number of grids increases, the optional movement locations of sink nodes increase and the selected anchors are relatively close to the optimal locations, so the network lifetime increases. When the number of grids reaches certain number, it slightly affects the performance of MLMS. But, when the number of grids increases, the coordinates of anchors have some change. It affects the mobile gathering of sink nodes, so the network lifetime and average node energy consumption fluctuate around optimal values when the numbers of grids are 40*40, 50*50, and 60*60.Figure 9
The effect on network lifetime under different number of grids.Figure 10
The effect on average node energy consumption under different number of grids.In summary, when the number of grids reaches certain number, it slightly affects network lifetime but increases the computation amount of algorithm.


## 5.3.2. Parameter Selection in Modified Subtractive Clustering Method

There are multiple parametersx1, x2, α1, and α2 in formula (1). The set of x1 is {0.1,0.3,0.5,0.7,0.9,1}; the set of α1 and α2 is {1,2,3,4,5,6}. The values of x1, α1, and α2 are selected in their sets, respectively.The simulation data are analyzed (e.g.,x1=0.5, x2=0.5, the number of nodes is 100, the gathering hop is 2, the number of sink nodes is 2, and the number of grids is 30*30). As is shown in Figures 11 and 12, when α1 is the small value (1,2,3), the network lifetime is comparatively long and the average node energy consumption is comparatively small. Network lifetime has the maximum value and average node energy consumption has the minimum value when α2=2. When α1 is the large value (4,5,6), with the α2 increases, the network lifetime becomes shorter and the average node energy consumption becomes larger. The reason is that when α1 is the small value (1,2,3), according to formula (1), the distance between node and grid center has great effect on the potential values of grids. The anchors are the locations around where node dense is high, so the network lifetime is longer and the average node energy consumption is smaller than that when α1 is the large value. When α2=2, the residual energy plays its effect on the potential values and the selected anchors are fit for the network topology. So network lifetime has the maximum value and average node energy consumption has the minimum value. When α1 is the large value (4,5,6), the effect of the distance between node and grid center on the potential values of grids weakens. With the α2 decreases, the effect of residual energy enhances; thus, the network lifetime increases and the average node energy consumption reduces.Figure 11
The effect on network lifetime under differentα1 and α2.Figure 12
The effect on average node energy consumption under differentα1 and α2.In summary, in MLMS, the smallα1 and α2 can prolong the network lifetime.The simulation data are analyzed (e.g.,α1=1, α2=2, the number of nodes is 100, the gathering hop is 2, the number of sink nodes is 2, and the number of grids is 30*30). As is shown in Figures 13 and 14, when x1=0.5, the mean value of network lifetime (the red line) is maximum and the mean value of average node energy consumption is minimum. The reason is that if x1 is 0.1 or 0.3, the effect of node residual energy on potential values of grids is prominent. Some anchors are the grid centers around where the node residual energy is large but the communication distance is also long. It increases the energy consumption of communication and reduces network lifetime. When x1 is 0.7, 0.9, or 1, the effect of the communication distance on potential values of grid network node is prominent. Some anchors are the grid centers around where the communication distance is small but the residual energy is also small. It increases the relay burden of low residual energy nodes, improves their energy consumption of data forwarding, and reduces the network lifetime.Figure 13
The effect on network lifetime under differentx1.Figure 14
The effect on average node energy consumption under differentx1.In summary, in MLMS, too large or too smallx1 and x2 affect the performance of MLMS.


## 5.3.3. Gathering Hop Selection

The simulation data are analyzed (e.g., the gathering hopsk are 1, 2, 3, resp., the number of sink nodes is 2, and the number of grids is 30*30). As is shown in Figures 15 and 16, when the gathering hop increases, the network lifetime is shorter and data gathering latency is lower. The reason is that when the gathering hop is 1, sink nodes only gather the data of neighbor nodes. The communication distance is short and sensor nodes do not forward other data. Therefore, it reduces the node energy consumption and prolongs the network lifetime. However, in order to ensure network coverage, sink node needs to gather data near all sensor nodes. It greatly increases the movement distance and data gathering latency. When the gathering hop of sink nodes increases, their gathering range increases. The sensor nodes near sink nodes not only transmit their own data, but also take the task of forwarding other data. It consumes much energy. The larger the gathering hop is, the more the data transmission amount is, the greater the node energy consumption is, and the shorter the network lifetime is. However, with the gathering hop increases, the movement distance in one date gathering period reduces, and the data gathering latency greatly reduces.Figure 15
The effect on network lifetime under different gathering hop.Figure 16
The effect on data gathering latency under different gathering hop.In summary, in MLMS, the gathering hop selection needs to be tradeoff between network lifetime and data gathering latency.


## 5.3.4. The Number Selection of Sink Nodes

The simulation data are analyzed (e.g., the gathering hop is 2, the numbers of sink nodes are 1, 2, 3, resp., and the number of grids is30*30). The data of one sink node represents the data of lifetime optimization algorithm with single mobile sink node. In the algorithm, only single sink node moves to gather data and k-means algorithm is not used to cluster, and the data gathering is the same as data gathering in MLMS. As is shown in Figures 17 and 18, when the number of sink node increases, network lifetime changes a little, but the data gathering latency is significantly smaller. The reason is that when the number of sink nodes is 1, sink node needs to traverse all the anchors and gather the data in k-hop range. When the number of sink nodes increases, more sink nodes are involved in data gathering. Each sink node only needs to move through some anchors. It greatly reduces the data gathering latency. But no matter how much the number of sink nodes is, the network topology and the selected anchors do not change. The energy consumption of static gathering is the same. There are some differences in the movement paths and the mobile gathering has some effect on the energy consumption. Therefore, when the number of sink nodes increases, the network lifetime changes a little.Figure 17
The effect on network lifetime under different number of sink nodes.Figure 18
The effect on data gathering latency under different number of sink nodes.In summary, in MLMS, the number of sink nodes affects the data gathering latency but slightly affects the network lifetime. Compared with lifetime optimization algorithm with single sink node, MLMS greatly reduces the data gathering latency.


## 6. Conclusions

In MLMS, the movement path selection method is proposed and network lifetime optimization model with known movement paths is established. The modified subtractive clustering method,k-means method, nearest neighbor interpolation method, subgradient method, and other methods are used to calculate the network lifetime, movement path scheme, and data transmission scheme. All sensor nodes transmit data according to the optimal data transmission scheme and sink nodes gather the data along the shortest movement paths. Compared with Ratio_w, TPGF, GRND, and RCC, MLMS has an improvement.The time complexity of MLMS is high. Some iteration time needs to converge. Only when the energy consumption of data transmission is far greater than the energy consumption of optimal solution calculation, the operation of MLMS works well. Therefore, the next goal is to research into the distributed lifetime maximization algorithm of wireless sensor networks with mobile sink nodes. In the algorithm, each node establishes its own optimization model according to the local information which is exchanged with neighbor nodes. The sink node solves its own model to find the next sojourn location and time. The sensor node solves its own model to judge the next forwarding node. Finally, all nodes find the optimal scheme and network lifetime is prolonged by distributed calculation.



---

*Source: 762979-2014-09-30.xml*