CEDCAP: Cluster-Based Energy-Efficient Data Collecting and Aggregation Protocol for WSNs

INTRODUCTION

---

With the advances of low-cost, low-power, multifunctional processor, memory and radio technologies, it becomes possible to develop inexpensive multifunctional wireless micro-sensors. Apparently these sensors are not so powerful and reliable compared to their expensive macro-sensor counter-parts, however, by using hundreds or thousands of them it is possible to establish a high quality, fault-tolerant wireless sensor network. These networks can be used to collect sensitive information from a large area of interest, especially where the physical environment is so harsh that the conventional macro-sensor counterparts cannot be deployed to resolve any problem. Wireless Sensor Networks (WSNs) have been used for numerous applications including military surveillance, facility monitoring and environmental monitoring. Typically, WSNs have a large number of sensor nodes with the ability to communicate among themselves and also to an external sink or a base station (Akyildiz et al., 2002). The sensors could be scattered randomly in harsh environments such as a battlefield or deterministically placed at specified locations. The sensors coordinate among themselves to form a communication network such as a single multi-hop network or a hierarchical organization with several clusters and cluster heads. The sensors periodically sense the data, process it and transmit it to the base station (Wang et al., 2011). The frequency of data reporting and the number of sensors which report data usually depends on the specific application. Data collecting is defined as the systematic collection of sensed data from some sensors to be eventually transmitted to the base station for processing. Since sensor nodes are energy constrained in wireless sensor network, it is inefficient for all the sensors to transmit the data directly to the base station. Data generated from neighboring sensors is often redundant and highly correlated. In addition, the amount of data generated in large sensor networks is usually enormous for the base station to process and the large amount of energy consumed to send the data. Hence, we need methods for combining data into high-quality information at the sensors or intermediate nodes which can reduce the number of packets transmitted to the base station resulting in conservation of energy and band width (Liu et al., 2010; Guo et al., 2010; Shi et al., 2010; Sabari and Duraisuwamy, 2010). This can be accomplished by data aggregation. Data aggregation is defined as the process of aggregating the data from multiple sensors to eliminate redundant transmission and provide fused information to the base station. Data aggregation usually involves the fusion of data from multiple sensors at intermediate nodes and transmission of the aggregated data to the base station.

LEACH (Heinzelman et al., 2000) (Low Energy Adaptive Clustering Hierarchy) is the classic hierarchical routing protocols in WSNs, The operation of LEACH is divided into “rounds”. Each round begins with a set-up phase when the clusters are organized, followed by a steady-state phase when data are transferred from the nodes to the cluster head and on to the BS. And then, the operation goes into the steady-state phase, the steady-state operation is broken into frames, where nodes send their data to the cluster head at most once per frame during their allocated transmission slot. The LEACH protocol is distributed and sensor nodes organize themselves into clusters for data fusion. A designated node (cluster head) in each cluster transmits the fused data from several sensors in its cluster to the sink. This reduces the amount of information that is transmitted to the sink. The data fusion is performed periodically at the cluster heads. LEACH is suited for applications which involve constant monitoring and periodic data reporting. Currently, there are a lot of articles been proposed for hierarchical routing algorithm. Compared with the Leach, in Lindsey and Raghavendra (2002), called PEGASIS which collects data by forming a chain, It reduces the number of nodes communicating directly with the base station to one which is responsible for transmitting the final data to the base station per round and limits the number of transmissions and receives among all nodes. Nodes take turns to transmit the fused data to the BS to balance the energy consumption in the network and preserves robustness of the sensor web as nodes die at random locations. Tan and Korpeoglu (2003) proposed two routing schema based on tree: PEDAP and PEDAP-PA, PEADP outperforms previous approaches by constructing minimum energy consuming routing for each round of communication. Another one takes it further and tries to balance the load among the nodes; the two algorithms perform well when the base station is inside the field. Energy efficient routing protocol for wireless sensor networks has been an important issue, up to now, many scholars have proposed several power efficient protocols (Singh et al., 1998; Stojmenovic and Lin, 2001; Chan and Perrig, 2004; Jiageng et al., 2005; Handy et al., 2002; Intanagonwiwat et al., 2003; Younis and Fahmy, 2004) for wireless sensor networks, There are also different protocols proposed by Xue et al. (2005), Chang and Tassiulas (2004), Tan and Korpeoglu (2003) and Chan and Perrig (Estrin) to maximize the lifetime of the system under different circumstances, Bhardwaj et al. (2001) gave the upper bounds on the lifetime of sensor networks. In the study of Tan et al. (2009), HCEP measures the load distribution among nodes by using clustering as a key communication control technique.

In this study, we have proposed a novel Cluster-based Energy-efficient Data Collecting and Aggregation Protocol (CEDCAP) for WSNs. It is based on clustering routing mechanism; the main contribution of this protocol is that employed a novel mechanism called node degree control after formation of the clusters. During the data transmission phase, the dormant nodes are into sleep mode and they do not send data so that can balance the energy consumption of all nodes and achieve the purpose of prolonging network lifetime.

SYSTEM MODEL AND PROBLEM ANALYSIS

The network model: There are various models for sensor networks. In this study, mainly consider the wireless sensor network consisting of a set of sensors and a Base Station (BS) in which sensors are randomly dispersed in the interested area. Sensor nodes are homogeneous and energy constrained. The BS and locations of sensors are fixed. The BS knows the locations of all sensors apriori which can be obtained by triangulation method or by using GPS-equipped sensors. A sensor can transmit data to any other sensor and can communicate directly with the BS. The sensors periodically monitor their vicinity and generate monitoring data. The Cluster Head (CH) are gathered from sensors which can be in the same the cluster at each round, where a round is defined as the process of gathering all the data from sensor nodes to the base station, regardless of how much time it takes. Then the CH performs data aggregation to reduce the number of messages, protocol assumes that combining n packets of size k results in one packet of size k instead of size nk. Finally, the CH can send the messages to the BS for further processing. The aim is efficient transmission of all the data to the base station so that the lifetime of the network is maximized in terms of rounds.

The radio model: In this study, assume a simple model for the radio hardware energy dissipation where the transmitter dissipates energy to run the radio electronics and the power amplifier and the receiver dissipates energy to run the radio electronics (Heinzelman et al., 2002). For this study, we will use both the free space (d² power loss) and the multipath fading (d⁴ power loss) channel models, that depending on the distance between the transmitter and receiver. In this experiments, power control can be used to invert this loss by appropriately setting the power amplifier, the free space (fs) model will be used when the distance is less than a threshold d_o;otherwise, the multipath (mp) model will be used. Therefore, when transmitting a l-bit data packet a distance d, the radio expends:

And want to receive this data packet, the radio expends:

In the specified radio model, E_elec indicates the electronics energy which depends on factors such as the digital coding, modulation, filtering and spreading of the signal. ε_fs.d² or ε_mp.d⁴ indicate the amplifier energy which depends on the distance to the receiver and the acceptable bit-error rate. For the experiments described in this study, these energy parameters are the same as those used in LEACH, as follow: E_elec = 50 nj/bit, ε_fs = 10 pj/bit/m², ε_mp = 0.0013 pj/bit/m⁴, the energy for data aggregation is set as E_DA = 5 pj/bit/signal and the initial energy is 2J for every sensor node. And assume that the radio channel is symmetric, in other words, the cost of transmitting a message from A to B is the same as the cost of transmitting a message from B to A.

PROTOCOL DESCRIPTION

In this section, we introduce the node degree control mechanisms for CEDCAP at first and then analyze the principle of algorithm CEDCAP.

Node degree control Mechanisms related definitions
Dormant radius r: Suppose node n_i has a dormant radius r, during the network operation time T_i, within coverage area of node n_i which radius is r, the rest of the nodes in time T_i are in a dormant state, they are neither gathering any data nor sending any data.

Dormant area S: It is a circular area which is based on node n_i as the center of the circle and the size of its radius is r.

Dormant node n_d: Which node in dormant area.

In Fig. 1, the dormant radius of node n_i is r, the dormant area S is the shaded area of the circle. Those dotted line nodes which in the dormant area are the dormant nodes. All nodes in the networks have their own dormant radius and own dormant area. The assumption by the protocol shows that all nodes (except the base station) are the same. And we also assume that each node has the same radius at the beginning of the network. The setting of the dormant radius depends on the characteristics of application of the wireless sensor network. When the radius becomes smaller, there is not any dormant node. This moment r =r_min, we call it the minimum dormant radius. When the radius becomes larger, all of the nodes in the current cluster become dormant nodes, at this time r =r_max and we call it the maximum dormant radius.

Fig. 1:	Distribute of a cluster, r is the dormant radius of ni, at Ti, there nodes of dormant area S from ni will be into sleep

Degree control mechanisms in cluster: After the initialization phase of the network, the base station calculates the node degree controls of every cluster. Here, the node degree control is only discussed in one cluster and the operation principles of other cluster are the same.

Let the current cluster is Cluster0, the cluster head is CH₀, C₀ = {CH₀, n₁, n₂, …n_m} stands for the set of m+1 nodes in the current cluster. And let D_i = {d_i|0≤d_i≤m'}denote the set of dormant nodes of the node n_i, in which m' is the number of dormant nodes in the dormant area of the node n_i. The base station uniformly makes the set of dormant nodes of every node at the initialization phase in the network. Let D_clustero is the set of dormant node of cluster Cluster0. The set of normal nodes in the cluster is N_Cluster0. The algorithm process of the node degree control is as follows:

Step 1:	Get cluster head node CH0 from set C0 and get the set of dormant nodes of CH0, name DCH
Step 2:	:Check whether all nodes in the set DCH are traversed completely, if yes, go to Step 4, if not, go to Step 3. Until all nodes in the set are traversed completely
Step 3:	Get a node n'j from set DCH0, if n'jεC0, put n'j into set DCluster0 and , C0 = C0\n'j. If n'j∉C0, the operation goes to Step 2, at the same time, set C0 = C0\CH0
Step 4:	Check whether the traversal for all nodes of the set C0 is completed. If yes, go to Step 6; if not, go to Step 5. Until all nodes in the set Co are traversed completely
Step 5:	Get the node ni from the set C0, if ni is in set DCluster0, the operation goes to Step 2; if not, put the node ni into set DCluster0, at the same time, make ,
Step 6:	The operation calculates the size of set NCluster0 and set DCluster0 and then, makes a TDMA schedule for the nodes in the cluster based on the rules of the node degree control and broadcasts the TDMA schedule to the cluster. Other nodes will go to the steady-state phase after received the message

The rules of the node degree control are as follow: all of the nodes in set N_Cluster0 will send data to its cluster head node CH_o at time T_i but the nodes in set D_Cluster0 will take turns to sent data to the cluster head CH_o. For example: in the dormant area of Fig. 1, n_i and another three dormant nodes will take turns to be woken up by the TDMA schedule, then, gather and send data to the cluster head CH_o.

Algorithm description: According to the characteristics of the clustering routing, CEDCAP protocol is divided into four phases: cluster head selection phase, cluster formation phase, node degree control phase and data transmission phase.

Cluster head selection phase: At the phase, each node sends the message which includes its geographical location information and the current residual energy to the base station, the base station calculates the average energy E_average of all nodes based on all messages. If the current residual energy of one node is less than the E_average, it cannot be the alternate cluster head for current round, next, using the remaining nodes as possible cluster heads, the base station computes clusters using the simulated annealing algorithm to find the optimal clusters. This algorithm attempts to minimize the amount for energy for the non-cluster head nodes to transmit their data to the cluster head, by minimizing the total sum of squared distances between all the cluster member nodes and closest cluster head.

Cluster formation phase: Once the cluster heads CH_i (0≤i≤k) are found, the base station broadcasts the message that contains the cluster heads set for each node to the whole network. If a node’s cluster head ID matches its own node ID, the node is a cluster head.

Node degree control phase: After the cluster formation phase, the base station computes a TDMA based on the node degree control between all of nodes in each cluster and sends to the network. Then the node determines its TDMA slot for data transmission and goes to sleep until it is time to gather and send data. The TDMA also provides: in one round, only one node which be included in a dormant area can send data to its cluster head. The others go to sleep and they will be woken up in turn to gather and send data to the cluster head in the next cycles.

Data transmission phase: Once the clusters are created and the TDMA schedule is fixed by node degree control, data transmission can start. The radio of each non-cluster-head node which must be dormant area can be turned off until the node’s allocated transmission time, thus minimizing energy dissipation in these nodes. The cluster head must keep its receiver on to receive all data from the sending nodes in its cluster. When all the data has been received, the cluster head performs data aggregation functions to compress the data into only one single packet. This packet is sent to the base station by the cluster head.

After a certain time, the operation will perform the four phases again so that can achieve the energy dissipation balance between all nodes in the network.

PROTOCOL EVALUATION

Significance of dormant area: Estrin (2002) described the energy consumption of node subsystems and shown in Fig. 2, it can be seen that the most of the energy consumption is generated by the communication module of the node.

And according to the analysis by the communication model of network, transmission distance plays a significant impact on the energy consumption of nodes. Thus, as long as the node in working state, the energy consumption is relatively large. In order to prolong the lifetime of the node, without compromising the network monitoring application, we should try to let the node keep sleep state. To make the energy load balance in the lifetime, we also need to ensure that each node at the same energy dissipation level in the network, so that prolong the lifetime of the entire network. All nodes are randomly deployed, node density is not to be known prior, so that some regions may lead to a larger density of nodes but some are small.

Fig. 2:	Sensor node energy consumption distribution

Fig. 3:	The impact of size of r to data collection from monitor area

By setting a certain amount of dormant area can guarantee that both to achieve the integrity of data collection and to make part of the node can be in sleep mode under a certain scope of monitoring, so that can greatly save the network energy.

Impact of dormant radius r for data collection: Assuming the network k clusters Cluster_i (0≤i≤k) are evenly distributed and the monitor area is divided equally between them as shown in Fig. 3:

•	When r≤rmax, there are not any dormant nodes in the dormant area S, as shown in left part of Fig. 3. Setting of dormant area for network will have no affect under this scenario; CEDCAP will be the same as the LEACH
•	When r≤rmax, the dormant area S of cluster head will cover the other cluster, as shown in right of Fig. 3. At this time, there will be a small number of nodes in the network gathering data and sending data to the base station. The accuracy of data monitoring will be biased. Especially for the event-driven monitoring application, since the dormant node may be in the region where the events happened. Then, if the node is dominating, it will miss the best time to listen the event; this will reduce the suitability of the protocol
•	When rmin<r<rmax, the network dormant area will be located in the cluster, so that can ensure that part of the nodes effectively go to sleep. In this case, the number of monitoring nodes will not be too small, thus, the data which be aggregated by cluster head will be objective and accurate

Impact of dormant radius r for average energy consumption per round:

•	When r≤rmax, the average energy consumption per round in CEDCAP will be maximum and will be the same as LEACH
•	When r≤rmax, the average energy consumption per round in CEDCAP will be minimum, at this point, there are only a small number of nodes in the network keeping work, therefore, the minimum energy will be consumed in the entire network
•	When rmin<r<rmax, , the network energy consumption will be more evenly, CEDCAP will play a significant role in data gathering. When running to a certain round, the number of dormant nodes is n', the size of every data packet is l, the energy consumption of cluster head is:

And the energy savings by non-cluster-head nodes is:

Time complexity of cedcap: Let m+1 denotes the number of nodes in cluster Cluster_i and the set is expressed as . Assume the m'_j denotes dormant nodes of the node j.

Let time complexity is denoted by the number of traversing the nodes:

By the analysis of Heinzelman et al. (2000) LEACH, Let where, N denotes the total number of the nodes in network.

So the time complexity of the whole process is as follow:

The minimum of time complexity is O (N.m') which less than O (N²).

PERFORMANCE EVALUATION

Simulation environment: In order to evaluate the performance of our protocol, we simulated two different routing protocols (LEACH and our protocol CEDCAP) by NS-2 simulator. We did this project in 2011 between January and February and completed this project under the guidance of Professor Wang in control theory laboratory.

This simulation environment is the same as LEACH, in order to see the level of energy savings that our protocols can achieve.100 sensor nodes are randomly distributed over the region of 100x100 m as shown in Fig. 4. The base station is located far away from the region, at point (50,175).

Fig. 4:	100 nodes random sensor network

Table 1:	Main parameters setting in simulation

Fig. 5:	The number of nodes alive over the simulation time

In these simulations, each node has only 2 J of energy at the beginning of experiments and an unlimited amount of data to send to the base station. When the nodes use up their limited energy power during the course of the experiment, they can close their models and never transmit or receive data. And the main parameters setting in simulation are shown in Table 1.

Network lifetime: In wireless sensor networks, the network lifetime mainly concerns the time of the first died node and time of the last died node in whole network runtime. In this simulation, we are also concerned about these two parameters. The simulation results are shown in Fig. 5.

Figure 5 shows the total number of nodes that remain alive over the simulation time. While nodes remain alive from a long time in CEDCAP, this is because a much smaller number of cluster member nodes have to be woken up to work with the cluster head and much more nodes can be off to save the energy. As can clearly be seen from Fig. 5, the time of the first died node and the last died node in CEDCAP is much longer than LEACH. CEDCAP’s lifetime is approximately 30% longer than LEACH.

Network energy balance: The network energy balance mainly considers the total energy consumption of each round. Figure 6 shows the simulation results for network energy balance.

In Fig. 6, we can see the total energy dissipated using LEACH and CEDCAP over the simulation time in the same network. This figure shows the more energy savings achieved using CEDCAP for most of the parameter space. The variation trend of CEDCAP is smoother than LEACH. In addition to reducing energy consumption, CEDCAP minimum the number of the cluster member nodes which need not to keep working. Compared with LEACH, it makes the network more uniform energy consumption.

Fig. 6:	Simulation results of energy consumption