Ad hoc网络稳定的蚁群多路由算法

摘　要：移动Ad hoc网络又称MANET，具有多跳路由和拓扑动态变化的特点，是一种特殊的无线移动通信网络。本文提出了一种基于稳定拓扑和蚁群优化的Ad hoc网络多路由算法SAMR。

关键词：Ad hoc网络；蚁群优化；多路由算法
　　Ad hoc网络路由协议是当前研究的热点之一，在建立路由后如果路径没有失效则一直使用，降低了路由协议的控制开销，但带来了路由老化的问题，而且对拓扑变化的适应性差。路由协议要能适应拓扑的动态变化，随拓扑的变化进行更新。SAMR算法用节点在本地获取的局部拓扑稳定度信息计算路径的拓扑稳定度，以路径的拓扑稳定度和时延度量路径质量，并把蚁群优化算法应用于Ad hoc网络中，将路径质量映射为蚁群信息素，通过更新信息素动态更新路由质量信息，避免路径老化。
　　1 蚁群优化算法
　　蚁群优化算法是针对AS(ant system)的各种改进算法进行总结后提出的用于求解离散优化问题的通用框架，具有正反馈、分布式计算和启发性搜索等特点。蚁群优化算法的关键特征是通过模仿蚂蚁的集体行为，解决网络中路由的组合优化问题，提高网络的稳定性、可靠性，增强网络的健壮性。目前很多学者将蚁群优化算法用于Ad hoc网络的路由算法设计。
　　2 SAMR算法
　　2.1 算法设计思想
　　本文将蚁群优化算法应用于Ad hoc网络的路由算法设计中，将路径的拓扑稳定度和传输时延作为路径质量度量，提出了基于稳定拓扑和蚁群优化的多路由算法。为克服蚁群算法收敛速度慢的缺点，SAMR在路由建立过程中采用与AODV类似的洪泛法，以降低路由建立时间；在路由建立后，通过周期性地选择数据包携带人工蚂蚁分组信息进行路由更新。在节点转发数据包过程中，由于路径上的信息素随着路径质量动态更新，因此要实时计算出全部邻居节点的转发概率，再根据概率结果选择信息素较大的路径进行转发，使网络流量能够动态分配，网络资源得到有效利用。在节点i，由节点j转发到达目的节点D的转移概率为：　　
　　2.2 算法实现
　　2.2.1 路由发现
　　首先，初始化信息素，设置各链路信息素的初始值；其次，源节点发送前向蚂蚁(forward ant，FA)，FA中记录经过的节点列表、路径时延和路径的拓扑稳定度信息；然后，中间节点收到FA后，根据节点列表判断是否出现环路；接着，目的节点收到FA后，建立或更新到源节点的信息素路由表项。前向蚂蚁死亡，目的节点生成后向蚂蚁(backward ant，BA)，BA中记录反向路径的时延和拓扑稳定度信息，并复制FA中的节点条目，目的节点对每一个FA都产生BA回复，BA沿FA节点指示路径反向传输，实现多条路径的建立；中间节点收到BA后，建立或更新到目的节点的信息素路由表项，更新BA中的路径度量信息，然后按节点序列指示的下一跳节点继续转发BA；源节点收到BA后建立或更新到目的节点的信息素路由表。源节点收到一个BA建立一条到目的节点的路径，收到多个BA建立多条到目的节点的路径。
　　2.2.2 路由更新
　　源节点每发送K个数据分组，就选取一个分组添加路径度量信息和经过节点的列表，通过更新分组(refreshing packet，RP)，路由表进行更新。更新分组采用普通数据分组规则进行转发；中间节点收到RP后，更新本节点到源节点的信息素路由表，并根据节点获取时间、邻节点、观测周期等信息更新RP中的路径度量。RP后续处理与普通数据包相同；目的节点收到RP时，对源节点的信息素路由表进行更新，RP中的数据部分和普通数据包处理相同。之后，产生BA返回源节点进行正向路径更新。中间节点收到BA的处理和路由发现时相同。
　　3 仿真分析
　　仿真基于同一场景：节点移动采用随机点移动模型，MAC层协议使用IEEE 802.11bDCF，移动节点的无线覆盖距离为200m，信道带宽为2×106bit/s，在1000m×1000m的区域内随机分布50个移动节点，选取10对移动节点发送恒定比特速率数据流(CBR)。每个仿真组合选取5个不同的种子，将平均值作为仿真结果。随着停顿时间的增加，节点的移动性逐渐减弱，仿真结果如图1所示：
　　分析仿真结果，得出如下结论：SAMR和AODV的时延都随着节点移动性的减弱而降低，SAMR的时延性能优于AODV。SAMR选择较稳定的节点进行数据转发，并且根据路径质量动态调整路由权重，此外，路由发现过程中建立多条路径可增强网络的健壮性，时延性能得到提高；SAMR和AODV的吞吐量随着节点移动性的减弱而增加，SAMR的吞吐量比AODV有明显提高，在快速移动场景中性能更好。
参考文献：
[1]郑少仁,王海涛,赵志峰.Ad hoc网络技术[M].北京:人民邮电出版社,2005:64-92
[2]唐泳,马永开.用改进蚁群优化算法求解多目标优化问题[J].电子科技大学学报,2005,34(2):281-284.