An energy efficient protocol with static clustering for wsn

An energy efficient protocol with static clustering for wsn

• 1.
  World Academy ofScience, Engineering and Technology 28 2007 An Energy-Efficient Protocol with Static Clustering for Wireless Sensor Networks Amir Sepasi Zahmati, Bahman Abolhassani, Ali Asghar Beheshti Shirazi, and Ali Shojaee Bakhtiari typical deployment of large number of sensor nodes, have Abstract—A wireless sensor network with a large number of tiny posed many challenges to the design and management of sensor nodes can be used as an effective tool for gathering data in sensor networks and necessitate energy-awareness at all layers various situations. One of the major issues in wireless sensor of networking protocol stack [2], [3]. networks is developing an energy-efficient routing protocol which In this paper we assume a sensor network model, similar to has a significant impact on the overall lifetime of the sensor network. In this paper, we propose a novel hierarchical with static clustering those used in [4]–[6], with the following properties: routing protocol called Energy-Efficient Protocol with Static • All sensor nodes are immobile and homogeneous Clustering (EEPSC). EEPSC, partitions the network into static with a limited stored energy. clusters, eliminates the overhead of dynamic clustering and utilizes • The nodes are equipped with power control temporary-cluster-heads to distribute the energy load among high- capabilities to vary their transmitted power. power sensor nodes; thus extends network lifetime. We have conducted simulation-based evaluations to compare the performance • None of the nodes know their location in the of EEPSC against Low-Energy Adaptive Clustering Hierarchy network. (LEACH). Our experiment results show that EEPSC outperforms • Each node senses the environment at a fixed rate LEACH in terms of network lifetime and power consumption and always has data to send to the base station. minimization. • Base station is fixed and not located between sensor nodes. Keywords—Clustering methods, energy efficiency, routing In this paper, we propose EEPSC (Energy-Efficient protocol, wireless sensor networks. Protocol with Static Clustering), a hierarchical static I. INTRODUCTION clustering based protocol, which eliminates the overhead of dynamic clustering and engages high power sensor nodes for A wireless sensor network is a collection of sensor nodes interconnected by wireless communication channels. Each sensor node is a small device that can collect data from power consuming tasks and as a result prolongs the network lifetime. In each cluster, EEPSC chooses the sensor node with maximum energy as the cluster-head (CH); thus, not only its surrounding area, carry out simple computations, and there is always one CH for each cluster, but also the overhead communicate with other sensors or with the base station (BS). of dynamic clustering is removed. EEPSC is a modified Such networks have been realized due to recent advances in version of the Low-Energy Adaptive Clustering Hierarchy micro electromechanical systems and are expected to be (LEACH) protocol presented in [7]. widely used for applications such as environment monitoring, LEACH uses the paradigm of data fusion to reduce the home security, and earthquake warning [1]. amount of data transmitted between sensor nodes and the base Despite the infinite scopes of wireless sensor networks, station. Data fusion combines one or more data packets from they are limited by the node battery lifetime. Once they are different sensors in a cluster to produce a single packet. It deployed, the network can keep operating while the battery selects a small number of CHs by a random scheme which power is adequate. This is critical point to be considered as it collects and fuses data from sensor nodes and transmits the is almost impossible to replace the node battery once deployed result to the base station. LEACH uses randomization to rotate over an inaccessible area. Such constraints combined with a the CHs and achieves a factor of 8 improvement compared to the direct approach before the first node dies [7]. Manuscript received May 6, 2007. This work was supported in part by Iran Telecommunication Research Center (ITRC). The main difference between EEPSC and LEACH are A. Sepasi Zahmati is the MSc student of Department of Electrical described below: Engineering, Iran University of Science and Technology, Tehran, Iran (e-mail: • EEPSC benefits a new idea of using temporary- amir_sepasizahmati@ee.iust.ac.ir). B. Abolhassani is the Assistant Professor of the school of Electrical CHs and utilizes a new setup and responsible node Engineering, Iran University of Science and Technology, Tehran, Iran (e-mail: selection phase. abolhassani@iust.ac.ir). • EEPSC utilizes static clustering scheme, therefore A. A. Beheshti Shirazi is the Assistant Professor of the school of Electrical Engineering, Iran University of science and Technology, Tehran, Iran (e-mail: eliminates the overhead of dynamic clustering. abeheshti@iust.ac.ir). The rest of the paper is organized as follows. Section II A. Shojaee Bakhtiari is the MSc from Iran University of Science and describes the proposed method. In Section III simulation Technology, Iran (email: ali_shojaeebakhtiari@iust.ac.ir). 69
• 2.
  World Academy ofScience, Engineering and Technology 28 2007 results are presented, and finally the conclusions are presented next phase can begin. in section IV. B. Responsible Node Selection Phase II. EEPSC PROTOCOL ARCHITECTURE After the clusters are established, network starts its normal operation and responsible nodes (temporary-CH and CH) EEPSC is a self-organizing, static clustering method that selection phase begins. At the beginning of each round, every forms clusters only once during the network action. The node sends its energy level to the temporary-CH in it’s time operation of EEPSC is broken up into rounds, where each slot. Afterward, temporary-CH choose the sensor node with round consists set-up phase, responsible node selection phase utmost energy level as CH for current round to collect the data and steady-state phase. In the following sub-sections we of sensor nodes of that cluster, perform local data aggregation, discuss each of these phases in details. and communicate with the base station; and the node with A. Setup Phase lowest energy level as temporary-CH for next round and sends According to the static clustering scheme which is used in a round-start packet including the new responsible sensor IDs EEPSC, cluster formation is performed only once at the for the current round. This packet also indicates the beginning beginning of network operation. For this aim, base station of round to other sensor nodes. Since every sensor node has a broadcasts k-1 different messages with different transmission pre-specified time slot, changing the CHs has no effect on the powers, which k is the desired number of clusters (specified a schedule of the cluster operation. priori). By broadcasting the k=1 message all the sensor nodes C. Steady-State Phase which hear this message (are in the radio range of this The steady-state phase is broken into frames where nodes message) set their cluster ID to k and inform the base station send their data to the CH during pre-allocated time slots. that they are member of the cluster k via transmitting a join- These data contain node ID and the measure of sensed request message (Join-REQ) back to the base station. parameter. We show in the next section that the total energy Similarly, by broadcasting the k=k-1 message, all the sensor expended in the system is greater using multi-hop routing than nodes which are not joined to any clusters yet and hear this direct transmission to the base station; thus, we use direct message set their cluster ID to k-1 and inform base station transmission approach among CH and base station. with a Join-REQ message. Later, all sensor nodes which are The duration of each slot in which a node transmits data is not joined to any clusters set their cluster ID to k and inform constant, so the time to send a frame of data depends on the base station. Fig. 1 shows how the network area is divided number of nodes in the cluster. into k=4 clusters with broadcasting k-1=3 different messages To reduce energy dissipation, the radio of each non-cluster from base station. head node is turned off until its allocated transmission time, but the CHs must be awake to receive all the data from nodes in the cluster. III. SIMULATION RESULTS To validate the performance of EEPSC, we simulate EEPSC and utilize a network with 100 nodes randomly deployed between (x=0, y=0) and (x=100, y=100) and base station at (50,175). The bandwidth of channel is set to 1 Mb/s, each data message is 500 bytes long, and the packet header for Fig. 1 Network area is divided into 4 clusters with broadcasting 3 each type of packet is 25 bytes long. The initial power of all different messages from base station nodes is considered to be 2J and duration of each round is 20s. Authors in [7] has revealed analytically that the number of These messages are small messages containing node’s IDs clusters for above assumptions is optimized for 1 < k < 6. So and a header that distinguishes them as announcement for the rest of the experiment, we set k=4. messages. Like LEACH, in order to reduce the probability of We assume a simple model for the radio hardware energy collision among joint-REQ messages during the setup phase, dissipation where the transmitter dissipates energy to run the CSMA (Carrier Sense Multiple Access) is utilized as the radio electronics and the power amplifier, and the receiver MAC layer protocol [7]. dissipates energy to run the radio electronics [7, 8], as shown Afterward, the base station selects randomly one in Fig. 2. For the experiments described here, both the free temporary-CH for each cluster and advertises these rules to space (d2 power loss) and the multi path fading (d4 power the whole network. In addition, base station (based on the loss) channel models were used, depending on the distance number of each cluster) sets up a TDMA (time-division between the transmitter and receiver. If the distance is less multiple-access) schedule and transmits this schedule to the than a threshold, the free space (fs) model is used; otherwise, nodes in each cluster. Once the TDMA schedule is known by the multi path (mp) model is used. Thus, to transmit an l-bit all nodes in the cluster, the set-up phase is complete and the message a distance d, the radio expends: 70
• 3.
  World Academy ofScience, Engineering and Technology 28 2007 d ETx (l, d) ERx (l) l bit packet l bit packet Transmit Tx Amplifier Receive Electronics Electronics Eelec × l εamp × l × dn Eelec × l Fig. 2 Radio energy dissipation model E TX (l , d ) = E TX − elec (l ) + E TX − amp (l , d ) and Equations 1 and 3, we have: ⎧lE elec + l ε fs d , 2 d < do (1) ⎪ n −1 =⎨ E TX = l ε fs − amp ( r ) 2 + lE elec (4) ⎪lE elec + lε mp d , d > do 4 ⎩ β Where d o is: Where β is the number of hops. Thus, the total energy is: E tot = β E TX + β E RX ε fs (2) do = ( n − 1) 2 r 2 (5) ε = 2 l β E elec + l ε friss − amp β mp The electronics energy (Eelec) depends on factors such as the And the optimum number of hops is computed as below: digital coding, modulation, filtering, and spreading of the signal, whereas the amplifier energy, εfsd2 or εmpd4, depends dE tot d2 on the distance to the receiver and the acceptable bit-error = 2 lE elec − l ε friss − amp 2 = 0 rate. For the experiments described in this paper, the dβ β opt (6) communication energy parameters are set as: Eelec=50nJ/bit, ε friss − amp d εfs=10pJ/bit/m2, εmp=0.0013pJ/bit/m4 and the energy for data ⇒ β opt = d = 2 E elec 100 aggregation is set as EDA=5nJ/bit/signal. As well, to receive an l-bit message, the radio expends: This shows that, when transmission energy is on the same order as receive energy, which occurs when transmission E RX ( l ) = E RX − elec ( l ) = lE elec (3) distance is short, direct transmission is more energy-efficient than multi-hop routing. Thus we use direct transmission CHs can send their data via just one (high-energy) transmit communication among CHs and the base station. of data to the base station or via a multi-hop scheme where The improvement gained through EEPSC compared to each data message must go through n (low energy) transmits LEACH is further illustrated by Figs. 4-7 which indicates the and n receives. Depending on the relative costs of the transmit lifetime of network is extended and the overall number of amplifier and the radio electronics, the total energy expended messages received at base station is increased. With LEACH, in the system might actually be greater using multi-hop all nodes remain alive for 220 seconds before the first node routing than direct transmission to the base station. dies, while in EEPSC, all nodes remain alive for 320 seconds; which is 45% more than LEACH. Figs. 3 and 4 show that, the total number of data messages received at base station at the end of network lifetime is greater for EEPSC. Furthermore, Figs. 5 and 6 clearly indicate the advantages of EEPSC over LEACH in terms of network lifetime. Fig. 3 Simple linear network IV. CONCLUSION AND FUTURE WORK We introduce EEPSC; a novel energy-efficient routing To illustrate this point, consider the linear network shown protocol which partitions the network into static clusters, in Fig. 3, where the distance between the nodes is r. If we eliminates the overhead of dynamic clustering and utilizes consider the energy expended transmitting a single l-bit temporary-cluster-heads (CHs) to distribute the energy load message from a node located a distance nr from the base among high power sensor nodes; thus extends network station using the direct communication approach via one hop 71
• 4.
  World Academy ofScience, Engineering and Technology 28 2007 Fig. 4 Number of data messages received at base station over time Fig. 5 Number of data messages received at base station over energy Fig. 6 Number of nodes alive over time Fig. 7 Number of nodes alive per amount of data messages received at base station lifetime. The energy efficiency and ease of deployment make [3] J. N. Al-Karaki and A. E. Kamal, “Routing Techniques in Wireless Sensor Networks: A Survey”, IEEE Wireless Communications, vol. 11, EEPSC a desirable and robust protocol for wireless sensor no. 6, Dec 2004. networks. Simulation results show that EEPSC has a better [4] W. R. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, “Energy- performance than LEACH. For future work, a model with Efficient Communication Protocol for Wireless Microsensor Networks,” Proc. 33rd Hawaii Int’l. Conf. Sys. Sci., Jan. 2000. heterogeneous sensor nodes may be investigated. [5] S. Lindsey, C. Raghavendra, and K. M. Sivalingam, “Data Gathering Algorithms in Sensor Networks using Energy Metrics,” IEEE Trans. ACKNOWLEDGMENT Parallel and Distrib. Sys., vol. 13, no. 9, Sept. 2002, pp. 924–35. [6] Amir Sepasi Zahmati and Bahman Abolhassani, “EPMPLCS: An The authors would like to express their sincere thanks to the Efficient Power Management Protocol with Limited Cluster Size for Iran Telecommunication Research Center (ITRC) for Wireless Sensor Networks”, Proc. 27th International Conference on supporting this work. Distributed Computing Systems (ICDCS 2007), submitted for publication. [7] W. B. Heinzelman, A .Chandrakasan, and H. Balakrishanan, “An REFERENCES Application-Specific Protocol Architecture for Wireless Microsensor [1] F. Zhao and L. Guibas, “Wireless Sensor Networks: An Information Networks”,IEEE Trans. Wireless Commun., vol. 1, no. 4, Oct. 2002, pp. Processing Approach (Morgan Kaufmann Series in Networking).” San 660-70. Mateo, CA: Morgan Kaufmann, 2004. [8] T. Rappaport, Wireless Communications: Principles & [2] Q. Xue, A. Ganz, “Maximizing Sensor Network Lifetime: Analysis and Practice.Englewood Cliffs, NJ: Prentice-Hall, 1996. Design Guides”, in Proceedings of MILCOM, October 2004. 72