# A Novel Satellite PRN Code Assignment Method Based on Improved RLF Algorithm
## 3 Algorithm
### Algorithm Improvement  
In the previous subsection, we showed that compared with the other five algorithms, the RLF algorithm is the most suitable for calculating the minimum number of PRN codes. The RLF algorithm was originally proposed by [PERSON] in 1979, in part for use in constructing solutions to large timetabling problems [39]. Paper [40] proposed a variant of RLF, which is called LAZY RLF, that exploits possible savings in the computations during algorithm execution. In spite of its best results in terms of quality, the RLF heuristic has been seldom used in the literature [40]. Because the satellites are usually uniformly distributed in the sky and the constellation is symmetrical, the conflicts of satellites have certain characteristics. We used these charac \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Constellation** & **Type of** & **Altitude** & **Inclination** & **Planes** & **Approximate** & \\
**Name** & **Orbit** & **Number** & **(km)** & **(deg)** & **Number** & **Minimum** & **Ratio** \\ \hline 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 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Detailed orbital configurations and approximate minimum solution of the designed LEO constellations. Figure 5: Comparison of the optimal approximate solutions for the 6 algorithms. The parameters and methods used in the algorithm are as follows: **DFS**, We assigned PRN codes to satellites with few optional PRN codes as soon as possible; **GA**, The number of populations was 300, the Max Generation was 2000, and the program needed to be run multiple times; **Greedy**, The number of iterations was 100,000; **ACO**, 50 ants walked 2000 times, the decay factor was 0.99, and the program needed to be run multiple times; **SA**, The initial temperature was \(10^{6}\), the temperature decay factor was 0.9, and the program needed to be run multiple times; **RLF**: The number of iterations was 20,000.  
teristics to improve the RLF algorithm. Before presenting the improvement, we introduce the RLF algorithm process, and the specific steps used in the RLF algorithm are as follows:  
* Step 1: Initialization. Set \(q\) to 0, and set \(U=V\). \(q\) indicates the current PRN code and \(U\) represents the set of unnumbered satellites. Proceed to 2. \[q:=0;\;\;U:=V\] (8)
* Step 2: Using the new PRN code, increase \(q\) by 1 and set \(C_{q}\) to empty. Then, proceed to 3. \[q:=q+1;\;\;\;C_{q}:=\phi\] (9)
* Step 3: Find the satellite set \(W\), and number each satellite in set \(W\) as \(q\). There are two conditions. The first is that all satellites \(v_{i}\;\in W\) must be unnumbered, and the second is that all satellites \(v_{i}\;\in W\) must not conflict with satellites in \(C_{q}\). Proceed to 4. \[ \begin{array}{c}W=\{v_{i}\},\;\;\;v_{i}\in U\\ R(i,j)=0,\;\;\;v_{i}\;\in W,\;\;\;v_{j}\in C_{q}\end{array} \] (10)
* Step 4: Compute the degree of all satellites in \(W\) 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 \(W_{0}\). Proceed to 5. \[ \begin{array}{c}W_{0}=\{v_{j}\},\;v_{j}\in\;W\\ deg(v_{j})=\text{max}deg(v_{i}),\;\;v_{i}\;\in W,\;\;\;v_{j}\in W_{0}\end{array} \] (11)
* Step 5: Choose a satellite \(v_{k}\in W_{0}\) at random and assign a 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. \[v_{k}\in C_{q}\;\;v_{k}\
otin U\] (12)
* Step 6: Check whether \(U=\phi\). If so, all satellites are numbered, and the program should be stopped. If not, no other satellite fits this PRN code \(q\), so return to Step 2.