6TiSCH Working Group Seo Hyang Kim
Internet-Draft Seoul National University
Intended status: Standards Track Na Eon Kim
Expires: June 17, 2017 Seoul National University
Nguyen Duc Lam
Seoul National University
Chong Kown Kim
Seoul National University
December 15, 2016
Autonomous Link-based TSCH Cell Scheduling
draft-3k1n-6tisch-alice0-01
Abstract
This document describes the limitation of present TSCH cell
scheduling methods which use centralized or decentralized approach.
It firstly overview pros and cons of various cell scheduling
approaches including centralized, decentralized and autonomous TSCH
cell scheduling methods. It also suggest design considerations on
devising autonomous scheduling approach to avoid unexpected
confliction and increase channel utilization. For the last, it
provides one example that reflects all design considerations
mentioned.
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). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
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."
This Internet-Draft will expire on June 17, 2017.
Kim, et al. Expires June 17, 2017 [page 1]
Internet-Draft ALICE December 2016
Copyright Notice
Copyright (c) 2016 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 . . . . . . . . . . . . . . . . . . . .. . . . . . 3
2. Requirements Language . . . . . . . . . . . . . . . . . . . . . 3
3. Terminology. . . . . . . . . . . . . . . . . . . . . . . . . . 3
4. TSCH Cell Scheduling. . . . . . . .. . . . . . . . . . . . . . 3
4.1. Centralized Approach . . . . . . . . . . . . . . . . . . 4
4.2. Decentralized Approach. . . . . . . . . . . . . . . . . 5
4.3. Autonomous Approach . . . . . . . . . . . . . . . . . . 5
5. Design Considerations for Autonomous TSCH Cell Scheduling . . . 6
5.1. Link-based scheduling . . . . . . . . . . . . . . . . . 6
5.2. Hop-count-based scheduling . . . . . . . . . . . . . . . 7
5.3. SlotframeID . . . . . . . . . . . . . . . . . . . . . . 7
5.4. Upstream: link-based, Downstream: node-based . . . . . . 7
5.5. Upstream downstream scheduling . . . . . . . . . . . . . 8
6. ALICE overview . . . . . . . . . .. . . . . . . . . . . . . . 8
6.1. Link-based scheduling . . . . . . . . . . . . . . . . . 9
6.2. Hop-count-based scheduling . . . . . . . . . . . . . . . 9
6.3. SlotframeID . . . . . . . . . . . . . . . . . . . . . . 9
6.4. Upstream: link-based, Downstream: node-based . . . . . . 10
6.5. Upstream downstream scheduling . . . . . . . . . . . . . 10
7. ALICE details . . . . . . . . . . . . . . . . . . . . . . . . . 10
7.1. Upstream cell scheduling. . . . . . . . . . . . . . . . . 11
7.1.1. Recieve scheduling . . . . . . . . . . . . . . . . 11
7.1.2. Send scheduling. . . . . . . . . . . . . . . . . . 11
7.2. Downstream cell scheduling. . . . . . . . . . . . . . . . 11
7.2.1. Recieve scheduling . . . . . . . . . . . . . . . . 11
7.2.2. Send scheduling. . . . . . . . . . . . . . . . . . 11
7.3. Upstream and Downstream Scheduling. . . . . . . . . . . . 12
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 12
9. Security Considerations . . . . . . . . . . . . . . . . . . . 12
10. Acknowlegement. . . . . . . . . . . . . . . . . . . . . . . . 12
11. References. . . . . . . . . . . . . . . . . . . . . . . . . . . 13
11.1. Normative References. . . . . . . . . .. . . . . . . . . 13
11.2. Informative References. . . . . .. . . . . . . . . . . 13
Authors' Addresses . . . . . . . . . . . . . . . . . . . . .. . . . 14
Kim, et al. Expires June 17, 2017 [page 2]
Internet-Draft ALICE December 2016
1. Introduction
In the communication using TSCH, multiple channels can be used
simultaneously and channel hopping is used. It is different from
traditional ZigBee communication. With increasing interest on IoT
network, various TSCH cell scheduling method has been provided. This
document describes the limitation of present TSCH cell scheduling
methods which mainly use centralized or decentralized approach. It
firstly overview pros and cons of various cell scheduling approaches
including centralized, decentralized and autonomous TSCH cell
scheduling methods.
Specifically, this document focus on autonomous approach. The biggest
benefits of autonomous scheduling method is its simple and light
scheduling without any negotiation and its quick response to the
sudden network changes.
This document also suggest design considerations on devising
autonomous scheduling approach to avoid unexpected confliction and
increase channel utilization. For the last, it provides one example
that reflects all design considerations mentioned: Autonomous Link-
based TSCH Cell Scheduling (ALICE).
2. Requirements Language
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 RFC 2119 [RFC 2119].
3. Terminology
Cell : This document follows the same definition used in [RFC 7554]
ASN : This document follows the same definition used in [RFC 7554]
Slotframe : This document follows the same definition used in
[RFC 7554]
LinkNum : In the IoT sensor network, nodes and links form a graph and
each link has a node at both ends. LinkNum of specific link is
defined as the sum of NodeIDs of two connected nodes with that link.
SlotframeID : ID of the slotframe in the TSCH network.
4.TSCH cell scheduling
Regarding TSCH cell scheduling, detailed description is provided in
[RFC 7554]. Here, we briefly overview important characteristics used
in this document.
Kim, et al. Expires June 17, 2017 [page 3]
Internet-Draft ALICE December 2016
chOff ^ Slotframe
|
- +-----------------------------------------+
| | | B | | | | |
| +-----------------------------------------+
| | | | C | | | |
M | +-----------------------------------------+
| | | F | | | D,G | |
| +-----------------------------------------+
| | A | | | | | E |
_ +-----------------------------------------+---> Time
___________________________________________
Z
Figure 1: Structure of TSCH slotframe
In the communication using TSCH, multiple channels can be used
simultaneously and channel hopping is used. It is different from
traditional ZigBee communication. In TSCH, slotframe repeats over
time and the slotframe length is defined as the number of time
offsets. In Figure 1, one example of TSCH slotframe is described. In
this example, the number of channel offsets is M=4 and the number of
time offsets is Z=6. Z is also a slotframe length. The total number
of cells that is available in a slotframe is M*Z=24. In the example,
only 6 cells are scheduled in the slotframe. If two closely located
nodes try to send packets in the same cell, it will conflict and the
transmission of the both users will fail. So to avoid confliction
while achieving high channel utilization and energy efficiency, wise
and canny scheduling method should be used in TSCH cell scheduling.
Present method can be mainly categorized by two major approaches:
Centralized and decentralized scheduling.
4.1. Centralized approach
In the IoT sensor network using centralized TSCH cell scheduling
approach, one representative node schedules wakeup and sleep of every
node in the same network. Since only one node schedules the whole
communication in the network, for that node, large amount of
information is needed. Depending on the algorithm, various
information can be used and an optimized scheduling can be realized.
However, since only one specific node can execute TSCH cell
scheduling, quick action cannot be executed when the network topology
has been changed suddenly. Moreover, every node has to deliver the
information that will be used in the scheduling node, which causes
communication overhead using additive energy and bandwidth resources.
Furthermore, centralized approach takes long time for the
initialization.
* We categorize following kinds of scheduling as centralized
approach.
Kim, et al. Expires June 17, 2017 [page 4]
Internet-Draft ALICE December 2016
The network is divided into multiple regions. In each region, one
centralized scheduler executes centralized TSCH cell scheduling for
every node located in the same region with that node. In this
network, though multiple schedulers execute TSCH cell scheduling, it
is not fully decentralized manner. Rather, it can be viewed as a
combination of multiple centralized scheduling.
4.2. Decentralized approach
In the IoT sensor network using decentralized TSCH cell scheduling
approach, every node can schedule their own plan for wakeup and sleep
time. Each node communicate with their neighbors to avoid confliction
caused by simultaneous same channel usage among interfering nodes. To
implement this network, specific negotiation protocol should be
decided. Compared to the centralized approach, each node using the
decentralized TSCH cell scheduling approach needs only small amount
of information received from their close neighbors. As a result, it
is robust for a sudden network change compared to the centralized
approach. However, because of the scanty information, decentralized
approach lacks visibility on the view of the whole network.
4.3. Autonomous approach
Though decentralized approach shows quick response for the sudden
changes of network topology, it still needs additive communication
for the negotiation between neighbors. In the autonomous approach,
no negotiation is needed for the TSCH scheduling. One representative
method has been proposed in [Orchestra-Sensys15]. They only use
information received from RPL routing protocol [RFC 6550]. They do
not use additive communication for the negotiation among the
neighbors in TSCH cell scheduling. They autonomously calculate their
own plan on cell usage based on the RPL structure. They use NodeID
such as MAC address of their RPL parent node. With this method,
node-based cell scheduling is executed. For example, in the
receiver-based scheduling, receiving nodes are scheduled on the TSCH
cells. Scheduled node listen at the corresponding cell and any node
who wants to send packet to that node wakeup and send packet to the
receiving node at the same cell. Sender-based scheduling executes in
the similar manner.
Including the above method [Orchestra-Sensys15], though autonomous
TSCH cell scheduling approach also lacks other available information,
the biggest benefits of this approach is its simple and light
scheduling without any negotiation and its quick response to the
sudden network changes.
Kim, et al. Expires June 17, 2017 [page 5]
Internet-Draft ALICE December 2016
5. Design considerations of autonomous TSCH cell scheduling method
This section describes the design considerations for autonomous TSCH
cell scheduling.
In the design of TSCH cell scheduling, one of the biggest challenge
is to make scheduling by avoiding confliction among interfering
nodes. However, since autonomous scheduling does not use any
negotiation, it lacks information. In this condition, the thing that
autonomous scheduler can do is to reduce the probability of
confliction.
+---+
| A |
+---+
/ \
/ \
+---+ +---+
| B | | C |
+---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| D | | E | | F | | G |
+---+ +---+ +---+ +---+
/ \ / \ / \ / \
H I J K L M N O
Figure 2: Nodes and Links in the Tree Topology
5.1. Link-based scheduling
Consideration 1: One node cannot receive packets from the two
different nodes simultaneously at the same timeslot. For example, in
the topology described in Figure 2, in the upstream transmission,
node B is connected to both node D and node E. If these two child
nodes send packets to the node B at the same timeslot, B will fail to
listen both two packets successfully. In this situation, the link D-B
and the link E-B can be scheduled in the same channel offset or in
the different channel offsets. In the former case, if two child node
sends packet simultaneously at the same time offset, two transmission
will be conflict at the same channel and B cannot receive any packet.
In the latter case, depending on the node B's selection of the
channel offset to listen at, one of the packets sent from the node A
or the node B can be received successfully.
Kim, et al. Expires June 17, 2017 [page 6]
Internet-Draft ALICE December 2016
5.2. Hop-count-based scheduling
Consideration 2: One node cannot listen and send packets
simultaneously at the same timeslot. For example, in the topology
described in Figure 2, in the upstream, node B is connected to both
node A and node D. If the link B-A and the link D-B is scheduled at
the same timeslot, node D will send to the node B and the node B will
send to the node A. However, node D cannot listen and send
simultaneously at the same timeslot.
5.3. SlotfrmaeID
Consideration 3: In the view of one specific node, the scheduling of
different slotframes should be changed to avoid consistent
confliction. If the scheduling result for a slotframe persists, the
conflicting nodes in a cell will conflict again at the next
slotframe. For example, in the topology described in Figure 2, in the
upstream, there are two links B-A and C-A. If these links are
scheduled in the same cell and node B and node C send packets to the
node A at the same timeslot, two packet transmissions will fail. If
this scheduling persist at the next slotframe, the same situation
will occur again.
5.4. Upstream: link-based, Downstream: node-based
Consideration 4: Cell scheduling method of upstream and downstream
should be differentiated. In the case of IoT network, the amount of
upstream traffic is much larger than that of downstream traffic.
Moreover, if tree topology is used for the routing protocol as
described in Figure 2, one node has multiple child nodes and only one
parent node. In this structure, in the case of upstream, every child
node has different packets to send to their parent node. So one node
should listen from their multiple child using different cells.
However, in the case of downstream, the server may request or respond
to every node in the network or to the one specific node. Moreover,
the amount of downstream packets are smaller than that of upstream
packets and the scheduled cell for downstream may not be used with
high probability. So, in the topology described in Figure 2, when the
link B-D and the link B-E is scheduled, scheduling these two links at
the same cell is more efficient than scheduling these links at the
different cells. By doing this, in the case where the server sends
one packet to every node in the network, node B can forward this
message to all their child nodes at only one transmission. In the
other case where the node B sends a packet to one of its child nodes,
it can send the packet to the specific node while multiple child
nodes listen at the same timeslot.
Kim, et al. Expires June 17, 2017 [page 7]
Internet-Draft ALICE December 2016
5.5. Upstream downstream scheduling
Consideration 5: One node cannot receive or send packets from both
their parent node and child node simultaneously. In other words, in
the view of one specific node, upstream and downstream can not be
happen at the same timeslot. For example, in the topology described
in Figure 2, the node B is connected to both node A and node D. If
both node A and node D is scheduled to send packets to the node B at
the same timeslot, or the node B is scheduled to send packets to the
node A and the node D at the same timeslot as a result of cell
calculation by using autonomous scheduling method, at least one
transmission will fail since node B cannot receive different packets
from the different nodes and send different packets to the different
nodes.
6. ALICE overview
In this section, we define Autonomous LInk-based tsch CEll
scheduling (ALICE). This scheduling method reflects 5 design
considerations described above. To use autonomous scheduling
approach, ALICE utilizes limited information on the basis of RPL
routing topology as shown in [Orchestra-Sensys15]. By using all 3
types of RPL messages (DIS, DIO and DAO), each node using ALICE knows
NodeID (e.g. MAC address) of their parent and child nodes. They use
another information such as Absolute Slot Number (ASN) and RPL
hop-count.
chOff ^ Slotframe
| Even Rank || Odd Rank |
- +--------------------||--------------------+
| | L->F | C->A | M->F || F->C | | |
| | | | || | | |
| +--------------------||--------------------+
| | I->D | | J->E || | G->C | |
| | | | O->G || | | |
M | +--------------------||--------------------+
| | | H->D | || | D->B | |
| | | | || | | |
| +--------------------||--------------------+
| | B->A | | N->G || | | E->B |
| | K->E | | || | | |
- +--------------------||--------------------+---> Time
|__________________________________________|
Z
Figure 3: Autonomous Link-based TSCH Cell Scheduling (ALICE)
Kim, et al. Expires June 17, 2017 [page 8]
Internet-Draft ALICE December 2016
6.1. Link-based scheduling
In ALICE, the tree topology is used for the routing protocol as RPL
is used together with TSCH. In its TSCH cell scheduling, every link
in the tree topology is scheduled at least once a slotframe. For
example, in Figure 2, there are 13 links and each link is scheduled
in a cell in a slotframe as described in Figure 3. Since ALICE uses
link-based scheduling, we allocate LinkNum to every link. LinkNum is
the sum of NodeIDs of two connected nodes with that link. For
example, in the Figure 2, node A and node B is connected with the
link A-B. Then, LinkNum of the link A-B is the sum of NodeID of node
A and that of node B. By using the value of LinkID, nodes in the
network autonomously calculate their plan for wakeup and sleep time.
6.2. Hop-count-based scheduling
By using hop-count-based scheduling, ALICE avoids the situation where
one node listens and sends simultaneously. With RPL, every node knows
their own hop-count. In this document, we call hop-count as rank.
Multiple cells in a slotframe is grouped into two different sections.
Even rank nodes are scheduled in the cells in the first section and
the odd rank nodes are scheduled in the the cells in the second
section.
6.3. SlotframeID
In ALICE scheduling, every slotframe has different cell scheduling
results since ALICE uses SlotframeID in their autonomous scheduling
algorithm. SlotframeID increases with time. SlotframeID is calculated
by flooring ASN%Z.
SlotframeID = floor(ASN%Z)
As Figure 4 describes, as SlotframeID changes, the result of cell
scheduling becomes completely different.
^
chOff |
+-----------------------------------------------+
| | B | | | | |F | | |D | | |
+-----------------------------------------------+
| | |C | | | | |A | | | | |
+-----------------------------------------------+
| | F | | |D,G| | | | | |E | |
+-----------------------------------------------+
#chOff=0 |A | | | | |E |C | |B | | |G |
+-----------------------------------------------+-->Time
|-----------------------|-----------------------|
Z Z
Figure 4: Differenct slotframes have different cell scheduling results
Kim, et al. Expires June 17, 2017 [page 9]
Internet-Draft ALICE December 2016
6.4. Upstream: link-based, Downstream: node-based
ALICE uses different scheduling style for uplink and downlink
streams. For the upstream, it has link-based scheduling approach and
for the downstream, it has node-based scheduling approach as
[Orchestra-Sensys15].
6.5. Upstream downstream scheduling
Since the amount of upstream traffic is much more than that of
downstream traffic, ALICE give more chance for the upstream traffic
compared to the downstream traffic in its cell scheduling. For
example, with the length K for a slotframe-cycle, K-1 slotframes are
allocated for the upstream and 1 slotframe is allocated for the
downstream. More specific example is described in Figure 5. If K=3,
2 slotframes are allocated for the upstream and 1 slotframe is
allocated for the downstream.
^ [ K=3 ]
chOff |
+-----------+-----------+-----------++-----------+--
| | B | | | C | D | C | | B || A | | E |
+------------------------------------------------+--
| E | C | | |A,B| | E | | A || | C | |
+------------------------------------------------+--
0 | A | | D | E | | | | D | || | B | D |
+-----------+-----------+-----------++-----------+---->Time
|-----Z-----+-----Z-----|-----Z-----||-----Z-----|--
|........uplink.........|..downlink.||......uplink..
|______________1cycle_______________||______1cycle__
Figure 5: Upstream and Downstream Scheduling
7. ALICE details
In this section, we define ALICE scheduling details. In the network
with ALICE, every node has ALICE scheduler and calculates specific
cells for send or receive packets autonomously on the basis of
LinkNum, SlotframeID and Rank. As defined above, LinkNum of one link
is defined on the basis of NodeID of two nodes that is connected with
that link. SlotframeID is on the basis of ASN. To calculate the
specific ChannelOffset and the TimeOffset, ALICE uses hash function
as [Orchestra-Sensys15] does.
Here, we use M and Z for the number of channel offsets and the number
of time offsets in a slotframe, respectively.
Kim, et al. Expires June 17, 2017 [page 10]
Internet-Draft ALICE December 2016
7.1. Upstream cell scheduling
In the upstream traffic, a node receives packets from its child nodes
and sends packet to its parent node. Upstream cell scheduling is done
only in the upstream period.
7.1.1. Receive Scheduling
TimeOffset = (NodeRank%2)*(Z/2) +Hash(NodeID+ChildID+SlotframeID)
%(Z/2)
ChannelOffset = Hash(ChildID+SlotframeID)%M
7.1.2. Send Scheduling
TimeOffset = (ParentRank%2)*(Z/2) + Hash(ParentID+NodeID+SlotframeID)
%(Z/2)
ChannelOffset = Hash(NodeID+SlotframeID)%M
7.2. Downstream cell scheduling
In the downstream traffic, a node receives packet from its parent
node and sends packet to its child nodes. Downstream cell scheduling
is done only in the downstream period.
7.2.1. Receive Scheduling
TimeOffset = (ParentRank%2)*(Z/2) + Hash(ParentID+SlotframeID)%(Z/2)
ChannelOffset = Hash(ParentID+SlotframeID)%M
7.2.2. Send Scheduling
TimeOffset = (NodeRank%2)*(Z/2) + Hash(NodeID+SlotframeID)%(Z/2)
ChannelOffset = Hash(NodeID+SlotframeID)%M
Kim, et al. Expires June 17, 2017 [page 11]
Internet-Draft ALICE December 2016
7.3. Upstream and Downstream Scheduling
K is the number of slotframes in a group that is composed multiple
slotframes during a pair of one upstream period and one downstream
period. In other words, in each cycle, one downstream period and one
upstream period are shown. Since the amount of upstream traffic is
much more than that of downstream traffic, the number of cells for
the upstream traffic should be larger than that of downstream
traffic. Since the number of cells in a timeslot does not change,
longer time is allocated for the upstream period compared to
downstream period. During the upstream period, upstream cell
scheduling is executed and during the downstream period, downstream
cell scheduling is executed. Decision of upstream and downstream
period is simple as follows. The algorithm is on the basis of
SlotframeID and the parameter K.
If (SlotframeID%K==0)
Downstream period
Else
Upstream period
End
8. IANA Considerations
There are no IANA considerations related to this document.
9. Security Considerations
Autonomous TSCH cell scheduling method has similar requirements on
security as [RFC7554].
10. Acknolwedgement
This work was supported by Institute for Information & communications
Technology Promotion(IITP) grant funded by the Korea government(MSIP)
(No.B0190-16-2017,Resilient/Fault-Tolerant Autonomic Networking Based
on Physicality, Relationship and Service Semantic of IoT Devices),
the MSIP(Ministry of Science, ICT and Future Planning), Korea, under
the ITRC(Information Technology Research Center) support program
(IITP-2016-R0992-16-1023) supervised by the IITP(Institute for
Information & communications Technology Promotion and the National
Research Foundation of Korea(NRF) Grant funded by the Korean
Government(MSIP) (No.2016R1A5A1012966).
Kim, et al. Expires June 17, 2017 [page 12]
Internet-Draft ALICE December 2016
11. Reference
11.1. Normative References
[RFC 7554] T. Watteyne, Ed., L. Grieco, "Using IEEE 802.15.4e
Time-Slotted Channel Hopping (TSCH) in the Internet of
Things (IoT): Problem Statement", RFC 7554, May 2015
[RFC 6550] T. Winter, Ed., P. Thubert, Ed., A. Brandt, J. Hui,
R. Kelsey, P. Levis, K. Pister, R. Struik, JP. Vasseur,
R. Alexander, "RPL: IPv6 Routing Protocol for Low-Power
and Lossy Networks", RFC 6550, March 2012
11.2. Informative References
[Orchestra-Sensys15] Duquennoy, Simon, et al. "Orchestra: Robust mesh
networks through autonomously scheduled TSCH."
Proceedings of the 13th ACM Conference on
Embedded Networked Sensor Systems. ACM, 2015.
Kim, et al. Expires June 17, 2017 [page 13]
Internet-Draft ALICE December 2016
Authors' Addresses
Seo Hyang Kim
Department of Computer Science and Engineering
Seoul National University
Seoul, South Korea
Phone: +82 (0)2 880 1858
Email: shkim@popeye.snu.ac.kr
Na Eon Kim
Department of Computer Science and Engineering
Seoul National University
Seoul, South Korea
Phone: +82 (0)2 880 1858
Email: nekim@popeye.snu.ac.kr
Nguyen Duc Lam
Department of Computer Science and Engineering
Seoul National University
Seoul, South Korea
Phone: +82 (0)2 880 1858
Email: lam@popeye.snu.ac.kr
Chong Kwon Kim
Department of Computer Science and Engineering
Seoul National University
Seoul, South Korea
Phone: +82 (0)2 880 1858
Email: ckim@snu.ac.kr
Kim, et al. Expires June 17, 2017 [page 14]