Pascale Minet
email: pascale.minet@inria.fr

Paul Muhlethaler
email: paul.muhlethaler@inria.fr

Ines Khoufi
email: ines.khoufi@inria.fr

Collision Avoidance on Shared Slots in a Wireless Slotted Network: Models and Simulations

In this paper we propose an analysis of a slotted based protocol designed for devices of the Internet of Thing (IoT). In contrast to other TDMA-based protocols this scheme uses a random technique to access shared slots which presents similarities with CSMA protocols. In practice the transmissions are scheduled in a given back-off window of slots whose duration allows the transmission of a packet and its acknowledgment. Therefore this protocol can be analyzed according to the methodology introduced by Bianchi for the IEEE 802.11 protocol even if the protocol studied differs in many aspects. The model we use is also particular because we succeed in obtaining a Markov model even if the scheme used to send a packet (in a node) may depend on the transmission of the previous packet.

We distinguish two protocols; in the first one, at the initial stage or after a successful transmission, the packets are transmitted without any back-off, whereas in the second protocol each transmission is always preceded by the count down of a random back-off. Extensive simulations validate the models of both protocols and a comparative performance evaluation is carried out.

I. INTRODUCTION

Our purpose is to model various methods of collision avoidance on shared slots in a wireless slotted network. All the methods studied in this paper are fully distributed and based on a probabilistic transmission by each network node. More precisely, each node draws a random backoff in a backoff window. This backoff is decremented at each slot. The node waits until the backoff is zero to be allowed to transmit. The methods vary in:

• the size of the backoff window: it may be constant or increased with the number of successive collisions. • the reset of the backoff window: after each transmission, or only after each successful transmission, or at each first transmission of a message, etc. • the increment of the backoff window: for instance after each unsuccessful transmission of a message, until a maximum value is reached. Two methods will be studied and modeled, including the method used by Time Slotted Channel Hopping (TSCH) which is specified in amendment e of the IEEE 80.15.4 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]. It is based on a time slotted medium access operating on several channels in parallel. Frequency hopping is used to protect against perturbations. TSCH has been designed for process automation, process control, equipment monitoring and more generally the Internet of Things. We focus on shared slots where all transmitters are allowed to transmit. These models will be validated through simulations on the NS3 simulation tool [START_REF]NS3 a discrete network event simulator for internet systems[END_REF].

The studies [START_REF] Park | Throughput and energy consumption analysis of IEEE 802.15. 4 slotted CSMA/CA[END_REF], [START_REF] Pollin | Performance analysis of slotted carrier sense IEEE 802.15.4 medium access layer[END_REF], [START_REF] Park | A Generalized Markov Chain Model For Effective Analysis of Slotted IEEE 802[END_REF], [START_REF] Wen | An Improved Markov Model for IEEE 802.15.4 Slotted CSMA/CA Mechanism[END_REF] analyze the slotted access of the IEEE 802.15.4 protocol and provide an evaluation of the throughput, average delay, energy consumption and reliability. All these papers propose nearly the same Markov chain model. In contrast to the present paper, the back-off evolves during the lifetime of the packet when it encounters collisions. However, when the packet is rejected (i.e; the maximum number of transmissions of this message has been reached and the last transmission collides) the protocol does not remember the actual value of the collision window for the next transmission as our model does. Moreover the models in [START_REF] Park | Throughput and energy consumption analysis of IEEE 802.15. 4 slotted CSMA/CA[END_REF], [START_REF] Pollin | Performance analysis of slotted carrier sense IEEE 802.15.4 medium access layer[END_REF], [START_REF] Park | A Generalized Markov Chain Model For Effective Analysis of Slotted IEEE 802[END_REF], [START_REF] Wen | An Improved Markov Model for IEEE 802.15.4 Slotted CSMA/CA Mechanism[END_REF] handle the case where the node buffers always have pending packets. Our model handles the more realistic situation where we have a given packet generation rate in a single buffer with loss and provides a much simpler normalization equation than [START_REF] Park | Throughput and energy consumption analysis of IEEE 802.15. 4 slotted CSMA/CA[END_REF], [START_REF] Pollin | Performance analysis of slotted carrier sense IEEE 802.15.4 medium access layer[END_REF], [START_REF] Park | A Generalized Markov Chain Model For Effective Analysis of Slotted IEEE 802[END_REF], [START_REF] Wen | An Improved Markov Model for IEEE 802.15.4 Slotted CSMA/CA Mechanism[END_REF].

This paper is organized as follows. In Section II we define the problem of slotted medium access to shared slots; the notation used throughout the paper is given. In Section III, we analyze the medium access protocol that always performs a backoff before each transmission. We propose a Markov model of node behavior taking into account the backoff stage and the maximum number of message transmissions. We evaluate the probabilities of success, collision and empty slots. This model is validated through simulations done with NS3. We then model the protocol that does not perform a backoff before the first transmission of each message and design its Markov model in Section IV, which is also validated by means of NS3 simulations. We compare the performance of each protocol in terms of successful message transmissions, rejected messages and node fairness in Section V. Finally, we conclude in Section VI.

II. PROBLEM STATEMENT

A. Assumptions

In this paper, we adopt the following assumptions:

• A 1 ) We consider a wireless slotted network: each transmission starts at the beginning of a slot. The slot size allows the transmission of one packet and its immediate acknowledgment when this packet is sent point-to-point. • A 2 ) All the slots are shared.

• A 3 ) Access to the shared slots is ruled by a backoff expressed in terms of the number of shared slots that the competing node must wait for before being allowed to transmit. • A 4 ) There is no channel sensing before transmitting.

• A 5 ) Each network node has N 1-hop neighboring nodes.

• A 6 ) Each node generates a message with a probability 1 -r. • A 7 ) Each node has a buffer of size one. If a message is generated, when the node's buffer is not empty, it is lost.

B. Notation

We now introduce some notations that will be used in this paper. These notations are summarized in Table I. Upper bound of backoff window

W j = 2 j at stage j M inB ≤ j ≤ M axB States Name Meaning Default value (i, j, k)
State of the node considered where i is the number of transmissions

1 ≤ i ≤ R j is the backoff stage M inB ≤ j ≤ M axB k is the number of slots to wait for 0 ≤ k ≤ W j -

C. Simulation

The NS3 simulation tool is used to evaluate the performance of different methods of collision avoidance on shared slots. It also validates the models proposed.

In these simulations, different probabilities are evaluated as follows. Each result is the average of 30 simulations. In each simulation, 10 000 slots are simulated. The parameters given in Table I are used: the maximum number of transmissions of a message is 4 and the backoff stage belongs to the interval [START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF][START_REF] Wen | An Improved Markov Model for IEEE 802.15.4 Slotted CSMA/CA Mechanism[END_REF] and W j = 2 j .

III. BACKOFF BEFORE EACH TRANSMISSION A. Principle of the method

Each node in the slotted wireless network behaves as follows.

• Before transmitting a message, a backoff is drawn in the backoff window. The backoff window is defined by the backoff stage. The backoff stage j starts with 1 and is incremented after each unsuccessful transmission (see the definition below) up to a maximum value M axB. The backoff window at stage j is equal to [0, W j -1]. The backoff drawn in this window represents the number of shared slots the node must wait for before being allowed to transmit its message. • When a message is sent, two cases are possible:

either an acknowledgment is received and the transmission is considered successful. The backoff stage is reset to the initial value M inB. The node serves the next message in its Transmit queue. no acknowledgment is received after a time-out and the transmission is considered unsuccessful. There are two possible cases: * the node has already transmitted this message R times, this message is rejected, a failure notification is reported to the upper layer. Notice that the backoff stage is incremented by one (up to the maximum value M axB). * otherwise, the node increments its backoff stage j by one (up to the maximum value M axB) and its number of transmissions for this message. It then draws a random backoff in [0, W j -1]. When the backoff has elapsed, it transmits its message.

• The message is removed from the buffer only after its acknowledgment has been received or the maximum number of retries has been reached.

B. Model based on a Markov chain

The state of a node having an empty buffer is denoted Idle. Any message generated while the node is not in the Idle state is lost. Except in the Idle state where the buffer of the node is empty, the state of the node is represented by a triplet (i, j, k) where i denotes the number of transmissions of the message considered, j denotes the backoff stage of the node and k is the backoff drawn by the node in the backoff window [0, W j -1]. We have the following inequalities:

• 1 ≤ i ≤ R,
where R denotes the maximum number of transmissions of a message. • M inB ≤ j ≤ M axB, where M inB and M axB are constant parameters fixed by the MAC protocol considered.

• i ≤ j • 0 ≤ k ≤ W j -1.
The behavior of such a node can be modeled by a Markov chain. This model, following in the footsteps of Bianchi [START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF] has many differences:

• There is no Clear Channel Access (CCA) before transmitting a message. • The backoff is decremented at each shared slot even if this slot is not empty.

• The backoff stage after R unsuccessful transmissions of a message is not reset to the initial value for the next message. As a consequence, the first transmission of a new message may correspond to three different states, which we explain for the case R = 4 and M axB = 7:

-(1, 1, 0), when the previous message transmission was successful. The backoff stage is equal to 1. -(1, 5, 0), when the previous message was rejected.

The backoff stage is equal to R + 1 = 5. -(1, 7, 0), when the two previous messages were rejected. The backoff stage is equal to its maximum value i.e. 7. • Medium saturation is not assumed. We suppose that the probability of packet generation is 1 -r at each slot. Let us focus on the Idle state, state of a node when it has no message to transmit. We distinguish three Idle states according to the result of the previous transmission. These states are denoted:

• Idle 1 , when the previous message transmission was successful. The backoff stage will be reset to 1 for the next transmission. • Idle 2 , when the previous message was rejected. The backoff stage will be incremented for the next transmission, it will be R + 1 = 5. • Idle 3 , when the two previous messages were rejected.

The backoff stage keeps its current maximum value of 7. The introduction of these states allows us to model the node behavior by a Markov chain, where the next state of the node depends only on the current state and the event occurring. The Markov chain of this contention avoidance method is depicted in Figure 1, where the three Idle states are depicted by a red rectangle, whereas the three states corresponding to the first transmission of a message are depicted by a blue double-lined rectangle.

To improve the readability of the notation we denote by: • a i the probability of being in state (i, i, 0)

for i = 1, 2, 3 or 4 = R, • b i the probability of being in state (i, min(4 + i, 7), 0) for i = 1, 2, 3 or 4 = R, • c i the probability of being in state (i, 7, 0) for i = 1, 2, 3 or 4 = R, with M axB = 7 < 2 * R, • I 1 the probability of being in state Idle 1 ,
• I 2 the probability of being in state Idle 2 , • I 3 the probability of being in state Idle 3 , • τ the probability that a node transmits in a random slot. We obtain the following system of equations:

                 I1 = (1 -p) * τ + r * I1 a1 = (1 -r) * I1 = (1 -p) * τ a2 = p * a1 = p * (1 -r) * I1 a3 = p * a2 = p 2 * a1 = p 2 * (1 -r) * I1 a4 = p * a3 = p 3 * a1 = p 3 * (1 -r) * I1                I2 = p * a4 + r * I2 b1 = (1 -r) * I2 = p * a4 = p 4 * a1 b2 = p * b1 = p 5 * a1 b3 = p * b2 = p 6 * a1 b4 = p * b3 = p 7 * a1
Fig. 1. The Markov chain of the collision avoidance method on shared slots with a backoff before each transmission.

                     I3 = p * (b4 + c4) + r * I3 c1 = (1 -r) * I3 = p * (b4 + c4) c2 = p * c1 c3 = p * c2 = p 2 * c1 c4 = p * c3 = p 3 * c1 c1 = p * b4 + p * c4
We get:

c1 = p * b4 + p 4 * c1 c1 * (1 -p 4 ) = p * b4 = p 8 * a1 c1 = p 8 * a 1 1-p 4
If we now focus on the different backoff states before the first transmission of a message generated while in state Idle 1 , we have:

       a 1,W 1 -1 = a1/W1 a 1,W 1 -2 = 2 * a1/W1 a1,0 = W1 * a1/W1
Summing member to member, we get:

             W 1 -1 k=0 a 1,k = a1 * (W1 + 1)/2 W 2 -1 k=0 a 2,k = a2 * (W2 + 1)/2 = p * a1 * (W2 + 1)/2 W 3 -1 k=0 a 3,k = a3 * (W3 + 1)/2 = p 2 * a1 * (W3 + 1)/2 W 4 -1 k=0 a 4,k = a4 * (W4 + 1)/2 = p 3 * a1 * (W4 + 1)/2
Similarly, we obtain: For simplicity reasons, we set A =

             W 5 -1 k=0 b 1,k = b1 * (W5 + 1)/2 = p 4 * a1 * (W5 + 1)/2 W 6 -1 k=0 b 2,k = b2 * (W6 + 1)/2 = p 5 * a1 * (W6 + 1)/2 W 7 -1 k=0 b 3,k = b3 * (W7 + 1)/2 = p 6 * a1 * (W7 + 1)/2 W 7 -1 k=0 b 4,k = b4 * (W7 + 1)/2 = p 7 * a1 * (W7 + 1)/2 and                  W 7 -1 k=0 c 1,k = c1 * (W7 +
4 i=1 Wi-1 k=0 a i,k , B = 4 i=1 W min(i+4,7) -1 k=0 b i,k and C = 4 i=1 W7-1 k=0 c i,k .
We have:

                     A = a1 * W 1 +1 2 + p * a1 * W 2 +1 2 + p 2 * a1 * W 3 +1 2 +p 3 * a1 * W 4 +1 2 B = p 4 * a1 * W 5 +1 2 + p 5 * a1 * W 6 +1 2 + p 6 * a1 * W 7 +1 2 +p 7 * a1 * W 7 +1 2 C = (1 + p + p 2 + p 3 ) * ( p 8 * a 1 1-p 4 ) * W 7 +1 2 = a1 * p 8 1-p * W 7 +1 2          A = a1 * ( W 1 +1 2 + p * W 2 +1 2 + p 2 * W 3 +1 2 + p 3 * W 4 +1 2 ) B = a1 * (p 4 * W 5 +1 2 + p 5 * W 6 +1 2 + p 6 * W 7 +1 2 + p 7 * W 7 +1 2 ) C = p 8 * a 1 1-p * W 7 +1 2
From the model depicted in Figure 1 and normalizing the sum of the probabilities, we get:

                   τ = a1 + a2 + a3 + a4 + b1 + b2 + b3 + b4 + c1 + c2 + c3 + c4 1 = A + B + C + I1 + I2 + I3 I1 = a 1 1-r I2 = p 4 * a 1 1-r I3 = p 8 * a 1 (1-r) * (1-p 4 )
By replacing the a i , b i and c i and I i by their value function of a 1 and replacing A + B + C by its value computed previously, we have:

               τ = a1 * (1 + p + p 2 + p 3 + p 4 + p 5 + p 6 + p 7 1-p ) 1 = a1 * ( W 1 +1 2 + p * W 2 +1 2 + p 2 * W 3 +1 2 + p 3 * W 4 +1 2 +p 4 * W 5 +1 2 + p 5 * W 6 +1 2 + p 6 * W 7 +1 2 + p 7 1-p * W 7 +1 2 + 1 1-r + p 4 1-r + p 8 (1-r) * (1-p 4 ) )              τ = a 1 1-p a1 = ( W 1 +1 2 + p * W 2 +1 2 + p 2 * W 3 +1 2 + p 3 * W 4 +1 2 +p 4 * W 5 +1 2 + p 5 * W 6 +1 2 + p 6 * W 7 +1 2 + p 7 1-p * W 7 +1 2 + 1 1-r + p 4 1-r + p 8 (1-r) * (1-p 4 ) ) -1
By replacing a 1 by its value as a function of p, we have:

τ = 1 1-p * ( W 1 +1 2 + p * W 2 +1 2 + p 2 * W 3 +1 2 + p 3 * W 4 +1 2 + p 4 * W 5 +1 2 +p 5 * W 6 +1 2 + p 6 * W 7 +1 2 + p 7 1-p * W 7 +1 2 + 1 1-r + p 4 1-r + p 8 (1-r) * (1-p 4 ) ) -1 (1)
We can compute p the probability of a collision knowing that one node already transmits. It is equal to 1 minus the probability that none of the N -1 other nodes transmits. Hence, we obtain:

p = 1 -(1 -τ ) N -1 (2)
Replacing p by its value as a function of τ in Equation 1 leads to f (τ ) = τ where the function f (.) is defined as follows:

f (τ ) = 1 (1-τ ) N -1 * ( W 1 +1 2 + W 2 +1 2 * (1 -(1 -τ ) N -1 ) + W 3 +1 2 * (1 -(1 -τ ) N -1 ) 2 + W 4 +1 2 * (1 -(1 -τ ) N -1 ) 3 + W 5 +1 2 * (1 -(1 -τ ) N -1 ) 4 + W 6 +1 2 * (1 -(1 -τ ) N -1 ) 5 + W 7 +1 2 * (1 -(1 -τ ) N -1 ) 6 + W 7 +1 2 * (1-(1-τ ) N -1 ) 7 (1-τ ) N -1 + 1 1-r + (1-(1-τ ) N -1 ) 4 1-r + (1-(1-τ ) N -1 ) 8 (1-r) * (1-(1-(1-τ ) N -1 ) 4 ) ) -1 (3)
We are looking for the value of τ ∈ [0, 1] giving f (τ ) = τ . In [0, 1], the function f (τ ) -τ is monotonic. Hence, Equation 3 has a unique solution.

After having computed the value of τ , the unique solution of Equation 3, we can compute the probabilities of success, collision and empty slots as follows.

                           a 1 = (1 -p) * τ I 1 = a 1 /(1 -r) = (1-p) * τ 1-r I 2 = p 4 * a1 1-r I 3 = p 8 * a1

IV. NO BACKOFF FOR THE FIRST TRANSMISSION

We now focus on the collision avoidance method used by TSCH on the shared slots. It differs from the method explained in Section III by the fact that no backoff is drawn before the first transmission of the message sent after the successful transmission of the previous message. It is also the case for the first transmission of the first message sent by the wireless node.

A. Model based on a Markov chain

The behavior of such a node can be modeled by a Markov chain. As stated above, the state of a node having an empty buffer is denoted Idle. Any message generated while the node is not in the Idle state is lost. Except in the Idle state where the buffer of the node is empty, the state of the node is represented by a triplet (i, j, k) where i denotes the number of transmissions of the message considered, j denotes the backoff stage of the node and k is the backoff drawn by the node in the backoff window [0, W j -1]. We have the following inequalities:

• 1 ≤ i ≤ R, where R denotes the maximum number of transmissions of a message. • M inB ≤ j ≤ M axB, where M inB and M axB are constant parameters fixed by the MAC protocol considered.

• 0 ≤ k ≤ W j -1.
As a consequence, the first transmission of a new message may correspond to three different states, which we explain for the case R = 4 and M axB = 7:

• (1, 0, 0), when the previous message transmission was successful. By convention, the backoff stage is set to 0. • (1, 4, 0), when the previous message was rejected. The backoff stage is equal to R = 4. • (1, 7, 0), when the two previous messages were rejected.

The backoff stage is equal to its maximum value, i.e. M axB = 7. The Markov chain of this contention avoidance method is depicted in Figure 3, where the three Idle states are depicted by a red rectangle, whereas the three states corresponding to the first transmission of a message are depicted by a blue double-lined rectangle.

To improve the readability of the notation we denote by:

• a i the probability of being in state (i, i -1, 0) for i = 1, 2, 3 or 4 = R, • b i the probability of being in state (i, 3 + i, 0) for i = 1, 2, 3 or 4 = R, • c i the probability of being in state (i, 7, 0) for i = 1, 1, 2, 3 or 4 = R, with M axBE = 7 < 2 * R. We have the following system of equations:

                 I1 = (1 -p) * τ + r * I1 a1 = (1 -r) * I1 = (1 -p) * τ a2 = p * a1 = p * (1 -r) * I1 a3 = p * a2 = p 2 * a1 = p 2 * (1 -r) * I1 a4 = p * a3 = p 3 * a1 = p 3 * (1 -r) * I1
Fig. 3. The Markov chain of the collision avoidance method on shared slots of TSCH.

              I2 = p * a4 + r * I2 b1 = (1 -r) * I2 = p * a4 = p 4 * a1 b2 = p * b1 = p 5 * a1 b3 = p * b2 = p 6 * a1 b4 = p * b3 = p 7 * a1                      I3 = p * (b4 + c4) + r * I3 c1 = (1 -r) * I3 = p * (b4 + c4) c2 = p * c1 c3 = p * c2 = p 2 * c1 c4 = p * c3 = p 3 * c1 c1 = p * b4 + p * c4
We get:

c1 = p 8 * a 1 1-p 4
If now we focus on the different backoff states after the failure of the first transmission of a message generated in state Idle 1 , we obtain:

     a 2,W 1 -1 = a2/W1 a 2,W 1 -2 = 2 * a2/W1 a2,0 = W1 * a2/W1
Summing member to member, we have:

         W 1 -1 k=0 a 2,k = a2 * (W1 + 1)/2 = p * a1 * (W1 + 1)/2 W 2 -1 k=0 a 3,k = a3 * (W2 + 1)/2 = p 2 * a1 * (W2 + 1)/2 W 3 -1 k=0 a 4,k = a4 * (W3 + 1)/2 = p 3 * a1 * (W3 + 1)/2
Similarly, we get:

             W 4 -1 k=0 b 1,k = b1 * (W4 + 1)/2 = p 4 * a1 * (W4 + 1)/2 W 5 -1 k=0 b 2,k = b2 * (W5 + 1)/2 = p 5 * a1 * (W5 + 1)/2 W 6 -1 k=0 b 3,k = b3 * (W6 + 1)/2 = p 6 * a1 * (W6 + 1)/2 W 7 -1 k=0 b 4,k = b4 * (W7 + 1)/2 = p 7 * a1 * (W7 + 1)/2 and                  W 7 -1 k=0 c 1,k = c1 * (W7 + 1)/2 = p 8 1-p 4 * a1 * (W7 + 1)/2 W 7 -1 k=0 c 2,k = c2 * (W7 + 1)/2 = p 9 1-p 4 * a1 * (W7 + 1)/2 W 7 -1 k=0 c 3,k = c3 * (W7 + 1)/2 = p 10 1-p 4 * a1 * (W7 + 1)/2 W 7 -1 k=0 c 4,k = c4 * (W7 + 1)/2 = p 11 1-p 4 * a1 * (W7 + 1)/2
For simplicity reasons, we set A = a 1,0 +

4 i=2 Wi-1-1 k=0 a i,k , B = 4 i=1 Wi+3-1 k=0 b i,k and C = 4 i=1 W7-1 k=0 c i,k .          A = a1 * (1 + p * W 1 +1 2 + p 2 * W 2 +1 2 + p 3 * W 3 +1 2 ) B = a1 * (p 4 * W 4 +1 2 + p 5 * W 5 +1 2 + p 6 * W 6 +1 2 + p 7 * W 7 +1 2 ) C = p 8 * a 1 1-p * W 7 +1 2
From the model depicted in Figure 3 and by similarity with the analysis given in Section III, we finally have:

               τ = a1 * (1 + p + p 2 + p 3 + p 4 + p 5 + p 6 + p 7 1-p ) 1 = a1 * (1 + p * W 1 +1 2 + p 2 * W 2 +1 2 + p 3 * W 3 +1 2 +p 4 * W 4 +1 2 + p 5 * W 5 +1 2 + p 6 * W 6 +1 2 + p 7 1-p * W 7 +1 2 + 1 1-r + p 4 1-r + p 8 (1-r) * (1-p 4 ) )              τ = a 1 1-p a1 = (1 + p * W 1 +1 2 + p 2 * W 2 +1 2 + p 3 * W 3 +1 2 +p 4 * W 4 +1 2 + p 5 * W 5 +1 2 + p 6 * W 6 +1 2 + p 7 1-p * W 7 +1 2 + 1 1-r + p 4 1-r + p 8 (1-r) * (1-p 4 ) ) -1
By replacing a 1 by its value function of p, we obtain:

τ = 1 1-p * (1 + p * W 1 +1 2 + p 2 * W 2 +1 2 + p 3 * W 3 +1 2 +p 4 * W 4 +1 2 + p 5 * W 5 +1 2 + p 6 * W 6 +1 2 + p 7 1-p * W 7 +1 2 + 1 1-r + p 4 1-r + p 8 (1-r) * (1-p 4 ) ) -1 (4)
As in Section III, p the probability of a collision knowing that one node transmits is given by Equation 2.

Replacing p by its value as a function of τ in Equation 4 leads to f (τ ) = τ where the function f (.) is defined as follows:

f (τ ) = 1 (1-τ ) N -1 * (1 + (1 -(1 -τ ) N -1 ) * W 1 +1 2 + (1 -(1 -τ ) N -1 ) 2 * W 2 +1 2 +(1 -(1 -τ ) N -1 ) 3 * W 3 +1 2 + (1 -(1 -τ ) N -1 ) 4 * W 4 +1 2 +(1 -(1 -τ ) N -1 ) 5 * W 5 +1 2 + (1 -(1 -τ ) N -1 ) 6 * W 6 +1 2 + (1-(1-τ ) N -1 ) 7 (1-τ ) N -1 * W 7 +1 2 + 1 1-r + (1-(1-τ ) N -1 ) 4 1-r + (1-(1-τ ) N -1 ) 8 (1-r) * (1-(1-(1-τ ) N -1 ) 4 ) ) -1 (5)
We are looking for the value of τ ∈ [0, 1] giving f (τ ) = τ . In [0, 1], the function f (τ ) -τ is monotonic. Hence, Equation 5has a unique solution.

After having computed the value of τ , the unique solution of Equation 5, we can compute the probabilities of success, collision and empty slots as in Section III.

B. Model validation by simulation

Assuming no backoff before the first transmission, Figure 4 compares the results obtained by simulations and the model for 4, 8, 16 or 32 nodes, when r = 1 -1/N . The values of P success, also called normalized throughput, and P empty are depicted. Since the value of P collide is deduced from the two previous, it is not depicted. Our model is validated by the very close results obtained.

V. COMPARATIVE PERFORMANCE EVALUATION

We now compare the two protocols analyzed in the two previous sections, for a number of neighboring nodes N ranging from 4 to 32. We distinguish two cases of channel load: moderate and heavy.

A. Moderate medium load

When the medium is moderately loaded, simulation results concerning the probability of success, collision and empty slots are very stable, the error bars of the simulation for a confidence interval of 95% are very small and not visible in the figures. Figure 5 shows that for a number of neighboring nodes in [START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF][START_REF] Wen | An Improved Markov Model for IEEE 802.15.4 Slotted CSMA/CA Mechanism[END_REF] the protocol used by TSCH provides a higher probability of success, hence a higher normalized throughput. This is no longer the case as soon as N ≥ 8. Similarly, simulation results show a higher number of collisions suffered by transmitting nodes for this protocol, whatever the number of nodes. This is due to the fact that the first transmission of each message very often leads to a collision. The probability of empty slots that measures the channel under-utilization is minimized by TSCH.

In this comparison, we have adopted r = 1 -1/N or in other words the packet generation rate is 1/N for each node and in each slot. Other figures for this generation rate are acceptable and lead to a model well in accordance with simulation results. However, if the total load becomes too high, significant unfairness appears in the throughput for the TSCH protocol, as we will see in the next subsection. When the unfairness becomes high, the model is no longer able to predict the simulation results accurately.

B. High medium load

When the load is high and especially in channel saturation, we are interested in the normalized throughput, the ratio of successfully transmitted messages over the total number of messages that are either successfully transmitted or rejected, as well as node fairness. Node fairness is evaluated by the Jain fairness index defined on the transmission opportunities given to a node. We have J(T x) =

( n i=1 T xi) 2 n n i=1 T x 2 i
, where T x i denotes the number of transmission attempts of node i.

Figure 6 and Figure 7 allow us to compare the performance of the two collision avoidance protocols studied in this paper with the 1/N Aloha protocol where each node transmits in each slot with a probability equal to 1/N , where N is equal to 8 and 16, respectively. In both cases, the 1/N Aloha protocol provides the best node fairness (higher than 0.998) and the best ratio of successfully transmitted message (higher than 0.8525). This is explained by the fact that each node receives a fair share (i.e. 1/N ) of the bandwidth. The protocol used by TSCH provides the highest normalized throughput (higher than 0.4265), the smallest ratio of empty slots (less than 0.1279), but the worst fairness (less than 0.972). This is because the node that succeeds in transmitting its message, immediately transmits its next message, whereas other nodes are waiting for the end of their backoff. The protocol based on a backoff before each transmission provides a normalized throughput smaller than TSCH (0.4332 and 0.3807 for 8 and 16 nodes, respectively) but higher than the 1/N Aloha protocol (0,3927 and 0.3806 for 8 and 16 nodes, respectively). It also ensures a better fairness than TSCH (higher than 0.986).

VI. CONCLUSION

In this paper, we have analyzed two medium access protocols operating in a wireless slotted network. Their performances have been evaluated by means of two new Markov models that take into account the unsuccessful transmission of the previous message. Extensive simulations show a very good match between the model and the simulation results. For moderate medium load, the protocol performing a backoff before each transmission outperforms the TSCH protocol, when the number of neighboring nodes is greater than or equal to 8. For a smaller number of neighboring nodes, the TSCH protocol provides a higher throughput. For high medium load, the TSCH protocol provides the highest normalized throughput at the cost of some unfairness in the transmission opportunities.

S

  = T otal number of slots. τ = T otal number of transmissions /S. P success = N umber of slots with successf ul receptions /S. P empty = N umber of empty slots /S. P collide = N umber of slots with 2 or more transmitters /S.

4 *

 4 a1 * (W7 + 1)/2

PFig. 2 .

 2 Fig. 2. Model validation.

Fig. 4 .

 4 Fig. 4. Model validation.

Fig. 5 .

 5 Fig. 5. Normalized throughput and probability of empty slots.

Fig. 6 .

 6 Fig. 6. Comparative performance evaluation for 8 nodes.

Fig. 7 .

 7 Fig. 7. Comparative performance evaluation for 16 nodes.

ACKNOWLEDGMENT Study co-funded by CNES and Inria in the framework of the CNES Launchers Research and Technology program.


Ines Khoufi

Pascale Minet

Badr Rmili
email: badr.rmili@cnes.fr

Scheduling transmissions with latency constraints in an IEEE 802.15.4e TSCH network

Abstract-Time Slotted Channel Hopping (TSCH), specified in the IEEE 802.15.4e amendment, has been designed for industrial automation, process control and equipment monitoring. It uses a slotted medium access on several channels in parallel and supports multihop communications. In this paper, we study how applications with data delivery constraints can be supported by a TSCH network. We first propose a framework based on a multislotframe that allows the coexistence of Data Slotframes and Control Slotframes. We then determine a lower bound on the minimum number of slots required to perform data gathering, taking into account the number of channels, the number of interfaces of the sink, the number of packets generated by each sensor node as well as the number of children of the sink. These feasibility conditions are established for two cases: with spatial reuse and without. We propose a debt-based scheduler that for simple topologies, provides a schedule minimizing the slotframe size. Finally, we consider a network configuration representative of an industrial application and evaluate the performance of the TSCH network in terms of data delivery delay and queue size for each sensor node, using the NS-3 simulator. Simulation results confirm the theory.

I. CONTEXT AND MOTIVATION

Most wireless sensor networks (WSNs) deployed up to now use a technology based on the IEEE 802.15.4 standard. This standard has been recently amended with the IEEE 802. [START_REF]A Step Towards the Internet of Things[END_REF].4e amendment to meet the requirements of industrial applications with regard to latency, robustness and energy. Among the five modes proposed, the TSCH (Time Slotted Channel Hopping) mode has been designed for industrial automation, process control and equipment monitoring. The TSCH network should ensure that the time needed to gather all the data generated by sensor nodes is less than a given threshold, usually called delivery latency. The TSCH network should be able to tolerate some channel perturbations. These perturbations can be caused either on the one hand by devices belonging to the same network or another network coexisting in the same geographical area, or on the other hand by an external source (e.g. a radar). In addition, since some sensor nodes are battery-equipped, their lifetime should be maximized. Huge energy savings can be achieved by making sensor nodes sleep. However, this should not degrade the performances of data gathering. The TSCH solution is based on a multichannel time-slotted medium access using channel hopping. It supports star, tree and mesh topologies. These features make it a very promising candidate for industrial applications. That is why TSCH is the focus of this paper.

Most of the studies on IEEE 802. [START_REF]A Step Towards the Internet of Things[END_REF].4e TSCH networks focus on communications in an operational network. Some evaluate the average throughput, the average delays and the average energy consumption either by means of simulations like [START_REF] Guglielmo | Advances onto the Internet of Things[END_REF], or analytical models like Markov models in [START_REF] Chen | Performance Analysis of IEEE 802.15.4e Time Slotted Channel Hopping for Low-Rate Wireless Networks[END_REF], or estimators validated on real implementations like [START_REF] Watteyne | Industrial IEEE802.15.4e Networks: performance and trade-offs[END_REF] and [4]. Others compute upper bounds on the delays for star topologies, using Network Calculus like [START_REF] Kurunathan | Towards Worst-Case Bounds Analysis of the IEEE 802.15.4e[END_REF]. The gains brought by TSCH networks with regard to IEEE 802.15.4 networks are highlighted in [START_REF] Guglielmo | Advances onto the Internet of Things[END_REF], where the NS2 simulator is used to compare the performances of both networks for a star topology with a number of nodes ranging from 20 to 120 in terms of delivery ratio, energy consumed and delivery delays. TSCH outperforms classical 802.15.4 both in beacon-enabled and non-beacon-enabled modes. In [START_REF] Chen | Performance Analysis of IEEE 802.15.4e Time Slotted Channel Hopping for Low-Rate Wireless Networks[END_REF], the authors model the transmission delays obtained with the shared slots of TSCH, for which collisions may occur and compare the performance with CSMA/CA, pointing out the differences in collision avoidance used by TSCH and CSMA/CA.

The contribution of this paper is twice. First we determine theoretical bounds on the minimum number of slots needed by data gathering and on the maximum delivery time, taking into account network parameters. Second, we focus on an industrial application with strong latency constraints and evaluate the TSCH performances in various configurations with the NS3 simulator. This paper is organized as follows: Section II presents the theoretical framework of this study and defines the problem. In Section III, the feasibility conditions are given for a valid schedule to meet the latency constraint, taking into account the topology, the sampling rate of each sensor node, the data gathering tree, the number of interfaces of each wireless node (sensor node or sink), the number of channels simultaneously used by the WSN. Section IV proposes a debt-based scheduler to build a valid schedule meeting the latency constraint, if the problem is feasible. Section V reports the simulation results obtained with the NS3 simulation tool for various configurations (random topologies, heterogeneous sampling rates, number of interfaces of the sink). Simulation results confirm that the schedule provides the minimum number of slots required by the configurations studied.

II. THEORETICAL FRAMEWORK

TSCH uses time-synchronized communications (time slots) and different channels in parallel (with frequency hopping) to improve network robustness by a spectral and time redundancy. The minimization of collisions increases the through-put. Channel hopping limits the effects of multipath and interferences. TSCH can be used with any network topology.

There exists 16 frequencies available in the 2.4 GHz frequency band according to the IEEE 802.15.4 [START_REF]IEEE Standard for Local and metropolitan area networks-Part 15.4: Low-Rate Wireless Personal Area Networks (LR-WPANs)[END_REF] standard that rules the physical layer (PHY) of any TSCH network. In this study, a constraint of having at most three TSCH networks present in the same area is considered. Thus, to avoid internetworks interferences, the number of frequencies available per network is N Channel ≤ 5. Concerning the constraint on the distance between the frequencies used by a multi-interface node, usually the sink, it is preferable to use frequencies that are not direct neighbors. For instance, the set of frequencies used by a network could be a subset of 5 frequencies such as {11, 15, 19, 23, 26}.

A. MultiSlotframe

The solution that we propose to meet the latency and robustness constraints is based on the concept of MultiSlotframe. A MultiSlotframe is an ordered sequence of Slotframes that is periodically repeated. Figure 1 depicts an example of a simple MultiSlotframe.

Fig. 1: An example of a MultiSlotframe.

All the Slotframes of a same MultiSlotframe have the same size expressed as a number of slots, but they differ by their type. We define three different types of Slotframe:

• Beacon: this type is used for the downstream cascading transmission (i.e. from the sink to the sensor nodes) of control frames, the Enhanced Beacons. By means of Information Elements (IE) contained in the Beacon specified by the IEEE 802.15.4e standard [START_REF]IEEE Standard for Local and metropolitan area networks-Part 15[END_REF] or created to meet our needs, this control traffic performs neighborhood discovery, selection of potential parents (routing in the data gathering tree) and the installation of schedules used for data gathering. A multihop cascading according to the address of each node allows each node to receive the information broadcast by the sink (i.e. the CPAN). • Shared: this type is used for the transmission of downstream / upstream control traffic during the association of nodes (insertion of a node in the network) and the notifications (e.g. application or topology change detected by a node). Collisions are possible. • Data: this type allows the transmission of useful data frames, in TDMA mode, without collisions. The positioning of these different types of Slotframes has a very strong impact on the latency that is met by data gathering on the one hand, and on the buffer size on sensor nodes on the other hand. To avoid that data accumulate on the nodes while waiting for their transmission, it is highly recommended that the Data Slotframes are fairly distributed in the Multislotframe to minimize the value of Reprod that denotes the maximum number of consecutive Slotframes to consider in the MultiSlotframe to get one Data Slotframe. In the example depicted in Figure 1, the Data Slotframe is repeated at least every 2 Slotframes. Hence Reprod = 2 in this example. Notice that if all Slotframes are Data Slotframes, Reprod = 1.

B. Slotframe

The following property ensures that the transmission of a node N 1 to a neighboring node N 2 , scheduled in the SlotOffset j and done on the channel ch 1 in the Slotframe i will be done in a channel ch 2 ̸ = ch 1 in the Slotframe i + 1. This rule guarantees that all channels of the TSCH network are visited by the transmissions of N 1 to N 2 scheduled in SlotOffset j in the successive Slotframes.

Property 1: For robustness reasons, the size of the Slotframe, expressed as a number of slots, and the number of channels used by the network should be co-prime.

If this property is not met, any transmission scheduled in a given SlotOffset will only visit a subset of the channels granted to the TSCH network, which does not allow the TSCH network to take full advantage of frequency diversity. The size of the Slotframe is selected to meet this property. Its value is advertised in the Enhanced Beacons.

The MAC layer is in charge of managing multichannel medium accesses according to the Slotframe. Two types of slots are distinguished. Shared slots provide a medium access in CSMA/CA mode, with possible collision. Dedicated slots provide a medium access in TDMA mode, without collision.

A Data Slotframe has all its slots of type dedicated: only the transmitter is in Transmit state and only the receiver(s) specified are in the Receive state. A Shared Slotframe has all its slots of type shared: any node may transmit. A Beacon Slotframe has all its slots of type dedicated: in each slot, only one node is allowed to transmit (all nodes transmit in sequence, the sequence is determined by the nodes adresses). In each slot of a Beacon Slotframe, all nodes are in Receive state. The assignment of slots and channels is performed by the sink (i.e. the CPAN) which is in charge of computing the schedule.

C. Notation

In the following, we adopt the notations given in Table I for the TSCH network considered.

D. Dimensioning of the Slotframe and the MultiSlotframe

The size of the Slotframe and the MultiSlotframe must meet some constraints. These constraints are related to data

BI = N Slotf rame × Slotf rameSize × SlotDuration (2)
For a MultiSlotframe with 15 Slotframes of 13 slots each, we get BI = 1.95s.

E. Problem statement

In the absence of link and node failure, the strongest constraint that must be met by data gathering concerns the maximum end-to-end delivery time, that should be less than or equal to a given Latency. To meet this constraint, data gathering must be scheduled in a smart way.

The scheduling problem consists in minimizing the number of slots required to gather data from sensor nodes in a TSCH network, under the following constraints:

• A0. The maximum end-to-end delivery time should be less than or equal to a given Latency. • A1. Packets are timestamped when generated at the Network layer. • A2. Each node transmits the packet with the smallest timestamp in its Transmit queue. This packet may be either a packet generated locally, or a packet received that has to be forwarded.

III. FEASIBILITY CONDITIONS

A. Sampling rate and Packetization

The first question that has to be answered when computing delivery delays of packets containing samples is how these packets are generated. Each packet is timestamped when it is generated at the network layer. The application determines the sampling period and the generation time of the first packet.

For the Packet Header at the Application level, we propose a format on 13 bytes: 8 bytes for the long address of the sensor node, 1 byte for the number of samples included in the packet, and 4 bytes for the packet timestamp. The useful size of a packet at the Application level is determined in Table II:

B. Slots needed by a raw data convergecast

With these notations, we can prove the following properties. Property 2: In a raw data convergecast we have:

N umber of packets received by the sink = ∑ i∈W SN Gen(i).

(3) T otal number of transmissions = ∑ i∈W SN

Gen(i) * Depth(i).

(4) P roof : By definition of raw data gathering, the sink must receive all the packets generated by each sensor node; hence, Equation 3. A packet generated by a node i at depth Depth(i) in the data gathering tree is transmitted Depth(i) times to reach the sink. Hence, the total number of transmissions is given by Equation 4. Equation 4 highlights the impact of the data gathering tree on the number of transmissions that must be scheduled to perform data gathering.

Property 3: When all nodes in the wireless sensor network are in range of each other, the data gathering tree minimizing the latency is given by a binomial tree. P roof : See [START_REF] Mengfan Shan | On minimizing data aggregation delay in low duty cycle sensor networks[END_REF]. This property has a limited interest since it considers a very specific topology where all nodes are in range of each other.

The problem being NP-hard, the extension to a multihop network is complex.

The number of slots needed strongly depends on the data gathering tree and on the traffic demand.

Property 4: In a raw data convergecast, the minimum number of slots assigned to sensor nodes is lower bounded by max(S n , S t ), with:

S n = ⌈ ∑ i∈W SN Gen(i)/g⌉ + δ n ( 5
)
S t = Gen(c 1 ) + 2 ∑ v∈subtree(c 1 ) v̸ =c 1 Gen(v) + δ t ( 6
)
with g = min(N Interf, N Child, N Channel), where N Interf denotes the number of radio interfaces of the sink, N Child the number of children of the sink, N Channel > 1 the number of available channels for the convergecast.

δ n = 1 if ∑ i∈W SN Gen(i)
is a multiple of g and Depth > 1 and N channel ≤ min(N child, N interf ), δ n = 0 otherwise. δ t = 1 if the (g + 1) th child requests the same number of slots as the first one, denoted c 1 , the children of the sink being sorted by decreasing order of slot demands, subtree(c 1 ) is the subtree rooted at c 1 , δ t = 0 otherwise. P roof : The value of S n expresses the fact that the sink must be able to receive all the packets generated by the sensor nodes that is ∑ i Gen(i). Since the sink is able to receive at most M in(N Channel, N Interf, N Child) packets simultaneously, we get the value of S n . The term δ n is introduced for topologies with a depth strictly higher than 1, when the number of messages received by the sink is a multiple of g. In this case, no node at depth 2 can transmit simultaneously with a child of the sink without causing a collision; an additional slot is needed for that purpose, hence the term δ n . The value of S t expresses the fact that the slot demand of the most demanding child of the sink must be met. Let c 1 denote this child of the sink: it requires Gen(c 1 ) slots to transmit the packets locally generated, plus ∑ v∈subtree(c 1 ) v̸ =c 1

Gen(v) slots to receive the packets generated by its descendants, plus the same amount of slots to forward these packets. The term δ t is introduced for topologies where the (g + 1) th child of the sink requests the same number of slots as the first one, assuming that the children of the sink are ordered by decreasing slot demand. In this case, the first slot granted to the (g + 1) th child is one slot later than the first child. Since these two children have the same slot demand, the last slot granted to the (g + 1) th child is one slot later than the last slot of c 1 . Property 4 is very important for the following reasons: It supports sensor nodes with heterogeneous sampling rates.It adapts to various numbers of available channels for the network. It takes into account the number of interfaces of the sink. It applies to any topology. However, we can notice that the lower bound on the minimum number of slots is reached when there is no topology link that exists in addition to those of the data gathering tree. From Property 4 we can also deduce that:

• It is useless to equip the sink with a number of radio interfaces strictly higher than the number of available channels or the number of the sink's children. • It is important to build a routing tree where no subtree rooted at a sink's child has a slot request considerably higher than the average. Indeed, a data gathering tree where all subtrees are balanced in terms of slot requests would require fewer slots to ensure data gathering. Property 5: In a raw data convergecast, the maximum packet delivery time, denoted M axDelivery is given by Equation 7M axDelivery ≤ (Reprod+1)×Slotf rameSize×SlotDuration.

(7) P roof : Let us consider a Multislotframe, where each Data Slotframe reproduces every Reprod Slotframes. Let us consider any sensor node i and any packet p generated by this node. The worst delivery time is obtained for p when it is generated just after the last slot granted to i has just started. Packet p cannot be transmitted in this Data Slotframe. It has to wait the next Data Slotframe that occurs Reprod Slotframes later. Since according to Assumption A7, any packet transmitted in a given Data Slotframe is delivered to the sink in the same Slotframe, p experienced at most one additional Slotframe to be delivered to the sink. Hence, the maximum delivery time of packet p is equal to (Reprod+1)×Slotf rameSize×SlotDuration.

Notice that Equation 7 justifies the choice of a schedule minimizing the total number of slots.

Corollary 1: The Slotframe size should meet:

Slotf rameSize ≤ L (Reprod + 1) × SlotDuration ( 8
)
Assuming Reprod = 2 and SlotDuration = 10ms, which are the default values, Equation 8gives for L = 1200ms, Slotf rameSize ≤ 40 slots.

C. Feasibility conditions with and without spatial reuse

Without spatial reuse, each cell defined by the couple (slotOf f set, channelOf f set) represents an opportunity to transmit for a single node. As a consequence, the number of cells is equal to the number of transmissions. We have the following property:

Property 6: Without spatial reuse, the SlotframeSize should meet the following condition, in addition to the conditions expressed in Property 4, [START_REF]NS3[END_REF] with δ noreuse = 1 if ∑ i Gen(i) * Depth(i) is multiple of N Channel and min(N child, N Interf ) < N Channel, δ noreuse = 0 otherwise. P roof : Without spatial reuse, the SlotframeSize should contain a number of cells at least equal to the total number of transmissions. The term δ noreuse has been introduced to deal with topologies where the total number of transmissions is a multiple of N Channel and min(N child, N Interf ) < N Channel. In such a case, we observe that in the last slot all transmissions are mandatorily transmissions from the children of the sink toward the sink. At most min(N child, N Interf ) < N channel transmissions are possible in the same slot. Hence a contradiction with the fact that all channels are used in this slot since the total number of transmissions is a multiple of N Channel. Hence, an additional slot is needed.

Slotf rameSize ≥ ⌈ ∑ i Gen(i) * Depth(i) N Channel ⌉ + δ noreuse
With spatial reuse, several transmissions can share the same cell without interfering. All the difficulty lies in determining whether two nodes conflict or not. This requires a perfect knowledge of the 1-hop and 2-hop neighborhoods as well a partial knowledge of the 3-hop neighborhood. This requires messages exchanges that we wish to avoid. In addition a schedule without spatial reuse is more robust than a schedule with spatial reuse: it remains valid even if new wireless links appear. However, spatial reuse may be required to meet the latency constraint given by the application.

We are now able to determine the size of the Slotframe taking into account various constraints: latency constraint with Property 5, robustness constraint with Property 1, raw data convergecast with Property 4, no spatial reuse with Property 6.

The feasibility conditions without spatial reuse become:

Slotf rameSize ≥ max ( ∑ i Gen(i) M in(N Channel, N Interf, N Child) + δn, Gen(c1) + 2 ∑ v∈subtree(c 1 ) v̸ =c 1 Gen(v) + δt, ⌈ ∑ i Gen(i) * Depth(i) N Channel ⌉ + δnoreuse )
Slotf rameSize ≤ L (Reprod + 1) × SlotDuration Slotf rameSize and N Channelshould be coprime.

These feasibility conditions are necessary conditions. They give the minimum number of slots needed by data gathering able to meet the latency constraint when the problem is feasible without spatial reuse. The next step will be to compute a valid schedule that meets this minimum number of slots.

IV. A DEBT-BASED SCHEDULE

A. Characterization of the schedule

To characterize the schedule we want to compute, we use the following concepts.

Definition 1: A valid schedule is a schedule where in any timeslot of the schedule:

• the number of interfaces used by each wireless node, taking into account all the channelOffsets used, is less than or equal to the number of interfaces of this node; • at most, N Channels are used; • a transmission is scheduled if and only if the transmitter has at least one packet to transmit, and it has at least one interface available as well as its parent.

Definition 2: A schedule is said to be collision-free if and only if no two conflicting nodes are assigned the same timeslot and the same channel.

Definition 3: A schedule is said to be traffic-aware if and only if each sensor node is assigned a number of slots that enables it to transmit all its messages in the same Slotframe.

Definition 4: A traffic-aware collision-free schedule is said to minimize data gathering delays if and only if the total number of slots needed to allow each sensor node to transmit all its messages in the same Slotframe and deliver them to the sink in the same Slotframe, is minimized.

We want to compute a valid schedule that is collisionfree, traffic-aware and minimizes the data gathering delays. Among all the possible schedulers, we select the debtbased schedulers as developed in the next section.

B. A simple Debt-based scheduler

Definition 5: A scheduler is said to be debt-based if and only if it schedules first the node having the highest debt.

In our context, we propose to define the debt of a node i as follows: Debt(i) = RemainT rans(i) × Depth(i) if node i has at least one packet in its Transmit queue, and 0 otherwise. Depth(i) is the distance of i to the sink expressed in the number of hops, and RemainT rans(i) is the number of packets remaining to be scheduled, even if only one of them is present in the Transmit queue.

The debt of a node i is updated when:

• a packet of node i is transmitted by i;

• a packet of a child of i is received by i;

• a new packet is generated on node i.

We focus on a simple debt-based scheduler that schedules at most one transmission per cell. Each cell is defined by its couple (slotOf f set, channelOf f set). In other words, this scheduler makes no spatial reuse of the timeslots. This scheduler orders the nodes by decreasing debt. It selects the node with the highest debt and inserts a transmission of this node to its parent in the current timeslot and current channeloffset if and only if this node and its parent have an available interface in this slot. Otherwise, the node with the second highest debt is tried, and so on. The scheduler then moves to the next channelOffset. If all channel offsets have been visited, it moves to the next timeslot, until all the packets generated by the sensor nodes have been received by the sink. This debt-based scheduler is used to compute the schedules without spatial reuse for all the scenarii studied in Section V.

V. PERFORMANCE EVALUATION

Our goal is to evaluate the performance of different scenarii running on a random network topology. The performance evaluation is conducted using the NS3 simulator [START_REF]NS3[END_REF], that we extend to integrate the functionalities needed to support our framework including the multi-interface management.

A. The application considered

We focus on a network consisting of 20 sensor nodes plus the sink denoted as node 0. The topology of this network is randomly selected. The routing tree associated with this topology is depicted in Figure 2. It has a depth of three. Four sensor nodes are one-hop away from the sink. These nodes have ten children that have six children as depicted in Figure 2. Such a configuration is representative of the industrial application considered. The sampling rate of each sensor node is given in Table III.

B. Feasibility conditions for this configuration

For this configuration where the sink has 4 children, the feasibility conditions established in Section III-C are given in Table IV. They show the impact of the numbers of interfaces and channels on the number of slots needed by data gathering for the topology considered. For the feasibility conditions with spatial reuse, we assume that the only topology links are those of the data gathering tree. With and without spatial reuse, we observe that an increase in the number of interfaces of the sink strictly higher than the number of sink's children brings no benefit. Similarly, a number of interfaces higher than the number of channels has no interest. An increase in the number of channels or interfaces that increases the value of min(N channel, N child, N interf ) tends to reduce the number of slots needed or keeps the same value in the worst case. This is explained by Property 4. For 4 channels, the number of slots obtained in Table IV does not take into account the constraint expressing that Slotf rameSize and N channel should be coprime to avoid that the same transmission is done on the same physical channel in two consecutive Data Slotframes. If this constraint is taken into account, the minimum number of slots would be without reuse, 21 slots for 2 and 3 interfaces, and 15 slots for 4 interfaces; whereas with reuse it would be 21 slots for 2 interfaces, and 15 slots for 3 and 4 interfaces.

As a consequence, selecting an even number of channels for a TSCH network is interesting only if the perturbations of channels are very short (i.e. less than Reprod×Slotf rameSize× SlotDuration). Otherwise, an even number of channels may lead to a larger Slotf rameSize that is not compatible with the short latency required by the application, as illustrated by this example, where we obtain 21 slots for 4 channels instead of 16 slots for 3 channels. No valid schedule may need a smaller number of slots than this given in Table IV for the configuration considered.

C. Simulation results

We now consider different scenarii, corresponding to different numbers of channels and sink's interfaces. For each scenario, we trigger 30 simulation runs. Each simulation run differs by the random generation times of the first packet on the sensor nodes. Simulation parameters are given in Table V. We evaluate the average and maximum delivery times of packets generated by each sensor node. The packet delivery time is equal to the time where the packet is inserted in the Receive queue at the Network layer of the sink minus the generation time of the packet at the Network layer of the sensor node. It is interesting to compare the maximum delivery time obtained in the simulations with the theoretical one. We also evaluate the average and maximum sizes of the Transmit queue on each sensor node. This size is expressed in terms of the number of packets in this queue. We study the impact of the numbers of channels and sink's interfaces on the packet delivery times and the Transmit queue size.

We first assume that we have 4 channels and the sink has 2 or 3 interfaces. Figure 3 depicts the average and maximum delivery times of packets generated by each sensor node. Nodes 1 and 2 have 4 packets to transmit in each Slotframe. We can see that these nodes have the smallest packet delivery delay. Nodes 3, 4, 5, 6, 9, 15 and 19 have 3 packets to transmit in each Slotframe. These nodes have a packet delivery delay less than the remaining nodes that have only 1 packet to transmit per Slotframe. This is due to the debt-based schedule that favors nodes with a high debt. Figure 4 depicts the average and maximum delivery times of packets when the number of channels is 5 and the number of sink's interfaces varies from 2 to 4. Compared with Figure 3, the maximum delivery time is smaller when the number of channels increases. When the sink has 2 interfaces, the maximum delivery time reaches 0.48s for 4 channels whereas it decreases to 0.37s with 5 channels. And when the number of sink's interfaces is 3, the maximum delivery time is equal to 0.48s with 4 channels and 0.34s with 5 channels. This decrease in the delivery delay is expected due to Property 4. Figure 5 depicts the average and maximum sizes of the Transmit queue in each sensor node when the number of channels used is equal to 5 and the sink's interfaces varies from 2 to 4. We observe that parent nodes have longer queues than non-parent nodes. This is explained by the fact that they have to forward the packets received from their children. In any case, the maximum size of the queue is 4.

VI. CONCLUSION

TSCH with its time-slotted and multichannel medium access provides an efficient support for data gathering. In this paper, we showed how applications with latency constraints can be supported by a TSCH network. We established the feasibility conditions for various configurations taking into account heterogeneous packet generation rates, various numbers of channels and sink's interfaces. We determined the conditions for which an increase in the number of channels or sink's interfaces leads to a shorter data delivery delay. We compared the number of slots needed by data gathering with and without spatial reuse for small configurations. We integrated the proposed framework in the NS3 simulator and evaluated the performance in a random topology for different configurations representative of an industrial application. Simulation results showed that the maximum theoretical delivery delay is never exceeded and the number of messages in the Transmit queue of each sensor node remains small. In addition, the debt-based scheduler builds a valid schedule with the minimum number of slots for the industrial application considered.

Fig. 2 :

 2 Fig. 2: An example of a 3-hop random network topology.

Fig. 3 :

 3 Fig.3: Average and max. packet delivery times for 4 channels.Figure4depicts the average and maximum delivery times of packets when the number of channels is 5 and the number of sink's interfaces varies from 2 to 4. Compared with Figure3, the maximum delivery time is smaller when the number of channels increases. When the sink has 2 interfaces, the maximum delivery time reaches 0.48s for 4 channels whereas it decreases to 0.37s with 5 channels. And when the number of sink's interfaces is 3, the maximum delivery time is equal to 0.48s with 4 channels and 0.34s with 5 channels. This decrease in the delivery delay is expected due to Property 4.

Fig. 4 :

 4 Fig.4: Average and max. packet delivery times for 5 channels.

Fig. 5 :

 5 Fig. 5: Size of the Transmit queue for 5 channels.

TABLE I :

 I Notations.

	L	maximum end-to-end delivery time acceptable by the
		application
	N Channel	number of channels in the frequency hopping se-
		quence, N Channel > 1
	N Interf	number of interfaces of the sink
	N Child	number of children of the sink
	N node	number of nodes in the TSCH network
	Gen(i)	number of packets locally generated by node i
	Reprod	the Data Slotframe is repeated every Reprod Slot-
		frames, Reprod = 2 by default
	Slotf rameSize	number of slots in the Slotframe
	BI	Beacon Interval, period between two successive ad-
		vertisements by the same node
	N Slotf rame	number of slotframes in the MultiSlotframe
	SlotDuration	duration of the timeslot = 10ms by default
	gathering, beacon advertisement as well as control messages.
	Concerning the Beacon Slotframe, we have:

• Each node must be able to transmit its beacon once per MultiSlotframe. Hence the Slotframe size should meet:

N node ≤ Slotf rameSize×N BeaconSlotf rame (1)

For a WSN with 20 sensor nodes and a sink, with 2 Beacon Slotframes per MultiSlotframe, we get Slotf rameSize ≥ 11. • For robustness reason, Slotf rameSize × N Slotf rame and N Channel should be coprime. • The periodicity of beacon also called Beacon Interval, denoted BI, is given by

  A6. The Data Slotframe is repeated every Reprod Slotframes.• A7. Any data packet present at the beginning of the Data Slotframe is transmitted in this Slotframe and delivered to the sink in the same Slotframe.

• A3. No link/node failures are assumed in this paper. • A4. There is no aggregation done by intermediate nodes. Such data gathering is also called raw data convergecast. • A5. Packets are only transmitted in Data Slotframes. Each packet is transmitted in a single time slot and acknowledged in the same time slot (i.e. immediate acknowledgment). •

TABLE II :

 II Useful size of a packet at the Application level.

	Maximum size of a MAC frame	127 bytes
	MAC Header + Trailer	11 bytes
	Network Encapsulation	4 bytes
	Packet Timestamp	4 bytes
	Sample size	2 bytes
	Application Packet Header	13 bytes
	Useful size for Data	99 bytes

TABLE III :

 III Sampling rate of each sensor node.

	Sampling rate per second	Sensor nodes
	400	1 2
	300	3 4 5 6 9 15 19
	100	7 8 10 11 12 13 14 16 17 18 20

TABLE IV :

 IV Minimum number of slots needed for various numbers of channels and interfaces.

	#	3 channels	4 channels	5 channels
	Int.	No reuse	Reuse	No reuse	Reuse	No reuse	Reuse
	1	Unfeas.	Unfeas.	Unfeas.	Unfeas.	Unfeas.	Unfeas.
	2	Unfeas.	16 slots	16 slots	16 slots	16 slots	16 slots
	3	Unfeas.	14 slots	16 slots	14 slots	14 slots	14 slots
	4	Unfeas.	14 slots	15 slots	14 slots	14 slots	14 slots

TABLE V :

 V Simulation parameters.

	Parameter	Value
	N Channel	4, 5
	N Interf	4, 3, 2 or 1
	N Child	4
	Latency	1200 ms
	SlotDuration	10 ms
	SlotF rameSize	variable
	Reprod	2
	Simulation duration	300 s
	Number of simulations	30