一种基于维诺划分和虚拟力的多无人机部署优化算法

      A multi-UAV deployment optimization algorithm based on Voronoi partitioning and virtual force

      • 摘要: 为解决当前多无人机部署优化算法在覆盖效率上的不足,提出了一种基于维诺划分与虚拟力(Voronoi partitioning and virtual force, VVF)的无人机部署优化算法。首先,在初始随机部署的基础上,通过维诺划分将目标区域划分为多个子区域,并在每个子区域上构建局部覆盖模型;接着,在每个局部覆盖模型中采用虚拟力迭代更新无人机位置,并通过改进虚拟力作用机制加速消除覆盖空洞;最后,评估当前部署结果并剔除冗余无人机对算法迭代优化,直至获得最优的无人机部署位置和数量。与边虚拟力(edge virtual forces, EVF)算法、点EVF (vertex-EVF, VEVF)算法以及基于粒子群优化(particle swarm optimization, PSO)与维诺图(PSO and Voronoi diagram, PSOVD)的算法相比,VVF的覆盖效率最高提升了9.32%,与PSO算法和人工蜂群(artificial bee colony, ABC)算法相比,VVF的执行效率最高提升了31.26%。

         

        Abstract: To address the limitations of current multi-UAV deployment optimization algorithms in terms of coverage efficiency, this paper proposes a UAV deployment optimization algorithm based on Voronoi partitioning (VP) and virtual force (VVF). Specifically, the algorithm first divides the target area into multiple sub-regions using Voronoi partitioning based on an initial random deployment, and constructs a local coverage model for each sub-region. Then, in each local coverage model, the algorithm uses an improved virtual force mechanism to adjust the UAV positions and efficiently eliminate coverage holes. Finally, the current deployment result is evaluated, and redundant UAVs are removed. Compared with the edge virtual force (EVF) algorithm, the vertex-edge virtual force (VEVF) algorithm, and the particle swarm optimization and Voronoi diagram (PSOVD) algorithm, the proposed VVF achieves a maximum improvement of 9.32% in coverage efficiency. In addition, compared with the particle swarm optimization (PSO) algorithm and the artificial bee colony (ABC) algorithm, VVF improves execution efficiency by up to 31.26%.

         

      /

      返回文章
      返回