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: Gurashish Brar , Douglas M. Blough , Paolo Santi, Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161092]
• 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: Jimmi Grönkvist , Anders Hansson, Comparison between graph-based and interference-based STDMA scheduling, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501449.501453]
• 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: Harry B. Hunt, III , Madhav V. Marathe , Venkatesh Radhakrishnan , S. S. Ravi , Daniel J. Rosenkrantz , Richard E. Stearns, NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs, Journal of Algorithms, v.26 n.2, p.238-274, feb. 1998 [doi>10.1006/jagm.1997.0903]
• 16: Kamal Jain , Jitendra Padhye , Venkata N. Padmanabhan , Lili Qiu, Impact of interference on multi-hop wireless network performance, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938993]
• 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: Sven O. Krumke , Madhav V. Marathe , S. S. Ravi, Models and approximation algorithms for channel assignment in radio networks, Wireless Networks, v.7 n.6, p.575-584, November 2001 [doi>10.1023/A:1012311216333]
• 20: V. S. Anil Kumar , Madhav V. Marathe , Srinivasan Parthasarathy , Aravind Srinivasan, End-to-end packet-scheduling in wireless ad-hoc networks, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 21: K. Leung and L. Wang. Integrated link adaptation and power control for wireless ip networks, 2000.
• 22: Mainak Chatterjee , Haitao Lin , Sajal K. Das, Rate Allocation and Admission Control for Differentiated Services in CDMA Data Networks, IEEE Transactions on Mobile Computing, v.6 n.2, p.179-191, February 2007 [doi>10.1109/TMC.2007.29]
• 23: Thomas Moscibroda, The worst-case capacity of wireless sensor networks, Proceedings of the 6th international conference on Information processing in sensor networks, April 25-27, 2007, Cambridge, Massachusetts, USA [doi>10.1145/1236360.1236362]
• 24: Thomas Moscibroda , Roger Wattenhofer, Coloring unstructured radio networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073977]
• 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: Thomas Moscibroda , Roger Wattenhofer , Aaron Zollinger, Topology control meets SINR: the scheduling complexity of arbitrary topologies, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132939]
• 28: Symeon Papavassiliou , Leandros Tassiulas, Joint optimal channel base station and power assignment for wireless access, IEEE/ACM Transactions on Networking (TON), v.4 n.6, p.857-872, Dec. 1996 [doi>10.1109/90.556343]
• 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: Subramanian Ramanathan , Errol L. Lloyd, Scheduling algorithms for multihop radio networks, IEEE/ACM Transactions on Networking (TON), v.1 n.2, p.166-177, April 1993 [doi>10.1109/90.222924]
• 32: Gaurav Sharma , Ravi R. Mazumdar , Ness B. Shroff, On the complexity of scheduling in wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161116]
• 33: Suresh Singh , C. S. Raghavendra, PAMAS—power aware multi-access protocol with signalling for ad hoc networks, ACM SIGCOMM Computer Communication Review, v.28 n.3, p.5-26, July 1998 [doi>10.1145/293927.293928]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Theory

Keywords:
NP-complete, SINR, ad-Hoc networks, approximation algorithms, geometric SINR, scheduling, weighted scheduling, wireless