Internet DRAFT - draft-jaehwa-pnl
draft-jaehwa-pnl
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
<draft-jaehwa-pnl-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 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.
