1 Introduction↩︎

With the evolution of 5G-Advanced and future 6G cellular networks, a key design objective is to achieve truly global coverage, service ubiquity, and reliable continuous connectivity. To meet these ambitious requirements, non-terrestrial networks (NTNs) have emerged as a promising and essential complement to traditional terrestrial networks [1]. NTNs leverage spaceborne and airborne platforms, such as satellites in Low Earth Orbit (LEO), Medium Earth Orbit (MEO), Geostationary Orbit (GEO), as well as High Altitude Platform Stations (HAPS) to extend connectivity beyond the limitations of ground-based deployments. By integrating NTNs with terrestrial cellular networks, it becomes possible to provide seamless connectivity to users anywhere on the globe, including remote, rural, maritime, and aerial environments.

Recognizing the potential of NTN, the Third Generation Partnership Project (3GPP) has incorporated NTN support into 5G cellular standards with significant work introduced in Release 15 and further enhancements in subsequent releases [2]. This standardization effort enables the harmonized operation of terrestrial and non-terrestrial components within a unified cellular framework. LEO satellites typically operate at altitudes between approximately 300 km and 1500 km above the Earth’s surface. Their close proximity to the ground significantly reduces the signal propagation delay, resulting in much lower communication latency compared to MEO and GEO satellite systems, and latency levels that are comparable to those of terrestrial networks. In addition, LEO satellites offer advantages such as high speed throughput, lower launch and manufacturing costs, reduced power needs, and improved resiliency. In this work, we consider an LEO satellite system with a 5G gNB onboard.

An LEO satellite is typically visible from a fixed location on Earth for only about 8–12 minutes, depending on its altitude. Due to the high orbital speeds of LEO satellites, ensuring continuous connectivity between users and satellites is a key challenge in such networks. As a result, users must periodically transition their connection from one satellite to another through a process known as satellite handover. Based on user-reported measurements and satellite ephemeris data, the network identifies a set of candidate target satellites. It then proactively selects the most suitable target and initiates the handover following the standard phases of the 3GPP 5G—namely handover preparation, execution, and completion. Since satellite trajectories are predictable and available in advance through ephemeris data, handover events can be pre-determined and strategically planned for a given satellite system.

Unlike terrestrial networks, where handovers are primarily triggered by user mobility, handovers in LEO satellite networks occur mainly due to satellite mobility. The frequent movement of satellites makes handovers inevitable, even for stationary users. This leads to significant signaling overhead, increased power consumption, and potential service interruptions, which negatively affect throughput and latency. Therefore, our objective is to minimize the number of handovers in LEO systems. Reducing handovers can enhance overall system performance by reducing power consumption and improving both throughput and latency.

In [3], the authors give a general overview of the different solutions for handover in LEO satellite systems. In [4], the authors propose a handover strategy by modeling the user satellite connection as a potential game on a bipartite graph. In [5], the authors propose a distributed multi-agent deep Q-network-based handover strategy for LEO satellite networks that enables each user to independently make real-time handover decisions to minimize handovers while maximizing throughput and Quality of Service (QoS) satisfaction. [6] puts forward a distributed Graph Neural Network (GNN)-based handover procedure for LEO satellite networks that selects target satellites while ensuring load balancing to maximize the user sum rate and reduce handover failures. The authors in [7] propose a graph-based customizable handover framework that jointly determines the optimal handover timing and target satellite in LEO networks by modeling satellite instances over time as a graph and selecting the QoS-optimal handover sequence using shortest path optimization.

[8] proposes a caching-aware intelligent handover strategy for LEO satellite networks based on deep reinforcement learning, jointly considering caching capacity, remaining service time, and idle channels to reduce handover failures and call blocking. In [9], the authors propose a distributed load-aware satellite handover strategy based on multi-agent reinforcement learning that minimizes average handovers while reducing the user blocking rate in LEO networks. In this work, our objective is to design a handover policy for the LEO satellite system that minimizes the number of handovers while ensuring that the system is not overloaded. Our work differs from existing studies [6]–[9] in that it focuses on minimizing the instantaneous number of handovers rather than optimizing other metrics such as the average number of handovers [9], handover failures [6], [8], or handover delay [7].

2 System Model and Problem Formulation↩︎

We consider a communication system with \(M\) stationary (not mobile) users and \(N\) LEO satellites. Note that each satellite, depending on its position in the orbit, covers a certain limited area on the surface of the earth. Thus, based on user’s position, it may have potential connectivity to only a few satellites at a given point in time. Moreover, this connectivity evolves over time due to the mobility of the satellites. Let \(c_{ij}(t)\) denote the coverage indicator between user \(i\) and satellite \(j\) at time \(t\). \(c_{ij}(t)\) is defined as follows: \[c_{ij}(t)= \begin{cases} 1,& \text{if user } i \text{ can associate to satellite } j \text{ at time }t\\ 0, & \text{otherwise.} \end{cases}\]

Let \(C(t) = [c_{ij}(t)]_{i\in1, \ldots ,M,j\in1, \ldots ,N}\). We refer to the \(M\times N\) matrix \(C(t)\) as the coverage matrix at time \(t\) as it captures potential associations between users and satellites at time \(t\). Since satellites move in a predictable manner and users are assumed to be stationary, \(C(t)\) can be calculated in advance for every time \(t\). Let us define \(t_0 = 0\), and time instance \(t_k\) recursively as follows: \[\begin{align} t_k = \inf\{t\;| \;t>t_{k-1} \;andC(t) \not= C(t_{k-1})\}. \end{align}\] Note that \(\{t_k\}_{k\ge 0}\) denotes the time epochs at which the coverage matrix changes. Alternatively, the coverage matrix remains unchanged in the interval \((t_{k-1},t_{k}]\) for every \(k \ge 0\). We refer to this as the \(k\)th time slot. Let \(C[k]\) equal \(C(t_{k})\). Due to the periodic nature of satellite mobility in their respective orbits, we assume that the sequence \(\{C[k]\}_{k\ge 1}\) is also periodic, that is, there exists \(K\) such that \(C[k] = C[K+k]\) for every \(k \ge 1\). Our aim is to manage the association between users and satellites over time. To achieve this, it is sufficient to make association decisions at discrete time epochs \(\{t_1,\ldots,t_{K}\}\) due to the periodicity in the coverage matrix. Let \(\mathcal{S}_i[k]\) denote the set of satellites with which user \(i\) can associate in the \(k\)th time-slot. Define: \[\mathcal{S}_i[k] = \{j | c_{ij}[k] = 1, j = 1, \ldots ,N\}.\]

Next, we formulate our problem.

Let the \(K\)-dimensional vector \(\boldsymbol{x_i^\delta} = [x_{i1}^\delta \;\cdots \;x_{iK}^\delta]\) denote the association for user \(i\) under policy \(\delta\). Specifically, \(x_{ik}^\delta = j\) indicates that user \(i\) is associated to satellite \(j\) in \(k\)th time-slot under policy \(\delta\).

The condition (a) of Definition 2 ensures that at each point in time a user is associated with a satellite that covers it. For a user \(i\), the total number of handovers under \(\delta\) is given by: \[\label{Hi95delta} H_i(\delta) = \sum_{k=1}^{K}\mathbb{1}(x_{i(k-1)}^\delta \neq x_{ik}^\delta).\tag{1}\] The handover of the user \(i\) would incur a handover cost \(H_i(\delta)\). The total handover cost for the policy \(\delta\) would then be: \[H(\delta) = \sum_{i=1}^M H_i(\delta).\]

Each satellite has finite resources like bandwidth, power, etc. Hence, if a large number of users are associated with a single satellite, then the user experience may degrade. Hence, we assume that each satellite \(j\) can meet the QoS requirements of all associated users if the total number of users associated with satellite \(j\) is less than a given constant, say \(U_j\). The value of \(U_j\) may depend on the availability of resources at the satellite and the QoS requirement of the users. If the number of users associated with satellite \(j\) exceeds \(U_j\), then the QoS experienced by all users associated with satellite \(j\) deteriorates. For user \(i\) associated with satellite \(j\), the overload cost is given by \[O_i(\delta) = \mathbb{1}( \sum_{m=1}^M\mathbb{1}(x^{\delta}_{mk} = j) > U_j ).\] The total overload cost for policy \(\delta\) would then be: \[O(\delta) = \sum_{i=1}^M O_i(\delta).\]

We refer to \(\delta_{\lambda}^\star\) as Handover-Optimal Association Policy (HOAP).

3 HOAP without overload cost↩︎

Finding HOAP, that is, \(\delta_{\lambda}^\star\) is NP-hard. However, when \(\lambda=0\), the overload cost is 0 and HOAP (\(\delta_{0}^\star\)) can be found in polynomial time, which we discuss in the next subsection.

3.1 Optimal Handover Strategy (\(\delta_0^\star\))↩︎

When \(\lambda = 0\), the overload cost in the network becomes zero, and the objective is reduced to minimizing only the handover cost. This case therefore represents the lower bound on the total cost and can be found in polynomial time. The following lemma characterizes this scenario.

Next, we consider the case \(\lambda > 0\), where the total cost is the sum of the handover cost and the overload cost. In this scenario, if each user independently follows its optimal path (\(\delta_0^\star\)) and associates with the satellite that provides the longest continuous connectivity duration, the resulting assignment would be optimal from an individual user’s perspective. However, this strategy may lead to satellite overloading, since multiple users may have overlapping paths and may prefer to associate with the same satellite at a given time instant.

When a satellite is overloaded, each user connected with the satellite faces a degradation in QoS which is the overload cost per user. In such situations, certain users must deviate from their optimal assignment to balance the overall handover and overload costs. Unlike the single-user case, the multi-user scenario introduces interdependencies, where the decision of one user impacts the others.

The assignment of users to satellites must be determined globally by considering both the current and future time instants, due to the interdependencies among users. This makes the problem NP-hard. However, the user dependency is largely localized, since users that are geographically close tend to compete for the same satellite resources. Therefore, the problem can be simplified to resource sharing within local groups of users rather than across all users in the network. This allows the problem structure to be modeled as a local interaction game. In the following section, we present the formulation of this local interaction game.

4 Local Interaction game↩︎

We integrate our model into the game-based analytical framework. We model each user \(i\) as a player who chooses an action \(x_{ik}\) at \(k\)th time-slot. \(x_{ik}\) takes values from respective finite action set \(\mathcal{S}_i[k]\), consisting of the satellites to which the user \(i\) can associate at time-slot \(k\). Then the strategy of user \(i\) for \(K\) time-slots is the vector \(\mathbf{x_i}:= (x_{i1}, x_{i2}, \dots x_{iK})\) and let \(\mathcal{S}_i = \prod_{k=1}^{K} \mathcal{S}_i[k]\) denote the collection of all possible strategies (states) of player \(i\). Then \(\mathbf{x_i} \in \mathcal{S}_i\). The terms user and player are used interchangeably throughout the rest of the paper.

There are a total of \(M\) players in the network. Let \(\mathcal{M}= \{1,\ldots,M\}\) denote the set of the players in the network. Let the vector \(\mathbf{x}:= (\mathbf{x_1}, \mathbf{x_2}, \dots ,\mathbf{x_M})\) denote the state (or the strategy profile) of all players. Let us denote \(\mathcal{S} := \mathcal{S}_1 \times \mathcal{S}_2 \dots \times \mathcal{S}_M\). Then \(\mathbf{x} \in \mathcal{S}\). Let the utility function of player \(i\), which is dependent on the actions of all players, be denoted as \(u_i(\mathbf{x}) : \mathcal{S} \rightarrow \mathbb{R}\). Then \(\mathcal{G}=\) {\({\mathcal{M}, \mathcal{S}, (u_i(\mathbf{x}),i \in \mathcal{M})}\)} is a game.

4.1 Definition of utility function↩︎

Definition of \(u_i(\mathbf{x})\): We now begin to define the utility function \(u_i(\mathbf{x}),i \in \mathcal{M}\). The handover cost experienced by player \(i\) is defined as: \[H_i(\mathbf{x_i}) = \sum_{k=1}^{K}\mathbb{1}(x_{i(k-1)} \neq x_{ik}).\] Now, the total handover cost of all the players is given by: \[H(\mathbf{x}) = \sum_{i=1}^{M} H_i(\mathbf{x_i}).\]

Now, let \(Y_{jk}(\mathbf{x}) = \sum_{i=1}^M\mathbb{1}(x_{ik} = j)\) denote the number of users associated with satellite \(j\) in the time-slot \(k\). Let \(U_j\) indicate the maximum number of users that can associate to a satellite \(j\) at any point of time so that their QoS are satisfied. If user \(i\) overloads satellite \(j\), that is, if user \(i\) associates to satellite \(j\) and \(j\) already has \(Y_{jk}(\mathbf{x}) = U_j\) users associated with it, then satellite \(j\) is overloaded and user \(i\) incurs an overload cost of \(\lambda\). This overload cost for player \(i\) is defined as: \[O_i(\mathbf{x}) = \begin{cases} \begin{align} 0, & \quad \text{ if } Y_{jk}(\mathbf{x}) \leq U_j , \\ \lambda , & \quad \text{ otherwise,} \end{align} \end{cases}\] where \(\lambda\) is a constant denoting per-user overload cost.

Then, the total overload cost in the network is given by: \[O(\mathbf{x}) = \sum_{i=1}^{M} O_i(\mathbf{x}).\]

Our objective is to determine user associations that minimize both handover and overload costs across the network. The optimization problem is as follows: \[\label{p1} \begin{align} \mathcal{P}: \min_{\mathbf{x} \in \mathcal{S}} \quad & \sum_{i \in \mathcal{M}} H_i(\mathbf{x}) + O_i(\mathbf{x}). \end{align}\tag{2}\]

Now, construct the welfare function \(f_i(\mathbf{x})\) corresponding to every player \(i\) as \[\label{fi} f_i(\mathbf{x}) = - H_i(\mathbf{x}) - O_i(\mathbf{x}).\tag{3}\]

Thus, let the social welfare function be defined as \[\label{f} f(\mathbf{x}) := \sum_{i \in \mathcal{M}} f_i(\mathbf{x}).\tag{4}\]

Next, we formally define the Neighbors of a player.

Note that nodes \(i\) and \(i'\) will be neighbors if they are geographically close to each other. Thus, \(|\mathcal{M}_i| \ll |\mathcal{M}|\), that is, the number of neighbors of a user is significantly smaller than the total number of users in the system. In other words, each user interacts only with a small subset of users, resulting in a sparse interaction graph. By this definition of Neighbors, the nodes are symmetric, that is, if node \(i\) is a neighbor of \(i'\), then node \(i'\) is a neighbor of \(i\) and the interaction graph simplifies to an undirected graph.

Now, define the utility function of a user \(i\) as the sum of the welfare functions of all its neighbors. \[\label{utility} u_i(\mathbf{x}) = \sum_{m \in \mathcal{M}_i} f_m(\mathbf{x}),\tag{5}\] where \(\mathcal{M}_i\) denotes the neighbors of user \(i\). That is, the utility function of the user \(i\) depends only on the welfare functions of its neighbors. The undirected graph formed by \((\mathcal{M},\{\mathcal{M}_i\})\) is called as the interaction graph with each player in \(\mathcal{M}\) represented as node and \(\mathcal{M}_i\) specifies their neighbors. This implies that if player \(i\) changes its decision unilaterally, it affects only the utilities of the players in \(\mathcal{M}_i\), while the utilities of other players remain unchanged. Therefore, the action of a player leads to only local changes in utility within the interaction graph. Hence, it is called a local interaction game. Thus, our game \(\mathcal{G}=\) {\({\mathcal{M}, \mathcal{S}, (u_i(\mathbf{x}),i \in \mathcal{M})}\)} is a local interaction game.

4.2 Exact potential game↩︎

Consider the following notation. For \(\mathbf{x} = (\mathbf{x_i}, i\in \mathcal{M})\), denote \(\mathbf{x}_{-i} := (\mathbf{x_1},\ldots,\mathbf{x_{i-1}},\mathbf{x_{i+1}},\ldots,\mathbf{x_M})\) and \((\mathbf{x}'_i,\mathbf{x}_{-i}) := (\mathbf{x_1},\ldots,\mathbf{x_{i-1}},\mathbf{x}'_i,\mathbf{x_{i+1}},\ldots,\mathbf{x_M})\).

In a potential game, the incentives for all players to change their strategy are captured by a single global function called the potential function \(V\). All maximizers of a potential function \(V\) are Nash equilibria of the potential game. If the local utility of users is maximized, the global social welfare of the system would, in turn, be maximized. The utility functions of players are totally aligned with our objective of maximizing social welfare, which leads to the following lemma.

Next, we look at algorithms to find the global optimizer of the potential function \(f(\mathbf{x})\).

5 Proposed Algorithms↩︎

Our aim is to find the solution to the optimization \(\mathcal{P}\) defined in Eq. (2 ). Since the game formulation of this problem \(\mathcal{G}\) is an exact potential game, global optima exist and can be found using certain learning algorithms. Spatial Adaptive Play (SAP) is one such learning algorithm which finds the global optima after performing a sufficiently large number of iterations.

5.1 SAP algorithm↩︎

SAP is one of the algorithms that leads to an optimizer of the potential function with high probability, in the case of potential games. It is often used in spatial or networked environments where agents are connected through a graph structure, and their decisions influence each other through local interactions. The SAP Algorithm is presented in Algorithm 1.

The main idea of the algorithm is to choose a strategy \(\mathbf{x_i}\) for a player \(i\) chosen at random and compute its utility function \(u_i(\mathbf{x_i},\mathbf{x}_{-i})\) (Step 5), by changing the strategy of the player \(i\) and keeping the strategies of other players intact. Then compute the following probability (Step 7): \[\label{gibbs} p(\mathbf{x_{i}}) = \frac{e^{\beta u_i(\mathbf{x_{i}},\mathbf{x}_{-i})}}{\sum_{\mathbf{z} \in \mathcal{S}_i} e^{\beta u_i(\mathbf{z},\mathbf{x}_{-i})}},\tag{6}\] Then change the strategy of the player \(i\) according to this \(p(\mathbf{x_{i}})\), otherwise with probability \(1-p(\mathbf{x_{i}})\), do not change the strategy of the player \(i\) (Step 6). We repeat this process until the maximum number of iterations \(max_{iter}\) is reached. \(\beta\) is the learning rate for the SAP algorithm; it determines the trade-off between exploration and exploitation in SAP. The SAP algorithm provides the following analytical guarantee.

The SAP Algorithm updates one node at a time, which can lead to slow convergence. Next, we discuss a modified version of SAP, called Concurrent-SAP (C-SAP), which is found to be effective in the case of local interaction games.

5.2 Concurrent-SAP algorithm↩︎

The nodes that are separated by more than two hops (i.e., non-neighboring nodes) can update their utility functions simultaneously and independently without causing conflicts. Due to this parallel update capability, this version of SAP is referred to as the Concurrent-SAP (C-SAP) algorithm. For this modification of SAP, the stationary distribution is the same as the Gibbs distribution (Eq. 6 ). Moreover, it results in faster convergence compared to SAP, where only one node is updated at a time. For C-SAP, we use the selection scheme presented in [10]. However, it is computationally intensive. Therefore, in the next subsection, we propose a heuristic algorithm that has a lower computational complexity while achieving performance comparable to that of the C-SAP algorithm, as demonstrated by our simulations in Section 6.

5.3 Heuristic algorithm↩︎

In this subsection, we propose a greedy hill-climbing scheme that begins with an initial policy and iteratively moves toward the optimal solution by modifying one action at a time. Starting from the initial random policy, the algorithm examines each action in each iteration, changes one action, and evaluates the resulting social welfare function. If an improvement is observed, the new action is adopted. In this manner, the scheme greedily climbs toward the optimum. However, its performance depends on the choice of the initial policy. We refer to this as the greedy algorithm.

6 Simulation Results↩︎

In this section, we compare the three schemes discussed in the preceding section through extensive simulations. We consider a square region of 1000 km \(\times\) 1000 km within which 74 satellites are in motion. The region is divided into four vertical bands. In each band, two satellites have a fixed position along the x-axis while their starting positions along the y-axis are randomly assigned. The remaining satellites are randomly distributed throughout the region. The velocity of each satellite is randomly selected in the range of 7 to 8 km/s. The users are assumed to be stationary and are uniformly distributed throughout the region.

The simulation parameters used are as listed in Table ¿tbl:sim95par?, unless otherwise specified.

Figures 2 and 3 illustrate the variation in the number of handovers and total cost, respectively, as the number of users increases from 50 to 400. Green line represents the first baseline, namely the handover optimal policy (\(\delta_0^\star\)), which results in the minimum number of handovers, since overload cost is zero. Blue line represents the second baseline, the C-SAP algorithm, which provides the optimal policy by considering both handover cost and overload cost. However, this algorithm is computationally expensive. Therefore, a greedy heuristic algorithm (red) is proposed, which achieves performance comparable to the C-SAP algorithm.

In these simulations, the system parameters are fixed as follows: \(\lambda=10\), the number of satellites is 74, the number of time-slots is 100, and each satellite has a fixed capacity of 3 users per time-slot. As the user population grows, the network becomes more congested, leading to increased handovers and higher overall system cost, showing the general trend in the plots.

For the ‘Handover optimal policy’, the objective reduces to minimizing only the number of handovers. Consequently, this policy achieves the minimum number of handovers among all schemes. However, because it does not penalize satellite overloading, it allows capacity violations, resulting in artificially high social welfare in Figure 3. The C-SAP algorithm, which accounts for the overload cost (\(\lambda = 10\)), yields the lowest social welfare among the compared schemes. This is because it strictly considers both handover and overload costs, thereby avoiding excessive satellite congestion. The greedy hill-climbing algorithm is a heuristic approach that makes locally optimal decisions. Its performance closely tracks that of the C-SAP algorithm across the entire user range, indicating that it provides a reasonable approximation with lower computational complexity.

7 Conclusions↩︎

In this paper, we model the problem of user handovers and satellite overloading in a LEO satellite system as a local interaction game within a game-theoretic framework. To achieve a handover-optimal and load-balanced network state, we apply the SAP algorithm from game theory. To improve convergence speed, we further propose a modified version of SAP, termed Concurrent-SAP (C-SAP), in which multiple users update their utility functions simultaneously, enabling faster convergence to a stable solution. In addition, we design a simple greedy heuristic algorithm with lower computational complexity compared to SAP. Finally, we evaluated and compared the performance of these algorithms against a minimum-handover policy through extensive simulations.

References↩︎