Internet DRAFT - draft-wang-roll-energy-optimization-scheme

draft-wang-roll-energy-optimization-scheme



ROLL Working Group                                             H. Wang
Internet Draft                                                  M. Wei
Interned status: Standards Track                                 S. Li
Expires: August 25, 2017                                      Q. Huang
                                                               P. Wang
                                                               C. Wang
                                               Chongqing University of
                                          Posts and Telecommunications
                                                     February 21, 2017

              An energy optimization routing scheme for LLSs
               draft-wang-roll-energy-optimization-scheme-00


Abstract

   Low-Power and Lossy Networks (LLNs) are composed of devices that
   have constraints on processing power, memory, and energy (battery
   power). It is obvious that conserving energy is especially important
   in the LLNs. This document is aimed at proposing an efficient and
   effective scheme to optimize the energy in the process of seeking
   the DAG root node.

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 August 25, 2017.






Wang, et al.           Expires August 25, 2017                [Page 1]

 Internet-Draft     Energy Optimization Routing Scheme     February 2017


Copyright Notice

   Copyright (c) 2017 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.

Table of Contents


   1. Introduction ................................................ 2
      1.1. Requirements Notation................................... 3
      1.2. Terms Used ............................................. 3
   2. Requirements ................................................ 3
   3. An Energy Optimization Routing Scheme ........................4
      3.1. The network topology.................................... 4
      3.2. Increasing Broadcast.................................... 5
      3.3. The implementation of the scheme ........................7
   4. Security Considerations...................................... 8
   5. IANA Considerations ......................................... 8
   6. Acknowledgements ............................................ 8
   7. References .................................................. 9
      7.1. Normative References.................................... 9
      7.2. Informative References.................................. 9

1. Introduction

   IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL) is
   specified in [RFC6550], which provides a mechanism whereby
   multipoint-to-point traffic from devices inside the LLN towards a
   central control point as well as point-to-multipoint traffic from
   the central control point to the devices inside the LLN are
   supported. The routing metrics and constraints are specified in
   [RFC6551], which provides a high degree of flexibility and a set of
   routing metrics and constraints. A variety of node
   constraints/metrics must be possible taken into account during path
   computation (see RFC[6551]).




Wang, et al.           Expires August 25, 2017                [Page 2]

 Internet-Draft     Energy Optimization Routing Scheme     February 2017


   Low-Power and Lossy Networks (LLNs) have recently attracted a lot of
   interest to the researchers due to its wide range of applications
   such as military implementations in a battlefield, an environmental
   monitoring, and multifunction in health sector. However, due to the
   characteristics of LLNs, it has such limitations as limited battery
   power, finite computing and memory capability, the large scale of
   deployment and narrow communication bandwidth. Therefore, there is
   an urgent need for conserving energy in the LLNs so as to ensure
   long term operation.

1.1. Requirements Notation

   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].

1.2. Terms Used

   DAG: Directed Acyclic Graph. A directed graph has the property that
   all edges are oriented in such a way that no cycles exist. All edges
   are contained in paths oriented toward and terminating at one or
   more root nodes.

   DAG root: A DAG root is a node within the DAG that has no outgoing
   edge. Because the graph is acyclic, by definition, all DAGs MUST
   have at least one DAG root and all paths terminate at a DAG root.

   Increasing broadcast: Increasing broadcast is a routing scheme used
   for energy optimization. In the process of seeking the DAG root node,
   the routing request message will be sent to the nodes which have the
   most neighbors. And the number of nodes is increasing order.

2. Requirements

   Due to the restrained hardware resource and energy of LLNs, its data
   processing and transmission ability is weak. Therefore, how to make
   full use of energy becomes an important research area of routing
   protocol. LLNs is a multiple hops self-organizing networks, that the
   data is forwarded along the optimal path is main function of routing
   protocol. In order to make full use of limited resource, the current
   routing protocols attempt to find the path that consumes the least
   energy. However, it is not comprehensive to merely focus on the
   efficiency of energy when designing the routing protocol, the
   balance of energy consumption and the security can also affect the
   performance of the networks. Studies have shown that the nodes close
   to DAG root node are faced with more data transmission tasks due to
   the influence of RPL (Routing Protocol for Low Power and Lossy


Wang, et al.           Expires August 25, 2017                [Page 3]

 Internet-Draft     Energy Optimization Routing Scheme     February 2017


   Networks), so the energy consumption is much faster than the nodes
   far away from DAG root node. With the frequent data transmission to
   DAG root node, the closer nodes will have a shorter lifetime. As a
   result, it leads to an energy hole around the DAG root node. And it
   makes the data of other nodes cannot be transmitted to the DAG root
   node through multiple hops, which seriously influence the functions
   and the lifetime of networks. However, the nodes outside the energy
   hole still have much residual energy.

   Worse still, in current technology, multiple DAG root nodes can move
   randomly and make up routing topology to accomplish data collection
   in a small area. The nodes in the routing topology transmit data to
   the DAG root node directly, while the nodes outside the routing
   topology need to seek the DAG root node firstly and then finish the
   data transmission. Many researches show that the nodes outside the
   routing topology seek the DAG root node by flooding broadcast, which
   makes the nodes consume energy vastly. Meanwhile, when the nodes
   transmit the data to the DAG root node after finding it, the DAG
   root node may move to another place, thus causing the loss of data.

   Consequently, the balance of energy is important to routing protocol,
   thus avoiding some nodes die quickly because of excessive energy
   cost. And it is an important technology to prolong the life cycle of
   LLNs. The document proposes an energy optimization routing scheme
   based on increasing broadcast for LLNs.

3. An Energy Optimization Routing Scheme

3.1. The network topology

   The scheme proposed by this document is applied to the network
   topology shown in the figure 1. The mobile DAG root node builds a
   DAG by using the RPL in a range of limited hops. And the member
   nodes that belong to the DAG send data to the DAG root node directly.
   However, the nodes outside the DAG need to seek the DAG root node
   firstly and then send data to the DAG root node found by them.
   Meanwhile, the mobile DAG root node will move to another place after
   staying for a period of time and set up a new DAG through the RPL.










Wang, et al.           Expires August 25, 2017                [Page 4]

 Internet-Draft     Energy Optimization Routing Scheme     February 2017


  +--------------------+                        +--------------------+
  |                    |       --               |                    |
  |         +--+       |      |SN|              |         +--+       |
  |     ---| R |---    |       --               |     ---| R |---    |
  |     |   +--+   |   |                        |    |    +--+   |   |
  |     |          |   |              --        |    |           |   |
  |    --         --   |             |SN|       |   --           --  |
  |   |SN|       |SN|  |              --        |  |SN|         |SN| |
  |    --         --   |                        |   --           --  |
  |     |          |   |      --                |    |            |  |
  |     |          |   |     |SN|               |    |            |  |
  |    --         --   |      --                |   --           --  |
  |   |SN|       |SN|  |                        |  |SN|         |SN| |
  |    --         --   |                        |   --           --  |
  |                    |                        |                    |
  +--------------------+                        +--------------------+
                      Figure 1 The network topology

   As shown in the figure above, the root node builds a DAG in some
   area. Some nodes are in the DAG, while others are outside of the DAG.

3.2. Increasing Broadcast

   For the purpose of lowering the energy consumption used for seeking
   the DAG root node, the document proposes a method named increasing
   broadcast to forward the routing request message instead of using
   the previous flooding broadcast. The detailed process of the
   increasing broadcast is shown as figure 2.




















Wang, et al.           Expires August 25, 2017                [Page 5]

 Internet-Draft     Energy Optimization Routing Scheme     February 2017


             +-------------------------------------------+
             |The node chooses its neighbor node which   |
             |has the most neighbor nodes and sends the  |
             |routing request message to it.             |
             +-------------------------------------------+
                                  |
                                  V
             +-------------------------------------------+
             |The node receiving the above routing       |
             |request message chooses two neighbor nodes |
             |which have the most neighbor nodes and     |
             |sends the routing request message to them. |
             +-------------------------------------------+
                                  |
                                  V
             +-------------------------------------------+
             |The nodes receiving the above routing      |
             |request message choose three neighbor nodes|
             |which have the most neighbor nodes and send|
             |the routing request message to them. And   |
             |these three nodes respectively broadcast   |
             |the message according to this rule.        |
             +-------------------------------------------+
                                  |
                                  V
             +-------------------------------------------+
             |The process ends until the increasing      |
             |broadcast reaches the largest hop or the   |
             |DAG root node (the member of a DAG) has    |
             |been found.                                |
             +-------------------------------------------+
           Figure 2 The process of the increasing broadcast

   (1) Firstly, the node determines which neighbor node has the most
   neighbor nodes, and then sends the routing request message to it.
   Because the node chooses one of its neighbor nodes, which has the
   most neighbor nodes to forward the routing request message, the odds
   of finding the DAG root node or the member of a DAG (directed
   acyclic graph) is much larger.

   (2) The nodes receiving the above message choose two of its neighbor
   nodes, which have the most neighbor nodes and send the routing
   request message to them. It is noted that the node SHOULD choose
   other nodes except for the source nodes, thus avoiding the situation
   that the routing request message is sent back to them.




Wang, et al.           Expires August 25, 2017                [Page 6]

 Internet-Draft     Energy Optimization Routing Scheme     February 2017


   (3) The above two nodes which receive the routing request message
   choose three neighbor nodes which have the most neighbor nodes and
   broadcast routing request message to them. All the nodes broadcast
   the message according to the aforementioned rule. To put it simply,
   the nodes broadcast the routing request message after receiving it
   through the increasing broadcast. When the node chooses the neighbor
   nodes with the most neighbors, the number will be increased by one
   on the basis of the prior choice. The energy can be saved and the
   area of seeking the DAG root node is also expanded at the same time.

   (4) When the increasing broadcast reaches the largest hop and the
   last hop is not the DAG root node or the member of a DAG, the
   routing request message will be discarded directly. If the DAG root
   node or the member of a DAG is found in the process of finding, the
   routing request message will be stopped to forward to other nodes
   and the routing response message will be sent back to source node.

3.3. The implementation of the scheme

   Because the nodes seek DAG root node or the member of a DAG by using
   flooding broadcast in the original routing scheme, the energy is
   consumed largely. Worse still, the DAG root node is mobile in lots
   of mobile routing algorithms which focus on the balance of the
   energy in the LLNs. When the nodes outside the topology find the DAG
   root node, it may move to another place when the data is transmitted
   to it, thus causing the loss of the data. The document proposes an
   energy optimization routing scheme based on above-mentioned
   increasing broadcast. It can be used to seek DAG root node with low
   energy consumption, meanwhile, it guarantees the success of data
   transmission. As a result, the overhead of the network energy is
   lowered and the reliability of data transmission is ensured. The
   detailed scheme is shown as follows:

   (1) Due to the fact that the DAG root node only maintains a DAG in
   an area of limited hops and there exist many DAGs with the mobile
   DAG root node in the network, a part of nodes in the network belong
   to the DAG while others are outside of the DAG. Firstly, the node
   SHOULD be determined whether it is a member of a DAG.

   (2) When the node that is going to transmit the data is a member of
   a DAG, the data will be transmitted to its father node directly. And
   the father node will finally transmit the data to the DAG root node.

   (3) When the node that is going to transmit the data is not a member
   of a DAG, it will send routing request message to neighbor nodes by
   means of increasing broadcast so as to find the DAG root node and
   transmit data to it. It needs to be noted that the node is pre-


Wang, et al.           Expires August 25, 2017                [Page 7]

 Internet-Draft     Energy Optimization Routing Scheme     February 2017


   configured a largest hop before sending the routing request message.
   When the increasing broadcast reaches the largest hop and the node
   of the last hop is not the DAG root node or a member of a DAG, the
   routing request message will be discarded. In addition, the node of
   last hop will send a message of failure back to the source node, and
   the source node directly broadcast the routing request message to
   every node in the network.

   (4) If the DAG root node or the member of a DAG is found through the
   increasing broadcast, the routing request message is sent to it by
   the source node. And the source node will receive a routing response
   message from the DAG root node or the member of a DAG. The routing
   response message includes the time for which the DAG root node stays
   in the present DAG and the number of hops between the DAG root node
   and the source node.

   (5) The source node selects the DAG root node whose standing time is
   greater than the transmission time according to the routing response
   message. And then the source node continues selecting the closest
   DAG root node to transmit the data. The transmission time (Tn) is
   obtained by the formula Tn=nT1, where n means the hops between the
   source node and the DAG root node, and T1 denotes the mean
   transmission time per hop.

4. Security Considerations

   TBD.

5. IANA Considerations

   This memo includes no request to IANA.

6. Acknowledgements

   Thanks to the authors of RFC 6550 RFC 6551 RFC 6554 and RFC 6552.
   The authors would like to acknowledge the review, feedback, and
   comments.











Wang, et al.           Expires August 25, 2017                [Page 8]

 Internet-Draft     Energy Optimization Routing Scheme     February 2017


7. References

7.1. Normative References

7.2. Informative References

[RFC6550]
           Winter, T., P. Thuber, and B. Brandt. "RFC 6550: IPv6 Routing
           Protocol for Low-Power and Lossy Networks." Internet
           Engineering Task Force (IETF) Request For Comments (2008).

[RFC6551]
           Vasseur, J. P., et al. "RFC 6551: Routing Metrics Used for
           Path Calculation in Low-Power and Lossy Networks." Internet
           Engineering Task Force (IETF) Request For Comments (2012).

[RFC2119]
           RFC2119, RFC2119. "Key words for use in RFCs to Indicate
           Requirement Levels." (1997).





























Wang, et al.           Expires August 25, 2017                [Page 9]

 Internet-Draft     Energy Optimization Routing Scheme     February 2017


Authors' Addresses

   Hao Wang
   Key Laboratory of Industrial Internet of Things & Networked Control
   Ministry of Education
   Chongqing University of Posts and Telecommunications
   2 Chongwen Road
   Chongqing, 400065
   China

   Email: wanghao@cqupt.edu.cn

   Min Wei
   Key Laboratory of Industrial Internet of Things & Networked Control
   Ministry of Education
   Chongqing University of Posts and Telecommunications
   2 Chongwen Road
   Chongqing, 400065
   China

   Email: weimin@cqupt.edu.cn

   Shuaiyong Li
   Key Laboratory of Industrial Internet of Things & Networked Control
   Ministry of Education
   Chongqing University of Posts and Telecommunications
   2 Chongwen Road
   Chongqing, 400065
   China

   Email: lishuaiyong@cqupt.edu.cn

   Qingqing Huang
   Key Laboratory of Industrial Internet of Things & Networked Control
   Ministry of Education
   Chongqing University of Posts and Telecommunications
   2 Chongwen Road
   Chongqing, 400065
   China

   Email: huangqq@cqupt.edu.cn

   Ping Wang
   Key Laboratory of Industrial Internet of Things & Networked Control
   Ministry of Education
   Chongqing University of Posts and Telecommunications
   2 Chongwen Road


Wang, et al.           Expires August 25, 2017               [Page 10]

 Internet-Draft     Energy Optimization Routing Scheme     February 2017


   Chongqing, 400065
   China

   Phone: (86)-23-6246-1061
   Email: wangping@cqupt.edu.cn

   Chaomei Wang
   Key Laboratory of Industrial Internet of Things & Networked Control
   Ministry of Education
   Chongqing University of Posts and Telecommunications
   2 Chongwen Road
   Chongqing, 400065
   China

   Email: wangcm24@126.com

































Wang, et al.           Expires August 25, 2017               [Page 11]