## 5 Intrusion Detection Scheme Based on Relaxed Flow Conservation Constraints
### Two-Hop Energy-Efficient and Secure Reporting Scheme
#### 5.2.2 Two-Hop Energy-Efficient Reporting Scheme  
We propose a lightweight method for reporting node \(w\)'s opinions about node \(u\) to node \(Parent_{u}=m\). Each node \(i\) stores the following variables: (1) \(\mathit{Child}_{i}\) (i.e., the set of \(i\)'s upstream nodes in the tree-based routing topology), (2) \(\mathit{Witnessing}_{i}\) (i.e., the set of witness nodes that can monitor any node in \(\mathit{Child}_{i}\)), (3) \(\mathit{Witnessed}_{i}\) (i.e., the set of nodes that node \(i\) can monitor, ordered according to the lexicographical order (where \(0<1<2\ldots\))), (4) \(\mathit{Relay}_{i}\) (i.e., the set of witness nodes that use \(i\) as a relay to reach their two-hop monitoring nodes). The method is executed in two phases: (a) initialization  
Figure 3: Witness region for \((u_{1},u)\) and total witness region for \(u\). phase, executed once, and (b) a rating phase, executed periodically. Figure 4 shows the value of some variables that resulted from executing the reporting scheme. In the figure, the directed links represent the tree-based routing topology, and a dotted line drawn from a node \(w\) to link \((\omega,u)\) indicates that \(w\) can overhear the messages transmitted by \(\omega\) and \(u\). In the initialization phase, the following operations are carried out:  
1. Each witness node \(w\) that can observe the network traffic traversing the link \((\omega,u)\) adds \(u\) to the set \(\mathit{Witnessed_{w}}\). Subsequently, \(w\) broadcasts \(\mathit{Witnessed_{w}}\) with \(TTL=2\). 2. When a monitoring node \(m\) receives \(\mathit{Witnessed_{w}}\) and \(\mathcal{W}_{w}=\{Child_{m}\cap\mathit{Witnessed_{w}}\}\
eq\emptyset\) (i.e., \(w\) can monitor at least one of \(i\)'s children), \(m\) adds \(w\) to \(\mathit{Witnessing_{m}}\). Subsequently, it stores for each \(p\in\mathcal{W}_{w}\) the position of \(p\) in \(\mathit{Witnessed_{w}}\). Afterwards, node \(m\) broadcasts a message containing \(\mathit{Witnessing_{m}}\). In Figure 4, as node 3 can observe node \(m\)'s children, it is added to \(\mathit{Witnessing_{m}}\). 3. When a node \(r\) receives \(\mathit{Witnessing_{m}}\), it checks for all \(j\in\mathit{Witnessing_{m}}\) if \((j\in N_{r}\wedge j\
otin N_{m})\) (i.e., witness node \(j\) cannot reach \(m\) directly, but only through \(r\)). If so, it adds \(j\) to \(\mathit{Relay_{r}}\). In the rating phase, each node \(i\) has to report periodically its observations and forward the observations of nodes in \(\mathit{Relay_{i}}\) to the monitoring nodes (i.e., \((|\mathit{Relay_{i}}|+1)\) observations are periodically reported by node \(i\)). Each observation from node \(w\) has to include the ID of all nodes \(j\in\mathit{Witnessed_{w}}\) and their ratings. As \(N\) is the total number of nodes, the ID and the rating can be encoded using \(\log_{2}N\) bits and one bit, respectively. Thus, the size of this observation is: \(|\mathit{Witnessed_{w}}|(\log_{2}N+1)\) bits, and the total size of information that is transmitted periodically by each node \(i\) is \((\sum_{w\in\mathit{Relay}}|\mathit{Witnessed_{w}}|+|\mathit{Witnessed_{i}}|)( \log_{2}N+1)\) bits. \(|\mathit{Relay_{i}}|\) and \(|\mathit{Witnessed_{w}}|\) are upper-bounded by \(d_{max}\), where \(d_{max}\) is the maximum node degree of the network. As, for example, let us consider \(N=1024\) and \(d_{max}=10\), the size of one observation is \(110\) bits, and the total size of observations to be sent by node \(i\) is: \(1210\) bits. To reduce this size, we apply a spatial-temporal compression, as follows:  
* Spatial compression: as the monitoring node knows the position of its children in \(\mathit{Witnessed_{w}}\), we do not need to transmit the couple \((j,rating_{w}^{j})\) for each \(j\in\mathit{Witnessed_{w}}\). Instead, \(w\)'s observation will consist of \(w\)'s ID, and a boolean bit vector, denoted by \(\mathit{Rep_{w}}\) and composed of \(|\mathit{Witnessed_{w}}|\) bits.