TGN-MCDS: A Temporal Graph Network-Based Algorithm for Cluster-Head Optimization in Large-Scale FANETs

With the growing deployment of Flying Ad hoc Networks (FANETs) in military and civilian applications, constructing a stable and efficient communication backbone has become a critical challenge. This paper tackles the Cluster Head (CH) optimization problem in large-scale and highly dynamic FANETs by formulating it as a Minimum Connected Dominating Set (MCDS) problem. However, since MCDS is NP-complete on general graphs, existing heuristic and exact algorithms suffer from limited coverage, poor connectivity, and high computational cost. To address these issues, we propose TGN-MCDS, a novel algorithm built upon the Temporal Graph Network (TGN) architecture, which leverages graph neural networks for cluster head selection and efficiently learns time-varying network topologies. The algorithm adopts a multi-objective loss function incorporating coverage, connectivity, size control, centrality, edge penalty, temporal smoothness, and information entropy to guide model training. Simulation results demonstrate that TGN-MCDS rapidly achieves near-optimal CH sets with full node coverage and strong connectivity. Compared with Greedy, Integer Linear Programming (ILP), and Branch-and-Bound (BnB) methods, TGN-MCDS produces fewer and more stable CHs, significantly improving cluster stability while maintaining high computational efficiency for real-time operations in large-scale FANETs.