# A Multi-Hop Clustering Mechanism for Scalable IoT Networks
## 3 Multi-Hop Clustering for IoT Networks
### The Proposed Mechanism
After obtaining \(B_{i}\) for all \(n_{i}\in N\), the element of coordinator set \(C\) is selected from \(N_{u}\) one by one, that is, the \(n_{i}\) whose \(\left|B_{i}\right|\) is \(\underset{n_{j}\in N_{u}}{\max}\left\{\left|B_{j}\right|\right\}\) is selected as the next coordinator to be included in \(C\). When node \(n_{i}\) is selected as the next coordinator to be included in \(C\), the selected node \(n_{i}\), as well as all the nodes in \(B_{i}\), are removed from \(N_{u}\) and then from every \(B_{j}\) for \(n_{j}\in N_{u}\) before proceeding to the selection of next coordinator. The selection continues until \(N_{u}=\varnothing\). For each selection of a coordinator, the comparisons among \(\left|B_{j}\right|\) for \(n_{j}\in N_{u}\) to select the \(n_{i}\) whose \(\left|B_{i}\right|\) is \(\underset{n_{j}\in N_{u}}{\max}\left\{\left|B_{j}\right|\right\}\) occur \(\left|N\right|\) times at most since \(\left|N_{u}\right|\) is at most \(\left|N\right|\). Furthermore, the iterations of this selection step occur at most \(\left|N\right|\) times to complete the selection of coordinators for the set \(C\). The comparisons among \(\left|B_{j}\right|\) for \(n_{j}\in N_{u}\), hence, occur \(\left|N\right|^{2}\) at most, meaning the time complexity of \(\text{O}(\left|N\right|^{2})\). Since a partition of set \(N\) is removed from \(N_{u}\) at each selection step and the selection step continues until \(N_{u}\) becomes empty, the element removal from \(N_{u}\) occurs exactly \(\left|N\right|\) times in total until the set \(C\) is completed. Similarly, the element removal occurs \(\left|N\right|\) times at most for each \(B_{j}\) for \(n_{j}\in N_{u}\). The removal of a node from \(N_{u}\) or \(B_{j}\) for \(n_{j}\in N_{u}\) requires the lookup of that specific node in \(N_{u}\) or \(B_{j}\) for \(n_{j}\in N_{u}\), and it requires, at most, \(\text{log}\left|N\right|\) comparisons since \(\left|N_{u}\right|\) and \(\left|B_{j}\right|\) for \(n_{j}\in N_{u}\) are \(\left|N\right|\), at most. Since all of nodes in \(N_{u}\) have to be removed to complete the selection of coordinators, exactly \(\left|N\right|\) lookups for \(N_{u}\) and at most \(\left|N\right|\) lookups for each of \(B_{j}\) for \(n_{j}\in N_{u}\), respectively, are necessary. Therefore, at most \(\left|N\right|\text{log}\left|N\right|\) comparisons for \(N_{u}\) and \(B_{j}\) for \(n_{j}\in N_{u}\). Therefore, the time complexity to remove all nodes from \(N_{u}\) and \(B_{j}\) for all \(n_{j}\in N_{u}\), that is, the time complexity of completing the selection of coordinators is \(\text{O}(\left|N\right|^{2}\text{log}\left|N\right|)\). The procedure of computing the coordinator set \(C\) proceeds with computing the initial set of \(B_{i}\) for all \(n_{i}\in N\), and then selecting the coordinators. Note the time complexity required for the former is \(\text{O}(\left|N\right|^{2})\), and \(\text{O}(\left|N\right|^{2}\text{log}\left|N\right|)\) for the latter. Therefore, the time complexity of obtaining \(C\) is \(\text{O}(\left|N\right|^{2}\text{log}\left|N\right|)\). Lemma 2: _The time complexity of assigning the best (closest) coordinator among all the available coordinators in \(C\) for every node in \(N\) is \(\text{O}(\left|N\right|^{2})\)._

**Proof. ** Finding the best coordinator for each \(n_{i}\in N\) requires the comparison of \(dist(c_{j},\,n_{i})\) for all \(c_{j}\in C\). Since \(\left|C\right|\) is at most \(\left|N\right|\), the time complexity of finding the best coordinator for all \(n_{i}\in N\) is \(\text{O}(\left|N\right|^{2})\). By determining the best coordinator for all \(n_{i}\in N\), \(M_{j}\), the set of member nodes for each coordinator \(c_{j}\in C\) is computed.