# Service-Aware Clustering: An Energy-Efficient Model for the Internet-of-Things
## 2 The Energy-Efficient Internet-of-Things Model
### The SAC Algorithm
#### 2.4.2 Step 2: Cluster Formation  
During this step, the base station arranges the sensor nodes into an optimized number of clusters. The steps taken by the base station in organizing the network into clusters are presented below. Figure 8 summarizes the process that each node undergoes to contribute to the cluster head election.  
1. Cluster head pre-election: After receiving the broadcast information from all nodes, the base station uses the residual energy information to compute the network's average residual energy \(avgE==\frac{\sum_{v\in\mathcal{N}}\tau_{cgy}(y)}{|\mathcal{N}|}\) for all nodes \(x\in\mathcal{N}=\mathcal{N}_{c}\cup\mathcal{N}_{n}\). Knowing the network's residual energy, the base station proceeds with the pre-election of cluster heads. Two processes are used in cluster head pre-election. Energy-aware pre-selection: First, the base station compares the energy of the current node to the average network's residual energy. If the node energy is higher, then the current node energy is compared to that of the next node in the list. If it is still higher, then the current node is a candidate for the cluster head election. In agreement with Equation (6a) and the nodes's roles defined in Table 1, the combination of both of these conditions enables the SAC algorithm to increase the possibility of electing as cluster head only those nodes that have the highest energy in the network. Service-aware pre-selection: In the second stage of the pre-election, the base station uses the nodes' service (SE) to check if the selected node is an HSN. This is because, following the constraint Equation (6c) of the SAC formulation, we want to prevent HSNs from being electedas cluster heads. Here, we assume that using the nodes' SE, the base station is able to distinguish HSNs from other nodes.
2. Cluster head election: Finally, the election process is concluded by checking if the number of nodes that have met the previous requirements are less than the pre-determined number of cluster heads. If this is the case, then the base station re-examines each node in the network and selects any node whose energy is greater than the average.
3. Cluster slave association: After the base station has determined all the eligible nodes, it performs an optimization algorithm that uses the geographical location of each candidate and its current residual energy to elect only the best \(k\) cluster heads and clusters that optimize the Equation (7). \[cost = \beta f_{1}\times(1-\beta)f_{2}\] \[f_{1} = max\{\sum_{\forall n_{i}\in C_{k}}\frac{d(n_{i},CH_{k})}{|C_{k}|}\}\] (7) \[f_{2} = \frac{\sum_{i=1}^{N}E(n_{i})}{\sum_{k=1}^{K}E(CH_{k})}\] Where \(f_{1}\) represents the maximum of the mean distance between non-eligible nodes and their associated cluster heads, \(f_{2}\) the ratio of the total initial energy of all nodes over the total residual energy of the temporary elected cluster heads in the current round and \(c_{k}\) the number of nodes that belong to cluster \(C_{k}\) for \(k\in\{1,2,\ldots,K\}\). Finally, constant \(\beta\) is used to weigh the contribution of each of the functions. The two functions \(f_{1}\) and \(f_{2}\) provide the base station with the ability to evaluate the fitness level of each individual node \(n_{i}\). Node \(n_{i}\) is associated with a cluster head \(CH_{k}\) only if its distance to \(CH_{k}\) is the smallest of its distances to all other cluster heads. With this, the intra- cluster distance between cluster heads and their members and the network's energy usage are both optimized.
4. TDMA transmission schedule: After cluster formation, the base station allocates time slots to each node within a cluster using time division multiple access (TDMA) while code division multiple access (CDMA) is used to reduce collision between cluster heads.