## 4 HCR-1 Protocol Description
### Protocol Properties  
Based on the algorithms given above, HCR-1 has the following properties.  
**Lemma 1**: _In \(\mathcal{R}(1)\), when a node decides to be a CH, it can immediately select the sink or a CH with NEXT=1 as its next-hop node._  
The CHs in \(\mathcal{R}(1)\) can be classified by the NEXT flag. For the CH with NEXT = 1, its next-hop is destined to be the sink. For the CH with NEXT = 0, it has less residual energy than CH with NEXT = 1. According to Equation (5), the backoff timer \(T_{b}\) in the same \(\mathcal{R}(1)\) lasts longer with lower residual energy. Thus, the CHs with NEXT = 1 have to broadcast their AR messages before the CHs with NEXT = 0. The CH with NEXT = 0 has recorded all of its relay candidates in the RELAY list before its backoff timer \(T_{b}\) terminates. Therefore, if the RELAY list is not empty, it can select one proper relay based on the routing cost function as soon as it becomes a CH. However, if the RELAY list is empty, the CH with NEXT = 0 selects the sink as its next hop.  
**Lemma 2**: _In \(\mathcal{R}(1)\), when a node decides to be a CM, it can immediately select a proper CH as its next-hop node._  
According to the cluster head selection algorithm in \(\mathcal{R}(1)\), that the JOIN list is not empty is the necessary condition of becoming a CM. This means that there are CHs within its clustering range \(R_{c}\). Therefore, the node in \(\mathcal{R}(1)\) could select the proper CH in its JOIN list based on the clustering cost function as soon as it becomes a CM.  
Lemmas 1 and 2 prove that the HCR-1 protocol completes the clustering and routing simultaneously. Based on these results, the network topology of HCR-1 has the following properties.  
**Theorem 1**: _In HCR-1, the CH in \(\mathcal{R}(1)\) transmits its data to the sink in one to two hops._  
According to Lemma 1, the CH with NEXT = 1 transmits its data to the sink directly, and the CH with NEXT = 0 forwards its data to the CH with NEXT = 1. This means that the CH with NEXT = 1 transmits data to the sink in one hop, and the CH with NEXT = 0 transmits data to the sink in two hops.  
**Theorem 2**: _In HCR-1, the CM in \(\mathcal{R}(1)\) transmits its data to the sink in two to four hops._  
Since the clustering range \(R_{c}\) is constrained by \(R_{c}\geqslant R_{t}\), the CHs in the JOIN list of CM in \(\mathcal{R}(1)\) are only in \(\mathcal{R}(1)\) or \(\mathcal{R}(2)\). In the best case, the CM in \(\mathcal{R}(1)\) selects its CH in \(\mathcal{R}(1)\) with NEXT = 1. Thus, the hop count from the CM to the sink is minimized to two hops based on Theorem 1. In the worst case, the CM selects its CH \(j\) in \(\mathcal{R}(2)\), and the next-hop node of the CH \(j\) is a CH in \(\mathcal{R}(1)\) with NEXT = 0. According to Theorem 1, the maximum hop count from the CH in \(\mathcal{R}(1)\) is two, which makes the maximum hop count three from the CH in \(\mathcal{R}(2)\) to the sink. In this case, the data transmission from a CM, who selects its CH in \(\mathcal{R}(2)\), to the sink is maximized to four hops. To summarize, the CM \(\mathcal{R}(1)\) transmits its data to the sink in two to four hops.  
**Theorem 3**: _The HCR-1 protocol generates a connected network topology._  
**Proof.** According to Theorem 2 and Theorem 1, the nodes in \(\mathcal{R}(1)\) transmit data to the sink in limited hops. On the other hand, the algorithms for nodes with \(k\geqslant 2\) are the same as HCR. Combined with the analytical results given in [19], the network connectivity of \(k\geqslant 2\) is guaranteed. Therefore, the network is ensured to be connected. \(\square\)  
**Theorem 4**: _The HCR-1 protocol is completely distributed._  
**Proof.** A node changes its status and selects its next-hop node according to received ADV messages, its backoff timer \(T_{b}\) and residual energy \(E_{r}\). The ADV messages are broadcast by the CHs within its range \(R_{c}\) and \(R_{t}\). The \(T_{b}\) and \(E_{r}\) are determined by the local information. Therefore, the HCR-1 protocol is completely distributed. \(\square\)