Distributed Link Scheduling in Wireless Networks

Jean-Claude Bermond 1 Dorian Mazauric 2 Vishal Misra 3 Philippe Nain 4
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
2 ABS - Algorithms, Biology, Structure
CRISAM - Inria Sophia Antipolis - Méditerranée
4 DANTE - Dynamic Networks : Temporal and Structural Capture Approach
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme, IXXI - Institut Rhône-Alpin des systèmes complexes
Abstract : This work investigates distributed transmission scheduling in wireless networks. Due to interference constraints, "neighboring links" cannot be simultaneously activated, otherwise transmissions will fail. Here, we consider any binary model of interference. We use the model described by Bui, Sanghavi, and Srikant in [BSS09, SBS07]. We assume that time is slotted and during each slot there are two phases: one control phase which determines what links will be activated and a data phase in which data are sent. We assume random arrivals on each link during each slot, so that a queue is associated to each link. Since nodes do not have a global knowledge of the network, our aim (like in [BSS09, SBS07]) is to design for the control phase a distributed algorithm which determines a set of non-interfering links. To be efficient the control phase should be as short as possible; this is done by exchanging control messages during a constant number of mini-slots (constant overhead). In this paper, we design the first fully distributed local algorithm with the following properties: it works for any arbitrary binary interference model; it has a constant overhead (independent of the size of the network and the values of the queues), and it does not require any knowledge of the queue-lengths. We prove that this algorithm gives a maximal set of active links, where in each interference set there is at least one active link. We also establish sufficient conditions for stability under general Markovian assumptions. Finally, the performance of our algorithm (throughput, stability) is investigated and compared via simulations to that of previously proposed schemes.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [50 references]  Display  Hide  Download

https://hal.inria.fr/hal-01977266
Contributor : Philippe Nain <>
Submitted on : Thursday, January 10, 2019 - 4:27:11 PM
Last modification on : Wednesday, January 23, 2019 - 7:48:12 PM
Long-term archiving on : Thursday, April 11, 2019 - 5:18:46 PM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01977266, version 1

Citation

Jean-Claude Bermond, Dorian Mazauric, Vishal Misra, Philippe Nain. Distributed Link Scheduling in Wireless Networks. 2019. ⟨hal-01977266⟩

Share

Metrics

Record views

139

Files downloads

126