Complexity in geometric SINR

ABSTRACT

In this paper we study the problem of scheduling wireless links in the geometric SINR model, which explicitly uses the fact that nodes are distributed in the Euclidean plane. We present the first NP-completeness proofs in such a model. In particular, we prove two problems to be NP-complete: Scheduling and One-Shot Scheduling. The first problem consists in finding a minimum-length schedule for a given set of links. The second problem receives a weighted set of links as input and consists in finding a maximum-weight subset of links to be scheduled simultaneously in one shot. In addition to the complexity proofs, we devise an approximation algorithm for each problem.

References

1. A. Behzad and I. Rubin. On the Performance of Graph-based Scheduling Algorithms for Packet Radio Networks. In Proc. of the IEEE Global Telecommunications Conference (GLOBECOM), 2003.
2. A. Behzad and I. Rubin. Impact of Power Control on the Performance of Ad Hoc Wireless Networks. In Proc. of the 24th INFOCOM, 2005.
3. P. Björklund, P. Värbrand, and D. Yuan. A column generation method for spatial TDMA scheduling in ad hoc networks. Ad Hoc Networks, 2(4):405--418, 2004.
4. A. Borbash, S. A. ;Ephremides. Wireless link scheduling with power control and sinr constraints. Information Theory, IEEE Transactions on, 52(5):5106--5111, 2006.
5. G. Brar, D. Blough, and P. Santi. Computationally Efficient Scheduling with the Physical Interference Model for Throughput Improvement in Wireless Mesh Networks. In Proc. of the 12th International Conference on Mobile Computing and Networking (MOBICOM), 2006.
6. R. Cruz and A. Santhanam. Optimal routing, link scheduling and power control in multi-hop wireless networks, 2003.
7. A. Ephremides and T. V. Truong. Scheduling broadcasts in multihop radio networks. IEEE Trans. Communications, 38(4):456--460, Apr. 1990.
8. M. Fussen, R. Wattenhofer, and A. Zollinger. Interference Arises at the Receiver. In International Conference on Wireless Networks, Communications, and Mobile Computing (WIRELESSCOM), Maui, Hawaii, USA, June 2005.
9. A. Giridhar and P. R. Kumar. Computing and communicating functions over sensor networks. IEEE Journal on Selected Areas in Communication, 23(4), 2005.
10. J. Grönkvist. Interference-Based Scheduling in Spatial Reuse TDMA--PhD thesis, Royal Institute of Technology, Stockholm, Sweden, 2005.
11. J. Grönkvist and A. Hansson. Comparison Between Graph-Based and Interference-Based STDMA Scheduling. In Proc. of the 2nd ACM International Symposium on Mobile Ad Hoc Networking & Computing (MOBIHOC), pages 255--258, 2001.
12. P. Gupta and P. R. Kumar. Critical Power for Asymptotic Connectivity in Wireless Networks. Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming (March 1998), pages 547--566, 1998.
13. P. Gupta and P. R. Kumar. The Capacity of Wireless Networks. IEEE Trans. Information Theory, 46(2):388--404, 2000.
14. B. Hajek and G. Sasaki. Link scheduling in polynomial time. Information Theory, IEEE Transactions on, 34(5):910--917.
15. H. Hunt, M. Marathe, V. Radhakrishnan, S. Ravi, D. Rosenkrantz, and R. Stearns. NC-Approximation Schemes for NP-and PSPACE-Hard Problems for Geometric Graphs. ALGORITHMS:Journal of Algorithms, 26, 1998.
16. K. Jain, J. Padhye, V. N. Padmanabhan, and L. Qiu. Impact of interference on multi-hop wireless network performance. In MobiCom'03:Proc. of the 9th Annual International Conference on Mobile Computing and Networking, pages 66--80, New York, NY, USA, 2003. ACM Press.
17. R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85--103. 1972.
18. I. T. L. Kozat, U. C. ;Koutsopoulos. Cross-layer design for power efficiency and qos provisioning in multi-hop wireless networks. Wireless Communications, IEEE Transactions on, 5, 2006.
19. S. O. Krumke, M. Marathe,, and S. Ravi. Models and approximation algorithms for channel assignment in radio networks. Wireless Networks, 6:575--584.
20. V. S. A. Kumar, M. V. Marathe, S. Parthasarathy, and A. Srinivasan. End-to-end packet-scheduling in wireless ad-hoc networks. In Proc. of the 15th annual ACM-SIAM symposium on Discrete Algorithms (SODA'04), pages 1021--1030, 2004.
21. K. Leung and L. Wang. Integrated link adaptation and power control for wireless ip networks, 2000.
22. H. L. Mainak Chatterjee and S. K. Das. Rate allocation and admission control for differentiated services in cdma data networks. IEEE Transactions on Mobile Computing, 6(2):179--191, 2007.
23. T. Moscibroda. The worst-case capacity of wireless sensor networks. In IPSN, pages 1--10, 2007.
24. T. Moscibroda and R. Wattenhofer. Coloring Unstructured Radio Networks. In Proc. of the17th Symposium on Parallel Algorithms and Architectures (SPAA), pages 39--48, 2005.
25. T. Moscibroda and R. Wattenhofer. The Complexity of Connectivity in Wireless Networks. In Proc. of the 25th IEEE INFOCOM, 2006.
26. T. Moscibroda, R. Wattenhofer, and Y. Weber. Protocol Design Beyond Graph-based Models. In Proc. of the 5th ACM SIGCOMM Workshop on Hot Topics in Networks (HotNets), 2006.
27. T. Moscibroda, R. Wattenhofer, and A. Zollinger. Topology Control meets SINR:The Scheduling Complexity of Arbitrary Topologies. In Proc. of the 7th ACM Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), 2006.
28. S. Papavassiliou and L. Tassiulas. Joint optimal channel base station and power assignment for wireless access. IEEE/ACM Trans. Netw, 4(6):857--872, 1996.
29. B. Radunovic and J.-Y. Le Boudec. Optimal Power Control, Scheduling, and Routing in UWB Networks. Journal on Selected Areas in Communications, 2(7), 2004.
30. B. Radunovic and J.-Y. Le Boudec. Rate Performance Objectives of Multi-hop Wireless Networks. In Proc. 23th IEEE INFOCOM, 2004.
31. S. Ramanathan and E. L. Lloyd. Scheduling algorithms for multihop radio networks. IEEE/ACM Trans. Netw., 1(2):166--177, 1993.
32. G. Sharma, R. R. Mazumdar, and N. B. Shroff. On the complexity of scheduling in wireless networks. In MobiCom '06:Proc. of the 12th annual international conference on Mobile computing and networking, pages 227--238, New York, NY, USA, 2006. ACM Press.
33. S. Singh and C. S. Raghavendra. PAMAS -Power Aware Multi-Access Protocol with Signalling for Ad Hoc Networks. SIGCOMM Comput. Commun. Rev., 28(3):5--26, 1998.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Combinatorics

      • Combinatorial algorithms

    • Graph theory

      • Network flows

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Scheduling algorithms

    • Graph algorithms analysis

      • Network flows

    • Online algorithms

      • Online learning algorithms

        • Scheduling algorithms

  • Randomness, geometry and discrete structures

    • Computational geometry

  • Theory and algorithms for application domains

    • Machine learning theory

      • Reinforcement learning

        • Sequential decision making