Integration of A* and k-means clustering for star network design in environments considering obstacles

Multi-level is a widely adopted topology in many telecommunication systems, including both wireless and wired networks. The optimization of multi-level star networks, however, is not trivial, especially in the presence of obstacles. In this paper, we employ the well-known k-means clustering method but, instead of using a distance metric that neglects obstacles, we use the A* algorithm to find trajectories that allow circumventing obstacles. In order to assess the feasibility of the proposed approach, we apply it to 25 users arbitrarily located in a 20x20 uniform grid. This example indicates that by adopting A* to find obstacle-aware trajectories, the mean distance between the users and their associated centroids is sensibly reduced.