PaperlayerView exact revision on arXiv

Source-linked AI summary

Traffic-Adaptive Per-Hop Multipath Routing in Multi-Hop UAV Networks

Zhenyu Zhao, Tiankui Zhang, Xiaoxia Xu, Yuanpeng Zheng, Junjie Li, Wenjuan Xing

arXiv:2608.25383v1cs.NI

TL;DR

Heterogeneous traffic and rapidly changing UAV links limit conventional end-to-end multipath routing, motivating adaptive per-hop traffic splitting. The paper formulates this problem as a Dec-POMDP and solves it with MAPPO-DM, which achieves the best overall performance and robust latency and loss outcomes across tested conditions.

  • Problem

    Heterogeneous task traffic and changing UAV links make predefined end-to-end multipath paths less responsive in dynamic multi-hop UAV networks.

  • Method

    The paper proposes traffic-adaptive per-hop multipath routing, formulates it as a Dec-POMDP, and solves it with MAPPO-DM using continuous Dirichlet-modeled traffic-splitting actions.

  • Results

    MAPPO-DM achieves the best overall performance among compared schemes and maintains better latency guarantees and lower packet loss under different network loads, UAV scales, and forwarding constraints.

  • Takeaways & Limitations

    Per-hop traffic splitting provides an adaptive routing approach for heterogeneous computation-task traffic in dynamic multi-hop UAV networks.

Abstract

from arXiv · show

In uncrewed aerial vehicle (UAV)-relayed mobile edge computing (MEC) networks, computation tasks generate traffic with diverse latency requirements and data sizes. Routing decisions therefore need to adapt to both traffic characteristics and changing network conditions. Compared with single-path routing, multipath routing is better suited to such heterogeneous traffic because it provides multiple forwarding options and enables flexible traffic splitting. However, conventional multipath routing usually splits traffic over predefined end-to-end paths, making it difficult to respond quickly to link fluctuations and topology changes in UAV networks. To address this issue, we propose a traffic-adaptive per-hop multipath routing method for multi-hop UAV networks, in which each UAV dynamically distributes traffic among multiple candidate next hops. We formulate the routing problem to improve the on-time packet delivery ratio while reducing the packet loss ratio, and model it as a decentralized partially observable Markov decision process (Dec-POMDP). To solve this problem, we develop a multi-agent reinforcement learning (MARL) algorithm, termed Multi-Agent Proximal Policy Optimization with Dirichlet Modeling (MAPPO-DM). MAPPO-DM follows the centralized-training-and-decentralized-execution framework and models continuous traffic-splitting actions using a Dirichlet distribution. Simulation results show that MAPPO-DM outperforms the baseline methods and maintains robust performance under various network conditions.

I. INTRODUCTION

Multi-hop UAV routing must handle heterogeneous traffic, changing topology, and limited resources. The paper addresses these challenges with traffic-adaptive per-hop multipath routing and MAPPO-DM.

  • Heterogeneous task traffic, frequent topology changes, and limited network resources make reliable multi-hop UAV transmission challenging.
  • Existing routing schemes include protocol-based methods with predefined rules and learning-based methods that adapt decisions to changing network conditions.
  • Conventional multipath routing relies on predefined end-to-end paths, whereas per-hop routing dynamically splits traffic among next hops using current link and traffic conditions.
  • Per-hop routing couples next-hop selection with traffic assignment, creating a large decision space and making efficient policies difficult to obtain.
  • The proposed method uses local network and traffic information, formulates routing as a Dec-POMDP, and solves it with MAPPO-DM.
  • MAPPO-DM combines a Transformer and GRU in decentralized Actors, Dirichlet traffic-splitting actions, and graph attention in the centralized Critic.

1) Communication Model:

The communication model represents UAV links through channel, interference, and reachability conditions. Candidate next hops are selected and ranked by transmission reliability and geographic progress toward the GBS.

  • Inter-UAV communications use a line-of-sight channel model based on time-varying distances and reference-distance channel gain.
  • Each UAV equally divides its transmit-power budget across at most N candidate UAV links and one direct GBS link.
  • Interference from transmissions sharing a sub-band is incorporated into the SINR for UAV-to-UAV and UAV-to-GBS links.
  • Reachable neighbors must satisfy the minimum SINR and be geographically closer to the GBS, preventing routing loops.
  • Reachable neighbors are ranked by geographic forwarding score, with higher scores indicating greater progress relative to forwarding distance.
  • A direct UAV-to-GBS link is available only when its elevation angle meets the minimum threshold, and its rate follows the bandwidth-weighted logarithmic SINR expression.

2) Queueing Model:

The queueing model uses finite-capacity, priority-aware queues and forwards selected packets directly or by splitting them across candidate next hops, subject to link and buffer constraints.

  • Queue organization: Each UAV has a finite-capacity communication buffer with three sub-queues for high-, medium-, and low-priority traffic.Traffic is placed according to deadline urgency.
  • Queue selection: At each time slot, a UAV selects the highest-priority nonempty sub-queue for packet forwarding.The selected queue’s priority level and length characterize the forwarding decision.
  • Direct forwarding: If a direct GBS link exists, packet delivery is limited by the UAV-to-GBS link capacity.Packets that cannot be transmitted in the current slot remain queued for later transmission.
  • Multipath forwarding: Without a direct GBS link, the UAV splits selected packets among multiple candidate next hops and may retain some locally.Splitting ratios are bounded between 0 and 1 and include a local-retention component.
  • Transmission constraints: Successful transmissions are constrained by intended allocation, link capacity, and receiver-buffer availability; packets failing admission are dropped.The model explicitly records dropped packets and receiver-side congestion effects.
  • Performance metrics: Evaluation considers flows whose deadlines occur within the flight duration and reports packet loss and on-time packet delivery ratios.Packets never reaching the GBS are assigned an infinite arrival time.

B. Problem Formulation

The problem formulation targets traffic-adaptive per-hop routing that jointly improves on-time delivery and reduces packet loss, using local observations of traffic, neighbors, link conditions, and congestion.

  • B. Problem Formulation: The optimization objective jointly improves on-time packet delivery ratio and reduces packet loss ratio over all UAV routing decisions.The action set includes traffic-splitting decisions across the flight duration.
  • B. Problem Formulation: Traffic-splitting ratios are constrained to [0, 1] and must sum to one.Additional constraints limit transmissions by link capacity, packet allocation, and receiver-buffer space.
  • A. Dec-POMDP Formulation: The sequential multi-UAV problem is modeled as a Dec-POMDP with global states, local observations, local actions, state transitions, and a shared reward.Each UAV acts from partial local information while the environment evolves after joint actions.
  • 1) Observation Space:: Each local observation includes traffic information and candidate-neighbor information.Traffic features represent selected-packet volume and delay urgency, with greater urgency values indicating more urgent forwarding.
  • 1) Observation Space:: Candidate-neighbor information accounts for dynamic candidate-set size, sorted neighbor identities, geographical progress, link validity, capacity-demand matching, and receiver buffer space.Neighbor features are zero-padded when fewer than N candidates exist.
  • 1) Observation Space:: Link-quality estimates use historical receiver-side interference measurements to approximate current interference and communication capacity without additional pre-forwarding signaling.An EWMA estimate gradually reverts toward a default interference level as measurements become outdated.
  • 1) Observation Space:: The observation design also includes candidate-link validity, capacity-demand matching, receiver buffer availability, and potential incoming-neighbor congestion.These features describe whether links can accommodate the selected traffic and how many UAVs may transmit simultaneously.

2) State Space:

The state space represents the dynamic UAV network as a graph whose node and edge features encode roles, queues, traffic, topology, forwarding direction, and link conditions.

  • 2) State Space:: The global network state is a graph with UAV nodes and forward, reverse, and self-loop edges.Reverse edges inherit forward-edge features with an inverted direction indicator, while self-loop features are zero.
  • 2) State Space:: Node features include direct-GBS connectivity, UAV role, queue occupancy, available buffer, flow urgency, selected-packet count, neighbor counts, and traffic-generation probability.Role information distinguishes hotspot, gateway, relay, and regular UAVs.
  • 2) State Space:: Forward-edge features encode direction, geographical progress, estimated and actual capacities, receiver buffer space, and actual SINR.These features describe both routing progress and communication conditions.
  • 2) State Space:: Continuous features are normalized by their physical ranges and clipped when necessary for numerical stability during training.The state representation therefore combines graph structure with normalized node and link information.

3) Action Space:

The action space represents each UAV’s per-hop traffic split, while the reward combines forwarding progress, capacity fit, congestion, packet loss, holding behavior, and network-wide deadline outcomes.

  • 3) Action Space:: Each UAV divides selected packets among neighbors or retains them locally using a normalized action vector.The local-retention component is indexed by zero, while other components correspond to sorted candidate neighbors.
  • 4) Reward Function:: The local routing reward combines geographic progress, capacity satisfaction, congestion risk, and packet-loss penalties.The packet-loss term applies a sharper penalty at high loss ratios.
  • 3) Action Space:: Only UAVs with packets awaiting forwarding, at least one candidate next hop, and no direct GBS link make active routing decisions.Inactive UAVs receive no active-decision indicator.
  • 4) Reward Function:: For nonlocal forwarding, each action component is paired with the corresponding next hop and its local forwarding reward.The reward terms are weighted by progress, congestion, and loss coefficients.
  • 4) Reward Function:: Forwarding progress is rewarded when a decision advances packets toward the GBS while providing sufficient capacity and successfully delivering them to the next hop.Congestion penalties discourage links that cannot support the intended forwarding load.
  • 4) Reward Function:: Holding packets is penalized when aggregate downstream capacity can accommodate the selected traffic, but not when holding is otherwise necessary.The penalty increases for more urgent traffic.
  • 4) Reward Function:: A shared event reward incorporates packets arriving at the GBS on time and penalties for packets missing their deadlines.When valid UAVs exist, the global event reward and penalty are distributed among them.

B. The Proposed MAPPO-DM Algorithm

MAPPO-DM uses decentralized Actors to encode local neighbor interactions, temporal network changes, and traffic conditions, then models continuous per-hop traffic splitting with a Dirichlet policy.

  • Decentralized Actor Design: The decentralized Actor is shared across UAV agents and combines neighbor-set encoding, recurrent temporal modeling, traffic-conditioned scoring, and Dirichlet concentration estimation.It operates within centralized training and decentralized execution.
  • Decentralized Actor Design: A Transformer encodes interactions among candidate next hops, masking invalid neighbor positions without positional encoding.Identifier-based neighbor ordering aligns neighbor features with action components.
  • Decentralized Actor Design: A GRU preserves temporal information by updating its hidden state from contextualized neighbor summaries, while an MLP encodes traffic features into the decision context.The temporal state and traffic embedding are concatenated before action scoring.
  • Decentralized Actor Design: The Actor scores each candidate action, including an always-available holding action, and uses masked softmax to form a valid mean traffic-splitting preference.Invalid neighbor positions receive zero probability, and valid components sum to one.
  • Decentralized Actor Design: The continuous traffic-splitting vector is sampled from a Dirichlet distribution whose mean determines allocation and whose concentration controls exploration.The concentration is constrained between κmin and κmax; larger values stabilize splitting, while smaller values encourage exploration.
  • Decentralized Actor Design: During training, sampled actions support stochastic exploration and PPO evaluation, whereas deterministic execution uses the mean traffic-splitting vector.Invalid padded action components are set to zero.

2) Centralized Critic Design:

The centralized Critic estimates UAV state values from global graph and traffic information using edge-aware graph attention, attention pooling, and a value prediction head.

  • Centralized Critic Design: During training, the Critic takes the global graph state and traffic features to estimate an individual state value for each UAV.Its components include node encoding, edge-aware multi-head graph attention, global attention pooling, traffic encoding, and value prediction.
  • Centralized Critic Design: Node features are encoded before graph attention layers process multi-hop node and edge information.The graph attention network uses multiple layers and attention heads.
  • Centralized Critic Design: For each directed edge, receiver nodes provide Queries while sender nodes and edge features provide Keys and Values for attention.Attention scores are normalized over incoming neighbors of each receiving node.
  • Centralized Critic Design: The resulting attention weights capture both node-state compatibility and link attributes.Multi-head outputs are combined through projection, residual connections, and LayerNorm.
  • Centralized Critic Design: Attention pooling assigns importance scores to UAVs and produces a global graph representation.This representation is combined with node and traffic representations before value prediction.

3) Experience Collection and Policy Optimization:

MAPPO-DM collects joint UAV trajectories, estimates advantages with GAE, and updates its Actor and Critic using PPO objectives with policy and value stabilization mechanisms.

  • Experience Collection and Policy Optimization: Each UAV samples a Dirichlet routing action from its local observation, records its action log-probability, and receives an immediate reward after joint execution.The experience stores graph state, observations, actions, old log-probabilities, and rewards.
  • Experience Collection and Policy Optimization: The Actor replays observations in temporal order, recomputes Dirichlet parameters, evaluates stored actions, and includes Dirichlet entropy in policy updating.This reconstructs recurrent hidden states during optimization.
  • Experience Collection and Policy Optimization: After each episode, the Critic computes reference values and GAE recursively estimates advantages using temporal-difference errors.The discount factor γ and GAE parameter λ control the temporal estimation.
  • Experience Collection and Policy Optimization: PPO updates the Actor with a clipped surrogate objective and entropy regularization over valid routing-decision samples.The policy clipping threshold is ε1, and ℘ controls entropy regularization strength.
  • Experience Collection and Policy Optimization: The Critic uses value clipping and a one-step temporal-difference target to stabilize value-function training.The clipped value estimate uses threshold ε2.
  • Experience Collection and Policy Optimization: Training collects complete trajectories over Tmax time slots and repeatedly performs PPO updates using the stored experience.The procedure updates Actor and Critic parameters for Nupd iterations per trajectory.

C. Computational Complexity and Practical Feasibility

The Actor is designed for decentralized deployment with per-UAV forward computation, lightweight neighbor information exchange, and asynchronous updates that avoid strict global synchronization.

  • Computational Complexity and Practical Feasibility: Online Actor inference consists mainly of MLPs, a Transformer encoder, and a GRU.Only the shared Actor is required by each UAV during deployment.
  • Computational Complexity and Practical Feasibility: The Transformer processes N + 1 neighbor and summary tokens, while neighbor encoding is evaluated for N candidate neighbors.The Transformer cost includes token-interaction terms dependent on N.
  • Computational Complexity and Practical Feasibility: MAPPO-DM training repeatedly collects trajectories, computes reference values and advantages, and updates Actor and Critic parameters.Algorithm 1 samples Dirichlet actions from Actor-produced concentration parameters at each time slot.
  • Computational Complexity and Practical Feasibility: The online complexity scales as O(NCfnei + CTr + Cfproj + CGRU + Cftraf + Cfctx + (N + 1)Cfscore + N) per UAV per time slot.The scoring network evaluates N + 1 action components, followed by an O(N) masked Softmax.
  • Computational Complexity and Practical Feasibility: Deployment exchanges lightweight neighbor information such as identifiers, positions, queue states, interference estimates, and timestamps.Information can be exchanged asynchronously and refreshed on demand.

IV. NUMERICAL RESULTS

The numerical evaluation uses a three-dimensional UAV network and heterogeneous task traffic to assess routing reliability and robustness across varying conditions.

  • The simulations evaluate routing schemes under different traffic loads, UAV network scales, and candidate-neighbor limits.On-time packet delivery ratio and packet loss ratio are the main reliability and robustness metrics.
  • The simulated environment covers a 1200 m × 1200 m horizontal area with UAVs moving in three dimensions under a Gauss–Markov mobility model.UAV coordinates span x, y ∈[−600, 600] m and z ∈ [0, 100] m.
  • Heterogeneous traffic is modeled through hotspot, regular, relay, and gateway UAV roles with distinct task-generation probabilities.Tasks contain 1.0–2.0 MB of data, use 1500-Byte packets, and have routing deadlines of 8–14 s.
  • MAPPO-DM is implemented in PyTorch with AdamW optimization, cosine learning-rate annealing, and an initial learning rate of 1×10−5.The minimum learning rate is 1 × 10−6 and weight decay is 1 × 10−3.
  • Additional environment and algorithm settings, including baseline and ablation implementation details, are provided in the released source code.

2) Benchmark Algorithms:

The evaluation compares MAPPO-DM with single-path, heuristic multipath, and end-to-end-path-guided methods across traffic, topology, and forwarding constraints. MAPPO-DM achieves the best overall balance of timely delivery and packet loss, while adapting robustly to changing conditions.

  • Benchmark Algorithms: The benchmarks include one priority-aware single-path method, two heuristic per-hop multipath methods, and one I-AOMDV-guided per-hop multipath method.Performance comparisons are averaged over 50 independent runs for each environment setting.
  • Ablation Variants: The ablations remove or replace the Graph Critic, Transformer neighbor-interaction module, or adaptive Dirichlet concentration estimation.The fixed-concentration variant sets κ at 30.
  • A. Performance Evaluation: All methods gradually increase rewards and stabilize during training, indicating stable convergence.Figures 4 and 5 compare convergence and the two routing metrics for MAPPO-DM and its ablations.
  • A. Performance Evaluation: 96.40% on-time packet delivery and 0.48% packet loss are achieved by MAPPO-DM, which provides a better balance than its ablations.The w/o µ-κ Dirichlet variant reaches 96.70% delivery but 1.78% packet loss, while MAPPO-DM and w/o Graph Critic both achieve 0.48% loss.
  • A. Performance Evaluation: At the deadline, MAPPO-DM reaches about 96% cumulative packet arrival, compared with about 90% for Equal-Split and about 88% for Capacity-Aware Per-Hop Multipath.Priority-Aware Greedy Single-Path reaches about 45%, while MAPPO-DM nearly reaches 98% after the deadline.
  • A. Performance Evaluation: As hotspot regions increase, all algorithms deliver fewer packets on time and lose more packets, but MAPPO-DM remains best and degrades more slowly.This tests robustness under increasing traffic load.
  • A. Performance Evaluation: With approximately constant aggregate traffic, denser networks generally improve multipath performance until additional forwarding options provide limited benefit.I-AOMDV-Guided Per-Hop Multipath eventually degrades as periodic end-to-end path information becomes harder to maintain.
  • A. Performance Evaluation: When candidate forwarding nodes increase beyond four, Capacity-Aware Per-Hop Multipath suffers lower on-time delivery and higher packet loss because downstream conditions are not considered.MAPPO-DM improves slightly from N = 1 to N = 2 and then remains nearly unchanged, showing low sensitivity to the forwarding limit.
Loading 2608.25383v1…