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]