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]