Abstract-In a wireless sensor network (WSN), a huge number of sensor nodes with limited battery power are generally deployed over a severe field to gather data. It is impractical to recharge or replace the batteries of the sensor nodes in such a severe environment. Therefore, an energy efficient protocol is essential to maximize the lifetimes of nodes. In this paper, we propose a grid-based data aggregation scheme (GBDAS) for WSNs. We partition the whole sensor field into a 2-D logical grid of cells. In each cell, the node with the most residual energy takes turn to be the cell head, responsible for aggregating its own data with the data sensed by the other sensor nodes of the cell, and then transmitting it out. In order to reduce the data transmissions to the base station (BS), we further link each cell head to form a chain. In the chain, the cell head with the most residual energy is designated in turn as the chain leader. Aggregated data moves from head to head along the chain, and finally the chain leader transmits to the BS. In GBDAS, 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 shows that GBDAS outperforms Direct and PEGASIS. Index Terms-Base station, cell head, data aggregation, grid-based, wireless sensor networks. Wireless sensor networks (WSNs) with a variety of potential applications have been drawing a lot of attention in recent years [1] , [2] . Such networks usually comprise of a great number of low-cost and low-power tiny sensor nodes with the capability of gathering, processing, and transmitting data [3]- [5] . Sensor nodes are typically powered by batteries so their energy is strictly constrained. After being deployed, these sensor nodes are left unattended. Therefore, it is critical to manage sensor nodes in an energy efficiency manner. Since the energy consumption of sensor nodes is significantly spent in data transmission, especially for a long distance. An energy efficient transmission protocol is essential to maximize the lifetimes of sensor nodes. 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 nodes to directly transmit Manuscript received July 10, 2013; revised September 10, 2013 their data to the BS is so considerable that they 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] . In our proposed scheme, only a small portion of nodes are responsible for disseminating the data to the BS instead to decrease the data transmissions. To reduce the amount of data transmitted to the BS, the dissemination nodes aggregate their own data with the data sensed by others and then transmit out. Aggregated data moves from dissemination node to dissemination node, and finally a designated node transmits to the BS. It is our design goal to evenly distribute the energy consumption of sensor nodes to maximize their lifetimes, so as to extend the lifetime of the whole WSN. In this paper, we present a protocol called a grid-based data aggregation scheme (GBDAS) for WSNs. In order to extend the lifetime of a WSN, we construct a grid-based infrastructure by partitioning the whole sensor field into a grid of cells. Each cell has a head, the one with most residual energy of the cell, responsible for aggregating and disseminating data. Each cell head is further linked to form a chain. In each round, one cell head with the most residual energy is designated as the chain leader, responsible for directly transmitting data to the BS. In GBDAS, all sensor nodes periodically transmit the sensed data to its cell head. After receiving the data from the other member nodes of the 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 protocol [7] . The rest of this paper is organized as follows. Section II briefly reviews some related works. In Section III, our proposed scheme is described. The simulation results are discussed in Section IV. Finally, Section V draws the conclusion. Many WSN protocols have been developed to extend the system lifetime in recent years. Among of those, we briefly review some of relevant designs: diffusion-based, cluster-based, chain-based, and grid-based. In the diffusion-based protocol, Directed Diffusion [1] proposes a data centric dissemination protocol for sensor networks. Data generated by sensor nodes is named using attribute-value pairs so that a node requests data just by sending interests for named data. Data matching the interests is then drawn down toward that node. Intermediate nodes can cache and aggregate data. Directed Diffusion applies the technique of initial low-rate data flooding to establish a reinforced path from source to destination. Thus, data packets are then forwarded through that route instead of being broadcast. EADD [8] changes the node's forwarding moment that depends on each node's available energy, allowing the nodes with higher available energy to response more quickly than those with lower available energy. EADD solves uneven energy consumption problem to achieve balanced nodes' energy distribution and extend the network lifetime. Wan et al. [2] propose a gradient model based on one-phase Directed Diffusion. This model evenly distributes the energy load among all the nodes in the network. It also takes account of the hop count from sink to an intermediate node to satisfy some real-time applications. In the cluster-based protocol, LEACH [9] 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 [10], 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 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. Vidhya and Dananjayan's model [5] modifies the LEACH protocol and allows cluster heads to form a multi-hop backbone by incorporating cooperative MIMO scheme [11] through the selection of cooperative sending and receiving nodes. In the chain based protocol, PEGASIS [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 in the chain. Gathered data moves from node to node along the chain and finally a designated node called leader transmits to the BS. To reduce the average energy spent by each node per round, nodes take turns transmitting to the BS. EECB [12] improves PEGASIS by applying 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 minimum cost as leader to finally transmit gathered data to the BS. The cost is a function of the remaining energy of the node over the distance between the node and the BS. ECBSN [13] adopts 2-layer hierarchical chains. In low layer, ECBSN based on PEGASIS adopts multiple chains instead. Each chain has a leader, the node with the most remaining energy. ECBSN further links the leader of each low layer chain to form a single high layer chain. In the high layer chain, the node with the shortest distance to the BS is selected as high layer leader, responsible for transmitting the aggregated data finally to the BS. In data transmission phase, the token passing mechanism of each low layer chain is the same as that of PEGASIS. After receiving the gathered data, the leader of each low layer chain transmits to the high layer leader which eventually transmits to the BS. In the grid-based protocol, TTDD [14] 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 [15] 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. EEDD [16] also divides the whole sensor field into small virtual grids so that each grid has a head to forward data. Each grid is further divided into four sub-grids if an event is unceasing. Working nodes in the sub-grids are scheduled to stay active according to their corresponding sub-grid time slot. When a target is detected and needs to be sent to the sink, the data packets are forwarded by the working node to the neighboring grid head toward the sink. The proposed scheme has three primary phases: grid construction, chain formation, and data transmission. Our network model has the following properties: 1) All sensor nodes are stationary after deployment. 2) The BS is located far distantly from the sensor nodes. 3) Each sensor node is aware of its own geographic location based on GPS or other techniques [17, 18] . 4) Each senor node is also aware of its residual energy. 5) The sensor nodes are homogeneous and wireless channels are bidirectional. The whole sensor field is partitioned into a logical grid of M  N cells with equal size. Each cell is an α × α square with an ID, containing sensor nodes. A sensor node can calculate its cell ID [C x , C y ] from its geographic location (x, y) as follows: where (x 0 , y 0 ) is the location of the virtual origin set at the network initialization stage, α is the cell size, and   k is the largest integer not greater than k. For simplicity, we assume that all cell IDs are positive. Fig. 1 shows an example sensor field partitioned into a logical grid of 4  4 cells, where the cell IDs are enclosed by square brackets. By Eq. (1), each sensor node computes itself which cell it belongs to. Each node caches its own geographic location, cell ID, and the current cell head. In our scheme, each cell has a head, responsible for aggregating its own data with the data transmitted from the other sensor members of the cell and then forwarding to the neighboring cell head toward the BS. Networks, Vol. 1, No. 4, December 2013 330  Journal of Advances in Computer The main idea in GBDAS is to construct a chain by linking all cell heads so that sensed data can be disseminated along the chain. Basing on the assumption that all nodes start with an equal amount of energy, we randomly designate a node in each cell initially acts as the cell head. Since a head node consumes much more energy than a non head node. For gathering data in each round, 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 start with the farthest cell head to construct the chain applying the greedy algorithm. Fig. 2 shows that the chain starts from head h 0 connecting to head h 1 , head h 1 connecting to head h 2 , and finally head h 14 connecting to head h 15 . 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. In 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. 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 tokens t 1 and t 2 to its two neighboring cell heads, respectively. Token t 1 will be passed recursively along the chain clockwise to the next cell head. Conversely, token t 2 will be passed recursively along the chain counterclockwise 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 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 chooses h 10 as the chain leader. After receiving the request, h 10 sends two tokens t 1 and t 2 to its two neighbors, h 9 and h 11 , respectively. Token t 1 moves from h 9 along the chain clockwise to the end node h 0 . After receiving t 1 , h 0 transmits its aggregated data to its uplink head h 1 . Likewise, h 1 aggregates its own data with the data received from h 0 and then recursively transmits to h 2 , and eventually to h 10 . The chain leader h 10 waits to receive data from h 9 and h 11 , and then aggregates its own data with the data of h 9 and h 11 . Finally, h 10 transmits only one message to the BS. In this section, we evaluate the performance of GBDAS through simulations. We first describe our simulation model and then present some of the performance results. We use the first order radio model [9] to evaluate the energy consumption of each node. According to this model, a radio dissipates E elec = 50 nJoule/bit to run the transmitter or receiver circuitry. E elec is the energy consumption of the circuit itself. Assuming d 2 energy loss, where d is the distance between nodes, a transmission amplifier at the sender node further consumes E amp d 2 , where E amp = 100 pJoule/bit/m 2 . E amp is the energy consumed by the amplifier when transmitting packets. Thus, to transmit a k-bit message a distance d using this radio model, the radio expends: and to receive this message, the radio expends: Receiving a message is not a low cost operation 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 length k is set to 2000 bits and the energy consumed for data aggregation is assumed 5 nJoule/bit/message.  In the following, we compare the performance of GBDAS with that of Direct and PEGASIS [6] using several random 2000-node networks. Direct approach is simply for each node to transmit its data directly to the BS. In GBDAS, the BS is located at (1000, 1500) 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.  In this paper, we construct a grid-based infrastructure by dividing the sensor field into a grid of cells to minimize the amount of data transmitted to the BS. Each cell head aggregates its data with the data sensed by the other member nodes of the cell. Besides, GBDAS also performs data aggregation for each cell heads in the chain except both end nodes. In order to reduce data transmissions to the BS, we further connect the cell heads by greedy algorithm to form a chain. Only cell heads in the chain need to disseminate data to the leader then to the BS. In each round for data collecting, member nodes take turns to be cell head. Likewise, cell heads in the chain also take turns to be the chain leader. Therefore, the energy consumption of sensor nodes is evenly distributed so as to maximize their lifetimes. As a result, the lifetime of the whole WSN extends. Our simulations show that GBDAS outperforms Direct and PEGASIS when 1%, 20%, 50%, and 100% of nodes die for different initial energy levels. Networks, Vol. 1, No. 4  Journal of Advances in Computer
GBDAS REF is a grid-based data aggregation scheme that partitions the sensor field into a 2-D logical grid of cells.
Grid-Based Data Aggregation for Wireless Sensor Networks
Journal of Advances in Computer Networks
Computer Science