On the Complexity of Scheduling in Wireless Networks
Tóm tắt
We consider the problem of throughput-optimal scheduling in wireless networks subject to interference constraints. We model the interference using a family of
-hop interference models, under which no two links within a
-hop distance can successfully transmit at the same time. For a given
, we can obtain a throughput-optimal scheduling policy by solving the well-known maximum weighted matching problem. We show that for
, the resulting problems are NP-Hard that cannot be approximated within a factor that grows polynomially with the number of nodes. Interestingly, for geometric unit-disk graphs that can be used to describe a wide range of wireless networks, the problems admit polynomial time approximation schemes within a factor arbitrarily close to 1. In these network settings, we also show that a simple greedy algorithm can provide a 49-approximation, and the maximal matching scheduling policy, which can be easily implemented in a distributed fashion, achieves a guaranteed fraction of the capacity region for "all
." The geometric constraints are crucial to obtain these throughput guarantees. These results are encouraging as they suggest that one can develop low-complexity distributed algorithms to achieve near-optimal throughput for a wide range of wireless networks.
Tài liệu tham khảo
Tassiulas L, Ephremides A: Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control 1992, 37(12):1936-1948. 10.1109/9.182479
Xiao L, Johansson M, Boyd SP: Simultaneous routing and resource allocation via dual decomposition. IEEE Transactions on Communications 2004, 52(7):1136-1144. 10.1109/TCOMM.2004.831346
Neely MJ, Modiano E, Rohrs CE: Power allocation and routing in multibeam satellites with time-varying channels. IEEE/ACM Transactions on Networking 2003, 11(1):138-152. 10.1109/TNET.2002.808401
Tassiulas L, Ephremides A: Jointly optimal routing and scheduling in packet radio networks. IEEE Transactions on Information Theory 1992, 38(1):165-168. 10.1109/18.108264
Cruz RL, Santhanam AV: Optimal routing, link scheduling and power control in multi-hop wireless networks. Proceedings of the 22nd Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM '03), April 2003 702-711.
Kelly FP, Maulloo AK, Tan D: Rate control for communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society 1998, 49(3):237-252.
Yaïche H, Mazumdar RR, Rosenberg C: A game theoretic framework for bandwidth allocation and pricing in broadband networks. IEEE/ACM Transactions on Networking 2000, 8(5):667-678. 10.1109/90.879352
Lin X, Shroff NB: The impact of imperfect scheduling on cross-layer rate control in wireless networks. Proceedings of the Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM '05), March 2005 3: 1804-1814.
Wu X, Srikant R: Scheduling efficiency of distributed greedy scheduling algorithms in wireless networks. Proceedings of the 25th Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM '06), April 2006
Stolyar AL: Maximizing queueing network utility subject to stability: greedy primal-dual algorithm. Queueing Systems 2005, 50(4):401-457. 10.1007/s11134-005-1450-0
Miller B, Bisdikian C: Bluetooth Revealed: The Insider's Guide to an Open Specification for Global Wireless Communications. Prentice-Hall; 2000.
Hajek B, Sasaki G: Link scheduling in polynomial time. IEEE Transactions on Information Theory 1988, 34(5):910-917. 10.1109/18.21215
Gabow HN: Data structures for weighted matching and nearest common ancestors with linking. Proceedings of the Symposium on Discrete Algorithms (SODA '90), 1990
Balakrishnan H, Barrett CL, Kumar VSA, Marathe MV, Thite S: The distance-2 matching problem and its relationship to the MAC-layer capacity of ad hoc wireless networks. IEEE Journal on Selected Areas in Communications 2004, 22(6):1069-1079. 10.1109/JSAC.2004.830909
Chaporkar P, Kar K, Luo X, Sarkar S: Throughput and fairness guarantees through maximal scheduling in wireless networks. IEEE Transactions on Information Theory 2008, 54(2):572-594.
Modiano E, Shah D, Zussman G: Maximizing throughput in wireless networks via gossiping. Performance Evaluation Review 2006, 34(1):27-38. 10.1145/1140103.1140283
Sanghavi S, Bui L, Srikant R: Distributed link scheduling with constant overhead. Proceedings of the ACM International Conference on Measurement and Modeling of Computer Systems (Sigmetrics '07), June 2007 313-324.
Sharma G, Joo C, Shroff NB: Distributed scheduling schemes for throughput guarantees in wireless networks. Proceedings of the 44th Annual Allerton Conference on Communications, Control, and Computing, September 2006
Lin X, Rasool SB: Constant-time distributed scheduling policies for ad hoc wireless networks. IEEE Transactions on Automatic Control 2009, 54(2):231-242.
Joo C, Shroff NB: Performance of random access scheduling schemes in multi-hop wireless networks. Proceedings of the 26th Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM '07), May 2007 19-27.
Stockmeyer LJ, Vazirani VV: NP-completeness of some generalizations of the maximum matching problem. Information Processing Letters 1982, 15(1):14-19. 10.1016/0020-0190(82)90077-1
Joo C, Sharma G, Mazumdar RR, Shroff NB: On the complexity of scheduling in wireless networks. Korea University of Technology and Education; 2010.http://netlab.kut.ac.kr
Sharma G, Mazumdar RR, Shroff NB: Maximum weighted matching with interference constraints. Proceedings of the 4th Annual IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom '06), March 2006 70-74.
Gill J: Computational complexity of probabilistic turing machines. SIAM Journal on Computing 1977, 6(4):675-695. 10.1137/0206049
Håstad J:Clique is hard to approximate within . Acta Mathematica 1999, 182(1):105-142. 10.1007/BF02392825
Halldórsson MM: Approximations of weighted independent set and hereditary subset problems. Journal of Graph Algorithms and Applications 2000, 4(1):1-16.
Krumke SO, Marathe MV, Ravi SS: Models and approximation algorithms for channel assignment in radio networks. Wireless Networks 2001, 7(6):575-584. 10.1023/A:1012311216333
Teng SH: Points, spheres, and separators, a unified geometric approach to graph separators, Ph.D. thesis. School of Computer Science, Carnegie Mellon University, CMU-CS-91-184, Pittsburgh, Pa, USA; August 1991.
Kuhn F, Wattenhofer R, Zollinger A: Ad-hoc networks beyond unit disk graphs. Proceedings of the 1st ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC '03), September 2003, San Diego, Calif, USA 69-78.
Baker BS: Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM 1994, 41(1):153-180. 10.1145/174644.174650
Hunt HB III, Marathe MV, Radhakrishnan V, Ravi SS, Rosenkrantz DJ, Stearns RE: NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. Journal of Algorithms 1998, 26(2):238-274. 10.1006/jagm.1997.0903
Hochbaum DS, Maass W: Approximation schemes for covering and packing problems in image processing and VLSI. Journal of the ACM 1985, 32(1):130-136. 10.1145/2455.214106
Avis D: A survey of heuristics for the weighted matching problem. Networks 1983, 13(4):475-493. 10.1002/net.3230130404
Ramanathan S, Lloyd EL: Scheduling algorithms for multihop radio networks. IEEE/ACM Transactions on Networking 1993, 1(2):166-177. 10.1109/90.222924
Hoepman J-H: Simple distributed weighted matchings. http://arxiv.org/abs/cs/0410047v1
Joo C, Lin X, Shroff NB: Understanding the capacity region of the greedy maximal scheduling algorithm in multi-hop wireless networks. Proceedings of the Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM '08), April 2008 1103-1111.
Joo C, Lin X, Shroff NB: Performance limits of greedy maximal matching in multi-hop wireless networks. Proceedings of the 46th IEEE Conference on Decision and Control (CDC '07), December 2007 1128-1133.