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]