A Spatial Clustering and Matching Game–Based Multihop Routing Algorithm for Heterogeneous UAVs

Abstract

Unmanned aerial vehicle (UAV) clusters are increasingly deployed in military and civilian applications, necessitating efficient and reliable communication networks for cooperative operations. However, heterogeneous UAVs pose significant challenges for data transmission within and outside the cluster due to their high mobility, rapid topology changes, and limited node energy. For the routing planning problem of transmitting data from autonomous, heterogeneous UAVs to the cloud, existing methods struggle to accommodate the heterogeneity of UAVs and the communication bandwidth requirements, given the NP-hard nature of the problem. To address this issue, this paper first constructs an exact model based on mixed-integer linear programming to describe the heterogeneous UAVs, comprehensively searches the solution space, and generates a reasonable routing scheme for the heterogeneous UAVs, guiding the cluster communication network system design. Secondly, a heuristic algorithm is proposed that leverages density–based spatial clustering and matching game theory. The algorithm calculates relay nodes based on local density and relative distance. It generates an approximate optimal data transmission path for each UAV through a multilevel matching process, effectively reducing communication delay within the cluster. Finally, the paper conducts simulation experiments in randomly generated regional scenarios to validate the efficiency and effectiveness of the proposed method.