## 5 Intrusion Detection Scheme Based on Relaxed Flow Conservation Constraints
### Two-Hop Energy-Efficient and Secure Reporting Scheme
#### 5.2.1 Witness Set Model  
When the monitoring node \(m\) cannot judge directly based on its own observations whether the behavior of its upstream node \(u\) is normal or not, it has to collect ratings on node \(u\) from other nodes, called the witness nodes. Witness nodes that can rate \(u\) are: (1) nodes, which can overhear the transmission of node \(u\) and at least one of \(u\)'s children and (2) \(u\)'s children.  
To define the set of witness nodes, as denoted by \(WN_{u}\), which can rate node \(u\), we have to define first the witness region for the transmitter relay pair \((\omega,u)\) as:  
\[WR_{\omega\to u}=\{p=(x,y)\in\mathbb{R}^{2}:\mathit{dis}(p,\omega)\leq r \wedge\mathit{dis}(p,u)\leq r\}\]  
where \(r\) denotes the node transmission radius, and \(\mathit{dis}(p_{1},p_{2})\) denotes the euclidean distance between two points \(p_{1}\) and \(p_{2}\). Figure 2(a) shows the witness region for \((u_{1},u)\) as shaded region. The total witness region for node \(u\), which is shown in Figure 2(b), is defined by \(WR_{u}=\bigcup\limits_{\omega\in Child_{u}}WR_{\omega\to u}\).  
The set of witness nodes \(WN_{u}\) are the nodes that are located in the witness region \(WR_{u}\), except for node \(u\). Let us consider that a witness node \(w\) can overhear the transmission between a set of nodes \(\mathit{Child}_{u}^{[w]}\subseteq\mathit{Child}_{u}\) and node \(u\). The witness node \(w\) applies the following constraint C4 to rate node \(u\).  
\[\text{C4: }\mathit{wit}_{w}^{u}=\sum\limits_{\omega\in Child_{u}^{[w]}}f( \omega,u)-\sum\limits_{\omega\in Child_{u}^{[w]}}g(\omega,u,\mathit{Parent}_{u })\leq\chi_{w}^{u}\]  
C4 (or one-hop witness monitoring and detection process) node \(w\) checks if the data packets, which were sent by nodes \(\in\mathit{Child}_{u}^{[w]}\) to node \(u\), are forwarded by node \(u\). If the difference between the two elements: \(\sum\limits_{\omega\in Child_{u}^{[w]}}f(\omega,u)\) and \(\sum\limits_{\omega\in Child_{u}^{[w]}}g(\omega,u,\mathit{Parent}_{u})\) exceeds the threshold \(\chi_{w}^{u}\), node \(u\) will be considered as malicious. Otherwise, it is normal. \(\chi_{w}^{u}\) is the highest value of \(\mathit{wit}_{w}^{u}\) recorded by node \(w\) while observing node \(u\) during the training phase.  
If a witness node gives fair rating, then it is called honest. Otherwise, it is called liar. We can notice that each witness node located in \(WR_{u}\) partially monitors the traffic flow coming to node \(u\). As \(\mathit{Child}_{u}^{[w]}\
eq\mathit{Child}_{u}^{[w]}\), the amount of traffic monitored by \(w\) differs from that of \(w^{\prime}\) and, hence, it is impossible to fairly compare between two ratings \(\mathit{wit}_{w}^{u}\) and \(\mathit{wit}_{w^{\prime}}^{u}\) that resulted from different observations and tell which one is honest or liar. Figure 3 shows that the nodes, which are witnessing node \(u\), are \(\{w1,w2,u1,u2,u3\}\). Nodes \(w1\), \(u1\), and \(u2\) can only monitor the traffic flows \((u1,u)\) and \((u2,u)\). On the other hand, nodes \(w2\), \(u1\), and \(u3\) can only monitor the traffic flows \((u1,u)\) and \((u3,u)\). To deal with this issue, we use binary values to rate node \(u\). Formally, the reputation rating held by witness node \(w\) about node \(u\), denoted as \(rating_{w^{\prime}}^{u}\), is set to \(1\) if \(u\) is normal and \(0\) otherwise.