# Interference Avoidance through Periodic UAV Scheduling in RIS-Aided UAV Cluster Communications
## 3 UAV Scheduling to Avoid Interference  
### UAV Scheduling Graph  
The optimization problem (12) is an integer programming problem. Traditional methods, such as continuous relaxation, are not suitable for this problem due to the constraint (9) which requires strict integer variables. However, we can approach it as a multi-stage decision problem, where each stage involves assigning a beam with its initial time slot. There are a total of \(MN_{c}\) UAVs in the system, and their initial time slots are allocated successively by polling each cluster. The collection of all initial time slots for the UAVs forms the UAV scheduling vector, which is defined as  
\[\begin{split}\mathbf{\tilde{s}}_{MN_{c}}&=(\tilde{s}_{ 1},\ldots,\tilde{s}_{MN_{c}})\\ &=\left(\mathbf{s}_{1}^{1},\ldots,\mathbf{s}_{1}^{N_{c}},\mathbf{s}_{2}^{1}, \ldots,\mathbf{s}_{M-1}^{N_{c}-1},\mathbf{s}_{M}^{1},\ldots,\mathbf{s}_{M}^{N_{c}}\right),\end{split} \tag{13}\]  
where the initial time slot of UAV \(k\) is denoted as \(\tilde{s}_{k}\). The relationship between \(\tilde{s}_{k}\) and \(\mathbf{s}_{j}^{i}\) is determined by the mapping rule \(\tilde{s}_{k}=\mathbf{s}_{\lceil k/M\rceil}^{mod(k,M)}\). The allocation of initial time slots for \(MN_{c}\) UAVs can be described by a UAV scheduling graph, where the nodes correspond to different selections of the initial slots of each UAV.  
An example of the UAV scheduling graph is presented in Figure 2. The graph consists of \(MN_{c}+1\) layers, where each layer represents a stage in the allocation of initial slots to the beams. The state \(\tilde{s}_{k}\) denotes the UAV scheduling vector in stage \(k\). In the initial stage, denoted as stage 0, no time slot is allocated and, thus, \(\tilde{s}_{0}\) is empty. In stage \(k>0\), the decision of \(\tilde{s}_{k}\) updates the UAV scheduling vector as \(\tilde{s}_{k}=(\tilde{s}_{k-1},\tilde{s}_{k})\). Each node in the graph corresponds to a possible value of the UAV scheduling vector \(\tilde{s}_{k}\) in stage \(k\). It is important to note that the available time slots for a current UAV are determined by the previous selections of other UAVs, resulting in a connection between each node in stage \(k\) and a node in stage \(k-1\). Finally, in the last layer, the nodes are referred to as destinations, and each destination node represents an allocation result of the initial time slots for all \(MN_{c}\) UAVs, denoted as \(\tilde{\mathbf{s}}_{MN_{c}}\).  
For convenience, we denote the scheduling cycles of UAVs as \(\hat{T}_{k}=T_{\lceil k/M\rceil}^{mod(k,M)}\). In stage \(k\), the UAV \(k\) has a scheduling period of \(\hat{T}_{k}\). Therefore, the selection of time initial slot falls within the range of \(\big{(}1,\ldots,\hat{T}_{k}\big{)}\). However, the selection of initial time slots is also constrained by the number of RIS arrays, as shown in Equation (10). In the graph, there are some nodes that are not achievable, indicated by dash arrows. In the example illustrated in Figure 2, we have \(N_{c}=2\), \(M=2\), \(T_{1}^{1}=T_{2}^{1}=T_{2}^{2}=2\), and \(T_{1}^{2}=4\). Both clusters have only one RIS array. The process of reaching the destination node \(\tilde{\mathbf{s}}_{4}=(1,1,2,2)\) is as follows: At stage 1, the initial time slot of UAV \((1,1)\) is set to 1, i.e., \(\tilde{s}_{1}=1\). Then, \(\tilde{s}_{1},\tilde{s}_{2}\), and \(\tilde{s}_{3}\) are set to be 1, 2, and 2 respectively. In stage 3, it is observed that if \(\tilde{s}_{1}=1\), then \(\tilde{s}_{3}\) cannot be 1 or 3 due to the limited number of UAVs that can be scheduled, which is constrained by the number of available RIS arrays.