## 2 Background--Related Work
### Clustering and Routing Algorithms for WSNs  
Since energy efficiency is a crucial characteristic for the network lifetime in WSNs, it is necessary to design mechanisms that are not energy consuming. Several techniques have been proposed recently for energy efficient clustering and routing in WSNs. It has been proved that by using hierarchical (tiered) architectures, the network lifetime can be extended significantly [20,21]. A hierarchy may be created by using clustering mechanisms and hierarchical routing has to be selected. Clustering has been proven to be energy-efficient since data routing and relaying are only operated by cluster heads (CHs) [22]. CHs process, filter and aggregate data sent by cluster members, thus reducing network load and bandwidth utilisation. Besides, non-CH sensors are not involved in routing and relaying data and transmissions are only operated by CHs [15]. During the clustering process, it is necessary to take into account aspects such as the cluster size and formation, criteria for CHs selection, how to control inter-cluster and intra-cluster collisions and energy saving issues [15]. For the proper design of a clustering mechanism, multiple challenges have to be addressed. Clustering has to be efficient in terms of processing complexity and message exchanges and the clustering formulation technique has to be autonomic, i.e. each node takes decisions independently of the other nodes. The clustering process has to be completed within a bounded number of iterations and, after the clusters have been formulated, each node operates either as a CH or as a simple node. Furthermore, adequate distribution of CHs over the sensor field has to be accomplished [4]. Finally, since CHs consume more energy in aggregating and routing data, it is essential to have an energy-efficient mechanism for CHs election and rotation [15]. Hierarchical routing protocols have to be correlated with the clustering formulation mechanisms in order to reduce the routing messages exchanged and, thus, decrease energy consumption [14]. These protocols are closely related to the clustering mechanism and usually support multi-hop communication, where each cluster member forwards its data to the CH and the CHs forwards the data to the gateways in the network. Since many of the proposed systems involve large networks, it is essential to provide routing infrastructures that concurrently offer small routing state and robustness [23, 24]. Limiting routing states stored in the nodes is crucial for scalability and efficiency [25] while robustness entails handling efficiently topology and connectivity changes due to node failures and environmental impact. Moreover, it is important to provide mechanisms that are able to handle heterogeneous nodes with diverse capabilities in the network [26]. Energy-efficient clustering and routing algorithms for wireless sensor networks are presented in the literature [27-29]. Cluster formation is typically based on the energy reserve of sensors and sensor's proximity to the CH [30]. Low-Energy Adaptive Clustering Hierarchy (LEACH) [15] was one of the first clustering algorithms proposed for sensor networks. LEACH is a distributed, proactive, dynamic algorithm that forms clusters of sensors based on the received signal strength and uses local CHs as routers to the sink. It includes randomized rotation of the high-energy cluster-head position, _i.e._, delegate cluster-head functionality among the various sensors in order to preserve the battery of a single sensor. LEACH clustering terminates in a constant number of iterations but it does not guarantee good CH distribution and assumes uniform energy consumption for CHs. On the contrary, HEED [31] makes no assumptions on energy consumption and achieves to select well-distributed CHs. However, it prerequisites that the nodes in the network are quasi-stationary and have equal capabilities.