# A Hybrid Unequal Clustering Based on Density with Energy Conservation in Wireless Nodes
## 3 The Proposed HCD Algorithm
### Protocol Performance
#### 3.2.1 Cluster Initialization
After collecting the relevant information for layering in the cluster, scheduling the nodes, and constructing data transmission path to the BS, the current CH sends the aforementioned information to the new CH of the next rounds and then switches to be a member node. After CH rotation, there will be one updated adjustment route. In this part, cluster formation phase and route construction phase in cluster initialization stage are done with slightly different runs. The only difference in cluster formation phase in this part is that CH gains the relevant information for layering and determines the assistance nodes to CH nodes from the previous CH with no changes in the other actions. ## 4 Analysis of HCD

**Lemma 1**. : _Control message complexity is a clustering of type O(N), and in the proposed method, in the worst case scenario, it is decreased \(r\) times._

Proof of Lemma 1.: In this protocol it is assumed that \(N\) is the number of nodes, \(r\) is the number of rounds in a major slot, \(M\) refers to the number of major slots in data transmission, and \(R\) is the number of rounds in a data transmission, which is equal to \(r\times M\). During the layering stage BS broadcasts a message in the network. Subsequently, node \(N\) transmits self_info_msg to BS and BS broadcasts cmd_msg message in the network. Therefore, \(N+2\) messages are required for this stage. In the cluster initialization stage, node \(N\) broadcasts node_msg including information on node energy and location. Then, the \(K\) times head_msg is broadcasted by CHs and \(N\)\(-k\) join_msg messages are transmitted to the CHs by CM. Consequently, \(K\) messages of TDMA_msg are broadcasted by CHs. Moreover, \(2K\) control messages are required for constructing the data transmission path to the BS. Therefore, \(N+K+(N-K)+K+2K=2N+3K\) messages are required for clustering. In total, \(3N+3K+2\) messages are required during the above-mentioned stages. Therefore, in the worst case scenario, the control message complexity is of type \(O(N)\). In hybrid performance, it is not necessary to perform clustering in each round and data transmission is performed with \(M\) major slot, which consists of \(r\) rounds. For CH rotation and route adjustment, maximum \((N-K)+K\) and \(K+2K\) messages are required, respectively. Therefore, in the data transmission stage, \([(M-1)\times((N-k)+k+k+2k)]=(M-1)\times(N+3k)\) messages are needed. **Lemma 2**. : _If there is a node within the competition radius area of another node, then the presence of two CHs is impossible._

Proof of Lemma 2.: According to Equation (7), each node has a unique delay time. If a node has a lesser delay time, it transmits head_msg with \(Rc(i)\) radius and all other nodes with this radius change their own position to CM. Therefore, if there are two nodes located within competition radius, it is not possible to have more than two CHs. **Lemma 3**. : _After performing HCD, whole network space is covered by CHs; in other words, a node (either CH or CM) will be in the same cluster._

**Proof of Lemma 3. ** If a node such as A is neither a CH nor a CM after performing HCD, node A will have two positions before executing the algorithm: (1) it does not have any neighbors and (2) has a neighbor. In the first case, according to the algorithm, node A announces to be the cluster head at the end of the delay time. In the second position, given that node A is a CH nor a CM, none of the neighbor nodes broadcast the CH message. If one of them was CH, then A will be a CM. However, if A and some of its neighbors are not CH and they do not join to a cluster, then one of them will be converted to the CH after the end of delay time. Subsequently, a message is broadcasted and neighbor nodes receiving the message will change their positions to the CMs. Therefore, node A will be either a CH or will join another CH before the end of the algorithm. Hence, it can be said that the network is completely covered by CHs. \(\square\)

**Lemma 4**.