# OADC: An Obstacle-Avoidance Data Collection Scheme Using Multiple Unmanned Aerial Vehicles
## 3 System Model and Problem Formulation
### System Model
\begin{table}
\begin{tabular}{c c} \hline \hline
**Notation** & **Definition** \\ \hline n & number of sensors \\ c & number of UAVs or clusters \\ s & number of obstacles \\ \(\mathbb{N}\) & set of sensors, \(\mathbb{N}=\{0,1,...,n\}\) \\ \(\mathbb{M}\) & set of UAVs, \(\mathbb{M}=\{0,1,...,c\}\) \\ \(\mathbb{O}\) & set of obstacles, \(\mathbb{O}=\{0,1,...,s\}\) \\ D\({}_{ij}\) & traveling distance in case of no obstacle \\  & between sensor \(i\) and \(j\) \\ E\({}_{ij}\) & traveling distance in case of an obstacle \\  & between sensor \(i\) and \(j\) \\ \(v_{m}\) & velocity of UAV \(m\) \\ \(f_{m}\) & UAV flight time constraint \\  & a sensor-obstacle relationship matrix to define \\ \(\mathcal{R}\) & the relationships between sensors \((i,j)\) and the \\  & obstacle among them \\ \hline \hline \end{tabular}
\end{table} 
Table 1: List of notation. \[\mathrm{u}_{i}^{m}-\mathrm{u}_{j}^{m}+1\leq(|\mathbb{N}_{m}|-1)(1-\mathrm{w}_{ij}^{ m}),\forall m\in\mathbb{M};i,j\in\mathbb{N}_{m}\setminus\{0\} \tag{11}\]  
Equation (3) represents the objective function of the OCDM problem, where the total traveling distance of all UAVs is minimized considering obstacles in the environment. Constraints (4) and (5) ensure that each sensor in \(\mathbb{N}\) is visited exactly once by only one UAV except the BS. Equation (6) ensures sure that UAV \(m\) starts its journey from the BS to any other sensor \(j\), and Equation (7) assures that UAV \(m\) returns to the BS from exactly one sensor \(i\), so \(\sum_{i\in\mathbb{N},j\
eq 0}\mathrm{w}_{i0}^{m}=1\). Constraint (8) ensures that UAVs do not travel among two nodes in \(\mathbb{N}\), which belong to two different groups or subsets. Equation (9) represents the UAV flight-time constraint, which assures that each UAV \(m\) will finish its tour within a given flight time \(f_{m}\). Equations (10) and (11) eliminate the sub-tour in the path of each UAV while visiting the sensor nodes, avoiding the obstacles in each group \(\mathbb{N}_{m}\). Since the multiple traveling salesman (mTSP) problem, which is NP-hard, is polynomial time-reducible to OCDM, OCDM is an NP-hard problem. **Proposition 1**. : _OCDM is NP-hard._  
Proof. : It can be shown that an mTSP [28] is polynomial-time reducible to OCDM, i.e., mTSP \(\leq_{p}\) OCDM. Assume an mTSP instance with a set of \(n\) \"cities\" \(k_{1},\ldots,k_{n}\), \(c\) number of salesmen, a distance \(d(i,j)\) between each pair of cities \(i\) and \(j\) (\(1\leq i,j\leq n\)), and an integer \(L\). The corresponding OCDM instance has \(n\) sensor nodes, \(c\) UAVs, and assume that there are no obstacles between any two sensors. Each sensor node and UAV in the OCDM instance correspond to a city and a salesman in the mTSP instance, respectively, and the distance between two sensor nodes \(i\) and \(j\) is the same as \(d(i,j)\). Then, it is clear that if the mTSP instance has \(c\) tours with a total tour length \(L\), the total path length of the OCDM becomes \(L\) with \(c\) paths. Conversely, if the total length of \(c\) paths is \(L\) in OCDM, the total tour length of \(c\) tours becomes \(L\) in the mTSP. Since mTSP is an NP-Hard problem (mTSP is a generalization of the TSP, which is a well-known NP-Hard problem [29]), so is the OCDM.