Sage Journals: Discover world-class research

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%.

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: Section 2 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 that $v_{1}, v_{2}, \dots, v_{n}$ are sensor nodes in a sensing field and $v_{0}$ is the sink. These n nodes are randomly deployed in a $M \times 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}) \in 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. Let $E_{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 node $v_{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

\begin{matrix} L_{node} (v_{i}) = ⌊\frac{E (v_{i})}{l (E_{t} - E_{r}) + D (v_{i}) l E_{r}}⌋, \end{matrix}

(1)

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:

\begin{matrix} L_{tree} (T_{N}) = \min \{L_{node} (v_{i})\}, v_{i} \in T_{N}, \end{matrix}

(2)

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:

\begin{matrix} L_{N} (G) = \min_{T_{N} \in T P} \{L_{tree} (T_{N})\}, \end{matrix}

(3)

where

T_{N}

represents one subtree and TP is 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:

\begin{matrix} L_{tree} (T_{N}) = \min_{} \{⌊\frac{E (v_{i})}{D (v_{i}) + c}⌋, v_{i} \in T_{N}\}, \end{matrix}

(4)

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:

\begin{matrix} \max L_{N} (G) = \max \min_{T_{N} \in T P} \{⌊\frac{E (v_{i})}{D (v_{i}) + c}⌋, v_{i} \in T_{N}\} . \end{matrix}

(5)

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.

The 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 Algorithm 1 and Table 1.

Table 1

Notations used in EEBRHM algorithm.

Functions
$H (v)$	This function returns the height of v in its own SPT.
$Parent (v)$	This function returns the parent node of v.
$CN (v)$	This function returns the number of children nodes of v.
$Nb (v)$	This function returns a set of neighbor nodes of v.
Variables
$cn$	The variable is used to cache the number of children of node v.
$v t$	The variable is used to cache the node v 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 for G that cover all the vertices in V

(2) for each node v do {

(3) if $H (v)$ ⩾ 2 {

(4) $cn$ = $CN (Parent (v))$ ; $v t$ = v;

(5) for each node $v^{'}$ in $Nb (v)$ {

(6) if $H (v^{'})$ − $H (v)$ == −1 {

(7) if $CN (v^{'})$ < $c n$ {

(8) $cn$ = $CN (v^{'})$ ; $v t$ = $v^{'}$ ;

(9) }

(10) }

(11) }

(12) if $cn$ + 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 slots $T_{0}$ , $T_{1}$ , $T_{2}$ , $T_{0} < T_{1} < T_{2}$ ,

and set a constant $t^{'}$ , $t^{'}$ ≪ $T_{0}$ ;

(20) for each node v do {

(21) Get the unique integer ID of v;

(22) if v in one hop of $v_{0}$ {

(23) Allocate a delay time slot ( $T_{0}$ + ID $* t^{'}$ ) to v;

(24) }

(25) if v 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) if v 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 node v {

(33) if v 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 Algorithm 1, 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 path U 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 has K disconnected subnetworks and N is the total number of sensor nodes in the WSN $(1 ⩽ K ⩽ N)$ . For a subnetwork k ( $k = 1,2, \dots, 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 path U 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 that N sensor nodes are randomly distributed over an $M \times 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 radius R, bounded-hop d and the area are set as 30 m, 2 and $200 * 200$ m², 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.

Figure 2(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 Figure 3. The simulation setting of the experiments is that the number of nodes N and the area are fixed at 400 and $200 * 200$ m², 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 bounded d.

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

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

This work is sponsored by the National Natural Science Foundation of China under Grant nos. 61173169 and 61103203 and the State Key Program of National Natural Science of China under Grant no. 61232001/F02.

References

Rezaei

Mobininejad

Energy saving in wireless sensor networks

International Journal of Computer Science & Engineering Survey 2012 3 1 23 37

Heinzelman

W. R.

Chandrakasan

Balakrishnan

Energy-efficient communication protocol for wireless microsensor networks

Proceedings of the 33rd Annual Hawaii International Conference on System Siences (HICSS '33)

January 2000

Washington, DC, USA

IEEE Computer Society

3005 3014

2-s2.0-0033877788

Younis

Fahmy

HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks

IEEE Transactions on Mobile Computing 2004 3 4 366 379

10.1109/TMC.2004.41

2-s2.0-10944266504

Kui

X. Y.

Sheng

H. K.

Liang

J. B.

Constructing a CDS-based network backbone for data collection in wireless sensor networks

International Journal of Distributed Sensor Networks 2013 2013 12

258081

10.1155/2013/258081

Gao

Wang

A virtual-ring-based data storage and retrieval scheme in wireless sensor networks

International Journal of Distributed Sensor Networks 2012 2012 10

763015

10.1155/2012/763015

Lindsey

Raghavendra

C. S.

PEGASIS: power-efficient gathering in sensor information systems

Proceedings of the IEEE Aerospace Conference

March 2002

San Francisco, Calif, USA

1125 1130 IEEE Computer Society

10.1109/AERO.2002.1035242

2-s2.0-51949089156

Jung

S.-M.

Han

Y.-J.

Chung

T.-M.

The concentric clustering scheme for efficient energy consumption in the PEGASIS

Proceedings of the 9th International Conference on Advanced Communication Technology (ICACT '07)

February 2007

Phoenix Park

IEEE Computer Society

260 265

10.1109/ICACT.2007.358351

2-s2.0-34347223651

Wang

G. J.

Wang

Jia

W. J.

Guo

M. Y.

Adaptive location updates for mobile sinks in wireless sensor networks

Journal of Supercomputing 2009 47 2 127 145

10.1007/s11227-008-0181-5

2-s2.0-59449098459

Zhang

Xie

Z.-P.

Ling

Sun

W.-W.

Shi

B.-L.

Maximum lifetime data gathering algorithm for wireless sensor networks

Journal of Software 2005 16 11 1946 1957

10.1360/jos161946

2-s2.0-33644946980

10.

Liang

Liu

Online data gathering for maximizing network lifetime in sensor networks

IEEE Transactions on Mobile Computing 2007 6 1 2 11

10.1109/TMC.2007.250667

2-s2.0-33845622861

11.

Liao

Z. F.

Wang

J. X.

Zhang

S. G.

Cao

J. N.

Min

G. Y.

Minimizing movement for target coverage and network connectivity in mobile sensor networks

IEEE Transactions on Parallel and Distributed Systems 2014

10.1109/TPDS.2014.2333011

12.

Fahmy

Shroff

N. B.

On the construction of a maximum-lifetime data gathering tree in sensor networks: NP-completeness and approximation algorithm

Proceedings of the 27th IEEE Communications Society Conference on Computer Communications (INFOCOM '08)

April 2008

Phoenix, Ariz, USA

356 360 IEEE Computer Society

10.1109/INFOCOM.2007.80

2-s2.0-51349108846

13.

Liang

J.-B.

Wang

J.-X.

Chen

J.-E.

On the construction of a delay-constrained maximum lifetime tree in wireless sensor networks

Acta Electronica Sinica 2010 38 2 345 351

2-s2.0-77950349137

14.

Karenos

Kalogeraki

Traffic management in sensor networks with a mobile sink

IEEE Transactions on Parallel and Distributed Systems 2010 21 10 1515 1530

10.1109/TPDS.2009.172

2-s2.0-77956176985

15.

Luo

Zhang

Delay tolerant event collection in sensor networks with mobile sink

Proceedings of the IEEE INFOCOM

March 2010

10.1109/INFCOM.2010.5462075

2-s2.0-77953297684

16.

Zhao

Yang

Bounded relay hop mobile data gathering in wireless sensor networks

IEEE Transactions on Computers 2012 61 2 265 277

10.1109/TC.2010.219

MR2931787

2-s2.0-84855458870

17.

Shah

R. C.

Roy

Jain

Brunette

Data MULEs: modeling and analysis of a three-tier architecture for sparse sensor networks

Ad Hoc Networks 2003 1 2-3 215 233

10.1016/S1570-8705(03)00003-9

2-s2.0-3242765057

18.

Jain

Shah

R. C.

Brunette

Borriello

Roy

Exploiting mobility for energy efficient data collection in wireless sensor networks

Mobile Networks and Applications 2006 11 3 327 339

10.1007/s11036-006-5186-9

2-s2.0-33646575292

19.

Jea

Somasundara

Srivastava

Multiple controlled mobile elements (data mules) for data collection in sensor networks

Proceedings of the 1st IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS '05)

July 2005

244 257

2-s2.0-26444530098

20.

Somasundara

A. A.

Ramamoorthy

Srivastava

M. B.

Mobile element scheduling with dynamic deadlines

IEEE Transactions on Mobile Computing 2007 6 4 395 410

10.1109/TMC.2007.57

2-s2.0-33847756370

21.

Yang

Data gathering in wireless sensor networks with mobile collectors

Proceedings of the 22nd IEEE International Parallel and Distributed Processing Symposium (IPDPS '08)

April 2008

10.1109/IPDPS.2008.4536269

2-s2.0-51049112060

22.

Yang

SenCar: an energy-efficient data gathering mechanism for large-scale multihop sensor networks

IEEE Transactions on Parallel and Distributed Systems 2007 18 10 1476 1488

10.1109/TPDS.2007.1070

2-s2.0-34648846751

23.

Kusy

Lee

Wicke

Milosavljevic

Guibas

Predictive QoS routing to mobile sinks in wireless sensor networks

Proceedings of the International Conference on Information Processing in Sensor Networks (IPSN '09)

April 2009

109 120

2-s2.0-71049154457

24.

Luo

Hubaux

J.-P.

Joint mobility and routing for lifetime elongation in wireless sensor networks

Proceedings of the IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '05)

March 2005

1735 1746

2-s2.0-25844459686

25.

Zhao

Yang

Efficient data gathering with mobile collectors and space-division multiple access technique in wireless sensor networks

IEEE Transactions on Computers 2011 60 3 400 417

10.1109/TC.2010.140

MR2767391

2-s2.0-79551553785

26.

Lasassmeh

S. M.

Conrad

J. M.

Time synchronization in wireless sensor networks: a survey

Proceedings of the IEEE Conference: Energizing Our Future (SoutheastCon '10)

March 2010

Concord, NC, USA

242 245

10.1109/SECON.2010.5453878

2-s2.0-77952704966

27.

Cormen

T. H.

Leiserson

C. E.

Rivest

R. L.

Stein

Introduction to Algorithms 2001 2nd

Cambridge, Mass, USA

The MIT Press

MR1848805

28.

Chowdhury

Ghosh

Sinha

Das

A novel genetic algorithm to solve travelling salesman problem and blocking flow shop scheduling problem

International Journal of Bio-Inspired Computation 2013 5 5 303 314

10.1504/IJBIC.2013.057172

2-s2.0-84886539352

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

Abstract

1. Introduction

2. Related Work

3. Preliminaries

3.1. Network Model

3.2. Definitions

Definition 1.

Definition 2.

Definition 3.

Definition 4.

3.3. Problem Statement

4. Design of EEBRHM

4.1. Algorithm Description

Algorithm 1: EEBRHM algorithm.

4.2. Performance Analysis

5. Simulation Results

5.1. The Impact of Sensor Node Density

5.2. The Impact of Communication Radius

6. Conclusion

Footnotes

Conflict of Interests

Acknowledgments

References