## 1 Introduction and Motivation  
In the last few decades, researchers have shown tremendous interest in the deployment of sensor fields called underwater sensor networks (UWSNs) for various applications related to environmental monitoring, tactical surveillance, and reconnaissance data acquisition in oceanic fields. Most of the sensor nodes are interconnected through wireless links in such networks. These wireless links use acoustic signals because the propagation of radio or optical signals is severely affected by a large amount of absorption and scattering loss. However, acoustic signaling imposes many design challenges on communication protocol owing to high bit error rate, limited bandwidth, and long propagation delays. Under such poor channel conditions, high transmission power is necessarily used, and accordingly undesirable interference may occur widely over the network. This introduces a large amount of overhead in the form of retransmissions. Therefore, sensor nodes are forced to communicate with each other over a short distance as a possible way to combat the highly erroneous channels and limit the interference. Accordingly, multihop transmission techniques have been preferred as a data-gathering scheme to collect data distributed over an area into a pre-determined location known as a sink [1]. In a multihop transmission scenario, some sensor nodes act as a relay for other nodes located at a distance from the sink. It is observed that relay nodes consume most of their energy in relaying, and consequently exhaust their energy resources much faster than the other nodes. These relay nodes become ineffective over a period of time owing to rapid energy depletion which eventually results in disconnections in a large network. This phenomenon is known as the energy-hole problem in a sensor network. Therefore, many data-relaying schemes have been proposed for the multihop UWSN in order to reduce such uneven energy consumption in addition to improving other network performance parameters [1; 2; 3]. However, application of these protocols requires excessive bandwidth and energy resources in case of a large-scaled network. [PERSON] and [PERSON] [4; 5] proposed a clustering approach, where the sensor nodes forward data to a node called a cluster head (CH) in a single hop manner. Then, cluster heads employ multihop transmission technique to forward the data to the final destination, a sink. Although this data-relaying technique is an effective way to reduce the energy consumption in a large set of nodes, the issue of uniform energy consumption still remains unsolved for cluster heads. Thus, the need for using a mobile sink arises. The mobile sink can travel to neighborhoods to collect data so that sensor nodes may conserve energy by avoiding multihop and long-distance transmissions. The deep sea networking scenarios described in NorthEast Pacific Time-Series Undersea-Networked experiments (NEPTUNE) [6], Seatooth [7] and Subsea monitoring [8] are such examples, where an AUV visits several data gathering neighborhoods for data collections. In such cases, since the sensor nodes are not easily accessible for maintenance as compared to AUV and other surface elements like buoy, it is imperative to design an energy efficient data-gathering technique to prolong the lifetime of the sensor nodes. In [9], it is shown that an autonomous underwater vehicle (AUV) working as a mobile sink can effectively reduce the transmission range of sensors, which leads to saving energy for sensor nodes during transmission. An AUV travels a specified path and stops at number of locations, called tour points to gather data. The neighborhood of a tour point is highly random in nature because of constantly changing environmental conditions, and therefore is called a probabilistic neighborhood. The AUVprobes the probabilistic neighborhood to discover nodes during a specific time interval called a probe interval. After a probe interval, the AUV creates a communication schedule only for identified sensor nodes.