## 1 Introduction  
Typically, underwater acoustic sensor networks (UWSNs) consist of sensors that are deployed to perform collaborative monitoring tasks over a given region, such as oceanographic data collection, marine pollution monitoring, offshore exploration and disaster prevention and tactical surveillance [1, 2, 3]. UWSNs that require to monitor a large geographical area are often configured to operate in a multi-hoptransmission mode. In other words, sensor nodes typically rely on neighboring sensor nodes to relay their transmissions to the default destination which is commonly called a sink for collecting sensor data. Sensor nodes are prone to failures due to fouling and corrosion in the underwater environment. They are battery powered, which implies a limited operational lifetime. Due to the deployment remoteness of UWSNs, replacing faulty or flat sensor nodes incurs high cost. Thus, the deployment of UWSNs plays an important role in the _function_, _efficiency_ and _reliability_ of UWSNs, where (i) the function of UWSNs is related to the fulfillment of timely collection of sensor data, and sensing coverage and network connectivity are two common focuses; (ii) the efficiency of UWSNs is related to the energy consumption for the collection of a unit sensor data and for the operational maintenance of the UWSNs; and (iii) the reliability of UWSNs is related to the maintenance of the proper functions of UWSNs when some sensor nodes fail. There are broadly two strategies in sensor node deployments. If a certain precision of location can be achieved in sensor node deployment, a precise planning of sensor node location can be sought to ensure full functions of complete sensing coverage and network connectivity based on a certain geometrical arrangement with the least number of sensor nodes [4, 5, 6, 7]. The operational efficiency of such UWSNs can also be designed given the knowledge of sensor node geometrical arrangement. However, deploying sensor nodes precisely to their designated locations and maintaining their locations during the operation are often difficult underwater due to constant appearance of current in the environment. Moreover, achieving minimum redundancy of sensor nodes may not be desirable as it introduces low error resilience of operation in UWSNs when sensor nodes fail. In this paper, we consider an UWSN with random sensor node deployment. As opposed to the high-precision deployment of sensor nodes, here sensor nodes are deployed at random locations with no particular geometrical arrangements, which forms a random network. As a result, the function and the efficiency of such UWSN can no longer be guaranteed. Full sensing coverage and network-wide connectivity may not be reached, and operation may not be optimized for energy efficiency. In the aspect of energy efficiency, one key influencing factor is the transmission power of each sensor node. Intuitively, when a higher transmission power is used in a packet transmission, the transmission can reach a longer distance, hence a  
In [8], based on a simulation study, for an underwater environment, [PERSON] and [PERSON] illustrated that the optimal transmission power is found to be the one that corresponds to _minimal connectivity_. In other words, a transmission power from a sensor node just enough to reach its nearest neighbor in the direction towards the final destination gives the optimal use of energy. Their work suggests that in a random network, each node determines its minimum connectivity and then tunes its transmission power accordingly during the operation. By operating at the minimum connectivity, the minimum overall power consumption can be achieved while still maintaining the network-wide connectivity. However, their conclusion is only valid for an ideal situation, where there is no overhead for each transmission and reception. In practice, there are always a minimum transmission power requirement for a packet transmission and a receiving energy consumption.