Networking Working Group Md. Mamun-Or-Rashid Internet-Draft Choong Seon Hong Expires: April 16 , 2006 Kyung Hee University Dongjin Kwak KT Advanced Technology Lab October, 2005 Energy Efficient Routing for Highly Dense Sensor Network Based on Residual Energy and Distance draft-rashid-eerrd-sensornetwork-00.txt 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 16, 2006. Copyright Notice Copyright (C) The Internet Society (2005). Abstract Efficient energy utilization and prolonged lifetime are two most covetable targets for sensor network. For increased lifetime,each node must conserve energy as much as possible. In this paper we propose a protocol in which energy is conserved by amortizing the energy cost of superfluous packets and idle state energy consumption To achieve our goal we have exercised well-known periodic sleep protocol and reduce redundant transmission by creating broadcast tree based on residual energy and distance based communication cost. Wasteful energy consumption of sensor nodes (e.g. idle listening, retransmission due to packet collision, overhearing etc) can be minimized by selecting minimum number of forwarding nodes. Our proposed algorithm selects minimum number of forwarding while creating broadcast tree. All intermediate nodes acts as forwarding node (non-leaf) while all the other nodes acts as a non-forwarding (child) reduces wasteful energy consumption by keeping radio transceiver off. Simulation shows our algorithm is better in terms of energy conservation and network lifetime Rashid, et al. Expires April 16, 2006 [Page 1] Internet-Draft Energy Efficient Routing for Highly October 2005 Dense Sensor Network Based on Residual Energy and Distance Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 2 2. Related Energy Saving Protocols. . . . . . . . . .. . . . . 2 3. Energy Consumption Analysis. . . . . . . . . . . .. . . . . 3 4. Protocol Description. . . . . . . . . . . . . . . . . . . . 5 5. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 6 1. Introduction Sensor network has received great magnitude of attention due to its diverse application area specially, in hostile environment where human intervention is grueling or inopportune and sometimes impossible. While the exact application of sensor network is speculative, certain properties are typically assumed. First, sensors are static after initial deployment. Second, energy is scarce and it is inconvenient or impossible to replenish the energy source frequently. Sensors are deployed in a highly dense fashion. Effect of high density instigates the major problem of collision, overhearing and redundant transmission. While deployment with less density is contradictory as sensors are deployed in hostile environments and also they are energy constrained so sensor nodes are porn to failure. Such constraints combined with a typical deployment of large number of sensor nodes have posed many challenges to the design and management of sensor networks. These challenges necessitate energy-awareness at Rashid, et al. Expires April 16, 2006 [Page 2] Internet-Draft Energy Efficient Routing for Highly October 2005 Dense Sensor Network Based on Residual Energy and Distance all layers of networking protocol stack. The issues related to physical and link layers are generally common for all kind of sensor applications, therefore the research on these areas has been focused on system-level power awareness such as dynamic voltage scaling, radio communication hardware, low duty cycle issues, system partitioning, energy aware MAC protocols [6][7][8]. At the network layer, the main aim is to find ways for energy efficient route setup and reliable relaying of data from the sensor nodes to the sink so that the lifetime of the network is maximized. Energy consumption in a sensor node can be due to either useful or wasteful sources. Useful energy consumption can be due to (i) transmitting/receiving data, (ii) processing query requests, and (iii) forwarding queries/data to neighboring nodes. Wasteful energy consumption can be due to (i) idle listening to the media, (ii) retransmitting due to packet collisions, (iii) overhearing, and (iv) generating/handling control packets. While radios typically have four power levels corresponding the following states (i) transmit (ii) receive (iii) idle and (iv) sleep. Our idea is to minimize wasteful energy consumption by reducing redundant traffic and optimizing control message transmission while creating the sink rooted broadcast tree. Our work minimizes redundant traffic transmission and collision using sink rooted broadcast tree. The nodes will be having two status forwarding (non-leaf) and non-forwarding (Leaf) based on residual energy and distance towards sink. Non-forwarding (Leaf) nodes are in charge of sensing the vicinity and transfer sensed data through forwarding (non-leaf) nodes. Our proposed algorithm tries to select one forwarding node with in the transmission range. We also introduced a timer parameter to control the transmission while creating the tree and thus reduce collision and also reduce control message transmission required to generate the tree. 2. Related Energy Saving Protocols Routing protocols of sensor network can be classified into two according to network structure and protocol operation. According to network structure proposed protocols can be further classified into (i) Flat [5][10][11], (ii) Hierarchical [1]-[4][9][14] and (iii) Location based [13]. While based on protocol operation is further classified into (i) Negotiation based (ii) Multipath, (iii) Query based, (iv) QoS based and (v) Coherent based. We focus on hierarchical routing protocols. In a hierarchical architecture, higher energy nodes can be used to process and send the information while low energy nodes can be used to perform the sensing in the proximity of the target. This means that creation of clusters and assigning special tasks to cluster heads can greatly contribute to overall system scalability, lifetime, and energy efficiency. Hierarchical routing is an efficient way to lower energy consumption within a cluster and by performing data aggregation and fusion in order to decrease the number of transmitted messages to the BS. Rashid, et al. Expires April 16, 2006 [Page 3] Internet-Draft Energy Efficient Routing for Highly October 2005 Dense Sensor Network Based on Residual Energy and Distance Heinzelman, et. al. [1] introduced a hierarchical clustering algorithm for sensor networks, called Low Energy Adaptive Clustering Hierarchy (LEACH). LEACH randomly selects a few sensor nodes as clusterheads (CHs) and rotates this role to evenly distribute the energy load among the sensors in the network. Protocol assumes that all nodes can transmit with enough power to reach the BS if needed and that each node has computational power to support different MAC protocols. Therefore, it is not applicable to networks deployed in large regions. It also assumes that nodes always have data to send, and nodes located close to each other have correlated data. It is not obvious how the number of the predetermined CHs is going to be uniformly distributed through the network. Hierarchical Power-aware Routing (HPAR) protocol [15] finds the path with the least power consumption by using the Dijkstra algorithm and maximizes the minimal residual power in the network. But wasteful energy consumption due to idle listening is not considered in the protocol. Energy Aware Data- centric (EAD) protocol [9] was proposed by Boukerche et. al. EAD consider residual energy as a parameter to construct the broadcast tree. The idea is to produce more non-leaf nodes to save energy as well as reduced transmission. Our work differ form EAD as we have considered distance as parameter. Emphasis on only residual energy may generate longer paths which is undesirable as longer path requires more energy to transmit. Our work also generates sink rooted tree in which non-leaf and leaf nodes are considered as forwarding and non-forwarding nodes. In our proposed tree construction we emphasize both residual energy and distance which ensure a optimal forwarding node selection in terms of routing cost and thus achieve energy efficiency 3. Energy Consumption Analysis Sensor network is usually very dense. Certain amount of redundancy is introduced for the robustness of the network. In this section we will show the effect of idle nodes on per packet energy cost for single hop and multi hop transmission. A. Single Hop Based Analysis In simple case, the energy consumed by the network interface when a host sends receives or discards a packet can be represented using a linear equation Energy = P x Size + f Trivially, there is a fixed component associated with device state changes and channel acquisition overhear and an incremental component which is proportional to the size of the packet. Here in the equation coefficient P represents the variable cost and f is the fixed cost associated with the transmission. Note that the equation does not consider about the media contention cost. The relative magnitude of the various P and f coefficients also indicate the amount of per packet energy consumption overhead. Rashid, et al. Expires April 16, 2006 [Page 4] Internet-Draft Energy Efficient Routing for Highly October 2005 Dense Sensor Network Based on Residual Energy and Distance A packet may be sent as broadcast or point-to point traffic. Broadcast traffic received by all hosts within transmission range and point-point case traffic will be discarded by non- destination hosts. Sensor network operates in promiscuous mode and any sensed data is normally broadcast to the neighbors and destined for the sink. It is very evident that some of the neighbor will be useful for forwarding the data towards the sink and some other will not (as sensor network is highly dense and good number of redundant nodes are deployed to increase the robustness of the network). So in promiscuous mode of operation there will be three (broadcast, point-to-point receive and discard traffic) types of energy consumption. Node sensing any event will broadcast the data, nodes responsible to forward data towards sink will receive data and finally nodes other than receiving or sending will discard the data. Energy consumption for three kinds of operation can be presented by Ebsend = Pbsend * Size + bsend (for broadcast send) Let S be the source and N(s) be the number of nodes within one hop of S. Out of N(s) neighbors let Nfrd(s) are the required number of nodes for forwarding data towards sink and Nidl(s) are the number of idle nodes are discarding traffic. For a single source scenario total energy consumption can be represented by Etotal = Ebsend + Nfrd(s) * Erecv + Nidl(s) * Edisc Total energy cost per bit can be calculated by Ebit = Ebsend + Nfrd(s) * Erecv + Nidl(s) * Edisc / Psize where Psize represents the packet size It is clear form the equation that bit packet energy consumption will increase depending on number nodes receiving and discarding packets. Another significant consideration is to identify the required forwarding nodes for reliable delivery of data to the sink. B. Multi-hop Based Analysis Transmission of data from source to destination may require multiple hops. Energy consumption of each hop can be obtained from the single hop analysis and finally the total cost of data transmission from source to sink will be an additive matrix of each hop. Based on analysis energy efficient routing protocol should have the following properties i. Balance energy consumption among the nodes to ensure uniform failure rate. ii. Energy balanced path based on residual energy and distance towards sink iii. Optimal number of forwarding node selection Rashid, et al. Expires April 16, 2006 [Page 5] Internet-Draft Energy Efficient Routing for Highly October 2005 Dense Sensor Network Based on Residual Energy and Distance 4. Protocol Description In this section we will describe sink rooted tree (SRT) construction process and routing using the tree. Control message for tree construction consists of following four fields i. Node ID ii. Residual Energy iii. Distance up to sink iv. Type of the message: Type 1 indicates forwarding node selection message and type 0 means notification of individual energy and distance information. We define three different statuses of nodes depending on operation i. Non-forwarding: Each sensor node is having a sensing circuit and a radio transceiver. In this status nodes will turn off their radio transceiver and continue to sense for events within the sensing rage. If any node senses any stimuli, will turn on their radio and transmit to the nearest forwarding node. ii. Forwarding: Both the circuitry will remain on for the nodes in forwarding status. iii. Active: While constructing the tree all nodes will remain in active status. There is node major difference between forwarding and active status. We need this status to differentiate from normal operational state and tree construction state Initially all nodes will be in status 0 (active status). Sink node initiates tree construction with a type 0 message indicating s as node ID, 0 as distance toward sink and as the amount of residual energy. Nodes within the 1-hop of sink will receive the message and calculate parameter Tactive and Twait. Each node upo receiving type 0 message will check whether the node has selected forwarding node. If the forwarding node is not selected the node will store the node ID, residual energy and distance towards sink. Then sense the channel, if the channel is idle it will wait for another Twait time and if the channel is still idle it will transmit type 0 and type 1 message consecutively noticing its residual energy and distance towards sink and its forwarding node. Each node will select forwarding node based on the neighbor’s residual energy and distance towards sink. It should be noted that for each round of tree construction each node will transmit the messages once. Any node receiving type 1 message will check the incoming message node ID. If the node ID matches with own ID the node will change its status to forwarding node. It means any of the neighbor need the node to relay the data towards sink. If any node does not receive type 1 message with matching with its own ID with in Tactive time, the node will change its status to non-forwarding node. After the construction of the tree all nodes will be either in forwarding or non-forwarding state. Nodes settled in non-forwarding state will turn off their radio transceiver while keeping the sensing circuitry turned on. On the other hand forwarding nodes will keep both radio and sensing circuitry turned on. All nodes will continue to sense within the vicinity and if any stimuli detected for non-forwarding node, it will turn its radio on and transmit data to the pre-defined sink while Rashid, et al. Expires April 16, 2006 [Page 6] Internet-Draft Energy Efficient Routing for Highly October 2005 Dense Sensor Network Based on Residual Energy and Distance forwarding node having radio turned on will transmit to its forwarding node. After tree construction each node will dynamically set transmission range according to the distance of the parent or forwarding node. Tree construction algorithm will be executed every after T time where T is an application dependent parameter. T depends on amount of events and event generation rate as well on the load of the network. Each node participating in tree construction must have threshold energy. It is obvious that nodes with higher ratio of residual energy and distance will transmit first. Which ensures the chance to choose the best forwarding node among the neighbors. A. Timer parameter for Tree construction and message Transmission All the nodes will be in active status while constructing the tree. But the question is how long the nodes will be in active status? Another important consideration is transmission of control message for constructing the tree. As the nodes participate in a competition to notify residual energy and status to the neighbors, good scheduling among the neighbor for control message transmission is needed to reduce collision. Considering these two points we define two timer parameters for determining each node’s active status time and control message transmission time. Determining Active Status Time: Let be a node and is the set of 1-hop neighbor of for a particular transmission range r. We define as the round trip time for data propagation between any two pairs within the one hop neighbors. Active status time for node v is given by the following equation Tactive = Trtt+N1(v) It should be noted that, within nodes will be able to determine its necessity to be a forwarding node. If a node does not receive any message from any of the neighbor to become as forwarding node within time, the node will change its status to non-forwarding Determining Control Message Transmission Time: Tree construction algorithm will be initiated by sink and nodes within in the transmission range will receive the message first. Waiting time before further transmission can be obtained using the following equation Twait = Er / Ds Each node receiving the message will sense the channel and if the channel is idle, it will wait until time and then transmit own status and residual energy. mainly depends on and which prioritize the node with better energy and transmission cost towards sink. B . 5. Conclusion Our proposed protocol high lightens wasteful energy consumption due to idle listening. We propose a hierarchical routing protocol which creates a sink rooted tree with two different statuses (forwarding Rashid, et al. Expires April 16, 2006 [Page 7] Internet-Draft Energy Efficient Routing for Highly October 2005 Dense Sensor Network Based on Residual Energy and Distance and non-forwarding) for each sensor node. Nodes in non-forwarding status turn off their radio and conserves idle energy consumption and reduce redundant transmission. Simulation shows our algorithm is better in terms of efficient energy consumption and network lifetime. Sink mobility, very attractive feature for many applications of sensor network is not included in our work. We intend to introduce sink mobility in future. Significant amount of data aggregation is possible at the forwarding nodes as same stimuli may be detected by more than one node and transmitted to one forwarding node. In future we would like to focus on data aggregation also REFERENCES [1] W. Heinzelman, A. Chandrakasan and H. Balakrishnan, "Energy- Efficient Communication Protocol for Wireless Micro-sensor Networks," Proceedings of the 33rd Hawaii International Conference on System Sciences (HICSS '00), January2000. [2] A. Manjeshwar and D. P. Agarwal, "TEEN: a routing protocol for enhanced efficiency in wireless sensor networks," In1st International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing, April 2001. [3] A. Manjeshwar and D. P. Agarwal, "APTEEN: A hybrid protocol for efficient routing and comprehensive information retrieval in wireless sensor networks," Parallel and Distributed Processing Symposium., Proceedings International, IPDPS 2002, pp. 195-202. [4] S. Lindsey, C. Raghavendra, PEGASIS: Power-Efficient Gathering in Sensor Information Systems", IEEE Aerospace Conference Proceedings, 2002, Vol. 3, 9-16 pp. 1125-1130. [5] C. Intanagonwiwat, R. Govindan, and D. Estrin, "Directed diffusion: a scalable and robust communication paradigm for sensor networks," Proceedings of ACM MobiCom '00, Boston, MA, 2000, pp. 56-67. [6] W. R. Heinzelman, et al., "Energy-Scalable algorithms and protocols for Wireless Sensor Networks", in the Proceedings of the International Conference on Acoustics, Speech, and Signal Processing (ICASSP '00), Istanbul, Turkey, June 2000. [7] R. Min, et al., "An Architecture for a power aware distributed microsensor node", in the Proceedings of the IEEE Workshop on signal processing systems (SIPS'00), October 2000. [8] A. Woo and D. Culler. "A Transmission Control Scheme for Media Access in Sensor Networks," in the Proceedings of the 7th Annual ACM/IEEE International Conference on Mobile Computing and Networking (Mobicom'01), Rome, Italy, July 2001. Rashid, et al. Expires April 16, 2006 [Page 8] Internet-Draft Energy Efficient Routing for Highly October 2005 Dense Sensor Network Based on Residual Energy and Distance [9] Azzedine Boukerche,Xiuzhen Cheng,Joseph Linus,"Energy-aware data -centric routing in microsensor networks", Proceedings of the 8th international workshop on Modeling analysis and simulation of wireless and mobile systems,MSWiM 03, September 19, 2003, San Diego, California, USA. [10] J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, and K. Pister. System architecture directions for networked sensors. In Proc. of International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-IX), Cambridge, MA, USA, November 2000. [11] W. Heinzelman, J. Kulik, and H. Balakrishnan, "Adaptive Protocols for Information Dissemination in Wireless Sensor Networks, " Proc. 5th ACM/IEEE Mobicom Conference (MobiCom '99), Seattle, WA, August, 1999. pp. 174-85. [12] J. Kulik, W. R. Heinzelman, and H. Balakrishnan, "Negotiation-based protocols for disseminating information in wireless sensor networks, " Wireless Networks, Volume: 8, pp. 169-185, 2002 [13] Y. Xu, J. Heidemann, D. Estrin, Geography-informed Energy Conservation for Ad-hoc Routing," In Proceedings of the Seventh Annual ACM/IEEE International Conference on Mobile Computing and Networking 2001, pp. 70-84. [14] Q. Li and J. Aslam and D. Rus, Hierarchical Power-aware Routing in Sensor Networks", In Proceedings of the DIMACS Workshop on Pervasive Networking, May, 2001. Rashid, et al. Expires April 16, 2006 [Page 9] Internet-Draft Energy Efficient Routing for Highly October 2005 Dense Sensor Network Based on Residual Energy and Distance AUTHOR'S ADDRESS Questions about this document can also be directed to the author: Md. Mamun-Or-Rashid Department of Computer Engineering Kyung Hee University 1 Seocheon, Giheung, Yongin, Gyeongi-Do, 449-701, Korea Email: joon@networking.khu.ac.kr Choong Seon Hong Department of Computer Engineering Kyung Hee University 1 Seocheon, Giheung, Yongin, Gyeongi-Do, 449-701, Korea E-mail : cshong@khu.ac.kr Dongjin Kwak KT Advanced Technology Lab Woomyun, Secho, Seoul, Korea E-mail : djk@kt.co.kr Rashid, et al. Expires April 16, 2006 [Page 10] Internet-Draft Energy Efficient Routing for Highly October 2005 Dense Sensor Network Based on Residual Energy and Distance 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 procedures with respect to rights in RFC 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. Rashid, et al. Expires April 16, 2006 [Page 11] Internet-Draft Energy Efficient Routing for Highly October 2005 Dense Sensor Network Based on Residual Energy and Distance 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. Rashid, et al. Expires April 16, 2006 [Page 12]