Survivable Self-Organization for Prolonged Lifetime in Wireless Sensor Networks

Abstract

More often than not, wireless sensor networks (WSNs) are deployed in adverse environments, where failures of sensor nodes and disruption of connectivity are regular phenomena. Therefore, the organization or clustering of WSNs needs to be survivable to the changing situations. On the other hand, energy efficiency in WSNs remains the main concern to achieve a longer network lifetime. In this work, we associate survivability and energy efficiency with the clustering of WSNs and show that such a proactive scheme can actually increase the lifetime. We present an easy-to-implement method named DED (distributed, energy-efficient, and dual-homed clustering) which provides robustness for WSNs without relying on the redundancy of dedicated sensors, that is, without depending on node density. DED uses the information already gathered during the clustering process to determine backup routes from sources to observers, thus incurring low message overhead. It does not make any assumptions about network dimension, node capacity, or location awareness and terminates in a constant number of iterations. The correctness of the algorithm is proved analytically. Simulation results comparing with contemporary approaches demonstrate that our approach is effective both in providing survivability and in prolonging the network lifetime.

1. Introduction

Compared to nodes in mobile ad hoc networks (MANETs), nodes in wireless sensor networks (WSNs) are more power constrained and have limited memory, computation, and transmission capabilities. In most applications, sensors are immobile and left unattended once deployed. These unique features necessitate novel algorithms suited for WSNs [1].

Clustering is a proven effective approach for self-organizing large WSNs into a connected hierarchy [2]. A WSN is partitioned into small groups called clusters. Each cluster has a coordinator called the cluster head (CH) to whom other member nodes (MNs) of the cluster communicate. CHs conduct data aggregation and send results to the sink. Thus, CHs form the virtual backbone of the network. Data relay may be single hop or multihop [3], and the hierarchy may have multiple tiers [4]. In Figure 1, a two-tier WSN is depicted. Besides achieving higher throughput due to reduced packet collisions, clustering has other desirable features related to energy conserving, network management, security, and scalability [5].

Figure 1

An example of clustered WSNs.

In recent years, the interest in clustered WSNs has generated a significant body of research works, most of which vary in assumptions about the WSN architecture, for example, global positioning system (GPS) capability [6–9], node mobility [10–13], presence of specially powerful nodes [6–8, 14], continuous or event-driven data delivery models [15, 16], and so on. The clustering algorithms also differ in their objectives. For example, in ACE (Algorithm for Cluster Establishment) [17], the aim is to form highly uniform clusters within a constant number of iterations, whereas in [18], dense clusters are favored to elect the minimum dominating set of CHs; and in WCA (weighted clustering algorithm) [11], limited-sized clusters are produced to prevent the degradation of media access control (MAC) performance. Examples of studies in which the ways to achieve an objective differ are clustering algorithms in [19–21], where energy efficiency is the objective. However, the ultimate reason to save energy in the clustering of WSNs should be the extension of network lifetime.

To prolong lifetime, we need to compensate for the large difference in power consumption between a CH and an MN. By and large, two approaches are followed in WSNs: load-balanced clustering [5–7, 22] and periodic rescheduling of CHs [23–25]. The load-balanced algorithms focus on balancing the intracluster traffic [7], or both the intra- and intercluster traffic [5, 6]. The authors in [22] minimize total energy consumption which does not necessarily maximize network lifetime [5]. A drawback of these designs is that CH positions are relatively fixed. A node which works as a CH for a long time is vulnerable to attack and single-point failure. The other approach to extend lifetime is to dynamically rotate the duty of CHs among sensors as in LEACH (low-energy adaptive clustering hierarchy) [23] and HEED (hybrid energy-efficient distributed clustering) [24]. In [25], several disjoint dominating sets are found and activated successively. These solutions, again, do not provide stability and robustness. A small modification in the network topology due to failures implies that new computations are needed to rebuild clusters and to re-elect CHs, thus incurring excessive overhead.

Both permanent and transient failures are inevitable in WSNs. These range from predictable failures (e.g., gradual energy drain of a sensor) to unexpected crashes (e.g., sudden enemy attack in battlefield monitoring). The failure of a CH is more detrimental than that of an MN. A failed CH may cause a cluster to remain isolated until the next reclustering. Meanwhile, important data from sensors cannot be reported and may be lost. This problem imposes a great need for dependable and survivable clustering, that is, clustering that is resistant to failures [26–28].

In this paper, we propose a rotation-based technique named DED (distributed, energy-efficient, dual-homed clustering) for WSNs, where the clustering itself provisions dual-homed protection for each sensor. The information gathered during clustering is used to “absorb” failures to minimize early reclustering. As a result, WSNs experience relatively stable clustering, reduced overhead, and prolonged lifetime. Our main contribution over other conventional schemes is that we provide survivability without the deployment of redundant sensors (i.e., independent of node density) and without the need of an extra layer of CHs. A notable consequence of our approach is that the neighborhood information is used to achieve survivability in a decentralized fashion (i.e., providing survivability at node basis), which is more fault tolerant and load balanced than centralized counterpart (i.e., providing survivability at cluster basis). We neither use dedicated energy-affluent nodes to serve as CHs nor use location-aware sensors. We prove the correctness of our algorithm analytically and compare the simulation results with other related works.

The rest of this paper is organized as follows. Section 2 briefly surveys earlier literature. Section 3 defines the network model and our objectives. Section 4 presents the details of the proposed protocol. Section 5 establishes the effectiveness of DED via extensive simulation, followed by the conclusion section. For the convenience of readers, the notations used in the description of the algorithm are summarized in Table 1.

Table 1

Notation used in the description.

Notation	Meaning
$\text{WSN}$	A wireless sensor network
$\text{DED}$	Distributed, energy-efficient, and dual-homed clustering
$\text{CH}$	A cluster head
$\text{MN}$	A member node of a cluster other than CHs
$P_{\text{CH}}$	Probability of a node to become a CH
$P_{\min \hspace{0.17em}}$	A predetermined threshold for probability $P_{\text{CH}}$
$E_{\text{rem}}$	Remaining energy of a node
$E_{\text{rate}}$	The rate at which energy is expense
$S_{\text{CH}}$	A set of tentative CHs during the clustering process
T	A predetermined upper bound of the duration for which a node can continuously work as a CH
$\text{APCR}$	Average power consumption rate for communications

2. Related Work

We classify related studies into two categories: those that deal with general robustness issue in WSNs without concerning clustering protocols (e.g., fault-tolerant hardware and software design) and those that integrate robustness with clustering schemes. We are interested in the second category only. For a further review, please refer to [29, 30].

In [8], the authors show how to recover from a gateway collapse without reclustering and without predeployment of redundant gateways. Their gateways are not power constrained and sensors are GPS capable. A node density-based clustering algorithm is suggested in [10] for increased stability in dynamic wireless networks. Self-stabilization is attained by minimizing the maximum number of nodes that need to change their topology information as a result of node mobility. In [31], overlapping multihop clusters are formed that have expedited recovery of nodes after CH failures. In [32], a rigorous analysis of the k-fold dominating set problem for a synchronous communication model is presented. A distributed approximation algorithm for general graphs and a randomized algorithm for unit disk graphs are given. However, none of the works above has energy awareness as an issue.

In [14, 33, 34], both network lifetime and robustness are discussed. REED (robust energy efficient distributed clustering) [33] is a distributed method which constructs k independent CH overlays on the top of the physical network. This method requires each sensor to reach at least one CH from each overlay, and its success depends on the node density. Even for 2-connected overlays (i.e., $k=2$ ), the total number of CHs selected may be twice that of traditional clustering (i.e., $k=1$ ). The work in [34] is an extension of [24] for the case of a highly dense network, where every MN in a cluster must reach at least two CHs simultaneously. In [14], the authors achieve fault tolerance simply by selecting two dedicated CHs for every cluster in each layer of the layered networks and formulate the problem as the transportation problem. Note that a common problem of all these works is that they enforce every MN to reach more than one CHs directly. This may not always be practical, since node density of a randomly deployed WSN is not necessarily uniform, and, in the course of time, node density changes as some nodes eventually become dead. Hence, the quest for a distributed clustering protocol for general WSNs, which is simultaneously energy efficient, survivable under heterogenous failures, and, most importantly, independent of node density remains unsated.

3. Problem Statement

Let us consider a set of quasistationary and GPS-incapable wireless sensors that are dispersed randomly on a field. All sensors are equally significant and have similar processing and transmission capabilities (as in [23, 24, 31, 33]). That is, specially competent nodes are not supposed to be responsible for CHs. Due to man-made and natural reasons, failures of sensors may occur at any time.

Our primary goal is to find a distributed, energy-aware, probabilistic cluster formation algorithm that achieves fault tolerance by providing alternate routes from sources to observers (i.e., providing dual-home protection) without explicitly demanding dedicated CHs as backup services. Each regular node should have a primary CH and a secondary backup which may be either another CH or a neighboring MN. Data is forwarded to the secondary destination in case the primary CH fails. Figure 2 illustrates how sensors may be dual homed. Here, node x is backed up through the directly reachable CH of a different cluster. Since no such CH is found for node y, it is backed up by an MN of a neighboring cluster (thus utilizing multihop-based forwarding). In the third case, as for node z, the backup is a neighbor y who has the same primary CH (thus using the neighbor's backup). In the worst case where none of above dual-homing schemes is feasible (this may happen when the CH is the only neighbor of an MN), an MN itself may become a CH after its designated CH fails. Observe that our dual-homing scheme, unlike the traditional dual-homing proposals, does not enforce redundant idle backups and is independent of node density.

Figure 2

Different dual-homing schemes are shown for sensors x, y, and z.

We notice that providing protection for the entire cluster as a whole through a backup CH is worse than providing protection for each sensor node independently. The first approach requires that each member of the cluster be informed and comply unanimously with the designated backup CH. Therefore, the extra energy needed for establishing such a protection is not less than that for providing survivability at the sensor node granularity. Furthermore, the second approach accomplishes fault management in a noncentralized fashion. Such a distributed fault tolerance arrangement becomes important when multiple failures occur in the same locality. Figure 3 shows how MNs of a cluster are reaffiliated to the neighboring clusters using previously collected backup information after their CH in Figure 2 fails. Thus, multihop clusters are formed, and the triggering of reclustering is avoided. Since reaffiliation (i.e., partial reclustering) incurs less communication overhead than complete reclustering, it conserves energy.

Figure 3

Re-affiliation of MNs are shown after a CH failure.

4. The Design of DED

In this section, details of the algorithm, including the parameter selections and the analysis, are presented.

4.1. Clustering Criteria

To lengthen WSN lifetime, the remaining lifetime of each sensor should be an important consideration during clustering. To explain further, the CH selection process can be viewed from two perspectives: initially a few nodes advertise themselves as tentative CHs (1st perspective) and eventually MNs select nodes from these advertised nodes as final CHs (2nd perspective).

From the 1st perspective, to be in the list of tentative CHs, a node tests itself whether it can work as a CH for a reasonable length of time without much energy loss. That is, it calculates remaining energy, $E_{\text{rem}}$ divided by energy usage rate, $E_{\text{rate}}$ to measure how long it can run as a CH. The greater is this value, the higher is the probability for this node to be a tentative CH. This probability is denoted as $P_{\text{CH}}$ , which ranges in 0~1. Here, $E_{\text{rem}}$ is the current available energy at the sensor. $E_{\text{rate}}$ is estimated by summing energy expense rate for the extra functionalities defined for a CH (e.g., overhead for data fusion and processing, media access control, scheduling, etc.) and average power consumption rate (APCR) for cluster communications. When a single power level is used for intracluster communication by all the nodes in a WSN, then that fixed energy consumption rate is equal to the APCR. When variable power levels are allowed, each MN can use the minimum power level that is enough to reach the CH. In this case, APCR is the average of the minimum power rates required by the neighbors within the cluster range. A sensor can evaluate APCR by itself if the communication links are symmetric; that is, two nodes can reach each other using the same transmission power level. For simplicity, we assume in this paper that all MNs expense the same rate of energy in data processing and a CH expenses data fusion energy proportional to the number of nodes it supports. As we may not calculate the exact number of nodes supported by a CH until the clustering is completed, we may approximate this number by using the node degree of a tentative CH at the beginning of a clustering algorithm. This number is updated during the progress of the algorithm, as more and more member nodes choose specific CHs. Thus, the approximated number of nodes supported by a CH gradually converges (i.e., becomes more accurate).

Note that both in [24, 33], a tentative CH is nominated based on the ratio of the residual energy and the maximum energy (when the battery is fully charged). This method does not necessarily encounter the remaining lifetime of a sensor, since it overlooks $E_{\text{rate}}$ . Besides, this metric performs well when all nodes starts with the same battery capacity, but for heterogeneous node batteries, this is not a good option. For example, say two nodes x and y have the same residual energy of 0.5 joule. Also, assume node x had an initial maximum battery capacity of 1 joule and node y had the capacity of 2 joule. In this scenario, the probability of being a CH for node x is two times higher than that of node y although they have the same amount of energy available. Even if all nodes calculate the ratio using the same maximum battery power (hence requiring a global parameter), the problem still exists. For example, consider the case where more sensors are needed to be deployed after some sensors have already been deployed and the later type of sensors have a different initial battery charge from that of previously deployed sensors. Such problems are ameliorated in our $P_{\text{CH}}$ calculation through the measurement of time length that a node can serve as a CH, that is, $E_{\text{rem}}$ / $E_{\text{rate}}$ .

From the 2nd perspective, every sensor tries to optimize lifetime while choosing the final CH from the tentative CHs that are advertised to it. We designate this secondary evaluation parameter as cost. In fact, cost breaks ties among multiple candidate CHs. MNs can use $E_{\text{rate}}$ of CH as a cost metric, since it provides a good indication of energy consumption for the cluster as a whole. Using $E_{\text{rem}}$ , the most energetic CH may be selected. If the goal is to form balanced clusters as in [17], the node degree, that is, the number of neighbors, may be used as cost. Alternatively, to form larger clusters as in [12], a sensor can favor a CH with higher node degree. If multiple transmission power levels are available, a sensor can prefer a tentative CH (not including itself) that is inside the radio range of its lowest possible power level (i.e., the closest CH). While the last two cost metrics may create dense clusters and trim down the dominating set of CHs, they may result in faster energy consumption for the CHs. This is somewhat contrary to the load balancing. The cost can also be a weighted composite of multiple metrics [11].

4.2. Algorithm

The pseudocode of DED is given in Algorithm 1. In brief, each node independently executes the algorithm. Based on message exchanges containing corresponding clustering parameters, each node becomes either a CH or an MN. Using the same information, backup nodes are also decided. After a constant time interval, all nodes finish choosing CHs and backups. In Algorithm 1, we do not show message receptions, for example, updating the set of tentative CHs, $S_{\text{CH}}$ . The set $S_{\text{CH}}$ is maintained at each node independently during the clustering process. It is updated whenever the node receives a broadcast message from its neighbor expressing the willingness to be a CH. A node also includes itself in the set when it wants to be a candidate CH. To avoid the need for node synchronization, explicit message exchanges can be done at the initiation of the clustering algorithm as adopted in [24].

Algorithm 1: Pseudocode of the DED protocol.

Phase I: Initialization

(1) $S_{\text{Neighbor}}$ ←nodes lie inside my radio range

(2) Compute cost and probability $P_{CH}$

(3) Broadcast a clustering initiation message

(4) myCH ← NULL

(5) myBackup ← NULL

Phase II: Cluster Head Selection

(6) while $(P_{CH}<1)$

(7)   if $(S_{CH}$ is not empty)

(8)      if $($ myID = leastCost $(S_{CH}))$

(9)         broadcastCH (myID, cost, TENTATIVE)

(10)   else if (random(0, 1) ≤   $P_{CH}$ )

(11)      broadcastCH (myID, cost, TENTATIVE)

(12)    $P_{CH}\leftarrow P_{CH}\times 2$

(13) endwhile

(14) Remove those CHs from $S_{CH}$ which have not still declared themselves in the FINAL status

(15) if $(S_{CH}$ is empty)

(16)    myCH ← myID

(17)    broadcastCH (myID, cost, FINAL)

(18) else myCH ← leastCost ( $S_{CH}$ )

(19)     joinCluster (myID, myCH)

Phase III: Backup Selection

(20) if (myCH ≠myID)

(21)   if ( $|S_{CH}|>1$ )

(22)      myBackup ← 2ndLeastCost ( $S_{CH}$ )

(23)   else myBackup ← randomly select a neighbor which is in the FINISH

               state and whose cluster head is not equal to myCH

(24)   if (myBackup = NULL)

(25)        my Backup ← randomly select a neighbor which is in the FINISH

           state and whose backup is not equal to myCH

(26)   if (myBackup = NULL)

(27)     myBackup ← myID

(28)   broadcast (myID, myCH, myBackup, FINISH)

The algorithm is divided into three phases for clarity. Phase I initializes the parameters and variables. At the start of clustering, the set of neighbors is needed to compute cost and $P_{\text{CH}}$ as described before. The minimum value for $P_{\text{CH}}$ is set to a predetermined threshold $P_{\min \hspace{0.17em}}$ to ensure a constant time complexity of the algorithm (proof is given in Section 4.3). Now, the equation for $P_{\text{CH}}$ becomes

$P_{\text{CH}}=\max \left\{\frac{E_{\text{rem}}}{T\times E_{\text{rate}}},\hspace{0.17em}{P}_{\min }\right\},$

(1)

where T is a constant that indicates the upper bound of the duration for which a node can continuously work as a CH. The value of T should be chosen such that the maximum energy of a node in the WSN is not greater than $T\times E_{\text{rate}}$ . Note that in a quasistationary system, a neighborhood discovery protocol does not need to be initiated each time the clustering starts. Besides, a node can easily update the neighborhood information by listening to the broadcast messages from its neighbors.

In Phase II, each node waits for the announcements of CH candidates that are advertised based on $P_{\text{CH}}$ . A single iteration of lines 6–13 should be long enough to receive broadcast messages, if any, from neighbors. A CH-broadcast message contains three parameters: the node ID, the cost of being a CH (as explained in Section 4.1), and the status of the CH. The status can be either final (denoted as “FINAL”), or tentative (denoted as “TENTATIVE”). The status is tentative if $P_{\text{CH}}$ < 1; otherwise, it is final. A tentative CH may turn into a regular MN if it finds a neighboring CH with lower cost. The messages received from the neighbors are not re-broadcast. Eventually, $S_{\text{CH}}$ becomes the set of CHs that are in the final status, and the node with the lowest cost is chosen as the designated CH for the MN. If $S_{\text{CH}}$ is empty (i.e., no neighbor is found yet being a CH of final status), the sensor broadcasts a message advertising itself as a CH with final status.

In Phase III, the backup is determined locally from the information that a sensor collected at the end of previous phase. The preferable backup of an MN is another CH within cluster range, if any. Otherwise, the node randomly chooses one of its neighbors whose CH is different from its own CH. If no such neighbor is found, the node picks up a neighbor whose CH is the same as its own CH, but whose backup destination is not the same as its own CH. If no neighbors meet these conditions, the node represents itself as the backup. A node can be either a CH or the backup for itself but not both. As long as the WSN is connected, our approach will find two different nodes for the CH and the backup, which is proved in the next subsection. At the end of the algorithm, each node broadcasts a “FINISH” message informing its CH and the backup to other nodes. Although backups are selected from neighbors randomly here, the decision may be directed by some better metrics such as energy remaining, hop count, distance, node degree, or a combination of these attributes.

4.3. Analysis

We first prove that our algorithm finishes within a constant number of iterations.

Theorem 1.

The running time of DED is O(1).

Proof.

The algorithm has only one waiting loop in lines 6–13. Let us assume that it iterates i times before terminating at $P_{\text{CH}}\ge 1$ . Since the minimum (i.e., worst case) value of $P_{\text{CH}}$ is $P_{\min \hspace{0.17em}}$ and $P_{\text{CH}}$ doubles at every iteration, the loop continues as long as

$\begin{array}{cc}\hfill & P_{\min }\times 2^{i-1}<1,\hfill \\ \hfill & \hspace{1em}⟹i<1+{\log }_2\frac{1}{P_{\min }},\hfill \\ \hfill & \hspace{1em}⟹i\le \lceil {\log }_2\frac{1}{P_{\min }}\rceil .\hfill \end{array}$

(2)

Since $P_{\min \hspace{0.17em}}$ is constant, the algorithm terminates in O(1) iterations.

We analyze the message overhead incurred in DED with respect to the prominent clustering algorithm, REED [33]. The reason to select REED in comparison is that like DED, REED focuses on survivability and considers similar clustering assumptions (e.g., absence of extra power nodes for backups, GPS incapability, and so on). We exclude the neighborhood discovery procedure for both cases. In DED, one message is broadcasted at Phase I. At Phase II, there may be zero or one message broadcast in each iteration of the loop 6–13 and one message broadcast in lines 15–19. At Phase III, there is no broadcast if the node is a CH, but one broadcast if the node is an MN. Hence, in the worst case, the three phases of DED require a total of

$\begin{array}{c}1+\lceil {\log }_2\frac{1}{P_{\min }}\rceil +1+1⟹\lceil {\log }_2\frac{1}{P_{\min }}\rceil +3,\end{array}$

(3)

messages to broadcast. In REED, the “Initialization” phase broadcasts one message. For two CH overlays (i.e., $k=2$ ), the “main processing” phase repeats maximum

$k\times \left(\lceil {\log }_2\frac{1}{P_{\min }}\rceil +1\right)⟹2\times \lceil {\log }_2\frac{1}{P_{\min }}\rceil +2,$

(4)

times with zero or one message broadcast at each repetition. The “finalization” step broadcasts $k+1=3$ messages at most. Therefore, in the worst case, it needs a total of

$2\times \lceil {\log }_2\frac{1}{P_{\min }}\rceil +6,$

(5)

messages to broadcast. Thus, the clustering process of DED consumes significantly less energy than the other one. The impacts of this is also evident in simulation results as presented in Section 5.

We next prove that the working CH and the backup destination chosen for a node are not the same to ensure survivability upon failures.

Theorem 2.

The CH and the backup for an MN found by DED are different if the nodes in the WSN are connected.

Proof.

Let us consider an arbitrary node x. After the execution of line 14 of the DED algorithm, $S_{\text{CH}}$ of node x contains those candidate CHs that have reached their final states. There are three cases: the cardinality of $S_{\text{CH}}$ can be 0, 1, or greater than 1.

Case 1.

If $S_{\text{CH}}$ is empty, node x itself becomes a CH. As ensured in line 20 of Phase III, a CH does not select a backup.

Case 2.

Assume that there is a single node in $S_{\text{CH}}$ . Let us denote this node as y. Since node x does not declare itself as a final candidate CH before line 14, x ≠ y and node y must be a neighboring CH of node x. Consequently, node x becomes an MN joining to this single neighboring CH as in line 19. In Phase III, node x tries to find another neighbor (as a backup) whose CH is not node y, or, at least, whose backup is not node y. If no such neighbor is found, there may be two subcases: (a) node x has only one neighbor which is node y and (b) node x has other neighbors whose CHs and backups are chosen from the nodes x and y. For subcase (a), node x selects itself as the backup (as in lines 26-27), which means the CH and the backup for node x are not the same. Subcase (b) is impossible: node x cannot be selected by the other neighbors, since it has not yet finished executing DED.

Case 3.

The last possibility, where the cardinality of $S_{\text{CH}}$ is 2 or more, implies that these CHs are from different clusters and within the radio range of node x. One CH with the least cost is selected as the designated CH for node x (in line 18) and another CH with the second least cost is selected as the backup (in line 22). Thus, the CH and the backup of node x are different in this occurrence too.

We ascertain that the backups of MNs do not create a cycle. Otherwise, MNs cannot reach the sink after their CHs crash.

Theorem 3.

The backups of MNs never form a cycle.

Proof.

We will prove Theorem 3 by contradiction. Let there exists a cycle among c (≥2) distinct nodes $x_1$ , $x_2$ , …, $x_c$ . That is, the backup of $x_1$ is $x_2$ , the backup of $x_2$ is $x_3,\dots$ , and the backup of $x_c$ is $x_1$ .

First of all, none of these nodes can be a CH, since a CH is not protected by a backup directly in the DED protocol. Also, a node cannot be chosen as a backup until it reaches the “FINISH” state. Let us sort the nodes in the cycle in the order of finishing. Since $x_2$ is the backup of $x_1$ , $x_2$ must finish before $x_1$ . For similar reasons, $x_3$ finishes before $x_2,\dots$ , and $x_1$ finishes before $x_c$ . But this is a contradiction. Therefore, there can be no cycle in the chain of backups.

5. Performance Assessment

Most of the current simulators for WSNs largely focus on networking issues and are difficult to extend for distributed computing issues [35, 36]. Moreover, no single effort to simulate WSNs is dominant under various assumptions since WSNs are often tailored for specific applications. We develop a C/C++ language-based event-driven simulator to ensure fast and scalable simulation [37, 38]. We use the same simulation model as in [23, 24, 33] for comparison purposes.

5.1. Simulation Model

We use a 2D field of area $100\times 100$   ${\text{m}}^2$ where nodes are randomly dispersed. The initial energy of a node is arbitrarily chosen from the range of $1~2$ joule to simulate the variance of battery lifetime. We set $P_{\min \hspace{0.17em}}$ to 0.0009, which means that a maximum of $\lceil {\log \hspace{0.17em}}_{2}1/P_{\min \hspace{0.17em}}\rceil =11$ iterations are allowed in the loop of the algorithm. In the radio model, both the free space ( $d^2$ power loss) and the multipath fading ( $d^4$ power loss) channel models are used depending on the distance between the transmitter and receiver. To transmit a l-bit message over a distance d, the radio expends

$E_{Tx}\left(l,d\right)=\{\begin{array}{cc}l{E}_{\text{elec}}+l{ϵ}_{fs}{d}^2,\hfill & d<d_0,\hfill \\ l{E}_{\text{elec}}+l{ϵ}_{mp}{d}^4,\hfill & d\ge d_0,\hfill \end{array}$

(6)

and to receive this message, the radio expends

$E_{Rx}\left(l\right)=l{E}_{\text{elec}}.$

(7)

Here, $d_0$ is the threshold distance and $E_{\text{elec}}$ , ${ϵ}_{fs}$ , and ${ϵ}_{mp}$ are parameters for digital electronics and communication energy expense. These are set as $d_0=75\hspace{0.17em}\text{m}$ , $E_{\text{elec}}=50$  nJ/bit, ${ϵ}_{fs}=10$  pJ/bit/ ${\text{m}}^2$ , and ${ϵ}_{mp}=0.0013$  pJ/bit/ ${\text{m}}^4$ . For data fusion, energy is spent at 5 nJ/bit/signal. Other simulation parameters are data packet size = 100 bytes, broadcast packet size = 25 bytes, intercluster transmission range = 3 × intra-cluster transmission range, and sink position at (50 m, 110 m).

A node dies after 99.9% energy drainage. Other than this type of regular failure, there may be some unexpected failures. The probability of failing a CH unexpectedly is denoted by F (0% $~$ 100%). Between two clustering initiations, that is, during the normal WSN operation, multiple failures may occur. The network topology is re-generated randomly for each experiment. Every data point is drawn with 95% confidence interval.

5.2. Clustering Aspects

We study the effects of different cost functions. A good measure is to see how many clusters have only a single node. The fewer are such clusters, the better is the system organization. As depicted in Figure 4, we find that the number of nonsingle node clusters is increased when the cluster radius is increased. Both $E_{\text{rate}}$ and node degree-based cost generate fewer single-node clusters than the other metrics, since these two encourage load balancing.

Figure 4

Non-single node clusters in DED.

There are multiple definitions available for network lifetime [2, 39]. Lifetime can be regarded as the time elapsed until the first or last node dies, the time until a fraction of nodes dies, or the time until the WSN becomes partitioned. Using the last definition, Figure 5 plots lifetime for different cost functions. The WSN lifetime is found to be longer when cost is $E_{\text{rate}}$ . The inverse of node degree, which favors dense clustering rather than balanced clustering, shows poor lifetime. For comparison purposes, we implement the $P_{\text{CH}}$ as calculated in HEED [24] and find that lifetime under this $P_{\text{CH}}$ model is poorer, since it does not consider heterogenous initial battery power. We note that lifetime does not increase linearly with the increase in the number of sensors. The rationale behind this characteristic is that with the network area kept fixed, the higher number of nodes means the higher node density (i.e., higher number of neighbors). It increases the number of broadcast messages exchanged among neighbors during the clustering process. As a result, the ratio of clustering energy expense to the total dissipated energy goes up, affecting lifetime.

Figure 5

Lifetime at different cost metrics.

We also implement REED [33] clustering protocol for the 2-connected case. Since the two overlays there work independently, the percentage of nodes required to be CHs is found almost double to that of DED as depicted in Figure 6. This percentage is reduced at higher node density and larger cluster radius. Observe that narrower confidence intervals are achieved for the data points in this graph.

Figure 6

The number of CHs selected.

Figure 7 indicates that REED is more expensive than DED in terms of energy too. Clustering energy expended at each sensor is increased at larger cluster radius. Because longer cluster radius causes higher energy expense to send messages. Not only that, it causes higher energy expense to receive messages as the total number of receiving messages is increased due to the growth of neighbors. The growth of neighbors is also observed at higher node density resulting increased energy spent per clustering.

Figure 7

Clustering energy spent per node.

5.3. Fault Tolerance Properties

To view a comparative performance between DED and REED amid unanticipated failures of CHs, we study the first ten clustering rounds of each experiment to segregate failures due to energy depletion. The cost function is set node degree for both protocols. The default clustering radius is 15 meters. Figure 8 shows the increase in the percentage of successful data transmission (w.r.t. single-homed systems) at F = 0.2 and 0.4. Even though REED provides dual CHs per MN (at extra expense), the gain is not much higher (around 5%) than DED.

Figure 8

Comparison of throughput increase.

Figure 9 plots average total energy required (summing over all nodes of a WSN) for each clustering versus the number of nodes for different failure rates. We find that energy spent per clustering is independent of failure rates but goes up with node density.

Figure 9

Energy required per clustering.

Figure 10 shows that the time requirement to finish one clustering process does not differ at different failure rates. However, REED spends much higher time than DED due to the need for higher number of message communications as analyzed in Section 4.3. Unlike energy, time spent per clustering is not elevated with higher node density. The rationale behind this behavior is that clustering algorithms are executed in a distributed manner at each node, and the order of their running time do not depend on node density. In REED, increased node density rather results in fewer selection of proxy CHs, thus saving time a little bit.

Figure 10

Time spent per clustering.

Figure 11 demonstrates that the lifetime of WSNs reduces significantly at higher failure probability. However, increasing the node density prolongs network life. We find that DED achieves the much needed prolonged lifetime, as high as 200% of the lifetime in REED when there is 100% failure probability during normal operation. In REED, although each MN sends data through one of the two designated CHs at a time, all the nodes in WSNs may not be synchronized to use the same overlay. Consequently, the number of nodes serving as CHs during normal operation is higher. Not only that, the clustering process in REED is more expensive. Thus, the simplicity of DED clustering protocol helps it to perform better.

Figure 11

WSN lifetime over failures.

6. Conclusion

In this work, we propose an easy-to-implement, proactive, survivable, and energy-efficient organization scheme, DED, that does not depend on node redundancy for the purpose of fault tolerance, a feature contrasting with most of the survivable protocols suggested so far for WSNs. DED uses the information collected from its neighbors during the clustering process (thus inducing minimal overhead) to provide dual-home protection from failures and to reduce the number of reclustering. Rather than protecting the whole cluster collectively, DED provides backup at the member node level in a noncentralized fashion; this characteristic becomes more important when there are multiple failures in the same locality. The clustering parameters can address heterogeneous initial battery power as well. Analytical proofs of the correctness of the algorithm and simulation-based comparison with other protocols are provided. To the end, our scheme can achieve as much as 200% network lifetime of existing WSN protocols with dual-layer clusters, especially in highly failure-prone environment.

Our future research direction is to apply DED for multi-homing (higher than two) protection capabilities and study the tradeoff between network lifetime and extra energy spent on robustness. Rather than selecting backups randomly from neighbors, the selection may use some better metrics such as energy remaining, hop count, distance, node degree, or a combination of these attributes. We also plan to consider issues such as node mobility, triggering partial clustering in a local region in emergency cases, and forming non uniform cluster sizes by varying cluster radius to prevent a skewed load distribution near the sink [5].