Raphaël Naves

Gentian Jakllari

Hicham Khalifé

Vania Conan

André-Luc Beylot

COLiDeR: A Cross-Layer Protocol for Two-Path Relaying

In this work, we present COLiDeR , the first PHY/MAC cross-layer protocol for practical twopath relaying using off-the-shelf half-duplex radios. It relies on three main contributions. First, based on an off-line performance comparison, COLiDeR selects the best interference management technique for a radio to handle two overlapping signals depending on the measured channel conditions. Then, considering the real decoding capacities of the nodes, COLiDeR introduces a dynamic relaying strategy with the objective of achieving high throughput while reducing decoding failures.

This includes a light-weight protocol for the source to evaluate the channel state, a state-machine modeled approach driven by the source for switching between the defined scheduling schemes and an optional power adaptation mechanism for reducing the packet losses. Finally, COLiDeR comes with an adapted scheduling mechanism that aims to integrate two path-relaying in multi-hop wireless networks. Experiments on a 4-USRP testbed show that COLiDeR delivers between 80-95% of the relaying performance of an ideal full-duplex radio while incurring negligible decoding failures.

Just as important, large-scale simulations show that COLiDeR improves network throughput in multihop topologies by over 20% compared to traditional interference-free transmissions.

Introduction

Two-path relaying in a nutshell

A basic underlying principle of current wireless networks is that a radio cannot transmit and receive at the same time, i.e., it is half-duplex, significantly limiting the performance of in-band relay networks. Consider the simple 4-node network depicted in Fig. 1. The source node, S, wants to send a batch of packets to the destination, D, which is too far to receive the packets via a direct 1 Thales Communications & Security -France, Email: name.surname@thalesgroup.com 2 IRIT-INPT/ENSEEIHT -France, Email:name.surname@enseeiht.fr 3 An early version of this work appeared as a short paper in the Proc. of the 22nd International ACM Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM), 2019 [START_REF] Naves | Colider : A cross-layer protocol for two-path relaying[END_REF] Preprint submitted to Computer Communications December 17, 2020 Figure 1: Two-path relaying. The source, S, transmits on every slot, alternating between the two relays, R1 and R2. When a relay is receiving from the source, the other transmits to the destination, jointly creating the equivalent of a single full-duplex relay.

transmission. Traditionally, S would rely on either R 1 or R 2 (both in the range of S and D) to relay its packets to the destination, node D. With half-duplex radios, S and the relay, say R 1 , would have to take turns transmitting, meaning the end-to-end capacity would be at most half the link capacity -a significant penalty, also known as the multiplexing loss. If R 1 were to have a full-duplex radio, it would be able to transmit to the destination while receiving from the source, eliminating the 1/2 loss factor. The fundamental challenge in this scenario is that R 1 's own signal would be hundreds of thousands of times stronger than the signal from S. It makes the task of decoding S' transmission extremely challenging, explaining the difficulty of realizing a full-duplex radio [START_REF] Chen | Bipass: Enabling end-to-end full duplex[END_REF][START_REF] Bharadia | Fastforward: Fast and constructive full duplex relays[END_REF].

A far easier task, however, is for R 1 to decode the transmission from S while another remote station, say R 2 , is transmitting. The powers of two remotely transmitted signals are likely to only differ by several times, paving the way for two-path relaying [START_REF] Fan | Recovering multiplexing loss through successive relaying using repetition coding[END_REF]. Assuming a TDMA (Time-Division Multiple Access) channel access protocol for ease of presentation, the source, S, can transmit on every slot, alternating between two relays. As depicted in Fig. 1, in slot k, S transmits a packet to R 1 . In slot k + 1, R 1 forwards the packet to the destination, D, while S transmits a second packet, this time to R 2 . If R 2 can successfully decode the packet from S, despite the interference from R 1 , it will forward it to D in the following slot, while S will transmit a third packet to R 1 .

Thus, as long as one relay can decode a packet from the source while the other is transmitting a packet to the destination, two-path relaying can eliminate the 1/2 loss factor, achieving the same performance as single-path relaying with a general-purpose full-duplex radio.

Two-path relaying in practice: main challenges

While two-path relaying has been studied theoretically [START_REF] Zhai | Cooperative spectrum sharing based on two-path successive relaying[END_REF][START_REF] Simoni | Buffer-aided diamond relay network with block fading and inter-relay interference[END_REF], realizing it and making it practical for current multi-hop wireless networks faces three main challenges:

• PHY-Challenge -Interfering packets decoding: Since two-path relaying requires a relay to successfully decode a transmission from the source when the other relay is transmitting, the best interference management technique to handle colliding packets needs to be identified.

Many theoretical works [START_REF] Fan | Recovering multiplexing loss through successive relaying using repetition coding[END_REF][START_REF] Zhai | Cooperative spectrum sharing based on two-path successive relaying[END_REF][START_REF] Simoni | Buffer-aided diamond relay network with block fading and inter-relay interference[END_REF] relied on the well-known concept of Successive Interference Cancellation (SIC) for decoding at the relays. It assumes that the inter-relay channel is very strong, allowing the interference to be decoded first and then eliminated from the received signal, leaving only the signal from the source. However, in a practical system, there is no guarantee as to the inter-relay channel, especially if the nodes are mobile.

• REL-Challenge -Intra-diamond relaying: Depending on source-relay and inter-relay channel -we refer to for the rest of the paper as intra-diamond channel -and the decoding performance at relays, two-path relaying is not always feasible in practice since collisions between packets may lead to a high packet loss rate. Therefore, as proposed in [START_REF] Tian | An effective distributed space-time code for two-path successive relay network[END_REF], a dynamic relaying mechanism alternating between two-path relaying, when error-free decoding at relays is possible, and traditional one-path relaying, otherwise, is necessary. The question, however, of how the stations discover the environment, select and activate the best relaying strategy to use in practice is still open.

• MAC-Challenge -Diamond channel reservation: Most papers are limited to a feasibility study of two-path relaying on the simple 4-node scenario. In larger wireless networks with multiple competing traffic flows, however, two-path relaying requires a specific channel reservation method. The main difference from traditional methods is that 4 nodes (a source, two relays and a destination) have to cooperate to access the channel, instead of two (one source and one destination) as is the case in classical point-to-point communications.

Our contributions

We present COLiDeR, a novel PHY/MAC CrOss-Layer protocol for practical decode-andforward Diamond 4 Relaying. COLiDeR builds on two key contributions, addressing the PHY-Challenge and the REL-Challenge. To answer the MAC-Challenge, we design a realistic access method on top of COLiDeR.

• PHY: We lead a testbed-driven evaluation and analysis of the best interference management technique for a relay to decode a packet from the source node while the other relay is transmitting a packet to the destination. Among the tested candidates, our experimental study shows that interference-free equalization and Physical-Layer Network Coding [START_REF] Zhang | Hot topic: physical-layer network coding[END_REF], another interference management technique, outperforms Successive Interference Cancellation (SIC).

Nevertheless, beyond this unexpected result, this comparison of decoding capacity also shows that no solution works best in all channel conditions and that two-path relaying is not always feasible using off-the-shelf hardware. Thus, we introduce the concept of channel-aware decoding areas and use a measurement-driven approach to define their boundaries.

• REL: Building on the decoding areas, we design COLiDeR, a cross-layer protocol capable of identifying the relaying strategy that increases throughput while reducing packet losses due to decoding failures. COLiDeR is a four-pronged source-centered solution: a signaling protocol for the source to ascertain the intra-diamond channel state, a state-machine modeled approach driven by the source for switching between states, a distinct scheduling for every state and an optional power adaptation mechanism for limiting the packet losses at relays. As most wireless communication protocols, COLiDeR introduces different parameters that we left open. However, in order to set up COLiDeR in practice, we lead intensive measurement analysis to discuss the influence of each parameter and select the optimal values. Then, we implement COLiDeR on the USRP radio using a generic QPSK (Quadrature Phase-Shift Keying) modulation with the GNU Radio framework [9], and evaluate its performance on a 4-node testbed using over-the-air transmissions exclusively. The experimental results show that COLiDeR delivers between 80-95% of the relaying performance of an ideal full-duplex radio while incurring negligible decoding failures.

• MAC: We introduce a fully-distributed access method running over COLiDeR that aims at reserving the channel for each diamond involved in large wireless networks with multiple nodes and multiples flows. The proposed mechanism is inspired from a well-studied slotted version of the 802.11 DCF protocol, traditionally used for channel reservation of point-to-point communications. We implement the COLiDeR-adapted channel reservation in a discrete-event simulator and evaluate it over a large network topology with different communication patterns. The data shows that two-path relaying can increase the overall throughput of a 50-node network by 20%.

The remainder of the paper is organized as follows: In Section 2, we carry the experimental evaluation of physical-layer decoding approaches and introduce the channel-aware decoding areas (PHY-Challenge). In Section 3, we design and evaluate COLiDeR (REL-Challenge). In Section 4, we introduce and evaluate the access method that aims to integrate of COLiDeR (MAC-Challenge) in multihop wireless networks. Section 5 gives an overview of the existing works on two-path relaying and section 6 concludes the paper.

Simultaneous reception of multiple packets: A measurement-driven analysis

In this section, we carry out an experimental study on the feasibility of two-path relaying and the best strategy for relays to handle the simultaneous reception of two signals.

Problem formulation

To simplify the presentation, we consider one part of two-path relaying as depicted in Fig. 1(a).

S transmits a packet, p S , to R 1 while R 2 transmits a packet, p R 2 , to the destination, with R 1 facing the challenge of decoding p S . All the results shown apply to the second part, taking place in the subsequent slot, as depicted in Fig. 1(b).

We consider that packets are sent using an OFDM coding structure with a QPSK symbol modulation on each subcarrier. Denoting with x m,k S and x m,k R 2 the symbol transmitted simultaneously on the m-th OFDM symbol and the k-th subcarrier by nodes S and R 2 , respectively, the symbol y m,k received by R 1 can be expressed as follows: where, h m,k XY is the channel coefficient of the m-th OFDM symbol on the k-th subcarrier between X and Y nodes and n is the ambient noise.

y m,k = h m,k SR 1 x m,k S + h m,k R 2 R 1 x m,k R 2 + n (1)
Obviously, the symbol x m,k S is the signal of interest for R 1 .

The decoding candidates

We consider three decoding techniques that could potentially be applied at R 1 .

1) Interference-Free (IF) equalization [START_REF] Fan | Recovering multiplexing loss through successive relaying using repetition coding[END_REF][7]: R 1 decodes directly the packet p S considering the part h m,k R 2 R 1 x m,k R 2 + n of Eq. (1) as Gaussian noise. In particular, R 1 estimates the symbol ŝm,k S sent by S on the k-th subcarrier of the m-th OFDM symbol using the minimum distance criteria.

2) Successive Interference Cancellation (SIC) [4][7][6]: This decoding technique is used to decode many packets received simultaneously with different power levels. The principle is to decode the strongest one with an IF equalization and then to cancel its contribution in equation [START_REF] Naves | Colider : A cross-layer protocol for two-path relaying[END_REF], repeating the operation until the signal of interest is decoded [START_REF] Halperin | Taking the sting out of carrier sense: Interference cancellation for wireless lans[END_REF].

When SN R R 2 ,R 1 > SN R S,
|(y m,k -ĥm,k R2R1 × ŝm,k R2 ) -ĥm,k SR1 × s| 2 (2)
with S(QP SK) the 4 symbols composing a QPSK modulation, and ĥm,k R 2 R 1 and ĥm,k SR 1 the channel coefficients estimated at R 1 .

Obviously, when SN R S,R 1 > SN R R 2 ,R 1 , SIC falls back to a simple IF decoding in which R 1 aims to retrieve ŝm,k S directly.

3) Physical-Layer Network Coding (PLNC): Never before associated with two-path relaying, we make it the third candidate because it is designed to benefit from two interfering signals.

In its simplest form, PLNC [START_REF] Zhang | Hot topic: physical-layer network coding[END_REF] consists of decoding a linear combination (typically a XOR combination) of two interfering packets rather than the two individual packets. In the considered scenario for instance, R 1 aims to decode a linear combination of p S and p R 2 rather than p S only. However, with a QPSK modulation, decoding the xor-ed packet, p S ⊕ p R 2 , is not the optimal solution [START_REF] Koike-Akino | Optimzed constellations for two-way wireless relaying with physical network coding[END_REF].

Contrary to BPSK, for any modulation of 4-ary cardinality, the best denoising map depends on

θ m,k = arg( ĥm,k R 2 R 1 ĥm,k SR 1
), the phase between the two interfering signals. Let us denote with (ŝ m,k S , ŝm,k R 2 ), the solution to the following minimum distance equation:

(ŝ m,k S , ŝm,k R2 ) = argmin s1∈S(QP SK) s2∈S(QP SK) |y m,k -( ĥm,k SR1 × s 1 + ĥm,k R2R1 × s 2 )| 2 (3) If tan |θ m,k | < 1, R 1 estimates the symbol ŝm,k S ⊕ ŝm,k R 2 ; otherwise, it estimates ŝm,k S ⊕ Rot(ŝ m,k R 2 )
, where Rot(x) is the anti-rotation function on QPSK symbols given by the following equation:

Rot(x) = xe -jΠ/2 (4)
In order to apply the same decoding estimation for symbols belonging to the same packet, we consider a unique θ value for the whole payload. It is computed by averaging the phase difference obtained in the first OFDM symbol. This decoding technique is known to be optimal in the sense of the minimum distance criteria regardless of the channel conditions [START_REF] Muralidharan | Wireless network-coded bidirectional relaying using latin squares for m-psk modulation[END_REF].

Note that, with PLNC, R 1 decodes a linear combination of p S and p R 2 rather than the individual packet p S . The destination, using previously received packets (the very first is a single native packet) can perform the PLNC decoding. Implementation details: Packets are 1280 bit-long and each OFDM symbol includes 64 subcarriers: 40 subcarriers for data symbols, 12 guard subcarriers and 12 pilot subcarriers. To estimate the channel coefficients ĥm,k R 2 R 1 and ĥm,k SR 1 each interfering payload transmission is preceded by two interference-free preambles sent by S and R 2 successively [START_REF] You | Network-coded multiple access ii: Toward real-time operation with improved performance[END_REF]. In addition, R 1 tracks the channel variation thanks to the known symbols on the pilot subcarriers, distributed in orthogonal fashion between S and R 2 . Then, the data subcarriers channel coefficients are obtained thanks to a linear interpolation [START_REF] Hynek | Hardware implementation of distributed learning algorithm for mapping selection for wireless physical layer network coding[END_REF].

Experiment description: To evaluate R 1 's capability to decode the signal from the source under diverse intra-diamond channel conditions, we keep the inter-relay link stable and vary the source transmission power. Specifically, we start by modulating the transmission power of R 2 so as to obtain SN R R 2 ,R 1 = 30 dB. Leaving R 2 's transmission power unchanged for the rest of the experiment, we vary the transmission power of node S and evaluate the Bit Error Rate (BER) at R 1 . When PLNC decoding is applied, the BER is obtained by comparing the decoded packet to

p S ⊕ p R 2 or p S ⊕ Rot(p R 2 )
, depending on the θ value obtained at R 1 .

Results: Figure 3 delivers two main lessons. First and probably most surprisingly, contrary

to what is recommended by almost all literature on the subject [START_REF] Fan | Recovering multiplexing loss through successive relaying using repetition coding[END_REF][START_REF] Simoni | Buffer-aided diamond relay network with block fading and inter-relay interference[END_REF][START_REF] Tian | An effective distributed space-time code for two-path successive relay network[END_REF], SIC is a poor enabler of two-path relaying. Instead, the data shows that on off-the-shelf hardware, using PLNC yields an acceptable BER (< 10 -2 )) for far more intra-diamond channel values.

The second lesson is that depending on the intra-diamond channel state, there are three distinct areas relevant to two-path relaying. When SN R S,R 1 > SN R R 2 ,R 1 by more than 5dB (right part of the curve), R 1 can easily decode p s by using IF, as expected. Second, when the difference in SNR between the two signals is between (5dB, -15dB) -a wide region -using PLNC enables R 1 to decode with a reasonable BER. Finally, when the desired signal becomes too weak (< 15dB), the BER starts reaching unacceptable levels.

Summary

The empirical study of this section leads to two main conclusions which will drive the protocol design and evaluation for the rest of the paper. First, we showed that unlike what is commonly believed in literature [START_REF] Fan | Recovering multiplexing loss through successive relaying using repetition coding[END_REF][START_REF] Simoni | Buffer-aided diamond relay network with block fading and inter-relay interference[END_REF][START_REF] Tian | An effective distributed space-time code for two-path successive relay network[END_REF], a decoding technique based on Physical-Layer Network Coding clearly outperforms Successive Interference Cancellation.

Second, our measurement data showed that the performance of two-path relaying will highly depend on the intra-diamond channel (IDC). Thus, we identify three IDC-level decoding areas, depicted in Fig. 4, which could lead, as shown in § 3, to different decoding strategies at relays:

• Area A -the desired signal is stronger than the interfering signal. Using interference-free equalization (IF), the relay, say R 1 (resp. R 2 ), can decode the packet from the source while the other relay, R 2 (resp. R 1 ), is transmitting a packet to the destination. Therefore, the source and R 2 (resp. R 1 ) can transmit simultaneously.

• Area B -the desired signal is similar in strength to the interfering signal. Using PLNC-based decoding, the relay, say R 1 (resp. R 2 ), can decode the xor-ed packet containing the packet from the source while the other relay, R 2 (resp. R 1 ), is transmitting a packet to the destination. Therefore, the source and R 2 (resp. R 1 ) can transmit simultaneously.

• Area C -the desired signal is significantly weaker than the interfering signal. In this case, there is no known approach for one of the relays, say R 1 (resp. R 2 ), to decode the desired signal coming from the source, if the other relay, R 2 (resp. R 1 ) transmits to the destination at the same time. These transmissions have to be orthogonalized.

COLiDeR: Design & evaluation

In this section, we introduce COLiDeR, a CrOss-Layer Diamond Relaying protocol, whose design is driven by the measurement study presented in § 2. The goal is to achieve two complementary objectives: maximizing the received throughput at the destination while minimizing the number of packet losses due to decoding failures.

COLiDeR faces three key challenges in realizing two-path relaying. First, the definition of the

SNR S,R 1 SNR R 2 ,R 1 A B C S N R S ,R 1 = S N R R 2 ,R 1 α β (SNR R 1 ,R 2 ) (SNRS ,R 2 ) (S N R S ,R 2 = S N R R 1 ,R 2 )
Figure 4: Three decoding strategies at R1 depending on the intra-diamond channel (IDC)

decoding areas, A, B, C, in § 2.4 was given in qualitative terms -the exact SNR-based definition of each area is required for the proper functionality of COLiDeR ( § 3.4). Second, assuming the decoding areas are known, specific scheduling policies are necessary, especially for the cases when one relay is able to handle two signals while the other only one ( § 3.1). Finally, the three nodes will have to agree on which schedule to use in a distributed setting using wireless communications which are inherently lossy ( § 3.2).

In the following, we describe how COLiDeR addresses each challenge, starting by assuming that the decoding areas are known. In § 3.4, we show how COLiDeR relaxes this assumption by using a measurement-driven approach.

IDC-aware states and scheduling

As our measurement study in Sec. 2 demonstrated, the performance of two-path relaying depends on the intra-diamond channel (IDC). To successfully navigate the state of the diamond, COLiDeR identifies 5 states: for three of them scheduling is trivial while for the other two a new scheduling approach is introduced.

States 0 and 0'

None of the relays can decode a packet transmitted from the source, S, while the other relay is transmitting -area C in Fig. 4 for the two relays. In this case, COLiDeR relays packets through R 1 only (state 0) or R 2 only (state 0'), following the traditional one-path relaying approach. As a result, the source can send at most 1 packet every 2 time slots, for a 0. In this case, while full-capacity two-path relaying is not possible, there is a possibility for more simultaneous transmissions when compared to one-path relaying. Thus, COLiDeR introduces the concept of 2/3-capacity two-path relaying. To illustrate it, let us consider the case in which R 1 can handle the reception of two signals while R 2 cannot (State 1), as depicted in Fig. 5(b). In slot 1, the source, S, transmits an interference-free packet to R 2 . In slot 2, R 2 relays the packet to the destination while at the same time S transmits a second packet to R 1 . Finally, in slot 3, R 1 transmits the second packet, interference-free, to the destination, which ends up receiving two packets over 3 time slots (0.66 packets/slot) -a 2/3-capacity relaying.

State 2

Both relays can decode packets transmitted by the source while the other is transmittingareas A or B in Fig. 4 for the two relays. In this case, COLiDeR switches to full-capacity two-path relaying, as depicted in Fig. 5(c). The source transmits 1 packet per slot while either R 1 or R 2 relays a packet to the destination, which receives 1 packet/slot. At the high level, COLiDeR's approach is to have the source drive the transitions, with input from relays which are in the best position to estimate the best decoding strategy. The information necessary for the coordination is shared via the transmission of orthogonal control packets (H packets in Fig. 5), whose detailed format is presented in § 3.3 (Fig. 7). We use the finite-state machine, depicted in Fig. 6, to model the selection of the two-path relaying state. The initial state, as well as the conditions for each transition, are as follows:

Initial state: To bootstrap, COLiDeR uses the traditional single-relay, half-capacity forwarding of packets. Either R 1 (state 0) or R 2 (state 0') exclusively forwards the packets from the source to the destination.

Transitioning to a higher state: The source and two relays periodically transmit control packets, as depicted in Fig. 5. Leveraging the reception of these packets, R 1 (resp. R 2 ), can estimate The source, based on the T wo Signals field of the control packets it receives, decides whether to transition to a higher state. To avoid overreacting to what could be a momentary change, the source only moves to a higher state if it receives a given number, threshold ok, of consecutive packets with T wo Signals = 1.

SN R S,R 1 and SN R R 2 ,R 1 (resp. SN R S,R 2 and SN R R 1 ,R 2 ),
To elucidate, let us consider that COLiDeR is in state 0 and R 2 , based on its analysis of the the relays to immediately transition to state 1 . In the following slot the source transitions to state 1 as well, completing the state transition, and modifies the Current State field of the control packets it sends out accordingly. The transitions to states 1 and 2 follow a similar approach, with a detailed explanation omitted in the interest of brevity.

Transitioning to a lower state: The source will decide to shift to a lower state if one of the two events occur: a) it receives a given number, threshold nok, of control packets with T wo Signals = 0, or b) it receives no control packets that pass the CRC check for a given number, crc threshold, of cycles. Should that happen, the source executes a state change by modifying the N ext State and Current State fields in the control packets it sends out, similarly to the transition to higher state.

To account for the fact that packet losses are inevitable, the relays will transition by themselves to the initial state and send out control packets with T wo Signals = 0 if they receive no control packets from the source passing the CRC check for a given number, crc threshold, of cycles. 9. CRC: Cyclic Redundancy Check in order to control the integrity of the received control packet.

Control packet format

Knowing the ABC -A measurement-driven approach

In this section, we quantify the boundaries between decoding areas A, B, C using a measurementdriven approach. First, we start with the observation that the A-B and B-C boundaries are distinct in nature. Crossing from A to B, and vice versa, does not change a relay's capability to handle two overlapping signals, meaning this boundary is irrelevant to the source node (in both cases the relay sets T wo Signals = 1). The relay, however, needs to know the boundary as it uses different decoding strategies depending on whether it is in A or B. Crossing from B to C, on the other hand, causes a relay to lose its ability to handle two overlapping signals, which it will report by changing the value of T wo Signals from 1 to 0. What is more, such boundaries cannot obviously be clear-cut: one can be very conservative and make area C very large, at the cost of often being in states 0/0', or pursue the full-capacity performance of state 2 by making C very small and B very large, at the cost of higher packet losses. COLiDeR captures this inherent trade-off by introducing two parameters -α and β -as shown in Fig. 4. Formally, α and β represent the values (in dB) of interfering signals power difference, defining the boundaries of A, B and C areas. In the following, we rely on measurements on hardware to identify the values of these two parameters that strike the best balance between throughput and packet losses.

α selection

To determine the best value for α, we simply refer to the performance comparison conducted in § 2.3. Figure 3 shows that when SN R S,R 1 is 4dB higher or more than SN R R 2 ,R 1 IF decoding leads to a better Bit Error Rate than PLNC decoding. As a result, we adopt α = 4 dB.

SN R S,R 1 28 + G dB SN R S,R 2 31 + G dB SN R R 1 ,R 2 40 dB SN R R 2 ,R 1 43 dB SN R R 1 ,D SN R R 2 ,D > 40 dB 3.4.2

. β parameter selection

As mentioned at the beginning of this section, when a relay crosses from area B to C, it estimates that it cannot handle two signals anymore and changes T wo Signals from 1 to 0. It leads the source station to transition to a lower state (Cf. § 3.2) and the relay itself to switch to IF decoding. As a result, a low β value will cause the system to be in the low two-path relaying states, reducing the maximum throughput, while a large β value will lead to an aggressive pursuit of the higher states, with the higher maximum throughput, but at the cost of higher packet losses.

With the β parameter impacting the throughput and packet delivery rate, in the following we evaluate its impact on both these metrics. We place the 4 USRPs of our testbed so as to obtain the SNRs values indicated in Table 1. For three different values of β we carry a series of experiments in which we change the source transmission gain G, which directly affects SN R S,R 1 and SN R S,R 2 .

We assume the source always has packets to transmit.

Figure 8 reveals an interesting trade-off between throughput and packet delivery rate induced by the choice of β. When its value is highest, 15 dB, relays are always in area B, leading the source to always maintain state 2, resulting in the highest performance in terms of throughput, as illustrated in Fig. 8(a). However, because the relays overestimate their real ability to decode two interfering packets, this comes at a high cost in terms of packet losses, as Fig. 8(b) shows. On the other side of the spectrum, with β = 3 dB, the source remains in state 0. Even if very few packets are lost, the achieved throughput in this case does not exceed 0.5 frames per slot. Setting β = 9 dB strikes the best trade-off: the throughput is never more than 15% lower than with β = 15 dB but the number of lost packets is considerably reduced. Thus, it is the value adopted by COLiDeR.

Optional source power control

Our study for identifying the best values for β revealed that the system performance is still impacted by the intra-diamond channel. For example, Fig. 8(a) shows that the throughput never reaches the expected maximum throughput of 1 packet/slot. This is due to the fact that the performance of PLNC decoding can suffer under particular channel conditions. As Fig. 3 shows, the BER obtained with PLNC decoding presents two local peaks when

|SN R S,R 1 -SN R R 2 ,R 1 | = 3dB.
These particular BER variations values are not coincidental or result of particular hardware but rather represent singularities inherent to how PLNC decoding works. As detailed in [START_REF] Koike-Akino | Optimzed constellations for two-way wireless relaying with physical network coding[END_REF], they are due to a reduction in the distance between the received constellation points occurring when θ approaches Π 2 . Therefore, a clear path to improving performance is adjusting the transmit power levels so as to steer COLiDeR towards the BER local minima observed when SN R S,R 1 -SN R R 2 ,R 1 is 0 dB or -7 dB (Fig. 3). The simplest option would be to adjust the transmit power of all three nodes, however, this could have unintended consequences on the relay-destination links that we consider strong in this work. Thus, we adopt an approach in which only the source transmission power is adjusted. The basic idea is for the relays to report to the source the SNR difference between the signal from the source and the signal from the other relay and for the source to adjust its transmit power as necessary. When a relay, say R 1 , estimates that the power difference between the two signals is close to 3 dB (resp.-3 dB), it asks to the source to reduce its transmission power by a value indicated in the dedicated field of each control packet such that SN R In order to evaluate the gains of the proposed power adaptation mechanism, we place our USRP nodes with the aim of having COLiDeR transition to state 2 and both relays using PLNC decoding (area B). We then vary the maximum transmission power of the source node by varying the transmission gain G and evaluate the number of packets received at the destination with and without the power adaptation mechanism. As shown in Fig. 9, when using power control, COLiDeR's performance never drops below 0.85 frames/slot, a 15% improvement, on average and with no impact on packet loss.

S,R 1 -SN R R 2 ,R 1 = 0 dB (resp. SN R S,R 1 -SN R R 2 ,R 1 = -7 dB).

General evaluation

Method: To evaluate the overall performance of COLiDeR in different channel conditions, we implement a scenario incorporating four representative configurations. Initially, configuration I, the 4 USRP radios are placed in the classic diamond topology and the transmission power levels are selected such that only one relay can handle two simultaneous transmissions with a reasonable bit error rate. At time t 0 = 100 slots, relay R 2 is switched off, creating configuration t 0 aimed at emulating a relay loss due to mobility. At t 1 = 200 slots, relay R 2 is switched back on, emulating the selection of a new relay. In the final configuration, at t 2 = 300 slots, the source transmission power is increased, emulating a scenario in which the source moves closer to the relays.

Comparison: Our goal is to evaluate how COLiDeR navigates the trade-off between reliability and throughput, its principle design consideration. Note that COLiDeR could optimize reliability by permanently staying in state 0, the equivalent of traditional one-path relaying. Thus, this approach is included in the study. On the opposite side, having COLiDeR permanently in state 2 maximizes throughput even though it may cause severe packet losses. To see why this is true, consider the case in which R 1 and R 2 can not handle the reception of two interfering signals. While R 1 is transmitting a packet to the destination, the source has two choices. It can transmit to R 2 , the maximalist approach, leading to a packet loss. Or it does not transmit, which is what COLiDeR would have done since it would have transitioned to state 0. In terms of throughput, assuming layer two will retransmit the same packet in the following slot, the maximalist approach did no worse than COLiDeR even though it transmitted unnecessarily, wasting energy and augmenting interference. COLiDeR, however, may sometimes do worse than the maximalist approach in terms of throughput, either because it is designed to wait for a few rounds before it transitions to the next best state, or because it chooses to be in a lower state to avoid packet losses. Thus, the maximalist approach provides a good reference to compare against.

Results: Figure 10 plots the end-to-end throughput (Fig. 10(a)) and percentage of lost packets (Fig. 10(b)) against time. Each value is obtained by computing the throughput and loss ratio over the 30 previous slots.

In the initial configuration, I, R 1 can handle the reception of two signals with a reasonable bit error rate whereas R 2 cannot. COLiDeR adopts scheduling state 1 ( § 3.1), resulting in 0.66 packets/slot throughput and no packet losses -the best joint throughput-reliability performance.

When the source adopts the maximalist approach and transmits a packet every slot, a slightly higher (around 8%) throughput is achieved, because occasionally, R 2 successfully decodes the interfering packets. It comes, however, with a high penalty in terms of packet losses, around 25%.

Furthermore, COLiDeR performs just as well as one-path relaying in terms of packet losses while outperforming it by 25% in terms of throughput.

At t 0 = 100 slots R 2 is switched off, leaving a single path to the destination. Obviously, as Fig. 10(a) shows, the maximum throughput in this case, realized by all schemes, is 0.5 packet/slot.

Having the source sending 1 packet/slot when only R 1 is active, however, leads to an inevitable 50% rate loss. As described in § 3.2, COLiDeR, after receiving no control packets from R 2 , transitions from state 1 to state 0, limiting the packet losses.

At t 1 = 200 slots, relay R 2 is switched back on and is eventually integrated back to two-path relaying, enabling the two-path relaying schemes to realize the performance observed in the period 0-100 slots. Finally, at t 2 = 300 slots the source transmission power is increased, enabling R 2 to handle the reception of two simultaneous signals with a reasonable bit error rate. COLiDeR takes advantage of the newly created opportunity and transitions to state 2, achieving close to channelcapacity performance in terms of throughput with almost zero packet losses. The maximalist approach, while also transmitting 1 packet/slot, does not include power control, explaining its inferior performance when compared to COLiDeR.

COLiDeR in multi-hop wireless networks

In the previous sections, in order to design COLiDeR, we considered the 4 nodes involved in the relaying process in isolation. The question we consider in this section is how to integrate our scheme in larger networks, in particular in multihop wireless networks where tens of flows may be established simultaneously. In these networks, many nodes may be competing with each other for channel access. As a result, integrating COLiDeR is not straightforward: it requires a specific channel access mechanism for the 4 nodes to reserve the channel while causing all the potential interfering neighbors to defer. In this section, we address this challenge by introducing and evaluating an 802.11-inspired channel access method. However, this scheduling mechanism is designed for 1-hop interference-free transmissions. As illustrated in Fig. 12, we propose some modifications to integrate two-path relaying while keeping the same main design principles.

1. RTS/CTS transmission range: Whereas the original version leverages the 1-hop transmission range for both control and data packets, we increase the transmission range of RTS/CTS packets in order for the senders to reach their 2-hop neighbors. In practice, this can be done by increasing power transmission or by adopting a more robust Modulation-Coding Scheme (MCS).

With this, each source of a two-path relaying process can send directly its RTS packet to the

Performance in multi-hop wireless networks

To evaluate the performance of the proposed COLiDeR-adapted scheduling mechanism, we have developed our own discrete-event simulator in MATLAB that runs both the original interferencefree and COLiDeR-adapted mechanisms. We carried experiments on the 50-node topology shown in Fig. 13 and present here the results for two particular scenarios, relying on two different communication patterns.

Scenario 1: decentralized communications

Simulation description: In the first scenario, we instantiate 5 flows by selecting 5 different source-destination pairs, as illustrated in Fig. 13(a). Each path is randomly selected among the available shortest paths (in terms of hops) between the source and the destination. In the COLiDeR-adapted scheduling case, the nodes (sources and relays) always leverage two-path relaying opportunities when they occur (nodes know their 2-hop neighborhood and the two-path opportunities for each flow). As a consequence, as illustrated for the flow 1 in Fig. 13(a), paths may be composed of both traditional 1-hop link and COLiDeR's diamonds.

To ensure fairness in the evaluation, the scheduling parameters are the same for the interferencefree and the COLiDeR-adapted access methods: the contention slots are composed of 2 mini-slots (M = 2) in order to limit the overhead and the probability of transmission alpha is set to 0.02 in order to reduce collisions during the access race. A lot of algorithms have been developed in the last years in order to optimize these parameters [16] [17]. However, this is beyond the scope of this paper and we will use the same constant value for all the nodes of the network. Last but not least, we assume that the selected diamonds are in state 2 of COLiDeR, meaning that the relays can receive a packet from the diamond source when the other relay is transmitting. In other words, the diamonds have the same capacity as the traditional 1-hop links.

Results: As performance metric, we evaluate the average number of packets received by the 5 final destinations during 4000 slots over 500 simulation runs. We work at saturation: the 5 sources always have a packet to transmit in their queue. Fig. 14 shows that the integration of COLiDeR in this multi-hop wireless network increases the overall throughput, since the number of received packets is higher when two-path relaying is activated. Indeed, since COLiDeR triggers two transmissions instead of one, as is the case with the original interference-free reservation mode, more transmissions are established in a single frame and packets reach faster their destination.

Scenario 2: centralized communications

Simulation description: In the second scenario, we keep the same network topology but we change the communication pattern. Now, there is only one destination (red node in Fig. Results: As for decentralized communications, the total number of packets received by the central destination increases when two-path relaying is allowed (Fig. 15(a)). To refine and complement this result, we also evaluate in Fig. 15(b) the average throughput gain of two-path relaying compared to traditional interference-free transmissions as function of the number of hops between the source and the destination. As expected, the data shows that 2-hop flows achieved the highest gains (more than 30% after 4000 slots of simulation) since each path involved one diamond. Surprisingly, however, the data shows a throughput gain of 20% by the end of the simulation for one-hop flows. This can be explained by the fact that two and 3-hop flows are transmitted faster to the destination, leaving a larger share of the channel capacity to the one-hop flows.

Related Work

Due to its potential for minimizing the multiplexing loss using half-duplex radios, the twopath relaying has attracted a lot of attention in recent years. First, Fan et al. introduced a scheduling policy capable of eliminating the multiplexing loss, enabling the destination to receive 1 packet/slot [START_REF] Fan | Recovering multiplexing loss through successive relaying using repetition coding[END_REF]. However, this solution assumes optimal decoding of the two overlapping signals at the relays. Its performance drops significantly when realistic decoding errors are introduced [START_REF] Li | Outage analysis of co-operative two-path relay channel[END_REF]. As our work has shown, two-path relying is founded on the capability of modern radios to handle two overlapping transmissions, making the choice of the decoding strategy of paramount importance.

In [START_REF] Zhai | Cooperative spectrum sharing based on two-path successive relaying[END_REF] and [START_REF] Simoni | Buffer-aided diamond relay network with block fading and inter-relay interference[END_REF], Successive Interference Cancellation (SIC) [START_REF] Halperin | Taking the sting out of carrier sense: Interference cancellation for wireless lans[END_REF] was advanced as the best potential candidate. Nevertheless, it is noted that depending on the interfering signals power levels, SIC can be highly inefficient. Our work is the first to address this oversight and present a complete solution combining Physical-Layer Network Coding and interference-free equalization. A two-path relaying approach that relaxes the assumption of optimal decoding is proposed in [START_REF] Tian | An effective distributed space-time code for two-path successive relay network[END_REF]. The main idea is to fall back to one-path relaying when two-path relaying suffers from too many decoding errors. However, this work is mostly theoretical and leaves unaddressed many crucial practical issues such as how does the source know of the decoding errors in the first place. COLiDeR is the first protocol that addresses the challenges arising from realizing two-path relaying in practice.

Conclusion and Future Work

We have presented COLiDeR a PHY/MAC cross-layer solution for adaptive two-path relaying. Our solution addresses the 3 main challenges for the integration of two-path relaying in multihop wireless networks. First, our experimentally driven approach leverages real testbed evaluations for identifying the best interference management technique to handle colliding packets (PHY-challenge). Our experiments highlight the inefficiency of Self Interference-free Cancellation, leveled in its recommended area of operation by the Physical-Layer Network Coding and outperformed elsewhere by either PLNC or basic equalization. Then, COLiDeR includes a relaying protocol that selects dynamically the optimal scheduling scheme depending on channel state and topology evolution (REL-challenge). Optionally, our protocol integrates power control that leverages singularities in how PLNC works for increased efficiency. Based on a well defined control plane messages and an efficient setting of the thresholds that our solution relies on, COLiDeR ensures smooth and efficient sailing between the defined protocol states. Experimental results have shown that COLiDeR achieves between 80-95% of the relaying performance of the ideal fullduplex radio while incurring negligible decoding failures. Finally, on the top of COLiDeR, we also propose a fully-distributed access method in order to integrate it in multihop wireless networks (MAC-challenge). We have integrated this mechanism in an discrete-event simulator and the obtained results have shown that COLiDeR may increase the overall throughput by 20% in a 50-node networks, with multiple flows and different traffic patterns.

In the future, we intend to work on two different problems in order to extend the sphere of operation of COLiDeR. First, in this paper we leverage on measurement-driven approaches to select the optimal values of the defined parameters. We believe that these values could be adapted dynamically depending on the observed channel conditions, thanks to Deep or Reinforcement Learning techniques. Then, while this work paves the way to the integration of COLiDeR in multihop wireless networks, two-path relaying needs other higher layer protocols to fully efficient in these networks. Many questions could be of interest: How to identify diamonds with a limited 1hop topology knowledge? Can we override the next hop decisions imposed by the routing protocol in order to have the required flexibility in the relay selection?

Figure 2 :

 2 Figure 2: USRP testbed used for implementing and evaluating diamond-based relaying.

2. 3 .

 3 IF vs. SIC vs. PLNC Experimental platform: To compare the performance of the three decoding techniques, we use the testbed depicted in Fig. 2. It consists of 4 Ettus Research Universal Software Radio Peripherals (USRPs) N210 equipped with an SBX daughterboard and GPS antennas. Communications take place over the 1.8 GHz frequency band with a sampling rate of 400kB/s and the signal/MAC processing is done in C++ and Python within the GnuRadio framework [9]. A slotted TDMA channel access is built thanks to the GPS synchronization.

Figure 3 :

 3 Figure 3: Error Rate at R1 with different values of SN RS,R 1

Figure 5 :

 5 Figure 5: COLiDeR introduces 3 scheduling policies: the traditional half-capacity one-path relaying (5(a)); 2/3capacity two-path relaying (5(b)); and full-capacity two-path relaying (5(c)).

3. 1 . 2 .

 12 States 1 and 1' R 1 can handle the reception of two signals while R 2 cannot (state 1) or R 2 can handle the reception of two signals while R 1 cannot (state 1') -areas A or B in Fig. 4 for one of the relays and area C for the other.

Figure 6 :

 6 Figure 6: Source rate adaptive protocol state machine

  necessary for deciding in which decoding area of Fig. 4 it most likely is. If R 1 estimates that decoding two signals is possible, i.e. area A or B, it notifies the source by setting T wo Signals = 1 in the next control packet it transmits.

Figure 7 :

 7 Figure 7: Control Packet Format

Figure 7 outlines 2 .

 72 Figure 7 outlines COLiDeR's control packet format, which contains the following fields (sizes in bits): 1. P ilot Symbols: Used for channel estimation in order to decode the rest of the control packet and, potentially, the following payload. 2. Length: Length of the following payload. 3. N ext hop: Next hop of the following payload.

4 . 5 .

 45 ID: 24 bits for the 3 packet IDs (with PLNC and partial linear combination reduction at relays, each payload may be a combination of at most 3 native packets) and 1 bit each to indicate whether of the native packet or the rotated packet is in the linear combination. Current State: State of the diamond. 6. N ext State: State to be adopted in the subsequent slot 7. T wo Signals: It is set to 0 or 1, depending on the ability of the relays to handle the simultaneous reception of the packet sent by the source and the packet from the other relay. 8. P ower Reduction: Value in dB of the optional power reduction (see § 3.5).

Figure 8 :

 8 Figure 8: Trade-off between the received throughput and the percentage of lost packets

Figure 9 :Figure 10 :

 910 Figure 9: Power adaptation mechanism evaluation

4. 1 .Figure 11 :

 111 Figure 11: Frame: contention slot + data slot

Figure 12 :

 12 Figure 12: Two-path relaying channel reservation

2 Figure 13 : 3 .

 2133 Figure 13: COLiDeR performance in a 50-node scenario

Figure 14 :Figure 15 :

 1415 Figure 14: Scenario 1: Number of received packets during 4000 slots of simulation

Table 1 :

 1 Links state in the β evaluation

Due to the geometrical shape of the Fig.1topology, two-path relaying is also known as a diamond relay network.

SN RX,Y denotes the Signal-To-Noise Ratio of a signal sent by node X measured at node Y .


Romain Barbau

Vincent Deslandes

Gentian Jakllari

Jérôme Tronc

Jean-Frédéric Chouteau

André-Luc Beylot

NB-IoT over GEO Satellite: Performance Analysis

NB-IoT (Narrowband Internet of Things) has been introduced by 3GPP with the aim of meeting the 5G requirements for the IoT segment through coverage classes, repetitions, narrower subcarriers, user and control planes optimizations and power saving mechanisms. Recognizing the capability of satellite systems to offer wide coverage and enable cross-countries deployment, 3GPP is considering 5G technologies to support Non-Terrestrial Network (NTN). However, while studies have shown the capability of NB-IoT to meet the 5G latency and capacity expectations in terrestrial networks, the question remains open for the satellite context.

In this paper, we consider the necessary mechanisms for adapting NB-IoT to the satellite context and provide a study of the delay of a communication as function of gNodeB parameters, cell specification (size, link budget, satellite altitude) and payload size. Our study adopts the configurations used for the simulation based on the link budget given in the 3GPP Study Item and considers not only the random access procedure but also the whole communication process, with signalling, uplink /downlink messages and connection release. We find that the optimal Block Error Rate for minimizing the delay of the communication and optimizing the spectral efficiency is lower that the one recommended in nominal 5G specification.

I. INTRODUCTION

The Internet of Things (IoT) is a new paradigm that has emerged in cellular networks. The predicted growth of the number of devices connected has already begun and is expected to continue -25 billions devices today, 75 billions in 2025 ( [START_REF] Gsma | Gsma iot report iot in the 5g era[END_REF], [START_REF]Statistica. Report : Iot number of connected devices worldwide[END_REF]). In short, IoT solutions are aimed at a better performance than regular cellular networks (GSM, LTE) in terms of battery lifetime, coverage, device density, cost and complexity for low data rate communications. However, these improvements are done at the detriment of other metrics that are less critical to IoT communication such as latency, throughput and paging needs.

In the 2000's, cellular IoT applications were mainly using the GSM network (2G) because of the low cost (underused and already paid-for infrastructure) despite the low spectral and power efficiency. In 2013 Sigfox became one of the first large-scale cellular networks dedicated to IoT applications, along with the non-proprietary IoT technology LoRaWAN. Both Sigfox and LoRaWAN are deployed within the free ISM bands and are defined as Low Power Wide Area Networks (LPWAN). These LPWAN solutions demonstrated the huge potential market for IoT communications. Hence, 3GPP Long Term Evolution for Machine type communication (LTE-M), Extended-Coverage GSM (EC-GSM) and Narrowband IoT (NB-IoT) were first standardized in Release 13 -Q1 2016, improved in Releases 14 and 15 -respectively mid-2017 and Q4 2018.

In this paper, we focus on 3GPP NB-IoT, a solution that is expected to broaden the scope of 5G applications to include smart home -cities -grids -utilities -meters, object tracking and remote control among others. 5G-IoT aims to connect 5 billion devices by 2025. In parallel with the growth of IoT, satellite technologies have evolved and now allow the launch of low cost satellites and new kinds of services: nano-satellites, on-board payloads, regenerative payloads, etc. In addition to the current offerings of Orbcomm or Iridium (LEO) and Inmarsat, or Thuraya (GEO), new targeted IoT constellations are already being deployed: Astrocast, Fleet Space, Myriota, Kineis, ELO (Eutelsat) or Lacuna Space. Concerning NB-IoT, Ligado (formerly SkyTerra), a GEO operator, is partnering with Ericsson and Sequans for deploying a NB-IoT service over satellite in the United States [START_REF] Ligado | Satellite-adapted 5g iot[END_REF]. On European side, ESA and GateHouse Telecom are partnering to develop space-based NB-IoT network [START_REF] Group | Esa and gatehouse telecom sign contract to develop space-based nb-iot network[END_REF]. The 3GPP Study Item [START_REF] Gpp | Technical specification group radio access network; solutions for new radio (nr) to support non-terrestrial networks (ntn) (release 16)[END_REF] specifies the solutions considered so as to address the three challenges in the operation of 5G via satellite technologies:

• Signal propagation delay and differential propagation delay: In land deployments, the base station is located within a radius of 40 km. The propagation time is therefore less than one millisecond. For the satellite, a minimum signal propagation delay of 125 ms (GEO regenerative case) or 250 ms (GEO transparent case) must be taken into account for the geostationary case. The problems caused by this additional delay can usually be solved by increasing the protocol timers. However, as we show in Section II, the fact that intra-cellular delays can exceed milliseconds (up to 10 ms for the geostationary case) introduces the problem of collisions between different channels. This problem can be solved by adding guard times and increasing cyclic prefix durations, but at the expense of system performance. • Doppler frequency shift and drift: Both 4G and 5G are technologies designed to support travel speeds of up to 500 km/h (high-speed trains). But LEO satellites have much higher velocities, measured in kilometers per second. Guard bands or the use of GPS positioning in conjunction with satellite ephemeris are considered for overcoming the Doppler shift. However, there is still the challenge of Doppler drift because the satellites at low altitude are passing by. The generated Doppler shift is therefore not constant, switching between positive and negative values. • Moving cells: In a constellation, the satellites along with the cells are in constant motion so the terminal must handover between cells / satellites on tens of seconds / few minutes basis to maintain communication. In 3GPP systems, these frequent handovers may cause not only reliability and latency problems, but also generate a large amount of control messages for maintaining the connection and keeping position information of the terminal. In this work, we study the geostationary satellite case and therefore focus on studying the impact of signal propagation delay, intra-cell delay and coverage condition on the performance of NB-IoT communications and how to reduce this impact using existing configuration capabilities of the NB-IoT beam cell. To this end, we have implemented the entire communication process with both the random access and the allocated/connected phase.

The contributions of this paper can be summarized at two levels: first, we highlight the direct impact between beam size and spectral efficiency loss, second, we reveal an interresting finding about the targeted Block Error Rate, i.e. the trade-off between re-transmission and repetition.

The rest of the paper is organized as follows. Section II is a technical description of NB-IoT. Section III summarizes the mechanisms considered to allow NB-IoT satellite communications as well as their interaction with the features described in section II. In Section IV, we evaluate the performances of different cell configurations through simulations. We focused on the delay of the communcication and the cell capacity in term of aggregated throughput. Finally, we discover that the long-established terrestrial network optimum for Block Error Rate is challenged for the geostationary satellite context. Before to conclude this work, we underline the important related works on the performance of NB-IoT in section V.

II. NB-IOT

NB-IoT is organized in carriers of 180 kHz bandwidth, called Physical Resource Blocks (PRB). This is an heritage of legacy Long Term Evolution (LTE) technology (4G) which is deployed on a minimum of 6 PRBs. In this section, we focus on the functionality of one of these resource blocks. For scalability, PRBs can be stacked next to each other. 10 kHz guardbands are included on both sides of NB-IoT carriers to reduce interference with other technologies. As a technology designed at the end of the 4G era and the dawn of 5G, NB-IoT introduces three deployment modes: • Standalone, using a dedicated frequency band.

• Inband, in a resource block of an LTE carrier, resulting in lower performance because of LTE broadcast symbols. • Guardband, in the guardband between two LTE carriers which causes interference. In this work, we consider a standalone deployment because of the satellite context.

In the following, we describe the different phases of an NB-IoT communication with a particular emphasis on the channels used.

B. Access Phase

When the UE is synchronized, it sends a preamble to notify the base station that it wishes to transmit. Random Access Opportunities (RAO) are periodic in the UL PRB Fig. 1, offer from 12 to 48 different preamble indexes (3.75 kHz wide) and are associated to a given number of preamble repetitions. The UE randomly chooses an index on which to transmit its preamble. In order to avoid unnecessary repetitions, up to 3 coverage classes called CE (Coverage Enhancement) can be defined. A terminal derives its class based on the power threshold it receives from the base station. It deduces its RAO and therefore the number of preamble repetitions. The sum of the CEs constitutes the access channel -Narrowband Physical Random Access CHannel (NPRACH). All information about the NPRACH is available in the broadcast channel (periodicity, number of indexes, repetitions, timing offset, power thresholds). Note that preambles are deterministic symbols and do not contain particular data.

Figure 1 shows 2 CEs. The blue one corresponds to frequent opportunities (20 ms period) for devices in good coverage (1 repetition). And the red one is dedicated to devices in extreme coverage (8 repetitions) and offers far fewer opportunities (12 indexes every 80 ms). All other time-frequency slots are dedicated to allocated resources, referred to as the Narrowband Physical Uplink CHannel (NPUSCH).

If two or more UEs choose the same preamble index a collision occurs , in which case the UE will retransmit and send another preamble after some back-off time. After a number of unsuccessful retransmision attempts varying between one and several hundreds, depending on the cell configuration, the communication is definitively considered as having failed.

The first preamble that does not suffer a collision allows the UE to complete the connection process through the legacy LTE "hand-shake". After this "hand-shake", the UE enters the Data Phase, without further additional signalling (User Plane Optimization).

C. Data Phase

Since in this work we consider uplink traffic only (from UE to satellite), two kinds of messages are needed during the data phase: a) Resource Grants in the Narrowband Downlink Control CHannel (NPDCCH) allocating b) Transport Block (TB) in NPUSCH containing payload and buffer status. Thus, the data phase is a succession of resource grants and transport blocks. Every time the base station receives a TB, it allocates new resources for the next one, according to the buffer size and the possible TB sizes (from 16 to 2536 bits [START_REF]Technical specification group radio access network; evolved universal terrestrial radio access (e-utra)[END_REF]).

In case of reception errors, NB-IoT uses a Hybrid Automatic Repeat Request (HARQ) mechanism at the TB level. This is a typical ARQ process: each time a TB cannot be decoded successfully the grant message asks for a re-transmission (New Data Indicator not toggled). At the receiver side, the base station combines the re-transmissions of the same TB for increasing the chances of success.

In the Data Phase, messages are exchanged on allocated resources. Therefore no collisions should occur during NPUSCH. The base station allocates Resource Units (RUs) of different time-frequency shapes [START_REF]Technical specification group radio access network; evolved universal terrestrial radio access (e-utra)[END_REF]. The different shapes of an RU make possible to play either on the flow rate or on the received SNR. Furthermore, there are two categories of RU: multitone, several symbols sent simultaneously, or singletone, only one symbol at a time. The key difference between multitone and single-tone is the number of symbols they carry N symbols , 144 and 96, respectively.

The UL Grant specifies a number of useful bits to transmit, N bits , from 16 to 2536 bits, and a number of RU, N RU , from 1 to 10, depending on the coverage condition of the UE. Finally the UL grant contains the maximum number of repetitions, ranging from 1 to 128, R, necessary to improve the reliability of the communication in addition to the robustness already provided by turbo codes in RUs.

With all this information, one can compute the code rate associated to a TB as follows:

CR = N bits + N CRC N RU • N symbols • m • R (1)
where N bits , N RU , N symbols , R are described above, N CRC is the number of bits used for check code (24 for NB-IoT) and m is the order of the modulation used. The code rate is used to compute the probability of error on a given TB knowing the Signal to Noise Ratio (SNR).

III. MECHANISMS TO SUPPORT SATELLITE

This section summarizes the mechanisms considered to allow NB-IoT satellite communications as well as their interaction with the features described in the previous section.

A. Scenario definition

We consider the geostationary satellite case described in 3GPP Technical Report TR.38821 [START_REF] Gpp | Technical specification group radio access network; solutions for new radio (nr) to support non-terrestrial networks (ntn) (release 16)[END_REF] i.e. a transparent multibeam GEO satellite in S band (around 2 GHz). Each beam

Gateway + gNodeB

Reference point

GEO Satellite UE #x UE #y ! "# ! "$ ! $% ! $& 1 beam = 1 cell
Fig. 2: Transparent GEO satellite scenario (up to several hundreds beams per satellite) correspond to a NB-IoT cell. Within this context, the delay and the differential delay can be defined from the Figure 2.

UEs and satellite communicate using the NB-IoT radio interface. In transparent satellite mode, the satellite relay the raw signals (generally by transposing at higher frequencies) to/from the ground Gateway without any processing on the messages. The Gateway plays the role of gNobeB and performs the signal and message processing. From Figure 2, we get the following set of equations:

     Minimum delay: D min = 2•(d01+d02) c UE specific differential delay: D dif fx = 2•(d1x-d01) c Full delay: D = D min + D dif fx
(2) In the literature on 3GPP cellular technologies, The base station compensates for the propagation delay with so-called Timing Advance (TA). These TAs are specific to each UEs and enable them to transmit or listen to time-shifted signals in order to be synchronized with the cell uplink (UL) and downlink (DL) frames. Typically the TA in the terrestrial environment is less than one millisecond -the maximum cell radius to be considered for NB-IoT is 40 km1 (266µs cyclic prefix in preamble [START_REF]Technical specification group radio access network; evolved universal terrestrial radio access (e-utra)[END_REF]). For the transparent geostationary case, the maximum delay is around 270 ms and the maximum differential delay should not exceed 10.3 ms [START_REF] Gpp | Technical specification group radio access network; solutions for new radio (nr) to support non-terrestrial networks (ntn) (release 16)[END_REF] (≈ 3500 km max beam foot print size regardless of the elevation angle).

In the following, we describe the effects of these unusual propagation delays on the performance of NB-IoT.

B. Differential delay effect

When the terminal wakes up, it does not know its position relative to the gNodeB. The preambles contain the connection request, and inform the gNobeB on each UE specific propagation time. The gNobeB then transmits the TA to the UEs in The problem in the satellite case is that the differential delay within a single beam (= cell) is large enough to impact the resources allocated to NPUSCH that follow the RAOs, see Figure 3. The solution considered in the technical report [START_REF] Gpp | Technical specification group radio access network; solutions for new radio (nr) to support non-terrestrial networks (ntn) (release 16)[END_REF] is to use guard times to avoid allocating NPUSCH following the NPRACH based on cell size (maximum differential delay). It is also necessary to increase the CP size of the preambles, which must be at least equal to the maximum differential delay in order to guarantee the orthogonality of preamble transmissions on different subcarriers [START_REF] Lin | Random access preamble design and detection for 3gpp narrowband iot systems[END_REF]. Thus each RAO of CE n°i is extended by δ i ms (Eq.3).

δ i = δ + δ • 4 • N rep i (3)
with δ the maximum differential delay within the beam, 4 the number of CPs per preamble repetition and N rep i the number of repetition for the i th CE. In the satellite context, the uplink frame (from UE through satellite to the Gateway) received by gNodeB is impacted by the effect of the differential delay as shown in the Figure 4. Ratio of uplink resources lost due to differential delay, R loss , is then:

R loss = i∈CEs 3.75 • N sc,i 180 • δ i period i (4)
with 3.75 the width of the preamble subcarrier (kHz), N sc,i the number of subcarriers (preamble indexes), 180 the width of the PRB (kHz), period i the period of the i th CE, and δ i its extension due to differential delay as computed in Eq. 3. In Section IV, we observe the variation of the cell capacity in terms of number of UEs as function of beam/cell size, i.e., δ.

The other solution considered in TR.38.821 to solve the differential delay issue in satellite is to use the GPS of UEs. However, there are two issues. First, the base station does not know the TA of the UE until it is able to send data to it, and it is unable to provide it with a relevant resource allocation. And second, GPS is very energy consuming on the UE side. Thus, while it is reasonable to assume that 5G smartphones will have a GPS with sufficient battery size, for IoT terminals this seems less likely.

C. Propagation delay effect on BLER selection

Once the TA has been established, the delay should not cause any more concern since the protocol timers have been adapted to the satellite case. The base station allocates the resources in the NPUSCH according to the UE specific TA and shifts its reception window.

Nevertheless, an interesting trade-off between repetitions and re-transmissions in the HARQ process emerges. In NB-IoT, only one or two HARQ process at a time can be allocated (depending on device class). The base station waits until it has received Transport Block N before allocating Transport Block N+1 or N+2. Therefore, the total delay of the communication will be extended with the use of the satellite. However, when the base station is unable to decode Block N, the entire communication is delayed by 500ms (see Figure 6). Generally in GEO satellite context, the link is made more robust (lower probability to loss a Transport Block) in order to avoid such significant delay in the communication. The two solutions to make the communication more robust are a) to choose a lower Modulation and Coding Scheme (MSC) index -I M CS or b) to repeat the TB.

IV. RESULTS

The objective of this section is to evaluate the impact of both guard times § III.B and BLER selection § III.C mechanisms on the performance of an NB-IoT cell in a satellite context. For this purpose we have implemented an event driven simulator in python that includes random access, frame mechanics, subframe (DL) and Resource Unit (UL) allocation, and taking into account transmission times, propagation times and transition times between UE states. We used this simulator to determine a) the communication delays (defined as the duration between the first preamble transmission by the UE and the correct reception of data by the gNodeB) and b) the impact of the mechanisms described in Section III on the aggregated throughput of an NB-IoT cell.

A. Scenario configuration

Within the considered beam we used the SNR distributions defined in the technical report [START_REF] Gpp | Technical specification group radio access network; solutions for new radio (nr) to support non-terrestrial networks (ntn) (release 16)[END_REF]. Our work is aimed at Subcase n • 5 of this report:

• GEO satellite

• 45 • for central beam elevation • Handheld UEs (Omnidirectional antenna) • Band S • Frequency re-use
To study the effect of different target BLERs on the performance of the cell we need their values as a function of the SNR. They can be found in the literature and are quite similar to the LTE values for the QPSK modulation [START_REF] Soussi | Evaluating the performance of emtc and nb-iot for smart city applications[END_REF][START_REF] Ding | A novel mcs selection criterion for voip in lte[END_REF]. We obtained the curves for the downlink signal by our own Matlab simulations. The BLER curves for uplink are summarized in Figure 7. In order to take into account the effect of repetition, we consider that each time the number of repetitions doubles, the received SNR also doubles, i.e. a 3dB gain for a small number of repetitions [START_REF] Andres-Maldonado | An analytical performance evaluation framework for nb-iot[END_REF][START_REF]Analytic analysis of narrowband iot coverage enhancement approaches[END_REF]. We combined SNR distributions and BLER curves (Fig. 7) to adapt the MCS to the target BLER. Figure 8 corresponds to a targeted BLER of 10 -1 . Unlike for terrestrial links, SNRs have a much more homogeneous distribution in satellite links, which has the effect of attenuating the differences between the modulation and coding scheme of the different coverage classes. It is worth noticing that single-tone transmission and a targeted BLER of 10 -1 no repetitions are needed. We have also defined coverage areas based on the distribution of the SNR by choosing to assign 25% of the UEs to the best coverage, CE 0; 50% to the medium coverage, CE 1; and 25% to the worst coverage, CE 2 (Table I). UL thresholds are deduced from Figure 8.

B. Differential Delay Analysis

In this section, we study the impact of the guard times, introduced to deal with intra-cellular delay ( § III.B), from two

perspectives:

Communication Delay -Because every RAO is longer in case of differential delay, resource allocation is delayed. Simulations show that on a single communication, the impact on the duration of the communication is negligible -of the range of the differential delay. On the other hand, it is interesting to look at the impact of the differential delay when the cell load is increased.

Aggregated Cell Throughput -The additional resources taken by the NPRACH reduce the capacity of the cell according to Table II. Indeed, as explained in Section. II, it is expected to observe a degradation of performance due to guard times and the increase of the CP size. From Eq. 4, we obtain a linear loss with respect to guard times. However our results reveal that the relative throughput loss is higher than expected. This is due to a snowball effect: resource allocation is optimized for a segmentation of power of 2, resulting from a) the grant allocation in NPDCCH period2 and b) delay parameter in grant for NPUSCH can only take a value in {8,16,32,64} ms. These findings are crucial for dimensioning the size of the satellite beams.

C. Propagation Delay Analysis

In this section, we consider the trade-off between the delay and the spectral efficiency as function of the target BLER.

1) Delay depending on cell type: Figure 9 shows the delay of the communication according to the cell type. GEO cells add the effects of transmission delay with each new message exchange and poor coverage conditions. Steps appear when a longer Transport Block is allocated without increasing the average number of messages. The slope at these steps reflects coverage conditions alone.

2) BLER Selection: Impact on the communication delay: Figure 10 points to an interesting finding. For several decades, cellular standards have used a Block Error Rate of 10 -1 which optimizes the delay in a terrestrial setting. However, the balance between repetition and re-transmission is quite different in a geostationary satellite environment. Extreme propagation times encourage the reduction of re-transmissions (NACK) in favour of repetitions (MCS). So we found a path towards reducing the communication delay by 10% with a BLER configuration of 10 -2 . We can observe steeper slopes for strong BLERs (proof of the robustness of the communication), but fewer messages are sent on average. Fig. 10: Delay of communications depending on robustness (BLER) and payload. The optimum configuration for latency is found around a BLER of 10 -2 . A value all the more interesting knowing that the targeted BLER in terrestrial deployment is 10 -1 .

An interesting question is whether the results of Figure 10 are still valid when increasing the cell load. To find out if a 10 -2 is always preferable, we have increased the number of new communications per second, which leads to two types of message failure:

• Collision: when choosing random preambles during the Access Phase. • Congestion: resources starvation on allocated channels during the Data Phase. We can see the load is significantly increasing the communication time in Figure 11. Interestingly, we notice that the conclusions drawn from Figure 10 still hold with higher loads -the use of a 10 -2 BLER always leads to lower communication delays. Note that the data is traced with a minimum success rate of 99% hence the absence of values for high loads.

Impact on the cell capacity: Surprisingly, Figure 12 shows a higher system capacity in terms of aggregated useful bits (in uplink) for a BLER of 10 -2 . In the terrestrial case, a targeted BLER of 10 -1 is considered to be the most efficient. Our result is explained by a) an excellent distribution of SNR considered in 3GPP (Figure 8 from [START_REF] Gpp | Technical specification group radio access network; solutions for new radio (nr) to support non-terrestrial networks (ntn) (release 16)[END_REF]) and b) the fact that we used a 15kHz transmission bandwidth. We therefore recommend to favour small bandwidth transmissions if a configuration with a 10 -2 BLER is targeted.

In order to understand truly Figure 12, it is worth remembering that a communication fails for two reasons. Either it collides during the Access Phase in the NPRACH or it lacks resources (congestion) during the Data Phase. This is why we have plotted Figure 13, it shows that the channel limiting the capacity of the cell is not the same depending on the size of the payload. Three different situations can be noticed:

• Large Payloads: above 3000 Bytes. NPUSCH limits the cell capacity. This is the channel impacted the most when payload increases. • Medium Payloads: around 1000 Bytes. For every communication, we assumed a connection setup. This connection setup induces traffic on the different channels and especially on the control channel. This is the resource starvation in the NPDCCH which is the cause of the capacity reduction. • Small Payloads: under 100 Bytes. To evaluate the use of the NPRACH, the random access theory must be used. NPRACH is a Slotted Aloha process and therefore the channel is at its maximum potential when it is used at 36.7% [START_REF] Tanenbaum | Computer Networks[END_REF] , above this value, the collisions are counterproductive. So on Figure 13, we see that 100 Bytes payload per communication is the balance point where collisions on the NPRACH become more prevalent than the lack of resources in the NDPCCH. I.

36.7

Fig. 13: Occupancy of the spectral resources when the cell reaches its maximum utilization. Depending on the payload size the resource starvation does not occur on the same channel.

In the light of these results, it seems necessary to configure the different channels according to the type of service needed. For instance, the ratio of NPDCCH in the downlink could be increased in the case of mainly UL traffic: a) it will increase the number of possible connection setups and b) NPDSCH performance will not be impacted as we show the margin in its spectral occupancy.

V. RELATED WORK

The Narrowband IoT has already been the subject of satellite studies. In a LEO context, the authors of [START_REF] Kodheli | Resource allocation approach for differential doppler reduction in nbiot over leo satellite[END_REF] propose a technique to solve the problem raised by the differential Doppler shift between users of the same cell. Their solution is to divide the cell into sub-parts with comparable Doppler effects in order to cluster resource allocation. On the other hand, in [START_REF] Cluzel | 3gpp nb-iot coverage extension using leo satellites[END_REF], the authors studied the performance of NB-IoT when considering only random access slots. NPRACH and NPUSCH are mixed up and therefore there is no resource allocation. The interest is that the effects of Doppler (non-GEO cases) are not to be taken into account. On the downside, it is necessary to deal the the possibility of collisions between data packets. The authors therefore studied the performance of Coherent Combining on the NB-IoT waveform in a LEO satellite context.

In this work we considered 3 coverage classes with each one a modulation and a number of repetitions applied for all the devices of the class. In reality, however, the MODCODs allocations are fine tuned according to the SNR of the UEs and the load of the cell. This work is being undertaken by the authors of [START_REF] Mousavi | Lte physical layer: Performance analysis and evaluation[END_REF] for LTE communications, i.e., 4G. Furthermore, we have considered the backoff and the number of connection attempts constant throughout a scenario, but [START_REF] Chelle | Adaptive load control for iot based on satellite communications[END_REF] shows that, in a satellite scenario, a real-time adjustment of these parameters is required to optimize the cell throughput. The authors use the information available at the base station (current load and number of random access collisions) to predict the number of connections and the future load in order to optimize the cell configuration.

VI. CONCLUSION

Using terrestrial cellular technologies for satellite systems is traditionally considered as very challenging. However, the particularities of NB-IoT -repetitions, narrow band signal, low latency and throughput sensitivity -make it uniquely positioned to break the mold. Furthermore, 5G promises to implement software separation of network equipment in order to enable the co-existence of the different services on the same infrastructure. In this context, NB-IoT by satellite fits perfectly as one of the RANs meeting IoT-5G requirements that the terrestrial technologies will have difficulty fulfilling: global coverage and no roaming. As a result, there is a significant momentum around the specification of the "Non Terrestrial Network" at 3GPP, as illustrated by the technical reports TR.38811 and TR.38821 [START_REF] Gpp | Technical specification group radio access network; study on new radio (nr) to support non-terrestrial networks(release 15)[END_REF][START_REF] Gpp | Technical specification group radio access network; solutions for new radio (nr) to support non-terrestrial networks (ntn) (release 16)[END_REF].

After introducing the challenges arising from the use of 5G cellular technology on a geostationary satellite, we studied the mechanisms to address those related to delay. Our evaluation quantified the relative loss incurred by the use of the geostationary satellite for an NB-IoT cell. The results show how much the delay spread inside a beam is bringing down the performance, the advantage of using the narrowest possible beams is quite clear. The study of the impact of the target Block Error Rate selection on cell performance is also very interesting. In particular, the data revealed a different optimum for the trade-off between re-transmission and repetition concerning GEO satellite. In order to optimize the communication delay and the spectral efficiency, a target BLER of 10 -2 is preferable to a target BLER of 10 -1 . This is an especially interesting discovery as it results from both the use of NB-IoT-specific single-tone transmission and homogeneous SNR distribution of GEO satellite.

Fig. 1 :

 1 Fig. 1: NB-IoT -Uplink Frame

Fig. 3 :Fig. 4 :

 34 Fig. 3: Differential delay effect

Fig. 5 :

 5 Fig. 5: Error free HARQ process for 2 differents BLER selections.

Fig. 6 :

 6 Fig. 6: BLER impact on the HARQ process in the case of an error on the UE with the least robust communication.

Fig. 7 : 4 Fig. 8 :

 748 Fig. 7: Uplink BLock Error Rate curves depending on Signal to Noise Ratio. Modulation and Coding Scheme (MCS) is varying from index 0 to index 12 (multi-tone transmission).

Fig. 9 :

 9 Fig. 9: Delay of communications from first connection attempt to last payload bytes sent, depending on payload and cell type. The differences are due to coverage and round trip delay. Data plotted for BLER = 10 -1 .

1 BLER = 10 - 2 Fig. 11 :

 110211 Fig. 11: Delay of communications from first connection attempt to last payload bytes sent, depending on spectral occupancy and BLER.

1 BLER = 10 - 1 BLER = 10 - 2 BLER = 10 - 3 BLER = 0. 5 Fig. 12 :

 1101102103512 Fig. 12: The impact of the chosen BLER on the capacity of the cell in terms of communication per second and total cell throughput. Settings in TableI.

TABLE I :

 I Common Settings

		Parameter	Setting
		Backoff value	1024 ms
		UE Power Class	23 dBm
		Max number of attempts	8
		User-Plane Optimization	Activate
	Channels		CE 0	CE 1	CE 2
		UL SNR Thresholds (dB)		7.4	5.6
		Number of repetitions -Nrep	1	2	4
	NPRACH	Number of subcarriers -Nsc	12	12	12
		Periodicity (ms)	320	160	320
		DL SNR Thresholds (dB)		3.0	1.6
	NPDCCH	Nrep Ratio in Downlink (1/G)		1	2 25%	4

TABLE II :

 II Differential Delay impact on Cell Performance

	Beam Size in km	< 100	500	1000	3500
	Differential Delay -δ	< 267µs	4ms	7ms	10ms
	Throughput in NPUSCH from simu. (kbits.s -1 )	177.6	154.3	138.6	114.0
	Relative Loss	ø	12.9%	22.3%	33.8%
	Theoritical Loss	ø	12.5%	21.8%	31.2%

Rel. 15 enables a cell radius of up to 120 km through the use of 1.25 kHz preambles and 0.8 ms CPs.

The period of NPDCCH, T, is calculated such that T = G • max(Nrep) in ms according to[START_REF]Technical specification group radio access network; evolved universal terrestrial radio access (e-utra)[END_REF]-TableIpresents the settings for our simulations.

We believe that our findings could be a useful input to the work on the specification of the NB-IoT deployment on satellite, which is expected to start in the first quarter of 2021.