## 4 HCR-1 Protocol Description
### Cluster Head Selection in \(\mathcal{R}(1)\)  
In HCR-1, the CHs in \(\mathcal{R}(1)\) are selected with two goals:  
(1) To guarantee the network connectivity, _i.e._, to serve as the relay for the CHs in \(\mathcal{R}(2)\);  
(2) To balance the energy consumption in \(\mathcal{R}(1)\). For the network connectivity, the cluster head selection is driven by the gradient information exchange and random backoff strategy. This means that the status of a flat node has a tight relation to its backoff timer \(T_{b}\) and received messages. To balance the energy consumption, the basic idea of HCR-1 is to select a reasonable relay for the CH with low energy, such that its energy consumption can be reduced. To realize this idea, there are two problems that need to be solved: (1) how to identify a CH that requires a relay; (2) how to identify a node is able to be a relay candidate. In HCR-1, these problems are solved in the cluster head selection algorithm. Since the nodes in \(\mathcal{R}(1)\) can communicate with the sink directly, we use the average residual energy to classify the nodes. At first, the definition of average residual energy is given as follows. **Definition 4**. : _(Average residual energy) Assume that the set of nodes \(\mathcal{R}(j)\) includes node \(i=1,2,3\ldots N\), and the residual energy of node \(i\) is denoted as \(E_{r}(i)\). The average residual energy in \(\mathcal{R}(j)\) is denoted as \(E_{ave}(j)\), which is formulated by,_  
\[E_{ave}(j)=\frac{\sum\limits_{i=1}^{N}E_{r}(i)}{N},i\in\mathcal{R}(j) \tag{6}\]  
At the end of each round, every node in \(\mathcal{R}(1)\) is required to forward its residual energy \(E_{r}\) with its data packet to the sink, such that the sink can calculate the \(E_{ave}(1)\) by Equation (6). At the beginning of the next round, the sink broadcasts an ADV message with \(E_{ave}(1)\) in range \(R_{t}\), such that every node in \(\mathcal{R}(1)\) can receive it. Figure 3: The network topology of HCR-1. Once the node in \(\mathcal{R}(1)\) receives the message with \(E_{ave}(1)\), it compares its residual energy \(E_{r}\) to \(E_{ave}(1)\). If \(E_{r}>E_{ave}(1)\), it will set its NEXT flag (NEXT = 1). Otherwise, it will clear its NEXT flag (NEXT = 0). In \(\mathcal{R}(1)\), the NEXT flag is used to classify the nodes. The node with NEXT = 1 has sufficient energy to communicate with the sink directly, and it can serve as a relay for other nodes in \(\mathcal{R}(1)\). On the other hand, the node with NEXT = 0 has to select a reasonable relay to reduce its energy consumption. It is worth noting that the function of the NEXT flag in \(\mathcal{R}(1)\) is different from that in other rings. Please refer to Section 3.2.2 for the details. The NEXT flag will be exchanged among nodes during the cluster head selection. After determining its NEXT flag, the node sets up a backoff timer \(T_{b}(i)\) according to Equation (5). Then, it listens to the channel for incoming messages. the messages are only broadcast by CHs. There are two kinds of messages: ADV message for clustering (AC) and ADV message for routing (AR). Both AC and AR messages carry the information of the CH, including its ID, gradient \(k\), residual energy (\(E_{r}\)), NEXT flag and its distance to sink \(d(i,0)\). This information will be used in the following algorithms. When a node \(i\) receives an AC message from a CH \(j\), which means a proper CH is located within its clustering range \(R_{c}\), it will record the CH \(j\) in the JOIN list. However, the AR message could be sent by CHs in \(\mathcal{R}(1)\) and \(\mathcal{R}(2)\). Thus, the node that receives AR messages should deal with them in different ways. When the node \(i\) receives AR message from a CH \(j\) with \(k(j)=2\), it will check the NEXT flag in this AR message. If NEXT(j) = 0, which means the CH \(j\) in \(\mathcal{R}(2)\) has not found a forwarding relay, the node will become its relay candidate and record its information in the SERV list.