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$和开始时间${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
-
[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. -
图(11) / 表(2)
计量
- 文章访问数: 188
- HTML全文浏览量: 103
- PDF下载量: 40
- 被引次数: 0
下载:
