A Novel Satellite PRN Code Assignment Method Based on Improved RLF Algorithm
<p>Satellite PRN code assignment diagram of a constellation composed of 11 satellites. Three colors represent three PRN codes, which are enough to realize CDMA for 11 satellites. (<b>a</b>) Three-dimensional view of the PRN code assignment; (<b>b</b>) Two-dimensional view of the PRN code assignment. The points are satellite positions. The circles are the range in which the satellite PRN codes can be received on the ground.</p> "> Figure 2
<p>The search process for navigation signal acquisition.</p> "> Figure 3
<p>The consistency description of the two problems from the perspective of input, condition and output. The graph on the right is a model of graph coloring problem. The description of the graph coloring problem is in blue, and the description of the satellite PRN code assignment problem is in black.</p> "> Figure 4
<p>Designed LEO constellations: (<b>a</b>) 48 LEO, 1414 km, walker; (<b>b</b>) 66 LEO, 778 km, polar; (<b>c</b>) 120 LEO, 1000 km, walker; (<b>d</b>) 192 LEO, 1200 km, polar; (<b>e</b>) 288 LEO, 1000 km, polar; (<b>f</b>) 576 LEO, 900 km, walker.</p> "> Figure 5
<p>Comparison of the optimal approximate solutions for the 6 algorithms. The parameters and methods used in the algorithm are as follows: <b>DFS</b>, We assigned PRN codes to satellites with few optional PRN codes as soon as possible; <b>GA</b>, The number of populations was 300, the Max Generation was 2000, and the program needed to be run multiple times; <b>Greedy</b>, The number of iterations was 100,000; <b>ACO</b>, 50 ants walked 2000 times, the decay factor was 0.99, and the program needed to be run multiple times; <b>SA</b>, The initial temperature was 10<sup>6</sup>, the temperature decay factor was 0.9, and the program needed to be run multiple times; <b>RLF</b>: The number of iterations was 20,000.</p> "> Figure 6
<p>Comparison of the calculation speed between the RLF algorithm and the improved-RLF algorithm. The satellite configuration was the walker 120/12/6 at an altitude of 1000 km. Both RLF and improved-RLF were run 10,000 times, and the number of iterations was 6000. With a probability of 0.0119, the solution of RLF algorithm was found to be greater than the approximate optimal solution, while in all experiments, the optimal solution was obtained in 6000 iterations with the improved-RLF algorithm.</p> "> Figure 7
<p>The probability of not approximate optimal solution varying with the number of iterations. The experimental method is the same as that in <a href="#sensors-22-05538-f006" class="html-fig">Figure 6</a>.</p> "> Figure 8
<p>Comparison of minimum PRN codes between the RLF algorithm and the improved-RLF algorithm. The satellite configuration was the walker 288/12/6 at an altitude of 1000 km and the walker 576/24/12 at an altitude of 900 km. Both the RLF and improved-RLF were run once with 10,000 iterations.</p> "> Figure 9
<p>Graph of Iridium PRN code assignment. Ten colors and numbers represent ten PRN codes, which are enough to realize CDMA for Iridium constellation.</p> "> Figure 10
<p>Graph of the orbital altitude and approximate minimum number of PRN codes. The blue line shows the approximate minimum number of PRN codes, and the orange line shows the number of conflicts. This is a polar-orbiting constellation at low altitudes of 300–3000 km, which is divided into 6 orbits with 11 satellites each. The number of conflicts is equal to the number of instances of 1 in the conflict matrix <math display="inline"><semantics> <mi>R</mi> </semantics></math>.</p> "> Figure 11
<p>The critical state of two satellites observed by the same user. O is the center of the Earth, and G1, G2, G3, and G4 are the locations of users. A, B, C, and D are satellites with the same orbital altitudes, which are uniformly distributed.</p> "> Figure 12
<p>Graph of Globalstar grouping multiplexed PRN codes. The Globalstar constellation is a walker 52°:48/8/1 constellation with an altitude of 1414 km. Eight colors and numbers represent eight PRN codes, which are enough to realize CDMA for Globalstar constellation.</p> "> Figure 13
<p>Graph of the orbital altitude and approximate minimum number of groups. The blue line shows the approximate minimum number of PRN codes, and the orange line shows the number of conflicts. This is a walker constellation similar to Globalstar, which is divided into 8 orbits with 11 satellites each. The orbital inclination is 52 degrees. The number of conflicts is equal to the number of instances of 1 in the conflict matrix <math display="inline"><semantics> <mi>R</mi> </semantics></math>.</p> "> Figure 14
<p>Graph of the orbital inclination and approximate minimum number of groups. The blue line shows the approximate minimum number of PRN codes, and the orange line shows the number of conflicts. This is a walker constellation similar to Globalstar, which is divided into 8 orbits with 11 satellites each. The orbital altitude is 1414 km. The number of conflicts is equal to the number of instances of 1 in the conflict matrix <math display="inline"><semantics> <mi>R</mi> </semantics></math>.</p> "> Figure 15
<p>Diagram of sub-satellite points in different satellite orbits. These two different colors represent two satellites with different orbits. The points are satellite positions. The circles show the range in which the satellite PRN codes can be received on the ground.</p> ">
Abstract
:1. Introduction
2. Methods and Mathematical Models
2.1. Feasibility and Benefits
2.2. Mathematical Model
2.3. Calculation Process
3. Algorithm
3.1. Algorithm Comparison
3.2. Algorithm Improvement
- Step 1: Initialization. Set to 0, and set . indicates the current PRN code and represents the set of unnumbered satellites. Proceed to 2.
- Step 2: Using the new PRN code, increase by 1 and set to empty. Then, proceed to 3.
- Step 3: Find the satellite set , and number each satellite in set as . There are two conditions. The first is that all satellites must be unnumbered, and the second is that all satellites must not conflict with satellites in . Proceed to 4.
- Step 4: Compute the degree of all satellites in and get the maximum degree. The satellite degree is the number of distinct PRN codes assigned to other non-conflicting satellites. Move all satellites with the maximum degree to . Proceed to 5.
- Step 5: Choose a satellite at random and assign a PRN code to satellite . In other words, move to and remove from . Return to Step 3.
- Step 6: Check whether . If so, all satellites are numbered, and the program should be stopped. If not, no other satellite fits this PRN code , so return to Step 2.
- Step 5: Choose a satellite at random and assign PRN code to satellite . In other words, move to and remove from . Return to Step 3.
4. Results
4.1. Polar-Orbiting Constellation
4.2. Walker Constellation
4.3. Hybrid Constellation
5. Discussion
6. Conclusions
- It is feasible and meaningful for several satellites sharing the same PRN code to save storage resources and reduce the satellite acquisition time of the receiver.
- The RLF algorithm is effective for calculating the minimum number of PRN codes, and the improved-RLF algorithm accelerates the calculation speed.
- In terms of satellite orbital parameters of polar-orbiting or walker constellations, the higher the altitude is, the more PRN codes needed. If other satellite parameters remain the same, no matter what the orbital inclination is, the minimum number of PRN codes remains the same.
- In terms of hybrid constellations, we recommend that, after calculating the minimum number of PRN codes for each polar-orbiting or walker constellation separately, the minimum PRN code number of a hybrid constellation will be equal to the sum of the minimum PRN code numbers of the partial constellations that make up the hybrid constellation.
Author Contributions
Funding
Data Availability Statement
Conflicts of Interest
References
- Teunissen, P.J.G.; Montenbruck, O. Springer Handbook of Global Navigation Satellite Systems; Springer: Cham, Switzerland, 2017. [Google Scholar]
- Wang, L.; Li, D.; Chen, R.; Fu, W.; Shen, X.; Jiang, H. The Low Earth Orbiter (LEO) Navigation Augmentation Technique-Opportunities and Challenges. Strateg. Study CAE 2020, 22, 1–12. [Google Scholar]
- Kube, C. Russia Has Figured out How to Jam U.S. Drones in Syria, Officials Say. NBC News. 10 April 2018. Available online: https://www.nbcnews.com/news/military/russia-has-figured-out-how-jam-u-s-drones-syrian863931 (accessed on 1 February 2022).
- Wang, L.; Chen, R.; Li, D.; Zhang, G.; Shen, X.; Yu, B.; Wu, C.; Xie, S.; Zhang, P.; Li, M.; et al. Initial Assessment of the LEO Based Navigation Signal Augmentation System from Luojia-1A Satellite. Sensors 2018, 18, 3919. [Google Scholar] [CrossRef] [PubMed] [Green Version]
- Satelles. Satelles Time and Location; White Paper; Satelles: Redwood, CA, USA, 2016. [Google Scholar]
- Ge, H.; Li, B.; Ge, M.; Zang, N.; Nie, L.; Shen, Y.; Schuh, H. Initial Assessment of Precise Point Positioning with LEO Enhanced Global Navigation Satellite Systems (LeGNSS). Remote Sens. 2018, 10, 984. [Google Scholar] [CrossRef] [Green Version]
- Li, X.; Ma, F.; Li, X.; Lv, H.; Bian, L.; Jiang, Z.; Zhang, X. LEO constellation-augmented multi-GNSS for rapid PPP convergence. J. Geod. 2018, 93, 749–764. [Google Scholar] [CrossRef]
- Wang, K.; El-Mowafy, A.; Qin, W.; Yang, X. Integrity Monitoring of PPP-RTK Positioning; Part I: GNSS-Based IM Procedure. Remote Sens. 2022, 14, 44. [Google Scholar] [CrossRef]
- Wang, K.; El-Mowafy, A.; Wang, W.; Yang, L.; Yang, X. Integrity Monitoring of PPP-RTK Positioning; Part II: LEO Augmentation. Remote Sens. 2022, 14, 1599. [Google Scholar] [CrossRef]
- GPS World Staff. Iridium Launches Alternative GPS PNT Service. GPS World. 23 May 2016. Available online: https://www.gpsworld.com/iridium-launches-alternative-gps-pnt-service/ (accessed on 1 February 2022).
- GPS World Staff. Spectracom, Satelles Sync in Multiple Indoor Locations. GPS World. 22 March 2017. Available online: https://www.gpsworld.com/spectracom-satelles-sync-in-multiple-indoor-locations/ (accessed on 1 February 2022).
- Cookman, J.; Gutt, G.; Lawrence, D. Single Chip Receiver for GNSS and LEO Constellations. In Proceedings of the 26th International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GNSS+ 2013), Nashville, TN, USA, 16–20 September 2013. [Google Scholar]
- Li, M.; Xu, T.; Guan, M.; Gao, F.; Jiang, N. LEO-constellation-augmented multi-GNSS real-time PPP for rapid re-convergence in harsh environments. GPS Solut. 2022, 26, 29. [Google Scholar] [CrossRef]
- Joerger, M.; Gratton, L.; Pervan, B.; Cohen, C.E. Analysis of Iridium Augmented GPS for floating carrier phase positioning. J. Inst. Navig. 2010, 57, 137–160. [Google Scholar]
- Lawrence, D.; Cobb, H.S.; Gutt, G.; Tremblay, F.; Laplante, P.; O’Connor, M. Test Results from a LEO-Satellite-Based Assured Time and Location Solution. In Proceedings of the 2016 International Technical Meeting of the Institute of Navigation, Monterey, CA, USA, 25–28 January 2016. [Google Scholar]
- De Selding, P.B. Virgin, Qualcomm Invest in OneWeb Satellite Internet Venture. Space News. 15 January 2015. Available online: https://spacenews.com/virgin-qualcomm-invest-in-global-satellite-internet-plan/ (accessed on 1 February 2022).
- De Selding, P.B. SpaceX to Build 4000 Broadband Satellites in Seattle. Space News. 19 January 2015. Available online: https://spacenews.com/spacex-opening-seattle-plant-to-build-4000-broadband-satellites/ (accessed on 1 February 2022).
- De Selding, P.B. Boeing Proposes Big Satellite Constellations in V- and Cbands. Space News. 23 June 2016. Available online: http://spacenews.com/boeingproposes-big-satellite-constellations-in-v-and-c-bands/ (accessed on 1 February 2022).
- Meng, Y.; Bian, L.; Han, L.; Lei, W.; Yan, T.; He, M.; Li, X. A global navigation augmentation system based on LEO communication constellation. J. Terahertz Sci. Electron. Inf. Technol. 2019, 17, 65–71. [Google Scholar]
- Reid, T.G.R.; Neish, A.M.; Walter, T.F.; Enge, P.K. Leveraging Commercial Broadband LEO Constellations for Navigation. In Proceedings of the 29th International Technical Meeting of the Satellite Division of the Institute of Navigation (ION GNSS+ 2016), Portland, OR, USA, 12–16 September 2016. [Google Scholar]
- Dietrich, F.J.; Metzen, P.; Monte, P. The globalstar cellular satellite system. IEEE Trans. Antennas Propag. 2002, 46, 935–942. [Google Scholar] [CrossRef]
- Gebhardt, C. Iridium Boss Reflects as Final NEXT Satellite Constellation Launches. kc4mcq. 11 January 2019. Available online: https://www.kc4mcq.us/?p=15784/ (accessed on 1 February 2022).
- De Selding, P.B. LeoSat Corporate Broadband Constellation Sees GEO Satellite Operators as Partners. Space News. 14 June 2016. Available online: https://spacenews.com/leosat-corporate-broadband-constellation-sees-geo-satellite-operators-as-partners/ (accessed on 1 February 2022).
- CNAGA. CASIC Plans to Launch 156 Small Satellites for the Hongyun Program. Beidouchina. 18 May 2017. Available online: http://en.beidouchina.org.cn/c/393.html/ (accessed on 1 February 2022).
- De Selding, P.B. Telesat: LEO Gives More User Bandwidth than GEO HTS. Space Intel Report. 8 May 2017. Available online: https://www.spaceintelreport.com/telesat-leo-gives-more-user-bandwidth-than-geo-hts/ (accessed on 1 February 2022).
- Forrester, C. Astrome Planning Giant Broadband Constellation. Advanced Television. 26 October 2016. Available online: https://advanced-television.com/2016/10/26/astrome-planning-giant-broadband-constellation/ (accessed on 1 February 2022).
- Magan, V. Samsung Exec Envisions LEO Constellation for Satellite Internet Connectivity. Via Satellite. 18 August 2015. Available online: https://www.satellitetoday.com/telecom/2015/08/18/samsung-exec-envisions-leo-constellation-for-satellite-internet-connectivity/ (accessed on 1 February 2022).
- Harshal, A.R.; Nemade, B.; Bhattacharjee, R. Performance of Multiuser Communication System using Phase Coded Linear Chirp Modulation. In Proceedings of the Twenty-third National Conference on Communications (NCC), Chennai, India, 2–4 March 2017. [Google Scholar]
- Li, T.; Yan, T.; Bian, L.; Qu, B.; Wang, Y.; Meng, Y. Design and Validation of CPQC-NAV, A New LEO Navigation Augmentation Signal Compatible with GNSS. In Proceedings of the China Satellite Navigation Conference (CSNC 2022), Beijing, China, 22–25 May 2022. [Google Scholar]
- Xue, R.; Sun, Y.; Zhao, D. CPM Signals for Satellite Navigation in the S and C Bands. Sensors 2015, 15, 13184–13200. [Google Scholar] [CrossRef] [PubMed] [Green Version]
- Aho, A.V.; Hopcroft, J.E.; Ullman, J.D. The Design and Analysis of Computer Algorithms, 1st ed.; Addison-Wesley Publishing Company: Reading, MA, USA, 1974; pp. 364–404. [Google Scholar]
- Savage, C. Depth-first search and the vertex cover problem. Inf. Processing Lett. 1982, 14, 233–235. [Google Scholar] [CrossRef]
- Assi, M.; Halawi, B.; Haraty, R.A. Genetic Algorithm Analysis using the Graph Coloring Method for Solving the University Timetable Problem. Procedia Comput. Sci. 2018, 126, 899–906. [Google Scholar] [CrossRef]
- Culberson, J.C. Iterated Greedy Graph Coloring and the Difficulty Landscape; Technical Report 92-07; Department of Computing Science, The University of Alberta: Edmonton, AB, Canada, 1992. [Google Scholar]
- Salari, E.; Eshghi, K. An ACO Algorithm for the Graph Coloring Problem. Int. J. Contemp. Math. Sci. 2008, 3, 293–304. [Google Scholar]
- Chams, M.; Hertz, A.; Werra, D.D. Some experiments with simulated annealing for coloring graphs. Eur. J. Oper. Res. 1987, 32, 260–266. [Google Scholar] [CrossRef]
- Palubeckis, G. On the recursive largest first algorithm for graph colouring. Int. J. Comput. Math. 2008, 85, 191–200. [Google Scholar] [CrossRef]
- Li, X.; Zhang, K.; Ma, F.; Zhang, W.; Zhang, Q.; Qin, Y.; Zhang, H.; Meng, Y.; Bian, L. Integrated Precise Orbit Determination of Multi-GNSS and Large LEO Constellations. Remote Sens. 2019, 11, 2514. [Google Scholar] [CrossRef] [Green Version]
- Leighton, F. A graph coloring algorithm for large scheduling problems. J. Res. Natl. Bur. Stand. 1979, 84, 489–503. [Google Scholar] [CrossRef] [PubMed]
- Chiarandini, M.; Galbiati, G.; Gualandi, S. Efficiency Issues in the RLF Heuristic for Graph Coloring. In Proceedings of the 9th Metaheuristics International Conference, Udine, Italy, 25–28 July 2011. [Google Scholar]
- Walker, J.G. Satellite constellations. J. Br. Interplanet. Soc. 1984, 37, 559. [Google Scholar]
Constellation | Country | No. Satellites | Altitude (km) | Inclination (deg) | Year |
---|---|---|---|---|---|
Iridium [10] | USA | 66 | 781 | 86.4 | 1998 |
Globalstar [21] | USA | 48 | 1400 | 52 | 2000 |
Iridium NEXT [22] | USA | 75 | 780 | 86.4 | 2019 |
LeoSat [23] | USA | 108 | 1400 | - | 2019/2020 |
SpaceX Starlink [17] | USA | 1600 | 1110 | 53.8 | 2024 |
400 | 1130 | 74 | |||
1600 | 1150 | 53 | |||
375 | 1275 | 81 | |||
450 | 1325 | 70 | |||
7518 | 340 | - | - | ||
Boeing [18] | USA | 1190 | 1200 | 45 | 2027 |
612 | 55 | ||||
1155 | 88 | ||||
OneWeb [16] | USA/UK | 648 | 1200 | 88 | 2027 |
Hongyun [24] | China | 156 | 1000 | 2022 | |
Hongyan [19] | China | 54 | 1100 | - | 2023 |
324 | - | - | - | ||
Telesat [25] | Canada | 72 | 1000 | 99.5 | 2021 |
45 | 1248 | 37.4 | |||
Astrome Technology [26] | India | 150 | 1400 | - | - |
Samsung [27] | Korea | 4600 | 1400 | - | - |
Constellation Name | Type of Orbit | Number | Altitude (km) | Inclination (deg) | Planes Number | Approximate Minimum | Ratio |
---|---|---|---|---|---|---|---|
LEO-48 | Walker | 48 | 1414 | 52 | 8 | 8 | 6 |
LEO-66 | Polar | 66 | 778 | 86.4 | 6 | 10 | 6.6 |
LEO-120 | Walker | 120 | 1000 | 55 | 12 | 16 | 7.5 |
LEO-192 | Polar | 192 | 1200 | 90 | 12 | 34 | 5.65 |
LEO-288 | Polar | 288 | 1000 | 98.2 | 12 | 50 | 5.76 |
LEO-576 | Walker | 576 | 900 | 60 | 24 | 101 | 5.70 |
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. |
© 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).
Share and Cite
Wang, W.; Tian, Y.; Bian, L.; Wang, G.; Meng, Y.; Zhang, L. A Novel Satellite PRN Code Assignment Method Based on Improved RLF Algorithm. Sensors 2022, 22, 5538. https://doi.org/10.3390/s22155538
Wang W, Tian Y, Bian L, Wang G, Meng Y, Zhang L. A Novel Satellite PRN Code Assignment Method Based on Improved RLF Algorithm. Sensors. 2022; 22(15):5538. https://doi.org/10.3390/s22155538
Chicago/Turabian StyleWang, Weiwei, Ye Tian, Lang Bian, Guoyong Wang, Yansong Meng, and Lixin Zhang. 2022. "A Novel Satellite PRN Code Assignment Method Based on Improved RLF Algorithm" Sensors 22, no. 15: 5538. https://doi.org/10.3390/s22155538