ANALYTICAL COMPARISON OF SQUARE CIRCLE PACKING AND TRIANGULAR CIRCLE PACKING BASED ALGORITHMS FOR MAXIMUM COVERAGE AREA DENSITY OF MULTIPLE DEPLOYED UAV-ABS
Abstract
Circle packing theory (CPT) proffers square circle packing (SCP) and triangular circle packing (TCP) as two basic tools for closed-form packing or placement optimizations of 2D circular geometrical objects. Placement optimization of multiple deployed unmanned aerial vehicles with mounted aerial base stations (UAV-ABS) had been classified as a circle placement problem that CPT as a tool could resolve. However, the optimization constraints utilized by most researchers are more favourable to SCP than TCP. Furthermore, the non-linear constraints need to be simplified to linear forms. A proper analysis of the basic geometry of both SCP and TCP was used to derive linear mathematical models for both. The mathematical models were used to develop SCP-based and TCP-based algorithms for the placement of multiple deployed UAV-ABS in target rectangular border regions and a given optimal wireless network (WN) coverage radius. The algorithms equate the 2D position of the UAV-ABS on the horizontal plane as the centroid of the circle for the respective circular WN coverage regions. Both algorithms were implemented using MATLAB® 2023a and simulated using a rectangular border region of 3 km by 3 km and coverage radii ranging from 50 m to 1000 m at an interval of 10 m. Coverage area density (CAD) was used as the performance metric. The TCP-based algorithm was observed to perform better with an average of 13.97% higher CAD. Its minimum obtainable CAD was 44.57% but SCP-based alogorithm recorded 19.90%.
Keywords
Comparison, Square Circle Packing, Triangular Circle Packing Algorithms, Coverage Area Density, Multiple Deployed UAV-ABS