## 4 Balanced Energy-Efficient Clustering (BEE) and Multihop BEE (BEEM)
### Improved Iteration CH Election  
In HEED, the initial probability that a sensor elects itself to be a CH is  
\[CH_{prob}=C_{prob}\times\frac{E_{residual}}{E_{max}} \tag{1}\]  
\(C_{prob}\) is the initial CH probability (Both LEACH and HEED set it to be 5%). \(E_{max}\) is the initial energy for all the sensors. \(E_{residual}\) is the remaining energy on the current sensor. If a sensor is not covered by any CHs, it will elect itself as a _tentative_ CH when a random generated number is smaller than the value of \(CH_{prob}\). After each iteration, \(CH_{prob}\) is increased twice (maximal value is 1). Once \(CH_{prob}\) reaches 1, a _tentative_ sensor will declare itself as a \(final\) CH. If a sensor is not covered by any \(final\) CH, it will declare itself as a \(final\) CH when its \(CH_{prob}=1\). A sensor will terminate the iteration process when its \(CH_{prob}=1\). To void really small value for \(CH_{prob}\), it is set to the bigger value between \(C_{prob}\times\frac{E_{residual}}{E_{max}}\) and \(P_{min}=10^{-4}\). Otherwise the number of iterations can be unnecessarily large. Since \(C_{prob}\) starts from 5%, a high energy sensor still needs at least 6 iterations to have a chance to declare itself as a \(final\) CH (\(0.05\times 2^{N_{iter}-1}\) can be bigger than 1 only when \(N_{iter}\geq 6\) where \(N_{iter}\) presents the number of iterations required). As \(E_{residual}\) of a sensor decreases, it needs more iterations to terminate the CH election process. To address the first issue highlighted in Section 3, two improvements are made in the CH election process in BEE. 1. _Number of iterations:_ The number of iterations to terminate the CH election process has a significant impact on the network latency and congestion. Therefore, reducing the number can reduce the overhead of the iteration CH election process. 2. _Node density:_ Sensors in a high-density area are allowed to die sooner than the sensors in a low-density area for the purpose of maintaining the coverage of the network. In BEE, we believe that if a sensor's node degree is high, it is reasonable to assume that the node density around this sensor is high. The node degree of a sensor is referred as the number of sensors in its communication range. Based on HEED, in BEE, considering local density, \(CH_{prob}\) should be calculated as:  
\[CH_{prob}=C_{prob}\times\frac{E_{residual}}{E_{max}}\times\min\left(\frac{Node \, Degree}{D_{avg}},1\right) \tag{2}\]  
where \(D_{avg}\) is the average density of the network and it is calculated as:  
\[D_{avg}=\pi R^{2}\times\frac{Num_{sensors}}{Area} \tag{3}\]  
\(R\) is the default communication range of the sensors (normally it is set to the cluster radius), \(Num_{sensors}\) is the total number of sensors in the network and \(Area\) refers the area of the sensing field. \(D_{avg}\) is also the value for average node degree. To reduce the number of iterations, we separate the factors in Formula (2) into three parts: \(C_{prob}\), \(C_{en}=\frac{E_{residual}}{E_{max}}\) and \(C_{de}=\min\left(\frac{Node\, Degree}{D_{avg}},1\right)\). Three conditions that are used to determine whether a sensor can elect itself as a \(final\) or \(tentative\) CH are:  
1. C1= \(\left\langle Random\left(0,1\right)\leq C_{prob}\right\rangle\)
2. C2 = \(\left\langle\frac{E_{residual}}{E_{max}}\geq 1\right\rangle\)
3. C3 = \(\left\langle\frac{Node\, Degree}{D_{avg}}\geq 1\right\rangle\)  
As in HEED, \(C_{prob}\) is set to be the optimal CH ratio--5%. After each iteration, the value of \(C_{en}\) and \(C_{de}\) are both doubled. A sensor will terminate its own CH election thread when either \(C_{en}\) or \(C_{de}\) reaches 1. By separating the factors, we aim to decrease the number of iterations CH election process to construct the CH set. The status of the CH depends on which conditions are true as shown in Table 3. If two of the three conditions are true, the sensor will elect itself to be a \(final\) CH.