# A Multi-Hop Clustering Mechanism for Scalable IoT Networks
## 3 Multi-Hop Clustering for IoT Networks
### The Proposed Mechanism  
The proposed mechanism is comprised of two steps: (1) trying to compute the smallest set of coordinators which covers all IoT nodes in the network \(N\) within a maximum hop count constraint \(H\) by repeatedly selecting a node (coordinator) \(\in N\) which can reach the largest number of member nodes within \(H\) in a greedy manner and then (2) optimizing a total count of the selected coordinators during the first step by rearranging the mapping of member nodes to the coordinator. (1) Computing the Smallest Set \(C\) of Coordinators Using Greedy Heuristic  
The elements of coordinator set, \(C\), are determined in a greedy manner by selecting the node from which the largest number of nodes are reachable within the maximum hop count constraint \(H\). \(C\) starts with an empty set, and among the nodes that are not in \(C\) yet, the one that may reach out to the largest number of nodes that are not bound to any of the coordinators in \(C\) yet is selected as the next coordinator to be included in \(C\). Whenever a node is selected as the coordinator, all of those nodes reachable from that selected coordinator are bound to that coordinator as its member nodes so that they are no longer considered for the selection of next coordinator. This process is repeated until every node is bound to one of the coordinators in \(C\). In order to apply the processes explained above, the information about the distance among nodes is necessary. [PERSON]'s Shortest Path First (SPF) algorithm is assumed to be used to determine the distance among nodes in the IoT network. The pseudo-code of the first step of the algorithm is presented in Algorithm 1. First, set \(B_{i}\), which is the set of nodes that are reachable from node \(n_{i}\) within \(H\), is computed for every node in \(N\) (line 1-8). The coordinators are, then, selected one by one by the iteration of while loop from line 10 to 23. At each iteration of the while loop, \(crd\), which is the next coordinator to be included in the coordinator set \(C\) is determined by the for loop from line 12 to 17. That is, the node whose \(|B_{i}|\) is the largest among the nodes in \(N_{u}\) is determined as \(crd\) by the for loop from line 12 to 17. Note \(N_{u}\) is the set of nodes that have not been assigned to any coordinator yet and it is initialized with the entire set of nodes \(N\) before the while loop starts (line 10). After \(crd\), which is the next coordinator to be included in \(C\), is determined, \(crd\) as well as every node reachable from \(crd\) (i.e., \(B_{crd}\)) is removed from \(N_{u}\) as well as \(B_{i},\ \forall n_{i}\in N_{u}\). The iteration of while loop continues until \(N_{u}\) becomes empty (line 10). ```
1:\(N=\{n_{i}\ |\ i=1,\ 2,\ \ldots\}\): set of nodes
2:\(N_{u}\): nodes that have not been assigned to a coordinator yet
3:\(C=\left\{c_{j}\middle|\ j=1,\ 2,\ \ldots,\ k\right\}\): set of coordinators
4:\(H\): Constraint on the hop count between a node and its coordinator
5:\(B_{i}\) : set of reachable nodes from \(n_{i}\) within \(H\)
6:\(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})\))
7:for every \(n_{i}\in N\)
8:\(B_{i}=\varnothing\)
9:for every \(n_{j}\in N\)
10:if(\(dist(n_{i},n_{j})\leq H\)) then
11:\(B_{i}=B_{i}\cup\left\{n_{j}\right\}\)
12:endif
13:endfor
14:endfor
15:endfor
16:\(N_{u}=N_{,}C=\varnothing\)
17:while(\(N_{u}!=\varnothing\)) do
18:\(max\_{i}B_{i}=0\)
19:for every \(n_{i}\in N_{u}\)
20:if(\(|B_{i}|>max\_{i}B_{i}\)) then
21:\(crd=n_{i}\)
22:\(max\_{i}B_{i}=|B_{i}|\)
23:endif
24:endfor
25:\(C=C\cup\{crd\}\)
26:\(N_{u}=N_{u}-B_{crd}-\{crd\}\)
27:for every \(n_{i}\in N_{u}\)
28:\(B_{i}=B_{i}-B_{crd}-\{crd\}\)
29:endfor
30:endwhile
```  
**Algorithm 1** the first step of the algorithm.