On Emptying a Wireless Network in Minimum Time
2012 (English)In: 2012 IEEE International Symposium on Information Theory Proceedings (ISIT), Piscataway, NJ, USA: IEEE , 2012, 2671-2675 p.Conference paper (Refereed)
We consider N transmitter-receiver pairs that share a wireless channel and we address the problem of obtaining a schedule for activating subsets of these links so as to empty the transmitter queues in minimum time. Our aim is to provide theoretical insights for the optimality characterization of the problem, using both a cross-layer model formulation, which takes into account the effect of interference on achievable transmission rates, as well as a collision-based model, which does not incorporate the physical layer realities into the problem. We present the basic linear programming formulation of the problem and establish that the optimal schedule need not consist of more than N subset activation frames. We then prove that the problem is NP-hard for all reasonable continuous rate functions. Finally, we obtain sufficient and/or necessary conditions for optimality in a number of special cases.
Place, publisher, year, edition, pages
Piscataway, NJ, USA: IEEE , 2012. 2671-2675 p.
, IEEE International Symposium on Information Theory. Proceedings, ISSN 2157-8095
interference; optimality; scheduling; wireless networks
Engineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-96567DOI: 10.1109/ISIT.2012.6284004ISI: 000312544302154ISBN: 978-1-4673-2580-6 (print)ISBN: 978-1-4673-2578-3 (e-ISBN)OAI: oai:DiVA.org:liu-96567DiVA: diva2:642260
IEEE International Symposium on Information Theory Proceedings (ISIT), Cambridge, MA, USA, 1-6 July 2012