# A LEO Satellite Handover Strategy Based on Graph and Multiobjective Multiagent Path Finding

Authors: Zhiyun Jiang; Wei Li; Xiangtong Wang; Binbin Liang
Journal: International Journal of Aerospace Engineering
 (2023)

---

## Abstract

Low earth orbit (LEO) satellite network can provide services to users anywhere on the earth. However, the high-speed mobility of satellites leads to a dynamic environment, which brings challenges for handover and network performance optimization, especially in the scenario of multiuser using the networks meanwhile. In this paper, we exploit multiple directed graphs to model the handover process for multiuser. The nodes in a graph represent the satellites that the corresponding user may choose to access. The edges represent the possible handovers between adjacent timestamps. The path from the start node to the end node in each graph is the handover strategy of the corresponding user, and the path length is the reward that the user can get. Therefore, the handover strategy problem is transformed into a path planning problem. To minimize the average handover times, maximize the average received power, and minimize the average number of conflicts, we propose a novel handover strategy based on multiobjective multiagent path finding (MOMAPF). The simulated handover experiment on Starlink successfully derives the Pareto-optimal solution set, which corroborates the effectiveness of the proposed handover strategy. The results also show that the proposed strategy has better comprehensive performance than other strategies.


---

## Body

## 1. Introduction

In recent years, especially after SpaceX’s Starlink plan is bringing into effect, the satellite-terrestrial integrated networks (STINs) have become a major research hot spot. As an important part of STIN, satellites can ignore the terrain and cover the whole earth’s surface, providing communication connection for satellite communication equipment anywhere on the ground. Many studies focus on STIN’s key technologies in various situations, including the association strategy between users and base stations [1, 2], gateway placement strategy [3, 4], nonorthogonal multiple access technology [5], beamforming design [6, 7], and secure transmission technology [8]. In these studies, the user terminals need to be associated with the terrestrial base stations (BSs), and the satellites are exploited to establish backhaul links with BSs to improve the network capacity (i.e., the satellites act as backhaul relays). This network structure is not suitable for user terminal communication in case of lack of ground communication facilities. In order to ensure the communication between user terminals in places without terrestrial BSs, satellites need to be exploited as BSs to establish communication links with terrestrial terminals.Compared with geostationary orbit (GEO) and medium earth orbit (MEO), low earth orbit (LEO) has the lowest orbit altitude (≤2000 km). Therefore, LEO satellite networks have great advantages in propagation delay and energy consumption of satellite-to-ground links. It can meet the needs of real-time communication of ground user terminals. Nowadays, many institutions have explored into space and put forward plans to build their own LEO constellation. In addition to SpaceX mentioned above, Kuiper and Telesat are also included [9]. However, the lower the orbital altitude of a satellite brings, the smaller the coverage area of a single satellite and the faster the speed of the satellite. In order to achieve full coverage of the ground, a LEO system often contains thousands of satellites, forming a huge constellation. As a result, at a certain time, a user on the ground is usually covered by multiple satellites at the same time, which brings the issue of access point selection. In addition, according to 3GPP document [10], the moving speed of a LEO of altitude 600 km is 7.56 km/s, which is much higher than the rotation speed of the earth and the moving speed of ground users. This huge speed difference between satellite and ground users causes the access points within the view range of the ground users to change rapidly. The application of terrestrial networks’ strongest signal selection strategy in LEO satellite network inevitably results in frequent handover of satellite-to-ground links. Therefore, the dynamic and reasonable selection of satellite access points (i.e., handover strategy) for ground terminals needs to be studied in depth.Many studies have focused on the access and handover strategy of LEO networks. Chowdhury et al. [11] summarized the existing satellite handover schemes comprehensively and divided them into network-layer handover and link-layer handover. The link-layer handover is then subdivided into intersatellite link (ISL) handover, spotbeam handover, and satellite handover. The network-layer handover is subdivided according to connection transfer strategies. From the perspective of methods, many handover strategies that consider various performance metrics have been proposed. Dai et al. [12] divided the throughput factor and the load balancing factor to get a new factor and then used PSO algorithm to maximize this factor to get the handover strategy. Liu et al. [13] proposed a load balanced satellite handover strategy, which also employs a power allocation optimization algorithm to improve the system capacity. Lei et al. [14] developed a handover strategy for aircraft based on user dynamic preferences. Cao et al. [15] proposed a UE-driven deep reinforcement learning- (DRL-) based method for random mobile ground terminals to maximize the average system throughput and meanwhile minimize the number of handovers in nonterrestrial networks. He et al. [16] exploited DRL to derive the handover strategy for multiuser to minimize average handover under the satellite load constraints. Considering caching capacity, remaining idle channels, and remaining service time, Leng et al. [17] proposed a DRL-based intelligent handover strategy to enhance the performance of the system. Xu et al. [18] developed a DRL-based LEO handover mechanism, which can maximize the QoE of mobile terminals by predicting the handover factor. Wang et al. [19] defined three metrics to represent four handover criteria and exploited DRL to optimize the sum of them. In addition, several studies use graph-based methods to investigate the solution of handover strategy. Wu et al. [20] exploited a bipartite graph and potential game to derive the handover strategy for multiuser to minimize the average satellite handover times and balance the load of software-defined satellite network. Feng et al. [21] also proposed a bipartite graph-based handover strategy that uses Kuhn-Munkres algorithm to match ground stations and satellites to maximize communication quality and balance the load of satellites. Wu et al. [22] modeled the satellite handover process based on graphs and then selected the shortest path algorithm to derive optimal handover strategy for a user in satellite networks. Hu et al. [23] utilized the time-expanded graph to predict handover for mobile users to avoid the handover prediction failure. Dai et al. [24] proposed a handover scheme based on dynamic space-time graph and used Floyd algorithm to obtain the optimal solution.However, most of the above handover strategies use the weighting method to combine multiple attributes into one and then optimize it. In practice, it is intractable for decision makers to weigh the relative importance of various attributes, especially when there are three or more attributes. Besides, the dimensions of various attributes are not uniform, and the weighting method may lead to poor robustness. The emergence of Pareto-based multiobjective optimization such as NSGAII [25] and NSGAIII [26] solves these problems. In the LEO satellite networks, they can obtain a Pareto-optimal solution set, including multiple handover strategies for decision makers to choose according to the types of users. Even though there exist few handover strategies based on Pareto-based multiobjective optimization that avoid the difficulty of setting weights, the attributes they consider are relatively simple. In practice, a certain attribute of a user is often affected by other users’ strategies, and this attribute does not appear in these handover strategies. Finding a handover strategy for multiuser with Pareto-based multiobjective optimization and considering the impact between users in the objective functions is a challenge.To solve this problem, in this paper, we model the handover process of multiuser during a certain period as multiple directed graphs and obtain the handover strategy of all users through multiagent path finding (MAPF). To consider multiple attributes, we set the weight values of the edges in the multiple directed graph model as a multivariate array. Subsequently, we qualitatively analyze the impact of users choosing the same satellite during handover and define this situation as user conflict, which is represented as path conflict in the proposed multiple directed graph model. Finally, in order to avoid setting the weights, we propose a multiobjective multiagent path planning algorithm based on conflict reduction (CR-MOMAPF), which successfully combines Pareto-based multiobjective optimization with MAPF to optimize the received signal strength, handover times, and conflict times. To the best of our knowledge, this study is the first to use Pareto-based multiobjective optimization in a multiuser LEO satellite network to optimize three criterions for handover between ground users and satellites. The main contributions of this article are as follows:(i)
We model the handover process over a period for multiuser based on multiple directed graphs and formulate the optimization problem. We further propose a new parameter, called the number of conflicts between users. Users that access or hand over to the same satellite at the same time may have conflicts, which can affect some network performances. The handover optimization problem is then transformed into MOMAPF problem. We aim to minimize the average handover times, maximize the average signal reception strength, and minimize the average number of conflicts between users(ii)
The CR-MOMAPF is proposed to combine Pareto-based multiobjective with MAPF. Unlike previous graph-based handover strategies, CR-MOMAPF avoids setting the weights of each attribute to perform multiobjective optimization and considers the influence between nodes in different graphs. In addition, this algorithm can bypass the curse of dimensionality and obtain multiple solutions for decision makers to choose(iii)
We build a huge LEO constellation as the scene and select some cities as ground users. Then, we use the proposed algorithm to find the Pareto-optimal solution set for these users in the built scene and analyze the influence of user density on Pareto front. We count the handover success rate and handover delay to show the impact of the number of user conflicts on performance. Compared with some common handover strategies, the results obtained by CR-MOMAPF have better comprehensive performance and successfully prove the effectiveness of the algorithmThe rest of this paper is organized as follows. Section2 introduces the system model and formulates the problem. In Section 3, a handover strategy based on multiagent multiobjective path finding that can reduce the number of conflicts is proposed. Then, the simulation results are provided in Section 4. Finally, this paper is concluded in Section 5.


## 2. System Model and Problem Formulation

### 2.1. System Model

As shown in Figure1, a LEO satellite network is composed of M satellites to serve N users in a specific time period which is divided into T timestamps. The satellites are indexed by J=1,⋯,M, and the users which are static on the ground are indexed by i=1,⋯,N. The timestamps are indexed by t=1,⋯,T. We assume that the topology and coverage areas of satellites remain unchanged during each timestamp. The set of satellites, the set of users, and the set of timestamps can be denoted by M, N, and T, respectively. Significantly, in a single time stamp, a user can only select one satellite for access, and one satellite can provide services to multiple users.Figure 1
A LEO satellite network is composed ofM LEO satellites and N ground users.


#### 2.1.1. Channel Model

Antenna gain and misalignment, transmission loss, and shadowing multipath fading are considered in this model. We assume that the antenna gains of uplink and downlink are the same. All satellites and users are equipped with parabolic antennas. The gain is given by [27]
(1)Gr=Gt=ηπDfc2satellites,0groundusers,where η represents the aperture efficiency of the antenna, D is the diameter of the antenna, and c and f represent the speed of light and the transmission signal frequency, respectively.Antenna misalignment can cause the power loss which is given by [27]
(2)L=0.00245θDfc,where θ represents the angle between the antenna main reception direction and the main beam direction of the incoming signal.Transmission loss includes many parts. In this model, we only consider free space loss, which is the main part of transmission loss. The free space loss is given by(3)FSL=32.4+20lgdijt+20lgf,where dijt is the distance between satellite j and user i at t and 𝑓 is the frequency of the signal.According to the above formula and the transmitting powerPtj of satellite j, the receiving power Prij without multipath fading and shadowing of user i is expressed as
(4)Prij=Ptj+Gtj+Gri−L−FSL.Considering shadowing and multipath fading, we exploit the shadowed-Rician channel model in [28]. The shadowing effect is caused by obstacles between transmitter and receiver. The slowly varying local mean power Qij is generally exploited to describe the characteristics of this effect. The probability density function (PDF) of Qij is described as log-normal and given by
(5)fQijQij=12πsQijexp−lnQij−lnPrij22s2,where s is the shadowing spread.Given the local mean powerQij, the conditional PDF of the signal power Pij in Rician fading channel is described as
(6)fPijPijQij=Kr+1Qijexp−Kr−Kr+1PijQij,I04KrKr+1PijQij,where I0. is the first kind of zeroth-order modified Bessel function. Kr is Rice factor, which represents the ratio of direct component to scattered component in the signal of the receiver. The cumulative distribution function (CDF) of Pij is
(7)FPijp=∫−∞p∫−∞+∞fPijPijQijfQijQijdQijdPij.The received signal powerPij follows cumulative distribution Fpijp. So the signal strength received by user i from satellite j at time t is given by
(8)pi,j,t=FPij−1yuseriiscoverdbysatellitej,0otherwise.where FPij−1p is the inverse cumulative distribution function of Pij and y is a random variable subject to standard uniform distribution, i.e., y~U0,1.


#### 2.1.2. Multiple Directed Graph Model

As is shown in Figure2, a directed graph is created for each user to carry out path planning, so as to obtain the handover strategy. Graphs with different colors belong to different users. The nodes in each graph represent the state of the corresponding user. Nodes si,null0 and si,nullT+1 represent that the user i is not connected to any satellite and is in idle state. Within a timestamp, user i selects one of the nearest Ki satellites for access. The remaining node si,kt is the index of satellite and indicates that the user i is in the state of connecting to the kth nearest satellite si,kt within the tth timestamp. So, a satellite in different timestamps or in different graphs is regarded as different nodes in the graph model. There is an edge between every two nodes in the adjacent timestamp and no edge between any two nodes in the same timestamp. The edge indicates that the user has a state transition relationship between two timestamps, and its weight is the reward that the user can get after state transition. In this model, we can set weights representing various meanings for each edge and create an abstract agent i for user i to find the path from node si,null0 (i.e., the start location) to node si,nullT+1 (i.e., the final destination). The location of the agent in each timestamp is the state of the corresponding user in the timestamp. By using the path planning algorithm, we can get the optimal path of the agent, which represents the optimal satellite selection strategy of the corresponding user during the whole time period.Figure 2
The multiple directed graph model of agents and an example of conflicts between agenti and agent j.Through the above directed graph model, the multiuser handover strategy problem is transformed into MOMAPF problem. Agenti makes path planning on the directed graph Gi=Vi,Ei, where Vi represents the vertex set and Ei denotes the edge set. An edge between two vertices si,ut,si,vt+1∈Vi is denoted as si,ut,si,vt+1∈Ei.In this article, three criteria need to be optimized. The handover times and received signal strength in a single user handover strategy are independent (i.e., they are not affected by the strategies of other users). The number of satellite selection conflicts is possibly affected by other users’ strategies. For agenti, the weight of an edge is a binary vector, including the received signal strength psi,ut,si,vt+1 and a binary indicator hsi,ut,si,vt+1 representing whether user i performs handover or not. They are given by
(9)psi,ut,si,vt+1=0ifv=nullandt=T,pi,si,vt+1,t+1otherwise,hsi,ut,si,vt+1=0ifsi,ut=si,vt+1,1otherwise,where pi,si,vt+1,t+1 calculates the signal strength that user i can receive at t+1 by selecting the satellite with index si,vt+1 according to Equation (8). hsi,ut,si,vt+1=1 indicates that handover occurs, while hsi,ut,si,vt+1=0 indicates no handover.


#### 2.1.3. User Conflict

Letπi represent a path of agent i from node si,null0 to node si,nullT+1. It is a sequence of vertices (i.e.,πi=si,null0,si,k11,⋯,si,kTT,si,nullT+1). In this study, the conflict between agents is the vertex conflict, which is subdivided into two types.We usei,j,si,kiti,sj,kjtj,λ to denote a conflict of type of λ between users i,j∈N. λ=1 indicates that two users i,j access or hand over to the same satellite at the same time. λ=2 indicates that user i hand overs to the satellite already serving another user j. The λ will affect the user’s avoidance strategy when resolving the conflict in the following algorithm. We use φi,jt to count the number of conflicts caused by user i to user j at t timestamp:
(10)φi,jt=1t=1,πit=πjtort≠1,πit=πjt,πjt−1≠πjt,0otherwise.φi,jt=1 indicates that the two users i,j have a conflict at time t and φi,jt=0 otherwise.Then, we use matrixA to record the number of conflicts between all agents, and its element ai,j represents the total number of conflicts caused by agent i to agent j. ai,j is given by
(11)ai,j=0ifi=j,∑t=1Tφi,jtotherwise.


#### 2.1.4. User Conflict Analysis

Conflicting users compete for certain resources on the satellite they choose, thus affecting some aspects of their network performance. For multiple access protocol in LEO satellite networks, users compete for channel resources and bandwidth resources.For example, according to results in [29], in the orthogonal frequency division multiplexing- (OFDM-) based LEO satellite communication system, with the increase of the number of users, the average uplink rate and downlink rate decrease. In addition, according to [30], we know that users who access the same satellite at the same time share the computing resources of the satellite equally. Therefore, with the increase of users accessing the satellite, the computing resources allocated to each user are reduced, which further affects the authentication delay, handover delay, etc. In addition, reducing the number of users accessing the same satellite can also reduce the load of the satellite.Based on the above analysis, we can conclude that reducing the number of users switching to satellitej at the same time (i.e., called conflict in this paper) allows these users to be allocated more network resources, thus improving network performance. Therefore, we take minimizing the number of conflicts as one of the optimization objectives of this paper.


#### 2.1.5. Handover Delay

The handover delay mainly includes the signal propagation delay in the handover procedure and the time delay for the satellite to verify the user’s identity. The former is related to the distance between the satellite and the user, and the latter is related to the onboard processing capacity of the satellite. According to [30], the available computing resource for user i allocated by satellite j is
(12)αijt=FjNjt,where Fj is a constant representing the computing resources provided by each satellite j. Njt is the number of users accessing satellite j at t. The authentication delay for satellite j to authenticate the identity of user i is [30]
(13)Sijt=Baijt,where B denotes the amount of calculation required for each user in the handover procedure. We assume four signaling exchanges between the user and the target satellite after the source satellite notifies the user of the handover. Therefore, the handover delay for user i to handover to satellite j at t is
(14)HTijt=Sijt+4⋅dijtc.


#### 2.1.6. Handover Success or Failure

The user’s selection of satellite at a handover directly affects the success of the handover. According to [19], the coverage relationship of the satellite to the user, the communication quality of the link between the satellite and the user, and the load of the satellite all determine whether the handover is successful for the user. We use the value of ri,jt to indicate whether the handover from user i to satellite j is successful at t. ri,jt is given by [19]
(15)ri,jt=0,useriisnotcoveredbysatellitejorCNRi,jt<CNRminorNjt>Njmax,1,otherwise,where Njmax is the maximum channel number of satellite j. CNRti,j is the carrier to noise ratio of the link between user i and satellite j at t. CNRmin is the carrier to noise ratio threshold. When CNRi,jt is less than CNRmin, it indicates that the link quality is poor. CNRi,jt is given by [19]
(16)CNRi,jt=pi,j,tkBBdTtem,where kB is the Boltzmann’s constant (1.38×10‐23 W/(Hz∙K)). Bd is the bandwidth of shared spectrum. Ttem is the thermodynamic temperature of the receiver.


### 2.2. Problem Formulation

The cost vectorci of a single user path πi is defined as a binary vector including handover times and signal strength, i.e., ci=f1i,f2i. It is the cost vector of Individualsearch procedure in the following algorithm. Let πk=πk1,πk2,⋯,πkN represent a joint path for all the users, which is also called a solution. The size of a solution is N×T. Take the average number of conflicts contained in this solution as another cost element. The cost vector of a solution is defined as ck=f¯1,f¯2,f¯3. Therefore, this three-objective optimization can be formulated by
(17)maxf¯1=1N∑i=1Nf1i=1N∑i=1N∑si,ut,si,vt+1∈Eixsi,ut,si,vt+1psi,ut,si,vt+1minf¯2=1N∑i=1Nf2i=1N∑i=1N∑si,ut,si,vt+1∈Eixsi,ut,si,vt+1hsi,ut,si,vt+1minf¯3=1N∑i=1N∑j=1Nai,js.t.xsi,ut,si,vt+1∈0,1,∀i∈N,∀si,ut,si,vt+1∈Ei,where xsi,ut,si,vt+1 is a binary indicator representing whether agent i passes through the edge si,ut,si,vt+1 or not, i.e.,xsi,ut,si,vt+1=1 if the agent i passes through edge si,ut,si,vt+1 and xsi,ut,si,vt+1=0 otherwise. Given the paths of all agents, we can get the handover success rate of the corresponding users under the handover strategies, which is the ratio of the successful handover times of these users to the total handover times [31].
(18)hs=∑i=1N∑si,ut,si,vt+1∈Eixsi,ut,si,vt+1hsi,ut,si,vt+1ri,si,vt+1t+1∑i=1N∑si,ut,si,vt+1∈Eixsi,ut,si,vt+1hsi,ut,si,vt+1.Subsequently, we use the dominance relationship between the vectors to compare the cost vectors of any two solutions and finally get the Pareto-optimal solution set.


## 2.1. System Model

As shown in Figure1, a LEO satellite network is composed of M satellites to serve N users in a specific time period which is divided into T timestamps. The satellites are indexed by J=1,⋯,M, and the users which are static on the ground are indexed by i=1,⋯,N. The timestamps are indexed by t=1,⋯,T. We assume that the topology and coverage areas of satellites remain unchanged during each timestamp. The set of satellites, the set of users, and the set of timestamps can be denoted by M, N, and T, respectively. Significantly, in a single time stamp, a user can only select one satellite for access, and one satellite can provide services to multiple users.Figure 1
A LEO satellite network is composed ofM LEO satellites and N ground users.


### 2.1.1. Channel Model

Antenna gain and misalignment, transmission loss, and shadowing multipath fading are considered in this model. We assume that the antenna gains of uplink and downlink are the same. All satellites and users are equipped with parabolic antennas. The gain is given by [27]
(1)Gr=Gt=ηπDfc2satellites,0groundusers,where η represents the aperture efficiency of the antenna, D is the diameter of the antenna, and c and f represent the speed of light and the transmission signal frequency, respectively.Antenna misalignment can cause the power loss which is given by [27]
(2)L=0.00245θDfc,where θ represents the angle between the antenna main reception direction and the main beam direction of the incoming signal.Transmission loss includes many parts. In this model, we only consider free space loss, which is the main part of transmission loss. The free space loss is given by(3)FSL=32.4+20lgdijt+20lgf,where dijt is the distance between satellite j and user i at t and 𝑓 is the frequency of the signal.According to the above formula and the transmitting powerPtj of satellite j, the receiving power Prij without multipath fading and shadowing of user i is expressed as
(4)Prij=Ptj+Gtj+Gri−L−FSL.Considering shadowing and multipath fading, we exploit the shadowed-Rician channel model in [28]. The shadowing effect is caused by obstacles between transmitter and receiver. The slowly varying local mean power Qij is generally exploited to describe the characteristics of this effect. The probability density function (PDF) of Qij is described as log-normal and given by
(5)fQijQij=12πsQijexp−lnQij−lnPrij22s2,where s is the shadowing spread.Given the local mean powerQij, the conditional PDF of the signal power Pij in Rician fading channel is described as
(6)fPijPijQij=Kr+1Qijexp−Kr−Kr+1PijQij,I04KrKr+1PijQij,where I0. is the first kind of zeroth-order modified Bessel function. Kr is Rice factor, which represents the ratio of direct component to scattered component in the signal of the receiver. The cumulative distribution function (CDF) of Pij is
(7)FPijp=∫−∞p∫−∞+∞fPijPijQijfQijQijdQijdPij.The received signal powerPij follows cumulative distribution Fpijp. So the signal strength received by user i from satellite j at time t is given by
(8)pi,j,t=FPij−1yuseriiscoverdbysatellitej,0otherwise.where FPij−1p is the inverse cumulative distribution function of Pij and y is a random variable subject to standard uniform distribution, i.e., y~U0,1.


### 2.1.2. Multiple Directed Graph Model

As is shown in Figure2, a directed graph is created for each user to carry out path planning, so as to obtain the handover strategy. Graphs with different colors belong to different users. The nodes in each graph represent the state of the corresponding user. Nodes si,null0 and si,nullT+1 represent that the user i is not connected to any satellite and is in idle state. Within a timestamp, user i selects one of the nearest Ki satellites for access. The remaining node si,kt is the index of satellite and indicates that the user i is in the state of connecting to the kth nearest satellite si,kt within the tth timestamp. So, a satellite in different timestamps or in different graphs is regarded as different nodes in the graph model. There is an edge between every two nodes in the adjacent timestamp and no edge between any two nodes in the same timestamp. The edge indicates that the user has a state transition relationship between two timestamps, and its weight is the reward that the user can get after state transition. In this model, we can set weights representing various meanings for each edge and create an abstract agent i for user i to find the path from node si,null0 (i.e., the start location) to node si,nullT+1 (i.e., the final destination). The location of the agent in each timestamp is the state of the corresponding user in the timestamp. By using the path planning algorithm, we can get the optimal path of the agent, which represents the optimal satellite selection strategy of the corresponding user during the whole time period.Figure 2
The multiple directed graph model of agents and an example of conflicts between agenti and agent j.Through the above directed graph model, the multiuser handover strategy problem is transformed into MOMAPF problem. Agenti makes path planning on the directed graph Gi=Vi,Ei, where Vi represents the vertex set and Ei denotes the edge set. An edge between two vertices si,ut,si,vt+1∈Vi is denoted as si,ut,si,vt+1∈Ei.In this article, three criteria need to be optimized. The handover times and received signal strength in a single user handover strategy are independent (i.e., they are not affected by the strategies of other users). The number of satellite selection conflicts is possibly affected by other users’ strategies. For agenti, the weight of an edge is a binary vector, including the received signal strength psi,ut,si,vt+1 and a binary indicator hsi,ut,si,vt+1 representing whether user i performs handover or not. They are given by
(9)psi,ut,si,vt+1=0ifv=nullandt=T,pi,si,vt+1,t+1otherwise,hsi,ut,si,vt+1=0ifsi,ut=si,vt+1,1otherwise,where pi,si,vt+1,t+1 calculates the signal strength that user i can receive at t+1 by selecting the satellite with index si,vt+1 according to Equation (8). hsi,ut,si,vt+1=1 indicates that handover occurs, while hsi,ut,si,vt+1=0 indicates no handover.


### 2.1.3. User Conflict

Letπi represent a path of agent i from node si,null0 to node si,nullT+1. It is a sequence of vertices (i.e.,πi=si,null0,si,k11,⋯,si,kTT,si,nullT+1). In this study, the conflict between agents is the vertex conflict, which is subdivided into two types.We usei,j,si,kiti,sj,kjtj,λ to denote a conflict of type of λ between users i,j∈N. λ=1 indicates that two users i,j access or hand over to the same satellite at the same time. λ=2 indicates that user i hand overs to the satellite already serving another user j. The λ will affect the user’s avoidance strategy when resolving the conflict in the following algorithm. We use φi,jt to count the number of conflicts caused by user i to user j at t timestamp:
(10)φi,jt=1t=1,πit=πjtort≠1,πit=πjt,πjt−1≠πjt,0otherwise.φi,jt=1 indicates that the two users i,j have a conflict at time t and φi,jt=0 otherwise.Then, we use matrixA to record the number of conflicts between all agents, and its element ai,j represents the total number of conflicts caused by agent i to agent j. ai,j is given by
(11)ai,j=0ifi=j,∑t=1Tφi,jtotherwise.


### 2.1.4. User Conflict Analysis

Conflicting users compete for certain resources on the satellite they choose, thus affecting some aspects of their network performance. For multiple access protocol in LEO satellite networks, users compete for channel resources and bandwidth resources.For example, according to results in [29], in the orthogonal frequency division multiplexing- (OFDM-) based LEO satellite communication system, with the increase of the number of users, the average uplink rate and downlink rate decrease. In addition, according to [30], we know that users who access the same satellite at the same time share the computing resources of the satellite equally. Therefore, with the increase of users accessing the satellite, the computing resources allocated to each user are reduced, which further affects the authentication delay, handover delay, etc. In addition, reducing the number of users accessing the same satellite can also reduce the load of the satellite.Based on the above analysis, we can conclude that reducing the number of users switching to satellitej at the same time (i.e., called conflict in this paper) allows these users to be allocated more network resources, thus improving network performance. Therefore, we take minimizing the number of conflicts as one of the optimization objectives of this paper.


### 2.1.5. Handover Delay

The handover delay mainly includes the signal propagation delay in the handover procedure and the time delay for the satellite to verify the user’s identity. The former is related to the distance between the satellite and the user, and the latter is related to the onboard processing capacity of the satellite. According to [30], the available computing resource for user i allocated by satellite j is
(12)αijt=FjNjt,where Fj is a constant representing the computing resources provided by each satellite j. Njt is the number of users accessing satellite j at t. The authentication delay for satellite j to authenticate the identity of user i is [30]
(13)Sijt=Baijt,where B denotes the amount of calculation required for each user in the handover procedure. We assume four signaling exchanges between the user and the target satellite after the source satellite notifies the user of the handover. Therefore, the handover delay for user i to handover to satellite j at t is
(14)HTijt=Sijt+4⋅dijtc.


### 2.1.6. Handover Success or Failure

The user’s selection of satellite at a handover directly affects the success of the handover. According to [19], the coverage relationship of the satellite to the user, the communication quality of the link between the satellite and the user, and the load of the satellite all determine whether the handover is successful for the user. We use the value of ri,jt to indicate whether the handover from user i to satellite j is successful at t. ri,jt is given by [19]
(15)ri,jt=0,useriisnotcoveredbysatellitejorCNRi,jt<CNRminorNjt>Njmax,1,otherwise,where Njmax is the maximum channel number of satellite j. CNRti,j is the carrier to noise ratio of the link between user i and satellite j at t. CNRmin is the carrier to noise ratio threshold. When CNRi,jt is less than CNRmin, it indicates that the link quality is poor. CNRi,jt is given by [19]
(16)CNRi,jt=pi,j,tkBBdTtem,where kB is the Boltzmann’s constant (1.38×10‐23 W/(Hz∙K)). Bd is the bandwidth of shared spectrum. Ttem is the thermodynamic temperature of the receiver.


## 2.1.1. Channel Model

Antenna gain and misalignment, transmission loss, and shadowing multipath fading are considered in this model. We assume that the antenna gains of uplink and downlink are the same. All satellites and users are equipped with parabolic antennas. The gain is given by [27]
(1)Gr=Gt=ηπDfc2satellites,0groundusers,where η represents the aperture efficiency of the antenna, D is the diameter of the antenna, and c and f represent the speed of light and the transmission signal frequency, respectively.Antenna misalignment can cause the power loss which is given by [27]
(2)L=0.00245θDfc,where θ represents the angle between the antenna main reception direction and the main beam direction of the incoming signal.Transmission loss includes many parts. In this model, we only consider free space loss, which is the main part of transmission loss. The free space loss is given by(3)FSL=32.4+20lgdijt+20lgf,where dijt is the distance between satellite j and user i at t and 𝑓 is the frequency of the signal.According to the above formula and the transmitting powerPtj of satellite j, the receiving power Prij without multipath fading and shadowing of user i is expressed as
(4)Prij=Ptj+Gtj+Gri−L−FSL.Considering shadowing and multipath fading, we exploit the shadowed-Rician channel model in [28]. The shadowing effect is caused by obstacles between transmitter and receiver. The slowly varying local mean power Qij is generally exploited to describe the characteristics of this effect. The probability density function (PDF) of Qij is described as log-normal and given by
(5)fQijQij=12πsQijexp−lnQij−lnPrij22s2,where s is the shadowing spread.Given the local mean powerQij, the conditional PDF of the signal power Pij in Rician fading channel is described as
(6)fPijPijQij=Kr+1Qijexp−Kr−Kr+1PijQij,I04KrKr+1PijQij,where I0. is the first kind of zeroth-order modified Bessel function. Kr is Rice factor, which represents the ratio of direct component to scattered component in the signal of the receiver. The cumulative distribution function (CDF) of Pij is
(7)FPijp=∫−∞p∫−∞+∞fPijPijQijfQijQijdQijdPij.The received signal powerPij follows cumulative distribution Fpijp. So the signal strength received by user i from satellite j at time t is given by
(8)pi,j,t=FPij−1yuseriiscoverdbysatellitej,0otherwise.where FPij−1p is the inverse cumulative distribution function of Pij and y is a random variable subject to standard uniform distribution, i.e., y~U0,1.


## 2.1.2. Multiple Directed Graph Model

As is shown in Figure2, a directed graph is created for each user to carry out path planning, so as to obtain the handover strategy. Graphs with different colors belong to different users. The nodes in each graph represent the state of the corresponding user. Nodes si,null0 and si,nullT+1 represent that the user i is not connected to any satellite and is in idle state. Within a timestamp, user i selects one of the nearest Ki satellites for access. The remaining node si,kt is the index of satellite and indicates that the user i is in the state of connecting to the kth nearest satellite si,kt within the tth timestamp. So, a satellite in different timestamps or in different graphs is regarded as different nodes in the graph model. There is an edge between every two nodes in the adjacent timestamp and no edge between any two nodes in the same timestamp. The edge indicates that the user has a state transition relationship between two timestamps, and its weight is the reward that the user can get after state transition. In this model, we can set weights representing various meanings for each edge and create an abstract agent i for user i to find the path from node si,null0 (i.e., the start location) to node si,nullT+1 (i.e., the final destination). The location of the agent in each timestamp is the state of the corresponding user in the timestamp. By using the path planning algorithm, we can get the optimal path of the agent, which represents the optimal satellite selection strategy of the corresponding user during the whole time period.Figure 2
The multiple directed graph model of agents and an example of conflicts between agenti and agent j.Through the above directed graph model, the multiuser handover strategy problem is transformed into MOMAPF problem. Agenti makes path planning on the directed graph Gi=Vi,Ei, where Vi represents the vertex set and Ei denotes the edge set. An edge between two vertices si,ut,si,vt+1∈Vi is denoted as si,ut,si,vt+1∈Ei.In this article, three criteria need to be optimized. The handover times and received signal strength in a single user handover strategy are independent (i.e., they are not affected by the strategies of other users). The number of satellite selection conflicts is possibly affected by other users’ strategies. For agenti, the weight of an edge is a binary vector, including the received signal strength psi,ut,si,vt+1 and a binary indicator hsi,ut,si,vt+1 representing whether user i performs handover or not. They are given by
(9)psi,ut,si,vt+1=0ifv=nullandt=T,pi,si,vt+1,t+1otherwise,hsi,ut,si,vt+1=0ifsi,ut=si,vt+1,1otherwise,where pi,si,vt+1,t+1 calculates the signal strength that user i can receive at t+1 by selecting the satellite with index si,vt+1 according to Equation (8). hsi,ut,si,vt+1=1 indicates that handover occurs, while hsi,ut,si,vt+1=0 indicates no handover.


## 2.1.3. User Conflict

Letπi represent a path of agent i from node si,null0 to node si,nullT+1. It is a sequence of vertices (i.e.,πi=si,null0,si,k11,⋯,si,kTT,si,nullT+1). In this study, the conflict between agents is the vertex conflict, which is subdivided into two types.We usei,j,si,kiti,sj,kjtj,λ to denote a conflict of type of λ between users i,j∈N. λ=1 indicates that two users i,j access or hand over to the same satellite at the same time. λ=2 indicates that user i hand overs to the satellite already serving another user j. The λ will affect the user’s avoidance strategy when resolving the conflict in the following algorithm. We use φi,jt to count the number of conflicts caused by user i to user j at t timestamp:
(10)φi,jt=1t=1,πit=πjtort≠1,πit=πjt,πjt−1≠πjt,0otherwise.φi,jt=1 indicates that the two users i,j have a conflict at time t and φi,jt=0 otherwise.Then, we use matrixA to record the number of conflicts between all agents, and its element ai,j represents the total number of conflicts caused by agent i to agent j. ai,j is given by
(11)ai,j=0ifi=j,∑t=1Tφi,jtotherwise.


## 2.1.4. User Conflict Analysis

Conflicting users compete for certain resources on the satellite they choose, thus affecting some aspects of their network performance. For multiple access protocol in LEO satellite networks, users compete for channel resources and bandwidth resources.For example, according to results in [29], in the orthogonal frequency division multiplexing- (OFDM-) based LEO satellite communication system, with the increase of the number of users, the average uplink rate and downlink rate decrease. In addition, according to [30], we know that users who access the same satellite at the same time share the computing resources of the satellite equally. Therefore, with the increase of users accessing the satellite, the computing resources allocated to each user are reduced, which further affects the authentication delay, handover delay, etc. In addition, reducing the number of users accessing the same satellite can also reduce the load of the satellite.Based on the above analysis, we can conclude that reducing the number of users switching to satellitej at the same time (i.e., called conflict in this paper) allows these users to be allocated more network resources, thus improving network performance. Therefore, we take minimizing the number of conflicts as one of the optimization objectives of this paper.


## 2.1.5. Handover Delay

The handover delay mainly includes the signal propagation delay in the handover procedure and the time delay for the satellite to verify the user’s identity. The former is related to the distance between the satellite and the user, and the latter is related to the onboard processing capacity of the satellite. According to [30], the available computing resource for user i allocated by satellite j is
(12)αijt=FjNjt,where Fj is a constant representing the computing resources provided by each satellite j. Njt is the number of users accessing satellite j at t. The authentication delay for satellite j to authenticate the identity of user i is [30]
(13)Sijt=Baijt,where B denotes the amount of calculation required for each user in the handover procedure. We assume four signaling exchanges between the user and the target satellite after the source satellite notifies the user of the handover. Therefore, the handover delay for user i to handover to satellite j at t is
(14)HTijt=Sijt+4⋅dijtc.


## 2.1.6. Handover Success or Failure

The user’s selection of satellite at a handover directly affects the success of the handover. According to [19], the coverage relationship of the satellite to the user, the communication quality of the link between the satellite and the user, and the load of the satellite all determine whether the handover is successful for the user. We use the value of ri,jt to indicate whether the handover from user i to satellite j is successful at t. ri,jt is given by [19]
(15)ri,jt=0,useriisnotcoveredbysatellitejorCNRi,jt<CNRminorNjt>Njmax,1,otherwise,where Njmax is the maximum channel number of satellite j. CNRti,j is the carrier to noise ratio of the link between user i and satellite j at t. CNRmin is the carrier to noise ratio threshold. When CNRi,jt is less than CNRmin, it indicates that the link quality is poor. CNRi,jt is given by [19]
(16)CNRi,jt=pi,j,tkBBdTtem,where kB is the Boltzmann’s constant (1.38×10‐23 W/(Hz∙K)). Bd is the bandwidth of shared spectrum. Ttem is the thermodynamic temperature of the receiver.


## 2.2. Problem Formulation

The cost vectorci of a single user path πi is defined as a binary vector including handover times and signal strength, i.e., ci=f1i,f2i. It is the cost vector of Individualsearch procedure in the following algorithm. Let πk=πk1,πk2,⋯,πkN represent a joint path for all the users, which is also called a solution. The size of a solution is N×T. Take the average number of conflicts contained in this solution as another cost element. The cost vector of a solution is defined as ck=f¯1,f¯2,f¯3. Therefore, this three-objective optimization can be formulated by
(17)maxf¯1=1N∑i=1Nf1i=1N∑i=1N∑si,ut,si,vt+1∈Eixsi,ut,si,vt+1psi,ut,si,vt+1minf¯2=1N∑i=1Nf2i=1N∑i=1N∑si,ut,si,vt+1∈Eixsi,ut,si,vt+1hsi,ut,si,vt+1minf¯3=1N∑i=1N∑j=1Nai,js.t.xsi,ut,si,vt+1∈0,1,∀i∈N,∀si,ut,si,vt+1∈Ei,where xsi,ut,si,vt+1 is a binary indicator representing whether agent i passes through the edge si,ut,si,vt+1 or not, i.e.,xsi,ut,si,vt+1=1 if the agent i passes through edge si,ut,si,vt+1 and xsi,ut,si,vt+1=0 otherwise. Given the paths of all agents, we can get the handover success rate of the corresponding users under the handover strategies, which is the ratio of the successful handover times of these users to the total handover times [31].
(18)hs=∑i=1N∑si,ut,si,vt+1∈Eixsi,ut,si,vt+1hsi,ut,si,vt+1ri,si,vt+1t+1∑i=1N∑si,ut,si,vt+1∈Eixsi,ut,si,vt+1hsi,ut,si,vt+1.Subsequently, we use the dominance relationship between the vectors to compare the cost vectors of any two solutions and finally get the Pareto-optimal solution set.


## 3. Proposed MOMAPF-Based Handover Strategy for Multiuser

MAPF has been deeply studied in the field of robots and UAVs, and many algorithms have been developed, including A∗-based approaches [32] and Conflict-Based Search (CBS) [33]. However, there are few studies on the MOMAPF problem of NP-hard [34]. The studies in [34, 35], and [36] are based on a grid map scenario, and all the agents are on the same map. In addition, these studies enforce that conflict cannot occur, which is inconsistent with our goal of reducing the number of conflicts. Here, we propose CR-MOMAPF for multiagent multiobjective optimization in multiple directed graphs to obtain multiuser handover strategy in LEO satellite networks.The proposed CR-MOMAPF algorithm is an extension of CBS, which has two key points:twolevelsearch and conflictsplit. For the low level in twolevelsearch, each agent carries out path finding without considering other agents. Then, the high level in twolevelsearch solves the conflict between the paths obtained by the low level of multiagent. The specific approach to solve the conflict is to adopt conflictsplit, which splits the conflict into multiple constraints and then gives the constraints to the corresponding agents. The generation process of CR-MOMAPF solutions is visualized in Figure 3. The purpose of the initialization stage is to generate the initial root nodes (i.e., the blue nodes). In the search stage, for the root nodes that have not been abandoned, as long as conflicts are found, child nodes will be generated. Through iteration, nodes with better and better cost vectors are obtained. The goal of this stage is to find nodes with excellent cost vectors, and the solutions represented by these nodes are the final output of the algorithm. The specific process of each stage of CR-MOMAPF is described in Algorithm 1.Figure 3
Search process of CR-MOMAPF.


### 3.1. Initialization Stage

In the initialization stage, according to the Two-Line Orbital Element (TLE) information of the satellite constellation, each user calculates the distance of the satellite within multiple timestamps. To implement the path planning algorithm, a directed graphGi is constructed for each user i, and various weights and meanings are given to the edges and nodes in the graph according to the distance file and the previously mentioned channel model. Then, P (the Pareto-optimal solution set), P1 (the Pareto-front), and OPEN (node set to be searched) are set as empty sets. Based on the graph Gi, aiming at minimizing f1i and maximizing f2i, each user i executes Individualsearch procedure (i.e., multiobjective single-agent path finding algorithm) to find individual Pareto-optimal solution set Oi without constraint.


### 3.2. Search Stage

In this stage, a set of joint pathsΠ is generated by taking the combination of Oi, ∀i∈N, i.e., Π=πkπk=πk1,πk2,⋯,πkN,πki∈Oi,∀i∈N. Then, for each joint path πk∈Π, ck, πk, and the constraints (empty set) are combined to form a search node Rkπk,ck,Ωk and added to OPEN.For each search iteration in CR-MOMAPF (lines 14-42), a search nodeRkπk,ck,Ωk is popped from OPEN. Then, the Check procedure is exploited to determine whether the node Rk is worth continuing the search. If there is no vector dominating ck in P1 (i.e., CheckRk=False), we think node Rk is worth continuing to search, otherwise the node is discarded. With the Update procedure, those cost vectors dominated by ck in P1 and their corresponding strategies are removed from P1 and P, respectively. Then, πk and ck are added into P and P1, respectively. The procedure Update is necessary due to the fact that it can ensure that the vectors in P1 are Pareto-optimal in the whole search iteration progress. As a result, P1 is guaranteed to be the excellent Pareto-optimal front when the algorithm terminates.If there is no conflict inπk, then πk is a Pareto-optimal solution because it has the best performance in terms of f¯3 and no other vector can dominate it. If a conflict i,j,si,kiti,sj,kjtj,λ is detected in πk, we adopt the splitconflictapproach in CBS to resolve the detected conflict. However, different from CBS, here, we split a detected conflict to generate only one constraint i,si,kiti according the priority of users and the type of this conflict. The priority can determine which agent to change the node selection in case of a path conflict (i.e., determine which user’s constraint to generate). It can be set manually by the importance of the user or other factors. The constraint i,si,kiti indicates that the path of agent i cannot contain node si,kiti. There may be multiple conflicts in πk, and a new set of constraints Ω is generated.For each constraintωi∈Ω (lines 26–40), a new set of constraints Ωl is generated by combining ωi with Ωk. Then, agent i executes the Individualsearch procedure to get individual Pareto-optimal solution set Oi∗ under the restriction of constraints Ωli of user i in Ωl. Hereafter, for each oi∗, we get a new solution πl by copying πk and then replace πli in πl with oi∗. If there is no vector dominating the cost vector cl of πl in P1, a new search node Rlπl,cl,Ωl is created and added into the OPEN. This system stage continues until there is no search node in the OPEN.Algorithm 1: Pseudocode for CR-MOMAPF-based handover strategy.
Input: a distance file of all usersOutput:P, P11:Initialization stage:2: Build a set of directed graphs for all users from the distance file3:P⟵∅, P1⟵∅, OPEN⟵∅4:for each user i in Ndo5:Oi⟵Individualsearchi,∅6:end for7: Generate a set of joint pathsΠ8:for all πk∈Πdo9:Ωk⟵∅10:ck⟵compute path cost of πk11: CreateRkπk,ck,Ωk and add it to OPEN12:end for13:Search stage:14:whileOPENnot empty do15:Rkπk,ck,Ωk⟵OPEN.pop.16:ifCheckRk=Falsethen17:UpdateP, UpdateP118:  Addπk to P and ck to P119:else20:Continue21:end if22:if no conflict detected in πkthen23:Continue24:else25:Ω⟵split detected conflict26:for each ωi∈Ωdo27:Ωl=Ωk∪ωi28:Oi∗⟵Individualsearchi,Ωli29:for all oi∗∈Oi∗do30:πl⟵πk31:    Replaceπli in πl with oi∗32:cl⟵compute path cost of πl33:    CreateRlπl,cl,Ωl34:ifCheckRl=Falsethen35:     AddRl to OPEN36:else37:Continue38:end if39:end for40:end for41:end if42:end while43:returnP, P1


## 3.1. Initialization Stage

In the initialization stage, according to the Two-Line Orbital Element (TLE) information of the satellite constellation, each user calculates the distance of the satellite within multiple timestamps. To implement the path planning algorithm, a directed graphGi is constructed for each user i, and various weights and meanings are given to the edges and nodes in the graph according to the distance file and the previously mentioned channel model. Then, P (the Pareto-optimal solution set), P1 (the Pareto-front), and OPEN (node set to be searched) are set as empty sets. Based on the graph Gi, aiming at minimizing f1i and maximizing f2i, each user i executes Individualsearch procedure (i.e., multiobjective single-agent path finding algorithm) to find individual Pareto-optimal solution set Oi without constraint.


## 3.2. Search Stage

In this stage, a set of joint pathsΠ is generated by taking the combination of Oi, ∀i∈N, i.e., Π=πkπk=πk1,πk2,⋯,πkN,πki∈Oi,∀i∈N. Then, for each joint path πk∈Π, ck, πk, and the constraints (empty set) are combined to form a search node Rkπk,ck,Ωk and added to OPEN.For each search iteration in CR-MOMAPF (lines 14-42), a search nodeRkπk,ck,Ωk is popped from OPEN. Then, the Check procedure is exploited to determine whether the node Rk is worth continuing the search. If there is no vector dominating ck in P1 (i.e., CheckRk=False), we think node Rk is worth continuing to search, otherwise the node is discarded. With the Update procedure, those cost vectors dominated by ck in P1 and their corresponding strategies are removed from P1 and P, respectively. Then, πk and ck are added into P and P1, respectively. The procedure Update is necessary due to the fact that it can ensure that the vectors in P1 are Pareto-optimal in the whole search iteration progress. As a result, P1 is guaranteed to be the excellent Pareto-optimal front when the algorithm terminates.If there is no conflict inπk, then πk is a Pareto-optimal solution because it has the best performance in terms of f¯3 and no other vector can dominate it. If a conflict i,j,si,kiti,sj,kjtj,λ is detected in πk, we adopt the splitconflictapproach in CBS to resolve the detected conflict. However, different from CBS, here, we split a detected conflict to generate only one constraint i,si,kiti according the priority of users and the type of this conflict. The priority can determine which agent to change the node selection in case of a path conflict (i.e., determine which user’s constraint to generate). It can be set manually by the importance of the user or other factors. The constraint i,si,kiti indicates that the path of agent i cannot contain node si,kiti. There may be multiple conflicts in πk, and a new set of constraints Ω is generated.For each constraintωi∈Ω (lines 26–40), a new set of constraints Ωl is generated by combining ωi with Ωk. Then, agent i executes the Individualsearch procedure to get individual Pareto-optimal solution set Oi∗ under the restriction of constraints Ωli of user i in Ωl. Hereafter, for each oi∗, we get a new solution πl by copying πk and then replace πli in πl with oi∗. If there is no vector dominating the cost vector cl of πl in P1, a new search node Rlπl,cl,Ωl is created and added into the OPEN. This system stage continues until there is no search node in the OPEN.Algorithm 1: Pseudocode for CR-MOMAPF-based handover strategy.
Input: a distance file of all usersOutput:P, P11:Initialization stage:2: Build a set of directed graphs for all users from the distance file3:P⟵∅, P1⟵∅, OPEN⟵∅4:for each user i in Ndo5:Oi⟵Individualsearchi,∅6:end for7: Generate a set of joint pathsΠ8:for all πk∈Πdo9:Ωk⟵∅10:ck⟵compute path cost of πk11: CreateRkπk,ck,Ωk and add it to OPEN12:end for13:Search stage:14:whileOPENnot empty do15:Rkπk,ck,Ωk⟵OPEN.pop.16:ifCheckRk=Falsethen17:UpdateP, UpdateP118:  Addπk to P and ck to P119:else20:Continue21:end if22:if no conflict detected in πkthen23:Continue24:else25:Ω⟵split detected conflict26:for each ωi∈Ωdo27:Ωl=Ωk∪ωi28:Oi∗⟵Individualsearchi,Ωli29:for all oi∗∈Oi∗do30:πl⟵πk31:    Replaceπli in πl with oi∗32:cl⟵compute path cost of πl33:    CreateRlπl,cl,Ωl34:ifCheckRl=Falsethen35:     AddRl to OPEN36:else37:Continue38:end if39:end for40:end for41:end if42:end while43:returnP, P1


## 4. Simulation and Result

### 4.1. Scene Construction

To evaluate the effectiveness of the proposed algorithm, we first build a scene including a LEO satellite constellation and some ground users. For the satellite constellation, we build a typical LEO satellite constellation, Starlink, according to the constellation data in [37]. The parameters of this Starlink constellation are provided in Table 1, and the visualization is shown in Figure 4.Table 1
Scene parameters.
ParametersValuesAltitude550 kmOrbital planes24Satellites per plane66Inclination53°Satellite half angle of view44.85°Minimum communication elevation40°Figure 4
Huge LEO satellite constellation, Starlink, which is drawn by cesium [38].Due to the huge difference in the mobile speed between LEO satellites and ground users, we assume that the ground users are stationary and select some cities to represent the ground users. Their position parameters, number of visible satellites, and priority are provided in Tables2 and 3. Num represents the average number of satellites simultaneously covering the ground user in the whole constellation period. In the first type of conflict i,j,si,kiti,sj,kjtj,1 between two users, the user with lower priority needs to change the policy to reduce the number of conflicts. In the second type of conflict i,j,si,kiti,sj,kjtj,2 between two users, user i needs to change the policy. In this paper, we take NSGAIII [26] as the algorithm of the Individualsearch procedure and priority-based coding [39] as the coding method of NSGAIII. Other parameters used to calculate the objective function are shown in Table 4.Table 2
The parameters of cities.
ScenarioCityLat/Lon (°)NumPriority1 (sparse)Guangzhou29.13/113.262.970Tokyo35.69/139.693.861Sydney-33.87/151.213.672Xi’an34.29/108.943.713Islamabad33.70/73.063.6542 (general)Chongqing29.56/106.553.320Chengdu30.67/104.073.391Xi’an34.29/108.943.712Changsha28.23/112.943.143Wuhan30.58/114.273.4043 (dense)Shanghai31.22/121.463.430Nanjing32.05/118.793.511Wuxi31.54/120.303.472Hangzhou30.29/120.163.373Hefei31.86/117.283.494Table 3
The parameters of cities.
CityLat/Lon (°)NumPriorityChongqing29.56/106.553.320Chengdu30.67/104.073.391Xi’an34.29/108.943.712Changsha28.23/112.943.143Wuhan30.58/114.273.404Shanghai31.22/121.463.435Nanchang28.68/115.883.256Zhengzhou34.76/113.653.757Hangzhou30.29/120.163.378Hefei31.86/117.283.499Lanzhou36.06/103.793.9110Kunming25.04/102.723.0611Taiyuan37.86/112.554.1612Guiyang26.58/106.723.1613Beijing39.91/116.404.4814Table 4
The parameters of simulation.
ParametersValuesTransmission signal power of each satellite50 dBwCarrier frequency6 GHzs of shadowing4 dBKr for Rician fading10T50Duration of each timestamp10 sPopulation size ofIndividualsearch1000Evolution algebra ofIndividualsearch1000Cross rate ofIndividualsearch0.9Variation rate ofIndividualsearch0.2Parameters in Equation (1)η=0.55, D=3 mBd1 MHzTtem290 KCNRmin4 dBNjmax3Fj2200 MIPS [30]B6.6 M [30]


### 4.2.Individualsearch Procedure Performance Analysis

Here, we analyze the factors affectingf1i and f2i calculated by the Individualsearch procedure. Given a specific number of users in the scenario, we use three levels to measure the density of these users. The first level is sparse, which means that no satellite can cover multiple users at the same time. The second level is general, which means that a single satellite can cover multiple users at the same time, but not all users. The third level is dense, which indicates that a single satellite can cover all ground users. We construct three scenarios with different user density levels, and the initial Pareto fronts of users obtained by Individualsearchi,∅ procedure are shown in Figure 5. The user’s location (latitude, longitude) is used to represent the user, and different colored Pareto fronts belong to different users. The bidirectional Hausdorff distance values [40] between any two of the three Pareto fronts of the blue user (i.e., user with location (30, 104)) in the three scenarios are 0. So, these three Pareto-front are exactly the same. This indicates that user density does not affect handover times and received signal power of a single user. In addition to the constraints of the paths of users (i.e., the parameters of Individualsearch. procedure), f1i and f2i are only affected by their own location (i.e., longitude and latitude).Figure 5
The initial Pareto front of users with different density levels of users: (a) sparse; (b) general; (c) dense.
(a)(b)(c)


### 4.3. CR-MOMAPF with Different Density Levels of Users

We construct three scenarios with 5 ground users each based on the user density levels in Section4.2. The parameters of users are shown in Table 3. Depending on the Num parameter value of each user in Table 2, we set the Ki of user i to 3 or 4. The Pareto front of the proposed algorithm with different density levels of users is shown in Figure 6. Eight solutions in each scenario are randomly selected from their Pareto-optimal solution sets and then presented in Table 5. The corresponding numbers of Pareto-optimal solutions obtained in the three scenarios are 19, 56, and 99, respectively. So, the number of Pareto-optimal solutions increases when the density level grows. In addition, through comparison, we can observe that the average number of conflicts also increases when the density level grows. In other words, the Pareto front becomes higher when the density level grows. Specifically, when the distance between any two users in the scenario is greater than the coverage diameter of a single satellite, there can be no conflict between users. In this case, the problem in this paper becomes a two-objective optimization problem. As described in Section 4.2, f1i and f2i are only affected by the user’s location. So, for average handover times and average signal reception strength, their own distribution differences in different scenarios are caused by the differences in the location of users and the constraints generated by conflictsplit.Figure 6
The Pareto front with different density levels of users: (a) Scenario 1 (sparse); (b)Scenario 2 (general); (c) Scenario 3 (dense).
(a)(b)(c)Table 5
Some results to show the trade-off among different objectives.
(a)ObjScenario 1 (N=5, sparse)Scenario 2 (N=5, general)x1x2x3x4x5x6x7x8x1x2x3x4x5x6x7x8f1¯8.44.8∗6.87.65.06.45.27.26.45.0∗6.65.66.26.65.47.2f2¯1.650∗1.6121.6471.6491.6201.6461.6281.6481.730∗1.6791.6741.7221.6861.7271.7071.706f3¯0.00.00.0∗0.00.00.00.00.02.82.41.6∗3.01.82.62.42.0(b)ObjScenario 3 (N=5, dense)Scenario 4 (N=10, general)x1x2x3x4x5x6x7x8x1x2x3x4x5x6x7x8f1¯6.64.6∗6.25.25.66.45.85.27.14.8∗6.96.36.25.86.76.4f2¯1.643∗1.5711.5121.6301.6341.6411.6371.5541.695∗1.6371.5851.6911.6931.6881.6941.694f3¯16.28.06.4∗11.011.213.211.87.47.14.82.7∗4.95.35.05.85.8(c)ObjScenario 5 (N=15, general)x1x2x3x4x5x6x7x8Weighted-basedMHT-basedMCT-basedRSS-basedf1¯6.94.9∗5.76.05.64.96.45.515.63.035.87.3f2¯1.681∗1.6181.6231.6661.6331.6291.6791.6381.2701.3881.1651.690f3¯4.93.53.1∗3.93.33.84.83.33.33.80.96.8∗ represents that this value is the optimal value of the objective function in the Pareto-optimal solution set.


### 4.4. Unilateral Performance with Different Strategies

Here, we compare the performance of the proposed CR-MOMAPF with the following handover strategies:(1)
RSS-based strategy [41]: each ground user accesses the satellite that provides the strongest signal strength within each timestamp(2)
Minimum handover time- (MHT-) based handover strategy: based on the graph in [22], we set the weight of the edge as handover times and adopt Dijkstra’s shortest path algorithm to realize this handover strategy(3)
Minimum conflict time- (MCT-) based handover strategy: different ground users try to select different satellites for access within each timestamp. Based on geatpy [42], we adopt SOGA (single-objective genetic algorithm) to realize the handover strategy(4)
Weighted-based handover strategy [43]: the weight of the received signal strength, the handover times, and the conflict times are set as by w1=1/3, w2=1/3, and w3=1/3. Then, we exploit single-objective optimization to get the optimal solution based on geatpyIn this simulation, in order to make the results more obvious, we set more users in the scene. We take 15 cities in Table3 as ground users. The Pareto front obtained by CR-MOMAPF is shown in Figure 7. The Pareto-optimal solution set contains 427 solutions. We randomly select a solution from it and show the performance difference between this solution and the solutions of other strategies in Figure 8. From Figure 8(a), we can observe that users can receive the strongest signal strength under the RSS-based strategy, while the signal strength that users can receive under CR-MOMAPF is second only to the RSS-based strategy. Figure 8(b) shows the cumulative distribution of the number of handovers under each strategy. We can observe that the handover times of users under CR-MOMAPF are second only to those of MHT-based strategy and better than those of the other three strategies. As for the number of user conflicts, it can be observed from Figure 8(c) that CR-MOMAPF is better than the RSS-based strategy and worse than MCT-based strategy. Compared with MHT-based and weighted-based strategy, CR-MOMAPF does not have obvious advantage in the average number of conflicts. This is due to the fact that reducing the number of handovers can reduce the number of conflicts to a certain extent, which is known from the definition of user conflict. However, from the total number of conflicts, there are 47 conflicts in CR-MOMAPF, which is better than 57 conflicts under the MHT-based strategy and 50 conflicts under weighted-based strategy.Figure 7
The Pareto front of the scenario withN=15.Figure 8
Performance of users with different handover strategies: (a) received signal strength; (b) handover times; (c) conflict times.
(a)(b)(c)Subsequently, we calculate the handover delay of each strategy based on formula (14). Figure 9 shows the change of the cumulative handover delay of all users with time. The CR-MOMAPF strategy in the figure is a solution randomly selected from the Pareto-optimal solution set. We can observe that the handover delay of the CR-MOMAPF strategy is second only to the MHT-based strategy. This is because the latter has the least number of handovers. Then, for each of these handover strategies, we count the average delay of each handover. The average handover delay is 27.68 ms for the MCT-based strategy, 25.94 ms for the weighted-based strategy, 19.87 ms for the MHT-based strategy, and 19.53 ms for the RSS-based strategy. The average handover delay of CR-MOMAPF is the best, which is 17.96 ms.Figure 9
Comparison of accumulative handover delay for five different handover strategies.Without loss of generality, we count the performance of all solutions in the Pareto-optimal solution set and compare them with the other four strategies. We find that the cumulative handover delay of all solutions in the solution set is second only to the MHT-based strategy. Moreover, 89% of the solutions in the Pareto-optimal solution set (i.e., 381 solutions) have the lowest average handover delay. The handover efficiency is improved by up to 28.31% compared with the RSS-based strategy, 29.54% compared with the MHT-based strategy, 49.41% compared with the MCT-based strategy, and 46.03% compared with the weighted-based strategy.Finally, we compare the handover success rate under different strategies, and the results are shown in Figure10. We can see that the solution randomly selected from the Pareto-optimal set of CR-MOMAPF has the highest handover success rate. To avoid accidents, we calculate the handover success rate of all solutions in the Pareto-optimal solution set. It is found that the lowest handover success rate is 98.76%, and the highest handover success rate is 100%. This is due to the fact that the three optimization objectives of our proposed algorithm improve the users’ signal quality, reduce the number of handovers, and make the users choose the lightly loaded satellites for handover as much as possible.Figure 10
Comparison of handover success rate for five different handover strategies.In summary, our algorithm can comprehensively optimize three objectives, which further optimize the handover delay and handover success rate. Compared with the other four strategies, most of the solutions in the Pareto-optimal solution set have the best performances. The decision maker can select the appropriate handover strategy from the Pareto-optimal solution set according to the user classification.


### 4.5. Comprehensive Performance with Different Strategies

In this simulation, we design an index to evaluate the comprehensive performance of a solution. We firstly calculate the extremum of these three performance indexes in this problem. Then, we exploit min-max normalization to normalize the three indexes of a solution and sum them to get the evaluation indexEI of the solution. EI is given by
(19)EI=−pnormal+hnormal+cnormal,where pnormal, hnormal, and cnormal are the normalized values of the received signal strength, handover times, and the number of conflicts of a solution. It can be known that the smaller the EI value of the solution, the better the comprehensive performance of the solution. In this way, we compare the solutions obtained by each handover strategy.Based on the cities in Table3, we select three groups of users for this simulation. The first group is the top 5 cities (N=5), the second group is the top 10 cities (N=10), and the third group is all 15 cities (N=15). The Pareto front obtained in these three scenarios is shown in Figures 6(b), 7, and 11, respectively. Eight solutions in each scenario are randomly selected from their Pareto-optimal solution sets and then presented in Table 5. As is shown in Figure 12, in the three scenarios, the comprehensive performance of randomly selected solutions in the Pareto-optimal solution sets obtained by CR-MOMAPF is the best. MCT-based strategy produces too many handovers to reduce the number of conflicts, resulting in the worst comprehensive performance. Subsequently, to avoid contingency, we calculate the EI values of all solutions in the Pareto front. The results show that in the scenarios of N=5, N=10, and N=15, the solutions with the best comprehensive performance account for 62.5%, 87.83%, and 97.89%, respectively. The remaining solutions have the second best comprehensive performance. This means that there is a great possibility that selecting a solution from the Pareto-optimal solution set will have the best comprehensive performance.Figure 11
The Pareto front of the scenario withN=10.Figure 12
EI values of solutions under different strategies.


## 4.1. Scene Construction

To evaluate the effectiveness of the proposed algorithm, we first build a scene including a LEO satellite constellation and some ground users. For the satellite constellation, we build a typical LEO satellite constellation, Starlink, according to the constellation data in [37]. The parameters of this Starlink constellation are provided in Table 1, and the visualization is shown in Figure 4.Table 1
Scene parameters.
ParametersValuesAltitude550 kmOrbital planes24Satellites per plane66Inclination53°Satellite half angle of view44.85°Minimum communication elevation40°Figure 4
Huge LEO satellite constellation, Starlink, which is drawn by cesium [38].Due to the huge difference in the mobile speed between LEO satellites and ground users, we assume that the ground users are stationary and select some cities to represent the ground users. Their position parameters, number of visible satellites, and priority are provided in Tables2 and 3. Num represents the average number of satellites simultaneously covering the ground user in the whole constellation period. In the first type of conflict i,j,si,kiti,sj,kjtj,1 between two users, the user with lower priority needs to change the policy to reduce the number of conflicts. In the second type of conflict i,j,si,kiti,sj,kjtj,2 between two users, user i needs to change the policy. In this paper, we take NSGAIII [26] as the algorithm of the Individualsearch procedure and priority-based coding [39] as the coding method of NSGAIII. Other parameters used to calculate the objective function are shown in Table 4.Table 2
The parameters of cities.
ScenarioCityLat/Lon (°)NumPriority1 (sparse)Guangzhou29.13/113.262.970Tokyo35.69/139.693.861Sydney-33.87/151.213.672Xi’an34.29/108.943.713Islamabad33.70/73.063.6542 (general)Chongqing29.56/106.553.320Chengdu30.67/104.073.391Xi’an34.29/108.943.712Changsha28.23/112.943.143Wuhan30.58/114.273.4043 (dense)Shanghai31.22/121.463.430Nanjing32.05/118.793.511Wuxi31.54/120.303.472Hangzhou30.29/120.163.373Hefei31.86/117.283.494Table 3
The parameters of cities.
CityLat/Lon (°)NumPriorityChongqing29.56/106.553.320Chengdu30.67/104.073.391Xi’an34.29/108.943.712Changsha28.23/112.943.143Wuhan30.58/114.273.404Shanghai31.22/121.463.435Nanchang28.68/115.883.256Zhengzhou34.76/113.653.757Hangzhou30.29/120.163.378Hefei31.86/117.283.499Lanzhou36.06/103.793.9110Kunming25.04/102.723.0611Taiyuan37.86/112.554.1612Guiyang26.58/106.723.1613Beijing39.91/116.404.4814Table 4
The parameters of simulation.
ParametersValuesTransmission signal power of each satellite50 dBwCarrier frequency6 GHzs of shadowing4 dBKr for Rician fading10T50Duration of each timestamp10 sPopulation size ofIndividualsearch1000Evolution algebra ofIndividualsearch1000Cross rate ofIndividualsearch0.9Variation rate ofIndividualsearch0.2Parameters in Equation (1)η=0.55, D=3 mBd1 MHzTtem290 KCNRmin4 dBNjmax3Fj2200 MIPS [30]B6.6 M [30]


## 4.2.Individualsearch Procedure Performance Analysis

Here, we analyze the factors affectingf1i and f2i calculated by the Individualsearch procedure. Given a specific number of users in the scenario, we use three levels to measure the density of these users. The first level is sparse, which means that no satellite can cover multiple users at the same time. The second level is general, which means that a single satellite can cover multiple users at the same time, but not all users. The third level is dense, which indicates that a single satellite can cover all ground users. We construct three scenarios with different user density levels, and the initial Pareto fronts of users obtained by Individualsearchi,∅ procedure are shown in Figure 5. The user’s location (latitude, longitude) is used to represent the user, and different colored Pareto fronts belong to different users. The bidirectional Hausdorff distance values [40] between any two of the three Pareto fronts of the blue user (i.e., user with location (30, 104)) in the three scenarios are 0. So, these three Pareto-front are exactly the same. This indicates that user density does not affect handover times and received signal power of a single user. In addition to the constraints of the paths of users (i.e., the parameters of Individualsearch. procedure), f1i and f2i are only affected by their own location (i.e., longitude and latitude).Figure 5
The initial Pareto front of users with different density levels of users: (a) sparse; (b) general; (c) dense.
(a)(b)(c)


## 4.3. CR-MOMAPF with Different Density Levels of Users

We construct three scenarios with 5 ground users each based on the user density levels in Section4.2. The parameters of users are shown in Table 3. Depending on the Num parameter value of each user in Table 2, we set the Ki of user i to 3 or 4. The Pareto front of the proposed algorithm with different density levels of users is shown in Figure 6. Eight solutions in each scenario are randomly selected from their Pareto-optimal solution sets and then presented in Table 5. The corresponding numbers of Pareto-optimal solutions obtained in the three scenarios are 19, 56, and 99, respectively. So, the number of Pareto-optimal solutions increases when the density level grows. In addition, through comparison, we can observe that the average number of conflicts also increases when the density level grows. In other words, the Pareto front becomes higher when the density level grows. Specifically, when the distance between any two users in the scenario is greater than the coverage diameter of a single satellite, there can be no conflict between users. In this case, the problem in this paper becomes a two-objective optimization problem. As described in Section 4.2, f1i and f2i are only affected by the user’s location. So, for average handover times and average signal reception strength, their own distribution differences in different scenarios are caused by the differences in the location of users and the constraints generated by conflictsplit.Figure 6
The Pareto front with different density levels of users: (a) Scenario 1 (sparse); (b)Scenario 2 (general); (c) Scenario 3 (dense).
(a)(b)(c)Table 5
Some results to show the trade-off among different objectives.
(a)ObjScenario 1 (N=5, sparse)Scenario 2 (N=5, general)x1x2x3x4x5x6x7x8x1x2x3x4x5x6x7x8f1¯8.44.8∗6.87.65.06.45.27.26.45.0∗6.65.66.26.65.47.2f2¯1.650∗1.6121.6471.6491.6201.6461.6281.6481.730∗1.6791.6741.7221.6861.7271.7071.706f3¯0.00.00.0∗0.00.00.00.00.02.82.41.6∗3.01.82.62.42.0(b)ObjScenario 3 (N=5, dense)Scenario 4 (N=10, general)x1x2x3x4x5x6x7x8x1x2x3x4x5x6x7x8f1¯6.64.6∗6.25.25.66.45.85.27.14.8∗6.96.36.25.86.76.4f2¯1.643∗1.5711.5121.6301.6341.6411.6371.5541.695∗1.6371.5851.6911.6931.6881.6941.694f3¯16.28.06.4∗11.011.213.211.87.47.14.82.7∗4.95.35.05.85.8(c)ObjScenario 5 (N=15, general)x1x2x3x4x5x6x7x8Weighted-basedMHT-basedMCT-basedRSS-basedf1¯6.94.9∗5.76.05.64.96.45.515.63.035.87.3f2¯1.681∗1.6181.6231.6661.6331.6291.6791.6381.2701.3881.1651.690f3¯4.93.53.1∗3.93.33.84.83.33.33.80.96.8∗ represents that this value is the optimal value of the objective function in the Pareto-optimal solution set.


## 4.4. Unilateral Performance with Different Strategies

Here, we compare the performance of the proposed CR-MOMAPF with the following handover strategies:(1)
RSS-based strategy [41]: each ground user accesses the satellite that provides the strongest signal strength within each timestamp(2)
Minimum handover time- (MHT-) based handover strategy: based on the graph in [22], we set the weight of the edge as handover times and adopt Dijkstra’s shortest path algorithm to realize this handover strategy(3)
Minimum conflict time- (MCT-) based handover strategy: different ground users try to select different satellites for access within each timestamp. Based on geatpy [42], we adopt SOGA (single-objective genetic algorithm) to realize the handover strategy(4)
Weighted-based handover strategy [43]: the weight of the received signal strength, the handover times, and the conflict times are set as by w1=1/3, w2=1/3, and w3=1/3. Then, we exploit single-objective optimization to get the optimal solution based on geatpyIn this simulation, in order to make the results more obvious, we set more users in the scene. We take 15 cities in Table3 as ground users. The Pareto front obtained by CR-MOMAPF is shown in Figure 7. The Pareto-optimal solution set contains 427 solutions. We randomly select a solution from it and show the performance difference between this solution and the solutions of other strategies in Figure 8. From Figure 8(a), we can observe that users can receive the strongest signal strength under the RSS-based strategy, while the signal strength that users can receive under CR-MOMAPF is second only to the RSS-based strategy. Figure 8(b) shows the cumulative distribution of the number of handovers under each strategy. We can observe that the handover times of users under CR-MOMAPF are second only to those of MHT-based strategy and better than those of the other three strategies. As for the number of user conflicts, it can be observed from Figure 8(c) that CR-MOMAPF is better than the RSS-based strategy and worse than MCT-based strategy. Compared with MHT-based and weighted-based strategy, CR-MOMAPF does not have obvious advantage in the average number of conflicts. This is due to the fact that reducing the number of handovers can reduce the number of conflicts to a certain extent, which is known from the definition of user conflict. However, from the total number of conflicts, there are 47 conflicts in CR-MOMAPF, which is better than 57 conflicts under the MHT-based strategy and 50 conflicts under weighted-based strategy.Figure 7
The Pareto front of the scenario withN=15.Figure 8
Performance of users with different handover strategies: (a) received signal strength; (b) handover times; (c) conflict times.
(a)(b)(c)Subsequently, we calculate the handover delay of each strategy based on formula (14). Figure 9 shows the change of the cumulative handover delay of all users with time. The CR-MOMAPF strategy in the figure is a solution randomly selected from the Pareto-optimal solution set. We can observe that the handover delay of the CR-MOMAPF strategy is second only to the MHT-based strategy. This is because the latter has the least number of handovers. Then, for each of these handover strategies, we count the average delay of each handover. The average handover delay is 27.68 ms for the MCT-based strategy, 25.94 ms for the weighted-based strategy, 19.87 ms for the MHT-based strategy, and 19.53 ms for the RSS-based strategy. The average handover delay of CR-MOMAPF is the best, which is 17.96 ms.Figure 9
Comparison of accumulative handover delay for five different handover strategies.Without loss of generality, we count the performance of all solutions in the Pareto-optimal solution set and compare them with the other four strategies. We find that the cumulative handover delay of all solutions in the solution set is second only to the MHT-based strategy. Moreover, 89% of the solutions in the Pareto-optimal solution set (i.e., 381 solutions) have the lowest average handover delay. The handover efficiency is improved by up to 28.31% compared with the RSS-based strategy, 29.54% compared with the MHT-based strategy, 49.41% compared with the MCT-based strategy, and 46.03% compared with the weighted-based strategy.Finally, we compare the handover success rate under different strategies, and the results are shown in Figure10. We can see that the solution randomly selected from the Pareto-optimal set of CR-MOMAPF has the highest handover success rate. To avoid accidents, we calculate the handover success rate of all solutions in the Pareto-optimal solution set. It is found that the lowest handover success rate is 98.76%, and the highest handover success rate is 100%. This is due to the fact that the three optimization objectives of our proposed algorithm improve the users’ signal quality, reduce the number of handovers, and make the users choose the lightly loaded satellites for handover as much as possible.Figure 10
Comparison of handover success rate for five different handover strategies.In summary, our algorithm can comprehensively optimize three objectives, which further optimize the handover delay and handover success rate. Compared with the other four strategies, most of the solutions in the Pareto-optimal solution set have the best performances. The decision maker can select the appropriate handover strategy from the Pareto-optimal solution set according to the user classification.


## 4.5. Comprehensive Performance with Different Strategies

In this simulation, we design an index to evaluate the comprehensive performance of a solution. We firstly calculate the extremum of these three performance indexes in this problem. Then, we exploit min-max normalization to normalize the three indexes of a solution and sum them to get the evaluation indexEI of the solution. EI is given by
(19)EI=−pnormal+hnormal+cnormal,where pnormal, hnormal, and cnormal are the normalized values of the received signal strength, handover times, and the number of conflicts of a solution. It can be known that the smaller the EI value of the solution, the better the comprehensive performance of the solution. In this way, we compare the solutions obtained by each handover strategy.Based on the cities in Table3, we select three groups of users for this simulation. The first group is the top 5 cities (N=5), the second group is the top 10 cities (N=10), and the third group is all 15 cities (N=15). The Pareto front obtained in these three scenarios is shown in Figures 6(b), 7, and 11, respectively. Eight solutions in each scenario are randomly selected from their Pareto-optimal solution sets and then presented in Table 5. As is shown in Figure 12, in the three scenarios, the comprehensive performance of randomly selected solutions in the Pareto-optimal solution sets obtained by CR-MOMAPF is the best. MCT-based strategy produces too many handovers to reduce the number of conflicts, resulting in the worst comprehensive performance. Subsequently, to avoid contingency, we calculate the EI values of all solutions in the Pareto front. The results show that in the scenarios of N=5, N=10, and N=15, the solutions with the best comprehensive performance account for 62.5%, 87.83%, and 97.89%, respectively. The remaining solutions have the second best comprehensive performance. This means that there is a great possibility that selecting a solution from the Pareto-optimal solution set will have the best comprehensive performance.Figure 11
The Pareto front of the scenario withN=10.Figure 12
EI values of solutions under different strategies.


## 5. Conclusions

(1)
A multiobjective multiagent optimization algorithm is proposed for solving the handover problem that is transformed into a path finding problem, and the transformation is implemented by the proposed multiple directed graph model. We conducted our experiments using the Starlink constellation and some terrestrial cities as scenarios(2)
The experimental results show that the algorithm finds a set of Pareto-optimal solutions for the users in the scenario. It is also shown that the average number of user conflicts in a multiuser scenario is related to the density of users. Additionally, the increase in the number of users may not lead to an increase in the number of conflicts. The number of handover and the average received signal strength are related to the location of users, but not to the density of users. Compared with other strategies, this strategy has advantages in terms of the number of solutions and the quality of performance(3)
In the future, we will study the handover strategy for multiple users with high-speed mobility and the point of incorporating handover strategy into handover protocols



---

*Source: 1111557-2023-01-30.xml*