An Energy-Efficient Multilevel Clustering Algorithm for Heterogeneous Wireless Sensor Networks

Introduction

In recent years, with the advances in the technology of micro-electromechanical system (MEMS) and developments in wireless communications, wireless sensor networks (WSNs) have gained worldwide attention. WSNs consist of small nodes (sensors) having capabilities like sensing, computation, and communications. These sensors gather data by sensing the surroundings, aggregate this data to form useful information and transmit it to the base station or the neighboring node. WSNs have great potential for many application scenarios such as military sensing (Shen et al., 2010), industrial process monitoring and control (Kay et al., 2004), machine health monitoring (Hadim et al., 2006), environment and habitat monitoring (Hart et al., 2006), healthcare applications (Yan et al., 2009), home automation and traffic control (Chinrungrueng et al., 2006).

With the advances in MEMS, VLSI technology and wireless communication technology, it has become possible to form a large scale WSN with small sensor nodes scattered across some environment. These sensor nodes need to be in touch with far-away base stations. Clustering is an important technique to prolong the lifetime of WSNs and to reduce energy consumption as well, by topology management and routing. Many energy-efficient routing protocols are designed based on the clustering structure (Krishna et al., 1997; McDonald et al., 2001). The clustering technique can also be used to perform data aggregation (Mhatre et al., 2004; Heinzelman et al., 2000). Data aggregation combines the data from source nodes into a small set of meaningful information hence the fewer messages are transmitted thus securing communication energy. Within the clusters, localized algorithms can also efficiently operate. Clustering technique can be extremely effective in broadcast and data query (Ni et al., 1999; Estrin et al., 1999). Cluster-heads help to broadcast messages and collect interested data within their own clusters.

Sensor nodes in WSNs are limited in power, memory and computational capacity. So they may be short lived. A smart way to prolong the lifetime of sensor nodes and WSN is to make efficient use of energy. Many energy efficient algorithms have been proposed in the literature (Abbasi et al., 2007). LEACH (Heinzelman et al., 2000) is one of such algorithms that balances the energy consumption by rotating the clusterhead (CH) role to every node in the cluster. Another way to prolong the lifetime of WSN is to insert a percentage of sensor nodes equipped with additional energy resources i.e. making the WSN heterogeneous in terms of energy. Even though the nodes may have same initial energy in starting, energy of each node will not be same later on due to radio communication characteristics. Therefore, WSNs are more possibly heterogeneous networks rather than homogeneous ones. Many existing schemes for heterogeneous wireless sensor networks (HWSNs) like SEP (Smaragdakis et al., 2004), EEHC (Kumar et al., 2009), DEEC (Qing et al., 2006), etc., demonstrate that HWSNs survive for a longer time as compared to homogeneous WSNs.

Sometimes, direct communication may not be possible with the base station due to certain limitations. This leads to the need of multilevel clustering algorithms for large WSNs. In such algorithms, clusters are formed in hierarchical manner. Sensor nodes sense the events and forward the data to the immediate CH. This CH aggregates and forwards data to the next level CH and so on to the sink node. So the advantage of multilevel clustering algorithms is that the nodes have to transmit data comparatively to short distances so they can conserve their energy. Many energy efficient multilevel clustering algorithms have been proposed till date like (Jin et al., 2008; Rasid et al., 2007; Xinfang et al., 2008). An Energy Efficient Multilevel Clustering Algorithm (EEMC) to minimize the energy consumption in WSNs is proposed in (Jin et al., 2008). EEMC also covers the CH election scheme. The scheme assumes that the sensor network is homogeneous and does not perform well in heterogeneous environment. The low energy nodes will die more quickly than the high energy nodes because the algorithm does not discriminate each node in terms of energy.