# NFV/SDN as an Enabler for Dynamic Placement Method of mmWave Embedded UAV Access Base Stations
## 4 Proposed Method
### K-Means Algorithm + Smallest-Circle Problem  
As mentioned above, we use the millimeter-wave band for the access link in this study. Since the millimeter-wave band has a higher frequency than the microwave band used so far, the propagation loss is larger, as shown in Equation (5). To improve the data rate provided to the user, it is necessary to reduce the propagation loss, with Equation (5) showing that it is necessary to shorten the distance between the user and the UAV.  
As a previous method to shorten the distance between user and UAV, [41] uses the K-means method to derive the horizontal position of the UAV. The K-means method is a clustering method, in which a set of points is divided into multiple sets, minimizing as much as possible the sum of the Euclidean distances between the centers of the clusters and the points in each cluster.  
In [41], the user distribution is considered as a point cloud, while the resulting clusters are the set of users covered by each UAV and the cluster center, which is the center of gravity of each cluster, is the horizontal position of the UAV.  
The authors of [38] use another comparison scheme; however, this method is only effective for uniform user distributions. In other words, it is not effective for distributions where the variability occurred in actual environments. This is because when the user distribution in a target area is biased, the coverage circle becomes large, resulting in much useless coverage. If the coverage circle becomes large, the overlap between the coverage circles increases and the interference increases.  
In this paper, we propose a method to solve the problem of the K-means method, considering the characteristics of millimeter-waves. It is a method that introduces the smallest-circle problem to the K-means method. Here, the smallest-circle problem is a geometric problem to determine the smallest circle that can contain an asymmetric point group. Details are provided in Appendix A of this paper. The complexity of the proposed method depends on the complexity of the K-means method and the smallest-circle problem, which are \(\mathrm{O}(2 IKn)\) and \(\mathrm{O}(n)\) for the former and latter methods, respectively, where \(K\) is the number of clusters, \(I\) is the number of iterations until convergence of the K-means method, and \(n\) is the number of data points, i.e., the number of users [42]. In summary, the complexity of this UAV placement method can be given by \(\mathrm{O}((2 IK+1)n)\).  
Figure 3 shows the coverage circles derived by using only the K-means method for a specific user distribution and the coverage circles obtained by applying the smallest-circle problem in addition to the K-means method. Here, the number of UAVs is 5, which means the number of clusters is 5. In Figure 3, the x and y axes represent an area of 100 m \(\times\) 100 m. The points in the area represent the distribution of users and the color-coding represents clustering by the K-means method. The radius of the circle shows the coverage of each UAV and varies depending on the altitude of each UAV. The UAV is located at the center of the circle. As can be seen in Figure 3, by introducing the smallest-circle problem, the coverage circle becomes smaller. In other words, the wasted coverage is reduced, with the interference also expected to be reduced due to less overlap between the coverages.