航空学报 > 2017, Vol. 38 Issue (11): 321195-321195   doi: 10.7527/S1000-6893.2017.321195

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

吴高峰, 高晓光, 符小卫   

  1. 西北工业大学 电子信息学院, 西安 710072
  • 收稿日期:2017-02-27 修回日期:2017-07-31 出版日期:2017-11-15 发布日期:2017-07-31
  • 通讯作者: 高晓光 E-mail:cxg2012@nwpu.edu.cn
  • 基金资助:

    国家自然科学基金(61573285)

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

WU Gaofeng, GAO Xiaoguang, FU Xiaowei   

  1. School of Electronics and Information, Northwestern Polytechnical University, Xi'an 710072, China
  • Received:2017-02-27 Revised:2017-07-31 Online:2017-11-15 Published:2017-07-31
  • Supported by:

    National Natural Science Foundation of China (61573285)

摘要:

针对战场环境下急需在无法通信的节点间构建有效通信链路的情形,使用多无人机作为中继节点,建立了中继节点布置(RNP)问题模型。模型以中继链路有效和无人机安全为约束,以中继布置点位置及相应的无人机为输出,不但考虑了使用的中继无人机数量,还考虑了构建中继链路花费的时间。考虑到该问题是难以求解的混合整数多目标优化问题,同时在紧急应用情形下,要求求解算法快速有效,建立了一种多项式时间中继节点布置算法(PTRPA)。仿真实验验证了所提模型确实能够在更短的时间内完成有效中继链路构建;通过Monte-Carlo方法对比和分析不同因素对PTRPA算法、随机抽样算法、遗传算法求解该问题的结果性能和时间性能的影响,验证了PTRPA算法不但能够给出接近最优的解,且快速有效,满足战场决策需求。

关键词: 无人机, 中继, 无线通信, 节点布置, 多项式时间算法, 多目标优化

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

中图分类号: