## 4 Problem Formulation and Algorithm Proposed
### Algorithm Proposed
As for the former situation, \(b,c\) are covered by \(a\) because \(\mathcal{L}\) passes through \(O_{2}\); together with the reason that the beam boundaries of \(HexNode\) are parallel with the sectors boundaries, the coverage area of \(b\) and \(c\) is \(2\pi/3\). Considering that \(a\) lies opposite of \(b\) or \(c\), the angle of \(O_{2}\to a\) with \(\mathcal{L}\) must be less than \(\pi/3\), so \(b\) or \(c\) is affirmative to cover \(a\). In another situation in which \(b,c\) are covered by \(a\) and \(d\) individually, the center \(O_{1}\) must be covered by either \(b\) or \(c\), which is assumed to be \(c\), as Figure 11 shows. With the help of guideline \(\mathcal{L}\), we find that the included angle \(aO_{1}\) with \(\mathcal{L}\) is less than \(\pi/3\), so \(a\) is sure to be covered by either \(b\) or \(c\). In this way, the validation that two _target groups_ are connected in the case of \(dist<D_{t}\) is proved. While in Case 2, we know that all \(HexNodes\) of a _target group_ are covered by a single \(HexNode\), the situation will be the same with the first situation of Case 1, and therefore, they are connected too. Thus, we prove the truth of Lemma 4. For the last step, we just need to set up links between the _target group_ and between the _target group_ and _target group_, as well as links between _target groups_ and outliers, as the Algorithm 3 describes below:

Figure 11: Two target groups are connected in the case of \(DIST<D_{t}\). ```
1:Input:Target groups \(gGroups\), Isolated nodes \(outliers\)
2:Output: Void
3:procedureEstablish_Full_Connections(\(gGroups,outliers\))
4:\(MAXDIST=65536\)
5:\(gGroups\gets MST(gGroups)\)// Establish MST for \(gGroups\) centers
6:for all\(group\in gGroups\)do// link \(target\)\(group\) with peers
7:if\(group\) not \(tar\)then
8: link \(group\) with \(tar\)
9:endif
10:endfor
11:for all\(node\in group\)do// link \(TriNodes\) with \(HexNodes\)
12:if\(node\in TriNodes\)then
13: link \(node\) with its peer // peer: node locating in opposite sector
14:endif
15:for all\(node\in TriNodes\)do// link \(TriNodes\) themselves
16: find \(node\) corresponding to the smallest angle
17: link \(node\) with other 2 \(TriNodes\)
18:endfor
19:endfor
20:for all\(node\in outliers\)do// link outliers with their nearest \(target\)\(group\)
21:\(tGroup\gets null\)
22:\(dist\gets MAXDIST\)
23:for all\(group\in gGroups\)do
24:if\(distance(node,group)\leq dist\)then
25:\(dist\gets distance(node,group)\)
26:\(tGroup\gets group\)
27:endif
28: link \(node\) with \(tGroup\)
29:endfor
30:endfor
31:endprocedure
```

**Algorithm 3** MNCTO. In this way, connections for all the nodes in network are established. An artifice of recursion is adopted in Algorithm 1, aiming at finding as many target groups as possible, which guarantees that the algorithm can be maximally energy efficient. ## 5 Simulation Evaluations

In order to provide a detailed performance exhibition of the proposed MNCTO algorithm, several metrics such as the total energy consumption and average hop distance are designed to quantify the algorithm performance; a comparison of the omni-directional mode is provided as reference. ### Performance Metrics

* Network Energy Cost (\(E_{nc}\)) The energy consumed by a network \(G=(V,E)\) originates from packets delivered from the source node to sink node. In ad hoc networks, all nodes are homogeneous and able to act as at least one of sender/relay/sink, so the metric \(E_{nc}\) is defined to evaluate the energy efficiency, as shown below: \[E_{nc}=\frac{1}{N}\sum_{i=1}^{N}\sum_{u,v\in V}d_{u,v}^{k},\qquad u\
eq v\] (24)where \(N=1000\) random packet paths are counted, \(u,v\) in denote arbitrary two stochastic nodes and \(d_{u,v}^{k}\) implies that the cost is positively correlated to the spreading distance (see Equation (18)), where \(k\) denotes the spreading factor that ranges from 1 to 2 in an underwater environment; thus a median of 1.5 is used.