一种基于多无人机的中继节点布置问题建模与优化方法

doi:10.7527/S1000-6893.2017.321195

Abstract

Abstract:

In the battlefield environment, a relay communication chain is urgently needed to be formed between two nodes which are unable to communicate. In this paper, Unmanned Aerial Vehicles (UAVs) are used as relay nodes, and a model for relay node placement is given. The objective functions are the minimum number of required relay UAVs and the minimum time cost for forming the relay chain, and the constraints are the safety of UAVs and the effectiveness of the relay chain. Since the problem is mixed integer multi-objective optimization which is known hard to be solved, and the requirement for quick and effective decision is urgently needed, a Polynomial Time Relay Placement Algorithm (PTRPA) is given to solve the problem fast and provide a sub-optimal solution. The feasibility and effectiveness of the algorithm is validated with simulation, and the impacts of different factors on the algorithm is studied with the Monte-Carlo method. The research figures out a new relay node placement scenario in the coming networked warfare, and provides a referable modeling and solving method.

Key words: Unmanned Aerial Vehicle (UAV), relay, wireless communication, node placement, polynomial time algorithm, multi-objective optimization

CLC Number:

V279
TP2

WU Gaofeng, GAO Xiaoguang, FU Xiaowei. Modeling and optimization method of relay node placement using multi-UAV[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2017, 38(11): 321195-321195.

References

[1] GOLDSMITH A. Wireless communication[M]. New York:Cambridge University Press, 2005:24-53.
[2] RANGA V, DAVE M, VERMA A K. Relay node placement to heal partitioned wire less sensor networks[J]. Computers and Electrical Engineering, 2015, 48:371-388.
[3] CALINESCU G. Relay placement for two-connectivity[J]. Discrete Optimization, 2014, 14(14):17-33.
[4] CHANDRASHEKAR K, DEKHORDI M R, BARAS J S. Providing full connectivity in large ad hoc networks by dynamic placement of aerial platforms[C]//Proceedings of IEEE Military Communication Conference.Piscataway,NJ:IEEE Press, 2004:1429-1436.
[5] LANZA-GUTIERREZ J M, GOMEZ-PULIDO J A, VEGA-RODRIGUEZ M A. A trajectory algorithm to solve the relay node placement problem in wireless sensor net-works[C]//2nd International Conference on the Theory and Practice of Natural Computing. Berlin:Springer-Verlag Berlin Heidelberg,2013:145-156.
[6] 陆克中, 刘刚, 陶耀东, 等. 无线传感器网络中继节点的最小功耗布置算法[J]. 小型微型计算机系统, 2011, 32(6):1035-1040. LU K Z, LIU G, TAO Y D, et al. Algorithm of minimum power relay node placement in wireless sensor networks[J]. Journal of Chinese Computer Systems, 2011, 32(6):1035-1040(in Chinese).
[7] YANG P, YANG L, XUE Y, et al. On the optimum placement and number selection of relay nodes in multi-hop routing for minimizing communication power con-sumption[M]//WANG R, XIAO F. Advances in Wireless Sensor Networks. Berlin:Springer, 2012:598-612.
[8] BHATTACHARYA A, RAO A, NAVEEN K P, et al. QoS constrained optimal sink and relay placement in planned wireless sensor networks[C]//International Conference on Signal Processing and Communications (SPCOM).Berlin:Springer, 2014.
[9] LANZA-GUTIERREZ J M, GOMEZ-PULIDO J A, VEGA-RODRIGUEZ M A, et al. A parallel evolutionary approach to solve the relay node palcement problem in wireless sensor networks[C]//Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation. New York:ACM, 2013:1157-1164.
[10] CHEN G, CUI S. Relay node placement in two-tiered wireless sensor networks with base stations[J]. Journal of Combinatorial Optimization, 2013, 26(3):499-508.
[11] HAN B, LI J, SU J. Optimal relay node placement for multi-pair cooperative communication in wireless networks[C]//Proceedings of IEEE Wireless Communications and Networking Conference.Piscataway,NJ:IEEE Press, 2013:4724-4729.
[12] ISLAM M, DZIONG Z, SOHRABY K, et al. Capacity-optimal relay and base station placement in wireless networks[C]//The International Conference on Information Networking.Piscataway,NJ:IEEE Press, 2012:358-363.
[13] BURDAKOV O, DOHERTY P, HOLMBERG K, et al. Optimal placement of UV-based communication relay nodes[J]. Journal of Global Optimization, 2010, 48(4):511-531.
[14] RUBIN I, ZHANG R H. Placement of UAVs as communication relays aiding mobile Ad Hoc wireless networks[C]//Proceedings of IEEE Military Communications Conference MILCOM. Piscataway, NJ:IEEE Press, 2007.
[15] 郑锴, 童利标, 陆文骏. 应用无人机实现地面无线传感器网络通信中继的探讨[J]. 现代电子技术, 2007, 23:40-50. ZHENG K, TONG L B, LU W J. Discussion on the communication relay of the wireless ground sensor network by using UAV[J]. Modern Electronics Technique, 2007, 23:40-50(in Chinese).
[16] 朱秋明, 周生奎, 霍帅珂, 等. 无人机中继平台区域覆盖统计模型[J]. 航空学报, 2014, 35(1):223-229. ZHU Q M, ZHOU S K, HUO S K, et al. A statistical area coverage model for unmanned aerial vehicles as relay platforms[J]. Acta Aeranautica et Astronautica Sinica, 2014, 35(1):223-229(in Chinese).
[17] 欧阳键, 庄毅, 薛羽. 非对称衰落信道下无人机中继传输方案及性能分析[J]. 航空学报, 2013, 34(1):130-140. OUYANG J, ZHUANG Y, XUE Y. UAV relay transmission scheme and its performance analysis over asymmetric fading channels[J]. Acta Aeranautica et Astronautica Sinica, 2013, 34(1):130-140(in Chinese).
[18] BURDAKOV O, DOHERTY P, HOMBERG K, et al. Relay positioning for unmanned aerial vehicle surveillance[J]. International Journal of Robotics Research, 2010, 29(8):1069-1087.
[19] HAN Z, SWINDLEHURST A L, LIU K J R. Optimization of MANET connectivity via smart deployment & movement of unmanned aerial vehicles[J]. IEEE Transactions on Vehicular Technology, 2009, 58(7):3533-3546.
[20] BOSKOVIC J D, PRASANTH R, MEHRA R K. A multi-player autonomous intelligent control architecture for unmanned aerial vehicles[J]. Journal of Aerospace Computing, Information, and Communication, 2014, 1(12):605-629.
[21] LAWLER E L. Combinatorial optimization:networks and matroids[M]. New York:Library of Congress Catalging in Publication Data, 1976:182-214.
[22] 雷德明, 严新平. 多目标智能优化算法及其应用[M]. 北京:科学出版社, 2009. LEI D M, YAN X P. Multi-objective intelligent optimization algorithms and its application[M]. Beijing:Science Publication, 2009(in Chinese).
[23] MANATHARA J G, SUJIT P B, BEARD R W. Multiple UAV coalition formation for a search and prosecute mission[J]. Journal of Intelligent and Robotic Systems, 2011, 62(1):125-158.
[24] GEORGE J M, SUJIT P B, SOUSA J B. Coalition formation with communication delays and maneuvering targets[C]//AIAA Guidance, Navigation, and Control Conference. Reston, VA:AIAA, 2010.
[25] DIXON C, FREW E W. Optimizing cascaded chains of unmanned aircraft acting as communication relays[J]. IEEE Journal on Selected Areas in Communication, 2012, 30(5):883-898.
[26] KOPEIKIN A, PONDA S, HOW J P. Control of communication networks for teams of UAVs[M]//VALAVA-NIS K P, VACHTSEVANOS G J. Handbook of Unmanned Aerial Vehicles. Berlin:Springer, 2015:1619-1654.
[27] YAN Y, MOSTOFI Y. Robotic router formation in realistic communication environments[J]. IEEE Transactions on Robotics, 2012, 28(4):810-827.
[28] 王桂平, 王衍, 任嘉层. 图论算法理论、实现及应用[M]. 北京:北京大学出版社, 2011:131-192. WANG G P, WANG Y, REN J C. Graph theory, implementation and application[M]. Beijing:Peking University Press, 2011:131-192(in Chinese).
[29] CORMEN T H, LEISERSON C E, RIVEST R L, et al. Introduction to algorithm[M]. 3rd ed. Cambridge:MIT Press, 2009:589-64.
[30] 姚远, 周兴社, 张凯龙, 等. 基于稀疏A*搜索和改进人工势场的无人机动态航迹规划[J]. 控制理论与应用, 2010, 27(7):953-959. YAO Y, ZHOU X S, ZHANG K L, et al. Dynamic trajectory planning for unmanned aerial vehicle based on sparse A* search and improved artificial potential field[J]. Control Theory and Applications, 2010, 27(7):953-959(in Chinese).
[31] 金畅. 蒙特卡洛方法中随机数发生器和随机抽样方法的研究[D]. 大连:大连理工大学, 2006. JIN C. Study on random number generator and random sampling in Monte Carlo method[D]. Dalian:Dalian University of Technology, 2006(in Chinese).
[32] 雷英杰, 张善文. MATLAB遗传算法工具箱及应用[M]. 2版. 西安:西安电子科技大学出版社, 2014:62-105. LEI Y J, ZHANG S W. MATLAB genetic algorithm toolbox and its application[M]. 2nd ed. Xi'an:Xidian University Press, 2014:62-105(in Chinese).

Modeling and optimization method of relay node placement using multi-UAV

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Xudong LUO, Yiquan WU, Jinlin CHEN. Research progress on deep learning methods for object detection and semantic segmentation in UAV aerial images [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(6): 28822-028822.
[2]	Gaojie ZHENG, Xiaoming HE, Dongpo LI, Huijun TAN, Kun WANG, Zhenlong WU, Depeng WANG. Double 90° deflection inlet/volute coupling flow characteristics of tail-powered unmanned aerial vehicle [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(4): 128782-128782.
[3]	Qian YANG, Haoran ZHENG, Xianda CHENG, Wei DONG. Optimization design method for hot air anti⁃icing system based on bleed air control [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(S2): 729285-729285.
[4]	Kunda LIU, Xueming LIU, Bo ZHU, Qingrui ZHANG. Robust safe control for multi⁃UAV formation flight through narrow corridors [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(S2): 729768-729768.
[5]	Wei LI, Yan GUO, Ning LI, Cuntao LIU, Hao YUAN. Intelligent reflector surface assisted UAV mobile edge computing task data maximization method [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(19): 328486-328486.
[6]	Jiezhong DONG, Wuli CHU, Haoguang ZHANG, Bo LUO, Song YAN. Flow control mechanism of diffuser cascade with wavy leading⁃edge based on causal network analysis [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(19): 128336-128336.
[7]	Chao LIANG, Li YANG, Chengsheng PAN, Yaowen QI. Multi-QoS constraints routing algorithm based on satellite network dynamic resource graph [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2023, 44(1): 326422-326422.
[8]	ZOU Ziyuan, CHEN Qifeng. Decision tree-based target assignment for confrontation of multiple space vehicles [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(S1): 726910-726910.
[9]	LI Hui, LONG Teng, SUN Jingliang, XU Guangtong. Adaptive line-of-sight method for 3D path following of UAVs [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(9): 326105-326105.
[10]	SUN Gang, PENG Shuang, CHEN Hao, WU Jiangjiang, LI Jun. Multi-objective optimization method oriented to integrated scenario of TT & C resources and data transmission resources [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(9): 326114-326114.
[11]	ZHENG Shuai, WANG Zihan, ZHAO Haoran, YANG Pengtao, HONG Jun. Layout optimization method of aircraft fuel gauging sensor based on differential evolution algorithm [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(8): 125809-125809.
[12]	ZHANG Zhouyu, CAO Yunfeng, FAN Yanming. Research progress of vision based aerospace conflict sensing technologies for small unmanned aerial vehicle in low altitude [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(8): 25645-025645.
[13]	LIU Fang, SUN Yanan. UAV target tracking algorithm based on adaptive fusion network [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(7): 325522-325522.
[14]	JING Tao, TIAN Xitian. Multi-objective optimization method for aircraft tolerance allocation based on Monte Carlo-adaptive differential evolution algorithm [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(3): 425278-425278.
[15]	ZHU Zhengyu, WANG Zixuan, XU Jinlei, WANG Zhongyong, WANG Ning, HAO Wanming. Future wireless communication assisted by intelligent reflecting surface: State of art and prospects [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(2): 25014-025014.