On the complexity of scheduling in wireless networks

ABSTRACT

We consider the problem of throughput-optimal scheduling in wireless networks subject to interference constraints. We model the interference using a family of K -hop interference models. We define a K-hop interference model as one for which no two links within K hops can successfully transmit at the same time (Note that IEEE 802.11 DCF corresponds to a 2-hop interference model.) .For a given K, a throughput-optimal scheduler needs to solve a maximum weighted matching problem subject to the K-hop interference constraints. For K=1, the resulting problem is the classical Maximum Weighted Matching problem, that can be solved in polynomial time. However, we show that for K>1,the resulting problems are NP-Hard and cannot be approximated within a factor that grows polynomially with the number of nodes. Interestingly, we show that for specific kinds of graphs, that can be used to model the underlying connectivity graph of a wide range of wireless networks, the resulting problems admit polynomial time approximation schemes. We also show that a simple greedy matching algorithm provides a constant factor approximation to the scheduling problem for all K in this case. We then show that under a setting with single-hop traffic and no rate control, the maximal scheduling policy considered in recent related works can achieve a constant fraction of the capacity region for networks whose connectivity graph can be represented using one of the above classes of graphs. These results are encouraging as they suggest that one can develop distributed algorithms to achieve near optimal throughput in case of a wide range of wireless networks.

REFERENCES

• 1: Brenda S. Baker, Approximation algorithms for NP-complete problems on planar graphs, Journal of the ACM (JACM), v.41 n.1, p.153-180, Jan. 1994 [doi>10.1145/174644.174650]
• 2: D. J. Baker, J. Wieselthier, and A. Ephremides. A Distributed Algorithm for Scheduling the Activation of Links in a Self-organizing Mobile Radio Network. In IEEE ICC pages 2F.6.1--2F.6.5, 1982.
• 3: Thomas Bonald , Laurent Massoulié, Impact of fairness on Internet performance, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.82-91, June 2001, Cambridge, Massachusetts, United States
• 4: L. Bui, A. Eryilmaz, R. Srikant, and X. Wu. Joint Asynchronous Congestion Control and Distributed Scheduling for Multi-Hop Wireless Networks. In IEEE INFOCOM 2006.
• 5: P. Chaporkar, K. Kar, and S. Sarkar. Throughput Guarantees Through Maximal Scheduling in Wireless Networks. 43rd Annual Allerton Conf. on Communications, Control, and Computing, Sep 2005.
• 6: M. V. Clark, K. K. Leung, B. McNair, and Z. Kostic. Outdoor IEEE 802.11 cellular networks: Radio link performance. In IEEE ICC April 2002.
• 7: R. L. Cruz and A. V. Santhanam. Optimal routing, link scheduling and power control in multihop wireless networks. In INFOCOM 2003.
• 8: Harold N. Gabow, Data structures for weighted matching and nearest common ancestors with linking, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.434-443, January 22-24, 1990, San Francisco, California, United States
• 9: J. Gill. Computational Complexity of Probabilistic Turi ng Machines. SIAM Journal on Computing 6(4):675--695, 1977.
• 10: H. Balakrishnan et al. The Distance-2 Matching Problem and its Relationship to the MAC-layer Capacity of Ad Hoc Wireless Networks. IEEE JSAC 22(6):1069--1079, Aug 2004.
• 11: B. Hajek and G. Sasaki. Link Scheduling in Polynomial Time. IEEE Transactions on Information Theory 34(5):910--917,Sep 1988.
• 12: M. M. Halldorsson. Approximations of Weighted Independent Set and Hereditary Subset Problems. Journal of Graphs Algorithms and Applications 4(1):1--16, 2000.
• 13: J. Hastad. Clique is Hard to Approximate within n1ε. Acta Mathematica 182:105--142, 1999.
• 14: Dorit S. Hochbaum , Wolfgang Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the ACM (JACM), v.32 n.1, p.130-136, Jan. 1985 [doi>10.1145/2455.214106]
• 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: F. Kelly, A. Maulloo, and D. Tan. Rate control in communication networks: shadow prices, proportional fairness and stability. In Journalof the Oper. Res. Society volume 49, pages 237--252, 1998.
• 17: 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]
• 18: Fabian Kuhn , Aaron Zollinger, Ad-hoc networks beyond unit disk graphs, Proceedings of the 2003 joint workshop on Foundations of mobile computing, p.69-78, September 19, 2003, San Diego, CA, USA [doi>10.1145/941079.941089]
• 19: X. Lin and N. B. Shroff. The Impact of Imperfect Scheduling on Cross-Layer Rate Control in Multihop Wireless Networks. In IEEE INFOCOM Mar 2005.
• 20: Brent A. Miller , Chatschik Bisdikian, Bluetooth revealed: the insider's guide to an open specification for global wireless communication, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 21: M. J. Neely, E. Modiano, and C. Li. Fairness and optimal stochastic control for heterogeneous networks. In IEEE INFOCOM 2005.
• 22: M. J. Neely, E. Modiano, and C. E. Rohrs. Dynamic Power Allocation and Routing for Time Varying Wireless Networks. In IEEE INFOCOM 2003.
• 23: Michael J. Neely , Eytan Modiano , Charles E. Rohrs, Power allocation and routing in multibeam satellites with time-varying channels, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.138-152, February 2003 [doi>10.1109/TNET.2002.808401]
• 24: S. Sarkar and L. Tassiulas. End-to-end bandwidth guarantees through fair local spectrum share in wireless ad-hoc networks. IEEE Trans. on Automatic Control 50(9), Sep 2005.
• 25: G. Sharma, R. R. Mazumdar, and N. B. Shroff. Maximum Weighted Matching with Interference Constraints. In IEEE FAWN March 2006.
• 26: Rayadurgam Srikant, The Mathematics of Internet Congestion Control (Systems and Control: Foundations and Applications), SpringerVerlag, 2004
• 27: L. Stockmeyer and V. Vazirani. NP-completeness of some generalizations of the maximum matching problem. Inform. Process. Lett. 15(1):14--19, 1982.
• 28: Alexander L. Stolyar, Maximizing Queueing Network Utility Subject to Stability: Greedy Primal-Dual Algorithm, Queueing Systems: Theory and Applications, v.50 n.4, p.401-457, August 2005 [doi>10.1007/s11134-005-1450-0]
• 29: L. Tassiulas and A. Ephremides. Jointly optimal routing and scheduling in packet radio networks. IEEE Trans. on Info. Theory 38(1):165--168, Jan 1992.
• 30: L. Tassiulas and A. Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. on Automatic Control 37(12):1936--1948, December 1992.
• 31: Shang-Hua Teng, Points, spheres, and separators: a unified geometric approach to graph partitioning, Carnegie Mellon University, Pittsburgh, PA, 1992
• 32: X. Wu and R. Srikant. Regulated maximal matching: A distributed scheduling algorithm for multi-hop wireless networks with node exclusive spectrum sharing. In IEEE CDC 2005.
• 33: X. Wu and R. Srikant. Bounds on the Capacity Region of Multi-hop Wireless Networks under Distributed Greedy Scheduling. In IEEE INFOCOM 2006.
• 34: L. Xiao, M. Johansson, and S. Boyd. Simultaneous routing and resource allocation via dual decomposition. IEEE Trans. on Comm. 52(7):1136--1144, July 2004.
• 35: Haïkel Yaïche , Ravi R. Mazumdar , Catherine Rosenberg, A game theoretic framework for bandwidth allocation and pricing in broadband networks, IEEE/ACM Transactions on Networking (TON), v.8 n.5, p.667-678, Oct. 2000 [doi>10.1109/90.879352]
• 36: Y. Yi and S. Shakkottai. Hop-by-hop Congestion Control over a Wireless Multi-hop Network. In IEEE INFOCOM March 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

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.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
capacity, computational complexity, interference, maximum weighted matching, scheduling, throughput, wireless networks