PaperlayerView exact revision on arXiv

Source-linked AI summary

Service Function Chain Dynamic Scheduling in Space-Air-Ground Integrated Networks

Ziye Jia, Yilu Cao, Lijun He, Qihui Wu, Qiuming Zhu, Dusit Niyato, Zhu Han

arXiv:2502.10731v2cs.NI

TL;DR

Dynamic and heterogeneous SAGINs make resource allocation and multi-task SFC scheduling difficult, especially when urgent tasks compete for limited resources. The paper models these conditions with RTEG, formulates scheduling as an MDP, and applies DRL-based algorithms. Simulations report better convergence and performance than benchmark algorithms, with especially improved results for the proposed method as SFC demand increases.

  • Problem

    Dynamic topology, heterogeneous resources, and unexpected task competition make efficient multi-task SFC scheduling in SAGIN difficult.

  • Method

    The paper uses RTEG for time-varying resource representation, formulates SFC scheduling as an MDP, and designs DRL-based algorithms including VNF state transition.

  • Results

    The proposed DRL-MSSNL-SAGIN algorithm is slightly better than DQN, while both outperform Q-learning and Sarsa as the number of SFCs increases.

  • Takeaways & Limitations

    RTEG and DRL-based scheduling provide an evaluated approach for efficiently scheduling SFCs under SAGIN’s dynamic topology and resource constraints.

Abstract

from arXiv · show

As an important component of the sixth generation communication technologies, the space-air-ground integrated network (SAGIN) attracts increasing attentions in recent years. However, due to the mobility and heterogeneity of the components such as satellites and unmanned aerial vehicles in multi-layer SAGIN, the challenges of inefficient resource allocation and management complexity are aggregated. To this end, the network function virtualization technology is introduced and can be implemented via service function chains (SFCs) deployment. However, urgent unexpected tasks may bring conflicts and resource competition during SFC deployment, and how to schedule the SFCs of multiple tasks in SAGIN is a key issue. In this paper, we address the dynamic and complexity of SAGIN by presenting a reconfigurable time extension graph and further propose the dynamic SFC scheduling model. Then, we formulate the SFC scheduling problem to maximize the number of successful deployed SFCs within limited resources and time horizons. Since the problem is in the form of integer linear programming and intractable to solve, we propose the algorithm by incorporating deep reinforcement learning. Finally, simulation results show that the proposed algorithm has better convergence and performance compared to other benchmark algorithms.

I. INTRODUCTION

The paper addresses resource-allocation and SFC-scheduling challenges caused by SAGIN’s dynamic, heterogeneous multi-layer architecture. It models time-varying resources with RTEG and develops DRL-based scheduling algorithms for maximizing successful SFC deployments.

  • Motivation: SAGIN combines satellites, UAVs, ground stations, and users in a heterogeneous multi-layer network with diverse resources and complex structure.Satellite periodic motion, flexible UAV movement, and unequal node capabilities complicate resource cooperation and utilization.
  • Motivation: NFV decouples network functions from specialized hardware, enabling resource sharing across SAGIN and representing resource allocation through SFC deployment.An SFC is an ordered sequence of VNFs that delivers a specific network service.
  • Challenges: Dynamic topology, unexpected task demands, and heterogeneous node capabilities create difficulties in characterizing resources, avoiding deployment conflicts, and satisfying multiple SFC demands.Urgent tasks can compete for resources and cause task failures.
  • Proposed model: RTEG represents SAGIN resources by dividing the time horizon into slots in which topology is treated as quasi-static, while preserving node states and inter-slot storage.The same physical node can have different states and resource conditions across time slots.
  • Algorithms: The paper formulates SFC scheduling as an ILP to maximize successfully deployed SFCs, transforms it into an MDP, and designs DRL-based algorithms for scheduling.The proposed framework includes mutual SFC-node selection and a VNF state-transition algorithm.
  • Research gap: Prior approaches address terrestrial, single-layer, or SAGIN settings, but existing SAGIN studies insufficiently model topology dynamics across time and rely largely on heuristics.The paper targets multi-layer SAGIN networks and varied task requirements with DRL-based algorithms.

B. SFC Dynamic Scheduling Model

The model represents SFCs as ordered VNFs deployed across satellites and UAVs, then dynamically schedules them over time to respect resource and delay constraints. RTEG-based online scheduling can coordinate competing SFCs so both meet their delay requirements.

  • SFC representation: Each task corresponds to an SFC whose VNFs must execute in sequence across satellites or UAVs.The paper denotes the m-th VNF of task k as f^m_k and requires VNFs to follow their time order.
  • Resource constraints: Per-slot node capacity limits concurrent VNF processing, so arriving VNFs may be stored and incur waiting delay.At time slot 10, a VNF arriving at satellite s2 is stored because another VNF is already being processed there.
  • Offline deployment: The offline deployment can violate latency requirements when resource conflicts delay VNF processing.The described deployment does not complete because processing is not finished within the delay requirement.
  • Online scheduling: Online scheduling stores the first arriving VNF, prioritizes the next SFC’s VNF, and then processes the stored VNF to satisfy both SFC delay requirements.This ordering coordinates F2 and F3 when they reach satellite s2 in successive time slots.
  • Operating assumption: The scheduling illustration assumes tasks can reach nodes within communication distance and that nodes and links do not fail.Under these conditions, all tasks receive a comprehensive SFC scheduling scheme.
  • Communication setting: The SAGIN channel model includes G2U, U2U, U2S, S2S, S2G, and U2G links, with U2S and S2S treated as line-of-sight communication.The model also assumes ground-station-to-UAV communication is line of sight while ignoring small-scale fading and shadowing.

1) Channel Model of G2U and U2G:

The channel model characterizes link quality and achievable rates for heterogeneous SAGIN links. It uses distance, frequency, transmission parameters, antenna and propagation losses, SNR, bandwidth, and channel-specific effects such as rain attenuation.

  • G2U and U2G: The G2U channel gain is modeled from the link distance between a UAV and a ground station and their horizon locations.The associated SNR uses the transmission powers of the ground station and UAV together with a reference SNR.
  • U2U: The U2U path-loss model depends on UAV separation distance and carrier frequency, while its SNR uses transmission and noise powers.The passage identifies d^t_uu as the distance between two UAVs and f_uu as the frequency.
  • Data rate: Available link data rates are computed from transmission power, bandwidth, and SNR across the modeled channel types.The bandwidth and SNR sets include G2U, U2U, U2G, and S2G links.
  • Propagation parameters: The rate model accounts for antenna gains, total line loss, required received energy-per-bit ratio, system noise temperature, and maximum slant range.The formulation also includes centering frequency and free-space-related loss terms.
  • S2G: S2G channel quality incorporates atmospheric precipitation through rain attenuation obtained from ITU-R P.618-12.Meteorological satellites are used to predict the S2G channel state.

D. Energy Cost Model

The UAV energy model accounts for energy used in movement, hovering, and communication. It combines motion-related parameters with transmitted data and power to represent UAV path and communication costs.

  • Energy components: UAV energy consumption includes hovering, movement, and communication components.These are identified as the primary energy-consuming activities for UAVs.
  • Movement and hovering: The movement model uses UAV speed, maximum speed, maximum-speed power, and hovering power.These parameters support the formulation of UAV movement and hovering energy.
  • Propulsion model: The UAV propulsion formulation includes environmental parameters, UAV mass, propeller count, and geographical position.The environmental terms include earth gravity acceleration, air density, and an environmental parameter expressed as g^3/(2πϑ).
  • Communication energy: UAV communication energy depends on transmitted power and the data amount of each SFC.The passages identify transmitted power and SFC data amount as inputs to communication energy cost.

2) Energy Cost of Satellites:

The satellite energy model separates communication-related transmission and reception costs from general operating energy. It accounts for link-specific transmitter and receiver costs across satellite-connected links.

  • Communication energy: Satellite energy consumption is primarily associated with data transmission and reception.The model distinguishes transmitter and receiver energy costs for satellite communication.
  • Link-specific costs: The model identifies received powers for U2S and S2S links and transmitted powers for S2S and S2G links.These link-specific powers support the satellite communication energy formulation.
  • Operational energy: Total satellite energy consumption also includes a general operation energy cost.This term is separate from the communication-related transmitter and receiver costs.

A. Constraints

The SFC deployment model represents node, link, storage, and successful-deployment decisions with binary variables, while enforcing sequential VNF placement and flow conservation. These constraints ensure that each SFC follows a valid deployment path and occupies resources consistently over time.

  • Deployment variables: Binary variables indicate VNF placement, successful SFC deployment, and link usage within the deployment model.Each VNF is assigned to a node, while Ik indicates whether all VNFs of SFC Fk are successfully deployed.
  • Sequential deployment: VNFs in each SFC must be deployed sequentially, with each VNF assigned a processing time slot and resource requirement.The model associates VNF processing with node computation capability and required computing resources.
  • Flow constraints: Flow conservation constraints enforce valid SFC paths at the start, intermediate, and destination nodes.Equations (20a), (20b), and (20c) correspond respectively to flow constraints at start, intermediate, and end nodes.
  • Time-slot states: At each time slot, an SFC can be deployed on a node, transmitted on a link, or stored on a node.The model uses these mutually exclusive states to represent SFC progress through the network.
  • Resource constraints: The total computing resource allocated to deployed SFCs cannot exceed node computation capacity.This constraint limits aggregate SFC computation demand on each node.

4) Resource Constraints:

Resource constraints limit aggregate computation, storage, channel use, and energy consumption during SFC deployment. They also enforce the maximum tolerable deployment delay for every SFC.

  • Resource capacities: UAV and satellite nodes have distinct resource capacities that bound SFC allocation.The model distinguishes the resource capacities of UAVs and satellites.
  • Storage constraints: Waiting SFCs consume node storage, so stored data cannot exceed each node’s storage capacity.SFCs waiting for processing remain subject to storage-capacity constraints.
  • Channel constraints: Transmission demands from SFCs must satisfy the channel-capacity restriction of the links they use.The restriction applies when SFCs with different data amounts transmit over diverse links.
  • Energy constraints: Total energy consumption cannot exceed the network energy capacity, including transmission and computation costs.Computation energy is modeled separately for UAV and satellite nodes.
  • Delay constraints: The deployment time of each SFC cannot exceed its maximum tolerable delay Dmax.Deployment delay includes VNF processing and transmission delay.

5) Delay Constraints:

The model tracks VNF processing and transmission delays while optimizing successful SFC deployment under limited time. Its optimization objective is difficult to solve directly, motivating an MDP and DRL-based scheduling approach.

  • Delay components: SFC deployment delay includes VNF processing delay and transmission delay.These delay components determine the time cost of deploying each SFC.
  • Optimization objective: The optimization objective maximizes the number of successfully deployed SFCs.The objective is represented as an integer linear programming problem.
  • Problem solution: The formulated ILP is difficult to solve within limited time complexity, so the paper designs efficient DRL-based algorithms.The optimization problem is described as intractable to solve directly.
  • MDP transformation: The SFC scheduling problem is transformed into an MDP with states, actions, transitions, rewards, and a discount factor.The MDP formulation provides the basis for learning a scheduling policy.
  • State representation: System states capture SFC status and resource occupancy across SAGIN nodes at the beginning of each time slot.The SFC state includes its index, pending VNF, and previously selected node, while node states represent occupied resources.

2) Action:

The action and learning design selects nodes for SFCs over time, updates their states and rewards, and uses DDQN to learn scheduling policies in the dynamic SAGIN setting. Experience replay and separate online and target networks are used to stabilize training.

  • 2) Action: Each SFC action selects the node it will use in the current time slot.The joint action set contains one node-selection action for every SFC.
  • State transition: Node selections determine the next pending-VNF state based on transmission and remaining processing time.The transition accounts for channel transmission time and the processing time remaining for the current VNF.
  • Reward: The immediate reward penalizes ineffective time consumption, including transmission and waiting time.Weighting coefficients adjust the reward and the relative weights of transmission and waiting time.
  • B. DRL-based Algorithm: DDQN is used because DQN Q-values may fluctuate during training and fail to converge to the optimal solution.DDQN uses online and target networks to stabilize performance through delayed target updates.
  • Training process: Experience replay randomly samples batches to reduce training-sample correlation and avoid local minima.The replay memory stores transitions containing states, actions, rewards, and next states.
  • Dynamic scheduling: DDQN adjusts deployment schemes as SAGIN node distances and network conditions change across time slots.This addresses short-sighted deployment decisions caused by the network’s dynamic nature.
  • Mutual selection: When multiple SFCs select one node, the algorithm orders them by data size and admits them according to remaining node resources.The mutual-selection procedure updates the affected SFC states and node utilization.

C. Complexity Analysis

The algorithms use a DDQN-based deep reinforcement learning procedure to schedule SFCs, with state transitions handling shared-node competition and complexity determined by training, network, and node dimensions.

  • Complexity analysis: The forward-propagation complexity is O(S · A · PM−1 i=1 WiWi+1), where S and A denote state and action sizes.The expression depends on the widths of adjacent neural-network layers.
  • Algorithm procedure: Algorithm 1 initializes DDQN networks, replay memory, and system state, then selects SFC actions with an ϵ-greedy policy across time slots.The procedure obtains next pending states and VNF states before calculating rewards and updating the target network.
  • VNF state transition: The VNF transition algorithm separates UAV and satellite actions and updates node resources when multiple SFCs select the same node.Remaining SFCs are sorted by data amount and selected according to available computing resources.
  • Complexity analysis: The total computational complexity is O(D · P · (K · S · A · PM−1 i=1 WiWi+1 + I)), incorporating episodes, steps, SFCs, state-action sizes, layer widths, and nodes.Here D and P are the numbers of episodes and steps, K is the number of SFCs, and I is the number of nodes.

A. Simulation Setups

Simulations evaluate training settings, network scale, and benchmark algorithms for SFC scheduling in a SAGIN scenario with 30 UAVs and 2 satellites. The proposed method performs especially well as SFC and network scales increase.

  • Simulation environment: The simulation scenario contains 30 UAVs and 2 satellites, with UAVs randomly arranged on a 400 m-radius circle and separated by at least 20 m.Experiments use an Intel i9-10940X CPU, 64 GB RAM, and two GeForce RTX 3090 GPUs.
  • Simulation parameters: The DRL network uses three hidden layers with 64, 32, and 32 neurons, ReLU activation, Adam optimization, learning rate 0.001, discount factor 0.9, and 3,000 episodes.Each episode allows up to 100 time slots.
  • Training parameters: A learning rate of 0.001 produces superior rewards and deployment results, while learning rate 0.05 gives the worst, unstable convergence.The paper attributes poor behavior at large or small rates to local-optimum trapping and selects 0.001 for subsequent simulations.
  • Training parameters: The Adam optimizer converges quickly and smoothly and performs relatively well on the optimization objective, so it is selected for subsequent simulations.Adadelta rewards continue growing without converging quickly enough.
  • Training parameters: Three hidden layers provide an efficient configuration: one or two converge slowly, while four have similar results but increase training time.The selected structure is 64, 32, and 32 neurons.
  • Scale effects: When SFCs reach 400, increasing UAV quantity rapidly increases successful deployments, showing that scheduling outcomes depend on network scale.With fewer SFCs, adding UAVs has little effect on successful deployments.
  • Algorithm comparison: At 400 SFCs, DRL-MSSNL-SAGIN achieves more than twice the optimization result of Q-learning and Sarsa, with resource utilization approximately 15% above Sarsa and 20% above Q-learning.The proposed algorithm is slightly better than DQN and performs better than Q-learning and Sarsa as network and task scales grow.
Loading 2502.10731v2…