Efficient Fault-Tolerant Event Query Algorithm in Distributed Wireless Sensor Networks

Abstract

To overcome the faulty data query problem to improve the accuracy of data query, an efficient fault-tolerant event query algorithm (FTEQ) is proposed, which takes the short-term and long-term spatial and temporal similarities between sensors and environment into considerations. An imprecise and missing data correction algorithm based on Kalman filter is proposed to correct fault sensing data, and a score rank algorithm also is proposed to assign each sensor an appropriate value to reflect the importance of sensors. FTEQ performs self-evaluation and cooperative evaluation schemes with its trustful r neighbor nodes to filter fault data query with the importance of sensor. Simulation results prove that FTEQ performs extremely well in terms of faulty detection rate and data query cost.

1. Introduction

The advances microprocessor and wireless techniques have enabled the deployment of large-scale sensor networks, where thousands of cheap and small sensors are spread over a vast field for applications [1]. An important application of WSNs is to monitor, detect, and report the occurrences of events of interest, such as forest fire, environment temperature, chemical spills, network health, [1, 2]. Due to the strict resource limitations (e.g., battery power, bandwidth, etc.) of sensor nodes and the nature of some events, it is not feasible to collect all sensor measurements and compute event boundaries in a centralized manner. Several previous works [3, 4] proposed declarative SQL-like query which enable users to acquire the information about the network through issuing queries to the sink. Due to the characteristics of wireless sensor networks, sensors are usually deployed in a noneasily accessible or harsh environment and sensors are prone to failure and these faulty sensors are likely to report arbitrary data very different from the true environmental phenomenon and the faulty data of sensors are very common, which greatly influences the accuracy of data query. In order to overcome the faulty data query problem, Clouqueur et al. [5] sought algorithms to collaboratively detect the presence of a target in a region. Each sensor obtains the target energy (or local decision) from all other sensors in the region, drops extreme values if faulty sensors exist, computes the average, and then compares it with a predetermined threshold for final decision. However, it assumes that faulty measurements are either much larger or much smaller than normal measurements. In [6], the performances of sensors were considered to enhance the classical majority voting (CMV). Although a number of algorithms have been proposed to provide secure discrete event detection under adversarial environments [7–9]. However, this approach cannot be applied to a large-scale event directly, since it is neither feasible nor necessary for all the nodes in the event region to report its detection back to the sink due to the stringent resource constraints in WSNs.

Motivated by the above reasons, an efficient fault-tolerant event query algorithm called FTEQ is proposed to solve the faulty data query problem. We first give the system model and formulate the similarity of sensor behaviors among sensors in terms of both spatial and temporal behaviors of sensors to model the relationships among sensors. Then a rank algorithm is proposed to assign each sensor inappropriate value to reflect the importance of sensor. Based on the rank algorithm, FTEQ performs different schemes to filter fault data query.

The rest of this paper is organized as follows. System model and a rank algorithm and FTEQ algorithm to solve the faulty data query problem are given in Section 2. Performance studies are conducted in Section 3. This paper concludes with Section 4.

2. Proposed Algorithm

2.1. System Model and Temporal Similarity

Assume that each sensor is well positioned and is aware of its own location. Generally speaking, sensors have its valid sensing data readings range. Sensing data not fallen into the range are clearly viewed as faulty readings. Both faulty readings and noise readings are considered to be filtered out so as to improve the data accuracy of query results. In addition, once sensors are identified as faulty sensors that frequently report arbitrary readings, these sensors will not be inquired any more. To truly reflect the similarity of sensor behaviors, the similarity of sensors should be considered the reading behaviors of sensors.

The sensing data reading behavior of sensor consists of a series of sensing readings within a sliding window $\mathrm{\Delta }t$ . The sensing data reading behavior of $s_i$ is expressed as

$b(s_i,t)={\displaystyle \bigcup }_{j=1-\mathrm{\Delta }t}^{0}d(s_i,t+j),$

(1)

where $d(s_i,t)$ is the reading sensed by the time t.

Note that the width of the sliding window is set to $\mathrm{\Delta }t$ for all sensors and assume that the sensing frequencies of all sensors are the same. Therefore, the behavior of a sensor is represented as a vector. Since the trends of readings of two sensors are more important, we employ the Extended Jaccard similarity function. The temporal similarity of the reading behaviors of two sensors $s_i$ and $s_j$ is expressed by $\text{Sim}(s_i,s_j,\mathrm{\Delta }t)$ and defined as follows:

$\text{Sim}(s_i,s_j,\mathrm{\Delta }t)=\frac{d(s_i,t)d(s_j,t)}{M\left(s_i\right)+M\left(s_j\right)-d(s_i,t)d(s_j,t)},$

(2)

where

$\begin{array}{c}M\left(s_i\right)={\displaystyle \sum }_{k=1}^{\mathrm{\Delta }t}{\left|d\left(s_i,t-\mathrm{\Delta }t+k\right)\right|}^2,\end{array}$

(3)

$\begin{array}{c}M\left(s_j\right)={\displaystyle \sum }_{k=1}^{\mathrm{\Delta }t}{\left|d\left(s_j,t-\mathrm{\Delta }t+k\right)\right|}^2.\end{array}$

(4)

Note that sensors are required to periodically sense data. Consequently, the reading behaviors of sensors may vary with time. The sensing readings collected recently should be more important than those occurred long time ago. The temporal similarity of environments sensed by two sensors $s_i$ and $s_j$ is generally the normalized similarity $NSim(s_i,s_j,\mathrm{\Delta }t)$ of $b_i(t)$ and $b_j(t)$ . The short-term normalized temporal similarity $\text{SNSim}(s_i,s_j,\mathrm{\Delta }t)$ is defined as

$\text{SNSim}(s_i,s_j,\mathrm{\Delta }t)=\text{NSim}(s_i,s_j,\mathrm{\Delta }t-1).$

(5)

In essence, the temporal similarity will be calculated with a fixed period. Assume that each time we calculate the temporal similarity is referred to as one round. The long-term temporal similarity of $k+1$ round $\text{LN}{\text{Sim}}_{k+1}(s_i,s_j,\mathrm{\Delta }t)$ is derived as follows:

$\begin{array}{cc}\hfill \text{LN}{\text{Sim}}_{k+1}(s_i,s_j,\mathrm{\Delta }t)& =\rho ·\text{LN}{\text{Sim}}_k\left(s_i,s_j,\mathrm{\Delta }t-1\right)\hfill \\ \hfill & \hspace{1em}+(1-\rho )·\text{SNSim}\left(s_i,s_j,\mathrm{\Delta }t\right),\hfill \end{array}$

(6)

where $\rho \in [\mathrm{0,1}]$ is an adjustable variable.

A query event will trigger the sensor reading behaviors, along with the time while the event occurred. Denote the set of related sensors as Q, and let $|Q|$ denote the cardinality of the set Q. We define the query event as $T_{\text{event}}$ . We refer to n related sensors as temporal correlation n-graph. The special case of single sensor reading is referred to as unigraph. Two consecutive readings are referred to as digraph in the literatures, and trigraph means three consecutive sensed data readings, and so forth. Given a sequence of consecutive readings $R=\{r_1,r_2,\dots ,r_m\}$ , where m is the number of reading sequence, we have n-graph with the size of $m-n+1$ . We define the duration of temporal correlation n-graph $G=\{d_1,d_2,\dots ,d_k\hspace{0.17em}|\hspace{0.17em}k\in N,k\in [1,m-n+1]\}$ as follows:

$d_k=T_{\text{event}}^{r_{n+k-1}}-T_{\text{event}}^{r_k}.$

(7)

The durations of temporal correlation n-graph are used as timing features for further analysis. We make a natural assumption that the n-graph, with duration y, $P(y\hspace{0.17em}|\hspace{0.17em}q)$ , forms a Gaussian distribution, such that

$P\left(y\hspace{0.17em}|\hspace{0.17em}q\right)=\frac{1}{\sqrt{2\pi }{\sigma }_q}{e}^{-(y-{\mu }_q{)}^2/2{\sigma }_q^2},$

(8)

where ${\mu }_q$ is the mean value of the duration y for n-graph, and ${\sigma }_q$ is the standard deviation.

We have to deduce $\{(\widehat{{\mu }_q},\widehat{{\sigma }_q})\}$ of n-graph durations, give a reading sequence S, by the method of maximum likelihood estimation of the parameters. The maximum likelihood estimation of the parameters for Gaussian distribution can compute the sample mean and sample variance as follows:

$\begin{array}{c}\widehat{{\mu }_q}=\frac{{\sum }_{i=1}^k{d}_i\left(q\right)}{k},\\ {\widehat{{\sigma }_q}}^2=\frac{{\sum }_{i=1}^k{\left[d_i\left(q\right)-\widehat{{\mu }_q}\right]}^2}{k-1},\end{array}$

(9)

where is the number of n-graph q appeared in S.

2.2. Spatial Similarity

Sensor j is spatial correlation with sensor i if $(1)$     i and j are connected by at least a path, $(2)$ supposed that the path connecting i and j is $〈s_0=i,s_1,\dots ,s_k=j〉$ , sensor i can spatial correlation with $s_t$ for $t\in [1,k-1]$ , and $(3)$    $LN{Sim}_{k+1}(s_i,s_j,\mathrm{\Delta }t)\le \theta$ , the dissimilarity between i and j does not exceed the error threshold. Therefore, the spatial similarity can be described as a spatio-temporal similarity. The short-term spatial similarity $SSSim(s_i,s_j,\mathrm{\Delta }t)$ is defined as

$\text{SSSim}\left(s_i,s_j,\mathrm{\Delta }t\right)=\left\{s_i⟷s_j,\text{SN}{\text{Sim}}_{k+1}\left(s_i,s_j,\mathrm{\Delta }t\right)\le \theta \right\}.$

(10)

The long-term temporal similarity of $k+1$ round $\text{LS}{\text{Sim}}_{k+1}(s_i,s_j,\mathrm{\Delta }t)$ is derived as follows:

$\begin{array}{cc}\hfill \text{LS}{\text{Sim}}_{k+1}(s_i,s_j,\mathrm{\Delta }t)& =\rho ·\text{LS}{\text{Sim}}_k\left(s_i,s_j,\mathrm{\Delta }t-1\right)\hfill \\ \hfill & \hspace{1em}+\left(1-\rho \right)·\text{SSSim}\left(s_i,s_j,\mathrm{\Delta }t\right).\hfill \end{array}$

(11)

Thus, the problem that we study in this paper can be formally defined as follows. Given a set of sensors, the collection of the spatial correlation of all the sensors, and a prespecified error threshold θ, the fault event filter problem is to select a set of r-nodes R to judge the query event, such that for each sensor i, there is at least an r-node $r\in R$ spatio-temporal correlation i, and the number of r-nodes is minimized.

2.3. Data Correction and Importance Rank

In order to correct the imprecise and missing sensed data of sensor nodes in harsh environment, the original sensed data $x_t$ at time t will be correct at each sensor node:

$x_t=x_{t-1}+n_{t-1},$

(12)

where the random variable $n_{k-1}$ denotes noise. We assume that the random variable $n_{k-1}$ follows a time-independent normal distribution $N(0,Q)$ .

The measurement state is modeled as a vector and the measure at time t is denoted $m_t$ :

$m_t=H{x}_t+e_t,$

(13)

where the random variable $e_t$ describes measurement noise. We assume that $e_t$ follows a time-independent normal distribution $N(0,R)$ .

The correction procedure can be divided into three phases, namely, initialization, prediction and correction. We use ${\widehat{x}}_k^{-}$ and ${\widehat{x}}_k$ to denote the priori and posteriori state estimates at time t, respectively. The prior error covariance $P_k^{-}$ can be computed as follows:

$P_k^{-}=A{P}_{k-1}{A}^T+Q.$

(14)

Let the initial measurement of a given sensed data be $m_0$ , and the measurement noise follows the same distribution $N(0,R)$ across different time points, where

$m_0=x_0.$

(15)

The initial state estimate ${\widehat{x}}_0$ and posteriori error covariance $P_0$ can be described as

$\begin{array}{c}{\widehat{x}}_0=x_0,\\ P_0=x_{0}R.\end{array}$

(16)

The next step is to predict the sate and the error covariance at time point 1 using

$\begin{array}{c}{\widehat{x}}_1^{-}=A{\widehat{x}}_0,\\ P_1^{-1}=A{P}_0{A}^T+Q.\end{array}$

(17)

Then we execute the correction step to optimize the data quality. It is divided into three substeps. The first step is to compute the Kalman gain by applying:

$K_1=P_1^{-1}{H}^T{\left(H{P}_1^{-1}{H}^T+R\right)}^{-1},$

(18)

where H represents the relation between the measurement and the state.

The second step is to update the estimated state using the measurement $m_1$ by

${\widehat{x}}_1={\widehat{x}}_1^{-}+K_1\left(m_1-H{\widehat{x}}_1^{-}\right).$

(19)

The final step is to update the error covariance by:

$P_1=\left(1-K_{1}H\right)P_1^{-1}.$

(20)

This procedure is repeatedly executed to compute the state estimates for the following time points. The estimated location at time t is thus $H{\widehat{x}}_t$

The missing sensed data can be filled up simply by the predication of Kalman filter

${\widehat{x}}_k^{-}=A{\widehat{x}}_{k-1}.$

(21)

Given a spatio-temporal correlation network $G=(V,E)$ derived above, we should assign each sensor an appropriate value to reflect the importance of sensor. The value for each sensor is the degree to measure how many and how similar neighboring sensor the sensor has. The rank algorithm should consider not only one-hop neighbors but also k-hops neighbors when determining rank value. In order to measure the value, we could imagine the random walks on the correlation network. Intuitively, one could randomly select a sensor. Since this sensor has some edges that link to other sensors, it should follow the edge with a higher value of similarity.

We suppose that for an event query q from a sensor $s_i$ , the data frequently queried by sensors in the past are more relevant to $s_i$ than those seldom reading by $s_i$ , and thus, the score can be computed by

$\text{Score}(q,s_i)=\frac{\left|N\left(q,s_i\right)\right|}{\left|T\left(q,s_i\right)\right|+\beta },$

(22)

where $|N(q,s_i)|$ is the event query number on some sensed data by sensor $s_i$ on query q in the past, $|T(q,s_i)|$ is the total event query number on query q by sensor $s_i$ , and β is a smoothing factor.

When a sensor submits an event query, each of the returned data is also mapped to a weighting vector by temporal similarity:

${\text{Score}}_{\text{temp}}\left(q,s_i\right)=\frac{{\max \hspace{0.17em}}_{i\in \left[1,N\right]}\hspace{0.17em}{s}_{\text{temp}}^{m+1}\left(i,k\right)}{{\sum }_{k=1}^N{s}_{\text{temp}}^{m+1}\left(i,k\right)}·\text{Score}\left(q,s_i\right).$

(23)

The computation of rank value requires several iterations to determine the steady-state probability for each sensor. Specifically, ${\text{Score}}_{\text{temp}}(q,s_i)$ is the value of rank at the mth iterations. In the beginning, the initial ${\text{Score}}_{\text{temp}}(q,s_i)$ is set to 1. Note that ${\text{Score}}_{\text{temp}}(q,s_i)$ can be set to any constant a, and the results will be times the value generated when the initial rank value is set to 1. In the first round, each sensor $s_i$ updates its rank value as ${\text{Score}}_{\text{temp}}^1(q,s_i)$ using the initial rank value of its neighbors. Now each sensor has considered the first level neighbors to calculate its rank value. In the second round, each sensor can obtain some information from the second level neighbors through its first level neighbors since its first level neighbors have explored their first level neighbors as well. Therefore, after the mth round, sensor $s_i$ has explored the mth level neighbors and updated rank value as ${\text{Score}}_{\text{temp}}^m(q,s_i)$ . In the most situations, rank of every sensor will be stable in a few iterations. That is rank will come to a steady-state. But in some situations, it will not be stable. In order to solve this problem, a simple way is that an extra edge linked from a sensor to itself is added for every sensor.

2.4. Fault-Tolerant Event Query Algorithm

The proposed FTEQ algorithm consists of two phases: self-evaluation phase and cooperative evaluation phase. In self-evaluation phase, each sensor verifies whether the current reading of a sensor is unusual or not. Once the reading of a sensor goes through the self-evaluation phase, this sensor can directly report the reading. Otherwise, the sensor has to consult with the neighbors to further verify whether the current reading is faulty or caused by an interesting event. If the readings are determined as faulty readings, these faulty readings will be filtered out. Those sensor generated faulty readings will not get involved in negotiation since these sensors are likely to bias the negotiation for other sensors.

After collecting all the votes from the neighbors, $s_i$ has two classes of decisions: one is positive class and the other is negative class. If the weight of the former is larger than the weight of the later, the most neighbors will view $q_i(t)$ as normal. Note that the weight of a vote represents how much authority the judgment has. It is possible that a neighbor $s_j$ of $s_i$ has higher rank value with a low trust relation. In this case, these two sensors sense different environments by nature, and thus these two sensors cannot provide good judgments to each other. Therefore, each decision has to be multiplied by the corresponding trust relation. Thus, we have the following formula to justify whether the reading is faulty or not:

$D_i={\displaystyle \sum }_{s_j\in nei\left(i\right)}{\text{Decision}}_j\left(i\right)·{\text{Score}}_{\text{temp}}(q,s_i),$

(24)

where

${\text{Decision}}_j\left(i\right)=\{\begin{array}{cc}1,\text{positive}\hfill & \text{decision},\hfill \\ -1,\text{negative}\hfill & \text{decision}.\hfill \end{array}$

(25)

If the weights of the positive votes are more than the weight of the negative votes, $D_i$ will be positive which means that $s_i$ 's reading behavior is normal and the current reading can be aggregated. Otherwise, $D_i$ is negative, implying that the current reading of $s_i$ is a faulty reading.

3. Experimental and Simulation Results

3.1. Simulation Setup

The well-known simulation tool NS2 [10] is used to validate the proposed scheme. The simulation model consists of the environmental model, the faulty model, and the query model. The simulated sensor network is deployed in a $500\times 500$ sensing field for monitoring a synthetic environment where the reading range is $[-25,275]$ . We design a network simulator to generate the queries and the sensors associated with their readings. The simulated network consists of 1000 sensors randomly deployed in the two-dimensional area. The transmission range of each sensor is set to 40. In order to simulate the spatial correlation between nearby sensors in real-world data, we devised a mechanism to generate the readings of sensors according to the events in the network. An event characterizes the readings in a specific area. The readings of sensors which are near an event will be affected by the event. We randomly select 50 points in the network as the locations of events. The readings of events are generated following a random walk pattern. The initialized reading of each event is sampled from a normal distribution with mean 25°C and standard error 20°C. The move probability for the random walk is set to 0.7 for the purpose of making the readings more volatile, and the step size for each move is 1°C. The probability for the next reading to increase or decrease is 0.5°C. The reading of each sensor is affected by all the events in the network. The reading of a sensor at time t is the weighted average of the readings of events at time $t+1$ . The weight of an event is the inverse of the square of the distance between the sensor and the event.

To show the performance of the proposed FTEQ algorithm, we implemented the classical majority voting algorithm (denoted as CMV).

3.2. Experimental Results

In the first scenario, we examine the impact of the number of iterations of calculating rank value, reading behavior length of time window, and reading behavior length of time window on the proposed FTEQ algorithm.

Figure 1 shows the impact of the number of iterations of calculating rank value on faulty detection and convergence rates. The faulty rate is set to 0.5 to show the trend in the faulty detection rate and convergence rate. In Figure 1 when the number of iterations increases, the faulty detection rate increases. The reason is that when the number of iterations for calculating rank value is 0, rank value of each sensor is 1. In this situation, the proposed FTEQ is just like a general weighted voting. After three iterations for calculating rank value, we can find that rank value is convergence and thus the faulty detection rate and the false positive rate are also stable. The convergence rates for all sensors are averaged as experimental result. Figure 1 shows that rank value will converge fast in a few iterations. Explicitly, the convergence rate drastically decreases after three iterations of calculation. Therefore, after three iterations of calculating rank value, almost all sensors' rank values are stable.

Figure 1

Impact of number of iterations on faulty detection rate and convergence rate.

The impact of reading behavior length of time window on faulty detection rate is shown in Figure 2. When the length of the reading behavior is too long or too short, the performance of filtering faulty reading will not be good. It is intuitive that when $\mathrm{\Delta }t$ is small, wrong filtering will occur easily. When $\mathrm{\Delta }t$ is very large, the reading behavior may contain more noise. In this case, the similarity function generates small values and some normal readings are then filtered out. Thus, the false positive rate increases and faulty detection rate is not high.

Figure 2

Impact of the length of reading behavior.

Figure 3 shows the impact of the number of neighbors. We deployed a large number of sensors to increase the average number of neighbors of each sensor. In order to increase the number of neighbors, we increase the density of the deployment of sensors. Note that the more neighbors a sensor has the better performance a voting scheme is. The reason is that more neighbors will increase the number of spatio-temporal correlation nodes. For a negotiating-based scheme, if the probability that a sensor makes a wrong decision is low, the probability that the majority of neighbors make wrong decisions is much lower.

Figure 3

Impact of the number of neighbors.

In the second scenario, we compare the faulty detection rates, query processing cost, and energy consumption of the two algorithms.

Figure 4 shows that the proposed FTEQ can filter out about 87% faulty readings while CMV can only filter about 40% faulty readings. Intuitively, the faulty detection rate will be high in a low faulty sensor rate and will decrease when the faulty sensor rate increase. However, since faulty readings in FTEQ are biased normal readings, it is hard to identified faulty readings for CMV. Therefore, when the faulty sensor rate is low, the faulty detection rate is around 40%. When the faulty sensor rate increases, although almost all sensors are faulty, a faulty sensor can still be identified as faulty by its faulty neighbors due to dissimilar readings. Thus, the faulty detection rates are the same with various faulty sensor rates.

Figure 4

Faulty detection rate of two algorithms.

Figure 5 shows the data query processing cost of two algorithms, with the number of sensors varying from 200 to 1000. The event data set follows the uniform distribution. We investigate the number of messages exchanges among sensors. As shown in Figure 5, we can see that the results reveal the FTEQ being more scalable than CMV. With the number of sensors increasing, the number of messages for FTEQ increases slowly from 62 to 137. For CMV, the number of messages increases obviously and greatly from 89 to 521. The error between two algorithm increases greatly. This demonstrates that the proposed FTEQ can effectively filter faulty data query to accurate answer user queries while guaranteeing that data is accurate, which greatly decreases query processing cost.

Figure 5

Query processing cost of two algorithms.

In Figure 6, we compare the energy consumption of FTEQ and CMV. The initial energy capacity of each sensor is set to be equal to the simulated cost of 500 message transmissions. We repeat the experiment 10 times and present the average values. In each run, we let the sensors operate for 100 time-units. Algorithm FTEQ is executed every 100 time-units to select new r-nodes to detect data query event. The error threshold is 0.5°C. In FTEQ algorithm, for each query, a selected r-node reports its readings to the sink if some sensors in its spatio-temporal correlation within the query window. In CMV scheme, all the sensors within a query window report their readings to the sink. We account total remaining energy for FTEQ and CMV scheme every 100 time-units. As can be seen in Figure 6, the total remaining energy of sensors in CMV scheme is smaller than that of FTEQ. With the simulation time increasing, the total remaining energy of CMV decreases obviously, from 150200 to 3000. While for FTEQ, the total remaining energy decreases slowly. This proves that the proposed FTEQ saves energy effectively.

Figure 6

Average available energy of different algorithms over time.

4. Conclusions and Future Work

In this paper, we have considered the important problem of faulty-tolerant event data query in distributed WSNs so as to improve the date accuracy. The challenge problem is to distinguish between faulty readings and unusual readings caused by environments. In order to overcome the problem, we first formulated the similarity of sensor behaviors among sensors in term of both spatial and temporal behaviors of sensors, which also takes short- and long-terms spatio-temporal correlation into consideration. Then sensor nodes adopt Kalman filter to correct the imprecise and missing original sensed data in harsh environment. Based on the spatio-temporal correlation, we calculate score value to assign each sensor appropriate value to reflect the importance of sensor. FTEQ performs self-evaluation and cooperative evaluation schemes to filter fault data query. Detailed simulation results and comparisons with exited algorithms prove that the performance of FTEQ is much better in terms of faulty detection rate, data query cost, and energy consumption. The future work should be done on the issues of query moving objects and track objects.