, node u has to know if there is another arc e sending and interfering with e. Notice that, necessarily, node u knows if arc e = (u, v ) is sending. However, u does not know if there are other arcs interfering with it. Therefore, order to apply Algolog at the node level, and similarly to decide if an arc e = (u, v) not sending becomes PI (potentially inactive) or stays U)
, On the other hand, if u hears a signal from some node w, then it needs to determine whether or not a signal is aimed to it. From now on, we assume (Hypothesis H) that if
, We now show how, under H, one can emulate, in the primary node model, a mini-slot i of sending on the arc e = (u, v) by dividing it in two sub-mini-slots, denoted by i 1 and i 2 , that is how one can emulate the behavior of lines 5-6 of AlgoLog. As a result, the overhead will only be multiplied by two. During sub-mini-slot i 1
, Sub-mini-slot i 1 : For each arc e = (u, v) such that s(e) = U and ? t,e (i) = 1, then node u sends a signal in the direction of node v
, Within the sub-mini-slot i 1 , if node u detects a signal from some node w, then it knows that arc e = (w, u) is sending and, therefore, interfering with all the arcs with origin u. It remains to deal with interference of an arc e = (u, v) with some arc e due to node v, that is Problem 2. To answer the problem we design sub-mini-slot i 2 as follows: Sub-mini-slot i 2 : ? Case 1: If in sub-mini-slot i 1 node v has sent a signal
, ? Case 2: If in sub-mini-slot i 1 node v has not sent a signal, but has heard a signal from at least two of its neighbors, then v sends a signal (busy) to all of its neighbors
If in sub-mini-slot i 1 node v has not sent any signal and has heard a signal from exactly one of its neighbors (say node u), then v sends a signal (busy) to all of its neighbors, vol.3 ,
, Emulating lines 7-10 of AlgoLog After the two sub-mini-slots i 1 and i 2 , a node u can determine for each arc e = (u, v) if there is an arc sending and interfering with e. That happens exactly in the following three cases: ? Case a: In sub-mini-slot i 1
, ? Case b: In sub-mini-slot i 1 , node u hears a signal from some node w
, ? Case c: In sub-mini-slot i 2 , node u hears a signal (busy) from node v
, and in Case c e = (v, w) if the signal busy was sent in sub-mini-slot i 2 due to Case 1 or e = (w, v) if the signal busy was sent in sub-mini-slot i 2 due to Case 2 or Case 3. Furthermore, if we are not in one of Cases 1-3, then there is no arc interfering with e. Depending on what happens in sub-mini-slots i 1 and i 2 , a node u can know when there is an interference between an arc e = (u, v) and another arc e , so that it is able to make decisions which exactly emulate decisions taken in the link model (cf. lines 7-10 in Figure 2). More precisely, these three cases there is an arc e sending and interfering with e = (u, v), namely
, ? if e is not sending (i.e. ? t (f, i) = 0) and if there is an arc e sending and interfering with e
, ) and, so, are sending. In sub-mini-slot i 1 (Figure 16(b)), u 1 sends a signal to u 2, As an illustration of the above, consider the oriented grid displayed in Figure 16. Here, we assume that at the beginning of sub-mini-slot i, all the arcs are undetermined and five of them satisfy ? t,e (i) = 1 namely
, The state of an arc is represented by a dash line for PI (Potentially Inactive), a solid line for U (Undetermined), and Blue bold for A (Active). For each arc e = (u, v), the label 'case x' with x ? {a, b, c}
, Therefore, node u 1 changes the state of the arc (u 1 , u 4 ) from U to P I. For the arc (u 1 , u 2 ), there is no arc sending and interfering with it. Therefore, node u 1 changes the state of the arc (u 1 , u 2 ) from U to A. Consider node u 2 . In sub mini-slot i 1 , it hears a signal from u 1 and so it knows, p.33
, This node hears a signal from u 2 in sub-mini-slot i 2 (Case 3 as u 2 heard in sub-min-slot i 1 a signal from u 1 ). Therefore, by Case c, u 3 knows that there is a sending arc
, Emulating lines 11-16 of AlgoLog We can also emulate the synchronization slot (lines 11-12 of AlgoLog in Figure 2) with two submini-slots identical to the sub-mini-slots i 1 and i 2 . Each node u will know, exactly as above, for an arc e if there is an arc e sending and interfering with it (Cases a,b,c) and, therefore
, ) is active) sends a signal of synchronization to u 2 . Then, in the second sub-mini-slot of synchronization, u 1 sends a signal busy (Case 1) and u 2 sends a signal busy
, ) from P I to I, and u 4 will change the state of (u 4 , u 1 ) from P I to I as for these two arcs there is an interference with
Stochastic Geometry and Wireless Networks, vol.II, 2010. ,
URL : https://hal.archives-ouvertes.fr/inria-00403039
The distance-2 matching problem and its relationship to the mac-layer capacity of ad hoc wireless networks, J. Selected Areas in Communication, vol.22, issue.6, pp.1069-1079, 2004. ,
A distributed scheduling algorithm for wireless networks with constant overhead and arbitrary binary interference, ACM SIGMETRICS Performance Evaluation Review, vol.38, pp.345-346, 2010. ,
URL : https://hal.archives-ouvertes.fr/inria-00505519
Data gathering in wireless networks, Graphs and Algorithms in Communication Networks, Studies in Broadband, Optical, Wireless and Ad Hoc Networks, pp.357-377, 2010. ,
URL : https://hal.archives-ouvertes.fr/hal-00342958
Markov Chains, Gibbs Fields, Monte Carlo Simulation, and Queues, Texts in Applied Mathematics, vol.31, 1999. ,
Enabling distributed throughput maximization in wireless mesh networks: a partitioning approach, Proc. ACM MobiCom, pp.26-37, 2006. ,
Distributed link scheduling with constant overhead, IEEE/ACM Transactions on Networking, vol.17, issue.5, pp.1467-1480, 2009. ,
Induced matchings, Discrete Applied Mathematics, vol.24, issue.1-3, pp.97-102, 1989. ,
Throughput and fairness guarantees through maximal scheduling in wireless networks, IEEE Transactions on Information Theory, vol.54, issue.2, pp.572-594, 2008. ,
A queue-aware scheduling algorithm for multihop relay wireless cellular networks, Proc. IEEE Mobile WiMAX Symposium, pp.63-68, 2009. ,
, Graph Theory (Graduate Texts in Mathematics, 1997.
Polynomial complexity algorithms for full utilization of multi-hop wireless networks, Proc. IEEE INFOCOM, pp.499-507, 2007. ,
Edge-colourings of graphs, Research Notes in Mathematics, vol.16, 1977. ,
Low-complexity distributed scheduling algorithms for wireless networks, IEEE/ACM Transactions on Networking, vol.17, issue.6, pp.1846-1859, 2009. ,
The capacity of wireless networks, IEEE Transactions on Information Theory, vol.46, issue.2, pp.388-404, 2000. ,
Distributed random access algorithm: scheduling and congestion control, IEEE Transactions on Information Theory, vol.56, issue.12, pp.6182-6207, 2010. ,
A distributed CSMA algorithm for throughput and utility maximization in a wireless networks, Proc. 46th Allerton Conference on Communication, Control, and Computing, 2008. ,
Approaching throughput-optimality in distributed CSMA scheduling algorithms with collisions, IEEE/ACM Transactions on Networking, vol.19, issue.3, pp.816-829, 2011. ,
On the complexity of bandwidth allocation in radio networks, Theoretical Computer Science, vol.406, issue.3, pp.225-239, 2008. ,
URL : https://hal.archives-ouvertes.fr/hal-00342875
End-to-end packet-scheduling in wireless ad-hoc networks, Proc. ACM-SIAM SODA, pp.1021-1030, 2004. ,
Matching Theory, Annals of Discrete Mathematics, vol.29, 1986. ,
Maximum weighted matching with interference constraints, Proc. FAWN, 2006. ,
Markov Chains and Stochastic Stability, 1993. ,
A constructive proof of vizing's theorem, Information Processing Letters, p.41, 1992. ,
Maximizing throughput in wireless networks via gossiping, Proc. ACM SIGMETRICS -IFIP PERFORMANCE, vol.34, pp.27-38, 2006. ,
Network adiabatic theorem: an efficient randomized protocol for contention resolution, Proc. ACM SIGMETRICS -IFIP PERFORMANCE, vol.37, pp.133-144, 2009. ,
Distributed link scheduling with constant overhead, Proc. ACM SIGMETRICS, pp.313-324, 2007. ,
Log-weight scheduling in switched networks, Queueing Systems (QUESTA), vol.71, pp.97-136, 2012. ,
Randomized scheduling algorithm for queueing networks, Ann. Appl. Probab, vol.22, issue.1, pp.128-171, 2012. ,
Medium access using queues, Proc. IEEE 52nd Annual Symposium on Foundations of Computer Sciences (FOCS), 2011. ,
Switched networks with maximum weight policies: Fluid approximation and multiplicative state space collapse, Ann. Appl. Probab, vol.22, issue.1, pp.70-127, 2012. ,
On the accuracy of interference models in wireless communications, ICC 2016, IEEE international Conference on Communications, pp.1-6, 2016. ,
Interference model similarity index and its applications to mmwave networks: Extended version, IEEE Transactions on Wireless Communications, vol.10, p.2017 ,
Lingering issues in distributed scheduling, Proceedings of the ACM SIGMETRICS/International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS '13, pp.141-152, 2013. ,
URL : https://hal.archives-ouvertes.fr/hal-01888052
NP-completeness of some generalizations of the maximum matching problem, Information Processing Letters, vol.15, issue.1, pp.14-19, 1982. ,
Scheduling and performance limits of networks with constantly changing topology, IEEE Transactions on Information Theory, vol.43, issue.3, pp.1067-1073, 1997. ,
Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks, IEEE Transactions on Automatic Control, vol.37, issue.12, 1992. ,
Multiflows in multihop wireless networks, Proc. ACM MobiHoc, pp.85-94, 2009. ,
Queue length stability of maximal greeedy schedules in wireless networks, Proc. of Information Theory and Applications Inaugural Workshop, 2006. ,