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]