EEMC: An energy-efficient multi-level clustering algorithm for large-scale wireless sensor networks

Abstract

Wireless sensor networks can be used to collect environmental data from the interested area using multi-hop communication. As sensor networks have limited and non-rechargeable energy resources, energy efficiency is a very important issue in designing the topology, which affects the lifetime of sensor networks greatly. In this paper, the energy consumption is modeled and compared under the flat scheme and the clustering scheme, respectively. Motivated by the analysis, we propose an energy-efficient multi-level clustering algorithm called EEMC, which is designed to achieve minimum energy consumption in sensor networks. The cluster head election scheme is also considered in EEMC. EEMC terminates in O(log log N) iterations given N nodes. When the path loss exponent is 2, EEMC also achieves minimum latency. We focus on the case where sink node is remotely located and sensor nodes are stationary. Simulation results demonstrate that our proposed algorithm is effective in prolonging the network lifetime of a large-scale network, as well as low latency and moderate overhead across the network.

Introduction

With the development of very-large-scale integration (VLSI), micro-electro-mechanism system (MEMS) and wireless networking technology, wireless sensor networks (WSNs) have attracted more attention lately. A wireless sensor network is composed of numerous tiny devices. These devices have processing and communication capacities, which enable to collect surrounding information and then transmit report messages to a remote sink node (base station). The sink node aggregates and analyzes the report messages received and decides whether there is an unusual or exceptional event occurrence in the deployed region [1]. There are many practical applications of wireless sensor networks. Some of the most promising application areas are environmental monitoring, battlefield tracking and disaster recovery operation, building control systems, and smart entertainment devices that adjust audio and video signals based on their surroundings [2].

Sensor nodes are often deployed randomly in harsh, inaccessible terrains or in a hostile zone. For example, sensor nodes could be simply dropped in place from an airplane without any predetermined positions. Thus the position of sensor nodes need not be engineered or predetermined by human beings. On the other hand, it also requires that the sensor network protocols and algorithms possess self-organizing capabilities [3].

Because of the compact form factors of sensor nodes, wireless sensor nodes are severely energy constrained, which restricts sensor networks from being used for broader applications. Furthermore, it is impractical to replace the batteries on thousands of nodes in a potentially harsh environment. It is widely accepted that a key challenge in unlocking the potential of wireless sensor networks is maximizing their post-deployment active lifetime. Hence, energy efficiency is an important design consideration for all wireless sensor networks. There are various issues in designing low-power wireless sensor networks, such as design of dynamic voltage scaling, low-power radio communication hardware, low duty cycle, energy-aware MAC (layer) protocols [4], [5], and energy-efficient (network layer) routing protocols [6]. In the MAC protocol, power consumption can be reduced by decreasing the wake-up time of a transmitter or by employing a smart scheduling of slots to avoid signal collision and data retransmission. Compared with the MAC protocol, the routing protocol is more flexible because it generally does not need a special support of low-power hardware and thus can be easily adapted to different environments. Therefore, designing energy-efficient routing protocols and algorithms at the network layer has been the area of most extensive research in recent years.

SPIN (Sensor Protocols for Information via Negotiation), a flat (routing) algorithm for sensor networks, has been proposed by Heinzelman et al. [7]. It considers data negotiation between nodes in order to eliminate redundant data and thus save energy. After that, a breakthrough was made in data-centric routing by directed diffusion [8], which is different from address-centric routing protocols such as mobile ad hoc networks (MANETs). By utilizing low-power GPS, Rodoplu and Meng [9] proposed a distributed algorithm called MECN (Minimum Energy Communication Network) to set-up and maintain a minimum energy network for wireless networks. These flat schemes typically work well if the density of the network is low or the quantity of delivered data is small. Unfortunately, flat scheme will cause the gateway to overload as the node density increases. Such overload might lead to latency in communication and inadequate tracking capability of events.

In regard to energy savings vs. lifetime of network, Bhardwaj et al. studied a multi-hop sensor network and provided an upper bound network lifetime in a linear case and a two-dimensional case for the flat topology, which results in easy-to-use, closed-form expressions for the lifetime bounds [10]. However, the authors only focus on one pair of source–destination at a time without taking the many-to-one cases into an account.

To make the network more scalable, a lot of research efforts in cluster networking have been pursued recently. In MANET, many clustering algorithms elect cluster heads (CHs) based on node identity [11], [12], [13], connectivity degree [14], or connected dominating set [15]. The complexity of this clustering approach is O(N) where N is the number of nodes. Comparably, the algorithm of [16] generates d-hop cluster with O(d) rounds. Actually, most clustering approaches in MANET do not consider the energy issue. The main advantage of sensor network’s clustering algorithm is the ability to balance and reduce energy consumption of sensor nodes by associating them with a particular cluster and by performing data aggregation to decrease the number of packets transmitted to the sink node. For instance, it has been concluded that for a habitat monitoring application where data is continuously transmitted to the sink node, the clustering scheme is the most efficient choice [17].

According to LEACH (Low Energy Adaptive Clustering Hierarchy) [17], a distributed clustering algorithm, the sensor nodes elect themselves as CHs with some probability and broadcast their decisions. The remaining nodes join a cluster, of which the cluster head (CH) is closest in terms of the communication energy cost. Then the role of CH is periodically rotated among the nodes to balance energy dissipation, since CHs have the extra burden of performing the long-range transmission to a distant sink node. Thus, LEACH counteracts the problem of non-uniform energy drainage by role rotation. Since then, there have been many energy-efficient routing protocols derived from LEACH, such as PEGASIS [18], TEEN [19] and APTEEN [20]. They all try to preserve and balance the energy dissipation of the network using clustering architecture, thus prolonging the network lifetime. Although PEGASIS avoids the clustering overhead of LEACH, it still requires dynamic topology adjustment since the energy of each node is not tracked. TEEN and APTEEN are designed to satisfy critical data collection by adding a threshold function, which is not fit for a periodic information collection application. The main drawbacks of these two approaches are the overhead and complexity of implementing threshold-based functions and dealing with attribute-based naming of queries. To summarize, LEACH is relatively simple and typically the more effective clustering algorithm.

Although LEACH resolves the energy-balancing problem by rotation, it ignores the energy consumption issue of intra-clusters. As a result, the formation and structure of clusters maybe not be optimal. Based on LEACH, [21], [22] provide more effective clustering approaches to prolong the network lifetime. Younis and Fahmy presented an approach called HEED that periodically selects CHs based on the node’s residual energy and a secondary parameter, such as node proximity to its neighbors or node degree [21]. However, the convergence time for running HEED maybe related to the initial probability C_prob, which is chosen randomly by HEED.

Bandyopadhyay and Coyle proposed a distributed clustering algorithm where the communication between the node and its CH is organized in a multi-hop manner [22]. Using the results of stochastic geometry, the authors formulate a network energy dissipation function and derive the probability p of becoming a CH that minimizes the energy dissipation. The value of k, the maximal number of hops from a node to its CH, is also calculated. Furthermore, [22] extends the single-level to the multi-level hierarchical network. Under this topology, the solution space is not convex and the value of p on different levels is related to each other in a very complex fashion, hence the value of p for any level can be obtained by the numerical optimization. Besides, the authors show that the energy savings increase with the number of levels. On the other hand, if each node chooses the closest CH as its default CH, the nodes essentially form a Voronoi tessellation of the network region, where each cluster corresponds to a Voronoi cell [22], [23], [24]. For large-scale sensor networks, a typical cluster can be approximated as a circle with the CH at the center [25], [26]. This approach can simplify the theoretical analysis of this paper. Simulation results of this paper demonstrate that this approximation is reasonable. Instead of selecting the optimal probability when the sink node is located in the center of the network and the non-CH node is far away from its CH by at most k-hop [22], we consider the scenario where the sink node lies far away from the network and the node can transmit its data packet to the sink node directly by power control [17]. In [22], the authors have pointed out sensor nodes can run the clustering algorithm periodically for energy balancing, while the detailed approach about CH rotation and CH election has been less investigated in multi-level clustering scheme. Moreover, they assume that each node uses 1 unit of energy to transmit or receive 1 unit data. In fact, their results could be better convinced if they had considered the practical energy model.

In the clustering scheme, another important issue that should be considered is the latency, which is defined as the time that the sink node requires to collect all sensor node data once via CHs [26]. Based on the hierarchy of [22], Bandyopadhyay et al. further analyzed the tradeoffs among node density, energy usage, throughput, latency, temporal sampling rates and spatial sampling rates in a cluster [26]. They show the lower bound on the latency incurred in collecting data is O(k²N) in a clustering network, where N is the number of sensor nodes and k is the maximal number of hops from a node to its CH. Similar to [26], the latency issue is also discussed in this paper. It should be noted that our analysis pertains only to the periodic data collection networks, not to the event detection networks where the nodes start a data collection activity only when an event of interest occurs.

Motivated by the literatures [21], [22], the main contribution of this paper is threefold:

• Modeling and comparison of the energy consumption of the flat scheme, single-level clustering scheme and multi-level clustering scheme, respectively.

• Calculation of the optimal expected number of CHs to achieve minimum energy consumption and minimum latency in a multi-level clustering scheme, and the optimal number of levels asymptotically. Comparatively, the latter is the major difference between ours and others [17], [21], [22].

• Proposition of an energy-efficient multi-level clustering (EEMC) algorithm and comparison of this algorithm with other clustering algorithms by the simulations.

An initial version of above results can be found in [27].

The rest of the paper is organized as follows. Section 2 presents the assumptions and the energy model. Section 3 provides the analysis on the energy consumption of flat scheme, single-level clustering scheme, two-level clustering scheme, as well as the probability of becoming a CH in the networks. In Section 4, the latency issue in different schemes is analyzed and compared. Section 5 introduces EEMC algorithm. In Section 6, by comparing with existing clustering algorithms, the simulation results show EEMC achieves longer network lifetime and less latency than others. The conclusions and the future research directions are listed in the last section.