Thong Huynh

Fabrice Theoleyre
email: theoleyre@unistra.fr

Won-Joo Hwang
email: ichwang@inje.ac.kr

On the Interest of Opportunistic Anycast Scheduling for Wireless Low Power Lossy Networks

Keywords: opportunistic routing, multi-parent, scheduling, multichannel MAC, IEEE 802.15.4e TSCH

Low-Power and Lossy Networks (LLNs) aim at integrating smart objects into the Internet of Things. ieee 802.15.4-TSCH is currently a promising standard for the link layer: it schedules the transmissions and implements slow channel hopping to improve the reliability while the routing layer focuses on constructing distributed routes for a small collection of destinations (i.e. convergecast). We propose here an efficient scheduling policy to exploit an opportunistic feature of the MAC layer: a single transmission is received by a collection of next hops which decide opportunistically which one will forward the packet. We consider here the problem of the optimal scheduling policy for reliability and energy efficiency when considering such opportunistic forwarding at the MAC and routing layers. The simulation results demonstrate the effectiveness of the proposed policy: by effectively selecting the set of parents (i.e. next hops) and carefully considering the channel quality, the energy consumption per packet is reduced. Besides, we also improve the reliability: the network can also use unreliable radio links, where only one of the next hops receives the packet to forward. This scheduling policy may typically be implemented in the PCE of ieee 802.15.4e-TSCH.

Introduction

Recent advances in technology made possible the creation of smart objects that can be interconnected to create the new Internet of Things. The ieee 802.15.4 working group proposed in 2012 an amendment to enable energy efficient networking for the industrial market [1]. Since transmissions are often predictive, the TSCH (Timesloted channel Hopping) mode proposes to assign timeslots coupled with a slow channel hopping strategy to improve the reliability. To enable an energy efficient TDMA, TSCH implements an implicit synchronization: any data or control packet may be used by the receiver or the transmitter to compute the clock drifts. This strategy is particularly efficient for periodic and/or predictive transmissions.

In multihop networks, a centralized Path Computation Engine (PCE) may compute the path to use for each flow. Alternatively, a routing protocol such as RPL may construct distributively the routes [START_REF] Winter | RPL: IPv6 routing protocol for low-power and lossy networks[END_REF]. For a convergecast traffic, most of the approaches construct a Directed Acyclic Graph rooted at the border routers (i.e. gateways to the Internet). Then, each node has a set of parents, which constitute the next hops toward the border routers. However, RPL selects currently only one parent, which forwards all the traffic -the other ones serve just as a backup purpose. We propose here to modify the MAC forwarding strategy to enable opportunistic forwarding, exploiting all the parents to improve the reliability. Indeed, loosing packets may be prejudicial for many applications since packets may not be redundant (e.g. water metering, smart parking, etc.) Scheduling the transmissions after having selecting the routes to use has recently attracted much attention. In particular, the 6TiSCH working group [START_REF]6tisch, Ipv6 over the tsch mode of ieee 802.15[END_REF] aims at defining the mechanisms to enable RPL to work on top of ieee 802.15.4 TSCH. 6TiSCH defines a bootstrapping procedure with a minimal configuration so that a central controller (the Path Computation Engine -PCE) is then able to compute an efficient schedule. However, 6TiSCH currently focuses on unicast transmissions, with the concept of tracks. We aim at going further in this direction, with an opportunistic version of ieee 802.15.4-TSCH, exploiting several parents in parallel to increase the reliability while decreasing the energy consumption. Typically, our solution may be implemented in 6TiSCH working with a centralized controller (PCE).

Proposing an efficient schedule also requires to determine the optimal transmission power. Indeed, using the maximum power may improve the reliability but may also increase the energy consumption [START_REF] Willig | Recent and emerging topics in wireless industrial communications: A selection[END_REF]. Besides, the channel quality varies with time due to fading. Thus, we can achieve significant energy conversation by scheduling transmission during the time that the channel is in good quality [START_REF] Zafer | Optimal rate control for delay-constrained data transmission over a wireless channel, Information Theory[END_REF].

In this paper, we consider the problem of scheduling in multihop convergecast networks to improve both the end-to-end reliability and the global energy consumption. In particular, we use the multiple parent opportunistic scheduling at the MAC layer to cope with individually faulty links. The contributions of this paper are twofold:

1. We provide a dynamic and stochastic formulation of the problem by using dynamic programing. This policy can maximize a combination of reliability and energy consumption. We propose an approximate algorithm, which considers the problem in close form function rather than discrete value, to reduce the computational complexity; 2. We thoroughly evaluate the performance of this algorithm by simulations. Our scheme results in a lower energy consumption and a better end-to-end reliability compared to a non optimized, singleparent scheduling strategy (Section 6).

Related Work

2.1. ieee 802.15.4e-TSCH ieee 802. 15.4-2006 [6] was introduced at first in Personal Area Networks (PANs). While it enabled through Zigbee the adoption of IEEE 802.15.4 for the Internet of Things (IoT), it suffers from limits in multihop topologies [START_REF] Koubâa | TDBS: a time division beacon scheduling mechanism for zigbee cluster-tree wireless sensor networks[END_REF], and leads to many collisions [START_REF] Abdeddaim | Adaptive ieee 802.15.4 mac for throughput and energy optimization[END_REF].

The working group proposed in 2012 the ieee 802.15.4-TSCH amendment [1] to set-up an industrial wireless network TSCH adopts a FTDMA strategy such as Wireless HART [START_REF] Song | Wirelesshart: Applying wireless technology in real-time industrial process control[END_REF] to mitigate interference and multipath fading. Besides, TSCH is deterministic to provide predictable performance.

In ieee 802.15.4-TSCH, a schedule is established so that each node knows at the beginning of each timeslot if it has to stay awake to receive or transmit a frame. In the ieee 802.15.4-TSCH jargon, a cell represents a transmission opportunity, denoted by a timeslot and a channel offset. We denote in this paper by cell the pair <timeslot,channelOffset>.

The superframe structure is depicted in Fig. 1. A slotframe contains a certain number of timeslots and repeats over time. In a timeslot fits only one data packet, which may be acknowledged by the receiver. A slot may be either dedicated to one transmitter or shared among a group of interfering nodes. In Fig. 1, the radio link C → P AN c reserved two cells (timeslots 5 and 7) for its transmissions.

TSCH may use a centralized scheduling, with a Path Computation Engine (PCE). This PCE is the central entity in charge of computing the paths used by each flow, and the channel and timeslots used by each radio link. In that case, the 6TiSCH architecture is an extension of the detnet work Deterministic Networking Architecture [START_REF] Thubert | An architecture for ipv6 over the tsch mode of ieee 802[END_REF], adopting a SDN approach.

The schedule may also be decentralized, decided one-by-hop with the 6top protocol to negotiate a group of cells [START_REF] Wang | 6tisch operation sublayer (6top)[END_REF]. Because each pair of nodes selects autonomously the cell to use, collisions may arise. Some mechanisms are required to monitor and adapt the local schedule [START_REF] Thubert | An architecture for ipv6 over the tsch mode of ieee 802[END_REF].

Interference may arise in the following cases:

internal interference occurs if the same cell is allocated to a pair of interfering transmitters. Since no medium access is implemented, the collision will occur for sure in every cell.

We assume here the interfering topology is a priori known, and that our scheduling algorithm forbid to allocate the same cell to two different interfering transmitters. We neglect consequently this internal interference.

external interference may come from other wireless technologies (Bluetooth, Wifi, etc.) since we use the ISM band [START_REF] Lee | A comparative study of wireless protocols: Bluetooth, uwb, zigbee, and wi-fi[END_REF][START_REF] Yi | Developing zigbee deployment guideline under wifi interference for smart grid applications[END_REF]. However, channel hopping is particularly efficient to alleviate this kind of external interference, reducing the number of retransmissions [START_REF] Watteyne | Reliability through frequency diversity: Why channel hopping makes sense[END_REF].

We consider here that external interference impact negatively the Packet Error Rate (PER): more cells have to be allocated when external interference is present. Besides, we focus on long-term performance, i.e. we consider external interference is sufficiently stable to be estimated via the PER, and thus considered in the scheduling process.

Routing

RPL [START_REF] Winter | RPL: IPv6 routing protocol for low-power and lossy networks[END_REF] was designed for low power lossy networks (LLN), mainly for convergecast traffic, i.e. all the packets are collected by a border router.

The standard constructs a Destination Oriented Directed Acyclic Graph (DODAG): each node maintains a collection of parents, and the routing structure does not form any cycle. In the forwarding plan, a node chooses to forward all its packets to its preferred parent, other parents constitute backup solutions if the preferred one fails.

To construct a DODAG, each node computes a rank, denoting its virtual distance from the border router. Then, a node selects as parent any node with a lower rank (Fig. 2).

Lampin et al. [15] proposed an opportunistic forwarding version of RPL to exploit also long radio links with a poor reliability. The parent with the higher priority acknowledges first the packet, They use an opportunistic MAC layer, where a single transmission is sufficient to forward a packet to all the parents. Opportunistically, the parent with the higher priority and which received the packet acknowledges the reception and forwards the packet. We want to propose here a scheduling policy to exploit this opportunistic feature in a 6TiSCH stack.

FTDA Scheduling Algorithm

To assign the resource for each packet is currently a very challenging objective: we have to define which cell should be used for each radio link.

Ghosh et al. [START_REF] Ghosh | Multi-channel scheduling algorithms for fast aggregated convergecast in sensor networks[END_REF] proposed to minimize the schedule length in a multichannel TDMA environment. Tsitsiklis et al. [START_REF] Tsitsiklis | On the power of (even a little) centralization in distributed processing[END_REF] studied the tradeoff between a centralized and a distributed scheduling. By adopting a queue theory based approach, they demonstrated a centralized approach is more efficient. Thus, these approaches are well suited for industrial networks with strict requirements on reliability and delay.

Yang et al. [START_REF] Yan | Hypergraph-based data link layer scheduling for reliable packet delivery in wireless sensing and control networks with end-to-end delay constraints[END_REF] constructed an optimal schedule for time-sensitive flows: new cells are inserted in the schedule if the end-to-end reliability is insufficient until the deadline constraint is not fulfilled. TASA proposes to construct a centralized scheduling for a multihop TSCH network [START_REF] Palattella | On optimal scheduling in duty-cycled industrial iot applications using IEEE802.15.4e TSCH[END_REF]. Yigit et al. [START_REF] Yigit | On the interdependency between multi-channel scheduling and tree-based routing for WSNs in smart grid environments[END_REF] studied the impact of routing on the scheduling: using unreliable links increases the number of timeslots required to achieve a minimum reliability. Dobslaw et al. [START_REF] Dobslaw | End-to-end reliability-aware scheduling for wireless sensor networks[END_REF] proposed to reserve additional timeslots for retransmissions.

DeTAS proposed a decentralized version of TASA [START_REF] Accettura | Decentralized traffic aware scheduling for multi-hop low power lossy networks in the internet of things[END_REF]: the children of the border routers collect the information and compute the schedule of their subtree (called micro-schedules). Finally, the micro-schedules are re-arranged into a globally acceptable schedule. Distributed scheduling is particularly recommended when the traffic or the topology are dynamic, where the network may temporarily perform poorly before the network re-converges to a legal state.

In this paper, we propose to explore rather how opportunistic forwarding at the MAC layer may improve the reliability while limiting the energy consumption. This multi-parent feature may be incorporated in these scheduling algorithms.

Opportunistic Multi-Parent Forwarding with TSCH and 6TiSCH

We propose to modify TSCH to implement opportunistic forwarding: a node transmits its data frames in anycast toward any of its parents.

Opportunistic Forwarding with ieee 802.15.4-TSCH

For an opportunistic TSCH, several parents must wake-up at the beginning of a dedicated cell. A child transmits its data frame in anycast, and the parent with the largest priority and which received correctly the packet must send an acknowledgement. This method is similar to those adopted by Lampin et al. [15]. After the data packet, the remaining part of the timeslot is dedicated to the opportunistic acknowledgements. The parents are ranked by the child: the source gives a preference order among its parents. If a parent does not hear any acknowledgement for a suffficiently long time, it decides to forward the packet.

More precisely, the k th parent triggers k successive CCA, interspaced by a turnarroundtime (maximum time to switch from RX to TX mode). Since the parents are strictly ordered, we can see that a parent stops deferring as soon as it receives an ack.

To reduce the overhead, we upper bound the number of possible active parents in a given timeslot. Practically, 4 parents are sufficient to offer a certain diversity [START_REF] Pavkovic | Efficient topology construction for RPL over IEEE 802.15.4 in wireless sensor networks[END_REF]. Given the CCA duration (128µs) and the turnarroundtime (210µs), approximately 1ms is dedicated for the acknowledgments at the end of the timeslot.

The parents must hear each other to listen to the acks of others. To construct the schedule, a node should report the link quality toward its neighbors. Thus, the PCE will select in a given timeslot a set of parents with a very small PER. Besides, a parent will consider the packet is acknowledged if the CCA fails, i.e. it does not need to decode the ack packet, it just needs to sense a radio activity above the CCA threshold. Practically, missing the ack is very unfrequent. Finally, missing an acknowledgement means only duplicates are generated, consuming a little more resource.

Figure 3 illustrates the timeslot structure for the radio links (A,B) and (A,C) for the topology depicted in Fig. 2. We assume that the parent B is preferred over the parent C. In the first timeslot, the parent B answers first, and C will stop listening to the medium. In the second timeslot, B did not receive correctly the packet, and C will acknowledge after having deferred sufficiently. A transmission fails only if all the parents are unable to decode the packet.

Such feature is particular useful since unreliable links are the rule in realistic environments [START_REF] Srinivasan | Understanding the causes of packet delivery success and failure in dense wireless sensor networks[END_REF] and the radio link quality may even evolve along the time [START_REF] Cerpa | Temporal Properties of Low Power Wireless Links: Modeling and Implications on Multi-Hop Routing[END_REF].

6TiSCH

We aim in this paper at proposing a policy to schedule efficiently dedicated opportunistic cells: during one time a child transmits a frame to several parents. We aim at implementing our scheduling policy inside the Path Computation Element (PCE).

Thus, we expect to re-use entirely the 6TiSCH protocols. The PCE:

• collects globally the statistics from each participant (RSSI, LinkQuality, Queue status, etc.) with the 6TiSCH Resource Management features [START_REF] Sudhaakar | 6tisch resource management and interaction using coap[END_REF];

• uses consequently the network topology (link quality) to compute the schedule in a centralized manner;

• pushes each local schedule to each node, using end-to-end CoAP messages [START_REF] Sudhaakar | 6tisch resource management and interaction using coap[END_REF]. Symbol Meaning P i the parents of the node i x i,j (t) the node i may transmit a packet to j during the timeslot t z(i)(t)

the amount of packets left in the buffer of node i at time t D i the number of packet in the buffer node i need to transmit during the cycle T number of timeslot in each cycles s i,j (t) channel state for the transmissions from the node i to its parent j Γ i activation vector of node i (i.e. set of parents scheduled during this timelot) Γ feasible set of activation vectors (i.e. interference free)

I i,j (.)
the packet is correctly delivered from i to its parent j e i,j (.) energy consumed for a transmission from i to its parent j V (π) (.) value function of the ADP (i.e. total reward from the beginning)

V (k) (.)
approximate value function of the ADP at iteration k

System Model and Problem formulation

We consider the convergecast traffic problem in wireless sensor networks with one border router (root) and N sensor nodes. The sensor nodes report periodical measures (e.g. pollution, noise, gas or water consumption) to the root node. All sensor nodes are battery-powered with finite reserve. In our model, the DODAG structure is constructed by using a routing protocol such as RPL so that each node can forward its data to the root by using its parents. Our objective consists in determining a set of activate nodes allowed to transmit data, and its associated parents such that the transmission energy of overall network is minimized under condition of maximizing the total amount of receiving data.

System Model

Let i ∈ N represent the index of the sensor node and P i represent the set of its parents. Two nodes can communicate with each other if they are mutually in their radio range (i.e. the reception power is sufficient to decode the frame). We consider a slotted time frame structure that is used in ieee 802.15.4-TSCH. The time is divided into equal cycles (slotframes). Furthermore, each cycle is composed of T timeslots and a timeslot is the basic unit time for transmission (fig. 1). At the beginning of each cycle, the scheduling policy will decide the set of nodes allowed to transmit, based on the energy budget of each sensor node within a cycle.

Channel Model

We model the channel condition by using a Finite-State Markov Channel (FSMC) model. This FSMC models accurately Rayleigh fading channel [START_REF] Wang | Finite-state markov channel-a useful model for radio communication channels[END_REF]. Each node may use some dedicated beacon frames to estimate the signal-to-noise ratio (SNR) on the radio link. We divide the range of possible SNR values into equal intervals where each interval represents a state in the Markov chain. We denote the set of the states by s (w) ∈ S = {s (0) , s (1) , ...}. Let s i (t) = {s i,j } i∈N,j∈Pi be the vector representing the channel state of node i, where s i,j ∈ S is the channel states of radio link between node i and its parent j. The channel states of sensor nodes among these states s i (t) follow the Markov processes. The successive states s i,j (t + 1) of link (i, j) at t + 1 are governed by the transition probability p

(w,k) i,j = P r[s i,j (t + 1) = s (k) |s i,j (t) = s (w) ].
These transition probabilities are estimated through the probability density function (PDF) of the SNR. Each Markov state represents the interval of the SNR. From this function, we can estimate the states transition probability in Markov model as in [START_REF] Sadeghi | Finite-state markov modeling of fading channels -a survey of principles and applications[END_REF]. This probability is equal to the probability that the SNR lies inside the given interval.

Interference model

Let x i (t) = {x i,j } i∈N,j∈Pi be a vector representing the activation state of node i where x i,j = 1 if node i transmits data to its parents j ∈ P i , otherwise x i,j = 0. In case we use the Opportunistic Multi-Parent approach, each node may forward data to its parents simultaneously by using the timeslot structure as depicted in Fig. 3.

To determine which radio links may be scheduled simultaneously, we use the contention graph model [START_REF] Tang | Cross-layer design for end-to-end throughput and fairness enhancement in multi-channel wireless mesh networks[END_REF]. Each vertex in the contention graph represents a radio link and a pair of radio links are neighbors in the contention graph (i.e. an edge exists) if they interfere with each other. We use here the interference range model [START_REF] Tang | Cross-layer design for end-to-end throughput and fairness enhancement in multi-channel wireless mesh networks[END_REF] in order to construct the contention graph. If the distance between two nodes is shorter than the interference range, they cannot be scheduled at the same time without collision, and an edge exists in the contention graph. However, any other interference model is also relevant, it just has to be mapped in the contention graph.

Let Γ i be the feasible activation vector of node i regarding its parents P i and Γ = {Γ i } i∈N is the feasible set in which all nodes in Γ can be active at the same time. Let G C denote the contention graph. It is clear that a feasible set corresponds to an independent set, a set of radio links for which no edge between two arbitrary vertices exists in the contention graph. Finding the independent set is widely known as a NP-hard problem. However, there are several techniques to reduce the complexity [START_REF] Johnson | On generating all maximal independent sets[END_REF]. Moreover, for a specific network topology, we need to compute the independent set only once at the beginning. We here adopt the heuristic algorithm in [START_REF] Tang | Cross-layer design for end-to-end throughput and fairness enhancement in multi-channel wireless mesh networks[END_REF], to determine a subset of independent sets. It has been shown that the transmission rates under this heuristic algorithms are very close to those computed by using all possible transmissions.

The success/failure delivery of the packet from node i to its parent j is represented by an indicator transmission random variable I i,j (x i,j (t), s i,j (t)) that depend on the channel states and the scheduling policy. Specifically, this indicator function is defined as follows:

I i,j (x i,j (t), s i,j (t)) =     
1, if a packet is sucessfully received by j 0 otherwise Note that I i,j (x i,j (t), s i,j (t)) is a random variable, and its conditional expectation given (x i,j (t), s i,j (t)) is equal to the success probability under a given channel quality. Thus, under specific channel states s i,j (t), activation vector, I i,j (x i,j (t), s i,j (t)) can be a deterministic function 0/1 [START_REF] Li | Lifetime optimization for wireless sensor networks with outage probability constraints[END_REF][START_REF] Urgaonkar | Delay-limited cooperative communication with reliability constraints in wireless networks[END_REF].

Illustrative Example: Let us consider in Fig. 4 the two-states Markov channel, also known as the Gilbert-Elliot channel. In this channel model, each state corresponds to a specific channel quality which is either very good or totally bad. If the measured SNR is below the threshold value, the channel is labeled as "Bad" (B), otherwise, the channel is labeled as "Good" (G). The channel state is S = {G, B}. The transition probability from state i to state j is determined by p i,j . Otherwise, each state associates with the success transmission probabilities p i , (i = G, B). The indicator transmission on radio link (i, j), I i,j , evolves over slots according to a random process with probability p i , (i = G; B). In our example, if the channel state is B, the transmission will fail (p B = 0) and if the channel state is G, the probability of having successful transmission will be p G .

Energy model

We make the common assumption that communication radios are the main source of energy consumption. This energy includes i) energy for transmitting packets, ii) energy for receiving packets. However, the total energy consumption for receiving a packet is fixed and does not depend on the channel states and the scheduling policy. Consequently, we neglect here this part.

Similarly to [START_REF] Srivastava | Energy optimal transmission scheduling in wireless sensor networks[END_REF], we focus on optimizing the transmission energy. Let e i,j (x i,j (t), s i,j (t)) be the transmitting energy of the user i at a specific channel state s i,j (t) = s (w) ∈ S, when it transmits a packet to its parent j. This energy can be calculated using the well-known Shannon capacity formula:

P G,B P B,G 1 -P B,G 1 -P G,B I=1 G B I=0 1 p G 1-p G
e i,j (x i,j (t) , s i,j (t)) = x i,j (t) N 0 W 2 r/W -1 h(t) (si,j (t)) 2 (1)
where N 0 is the additive Gaussian noise, r is the transmission rate, and W is the bandwidth. h(t)

(si,j (t))
is the channel gain between nodes i and j under the channel condition s i,j . Since e i,j (x i,j (t), s i,j (t)) = 0 if x i,j (t) = 0, this allocation power is also a function of the activation vector. Let e i (t) = max j∈Pj e i,j (t) be the transmission energy of node i at time t. It will ensure that all packets are transmitted with a sufficient power to reach all its parents. For notational convenience, in the rest of the paper, we use e i,j (t), I i,j (t) instead of e i,j (s i,j (t)), and I i,j (x i (t), s i (t)); the dependence on x i (t), s i (t) is implicit.

Problem formulation

To this end, each node i is associated with a utility:

U i (t) = j∈Pi I i,j (t) -δe i (t) (2)
that describes the balance between the throughput (i.e. number of received packets) and the allocated energy. The parameter δ controls the trade off between two objectives: the throughput maximization and the energy consumption minimization for each node. We consider long-term network performance over one cycle length, which consists in T timeslots. Network performance is characterized by the network-wide utility of all sensor nodes over T timeslots. Each sensor node i has D i packets which must be sent during the cycle. We would like to maximize the total utility max

T t=0 i∈N U i (t) (3)
subject to constraints on the energy consumption, and the transmitted packet:

T t=0 j∈Pi e i,j (t) ≤ E m,i (4)
T t=1

x i (t) = D i (5)
x i,j (t) ∈ {0, 1}

The equation ( 4) limits the energy budget of each sensor node within a cycle. The constraint (5) ensures that each sensor node i will transmit D i packets during the cycle. This problem belongs to the category of nonlinear integer programming, which is known to be NP-hard. Otherwise, it is challenging to find the optimal solution since the channel states of each user are uncertain, and the complexity of the problem which spreads over T timeslots and N nodes is increasingly high.

Dynamic Programming Framework

Original Dynamic Programming

This problem can be considered as a sequential decision problem with T stages. Let E(t) = {E i (t)} i∈N be the energy remaining of all sensor nodes at time t. We define the variable z(t) = {z i } i∈N that indicates the amount of packets left in the buffer at time t. The sensor node needs to transmit these packets by the end of the cycle.

We define a dynamic system in which states are the pair S(t) = (E(t), z(t)). The control action is the activation vector x(t). At the beginning of each cycle, these states are measured and the scheduling policy chooses the action vector x(t) ∈ Γ(t) to forward the system to the next stage. The transition function from the state at time t to the state at time t + 1 is defined by a function of x(t) as follows:

E(t + 1) = E(t) -e(t)x(t) z(t + 1) = z(t) -x(t) (6)
We also define the penalty cost p = {p i } i∈N that are charged at the end of horizon T if a node i does not transmit completely D i packets during the cycle. This cost is higher than the utility cost to ensure the scheduling policy must choose the control vector x(t) to satisfy the constraint (5). This penalty cost function is computed at the end of the cycle as follows:

C(z(T )) = pz (T ) (7)
where z(T ) is the amount of packet left in the buffer at the end of the cycle.

We now calculate the one-period reward function R(t) = {R i } i∈N under states S(t) and activation vector x(t) at each time t as follows:

R i (t) = U i (t) if t > T U i (T ) -C(z(T )) if t = T (8)
As shown in equation ( 2), the utility depends on the current channel state. However, the current channel states at time t are random variables with distributions which may be computed from the one-step transition probability provided that the channel state at t = 0 is given [START_REF] Zafer | Optimal rate control for delay-constrained data transmission over a wireless channel, Information Theory[END_REF][START_REF] Wang | Finite-state markov channel-a useful model for radio communication channels[END_REF]. Let p (w) i,j (t) be the probability that the radio link (i, j) undergoes the channel state s (j) at time t; thus, s (j) ∈S p (w) i,j (t) = 1. The total expected utility at t is:

U (S(t), x(t)) = i∈N s (j) ∈S p (w) i (t)U (w) i (S(t), x(t)),
where U (w) i (S(t), x(t)) is the utility of node i with channel states s (w) . This utility is computed as follows The problem now becomes static: the expected reward function at each stage is a function only of the control decision x(t) and the state S(t). A policy π = {x(t)} t=0,1,...,T -1 is a set of consecutive control actions generated from the states S(0), S(1), ..., S(T ). The dynamic programming problem is formulated with the dynamic evolution of states described in (6) as

U (w) i (S (t) , x (t)) = j∈Pi I (w) i,j (t) -δe
max π V (π) (S(0)) = R(S(T ), x(T )) + T -1 t=0 R(S(t), x(t)) , (9)
where (S(0)) and (S(T )) are the initial and terminal states and the value function V (π) (S(t)) is the total reward starting from t to T under the policy π. This function is equivalent to the negative of the cost-to-go function in control theory. Problem ( 9) is a formal representation of the association control problem in T stages. The problem consists in finding a control policy π so that the value function V (π) (S(t)) (i.e. the total reward of the network) is maximized. Let V * (S(t)) = max π V (π) (S(t)) be the optimal value function at stage t. We use * to denote the optimal setting, i.e. states and control actions. The relationship between V (S * (t)) and V * (S(t + 1)) is given by

V * (S (t)) = max S(t),x(t)
{R(S(t), x(t)) + V * (S (t + 1))} (10)

V * (S(t)), the optimal control action x * (t) and state S(t) may be computed recursively backward in time starting from t = T -1 and stopping at t = 0. At the final step, an optimal scheduling policy π * , which is defined by a set of actions x * (t), is generated.

Computation Complexity: It is important to note that the energy states are not discrete. We may divide the energy into quantified sample values. However, since we work with discrete quantities, solving the dynamic programming optimally becomes computationally intractable when the number of states and the decision variables exponentially increase.

The size of our states

S(t) = {E(t), z(t)} is |E m | N 2 L
where |E m | is the cardinality of the sample energy set. Thus, by using the backward induction algorithms to solve the dynamic programming, it requires T |E m | N 2 N |Γ| to find the optimal activation vector [START_REF] Tran | Adaptive scheduling for multicasting hard deadline constrained prioritized data via network coding[END_REF]. This is the classical curse of dimensionality which is cited as the weakness of dynamic programming.

Consequently, we propose now to approximate the dynamic programming method, to obtain a complexity linear with the number of nodes.

Approximate dynamic policy (ADP): Value function approximation

Clearly, the time complexity increases with the number of nodes. The optimal policy suffers from the curse of dimensionality. Furthermore, calculating the backward cost is generally intractable, To alleviate this problem, we may use an approximate dynamic programming scheme.

In this approach, we propose to replace the value function V (E(t), z(t)) with a linear approximation. However, this approximation implies that this algorithm runs iteratively. We use the notation [parameter] k Algorithm 1: Approximate Dynamic Programming (ADP)

Step 0: Initialization. Initialize V 0 (t) = 0 for all t. Set k=1.

Initialize E 1 (0) = {E i,m }, z 1 (0) = 1.
Step 1: Do for t = 0, 1, ..., T .

Step 1a: Solve.

x k (t) = arg max

x(t)∈Γ R(S k (t), x(t)) + V k-1 S k (t + 1) . Ṽ k S k (t) ← R(S k (t), x k (t)) + V k-1 S k (t + 1) .
Step 1b: Update the states.

E k (t + 1) ← E k (t) -e k (t)x k (t). z k (t + 1) ← z k (t) -x k (t).
Step 1c: Update the value function.

V k S k (t) = (1 -α k ) V k-1 S k (t) + α k Ṽ k (S (t)) .
Step 2: Update iteration.

k ← k + 1. if k < K then Go to step 1. end if Step 3:
Return the value function V K (t) t=1,...,T .

Return the activation vector x K (t) t=1,...,T .

to represent the specific value of [parameter] at iteration k. Let V (E(t), z(t)) be an approximation of the value function. In the following, we demonstrate how to iteratively calculate the V (E(t), z(t)).

During the iteration k, at time t, given the current states S k (t) , the decision x k (t) is computed by using the value function approximation Vk-1 S k (t) . This value function is computed from the previous iteration k = 1, ..., k -1 so it is indexed by k -1. The scheduling variable x k (t) is given by solving

Ṽ k (S (t)) = max S k (t),x k (t) R(S k (t), x k (t)) + V k-1 S k (t + 1) . ( 11
)
After getting the decision x k (t), the states E k (t + 1), z k (t + 1) is updated as in (6). Then the approximation value function at iteration k is calculated based on the moving average

V k S k (t) = (1 -α k ) V k-1 S k (t) + α k Ṽ k (S (t)) ( 12
)
where {α k } is the sequence that satisfies the following properties: 0 [START_REF] Powell | Approximate Dynamic Programming: Solving the Curses of Dimensionality[END_REF]. The equation ( 12) is described as the exponential smoothing approximation. It can help to robust the approximation [START_REF]Forecasting with Exponential Smoothing: The State Space Approach[END_REF]. After reaching the end of cycle, we increase k and start over again.

< α k < 1; ∞ k=0 α k = ∞; and ∞ k=0 α 2 k < ∞ to ensure the convergence
Thus, beginning with the initial value function, we step forward in time. We solve the dynamic programing [START_REF] Thubert | An architecture for ipv6 over the tsch mode of ieee 802[END_REF] approximately by using the value function approximations of the future states. More specifically, for each iteration k, we go through a horizon time, obtain the state trajectory and update the approximated value function for next iteration k + 1. We repeat this procedure over several iterations and update the value function V (E(t), z(t)). The pseudo code for this approach is illustrated in Algorithm 1.

There are two interesting features of the ADP: First, we compute the value at each iteration by going forward in time instead of going backward as in the original dynamic programming approach. Thus, we can eliminate the step that required the looping over all the states. The ADP implementation uses consequently more efficiently the memory caches. Secondly, the approximate value function has a linear form. Indeed, our algorithm only adds the linear element to the original approximation. Thus, at each iteration, the approximate value function includes the original approximation and the linear element.

Lemma 1: The approximation function V k at iteration k is a linear function.

Proof. Let us prove this lemma by induction. We assume this lemma is true for the iteration k -1: V k-1 has linear form. We show it also holds k. From ( 12), we can write

V k S k (t) = (1 -α k ) V k-1 S k (t) + α k Ṽ k S k (t) . = (1 -α k ) V k-1 S k (t) + α k R(S k (t)) + α k V k-1 S k (t + 1)
Since the function V k-1 S k (t) and R(S k (t)) have the linear form, the V k S k () is a linear function.

Further Discussion

Computation Complexity: Since the approximated function V k has a linear form, the problem (11) corresponds to linear integer programing. In ADP algorithms, we need to solve the problem in [START_REF] Wang | 6tisch operation sublayer (6top)[END_REF], KT (2N + 1) times. This is linear with the number of nodes in the network, as opposed with the original dynamic programming. However, our approximate algorithm also converges to the optimal value when K is sufficiently large [START_REF] Cheung | Shape -a stochastic hybrid approximation procedure for two-stage stochastic programs[END_REF].

Message passing: At the beginning of the cycle, the sensor node measures the channel quality and determines the Markov states from itself to the parent. Then the sensor nodes send the message about the Markov states and the number of packet D need to be sent during the cycle to the PCE. The message can be of log 2 (C + D) bits where C is the number of Markov states. The PCE computes the schedule as in the Algorithms 1. Then, it pushes the scheduling decision to each sensor node by sending T bits message to indicate the node deffer or transmit data over T timeslots of the cycle. Since we limit the maximum number of active parent to 4, total 4N log 2 (C + D) + T N bits are required to compute the schedule at each cycle.

A node may send the channel state toward its parents in a CoAP message, using the 6TiSCH Resource Management features. In addition, the PCE can also broadcast the schedule using constrained application protocol (CoAP) with end-to-end CoAP message [START_REF] Sudhaakar | 6tisch resource management and interaction using coap[END_REF].

Since we consider the channel states are known at the beginning of the slotframe, our scheduling policy obtains an upper bound of what we may obtain without this knowledge. The schedule may provide a lower throughput if the channel states are not known by the PCE.

Our results show that opportunistic anycast scheduling improves the throughput in these conditions. In a future work, we aim at investigating how such anycast policy may be implemented practically while minimizing the overhead. Prediction Techniques may help to achieve such feature [START_REF] Liu | Talent: Temporal adaptive link estimator with no training[END_REF].

Performance Evaluation

In this section, we evaluate the proposed approximate dynamic policy (ADP) in comparison with a few existing policies under different performance criteria. We measure the following metrics:

Percent from optimal is the distance between the utility under ADP and under the original dynamic policy. This metric estimates the convergence of the ADP policy to the optimal value; Throughput (packet/timeslots) is the average number of packets received successfully by the sink;

Energy consumption per packet (mW/packet) is calculated by taking a ratio of the total energy consumed by all the nodes to the total number of packets that are successfully received by the sink; Packet error rate is the ratio between the number of lost packets and the number of transmissions. A packet may be lost either because of a queue overflow or a bad quality channel error.

We model the networks environment and conduct the simulation by using MATLAB simulator. We implemented the following scheduling policies for comparison:

1. Conventional RPL policy (CRPL): This policy is a variant of our proposition. A node uses only one single parent to send all its traffic to the border router. This represents the usual behavior of RPL, forwarding the packets only to the preferred parent. The policy is:

V (S * (t)) = max {R(S(t), x(t)) + V (S * (t + 1))} subject to j∈Pi x i,j ≤ 1
This constraint guarantees that each node uses exactly one parent. 2. Multi-Parent Greedy policy (MPaG) is a sub-optimal policy, which selects the set of users with the maximum possible utility to transmit at a given time. It ignores the impact of the current optimal solution to the future cost function. The MPaG also uses the multi-parent scheme. At the timeslot t, we choose the user and its set of parents according to the following objective: V (S * (t)) = max {R(S(t), x(t)) + V (S * (t + 1))} .

arg max i∈N U i (t) .
6.1. Simulation Environment

Network Scenario

We consider random network topologies (Fig. 5) where all the nodes send packets to the root node. We place randomly 40 nodes in a square area: the typical network diameter is around 7 hops. We use the interference range model [START_REF] Cui | Dynamic scheduling for wireless data center networks, Parallel and Distributed Systems[END_REF]. The dot line in Fig. 5 shows the communication link of sensor nodes. We use expected transmission (ETX), a common routing metric in low power lossy networks [START_REF] Winter | RPL: IPv6 routing protocol for low-power and lossy networks[END_REF]. A node has at most 4 active parents.

Channel model

We use the channel model introduced in Fig. 4 to capture the channel condition. Different transition probabilities, p i,j , reflect the channel quality. For example, if p G,B is high and p B,G is low, the channel quality is bad.

In addition, we model the external interference as the ON/OFF process and the transitions of the states follow the Bernoulli random variable with parameter p ext . If the states is ON, the external interference cause the attenuation β to the signal strength of the link. The SNR is the product of the exponential random variable with paramagnet and Bernoulli random variable with parameter p ext . We set attenuation factor is 0.7. in the simulation.

Operation of the simulation

The simulation runs in a slotted time manner. At each simulation timeslot of (100 ms), the simulation executes the following steps. At the first step, the SNR is updated according to the channel model. Second, we update the energy and the success probability under the given channel condition. Finally, we run the scheduling policy using one of the three algorithms. The simulation parameters are listed in the Table 1, using ieee 802.15.4e-TSCH [1], [START_REF] Palattella | Using IEEE 802.15.4e Time-Slotted Channel Hopping (TSCH) in the Internet of Things (IoT): Problem Statement[END_REF]. The transmission rate is 250 kps for the 2.4Ghz band. The duration timeslot is 10ms. The maximum-length packet is 127 bytes which takes 4.256ms to transmit. Four mini-timeslots are used for ack in the end of timeslot. The duration of each mini-timeslot is 0.672ms which include : 192µs for turnarroundtime, 0.128 ms for ACC, and 0.352 ms for acknowledgment transmission.

Convergence

In the first scenario, we verify the convergence of the ADP policy by investigating the utility over 50 iterations. Fig. 6 shows the distance between the utility under ADP and the original dynamic policy which obtains the optimal utility. The convergence rate largely depends on the number of timeslots in a cycle: the larger value of T , the larger number of iteration to obtain the optimal solution.

In general, the ieee 802.15.4-TSCH proposes to use by default 100 timeslots in a cycle [1]. We are within 5 percent after 15 iterations and 1 percent after 30 iterations when the number of timeslots is 100. Thus, our ADP policy obtains a solution close to the optimal one even with a low number of iterations.

In the following scenarios, we set the number of iteration K = 15 and T = 100, where the percentage form the optimal solution is 5 %. It will ensure the convergence of the ADP policy.

Tradeoff between throughput and energy consumption

We now investigate the impact of the δ control parameter (eq. 2). In the utility function, the throughput is about ten times different in value than energy consumption. Thus, we evaluate the power consumption and the throughput by varying the control parameter δ from 10 to 90. In Fig. 7, we show the Pareto curves, which reveal the dependency of the throughput and the energy consumption. Fig. 7(a) depicts the Pareto curves when the channel states have bad quality, p G,B = 0.8. CRPL saves energy, but mainly because of reliability: many packets are not delivered to the sink, and do not consume energy. Indeed, exploiting one unique parent increases the probability the packet is not received correctly, even after a few retransmissions . We observe that ADP has the highest throughput and it has a lower energy consumption compared with MPaG. We guess this significantly higher throughput justifies the slightly larger energy consumption.

Similar results are shown in Fig. 7(b) where the channel qualities between each radio link are higher at p G,B = 0.2. MPaG provides a better throughput than CRPL, since it has wider degrees of freedom for selecting multiple parents for every timeslot. Since ADP makes scheduling decision based on the expected rewards, disturbance of stochastic channel is thus reduced. Hence, its performance is better than MPaG. In the remaining scenarios, we set the control parameter δ = 50 which is the middle point of these Pareto curves.

Impact of the channel quality

We investigate the performance of the policies under different channel qualities since they impact significantly the performance of the scheduling. Figure 8(a) and Figure 8(b) confirm the strong dependency with the channel quality. Obviously, the throughput of ADP, CRPL and MPaG increases with a better channel quality: less packets are lost, meaning also less retransmissions. However, It provides the highest throughput compared with CRPL and MPaG.

On other side, ADP is the most energy efficient strategy (fig. 8(b)): the quantity of energy spent by the network for each packet received by the sink is minimal. Indeed, using multiple parents helps to reduce the energy consumption by increasing the reliability. By effectively selecting several parents and carefully considering the channel quality, we can avoid the packet losses by distributing the traffic among several parents which have a good channel quality. In other words, CRPL and MPaG waste energy for packets which are not correctly received by the next hop because of unreliable links.

In addition, Figure 8(c) shows the energy per total transmissions. This energy is calculated by taking a ratio of the total energy consumed by all the nodes to the total number of transmissions that include both successful transmission and error transmission. ADP consumes the highest energy to transmit one packet especially when the channel quality is bad. The main reason is that the child i needs to transmit with a sufficient power to reach all its parents j ∈ P i : e i (t) = max j∈Pi e i,j (t).

Impact of the external interference

We investigate the performance of policies under the different probability that the external interference occurs. The results in Figure 9 have two interesting features. First, when external interference occur more frequently (p ext ≥ 0.8), the ADP cannot predict the behavior of the channel quality properly. Therefore, the performance of the ADP slightly decreases in comparison with the MPaG which use instantaneous channel quality to make decision. Second, the gap between the CRPL and the ADP, MPaG increase when more external interference occurs. By using multi-parent to forward data, both ADP and MPaG policies can combat with the external interference better than the CRPL which use single parent to forward data does.

Impact of the duty cycle ratio

We evaluate the impact of the number of timeslots in a cycle (Fig. 10). We vary the timeslot in a cycle from 50 to 150. The throughput slightly increases with a larger number of timeslots. Indeed, the throughput is proportional to the number of transmission opportunities, and the pressure reduces when the cycle (slotframe) is larger. In other words, we have the same quantity of traffic to transmit in a single slotframe while increasing the number of possible timeslots. However, incrementing the number of timeslots does not significantly affect the energy consumption. This means that these policies, including ADP, are scalable with the number of timeslots in a cycle.

Reliability

Finally, we provide the packet loss ratio for each policy under different channel qualities. Obviously, less packets are lost with reliable links (i.e. larger channel quality).

We can observe in Fig. 11 that ADP outperforms MPaG and CRPL concerning the packet loss rate. As we mention before, using multiple parents in ADP reduces the packet losses. Thus, ADP obtains a low energy consumption and an high throughput.

In addition, Fig. 11(b) illustrates the packet error rate when varying the duty cycle ratio. The error rate is only marginally impacted by the duty cycle ratio. We can remark that ADP performs significantly better than MPaG and CRPL when we have an high pressure, i.e. less timeslots to schedule all the traffic. Thus, our scheduling solution is efficient to schedule all the transmissions while limiting the energy consumption and presenting an high spectral efficiency.

Figure 1 :

 1 Figure 1: Structure of the ieee 802.15.4-TSCH superframe

Figure 2 :

 2 Figure 2: DODAG structure of RPL

Figure 3 :

 3 Figure 3: Opportunistic Multiparent Transmission

Figure 4 :

 4 Figure 4: Illustration of a 2 states Markovian Channel model

i

  (t) are an indicator of the transmission random variable, and the energy consumed by the sensor i under channel states w.

Figure 5 :

 5 Figure 5: Random network topology used in evaluation

Figure 6 :

 6 Figure 6: Convergence of the ADP policy

2 Figure 7 :

 27 Figure 7: Throughput and energy consumption under different channel quality.

Figure 8 :Figure 9 :

 89 Figure 8: Throughput and energy consumption under variant channel quality, p B,G .

Figure 10 :

 10 Figure 10: Throughput and energy consumption under variant of timeslots in cycle, T .

Table 1 :

 1 Notation

Table 2 :

 2 Network parameter Approximate dynamic programming policy (ADP) is our proposition. Contrary to CRPL, the ADP considers all the parents. By using Algorithm 1, we solve the original dynamic programing as follows:

	Parameters	Values
	# Sensor node and # sink	40 and 1
	Simulation area	40 × 40m 2
	Transmission range	15m
	Interference range	30m
	Transmission rate (r)	250 kbps
	Timeslot duration	10 ms
	Data transmission duration	4.256 ms
	Mini-timeslot duration	0.672 ms
	# Max retransmission	3
	# Max parents	4
	Bandwidth (B)	20kHz
	Noise (N 0 )	-90dB
	Energy budget for each cycle (E m,i ) 500mW
	Tradeoff parameter (δ)	10 to 90
	3.

Acknowledgments

This work was partially supported by the PHC STAR 2012 program (Korean and French governments) under contract DCS and by the French National Research Agency (ANR) project IRIS under contract ANR-11-INFR-016

Conclusion

Channel Hopping MAC are considered one of the most promising solution for industrial networks. ieee 802.15.4-TSCH proposes in particular to assign time-frequency blocks for each radio link, coupled with channel hopping to improve the reliability. We propose here a new scheduling policy to exploit an opportunistic forwarding scheme: during each timeslot, the next hop is dynamically chosen among the next hops which received correctly the packet. We propose consequently to improve the reliability since the transmission is successful if any of the parents correctly received the packet. A node may exploit in the same timeslot both unreliable and reliable links to improve the energy efficiency.

We proposes an Approximate Dynamic Programming (ADP) policy to schedule during each timeslot non-interfering links while optimizing the energy and the spectral efficiency. We formulate a policy using a Markovian model for the radio channel quality. Simulations results highlight the interest of such feature to improve both the reliability and the energy consumption.

While we demonstrated the interest of opportunistic forwarding, we have now to investigate the most accurate scenarios where this technique has to be adopted. In particular, a transmission requires several receivers to stay awake: because a node can listen to one channel at a time, we create a more constrained coloring problem. We aim at investigating the particular scenarios (i.e. for which radio links) this opportunistic strategy is the most recommended?

Besides, we assumed here the channel states are known at the beginning of the slotframe. How could we propose a schedule which relaxes this assumption? Could prediction algorithms help to solve this problem?

We also plan to investigate experimentally the performance of this strategy, implemented in a Path Computation Engine (PCE). We aim at providing also a traffic adaptive approach: when a new flow is accepted, the schedule is modified and the network reconfigured.


Xavier Sauvage
email: xavier.sauvage@univ-rouen.fr

Simona Moldovan

Fabien Cuvilly

M Bahri

T Grosdidier

In-situ transmission electron microscopy investigation of the influence of hydrogen on the oxidation mechanisms of fine grained magnesium

Keywords: Magnesium, hydrogen, in-situ microscopy, grain boundaries, oxidation

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Hydrogen storage in solid state materials has attracted a wide interest during the past years since it is considered as one of the safest and most effective for mobile applications [START_REF] Cox | Hydrogen: its technology and implications[END_REF][START_REF] Schlapbach | [END_REF]. Magnesium and magnesium based alloys have been deeply investigated because they offer theoretically a high hydrogen capacity (up to 7.6wt.% H in the MgH 2 phase), a low density and a relatively low cost. However, using magnesium hydrides for hydrogen storage applications is hindered by its slow hydrogen absorption and desorption kinetics. The poor hydrogen charge kinetics is usually attributed to surface magnesium oxides and a low diffusion rate of H in MgH 2 . Besides, relatively high dehydrogenation temperatures (beyond 600K for MgH 2 ) are directly linked to the strong Mg-H binding energy [3]. The kinetics and mechanisms of metal hydrides formation has been investigated for quite some time [4] and based on this, several approaches have been proposed to improve the kinetics of hydrogen exchange with Mg: i) the introduction of catalysts or alloying elements to favor the dissociation of H 2 molecules or to reduce the binding energy between Mg and H [5], ii) the introduction of crystalline defects to promote the diffusion of hydrogen [6][7][8][9][10][11]. However, Mg and Mg alloys oxidize very quickly even at low temperature and at very low O 2 partial pressure. It has been shown for example that at 31°C, under 10 -5 Pa O 2 a nanoscale layer of MgO form on the surface of a Mg-2.63%Al alloy in few seconds [12]. This is connected to the extremely high affinity of O with Mg giving rise to a very negative formation enthalpy for MgO (about -600 kJ/mol [START_REF] Wriedt | The Mg-O (Magnesium-Oxygen) System[END_REF]) at room temperature with a corresponding equilibrium O 2 partial pressure below 10 -35 Pa [START_REF] Hasegawa | Treatise on Process Metallurgy[END_REF]. This fast oxidation might be a critical issue for the application of Mg or Mg based alloys for solid state hydrogen storage because even under high H 2 pressure some residual O 2 cannot be avoided. Since the formation enthalpy of H 2 O is only of -286 kJ/mol [START_REF] Cox | CODATA Key Values for Thermodynamics[END_REF] and that of MgH 2 of about -75kJ/mol [START_REF] Stampfer | [END_REF], oxidation is unavoidable. Besides, the MgO surface layer reduces the hydrogenation and dehydrogenation kinetics because it acts as a diffusion barrier against H and it has been reported that after a large number of cycles, the storage efficiency might decrease [10,11] which could be attributed to a progressive increase of the volume fraction of MgO. The growth of MgO (fcc structure, Fm-3m space group) is controlled by the diffusion of Mg toward the surface and it is important to note that at a temperature higher than 400°C the kinetics may change due to Mg sublimation [17][18][19]. Thus, the understanding of the interplay between the oxidation of Mg at low O 2 pressure and the hydride formation (effect of H 2 ) is of peculiar importance. To this end, the present work investigates the oxidation mechanisms of Mg under low O 2 partial pressure with or without H 2 .

Since crystalline defects seem to promote hydrogenation, a special emphasis was also given on the role of grain boundaries. Thus, Transmission Electron Microscopy (TEM) observations were carried out on ultrafine grained Mg under high vacuum conditions (10 -5 Pa) and under a H 2 pressure of 10 5 Pa at a temperature up to 400°C thanks to an in-situ specimen holder [20,21].

Experimental details

The ultrafine grained Mg material used here was prepared from a commercial purity (99.8%) atomized powder consolidated by severe plastic deformation using High Pressure Torsion [22]. TEM samples were prepared using a Helios (Thermofisher) Plasma Focused Ion Beam (FIB) operated with Xe ions under an accelerating voltage of 30 kV. A tungsten protective layer was deposited on the surface prior to the milling and thinning procedures to limit irradiation damages and implantation of Xe. For in-situ experiments under a pressure of 10 5 Pa of H 2 , thin foils were deposited and welded with tungsten on the SiN membrane of the chip used in the in-situ TEM holder. For in-situ experiments without H 2 thin foils were welded on a Cu grid.

TEM observations have been carried out both in conventional mode with a parallel beam (including diffraction) and in scanning mode (STEM) using a Bright Field (BF) and a High Angle Annular Dark Field (HAADF) detector. In-situ TEM experiments under a pressure of 10 5 Pa of H 2 were carried out in a Cs probe corrected JEOL 2100F microscope operated at 200kV. Sample was mounted on an "Atmosphere" Protochips specimen holder, designed as an environmental cell able to withstand high temperature (up to 1000°C) and pressure conditions. A pressure of 10 5 Pa of H 2 was introduced after a complete purge of the system with Ar. The O 2 partial pressure as measured by the spectrometer connected to the specimen holder outlet was 10 Pa during the experiment. A heating rate of 0.3°C s -1 was then applied up to 400°C. In-situ TEM observations without H 2 were carried out with a JEOL ARM 200F microscope operated at 200 kV using a double tilt heating holder (Gatan 652 MA) under a pressure of 2 10 -5 Pa and an O 2 partial pressure below 10 -5 Pa. The heated volume is much larger with this latter specimen holder which may leads to significant sample drift, gas desorption and possibly to some local temperature overshoot. To minimize these issues, a slightly different heating procedure was applied to reach 400°C. A heating rate of 1°C s -1 was applied up to 150°C, then 0.5°C s -1 up to 300°C where the sample was held during 5min, and then 0.2°C s -1 up to 400°C. Thus, the main difference stands at temperatures below 300°C, and it is believed that it does not affect significantly the mechanisms observed at 400°C.

Results and discussion

Figure1: STEM-BF image showing the ultrafine grain structure with large fraction of GBs.

Corresponding SAED pattern (aperture size 1.6m) where spots are indexed with hcp Mg reflections and the diffuse rings are attributed to nanoscaled MgO particles on the foil surface.

As shown on the STEM Bright Field (BF) image (Fig. 1), the material processed by severe plastic deformation exhibits a submicron grain size, in agreement with an earlier study [22,23]. The grain size is slightly finer than in bulk Mg processed by SPD [X2] due to a small fraction of nanoscaled oxide particles pinning boundaries. On the selected area electron diffraction (SAED) pattern (Fig. 1 inset), the main spots correspond to hcp Mg and additional diffuse rings to nanoscaled MgO particles. Few of them originate from the initial powder process but most of them have nucleated on the sample surface in the vacuum chamber or during the transfer from the FIB to the TEM. Pa). No significant grain growth occurred and only small local changes of the contrast could be observed. It is the result of recovery of lattice defects that were introduced during the severe plastic deformation processing. This relatively high thermal stability of the UFG structure might be attributed to the pinning of triple lines by the thin foil surface as reported for Al alloys observed by in-situ TEM [24]. Meanwhile, within a very short period of time (5min at 300°C, Fig. 2(a)), a fully transformed area (width 1m, depth 0.4 m) with a bright contrast appears at the TEM sample edge (top of Fig. 2(a)). It quickly grows at 400°C, expanding downward (Fig. 2(b) and 2(c)) along a direction that is perpendicular to the sample edge and reaching a depth of about 2m. Surprisingly, the lateral growth is more limited and the width remains relatively constant. The high resolution TEM image and the corresponding SAED pattern (Fig. 2(d)) taken in this region show that the original hcp Mg was fully oxidized leading to the formation of nanoscaled MgO particles.

Figure3: TEM-BF images showing the growth of MgO along GBs (arrowed) in the UFG Mg under 10 5

Pa of H 2 and 10 Pa of O 2 , after 5min (a), 7min (b) and 10min (c) at 400°C. STEM-HAADF image after 40min at 400°C and SAED pattern recorded in the oxide (inset) (d)

Fig. 3 shows a sequence of TEM BF images taken in situ during holding at 400°C under a high partial pressure of H 2 (10 5 Pa). While no significant change was detected below 400°C, at this temperature, the transformation of the structure starts along GBs. Some thin layers with a bright contrast on TEM BF images (arrowed on Fig. 3(a), 3(b)) start to grow after only few minutes at 400°C but no transformation occurs at the sample edge (located on the bottom right of images). After 10 min the transformation has taken place in the whole microstructure (Fig. 3(c)) and a network covers initial crystalline defects with layers having a thickness ranging from 20 to 100nm. They are darkly imaged on STEM-HAADF images (Fig. 3(d)) and the SAED pattern clearly indicates that they are the result of the nucleation of nanoscaled MgO particles. Although the partial pressure of H 2 was relatively high, it should be noted that MgH 2 phase was not detected during the experiment. For both in-situ TEM experiments (with and without H 2 ), no significant differences could be seen between regions kept a long time under the electron beam to track real time changes and adjacent regions that have been checked more occasionally. Thus, even if the influence of the electron beam on the transformation cannot be completely ruled out [25], it is believed that it has no major effect and in any case it cannot explain the differences seen under vacuum conditions and under 10 5 Pa H 2 .

Figure4: Schematic representation of the evolution of the TEM lamellae during the in-situ experiment. (a) initial state with a thin oxide layer on the surface, (b) oxidation under vacuum conditions, (c) oxidation under a high partial pressure of H 2 .

A comparative schematic representation of the oxidation mechanisms of the UFG Mg under vacuum conditions as well as under 10 5 Pa H 2 is represented in Fig. 4. The initial sample exhibits a nanometer scaled MgO layer on the surface (Fig. 4(a)). It is known that further oxidation of Mg requires the outward diffusion of Mg which is possible only at a temperature higher than room temperature [17][18][19]26]. During heating up to 400°C, this layer does not significantly grow because the oxygen partial pressure is low and, thus, the driving force for the outward diffusion of Mg remains rather limited.

Besides, the thermal expansion coefficient of Mg being close to that of MgO, the thermal dilatation does not lead to a stress that could break up the layer and promote the oxidation of the underneath Mg. Under vacuum conditions (without H 2 ) however, it was shown that the oxidized regions could grow along a direction perpendicular to the sample edge (Fig. 2). This region appears with a bright contrast on bright field images, indicating that a significant amount of Mg was sublimated. The extreme situation would be that all Mg contained inside the original MgO crust would evaporate and only a thin layer of MgO would remain such as the hollow structures reported by Pasquini and coauthors [27]. However, in the present situation the intensity of MgO reflections on SAED patterns is much stronger in the reacted region than in the original sample, indicating that some additional MgO nanoparticles have grown. The resulting structure evolution is schematically represented in Fig. 4

(b).

The reaction is very localized, and it starts at the sample edge. In this location, the curvature is large and it may promote the sublimation of Mg under vacuum conditions [17][18][19]26]. Then, local volume changes create stresses leading to cracking of the external MgO crust, facilitating concomitantly the sublimation of Mg and the inward diffusion of O 2 . As soon as it starts, this mechanism can promote the nucleation and growth of additional MgO nanoparticles and it would propagate toward a direction perpendicular to the sample edge as observed experimentally. Under 10 5 Pa H 2 , a much slower kinetic and a more homogenous transformation were observed (Fig. 3). This could be explained by a significantly reduced sublimation of Mg at higher pressure, but it is important to note as well that the atomic mobility of Mg might be also reduced as a result of the interaction between H and vacancies. Then, the high density of crystalline defects and especially GBs resulting from severe plastic deformation play a key role (Fig. 4(c)). They act as fast diffusion paths for O 2 coming from the outside and they are easy nucleation sites for MgO. In principle, this mechanism could also operate under vacuum conditions, but it exhibits such a low kinetic that it does not play a significant role on the overall transformation.

Conclusions

We have shown that the oxidation of Mg under low partial pressure of O 2 clearly occurs with different mechanisms under vacuum conditions and under H 2 at atmospheric pressure. Crystalline defects like GBs enhance the hydrogenation of Mg but also promote the nucleation and growth of MgO. This could be detrimental for application of UFG Mg based alloys as solid state storage media for hydrogen. Due to the extremely negative formation enthalpy for MgO, nanoscaled oxide layers are unavoidable on Mg alloys even under high H 2 partial pressure. At low temperature and low O 2 partial pressure, such oxide layers do not grow significantly but during hydrogenation, the growth of hydrides may generate stresses that could break up the oxide layer promoting both the hydride formation (MgH 2 , -75 kJ/mol) but also the oxidation (MgO, -600kJ/mol). This feature is another important reason to develop Mg alloys with dehydrogenation temperature as low as possible.

Figure2:

  Figure2: STEM-BF images showing the growth of MgO inside the UFG Mg at low partial pressure of O 2 and H 2 (below 10 -5 Pa) (a) after 5min at 300°C, (b) after 2min at 400°C and (c) after 5min at 400°C. (d) HRTEM image taken in the oxidized region showing the nanoscaled structure of the MgO oxide, confirmed by the SAED (inset)

Acknowledgements

Some of the TEM experiments have been carried out on the GENESIS facility which is supported by the Région Normandie, the Métropole Rouen Normandie, the CNRS via LABEX EMC3 and the French National Research Agency as a part of the program "Investissements d'avenir" with the reference ANR-11-EQPX-0020. Part of this work was also supported by the French State via the program "Investment in the future" operated by the National Research Agency (ANR) and referenced by ANR-11-LABX-0008-01 (Labex DAMAS).


Mengchuan Zou

Jia-Liang Lu

Fan Yang

Mathilde Malaspina

Fabrice Theoleyre

Min-You Wu

Distributed Scheduling of Enhanced Beacons for IEEE802.15.4-TSCH Body Area Networks

Body Area Networks (BANs) expect to exploit IEEE802.15.4-2015-TSCH, proposing an efficient MAC layer for wireless industrial sensor networks. The standard relies on techniques such as channel hopping and bandwidth reservation to ensure both energy savings and reliable transmissions. With the expected growth of the BAN usage, we must now consider dense topologies, and interference. In this paper, we propose a rescheduling algorithm to avoid the collisions among the Enhanced Beacons (EB): each coordinator is able to adapt distributively its transmission to avoid interference. Indeed, EB losses impact negatively the performance of a BAN. We also optimized conjointly the neighbor discovery mechanism since a multichannel MAC would else increase too much the discovery delay. Our simulations validate the relevance of our discovery and scheduling mechanisms to cope with a very dense deployment of interfering BANs.

Introduction

BANs consist in small wearable wireless devices expected to fulfill the society needs in a variety of applications such as ubiquitous monitoring, health-care, entertainment and multimedia, and training. The PAN coordinator often collects measures transmitted from the wearable devices in its BAN.

The IEEE802.15 working group is currently finalizing the IEEE802.15.4-2015 standard [START_REF]IEEE Standard for Local and metropolitan area networks-Part 15.4: Low-Rate Wireless Personal Area Networks (LR-WPANs) Amendment 1: MAC sublayer. IEEE Std[END_REF]. In particular, the TSCH mode aims at improving the reliability for industrial sensor networks in noisy environments. A common schedule aims at reserving a certain amount of bandwidth for each flow, and channel hopping aims at defeating narrow band noise. This standard is particularly accurate for Body Area Networks, where devices aim at transmitting periodically their measures to the PAN coordinator (i.e. BAN gateway).

However, IEEE802.15.4-TSCH was originally designed for a large multihop wireless sensor network. In Body Area Networks, we rather face to a user centric topology: one PAN coordinator attached to a collection of devices. However, because we expect to have a large collection of co-located BANs, we will face to an explosion of collisions: each BAN computes independently its own schedule. We must propose a certain cooperation among different BANs to detect collisions and to adapt locally their schedule. Besides, BANs require a very short network attachment delay: a person may exchange data sporadically within a group of individuals (aka. opportunistic mobile social networks [START_REF] Pietiläinen | Mobiclique: Middleware for mobile social networking[END_REF]). Thus, we must propose a mechanism to detect quickly neighboring BANs.

Due to the dynamic environment for BAN communication, one important assumption is that a newly arrived node has no initial information about the neighborhood. Therefore it needs to set up a listening schedule determining when, for how long, and on which channel it should listen to the beacons. When it receives an Enhanced Beacon (EB), it is then able to join the corresponding BAN. We chose here to optimize this discovery delay, i.e. waiting time before receiving the first EB.

In our scenario, we consider co-located BANs, possibly mutually interfering (fig. 1). However, we consider here only single hop traffic: only neighboring PAN coordinators /devices may exchange data packets. We have consequently a collection of stars, independent concerning the traffic, interdependent concerning interference.

The contributions of this paper are fourfold:

1. we introduce a cooperation among independent BAN: while they don't exchange traffic, we propose mechanisms to locally re-schedule the transmissions of beacons to limit the number of collisions; 2. we reduce the schedule problem (and the detection of collisions) to a classical maximum-weight independent set problem in undirected graphs; 3. we also propose a mechanism so that a new node is able to discover quickly an existing neighboring BAN, even when its EBs use channel hopping; 4. we highlight the relevance of our approach with omnet++ simulations. When a timeslot starts, a device knows if it has to wake-up to transmit or receive a packet. A slot can be either dedicated (without contention) or shared (a CSMA-CA mechanism handles contentions). Thus, a node turns off its radio for all its unused slots, where it is neither receiver nor transmitter.

Related Work

To improve the reliability, TSCH proposes to implement a channel hopping scheme. To each transmission opportunity is attached a channel offset. Let's consider the schedule illustrated in figure 2. Three timeslots/channel offsets are dedicated for the advertisements of the nodes A, B and C (in green). Two other slot/channel offsets are dedicated for some radio links (in pink), for their unicast transmissions.

Palatella et al. proposed a centralized scheduling for a multihop IEEE802.15.4-TSCH [START_REF] Palattella | On optimal scheduling in duty-cycled industrial iot applications using ieee802.15.4e tsch[END_REF] for unicast transmissions. Accetura et al. also proposed a decentralized version of their scheduling algorithm [START_REF] Accettura | Decentralized Traffic Aware Scheduling for Multi-hop Low Power Lossy Networks in the Internet of Things[END_REF]. However , these approaches only work within a single BAN, i.e. they don't address the case of multiple interfering and concurrent BANs.

Neighbor discovery

Two major methods exist to discover a neighboring node: passive discovery: a new node has to listen for the beacon packets from its neighbors. The period of beacon transmissions directly impacts the discovery delay. active discovery: a new node sends an hello packet, and neighbors acknowledge it to notify the transmitter of their presence. In multichannel, it is related to the birthday protocol [START_REF] Michael | Birthday protocols for low energy deployment and flexible neighbor discovery in ad hoc wireless networks[END_REF]. This method often performs faster, but consumes more resource, and may create collisions with data packets.

A new device has to discover very fast a BAN to attach to. However, multichannel increases the convergence delay, since a receiver is deaf to the transmissions on different channels. In Bluetooth, a transmitter sends avertissements and a listener must receive this advertisement before exchanging packets. Thus, a node must change randomly its role between listener and transmitter for Peer-To-Peer topologies [START_REF] Drula | Adaptive energy conserving algorithms for neighbor discovery in opportunistic bluetooth networks. Selected Areas in Communications[END_REF].

In multichannel, scanning all the channels takes a long time. Dasilva et al. proposed to use a complete permutation of all possible channels to scan, which decreases the convergence delay [START_REF] Dasilva | Sequence-based rendezvous for dynamic spectrum access[END_REF]. When a group of nodes can cooperate, they can exchange information to accelerate the discovery [START_REF] Chen | Group-based discovery in low-duty-cycle mobile sensor networks[END_REF][START_REF] Nardis | Role of neighbour discovery in distributed learning and knowledge sharing algorithms for cognitive wireless networks[END_REF]. [START_REF] Karowski | Optimized asynchronous multi-channel neighbor discovery[END_REF]. Later, they constructed also an optimal schedule, to discover in priority the nodes with a larger duty cycle ratio [START_REF] Karowski | Optimized asynchronous multichannel discovery of ieee 802.15. 4-based wireless personal area networks[END_REF]. However, they focus on the listening device, so that their optimization could only be applied to a fixed advertising schedule.

Collision-Free Schedule of multiple BANs

We consider a dense collection of Body Area Networks, with one PAN coordinator per BAN. Any pair of nodes may interfere with each other, and create collisions. We adopt in this paper the notation described in Table 1.

Problem Statement

Each BAN may select a different duty cycle ratio. In particular, they may choose a different slotframe length (the cycle duration of the schedule). Each node sends an Enhanced Beacon (EB) at a fixed interval during an advertisement slot of the schedule. More precisely, a node u sends an EB every:

T EB (u) = T cst * 2 BO (1)
where T cst is a duration defined by IEEE802.15.4-2015, and BO is the beacon order (constant) selected by the node u (the rest of the notation is described in table 1). IEEE802.15.4-TSCH adopts a FTDMA approach. We consider the PAN coordinator is co-located with the Path Computation Engine (PCE). It computes which channels and timeslots have to be used for all the pairs of active nodes, rl1,t1,c1 rl1,t2,c2 rl1,t2,c1 rl1,t1,c2 rl2,t3,c1 rl2,t4,c2 rl2,t4,c1 rl2,t3,c2 Fig. 3. Conflict Graph Model for ASP and distributes this schedule. In particular, it assigns an advertisement slot for each node to transmit periodically its EBs.

The PAN coordinator changes dynamically the schedule when it detects a collision with a neighboring network.

A new device has to receive the Enhanced Beacons to decide which network it should join. We adopt consequently a similar objective as [START_REF] Karowski | Optimized asynchronous multichannel discovery of ieee 802.15. 4-based wireless personal area networks[END_REF]: we aim at maximizing the number of EB nb rx (EBs) received during a scanning duration T scan /nb rx (EBs). All the PAN coordinators have to compute a schedule for their network, where the number of collisions between EBs is minimized.

We consider the different BANs are able to maintain a synchronization, so that all the schedules are aligned. It may be implemented by maintaining a synchronization with neighboring BA, such as [START_REF] Lipa | Firefly-inspired and robust time synchronization for cognitive radio ad hoc networks[END_REF] does.

Problem Formulation

We use the conflict graph model to define an accurate schedule. Let G c = (V c , E c ) be an undirected graph, where V is the set of radio links, and E is the set of mutually interfering radio links. G c is named the conflict graph. The schedule consists in the set of activated radio links v = (rl, t, c) ∈ V c , where rl is the radio link, t a timeslot, and c a channel offset (cf. Fig. 3). For the sake of simplicity, a radio link may also be denoted by the transmitter only if it corresponds to a broadcast (i.e. EB).

An edge (u, v) ∈ E c indicates transmitters u and v interfere with each other:

1. either both transmitters own to the same BAN. The PAN coordinator can easily reallocate the transmitters to use different timeslots / channels; 2. or both transmitters own to different BAN: the corresponding PAN coordinators must cooperate to avoid this kind of overlap.

Let's consider the nodes u and v with their associated beacon periods (T EB (u) and T EB (v)). The pair of nodes should not share any common timeslot and channel for any of their Enhanced Beacons. If they have different slot frame lengths, a collision may occur if they have the same channel offset and a common active slot to advertise their EB during at least one slotframe:

∃(i v , i u ) ∈ N 2 / slot EB (v) + i v * T EB (v) = slot EB (u) + i u * T EB (u) (2)
This equation is an indefinite equation, with a solution (i u , i v ). We may use the Extended Euclidean algorithm to check the existence of an integer solution.

We are then able to construct the conflict graph, with all the edges which respect the equation 2.

Optimization Function

A node may attach to the network as soon as it discovers an accurate neighbor. Let w(u) be a weight associated to a node u, denoting the amount of EBs it transmitted during the scanning time:

w(u) = T scan -slot EB (u) T EB (u) (3)
Our objective consists in maximizing the total amount of EBs received by all the devices during the scanning period:

Objective = max u∈V w(u) (4)

Reduction to the Maximum-Weight Independent Set Problem

When no collision occurs, the number of received EBs equals to the number of sent EBs. More precisely, no edge is present in the conflict graph between any pair of vertices: they form an independent set. Let us consider the undirected graph G c = (V c , E c ). An Independent Set (IS) is a set of vertices such that no edge exists between any pair of vertices. Let S be the set of all possible independent sets:

S ∈ S ⇔ ∀(u, v) ∈ V 2 c ∩ S 2 , (u, v) ∈ E c (5)
If the set of active vertices in G c (i.e. radio links) forms an independent set, no collision arises: the schedule of EBs is optimal. Let S be the set of all possible independent sets:

if S ∈ S, Objective = u∈S w(u) (6)
Since no conflict exists in the conflict graph, the maximization objective can be removed safely: no EB is dropped because of collisions. In conclusion, the optimization problem turns out to be a maximum-weight independent set problem (MWIS) in a undirected graph. We schedule then a MWIS in a given timeslot / channel offset. MWIS consists in finding an independent set S ⊆ V , which has the maximum weight:

max v∈S w(v) (7)
As we aim at maximizing the number of EBs received, our problem may be reduced to the MWIS problem, known as an NP-hard problem [START_REF] Trevisan | Inapproximability of combinatorial optimization problems[END_REF].

We propose here a localized heuristic. Indeed, a centralized approach presents the following limits:

1. Overhead and Consistency: An exhaustive search requires a global knowledge. All the schedules owning to different BANs must be shared. Practically, a huge volume of information has to be exchanged, and inconsistencies may arise because of packet losses; 2. Complexity: An exhaustive exploration of the solutions is unrealistic for devices with limited capabilities. Besides, we cannot assume a server (connected to the PAN coordinators) is dedicated to this computation.

Our algorithm proceeds in the following way:

Step 1 -Division: we first create groups of devices, sharing the same EB period. We can assign orthogonal resources (i.e. channel offsets) to different groups to avoid collisions. This way, we avoid collisions among devices with different EB periods;

Step 2 -Initialization: a coordinator selects an initial schedule for all the EBs in its BAN. Each device maintains the list of occupied cells in its neighborhood, to detect collisions (i.e. at least one interfering device exists); Step 3 -Collision resolution: we propose heuristics to re-schedule the colliding slots. We use hash tables to detect collisions and we re-allocate the concerned timeslots while limiting the number of changes in the schedule; Step 4 -Backtracking: if the algorithm does not succeed to allocate a timeslot for each EB, we backtrack to the step 1, by selecting a group with a larger EB period.

Division: Dealing with Different EB Periods

We consider the same conflict graph as previously: a vertex is the triplet < device, timeslot, channel of f set >, and two vertices are linked together if the associated devices interfere. We can remark the following properties:

1. All vertices representing the same device (for different EBs) form a clique in the conflict graph; 2. when considering a set of vertices with the same EB interval and using the same channel offset, the collision is present for all the timeslots, and can be easily detected.

So, we propose a partition and re-grouping method:

1. we divide the graph into cliques. We insert an edge between two cliques if they are neighbors in the conflict-graph; 2. we merge the cliques with the same EB interval into a group. We will assign later a given channel offset to a group;

3. then, we assign a given timeslot for each device within a group: they should not interfere since they use the same channel offset. Assigning distinct timeslots is sufficient since they have the same T EB .

By adopting a three-steps approach, we are able to deal with devices with different EB intervals. Indeed, devices with different intervals are partitioned in distinct groups (i.e. different channel offsets). Then, we solve the conflicts among the devices with the same EB interval, using a TDMA repartition. Since times slots are distinct, they cannot collide in any slot frame: the period of repetition is the same for all of them -same T EB .

Group Merging If too many EB intervals exist, partitioning the graph would create too many groups. However, as equation ( 1) states, the EB intervals are multiples of 2. Let's denote by group i all the devices with an EB period equals to BO i . Several devices of the group i may actually be scheduled with the devices in the group i -1. The devices of the group i have either to be scheduled in different timeslots or in different slotframes. Intuitively, a slotframe of the group i contains two slotframes of the group i -1.

Obviously, we can merge any group i and j (i < j) of devices Finally, at most 2 BO j -BO i nodes of the group j may be schedule in the final same timeslot. Inversely, a device of the group i uses a given timeslot in all the slotframes.

Initialization: Assigning Timeslots to Each Device

All the devices which share the same EB interval are scheduled in the same channel offset, and the PAN coordinator assigns randomly one free timeslot for each of them. The PAN coordinator has to compute its schedule, and to push it to all the devices. The schedule table is actually the set of timeslots/channel offsets (row), and their corresponding occupation (0 if this timeslot is unoccupied by any transmitter).

Each PAN coordinator broadcasts its schedule periodically in dedicated packets, with an increasing sequence number. A neighbor is thus able to detect a timeslot collision, equivalent to a collision in both hash tables.

A node is able to maintain an up-to-date schedule table of its neighboring PAN coordinators:

any neighbor for which it stops receiving packets is removed from the neighborhood table after a certain timeout; only the last schedule is memorized for each neighbor (i.e. largest sequence number).

Thus, we guarantee a certain consistency in the decisions: each device is able to replace obsolete information from its neighborhood schedule table.

Collision Resolution in the Same Group -Linear Time Scanning

A PAN coordinator may detect a collision after the reception of the schedule from one neighbor. To solve the collisions, we use hash tables. More precisely, an hash table makes a correspondence between a key (here, a timeslot) and the value (1 if the timeslot is occupied by at least one node, else 0). A collision of timeslots means also a collision in the hash table. Thus, finding compliant schedules (i.e. interference free) is equivalent to resolving the collisions in the hash table.

Two methods exist to resolve collisions in hash tables:

1. separate chaining: each entry of the has table is a chained list of values; 2. open addressing: the values are stored in contiguous entries in the hash table.

Since the former approach does not maintain the original order in the hash tables, we adopt the open addressing method. When the network is very dense, many timeslots are occupied. To accelerate the convergence, we propose here to solve several conflicts simultaneously. The following two steps are required:

1. Preprocessing: for any channel, the node combines all the schedules present in the neighborhood table with the OR operator. Then, the node is able to compute the list of slots used by at least one of the BANs, and the list of the idle slots. 2. Linear time scan: we create two pointers (cf. Fig. 4.

3). The first one (in red)

points to the first colliding slot in our schedule, and the second one (in green) to the first idle slot in the merged schedules. Then, we modified our schedule: the colliding cell is moved to be placed in the next free cell (in the merged schedule). Then, the pointers keep on iterating, to solve the next conflict.

When resolving the conflicts, both pointers visit each slot exactly once. Thus, our algorithm runs in O(n) time. We have consequently a linear time rescheduling algorithm.

Backtracking: Group Change

If the previous search has failed, this means no timeslot is available.

We backtrack the algorithm to the step 3. The device joins a group with a lower EB interval, and re-executes the assignement to find an idle slot in the new group.

This backtracking method is particularly relevant when all the groups do not have the same number of devices. A BAN will be moved to another group to balance the load.

Analysis

Let's now consider the initialization step. We have nb tslots slots (all the timeslots in a slotframe, across the nb ch possible channel offsets). The number of EBs to be sent is n, and timeslots are assumed to be assigned randomly for initialization.

So, the expected number of collision-free EBs (n nocoll ) is the complementary of colliding EBs:

n coll = n * 1 - n k=2 nb tslots -(k -1) nb tslots (8)
We denote by ρ the ratio of the number of devices and the number of timeslots (ρ = n/nb tslots ). Thus ρ denotes the pressure for the scheduling process. The ratio σ of conflicting EBs is consequently:

σ = n coll n = 1 - n k=2 n -ρ * (k -1) n (9)
Because of the well-known birthday problem [START_REF] Frank | A generalized birthday problem[END_REF], the ratio of collisions will be quite large when ρ grows.

Our algorithm solves the conflicts created in the initialization phase. We group the devices by their EB interval, and thus their channel offset. We denote by x i the number of devices using the channel offset i. If the following condition holds, our scheduling algorithm is able to assign non colliding slots:

∀i ∈ [0..nb ch ], x i ≤ nb tslots nb ch , (10)
In other words, there exist enough timeslots to schedule all the devices of a group.

According to [START_REF] Borodin | A time-space tradeoff for sorting on a general sequential model of computation[END_REF], our algorithm converges with the probability:

P ∀i, x i ≤ nb tslots nb ch = 1 -nb ch * n nb tslots nb ch * ( 1 nb ch )
nb tslots nb ch [START_REF] Karowski | Optimized asynchronous multichannel discovery of ieee 802.15. 4-based wireless personal area networks[END_REF] This represents a lower bound for the probability of convergence. For each iteration, we have:

1. After probing and changing a schedule on one channel i, we have x t+1 i ≤ x t i which means x i doesn't increase. 2. If the device switches to another channel j, we have

x t+1 i ≤ x t i -1, x t+1 j ≤ nb tslots nb ch (12)
so that there is also ∀i, x i ≤ nb tslots nb ch .

Moreover, if ∃i, x i > nb tslots nb ch , at least one device is able to switch to another channel offset to find a free timeslot. So eq. 11 is a lower bound of convergence probability.

Performance Evaluation

We used Castalia 3.0 (http://castalia.npc.nicta.com.au), a simulator based on the OMNeT++ framework version 4.1 (http://www.omnetpp.org). Castalia is widely used to simulate a Body Area Network. For the initialization, each coordinator chooses independently and randomly a timeslot to send EBs.

We simulated a multi-BANs scenario where a set of PAN coordinators are directly connected to a random number of devices. The number of coordinators varies between 5 and 20 (with increment of 5). Besides, the ratio of slot occupation varies from 10% to 90%, with increment of 20%. We run 500 simulations for each set of parameters.

We compared the following algorithms:

-PSV: the passive scan mode in IEEE802.15.4-2015 [START_REF]IEEE Standard for Local and metropolitan area networks-Part 15.4: Low-Rate Wireless Personal Area Networks (LR-WPANs) Amendment 1: MAC sublayer. IEEE Std[END_REF]. An arriving device just listens for the maximal possible length of time on each channel; -SUBOPT: this low-complexity algorithm computes a listening schedule [START_REF] Karowski | Optimized asynchronous multi-channel neighbor discovery[END_REF].

Intuitively, the device has not to scan all the timeslots when a neighbor sends very fast its EBs. It avoids these redundant timeslots; -EBAS: our rescheduling algorithm detecting collisions and reallocating the colliding devices to free timeslots.

We have the following main parameters / performance criteria:

ratio of occupation: the ratio of the number of devices (EB to schedule) and the number of timeslots; -Percentage of EBs received: number of EB received by a discovering device.

The higher this value is, the faster a device may discover a network to join; -Percentage of EB conflicts: ratio of EB which use a timeslot which collides with another EB (i.e. for at least one timeslot when both transmitters have not the same EB interval).

We first measured the number of EBs correctly received (Figure 5). The efficiency of SUBOPT and PSV decreases when the network comprises more coordinators: SUBOPT has been designed to reduce the discovery delay, but Fig. 5. Ratio of EBs received correctly (i.e. without collision) Fig. 6. Ratio of colliding EBs before EBAS algorithm doesn't try to re-schedule the colliding beacons. On the contrary, EBAS is much more scalable and successfully solves most of the conflicts even for a very large occupation ratio. Such feature is vital for very dense BAN deployments.

We also measured the percentage of colliding EBs without (respectively with) EBAS in Figure 6 (resp. Figure 7). Comparing both figures, we clearly notice EBAS is very efficient when less than 70% of the slots are occupied: it solves 100% of the collisions, re-allocating the incriminated devices. Even for a very large occupation ratio (e.g. 90%), only 10% of the EBs collide. On the contrary, a distributed random assignment rather leads to a ratio of 60% of collisions.

Finally, we measured the number of iterations with EBAS before obtaining a conflict-free schedule (Figure 8). For small BANs, only a few iterations are required (at most 4). Without surprise, the number of iterations grows with the occupation ratio. However, EBAS converges in less than 20 iterations, even in very extreme conditions.

Conclusion

We proposed here an algorithm to schedule the EBs transmissions when several Body Area Networks co-exist and mutually interfere. We proposed first a dividing strategy, grouping together the devices with the same EB. Then, we propose to detect and solve collisions after a random assignment. Neighboring BANs exchange their schedule to detect conflicts, and reallocate the timeslots while preserving the other collision-free schedules. Simulations prove the relevance of our approach: we reduce the number of collisions even in dense deployments.

In the future, we plan to combine a fast collision detection mechanism with our re-scheduling algorithm. We also aim at validating experimentally our solutions with complex radio propagation (and interference). Besides, we also aim at quantifying the impact of clock drifts on the accuracy of our re-scheduling process. Finally, we expect to investigate the performance of the proposed solution under different conditions (e.g. multi-hop traffic, QoS requirements).

Fig. 1 .

 1 Fig. 1. Multi-BAN Topology

2. 1 Fig. 2 .

 12 Fig. 2. Schedule in a IEEE802.15.4-TSCH network -illustration of a slotframe

Fig. 4 .

 4 Fig. 4. Linear Time Scanning

Fig. 7 .Fig. 8 .

 78 Fig. 7. Ratio of colliding EBs after EBAS algorithm

Table 1 .

 1 Notation used in the article IEEE802.15.4 proposes a passive discovery: a new device sequentially scans each channel for a sufficient long time. The scanning time should be sufficient to capture any Enhanced Beacon from a neighbor. A device may require in the worst case 8.7 hours to scan the 16 channels. To accelerate the discovery time, Karowski et al. presented a linear programming model describing the discovery process

	Notation Meaning
	TEB(u) the interval between two Enhanced Beacons (EB) of the node u (de-
	noted further EB interval)
	slotEB(u) the cumulative nb. of broadcast slots (EBs) for the node u since the
	beginning of the scan
	nb ch nb. of channels
	nb tslots nb. of timeslots for all the possible channel offsets
	ASN Absolute Sequence Number (≈ time)
	Tscan Duration of the scan of the discoverer (nb. of slots)
	nbrx(EBs) nb. of EB received during the scan by the discoverer
	S =< (rl, t, c) > the IEEE802.15.4-TSCH schedule S is a set of triplets <radio link,
	timeslot, channel offset>

Acknowledgment

This research was supported by NSF of China under grant No.61100210 and China 863 No. 2015AA015802 and by the French National Research Agency (ANR) project IRIS under contract ANR-11-INFR-016.