# A Novel Satellite PRN Code Assignment Method Based on Improved RLF Algorithm
## 3 Algorithm
### Algorithm Improvement
In this study, we improved the RLF algorithm and evaluated the performance of the algorithm before and after the improvement. Satellites of a polar-orbiting or walker configuration, which are commonly used in the LEO constellation, are usually equally distributed at the same orbital altitude. Therefore, in Step 4 of the RLF algorithm, when computing the degree of all satellites in \(W\), we found that, in some cases, many satellites' degrees are equal to the maximum degree, and there are many satellites in the set \(W_{0}\). In step 5, a satellite in set \(W_{0}\), which may consist of many satellites, is randomly selected. The satellite selected has a great influence on the calculation result. To improve the performance of the algorithm, we optimized the way in which the random selection in step 5 is conducted. We combined all satellites in pairs to get \(N_{sat}\cdot(N_{sat}-1)/2\) satellite pairs. We composed a set of satellites that conflict with satellite \(v_{i}\) and a set of satellites that conflict with satellite \(v_{j}\) and calculated the union of two sets to obtain the conflict set of satellite pairs \((i,j)\) consisting of satellites \(v_{i}\) and \(v_{j}\). When the number of elements in this union is minimal, we believe that this satellite pair can share the same PRN code. These satellite pairs were recorded, and a set \(P\) of satellite pairs was formed. In step 5, we preferentially selected the satellite pairs in set \(P\). We replaced step 5 with the following:  
* Step 5: Choose a satellite \(v_{k}\in W_{0}\) at random and assign PRN code \(q\) to satellite \(v_{k}\). In other words, move \(v_{k}\) to \(C_{q}\) and remove \(v_{k}\) from \(U\). Return to Step 3. \[ \begin{array}{c}If\;exist\;(i,j)\in P\;\&\&\;v_{i},v_{j}\in W_{0}\;\;\;then \;\;v_{i},v_{j}\in C_{q}\;\;\;\;\;v_{i},v_{j}\
otin U\\ Otherwise\;\;randomly\;choose\;v_{k}\in W_{0}\;\;\;then\;\;\;v_{k}\in C_{q}\;\;v_{k} \
otin U\end{array} \] (13)In order to evaluate the performance of the algorithm before and after the improvement, we used LEO-120 as the study object, and the approximate minimum PRN code of the LEO-120 is 16. Due to the randomness of the RLF algorithm, we needed to iterate many times to get the approximate optimal solution. We repeated the experiment 10,000 times and recorded the number of iterations required for the RLF and the improved-RLF to obtain the approximate optimal solution in each experiment. Obviously, the more iterations there is, the greater the computational time of the algorithm is. A histogram of the number of iterations is shown in Figure 6, and the average number of iterations for the RLF is 1138.411, while the average number of iterations for the improved-RLF is 668.752. As can be seen from the figure, in most of the experiments, the RLF algorithm reached the optimal solution within 5000 iterations, while the improved-RLF algorithm reached the optimal solution within 3000 iterations. Overall, through the experiments, we obtained the conclusion that the calculation time for the improved RLF algorithm is faster than that of the RLF algorithm for the problem of calculating the minimum number of PRN codes. Due to the randomness of the RLF algorithm, the convergent solution of RLF algorithm may be not an approximate optimal solution. In order to evaluate the uncertainty, we analyzed the uncertainty based on the above experimental data, as shown in Figure 7. The probability of a non-approximate optimal solution of the RLF algorithm is greater than that of an improved-RLF algorithm. In order to obtain the approximate optimal solution, the number of iterations should be increased as much as possible during the calculation process. Figure 6: 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.