# A Multi-Hop Clustering Mechanism for Scalable IoT Networks
## 3 Multi-Hop Clustering for IoT Networks
### The Proposed Mechanism
\(\square\)

To reduce \(C\) further, for \(c_{i}\) with \(\left|M_{i}\right|=1\), that is, for the coordinator with no member node, \(dist(c_{j},\,c_{i})\) for all \(c_{j}\in C\) with \(\left|M_{j}\right|\geq 2\) and \(dist(c_{j},\,c_{i})\leq H\) are compared to determine whether \(c_{i}\) can be eliminated from \(C\), and if so, to choose the best coordinator for \(c_{i}\). The number of coordinator \(c_{i}\) with \(\left|M_{i}\right|=1\) and the number of coordinator \(c_{j}\) with \(\left|M_{j}\right|\geq 2\) and \(dist(c_{j},\,c_{i})\leq H\) are at most \(\left|C\right|\), andin turn \(|C|\) is at most \(|N|\). Therefore, the time complexity to choose coordinators for the coordinators that have no member for further reduction of \(C\) is also \(\mathrm{O}(\left|N\right|^{2})\). **Theorem 1**. : _The time complexity of proposed mechanism is \(O(\left|N\right|^{2}\log\left|N\right|+\left|N\right|\left|E\right|)\)._

Proof. : The time complexity of obtaining the coordinator set \(C\) and assigning the best coordinator for each node in \(N\) are analyzed in Lemmas 1 and 2, respectively. Therefore, the time complexity of the proposed mechanism is \(\mathrm{O}(\left|N\right|\left(\left|N\right|\log\left|N\right|+\left|E \right|\right)+\left|N\right|^{2}\log\left|N\right|+\left|N\right|^{2})= \mathrm{O}(\left|N\right|\left(\left|N\right|\log\left|N\right|+\left|E \right|\right))\), where \(\left|E\right|<\mathrm{O}(\left|N\right|^{2})\). That is, the time complexity of proposed mechanism is determined by the [PERSON]'s SPF algorithm to determine \(dist(n_{i},\ n_{j})\) for all \(n_{i},\ n_{j}\in N\). \(\square\)

## 4 Performance Evaluation

The performance of the proposed mechanism is analyzed and compared to that of the brute-force-based optimal solution. The objective of mechanism is to minimize the number of coordinators while satisfying the QoS requirements, which is represented as the number of maximum hop count from a node to its coordinator, so that the number of required Internet connections is minimized with the given QoS constraint. Furthermore, it is desirable for a node to be connected to the nearest coordinator among the available ones to conserve the wireless resource, as well as to minimize the delay. Hence, the performance metrics are the \"number of selected coordinators\" and the \"average hop counts from a node to its coordinator\". The experimental settings and the compared optimal solutions are first explained in Section 4.1, and in Section 4.2 the numerical results are presented. ### Experimental Settings

Selecting the optimal and minimum number of coordinators among the \(|N|\) nodes while satisfying the maximum hop count constraint is an NP-hard problem and, thus, the size of the network for which the optimal solution is applicable is very limited. As seen in the pseudo-code of Algorithm 3, the optimal approach opts to find the minimum count \(k\) of coordinators via which all IoT nodes in \(N\) are reachable in one hop by trying all possible sets of \(k\) coordinators \(\in N\) in rounds. In the first round, the algorithm tries \(k\) is 1 and checks there is a node \(n_{x}\in N\) from which all nodes \(\in N\) are directly accessible. If such a node \(n_{x}\) exists, it becomes a coordinator and the algorithm terminates with \(k\) = 1. Otherwise in the second round, \(k\) increases by one and the same procedure is repeated for nodes in each set \(\in N_{2}^{j},\ \forall j\) which includes all possible 2(=\(k\)) combinations of nodes \(\in N\) (lines 3-12). The algorithm terminates when nodes in a set \(N_{k}^{x}\) cover all nodes in \(N\) and returns \(k\) and a set of the selected coordinators, \(N_{k}^{x}\) (line 10). Clearly, this is a very exhaustive and time-consuming procedure and cannot be practically applied for a large network. Nonetheless, running such brute-force procedure for a small setup helps in qualifying the performance of the proposed algorithm relative to the optimal solution.