A Maximum Concurrent Network Flow Based Channel Assignment Algorithm for Wireless Mesh Networks

Abstract:

We proposed a maximum concurrent network flow based channel assignment algorithm (MCFCA) for wireless networks. In the MCFCA algorithm, we first use the maximum concurrent network flow algorithm to compute the maximum network capacity, then we assign each link a priority according to its link throughput, finally the channel is assigned to minimize the interference between neighbor nodes in the priority order. Performance simulation shows its effectiveness in channel assignment.

• Periodical: Applied Mechanics and Materials (Volumes 427-429)
• Pages: 2212-2216
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.427-429.2212
• Online since: September 2013
• Authors: Lei Zhang*, Xue Hui Wang
• Keywords: Channel Assignment Algorithm, Maximum Concurrent Network Flow, Performance Simulation, Wireless Mesh Network (WMN)

References

[1] R. Draves, J. Padhye, and B. Zill, Routing in multi-radio, multi-hop wireless mesh networks, in Algoritmica, 18, (1997).

DOI: 10.1145/1023720.1023732

[2] A. Raniwala, K. Gopalan, and T. Chiueh, Centralized Channel Assignment and Routing Algorithms for Multichannel Wireless Mesh Networks, ACM Mobile Comp. and Commun. Rev., Apr. 2004, p.50–65.

DOI: 10.1145/997122.997130

[3] K. Ramachandran, K. Almeroth, E. Belding-Royer, and M. Buddhikot, Interference aware channel assignment in multi-radio wireless mesh networks, in Proc. IEEE Infocom, (2006).

DOI: 10.1109/infocom.2006.177

[4] M. Marina and S. R. Das, A toplogy control approach for utilizing multiple channels in multi-radio wireless mesh networks, " in Proc. IEEE Broadnets, 05, pp.381-390, (2005).

DOI: 10.1109/icbn.2005.1589641

[5] Piyush Gupta and P.R. Kumar, The capacity of wireless networks, IEEE Transcations Information Theory, vol. 46, no. 2, pp.388-404, (2000).

[6] A. Subramanian, H. Gupta, and S. R. Das, Minimum-interference channel assignment in multi-radio wireless mesh networks, Student Poster Session, 13th International Conference on Network Protocols(ICNP), (2005).

DOI: 10.1109/sahcn.2007.4292860

[7] A. Coja-Oghlan, C. Moore, and V. Sanwalani. MAX k-CUT and Approximating the Chromatic Number of Random Graphs. In ICALP, (2003).

DOI: 10.1007/3-540-45061-0_18

[8] Arindam K. Das, Hamed M.K. Alazemi, Rajiv vijayakumar and Sumit Roy, Optimization models for fixed channel assignment in wireless mesh networks with multiple radios, in Proc. 2nd Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks(SECON), Santa Clara, CA, Sep. 2005, pp.463-474.

DOI: 10.1109/sahcn.2005.1557099

[9] A. Raniwala, K. Gopalan, and T. Chiueh, Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks, ACM Mobile Computing and Communications Review, (2004).

DOI: 10.1145/997122.997130

[10] H. Skalli, S. Ghosh, S. K. Das, L. Lenzini, and M. Conti, Channel assignment strategies for multi-radio wireless mesh networks: Issues and solutions, " IEEE communications Magzine, Special Issue on "Wireless Mesh Networks, Nov. (2007).

DOI: 10.1007/978-0-387-68839-8_5

[11] A. H. M. Rad and V. W. S. Wong, Logical topology design and interface assignment for multi-channel wireless mesh networks, in Proc. IEEE global Telecommunications Conference, (2006).

DOI: 10.1109/glocom.2006.985

[12] Li Li, Qin, Bin, Chunyuan Zhang. Interference-Aware Broadcast Routing and Channel Assignment in Multi-Radio Wireless Mesh Networks. Vehicular Technology Conference Fall, (2009).

DOI: 10.1109/vetecf.2009.5378930

[13] Yan Xia, Zhenghu Gong, Yingzhi Zeng. A Novel Channel Assignment Scheme for Multi-channel Wireless Mesh Networks. Communications in Computer and Information Science Volume 119, 2010, pp.15-22.

DOI: 10.1007/978-3-642-17587-9_3

[14] Lei Zhang, Xuehui Wang, Wenhua Dou. A Distributed Topology Control Algorithm for Heterogeneous Ad Hoc Networks. Parallel and Distributed Computing: Applications and Technologies. Lecture Notes in Computer Science Volume 3320, 2005, pp.681-684.

DOI: 10.1007/978-3-540-30501-9_131

[15] Mansoor Alicherry, Randeep Bhatia, Li (Erran) Li, Joint Channel Assignment and Routing for Throughput Optimization in Multi-radio Wireless Mesh Networks, Proceedings of ACM MOBICOM, (2005).

DOI: 10.1007/978-1-4939-2864-4_67

[16] Daniel Wu, Prasant Mohapatra, From Theory to Practice: Evaluating Static Channel Assignments on a Wireless Mesh Network, Proceedings of IEEE Infocom, (2010).

DOI: 10.1109/infcom.2010.5462254

[17] W. Peng and X. Lu. AHBP: An Efficient Broadcast Protocol for Mobile Ad Hoc Networks, J. Science and Technology, (2002).