# Interference Avoidance through Periodic UAV Scheduling in RIS-Aided UAV Cluster Communications
## 3 UAV Scheduling to Avoid Interference
### LIM-Based Rollout Scheme  
The rollout algorithm is a general approach for enhancing the solutions of multi-stage decision problems. The main concept involves taking a one-step lookahead to evaluate neighboring nodes using a basic heuristic strategy. It has been demonstrated in [33] that if the base strategy exhibits the property of sequential consistency, a rollout algorithm based on this strategy can yield benefits. A strategy satisfies the sequential consistent condition if it leads to the same decision sequence regardless of the stage it starts. A strategy fulfills the condition of sequential consistency if it consistently leads to the same decision sequence, regardless of the starting stage. In the context of UAV slot allocation, a sequential consistent strategy adheres to the following principle: for \(k=1,\ldots,MN_{c}\), if the strategy selects the initial time slots sequence \((s_{k},s_{k+1},\ldots,s_{MN_{c}})\) when commencing at stage \(k-1\), it will select the time slot sequence \((s_{k+1},\ldots,s_{MN_{c}})\) when starting at stage \(k\). In the LIM algorithm, the choice of \(s_{k}\) depends on the local interference \(\hat{\gamma}_{k}(s)\), and the selected time slot sequence remains unchanged regardless of the starting stage. Thus, the LIM algorithm satisfies the condition of sequential consistency and can serve as the fundamental strategy for constructing a rollout algorithm. Algorithm 2 presents the procedure for the rollout algorithm based on the LIM. In stage \(k\), the RIM algorithm applies the LIM based on all feasible \(\tilde{s}_{k}\) to reach a destination, and subsequently selects the \(\tilde{s}_{k}\) with the minimum interference level. Steps 4-8 identify all candidate time slots that satisfy the RIS constraint for each cluster, followed by the application of the LIM algorithm for different selections of time slot \(s_{k}\in\mathcal{N}_{k-1}\). Finally, steps 9 and 10 determine the optimal time slot and update the UAV scheduling vector. ```
1 Let \(k=0\). Initial the UAV scheduling vector \(\hat{\mathbf{s}}=\Phi\), and initial the RIS occupation vector \(\mathbf{s}_{o}=\mathbf{0}_{N}\) ;
2 forstage\(k=1,\dots,MN_{c}\)do
3\(n=mod(k,M)\)\(m=\lceil k/M\rceil\) ;
4 Find \(\mathcal{N}(k-1)\) using steps 4-9 of the LIM algorithm;
5 forall\(s\in\mathcal{N}(k-1)\)do
6 Based on \(\hat{\mathbf{s}}=(\hat{\mathbf{s}},s)\) and \(\mathbf{s}_{o}=\hat{\mathbf{s}}_{o}+\mathbf{s}_{m}^{n}\), apply steps 3-11 of the LIM algorithm for stage \(k+1,\dots,MN_{c}\) and update \(\hat{\mathbf{s}}\) ;
7 Obtain \(s_{j}^{i}\) in \(\hat{\mathbf{s}}\) according to the mapping rule in (13). Calculate the interference level \(\bar{\gamma}_{k}(s)=\sum\limits_{i=1}^{N_{c}}\sum\limits_{j=1}^{M}\sum\limits_ {i^{\prime}=1}^{N_{c}}\sum\limits_{j^{\prime}=1}^{M}\left(I\left(s_{i^{\prime}} ^{j}s_{i^{\prime}}^{j^{\prime}}\right)+I\left(s_{i^{\prime}}^{j}s_{i^{\prime} }^{j}\right)\right)\) ;
8
9 end for
10\(s_{k}^{*}=\underset{s_{i}\in\mathcal{N}(k-1)}{\arg\min}\)\(\bar{\gamma}_{k}(s)\) ;
11 Update the UAV scheduling vector \(\hat{\mathbf{s}}=\left(\hat{\mathbf{s}},s_{k}^{*}\right)\) ;
12
13 end for
```  
**Algorithm 2**Rollout interference minimization (RIM). To illustrate the improvement of the RIM algorithm compared to the LIM algorithm, we provide an example in Figure 3. In this example, each UAV has two choices for the initial time slot. We focus on applying one step of the RIM algorithm at stage \(k\) and compare it to the LIM algorithm. The node \(\hat{s}_{k-1}\) represents the UAV scheduling vector in stage \(k-1\), the two time slot selections for UAV \(k\) result in two nodes, \(\hat{\mathbf{s}}_{k,1}\) and \(\hat{\mathbf{s}}_{k,2}\). Assuming that \(\gamma_{k}(\hat{\mathbf{s}}_{k,1})<\gamma_{k}(\hat{\mathbf{s}}_{k,2})\), the LIM scheme will select \(\hat{\mathbf{s}}_{k,1}\) based on the node \(\hat{s}_{k-1}\), as indicated by the blue arrow in the figure.