## 4 Problem Formulation and Algorithm Proposed
### Algorithm Proposed
In addition, \(ECR_{D}^{O}\) needs to be weighted when compared with the omni-directional mode, and \(d_{u,v}\) should be normalized by a common constant; thus the network deployment boundary is chosen. * Delivery Distance Distribution As the term suggests, this metric counts the distribution of traveling distances of large quantities of packets with random source and sink, which is actually another enhanced metric of network energy consumption that presents key performance intuitively. * Average Single Hop Distance(\(D_{hop}\)) It indicates the average link distance, and can be measured as Equation (25), where \(d_{u,v}\) denotes the traveling path length of a random packet, while \(h_{u,v}\) denotes the hops number between \(u,v\). \[D_{hop}=\frac{\sum d_{u,v}}{h_{u,v}} \tag{25}\]

In order to confirm the performance of the algorithm under stable conditions and meet the premise of Lemmas 1 and 4, MNCTO is designed to be a transmission range free algorithm, meaning that the network implementing MNCTO is always connected without much attention given to the parameter of the transmission range, but it is not the same with an omni-directional network modeled as an unit disk graph (UDG), where a communication link between two peers is set up as long as their distance is less than a certain value. A situation that must be guaranteed is the connectivity of the latter, which is still a challenging topic of research so far [31]; thus, a Monte Carlo analytical method is developed. Various situations with different combinations of nodes number and transmission range are simulated to provide comparisons. ### Simulation Performance

Given an Euclidean 2D square plane and some nodes randomly deployed within the water area, different metrics between underwater acoustic sensor networks running MNCTO and UDG are evaluated. The simulation parameters are listed in Table 2:

The reason why the clustering ratio (CR) is chosen as a parameter bases on an observation that the recursive MNCTO would try its best to make every 9 nodes _target groups_; nevertheless, it is not always necessary because it may generate groups of large communication radii during the anaphase, as Figure 12 exhibits. \begin{table}
\begin{tabular}{c c c} \hline \hline  & \multicolumn{2}{c}{**Network Type**} \\ \cline{2-3}
**Parameter** & **UADSNs** & **UASNs** \\ \hline Connection Algorithm & MNCTO & UDG \\ Deployment Range & 1000 \(\times\) 1000 & 1000 \(\times\) 1000 \\ Number of Nodes & 100–400 & 100–400 \\ Clustering Ratio & 0.2–1.0 & - \\ Transmission Range & - & [150, 200, 250, 300] \\ Unit Distance Energy Cost & 1 & 14.93 \\ Routing Algorithm & Dijkstra & Dijkstra \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Parameters for simulation evaluations. In the figure above, the circle with six sectors denotes a _target group_ with a certain rotation angle; this phenomenon is more obvious on occasions of higher ratio value. Solid circles of the same color within a group denote the corresponding _HexNodes_, while a _TriNode_ is displayed as an isomorphic one with a black edge. The other black squares denote _Outliers_, which should be connected to their nearest _group_. At last, the dashed dotted line indicates that the two _groups_ are connected. Not all connections are shown for the simple purpose that the figure is not chaotic. As can be seen, various numbers of target groups are generated, according to the value of the ratio. Recall that in a network of 200 nodes, the maximum number of groups formed is 22, as, for the greedy MNCTO, it will find as many _target groups_ as possible, so the phenomenon will be inevitable in the convergence stage of the algorithm. A simple but effective method is to limit the upper boundary of the intended number of the _target groups_. In fact, with the increase in the number of _target groups_, the average scope that a group covers decreases as a trade-off, so the gap is not as obvious as imagined.