# Smooth 3D Dubins Curves Based Mobile Data Gathering in Sparse Underwater Sensor Networks
## 3 Smooth 3D Dubins Curves Planning-Based Mobile Data Gathering Algorithm
### 3D Dubins Based Mobile Data Gathering Procedures  
All in all, the proposed Bezier interpolation 3D Dubins curves based MDG algorithm has the following key steps.  
Step 1: For the sake of simplicity, the smooth 3D Dubins problem with Bezier interpolation is utilized with the Euclidean distance \(d_{ij}\) between USNs \(S_{i}\) and \(S_{j}\), which is defined as  
\[d_{ij}=\sqrt{(x_{i}-x_{j})^{2}+(y_{i}-y_{j})^{2}+(z_{i}-z_{j})^{2}}, \tag{19}\]  
where \(i,j=1,2,...,n\) and \(i\
eq j\).  
It is noted that the visiting sequence assignment for underwater sensors is modeled as the traveling salesman problem with the following integer programming formulation:  
minimize \[\mathcal{L}(k)=\sum_{i=1}^{n}\sum_{j=1}^{n}k_{ij}\cdot d_{ij},\] (20) \[\sum_{i=1}^{n}k_{ij}=1,\ \ \ \forall j=1,2,\cdots,n,\] (21) \[\sum_{j=1}^{n}k_{ij}=1,\ \ \ \forall i=1,2,\cdots,n,\] (22)  
where Equation (20) is our objective function representing the total distance \(\mathcal{L}(k)\) to visit all underwater sensors. Equations (21) and (22) guarantee that all underwater sensors are visited by the AUV exactly once.  
Step 2: The genetic algorithm (GA)-based heuristic algorithm [25] is used to obtain the optimal sensor node sequence. The procedures of the GA-based iteration calculation for solving the traveling salesman problem are described in Figure 5 with the following critical steps:1. Generate the first random population and evaluate the fitness value; the fitness function is defined as the reciprocal of Euclidean distances.
2. Select the best solutions as parents and use chromosome crossover and mutation operations to generate a new population.
3. Calculate the fitness value of the new population and find the best chromosome.
4. If the best solution satisfies the terminal criteria, we obtain the best chromosome. If not, we need to repeat the above step until the best solution meets the terminal condition.  
Step 3: The optimal orientation of azimuth headings can be selected using the decision table in [26]. For underwater sensors in the middle of the node sequence, the outgoing angle has to be the same as the incoming angle. Furthermore, simplified azimuth headings of AUVs with a finite number of directions, as in Figure 6, are confined by the following equations (cases 1 and 2) to reduce the computational complexity:  
\[\text{Case 1:}\ \Phi=\{\phi=\frac{\lambda\pi}{4}|\lambda=0,1,2,...,7\} \tag{23}\]  
\[\text{Case 2:}\ \Phi=\{\phi=\frac{\lambda\pi}{6}|\lambda=0,1,2,...,11\}. \tag{24}\]  
Step 4: The optimal sequence of sensor nodes is mapped to 3D Dubins curves by 2D Dubins curves' construction in the \(X\)-\(Y\) plane and Bezier interpolation in the \(Z\)-axis.  
Step 5: The derived smooth curves are assigned to the AUV for trajectory cruising and data gathering. In fact, it needs to be explained that the AUV should only cruise and reach within the communication range of the exact sensor's position, as depicted in Figure 7. The detailed interactive process and protocol between sensor nodes and the AUV are omitted because of their simplicity.  
Figure 5: Genetic algorithm (GA)-based iteration process.  
As depicted in Figure 7, the communication range of an underwater sensor is \(R_{max}\). We suppose there are \(W\) bits of sensory data to delivery and that the acoustic communication speed is \(V\) bit/s; \(\mathcal{T}_{C_{k}}\) denotes the cruising time across the communication sphere once the cruising speed of the AUV is normalized. To accomplish the data collecting task for underwater sensor \(S_{i}\), this should be  
\[\mathcal{T}_{C_{k}}\geq\frac{W}{V}. \tag{25}\]  
To be more specific, the sensory data collection process \(\mathcal{T}_{C_{k}}\) should be accomplished in the specified sphere with radius \(R_{max}\). The greater the communication radius, the longer the data acquisition time. However, this article assumes that the communication range is enough for data collection of the AUV. Moreover, this paper simplifies some possible influences caused by wireless acoustic communication.