# Node Deployment of Marine Monitoring Networks: A Multiobjective Optimization Scheme
## 4 Ant-Colony-Based Efficient Topology Optimization (AC-ETO)  
### Algorithm Description  
As the formulated optimization problem is an integer linear programming problem, which is known to be NP-hard [37]. The ant colony is widely used to solve various NP-hard problems. especially [38]. Thus, in this section, we propose an Ant-Colony-based efficient topology optimization algorithm, namely, AC-ETO, to solve the proposed problem in P1. In a traditional ACO algorithm, ants choose the next city through a probabilistic rule, and then iteratively construct the best path [39]. The probability for an ant to move from city \(i\) to city \(j\) is  
\[\text{P}_{ij}=\frac{(\tau_{ij})^{n}\eta_{ij}^{\beta}}{\sum\limits_{j\in\text{ Vallowed}}(\tau_{ij}+\tau_{ij}^{t})\alpha\eta_{ij}^{\beta}}, \tag{21}\]  
where \(\tau_{ij}\) is the amount of pheromone deposited for a transition from city \(i\) to \(j\); \(\alpha\) is a parameter to control the influence of \(\tau_{ij}\); \(\eta_{ij}\) is a heuristic factor for the transition from city \(i\) to \(j\) and is typically inversely proportional to the distance between cities \(i\) and \(j\), i.e., \(\eta_{ij}=1/d_{ij}\); \(\beta\) is a parameter to control the influence of \(\eta_{ij}\); and \(\text{V}_{\text{allowed}}\) is the feasible neighborhood of an ant in city \(i\). In AC-ETO, we select data forwarding paths in the hierarchical HMMN-EC step-by-step. In each step, a probabilistic transition rule is applied to select a deployment location. For example, at node \(i\), the probability that the deployment location \(j\) (\(j\) = 1,2,... \(\text{V}_{\text{FCL}}^{i}\) ) is selected is given by  
\[\text{P}_{ij}=\frac{(\tau_{ij}^{t}+\tau_{ij}^{t})\tau_{ij}^{t}\eta_{ij}^{t}}{ \sum\limits_{j\in\text{V}_{\text{FCL}}^{i}}(\tau_{ij}^{t}+\tau_{ij}^{t})\tau_{ ij}^{t}\eta_{ij}^{\beta}}, \tag{22}\]  
where \(\tau_{ij}^{\prime}\) given in Formula (23) is the global pheromone trail value between node \(i\) and node \(j\); \(\tau_{ij}^{\prime\prime}\) given in Formula (24) is the local value between the two nodes \(i\) and \(j\); \(\eta_{ij}^{\prime}\) is the heuristic value of adding node \(j\) to the connected cover currently being built by the ant, which is defined as Formula (25); and \(\alpha\) and \(\beta\) are parameters that control the influence of the pheromone trail values and heuristic information on \(p_{ij}\), respectively. \(\text{V}_{\text{FCL}}^{i}\) is the Feasible Candidate Location (FCL) set of node \(i\), and FCL is defined as CLs within the communication range of a node. \[\tau_{ij}^{\prime}=(1-\rho_{1})\tau_{ij}^{\prime}+\Delta\tau_{ij}^{\prime}, \tag{23}\]  
\[\tau_{ij}^{\prime\prime}=(1-\rho_{2})\tau_{ij}^{\prime\prime}+\Delta\tau_{ij}^ {\prime\prime}, \tag{24}\]\[\eta^{\prime}_{ij}=\left\{ \begin{array}{cc}\frac{1}{\mathrm{E}_{\mathrm{tr}}}&i \in V_{URN}\cup V_{SSN}\\ 1&otherwise\end{array} \right. \tag{25}\]  
where \(\mathrm{E}_{\mathrm{tr}}^{i}\) is given by Formula (1). \(\Delta\tau^{\prime}_{ij}\) and \(\Delta\tau^{\prime\prime}_{ij}\) are defined as follows:  
\[\Delta\tau^{\prime}_{ij}=\left\{ \begin{array}{cc}\frac{Q-C^{j}}{\mathrm{C} _{bestnet}}&e_{ij}=1\\ 0&otherwise\end{array} \right. \tag{26}\]  
\[\Delta\tau^{\prime\prime}_{ij}=\left\{ \begin{array}{cc}\frac{Q-C^{j}}{ \mathrm{C}_{path}}&e_{ij}=1\\ 0&otherwise\end{array} \right. \tag{27}\]  
where \(C^{j}\) is the cost of node \(j\), \(C_{bestnet}\) is the current minimum network cost, and \(C_{path}\) is the cost of the path. \(Q\) is a constant greater than 1, and \(\rho_{1}\) and \(\rho_{2}\) are the rates of global and local pheromone evaporation. The process of AC-ETO is divided into two phases. The first phase is the initialization phase, which reduces the search space so that only FCLs are selected and stored by certain nodes. The second phase is the planning phase, where the optimization process is iteratively performed to construct the network topology and remove the redundant edges until the desired result is reached. We first use a small-scale network with 2 MPs as an example to describe the algorithm.