## 1 Introduction  
Underwater wireless sensor networks (UWSNs) are an aquatic environment monitoring network system that consists of many nodes with data acquisition, storage, processing, and wireless acoustic transmission features. UWSNs have extensive applications in water environmental pollution prediction, ocean exploitation, marine monitoring system, and other areas [1; 2; 3; 4]. With the increasing depletion of land resources, coastal countries are paying increasing attention to maritime rights and resource exploitation, and the ocean economy plays a vital role in the development of the world economy. Therefore, UWSN technology has become a popular research topic in the field of wireless sensor networks. As a technology extension of terrestrial wireless sensor networks (TWSNs) [5; 6] to aquatic environments, UWSNs inherit some characteristics of TWSNs, however due to the special application environment and underwater acoustic communication model of UWSNs, they ordinarily bring some new characteristics, namely, their network structure, which is distributed in three dimensions, high latency of acoustic signal, limited bandwidth of communication, high transmission bit-error-rates, constrained movement of nodes, very limited energy, and others [1; 7; 8]. In view of the abovementioned characteristics of UWSNs, the deployment algorithms and routing protocols of TWSNs cannot be directly migrated to the UWSNs. These new characteristics must be combined to design more reasonably effective deployment algorithms and positioning and routing protocols for UWSNs [9; 10; 11]. The protocol and algorithm design of UWSNs mostly relate to node deployment, topology control, node localization, time synchronization, routing protocol, and others. Meanwhile, the node deployment is not only directly related to the quality of network monitoring but also dramatically affects subsequent processing on the design of all kinds of protocols and algorithms. Therefore, in this study, this basic and crucial problem is further investigated, namely, node deployment. According to whether the target location of the node is determined, the node deployment algorithm of UWSNs can be divided into the following two major categories: stochastic deployment algorithm and deterministic deployment algorithm [12]. After all of the nodes are scattered on the monitoring water surface uniformly and randomly by boat or aircraft, if these nodes only execute random depth adjustment in the vertical direction, then the deployment strategy is referred to as stochastic deployment. If the node can be moved to a definite position calculated by the corresponding optimization algorithm, then the deployment algorithm is referred to as deterministic deployment. Compared to the stochastic deployment, the deterministic deployment can achieve better network performance and therefore is widely used. However, for the node deterministic deployment, based on the assumption of node mobility, the existing deterministic deployment algorithms can be classified into three categories, namely, vertical movement deployment [13; 14; 15], static deployment [16; 17; 18], and free movement deployment [19; 20; 21]. In this study, we mostly consider vertical movement deployment (depth-adjustment deployment). Depth-adjustment deployment refers to the deployment in which all of the nodes only execute depth-adjustment along the vertical direction in the underwater monitoring space. Different from free movement deployment, vertical movement deployment can only achieve node vertical depth adjustment by adjusting the length of the rope or some other economical method [13], thus the vertical movement deployment strategy or algorithm has strong feasibility and applicability. Among existing vertical movement deployments, the deployment strategy based on graph theory in the underwater node deployment is widely used.