## 2 System Model of NGSO Satellites Equipped with Multi-Beam Antennas
### Channel Allocation Method
Rotating the configuration will result in significant distance variations between different beams that work in the same channel. Thus, the rotation angle is regarded as an optimization variable. The illustration of rotation angle for seven beams condition is shown in Figure 8b. The equilateral hexagon has the characteristic of central symmetry, so the rotation angle is limited to \(\pi/3\). In order to mitigate the co-channel interference between different communication systems, the maximum total amount of beam distances is regarded as the optimization objective, and the optimization problem can be formulated as  
\[\max\sum_{i=1}^{N_{\mathrm{s}}}(l_{a}+l_{r}) \tag{30}\] \[s.t.\left\{ \begin{array}{l}\sum_{i=1}^{N_{\mathrm{s}}}a_{ij} \geq 0\\ \sum_{i=1}^{N_{\mathrm{s}}}a_{ij}\leq M_{\mathrm{P}}\\ a_{ij}+a_{kj}=1\\ l\geq l_{\mathrm{th}}\\ 0\leq\theta_{\mathrm{rot}}\leq\pi/3\end{array} \right.\]  
Figure 8: Layout of NGSO satellite beams and illustration of rotation angle. (**a**) Layout of NGSO satellite beams with 37 beams; (**b**) Illustration of rotation angle for seven-beam scenario. where \(N_{8}\) stands for the number of interfering satellite beams, and \(M_{\text{P}}\) is the number of available beam colors of the interfered satellite. The values of \(i\) and \(k\) should satisfy the condition that two beams represented by integers are adjacent in the topology of the equilateral hexagon of coverage. This optimization problem is typically a mixed integer nonlinear programming problem [36], which could be solved by methods such as enumeration method [37], greedy algorithm [38; 39], genetic algorithm [40; 41], beam search algorithm [42], and the Monte Carlo method [38; 43], among other techniques. And this problem is an NP-hard problem. The enumeration method is preferred when the problem is small-scale. However, when the scale of the problem becomes large enough, the time consumption of the enumeration method is unbearable. Thus, many optimization algorithms are developed to not only achieve optimal solutions, but also greatly reduce the computational time. In this article, a beam search algorithm is mainly selected to solve the presented optimization problem. Beam search is a heuristic algorithm, an adaptation of the branch and bound method [44], and only a certain number of nodes are expanded and evaluated in the search tree. At each level, only the nodes with higher evaluation values are kept for further expansion, and the remaining nodes are pruned off permanently. The beam search-based channel allocation procedure is specified in Algorithm 1. ```
Input: Ephemeris of satellites Output: Allocation matrix \(A\) initialization; whilenot at end of simulation instantdo whilenot at the maximum of rotation angledo  Determine available colors for each beam ; foreachavailable color for TreeLength = 1 do  Set root nodes ;  end  CurrentLevel = NextLevel ;  TreeLength = TreeLength + 1 ; whileTreeLength < Number of beamsdo foreachTreeLength other than TreeLength = 1 do  UnallocatedColor = available colors in current level ; foreach\(color\in UnallocatedColor\)do ifother constraints are satisfiedthen  Calculate the beam distance based on locations ;  Add this distance to Branches ;  end foreach  Sort Branches, add certain number of colors to NextLevel ;  end fore Sort NextLevel, keep branches with certain colors and prune the rest off ;  CurrentLevel = NextLevel ;  TreeLength = TreeLength + 1 ;  end foreach Obtain certain number of best optimization results ;  end foreach  end foreach
```  
**Algorithm 1**Beam search-based channel allocation method