Internet DRAFT - draft-tan-roll-clustering
draft-tan-roll-clustering
ROLL Yuan-Rui Tan
Internet Draft De-Yun Gao
Expires: December 25, 2015 Wan-Ting Zhu
Wei-Cheng Zhao
Hong-Ke Zhang
Beijing Jiaotong University
June 25, 2015
RPL-based Clustering Routing Protocol
draft-tan-roll-clustering-00.txt
Status of this Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and 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 December 25, 2015.
Copyright Notice
Copyright (c) 2015 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents carefully,
as they describe your rights and restrictions with respect to this
document. Code Components extracted from this document must include
Simplified BSD License text as described in Section 4.e of the Trust
Legal Provisions and are provided without warranty as described in
the Simplified BSD License.
Abstract
Tan et al. Expires December 25, 2015 [Page 1]
Internet-Draft RPL-based Clustering Routing Protocol June 25, 2015
The IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL) is
one of the emerging routing standards for multi-hop Wireless Sensor
Networks (WSNs). RPL is based on the construction of a Destination-
Oriented Directed Acyclic Graph (DODAG), which offers a loop-free
topology to route data packets. But due to the tree topology, the
upper nodes in tree topology are easy to run out of energy. Moreover,
the hop count and ETX are the only route metrics for which standards
related to their usage in RPL are published. Due to the seriously
resource-constrained character, we take nodes' residual energy into
account. Here we present an RPL-based clustering scheme and detailed
description of Objective Function.
Table of Contents
1. Introduction ................................................ 2
2. Conventions used in this document ........................... 3
3. The whole routing protocol .................................. 3
4. Packet formats .............................................. 4
5. Objective Function .......................................... 7
6. References .................................................. 8
6.1. Normative References ................................... 8
6.2. Informative References ................................. 8
7. Acknowledgments ............................................. 9
1. Introduction
Low power and Lossy Networks (LLNs) consist of numerous constrained
nodes (with limited processing power, memory, and sometimes energy).
For such low-power lossy network characteristics, IETF ROLL working
group developed RPL (Routing Protocol for Low-Power and Lossy
Networks). RPL is a distance-vector routing protocol and organizes
networks as one or more Directly Acyclic Graph (DAG).
Furthermore, Wireless Sensor Network (WSN) consists of hundreds or
thousands of nodes scattered in an environment of interest, although
network topology built by RPL protocol can better ensure network
stability, because of the tree topology, when the nodes are
distributed densely and in a large scale, the topology depth will be
deeper. Sensor nodes in the network topology whose relative position
is near the sink are not only responsible for collecting sensor
information themselves, but also undertake the task of forwarding
packets, which make them easier to deplete energy. Once the sensor
nodes in relative top position are invalid, the entire network will
have a great concussion.
Tan et al. Expires December 25, 2015 [Page 2]
Internet-Draft RPL-based Clustering Routing Protocol June 25, 2015
This document proposes a hierarchical routing mechanism based on the
RPL routing protocol.
2. Conventions used in this document
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119].
3. The whole routing protocol
In wireless sensor networks, after the routing topology is basically
established, first of all, the network is hierarchized. In each layer,
a cluster head is selected according to specific rules and a certain
percentage (See Section 5).
The nodes elected as cluster head will broadcast "office information"
to other nodes in the same layer, which invite other nodes to join
the clusters. After receiving the message, nodes decide whether to
join in the cluster in accordance with rules. If deciding to join,
the cluster member node will add its cluster head into the routing
table as the sub-optimal parent. Otherwise the node will restart the
process of selecting cluster head. Thus, until all the nodes repeat
the above process, the whole network process is completed.
In the packet forwarding, the cluster member node sends its own
collection of information directly to the cluster head node and data
fusion processed by the cluster head node. If a node receives packets
from lower layer which have been integrated, it will forward the
integrated massages directly to the original optimal parent rather
than the cluster head. So the node can keep two parents, one is the
original optimal parent and the other is the cluster head which is
the sub-optimal parent. In other words, packets without fusion are
forwarded to the cluster head, and the fusion data are forwarded
along the original path. Thereby, this method can reduce the packet
flow, balance node energy consumption and increase network
reliability.
Route establishment process is as follows: Cluster head node
broadcasts DIOs that carry with cluster information. After cluster
members receive the DIOs, they will judge whether they are in the
same layer. If in the same layer, it will compare cRank (Rank for
Cluster) which is a new route metric in the cluster and defined by
EXT and RE(Remaining Energy)(See Section 5). Only if the cRank is
less than itself, node will send DAO to request to join the cluster.
The cluster head receives the request message and judges whether it
is in the same layer. If in the same layer, cluster head replies CH-
Tan et al. Expires December 25, 2015 [Page 3]
Internet-Draft RPL-based Clustering Routing Protocol June 25, 2015
Ack to the node. Cluster member will get the CH-Ack and if its
cluster head agrees to be joined, then it will update information
table and add the cluster head to parents list as the sub-optimal
parent. This process is shown in figure 1.
cluster head cluster member
| |
| |
|------------DIOC----------->|
| |
| |
| |
| |
|<------------DAOC-----------|
| |
| |
| |
| |
|----------CH-Ack----------->|
| |
Figure 1 Route establishment
4. Packet formats
This document defines three kinds of messages and two among them are
derived from RPL control massage which is defined in RFC 6550.The
packet formats are defined as follow:
1)DODAG Information Object for Cluster (DIOC)
The DODAG Information Object for Cluster carries information that
allows a node to discover a RPL Instance and cluster, learn its
configuration parameters, select a DODAG parent set, and maintain the
DODAG and the cluster.
Tan et al. Expires December 25, 2015 [Page 4]
Internet-Draft RPL-based Clustering Routing Protocol June 25, 2015
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RPLInstanceID | Version Number| Rank |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|G|0| MOP | Prf | DTSN | Flags | Reserv |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ +
| |
+ DODAGID +
| |
+ +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Option Length | cRank |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Msg Type | N |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 2. Format of DIOC
Option Type: 0X99, 8-bit unsigned integer indicating cluster massage.
Option Length: 0X05, 8-bit unsigned integer indicating length of
option.
cRank: 16-bit unsigned integer indicating node's relative position in
the cluster (See Section 5).
N: 8-bit unsigned integer indicating that node's in the Nth layer.
Msg Type: 8-bit indicating the type of message.
+----------+------------------+
| Msg Type | Meaning |
+----------+------------------+
| 0x01 | Cluster head |
| 0x02 | Cluster member |
| 0x03 | Cluster pre-head |
+----------+------------------+
Figure 3. Msg Type Encoding
2) Destination Advertisement Object for Cluster (DAOC)
The Destination Advertisement Object for Cluster (DAOC) is used to
propagate destination information upwards along the DODAG.
Tan et al. Expires December 25, 2015 [Page 5]
Internet-Draft RPL-based Clustering Routing Protocol June 25, 2015
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RPLInstanceID |K|D| Flags | Reserved | DAOSequence |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ +
| |
+ DODAGID* +
| |
+ +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Option Length | Msg Type | N |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Node Status |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 4. Format of DAOC
Option Type: 0X99, 8-bit unsigned integer indicating cluster massage.
Option Length: 0X03, 8-bit unsigned integer indicating length of
option.
N: 8-bit unsigned integer indicating that node's in the Nth layer.
Msg Type: 8-bit indicating the type of message (See Figure 3).
Node Status: 8-bit indicating the node current status.
+-------------+--------------+
| Node Status | Meaning |
+-------------+--------------+
| 0x01 | joined |
| 0x02 | unjoined |
+-------------+--------------+
Figure 5. Node Status Encoding
3)CH-Ack
ACK of cluster head is used to reply to cluster members whether to
agree to serve.
Tan et al. Expires December 25, 2015 [Page 6]
Internet-Draft RPL-based Clustering Routing Protocol June 25, 2015
0 1 2
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Msg Type | Status | DODAG Versioin|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 6 Format of CH-Ack
Msg Type: the same in DIOC and DAOC.
Status: 8-bit indicating cluster head whether agrees to be joined.
+-------------+--------------+
| Node Status | Meaning |
+-------------+--------------+
| 0x01 | agree |
| 0x02 | not agree |
+-------------+--------------+
Figure 7. Status Encoding
DODAG Versioin: 8-bit, recording DODAG version of cluster head node.
5. Objective Function
Objective Function (OF), which uses routing metrics to select node's
preferred parent among neighbors. Different criteria, also called
routing metrics, are defined to capture link or node characteristics
on the path for parent selection. They could be node attributes: hop
count, node residual energy, or link attributes: throughput, latency,
link quality level or expected transmission count (ETX).
Most protocol implementations use expected transmission count as the
routing metric focusing on the link reliability. As the battery
recharging of sensor nodes is practically very difficult, we hope
that the data can be transmitted with the minimum energy consumption.
Thus the routing metric has to consider energy awareness. In this
document, we organize routing topology based on node's ETX and
battery power level.
To avoid loop in the network, every node uses a scalar values, called
cRank, to record its relative position to other nodes with regard to
cluster head. The cRank is not a path cost, although its value can be
derived from and influenced by path metric. The calculation method is
as follows: Once a node (say M) has chosen its preferred parent (P),
node computes its own cRank from preferred parent's cRank.
cRank(M)=cRank(P)+RankIncrease (1)
Tan et al. Expires December 25, 2015 [Page 7]
Internet-Draft RPL-based Clustering Routing Protocol June 25, 2015
RankIncrease=*RankIncrease_ETX+*RankIncerase_RE (2)
RankIncease_RE=step+MinHopInc (3)
where Step=MAX_energy-Node_energy
These formulas ensure the monotonic property of the rank which
increases by at least one point (MinHopRankIncrease) between node and
its preferred parent, when child node has a full battery level. Root
rank is set to the same value as MinHopRankInc. RankIncrease_ETX is
increase of ETX metric while RankIncerase_RE is increase of residual
energy metric. MAX_energy, Node_energy, RankIncrease_ETXare defined
in RFC6551.
After computing the path cost for all reachable candidate neighbors,
a node selects the preferred parent. A node MUST select the candidate
neighbor with the lowest path cost as its preferred parent. The
specific rules is described in [RFC 6550] Section3.5.
6. References
6.1. Normative References
[RFC6550] T. Winter, P. Thubert, A. Brandt, J. Hui, R. Kelsey, P.
Levis, K. Pister, R. Struik, JP. Vasseur, and R. Alexander,
"RPL: IPv6 Routing Protocol for Low-Power and Lossy
Networks", RFC6550, March 2012.
[RFC2119] S.Bradner, "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC6551] JP. Vasseur, Ed., M. Kim, Ed., K. Pister, N. Dejean and D.
Barthel, "Routing Metrics Used for Path Calculation in Low-
Power and Lossy Networks",RFC6551 March 2012.
[RFC6552] P.Thubert, "RPL Objective Function 0", RFC6552, March 2012.
[RFC6206] P.Levis, T.Clausen, J.Hui, O.Gnawali, and J.Ko, "The
Trickle Algorithm", RFC6206, March 2011.
6.2. Informative References
[1] Jennifer Yick. Wireless sensor network survey[J]. Computer
networks,2008,52(12): 2292-2330.
[2] POTTIE G J, KAISER W J. Wireless Integrated Network Sensors[ J].
Communications of the ACM (S0001-0782),2000,43(5) : 551-558.
Tan et al. Expires December 25, 2015 [Page 8]
Internet-Draft RPL-based Clustering Routing Protocol June 25, 2015
[3] A. M. El-Semary and M. M. A. Azim. Path energy weight: A global
energy-aware routing protocol for wireless sensor network. In
Proc. of IFIP WD, Venice, Oct. 2010.
[4] K. S. Shivaprakasha and M. Kulkarni. Energy efficient shortest
path routing protocol for wsn. In Proc. of 3rd CICSYN, pages
333-337, Bali, Indonesia, Jul. 2011.
[5] T. Zahariadis and P. Trakadas. Design guidelines for routing
metrics composition in lln.IETF Work in progress, Nov. 2012.
[6] A. Mohajerzadeh and M. Yaghmaee. An efficient energy aware
routing protocol for real time traffic in wsn. In Proc. of
ICUMT, pages 1-9, St-P, Russia, Oct. 2009.
7. Acknowledgments
This work was supported by National S&T Major Program
(2012ZX03005003).
Tan et al. Expires December 25, 2015 [Page 9]
Internet-Draft RPL-based Clustering Routing Protocol June 25, 2015
Authors' Addresses
Yuan-Rui Tan, De-Yun Gao, Wan-Ting Zhu, Wei-Cheng Zhao, Hong-Ke Zhang
National Engineering Lab for NGI Interconnection Devices
Beijing Jiaotong University, China
Phone: +8613521693762
Email: 13120124@bjtu.edu.cn
gaody@bjtu.edu.cn
11111019@bjtu.edu.cn
11111018@bjtu.edu.cn
hkzhang@bjtu.edu.cn
Tan et al. Expires December 25, 2015 [Page 10]
