# Lightweight Anomaly Detection for Wireless Sensor Networks

Authors: Pu Cheng; Minghua Zhu
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## 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.


---

## Body

## 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 Section2. 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(n3) 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 thatn data vectors {xi∈Rd,i=1,…,n} of d variables in the input space are mapped into the feature space using a certain nonlinear mapping function ϕ(g). The constrained optimization problem of QSSVM can be formalized as follows:(1)minR∈R,ξ∈RnR2+1vn∑i=1nξisubject  to:ϕxi2≤R2+ξi,ξi≥0,i=1,…,n,where {ξi:i=1,2,…,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∈(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ϕ(xi)2 are replaced by the kernels k(xi,xi). The dual formulation of (1) will become(2)minα∈Rn-∑i=1nαikxi,xisubject  to:∑i=1nαi=1,0≤αi≤1vn,i=1,…,n.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(xi,xi) 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:(3)ϕxic=ϕxi-1n∑i=1nϕxi.There is no explicit vector in feature space that represents the mean; however the dot productKc=(ϕ(xi)c,ϕ(xj)c) of the centred image vectors can be obtained in terms of the kernel matrix K=k(xi,xj)=(ϕ(xi)·ϕ(xj)) using Kc=K-1nK-K1n+1nK1n, where 1n is an n×n matrix with all values equal to 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(xi,xi) of (2) are replaced by the diagonal elements kc(xi,xi) of the centered kernel matrix Kc. kc(xi,xi) can be considered as the distances between data vectors xi and the origin of its centered quarter-sphere in the feature space. Consequently, the dual problem (2) can be solved.After solving (2) for {αi}, the data vectors can be classified as follows. Data vectors with αi=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 αi=1/vn are considered as anomalies, which lie outside the hypersphere. Data vectors with 0<αi<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 R2=kc(xi,xi) for any border support vector xi.


### 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 radiusR of one-class quarter-sphere for the training set, which can be obtained by the distances between border support vectors xi and its origin in the feature space using R2=kc(xi,xi). This process has high computational and memory complexity due to the fact that it requires solving the linear programme and finding data vectors xi with 0<αi<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 kc(xi,xi) between data vector xi with 0<αi<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(xi,xi) of (2) have been actually replaced by the diagonal elements kc(xi,xi) of the centered kernel matrix Kc 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 kc(xi,xi) corresponding to αi satisfying the formulation of (2) and 0<αi<1/vn, instead of solving the linear programme for (2).In order to find the minimal radiusR, the sequence {kc(xi,xi)} is sorted in descending order and becomes {kc(x1′,x1′),kc(x2′,x2′),…,kc(xn′,xn′)}, where kc(x1′,x1′)≥kc(x2′,x2′)≥⋯≥kc(xn′,xn′). For convenience, we replace kc(xi,xi) with di. Consequently, the dual formulation of (2) will be simplified to(4)maxα∈Rn∑i=1nαi′di′subject  to:∑i=1nαi′=1,0≤αi′≤1vn,i=1,…,n,where d1′≥d2′≥⋯≥dn′, v∈(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αi′=αj′ if and only if di′=dj′. 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 radiusR can be computed directly from the descending sequence {d1′,d2′,…,dn′} through the parameters v and n.Theorem 1.
If the values ofα1′,α2′,…,αn′ are the solution of (4), one has α1′≥α2′≥⋯≥αn′.Proof.
Sinceα1′,α2′,…,αn′ is the solution of (4), the value of the objective function attains maximum under the constrained condition and can be denoted as f1=α1′d1′+α2′d2′+⋯+αn′dn′.
Firstly, we prove thatα1′ is the maximum of {α1′,α2′,…,αn′} if d1′ is the maximum of {d1′,d2′,…,dn′}. Assume the contrary that the value of α1′ is not maximal if the value of d1′ is maximal. This assumption indicates that there exists αj′ such that value of αj′ is the maximal of {αi′}. We exchange the value of αj′ with α1′, so the value of the objective function becomes(5)f2=αj′d1′+α2′d2′+⋯+αj-1′dj-1′+α1′dj′+αj+1′dj+1′+⋯+αn′dn′.
Subtractf1 from f2 and we have(6)f2-f1=αj′d1′+α1′dj′-α1′d1′+αj′dj′=d1′-dj′αj′-α1′.
From the contradictions, we haved1′≥dj′ and αj′≥α1′. So we get f2-f1≥0. This contradicts the fact that f1 is not the maximum of the objective function. Thus we have derived that α1′ is the maximum of {αi′∣i′=1,2,…,n}.
In a similar way, we can prove thatα2′ is the second maximum of {α1′,α2′,…,αn′}, if d2′ is the second maximum of {d1′,d2′,…,dn′}. And so, we can prove that αi′ is the ith maximum of {α1′,α2′,…,αn′} if di′ is the ith maximum of {d1′,d2′,…,dn′}.
As proved above, it is evident thatα1′≥α2′≥⋯≥αn′ if the values of α1′,α2′,…,αn′ are the solution of (4). This completes the proof.According to Theorem1, we can infer Theorems 2 and 3 as follows.Theorem 2.
If the values of{α1′,α2′,…,αn′} are the solution of (4), one has 0<αj+1′<1/vn when j=vn and j≠vn.Proof.
Since one of the constraint conditions is0≤αi′≤1/vn, Theorem 3 will be proved if we can show that αj+1′≠0 and αj+1′≠1/vn when j=vn and j≠vn. If the assertion were not true, then we would have αj+1′=0 or αj+1′=1/vn when j=vn and j≠vn.
Recalling Theorem1, we have 1/vn≥α1′≥⋯≥αj′≥αj+1′≥⋯≥αn′≥0. By the assumption of αj+1′=0, it is easy to see that αj+1′=αj+2′=⋯=αn′=0. And we have ∑i=1nαi=∑i=1jαi≤j/vn. When j=vn and j≠vn, the above inequation will become ∑i=1nαi≤j/vn<1. This contradicts the fact of ∑i=1nαi=1. By the assumption of αj+1′=1/vn, it is clear that α1′=α2′=⋯=αj′=αj+1′=1/vn. And we get ∑i=1nαi≥j+1/vn. When j=vn and j≠vn, the inequation will become ∑i=1nαi≥j+1/vn>1. This is contrary to the constraint condition of ∑i=1nαi=1. This completes the proof.Theorem 3.
Given that the values of{α1′,α2′,…,αn′} are the solution of (4), if j=vn and j=vn, one hasif(7)d1′=d2′=⋯=dn′,α1′=α2′=⋯=αn′;otherwise,(8)α1′=⋯=αj′=1vn,αj+1′=⋯=αn′=0.Proof.
In the case whend1′=d2′=⋯=dn′, obviously, we have α1′=α2′=⋯=αn′ by the implied constraint that there exists αi′=αj′ if and only if di′=dj′. In the other cases, let the value βi′ of αi′ be the solution of (4). If the assertion were not true, we would have the value βi′ of αi′ such that βk′≠1/vn or βl′≠0, where k∈{1,…,j} and l∈{j+1,…,n}. Consequently, the value of objective function becomes f1=∑i=1nβi′di′. When α1′=α2′=⋯=αj′=1/vn and αj+1′=⋯=αn′=0, where j=vn and j=vn, let the value of objective function be f2=∑i=1nαi′di′=1/vn∑i=1jdi′. Since the value βi′ of αi′ is the solution of (4), f1 is the maximal of the objective function and f1≥f2. Subtract f1 from f2 and we have f2-f1=(1/vn-β1′)d1′+⋯+(1/vn-βj′)dj′-βj+1′dj+1′-⋯-βn′dn′. Recalling Theorem 1 and the constraints, we have 1/vn≥α1′≥⋯≥αj′≥αj+1′≥⋯≥αn′≥0 and d1′≥⋯≥dj′≥dj+1′≥⋯≥dn′≥0. So we get f2-f1≥(1/vn-β1′)d1′+⋯+(1/vn-βj′)dj′-βj+1′dj′-⋯-βn′dj′. According to the implied constraint, the equality sign holds if and only if dj′=dj+1′=⋯=dn′ or βj+1′=⋯=βn′=0. And we also have f2-f1≥(1/vn-β1′)dj′+⋯+(1/vn-βj′)dj′-βj+1′dj′-⋯-βn′dj′, where the equality sign holds if and only if (d1′=⋯=dj′ and dj′=dj+1′=⋯=dn′) or (β1′=⋯=βj′=1/vn and βj+1′=⋯=βn′=0). However, this is not the case when d1′=d2′=⋯=dn′ and the definition and condition of βi′ show that βk′≠1/vn or βl′≠0, where k∈{1,…,j} and l∈{j+1,…,n}. So the equality sign does not hold and we have f2-f1>(1/vn-β1′)dj′+⋯+(1/vn-βj′)dj′-βj+1′dj′-⋯-βn′dj′. And we get f2-f1>(j/vn-β1′-⋯-βn′)dj′. From j=vn and j=vn and the constraint of ∑i=1nβi′=1, we obtain f2-f1>0. This is contrary to f1>f2. That is, it completes the proof.Theorem 4.
The minimal radiusR of the quarter-sphere in QSSVM can be obtained by(9)R2=dj+1′,where dj+1′ is the (j+1)th largest squared distances kc(xi,xi) between xi 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(xi,xi) of (2) are replaced by kc(xi,xi). After calculating the values of {α1,α2,…,αn} in (2), the minimal radius R of the quarter-sphere in QSSVM can be computed using R2=kc(xi,xi) for any data vector xi with 0<αi<1/vn. Given di=kc(xi,xi), when {kc(xi,xi)} 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≠vn,we have 0<αj+1′<1/vn from Theorem 3 and R2=dj+1′. In the second case when j=vn and j=vn, we have α1′=α2′=⋯=αn′ or α1′=α2′=⋯=αj′=1/vn, αj+1′=⋯=αn′=0 from Theorem 2. The fact of α1′=α2′=⋯=αn′ means that we get 0<α1′=⋯=αj′=1/n<1/vn by the constraints of ∑i=1nαi=1 and v∈(0,1) and R2=dj+1′. The fact of α1′=α2′=⋯=αj′=1/vn and αj+1′=⋯=αn′=0 means that there are no border support vectors xi′, which are the vectors with 0<αi′<1/vn. By the decision rule of QSSVM, the vectors with αi′=0 or the vectors with αi′=1/vn are considered as normal or anomalies, respectively. And their squared distances to origin are, respectively, not larger or larger than dj+1′, which means the largest squared distance between the normal vectors and the origin. Therefore the minimal radius R can be treated as dj+1′. Moreover, we have R2=dj+1′ in both cases. This completes the proof.From Theorem4, 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 {kc(xi,xi)}. 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 vectorsxi 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 {kc(xi′,xi′)}, where kc(x1′,x1′)≥⋯≥kc(xn′,xn′). The (j+1)th largest squared distance kc(xj′,xj′) (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 Algorithm1.Algorithm 1
Step  1. Calculate kc(xi,xi).
Step  2. Sort kc(xi,xi) in descending order and have kcxi′,xi′.
Step  3. Calculate R=d(j+1)′ using (9).
Step  4. If kc(xi,xi)>R2
xi is outlier
Else
xi is normal
End If


### 3.3. Lightweight Anomaly Detection Algorithm Using Quick Select

As discussed in the previous section, the minimal radiusR of the quarter-sphere in QSSVM can be obtained from the descending sequence {kc(xi′,xi′)}. The computational complexity for obtaining the descending sequence is O(nlog2⁡n). In fact, the process for the descending sequence is unnecessary, because R can be determined by (9) if the (vn+1)th largest element of the original sequence {kc(xi,xi)} can be found. So we propose an anomaly detection method LADQS based on Quickselect algorithm [14] to find the (vn+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(nlog2⁡n) to O(n). The pseudocode of LADQS algorithm is shown in Algorithm 2.Algorithm 2:The pseudocode of LADQS algorithm.
function LADQS()
let{xi∈Rd,i=1,…,n} be the data vectors in the training set;
calculate the distancek(xi,xi) to origin for each data vector xi;
obtainA={k(xi,xi),i=1,…,n};
returnR = QuickSelect(A,1,n,vn+1)
// Returns thenth largest element of list.
function QuickSelect(list,l,r,n)
ifl=r      // If the list contains only one element
return list[l]  // Return that element
pivotIndex =l + floor(rand() ∗ (r-l+1))
// randomly select a pivotIndex betweenl and r
pivotIndex = QuickPartition(list,l, r, pivotIndex)
ifn = pivotIndex
return list[n]
else ifn < pivotIndex
return QuickSelect(list,l, pivotIndex − 1, n)
else
return QuickSelect(list, pivotIndex + 1,r, n)


## 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 thatn data vectors {xi∈Rd,i=1,…,n} of d variables in the input space are mapped into the feature space using a certain nonlinear mapping function ϕ(g). The constrained optimization problem of QSSVM can be formalized as follows:(1)minR∈R,ξ∈RnR2+1vn∑i=1nξisubject  to:ϕxi2≤R2+ξi,ξi≥0,i=1,…,n,where {ξi:i=1,2,…,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∈(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ϕ(xi)2 are replaced by the kernels k(xi,xi). The dual formulation of (1) will become(2)minα∈Rn-∑i=1nαikxi,xisubject  to:∑i=1nαi=1,0≤αi≤1vn,i=1,…,n.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(xi,xi) 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:(3)ϕxic=ϕxi-1n∑i=1nϕxi.There is no explicit vector in feature space that represents the mean; however the dot productKc=(ϕ(xi)c,ϕ(xj)c) of the centred image vectors can be obtained in terms of the kernel matrix K=k(xi,xj)=(ϕ(xi)·ϕ(xj)) using Kc=K-1nK-K1n+1nK1n, where 1n is an n×n matrix with all values equal to 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(xi,xi) of (2) are replaced by the diagonal elements kc(xi,xi) of the centered kernel matrix Kc. kc(xi,xi) can be considered as the distances between data vectors xi and the origin of its centered quarter-sphere in the feature space. Consequently, the dual problem (2) can be solved.After solving (2) for {αi}, the data vectors can be classified as follows. Data vectors with αi=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 αi=1/vn are considered as anomalies, which lie outside the hypersphere. Data vectors with 0<αi<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 R2=kc(xi,xi) for any border support vector xi.


## 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 radiusR of one-class quarter-sphere for the training set, which can be obtained by the distances between border support vectors xi and its origin in the feature space using R2=kc(xi,xi). This process has high computational and memory complexity due to the fact that it requires solving the linear programme and finding data vectors xi with 0<αi<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 kc(xi,xi) between data vector xi with 0<αi<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(xi,xi) of (2) have been actually replaced by the diagonal elements kc(xi,xi) of the centered kernel matrix Kc 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 kc(xi,xi) corresponding to αi satisfying the formulation of (2) and 0<αi<1/vn, instead of solving the linear programme for (2).In order to find the minimal radiusR, the sequence {kc(xi,xi)} is sorted in descending order and becomes {kc(x1′,x1′),kc(x2′,x2′),…,kc(xn′,xn′)}, where kc(x1′,x1′)≥kc(x2′,x2′)≥⋯≥kc(xn′,xn′). For convenience, we replace kc(xi,xi) with di. Consequently, the dual formulation of (2) will be simplified to(4)maxα∈Rn∑i=1nαi′di′subject  to:∑i=1nαi′=1,0≤αi′≤1vn,i=1,…,n,where d1′≥d2′≥⋯≥dn′, v∈(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αi′=αj′ if and only if di′=dj′. 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 radiusR can be computed directly from the descending sequence {d1′,d2′,…,dn′} through the parameters v and n.Theorem 1.
If the values ofα1′,α2′,…,αn′ are the solution of (4), one has α1′≥α2′≥⋯≥αn′.Proof.
Sinceα1′,α2′,…,αn′ is the solution of (4), the value of the objective function attains maximum under the constrained condition and can be denoted as f1=α1′d1′+α2′d2′+⋯+αn′dn′.
Firstly, we prove thatα1′ is the maximum of {α1′,α2′,…,αn′} if d1′ is the maximum of {d1′,d2′,…,dn′}. Assume the contrary that the value of α1′ is not maximal if the value of d1′ is maximal. This assumption indicates that there exists αj′ such that value of αj′ is the maximal of {αi′}. We exchange the value of αj′ with α1′, so the value of the objective function becomes(5)f2=αj′d1′+α2′d2′+⋯+αj-1′dj-1′+α1′dj′+αj+1′dj+1′+⋯+αn′dn′.
Subtractf1 from f2 and we have(6)f2-f1=αj′d1′+α1′dj′-α1′d1′+αj′dj′=d1′-dj′αj′-α1′.
From the contradictions, we haved1′≥dj′ and αj′≥α1′. So we get f2-f1≥0. This contradicts the fact that f1 is not the maximum of the objective function. Thus we have derived that α1′ is the maximum of {αi′∣i′=1,2,…,n}.
In a similar way, we can prove thatα2′ is the second maximum of {α1′,α2′,…,αn′}, if d2′ is the second maximum of {d1′,d2′,…,dn′}. And so, we can prove that αi′ is the ith maximum of {α1′,α2′,…,αn′} if di′ is the ith maximum of {d1′,d2′,…,dn′}.
As proved above, it is evident thatα1′≥α2′≥⋯≥αn′ if the values of α1′,α2′,…,αn′ are the solution of (4). This completes the proof.According to Theorem1, we can infer Theorems 2 and 3 as follows.Theorem 2.
If the values of{α1′,α2′,…,αn′} are the solution of (4), one has 0<αj+1′<1/vn when j=vn and j≠vn.Proof.
Since one of the constraint conditions is0≤αi′≤1/vn, Theorem 3 will be proved if we can show that αj+1′≠0 and αj+1′≠1/vn when j=vn and j≠vn. If the assertion were not true, then we would have αj+1′=0 or αj+1′=1/vn when j=vn and j≠vn.
Recalling Theorem1, we have 1/vn≥α1′≥⋯≥αj′≥αj+1′≥⋯≥αn′≥0. By the assumption of αj+1′=0, it is easy to see that αj+1′=αj+2′=⋯=αn′=0. And we have ∑i=1nαi=∑i=1jαi≤j/vn. When j=vn and j≠vn, the above inequation will become ∑i=1nαi≤j/vn<1. This contradicts the fact of ∑i=1nαi=1. By the assumption of αj+1′=1/vn, it is clear that α1′=α2′=⋯=αj′=αj+1′=1/vn. And we get ∑i=1nαi≥j+1/vn. When j=vn and j≠vn, the inequation will become ∑i=1nαi≥j+1/vn>1. This is contrary to the constraint condition of ∑i=1nαi=1. This completes the proof.Theorem 3.
Given that the values of{α1′,α2′,…,αn′} are the solution of (4), if j=vn and j=vn, one hasif(7)d1′=d2′=⋯=dn′,α1′=α2′=⋯=αn′;otherwise,(8)α1′=⋯=αj′=1vn,αj+1′=⋯=αn′=0.Proof.
In the case whend1′=d2′=⋯=dn′, obviously, we have α1′=α2′=⋯=αn′ by the implied constraint that there exists αi′=αj′ if and only if di′=dj′. In the other cases, let the value βi′ of αi′ be the solution of (4). If the assertion were not true, we would have the value βi′ of αi′ such that βk′≠1/vn or βl′≠0, where k∈{1,…,j} and l∈{j+1,…,n}. Consequently, the value of objective function becomes f1=∑i=1nβi′di′. When α1′=α2′=⋯=αj′=1/vn and αj+1′=⋯=αn′=0, where j=vn and j=vn, let the value of objective function be f2=∑i=1nαi′di′=1/vn∑i=1jdi′. Since the value βi′ of αi′ is the solution of (4), f1 is the maximal of the objective function and f1≥f2. Subtract f1 from f2 and we have f2-f1=(1/vn-β1′)d1′+⋯+(1/vn-βj′)dj′-βj+1′dj+1′-⋯-βn′dn′. Recalling Theorem 1 and the constraints, we have 1/vn≥α1′≥⋯≥αj′≥αj+1′≥⋯≥αn′≥0 and d1′≥⋯≥dj′≥dj+1′≥⋯≥dn′≥0. So we get f2-f1≥(1/vn-β1′)d1′+⋯+(1/vn-βj′)dj′-βj+1′dj′-⋯-βn′dj′. According to the implied constraint, the equality sign holds if and only if dj′=dj+1′=⋯=dn′ or βj+1′=⋯=βn′=0. And we also have f2-f1≥(1/vn-β1′)dj′+⋯+(1/vn-βj′)dj′-βj+1′dj′-⋯-βn′dj′, where the equality sign holds if and only if (d1′=⋯=dj′ and dj′=dj+1′=⋯=dn′) or (β1′=⋯=βj′=1/vn and βj+1′=⋯=βn′=0). However, this is not the case when d1′=d2′=⋯=dn′ and the definition and condition of βi′ show that βk′≠1/vn or βl′≠0, where k∈{1,…,j} and l∈{j+1,…,n}. So the equality sign does not hold and we have f2-f1>(1/vn-β1′)dj′+⋯+(1/vn-βj′)dj′-βj+1′dj′-⋯-βn′dj′. And we get f2-f1>(j/vn-β1′-⋯-βn′)dj′. From j=vn and j=vn and the constraint of ∑i=1nβi′=1, we obtain f2-f1>0. This is contrary to f1>f2. That is, it completes the proof.Theorem 4.
The minimal radiusR of the quarter-sphere in QSSVM can be obtained by(9)R2=dj+1′,where dj+1′ is the (j+1)th largest squared distances kc(xi,xi) between xi 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(xi,xi) of (2) are replaced by kc(xi,xi). After calculating the values of {α1,α2,…,αn} in (2), the minimal radius R of the quarter-sphere in QSSVM can be computed using R2=kc(xi,xi) for any data vector xi with 0<αi<1/vn. Given di=kc(xi,xi), when {kc(xi,xi)} 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≠vn,we have 0<αj+1′<1/vn from Theorem 3 and R2=dj+1′. In the second case when j=vn and j=vn, we have α1′=α2′=⋯=αn′ or α1′=α2′=⋯=αj′=1/vn, αj+1′=⋯=αn′=0 from Theorem 2. The fact of α1′=α2′=⋯=αn′ means that we get 0<α1′=⋯=αj′=1/n<1/vn by the constraints of ∑i=1nαi=1 and v∈(0,1) and R2=dj+1′. The fact of α1′=α2′=⋯=αj′=1/vn and αj+1′=⋯=αn′=0 means that there are no border support vectors xi′, which are the vectors with 0<αi′<1/vn. By the decision rule of QSSVM, the vectors with αi′=0 or the vectors with αi′=1/vn are considered as normal or anomalies, respectively. And their squared distances to origin are, respectively, not larger or larger than dj+1′, which means the largest squared distance between the normal vectors and the origin. Therefore the minimal radius R can be treated as dj+1′. Moreover, we have R2=dj+1′ in both cases. This completes the proof.From Theorem4, 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 {kc(xi,xi)}. 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 vectorsxi 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 {kc(xi′,xi′)}, where kc(x1′,x1′)≥⋯≥kc(xn′,xn′). The (j+1)th largest squared distance kc(xj′,xj′) (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 Algorithm1.Algorithm 1
Step  1. Calculate kc(xi,xi).
Step  2. Sort kc(xi,xi) in descending order and have kcxi′,xi′.
Step  3. Calculate R=d(j+1)′ using (9).
Step  4. If kc(xi,xi)>R2
xi is outlier
Else
xi is normal
End If


## 3.3. Lightweight Anomaly Detection Algorithm Using Quick Select

As discussed in the previous section, the minimal radiusR of the quarter-sphere in QSSVM can be obtained from the descending sequence {kc(xi′,xi′)}. The computational complexity for obtaining the descending sequence is O(nlog2⁡n). In fact, the process for the descending sequence is unnecessary, because R can be determined by (9) if the (vn+1)th largest element of the original sequence {kc(xi,xi)} can be found. So we propose an anomaly detection method LADQS based on Quickselect algorithm [14] to find the (vn+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(nlog2⁡n) to O(n). The pseudocode of LADQS algorithm is shown in Algorithm 2.Algorithm 2:The pseudocode of LADQS algorithm.
function LADQS()
let{xi∈Rd,i=1,…,n} be the data vectors in the training set;
calculate the distancek(xi,xi) to origin for each data vector xi;
obtainA={k(xi,xi),i=1,…,n};
returnR = QuickSelect(A,1,n,vn+1)
// Returns thenth largest element of list.
function QuickSelect(list,l,r,n)
ifl=r      // If the list contains only one element
return list[l]  // Return that element
pivotIndex =l + floor(rand() ∗ (r-l+1))
// randomly select a pivotIndex betweenl and r
pivotIndex = QuickPartition(list,l, r, pivotIndex)
ifn = pivotIndex
return list[n]
else ifn < 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 Figure2. 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 [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 functionkRBF=exp(-x1-x22/σ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 parameterv 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.Figures3 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 parameterv selection.Figure 4
False alarm rate of LADS in terms of parameterv selection.Figure5 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 parameterv 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 Table1, 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
)


## 4.1. Experimental Datasets

The real data are collected from a closed neighborhood from a WSN deployed in Grand-Saint-Bernard as shown in Figure2. 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 [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 functionkRBF=exp(-x1-x22/σ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 parameterv 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.Figures3 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 parameterv selection.Figure 4
False alarm rate of LADS in terms of parameterv selection.Figure5 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 parameterv 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 Table1, 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 forv and implementing our algorithms on multiple sensor nodes in real-life.



---

*Source: 653232-2015-08-13.xml*