inria-00345669, version 3

Distributed Call Scheduling in Wireless Networks

Jean-Claude Bermond () ¹, Dorian Mazauric () ^1, 2, Vishal Misra () ³, Philippe Nain () ²

N° RR-6763 (2008)

• 1 :  MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
• 
  INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271 France
• 2 :  MAESTRO (INRIA Sophia Antipolis)
• 
  INRIA – Université Montpellier II - Sciences et techniques France
• 3 :  Department of Computer Science [New York]
• http://www.cs.columbia.edu/
  Columbia University Department of Computer Science 450 Computer Science Building 1214 Amsterdam Avenue, Mailcode: 0401 New York États-Unis

Versions disponibles :  v1 (10-12-2008) v2 (29-01-2009) v3 (21-11-2009)

Références bibliographiques

• Type de publication : Rapports
• Domaine : Informatique/Algorithme et structure de données
• Titre : Distributed Call Scheduling in Wireless Networks
• Résumé : 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 follow the model described by Bui, Sanghavi, and Srikant in SBS09,SBS07. We suppose that time is slotted and during each slot we have two phases: one control phase which determines what links will be activated and send data during the second phase. We assume random arrivals on each link during each slot, therefore a queue is associated to each link. Since nodes do not have a global knowledge of the network, our aim (like in SBS09,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 article 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 needs no knowledge. Indeed contrary to other existing algorithms, we do not need to know the values of the queues of the "neighboring links'', which are difficult to obtain in a wireless network with interference. We prove that this algorithm gives a maximal set of active links (in each interference set, there is at least one active edge). We also give sufficient conditions for stability under Markovian assumptions. Finally the performance of our algorithm (throughput, stability) is investigated and compared via simulations to that of previously proposed schemes.
• Langue du document : Anglais
• Type de rapport : Rapport de recherche
• Date de publication : 2008
• Mots-clés : wireless network – transmission scheduling – interference – distributed algorithm – stability
• Date de rédaction : 2008
• Référence interne : RR-6763

Liste des fichiers attachés à ce document :

• inria-00345669, version 3
• http://hal.inria.fr/inria-00345669
• oai:hal.inria.fr:inria-00345669
• Contributeur : Dorian Mazauric <>
• Soumis le : Samedi 21 Novembre 2009, 10:39:41
• Dernière modification le : Samedi 21 Novembre 2009, 11:31:47