# OADC: An Obstacle-Avoidance Data Collection Scheme Using Multiple Unmanned Aerial Vehicles
## 3 System Model and Problem Formulation
### System Model  
This study considered a WSN with \(\mathbb{N}(\mathbb{N}=\{0,1,...,\mathrm{n}\})\) sensors, where 0 represents the \"BS (or sink)\". Sensor nodes are deployed in a square area at random places; the positions of the sensors are known a priori. Each sensor periodically generates data and stores them in its buffer until a UAV visits and collects it. Let \(\mathbb{M}(\mathbb{M}=\{1,2,...,\mathrm{c}\})\) be the set of UAVs in the network that collect data from the sensors. Each UAV is associated with the velocity \(v_{m}\) and the flight time \(f_{m}\), in which a UAV needs to finish data collection from all the sensors assigned to it and come back to the BS. In addition, assume that \(\mathbb{O}(\mathbb{O}=\{1,2,...,\mathrm{s}\})\) is the set of obstacles in the environment and the positions of the obstacles are known. If an obstacle is in the path of a UAV, i.e., between any two sensors that the UAV has to visit serially for data collection, it needs to take a detour to avoid the obstacle and reach the next sensor on the path. **Definition 1**. : _Obstacle-constrained distance minimization (OCDM): Assume that \(\mathbb{N}\) is divided into \(\mathrm{c}+1\) subsets, i.e., \(\mathbb{N}_{0},\mathbb{N}_{1},\mathbb{N}_{2},...,\mathbb{N}_{\mathrm{c}}\), where \(\mathbb{N}_{0}=\{0\}\), \(\mathbb{N}_{1}\bigcap\mathbb{N}_{2}...\bigcap\mathbb{N}_{\mathrm{c}}=0\) and \(\mathbb{N}_{1}\bigcup\mathbb{N}_{2}...\bigcup\mathbb{N}_{\mathrm{c}}=\mathbb{N}\). Given \(\mathrm{c}+1  
into the problem formulation, a sensor-obstacle relationship matrix \(\mathcal{R}\) is defined to describe the relationship between sensors and obstacles. That is,  
\[\mathcal{R}_{(i,j)}= \begin{cases}1,&\text{if there is an obstacle between the sensor }i\\ &\text{and }j.\\ 0,&\text{otherwise}\end{cases}  \tag{1}\]  
A binary decision variable \(\mathrm{w}_{ij}^{m}\) is defined whose value is one when arc \((i,j)\) is on the paths of the UAV \(m\), \(m\in\mathbb{M}\), and otherwise zero:  
\[\mathrm{w}_{ij}^{m}= \begin{cases}1,&\text{if arc }(i,j)\text{ is on the path of UAV }m;i,j\in\mathbb{N},\\ &m\in\mathbb{M}.\\ 0,&\text{otherwise}\end{cases}  \tag{2}\]  
Table 1 lists the definitions for the rest of the symbols used in the problem formulation. Therefore, the ILP OCDM problem can be formulated as follows:  
\[\text{minimize }\sum_{m\in\mathbb{M}}\sum_{i\in\mathbb{N}}\sum_{j\in\mathbb{N},j\
eq i}(\mathrm{D}_{ij}(1-\mathcal{R}_{(i,j)})+\mathrm{E}_{ij}\mathcal{R}_{ (i,j)})\,\mathrm{w}_{ij}^{m} \tag{3}\]  
Subject to:  
\[\sum_{m\in\mathbb{M}}\sum_{i\in\mathbb{N},i\
eq j}\mathrm{w}_{ij}^{m}=1,\forall m \in\mathbb{M},j=1,...,\mathrm{n} \tag{4}\]  
\[\sum_{m\in\mathbb{M}}\sum_{j\in\mathbb{N},j\
eq i}\mathrm{w}_{ij}^{m}=1, \forall m\in\mathbb{M},i=1,...,\mathrm{n} \tag{5}\]  
\[\sum_{j\in\mathbb{N},j\
eq 0}\mathrm{w}_{0j}^{m}=1,\forall m\in\mathbb{M} \tag{6}\]  
\[\sum_{i\in\mathbb{N},i\
eq 0}\mathrm{w}_{i0}^{m}=1,\forall m\in\mathbb{M} \tag{7}\]  
\[\sum_{i\in\mathbb{N}_{m}}\sum_{j\in\mathbb{N},j\
eq i}\sum_{(\mathbb{N}_{m}\cup \mathbb{N}_{0}}\mathrm{w}_{ij}^{m}=0,\forall m\in\mathbb{M} \tag{8}\]  
\[\sum_{i\in\mathbb{N}}\sum_{j\in\mathbb{N},j\
eq i}\biggl{(}\frac{\mathrm{D}_{ ij}}{v_{m}}(1-\mathcal{R}_{(i,j)})+\frac{\mathrm{E}_{ij}}{v_{m}}\mathcal{R}_{(i,j)} \biggr{)}\mathrm{w}_{ij}^{m}\leq f_{m},\forall m\in\mathbb{M} \tag{9}\]  
\[\mathrm{u}_{0}^{m}=1,\forall m\in\mathbb{M} \tag{10}\]