基于SIR冲突图和最大独立集的无线Mesh网络信道分配方案

戴 冬， 卫 娟， 王 磊

(1.河南工学院 计算机科学与技术系，河南 新乡 453003;2.西南财经大学 经济信息工程学院，四川 成都 610074)



基于SIR冲突图和最大独立集的无线Mesh网络信道分配方案

戴 冬1， 卫 娟1， 王 磊2*

(1.河南工学院 计算机科学与技术系，河南 新乡 453003;2.西南财经大学 经济信息工程学院，四川 成都 610074)

针对现有无线Mesh网络信道分配方案中的冲突模型不能反映真实网络干扰，提出一种基于信号干扰比(SIR)冲突图和最大独立集的信道分配方案.首先，由于射频信号的反射干扰远高于噪声，所以利用节点间的SIR代替传统信号干扰噪声比(SINR)来构建冲突图，同时考虑了节点累积干扰.然后，在冲突图基础上，通过提出的信道分配算法构建节点最大独立集，最终获得最低干扰的信道分配方案.实验结果表明，该方案在不同节点度下都具有较低的干扰比例和较高的网络吞吐量.

无线Mesh网络；信道分配；冲突图；信号干扰比；最大独立集

无线Mesh网络(WMN)是一种由网关、无线路由器和移动站组成的网络[1].WMN的多跳特性和快速增长的吞吐量需求使其形成多信道、多接口的网状网络[2]，然而这也增加了信道之间的干扰[3].在WMN中，信道分配是一种NP-Hard问题.最近十年间，研究者提出了多种信道分配方法.[4]提出一种基于集中式算法的信道分配方法，该方法提供了一种结合连通性和流量模式的信号分配方法，但是会导致一系列连锁反应，即已经分配的链路会重新被访问，增加了时间复杂度. [5]提出一种基于禁忌搜索的图着色算法(TABU)，然而，该算法通过迭代共享分配的两种无线电来避免冲突增加，因此，增加了复杂度且降低了系统性能.[6]提出一种基于离散粒子群优化算法(DPSO)的拓扑保形信道分配策略，以最小化网络中的信道干扰为目标，通过粒子运动来寻找最优解.然而，这些方案都在基于传统信号干扰噪声比(SINR)模型的冲突图上执行[7]，只有构建出能够真切反映网络干扰情况的冲突图，才能有效合理分配信道并降低干扰.传统SINR模型不能反映无线连接中信号传播的实际情况.在真实的无线信道中，射频信号会从附近物体反射回来并围绕物体，这导致了信号强度在空间内波动[8].由于同波段干扰远高于噪声，所以本文使用信号干扰比(SIR)代替传统SINR，提出一种基于SIR冲突图和最大独立集的WMN信道分配方案.首先，基于节点间的SIR和累积干扰构建网络冲突图.然后，在冲突图上，通过提出的信道分配算法构建节点最大独立集，最终获得最低干扰的信道分配方案.实验结果表明，本文方案具有较低的干扰比例和较高的网络吞吐量.

1 基于SIR模型的冲突图

不同于包含1(表示冲突)和0(表示非冲突)的传统冲突图矩阵[9]，本文基于SIR模型冲突图中的冲突矩阵元素为1和一个链接从其他链接接收到的最大功率.冲突图的输入如下：f：频率；Gt：发射器的增益；Gr：接收器的增益；ht：发射器天线的高度；hr：接收器天线的高度；n：节点数量；RxThresh_dBm：dBm中的接收阈值；SIRThresh_dB：dB中的SIR阈值；L：路由中包含的链接集；locations_x：节点横坐标集；locations_y：节点纵坐标集.

输入:f、Gr、ht、hr、n、RxThresh_dBm、SIRThresh_dB、L、locations_x、locations_y.输出:冲突图conflict_matrix1.RxThresh_mwatts←10SIRThresh_dB/10()2.SIRThresh←10SIRThresh_dB/10()3.m←L4.Fori=1ton:5.Forj=1ton:6.dist_alli,j()←节点i和节点j之间的距离7.endFor8.endFor9.Fori=1tom:10.Li,3()←链接i中两节点之间的距离11.Li,4()←链接i的传输功率12.endFor13.初始化一个m×mconflict_matrix14.Fori1=1tom:15.初始化一个空的冲突表16.Forj=1tom:17.conflict_tablej,1()←链接i1上的节点x18.conflict_tablej,2()←链接i1上的节点y19.conflict_tablej,3()←链接j上的节点p20.conflict_tablej,4()←链接j上的节点q21.Pr,xp←使用公式(2)或(4)得到的链接i1上的节点x从链接j上的节点p接收的功率22.Pr,xq←使用公式(2)或(4)得到的链接i1上的节点x从链接j上的节点q接收的功率23.Pr,yp←使用公式(2)或(4)得到的链接i1上的节点y从链接j上的节点p接收的功率24.Pr,yq←使用公式(2)或(4)得到的链接i1上的节点y从链接j上的节点q接收的功率25.conflict_tablej,5()←Pr,xp26.conflict_tablej,6()←Pr,xq27.conflict_tablej,7()←Pr,yp28.conflict_tablej,8()←Pr,yq29.conflict_tablej,9()←maxPr,xp,Pr,xq,Pr,yp,Pr,yq()30.conflict_tablej,10()←RxThresh_mwatts/maxPr,xp,Pr,xq,Pr,yp,Pr,yq()31.endFor32.Fori2=1tom:33.如果conflict_tablei2,10()>SIRThresh:34.conflict_matrixi1,i2()←conflict_tablei2,9()35.endIf36.endFor37.endFor38.输出conflict_matrix结束

图1 基于SIR模型构建冲突图过程

Fig.1 Theprocess of building conflict graph based on the SIR model

2 基于冲突图的信道分配

本文信道分配算法的基本思想是：首先从冲突图中选择具有最大节点度的顶点并将该顶点加入到建设中的临时WMIS中.然后逐一检查该冲突图的其他顶点，如果这些顶点没有边与已在该集合中的任何顶点连接，那么将其放入WMIS中.然而，上述思想考虑了单一干扰，为了进一步提高其实用性，本文添加考虑了累积干扰，即WMIS上每个顶点的累积SIR都必须比SIR阈值大，其中，一个顶点的累积SIR为RxThresh_mwatts与从WMIS中所有其他顶点接收的最大功率总和的比值.这解释了WMIS中一个顶点从该集合中所有其他顶点受到的累积干扰.那么，此时本文信道分配算法可描述为，如果一个顶点w不受到WMIS中顶点的干扰，那么将w和该顶点加入到WMIS的一个临时集合中.如果此时临时集合中的每个顶点从该集合中的所有其他顶点得到累积SIR都大于SIR阈值，那么就将w加入WMIS.图2显示了本文提出的信道分配算法的伪代码.

3 实验及分析

3.1 网络环境

利用NS-2网络仿真器构建500 m×500 m大小的无线Mesh网络，并划分成单元格，将节点随机放入单元格中，构建10个包含51个节点的不同拓扑结构的网络.将节点15设定为网关节点，并放置在网络中央，用于汇聚各节点信息.那么，网络中存在35个流量源，通过不同路径到达网关节点.为了构建基于SIR模型的冲突图，本文设定通信频率为5.805 GHz，Gt和Gr都为1，ht和hr都为3 m，接收SIR阈值为65 dBm，链接数据率为24 Mbps，网络中可用信道数为12.

输入:L:路由包含链接的集合;FVF,EF():冲突图;SIRThresh_dB:SIR在dB中的阈值;RxThresh_dBm:dB中接收器的阈值.输出:VWMIS:顶点的WMIS;LWMIS:中相应于WMIS中顶点的链接的集合;c:WMIS的数量.1.c←02.m←L=VF3.SIRThresh←10SIRThresh_dB/10()4.RxThresh_mwatts←10SIRThresh_dB/10()5.当m≥16.如果F是全连接或m=1dist_alli,j()←节点i和节点j之间的距离7.Ford=1tom:8.初始化空的VWMIS和LWMIS9.将顶点d添加到VWMIS并且将相应的链接添加到LWMIS10.输出VWMIS和LWMIS11.c←c+112.endFor13.输出c和信道14.endIf15.初始化空的VWMIS和LWMIS16.将F中具有最大节点度的顶点添加到VWMIS并将相应的链接添加到LWMIS17.Fori=1tom:18.如果顶点i与VWMIS中的节点没有界限:19.Vtemp←VWMIS∪i20.endIf21.如果Vtemp中的每个顶点从Vtemp中其他顶点得到的累积SIR大于SIRThresh:22.将顶点i添加到VWMIS并将相应的链接添加到LWMIS23.endIf24.endFor25.输出VWMIS和LWMIS26.c←c+127.VF←VFVWMIS28.L←LLWMIS29.m←L30.endWhile31.输出c结束

图2 本文提出的信道分配算法

Fig.2 The channel allocation algorithm

3.2 性能比较

本文在网络干扰比例和网络吞吐量方面，与[5]提出的禁忌搜索方案和[6]提出的离散粒子群方案进行比较，其中网络干扰比例为受干扰的链接占所有链接的数量，网络吞吐量为网络中所有50个流量源所传输的流量总和.实验中，设定节点度(NDC)为2～7不同的场景.通常节点度越多(即链路数量越多)，干扰越强[12].实验中的数据都为在10个不同拓扑结构网络上实验结果的平均值.

图3显示了节点具备不同节点度时的网络干扰比值.可以看出，随着节点度的增加，网络干扰量也在增加，这是因为每个节点与其他节点的链路增加，但网络信道数量是一定的，所以增加了链路间的干扰概率.其中，本文方案具有最低的网络干扰比例，在NDC=2时，约为0.8%；NDC=7时，约为7.9%，明显低于其他两种方案.这是因为，本文方案利用SIR构建冲突图，并考虑了累积干扰，同时利用提出的信道分配算法获得顶点加权最大独立集(WMIS)，实现了网络的最低干扰.

图4显示了不同节点度下的网络总吞吐量.同样，随着节点度的增加，网络吞吐量也增加，但达到一定程度后趋于稳定.这是因为节点度的增加使网络中链路数量增加，从而使节点发送数据的量增加，最终提高了网络吞吐量.但增加链路数量也增加了网络干扰，影响了吞吐量，所以最终会趋于稳定.其中，本文方案具有最高的吞吐量.例如，在节点具有4个接口时，与[5]和[6]相比，吞吐量分别提高了25.6%和10.7%.

4 结 论

由于在障碍物较多的环境中，射频信号的反射干扰远高于噪声，传统基于SINR构建的冲突图不能反映真实网络干扰情况.为此，提出了一种基于信号干扰比(SIR)冲突图和最大独立集的信道分配方案.利用SIR模型构建冲突图，并利用提出的分配算法构建节点最大独立集，获得干扰最低的信道分配方案.与现有方案相比，本文方案获得了较低的干扰和较高的网络吞吐量.

[1] 邝祝芳, 陈志刚. 认知无线Mesh网络中一种有效的多目标优化频谱分配算法[J]. 中南大学学报：自然科学版, 2013, 44(6):124-129.

[2] 黄向党, 羊秋玲, 金志刚. 无线Mesh网络延迟及丢包控制机制研究[J]. 湘潭大学自然科学学报, 2013, 35(3):95-101.

[3] PENG Y, YU Y, GUO L, et al. An efficient joint channel assignment and Q∘S routing protocol for IEEE 802.11 multi-radio multi-channel wireless mesh networks[J]. Journal of Network and Computer Applications, 2013, 36(2): 843-857.

[4] LIN T Y,HSIEH K C,HUANG H C. Applying genetic algorithms for multiradio wireless mesh network planning[J]. Vehicular Technology, Transactions on IEEE, 2012, 61(5):2 256-2 270.

[5] GIRGIS M R, MAHMOUD T M, ABDULLATIF B A, et al. Solving the wireless mesh network design problem using genetic algorithm and tabu search optimization methods[J]. Ijcnwc Org, 2014, 4(11):2 250-3 501.

[6] VAEZPOUR E, DEHGHAN M. Evolutionary-based channel assignment in multi-radio multi-channel wireless mesh networks for multicast applications[J]. International Journal of Ad Hoc & Ubiquitous Computing, 2013, 13(1):38-47.

[7] 胡首都, 胡捍英, 仵国锋. 一种认知无线电网络接入控制和功率控制联合设计[J]. 计算机应用与软件, 2011, 28(9):70-72.

[8] 田启明, 余官定. 无线Mesh网络中基于信道流量干扰感知的路由协议[J]. 计算机应用研究, 2011, 28(6):2 254-2 256.

[9] SIRIS V A, DELAKIS M. Interference-aware channel assignment in a metropolitan multi-radio wireless mesh network with directional antennas[J]. Computer Communications, 2011, 34(12):1 518-1 528.

[10] 谢琦, 黄廷磊. 基于节点度优化的无线mesh网络拓扑控制算法[J]. 桂林电子科技大学学报, 2012, 32(3):233-236.

[11] ZHU G, JIANG X, WU C, et al. A cluster head selection algorithms in wireless network based on maximal weighted independent set[C]// Ubiquitous Information Technologies and Applications (CUTE), 2010 Proceedings of the 5th International Conference on IEEE, 2010:1-6.

[12] 邱振谋, 姚国祥, 官全龙,等. 多信道无线Mesh网络的多播信道分配算法[J]. 计算机工程, 2011, 37(6):107-109.

责任编辑：龙顺潮

Wireless Mesh Network Channel Assignment Scheme Based on SIR Conflict Graph and Maximal Independent Set

DAIDong1,WEIJuan1,WANGLei2*

(1.Department of Computer Science and Technology, Henan Institute of Technology, Xinxiang 453003; 2.College of Economic Information Engineering, Southwestern University of Finance and Economics, Chengdu 610074 China)

For the issues that the existing conflict model in wireless Mesh network channel allocation scheme can not reflect the real network interference, a channel assignment scheme based on signal interference ratio (SIR) conflict graph and maximum independent set is proposed. Firstly, because the reflection interference of radio frequency signal is much higher than the noise, the SIR is used to instead the traditional signal to interference noise ratio (SINR) for constructing the conflict graph. Then, the maximum independent set of nodes is constructed by the proposed channel assignment algorithm based on the conflict graph, and the minimum interference channel allocation scheme is obtained. Experimental results show that the proposed scheme has a lower interference ratio and higher network throughput at different node degrees.

wireless mesh network; channel assignment; conflict graph; signal interference ratio; maximal independent set

2016-02-17

国家自然科学基金(71473201)；中央高校基本科研业务费重大基础理论研究项目(JBK151127)；河南省高等学校重点科研项目(16A520048，15B520007)

王磊(1978-)，男，河南 信阳人，博士，副教授，硕士生导师.E-mail:wanglei_t@swufe.edu.cn

TP393

A

1000-5900(2016)02-0109-05