Internet DRAFT - draft-rashid-eerrd-sensornetwork
draft-rashid-eerrd-sensornetwork
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]
