Performance Evaluation of a Simple Cluster-Based Aggregation and Routing in Wireless Sensor Networks

Abstract

In future ubiquitous networks, sensor nodes should collect various environmental data and parameters. Because sensor nodes tend to have small and often irreplaceable batteries with limited power capacity, energy-efficient aggregation and routing are essential to achieve to a prolonged network lifetime. We propose a simple cluster-based data aggregation and routing algorithm (SCAR) that decreases the incurred overhead during the selection of cluster heads in wireless sensor networks. The performance results show that SCAR can prolong network lifetime via energy conservation and achieve energy-balancing when nodes are fixed or have limited mobility.

1. Introduction

1.1. Background

Recent advances in wireless communications and hardware techniques have made it possible to emerge the new networks called “wireless sensor networks (WSNs)” [1, 2]. The networks can be used mainly for monitoring the environments that human beings cannot access easily. However, because the networks have many limits as compared with traditional wireless networks, they cannot easily adopt the protocols used in traditional wireless networks. Particularly, due to a limited battery of each node, it is crucial for each node to consume its own energy efficiently and evenly [3].

In WSNs, a large number of sensor nodes and a sink node are deployed in spacious areas, and all of them are able to communicate with each other. Generally, every sensor node consists of processing units, diverse sensors, actuators, and an RF transceiver. Most of sensor nodes have capabilities to sense environments via sensors and to take measurements by controlling actuators. A WSN employs a sink node as a gateway device, which is used to link between its WSN and other networks such as Internet. Moreover, the sink node manages its network topologies and sensor nodes' tasks. The WSN can be used in many application areas for monitoring what is happening in certain areas and for managing services.

1.2. Motivation and Design Issues

Sensor networks complying with IEEE 802.15.4 will enable service users to access data or information whenever and wherever. In addition, routing transmission techniques using such a sensor have been sought in multilateral ways [4]. For WSNs, attribute-based addressing rather than global addressing is more appropriate [1, 2]. Since query characteristics generated in sensor works concern mostly attributes, attribute-based addressing is necessary. Thus, broadcasting or multicasting rather than point-to-point communications is more suitable. In addition, the data collected from sensor nodes are delivered to the user requesting it, by any of the various external media such as Internet or artificial satellite which are connected with nodes called sink nodes. At this time, data aggregation is required to save the wasted energy attributed to redundant transmission of similar information among adjacent nodes in the process of delivering collected data.

Examining the characteristics of sensor networks, a cluster-based hierarchical routing algorithm seems to be ideal for WSNs. Such algorithm has several merits; it ensures more energy-efficient routing in the manner of forming local clusters and transmitting the information on events incurred in an adjacent area to the gateway nodes, followed by data aggregation by means of the gateway nodes. It also prevents inefficient query flooding through delivery to the gateway nodes for the requested query. To improve energy efficiency at the network layer, inefficient routing should be reduced and instead power control for sensor nodes can be added. It is possible to improve significantly energy efficiency by controlling sensor nodes to prevent them from being involving in transmission, for example, in sleep mode, with powering off their transceivers, although this technique is applicable to some kinds of applications only. Similarly, the technique of powering off transceivers except in the case of data transmission and receipt is used at the media access control (MAC) layer as well. At the MAC layer, however, any information on networks is insufficient and if necessary, it takes some time to power on and off transceivers, leading inevitably to delayed transmission. Since it is feasible to obtain information on the networks controlling transceiver power above the network layer, the power can be controlled with separation between some nodes where it is possible to transmit data to sink nodes and the other nodes where it is impossible to do so. As mentioned earlier, as it is possible to power off nodes not involved in transmission depending on the applications, its combination with an MAC layer protocol can enable it to achieve a more significant energy-saving effect.

Network-level communication protocols for WSNs can be classified into hierarchical and flat protocols. Hierarchical approaches, such as LEACH [5], TEEN [6], AP-TEEN [7], and MTE [8], use clustered structures to aggregate and route packets. Cluster heads collect data from their cluster members, aggregate it to reduce the amount of data to be transmitted, and transmit it to the sink node, a gateway to the user. Cluster members, which make up a majority of the nodes, can conserve energy, because they communicate only with their corresponding cluster heads and their distance from the head is generally short. Long-range direct transmission to the sink node, which requires high amounts of power, is only performed by a small number of cluster heads. Although these methods may significantly improve energy efficiency and network lifetime, they have their own limitations and drawbacks in practice. For example, they assume that all nodes in the sensor field, including the sink node, can communicate directly with one another. Additionally, they assume that each node can control the power. Without the first assumption, some nodes distant from the sink node may not be able to serve as a cluster head because they cannot transmit to the sink node. Moreover, because cluster heads are selected randomly, they may all end up being on one side of the network, although the probability of this happening is very small. In this case, the nodes on the opposite side have to transmit across the entire sensor field. Thus, the physical dimensions of the sensor field are limited by the transmission range of nodes. The second assumption is the basis for the argument that short-range transmission consumes less power than long-range transmission does. Without power control, the transmission of the same amount of data consumes the same amount of energy regardless of transmission distance. However, power control requires additional signaling between transmitter and receiver. Moreover, if a node generates small amounts of data infrequently, signaling overhead for power control (delay, power consumption) may be greater than that for the user data itself. More precise control requires more signaling because nodes are greatly influenced by small changes in environmental conditions such as temperature and humidity.

The algorithm proposed in this paper has the following properties. The designs of clustering and reclustering are simple, and clustering efficiency is considered a secondary problem. Cluster head selection is performed in a greedy manner via the local exchange of node energy states. Each cluster head determines when to abandon this role and become a cluster member, depending only on its own energy state. These local interactions and local decisions regarding clustering and reclustering reduce control overhead and increase scalability at the cost of reduced optimality. The clustered structure is not for routing purposes. Routing information is managed independently from cluster structure. A cluster member transmits packets only to its cluster heads, but a cluster head can transmit packets to any nodes that can route the packets to the sink node. This routing mechanism further simplifies the clustering process because gateway nodes for inter-cluster communication can be selected independently from other clusters.

The remainder of this paper is organized as follows. Section 2 presents a brief review of related work. In Section 3, we introduce our system model with network and energy models. In Section 4, we present the detailed operations of the proposed algorithm. Section 5 illustrates the impact of energy balancing on network connectivity using simulations. Finally, Section 6 concludes the paper.

2. Related Work

Supporting the mobility of sensor nodes is one of the most important factors to enable WSNs because wireless sensor nodes can be attached to the human body, vehicles, and other mobile objects. Hence, the network layer should be implemented with an efficient routing algorithm for such nodes [7, 9–13].

2.1. Hierarchical Routing Protocols

Direct communication is the simplest and the most intuitive way to send and collect sensor data. In a direct connection, each sensor node sends data to the base station directly. It is quite simple, but it may consume a large amount of energy for nodes farther away from the base station. Based on the first-order radio model [5], energy drains more rapidly as the distance from the base station grows. To efficiently maintain the routing path between a sink node and sensor nodes, various routing algorithms have been proposed. The hierarchical routing algorithm is one of them. The typical representative algorithms are LEACH [5] and LEACH-C [14].

Heinzelman et al. [5] introduced clustering algorithm for sensor networks called low energy adaptive clustering hierarchy (LEACH). LEACH is a cluster-based protocol that includes distributed cluster formation. The authors allowed for a randomized rotation of the cluster head's role in the objective of reducing energy consumption (i.e., extending network lifetime) and to distribute the energy load evenly among the sensors in the network. Some variations of LEACH for energy saving have been reported in the literature. In [15], authors tried to improve the performance of LEACH in terms of energy-saving, by selecting cluster heads according to nodes' residual energy and distance with other cluster heads.

LEACH-centralized (LEACH-C) was proposed as an improvement of LEACH which uses a centralized clustering algorithm to create the clusters [14]. In LEACH-C, the base station collects the information on the position and energy level from all sensor nodes in the networks. Based on this information, the base station calculates the number of cluster heads and configures the network into clusters.

In contrast to LEACH, PEGASIS [16] organizes sensor nodes into a single chain. Messages are sent hop-by-hop along the chain starting with the node farthest from the base station. PEGASIS is often referred to as a chain-based protocol. The main advantage of this protocol is the low total energy dissipation, as nodes only need to communicate with their neighbors. It uses a linear programming model to generate the optimal cluster formation for extending the lifetime of a sensor network. However, PEGASIS assumes that every node has a global knowledge of the network, which is not feasible. Delays also increase as chains get longer. Spreading and collecting all sensors' information across a large network is often costly and impractical. Therefore, distributed clustering protocols are more desirable for large networks.

2.2. Other Routing Protocols

Various approaches have been recently reported in the literature. In [8], a new centralized algorithm for constructing the minimum total energy (MTE) chain was proposed. In each step of chain construction, the algorithm searches all remaining nodes and all possible insertion positions in the chain to select a node and a corresponding position in the chain that increases the total transmission cost of the chain. Then, the node is inserted into the chain at that position. MTE constructs chains with less total transmission energy cost than PEGASIS but is more computationally complex.

In [17], authors proposed the hybrid, energy-efficient, distributed (HEED) clustering protocol to prolong network lifetime and support scalable data aggregation. In this protocol, cluster heads are probabilistically selected based on their residual energy and the sensor nodes join the clusters according to their power level. HEED extends LEACH by incorporating communication range limits and cost information. In HEED, the clustering process is divided into a number of iterations. The cost can be either the node degree or the residual energy of a cluster head. Both HEED and LEACH can finish their executions within a constant number of iterations. To balance the energy consumption of all sensors, both protocols require reclustering after a period of time (called round), which causes extra energy consumption.

In [12], authors proposed hot spot-aware clustering approach based on two-tier hierarchy, in which cluster heads form the higher tier while member nodes form the low tiers. They address a hot spot problem that arises in the vicinity of the base stations. The unequal clustering mechanism that can evenly distribute energy consumption among nodes at different distances from the base station in WSNs was presented to solve the problem.

In [18], authors suggested a mixed algorithm with virtual gateway nodes, which includes both the advantages of existing hierarchical-structure algorithm and flat-structure algorithm in WSNs.

Our work is partly inspired by LEACH [5] and IGN [18]. In particular, IGN is divided into two classes: the primary class is to set a gateway-selection level and the secondary class is to offer a home automation with a routing technique, focusing on a sensor network to set a flooding level. However, the proposed scheme (SCAR) focuses on extending the lifetime of sensor networks with the integrated gateway node. Thus, it can provide an energy-efficient MAC protocol in network layer. Our scheme, together with the MAC protocol, can also be used for the enhancement of energy conservation and easily implementation.

3. System Model for Efficient Routing Protocol

3.1. WSN Clustering Environments

We use the same WSN environments as in [18]. Therefore, low-layer process with sensor nodes is also same. In most cases, it is reasonable to assume that sensor nodes have a fixed and relatively short transmission range. In this case, an energy-efficient multihop routing mechanism is essential, and cluster organization becomes more complex than in the single-hop condition. Efficient clustering algorithms for WSNs have to satisfy several requirements, such as [18] the following: (1)

clusters should cover entire sensor fields;

(2)

average cluster size should be as large as possible to maximize data aggregation efficiency;

(3)

clusters should be repeatedly reorganized to balance energy consumption among the nodes;

(4)

clustering overhead should be small;

(5)

clustering algorithms should be simple enough to be performed by low-performance processors with small available memory space.

A clustered structure organizes the sensor nodes into clusters, each governed by cluster head. The nodes in each cluster are involved in message exchanges with their respective cluster heads, and these heads send messages to a sink node, which is usually an access point connected to a wired network. Figure 1 represents a cluster architecture where message can reach the sink node in a shorter hop. Clustering can extended to greater depths hierarchically.

Figure 1

The proposed WSN clustering system model.

A clustered structure is especially useful for sensor networks because of its inherent suitability for data fusion. The data gathered by all members of the cluster can be fused at the cluster head, and only the resulting information needs to be communicated to the sink node. Sensor networks should be self-organizing; hence, the cluster formation and selection of cluster head must be an autonomous, distributed process. This is achieved through network layer protocol such as the LEACH.

A clustered structure is very useful for conserving energy in a network [5]. The benefit comes from the data aggregation of cluster heads. Aggregation efficiency increases as more data packets are aggregated. This benefit, however, is limited in multihop networks because cluster size is limited by the radio transmission range of the nodes. On the other hand, clustering overhead increases as clustering becomes more complex. The complexity stems mainly from the fact that, in multihop networks, it is difficult to recluster in a synchronized, and when one cluster is reorganized (i.e., the role of a cluster head shifts from one node to another), the physical region that the cluster head covers is also changed. This may necessitate reorganization of other clusters to satisfy requirements 1 and 2. To better satisfy these requirements, however, more signaling and processing are required. However, requirements 4 and 5 prevent increasing the overhead and complexity [18].

Requirement 3 entails clustering overhead continually. However, if the nodes are mobile, this will greatly increase the overhead. Thus, the benefit of clustering can be reduced by the clustering overhead. In single-hop networks, node mobility does not affect any network operations as long as the node does not move out of the transmission range of any other node. Several network models for hierarchical protocols for WSNs, all single-hop networks, have been proposed [5–7]; those for flat routing protocols are all multihop networks [9, 10]. Clustering complexity in multihop networks can be one explanation for this research trend in sensor networks [11, 18–20].

Figure 1 shows our proposed WSN clustering system model. We assume that a WSN consists of N sensor nodes. The goal is to identify a set of cluster heads that cover the entire WSN. We denote a sensor node set by $S = {s_{1}, s_{2}, \dots, s_{N}}$ , where $s_{i}$ represents the ith sensor $(i \in {1,2, \dots, N})$ and $| S | = N$ . Each node $s_{i}$ is then mapped to exactly one cluster $C_{j}$ , where $j \in {1,2, \dots, C}$ . C is the total number of clusters that covers all the nodes in the WSN ( $C < N$ ). Each node in the WSN is mapped to exactly one cluster and must be able to directly communicate with its cluster head. Usually, communication within the cluster takes place over one-hop distance while traffic moves through the network over multiple hops to reach the base station.

In our model, every node can act as both a sensing source and a data-gathering source (cluster head), which motivates the need for efficient algorithms to select servers according to the system goals outlined later. A node only knows about the servers that are within its reachable range, which implies that achieving global goals cannot always be guaranteed but can be approximated through intelligent local decisions (given lower-layer flooding level in [18]). Finally, a node may fail if its energy resource is depleted, which motivates the need for rotating the server role among all nodes for load balancing.

Energy conservation can be considered at the levels of individual nodes and the entire network. The energy efficiency of individual nodes is determined in various design stages including that of the circuit design, operating system, and medium access control (MAC), among others. The mechanism of energy conservation of each node has a significant impact on network lifetime. However, it is equally important to have an even distribution of energy consumption among nodes because the network may be unable to provide the required services if some nodes have used up their battery power, even if all other nodes have almost full batteries. Specifically, in multihop networks, one node failure can create one or more disconnects between other nodes and sink nodes, even if other nodes still have enough energy to operate. To prevent such situations, a network-level protocol is required to balance energy consumption among the nodes. In addition to energy consumption regulation, a network protocol should be able to achieve network-level energy conservation by reducing packet transmission via in-network data processing including data aggregation [1, 2, 18].

To improve energy efficiency at the network layer, inefficient routing should be reduced, and instead, a power control for sensor nodes can be added. It is possible to significantly improve energy efficiency by controlling sensor nodes, for example, by preventing them from being involved in transmission (e.g., entering sleep mode) and/or powering off their transceivers (for some applications). This latter technique can also be used at the MAC layer. However, it takes time to turn transceivers on and off, inevitably leading to delays in transmission. Because it is feasible to obtain information on networks controlling transceiver power above the network layer, the power can be controlled separately for nodes that can transmit data to sink nodes and those that cannot.

3.2. Network Model

Based on the network model presented in [5, 18, 21], we assume our network model to be as follows. (1)

Many sensor nodes are dispersed randomly on a region of interest.

(2)

Sink nodes are located at some convenient places in or near the sensor field. Users can obtain information from the sensor field and control it via sink nodes by direct or remote access. Thus, the sink nodes should have user interfaces or capabilities for communicating with remote users with high-powered radio or wired connections. There are very few sink nodes compared to the number of sensor nodes. Thus, they can be given special capabilities, such longer-lasting batteries or external power supplies.

(3)

The sensor nodes have limited processing and communication capabilities. Thus, it is difficult to adopt very complex and/or highly energy-consuming algorithms

(4)

All sensor nodes have the same constant transmission range. All nodes have similar capabilities (processing/communication) and equal significance. This motivates the need for extending the lifetime of every sensor

(5)

Users request data from the sensor network by disseminating query packets through the sink nodes. The data sensed from each node are gathered by sink nodes through cluster heads so that users can access the data through the sink nodes.

(6)

Clustering is completely distributed. Each node independently makes its decisions based only on local information.

(7)

Clustering terminates within a fixed number of iterations (regardless of network diameter).

(8)

Clustering should be efficient in terms of processing complexity and message exchange.

(9)

Cluster heads are well distributed over the sensor field and have relatively high average residual energy compared to regular nodes.

Based on these characteristics, attribute-based addressing rather than global addressing is more appropriate and thus broadcasting or multicasting is more suitable than point-to-point communication. Cluster-based hierarchical routing is also suitable for the energy-saving of sensor nodes.

3.3. Energy Model

The parameters used in most energy models are similar to those used in LEACH [5]. Using the radio model presented in [5], the radio of power, $E_{T_{x}} (k, d)$ , consumed by a transmitting node to send a k-bit message over distance d is

\begin{array}{l} E_{T_{x}} (k, d) = E_{T_{x} - elec} (k) + E_{T_{x} - amp} (k, d) \\ = E_{elec} \times k + ε_{amp} \times k \times d^{2} . \end{array}

(1)

To receive this message, the radio of power

(E_{R_{x}} (k))

expends

\begin{matrix} E_{R_{x}} (k) = E_{R_{x} -elec} (k) = E_{elec} \times k, \end{matrix}

(2)

where

E_{elec} = E_{T_{x} -elec} = E_{R_{x} -elec}

In this paper, we use the typical values $E_{elec} = 50 nJ/bit$ and $ε_{amp} = 100 nJ/bit/ m^{2}$ . As described previously, cluster heads are responsible for aggregating their cluster members' data.

4. Simple Cluster-Based Aggregation and Routing

In this section, a routing algorithm for WSNs is proposed to improve the efficiency of energy consumption in sensor nodes. Each sensor node has the value called “Flooding Level” obtained through the initial flooding from a sink node instead of sending beacon messages in multihop sensor field. This value can be used for guaranteeing the sensor nodes to connect with a sink node and determining the roles of cluster-head and cluster-gateway node efficiently and simply during the clustering. The proposed algorithm, simple cluster based aggregation routing algorithm (SCAR), can provide the energy efficiencies in networks layer. This SCAR algorithm can be used together with existing energy-efficient MAC protocols to increase energy conservation. SCAR is divided into two parts, self-organization and routing algorithms.

4.1. Self-Organization for Cluster-Head Selection

The self-organization procedure consists of setting the routing information, an initial clustering, and then a reclustering procedure [22, 23].

4.1.1. Setting Routing Information

Routing information is flooded from the sink nodes. The procedure for each node to set the routing information for each sink node is similar to the distance vector algorithm. In the routing information packet, the number of hops to a specific sink node and the address of the transmitting node are included. When a node receives routing information from a neighbor node, it increases the number of hops by one and uses the number as its own number of hops to the sink node. Then, it retransmits this information with its own address. When different numbers of hops are received from different neighbor nodes, the smallest number is used. If a node receives a smaller number after it has retransmitted routing information, the smaller number should again be retransmitted to correct the propagated errors. Through this procedure, each node can determine its own number of hops to a specific sink and the address of the next hop node to the sink [18].

4.1.2. Initial Clustering

The initial clustering occurs during the initial distribution of routing information. In a routing information packet, information on the energy state of the transmitting node should be included. When a node has transmitted routing information, every neighbor of the node, except those who have previously transmitted the information, will retransmit that information. In this way, each node can gather information about the energy states of every neighbor node and compare those energy states to its own. When a node has the local maximum amount of energy, it becomes a cluster head and broadcasts a cluster head advertisement (CHAD) message to its neighbors. Nodes that cannot become a cluster head wait for a CHAD message from other nodes for a predetermined period of time; a node that does not receive one repeats the exchange process of energy state information with other nonaffiliated nodes. This procedure is repeated until every node is affiliated with one cluster head. Any nonaffiliated node affiliates with the node whose CHAD message it receives first [24–27].

4.1.3. Gateway Selection

Each cluster head has one gateway node to be connected to a sink node. That is, cluster members are connected to a sink node through the cluster head at least within 3 hops. The gateway node may or may not be a cluster member of the cluster head that selects it. A cluster head sends a gateway selection (GWS) message to select its gateway node. Query dissemination from a sink node and data gathering to a sink node are performed through cluster heads and gateway nodes.

4.1.4. Reclustering

When a cluster head's energy decreases below a predefined threshold, it broadcasts a break up cluster (BUC) message to its neighbors and gives up its role as a cluster head. Cluster members that receive this message behave in one of the following two ways: (1) a node with another cluster head within one hop affiliates with that cluster head; (2) a node without a cluster head within one hop repeats the energy state information exchange process to elect a new cluster head, until no unaffiliated nodes remain. Figure 2 illustrates the reclustering procedure. Nodes “B” to “F” are formally affiliated with cluster head “A”. When node “A” gives up the role of cluster head, the cluster members of “A” search for other cluster heads. Nodes “B” and “C” find a new cluster head in their respective one-hop range and affiliate with it. The remaining nodes start exchanging their energy states. Node “D” is elected as a new cluster head, and nodes “A”, “C”, and “E” become affiliated with node “D”. In other cases, however, they can form two or more clusters depending on their energy states.

Figure 2

Reclustering procedure.

Newly organized clusters will generally have relatively small numbers because some of the former members can affiliate with other clusters, and moreover, the remaining nodes can be divided into smaller clusters. This degrades the data aggregation efficiency of the cluster, but greatly simplifies the reclustering process. To optimize cluster size for data aggregation efficiency, entire sensor fields may be reclustered. Moreover, cluster fragmentation is not permanent because small clusters will grow again when neighbor clusters are broken up.

4.2. Routing

Routing in sensor networks is different from traditional ad hoc networks and includes query dissemination and data gathering [11, 18].

4.2.1. Query Dissemination

Query dissemination is initiated from any sink node. When a sink node broadcasts a query packet, cluster heads within one hop of the sink node receive it and rebroadcast it to their member nodes. Whereas a non-gateway node just receives the query packet, a gateway node retransmits it to the cluster head that has selected it as a gateway. By repeating this procedure, all of the nodes in the sensor field can receive the query packet [18].

4.2.2. Data Gathering

Data are gathered by simply reversing the path of query dissemination. A cluster member node transmits its sensed data to its cluster head, which aggregates all received data with its own sensed data and retransmits them to its gateway. The gateway node forwards the data to its cluster head as an ordinary cluster member [18].

Once the power supply starts for data transmission, a control message that checks whether communications among neighboring sensor nodes are enabled is delivered. For the data flow in sensor networks, a query called “interest” requesting data transmission from a sink node to sensor nodes within the domain of the gateway node is transmitted to the closest gateway node. Then, the gateway node registers sensor nodes within its own domain as member nodes and delivers a specified address to each one. To transmit the data detected, the path from each node to the gateway node should be secured. Checking this requires receiving the minimal flooding signals originating from the sink node. In other words, any nodes failing to receive a flooding signal during this process would be isolated from neighboring nodes.

To check the connectivity of sensor nodes, flooding is necessary. Obviously, any energy that is consumed sending signals that are never received by any nodes is wasted. However, using this flooding process, sensor nodes can check that they are securely connected to the sink node, ensuring that their operations never waste energy and that they acquire the same network level as the sink node. Nodes that receive signals directly from the sink node set their own level to 1 and deliver the flooding message to neighboring nodes. Of the neighboring nodes that receive it, those that are not already set to a level of 1 set their own level to 2 and then again send the flooding message to neighboring nodes. This method makes it possible to check for the presence of neighboring nodes and at the same time secure connections with the sink node. Additionally, this technique can be used for cluster control. This process is shown in Figure 3.

Figure 3

The link-setup processes of the cluster head.

5. Performance Evaluation

We evaluated the performance of the SCAR protocol via simulations and compared it with that of the MTE protocol [8], an energy-efficient flat routing protocol for multihop sensor networks.

We first examined the impact of the energy-balancing procedure on network connectivity defined as the ratio of the number of nodes with single-hop or multihop connectivity to the total number of nodes. Figure 4 shows the variation in connectivity depending on node density when node positions have a uniform random distribution in a square region. Two regions were designated: 500 × 500 m² and 1000 × 1000 m². We assumed that each sensor had a radio range of 50 m or 100 m. The simulation was repeated 100,000 times for each parameter vector (node density, radio range, region area).

Figure 4

The effect of node density on network connectivity.

Figure 4 can also be interpreted as an illustration of the effect of dead nodes on connectivity. For example, when nodes with a radio range of 50 m are deployed on a 0.25 km² (500 × 500 m²) square region at a density of 200 nodes/km², the random death of 25% of the nodes (50/200) results in a disconnection (from the sink node) of roughly 55% of the nodes that are still alive. These nodes are useless, because the information sensed by these nodes cannot be delivered to the user. On the other hand, in a single-hop network, the death of one node eliminates just one node from the network. This explains why the balancing of energy consumption among nodes is especially important in multihop sensor networks.

The simulation scenario and the parameters are as follows. Initially, 100 nodes are dispersed randomly on a 500 × 500 m² region and a sink node is randomly selected from the nodes. The sink node initiates the routing information setup and initial clustering. Then, it transmits a query packet once every 100 ms and all nodes connected to the sink node respond to the query by transmitting a data packet.

Figure 5 illustrates the energy dynamics using SCAR and MTE. To illustrate the overhead of initial clustering, the initial energy is shown after initial clustering was finished. Due to the energy used for the first clustering, sensors in SCAR will start with less energy than will those in MTE. Indeed, in the simulations, SCAR initially had a lower energy than MTE for this reason. However, over time, SCAR gains energy efficiency. In MTE, the average remaining energy gradually decreases after 4 seconds. because the nodes start to die and become disconnected nodes, which no longer participate in data gathering and thus consume no more energy. Therefore, we can see from the results shown in Figure 5 that, in terms of data aggregation, the cluster structure of SCAR is superior to that of MTE.

Figure 5

Average remaining energy over time.

Next, we examined the energy efficiency of nodes in SCAR. Figure 6 shows the average remaining energy of nodes over time. The reduction in the energy of cluster heads begins to slow down after 7 seconds. due to energy-balancing. Some of the cluster heads give up their role and then become normal nodes. In this case, they consume more energy, and their energy falls below the threshold. On the other hand, the average remaining energy of normal nodes rapidly decreases from the initial stage, as some become cluster heads or gateway nodes. This local and nonperiodic reclustering is repeated continually. As a result, energy-balancing can be achieved in SCAR.

Figure 6

Average remaining energy for node role.

6. Conclusion

Our proposed algorithm, SCAR, is a simple, energy-efficient distributed clustering mechanism for multihop wireless sensor networks. It can decrease the incurred overhead during the selection of cluster heads in WSNs. Thus, the proposed algorithm enables efficient data aggregation, resulting in less data transmission and energy consumption. Performance results showed that our algorithm is much more efficient than MTE, an energy-efficient flat routing protocol, in terms of average energy consumption and network lifetime. Finally, our algorithm is appropriate for fixed and low-mobility networks. As a tradeoff for its simplicity, it can more or less lack an optimal cluster organization. Nevertheless, we showed that our algorithm operates effectively.

Footnotes

Acknowledgments

This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (2012R1A1A4A01015777).

References

Akyildiz

I. F.

Sankarasubramaniam

Cayirci

Wireless sensor net-works: a survey

Computer Networks 2002 38 4 393 422

Rentala

Musunnuri

Gandham

Saxena

Survey on sensor networks

2003 UTDCS-10-03

University of Texas

Kusdaryono

Lee

K. O.

A clustering protocol with mode selection for wireless sensor network

Journal of Information Processing Systems 2011 7 1 29 42

Khan

M. K.

Alghathbar

Cryptanalysis and security improvements of ‘two-factor user authentication in wireless sensor networks’

Sensors 2010 10 3 2450 2459

2-s2.0-77955495427

10.3390/s100302450

Heinzelman

W. R.

Chandrakasan

Balakrishnan

Energy-efficient communication protocol for wireless microsensor networks

Proceedings of the 33rd Annual Hawaii International Conference on System Siences (HICSS-33 ′00)

January 2000

1 10

2-s2.0-0033877788

Manjeshwar

Agrawal

D. P.

TEEN: a routing protocols for enhanced efficiency on wireless sensor networks

Proceedings of the 1st International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing

2001

2009 2015

Manjeshwar

Agrawal

D. P.

APTEEN: a protocol for efficient routing and comprehensive information retrieval in wireless sensor networks

Proceedings of the 2nd International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing

April 2002

195 202

Zhou

Chain-based protocols for data broadcasting and gathering in the sensor networks

Proceedings of the International Parallel and Distributed Processing Symposium

April 2003

Intanagonwiwat

Govindan

Estrin

Directed diffusion: a scalable and robust communication paradigm for sensor networks

Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MOBICOM ′00)

August 2000

56 67

2-s2.0-0034539015

10.

Kulik

Heinzelman

Balakrishnan

Negotiation-based protocols for disseminating information in wireless sensor networks

Wireless Networks 2002 8 2-3 169 185

2-s2.0-0036499227

10.1023/A:1013715909417

11.

Estrin

Govindan

Heidemann

Kumar

Next century challenges: scalable coordination in sensor networks

Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM ′99)

August 1999

12.

Joshi

M. K.

Osborne

Sun

Makki

S. K.

Hot spot aware energy efficient clustering approach for Wireless Sensor Networks

Proceedings of the IEEE Consumer Communications and Networking Conference (CCNC ′11)

January 2011

585 589

2-s2.0-79957887135

10.1109/CCNC.2011.5766548

13.

Marco

P. D.

Park

Fischione

Johansson

K. H.

TREnD: a timely, reliable, energy-efficient and dynamic wsn protocol for control applications

Proceedings of the IEEE International Conference on Communications (ICC ′10)

May 2010

1 6

2-s2.0-77955361023

10.1109/ICC.2010.5501971

14.

Heinzelman

W. B.

Chandrakasan

A. P.

Balakrishnan

An application-specific protocol architecture for wireless microsensor networks

IEEE Transactions on Wireless Communications 2002 1 4 660 670

2-s2.0-33646589837

10.1109/TWC.2002.804190

15.

Chen

Improvement of LEACH routing algorithm based on use of balanced energy in wireless sensor networks

Lecture Notes in Computer Science 2011 6838 71 76

16.

Lindsey

Raghavendra

C. S.

Pegasis: power-efficient gathering in sensor information systems

Proceedings of the IEEE Aerospace Conference

March 2002

17.

Younis

Fahmy

HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks

IEEE Transactions on Mobile Computing 2004 3 4 366 379

2-s2.0-10944266504

10.1109/TMC.2004.41

18.

Hong

S.-H.

Kim

B.-K.

An efficient data gathering routing protocol in sensor networks using the integrated gateway node

IEEE Transactions on Consumer Electronics 2010 56 2 627 632

2-s2.0-77954738592

10.1109/TCE.2010.5505980

19.

Wong

J. L.

Potkonjak

Search in sensor networks: challenges, techniques, and applications

Proceedings of the IEEE International Conference on Acoustic, Speech, and Signal Processing

May 2002

13 17

2-s2.0-0036288610

20.

Park

Cho

D.-H.

Adaptive multicluster based cooperative communication in ad-hoc network

Proceedings of the IEEE Consumer Communications and Networking Conference (CCNC ′12)

January 2012

14 17

21.

Huang

Hou

T.-W.

Chen

H.-H.

Coverage and connectivity guaranteed topology control algorithm for cluster-based wireless sensor networks

Wireless Communications and Mobile Computing 2012 12 1 23 32

22.

Sohrabi

Gao

Ailawadhi

Pottie

G. J.

Protocols for self-organization of a wireless sensor network

IEEE Personal Communications 2000 7 5 16 27

2-s2.0-0034291065

10.1109/98.878532

23.

Haas

Tabrizi

On some challenges and design choices in ad-hoc communications

Proceedings of the IEEE Military Communications Conference (MILCOM ’98)

October 1998

24.

Heidemann

Estrin

Geography-informed energy conservation for ad hoc routing

Proceedings of the 7th Annual International Conference on Mobile Computing and Networking

July 2001

70 84

2-s2.0-0034772133

25.

Cerpa

Estrin

ASCENT: adaptive self-configuring sensor networks topologies

IEEE Transactions on Mobile Computing 2004 3 3 272 285

2-s2.0-4544225837

10.1109/TMC.2004.16

26.

Chen

Jamieson

Balakrishnan

Morris

Span: an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks

Wireless Networks 2002 8 5 481 494

2-s2.0-0036739784

10.1023/A:1016542229220

27.

Aghbari

Z. A.

Kamel

Elbaroni

Energy-efficient distributed wireless sensor network scheme for cluster detection

International Journal of Parallel, Emergent and Distributed Systems 2013 28 1 1 28