移动AdHoc网络基于蚁群需求的分群路由算法研究

刘军华，蔡卫红，雷超阳

(湖南邮电职业技术学院，长沙 410015)

移动AdHoc网络基于蚁群需求的分群路由算法研究

刘军华，蔡卫红，雷超阳

(湖南邮电职业技术学院，长沙 410015)

针对移动Ad Hoc网络因受带宽和电量等因素影响而造成封包遗失机率较高的现象，提出了一种移动Ad Hoc网络基于蚂蚁算法的需求式群集路由算法．该路由算法利用弱连接支配集群概念，从每个群集广播给其它群集节点，算法中网络上的状态信息通过前行的蚂蚁获得，回退的蚂蚁采用伪随机比例选择策略并根据节点剩余电量、网络平均剩余电量以及路径平均剩余电量来评估从源节点到目的地节点的最佳路径．仿真结果表明：随着网络信息流量的增加，AOCR路由算法在封包抵达率、延迟时间均比AODV和AntSence算法有较大改善，因此，基于蚁群需求的群集路由算法在网络效能上比基于距离矢量路由AODV算法及传统的蚁群路由算法效率更高．

移动网络；Ad Hoc网络；分群；路由算法

Ad Hoc网络是一种当通信终端附近无BS时也能借由其它通信设备桥梁来进行信息的传送，间接地将信息传送给接收装置的一种网络环境[1].Ad Hoc网络因为不需依靠网络基础架构及无中心管理特性，其应用环境可不受 BS的限制，从而可应用于无法建立 BS通信的环境，如深山、海底、战场等特殊区域通信环境[2]．移动Ad Hoc网络就属于这种可不受通信基础环境相关因素影响的无基础网络架构，因受限于有限的带宽、电量等影响，其网络信息的传送无固定的路径，因此封包的遗失机率较高．Ad Hoc网络如何能跟随网络的变化快速找出一条传输路径非常重要．

1 相关路由算法

1.1 AntSense蚁群路由算法

图1 蚁群路由算法示意图

蚁群路由算法是一种启发式算法，常用来解决组合最佳化问题．其原理是模拟蚁群寻找食物的行为来在网络上寻找最佳路由[3]．如图 1所示，图中有两个蚂蚁分别从较短路径A及较长路径B走过并放置费洛蒙以备食物寻找，通过短路径A的蚂蚁会先找到食物并沿原路返回，并继续留下费洛蒙来增加路径A的费洛蒙浓度，因路径A的费洛蒙浓度比路径B高，因此走路径B的蚂蚁会有较大概率被费洛蒙浓度高的A路径所吸引而走路径A返回去并也沿路留下费洛蒙，如此周而复始，路径 B会因越来越少蚂蚁走过而逐渐消失，而路径A会因越来越多的蚂蚁走过而逐渐形成主要的路径，即找到了1条最佳(短)路径．Ad Hoc网络依据其原理来决定从来源节点到目的地节点的最短路由，但其路由算法最优路径上信息素积累不够迅速，且局部最优容易造成网路拥塞．

1.2 AODV路由算法

AODV(Ad Hoc On-demand Distance Vector)路由算法是一种无线Ad Hoc基于距离矢量算法的反应式路由算法．节点只有向目的节点发送封包时，源节点才会在网络中发送控制封包发起路由查找过程，也就是只有当某节点有连接建立需求时，才广播1个连接建立的请求[4]．其它收到连接请求的AODV节点马上转发这个请求消息，并记录源节点以及回到源节点的临时路由，直到某个收到连接请求的节点知道到达目的节点的路由时，就把这个路由信息按照先前记录的回到源节点的临时路由发回源节点，源节点就开始使用这个具有最短路径的路由，当链路断掉时，错误的信息被回传至源节点，源节点再重新发起路由查找．该算法高效、扩展性能良好，但因其路径选择仅以最短路径及最快响应为准则，不考虑节点能量状态及负载等情况，故其选择的路径非最优，在高负载及高移动速率下性能下降快，网络拓扑结构改变后，链路修复性能差，数据传输延迟大，路由重建时间长．

2 AOCR路由算法

AOCR(Ad Hoc On-demand Clustering Routing)算法是一种以蚁群算法为基础的需求式群集路由算法，是主动式群集分配与被动式群集间沟通的混合式路由算法[5-6]．当有节点需传送信息包时，它会先检查路由表中是否有路径可达到目的地节点，如没有就进入路径搜寻阶段，并发送Forward-Ant，当1个节点收到Forward-Ant时首先会检查是否有重复收到同样编号的封包，若有即弃掉这个封包，反之，则进入下一阶段[7]．

为计算出蚂蚁封包所要放置的费洛蒙值，首先需要计算出路径的健康值，其计算公式为

前1个节点i到现在节点j的路径健康值Gij是前1个节点i所计算出的路径健康值的和，cP表示现节点j接收封包需消耗的功率值，而Mij表示对现节点j所测量到的剩余电量合并得到的电量测量值，其计算公式为

式中Ej表示节点j的剩余电量，Ejmin表示是Forward-Ant从来源节点走到节点j的这段路上所记录到的最小节点剩余电量，其计算公式为

测量完路径健康值之后，节点会根据公式(6)更新费洛蒙表里的费洛蒙值，

式中ρ表示费洛蒙蒸发率，△τij表示节点i到节点j所需更新的费洛蒙值，将其有的费洛蒙值τij乘上(1-ρ)成为蒸发过后的费洛蒙值后再加上欲增加的费洛蒙值即为节点i到节点j的新费洛蒙值，欲增加的费洛蒙值计算公式为

式(5)可知电量的测量值与路径健康值成反比，因此需将路径健康值取倒数才符合蚂蚁算法中剩余电量越多费洛蒙值会越多，而费洛蒙值越多则可吸引越多的蚂蚁走这条路以达到最佳化．

更新完费洛蒙表后，接着节点将检查是否已抵达目的地节点，如是则发送Backward-Ant至源节点，反之则根据此节点是否cluster-head来决定是要转传给该群集的 cluster-head还是广播Forward-Ant给其它的cluster-head．

当目的地节点收到Forward-Ant封包后，会把Forward-Ant封包删除并产生一个 Backward-Ant封包，按图1流程来发送与接收Backward-Ant封包，收到Backward-Ant封包的节点会先更新其路由表，接着判断是否回到源节点，若没有则继续转传 Backward-Ant出去，在发送 Backward-Ant封包之前，将根据伪随机比例选择策略来判断下一个节点，其判断方法如式(8)所示．

式中Pj表示0~1之间的一个随机数，P0表示0~1之间的常数，当Pj小于P0时直接在节点i的所有邻居节点当中选择出费洛蒙值最大的节点j作为下一个跳点．如果Pj大于P0的话则根据

的机率决定出下一个跳点，式中Pis表示节点i会选出下一个跳点S的机率．其原理类似如一个俄罗斯转盘，转盘每一个区域的大小取决于费洛蒙值的大小，值越大的节点就越有机率会被选中．每个收到Backward-Ant封包的节点都会按此策略直到Backward-Ant封包抵达源节点为止，一旦源节点收到Backward-Ant封包并更新路由表后，网络路径探索即完成了．

3 模拟仿真

3.1 模拟仿真参数设置

为对以上3种路由算法各主要性能作比较，搭建移动AdHoc网络的MATLAB仿真环境，对网路各主要参数的设置情况见表1．

表1 模拟环境参数设置

3.2 仿真结果

根据前面仿真参数设置，模拟AODV算法、蚂蚁算法AntSense及本文所提出的AOCR算法，在不同信息流量的情况下观察并比较它们封包达到率、网络实际资料吞吐量、平均点对点延迟．

3.2.1 AODV、AntSence及AOCR算法封包抵达率比较

图2的模拟结果显示 AODV、AntSence及AOCR的PDR都会随着信息流量的增加而降低，这是因为网络变得越来越拥塞所致．但AntSence算法最为明显，这是因为AntSence算法持续不断地发送蚂蚁封包，且以随机的方式选取一个方向去寻找路径．而AOCR算法因为WCDS网络架构能够有效率地传送封包，使得其PDR即使在信息流量增大的情况下也不会下降很多，而AODV在整体性能上与AOCR相差并不多，但因其仅仅

图2 动态网络下AODV、AntSence及AOCR算法封包抵达率比较图

考虑最短路径而没有建立任何架构，因此当信息流量变大时有时其PDR甚至会低于AOCR．

3.2.2 AODV、AntSence及AOCR算法网络实际信息吞吐量比较

图3的模拟结果显示AODV与AOCR两种算法的实际信息吞吐量都会随着信息流量的增加而增加，但AntSence算法的实际信息吞吐量当信息流量增加到50 packets/s后即开始下降．

图3 动态网络下AODV、AntSence及AOCR算法网络实际信息吞吐量比较图

这是因AOCR与AODV两种算法的目的地节点实际收到的信息封包都可随着信息流量增加而增加，而 AntSence算法当信息流量超过 50 packets/s后对持续送蚂蚁封包负担过重，使得网络拥塞过重，最终导致达到目的地节点的信息封包反而减少．

3.3.3 AODV、AntSence及AOCR算法平均点对点延迟比较

当网络上的封包流量越来越多时会容易造成网络的拥塞，进而使得封包抵达目的地节点的时间变长．从图4模拟结果可知AOCR算法有着最小延迟时间．

图4 动态网络下AODV、AntSence及AOCR算法平均点对点延迟比较图

这是因为 AOCR算法能在事先建立好的WCDS架构让封包能快速且有效地传送到目的地节点．且 AntSence有着最大的延迟时间，因为AntSence持续不断地发送蚂蚁封包寻找目的地节点，从而导致网络拥塞的情况发生，尤其是当信息流量为50 packets/s时，延迟时间上升的情况特别明显．

4 总结

本文提出的AOCR算法基于区域分配演算法WCDS群架构思想,使得封包相当于在网络上的cluster-head之间做沟通而非网络上的每个节点，能有效率地寻找一条适当的路径抵达目的地节点，因此能够迅速地将封包传送到网络的每个角落．从模拟结果可知，无论是封包抵达率、信息吞吐量，还是点对点延迟时间，AOCR算法都比基于距离矢量路由算法及传统的蚁群路由算法效率更高，可让整个网络的效能获得较大的改善．

[1]黄浩军, 尹浩, 陈和平, 等．无线Ad Hoc网络能量感知地理路由协议研究进展[J]. 软件学报, 2014, 25(5): 1061-1084.

[2]薛亮, 关新平, 袁亚洲. 无线传感器网络中事件驱动的能量均衡多流聚合路由算法[J]. 控制与决策, 2012, 27(2): 227-231.

[3]胡青松, 吴立新, 张申, 等. 协作WSN路由算法的能耗及其影响因素研究[J]. 华中科技大学学报: 自然科学版, 2013, 41(2):81-85.

[4]张志协, 曹阳. 基于改进型蚁群算法的最优路径问题求解[J].计算机系统应用, 2012, 21(10): 76-80.

[5]夏亚梅, 程渤, 陈俊亮, 等. 基于改进蚁群算法的服务组合优化[J]. 计算机学报, 2012, 35(2): 270-281.

[6]戴天虹, 李昊. 基于改进蚁群算法的无线传感器网络路由的优化[J]. 计算机测量与控制, 2016, 24(2): 321-324

[7]周治辰, 费树岷. 基于退火蚁群混合算法的裁剪分配优化系统的研究[J]. 工业控制计算机, 2014, 27(11): 39-41.

(责任编校：蒋冬初)

Research of Clustering Routing Arithmetic Based on Ant Colony Demand for Mobile AdHoc Network

LIU Jun-hua,CAI Wei-hong,LEI Chao-yang
(Hunan Post and Telecommunication Vocational College, Changsha, Hunan 410015, China)

For mobile Ad Hoc networks due to affected by factors such as bandwidth and power phenomenon of packet loss probability higher, a mobile Ad Hoc network demand type clustering routing algorithm based on ant algorithm is proposed. The routing algorithm uses weak links to dominate the cluster concept, from each cluster broadcast to other cluster nodes, the state information of the network access arithmetic through the forward ants, regression of ants using pseudo random proportional selection strategy according to the residual energy and network average residual energy and average residual energy to evaluate from the path the best path to the source node to the destination node. The simulation results show: With the increase of network traffic, the AOCR routing algorithm in packet arrival rate, delay time than AODV and AntSence algorithm are greatly improved, so the cluster routing algorithm in the network performance requirements of ant colony based on distance vector routing AODV algorithm and the traditional ant colony routing algorithm based on higher efficiency.

mobile network; Ad Hoc network; clustering; routing arithmetic

TP393

A

10.3969/j.issn.1672-7304.2017.02.0013

1672–7304(2017)02–0059–04

2017-02-20

湖南省教育科学规划课题(XJK013CZY055)；湖南省教育厅科研项目(14C0834)

刘军华(1979-)，男，湖南衡阳人，副教授，硕士，主要从事移动互联网应用技术和软件工程研究，E-mail: 38474478@qq.com．