【2023年第10期】基于蚁群优化的混合多路径QoS路由协议
"移动自组织"专题 04
基于蚁群优化的混合多路径QoS路由协议
顾斌1，陆杰2，张策1
（1.南京邮电大学通信与信息工程学院，江苏 南京 210003；
2.中国电科新一代移动通信创新中心，江苏 南京 210019）
【摘 要】针对移动自组网中不同种类业务QoS保障问题，提出基于蚁群优化的混合多路径QoS路由协议（HMQ-ACO），该协议融合了反应式路由建立与主动式路由维护的策略并支持多路径，根据多约束QoS条件建立目标函数，并基于该目标函数设计信息素更新机制，同时考虑节点拥塞度和费用，利用蚁群优化算法寻找满足带宽、时延、丢包率约束的路径集合，依据目标函数值选择合适路径。仿真结果表明，所提出的协议在端到端时延、分组传递率方面优于其他传统路由协议。
【关键词】移动自组网；QoS；蚁群优化；多路径；路由协议
doi:10.3969/j.issn.1006-1010.20230825-0004
中图分类号：TN929.5 文献标志码：A
文章编号：1006-1010(2023)10-0024-00
引用格式：顾斌,陆杰,张策. 基于蚁群优化的混合多路径QoS路由协议[J]. 移动通信, 2023,47(10): 24-31.
GU Bin, LU Jie，ZHANG Ce. Hybrid Multipath QoS Routing Protocol Based on Ant Colony Optimization[J]. Mobile Communications, 2023,47(10): 24-31.
0 引言
移动自组网（MANET, Mobile Ad hoc Network）是由无线链路连接的移动节点组成的网络[1-4]。在这种网络中，节点的位置和连接状态都会频繁变化，因此需要具备适应快速变化环境的路由协议。目前，针对MANET已经开发了许多路由协议，如AODV（Ad hoc On-Demand Distance Vector Routing，无线自组网按需平面距离向量路由协议）、DSR（Dynamic Source Routing，动态源路由协议）、OLSR（Optimized Link State Routing，优化链路状态路由协议）等，然而，这些协议都着眼于找到从源到目的地的可行路径，它们未能很好地适应多种网络流量和QoS（Quality of Service，服务质量）需求，而当今众多应用程序正需要高质量的网络服务。因此，对路由协议进行QoS保障成为必要之举。
合理的QoS路由协议能够为业务提供满足一系列服务要求的路径[5-8]，这些服务要求是通过带宽、延迟、抖动、丢包率等多个可量化的指标来度量的。
近年来，研究者们从负载均衡、带宽预留等角度提出许多QoS路由协议，扩展了传统路由协议，根据路由发现和维护策略这些协议可以划分为两类：主动式路由协议和反应式路由协议[9]。主动式路由协议维护节点的完整路由信息，以便在需要转发数据时迅速找到合适路由，这类协议需要持续更新和交换路由信息以应对网络拓扑变化，其路由开销较大。而反应式协议则仅在节点需要传输信息时才寻找路由，避免了周期性的路由信息交换，从而减小了路由开销。文献[10]应用多路径路由策略提高了分组投递率和吞吐量，但是开销很大，并且无法应对快速移动场景下的QoS路由问题。文献[11]在传统AODV基础上引入跨层路由以解决QoS路由问题，却没有考虑业务对时延的要求。
由于多约束QoS问题在文献[12]中已经被证实是一个NP-C（Nondeterministic Polynomial Time Complete，非确定性多项式时间完全）问题，并且针对NP-C问题人们大多采用启发式算法解决，使得蚁群优化算法、遗传算法等智能算法得到广泛应用。而蚁群优化（ACO, Ant Colony Optimization）通过模拟蚂蚁寻找食物的行为，具有一些独特的特性，包括分布式计算、正反馈机制、贪婪启发式和灵活性等。首先，ACO算法的分布式计算特点与传统的集中式算法不同，其将问题分解为多个蚂蚁个体，每只蚂蚁根据局部信息素和问题相关的启发式信息独立地选择路径和做出决策，再将其经验贡献到全局信息素中，使它们在分布式环境中协作解决问题，在处理网络模型问题时具有出色的拓展性和并行性。其次，正反馈意味着蚂蚁更有可能选择已知信息素浓度高的路线，有助于加速全局最优路径的搜索。最后，蚂蚁在路径选择时不仅考虑信息素浓度，还考虑基于需求设计的启发式信息，可以帮助蚂蚁更有针对性选择路径，提高路径质量。基于蚁群优化的这些特性，使得本文选择它处理路由多约束QoS问题。文献[13]基于AntNet蚁群算法引入QoS约束机制，考虑负载均衡来选择节点。文献[14]基于蚁群算法综合考虑带宽、跳数、端到端时延三种QoS参数来计算路径优先的概率，以选择合适的路径来传输数据。文献[15]引入奖励函数，信息素更新时奖励优秀蚂蚁，提高了算法的收敛能力。文献[16]提出基于蚁群算法的混合路由，其在路由建立时考虑端到端延迟指标和节点位置信息。文献[17]提出基于区域的混合路由协议HRP，综合DSDV和DSR协议的优势，具有从主动性切换到反应性的功能。
虽然以上QoS路由协议具有一些优势，但是这些协议存在一些局限：
（1）缺乏考虑不同种类业务问题，不同应用可能对QoS参数有不同的要求，没有充分考虑带宽、时延、丢包率、链路拥塞、费用要求。
（2）传统蚁群算法会存在收敛速度慢，易于陷入局部最优解问题。
（3）大多协议没有兼顾路由建立和维护两个关键阶段，使得协议在动态网络环境下十分脆弱。
针对以上局限性，本文提出了一种基于蚁群优化的混合多路径QoS路由协议。首先，HMQ-ACO（Hybrid Multipath QoS Routing Protocol Based on Ant Colony Optimization）引入多约束QoS指标，充分考虑多种业务需求，如会话和交互类业务。其次，协议中蚁群优化算法改进了传统蚁群算法，先是加入新的启发式信息来建立路径选择模型，并采用多路径并行搜索以避免陷入局部最优解，然后重新设计局部和全局信息素更新规则，引导蚂蚁选择较优的路径，来加快蚁群算法收敛速度。最后，HMQ-ACO结合主动式和反应式路由协议的优点，设计反应式蚂蚁和主动式蚂蚁来建立和维护最佳路径。
2.2 HMQ-ACO路由协议流程
HMQ-ACO是混合式路由协议，综合了反应式路由建立和主动式路由维护的策略，以达到有效的路径选择和优化目的。反应性表现在节点在会话开始时才建立到目的地的路由，而主动性则表现在会话期间，协议尝试维护和改进已建立的路由信息。HMQ-ACO通过创建多条路径来连接源节点和目的节点，从而提高网络的可靠性和鲁棒性。
(1)反应式QoS路由建立流程
当源节点(标记为s)与目的节点(标记为d)需要建立会话时，且当前的路由表中不存在满足会话QoS要求的s到d的路径时，开始进行反应式路由建立。此过程包括两种控制包：反应式前向蚂蚁（RFA，Reactive Forward Ant）和反应式后向蚂蚁（RBA，Reactive Backward Ant）。反应式路由建立步骤如下：
步骤1. 反应式前向蚂蚁RFA从源节点广播出发，其结构如图1所示。RFA携带源节点地址、目的节点地址、蚂蚁代数编号、QoS约束指标值、路径上的QoS度量值以及禁忌表P，记录从源节点s到目的节点d经过的节点；
步骤2. 当中间节点i收到RFA时，先根据RFA中的源节点地址和代数编号判断是否处理过此报文，如果是，直接丢弃；然后检查自身地址是否在禁忌表P中出现，如果是，直接丢弃，以避免环路；否则进入步骤3；
步骤3. 节点i收到RFA时，检查是否为目标节点。若是，进入步骤4；否则执行以下操作：
①提取RFA的时延值D，判断D与本节点的处理时延之和是否满足时延约束。若不满足，则丢弃RFA；否则，继续执行②。
②判断节点i的剩余带宽是否满足RFA的带宽约束。若不满足，表明自身带宽资源不满足QoS要求，丢弃RFA；否则，继续执行③。
③检查节点的丢包率是否满足RFA的丢包率约束。若不满足，丢弃RFA；否则，继续执行④。
④将RFA携带的代数编号和源节点地址添加到本地识别列表，对于从源节点到当前节点的路径，进行本地路由表的添加或更新操作，以反映出反向路由的信息。路由表包括了源地址、目的地址、下一跳节点地址和跳数，同时还有与业务相关的QoS约束，包括业务带宽约束、时延约束和丢包率约束，以及当前节点拥塞度。
⑤将RFA的代数编号k提取，则当蚂蚁k在中继节点i发现到目的节点d有多条可用的路由时，根据式(13)的概率
⑥当前向蚂蚁k完成一次路径选择后，RFA在转发到下一跳的过程中，链路(i,j)的信息素按照式(15)进行局部信息素更新。
步骤4. 所有反应式前向蚂蚁从s到d的旅程结束，即当所有蚂蚁完成一次迭代，根据式(9)计算每只蚂蚁的目标函数K。
通过评估每次迭代后不同蚂蚁所经过路径的目标函数值，选择K值较大的M只反应性前向蚂蚁，对它们进行信息，然后销毁这些蚂蚁。随后，构造反应式后向蚂蚁RBA，其结构如图2所示，将来自RFA的相关信息填充到RBA相关字段，具体包括跳数值和信息素奖励值。此外，还将之前禁忌表P反过来添加到RBA中。最终它将沿着RFA的路径单播返回到源节点s。
步骤5. 反应式后向蚂蚁不被广播，每经过一个中间节点i，会进行以下操作：
①蚂蚁k每到一个节点按式(17)更新本地路由表的跳数信息：
式(17)中hij表示节点i经节点j到达目的节点d的平均跳数历史记录；
②根据式(16)的全局信息素更新规则更新本地信息素表。
步骤6. RBA回到源节点s，该蚂蚁被丢弃，此时建立了源节点到目的节点的正向路由。
根据步骤1至步骤3画出反应式前向路由建立过程如图3所示，根据步骤4至步骤6画出反应式后向路由建立过程如图4所示。
在建立了到目的节点路径之后，会通知业务进行数据发送，数据包根据路由表中的信息进行转发。如果节点存在多条到目标的路径，则尽可能选最优路径。
（2）主动式QoS路由维护
主动式路由维护旨在通过更新信息素值来保证路径选择的准确性和时效性，从而有效维护网络的路由状态。
源节点周期性地派发主动式前向蚂蚁（PFA，Proactive Forward Ant），以维护已构建路径的完整性并寻求更优或替代性的路径。PFA结构与RFA相同，并且都是由源节点广播，中间节点单播转发, 其派发速率会根据网络负载情况和流量变化动态调整，与主动数据发送速率相协调。
PFA在传播过程中收集与已建立路径有关的最新信息，并通过转化为相应的主动式后向蚂蚁（PBA，Proactive Backword Ant），更新路径上节点的路由表中的信息素值。
（3）链路断裂检测和路由修复
移动自组网中的链路断裂是一个重要的问题[22]，因为移动节点之间的链路不稳定，容易导致通信中断。为了检测链路断裂，协议中采用Hello消息蚂蚁（Hant，Hello Ant）检测机制和数据包传输失败检测机制两种。Hant结构包含源节点地址、蚂蚁代数编号、检测标志位。
每个节点定期发送Hant管理邻居节点，Hant只在一跳内转发，不能广播。若某节点在一定时间内未收到来自邻居的Hant，则是为检测到邻居链路断裂，会采取以下措施：本地节点将该邻居节点从邻居列表删除，并会向其他邻居节点广播链路断裂的消息，所有接收到此消息的邻居也会更新路由表。
如果源节点检测到数据包传输失败，并且不存在其他可用路径，则将数据包放入缓冲区并启动路由修复过程。
路由修复过程是由路由修复前向蚂蚁（RFFA，Route Fixing Forward Ant）和路由修复后向蚂蚁（RFBA，Route Fixing Backward Ant）完成，主要是为了尽快寻找到到达目的点的路径，RFFA和RFBA结构相同，包括目的节点地址、源地址、代数编号、失败链路信息。RFFA沿着反应式前向蚂蚁所采取的路径前进到指定目的地（在该节点广播，在后续节点单播），然后转化成为RFBA返回源节点。如果RFBA返回到源节点，则继续发送存在缓冲区的数据包。如果在一定时间内没有收到RFBA，则节点会认为路径修复失败。然后，它会广播丢失目标的链路故障通知并丢弃所有临时缓冲的数据包。
3 仿真设置与结果分析
3.1 仿真设置
本节对提出的HMQ-ACO路由协议进行仿真验证，并选择AODV、文献[13]AntNet-QoS协议以及文献[16]中的路由协议作对比分析，选择它们的理由是为了充分评估HMQ-ACO在MANET中的性能和优越性。首先，AODV代表传统的反应式路由协议，其优势在于快速路由建立，与其对比，旨在评估HMQ-ACO在网络动态性较高时路由建立和数据传输表现以及能否有效降低时延。其次，文献[13]中AntNet-QoS基于蚁群算法并考虑了带宽、时延等QoS约束，与其对比，来衡量HMQ-ACO在QoS支持方面的性能。最后，文献[16]路由协议基于蚁群优化算法并采用混合路由方法，与之对比，考察HMQ-ACO在复杂网络环境中的QoS保障性能，以及是否能够建立并维护好路由，保证较高分组传递率。
仿真中节点按照RWP（RandomWaypoint，随机路径点）移动模型来移动，并会有停顿时间。采用两径衰落信号传播模型模拟无线电传播，物理层采用IEEE 802.11协议，链路带宽为2 Mbps。MAC层使用802.11b协议。考虑通信业务主要为话音数据流。仿真场景参数配置如表1所示，协议参数配置如表2所示。
3.2 结果分析
本节考虑了数据包的端到端延迟和传递率这2个性能指标。
首先，在第1组实验中，改变节点速度从5 m/s变化到30 m/s。仿真结果如图5和图6。
图5为不同协议随节点速度变化时的端到端时延。显然AODV的时延性能较差，由于它只能寻找从源到目的地的最短路由，而且其所构建的路径不符合QoS概率也很高，当其在QoS业务不能满足要求时，它会重复构建路径，从而造成了平均端到端时延随速率的较大幅度上升。而其他的3类ACO协议均采用QoS，尽管时随着速率提高端到端时延也会有所增加，但受到平均端到端时延的制约，其平均端到端时间延迟的增加幅度相对较小。
图6为不同协议随节点速度变化时的分组投递率。对于所有协议，分组投递率都随着节点速度的增加而降低。值的注意的是3种基于蚁群优化思想的协议在分组投递率方面表现明显均优于AODV，这种优势归因于AODV在建立路由时未考虑QoS支持，因此在传输QoS敏感的业务时，其传输失败率相对较高。在这些ACO类协议中，HMQ-ACO达到了最高分组投递率,这一成就可以归功于在路由建立过程中尽量避免了拥塞节点，因此在这一方面胜过了AntNet-QoS和文献[16]的协议。
接下来，第2组实验中逐步增加节点数量，从100增加到800，同时按比例增加网络面积以保持节点密度稳定。图7和图8展示了相应结果。
图7为不同协议随节点数量变化时的端到端时延。HMQ-ACO表现很好，但是AODV落后很多，而且随着网络规模的增加，差距越来越大。AntNet-QoS和文献[16]协议时延表现相近。
图8为不同协议随节点数量变化时的分组投递率。4种协议的分组投递率都会随着节点数量的增加而下降。但HMQ-ACO能够比其他协议正确的传送更多的数据包。此外，性能的差距随着网络规模的增加而增加。对于最大的网络规模，HMQ-ACO仍能提供80%的投递率,这是由于HMQ-ACO可以搜索多条路径，有很多替代方案，因此在链路故障后重建路由相对容易。而AntNet-QoS和文献[16]协议时延表现相近。
4 结束语
本文针对MANET中传统蚁群优化QoS的路由协议的局限性，改进了蚁群算法的路径选择模型和信息素更新策略，并采用特殊的混合路由协议设计思想，综合考虑多种QoS约束指标以及链路拥塞度、费用，提出基于蚁群优化的混合多路径QoS路由协议HMQ-ACO。仿真结果表明，HMQ-ACO在端到端延迟、数据包传递率方面表现较好。在未来的研究工作中，会考虑更多业务种类，并优化路由协议的开销。
参考文献：（上下滑动浏览）
[1] Nallusamy C, Sabari A. Particle Swarm Based Resource Optimized Geographic Routing for Improved Network Lifetime in MANET[J]. Mobile Networks and Applications,2019,24(2): 375-385.
[2] A S A, Abdulhussein A J A, Fadhil E A. Mobile ad hoc network (MANET) proactive and reactive routing protocols[J]. Journal of Discrete Mathematical Sciences and Cryptography,2021,24(7): 2017-2025.
[3] Kranthi S, Shawan A A, Vijaya S K, et al. The Performance Analysis and Security Aspects of Manet[J]. Electrochemical Society Transactions, 2022,107(1):10945-10955.
[4] 王涵. 移动自组织网络分析[J]. 无线互联科技, 2018,15(23): 22-23.
[5] Pradeep Karanje, Ravindra Eklarker. Efficient Multipath Routing to Increase QoS by Link Estimation and Minimum Interference path in MANET'S[J]. International Journal of Engineering and Advanced Technology,2019,9(2):4806-4811.
[6] S.G. Ramesh kumar, N. Vijaya Lakshmi. Multipath Routing for Balancing the Load in Manet[J]. International Journal of Engineering and Advanced Technology,2019,9(2): 3466-3468.
[7] A W , R A. QOS Analysis of Routing Protocol Babel on Mobile Ad-Hoc Network (MANET)[J]. IOP Conference Series: Materials Science and Engineering, 2020,771(1): 12032-12037.
[8] Badhe K M, Jain S D. Implementation of Mobility and QoS Aware Energy Efficient Anycast Routing in MANET[J]. International Journal of Advanced Networking and Applications,2017,9(1) 3338-3344.
[9] 杨绪彬,张文强. 移动自组织网络中服务质量路由协议的研究与展望[J]. 计算机应用, 2015,35(S2): 11-13+26.
[10] 王迤冉,郑光,刘云霞. MANET中基于链路稳定性的链路状态QoS路由协议[J]. 计算机应用研究, 2015,32(09): 2757-2761+2765.
[11] 何超男,林威,刘佳. 一种基于QoS的改进AODV路由协议设计及其实现[J]. 物联网技术, 2015,5(08): 32-34+37. DOI:10.16667/j.issn.2095-1302.2015.08.019.
[12] CHEN S, Nahrstedt K. On Finding Multi-Constrained Paths[C]//ICC98: Proceedings of the 1998 IEEE Inter-national Conference on Communications. Piscataway:IEEE,1998,2: 874-879.
[13] 朱尚明,高大启. AntNet的多路径QoS路由算法研究[J]. 智能系统学报, 2008(04):349-354.
[14] Kute B V, Kharat U M. Analysis of Quality of Service for the AOMDV Routing Protocol[J]. Engineering, Technology & Applied Science Research, 2013,3(1):359-362.
[15] 陈岩,杨华江,沈林成. 基于再励学习蚁群算法的多约束QoS路由方法[J]. 计算机科学,2007(05):25-27+44.
[16] Di Caro G, Ducatelle F, Gambardella L. AntHocNet: anadaptive nature-inspired algorithm for routing in mobile ad hocnetworks[J].European Transactions on Telecommunications,Special Issue on Self-Organization in Mobile Networking,2005,2:134-143.
[17] S.R. Biradar, Hiren Kumar Deva Sarma, Subir Kumar Sarkar and Puttamadappa C. Hybrid (Day-Night) Routing Protocol for Mobile Ad-Hoc Networks[J]. Proceedings of International Conference on Microwave, 2008,8:875-877.
[18] 尹凤杰,褚群森. 基于改进蚁群算法的QoS路由研究[J]. 辽宁大学学报(自然科学版), 2020,47(04): 312-318.
[19] 袁玉莹,付雄. 基于扩展Dijkstra的多约束QoS路由研究[J]. 计算机技术与发展, 2021,31(11): 122-128.
[20] Sllame M A. Evaluating the Impact of Routing on QoS of VoIP over MANET Wireless Networks[J]. Open Access Library Journal,2017,4(2):1-22.
[21] 杨绪彬,张文强. 一种多子网战术MANET中基于蚁群优化的QoS路由算法[J]. 通信技术, 2018,51(10): 2396-2401.
[22] 王迤冉,郑光,刘云霞. MANET中基于链路稳定性的链路状态QoS路由协议[J]. 计算机应用研究, 2015,32(09): 2757-2761+2765. ★
★扫描二维码，到知网阅读下载本篇论文
★原文发表于《移动通信》2023年第10期★
doi:10.3969/j.issn.1006-1010.20230825-0004
中图分类号：TN929.5 文献标志码：A
文章编号：1006-1010(2023)10-0024-00
引用格式：顾斌,陆杰,张策. 基于蚁群优化的混合多路径QoS路由协议[J]. 移动通信, 2023,47(10): 24-31.
GU Bin, LU Jie，ZHANG Ce. Hybrid Multipath QoS Routing Protocol Based on Ant Colony Optimization[J]. Mobile Communications, 2023,47(10): 24-31.
《移动通信》投稿方式为在线投稿
请您登录网页投稿系统
链接地址：http://ydtx.cbpt.cnki.net
面向6G的物联网技术 | 2023年第8期专题论文（11篇）
空天地海一体化网络 | 2023年第7期专题论文（13篇）
《移动通信》用论文解读通信
《移动通信》杂志由中国电子科技集团公司主管，中国电子科技集团公司第七研究所主办，是中国期刊方阵“双效期刊”、工业和信息化部精品电子期刊、中国科技论文统计源刊、中国科协《高质量科技期刊分级目录》入选期刊、日本JST收录期刊。国内连续出版物号：CN44-1301/TN，国际连续出版物号：ISSN1006-1010，邮发代号：46-181。