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 (SqCP) and triangular circle packing (TriCP) 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 SqCP than TriCP. Furthermore, the non-linear constraints need to be simplified to linear forms. A proper analysis of the basic geometry of both SqCP and TriCP was used to derive linear mathematical models for both. The mathematical models were used to develop SqCP-based and TriCP-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 TriCP-based algorithm was observed to perform better with an average of 13.97% higher CAD. Its minimum obtainable CAD was 44.57% but SqCP-based alogorithm recorded 19.90%. The outcome of the research indicated that the TriCP is more appropriate for optimal deployment or placement of UAV-ABS and any other circular objects on a 2D plane when coverage area density is the utmost optimization objective.