A channel and rate assignment algorithm and a layer-2.5 forwarding paradigm for multi-radio wireless mesh networks

ABSTRACT

The availability of cost-effective wireless network interface cards makes it practical to design network devices with multiple radios which can be exploited to simultane-ously transmit/receive over different frequency channels. It has been shown that using multiple radios per node increases the throughput of multi-hop wireless mesh networks. However, multi-radios create several research challenges. A fundamental problem is the joint channel assignment and routing problem, i.e., how the channels can be assigned to radios and how a set of flow rates can be determined for every network link in order to achieve an anticipated objective. This joint problem is NP-com-plete. Thus, an approximate solution is developed by solving the channel assignment and the routing problems separately. The channel assignment problem turns out to be the problem to assign channels such that a given set of flow rates are schedulable and itself is shown to be also NP-complete. This paper shows that not only the channels but also the transmission rates of the links have to be properly selected to make a given set of flow rates schedulable. Thus, a greedy heuristic for the channel and rate assignment problem is developed. Algorithms to schedule the resulting set of flow rates have been proposed in the literature, which require synchronization among nodes and hence modified coordination functions. Unlike previous work, in this paper a forwarding paradigm is developed to achieve the resulting set of flow rates while using a standard MAC. A bi-dimensional Markov chain model of the proposed forwarding paradigm is presented to analyze its behavior. Thorough performance studies are con-ducted to: a) compare the proposed greedy heuristic to other channel assignment algorithms; b) analyze the behavior of the forwarding paradigm through numerical simulations based on the Markov chain model; c) simulate the operations of the forwarding paradigm and evaluate the achieved network throughput.

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: Y. Liu and E. Knightly, "Opportunistic fair scheduling over multiple wireless channels," in Proc. IEEE INFOCOM, 2003, vol. 2, pp. 1106-1115.
• 3: Jungmin So , Nitin H. Vaidya, Multi-channel mac for ad hoc networks: handling multi-channel hidden terminals using a single transceiver, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989487]
• 4: P. Kyasanur and N. H. Vaidya, "Routing and interface assignment in multi-channel multi-interface wireless networks," in Proc. IEEE WCNC, 2005, vol. 4, pp. 2051-2056.
• 5: Ashish Raniwala , Kartik Gopalan , Tzi-cker Chiueh, Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.8 n.2, April 2004 [doi>10.1145/997122.997130]
• 6: A. Raniwala and T. Chiueh, "Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network," in Proc. IEEE IN-FOCOM, 2005, vol. 3, pp. 2223-2234.
• 7: M. Alicherry, R. Bhatia, and E. Li, "Joint channel assignment and routing for throughput optimization in multiradio wireless mesh net-works," IEEE J. Sel. Areas Commun., vol. 24, no. 11, pp. 1960-1971, Nov. 2006.
• 8: Jian Tang , Guoliang Xue , Weiyi Zhang, Interference-aware topology control and QoS routing in multi-channel wireless mesh networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062700]
• 9: M. K. Marina and S. R. Das, "A topology control approach for uti-lizing multiple channels in multi-radio wireless mesh networks," in Proc. IEEE BroadNets, 2005, vol. 1, pp. 381-390.
• 10: K. N. Ramachandran, E. M. Belding, K. C. Almeroth, and M. M. Bud-dhikot, "Interference-aware channel assignment in multi-radio wireless mesh networks," in Proc. IEEE INFOCOM, 2006, pp. 1-12.
• 11: 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]
• 12: A. H. Mohsenian Rad and V. W. S. Wong, "Joint optimal channel as-signment and congestion control for multi-channel wireless mesh net-works," in Proc. IEEE ICC, 2006, vol. 5, pp. 1984-1989.
• 13: M. Chiang, "Balancing transport and physical layers in wireless mul-tihop networks: Jointly optimal congestion control and power control," IEEE J. Sel. Areas Commun., vol. 23, no. 1, pp. 104-116, 2005.
• 14: Steven H. Low, A duality model of TCP and queue management algorithms, IEEE/ACM Transactions on Networking (TON), v.11 n.4, p.525-536, August 2003 [doi>10.1109/TNET.2003.815297]
• 15: Daji Qiao , Sunghyun Choi , Kang G. Shin, Goodput Analysis and Link Adaptation for IEEE 802.11a Wireless LANs, IEEE Transactions on Mobile Computing, v.1 n.4, p.278-292, October 2002 [doi>10.1109/TMC.2002.1175541]
• 16: P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Trans. Inf. Theory, vol. 46, no. 2, pp. 388-404, Mar. 2000.
• 17: Kamal Jain , Jitendra Padhye , Venkata N. Padmanabhan , Lili Qiu, Impact of interference on multi-hop wireless network performance, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938993]
• 18: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 19: B. V. Cherkassky and A. V. Goldberg, "On implementing push-relabel method for the maximum flow problem," Algorithmica, vol. 19, pp. 390-410, 1997.
• 20: F. Ye, A. Chen, S. Lu, and L. Zhang, "A scalable solution to minimum cost forwarding in large sensor networks," in Proc. IEEE ICCCN, 2001, pp. 304-309.
• 21: C. Perkins , E. Belding-Royer , S. Das, Ad hoc On-Demand Distance Vector (AODV) Routing, RFC Editor, 2003
• 22: Alberto Caprara , Hans Kellerer , Ulrich Pferschy, The Multiple Subset Sum Problem, SIAM Journal on Optimization, v.11 n.2, p.308-319, 2000 [doi>10.1137/S1052623498348481]

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: Wireless communication; Network topology; Store and forward networks
      C.2.3 Network Operations
          Subjects: Network management

  E. Data
  E.4 CODING AND INFORMATION THEORY

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

General Terms:
Algorithms, Design, Management

Keywords:
channel assignment, layer-2.5 forwarding paradigm, multi-radio wireless mesh networks, physical model of interference