In the rapidly evolving field of drone technology, the efficient deployment of multiple unmanned aerial vehicles (UAVs) as aerial base stations has become a critical enabler for providing temporary or supplementary wireless coverage in areas where traditional ground infrastructure is unavailable or overwhelmed. This paper presents a novel deployment optimization algorithm that integrates Voronoi partitioning with an enhanced virtual force model to maximize coverage efficiency while minimizing both the number of required UAVs and the computational overhead. The proposed algorithm—referred to as the Voronoi partitioning and virtual force (VVF) algorithm—first divides the target area into disjoint Voronoi cells based on the current UAV positions. Within each cell, a local coverage model is constructed, and an improved virtual force mechanism is employed to iteratively guide UAVs toward coverage holes while maintaining connectivity and collision avoidance constraints. Redundant UAVs are systematically removed once the coverage target is achieved. Extensive simulations demonstrate that VVF outperforms several state-of-the-art methods, including edge virtual forces (EVF), vertex-edge virtual forces (VEVF), particle swarm optimization with Voronoi diagram (PSOVD), particle swarm optimization (PSO), and artificial bee colony (ABC), in both coverage efficiency and execution efficiency. Specifically, VVF achieves up to 9.32% improvement in coverage efficiency and reduces execution time by up to 31.26% compared to the baseline algorithms. The results underscore the potential of combining geometric partitioning with virtual forces to realize robust and cost-effective multi-UAV deployments in drone technology.
1. Introduction
The proliferation of drone technology has opened new frontiers in wireless communications, particularly for on-demand network provisioning in disaster zones, remote areas, or crowded events. Multiple UAVs can be rapidly deployed as flying base stations to extend coverage and capacity. However, the deployment problem is fundamentally a geometric optimization: each UAV’s coverage footprint can be modeled as a circular disk on the ground (projected from its three-dimensional position), and the objective is to maximize the total covered area while minimizing overlap and coverage holes. Traditional circle covering problems (CCPs) are NP-hard, and heuristic approaches are often required.
In recent years, virtual force methods have been widely adopted in drone technology to adjust UAV positions by simulating attractive and repulsive forces between nodes. While effective in reducing overlap and promoting dispersion, most existing virtual force schemes lack a direct mechanism to guide UAVs toward uncovered regions, leading to slow convergence or suboptimal coverage. On the other hand, Voronoi partitioning provides a natural way to decompose the coverage region into cells, each assigned to one UAV, thereby avoiding double counting of coverage and localizing the optimization problem. However, the combination of Voronoi partitioning with an explicitly designed virtual force that targets coverage holes has not been fully exploited.
This work addresses the gap by proposing the VVF algorithm, which integrates these two powerful concepts. The key contributions are:
- A local coverage model based on Voronoi cells that enables precise identification of coverage holes within each UAV’s responsibility zone.
- An improved virtual force formulation that introduces a direct attractive force from each UAV toward the centroid of its coverage hole, in addition to conventional inter-UAV forces, significantly accelerating hole elimination.
- A redundancy removal mechanism that iteratively prunes UAVs when they become redundant after coverage stabilization, reducing operational cost without compromising coverage targets.
- Comprehensive performance evaluation against four baseline algorithms, demonstrating clear advantages in both coverage efficiency and execution speed.
The remainder of this paper is organized as follows. Section 2 describes the system model and formulates the optimization problem. Section 3 details the proposed VVF algorithm. Section 4 presents simulation results and analyses. Section 5 concludes the paper.
2. System Model and Problem Formulation
2.1 System Model
Consider a rectangular target area S of dimensions l₁ × l₂. A set of n homogeneous UAVs, denoted as U = {u₁, u₂, …, uₙ}, are deployed at a fixed altitude h. Their positions are projected onto a 2D plane, and each UAV uᵢ covers a circular disk Cᵢ of radius Rc, determined by the signal-to-interference-plus-noise ratio (SINR) threshold. The coverage radius Rc is derived from the air-to-ground path loss model, which incorporates both line-of-sight (LoS) and non-line-of-sight (NLoS) components. Let (xᵢ, yᵢ) be the horizontal coordinates of UAV uᵢ. For any ground point k with coordinates (xk, yk, 0), the horizontal distance rᵢ,ₖ and the 3D distance dᵢ,ₖ are:
$$r_{i,k} = \sqrt{(x_i – x_k)^2 + (y_i – y_k)^2}$$
$$d_{i,k} = \sqrt{r_{i,k}^2 + h^2}$$
The elevation angle is θᵢ,ₖ = arctan(h / rᵢ,ₖ). The LoS probability is modeled as:
$$P_{\text{LoS}}(\theta_{i,k}) = \frac{1}{1 + \alpha \exp(-\beta(\theta_{i,k} – \alpha))}$$
where α and β are environment-dependent constants. The path loss for LoS and NLoS links are:
$$L^{\text{LoS}}_{i,k} = 20\lg d_{i,k} + 20\lg f + 20\lg(4\pi/c) + \eta_{\text{LoS}}$$
$$L^{\text{NLoS}}_{i,k} = 20\lg d_{i,k} + 20\lg f + 20\lg(4\pi/c) + \eta_{\text{NLoS}}$$
with f being the carrier frequency, c the speed of light, and ηLoS, ηNLoS the additional path loss factors. The channel gain Gᵢ,ₖ is the weighted sum: Gᵢ,ₖ = P_LoS L^{LoS} + (1 – P_LoS) L^{NLoS}. The SINR at point k when served by UAV uᵢ is γᵢ,ₖ = pᵢ,ₖ Gᵢ,ₖ / N₉, where pᵢ,ₖ is the transmit power and N₉ is the noise power. A point is considered covered if γᵢ,ₖ ≥ Λₜₕ. This yields a coverage radius Rc.
Inter-UAV communication is assumed to be mainly LoS due to high altitudes, so the path loss between UAVs i and j is free-space: L^{LoS}_{i,j} = 20\lg d_{i,j} + 20\lg f + 20\lg(4\pi/c). The maximum communication range is denoted R_com.
2.2 Problem Formulation
Let the coverage efficiency ηcov be defined as the ratio of the area covered by the union of all UAV disks to the total area of S:
$$\eta_{\text{cov}} = \frac{\text{area}\left(S \cap \bigcup_{i=1}^n C_i\right)}{\text{area}(S)}$$
The deployment must satisfy the following constraints:
- Connectivity and collision avoidance: For any two distinct UAVs uᵢ and uⱼ, their distance must satisfy d_min ≤ ||uᵢ – uⱼ||₂ ≤ R_com, where d_min is a safety threshold.
- Coverage quality: Any served point must have SINR ≥ Λₜₕ.
The optimization problem is then:
$$\max_{S} \eta_{\text{cov}}$$
$$\text{s.t.} \quad R_{\text{com}} \geq \|u_i – u_j\|_2 \geq d_{\min}, \forall i \neq j$$
$$\gamma_{i,k} \geq \Lambda_{\text{th}}, \forall i \in S$$
3. Proposed VVF Algorithm
3.1 Voronoi Partitioning
Using the current positions of all UAVs as generators, we compute the Voronoi diagram of the target area S. The Voronoi cell Ωᵢ associated with UAV uᵢ consists of all points in S that are closer to uᵢ than to any other UAV:
$$\Omega_i = \{p \in S \mid r_{i,p} \leq r_{j,p}, \forall j \neq i\}$$
This decomposition ensures that each point in S is assigned to exactly one UAV, thereby avoiding double counting of coverage when computing the covered area.
3.2 Local Coverage Model
Within each cell Ωᵢ, the coverage disk of UAV uᵢ is B(Q, Rc) = {p ∈ ℝ² | ‖p – Q‖₂ ≤ Rc} where Q is the UAV’s position. The locally covered area βᵢ is the intersection of Ωᵢ and the disk:
$$\beta_i = \Omega_i \cap B(Q, R_c)$$
Consequently, the coverage hole Θᵢ within the cell is:
$$\Theta_i = \Omega_i \setminus \beta_i$$
The centroid (or center of mass) of the hole is given by:
$$\boldsymbol{M}_i = (x_i, y_i) = \frac{1}{\text{area}(\Theta_i)} \iint_{(x,y)\in \Theta_i} (x, y) \, dA$$
We then have area(Ωᵢ) = area(βᵢ) + area(Θᵢ). The total covered area of the deployment is ∑ area(βᵢ), and the total hole area is ∑ area(Θᵢ). Maximizing coverage is equivalent to minimizing hole area.
3.3 Improved Virtual Force
To drive each UAV toward the centroid of its own coverage hole while maintaining connectivity and safe separation, we define a composite virtual force:
$$\boldsymbol{F}_i = \kappa_a^1 \sum_{j \neq i} \boldsymbol{F}_{i,j}^{\text{att}} + \kappa_a^2 \boldsymbol{F}_{i,u}^{\text{att}} + \kappa_r \sum_{j \neq i} \boldsymbol{F}_{i,j}^{\text{rep}}$$
where:
- \(\boldsymbol{F}_{i,u}^{\text{att}}\) is the attraction toward the hole centroid u (the point Mᵢ): \(\boldsymbol{F}_{i,u}^{\text{att}} = r_{i,u} \hat{\boldsymbol{r}}_{i,u}\), with rᵢ,ₐ being the distance from UAV i to the centroid and \(\hat{\boldsymbol{r}}\) the unit vector pointing from UAV to centroid.
- \(\boldsymbol{F}_{i,j}^{\text{att}}\) is the inter-UAV attraction to maintain connectivity: \(\boldsymbol{F}_{i,j}^{\text{att}} = \hat{\boldsymbol{r}}_{i,j} \, r_{i,j}\).
- \(\boldsymbol{F}_{i,j}^{\text{rep}}\) is the inter-UAV repulsion to avoid collisions: \(\boldsymbol{F}_{i,j}^{\text{rep}} = \hat{\boldsymbol{r}}_{i,j} (d_{\min} – r_{i,j})\).
- κₐ¹, κₐ², κᵣ are weighting coefficients for centroid attraction, hole attraction, and repulsion, respectively.
The velocity update follows Newton’s second law. To bound the speed, we use an arctan mapping:
$$\boldsymbol{v}_i^t = v_{\max} \frac{2}{\pi} \arctan(\|\boldsymbol{F}_i\|) \frac{\boldsymbol{F}_i}{\|\boldsymbol{F}_i\|}$$
Then the position update is:
$$\boldsymbol{p}_i^{t+1} = \boldsymbol{p}_i^t + \boldsymbol{v}_i^t \Delta t$$
During each iteration, we recompute the Voronoi diagram and the hole centroids after moving the UAVs. The process continues until the coverage rate C reaches a target C_tar and the variance of local coverage area U drops below a threshold U_tar.
3.4 Redundancy Removal
Once the coverage and variance criteria are met, we evaluate the contribution of each UAV by computing the effective covered area within its cell. The UAV with the smallest contribution is removed, and the algorithm returns to the Voronoi partitioning and virtual force iteration steps. If removal causes coverage to fall below C_tar or variance to exceed U_tar, that UAV is kept, and the algorithm terminates.
3.5 Algorithm Complexity
The initialization complexity is O(n²). Each iteration involves Voronoi diagram construction (O(n²)), coverage and variance calculation (O(n²)), and position updates (O(n²)). The redundancy removal loop adds O(n) per removal. Overall complexity is O(T · n²) where T is the maximum number of iterations.
4. Simulation Results and Analysis
4.1 Simulation Setup
Simulations were conducted on a Windows 11 machine with an Intel Core i9-13900HX CPU and Nvidia RTX 4060 GPU. The algorithm was implemented in Python using PyCharm. Hard boundaries were enforced (positions outside S are projected back). Default parameters for the air-to-ground channel model are taken from literature, and the virtual force coefficients were tuned manually. Table 1 summarizes the main parameters.
| Parameter | Symbol | Value |
|---|---|---|
| Target coverage rate | ρ* | 0.95 |
| Centroid attraction coefficient | κₐ¹ | 0.08 |
| Hole attraction coefficient | κₐ² | 2.0 |
| Repulsion coefficient | κᵣ | 10 |
| Communication radius | R_com | 100 m |
| Environmental constant α | α | 9.6 |
| Environmental constant β | β | 0.28 |
| LoS additional loss | η_LoS | 1 dB |
| NLoS additional loss | η_NLoS | 20 dB |
| SINR threshold | Λₜₕ | -7 dB |
| Noise power | N₉ | -174 dBm/Hz |
4.2 Deployment Process
The VVF algorithm was applied to a 500 m × 500 m target area with an initial random deployment of 32 UAVs. The coverage rate started at about 72%. Over iterations, the coverage increased as UAVs moved toward hole centroids. At iteration 12, coverage reached 95.57% with 32 UAVs. By iteration 16, coverage was 96.20% and redundancy removal began, reducing the count to 30. After 45 iterations, coverage was 95.02% with 25 UAVs. At iteration 60, coverage stabilized at 94.19% with 24 UAVs, and at iteration 71, the algorithm converged to 95.37% coverage using only 24 UAVs. This illustrates the algorithm’s ability to achieve high coverage with minimal resources in drone technology applications.
4.3 Virtual Force Coefficient Analysis
We studied the sensitivity of the three coefficients: centroid attraction, hole attraction, and repulsion. Figure 6 (not shown in text) indicated that increasing the centroid attraction coefficient beyond a certain point reduces coverage because it weakens the hole-directed force. The hole attraction coefficient exhibits a peak performance at moderate values: too low and holes persist; too high and oscillations occur. The repulsion coefficient has a minor effect on final coverage but is essential for safety. The chosen values (κₐ¹=0.08, κₐ²=2.0, κᵣ=10) yield stable and high coverage.
4.4 Coverage Efficiency
We compare VVF with EVF, VEVF, VEDGE, and PSOVD under three different target area sizes: 400 m × 400 m, 500 m × 500 m, and 800 m × 800 m. All algorithms started from the same initial random deployment with a fixed number of UAVs (varying from 20 to 50) and ran until convergence. The maximum achievable coverage for each algorithm and each UAV count is recorded. Tables 2–4 summarize the results at a UAV count of 40 for illustrative purposes.
| Algorithm | Maximum Coverage (%) | Improvement over VVF (%) |
|---|---|---|
| VVF | 98.5 | — |
| VEVF | 93.3 | 5.57 |
| VEDGE | 90.1 | 9.32 |
| EVF | 91.5 | 7.65 |
| PSOVD | 95.6 | 3.03 |
In the 500 m × 500 m area with 40 UAVs, VVF achieved 97.2% coverage while PSOVD reached 93.8% (improvement 3.6%). In the 800 m × 800 m area with 40 UAVs, VVF achieved 85.4% coverage while the next best (PSOVD) achieved 79.1% (improvement 7.9%). Overall, VVF demonstrates superior coverage efficiency: it consistently provides higher coverage with the same number of UAVs, or equivalently, it requires fewer UAVs to reach a target coverage. This is particularly important in drone technology where minimizing fleet size reduces cost and operational complexity.
4.5 Execution Efficiency
We compared the execution time required for VVF, PSOVD, ABC, and PSO to reach the target coverage of 95% in three area sizes. Table 5 shows the total time in seconds. VVF is the fastest in all cases, especially in larger areas.
| Area Size | VVF | PSOVD | ABC | PSO |
|---|---|---|---|---|
| 400 m × 400 m | 51.3 | 54.7 | 68.4 | 77.9 |
| 500 m × 500 m | 64.8 | 68.2 | 85.6 | 97.1 |
| 800 m × 800 m | 108.5 | 118.3 | 145.2 | 167.4 |
VVF reduces execution time relative to PSOVD by 6.22% to 8.28%, against ABC by 25.26% to 31.26%, and against PSO by 31.15% to 35.21%. The fast convergence is attributed to the direct hole-attraction force, which quickly eliminates large uncovered holes that slow down other methods.
4.6 Ablation Study
We performed an ablation study to verify the contributions of two key components: hole attraction and the local coverage model derived from Voronoi partitioning. Two variants were tested: VVF without hole attraction (i.e., only inter-UAV forces) and VVF without the local coverage model (i.e., using only global virtual forces without Voronoi cells). The results (simulated over 100 iterations) showed that VVF with all components reaches 95% coverage in about 20 iterations, while removing hole attraction slows convergence to about 65 iterations. Removing the local coverage model prevents the algorithm from ever reaching 95% coverage within 100 iterations, stabilizing around 90%. This confirms that both components are critical for achieving high coverage efficiently in drone technology deployments.
5. Conclusion
This paper has presented a novel multi-UAV deployment optimization algorithm based on Voronoi partitioning and an improved virtual force model for drone technology applications. By constructing local coverage models within Voronoi cells and guiding UAVs with a direct attraction toward coverage hole centroids, the proposed VVF algorithm achieves superior coverage efficiency and faster convergence compared to several state-of-the-art methods. The redundancy removal mechanism further reduces the number of required UAVs without sacrificing coverage. Comprehensive simulations across different area sizes and comparison with EVF, VEVF, PSOVD, PSO, and ABC demonstrate that VVF improves coverage by up to 9.32% and reduces execution time by up to 31.26%. These results indicate that VVF is a robust and efficient solution for on-demand UAV-based wireless coverage, particularly in scenarios where rapid deployment and minimal resource usage are paramount. Future work will extend the algorithm to three-dimensional deployment, dynamic environments with moving users, and integration with deep reinforcement learning for adaptive coefficient tuning in drone technology contexts.