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 (d2 power loss) and
the multipath fading (d4 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
do;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, Eelec indicates the electronics energy which depends on factors such as the digital coding, modulation, filtering and spreading of the signal. εfs.d2 or εmp.d4 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: Eelec = 50 nj/bit, εfs = 10 pj/bit/m2, εmp = 0.0013 pj/bit/m4, the energy for data aggregation is set as EDA = 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 ni has a dormant radius
r, during the network operation time Ti, within coverage area of
node ni which radius is r, the rest of the nodes in time Ti
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 ni as the center of the circle and the size of its radius is r.
Dormant node nd: Which node in dormant area.
In Fig. 1, the dormant radius of node ni 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 =rmin, 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 =rmax 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 CH0, C0
= {CH0, n1, n2, …nm} stands
for the set of m+1 nodes in the current cluster. And let Di = {di|0≤di≤m'}denote
the set of dormant nodes of the node ni, in which m' is the number
of dormant nodes in the dormant area of the node ni. The base station
uniformly makes the set of dormant nodes of every node at the initialization
phase in the network. Let Dclustero is the set of dormant node of
cluster Cluster0. The set of normal nodes in the cluster is NCluster0.
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 NCluster0 will send data to its cluster head node CHo at time Ti but the nodes in set DCluster0 will take turns to sent data to the cluster head CHo. For example: in the dormant area of Fig. 1, ni 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 CHo.
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 Eaverage
of all nodes based on all messages. If the current residual energy 
of
one node is less than the Eaverage, 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 CHi (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 Clusteri (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
Clusteri 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 (N2).
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 |
CONCLUSION
In this study, a novel cluster-based energy-efficient data collecting and aggregation protocol, called CEDCAP, has been presented which based on clustering; CEDCAP divides a round into four phases: Cluster head selection phase, Cluster formation phase, Node degree control phase, Data transmission phase. At node degree control phase, we employ the node degree control mechanism to minimum the waking node to gather and send data to its cluster head. It is different from LEACH; in CEDCAP, there are only a few part of cluster member nodes to work together with the cluster head in each cluster, dormant nodes keep off-duty until they are woken up in next transmission slot. Thus, CEDCAP can significantly reduce the total energy consumption between all cluster member nodes and make the energy consumption of all nodes more evenly. By the NS-2 simulations, the results show that CEDCAP achieves better performances than LEACH. CEDCAP can more balance the energy consumption of all nodes and prolong the lifetime of the networks.
ACKNOWLEDGMENTS
This work is supported by two grants from the National Natural Science Foundation of China (No. 60773190, No. 60802002).
Subscribe Today
