, In mini-slot i 2 (Figure 16(c)), according to Case (1), us describe the two mini-slots for the oriented grid depicted in Figure 16. Here we suppose that at the beginning of mini-slot i, all the arcs are undetermined and five of them satisfy ? t,e (i) = 1 namely, vol.16
, There decisions are the following:-Case a: if in mini-slot i 1 node u hears a signal, then:-it changes the state of the arcs f with origin u such that s( f ) = U and ? t ( f , i) = 0 from U to PI, According to what happens in mini-slots i 1 and i 2 , the nodes take decisions which exactly emulate the decisions taken in the link model (lines 7-10)
heard a signal from any of its neighbors, but has sent signals to at least two of its neighbors then:-it changes the state of the arcs f with origin u such that s( f ) = U and ? t ( f , i) = 0 from U to PI.-it leaves the state of the arcs f with origin u such that s( f ) = U, mini-slot i 1 node u has not ,
, Case c: if in mini-slot i 1 node u has not heard a signal from any of its neighbors and has sent a signal only to node v, then:-u changes the state of all the arcs f different than (u, v) with origin u which necessarily satisfy s( f ) = U
, u, v) at U.-Case d: if in mini-slot i 1 node u has not sent a signal and has not heard a signal from any of its neighbors, then-if in mini-slot i 2 node u hears a signal sent by node w and if arc f = (u, w) satisfies s( f ) = U (necessarily ? t ( f , i) = 0, mini-slot i 2 node u hears a signal sent by node v it leaves the state of arc e =
, mini-slot i 2 node u has not heard a signal from node w and if arc f = (u, w) satisfies s( f ) = U (necessarily ? t ( f , i) = 0)
, In the proof, we describe the decisions taken by the nodes after the two mini-slots, for the oriented grid depicted in Figure 16. 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). The four cases correspond to arcs labeled case x ? {a, b, c, Proposition 4 proves the equivalence between AlgoLog and AlgoLogNodes
, Proposition 4 Under the primary node interference model, decisions taken by AlgoLogNodes after the two mini-slots i 1 and i 2 emulate the decisions taken by AlgoLog after mini-slot i, pp.7-10
, Throughout the proof, we focus on mini-slot i = 1,. .. , T , of slot t. Recall that under AlgoLogNodes mini-slot i is composed of the two (sub-) mini-slots i 1 and i 2
, e (i) = 1 then v has sent a signal in mini-slot i 1 and, from Case (1), in mini-slot i 2 , v has sent a signal to u so that, from Case (c), u leaves e undetermined, First, consider an arc e = (u, v) such that s(e) = U and ? t,e (i) = 1. Under AlgoLog, e sends a signal in the mini-slot i and from there two things may happen: (i) hears a signal from w and
, When (ii) occurs, we are in Case (c) above and u changes the state of e from U to A
) such that s( f ) = U and ? t, f (i) = 0. In AlgoLog, f does not send any signal in the mini-slot i and from there two things may happen: (i') f hears a signal from an arc f in I( f ) and it changes its state from U to PI or (ii') f does not hear any signal and its state remains in U ,
, When (i') occurs, we need to investigate four cases according to the origin or destination of f (i.e. either f has destination/origin u or w):-If there is an arc f = (w , u) with destination u satisfying s( f ) = U and ? t, f (i) = 1, then u hears in mini-slot i 1 a signal from w and so by Case
The distance-2 matching problem and its relationship to the mac-layer capacity of ad hoc wireless networks, Graphs and Algorithms in Communication Networks, Studies in Broadband, Optical, Wireless and Ad Hoc Networks, vol.II, pp.357-377, 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
Distributed link scheduling with constant overhead, IEEE/ACM Transactions on Networking, vol.17, issue.5, pp.1467-1480, 2009. ,
Enabling distributed throughput maximization in wireless mesh networks: a partitioning approach, Proc. ACM MobiCom, pp.26-37, 2006. ,
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. ,
On the stochastic matrices associated with certain queuing processes, Ann. Math. Statistics, vol.24, pp.355-360, 1953. ,
Edge-colourings of graphs, Research Notes in Mathematics, vol.16, 1977. ,
The capacity of wireless networks, IEEE Transactions on Information Theory, vol.46, issue.2, pp.388-404, 2000. ,
Low-complexity distributed scheduling algorithms for wireless networks, IEEE/ACM Transactions on Networking, vol.17, issue.6, pp.1846-1859, 2009. ,
Two mini-slots of AlgoLogNodes (that emulates AlgoLog) for an oriented grid network, vol.16 ,
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. ,
A constructive proof of vizing's theorem, Information Processing Letters, p.41, 1992. ,
Maximum weighted matching with interference constraints, Proc. FAWN, 2006. ,
Maximizing throughput in wireless networks via gossiping, Proc. ACM SIGMETRICS-IFIP PERFORMANCE, vol.34, pp.27-38, 2006. ,
Markov Chains and Stochastic Stability, 1993. ,
Approximability results for the maximum and minimum maximal induced matching problems, Discrete Optimization, vol.5, issue.3, pp.584-593, 2008. ,
Network adiabatic theorem: an efficient randomized protocol for contention resolution, Proc. ACM SIGMETRICS-IFIP PERFORMANCE, vol.37, pp.133-144, 2009. ,
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
Distributed link scheduling with constant overhead, Proc. ACM SIGMETRICS, pp.313-324, 2007. ,
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. ,
NP-completeness of some generalizations of the maximum matching problem, Information Processing Letters, vol.15, issue.1, pp.14-19, 1982. ,
Log-weight scheduling in switched networks, Queueing Systems (QUESTA), vol.71, pp.97-136, 2012. ,
Switched networks with maximum weight policies: Fluid approximation and multiplicative state space collapse, Ann. Appl. Probab, vol.22, issue.1, pp.70-127, 2012. ,
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. ,