# A Multi-Hop Clustering Mechanism for Scalable IoT Networks
## 2 Related Works  
In sensor network clustering, sensors are grouped into clusters and the representative sensor of a cluster, commonly called as the \"cluster head (CH)\", gathers and transmits the sensing data of the other sensors in the cluster to the base station (BS) which connects the sensor network to the outside networks. Typically, the energy consumption of sensors is minimized by having them only communicate with either the nearest neighboring sensor or its CH, which is within one hop distance. The energy consumption of CHs is relatively higher than the other sensors since they have to communicate with the BS which is farther away. Eventually the sensors take turns to undertake the role of CH to balance the energy consumption level among themselves and prolong the lifetime of sensor network. The clustering mechanisms of sensor networks can be largely classified into the Voronoi-based and the non-Vornoi-based ones [4]. The Voronoi-based mechanisms first select a set of CHs and then have each sensor connected to the nearest CH so that the sensors may communicate with their CH with the minimum energy consumption [8; 9; 10; 11; 12; 13; 14; 15]. In the Energy Potential Low-Energy Adaptive Clustering Hierarchy (EP-LEACH) algorithm [9], the CHs are selected among sensors based on the sensor node's energy harvesting capability. If the energy level of a selected CH falls behind a certain threshold, CH replacement occurs to extend the lifetime of network. The clusters are formed by having each sensor assigned to the closest one-hop away CH and thereby, the energy consumption of sensors is minimized. The Voronoi-based mechanisms are, therefore, not applicable for the objective of configuring clusters as large as possible to minimize the number of Internet connections. The non-Voronoi-based approach is further classified into the chain-based and the spectrum-based mechanisms [4]. Differing from the Voronoi-based mechanisms, chain-based mechanisms form multi-hop clusters, i.e., the sensors are one or more hops away from their CH. In the chain-based mechanisms, the entire network is formed into chain(s) of sensors having a CH for each chain and the data is transmitted in one direction only following through the chain to be delivered to the CH [16; 17; 18; 19; 20; 21; 22; 23; 24; 25]. The chain is configured so that, for each sensor, the next sensor on the chain is the nearest sensor among the neighboring sensors that are nearer to the BS than itself. Eventually, the sensor(s) that receive data from more than one direction become the CH(s) and the rest of the sensors transmit/receive data to/from a fixed direction only following the chain. The enhanced Power-Efficient GAthering in Sensor Information Systems (Big Sky, MT, USA) (E-PEGASIS) [16] is the chain-based mechanism which opts to reduce the data redundancy to BS. E-PEGASIS finds a dominating set (DS) that includes a subset of deployed nodes to be activated and then the near optimal chain is formed out of DS nodes by using an ant colony optimization. Finally, a chain leader is selected based on residual energy and proximity to BS and then the overhead to BS can be reduced. Meanwhile, the Concentric Clustering Scheme (CCS) [17] proposes a mechanism to configure the network into multiple chains. In CCS, a sensor network is divided into multiple clusters based on the distance from the BS and a chain is formed within each cluster. In the chain-based mechanisms, the energy consumption of sensors can be minimized since a sensor transmits data to the nearest neighboring sensor. The chain-based mechanisms may form long chains and thereby enable to configure large clusters to minimize the number of necessary Internet connections. However, unnecessary detouring in the data delivery paths as well as the extensive delay from sensors to the CH may occur and, thus, it is not applicable to the clustering of IoT networks that have a delay constraint.