Energy-Efficient Self-Organized Clustering with Splitting and Merging for Wireless Sensor Networks

Abstract

Energy efficiency is one of the most important issues for WSNs, because the battery of each wireless sensor node cannot be recharged or replaced. Therefore, all batteries have to be well managed, in order to provide a long network lifetime, as well as to reduce energy consumption for WSNs, particularly in clustering and routing. In this paper, we propose an energy-efficient self-organized clustering model with splitting and merging (EECSM), which performs clustering and then splits and merges clusters for energy-efficient cluster-based routing. EECSM uses information of the energy state of sensor nodes, in order to reduce energy consumption and maintain load balance. We show the validity of splitting and merging of clusters and then compare the performance of the proposed EECSM with that of a well-known cluster-based self-organization routing protocol for WSNs. The results of our experiment show good performance of EECSM, in terms of network lifetime, residual energies, scalability, and robustness.

1. Introduction

A sensor node of a wireless sensor network (WSN) senses the environment, and the information obtained from the environment is converted into data packets and then transmitted to the base station (BS), which is the external final processing node for users [1]. According to the advancement in wireless sensor devices, WSNs have performed important roles in recent years, such as environmental monitoring and target tracking.

WSNs have many unique characteristics, as well as the following constraints. First, a WSN consists of hundreds or thousands of wireless sensor nodes. Therefore, each wireless sensor node should consist of several cheap devices, which are constrained in terms of the processing capability and storage capacity. Second, the battery of each wireless sensor node cannot be recharged or replaced, and thus all batteries have to be well managed, in order to provide long network lifetime and reduce energy consumption for WSNs [1, 2].

For the energy-efficient transmission of information obtained by sensor nodes, many routing protocols have been developed. The routing protocol decides the transmission route for a data packet, from the sensor node to the external final destination BS. In general, routing protocols in WSNs can be divided into flat routing, cluster-based routing, and location-based routing, depending on the network structure. Sensor nodes of flat routing typically have identical roles, whereas sensor nodes of cluster-based routing have different roles, in order to create hierarchy. Meanwhile, location-based routing uses the location of sensor nodes for routing. Among these routing protocols, cluster-based routing protocol is the most energy efficient [3]; therefore, we study cluster-based routing in this paper.

In cluster-based routing, a network consists of several clusters, and each cluster is comprised of a cluster head (CH) and many cluster members (CMs). Due to the limitation of a wireless sensor node, a centralized clustering and routing method is almost impossible in WSNs.

Considering these limitations, a distributed clustering and routing method is normally used for WSNs. In distributed clustering and routing, each sensor node can reduce energy consumption, by clustering when transmitting the data packets.

Self-organization, which is a further development of distributed processing, has recently been studied intensively. Although wireless sensor nodes have limited capacities, the self-organization method can perform adequate clustering and routing, by using only localized neighbor information and simple rules. Self-organization processing also has advantages, such as scalability and robustness.

Although the size of clusters should be adjusted properly, in order to maximize energy efficiency, the usual cluster-based routing protocols do not guarantee proper clustering size, since they only use localized neighbor information. Since the CMs send data packets to a distant CH when the size of a cluster is too large, high energy consumption can occur. In addition, the CH may experience transmission delays and cause bottlenecks. In contrast, when the size of clusters is too small, the number of clusters is increased, engendering an increase in the number of CHs, which consume much more energy when compared with CMs.

In this paper, we propose an energy-efficient self-organized clustering with splitting and merging (EECSM) model for WSN. In order to increase energy efficiency, EECSM performs clustering, by considering the energy state information and also by deciding on the split or merge clusters. This action is performed by monitoring the size of the clusters in self-organized ways.

This paper is organized as follows. Section 2 reviews the previous studies on cluster-based and self-organized routing and on the protocols that use splitting and merging clusters. Section 3 presents the radio model and the definitions used in this study. Section 4 explains the process of the EECSM model. Section 5 proves the validity of splitting and merging and compares the performance of the proposed EECSM with that of another well-known clustering model. The last section presents the conclusions of this study and proposes future research directions.

2. Related Works

According to the energy state or the location of sensor nodes, sensor nodes have different roles: CH, CM, gateway, and so on. The data transmission of cluster-based routing is performed in accordance with the following procedures. (i) The CMs transmit the data packet, created by the sensing environment, to their CHs. (ii) The CHs aggregate the data packets received from their CMs and transmit them to the BS, either directly or via other CHs [3].

Cluster-based routing protocols have advantages of energy efficiency and scalability, and clustering can localize the transmission of signals that is used to maintain the routing paths and clusters. In addition, localized transmission avoids the redundant exchange of messages among sensor nodes. According to the decrease in the transmission range, clustering can reduce the transmission energy of the data packets [3–6]. A single-tier network (flat routing protocol) can cause sensor nodes to overload with an increase in the number of sensor nodes; it does not offer scalability. Cluster-based routing protocols have more than two tiers; thus, they can prevent an increase of overload. Therefore, cluster-based routing is the most proper method to cover a large area without any service degradation [4].

Recently, research on “Self-organization” has advanced in many fields, such as forming clusters and routing packets in WSNs or ad hoc networks [7, 8]. Here, “self-organization” refers to a network that is organized without any centralized control mechanism, using only local information and simple rules, that is, solely organized through a distributed method. The advantages of using self-organization are completely distributed control, adaptability to a changing environment, robustness of a sudden change of environment, and scalability. Several cluster-based self-organization protocols for WSNs were studied as follows.

The Low-Energy Adaptive Clustering Hierarchy (LEACH) protocol [9] is a well-known self-organized cluster-based protocol. The LEACH decides CHs by a randomized rotation, in order to distribute the energy consumption of sensor nodes. Each sensor node compares the threshold T(n) that has a random number, in order to elect a CH. The CHs are changed periodically, in order to balance the energy of sensor nodes. Sensor nodes of LEACH organize the clusters on their own, by using both local decision and local communication [7, 9].

LEACH-Energy Distance (LEACH-ED) [10] is another self-organized cluster-based protocol. The LEACH-ED decides CHs based on two thresholds. First, the threshold is the ratio between the residual energy of a sensor node, and the total current energy of all of the sensor nodes in the network. Second, the threshold is the distance between some nodes that is less than the distance threshold; only one node becomes a CH. The LEACH-ED improves the load balance and the network lifetime better than does the LEACH.

The Hybrid Energy-Efficient Distributed Clustering Approach (HEED) [11] also uses clustering techniques for energy efficiency. The HEED decides CHs by two parameters. The first parameter is the residual energy of the sensor nodes. The second parameter is the intracluster communication cost to solve break-ties. The intra cluster communication costs are the (i) minimum degree cost, (ii) maximum degree cost, and (iii) average minimum reachability power (AMRP). The HEED prolongs the network lifetime longer than that of the generalized LEACH.

Robust Energy-Efficient Distributed (REED) clustering [12] uses clustering techniques for energy efficiency and robustness from unexpected failures or attacks on a CH. REED achieves fault tolerance by constructing multiple independent CH overlays, on top of the physical network. The CH selection method of REED is similar to that of HEED.

To maintain high energy efficiency, some cluster-based algorithms utilize one of several splitting and merging clustering methods, each of which adjusts the size of the cluster by itself [13–15]. Algorithms for the splitting and merging of clusters of WSNs were studied as follows.

To detect and track continuous objects (e.g., biochemical material), a location-based clustering method [13] is proposed. A boundary sensor detects an object in its vicinity, but has one or more one-hop neighbors that do not detect the object. To reduce the communication cost, the algorithm organizes boundary sensors into several clusters. If a cluster is larger than the predefined maximum cluster size, the cluster is split into two clusters. If a cluster is smaller than the predefined minimum cluster size, the cluster is merged into another cluster. However, that paper presents only the concept of splitting and merging. The actual process of splitting and merging is not addressed.

The energy-balanced dispatch algorithm [14] focuses on the energy efficiency problem of dispatching mobile sensor nodes to event areas. To reduce the energy consumption of dispatching mobile sensor nodes, the algorithm assigns each dispatching mobile sensor node to each cluster. At the clustering process, the algorithm splits and merges iteratively, to balance clusters and reduce the costs of clusters. However, the splitting and merging are operated not in a distributed way, but by a centralized dispatch algorithm.

The clustering-based data collection algorithm [15] focuses on the energy efficiency problem of clustering and prediction. In clustering, this algorithm uses dynamic splitting and merging clusters, in order to reduce the communication cost. However, these clustering, splitting, and merging methods are operated not for energy-efficient routing, but for using AR model-based similarity of features of CH and CMs.

In this paper, we propose EECSM for energy-efficient clustering of WSN. To reduce the energy consumption of CHs and CMs, EECSM adjusts the size of the clusters. When the size of a cluster is too large, EECSM splits the cluster into two clusters. On the other hand, when the size of a cluster is too small, EECSM merges the cluster into other clusters. Through splitting and merging clusters, EECSM prolongs the network lifetime.

3. Network Modeling

3.1. First Order Radio Model

A sensor node consumes energy, when transmitting and receiving data packets in a WSN. In wireless data transmission, energy consumption is correlated to the data packet size and the distance between the two sensor nodes. Extensive research has been conducted in the area of low-energy radios. Different assumptions about the radio characteristics, including energy dissipation in the transmission and receive modes, will change the advantages of different protocols. In our work, we assume the following first order radio model as the radio energy consumption model [9]. We also assume that a sensor node can identify its own energy, by using the radio model. This assumption is also used in LEACH [9] and HEED [11]. (i)

Transmitting the data packet: a sensor node consumes $ε_{elec} = 50 nJ/bit$ at the transmitter circuitry and $ε_{amp} = (100 pJ/bit) / m^{2}$ at the amplifier.

(ii)

Receiving the data packet: a sensor node consumes $ε_{elec} = 50 nJ / bit$ at the receiver circuitry.

(iii)

A k-bit data packet is transmitted from sensor node to sensor node, and $d_{i j}$ is the distance between the two sensor nodes i and j: the energy consumption of the sensor node i is given by $T_{i j} = ε_{elec} \times k + ε_{amp} \times d_{i j}^{2} \times k$ .

(iv)

The sensor node receives the data packet: the energy consumption of the sensor node is given by $R_{i} = ε_{elec} \times k$ .

3.2. Definitions for the Model

We define the following terms for our EECSM model. (i)

Period: in the data transmission phase, data packets are transmitted from all CMs to the BS. A cycle of this process is defined as a “period.”

(ii)

Clustering round: the number of repeated periods during a data transmission phase. EECSM maintains the same cluster configuration of the WSN during one clustering round.

(iii)

Network lifetime: the periods until a certain number of sensor nodes (e.g., 30 sensor nodes) are all discharged of their energy.

(iv)

Merging threshold: if the number of CMs of a cluster is below the merging threshold, the EECSM merges the cluster into other clusters.

(v)

Splitting threshold: if the number of CMs of a cluster is above the splitting threshold, the EECSM splits the cluster into two clusters.

4. Energy-Efficient Self-Organized Clustering with Splitting and Merging (EECSM): The Proposed Clustering-Based Routing Protocol

We propose EECSM for a WSN. To achieve energy efficiency, EECSM has the following five considerations, using the local information. First, sensor nodes that have the most remaining energy from neighbors become the candidates for the CHs, since the CH consumes a lot of energy. Second, each sensor node, except CHs, selects the nearest CH, in order to minimize energy consumption during the data transmission phase. Third, a cluster that has a number of CMs that is less than the merging threshold merges into other clusters, in order to minimize energy consumption of transmitting the data packets from the CHs to the BS. Fourth, a cluster that has a number of CMs that is larger than the splitting threshold splits into two clusters, in order to reduce the overhead of the CH. Fifth, to prevent any breakdown of CHs, a CH-backup mechanism selects a new CH that has maximum energy in the cluster.

The performance of EECSM is focused on clustering, splitting, and merging. For proper performance evaluation, EECSM does not use a particular routing method between CHs. This means that the CHs directly transmit data packets received from their particular CMs to the BS.

EECSM is comprised of three phases and a CH-backup mechanism; the clustering phase forms the clusters for the WSN (in Section 4.2); the merging cluster phase decides whether to merge clusters or not (in Section 4.3); the data transmission phase sends/receives the data packets (in Section 4.4); and the CH backup mechanism elects a new CH when the CH is a breakdown (in Section 4.5).

Before explaining the EECSM model, we explain the transition of state for each sensor node.

4.1. States of Sensor Nodes

Each sensor node of EECSM performs its roles while being transformed into the following four states (undecided state, CH state, CM state, and discharged state); if a sensor node becomes a node with the discharged state, it does not change its state. Table 1 indicates the roles of a sensor node, according to its state; moreover, Figure 1 indicates the state transition diagram of EECSM.

Table 1

State of sensor nodes.

State of sensor node		Specification
Undecided state	Condition	When a sensor node has been scattered first in the sensor field or a sensor node has acted as a CH or CM, the sensor node becomes an undecided state node.
Undecided state	Act	An undecided state node awaits signal packets from the CHs, except when a sensor node has been scattered in the sensor field for the first time.

CH state	Condition	(1) When the number of CMs of a cluster is less than the splitting threshold, one CM becomes the CH state node. (2) When the number of CMs of a cluster is more than the splitting threshold, two CMs become CH state nodes. (3) When a CH breaks or fails, a node with the CM state within the broadcasting range of the CH becomes a CH state node.
CH state	Act	A CH collects and aggregates information from its CMs and then transfers data packets to the BS. Also, a CH decides the CH(s) for the next clustering round.

CM state	Condition	When a CH is decided, all nodes with the undecided state in the cluster of the CH become CM state nodes.
CM state	Act	A CM periodically sends sensed information to its CH.

Discharged state	Condition	When a sensor node cannot function anymore, because all of its energy has been discharged, or it has broken down, it becomes a discharged state node.
Discharged state	Act	Nothing is done.

Figure 1

Transition diagram of sensor node states.

4.2. Clustering Phase

The clustering phase commences when the sensor nodes are first scattered in the sensor field or after the completion of the “data transmission phase.” This phase decides new CHs to form new clusters for the WSN. To achieve energy efficiency, the criterion in the selection of CH is the remaining energy of CMs. To reduce the load (or overhead) of CHs, the EECSM regulates the size of the clusters. The clustering phase is comprised of four steps: broadcasting step, splitting step, CH selection step, and clustering step, as follows.

4.2.1. Broadcasting Step

When the sensor nodes are scattered in the sensor field at period zero, there is no CH. Thus, all sensor nodes must decide on the CHs only on their own. The EECSM always uses the remaining energy, in order to decide the next CHs, except in period zero. Because the initial energies of all sensor nodes are identical in our assumption, all sensor nodes become CHs in period zero. To avoid this wasteful situation, EECSM uses another CH selection method just once at period zero. We define the broadcasting range, before the explanation of the other CH selection method. The broadcasting range is the reachable range of a data packet transmitted from a sensor node. The CH selection method at period zero uses the number of neighborhood sensor nodes within the broadcasting range, in order to decide who will be the CHs for the first round. In selecting a sensor node having the most neighbors within the broadcasting range as a CH, distances between the CH and CMs are reduced. This reduces the transmission energy between the CH and its CMs. Therefore, in order to decide CHs, we use the number of neighborhood sensor nodes within the broadcasting range just once at period zero. The procedure of deciding CHs at period zero is presented from 1.1 to 1.4.

To avoid selecting many CHs, the comparison range of the number of received signal packets widens the broadcasting range twice (from 1.3 to 1.4). The broadcasting step is not included in Figure 2, the flowchart of EECSM, since it is used only once at period zero.

Figure 2

Flowchart of EECSM.

4.2.2. Splitting Cluster Step

After each cluster configuration, EECSM considers the suitable number of clusters. First, EECSM tries to split a large cluster into two small clusters. The disadvantage of a large cluster is the high energy consumption of its CH, when the data packets are transmitted from its CM to its CH via a relatively long transmission path. When receiving the data packets, the more CMs the cluster has, the more its CH consumes energy. A processing bottleneck can also occur at the CH in a large cluster.

After the data transmission phase of the previous clustering round, in order to decide the number of clusters in the next clustering round, EECSM selects the next step, according to the value of the splitting threshold. If the number of CMs of a cluster is more than the splitting threshold value, the EECSM executes the splitting cluster step. Since a cluster is split into two clusters at the splitting cluster step, in the next round, two CHs for the split cluster are identified as the First CH and the Second CH, respectively.

The procedure of deciding the First CH is described from 2.1 to 2.5 of Algorithm 1. The procedure of deciding the Second CH can be seen from 2.6 to 2.8 of Algorithm 1. The CH consumes energy much more than the CMs. If a sensor node having low energy becomes the CH, it can quickly reach the discharged state. To prevent this problem, EECSM selects a CM having maximum energy as the next round CH. To prevent locating the First CH and the Second CH in close proximity, the procedures from 2.3 to 2.5 of Algorithm 1 are executed.

Algorithm 1: The clustering phase.

Clustering phase

(1) Broadcasting step

{If (Period = 0)}

(For all sensor nodes)

(1.1) Broadcast an undecided state-signal packet within the broadcasting range.

(1.2) Receive the undecided state-signal packets and count the number of received signal packets.

(For all sensor nodes)

(1.3) Broadcast the number of received signal packets within 2*(broadcasting range).

(1.4) Receive the signal packets (from 1.3), and compare the number of received signal

packets from others with the number of received signal packets of its own.

Within 2*(broadcasting range), if one's value is Max, the sensor node becomes a CH.

Else

(For each cluster)

If (The number of CMs ≥ Splitting threshold)

(2) Splitting cluster step

(For each CH)

(2.1) The CH decides the First CH that is the CM having maximum residual energy

of the cluster.

(2.2) The CH transmits a First CH-signal to the First CH.

(2.3) The First CH broadcasts a neighborhood-signal to neighbor sensor nodes.

(2.4) The CMs that receive a neighborhood-signal transmit ACK to the First CH.

(2.5) The First CH aggregates information of ACKs, and transmits to the CH.

(List of neighbors)

(2.6) The CH decides the Second CH that is the CM having maximum residual

energy of the cluster, except for the First CH and the CMs included in the list of neighbors.

(2.7) The CH transmits a Second CH-signal to the Second CH.

(2.8) The CH becomes a node with an undecided state.

Else

(3) CH selection step

(For each CH)

(3.1) The CH decides the next CH that is the CM having maximum residual energy

of the cluster.

(3.2) The CH transmits a CH-signal to the next CH.

(4) Clustering step

(4.1) CH broadcasts a CH-signal packet to the entire area of the sensor field.

(4.2) Others decide their own CH, by finding the closest CH.

4.2.3. CH Selection Step

If the number of CMs of a cluster is less than the splitting threshold value, the EECSM executes not the splitting cluster step, but the CH selection step. In this step, the CH decides only one CH for the next clustering round. The procedure of deciding the next round CH is presented from 3.1 to 3.2 of Algorithm 1. It is similar to deciding the First CH of the splitting cluster step.

4.2.4. Clustering Step

Each CH broadcasts a CH-signal packet to the entire sensor field for clustering. The sensor nodes, except for CHs, or nodes with discharged state receive, store, and list the CH-signal packets. Due to the fact that information can be used at the reclustering step of the merging cluster phase, the EECSM stores and lists the information temporally. This can reduce overhead of re-clustering. To minimize energy consumption of CMs during the data transmission phase, the sensor nodes select the nearest CH as its CH.

4.3. Merging Cluster Phase

After the clustering phase of the current clustering round, the EECSM checks the size of the clusters. Since the EECSM checks and splits the large clusters at the previous phase, it needs to check only the small clusters at this phase. The disadvantage of a small cluster is inefficient energy consumption, particularly when the data packets are transmitted from the CH to the BS, since energy consumption from a CH to the BS is much more than the energy consumption from a CM to the BS for longer transmission. For this reason, energy consumption of a small cluster is not energy efficient, and therefore the small clusters need to be merged into large clusters. The merging cluster phase on EECSM is comprised of two steps: merging cluster step and re-clustering step, as follows.

4.3.1. Merging Cluster Step

If the number of CMs of a cluster is less than the merging threshold value, the EECSM executes the merging cluster step. To merge small clusters into large clusters, procedures 1.1 to 1.2 are executed.

4.3.2. Reclustering Step

Procedure 2.1 is executed using the information stored in the clustering step of the clustering phase; after the re-clustering step is executed, the information stored in the clustering step is deleted (Algorithm 2).

Algorithm 2: The merging cluster phase.

Merging cluster phase

(For each cluster)

If (The number of CMs ≤ Merging threshold)

(1) Merging cluster step

(Each CH)

(1.1) Broadcast a merging cluster signal packet.

(1.2) All CMs and CH of the cluster become nodes

with an undecided state.

(2) Re-clustering step

(2.1) All nodes with an undecided state decide on their own CH,

by finding the closest CH.

Else

Do nothing

4.4. Data Transmission Phase

If the merging cluster phase is finished, clustering is complete. The EECSM enters into the data transmission phase, as EECSM starts to inform the situation of the sensor field to the external BS, by sending gathered data. The data transmission phase is divided into 2 steps: CM transmission step and CH transmission step.

In Algorithm 3, each CM creates a data packet that contains neighboring environment information for each period. The data packets are transmitted to the CH. Each CH aggregates the received data packets into a data packet and transmits the data packet to the BS directly. These procedures are repeated during each clustering round.

Algorithm 3: The data transmission phase.

Data transmission phase

While (1 clustering round)

(1) CM transmission step

(Each CM)

(1.1) Sense environment.

(1.2) Make a data packet.

(1.3) Transmit a data packet to its CH.

(2) CH transmission step

(Each CH)

(2.1) Aggregate received data packets from its CMs

(2.2) Transmit a data packet to the BS.

End while

4.5. CH Backup Mechanism

WSNs are useful in inaccessible and dangerous areas, such as military targets, disaster regions, and hazardous environments: they protect humans from danger. Using sensor nodes in those areas may cause a breakdown of individual sensor nodes. This can reduce the network lifetime. Furthermore, the breakdown of CHs can affect the network lifetime, as well as entail a loss of information. If the CHs break or fail, information received from its CMs to the BS may be lost.

In order to reduce the degradation of the network lifetime, EECSM has a “CH backup mechanism.” If the CH breaks or fails, the CMs that are close to their CH can recognize the breakdown of their CH. The reason why the CMs can realize the breakdown of their CH is that the CMs can recognize whether the data packet is transmitted from their CH to the BS. The advantage is that there is no additional overhead for recognizing the state of the CH.

The CH-backup mechanism of EECSM decides a new CH, after the breakdown of the CH. The CH backup mechanism is comprised of the following 2 steps: CH reelection step and cluster recovery step.

4.5.1. CH Reelection Step

The CH reelection step is carried out immediately, when the CM recognizes a breakdown of its CH during the data transmission phase (in procedure 1.1 of Algorithm 4). The CM recognizing a breakdown of its CH is usually the closest CM from the CH. In procedure 1.2 of Algorithm 4, the CMs broadcast the energy state-signal within the broadcasting range twice, in order to elect a new CH. The reason why that signal is broadcasted within the broadcasting range twice, rather than to the entire cluster, is to reduce the energy consumption of CMs. The CM having maximum residual energy becomes the new CH within that range.

Algorithm 4: The CH-backup mechanism.

CH backup mechanism

(For each cluster)

If (CH is dead; breakdown or discharged of energy)

(1) CH reelection step

(1.1) A CM that detects a failure of its CH broadcasts a CH-failure-signal

(For each CM received the signal)

(1.2) The CMs broadcast an energy state-signal within

2*broadcasting ranges

(1.3) The CMs compare the energy states

The CM having maximum energy becomes the new CH

(2) Cluster recovery step

(2.1) The CH broadcasts a CH-signal packet to the entire area of the

sensor field

(For each CM of the cluster)

(2.2) Receive the CH-signal packet

(2.3) The CMs compare the distances

If (the distance between the CH of the cluster and the

CM ≤ The distance between the closest CH of other

cluster and the CM)

The CM becomes a CM of the cluster

Else

The CM becomes a CM of the other closest cluster

4.5.2. Cluster Recovery Step

In procedure 2.1 of Algorithm 4, the new CH broadcasts the CH-signal to the entire area of the sensor field, since the new CH does not know the area of the cluster exactly. In procedure 2.3 of Algorithm 4, the CMs can decide their CH not only for the new CH of the cluster, but also for the CHs of other clusters, according to the distance. This can minimize the energy consumption of CMs during the data transmission phase.

The CH backup mechanism of EECSM can restore the unstable state of a network to the stable state of a network. It provides the robustness of the WSN.

5. Computational Experiments of EECSM

In this section, we show the performance of EECSM. To measure the performance of EECSM, we use Visual C++ of Visual Studio 2008.

5.1. Experimental Assumptions

In this section, we introduce the experimental environment of the EECSM. (i)

The locations of all sensor nodes and the BS are fixed.

(ii)

The deployment of sensor nodes uses random distribution.

(iii)

The location of the BS (x-axis: 25 m, y-axis: 150 m) is known in advance in the 50 m*50 m sensor field. For this field, the broadcasting range of EECSM is set to 10 m.

(iv)

The data packet size is 1,000 bits, and the signal packet size is 50 bits.

(v)

All sensor nodes have an initial energy of 0.5 J.

(vi)

The test utilized the average of the performances of 10 different deployments of sensor nodes in the sensor fields.

(vii)

We assumed a WSN cannot operate when more than 30% of the sensor nodes are discharged. Therefore, the network lifetime is defined as the time when 30% of sensor nodes are discharged in our experiments, except in the robustness experiment.

(viii)

In the experiments, the number of sensor nodes is 100, except for scalability experiments.

5.2. Clustering with Splitting and Merging

The size of clusters and the number of clusters seriously affect energy efficiency and the network lifetime. To properly adjust the size of clusters and the number of clusters, EECSM merges small clusters into other clusters and splits each large cluster into two clusters. To prove the validity of clustering with the splitting and merging method of EECSM, we show the following experiments.

5.2.1. Setting of Splitting and Merging Threshold Value

In this experiment, we find the optimal values of the splitting threshold value and the merging threshold value. We have that the range of experiments of the splitting threshold value is $31 ~ 60$ , and the range of experiment of the merging threshold value is $1 ~ 30$ , for the cases of 100 sensor nodes. The result of the enumerative method is as follows: the optimal value of the splitting threshold value is 46, and the optimal value of the merging threshold value is 20. Therefore, from now on, EECSM splits a cluster that has more than 46 CMs into two clusters and merges a cluster that has less than 20 CMs into other clusters.

5.2.2. Relative Frequency of Splitting and Merging

To prove the validity of clustering with the splitting and merging method of EECSM, we show how many splitting cluster steps and merging cluster steps are used. In this experiment, we do not count the number of splitting cluster steps or merging cluster steps per one clustering round, but rather count the number of clustering rounds when splitting cluster steps or merging cluster steps occur.

Table 2 indicates the average of relative frequency of splitting cluster steps and the average of relative frequency of merging cluster steps during network lifetimes. The splitting cluster step happens 60.3% of the total rounds, and the merging cluster step happens 55.0% of the total rounds. The results show that the splitting and merging of clusters happen frequently, in order to maintain the suitable number of clusters of EECSM, and this can seriously affect the network lifetime.

Table 2

The relative frequency of merging and splitting.

	Splitting cluster step	Merging cluster step
The average of steps	173.3	158.1
The average of clustering rounds	287.2	287.2
The average of relative frequency	60.3%	55.0%

5.2.3. Comparison of Network Lifetime of Clustering with and without Splitting and Merging

To prove the validity of clustering with the splitting and merging method of EECSM, we show the network lifetimes of clustering with and without the splitting and merging method of EECSM.

Figure 3 demonstrates that the network lifetime of clustering with the splitting and merging method of EECSM is between 7.03% (when the 1st sensor node is discharged) and 11.21% (when the 30th sensor node is discharged) longer than clustering without the splitting and merging method of EECSM. This experiment indicates that clustering with the splitting and merging method of EECSM prolongs network lifetime, by maintaining the suitable size of clusters. The suitable sizes of clusters reduce energy consumptions of sensor nodes, by reducing the transmission range of sensor nodes.

Figure 3

Comparison of network lifetimes of clustering with and without the splitting and merging method of EECSM.

5.3. Comparisons of Basic Performance with HEED

In this section, we compare the network lifetimes and residual energies of the sensor nodes of EECSM and HEED.

5.3.1. Network Lifetime Comparison

In this experiment, we compare the network lifetime of HEED and EECSM with the splitting and merging mechanism.

Figure 4 shows that the network lifetime of EECSM is 168.9% (when the 1st sensor node is discharged) longer and 23.7% (when the 30th sensor node is discharged) longer than the lifetime of HEED, respectively. This means that the five considerations of EECSM using the energy information operate properly and also prolong the network lifetime.

Figure 4

Comparison of network lifetimes of EECSM and HEED.

5.3.2. Residual Energy Comparison

In this experiment, we compared the average ratios of the residual energies to the network lifetimes of EECSM and HEED.

In Figure 5, the average ratio of residual energy of EECSM is at most 13.0% of that of HEED. This experiment indicates that the sensor nodes of EECSM consume energy much more uniformly than do those of HEED.

Figure 5

Experiment on the residual energy ratios of EECSM and HEED.

Comparisons of the two experiments (Figures 4 and 5) indicate the following. First, the sensor nodes having maximum energy from the neighborhood are decided by the next CHs, while reducing the frequent selection of certain sensor nodes. This allows a variety of selection of CH and maintains fair balance in the energy of sensor nodes.

Second, proper splitting and merging of clusters reduce the transmission distance of sensor nodes. In these results, we conclude that EECSM reduces and maintains fair balance in energy consumptions of sensor nodes, with the consequence that it prolongs network lifetime.

5.4. Advanced Performance of EECSM

In this section, we show the scalability and robustness of EECSM.

5.4.1. Scalability

Because WSNs consist of hundreds or thousands of sensor nodes, clustering and routing protocols of WSNs should have scalability. Since EECSM is a self-organized clustering model, EECSM should have good scalability. In this experiment, the number of sensor nodes is increased, in order to prove the scalability of EECSM from 100 sensor nodes to 500 sensor nodes. Here, the network lifetime of the WSN is defined only as the time when 30% of the sensor nodes are discharged.

Figure 6 shows that the network lifetime of EECSM, when the number of sensor nodes is more than 200 sensor nodes, is longer than the lifetime of EECSM, when the number of sensor nodes is 100 sensor nodes, from a minimum 11.67% to a maximum 14.68%. According to the increase of the number of sensor nodes, EECSM tends to increase the network lifetime, rather than to degrade the network lifetime. We can conclude that EECSM has good scalability, since the splitting and merging method of EECSM reduces the transmission range and maintains fair balance in energy consumptions of sensor nodes.

Figure 6

Experiment on the scalability of EECSM.

5.4.2. Robustness

WSNs are useful in dangerous areas, such as military targets, disaster regions, and hazardous areas. Thus, sensor nodes of WSNs in these areas can break suddenly. To use WSNs in these dangerous areas, clustering and routing protocols should be able to restore the network when a break happens. In order to prove that the CH backup mechanism works properly, we conduct the following experiments.

In this experiment, we compare the network lifetimes of normal states and abnormal states. The normal state means that a WSN is operating normally, without sudden breakdowns of sensor nodes. The abnormal state means that 0, 10, 20, 30, or 40 sensor nodes suddenly broke, sporadically, in the WSNs, before the 2,000th period.

In this experiment, the network lifetime is defined as the time when 50% of the sensor nodes which malfunctioned. 50% of sensor nodes malfunctioned is the total percentage of 100 sensor nodes that have encountered sudden breakdowns or discharged their energy; for example, when the number of sensor nodes are 100, 50% of sensor nodes which malfunctioned consist of sensor nodes discharged of their energy (A) and sensor nodes which suddenly broke down (B). (A, B) is (50, 0), (40, 10), (30, 20), (20, 30), or (10, 40).

Figure 7 shows that, although unexpected breakdowns occur, the effect is not serious. The maximum degraded network lifetime, when 40 sensor nodes suddenly break down, is at most 6.30%. The CH backup mechanism can restore the unstable state of the network to the stable state of a network, without any additional overhead. It can minimize the energy consumption of the unstable state and the CH backup mechanism, also. Therefore, the CH backup mechanism of EECSM is a robust mechanism, capable of coping with abnormal conditions of the external environment.

Figure 7

Experiment on sporadic failures.

6. Conclusion

This paper has proposed an energy-efficient self-organized clustering model, the so-called EECSM. The proposed model attempts to maximize the network lifetime and maintain load balance through the selection of CHs and by resizing clusters through combined techniques of advantages of self-organized protocols and cluster-based routing. Since EECSM uses a self-organizing approach, it has good characteristics, such as distributed control, adaptability, robustness, and scalability. Moreover, EECSM can decide on the proper CHs for energy efficiency. It can also resize clusters for maintaining a suitable size, and further it can also restore damaged clusters on its own, based on local information.

Clustering with the splitting and merging method has many interesting research issues. Appropriate research examples are the self-decision method of the merging threshold and the splitting threshold through information, which are localized neighbor information, for example, the number of neighbors, the current state of neighbors, and so on. In addition, research on clustering with the splitting and merging method for mobile ad-hoc networks (MANETs) holds the promise of valuable results.

Footnotes

Acknowledgments

This paper is the result of the research with the support of National Research Foundation of Korea (2009-0074081), using the funds from the Ministry of Education, Science and Technology, in 2009.

References

Yick

Mukherjee

Ghosal

Wireless sensor network survey

Computer Networks 2008 52 12 2292 2330

2-s2.0-46449122114

10.1016/j.comnet.2008.04.002

Mahfoudh

Minet

Survey of energy efficient strategies in wireless ad hoc and sensor networks

Proceedings of the 7th International Conference on Networking (ICN ′08)

April 2008

1 7

2-s2.0-50049115830

10.1109/ICN.2008.55

Al-Karaki

J. N.

Kamal

A. E.

Routing techniques in wireless sensor networks: a survey

IEEE Wireless Communications 2004 11 6 6 28

Akkaya

Younis

A survey on routing protocols for wireless sensor networks

Ad Hoc Networks 2005 3 3 325 349

2-s2.0-13944283393

10.1016/j.adhoc.2003.09.010

Israr

Awan

I. U.

Multilayer cluster based energy efficient routing protocol for wireless sensor networks

International Journal of Distributed Sensor Networks 2008 4 2 176 193

2-s2.0-46349103291

10.1080/15501320802001226

Younis

Youssef

Arisha

Energy-aware management for cluster-based sensor networks

Computer Networks 2003 43 5 649 668

2-s2.0-0142094198

10.1016/S1389-1286(03)00305-0

Dressler

Self-Organization in Sensor and Actor Networks 2007

New York, NY, USA

John Wiley & Sons

Prehofer

Bettstetter

Self-organization in communication networks: principles and design paradigms

IEEE Communications Magazine 2005 43 7 78 85

2-s2.0-24744466465

10.1109/MCOM.2005.1470824

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

2-s2.0-0033877788

10.

Sun

Clustering routing based maximizing lifetime for wireless sensor networks

International Journal of Distributed Sensor Networks 2009 5 1 88 88

10.1080/15501320802575047

11.

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

12.

Younis

Fahmy

Santi

An architecture for robust sensor network communications

International Journal of Distributed Sensor Networks 2005 1 3-4 305 327

10.1080/15501320500330786

13.

Zha

Metzner

J. J.

Kesidis

Dynamic cluster structure for object detection and tracking in wireless ad-hoc sensor networks

Proceedings of IEEE International Conference on Communications

June 2004

3807 3811

2-s2.0-4143126709

14.

Wang

Y. C.

Peng

W. C.

Tseng

Y. C.

Energy-balanced dispatch of mobile sensors in a hybrid wireless sensor network

IEEE Transactions on Parallel and Distributed Systems 2010 21 12 1836 1850

2-s2.0-78149285943

10.1109/TPDS.2010.56

15.

Jiang

Jin

Wang

Prediction or not? An energy-efficient framework for clustering-based data collection in wireless sensor networks

IEEE Transactions on Parallel and Distributed Systems 2011 22 6 1064 1071

2-s2.0-79955521337

10.1109/TPDS.2010.174