## 3 AUV-Aid Underwater Data Gathering Problem
### Problem Formulation
Because of the interference in acoustical communication, each sensor can only transmit to or receive from another sensor through a specific acoustic channel at a time (Equation (5)). We use a binary variable \(\chi^{m}_{ij}(t)\) to indicate the sub-channel state. If node \(i\) transmits data to node \(j\) on sub-channel \(m\) at time \(t\), \(\chi^{m}_{ij}(t)=1\). Otherwise, \(\chi^{m}_{ij}(t)=0\). In Equation (6), \(\mathcal{I}^{j}_{m}\) is the sensor set within the \(j\)th sensor's interference range on channel \(m\). If sensor \(j\) is within the interference range of sensor \(k\) on sub-channel \(m\), and sensor \(k\) is transmitting data to its neighbor \(l\) via \(m\) sub-channel, then sensor \(j\)'s neighbor \(i\) will fail to transmit to sensor \(j\) through sub-channel \(m\) at this time because of signal interference (Equation (6)). Equation (8) to (14) are data flow constraints. We define \(S_{A}\) and \(S_{U}\) to represent the sensor sets that will be visited by AUV and will not be visited by AUV, respectively. Then there is no data flow to \(S_{U}\) sensors (Equations (8) and (9)) and no data flow from \(S_{A}\) sensors (Equations (10) and (11)). Moreover, the data flow from an \(S_{U}\) sensor equals the data it sensed (Equation (12)), and the outgoing data of each sensor is the sum of the incoming data and its sensing data (Equation (13)). Variable \(v_{i}\) in Equation (12) is the sensing rate of sensor \(i\). In addition, the data flow on each sub-channel should not exceed the link capacity (Equation (14)). Variable \(c^{m}_{ij}\) in Equation (14) is the channel capacity between sensor \(i\) and sensor \(j\) on sub channel \(m\). Equation (15) means that, during the data gathering process, each node should not spend more energy than its remained energy. Variable \(d_{i}\) in Equation (16) is the buffer size of the \(i\)th sensor, and Equation (16) constrain the data amount stored on an \(S_{A}\) sensor should not exceed the buffer size of this sensor. A binary variable \(y_{i}\) is used to indicate the sensor type. If sensor \(i\) is an \(S_{A}\) sensor, then \begin{table}
\begin{tabular}{c l} \hline \hline \(d_{ij}\) & The distance between node \(i\) to node \(j\). \\ \(c_{i}\) & The coordinate of node \(i\). \\ \(\chi^{m}_{ik}(t)\) & A binary variable, that equals to 1 if node \(i\) transmits data to node \(j\) on sub-channel \(m\) at time \(t\). \\ \(N_{i}\) & The neighbor node set of node \(i\). \\ \(D_{ik}\) & The data amount from node \(i\) to node \(k\). \\ \(c^{m}_{ij}\) & The channel capacity between node \(i\) and node \(j\) on sub channel \(m\). \\ \(y_{i}\) & An indicator that equals 1 if node \(i\) is an \(S_{A}\) node. \\ \(S_{A}\) & The node set that will be visit by an AUV. \\ \(S_{U}\) & The node set that will not be visit by an AUV. \\ \(S_{C}\) & The node set that need to be confirm whether will be visit by AUV. \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Notations. \(y_{i}=1\). Otherwise, \(y_{i}=0\). Equations (18) and (19) are the travel tour constraints that each chosen sensor must visit exactly once. In addition, the AUV stop time on each sensor for data gathering is:  
\[t_{i}=\frac{v_{i}\Delta t-\sum\limits_{j\in\mathcal{N}_{i}}D_{ji}+\sum\limits_ {j\in\mathcal{N}_{i}}D_{ji}}{m},\forall i\in S. \tag{20}\]  
Since there is a polynomial-time reduction from the traditional traveling salesman problem to the above problem by setting \(p_{i}^{in}\) and \(p_{i}^{out}\) to zero, the above problem is an non-deterministic polynomial-time hard (NP-hard) problem. We implement the problem using Matlab+YALMP+GUROBI and found that, for a small scenario with no more than eight nodes, it takes more than an hour to find the optimal solution. Considering that this problem is NP-hard, the execution time would grow exponentially, and we propose a heuristic algorithm \(HAS^{4}\) to solve this problem in the following section.