Document Open Access Logo

Spanning Trees With Edge Conflicts and Wireless Connectivity

Authors Magnús M. Halldórsson, Guy Kortsarz, Pradipta Mitra, Tigran Tonoyan

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.158.pdf
  • Filesize: 424 kB
  • 15 pages

Document Identifiers

Author Details

Magnús M. Halldórsson
  • School of Computer Science, Reykjavik University, Iceland
Guy Kortsarz
  • Rutgers University, Camden, NJ, USA
Pradipta Mitra
  • Google Research, New York, USA
Tigran Tonoyan
  • School of Computer Science, Reykjavik University, Iceland

Funding

The first and last authors are supported by grants nos. 152679-05 and 174484-05 from the Icelandic Research Fund. The second author is supported by NSF grant 1540547.

Cite AsGet BibTex

Magnús M. Halldórsson, Guy Kortsarz, Pradipta Mitra, and Tigran Tonoyan. Spanning Trees With Edge Conflicts and Wireless Connectivity. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 158:1-158:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.158

Abstract

We introduce the problem of finding a spanning tree along with a partition of the tree edges into fewest number of feasible sets, where constraints on the edges define feasibility. The motivation comes from wireless networking, where we seek to model the irregularities seen in actual wireless environments. Not all node pairs may be able to communicate, even if geographically close - thus, the available pairs are specified with a link graph {L}=(V,E). Also, signal attenuation need not follow a nice geometric formula - hence, interference is modeled by a conflict (hyper)graph {C}=(E,F) on the links. The objective is to maximize the efficiency of the communication, or equivalently, to minimize the length of a schedule of the tree edges in the form of a coloring. We find that in spite of all this generality, the problem can be approximated linearly in terms of a versatile parameter, the inductive independence of the interference graph. Specifically, we give a simple algorithm that attains a O(rho log n)-approximation, where n is the number of nodes and rho is the inductive independence, and show that near-linear dependence on rho is also necessary. We also treat an extension to Steiner trees, modeling multicasting, and obtain a comparable result. Our results suggest that several canonical assumptions of geometry, regularity and "niceness" in wireless settings can sometimes be relaxed without a significant hit in algorithm performance.

Subject Classification

ACM Subject Classification
  • Theory of computation → Routing and network design problems
  • Networks → Network design and planning algorithms
Keywords
  • spanning trees
  • wireless capacity
  • aggregation
  • approximation algorithms

Metrics

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

Related Versions

References

  1. Karhan Akcoglu, James Aspnes, Bhaskar DasGupta, and Ming-Yang Kao. Opportunity cost algorithms for combinatorial auctions. In Computational Methods in Decision-Making, Economics and Finance, pages 455-479. Springer, 2002. Google Scholar
  2. Nouha Baccour, Anis Koubaa, Luca Mottola, Marco Antonio Zuniga, Habib Youssef, Carlo Alberto Boano, and Mario Alves. Radio link quality estimation in wireless sensor networks: a survey. ACM Trans. Sensor Netw., 8(4):34, 2012. Google Scholar
  3. Vittorio Bilò, Ioannis Caragiannis, Angelo Fanelli, Michele Flammini, and Gianpiero Monaco. Simple greedy algorithms for fundamental multidimensional graph problems. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 125:1-125:13, 2017. Google Scholar
  4. Marijke H. L. Bodlaender and Magnús M. Halldórsson. Beyond geometry: towards fully realistic wireless models. In ACM Symposium on Principles of Distributed Computing, PODC '14, Paris, France, July 15-18, 2014, pages 347-356, 2014. Google Scholar
  5. Parinya Chalermsook, Bundit Laekhanukit, and Danupon Nanongkai. Graph products revisited: Tight approximation hardness of induced matching, poset dimension and more. In SODA, pages 1557-1576. SIAM, 2013. Google Scholar
  6. Johannes Dams, Martin Hoefer, and Thomas Kesselheim. Scheduling in wireless networks with Rayleigh-fading interference. IEEE Transactions on Mobile Computing, 14(7):1503-1514, 2015. Google Scholar
  7. A. Fanghänel, T. Kesselheim, H. Räcke, and B. Vöcking. Oblivious interference scheduling. In PODC, pages 220-229, 2009. Google Scholar
  8. Martin Fürer and Balaji Raghavachari. Approximating the minimum-degree steiner tree to within one of optimal. Journal of Algorithms, 17(3):409-423, 1994. Google Scholar
  9. Rajiv Gandhi, Magnús M. Halldórsson, Christian Konrad, Guy Kortsarz, and Hoon Oh. Radio aggregation scheduling. In Algosensors, pages 169-182, 2015. Google Scholar
  10. Deepak Ganesan, Bhaskar Krishnamachari, Alec Woo, David Culler, Deborah Estrin, and Stephen Wicker. Complex behavior at scale: An experimental study of low-power wireless sensor networks. Technical report, UCLA/CSD-TR 02, 2002. Google Scholar
  11. Oliver Göbel, Martin Hoefer, Thomas Kesselheim, Thomas Schleiden, and Berthold Vöcking. Online independent set beyond the worst-case: Secretaries, prophets, and periods. In ICALP, pages 508-519, 2014. Google Scholar
  12. Olga Goussevskaia, Magnús M Halldórsson, and Roger Wattenhofer. Algorithms for wireless capacity. IEEE/ACM Transactions on Networking (TON), 22(3):745-755, 2014. Google Scholar
  13. P. Gupta and P. R. Kumar. The Capacity of Wireless Networks. IEEE Trans. Information Theory, 46(2):388-404, 2000. Google Scholar
  14. M. M. Halldórsson. Wireless scheduling with power control. ACM Transactions on Algorithms, 9(1):7, December 2012. Google Scholar
  15. Magnús M. Halldórsson, Stephan Holzer, Pradipta Mitra, and Roger Wattenhofer. The power of oblivious wireless power. SIAM J. Comput., 46(3):1062-1086, 2017. Google Scholar
  16. 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. Google Scholar
  17. Magnús M. Halldórsson and Pradipta Mitra. Wireless connectivity and capacity. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 516-526, 2012. Google Scholar
  18. Magnús M. Halldórsson and Pradipta Mitra. Nearly optimal bounds for distributed wireless scheduling in the SINR model. Distributed Computing, 29(2):77-88, 2016. URL: http://dx.doi.org/10.1007/s00446-014-0222-7.
  19. Magnús M. Halldórsson and Tigran Tonoyan. How well can graphs represent wireless interference? In STOC, pages 635-644, 2015. Google Scholar
  20. 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. Google Scholar
  21. Magnús M. Halldórsson and Tigran Tonoyan. Optimal aggregation throughput is nearly constant. In Mobihoc, 2017. Poster abstract. Google Scholar
  22. Magnús M. Halldórsson and Tigran Tonoyan. Wireless link capacity under shadowing and fading. In MobiHoc, pages 27:1-27:10, 2017. Google Scholar
  23. Magnús M. Halldórsson and Tigran Tonoyan. Optimal aggregation throughput is nearly constant. In 38th IEEE International Conference on Distributed Computing Systems, July 2-5, 2018, Vienna, Austria, 2018. Google Scholar
  24. Martin Hoefer and Thomas Kesselheim. Secondary spectrum auctions for symmetric and submodular bidders. ACM Transactions on Economics and Computation, 3(2):9, 2015. Google Scholar
  25. Martin Hoefer, Thomas Kesselheim, and Berthold Vöcking. Approximation algorithms for secondary spectrum auctions. ACM Transactions on Internet Technology (TOIT), 14(2-3):16, 2014. Google Scholar
  26. Özlem Durmaz Incel, Amitabha Ghosh, and Bhaskar Krishnamachari. Scheduling algorithms for tree-based data collection in wireless sensor networks. In DCOSS, pages 407-445. Springer, 2011. Google Scholar
  27. David S. Johnson. Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci., 9:256-278, 1974. URL: http://dx.doi.org/10.1016/S0022-0000(74)80044-9.
  28. T. Kesselheim and B. Vöcking. Distributed contention resolution in wireless networks. In DISC, pages 163-178, August 2010. Google Scholar
  29. 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. Google Scholar
  30. Thomas Kesselheim. Approximation algorithms for wireless link scheduling with flexible data rates. In ESA, pages 659-670, 2012. Google Scholar
  31. Thomas Kesselheim. Dynamic packet scheduling in wireless networks. In PODC, pages 281-290, 2012. Google Scholar
  32. David Kotz, Calvin Newport, Robert S Gray, Jason Liu, Yougu Yuan, and Chip Elliott. Experimental evaluation of wireless simulation assumptions. In Proceedings of the 7th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, pages 78-82. ACM, 2004. Google Scholar
  33. Fabian Kuhn, Nancy Lynch, Calvin Newport, Rotem Oshman, and Andrea Richa. Broadcasting in unreliable radio networks. In PODC, pages 336-345. ACM, 2010. Google Scholar
  34. Thomas Moscibroda. The worst-case capacity of wireless sensor networks. In IPSN, pages 1-10, 2007. Google Scholar
  35. 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. Google Scholar
  36. Thomas Moscibroda, Roger Wattenhofer, and Aaron Zollinger. Topology control meets SINR: The scheduling complexity of arbitrary topologies. In MOBIHOC, pages 310-321, 2006. Google Scholar
  37. Yuli Ye and Allan Borodin. Elimination graphs. ACM Trans. Algorithms, 8(2):14:1-14:23, 2012. Google Scholar
  38. Marco Zúñiga Zamalloa and Bhaskar Krishnamachari. An analysis of unreliability and asymmetry in low-power wireless links. ACM Transactions on Sensor Networks (TOSN), 3(2):7, 2007. Google Scholar
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 Imprint Privacy Contact