Enabling distributed throughput maximization in wireless mesh networks: a partitioning approach

ABSTRACT

This paper considers the interaction between channel assignment and distributed scheduling in multi-channel multiradio 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, in this paper 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 recently introduced 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 channel assignment algorithms that are based on a matroid intersection algorithm. These algorithms 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. Finally, we evaluate the performance of the algorithms via simulation and show that they significantly increase the distributedly achievable capacity region.

REFERENCES

• 1: 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]
• 2: Mansoor Alicherry , Randeep Bhatia , Li (Erran) Li, Joint channel assignment and routing for throughput optimization in multi-radio 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.1080836]
• 3: 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 (BROADNETS'04), p.344-354, October 25-29, 2004 [doi>10.1109/BROADNETS.2004.8]
• 4: R. Bhatia, A. Segall, and G. Zussman. Analysis of bandwidth allocation algorithms for wireless personal area networks. To appear in ACM/Springer Wireless Networks, 12, 2006.
• 5: A. Brzezinski and E. Modiano. Greedy weigthed matching for scheduling the input-queued switch. In Proc. CISS '06, March 2006.
• 6: A. Brzezinski, G. Zussman, and E. Modiano. Enabling distributed throughput maximization in wireless mesh networks via local pooling. MIT/LIDS Technical Report #2696, March 2006.
• 7: P. Chaporkar, K. Kar, and S. Sarkar. Throughput guarantees through maximal scheduling in wireless networks. In Proc. Allerton Conf. on Commun., Control, and Comp., September 2005.
• 8: L. Chen, S. H. Low, M. Chiang, and J. C. Doyle. Optimal cross-layer congestion control, routing and scheduling design in ad hoc wireless networks. In Proc. IEEE INFOCOM '06, April 2006.
• 9: J. Dai and B. Prabhakar. The throughput of data switches with and without speedup. In Proc. IEEE INFOCOM '00, March 2000.
• 10: A. Dimakis and J. Walrand. Sufficient conditions for stability of longest queue first scheduling: second order properties using fluid limits. Advances of Applied Probability, 38(2):505--521, June 2006.
• 11: H. N. Gabow and H. H. Westermann. Forests, frames, and games: algorithms for matroid sums and applications. Algorithmica 7(5&6):465--497, 1992.
• 12: F. Harary. Graph Thoery, Addison-Wesley, Reading, MA, 1969.
• 13: J.-H. Hoepman. Simple distributed weighted matchings. eprint cs.DC/0410047, October 2004.
• 14: 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]
• 15: 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]
• 16: E. L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York, 1976.
• 17: X. Lin and N.B. Shroff. The impact of imperfect scheduling on cross-layer rate control in wireless networks. In Proc. IEEE INFOCOM '05, March 2005.
• 18: N. McKeown, A. Mekkittikul, V. Anantharam, and J. Walrand. Achieving 100% throughput in an input-queued switch. IEEE Trans. Commun., 47(8):1260--1267, August 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., 23(1):89--103, January 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, March 2005.
• 23: S. Sarkar, P. Chaporkar, and K. Kar. Fairness and throughput guarantees with maximal scheduling in multihop wireless networks. In Proc. WiOpt'06, April 2006.
• 24: L. Tassiulas and A. Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. Autom. Control, 37(12):1936--1948, December 1992.
• 25: 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, December 2005.
• 26: Gil Zussman , Adrian Segall, Capacity assignment in Bluetooth scatternets: optimal and heuristic algorithms, Mobile Networks and Applications, v.9 n.1, p.49-61, Feburary 2004 [doi>10.1023/A:1027321806934]

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:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design, Performance

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