# An Energy-Efficient and Relay Hop Bounded Mobile Data Gathering Algorithm in Wireless Sensor Networks

Authors: Ling Chen; Jianxin Wang; Xiaoqing Peng; Xiaoyan Kui
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

Recent studies reveal that great benefit can be achieved by employing mobile collectors to gather data in wireless sensor networks. Since the mobile collector can traverse the transmission range of each sensor, the energy of nodes may be saved near maximally. However, for directly receiving data packet from every node, the length of mobile collector route should be very long. Hence it may significantly increase the data gathering latency. To solve this problem, several algorithms have been proposed. One of them called BRH-MDG found that data gathering latency can be effectively shortened by performing proper local aggregation via multihop transmissions and then uploading the aggregated data to the mobile collector. But, the BRH-MDG algorithm did not carefully analyze and optimize the energy consumption of the entire network. In this paper, we propose a mathematical model for the energy consumption of the LNs and present a new algorithm called EEBRHM. The simulation results show that under the premise of bounded relay hop, compared with BRH-MDG, EEBRHM can prolong the networks lifetime by 730%.


---

## Body

## 1. Introduction

Recent years, with better foreground of practical application, research work on wireless sensor networks (WSNs) has attracted more and more attention. In general, a WSN is made up of low-cost and low-energy sensor nodes that can communicate with each other by wireless links. Since sensor nodes are often deployed in remote or inaccessible environments, recharging sensors’ battery is usually impossible. If the battery of one sensor node runs out, the node will die. Thus, how to save sensor energy and maximize network lifetime is a main challenge of WSNs. Existing research works indicate that the communication cost is the main part of sensor nodes’ energy consumption. And most of communication cost is produced in the process of gathering sensing data from sensor nodes. Thus, how to design an energy-efficient data gathering protocol has become a hot research issue [1].Some data gather protocols which focus on sensor nodes themselves [2–13], which can be divided into three categories: (1) cluster-based protocols [2–5], (2) chain-based protocols [6–8], (3) tree-based protocols [9–13]. In these protocols, sensing data will be sent to static data sink through one and more relay nodes. However, the multihop transmission will consume plenty of energy and the nodes near around data sink will consume much more energy than others. As a result, these nodes become the bottlenecks of the network. Once these bottleneck-nodes fail, other sensors cannot send sensing data to sink and that means the lifetime of the whole network is over, although other nodes’ batteries are still enough. Therefore, all these protocols may cause nonuniform energy consumption across the WSN.Particularly in a large-scale data-centric WSN, it will be difficult to obtain an ideal lifetime of the whole network if only use static data sink to gather data from all sensor nodes [14, 15]. Thus, recent research work focuses on mobile data gathering, which sets one or more mobile collectors with powerful transceivers and batteries to traverse the whole sensing area. In general, to collect data from sensors in short-range communications, a mobile collector will stop for a short time at some anchor points on its moving path. Because the mobility of the collector can effectively decrease the relay hops of data packet, energy consumption of each sensor node would be greatly reduced. Furthermore, to maximize energy saving, the mobile collector could traverse the transmission range of each sensor node so that each sensing data packet can be transmitted to the mobile collector in one hop. But, because of low speed of the mobile collector and long length of moving path, the latency of WSN may be very long in the process of data gathering, which will not meet the requirement of delay in some time-sensitive applications [16].In fact, the latency of multihop data gathering is much shorter than mobile data gathering. Thus, in the time-sensitive applications, we have to make a trade-off between the energy saving and the data gathering latency. A general way in some papers is to shorten the latency of mobile data gathering by setting local data aggregation nodes (LNs). Specifically, a part of sensor nodes will be selected as the LNs, which can aggregate the local sensing data from its affiliated sensor nodes within a limited hop count. These LNs could temporarily cache the sensing data and upload them to the mobile collector when it arrives [16]. Although the protocols of setting LNs can effectively reduce the latency of mobile data gathering, they do not consider the energy consumption of the whole network which will have an adverse impact on the lifetime of network.The main contributions of this paper can be summarized as follows.(1)
By modeling and analyzing the energy consumption of whole network, we characterize the energy-efficient bounded relay hop mobile data gathering as an optimization problem.
(2)
We propose an efficient algorithm which is energy-efficient and can achieve a longer lifetime of network than these existing mobile data gathering protocols with LNs.
(3)
The performance of the proposed algorithm is evaluated by comparing with other three existing mobile data gathering schemes. Simulation results illustrate that the proposed algorithms achieve distinctive performance.The rest of the paper is organized as follows: Section2 reviews the related work on mobile data gathering. Section 3 models and analyzes the energy consumption of whole network and then formulates the problem. Section 4 gives detailed description on our algorithm and analyzes the performance of it. The performance evaluation is demonstrated in Section 5. Finally, Section 6 concludes the paper.


## 2. Related Work

In this section, let us briefly review some recent work on mobile data gathering in WSNs. The mobile data gathering protocols can be divided into two categories according to the mobility pattern.In the first category the mobility is uncontrollable, and the moving path of the mobile collector is either random or determinate. For example, [17–19]. In [17], Shah et al. proposed a scheme in which a special type of mobile nodes is used as forwarding agents to facilitate connectivity among static sensors and transport data with random mobility. To improve the work in [17], Jain et al. [18] presented an analytical model to understand the key performance metrics of the WSNs with mobile collector, such as data transfer, latency of data gathering, and power consumptions. Jea et al. [19] set some fixed straight moving paths, and the mobile collector gathered sensing data from the nodes near these paths. A common advantage of these protocols is that they can get high stability and reliability, and it is easy for network maintaining. But, they lack agility and cannot apply to highly dynamic environment.The mobility of the second category is controlled, in which mobile collector can freely move to any position of the WSN and its path can be constructed for specific purpose, such as, [20–25]. Furthermore, in this category, the approaches can be classified into three subclasses. In the first subclass, the mobile collector visits each sensor node or traverses the transmission range of each node and gathers sensing data in one hop [20, 21]. To ensure no data loss, Somasundara et al. [20] studied the scheduling of mobile collector. Ma and Yang [21] proposed tour planning algorithm for getting a short moving path and ensuring all data gathering to be completed in one hop, and it can achieve perfect uniformity of energy consumption. Although these protocols can minimize the energy cost by completely avoiding multihop relays, they may make a long latency of data gathering especially in a large-scale WSN. In the second subclass, mobile collector gathers sensing data from the sensor nodes near moving path by multihop transmission. Ma and Yang [22] proposed a moving trajectory planning algorithm via finding some turning points, which is adaptive to the sensor nodes distribution and can effectively avert barriers on the trajectory. In this approach, the sensor nodes along each moving line segment forward packets to the mobile collector by a multihop fashion. For improving routing reliability, Kusy et al. [23] constructed an algorithm by introducing the mobility graph, which can encode the knowledge of likely mobility patterns within the network. We can extract the mobility graph from training data and predict future relay nodes by applying it on the mobile collector to ensure uninterrupted data streams. Luo and Hubaux [24] thought that sensing data should be gathered via multihop relays while the mobile collector moves along the perimeter of the WSN, which is considered as the optimal path for the mobile collector. These protocols could effectively reduce or limit the length of moving path to a certain level. However, they do not set any limitation on the hop count that will make network lifetime (or a certain level of energy efficiency) uncertain. In the third subclass, data transmission patterns and moving path planning are both considered. For example, Zhao et al. [25] constructed a mobile data gathering algorithm by considering the full utilization of concurrent data uploading and the minimization of path length. In the algorithm, multiple sensor nodes can upload sensing data to the mobile collector in one hop at the same time, which effectively reduces the time of data uploading. Zhao and Yang [16] proposed an algorithm called BRH-MDG (bounded relay hop mobile data gathering), in which the length of moving path is minimized and the local data aggregation is guaranteed in bounded-hop count. In this paper, our work falls into the third subclass. Via modeling and analyzing the energy consumption of whole network we construct a new algorithm called energy-efficient bounded relay hop mobile data gathering (EEBRHM), which can achieve much longer network lifetime than others and only increases a little delay compared with the BRH-MDG.


## 3. Preliminaries

### 3.1. Network Model

Assume thatv
1
,
v
2
,
…
,
v
n are sensor nodes in a sensing field and v
0 is the sink. These n nodes are randomly deployed in a M
×
M field and form a WSN. This WSN can be represented by a connective undirected graph G
(
V
,
E
), where V is the set of sensor nodes and E is the set of edges. If the distance between nodes v
i
and v
j is shorter than the maximum communication distance, there is an edge v
i
,
v
j
∈
E. V
=
n
+
1 is the number of sensor nodes, and E
=
m is the number of edges. There are some characteristics in the WSN.(1)
The sensor nodes are stationary after deployment.
(2)
In the process of data gathering, for a relay node, both the received data and its sensing data will be aggregated into a certain length packet. Then the packet will be sent to the next node.
(3)
After deployment the energy of sensor nodes cannot be recharged, and the initial energy of each sensor nodes is the same.
(4)
There has been a time synchronization scheme in the WSN. And the time accuracy can be in milliseconds [26].In general, we can assume that the amount of energy required to transmitting/receiving 1 bit of data is a fixed value. LetE
t denote energy required by transmitting and E
r denote energy required by receiving. At the same time, we assume that there are some excellent congestion control strategies in the WSN, which can avoid congestion and retransmission in the process of data gathering.


### 3.2. Definitions

In the protocols of mobile data gathering with bounded-hop LNs, such as BRH-MDG algorithm, the WSN is divided into some subtrees whose roots are the LNs. Because mobile collector can be recharged, the lifetime of network is determined by the life cycle of subtrees. According to paper [13], we give several definitions which will be used in this paper.Definition 1.
A round is defined as the process of gathering the sensing data from sensor nodes to the sink in one cycle by mobile collector, which could be equal to the time spent at the moving path by mobile collector.Definition 2.
The lifetime of a nodev
i is defined as the number of rounds in the node survival period. We can judge whether one sensor node is survival by a formula E
(
v
i
)
>
e, when the residual energy of one node is lower than it, the node is dead. Specifically, E
(
v
i
) represents the residual energy of one node, and e is a threshold. In this paper, each sensor node can aggregate received data and itself sensing data into a l bits packet. Formula (1) is used to count the lifetime of a node(1)
L
node
v
i
=
E
v
i
l
E
t
-
E
r
+
D
v
i
l
E
r
,where D
(
v
i
) represents the degree of a node in the subtree.Definition 3.
The lifetime of a subtree is the lifetime of the first dead node in the subtree, defined as the following formula:(2)
L
tree
T
N
=
min
⁡
⁡
L
node
v
i
,
v
i
∈
T
N
,where T
N represents one subtree and v
i is a node in the subtree.Definition 4.
The lifetime of the whole network is the shortest lifetime of the subtrees, defined as the following formula:(3)
L
N
G
=
min
⁡
T
N
∈
T
P
L
tree
T
N
,where T
N represents one subtree andTPis the set of subtrees.


### 3.3. Problem Statement

As shown above, the subtrees with the shortest lifetime determine the lifetime of the whole network. Thus, if we want to optimize the energy consumption of the whole network, we should maximize the lifetime of all subtrees.In Formula (1), l, E
r, and E
t are constant, and E
(
v
i
) is initialized as a constant. Only D
(
v
i
) is a variable, so it is the main optimization objective. To extract the constant E
r, E
t from the denominator and use Formula (1) to substitute L
node
(
V
i
) in formula (2), formula (2) can be transformed into an equivalent form:(4)
L
tree
T
N
=
min
⁡
E
v
i
D
v
i
+
c
,
v
i
∈
T
N
,where c
=
(
E
t
-
E
r
)
/
E
r. Based on formulas (3) and (4), the maximum lifetime of the whole network can be calculated by the following formula:(5)
max
⁡
L
N
G
=
max
⁡
min
⁡
T
N
∈
T
P
E
v
i
D
v
i
+
c
,
v
i
∈
T
N
.In formula (5), to maximize the lifetime of subtrees, D
(
v
i
) of each node of subtrees should be minimized. The problem of how to obtain a spanning tree with minimum node degree on the premise of hop bounded has been proved to be NP-hard in [13].


## 3.1. Network Model

Assume thatv
1
,
v
2
,
…
,
v
n are sensor nodes in a sensing field and v
0 is the sink. These n nodes are randomly deployed in a M
×
M field and form a WSN. This WSN can be represented by a connective undirected graph G
(
V
,
E
), where V is the set of sensor nodes and E is the set of edges. If the distance between nodes v
i
and v
j is shorter than the maximum communication distance, there is an edge v
i
,
v
j
∈
E. V
=
n
+
1 is the number of sensor nodes, and E
=
m is the number of edges. There are some characteristics in the WSN.(1)
The sensor nodes are stationary after deployment.
(2)
In the process of data gathering, for a relay node, both the received data and its sensing data will be aggregated into a certain length packet. Then the packet will be sent to the next node.
(3)
After deployment the energy of sensor nodes cannot be recharged, and the initial energy of each sensor nodes is the same.
(4)
There has been a time synchronization scheme in the WSN. And the time accuracy can be in milliseconds [26].In general, we can assume that the amount of energy required to transmitting/receiving 1 bit of data is a fixed value. LetE
t denote energy required by transmitting and E
r denote energy required by receiving. At the same time, we assume that there are some excellent congestion control strategies in the WSN, which can avoid congestion and retransmission in the process of data gathering.


## 3.2. Definitions

In the protocols of mobile data gathering with bounded-hop LNs, such as BRH-MDG algorithm, the WSN is divided into some subtrees whose roots are the LNs. Because mobile collector can be recharged, the lifetime of network is determined by the life cycle of subtrees. According to paper [13], we give several definitions which will be used in this paper.Definition 1.
A round is defined as the process of gathering the sensing data from sensor nodes to the sink in one cycle by mobile collector, which could be equal to the time spent at the moving path by mobile collector.Definition 2.
The lifetime of a nodev
i is defined as the number of rounds in the node survival period. We can judge whether one sensor node is survival by a formula E
(
v
i
)
>
e, when the residual energy of one node is lower than it, the node is dead. Specifically, E
(
v
i
) represents the residual energy of one node, and e is a threshold. In this paper, each sensor node can aggregate received data and itself sensing data into a l bits packet. Formula (1) is used to count the lifetime of a node(1)
L
node
v
i
=
E
v
i
l
E
t
-
E
r
+
D
v
i
l
E
r
,where D
(
v
i
) represents the degree of a node in the subtree.Definition 3.
The lifetime of a subtree is the lifetime of the first dead node in the subtree, defined as the following formula:(2)
L
tree
T
N
=
min
⁡
⁡
L
node
v
i
,
v
i
∈
T
N
,where T
N represents one subtree and v
i is a node in the subtree.Definition 4.
The lifetime of the whole network is the shortest lifetime of the subtrees, defined as the following formula:(3)
L
N
G
=
min
⁡
T
N
∈
T
P
L
tree
T
N
,where T
N represents one subtree andTPis the set of subtrees.


## 3.3. Problem Statement

As shown above, the subtrees with the shortest lifetime determine the lifetime of the whole network. Thus, if we want to optimize the energy consumption of the whole network, we should maximize the lifetime of all subtrees.In Formula (1), l, E
r, and E
t are constant, and E
(
v
i
) is initialized as a constant. Only D
(
v
i
) is a variable, so it is the main optimization objective. To extract the constant E
r, E
t from the denominator and use Formula (1) to substitute L
node
(
V
i
) in formula (2), formula (2) can be transformed into an equivalent form:(4)
L
tree
T
N
=
min
⁡
E
v
i
D
v
i
+
c
,
v
i
∈
T
N
,where c
=
(
E
t
-
E
r
)
/
E
r. Based on formulas (3) and (4), the maximum lifetime of the whole network can be calculated by the following formula:(5)
max
⁡
L
N
G
=
max
⁡
min
⁡
T
N
∈
T
P
E
v
i
D
v
i
+
c
,
v
i
∈
T
N
.In formula (5), to maximize the lifetime of subtrees, D
(
v
i
) of each node of subtrees should be minimized. The problem of how to obtain a spanning tree with minimum node degree on the premise of hop bounded has been proved to be NP-hard in [13].


## 4. Design of EEBRHM

### 4.1. Algorithm Description

Base on formula (5), our problem of maximizing the lifetime of subtrees can be transformed to minimize the degree of each node of subtrees. To solve this problem, a general idea is to balance degrees of nodes in subtrees, such as BRH-MDG algorithm. As shown in Figure 1(a), the BRH-MDG algorithm divides the network into three subtrees. Since the process of generating subtrees is random, the distribution of nodes’ degrees is not uniform. In Figure 1(a), the dotted lines represent the moving path, the black nodes represent the nodes which have maximum degrees in subtrees, and the maximum degree among these black nodes is 5. By applying a method to balance the degrees of nodes in Figure 1(a), a new set of subtrees can be obtained as shown in Figure 1(b) and the maximum degree is reduced to 2. According to Definitions 3 and 4, the lifetime of network in Figure 1(b) is twice more than that in Figure 1(a).Figure 1
An example to show the effect of balancing the degree of each node.
(a)
An example of BRH-MDG algorithm
(b)
After balancing the degree of each nodeThe example demonstrates that the key point to optimize the energy consumption of the whole WSN is to balance the distribution of nodes’ degree in their own subtrees. In this paper, we propose a new algorithm called EEBRHM which uses the number of children of nodes in the initial tree as control metric to adjust the degree of each node. The detail of EEBRHM algorithm is shown in Algorithm1 and Table 1.Table 1
Notations used in EEBRHM algorithm.
Functions
H
(
v
)
This function returns the height ofv in its own SPT.
Parent
(
v
)
This function returns the parent node ofv.
CN
(
v
)
This function returns the number of children nodes ofv.
Nb
(
v
)
This function returns a set of neighbor nodes ofv.
Variables
cn
The variable is used to cache the number of children of nodev.
v
t
The variable is used to cache the nodev which is relevant to cn.Algorithm 1:EEBRHM algorithm.
Algorithm EEBRHM
Input: Network topology G
(
V
,
E
), the relay hop bound d,
and the static data sink v
0.
Output: A set of LNs, a set of sub-trees and the tour U
visiting the LNs and the data sink.
(1)   Construct SPTs forG that cover all the vertices in V
(2)   for each nodev do {
(3)      ifH
(
v
)
⩾ 2 {
(4)cn = CN
(
Parent
(
v
)
); v
t = v;
(5)        for each nodev
′ in Nb
(
v
) {
(6)           ifH
(
v
′
) − H
(
v
) == −1 {
(7)                ifCN
(
v
′
) < c
n  {
(8) cn = CN
(
v
′
); v
t = v
′;
(9)                }
(10)         }
(11)        }
(12)        ifcn + 2 < CN
(
Parent
(
v
)
)  {
(13)          Parent(
v
)  ⩽  vt;
(14)          Broadcast ACK Message;
(15)          When received the ACK Message,
the related nodes will make response;
(16)        }
(17)    }
(18) }
(19) Set three large time slotsT
0, T
1, T
2, T
0
<
T
1
<
T
2,
and set a constantt
′, t
′  ≪  T
0;
(20) for each nodev do {
(21)    Get the unique integer ID ofv;
(22)    ifv in one hop of v
0  {
(23)     Allocate a delay time slot (T
0 + ID∗
t
′) to v;
(24)    }
(25)    ifv is out of one hop of v
0 but it is in two hop {
(26)     Allocate a delay time slot (T
1 + ID∗
t
′) to v;
(27)    }
(28)    ifv is out of two hop of v
0  {
(29)     Allocate a delay time slot (T
2 + ID∗
t
′) to v;
(30)    }
(31) }
(32) In the delay time slot of each nodev  {
(33)    ifv is not belong to a LN {
(34)      Let it be a LN and broadcast a probe packet
with d hops of time to live;
(35)    }
(36)    if other nodes received the probe packet {
(37)       if it is not a LN {
(38)          if it is the child of relay node {
(39)            Let it be an affiliated node of the source
node of the probe packet;
(40)            }
(41)         }
(42)    }
(43) }
(44) Use the TSP algorithm to find an approximate shortest
tour U visiting v
0 and all the LNs.First of all, EEBRHM algorithm will construct shortest path trees (SPTs) which should cover all sensor nodes with minimum hops in the WSN (see Algorithm1, line (1)). Because a large WSN may not be fully connected, it may be constituted by several subnetworks and thus it needs more than one SPT to cover all sensor nodes. In EEBRHM algorithm, generally, the root of SPT is the data sink. For the nodes from other subnetworks, which are far from the data sink, we can set virtual roots in the center of the subnetworks. Thus, the new algorithm can be applied to not only connected WSNs, but also disconnected WSNs, which is one of the main advantages for the mobile data gathering. Moreover, before all sensor nodes being deployed, each node will be assigned a unique integer ID which will be used to allocate separate delay time slot for each sensor node. Then, EEBRHM will use the number of sensor nodes’ children as metric to balance the degrees of sensor nodes (see Algorithm 1, lines (2)–(18)). Specifically, the energy of root is assumed to be infinite; so its degree does not need to be balanced. For a sensor node, if its parent node is not root and there exists a neighbor node with the minimum number of children and at the same height as its parent in its own SPT (to effectively balance, the minimum number of children must be less than original value at least 2), this neighbor node will be the new parent of the node. After updating the new parent, the old parent and the new parent node will renew the numbers of children and inform all their own neighbor nodes.The next task of EEBRHM is to determine the LNs. Since the LNs are more close to the data sink and the length of moving pathU is shorter than other sensor nodes, the sensor nodes which is more close to the data sink will more likely to be LNs. To determine LNs, firstly, all sensor nodes are assigned to one of three separate large time slots according to the distance between sensor nodes and the data sink. The formula T
n
+
ID
∗
t
′
n
=
0
,
1
,
2 ensures that each node will be assigned to a separate small time slot, so that the sensor nodes will not interfere with each other in the process of algorithm. Moreover, T
n is measured in seconds and t
′ is measured in milliseconds. A node, which is more close to the data sink, will be assigned to an earlier large time slot and would have priority to be a LN. At last, TSP algorithm is used to construct an approximate shortest tour U visiting v
0 and all the LNs.


### 4.2. Performance Analysis

To evaluate the performance of EEBRHM, firstly, we will analyze the time complexity of EEBRHM. Assume a WSN hasK disconnected subnetworks and N is the total number of sensor nodes in the WSN (
1
⩽
K
⩽
N
). For a subnetwork k (k
=
1,2
,
…
,
K), it would take O
(
(
N
k
)
2
) time to find a SPT [27], where N
k represents the number of sensor nodes in subnetwork k. In our algorithm, it runs in O
(
N
) time to balance the nodes’ degree and construct LNs. And it runs in O
N
2 time to find tour U at most by using TSP algorithm [28]. Thus, the total time complexity of EEBRHM is O
(
N
k
2
)
+
O
N
+
O
N
2
. In the worst case, the time complexity of EEBRHM is O
(
N
2
).Due to balancing degree of sensor nodes, the length of moving pathU of EEBRHM may be longer than BRH-MDG algorithm, which will increase a bit latency of network by EEBRHM. But the performance of network lifetime of EEBRHM is much better than BRH-MDG.EEBRHM is also one of mobile data gathering algorithms and the data transmission between nodes and mobile sink is the main part of communication overhead. The mechanism of constructing the path of mobile sink of EEBRHM is the same as BRH-MDG. Thus, the communication cost of EEBRHM is just the same as BRH-MDG.


## 4.1. Algorithm Description

Base on formula (5), our problem of maximizing the lifetime of subtrees can be transformed to minimize the degree of each node of subtrees. To solve this problem, a general idea is to balance degrees of nodes in subtrees, such as BRH-MDG algorithm. As shown in Figure 1(a), the BRH-MDG algorithm divides the network into three subtrees. Since the process of generating subtrees is random, the distribution of nodes’ degrees is not uniform. In Figure 1(a), the dotted lines represent the moving path, the black nodes represent the nodes which have maximum degrees in subtrees, and the maximum degree among these black nodes is 5. By applying a method to balance the degrees of nodes in Figure 1(a), a new set of subtrees can be obtained as shown in Figure 1(b) and the maximum degree is reduced to 2. According to Definitions 3 and 4, the lifetime of network in Figure 1(b) is twice more than that in Figure 1(a).Figure 1
An example to show the effect of balancing the degree of each node.
(a)
An example of BRH-MDG algorithm
(b)
After balancing the degree of each nodeThe example demonstrates that the key point to optimize the energy consumption of the whole WSN is to balance the distribution of nodes’ degree in their own subtrees. In this paper, we propose a new algorithm called EEBRHM which uses the number of children of nodes in the initial tree as control metric to adjust the degree of each node. The detail of EEBRHM algorithm is shown in Algorithm1 and Table 1.Table 1
Notations used in EEBRHM algorithm.
Functions
H
(
v
)
This function returns the height ofv in its own SPT.
Parent
(
v
)
This function returns the parent node ofv.
CN
(
v
)
This function returns the number of children nodes ofv.
Nb
(
v
)
This function returns a set of neighbor nodes ofv.
Variables
cn
The variable is used to cache the number of children of nodev.
v
t
The variable is used to cache the nodev which is relevant to cn.Algorithm 1:EEBRHM algorithm.
Algorithm EEBRHM
Input: Network topology G
(
V
,
E
), the relay hop bound d,
and the static data sink v
0.
Output: A set of LNs, a set of sub-trees and the tour U
visiting the LNs and the data sink.
(1)   Construct SPTs forG that cover all the vertices in V
(2)   for each nodev do {
(3)      ifH
(
v
)
⩾ 2 {
(4)cn = CN
(
Parent
(
v
)
); v
t = v;
(5)        for each nodev
′ in Nb
(
v
) {
(6)           ifH
(
v
′
) − H
(
v
) == −1 {
(7)                ifCN
(
v
′
) < c
n  {
(8) cn = CN
(
v
′
); v
t = v
′;
(9)                }
(10)         }
(11)        }
(12)        ifcn + 2 < CN
(
Parent
(
v
)
)  {
(13)          Parent(
v
)  ⩽  vt;
(14)          Broadcast ACK Message;
(15)          When received the ACK Message,
the related nodes will make response;
(16)        }
(17)    }
(18) }
(19) Set three large time slotsT
0, T
1, T
2, T
0
<
T
1
<
T
2,
and set a constantt
′, t
′  ≪  T
0;
(20) for each nodev do {
(21)    Get the unique integer ID ofv;
(22)    ifv in one hop of v
0  {
(23)     Allocate a delay time slot (T
0 + ID∗
t
′) to v;
(24)    }
(25)    ifv is out of one hop of v
0 but it is in two hop {
(26)     Allocate a delay time slot (T
1 + ID∗
t
′) to v;
(27)    }
(28)    ifv is out of two hop of v
0  {
(29)     Allocate a delay time slot (T
2 + ID∗
t
′) to v;
(30)    }
(31) }
(32) In the delay time slot of each nodev  {
(33)    ifv is not belong to a LN {
(34)      Let it be a LN and broadcast a probe packet
with d hops of time to live;
(35)    }
(36)    if other nodes received the probe packet {
(37)       if it is not a LN {
(38)          if it is the child of relay node {
(39)            Let it be an affiliated node of the source
node of the probe packet;
(40)            }
(41)         }
(42)    }
(43) }
(44) Use the TSP algorithm to find an approximate shortest
tour U visiting v
0 and all the LNs.First of all, EEBRHM algorithm will construct shortest path trees (SPTs) which should cover all sensor nodes with minimum hops in the WSN (see Algorithm1, line (1)). Because a large WSN may not be fully connected, it may be constituted by several subnetworks and thus it needs more than one SPT to cover all sensor nodes. In EEBRHM algorithm, generally, the root of SPT is the data sink. For the nodes from other subnetworks, which are far from the data sink, we can set virtual roots in the center of the subnetworks. Thus, the new algorithm can be applied to not only connected WSNs, but also disconnected WSNs, which is one of the main advantages for the mobile data gathering. Moreover, before all sensor nodes being deployed, each node will be assigned a unique integer ID which will be used to allocate separate delay time slot for each sensor node. Then, EEBRHM will use the number of sensor nodes’ children as metric to balance the degrees of sensor nodes (see Algorithm 1, lines (2)–(18)). Specifically, the energy of root is assumed to be infinite; so its degree does not need to be balanced. For a sensor node, if its parent node is not root and there exists a neighbor node with the minimum number of children and at the same height as its parent in its own SPT (to effectively balance, the minimum number of children must be less than original value at least 2), this neighbor node will be the new parent of the node. After updating the new parent, the old parent and the new parent node will renew the numbers of children and inform all their own neighbor nodes.The next task of EEBRHM is to determine the LNs. Since the LNs are more close to the data sink and the length of moving pathU is shorter than other sensor nodes, the sensor nodes which is more close to the data sink will more likely to be LNs. To determine LNs, firstly, all sensor nodes are assigned to one of three separate large time slots according to the distance between sensor nodes and the data sink. The formula T
n
+
ID
∗
t
′
n
=
0
,
1
,
2 ensures that each node will be assigned to a separate small time slot, so that the sensor nodes will not interfere with each other in the process of algorithm. Moreover, T
n is measured in seconds and t
′ is measured in milliseconds. A node, which is more close to the data sink, will be assigned to an earlier large time slot and would have priority to be a LN. At last, TSP algorithm is used to construct an approximate shortest tour U visiting v
0 and all the LNs.


## 4.2. Performance Analysis

To evaluate the performance of EEBRHM, firstly, we will analyze the time complexity of EEBRHM. Assume a WSN hasK disconnected subnetworks and N is the total number of sensor nodes in the WSN (
1
⩽
K
⩽
N
). For a subnetwork k (k
=
1,2
,
…
,
K), it would take O
(
(
N
k
)
2
) time to find a SPT [27], where N
k represents the number of sensor nodes in subnetwork k. In our algorithm, it runs in O
(
N
) time to balance the nodes’ degree and construct LNs. And it runs in O
N
2 time to find tour U at most by using TSP algorithm [28]. Thus, the total time complexity of EEBRHM is O
(
N
k
2
)
+
O
N
+
O
N
2
. In the worst case, the time complexity of EEBRHM is O
(
N
2
).Due to balancing degree of sensor nodes, the length of moving pathU of EEBRHM may be longer than BRH-MDG algorithm, which will increase a bit latency of network by EEBRHM. But the performance of network lifetime of EEBRHM is much better than BRH-MDG.EEBRHM is also one of mobile data gathering algorithms and the data transmission between nodes and mobile sink is the main part of communication overhead. The mechanism of constructing the path of mobile sink of EEBRHM is the same as BRH-MDG. Thus, the communication cost of EEBRHM is just the same as BRH-MDG.


## 5. Simulation Results

In the simulation, we assume thatN sensor nodes are randomly distributed over an M
×
M square area and the data sink is set in the center of the area. Furthermore, we compare our algorithm with BRH-MDG [16], SHDG [21], and CME [19]. SHDG is one kind of one hop mobile data gathering scheme. This algorithm will choose some pausing locations for mobile collector from a set of candidate locations, so that mobile collector can gather sensor data from nodes in a single hop. Although we can use TSP algorithm to construct an approximate shortest tour U for mobile collector to visit all pausing locations and the data sink, the latency of network of SHDG is too long. CME generates some parallel straight tours in advance which across the WSN. Then, the mobile collector will traverse along these tours while gathering data from the sensor nodes nearby the tours. And the other sensor nodes would send their own sensor data to the nodes nearby tours by multihop relays. The latency of network of CME is acceptable, but due to randomly choosing a relay node, the network lifetime achieved by CME may be poor. The description of BRH-MDG has been mentioned in Section 3.1. All simulations are performed 30 times and average values of their results are taken as final results.


### 5.1. The Impact of Sensor Node Density

To compare the performance of different algorithms, we change the density of sensor nodes. The simulation setting in the experiments is that communication radiusR, bounded-hop d and the area are set as 30 m, 2 and 200
∗
200 m2, respectively. Figure 2(a) plots the performance of EEBRHM and BRH-MDG as a function of density of sensor nodes, in terms of network lifetime. From Figure 2(a), we can find that when the number of sensor nodes becomes larger, the advantage of EEBRHM over BRH-MDG become more obvious. The performance of network lifetime of EEBRHM is 4.7 times than BRH-MDG on average. There are two reasons to explain this. First, the degrees of sensor nodes in BRH-MDG are very uneven which leads to uneven node energy consumption and therefore make the network lifetime short. Our EEBRHM algorithm can balance the degree of each node; thus its performance of network lifetime is much better than BRH-MDG. The second reason is that since BRH-MDG does not balance the degree of each node, when the density of sensor nodes becomes larger, the degree of nodes in the WSN may increase very quickly; therefore the network lifetime of BRH-MDG would become shorter and shorter.Figure 2
Performance comparison with changing the density of sensor nodes.
(a)
Network lifetime comparison
(b)
Length of tour comparisonFigure2(b) shows the performance of four algorithms as a function of density of sensor nodes, in terms of tour length. The simulation setting is the same as above. For SHDG, BRH-MDG, and EEBRHM, TSP algorithm is used to generate an approximate shortest tour and mobile collector will move along it. For CME, the parallel straight tours traversing the sensor field are 100 m apart from each other. One of these tours must go through the center of the field. The mobile collector can change onto other tours by moving along the sensor field border. Both SHDG and CME algorithms are implemented in a centralized fashion. BRH-MDG and EEBRHM are implemented in a distributed fashion. In Figure 2(b), it is easy to observe that the tour length of BRH-MDG and EEBRHM gradually increases at first and then stabilizes when the density of nodes becomes sufficiently large. The reason is that when sensor nodes become more densely dispersed, they will have higher probability to be affiliated with a LN which is close to the data sink. EEBRHM will generate more LNs than BRH-MDG by balancing the degree of each node, which makes the average tour length of EEBRHM longer than BRH-MDG. In contrast, the average tour length of SHDG is longer than BRH-MDG and EEBRHM. Because SHDG must visit one hop range of each node, its pausing locations of mobile collector will become much more than BRH-MDG and EEBRHM with the continuously increased density. Since the mobile collector goes along the fixed tours in the sensor field, the tour length of CME is a constant which in general is bigger than the average tour length of BRH-MDG and EEBRHM.


### 5.2. The Impact of Communication Radius

To evaluate the performance of different algorithms with changing the communication radius, the comparison is shown in Figure3. The simulation setting of the experiments is that the number of nodes N and the area are fixed at 400 and 200
∗
200 m2, respectively. And the bounded-hop d is set as 2 and 3, respectively. Figure 3(a) illustrates the performance of EEBRHM and BRH-MDG as a function of communication radius R, in terms of network lifetime. As shown in Figure 3(a), the network lifetime of EEBRHM quit outperforms that of BRH-MDG with d
=
2 or 3, and it becomes more obvious when R increases. When R is 60 m, the network lifetime of EEBRHM is 10 times longer than that of BRH-MDG. The reason has been explained in Section 5.1.Figure 3
Performance comparison with changing the boundedd
.
(a)
Network lifetime comparison
(b)
Length of tour comparisonIn Figure3(b), the performance of EEBRHM and BRH-MDG as a function of communication radius R, in terms of tour length, is compared. From Figure 3(b), we can know that the tour length of EEBRHM and BRH-MDG first gradually reduces as R increases and then stabilizes when R becomes sufficiently long. For the same reason as above, the average tour length of EEBRHM in this case is longer than BRH-MDG. Furthermore, for BRH-MDG, as d increases the LNs can own more subordinate nodes which will make the average tour length of BRH-MDG became shorter. When the R is 60 m and d is 2, the tour length of BRH-MDG is near 0.


## 5.1. The Impact of Sensor Node Density

To compare the performance of different algorithms, we change the density of sensor nodes. The simulation setting in the experiments is that communication radiusR, bounded-hop d and the area are set as 30 m, 2 and 200
∗
200 m2, respectively. Figure 2(a) plots the performance of EEBRHM and BRH-MDG as a function of density of sensor nodes, in terms of network lifetime. From Figure 2(a), we can find that when the number of sensor nodes becomes larger, the advantage of EEBRHM over BRH-MDG become more obvious. The performance of network lifetime of EEBRHM is 4.7 times than BRH-MDG on average. There are two reasons to explain this. First, the degrees of sensor nodes in BRH-MDG are very uneven which leads to uneven node energy consumption and therefore make the network lifetime short. Our EEBRHM algorithm can balance the degree of each node; thus its performance of network lifetime is much better than BRH-MDG. The second reason is that since BRH-MDG does not balance the degree of each node, when the density of sensor nodes becomes larger, the degree of nodes in the WSN may increase very quickly; therefore the network lifetime of BRH-MDG would become shorter and shorter.Figure 2
Performance comparison with changing the density of sensor nodes.
(a)
Network lifetime comparison
(b)
Length of tour comparisonFigure2(b) shows the performance of four algorithms as a function of density of sensor nodes, in terms of tour length. The simulation setting is the same as above. For SHDG, BRH-MDG, and EEBRHM, TSP algorithm is used to generate an approximate shortest tour and mobile collector will move along it. For CME, the parallel straight tours traversing the sensor field are 100 m apart from each other. One of these tours must go through the center of the field. The mobile collector can change onto other tours by moving along the sensor field border. Both SHDG and CME algorithms are implemented in a centralized fashion. BRH-MDG and EEBRHM are implemented in a distributed fashion. In Figure 2(b), it is easy to observe that the tour length of BRH-MDG and EEBRHM gradually increases at first and then stabilizes when the density of nodes becomes sufficiently large. The reason is that when sensor nodes become more densely dispersed, they will have higher probability to be affiliated with a LN which is close to the data sink. EEBRHM will generate more LNs than BRH-MDG by balancing the degree of each node, which makes the average tour length of EEBRHM longer than BRH-MDG. In contrast, the average tour length of SHDG is longer than BRH-MDG and EEBRHM. Because SHDG must visit one hop range of each node, its pausing locations of mobile collector will become much more than BRH-MDG and EEBRHM with the continuously increased density. Since the mobile collector goes along the fixed tours in the sensor field, the tour length of CME is a constant which in general is bigger than the average tour length of BRH-MDG and EEBRHM.


## 5.2. The Impact of Communication Radius

To evaluate the performance of different algorithms with changing the communication radius, the comparison is shown in Figure3. The simulation setting of the experiments is that the number of nodes N and the area are fixed at 400 and 200
∗
200 m2, respectively. And the bounded-hop d is set as 2 and 3, respectively. Figure 3(a) illustrates the performance of EEBRHM and BRH-MDG as a function of communication radius R, in terms of network lifetime. As shown in Figure 3(a), the network lifetime of EEBRHM quit outperforms that of BRH-MDG with d
=
2 or 3, and it becomes more obvious when R increases. When R is 60 m, the network lifetime of EEBRHM is 10 times longer than that of BRH-MDG. The reason has been explained in Section 5.1.Figure 3
Performance comparison with changing the boundedd
.
(a)
Network lifetime comparison
(b)
Length of tour comparisonIn Figure3(b), the performance of EEBRHM and BRH-MDG as a function of communication radius R, in terms of tour length, is compared. From Figure 3(b), we can know that the tour length of EEBRHM and BRH-MDG first gradually reduces as R increases and then stabilizes when R becomes sufficiently long. For the same reason as above, the average tour length of EEBRHM in this case is longer than BRH-MDG. Furthermore, for BRH-MDG, as d increases the LNs can own more subordinate nodes which will make the average tour length of BRH-MDG became shorter. When the R is 60 m and d is 2, the tour length of BRH-MDG is near 0.


## 6. Conclusion

In this paper, we have studied the energy consumption model of the WSN with mobile data gathering with bounded-hop LNs. A new novel algorithm EEBRHM is proposed to optimize the network lifetime of WSN. Extensive simulations have been carried out to prove the efficiency of the protocol. The results demonstrate that the proposed algorithm can greatly prolong the network lifetime of the WSN with bounded relay hop and obtain about 7.3 times improvement on the network lifetime compared with BRH-MDG. Moreover, the tour length of EEBRHM is shorter than SHDG and CME and is only longer than BRH-MDG by 35%.



---

*Source: 680301-2015-05-14.xml*