# A Novel Satellite PRN Code Assignment Method Based on Improved RLF Algorithm
## 2 Methods and Mathematical Models
### Calculation Process  
The calculation of the minimum number of PRN codes can be divided into four steps. The details are as follows:  
Firstly, we set the users' positions and simulated the satellite orbits. A total of 65,160 ground stations were established at intervals of 1 degree latitude and 1 degree longitude on the ground. These were regarded as user positions, and the user elevation threshold \(e_{\text{threshold}}\) was set as 7 degrees. By simulating the satellite orbit for a long time, the elevation \(e\) from the user to the satellite at each moment was obtained through the position of the satellite and user according to the following formula.  
\[e=\arctan\left(\frac{\cos(\phi_{1}-\phi_{2})\times\cos\theta_{1}-0.15127}{ \sqrt{1-\left[\cos(\phi_{1}-\phi_{2})\times\cos\theta_{1}\right]^{2}}}\right) =\left\{\begin{array}{l}>e_{\text{threshold}},\ \ \ \ \ \text{can be received}\\ <e_{\text{threshold}},\ \ \ \text{can not be received}\end{array}\right. \tag{6}\]  
where \(\phi_{1}\) and \(\theta_{1}\) are the longitude and latitude of the user; \(\phi_{2}\) is the longitude of the satellite. If the elevation angle from the user to the satellite was higher than the user elevation threshold, we deemed that the satellite navigation signals could be received by users.  
Secondly, we obtained the satellite conflict relationships based on the positions of users and satellites. The PRN code transmitted by the satellite has the CDMA function. Therefore, when sharing PRN codes, it is essential to ensure that the satellites broadcasting the same  
Figure 3: 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.  
PRN code cannot appear in the user's view at any position on the Earth. We defined the conflict relationship of a satellite as follows: a signal of satellites can be received by the same user at a certain time, and the satellites with a conflict relationship cannot share the same PRN code. If a constellation consists of \(N_{sat}\) satellites, a matrix \(R\) of size \(N_{sat}\times N_{sat}\) is established to record the conflict relationship between satellites, and the matrix \(R\) is defined as follows:  
\[R(i,j)=\left\{\begin{array}{ll}1,&\text{signal of Satellite $i$ and $j$ can be received by the same user at $a$ certain time}\\ 0,&\text{signal of Satellite $i$ and $j$ cannot be observed by the same user at any time or $(i=j)$}\end{array}\right. \tag{7}\]  
We simulated the satellite orbit for as much time as possible. If the matrix \(R\) did not change within a certain time (several period of satellite), we considered that all satellite conflicting relationships had been collected.  
Thirdly, we built the computational model, which is similar to the optimum graph coloring problem. The graph coloring problem has been proven to be a NP complete problem. There is currently no algorithm to find the optimal coloring in a time bounded by a polynomial in the graph [31]. Fortunately, there are many algorithms to solve the problem sub-optimally and obtain the approximate optimum solution, from which the most suitable algorithm for the optimum satellite PRN code assignment problem could be found. According to the characteristic that the LEO satellites are usually uniformly distributed, we improved the algorithm to make it more suitable for our question.  
Finally, we obtained an approximate optimal solution with a suitable algorithm and verified its feasibility. Meanwhile, a satellite PRN code assignment scheme, corresponding to the approximate optimal solution could be obtained, and we brought the scheme back to the satellite constellation in order to verify whether this satellite PRN code assignment scheme was feasible.