Abstract: In Wireless Sensor Networks (WSNs), since the network consists of low-cost sensor nodes with finite battery power, power efficient strategies must be applied for data transmission in order to prolong the network lifetime. It is important to minimize the total energy consumption in each round so that the network lifetime is maximized. In this study, we have proposed a new energy efficient protocol, named CTPEDCA (Cluster-Based and Tree-Based Power Efficient Data Collection and Aggregation Protocol for WSNs), which using the full distributed in hierarchical WSNs. CTPEDCA is based on clustering and Minimum Spanning Tree (MST) routing strategy for cluster heads. We use the MST to improve the transmission routing mechanism between the cluster heads so that let only one cluster head communicate directly with the faraway base station in each round. The simulation results show that CTPEDCA is better 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, therefore, the time complexity is small.
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)