无线Mesh网络中基于离散粒子群优化的信道分配算法
摘 要： 无线Mesh网络中配置多接口Mesh路由器并使用多信道可有效增加网络容量并降低干扰。信道分配问题已被证明是一个NP难题。信道分配的目的是将可用信道分配到通信链路以实现网络干扰最小的目标。针对多接口多信道无线Mesh网络中的信道分配，提出了基于粒子群优化（PSO）算法。在实现过程中，通过增加交叉操作将其改进为离散粒子群优化（DPSO）用以处理信道分配这一离散问题。同时，引入了信道合并过程用以消除违背接口约束情况。通过仿真试验并与Tabu?Based算法对比，该算法能有效降低网络干扰并提升网络性能。
主题词： 无线Mesh网络； 多接口多信道； 信道分配； 离散粒子群优化算法
中图分类号： TN911?34； TP393 文献标识码： A 文章编号： 1004?373X（2013）08?0031?04
0 引 言
无线Mesh网络（Wireless Mesh Networks，WMN）作为下一代宽带接入的关键技术，由于具备动态自组织、自配置的优势，网络节点可以自动建立和维护，具备低投入、易维护、安全性强，覆盖范围广而引起业界和学术界极大的研究兴趣。WMN中一个重要的设计目标是使容量最大化，但无线干扰严重限制了多跳无线网络中的网络容量。采用多接口多信道能改进网络容量，如何给接口或链路分配信道依然是一个复杂的问题，许多文献都对信道分配问题进行了探讨。
粒子群优化（Particle Swarm Optimization，PSO）算法是1995年由J.Kennedy博士和R.Eberhart博士基于对鸟群、鱼群捕食行为的模拟而提出的群智能优化算法。信道分配问题是一个离散优化问题，虽然传统的PSO算法并不适合求解离散问题，但通过将其位置和速度更新公式进行改进后，其求解离散优化问题的效果也比较明显。文献[1]提出了基于节点组织的拓扑保护信道分配算法，并采用离散离子群优化算法针对节点进行信道分配。但针对节点的信道分配有可能造成网络隔离，因为相邻的节点有可能出现没有共同信道的情况。为此，本文提出了基于离散粒子群优化算法的信道分配方案，主要是将信道分配给网络中的链路，目标是使网络干扰最小化。主要实现了以下功能：
（1）建立了基于网络干扰最小的信道分配模型；
（2）提出了基于离散粒子群算法的信道分配方案；
（3）对基于冲突图信道分配可能违背接口约束的问题进行信道合并处理。最后，通过仿真实验对所提算法进行分析验证，结果表明该算法能有效降低网络干扰并提高吞吐量。
1 离散粒子群优化算法
为了解决实际工程中的离散问题，Kennedy等人于1997年提出了离散二进制离子群算法[1]，采用二进制方式对粒子位置进行编码，通过采用Sigmoid函数将速度约束[0，1]区间，并以此确定取1的概率。随后，Hu等对文献[2]中的方法进行了改进，用于解决置换排列问题，其中：粒子用置换排列来表示，而速度则根据两个粒子的相似度来定义，决定粒子位置变化的概率，同时引入变异操作防止最优粒子陷入局部极小[1]。文献[1]在PSO算法的基础上提出了求解离散变量优化问题的DPSO算法，定义了粒子的离散位置来表示解空间，在此基础上给出离散位置之间的差运算、离散速度之间和运算、常数与离散速度间的乘运算以及离散位置与离散速度之间的和运算，由此可得DPSO算法的基本公式为：
[vi（t+1）=c1?vi（t）c2?（pi（t）Θxi（t）⊕c3?（pgΘxi（t））] （1）
[xi（t+1）=xi（t）⊕vi（t+1）] （2）
式中：xi为第i个粒子的离散位置；vi为第i个粒子的离散速度；pi为第i个粒子的个体极值；pg为种群的全局极值。c1，c2，c3，为相应的权值，取值为[0，1]之间的常数；[“·”，“⊕”，“Θ”“]分别表示DPSO中的乘法、加法和减法。
2 网络模型及问题描述
下面主要对网络模型及信道分配问题进行建模。
2.1 网络模型
网络模型采用无向图[G=（V，E）]表示。其中，V表示Mesh路由器（节点）；E表示节点间的边（通信链路），当节点i与节点j处于各自的通信范围且有节点配置了相同的信道，则构成一条通信链路。网络中可用信道数目是有限的，在此用K表示。
2.2 干扰模型
由于无线媒介的广播特性，处于通信范围内的两个节点间的通信可能干扰附近属于其干扰范围内的其他节点。两条相互干扰的链路使用相同信道不能同时传输。目前，对干扰的描述主要有物理模型和协议模型。
本文采用协议模型进行描述，即根据节点间的距离判断其组成的链路之间是否存在干扰，相互干扰用1表示，否则为0。在第4节中，将采用冲突百分比对干扰进行量化描述。
对于给定的干扰模型，假设相互干扰的链路同时使用相同信道，可用冲突图表示。为了定义冲突图，首先要定义其顶点集[Vc]与网络中的通信链路相对应，即：
[Vc={lij（i，j） isacommunicationlink}]
冲突图Gc（Vc，Ec）可定义为顶点集Vc，冲突边集Ec表示链路（lij，lab）之间使用同一信道时相互干扰。根据上面的定义，冲突图可用于表示所有干扰模型，信道分配不改变其冲突图。图1表示通信图和干扰图之间的对应关系。
2.3 信道分配问题
多接口无线Mesh网络中的信道分配问题可描述为：对多接口路由器组成的Mesh网络，通过给通信链路分配特定的信道使得使干扰最小且保持网络连接性，还要考虑给每个节点分配的不同信道数目不能超过其接口数目。基于上述分析，信道分配问题就可以描述为：对配置了N个节点的WMN，信道分配问题即是求解函数[f：Vc→K]使得网络总的干扰[I（f）]最小且满足如下的接口约束。
接口约束：
[?i∈N，{kf（e）=kforsomee∈E（i）}≤Ri]
网络干扰[I（f）]：
[I（f）={u，v}∈Ecf（u）=f（v）] （3）
下面采用离散粒子群优化算法对信道分配问题进行求解。
3 基于粒子群优化的信道分配算法
针对多接口信道分配问题，文献[3]已证明了多接口信道分配问题是NP?hard，要想完全消除网络中链路之间的干扰是几乎不可能的，只能尽力减小干扰。显然，采用穷举搜索可解决这一问题，但在合理的时间内很难找到最优解。针对信道分配问题，已有很多解决办法。本文采用DPSO算法对信道分配问题进行求解。
3.1 粒子的编码
无线Mesh网络中节点数目为N，可用信道数目为K，算法中的粒子代表一个可行的信道分配方案，即为冲突图中的每个顶点与可用信道间的对应关系。第i个粒子在时刻t的位置可表示为：[Xti=（xti1，xti2，…，xtim）]，其中，[xtik]记作通信图中边k在t时刻分配的信道。
3.2 适应度函数
粒子将根据当前和全局最优位置改变当前位置，所以需要设计一个适应度函数来度量粒子位置。信道分配的目标是实现网络干扰最小，因此采用网络干扰数目[I（f）]对信道分配的性能进行评价。
[I（f）=e∈VcIN（e）] （4）
式中[IN（e）]表示链路e的受到的干扰数量。
3.3 约束的处理
针对冲突图顶点（即通信图中链路）的信道分配算法，在满足网络干扰最小约束的前提下，可能违背每个节点分配的信道数目不超过其接口数目的约束。因此，在粒子群优化迭代过程中，增加了信道合并操作，确保每个节点所分配的信道数目不超过其接口数目。
3.4 信道分配过程
在引入约束处理的同时，对DPSO算法的更新迭代过程进行了改进，引入了随机扰动操作，改进了DPSO算法易陷入局部最优的不足，从而改进了算法的全局搜索能力。改进后的位置更新公式如下：
[xt+1i=c3⊕F（c2⊕F（c1⊕F（xti，pi），pg），random（K，Edgenum））] （5）
式中，c1，c2，c3为[0，1]间的常数，函数[c⊕F（x1，x2）]为本算法定义的特殊运算形式，即当系统随机产生数小于等于c时切换为x2，大于时保持x1；pi代表个体最优解，pg全局最优解，random（K，EdgeNum）粒子中的某一条边的随机扰动。信道分配的伪代码见表1。
4 仿真实验与分析
为了测试所提出算法的性能，利用Matlab软件实现所提算法，并与文献[4]中的Tabu?based算法进行对比。用冲突百分比评价算法性能，其定义为网络干扰数量与总链路数量之间的比值。
首先，通过改变算法相关参数研究参数对算法结果的影响。其次，模拟两种场景进行实验：
（1）可用信道数目固定，每个节点接口数目变化时干扰的变化；
（2）接口数目固定，可用信道数目变化。算法主要参数如表2所示。
4.1 参数对算法的影响
图2显示了变异因子取值不同时对算法性能的影响。在此实验中，每个节点的接口数目设置为3，可用信道数目为12个。当c3=0.3时，由于最终解的变异概率较小，初期解收敛较快，但容易陷入局部最优解中，致使后期解的效果不是很明显；而当c3=0.8时，由于对寻找出来的解变异的概率比较大，在初期收敛较慢，但在迭代后期解的质量较高。
4.2 接口和信道数目变化对干扰的影响
实验中25个节点随机分布在参数表内所设定的区域内，节点之间的传输距离为250 m，干扰距离为500 m，根据节点分布情况编写程序自动生成通信图和冲突图，算法即是根据冲突图进行信道分配。
图3显示了可用信道数目为12时，在所有情况下，由于接口数目的增加，每个节点相应可用信道数目增加，网络冲入百分比呈下降趋势。本文所提算法在冲突百分比方面均优于Tabu?Based算法。例如，接口数目为4，可用信道数目为12时，冲突百分比降低了近50%。
图4显示了在每个节点配置3个接口时，在可用信道数目相同时，本文所提算法优于Tabu?Based算法。
5 结 语
针对多接口多信道无线Mesh网络，分析了网路干扰模型，并提出了基于粒子群优化的信道分配算法，采用Matlab设计实现算法。仿真表明，该算法有效降低了网络干扰并显著提升网络性能。
参考文献
[1] AKYILDIZ I F， WANG X， WANG W. Wireless mesh networks： a survey [J]. Computer Networks， 2005， 47： 445?487.
[2] KENNEDY J， EBERHART R. A discrete binary version of the particle swarm algorithm [C]// IEEE Int Conf on Computional Cybernetics and Simulation. Orlando， US： IEEE， 1997： 4104?4108.
[3] 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.
[4] SUBRAMANIAN A P， GUPTA H. Minimum interference channel assignment in multiradio wireless mesh networks [J]. IEEE Transactions on Mobile Computing， 2008， 7（12）： 1459?1473.
[5] RAMACHANDRAN K N， BELDING E M， Almeroth KC. Interference?aware channel assignment in multi?radio wireless mesh networks [C]// Proceedings of INFOCOM. [S.l.]： INFOCOM， 2006： 111?121.
[6] KO B J， MISHRA V， PADHYE J， et al. Distributed channel assignment for multi?radio 802.11 mesh networks [R]. US： Colombia University， 2006.
[7] SKALLI H， GHOSH S， DAS S K， et al. Channel assignment strategies for multiradio wireless mesh networks： issues and solutions [J]. IEEE Communications Magazine， 2007， 45（11）： 86?95.
[8] CHENG H， XIONG N. Nodes organization for channel assignment with topology preservation in multi?radio wireless mesh networks [J]. Ad Hoc Networks， 2012 （10）： 760?773.
[9] SHAO B， TAO J， WANG F. Static channel assignment with the physical interference model for maximum capacity in multi?radio multi?channel wireless mesh networks [C]// 2010 Ninth International Conference on Grid and Cloud Computing. Nanjing， China： ICGCC， 2010： 338?343.
[10] HU X H，EBERHART R，SHI Y H. Swarm intelligence for permutation optimization a case study of n?queens problem [C]// Proc. of the 2003 IEEE Swarm Intelligence Symposium. Indianapolis， US： IEEE， 2003： 243?246.
[11] 胡家声，郭创新，叶彬.离散离子群优化算法在输电网络扩展中的应用[J].电子系统自动化，2004，28（20）：31?36.
[12] JAIN K， PADHYE J， PADMANABHAN V N， et al. Impact of interference on multi?hop wireless network performance [C]// Proc. of ACM MobiCom. US： ACM， 2003： 45?54.
[13] 高广恩，刘全利，王伟.基于离散粒子群优化的工业无线网多信道分配算法[J].控制与决策，2012，27（5）：697?702.
