Proximity-Based Robust Event Detection in Wireless Sensor Networks

Abstract

This paper presents a proximity-based event detection scheme for wireless sensor networks. It is a hybrid scheme in the sense that it takes advantage of both neighbor-based and cluster-based schemes in distinguishing events from false alarms due to faulty nodes. It gives more weights to alarms in closer proximity, while making event decisions at the cluster heads to reduce the communication overhead. The proposed scheme can effectively reduce false alarms while accurately detecting events even for a relatively small event region. Simulation results show that it greatly lessens the tradeoff between event detection accuracy and false alarm rate. Further improvements in performance can be made by removing identified faulty nodes from the network during normal operation.

1. Introduction

A wireless sensor network (WSN) is a network comprised of tiny sensor nodes that are spatially distributed to monitor various environments and detect events of interest. Such a network left unattended is vulnerable to faults including malicious attacks. Incorrect reports due to faulty sensor nodes might result in a wrong decision on the occurrence of an event. Hence, it is important to draw precise inferences from the sensed data collected and reliably detect an event in the presence of faulty or malicious nodes.

A number of fault or fault-tolerant event detection schemes have been proposed for wireless sensor networks to achieve high reliability in data aggregation and decision-making [1–10]. They are primarily either neighbor-based or cluster-based schemes, mostly without requiring any external processing. Neighbor-based schemes can achieve good performance for a relatively high node degree or at the expense of more internode communication. Cluster-based schemes, on the other hand, can make more efficient use of resources and are known to be energy efficient in aggregating sensor readings. They, however, might suffer from inaccuracy in local decision or difficulty in aggregating data from different clusters. If an event area is relatively small and lies across multiple clusters, it is difficult to set a threshold for decision-making. Especially for a fault-prone sensor network there is a strong tradeoff between event detection accuracy and false alarm rate, which can hardly be overcome.

Krishnamachari and Iyengar [6] made some initial steps to solving the fault-event disambiguation problem in sensor networks. They presented Bayesian algorithms to detect events in the face of faulty sensor nodes by exploiting the fact that sensor faults are likely to be stochastically uncorrelated, while event measurements are likely to be spatially correlated. Luo et al. [7] proposed a fault-tolerant energy-efficient event detection scheme. For a given detection error bound minimum neighbors can be selected to minimize the communication cost. In [8] a secure distributed event boundary detection scheme for WSN was proposed to identify event boundaries in an adversarial environment. Distributed event detection using a reputation-based voting and decision tree classifiers has been presented for disaster management in WSNs [9]. Most of them have presented fault-tolerant detection schemes for flat architecture. Little effort has been made in developing distributed detection schemes for hierarchical sensor networks.

Fault and event detection problems in clustered hierarchical networks have been investigated in [11–13]. Atakli et al. [11] proposed a fault detection scheme using weighted trust evaluation for a hierarchical sensor network. Trust values are employed to identify faulty nodes behaving arbitrarily regardless of the actual readings. Ju et al. [12] presented another intrusion detection scheme based on similar weighted trust evaluation, where the mistaken ratio of each individual sensor node is used in updating the trust values. More recently a distributed fault-tolerant event region detection scheme for a hierarchical sensor network is proposed [13]. However, the event detection problem for relatively small event regions and without location information of sensor nodes has not been investigated. In addition, the problem of distinguishing events from false alarms due to malicious faults in clustered networks has not been sufficiently studied. Fault or event detection schemes based on natural faults cannot function effectively in the face of malicious faults. The problem becomes even more complicated as the size of the event region decreases.

In this paper, we present a hybrid scheme for detecting events in the presence of faulty nodes in clustered sensor networks. It uses hierarchical decision based on a threshold test, while employing proximity-based local aggregation in computing the weight of each sensor node for the test. The final decision on the occurrence of an event is made at the cluster head without location information of sensor nodes and intergrid communication. It achieves good performance even for a relatively small event region. The scheme is robust to both natural and malicious faults and can maintain consistent performance as long as the number of faulty nodes is gradually increasing.

The rest of the paper is organized as follows. Section 2 discusses some preliminaries to our work, including fault model and event model. In Section 3, the proposed scheme for detecting events is presented. Simulation results are shown in Section 4. Section 5 concludes the paper.

2. Preliminaries

The problem of fault or event detection in sensor networks becomes complicated as the number of faulty nodes increases. In particular when the number of faulty nodes in a cluster is comparable to the number of event nodes in a cluster, it is difficult to choose a threshold value for distinguishing events from false alarms due to faulty nodes. The resulting event detection accuracy can hardly be high without increasing false alarm rate. To lessen the tradeoff between event detection accuracy and false alarm rate we propose a proximity-based detection scheme which gives more weights to alarm nodes located close to each other. We first describe the event detection problem for a special type of sensor network, called grid-based clustered sensor network [14, 15], for comparison purposes, and then introduce our proposed scheme in the subsequent section.

2.1. Grid-Based Sensor Networks

Grid-based sensor networks have been investigated for energy efficient data aggregation and routing [14]. The sensor field in a grid-based sensor network here is assumed to be divided into $M\times N$ square-shaped grids as illustrated in Figure 1, where there are four grids, A through D, each with a cluster-head (CH), and l is the side of a grid. The cluster-head is elected dynamically in each grid. All other nodes in the grid become member nodes and communicate directly with the head, although multihop communication can also be used.

Figure 1

A sensor network with four grids.

In detecting an event in the face of faulty or malicious nodes, sensor nodes with an abnormal sensor reading report an alarm to the CH so that it can make the final decision on the occurrence of an event. However, the decision made at the head based on the aggregated data might be inaccurate due to the difficulty in distinguishing an event from false alarms, especially when the size of the event region is relatively small. If the region lies across multiple grids as illustrated in Figure 1 (see the dotted circle), each grid might have insufficient number of event-nodes to apply a threshold test. Consequently, lowering the threshold might be needed to meet the event detection accuracy requirement, sacrificing the false alarm rate. To cope with the expected poor performance intergrid communication can be employed to exchange information among the adjacent grids. This might cause significant communication and computation overheads.

In order to lessen the tradeoff between event detection accuracy and false alarm rate we extend the model slightly for our hybrid scheme to be addressed in the next section.

2.2. Fault Model and Event Model

In this paper, we focus on a special type of fault, called data fault. That is, each sensor node behaves as a normal node but might generate incorrect readings naturally or intentionally due to faults. We assume that each sensor node is aware of the range of valid readings during no event period. Any readings outside the valid range are called “unusual” readings for clarity. Hence, each sensor node can make a binary decision on its own sensor reading, where a “1” indicates an unusual reading. Sensor nodes in an event region are expected to report a 1, unless they are faulty. That is, event reports to the CH are binary specifying the potential occurrence of an event.

We assume that sensor nodes are faulty randomly and independently with the same probability $p_m$ . Faulty nodes are allowed to change their readings arbitrarily to cover malicious behavior. In addition, sensor readings of normal sensor nodes are assumed to be incorrect with the same probability. They are also assumed to occur randomly and independently in space and time. The transient fault probability $p_t$ is expected to be relatively small since most of the incorrect readings due to transient faults can be filtered or smoothed out locally at each node.

An event region is assumed to be a circle with radius $r_e$ , although the proposed scheme can be applied to event regions of other shapes. The size of an event region will be taken into account in selecting a threshold for event detection. For a relatively large event region it is easy to set a threshold since at least one grid is likely to have sufficient number of event nodes to distinguish an event from false alarms. As the size of an event region decreases, each grid might contain only a small number of event nodes, making it difficult to meet the performance requirements.

3. Event Detection Using Proximity Information

In order to achieve high event detection accuracy while keeping false alarm rate low we use a hybrid approach in aggregating sensor readings to take advantages of both neighbor-based and hierarchical schemes.

3.1. Network Model

We assume that the network consists of low-cost tiny sensor nodes and more powerful head nodes, although a homogeneous network with rotating cluster-heads may be used as well. Sensor nodes are logically divided into multiple grids (clusters), each of which has its own CH. Each sensor node in the network is assumed to have a unique ID and thus can construct a list of its neighboring nodes, where two nodes are neighbors of each other if the distance between them is less than or equal to $r_c$ (transmission range to send an alarm to neighbors). Some nodes in the adjacent grids may be included if there exist overhearing links. In addition, each node in a grid can directly or indirectly (using multihopping) report to the CH.

In Figure 2, for example, node $v_x$ has four neighbors within the range of $r_c$ . When it observes an unusual reading, it sends a 1 to its neighbors. It then counts the number of 1's received from its neighbors and reports it to the CH. CH makes the final decision on the occurrence of an event using a threshold test to be explained shortly.

Figure 2

Hierarchical decision with proximity information.

The extra work to be done by each node in the network, as compared to the typical grid-based sensor network, is that each node should broadcast to its neighbors only once if it is an alarm node (i.e., its sensor reading is a 1). Since the process is event-driven, only the alarm nodes are involved as far as counting the number of 1's is concerned. In addition, events may occur randomly in any place in the monitored area. Hence, the energy consumed by each node might be balanced over time. Furthermore, $r_c$ is set to a relatively small value to reduce the required internode communication. In the later simulation, $r_c$ will be chosen to make the average node degree about 5.

3.2. Trust Level of Sensor Nodes

Trust level is defined here to indicate the trustworthiness of sensor nodes in reporting alarms in the wireless sensor network. For a CH with n member nodes $v_{\mathrm{1}},v_{\mathrm{2}},\dots ,v_n$ , the CH maintains $c_{\mathrm{1}},c_{\mathrm{2}},\dots ,c_n$ , as their trust levels, respectively. Initially all the levels ( $\mathrm{0}\le c_i\le \mathrm{1}$ ) are set to 1. Each time the decision on the occurrence of an event is made at the CH, using the proximity-based threshold test which is to be detailed in the next subsection, the CH updates the levels depending on the correctness of their reports. Here we adopt the updating policy [16] to locate faulty nodes while tolerating transient faults, although other policies may be used as well. Nodes whose trust levels reach a predefined lower bound (0 in this paper) are determined to be faulty and will thus be isolated from the rest of the network thereafter.

In the case where the decision at the CH is no event, the CH updates the trust levels of its member nodes as follows:

$$\begin{array}{cc}& c_j=\{\begin{array}{cc}\max \left(\mathrm{0},c_j-\alpha \right)\hfill & \text{for}\hspace{0.17em}\hspace{0.17em}{x}_j=\mathrm{1},\hfill \\ \min \left(\mathrm{1},c_j+\beta \right)\hfill & \text{for}\hspace{0.17em}\hspace{0.17em}{x}_j=\mathrm{0},\hfill \end{array}\end{array}$$

(1) where $x_j$ denotes the sensor reading of node $v_j$ and $\mathrm{0}<\alpha ,\beta \le \mathrm{1}$ . Nodes reporting a 1 in the case of no event lose their levels, $c_j$ , by α. Otherwise, they gain weights by β. The two parameters, α and β, play an important role in tolerating transient faults. If $\alpha =0.2$ and $\beta =0.05$ , a sensor node reporting a 1 every 5 cycles recovers its trust level to 1. That is, a normal sensor node is highly likely to remain in the network unless the transient fault probability $p_t$ is greater than 0.2. Nodes reporting a 1 more frequently than this gradually lose their trust levels and will eventually be isolated from the network.

In the case of an event, the levels of the nodes within the event region need to be lowered if they have reported a 0. Due to the difficulty in finding the exact boundary of an event region without any location information, we do not apply any updates when the decision is an event.

3.3. Proximity-Based Event Detection

In detecting an event, proximity information is used at the CH to perform a simple test with a predefined threshold. In the beginning each sensor node identifies its neighboring nodes and reports them to the CH so that the CH can figure out the names and node degrees of its member nodes and how they are connected. For convenience we first list the notation to be used in this paper (see Nomenclature Section).

Once an unusual reading is observed at a sensor node, the node sends a 1 to its neighbors so that each of the alarm nodes can count the number of 1's (including its own reading), $s_i$ , it has received. Each sensor node $v_i$ with its reading $x_i=1$ then reports $s_i$ to the CH so that the CH can perform a threshold test for event detection. The reason for computing $s_i$ is to give more weight to the node with higher $s_i$ . Since the node degree $d_i$ is also important in estimating the weight of the node $v_i$ , we take node degree into account in making the final decision at the CH. The contribution of a node $v_i$ with its $x_i=1$ is increased to $k_i{\mathrm{2}}^{s_i-\mathrm{1}}$ , where $k_i\hspace{0.17em}\hspace{0.17em}(\mathrm{0}\le k_i\le \mathrm{1}$ ) is determined based on $s_i$ and $d_i$ using two thresholds, ${\theta }_{\mathrm{1}}$ and ${\theta }_{\mathrm{2}}\hspace{0.17em}\hspace{0.17em}({\theta }_{\mathrm{1}}>\mathrm{\hspace{0.17em}\hspace{0.17em}}{\theta }_{\mathrm{2}}$ ), to be explained below. If $k_i$ is assigned to 1, for example, a node with $s_i=1$ is treated as a single 1, while a node with $s_i=3$ is taken as ${\mathrm{2}}^{\mathrm{2}}$ alarm nodes. Since $s_i$ is determined out of $d_i+1$ sensor nodes, the ratio $s_i/(d_i+\mathrm{1})$ is used in assigning the value of $k_i$ as follows:

$$\begin{array}{cc}& k_i=\{\begin{array}{cc}\mathrm{1}\hfill & \text{for}\hspace{0.17em}\hspace{0.17em}\frac{s_i}{d_i+1}>{\theta }_{\mathrm{1}},\hfill \\ \frac{s_i}{d_i+\mathrm{1}}\hfill & \text{for}\hspace{0.17em}\hspace{0.17em}{\theta }_{\mathrm{2}}<\frac{s_i}{d_i+1}\le {\theta }_{\mathrm{1}},\hfill \\ \mathrm{0}\hfill & \text{otherwise}.\hfill \end{array}\end{array}$$

(2) If $s_i/(d_i+\mathrm{1})>{\theta }_{\mathrm{1}}$ (upper threshold), $k_i$ is set to 1 to fully accept the node's contribution. If ${\theta }_{\mathrm{2}}<s_i/(d_i+\mathrm{1})\le {\theta }_{\mathrm{1}}$ , only   $s_i/(d_i+\mathrm{1})$ of ${\mathrm{2}}^{s_i-\mathrm{1}}$ is accepted to lower its contribution proportionally. If the ratio cannot pass ${\theta }_{\mathrm{2}}$ (lower threshold), $k_i$ is set to 0 to ignore the contribution of the node.

Finally, the decision on the occurrence of an event is made at the CH as follows with another predefined threshold ${\theta }_{\mathrm{3}}$ :

$$\begin{array}{cc}& E\left(\text{an}\hspace{0.17em}\text{event}\right)=\mathrm{1}\hspace{1em}\text{if}\hspace{0.17em}\hspace{0.17em}\frac{\sum ‍x_i{k}_i{\mathrm{2}}^{s_i-\mathrm{1}}}{\sum ‍\left(\mathrm{1}-x_i\right)+\sum ‍x_i{k}_i{\mathrm{2}}^{s_i-\mathrm{1}}}>{\theta }_{\mathrm{3}},\end{array}$$

(3) where $\sum ‍(\mathrm{1}-x_i)$ is the number of nodes with $x_i=0$ and $\sum ‍x_i{k}_i{\mathrm{2}}^{s_i-\mathrm{1}}$ is the sum of the contributions from alarm nodes.

Our fault model defined earlier assumes only data faults in sensor readings. Internode communication is assumed to be fault-free. The scheme, however, is robust, to some extent, to communication faults as far as computing the number of 1's, $s_i$ , and the resulting $k_i$ are concerned. In such a nonideal wireless environment, the actual number of 1's received might be smaller than expected. Even in this case the scheme still functions in a gracefully degradable manner with the potentially incorrect $s_i^{\prime }s$ . If necessary, the upper and lower thresholds can be adjusted accordingly although the issue is beyond the scope of this paper.

Our event and fault detection scheme can be described as follows.

Proximity-Based Event Detection.

• (1)

Each sensor node $v_i$ sends a 1 to its neighboring nodes if $x_i=1$ .

(2)

Each sensor node $v_i$ with $x_i=1$ computes $s_i$ (number of 1's) and reports it to CH.

(3)

CH determines $k_i$ for each node with $x_i=1$ (using two thresholds ${\theta }_{\mathrm{1}}$ and ${\theta }_{\mathrm{2}}$ ) to adjust the amount of contribution.

(4)

CH performs the threshold test with ${\theta }_{\mathrm{3}}$ to make a decision on event occurrence.

(5)

Update trust levels of member nodes at the CH in the case of no event.

The values of ${\theta }_{\mathrm{1}}$ , ${\theta }_{\mathrm{2}}$ , and ${\theta }_{\mathrm{3}}$ are assigned as follows. Let $p_f\hspace{0.17em}(\approx p_m\hspace{0.17em}+p_t$ ) represent the fault probability. Then we can expect a functioning sensor network to be likely to have an upper bound on $p_f$ , $p_f^u$ . Under the assumption sensor nodes within an event region are likely to satisfy $s_i/(d_i+\mathrm{1})>(\mathrm{1}-p_f^u)$ on average. Hence, we set ${\theta }_{\mathrm{1}}$ close to $1-p_f^u$ . In addition, faulty sensor nodes in the case of no event are unlikely to have $s_i/(d_i+\mathrm{1})$ greater than $p_f^u$ on average. Thus, we set ${\theta }_{\mathrm{2}}$ to $p_f^u$ . Since the proximity information is used in the proposed threshold decision scheme, it is not easy to choose a proper value for ${\theta }_{\mathrm{3}}$ . Due to the fact that all the parameters $d_i$ , l, $r_e$ , and $r_c$ affect the performance we choose a proper value of ${\theta }_{\mathrm{3}}$ based on the simulation results in the subsequent section and present a guideline for setting the value of ${\theta }_{\mathrm{3}}$ .

Communication between CHs is needed only in Step (5) to logically isolate faulty nodes from the network. The IDs of faulty nodes are broadcasted to the member nodes so that they can update their neighbor lists accordingly. Updating the neighbor lists is also needed at the CH for the future threshold decisions.

4. Simulation Results

We conducted some experiments to evaluate the performance of the proximity-based robust detection scheme. A sensor network where 320 sensor nodes are randomly deployed in a square area is used for the simulation. The network area is logically divided into 4 × 4 grids of the same size, each of which has 20 nodes on average. The transmission range $r_c$ is set to make the degree of each node approximately 5. The radius of an event region, $r_e$ , is assumed to be 0.5l, where l is the side of a square grid, to estimate the performance for a relatively small event region. Event center is generated in such a way that the corresponding circle can be within the monitored area. Two metrics, event detection accuracy (EDA) and false alarm rate (FAR), are used in the evaluation. EDA is defined as the ratio of the number of events detected and the total number of events generated. FAR is used to denote the ratio of the number of false alarm cycles to the total number of no event cycles operated. The results for the metrics EDA and FAR are averaged over 10⁴ runs.

Although there are many fault or event detection schemes for sensor networks, few schemes can be applied to clustered sensor networks without location information of sensor nodes. In addition, most of them deal with only natural faults. Due to the differences in fault models malicious behavior can hardly be effectively dealt with under the models, especially for a relatively small event region. Hence, the local decision scheme with a single threshold θ in a grid-based sensor network, introduced in Section 2.1, is also simulated for comparison purposes.

We first evaluate EDA and FAR for the local decision scheme (called LDG for convenience). The results for various values of $p_m$ up to 0.2 when $p_t=0.05$ are shown in Figure 3, where five different threshold values are chosen to see the tradeoff between EDA (solid lines) and FAR (dotted lines).

Figure 3

EDA and FAR for various values of $p_m$ when $p_t=0.05$ for LDG.

EDA is required to be high since an event undetected might cause a significant damage. EDA ≥ 0.95 in the figure can be achieved only when $\theta <0.25$ . FAR for the chosen value of θ, however, is too high for the scheme to be used in practice. FAR is over 0.7 even when $p_m=0.1$ . Hence, satisfying both high EDA and low FAR for LDG is difficult or might be impossible with a single threshold θ.

To see the performance improvements we then evaluate EDA and FAR of the proposed proximity-based scheme (PBS) for various values of $p_m$ when $p_t=0.05$ . The results are shown in Figure 4, where ${\theta }_{\mathrm{1}}=0.7$ , ${\theta }_{\mathrm{2}}=0.3$ , and three different values of ${\theta }_{\mathrm{3}}$ , 0.60, 0.65, and 0.70 are chosen for comparison.

Figure 4

EDA and FAR for PBS for various values of $p_m$ when $r_e=0.5l$ and $p_t=0.05$ .

EDA can be maintained relatively high for the chosen values of ${\theta }_{\mathrm{3}}$ , although ${\theta }_{\mathrm{3}}=0.60$ shows the best performance among them. FAR is greatly reduced at the same time as compared with that of LDG. Similar but better performance can be expected as the event region increases. To see the changes in EDA the same simulation is conducted for $r_e=0.6l$ . The results are shown in Figure 5. EDA becomes higher, very close to 1 for all the three values of ${\theta }_{\mathrm{3}}$ , since more event nodes exist in each grid involved. The trends inform us that FAR can be further lowered to an acceptably low value by slightly increasing ${\theta }_{\mathrm{3}}$ without noticeably sacrificing EDA.

Figure 5

EDA and FAR for PBS for various values of $p_m$ when $r_e=0.6l$ and $p_t=0.05$ .

The tradeoff between EDA and FAR for LDG can also be lessened when $r_e=\mathrm{0.6}l$ . However, the tradeoff is still strong to make it difficult to choose a proper threshold value satisfying both EDA and FAR requirements. The proposed proximity-based event detection scheme can also be applied within each grid. This also outperforms LDG although slightly lower EDA and higher FAR are unavoidable as compared with PBS.

Further reductions in FAR can be made by identifying faulty nodes using trust levels and removing them upon detection. Isolating faulty nodes upon detection effectively lowers the fault probability in such a way that the corresponding FAR can be greatly reduced with time as shown in Figures 6 and 7, where $\alpha =0.1$ and $\beta =0.02$ are chosen for two different values of $p_m$ , 0.1 and 0.2, respectively. After about 10 cycles of operation most faulty nodes are isolated, resulting in significant reductions in FAR. Even for $p_m=0.2$ FAR approaches 0.1 when ${\theta }_{\mathrm{3}}=0.7$ . Additional differences in FAR can also be observed with a small increase in ${\theta }_{\mathrm{3}}$ .

Figure 6

FAR of PBS for for $p_m=0.1$ when $p_t=0.05$ .

Figure 7

FAR of PBS for $p_m=0.2$ when $p_t=0.05$ .

So far we have performed simulation for various values of $p_m$ to see how effectively the scheme meets the requirements on EDA and FAR. We have observed that FAR can be controlled to low values without noticeably sacrificing EDA. As $p_m$ increases beyond the range of our experiments, however, it might be difficult to satisfy both EDA and FAR requirements unless the size of an event region is sufficiently large. If we take into account the fact that all the faults are unlikely to occur at the same time, we can exploit the adaptive nature of the proposed scheme to further enhance the performance. Since our scheme allows to remove faulty nodes upon detection, the resulting network can still keep the fault probability $p_m$ manageably low. To see the adaptability of the proposed scheme, we also perform similar simulation where $p_m$ is stepwise increased every 20 cycles up to 0.3. Two different increments, 0.05 and 0.1, are chosen to see the adaptability of the scheme, and the results are shown in Figures 8 and 9, respectively. Most faulty nodes are identified and isolated. Hence, FAR for the proposed adaptive scheme can be maintained extremely low even with the stepwise increase in $p_m$ .

Figure 8

FAR for PBS when $p_m$ increases up to 0.3 by 0.05.

Figure 9

FAR for PBS when $p_m$ increases up to 0.3 by 0.1.

In our simulation, relatively small event regions are considered to see the worst case performance. Hence, we claim that the proposed scheme can perform better as the size of the event region increases. The adaptability of the proposed scheme allows us to meet both EDA and FAR requirements even for relatively high fault probabilities. The same is true unless the faults occur almost simultaneously.

5. Conclusion

In this paper, we presented a proximity-based robust event detection scheme for wireless sensor networks. The scheme does not assume that sensor nodes have any prior knowledge about their locations. It makes event decisions at the cluster-head based on a threshold test using the proximity information. Overhearing links are exploited to extend the coverage area of each cluster. More weights are given to alarm nodes located close to each other in distinguishing events from false alarms. The proposed scheme is adaptive in the sense that faulty nodes detected are isolated from the rest of the network to maintain consistent performance. The simulation results show that the scheme yields high performance even for a relatively small event region. Much better performance can be expected as the event region increases. The scheme is also shown to be effective for increased number of faults unless all the faults occur almost simultaneously.