# Node Deployment of Marine Monitoring Networks: A Multiobjective Optimization Scheme
## 4 Ant-Colony-Based Efficient Topology Optimization (AC-ETO)
### Computational Complexity Analysis  
In this subsection, we analyze the computational complexity of the proposed (AC-ETO) algorithm.  
Phase I: Initialization (Lines 1-7): In the initialization phase, the locations of a number of network nodes, including BS, MPs, CLs of ARNs, ECNs, SSNs and URNs, are imported. Accordingly, the network parameters such as communication distance, initial energy, and transmit and receive power are set. The complexity of initialization is \(O(N)\), where \(N\) is the network size. Then, the distance matrix between neighboring nodes are calculated first, and the complexity is \(O(N^{2})\). According to the distance matrix, each node maintains an FCL table that includes the list of nodes that it can directly communicate with. For example, an URN list a set of other URNs and/or SSNs in its communication coverage. The worst-case complexity is \(O((N-1)(N-M))\). Therefore, the complexity of Phase I is \(O(2N^{2}-MN-N+M)\).  
Phase II: Topology planning (Lines 8-34): Based on the FCL tables calculated in phase I, an AC-basedoptimal method is used to find the placement of the minimum cost and the energy consumption. The algorithm is iteratively performed for network construction and redundant edge removal until a desirable result is reached. In Lines 9-10, the matrix of global pheromone is initialized to 1 by the memset function with a complexity of \(O(N)\), and the subset \(\mathrm{V_{MP}}\), which has \(M\) elements, is set as the set of starting points \(\mathrm{V_{start}}\) and the complexity is \(O(M)\), where M is the number of MPs. In Lines 11-34, the iterative optimization process is executed, where Lines 12-31 are for Step 1--Network construction, and Lines 32-33 are for Step 2--Redundant edge removal. In Step 1, an ant colony is placed on a MP which is randomly selected from \(\mathrm{V_{MP}}\), and then moves to construct paths towards the BS. By comparing the values of (9) for each feasible path, the best one--the one with the minimum value of (9)--is selected and stored. When \(M\) ant colonies complete path construction, the sequences of \(M\) best paths are selected to construct a network. Step 1 yields the worst case complexity \(O(MN^{2}+MN+M^{2})\). In Step 2 (Lines 32-33), the result of Step 1 is modified by removing some redundant edges according to the characteristics of the tree structure constraints, and the complexity of this step is \(O(N^{2}+M^{2}+M)\). Figure 2 shows an example of Step 2. Figure 2a shows the constructed network topology after step 1. It can be seen that the structure is not a tree topology as the out degree of \(ECN_{0}\) is 2. In Figure 2b, two redundant edges are removed from the network to form a tree topology. Thus, the complexity of Lines 12-33 is as follows.  
\[O(MN^{2}+MN+M^{2})+O(N^{2}+M^{2}+M)=O(MN^{2}+N^{2}+MN+2M^{2}+M).\]  
Accordingly, if \(N\) is sufficiently large, the complexity of Phase II is approximately \(O(\psi MN^{2}+\psi MN+\psi M^{2}+\psi M)\), where \(\psi\) is the maximum number of iterations.  
Therefore, the overall computation complexity of the algorithm is \(O(2N^{2}-MN-N+M)\)+\(O(\psi MN^{2}+\psi MN+\psi M^{2}+\psi M)\approx O(\psi MN^{2}+\psi MN+\psi M^{2})\). The AC-ETO is efficient and achieves a polynomial time complexity.