Distributed throughput maximization in wireless mesh networks via pre-partitioning

ABSTRACT

This paper considers the interaction between channel assignment and distributed scheduling in multi-channel multi-radio Wireless Mesh Networks (WMNs). Recently, a number of distributed scheduling algorithms for wireless networks have emerged. Due to their distributed operation, these algorithms can achieve only a fraction of the maximum possible throughput. As an alternative to increasing the throughput fraction by designing new algorithms, we present a novel approach that takes advantage of the inherent multi-radio capability of WMNs. We show that this capability can enable partitioning of the network into subnetworks in which simple distributed scheduling algorithms can achieve 100% throughput. The partitioning is based on the notion of Local Pooling. Using this notion, we characterize topologies in which 100% throughput can be achieved distributedly. These topologies are used in order to develop a number of centralized channel assignment algorithms that are based on a matroid intersection algorithm. These algorithms pre-partition a network in a manner that not only expands the capacity regions of the subnetworks but also allows distributed algorithms to achieve these capacity regions. We evaluate the performance of the algorithms via simulation and show that they significantly increase the distributedly achievable capacity region. We note that while the identified topologies are of general interference graphs, the partitioning algorithms are designed for networks with primary interference constraints.

REFERENCES

• 1: Atul Adya , Paramvir Bahl , Jitendra Padhye , Alec Wolman , Lidong Zhou, A Multi-Radio Unification Protocol for IEEE 802.11 Wireless Networks, Proceedings of the First International Conference on Broadband Networks, p.344-354, October 25-29, 2004 [doi>10.1109/BROADNETS.2004.8]
• 2: Ian F. Akyildiz , Xudong Wang , Weilin Wang, Wireless mesh networks: a survey, Computer Networks and ISDN Systems, v.47 n.4, p.445-487, 15 March 2005 [doi>10.1016/j.comnet.2004.12.001]
• 3: M. Alicherry, R. Bhatia, and L. E. Li, "Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks," IEEE J. Sel. Areas Commun., vol. 24, no. 11, pp. 1960-1971, Nov. 2006.
• 4: A. Brzezinski and E. Modiano, "Greedy weighted matching for scheduling the input-queued switch," in Proc. 40th Conf. Information Sciences and Systems (CISS'06), Mar. 2006, pp. 1738-1743.
• 5: Andrew Brzezinski , Gil Zussman , Eytan Modiano, Enabling distributed throughput maximization in wireless mesh networks: a partitioning approach, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161094]
• 6: P. Chaporkar, K. Kar, X. Luo, and S. Sarkar, "Throughput and fairness guarantees through maximal scheduling in wireless networks," IEEE Trans. Inf. Theory, vol. 54, no. 2, pp. 572-594, Feb. 2008.
• 7: L. Chen, S. H. Low, M. Chiang, and J. C. Doyle, "Cross-layer congestion control, routing and scheduling design in ad hoc wireless networks," in Proc. IEEE INFOCOM'06, Apr. 2006, pp. 1-13.
• 8: J. Dai and B. Prabhakar, "The throughput of data switches with and without speedup," in Proc. IEEE INFOCOM 2000, Mar. 2000, vol. 2, pp. 556-564.
• 9: A. Dimakis and J. Walrand, "Sufficient conditions for stability of longest queue first scheduling: Second order properties using fluid limits," Adv. Appl. Probabil., vol. 38, no. 2, pp. 505-521, June 2006.
• 10: H. N. Gabow and H. H. Westermann, "Forests, frames, and games: Algorithms for matroid sums and applications," Algorithmica, vol. 7, no. 5&6, pp. 465-497, 1992.
• 11: F. Harary, Graph Theory. Reading, MA: Addison-Wesley, 1969.
• 12: J.-H. Hoepman, "Simple distributed weighted matchings," Oct. 2004, eprint cs.DC/0410047.
• 13: Kamal Jain , Jitendra Padhye , Venkata N. Padmanabhan , Lili Qiu, Impact of interference on multi-hop wireless network performance, Wireless Networks, v.11 n.4, p.471-487, July 2005 [doi>10.1007/s11276-005-1769-9]
• 14: Murali Kodialam , Thyaga Nandagopal, Characterizing the capacity region in multi-radio multi-channel wireless mesh networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080837]
• 15: E. L. Lawler, Combinatorial Optimization: Networks and Matroids. New York: Holt, Rinehart and Winston, 1976.
• 16: X. Lin and S. Rasool, "Constant-time distributed scheduling policies for ad hoc wireless networks," in Proc. IEEE Conf. Decision and Control (CDC'06), Dec. 2006, pp. 1258-1263.
• 17: Xiaojun Lin , Ness B. Shroff, The impact of imperfect scheduling on cross-layer congestion control in wireless networks, IEEE/ACM Transactions on Networking (TON), v.14 n.2, p.302-315, April 2006 [doi>10.1109/TENT.2006.872546]
• 18: N. McKeown, A. Mekkittikul, V. Anantharam, and J. Walrand, "Achieving 100% throughput in an input-queued switch," IEEE Trans. Commun., vol. 47, no. 8, pp. 1260-1267, Aug. 1999.
• 19: Eytan Modiano , Devavrat Shah , Gil Zussman, Maximizing throughput in wireless networks via gossiping, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
• 20: M. Neely, E. Modiano, and C. Rohrs, "Dynamic power allocation and routing for time-varying wireless networks," IEEE J. Sel. Areas Commun., vol. 23, no. 1, pp. 89-103, Jan. 2005.
• 21: 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]
• 22: A. Raniwala and T.-C. Chiueh, "Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network," in Proc. IEEE INFOCOM'05, Mar. 2005, vol. 3, pp. 2223-2234.
• 23: L. Tassiulas and A. Ephremides, "Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks," IEEE Trans. Automat. Contr., vol. 37, no. 12, pp. 1936-1948, Dec. 1992.
• 24: X. Wu and R. Srikant, "Regulated maximal matching: A distributed scheduling algorithm for multi-hop wireless networks with node-exclusive spectrum sharing," in Proc. IEEE CDC-ECC'05, Dec. 2005, pp. 5342-5347.
• 25: G. Zussman, A. Brzezinski, and E. Modiano, "Multihop local pooling for distributed throughput maximization in wireless networks," in IEEE INFOCOM'08, Phoenix, AZ, Apr. 2008.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology; Wireless communication
      C.2.3 Network Operations
          Subjects: Network management
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

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

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Design, Management, Performance

Keywords:
channel assignment, distributed algorithms, local pooling, matroid intersection, scheduling, stability