# Interference Avoidance through Periodic UAV Scheduling in RIS-Aided UAV Cluster Communications
## 3 UAV Scheduling to Avoid Interference
### Local Interference Minimization Scheme  
In the UAV scheduling graph, each destination node \(\tilde{\mathbf{s}}_{MN_{c}}\) is associated with a specific total interference level. The main objective of the UAV scheduling problem is to identify the destination node that exhibits the lowest interference level. To achieve this, an exhaustive search scheme can be employed to consider every possible destination node. However, even with the constraints imposed by the RIS number, the total number of destination nodes remains substantial, on the order of \(\prod_{k=1,\ldots,MN_{c}}T_{k}\). Consequently, the exhaustive search or directing dynamical programming approach becomes excessively complex. To address this complexity, we propose a greedy scheme known as local interference minimization. This scheme selects the UAV scheduling time slot based on minimizing the current interference level at each decision stage. Consider a node in stage \(k-1\), where \(k=1,\ldots,MN_{c}\), and \(k-1\) UAVs are already allocated with their initial time slots in the vector \(\tilde{\mathbf{s}}_{k-1}\). The interference level in stage \(k-1\) is denoted as \(\gamma_{k-1}(\tilde{\mathbf{s}}_{k-1})\). Each node in stage \(k\) is assigned a cost, represented as \(\gamma_{k}(\tilde{\mathbf{s}}_{k})\). Figure 2: The multi-stage decision of initial time slot allocation with two UAV clusters and two UAVs per cluster. \(N_{c}=2\), \(M=2\), \(T_{1}^{1}=T_{2}^{1}=T_{2}^{2}=2\), \(T_{1}^{2}=4\) and \(L=1\). The LIM scheme selects \(\tilde{s}_{k}\) to minimize \(\gamma_{k}(\tilde{\mathbf{s}}_{k})\). The interference level of the LIM scheme in stage \(k\) can be derived using the formula for interference level in Equation (11). \[ \begin{split}&\gamma_{k,LIM}=\underset{\tilde{\mathbf{s}}_{k}}{min} \gamma_{k}(\tilde{\mathbf{s}}_{k})\\ &=\gamma_{k-1,LIM}+\underset{\tilde{s}_{k}\in\mathcal{N}_{k-1}}{ \min}\tilde{\gamma}_{k}(\tilde{s}_{k})\\ &=\gamma_{k-1,LIM}+\underset{\tilde{s}_{k}\in\mathcal{N}_{k-1}}{ \min}\sum_{k^{\prime}=1}^{k}(I(\tilde{s}_{k},\tilde{s}_{k^{\prime}})+I(\tilde{ s}_{k^{\prime}},\tilde{s}_{k}))\\ &=\gamma_{k-1,LIM}+\underset{\tilde{s}_{k}\in\mathcal{N}_{k-1}}{ \min}\sum_{i^{\prime}=1}^{N^{\prime}}\sum_{j^{\prime}=1}^{M^{\prime}}\left(I \left(s_{j^{\prime}}^{i},s_{j^{\prime}}^{j^{\prime}}\right)+I\left(s_{j^{ \prime}}^{i^{\prime}},s_{j}^{i}\right)\right),\end{split}  \tag{14}\]  
where \(N^{\prime}_{c}=mod(k-1,M)\), \(M^{\prime}=\left\lceil k-1/M\right\rceil\) and \(i=mod(k,M)\), \(j=\left\lceil k/M\right\rceil\) as shown in Equation (13). The set \(\mathcal{N}_{k-1}\) contains all feasible initial slots for UAV \(k\) that satisfy the RIS constraints. \(\tilde{\gamma}_{k}(s_{k})\) represents the local interference, which includes the interference between UAV \(k\) and the previously scheduled UAVs. The interference level caused by the scheduling collision of two UAVs, denoted as \(I\left(s_{i^{\prime}}^{i},s_{i^{\prime}}^{j^{\prime}}\right)\), can be calculated using a simple formula. Let the initial time slots of two UAVs be \(s_{j}^{i}\) and \(s_{j^{\prime}}^{j^{\prime}}\), and their periods be \(T_{j}^{i}\) and \(T_{j^{\prime}}^{j^{\prime}}\). According to the condition for the existence of integer solutions of Diophantine equations [32], the two UAVs will collide if there exists an integer \(q\) such that \(s_{j}^{i}-s_{j^{\prime}}^{i^{\prime}}=qe\left(T_{j}^{i},T_{j^{\prime}}^{j^{ \prime}}\right)\), where \(e(a,b)\) represents the greatest common divisor (GCD) of integer numbers \(a\) and \(b\). Given the scheduling periods and allocation result, the collision ratio can be determined when two UAVs collide with each other. The collision ratio is given by the following conclusion: If two UAVs with transmit periods \(T_{1}\) and \(T_{2}\) cause collisions, the ratio of collision time slots is \(\epsilon(T_{1}T_{2})\) as \(N\) approaches infinity.