Internet Engineering Task Force Jaehwa. Lee INTERNET DRAFT KT Advanced Technology Lab Choong Seon Hong Kyung Hee University Expires: April 2006 October 17, 2005 Prolonging Network Lifetime via Intra-Cluster Routing Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html This Internet-Draft will expire on April 17, 2006. Copyright Notice Copyright (C) The Internet Society (2005). Abstract An important challenge in wireless sensor network (WSN) is that how to route data packets from sources to base station energy efficiently. Inspiring data fusion feature and multi-hop routing, in this document, we introduce a clustering approach called PLIR (Prolonging Network Lifetime via Intra-Cluster Routing) for saving energy and distributing data dissipation evenly by improving BS cluster formation algorithm of LEACH-Centralized and providing 3-hop routing algorithm within clusters. Hence, it prolongs the lifetime of WSN. PLIR consumes less energy and reduces communication overhead, and extends the network lifetime compared with other approaches. Jaehwa Lee, et al. Expires April 17, 2006 [Page 1] Internet-Draft Prolonging Network Lifetime via October 17, 2005 Intra-Cluster Routing in WSNs Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2. Classification of Sensor Networks. . . . . . . . . . . . . . . 3 3. Sensor Network Model . . . . . . . .... . . . . . . . . . . . . . 4 4. Clustering Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 5. Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 6. Analysis and Conclusion. . . . . . . . . . . . . . . . . . . . . . 9 7. References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 8. Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 11 Jaehwa Lee, et al. Expires April 17, 2006 [Page 2] Internet-Draft Prolonging Network Lifetime via October 17, 2005 Intra-Cluster Routing in WSNs 1. Introduction In WSNs, where sensors are deployed densely in inhospitable environments, the proximate nodes will sense the identical data. Data aggregation from many of correlative data will reduce a large amount of data traffic on network, avoid information overload, produce a more accurate signal and require less energy than sending all the unprocessed data throughout the network. In various literatures, clustering approach is addressed as a routing method using the data aggregation feature effectively. The second version of protocol in [Heinzelman] called LEACH-Centralized shows a base station (BS) cluster formation approach but the communication between sensor nodes is one hop. This causes more interference to proximate sensor nodes and the energy dissipation is distributed unevenly. In addition, each node sends information about its current location and energy level to the BS during the cluster formation phase. This causes high delay in network, the amount of overhead transmitted in the network will increase significantly. Moreover, after several rounds, direct communication from all sensor nodes to BS is unfeasible. Another method of wireless communication is to use multi-hop approach. There has been much work on multi-hop routing protocols for wireless networks [Younis][Scott][Meng]. In these protocols, authors discusses strategies for choosing multi-hop routes to minimize the power dissipated in the sensor nodes along the route and find optimal routes by relying on the energy at each node along the route. However they do not take full advantage of data aggregation feature in WSNs. Inspired by LEACH and multi-hop approaches, this document improves BS cluster formation approach of LEACH-Centralized protocol [Heinzelman]. Then, it provides an intra-cluster 3-hop routing approach for WSN. Sensors within each cluster are partitioned into sets of nodes based on their location and remaining energy level. Each set of nodes has its own task. Then, the Shortest Path algorithm is used to determine the best route from sensor nodes to CH node through these sets of nodes. The document is organized as follows: Section 2 describes briefly the Classification of sensor networks. Section 3 and 4 describe the network and clustering model respectively. In section 5, our approach will be addressed. We analyze and conclude on this approach in section 6 and 7, respectively. Jaehwa Lee, et al. Expires April 17, 2006 [Page 3] Internet-Draft Prolonging Network Lifetime via October 17, 2005 Intra-Cluster Routing in WSNs 2. Classification of Sensor Networks Here, this document presents a simple classification of sensor networks on the basis of their mode of functioning and the type of target application. a) Proactive networks: The nodes in this network periodically switch on their sensors and transmitters, sense the environment and transmit the data of interest. Thus, they provide a snapshot of the relevant parameters at regular intervals. They are well suited for applications requiring periodic data monitoring. b) Reactive networks: In this scheme the nodes react immediately to sudden and drastic changes in the value of a sensed attribute. As such, they are well suited for time critical applications. Jaehwa Lee, et al. Expires April 17, 2006 [Page 4] Internet-Draft Prolonging Network Lifetime via October 17, 2005 Intra-Cluster Routing in WSNs 3. Sensor Network Model In a typical WSN, the sensor nodes?locations are fixed and the instability of cluster due to mobility of sensor is not an issue. It means that sensor nodes are mobile but not much and with low rate. Hence, in this network model, we assume the sensors are quasi-stationary. Each tiny sensor has a sensing module, a computing module, memory and wireless communication module. Sensor nodes are left unattended after deployment. BS has adequate energy to communicate directly with all sensor nodes in the network. However, the sensor nodes cannot always do this because of their limited energy supply and it may be impossible to recharge batteries for them. The sensors are homogeneous and begin with the equal initial energy. They can use power control to vary the amount of transmit power to reduce the possibility of interfering with nearby cluster and its own energy dissipation. Also, each node has computation power to support different MAC protocols and performs signal processing functions. The sensor nodes located close to each other sense correlated data and they always have data to send to BS. 4. Clustering Model In this model, the sensor nodes are grouped into clusters controlled by a BS. Each cluster has a cluster-head (CH) node that aggregates all data sent to it by all its members and transmits data to the remote BS. Therefore, the CH node must have much more energy than the non-CH node(sensor node, relaying node). BS performs cluster formation in the network, and informs all sensor nodes of clustering information afterwards. Network lifetime is divided into rounds. Each round begins with cluster formation phase followed by data transmission phase. In each frame of data transmission phase, non-CH node is assigned its own time slot to transmit data to CH node. Jaehwa Lee, et al. Expires April 17, 2006 [Page 5] Internet-Draft Prolonging Network Lifetime via October 17, 2005 Intra-Cluster Routing in WSNs 5. Algorithms The operation of PLIR is depicted in figure 1. ------------------------------------ | Sensor nodes send information | ----------| (location, energy level) to BS | | ------------------------------------ V ---------------------------------------- | BS forms clusters and creates TDMA |<-------------------- | schedule, then send clustering and | Next round | | routing information to sensor nodes | | ---------------------------------------- | | | | -------------------------------- | ----------->| Sensor nodes send data to BS |----- | (in-clude residual energy) | -------------------------------- Fig 1. Flowchart of PLIR PLIR distinguishes between the first round and the remaining rounds. In the first round, all sensors must send information about their location and current energy level to BS directly. The BS, based on this information, uses a cluster formation algorithm as will be described below to choose CH nodes and distribute remaining nodes into associated clusters. In subsequent rounds, to form clusters, the sensor nodes do not need to resend the information about location and residual energy to BS anymore. Instead of this, information will be extracted from the INFOR part in the data packets received from CH nodes at previous round. The last packet from each node at the end of each round is the only one that carries information about residual energy level of that node. The other packets carry data normally. CH nodes receive data packets from non-CH nodes, perform data integration then send data packet to BS directly. This packet format is depicted in figure 2. -------------------------------------------- | Header | Data | INFOR | -------------------------------------------- | | V ------------------------- Node Information | | | | | ... | ------------------------- Fig 2. The Packet format. The INFOR part includes information about {ID, energy} of nodes that packet passed. Jaehwa Lee, et al. Expires April 17, 2006 [Page 6] Internet-Draft Prolonging Network Lifetime via October 17, 2005 Intra-Cluster Routing in WSNs After having information about location and energy level of all sensor nodes in WSN, BS begins determining CH nodes and using the simulated annealing algorithm [Murata] to find out associated clusters. Firstly, BS computes the average node energy (ANE) among all the nodes. Whichever nodes have energy more than ANE are candidate for CH nodes. After that, BS runs the simulated annealing algorithm [Murata] to find out k nodes that are the best to be CH nodes for next round using probability Pk. Based on this, BS finds associated clusters by determining the minimum distance between the set of CH nodes and the set of remaining nodes. After determining CH nodes and associated clusters, BS performs 3-hop routing within each cluster as following algorithm: AD = average distance from non-CH nodes to associated CH node; CAE = average energy for each cluster; I1 = {}: set of nodes that are level-1 relaying nodes (relay for J1, J2); J1 = {}: set of nodes that are level-2 relaying nodes (relay for K); I2 = {}, J2 = {}, K = {}: sets of sensor nodes; Ei : Energy of node i; If (Di,CH < AD) then // Di,CH : distance from node i to CH If (Ei >= CAE) then I1 = I1 U i; Else I2 = I2 U i; Else If (Di,CH >= AD and Di,CH < 2*AD) then If (Ei >= CAE) then J1 = J1 U i; Else J2 = J2 U i; Else K = K U i; Jaehwa Lee, et al. Expires April 17, 2006 [Page 7] Internet-Draft Prolonging Network Lifetime via October 17, 2005 Intra-Cluster Routing in WSNs Apply the Shortest Path Algorithm to determine the best route from CH node to J(J1,J2), K using the set nodes I1, J1 respectively. Our routing problem can be considered as determining the shortest route (least cost) from one node to a set of nodes. We use Dijkstra algorithm [Zhan] for solving this routing approach with the link cost Cij for the link between the nodes i and j defined as follows: Cij = Total (Ck) k=1:5 Where: C1 = c1*(dij)2 : data communication cost (energy) from node i to node j where c1 is a constant. C2 = data sensing cost of node j. C3 = c3*dij : delay cost because of propagation between the nodes i and j where c3 is a constant which describes the speed of wireless transmission. C4 = 1/energy of node j. C5 = 1/number of connections to node j. dij is distance between the nodes i and j. Jaehwa Lee, et al. Expires April 17, 2006 [Page 8] Internet-Draft Prolonging Network Lifetime via October 17, 2005 Intra-Cluster Routing in WSNs After determining routes for sensor nodes within each cluster, BS creates the TDMA schedule for sensor nodes. As such, each cluster uses a unique spreading code; each non-CH node assigned its own time slot to transmit data to CH node uses this spreading code. The other sensors turn of their receivers for saving energy. However, the relaying node that is the next hop for the node transmitting data at its time slot must be in active mode to receive data from the transmitting node. The other nodes are idle to save energy. CH nodes use a fixed spreading code and CSMA approach to send data to BS. It means that, when CH node has data to send, it must sense the channel to see if anyone else is transmitting using the BS spreading code. If so, CH node has to wait. Otherwise, the CH node sends data using the BS spreading code. Finally, BS informs clustering information to all sensors in the network. The sensor nodes perform data transmission according to clustering information received. Data packet transmitted to BS will be added information about residual energy of nodes that packet passed. So, from the second round, sensor nodes will not send any information to BS anymore. BS will extract information from data packet received at previous round as described above. Jaehwa Lee, et al. Expires April 17, 2006 [Page 9] Internet-Draft Prolonging Network Lifetime via October 17, 2005 Intra-Cluster Routing in WSNs 6. Analysis and Conclusion In this section, we analyze performance of PLIR compared with LEACH-Centralized protocol (LEACH_C) in terms of communication overhead, the number of nodes alive, total amount of energy dissipated in the system over time. PLIR does not allow all non-CH nodes to communicate directly with CH node, number of nodes died after each round will be reduced significantly. It means that our algorithm optimizes the issue that many nodes died early while the other nodes are still alive; hence, it prolongs the lifetime of the network. PLIR does not allow sensors to send information required for cluster formation to BS at the beginning of each round, amount of overhead will be reduced significantly. PLIR use 3-hop routing within each cluster, the relaying nodes have the capability to aggregate data from sensors which reduces a larger amount of the same data passed unnecessarily in the network. This is one of the reasons that the total amount of energy dissipated in the network is reduced significantly. Clustering approach in WSNs has more advantages than other approaches such as direct transmission or multi-hop routing for saving energy. In this document, we improve the BS cluster formation of the second version of LEACH and provide a 3-hop routing approach within each cluster in order to balance the energy consumption for all sensor nodes in the network, extend lifetime of network and reduce the number of communication overhead in the network. Jaehwa Lee, et al. Expires April 17, 2006 [Page 10] Internet-Draft Prolonging Network Lifetime via October 17, 2005 Intra-Cluster Routing in WSNs 7. References [Heinzelman] W. R. Heinzelman, A. Chandrakasan, H. Balakrishnan, "An Application-Specific Protocol Architecture for Wireless Microsensor Networks" in IEEE Transactions on Wireless Communications, October 2002. [Younis] Ossama Younis, Sonia Fahmy, "Distributed clustering in ad-hoc sensor networks: A hybrid, energy-efficient approach", IEEE INFOCOM, 2004. [Murata] T. Murata, H. Ishibuchi, "Performance Evaluation of Genetic Algorithms for Flowshop Scheduling Problems" in Proceedings of the 1st IEEE Conference on Evolutionary Compu-tation, June 1994. [Scott] K. Scott, N. Bambos, "Routing and Channel Assignment for Low Power Transmission in PCS", 5th IEEE International Conference on Universal Personal Communications, September 1996. [Meng] T. Meng, R. Volkan, "Distributed Network Protocols for Wireless Communication" in Proceeding IEEE ISCAS, May 1998. [Zhan] F. Zhan, C. Noon, "Shortest Path Algorithms: An Evaluation Using Real Road Networks" Transportation Science, 1996. [Sentech] "Data sheet for the Acoustic Ballistic Module", SenTech Inc., http://www.sentech-acoustic.com/ [USNO] US Naval Observatory (USNO) GPS Operations, http://tycho.usno.navy.mil/gps.html. [ Manjeshwar] A. Manjeshwar, D. P. Agrawal, "APTEEN: A Hybrid Protocol for Efficient Routing and Comprehensive Information Retrieval in WSNs" in the Proceedings of IEEE IPDPS?2, April 2002. [ Youssef] M. Younis, M. Youssef, K. Arisha, "Energy-Aware Routing in Cluster-Based Sensor Net-works" in the Proceedings of IEEE MASCOTS02, October 2002. Jaehwa Lee, et al. Expires April 17, 2006 [Page 11] Internet-Draft Prolonging Network Lifetime via October 17, 2005 Intra-Cluster Routing in WSNs Author's Addresses Jaehwa Lee 1 Woomyun, Seocho, Seoul, Korea KT Advaned Technology Lab Korea Email: lethal@kt.co.kt Choong Seon Hong Dept of Computer Eng. Kyung Hee University 1 secheon, Giheung, Yongin, Gyeonggi, Korea Email: cshong@khu.ac.kr Intellectual Property Statement The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the IETF's procedures with respect to rights in IETF Documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf- ipr@ietf.org. Jaehwa Lee, et al. Expires April 17, 2006 [Page 12] Internet-Draft Prolonging Network Lifetime via October 17, 2005 Intra-Cluster Routing in WSNs Disclaimer of Validity This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Copyright Statement Copyright (C) The Internet Society (2005). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society.