无人机自组网中基于蚁群优化的多态感知路由算法

doi:10.12305/j.issn.1001-506X.2021.09.24

摘要/Abstract

摘要：

无人机自组织网络具有节点移动性强、网络拓扑变化快、数据交互频繁、应用环境复杂等特点, 采用传统的路由算法会使该网络在传输延时、丢包率、路由开销等方面性能均较差, 以至于无法为多无人机协同执行任务提供有效的通信保障。为了解决该问题, 提出一种基于蚁群优化的多态感知路由(ant colony optimization based polymorphism-aware routing, APAR)算法。该算法将蚁群算法与动态源路由算法相结合, 通过感知路径长度、路径拥塞度和路径稳定性, 计算出由路由发现过程得到路径的信息素水平, 并将其作为选路标准, 经过改进的信息素挥发机制也被引入该算法。同时, 根据无人机编队的变化做出合适的调整, 以保证其网络性能不下降。仿真结果表明, 与其他经典算法相比, APAR算法提高了数据包成功传输率, 降低了平均端到端延时, 减少了路由开销, 且在战场环境下有较高的可靠性。

关键词: 无人机自组织网络, 蚁群算法, 动态源路由算法, 多态感知, 路径拥塞度, 路径稳定性

Abstract:

AdHoc unmanned aerial vehicle (UAV) network is characterized for its high node mobility, fast changing network topology, high frequency of interchanging data and complex application environment. The performances of traditional routing algorithms are so bad over aspects such as transmitting delay, packet loss rate and routing overhead that they cannot provide efficient communication for multi-UAVs carrying out missions synergistically. To solve the problems, an ant colony optimization based polymorphism-aware routing (APAR) algorithm is proposed. This algorithm integrates ant colony optimization algorithm and dynamic source routing algorithm, and the level of pheromone in routes, which are gained in routing discovery process, is chosen as a standard to choose route and calculated by sensing the distance, the congestion level, and the stability of a route. A new volatilization mechanism of pheromone is also introduced to the algorithm. Meanwhile, the algorithm can make adjustment to the variance of UAV formation to prevent the compromise of the network performance. The simulation results show that compared with traditional algorithms the APAR algorithm improves the data packet transmission ratio, reduces the average end to end delay, reduces the routing overhead and has reliability in battlefield environment.

Key words: AdHoc unmanned aerial vehicle (UAV) network, ant colony algorithm, dynamic source routing algorithm, polymorphism-aware, congestion level of route, stability of route

中图分类号:

V271.4

孙明杰, 周林, 于云龙, 顾金玲. 无人机自组网中基于蚁群优化的多态感知路由算法[J]. 系统工程与电子技术, 2021, 43(9): 2562-2572.

Mingjie SUN, Lin ZHOU, Yunlong YU, Jinling GU. Ant colony optimization based polymorphism-aware routing algorithm for AdHoc UAV network[J]. Systems Engineering and Electronics, 2021, 43(9): 2562-2572.

图/表 9

图1

图2

表1

图3

图4

图5

图6

图7

图8

参考文献 35

1	PERKINS C E, WATSON T J. Highly dynamic destination sequenced distance vector routing (DSDV) for mobile computers[C]//Proc. of the ACM SIGCOMM Conference on Communications Architectures, 1994: 234-255.
2	PEI G, GERLA M, CHEN T W. Fish eye state routing: a routing scheme for ad hoc wireless networks[C]//Proc. of the IEEE International Conference on Communications, 2000.
3	GARCIA-LUNA-ACEVES J J, MARCELO S C. Source-tree routing in wireless networks[C]//Proc. of the 7th Annual International Conference on Network Protocols, 1999: 273-282.
4	CLAUSEN T. Optimized link state routing protocol[C]//Proc. of the IEEE International Multitopics Conference, 2001.
5	MURTHY J J, GARCIA L A. A routing protocol for packet radio networks[C]//Proc. of the 1st Annual ACM International Conference on Mobile Computing and Networking, 1995: 86-95.
6	BELLUR B . Topology dissemination based on reverse-path forwarding (TBRPF)[J]. Proceedings of IEEE International Publication, 2003, 4 (5): 44- 56.
7	PERKINS C, ROYER E. AdHoc on demand distance vector (AODV) routing[C]//Proc. of the IEEE 2nd Workshop on Mobile Computing Systems and Applications, 1999: 90-100.
8	JOHNSON D B , MALTZ A D , BROCH J . DSR: the dynamic source routing protocol for multi-hop wireless adHoc networks[J]. AdHoc Networking, 2001, 5, 139- 172.
9	PEI G, GERLA M, HONG X. A wireless hierarchical routing protocol with group mobility[C]//Proc. of the IEEE Wireless Communications and Networking, 1999: 1538-1542.
10	DUBE R , RAIS C D , WANG K Y , et al. Signal stability based adaptive routing(SSA)for ad hoc mobile networks[J]. IEEE Personal Communications Magazine, 1997, 4 (1): 36- 45. doi: 10.1109/98.575990
11	BAROLLI L, HONMA Y, KOYAMA A. A selective border-casting zone routing protocol for AdHoc networks[C]//Proc. of the 15th International Workshop on Database and Expert Systems Applications, 2004: 326-330.
12	DORIGO M. Optimization, learning and natural algorithms[D]. Milano: Dipartimento di Elettronica, Politecnico DiMilano, 1992.
13	GURPREET S , NEERAJ K , ANIL K V . Ant colony algorithms in MANETs: a review[J]. Journal of Network and Computer Applications, 2012, 35, 1964- 1972. doi: 10.1016/j.jnca.2012.07.018
14	AISSANI M, FENOUCHE M, SADOUR H. Ant-DSR: cache maintenance based routing protocol for mobile ad-hoc networks[C]//Proc. of the 3rd Advanced International Conference in Telecommunications, 2007.
15	ASOKAN R , NATARAJAN A M , VENKATESH C . Ant based dynamic source routing protocol to support multiple quality of service (QoS) metrics in mobile AdHoc networks[J]. International Journal of Computer Science and Security, 2008, 2 (3): 48- 56.
16	WANG J , OSAGIE E , THULASIRAMAN P , et al. HOPNET: a hybrid ant colony optimization routing algorithm for mobile AdHoc network[J]. AdHoc Networks, 2009, 7 (4): 690- 705.
17	RAFSANJANI M K , ASADINIA S . A hybrid routing algorithm based on ant colony and ZHLS routing protocol for MANET[J]. Communications in Computer & Information Science, 2010, 120, 112- 122.
18	ZHU W, SONG M, OLARIU S. Integrating stability estimation into quality of service routing in mobile AdHoc networks[C]//Proc. of the IEEE International Workshop on Quality of Service, 2006.
19	SARMA N , NANDI S . Route stability based QoS routing in mobile AdHoc networks[J]. Wirel Person Communications, 2010, 54, 203- 204. doi: 10.1007/s11277-009-9718-z
20	HU X, WANG J K, WANG C R. Stability-enhanced routing for mobile AdHoc networks[C]//Proc of the International Confe-rence on Computer Design and Applications, 2010: 553-556.
21	DUNG L T, AN B. The analysis of route availability and route stability in mobile AdHoc wireless networks[C]//Proc. of the IEEE International Conference on & International Conference on Ubiquitous Intelligence & Computing, 2014.
22	XIA L, LI Q L, ZOU J, et al. A state-aware routing protocol based on energy and stability for mobile AdHoc network[C]//Proc. of the International Conference on Communication Systems Networks and Applications, 2010: 329-332.
23	MOUSSAOUI A , SEMCHEDINE F , BOUKERRAM A . A link-state QoS routing protocol based on link stability for mobile Ad hoc networks[J]. Journal of Network & Computer Applications, 2014, 39, 117- 125.
24	KIM J Y , TOMAR G S , SHRIVASTAVA L , et al. Load ba-lanced congestion adaptive routing for mobile AdHoc networks[J]. International Journal of Distributed Sensor Networks, 2014, 10 (7): 1- 10. doi: 10.1007/s11277-014-1663-9
25	KANG J, ZHANG Y, NATH B. Accurate and energy-efficient congestion level measurement in ad hoc networks[C]//Proc. of the Wireless Communications & Networking Conference, 2005: 75-83.
26	BASARKOD P I, MANVI S S. Node movement stability and congestion aware anycast routing in mobile AdHoc networks[C]//Proc. of the IEEE International Advance Computing Confe-rence, 2014: 124-131.
27	ANDREA G . Wireless communication[M]. Cambridge: Cambridge University Press, 2005.
28	BETTSTETTER C , HARTENSTEIN H , XAVIER P . Stochastic properties of the random waypoint mobility model[J]. Wireless Networks, 2004, 10 (5): 555- 567. doi: 10.1023/B:WINE.0000036458.88990.e5
29	CSISZAR V , MORI T F . A Bienayme-chebyshev inequality for scale mixtures of the multivariate normal distribution[J]. Mathematical Inequalities and Applications, 2009, 12 (4): 839- 844.
30	HUANG Q , YIN P , CHEN Q , et al. A bioinspired adaptive congestion-avoidance routing for mobile AdHoc networks[J]. Mathematical Problems in Engineering, 2014, 431013. doi: 10.1007/s11277-014-1663-9
31	REINA D G , TORAL S L , JOHNSON P , et al. Improving discovery phase of reactive AdHoc routing protocols using Jaccard distance[J]. Journal of Supercomputing, 2014, 67 (1): 131- 152. doi: 10.1007/s11227-013-0992-x
32	RAMREKHA T A , PANAOUSIS E , POLITIS C . Standar-disation advancements in the area of routing for mobile AdHoc networks[J]. Journal of Supercomputing, 2013, 64 (2): 409- 434. doi: 10.1007/s11227-011-0705-2
33	STOJMENOVIC M . Swarm intelligence for routing in AdHoc wireless networks[J]. Security and Routing in Wireless Networks, 2005, 12, 167- 188.
34	陈余庆, 李桐训, 于双和, 等. 基于势场蚁群算法的机器人全局路径规划[J]. 大连理工大学学报, 2019, 59 (3): 316- 322.
	CHEN Y Q , LI T X , YU S H , et al. Global path planning of robots based on potential field ant colony algorithm[J]. Journal of Dalian University of Technology, 2019, 59 (3): 316- 322.
35	刘中强, 游晓明, 刘升. 启发式强化学习机制的异构双种群蚁群算法[J]. 计算机科学与探索, 2020, 14 (3): 460- 469.
	LIU Z Q , YOU X M , LIU S . Two-population ant colony algorithm based on heuristic reinforcement learning[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14 (3): 460- 469.

参数	值
移动场景/km	1×1
无人机个数	30(稀疏编队) 200(密集编队)
通信半径/m	30
仿真时间/min	10
业务类型	Constant Bit Rate
移动模型	Random Way Point
移动速度/(m/s)	20
MAC协议	IEEE 802.11
无线传输模型	Two-ray ground
无人机放置策略	Random

[1]	宋鑫康, 赵尚弘, 王翔, 郝少伟. 航空信息网络服务功能链协同构建与映射策略[J]. 系统工程与电子技术, 2022, 44(11): 3556-3563.
[2]	任送莲, 孙海权, 靳鹏. 基于任务合成机制的多星调度问题[J]. 系统工程与电子技术, 2021, 43(1): 171-180.
[3]	李莉莉, 张晓勇, 岳伟. 移动自组织网中基于贪婪蚁群算法的广播策略[J]. 系统工程与电子技术, 2020, 42(4): 926-932.
[4]	廖天俊, 余赟. 面向混合变量和任意时间优化的蚁群算法[J]. 系统工程与电子技术, 2017, 39(3): 675-680.
[5]	何磊, 刘晓路, 陈英武, 邢立宁. 面向敏捷卫星任务规划的云层建模及处理方法[J]. 系统工程与电子技术, 2016, 38(4): 852-858.
[6]	肖秦琨, 王弋, 罗艺闯. 偏微分高程图环境蚁群算法的三维路径规划[J]. 系统工程与电子技术, 2015, 37(7): 1550-1561.
[7]	常天庆, 陈军伟, 郝娜, 马殿哲. 装甲分队动态武器目标分配中蚁群算法终止控制[J]. 系统工程与电子技术, 2015, 37(2): 343-347.
[8]	黄峰，陈中起，冯金富，李战武，樊文智. 基于半约束随机搜索的空舰导弹目标分配方法[J]. Journal of Systems Engineering and Electronics, 2013, 35(8): 1676-1680.
[9]	唐贤伦，李亚楠，樊峥. 未知环境中多Agent自主协作规划策略[J]. Journal of Systems Engineering and Electronics, 2013, 35(2): 345-349.
[10]	李红亮，宋贵宝，曹延杰. 多反舰导弹攻击多目标协同航路规划[J]. 系统工程与电子技术, 2013, 35(10): 2102-2109.
[11]	李积英，党建武. 基于量子空间的蚁群算法及应用[J]. 系统工程与电子技术, 2013, 35(10): 2229-2232.
[12]	郭浩，伍国华，邱涤珊. 敏捷成像卫星密集任务聚类方法[J]. Journal of Systems Engineering and Electronics, 2012, 34(5): 931-935.
[13]	吴红, 王维平, 杨峰. 贝叶斯网络参数学习中的连续变量离散化方法[J]. Journal of Systems Engineering and Electronics, 2012, 34(10): 2157-2162.
[14]	焦亚萌，黄建国，侯云山. 基于蚁群算法的最大似然方位估计快速算法[J]. Journal of Systems Engineering and Electronics, 2011, 33(8): 1718-1721.
[15]	麻士东, 龚光红, 韩亮, 宋晓. 目标分配的蚁群-模拟退火算法及其改进[J]. Journal of Systems Engineering and Electronics, 2011, 33(5): 1182-.