利用离散时间聚合图的无人机编队最短时延路由协议

李博; 王改芳; 杨洪娟; 茹雪菲; 张敬淳; 王钢

doi:10.11999/JEIT230707

利用离散时间聚合图的无人机编队最短时延路由协议

doi: 10.11999/JEIT230707

1.
哈尔滨工业大学(威海)信息科学与工程学院威海 264209
2.
哈尔滨工业大学通信技术研究所哈尔滨 150001

基金项目: 国家自然科学基金(62171154, 61971156)，山东省自然科学基金(ZR2020MF007)，广东省空天通信与网络技术重点实验室开放基金(2018B030322004)

详细信息

作者简介:
李博：男，副教授，研究方向为空天地网络、飞行自组织网络、物理层网络编码

王改芳：女，硕士生，研究方向为时变图理论、无人机自组网

杨洪娟：女，副教授，研究方向为无线通信、水声通信、无人机网络

茹雪菲：女，博士生，研究方向为无线携能通信

张敬淳：男，博士生，研究方向为海洋通信感知一体化

王钢：男，教授，研究方向为物理层网络编码、通信网理论与技术、数据通信

通讯作者:
杨洪娟　hjyang@hit.edu.cn

中图分类号: TN929.5
计量
- 文章访问数: 235
- HTML全文浏览量: 145
- PDF下载量: 43
- 被引次数: 0
出版历程
- 收稿日期: 2023-07-15
- 修回日期: 2024-01-17
- 网络出版日期: 2024-01-25
- 刊出日期: 2024-05-30

Shortest Delay Routing Protocol for UAV Formation with Discrete Time Aggregation Graph

1.
School of Information Science and Engineering, Harbin Institute of Technology at Weihai, Weihai 264209, China
2.
Communication Research Center, Harbin Institute of Technology, Harbin 150001, China

Funds: The National Natural Science Foundation of China (62171154, 61971156), The Natural Science Foundation of Shandong Province (ZR2020MF007), The Research Fund Program of Guangdong Key Laboratory of Aerospace Communication and Networking Technology (2018B030322004)

摘要

摘要: 针对传统的无人机编队路由算法无法有效利用拓扑变化的可提前预知特性、以发送探测包的方式获取链路的连接情况会导致开销大等问题，该文引入时变图模型，提出了基于离散时间聚合图的无人机编队最短时延路由协议。首先，利用无人机编队网络的先验知识，如节点的运动轨迹以及网络拓扑变化情况，使用离散时间聚合图对网络的链路资源和拓扑进行表征。其次，基于该图模型设计路由决策算法，即在路由探索阶段将链路时延作为链路权重求解网络的源节点到目的节点的最短时延路由。最后，性能仿真结果表明，该路由协议与传统按需距离矢量路由协议相比提高了网络的分组投递率、降低了端到端时延和网络的控制开销。
- 无人机自组网 /
- 无人机编队 /
- 时变图模型 /
- 最短时延路由
Abstract: Aiming at the problems that the traditional UAV formation routing algorithm cannot effectively utilize the advance predictability of topology changes, and the high cost is caused by acquiring the link connection by sending detection packets, a UAV formation shortest delay routing protocol based on discrete time aggregation graph is proposed by introducing the time-varying graph model. Firstly, using the prior knowledge of the UAV formation network, such as the movement trajectory of nodes and the network topology changes, the network link resources and network topology are characterized by using the discrete time aggregation graph. Secondly, the routing decision algorithm is designed based on the graph model. The delay in the process of route discovery is used as the link weight to solve the shortest delay route from the source node to the destination node of the network. Finally, the simulation performance shows that the routing protocol improves the packet delivery rate, reduces the end-to-end delay and diminishes the network control overhead compared with the traditional Ad-hoc On-Demand Distance Vector routing protocol.
- UAV ad hoc network /
- UAV formation /
- Time-varying graph model /
- Shortest delay route

HTML全文

图 1 常用的无人机编队路由协议分类

下载: 全尺寸图片幻灯片

图 2 离散时间聚合图模型

下载: 全尺寸图片幻灯片

图 3 三节点离散时间聚合图模型

下载: 全尺寸图片幻灯片

图 4 先进先出与非先进先出原则示意图

下载: 全尺寸图片幻灯片

图 5 到达时间转换示意图

下载: 全尺寸图片幻灯片

图 6 网络节点密度对两种协议平均端到端时延的影响

下载: 全尺寸图片幻灯片

图 7 网络节点密度对两种协议分组投递率的影响

下载: 全尺寸图片幻灯片

图 8 网络节点密度对两种协议路由控制开销的影响

下载: 全尺寸图片幻灯片

图 9 网络节点移动速度对两种协议平均端到端时延的影响

下载: 全尺寸图片幻灯片

图 10 网络节点移动速度对两种协议分组投递率的影响

下载: 全尺寸图片幻灯片

图 11 网络节点移动速度对两种协议路由控制开销的影响

下载: 全尺寸图片幻灯片

1 基于离散时间聚合图的无人机编队最短时延路由算法

输入：无人机编队在给定时间 $T$ 内的移动轨迹，源节点 $s$ ，目的　节点 $d$ 和开始时间 ${t_{{\mathrm{start}}}}$
输出：在 ${t_{{\mathrm{start}}}}$ 时刻从源节点 $s$ 到目的节点 $d$ 的最短时延路径
1：根据编队移动轨迹计算网络的离散时间聚合图 $G = (V,E)$ ，　其中 $V$ 表示节点集， $E$ 表示链路集，且每条边 $e \in E$ 都有对应的　链路传播时延序列
2：根据ATST转换将链路传播时延序列转换为到达时间序列
3：变量初始化，令 ${c_{{\mathrm{ss}}}} = {t_{{\mathrm{start}}}}$ ； $\forall d \ne s,{c_{{\mathrm{sd}}}} = \infty$ ； $Q = \{ s\}$ ；　 $P = \varnothing$ // ${c_{{\mathrm{sd}}}}$ 为从节点 $s$ 出发，节点 $d$ 的最早到达时间
4：if $Q \ne \varnothing$ do
5：　从 $Q$ 中提取头部节点 $u$ 并将节点 $u$ 的邻居节点加入 $P$ 中
6：　if $P \ne \varnothing$ do
7：　　从 $P$ 中提取头部节点 $v$ ，并计算 ${c'_{{\mathrm{sv}}}} = \min\{ {T_{{\mathrm{uv}}}}(t)\}$
8：　　if ${c'_{{\mathrm{sv}}}} < {c_{{\mathrm{sv}}}}$ do
9：　　　更新节点 $v$ 的最早到达时间 ${c'_{{\mathrm{sv}}}} = {c_{{\mathrm{sv}}}}$ 和 $v$ 的上一跳节　　　　　点 ${{\mathrm{parent}}_{{\mathrm{sv}}}} = u$
10：　　若节点 $v$ 未被遍历，则将节点 $v$ 加入队列 $Q$
11：　 end
12： else do
13：　返回步骤4
14： end
15：end
16：输出源节点到目的节点的最短时延 ${c_{{\mathrm{sd}}}} - {c_{{\mathrm{ss}}}}$ 以及对应的路径

下载: 导出CSV

表 1 部分参数设置

仿真参数	参数值	仿真参数	参数值
移动范围	1000 m×1000 m	节点移动模型	追踪群移动模型
MAC层协议	802.11g	网络带宽	2 Mbit/s
传输距离	250 m	仿真时间	200 s
连接对数	10	最大队列	50
数据包大小	512 Byte	数据发送速率	4个/s
节点初始能量	60 J	节点发送功率	0.665 W

下载: 导出CSV

参考文献(17)

[1]	AZARI M M, GERACI G, GARCIA-RODRIGUEZ A, et al. UAV-to-UAV communications in cellular networks[J]. IEEE Transactions on Wireless Communications, 2020, 19(9): 6130–6144. doi: 10.1109/TWC.2020.3000303.
[2]	陈新颖, 盛敏, 李博, 等. 面向6G的无人机通信综述[J]. 电子与信息学报, 2022, 44(3): 781–789. doi: 10.11999/JEIT210789. CHEN Xinying, SHENG Min, LI Bo, et al. Survey on unmanned aerial vehicle communications for 6G[J]. Journal of Electronics & Information Technology, 2022, 44(3): 781–789. doi: 10.11999/JEIT210789.
[3]	YOU Wenjing, DONG Chao, CHENG Xiao, et al. Joint optimization of area coverage and mobile-edge computing with clustering for FANETs[J]. IEEE Internet of Things Journal, 2021, 8(2): 695–707. doi: 10.1109/JIOT.2020.3006891.
[4]	SRILAKSHMI U, ALGHAMDI S A, VUYYURU V A, et al. A secure optimization routing algorithm for mobile ad hoc networks[J]. IEEE Access, 2022, 10: 14260–14269. doi: 10.1109/ACCESS.2022.3144679.
[5]	SRIVASTAVA A, BAGGA N, and RAKHRA M. Analysis of cluster-based and position-based routing protocol in VANET[C]. Proceedings of the 2021 9th International Conference on Reliability, Infocom Technologies and Optimization (Trends and Future Directions), Noida, India, 2021: 1–5. doi: 10.1109/ICRITO51393.2021.9596325.
[6]	KANG Hongyue, CHANG Xiaolin, MIŠIĆ J, et al. Improving dual-UAV aided ground-UAV bi-directional communication security: Joint UAV trajectory and transmit power optimization[J]. IEEE Transactions on Vehicular Technology, 2022, 71(10): 10570–10583. doi: 10.1109/TVT.2022.3184804.
[7]	DARABKH K A, ALFAWARES M G, and ALTHUNIBAT S. MDRMA: Multi-data rate mobility-aware AODV-based protocol for flying ad-hoc networks[J]. Vehicular Communications, 2019, 18: 100163. doi: 10.1016/j.vehcom.2019.100163.
[8]	LI Xianfeng and YAN Jiaojiao. LEPR: Link stability estimation-based preemptive routing protocol for flying ad hoc networks[C]. Proceedings of 2017 IEEE Symposium on Computers and Communications, Heraklion, Greece, 2017: 1079–1084. doi: 10.1109/ISCC.2017.8024669.
[9]	GANKHUYAG G, SHRESTHA A P, and YOO S J. Robust and reliable predictive routing strategy for flying ad-hoc networks[J]. IEEE Access, 2017, 5: 643–654. doi: 10.1109/ACCESS.2017.2647817.
[10]	LEE S W, ALI S, YOUSEFPOOR M S, et al. An energy-aware and predictive fuzzy logic-based routing scheme in flying ad hoc networks (FANETS)[J]. IEEE Access, 2021, 9: 129977–130005. doi: 10.1109/ACCESS.2021.3111444.
[11]	TANG Zhu, YU Wanrong, ZHAO Baokang, et al. Time-efficient transient loops avoiding in snapshot routing algorithm[C]. Proceedings of 2014 International Conference on Smart Computing Workshops, Hong Kong, China, 2014: 57–64. doi: 10.1109/SMARTCOMP-W.2014.7046668.
[12]	KÖHLER E, LANGKAU K, and SKUTELLA M. Time-expanded graphs for flow-dependent transit times[C]. Proceedings of the 10th Annual European Symposium on Algorithms, Rome, Italy, 2002: 599–611. doi: 10.1007/3-540-45749-6_53.
[13]	GEORGE B and SHEKHAR S. Time-aggregated graphs for modeling spatio-temporal networks[C]. Proceedings of International Conference on Conceptual Modeling, Tucson, USA, 2006: 85–99. doi: 10.1007/11908883_12.
[14]	GEORGE B, KIM S, and SHEKHAR S. Spatio-temporal network databases and routing algorithms: A summary of results[C]. Proceedings of the 10th International Symposium on Spatial and Temporal Databases, Boston, USA, 2007: 460–477. doi: 10.1007/978-3-540-73540-3_26.
[15]	LI Hongyan, ZHANG Tao, ZHANG Yangkun, et al. A maximum flow algorithm based on storage time aggregated graph for delay-tolerant networks[J]. Ad Hoc Networks, 2017, 59: 63–70. doi: 10.1016/j.adhoc.2017.01.006.
[16]	ZHANG Tao, LI Hongyan, ZHANG Shun, et al. STAG-based QoS support routing strategy for multiple missions over the satellite networks[J]. IEEE Transactions on Communications, 2019, 67(10): 6912–6924. doi: 10.1109/TCOMM.2019.2929757.
[17]	LEI Liu and LI Hongyan. A routing policy based on time-varying graph for predictable delay tolerant networks[C]. Proceedings of 2015 International Conference on Wireless Communications & Signal Processing, Nanjing, China, 2015: 1–6. doi: 10.1109/WCSP.2015.7341072.