## 5 The Detail of Our Protocol
### Clusters Formation  
To construct the cluster topology, four steps are performed sequentially. In addition, they are tentative CHs selection, final CHs contention, tentative clusters formation and final clusters formation. Our CH selection mechanism is similar to that adopted in LEACH. At the beginning of each round, a sensor node which has the eligibility to be a CH randomly chooses a number within range [0,1]. In  
Figure 4: Topology formation phase pseudo code in Multi-hop Energy Neutral Clustering (MENC). addition, if this number is less than a threshold, this node will serve as a CH in the current round. The threshold \(Th_{i,j}\) for any sensor node \(j\) in unit \(i\) can be expressed as follows:  
\[Th_{i,j}=\left\{ \begin{aligned} &\frac{p_{i}}{1-p_{i}\left(r \text{mod}\frac{1}{p_{i}}\right)}&\quad\text{if}\,j\in G\\ & 0&\quad\text{otherwise}\end{aligned} \right. \tag{41}\]  
where \(p_{i}\) is the desired percentage of CHs in unit \(i\); \(r\) is the current round and \(G\) is the set that consists of the sensor nodes which have eligibility to be CHs. If node \(j\) meets the following two conditions, it can be classified into set \(G\): First, it has not been a CH during the last \(1/p_{i}\) rounds; Second, its accumulated energy is more than the energy threshold \(ETh_{i}\). Since a sensor node in unit \(i\) serves as a CH once every \(n_{i}\) rounds, then \(p_{i}\) can be calculated by  
\[p_{i}=\frac{1}{n_{i}} \tag{42}\]  
For a CH in unit \(i\), its cluster radius is \(Rc_{i}\) which is calculated by Equation (8). To avoid the case that two CHs in the same unit may be within each other's cluster radius, these nodes successfully selected as CHs keep the CH state tentatively (tentative CH) and will further compete for the final CHs. Each tentative CH first broadcasts \"_tentative CH\"_ message (including node ID, unit number and CH status) within the corresponding cluster radius. In addition, then, by receiving this kind of messages broadcasted by other CHs in the same unit and storing these messages into set \(S_{t}\), each tentative CH knows its neighbor CHs within its cluster radius. If a tentative CH has no neighbor CHs, it will immediately announce itself to be a final CH by broadcasting the \"_final CH\"_ message (including node ID, unit number and CH status) within its cluster radius. In addition, then, its neighbor sensor nodes know its successful election by receiving this message and storing it into set \(S_{f}\). If a tentative CH has several neighbor CHs, it will announce itself to be a final CH in a randomly selected time slot. In addition, once hearing the announcement, its neighbor CHs will abandon the declaration to be a final CH and return to the normal state. After all final CHs are determined, each normal sensor node will choose a CH in the same unit to join cluster. If a normal node has received several \"_final CH\"_ messages, it randomly selects one CH to join tentative cluster; Otherwise, this normal node (isolate node) will be given another chance to compete for the CH. If the residual energy of an isolate node is more than the corresponding energy threshold, this node will broadcast a \"_final CH\"_ message in a randomly selected time slot. In addition, an isolate node which has received one or more \"_final CH\"_ messages before it broadcasts this kind of message, it will give up broadcasting the \"_final CH\"_ message and randomly select one message broadcaster to join tentative cluster; otherwise, it will be a final CH. For a tentative cluster in unit \(i\), it becomes the final cluster automatically if there are no more than \(n_{i}\) sensor nodes in it. However, if this cluster contains more than \(n_{i}\) sensor nodes, the corresponding CH may have no enough energy to burden the intra-cluster data traffic. To avoid this problem, such a tentative cluster should be divided into several final clusters with no more than \(n_{i}\) sensor nodes in each of them.