## 5 Intrusion Detection Scheme Based on Relaxed Flow Conservation Constraints
### One-Dimensional One-Class Classifier: Relaxed Flow Conservation Constraint  
We model WSN as a directed tree \(G=(V,E)\), where each edge \(e=(u,v)\) has a defined capacity denoted by \(\mathcal{C}(e)\) or \(\mathcal{C}(u,v)\). Each node \(m\) monitors its downstream neighbor (i.e., \(m\)'s parent denoted by \(Parent_{m}\)) and all of its upstream neighbors (i.e., \(m\)'s children denoted by \(Child_{m}\)). Based on the known multi-flow problem [42], we define a flow as a function \(f(u,v):V\times V\rightarrow\mathbb{N}\), which counts the number of packets sent from node \(u\) to node \(v\) during a monitoring period of length \(\Delta\) and satisfies the following constraints:  
* Flow conservation constraint: the sum of flows entering \(v\) and that generated by \(v\) during a monitoring period \(\frac{\Delta}{\Delta t}\) must equal the flow leaving \(v\) towards \(Parent_{v}\) for all nodes, except the sink node and the leaf nodes in the tree-based topology, as depicted in Figure 2. Formally: \[\bigg{(}\sum_{\omega\in Child_{\omega}}f(\omega,v)+\frac{\Delta}{\Delta t} \bigg{)}-f(v,Parent_{v})=0\] A flow \(f(u,v)\) can also be written as: \[f(u,v)=self_{u}+\sum_{\omega\in Child_{\omega}}g(\omega,u,v)\] such that: \(self_{u}\) is the flow actually generated by node \(u\), and \(g(\omega,u,v)\) is the flow received by node \(u\) from node \(\omega\) and forwarded later to node \(v\). * Capacity constraint: the flow along any edge must be positive and less than the capacity of that edge. Formally: \(0\leq f(u,v)\leq\mathcal{C}(u,v)\). As the wireless channel is error-prone, some packets could be lost due to collisions, and thus the flow conservation constraint cannot be ensured. To deal with this issue, we use instead a relaxed flow conservation constraint, which represents the difference between (a) the flows leaving \(v\), and (b) the sum of flows entering \(v\) and the flow generated by \(v\). The value of this difference is bounded between 0 and a given threshold \(\in\mathbb{N}^{*}\). Our objective is to determine the threshold that encompasses all the normal instances \(d_{v}\) such that:  
\[d_{v}=\bigg{(}\sum_{\omega\in Child_{\omega}}f(\omega,v)+\frac{\Delta}{\Delta t }\bigg{)}-f(v,Parent_{v})\]  
To this end, the relaxed flow conservation constraint can be written as one-dimensional one-class classifier that satisfies the following:  
\[d_{v}\leq\max_{t\in[0,T]}\delta_{v}(t)=\delta_{v}\]  
where \(\delta_{v}(t)\) denotes the flow drop, defined as the number of packets sent and forwarded by node \(v\) and lost due to normal failures during a monitoring period \(t\). \(\delta_{v}\) is the highest value of \(d_{v}\) observed during the training phase \(T\). Formally, we have:  
\[d_{v}=\bigg{(}\sum_{\omega\in Child_{\omega}}f(\omega,v)+\frac{\Delta}{\Delta t }\bigg{)}-f(v,Parent_{v})\leq\delta_{v}\]The above constraint can also be written as:  
\[d_{v}=\left(\sum_{\omega\in Child_{u}}f(\omega,v)+\frac{\Delta}{\Delta t}\right)- \left(self_{0}+\sum_{\omega\in Child_{u}}g(\omega,v,Parent_{v})\right)\leq\delta_ {v}\]  
Proposition 1: \(d_{v}\) _is a path-free feature._  
Proof: Let us consider the path \(u\longrightarrow v\longrightarrow Parent_{v}\). Let \(u\) be a malicious node, which drops some packets. A feature is called dependent-path if and only if any increase in \(d_{u}\) will eventually increase \(d_{v}\). Let \(f^{t}(u,v)\), \(d^{t}_{v}\), \(self^{t}_{v}\), and \(g^{t}(u,v,Parent_{v})\) be the value of \(f(u,v)\), \(d_{v}\), \(self_{v}\) and \(g(u,v,Parent_{v})\) at time \(t\). \(d^{t}_{v}\) can be written as: \(\left(\sum_{\omega\in Child_{u}}f^{t}(\omega,v)+\frac{\Delta}{\Delta t}\right) -f^{t}(v,Parent_{v})\). At time \(t^{\prime}>(t+\Delta)\) node \(u\) starts behaving maliciously by dropping some/all packets, its \(d^{t^{\prime}}_{u}>\delta_{u}\), and it can be written as: \(\left(\sum_{\omega\in Child_{u}}f^{t^{\prime}}(\omega,u)+\frac{\Delta}{\Delta t }\right)-f^{t^{\prime}}(u,v)\).