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]