# A Multi-Hop Clustering Mechanism for Scalable IoT Networks
## 3 Multi-Hop Clustering for IoT Networks
### The Proposed Mechanism
\begin{table}
\begin{tabular}{c c c} \hline \hline \multirow{2}{*}{**Parameters**} & **(1) Small Scale Network** & **(2) Large Scale Network to** \\  & **for the Comparison with** & **Analyze the Performance of the** \\  & **the Optimal Solution** & **Proposed Mechanism under** \\  & **Varying Parameters** \\ \hline Size of network & 25 m \(\times\) 25 m & 1000 m \(\times\) 1000 m \\ Transmission range \(TR\) & 6 m & 20, 40, 60, 80, 100 m \\ Max. hop count constraint \(H\) & 1 hop & 1, 2, 3, 4, 5 hops \\ No. of nodes & 20, 30, 40, 50, 60, 700 nodes & 200, 300, 400, 500, 600, 700, 800, \\  & & 900, 1000 nodes \\ Distribution of nodes & Uniform random & Uniform random \\ \hline \hline \end{tabular}
\begin{tabular}{l} \hline \hline \(N=\{n_{i}\mid i=1,\ 2,\ \dots\}\): set of nodes \\ \(N_{u}\): nodes that have not been assigned to a coordinator yet \\ \(C=\left\{c_{j}\mid j=1,\ 2,\ \dots,\ k\right\}\): set of coordinators \\ \(H\): Constraint on the hop count between a node and its coordinator \\ \(dist(n_{i},\ n_{j})\): distance of shortest path between \(n_{i}\) and \(n_{j}\) for \(n_{i},\ n_{j}\in N\) ([PERSON]’s SPF algorithm is assumed to be used to compute \(dist(n_{i},\ n_{j})\)) \\ \(B_{i}\) : set of reachable nodes from \(n_{i}\) within \(H=1\) \\ \(N_{k}=\{N_{k}^{l}|k=1,\ 2,\ \dots,\ |N|,\ j=1,\ 2,\ \dots,\ \left(\begin{array}{c}|N|\\ k\end{array}\right)\}\): set of all possible k-combinations of nodes \(\in N\) \\ \(\mathbf{Computing}\ C\), **the set of coordinators** \\
1: \(C=\varnothing\) \\
2: **for**\(k=1\) to \(|N|\) \\
3: **for**\(j=1\) to \(\left(\begin{array}{c}|N|\\ k\end{array}\right)\) \\
4: \(N_{u}=N\) \\
5: **for**\(n_{x},\ \forall x\in N_{k}^{j}\ //\ n_{x}\) is an element of \(j^{\text{th}}\)\(k\)-combination for \(N\) \\
6: \(N_{u}=N_{u}-B_{x}-\{n_{x}\}\ //\) removal of all reachable nodes by \(n_{x}\) in \(1\)-hop from \(N_{u}\) \\
7: **end for** \\
8: **if**\((N_{u}=\varnothing)\) **then**\(//\) if all nodes \(\in N\) are reachable from the selected nodes \(\in N_{k}^{j}\) \\
9: \(C=N_{k}^{j}\) // then the nodes in \(N_{k}^{j}\) become a coordinator. \\
10: **return**\((k,C)\) \\
11: **end if** \\
12: **end for** \\
13: **end for** \\ \hline \end{tabular}
\end{table} 
Table 1: Parameters for the two kinds of experimental settings. fewer coordinators to the entire nodes can provide the Internet connection to all IoT nodes in a given network size as the node density increases, as seen in Figure 1b, which shows a ratio of the selected coordinators to all of the nodes in the network. #### 4.2.2 Experiments with Large-Scale Networks with Varying Parameters

With the proposed mechanism, the number of selected coordinators and the average distance from a node to its corresponding coordinator are obtained for varying transmission range \(TR\), the maximum hop count constraint \(H\), and number of nodes in the network. The effects of \(TR\), \(H\), and the node density to the number of coordinators required by the optimal solution are expected to be as follows:

1. With the larger \(TR\), the degree of node connectivity becomes higher, which leads to the increase of number of nodes that can be connected to a single coordinator. As a result the number of required coordinators for a network declines. 2. For a given \(TR\) value, the larger maximum hop count constraint allows more nodes to be covered by a coordinator and also leads to a smaller number of coordinators in the network. 3. As the node density increases, the degree of connectivity among nodes becomes higher and, as a result, the ratio of selected coordinators to the entire nodes becomes lower. The results obtained from proposed mechanism well align with the above expectations on the optimal solution as shown in Figures 2 and 3. For the transmission range \(TR\) of 20, 40, 60, 80, and 100, the number of selected coordinators for increasing node density are shown in Figure 2a-e, respectively. For each of the transmission range values, a maximum hop constraint of 1 to 5 is applied.