收稿日期: 2017-02-27
修回日期: 2017-07-31
网络出版日期: 2017-07-31
基金资助
国家自然科学基金（61573285）
Modeling and optimization method of relay node placement using multi-UAV
Received date: 2017-02-27
Revised date: 2017-07-31
Online published: 2017-07-31
Supported by
National Natural Science Foundation of China (61573285)
针对战场环境下急需在无法通信的节点间构建有效通信链路的情形，使用多无人机作为中继节点，建立了中继节点布置（RNP）问题模型。模型以中继链路有效和无人机安全为约束，以中继布置点位置及相应的无人机为输出，不但考虑了使用的中继无人机数量，还考虑了构建中继链路花费的时间。考虑到该问题是难以求解的混合整数多目标优化问题，同时在紧急应用情形下，要求求解算法快速有效，建立了一种多项式时间中继节点布置算法（PTRPA）。仿真实验验证了所提模型确实能够在更短的时间内完成有效中继链路构建；通过Monte-Carlo方法对比和分析不同因素对PTRPA算法、随机抽样算法、遗传算法求解该问题的结果性能和时间性能的影响，验证了PTRPA算法不但能够给出接近最优的解，且快速有效，满足战场决策需求。
吴高峰 , 高晓光 , 符小卫 . 一种基于多无人机的中继节点布置问题建模与优化方法[J]. 航空学报, 2017 , 38(11) : 321195 -321195 . DOI: 10.7527/S1000-6893.2017.321195
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.
[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).
/
| 〈 |
|
〉 |
CJA