The Love-Hate Relationship between IEEE802.15.4 and RPL Oana Iova, Fabrice Theoleyre, Thomas Watteyne, Thomas Noel

Abstract-Low-Power Lossy Networks (LLNs) are at the core of many Internet of Things solutions. Significant standardization effort has been put in creating a protocol stack suited for LLNs. Among these standards, IEEE802.15.4-2011 and RPL allow LLN devices to form a multi-hop mesh network. Today, RPL creates a routing topology without a priori knowledge about the topology created at the MAC layer. This negatively impacts the number of redundant paths, their quality, and the overall performance of the routing protocol. In this article, we highlight the need for an intermediate layer between MAC and network layers to solve these problems. We describe the protocols to be used in future Internet of Things, emphasize their weaknesses when deployed together, and provide areas of improvement.

Index Terms-IEEE802. 15.4, RPL, LLN, Internet of Things, joint optimization, topology control, link metric, dynamics.

I. INTRODUCTION

Miniaturization of computation and communication solutions has enabled the creation of small, durable, and inexpensive wireless devices often called "motes". Motes can be programmed to interconnect wirelessly, and form a multi-hop low-power wireless network, known as a "Low-Power and Lossy Network" (LLN). LLNs are one of the core technologies in the Internet of Things (IoT). LLN protocols and standards need to take into account their specific constraints in terms of energy, memory, and processing power.

The IEEE and IETF, two major Standards Development Organizations (SDOs) in the telecommunication arena, have published several standards that contribute to the creation of a fully standards-based protocol stack for LLNs. IEEE802. 15.4 [1] is arguably the standard with the most impact on lowpower wireless technology. It defines both the physical layer (i.e., modulation scheme, data rate) and the Medium Access Control (MAC) layer for low-rate Wireless Personal Area Networks (WPANs). In 2012, the IETF ROLL working group published the "IPv6 Routing Protocol for Low-Power and Lossy Networks" (RPL) [START_REF] Winter | RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks[END_REF], which enables low-power devices to form a multi-hop topology. Because of energy constraints, the focus was given to single interface nodes.

While blind layer separation allows modularity, it also comes with some limitations, especially in constrained environments. An LLN is a canonical example of a constrained Manuscript received December 20, 2016. Oana Iova is with University of Strasbourg, France and University of Trento, Italy (email: oanateodora.iova@unitn.it, address: University of Trento, Department of Information Engineering and Computer Science (DISI), via Sommarive 9, I-38123 Povo (TN), Italy, Tel: +39 0461 28 3992). Fabrice Theoleyre and Thomas Noel are with the CNRS, University of Strasbourg, France (email: theoleyre@unistra.fr, noel@unistra.fr). Thomas Watteyne is with Inria, France (email: thomas.watteyne@inria.fr) network: a large number of low-end and energy-constrained devices form a multi-hop mesh network using unreliable links over which small packets can be transmitted at low data rate. In such an environment, there is a great potential for crosslayer optimization, where different (theoretically independent) layers could exchange information to coordinate their actions. In some cases, a sublayer might be introduced to perform adaptation between two layers otherwise unaware of each another. One such example is 6LoWPAN. Situated above the MAC layer, it compacts (long) IPv6 headers so they fit in (short) IEEE802.15.4 frames.

In this paper, we show the shortcomings of blind layer separation in the current protocol stack for LLNs, focusing on the MAC and network layers. In short, the contribution of this paper is:

• we propose to use the same topology control at the MAC and routing layer; • we highlight the instability problem of RPL when using the current routing metrics; • we propose to estimate the link quality by exploiting all the parents at the topology created by RPL.

II. A STANDARDS-BASED PROTOCOL STACK FOR LLNS

This section discusses the standards with the most impact on the LLN technology.

A. MAC layer: IEEE802.15.4-2011

The IEEE802.15.4 standard was introduced in 2003 to be used in WPANs. Two revisions later (2006,2011), and with one upcoming revision (2015), IEEE802.15.4 is arguably the standard with the highest impact on low-power wireless in general, and on the IoT in particular.

Link layer topology. In an IEEE802.15.4-2011 network, the devices are managed by a controller known as the "PAN coordinator" (or "sink", two terms which we use interchangeably in this paper). The standard defines two types of network topologies: star and peer-to-peer, both illustrated in Fig. 1a.

In a star topology, all devices communicate only with the PAN coordinator, over a single hop. While devices can run on batteries, the PAN coordinator is usually mains powered, as it needs to keep its radio on at all times.

In a peer-to-peer topology, communication is not restricted to the PAN coordinator. In contrast to a star topology, devices communicate with one another, enabling multi-hop connectivity. Multi-hop is a key feature in many IoT applications where not all nodes are deployed sufficiently close to the PAN coordinator to be in its radio range. The drawback of the peerto-peer topology is that a node must always stay awake as it can receive a packet from a neighbor at any time. A third topology, called "cluster-tree" can be used to overcome this. In a cluster-tree topology, a tree rooted at the PAN coordinator organizes the sleeping periods of the different router nodes to enable multi-hop communication with energy savings.

Medium access and energy efficiency. In IEEE802.15.4-2011, accessing the medium can be either done in a asynchronous (beacon-less) or synchronous (with beacons) mode.

In beacon-less mode, nodes use unslotted Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA), without exchanging request-to-send and clear-to-send (RTS/CTS) messages. In a multi-hop topology, all routing nodes must stay awake to be able to receive packets, which can be sent at any time. Preamble-sampling can reduce energy consumption: the transmitter node pre-sends a long preamble (a series of well-known bytes) to its packet; a receiver periodically samples the medium and stays on when it hears an on-going preamble. Unfortunately (besides breaking compliance with IEEE802.15.4, which does not include it), preamble sampling puts the energy burden on the transmitter, and significantly lowers the throughput of the network.

In beacon mode, IEEE802.15.4 cuts the time into superframes. Each superframe starts when the coordinator (possibly a router) sends a beacon. As we can see in Fig. 1b, this is followed by an active period (in which all transmitters compete using slotted CSMA/CA), and an inactive period (in which nodes sleep until the next beacon). The beacon mode saves energy in multi-hop topologies only when using the cluster-tree topology. As previously stated, in the peer-to-peer topology nodes have to always keep their radio on.

B. Routing over LLNs with RPL

RPL is a distance-vector routing protocol designed to scale to thousands of devices in an LLN. It organizes the topology in a Destination Oriented Directed Acyclic Graph (DODAG), a directed graph with no cycle. This DODAG is rooted at the sink (or at each sink when multiple sinks are present). To build the DODAG, RPL assigns a Rank to each mote, i.e., a virtual distance to the sink. An Objective Function defines how routing metrics (e.g., link quality, hop count) are used to compute a node's Rank. For example, if the objective is to create shortest paths, a node computes its Rank by adding a scalar value to the Rank of its preferred parent.

DODAG construction. The DODAG construction starts when the sink is switched on. It periodically broadcasts a DODAG Information Object (DIO), a control packet containing its Rank, as well as configuration parameters. When a joining node receives a DIO, it inserts the transmitter's address in its list of possible parents. From that list, it chooses its preferred parent as the node that advertises the smallest Rank1 . Once this parent-child relationship is established, a node forwards all packets for the sink through its preferred parent. After a node has computed its own Rank (usually using the Rank of its parent and link and node metrics), it starts periodically broadcasting its own DIOs.

Fig. 2 illustrates this DODAG construction routine. For simplicity, we use hop count (the number of hops to the sink) as routing metric. The Rank of a node is computed as the Rank of its parent plus a constant step value of 1. The sink R starts broadcasting DIO messages (Fig. 2a). The neighbors of R choose it as their preferred parent, compute their Rank, and start broadcasting their own DIOs (Fig. 2b). The network is fully formed when all the nodes have chosen their preferred parent (Fig. 2d).

The Trickle algorithm. Even after the RPL DODAG has formed, nodes keep transmitting DIOs to update the DODAG to topological changes. Unlike IEEE802.15.4, which sends beacons at a fixed rate, the rate at which the DIOs are being sent is tuned using the Trickle algorithm [START_REF] Levis | The Trickle Algorithm[END_REF]. The idea is for nodes to send less DIOs when the topology is stable, leading to a smaller energy consumption.

When a node receives DIO messages which contain the same information as the last ones, it doubles its own period for sending DIOs. When an inconsistency is detected (e.g., the Rank of the preferred parent has changed), the Trickle algorithm resets this period to an initial value. This causes the nodes to send DIOs more frequently, and the DODAG to adapt more quickly to the change.

C. Gotchas when Using Lossy Links

Wireless phenomena such as external interference and multi-path fading cause links to be unreliable. It is therefore crucial for a mote to continuously estimate the quality of the links to its neighbors, in order to choose the subset of "good" links to forward packets on. Routing metrics such as hop count are not enough, as nodes might elect a preferred parent which is close to the sink, but with which it has poor connectivity.

De Cuoto et al. propose to use the Expected Transmission count (ETX) [START_REF] Couto | A High-throughput Path Metric for Multi-hop Wireless Routing[END_REF] as a link metric, and use only "good" links. ETX estimates the number of required transmissions needed before the neighbor correctly receives the frame. It can also be used to estimate the energy cost associated with communicating over that link.

Yet, as highlighted by Liu et al. [START_REF] Liu | Performance Evaluation of Link Quality Estimation Metrics for Static Multihop Wireless Sensor Networks[END_REF] and Passos et al. [START_REF] Passos | Mesh Network Performance Measurements[END_REF], using ETX causes network churn (i.e., nodes changing routing parent) because of its greedy approach. That is, a node always searches for the link with the best (instantaneous) quality.

The IETF has defined several routing metrics [START_REF] Jp | Routing Metrics Used for Path Calculation in Low-Power and Lossy Networks[END_REF] that can be used by RPL to construct the DODAG:

• node metrics: node characteristics, hop count to the sink, and residual energy of the node; • link metrics: throughput, latency, link reliability, and link color (a semantic constraint).

Unlike RPL, IEEE802.15.4 does not specify any metric for the construction of its cluster-tree. Cuomo et al. propose to select the routing nodes based on the LQI (Link Quality Indicator) from the physical layer, or a combination of LQI and hop count [START_REF] Cuomo | Performance Analysis of IEEE 802.15.4 Wireless Sensor Networks: An Insight into the Topology Formation Process[END_REF].

It is very common for each layer (network, MAC) to use its own (routing, link) quality metric. We will show in the next section the limits of such approach.

III. EVALUATION, LIMITS AND RECOMMENDATIONS

In this section, we simulate a LLN and highlight its poor performance when the MAC and routing protocols are used independently, while offering guidelines for improvement.

A. Methodology

We simulate the behavior of RPL and IEEE802.15.4 on multi-hop networks in WSNet, a well-known network simulator for LLNs [START_REF] Ben Hamida | On the Complexity of an Accurate and Precise Performance Evaluation of Wireless Networks using Simulations[END_REF]. We use either the peer-to-peer topology of IEEE802.15.4 operating in beacon-less mode, or the cluster-DAG topology from [START_REF] Pavkovic | IEEE 802.15.4 and RPL Crossoptimization for Reliable Opportunistic Routing in WSN[END_REF] for the beacon-enabled mode (as stated in Section II-A, the peer-to-peer topology cannot be used together with the beacon mode). Table I lists the simulation parameters.

B. Topology Control

We are interested in how a node chooses the neighbors to communicate with, both at the MAC and routing layers. The problem is that under blind layer separation, decisions made by these layers might conflict. In this section, we evaluate how this affects network performance.

Context. Usually, the MAC layer only filters the neighbors a node may use. However, IEEE802.15.4 (the MAC layer) imposes a topology to the network: star, peer-to-peer or cluster-tree. If the MAC layer structures the network as a cluster-tree (Fig. 3a), the routing layer is presented with a topology without redundancy, and has to stick to the neighbors selected by the MAC layer (Fig. 3b).

A better solution is for the MAC layer to structure the network as a peer-to-peer topology (Fig. 3c). RPL then creates a redundant DODAG (see Fig. 3d, where D and E have redundant paths to the sink). The peer-to-peer mode does not, however, implement low radio duty-cycle, so the network's energy consumption is high.

To introduce redundancy at the MAC layer, while remaining energy efficient, Pavkovic et al. [START_REF] Pavkovic | IEEE 802.15.4 and RPL Crossoptimization for Reliable Opportunistic Routing in WSN[END_REF] propose to use a cluster-DAG in IEEE802.15.4-2011. This allows RPL to select multiple parents (Fig. 3e), at no extra costs: the same amount of DIOs are sent regardless the number of parents selected.

To avoid loops in the cluster-tree or the cluster-DAG, a path metric is required at the MAC layer, but none is defined in IEEE802.15.4. Here again, MAC and routing layers can be in conflict: if the MAC layer uses hop count, it creates a cluster-DAG with long and potentially bad links. Even if the routing protocol uses a different metric, it can only choose from MAC links. Hence, it will keep on using long and bad radio links, negatively impacting the network's reliability and energy consumption.

Having several applications run on the same network imposes further requirements. RPL can implement a DODAG instance per application, each DODAG potentially using a different routing metric. This requires the MAC layer to offer sufficient neighbor choices.

Evaluation. We quantify the impact of blind layer separation on topology control, through simulation.

Fig. 4a shows the Complementary Cumulative Distribution Function (CCDF) of the number of routing neighbors a node has, when using both cluster-DAG and peer-to-peer MAC topologies. The peer-to-peer MAC topology gives RPL a larger choice of neighbors, hence more diversity.

Fig. 4b illustrates the CCDF of the end-to-end Packet Delivery Ratio, when using either hop count or ETX at both MAC and routing layers. The network performs best when both MAC and network layers use ETX, offering the largest end-to-end reliability. In this case, MAC and routing layers make consistent decisions and use the links with the smallest ETX, improving the end-to-end reliability.

Recommendations. We recommend that the MAC protocol does not impose a topology to the network, but only filters out bad links (e.g., link with the quality below a certain threshold). It is up to the routing protocol to use the set of good links presented by the MAC layer and construct a multihop redundant routing topology.

C. Routing Topology Dynamics

Context. When a node changes its preferred parent, it resets its trickle timer, which generates more DIOs and a higher energy consumption. Changing parent too often is not efficient. One option is to limit parent changes by reducing the number of MAC neighbors. However, this also comes with the price of limiting routing diversity.

Evaluation. We quantify the impact of the number of neighbors on network dynamics by simulation. We implement the Minimum Rank with Hysteresis Objective Function (MRHOF) [START_REF] Gnawali | The Minimum Rank with Hysteresis Objective Function[END_REF], in which a node changes its preferred parent only when its new rank differs significantly from the old one.

Fig. 4c shows the CCDF of the average number of parent changes for a node, over a simulated hour, when both RPL and IEEE802.15.4 use ETX. A node changes its preferred parent more frequently when using a peer-to-peer MAC topology. It offers more choices, and a small variation in the link quality estimation can result in changing the preferred parent. Fig. 4c also confirms the conclusions of [START_REF] Iova | Stability and Efficiency of RPL under Realistic Conditions in Wireless Sensor Networks[END_REF] that parent changes are more frequent in larger networks.

Recommendations. To reduce the number of RPL parent changes, we recommend the use of hysteresis when estimating the link quality, such as the Window Mean with Exponentially Weighted Moving Average (WMEWMA). Several other techniques have been proposed in the literature, still WMEWMA offers the highest performance [START_REF] Woo | Taming the Underlying Challenges of Reliable Multihop Routing in Sensor Networks[END_REF].

D. Estimating Link Quality

Context. To estimate the quality of a link to a neighbor, a node can use statistics of data packets exchanged in the network. The main problem with this passive approach is that the estimation is done only for the neighbors the node communicates with. In an active approach, the node can send probe packets, at the cost of extra overhead. OpenWSN 1.9.0, Contiki 2.6 and TinyOS 2.1.2 all use the passive approach.

In RPL, a node communicates only with the preferred parent, so there is no way to estimate the link quality to the other neighbors. The preferred parent can be a set of parents if those parents are equally preferred. Still, RPL does not specify the forwarding rule. [START_REF] Lampin | Exploiting Long-range Opportunistic Links to Improve Delivery, Delay and Energy Consumption in Wireless Sensor Networks[END_REF] proposes for a node to send outgoing traffic to all its neighbors simultaneously. One parent will be selected opportunistically to forward the packets.

Evaluation. Fig. 4d plots the CCDF of the number of parent changes, when using a single parent or a set of parentst. Not only that the latter approach allows a node the estimate the link quality to several neighbors, but it also increases the stability of the routing topology.

Recommendations. We propose for a node to use all parents in its parent set to route packets to the root (not just the preferred one), allowing the quality to the links to all parents to be passively monitored.

E. Computing ETX

Context. The ETX of a link is defined as 1 P DR , with PDR the Packet Delivery Ratio of that link. The PDR is computed as the ratio between the number of acknowledgments received and the number of packets sent. Both Contiki and TinyOS compute ETX by simply counting the number of retransmissions, without taking into account packets dropped by the MAC layer (because of successive CCA failures or buffer timeout). Still, these dropped packets reflect the quality of those links.

Evaluation. Using the simulation setting from Section III-A, we observed that while only 0.05% of packets are dropped when using a peer-to-peer MAC topology, this ratio shockingly increases to 12% with the cluster-DAG. The latter can be attributed to additional contention because of the inactive periods of the beacon mode, and clearly should be taken into consideration when evaluating the quality of a link.

Recommendations. We recommend that the computation of ETX accounts for the packets dropped by the MAC layer, including because of successive CCA failures or buffer timeout.

IV. TOMORROW'S LLN TECHNOLOGY: IEEE802.15.4E TSCH AND IETF 6TISCH

The IEEE802.15.4e amendment was published in 2012, and introduces a radically new medium access control technique: Time Slotted Channel Hopping (TSCH). In a TSCH network, nodes are tightly synchronized, and time is cut into time slots. Slots are grouped in a slotframe, which continuously repeats over time. As depicted in Fig. 5, a slot is long enough (typically 10ms) for a node to send a packet to its neighbor, and for that neighbor to indicate successful reception through a link-layer acknowledgment (ACK).

Communication is orchestrated by a schedule which indicates to each node what to do in each slot: transmit, receive, or sleep. "Scheduling" a network corresponds to populating the slotframe with communication slots. Fig. 5 shows a canonical example schedule for the depicted topology. When E needs to communicate data to A, it sends the data packet to C at slot offset 1, on channel offset 2. C acknowledges successful reception (causing E to clear the data from its transmit buffer), after which C sends to A at slot offset 4, channel offset 3. The slotframe repeats continuously, giving the nodes repeated opportunities to communicate. Fig. 5 is simplified to be easily explained, real-world slotframes are 10's to 1000's slots long, with typically 16 channel offsets (when using the IEEE802.15.4 physical layer at 2.4GHz).

There is a subtle but important difference between channel offset and frequency. The schedule indicates the former; the channel offset is translated on-the-fly into a frequency through a pseudo-random hopping pattern each time the device turns its radio on. This means that, in successive slotframe iterations, the same channel offset translates into different frequencies. The result is "channel hopping": when two nodes communicate, successive retransmissions happen at different frequencies, thereby combating external interference and multi-path fading. [15] highlights the effectiveness of channel hopping in IEEE802.15.4 networks.

TSCH allows the network to be abstracted by its communication schedule. This schedule must be built to match link-layer resources (the cells) to the requirements of the applications running on the network. This allows a clean tradeoff between throughput, latency and energy consumption. IEEE802.15.4e does not define how to build or maintain the TSCH schedule. A "standardization gap" hence exists between the IEEE802.15.4e link-layer standard and upper layer standards such as 6LoWPAN, as neither define the entity responsible for building and managing the TSCH schedule.

The IETF 6TiSCH standardization working group was created in 2013 to fill this standardization gap by defining mechanisms to manage the TSCH communication schedule. 6TiSCH defines the 6top sublayer which operates at layer 2.5, between IEEE802.15.4e and 6LoWPAN. 6top offers a management interface (detailed below), and gathers statistics about each communication cell. Statistics include the number of transmitted frames in that cell, and the portion of those frames which were acknowledged.

6top supports centralized and distributed scheduling. In a centralized approach, the 6top sublayer of each node implements a CoAP-based management interface. This allows a central scheduling entity (called a Path Computation Element, PCE) sitting outside of the network to gather information about the topology of the network, compute an appropriate schedule, and configure each node with the cells of the schedule it participates in (using the CoAP application-level protocol). When using the distributed approach, no PCE is present in the network, and nodes need to agree on the schedule to use in a distributed fashion. The 6top sublayer implements a management interface allowing two neighbor nodes to negotiate adding/removing cells to one another. Communication happens through "Information Elements" in the IEEE802.15.4e header, fields which can serve as containers for a layer 2.5 protocol. In this distributed approach, a node monitors the transmission queue to each of its neighbors: if the queue overflows (resp. underflows), the node contacts its neighbor to negotiate to add (resp. remove) cells.

6TiSCH defines the mechanisms which support both centralized and distributed schedule management (packet formats and typical interaction). As a standardization entity, IETF 6TiSCH does not define the policy (when to use centralized/distributed, and the scheduling algorithm). Identifying the scheduling approach to adopt, and the associated limits is an open research problem. Intuitively, a centralized approach can compute near-optimal schedules, provided it has up-to-date information about the network topology and the needs of the applications running in the network. A distributed approach might be preferred when the topology is highly dynamic (e.g. a swarm of mobile robots), or when a PCE cannot be installed (e.g. a very simple home network where a PCE is not costefficient).

This paper highlights several issues which are closely related to the current standardization work at IETF 6TiSCH.

Topology control. The choice of the topology at the MAC layer impacts the diversity of the routes. 6TiSCH proposes to use shared slots for exchanging broadcast control packets such as DIOs. This allow RPL to use any neighbor as a parent; 6top is then in charge of negotiating dedicated slots between the node and its parent. This is directly in line with the recommendations done in Section III-B. What is missing in the 6TiSCH solution is a mechanism to modify the schedule on-the-fly in a distributed fashion.

Using different metrics. The 6top sublayer gathers cell statistics, which RPL uses to select the best routes. However, link metrics are needed to aggregate these statistics, some of which being TSCH-specific (e.g., per-frequency transmission counters). One option is to develop a unified link metric which encompasses both MAC and routing metrics. This remains an open research problem, especially when several applications run on the same network and RPL has to implement a DODAG instance per application.

Routing topology dynamics. TSCH uses channel hopping to make links more reliable, and the connectivity in the network more stable. However, capturing the variations over time, while not overreacting to inaccurate estimators remains an open challenge.

Link quality estimation (ETX) with 6TiSCH. 6top maintains per-cell statistics (including the number of packets sent and acknowledged). The ETX between two neighbor nodes is calculated by aggregating the statistics from the different cells scheduled between those nodes. What is missing is a way to discover neighbors a node is not communicating with, and estimate the quality of the link to that neighbor.

V. CONCLUSION Network performance depends not only on the MAC and routing protocols used, but also on their interaction. This article highlights the interaction between the topology defined at the MAC layer and the decision made by the routing protocol. Through simulation, we show that a peer-to-peer MAC topology yields higher performance compared to cluster-DAG topology, as it presents more neighbors to the RPL routing protocol. However, having more neighbors does mean that RPL might change a node's preferred parent more often (especially with large networks). Still, this article shows how using a set of parents and passive link quality estimation, reduces network churn.

These observations are being addressed by the new IETF 6TiSCH working group, which defines 6top, a sublayer between the link-layer (IEEE802.15.4e) and networking/routing layers (RPL). The resulting architecture, which combines the performance of IEEE802. 15

  Superframe structure of IEEE802.15.4.

Fig. 1 :Fig. 2 :

 12 Fig. 1: IEEE802.15.4-2011 concepts.

Fig. 3 :Fig. 4 :

 34 Fig. 3: Topology control using hop count as a metric.

Fig. 5 :

 5 Fig. 5: IEEE802.15.4e TSCH network example

  .4e TSCH with the an IPv6based upper stack has the potential of revolutionizing LLN technology. With the work already done, IETF 6TiSCH is starting to do so, but several challenges remain open, including the ones highlighted in this paper, i.e., an on-the-fly distributed reservation mechanism, and a link metric that combines MAC and routing statistics. BIOGRAPHIES Dr. Oana Iova is a Post-Doctoral Researcher at the University of Trento, where she works in the Department of Information Engineering and Computer Science (DISI). Her research interests include routing solutions for low power and lossy networks, and MAC protocols for multihop wireless networks. She received her Ph.D. from University of Strasbourg, France in 2014, and her M.S. degree in Computer Science from Ecole Normale Superieure de Lyon, France in 2011. Fabrice Theoleyre is a senior research scientist in the CNRS, and is now affiliated with ICUBE/University of Strasbourg. He received his PhD in computer science from INSA, Lyon (France) in 2006. He was a visiting researcher in INRIA Sophia-Antipolis in 2005 and a visiting scholar in University of Waterloo in 2006. He has been an associate editor for IEEE Communications Letters and a guest editor for Computer Communications and Eurasip JWCN. Thomas Watteyne is a researcher at Inria-Paris, in the EVA team, where he builds the Industrial Internet of Things. He is Senior Networking Design Engineer at Linear Technology/Dust Networks. He co-chairs the IETF 6TiSCH WG. Thomas completed his postdoctoral research at UC Berkeley, with Prof. Pister. He co-leads the OpenWSN project. In 2005-2008, he was research engineer at Orange Labs. He holds a PhD (2008), MSc (2005) and MEng (2005) in Telecommunications, INSA Lyon, France. Thomas Noel is professor at University of Strasbourg, France. His research activities include several aspects of wireless communications networks and telecommunications systems. He is particularly interested in: network mobility, self-organized mobile networks, mobile network architecture and protocols, wireless sensor networks, ubiquitous computing and multicast and group communications.

Alternatively, a node can choose its parent as the neighbor that gives it the smallest Rank; this takes into account the neighbor's Rank, and the cost of the link between the current node and the neighbor.


Member, IEEE Maria-Rita Rita Palattella
email: maria-rita.palattella@uni.lu

Thomas Watteyne
email: thomas.watteyne@inria.fr

Member, IEEE Qin Wang
email: wangqin@ies.ustb.edu.cn

Kazuki Muraoka
email: k-muraoka@eecs.berkeley.edu

Member, IEEE Nicola Accettura
email: accettura@eecs.berkeley.edu

Member, IEEE Diego Dujovne
email: diego.dujovne@mail.udp.cl

Senior Member, IEEE Luigi Alfredo Grieco
email: a.grieco@poliba.it

Member, IEEE. Thomas Engel
email: t.engel@uni.lu

Member, IEEE Kazushi Muraoka

K Muraoka

On-the-Fly Bandwidth Reservation for 6TiSCH Wireless Industrial Networks

Keywords: IEEE802.15.4e Sensor Networks, Timeslotted Channel Hopping, 6TiSCH Architecture, 6top, On-The-Fly (OTF) Bandwidth Reservation

published or not. The documents may come   L'archive ouverte pluridisciplinaire

I. INTRODUCTION

For a long time, industrial systems have relied on wired networks for robust and predictable communication. These networks connect sensing and control capabilities at different steps in the production process [START_REF] Decotignie | A Survey on Industrial Communication Networks[END_REF], [START_REF] Gaj | Computer Communication Within Industrial Distributed Environment: A Survey[END_REF]. The installation and maintenance costs of wires in an industrial setting have fueled the introduction of wireless technology. Yet, for wireless networks to be usable in this context, they need to fulfill two fundamental requirements: almost deterministic communication and robustness. These two constraints were first met by the Time Synchronized Mesh Protocol (TSMP) [START_REF] Pister | TSMP: Time Synchronized Mesh Protocol[END_REF]. In TSMP, time-scheduling enables precise end-to-end delay calculation, while frequency hopping reduces packet loss due to interference and multi-path fading.

To guarantee the interoperability of wireless sensor motes, the core concepts of TSMP were introduced into WirelessHART (2008) [START_REF]WirelessHART Specification 75: TDMA Data-Link Layer[END_REF], ISA100.11a (2011) [START_REF]Wireless Systems for Industrial Automation: Process Control and Related Applications[END_REF] and IEEE802. 15.4e (2012) [6]. While the first two standards define a complete protocol stack, the latter only defines the physical and three distinct Medium Access Control (MAC) layers: Low Latency Deterministic Network (LLDN), Timeslotted Channel Hopping (TSCH), and Deterministic and Synchronous Multi-channel Extension (DSME). Among these, the TSCH mode is the one facilitating multi-hop operation, and is able cope efficiently with external interference and multi-fading in distributed sensing and process control applications. The clean layering allows IEEE802. 15.4e TSCH to fit under an IPv6-enabled protocol stack for low-power wireless networks. This architecture was recently proposed by the IETF 6TiSCH Working Group (WG) 1 .

The IETF 6TiSCH WG, created in October 2013, is playing a key role introducing IPv6 [START_REF] Deering | Internet Protocol[END_REF] to industrial standards, and fostering the convergence between Operational Technology (i.e. industrial networks) and Information Technology (i.e. computer networks) [START_REF] Palattella | Internet of Things: Challenges and Opportunities[END_REF]. The goal of the 6TiSCH architecture [START_REF] Thubert | An Architecture for IPv6 over the TSCH mode of IEEE 802[END_REF] is an IPv6 multi-link subnet, including several Low Power and Lossy Networks (LLNs) connected by a high-speed backbone, through a number of Backbone Routers (BBRs). 6TiSCH "glues" together the IEEE802. 15.4e TSCH MAC layer with an IPv6-enabled upper stack (e.g. 6LoWPAN [START_REF] Shelby | Neighbor Discovery Optimization for IPv6 over Low-power Wireless Personal Area Networks (6LoWPANs)[END_REF], and the Routing Protocol for Low-Power and Lossy Networks, RPL [START_REF] Winter | RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks[END_REF]). TSCH, like TSMP, combines time synchronization with channel hopping: all sensor motes in the network follow a common schedule that specifies for each sensor mote at which time slot and on which channel it can communicate with its neighbors. The IEEE802.15.4e standard does not define how the schedule is built and matched to network traffic requirements.

To bridge this gap, 6TiSCH has defined the 6TiSCH Operation Sublayer (6top) [START_REF] Wang | 6TiSCH Operation Sublayer (6top)[END_REF], which (de)allocates resources within the schedule, while monitoring performance and collecting statistics. Different bandwidth reservation approaches are supported by the 6TiSCH architecture. A centralized approach is suitable for applications with static traffic patterns. This is the approach taken by industrial wireless standards such as WirelessHART (2008) [START_REF]WirelessHART Specification 75: TDMA Data-Link Layer[END_REF] and ISA100.11a (2011) [START_REF]Wireless Systems for Industrial Automation: Process Control and Related Applications[END_REF]. For applications with highly dynamic topologies and bursty data transmissions, distributed scheduling is an alternative.

For instance, when a Wireless Sensor Network (WSN) is deployed for continuous real-time monitoring of a given field, it is easier to estimate and tune the amount of traffic that each sensor mote has to deliver over the time and, hence, define a schedule using a centralized approach. Contrariwise, if the WSN is set up to detect an event, sensor motes will be almost silent over the time (except for unavoidable signaling messages) but they will start sending notifications upon the event they are looking for is detected. Under these circumstances, it is not possible to predict in advance the traffic patterns and a distributed approach would be more useful.

In safety-related industrial sensors applications, traffic can be bursty. For instance, gas leak detection [15], [START_REF] Murvay | A survey on gas leak detection and localization techniques[END_REF] must start transmitting at a higher sample rate to reduce the time to locate the leak, to calculate its magnitude, and to estimate the prospective evolution of this failure. Another example is monitoring grain silos to prevent fire or explosions [START_REF] Ogle | Explosion from a smoldering silo fire[END_REF]; sensor motes are programmed to change the data capture frequency and wake up secondary sensing devices when certain humidity, temperature, oxygen, or carbon monoxide levels are reached. During these bursts, a high packet loss cannot be tolerated.

On-The-Fly (OTF) bandwidth reservation [START_REF] Dujovne | 6TiSCH On-the-Fly Scheduling[END_REF] is a solution for distributed scheduling. Based on a bandwidth allocation algorithm, OTF dynamically matches the scheduled bandwidth between pairs of sensor motes to the actual traffic load. OTF decides when to add/delete resources, and the 6top sublayer then makes the appropriate changes to the TSCH schedule. The range of application domains where OTF can be applied spans from semi-centralized systems (in which a rapid reaction is needed when a surge in bandwidth is detected) and fully distributed systems (where neighbor motes negotiate bandwidth with one another without the intervention of a Path Computation Element, PCE).

Application examples of OTF as a distributed bandwidth reservation module include temporary monitoring deployments for specific magnitude measurement, such as vibration and strain in bridges [START_REF] Hu | A Wireless Sensor Network-Based Structural Health Monitoring System for Highway Bridges[END_REF]- [START_REF] Bocca | A synchronized wireless sensor network for experimental modal analysis in structural health monitoring[END_REF] where sensor motes reserve bandwidth dynamically according to the number of parameters, sampling rate and aggregate requirements. OTF can be used in industrial processes monitoring applications to take advantage of flexible bandwidth allocation. For example, transport belts in the mining industry [START_REF] Luo | Energy cost optimal operation of belt conveyors using model predictive control methodology[END_REF], [START_REF] Wang | Research on Control System of Belt Conveyor in Coal Mine[END_REF] require several sensing points such as misalignment switches, speed monitors, belt wear monitors and metal detectors. When the dynamics of the belt changes, it triggers a spike in data generation until a new equilibrium point is reached.

This article describes the 6top sublayer and the OTF bandwidth reservation module, and presents their performance through simulation. This article is not an attempt at answering which approach to use (centralized, distributed, hybrid), but rather shows the performance of OTF, and the first proof of concept, proving OTF can be implemented in low power sensor motes, in real scenarios.

The remainder of this article is organized as follows. Section II provides an overview of the IEEE802.15.4.e TSCH MAC and the 6top sublayer, on which OTF is built. Section III details the OTF mechanism, including the bandwidth allocation algorithm at its core. Section IV describes the 6TiSCH simulator used in this contribution and reports key performance indicators for OTF as well as its preliminary experimental evaluation. Section V concludes this article.

II. 6TISCH ARCHITECTURE

The OTF Bandwidth Reservation module is designed for 6TiSCH networks. The 6TiSCH architecture implements the IEEE802.15.4e TSCH link-layer protocol, the 6top sublayer, and the RPL routing protocol. The TSCH MAC and the 6top sublayer are described in more details in this section.

A. IEEE802.15.4e TSCH IEEE802. 15.4e [6] is an amendment to the MAC protocol of IEEE802.15.4-2011 [START_REF]Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-Rate Wireless Person-alArea Networks (LR-WPANs)[END_REF]. The Time Synchronized Channel Hopping (TSCH) mode of IEEE802.15.4e yields ultra-high reliability and lower-power operation. All sensor motes in a IEEE802.15.4e network are synchronized. Time is split into time slots, each typically 10ms long. Time slots are grouped into a slotframe, which continuously repeats over time. All communication is orchestrated by a "schedule" which instructs each sensor mote what to do in each slot of the slotframe: sleep, transmit (TX) or receive (RX). Channel diversity is achieved by specifying, for each TX or RX slot, a channel offset. In consecutive slotframe cycles, the same channel offset translates into a different communication frequency, resulting in "channel hopping". Channel hopping reduces the impact of external interference and multi-path fading, thereby increasing the reliability of the network [START_REF] Watteyne | Reliability Through Frequency Diversity: Why Channel Hopping Makes Sense[END_REF].

The TSCH schedule can be represented by 2-D matrix of width the number of slots in a slotframe, and height the number of available frequencies. Each element in the matrix is called a "cell". A cell is "scheduled" when used either to transmit or receive. Each scheduled cell is an opportunity for a sensor mote to communicate with its neighbor. The schedule is managed through a centralized or distributed scheduling entity; OTF -presented in this article -is a example of the latter. The role of the scheduling entity is to ensure that there are enough communication opportunities to satisfy the communication needs of the applications (amount of traffic load offered to the network, reliability, latency).

The IEEE802.15.4e standard specifies the scheduling mechanism (i.e. how to execute a schedule), but does not specify the scheduling policy (i.e. how the schedule is built and maintained). Constructing a schedule is policy-specific. Example policies include a centralized scheduling based on graph coloring techniques [START_REF] Palattella | Traffic Aware Scheduling Algorithm for reliable low-power multihop IEEE 802.15. 4e networks[END_REF], [START_REF] Palattella | On optimal scheduling in duty-cycled industrial IoT applications using IEEE802. 15.4e[END_REF], and distributed scheduling using gossiping at two-hop neighbors [START_REF] Morell | Label Switching over IEEE802.15.4e Networks[END_REF]. The scheduling entity requires a method to distribute and install the schedule at each sensor mote.

B. 6TiSCH Operation Sublayer (6top)

The 6TiSCH working group is defining the 6top sublayer as the next upper layer of the TSCH MAC (see Fig. 2). Layers on top of 6top can use it to manage the TSCH schedule, configure monitoring, and collect statistics [START_REF] Wang | 6TiSCH Operation Sublayer (6top)[END_REF]. 6top has been designed to be used with several scheduling approaches. With a centralized one, a PCE collects topology and traffic requirements that are used to build a communication schedule, which is then sent to the sensor motes in the network. In a distributed approach, sensor motes compute their own schedule according to local information or by using a distributed resource reservation protocol similar to the Resource Reservation Protocol (RSVP) [START_REF] Braden | Resource ReSerVation Protocol (RSVP)[END_REF], [START_REF] Morell | Label Switching over IEEE802.15.4e Networks[END_REF] or Next Steps In Signaling (NSIS) [START_REF] Hancock | Next Steps in Signaling (NSIS): Framework[END_REF].

6top labels each scheduled cell by its cellType, which can be either "hard" or "soft". A hard cell is a cell that cannot be dynamically relocated2 by 6top. The cell is installed by 6top at a particular slotOffset and channelOffset in the schedule. This type of cell is typically scheduled by a PCE.

Once installed, only the PCE can move/delete it inside the TSCH schedule. A soft cell is a cell that can be relocated by 6top dynamically. This type of cell is typically scheduled by a distributed scheduling entity, e.g. OTF proposed in this paper. Instead of specifying the exact slotOffset and channelOffset, the scheduling entity indicates how many cells to schedule to a given neighbor, i.e. the bandwidth requirement. With the bandwidth requirement, 6top will choose specific slotOffset(s) and channelOffset(s) through the soft cell negotiation procedure described in [START_REF] Wang | 6TiSCH Operation Sublayer (6top)[END_REF]. The monitoring process of 6top keeps track of the performance of each of the cells to the same neighbor. If a cell performs significantly worse than the other cells scheduled to the same neighbor, 6top relocates this cell at a different slotOffset and channelOffset inside the TSCH schedule. The concept of soft cells allows the 6top sublayer deal with the interference efficiently.

Once a TSCH schedule is established, 6top is responsible for feeding the data from the upper layer into TSCH. A 6TiSCH network can transport different types of traffic, possibly for different administrative entities (e.g. equipment or process status data like temperature, pressure, vibration and Heating, Ventilation, and Air Conditioning (HVAC) data in a smart building), with different Quality of Service (QoS) constraints. Since 6top is a sublayer between 6LoWPAN and IEEE802.15.4e TSCH (Fig. 2), the properties associated with a packet/fragment are translated by the upper layer into parameters such as next hop neighbor address, or priority associated with that packet. 6top comes with its own queuing model to satisfy the associated service differentiation. The 6top queue model is depicted in Fig. 3. Q i represents a queue, which is either broadcast or unicast, and has an assigned priority. The number of queues is configurable. When 6top receives a packet to forward, the Inverse Multiplexer (I-MUX) module selects a queue where to insert it, according to the priority associated with the packet. The Multiplexer (MUX) module is invoked at each scheduled transmit cell by TSCH. When invoked, the MUX module goes through the queues using the neighbor address attached to the scheduled transmit cell, looking for the best matching frame to send. If it finds a frame, it hands it over to TSCH for transmission.

6top maintains statistics about the performance of scheduled cells. When using a centralized scheduler, this information is periodically sent to the PCE, which continuously adapts the schedule and sends schedule updates as needed. This information can also be used by the objective function of RPL or bandwidth reservation modules.

6top provides a set of commands to support decentralized, centralized and hybrid scheduling solutions. These form an interface an upper layer can use. For bandwidth reservation functions, CREATE/DELETE.softcell [START_REF] Wang | 6TiSCH Operation Sublayer (6top)[END_REF] adds or deletes soft cells. The monitoring process of 6top is responsible for the quality of those soft cells by relocating the cells with significantly low communication performance.

RPL can leverage the statistic information 6top gathers at each node to further optimize routes, subject to the QoS requirements of served applications. This way, soft real time services can be provided over the best effort track by dynamically updating paths, based on a quasi real-time monitoring of the different candidate next hop nodes along a path.

III. ON-THE-FLY BANDWIDTH RESERVATION

Most industrial networks require a high level of determinism. Typically, data flows are known a priori, and it is therefore possible to compute the communication schedule in advance, taking into account the QoS level of each flow (amount of data, latency, reliability), while optimizing the use of cells scheduled to limit the energy spent. When flow requirements change (e.g. a sensor node generates a new data flow), the schedule needs to be adapted accordingly. Several approaches are possible, including centralized and distributed ones. The 6top sublayer follows a distributed approach, and allocates soft cells upon request from a higher level reservation protocol module, such as OTF, and makes sure that the requested QoS is constantly met in a hop-by-hop basis. The OTF module presented in this work deals with the best-effort track, which corresponds to the class of traffic with the lowest priority, prone to higher packet loss and variable delay. Consequently, OTF does not guarantee the same compliance with the delay and packet loss requirements offered by other tracks, with different QoS settings.

The OTF module is located on top of the 6top sublayer, and implements a distributed bandwidth allocation algorithm: this module monitors the amount of data being sent to each of the mote's neighbors; when this amount of data becomes too large (resp. too small) compared to the number of cells scheduled to that neighbor, OTF asks 6top to add (resp. delete) cells scheduled to that neighbor. Adding/deleting cells triggers a specific communication process ("negotiation") between the neighbor motes, which results in transmission overhead. Complimentary to the OTF bandwidth estimation algorithm, an allocation algorithm module is implemented before the requests are forwarded to 6top. By adding configurable overprovisioning through a threshold, this allocation algorithm module reduces bandwidth estimation algorithm instabilities such as cells continuously added/deleted. However, there is a need to find the optimal trade-off between over-provisioning too many cells (which implies motes would switch their radios on unnecessarily) or too few cells (which translates in an unnecessary increase of 6top's communication overhead).

As shown in Fig. 4, a network administrator can fine-tune OTF parameters using the Constrained Application Protocol (CoAP), an application-level protocol [START_REF] Sudhaakar | 6TiSCH Resource Management and Interaction using CoAP[END_REF] developed as a light version of HTTP for low power networks. The OTF module has the possibility to host several bandwidth estimation algorithms which can be selected from an external application by using CoAP. In this way, a single implementation can be configured to the needs of different applications. Furthermore, once the bandwidth estimation algorithm is selected, it can be adjusted to obtain the best performance by sending CoAP messages to modify internal parameters and configure the actual algorithm behavior.

OTF was designed with two main use cases in mind: as a completely distributed allocation module or as a complement to a PCE-based approach. In the first case, it may be used to allocate cells to build tracks between sensor nodes given routing and QoS requirements -for example for a temporal instrumentation setting -while in the second case, it may be used to increment available bandwidth among sensor nodes to adapt to surges in bandwidth requirements, for example to install and reconfigure firmware nodes, or for non-critical alarms from the production line. Given the wide range of network deployments and applications, the bandwidth estimation algorithm and the threshold value are implementation-specific.

Finally, the OTF allocation algorithm is triggered by a set of 6top events, such as the reception of a packet.

A. OTF Allocation Algorithm

The OTF allocation algorithm uses a set of three parameters for each of the mote's neighbors: (i) S, the number of currently scheduled cells; (ii) R, the number of cells required given the outgoing traffic to that neighbor; (iii) T , the neighborspecific threshold. OTF uses the 6top statistics to obtain S. The Bandwidth Estimation Algorithm provides R to the allocation algorithm that, comparing R with S, establishes the number of cells to be added or deleted, according to the threshold T . As described in Algorithm 1, for each neighbor, the allocation algorithm reserves the number of cells needed at that time (R), plus T /2 over-provisioned cells to allow for variations in the amount of bandwidth. In detail, the algorithm adds/deletes respectively the ceil/floor value of T /2, to avoid triggering a new 6top add/delete command when R even changes of 1 unit (as it should happen by considering T instead of T /2 in the formula). Fig. 5 shows the number of cells added/deleted by the OTF algorithm, for different values of R, when S = 11 and T = 3.

Algorithm 1 OTF Allocation Algorithm procedure OTF ALLOCATION(S, R, T ) ⊲ S: Scheduled cells ⊲ R: Required cells ⊲ T : Threshold if R < (S -T ) then ⊲ DELETE cells S = R + ⌊(T /2)⌋ else if R > S then ⊲ ADD cells S = R + ⌈(T /2)⌉ else ⊲ (S -T ) ≤ R ≤ S ⊲
The allocation algorithm also increases the stability of the bandwidth estimation algorithm. For T = 0, the allocation algorithm has no effect, and no cells are over-provisioned. As a consequence, when a new packet increases the bandwidth requirement even in 1 byte/s on top of the currently allocated bandwidth, a new cell allocation request is sent to 6top; thus generating a negotiation process. After the packet is transmitted, another negotiation process to deallocate the cell is triggered, since the new allocated bandwidth will not be needed any more. This phenomenon will happen for every packet exceeding the allocated bandwidth, thus generating an oscillation on the cell allocation process. If T = 0, the allocation algorithm is enabled, and the former problem is avoided by over-provisioning: the required bandwidth is already allocated in excess when the packet arrives, and it will still be allocated when the packet has been transmitted. Furthermore, the two original negotiation processes do not take place, reducing both delay response and power consumption due to management traffic.

B. OTF-6top Interaction

OTF issues two 6top commands (CREATE.softcell, DELETE.softcell [START_REF] Wang | 6TiSCH Operation Sublayer (6top)[END_REF]) and retrieves statistics.

6top keeps statistics in the following structures [START_REF] Wang | 6TiSCH Operation Sublayer (6top) Interface[END_REF]:

1) The CellList structure holds per-cell quality statistics (e.g. number of packets sent, number of packets acknowledged, signal strength of received packets on that cell).

2) The MonitoringStatusList structure holds perneighbor scheduling statistics (e.g. number of scheduled cells to that neighbor).

3) The NeighborList structure holds per-neighbor connectivity statistics (e.g. signal strength of received packets from that neighbor). 4) The QueueList holds per-queue statistics (e.g. queue fill levels, amount of time a packet spends in a queue). OTF uses the MonitoringStatusList to retrieve S, the number of scheduled cells for a specific neighbor. It determines R, the required number of cells, through QueueList and NeighborList statistics. OTF allocation algorithm then decides to add/delete cells.

OTF also configures 6top's monitoring function. This function is responsible for detecting schedule collisions (two pairs of sensor motes use the same soft cell in the schedule). When the link quality of a soft cell is lower than the average link quality of all soft cells to that neighbor, the monitoring function relocates the soft cell to a different (slotOffset,channelOffset) in the schedule. When issuing CREATE.softcell and DELETE.softcell commands, OTF specifies the number of cells to be added/deleted. 6top is responsible for choosing the specific cells within the schedule. The mote and its neighbor go through a 6top cell negotiation process: the mote sends a candidate cell list to its neighbor, which picks a subset of those cells.

IV. PERFORMANCE EVALUATION

We evaluate the performance of OTF, both in simulation and experimentation. This section first details the simulation environment, presents the simulation results, and discusses lessons learned. It then describes the first OTF proof of concept presented at the IETF90 standardization meeting.

The goal of the performance evaluation is to answer the following questions: What end-to-end latency can a network running OTF offer?, What about end-to-end reliability? and What trade-offs does the OTF threshold allow?

A. The 6TiSCH Simulator

The 6TiSCH simulator3 is used to measure the evolution of the number of scheduled cells, the number of OTF add/remove operations, the end-to-end latency and end-to-end reliability, for a number of use cases and simulation parameters. The 6TiSCH simulator is an open-source discrete-event simulator written in Python, developed by members of the 6TiSCH WG to quantify the performance of proposals early in the standardization process. It implements the standards and protocols defined in the 6TiSCH architecture document [START_REF] Thubert | An Architecture for IPv6 over the TSCH mode of IEEE 802[END_REF]: established standards (IEEE802.15.4e MAC [6], RPL [START_REF] Winter | RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks[END_REF]) and 6TiSCH draft standards (6top [START_REF] Wang | 6TiSCH Operation Sublayer (6top)[END_REF], OTF [START_REF] Dujovne | 6TiSCH On-the-Fly Scheduling[END_REF]). The latter two have been developed and added to the simulator as part of the work done and presented in this article. The set of parameters used in the simulations are summarized in Table I, and detailed in the remainder of this section.

The simulator is instrumented to measure and record the state of different parameters of interest (e.g. the timestamp at which a packet is transmitted). A single simulation run includes two stages: deploying a network with a given topology, and simulating the behavior of the network for a period of time. A new topology is used for each run. For each set of parameters, a large number of runs are performed. All results in Section IV-B are presented with a 95% confidence interval.

Each wireless link is associated a Packet Delivery Ratio (PDR), a number between 0.00 and 1.00. When a sensor mote transmits, the PDRs of the link connecting it to its neighbors is used to determine whether or not neighbors receive the packet. The PDRs are calculated on the basis of a Radio Signal Strength Indicator (RSSI) of each link, which is determined by a radio propagation model [START_REF] Zats | Wireless Sensor Networks Scaling and Deployment in Industrial Automation[END_REF] according to the distance between two sensor motes. The PDR of a link is constant for the duration of a simulation run. In case different pairs of sensor motes transmit in the same timeslot and at the same frequency, packets collide. In this case, at each receiver, the RSSIs of each colliding packet are converted to Signal to Interference-plus-Noise Ratio (SINR), which is mapped to a PDR. The PDR of the link is lowered as a function of the interference by the colliding packet(s).

The simulation parameters (summarized in Table I) have been set according to RFC5673 [START_REF] Pister | Industrial Routing Requirements in Low-Power and Lossy Networks[END_REF], and are representative of industrial networks (e.g. deployed in a smart factory).

Deploying simulated sensor motes must result in enough wireless connectivity for the RPL routing protocol to create an efficient multi-hop topology. The deployment routine starts by placing the DAG root (the gateway mote, or sink) at the center of the deployment area. This placement is typical for industrial applications [START_REF] Pister | Industrial Routing Requirements in Low-Power and Lossy Networks[END_REF]. It then places other sensor motes one-by-one at random locations. At each candidate placement, the deployment routine ensures that the new sensor mote can communicate with at least 3 neighbors over wireless links with a PDR of at least 50%. It moves the new mote to a different random location until this condition is satisfied. Even though we ensure that each node is well connected to at least 3 neighbor, all links (including the ones with PDR≤50%) are used in the simulation. Fig. 6 depicts an example of topology generated by the simulator. This yields topologies with an average (resp. maximum) depth of 1.963 (resp. 8 hops), when only taking into account links with PDR>50%.

For all simulation runs, the TSCH schedule contains 101 cells, each 10ms long (the default value in the IEEE802.15.4e standard [6]). When a mote transmits a packet to its neighbor, it expects an acknowledgment packet; if it has not received one after 5 tries, it drops the packet. The radio sensitivity (defined as the RSSI satisfying PDR of 1%) is -101dBm.

On top of TSCH, 6top is in charge of negotiating and deleting cells with neighbors. When adding cells, 6top takes as input by OTF the number x of cells to be ideally allocated with a neighbor. The 6top routine on a mote collects the timeslots available against its own schedule, and informs the neighbor about such availability and the desired number x of cells needed. The neighbor discards among these timeslots those that are already busy on its own schedule, i.e. timeslots already in use. From the remaining set of timeslots (which corresponds to the free timeslots common to both motes), the neighbor randomly picks x timeslots if that set cardinality is bigger than x. Otherwise, it picks exactly the remaining timeslots.

To each of the selected timeslots, the neighbors associate a randomly chosen channel offset among the 16 available at 2.4GHz. When deleting cells, 6top sends to its neighbor the cells to be deleted on their link.

OTF decides whether to add or remove cells to neighbor motes and, in case, feeds 6top for performing such an operation. The OTF algorithm running on a mote is executed every second, and leads the bandwidth allocation strategy. It estimates the outgoing amount of traffic as the sum of: (i) the forwarded traffic, as the average number of packets received by "child" neighbors and to be relayed towards the DAGroot, and (ii) the self-generated traffic, as the number of packets generated by the mote itself for each slotframe. If the latter is very well known to an OTF-enabled mote, an estimation technique is required for evaluating the forwarded traffic. Such an estimation is performed through an auto-regressive filter, which averages with equal weights (i.e. 0.5) a previous estimation of the incoming traffic and the number of packets received in the time interval elapsed (expressed in number of slotframes) since the previous estimation took place. At steady state, i.e. when the network churn is null, this filter outputs the average traffic incoming to the mote.

On the basis of the estimated outgoing traffic, OTF computes the number R of required TX cells, and compares this value to the number of S TX scheduled cells. It takes the threshold T into account (Section III-A) to decide whether to trigger a 6top negotiation.

To assess the OTF over-provisioning performances, several OTF threshold values have been used (0, 2, 4, 6, 8 and 10 cells).

In the RPL implementation, each mote maintains a routing parent set of 3 motes. The MinHopRankIncrease, the minimum increase of the DAG rank between a mote and its parent [START_REF] Winter | RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks[END_REF], is set to 256, according to 6TiSCH-minimaldraft [START_REF] Vilajosana | Minimal 6TiSCH Configuration[END_REF].

Each sensor mote generates data packets regularly, with a period equal to packetPeriod ±50%. Three values of packetPeriod are used: 1s, 10s, 60s. The packetPeriod is the same for all sensor motes in the network; each sensor mote uniformly selects a new random period within [ packetPeriod 2 . . . ] after each transmitted packet.

B. Simulation Results

The simulation results presented in this section are depicted as average values with a 95% confidence interval. Each data point represents 100 simulation runs. Fig. 7 shows the evolution of the number of scheduled cells over time, which is the sum of all cells scheduled by all the sensor motes in the network related to the activity (and energy consumption) in the network. The purpose of OTF is to match the number of communication cells scheduled in the network to the amount of data traffic. The lower the packet period, the more traffic, and hence the more cells are required. The OTF threshold is the number of cells that are over-provisioned: the larger the value of the threshold, the more cells are scheduled.

Fig. 8 shows the number of scheduled cells at the end of the simulation depicted in Fig. 7, i.e. after 100 slotframe cycles Fig. 8. Sum of the scheduled cells at each of the 50 sensor motes in the network, at the end of the simulation presented in Fig. 7, as a function of the OTF threshold. Note that results for packet period 10 s and 60 s are so close that they appear on top of one another.

have elapsed. This number of scheduled cells is plotted as a function of the OTF threshold. As expected, the larger the threshold, the more cells are scheduled.

These results are obtained for a slotframe duration of 101 slots. With 16 frequencies, there are hence 1616 cells in the schedule. Even with each of the 50 sensor motes generating one packet per second, and an OTF threshold of 10 slot, only approx. 500 cells are scheduled, thus, around 30%. Readers interested in the scalability limits of such scheduling are referred to the work of Samuel Zats [START_REF] Zats | Scalability of Time Synchronized Wireless Sensor Networking[END_REF].

Figs. 7 and 8 depict the averall number of cells schedule for all 50 motes. The evolution of the total number of cell (for example over time) is representative of the evolution of the number of scheduled cells at an average mote.

OTF triggers the 6top sublayer to add or delete cells to neighbors. This is called an "OTF operation". Fig. 9 depicts the average number of OTF operations per cycle (one cycle is 101 cells long, or 1.01s) for the whole network, over the first 100 cycles. The more dynamic OTF, the more operations it performs. Each operation causes the 6top sublayer of two neighbor motes to negotiate to add/delete a cell, which induces communication overhead. Lower activity is therefore preferred. The larger the OTF threshold, the more cells are over-provisioned in the network; this hysteresis will cause OTF to add/delete cells less often. Fig. 10 shows the "impulse response" of OTF. Instead of generating data at a constant rate, he application on each sensor mote generates 5 packets at the time, at t=20 s and t=60 s. Fig. 10 shows how this results in OTF adding a number of cells, then removing those as the burst of traffic has ended.

End-to-end latency is calculated as the amount of time between the moment a packet is generated at a sensor mote, and the moment it is received at the DAGroot, possibly after traveling multiple hops. Fig. 11 shows this latency as a function of time. Motes only start generating data at the earliest packetPeriod 2

seconds after the beginning of the simulation. The packets generated at neighbor motes of the DAG root can reach it the fastest, leading to a "ramp up" effect of the latency. The steady-state portion of Fig. 11 shows how the latency is smaller for larger values of the OTF threshold. With a larger threshold, more cells are scheduled, giving a packet more frequent opportunities to progress one hop, which results in lower latency.

The portion of packets generated in the network that reaches the DAG root is called end-to-end reliability. A packet can be lost for three reasons: (1) the maximum number of MAC retries is exceeded, possibly because of a too low link PDR or collisions, (2) a sensor mote has no RPL routing parent to forward data to, or (3) a sensor mote has no outbound cells to communicate with that RPL parent. The simulator logs all three events. Except for the first 2 slotframe cycles during which the very first cells are installed, all packet loss is due to reason [START_REF] Decotignie | A Survey on Industrial Communication Networks[END_REF].

Fig. 12 shows the end-to-end reliability as a function of OTF threshold and packet period. For a packet period of 10s and 60s, end-to-end reliability is above 99%. It is well below for a 1s packet period because of collisions. With a 1s period, between 200 and 500 combined cells are scheduled in the network (see Figs. 7 and8). The probability that two pairs of neighbor motes randomly pick the same cell becomes significant, resulting in a higher packet collision rate and lower reliability. This is exacerbated at higher OTF threshold values, since sensor motes are more cell-hungry. When trying to greedily over-provision their bandwidth, some sensor motes will not be able to allocate a sufficient number of cells. Hence, an equilibrium of load-balanced resources among sensor motes will not be reached. This is also confirmed by observing that, with the OTF threshold equal to 6, the reliability starts decreasing while the OTF activity starts increasing (Fig. 9).

C. Lesson learned from Simulation Results

The obtained simulation results show that OTF is a valid approach for managing a TSCH schedule in a distributed manner. They highlight the importance of choosing a value of the OTF threshold, as it determines the trade-off between energy consumption, network stability, latency and reliability.

A higher threshold leads to a higher number of scheduled cells (Fig. 8) -hence energy consumption-, but a more stable network with less OTF operations (Fig. 9), a lower latency (Fig. 11) and, in general, a higher reliability (Fig. 12).

Yet, the cells OTF schedules are shared by nature. This "slotted Aloha" behavior means that packet collisions are possible, and can lead to network collapse if too many cells are scheduled. Fig. 12 shows the end-to-end reliability plummeting for a 1s packet period and an OTF threshold of 10 cells. Under these parameters (see Fig. 7) only about a third of the 1616 cells (101 cells × 16 frequency channels) in the network are scheduled.

To answer the questions posed at the beginning of Section IV, these results show how, in a 50-sensor mote multihop network typical for an industrial application, a purely distributed approach such as OTF can achieve end-to-end latencies in the order of a second, with over 99% end-to-end reliability.

D. First OTF Proof of concept

During the IETF90 standardization meeting (in Toronto, Canada), a plugfest4 was organized to demonstrate different applications of the 6TiSCH, 6lo 5 and ROLL6 Working Groups.

At the plugfest, we presented the first OTF proof of concept, implemented in the context of the OpenWSN project [START_REF] Watteyne | OpenWSN: A Standards-Based Low-Power Wireless Development Environment[END_REF]. OpenWSN 7 is an open-source implementation of a protocol stack based on Internet of Things standards, using a variety of hardware and software platforms. Its default protocol stack includes IEEE802.15.4e, as well as 6LoWPAN and other upper-layer IETF standards, including CoAP, RPL and several recent drafts from the 6TiSCH WG.

Among them, the OTF draft was implemented and run on a heterogeneous 10-sensor mote wireless mesh network. In detail, as the first proof that OTF can run in a real network, on low power motes, we implemented a simplified version of OTF, based on a chain-reaction. Each sensor mote, along the multi-hop path from a leaf mote towards the DAG root, following the request of more bandwidth (soft cells) from its child, asked for the same number of cells to its parent sensor mote. By doing so, the new request of bandwidth was fulfilled, in a distributed manner in the whole network, along each multi-hop path, without the intervention of a PCE. This chained reservation (cascade of cells allocations) from the leaf until the DAG root did not use any centralized scheduling entity, but relied on the OTF module to establish a higher bandwidth path among all sensor motes on the multihop path. This powerful behavior demonstrates the potential of OTF for providing distributed soft cell allocation.

The OTF proof of concept presented at IETF90 plugfest covered its basic functionality. As next steps, we plan to develop a full OTF implementation, including bandwidth allocation algorithms, threshold management, triggering events, and CoAP interface.

V. CONCLUSION

This article presents the OTF bandwidth reservation module for 6TiSCH networks, based on the 6top sublayer and IEEE802.15.4e TSCH. OTF is a distributed scheduling algorithm that dynamically matches link-layer resources to the communication needs of network applications. OTF monitors 6top statistics and, if required, triggers 6top to add/delete cells. 6top executes an internal negotiation protocol to make the necessary changes to the TSCH schedule. A threshold mechanism in OTF provides hysteresis, thereby preventing ringing effects in consecutive cell allocations. This threshold balances communication overhead (due to frequent 6top negotiations) and energy consumption (due to unused overprovisioned cells).

Performance of OTF was assessed through simulations run over a 50-sensor mote multi-hop network representative of a smart factory. The results have shown that OTF can pursue end-to-end latencies of the order of a second, with over 99% end-to-end reliability. The first OTF proof of concept implementation in OpenWSN was demonstrated and also presented in this article in order to pragmatically highlight the relevance of OTF to the 6TiSCH architecture.

The future work includes evaluating the performance of OTF using different bandwidth estimation algorithms, and 6top negotiation procedures. Both mechanisms have been left open in the 6top and OTF standardization work to allow practitioners to tailor 6TiSCH to their own vertical requirements. Finally, large-scale experimental studies are envisaged in the near future using OpenWSN.

Fig. 1 .

 1 Fig. 1. A simple TSCH schedule.

Fig. 2 .

 2 Fig. 2. The 6TiSCH protocol stack.

Fig. 3 .

 3 Fig. 3. The 6top queue model.

Fig. 4 .

 4 Fig. 4. Main components of the OTF module.

Fig. 5 .

 5 Fig. 5. Example of the OTF allocation algorithm, when S = 11, T = 3, for different values of R.

Fig. 6 .

 6 Fig. 6. Example simulated topology. The DAG root appears shaded in red (in the center of the topology). Links are shaded grey according to their PDR. The histogram shows the cumulative density function of the 434 links binned in different PDR levels.

Fig. 7 .

 7 Fig. 7. Sum of the scheduled cells at each of the 50 motes in the network, as a function of time. One slotframe cycle is 101 slots long, or 1.010 s.

Fig. 9 .

 9 Fig.9. The average number of times OTF asks the 6top sublayer to add/delete some cells to a neighbor per cycle, over the whole 50-sensor mote network.

  per node) OTF threshold 8.0 cells OTF threshold 4.0 cells OTF threshold 1.0 cells

Fig. 10 .

 10 Fig. 10. Impulse response of OTF: 5 packets are generated by each mote at times 20 s and 60 s. The top plot shows the OTF activity (above the line quantifies the number of cells added, below the line the numbers of cells removed). The bottom portion shows the resulting number of scheduled cells.

Fig. 11 .

 11 Fig. 11. The evolution of end-to-end latency over time.

Fig. 12 .

 12 Fig. 12. End-to-end reliability as a function of OTF threshold.

ACKNOWLEDGMENT

  This publication was supported by the IN-TER/POLLUX/12/4434480 CoSDN project, funded by the Fonds National de la Recherche, Luxembourg, the Anillo Project ACT-53, Fondecyt No. 11121475 and the CIRIC (INRIA-Chile) Project "Network Design". The Authors would like to thank Pascal Thubert, Xavier Vilajosana and Kris Pister for the valuable discussions and suggestions.

IPv6 over the TSCH mode of IEEE802.15.4e (6TiSCH), http://tools.ietf.org/wg/6tisch/charters.

We use the term "relocate" to mean that the cell is moved from one [ slotOffset,channelOffset] coordinate to a different one in the TSCH schedule.

As an online addition to this article, the source code of the simulator used is available at https://bitbucket.org/6tisch/simulator/.

Plugfest, https://openwsn.atlassian.net/wiki/display/OW/IETF90+plugfest

6lo, http://datatracker.ietf.org/wg/6lo/charter/

ROLL, http://datatracker.ietf.org/wg/roll/charter/

OpenWSN, http://www.openwsn.org