# Towards an Efficient Method for Large-Scale Wi-SUN-Enabled AMI Network Planning
## 4 Proposed Method
### Computational Complexity  
For the computational complexity analysis, more specifically, for the Time Complexity analysis of the AIDA method, it is necessary to consider its main components, which include the dual-tree Boruvka minimum spanning tree (Euclidean MST--EMST) algorithm, the bottom-up (BU) and the top-down (TD) clustering approaches, the depth-first search (DFS) algorithm to establish the MST multihop analysis, and the weighted K-means algorithm, used for grouping routers and selecting gateway positions. \begin{table}
\begin{tabular}{l c c c} \hline
**Parameter** & **Iter. 1** & **Iter. 2** & **Iter. 3** \\ \hline Grid spacing (km) & 5.0 & 2.5 & 1.25 \\ \hline Minimum distance between poles (km) & 3.0 & 1.5 & 0.75 \\ \hline Minimum distance between poles and poles with DA (km) & 1.0 & 1.0 & 1.0 \\ \hline \end{tabular}
\end{table} 
Table 4: Iteration parameters for grid and poles separation. The MST, the clustering algorithms (BU and TD), and the depth-first search algorithm can be run over several iterations until the expected connectivity coverage for existing smart meters is achieved. The weighted K-means algorithm, in turn, is executed only once as the last step of the AIDA method. According to the authors in [40], the EMST dual-tree Boruvka algorithm presents the complexity, \(T(MST)\), established by (13):  
\[T(MST)\approx\mathcal{O}(|\mathcal{V}|\times\log|\mathcal{V}|) \tag{13}\]  
where \(|\mathcal{V}|\) corresponds to the total points of the \(MST\), which is equal to the number of smart meters. To calculate the complexity of the bottom-up (_BU_) algorithm, we can observe the existence of two nested loops (see Algorithm 1). The time complexity must be calculated considering the number of meters \(|\mathcal{V}|\), which establishes the number of executions of the main loop, the existence of the select code responsible for filtering candidate positions that are within reach of each meter, and the execution of the inner loop, which identifies the  
Figure 5: Selected Candidate Positions. Figure 6: Gateway positioning. The figure presents the different clusters computed by the Weighted K-Means algorithm. Each group has a gateway positioned and can have zero or more routers. ideal candidate position for connecting the meter under analysis. The complexity of the BU algorithm, \(T(BU)\), can be established by Equation (14):  
\[T(BU)=\mathcal{O}(|\mathcal{V}|\times|\mathcal{C}|) \tag{14}\]  
where \(|\mathcal{V}|\) is equal to the number of meters and \(|\mathcal{C}|\) is equal to the number of candidate positions within the range of each SM, in the worst case. For the top-down (\(TD\)) algorithm (see Algorithm 2), we can calculate the complexity by observing the existence of one loop that uses a select instruction at each execution to identify/update the list of CPs available for processing. In addition, another select function is performed to update the list of possible connections between meters and CPs. Based on this description, the complexity of the TD algorithm, \(T(TD)\), can be established by Equation (15):  
\[T(TD)=\mathcal{O}(|\mathcal{C}|\times n_{max}) \tag{15}\]  
where \(|\mathcal{C}|\) corresponds to the number of CPs (considered as the worst case), and \(n_{max}\) indicates the maximum number of SMs per CP. For the depth-first search algorithm used for the multihop analysis, the complexity \(T(DFS)\) is computed as (16):  
\[T(DFS)=\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|) \tag{16}\]  
where \(|\mathcal{V}|\) is the number of nodes (smart meters) and \(|\mathcal{E}|\) is the number of edges (connections between smart meters) of the MST. The complexity of the weighted K-means algorithm, \(T(WK)\), is estimated with Equation (17):  
\[T(WK)=\mathcal{O}(|\mathcal{C}|^{2}) \tag{17}\]  
where \(|\mathcal{C}|\) is equal to the number of candidate positions selected to be grouped. Considering the need for a small number of \(i\) iterations, the complexity of the _AIDA_ method (\(T(AIDA)\)) can be established as (18):  
\[