## 4 Problem Formulation and Algorithm Proposed
### Algorithm Proposed
Other performance indicators, such as the delivery distance distribution and average hop distance, are provided below in Figure 13. It can be seen from the left of the figure that the curve with a higher number of nodes is more dumpy, indicating that with an increase in nodes, the total path length tends to be uniform. The right of the figure shows a mutually corroborating conclusion, namely, the too-high or too-low numbers of hops reduce, and

Figure 12: The connectivity graph of the network with 200 nodes. the waveform energy is concentrated in a certain value of the distance of 200, meaning that the energy consumption of the nodes is balanced. In Figure 14, the performance of the average hop distance (AHD) between MNCTO and UDG are simulated. It is apparent that with CR increasing, the AHD of MNCTO tends to decrease but is still higher than that of UDG. The reason lies in the algorithm generating a target group that a directional node cannot communicate to its adjacent neighbors directly. While taking the energy cost into account, the former is more energy efficient, as is depicted below in Figure 15a, where the scales are all relative:

What can be seen from the above figure is that the relay process of the directional mode saves as much as 90% energy compared to the omni-directional mode. It also has a better performance of the average delivery cost all over the whole network in spite of

Figure 14: Average hop distance comparison. Figure 13: Path length distributions for different node numbers and ratios. Figure 15: Energy cost of a single hop and a successful delivery. its higher path length, as Figure 15b reveals. The figure has two scales: the MNCTO is represented by the ordinate on the left, while UDG is represented by the opposite ordinate. A network implementing MNCTO with appropriate parameters may save more than half of the energy, which is crucial for the underwater environment. Another observation is that, with the expansion of network scale, the average hop cost reduces, the performance differs from Figure 14; the reason lies in the result shown in Figure 13, i.e., the hop distances distributions are more concentrated. Larger CR leads to a longer path distance, neutralizing the advantages brought by short single hop distance; however, it is still comfortably ahead of the omni-directional network. ## 6 Conclusions

From the perspective of the challenges that UASNs are confronted with, such as topology control and energy efficiency, this paper investigates the advantages brought by directional communication technology. However, there are many difficulties involved, among them, the network connectivity being the key challenge to be solved. This research provides a reduction from HPHGG to prove that the issue to connect an UADSN with a \(\pi/3\) beamwidth directional transducer is NP-complete as well as to further the NP-complete proof of connecting the network with minimum cost, which are defined as the TOP and MNCTO problems, individually. Subsequently, a greedy heuristic algorithm is proposed to construct a connected network of \(O(n^{2})\) complexity degree with constant probability 100%; relevant proofs are also provided within the paper. The simulation results show that the proposed algorithm achieves the goal of full connection with lower energy cost, compared with traditional UASNs equipped with omni-directional transducers, which saves more than half of the energy. The research provides some significant guidance for further research in related fields. The authors have equally contributed to the research. [PERSON] conceived the idea of the algorithm described in this paper as well as its relevant proofs and organized, and wrote the manuscript. [PERSON] contributed to the idea in Section 3.1.2 and provided its computational result. [PERSON], [PERSON] and [PERSON] put forward some effective opinions on simulation parameters and methods and supervised the manuscript. All authors have read and agreed to the published version of the manuscript. This research received no external funding. Not applicable.