# Optimizing Charging Pad Deployment by Applying a Quad-Tree Scheme
## 4 Simulation Results
### Performance Comparison  
In our simulation, we utilized three types of maps: small-scale (4096 \(\times\) 4096), medium-sized (6144 \(\times\) 6144), and large-scale (8192 \(\times\) 8192). Across these three map scales, we computed the required number of charging pads and the algorithm computation time for six methods: MSC, GNC, TNC, CDC&DSC, our proposed Quad-Tree algorithm (QT&MSC), and QT&MSC&DSC. MSC, GNC, and TNC were proposed by [PERSON] et al. [6]. CDC&DSC was proposed by [PERSON] et al. [13]. Additionally, [6; 13] were the only current papers we found that propose a pad allocation algorithm, and the pad configuration obtained using CDC&DSC is quite streamlined. By combining its proposed algorithm for removing duplicate pads (DSC), we propose a version of QT&MSC&DSC and include it in the comparison. Figures 6-8 depict the performance of different methods on maps of different sizes. Firstly, in the small map (Figure 6), MSC, GNC, and TNC failed to find an appropriate pad configuration for some maps with only 50 scattered sensors. Conversely, the proposed methods and CDC&DSC encountered no problems with these maps. Without using DSC, the number of pads used by QT&MSC could be reduced by up to 2.92% compared to MSC, with an average reduction of only 0.48%. CDC&MSC exhibited a maximum reduction of 7.73% and an average reduction of 5.11%. When combined with DSC, QT&MSC&DSC achieved reductions of up to 8.02% and an average of 5.05%. Therefore, in terms of reducing the number of pads used, CDC&DSC and QT&MSC&DSC performed similarly, indicating that appropriate removal of redundant \begin{table}
\begin{tabular}{c c} \hline \hline
**Parameters** & **Values** \\ \hline \(E_{sensor}\) & 200 J \\ \(E_{max}\) & 1000 J \\ \(P_{fly}\) & 10 J/s \\ \(V_{fly}\) & 35 m/s \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Parameters and values. Figure 8: Comparisons of (**a**) the required number of pads and (**b**) the average execution time of related methods on large-scale maps. Figure 6: Comparisons of (**a**) the required number of pads and (**b**) the average execution time of related methods on small-scale maps. Figure 7: Comparisons of (**a**) the required number of pads and (**b**) the average execution time of related methods on medium-scale maps. However, Figure 6b illustrates the high computational complexity associated with DSC. CDC requires appropriate determination of the number of clusters. In our simulation environment, CDC generated a significant number of clusters, leading to prolonged processing time for DSC. Compared to MSC, the average computation time increased by 2588.89%. The issue with QT&MSC is relatively minor. Compared to MSC, QT&MSC experienced an average increase in computation time of 164.44%, while QT&MSC&DSC, which incorporates DSC, experienced an average increase of 201.43%. As the network size expands to 6144 \(\times\) 6144, the gap between the proposed methods and MSC widens slightly. During the simulations, it was observed that MSC, TNC, and GNC algorithms fail when nodes are distributed far apart, as they struggle to find suitable sensor locations meeting the adjacency conditions from the base station. For 50 sensors, MSC, GNC, and TNC encountered problems in finding appropriate pad configurations in some maps. Additionally, MSC and TNC also faced issues when there were 100 sensors. However, because GNC utilizes flight range to choose the next optimal position, resulting in larger coverage compared to using the two-hop method as in MSC and TNC, GNC did not encounter similar problems with 100 sensors. There were no issues with the proposed methods and CDC&DSC, as these algorithms consider that when the relevant adjacent position cannot be found, pads are filled in at the appropriate positions and connected to the nearest candidate pad position. Excluding the cases of 50 or 100 sensors, without using DSC, the number of pads used by QT&MSC could be reduced by up to 7.67% compared to MSC, with an average reduction of 3.74%.