4.1.1 Fault Detection

Jiang [102] proposed a DFD scheme that detected faulty sensor nodes by exchanging data and mutually testing neighboring nodes. Jian-Liang et al. [103] proposed a weighted median fault detection scheme that used spatial correlations among the sensor measurements (e.g., temperature, humidity). Lee and Choi [104] presented a DFD algorithm that identified faulty sensor nodes based on comparisons between neighboring sensor nodes' data. The DFD algorithm used time redundancy to tolerate transient faults in sensing and communication. Khilar and Mahapatra [105] proposed a probabilistic approach to diagnose intermittent WSN faults. The simulation results indicated that the DFD algorithm's accuracy increased as the number of diagnostic rounds increased where neighboring sensor nodes exchanged measurements in each round.

Ding et al. [91] proposed algorithms for faulty sensor identification and FT event boundary detection. The algorithms considered that both the faulty sensors and normal sensors in an event region could generate abnormal readings (readings that deviate from a typical application-specific range). Krishnamachari and Iyengar [106] proposed a distributed Bayesian algorithm for sensor fault detection and correction. The algorithm considered that measurement errors due to faulty equipment are likely to be uncorrelated. Wu et al. [107] presented a fault detection scheme in which the fusion center (the node that aggregated data from different nodes) attempted to identify faulty sensor nodes through temporal sequences of received local decisions using a majority voting technique. Lo et al. [108] presented a distributed, reference-free fault detection algorithm based on local pairwise verification between sensor nodes monitoring the same physical phenomenon. The authors observed that a linear relationship existed between the outputs of a pair of sensor nodes that could be exploited to detect faulty sensor nodes. Since the fault detection was done pairwise, the algorithm was able to conserve energy. Results revealed that the proposed algorithm could achieve a detection accuracy of 84% and a false alarm rate of 0.04%.

Miao et al. [109] proposed agnostic diagnosis for detecting silent failures (i.e., failures with unknown types and symptoms). The proposed detection technique exploited the fact that a sensor node's metrics (e.g., radio on-time, number of packets transmitted in a time interval) exhibited certain correlation patterns, violation of which indicated potential silent failures. The detection accuracy of the proposed scheme was close to 100% for small WSNs, whereas the detection accuracy decreased sharply and false alarm rate increased as the WSN size increased. The proposed technique required a sink node to collect data from all the sensor nodes in the WSN, which resulted in rapid energy depletion of the sink node and sensor nodes near the sink node. Furthermore, the fault detection latency of the proposed scheme was high due to its centralized nature.

There exists some work related to anomaly detection in WSNs. Bhargava and Raghuvanshi [110] proposed a method for anomaly detection in WSNs based on S-transform (an extension of continuous wavelet transform). The S-transform extracted the features from sensor nodes' data set, which were used for training of support vector machine (SVM). The SVM was then used for the classification of normal and anomalous data. Results revealed that the proposed scheme's accuracy for data classification ranged from 78% to 94%. Salem et al. [111] proposed an anomaly detection algorithm for medical WSNs. The proposed algorithm first classified instances of sensed patient attributes as normal and abnormal. The algorithm then used regression prediction to discern between a faulty sensor reading and a patient entering into a critical state. The results demonstrated the algorithm's ability to achieve a relatively low false alarm rate (1%) and a good detection accuracy (the attained accuracy was not specified) for the medical WSN application.

4.1.2 Fault Tolerance

In work related to FT for WSNs, Koushanfar et al. [94] proposed an FT scheme that provided backup for one type of sensor using another type of sensor, but they did not propose any FT model. Clouqueur et al. [112] presented algorithms for collaborative target detection in the presence of faulty sensors. Chiang et al. [113] designed system-level test interfaces for remote testing, repair, and software upgrade for sensor nodes. The authors evaluated the proposed test interfaces on Texas Instrument's MSP430 microcontroller-based sensor nodes. Experimental results revealed that the test interfaces with double, triple, and quadruple redundancies increased the WSN's availability.

Krasniewski et al. [114] proposed a protocol to diagnose and mask arbitrary sensor node failures in an event-driven WSN. The protocol considered a clustered WSN with rotating cluster heads. The protocol assigned each sensor node a trust index to indicate the sensor node's track record in reporting past events correctly. The cluster head analyzed the event reports using the trust index and made event decisions. The authors simulated the protocol using ns2 and observed that the protocol was able to detect events correctly even if more than 50% of the sensor nodes were compromised. Sun et al. [115] introduced a trust mechanism to evaluate the trustworthiness of a sensor node and the sensor node's data. The authors defined memory depth to characterize the temporal correlation and aggregation bandwidth to characterize spatial correlation. A sensor node used memory depth to calculate self-trustworthiness of the sensor node's data based on stored historical/past data and the current data. When a sensor node reported its sensed data to the aggregator, the aggregator's trustworthiness to the reported result depended both on the trustworthiness of the sensor node reporting data and the trustworthiness of the sensor node to its sensed data. Subsequently, each aggregator reported the aggregated result and the aggregator's self-trust opinion to the upper layer aggregator progressively, and so on until the aggregated result reached the sink node. Results demonstrated the effectiveness of the proposed mechanism for continuous media streaming and discrete data in wireless multimedia sensor networks (WMSNs).

There exists some work on providing FT in WSNs by deploying relay nodes and considering connectivity as an FT metric. Relay nodes communicate with sensor nodes, other relay nodes, and sink nodes to prolong WSN lifetime. Zhang et al. [116] developed approximation algorithms for determining a minimum number of relay nodes along with the relay nodes' placement to achieve certain connectivity requirements. Han et al. [117] considered the problem of deploying relay nodes to provide FT in heterogeneous WSNs where sensor nodes had different transmission radii. They developed approximation algorithms for full and partial FT relay node placement. Full FT relay node placement deployed a minimum number of relay nodes to establish disjoint paths between every sensor and/or relay node pair, whereas partial FT relay node placement only considered sensor node pairs. Baldi et al. [118] evaluated gossip algorithms, which are distributed algorithms that distribute computational burden across all nodes and considered connectivity as an FT metric.

Sen et al. [119] introduced region-based connectivity: an FT metric defined as the minimum number of nodes within a region whose failure would disconnect the network. Alwan and Agarwal [120] provided a survey of FT routing techniques in WSNs. Souza [121] presented a framework for failure management in WSNs, focusing on fault diagnosis and recovery techniques. The presented FT framework mitigated the failure propagation in a business (enterprise) environment by implementing different FT techniques.

4.1.3 WSN Reliability Modeling

There exists some work on FT WSN modeling. Cai et al. [122] presented a reliability model to prolong the network lifetime and availability based on connectivity and coverage constraints. Zhu and Papavassiliou [123] presented a model that characterized sensor connectivity and investigated the trade-offs among sensor node connectivity, power consumption, and data rate. They also discussed the impact of sensor connectivity on system reliability. Vasar et al. [124] presented Markov models for WSN reliability analysis. They presented a reliability comparison for various numbers of defective components' replacements with hot-standby redundant components. Xing and Michel [125] presented WSN reliability and security modeling in an integrated manner. Their modeling technique differentiated two types of WSN failures: security failures due to malicious intrusions and traditional failures due to malfunctioning components.

Moustapha and Selmic [88] used recurrent neural networks to model sensor node dynamics for sensor fault detection. Their network model corresponded to the WSN topology such that the recurrent neural network input was taken from the modeled sensor node and neighboring sensor nodes. Kannan and Iyengar [126] developed a game-theoretic model of reliable length- and energy-constrained routing in WSNs. They showed that optimal length-constrained paths could be computed in polynomial time in a distributed manner using geographic routing. Mukhopadhyay et al. [127] presented a method that used sensor data properties to enable reliable data collection. The method consisted of predictive models based on temporal correlation in sensor data. They demonstrated that their method could handle multiple sources of errors simultaneously and could correct transient errors arising in sensor node hardware and wireless communication channels.

Although DFD algorithms were proposed in the literature for detecting sensor faults, the fault detection was not leveraged to provide FT. There exists work in the literature regarding FT in WSNs [94, 116, 117, 119, 122]; however, FT metrics such as reliability and MTTF were not investigated rigorously in the context of WSNs. Specifically, reliability and MTTF were not considered hierarchically at the sensor node, WSN cluster, and WSN level. This hierarchical characterization of FT metrics facilitates a WSN designer to determine an appropriate WSN topology (i.e., number of clusters and sensor nodes with required FT capability in each cluster).

4.2.1 Sensor Faults

The faults in sensor nodes include permanent faults where a node becomes dead and Byzantine faults where the node behaves arbitrarily or maliciously. Figure 4.2 shows an example of Byzantine faults where sensor nodes A–E are equipped with temperature sensors and process the measured reading to give temperature in Fahrenheit. The sensor nodes send the sensor node's sensed temperature readings to other neighboring nodes. The temperature sensor in the sensor node D behaves maliciously and sends inconsistent and arbitrary temperature values to other nodes (60, 100, 150, and 10 to A, B, C, and E, respectively). The rest of the sensor nodes send consistent values to other neighboring nodes. As a consequence, nonfaulty sensor nodes obtain different global information about the temperature in the region and may conclude on a false value of the overall temperature of the region. The fault detection algorithm needs to be robust to such inconsistent behavior that can jeopardize the collaboration in the WSN [112].

Several efforts have been made to classify malicious sensor behavior [93, 128]. While different sensor fault taxonomies have been proposed, three particular behaviors are targeted by DFD methods. The outlier faults occur when a sensor signal spikes in value (Fig. 4.3(a)) and can be detected by comparing sensor readings to previous readings or neighboring sensor nodes' readings. The stuck-at faults occur when the output remains at a constant level (Fig. 4.3(b)). The noisy faults occur when the signal-to-noise ratio of the sensor's output is low, resulting in random data (Fig. 4.3(c)). An effective fault detection algorithm must be able to identify the broadest possible range of malicious output while minimizing fault positives. Because the broad range of sensor failures result in a mixed detection rate for different algorithms, accurate simulation is important for studying sensor failures [93].

4.2.2 Taxonomy for Fault Diagnosis Techniques

A fault diagnosis system is a monitoring system that detects faulty sensor nodes and their location in the WSN. Fault diagnosis techniques are classified based on the nature of tests, correlation between sensor readings, and characteristics of sensor nodes [129]. The key component of a fault diagnosis system is a fault detection algorithm, and the key terminology includes correctness, latency, detection accuracy, and false alarm rate. A fault diagnosis is correct if no fault-free sensor nodes are mistakenly diagnosed as faulty. Latency is defined as the time elapsed since the appearance of the fault to the isolation of the faulty sensor node. Detection accuracy is defined as the ratio of the number of faulty sensor nodes detected to the actual number of faulty sensor nodes in the network. The accuracy of the fault detection algorithm is a crucial factor in maintaining reliable WSN operation. The ratio of the number of fault-free sensor nodes diagnosed as faulty to the actual number of fault-free sensor nodes is the false alarm rate. Fault detection techniques for WSN can be broadly categorized into centralized and distributed approaches [129].

4.3.1 Fault Detection Algorithm 1: The Chen Algorithm

The first algorithm, which we refer to as the Chen algorithm [90], relies on simple majority counts to determine faults. The approach is practical because sensor nodes have limited computing ability; hence, lightweight calculations are preferred over intensive calculations. Each sensor node can exist in four states: good (GD), faulty (FT), likely good (LG), or likely faulty (LF). A sensor node in likely states is unsure if the sensor node is faulty and uses the neighbors' states of sensor nodes to finalize the sensor node's decision. The algorithm's implementation complexity is low and the probability of correct diagnosis is high.

Table 4.1 lists the notations used in the Chen algorithm [90]. The neighboring sensor nodes in a WSN are those that are within the transmission range of each other. Each sensor node sends the sensor node's sensed values to the sensor node's neighboring sensor nodes. A sensor generates test result based on the sensor node's neighbor 's measurements using variables , , and threshold values and . The sensors and are both good or both faulty if ; however, the sensor nodes have a different good or faulty status if . Each sensor node sends the sensor node's tendency values (i.e., estimated state) to all the sensor node's neighboring sensor nodes. The test values from neighboring sensors determine the tendency value of sensors to be LG or LF, and the number of LG sensors with the same results determines whether the sensors are GD or FT. Precisely, and , must be greater than or equal to for to be identified as good. The algorithm diagnoses a good sensor as GD in the first round if the sensor node has less than bad neighbors. The Chen algorithm's important steps are depicted in Algorithm 1.

Notation	Description
	Set of all the sensors involved in the DFD algorithm
	Set of neighbors of sensor node
	Measurement of
	Measurement difference between and
at time (i.e., )
	Measurement time difference,
	Measurement difference between and
from time to (i.e., )
	Test between and , ,
and	Two predefined thresholds
	Tendency value of a sensor:

4.3.2 Fault Detection Algorithm 2: The Ding Algorithm

The second algorithm, which we refer to as the Ding algorithm [91], is a WSN fault detection algorithm with a low computational overhead. The results indicate that the algorithm can identify faulty sensors with relatively high accuracy even when the sensor failure probability is as high as 20%. The Ding algorithm's important steps are shown in Algorithm 2.

The algorithm compares the sensor node 's reading with the sensor node's neighbors with measurements . The comparison is done by comparing with median of , that is,

4.1

If there are sensors in total, the algorithm computes (i.e., ). The mean of is given by Ding et al. [91]:

4.2

The standard deviation of is given as [91]:

4.3

Standardizing the dataset yields , that is:

4.4

If , then the Ding algorithm detects as faulty where is a predefined threshold value. Mathematically, if where denotes the set of sensors claimed as faulty.

Section 4.5 discusses the implementation and effectiveness, in particular the detection accuracy, which is used implicitly in our Markov model as the coverage factor , of these fault detection algorithms.

4.4.1 Fault-Tolerance Parameters

Fault tolerance in WSNs is highly dependent on fault diagnosis in WSNs (Section 4.2). In this section, we characterize the FT parameters by exploiting the synergy between fault detection and FT in WSNs. The FT parameters leveraged in our Markov model are the coverage factor and sensor failure rate.

4.4.1.1 Coverage Factor

The coverage factor is defined as the probability that the faulty active sensor is correctly diagnosed, disconnected, and replaced by a good inactive spare sensor. The estimation is critical in an FT WSN model and can be determined by

4.5

where denotes the accuracy of the fault detection algorithm in diagnosing faulty sensors and denotes the probability of an unsuccessful replacement of the identified faulty sensor with the good spare sensor. depends on the sensor switching circuitry and is usually a constant, whereas 's estimation is challenging as different fault detection algorithms have different accuracies. We analyze different fault detection algorithms [91, 102, 103, 106] and observe that the accuracy of a fault detection algorithm depends on the average number of sensor node neighbors and the cumulative probability of sensor failure . We model with the empirical relation:

4.6

where is a function of and denotes an adjustment parameter that may correspond loosely to the desired average number of neighboring sensor nodes required to achieve a good fault detection accuracy for a given . We have derived Eq. (4.6) by experimenting with the relationship between the fault detection algorithms' parameters (i.e., the average number of sensor node neighbors), sensor failure probability, and the fault detection algorithms' accuracy. We point out that Eq. (4.6) provides a good estimate of in general for any fault detection algorithm, whereas exact for a particular fault detection algorithm can be derived from the algorithm's mathematical model. Equation (4.6) approximates the relationship between a fault detection algorithm's parameters to obtain the fault detection algorithm's accuracy (in case the accuracy is unknown). In practice, a fault detection algorithm's accuracy should be determined accurately by the algorithm's designer that would alleviate the need of using an approximation (as in Eq. (4.6)). To clarify further, we point out that our Markov models are independent of 's determination methodology and are equally applicable to any value.

4.4.1.2 Sensor Failure Rate

The sensor failure rate can be represented by exponential distribution with a failure rate of over the period [131]. The exponential distribution, which has a property of constant failure rate, is a good model for the long, flat intrinsic failure portion of the bathtub curve. The exponential distribution is applicable to a variety of practical situations since many embedded components and systems spend most of their lifetimes in the flat portion of the bathtub curve. Furthermore, any failure rate curve can be approximated by piecewise exponential distribution segments patched together. Each exponential distribution segment in the overall approximation specifies a constant failure rate over a small time unit (e.g., daily, weekly, or monthly) that is the average of the failure rates during the respective time duration. The constant failure rate assignment for each exponential distribution segment is justifiable as many natural phenomena have a constant failure rate (or occurrence rate) property (e.g., the arrival rate of cosmic ray alpha particles). The failure rate curve approximation by piecewise exponential distributions is analogous to a curve approximation by piecewise straight line segments.

The exponential model works well for the interarrival times where the total number of events in a given time period is given by the Poisson distribution. When these events trigger failures, the exponential lifetime distribution model naturally applies [132]. The cumulative distribution function (CDF) for the sensors with exponentially distributed failure rate is

4.7

where denotes the cumulative probability of sensor failure (for simplicity) and signifies the time over which is specified. Solving Eq. (4.7) for gives

4.8

4.4.2 Fault-Tolerant Sensor Node Model

As a base case, we describe an NFT sensor node Markov model (Fig. 4.4) containing one sensor (temperature sensor in this case, but the sensor type is arbitrary). The NFT sensor node model consists of two states: state 1 (good state) and state 0 (failed state). The NFT sensor node fails when the node transitions from state 1 to state 0 due to a sensor failure. The differential equations describing the NFT sensor node Markov model are

4.9

where denotes the probability that the sensor node will be in state at time , and represents the first-order derivative of . represents the failure rate of an active temperature sensor.

Solving Eq. (4.9) with the initial conditions and yields

4.10

The reliability of the NFT sensor node is

4.11

The MTTF of the NFT sensor node is

4.12

The average failure rate of the NFT sensor node is

4.13

Since sensors have comparatively higher fault rates than other components [88, 93, 94], we propose an FT duplex sensor node model consisting of one active sensor and one inactive spare sensor. Using TMR [92] for FT is a possible scenario, but we consider a duplex sensor node model to minimize the additional cost as the additive cost of spare sensors can be prohibitive for large WSNs. In addition, a duplex model limits the increase in sensor node size. We point out that our modeling methodology can be extended to sensor nodes with NMR.

In our duplex sensor node, the inactive sensor becomes active only once the active sensor is declared faulty by the fault detection algorithm. We refer to our duplex sensor node as an FT sensor node, whose Markov model is depicted in Fig 4.5. The states in the Markov model represent the number of good sensors. The differential equations describing the FT sensor node Markov model are

4.14

where denotes the probability that the sensor node will be in state at time and represents the first-order derivative of . represents the failure rate of an active temperature sensor and is the rate at which recoverable failure occurs. The probability that the sensor failure cannot be recovered is and the rate at which unrecoverable failure occurs is .

Solving Eq. (4.14) with the initial conditions , , and yields

4.15

The reliability of the FT sensor node is

4.16

where subscript in stands for duplex. The MTTF of the FT sensor node is

4.17

The average failure rate of the FT sensor node depends on (since the fault detection algorithm's accuracy depends on (Section 4.4.1)):

4.18

where and denote the failure rate and MTTF of an FT sensor node with neighbors.

4.4.3 Fault-Tolerant WSN Cluster Model

A typical WSN consists of many clusters (Fig. 4.1), and we assume for our model that all nodes in a cluster are neighbors to each other (could be one-hop or two-hop neighbors depending on the topology). We note that our model does not impose any specific topology on a sensor network cluster. If the average number of nodes in a cluster is , then the average number of neighboring nodes per sensor node is . Figure 4.6 depicts our Markov model for a WSN cluster. We assume that a cluster fails (i.e., fails to perform its assigned application task) if the number of alive (nonfaulty) sensor nodes in the cluster reduces to . The differential equations describing the WSN cluster Markov model are

4.19

where , , and represent the FT (duplex) sensor node failure rate (Eq. (4.18)) when the average number of neighboring sensor nodes are , , and , respectively. For mathematical tractability and closed-form solution, we analyze a special (simple) case when , which reduces the Markov model to three states (Fig. 4.7). The differential equations describing the WSN cluster Markov model when are

4.20

Solving Eq. (4.20) with the initial conditions , , and yields

4.21

where denotes in Eq. (4.21) for conciseness. The reliability of the WSN cluster is

4.22

The MTTF of the WSN cluster is

4.23

where denotes in Eq. (4.23) for conciseness. The average failure rate of the cluster depends on the average number of nodes in the cluster at deployment time:

4.24

where denotes the MTTF of a WSN cluster of sensor nodes.

4.4.4 Fault-Tolerant WSN Model

A typical WSN consists of clusters where denotes the total number of sensor nodes in the WSN and denotes the average number of nodes in a cluster. Figure 4.8 depicts our WSN Markov model. We assume that the WSN fails to perform the WSN's assigned task when the number of alive clusters reduces to . The differential equations describing the WSN Markov model are

4.25

where represents the average cluster failure rate (Eq. (4.24)) when the cluster contains sensor nodes at deployment time. For mathematical tractability, we analyze a special (simple) case when , which reduces the Markov model to three states. The differential equations describing the WSN Markov model when are

4.26

Solving Eq. (4.26) with the initial conditions , , and yields

4.27

The WSN reliability is

4.28

The WSN MTTF when is

4.29

Discussion: Our hierarchical Markov modeling exploits the relationship between failure rates at the sensor component, sensor node, WSN cluster, and WSN levels. Markov modeling of sensor nodes (Section 4.4.2) takes the failure rate of the sensor node's components (e.g., temperature sensor) as input and then derives the failure rate of the sensor node (for simplicity, the failure rate of one component is considered for illustration; however, the failure rates of different components can be considered or combined into a single representative failure rate).

For an FT sensor node model (e.g., duplex sensor node or triple modular redundant sensor node), the average failure rate of the FT sensor node implicitly depends on since the fault detection algorithm's accuracy depends on (Sections 4.3 and 4.4.1.1). Hence, the failure rate of an FT sensor node is calculated for different values in our numerical results (Section 4.6). The WSN cluster Markov model relies on the failure rates calculated from the FT sensor node Markov model for different values of . For example, for a cluster with sensor nodes (Fig. 4.6) and assuming each sensor node has all other sensor nodes in the cluster as neighbors, the number of neighboring sensor nodes for a given sensor node is . Thus, the failure rate of an FT sensor node is calculated from the sensor node Markov model with , which is then used in the WSN cluster Markov model (Fig. 4.6). When a sensor node fails, the remaining operational (healthy) neighboring nodes of a given sensor node in a cluster become ; thus, the failure rate of an FT sensor node is calculated from the sensor node's Markov model with and so on. The cluster becomes nonoperational when the number of operational sensor nodes in the cluster reaches a minimum and consequently the overall failure rate of a WSN cluster with sensor nodes is calculated for that .

The WSN cluster failure rate with sensor nodes obtained from the WSN cluster Markov model is then used in the WSN Markov model (Section 4.4.4). The WSN is assumed to be consisting of clusters and WSN becomes nonoperational when the number of alive (operational) clusters reduces to . The WSN Markov model is then used to calculate the MTTF and reliability of a given WSN using the cluster failure rate calculated from the WSN cluster Markov model.

4.5.1 Using ns2 to Simulate Faulty Sensors

In prior work, the Chen and Ding algorithms were simulated strictly algorithmically using simplified fault models that approximated a Poisson process. To compare these two models as realistically as possible, we use ns2 [101], which is a widely used discrete event simulator for both wired and wireless networks, and a custom fault model. ns2 allows us to see how these algorithms perform atop a detailed network stack over a wireless channel. We have leveraged ns2 instead of ns3 as ns2 provides better support for WSN and mobile ad hoc network (MANET) protocols [133].

Wireless entities in ns2 are called nodes and have modules called agents representing network layers stacked atop the nodes. Agents are typically used to generate application traffic, but we use agents as a fault detection unit in a sensor node (Fig. 4.9). The agent first receives scheduled, scripted commands to read values from a SensorNodeData module. The SensorNodeData module generates random sensor readings based on our implemented fault models.

After recording a data sample, the sensor node broadcasts the data as a packet and builds a record of each broadcasted packet that the sensor node receives from other sensor nodes. After a listening period, a separately scheduled event commands the detection agent to apply the two fault detection algorithms (i.e., the Ding and Chen algorithms). A fault tracker unit records statistics of detected and undetected errors. In the case of the Chen algorithm, each round of tendency broadcasting occurs in two-second intervals. The sensor readings are also broadcasted similarly in two-second intervals.

A duplex configuration was implemented for permanent errors. When a sensor node passes a threshold of detected errors, the sensor “fails” and is replaced by a spare sensor. For the simplified fault model, this replacement helps little because Poisson events are memoryless, and a sensor node with a new sensor and a sensor node with an old sensor will have the same error rate. However, for realistic data, constant errors are permanent and are repaired when the sensor is replaced. The realistic data usage also results in a penalty of false positives and causes more sensor nodes to be identified as faulty. The following sections describe our experiments with both simulated and real-world data.

4.5.2 Experimental Setup for Simulated Data

To compare the performance of each algorithm, it is useful to observe each algorithm using a simplified fault model; thus, we consider the scenario used by Chen et al. [90]. Each sensor records a uniformly random temperature between 70 and 75. Errors occur as a Poisson process, with an arbitrary, scalable mean, and corrupt a single sensor on a single sensor node during the event. A corrupted sample is randomly distributed between 100 and 105. We simulate each sensor node for 4 h and take samples every 30 s.

Fig. 4.10(a) and (b) depicts the detection performance of the Chen algorithm across different parameters and error rates. We observe that for the Chen algorithm, the error rate affects detection performance significantly; however, the value has a relatively minor impact. Fig. 4.11(a) and (b) depicts the detection performance of the Ding algorithm across different parameters and error rates. For the Ding algorithm, as is scaled, the number of false positives scales proportionately. For both algorithms, low error rates improve detection accuracy as low error rates make errors more distinguishable. In the simulated data scenario, the Chen algorithm performs better than the Ding algorithm in terms of the percentage of false positives, and the detection accuracy is relatively less dependent on . However, this simulated scenario is very specific and consistent, which may not always be the case.

4.5.3 Experiments Using Real-World Data

Since transient faults are manifested in different ways, a more realistic error model that closely follows a real-world scenario is desirable for analysis. For our real-world data case study, we leverage publicly available sensor data from the Intel Berkeley Research Laboratory [134]. The data comes from an indoor sensor network deployment that measures temperature, humidity, and other metrics. Using temperature data from 53 sensor nodes, we have produced a variety of empirical observations on which we have based our simulation.

We note a few empirical observations from the Intel Berkeley data. One observation is that the real-world data includes noise. Noise in sensor readings is correlated with past values (autocorrelated) and can have high power levels for certain time periods. To measure the effect of noise on sensor data, we apply a denoising filter available in the MATLAB Wavelet toolkit to the Intel Berkeley data to approximate a reference “noise-free” signal. We measure the power level of noise in the data (Fig. 4.12) and record the values in a text file. We play back the recorded noise power level values during simulation, and multiply the noise values with simulated white Gaussian noise to imitate the bursty behavior of noisy faults.

Another observation from the Intel Berkeley data is that for nearly all sensor nodes, sensor samples level off as they approach their end-of-life, resulting in a “constant” fault. A histogram of the times at which this occurs (Fig. 4.13) reveals that the distribution of sensor node lifetimes fits well into a Student's -distribution, which is supported by MATLAB's distribution fitting tools. For our experiments, we have recorded a set of several thousand random numbers fitting the Student's -distribution. The sensor nodes then randomly select a value from the recorded -distribution values to select a time for the fault occurrence.

Finally, we observe that voltage spikes are not frequent in the Intel Berkeley data set, occurring in only 6 out of 53 nodes. Because of the rare occurrence of voltage spikes, our simulations inject a spike once during the lifetime of each sensor node. The time of the spike occurrence is modeled using a uniform process. The base signal is a sine wave with a period of 2 h between 20 and 30 C. To allow minor variations in temperature readings sensed by sensor nodes, the temperature values are treated as being generated from a radiating heat source. The nodes furthest from the center have a lower temperature proportional to the inverse of the distance squared as in the free space path loss model. The noise and spike errors are added to the signal, and the constant fault causes the signal to hang at the signal's last valid value during an error. A signal is considered erroneous if the variation is more than half a degree from the signal's true value. In our experiments, the faulty signals are never repaired unless faults accumulate, and ultimately the sensor is replaced if diagnosed as faulty.

Figure 4.14 shows the performance of the Chen algorithm for the real-world data. Despite detecting over 90% of the faults in the simplified model, the algorithm fails to perform well with the real-world data, detecting fewer than 50% of erroneous readings. The poor performance of the Chen algorithm on the real-world data is due to the nature of the algorithm. For an error to be detected, the error must be not only disruptive, causing a node to have different values from the node's neighbors, but also transient and have a sharp transition boundary. Since noise events last for multiple samples, the Chen algorithm is not equipped to handle these errors.

The Ding algorithm's performance with real-world data is shown in Fig. 4.15. Similar to the Chen algorithm, the Ding algorithm's performance degrades as compared to the previous simplified model environment. However, the Ding algorithm still detects a majority of occurring faults. As with the previous simplified model experiment, the Ding algorithm is highly dependent on the algorithm's parameters. The higher the detection rate is, the higher the rate of false positives is for the Ding algorithm; however, the false positive rate remains low, peaking at 20%.

4.6.1 Experimental Setup

In this section, we describe our FT sensor node, WSN cluster, and WSN model implementation in the SHARPE Software Package [135, 136]. We also present a typical fault detection algorithm's accuracy for different cumulative sensor failure probability values. Owing to SHARPE limitations that take only exponential polynomials, we assume our sensor failure rate to be exponentially distributed (Section 4.4.1.2).

SHARPE is a software tool for performance, reliability, and performability model specification and analysis. The SHARPE toolkit provides a specification language and solution methods for commonly used performance, reliability, and performability model types. Supported models of SHARPE include combinatorial models, state-space (e.g., Markov and semi-Markov reward models), and stochastic Petri nets. SHARPE allows computation of steady-state, transient, and interval measures. SHARPE allows output measures of a model to be used as parameters of other models to facilitate the hierarchical combination of different model types.

Our Markov model exploits the synergy of fault detection and fault tolerance for WSNs. Table 4.3 depicts values estimated for a DFD algorithm using Eq. (4.6) for different and values. These estimated values approximate the accuracy of the DFD algorithms proposed in [91, 102, 103, 106]. We note that any inaccuracy in the estimation does not affect our calculations of results because these calculations leverage values but are independent of whether these values reflect accurately a particular DFD algorithm's accuracy. We assume in Eq. (4.5) (i.e., once a faulty sensor is identified, the faulty sensor is replaced by a good spare sensor perfectly), which gives in Eq. (4.5).

		5	6	7	10	15
0.05	25	0.979	1	1	1	1
0.1	50	0.858	0.895	0.921	0.957	0.96
0.2	56	0.755	0.717	0.81	0.845	0.851
0.3	65	0.652	0.679	0.699	0.732	0.742
0.4	66	0.558	0.5813	0.599	0.627	0.636
0.5	67	0.464	0.484	0.498	0.522	0.53
0.6	68	0.371	0.386	0.398	0.417	0.424
0.7	69	0.278	0.29	0.298	0.313	0.318
0.8	70	0.185	0.193	0.198	0.208	0.212
0.9	71	0.092	0.096	0.099	0.104	0.106
0.99	72	0.0092	0.00962	0.0099	0.0104	0.0106

4.6.2 Reliability and MTTF for an NFT and an FT Sensor Node

In this section, we present the reliability and MTTF results for an NFT and an FT sensor node for the two cases: and , when and . The case corresponds to a real-world fault detection algorithm (typical values are shown in Table 4.3), whereas the case corresponds to an ideal fault detection algorithm, which detects faulty sensors perfectly for all values. We calculate reliability at days since we assume days [137] in Eq. (4.8); however, we point out that reliability can be calculated for any other time value using our Markov models.

For an NFT sensor node reliability calculation, we require the sensor failure rate , which can be calculated using Eq. (4.8) (i.e., failures/day). SHARPE gives and sensor node reliability . Evaluating at gives = 0.94999.

For an FT sensor node when , different reliability results are obtained for different because the fault detection algorithm's accuracy and coverage factor depend on . For , (Table 4.3), SHARPE gives = and = . The reliability = , which when evaluated at = 100 gives = 0.99770. For an FT sensor node when for all , SHARPE gives and . Using Eq. (4.16), the reliability = 0.99872.

Table 4.4 shows the reliability for an NFT and an FT sensor node evaluated at days for values of 5, 10, and 15. As expected, the results show that reliability decreases for both NFT and FT sensor nodes as increases, and the reliability attained by an FT sensor node (both for and ) is always better than an NFT sensor node. For example, the percentage reliability improvement achieved by an FT sensor node with , over an NFT sensor node is 18.98% when . However, an FT sensor node with outperforms both an FT sensor node with and an NFT sensor node for all values. For example, the percentage improvement in reliability for an FT sensor node with over an NFT sensor node is 69.09%, and the percentage improvements in reliability for an FT sensor node with over an FT sensor node () with equal to 5, 10, and 15 are 28.11%, 24.32%, and 23.82%, respectively, for . The percentage improvement in reliability attained by an FT sensor node with over an NFT sensor node is 230%, and the percentage improvements in reliability for an FT sensor node with over an FT sensor node () with equal to 5, 10, and 15 are 172.36%, 166.31%, and 165.32%, respectively, for . These results reveal that the percentage improvement in reliability attained by an FT sensor node with increases as because for an FT sensor node with , decreases as (Table 4.3). The sensor node reliability analysis reveals that a robust fault detection algorithm with for all and values is necessary to attain good reliability for an FT sensor node.

Probability	NFT	FT	FT	FT	FT
0.05	0.94999	0.99770	0.99872	0.99872	0.99872
0.1	0.89996	0.98135	0.99074	0.99102	0.99482
0.2	0.80011	0.93481	0.95088	0.95195	0.97853
0.3	0.69977	0.86265	0.88263	0.88513	0.94959
0.4	0.59989	0.77094	0.79209	0.79485	0.90643
0.5	0.5007	0.66086	0.68097	0.68374	0.84662
0.6	0.40012	0.53610	0.55295	0.55552	0.76663
0.7	0.30119	0.40167	0.41432	0.41612	0.66262
0.8	0.19989	0.25943	0.26683	0.26812	0.52171
0.9	0.10026	0.12148	0.12424	0.12470	0.33086
0.99	0.01005	0.01048	0.01053	0.01056	0.05628

Figure 4.16 depicts the MTTF for an NFT and an FT sensor node for values of 5, 10, and 15 versus the sensor failure probability when in Eq. (4.7) is 100 days [91, 106]. The results show that the MTTF for an FT sensor node improves with increasing . However, the MTTF shows negligible improvement when over as the fault detection algorithm's accuracy improvement gradient (slope) decreases for large values.

Figure 4.16 also compares the MTTF for an FT sensor node when . When for existing fault detection algorithms, comparison with provides insight into how the fault detection algorithm's accuracy affects the sensor node's MTTF. Figure 4.16 shows that the MTTF for an FT sensor node with is always greater than an FT sensor node with .

Figure 4.16 shows that the MTTF for an NFT and an FT sensor node decreases as increases; however, the FT sensor node maintains better MTTF than the NFT sensor node for all values. This observation reveals that a sensor with a lower failure probability achieves better MTTF for both the NFT and FT sensor nodes. Figure 4.16 also shows that the MTTF for both the NFT and the FT sensor nodes approaches zero as approaches 1 (i.e., MTTF 0 1). This observation is intuitive because a faulty sensor (with ) is unreliable and leads to a failed sensor node with zero MTTF and suggests that depending on the application's reliability and MTTF requirements, the faulty sensor should be replaced before approaches 1.

Table 4.5 depicts the percentage MTTF improvement gained by an FT sensor node over an NFT sensor node for different values of . We calculate the percentage improvement as . The table shows that the MTTF percentage improvement for an FT sensor node decreases as increases when . The percentage MTTF improvement for an FT sensor node with and are 85.75% and 95.65%, respectively, for and drops to 0.875% and 1.34%, respectively, for . This observation reveals that having more neighboring sensor nodes (a higher value) improves MTTF because, in general, a fault detection algorithm's accuracy and improve with increasing . Table 4.5 also shows that the MTTF percentage improvement for an FT sensor node over an NFT sensor node is 100% on average when , thus highlighting the importance of a robust fault detection algorithm.

Probability	FT	FT	FT
0.1	85.75	95.65	100
0.2	75.61	84.63	100
0.3	65.14	72.99	100
0.5	46.25	52.49	100
0.7	27.62	31.23	100
0.9	9.37	10.52	100
0.99	0.875	1.34	100

Model Validation: We compare the MTTF results for an NFT sensor node obtained using our Markov model with other existing models in the literature as well as practical sensor node implementations to provide insights into the accuracy of our models. We note that a detailed comparison and verification of our model with existing models is not possible because there are no similar/related models that leverage FT constructs. Jung et al. [71] modeled the lifetime of trigger-driven sensor nodes with different event arrival rates (trigger-driven sensor nodes perform processing based on events as opposed to duty-cycle-based sensor nodes that perform processing based on a duty cycle), which can be interpreted as sensing events that depend on the sensor node's sensing frequency. Results were obtained for three trigger-driven sensor node platforms: XSM, MICAz, and Telos. XSM and MICAz consisted of an ATmega128L 8-bit processor with a maximum processor frequency of 16 MHz and a maximum performance of 16 million instructions per second (MIPS). Telos consisted of a TI MSP430 16-bit processor with a maximum processor frequency of 8 MHz and a maximum performance of 16 MIPS. Results revealed that Telos, XSM, and MICAz delivered lifetimes of 1500, 1400, and 600 days, respectively, with an event arrival rate of 0.1 events/h, which dropped to 350, 100, and 0 days, respectively, with an event arrival rate of 100 events/h. The lifetime values for an NFT sensor node obtained from our Markov model ranges from 949 to 22 days for different sensor failure probabilities. Depending on the sensor node energy consumption, the lifetime model proposed in [70] estimated that the sensor node lifetime varied from 25 to 215 days. These comparisons indicate that our Markov model yields sensor node lifetime values in the range obtained from other existing models.

We also compare the NFT sensor node lifetime estimation from our model with an experimental study on sensor node lifetimes [74]. This comparison verifies conformity of our model with real measurements. For example, with a sensor node battery capacity of 2500 mA h, experiments indicate a sensor node lifetime ranging from 72 to 95 h for a 100% duty cycle for different battery brands (e.g., Ansmann, Panasonic Industrial, Varta High Energy, Panasonic Extreme Power) [74]. The sensor node lifetime for a duty cycle of 18% can be estimated as 95/0.18 = 528 h 22 days and for a duty cycle of 0.42% as 95/0.0042 = 22,619 h 942 days. This comparison reveals that our NFT sensor node lifetime model estimates lifetime values in the range obtained by experimental sensor node implementations.

4.6.3 Reliability and MTTF for an NFT and an FT WSN Cluster

In this section, we present the reliability and MTTF results for two WSN clusters that contain on average and sensor nodes at deployment time (). The selection of two different values provides insight into how the size of the cluster affects reliability and MTTF (other and values depicted similar trends). The NFT WSN cluster consists of NFT sensor nodes and the FT WSN cluster consists of FT sensor nodes. For brevity, we present example WSN cluster reliability calculations for () and .

Leveraging our bottom-up approach model, the NFT WSN cluster uses the failure rate of an NFT sensor node. By using Eq. (4.8), = failures/day. Since the coverage factor does not appear in the reliability (and MTTF) calculation for an NFT sensor node, the failure rate = = = failures/day. In other words, for an NFT sensor node, = , , and = , which denote the sensor node failure rate when the average number of neighboring sensor nodes are 4 and 5, respectively. The NFT WSN cluster reliability calculation utilizes and , which gives = and = . The reliability = + , which when evaluated at days gives .

For an FT WSN cluster when , the reliability calculation requires and , which depends on as the fault detection algorithm's accuracy and depends on , yielding different reliability results for different values. Using Table 4.3 and Eq. (4.18), = = = = failures/day and = = = = failures/day. SHARPE gives = and . The reliability of the FT WSN cluster is calculated as = 0.95969.

For an FT WSN cluster when , the reliability calculation does not depend on , which gives failures/day and failures/day. SHARPE gives and , from which we calculate .

Table 4.6 shows the reliability for an NFT and an FT WSN cluster (for and ) evaluated at days when (). We observe similar trends as with sensor node reliability (Table 4.4) where the reliability of both NFT and FT WSN clusters decreases as increases (i.e., reliability ) because decreased individual sensor node reliability decreases the overall WSN cluster reliability. Table 4.6 depicts that an FT WSN cluster with outperforms an FT WSN cluster with and an NFT WSN cluster for all values. For example, the percentage improvement in reliability for an FT WSN cluster with over an NFT WSN cluster and an FT WSN cluster with is 77.33% and 12.02% for and 601.12% and 142.73% for , respectively. These results show that the percentage improvement in reliability attained by an FT WSN cluster increases as increases because a fault detection algorithm's accuracy and decrease as increases (Table 4.3). This trend is similar to the percentage improvement in reliability for an FT sensor node (Section 4.6.2). The results show that an FT WSN cluster always performs better than an NFT WSN cluster. For example, the percentage improvement in reliability for an FT WSN cluster with over an NFT WSN cluster is 58.31% for .

	NFT	FT	FT
0.05	0.96720	0.99058	0.99098
0.1	0.88562	0.95969	0.96552
0.2	0.65567	0.84304	0.87474
0.3	0.41968	0.66438	0.74422
0.4	0.23309	0.45925	0.59388
0.5	0.10942	0.26595	0.43653
0.6	0.04098	0.11837	0.28732
0.7	0.01114	0.03548	0.16279
0.8			0.06723
0.9			0.01772
0.99

Figure 4.17 depicts the MTTF for an NFT WSN cluster and an FT WSN cluster versus when for average cluster sizes of and sensor nodes, respectively, at deployment time. The figure reveals that the FT WSN cluster's MTTF is considerably greater than the NFT WSN cluster's MTTF for both cluster sizes. Figure 4.17 also compares the MTTF for an FT WSN cluster when with and shows that the MTTF for an FT WSN cluster with is always better than an FT WSN cluster with . This observation again verifies the significance of a robust (ideal) fault detection algorithm, which can ideally provide values close to 1 (i.e., for all values). We note that both an NFT and an FT WSN clusters with have redundant sensor nodes and can inherently tolerate sensor node failures. The WSN cluster with has more redundant sensor nodes than the WSN cluster with , resulting in a comparatively greater MTTF. Figure 4.17 shows that the MTTF for both an NFT and an FT WSN clusters approaches zero as approaches 1 and further solidifies the necessity of low failure probability sensors to achieve better MTTF in WSN clusters. The MTTF variation for a WSN cluster with varying is similar to the MTTF variation for a sensor node (Fig. 4.16) because a WSN cluster is composed of sensor nodes and reflects the MTTF variation of WSN cluster's constituent sensor nodes.

Table 4.7 shows the percentage MTTF improvement for an FT WSN cluster as compared to an NFT WSN cluster for cluster sizes of and sensor nodes. The percentage improvements are calculated separately for the two cluster sizes and we compare the MTTFs of clusters of the same size. We observe that the MTTF improvement for an FT cluster is slightly greater when as compared to when ; however, the MTTF improvement decreases with increasing when . This observation reveals that a WSN cluster consisting of more sensor nodes can achieve better MTTF improvements when compared to a WSN cluster containing fewer sensor nodes. The MTTF percentage improvement for an FT WSN cluster with , , is 83.04% for and drops to 2.26% for . Similarly, the percentage MTTF improvement for an FT WSN cluster with , , is 87.55% for and drops to 2.47% for . The percentage MTTF improvement for both cluster sizes is 100% on average when (results are not shown for when in Table 4.7 for brevity). We observed that the MTTF percentage improvement for an FT WSN cluster with over is 103.35% on average. Intuitively, these results confirm that clusters with more redundant sensor nodes are more reliable and have a better MTTF than clusters with fewer redundant sensor nodes.

Probability	FT	FT	FT
0.1	83.04	87.55	100
0.2	73.84	77.24	100
0.3	63.58	66.51	100
0.5	44.97	47.22	100
0.7	26.4	28.71	100
0.9	9.81	9.57	100
0.99	2.26	2.47	100

Since SHARPE provides information on MTTF directly from Markov models whereas reliability calculation requires manual substitution in state transition probabilities, we present iso-MTTF results for WSN clusters. Table 4.8 depicts the MTTFs for an FT WSN cluster and an NFT WSN cluster for varying from 0.1 to 0.99 and when = 4. Results indicate that an NFT WSN cluster requires three redundant NFT sensor nodes to achieve a comparable MTTF as that of an FT WSN cluster.

Probability	MTTF FT (days)	MTTF NFT (days)	NFT
0.1	695.89	707.43	3
0.3	205.3	208.86	3
0.5	105.97	107.6	3
0.7	61.213	62.136	3
0.99	15.942	16.209	3

4.6.4 Reliability and MTTF for an NFT and an FT WSN

This section presents the reliability and MTTF results for an NFT WSN and an FT WSN containing and clusters at deployment time (). We consider WSNs containing different number of clusters to provide an insight into how the number of clusters affects WSN reliability and MTTF (other and values depicted similar trends). The FT WSN contains FT sensor nodes, and the NFT WSN contains NFT sensor nodes. We present example WSN reliability calculations for (, i.e., each WSN fails when there are no more active clusters) and = 0.2. We assume that both WSNs contain clusters with () = 9 sensor nodes on average with a cluster failure rate .

The reliability calculation for an NFT WSN requires the NFT WSN cluster failure rate , which can be calculated using Eq. (4.24) with (i.e., = failures/day). Using , SHARPE gives and . The WSN reliability when evaluated at days gives .

For an FT WSN when , the reliability calculation requires the FT WSN cluster failure rate (for ) (i.e., failures/day). Using , SHARPE gives , . The WSN reliability .

For an FT WSN cluster when , the reliability calculation requires the FT WSN cluster failure rate (for ) (i.e., failures/day). Using , SHARPE gives , , which gives .

Table 4.9 shows the reliability for an NFT WSN and an FT WSN evaluated at days when () for clusters with nine sensor nodes on average. We observe similar trends as with sensor node reliability (Table 4.4) and WSN cluster reliability (Table 4.6) where reliability for both an NFT WSN and an FT WSN decreases as increases (i.e., reliability ) because a WSN contains clusters of sensor nodes and decreased individual sensor node reliability, with increasing decreases both WSN cluster and WSN reliability. Table 4.9 shows that an FT WSN with outperforms an FT WSN with and an NFT WSN for all values. For example, the percentage improvement in reliability for an FT WSN with over an NFT WSN and an FT WSN with is 5.1% and 0.51% for and 350.18% and 236.22% for , respectively. These results show that the percentage improvement in reliability attained by an FT WSN increases as increases because the fault detection algorithm's accuracy and decreases as increases (Table 4.3). This trend is similar to the percentage improvement in reliability for an FT sensor node (Section 4.6.2) and an FT WSN cluster (Section 4.6.3). The results show that an FT WSN always performs better than NFT WSN. For example, the percentage improvement in reliability for an FT WSN with over an NFT WSN is 4.57% for .

	NFT	FT	FT
0.05	0.99557	0.99883	0.99885
0.1	0.98261	0.99474	0.99534
0.2	0.93321	0.97583	0.98084
0.3	0.85557	0.93775	0.95482
0.4	0.75408	0.87466	0.91611
0.5	0.63536	0.78202	0.86218
0.6	0.51166	0.65121	0.78948
0.7	0.36303	0.49093	0.69527
0.8	0.20933	0.30328	0.55494
0.9	0.08807	0.11792	0.39647
0.99			0.08807

Figure 4.18 depicts the MTTF for an NFT WSN and an FT WSN containing on average and clusters () at deployment time. The figure reveals that an FT WSN improves the MTTF considerably over an NFT WSN for both number of clusters. Figure 4.18 also shows that the MTTF for an FT WSN when is always greater than the MTTF for an FT WSN when . We observe that since the MTTF for an FT WSN drops nearly to that of an NFT WSN as , building a more reliable FT WSN requires low failure probability sensors. This WSN MTTF variation with follows similar trends as observed in WSN clusters (Fig. 4.17) and sensor nodes (Fig. 4.16). Similar MTTF variations for a WSN, WSN cluster, and a sensor node results from our bottom-up modeling approach (Section 4.4), where each hierarchical level captures the MTTF variation trends of lower levels. We observe that the MTTF for a WSN with is always greater than the MTTF for a WSN with . This observation is intuitive because WSNs with have more redundant WSN clusters (and sensor nodes) and can survive more cluster failures before reaching the failed state () as compared to a WSN with .

We observe the percentage MTTF improvement for an FT WSN over an NFT WSN containing on average and clusters. We observe that the MTTF improvement for both number of clusters decreases with increasing when (similar trend as for a WSN cluster and for a sensor node). The MTTF percentage improvement for an FT WSN with , , is 87.56% for and drops to 3.3% for . Similarly, the MTTF percentage improvement for an FT WSN with , , is 88.2% for and drops to 3.26% for . We observe that the MTTF improvement for an FT WSN with is 100% on average for all values and is greater than an FT WSN with . The MTTF percentage improvement for an FT WSN with over an FT WSN with is 52.22% on average.

We also investigate iso-MTTF for WSNs. Table 4.10 depicts the MTTFs for an FT WSN and an NFT WSN for varying from 0.1 to 0.99 and when = 0. Results indicate that an NFT WSN requires nine redundant NFT WSN clusters to achieve a comparable MTTF as that of an FT WSN.

Probability	MTTF FT (days)	MTTF NFT (days)	NFT
0.1	2121.6	2135.7	9
0.3	627.62	631.77	9
0.5	323.28	326.12	9
0.7	186.8	188.74	9
0.99	48.387	48.71	9

4.7.1 Accurate Fault Detection

Our Markov modeling results in Section 4.6 reveal that the fault detection algorithm's accuracy plays a crucial role in realizing FT WSNs. An accuracy close or equal to 100% and a false alarm rate close or equal to 0% is desirable for fault detection algorithms. There is a need to develop novel fault detection algorithms and/or improve the existing fault detection algorithms with the objective of attaining 100% fault detection accuracy.

4.7.2 Benchmarks for Comparing Fault Detection Algorithms

There is a need to develop standard benchmarks for comparing different fault detection algorithms for various fault models and topologies. The development of these benchmarks would facilitate designers to select an appropriate fault detection algorithm for WSNs with given FT requirements.

4.7.3 Energy-Efficient Fault Detection and Tolerance

Since sensor nodes have stringent resource constraints, fault detection and FT approaches for WSNs need to be energy efficient. Although initiatives have been taken in developing DFD approaches to minimize energy overhead, the area requires further research. Moreover, FT techniques developed for WSNs need to be energy efficient. The impact of added redundancy in sensor nodes to provide FT not only has economic cost overhead but can also have power consumption overhead, which needs to be considered and minimized during the design. Energy efficiency in fault detection and tolerance can also be achieved by exploiting near-threshold computing (NTC) in sensor node design. NTC refers to using a supply voltage () that is close to a single transistor's threshold voltage (generally is slightly above in near-threshold operation, whereas is below for subthreshold operation). Lowering the supply voltage reduces power consumption and increases energy efficiency by lowering the energy consumed per operation. The widespread adoption of NTC in sensor node designs for reduced power consumption requires addressing NTC challenges such as increased process, voltage, and temperature variations, subthreshold leakage power, and soft error rates.

4.7.4 Machine-Learning-Inspired Fault Detection

Machine learning-based approaches can be leveraged to classify normal and anomalous data. Since sensor nodes are resource constrained, innovative approaches are required to extract features from the sensed data. The machine learning techniques for sensor nodes need to reduce the training data size for the classifier (e.g., SVM) based on extracted features. The goal of machine-learning-inspired fault detection is to classify normal and anomalous data in or near real time. There exist some initiatives in machine-learning-inspired fault detection [110]; however, further work is required in this domain for accurate and energy-efficient fault detection.

4.7.5 FT in Multimedia Sensor Networks

Fault detection and tolerance in WMSNs is a relatively new research field [115]. FT data aggregation in WMSNs is imperative to reduce the throughput of data transmission, energy conservation, accuracy of event detection, and alleviate the interference from compromised nodes. Another research challenge in WMSNs is to ensure the trustworthiness of aggregated results. Since multimedia data sensed by sensor nodes require compute-intensive processing, multicore-based design of sensor nodes could meet the performance, energy, and FT requirements of WMSNs. Accurate fault detection, FT, reliability, and security in WMSNs require further research endeavors.

4.7.6 Security

Security is critical for many WSNs, such as military target tracking and biomedical applications. Security aspects are crucial to consider in developing a reliable, robust, and trustworthy WSNs. Since sensor nodes use wireless communication, WSNs are susceptible to eavesdropping, message injection, replay, and other attacks. In many situations, an adversary is capable of deploying malicious nodes in the WSN or compromising some legitimate sensor nodes. Since the sink node is a gateway between a WSN and the outside world, compromising the sink node could render the entire WSN useless. Hence, security integration in sink nodes is imperative. The security integration objective in WSNs is to provide confidentiality, integrity, authenticity, and availability of all messages in the presence of adversaries. In a secure and reliable WSN, every eligible receiver should receive all messages intended for that receiver. Furthermore, the receiver should be able to verify the integrity of each message as well as the identity of the sender.

Integration of security and privacy in sensor nodes is challenging because of the sensor nodes' resource constraints in terms of computation, communication, memory/storage, and energy supply. The security mechanisms for prevalent end-to-end systems (e.g., secure socket layer (SSL)) are not directly applicable to WSNs. In traditional end-to-end systems, it is neither necessary nor desirable for the contents of the message (except the message headers) to be available to the intermediate routers. On the contrary, in WSNs, the dominant traffic pattern is many-to-one (i.e., from sensor nodes to the sink node) [138]. Each intermediate sensor node in a WSN also needs access to message contents to perform in-network processing, such as data aggregation and data compression, to conserve energy. Security incorporation in WSNs has several aspects, some of which are discussed below.

Time Synchronization: Due to the collaborative nature of sensor nodes, secure time synchronization is important for various WSN operations, such as coordinated sensing tasks, sensor scheduling, target tracking, data aggregation, and time division multiple access (TDMA) medium access control. The network time protocol (NTP), which is used for synchronization in the Internet, cannot be directly used by WSNs due to a sensor node's constrained resources. Sometimes, synchronization protocols for WSNs have been proposed in the literature such as reference-broadcast synchronization (RBS) [139] and timing-sync protocol for sensor networks (TPSN) [140]; however, security is not considered in the design of these synchronization protocols.

Sensor Location Discovery: Sensor node location is important for many WSN applications, such as target tracking and environmental monitoring. The geographical routing protocols developed for WSNs also require sensor node location information to make routing decisions. Sensor location discovery protocols make use of special nodes known as beacon nodes, which are assumed to know their own location via global positioning system (GPS) or manual configuration. Nonbeacon nodes receive radio signals (reference signals) from beacon nodes. These reference signals contain the location of beacon nodes. The nonbeacon nodes then determine their own location based on features of the reference messages, such as using received signal strength indicator (RSSI). Without any protection, the adversary has the potential to mislead the location estimation at sensor nodes. For example, an attacker may provide incorrect location references by replaying the beacon signals intercepted in different locations. A more serious attack launched by an adversary could be compromising a beacon node and distributing malicious location references by manipulating the beacon signals (e.g., changing the signal strength if RSSI is used to estimate the distance). In the presence of such attacks, nonbeacon nodes will determine their location incorrectly. There are a few methods to counter these attacks and to increase the reliability and trustworthiness of WSN. For instance, voting-based location references use voting of different received location references from different beacon nodes; however, this technique would increase the cost of the WSN as the approach would require more beacon nodes equipped with GPS.

Secure Routing: An adversary can also impact routing within a WSN, which consequently degrades the reliability of the WSN. Secure routing protocols for MANETs or wired networks are not suitable for WSNs because these protocols are computationally expensive and are meant for routing between any pair of nodes and not for the many-to-one traffic pattern prevalent in WSNs.

Intrusion Detection: Most of the existing WSNs are designed without considering security and intrusion detection. WSNs are more prone to malicious intruders as compared to traditional wired networks due to an open medium, a low degree of physical security, the dynamic topology, and a limited power supply. Security vulnerabilities in WSNs can be alleviated using an intrusion detection system (IDS). Intrusion detection is a security technology that attempts to identify those who are trying to break into and misuse a system without authorization as well as those who have legitimate access to the system but are abusing their privileges [141]. By modeling the behavior of normal sensor node activities and operations, an IDS can identify potential intruders and maintain trustworthy operation of a WSN. IDSs are of two types: misuse-based detection and anomaly-based detection. A misuse-based IDS encodes known attack signatures and vulnerabilities and stores this information in a database. An alarm is generated by the IDS if a discrepancy exists between the current activities and stored signatures. A misuse-based IDS cannot detect novel attacks because of the lack of corresponding signatures. An anomaly-based IDS creates normal profiles of sensor node behavior and compares them with current activities. If a significant deviation in a sensor node's behavior is observed, the anomaly-based IDS raises an alarm. An anomaly-based IDS can detect unknown attacks; however, developing profiles of a sensor node's normal behavior is challenging.

4.7.7 WSN Design and Tuning for Reliability

WSNs are more susceptible to failure than wired networks due to a WSN's deployment in unattended and often hostile environments. The vulnerability of sensor nodes to failures and attacks from malicious intruders requires reliability and security incorporation in the design of sensor nodes and WSNs. For instance, in the case of failures of some sensor nodes or some sensor nodes being compromised by an adversary, a WSN should be able to detect these failures and then adapt accordingly to remain operational. For example, if a few nodes are diagnosed as misbehaving or failed, routing protocol should be able to adapt to the situation and find alternative routes. This adaptation may require some sensor nodes to increase their transmission energy to get their sensed information to healthy nodes. Furthermore, the frequency of packet transmission can be reduced in such situations to conserve energy of sensor nodes to compensate for the increased transmission energy. This tuning of sensor nodes and the WSN would maintain the reliable operation of WSN although at a reduced efficiency. Moreover, the WSN manager should be alarmed of the situation to take necessary actions to increase the efficiency of the WSN, including removal of identified malicious nodes and placement of new healthy sensor nodes in the WSN.

4.7.8 Novel WSN Architectures

To maintain reliable and secure operation of WSNs in the presence of failures and malicious intruders, innovative WSN architectures are desired. For instance, a heterogeneous hierarchical multicore embedded wireless sensor network (MCEWSN) can better meet performance and reliability requirements of WSN [142]. The heterogeneity in the architecture subsumes the integration of numerous single-core embedded sensor nodes and several multicore embedded sensor nodes. A hierarchical architecture comprising of various clusters and a sink node is appropriate for large WSNs since in small WSNs, sensor nodes can send the sensed data directly to the sink node. Each cluster comprises several leaf sensor nodes and a cluster head. Leaf sensor nodes embed a single-core processor and are responsible for sensing, preprocessing, and transmitting the sensed data to the cluster head nodes. Cluster head nodes embed a multicore processor and are responsible for coalescing/fusing the data received from leaf sensor nodes for transmission to the sink node. Multicore embedded sensor nodes enable energy savings over conventional single-core embedded sensor nodes in two ways. First, multicore embedded sensor nodes reduce the energy expended in communication by performing in situ computation of sensed data and transmitting only processed information. Second, a multicore embedded sensor node permits the computations to be split across multiple cores while running each core at a lower processor voltage and frequency, as compared to a single-core system, which results in energy savings. Multicore cluster heads are also amenable for supervising a fault diagnosis algorithm within the cluster. Additionally, security primitives could be integrated in these multicore cluster heads to thwart attacks from malicious intruders or malicious sensor nodes.