A Path-Based Approach for Data Aggregation in Grid-Based Wireless Sensor Networks

Neng-Chung Wang, Yung-Kuei Chiang, and Chih-Hung Hsieh

A Path-Based Approach for Data Aggregation in Grid-Based Wireless Sensor Networks

Neng-Chung Wang, Yung-Kuei Chiang, and Chih-Hung Hsieh

—Sensor nodes in a wireless sensor network (WSN) are typically powered by batteries, thus the energy is constrained. It is our design goal to efficiently utilize the energy of each sensor node to extend its lifetime, so as to prolong the lifetime of the whole WSN. In this paper, we propose a path-based data aggregation scheme (PBDAS) for grid-based wireless sensor networks. In order to extend the lifetime of a WSN, we construct a grid infrastructure by partitioning the whole sensor field into a grid of cells. Each cell has a head responsible for aggregating its own data with the data sensed by the others in the same cell and then transmitting out. In order to efficiently and rapidly transmit the data to the base station (BS), we link each cell head to form a chain. Each cell head on the chain takes turn becoming the chain leader responsible for transmitting data to the BS. Aggregated data moves from head to head along the chain, and finally the chain leader transmits to the BS. In PBDAS, only the cell heads need to transmit data toward the BS. Therefore, the data transmissions to the BS substantially decrease. Besides, the cell heads and chain leader are designated in turn according to the energy level so that the energy depletion of nodes is evenly distributed. Simulation results show that the proposed PBDAS extends the lifetime of sensor nodes, so as to make the lifetime of the whole network longer.

Index Terms—Base station, cell head, data aggregation, grid-based, wireless sensor networks.

1. Introduction

Wireless sensor networks (WSNs) consist of a great number of sensor nodes that are randomly deployed in a region of interest. In WSNs, sensors are not only capable of gathering and sending data but processing data as well. Advances in sensor technology, wireless communications, and digital electronics have made it possible to develop low-cost, low-power, and multi-functional small sensor nodes[1],[2]. WSNs can be applied in many applications such as environmental and habitat monitoring, target tracking, object detection, intelligent transport monitoring, and battlefield surveillance[3]-[5].

In WSNs, sensor nodes are typically powered by batteries so that their energy is restricted. It is impractical to recharge or replace the batteries of the senor nodes in such a harsh environment. The energy consumption of sensor nodes is mainly used in data transmission, especially for a long drive. This paper mainly addresses the problem of data transmission from sensor nodes to a remote base station (BS), where the end-user can access the data. Since the location of the BS is distant, the energy consumed by each node to directly transmit its data to the BS is considerable, and nodes will die very soon. Therefore, it is important for an approach to use as few transmissions as possible to the BS and reduce the amount of data that needs to be transmitted to the BS[6].

Lots of improved approaches have been proposed. Only a few nodes are responsible for forwarding the data to the BS instead of reducing the data transmissions. The forwarding sensor nodes aggregate their own data with the data sensed by others and then transmit to the BS. Aggregated data moves from node to node, and finally a designated node transmits to the BS. Therefore, it is our design goal to evenly distribute the energy consumption of sensor nodes to extend the lifetime of each sensor, so as to prolong the lifetime of the whole WSN.

In this paper, we present a path-based data aggregation scheme (PBDAS) for grid-based wireless sensor networks. In order to extend the lifetime of a WSN, we build a grid-based infrastructure by partitioning the whole sensor field into a two-dimensional (2D) logical grid of cells. Each cell has a head, the one with most residual energy. Each cell head is linked to form a chain. In each round, one cell head takes turn as a chain leader responsible for directly transmitting data to the BS. In PBDAS, all sensor nodes periodically transmit the sensed data to its cell head. After receiving the data from the others of the same cell, the cell head aggregates with its own data and then sends out. Only cell heads need to transmit data to the chain leader. The other sensor nodes just fall into sleep mode based on GAF (geographical adaptive fidelity) protocol[7].

The rest of this paper is organized as follows. Section 2 briefly reviews some related work. In Section 3, our proposed scheme is described. The simulation results are discussed in Section 4. Finally, Section 5 draws the conclusions.

2. Related Work

Many routing protocols have been developed to maximize the lifetime of while WSNs in recent years. Among of those, we roughly review some of relevant designs: chain-based, cluster-based, and grid-based.

In the chain based protocol, PEGASIS (power-efficient gathering in sensor information system)[6]links all sensor nodes with a greedy algorithm to form a chain. Each node receives from one neighbor data fused with its own and then transmits to the other on the chain. Gathered data moves from node to node along the chain, and finally a designated node, called leader, transmits the data to the BS. To reduce the average energy spent by each node per round, nodes take turns transmitting to the BS. EECB (energy-efficient chain-based routing protocol)[8]improves PEGASIS by applying a distance threshold to avoid the formation of LL (long link) on the chain to further distribute energy load evenly among the nodes. Besides, EECB selects the node with the minimum cost as leader to finally transmit gathered data to the BS. The cost is a function of the remaining energy of a node over the distance between the node and the BS.

In the cluster-based protocol, LEACH (low energy adaptive clustering hierarchy)[4]combines the ideas of cluster-based routing and media access together with application-specific data aggregation for WSNs. In LEACH, distributed clusters are self-organized by the nodes in the local cluster. Each cluster has a head responsible for aggregating data and transmitting data to the remote BS. LEACH incorporates randomized rotation of cluster head position to evenly distribute the energy load among all the nodes so as to prolong the system lifetime. In GROUP (grid-clustering routing protocol)[9], one of sinks proactively, dynamically, and randomly constructs a cluster grid structure to relay queries and data packets. Only a small part of sensor nodes will participate in the election of cluster heads. Cluster heads can expediently aggregate data to reduce the volume of data packets. GROUP can also distribute the energy load among the sensor nodes in the network.

In the grid-based protocol, TTDD (two-tier data dissemination model)[10]builds the grid on a per-source basis. A source transmits data by building a grid structure. Each grid point has a dissemination node responsible for storing and forwarding data. A sink sends the immediate dissemination node a query which is in turn forwarded towards the source. The query forwarding process lays the information of the path to the sink to enable the requested data from the source to the sink. Unlike TTDD’s per source-based grid structure, CODE[11]divides the whole sensor field into grids. Each grid has one coordinator which acts as an intermediate node to cache and relay data. In data announcement and query transfer phases, CODE establishes a data dissemination path first so that the source can send data to the mobile sink along the path.

3. Proposed Scheme

In a WSN, a great number of sensor nodes are usually deployed and the amount of sensed data from them is tremendous. These large volumes of real-time data generally need to be transmitted to the destination in such a short constrained time that the data collisions occur frequently. It greatly causes both data transmitting delay and energy depletion. Therefore, a well-designed routing protocol is needed to improve the poor network performances. In this section, we will describe the proposed protocol for WSNs in detail. The network model is based on the following basic assumptions:

1) All sensor nodes are stationary after deployment.

2) Each sensor node is aware of its own geographic location based on GPS or other techniques[12],[13].

3) Each senor node is also aware of its residual energy.

4) The sensor nodes are homogeneous and wireless channels are bidirectional.

PBDAS has three primary phases: grid construction, chain formation, and data transmission.

3.1 Grid Construction

In PBDAS, the whole sensor field is partitioned into a 2D logical grid ofM×Ncells, whereNis even. Each cell has an ID with sensor nodes. A sensor node can calculate its cell ID [CX,CY] from its geographic location (x,y) as follows:

Fig. 1. Logical grid structure.

We take 4×4 cells as an example, as shown in Fig. 1. From left to right, the cell IDs are [0, 0], [1, 0], [2, 0] and [3, 0] in the first row, the cell IDs are [0, 1], [1, 1], [2, 1] and [3, 1] in the second row, and so on and so forth.

Each sensor node computes itself which cell it belongs to by (1). All member nodes in each cell determine their own unique sequence numbers by using simple HELLO protocol. Besides, every node maintains a table to keep its own sequence number, geographic location, cell ID, and the current cell head.

In PBDAS, each cell has a head responsible for aggregating data transmitted from the other sensor nodes of the same cell and then transmitting to the neighboring cell head toward the chain leader.

3.2 Chain Formation

The main idea in PBDAS is to construct a chain by linking all cell heads so that sensed data can be disseminated along the chain. Based on the assumption that all nodes start with an equal amount of energy, we randomly designate a node in each cell initially to act as the cell head, since a head node consumes much more energy than a non head node. For gathering data in the following rounds, the node with the most residual energy of the cell subsequently takes turn being the cell head. Consequently, the energy load of being a cell head is evenly distributed among the nodes.

Once the cell head of each cell is determined, we construct the chain from the farthest row by linking the cell heads left to right then the next farthest row right to left until the nearest row of the BS.

Fig. 2 shows that the chain connection starts from headh0to headh1, then to headh2, etc., and finally to headh15. The cell head caches the information of its neighbor cell heads. In this way, the cell heads of the whole grid are finally connected together to form a chain. On the chain, a cell head with the most residual energy will be designated as the chain leader responsible for transmitting the final aggregated data to the BS.

Fig. 2. A chain.

3.3 Data Transmission

For gathering data in each round, the BS chooses the cell head with the most residual energy as the chain leader, responsible for receiving data from its two neighboring cell heads (if it has two neighbors), aggregating with its own data, and then transmitting the aggregated data to the BS.

Once the chain leader receives the request from the BS, it will send two tokenst1andt2to its two neighboring cell heads, respectively. Tokent1will be passed recursively along one chain direction (chain direction 1) to the next cell head. Conversely, tokent2will be passed recursively along the other chain direction (chain direction 2) to the next cell head. Each token travels from head to head along the chain in its own direction. When the token reaches its end, the end node transmits its own aggregated data to its uplink head in a reverse direction. Likewise, the uplink head aggregates its own data with the received data from its downlink head and then recursively transmits to its uplink head, and eventually to the chain leader. The chain leader waits to receive data from both neighbors and then aggregates its own data with its two neighbors’ data. At last, the leader transmits only one message to the BS.

For example as shown in Fig. 3, the BS choosesh13as the chain leader. After receiving the request,h13sends two tokenst1andt2to its two neighbors,h12andh14, respectively. Tokent1moves fromh12along the chain direction 1 to the end nodeh0. After receivingt1,h0transmits its aggregated data to its uplink headh1. Likewise,h1aggregates its own data with the data received fromh0and then recursively transmits toh2, and eventually toh13. The chain leaderh13waits to receive data fromh12andh14, and then aggregates its own data with the data ofh12andh14. Finally,h13transmits only one message to the BS.

Fig. 3. Data gathering for each round.

4. Simulation Results

The effectiveness of our scheme for transmitting the gathered data to the BS is validated through simulation. In this section, we present some of the performance results.

4.1 Simulation Model

We use the first order radio model[3]to evaluate the energy consumption of each node. According to this model, a radio dissipatesEelec=50 nJoule/bit to run the transmitter or receiver circuitry.Eelecis the energy consumption of the circuit itself. Assuming2denergy loss, wheredis the distance between nodes, a transmission amplifier at the sender node further consumespJoule/bit/m2.Eampis the energy consumed by the amplifier when transmitting packets. Thus, to transmit ak-bit message away a distancedusing this radio model, the radio expends:

and to receive this message, the radio expends:

Receiving a message is not a low cost operation by using these parameter values. Protocols should thus try to minimize not only the transmission distances but also the numbers of transmission and reception operations for each message. We can generalize the total transmission consumption as follows:

In our simulations, the packet lengthkis set to 2000 bits and the energy consumed for data aggregation is assumed 5 nJ/bit/message.

4.2 Performance Analysis

In the following, we compare the performance of PBDAS with that of Direct and PEGASIS[5]using several random 2000-node networks. Direct approach is simply for each node to transmit its data directly to the BS.

In PBDAS, the BS is located at (1000, 2500) in 2000 m ×2000 m field partitioned into a grid of 10×10 cells. We conducted the simulations to verify the number of rounds when 1%, 20%, 50%, and 100% of nodes die for each scheme with each node having the same initial energy level.

Fig. 4. Performance results for the network with 0.25 J/node initially.

Fig. 4, Fig. 5, and Fig. 6 show the number of rounds until 1%, 20%, 50%, and 100% of nodes die for each node with initial energy levels 0.25 J, 0.5 J, and 1.0 J, respectively. As shown in the figures, PBDAS outperforms Direct and PEGASIS in all cases. As expected, PBDAS extends the lifetime of sensor nodes so as to prolong the lifetime of the whole network.

Fig. 5. Performance results for the network with 0.5 J/node initially.

Fig. 6. Performance results for the network with 1.0 J/node initially.

5. Conclusions

In this paper, we proposed a path-based data aggregation scheme to transmit the gathered data to the BS. In terms of the overhead for building the grid structure, we only constructed the grid infrastructure once in the initial phase. Each node determines which cell it belongs to simply by an arithmetic operation. The formation of the chain is easy. Only the cell heads on the chain need to forward data to the chain leader then to the BS. It greatly reduces the energy consumption of non cell heads. To decrease the energy load of cell heads, the node with most residual energy is chosen to be cell head. Besides, cell heads take turns being the chain leader to transmit data to the BS so that the energy depletion in the network is evenly distributed. As a result, the lifetime of the sensor nodes extends so as to prolong the lifetime of the whole network. Choosing a cell head according to the energy level increases the lifetime and robustness of the WSN. Simulation results show that the proposed PBDAS outperforms Direct and PEGASIS.

[1] I. F. Akyildiz,W. Su, Y. Sankarasubramaniam, and E. Cayirci,“A survey on sensor networks,” IEEE Communication Magazine, vol. 40, no. 8, pp. 102-114, 2002.

[2] J. N. Al-Karaki and A. E. Kamal, “Routing techniques in wireless sensor networks: A survey,” IEEE Wireless Communications, vol. 11, no. 6, pp. 6-28, 2004.

[3] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan,“Energy-efficient communication protocol for wireless microsensor networks,” in Proc. of the IEEE Annual Hawaii Int. Conf. on Systems Sciences, Maui, 2000, pp. 3005-3014. [4] W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan,“An application-specific protocol architecture for wireless microsensor networks,” IEEE Trans. on Wireless Communications, vol. 1, no. 4, pp. 660-670, 2002.

[5] H. Mostafaei, M. R. Meybodi, and M. Esnaashari, “A learning automata based area coverage algorithm for wireless sensor networks,” Journal of Electronic Science and Technology, vol. 8, no. 3, pp. 200-205, 2010.

[6] S. Lindsey and C. S. Raghavendra, “PEGASIS: Power-efficient gathering in sensor information systems,” in Proc. of the IEEE Aerospace Conf., Big Sky, 2002, pp 1125-1130.

[7] Y. Xu, J. Heidemannn, and D. Estrin, “Geography informed energy conservation for ad hoc routing,” in Proc. of the Annual ACM/IEEE Int. Conf. on Mobile Computing and Networking, Rome, 2001, pp. 70-84.

[8] Y.-C. Yu and Y.-C. Song, “An energy-efficient chain-based routing protocol in wireless sensor network,” in Proc. of the Int. Conf. on Computer Application and System Modeling, Taiyuan, 2010, pp. 486-489.

[9] L. Yu, N. Wang, W. Zhang, and C. Zheng, “GROUP: A grid-clustering routing protocol for wireless sensor networks,” in Proc. of the Int. Conf. on Wireless Communications, Networking and Mobile Computing, Beijing, 2006, pp. 1-5.

[10] F. Ye, L. Haiyun, C. Jerry, L. Songwu, and L. Zhang,“Sensor networks: A two-tier data dissemination model for large-scale wireless sensor networks,” in Proc. of the Annual ACM/IEEE Int. Conf. on Mobile Computing and Networks, Atlanta, 2002, pp. 148-159.

[11] H. L. Xuan and S. Lee, “A coordination-based data dissemination protocol for wireless sensor networks,” in Proc. of the Intelligent Sensors, Sensor Networks and Information Processing Conf., Melbourne, 2004, pp. 13-18. [12] J. Albowitz, A. Chen, and L. Shang, “Recursive position estimation in sensor networks,” in Proc. of the Int. Conf. on Network Protocols, Riverside, 2001, pp. 35-41.

[13] E. D. Kaplan, Understanding GPS: Principles and Applications, 2nd ed. Boston: Artech Hourse, 1996.

Neng-Chung Wangwas born in Taichung in 1966. He received the B.S. degree in information and computer engineering from Chung Yuan Christian University in 1990, and the M.S. and Ph.D. degrees in computer science and information engineering from National Cheng Kung University in 1998 and 2002, respectively. He joined the Faculty of the Department of Computer Science and Information Engineering, Chaoyang University of Technology as an assistant professor in August 2002. From August 2006 to July 2007, he was an assistant professor with the Department of Computer Science and Information Engineering, National United University. Since August 2007, he has been an associate professor with the Department of Computer Science and Information Engineering, National United University. His current research interests include wireless and mobile networks, communication protocols, mobile computing, and parallel and distributed computing. He is a member of the IEEE Computer Society, IEEE Communications Society, and Phi Tau Phi Society.

Yung-Kuei Chiangwas born in Nantou in 1956. He received the B.S. degree in meteorology from Chinese Culture University in 1980, and the M.S. degree in computer science from University of Maryland, Baltimore County in 1989. Currently, he is an assistant professor with the Department of Computer Science and Information Engineering, National United University. His current research interests are mobile computing and wireless networks.

Chih-Hung Hsiehwas born in Miaoli in 1989. He received the B.S. degree in computer science and information engineering from Ming Chuan University in 2012. He is currently working toward the M.S. degree in computer science and information engineering at National United University. His research interests include mobile computing and wireless networks.

Manuscript received November 4, 2013; revised March 14, 2014. This work was supported by the NSC under Grant No. NSC-101-2221-E-239-032 and NSC-102-2221-E-239-020.

N.-C. Wang is with the Department of Computer Science and Information Engineering, National United University, Miaoli 360 (Corresponding author e-mail: ncwang@nuu.edu.tw).

Y.-K. Chiang and C.-H. Hsieh are with the Department of Computer Science and Information Engineering, National United University, Miaoli 360 (e-mail: ykchiang@nuu.edu.tw; x06231@gmail.com).

Color versions of one or more of the figures in this paper are available online at http://www.journal.uestc.edu.cn.

Digital Object Identifier: 10.3969/j.issn.1674-862X.2014.03.013