Shortest Delay Routing Protocol for UAV Formation with Discrete Time Aggregation Graph
-
摘要: 针对传统的无人机编队路由算法无法有效利用拓扑变化的可提前预知特性、以发送探测包的方式获取链路的连接情况会导致开销大等问题,该文引入时变图模型,提出了基于离散时间聚合图的无人机编队最短时延路由协议。首先,利用无人机编队网络的先验知识,如节点的运动轨迹以及网络拓扑变化情况,使用离散时间聚合图对网络的链路资源和拓扑进行表征。其次,基于该图模型设计路由决策算法,即在路由探索阶段将链路时延作为链路权重求解网络的源节点到目的节点的最短时延路由。最后,性能仿真结果表明,该路由协议与传统按需距离矢量路由协议相比提高了网络的分组投递率、降低了端到端时延和网络的控制开销。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.
-
Key words:
- UAV ad hoc network /
- UAV formation /
- Time-varying graph model /
- Shortest delay route
-
1 基于离散时间聚合图的无人机编队最短时延路由算法
输入:无人机编队在给定时间T内的移动轨迹,源节点s,目的
节点d和开始时间tstart输出:在tstart时刻从源节点s到目的节点d的最短时延路径 1:根据编队移动轨迹计算网络的离散时间聚合图G=(V,E),
其中V表示节点集,E表示链路集,且每条边e∈E都有对应的
链路传播时延序列2:根据ATST转换将链路传播时延序列转换为到达时间序列 3:变量初始化,令css=tstart;∀d≠s,csd=∞;Q={s};
P=∅ //csd为从节点s出发,节点d的最早到达时间4:if Q≠∅ do 5: 从Q中提取头部节点u并将节点u的邻居节点加入P中 6: if P≠∅ do 7: 从P中提取头部节点v,并计算c′sv=min{Tuv(t)} 8: if c′sv<csv do 9: 更新节点v的最早到达时间c′sv=csv和v的上一跳节
点parentsv=u10: 若节点v未被遍历,则将节点v加入队列Q 11: end 12: else do 13: 返回步骤4 14: end 15:end 16:输出源节点到目的节点的最短时延csd−css以及对应的路径 表 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 -
[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. 期刊类型引用(12)
1. 于卫刚,徐少坤,吴昌松,袁翔宇. 基于特征提取的ISAR成像欺骗干扰评估方法研究. 航天电子对抗. 2024(03): 16-20 . 百度学术
2. 韩立珣,田波,冯存前. 基于MIMO-ISAR的弹道目标结构参数估计方法. 系统工程与电子技术. 2020(03): 603-612 . 百度学术
3. 霍超颖,殷红成,邢笑宇,满良. 基于雷达图像特征的空间目标载荷指向估计方法. 电波科学学报. 2019(01): 45-51 . 百度学术
4. 鲁逸杰,宫志华,张群,王剑钦,李开明. 基于变分模态分解的进动目标微多普勒特征提取方法. 探测与控制学报. 2019(04): 30-35 . 百度学术
5. 任枫轩,王忠勇. 基于ISAR像序列的多旋翼无人机参数估算. 电光与控制. 2018(04): 55-60 . 百度学术
6. 王超,叶春茂,文树梁. 低重频宽带雷达中小幅微动目标的周期估计. 系统工程与电子技术. 2018(09): 1945-1952 . 百度学术
7. 徐少坤,刘记红,袁翔宇. 基于HRRP序列的中段目标二维几何特征反演方法. 电子与信息学报. 2017(10): 2366-2373 . 本站查看
8. 刘浩,杨清亮,陈佳东. 近程弹道导弹防御目标识别技术研究. 飞航导弹. 2017(06): 73-77 . 百度学术
9. 束长勇,张生俊,黄沛霖,姬金祖. 基于微多普勒估计进动锥体目标特征参数. 系统工程与电子技术. 2017(01): 15-20 . 百度学术
10. 王英,束长勇,张生俊,黄沛霖,姬金祖. 快慢时间域间歇采样转发干扰生成进动锥体ISAR群阵列. 电子与信息学报. 2016(02): 450-454 . 本站查看
11. 周叶剑,张磊,王虹现,邢孟道,牛威. 多站ISAR空间目标姿态估计方法. 电子与信息学报. 2016(12): 3182-3188 . 本站查看
12. 黄小红,文贡坚. L波段雷达电离层高速运动目标ISAR成像补偿方法. 电子与信息学报. 2015(12): 2971-2976 . 本站查看
其他类型引用(7)
-