{'fraction_non_alphanumeric': 0.03511545463255725, 'fraction_numerical': 0.007952476765354028, 'mean_word_length': 4.850616591928251, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Cooperative Beam Hopping for Accurate Positioning in Ultra-Dense LEO Satellite Networks

In ultra-dense LEO satellite networks, conventional communication-oriented beam pattern design cannot provide multiple favorable signals from different satellites simultaneously, and thus leads to poor positioning performance. To tackle this issue, in this paper, we propose a novel cooperative beam hopping (BH) framework to adaptively tune beam layouts suitable for multi-satellite coordinated positioning. On this basis, a joint user association, BH design and power allocation optimization problem is formulated to minimize average Cram\'er-Rao lower bound (CRLB). An efficient flexible BH control algorithm (FBHCA) is then proposed to solve the problem. Finally, a thorough experimental platform is built following the Third Generation Partnership Project (3GPP) defined non-terrestrial network (NTN) simulation parameters to validate the performance gain of the devised algorithm. The numerical results demonstrate that FBHCA can significantly improve CRLB performance over the benchmark scheme.


I. INTRODUCTION
With the advent of New Space era, satellite communication has gained a renewed upsurge due to its ability to provide global wireless coverage and continuous service guarantee especially in scenarios not optimally supported by terrestrial infrastructures [1], [2]. Specifically, some standardization endeavors have been sponsored by the Third Generation Partnership Project (3GPP) to study a set of necessary adaptations enabling the operation of 5G New Radio (NR) protocol in nonterrestrial network (NTN) with a priority on satellite access [3], [4]. In the NTN context, compared with conventional geostationary earth orbit (GEO) and medium earth orbit (MEO), low earth orbit (LEO) based satellite networks stand out as a promising solution concerning the lower propagation delay, power consumption and launch cost. As such, numerous companies have announced ambitious plans to provide broadband Internet access over the globe by deploying LEO satellite mega-constellations, e.g., Oneweb, Kuiper and Starlink.
On the other hand, the rapid proliferation of locationbased services, e.g., smart transportation, augmented reality and autonomous driving, bring marvellous value-added opportunities to communication networks. Besides, location-aided communication optimization such as enhanced access control and simplified mobility management can be fully exploited to improve network scalability, latency, and robustness [5]. Given those benefits, it is imperative to provide high precision positioning information on top of communication networks. As stipulated by NR Release-16, a positioning accuracy of 3-meter within 1 second end to end latency should be achieved for commercial use cases, and subsequent releases are expected to further realize sub-meter localization accuracy and millisecond level lower latency [6]. This induces great challenge to meet such stringent requirements.
To circumvent this issue, a plenty of research efforts on localization techniques have been conducted from both the academic and industry communities [7], [8]. In terrestrial cellular networks, numerous ranging measurement based positioning schemes, e.g., time of arrival (TOA), time difference of arrival (TDOA), angle of arrival (AOA), and received signal strength (RSS), are devised to figure out source location. Nevertheless, those positioning schemes cannot be directly applied to LEO satellite communication, owing to its unique characteristics such as dynamic network topology, strong multibeam interference, and channel model. While in the satellite scenario, state of the art positioning studies mainly focus on range error analysis, e.g., Cramér-Rao lower bound (CRLB), from a macroscopic constellation design perspective [9], [10]. However, the concrete multibeam structure design philosophy and underlying beam management problem to optimize positioning performance remain unexplored in LEO mega-constellation communication networks.
It is technically challenging to develop accurate positioning schemes for ultra-dense LEO satellite networks, due to several reasons: 1) A LEO satellite generally suffers from limited available onboard payload, and thus only a few physical transceivers/beams can be utilized. These beams should be efficiently shared for dual functional communication and positioning purposes. However, conventional communication oriented multibeam design cannot guarantee multiple strong signals from different satellites, and thus significantly degrades localization performance; 2) Since there is no near-far effect, the interference problem in satellite environment becomes critical. Besides, the fast mobility of LEO satellites makes the multibeam interference more complex and time-varying [11]; 3) To support accurate localization, it is essential to perform coordinate beam management among multiple satellites. The problem is quite difficult to handle considering both the nonlinearity of optimization metric and intrinsic coupling within user association, power/beam allocation and interference.
In this paper, to address the aforementioned challenges, we investigate the positioning oriented multibeam pattern design as well as the beam management problem in LEO megaconstellation communication system. The main contributions of this paper are summarized as follows. Firstly, we propose a novel cooperative beam hopping (BH) framework to flexibly tune the physical beam layout for optimized positioning usage. On the basis, an average CRLB minimization problem subject to user association, BH management and power allocation related constraints is formulated. Secondly, a flexible BH control algorithm (FBHCA) is proposed to decompose the original problem into three sub-problems, i.e., user association, BH design and power allocation sub-problems, which are further solved by max-SINR criteria, Voronoi diagram and semidefinite programming (SDP) technique, respectively. Finally, we provide extensive simulations in calibrated 3GPP NTN platform to evaluate the effectiveness of FBHCA and demonstrate its CRLB performance gain over existing schemes.
The remainder of this paper is organized as follows. Section II introduces the system model and presents the cooperative BH framework. The optimization problem formulation and corresponding FBHCA solution are investigated in Section III and Section IV, respectively. Section V provides the simulation results, followed by conclusions in Section VI.

A. System Model
We consider an orthogonal frequency division multiplexing (OFDM) based ultra-dense LEO multibeam satellite network. The satellite system operates at a center frequency f 0 with total system bandwidth W . To mitigate intra-satellite inter-beam interference, a frequency/polarization reuse factor of ρ is applied. For inter-satellite interference reduction, time/frequency/code domain multiplexing can be utilized, and such kind of interference is neglected. For example, the positioning reference signal design with frequency reuse and muting configuration in 3GPP LTE can mitigate inter-cell interference. In the network, there are a set of I = {1, . . . , I} LEO satellites. A satellite i ∈ I is equipped with a set of B = {1, . . . , B} beams. For beam allocation, we further define a binary variable γ i,b = 1 if beam i is allocated by satellite i, and γ i,b = 0 otherwise. A set of J = {1, . . . , J} user equipments (UEs) are distributed requesting for positioning service. For a user j ∈ J , the associated set of satellites used for positioning is denoted as I j = {1, . . . , I j }. The TDOA positioning scheme is adopted to calculate UE location results.
As per 3GPP NTN specifications [4], the following satellite antenna pattern is considered where J 1 (·) is the Bessel function of the first kind and first order with the argument, a is the antenna aperture radius, θ is the steering angle, and c is the light propagation speed. Meanwhile, the total path loss consists of following components: where SF is the shadow fading modeled by a log-normal distribution N (0, σ 2 SF ), d is the slant path distance, and P L g and P L s represent the atmospheric absorption and scintillation loss, respectively. The power P j i,b received by the j-th user from b-th beam of i-th satellite is where θ j i,b and d j i,b denote the angle and distance between user j and beam b in satellite i, respectively. Besides, EIRP i,b = P i,b + G T is the transmitted Equivalent Isotropically Radiated Power density allocated to beam b in satellite i, P i,b is the beam transmit power, and G T and G R denote the constant transmit and receive antenna gain, respectively. To this end, the overall signal-to-interference plus noise ratio (SINR) is where N 0 is the noise power determined by UE noise figure and antenna temperature [4].

B. Cooperative Beam Hopping Design
As a promising solution, BH is devised to employ only a small subset of transceivers/beams for serving extensive satellite coverage area. More specifically, assuming that a satellite aims to achieve a coverage of B cov beams by using B beams with B < B cov . For this purpose, at each time stamp, a maximum number of B beams are assigned to illuminate a portion of the whole satellite coverage area, and time-division multiplexing approach is implemented to manipulate the set of B beams into different portions within the coverage area of B cov beams. Through flexible beam allocation, full satellite coverage can be eventually served.
To support accurate positioning, we exploit BH to adaptively tune the physical beam layout from communication-oriented to positioning-oriented design. With cooperative BH from multiple neighboring satellites, localization performance can be significantly improved for UEs in a target satellite. An example BH for dual functional communication and positioning beams in a 4-satellite scenario is depicted in Fig. 1. On the one hand, communication beams are generally pointed to coverage area centered at the satellite nadir as in Fig. 1(a), such that seamless coverage is formed. On the other hand, to enhance localization performance, a set of neighbor satellites need to direct their beams to the target satellite. The center point of positioning beams normally stays far away from satellite nadir point. The cooperative BH patterns for positioning of Sat-1 and Sat-2 are sketched in Fig. 1(b) and Fig. 1(c), respectively.
An efficient UV plane based BH scheme (UVBHS) is devised for beam operation. As plotted in Fig. 2, UV plane is defined as the perpendicular plane to the satellite-earth line on the orbital plane. In UVBHS, a hexagonal beam layout is defined on the UV plane with UV coordinate of the nadir of the reference satellite setting to (0,0) for communication beams. For positioning beams, there are two different configuration situations. Firstly, to perform localization in its own service area, the satellite can simply reuse the communication configurations for positioning usage. Secondly, to assist localization Positioning beam coverage for Sat-1 Communication beam coverage Positioning beam coverage for Sat-2 for a neighboring satellite, the satellite needs to translate the beams centered at (0,0) to the center of the neighbor satellite's nadir in the UV plane denoted by (u, v). We can derive u = sinθcosϕ and v = sinθsinϕ, where θ and ϕ represent beam bore-sight steering angle and azimuth, respectively.

A. CRLB Analysis
In the mean squared error (MSE) sense, CRLB gives the lowest possible variance that an unbiased linear estimator can achieve. To this end, we use CRLB as the accuracy indicator for TDOA positioning error analysis.
1) TOA Measurement in OFDM system: For TDOA positioning, a set of TOA measurements from multiple satellites should be conducted at first. In an OFDM system, denote S l (k) as the signal allocated on the k-th subcarrier of the l-th symbol. The number of symbols and subcarriers used for positioning is expressed as N s and K, respectively. According to [12], under a static AWGN channel, the MSE σ i of TOA measurement τ i at satellite i is calculated by where T s is the OFDM symbol duration, δ j i,b denotes the association variable of user j to beam b in satellite i, and Γ = Ns−1 l=0 2) CRLB analysis for TDOA positioning: Based on the above TOA measurements, the CRLB for TDOA positioning at a target UE is explicitly analyzed herein. The positions of UE j ∈ J and satellites i ∈ I j are denoted as s = (x, y, z) T and s i = (x i , y i , z i ) T , i = 1, . . . , I j , respectively. The distance between the target UE j and satellite i is expressed as Without loss of generality, we choose s 1 as the reference satellite location. Under a line of sight (LOS) scenario prevalent in satellite context, the TDOA received by s i and s 1 is where e i is the TOA measurement noise with zero mean and covariance σ 2 i . The CRLB for estimating s in user j equals where tr{·} is the trace operator of matrix, and

B. Average CRLB Minimization Problem Optimization
Based on the envisioned cooperative BH framework, i.e., UVBHS, an average CRLB optimization problem is formulated to improve positioning accuracy.
In problem (9), the objective is to minimize average CRLB of UEs by optimizing decision variables δ = {δ j i,b }, P = {P i,b }, and γ = {γ i,b }. Constraints C1 states that each user should be associated to at most one beam at a given satellite; C2 specifies that the beam should be allocated once a user is associated to the beam, where Λ is a sufficiently large integer; C3 is the individual beam power constraint; and C4 is imposed to guarantee that the allocated power at a satellite should not exceed its total available power. The NP-hardness of the optimization problem is shown below.

Lemma 1. Problem (9) is NP-hard.
Proof: Consider a generalized case where power related constraints C3 and C4 are relaxed. To this end, (9) is reduced to the sensor selection problem [13], which is NP-hard with nonlinear objective and non-convex constraints. Thus, the NPhardness of the original problem is derived as well.
IV. PROPOSED SOLUTION Herein, the problem is first decomposed and an efficient FB-HCA solution is proposed, followed by complexity analysis.

A. Problem Decomposition based Solution
The problem (9) is solved by decomposing it into three subproblems, namely, user association sub-problem, BH design sub-problem, and power allocation sub-problem.
1) User association: To solve the user association subproblem, the following lemma is introduced.
According to the Matrix Inversion Lemma, we obtain On the basis, the CRLB expression can be equivalently written as follows i Ω ≪ 1 holds for a typical LEO satellite network, and thus the value of tr Y −1 dominates the final result. Consequently, CRLB j (s) decreases as β j i,b increases. According to Lemma 2, if the initial power allocation P (0) is given, the SINR β j i,b can be computed using (4). Therefore, δ j i,b is optimally solved by attaching user j to the beam with maximum SINR for satellite i, which is Note that for positioning purpose, association to multiple satellites is required for a UE. This is different from user attachment to only one serving satellite in communication oriented design. Given maximum SINR based user association criteria, the decisions of δ = {δ j i,b } are easily obtained. 2) BH design : After solving δ = {δ j i,b }, problem (9) can be further reformulated as where the objective is rewritten by using (11), and the auxiliary variable X satisfies Meanwhile, the constraint C7 in reformulated problem (13) is added based on the Schur complement law [13]. Since the only non-convex decision variables in problem (13) are γ = {γ i,b }, an efficient Voronoi diagram [14] is used to solve the beam allocation problem. More specifically, each beam corresponds to a polygon representing its serving coverage area. We set γ i,b = 1 if at least one user lies in the Voronoi area, and γ i,b = 0 otherwise. To this end, the BH design sub-problem is successfully tackled. An example Voronoi graph for a 10beam satellite is given in Fig. 3, where a polygon formed by several blue lines corresponds to a beam serving area. Note that because no UE attaches to beam 4 in Fig. 3, γ i,4 = 0 can be determined for the satellite.
3) Power allocation: Until now, the original problem is reduced to a power allocation problem with convex constraints min BH design: Construct Voronoi graph for beams in each satellite involved in the positioning process; 5: if At least one user lies in the Voronoi area then The above sub-problem (15) is a typical SDP problem, and can be efficiently solved by existing convex optimization methods, e.g., the interior-point method [15]. The obtained power results are capitalized to update the preceding power vector. Then, the algorithm moves forward to the next iteration. The iterations cease until a predetermined number M is reached. The detailed procedure of FBHCA is summarized in Algorithm 1.

B. Complexity Analysis
The computational complexity of the devised algorithm is

V. PERFORMANCE EVALUATION
In this section, simulation settings following 3GPP NTN assumptions are first configured. Afterwards, numerical results are presented to verify the effectiveness of the algorithm.

A. Simulation Settings
The set of key parameters used for simulations are summarized in Table I. Particularly, the satellite network comprises a total of 2400 satellites, with an orbit height varying from 800 km to 1500 km and inclination of 87.5 degree. The synchronization signal blocks (SSBs) in 3GPP NR are used for ToA measurements. The value of σ 2 SF for shadow fading is a function of elevation angle following Table 6.6.2-3 in [4]. For dynamic simulation, the orbit period is divided into 100 snapshots of equal time duration. A total of 500 stationary UEs are randomly deployed in the target area with longitude and latitude setting to [-70,-60] and [-5,5], respectively. Note that all simulations are performed by extending the already calibrated platform for 3GPP NTN [17].

B. Numerical Results
For comparison, two benchmark algorithms are used. One is the traditional method using communication beams (TMCB) for multi-satellite positioning as shown in Fig. 1(a). In TMCB,  maximum SINR based user association and equal power allocation among all satellite beams are assumed. The other one is termed as UVBHS-EPA, which combines the proposed UVBHS framework with equal power allocation. Fig. 4 depicts the average CRLB performance for different schemes as orbital height changes. As orbit height increases, the CRLB of all the three algorithms first decreases. The reason is that the constellation of 2400 satellites is not sufficient to provide full coverage for lower orbit height than around 1100 km. Lower orbit can cause worse SINR and positioning performance. With orbit height further rising, the CRLB increases as well due to the larger experienced path loss. Besides, both UVBHS-EPA and FBHCA significantly outperform TMCB in terms of CRLB. This is because in TMCB, although the received signal quality from the serving satellite is favorable, the signal quality from neighboring satellites is very poor due to the long distance between UE and beam center. Nonetheless, in the other two methods, neighboring satellite beams are directed to cover UEs of interest, and thus multiple signals with good quality can be measured to enhance positioning accuracy. To verify the performance gain, we list the SNR values of different satellites in Table II. The CRLB results for different schemes as time snapshot varies are given in Fig 5. The orbit height is fixed to 1200 km in the simulation. All the algorithms exhibit CRLB fluctuation as time snapshots change. The variation tendency is quite complicated, due to the intertwined influence by time varying inter-beam interference and dynamic geometric dilution of precision. Besides, as the number of positioning satellites increases from 6 to 8, the CRLBs for all the three algorithms improve as well. This phenomena can be expected, because more signals and better network geometry are obtained by exploring satellite diversity.

VI. CONCLUSION
In this paper, we have investigated the problem of high accuracy positioning in ultra-dense LEO satellite networks. A BH framework is proposed for flexible beam operation. With the framework, we further devise an efficient FBHCA solution to handle the joint user association, BH design, and power allocation problem. Significant positioning performance improvement in terms of average CRLB is demonstrated through 3GPP NTN simulation platform. As for future work, we tend to take inter-satellite interference issue into account and deal with the positioning reference signal design problem to further enhance localization accuracy.