# A Novel Satellite PRN Code Assignment Method Based on Improved RLF Algorithm
## 3 Algorithm
### Algorithm Comparison  
The above analysis shows that the problem of optimum satellite PRN code assignment is similar to the minimum graph coloring problem, so we studied the algorithms that solve the graph coloring problem and tried to apply these algorithms to calculate the minimum number of PRN codes. The minimum graph coloring problem has been shown to be an NP complete problem, and there is currently no algorithm to find the optimal solution in a time bounded by a polynomial in the graph. Fortunately, there are many algorithms that can solve the problem sub-optimally to obtain the approximate optimum solution, e.g., the depth-first search (DFS) [32], genetic algorithm (GA) [33], greedy algorithm [34], ant colony optimization (ACO) [35], simulated annealing (SA) [36], RLF [37], and so on. In order to find the most suitable algorithm for the optimum satellite PRN code assignment problem, we selected 6 algorithms and used these to calculate the minimum number of PRN codes. These 6 algorithms are described briefly. DFS obtains the minimum number of PRN codes by traversing all possibilities, and the minimum value can be obtained in theory. However, the time complexity of DFS is exponential, which means it is difficult to reach the optimal solution within a limited time. Both GA and SA generate a random PRN code assignment scheme. If the assignment scheme error occurs, it will be included in the cost: the more errors that occur, the greater the cost is. The assignment scheme is changed according to a certain probability of mutation/disturbance, meaning that the cost might be decrease. However, the convergent solution may not be the approximate optimal solution, so multiple calculations are required. The greedy algorithm can be described as follows: satellites are arranged in a random order, as many satellites as possible are selected to share the same PRN code in order, and if the remaining satellites cannot share this PRN code, the next PRN code is assigned. The greedy algorithm can be calculated within a short time, but the calculation result depends on the order of the satellites, and the approximate optimal solution can be obtained through repeated calculations by constantly disrupting the order of the satellites. ACO and RLF can be regarded as improved greedy algorithms. In ACO, a group of ants is released, and results are obtained by pheromone and greedy methods. Then, the pheromone is added to the correct path, and the ants are released again and again, until an approximate optimal solution is obtained. On the basis of greed, the RLF algorithm preferentially selects large-degree satellites so that more satellites may be assigned to the same PRN code. To evaluate the performance levels of these 6 common algorithms in relation to this problem, we designed 6 LEO constellations with different satellite numbers, orbital altitudes, and types of orbits using simulation software and then obtained the minimum number of PRN codes using these 6 algorithms. Figure 4 shows the designed LEO constellations and two typical orbits, including the polar-orbiting orbit and the walker orbit. In particular, the LEO-48 constellation is borrowed from the Globalstar constellation [21], and the LEO-66 constellation scheme is related to the Iridium constellation [38]. Table 2 shows the detailed orbital configurations and approximate minimum solutions of the designed LEO constellations. The ratios in the table represent the satellite number compared with the minimum number of PRN codes. The results of this ratio further demonstrate its benefits for the navigation signal receiver, and this method can greatly reduce the storage resources needed and the average satellite acquisition time of the receiver. Figure 4: Designed LEO constellations: (**a**) 48 LEO, 141 km, walker; (**b**) 66 LEO, 778 km, polar; (**c**) 120 LEO, 1000 km, walker; (**d**) 192 LEO, 1200 km, polar; (**e**) 288 LEO, 1000 km, polar; (**f**) 576 LEO, 900 km, walker. Figure 5 shows a comparison of the optimal approximate solutions for the 6 algorithms.