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

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

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

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 simu-lation ,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 meth-od.