基于穷举搜索的无线Mesh网络分配信道可行性研究
|
摘要
信道分配问题在多天线无线Mesh网络中已被各种文献证明是NP难问题。分析了一般的信道分配问题的复杂性与某些基本和常见的属性。结果表明,不同信道分配数量的复杂度和无线链路的数量呈指数关系。此外,估计了通过穷举搜索确定最优信道分配的理论运行时间,并通过实验验证。实验表明,给予一定的计算能力(如一个现成的笔记本电脑),在小规模和中等规模的商业无线Mesh网络中,对于最优解决信道分配问题是可行的。
The channel assignment problem in multi-radio wireless Mesh networks(WMNs)is the NP-hard problem proved by various literatures. The complexity of the general channel assignment problem is analyzed,as well as a certain basic and common properties. The results show that the complexity of different possible channel assignment quantity has exponent relation to the wireless link quantity. Furthermore,the theoretical runtime of optimal channel assignment determined by exhaustive search was estimated,and verified with experiments. The experimental results show that,giving a certain computing power(notebook PC),it is feasible to solve the optimal channel assignment problem in small-and medium-scale commercial WMNs.
The channel assignment problem in multi-radio wireless Mesh networks(WMNs)is the NP-hard problem proved by various literatures. The complexity of the general channel assignment problem is analyzed,as well as a certain basic and common properties. The results show that the complexity of different possible channel assignment quantity has exponent relation to the wireless link quantity. Furthermore,the theoretical runtime of optimal channel assignment determined by exhaustive search was estimated,and verified with experiments. The experimental results show that,giving a certain computing power(notebook PC),it is feasible to solve the optimal channel assignment problem in small-and medium-scale commercial WMNs.
引文
[1]AKYILDIZ I F,WANG X,WANG W.Wireless mesh networks:a survey[J].Computer networks&ISDN systems,2005,47(3):445-487.
[2]夏汉铸,刘辉元.无线Mesh网络中基于信道状态的动态信道分配算法研究[J].重庆邮电大学学报(自然科学版),2014,26(3):362-366.XIA Hanzhu,LIU Huiyuan.Channel-state-based dynamic channel assignment algorithm in multichannel wireless Mesh networks[J].Journal of Chongqing University of Posts and Telecommunications(natural science edition),2014,26(3):362-366.
[3]乐光学,李明明,丁辉,等.无线Mesh网络中基于演化博弈的抗振荡信道分配策略[J].电子学报,2016,44(1):176-185.YUE Guangxue,LI Mingming,DING Hui,et al.The antichannel oscillation channel assignment scheme based on evolutionary game in wireless Mesh network[J].Acta electronica sinica,2016,44(1):176-185.
[4]王子凡,刘作学,代健美.基于干扰感知的多接口无线Mesh网络信道分配算法[J].现代电子技术,2014,37(14):24-27.WANG Zifan,LIU Zuoxue,DAI Jianmei.Interference-aware based channel assignment algorithm for multi-interface wireless Mesh networks[J].Modern electronics technique,2014,37(14):24-27.
[5]张伟昆,黄炜,张大伟.基于连接低干扰的无线Mesh网络信道分配算法研究[J].电子科技大学学报,2014,43(6):817-822.ZHANG Weikun,HUANG Wei,ZHANG Dawei.A study of wireless Mesh networks based on connected low interference channel assignment algorithm[J].Journal of University of Electronic Science and Technology of China,2014,43(6):817-822.
[6]张绳武,曾锋,陈志刚.无线Mesh网中一种流量感知和干扰优化的信道分配机制[J].计算机应用研究,2016,33(3):810-812.ZHANG Shengwu,ZENG Feng,CHEN Zhigang.Traffic-aware and interference optimized channel assignment mechanism in wireless Mesh network[J].Application research of computers,2016,33(3):810-812.
[7]WU Di,YANG S H,BAO Lichun,et al.Joint multi-radio multi-channel assignment,scheduling,and routing in wireless mesh networks[J].Wireless networks,2014,20(1):11-24.
[8]ULUCINAR A R,KORPEOGLU I.Distributed joint flow-radio and channel assignment using partially overlapping channels in multi-radio wireless mesh networks[J].Wireless networks,2016,22(1):83-104.
[9]CHENG Hongju,XIONG Naixue,CHEN G,et al.Links organization for channel assignment in multi-radio wireless mesh networks[J].Multimedia tools&applications,2013,65(2):239-258.
[10]RANIWALA A,GOPALAN K,CHIUEH T.Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks[J].ACM mobile computing and communications review,2004,8(2):50-65.
[11]DAS S M,PUCHA H,KOUTSONIKOLAS D,et al.DMesh:incorporating practical directional antennas in multi-channel wireless mesh networks[J].IEEE journal on selected areas in communications,2006,24(11):2028-2039.
[2]夏汉铸,刘辉元.无线Mesh网络中基于信道状态的动态信道分配算法研究[J].重庆邮电大学学报(自然科学版),2014,26(3):362-366.XIA Hanzhu,LIU Huiyuan.Channel-state-based dynamic channel assignment algorithm in multichannel wireless Mesh networks[J].Journal of Chongqing University of Posts and Telecommunications(natural science edition),2014,26(3):362-366.
[3]乐光学,李明明,丁辉,等.无线Mesh网络中基于演化博弈的抗振荡信道分配策略[J].电子学报,2016,44(1):176-185.YUE Guangxue,LI Mingming,DING Hui,et al.The antichannel oscillation channel assignment scheme based on evolutionary game in wireless Mesh network[J].Acta electronica sinica,2016,44(1):176-185.
[4]王子凡,刘作学,代健美.基于干扰感知的多接口无线Mesh网络信道分配算法[J].现代电子技术,2014,37(14):24-27.WANG Zifan,LIU Zuoxue,DAI Jianmei.Interference-aware based channel assignment algorithm for multi-interface wireless Mesh networks[J].Modern electronics technique,2014,37(14):24-27.
[5]张伟昆,黄炜,张大伟.基于连接低干扰的无线Mesh网络信道分配算法研究[J].电子科技大学学报,2014,43(6):817-822.ZHANG Weikun,HUANG Wei,ZHANG Dawei.A study of wireless Mesh networks based on connected low interference channel assignment algorithm[J].Journal of University of Electronic Science and Technology of China,2014,43(6):817-822.
[6]张绳武,曾锋,陈志刚.无线Mesh网中一种流量感知和干扰优化的信道分配机制[J].计算机应用研究,2016,33(3):810-812.ZHANG Shengwu,ZENG Feng,CHEN Zhigang.Traffic-aware and interference optimized channel assignment mechanism in wireless Mesh network[J].Application research of computers,2016,33(3):810-812.
[7]WU Di,YANG S H,BAO Lichun,et al.Joint multi-radio multi-channel assignment,scheduling,and routing in wireless mesh networks[J].Wireless networks,2014,20(1):11-24.
[8]ULUCINAR A R,KORPEOGLU I.Distributed joint flow-radio and channel assignment using partially overlapping channels in multi-radio wireless mesh networks[J].Wireless networks,2016,22(1):83-104.
[9]CHENG Hongju,XIONG Naixue,CHEN G,et al.Links organization for channel assignment in multi-radio wireless mesh networks[J].Multimedia tools&applications,2013,65(2):239-258.
[10]RANIWALA A,GOPALAN K,CHIUEH T.Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks[J].ACM mobile computing and communications review,2004,8(2):50-65.
[11]DAS S M,PUCHA H,KOUTSONIKOLAS D,et al.DMesh:incorporating practical directional antennas in multi-channel wireless mesh networks[J].IEEE journal on selected areas in communications,2006,24(11):2028-2039.