A fast improved quasi-physical dynamic algorithm for efficient wireless coverage in convex polygonal regions
2026-08-24 • Computational Geometry
Computational Geometry
AI summaryⓘ
The authors focus on placing wireless nodes to cover an area efficiently, which is a tricky math problem especially for irregular shapes. They created a new method called IQPD that starts with a smart pattern, uses virtual forces with friction to avoid too much overlap, and keeps nodes inside the area boundaries. Their approach works better than others for various convex shapes, achieving higher coverage and better use of nodes. This improves how wireless coverage can be planned in real-world settings.
wireless node deploymentcoverage optimizationconvex polygonshexagonal close packingvirtual force algorithmNP-hard problemsboundary constraintsmetaheuristic algorithmscoverage overlapscaling and affine transformation
Authors
Zeping Yi, Yongjun Wanga, Baoshan Wang, Jian Zhang, Songyi Liu
Abstract
Deploying wireless nodes to maximize coverage area within a given region is an important challenge in wireless sensor networks, UAV path planning, base station placement and other industrial fields. This practical problem can be mathematically equivalent to an optimal circle covering problem. Although theoretical optimal configurations exist for simple cases in mathematics, the NP-hard nature of this problem makes it computationally prohibitive for complex polygons with numerous nodes. Existing approaches are usually designed for regular domains, while those applicable to irregular polygons often suffer from poor initialization, excessive coverage overlap and failure to constrain nodes within the boundary, leading to low coverage efficiency and long runtime. To address these issues, we propose an improved quasi-physical dynamic algorithm (IQPD) for wireless node deployment in arbitrary convex polygons. Our contributions are threefold: (1) proposing a structure-preserving initialization that maps a hexagonal close packing pattern into the target polygon via scaling and affine transformation, ensuring near-optimal initial node distribution; (2) constructing a refined virtual force model by incorporating friction and a radius-expansion optimization mechanism to reduce coverage area overlap; (3) developing a boundary encircling strategy leveraging normal and tangential gradients to reposition nodes deployed outside boundaries after initial optimization. Extensive experimental results demonstrate that our method consistently outperforms other new metaheuristic algorithms across diverse convex polygon shapes, including randomly generated data and real-world scenarios. Our method achieves the highest coverage rate and node utilization rate among all compared algorithms, greatly improving wireless coverage efficiency.