## 3 Grid-Based Event Detection
### Grid-Based Fault-Tolerant Event Detection  
The proposed grid-based fault-tolerant event detection scheme consists of five steps. Initially each cluster head \(H_{i}\) is assumed to know the numbers of sensor nodes in its four subgrids, \(n_{i}^{0},n_{i}^{1},n_{i}^{2},n_{i}^{3}\). In addition, the four numbers of each of its neighboring grids are also assumed to be given. In fact, the numbers can be obtained right after deployment by intra- and inter-cluster communications. In Step 1, each sensor node \(v_{j}\) computes \(b_{j}^{k}\) based on \(w\) most recent readings. In Step 2, each sensor node with \(b_{j}^{k}=\) 1 reports a 1 to the cluster head \(H_{i}\), and the cluster head counts the number of nodes reporting a 1 in each subgrid. Hence each cluster head will have the following eight numbers: \(n_{i}^{0},n_{i}^{1}\), \(n_{i}^{2}\), \(n_{i}^{3}\), \(e_{i}^{0}\), \(e_{i}^{1}\), \(e_{i}^{2}\), \(e_{i}^{3}\), where the first four represent the numbers of sensor nodes in the corresponding subgrids and the \begin{table}
\begin{tabular}{c c c} \hline \(\mathbf{D}\) & \(\mathbf{b_{k}}\) & \(\mathbf{c_{k}}\) \\ \hline
0 & 0 & min (\(c_{k}+\alpha\), 1) \\
0 & 1 & max (\(c_{k}-\beta\), 0) \\
1 & 0 & no change \\
1 & 1 & no change \\ \hline \end{tabular}
\end{table} 
Table 3: Updating \(c_{k}\) at cluster heads. remaining four denote the numbers of nodes reporting a 1 in the four subgrids. The cluster head then computes the number of 1's, \(E\), in the grid. In the grid A, for example, \(E_{A}=e_{i}^{0}+e_{i}^{1}+e_{i}^{2}+e_{i}^{3}\). The cluster head then applies a threshold test to determine on an event (_i.e._, \(D_{A}\) = 1 (_i.e._, an event) if \(E_{A}\geq\theta\)). In Step 3, each cluster head receives the four numbers \(e_{j}^{0},e_{j}^{1},e_{j}^{2},e_{j}^{3}\) from each of its neighboring cluster-head \(H_{j}\)'s. It then computes the number of nodes reporting a 1 in each of the SRs (2 \(\times\) 2 subgrids), and applies the same test with a threshold \(\theta\) in Step 4. Finally in Step 5, depending on \(D\) and \(b_{j}^{k}\) the confidence level of \(v_{j}\) (_i.e._, \(c_{j}\)) is updated according to Table 3.  
Due to the inherent tradeoff between DA and FAR, the value of \(\theta\) is important to satisfy both requirements on DA and FAR. In determining \(\theta\), the number of nodes in a grid (or SR) and the event size are taken into account. We set the threshold \(\theta\) at a grid to be  
\[\theta=\text{min}\;(\frac{d}{q_{d}},\;q_{c}) \tag{3}\]  
where \(q_{d}\) and \(q_{c}\) are predefined constants and \(d\) denotes the number of sensor nodes in the grid (or SR). For \(m=3\), in Table 1, about 1/3 of the nodes in a grid are in an event region on average. Hence to achieve high event detection accuracy for such a small event region, \(q_{d}\) must be greater than 3. Under the assumption that \(m\leq 3\), we set \(q_{d}\) to 4 to tolerate some variations due to nonuniform distribution of sensor nodes. Adjusting \(q_{d}\) alone (_i.e._, \(\theta=\frac{d}{q_{d}}\)), depending on the event region size, might be good enough to achieve high performance. We, however, employ \(q_{c}\) to achieve even higher DA with a negligibly small increase in FAR for relatively high \(d\). The reason is that in a randomly deployed sensor network, very few sensor nodes might be placed in some sub-grids, even for high \(d\). In that case, \(q_{c}\) will allow the grid or SR to pass the threshold, while maintaining small FAR. If \(\theta=\text{min}\;(\frac{d}{4},\;3)\), for example, the threshold \(d/4\) is effective until it reaches 3. After that, it remains there. Correcting most transient faults and isolating permanent faulty nodes allow us to lower \(\theta\) to handle small event regions effectively. Since FAR is independent of the event region size, lowering \(\theta\) will guarantee higher DA as event region size increases. If the event region size is approximately given based on experiments, adjusting the values of \(q_{d}\) and \(q_{c}\) accordingly will lead to a better performance.