1
Diverge-Merge Formation and MAC Control in Structured Airspace
arXiv:2607.17489v1 [cs.NI] 20 Jul 2026
Kai Xiong, Member, IEEE, Xingyu Wu, Ba Zhang, Li Wei, Member, IEEE, Min Zeng, Supeng Leng, Senior Member, IEEE
Abstract—The rapid scaling of advanced air mobility (AAM) makes corridor-based structured airspace a promising infrastructure for high-density unmanned aerial vehicle (UAV) traffic. Formation flight can improve corridor capacity by suppressing shockwave propagation, but rigid formations become inefficient or unsafe during ramp branching, merging, and congestion. To address this problem, this paper proposes a task-driven divergemerge control framework for UAV formations in structured airspace. At the beginning, a corridor-ramp branching structured airspace model is established to characterize the traffic dynamics and spatial constraints. Building upon this, a fast task-driven clustering mechanism integrates spatial connectivity, flight intent, and aerial task interactions to enable real-time diverge and merge for ramp branching and traffic reshaping. To make the diverge-merge reconfigurations executable at the media access control (MAC) layer of the formation, a cluster-aware distributed time division multiple access (CAD-TDMA) protocol is further designed. It protects intra-cluster control synchronization while conservatively reusing low-risk inter-cluster slots. Simulation results show that the proposed diverge-merge algorithm maintains near-zero geometrical misclassification under severe physical overlapping and congestion. With the formation diverge-merge traces, CAD-TDMA achieves the best delay–loss–throughput tradeoff over fixed TDMA and WiFi MAC. It shows that the proposed formation control framework can jointly support realtime formation reconfiguration and reliable communication in corridor-ramp structured airspace. Index Terms—UAV Formation, Diverge and Merge Control, MAC Design, Corridor-Ramp Structured Airspace
spatial boundaries and flow segregation, thereby laying the physical foundation for safe low-altitude operations. Despite the structural advantages of corridors, independent UAV flight remains highly vulnerable to string shockwave effects, where minor velocity perturbations amplify backward and drastically degrade traffic flux. To breach this capacity limit, formation flight has been proposed as a highly effective paradigm. As illustrated in Fig. 1a, upon impact with a traffic shockwave, formation flight sustains and releases a higher traffic flux compared to individual flight. Furthermore, Fig. 1b shows that formation flight enables the swarm to recover the required safety separation faster after a shockwave disturbance. By restructuring multiple UAVs into a macroscopic kinematic unit, formation flight acts as a low-pass filter that suppresses high-frequency perturbations, thereby establishing the necessity of coordinated formations for high-capacity and safe corridor traffic.
(a) Individual flight dynamics in response to traffic shockwaves
(c) Traffic flux upon shockwave hit
I. I NTRODUCTION Dvanced air mobility (AAM) has catalyzed an unprecedented surge in low-altitude airspace utilization, positioning unmanned aerial vehicles (UAVs) as the primary carriers for next-generation urban logistics and on-demand transportation. As aerial traffic scales toward density, the conventional paradigm of unconstrained free-flight becomes untenable, plagued by intractable route-crossing conflicts, congestion, and stringent regulatory safety mandates. To mitigate these systemic bottlenecks, corridor-based airspace has emerged as an indispensable architectural paradigm, organizing UAV flight into unidirectional, pipe-straight structures that enforce strict
A
K. Xiong, X. Wu, B. Zhang, and S. Leng are with School of Information and Communication Engineering, University of Electronic Science and Technology of China, Chengdu, 611731, China. L. Wei is with College of Information Science and Electronic Engineering, Zhejiang University, Hangzhou 310027, China. M. Zeng is with the Network and Communication Research Institute, College of Information Engineering, Southwest University of Science and Technology, Mianyang, Sichuan 621010, China.
Oscillated position (b) Formation flight dynamics in response to traffic shockwaves
(d) Safety separation upon shockwave hit
Fig. 1: Corridor-based formation flight v.s. individual flight.
However, in realistic low-altitude traffic scenarios, UAVs cannot fly strictly straight. The reason is that navigating around no-fly zones, accommodating diverse destinations, and adapting to heterogeneous task distributions inevitably necessitate frequent changes in corridors with different directions. This demands a multidirectional corridor network. To guarantee flight safety, these multidirectional corridors cannot physically intersect at the same altitude. Consequently, to facilitate seamless direction switching among non-overlapping corridors, ramp structures, serving as dedicated transitional links between distinct corridors, are strictly required. Motivated by this, we propose the concept of a corridor-ramp structured airspace, as depicted in Fig. 2. This structured airspace comprises altitude-
2
layered corridors interconnected by both intralayer and interlayer ramps, with individual corridors further longitudinally partitioned into multiple parallel lanes. It not only maintains corridor flight advantages but also provides a tractable environment for modeling complex route branching, merging, and capacity bottlenecks in high-density UAV dispatch. Unfortunately, the introduction of the corridor-ramp structured airspace dictates that UAV formations must undergo dynamic diverge and merge maneuvers to navigate the network efficiently. As a formation approaches a ramp junction, its members often possess diverse downstream destinations, necessitating a diverge operation to decouple the macroscopic formation into sub-formations for corridor-switching navigation. Conversely, when sub-formations exit a ramp and enter a main corridor, maintaining overly fragmented formations wastes valuable spatial capacity and escalates routing overhead. In such scenarios, these sub-formations must proactively execute a merge operation to re-aggregate with nearby co-directional formations, thereby maximizing the corridor’s carrying density. Therefore, the capability to execute agile and appropriate diverge-merge transition is the prerequisite for efficient formation flight within this structured airspace. Crucially, these transient diverge-merge operations impose severe stresses on the underlying UAV ad-hoc networks. Formation flight control, cooperative collision avoidance, and state synchronization heavily rely on reliable and stable intra-formation communications. During dynamic diverging and merging, formation node density fluctuates sharply, and formation-management traffic becomes highly bursty. Traditional medium access control (MAC) protocols struggle to provide comprehensive and stable network performance under such conditions. Contention-based protocols (e.g., CSMA/CA) suffer from severe air interface collisions and unpredictable delays when local density spikes, whereas fixed TDMA avoids random contention but introduces excessive waiting latency and lacks the flexibility to accommodate bursty, topologyaware control traffic. Consequently, a communication-support mechanism tailored for the dynamic diverge and merge process is needed to bridge the gap between physical formation control and cybernetic wireless access. To address these intertwined challenges, this paper proposes a task-driven diverge-merge control framework tailored for the corridor-ramp structured airspace. First, we develop a task-driven diverge-merge algorithm that transcends traditional spatial-only clustering. This method integrates communication connectivity, 3-dimensional (3D) flight intent, and historical task interaction intensity. Furthermore, to support the resulting high-frequency network changes at the wireless access layer, we design a cluster-aware distributed TDMA (CADTDMA) protocol. CAD-TDMA explicitly maps the task-aware cluster labels into distributed frame-level slot management. It strictly protects intra-cluster owner slots for critical control synchronization while conservatively reusing low-risk intercluster slots based on passive overhearing and local risk history, thereby achieving an optimal delay-loss-throughput tradeoff. Specifically, the main contributions of this paper are summarized as follows: • We propose a corridor-ramp structured airspace model
that explicitly captures the geometric constraints and topological complexities of low-altitude traffic. By incorporating altitude-layered, multi-lane unidirectional corridors interconnected by ramps, this structured airspace enforces flow segregation to eliminate free-flight conflicts while providing a foundation for modeling capacity bottlenecks during high-density UAV dispatch. • We develop a task-driven dynamic diverge-and-merge collaborative control algorithm that achieves precise formation reconfiguration under stringent spatial constraints. Distinct from traditional group partitioning, our approach leverages unsupervised state-feedback for closed-loop weight adaptation and an accelerated Fast Spectral Clustering (FSC) technique. By anchoring topology evolution on historical task interactions and 3D flight intent, the algorithm effectively prevents blind fragmentation and erroneous merging when physical distance cues degrade during complex ramp maneuvers. • We design a cluster-aware distributed TDMA (CADTDMA) MAC protocol specifically tailored to support the bursty communication demands of formation divergeand-merge operations. By mapping task-aware cluster labels into frame-level slot management, CAD-TDMA protects intra-cluster reserved slots for critical synchronization and conservatively reuses low-risk inter-cluster slots according to local observation history. Extensive ns-3 validations demonstrate that this communicationsupport mechanism achieves a more balanced delay– reliability tradeoff than fixed TDMA and WiFi baselines in dense, dynamic corridor flight scenarios. The remainder is organized as follows: Sec. II reviews related work. Sec. III presents the system model. Sec. IV and V give the proposed algorithms. Sec. VI presents the simulation, and Sec. VII concludes the paper. II. R ELATED W ORK The realization of AAM necessitates the seamless integration of airspace architecture, flight formation coordination, and wireless communication support. This section reviews the state-of-the-art in these three interconnected domains and identifies the critical gaps that motivate our diverge-merge formation control and network design. A. Structured airspace architecture As the scale of AAM expands, the conventional free-flight paradigm becomes nonviable for managing high-density UAVs due to massive route-crossing conflicts and collision risks [1]. Consequently, both academia and aviation authorities have proposed various airspace architectures to regulate low-altitude operations [2]. Existing low-altitude airspace studies have explored static grid-based partitioning via geofencing [3] and multi-layered airspace designs aimed at vertical flow segregation [4]. Additionally, directional corridors championed by the federal aviation administration (FAA) [5, 6] and cooperative virtual-tube models [7] have been extensively investigated. These pioneering airspace architectures have advanced aerial traffic management, capacity estimation, and route planning.
3
Top View
Layer3 : 𝓛𝟑
Structured Airspace
Formation Flight
Layer2 : 𝓛𝟐
Lane1: 𝒒𝟏
Layer1: 𝓛𝟏 Lane2: 𝒒𝟐
Side View
Lane3: 𝒒𝟑
Ramp
Dynamic Network Support
Layer3
Corridor(𝒆i ) Layer2
Diverge Sub-cluster
Sub-cluster
Ramp
Ramp
Layer1
Merge Take-off
Landing
Fig. 2: Corridor-ramp structured airspace.
Despite exploring diverse airspace architectures, existing studies overlook the extreme spatial squeezing effects imposed by geometric boundaries on formation flight at the structured bottlenecks. They fail to address the network-physical coupling between macroscopic spatial constraints and microscopic formation control and communication scheduling. B. Formation flight control In structured airspace, formation flight is a promising paradigm for enhancing macroscopic traffic flux and mitigating collision risks associated with uncoordinated movements. However, maintaining rigid formations is impractical when confronted with narrow ramps and dynamic task requirements. Hence, dynamic formation reshaping has emerged as a prominent research area [8–10]. Existing literature explores formation diverge-merge mechanisms: some employ autonomous decision, such as improved potential field control or multi-agent consensus protocols, to achieve adaptive obstacle avoidance [11, 12]. Moreover, graph-theoretic clustering and heuristic rules are widely utilized. By partitioning adjacency matrices based on spatial metrics and communication quality to sever weak edges, these methods facilitate safe formation diverging at route convergences [13–15]. Despite these efforts, current strategies exhibit limitations. Traditional algorithms often rely on homogeneous physical distance or relative velocity features, neglecting historical task interactions and flight intents. Furthermore, handling real-time evolution for large-scale nodes incurs prohibitive computational overhead for eigen-decomposition in spectral clustering, failing to meet millisecond-level low-altitude operation requirements [16, 17]. C. Distributed MAC protocols MAC design has been widely studied in wireless AdHoc, vehicular, and aerial networks. Classical carrier-sense random access protocols, such as carrier sense multiple access with collision avoidance (CSMA/CA) and IEEE 802.11 distributed coordination function (DCF), provide flexible distributed access without global coordination. However, their performance is strongly affected by contention intensity and
hidden-terminal conditions. In dense and dynamic UAV formations, diverge-merge operations may cause sudden nodedensity variations and bursty traffic, increasing collision probability, retransmissions, and access delay uncertainty [18– 20]. In contrast, TDMA-based MAC divides time into frames and slots, which can provide more predictable transmission opportunities by reducing random contention. It is suitable as a MAC-support mechanism for high-dynamic formations. Existing distributed TDMA MAC protocols have been investigated in Ad-Hoc, vehicular, and aerial networks. For example, distributed slot reservation and reuse have been widely studied for reliable broadcast and delay-sensitive communication [21–25]. Nevertheless, these protocols mainly manage slots according to node-level reservations, local topology, or traffic demand. They do not explicitly apply the task-aware cluster labels, and therefore cannot directly distinguish intra/inter-cluster synchronization slots. III. S YSTEM M ODEL Conventional swarm control isolates formation reshaping from network scheduling, inevitably triggering disconnections and collisions. To fulfill the research gap, this section provides a joint formation and wireless MAC scheduling optimization model. Specifically, we first construct the corridorramp airspace and UAV kinematics. Then, a multi-dimensional similarity metric is proposed to optimize the formation control. A. Corridor-ramp structured airspace Emerging urban traffic management frameworks such as UTM [26] and U-space [27] confine UAV operations within corridors. We accordingly propose a multi-layered and multilane corridor-ramp structured airspace. The airspace is stratified into NL altitude layers {L1 , . . . , LNL } that separate conflicting flows. Each layer Lℓ hosts a set of parallel unidirectional corridors {e1 , e2 , . . . }, and adjacent layers differ by a fixed heading angle α so that their flows do not intersect at the same altitude, as shown in the top view of Fig. 2. Each corridor e is in turn divided into nL,e parallel lanes {q1 , . . . , qnL,e } across its cross-section, which form the discrete lateral slots along which a formation arranges its members, as shown in the formation flight panel of Fig. 2. Corridors are interconnected by ramps. A ramp is a transitional link that connects either two corridors within the same layer or two corridors residing in different layers, so that a UAV switches corridors through a ramp according to its destination and the downstream congestion. The airspace is abstracted as a directed graph G = (V, E), where V collects the junctions such as waypoints and ramp endpoints, and each edge e ∈ E is a corridor segment: e = le , Re , nL,e , ze , Cmax,e (v) , (1) with length le , cross-sectional radius Re , lane count nL,e ≤ ⌊2Re /wL ⌋, lateral lane spacing wL , and host layer ze ∈ {1, . . . , NL } determining corridor altitude and heading. Rearend safety within each lane q enforces a velocity-dependent 2 longitudinal separation dsaf e (v) = d0 + τ v + 2avmax , which combines the static margin d0 , the reaction delay τ , and the
4
maximum deceleration amax . Aggregating the nL,e lanes, the corridor capacity is: le Cmax,e (v) = nL,e . (2) dsaf e (v) When the speed rises or a formation approaches a ramp, both the per-lane admissible count and the available lane number decrease, so a formation executes diverge-merge maneuvers to change the lane occupancy across different corridors and keep the traffic load within the corridor capacity Cmax,e (v). B. Formation flight dynamics Conventional free-flight mobility models fail to capture the severe physical mutual exclusions inherent in confined structured airspace. To reflect fluid-like congestion and collision avoidance, the kinetic state of UAV ui ∈ U at time t is assembled by its position pi (t) ∈ R3 and velocity vi (t) ∈ R3 . Let ptgt,i denote the terminal waypoint for node ui . To enforce the required safety separation dsaf e during spatial squeezing, we integrate an artificial potential field (APF)-based spatial repulsive force. For the detectable neighbor set Ni , the repulsion frep,i (t) is activated exclusively when the inter-UAV distance di,j (t) = ∥pi (t) − pj (t)∥ breaches dsaf e : X 1 pi (t) − pj (t) 1 − , (3) frep,i (t) = κ di,j (t) dsaf e di,j (t) j∈Ni ,di,j <dsaf e
where κ is the repulsive gain. The actual steering ui (t) synthesizes destination attraction, velocity damping, and this collision repulsion. To comply with the physical limits, the joint force is bounded by the allowable acceleration amax : ptgt,i −pi (t) ui (t) = satamax vmax −vi (t)+frep,i (t) , ∥ptgt,i −pi (t)∥ (4) where the standard vector saturation operator is satC (x) = C x min(1, ∥x∥ ). Besides, navigating narrow corridors exacerbates aerodynamic disturbances (e.g., wall effects). This exogenous perturbation is modeled as a Gaussian noise ni (t) ∼ N (0, σ 2 I). The discrete-time kinematic updates, bounded by the allowable speed vmax , are given as: vi (t + 1) = satvmax vi (t) + ui (t)∆t + ni (t), (5) pi (t + 1) = pi (t) + vi (t + 1)∆t. Ultimately, this mobility model couples kinematic bottlenecks with fluidic congestion, providing a physical foundation for evaluating the subsequent formation transition mechanisms. C. Multi-dimensional clustered similarity Conventional spatial clustering algorithms blindly equate physical proximity with logical affiliation. This is a fatal assumption in structured airspace where functionally distinct formations frequently cross corridors and ramps. To shatter this spatial rigidity, we construct a time-varying, undirected, and non-negative logical graph H(t) = (U , S(t)) to represent the cyber-physical relationships within the formation. The similarity matrix S(t) ∈ RN ×N quantifies the logical coupling
degree between any pair of nodes. To satisfy the symmetric and non-negative prerequisites for the subsequent Normalized Cut (Ncut) operations, S(t) is assembled by three densityadaptive similarities, which are the communication similarity, flight intent similarity, and task similarity. 1) Communication similarity: This similarity characterizes the communication link reliability. In congested spaces (e.g., rear-end congestion in a single corridor or ramp merging), the abrupt surge in UAV density leads to severe communication interference. Assuming the transmission power of all UAVs is Ptx . When node j receives a signal from node i, the physicallayer Signal-to-Interference-plus-Noise Ratio (SINR) is [28]: γi,j (t) =
2 Ptx G0 d−α i,j (t)|hi,j |
N0 +
, −α 2 k∈U \{i,j} Ptx G0 dk,j (t)|hk,j |
P
(6)
where di,j (t) is the distance between UAV i and j, α is the path loss exponent, G0 is the reference channel gain, h is the fading coefficient, and N0 is the ambient noise power. Due to the distinct interference perceived at different UAVs (receivers), we then define the communication similarity using a Sigmoid activation function that maps the averaged SINR of bidirectional UAV i and j into a continuous probability: 1 , (7) SLi,j = γi,j (t)+γj,i (t) − γ 1 + exp −κ th 2 where γth is the minimum SINR demodulation threshold, and κ controls the activation steepness. This formulation intrinsically filters out weak links while preserving symmetric topological connectivity. 2) Flight intent similarity: During UAV formation merging and overtaking, distinct task groups may spatially overlap. Flight intent serves to decouple spatially intermingled UAVs. The intent similarity SIi,j ∈ [0, 1] is jointly determined by short-term kinematic heading alignment and long-term 3D trajectory convergence: 1 viT (t)vj (t) SIi,j = λ + 2 2∥vi (t)∥∥vj (t)∥ (8) ∥ptgt,i − ptgt,j ∥2 + (1 − λ) exp − , 2 2σtgt where v(t) denotes the instantaneous velocity vector, ptgt represents the 3D terminal task waypoint, λ ∈ [0, 1] balances the influence of short-term heading and long-term destination, and σtgt defines the distance threshold for destination similarity. The first term calculates the cosine similarity of velocity vectors to align UAV headings, while the second term employs a Gaussian kernel to measure terminal waypoint proximity. 3) Task interaction similarity: To verify the underlying logical affinity, we mine the historical task interactions through the proposed time-decayed frequent pattern tree (TD-FPTree) algorithm. Denote Ωi,j (τ ) ∈ {0, 1} as a binary indicator, where Ωi,j (τ ) = 1 if node i and node j cooperate in the same task transaction at time τ , and 0 otherwise. To enhance recent interactions while fading obsolete relations, the interaction intensity STi,j is defined over a sliding time window [t−Tw , t]: STi,j =
1 Φ
t X τ =t−Tw
Ωi,j (τ )e−ηd (t−τ ) ,
(9)
5
where ηd > 0 is the coefficient, and Tw is P the window length. t −η(t−τ ) Crucially, the normalization factor Φ = τ =t−Tw e i,j bounds ST within [0, 1]. Finally, the adjacency matrix of the logical connection graph H(t) is a weighted sum of three similarity metrics: S i,j (t) = β1 (t)SLi,j + β2 (t)SIi,j + β3 (t)STi,j , (10) P where βk (t) ≥ 0 and i βi (t) = 1. This construction ensures that S(t) is symmetric, non-negative, and properly bounded within [0, 1], satisfying all necessary and sufficient prerequisites for the subsequent graph partitioning operations.
construct the similarity matrix. A subsequent formation control component evaluates trigger conditions to set the target cluster count. If the triggering conditions are met, the formation performs a FSC algorithm to reshape its envelope geometry; otherwise, it bypasses re-clustering. Finally, an adaptive weighting component computes the weighting parameters for the next time slot, providing feedback to the similarity construction.
Dynamic diverge-merge control 1. Similarity Construction
𝑺(𝑡)
link·intent·task similarity
Upon the multi-dimensional connection graph H(t) = (U, S(t)), the dynamic diverge-and-merge process is formed as a capacity-constrained Ncut problem. Let the formation U be partitioned into k disjoint clusters (sub-formations), denoted as C = {C1 , C2 , . . . , Ck }. Furthermore, the objective is designed to maximize the intra-cluster networkformation cohesiveness while safely severing weak logical connections. given cluster Cm , the external edge-cut P P For any i,j S (t) (overall severed logical connections) i∈Cm j ∈C / m P P and the degree-volume i∈Cm j∈U S i,j (t) (overall connectivity intensity) are functions of similarity matrix S(t). Unlike traditional clustering algorithms, any formation control in structured airspace must respect the underlying spatial and communication bottlenecks. To prevent oversized formations from overwhelming the MAC-layer scheduling, the partition is subjected to a wireless access capacity Nmax , dictated by the available air-interface resources. This constraint acts as the bridge linking the formation control with wireless limits. Consequently, the optimization problem is: P k P i,j X i∈Cm / m S (t) P Pj ∈C P1 : min i,j C (11) i∈Cm j∈U S (t) m=1 |Cm | ≤ Nmax ,
Evaluate trigger & set target 𝑲
𝑆(t) = 𝛽(t)1 𝑆ℒ + 𝛽(t)2 𝑆ℐ + 𝛽(t)3 𝑆𝒯
D. Problem formulation
s.t.
2. Diverge-merge Decision
∀m ∈ {1, . . . , k}.
IV. DYNAMIC D IVERGE -M ERGE C ONTROL Solving the network-spatial constrained cluster partitioning problem P1 in real time constitutes the core challenge of the proposed diverge-merge control. To meet the stringent real-time computational demands imposed by high-frequency formation transitions, the proposed algorithm is designed into three core modules: 1) an on-demand diverge-and-merge mechanism; 2) a fast spectral clustering paradigm; and 3) a closed-loop adaptive clustering adjustment. A. Network-supported formation control To shatter the network-formation isolation inherent in swarm optimization, we propose a network-support diverge and merge formation control scheme, as depicted in Fig. 3. Specifically, this architecture has two coupled modules. At the upper module, the dynamic diverge-merge control operates through a four-step closed loop. Rather than relying on spatial proximity, the process begins by evaluating multi-dimensional connections (communication link, flight intent, and task) to
else 𝜷(𝑡 + 1)
Next time slot
If trigger target 𝑲
𝓒, 𝑺(𝑡)
3. Fast Spectral Cluster
4. Adaptive weighting 𝜷 𝑡 + 1 ← ΠΔ 𝜷 𝑡 − 𝜂ො𝐠 𝑡
Cluster Label
𝑂(𝑁 3 ) → 𝑂(𝑁𝑙𝑜𝑔𝑁 + 𝑁𝑘 2 )
Topological basis for slot allocation
Information Input - Cluster label - Overhearing records - Risk evidence - Distance check
Three-step clustering
Cluster 𝓒∗
𝐠ො 𝑡 ≈ SPSA_grad 𝒞, 𝐒
𝑵𝒎𝒂𝒙
CAD-TDMA Slot-state Decision
Network-supported maximum number of UAVs
Slot-state Output - Own(Protected) - Forbidden(Same-cluster) - Reusable(Inter-cluster) - Cooling(Inter-cluster) - Idle/Unobserved
Fig. 3: Network-supported diverge-merge control framework.
At the lower module of Fig. 3, the generated cluster labels from the diverge-merge control module serve as the basis for MAC slot allocation. CAD-TDMA maps these labels, alongside passive overhearing records, risk evidence, and distance checks, into local slot-state decisions. Each slot is classified as one of the Own (Protected), Forbidden (Samecluster), Reusable (Inter-cluster), Cooling (Inter-cluster), or Idle/Unobserved, ensuring same-cluster slots are protected while low-risk inter-cluster slots can be reused. To maintain network-formation consistency, CAD-TDMA feeds back the wireless access capacity to the diverge-merge control module of Fig. 3, ensuring that the number of cluster and an individual cluster scale adhere to the real-time wireless access capability. B. Dynamic diverge-and-merge triggers In spatial confined corridors, relying on a static number of clusters k inevitably degrades communication and collisionproof flight efficacy. To avoid this, we design an event-driven mechanism to dynamically manage the formation scale. As multiple clusters converge at spatial bottlenecks (e.g., multi-ramp junctions), inter-cluster distances drastically diminish. To accurately capture imminent collision risks, the physical inter-cluster distance is defined by the minimum edge distance: Dinter (Cm , Cn ) = mini∈Cm ,j∈Cn di,j (t). A merge maneuver is executed when Dinter falls below a predefined threshold dmerge . Crucially, in structured airspace, physical survival strictly supersedes logical task independence. Crucially, in structured airspace, flight safety supersedes logical
6
task independence. Therefore, physically proximal clusters are compelled to logically merge, forcing them to share a unified TDMA frame for coordinated collision avoidance. Provided their merged cluster size satisfies the MAC access capacity, the merge trigger is formulated as: Dinter (Cm , Cn ) ≤ dmerge
∧
|Cm | + |Cn | ≤ Nmax . (12)
Once the triggering conditions are met, the adjacent formations logically merge (k ← k − 1). Conversely, maintaining an oversized formation incurs prohibitive intra-communication delays. To comply with the MAC access capacity Nmax limitation, the local degradation loss is evaluated through the maximum physical dispersion: ϵL (Cm ) = maxi,j∈Cm (di,j (t)/Rc )2 . Hence, the local diverge is activated if: |Cm | > Nmax
∨
ϵL (Cm ) ≥ ϵth .
(13)
Upon activation, the FSC algorithm is locally invoked to cleave this specific oversized formation (klocal ← ⌈|Cm |/Nmax ⌉), releasing network pressure. Prolonged reliance on local operations may gradually fragment the macro-connections. Let kmax ≥ ⌈|U|/Nmax ⌉ denote the upper bound of manageable sub-nets for the corridor routing protocol. When the total cluster count exceeds this threshold (k > kmax ), local adjustments are deemed insufficient. Serving exclusively as a last-resort fallback due to its high computational overhead, a cluster-wide FSC execution is triggered (kglobal ← ⌈|U |/Nmax ⌉) to eradicate accumulated formations fragmentation and restore traffic efficiency. C. Fast spectral clustering While spectral clustering provides mathematically optimal topology boundaries, its baseline O(N 3 ) complexity is computationally catastrophic for resource-constrained UAVs executing high-frequency maneuvers. To shatter this bottleneck, we propose a three-stage FSC pipeline that drastically curtails the computational footprint without sacrificing algebraic rigor. First, we aggressively sparsify the dense similarity matrix S(t) to bypass the O(N 2 ) graph construction bottleneck. By deploying spatial KD-trees, we construct a mutual K-nearest neighbor (K-NN) graph in just O(N log N ) time. For any node i with its Knn strongest connections denoted by NK (i), the sparse symmetric adjacency matrix is defined as: ( S i,j (t), if j ∈ NK (i) or i ∈ NK (j) i,j Ssparse = . (14) 0, otherwise
Algorithm 1: Fast Spectral Clustering (FSC) Input: S(t), neighbor count Knn , numerical shift δ Output: Cluster partition C = {C1 , C2 , . . . , Ck } 3 Sparsify S(t) by mutual Knn nearest neighbors 4 Regularize degree matrix: Dδ ← diag(Ssparse 1) + δI 5 Compute symmetric normalized Laplacian: −1/2 −1/2 Lsym ← I − Dδ Ssparse Dδ 6 Extract top k eigenvectors of Lsym via IRLM 7 Normalize eigenvector matrix U by rows to get embedding E∗ ∈ RN ×k ∗ 8 Apply Mini-Batch K-Means++ on E
1 2
eigenvectors corresponding to the smallest eigenvalues, IRLM drastically curtails the embedding complexity to O(N k 2 ). The optimal cluster count k is dynamically determined by the standard eigengap heuristic, k = arg maxi (λi+1 − λi ). The extracted eigenvectors are then row-wise ℓ2 -normalized to form the low-dimensional feature matrix E∗ ∈ RN ×k . Finally, to accelerate the discretization phase, we replace standard K-Means with MiniBatchKMeans on E∗ . Initialized via KMeans++ [30], it updates centroids using random subsets rather than the entire swarm, operating in just O(b·k ·I) where b is the batch size and I is the iteration count. By cascading KD-tree sparsification (O(N log N )), IRLM partial extraction (O(N k 2 )), and MiniBatch discretization (O(b · k · I)), the computational core of the FSC mechanism is strictly bounded by O(N log N + N k 2 ). Since the batch size, iterations, and cluster count satisfy b, I, k ≪ N , this FSC mechanism solidly guarantees compliance with the strict real-time processing constraints of onboard flight controllers, with the complete procedure given in Alg. 1. D. Adaptive weight adjustment
(15)
Static topology weights leave the swarm blind to structural degradation in fluid corridor environments. The three similarity modalities also differ in how informative they are over time. In free flow, spatial proximity separates formations cleanly, while inside a congested corridor the formations interpenetrate and the link modality loses its discriminative power. The weighting vector β(t) = [β1 (t), β2 (t), β3 (t)]T is therefore adapted online via structural feedback. We define three unsupervised penalty metrics to quantify distinct topological defects: 1) Communication degradation: This metric evaluates the loss of intra-cluster spatial cohesiveness by measuring physical link dispersion. Let Rc denote the maximum reliable communication range. The global penalty is formulated as the mean squared distance ratio: k X X di,j (t) 2 1 X 1 ϵL (t) = . (16) k m=1 |Cm |2 Rc
where Dδ = Dsparse (t) + δI. This strict regularization securely bounds the eigenvalues within [0, 2]. Second, rather than executing an exhaustive O(N 3 ) eigendecomposition, we employ the Implicitly Restarted Lanczos Method (IRLM) [29]. By extracting only the first k
An elevated ϵL (t) indicates that the partition stretches intracluster links beyond reliable range. 2) Clustering oscillation: To penalize structural jitter while bypassing the label permutation problem of unsupervised clustering, we introduce a co-membership indicator matrix
To prevent ill-conditioned matrix exceptions caused by isolated nodes during sparsification, a tiny numerical stabilizer δ > 0 is injected. The regularized symmetric normalized Laplacian is given as: −1/2
Lsym (t) = I − Dδ
−1/2
Ssparse (t)Dδ
,
i∈Cm j∈Cm
7
Z(t) ∈ {0, 1}N ×N , where Zi,j (t) = 1 if UAVs i and j share a cluster and 0 otherwise. The macroscopic oscillation is quantified by the temporal disagreement: XX 1 ϵI (t) = |Zi,j (t) − Zi,j (t − 1)| . (17) N (N − 1) i∈U j̸=i
A high ϵI (t) indicates that the partition churns between slots instead of tracking a persistent structure. Algorithm 2: Fast Diverge-and-Merge Control Input: U, Nmax , kmax , ϵth , dmerge , ddiverge , η, Tβ Output: Cluster assignments C(t) T 3 Initialize β(0) ← [1/3, 1/3, 1/3] 4 for each time slot t do 5 if t mod Tβ = 0 then 6 Update β(t) using SPSA gradient ĝ(t) 1 2
7 8 9 10 11 12 13 14 15 16 17 18
Refresh S(t) using β(t), set kcap ← ⌈|U|/Nmax ⌉ if Diverge Condition then ktgt ← k(t − 1) + 1 else if Merge Condition then ktgt ← k(t − 1) − 1 else ktgt ← EigenGap(S(t)) ktgt ← clip(ktgt , max(kmin , kcap ), kmax ) if ktgt ̸= k(t − 1) OR Trigger conditions met then C(t) ← FSC(S(t), ktgt ) ; // via Alg. 1 else C(t) ← C(t − 1)
3) Logical fragmentation: This metric quantifies the proportion of collaborative relationships severed by the current partition, defined as the normalized cut of the historical interaction graph: Pk P P i,j m=1 i∈Cm j ∈C / m ST ϵT (t) = . (18) P P i,j i∈U j∈U ST A rising ϵT (t) indicates that cohesive task sub-groups are being cut apart. The three indicators live on incommensurable scales, as ϵL is a squared distance ratio while ϵT is a normalized cut ratio. Each is standardized by its own exponential moving scale sk (t) = ρ sk (t − 1) + (1 − ρ) |ϵk (t)|, yielding the dimensionless defect ϵ̂k = ϵk /sk . With ϵ̂(t) = [ϵ̂L , ϵ̂I , ϵ̂T ]T , the weighting is posed as the online minimization of the aggregate normalized defect: min J(β) = 1T ϵ̂(β),
β∈∆
stochastic approximation (SPSA) estimate [31], which probes the cost along one random direction and needs two extra evaluations of J per update: J Π∆ (β + c d) − J Π∆ (β − c d) d, ĝ(t) = 2c (20) β(t) = Π∆ β(t − 1) − η ĝ(t) , where c is the perturbation magnitude, d ∈ {−1, +1}3 is a Rademacher vector, η is the step size, and Π∆ denotes Euclidean projection onto the simplex. The perturbation is applied once every Tβ slots to limit overhead. The recursion converges to a stationary point of J, at which no modality can be down-weighted without inflating the aggregate defect. Coupling this feedback with the proposed FSC and the ondemand triggers completes the formation diverge and merge algorithm, given as Alg. 2. V. C LUSTER -AWARE D ISTRIBUTED TDMA The diverge-merge algorithm in Section ?? outputs spatialand task-aware cluster labels. These labels indicate which UAVs should frequently exchange control information and task-related data. However, in dense corridors, formation diverge-merge maneuvers may suddenly increase network traffic load. If the MAC layer cannot support these communication bursts, UAVs may suffer from large access delay and frequent air-interface packet losses, finally affecting flight safety during formation maneuvers. Therefore, CAD-TDMA is designed as a network mechanism for formation diverge-merge control. Regarding this, the MAC layer should support a large cluster size while keeping communication quality acceptable. Let Nmax denote the maximum cluster size supported by the MAC layer. The objective is: P2 : max Nmax ¯ ≤ ∆th , ℓair ≤ ℓth . s.t. ∆
(21)
¯ is the average packet delay and ℓair is the airwhere ∆ interface loss rate. The air-interface loss rate represents failed MAC-layer delivery caused by simultaneous transmissions, slot conflicts, strong interference, or SINR degradation, and thus reflects the collision and interference risk at the air interface. This objective is feasibility-oriented rather than throughput-maximization-oriented: CAD-TDMA first aims to support the largest feasible cluster size under bounded delay and air-interface loss, while throughput Θ is used afterwards to evaluate slot-resource utilization. Therefore, the ns-3 evaluation in Section VI does not simply compare the maximum achievable throughput, but examines the delay-loss-throughput tradeoff under the same dynamic diverge-merge traces.
(19)
P3 where ∆ = {β : i=1 βi = 1, βi ≥ βmin } and the floor βmin keeps every modality alive. Minimizing J steers the weight toward the modality that currently explains the swarm structure, since a modality that fails to do so inflates its own defect term. As each ϵk depends on β only through the discrete clustering output, J admits no closed-form gradient. We adopt projected gradient descent with a simultaneous perturbation
Fig. 4: Frame structure and representative slot states in CAD-TDMA.
8
The core idea of CAD-TDMA is to distinguish protected intra-cluster access from cautious inter-cluster reuse. Intracluster communication is usually more frequent and more important for diverge-merge synchronization, so same-cluster slots should be protected and not reused. Inter-cluster communication is relatively less coupled, so inter-cluster slots can be reused only when the distance and recent overhearing history indicate low risk. In this way, CAD-TDMA reduces delay and air-interface losses for critical intra-cluster traffic while maintaining effective resource utilization through conservative inter-cluster slot reuse. A. Frame-slot structure and state CAD-TDMA divides time into consecutive frames, and each frame contains Nslot configurable slots indexed by Q = 1, 2, . . . , Nslot . Each UAV maintains one owner slot ωi (t) ∈ Q as its primary reserved transmission opportunity in frame t. The owner slot is applied for reservation announcements, cluster-state control messages, and regular data packets. When the local queue becomes busy, a UAV may occupy low-risk inter-cluster slots for opportunity access. For a single UAV, each slot is classified into one of five states, as shown in Fig. 4. • Own: A slot owned by the node. The node can directly transmit data in this slots. • Reusable: A low-risk inter-cluster slot. The node can occupy it as an opportunity slot when the queue is busy. • Forbidden: An owner slot declared by another node. The node cannot occupy it. • Cooling: An inter-cluster slot with recent risk or insufficient spatial separation. The node should temporarily avoids it. • Idle/Unobserved: A slot without a fresh slot-binding record. It is designed as a candidate for future owner-slot allocation. Therefore, a UAV can transmit only in its Own slot or in a Reusable slot. In Forbidden, Cooling, and Idle/Unobserved slots, the UAV keeps silent and listens to nearby packets. The guard interval between adjacent slots is only used to absorb timing offsets and is not treated as a transmission resource. B. Passive slot-view update To support distributed operation, each CAD-TDMA packet carries a lightweight CAD header between the L2 header and the upper-layer payload, as illustrated in Fig. 5. By passively overhearing ordinary packets, a UAV can decode the CAD header and update its local slot-view records, including the observed slot binding, cluster identity, freshness, and risk state. Therefore, CAD-TDMA does not require a centralized scheduler or an explicit reservation handshake in every frame. The decoded CAD header provides the minimum information needed for local slot-view maintenance. Specifically, it contains five fields: • Type: packet type, such as data transmission, reservation announcement, release notification, or conflict feedback. • EpochId: cluster-state version. It helps discard stale slotbinding records after diverge or merge events. • ClusterId: sender’s current cluster label. It is used to distinguish same-cluster protected slots from inter-cluster reuse candidates.
Fig. 5: Slot diagram of CAD-header-based passive update.
OwnerSlot: sender’s reserved owner slot. Role: sender’s role, such as cluster head, boundary node, or ordinary member. By overhearing CAD headers, a UAV can maintain a local slot view of nearby transmissions. In particular, it can determine which slots are occupied by same-cluster nodes, which slots belong to inter-cluster nodes, and whether the corresponding records are still fresh. In addition, undecodable busy slots, failed acknowledgements, and conflict feedback are recorded as risk evidence. These local observations are then used for next-frame slot classification and allocation. • •
C. Cluster-aware allocation and inter-cluster reuse CAD-TDMA first protects same-cluster slots. Let gi (t) denote the cluster label of node i in frame t, and let ωi (t) denote its owner slot. After overhearing CAD headers, node i builds a same-cluster blocked set: Bi (t) = {ωj (t) | gj (t) = gi (t), j ̸= i, Freshj (t) = 1}, (22) where Freshj (t) = 1 means that the record of node j has a consistent EpochId and has not expired. Node i must select its owner slot outside Bi (t), so same-cluster UAVs do not reuse each other’s reserved slots. This rule prevents UAVs in the same cluster from reusing each other’s reserved slots. Since same-cluster UAVs frequently exchange heartbeat packets, acknowledgements, and cluster-state updates, such protection reduces high-risk simultaneous transmissions and helps lower access delay and airinterface losses. After same-cluster slots are excluded, CAD-TDMA checks whether an inter-cluster slot can be reused. Let Pi (q, t) denote the set of fresh passive overhearing records associated with inter-cluster transmitters on slot q at node i. The distance safety of slot q is evaluated by the minimum distance from node i to the transmitters in Pi (q, t). If no fresh inter-cluster record exists on slot q, the slot is treated as Idle/Unobserved rather than being directly reused. Let τirisk (q) denote the latest frame in which node i observes risk evidence on slot q, and let Tobs be the observation window. The available opportunity-slot set of node i is defined as Ai (t) = q ∈ Q | q ∈ / Bi (t), Pi (q, t) ̸= ∅, min ∥p (t) − p (t)∥ ≥ δ , t − τ risk (q) > T , (23) j∈Pi (q,t)
i
j
reuse
i
obs
9
leaves or changes its cluster epoch, its previous slot binding is removed either by explicit release or by local aging. VI. N UMERICAL S IMULATION
Fig. 6: Distributed CAD-TDMA protocol.
where the first condition protects same-cluster slots, the second ensures that the slot is a known inter-cluster slot rather than an unobserved slot, the third avoids reuse when the intercluster transmitter is too close, and the fourth requires that no recent risk evidence has been observed. A node may select opportunity slots only from Ai (t). Algorithm 3: CAD-TDMA Slot-state Decision Input: Cluster label gi (t), epoch, role, slot set Q Output: Owner slot ωi (t) and opportunity-slot Ai (t) for each frame f do 2 Update local slot view by overhearing CAD headers 3 Remove stale records and update τirisk (q) 4 Build Bi (t) according to (22) 5 if ωi (t) is invalid or ωi (t) ∈ Bi (t) then 6 Select ωi (t) ∈ Q \ Bi (t)
1
7 8 9
10 11
Build Ai (t) according to (23) for each slot q in the next frame do Transmit if q = ωi (t) or q ∈ Ai (t) with a busy queue; otherwise overhear if node i exits or changes epoch then Release or age the previous owner slot
D. Distributed protocol procedure The distributed protocol of CAD-TDMA is summarized in Fig. 6 and Alg. 3. Each UAV maintains a local slot view by overhearing CAD headers in the slots where it does not transmit. At the beginning of each frame, stale records are removed according to the EpochId and aging timer. The node then updates its same-cluster blocked set and evaluates whether inter-cluster slots have sufficient spatial separation and no recent risk evidence. If the current owner slot becomes invalid due to a clusterepoch change or a same-cluster conflict, the UAV selects a new owner slot outside the same-cluster blocked set. For data transmission, the node first uses its owner slot. When the queue is busy, it may occupy slots classified as reusable. In Forbidden, Cooling, and Idle/Unobserved slots, the node remains silent and continues passive listening. When a node
This section presents a comprehensive numerical validation of the proposed dynamic diverge-merge collaborative control framework. The evaluation methodology is structured into two primary components: 1) a kinematic algorithmic validation using a Python-based simulator to assess the topological reconstruction accuracy of a 100-UAV swarm; and 2) a communication-support validation using ns-3 to evaluate the underlying MAC protocol’s capability in supporting highfrequency topology evolution.
A. Diverge-Merge Algorithm Validation To evaluate the proposed framework, we implement a 3D kinematic UAV simulator. The mobility follows the APF-based bounded control model established in Section III, while the communication layer evaluates dynamic SINR using a logdistance path-loss model. The primary simulation parameters are summarized in Table I. TABLE I: Primary simulation parameters Param.
Value
Param.
Value
N Tc amax κ0 Ptx Tw dmerge
100 1s 3 m/s2 60 m/s2 23 dBm 400 s 45 m
∆t vmax d0 Rc α Nmax ddiverge
0.1 s 15 m/s 5m 250 m 2.5 45 90 m
We benchmark the proposed framework against two baselines. The proposed framework executes the complete pipeline equipped with adaptive weights and TD-FPTree task memory. Standard SC represents spectral clustering driven only by spatial and intent similarities (SL and SI ), lacking historical task memory. K-Means serves as the spatial-only baseline, applying standard K-means directly to raw 3D coordinates. To quantitatively capture the utility of the resulting topologies, we define two outcome-oriented metrics based on the ground-truth task groups {Tg }G g=1 and the algorithm-assigned clusters {Ci }N i=1 . First, the Task-Cluster Alignment (TCA) measures the proportion of same-task UAVs successfully grouped into the same macroscopic cluster. It is defined as the ratio of the most frequent cluster label within each task group: G
X 1 X 1 TCA = max I(Ci = c), G g=1 |Tg | c
(24)
i∈Tg
where I(·) is the indicator function. Second, the Task Communication Score (TCS) evaluates the effective data exchange quality among collaborating nodes. Intra-cluster links preserve their full capacity, whereas cross-
10