Self-deployment of sensors with maximized coverage in Underwater Acoustic Sensor Networks (UWASNs) is challenging due to difficulty of access to 3-D underwater environments. The problem is further compounded if the connectivity of the final network is desired. One possible approach to this problem is to drop the sensors on the water surface and then move them to certain depths in the water to maximize the 3-0 coverage while maintaining the initial connectivity. In this paper, we propose a fully distributed node deployment scheme for UWASNs which only requires random dropping of sensors on the water surface. The idea is based on determining the connected dominating set (CDS) of the initial network on the surface and then adjust the depths of all neighbors of a particular dominator node (i.e., the backbone of the network) for minimizing the coverage overlaps among them while still keeping the connectivity with the dominator. The process starts with a leader node and spans all the dominators in the network for repositioning them. In addition to depth adjustment, we studied the effects of possible topology alterations due to water mobility caused by several factors such as waves, winds, currents, vortices or random surface effects, on network coverage and connectivity performance. On the one hand the mobility of nodes may help the topology to get stretched in 2-D, which helps to maximize the coverage in 3-0. On the other hand the mobility may cause the network to get partitioned where some of the nodes are disconnected from the rest of the topology. We investigated the best node deployment time where 2-D coverage is maximized and the network is still connected. To simulate the mobility of the sensors, we implemented meandering current mobility model which is one of the existing mobility models for UWASNs that fits our needs. The performance of the proposed approach is validated through simulation. Simulations results indicate that connectivity can be guaranteed regardless of the transmission and sensing range ratio with a coverage very close to a coverage-aware deployment approach. (C) 2014 Elsevier B.V. All rights reserved.