## 4 Joint Message-Passing and Convex Optimization Framework for UAV Scheduling
### Algorithm Details
#### 4.2.1 MWIS-Based UAV Scheduling via Message-Passing  
Consider an undirected graph \(G=(V,E)\), where \(V\) and \(E\) are the sets of vertices and edges, respectively. Our objective is to select (or schedule) UAVs that can turn off their own built-in surveillance cameras when the corresponding monitoring areas overlap. Thus, we define a visual interference model, where surveillance is considered successful if no neighbor is simultaneously monitoring the same surveillance area. For scheduling, a conflict graph is organized where the set of vertices is connected by an edge if the corresponding vertices cannot be scheduled simultaneously. Based on this concept, the conflict graph can be formulated by an adjacency matrix, whose \(\mathcal{A}_{(i,j)}\) between \(s_{i}\in\mathcal{S}\) and \(s_{j}\in\mathcal{S}\) are defined, as follows:  
\[\mathcal{A}_{(i,j)}\triangleq\left\{ \begin{array}{ll}1,&\text{if $s_{i}$ interferes with $s_{j}$ where $s_{i}\in\mathcal{S}$, $s_{j}\in\mathcal{S}$, and $i\
eq j$.}\\ 0,&\text{otherwise.}\end{array} \right. \tag{6}\]  
The set of neighbors of \(s_{i}\) is defined, as follows:  
\[\mathcal{N}(i)\triangleq\{s_{j}\mid\mathcal{A}_{(i,j)}=1,\,\text{where}\,s_{ j}\in\mathcal{S}\},\,\,\forall s_{i}\in\mathcal{S}. \tag{7}\]  
We consider determining the set of vertices of the conflict graph where adjacent connected vertices via the edges cannot be simultaneously selected. This is equivalent to the case that maximizes the summation of weights of all possible independent sets in a given conflict graph. Thus, scheduling can be formulated with MWIS, as follows [3]:  
\[\max: \sum_{\forall s_{k}\in\mathcal{S}}w_{k}\mathcal{A}_{k},\] (8) s.t. \[\mathcal{I}_{i}+\mathcal{I}_{j}+\mathcal{A}_{(i,j)}\leq 2,\, \forall s_{i}\in\mathcal{S},\forall s_{j}\in\mathcal{S}, \tag{9}\] \[\mathcal{I}_{i}\in\{0,1\},\forall s_{i}\in\mathcal{S}, \tag{10}\]  
where  
\[\mathcal{I}_{i}\triangleq\left\{ \begin{array}{ll}1,&\text{if $s_{i}$ is scheduled where $s_{i}\in\mathcal{S}$,}\\ 0,&\text{otherwise,}\end{array} \right. \tag{11}\]where \(w_{k}\) is a positive integer weight that is associated at each node, and it can be formulated, as follows, in each unit period of time \(t\):  
\[w_{k}\triangleq Q_{k}(t),\,\forall s_{k}\in\mathcal{S}, \tag{12}\]  
where \(Q_{k}(t)\) stands for the battery energy status of UAV \(s_{k}\), as defined in (1). The above formulation ensures that conflicting UAVs are not scheduled simultaneously. If \(\mathcal{A}_{(i,j)}=0\) (no edges between \(s_{i}\) and \(s_{j}\)), then \(\mathcal{I}_{i}+\mathcal{I}_{j}\leq 2\) (i.e., both indicator functions can be 1). In contrast, if \(\mathcal{A}_{(i,j)}=1\), then \(\mathcal{I}_{i}+\mathcal{I}_{j}\leq 1\) (i.e., at most one of the two indicators can be 1). In our considered UAV-based surveillance systems, it can be assumed that the UAVs are vertices and the edges can be established among the vertices (i.e., the UAVs) when the UAVs observe wider overlapping areas because monitoring an area with multiple UAVs is inefficient. The optimization problem (8)-(11) for solving MWIS is a well-known NP-hard problem. To solve this MWIS problem in a computationally efficient manner, we resort to a message-passing approach, which is a message inferential method performed on the conflict graph. Algorithm 1 presents the entire procedure for solving the MWIS problem with message-passing. Note that the message-passing (also called belief propagation, in the literature) can be used to solve our given MWIS problem for any graph [67]. In the standard form, such an algorithm is required to iterate for a while before it converges to (or, stops and estimates) a solution, as illustrated in Algorithm 1. In every single iteration, each node in the graph sends the message to its adjacent neighbors. Each node compares its own weight with the summation of weights in adjacent neighbor nodes during the update phase (line 6-11). Subsequently, each node computes its beliefs and determines whether it should be scheduled or not during the estimation phase (line 12-19).