无线Mesh网按需路由算法的研究与实现

李建利

（山西警察学院，山西 太原 030021）

无线Mesh网按需路由算法的研究与实现

李建利

（山西警察学院，山西 太原 030021）

针对无线Mesh网QoS的路由特点，本文主要以蚁群算法为基础，将其应用到无线Mesh网络中，系统地分析了这种算法，对其性能进行了改进，并在此基础上，提出了一种全新的基于蚁群算法的无线Mesh网按需路由算法.实验结果表明，结合贪婪搜索和分布式计算，本文提供的算法具有强大的搜索能力.

无线Mesh网；Ad Hoc网络；蜂窝无线网；蚁群算法

随着计算机网络技术，移动技术的更新换代，人们对技术的需求逐渐转换为便捷化，通过手机,PAD等设备把计算机无线网络推向一个的高峰.国内外的专家学者对无线组网进行了大量研究与实践.其中，一种新型宽带无线网络结构——无线Mesh网络(WMN)成为无线网络研究中的一个热点课题.在OSI的参考模型中，网络操作系统实现的通信协议主要通过网络层完成，网络层通过地址来确定信息，并且实现了逻辑地址到物理地址的翻译.首先通过源点，然后到网络结点，最后到目标节点对路由器进行选择，并且实现业务流处理.例如通过路由控制了数据分组阻塞.在OSI模型中，网络层最复杂，由于无线Mesh网络与传统的ad hoc网络和有线网络是完全不同的网络，传统的ad hoc网络必须首先访问集中接入的点才能进行无线连接，这样最少要两个节点相邻，网络中的每个节点，也只能通过接入点才能实现相互间的通信.这就意味着两个节点的实际距离不能太远，这样就大大地限制了无线网络的应用范围.

1 基于蚁群的按需路由算法设计

针对无线网络路由选择问题，设计按需路由算法，首先分析无线MESH网络中出现的各种问题，然后确定不同的数据，最后根据不同的需求，数据的传输通过最优路径来实现.通过算法设计建立简单模型：设定N个节点和节点之间的距离，确定一个经过每个节点，并且每次经历的节点都是最短路线.设定G=（V,A）,其中，A是G的边，V是G的顶点，通过每个节点之间的距离，对Hamilton回路确定一个最短的.

2 基于蚁群算法（ACO）实现的算法流程

为了说明问题，首先将以上问题实例化，以建立一个蚂蚁模型.通过图论进行定义，设定G=（V,A）,其中，A是G的边，V是G的顶点，通过每个节点之间的距离，对Hamilton回路确定一个最短的.

蚁群算法的简单个体特点如下：

2.1 节点i-j的运动实现了循环的过程，边(i,j)通过蚂蚁进行物质的释放，这种方式叫做信息素轨迹.

2.2 访问的节点通过蚂蚁概率进行选择，2个节点之间的距离和路径函数通过蚂蚁概率实现.

2.3 在循环之前，访问的过节点不能让蚂蚁进行选择，满足了约束条件.简单蚁群算法如下：(1)对初始化蚁群A(t)；(2)通过目标函数实现蚂蚁适应的评价A(t)；(3)对适应度选择，根据蚂蚁经过的路径释放信息素，如果适应度越高，那么信息素的释放越多；(4)依据选择路径和节点信息素通过蚂蚁进行节点移动；(5)通过时间不断消散进行信息素挥发.

3 基于蚁群无线MESH网路由算法实现

3.1 基于蚁群算法（ANT）实现模型

首先每条路径的信息量在初始时刻都是相等的.设置τij=C(C为为常），蚂蚁k(k=1,2,3…)，信息量的转移方向通过运动的路径实现.随机比例规则是通过蚂蚁系统的转移规则进行实现，随机比例规则针对节点i，对蚂蚁k选择给出节点j的概率.节点i的转移概率 在t时刻为：

其中，allowedk={0,1,2,3…,n-1}表示进行选择的节点，通公式（1），τijα(t)*ηijβ和pijk(t)成正比.节点能见度通过ηij表示，参数α和β表示在运动过程中，蚂蚁的启发和积累的信息进行路径的选择非常重要.人工蚁群针对不同的真实蚁群有记忆功能.通过不同的n个节点，蚂蚁经过的路径都实现了一个数据结构的设计，这种设计叫做禁忌表.通过禁忌表实现了蚂蚁在t时刻经过的节点，蚂蚁在本循环中不能在t时刻经过这些节点.循环结束后，通过禁忌表来建立和设计蚂蚁经过节点路径的长度.蚂蚁进行路径自由选择，最后清空禁忌表.

在完成循环的过程，在t时刻，经过路径的信息如下:

其中，,蚂蚁k在(t,t+1)时刻，信息信息素量在经过路径(i,j)为△τijk(t,t+1)，这个值是蚂蚁的优劣程度.信息素释放多，那么蚂蚁经过的路径就越短.在循环中，针对信息素量经过的路径(i,j)为△τijk(t,t+1).信息素轨迹系数是(1-ρ)，通过系数ρ＜1对蚂蚁经过路径轨迹量进行累加.依据不同的算法，根据不同的问题，△τij，△τijk及Pijk三种可以表达不同的形式.

3.2 蚁量系统和蚁密模型

蚁密蚁量模型和△τijk(t,t+1)的对不，他们的表示方式不同.蚁密模型中，每个单位的长度通过蚂蚁经过路径(i,j)进行信息量的释放.蚁密模型中，每单位长度Q/dij表示蚂蚁经过路径(i,j)进行信息量的释放.蚁密模型中,蚂蚁在路径(i,j)上，从i向j移动信息轨迹强度和dij没有关系.蚁量模型中，和dij成反比.蚁量模型中蚂蚁对短路径有吸引力，并且增加见度因数ηij.蚁密和蚁量模型中，通过伪码对实现过程进行表示.(1)算法的初始化过程：

设t:=0；t是计数器

Nc:=0；Nc是计数器

τij(t):=C；{为每条路径(i,j)设一个轨迹强度的初始值}

在n个节点上把m只蚂蚁进行设置：

设置s：=1，表索引通过s表示，在禁忌表中对蚂蚁初始节点设置

(2)对禁忌表进行重复(n-1)次

设s:=s+1

通过pijk(t)对节点j进行选择

针对蚂蚁k，在tabuk中加入节点j

对于每个路径(i,j)，根据方程式5-2计算τij(t,t+1)；

最短路径的记录if Nc＜Ncmaxthen对禁忌表进行清空.

设s:=1

循环结束后，回初始位置.

设t:=t+1

设△τij(t,t+1):=0

else设置最短路径；

蚁周模型实现：

以上2种模型和蚁周模型主要区别为△τijk(t,t+1)对蚂蚁经历的路径不同，在循环中，蚂蚁经过n步通过(t,t+n)，更新值如下：

方程不是每步轨迹更新，所以ρ1与ρ不同，通过建立完整的路径后，蚂蚁在更新轨迹量.

蚁周模型算法实现如下.（1）蚁周模型初始化：

设t:=0；t是计数器

Nc=0；Nc是循环次数

τij(t):=C；{为每条路径(i,j)设一个轨迹强度的初始值}

τij=0；{轨迹强度的增量的初始值为0}

模型中，ηij=1/dij，通过启发式算法对ηij进行确定

在n个节点中，对m只蚂蚁进行地置

设置s:=1

(2)针对禁忌表重复(n-1)次

设s:=s+1

for k:=1 to n-1 do{搜索蚂蚁k的禁忌表}

设(h.l):=(tabuk(s),tabuk(s+1)){(h,l)是在蚂蚁k的禁忌表中连接节点(s,s+1)的路径}

每一路径(i,j)依据公式5计算τij(t+n)

设△τij(t,t+n):=0

if Nc＜Ncmax，禁忌表被清空

设s:=1

tabuk(s)=i{一次循环后蚂蚁又重新回到初始位置}

设t:=t+1

本文主要以蚁群算法为基础，将其应用到无线Mesh网络中，系统地分析了这种算法，对其性能进行了改进，实验表明算法可以加快计算速度，减少时延；增加稳定性并且有利于负载平衡.实验表明本文提出的算法具有很强并行性，通过信息素实现合作，这种方式具有很好的可扩充性.在无线Mesh网络中节点中，移动性需要一种全新的简单快捷的算法，应用蚁群算法不失为一种好的选择.

〔1〕乔宏,张大方,谢鲲,何施茗,张继.多射频无线mesh网中的联合协作路由与信道分配算法 [J].电子学报,2016(06): 1400-1405.

〔2〕国润竹.面向无线Mesh网络的DSDV路由协议算法研究[D].辽宁大学,2016.

〔3〕付永涛.无线Mesh网络中的机会路由算法研究[D].电子科技大学,2015.

〔4〕谢忠明.无线Mesh网络多径路由算法的研究与应用[D].苏州大学,2015.

〔5〕杨阳.无线Mesh网络中具有QoS保障的路由算法研究[D].北京邮电大学,2015.

TN926；TP393

A

1673-260X（2017）08-0013-02

2017-05-29

本文系关心下一代“十三五”国家规划教科研微型课题，国家级阶段性成果（GGWEDU-W011）