## 1 Introduction  
Underwater wireless sensor networks (UWSNs) are network-monitoring systems in an underwater environment. The sensor nodes in these networks have perceptual, acoustic communication, and computational capabilities, and they can transmit the sensed information to the sink node for processing and analysis by one-hop or multi-hop methods [1; 2]. UWSNs have been applied to water environment monitoring, underwater resource exploration, and marine military defense [3; 4]. Research on UWSNs [5] mainly involves network architecture design [6], node deployment, node localization [7; 8], time synchronization [9], network protocol design [10; 11], etc. As the first step in UWSNs application, node deployment significantly affects network service in different aspects, including network coverage, network connectivity, and network energy consumption. The node-deployment problem is defined that move sensor nodes to the corresponding positions in an artificial or a self-organized manner to form a network topology that has special characteristics and increases the network service [4; 12]. Meanwhile, the goals of node deployment are to increase network coverage and network connectivity, decrease network energy consumption, and prolong network lifetime. Generally, the problem of node deployment can be divided into static deployment, move-restricted node self-deployment, and free-to-move node self-deployment according to the mobility of the node [2; 13; 14; 15; 16; 17]. In static deployment, the nodes cannot move and are deployed in the target area by the artificial method [14]. Thus, static deployment is not appropriate for the large-scale deployment. In move-restricted node self-deployment, the nodes can move only vertically and adjust their depth by themselves according to the local information near the node [18]. In free-to-move node self-deployment, the nodes have the capability to move freely in all directions [19]. With the improvement of the design level of the sensor node, the cost of the mobile nodes is reduced and more and more scholars concentrate on the research of free-to-move node self-deployment. Moreover, free-to-move node self-deployment is closer to the reality. Therefore, free-to-move node self-deployment has wide application scenarios and has important research significance. The existing free-to-move node self-deployment algorithms [20; 21; 22; 23; 24; 25] usually regard the event coverage as the research object, and aim at the network coverage, but these algorithms do not regard the network connectivity and network reliability as the goal simultaneously. Furthermore, in these algorithms, each node should move several rounds to determine the final deployed position, which increases the network deployment energy consumption. Consequently, there is still much space to improve the performance of free-to-move node self-deployment algorithms. Thus, the current paper proposes the pigeon-based self-deployment algorithm (PSA) to solve these problems. The sink node first finds its one-hop nodes and maximizes the coverage in its one-hop region. This process allows for the maintenance of the number of the nodes deployed in the region near the sink node and increases network reliability and network coverage as much as possible. The one-hop nodes then divide the network into layers and cluster in every layer. This mechanism forms a distribution in which the scale of the cluster is small and the number of cluster head nodes is great in the region close to the sink node. The cluster head nodes do not move again, thus, the number of nodes in the region close to the sink node increases. Each cluster head node subsequently constructs a connected path to the sink node to guarantee network connectivity. Finally, the cluster head node regards the ratio of the movement distance of a cluster-in node to the change in the coverage redundancy ratio (CRR) of the node as the target function on the premise that the cluster-in node should be connected to the cluster head node by one-hop or multi-hop path.