# Node Deployment of Marine Monitoring Networks: A Multiobjective Optimization Scheme
## 4 Ant-Colony-Based Efficient Topology Optimization (AC-ETO)
### Algorithm Description
In the initialization phase, the distances between nodes are calculated based on the location of nodes. Each node then constructs a FCL table which includes all nodes in its communication coverage. For instance, the FCL table of MP0 includes URN0 and URN1. In the planning phase, a number of iterations are involved. In each iteration, a number of ants are placed on each MP to construct paths to the BS by using the probabilistic rule, the local pheromone, and the global pheromone defined in (22)-(24). An ant placed on MP0 moves to the next node, e.g., URN0 in the FCL table according to the pheromones and the transition probability until it arrives at the BS. After the ant reaches the BS, the BS informs all nodes along the path to update the local pheromone and selects the best path from multiple ants, e.g., MP0-URN1-SSN0-ECN0-ARN1-BS0 and MP1-URN2-SSN2-ECN0-ARN0-BS0 in the 2-MP example, as shown in Figure 1(a). Notice that the two paths are independently found by ants and there may be multiple links between two nodes, e.g., ECN0-ARN1-BS0 and ECN0-ARN0-BS0. In such case, the two links are compared and the path with higher energy consumption, e.g., ECN0-ARN0-BS0, is removed to obtain a tree with \(\mathbb{C}_{net}+\omega\mathrm{E}_{\mathrm{max}}=68.417\), as shown in Figure 1(b). The iteration repeats until no better tree with a smaller \(\mathbb{C}_{net}+\omega\mathrm{E}_{\mathrm{max}}\) can be found. The pseudo code of the proposed AC-ETO is elaborated in Algorithm 1. Figure 2: The topology of the network with 2 MPs; (**a**) Before removing; (**b**) After removing. ```
1:Input:\(V_{\text{MP}},V_{\text{URN}}V_{\text{SSN}},V_{\text{ECN}},V_{\text{ARN}},V_{\text{BS}}\)
2:Phase I: Initialization
3:Input positions of nodes and other parameters;
4:\(N\leftarrow|V|\);
5:\(D_{N\times N}\leftarrow\) the distance between nodes;
6:for\(i=1\) to \(N\)do
7:\(T^{i}_{\text{Feuble}}\gets FCLtable\_Bld(i)\);
8:endfor
9:Phase II: Multi-objective planning
10:\(M\_Global_{N\times N}\leftarrow\{1\}\);
11:\(V_{start}\leftarrow V_{\text{MP}}\), \(M\leftarrow|V_{\text{MP}}|\);
12:repeat
13:Step 1-Network construction
14:for\(i=1\) to \(M\)do
15: Take a MP j randomly from \(V_{\text{start}}\);
16: Place m ants on j; \(\backslash\) m is a constant integer
17:for each ant \(r=1\) to \(m\)do
18:\(M\_Local_{N\times N}\leftarrow\{1\}\);
19: Put j into node_list of r: \(V^{r}_{list}\gets V^{r}_{list}\cup\{j\}\);
20:\(k\gets j\);
21:\(M\_prob_{N\times N}\leftarrow\{0\}\);
22:while (\(l\
otin V_{\text{BS}}\))do
23: Choose and move to next node k from \(T^{k}_{\text{Feuble}}\);
24:\(V^{r}_{list}\gets V^{r}_{list}\cup\{k\}\);
25:endwhile
26: Calculate the cost of \(V^{r}_{list}\);
27: Calculate the energy consumption of each node t:\(EC_{t}\) ;
28:endfor
29: Choose the best path for MP j from \(\{V^{1}_{list},...,V^{m}_{list}\}\rightarrow list_{j}\);
30: The Cost of \(list_{j}\rightarrow\text{C}_{j}\);
31: Calculate the energy consumption of each node t:\(EC_{t}\) ;
32: Update \(M\_Local_{N\times N}\);
33:endfor \(\backslash\) Step 2-Redundant edge removal
34: Remove redundant edges from the initial constructed network;
35: Update \(M\_Global_{N\times N}\);
36:until iterative number \(>\)\(\psi\))
37:Output: the optimal solution, total cost, and energy consumption;
```  
**Algorithm 1** The pseudo code of AC-ETO algorithm