Fortifying Intrusion Detection Systems in Dynamic Ad Hoc and Wireless Sensor Networks

Abstract

We investigate three aspects of dynamicity in ad hoc and wireless sensor networks and their impact on the efficiency of intrusion detection systems (IDSs). The first aspect is magnitude dynamicity, in which the IDS has to efficiently determine whether the changes occurring in the network are due to malicious behaviors or or due to normal changing of user requirements. The second aspect is nature dynamicity that occurs when a malicious node is continuously switching its behavior between normal and anomalous to cause maximum network disruption without being detected by the IDS. The third aspect, named spatiotemporal dynamicity, happens when a malicious node moves out of the IDS range before the latter can make an observation about its behavior. The first aspect is solved by defining a normal profile based on the invariants derived from the normal node behavior. The second aspect is handled by proposing an adaptive reputation fading strategy that allows fast redemption and fast capture of malicious node. The third aspect is solved by estimating the link duration between two nodes in dynamic network topology, which allows choosing the appropriate monitoring period. We provide analytical studies and simulation experiments to demonstrate the efficiency of the proposed solutions.

1. Introduction

Multihop ad hoc wireless networks are a set of nodes equipped with wireless interfaces, and data are forwarded through multiple nodes to reach the intended destinations. They include many types of networks such as mobile ad hoc networks (MANETs) [1], wireless sensor networks (WSNs) [2], and vehicular ad hoc networks (VANETs) [3].

In the last decade, there has been a substantial research in the area of security in ad hoc and wireless sensor networks [4, 5]. The security solutions have been designed with the goal of protecting the networks against some attacks such as selective forwarding, black hole, wormhole, sinkhole, and energy exhausting attack. Prevention mechanisms like key management and authentication, which represent the first line of defense, are not sufficient to provide an efficient security solution. Therefore, there is a need to deploy a second line of defence named intrusion detection system (IDS).

In general, intrusion detection systems are divided into two major approaches: misuse detection and anomaly detection [6]. Misuse detection performs signature analysis by comparing on-going activities with patterns representing known attacks, and those matched are labeled as intrusive attacks. The misuse approach is showing its limits as it cannot detect new attacks. Anomaly detection, on the other hand, builds profile of normal behavior and attempts to identify the patterns or activities that deviate from the normal profile. The main advantage of anomaly detection is that it can detect unknown attacks.

The detection model that we consider in the ad hoc and wireless sensor network is as follows. The IDS is implemented in a distributed manner; each node can act as a monitoring node that observes the behavior of its neighbors. Each observation lasts for a monitoring time interval of duration Δ, called the monitoring period. The IDS can judge whether the monitored node is normal or anomalous after one or multiple consecutive observations.

Although intrusion detection systems have received considerable attention in ad hoc and wireless sensor networks [7, 8], to the best of our knowledge, there are no studies on the impact of network dynamicity on IDS efficiency and how the IDS can react or adapt to these changes.

In this paper, we investigate the following three aspects of behavioral dynamicity that occur in the network and can negatively affect the IDS performance and efficiency.

• (i)

  Magnitude Dynamicity. Due to change of user requirements, a node changes the rate at which it generates data. For instance, a legitimate user wants to change (i.e., increase/decrease) the data collection rate received at the sink node. The challenge facing the IDS here is to be efficient at detecting attacks and distinguishing between the changes due to normal behaviors and the changes due to malicious attacks.

• (ii)

  Nature Dynamicity. In some detection models, a monitoring node has to observe the behavior of the monitored node during a set of consecutive monitoring periods before judging whether the monitored node is malicious or not. A monitored node might evade from IDS detection and confuses it by switching continuously its behavior between normal and anomalous. In this case, the malicious node strives to cause network disruption without being detected by the IDS.

• (iii)

  Spatiotemporal Dynamicity. The IDS detection mechanism is based on collecting a set of consecutive observations about the monitored node. An IDS is able to observe the behavior of the monitored node if the latter stays within the monitoring node's transmission range for a duration exceeding Δ. By knowing this fact, a malicious node can evade IDS detection by moving around in the network at a speed, which prevents it from being within the monitoring node's transmission range for a duration higher than Δ.

In this paper, we propose a solution for each aspect of dynamicity mentioned above. The contributions of the paper are threefold. Firstly, the magnitude dynamicity aspect is solved by defining a normal profile based on the invariants derived from the normal node behavior. This is achieved by generating a dependency graph consisting of strongly correlated features and then derives the high-level features from the graph. The high-level features are obtained by applying the divide-and-conquer strategy on the maximal cliques algorithm and the maximum weighted spanning tree algorithm. Secondly, to handle nature dynamicity aspect, we adopt the carrot and stick strategy (i.e., reward generously and punish severely) to prevent a malicious node from evading the IDS. To do so, we propose an adaptive reputation fading strategy to allow fast redemption and fast capture of malicious node. Thirdly, we use statistical analysis to estimate the link duration between two nodes in dynamic network topology. Based on this estimation, the monitoring node chooses the appropriate monitoring period, which allows it to observe the monitored node's behavior.

The rest of the paper is organized as follows. In Section 2, we describe the normal profile construction and the feature selection method. Section 3 presents the adaptive reputation fading strategy. In Section 4, we analyze link-node duration in a mobile wireless network and explain how the monitoring time period is estimated. Finally, Section 5 concludes the paper.

2. Magnitude Dynamicity

2.1. Background

2.1.1. One-Feature Profile

In the one-feature profile, we use a single feature to describe and detect anomalous behavior. To detect the network malicious behavior, a node can measure the following features, as shown in Table 1 [9]. The disadvantage of this profile structure is that there is a need to assign one feature for each known attack. In this case, the IDS has to measure each feature and check whether it has anomalous value. When the number of attacks increases, the detection speed of the IDS becomes slow. It also becomes slower when the size of rule set increases.

Table 1

Relation between attacks and features.

Attack	Feature
Packet sending rate	Energy exhausting attack
Packet dropping rate	Selective forwarding and black hole attacks
Packet receiving rate	Sinkhole attack
Packet sending power	Hello attack, wormhole attack

The one-feature profile might fail at distinguishing between normal and anomalous behaviors. Figure 1 shows that using some features individually to describe normal behavior is misleading and might make the detection system falsely accuse a legitimate node of being malicious. Figure 1(a) depicts a tree-based wireless network rooted at the sink B and it shows the normal traffic rates of the network. The value above each link indicates the flow rate traversing this link. Each node measures the flow rate coming from its upstream neighbors. Figure 1(b) (resp., Figure 1(c)) shows the state of the network when nodes D, H, and K become compromised and start behaving maliciously by dropping some packets (resp., generating more packets). As D, H, and K reduce (resp., increase) their sending rate, their respective downstream neighbors I and L have also to reduce (resp., increase) their sending rate accordingly. As a result, node B will falsely accuse nodes I and L of performing selective forwarding attack (resp., energy exhaustion attack), and hence a high false positive rate will be observed.

Figure 1

Impact of feature choice on false positive rate.

2.1.2. Multifeature Profile

In the multifeature profile, we describe the normal behavior by a d-feature vector and each element of the vector represents a feature. In this way, the IDS can determine whether some features together show an anomalous behavior. Experiments have shown that we can obtain better detection accuracy by combining related features rather than individually [10]. If node B in the example of Figure 1 considers two features: (a) the flow entering the monitored node and (b) the flow leaving the monitored node, it will conclude that nodes I and L are just forwarding what they received from their upstream neighbors, and hence they are not malicious.

Loo et al. [11] group the observed data into clusters and use a profile of 12 features to describe normal profile. To check whether a test instance belongs to a given cluster, they measure the Euclidian distance between the test point and the centroid of the cluster. If such a distance is higher than a threshold distance, the test point is considered anomalous. The following example shows that the Euclidian distance between two d-feature profiles reduces the detection accuracy. Let $(f{t}_{\mathrm{1}},f{t}_{\mathrm{2}})$ be a vector profile such that each feature of the vector is used to detect one attack. $f{t}_{\mathrm{1}}$ and $f{t}_{\mathrm{2}}$ take values in $[\mathrm{0,10}]$ . Let $(\mathrm{10,10})$ be the centroid vector. The first and the second attacks are detected when $f{t}_{\mathrm{1}}\le \mathrm{7}$ and $f{t}_{\mathrm{2}}\le \mathrm{6}$ , respectively. We take the distance between $(\mathrm{10,10})$ and $(\mathrm{7,6})$ , which is 5, as the threshold distance. Let a test vector be $(\mathrm{6,10})$ ; the distance between the two vectors is 4, which is lower than the distance threshold. In this case, the test point will be considered normal whereas the value of $f{t}_{\mathrm{1}}$ individually indicates the occurrence of an attack. The above example shows that aggregating features through the use of Euclidian distance result in loss of detection accuracy.

In [9, 12], the normal profile of a monitored node i is defined by a q-feature vector $f_i=(f{t}_{i\mathrm{1}},\dots ,f{t}_{iq})$ . If a node monitors a set of n nodes, it forms a matrix $F=(f_{\mathrm{1}},\dots ,f_n{)}^T$ . Both schemes assume that all feature vectors $f_i$ follow the same multivariate normal distribution with mean μ and variance-covariance matrix $\mathcal{M}$ . Node i is considered suspicious if the Mahalanobis distance between $f_i$ and the center of the set F is greater than a predefined threshold. The authors of both works use the orthogonalized Gnanadesikan-Kettenring estimation to find the center of the set F. Let $\widehat{\mu }$ and $\widehat{\mathcal{M}}$ denote the simple mean and the simple variance-covariance of F such that $\widehat{\mu }=(\mathrm{1}/n){\sum }_{i=\mathrm{1}}^n‍f_i$ and $\widehat{\mathcal{M}}=(\mathrm{1}/(n-\mathrm{1})){\sum }_{i=\mathrm{1}}^n‍(f_i-\widehat{\mu })(f_i-\widehat{\mu }{)}^T$ . The Mahalanobis distance between $f_i$ and the vector $\widehat{\mu }$ is given by $\sqrt{(f_i-\widehat{\mu }{)}^T{\widehat{\mathcal{M}}}^{-\mathrm{1}}(f_i-\widehat{\mu })}$ . The Mahalanobis distance differs from the Euclidian distance in that it takes into account the correlations between features. In [12], nodes are evaluated in terms of packet dropping rate, packet sending rate, forwarding delay time, and node readings. In [9], the attacks are detected by monitoring packet sending rate, packet dropping rate, packet mismatch rate, packet receiving rate, and received signal strength. As stated in [13], the works of [9, 12] suffer from two major criticisms: (1) the circumstances, under which the assumption of multivariate normal distribution holds, are not explained, and (2) the network features such as packet sending, packet dropping, and packet receiving rates do not follow the normal distribution for tree-based routing protocol.

2.2. Profile Construction Based on Strongly Correlated Features

When it comes to comparing distances, we find that the Mahalanobis distance is a powerful technique as it takes the covariances into account, which leads to elliptic decision boundaries in the 2D space. While the Euclidean distance builds circular boundaries and considers equal variances of the features, it appears that the Mahalanobis distance is more appropriate for multivariate data.

In our paper, we take a novel approach to select relevant features and construct the normal profile vector. We do not assume multivariate normal distribution and we feed only strongly correlated features to the distance measure unlike the Mahalanobis distance, which considers correlation between all features.

In the training phase, we investigate the significant associations between features. We are interested in identifying the level of correlation between those features, called Pearson's correlation coefficient, which measures the strength of the linear association between features. Pearson's correlation coefficient between two feature vectors X and Y is defined by

$$\begin{array}{cc}& \rho \left(X,Y\right)=\frac{\text{COV}\left(X,Y\right)}{{\sigma }_X{\sigma }_Y}=\frac{E\left[\left(x-{\mu }_X\right)\left(y-{\mu }_Y\right)\right]}{{\sigma }_X{\sigma }_Y},\end{array}$$

(1)

where ${\mu }_X$ (resp., ${\mu }_Y$ ) and ${\sigma }_X$ (resp., ${\sigma }_Y$ ) are the mean and standard deviation values of feature X (resp., feature Y). If $\rho (X,Y)=\mathrm{1}$ , then X and Y have a linear correlation. If $\mathrm{0.7}\le \rho (X,Y)<\mathrm{1}$ , then X and Y have a strong linear correlation, if $\mathrm{0.5}\le \rho (X,Y)<\mathrm{0.7}$ , then X and Y have a modest linear correlation, and if $\mathrm{0}\le \rho (X,Y)<\mathrm{0.5}$ , then X and Y are said to have a weak linear correlation.

The Pearson correlation indicates to what extent variables show a linear relationship (correlation) among them. The correlation takes its values in the range from −1 to +1. The extreme value +1 (resp., −1) informs about a perfect direct/increasing linear relationship (resp., inverse/decreasing). Indeed, strong relationship between variables is reflected by values close to the limits ( $-\mathrm{1}\le \rho \le -\mathrm{0.9}$ or $\mathrm{0.9}\le \rho \le +\mathrm{1}$ ) [14]. Pearson's correlation coefficient takes value 0 if we are in presence of independent variables. However, the reverse is not true since this coefficient deals only with figuring out linear dependencies between variables.

In our approach, we first use the training dataset F represented by $n\times d$ . F consists of n profile instances $f_i$ such that $i=\mathrm{1},\dots n$ , and each $f_i=(f{t}_{i\mathrm{1}},\dots ,f{t}_{id})$ . From F, we construct a correlation matrix Ω. The latter is a $d\times d$ matrix, where ${\Omega }_{ij}\in \mathbb{R}$ and $-\mathrm{1}\le {\Omega }_{ij}\le +\mathrm{1}$ :

$$\begin{array}{cc}& \Omega =\left(\begin{array}{cccc}{\Omega }_{\mathrm{11}}& {\Omega }_{\mathrm{12}}& \cdots & {\Omega }_{\mathrm{1}d}\\ {\Omega }_{\mathrm{21}}& {\Omega }_{\mathrm{22}}& \cdots & {\Omega }_{\mathrm{2}d}\\ ⋮& ⋮& \ddots & ⋮\\ {\Omega }_{d\mathrm{1}}& {\Omega }_{d\mathrm{2}}& \cdots & {\Omega }_{dd}\end{array}\right).\end{array}$$

(2)

We consider the set of d feature vectors $\{F_{\mathrm{1}},\dots ,F_d\}$ such that $F_i=\left(\begin{array}{c}f{t}_{\mathrm{1}i}\\ ⋮\\ f{t}_{ni}\end{array}\right)$ . For each pair of features $(F_i,F_j)$ , we compute ${\Omega }_{ij}=\rho (F_i,F_j)$ . Then, we derive a weighted graph $G=(V,E,w)$ from matrix Ω, defined as follows:

• (i)

  $V=\{v_{\mathrm{1}}\cdots v_d\}$ , the set of vertices (features) where $\left|V\right|=d$ ;

• (ii)

  $E=\{(v_i,v_j)$ , where $\mathrm{\hspace{0.17em}\hspace{0.17em}}{\Omega }_{ij}\ne \mathrm{0}\}$ and $\left|E\right|=m$ ;

• (iii)

  $w(v_i,v_j)=w_{ij}={\Omega }_{ij}$ .

A subgraph $G^{\left[\text{Th}\right]}=(V^{\left[\text{Th}\right]},E^{\left[\text{Th}\right]},w^{\left[\text{Th}\right]})$ is then induced from the graph G, where $\mathrm{0}<\text{Th}\le \mathrm{1}$ , by removing all the edges $(v_i,v_j)$ whose $w_{ij}<\text{Th}$ . $G^{\left[\text{Th}\right]}$ is defined as follows:

• (i)

  $E^{\left[\text{Th}\right]}=\{(v_i,v_j),\hspace{0.17em}\text{where}\mathrm{\hspace{0.17em}\hspace{0.17em}}{w}_{ij}\ge \text{Th}\}$ ;

• (ii)

  $V^{[\text{Th}]}=\{x\in V:\exists y\in V\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{and}\mathrm{\hspace{0.17em}\hspace{0.17em}}(x,y)\in E^{\left[\text{Th}\right]}\}$ , $\left|V^{\left[\text{Th}\right]}\right|\le d$ ;

• (iii)

  $w_{ij}^{[\text{Th}]}=w_{ij}$ .

The induced graph $G^{\left[\text{Th}\right]}$ from G might be composed of a set of disjoint connected partitions. The more the $\text{Th}$ is close to 1, the stronger the correlations exist in $G^{\left[\text{Th}\right]}$ .

We aim at finding the set of features that increase and decrease altogether in order to avoid the missed detection problem as in [11]. The best way to do so is to extract from G the set of cliques composed of strongly correlated features. One of the widely adopted solutions [15] to compute maximal cliques in an arbitrary graph of d vertices runs in time $O({\mathrm{3}}^{d/\mathrm{3}})=O(\mathrm{1.4}{\mathrm{4}}^d)$ . Instead of applying the maximal cliques algorithm on graph G, we propose to adopt the divide and conquer strategy by applying this algorithm on each connected component of the subgraph $G^{\left[\text{Th}\right]}$ . A clique ${\text{CL}}_i^{\left[\text{Th}\right]}=(V_i^{\left[\text{Th}\right]},E_i^{\left[\text{Th}\right]})$ ( $i\ge \mathrm{1}$ ) of a graph $G^{\left[\text{Th}\right]}$ is a set of vertices $V_i^{\left[\text{Th}\right]}\subseteq V^{\left[\text{Th}\right]}$ such that all the pairs of $C_i^{\left[\text{Th}\right]}$ are adjacent. This strategy significantly reduces the computational complexity to find maximal strongly correlated cliques. Let us consider that $G^{\left[\text{Th}\right]}$ is composed of d vertices belonging to a set of M connected components. Each connected component $P_i\mathrm{\hspace{0.17em}\hspace{0.17em}}i=\mathrm{1}\cdots M$ is composed of $S_i$ vertices. There are α singleton vertices and β partitions with two vertices, and the rest of connected components are composed of more than two vertices. The computational complexity incurred by applying the maximal cliques algorithm on graph G is

$$\begin{array}{cc}& \mathrm{1.4}{\mathrm{4}}^d=\mathrm{1.4}{\mathrm{4}}^{(\alpha +\mathrm{2}\beta +{\sum }_{j:S_j>\mathrm{2}}^{}{S}_j)}=\mathrm{1.4}{\mathrm{4}}^{\alpha }\mathrm{1.4}{\mathrm{4}}^{\mathrm{2}\beta }{\displaystyle \prod }_{j:S_j>\mathrm{2}}‍\mathrm{1.4}{\mathrm{4}}^{S_j}.\end{array}$$

(3)

By applying the same algorithm on each connected partition of $G^{\left[\text{Th}\right]}$ , we notice that there is no need to apply it on isolated vertices and the partitions of two vertices are cliques by definition, and hence we get the following computational complexity: ${\sum }_{j:S_j>\mathrm{2}}‍\mathrm{1.4}{\mathrm{4}}^{S_j}$ . It is obvious that applying the divide and conquer strategy can significantly reduce the running time of the algorithm and make it suitable for resource-constrained nodes.

Let ϕ be the set of edges belonging to all cliques in $G^{\left[\text{Th}\right]}$ , and $\left|\varphi \right|=d^{\prime }$ . For each edge $(F_l,F_k)$ , which is the tth element of ϕ ( $t=\mathrm{1},\dots ,d^{\prime }$ ), we define a high-level feature $H_t=F_l/F_k$ . From the training dataset F, we derive its high-level training dataset $HF$ defined as follows; for each d-profile vector $f_i\in F$ , we derive its $d^{\prime }$ -profile high-level vector $g_i=(g{t}_{i\mathrm{1}},\dots ,g{t}_{i{d}^{\prime }})$ , such that $g{t}_{it}=f{t}_{il}/f{t}_{ik}$ and $f{t}_{ik}\ne \mathrm{0}$ . If $f{t}_{ik}=\mathrm{0}$ , the high-level vector $g_i$ is then removed from the training dataset $HF$ . This choice is justified by the fact that the stronger the correlation between $F_l$ and $F_k$ is, the more the data instances of $(F_l,F_k)$ fall on the same straight line $F_l=a{F}_k+b$ , where a is the slope and b is the intercept.

The high-level features belonging to the same clique ${\text{CL}}_i^{[\text{Th}]}$ are grouped into a single vector ${\xi }_i$ . We consider that K cliques are obtained from $G^{\left[\text{Th}\right]}$ . Thus, the normal profile is then defined as the set of vectors ${\xi }_i$ ( $i=\mathrm{1},\dots ,K$ ). To further reduce the number of features in each vector ${\xi }_i$ , we apply the maximum weighted spanning tree algorithm on each clique. To do so, we apply Kruskal's algorithm originally used to obtain the minimum spanning tree by negating the weight of each edge [16]. The high-level features, whose edges do not belong to the tree, are removed from the normal profile. The resulted profile is called the minimum normal profile. The time complexity of the maximum weighted spanning tree is $O(|E_{\text{CL}}|\log |E_{\text{CL}}|)$ , where $E_{\text{CL}}$ is the number of edges in the clique. As $\left|E_{\text{CL}}\right|=\left|V_{\text{CL}}\right|(|V_{\text{CL}}|-\mathrm{1})/\mathrm{2}$ , the time complexity becomes proportional to $O(|E_{\text{CL}}|\log |V_{\text{CL}}|)$ . As the maximal cliques algorithm, the maximum weighted spanning tree is only applied on cliques with more than two vertices. The use of maximum weighted spanning tree is justified by the fact that all the low-level features of each clique in $G^{\left[\text{Th}\right]}$ have strong correlation between them. In each clique, if X and Y are strongly correlated and Y and Z are strongly correlated, then X and Z are strongly correlated. Hence, we can remove the redundant $(X,Z)$ edge from the clique.

To illustrate further the above method, we consider an example of seven network features, namely, $F_{\mathrm{1}}$ , $F_{\mathrm{2}}$ , $F_{\mathrm{3}}$ , $F_{\mathrm{4}}$ , $F_{\mathrm{5}}$ , $F_{\mathrm{6}}$ , and $F_{\mathrm{7}}$ . The correlation coefficient matrices Ω between these features are

$$\begin{array}{cc}& \Omega =\begin{array}{cc}& \begin{array}{ccccccc}\hspace{0.5em}{F}_{\mathrm{1}}& \hspace{0.5em}{F}_{\mathrm{2}}& \hspace{0.5em}{F}_{\mathrm{3}}& \hspace{0.5em}{F}_{\mathrm{4}}\hspace{0.5em}& \hspace{0.5em}{F}_{\mathrm{5}}\hspace{0.5em}& \hspace{0.5em}{F}_{\mathrm{6}}\hspace{0.5em}\hspace{0.17em}& \hspace{0.17em}\hspace{0.17em}{F}_{\mathrm{7}}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\end{array}\\ \begin{array}{c}{F}_{\mathrm{1}}\\ F_{\mathrm{2}}\\ F_{\mathrm{3}}\\ F_{\mathrm{4}}\\ F_{\mathrm{5}}\\ F_{\mathrm{6}}\\ F_{\mathrm{7}}\end{array}& \left(\begin{array}{ccccccc}\mathrm{1}& \mathrm{0.93}& \mathrm{0.97}& \mathrm{0.25}& \mathrm{0.73}& \mathrm{0.82}& \mathrm{0.98}\\ \mathrm{0.93}& \mathrm{1}& \mathrm{0.99}& \mathrm{0.81}& \mathrm{0.54}& \mathrm{0.62}& \mathrm{0.94}\\ \mathrm{0.97}& \mathrm{0.99}& \mathrm{1}& \mathrm{0.73}& \mathrm{0.87}& \mathrm{0.43}& \mathrm{0.95}\\ \mathrm{0.25}& \mathrm{0.81}& \mathrm{0.73}& \mathrm{1}& \mathrm{0.98}& \mathrm{0.52}& \mathrm{0.71}\\ \mathrm{0.73}& \mathrm{0.54}& \mathrm{0.87}& \mathrm{0.98}& \mathrm{1}& \mathrm{0.78}& \mathrm{0.60}\\ \mathrm{0.82}& \mathrm{0.62}& \mathrm{0.43}& \mathrm{0.52}& \mathrm{0.78}& \mathrm{1}& \mathrm{0.53}\\ \mathrm{0.98}& \mathrm{0.94}& \mathrm{0.95}& \mathrm{0.71}& \mathrm{0.60}& \mathrm{0.53}& \mathrm{1}\end{array}\right)\end{array}.\end{array}$$

(4)

According to the correlation matrix, we generate the graph $G^{\left[\text{Th}\right]}$ , where $\text{Th}>\mathrm{0.9}$ as shown in Figure 2(a). In the graph, there are two cliques: $\{F_{\mathrm{1}},F_{\mathrm{2}},F_{\mathrm{3}},F_{\mathrm{7}}\}$ and $\{F_{\mathrm{4}},F_{\mathrm{5}}\}$ .

Figure 2

Graph-based normal behavioral model.

The network normal profile is defined as $\{(F_{\mathrm{1}}/F_{\mathrm{2}}$ , $F_{\mathrm{1}}/F_{\mathrm{3}}$ , $F_{\mathrm{1}}/F_{\mathrm{7}}$ , $F_{\mathrm{2}}/F_{\mathrm{3}}$ ,    $F_{\mathrm{2}}/F_{\mathrm{7}}$ , $F_{\mathrm{3}}/F_{\mathrm{7}})$ , $(F_{\mathrm{4}}/F_{\mathrm{5}})\}$ . After applying the maximum weighted spanning tree algorithm, the edges $(F_{\mathrm{1}},F_{\mathrm{2}})$ , $(F_{\mathrm{2}},F_{\mathrm{7}})$ , and $(F_{\mathrm{3}},F_{\mathrm{7}})$ are removed, and the minimum normal profile becomes $\{(F_{\mathrm{1}}/F_{\mathrm{3}},F_{\mathrm{2}}/F_{\mathrm{3}},F_{\mathrm{1}}/F_{\mathrm{7}})$ , $(F_{\mathrm{4}}/F_{\mathrm{5}})\}$ .

Proposition 1.

For any data set of d low-level features, the number of high-level features induced by the graph-based generation method is upper-bounded by $d-K$ , such that K is the number of cliques in $G^{\left[Th\right]}$ .

Proof.

Consider $V^{\left[\text{Th}\right]}\subseteq V$ ; that is, in the worst case, each low-level feature belongs to a given clique ${\text{CL}}_i^{\left[\text{Th}\right]}$ ( $i\ge \mathrm{1}$ ). As a result, ${\sum }_{i=\mathrm{1}}^K‍\left|V_i^{\left[\text{Th}\right]}\right|\le d$ . It is known that the number of edges induced by executing the maximum weighted spanning tree on the clique ${\text{CL}}_i^{\left[\text{Th}\right]}$ is $h_i=\left|V_i^{\left[\text{Th}\right]}\right|-\mathrm{1}$ . As ${\sum }_{i=\mathrm{1}}^K‍(h_i+\mathrm{1})\le d$ , ${\sum }_{i=\mathrm{1}}^K‍h_i\le d-K$ . Thus, the number of edges (i.e., high-level features) induced by executing the maximum weighted spanning tree on all the cliques of $G^{\left[\text{Th}\right]}$ is upper-bounded by $d-K$ .

2.3. Detection Process

Each node constructs its local dataset represented by $n\times d$ matrix (i.e., n vector instances and d features). It then extracts K cliques from this dataset, as shown above, as well as its minimum profile composed of K vectors ${\xi }_l$ of size $m_l$ , where $l=\mathrm{1},\dots ,K$ . The node computes the centroid vector $C_l$ for all the n instances of ${\xi }_l$ .

To check whether a profile Z is normal or anomalous, we derive from Z its corresponding high-level profile $HZ$ and we execute the pseudocode depicted in Algorithm 1. In the algorithm, $\text{Dis}$ denotes the Euclidian distance between two vectors. ${\text{Low}}^l$ and ${\text{Up}}^l$ denote the lowest and highest values obtained from estimating $\text{Dis}({\xi }_l,C_l)$ for all the n instances of ${\xi }_l$ .

Algorithm 1: Intrusion detection algorithm.

(1) Let Z be the high-level test profile composed of $Z_l$ vectors ( $l=\mathrm{1},\dots ,K$ )

(2) forAll vectors $C_l$ such that: $l=\mathrm{1},\dots ,K$ do

(3) if $(Dis(Z_l,C_l)\notin [Lo{w}^l,U{p}^l])$ then

(4) return Z is anomalous

(5) end if

(6) end for

(7) return Z is normal;

2.4. Simulation Results

We study the performance of the proposed IDS using GloMoSim simulator [17]. Each node sends one packet/sec toward the sink. A watchdog is implemented at each node and its role is to monitor the network activities of all the node's neighbors. At every 10 seconds (i.e., one time period), a monitoring node i measures the feature vector of its monitored node j. After a training phase of T time periods, testing phase lasts for 1800 seconds. The role of IDS, which is implemented at a node i, is not just to detect if i's neighbor (node j) is malicious or not but also to detect if node j is malicious during a given time period. We evaluate the performance of the IDS using two metrics: detection rate and false positive rate. We select the following five quantitative features:

• (i)

  number of generated packets (GEN),

• (ii)

  number of received packets (RCV),

• (iii)

  number of forwarded packets (FWD),

• (iv)

  number of sent packets (SENT),

• (v)

  number of lost packets (LOSS).

We generate then the correlation matrix Ω as well as the minimum normal profile after performing the maximal cliques algorithm and the maximum weighted spanning tree algorithm as shown in Figure 3:

$$\begin{array}{cc}& \Omega =\begin{array}{cc}& \begin{array}{ccccc}\text{GEN}\hspace{0.5em}& \text{RCV}& \hspace{0.5em}\text{FWD}& \text{SENT}& \text{LOSS}\end{array}\\ \begin{array}{c}\text{GEN}\\ \text{RCV}\\ \text{FWD}\\ \text{SENT}\\ \text{LOSS}\end{array}& \left(\begin{array}{ccccc}1& \mathrm{0.4205}& \mathrm{0.4205}& \mathrm{0.7263}& \mathrm{0.6032}\\ \mathrm{0.4205}& 1& 1& \mathrm{0.9289}& \mathrm{0.9727}\\ \mathrm{0.4205}& 1& 1& \mathrm{0.9289}& \mathrm{0.9727}\\ \mathrm{0.7263}& \mathrm{0.9289}& \mathrm{0.9289}& 1& \mathrm{0.9828}\\ \mathrm{0.6032}& \mathrm{0.9727}& \mathrm{0.9727}& \mathrm{0.9828}& 1\end{array}\right)\end{array}.\end{array}$$

(5)

Figure 3

Normal profile and minimum normal profile.

Figure 4 shows the detection rate of the proposed IDS as a function of dropping probability. The first observation that we can draw from the figure is that the detection rate is 100% when the dropping probability is higher than 0.05, and it is under 100% when the dropping probability is $\le$ 0.02. This can be explained as follows: under very low dropping probabilities, the malicious nodes drop packets at low intensities and their activities become unnoticeable. This happens when the dropping probability becomes very close to or less than the normal packet loss, which is at most 2% during each time period. Figure 5 shows the detection rate of the IDS as a function of training period. The results are presented under the following levels of dropping probability $P=\mathrm{1,0.5,0.1},\mathrm{0.05,0.01}$ . The results show that the detection rate does not depend on the training period but on the dropping probability. Under high dropping probabilities, the detection rate is 100% for all the training periods. Under low dropping probabilities, the detection rate decreases as the malicious behavior becomes very close to the normal one.

Figure 4

Detection rate versus dropping probability.

Figure 5

Detection rate versus training time.

Figure 6 shows the false positive rate of IDS as a function of training period under the following levels of dropping probability $P=\mathrm{0.8,0.5,0.1,0.05,0.03,0.01}$ . We can notice that the false positive becomes 0 when the training period $T=\mathrm{30}$ for all $P>\mathrm{0.02}$ . At $T=\mathrm{30}$ , the IDS has learned all the possible instances of the normal profile and can accurately distinguish between normal and anomalous traffic. When $T<\mathrm{30}$ , the IDS still has not learned all the instances of the normal profile. In other words, the normal profiles, which are not observed during the training phase, will be considered anomalous during the testing phase. Thus, the false positive rate depends in this case on the number of times unlearned normal profiles are observed during the testing phase, which itself depends on the number of lost packets that are due to $(1)$ normal packet loss and $(2)$ dropping activities. As packet loss is an event that occurs randomly, the false positive curves are also random when $T<\mathrm{30}$ . For $P=\mathrm{0.01}$ , the false positive becomes $\mathrm{0}$ only when $T=\mathrm{40}$ . Given that the behavior of the malicious node becomes very close to the legitimate node, the IDS needs more time to learn about new instances of the normal profile.

Figure 6

False positive rate.

3. Nature Dynamicity

3.1. Background: Constant Fading Reputation Strategy

Reputation is defined as the general opinion of a society of nodes towards a certain node in a specific domain of interest, and it is the global perception on the future behavior of this node. In the IDS based on multiple observations, the IDS collects a series of consecutive observations, each of which occurs during a separate monitoring period.

Since reputation aggregates past experiences and dynamically evolves, it is similar to Bayesian analysis, which is a statistical procedure that estimates parameters of an underlying distribution based on observations. Starting with prior distribution, which is the initial state before any observation is made, Bayesian analysis continuously takes into account new experiences and derives posterior probability [18]. One of the used distributions in Bayesian analysis is Beta distribution.

Beta distribution has been recognized as a useful formal tool to model reputation [18–20]. A reputation value assumes a tuple of $(\alpha ,\beta \ge \mathrm{1})$ such that α and β represent positive and negative observations, respectively.

The Beta distribution and its probability density function (PDF) are defined as follows:

$$\begin{array}{l}\hspace{1em}B(\alpha ,\beta )={{\displaystyle \int }}_{\mathrm{0}}^{\mathrm{1}}‍t^{\alpha -\mathrm{1}}{\left(\mathrm{1}-t\right)}^{\beta -\mathrm{1}}dt\\ \hspace{1em}\hspace{1em}\hspace{1em}f\left(p\mid \alpha ,\beta \right)=\frac{\mathrm{1}}{B\left(\alpha ,\beta \right)}{p}^{\alpha -\mathrm{1}}{\left(\mathrm{1}-p\right)}^{\beta -\mathrm{1}},\\ \text{where}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{0}\le p\le \mathrm{1},\hspace{1em}\alpha ,\beta \ge \mathrm{0}.\end{array}$$

(6)

The reputation, denoted by R, is defined as the expectation (denoted by $\mathbb{E}$ ) of the Beta distribution, and it takes the following simple form:

$$\begin{array}{cc}& R=\mathbb{E}\left(B\left(\alpha ,\beta \right)\right)=\frac{\alpha }{\alpha +\beta }.\end{array}$$

(7)

We model the reputation of a node with a Beta distribution ( $\alpha ,\beta$ ). Initially, $\alpha =\mathrm{1}$ and $\beta =\mathrm{1}$ .

The standard Bayesian procedure is as follows. Initially, the prior is $\text{Beta}(\mathrm{1,1})$ , the uniform distribution on $[\mathrm{0,1}]$ . Then, when a new observation is made, say with n observed misbehaviors and p observed correct behaviors, the prior is updated according to $\alpha :=\alpha +p$ and $\beta :=\beta +n$ . The reputation relies on the node's direct observation. When the monitoring node makes one individual observation about the monitored node, it updates α and β as follows.

• (i)

  If the observation is qualified as misbehavior, β is set to $\beta +\mathrm{1}$ .

• (ii)

  If the observation is qualified as correct behavior, α is set to $\alpha +\mathrm{1}$ .

The standard Bayesian method is modified in [19] to give less weight to the observations received in the past so as to allow reputation fading and prevent any node from capitalizing on its previous good behavior forever. To achieve this aim, a discount factor for past observations is used. When a new observation $(p,n)$ is made, α and β are updated as follows:

$$\begin{array}{l}\hspace{1em}\hspace{1em}\alpha :=\omega \alpha +p,\\ \hspace{1em}\hspace{1em}\beta :=\omega \beta +n,\\ \text{where}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{0}\le \omega \le \mathrm{1}.\end{array}$$

(8)

The weight ω is a constant discount factor for past observations, which serves as the fading mechanism. We refer hereafter to the reputation system described above as the constant fading reputation strategy.

3.2. Adaptive Fading Reputation Strategy

The constant fading reputation mechanism uses the same discount factor for all types of observations and during all the time. The higher (resp., lower) the value of ω is, the slower (resp., quicker) the histories are forgotten. By knowing the value of ω, a malicious node can evade from IDS detection by misbehaving for a given time and goes back to normal behavior. Under high discount factor, the change of node behavior (from well-behaved to misbehaved and vice versa) will be detected after a long time. During this time, well-behaved nodes can count on their good histories and act maliciously. In addition, misbehaved nodes will have to wait a longer time to redeem themselves. On the other hand, a low discount factor permits a quicker detection redemption of nodes. However, it might raise false alarms especially when network faults and attacks both share the same failure symptoms. For instance, a misbehavior is detected if the observed node is not forwarding a packet. This rule is set to detect black hole and selective forwarding attacks. In addition, this rule is applied when packets are not forwarded due to collisions, which means that a well-behaved observed node might be falsely considered malicious.

To deal with this issue, we propose an adaptive fading reputation mechanism. This mechanism uses the carrot and stick strategy; that is, reward the well-behaved node and punish the misbehaved node. The adaptive mechanism uses two types of discount factors: one for past positive observations and the second one for past negative observations. The value of the discount factors is adjusted as function of reputation R as shown in Figure 7.

Figure 7

Positive and negative discount factors.

In the adaptive fading reputation mechanism, when a new observation $(p,n)$ is made, α and β are updated as follows:

$$\begin{array}{l}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\alpha :=\psi \left(R\right)\alpha +p,\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\beta :=\phi \left(R\right)\beta +n,\\ \text{where}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{0}\le \psi \left(R\right),\hspace{1em}\phi \left(R\right)\le \mathrm{1}.\end{array}$$

(9)

$\psi (R)$ and $\phi (R)$ denote the discount factors for past positive and negative histories, respectively, whose values fall into the range of $[\mathrm{0,1}]$ . According to the value of R, a reputation system executes the following two fading strategies.

• (i)

  Reward Strategy. It is applied when the reputation $R\ge \text{th}$ , such that $\text{th}\in [\mathrm{0,1}]$ . The IDS forgets the negative history more quickly than the positive one (i.e., $\psi (R)>\phi (R)$ ); this strategy is used when a node is well-behaved.

• (ii)

  Punishment Strategy. It is applied when the reputation $R<\text{th}$ . The IDS forgets the positive history more quickly than the negative one (i.e., $\psi (R)<\phi (R)$ ); this strategy is used when a node is misbehaved.

Formally, $\psi (R)$ and $\phi (R)$ are written as follows:

$$\begin{array}{cc}& \psi \left(R\right)=\left\{\begin{array}{cc}\left(\frac{{\text{PR}}_{\max }-{\text{PR}}_{\min }}{\mathrm{1}-t}\right)R+\frac{{\text{PR}}_{\min }-{\text{PR}}_{\max }\times t}{\mathrm{1}-t},\hfill & \hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\text{when}\mathrm{\hspace{0.17em}\hspace{0.17em}}R\ge t,\hfill & \hfill \\ \left(\frac{{\text{PP}}_{\max }-{\text{PP}}_{\min }}{t}\right)R+{\text{PP}}_{\min },\hfill & \hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\text{when}\mathrm{\hspace{0.17em}\hspace{0.17em}}R<t,\hfill & \hfill \end{array}\right.\\ \phi \left(R\right)=\left\{\begin{array}{cc}\left({\text{PR}}_{\max }+{\text{NR}}_{\min }\right)-\psi \left(R\right),\hfill & \text{when}\mathrm{\hspace{0.17em}\hspace{0.17em}}R\ge t,\hfill \\ \left({\text{NP}}_{\max }+{\text{PP}}_{\min }\right)-\psi \left(R\right),\hfill & \text{when}\mathrm{\hspace{0.17em}\hspace{0.17em}}R<t,\hfill \end{array}\right.\end{array}$$

(10)

where ${\text{PR}}_{\max }$ and ${\text{PR}}_{\min }$ are the upper and the lower bounds of the positive discount factor, respectively, under reward strategy. ${\text{NR}}_{\max }$ and ${\text{NR}}_{\min }$ are the upper and the lower bounds of the negative discount factor, respectively, under reward strategy. ${\text{PP}}_{\max }$ and ${\text{PP}}_{\min }$ are the upper and the lower bounds of the positive discount factor, respectively, under punishment strategy. ${\text{NP}}_{\max }$ and ${\text{NP}}_{\min }$ are the upper and the lower bounds of the negative discount factor, respectively, under punishment strategy.

For new nodes, positive and negative histories are kept with a discount factor equal to 1 when the number of observations is less than a given value named experience threshold.

From the above upper and lower bounds, we define the following two distance metrics.

• (i)

  Punish-to-Reward (PTR) Distance. It is defined by ${\text{PR}}_{\min }-{\text{PP}}_{\max }$ , and it shows to what extent the node is rewarded by the IDS when it transits from the misbehaved state to the well-behaved state; that is, the higher the PTR is, the slower the positive histories are forgotten.

• (ii)

  Reward-to-Punish (RTP) Distance. It is defined by ${\text{NP}}_{\min }-{\text{NR}}_{\max }$ , and it shows to what extent the node is punished by the IDS when it transits from the well-behaved state to the misbehaved state; that is, the higher the RTP is, the slower the negative histories are forgotten.

3.3. Performance of Adaptive Discount Factor Strategy

We evaluate the performance of the constant and adaptive discount factor strategies in terms of detection time. To do so, we implement three behavioral models.

• (i)

  Deterministic redemption model: in this model, a node with reputation $R=\mathrm{0}$ behaves correctly in the network.

• (ii)

  Deterministic evasion model: in this model, a node with reputation $R=\mathrm{1}$ behaves maliciously in the network.

• (iii)

  Probabilistic evasion model: the node's behavior is modeled with a two-state Markov chain as depicted in Figure 8. In state N, the node is well-behaved, and, in state M, the node is misbehaved. Initially, the node's reputation $R=\mathrm{1}$ . The node transits towards state N with probability $P_N$ and towards state M with probability $P_M$ , such that $P_N+P_M=\mathrm{1}$ . $P_M$ is called the evasion probability. The time spent in state N and state M is the monitoring time period.

Figure 8

Probabilistic evasion model.

The parameters for the experiment are shown in Table 2. We define three settings for the adaptive fading reputation.

• (i)

  Setting 1: $\text{PTR}$ and $\text{RTP}$ are high; for example, they equal 0.7.

• (ii)

  Setting 2: $\text{PTR}$ and $\text{RTP}$ are medium; for example, they equal 0.3.

• (iii)

  Setting 3: $\text{PTR}$ and $\text{RTP}$ are low; for example, they equal 0.1.

Table 2

Experiment parameters.

Parameter	Setting 1	Setting 2	Setting 3
$\text{N}{\text{P}}_{\max }$ , $\text{P}{\text{R}}_{\max }$	$\mathrm{1}$	$\mathrm{1}$	$\mathrm{1}$
$\text{P}{\text{R}}_{\min }$ , $\text{N}{\text{P}}_{\min }$	$\mathrm{0.9}$	$\mathrm{0.9}$	$\mathrm{0.9}$
$\text{P}{\text{P}}_{\max }$ , $\text{N}{\text{R}}_{\max }$	$\mathrm{0.2}$	$\mathrm{0.6}$	$\mathrm{0.8}$
$\text{N}{\text{R}}_{\min }$ , $\text{P}{\text{P}}_{\min }$	$\mathrm{0.1}$	$\mathrm{0.5}$	$\mathrm{0.7}$
ω	$\mathrm{0.2,0.5,0.8}$
$th$	$\mathrm{0.5}$

As for constant fading reputation, we define three levels of discount factor $\omega =\mathrm{0.2,0.5,0.8}$ .

We study the evolution of reputation over time when applying constant and adaptive discount factor. In Figure 9(a), the convergence time increases as ω increases. This is because higher (resp., lower) values of ω mean that the negative histories are forgotten at slower (resp., faster) rate, which leads to longer (resp., shorter) time to converge to $R=\mathrm{1}$ . In Figure 9(b), we observe that the deterministic redemption model under adaptive discount factor strategy requires less converge time than the constant one. It ranges between 3 and 9 observations under setting 1 and setting 3, respectively. The reason for this is that a node under setting 1 is rewarded more generously as long as it is well-behaving; that is, its positive histories are forgotten slower than those of setting 2 and setting 3.

Figure 9

Deterministic redemption model.

In Figure 10, we also notice that the malicious node that follows the deterministic evasion is detected more quickly when the adaptive discount factor strategy is applied. The time to converge to $R=\mathrm{0}$ is between 3 and 9 observations under the adaptive discount factor strategy and between 4 and 14 observations under the constant discount factor strategy. For instance, let $R=\mathrm{0.1}$ be the boundary between malicious behavior and normal behavior; the malicious node can evade IDS detection for a time required to collect only 3 observations if the IDS adopts the adaptive discount factor strategy under setting 3. Under the constant discount factor strategy and if $\omega =\mathrm{0.8}$ , IDS can detect the malicious after a time period of 5 observations.

Figure 10

Deterministic evasion model.

By knowing the required number of observations to detect a malicious node, the latter can adopt the probabilistic evasion model, which do discontinuous harm to the network to confuse the IDS and hence evade detection. Figures 11, 12, and 13 show that the adaptive discount factor strategy can quickly detect this type of behavior. In the figures, we consider that a node is malicious when $R=\mathrm{0.1}$ . When the evasion probability $P_M=\mathrm{0.5}$ , the adaptive strategy succeeds at detecting the malicious node after a time between 2 and 37 observations. On the other hand, the malicious node can evade the IDS adopting the constant strategy for a time of 751 observations when $\omega =\mathrm{0.8}$ . This value decreases to 10 and 2 when $\omega =\mathrm{0.5}$ and $\omega =\mathrm{0.2}$ , respectively. When $P_M=\mathrm{0.6}$ , the detection time decreases to 40 and 27 under $\omega =\mathrm{0.8}$ and setting 3, respectively. When $P_M$ is between $\mathrm{0.7}$ and $\mathrm{0.9}$ , the adaptive strategy (resp., constant strategy) achieves a detection time between 2 and 4 (resp., between 2 and 5) observations.

Figure 11

Probabilistic evasion model ( $P_M=\mathrm{0.5}$ ).

Figure 12

Probabilistic evasion model ( $P_M=\mathrm{0.6}$ ).

Figure 13

Probabilistic evasion model ( $P_M=\mathrm{0.7,0.8,0.9}$ ).

4. Spatiotemporal Dynamicity

A monitoring node i can make at least one observation about a monitored node j if the wireless link lasts for a duration higher than the monitoring period Δ. The malicious node j, which knows this fact, can move around in the network to create links with its neighbors of duration less than Δ.

As shown in Figure 14, the nodes start operating at time $t_{\mathrm{0}}$ . A wireless link between the monitoring node i and monitored node j is created at time $t_{\mathrm{1}}$ when node j comes within the transmission range of node i. Node i loses its link with node j either $(1)$ when node j moves out of the transmission range of node i at time $t_{\mathrm{2}}$ or $(2)$ when node j runs out of its battery power at time $t_{\mathrm{3}}$ . Therefore, node i estimates the link-node lifetime by the following equation: $\min (t_{\mathrm{2}}-t_{\mathrm{1}},t_{\mathrm{3}}-t_{\mathrm{1}})$ . $(t_{\mathrm{2}}-t_{\mathrm{1}})$ is the estimation of the link lifetime and $(t_{\mathrm{3}}-t_{\mathrm{1}})$ is the residual node lifetime after node j has been in existence for $(t_{\mathrm{1}}-t_{\mathrm{0}})$ time units.

Figure 14

Link-node lifetime.

In this section, we statistically analyze the link-node distribution. Based on this analysis, we choose appropriate values for the monitoring period so that the mobile monitored node cannot evade IDS detection. We use the random waypoint mobility model, in which each mobile node randomly selects a location, within an area of 100 m × 100 m, with a random speed uniformly distributed between 0 and a certain maximum speed $V_{\max }$ ; then it stays stationary during a pause time of $\mathrm{1}$ second before moving to a new random location. In our analysis, we consider two different numbers of nodes ( $\text{NN}$ ), that is, 10 and 20 nodes.

4.1. Link Lifetime Distribution

We obtain from our simulation the frequency of link durations and plot them into a histogram, as shown in Figures 15 and 16. The EasyFit software [21, 22] is used to measure the compatibility of a random sample with the theoretical probability distribution functions. As shown in the figures, the software approximates the simulation data to a Weibull distribution [23] with two parameters $\alpha =\mathrm{1.031}$ and $\beta =\mathrm{28.74}$ (resp., $\alpha =\mathrm{1.029}$ and $\beta =\mathrm{32.85}$ ) when $V_{\max }=\mathrm{20}$ and $\text{NN}=\mathrm{10}$ (resp., $\text{NN}=\mathrm{20}$ ). Weibull distribution has a PDF as shown in the following equation:

$$\begin{array}{cc}& f\left(x;\alpha ,\beta \right)=\frac{\alpha }{\beta }{\left(\frac{x}{\beta }\right)}^{\alpha -\mathrm{1}}{e}^{-{\left(x/\beta \right)}^{\alpha }}.\end{array}$$

(11)

Figure 15

Link lifetime distribution under $\text{NN}=\mathrm{10}$ and $V_{\max }=\mathrm{20}$ .

Figure 16

Link lifetime distribution under $\text{NN}=\mathrm{20}$ and $V_{\max }=\mathrm{20}$ .

Based on the properties of the Weibull distribution, the mean (expected value) is

$$\begin{array}{cc}& \text{Mean}=\beta \times \Gamma \left(\frac{\alpha +\mathrm{1}}{\alpha }\right).\end{array}$$

(12)

On the other hand, Samar and Wicker [24, 25] have described the expected link lifetime as a function of node velocity, say $v_{\mathrm{1}}$ , with the following equation:

$$\begin{array}{l}{F}_{\text{link}}^{v_{\mathrm{1}}}=\frac{R}{\mathrm{2}\left(b-a\right)}\\ \hspace{1em}\hspace{1em}\hspace{1em}\times \left({{\displaystyle \int }}_{\pi }^{\mathrm{0}}‍\log \left|\frac{b+\sqrt{b^{\mathrm{2}}-v_{\mathrm{1}}^{\mathrm{2}}{\sin }^{\mathrm{2}}\varphi }}{v_{\mathrm{1}}+v_{\mathrm{1}}\cos \varphi }\right|d\varphi \right.\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\left.-{{\displaystyle \int }}_{\pi }^{{\varphi }_{\mathrm{0}}}‍\log \left|\frac{a+\sqrt{a^{\mathrm{2}}-v_{\mathrm{1}}^{\mathrm{2}}{\sin }^{\mathrm{2}}\varphi }}{a-\sqrt{a^{\mathrm{2}}-v_{\mathrm{1}}^{\mathrm{2}}{\sin }^{\mathrm{2}}\varphi }}\right|d\varphi \right),\end{array}$$

(13)

where R is the radius of the circle centered at the node. $v_{\mathrm{1}}$ is uniformly distributed between a and b, expressed in meters/second. ϕ is the direction of motion: ${\varphi }_{\mathrm{0}}=\pi -{\sin }^{-\mathrm{1}}(a/v_{\mathrm{1}})$ .

Since (12) and (13) are both describing the expected value of the link lifetime, we can write

$$\begin{array}{l}\beta \Gamma \left(\frac{\alpha +\mathrm{1}}{\alpha }\right)=\frac{R}{\mathrm{2}\left(b-a\right)}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\times \left({{\displaystyle \int }}_{\pi }^{\mathrm{0}}‍\log \left|\frac{b+\sqrt{b^{\mathrm{2}}-v_{\mathrm{1}}^{\mathrm{2}}{\sin }^{\mathrm{2}}\varphi }}{v_{\mathrm{1}}+v_{\mathrm{1}}\cos \varphi }\right|d\varphi \right.\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{1em}\hspace{1em}\left.-{{\displaystyle \int }}_{\pi }^{{\varphi }_{\mathrm{0}}}‍\log \left|\frac{a+\sqrt{a^{\mathrm{2}}-v_{\mathrm{1}}^{\mathrm{2}}{\sin }^{\mathrm{2}}\varphi }}{a-\sqrt{a^{\mathrm{2}}-v_{\mathrm{1}}^{\mathrm{2}}{\sin }^{\mathrm{2}}\varphi }}\right|d\varphi \right).\end{array}$$

(14)

We derive then β as a function of velocity $v_{\mathrm{1}}$ as follows:

$$\begin{array}{l}\beta =\frac{R}{\mathrm{2}\left(b-a\right)\Gamma \left((\alpha +\mathrm{1})/\alpha \right)}\\ \hspace{1em}\hspace{1em}\times \left({{\displaystyle \int }}_{\pi }^{\mathrm{0}}‍\log \left|\frac{b+\sqrt{b^{\mathrm{2}}-v_{\mathrm{1}}^{\mathrm{2}}{\sin }^{\mathrm{2}}\varphi }}{v_{\mathrm{1}}+v_{\mathrm{1}}\cos \varphi }\right|d\varphi \right.\\ \hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{1em}\left.-{{\displaystyle \int }}_{\pi }^{{\varphi }_{\mathrm{0}}}‍\log \left|\frac{a+\sqrt{a^{\mathrm{2}}-v_{\mathrm{1}}^{\mathrm{2}}{\sin }^{\mathrm{2}}\varphi }}{a-\sqrt{a^{\mathrm{2}}-v_{\mathrm{1}}^{\mathrm{2}}{\sin }^{\mathrm{2}}\varphi }}\right|d\varphi \right).\end{array}$$

(15)

Simulations have been conducted to compare between the theoretical β obtained from (15) and the Weibull approximative one obtained from simulations, as shown in Table 3. The results show that the Weibull distribution fits well simulation data.

Table 3

Comparison between theoretical and approximative β.

Number ofnodes ( $\text{NN}$ )	Node velocity(m/s)	Approximative β	Theoretical β
10	20	28.74	28.36
	15	35.53	35.83
	10	53.63	50.17
	5	88.20	88.55
20	20	34.57	32.85
	15	40.04	39.44
	10	56.07	52.29
	5	84.50	80.386

4.2. Residual Node Lifetime Distribution

We assume that the node lifetime follows an exponential distribution with a parameter λ. This distribution is similar to the one used to model “time to failure” in reliability engineering. We consider that λ is the rate at which node's battery is discharged. The probability density function is then

$$\begin{array}{cc}& f\left(t\right)=\left\{\begin{array}{cc}\mathrm{0},\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}t<\mathrm{0},\hfill \\ \lambda e^{-\lambda t},\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}t\ge \mathrm{0}.\hfill \end{array}\right.\end{array}$$

(16)

The probability density function of the residual node lifetime for a node of age a is given by the following equation [26]:

$$\begin{array}{cc}& r_a\left(t\right)=\frac{f\left(t+a\right)}{\mathrm{1}-F\left(a\right)}=\lambda e^{-\lambda t},\end{array}$$

(17)

where F is the cumulative density function (CDF) of the exponential distribution. Thus, the residual node lifetime also follows an exponential distribution. The expected value for the random variable X following an exponential distribution is

$$\begin{array}{cc}& \mathbb{E}\left(X\right)=\frac{\mathrm{1}}{\lambda }.\end{array}$$

(18)

4.3. Link-Node Lifetime Distribution

Consider a random variable Z, where $Z=\min (X,Y)$ . X (resp., Y) is a random variable related to link lifetime (resp., residual node lifetime) following a Weibull distribution (resp., exponential distribution) with a joint cumulative distribution function $I_{X,Y}(x,y)$ . Then, since X and Y are independent, we have

$$\begin{array}{cc}& P\left(Z>t\right)=P\left(\min \left(X,Y\right)>t\right)=P\left(X>t,Y>t\right).\end{array}$$

(19)

Therefore,

$$\begin{array}{cc}& P\left(Z>t\right)=\mathrm{1}-P\left(X\le t\right)-P\left(Y\le t\right)+P\left(X\le t,Y\le t\right).\end{array}$$

(20)

Consequently, the cumulative distribution function (CDF) of Z is

$$\begin{array}{l}{H}_Z\left(t\right)=\mathrm{1}-P(Z>t)\\ \hspace{1em}\hspace{1em}\hspace{0.17em}=P\left(X\le t\right)+P\left(Y\le t\right)-P\left(X\le t,Y\le t\right).\end{array}$$

(21)

Thus,

$$\begin{array}{cc}& H_Z\left(t\right)=F_X\left(t\right)+G_Y\left(t\right)-I_{X,Y}\left(t,t\right).\end{array}$$

(22)

The approximated density function for the combined variables X and Y is a Phased Bi-Weibull distribution [27], which has a PDF as shown in

$$\begin{array}{cc}& g\left(t\right)=\left\{\begin{array}{cc}\frac{{\alpha }_{\mathrm{1}}}{{\beta }_{\mathrm{1}}}{\left(\frac{t-{\gamma }_{\mathrm{1}}}{{\beta }_{\mathrm{1}}}\right)}^{{\alpha }_{\mathrm{1}}-\mathrm{1}}{e}^{-{\left((t-{\gamma }_{\mathrm{1}})/{\beta }_{\mathrm{1}}\right)}^{{\alpha }_{\mathrm{1}}}}\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}{\gamma }_{\mathrm{1}}\le t\le {\gamma }_{\mathrm{2}}\hfill \\ \frac{{\alpha }_{\mathrm{2}}}{{\beta }_{\mathrm{2}}}{\left(\frac{t-{\gamma }_{\mathrm{2}}}{{\beta }_{\mathrm{2}}}\right)}^{{\alpha }_{\mathrm{2}}-\mathrm{1}}{e}^{-{\left((t-{\gamma }_{\mathrm{2}})/{\beta }_{\mathrm{1}}\right)}^{{\alpha }_{\mathrm{2}}}}\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}{\gamma }_{\mathrm{2}}<t<\infty .\hfill \end{array}\right.\end{array}$$

(23)

EasyFit software [22] approximates the simulation data to the Phased Bi-Weibull distribution, as shown in Figure 17 (resp., Figure 18), with parameters ${\alpha }_{\mathrm{1}}=\mathrm{0.87118}$ , ${\beta }_{\mathrm{1}}=\mathrm{19.482}$ , ${\gamma }_{\mathrm{1}}=\mathrm{0}$ , ${\alpha }_{\mathrm{2}}=\mathrm{0.68969}$ , ${\beta }_{\mathrm{2}}=\mathrm{31.875}$ , and ${\gamma }_{\mathrm{2}}=\mathrm{3}$ (resp., ${\alpha }_{\mathrm{1}}=\mathrm{0.90481}$ , ${\beta }_{\mathrm{1}}=\mathrm{22.976}$ , ${\gamma }_{\mathrm{1}}=\mathrm{0}$ , ${\alpha }_{\mathrm{2}}=\mathrm{0.71509}$ , ${\beta }_{\mathrm{2}}=\mathrm{14.819}$ , and ${\gamma }_{\mathrm{2}}=\mathrm{4}$ ).

Figure 17

Link-node lifetime distribution under $\text{NN}=\mathrm{10}$ and $V_{\max }=\mathrm{20}$ .

Figure 18

Link-node lifetime distribution under $\text{NN}=\mathrm{20}$ and $V_{\max }=\mathrm{20}$ .

Remark 2 (see [28]).

For real values $x,y\in \mathbb{R}$ , $\min \left(x,y\right)=x+y-\max \left(x,y\right)$ .

The result of this remark is extended to random variables by the following theorem.

Theorem 3 (see [28]).

Given two real-valued continuous random variables X, Y $\in \Omega \to \mathbb{R}$ , then the expected value of the minimum of the two variables is $\mathbb{E}\left(\min \left(X,Y\right)\right)=\mathbb{E}\left(X\right)+\mathbb{E}\left(Y\right)-\mathbb{E}\left(\max \left(X,Y\right)\right)$ .

Lemma 4 (see [28]).

Given two real-valued continuous random variables X, Y $\in \Omega \to \mathbb{R}$ , then the expected value of the maximum of the two variables is $\mathbb{E}\left(\max \left(X,Y\right)\right)={\int }_{-\infty }^{\infty }‍x{f}_X(x)F_Y(x)dx+{\int }_{-\infty }^{\infty }‍y{f}_Y(y)F_X(y)dy$ .

Based on Theorem 3 and Lemma 4, the expected link-node lifetime is given by

$$\begin{array}{cc}& \mathbb{E}\left(Z\right)=\mathbb{E}\left(X\right)+\mathbb{E}\left(Y\right)-\mathbb{E}\left(\max \left(X,Y\right)\right),\end{array}$$

(24)

where $\mathbb{E}(X)$ is given in (12) and $\mathbb{E}(Y)$ in (18). Figure 19 shows that the expected link-node lifetime resulted from simulation as a function of node velocity. The results show that the expected link-node lifetime decreases rapidly as its velocity is increased and it shows a significant decrease when $V_{\max }\in [\mathrm{1,5}]$ . The results also show that under higher network density the expected link-node lifetime becomes longer. The reason for this is that a node in this case shares links with larger number of neighbors, and consequently links with longer durations will be observed.

Figure 19

Expected link-node lifetime.

4.4. Monitoring Period Estimation

Based on the above statistical analysis, we propose a method to choose the appropriate value for the monitoring period. This method is low-cost and more appropriate for resource-constrained networks like sensor networks. We also propose another method that requires some communication cost and can be implemented on nodes with higher capabilities such as mobile sinks or mobile ad hoc networks and vehicular ad hoc networks.

4.4.1. Low-Cost Method

We assume that the monitoring node has no information about the monitored node's velocity, position, or residual battery, and it wants to ensure that $l\%$ of its links are observable; that is, they exist for a $\text{duration}>\Delta$ . As the link-node lifetime follows a Phased Bi-Weibull distribution, the minimum value of Δ, which ensures this requirement, is t such that $P(Z\le t)=l/\mathrm{100}$ .

4.4.2. High-Cost Method

We assume that each node i can estimate its remaining battery power $E_i$ and its rate of energy dissipation ${\text{EDisip}}_i$ for every time period Δ; an ultraconservative estimate of the residual node lifetime is derived as shown in the following equation:

$$\begin{array}{cc}& {\vartheta }_i=\frac{E_i}{\max \left({\text{EDisip}}_i\right)}\left(s\right).\end{array}$$

(25)

Each node i periodically broadcasts a beacon message containing its residual node lifetime ${\vartheta }_i$ and its position obtained from GPS. Upon receiving such a message from node i, node j first calculates $d_{ij}$ , that is, the distance separating it from its neighbor i. The relative velocity of node i with respect to node j is $\sqrt{v_i^{\mathrm{2}}+v_j^{\mathrm{2}}-\mathrm{2}{v}_i{v}_j\cos \theta }$ , where $v_i$ and $v_j$ are node i's and node j's velocity, respectively. θ denotes the angle between vectors $\overrightarrow{v_i}$ and $\overrightarrow{v_j}$ in the Cartesian coordinate system. The relative velocity is maximum when $v_i=v_j=V_{\max }$ and $\theta =\mathrm{180}$ °, and it equals then to $\mathrm{2}{V}_{\max }$ . Node j then calculates a conservative estimate of the residual link lifetime, that is, the minimum time for node i to move out of the transmission range of node j. The residual link lifetime, ${\xi }_{ij}$ , is given by the following equation, where $\text{TR}$ is the transmission range:

$$\begin{array}{cc}& {\xi }_{ij}=\frac{\text{TR}-d_{ij}}{\mathrm{2}{V}_{\max }}\left(s\right).\end{array}$$

(26)

After that, each node j estimates the residual link-node lifetime given by

$$\begin{array}{cc}& {\chi }_{ij}=\min \left({\vartheta }_i,{\xi }_{ij}\right).\end{array}$$

(27)

Therefore, the monitoring period required to observe the monitored node i must be less than ${\chi }_{ij}$ .

5. Conclusion

In this paper, we have proposed IDS solutions for three aspects of dynamicity in ad hoc and wireless sensor networks. The magnitude dynamicity aspect is solved by defining a normal profile based on the invariants derived from the normal node behavior. We have generated a dependency graph consisting of strongly correlated features, and we have derived the high-level features from the graph. The high-level features are obtained by applying the divide-and-conquer strategy on the maximal cliques algorithm and the maximum weighted spanning tree algorithm. Simulation results show that the IDS can achieve a detection rate of 100% when the malicious behavior is not similar to the normal one. In addition, it can also achieve a false positive rate of 0% when the duration of the training time exceeds a given value. To handle nature dynamicity aspect, we have adopted the carrot and stick strategy to prevent a malicious node from evading the IDS. To do so, we have proposed an adaptive reputation fading strategy to allow fast redemption and fast capture of malicious node. We have analytically studied link-node lifetime distribution and have shown that it can be approximated to the Phased Bi-Weibull distribution. Based on this analysis, we have proposed a low-cost method to estimate the minimum monitoring period required to observe the monitored node's behavior. In addition, based on some topology information, we have proposed a high-cost method designed for network having nodes less constrained with resource limitations.