## 4 Proposed Algorithm
### Cluster Head Selection  
In this process, the BS (N\({}^{+}\)) elects the CHs based on the distance from the centroid and the specified energy requirements, and it communicates the N\({}_{\text{i}}\) value corresponding to the selected CH to the participating nodes in the network. If the received N\({}_{\text{i}}\) value corresponds to the value of the receiving node, then the recipient recognises itself as the CH and creates and broadcasts to its member nodes for the coordination of the data transmission in the specified schedule. Otherwise, if the N\({}_{\text{i}}\) value does not correspond to the value of the receiving node, then it recognises itself as a normal member node of the cluster, sends a cluster joining request to the CH whose N\({}_{\text{i}}\) value it has received from N\({}^{+}\) and subsequently waits for the schedule to be generated by its CH. Once this process is completed, each member node in the cluster transmits the sensed data and the corresponding residual energy to the respective CH as per the received schedule. Between the subsequent transmission schedule, the sensor switches off the radios to conserve the energy. The CH compares its energy with the average energy of the cluster and communicates this information to the BS. If its energy is greater than or equal to the average energy of the cluster, then it remains the CH; otherwise, the BS elects a new CH by considering the residual energy and the distance from the centroid in the next round. New CHs are elected from the sensors within the current clusters only, and new clusters are created only when the ideal number of clusters to be formed is changed (depending on the C\({}_{\text{r}}\)). The cluster head election in FEHCA is shown in Algorithm 1 which has a worst-case time complexity of O (Cn\({}^{2}\) + Cn CN\({}^{2}\) log CN) and is discussed in Lemma 1. ``` Input: \((N,E_{i},n,C_{r})\)\(N\)\((N_{i},\)\(\forall\)\(i\in\{1,\)\(2,\dots,\)\(n\})\) alive nodes with co-ordinates \((x_{i},\)\(y_{i})\)\(E\): initial energy \((E_{1},\)\(E_{2},E_{3},\dots,E_{n})\)\(n\): number of alive nodes \(C_{r}\): Optimal cluster ratio Output: \(CH\) where \(CH\) represents cluster heads Procedure: \(FEHCA(N,\)\(E_{i},\)\(C_{r},\)\(n)\)\(C_{n}=round(n*C_{r})\)\(//\)Number of clusters in the network \(Centroid\), \(CN\gets KMEANS(N,\)\(Cn,\)\(n)\)\(//\)Calculating cluster(s) centroid, and respective participating members for \(i=1\) to all centroids in Centroid
3:\(//\)For finding the minimum distance node in a cluster
4:\(Cluster\_E_{avg}\gets 0\)\(for\)\(j=1\) to all member nodes in \(CN\)\(//\)For all nodes in a cluster
6:\(Cluster\_E_{avg}\gets Cluster\_E_{avg}+E_{j}\)\(d_{ij}\leftarrow distance\) between centroid and cluster node
8:endfor
9:\(Cluster\_E_{avg}\leftarrow\frac{Cluster\_E_{avg}}{number\ of\ node\ in\ CN}\)
10:while\(CH\_E_{res}<Cluster\_E_{avg}\)
11:do
12:\(CH\leftarrow\min(d_{i})\)\(//\)CH is elected cluster head
13:remove\(CH\) from \(d_{i}\)
14:endwhile
15:endforGenerally, the network lifetime is considered till the last cluster head is able to communicate with the base station; once the base station stops receiving the sensed data of the region, the network is assumed to be exhausted. Though this is a valid way of computing the lifetime of a network, it does not give a true picture of the sensed region. This is because, initially, the BS receives sensed values from the entire region being monitored but, as the time elapses, the CHs far away from the BS start dying earlier than the CHs near the BS (in the case of direct non-multi-hop networks) and, as the time elapses, only the CHs near the BS are able to communicate, as depicted in Figure 3, this fact is later validated in the results analysis section. Then, based on the nearby cluster readings, the BS is forced to either made decisions for the entire monitored area (which is not justified) or make decisions for only the areas from which it can communicate and preserving the rest of the area for further monitoring.