Design of relay link deployment algorithms for unmanned aerial vehicles

doi:10.11772/j.issn.1001-9081.2014.06.1558

Journal of Computer Applications ›› 2014, Vol. 34 ›› Issue (6): 1558-1562.DOI: 10.11772/j.issn.1001-9081.2014.06.1558

• Network and communications • Previous Articles Next Articles

Design of relay link deployment algorithms for unmanned aerial vehicles

FANG Bin¹,CHEN Tefang¹,²

1. School of Traffic and Transportation Engineering, Central South University, Changsha Hunan 410075, China;
2. School of Information Science and Engineering, Central South University, Changsha Hunan 410075, China

Received:2013-11-25 Revised:2014-01-14 Online:2014-06-01 Published:2014-07-02
Contact: FANG Bin

无人机中继链路部署算法设计

方斌¹,陈特放¹,²

1. 中南大学交通运输工程学院, 长沙 410075
2. 中南大学信息科学与工程学院, 长沙 410075

通讯作者: 方斌
作者简介:方斌(1982-),男,安徽合肥人,博士研究生,主要研究方向:多智能体协同控制、路径规划;陈特放(1957-),男,湖南涟源人,教授,博士,主要研究方向:智能交通、智能通信网络。

Abstract

Abstract:

To get a reasonable deployment and a communication relay link model of Unmanned Aerial Vehicle (UAV), and extend the data transmission distance, the Improved Bellman-Ford (IBF) algorithm and the Improved Dijkstra Algorithm (IDA) were proposed considering communication blind area and limited number of available UAVs. The UAV deployment problem was modeled as a All Hop Optimal Path (AHOP) problem, in which the IBF algorithm was used to generate a set of reachable records, and the solutions were got by accessing the records reversely; Then the IDA algorithm changed the connection weights of edges in each iteration process and found the path which decreased the hops of relay link, hence the feasible solution of UAV relay deployment problem was got. The simulation analysis illustrates that IBF and IDA can provide effective solutions of relay link deployment, and the time performance of the proposed algorithms are superior to Bellman-Ford (BF) algorithm.

摘要：

在存在通信盲区以及无人机(UAV)使用数目受限等情况下,针对如何合理地部署UAV并构建通信中继链路,以及扩展UAV的数据传输距离的问题,提出改进Bellman-Ford(IBF)算法和改进Dijkstra算法(IDA)两个UAV中继链路部署算法。将通信中继链路中UAV部署问题形式化表示为全跳最优路径(AHOP)问题, 其中IBF算法用来迭代生成一组可达记录集,通过逆向访问记录集可生成一组部署方案；IDA则在每轮迭代过程中改变连接边的权值,并查找能有效减少中继链路跳数的有效方案,得到UAV中继部署问题的可行解。仿真结果表明IBF和IDA能够提供中继链路部署的有效方案,同时它们的时间性能优于Bellman-Ford算法。

CLC Number:

TP273

FANG Bin CHEN Tefang. Design of relay link deployment algorithms for unmanned aerial vehicles[J]. Journal of Computer Applications, 2014, 34(6): 1558-1562.

方斌陈特放. 无人机中继链路部署算法设计[J]. 计算机应用, 2014, 34(6): 1558-1562.

References

[1]CERASOLI C. An analysis of unmanned airborne vehicle relay coverage in urban environments[C]// MILCOM 2007: Proceedings of the 2007 IEEE Military Communications Conference. Piscataway: IEEE Press, 2007:1-7.
[2]PINKNEY M F J, HAMPEL D, DIPIERRO S. Unmanned Aerial Vehicle (UAV) communications relay[C]// MILCOM 1996: Proceedings of the 1996 IEEE Military Communications Conference. Piscataway: IEEE Press, 1996,1:47-51.
[3]OLEG B, PATRICK D, KAJ H, et al. Optimal placement of UV-based communications relay nodes [J]. Journal of Global Optimization, 2010, 48(4): 511-531.
[4]CHEN M C, HSIAO P H, KUNG H T, et al. Maximizing throughputs of UAV-relaying networks with the load carry and deliver paradigm[C]// WCNC 2007: Proceedings of the 2007 IEEE Wireless Communications and Networking Conference. Piscataway: IEEE Press,2007:4417-4424.
[5]CHEN Y, DONG L, OH J-S. Real-time video relay for UAV traffic surveillance systems through available communication networks[C]// WCNC 2007: Proceedings of the 2007 IEEE Wireless Communications and Networking Conference. Piscataway: IEEE Press,2007:2608-2612.
[6]OMER C, IBRAHIM Z. Continuous airborne communication relay approach using unmanned aerial vehicles [J]. Journal of Intelligent & Robotic Systems, 2012,65(1): 549-562.
[7]IBRAHIM Z, OMER C. Obstacle free airborne communication relay approach by using autonomous unmanned aerial vehicles[EB/OL].[2013-10-10]. http://www.researchgate.net/profile/Omer_Cetin/publication/234025058_Establishing_Obstacle_and_Collision_Free_Communication_Relay_for_UAVs_with_Artificial_Potential_Fields/file/9fcfd511538f1092bb.pdf.
[8]JOEL M E, THOMAS W D. Maintaining wireless connectivity constraints for swarms in the presence of obstacles[C]// ICRA 2006: Proceedings of the 2006 IEEE International Conference on Robotics and Automation. Piscataway: IEEE Press,2006:946-951.
[9]GEIR D, LUIS G. On the directed hop-constrained shortest path problem[J]. Operations Research Letters, 2004, 32(1):15-22.
[10]ROCH G, ARIEL O. Computing shortest paths for any number of hops [J]. IEEE Transactions on Networking, 2002, 10(5): 613-620.
[11]ANANTARAM B, KEMAL A. Using a hop-constrained model to generate alternative communication network design [J]. Journal of Computing, 1992,4(2):192-205.
[12]THOMAS C, CHARLES L, RONALD R. Introduction to algo-rithms[M]. Cambridge: MIT Press, 1990.
[13]EUGENE L, LAWLER. Combinatorial optimization: networks and matroids[M].[S.l.]:Dover Publications, 1976.

[1]	YANG Zhen, MA Jianxiao, WANG Baojie. Signal timing optimization model of dual-ring phase under condition of setting waiting area [J]. Journal of Computer Applications, 2021, 41(7): 2108-2112.
[2]	MA Ziyu, HE Ming, LIU Zujun, GU Lingfeng, LIU Jintao. Survey of unmanned aerial vehicle cooperative control [J]. Journal of Computer Applications, 2021, 41(5): 1477-1483.
[3]	JIAO Hailin, GUO Yuying, ZHU Zhengwei. Acceleration compensation based anti-swaying flight control for unmanned aerial vehicle with slung-load [J]. Journal of Computer Applications, 2021, 41(2): 604-610.
[4]	GAO Shile, WANG Ying, LI Hailin, WAN Xiaoji. Prediction method on financial time series data based on matrix profile [J]. Journal of Computer Applications, 2021, 41(1): 199-207.
[5]	FENG Zikai, CHEN Lijia, LIU Mingguo, YUAN Meng’en. Nonlinear systems identification based on structural adaptive filtering method [J]. Journal of Computer Applications, 2020, 40(8): 2319-2326.
[6]	. Development of EtherCAT control system based on SylixOS operating system [J]. Journal of Computer Applications, 0, (): 0-0.
[7]	PEI Pei, LI Caiwei, LYU Bote. Improved migration operator biogeography-based optimization algorithm and its application in PID parameter tuning [J]. Journal of Computer Applications, 2020, 40(3): 728-734.
[8]	LIN Zheng, LYU Xiafu. Autonomous obstacle avoidance of unmanned surface vessel based on improved fuzzy algorithm [J]. Journal of Computer Applications, 2019, 39(9): 2523-2528.
[9]	TAN Xitang, LIU Sha, ZHU Qinyue, FAN Qingwen, WANG Chen. Matrix LED high-beam intelligent assistant control system [J]. Journal of Computer Applications, 2019, 39(6): 1855-1862.
[10]	YU Jiaxing, WEI Haiping, JIN Lina, WEI Yufeng. Average consensus of heterogeneous multi-agent based on model reference [J]. Journal of Computer Applications, 2019, 39(4): 1240-1246.
[11]	JIN Tao, DONG Xiucheng, LI Yining, REN Lei, FAN Peipei. Optimization of fractional PID controller parameters based on improved PSO algorithm [J]. Journal of Computer Applications, 2019, 39(3): 796-801.
[12]	YANG Jidong, SUN Zhaoqi, WANG Feilong. Optimal path control of parallel truss manipulator based on visual grasping [J]. Journal of Computer Applications, 2019, 39(3): 913-917.
[13]	GAO Junqiang, TANG Xiaqing, ZHANG Huan, GUO Libin. Processing method of INS/GPS information delay based on factor graph algorithm [J]. Journal of Computer Applications, 2018, 38(11): 3342-3347.
[14]	. Optimization of fractional PID controller parameters based on improved PSO algorithm [J]. Journal of Computer Applications, 0, (): 0-0.
[15]	ZOU Sifan, WU Guoqing, MAO Jingfeng, ZHU Weinan, WANG Yurong, WANG Jian. Adaptive backstepping sliding mode control for robotic manipulator with the improved nonlinear disturbance observer [J]. Journal of Computer Applications, 2018, 38(10): 2827-2832.

Design of relay link deployment algorithms for unmanned aerial vehicles

无人机中继链路部署算法设计

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics