无线Mesh网络中基于离散粒子群优化的信道分配算法.docVIP

无线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节中，将采用冲突百分比对干扰进行量化描述。 对于给定的干扰模型，假设相互干扰的链路同时使用相同信道，可用冲突图表示。为了定义冲突图，首先要定义其顶