A genetic approach to channel assignment for multi-radio multi-channel wireless mesh networks

ABSTRACT

Multi-channel communication in a Wireless Mesh Network with routers having multiple radio interfaces significantly enhances the network capacity. Efficient channel assignment is critical for realization of optimal throughput in such networks. In this paper, we investigate the problem of finding the largest number of links that can be connected with the overall network interference is minimized. Since the number of radios on any node can be less than the number of available channels, the channel assignment must obey the constraint that the number of different channels assigned to the links incident on any node is at most the number of radio interfaces on that node. The above optimization problem is known to be NP-hard. By presenting the theoretical model, the above task is formulated as a multi-objective problem, and then a novel channel assignment based on improved NSGA-II is proposed. Extensive empirical evaluations represent that the novel algorithm proposed in this paper can implement network connectivity with little interference rapidly and efficiently. To meet the actual demand in wireless mesh network, ns-2 simulations are used to demonstrate the performance potential of our channel assignment algorithms in 802.11-based multi-radio mesh networks.

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: Raniwala, A. and Chiueh, T. 2005. Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network. In Proceedings of the 24th the IEEE International Conf. on Computer Communications (Miami, March 13--17, 2005). INFOCOM'05. IEEE press, 2223--2234.
• 3: 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
• 4: 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]
• 5: 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]
• 6: Jingpu Shi , Theodoros Salonidis , Edward W. Knightly, Starvation mitigation through multi-channel coordination in CSMA multi-hop wireless networks, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132929]
• 7: Raniwala, A. Chiueh, T. 2004. Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks. In Proceedings of the 10th Annual International Conference on Mobile Computing and Networking (Philadelphia, USA, Sep. 26--30, 2004). Mobicom'04. ACM press, New York, NY, 50--65.
• 8: Marina, M.K. and Das, S.R. 2005. A topology control approach for utilizing multiple channels in multi-radio wireless mesh networks. In Proceedings of the 2nd International Conference on Broadband Networks (Boston, USA, Oct. 03--07, 2005). Broadnets'05. IEEE Press, 381--390.
• 9: 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]
• 10: Gong, M., Midkiff, S., and Mao, S. 2005. A combined proactive routing and multi-channel MAC protocol for wireless ad hoc networks. In Proceedings of the 2nd International Conference on Broadband Networks (Boston, USA, Oct. 03--07, 2005). Broadnets'05. IEEE Press, 444--453.
• 11: Maheshwari, R., Gupta, H., and Das, S.R. 2006. Multichannel MAC protocols for wireless networks. In Proceedings of the Int'l Conf. on Sensor, Mesh and Ad Hoc Comm. and Networks (Reston, USA, Sep. 25--28, 2006). SECON'06. IEEE Press, 393--401.
• 12: Ramanuja Vedantham , Sandeep Kakumanu , Sriram Lakshmanan , Raghupathy Sivakumar, Component based channel assignment in single radio, multi-channel ad hoc networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161132]
• 13: Xue, Q. and Ganz, A. 2005. Temporal topology control in multi-channel multihop wireless access networks. In Proceedings of the 2nd International Conference on Broadband Networks (Boston, USA, Oct. 03--07, 2005). Broadnets'05. IEEE Press, 398--407.
• 14: Das, A.K., Alazemi, H.M.K., Vijayakumar, R., and Roy, S. 2005. Optimization models for fixed channel assignment in wireless mesh networks with multiple radios. In Proceedings of the Int'l Conf. Sensor and Ad Hoc Comm. and Networks (Santa Clara, USA, Sept. 26--29, 2005), SECON'05, 463--474.
• 15: Ramachandran, K.N., Belding, E.M., Almeroth, K.C., and Buddhikot, M.M. 2006. Interference-aware channel assignment in multi-radio wireless mesh networks. In Proceedings of the 25th IEEE International Conference on Computer Communications (Barcelona, Spain, April 23--29, 2006). INFOCOM'06, IEEE Press, 1--12.
• 16: Ko, B. Misra, V. Padhye, J. and Rubenstein, D. 2007. Distributed channel assignment in multi-radio 802.11 mesh networks. In Proceedings of IEEE Wireless Comm. and Networking Conf. (Hong Kong, China, March 11--15, 2007), WCNC'07, IEEE Press, 3978--3983.
• 17: Subramanian, A.P., Gupta, H., and Das, S.R. 2007. Minimum interference channel assignment in multi-radio wireless mesh networks. In Proceedings of the 4th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Comm. and Networks (San Diego, California, USA, June 18--21, 2007). SECON'07, IEEE Press, 481--490.
• 18: Gupta, P. and Kumar, P.R. 2000. The capacity of wireless networks. IEEE Transactions on Information Theory. 46(2): 388--404.
• 19: 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]
• 20: Kenneth A., Jong, D. Evolutionary Computation: A Unified Approach, MIT Press, 2006.
• 21: N. Srinivas , Kalyanmoy Deb, Muiltiobjective optimization using nondominated sorting in genetic algorithms, Evolutionary Computation, v.2 n.3, p.221-248, Fall 1994 [doi>10.1162/evco.1994.2.3.221]
• 22: Benson S.J. and Ye, Y. 2005. DSDP5: Software for Semi-Definite Programming. Technical Report ANL/MCS-P1289-0905, Mathematics and Computer Science Division, Argonne National Laboratory.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Design, Performance, Reliability

Keywords:
channel assignment, connectivity, genetic algorithm, interference, multi-radio multi-channel, wireless mesh networks