Document Open Access Logo

Universal Framework for Wireless Scheduling Problems

Authors Eyjólfur I. Ásgeirsson, Magnús M. Halldórsson, Tigran Tonoyan

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.129.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Eyjólfur I. Ásgeirsson
Magnús M. Halldórsson
Tigran Tonoyan

Cite As Get BibTex

Eyjólfur I. Ásgeirsson, Magnús M. Halldórsson, and Tigran Tonoyan. Universal Framework for Wireless Scheduling Problems. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 129:1-129:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.129

Abstract

An overarching issue in resource management of wireless networks is assessing their capacity: How much communication can be achieved in a network, utilizing all the tools available: power control, scheduling, routing, channel assignment and rate adjustment? We propose the first framework for approximation algorithms in the physical model that addresses these questions in full, including  rate control. The approximations obtained are doubly logarithmic in the link length and rate diversity. Where previous bounds are known, this gives an exponential improvement. 

A key contribution is showing that the complex interference relationship of the physical model can be simplified into a novel type of amenable conflict graphs, at a small cost. We also show that the approximation obtained is provably the best possible for any conflict graph formulation.

Subject Classification

Keywords
  • Wireless
  • Scheduling
  • Physical Model
  • Approximation framework

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Karhan Akcoglu, James Aspnes, Bhaskar DasGupta, and Ming-Yang Kao. Opportunity cost algorithms for combinatorial auctions. CoRR, cs.CE/0010031, 2000. Google Scholar
  2. Mahmoud Al-Ayyoub and Himanshu Gupta. Joint routing, channel assignment, and scheduling for throughput maximization in general interference models. IEEE Trans. Mob. Comput., 9(4):553-565, 2010. URL: http://dx.doi.org/10.1109/TMC.2009.144.
  3. Jørgen Bang-Jensen and Magnús M. Halldórsson. Vertex coloring edge-weighted digraphs. Inf. Process. Lett., 115(10):791-796, 2015. URL: http://dx.doi.org/10.1016/j.ipl.2015.05.007.
  4. Deepti Chafekar, V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, and Aravind Srinivasan. Cross-layer latency minimization in wireless networks with SINR constraints. In Proceedings of the 8th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2007, Montreal, Quebec, Canada, September 9-14, 2007, pages 110-119, 2007. URL: http://dx.doi.org/10.1145/1288107.1288123.
  5. Michael Dinitz. Distributed algorithms for approximating wireless network capacity. In INFOCOM 2010. 29th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 15-19 March 2010, San Diego, CA, USA, pages 1397-1405, 2010. URL: http://dx.doi.org/10.1109/INFCOM.2010.5461905.
  6. Alexander Fanghänel, Thomas Kesselheim, and Berthold Vöcking. Improved algorithms for latency minimization in wireless networks. Theor. Comput. Sci., 412(24):2657-2667, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2010.05.004.
  7. Liqun Fu, Soung Chang Liew, and Jianwei Huang. Power controlled scheduling with consecutive transmission constraints: Complexity analysis and algorithm design. In INFOCOM 2009. 28th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 19-25 April 2009, Rio de Janeiro, Brazil, pages 1530-1538, 2009. URL: http://dx.doi.org/10.1109/INFCOM.2009.5062070.
  8. Olga Goussevskaia, Yvonne Anne Oswald, and Roger Wattenhofer. Complexity in geometric SINR. In Proceedings of the 8th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2007, Montreal, Quebec, Canada, September 9-14, 2007, pages 100-109, 2007. URL: http://dx.doi.org/10.1145/1288107.1288122.
  9. Olga Goussevskaia, Luiz Filipe M. Vieira, and Marcos Augusto M. Vieira. Wireless scheduling with multiple data rates: From physical interference to disk graphs. Computer Networks, 106:64-76, 2016. URL: http://dx.doi.org/10.1016/j.comnet.2016.06.016.
  10. Piyush Gupta and P. R. Kumar. The capacity of wireless networks. IEEE Trans. Information Theory, 46(2):388-404, 2000. URL: http://dx.doi.org/10.1109/18.825799.
  11. Magnús M. Halldórsson. Wireless scheduling with power control. ACM Trans. Algorithms, 9(1):7:1-7:20, 2012. URL: http://dx.doi.org/10.1145/2390176.2390183.
  12. Magnús M. Halldórsson and Pradipta Mitra. Wireless capacity with oblivious power in general metrics. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 1538-1548, 2011. URL: http://dx.doi.org/10.1137/1.9781611973082.119.
  13. Magnús M. Halldórsson and Pradipta Mitra. Wireless capacity and admission control in cognitive radio. In Proceedings of the IEEE INFOCOM 2012, Orlando, FL, USA, March 25-30, 2012, pages 855-863, 2012. URL: http://dx.doi.org/10.1109/INFCOM.2012.6195834.
  14. Magnús M. Halldórsson and Tigran Tonoyan. How well can graphs represent wireless interference? In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 635-644, 2015. URL: http://dx.doi.org/10.1145/2746539.2746585.
  15. Magnús M. Halldórsson and Tigran Tonoyan. The price of local power control in wireless scheduling. In 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2015, December 16-18, 2015, Bangalore, India, pages 529-542, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2015.529.
  16. Juha Heinonen. Lectures on Analysis on Metric Spaces. Springer, 1. edition, 2000. Google Scholar
  17. Klaus Jansen. Approximate strong separation with application in fractional graph coloring and preemptive scheduling. Theor. Comput. Sci., 302(1-3):239-256, 2003. URL: http://dx.doi.org/10.1016/S0304-3975(02)00829-0.
  18. Libin Jiang, Mathieu Leconte, Jian Ni, R. Srikant, and Jean C. Walrand. Fast mixing of parallel glauber dynamics and low-delay CSMA scheduling. IEEE Trans. Information Theory, 58(10):6541-6555, 2012. URL: http://dx.doi.org/10.1109/TIT.2012.2204032.
  19. Libin Jiang and Jean C. Walrand. A distributed CSMA algorithm for throughput and utility maximization in wireless networks. IEEE/ACM Trans. Netw., 18(3):960-972, 2010. URL: http://dx.doi.org/10.1109/TNET.2009.2035046.
  20. Changhee Joo, Xiaojun Lin, and Ness B. Shroff. Understanding the capacity region of the greedy maximal scheduling algorithm in multihop wireless networks. IEEE/ACM Trans. Netw., 17(4):1132-1145, 2009. URL: http://dx.doi.org/10.1145/1618562.1618572.
  21. Bastian Katz, Markus Völker, and Dorothea Wagner. Energy efficient scheduling with power control for wireless networks. In 8th International Symposium on Modeling and Optimization in Mobile, Ad-Hoc and Wireless Networks (WiOpt 2010), May 31 - June 4, 2010, University of Avignon, Avignon, France, pages 160-169, 2010. Google Scholar
  22. Thomas Kesselheim. A constant-factor approximation for wireless capacity maximization with power control in the SINR model. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 1549-1559, 2011. URL: http://dx.doi.org/10.1137/1.9781611973082.120.
  23. Thomas Kesselheim. Approximation algorithms for wireless link scheduling with flexible data rates. In Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings, pages 659-670, 2012. URL: http://dx.doi.org/10.1007/978-3-642-33090-2_57.
  24. Henry Lin and Frans Schalekamp. On the complexity of the minimum latency scheduling problem on the euclidean plane. CoRR, abs/1203.2725, 2012. Google Scholar
  25. Xiaojun Lin and N. B. Shroff. Joint rate control and scheduling in multihop wireless networks. In 2004 43rd IEEE Conference on Decision and Control (CDC) (IEEE Cat. No.04CH37601), volume 2, pages 1484-1489 Vol.2, Dec 2004. URL: http://dx.doi.org/10.1109/CDC.2004.1430253.
  26. Thomas Moscibroda and Roger Wattenhofer. The complexity of connectivity in wireless networks. In INFOCOM 2006. 25th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 23-29 April 2006, Barcelona, Catalunya, Spain, 2006. URL: http://dx.doi.org/10.1109/INFOCOM.2006.23.
  27. Devavrat Shah, David N. C. Tse, and John N. Tsitsiklis. Hardness of low delay network scheduling. IEEE Trans. Information Theory, 57(12):7810-7817, 2011. URL: http://dx.doi.org/10.1109/TIT.2011.2168897.
  28. L. Tassiulas and A. Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control, 37(12):1936-1948, Dec 1992. URL: http://dx.doi.org/10.1109/9.182479.
  29. Tigran Tonoyan. On some bounds on the optimum schedule length in the SINR model. In Algorithms for Sensor Systems, 8th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities, ALGOSENSORS 2012, Ljubljana, Slovenia, September 13-14, 2012. Revised Selected Papers, pages 120-131, 2012. URL: http://dx.doi.org/10.1007/978-3-642-36092-3_14.
  30. Peng-Jun Wan. Multiflows in multihop wireless networks. In Proceedings of the 10th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2009, New Orleans, LA, USA, May 18-21, 2009, pages 85-94, 2009. URL: http://dx.doi.org/10.1145/1530748.1530761.
  31. Peng-Jun Wan, Xiaohua Jia, Guojun Dai, Hongwei Du, Zhiguo Wan, and Ophir Frieder. Scalable algorithms for wireless link schedulings in multi-channel multi-radio wireless networks. In Proceedings of the IEEE INFOCOM 2013, Turin, Italy, April 14-19, 2013, pages 2121-2129, 2013. URL: http://dx.doi.org/10.1109/INFCOM.2013.6567014.
  32. Peng-Jun Wan, Zhu Wang, Lei Wang, Zhiguo Wan, and Sai Ji. From least interference-cost paths to maximum (concurrent) multiflow in MC-MR wireless networks. In 2014 IEEE Conference on Computer Communications, INFOCOM 2014, Toronto, Canada, April 27 - May 2, 2014, pages 334-342, 2014. URL: http://dx.doi.org/10.1109/INFOCOM.2014.6847955.
  33. Lixin Wang, C. P. Abubucker, William F. Lawless, and Anthony J. Baker. A constant-approximation for maximum weight independent set of links under the SINR model. In Seventh International Conference on Mobile Ad-hoc and Sensor Networks, MSN 2011, Beijing, China, December 16-18, 2011, pages 9-14, 2011. URL: http://dx.doi.org/10.1109/MSN.2011.1.
  34. Xinzhou Wu, R. Srikant, and James R. Perkins. Scheduling efficiency of distributed greedy scheduling algorithms in wireless networks. IEEE Trans. Mob. Comput., 6(6):595-605, 2007. URL: http://dx.doi.org/10.1109/TMC.2007.1061.
  35. Yuli Ye and Allan Borodin. Elimination graphs. ACM Trans. Algorithms, 8(2):14:1-14:23, 2012. URL: http://dx.doi.org/10.1145/2151171.2151177.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact