Raphaël Naves

Gentian Jakllari

Hicham Khalifé

Vania Conan

André-Luc Beylot

A Physical-Layer Network Coding Aware Distributed Scheduling Policy

Keywords: Physical-Layer Network Coding, scheduling, multi-hop networks

Physical-Layer Network Coding (PLNC) was first introduced as a solution to increase the throughput in simple bidirectional communication schemes. Unlike most wireless communication techniques which try to avoid collisions, PLNC allows two simultaneous transmissions to a common receiver. In this work, we propose a MAC layer distributed and realistic scheduling policy targeting PLNC based networks. In order to easily operate in large ad-hoc networks, our solution is completely decentralized and runs in constant time. By basing the transmission priority of every node on the queue sizes of its local neighbors and PLNC opportunities, our solution ensures high throughput when compared to classical interferencefree scheduling. Both our theoretical analysis corroborated by our simulation results highlight that the proposed algorithm outperforms existing scheduling policies with throughput gains of around 35%.

I. INTRODUCTION

The exponential growth in the exchanged data volumes in wireless networks as well as the increasing density of wireless deployments call for new interference mitigation strategies. In this context, the Physical-Layer Network Coding (PLNC) [START_REF] Zhang | Hot topic: physical-layer network coding[END_REF] is a candidate to enhance the network performance by allowing simultaneous transmissions (of multiple nodes) over the same time/frequency resource. It was originally proposed in [START_REF] Katti | Embracing wireless interference: Analog network coding[END_REF] as a solution to increase the throughput of a two way relay channel communication (TWRC). In this simple scenario, two nodes A and B exchange a packet mutually through the same relay R (Fig. 1). Unlike most wireless communication techniques which try to avoid collisions, PLNC allows simultaneous transmissions of two messages to the shared relay. Therefore A and B can transmit in the same time their packet (p 1 and p 2 respectively) to R. By decoding the two signals, naturally mixed at the physical level, R retrieves at the bit level a coded packet p 3 which is a linear combination of p 1 and p 2 . In the second step, R sends the multicast coded packet p 3 to the two end users, exploiting the broadcast nature of wireless medium. A and B can extract their intended message removing their contribution to the received packet thanks to a reverse operation with the message sent in the first slot. In this simple TWRC scenario, the Physical-Layer Network Coding theoretical throughput gains reach 100% and 50% compared to classical transmissions and traditional well known Network Coding [START_REF] Katti | Xor's in the air : Practical wireless network coding[END_REF], respectively. This gain comes at the price of strict While major efforts focus on designing a physical layer able to efficiently support this interference management technique [START_REF] Lu | Realtime implementation of physical-layer network coding[END_REF] [START_REF] Xie | The feasibility of mobile physical-layer network coding with bpsk modulation[END_REF], we propose in this work the first PLNC aware lowcomplexity distributed scheduling policy with provable efficiency. Our solution ensures network stability by scheduling nodes based on their queue sizes whereby a higher priority is given to nodes with larger queues. We furthermore integrate in this priority estimation, the ability of each node to exploit PLNC transmissions i.e. its participation in a TWRC transmission. More generally, our scheduling favors Physical-Layer Network Coding transmissions while in the same time guaranteeing the stability of queues for legacy communications. This achieved while operating in a distributed fashion, with a reasonable information exchange between nodes.

We have evaluated theoretically the proposed approach and computed the lower bound gains of our scheduling policy compared to classical interference free solution. We have also conducted realistic simulations, showing that our scheduling, by exploiting PLNC, offers close to optimal performance in some situations. It also achieves up to 35% throughput gain when compared to the reference scheduling introduced in [START_REF] Joo | Performance of random access scheduling schemes in multi-hop wireless networks[END_REF].

The remainder of the paper is structured as follows: In Section II, we give an overview on previous work on scheduling and Physical-Layer Network Coding in large multi-hop networks. We detail in III the designed scheduling algorithm, comparing its theoretical efficiency to a state-of-theart scheduling policy. Simulations of Section IV underline the throughput gains achieved with our scheduling policy in realistic environments. Section V concludes this paper and describes future research perspectives.

II. RELATED WORK

Scheduling techniques for wireless networks have already attracted a lot of attention from the research community. Jain et al., propose in [START_REF] Jain | Impact of interference on multi-hop wireless network performance[END_REF] a framework to determine the optimal scheduling for maximizing the total throughput of any network. However, its complexity and centralized operation mode render such solution hardly usable. To overcome these limitations, several scheduling policies have been designed. For instance, constant-time distributed random access algorithms are described in [START_REF] Lin | Constant-time distributed scheduling policies for ad hoc wireless networks[END_REF], [START_REF] Joo | Performance of random access scheduling schemes in multi-hop wireless networks[END_REF], [START_REF] Gupta | Low-complexity distributed scheduling algorithms for wireless networks[END_REF] and [START_REF] Joo | Queue-affectance-based scheduling in multi-hop wireless networks under sinr interference constraints[END_REF]. The main idea of these policies is to provide the channel to nodes with the largest queue lengths. In the proposed solutions, the time needed to schedule is independent of the size of the network, which makes them easier to implement in large multi-hop networks. More importantly, authors guarantee for each scheduling policy a bounded drift from the optimal scheduling. However, work have been realized for classical interference models such as the protocol interference model and the physical interference model which do not support PLNC transmissions.

The integration of PLNC in large multi-hop networks requires specific MAC layer modifications. Recently, a first access method adapted to PLNC concept has been designed in order to detect PLNC opportunities and trigger such transmissions [START_REF] Mao | Anc-era: Random access for analog network coding in wireless networks[END_REF]. However, this technique is based on Carrier Sense Multiple Access and the theoretical performance of such a mechanism is difficult to evaluate especially in a dense ad hoc environment.

III. SCHEDULING POLICY ADAPTED TO PHYSICAL-LAYER NETWORK CODING

A. A PLNC aware interference model

To elucidate the need for a novel interference model we use the simple example shown in Fig. 2. Three nodes, A, B, C, send packets to each other through a fourth node, R. With a traditional physical layer implementation, links (A, R), (B, R) and (C, R) interfere with each others and only one of them can be active at any point in time. When using PLNC, however, their ability to coexist depends on the nature of the transmitted packet. If A is transmitting a packet to R with B as final destination and B is transmitting a packet to R with A as final destination then links (A, R) and (B, R) can be active simultaneously (first step of the TWRC sequence). If, on the other hand, A is transmitting a packet to R with C as final destination and B is transmitting a packet to R with A as final destination, then links (A, R) and (B, R) do interfere.

Clearly, unlike traditional wireless networks in which interference between links depends only on the physics of the radio propagation, when using PLNC, link interference depends also on the traffic pattern. Therefore, we introduce the concept of logical link to model wireless networks using PLNC. Specifically, we model such a network as a graph G = (V, E, F, L), where V represents the set of nodes, E the set of physical links, F the set of traffic flows and L the set of logical links. In this model, a physical link is mapped to a set of logical links so as to capture the traffic dependent link interference. Going back to the example of Fig. 2, the physical link (A, R) is mapped to two logical links h and k, one for each flow generating from node A. Similarly, the physical link

(B, R) (resp. (C, R)) is mapped to one logical link v h (resp. v k ).
With this, we can say logical link h does not interfere with logical link v h but it does interfere with logical link v k . Similarly, k and v k do not interfere.

B. Scheduling mechanism overview

We consider a Time Division Multiple Access (TDMA) based network where time is divided into slots of unit length. Each slot is composed of two parts: a contention period used for allocating resources in a distributed manner and a transmission period for data communications (Fig. 3). The contention period is further divided into M mini-slots sized so as to allow the traditional RTS/CTS handshake to take place for the allocation of the following data transmission period. To protect both data and acknowledgment transmissions avoiding collisions and ensure stability of node queues, nodes rely on the RTS/CTS mechanism which we have modified to take into account the particularities of PLNC as follows.

In a given contention period mini-slot, a node wanting to access the channel will transmit a RTS with 3 possible precomputed probabilities if and only if one of the following these 3 conditions is satisfied: 1) The node has not overheard any RTS/CTS exchange during the previous mini-slots of this contention period (the channel is not yet reserved). 2) The node has heard a CTS but the particular reservation constitutes a PLNC opportunity for him (step 1 of the TWRC sequence, Fig. 1). In the latter case, the link still attempts a transmission in the following mini-slots with an updated probability, as explained in Section III-C. 3) The node has a multicast coded packet to transmit (i.e. a combination of 2 native packets, step 2 of Fig. 1) and has already sent a first RTS for one of the 2 destinations of this packet. In this particular case, the node can send another RTS to the second destination of the coded packet with a third possible probability (if no other RTS was heard before). Note that RTS are answered back with their corresponding CTS unless unexpected errors occur during the transmissions resulting in the reservation cancellation for this round.

One can easily observe that the pre-computed probabilities with which a node decides to transmit a RTS in a given mini-slot are the key parameters of the scheduling solution, accounting for contention and congestion control. Next we describe in detail how this probability is computed.

C. Access probability computation

From a broader perspective, our objective is twofold. Favoring the Physical-Layer Network Coding to increase the network throughput and second, ensure fairness and stability by giving higher priorities to nodes with larger queues. More importantly, both objectives are fulfilled in a distributed fashion.

At the beginning of time slot t, sources of each link l compute a probability x l (t) given by the following expression:

x l 1 (t) = δ l Q l (t) max k∈N 1 (l) i∈N 1 (k) δiQi(t) (1)
where Q l is the queue length of link l, δ l a normalizing parameter depending on link l, and N 1 (l) the set of one-hop neighbors of l, including l itself (refer to Fig. 4). Each link potentially involved in a PLNC transmission, computes another probability x l 2 (t) defined as follows:

x l 2 (t) = δ l Q l (t) max k∈Ns(l) i∈N 1 (k) δiQi(t) (2)
where N s (l) are the one-hop neighbors of l from the source side (see Fig. 4). Each link which is part of a multicast coded transmission computes another probability x l 3 (t) defined as follows:

x l 3 (t) = δ l Q l (t) max k∈N d (l) i∈N 1 (k) δiQi(t) (3)
where N d (l) is the set of links such that the destination node of l acts either as transmitter or receiver (one-hop neighbors of l from the destination side, as shown in Fig. 4).

To define the aggressiveness of our strategy we introduce β, whereby the higher the β value the more nodes are daring during the contention slot. Given β ∈ M -1), during the contention period (recall that M is the number of minislots during the contention period), sources of each link l will transmit a RTS in a given mini-slot using the above probabilities as follows:

1) The source node that has not already sent a RTS and has not heard a RTS/CTS exchange will send a RTS with probability equal to β

x l 1 (t) M .
2) The source node that has not already sent a RTS but has heard a RTS/CTS exchange letting him know that there is a PLNC opportunity, will send a RTS with probability equal to β

x l 2 (t) M .
3) The source node that has already sent a RTS to a first destination will send a second RTS to the second destination with probability equal to β

x l 3 (t)
M if the pending transmission is a coded multicast transmission. Remark 1: Unlike state of the art solutions, such as ANC-ERA [START_REF] Mao | Anc-era: Random access for analog network coding in wireless networks[END_REF], PLNC and multicast coded transmissions are not automatically triggered once one of the two corresponding links wins the access. To ensure fairness between TWRC sequence transmissions and classical interference-free transmissions, a link always competes for channel access with a probability taking into account its competing links queue states. Remark 2: Our scheduling policy gives higher priority to TWRC sequences: once a link that is part of a PLNC transmission wins the channel using the basic access probability, β

x l 1 (t)
M , the other link of the same scheme v l will attempt to gain channel access with an updated higher probability,

β x v l 2 (t) M (β x v l 2 (t) M > β x v l 1 (t) M ).
Similarly, a node wanting to transmit a multicast coded packet, will attempt to send a first RTS to one of the intended receivers using the basic probability, β

x l 1 (t)
M . If this succeeds, the second RTS to the second intended receiver will be sent on v l with an updated higher probability, β

x v l 3 (t) M > β x v l 1 (t)
M . Not only this makes sense in terms of favoring high throughput communication but also in terms of channel access. Once a link in a TWRC scheme has won channel access, the concurrent node area for the second link of the same scheme shrinks automatically.

D. Theoretical analysis

In order to precisely evaluate the theoretical performance of the designed algorithm, we estimate the minimum probability for a node to successfully transmit during a data slot, or equivalently win the access competition. We then compare the obtained lower bound to the same efficiency marker (baseline) computed for one of the reference scheduling policy without Physical-Layer Network Coding in the literature [START_REF] Joo | Performance of random access scheduling schemes in multi-hop wireless networks[END_REF].

We denote by P l (S m ) the probability of a link l to win the channel access race in the mini-slot m. We have:

P l (Sm) = P 1 l (Sm) + P 2 l (Sm) (4)
where P 1 l is the probability for link l to win the channel before the link v l implicated in the same PLNC or multicast coded transmission and P 2 l the probability to win after v l . Obviously, for traditional interference-free transmissions which do not belong to any TWRC schemes, P 2 l (S m ) = 0. We define N (l) (respectively Ň (l)) as the links set in N 2 (l) (l two-hop neighbors) such that their PLNC corresponding link (respectively multicast corresponding link) does not belong to N 2 (l). In Fig. 4 example, h 1 ∈ N (l) since its relative PLNC opportunity (v h1 ) is not part of N 2 (l), while h 2 ∈ Ň (l), because the link implicated in the same multicast coded transmission (v h2 ) is outside N 2 (l). We denote by N (l) the complement of

Ň (l) ∪ N (l) in N 2 (l) (N 2 (l) = N (l) ∪ Ň (l) ∪ N (l)).
The probabilities to win access at mini-slot 0 and mini-slot 1 can be expressed as:

P 1 l (S0) = β x l 1 M k∈N 2 (l) (1 -β x k 1 M ) P 1 l (S1) ≥ β x l 1 M k∈N 2 (l) (1 -β x k 1 M ) k∈N (l)∪l (1 -β x k 1 M ) k∈ N (l) 1 -β x v k 1 M β x k 2 M + (1 -β x v k 1 M )β x k 1 M k∈ Ň (l) 1 -β x v k 1 M β x k 3 M + (1 -β x v k 1 M )β x k 1 M ≥ β x l 1 M k∈N 2 (l) (1 -β x k 1 M ) k∈N (l)∪l (1 -β x k 1 M ) k∈ N (l) (1 -β x k 2 M ) k∈ Ň (l) (1 -β x k 3 M ) since x l 1 ≤ x l 2 and x l 1 ≤ x l 3 .
We simplify in the following the equations and rename the union of N (l) and Ň (l) in Ñ (l) ( Ñ (l) = N (l) ∪ Ň (l)). Then, for each link l in Ñ (l), we define the probability x l v as equal to x l 2 or x l 3 depending on whether l is in N (l) or Ň (l). Similarly, we can show that for any mini-slot m ∈ [0, ..., M -1]:

P 1 l (Sm) ≥ β x l 1 M   k∈N (l)∪l (1 -β x k 1 M ) k∈ Ñ (l) (1 -β x k v M )   m+1 since 1 - x k 1 M < 1.
As the access probability at any mini-slot of the contention period P 1 l (S) =

M -1 m=0 P 1 l (S m ), we get:

P 1 l (S) ≥ β x l 1 M M -1 m=0   k∈N (l)∪l (1 -β x k 1 M ) k∈ Ñ (l) (1 -β x k v M )   m+1
As (1β

x l 1 M ) m+1 ≥ (1 -β(m + 1)
x l 1 M ) and

(1ux k ) is decreasing in u, we have :

P 1 l (S) ≥ β x l 1 M M -1 m=0 k∈N (l)∪l (1 -β(m + 1) x k 1 M ) k∈ Ñ (l) (1 -β(m + 1) x k v M ) ≥ β x l 1 M M 0 k∈N (l)∪l (1 -β(m + 1) x k 1 M ) k∈ Ñ (l) (1 -β(m + 1) x k v M ) dm ≥ βx l 1   1 0 k∈N (l)∪l (1 -βx k 1 u) k∈ Ñ (l) (1 -βx k v u) du - 1 M   ( 5
)
This integral is hard to calculate because of the product term inside. Nevertheless, by comparing the derivatives, we can show that, when

K k=1 x k ≤ B : K k=1 (1 -ux k ) ≥ (1 -u) B (6)
Then, by finding an upper bound to h∈N (l)∪l x h 1 + h∈ Ñ (l) x h v , we are able to simplify [START_REF] Xie | The feasibility of mobile physical-layer network coding with bpsk modulation[END_REF].

To do so, we exploit the following property:

h∈N (l)∪l x h 1 + h∈ Ñ (l) x h v ≤ k∈N 1 (l)     h∈N 1 (k) h∈N (l)∪l x h 1 + h∈N 1 (k) h∈ Ñ (l) x h v     (7)
Additionally, for all k ∈ N 1 (l), by definition, we have:

h∈N 1 (k) h∈ Ñ (l) x h v = h∈N 1 (k) h∈ Ñ (l) δ h Q h max i∈Ns(h) or i∈N d (h) j∈N 1 (i) δjQj Since k ∈ N s (h) (resp. k ∈ N d (h)) when h ∈ N (l) (resp. h ∈ Ň (l)
), as shown in Fig. 4, we get the following inequality:

h∈N 1 (k) h∈ Ñ (l) x h v ≤ h∈N 1 (k) h∈ Ñ (l) δ h Q h j∈N 1 (k) δjQj (8)
Similarly, we can show that:

h∈N 1 (k) h∈N (l)∪l x h 1 ≤ h∈N 1 (k) h∈N (l)∪l δ h Q h j∈N 1 (k) δjQj (9)
Combining ( 8) and ( 9), we get:

h∈N 1 (k) h∈N (l)∪l x h 1 + h∈N 1 (k) h∈ Ñ (l) x h v ≤ 1 ∀k ∈ N1(l) (10)
Then, ( 7) and [START_REF] Joo | Queue-affectance-based scheduling in multi-hop wireless networks under sinr interference constraints[END_REF] give the expected upper bound: [START_REF] Mao | Anc-era: Random access for analog network coding in wireless networks[END_REF] where |N 1 (l)| is the cardinality of N 1 (l). Finally, using ( 5) and ( 11), we derive P 1 l (S) lower bound:

h∈N (l)∪l x h 1 + h∈ Ñ (l) x h v ≤ |N1(l)| (
P 1 l (S) ≥ βx l 1 1 0 (1 -u) β|N 1 (l)| du - 1 M ≥ x l 1 ( β β|N1(l)| + 1 - β M ) (12)
This lower bound corresponds to the result obtained in [START_REF] Joo | Performance of random access scheduling schemes in multi-hop wireless networks[END_REF]. Therefore, with Physical-Layer Network Coding a link not belonging to a TWRC scheme, is active at least as often as in the classical reference policies. In other words, adding the possibility of triggering PLNC and multicast coded transmissions does not affect the classical interference-free transmissions performance, ensuring the first constraint of our scheduling algorithm.

For links being part of a TWRC scheme, gains of Physical-Layer Network Coding are provided by the contribution of P 2 l (S), the probability of a link to win the channel after its corresponding link (recall that P 2 l (S) equals 0 for interferencefree transmissions). Thanks to a similar reasoning, we can show that for any link involved in the two steps of TWRC sequences, we have: where

P 2 l (S) ≥ x l 2 x v l 1 ( β β|N1(l, v l )| + 1 - β M ) (13)
|N 1 (l, v l )| is the cardinality of N 1 (l) ∪ N 1 (v l ).
Eq. ( 13) provides the worst case gain ensured by our scheduling policy with the new interference model. As expected, for any link involved in a TWRC sequence, the gain mostly depends on the ability of its PLNC corresponding link to access the channel; The bigger this probability, the higher the gains of TWRC sequences.

IV. PERFORMANCE EVALUATION THROUGH SIMULATIONS

After theoretically deriving the lower bound gains for our strategy, we simulate our scheduling policy using a discrete event simulator over the two topologies of Fig. 5. We compare the obtained results to the low-complexity distributed scheduling policy introduced in [START_REF] Joo | Performance of random access scheduling schemes in multi-hop wireless networks[END_REF]. In the latter solution, all the sources compete with the probability β

x l 1 M given in equation ( 1) and PLNC opportunities are not exploited. We also compare with the centralized Greedy Maximal Matching (GMM) algorithm under the new interference model (PLNC transmissions authorized). Although unusable in practice, GMM is known for being close to the optimal scheduling and therefore can serve as a good benchmark.

A. Performance gains in a basic topology

We first estimate the scheduling policy benefits on the basic topology depicted in Fig. 5(a). In the proposed scenario, two bidirectional flows forming a TWRC scheme are established between nodes 3 and 5. In parallel, nodes 2 and 7 are sources of two single-hop flows with classical interferencefree transmissions. In our simulations, we consider identical link capacity with each node sending at most 1 packet per slot. The parameter δ l of our algorithm is set to 1 for each link of the network. We also assume that each node has always exact knowledge of its neighbors queue states. Finally, the contention slot is divided into M = 60 mini-slots.

We first evaluate the queue lengths of each node belonging to the two opposite flows (3→5, 5→3) while varying the 4 traffic streams rates (uniform packet arrival). A traffic load value of 0.25 packet per slot means that each source receives on average 1 packet every 4 slots from the higher layers. We carry out simulations for two different values of β (the aggressiveness of the strategy): β = 2 and β = 10. For each flow load value, we carry out 20 simulations and we show in Fig. 6 the average queue lengths after 2000 slots of simulation time. For β = 10, our scheduling policy keeps the system stable (few packets in queues) for any load less than 0.3 packets per slot, whereas the baseline algorithm [START_REF] Joo | Performance of random access scheduling schemes in multi-hop wireless networks[END_REF] supports less load before losing its stability. This is due to the ability of our solution to exploit PLNC opportunities thus reducing the total load in the network. More importantly, our scheduling behavior is remarkably close to the GMM algorithm, known to offer near optimal performance. Finally, with β = 2, transmitters are less aggressive in the contention slot. This leads to worse bandwidth utilization than β = 10, explaining the relatively lower performance.

To assess the fairness between PLNC and classical interference-free transmissions, we evaluate queue lengths of the two single-hop flows (2→1, 7→6) in the same simulation environment. Results depicted in Fig. 7 highlight that classical transmissions are not negatively affected at all by neighboring PLNC transmissions. Moreover, some enhancement can be noticed since our algorithm keeps queue lengths smaller than the considered baseline. Indeed, since PLNC transmissions allow packets from the TWRC flows to be scheduled faster, it gives more channel access to classical transmissions.

B. Gains in a large topology

In order to validate our scheduling algorithm performance in a larger network, we simulate a grid topology of 30 nodes (Fig. 5(b)). Arrows between nodes illustrate all the instantiated flows. Once again, one part of the transmissions is implicated in TWRC schemes, leading to PLNC opportunities whereas the other part is constituted of classical interferencefree transmissions. All the simulation parameters are the same as before. Results depicted in Fig. 8 confirm that our scheduling policy outperforms Baseline in terms of stability for TWRC flows. Triggering PLNC transmissions allows to send more packets, draining the queues faster. Here again with β = 10, our strategy exhibits similar performance to the near optimal benchmark (GMM), mainly in terms of the stability breaking point. Nevertheless, a very competitive approach leads to a significant number of collisions during the contention period, explaining why the results are better with β = 10 than with β = 20.

In Fig. 9, we show the minimum, maximum and average throughput gains of the proposed algorithm compared to Baseline [START_REF] Joo | Performance of random access scheduling schemes in multi-hop wireless networks[END_REF] for flows implicated in TWRC schemes. To do so, we compare the number of received packets by each TWRC destination during the 2000 slots of simulation. At low loads, gains are close to zero because, under the two scheduling policies, all the injected packets are received by their destination. Nevertheless, average gains increase with the traffic load. They reach 35% when the packet arrival is 0.18 packets per slot. More interestingly, minimum and maximum per flow gains highlight that PLNC performance closely depends on the neighboring environment. In particular, minimum gains are obtained for bidirectional flows between nodes A and B (see Fig. 5(b)). Indeed, since they just have one interfering link on A side, classical interference-free transmissions are sufficient for supporting the lightly-loaded traffic. However, in denser traffic area, gains of the designed scheduling achieve 80% compared to the baseline.

Once again, PLNC gains would be less interesting in case of negative impact on traditional transmissions. For this reason, we also verify in Fig. 10 that queue lengths for traditional

V. CONCLUSION AND FUTURE WORK

We have proposed the first Physical-Layer Network Coding (PLNC) aware low-complexity distributed scheduling with verifiable efficiency. We have demonstrated that the theoretical performance of the proposed algorithm is in the worst case as good as state of the art solutions, clearly outperforming them when PLNC opportunities are available. Furthermore, by simulation, we have demonstrated that our solution outperforms a reference scheduling policy by around 35% in terms of throughput gains thanks to PLNC transmissions. It also guarantees that legacy interference-free transmissions are not negatively affected by these gains.

In the future, we plan to test the designed scheduling policy in our SDR testbed based on USRP devices.

Fig. 1 .

 1 Fig. 1. The Two Way Relay Model (TWRC) -2 steps (time-slots) illustration synchronization to guarantee the reception of perfectly aligned signals at the relay.While major efforts focus on designing a physical layer able to efficiently support this interference management technique[START_REF] Lu | Realtime implementation of physical-layer network coding[END_REF] [5], we propose in this work the first PLNC aware lowcomplexity distributed scheduling policy with provable efficiency. Our solution ensures network stability by scheduling nodes based on their queue sizes whereby a higher priority is given to nodes with larger queues. We furthermore integrate in this priority estimation, the ability of each node to exploit PLNC transmissions i.e. its participation in a TWRC transmission. More generally, our scheduling favors Physical-Layer Network Coding transmissions while in the same time guaranteeing the stability of queues for legacy communications. This achieved while operating in a distributed fashion, with a reasonable information exchange between nodes.We have evaluated theoretically the proposed approach and computed the lower bound gains of our scheduling policy compared to classical interference free solution. We have also conducted realistic simulations, showing that our scheduling, by exploiting PLNC, offers close to optimal performance in some situations. It also achieves up to 35% throughput gain when compared to the reference scheduling introduced in[START_REF] Joo | Performance of random access scheduling schemes in multi-hop wireless networks[END_REF].The remainder of the paper is structured as follows: In Section II, we give an overview on previous work on scheduling and Physical-Layer Network Coding in large multi-hop networks. We detail in III the designed scheduling algorithm, comparing its theoretical efficiency to a state-of-theart scheduling policy. Simulations of Section IV underline the throughput gains achieved with our scheduling policy in realistic environments. Section V concludes this paper and describes future research perspectives.

Fig. 2 .

 2 Fig. 2. Logical links example with 4 established flows : A→B, B→A, A→C, C→A

Fig. 3 .

 3 Fig. 3. Slot divided in a contention period of M mini-slots and a data transmission period

Fig. 4 .

 4 Fig. 4. Graph notation illustration

Fig. 5 .

 5 Fig. 5. Studied topologies : a) Basic topology with 4 established flows : 2→1, 7→6 (traditional transmissions) and 3→5, 5→3 (TWRC scheme) and b) Grid topology with several flows

Fig. 6 .Fig. 7 .

 67 Fig. 6. Total Queue lengths for TWRC flows (3→5 and 5→3)

Fig. 8 .Fig. 9 .

 89 Fig. 8. Total queue lengths for TWRC flows of the grid topology

Fig. 10 .

 10 Fig.10. Impact on classical interference-free transmissions of the grid topology evaluated by comparing their total queue lengths transmissions do not exceed the values obtained with the reference scheduling policy.