# A Multi-Hop Clustering Mechanism for Scalable IoT Networks
## 3 Multi-Hop Clustering for IoT Networks
### The Proposed Mechanism
(2) Optimizing a Total Count of Coordinators in \(C\) by Rearranging Member Nodes  
Since the previous step tries to find the least set of the selected coordinators by partitioning the member nodes among the selected coordinators, some member nodes may be reachable to multiple coordinators within the maximum hop count constraint \(H\). Therefore, in the second step we reorganize member nodes by changing their membership based on the shortest path. Throughout the second step, we opt to reduce the total number of the chosen coordinators in the first step by switching a coordinator with no member to a member node. First, let us sequence the coordinators in the order of selection by step (1). In step (1), a node is tentatively assumed to be assigned to the first coordinator that is reachable from itself. Amongthe coordinators in \(C\), which is determined by step (1), a node may have more than one coordinator reachable within \(H\). A node needs to be reassigned to the best coordinator among the available ones in order to minimize the hop count between a node and its coordinator. Note the delay, as well as the required wireless resource can be decreased by reducing the hop count between a node and the coordinator. After this rearrangement, some of the coordinators selected by step (1) may turn out to have no member node. For each of those coordinators, it is checked whether it can be served by the other coordinator that has one or more member nodes and if so, the coordinator that has no member node is then eliminated from \(C\) to reduce \(C\) further. Among the coordinators that can provide the service to the coordinator that has no member node, the nearest one is selected as its coordinator. The pseudo-code of the second step of the algorithm is presented in Algorithm 2. \(M_{i}\), the set of member nodes served by coordinator \(c_{i}\), is first initialized to include \(c_{i}\) only (lines 1-3). Then, every node \(n_{i}\) in \(N\) is assigned to the nearest coordinator among the coordinators in \(C\) (lines 4-7). Some of the coordinators may left with no member node except for itself after the coordinator assignment is finished at line 8. Each of those coordinators is then removed from \(C\) and assigned to the nearest coordinator similar to the other non-coordinator nodes in \(N\) if there exist some other coordinators that are reachable within \(H\) and have more than one member node (lines 8-14). ```
1:\(N=\{n_{i}\mid i=1,\ 2,\ \ldots\}\): set of nodes
2:\(C=\left\{c_{j}\right|\ j=1,\ 2,\ \ldots,\ k\}\): set of coordinators
3:\(M_{i}\): set of member nodes served by \(c_{i}\)
4:\(dist(n_{i},\ n_{j})\): distance of shortest path between \(n_{i}\) and \(n_{j}\) for \(n_{i},\ n_{j}



**Proof. ** Implementing with the Fibonacci heap structure, [PERSON]'s SPF algorithm takes \(\text{O}(\left|N\right|\text{log}\left|N\right|+\left|E\right|)\) for the computation of paths from a single source to all nodes [30]. The computation of paths for all possible sources in the network, hence, takes \(\text{O}(\left|N\right|\left(\left|N\right|\text{log}\left|N\right|+\left|E \right|)\right)\), where \(\left|E\right|=\text{O}(\left|N\right|^{2})\). Especially when \(\left|E\right|=\left|N\right|^{2}\), the connectivity of given network is a full mesh, and the problem that we are solving is simplified to choosing a single coordinator that is located nearest to the center of the network. Thus the time complexity becomes \(\text{O}(\left|N\right|)\) in this case. \(\square\)

To obtain \(B_{i}\), which is the set of nodes reachable from \(n_{i}\), for \(n_{i}\in N\), within \(H\) hops, the distance between \(n_{i}\) and all the other nodes in \(N\) needs to be checked. The time to compute \(B_{i}\) for a certain \(n_{i}\in N\) is, therefore, proportional to the number of nodes \(\left|N\right|\), and in turn, the time complexity to compute \(B_{i}\) for all \(n_{i}\in N\) is \(\text{O}(\left|N\right|^{2})\).