## 4 MEMAC Algorithm Design
### Design and Implementation of Clustering Protocol  
The overall flow of the clustering algorithm in this paper is shown in Algorithm 1, and the steps are as follows:  
1. Initialize the network, set the distance range, D, of the cluster, and start the clustering notification based on the central node. 2. Using Formulas (3) and (4), the multipath channel information R of node i is calculated. The traffic weight \(y_{ij}\) when node i is an ordinary ON node and the total traffic weight W when node i is a CH node are calculated by combining Formulas (6)-(9). 3. By combining Formulas (11)-(15), the revenue \(U_{i}\) of node i participating in the game is obtained. Substitute Formulas (4), (9) and (15) into Formula (22) to find the expected revenue of user i as a PCH node. 4. Node i is used as PCH and NCH, respectively, whether their expected revenues are equal or not. If yes, node i is added to the set of PCH; otherwise, add node i to the set of ON. 5. With the probability \(P_{a}^{i}\) calculated via Formula (26), PCH nodes are elected, as well as a set, \(S_{PCH}=\left\{PCH_{1},PCH_{2},\ldots\ldots\ PCH_{n}\right\}\). If the relation \(RAN_{i}<P_{a}^{i}\) is not satisfied, then the node i sets itself as an ordinary node. 6. All nodes in the \(S_{PCH}\) set participate in the CH node competition, and the node with the lowest \(T_{i}\) value in the set is selected as the CH node. 7. When the probability calculated via Formula (26) is zero, it is determined whether to rotate CH nodes according to Formula (31). If yes, node rotation is carried out. 8. If the formula is not met, go back to Step 6, and start from Step 6. 9. Every time a clustering period, T, is reached, new clustering is performed. The detailed process is as follows:```
0: Dataset \(S_{PCH}=\{PCH_{1},PCH_{2},.......\,PCH_{n}\}\), the random number \(RANi\), total underwater noise \(\sigma^{2}\), the node traffic weight \(W\), the adjustment coefficients \(\theta_{1}\) and \(\theta_{2}\). 1: Using Formulas (3) and (4), the multipath channel information R of node i is calculated. 2: The traffic weight \(y_{ij}\) when node i is an ordinary ON node and the total traffic weight W when node i is a CH node are calculated by combining Formulas (6)-(9). 3: By combining Formulas (11)-(15), the revenue \(U_{i}\) of node i participating in the game is obtained. 4: Substitute Formulas (4), (9) and (15) into Formula (22) to find the expected revenue of user i as a PCH node. 5:for\(i\in[1,N]\)do
6:if\(U_{i}^{\text{expect}}(S_{i}=PCH)=U_{i}^{\text{expect}}\left(S_{i}=NCH\right)\)then\(S_{i}\in S_{PCH}\)
7:else\(S_{i}\in S_{ON}\)
8:endif
9:endfor
10: Initialize the distance, D, between two CHs. 11: Use Formula (26) to calculate the \(P_{a}^{i}\)
12:for\(i\in[1,N]\)do
13:if\(RANi<P_{a}^{i}\)then\(S_{i}=PCH\)
14:else\(S_{i}=ON\)
15:endif
16:if\(S_{i}=PCH\)then\(S_{i}\in S_{PCH}\)
17:endif
18: Use Formula (31) to calculate the \(T_{i}\)
19:if\(T_{i}<T_{j}\) and \(S_{i}\in S_{PCH}\)then\(S_{i}=CH\)
20:else Repeat steps 16-19
21:endif
22:if\(S_{i}=CH\) and \(\delta_{1}\left(\frac{E_{i}^{\text{res}}}{E_{i}^{\text{max}}}\right)+\delta_{2 }\left(\frac{W_{i}}{W_{i}}\right)>1\)then CH rotation
23:else Reapeat steps 11-22
24:endif
25:endfor
26:The CH node is user i (or the CH node is user j)
```

**Algorithm 1** MEMAC algorithm

#### 4.3.1 Network Initialization

Assume that the communication radius of the node is R, the distance between two CH nodes is D, and the length, width, and height of the entire network are, respectively, L, W, and H; g(0.5,1) is a gradient coefficient. If the overlap between clusters is allowed at most for 1/4 of the parts, the distance can be set as follows:

\[D\geq(1+g)R \tag{28}\]

After that, the central node broadcasts a notification to the whole network to start clustering, and then each node in the cluster starts to exchange relevant status information with its neighbor nodes, including node ID, node location, and the energy, \(E_{neigh}\), consumed via the neighbor nodes in the interaction process.