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. They have a wide range of applications, from civil to
military, that may be realized by using different type of sensor devices with
different capabilities for different kinds of environments (Akyildiz
et al., 2002). The server constraint of sensor nodes is their low
finite battery energy, which limits the lifetime and the quality of the network.
Since, wireless communications consume significant amounts of battery power,
it is necessary to ensure that sensors should spend as little battery power
as possible sending and receiving data. For this reason, the route protocols
running on sensor networks should consume the resources of the sensors efficiently
in order to prolong the network lifetime. When power efficient communication
is considered, it is very important to maximize the lifetime of all nodes, reduce
bandwidth consumption by using local collaboration among the nodes and tolerate
node failures, besides delivering the data efficiently.
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; Chang and Tassiulas, 2000; Jiageng
et al., 2005) for wireless sensor networks, There are also different
protocols proposed in the literature (Xue et al.,
2005; Chang and Tassiulas, 2004; Tan
and Ibrahim, 2003; Lee et al., 2010) to maximize
the lifetime of the system under different circumstances, (Bhardwaj
et al., 2001) give the upper bounds on the lifetime of sensor networks.
Tan et al. (2009), HCEP measures the load distribution
among nodes by using clustering as a key communication control technique.
Since, a large number of nodes distributed in a large monitoring area, individual
nodes data are often correlated in the network, the end-user does not require
all the data, some of them are redundant, data generated in the sensor network
is too much for the end-user to process, functions for combining data into a
small set of useful information is required. A practical way of doing that is
aggregating (min, max, sum, count, average) the data originating from different
nodes in the correlated area. Heinzelman et al. (2000),
they proposed a more elegant solution which is data fusion which can be defined
as combination of several unreliable data measurements to produce a more accurate
signal by enhancing the common signal. There are many different protocols (Heinzelman
et al., 2000; Tan and Ibrahim, 2003; Lindsey
and Raghavendra, 2002) used these approaches. In particular, because of
the fact that they improve the performance of the wireless sensor network in
an order of magnitude by reducing the amount of data transmitted in the network,
in this way, it may save a lot of energy consumption required for transmitting
those data.
There are several classic protocols (Heinzelman et al.,
2000, 2002; Lindsey and Raghavendra,
2002; Tan and Ibrahim, 2003; Younis
and Fahmy, 2004; Intanagonwiwat et al., 2003)
proposed for wireless sensor netwoks, in order to reduce the energy consumption
of sending data to the base station where is far away and avoid the sensor nodes
die quickly. Heinzelman et al. (2000), called
LEACH, its main idea is to reduce the number of sensor nodes sending data directly
to the base station. The protocol achieves this by generating a small number
of clusters by way of self-organization, where each cluster-head collects the
data from its cluster members, then, fuses and sends the result messages to
the base station. LEACH also uses randomization to select cluster-head in each
round and achieves to evenly distribute the energy load among all the nodes
in the network so that there are no overly-utilized nodes that will run out
of energy before the others. Compared with the Leach, by 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 Ibrahim (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. Lindsey and Raghavendra (2002) and Tan
and Ibrahim (2003), these algorithms by the base station control is not
fully distributed and their adaptability is not very strong.
In this study, we proposed a new cluster-based and minimum spanning tree-based protocol called CTPEDCA (Cluster-Based and Tree-Based Power Efficient Data Collection and Aggregation Protocol). In CTPEDCA, the main target is to design a mechanism for data transmission between the cluster heads based on clustering, so that balance the energy consumption of all nodes and prolong the lifetime of the entire network, namely, prolong the lifetime of the last node in the system while providing a good lifetime for the first node.
SYSTEM MODEL AND PROBLEM ANALYSIS
The network model: There are various models for sensor networks. In this study we mainly consider a wireless sensor network consisting of a set of sensors and a Base Station (BS) that 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, we assume 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, we 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
d0; otherwise, the multipath (mp) model will be used. Therefore,
when we want to transmit 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 zrate. 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.
Problem statement and analysis: In this study, main consideration is that we use the fully distributed strategy in our network model and donot require the central control from the base station. We have seriously studied LEACH, PEGASIS and PEDAP and proposed our protocol after analyzing their problem and their design ideas. Our goal is to design a mechanism for data transmission between the cluster heads, based on clustering and tree routing; therefore, it can balance the energy consumption of all nodes and prolong the lifetime of the entire network.
In LEACH, the number of cluster heads generated by algorithm is not fixed and
donot distribute evenly, this conclusion can be drawn by NS2 simulation as shown
in Fig. 1. LEACH is simulated many times and then selects
the two representatives. From Fig. 1 we can see that the least
number of cluster heads is 1, the largest reached 27. This led the result: the
number of cluster heads sending directly data to the base station is not optimal
and the energy balance is not optimal. In PEGASIS, it form a chain to take turns
to send data in each round, there is only one node to send resultant data directly
to the far base station. And in PEDAP, they generate a routing tree, where base
station as the root, by constructing minimum energy consuming routing in each
round, in the final, there is very few nodes to send resultant data to the base
station.
|
| Fig. 1: | In
a 100-nodes random sensor network, number of cluster-heads generated in
each round |
Therefore, compared with LEACH, PEGASIS and PEDAP can balance the energy consumption
of the nodes and prolong the lifetime of the networks.
From the above analysis, in our algorithm, we optimize the number of nodes which directly sending data to the base station, let only one node communicate to the base station. We assume that the network has k cluster head nodes. In accordance with the radio model analysis, there is only one node using the mulitpath fading channel models, while the other k-1 cluster heads using the free space channel models, thus, the total energy consumption from all cluster heads has been significantly reduced. But in LEACH, the kcluster heads using the mulitpath fading channel models to send data directly to the base station.
However, what mechanism can be used to make cluster head nodes transmit data sequentially and let only one cluster head send resultant data directly to the base station? Figure 2 shows the solution to this problem. Let, all cluster heads in a round as the object of study, For the convenience, we only mark the cluster head nodes in the Fig. 2 and give them random numbers (No. 1 to 9) and simply simulate their spatial distribution. And let them generate a routing tree by minimum spanning tree algorithm, the cluster heads receive and send data in accordance with the order of tree, at the same time each node performs data aggregation, finally, the tree’s root node send the resultant data to the base station. In Fig. 2: No. 1 and 2 send their resultant data to No. 3, 3 fuses its data and sends to No. 5, according to this mechanism, No. 6 receives data from No. 5 and 7, fuses all data, then, sends the result to the base station. Therefore, it can achieve the balance the energy consumption of the cluster heads.
|
| Fig. 2: | Minimum
spanning tree based routing scheme between the cluster-heads in a clustering
network |
PROTOCOL DESCRIPTION
Our protocol is a fully distributed algorithm which does not require any calculation of the base station. First of all, we made some assumptions about the sensor nodes and the underlying network model. For the nodes of the network, these assumptions as follow:
| • | All
the nodes know their location information |
| • | The
transmit power range of the nodes can cover the entire network and all
nodes can transmit with enough power to reach the base station if needed,
that the sensor nodes can use power control to change the amount of transmit
power and that each node has the computational power to support different
MAC protocols and perform signal processing functions |
| • | Using
fully data fusion approach in the network |
We use similar clustering algorithm with LEACH to form k cluster heads, but compared with LEACH, we improve transmission routing mechanism between the cluster heads by minimum spanning tree method, only root node sends resultant data to the base station. A flowchart of this algorithm is shown in Fig. 3.
The whole process is divided into four phases during each round: Cluster head selection phase, Cluster formation phase, Tree formation of cluster heads phase, Data transmission phase.
Cluster head selection phase: In this phase, the cluster head selection
algorithms is the same as LEACH, it forms clusters by using the distributed
algorithm, where all of nodes make autonomous decisions without any centralized
control from the base station. We divide the networks into a certain number
of clusters, k, during each round, in other words, we will select k cluster
heads, they are responsible for receiving the data from the other nodes in local
cluster and perform data aggregation for the received data, then, send the resultant
data.
|
| Fig. 3: | Flowchart
of the distributed algorithm for CTPEDCA |
In order to evenly distribute the energy load among all the sensor nodes in
the network, our algorithm make a strategy that each node takes its turn as
cluster head, to ensure that all nodes die at approximately the same time. However,
there are many improved algorithms in this phase, some of them consider the
residual energy in electing cluster head, the others consider the transmission
distance or node degree, such as (Younis and Fahmy, 2004;
Handy et al., 2002) and so on. This study can
be applied to their improvement, but for general purposes, we use the same selection
algorithms with LEACH.
Cluster formation phase: The algorithm of this phase is also the same
as LEACH, each cluster head node broadcasts an ADV(advertisement message) using
CSMA (Carrier Sense Multiple Access), each non-cluster head node has to determine
its cluster for the current round by choosing the cluster head that requires
the minimum communication energy, that based on the received signal strength
of the advertisement from each cluster head. After each node has decided to
which cluster it belongs, each non-cluster head transmits a join-request message
back to the chosen cluster head using CSMA. Then, the cluster heads act as local
administrator to coordinate the data transmissions in local cluster, they set
up, respectively, a TDMA (Time Division Multiple Address) schedule and transmit
their own schedule to the member nodes in the cluster. Finally, the non-cluster
head nodes receive the schedule message. This process can be seen from the upper
half of the Fig. 3 (self is CH0). At this point,
the cluster formation phase is complete. So far, there are several improved
algorithms in the same phase. Cluster size, energy balance and number of nodes
in cluster are considered in those algorithms, such as Chan
and Tassiulas (2004) and so on.
Tree formation of cluster heads phase: After cluster formation, the cluster heads broadcast its ADV, where containing the cluster head’s ID, location information, cluster’s ID, cluster size(number of nodes in local cluster), residual energy and so on. Then, each cluster head can also receive and save them, finally, every cluster head can get a table message containing all of the cluster heads. Over to the next, we select a cluster head (denoted by CH0), which with maximum residual energy, to implement the remaining algorithms, this can be achieved to evenly distribute the energy load among all the nodes in the network. Our work is to create a minimum spanning tree among all the cluster heads to achieve the goal, in which k-1 cluster heads use free space channel models to send data and only one cluster head uses the multipath fading channel models to transmit data to the base station. We call the local algorithm CH_MST, it works as follows: Firstly, put CH0 (which implement the CH_MST) in the tree, after that, In each iteration we select the minimum weighted edge from a vertex in the tree to another vertex not in the tree, at the same time add this edge to the tree, cluster heads will send its data through these edges. We repeat this function until all cluster head are added to the tree. Finally, CH0 broadcasts the Tree Information Message (TIM) to the other cluster heads, the TIM is again a short message; it also contains a schedule for data transmission among the cluster heads. As shown in Fig. 3, the process can be seen after section self is CH0.
Data transmission phase: The data transmission operation is also broken
into frames, where non-cluster nodes send their data to their cluster head at
most once per frame during a allocated transmission slot, in which nodes can
transmit their data without collisions in the network. We assume that the nodes
are all time synchronized by having the base station send out synchronization
pulses to the nodes (Heinzelman et al., 2002).
In order to reduce energy dissipation, each non-cluster head node uses power
control to send data, furthermore, the radio of them are turned off until their
allocated transmission slot. The cluster heads will be awake to collect all
the data from the nodes in local cluster. Once they receive all the data from
local non-cluster head nodes, it performs data aggregation to generate a useful
data packet. After all the cluster heads complete the data collection of the
local cluster, they will transfer their resultant data along the tree (formed
by tree formation of cluster heads phase) and each receiver will sent its result
data after performing data aggregation for local resultant data and data received
from sender (the previous cluster head in the tree).The root node of the tree
sends the final resultant data to the base station. The resulting routing paths
are illustrated for the network in Fig. 2.
Algorithm pseudo code about CH_MST is analyzed below:
In the network, at time t,the topology described as an undirected graph G(t) = (V,E(t)), where, V is the set of cluster-heads, E(t) is the set of logical links which only contain the cluster-heads at time t. Given any u,v∈V, edge (u,v)∈E(t) if and only if v is in the transmitting range of u at time.
PROTOCOL EVALUATION
Time complexity of CTPEDCA: Here, we only consider the time complexity of the CH_MST, the time complexities of the other phases are so simple that we can ignore them here. According to the principle of minimum spanning tree, we can conclude this: the time complexity of the minimum spanning tree algorithm between the cluster heads is O(ElogV), since V is the set of the cluster heads, the number of them is limited and small, the simulation result shows that the number of the cluster heads during each round distribution between 1 and 27, but the average number is five and the theoretical value is 5. Therefore, time complexity is small, the speed of the algorithm is very fast.
PERFORMANCE EVALUATION
In order to evaluate the performance of our protocol, we simulated two different routing protocols (LEACH and our protocol CTPEDCA) by NS-2 simulator. We did this project in 2010 between June and August 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 10x100 m as shown in Fig. 4. The base station is located far away from the region, at point (50,175).
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. For convenience sake, we assume that energy is consumed whenever a node transmits or receives data or performs data aggregation or performs CH_MST.
In Fig. 5, we can see the total number of nodes that remain
alive over the simulation time under our network model.
|
| Fig. 4: | 100
nodes random sensor network |
While nodes remain alive from a long time in CTPEDCA, this is because a much
smaller number of cluster heads has to communication with the base station,
only one cluster head uses the multipath fading channel models to send data
to the base station. As can clearly be seen from Fig. 5, In
LEACH, When the first node die, the network time is approximately 391, this
can be denoted by the equation: FND = 391. When the last node die, the network
time is approximately 538, this can be denoted by the equation: LND = 538. However,
in CTPEDCA, the result is: FND = 495 and LND = 662.
In Fig. 6, we can see the total energy dissipated using LEACH and CTPEDCA over the simulation time in the same network. Figure 6 shows the more energy savings achieved using CTPEDCA for most of the parameter space. We can also be seen from the figure the trend of the two curves are not smooth, this is because the number of cluster heads in each round of the network is not fixed, which affect the total energy consumption of the network.
|
| Fig. 5: | The
number of nodes alive over the simulation time |
|
| Fig. 6: | The
total system energy dissipated using LEACH and CTPEDCA over the simulation
time |
However, the variation trend of CTPEDC is smoother than LEACH. In addition to reducing energy consumption, CTPEDCA minimum the number of the cluster head nodes which need send data to the base station. Compared with LEACH, it makes the network more uniform energy consumption.
DISCUSSION
In this study, we propose a new power efficient data collection and aggregation protocol based on clustering and minimum spanning tree called CTPEDCA, which using the full distributed. CTPEDCA divides a round into four phases: Cluster head selection phase, Cluster formation phase, Tree formation of cluster heads phase, Data transmission phase. Compared with LEACH, We use the minimum spanning tree to improve the transmission routing mechanism between the cluster heads and divide the entire network into k clusters, k-1 of them using the multipath fading channel models to transmit data, only one cluster head using the multipath fading channel models to send data to the base station, so that we can achieve that significantly reduce the total energy consumption of all cluster heads and make the energy consumption of all nodes more evenly. By the NS-2 simulations, the results show that CTPEDCA achieves better performances than LEACH. CTPEDCA can more balance the energy consumption of all nodes, particularly as the cluster head nodes in each round and prolong the lifetime of the networks. It is worth to note that our algorithm is very fast, its time complexity is O(ElogV), where V is the set of cluster-heads, theoretical value is 5 in this study, therefore, time complexity is small.
The improvement from LEACH to LEACH-C can be seen, If in some special application environment where required the base station control, CTPEDCA can also be improved by the same way, it can prolong the network lifetime and improve energy efficiency. This is one of the elements for future research.
ACKNOWLEDGMENTS
This study is supported by two grants from the National Natural Science Foundation of China (No. 60773190, No. 60802002)
Subscribe Today
