A Dynamic Virtual Force-Based Data Aggregation Algorithm for Wireless Sensor Networks

Abstract

In wireless sensor networks (WSNs), energy efficiency is critical for increasing network lifetime. WSNs consist of low-cost nodes with constrained energy. Present study demonstrates that data aggregation is an effective approach to reduce energy consumption in WSNs. Current data aggregation algorithms, such as cluster-based, tree-based, and chain-based data aggregation algorithm, incur high overhead to maintain structures and in dynamic scenarios incur much more cost to continuously reconstruct aggregate route. In this paper, we propose a dynamic virtual force-based algorithm (VFE) for data aggregation which can adapt to different scenario changes. Inspired by the concept of cost field and virtual force, VFE constructs dynamic routing without structure overhead, which makes data aggregation more efficient. The simulations confirm that VFE achieves significant energy saving and prolongs network lifetime.

1. Introduction

Wireless sensor networks are applied to numerous applications, for example, wild habitat monitoring, forest fire detection, building safety monitoring, military surveillance, and so on [1]. With the development of technology, the size of sensor node is getting smaller, so the battery capacity is constrained and the computing performance is getting stronger so the energy consumption is increased. The deployment of sensor nodes is always without careful preplanning and performed in an ad hoc manner [2]. Therefore, it is critical to design WSNs data aggregation algorithm that saves energy and consequently prolongs the network lifetime [3]. If a data aggregation algorithm maximizes the function of sensor network it is energy efficient [4]. In order to use the constrained energy more efficiently, most existing data aggregation algorithms attempt to find the optimal aggregation at nodes.

However, it is insufficient to only focus on the problem of energy efficiency when designing data aggregation algorithm. Other factors such as network lifetime, data accuracy, and data latency should also be taken into account. Previous research shows that nodes drain their energy much more faster if they are closer to the sink [5]. This energy consumption difference could make some nodes fail while others working and in this case, the network lifetime could be dramatically reduced. Therefore, it should be rational to keep suitable balance between energy efficiency and energy consumption difference [6]. With the data aggregation mechanism, a node could hold data received or self-generated data for a while and aggregate those data then send out aggregated data [7]. Data aggregation attempts to collect the most critical data from other sensors and make it available to the sink in an energy efficient manner with minimum data latency [4]. Data packets spatially and temporally convergent are two main methods for efficient data aggregation.

VFE maintains a cost field based on gradient and it provides sensor nodes with the direction to the sink. The concept of “gradient” usually means to set the neighboring nodes at a global direction towards destined sink. Thus, each sensor node obtains the direction to send sensing data to the sink. The cost field based design is inspired by a common, natural phenomenon: mountain water flows down into a valley, and the altitude at each point serves as the guide to direct the water from a high post to a low post and eventually to the valleys bottom, which has the lowest altitude [8]. It can be set up according to any common form, such as hop count, energy consumption, or physical distance [9]. In VFE the gradient is established based on the minimum energy consumption from node to sink.

Khatib [10] first proposed the virtual force theory and it was applied in the research of the mobile robotics route plan and obstacle avoidance. Howard et al. [11] applied it to the coverage problem of WSNs. Assuming that each sensor node attracts the other nodes with virtual force and attract them to transmit data to it, we consider the sensor node as a mass and then calculate its virtual force.

The structure of this paper is as follows. Section 2 introduces some related works. Section 3 presents the design of this algorithm. Section 4 is the evaluation of three different algorithms. Section 5 is the conclusion.

2. Related Works

However, current data aggregation algorithms, such as cluster-based, tree-based, and chain-based data aggregation algorithms, maintain a relatively fixed structures and cannot adapt to scenario change; we define those data aggregation algorithms as static algorithms. Heinzelman et al. [12] proposed low-energy adaptive clustering hierarchy (LEACH) algorithm and LEACH was the first cluster formation algorithm. LEACH divides the network into different clusters randomly; in each cluster it assigns a node as cluster head and cluster head transport and aggregates data from its cluster to the sink. Younis and Fahmy [13] proposed hybrid energy efficient distributed (HEED) algorithm; the ideal is to form clusters efficiently for extending network lifetime and select cluster head according to node residual energy and a secondary parameter. Lindsey et al. [14] proposed a typical chain-based data aggregation protocol, power efficient data gathering protocol for sensor information systems (PEGASIS); it employs greedy algorithm to construct the chain. Greedy chain formation assumes global knowledge of the network and it will incur high overhead. Ding et al. [15] proposed a method which generates minimum spanning tree (MST) by implementing Prim algorithm. These data aggregation routing algorithms may perform well in static scenario where nodes function properly.

Nevertheless in dynamic scenario, situations changing rapidly and nodes may move or fail unexpectedly, for example, monitoring of active volcano, difficult terrain border lands, battlefields, and so forth. In those scenarios, situations change rapidly and those routing algorithms incur high route constructing and maintenance overhead. Yue et al. [16] proposed a novel cluster-based data aggregation algorithm. The algorithm implemented cluster head rotation technique in each cluster and it helps in balancing the energy dissipation. Zechinelli-Martini et al. [17] proposed an energy aware data aggregation model, in which temporal database is implemented in the sensors and the intention of this aggregation model is to achieve WSNs energy efficiency by minimizing the packet transmissions. Esnaashari and Meybodi [18] proposed a learning automata protocol which relies on gathering similar sensors' data only, and it consists of two phases: route discovery and route selection, and these available routes consider the shortest discovered paths to the sink and have the same length. Li et al. [7] proposed a lifetime balanced data aggregation algorithm; that is, instead of focusing on energy consumption of individual node, design a unique algorithm to balance the nodal lifetime. Said et al. [19] proposed a new effective data aggregation protocol to reduce the energy consumption in WSNs; it uses in-network aggregation to distribute the processing all over the aggregate route to avoid unbalanced energy consumption on specific nodes until they run out. There still are plenty of novel algorithms such as those described in [20, 21]. These data aggregation routing schemes introduced some good solutions for dynamic scenario.

In this paper, we propose a dynamic data aggregation routing algorithm. We achieve this algorithm by building up the cost field based on the minimum energy consumption from node to sink, and then each node uses the virtual force to select the optimal node to be the next hop. Hence, we can use dynamic routes for data aggregation.

3. Design of Virtual Force-Based Energy Efficient Algorithm (VFE)

In the following analysis, the nodes are considered to be uniformly and randomly placed in a two-dimensional space. All nodes have equal, omnidirectional transmission patterns of range and the sink energy supply is adequate.

3.1. Cost Field

At the beginning of VFE, the sensor network establishes a cost field and the cost field provides the direction from node to the sink. Since a node decides whether it should forward a packet, it does not have to keep the information that the data should be forwarded to which neighbor [22]. When the transmission power of a node is adjustable, the total amount of energy consumed in transmitting a packet along a path is a better routing metric than hop count [9]. The probability that a neighbor node selects its next hop depends on this node's gradient.

Ye et al. [8] use the overhead of one packet per node to construct the optimal cost field and devised an efficient backoff-based cost field scheme. Define the cost as the minimum energy consumed by transmitting and recieving a packet from node to the sink. VFE adopts the backoff-based cost field. In a general way to set up a cost field is network-wide flooding. The flooding scheme rebroadcasts node's cost whenever it receives a lower cost. However, the backoff-based cost field scheme allows a node to broadcast it's cost after a certain delay and results in incuring much less overhead than the flooding scheme. In [9], the authors proposed an improved cost field establishment algorithm. However, cost field is not the main issue in this paper, and the backoff-based cost field setup algorithm is sufficient for both energy efficiency and computing complexity.

Initially sink broadcasts an ADV (advertisement) message and the initial cost is 0; each node sets its initial cost of ∞. If a node hearing an ADV message from other nodes while ADV message propagates in the whole network, then the node adds the heard ADV cost as its own cost, which is the cost between this node and the sender. It compares this new cost to the heard message (if there exist other cost), and if the new cost is smaller, it sets itself as the cost of this node. A node may hear many ADV messages before a node settles its minimum cost, to avoid significant redundancy with too many duplicated messages in a node. Instead of broadcasting immediately after obtaining a lower cost, we defer the node to broadcast its cost until it heard the message with minimum cost. Thus, the node may broadcast with its optimal cost and only broadcast once. Eventually, each node can implicitly offer the direction to send sensing data to the sink.

Once the cost field is established, data packets then can flow along minimum energy consumption paths to the sink. Note that these periodic broadcasts ADV messages throughout the whole network may cause excessive overhead in WSNs [23]. Furthermore, network topology may change, for instance, wireless link breakage, sensor node failure, or mobility; some gradient value will be changed and then require more frequent broadcast. Thus it will drain out nodes' energy on that path quickly and cause packets congestion. However, to reduce energy consumption in those nodes and extend network lifetime, VFE uses the cost field to restrict the direction of packets transmission, and nodes should choose the optimal path with the virtual force.

The dynamic routing scheme employed by VFE is based on a virtual force model. It is assumed that each node initially has a single sensed information to send to the sink in the network and each node attracts its neighbors with virtual force (in this paper, we define neighbors of nodes' as nodes within one hop away from node u, as shown in Figure 1, and all the grey dots are neighbors of node u), and the virtual force is a force which goes along a straight line between two sensor nodes; those blue arrows are virtual force between node u and its neighbors. The virtual force between node u and node v, $F_{u v}$ , is directly proportional to the mass of the node itself and the mass of neighboring sensor nodes and inversely proportional to the square of the distance between them. We define node's energy consumption ratio and data amount as “mass of sensor” and the equation of virtual force can be shown as follows:

\begin{matrix} F_{u v} = k \frac{M_{u} M_{v}}{r_{u v}^{2}}, \end{matrix}

(1)

where k is a constant coefficient and

M_{u}

and

M_{v}

are mass of node u and node v, while

r_{u v}

is the distance between u and v. The virtual force of node is defined in terms of the mass of neighboring nodes to it and it determines which node should be the next hop. The mass of node describes the energy consumption ratio and the data amount of the node, so the mass of sensor is as follows:

\begin{matrix} M_{u} = α \frac{E_{residual}}{E_{initial}} + (1 - α) \frac{1}{K_{u}}, \end{matrix}

(2)

where

E_{residual}

is the residual energy of node u and

E_{initial}

is the initial energy of node u and

K_{u}

is responsible for aggregation node v's data with its own. We have

\begin{matrix} K_{u} = k_{u} + δ (k_{1} + k_{2} + \dots + k_{i}), i \in (1, n), \end{matrix}

(3)

where

K_{u}

and

k_{u}

denote the data amount of node u before and after aggregation and

k_{i}

is the packet node i sent to node u and

k_{1} + k_{2} + \dots + k_{i}

are aggregated data from neighbors and δ is data aggregation ratio. In (2),

α \in \{0,1\}

, which means that when value of α increases, the proportion of energy consumption will increase and the proportion of data amount will decrease; as a result, mass of node u will correspondingly change, and the virtual force between different nodes will change too. The parameter α is changeable, while node's energy falling too quick, and reduces the value of α and the corresponding mass of this node will decrease. The parameter α is of great importance to extend the lifetime of network.

Figure 1

Data aggregation process of VFE.

In (2), $E_{residual} / E_{initial}$ reflects the ratio of energy consumption; hence node u is much more likely to choose the node with less energy consumption to be the next hop. $1 / K_{u}$ is inversely proportional to the data amount of node u, and node u is more likely to choose the node with less data amount to be the next hop.

Figure 1 illustrates our basic idea. We suppose that the dotted line in Figure 1 is the current cost field which is established through the broadcast of ADV messages at initial stage. Node u is attracted by all its neighbors in different directions and the power of those virtual forces is different. In this theory node u needs to determine which neighbor should be the next hop in the aggregate route.

3.2. Selection of Neighbor Nodes

Our goal is to send sensor nodes' data packets to sink in dynamic aggregate routes and to consider the energy balance, so we will select the maximum virtual force along the cost field. Hence the neighbor with the maximum virtual force will be the next hop in the aggregate route and it is a dynamic process. While the data aggregation process works, the residual energy and obtained data of nodes are diverse from each other and the virtual forces of neighbor nodes are changing; in this way, we can achieve dynamic routing and extend network lifetime and effective data aggregation. The process of VFE is summarized as Algorithm 1.

Algorithm 1: VFE algorithm.

(1) Initialization: nodes, sink

(2) sink broadcast ADV messages

(3) if nodes heard the message with minimum cost then

(4) build cost field

(5) end if

(6) node u (source node) detect event

(7) for all node u's neighbors do

(8) neighbors calculate virtual force

(9) end for

(10) node u choose the maximum virtual force node along the

cost field as next hop

(11) after 200 rounds, recalculate virtual force and rebuild

aggregate routes

Figure 2 is an example of neighbor nodes selection. As shown in Figure 2, all the grey dots are neighbors of node u; blue arrows are virtual force between node u and its neighbors; the black arrow is the direction of cost field. The virtual force is proportional to the length of arrows; then $F_{a u} > F_{b u} > F_{c u}$ . In a normal way, node u should choose node a as the next hop. However in VFE, the direction of cost field presents the direction to the sink, so the node with maximum virtual force along the cost filed should be the next hop; in Figure 2, node u should choose node b as the next hop.

Figure 2

Example of neighbor nodes selection.

4. Evaluation

This section shows the effect of the proposed algorithm on energy consumption. We use OMNET++ 4.3 simulator to evaluate the performance of our algorithm and the parameters of our simulations are shown in Table 1. Sensor nodes are uniformly distributed in a $100 \times 100$ m² field. There are 2 sources in the corner of the field, an event report every round, with a packet size of 32 bytes. After the cost field is established, to avoid frequent change of aggregate routes and reduce data calculation which is caused by variety of virtual force, we specify that virtual force will be recalculated after 200 rounds.

Table 1

Configuration of parameters.

Item	Parameters
Area size	100 m × 100 m
Deployment type	Randomly
Number of nodes	100
Radio range	10 m
Packet size	32 bytes
Default α	0.5
δ	0.3

We compare VFE with two existing data aggregation algorithms, power efficient data gathering and aggregation protocol-power aware (PEDAP-PA) [24] and energy efficient data aggregation ant colony algorithms (DAACA) [25]. In PEDAP-PA, it constructs minimum spanning tree (MST) by using Prim algorithm, where data packets transmit and aggregate along tree routes, and it provides near optimal lifetime for the first node although slightly decreasing the lifetime of the last node. In DAACA, authors consider each node as an artificial ant which is raised in ant colony optimization. Each node estimates the amount of pheromones and the remaining energy to compute the probabilities for selecting the next hop. After certain rounds of transmissions, the pheromones adjustments are performed; then it can build the optimal route.

Figure 3 shows the time of all nodes dead of network (we define round as a packet deliver from source node to sink). In PEDAP-PA, the Prim algorithm is used to construct the tree routes which can save energy with neighbor nodes; however, this is a centralized method; the sink will consume much more energy than other nodes. The energy cost in maintaining the network is high; hence nodes' energy consumption is quicker than the other two algorithms. In DAACA, there is no overhead for topology or MST reconstruction; therefore, the average energy cost is lower than PEDAP-PA. But the aggregate route of DAACA is static, so data packets will be sent along maximum pheromones routes and the energy of the nodes on these routes will drain quickly. In VFE, there is no overhead for structure maintenance and aggregate route is dynamic, so nodes' energy consumption is smaller than those other two algorithms. Assuming that a sensor network is properly functioning if 70% sensor nodes are alive and as shown in Figure 3, the network lifetime of VFE is longer than those two algorithms.

Figure 3

Number of dead nodes after a certain round.

Figure 4 shows the average remaining energy of three data aggregation algorithms. All sensor nodes are uniform, but different algorithms will cause huge difference in energy consumption. As expected, the PEDAP-PA consumes much more energy than DAACA and VFE. In PEDAP-PA, the sink needs to broadcast the topology of the network to all nodes in the network periodically; hence it consumes most energy. Although in DAACA, nodes need no topology of the network, when events source of the network changes frequently, it needs depositing global pheromones and because the established global pheromones are useless, the energy consumption is substantial. Whereas in VFE, it maintains a cost field based on the minimum energy consumption, and each node will compare the remaining energy and the amount of data packets with its neighbors to achieve balanced usage of energy.

Figure 4

Average energy cost of sensor node.

Figure 5 shows the total transmitted data amount of three data aggregation algorithms. The PEDAP-PA transmitted much less data than DAACA and VFE. In PEDAP-PA, as the energy consumption is faster than those two algorithms, the whole network's lifetime is less; thus transmitted data amount is less. In DAACA, because of the frequent reconstruction of aggregate routes which cannot adapt to dynamic scenario, the performance of this algorithm is worse. In VFE, while sensor nodes choose the next hop, they will calculate virtual force of their neighbors, and nodes will choose the maximum virtual force node as the next hop. In other words, node will choose neighbor nodes with more remaining energy and less data amount as next hop, and there are different routes existing at the same time. If some routes are congested or there are too many data packets in some nodes, new data packets can be delivered to the sink through different routes. Hence, our algorithm can avoid data congestion effectively and balance energy consumption of the whole network.

Figure 5

Transmitted data amount.

Figure 6 shows that different α cause different network lifetimes in VFE. As shown in Figure 6, while $α = 0.3$ , VFE can achieve the longest network lifetime, $α = 0.7$ ; the network lifetime of VFE is the shortest. The parameter α is of great importance in our mechanism. Though $α = 0.3$ the network lifetime is longer than the other two situations but it will reduce node's mass. Node's mass is reduced and the possibility to be choosen as the next hop by other nodes will decrease too, and it will be sharply reduced in data transmission. In different applications we can choose the more suitable α and achieve the best effect.

Figure 6

Network lifetime difference with varying α.

5. Conclusion

In this paper, we propose an energy efficient data aggregation algorithm adapting to dynamic routing to collect data in WSNs. Existing data aggregation algorithms cannot adapt to dynamically changing scenario and cannot make data aggregation effective. To achieve efficient data aggregation, we want packets to concentrate in space. But nodes on this path would drain their energy quickly. Motivated by the cost field and virtual force theories, we propose a virtual force-based dynamic routing algorithm which makes data aggregation more efficient.

Footnotes

Conflict of Interests

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

Acknowledgments

This work is supported by National Natural Science Foundation of China Grant no. 61001086 and Fundamental Research Funds for the Central Universities Grant no. ZYGX2011X004.

References

Roy

Conti

Setia

Jajodia

Secure data aggregation in wireless sensor networks

IEEE Transactions on Information Forensics and Security 2012 7 3 1040 1052

10.1109/TIFS.2012.2189568

2-s2.0-84861116512

Patil

Biradar

R. C.

A survey on routing protocols in Wireless Sensor Networks

Proceedings of the 18th IEEE International Conference on Networks (ICON '12)

December 2012

86 91

10.1109/ICON.2012.6506539

2-s2.0-84877857310

Luo

Tao

Das

S. K.

Data fusion with desired reliability in wireless sensor networks

IEEE Transactions on Parallel and Distributed Systems 2012 23 3 501 513

10.1109/TPDS.2010.93

2-s2.0-79551558434

Rajagopalan

Varshney

P. K.

Data-aggregation techniques in sensor networks: a survey

IEEE Communications Surveys & Tutorials 2006 8 4 48 63

Olariu

Stojmenović

Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting

Proceeding of the 25th IEEE International Conference on Computer Communications (INFOCOM '06)

April 2006

Barcelona, Spain

1 12

10.1109/INFOCOM.2006.296

2-s2.0-34047156164

Ren

Zhang

Lin

Ren

S. K. D.

EBRP: energy-balanced routing protocol for data gathering in wireless sensor networks

IEEE Transactions on Parallel and Distributed Systems 2011 22 12 2108 2125

10.1109/TPDS.2011.40

2-s2.0-80055033920

Peng

Qiao

Zhang

LBA: lifetime balanced data aggregation in low duty cycle sensor networks

Proceedings of the IEEE Conference on Computer Communications (INFOCOM '12)

March 2012

1844 1852

10.1109/INFCOM.2012.6195559

2-s2.0-84861611375

Chen

Zhang

A scalable solution to minimum cost forwarding in large sensor networks

Proceedings of the 10th International Conference on Computer Communications and Networks

2001

Scottsdale, Ariz, USA

304 309

10.1109/ICCCN.2001.956276

Huang

Chen

Xing

Tan

SGF: a state-free gradient-based forwarding protocol for wireless sensor networks

ACM Transactions on Sensor Networks 2009 5 2, article 14

10.1145/1498915.1498920

2-s2.0-65849210446

10.

Khatib

Real-time obstacle avoida nce for manipulators and mobile robots

International Journal of Robotics Research 1986 5 1 90 98

2-s2.0-0022674420

11.

Howard

Mataric

M. J.

Sukhatme

G. S.

Mobile sensor network deployment using potential field: a distributed scalable solution to the area coverage problem

Proceedings of the 6th International Symposium on Distributed Autonomous Robotics Systems (DARS '02)

June 2002

Fukuoka, Japan

12.

Heinzelman

W. R.

Chandrakasan

Balakrishnan

Energy-efficient communication protocol for wireless microsensor networks

Proceedings of the 33rd Annual Hawaii International Conference on System Sciences

January 2000

2-s2.0-0033877788

10.1109/HICSS.2000.926982

13.

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

14.

Lindsey

Raghavendra

Sivalingam

K. M.

Data gathering algorithms in sensor networks using energy metrics

IEEE Transactions on Parallel and Distributed Systems 2002 13 9 924 935

10.1109/TPDS.2002.1036066

2-s2.0-0036766616

15.

Ding

Cheng

Xue

Aggregation tree construction in sensor networks

Proceedings of the IEEE 58th Vehicular Technology Conference (VTC '03)

October 2003

16.

Yue

Zhang

Xiao

Tang

A novel unequal cluster-based data aggregation protocol for wireless sensor networks

Przegląd Elektrotechniczny 2013 89 1 20 24

17.

Zechinelli-Martini

J. L.

Bucciol

Vargas-Solar

Energy aware data aggregation in wireless sensor networks

Proceedings of the 2nd International Conference on Wireless Communication, Vehicular Technology, Information Theory and Aerospace and Electronic Systems Technology (Wireless VITAE '11)

March 2011

Chennai, India

1 5

10.1109/WIRELESSVITAE.2011.5940864

2-s2.0-79960904367

18.

Esnaashari

Meybodi

M. R.

Data aggregation in sensor networks using learning automata

Wireless Networks 2010 16 3 687 699

10.1007/s11276-009-0162-5

2-s2.0-77953356766

19.

Said

A. M.

Ibrahim

A. W.

Soua

Afifi

Dynamic aggregation protocol for Wireless Sensor Networks

Proceeding of the 27th IEEE International Conference on Advanced Information Networking and Applications (AINA '13)

March 2013

Barcelona, Spain

356 361

10.1109/AINA.2013.44

2-s2.0-84881064838

20.

Hoang

D. C.

Kumar

Panda

S. K.

Optimal data aggregation tree in wireless sensor networks based on intelligent water drops algorithm

IET Wireless Sensor Systems 2012 2 3 282 292

10.1049/iet-wss.2011.0146

2-s2.0-84866905021

21.

Cheng

C.-T.

Tse

C. K.

Lau

F. C. M.

A delay-aware data collection network structure for wireless sensor networks

IEEE Sensors Journal 2011 11 3 699 710

10.1109/JSEN.2010.2063020

2-s2.0-79251634987

22.

Zhong

Zhang

GRAdient broadcast: a robust data delivery protocol for large scale sensor networks

Wireless Networks 2005 11 3 285 298

10.1007/s11276-005-6612-9

2-s2.0-2442529460

23.

Han

K. H.

Y. B.

A novel gradient approach for efficient data dissemination in wireless sensor networks

Proceedings of the 60th IEEE Vehicular Technology Conference (VTC '04)

September 2004

Los Angeles, Calif, USA

IEEE

2979 2983

10.1109/VETECF.2004.1400607

24.

Tan

Korpeoglu

Power efficient data gathering and aggregation in wireless sensor networks

SIGMOD Record 2003 32 4 66 71

10.1145/959060.959072

2-s2.0-14344252208

25.

Lin

Xia

Yao

Pei

Energy efficient ant colony algorithms for data aggregation in wireless sensor networks

Journal of Computer and System Sciences 2012 78 6 1686 1702

10.1016/j.jcss.2011.10.017

MR2968170

2-s2.0-84866341621