Channel assignment with partially overlapping channels in wireless mesh networks

ABSTRACT

Many efforts have been devoted to maximizing the network throughput with limited channel resources in multi-radio multi-channel wireless mesh networks. It has been believed that the limited spectrum resource can be fully exploited by utilizing partially overlapping channels in addition to non-overlapping channels in 802.11b/g networks. However, there are only few studies of channel assignment algorithms for partially overlapping channels. In this paper, an extension to the traditional conflict graph model, weighted conflict graph, is proposed to model the interference between wireless links more accurately. Based on this model, we first present a greedy algorithm for partially overlapping channel assignment, and then propose a novel genetic algorithm, which has the potential to obtain better solutions. Through evaluation, we demonstrate that the network performance can be dramatically improved by properly utilizing the partially overlapping channels. In addition, the genetic algorithm outperforms the greedy algorithm in mitigating the interference within the network and therefore leads to higher network throughput.

REFERENCES

• 1: I. F. Akyildiz, X. Wang, and W. Wang, "Wireless mesh networks: a survey", in Computer Networks, 2005.
• 2: 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]
• 3: 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]
• 4: 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]
• 5: 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]
• 6: A. Raniwala and T. cker Chiueh, "Architecture and algorithms for an ieee 802.11-based multi-channel wireless mesh network", in INFOCOM, 2005.
• 7: 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]
• 8: A. P. Subramaniam, H. Gupta, and S. R. Das, "Minimum-interference channel assignment in multi-radio wireless mesh networks", in Technical Report, 2006.
• 9: K. N. Ramachandran, E. M. Belding, K. C. Almeroth, and M. M. Buddhikot, "Interference-aware channel assignment in multi-radio wireless mesh networks", in INFOCOM, 2006.
• 10: S.-L. Wu , C.-Y Lin , Y.-C. Tseng , J.-P. Sheu, A New Multi-Channel MAC Protocol with On-Demand Channel Assignment for Multi-Hop Mobile Ad Hoc Networks, Proceedings of the 2000 International Symposium on Parallel Architectures, Algorithms and Networks, p.232, December 07-07, 2000
• 11: 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]
• 12: Paramvir Bahl , Ranveer Chandra , John Dunagan, SSCH: slotted seeded channel hopping for capacity improvement in IEEE 802.11 ad-hoc wireless networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023742]
• 13: Arunesh Mishra , Eric Rozner , Suman Banerjee , William Arbaugh, Exploiting partially overlapping channels in wireless networks: turning a peril into an advantage, Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, p.29-29, October 19-21, 2005, Berkeley, CA
• 14: Arunesh Mishra , Suman Banerjee , William Arbaugh, Weighted coloring based channel assignment for WLANs, ACM SIGMOBILE Mobile Computing and Communications Review, v.9 n.3, July 2005 [doi>10.1145/1094549.1094554]
• 15: Arunesh Mishra , Vivek Shrivastava , Suman Banerjee , William Arbaugh, Partially overlapped channels not considered harmful, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
• 16: W. Yue, K. Miyazaki, and X. Deng, "Optimal channel assignment in wireless communication networks with distance and frequency interferences", in Computer Communications, 2004.
• 17: Daniel Aguayo , John Bicket , Sanjit Biswas , Glenn Judd , Robert Morris, Link-level measurements from an 802.11b mesh network, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 18: Jitendra Padhye , Sharad Agarwal , Venkata N. Padmanabhan , Lili Qiu , Ananth Rao , Brian Zill, Estimation of link interference in static multi-hop wireless networks, Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, p.28-28, October 19-21, 2005, Berkeley, CA
• 19: Bhaskaran Raman , Kameswari Chebrolu, Design and evaluation of a new MAC protocol for long-distance 802.11 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.1080847]
• 20: B. Raman, "Channel allocation in 802.11-based mesh networks", in INFOCOM, 2006.
• 21: Richard Draves , Jitendra Padhye , Brian Zill, Comparison of routing metrics for static multi-hop wireless networks, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 22: Richard Draves , Jitendra Padhye , Brian Zill, Routing in multi-radio, multi-hop wireless mesh networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023732]
• 23: Albert Gräf, Distance graphs and the T-coloring problem, Discrete Mathematics, v.196 n.1-3, p.153-166, Feb. 6, 1999 [doi>10.1016/S0012-365X(98)00199-X]
• 24: T. M. Michell, Machine Learning, N. Y. Mc Graw Hill, Ed., 1997.
• 25: "Hyacinth: An ieee 802.11-based multi-channel wireless mesh network, http://www.ecsl.cs.sunysb.edu/multichannel/."
• 26: "http://www.cc.gatech.edu/fac/ellen.zegura/graphs.html."

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Performance

Keywords:
channel assignment, genetic algorithm, partially overlapping channel, wireless mesh networks