# An AUV-Aided Cross-Layer Mobile Data Gathering Protocol for Underwater Sensor Networks +
## 4 Description of Our Proposed Cross-Layer Mobile Data-Gathering Protocol
### AUV Discovery Phase  
The cluster heads are selected during the Distributed Clustering Phase and AUV has no prior information about them. During the Discovery phase, AUV travels on a predefined path (e.g., moving-the-lawn pattern) and broadcasts small beacon packets to discover the CHs (e.g., polling the environment). Then, a nearby CH will reply by sending a small beacon to the approaching AUV. The CH (with the AUV current location) will then be added to the AUV list. Algorithms 1 and 2 detail the operation process between AUV and CH during the discovery phase. ```
1 Procedure AUV discovery ()
2 AUV starts from offshore sink and travels through a predefined path
3 whileAUV.location()!= offshore-sink.location()do
4 AUV broadcasts bc
5 ifAUV receives a rbcthen
6 new-CH \(\leftarrow\) rbc.ID
7 new-CH.location \(\leftarrow\) AUV.location()
8 foreachCH\({}_{i}\) in the AUV.CH-listdo
9 tempDist \(\leftarrow\) calculate Distance (new-CH, CH\({}_{i}\))
10 if(tempDist \(<=\) 2R)then
11 Remove CH\({}_{i}\);fr\({}_{n}\) from Ava-fr
12
13 Add new-CH and new-CH.location to AUV.CH-list
14 new-CH.fr \(\leftarrow\) first available frame from Ava-fr
15
16 AUV sends Ack to the new-CH about its frame number
17



### Normal Operational Phase

We illustrate the normal operational phase from two aspects: AUV data gathering and intracluster communication. #### 4.5.1 Auv Data Gathering

In the AUV data gathering mission, the objective is to visit all CHs in the underwater environment in the shortest possible tour. This problem can be formulated into a well-known problem called the Traveling Salesman Problem (TSP) which is an NP-hard problem [22]. A greedy heuristic approach is adopted from our previous work [22] to obtain the near-optimal solutions in less computational time. The 2-opt algorithm is also used to incrementally improve the initial tour by converting it to a tour without any crossed line. This algorithm swaps all possible pairs of edges while the current solution is replaced by the new one if the new tour is shortened [22]. This procedure will be stopped if no further improvement can be found. Data packets are collected by each CH in a fixed rate and this procedure is independent of the AUV activity. After the tour planning, the AUV initiates its tour to collect the aggregated data. When AUV arrives, the CH transfers the buffered data to the AUV. Upon the arrival of the AUV, a control packet is sent by the AUV to inform the approaching CH. All cluster members will be suspended after receiving the CH notification packet regarding the AUV arrival. Then, CH starts to transfer the data packets to the AUV. This procedure is repeated for the next CH within the tour until all CHs are visited. AUV finally returns to the sink to upload the collected information. This procedure has been shown in Figure 2. The next round of data gathering is similarly repeated. Figure 2: How the autonomous underwater vehicle (AUV) discovers cluster head and assigns different frames for each. #### 4.5.2 Intracluster Communications

The operational phase consists of several rounds, each of which includes two frames. Each frame includes several slots which are assigned for the data transmission or reception. In the operational phase, in periodic time slots, sensors become awake to transmit or receive data packets in some slots while they are in a sleeping mood in remaining slots. It means that sensors stay asleep when there is no data to be sent or received. The purpose of having two frames in each round is to allow neighboring CHs assigning different frames (i.e., transmission time), as shown in Figure 3. During the second phase, CHs have already reserved the frames in a way that adjacent clusters have been assigned with different frames. This is because it guarantees that no collision occurs between members of different clusters. Each cluster member also reserves a specific time slot during the distributed clustering phase in a way that there would be no conflict with other members within the same cluster.