Gaurav Sharma
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.
- B. S. Baker. Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1):153--180, January 1994. Google Scholar
Digital Library
- 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.Google Scholar
- T. Bonald and L. Massoulie. Impact of fariness on Internet performance. In ACM Sigmetrics 2001. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- R. L. Cruz and A. V. Santhanam. Optimal routing, link scheduling and power control in multihop wireless networks. In INFOCOM 2003.Google ScholarCross Ref
- H. N. Gabow. Data Structures for Weighted Matching and Nearest Common Ancestors with Linking. In SODA 1990. Google ScholarDigital Library
- J. Gill. Computational Complexity of Probabilistic Turi ng Machines. SIAM Journal on Computing 6(4):675--695, 1977.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- B. Hajek and G. Sasaki. Link Scheduling in Polynomial Time. IEEE Transactions on Information Theory 34(5):910--917,Sep 1988.Google ScholarDigital Library
- M. M. Halldorsson. Approximations of Weighted Independent Set and Hereditary Subset Problems. Journal of Graphs Algorithms and Applications 4(1):1--16, 2000.Google ScholarCross Ref
- J. Hastad. Clique is Hard to Approximate within n1ε. Acta Mathematica 182:105--142, 1999.Google ScholarCross Ref
- D. Hochbaum and W. Maass. Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI. J. ACM 32(1):130--136, 1985. Google ScholarDigital Library
- H. B. Hunt, M. V. Marathe, V. Radhakrishnan, S. S. Ravi, D. J. Rosenkrantz, and R. E. Stearns. NC-Approximation Schemes for NP-and PSPACE-Hard Problems for Geometric Graphs. Journal of Algorithms 26(2):238--274, Feb 1998. Google ScholarDigital Library
- 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.Google Scholar
- S. O. Krumke, M. V. Marathe, ,and S. S. Ravi. Models and Approximation Algorithms for Channel Assignment in Radio Networks. Wireless Networks 7(6):575--584, 2001. Google ScholarDigital Library
- F. Kuhn, R. Wattenhofer, and A. Zollinger. Ad-hoc networks beyond unit disk graphs. In 1st ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), San Diego, California, USA September 2003. Google ScholarDigital Library
- 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.Google Scholar
- B. Miller and C. Bisdikian. Bluetooth Revealed: The Insider's Guide to an Open Specification for Global Wireless Communications Prentice Hall, 2000. Google ScholarDigital Library
- M. J. Neely, E. Modiano, and C. Li. Fairness and optimal stochastic control for heterogeneous networks. In IEEE INFOCOM 2005.Google ScholarCross Ref
- M. J. Neely, E. Modiano, and C. E. Rohrs. Dynamic Power Allocation and Routing for Time Varying Wireless Networks. In IEEE INFOCOM 2003. Google ScholarDigital Library
- M. J. Neely, E. Modiano, and C. E. Rohrs. Power allocation and routing in multibeam satellites with time-varying channels. IEEE/ACM Trans. Netw. 11(1):138--152, 2003. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- G. Sharma, R. R. Mazumdar, and N. B. Shroff. Maximum Weighted Matching with Interference Constraints. In IEEE FAWN March 2006.Google Scholar
- R. Srikant. The Mathematics of Internet Congestion Control Birkhauser, 2004. Google ScholarDigital Library
- L. Stockmeyer and V. Vazirani. NP-completeness of some generalizations of the maximum matching problem. Inform. Process. Lett. 15(1):14--19, 1982.Google ScholarCross Ref
- A. L. Stolyar. Maximizing Queueing Network Utility subject to Stability: Greedy Primal-Dual Algorithm. Queueing Systems 50(4):401--457, 2005. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- S. H. Teng. 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, Aug 1991. Google ScholarDigital Library
- 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.Google Scholar
- X. Wu and R. Srikant. Bounds on the Capacity Region of Multi-hop Wireless Networks under Distributed Greedy Scheduling. In IEEE INFOCOM 2006.Google Scholar
- 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.Google ScholarCross Ref
- H. Yaiche, R. Mazumdar, and C. Rosenberg. A game-theoretic framework for bandwidth allocation and pricing in broadband networks. IEEE/ACM Trans. on Networking 8(5):667--678, Oct 2000. Google ScholarDigital Library
- Y. Yi and S. Shakkottai. Hop-by-hop Congestion Control over a Wireless Multi-hop Network. In IEEE INFOCOM March 2004. Google ScholarDigital Library
Index Terms
- On the complexity of scheduling in wireless networks
Recommendations
Efficient interference-aware TDMA link scheduling for static wireless networks
MobiCom '06: Proceedings of the 12th annual international conference on Mobile computing and networkingWe study efficient link scheduling for a multihop wireless network to maximize its throughput. Efficient link scheduling can greatly reduce the interference effect of close-by transmissions. Unlike the previous studies that often assume a unit disk ...
Performance of multichannel wireless ad hoc networks
This paper addresses the design of Medium Access Control (MAC) protocols for wireless ad hoc networks that derive benefits from using multiple orthogonal channels for data transmission. Each node is assumed to have a single half-duplex transceiver that ...
EMDF - A Broadcast Scheduling Policy for Wireless Multi-hop Networks with Interference Constraint
ICYCS '08: Proceedings of the 2008 The 9th International Conference for Young Computer ScientistsWireless interference is a key issue affecting network performance. In this paper, we address the broadcast scheduling problem in wireless multi-hop networks with interference. We propose a policy called EMDF (Evolved Minimum Degree First) which assigns ...
Comments