Chapter 3. Energy-aware Balanced In-Network Aggregation

After the detailed description of wireless sensor networks, problem of data aggregation for maximizing network lifetime, and existing aggregation techniques in chapter 1 and 2, we now present our proposed protocol for solving data aggregation problem. This chapter first gives you an introduction of our protocol “Energy-aware Balanced In-Network Aggregation (E-BINA)” and then briefly describes the system and energy model that has been considered for designed protocol. After this a detailed description of the algorithm will be presented. As there are some issues involved with every protocol, so with our proposed protocol also. These issues will be presented in brief and finally we summarize this chapter.

3.1 Introduction

The three broad categories of data aggregation techniques that we have described in previous chapter are: tree-based approach, multi-path approach, and cluster-based approach. Focusing on cluster-based approach, we found that the existing protocols assume a sensor network which is divided in to several clusters. Depending upon the protocol operation, each cluster-head receives the data packets from some cluster-member or from all cluster-member nodes directly and then cluster-head perform aggregation operation.

Taking the advantageous features of tree-based approach, we have designed our protocol which takes the merits of both cluster-based and tree-based approach. E-BINA assumes a cluster-based wireless sensor network and applies tree-based approach inside each cluster. When a cluster is formed and cluster-head selected, it consider cluster-head as root and construct an aggregation tree over cluster-member nodes. The process of aggregation tree construction requires the sensor nodes to reduce their transmission power as sensor nodes now have to send their data packets to the neighbor node which is selected as parent. Energy consumed in wireless transmission is directly proportional to the square of the distance between nodes in communication [13]. Since cluster-member node now sends their data packets to the neighbor node instead of cluster-head, the transmission distance is reduced and hence the energy consumption of the sensor node. Likewise, overall energy consumption of sensor nodes in a cluster is reduced and so for the whole sensor network. Hence overall network lifetime will be increased.

Energy-aware Balanced In-Network Aggregation (E-BINA) protocol is energy-aware as it has taken the residual energy of sensor node in to consideration while constructing the aggregation tree. The protocol also balances the network load by selecting different parent for a node according to the energy level remain in the sensor node during the aggregation tree construction process. Each parent node performs aggregation of data packet that it receives from its child nodes and hence the protocol justifies the in-network aggregation concept.

3.2 System & Energy Model

Consider a homogeneous network of n sensor nodes and a base station or sink node distributed over a region. The location of the sensors and the base station are fixed and known priori. Each sensor produces some information as it monitors its vicinity. We assume that the whole network is divided in to several clusters; each cluster has a cluster-head (CH). The clustering and the selection of cluster-head (CH) can be done by using any existing protocol like LEACH, such that cluster-head (CH) is maximum k-hop away from any node in cluster. We also assume that after the formation of cluster the transmission power of all nodes is adjusted in such a way that they can perform single hop broadcast. Single hop broadcast refers to the operation of sending a packet to all single-hop neighbors [8].

Our energy model for the sensors is based on the first order radio model described in [17]. A sensor consumes Eelec = 50nJ/bit to run the transmitter or receiver circuitry and Eamp = 100pJ/bit/m² for the transmitter amplifier. Thus, the energy consumed by a sensor i in receiving a l-bit data packet is given by,

E_Rxi = E_elec . l (1)

while the energy consumed in transmitting a data packet to sensor j is given by,

E_Txi,j = E_elec . l + E_amp . d_i,j² . l (2)

where di,j is the distance between nodes i and j.

3.3 Protocol Description

In a cluster-based wireless sensor network, our algorithm is designed to provide energy-aware in-network data aggregation in a cluster. Each cluster uses this algorithm independently. In a cluster, the nodes can be categorized as: one cluster-head (CH) and other cluster member node.

Function of cluster-head (CH)

1. Receive a query from base station.
2. Cluster-head (CH) sends configuration packets to all single-hop neighbors.
3. Receive data packets from all single hop neighbors.
4. Finally aggregate the data packets received and route it to base station.

Function of cluster member

1. Receive configuration packets from neighbor nodes.
2. Update and forward configuration packets to all single-hop neighbors.
3. Receive data packets from neighbor nodes.
4. Aggregate all data packets by applying redundancy factor and send it to selected parent node.

The algorithm works in two phases: Configuration packet flow and Data packet flow that are described below.

                                  

Figure 3.1 A typical scenario of data aggregation in a cluster.

3.3.1 Configuration Packet Flow

Initially cluster-head broadcast configuration packet to all its neighbors. Configuration packet contains the following fields:

Node Id  location of node that each node know in prior

Hop Distance  distance from cluster-head in terms of hop count (set zero for CH)

Residual Energy  current energy in node

Each node upon receiving the broadcast configuration packet that is originated from cluster-head adds the sender of the packet in the list of its possible parents with its node id, hop distance, residual energy. After this the node again broadcast the configuration packet to all its neighbors by updating node id to its own id, incrementing hop distance by one and its own residual energy. This process continues until all the nodes in cluster receive configuration packet. All nodes that broadcast the configuration packet do so by predefined and common signal strength that is know to all the nodes.

3.3.2 Data Packet Flow

When all nodes receives configuration packets, each node now select the parent to which it can forward the data packet. The parent selection procedure is shown in fig. 3.2.

Each node looks in to the list of all its possible parents. The neighbor node which has least hop distance, ie closest to cluster-head, is selected as parent by a node. In case when two neighbor nodes have the least but equal hop distance, the node checks the residual energy of two neighbor nodes. The neighbor node that has greater residual energy is now selected as parent. In both the cases, node also calculate the difference of residual energy of two neighbor nodes, which have least hop distance, and checks whether this difference is less than the threshold or not. If it is then the node selects the parent as usual. But if it is not then the node selects other neighbor node as its parent.

Figure 3.2 Parent selection procedure.

This allows a node that has more available resources to be selected as a parent node. This also balances the consumption of energy of nodes in the cluster and leads to die out of nodes nearly at same time.

After selecting the parent node, each node now forwards its data to its parent. When a parent node receives multiple data packets from its neighbor nodes, it performs aggregation operation by eliminating redundancy in the data. Each parent node checks the equation below:

| V_Ni – V_Nj | < K (3)

                                      where, V_Ni  data value of node i

V_Nj  data value of node j

K  redundancy factor

If this equation satisfies, the parent node perform aggregation by applying any aggregation functions like MIN, MAX, and AVG on the values of data packet and send only one packet while discarding other packets. But if this equation do not satisfies, the parent performs aggregation by simply concatenating two data packet in to one keeping value of both packets intact.

The selection of value for redundancy factor (K) has a trade-off between precision and energy consumption. If the application wants more precision, it should select a low value for redundancy factor otherwise a high value. Selecting high value for K means sending only one value thus less number of bits needs to be transmitted and hence low energy consumption.

3.4 Issues

E-BINA significantly reduces the energy consumption of all nodes in the cluster by reducing the transmission power of all nodes. The one issue that arises in our designed protocol is that after the formation of cluster and selection of cluster-head, all nodes have to reduce their transmission power. All nodes have to reduce their transmission power in such a way that they could only reach their single-hop distance neighbors. This operation requires some kind of synchronization among all nodes. The nodes have to program before to perform the above task. For this, the programming task needs little extra effort. Now when cluster-head received all data packets and aggregated them, it has to now increase its transmission power so that it can transmit the final aggregated data up in the cluster-head hierarchy towards the sink. Another issue that remains with any tree based approach is robustness of the system. In case of failure of any intermediate node in the tree hierarchy during operation will lead to the loss of data.

Though E-BINA requires all nodes to adjust their transmission power after the deployment and requires extra effort for programming before, it conserves a significant amount of energy. So in the presence of the above issue, E-BINA outperforms when we try to maximize the network lifetime.

3.5 Summary

• E-BINA takes the advantageous features of cluster-based and tree-based approaches.
• Instead of sending data directly to cluster-head, nodes form an aggregation tree in each cluster.
• In aggregation tree, the selection of parent is based on two factors: hop distance and residual energy of node.
• Energy model is based on first order radio model.
• Protocol requires all nodes to adjust their transmission power.
• Protocol defines two types of packets: configuration packet and data packet.
• Each node eliminates redundancy in the data by satisfying equation (3).
• In-network aggregation is performed during data flow towards cluster-head.
• Issue: Adjustment of transmission power after deployment requires extra programming effort.