## 1 Introduction  
Wireless Sensor Networks (WSNs) have wide range of applications such as environmental monitoring [1], habitat monitoring [2], military applications [3], weather monitoring [4], smart grid [5], traffic monitoring [6] and forest fire detection [7] etc. In WSNs, plethora of small-sized application-specific sensor nodes are randomly deployed in the sensor field. These sensor nodes collect information and forward it towards their managing node (sink node or cluster head (CH)) via wireless communication. The nodes are resource constrained in terms of energy, computational capability, storage capacity, and communication range. The WSN nodes are battery operated and replacement of battery might not be possible due to harsh terrains and severe environmental conditions. When the nodes deplete their whole energy, the network may not operate properly and may result in performance degradation. Therefore, an efficient energy management scheme is of paramount importance to minimize the energy consumption of sensor nodes in order to prolong the lifetime of network. To minimize the energy consumption and to prolong the lifetime of nodes in WSNs, several efforts have been devoted in the literature such as MAC protocols [8], routing protocols [9], and clustering algorithms [10, 11], etc. Clustering algorithms are the most prominent mechanisms to make WSNs energy efficient. These algorithms organize a WSN in multiple clusters of various sizes as shown in Figure 1. A single node among each cluster is elected as CH and the member nodes can communicate directly with their respective CH located at the shorter distance which in turn reduces the transmission energy of node as compared to direct or multi-hop transmissions towards the sink node. Clustering algorithms can be classified based on: (1) the parameters considered for the CH election (a detailed description of CH election approaches is presented in Section 2) and (2) the nature of the execution of the clustering algorithm (e.g., centralized or distributed) [12]. Considering the nature of execution, these algorithms can be either centralized (e.g., sink node decides the CHs in the network) or distributed (e.g., the nodes execute the CH election process locally). The centralized algorithms require the complete topology information. Therefore, the efficiency of centralized algorithms may degrade in large scale WSNs, as collecting the entire network information at the sink node or base station may result in high energy consumption and brings on large delays. On the other hand, distributed algorithms are highly efficient for large scale WSNs. In distributed algorithms, each node decides its role (e.g., to declare itself as a CH or to associate with CH) based on the information of its neighboring nodes [11, 12]. Clustering in WSNs is very beneficial to prolonging the network lifetime and reducing the energy consumption of the nodes. It is shown that clustering improves the network lifetime by 2 to 3 times more than that of non-clustering schemes [13]. Without clustering, significant amount of energy is consumed in data transmission, where nodes communicate with the sink node directly which may result in excessive amount of energy consumption. However, in clustering, nodes only communicate with the CH located at a shorter distance rather than the sink node which may be located far away from the node. Therefore, an efficient organization of sensor nodes into clusters is of extreme importance for reducing overall energy consumption in the network. Most of the existing cluster-based schemes are developed for homogeneous networks [14]. These schemes only consider homogeneous nodes in the network e.g., those nodes have identical resources such as residual energy, computational capability, and storage capacity. Therefore, it is  
Figure 1: Clustering in Wireless Sensor Networks (WSNs). highly likely that each node in the network may have an equal probability of becoming CH.