Electronics and Electrical Engineering and Control

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

  • WU Gaofeng ,
  • GAO Xiaoguang ,
  • FU Xiaowei
Expand
  • School of Electronics and Information, Northwestern Polytechnical University, Xi'an 710072, China

Received date: 2017-02-27

  Revised date: 2017-07-31

  Online published: 2017-07-31

Supported by

National Natural Science Foundation of China (61573285)

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.

Cite this article

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 . DOI: 10.7527/S1000-6893.2017.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).

Outlines

/