# A Multi-Hop Clustering Mechanism for Scalable IoT Networks
## 3 Multi-Hop Clustering for IoT Networks
### The Proposed Mechanism
Since it is an NP-hard problem, we proposed a heuristic mechanism which has the time complexity of \(\text{O}(\left|N\right|^{2}\log\!\left|N\right|+\left|N\right|\!\left|E\right|)\), where \(\left|N\right|\) and \(\left|E\right|\) are the number of nodes and the number of wireless links in the IoT network, respectively. The proposed mechanism is applied to a set of networks with varying transmission range and number of nodes with different maximum hop count constraint. The results show that the performance characteristics of proposed mechanism well align with the expected performance characteristics of the optimal solution. That is, the number of selected coordinators reduces as the transmission range and the maximum hop count constraint increase and the ratio of selected coordinators to the entire nodes becomes lower as the node density increases. Our future work includes reducing the complexity of the proposed heuristic algorithm which mainly depends on the complexity of [PERSON]'s SPF algorithm used to compute a set of paths between every IoT node and the remaining IoT nodes. This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2015R1D1A1A01057095). [PERSON] developed the proposed approach and simulated the experiments; [PERSON] defined the problem statement and analyzed the complexity of the proposed algorithm; [PERSON] developed the proposed approach and wrote the manuscript in collaboration with [PERSON]. The authors declare no conflict of interest. ## References

* [PERSON] et al. (2010) [PERSON]; [PERSON]; [PERSON] The Internet of Things: A Survey. _Comput. Netw._**2010**, 54, 2787-2805. [CrossRef]
* [PERSON] et al. (2014) [PERSON]; [PERSON]; [PERSON]; [PERSON] [PERSON] An Architecture to Support the Collection of Big Data in the Internet of Things. In Proceedings of the 2014 IEEE World Congress on Services (SERVICES), Anchorage, AK, USA, 27 June-2 July 2014. * [PERSON] et al. (2015) [PERSON]; [PERSON]; [PERSON] Device clustering for fault monitoring in Internet of Things systems. In Proceedings of the IEEE 2 nd World Forum on Internet of Things (WF-IoT), Milan, Italy, 14-16 December 2015. * [PERSON] et al. (2017) [PERSON]; [PERSON]; [PERSON]. A Survey of Clustering Techniques in WSNs and Consideration of the Challenges of Applying Such to 5G IoT Scenarios. _IEEE Internet Things J._**2017**, 4, 1229-1249. [CrossRef]
* [PERSON] et al. (2017) [PERSON]; [PERSON]; [PERSON] A Smart and Balanced Energy-Efficient Multihop Clustering Algorithm (Smart-BEEM) for MIMO IoT Systems in Future Networks. _Sensors_**2017**, 17, 1574. [CrossRef] [PubMed]
* [PERSON] and [PERSON] (2012) [PERSON]; [PERSON] _Combinatorial Optimization: Theory and Algorithms_, 5 th ed. ; Springer: Berlin, Germany, 2012; p. 414, ISBN 978-3-642-24488-9. * Cisco (2018) Cisco. Available online: [[http://www.cisco.com/c/dam/en_us/solutions/industries/docs/scc/digital-cities-value-at-stake.pdf](http://www.cisco.com/c/dam/en_us/solutions/industries/docs/scc/digital-cities-value-at-stake.pdf)]([http://www.cisco.com/c/dam/en_us/solutions/industries/docs/scc/digital-cities-value-at-stake.pdf](http://www.cisco.com/c/dam/en_us/solutions/industries/docs/scc/digital-cities-value-at-stake.pdf)) (accessed on 20 March 2018). * _[PERSON] et al. (2010)_ [PERSON]; [PERSON]; [PERSON]. Low latency and energy efficient routing protocols for wireless sensor network. In Proceedings of the International Conference on Wireless Communication and Sensor Computing (ICW CSC 2010), Chennai, India, 2-4 January 2010. * _[PERSON] et al. (2013)_ [PERSON]; [PERSON]; [PERSON] An effective routing protocol for energy harvesting wireless sensor networks. In Proceedings of the 2013 IEEE Wireless Communications and Networking Conference (WCNC), Shanghai, China, 7-10 April 2013. * _[PERSON] et al. (2008)_ [PERSON]; [PERSON] A Hybrid Routing Protocol for Wireless Sensor Networks Based on a Two-Level Clustering Hierarchy with Enhanced Energy Efficiency.