IEEE TRANSACTIONS ON MOBILE COMPUTING
1
Aidos: A Hybrid Optimization Algorithm for Beam Hopping Scheduling in NGSO Mega-Constellations
arXiv:2606.14151v1 [cs.NI] 12 Jun 2026
Lingkai Zhao, Zhe Chen, Member, IEEE, Kun Qiu, Senior Member, IEEE, and Yue Gao, Fellow, IEEE
Abstract—With the rapid proliferation of non-geostationary orbit (NGSO) mega-constellations, beam hopping (BH) has become indispensable for resource scheduling in multi-satellite, multicoverage scenarios. By dynamically adjusting spot beam power and pointing within each time slot, BH enables highly efficient spectrum utilization. A principal engineering challenge is the real-time generation of beam hopping time plans (BHTP). Traditional algorithms, such as the round-robin strategy, distribute beams evenly across all service cells in a round-robin fashion. However, real traffic follows a long-tail distribution; the most active 10% of hotspot cells generate more than 50% of the aggregate demand, making uniform allocation inadequate. To address this issue, existing frameworks adopt a genetic algorithm (GA), whose throughput is approximately 80.7% higher than the traditional baseline. Operational satellite footprints encompass more than 1,000 service cells. The GA requires 67.8 s to generate a BHTP for 1,127 cells. With a 550 km LEO satellite providing only a 300 s visibility window, multiple online recomputations are impractical. State-of-the-art algorithms, such as multi-agent deep reinforcement learning (MADRL), fail to converge once the cell count exceeds 200. To overcome these challenges, we propose a novel BH scheduling algorithm Aidos. The algorithm integrates traffic-aware random-key encoding into a multi-objective metaheuristic search, and then applies a sliding-window Beta resampling strategy during adaptive distribution evolution, to improve both the search efficiency and the solution quality of the BHTP. Experiments demonstrate that Aidos improves throughput by 79.2% and reduces latency by 99.45%. Its average computation time is 9.3 s, enabling online replanning within a 300 s satellite overpass window. Index Terms—beam hopping scheduling, multi-objective optimization, PSO, real-time resource management, NGSO.
I. I NTRODUCTION
W
ITH the rapid growth of non-geostationary orbit (NGSO) mega-constellations such as Starlink, OneWeb, and Kuiper, on-demand resource scheduling and interference mitigation under high mobility and multi-coverage conditions have become essential [1] [2]. To address these challenges, standardization bodies including 3GPP Releases 17/18/19 and DVB-S2X have advanced phased-array-based beam hopping (BH) technology [3] [4]. At the timeslot scale, BH reconfigures the pointing direction and transmit power of multiple spot beams in a time-division manner, focusing on hotspot cells as needed and reducing idle capacity in low-load This work was sponsored by Natural Science Foundation of Shanghai under Project No. 25ZR1402021. (Corresponding author: Kun Qiu.) Lingkai Zhao, Zhe Chen, Kun Qiu and Yue Gao are with the School of Computer Science, Fudan University, Shanghai 200438, China, and also with the Institute of Space Internet, Fudan University, Shanghai 200438, China (e-mail: [email protected]; [email protected]; [email protected]; [email protected]).
regions. With appropriate dwell time and scheduling, BH can significantly increase system capacity [5]. A critical challenge in deploying BH technology is the realtime generation of an optimal beam hopping time plan (BHTP) [4]. In multi-satellite cooperative scenarios, the goal of BH scheduling is to maximize throughput and minimize latency while meeting engineering constraints such as interference limits and revisit time. The resulting optimization problem is a non-convex nonlinear mixed-integer programme [6], proven to be NP-hard [7]. The decision-space size grows approximately with the product of cells, beams, time slots, and satellites. For example, a single Starlink satellite can cover about 1,000 cells [8]. Multi-satellite cooperation increases the problem scale to 103 -104 , which substantially raises computational cost and solution difficulty. The core task of a BHTP is to compute an onboard resource allocation scheme that includes carrier frequency, transmit power, beam index and time slot, in order to satisfy the traffic demands of terrestrial cells. In practical implementations, the most straightforward approach is the round robin strategy [9]. Uniform allocation cannot track spatial demand heterogeneity. Hotspots receive insufficient resources and low-load cells waste capacity, which reduces aggregate throughput. To enhance system performance, prior studies have explored metaheuristic search algorithms such as the multi objective genetic algorithm (MOGA-BH) [10] and the artificial bee colony algorithm [11]. These methods, however, typically optimize only a single objective and report solely offline results, without fully accounting for real-time applicability. Experimental results show that MOGA-BH improved throughput by approximately 80.7% over the conventional baseline in a 1,127-cells scenario. However, generating a single BHTP still required 67.8 s, which is impractical for operational systems. The state-of-the-art method adopts a multi-agent deep reinforcement learning (MADRL) approach, in which each satellite employs a policy trained with the QMIX algorithm to collaboratively generate real-time BH decisions [12] [13]. This MADRL framework achieves millisecond-level inference latency and schedules beams effectively, but it has been validated only in a scenario with 76 ground cells. In large-scale LEO constellations, however, a single satellite may cover thousands of cells and is equipped with 48 independent downlink beams [8]. As the numbers of cells and beams surge, the action space grows exponentially, triggering the curse of dimensionality. Experimental results show that when the number of cells exceeds 200, gradient vanishing occurs and the model fails to learn effective policies. Consequently, such MADRL methods are unsuitable for large-scale LEO satellite scenarios.
IEEE TRANSACTIONS ON MOBILE COMPUTING
To overcome the above limitations and generate BHTP under realistic NGSO constellation coverage, we propose Aidos. The algorithm takes real traffic as input and outputs an executable BHTP. Motivated by the high-dimensional and discrete nature of BHTP, we design a traffic-aware random-key encoding that embeds discrete traffic demands into a continuous key space. Building on this representation, we construct a multi-objective metaheuristic search that jointly optimizes throughput, delay, and fairness. We further introduce a slidingwindow Beta resampling strategy to accelerate convergence and improve solution quality. Our evaluation indicates that Aidos outperforms MOGA-BH and MADRL-BH by 79.2% and 247.2% in throughput, respectively, while reducing latency by 99.45%. Its average computation time is 9.3 s, enabling online replanning within a 300 s satellite overpass window. Briefly speaking, this paper makes the following contributions: • We propose Aidos, an improved metaheuristic search algorithm. The algorithm can be used for computing BHTP in large-scale scenarios. • We design a traffic-aware random-key encoding to handle discrete traffic inputs and build a multi-objective metaheuristic search to compute the optimal BHTP. In addition, we introduce sliding-window Beta resampling and multi-scale perturbation to accelerate convergence and improve the quality of the optimal solution. • The proposed algorithm is evaluated from four perspectives: overall performance, convergence behavior, scalability and computation time. Comparative results against multiple baseline algorithms confirm that Aidos achieves superior throughput and delay performance. Moreover, the framework supports online computation in large-scale scenarios. The rest of the paper is organized as follows: Section II introduces the background of beam hopping scheduling. Section III demonstrates the overview design of Aidos. Section IV describes the detailed design of the core modules in Aidos. Section V evaluates Aidos and analyzes the evaluation results. Finally, Section VI concludes.
2
fields defined in Annex E of DVB-S2X, and then forwarded to the satellite over the feeder link. • On-board execution layer: A digital beam-former dynamically adjusts the antenna, switching the beam pointing direction and transmit power in real time according to the BHTP. NGSO satellites
t = t0
h dc
n
Cell 1 Cell 2
ls
ne
an
cell traffic queues
e tat
tra
...
ca ffi
Feeder link
Cell N
TP
BH BHTP
Network Control Center (NCC)
Gateway Station (GW)
Illumination pattern varies across time slots
Time slot 1
Time slot 2
Time slot 3
t
Fig. 1: Three layers of BH systems: ground planning layer, airinterface signalling layer and on-board execution layer.
B. Beam Hopping Time Plan (BHTP) In a pre-scheduled DVB-S2X BH system, several beam hopping traffic channels (BHTC) run in parallel and repeat periodically to serve different cell clusters. Each BHTC illuminates the cells in its cluster according to a beam hopping time plan (BHTP). A BHTP specifies, for every time slot in one complete hopping period, two items: 1) the cell to be illuminated and 2) its dwell time [4]. For simplicity, we set the dwell time equal to the slot length [14]. Thus, the BHTP fully describes the slot-by-slot illumination sequence. After a satellite receives a BHTP from the gateway, it executes the table in a loop until a new BHTP arrives. Fig. 2 shows the detailed structure of a BHTP.
II. BACKGROUND
Beam_1 Beam_2 Beam_3 Beam_4
A. Beam Hopping (BH)
Slot_1
Beam hopping (BH) is a time-division satellite resourcescheduling technique. Using phased-array antennas, a satellite steers a limited set of high gain spot beams to different ground cells in successive time slots to match the spatial traffic distribution. Compared with fixed multibeam systems, BH concentrates spectrum and amplifier power on hotspot areas while reducing idle capacity in lightly loaded regions, thereby improving instantaneous throughput and spectral efficiency. As shown in Fig. 1, BH systems usually comprise three layers [4]: • Ground planning layer: The satellite collects real-time traffic and channel information and downlinks it to the gateway, where a BHTP is computed. The BHTP specifies the service order and dwell time of each beam. • Air-interface signalling layer: The generated BHTP is encapsulated in the superframe header and other control
... ...
41
910
Beam_K-1 Beam_K
Slot_2
2
729
84
183
...
...
23
111
Slot_3
536
45
765
245
...
...
34
632
...
...
...
...
...
...
...
...
...
947
...
...
9
723
826
The BHTP of beam 3
372
...
154
Slot_L
839
...
28
341
Illumination pattern of slot 3
345
Cell_ID
Fig. 2: A complete BHTP for Kmax beams across L time slots. Each row corresponds to a time slot, each column to a beam ID, and each matrix element to a cell ID.
C. Slot and Cycle Configuration The physical layer follows the DVB-S2X Annex E superframe configuration, and the system operates in a burst-mode downlink. Based on Starlink FCC reports, we set the singlebeam net bit rate to 200 Mbps. We adopt 16-APSK with a
IEEE TRANSACTIONS ON MOBILE COMPUTING
3
3/4 code rate as the baseline MODCOD. Annex E defines a fixed superframe length of LSF = 612,540 symbols. This value implies a physical lower bound of about 10 ms for the BH dwell time. This bound preserves full alignment of the synchronization fields. We set the BH slot to 30 ms. The slot aggregates three superframes and reserves about 2 ms as a guard interval to absorb clock drift and reduce beam-switching overhead. Within the 30 ms slot, the system can switch among multiple MODCODs, such as 16-APSK 3/4 and 8-PSK 5/6, which improves link adaptation. To meet the cell revisit time constraint, we set a BH cycle of 20 slots and a total duration of 600 ms, as shown in Fig. 3. A satellite at 550 km altitude has a visibility window of about 300 s, which is much longer than this cycle. The configuration provides sufficient spatiotemporal resolution for dynamic traffic.
Traffic Distribution
③ Multi-Scale Perturbation • Gaussian perturbation • Personalized pull to gbest
Population Member
① Traffic-Aware Random Key ④ Local Refinement • Greedy injection • Seq-2Opt timeslot exchange
Aidos Algorithm
• Random Keys K
• keynew = key - βRK ·back - γRK ·gap_norm • Sort scores and select top-Q cells • Output: decoded BHTP pattern
② Short-term Prediction Probability Model Driven • Elites → window mean µ • Backlog shift µ′ µ–Δ(t) • Beta (αµ′, α(1-µ′)) sampling • Replace worst particles with K′
Environment Simulation & Fitness [-fairness, delay, -throughput]
Pareto Archive & MultiObjective Optimization • Non-dominated sorting • Crowding distance
BHTP Postamble
Superframe ≈ 10 ms SOSF
SFFI
SF 1
SFH
P CU1 CU2
SF 2
…
Fig. 4: The overall architecture of Aidos …
CUn P
SF 3
Slot = 30 ms
Slot 1
Slot 2
Slot 3
……
Slot 19
Slot 20
BHTP = 600 ms
Fig. 3: Illustration of the hierarchical relationship among the BH period, time slot, and superframe structure.
D. Particle Swarm Optimization (PSO) The proposed Aidos is inspired by particle swarm optimization (PSO). PSO is a population-based metaheuristic motivated by swarm intelligence. The algorithm maintains a swarm of particles. Each particle has a position and a velocity, which represent a candidate solution and its update direction. A particle moves using two sources of information: its personal best position pbest and the best position observed by the swarm gbest . The main procedure is as follows. First, evaluate the fitness of Np particles. Next, each generation iterates through the loop of evaluation → update of pbest and the Pareto archive → individualized selection of gbest → particle perturbation. Once a preset iteration limit is reached, select the best Pareto solution from the elite archive as the output. E. Previous Frameworks and Issues Various standards organizations have supported BH technology from different perspectives. DVB-S2X Annex E defines a beam hopping oriented superframe (SF) at the air-interface layer and specifies how the BHTP is carried in the control fields. ITU-R provides reference radiation patterns for NGSO multi-beam antennas operating in the Ku bands. 3GPP Releases 17/18/19 enhance the beam management procedures in NR-NTN to accommodate the rapid beam switching required on the satellite side.
Early practical systems adopted round-robin scheduling [15] and random scheduling [16]. These approaches are easy to implement but yield poor throughput. Greedy heuristics [17] offer fast computation as well. However, they ignore nonlinear coupling and lack global information, so they cannot reach the maximum throughput in an NP-hard search space. State-ofthe-art studies employ metaheuristic search with GA [10] and MADRL. GA has high computational complexity and cannot support online computation in large-scale scenarios. MADRL also fails to converge at scale. Value-based methods, such as Q-learning and DQN, require maximization over a discrete action set. In large-scale scenarios, the per-slot action space grows to NBc , making such methods difficult to implement [12] [13] [18] [19] [20] [21]. Actor–critic methods such as MAPPO rely on a centralized critic, whose growing global state and joint action spaces hinder efficient and stable training [22] [23]. To address these issues, we propose Aidos to compute the BHTP efficiently in large-scale settings. III. D ESIGN OVERVIEW To compute the BHTP in large-scale scenarios, we propose a hybrid optimization algorithm Aidos. The algorithm employs a multi-objective, population-based search that iteratively improves the BHTP. In each generation, it evaluates the fitness of the population, updates personal bests and the Pareto archive, and then assigns a personalized reference solution to guide the next update. The outer-loop search is configured by the swarm size Np , the iteration budget Niter , and the update coefficients (win , c1 , c2 ) in Table II. To enhance search capability, Aidos integrates four cooperative modules for encoding, probability guidance, local acceleration, and step-size adaptation. These modules enable fast convergence to high-quality BHTP solutions in large-scale scenarios. The overall structure of the algorithm is illustrated in Fig. 4. A. Traffic-Aware Random Key Encoding Module (TARK) As shown in Fig. 2, the BHTP can be modeled as a high-dimensional discrete matrix. Each entry stores a cell ID.
IEEE TRANSACTIONS ON MOBILE COMPUTING
Discrete decisions do not fit population-based search. Aidos therefore introduces a TARK module. For each slot–cell pair, the module generates a key in (0, 1) and forms a continuous key matrix with shape [num slots, num cells]. This matrix encodes the service-priority order of all cells. During decoding, the algorithm computes a composite priority from the key value, the current backlog weight, and the revisit interval. The system then selects covered cells for each time slot according to this priority and obtains a BHTP that satisfies the constraints. The method preserves the solution-space structure and embeds hotspot preference and fairness in the continuous domain, which makes the search process smoother. B. Short-term Prediction Probability Model Driven Resampling Module (STP-PMD) Every TPMD generations, where TPMD is the trigger interval of STP-PMD, Aidos activates this module after fitness evaluation and Pareto-archive update to improve subsequent BHTP iterations. The module selects the top ρ = 20% elite random-key matrices from the Pareto archive to estimate slotcell selection patterns. These elites carry useful spatiotemporal priors about effective service of slot–cell pairs. By computing sliding-window means of the keys, the module estimates slot–cell occupancy probabilities empirically. It then shifts the mean using short-term traffic predictions and backlog traffic. Using the corrected occupancy probability µ′ , we build a probabilistic model Beta(αµ′ , α(1 − µ′ )) with prior information. Here, Beta(a, b) denotes the Beta distribution on (0, 1) with shape parameters a > 0 and b > 0 (details in Section IV.C). We sample new random-key matrices from this model and replace the worst-fitness solutions. By estimating slot–cell occupancy probabilities and periodically injecting layouts that match hotspot and temporal statistics, the module accelerates multi-objective convergence. C. Local Refinement Module (LR) The LR module is triggered every TLR generations to rapidly advance the Pareto front. The module first selects individuals with high crowding and poor fitness. It then applies two direct operations to their BHTP: 1) greedy injection: overwrite selected beam columns with the set of cells that have the largest current backlog to relieve queue pressure; 2) Seq2Opt: swap two entire time-slot rows within |t1 − t2 | ≤ 3 and accept the swap if the estimated throughput increases. After the column overwrite and the row swap, the BHTP obtains a local improvement. D. Multi-Scale Perturbation Module (MSP) The MSP module operates on the BHTP random-key matrix at the end of each generation and preserves exploration through multi-scale perturbations. First, it adds Gaussian noise to the full matrix to generate diversified slot–cell priority patterns. Second, with a fixed probability, it moves the perturbed matrix toward an individualized guiding solution to avoid excessive drift. Finally, it updates the private step size σi of particle i by the 1/5 success rule, where σi controls the magnitude of
4
TABLE I: NOTATION AND DESCRIPTION Notation N M Kmax Q L B Tslot Tcycle Dm,i Dm,0 Cm,i Am,i Lpkt λtot m,i λrt m,i µm,i bi,q F1 , F2 , F3
Definition Number of satellites Number of cells Maximum active beams per satellite Total number of schedulable beams per slot Number of time slots Global BHTP matrix Duration of one time slot Duration of one BHTP cycle Traffic demand of cell m at slot i Initial traffic demand of cell m at the start of a cycle Channel capacity of cell m at slot i Rate relaxation gain of cell m during slot i Fixed packet length Total packet arrival rate of cell m at slot i Real-time packet arrival rate of cell m at slot i Service rate of cell m at slot i Cell assigned to global beam q at slot i of the BHTP Fairness, delay, and throughput objective
subsequent Gaussian perturbations on individual key values. The procedure preserves diversity and improves convergence efficiency, thereby yielding high-quality BHTP solutions. IV. A LGORITHM D ESIGN In this section, we introduce the system model of the Aidos and the design details of each module.
A. Problem Formulation This study focuses on centralized BH scheduling for the downlink of an NGSO constellation. Let the minimum receive elevation angle at the ground control center be θ. At any slot, the number of visible satellites is N , indexed by n = 1, 2, . . . , N . The control center allocates beams to these N satellites in a unified manner. The Earth’s surface is discretized into hexagonal cells using the H3 geospatial indexing library at resolution level 5, yielding a cell area that closely matches the coverage footprint of a Starlink spot beam. Superimposing the instantaneous fields of view of all visible satellites yields M ground cells, indexed by m = 1, 2, . . . , M . Each satellite can illuminate at most Kmax spot beams simultaneously. Therefore, the total number of schedulable beams in each slot is Q = N Kmax . The satellite–ground communication model adopted in this study follows the generic framework in [12] [13]. The BHTP is the core decision variable in Aidos and is defined as B = bi,q ∈ {0, 1, 2, . . . , M }L×Q (1) where i = 1, . . . , L and q = 1, . . . , Q denote the slot and global beam indices, respectively. The Q columns are grouped by satellite, with columns (n−1)Kmax +1 to nKmax corresponding to satellite n. Each element bi,q denotes the assignment of beam q in slot i, where bi,q = m means serving cell m and bi,q = 0 means idle. Moreover, L = Tcycle /Tslot . The optimization objectives considered in this work comprise fairness, average real-time packet delay, and throughput. Once the BHTP has been determined, these three metrics are
IEEE TRANSACTIONS ON MOBILE COMPUTING
5
evaluated at the end of each scheduling cycle. The fairness metric is defined as follows: M PL X i=1 Cm,i (B)Tslot F1 (B) = (2) PL m=1 Dm,0 + i=1 Am,i where Dm,0 denotes the unserved traffic demand of cell m at the start of the cycle; Cm,i (B) · Tslot is the amount of data served to cell m during slot i; and Am,i represents the rate relaxation gain at cell m during slot i, assumed to follow a Poisson distribution. Consistent with prior research, the BH service process is commonly modeled as an M/M/1 queuing system [24], where the service rate of a downlink beam is given by Cm,i (B) µm,i (B) = Lpkt
(3)
Algorithm 1: Traffic-aware Random-Key Decoding Input: key matrix KL×M ; number of slots L; number of cells M ; number of beams Q; backlog weights back; ∆t counters gap1..M ; βRK , γRK ; Output: illumination pattern P atternL×Q ; updated gap 1
for t ← 1 to L do
2
gap norm ←
3 4 5 6 7
where Lpkt denotes the fixed packet length. For cell m, the total packet arrival rate at slot i is denoted by λtot m,i . When λtot < µ (B), the average queuing delay is given by m,i m,i Wm,i (B) =
1 µm,i (B) − λtot m,i
The average delay objective of real-time packets is then given by PM PL rt f i=1 λm,i Wm,i (B) F2 (B) = m=1 (6) PM PL rt m=1 i=1 λm,i where the average arrival rate of real-time traffic is λrt m,i = 0.3 λtot m,i . The total system throughput within a BH cycle is given by F3 (B) =
M X L X
Cm,i (B)Tslot
(7)
m=1 i=1
In summary, the following multi-objective optimization problem is formulated in this study: P1 : min B
C1 :
Q X
[−F1 (B), F2 (B), −F3 (B)]
1{bi,q =m} ≤ 1,
∀m, i,
(8)
(9)
q=1
C2 :
nK max X
M X
1{bi,q =m} ≤ Kmax ,
Algorithm 2: Traffic-aware Random-Key Encoding Input: illumination pattern P atternL×Q ; number of slots L; number of cells M ; number of beams Q; ′ Output: encoded key matrix KL×M
(4)
Following the mixed-traffic profile reported by the NGMN Alliance [25], [26], we assume that real-time traffic accounts for 30% of the total demand. For real-time service with a delay deadline τmax , packets whose queuing delay exceeds τmax are treated as dropped. Dropped packets are assigned a fixed penalty delay κτmax in the objective, where κ > 1 is a penalty factor and κ = 10 in this paper. The penalized delay is defined as ( fm,i (B) = Wm,i (B), Wm,i (B) < τmax , W (5) κτmax , Wm,i (B) ≥ τmax ,
∀n, i. (10)
q=(n−1)Kmax +1 m=1
where F1 , F2 , and F3 are defined in (2), (6), and (7), respectively. Aidos optimizes this three-dimensional objective
gap − min(gap) ; max(gap) − min(gap) + ε score ← K[t, :] − βRK ·back − γRK ·gap norm; order ← argsort(score); sel ← order[1 . . . Q]; P attern[t, :] ← sel; gap ← gap + 1; gap[sel] ← 0;
K ′ ← 0L×M ; 2 for t ← 1 to L do 3 ranks ← rank ascending(P attern[t, :])/M ; 4 K ′ [t, P attern[t, :]] ← ranks; 5 mask ← {1, . . . , M } \ P attern[t, :]; 6 K ′ [t, mask] ← 0.8 + 0.2 · UniformRand(|mask|); 1
vector in a Pareto sense. Constraints C1–C2 ensure scheduling feasibility. Specifically, C1 enforces that each cell is served by at most one global beam in each slot. C2 is a structural feasibility constraint consistent with the global BHTP representation, ensuring that the beam assignments associated with satellite n remain within its dedicated Kmax beam-column block. B. Traffic-Aware Random Key Encoding Module (TARK) Solving the BHTP is a high-dimensional discrete combinatorial optimization problem. Directly updating particle velocity and position in the discrete space does not yield smooth improvement and often causes premature convergence. Therefore, we design a traffic-aware random-key encoding that maps discrete assignments to a continuous domain. This representation improves exploration efficiency. Specifically, each population member holds a random-key matrix K with shape [num slots, num cells]. Each entry lies in the interval (0, 1). The value keyt,c denotes the priority key for slot t and cell c; a smaller value indicates a higher priority. Optimization proceeds in the continuous key space and the discrete beam assignment is generated during decoding. During decoding, we execute three steps for each time slot: 1) Update the row vector of key values using backlog vector back and the unserved-interval vector gap norm: keynew = keyt − βRK back − γRK gap norm t
(11)
IEEE TRANSACTIONS ON MOBILE COMPUTING
6
Num_cells = 5, Num_beams = 3, Num_slots = 2，βRK = 0.5，γRK = 0.1
Initialization of Particle Positions Random key matrix：keyij ~ U(0,1) C0 K[0] 0.07 K[1] 0.53
C1 0.77 0.61
C2 0.43 0.86
C3 0.72 0.26
Traffic backlog vector back = [0,0,0,0,0]
Unserved time vector gap_norm = [0,0,0,0,0]
C4 0.97 0.49
Traffic state awareness Keynew = key –βRK ·back–γRK ·gap_norm
Random key decode
Beam Hopping Time Plan
timeslot 0： C0 K[0] 0.07
C1 0.77
C2 0.43
C3 0.72
C4 0.97
0
C1 0.51
C2 0.86
C3 0.26
2
3 Num_ slots
timeslot 1： gap_norm = [0,1,0,0,1] C0 K[1] 0.53
Num_beams
order = [0,2,3,1,4]
3
4
1
order = [3,4,1,0,2]
C4 0.39
Fig. 5: A numerical example of TARK module. Each particle initializes a random 2×5 key matrix representing five cells over two time slots. At time slot 0, the backlog is zero, so the original keys are retained. After sorting, the top three cells C0 , C2 , and C3 are selected, and gap norm is updated to [0, 1, 0, 0, 1]. At time slot 1, only unserved cells C1 , C4 have their key values reduced by 0.1 to increase their selection priority. This process yields the final BHTP.
where βRK and γRK are the weight coefficients of the random key module. 2) Sort the row by the updated keys and select beams in ascending order to form the slot’s illumination pattern. 3) Update gap norm and proceeds to the next slot. After selecting beams for all time slots, we obtain the final BHTP. The module embeds fairness based on backlog and waiting time directly in the decoding logic. This design balances service frequency between hotspots and low-load regions in a dynamic manner. Algorithm 1 presents the pseudocode of the TARK decoding. Line 2 computes the information required for decoding. It iterates over time slots and normalizes the revisit interval to obtain gap norm. Lines 3–5 perform priority evaluation and candidate selection. Lines 6–7 update the state. The time complexity of the decoding algorithm is summarized as follows: line 2-3 require O(M ) time; at line 4, the argsort call costs O(M logM ); line 5-7 contribute O(M + Q). Since the loop executes for L slots, the total complexity is O(LM logM ). Algorithm 2 presents the pseudocode of the TARK encoding. Line 1 initializes the encoded key matrix K ′ with zeros. Lines 2–4 assign very small keys to the cells selected in the current slot, in ascending rank order, and write them back to their positions. Lines 5–6 assign large random keys in [0.8, 1.0) to the unselected cells. The time complexity of the encoding procedure is as follows: line 1 takes O(LM ); lines 2–4 together incur O(QlogQ + Q); line 5-6 contribute O(M ). Over all L slots, the total complexity is O(L(QlogQ + M )). Since M ≫ Q in practice, the dominant term is O(LM ). Example Analysis: For example, as shown in Fig. 5, a random 2×5 key matrix is first generated for each particle, representing the continuous encoding of five cells across two time slots. At time slot t, the key values are updated based on back and gap norm. In time slot 0, since the backlog is zero, the original key values are retained. After sorting the key values in ascending order, the top three cells C0 , C2 and C3 are selected for illumination, and the gap norm is updated to [0, 1, 0, 0, 1]. Upon entering time slot 1, the key values are
updated again. It can be observed that only the cells C1 and C4 , which were not served in the previous time slot, have their key values decreased by 0.1 to increase their relative priority in the current time slot’s sorting. The final result is then used to compute the BHTP. C. Short-term Prediction Probability Model Driven Resampling Module (STP-PMD) To suppress clustering of population members in local optima and to exploit the spatiotemporal structure of the BHTP, we design a STP-PMD module, as shown in Fig. 6. The module triggers every TPMD generations. First, select the top ρ = 20% elite random-key matrices from the Pareto archive. Then, apply exponential smoothing to each cell queue: q̂j (t) = αp dj (t) + (1 − αp )q̂j (t − 1)
(12)
where qj (t) denote the backlog of cell j at slot t; dj (t) represents the actual arrival rate. Then, generate a short-term queue prediction: q̂jpred (t + 1) = q̂j (t) + βp [q̂j (t) − q̂j (t − 1)]
(13)
where αp and βp are the coefficients of the module. For the selected elite random-key matrices, use an overlapping time window of length wp (in slots) to compute the local mean µ of the key values. Add a backlog- and prediction-based offset to obtain the corrected occupancy probability µ′b,j : µ′b,j = µb,j − ∆j (t) pred
(14)
q̂j (t + 1) − qj (t) qj (t) + ηe , ∀j, (15) qmax qmax where βq and ηe are weighting coefficients, qmax is the backlog normalization constant, and ∆j (t) is the backlogand-prediction offset for cell j. This offset biases the slidingwindow mean toward cells with larger backlog and higher predicted load. We then build a probabilistic model X ∼ Beta(αµ′ , α(1 − µ′ )) to guide resampling, where Beta(a, b) denotes the Beta distribution on (0, 1) with a > 0 and b > 0. Its probability density function (PDF) is 1 fX (x; a, b) = xa−1 (1 − x)b−1 , 0 < x < 1. (16) B(a, b) ∆j (t) = βq
IEEE TRANSACTIONS ON MOBILE COMPUTING
7
a subset of the worst particles
Extract elites and compute the mean random-key matrix
Sliding window mean µ
Num_cells = 3,
Window length wp = 2
0.10 𝐾1 = 0.15 0.12
2 elites
Num_slots = 3
0.80 0.60 0.78 0.55 0.82 0.58
0.14 0.76 0.62 𝐾2 = 0.18 0.79 0.57 0.16 0.81 0.61
0.12 𝐾 = 0.165 0.14
0.78 0.785 0.815
0.5825 0.6000 0.6000
backlog at slot t-1: q(t-1) = [10,50,5] arrivals at slot t : d(t) = [15,80,8] backlog at slot t : q(t) = [12,90.6]
Block 2 0.1525 0.8000 0.5775
Backlog and prediction bias corrected mean µ' b, j = b , j − j (t )
α = 8, Beta (αµ′, α(1-µ′)) 0.0995 For illustration, the example 𝐾′ = 0.1095 uses the µ′ instead of 0.1095 random resampling.
qmax = 100, αp = 0.5 βp = 0.5, βq = 0.3, ηe = 0.4
Block 1 0.1425 0.7825 0.585
0.61 0.56 0.595
Generate a new K' using the Beta distribution Replace
Short-term queue prediction
0.5620 0.5545 0.5545
j (t ) = q
Block 1' 0.0995 0.5825 0.5620
qmax
+ e
q jpred (t + 1) − q j (t ) qmax
∆= 0.043 0.200 0.023
Block 2' 0.1095 0.6000 0.5545
Pareto front
q j (t )
Fig. 6: Illustrative example (L = 3, M = 3, wp = 2). The STP-PMD module first averages two elite key matrices and computes the sliding-window mean for each block–cell pair. It then evaluates the offset ∆j (t) to obtain the corrected occupancy probability µ′b,j , based on which the Beta model is constructed and new keys K ′ are sampled to replace the worst solution.
This parameterization satisfies E[X] = µ′ and Var(X) = µ′ (1−µ′ )/(α+1); thus the model carries spatiotemporal priors through µ′ , while α controls the concentration around µ′ . Finally, we sample a fraction ξ = 20% of new random keys from the model to refresh inferior particles, and apply small perturbations. These samples replace particles with the worst fitness and the highest crowding. During decoding, the algorithm prefers cells that have delivered gains in the corresponding slots historically. It also preserves temporal smoothness and population diversity. As a result, it is easier to produce BHTP that satisfy hotspot preference and fairness constraints. The short-term prediction only biases the probabilistic resampling, rather than directly determining the final schedule. Therefore, prediction errors mainly affect candidate-generation efficiency, while the final solutions are still screened through multi-objective evaluation and archive update. Moreover, under rolling online replanning, newly observed traffic is incorporated in subsequent updates, which helps reduce the impact of abrupt traffic changes. The pseudocode of the STP-PMD module is described in Algorithm 3. Lines 1–5 perform initialization and the standard iterative loop. When the trigger condition is met, the PMD branch is executed. Lines 6–7 select a fraction ρ of elites by nondominated rank and crowding. Lines 8–9 compute the short-term queue predictions. Lines 10–12 compute window means and add offsets. It then maps these occupancies to Beta distribution parameters. Given this prior, Lines 13–18 sample new random keys and replace inferior solutions. The time complexity of STP-PMD is summarized as follows. A single trigger incurs four main costs: elite selection O(|A| log |A|); window statistics O(Nblk M wp ); sampling and assembling ξ|P | key matrices O(ξ|P |LM ); selection and replacement of inferior solutions O(|P | log |P |). Over G generations, with a trigger every TPMD generations, the total complexity is: G O [ξ|P | · LM + (|A| + |P |) log |P | + Nblk M wp ] TPMD (17) Example Analysis: As shown in Fig. 6, we set L = 3 time slots, M = 3 cells, and window length wp = 2. First, the algorithm takes two elite random-key matrices and computes
Greedy Hot-spot Pool Injection 839 372
...
...
729
84
183
...
...
23
52
45
765 245
...
...
34
81
...
...
...
...
...
...
826 341 947
...
...
9
117
839 372
...
...
41
673
Seq-2Opt Time-slot Exchange
729
84
183
...
...
23
52
45
765 245
...
...
34
81
• with probability 0.6 • select timeslot t , w2opt randomly
28
41
Hotspot pool:
673
top M cells with the highest backlog
Num_ slots
28
Num_ slots
...
...
...
...
...
...
826
341
947
...
...
9
Iteratively replace
564 183
46
...
4
• randomly select m beam columns • overwrite them with m distinct hotspot cells
• Swap two rows in the pattern 117
Fig. 7: LR module. Greedy injection repairs the worst ηGI = 25% of particles using cells from the top-M backlog. Seq-2Opt swaps two slot patterns within a span window with probability p2opt = 0.6, and keeps the swap only if throughput increases.
their element-wise mean. It then applies a sliding-window mean over block × cell; for Block 1, it uses rows 1–2. Given the backlogs and arrivals, it computes the correction ∆ via the prediction formula and updates the block values. With α = 8, it builds a Beta model. For reproducibility, it uses the Beta expectation instead of random sampling and generates a new random-key matrix K ′ . Finally, the worst solution is replaced by the newly generated matrix K ′ . D. Local Refinement Module (LR) To avoid premature convergence caused by population members trapped in suboptimal regions, we introduce the LR module, as shown in Fig. 7. It comprises two operators: greedy injection and Seq-2Opt timeslot exchange. The LR module activates every TLR generations. In the greedy injection step, particles are ranked by instantaneous throughput, and the worst ηGI = 25% are selected for repair. Then, build a hotspot pool from the top M high-load cells. Finally, randomly choose m beam columns and overwrite each full column in the BHTP with mutually distinct hotspot cells from the pool.
IEEE TRANSACTIONS ON MOBILE COMPUTING
Algorithm 3: Short-term Prediction Probability Model Driven Resampling (STP-PMD) Input: P = {K1 , . . . , K|P | }; archive A; queues qj (t); wp ; number of slots L; number of cells M ; number of blocks Nblk ; elite fraction ρ; refresh fraction ξ; αp , βp , βq , ηe , α, σi ; qmax Output: Updated P and A g ← 0; Nblk ← L − wp + 1; while termination criterion not met do 3 E VALUATE F ITNESS(P ); 4 U PDATE P BEST(P ); 5 U PDATE A RCHIVE(A); 6 if g mod TPMD = 0 then 7 E← top ρ|P | elites from A ; 8 foreach cell j do 9 q̂j (t) ← αp dj (t) + (1 − αp )q̂j (t − 1); q̂jpred (t+1) ← q̂j (t)+βp [q̂j (t)− q̂j (t−1)];
1 2
10 11 12 13 14 15 16 17 18
19 20 21 22 23
for b ← 1 to Nblk , j = 1 . . . M do µb,j ← mean E rows [b:b+wp −1], col j ; q̂jpred (t + 1) − qj (t) qj (t) ∆j (t) ← βq +ηe ; qmax qmax ′ µb,j ← µb,j − ∆j (t); for b ← 1 to Nblk , j = 1 . . . M do ab,j ← αµ′b,j ; bb,j ← α(1 − µ′b,j ); Snew ← ∅; for k ← 1 to ⌈ξ|P |⌉ do K ′ ← S AMPLE B ETA (ab,j , bb,j ) + N (0, σi2 ) ; Snew ← Snew ∪ {K ′ }; Worst ← S ELECT W ORST P, ⌈ξ|P |⌉ ; R EPLACE(Worst, Snew ); g ← g + 1; return P, A;
Next, the Seq-2Opt operator is executed with probability p2opt = 0.6 to locally adjust the BHTP slot order. Within a window of length w2opt (in slots), randomly swap two BHTP rows. w2opt is the row-swap neighborhood size, and each row represents one slot’s illumination pattern. The swap is accepted only if the resulting throughput increases. Set the fitness of all modified particles to +∞ to force reevaluation in the next generation and keep them in the evolutionary process. This rapidly clears hotspots and advances the Pareto front without sacrificing exploration.
E. Multi-Scale Perturbation Module (MSP) The MSP module applies coarse- and fine-scale perturbations at the population level, together with a σi -adaptive perturbation at the individual level, where σi denotes the private perturbation step size of particle i. It operates directly on the BHTP random-key matrix at the end of each generation. At initialization, 20% of the particles receive a coarse step
8
size, while the remaining particles use a fine step size. Then, Gaussian perturbation is applied in each generation: g = (keyt,c + N (0, σi )) mod 1 key t,c
(18)
With probability 0.5, the perturbed particle is averaged with an individualized guiding solution to avoid excessive drift. To adapt the perturbation scale, the 1/5th success rule is used within a window of length wσ . A success is recorded when particle i updates its personal best within the current window, and the resulting success rate is used to adjust σi . Thus, MSP enables an adaptive transition from coarse exploration to finegrained refinement. F. Convergence and Computational Complexity Since the studied BHTP is a high-dimensional discrete multi-objective optimization problem, we design Aidos as a population-based metaheuristic rather than a deterministic solver. We discuss its convergence behavior from three aspects: elitist archive preservation, non-worsening local refinement, and bounded guided perturbation, as summarized in the following propositions. Proposition 1: Elitist archive preservation. Let At denote the external archive at generation t. If At+1 keeps the nondominated solutions from the current archive and the newly generated candidates, with diversity-based truncation when needed, then previously found high-quality solutions cannot be replaced by dominated ones. This proposition shows that the archive update is elitist. Therefore, high-quality non-dominated solutions can be preserved throughout subsequent iterations. Proposition 2: Non-worsening local refinement. If a local refinement operator accepts a new solution only when the acceptance criterion improves, then each accepted refinement step is non-worsening under that criterion. In Aidos, Seq-2Opt in the LR module is accepted only when the throughput of the swapped pattern exceeds that of the original pattern. Thus, local refinement is a directed improvement rather than a random perturbation. Proposition 3: Bounded perturbation scale. If the perturbation step size of each particle is kept within a predefined bounded range, then the update magnitude of the MSP module remains bounded in every generation and cannot diverge due to unbounded step growth. Since the step size is always bounded, the search gradually shifts from exploration to refinement. These properties do not establish convergence to the global Pareto-optimal set. They suggest that Aidos is a structured iterative process. This is also consistent with the empirical convergence in Section V. The per-generation cost of Aidos consists of four parts: TARK decoding and fitness evaluation for all |P | particles, the MSP update, and the periodically triggered STP-PMD and LR modules. The complexity of TARK decoding has been given above, and the total cost of fitness evaluation is denoted by Ceval . MSP updates all random-key matrices, with complexity O(|P | · LM ). The complexity of STP-PMD is
IEEE TRANSACTIONS ON MOBILE COMPUTING
9
given by Equation (17), and the amortized complexity of LR is O(CLR /TLR ). Therefore, the overall complexity is: O |P | · LM log M + Ceval + |P | · LM +
+ F H O O V D U H D
CLR TLR
ξ|P | · LM + (|A| + |P |) log |P | + Nblk M wp + TPMD
! (19)
V. EVALUATION A. Experiment Setup
TABLE II: Simulation Parameters PARAMETERS
VALUES
COMMUNICATION PARAMETERS Satellite altitude H Number of orbital planes Number of satellites per orbital plane Orbit inclination Number of downlink beams per satellite Total capacity per satellite Per-beam capacity Carrier frequency fc 3-dB beamwidth θ3dB Satellite transmit EIRP H3 res Time slot duration Tslot Total duration of BHTP
550 km 72 22 53° 48 20 Gbps 200 Mbps 20 GHz 0.15° 60 dBW 5 30 ms 600 ms
OUTER-LOOP SWARM PARAMETERS Number of particles Np Number of iterations Niter Cognitive acceleration coefficient c1 Social acceleration coefficient c2 Inertia weight win
20 150 1.5 1.5 0.7
MODULE PARAMETERS Elite fraction ρ Refresh fraction ξ Beta concentration α Window length wp , wσ Backlog weight βq Prediction weight ηe Greedy injection fraction ηGI Seq-2Opt probability p2opt
0.2 0.2 4 4,30 0.6 0.4 0.25 0.6
The preset ratios in Table II are module-level hyperparameters of Aidos. The elite fraction ρ = 0.2 keeps STPPMD focused on high-quality Pareto solutions while retaining enough samples for stable slot-cell selection statistics. The refresh fraction ξ = 0.2 injects Beta-resampled candidates biased toward high-demand cells. In LR, greedy injection
Fig. 8: Kontur population map (H3 Res 5, China); red: 1000-cell coverage area.
) U H T X H Q F \
Simulation Scenario: This study evaluates Aidos on the second-generation Starlink constellation to verify its effectiveness in large-scale satellite networks. The constellation uses circular orbits at 550 km. It comprises 72 orbital planes with 22 satellites per plane, for a total of 1,584 satellites. Each satellite carries 48 independent downlink spot beams. Each beam provides a peak capacity of 200 Mbps, as illustrated in TABLE II.
8 Q L I R U P 3 R S = L S I
' D W D 5 D W H 0 E S V
Fig. 9: Traffic Distribution Histogram. Under uniform traffic, most cell demands do not exceed 10 Mbit/s, whereas the population–Zipf model exhibits a pronounced long-tail distribution, with a minority of hotspot cells exceeding several hundred Mbit/s.
repairs the worst ηGI = 0.25 particles to improve lowthroughput BHTP, and Seq-2Opt uses p2opt = 0.6 for local BHTP-row swaps that refine the slot order. Dataset: Due to the absence of a public satellite-network traffic dataset, we generate a dataset based on the Kontur world population grid and the traffic-modeling principles in 3GPP TR 38.821. Ground cells within satellite coverage are derived using the H3 hexagonal grid library. Each cell’s initial traffic demand combines Kontur population data with Zipflaw weighting. We then add independent Poisson increments at each time slot to emulate bursty arrivals. Fig. 8 shows a population heatmap of mainland China on an H3-5 grid. Fig. 9 shows the traffic distribution histogram. The uniform baseline concentrates near 0–10 Mbps. The population–Zipf case exhibits a clear long tail, with a small number of cells reaching several hundred Mbps. These figures confirm strong load heterogeneity: hotspot cells consume a large share of capacity. The dataset approximates real-world conditions and provides a credible basis for evaluating BH schedulers. Overall Performance: We evaluate throughput and average real-time packet delay over the entire BH cycle. To quantify Aidos under different traffic intensities, we set the total satellite capacity to D and evaluate performance with ground demand [0.2, 0.4, 0.6, 0.8, 1.0] × D. We report the trends of the performance metrics.
1 R U P D O L ] H G 7 K U R X J K S X W
IEEE TRANSACTIONS ON MOBILE COMPUTING
10
$ L G R V 6 $ % + 0 2 * $ % + 5 D Q G R P % + * U H H G \ % + 0 $ ' 5 / % +
7 U D I I L F 5 D W L R
$ Y H U D J H 3 D F N H W ' H O D \ V
Fig. 10: Throughput performance trends of multiple algorithms under varying ground-traffic loads. Among the compared algorithms, Aidos achieves the highest normalized throughput.
$ L G R V 6 $ % + 0 2 * $ % + 5 D Q G R P % + * U H H G \ % +
7 U D I I L F 5 D W L R
Fig. 11: Delay performance trends of multiple algorithms under varying ground-traffic loads. Among the compared algorithms, Aidos achieves the lowest average packet delay.
The proposed Aidos is benchmarked against five baseline BH schemes: (1) Random-BH: Randomly selects Kmax cells each time slot, incurring negligible cost and serving as a lowerbound benchmark. (2) Greedy-BH: Select the top Kmax cells with the highest backlog each time slot to maximize instantaneous throughput. (3) MOGA-BH: The BH schedule is encoded as chromosomes. Genetic operations including selection, crossover, and mutation are applied to evolve solutions across generations. (4) SA-BH: Simulated annealing perturbs the current solution and probabilistically accepts worse moves under a temperature schedule to evade local optima; precise cooling-schedule tuning remains essential. (5) MADRL-BH: According to [12] , the MADRL algorithm is used to compute the illumination pattern in each time slot. Ablation Study: To quantify the independent contribution of four key mechanisms in Aidos, we conduct ablation studies on the following modules: TARK, STP-PMD, LR, and MSP. We disable one module at a time while keeping the remaining pipeline and hyper-parameters unchanged. This procedure yields four controlled variants, and the full Aidos serves as the baseline. All variants run on the same traffic scenario with ten random seeds. We record the main performance metrics
and the hyper-volume (HV) curves. Convergence: Metaheuristic algorithms improve solution quality through iterative optimization. In practice, convergence is constrained by the available computation time. Consequently, we evaluate SA-BH, MOGA-BH, and Aidos over 300 iterations. We report the mean and the 95% confidence interval across 10 independent runs. All experiments use the same traffic load of 10 Gbps. Scalability: In next-generation LEO constellations such as Starlink and OneWeb, cells are significantly smaller, and a single satellite covers thousands of cells. Scalability is therefore a key evaluation criterion. Aidos is evaluated under the operational Starlink constellation, with the Beijing ground station (39.91° N, 116.40° E) designated as the observation point. By varying the minimum receive elevation angle at the ground station, we assess the scalability of Aidos across multiple scenarios. B. Overall Performance The experimental results report throughput and latency trends under different ground-traffic intensities. As illustrated in Fig. 10, Aidos exhibits a marked advantage in throughput. At a traffic ratio of 0.1, Aidos achieves a throughput of 0.559. The gains over SA-BH, MOGABH, Random-BH, and Greedy-BH are about 93.5%, 79.2%, 232.1%, and 33.9%, respectively. As the traffic ratio increases, all algorithms face reduced headroom and show a consistent decline. Nevertheless, Aidos undergoes the smallest degradation. Even under full load, where the traffic ratio equals 1, Aidos still exceeds the second-best method, Greedy-BH, by 26.67%. By contrast, MADRL-BH performs the worst because the agents fail to learn an effective policy, confirming that the method us unsuitable for large-scale BH scenarios. Fig. 11 shows the latency results. Aidos maintains stable latency across traffic levels and remains below 70 ms. The value meets the common voice target of less than 150 ms [27]. Compared with SA-BH, MOGA-BH, Random-BH, and Greedy-BH, Aidos reduces average latency by about 99.45% to 99.9%. C. Ablation Study Results Fig. 12 and 13 reports ablation results for the four key modules in the Aidos and confirms their independent contributions. As illustrated in Fig. 12(a), the TARK module is the most critical component. It expands the searchable space and increases the HV by 40%–60%. Fig. 12(b) and Fig. 12(c) further reveal that STP-PMD and MSP both enhance population diversity and accelerate convergence; their HV gains are 12%–25% and 15%–30%, respectively. In Fig. 13(a), the LR module refines already converged solutions. It improves latency by about 7% without any throughput loss. Finally, Fig.13(b) shows that local refinement also raises the overall HV by 5%-10%. D. Convergence Result Fig. 14 and 15 present throughput and latency performance over 300 iterations for Aidos, SA-BH, and MOGA-BH. As
IEEE TRANSACTIONS ON MOBILE COMPUTING
7 U D I I L F 5 D W L R 5 H O D W L Y H W R 7 R W D O 7 U D I I L F ' H P D Q G
: L W K 3 0 '
: L W K R X W 0 X O W L B 6 F D O H
7 U D I I L F 5 D W L R 5 H O D W L Y H W R 7 R W D O 7 U D I I L F ' H P D Q G
(a) TARK module
: L W K 0 X O W L B 6 F D O H
: L W K R X W 3 0 '
+ 9 9 D O X H D W W K , W H U D W L R Q
+ 9 9 D O X H D W W K , W H U D W L R Q
+ 9 9 D O X H D W W K , W H U D W L R Q
: L W K 5 D Q G R P . H \ : L W K R X W 5 D Q G R P . H \
11
7 U D I I L F 5 D W L R 5 H O D W L Y H W R 7 R W D O 7 U D I I L F ' H P D Q G
(b) STP-PMD module
(c) MSP module
: L W K / 2 & $ / B 5 ( ) , 1 ( : L W K R X W / 2 & $ / B 5 ( ) , 1 (
$ Y H U D J H ' H O D \ V
: L W K / 2 & $ / B 5 ( ) , 1 ( : L W K R X W / 2 & $ / B 5 ( ) , 1 (
+ 9 9 D O X H D W W K , W H U D W L R Q
7 U D I I L F 5 D W L R 5 H O D W L Y H W R 7 R W D O 7 U D I I L F ' H P D Q G
7 U D I I L F 5 D W L R 5 H O D W L Y H W R 7 R W D O 7 U D I I L F ' H P D Q G
(a) Delay
(b) HV
Fig. 13: The ablation study results of LR module. With the LR module enabled, latency is reduced by approximately 7%, while the HV metric improves by 5%-10%.
1 R U P D O L ] H G 7 K U R X J K S X W
$ Y J 6 $ $ Y J 0 2 * $ $ Y J $ L G R V & , 6 $ & , 0 2 * $ & , $ L G R V
, W H U D W L R Q
Fig. 15: Delay performance of the three algorithms over 300 iterations. Aidos’s latency plunges early and settles near 0.5 s. TABLE III: Extended Scenario Parameters
$ Y J 6 $ $ Y J 0 2 * $ $ Y J $ L G R V & , 6 $ & , 0 2 * $ & , $ L G R V
$ Y H U D J H U H D O W L P H S D F N H W G H O D \ V
Fig. 12: The ablation study results of TARK, STP-PMD and MSP modules. Experimental results indicate that all three modules effectively broaden the optimization algorithm’s solution space, thereby enhancing the overall HV performance.
, W H U D W L R Q
Fig. 14: Throughput performance of the three algorithms over 300 iterations. Aidos converges fastest, reaching 0.27 within 50 generations with only minor gains afterwards.
shown, Aidos exhibits the best convergence characteristics. In terms of throughput, Aidos reaches 0.27 within 50 generations and continues to improve slightly, whereas SA-BH and MOGA-BH require about 250 iterations to approach convergence. In terms of latency, Aidos exhibits a rapid decline during the initial iterations and stabilizes at approximately 100 ms. By contrast, MOGA-BH reduces to about 34 s only after 40 generations, while SA-BH still fluctuates slowly at 45 s even after 100 generations. Aidos reaches the convergence threshold after only 50 iterations: the running mean varies by no more than 1% over 20 consecutive generations. MOGA-BH requires 150
Min. Elev.
Visible
Capacity
Scenario Size
Angle /◦
Satellite
/Gbps
(cells, beams)
Scenario 0
50◦
2
19.2
(1127, 96)
Scenario 1
42◦
3
28.8
(1667, 144)
Scenario 2
38◦
5
48
(2282, 240)
Scenario 3
33◦
7
67.2
(2693, 336)
generations and SA-BH still oscillates after 250 generations. Aidos also shows the smallest standard-deviation change, highlighting its superior stability. Therefore, 300 iterations are sufficient to cover the steady-state phase for all three algorithms. With an early-stopping rule based on the target threshold, Aidos can cap the iteration limit at 50 generations and save more than 65% of the computational budget. E. Scalability Result Fig. 18 presents the actual Starlink coverage observed from the Beijing ground station (39.91° N, 116.40° E). We set the minimum receive elevation to 50°, 42°, 38°, and 33°. By counting the number of visible satellites and the total H3 cells within the coverage footprint, we obtain three extended experimental scenarios as listed in TABLE III. Fig. 16 and 17 reports the throughput and latency in three extended scenarios. The results show that not all algorithms scale well. Aidos exhibits the best scalability and handles large
$ L G R V 6 $ % + 0 2 * $ % + 5 D Q G R P % + * U H H G \ % +
7 U D I I L F 5 D W L R
(a) Throughput in scenario 1
$ L G R V 6 $ % + 0 2 * $ % + 5 D Q G R P % + * U H H G \ % +
1 R U P D O L ] H G 7 K U R X J K S X W
12
1 R U P D O L ] H G 7 K U R X J K S X W
1 R U P D O L ] H G 7 K U R X J K S X W
IEEE TRANSACTIONS ON MOBILE COMPUTING
$ L G R V 6 $ % + 0 2 * $ % + 5 D Q G R P % + * U H H G \ % +
7 U D I I L F 5 D W L R
7 U D I I L F 5 D W L R
(b) Throughput in scenario 2
(c) Throughput in scenario 3
$ L G R V 6 $ % + 0 2 * $ % + 5 D Q G R P % + * U H H G \ % +
7 U D I I L F 5 D W L R
$ L G R V 6 $ % + 0 2 * $ % + 5 D Q G R P % + * U H H G \ % +
7 U D I I L F 5 D W L R
(a) Latency in scenario 1
(b) Latency in scenario 2
$ Y H U D J H 3 D F N H W ' H O D \ V
$ Y H U D J H 3 D F N H W ' H O D \ V
$ Y H U D J H 3 D F N H W ' H O D \ V
Fig. 16: Across the three enlarged scenarios, Aidos retains the highest aggregate throughput, outperforming MOGA-BH by 79.2%–123.1%. Both SA-BH and MOGA-BH show noticeable throughput degradation as the beam count rises, highlighting Aidos’s superior scalability.
$ L G R V 6 $ % + 0 2 * $ % + 5 D Q G R P % + * U H H G \ % +
7 U D I I L F 5 D W L R
(c) Latency in scenario 3
Fig. 17: Aidos keeps latency below 5 s over all beam counts, whereas SA-BH’s delay grows sharply and MOGA-BH exceeds real-time bounds under large-scale settings. The trend confirms that only Aidos scales efficiently in terms of latency.
% H L M L Q J * U R X Q G 6 W D W L R Q
/ R Q J L W X G H
(a) θelev ≥ 50◦
/ R Q J L W X G H
(b) θelev ≥ 42◦
% H L M L Q J * U R X Q G 6 W D W L R Q
% H L M L Q J * U R X Q G 6 W D W L R Q
/ D W L W X G H
/ D W L W X G H
% H L M L Q J * U R X Q G 6 W D W L R Q
/ D W L W X G H
/ D W L W X G H
/ R Q J L W X G H
(c) θelev ≥ 38◦
/ R Q J L W X G H
(d) θelev ≥ 33◦
Fig. 18: Actual coverage of the Starlink constellation as observed from the Beijing ground station (39.91°N, 116.40°E), under minimum elevation angle thresholds of 50°, 42°, 38°, and 33°, respectively.
networks as the number of beams increases. It maintains the highest throughput, exceeding MOGA-BH by 79.2%–123.1%, and keeps latency below 5 s. In contrast, the performance of SA-BH degrades markedly under high beam counts. Although MOGA-BH surpasses SA-BH, it still falls short of Aidos overall. Due to limits from evolutionary step size and computation
time, MOGA-BH is better suited to offline planning where accuracy is prioritized and real-time demands are low. F. Computation Time TABLE IV indicates that Aidos’s average runtime increases almost linearly with the problem size, indicating that instance scale and iteration count are the dominant factors in its computational cost. With the iteration limit uniformly set to 150, Aidos still completes within 2 min for the largest scenario. The computation time is about 54.5% lower than MOGA-BH. SA-BH, Greedy-BH, and Random-BH each run in under 3 s and remain real time even at maximum scale, but their solution quality is markedly lower than Aidos. Based on the convergence analysis, the iteration limit for Aidos can be reduced to 50 without sacrificing solution optimality. With this cap, the average runtime in the largest scenario falls to 23 s. These results indicate that the adopted outer-loop setting provides a practical balance between solution quality and runtime. Using a significantly larger iteration budget would bring only limited improvement while increasing the computation time. In this scenario, the minimum elevation is 33°, and a 550 km LEO satellite has an overpass window of about 300 seconds. Hence, Aidos can recompute about 13 times within one visibility window. This provides ample opportunity for online re-planning and ensuring strong realtime performance. VI. C ONCLUSION In this paper, we present Aidos, a hybrid optimization algorithm for computing the BHTP. The method integrates
IEEE TRANSACTIONS ON MOBILE COMPUTING
13
TABLE IV: Average Computation Time of Different Algorithms Algorithm
Average Computation Time(s) Scenario 0
Scenario 1
Scenario 2
Scenario 3
MOGA-BH
67.793
88.560
128.374
151.451
Aidos (150 iters)
30.903
49.050
69.7837
86.140
Aidos (50 iters)
9.298
17.204
19.971
22.952
traffic-aware random-key encoding with a multi-objective metaheuristic search. It further adopts sliding-window Beta resampling within an adaptive distribution evolution to improve efficiency and solution quality. Compared with MOGABH and MADRL-BH, Aidos increases throughput by 79.2% and 247.2%, respectively, and reduces latency by 99.45%. Scalability experiments across multiple cell counts show that, with the iteration limit set to 50 generations, Aidos achieves an average runtime of 9.3 s in the 1,127-cell scenario. The value fits within a 300 s satellite overpass window and enables multiple online re-optimizations. These findings confirm that Aidos is well-suited for real-time BHTP synthesis in largescale NGSO constellations. Future work will investigate more scalable distributed implementations and multi-satellite cooperative scheduling architectures for LEO mega-constellation systems. It will also extend the current BH framework to incorporate resource allocation in an additional power dimension. This may improve allocation flexibility, but also results in a more challenging higher-dimensional coupled optimization problem. ACKNOWLEDGMENT The research is sponsored by the Natural Science Foundation of Shanghai under Project No. 25ZR1402021. R EFERENCES [1] O. Kodheli, E. Lagunas, N. Maturo, S. K. Sharma, B. Shankar, J. F. M. Montoya, J. C. M. Duncan, D. Spano, S. Chatzinotas, S. Kisseleff et al., “Satellite communications in the new space era: A survey and future challenges,” IEEE Communications Surveys & Tutorials, vol. 23, no. 1, pp. 70–109, 2020. [2] H. Al-Hraishawi, H. Chougrani, S. Kisseleff, E. Lagunas, and S. Chatzinotas, “A survey on non-geostationary satellite systems: The communication perspective,” IEEE Communications Surveys & Tutorials, vol. 25, no. 1, pp. 101–132, 2022. [3] W. 3GPP, “Study on new radio (nr) to support non-terrestrial networks,” 3rd Generation Partnership Project (3GPP), Technical Report (TR), TR 38.811, 2020. [4] Digital Video Broadcasting (DVB); Second Generation Framing Structure, Channel Coding and Modulation Systems for Broadcasting, Interactive Services, News Gathering and Other Broadband Satellite Applications; Part 2: DVB-S2 Extensions (DVB-S2X), European Telecommunications Standards Institute (ETSI) ETSI EN 302 307-2, standard, August 2020. [5] C. Rohde, R. Wansch, S. Amos, H. Fenech, N. Alagha, S. Cioni, G. Mocker, and A. Trutschel-Stefan, “Beam-hopping systems for nextgeneration satellite communication systems,” in Satellite Communications in the 5G Era. IET, 2018. [6] G. Cocco, T. De Cola, M. Angelone, Z. Katona, and S. Erl, “Radio resource management optimization of flexible satellite payloads for dvbs2 systems,” IEEE Transactions on Broadcasting, vol. 64, no. 2, pp. 266–280, 2017. [7] A. I. Aravanis, B. S. MR, P.-D. Arapoglou, G. Danoy, P. G. Cottis, and B. Ottersten, “Power allocation in multibeam satellite systems: A two-stage multi-objective optimization,” IEEE Transactions on Wireless Communications, vol. 14, no. 6, pp. 3171–3182, 2015.
[8] Federal Communications Commission, “SpaceX V-Band Non-Geostationary Satellite System,” FCC International Bureau Filing – SAT-LOA-20170301-00027, [Online], 2017, accessed: Jan. 8, 2024. [Online]. Available: https://fcc.report/IBFS/SAT-LOA-20170301-00027/ 1190019.pdf [9] J. Anzalchi, A. Couchman, P. Gabellini, G. Gallinaro, L. D’agristina, N. Alagha, and P. Angeletti, “Beam hopping in multi-beam broadband satellite systems: System simulation and performance comparison with non-hopped systems,” in 2010 5th Advanced Satellite Multimedia Systems Conference and the 11th Signal Processing for Space Communications Workshop. IEEE, 2010, pp. 248–255. [10] H. Deng, K. Ying, D. Feng, L. Gui, Y. He, and X.-G. Xia, “Satellites beam hopping scheduling for interference avoidance,” IEEE Journal on Selected Areas in Communications, 2024. [11] D. Wei, D. Zheng, C. Pan, and L. Yang, “Dynamic beam scheduling of multibeam low earth orbit satellites based on an enhanced artificial bee colony algorithm,” IEEE Access, vol. 10, pp. 115 424–115 434, 2022. [12] Z. Lin, Z. Ni, L. Kuang, C. Jiang, and Z. Huang, “Satellite-terrestrial coordinated multi-satellite beam hopping scheduling based on multiagent deep reinforcement learning,” IEEE Transactions on Wireless Communications, vol. 23, no. 8, pp. 10 091–10 103, 2024. [13] D. Kim, H. Jung, and I.-H. Lee, “Dqn-based scheduling algorithm for beam-hopping leo satellite communication systems,” IEEE Wireless Communications Letters, 2025. [14] D. Duyck, D. Christopoulos, U. D. Bie, A. Dupuy, J. V. Wonterghem, P. Delbeke, H. C. Sanchez, M. Crosnier, R. Pons, O. Vidal, and P. Nayler, “Demonstrating end-to-end standards-based beam hopping with commercial equipment derisking the physical-layer challenges,” in Proc. 28th Ka and Broadband Communications, Navigation and Earth Observation Conf., Bradford, U.K., Oct. 2023, pp. 1–22, [Online]. [Online]. Available: https://proceedings.kaconf.com/papers/2023/ka3 2. pdf [15] E. Feltrin, S. Amos, H. Fenech, and E. Weller, “Eutelsat quantum-class satellite: Beam hopping,” in 3rd ESA Workshop on Advanced Flexible Telecom Payloads, 2016, pp. 21–24. [16] A. Freedman, D. Rainish, and D. Elinav, “Beam hopping system design considerations,” in 23rd Ka and Broadband Communications Conference, 2017. [17] F. Tian, L. Huang, G. Liang, X. Jiang, S. Sun, and J. Ma, “An efficient resource allocation mechanism for beam-hopping based leo satellite communication system,” in 2019 IEEE International Symposium on Broadband Multimedia Systems and Broadcasting (BMSB). IEEE, 2019, pp. 1–5. [18] K. Chen, X. Liu, and W. Li, “A distributed multi-agent deep reinforcement learning approach for dynamic beam hopping optimization in leo mega-constellations,” Swarm and Evolutionary Computation, vol. 97, p. 102039, 2025. [19] L. Gong, Q. Chen, L. Yang, Z. Yin, and Y. Wang, “Distributed beamhopping scheduling for leo mega-constellation networks based on hierarchical multi-agent deep reinforcement learning,” IEEE Transactions on Wireless Communications, 2026. [20] H. Xu, L. Liu, and Z. Zhang, “Service-driven dynamic beam hopping with resource allocation for leo satellites,” Electronics, vol. 14, no. 12, p. 2367, 2025. [21] Q. Ouyang, N. Ye, W. Shin, X. Gao, D. Niyato, and K. Yang, “Dependency-elimination madrl: Scalable on-board resource allocation for feeder-and user-link integrated satellite communications,” IEEE Transactions on Communications, vol. 73, no. 8, pp. 6673–6688, 2025. [22] R. Huang, J. Si, Z. Li, B. Deng, J. Wang, and H. Zhao, “A hybrid beam hopping scheme for uneven traffic and complex jamming environments in leo satellites: Integrating statistical planning and reinforcement learning,” IEEE Internet of Things Journal, 2025. [23] Y. Lai, Y. Li, Y. Zhang, and S. Liu, “Dynamic beam hopping based on cooperative mappo for leo satellite communication systems,” in Second Conference of Young Scientists of the Chinese Society of Optical Engineering, vol. 13799. SPIE, 2025, pp. 1082–1096. [24] S. Zheng, X. Zhang, J. Zhang, P. Wang, and W. Wang, “Traffic-aware resource management of beam hopping in satellite-enabled internet of things,” IEEE Internet of Things Journal, vol. 11, no. 21, pp. 34 504– 34 518, 2024. [25] Next Generation Mobile Networks (NGMN) Alliance, “Radio access performance evaluation methodology,” NGMN Alliance, Tech. Rep., Jan. 2008, accessed: 2026-03-05. [Online]. Available: https://www.ngmn.org/wp-content/uploads/NGMN Radio Access Performance Evaluation Methodology.pdf [26] ——, “Further study on critical c-ran technologies,” NGMN Alliance, Tech. Rep. Version 1.0,
IEEE TRANSACTIONS ON MOBILE COMPUTING
Mar. 2015, accessed: 2026-03-05. [Online]. Available: https://www.ngmn.org/wp-content/uploads/NGMN RANEV D2 Further Study on Critical C-RAN Technologes v1.0.pdf [27] “Recommendation ITU-T G.1051 (2023) Amd. 1 (04/2024),” International Telecommunication Union, Telecommunication Standardization Sector (ITU-T), Tech. Rep., Apr. 2024, amendment 1 to Recommendation ITU-T G.1051 (2023). [Online]. Available: https://www.itu.int/rec/T-REC-G.1051/en
Lingkai Zhao received the B.S. degree in Remote Sensing and the M.S. degree in Communication Engineering , both from Harbin Institute of Technology, Harbin, China. She is currently pursuing the Ph.D. degree at Fudan University, Shanghai, China. Her research interests include satellite communications and beam hopping.
Zhe Chen received his PhD in Computer Science from Fudan University, China, with a 2019 ACM SIGCOMM China Doctoral Dissertation Award. He is an Assistant Professor in the School of Computer Science at Fudan University and the Co-Founder of AIWiSe Ltd. Inc. Before joining Fudan University, he worked as a research fellow at NTU for three years, and his research achievements, along with his efforts in launching products based on them, have thus earned him 2021 ACM SIGMOBILE China Rising Star Award recently.
Kun Qiu received his B.Sc. from Fudan University in 2013 and his PhD from Fudan University in 2019. He works for Intel as a software engineer from 2019 to 2023. He joined Fudan University in 2023 as an Assistant Professor in the School of Computer Science at Fudan University. His research interests include computer networks and computer architecture. He is a member of IEEE, ACM, and CCF.
Yue Gao received his PhD from the Queen Mary University of London, UK, in 2007. He is a Chair Professor at the School of Computer Science, Director of the Intelligent Networking and Computing Research Centre at Fudan University, China and a Visiting Professor at the University of Surrey, UK. His research interests include smart antennas, sparse signal processing and cognitive networks for mobile and satellite systems. He is a Fellow of the IEEE.
14