基于GWO的无线Mesh网络最优模板对比的路由算法

于小民，夏换，杨秀璋，范郁锋

（1.贵州财经大学贵州省经济系统仿真重点实验室，贵阳550025；2.贵州财经大学信息学院，贵阳 550025；3.贵州财经大学计划财务处，贵阳 550025）

0 引言

无线Mesh网络（Wireless Mesh Network）以其优良的特性被广泛应用于区域局域网之中，如大型车间、库房、实验室等，由于其桥接和多跳的特点极大提高了网络部署的灵活性和数据传输质量，在以后的物联网领域甚至是我们平时所应用的移动网络领域，Mesh网络都会发挥出不可估量的作用。

基于无线Mesh网络的特性，路由算法对其而言是至关重要的。现在关于Mesh网络的路由算法也是不胜其数如基于遗传算法和QoS（Quality of Service，服务质量）模型的路由算法等，但是这些算法的评估函数数值均是基于所选择的路径，自始至终也没有一个最佳的评估数值，在现实的网络架设中其实是需要这样的一个最佳评估值作为衡量标准的，设计师可以以这个衡量标准作为参考，确定需要选择Mesh节点的参数以及确定各个节点安装位置的方案。

本算法对于灰狼算法（Grey Wolf algorithm）进行改进，从而能够在Mesh节点承受的参数（带宽、数据处理延迟和传输时间、丢包率）范围内算出节点之间的最佳性能参数，也算出在各个参数最佳情况下的Mesh网络数据传输的最佳代价，然后以最佳代价为模板在Mesh网络中选择路由方案，当方案所产生的路由代价和最佳路由代价最接近的时候可以确定所产生的路由路径为最佳路径。

综上，本研究主要旨在提供一种新的无线Mesh路由算法此算法不仅能够选择出路由路径还能提供最佳路径参考模板协助衡量所选的路由路径质量以及网络节点架设质量。

1 无线Mesh网络及QoS模型

1.1 无线Mesh网络

如图1所示无线Mesh与传统网络的主要区别在于它的无线传输拓扑结构，传统网络中节点路由之间不能相互连接多采用星型结构，起始节点要传输数据的时候直接将数据传输给路由节点，由路由节点将数据传输给目标节点，由于这种传输结构的限制，目标节点和起始节点必须连接在一个路由节点上，由于网络信号传输距离是有限的，这样的传输结构大大限制了网络。但是，在无线Mesh网络中路由节点之间可以相互连接从而形成骨干网络如图1所示，起始节点可以跟最近（网络信号最强或者是最符合算法要求）的路由节点相连接，连接之后数据通过骨干网络中的节点以多跳的方式一步一步传输给目标节点，以这种传输方式目标节点不需要和起始节点连接在一个路由节点上。也可以达到数据传输给目标节点的目的。

图1 WNM拓扑结构

1.2 QoS约束模型

QoS本身是一种网络安全机制，它主要是通过控制和约束各种基础技术的参数来控制网络的传输能力，这种参数配比主要是基于现有技术的局限性，如果网络传输的带宽可以无限大、延迟时间无限小、丢包率为0那么QoS模型就没有存在的意义了，正因为这三项参数和网络传输代价息息相关所以需要QoS模型均衡各个参数来使网络达到最好的效果。QoS模型参数定义如下：

（1）时延：

（2）带宽：

（3）丢包率：

（4）代价：

根据无线Mesh网络的特点我们执行基于QoS模型的路由算法就是在满足QoS模型约束（小于最大延迟、大于最小带宽、小于最大丢包率）的基础上使产生的传输代价最小或者是最佳的路由路径。在某些特定的情况下我们可能会把评价函数设置成最符合我们要求的函数的评估值可能不是最小但是在某种程度上最符合我们对网络传输的要求，满足QoS模型公式表达为：

其中D为最大延迟时间，B为最小带宽，L为最大丢包率。

2 算法原理及其设计

2.1 灰狼算法原理

灰狼算法的主要思想是将决定最终结果值的数据转换成多维坐标系统中的维度，将我们需要的最佳结果定义为坐标系系中的位置，在坐标系中有N头寻找最佳结果的坐标节点即所说的捕获猎物的灰狼，灰狼的位置以及猎物的坐标值会根据评估函数以及α狼、β狼、γ狼的位置不断更新，其中α狼、β狼、γ狼分别是第一符合、第二符合、第三符合评估函数标准的三个点的坐标。其他狼的位置根据距离三头狼的位置更新坐标，而猎物的位置为三头狼坐标的平均值，算法以这种方式不断迭代，直到最终寻找到我们需要的最优结果的位置即α狼的位置一直不发生变化。

2.2 基于灰狼算法QoS最优参数算法

本文提出的Mesh网络路由算法，首先需要利用灰狼算法算出最优解，在QoS模型中每个传输节点有三个变量来决定传输代价，分别为带宽（Bandwidth）、时延（Delay）、丢包率（Loss）。所以在本算法中每个维度的变量由这三部分组成，决定最优解的维度为数据传输经过Mesh节点的个数。

利用灰狼算法计算Mesh网络传输的最佳路径模板，设寻找最优解的灰狼个数为N，设数据传输经过G个Mesh节点即灰狼在G维度空间中寻找最优解，那么可以表示为Xn=(Xi1,Xi2,…,XiG)。在首次利用评估函数计算的时候计算数值最符合要求的前三个节点命名为α、β、γ三只头狼，在下一轮计算中群狼的位置由α狼、β狼、γ狼决定。

在捕食过程中灰狼首先对猎物采取包围行动，所以开始要做的灰狼和猎物（最优解）之间的距离：

在公式中Xp(t)为第t代时猎物的位置向量，在本算法对应的是第t代G个节点带宽（Bandwidth）、时延（Delay）、丢包率（Loss）的参数代入评估函数后所得到数值，X(t)代表第t代灰狼的位置，A和C分别代表系数，a随着迭代次数从2线性递减到0；r1和r2为[0,1]之间的随机数。

从上面的公式可以知道要对猎物进行包围，那么我们首先需要确定猎物的位置，在本算法中猎物的位置由上一代离猎物最近的α狼、β狼、γ狼确定：

在本算法中每个维度包含三个变量（带宽、时延、丢包率）对于三个变量均采用上述算法即可找出每个维度每个变量最合适的综合节点，经过多次迭代之后即可得到最符合评估函数的G个Mesh节点的路由路径。

经过上述处理之后函数可以找出供对比使用的最佳函G跳Mesh数据传输路由模板，同时此模板也可以作为衡量网络架设质量的参考。

得到最佳模板之后，可以根据最佳模板Mesh节点之间的参数衡量节点与起始Mesh节点相连接的参数衡量函数为：

Len为两节点之间和起始连接所有节点参数与此段标准参数之间的差距，在两点之间，与起始节点所有相连节点中选择和标准参数差距最小的参数作为起始节点的下一跳节点以此类推直到找到最终节点为止。

3 仿真实验

本算法使用Python来分析本算法所选择的出来的路径的质量，仿真的数据传输分别通过4跳（5节点）、5跳（6节点）、6跳（7节点）进行数据传输。传输所消耗的代价跟所有路径之间作对比，然后对对比结果进行从小到大排序，观察所选路径在所有路径之间的占优比（比所选路径代价大的路径的个数与所有路径个数的比值）。按照标准对结果进行评估。本文规定平均自占优比在90%以上的符合试验要求。

如表1所示为试验中带宽、时延、丢包率的取值范围，算法在能够满足路由选择的要求同时计算出最优模板，然后以最优模板为基础选择符合要求的路由路径，用户也可以根据需求进行多次迭代直到选出占优比为1.0（路由代价最小）的路由路径。表2分别是5节点、6节点、7节点、8节点Mesh网络数据传输500次数据传输试验的平均占优比均在90%以上达到了预期实验目的。

表1 实验数据参数范围

表2 各节点平均占优比

如图2所示5节点、6节点、7节点、8节点，各500次试验（每次试验迭代10次将离最有模板最近评估值的路径选为最优路径）所得到的占优比分布，占优比在0.9-1.0之间的个数都远远高于其他范围。说明算法达到预期效果。

图2 占优比分布图

3 结语

本文所提出算法的应用除了能够对最佳路由路径进行筛选外，还可以计算出最佳路由代价，最佳路由代价的参数除了可以为选择路由路径提供参考外，还可以为网络架设提供标准，这样就可以大大提高网络架设和路由筛选的灵活性。除此之外用户还可以根据选择Mesh路由节点的参数调节最适合的当前网络的参数如我们网络是速度型的那么我们可以将延迟时间所占的路由代价比重调节地更高那么算法就可以直接根据需求选出有所倾向的最佳路由代价，这对于网络的灵活性也是非常重要的。