无线Mesh网络中基于萤火虫和粒子群优化的网关部署组合算法

刘友武

(三明学院 经济与管理学院，福建 三明 365004)

无线Mesh网络[1]作为新兴一代无线技术出现，其动态、自适应、高带宽、多跳及易扩展等特点为很多场景解决“最后一公里”提供了优良的方案。自2006年发布的《国家中长期科学和技术发展规划纲要》实施和2015年互联网大会以来，无线mesh网络作为我国信息化发展的重要战略领域，取得了长足发展[2-3]。无线Mesh网络广泛应用于各个领域，小到家庭，大到学校、医院及休闲场所等，为国家的安全稳定、社会的进步和经济的发展做出了巨大贡献。

在无线Mesh网络部署中，虽然网络性能可以通过增加网关节点数量有效提升，但是网关节点数量的增加也造成部署成本和后期维护成本的增加。网关节点作为无线Mesh网络和外部网络之间的桥梁，其负载积累将对无线Mesh网络的容量产生消极影响。如图1的WMN骨干网架构图所示，图中两个网关节点（Gateway1和Gateway2）和10个路由节点（router1～10）共同组成了一个WMN骨干网，其中两个网关节点与Internet直连，10个路由节点分别以两个网关节点为簇头形成了两个簇，簇区域内的路由节点通过链路与簇头进行数据传输通信。图中显示Gateway1负责四个路由节点的数据汇聚，而Gateway2负责六个路由节点的数据汇聚，显然Gateway1相对于Gateway2负载较轻，整个WMN网络资源没有得到充分利用。在具有多个网关节点的WMN中，负载均衡在网络中低带宽的回程链接时具有重要作用。网关链路的带宽和延迟受限于WMN的类型和具体环境，而且网关自身性能对流量和负载表现不同，对负载均衡的影响程度具有差异性。另外，网关也有耗尽回程链路带宽容量的可能性。因此，WMN中网关节点的合理部署对缓解节点过载问题具有重要作用。

图1 WMN骨干网架构图

1 相关工作

目前网关负载均衡的策略主要可以分为3种[4]。第一种是基于移动边界的负载均衡（moving boundary-based load balancing,MBLB）。 文献[5]提出一种最大流量最短路径的网关部署算法来满足无线网络中路由器的带宽需要；文献[6]以分层思想为基础、根据簇的大小并以之为条件提出多层的网关部署算法。第二种是基于分区的负载均衡（partitioned host-based load balancing,PHLB）。文献[7]将网络当中的节点分成不相关的簇，簇首为网关节点，簇中各节点以生成树中的路径来进行数据转发；文献[8]综合考虑了网关数量和MR-GW(mesh router-gateway)路径长度，提出一种网关部署优化的启发式算法。第三种是基于概率分割的负载均衡。文献[9]同时考虑了路由器数量、客户端数量以及客户端对流量的需求，提出了以网关的位置多路通信的流权值为判定的算法；文献[10]提出一种在满足QOS的约束条件下寻求最小的网关数目的算法；文献[11]通过对粒子的速度、相关运算规则及其运动方程的重新定义和设计,提出了一种基于粒子群的无线Mesh网关优化部署算法。

近年来，有学者将萤火虫算法（combination of firefly and particle swarm optimization，CFPSO）和粒子群优化算法应用到无线网络的研究中。萤火虫算法（FF）[12]是一种生物启发式算法，常用于解决无线网络的聚类问题。萤火虫算法由萤火虫根据发光的亮度进行驱动，两只萤火虫个体通过亮度对比，其中较暗的个体被较亮的个体吸引，从而驱动进行空间搜索。

粒子群优化（particle swarm optimization,PSO）算法是由Kennedy和Eberhart[13]提出,该算法由鸟群捕食行为演化而来,其思想主要源于鸟类和鱼类群体的社会行为[14]。在PSO算法中，群体中的每个粒子根据被赋予的速度值在空间中不断搜索运动，每个粒子被赋予一个储存单元，储存单元将记录位置和速度的信息，通过对比后迭代得出全局最优化值。

文献[15]针对传感器网络中计算复杂度和性能之间的优化平衡问题,提出一种基于多传感器的HAR（human activity recognition）系统，通过一种改进的二进制萤火虫群优化算法(improved binary glowworm swarm optimization，IBGSO),并选取了对HAR性能有显著影响的传感器源,进而针对HAR构建了基于优化传感器部署的集成学习系统。文献[16]提出了一种融合GSO（glowworm swarm optimization）和 FF（Firefly algorithm）关键元素的网络萤火虫算法(cyber firefly algorithm，CFA)，并通过多引导解、模式搜索、多起始搜索、群体重建和目标景观分析等AMP（adaptive memory programming）响应策略，进一步发挥了CFA的优势。文献[17]针对变电站选址定容规划的经济性与供电可靠性的问题，提出了一种运用参数方差调节的萤火虫优化算法对基于设备全寿命周期成本的变电站选址定容新模型进行求解，该算法通过区分萤火虫种群的搜索阶段来提高寻优速度和全局寻优能力。文献[18]针对无线传感器网络节点的分布优化问题,提出了一种有效的混沌萤火虫优化算法。利用萤火虫算法的优越的寻优能力来实现最优的网络节点分布,并引入立方映射混沌算子来提高算法的局部搜索能力和保持种群的多样性。文献[19-21]通过粒子群优化算法在无线网络定位和干扰点部署方面进行了应用研究。文献[22]针对无线传感器的网络节点参与构建网络的问题，通过模糊粒子群算法，利用每个粒子代表一个可能解，进行迭代寻优，对节点进行优化部署。

从上述研究可见，无线Mesh网络的网关部署问题主要集中于网关节点的定位、数量以及负载均衡等方面。首先，网关节点本身作为无线mesh网络的关键节点所承担的“责任”非常重要，因此无线mesh网络中网关节点的数量和定位决定了其它mesh节点是否能高质量地与Internet进行连接。网关节点的数量和定位对部署成本具有重要影响，因此如何在可控的成本范围内达到网络的最佳状态，网关节点的数量和定位显得尤其重要。其次，网关节点作为内外网络的桥梁，负载均衡问题也对整个网络的拓展产生极大的影响。再者，已经有学者利用萤火虫和粒子群优化的组合算法来解决在端对端的WMN中提高资源共享效率的问题，如文献[23]利用萤火虫和粒子群优化的混合方法应用于多跳网络中以提升和弦协议(chord protocol)的性能，进而希望能在端对端的无线mesh网络中提高资源共享效率，但是该算法只是立足于WMN节点中端与端之间,并没有考虑到整个WMN的负载均衡,实验结果也只是说明提高了端与端之间的和弦协议的性能，仅解决了WMN局部的性能优化问题。

以上所述说明目前还没有发现将萤火虫和群粒子算法应用到无线mesh网络的网关部署优化问题的实例。因此,针对网关节点的数量与定位控制、负载均衡等问题，本文在文献 [23]的基础上对萤火虫和粒子群优化算法进行组合优化，在给定的网络拓扑结构中，利用萤火虫算法，寻找目标网关节点，实现冗余节点的移动和更新，并将粒子群优化算法融入萤火虫算法中以解决萤火虫算法陷入局部极小的局限性问题，改善萤火虫算法在寻找最优解过程中的行为。

2 网络模型

本文参考文献[24]以无向图 G=（V,E)来表示 WMN 的网关部署问题,其中 V={v1，v2，v3，…，vn}表示网络中的网关节点，N为网关节点的总数。用eij表示网络中的节点i与节点j之间的双向链路，eij∈E,E表示网络中的节点在指定的传输阈值内双向通信的有向链路集合。本文假设了一个平面，平面中所有的射频端都有一个覆盖范围R和一个相同的干扰范围R'。当覆盖范围小于干扰范围，即R＜R'时，说明接收点处于相对应的两个发射节点所覆盖的位置交叉范围内，那么此时的节点分组传输就会产生相互干扰。

本文将无线mesh网络划分的簇区域规定为具有独立性，网关将覆盖网络中簇区域的所有节点，簇中的成员节点通过网关与Internet进行联通。本文用S={s1，s2，s3，…，sk}表示网络中候选的网关集合，用表示网络中候选网关节点的数量。node（sk）用来表示普通成员节点的集合。本文用εi记录算法中节点vi未被覆盖的次数，初始值为0。

2.1 相关概念

定义1网关节点的负载均衡指数(Gateway node load index,GNLI)。GNLI表示无线mesh网络中网关节点的负载情况。

式中βki为节点k的负载流量所需通过网关发送的部分;Tk表示节点k在通信过程中产生的负载;Di表示该节点与网关之间的回程链路的带宽。LI表示网关节点占用返程链路的比例。网关节点负载均衡的目标就是根据网关最大化返程链路开销，使GNLI值最小化。

定义2簇Di的平均有效载荷（average payload，AP）

其中，γij的取值为0或1，表示如果mesh路由器的指定网关节点为vj∈Di，则γij=1；反之γij=0。

定义3节点距离关系

假设 M={m1，m2，…，mn}其中节点 mi的位置坐标为（xi，yi）（i=1,2，…，N），且任何一个节点性能具有排它性。本文参考文献[25]，为了优化节点数量，设定节点的感知半径为RS，节点的检测半径为r，RS且大于r。在节点vi的检测半径内，假设存在一个冗余节点vj，它的位置坐标为(xj，yj)，则可得两节点之间的距离Dij。

2.2 目标描述

无线MESH网络在QOS服务保障要求下，通过算法能实现网关数量和负载均衡的最小化及对网络有效载荷的最大化。即具体优化目标为：

3 基于萤火虫和粒子群优化组合的网关部署算法

3.1 萤火虫算法

萤火虫算法中，萤火虫在相互吸引过程中无关性别，萤火虫的关注度与萤火虫本身亮度有关，即一只萤火虫会根据亮度与本身对比而受到影响，而且萤火虫之间的吸引力与它们之间的亮度成正比，而与距离成反比[26]。

其中r表示源个体与目标个体的距离，IS表示源个体的强度。

其中β0表示的吸引力变化，γ是光吸收系数。

3.2 粒子群优化算法

3.2.1 粒子表示

在PSO算法中，利用群中每个粒子具有的位置和速度的特性，本文定义Xi（t）为群中粒子i在 t时刻的位置向量;Vi（t）为粒子在时刻的速度向量;Pi（t）为粒子i在 t时刻的局部最优位置向量。

3.2.2 粒子的适应度

粒子适应度函数作为粒子群中粒子性能的表现，粒子适应度值与粒子所处的位置成正比关系。因此适应度值越大表示粒子位置最优，适应度函数f（Xi）的计算式如式（6）

式中GNLI为网关节点的负载均衡指数;n（xi）指所部署网络的网关节点的总量;其中α+β=1，Si表示候选网关节点。

3.2.3 粒子位置及速度相关公式

式中，c1和c2为学习因子;r1和r2是介于 [0，1]的随机数;vij∈[-vmax,vmax],vmax是一个由用户设定的常数，所设定的值限定粒子在一个循环中的最大移动距离。

3.3 基于萤火虫和粒子群优化的组合网关部署算法

由于萤火虫算法移动方向随机，很难从全局最优位置找到最优解。采用粒子群优化算法能较好地消除萤火虫算法的局限性，改善萤火虫算法从全局寻找最优解。

本文先利用萤火虫算法，在指定监测区域内，通过k均值聚类算法（k-means clustering algorithm,k-means）[25]对网络节点进行分簇，选出冗余节点，然后使冗余节点处于睡眠状态[27]，在WMN运行一段时间后，簇首承载和传输了大量数据，当节点负载达到一定阈值，此时唤醒冗余节点，计算出节点间相对距离进而进行排序，最后通过粒子群优化算法对节点全局进行优化。算法流程图如图2所示。

图2 基于萤火虫和粒子群优化的组合（CFPSO）算法流程图

Step1根据萤火虫算法初始化粒子群，根据k-means算法对节点进行分簇，选出冗余节点。设置粒子种群数量、最大距离阈值及迭代次数等。

Step2根据公式(3)计算网络中的簇间的距离并根据距离进行排序。

Step3根据公式(6)对群中每个粒子的适应度函数和速度进行计算并将得到的结果进行相应更新处理。

Step4根据粒子适应度值的比较，得出粒子个体最佳情况，并将位置标记为最佳。

Step5使用粒子群组合算法产生下一代粒子，根据算法对粒子群进行重新分簇，并且将下一代粒子的适应度值进行重新计算与前一代粒子进行比较排序。

算法中产生的下一代粒子将会与上一代粒子进行比较，择优算出适应度值以保证算法的收敛性。算法根据下一代粒子的适应度值与上一代粒子的适应度值的比较来判断规则是否有效,如果判断有效则流程转向Step2，否则转向Step6。

Step6输出位置和速度最佳的粒子。

4 仿真实验

4.1 环境参数

为了验证算法的时效性，利用NS2（network simulator version 2）网络仿真工具模拟无线mesh网络环境。仿真实验中部署4种算法，即CFPSO算法、SMS算法、FF算法和PSO算法[23]。通过网关负载、有效荷载、数据投递率和端到端延迟等四个方面进行比较。实验中预设随机生成50个拥有100个网络节点的无线mesh网络拓扑结构，并采用随机抽取的方式将候选网关节点的数量控制在总节点数量的20%内，其中α=0.3,β=0.3,L=20,w=0.7,c1=c2=2,vmax=4,C=120。根据网络中的节点总数计算候选网关和Mesh节点的数量。具体仿真环境参数如表1所示。

表1 仿真实验参数列表

4.2 实验结果及分析

仿真实验中部署的四种算法在不同时间维度下针对、、数据投递率和端到端延迟等四个方面进行比较，得到的结果如图3～6所示。

图3 网关负载指数的比较

图4 网关有效载荷的比较

图5 数据包投递率的比较

图6 端到端延迟的比较

图3显示仿真时间下4种算法的网关负载指数的情况比较。由于CFPSO算法根据K-means算法对节点进行分簇，并利用萤火虫算法选出冗余节点，然后通过粒子群优化算法对全局进行了进一步优化，因此CFPSO算法在GNLI值上比其它几种算法要低，说明CFPSO算法相对于其它算法更加有效地实现网关的负载均衡。

图4显示仿真时间下网关有效荷载的情况。随着通信链路联通，网络节点增加的情况下，节点相互的吸引力也随之加大，从而也促使网关节点的有效荷载增大。结果显示，CFPSO算法总体性能优于其它几种算法。

数据包投递率（packet delivery ratio，PDR）是目标节点接收到的数据包与源节点发送的数据包的比值。PDR主要体现网络可靠性和网络拥塞状况。图5的仿真结果表明，随着网络节点通信数量的增加，数据包投递率的前期呈现上升趋势，在60s～90s时间段时由于节点通信出现拥塞，四种算法的数据包投递率都有大幅降低，之后数据包投递率稳步上升。本文提出的算法采用分簇思想，改善了萤火虫算法从全局寻找最优解的问题，因此数据包投递率总体表现好于其它几种算法

图6的仿真结果表明，在仿真时间前期四种算法的端到端延迟时间差别不大，但是随着随着时间的推移，网络节点数量不断增加，从而端到端的延迟时间也变大。本文提出的算法在仿真时间后期由于采用了分簇的策略，将区域分为多个簇区，较好地实现了节点间的负载均衡，因此，簇区内的节点通信延迟相对于其它几种算法要低。

5 结论

根据萤火虫算法在聚类应用方面的优势及粒子群优化算法的全局优化的特性，研究了网关部署与网关负载均衡的问题，提出了萤火虫与粒子群优化的组合算法，具有如下几点优势：（1）该算法考虑了节点间的距离，实现网关节点部署与网关之间负载均衡的动态平衡。（2）与文献[23]相比，本文研究立足于整个WMN中网关部署和负载均衡的全局问题,克服了文献研究仅针对WMN中端对端的和弦协议优化的局部问题。文献[23]是本文研究的一个局部特例，本文是文献[23]算法应用的衍生，是对文献[23]算法的进一步利用和拓展。(3)模拟仿真实验结果表明CFPSO算法在负载均衡、网关有效载荷、数据投递率和端到端延迟等4个方面优于其它算法。今后的研究将考虑萤火虫算法与其它的自然启发算法相结合，进一步提高网络性能。