Lightweight Anomaly Detection for Wireless Sensor Networks

Abstract

Anomaly detection in wireless sensor networks (WSNs) is critical to ensure the quality of senor data, secure monitoring, and reliable detection of interesting and critical events. The main challenge of anomaly detection algorithm in WSNs is identifying anomalies with high accuracy while consuming minimal resource of the network. In this paper two lightweight anomaly detection algorithms LADS and LADQA are proposed for WSNs. Both algorithms utilize the one-class quarter-sphere support vector machine (QSSVM) and convert the linear optimization problem of QSSVM to a sort problem for the reduced computational complexity. Experimental results show that the proposed algorithms can keep the lower computational complexity without reducing the accuracy for anomaly detection, compared to QSSVM.

1. Introduction

Wireless sensor networks (WSNs) have been widely used in various applications including civil and military domains [1]. However, the harsh deployment environment and the constrained capabilities of sensors (energy, CPU, memory, etc.) make WSNs more vulnerable to different types of misbehaviors or anomalies. In WSNs, an anomaly or outlier (these terms are used interchangeably in this paper) is defined as the measurement that significantly deviates from the normal pattern of the sensed data [2]. Sensor data are affected by these anomalies that always correspond to node software or hardware failure, reading errors, unusual events, and malicious attacks. Therefore, it is critical to efficiently and accurately identify anomalies in the sensor data to ensure data quality, secure monitoring, and reliable detection of interesting and critical events.

The context of sensor networks and nature of sensor data make design of an appropriate anomaly detection technique challenging [3]. The constrained environment of a WSN impacts on anomaly detection algorithms. Node constraints on computational power and memory mean that algorithms for anomaly detection should have low computational complexity and occupy little memory space. Moreover, prelabelled data are expensive or difficult to obtain in WSNs. Anomaly detection for WSNs should be able to operate on unlabelled data. In general, the key challenge of anomaly detection algorithm in WSNs is identifying anomalies with high accuracy while consuming minimal resource of the network.

Recently, support vector machines (SVM) in the form of the one-class quarter-sphere (QSSVM) have been used for anomaly detection in WSNs due to their reduced computational complexity and ability to operate on unlabelled data [4, 5]. QSSVM can convert the quadratic optimization problem of one-class SVM to a linear optimization problem. A family of algorithms based on QSSVM are proposed for anomaly detection in WSNs and have shown the potential for anomaly detection. However, the main disadvantage of those algorithms derived from QSSVM is the high computational cost for the solution of a linear programme.

In this paper, we convert the linear optimization problem of QSSVM to a sort problem and propose two lightweight anomaly detection algorithms for WSNs to identify anomalies. Simulations show that our proposed algorithms are able to reduce the computational complexity without reducing the accuracy for anomaly detection.

Our paper makes the following contributions:

• (1)

We present a mathematic method to prove that the linear optimization problem of QSSVM can be converted to a sort problem.

(2)

Based on the presented method, we propose two lightweight anomaly detection algorithms for WSNs, namely, lightweight anomaly detection algorithm using sort (LADS) and lightweight anomaly detection algorithm using quick select (LADQS). It is shown that our algorithms are equivalent to QSSVM but have lower computational complexity.

(3)

The experimental evaluation of the effectiveness and efficiency of the proposed algorithms on real world WSN dataset is presented.

The remainder of this paper is structured as follows. Related works on QSSVM-based anomaly detection models are presented in Section 2. In Section 3, first the principle of QSSVM is described, and then a method to convert the linear optimization problem of QSSVM to a sort problem is discussed. Furthermore, our proposed lightweight anomaly detection algorithms are also explained. Experimental results and performance evaluation are reported in Section 4. Section 5 concludes the paper and suggests some directions for future research.

2. Related Work

Anomaly detection typically makes use of data mining and machine learning techniques to detect abnormal activities in the systems [2]. Anomaly detection techniques for WSNs can be categorized into statistical-based, nearest neighbor-based, clustering-based, classification-based, and spectral decomposition-based approaches [6]. Classification models are important models of data mining and machine learning community in which a classification model is learned using the known training data and used after that to classify the unseen testing data into different types of classes. SVM-based techniques are one of the popular classification-based approaches and have been widely used to detect anomalies due to the advantages of no requirement of an explicit statistical model and prevention from the curse of dimensionality.

In WSNs, prelabelled data are expensive or difficult to obtain. Several one-class SVM-based anomaly detection techniques have been proposed to process the unlabeled data. Their main idea is to use a nonlinear function to map the data vectors collected from the original input space to a higher dimensional space called feature space. Then a decision boundary of normal data is found, which encompasses the majority of data vectors in the feature space. Those data vectors falling outside the normal boundary are classified as anomalous. To this end, Schölkopf et al. have presented a hyperplane-based one-class SVM by fitting a hyperplane from the origin. Those data vectors near the origin are considered as anomalous [7]. Tax and Duin have proposed a hypersphere-based one-class SVM by fitting a hypersphere with a minimum radius [8]. Those data vectors falling outside the hypersphere are considered as anomalous. However, these one-class SVM-based techniques still require solving a quadratic optimization, and that is extremely costly.

In order to reduce expensive computational complexity of the quadratic optimization, Campbell and Bennett have formulated a linear programming approach for the hyperplane-based SVM proposed in [9], which is based on attracting the hyperplane towards the average of the distribution of mapped data vectors. Laskov et al. have extended work in Tax and Duin by proposing a quarter-sphere one-class SVM, which converts the quadratic optimization problem to a linear optimization problem by fitting a hypersphere centered at the origin and consequently reduces computational complexity of learning the normal boundary of data vectors [5, 8]. Based on QSSVM, several distributed outlier detection techniques for WSNs are proposed by Rajasegarar et al. and Zhang et al. [10, 11]. After that, Rajasegarar et al. have further extended work in [12] by proposing a hyperellipsoidal one-class SVM using a linear optimization. However, the solution of a linear optimization, rather than a quadratic, still requires expensive computational complexity due to the fact that the solution of the linear programme is $O(n^{\mathrm{3}})$ where n is the number of data vectors in the training set.

In this paper, we propose two lightweight anomaly detection techniques which convert the linear optimization problem of QSSVM to a sort problem and consequently reduce computational complexity of learning the normal boundary of data vectors.

3. Lightweight Anomaly Detection Algorithm for WSNs

In this section, we first introduce the principles of modeling the one-class quarter-sphere support vector machine (QSSVM) proposed in [5]. After that, we use a mathematical method to prove that the linear optimization problem of QSSVM can be converted to a sort problem and further propose two lightweight anomaly detection algorithms for WSNs.

3.1. Principles of the One-Class Quarter-Sphere SVM

In this section we discuss the principles of QSSVM proposed by Laskov et al. in [5]. They have converted the quadratic optimization problem of the one-class SVM to a linear optimization problem by fixing the center of the quarter-sphere at the origin. The geometry of hypersphere SVM is shown in Figure 1.

Figure 1

Geometry of QSSVM formulation in the feature space.

Assume that n data vectors $\{x_i\in R^d,\hspace{0.17em}\hspace{0.17em}i=\mathrm{1},\dots ,n\}$ of d variables in the input space are mapped into the feature space using a certain nonlinear mapping function $\varphi (g)$ . The constrained optimization problem of QSSVM can be formalized as follows:

$$\begin{array}{cc}& \underset{R\in \mathfrak{R},\xi \in {\mathfrak{R}}^n}{\mathrm{m}\mathrm{i}\mathrm{n}}\hspace{1em}{R}^{\mathrm{2}}+\frac{\mathrm{1}}{vn}{\displaystyle \sum }_{i=\mathrm{1}}^n{\xi }_i\\ \text{subject\hspace{0.17em}\hspace{0.17em}to:}\hspace{1em}{‖\varphi \left(x_i\right)‖}^{\mathrm{2}}\le R^{\mathrm{2}}+{\xi }_i,\\ {\xi }_i\ge \mathrm{0},\hspace{0.17em}\hspace{0.17em}i=1,\dots ,n,\end{array}$$

(1)

where $\{{\xi }_i:i=\mathrm{1,2},\dots ,n\}$ are the slack variables that allow some of the data vectors to fall outside the quarter-sphere. The regularization parameter v is a representation of the number of data vectors that are expected to be anomalies, where $v\in (\mathrm{0,1})$ .

Obtaining the dual form of the optimization problem allows its formulation in terms of dot products of the data vectors in the training set. Using the kernel trick, the dot products ${‖\varphi (x_i)‖}^{\mathrm{2}}$ are replaced by the kernels $k(x_i,x_i)$ . The dual formulation of (1) will become

$$\begin{array}{cc}& \underset{\alpha \in {\mathfrak{R}}^n}{\mathrm{m}\mathrm{i}\mathrm{n}}\hspace{1em}-{\displaystyle \sum }_{i=\mathrm{1}}^n{\alpha }_{i}k\left(x_i,x_i\right)\\ \text{subject\hspace{0.17em}\hspace{0.17em}to:}\hspace{1em}{\displaystyle \sum }_{i=\mathrm{1}}^n{\alpha }_i=\mathrm{1},\\ \hspace{1em}\mathrm{0}\le {\alpha }_i\le \frac{\mathrm{1}}{vn},\hspace{0.17em}\hspace{0.17em}i=1,\dots ,n.\end{array}$$

(2)

It can be seen from (2) that optimization problem is stated in terms of a dot product of an image vector with itself; this causes an issue with distance-based kernels, such as the RBF kernel, as the diagonal term $k(x_i,x_i)$ becomes equal for all the vectors. This can be solved by centering the kernel matrix in feature space where the mean of the image vectors is subtracted from each image vector as follows:

$$\begin{array}{cc}& \varphi {\left(x_i\right)}_c=\varphi \left(x_i\right)-\frac{\mathrm{1}}{n}{\displaystyle \sum }_{i=\mathrm{1}}^n\varphi \left(x_i\right).\end{array}$$

(3)

There is no explicit vector in feature space that represents the mean; however the dot product $K_c=(\varphi (x_i{)}_c,\varphi (x_j{)}_c)$ of the centred image vectors can be obtained in terms of the kernel matrix $K=k(x_i,x_j)=(\varphi (x_i)·\varphi (x_j))$ using $K_c=K-{\mathrm{1}}_{n}K-K{\mathrm{1}}_n+{\mathrm{1}}_{n}K{\mathrm{1}}_n$ , where ${\mathrm{1}}_n$ is an $n\times n$ matrix with all values equal to $\mathrm{1}/n$ [13]. When the kernel matrix is centred in feature space the norms of the kernels are no longer equal and the terms $k(x_i,x_i)$ of (2) are replaced by the diagonal elements $k_c(x_i,x_i)$ of the centered kernel matrix $K_c$ . $\sqrt{k_c(x_i,x_i)}$ can be considered as the distances between data vectors $x_i$ and the origin of its centered quarter-sphere in the feature space. Consequently, the dual problem (2) can be solved.

After solving (2) for $\{{\alpha }_i\}$ , the data vectors can be classified as follows. Data vectors with ${\alpha }_i=\mathrm{0}$ , which lie inside the hypersphere, are considered as normal and their distances from the origin are smaller than the radius of the quarter-sphere. Data vectors with ${\alpha }_i=\mathrm{1}/vn$ are considered as anomalies, which lie outside the hypersphere. Data vectors with $\mathrm{0}<{\alpha }_i<\mathrm{1}/vn$ , which lie on the surface of the hypersphere, are called the border support vectors. Moreover, the minimal radius R of the hypersphere can be obtained using $R^{\mathrm{2}}=k_c(x_i,x_i)$ for any border support vector $x_i$ .

3.2. Lightweight Anomaly Detection Algorithm Using Sort

In the previous section, we introduced the principle of QSSVM which convert the quadratic optimization problem to a linear optimization problem. We are aware that the learning process of QSSVM is to find the minimal radius R of one-class quarter-sphere for the training set, which can be obtained by the distances between border support vectors $x_i$ and its origin in the feature space using $R^{\mathrm{2}}=k_c(x_i,x_i)$ . This process has high computational and memory complexity due to the fact that it requires solving the linear programme and finding data vectors $x_i$ with $\mathrm{0}<{\alpha }_i<\mathrm{1}/vn$ , that is, the border support vectors. To reduce the cost of modeling QSSVM, we propose a lightweight anomaly detection algorithm using sort to identify anomalies. Our algorithm can obtain the minimal radius R of QSSVM, that is, the distance $\sqrt{k_c(x_i,x_i)}$ between data vector $x_i$ with $\mathrm{0}<{\alpha }_i<\mathrm{1}/vn$ and the origin, by a descending sorted sequence instead of the solution of a linear optimization problem. That is to say, our algorithm will be equivalent to QSSVM but converts the linear optimization problem to a sort problem. For doing so, we first fix the data vectors at the origin in the feature space through generation of kernel matrix and the transformation of central kernel matrix like QSSVM [5] and obtain the formulation of (2). Note that the terms $k(x_i,x_i)$ of (2) have been actually replaced by the diagonal elements $k_c(x_i,x_i)$ of the centered kernel matrix $K_c$ as we discussed in the previous subsection. Next we require finding the minimal radius R from (2). Obviously, the process for calculation of R only needs to find a distance $\sqrt{k_c(x_i,x_i)}$ corresponding to ${\alpha }_i$ satisfying the formulation of (2) and $\mathrm{0}<{\alpha }_i<\mathrm{1}/vn$ , instead of solving the linear programme for (2).

In order to find the minimal radius R, the sequence $\{k_c(x_i,x_i)\}$ is sorted in descending order and becomes $\{k_c(x_{{\mathrm{1}}^{\prime }},x_{{\mathrm{1}}^{\prime }}),k_c(x_{{\mathrm{2}}^{\prime }},x_{{\mathrm{2}}^{\prime }}),\dots ,k_c(x_{n^{\prime }},x_{n^{\prime }})\}$ , where $k_c(x_{{\mathrm{1}}^{\prime }},x_{{\mathrm{1}}^{\prime }})\ge k_c(x_{{\mathrm{2}}^{\prime }},x_{{\mathrm{2}}^{\prime }})\ge \cdots \ge k_c(x_{n^{\prime }},x_{n^{\prime }})$ . For convenience, we replace $k_c(x_i,x_i)$ with $d_i$ . Consequently, the dual formulation of (2) will be simplified to

$$\begin{array}{cc}& \underset{\alpha \in {\mathfrak{R}}^n}{\mathrm{m}\mathrm{a}\mathrm{x}}\hspace{1em}{\displaystyle \sum }_{i=\mathrm{1}}^n{\alpha }_{i^{\prime }}{d}_{i^{\prime }}\\ \text{subject\hspace{0.17em}\hspace{0.17em}to:}\hspace{1em}{\displaystyle \sum }_{i=\mathrm{1}}^n{\alpha }_{i^{\prime }}=\mathrm{1},\\ \hspace{1em}\mathrm{0}\le {\alpha }_{i^{\prime }}\le \frac{\mathrm{1}}{vn},\hspace{0.17em}\hspace{0.17em}i=1,\dots ,n,\end{array}$$

(4)

where $d_{{\mathrm{1}}^{\prime }}\ge d_{{\mathrm{2}}^{\prime }}\ge \cdots \ge d_{n^{\prime }}$ , $v\in (\mathrm{0,1})$ is the regularization parameter that represents the fraction of outliers, and n is the number of the data vectors in the training set.

Actually, there exists an implied constraint that ${\alpha }_{i^{\prime }}={\alpha }_{j^{\prime }}$ if and only if $d_{i^{\prime }}=d_{j^{\prime }}$ . This implies that the data vectors which have the same distances to origin in the feature space either are normal or not.

Now we prove that the minimal radius R can be computed directly from the descending sequence $\{d_{{\mathrm{1}}^{\prime }},d_{{\mathrm{2}}^{\prime }},\dots ,d_{n^{\prime }}\}$ through the parameters v and n.

Theorem 1.

If the values of ${\alpha }_{{\mathrm{1}}^{\prime }},{\alpha }_{{\mathrm{2}}^{\prime }},\dots ,{\alpha }_{n^{\prime }}$ are the solution of (4), one has ${\alpha }_{{\mathrm{1}}^{\prime }}\ge {\alpha }_{{\mathrm{2}}^{\prime }}\ge \cdots \ge {\alpha }_{n^{\prime }}$ .

Proof.

Since ${\alpha }_{{\mathrm{1}}^{\prime }},{\alpha }_{{\mathrm{2}}^{\prime }},\dots ,{\alpha }_{n^{\prime }}$ is the solution of (4), the value of the objective function attains maximum under the constrained condition and can be denoted as $f_{\mathrm{1}}={\alpha }_{{\mathrm{1}}^{\prime }}{d}_{{\mathrm{1}}^{\prime }}+{\alpha }_{{\mathrm{2}}^{\prime }}{d}_{{\mathrm{2}}^{\prime }}+\cdots +{\alpha }_{n^{\prime }}{d}_{n^{\prime }}$ .

Firstly, we prove that ${\alpha }_{{\mathrm{1}}^{\prime }}$ is the maximum of $\{{\alpha }_{{\mathrm{1}}^{\prime }},{\alpha }_{{\mathrm{2}}^{\prime }},\dots ,{\alpha }_{n^{\prime }}\}$ if $d_{{\mathrm{1}}^{\prime }}$ is the maximum of $\{d_{{\mathrm{1}}^{\prime }},d_{{\mathrm{2}}^{\prime }},\dots ,d_{n^{\prime }}\}$ . Assume the contrary that the value of ${\alpha }_{{\mathrm{1}}^{\prime }}$ is not maximal if the value of $d_{{\mathrm{1}}^{\prime }}$ is maximal. This assumption indicates that there exists ${\alpha }_{j^{\prime }}$ such that value of ${\alpha }_{j^{\prime }}$ is the maximal of $\{{\alpha }_{i^{\prime }}\}$ . We exchange the value of ${\alpha }_{j^{\prime }}$ with ${\alpha }_{{\mathrm{1}}^{\prime }}$ , so the value of the objective function becomes

$$\begin{array}{ll}{f}_{\mathrm{2}}& ={\alpha }_{j^{\prime }}{d}_{{\mathrm{1}}^{\prime }}+{\alpha }_{{\mathrm{2}}^{\prime }}{d}_{{\mathrm{2}}^{\prime }}+\cdots +{\alpha }_{{\left(j-\mathrm{1}\right)}^{\prime }}{d}_{{\left(j-\mathrm{1}\right)}^{\prime }}+{\alpha }_{{\mathrm{1}}^{\prime }}{d}_{j^{\prime }}\\ & +{\alpha }_{{\left(j+\mathrm{1}\right)}^{\prime }}{d}_{{\left(j+\mathrm{1}\right)}^{\prime }}+\cdots +{\alpha }_{n^{\prime }}{d}_{n^{\prime }}.\end{array}$$

(5)

Subtract $f_{\mathrm{1}}$ from $f_{\mathrm{2}}$ and we have

$$\begin{array}{ll}{f}_{\mathrm{2}}-f_{\mathrm{1}}& =\left({\alpha }_{j^{\prime }}{d}_{{\mathrm{1}}^{\prime }}+{\alpha }_{{\mathrm{1}}^{\prime }}{d}_{j^{\prime }}\right)-\left({\alpha }_{{\mathrm{1}}^{\prime }}{d}_{{\mathrm{1}}^{\prime }}+{\alpha }_{j^{\prime }}{d}_{j^{\prime }}\right)\\ & =\left(d_{{\mathrm{1}}^{\prime }}-d_{j^{\prime }}\right)\left({\alpha }_{j^{\prime }}-{\alpha }_{{\mathrm{1}}^{\prime }}\right).\end{array}$$

(6)

From the contradictions, we have $d_{{\mathrm{1}}^{\prime }}\ge d_{j^{\prime }}$ and ${\alpha }_{j^{\prime }}\ge {\alpha }_{{\mathrm{1}}^{\prime }}$ . So we get $f_{\mathrm{2}}-f_{\mathrm{1}}\ge \mathrm{0}$ . This contradicts the fact that $f_{\mathrm{1}}$ is not the maximum of the objective function. Thus we have derived that ${\alpha }_{{\mathrm{1}}^{\prime }}$ is the maximum of $\{{\alpha }_{i^{\prime }}\hspace{0.17em}|\hspace{0.17em}{i}^{\prime }=\mathrm{1,2},\dots ,n\}$ .

In a similar way, we can prove that ${\alpha }_{{\mathrm{2}}^{\prime }}$ is the second maximum of $\{{\alpha }_{{\mathrm{1}}^{\prime }},{\alpha }_{{\mathrm{2}}^{\prime }},\dots ,{\alpha }_{n^{\prime }}\}$ , if $d_{{\mathrm{2}}^{\prime }}$ is the second maximum of $\{d_{{\mathrm{1}}^{\prime }},d_{{\mathrm{2}}^{\prime }},\dots ,d_{n^{\prime }}\}$ . And so, we can prove that ${\alpha }_{i^{\prime }}$ is the ith maximum of $\{{\alpha }_{{\mathrm{1}}^{\prime }},{\alpha }_{{\mathrm{2}}^{\prime }},\dots ,{\alpha }_{n^{\prime }}\}$ if $d_{i^{\prime }}$ is the ith maximum of $\{d_{{\mathrm{1}}^{\prime }},d_{{\mathrm{2}}^{\prime }},\dots ,d_{n^{\prime }}\}$ .

As proved above, it is evident that ${\alpha }_{{\mathrm{1}}^{\prime }}\ge {\alpha }_{{\mathrm{2}}^{\prime }}\ge \cdots \ge {\alpha }_{n^{\prime }}$ if the values of ${\alpha }_{{\mathrm{1}}^{\prime }},{\alpha }_{{\mathrm{2}}^{\prime }},\dots ,{\alpha }_{n^{\prime }}$ are the solution of (4). This completes the proof.

According to Theorem 1, we can infer Theorems 2 and 3 as follows.

Theorem 2.

If the values of $\{{\alpha }_{{\mathrm{1}}^{\prime }},{\alpha }_{{\mathrm{2}}^{\prime }},\dots ,{\alpha }_{n^{\prime }}\}$ are the solution of (4), one has $\mathrm{0}<{\alpha }_{{\left(j+\mathrm{1}\right)}^{\prime }}<\mathrm{1}/vn$ when $j=⌊vn⌋$ and $j\ne vn$ .

Proof.

Since one of the constraint conditions is $\mathrm{0}\le {\alpha }_{i^{\prime }}\le \mathrm{1}/vn$ , Theorem 3 will be proved if we can show that ${\alpha }_{{\left(j+\mathrm{1}\right)}^{\prime }}\ne \mathrm{0}$ and ${\alpha }_{{\left(j+\mathrm{1}\right)}^{\prime }}\ne \mathrm{1}/vn$ when $j=⌊vn⌋$ and $j\ne vn$ . If the assertion were not true, then we would have ${\alpha }_{{\left(j+\mathrm{1}\right)}^{\prime }}=\mathrm{0}$ or ${\alpha }_{{\left(j+\mathrm{1}\right)}^{\prime }}=\mathrm{1}/vn$ when $j=⌊vn⌋$ and $j\ne vn$ .

Recalling Theorem 1, we have $\mathrm{1}/vn\ge {\alpha }_{{\mathrm{1}}^{\prime }}\ge \cdots \ge {\alpha }_{j^{\prime }}\ge {\alpha }_{{\left(j+\mathrm{1}\right)}^{\prime }}\ge \cdots \ge {\alpha }_{n^{\prime }}\ge \mathrm{0}$ . By the assumption of ${\alpha }_{{\left(j+\mathrm{1}\right)}^{\prime }}=\mathrm{0}$ , it is easy to see that ${\alpha }_{{\left(j+\mathrm{1}\right)}^{\prime }}={\alpha }_{{\left(j+\mathrm{2}\right)}^{\prime }}=\cdots ={\alpha }_{n^{\prime }}=\mathrm{0}$ . And we have ${\sum }_{i=\mathrm{1}}^n{\alpha }_i={\sum }_{i=\mathrm{1}}^j{\alpha }_i\le j/vn$ . When $j=⌊vn⌋$ and $j\ne vn$ , the above inequation will become ${\sum }_{i=\mathrm{1}}^n{\alpha }_i\le j/vn<\mathrm{1}$ . This contradicts the fact of ${\sum }_{i=\mathrm{1}}^n{\alpha }_i=\mathrm{1}$ . By the assumption of ${\alpha }_{{\left(j+\mathrm{1}\right)}^{\prime }}=\mathrm{1}/vn$ , it is clear that ${\alpha }_{{\mathrm{1}}^{\prime }}={\alpha }_{{\mathrm{2}}^{\prime }}=\cdots ={\alpha }_{j^{\prime }}={\alpha }_{{\left(j+\mathrm{1}\right)}^{\prime }}=\mathrm{1}/vn$ . And we get ${\sum }_{i=\mathrm{1}}^n{\alpha }_i\ge \left(j+\mathrm{1}\right)/vn$ . When $j=⌊vn⌋$ and $j\ne vn$ , the inequation will become ${\sum }_{i=\mathrm{1}}^n{\alpha }_i\ge \left(j+\mathrm{1}\right)/vn>\mathrm{1}$ . This is contrary to the constraint condition of ${\sum }_{i=\mathrm{1}}^n{\alpha }_i=\mathrm{1}$ . This completes the proof.

Theorem 3.

Given that the values of $\{{\alpha }_{{\mathrm{1}}^{\prime }},{\alpha }_{{\mathrm{2}}^{\prime }},\dots ,{\alpha }_{n^{\prime }}\}$ are the solution of (4), if $j=vn$ and $j=⌊vn⌋$ , one has

•  

if

$$\begin{array}{cc}& d_{{\mathrm{1}}^{\prime }}=d_{{\mathrm{2}}^{\prime }}=\cdots =d_{n^{\prime }},\\ {\alpha }_{{\mathrm{1}}^{\prime }}={\alpha }_{{\mathrm{2}}^{\prime }}=\cdots ={\alpha }_{n^{\prime }};\end{array}$$

(7)

 

otherwise,

$$\begin{array}{cc}& {\alpha }_{{\mathrm{1}}^{\prime }}=\cdots ={\alpha }_{j^{\prime }}=\frac{\mathrm{1}}{vn},\\ {\alpha }_{{\left(j+\mathrm{1}\right)}^{\prime }}=\cdots ={\alpha }_{n^{\prime }}=\mathrm{0}.\end{array}$$

(8)

Proof.

In the case when $d_{{\mathrm{1}}^{\prime }}=d_{{\mathrm{2}}^{\prime }}=\cdots =d_{n^{\prime }}$ , obviously, we have ${\alpha }_{{\mathrm{1}}^{\prime }}={\alpha }_{{\mathrm{2}}^{\prime }}=\cdots ={\alpha }_{n^{\prime }}$ by the implied constraint that there exists ${\alpha }_{i^{\prime }}={\alpha }_{j^{\prime }}$ if and only if $d_{i^{\prime }}=d_{j^{\prime }}$ . In the other cases, let the value ${\beta }_{i^{\prime }}$ of ${\alpha }_{i^{\prime }}$ be the solution of (4). If the assertion were not true, we would have the value ${\beta }_{i^{\prime }}$ of ${\alpha }_{i^{\prime }}$ such that ${\beta }_{k^{\prime }}\ne \mathrm{1}/vn$ or ${\beta }_{l^{\prime }}\ne \mathrm{0}$ , where $k\in \{\mathrm{1},\dots ,j\}$ and $l\in \{j+\mathrm{1},\dots ,n\}$ . Consequently, the value of objective function becomes $f_{\mathrm{1}}={\sum }_{i=\mathrm{1}}^n{\beta }_{i^{\prime }}{d}_{i^{\prime }}$ . When ${\alpha }_{{\mathrm{1}}^{\prime }}={\alpha }_{{\mathrm{2}}^{\prime }}=\cdots ={\alpha }_{j^{\prime }}=\mathrm{1}/vn$ and ${\alpha }_{{\left(j+\mathrm{1}\right)}^{\prime }}=\cdots ={\alpha }_{n^{\prime }}=\mathrm{0}$ , where $j=vn$ and $j=⌊vn⌋$ , let the value of objective function be $f_{\mathrm{2}}={\sum }_{i=\mathrm{1}}^n{\alpha }_{i^{\prime }}{d}_{i^{\prime }}=\left(\mathrm{1}/vn\right){\sum }_{i=\mathrm{1}}^j{d}_{i^{\prime }}$ . Since the value ${\beta }_{i^{\prime }}$ of ${\alpha }_{i^{\prime }}$ is the solution of (4), $f_{\mathrm{1}}$ is the maximal of the objective function and $f_{\mathrm{1}}\ge f_{\mathrm{2}}$ . Subtract $f_{\mathrm{1}}$ from $f_{\mathrm{2}}$ and we have $f_{\mathrm{2}}-f_{\mathrm{1}}=(\mathrm{1}/vn-{\beta }_{{\mathrm{1}}^{\prime }})d_{{\mathrm{1}}^{\prime }}+\cdots +(\mathrm{1}/vn-{\beta }_{j^{\prime }})d_{j^{\prime }}-{\beta }_{{\left(j+\mathrm{1}\right)}^{\prime }}{d}_{{\left(j+\mathrm{1}\right)}^{\prime }}-\cdots -{\beta }_{n^{\prime }}{d}_{n^{\prime }}$ . Recalling Theorem 1 and the constraints, we have $\mathrm{1}/vn\ge {\alpha }_{{\mathrm{1}}^{\prime }}\ge \cdots \ge {\alpha }_{j^{\prime }}\ge {\alpha }_{{\left(j+\mathrm{1}\right)}^{\prime }}\ge \cdots \ge {\alpha }_{n^{\prime }}\ge \mathrm{0}$ and $d_{{\mathrm{1}}^{\prime }}\ge \cdots \ge d_{j^{\prime }}\ge d_{{\left(j+\mathrm{1}\right)}^{\prime }}\ge \cdots \ge d_{n^{\prime }}\ge \mathrm{0}$ . So we get $f_{\mathrm{2}}-f_{\mathrm{1}}\ge (\mathrm{1}/vn-{\beta }_{{\mathrm{1}}^{\prime }})d_{{\mathrm{1}}^{\prime }}+\cdots +(\mathrm{1}/vn-{\beta }_{j^{\prime }})d_{j^{\prime }}-{\beta }_{{\left(j+\mathrm{1}\right)}^{\prime }}{d}_{j^{\prime }}-\cdots -{\beta }_{n^{\prime }}{d}_{j^{\prime }}$ . According to the implied constraint, the equality sign holds if and only if $d_{j^{\prime }}=d_{{\left(j+\mathrm{1}\right)}^{\prime }}=\cdots =d_{n^{\prime }}$ or ${\beta }_{{\left(j+\mathrm{1}\right)}^{\prime }}=\cdots ={\beta }_{n^{\prime }}=\mathrm{0}$ . And we also have $f_{\mathrm{2}}-f_{\mathrm{1}}\ge (\mathrm{1}/vn-{\beta }_{{\mathrm{1}}^{\prime }})d_{j^{\prime }}+\cdots +(\mathrm{1}/vn-{\beta }_{j^{\prime }})d_{j^{\prime }}-{\beta }_{{\left(j+\mathrm{1}\right)}^{\prime }}{d}_{j^{\prime }}-\cdots -{\beta }_{n^{\prime }}{d}_{j^{\prime }}$ , where the equality sign holds if and only if ( $d_{{\mathrm{1}}^{\prime }}=\cdots =d_{j^{\prime }}$ and $d_{j^{\prime }}=d_{{\left(j+\mathrm{1}\right)}^{\prime }}=\cdots =d_{n^{\prime }}$ ) or ( ${\beta }_{{\mathrm{1}}^{\prime }}=\cdots ={\beta }_{j^{\prime }}=\mathrm{1}/vn$ and ${\beta }_{{\left(j+\mathrm{1}\right)}^{\prime }}=\cdots ={\beta }_{n^{\prime }}=\mathrm{0}$ ). However, this is not the case when $d_{{\mathrm{1}}^{\prime }}=d_{{\mathrm{2}}^{\prime }}=\cdots =d_{n^{\prime }}$ and the definition and condition of ${\beta }_{i^{\prime }}$ show that ${\beta }_{k^{\prime }}\ne \mathrm{1}/vn$ or ${\beta }_{l^{\prime }}\ne \mathrm{0}$ , where $k\in \{\mathrm{1},\dots ,j\}$ and $l\in \{j+\mathrm{1},\dots ,n\}$ . So the equality sign does not hold and we have $f_{\mathrm{2}}-f_{\mathrm{1}}>(\mathrm{1}/vn-{\beta }_{{\mathrm{1}}^{\prime }})d_{j^{\prime }}+\cdots +(\mathrm{1}/vn-{\beta }_{j^{\prime }})d_{j^{\prime }}-{\beta }_{{\left(j+\mathrm{1}\right)}^{\prime }}{d}_{j^{\prime }}-\cdots -{\beta }_{n^{\prime }}{d}_{j^{\prime }}$ . And we get $f_{\mathrm{2}}-f_{\mathrm{1}}>(j/vn-{\beta }_{{\mathrm{1}}^{\prime }}-\cdots -{\beta }_{n^{\prime }})d_{j^{\prime }}$ . From $j=vn$ and $j=⌊vn⌋$ and the constraint of ${\sum }_{i=\mathrm{1}}^n{\beta }_{i^{\prime }}=\mathrm{1}$ , we obtain $f_{\mathrm{2}}-f_{\mathrm{1}}>\mathrm{0}$ . This is contrary to $f_{\mathrm{1}}>f_{\mathrm{2}}$ . That is, it completes the proof.

Theorem 4.

The minimal radius R of the quarter-sphere in QSSVM can be obtained by

$$\begin{array}{cc}& R^{\mathrm{2}}=d_{{\left(j+\mathrm{1}\right)}^{\prime }},\end{array}$$

(9)

where $d_{{\left(j+\mathrm{1}\right)}^{\prime }}$ is the $(j+1)$ th largest squared distances $k_c(x_i,x_i)$ between $x_i$ and the origin of its centered quarter-sphere in the feature space.

Proof.

As we know, the constrained optimization problem of QSSVM can be formulated as (2). Note that the terms $k(x_i,x_i)$ of (2) are replaced by $k_c(x_i,x_i)$ . After calculating the values of $\{{\alpha }_{\mathrm{1}},{\alpha }_{\mathrm{2}},\dots ,{\alpha }_n\}$ in (2), the minimal radius R of the quarter-sphere in QSSVM can be computed using $R^{\mathrm{2}}=k_c(x_i,x_i)$ for any data vector $x_i$ with $\mathrm{0}<{\alpha }_i<\mathrm{1}/vn$ . Given $d_i=k_c(x_i,x_i)$ , when $\{k_c(x_i,x_i)\}$ in (2) is sorted in descending order, the optimization problem of (2) becomes the formulation of (4). According to Theorems 2 and 3, the minimal radius R can be obtained in two cases. In the first case when $j=⌊vn⌋$ and $j\ne vn$ ,we have $\mathrm{0}<{\alpha }_{{\left(j+\mathrm{1}\right)}^{\prime }}<1/vn$ from Theorem 3 and $R^{\mathrm{2}}=d_{{\left(j+\mathrm{1}\right)}^{\prime }}$ . In the second case when $j=⌊vn⌋$ and $j=vn$ , we have ${\alpha }_{{\mathrm{1}}^{\prime }}={\alpha }_{{\mathrm{2}}^{\prime }}=\cdots ={\alpha }_{n^{\prime }}$ or ${\alpha }_{{\mathrm{1}}^{\prime }}={\alpha }_{{\mathrm{2}}^{\prime }}=\cdots ={\alpha }_{j^{\prime }}=\mathrm{1}/vn$ , ${\alpha }_{{\left(j+\mathrm{1}\right)}^{\prime }}=\cdots ={\alpha }_{n^{\prime }}=\mathrm{0}$ from Theorem 2. The fact of ${\alpha }_{{\mathrm{1}}^{\prime }}={\alpha }_{{\mathrm{2}}^{\prime }}=\cdots ={\alpha }_{n^{\prime }}$ means that we get $\mathrm{0}<{\alpha }_{{\mathrm{1}}^{\prime }}=\cdots ={\alpha }_{j^{\prime }}=\mathrm{1}/n<\mathrm{1}/vn$ by the constraints of ${\sum }_{i=\mathrm{1}}^n{\alpha }_i=\mathrm{1}$ and $v\in (\mathrm{0,1})$ and $R^{\mathrm{2}}=d_{{\left(j+\mathrm{1}\right)}^{\prime }}$ . The fact of ${\alpha }_{{\mathrm{1}}^{\prime }}={\alpha }_{{\mathrm{2}}^{\prime }}=\cdots ={\alpha }_{j^{\prime }}=\mathrm{1}/vn$ and ${\alpha }_{{\left(j+\mathrm{1}\right)}^{\prime }}=\cdots ={\alpha }_{n^{\prime }}=\mathrm{0}$ means that there are no border support vectors $x_{i^{\prime }}$ , which are the vectors with $\mathrm{0}<{\alpha }_{i^{\prime }}<\mathrm{1}/vn$ . By the decision rule of QSSVM, the vectors with ${\alpha }_{i^{\prime }}=\mathrm{0}$ or the vectors with ${\alpha }_{i^{\prime }}=\mathrm{1}/vn$ are considered as normal or anomalies, respectively. And their squared distances to origin are, respectively, not larger or larger than $d_{{\left(j+\mathrm{1}\right)}^{\prime }}$ , which means the largest squared distance between the normal vectors and the origin. Therefore the minimal radius R can be treated as $\sqrt{d_{{\left(j+\mathrm{1}\right)}^{\prime }}}$ . Moreover, we have $R^{\mathrm{2}}=d_{{\left(j+\mathrm{1}\right)}^{\prime }}$ in both cases. This completes the proof.

From Theorem 4, the minimal radius R of the quarter-sphere in QSSVM can be obtained by a descending sorted sequence using (9). So the linear optimization problem of QSSVM is converted to a sort problem of $\{k_c(x_i,x_i)\}$ . Now, we propose a lightweight anomaly detection algorithm using sorting (LADS), which is equivalent to the QSSVM. The detail of LADS is described as follows.

After the generation of kernel matrix and the transformation of central kernel matrix, the data vectors $x_i$ are centered at the origin in the feature space the same as QSSVM. These squared distances to the origin are sorted in descending order and form a descending sequence $\{k_c(x_{i^{\prime }},x_{i^{\prime }})\}$ , where $k_c(x_{{\mathrm{1}}^{\prime }},x_{{\mathrm{1}}^{\prime }})\ge \cdots \ge k_c(x_{n^{\prime }},x_{n^{\prime }})$ . The $(j+1)$ th largest squared distance $k_c(x_{j^{\prime }},x_{j^{\prime }})$ ( $j=⌊vn⌋$ ) is chosen from the descending sequence as the minimal radius R by (9). The data vectors can be classified depending on R. The data vectors whose distances to origin are not larger than R are considered as normal. Otherwise, the data vectors whose distances to origin are larger than R are considered as outliers.

Now, our algorithm can be described in Algorithm 1.

Algorithm 1

Step  1. Calculate $$k_c(x_i,x_i)$$ .

Step  2. Sort $$k_c(x_i,x_i)$$ in descending order and have $$\left\{k_c\left(x_{i^{\prime }},x_{i^{\prime }}\right)\right\}$$ .

Step  3. Calculate $$R=\sqrt{d_{{(j+\mathrm{1})}^{\prime }}}$$ using (9).

Step  4. If $$k_c(x_i,x_i)>R^{\mathrm{2}}$$

      $$x_i$$ is outlier

   Else

      $$x_i$$ is normal

   End If

3.3. Lightweight Anomaly Detection Algorithm Using Quick Select

As discussed in the previous section, the minimal radius R of the quarter-sphere in QSSVM can be obtained from the descending sequence $\{k_c(x_{i^{\prime }},x_{i^{\prime }})\}$ . The computational complexity for obtaining the descending sequence is $O(n\hspace{0.17em}{\log }_{\mathrm{2}}n)$ . In fact, the process for the descending sequence is unnecessary, because R can be determined by (9) if the $(⌊vn⌋+\mathrm{1})\mathrm{t}\mathrm{h}$ largest element of the original sequence $\{k_c(x_i,x_i)\}$ can be found. So we propose an anomaly detection method LADQS based on Quickselect algorithm [14] to find the ( $⌊vn⌋+\mathrm{1}$ )th largest distance to the origin, that is, minimal radius R. In computer science, Quickselect is a selection algorithm to find the kth largest element in an unordered list. Quickselect uses the same overall approach as quicksort [14], choosing one element as a pivot and partitioning the data in two based on the pivot, accordingly as less than or greater than the pivot. However, instead of recursing into both sides, as in quicksort, Quickselect only recurses into one side—the side with the element it is searching for. This reduces the average computational complexity from $O(n\hspace{0.17em}{\log }_{\mathrm{2}}n)$ to $O(n)$ . The pseudocode of LADQS algorithm is shown in Algorithm 2.

Algorithm 2: The pseudocode of LADQS algorithm.

function LADQS()

 let $$\{x_i\in R^d,i=\mathrm{1},\dots ,n\}$$ be the data vectors in the training set;

 calculate the distance $$k(x_i,x_i)$$ to origin for each data vector $$x_i$$ ;

 obtain $$A=\{k(x_i,x_i),i=\mathrm{1},\dots ,n\}$$ ;

return R = QuickSelect( $$A,\mathit{1},n,⌊vn⌋+\mathrm{1}$$ )

// Returns the nth largest element of list.

function QuickSelect(list, $$l,r,n$$ )

 if $$l=r$$       // If the list contains only one element

  return list $$[l]$$  // Return that element

 pivotIndex = l + floor(rand() ∗ ( $$r-l+\mathit{1}$$ ))

 // randomly select a pivotIndex between l and r

 pivotIndex = QuickPartition(list, l, r, pivotIndex)

 if n = pivotIndex

  return list $$[n]$$

 else if n < pivotIndex

  return QuickSelect(list, l, pivotIndex − 1, n)

 else

  return QuickSelect(list, pivotIndex + 1, r, n)

4. Experimental Results and Evaluation

This section specifies the performance evaluation of our two techniques compared to QSSVM. In our experiments, we have used real data gathered at the Grand-Saint-Bernard [15], which is similar to the one used in [16]. For simulation, we use Matlab to implement our algorithms and QSSVM on a single node in a WSN. For fairness, we use the average of the tests operated on 7 different nodes, respectively, as the experimental results.

4.1. Experimental Datasets

The real data are collected from a closed neighborhood from a WSN deployed in Grand-Saint-Bernard as shown in Figure 2. The closed neighborhood consists of node 2 and its 6 spatially neighboring nodes, namely, nodes 3, 4, 8, 12, 20, and 14. In our simulations, we test the real data collected during the period of 6 am–6 pm on September 20, 2007, with two attributes: ambient temperature and relative humidity for each sensor measurement. The data is preprocessed and normalized to the range $[\mathrm{0,1}]$ . The number of anomalous data is about 10% of normal data. Measurements are labeled depending on the degree of dissimilarity between one another.

Figure 2

The relative positions of the nodes in Grand-Saint-Bernard.

4.2. Experimental Results and Evaluation

We choose radial basis function (RBF) kernel function to generate kernel matrices. RBF kernel function $k_{\mathrm{R}\mathrm{B}\mathrm{F}}=\mathrm{e}\mathrm{x}\mathrm{p}(-{‖x_{\mathrm{1}}-x_{\mathrm{2}}‖}^{\mathrm{2}}/{\sigma }^{\mathrm{2}})$ , where σ is the width parameter of the kernel function. And the kernel width parameter σ is set to 0.25 in our experiments.

We have examined the effect of the regularisation parameter v for our two anomaly detection algorithms and QSSVM. v represents the fraction of anomalies in training set and we have varied it in the range from 0.01 to 0.25 in intervals of 0.03. And we also have examined the training time for the three algorithms.

Figures 3 and 4 show that the detection rate and the false alarm rate obtained for our algorithm LADS use RBF kernel function for real data, respectively. As we discussed in the previous section, LADS, LADQS, and QSSVM have the same principle of data classification but have difference in the way of finding the minimal radius R. This means the LADS behaves in a similar manner to LADQS. Therefore, results of LADQS and QSSVM have been omitted.

Figure 3

Detection rate of LADS in terms of parameter v selection.

Figure 4

False alarm rate of LADS in terms of parameter v selection.

Figure 5 shows the training time elapsing for the three algorithms. We can see that the training time of our algorithms LADS and LADQS is significantly less than that of QSSVM. It indicates that our two algorithms have less time and lower computational complexity, compared to QSSVM.

Figure 5

Training time in terms of parameter v selection.

Simulation results show that our two algorithms LADS and LADQS have the lower computational complexity without reducing the accuracy for anomaly detection, compared to QSSVM.

Computational complexity of our techniques is presented in Table 1, where n denotes the number of data in the training sets, d represents the dimensionality of the measurement, v represents the fraction of anomalies in the training set, and $O(L)$ represents the computational complexity of solving a linear optimization problem.

Table 1

Computational complexity of our techniques.

Techniques	Computational complexity
QSSVM	$$O(L)$$
LADS	$$O(n\log n)$$
LADQS	$$O(n)$$

5. Conclusion

In this paper we propose two lightweight anomaly detection algorithms for WSNs, LADS and LADQS. Both algorithms are based on QSSVM but convert the linear optimization problem of QSSVM to a sort problem. Simulation results show that our algorithms reduce the computational complexity while achieving the same accuracy for anomaly detection. Our future research includes selecting the optimal parameters for v and implementing our algorithms on multiple sensor nodes in real-life.