# SVM Based Event Detection and Identification: Exploiting Temporal Attribute Correlations Using SensGru

Authors: Nauman Shahid; Ijaz Haider Naqvi; Saad Bin Qaisar
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

In the context of anomaly detection in cyber physical systems (CPS), spatiotemporal correlations are crucial for
high detection rate. This work presents a new quarter sphere support vector machine (QS-SVM) formulation based
on the novel concept ofattribute correlations. Our event detection approach, SensGru, groups multiple sensors on
a single node and thus eliminates communication between sensor nodes without compromising the advantages of
spatial correlation. It makes use of temporal-attribute (TA) correlations and is thus a TA-QS-SVM formulation.
We show analytically that SensGru (or interchangeably TA-QS-SVM) results in a reduced node density and gives
the same event detection performance as more dense Spatiotemporal-Attribute Quarter-Sphere SVM (STA-QS-SVM)
formulation which exploits both spatiotemporal and attribute correlations. Moreover, this paper develops theoretical bounds on the internode distance, the optimal number of sensors, and the sensing range with SensGru so that the performance difference with SensGru and STA-QS-SVM is negligibly small. Both schemes achieve event detection
rates as high as 100% and an extremely low false positive rate.


---

## Body

## 1. Introduction

In cyber physical systems (CPS), monitoring and control applications using wireless sensor networks (WSN) have been gaining interest [1–3]; however, such systems are vulnerable to anomalies (malicious attacks, noise, and errors) [4–6]. Therefore, it is essential to identify anomalies to provide reliable functioning of network [7–9]. Anomalies may result from sensor faults (errors or outliers) or from an event of interest [10]. Anomaly and event detection in WSNs finds various applications [11–14], especially, disaster prevention, detection, and identification, for instance, in underground mine wells and volcanic sites [4].A comparison of various types of outlier detection techniques for WSNs has been carried out in [1].Classification based techniques learn a classification model in the training phase and then classify the data instance to one of the training classes [15]. They are grouped intoSupport Vector Machine (SVM) based andBayesian Network based approaches, depending upon the type of classification model that is used [1, 16]. In wireless sensor networks, a majority of energy is consumed in radio communication rather than in computation [1]. Hence, in order to make the system energy efficient, it is advantageous to decrease the communication overhead at the cost of increasing computational overhead in the network. SVM based approaches naturally fit in for these requirements, as they are unsupervised and nonparametric and perform in-network processing.The earliest known formulations of Support Vector Machines construct a set of hyperplanes [17, 18], hyperspheres [19], quarter-spheres (QS-SVM) [20], hyperellipsoids (TOCC) [21], centered hyperellipsoids [22] (CESVM), or conic segments (CS-SVM) [23] in a high dimensional space, which can be used for separation of normal and anomalous data (outliers and events). QS-SVM and CE-SVM have an advantage of linear optimization formulation as compared to the quadratic optimization for other. CS-SVM is more suited to multiclass problems; therefore, it is not used for outlier detection (one-class problem). A detailed analysis of one-class SVM based outlier detection techniques has been carried out in [24]. Amongst online schemes, QS-SVM scheme is more communication efficient as compared to online CE-SVM [25] and is therefore preferred over CE-SVM for outlier detection in WSNs [26]. QS-SVM techniques for outlier detectionuse only spatiotemporal correlations of nodes’ data, (hence, we call them Spatiotemporal Quarter-Sphere SVM (ST-QS-SVM)), ignoring the attribute correlations which must be incorporated for better outlier and event detection rates [1] (event detection rates have never been presented for these techniques).In our previous work, STA-QS-SVM formulation has been proposed [27] which incorporates attribute correlations into ST-QS-SVM and achieves better detection and false positive rates as compared to ST-QS-SVM. This paper introduces SensGru, a novel energy efficient, temporal-attribute based (TA-QS-SVM) formulation, which groups multiple sensors at a single node, and presents a thorough analysis of event detection performance of STA-QS-SVM and SensGru. We show analytically that SensGru (or interchangeably TA-QS-SVM) results in a reduced (as much as 75%) node density and gives the sameevent detection performance as more dense STA-QS-SVM formulation. Moreover, this paper develops theoretical bounds on the internode distance, the optimal number of sensors, and the sensing range with SensGru so that the performance difference with SensGru and STA-QS-SVM is negligibly small. Both schemes achieve event detection rates as high as 100% and an extremely low false positive rate.The main contributions of this paper are as follows.(1)
It establishes that SensGru can give a performance which is within a negligible difference to STA-QS-SVM. With this benchmark performance with SensGru, this paper further derives.(2)
The ratio of internode distance with SensGru to internode distance with STA-QS-SVM.(3)
Maximum sensing range with both schemes.(4)
The optimal value of the number of sensors with SensGru.(5)
The worst case performance analysis and distance ratio.(6)
The complexity analysis of both schemes.


## 2. Problem Statement

Figure1 presents the network model for both STA-QS-SVM and SensGru. The model for STA-QS-SVM considers a densely deployed homogeneous wireless sensor network in a stationary environment (whose spatial and temporal characteristics do not change), where the sensor nodes are localized and connected to each other, such that the sensor data are correlated in time and space. The nodes in the network are represented as Si. In a neighborhood, represented as N(Si), k boundary nodes are connected to a central node with an internode distance of rc units (as shown in Figure 1(a)). For TA-QS-SVM based SensGru, the internode distance is rc′; however, k sensors per attribute are grouped together on each node (as shown in Figure 1(b)). Hence, no communication is required for event detection based on temporal and attribute correlations. In case an anomaly gets detected, the nodes transmit with a higher power in order to increase their transmission radius and communicate with each other (details follow).RegionsR and R′ for STA-QS-SVM and TA-QS-SVM approaches.
(a)
RegionR for STA-QS-SVM
(b)
RegionR′ for SensGru (TA-QS-SVM)


### 2.1. Spatiotemporal and Attribute Correlations Based Outlier Detection in WSNs (STA-QS-SVM)

For STA-QS-SVM, the central nodeSi is considered to be within the radio transmission range rc of all other nodes in N(Si). The k spatially neighboring nodes of Si are represented by Sij, such that {j=1,2,…,k}. At each time interval m, each sensor node Si in the set N(Si) measures a d- dimensional data vector xm→. Thus, a sensor node equipped with d different types of sensors will sense a d-point data vector. Let xm0→,xm1→,xm2→,…,xmk→ denote the d-point data vectors at Si,Si1,Si2,…,Sik, in the set N(Si), at the mth time instant, respectively. The goal is to identify every new measurement arriving at Si as normal or anomalous in real-time. STA-QS-SVM determines the radius of quarter-sphere based onattribute correlations in addition to thespatiotemporal correlations.LetRi and R*i be temporal and attribute radii of quarter-spheres that have to be determined during the training phase from a set of n measurements Xi={x1i→,x2i→,…,xni→} at the nodes Si in the set N(Si), corresponding to n time instants, where d is the number of attributes/data points corresponding to each vector. Let the vectors xmi→ at each time instant m be mapped onto feature space via some function ϕ(xmi).The constrained optimization problem of the one-class centered quarter-sphere SVM based on spatiotemporal correlations (ST-QS-SVM) is formulated as in [26] to obtain the radius Ri and identify support, nonsupport, and border support vectors based on the Lagrangian multiplier αm values. The other part of this problem consists of applying the quarter-sphere SVM formulation along the d attributes of received vectors xmi→. This is done at each node Si of the set N(Si) and at each time instant m, to determine the radius R*i and the set of support vectors based on attribute correlations [27].Consider the training data setXi consisting of n,d point data vectors x1i→,x2i→,x3i→,…,xni→, at node Si and let the vectors xmi→ at each time instant m be mapped onto feature space via some function ϕ*(xmi). We divide the received data set Xi of dimension n×d into n/d portions of d×d dimensions each named as Xip. Each row of Xip corresponds to a data measurement at a specific time instant, whereas each column corresponds to a specific attribute over different time instants. Our approach, based on attribute correlations, applies the constrained optimization problem of one-class quarter-sphere to each Xip, where p=1,2,…,n/d, using each column of Xip as a d-point data vector. Thus, we treat a single attribute of the d consecutive time measurements as a vector for optimization purpose, in contrast to the previous spatiotemporal approach (ST-QS-SVM), which takes into account each row of Xi as a vector for optimization. For details on formulation of n/d dimensional vector optimization problem and its solution and the algorithm for outlier and event detection, the reader is referred to [27].By using some effective linear optimization techniques, we can compute the Lagrangian multipliers,αp,q*i, ∀q=1,2,…,d, p=1,2,…,n/d. We obtain n/d sets of αp,q*i, corresponding to n/d portions of  Xi, each set containing d number of αp,q*i. The vectors present in each of the pth portion of Xi can be further classified depending on the results of αp,q*i. The data vectors with αp,q*i=0, which fall inside the quarter-sphere and whose distances from the origin are smaller than the radius of the quarter-sphere, are called nonsupport vectors. The data vectors with αp,q*i>0 are called margin support vectors. Their distances to the origin indicate the radius of the quarter-sphere. Support vectors with αp,q*i=1/vd, which fall outside the quarter-sphere and whose distances from the origin are larger than the radius of the quarter-sphere, are called nonmargin support vectors. These data vectors are called outliers. The norm of support vectors with 0<αp,q*i<1/vd determines the radius R*i. Since we have n/d sets of support vectors, we determine n/d values of radius Rp*i from each set using these support vectors
(1)Rp*i2=kc*xp,qi→,xp,qi→,
where kc*(xp,qi→,xp,qi→) is a centralized kernel function. The final attribute radius is then determined by taking the median of all n/d radii:
(2)R*i=medianR1*i,R2*i,…,Rn/d*i.


### 2.2. SensGru: The Communication Independent Approach to Anomaly Detection

Now, consider the problem of a wireless sensor network, consisting of localized nodesSi. Assume that the nodes do not lie in a closed neighborhood to any other nodes and are separated by a distance rc′. Also, let rc′=C·rc, where C>1. Also, assume that each region R′ contains only one node Si (as shown in Figure 1(b)) with k sensors for each attribute. Hence, no communication is required for majority voting based event detection. The SVM based approaches identify outliers based on temporal deviations and then exploit spatial information of neighboring nodes to identify events from the detected outliers. This approach, however, considers exploiting only the temporal and attribute information at each node Si, to identify both outliers and events. Assuming that an event at node Si is equally likely to be detected in the neighborhood N(Si) due to spatial correlations [12], events are identified by introducing a consensus of multiple sensors at Si. The probability of a faulty node reporting a low measurement in an event region cannot be ignored [12]. Thus, the presence of multiple sensors for each attribute at each node incorporates the flexibility of some faulty sensors at each Si. Assuming that the probability of all sensor nodes being faulty together is very low, this system detects events at a high rate based on majority voting.The nodeSi in R′, thus, has k sensors for measuring each of the d attributes, where k={2,3,…,t}, t being the maximum number of sensors which can be deployed at Si. We define a sensor array as a group of sensors which measure d different attributes. Let sji represent the jth sensor array for measuring d attributes at ith node:
(3)Si=s1i,s2i,…,ski,
where each sji measures d different attributes
(4)sji=s1jis2ji⋯sdjiT.Letxdmj be the d attribute data vector corresponding to the jth sensor array measured at mth time instant at ith node, such that j={1,2,…,k} and m={1,2,…,n}. Thus, a set of k data vectors Xm, at the jth node, corresponding to k sensor arrays will be obtained at the mth time instant:
(5)Xm=xdm1,xdm2,…,xdmk,wherexdmj=x1mjx2mj⋯xdmjT.The problem is to identify each newly arrived data vectorxdmj at each of the k sensor arrays as normal or anomalous in real time using temporal and attribute correlations only, based on quarter-sphere one-class SVM formulation.When a new data measurementxnewj arrives at node Si, it computes the distance d(x)cj, which is the mean of the distances between xnewj and origin of its centered quarter-spheres in the feature space, using the kernels. Thus, a set of k distances d(x)cj, corresponding to k sensor arrays, is obtained at each node Si. Now, we make use of the reading from k sensors to find the spatial radius Ri. The temporal radius R*i is found in a similar manner described above. Once we have both these radii, we use the algorithm presented in [27] to identify an outlier or event at each sensor node. The two approaches are linked by the analysis that follows. This paper addresses several unanswered questions. The most important contribution of this paper is that it develops theoretical bounds on important parameters with SensGru required to achieve the same performance as the spatiotemporal-attribute approach. It serves as a mathematical justification of the fact that SensGru is feasible (much more cost efficient), at a cost of deploying a few additional sensors at each node.


## 2.1. Spatiotemporal and Attribute Correlations Based Outlier Detection in WSNs (STA-QS-SVM)

For STA-QS-SVM, the central nodeSi is considered to be within the radio transmission range rc of all other nodes in N(Si). The k spatially neighboring nodes of Si are represented by Sij, such that {j=1,2,…,k}. At each time interval m, each sensor node Si in the set N(Si) measures a d- dimensional data vector xm→. Thus, a sensor node equipped with d different types of sensors will sense a d-point data vector. Let xm0→,xm1→,xm2→,…,xmk→ denote the d-point data vectors at Si,Si1,Si2,…,Sik, in the set N(Si), at the mth time instant, respectively. The goal is to identify every new measurement arriving at Si as normal or anomalous in real-time. STA-QS-SVM determines the radius of quarter-sphere based onattribute correlations in addition to thespatiotemporal correlations.LetRi and R*i be temporal and attribute radii of quarter-spheres that have to be determined during the training phase from a set of n measurements Xi={x1i→,x2i→,…,xni→} at the nodes Si in the set N(Si), corresponding to n time instants, where d is the number of attributes/data points corresponding to each vector. Let the vectors xmi→ at each time instant m be mapped onto feature space via some function ϕ(xmi).The constrained optimization problem of the one-class centered quarter-sphere SVM based on spatiotemporal correlations (ST-QS-SVM) is formulated as in [26] to obtain the radius Ri and identify support, nonsupport, and border support vectors based on the Lagrangian multiplier αm values. The other part of this problem consists of applying the quarter-sphere SVM formulation along the d attributes of received vectors xmi→. This is done at each node Si of the set N(Si) and at each time instant m, to determine the radius R*i and the set of support vectors based on attribute correlations [27].Consider the training data setXi consisting of n,d point data vectors x1i→,x2i→,x3i→,…,xni→, at node Si and let the vectors xmi→ at each time instant m be mapped onto feature space via some function ϕ*(xmi). We divide the received data set Xi of dimension n×d into n/d portions of d×d dimensions each named as Xip. Each row of Xip corresponds to a data measurement at a specific time instant, whereas each column corresponds to a specific attribute over different time instants. Our approach, based on attribute correlations, applies the constrained optimization problem of one-class quarter-sphere to each Xip, where p=1,2,…,n/d, using each column of Xip as a d-point data vector. Thus, we treat a single attribute of the d consecutive time measurements as a vector for optimization purpose, in contrast to the previous spatiotemporal approach (ST-QS-SVM), which takes into account each row of Xi as a vector for optimization. For details on formulation of n/d dimensional vector optimization problem and its solution and the algorithm for outlier and event detection, the reader is referred to [27].By using some effective linear optimization techniques, we can compute the Lagrangian multipliers,αp,q*i, ∀q=1,2,…,d, p=1,2,…,n/d. We obtain n/d sets of αp,q*i, corresponding to n/d portions of  Xi, each set containing d number of αp,q*i. The vectors present in each of the pth portion of Xi can be further classified depending on the results of αp,q*i. The data vectors with αp,q*i=0, which fall inside the quarter-sphere and whose distances from the origin are smaller than the radius of the quarter-sphere, are called nonsupport vectors. The data vectors with αp,q*i>0 are called margin support vectors. Their distances to the origin indicate the radius of the quarter-sphere. Support vectors with αp,q*i=1/vd, which fall outside the quarter-sphere and whose distances from the origin are larger than the radius of the quarter-sphere, are called nonmargin support vectors. These data vectors are called outliers. The norm of support vectors with 0<αp,q*i<1/vd determines the radius R*i. Since we have n/d sets of support vectors, we determine n/d values of radius Rp*i from each set using these support vectors
(1)Rp*i2=kc*xp,qi→,xp,qi→,
where kc*(xp,qi→,xp,qi→) is a centralized kernel function. The final attribute radius is then determined by taking the median of all n/d radii:
(2)R*i=medianR1*i,R2*i,…,Rn/d*i.


## 2.2. SensGru: The Communication Independent Approach to Anomaly Detection

Now, consider the problem of a wireless sensor network, consisting of localized nodesSi. Assume that the nodes do not lie in a closed neighborhood to any other nodes and are separated by a distance rc′. Also, let rc′=C·rc, where C>1. Also, assume that each region R′ contains only one node Si (as shown in Figure 1(b)) with k sensors for each attribute. Hence, no communication is required for majority voting based event detection. The SVM based approaches identify outliers based on temporal deviations and then exploit spatial information of neighboring nodes to identify events from the detected outliers. This approach, however, considers exploiting only the temporal and attribute information at each node Si, to identify both outliers and events. Assuming that an event at node Si is equally likely to be detected in the neighborhood N(Si) due to spatial correlations [12], events are identified by introducing a consensus of multiple sensors at Si. The probability of a faulty node reporting a low measurement in an event region cannot be ignored [12]. Thus, the presence of multiple sensors for each attribute at each node incorporates the flexibility of some faulty sensors at each Si. Assuming that the probability of all sensor nodes being faulty together is very low, this system detects events at a high rate based on majority voting.The nodeSi in R′, thus, has k sensors for measuring each of the d attributes, where k={2,3,…,t}, t being the maximum number of sensors which can be deployed at Si. We define a sensor array as a group of sensors which measure d different attributes. Let sji represent the jth sensor array for measuring d attributes at ith node:
(3)Si=s1i,s2i,…,ski,
where each sji measures d different attributes
(4)sji=s1jis2ji⋯sdjiT.Letxdmj be the d attribute data vector corresponding to the jth sensor array measured at mth time instant at ith node, such that j={1,2,…,k} and m={1,2,…,n}. Thus, a set of k data vectors Xm, at the jth node, corresponding to k sensor arrays will be obtained at the mth time instant:
(5)Xm=xdm1,xdm2,…,xdmk,wherexdmj=x1mjx2mj⋯xdmjT.The problem is to identify each newly arrived data vectorxdmj at each of the k sensor arrays as normal or anomalous in real time using temporal and attribute correlations only, based on quarter-sphere one-class SVM formulation.When a new data measurementxnewj arrives at node Si, it computes the distance d(x)cj, which is the mean of the distances between xnewj and origin of its centered quarter-spheres in the feature space, using the kernels. Thus, a set of k distances d(x)cj, corresponding to k sensor arrays, is obtained at each node Si. Now, we make use of the reading from k sensors to find the spatial radius Ri. The temporal radius R*i is found in a similar manner described above. Once we have both these radii, we use the algorithm presented in [27] to identify an outlier or event at each sensor node. The two approaches are linked by the analysis that follows. This paper addresses several unanswered questions. The most important contribution of this paper is that it develops theoretical bounds on important parameters with SensGru required to achieve the same performance as the spatiotemporal-attribute approach. It serves as a mathematical justification of the fact that SensGru is feasible (much more cost efficient), at a cost of deploying a few additional sensors at each node.


## 3. Analysis of Event Detection in STA-QS-SVM and TA-QS-SVM

LetR be a uniform circular region consisting of exactly k sensors for the STA-QS-SVM approach. k-1 of the k sensors are uniformly distributed around the boundary at a distance of rc from the sensor present at the center of the region. Also, consider another similar region R′, consisting of a single sensor node with exactly k sensors, for the TA-QS-SVM approach. Let rc′=C·rc, where C>1, (we call C the distance ratio) be the distance between the node of the region R′ and nodes in similar neighboring regions. Each sensor in regions R and R′ has a radio communication range rc and a sensing range rs. The problem is to evaluate C, such that the performance of the event detection techniques in both the deployments is approximately the same:
(6)DRSTA-DRTA<ϵ,
where ϵ≪1 and DRSTA and DRTA are the detection rates of STA-QS-SVM and TA-QS-SVM techniques, respectively, and C is defined as the distance ratio:
(7)C=DistancebetweenthenodesinTA-QS-SVM(rc′)DistancebetweenthenodesinSTA-QS-SVM(rc).Letn be the total number of measurements in time interval T and let n(Ea) be the number of events in a region R or R′. Then, n(Ea)=nμ, where μ is the fraction of events occurring in T. Also, let n(ESTA) and n(ETA) be the number of events correctly detected by STA-QS-SVM and TA-QS-SVM approaches, respectively. Then,
(8)DRSTA=nESTAnEa,DRTA=nETAnEa.
Substituting (8) in (6), we get
(9)nESTA-nETA<nϵμ.Proposition 1.
LetDRSTA and DRTA be the event detection rates for STA-QS-SVM and TA-QS-SVM approaches; then, DRSTA=p(ESTA∣Ea) and DRTA=p(ETA∣Ea), where p(ESTA∣Ea) and p(ETA∣Ea) are the probabilities of event detection by STA-QS-SVM and TA-QS-SVM approaches, respectively, given that an event has occurred.Proof.
Letpd be the probability of the detection of a sensor given as
(10)pd=e-βxifx≤rs,0else,
where x is the distance of a sensor from event/outlier location and β is a constant that depends on the physical characteristics of an environment. We make the following assumptions in order to prove this proposition.(1)
Letpe be the probability of the error of a sensor; then, pe≈0.(2)
An outlier (extreme condition) can occur uniformly in a region.(3)
An outlier occurring in a given region is independent of other regions.(4)
An event is reported if there is an outlier onk/2+1 sensors in the region.(5)
An event is within the sensing range of all the sensors in the region.(6)
The probability of detection of a sensor atx=rs, that is, pd(x=rs)≥1/2.(7)
The probability of detection of an event, given that assumption (6) is satisfied, is(11)pESTA∣Ea≥1-δSTA,pETA∣Ea≥1-δTA,whereδSTA and δTA are the SVM generalization errors for STA-QS-SVM and TA-QS-SVM approaches, respectively.We analyze a set of n measurements in a time interval T. Thus, each instant corresponds to the small interval τ=T/n. Let λ be the rate of arrival of an outlier in a region per τ. The rate of arrival of outliers can be modeled as a Poisson process with parameter λ. Assuming that λ≪1 and only one outlier arrives at an instant τ, the probability of the arrival of one outlier in an instant τ is
(12)p1,τ=λτe-λτ.
Further, we assume that an arriving outlier is equally likely to touch all the sensors. Thus, the probability that an outlier occurs and affects the sensor is
(13)po=λτe-λτk.
Thus, the probability of outlier detection at an instant τ, using (10) and (13), is given as
(14)pOd=λτe-λτe-βxk;
also,
(15)pOd=pOd∣Opo+pOd∣Ocpo′,
where p(Od∣O) is the probability of detection of an outlier given that an outlier occurs and p(Od∣Oc) is the probability of detection of an outlier given that an outlier does not occur. From the first assumption pe≈0, thus, p(Od∣Oc)=pe=0. Comparing (13), (14), and (15) we get
(16)pOd∣Oc=e-βx.
Again from assumption (1), as p(Od∣Oc)=pe=0, we need not consider the interarrival times of outlier in the outlier detection or event detection performance. Hence, the problem of comparing the event detection rates of both the techniques becomes independent of the interarrival times. Hence,
(17)pESTA∣Ea=∑j=k/2+1k‍∑l=1(kj)‍e-βxljj1-e-βxljk-j,pETA∣Ea=∑j=k/2+1k‍kje-βxjj1-e-βxjk-j.
Thus, using the assumptions (5) and (6) and the abovementioned facts, the detection rates DRSTA and DRTA are equal to the probabilities of the detection of an event given in which an event occurs, that is, p(ESTA∣Ea) and p(ETA∣Ea).Thus, (6) can be written as
(18)pESTA∣Ea-pETA∣Ea<ϵ.Using (17) in (18) we obtain
(19)∑j=k/2+1k‍∑l=1kj‍e-βxljj1-e-βxljk-j(20)∑j=k/2+1k‍∑l=1kj‍e-βxjlj1-e-βxjlk-j-∑j=k/2+1k‍kje-βxjj1-e-βxjk-j<ϵ.
The exact value of p(ESTA∣Ea) in (19) is complex to evaluate, since the value of xlj is different for different combinations of sensors. Hence, we perform an average case analysis for p(ESTA∣Ea). We find the expected value of distance, that is, xSTA, between the event and sensors, for the STA-QS-SVM approach. Let (ρ1,θ1) be the coordinates of the event in the region R, centered at the origin. Then, PDF of ρ1 and θ1 are
(21)fρ1ρ1=1rcfor0≤ρ1≤rc,0else,fθ1θ1=12πfor0≤θ1≤2π,0else.
Let (ρ2,θ2) be the coordinates of the sensors present at the boundary of region R:
(22)fρ2ρ2=k-1kforρ2=rc,1kforρ2=0,0else.
Thus, for STA-QS-SVM, the expected value of the distance of a sensor from the event location xSTA is given using the cosine law and Jensen’s inequality as
(23)Eρ12+ρ22-2ρ1ρ2cos⁡⁡θ1-θ2≥Eρ12+Eρ22-2Eρ1ρ2cos⁡⁡θ1-θ2.
Assuming that cos⁡(θ1-θ2) is independent of ρ1, we get
(24)xSTA=rc13+k-1k2.
For the TA-QS-SVM approach, we note that rc′ is the distance between the sensor nodes. Since the sensor nodes need not communicate with each other, in the worst case, a sensor node can detect an event at a distance of rc′/2. Assume that the event is equally likely to occur in the range of 0 to rc′/2. Thus, the expected distance of a sensor from event location (xTA)=rc′/4=(C·rc)/4. Since we are evaluating p(ESTA∣Ea) and p(ETA∣Ea) for the expected value of distances, that is, xSTA and xTA, (19) transforms to the following form:
(25)∑j=k/2+1k‍kje-βxSTAj1-e-βxSTAk-j×∑j=k/2+1k‍kje-βxTAj1-e-βxTAk-j<ϵ.
Further, we assume that the central sensor always detects the event
(26)∑j=k/2k-1‍k-1j×e-βjrc1/3+k-1/k21-e-βrc1/3+k-1/k2k-je-βjrc1/3+k-1/k21-e-βrc1/3+k-1/k2k-j-e-jβC·rc/41-e-βC·rc/4k-j<ϵ.Solving the above equation using Taylor expansion,(27)∑m=1∞‍-1m∑j=k/2k-1‍k-1j∑i=1m‍jm-ik-j-1ii!m-i!︸λmβm×rcm13+k-1k2m/2-C·rc4m<ϵ.Bounding the above summation by a finite number of terms, that is,l, we obtain the following expression for C:
(28)C=413+k-1k2l/2-ϵl.The above equation gives an expression of distance ratio(C). Thus, the events would be detected with approximately the same detection rates for both STA-QS-SVM and TA-QS-SVM approaches if rc′=C·rc. A plot of C for different values of k is shown in Figure 2. The figure shows that C increases with an increase in the corresponding value of k.Figure 2
Variation of distance ratio(C) with number of sensors (k).


### 3.1. Maximum Sensing Rangesrs for STA-QS-SVM and TA-QS-SVM (SensGru)

Letrs and rc be the sensing and communication ranges of each of the k sensors deployed in a region R consisting of a central sensor at a distance of rc from uniformly deployed sensors at the border of the region for the STA-QS-SVM approach. Then, the maximum value of rs required for event detection is 2rc.Proof.
Given that regionR consists of exactly k sensors, k-1 of which are deployed uniformly along the circumference of the region and are at a distance rc apart from the central sensor; event detection occurs when at least k/2+1 sensors detect it. In the worst case, an event occurring at the border of region R should be detected. Two cases arise.
Case
I (k/2+1 sensors detect the event). In this case, the k/2+1 nearest sensors detect the event. Thus, a sensor present at the distance 2rc1-cos⁡(k-1/2π/(k-1)) should be able to detect it. Moreover, from assumption (7) and (27) and using finite number of l terms to bound the summation, we have
(29)λ1βxSTA+λ2β2xSTA2+⋯+λlβlxSTAl≥1-δSTA.
Let κ be the real root of this equation; then, using the above relation between the minimum possible rs, k, and rc, we get rs≥κ21-cos⁡⁡((k-1)/2π/(k-1))/2β(1/3+((k-1)/k)2)l/2-ϵl. Hence,(30)rs≥max⁡rc,κ2β1/3+k-1/k2l/2-ϵl21-cos⁡k-1/2πk-1︸Ω.
Case II (all the sensors detect the event). In this case, a sensor present at the maximum distance, that is, 2rc, from the event must detect the event.
Hence, the range ofrs for event detection is
(31)Ω≤rs≤2rc.Proposition 2.
Letrs and rc be the sensing and communication ranges of each of the k sensors deployed in a region R′ at a central node for SensGru. Each node is at a distance of rc′ from nodes in the neighboring regions. Then, the maximum value of rs required for event detection is (C·rc)/2.Proof.
Given that the regionR′ consists of exactly k sensors at a central node and each node is at a distance of C·rc from other neighboring nodes, event detection occurs when at least k/2+1 sensors detect it. In the worst case, an event occurring at the border of the region R′ should be detected. Since the border of the region R′ is at the distance of C·rc/2=2rc(1/3+(k-1/k)2)l/2-ϵl from the nodes, the event at the border will be detected if all the sensors have
(32)rs=2rc13+k-1k2l/2-ϵl.A plot of maximumrs for various values of k and ϵ=0.001 for STA-QS-SVM and SensGru (TA-QS-SVM) approaches is shown in Figure 3. The figure indicates that the maximum value of rs required for SensGru increases with an increase in the number of sensors per subregion k. However, as the value of k increases, the increase in the maximum rs reduces.Figure 3
Variation of maximum sensing range with number of sensors(k).Proposition 3.
The optimal value ofk, that is, kopt, for event detection in STA-QS-SVM and SensGru is 7.Proof.
The optimal value ofk is defined as the value for which maximum reduction in computation complexity and sensor node density is attained in SensGru, given that the event detection performance with both schemes is approximately the same. The maximum reduction in computation complexity and cost is attained when the sensors deployed in both regions R and R′ have the same maximum sensing ranges rs (as shown in Figure 3). Thus, equating the maximum rs values for STA-QS-SVM and SensGru, we get
(33)2rc13+kopt-1kopt2l/2-ϵl=2rc,kopt=11-1+ϵ2/l-1/3.The above equation indicates that the optimal value ofk, that is, kopt, depends only on ϵ and l. Hence, as evident from the figures, the optimal value kopt=5.5. Thus, for experimental purposes, kopt=6 can be chosen. However, since we prove in the following that the detection probabilities for even number of sensors are less as compared to odd number of sensors, we choose kopt=7.


### 3.2. Worst Case Analysis

Proposition 4.
For the worst case analysis,(34)pESTA∣Eak=odd>pESTA∣Eak=even.Proof.
The worst case analysis is made assuming that the event is located at the boundary of regionR′ for the SensGru and in between the two sensors present along the boundary of R for the STA-QS-SVM approach. The worst case probabilities of event detection in regions R are greater for odd number of sensors as compared to the even number of sensors. When the number of sensors are even, one of the k sensors will always be located at maximum distance, that is, 2rc from the event location, whereas when the number of sensors is odd, no sensor is located at maximum distance from the event location; hence, the probability of detection increases. This is shown in Figures 4 and 5 for the STA-QS-SVM approach.Figure 4
Worst case probability of detection for STA-QS-SVM for even number of sensors(k).Figure 5
Worst case probability of detection for STA-QS-SVM for odd number of sensors(k).Proposition 5.
The worst case distance ratio (Cworst) is equal to 2.36.Proof.
The worst case distance ratioCworst was evaluated assuming that the event is located at the boundary of region R′ for SensGru and in between the two sensors present along the boundary of R for the STA-QS-SVM approach. The optimal value kopt was assumed for R and R′. The worst case distance ratio Cworst was found such that probabilities of detection p(ESTA∣Ea) and p(ETA∣Ea) differ by ϵ. p(ESTA∣Ea) and p(ETA∣Ea) were evaluated for various values of β. An example plot of worst case distance ratio for various values of β is shown in Figure 6. The figure shows that the worst case distance ratio Cworst does not vary significantly with β. The results shown in Figure 6 also prove that the worst case distance ratio is equal to 2.36. The value of Cworst=2.36 implies that, for the worst case scenario, where the event is located at the boundary of regions R and R′, distance between sensor nodes in R′ = 2.36 × (distance between sensor nodes in R). Thus, if this condition is satisfied, p(ESTA∣Ea) and p(ETA∣Ea) will differ by ϵ.Figure 6
Variation ofCworst with β.


## 3.1. Maximum Sensing Rangesrs for STA-QS-SVM and TA-QS-SVM (SensGru)

Letrs and rc be the sensing and communication ranges of each of the k sensors deployed in a region R consisting of a central sensor at a distance of rc from uniformly deployed sensors at the border of the region for the STA-QS-SVM approach. Then, the maximum value of rs required for event detection is 2rc.Proof.
Given that regionR consists of exactly k sensors, k-1 of which are deployed uniformly along the circumference of the region and are at a distance rc apart from the central sensor; event detection occurs when at least k/2+1 sensors detect it. In the worst case, an event occurring at the border of region R should be detected. Two cases arise.
Case
I (k/2+1 sensors detect the event). In this case, the k/2+1 nearest sensors detect the event. Thus, a sensor present at the distance 2rc1-cos⁡(k-1/2π/(k-1)) should be able to detect it. Moreover, from assumption (7) and (27) and using finite number of l terms to bound the summation, we have
(29)λ1βxSTA+λ2β2xSTA2+⋯+λlβlxSTAl≥1-δSTA.
Let κ be the real root of this equation; then, using the above relation between the minimum possible rs, k, and rc, we get rs≥κ21-cos⁡⁡((k-1)/2π/(k-1))/2β(1/3+((k-1)/k)2)l/2-ϵl. Hence,(30)rs≥max⁡rc,κ2β1/3+k-1/k2l/2-ϵl21-cos⁡k-1/2πk-1︸Ω.
Case II (all the sensors detect the event). In this case, a sensor present at the maximum distance, that is, 2rc, from the event must detect the event.
Hence, the range ofrs for event detection is
(31)Ω≤rs≤2rc.Proposition 2.
Letrs and rc be the sensing and communication ranges of each of the k sensors deployed in a region R′ at a central node for SensGru. Each node is at a distance of rc′ from nodes in the neighboring regions. Then, the maximum value of rs required for event detection is (C·rc)/2.Proof.
Given that the regionR′ consists of exactly k sensors at a central node and each node is at a distance of C·rc from other neighboring nodes, event detection occurs when at least k/2+1 sensors detect it. In the worst case, an event occurring at the border of the region R′ should be detected. Since the border of the region R′ is at the distance of C·rc/2=2rc(1/3+(k-1/k)2)l/2-ϵl from the nodes, the event at the border will be detected if all the sensors have
(32)rs=2rc13+k-1k2l/2-ϵl.A plot of maximumrs for various values of k and ϵ=0.001 for STA-QS-SVM and SensGru (TA-QS-SVM) approaches is shown in Figure 3. The figure indicates that the maximum value of rs required for SensGru increases with an increase in the number of sensors per subregion k. However, as the value of k increases, the increase in the maximum rs reduces.Figure 3
Variation of maximum sensing range with number of sensors(k).Proposition 3.
The optimal value ofk, that is, kopt, for event detection in STA-QS-SVM and SensGru is 7.Proof.
The optimal value ofk is defined as the value for which maximum reduction in computation complexity and sensor node density is attained in SensGru, given that the event detection performance with both schemes is approximately the same. The maximum reduction in computation complexity and cost is attained when the sensors deployed in both regions R and R′ have the same maximum sensing ranges rs (as shown in Figure 3). Thus, equating the maximum rs values for STA-QS-SVM and SensGru, we get
(33)2rc13+kopt-1kopt2l/2-ϵl=2rc,kopt=11-1+ϵ2/l-1/3.The above equation indicates that the optimal value ofk, that is, kopt, depends only on ϵ and l. Hence, as evident from the figures, the optimal value kopt=5.5. Thus, for experimental purposes, kopt=6 can be chosen. However, since we prove in the following that the detection probabilities for even number of sensors are less as compared to odd number of sensors, we choose kopt=7.


## 3.2. Worst Case Analysis

Proposition 4.
For the worst case analysis,(34)pESTA∣Eak=odd>pESTA∣Eak=even.Proof.
The worst case analysis is made assuming that the event is located at the boundary of regionR′ for the SensGru and in between the two sensors present along the boundary of R for the STA-QS-SVM approach. The worst case probabilities of event detection in regions R are greater for odd number of sensors as compared to the even number of sensors. When the number of sensors are even, one of the k sensors will always be located at maximum distance, that is, 2rc from the event location, whereas when the number of sensors is odd, no sensor is located at maximum distance from the event location; hence, the probability of detection increases. This is shown in Figures 4 and 5 for the STA-QS-SVM approach.Figure 4
Worst case probability of detection for STA-QS-SVM for even number of sensors(k).Figure 5
Worst case probability of detection for STA-QS-SVM for odd number of sensors(k).Proposition 5.
The worst case distance ratio (Cworst) is equal to 2.36.Proof.
The worst case distance ratioCworst was evaluated assuming that the event is located at the boundary of region R′ for SensGru and in between the two sensors present along the boundary of R for the STA-QS-SVM approach. The optimal value kopt was assumed for R and R′. The worst case distance ratio Cworst was found such that probabilities of detection p(ESTA∣Ea) and p(ETA∣Ea) differ by ϵ. p(ESTA∣Ea) and p(ETA∣Ea) were evaluated for various values of β. An example plot of worst case distance ratio for various values of β is shown in Figure 6. The figure shows that the worst case distance ratio Cworst does not vary significantly with β. The results shown in Figure 6 also prove that the worst case distance ratio is equal to 2.36. The value of Cworst=2.36 implies that, for the worst case scenario, where the event is located at the boundary of regions R and R′, distance between sensor nodes in R′ = 2.36 × (distance between sensor nodes in R). Thus, if this condition is satisfied, p(ESTA∣Ea) and p(ETA∣Ea) will differ by ϵ.Figure 6
Variation ofCworst with β.


## 4. Complexity Analysis

Letn be the total number of data measurements at a node and let d be the number of data attributes. Let k be the number of sensors in the region R for STA-QS-SVM approach and region R′ for SensGru approach.


### 4.1. Computation Complexity

#### 4.1.1. ST-QS-SVM

ST-QS-SVM requires the computation ofn×n kernel matrix K which poses a complexity of O(n2). The radius is computed at each node via a linear optimization problem. Hence, the radius computation poses a complexity of O(n). Each node then broadcasts its radius information to the central node. On the receipt of radius information, the central node computes the global radius in O(k) complexity (k being the number of nodes). Hence, the total computation complexity is O(n2).


#### 4.1.2. STA-QS-SVM

Online STA-QS-SVM requires the computation ofn×n kernel matrix K and d×d matrix K* which poses a complexity of O(n2+nd2). The radii (temporal and attribute) are computed at each node via a linear optimization problem. Hence, the radius computation poses a complexity of O(n+nd). Each node then broadcasts its radius information to the central node. On the receipt of radius information, the central node computes the global radius in O(k) complexity (k being the number of nodes). Hence, the total computation complexity is O(n2+nd2). In offline STA-QS-SVM, the matrix K* is computed at the beginning only; hence, the computation complexity is O(n2).


#### 4.1.3. SensGru (TA-QS-SVM)

SensGru requires the computation ofn×n kernel matrix K and d×d matrix K* which poses a complexity of O(n2+nd2). The radii (temporal and attribute) are computed at each sensor via a linear optimization problem. Hence, the radius computation poses a complexity of O(n+nd). Each sensor then sends its radius information to the central sensor. On the receipt of radius information, the central sensor computes the global radius in O(k) complexity (k being the number of nodes). Hence, the total computation complexity is O(n2+nd2). Note that SensGru can have online and offline versions.


### 4.2. Communication Complexity

#### 4.2.1. ST-QS-SVM

ST-QS-SVM requires the broadcast of temporal radius to the central node which poses a communication complexity ofO(n).


#### 4.2.2. STA-QS-SVM

STA-QS-SVM requires the broadcast of the temporal and the attribute radii to the central node which poses a communication complexity ofO(n+d).


#### 4.2.3. TA-QS-SVM

TA-QS-SVM poses no communication complexity as it does not require the broadcast of radii to the central sensor.


### 4.3. Sensor Node Density

Consider regionsA (for STA-QS-SVM) and A′ (for SensGru) having the same physical characteristics (the same values of β). Assume that region A=b2·R and region A′=c2·R′. Thus, A and A′ (of the same area) contain b2 and c2 number of closely packed subregions R and R′. Further, we assume that the subregions R and R′ are hexagon shaped, since they can then be closely packed to form A and A′. Let each of the subregions R and R′ have radii rc and rc′; then, the radii of A and A′ are b·rc and c·rc′/2 approximately. Further, assume that each of the subregions R in A has k number of sensors, of which one is the central and k-1 are located uniformly along the boundary of R. Each of the subregions R will then have some sensors in common with the neighboring subregions. Also let the subregions R′ in A′ have a single node located at the center and have k sensors on it. Thus, the number of sensors in region A will be given as
(35)k+∑i=1b/2‍k2i2+7i2-3=kb396+kb232-71kb48.Since we want to evaluate the number of sensors for equal areas ofA and A′, equating the two areas and using (28), we get the number of sensors in A′:
(36)NA′=b21/3+k-1/k2l/2-ϵl2k.
Figure 7 shows the number of subregions required for the same area of A and A′. The figure clearly shows that the number of subregions R′ in A′ is less as compared to the number of regions R in A. Figure 8 shows the variation of total number of sensors in regions A and A′ with the parameter b of the regions. Clearly the number of sensors for region A is much greater as compared to the number of sensors for region A′ for larger values of b. The results also indicate that with an increase in the parameter b, the increase in N(A) will be much greater as compared to N(A′). Similar results are shown in Figure 9, which gives the total number of sensors in regions A and A′ for different values of k. The number of sensors N(A) and N(A′) increases linearly with an increase in k. Thus, the sensor density required in TA-QS-SVM approach is significantly less as compared to that required for the STA-QS-SVM approach.Figure 7
Number of subregions inA and A′ for a fixed area.Figure 8
Variation of the total number of sensors inA and A′ with the parameter b.Figure 9
Variation of the total number of sensors inA and A′ with the number of sensors per subregion k.


## 4.1. Computation Complexity

### 4.1.1. ST-QS-SVM

ST-QS-SVM requires the computation ofn×n kernel matrix K which poses a complexity of O(n2). The radius is computed at each node via a linear optimization problem. Hence, the radius computation poses a complexity of O(n). Each node then broadcasts its radius information to the central node. On the receipt of radius information, the central node computes the global radius in O(k) complexity (k being the number of nodes). Hence, the total computation complexity is O(n2).


### 4.1.2. STA-QS-SVM

Online STA-QS-SVM requires the computation ofn×n kernel matrix K and d×d matrix K* which poses a complexity of O(n2+nd2). The radii (temporal and attribute) are computed at each node via a linear optimization problem. Hence, the radius computation poses a complexity of O(n+nd). Each node then broadcasts its radius information to the central node. On the receipt of radius information, the central node computes the global radius in O(k) complexity (k being the number of nodes). Hence, the total computation complexity is O(n2+nd2). In offline STA-QS-SVM, the matrix K* is computed at the beginning only; hence, the computation complexity is O(n2).


### 4.1.3. SensGru (TA-QS-SVM)

SensGru requires the computation ofn×n kernel matrix K and d×d matrix K* which poses a complexity of O(n2+nd2). The radii (temporal and attribute) are computed at each sensor via a linear optimization problem. Hence, the radius computation poses a complexity of O(n+nd). Each sensor then sends its radius information to the central sensor. On the receipt of radius information, the central sensor computes the global radius in O(k) complexity (k being the number of nodes). Hence, the total computation complexity is O(n2+nd2). Note that SensGru can have online and offline versions.


## 4.1.1. ST-QS-SVM

ST-QS-SVM requires the computation ofn×n kernel matrix K which poses a complexity of O(n2). The radius is computed at each node via a linear optimization problem. Hence, the radius computation poses a complexity of O(n). Each node then broadcasts its radius information to the central node. On the receipt of radius information, the central node computes the global radius in O(k) complexity (k being the number of nodes). Hence, the total computation complexity is O(n2).


## 4.1.2. STA-QS-SVM

Online STA-QS-SVM requires the computation ofn×n kernel matrix K and d×d matrix K* which poses a complexity of O(n2+nd2). The radii (temporal and attribute) are computed at each node via a linear optimization problem. Hence, the radius computation poses a complexity of O(n+nd). Each node then broadcasts its radius information to the central node. On the receipt of radius information, the central node computes the global radius in O(k) complexity (k being the number of nodes). Hence, the total computation complexity is O(n2+nd2). In offline STA-QS-SVM, the matrix K* is computed at the beginning only; hence, the computation complexity is O(n2).


## 4.1.3. SensGru (TA-QS-SVM)

SensGru requires the computation ofn×n kernel matrix K and d×d matrix K* which poses a complexity of O(n2+nd2). The radii (temporal and attribute) are computed at each sensor via a linear optimization problem. Hence, the radius computation poses a complexity of O(n+nd). Each sensor then sends its radius information to the central sensor. On the receipt of radius information, the central sensor computes the global radius in O(k) complexity (k being the number of nodes). Hence, the total computation complexity is O(n2+nd2). Note that SensGru can have online and offline versions.


## 4.2. Communication Complexity

### 4.2.1. ST-QS-SVM

ST-QS-SVM requires the broadcast of temporal radius to the central node which poses a communication complexity ofO(n).


### 4.2.2. STA-QS-SVM

STA-QS-SVM requires the broadcast of the temporal and the attribute radii to the central node which poses a communication complexity ofO(n+d).


### 4.2.3. TA-QS-SVM

TA-QS-SVM poses no communication complexity as it does not require the broadcast of radii to the central sensor.


## 4.2.1. ST-QS-SVM

ST-QS-SVM requires the broadcast of temporal radius to the central node which poses a communication complexity ofO(n).


## 4.2.2. STA-QS-SVM

STA-QS-SVM requires the broadcast of the temporal and the attribute radii to the central node which poses a communication complexity ofO(n+d).


## 4.2.3. TA-QS-SVM

TA-QS-SVM poses no communication complexity as it does not require the broadcast of radii to the central sensor.


## 4.3. Sensor Node Density

Consider regionsA (for STA-QS-SVM) and A′ (for SensGru) having the same physical characteristics (the same values of β). Assume that region A=b2·R and region A′=c2·R′. Thus, A and A′ (of the same area) contain b2 and c2 number of closely packed subregions R and R′. Further, we assume that the subregions R and R′ are hexagon shaped, since they can then be closely packed to form A and A′. Let each of the subregions R and R′ have radii rc and rc′; then, the radii of A and A′ are b·rc and c·rc′/2 approximately. Further, assume that each of the subregions R in A has k number of sensors, of which one is the central and k-1 are located uniformly along the boundary of R. Each of the subregions R will then have some sensors in common with the neighboring subregions. Also let the subregions R′ in A′ have a single node located at the center and have k sensors on it. Thus, the number of sensors in region A will be given as
(35)k+∑i=1b/2‍k2i2+7i2-3=kb396+kb232-71kb48.Since we want to evaluate the number of sensors for equal areas ofA and A′, equating the two areas and using (28), we get the number of sensors in A′:
(36)NA′=b21/3+k-1/k2l/2-ϵl2k.
Figure 7 shows the number of subregions required for the same area of A and A′. The figure clearly shows that the number of subregions R′ in A′ is less as compared to the number of regions R in A. Figure 8 shows the variation of total number of sensors in regions A and A′ with the parameter b of the regions. Clearly the number of sensors for region A is much greater as compared to the number of sensors for region A′ for larger values of b. The results also indicate that with an increase in the parameter b, the increase in N(A) will be much greater as compared to N(A′). Similar results are shown in Figure 9, which gives the total number of sensors in regions A and A′ for different values of k. The number of sensors N(A) and N(A′) increases linearly with an increase in k. Thus, the sensor density required in TA-QS-SVM approach is significantly less as compared to that required for the STA-QS-SVM approach.Figure 7
Number of subregions inA and A′ for a fixed area.Figure 8
Variation of the total number of sensors inA and A′ with the parameter b.Figure 9
Variation of the total number of sensors inA and A′ with the number of sensors per subregion k.


## 5. Simulations and Results

Experimental evaluation was performed on matlab with a synthetic data set that consists of a mixture of Type-1, Type-2, Type-3, and Type-4 outliers. Type-1 and Type-2 outliers are isolated errors which may occur due to noise at random time instants in the data set, whereas Type-3 and Type-4 outliers consist of sequences of Type-1 and Type-2 outliers [10, 28–30]. The data set consists of a mixture of various Gaussian distributions, with mean randomly selected from (0.03–0.6) and standard deviation 0.03, along each of the attributes. The number of Gaussian distributions depends on the number of attributes. The testing data set consisted of 2500 measurements. The training window n was kept equal to 250. Performance evaluation was done for data vectors with 2 to 15 attributes (A), with 5% of uniformly distributed outliers in the range [0.65,1] along each of the attributes. RBF Kernel function is used to generate the results with sigma 0.2, because it has infinite VC dimension. The simulation environment assumed a central node surrounded by 6–9 (N or k) spatially correlated neighboring nodes. The distance between the nodes in STA-QS-SVM is kept equal to the maximum rs as given in (32). Further, all the assumptions have been taken into account as described in the above sections.The comparison of event detection rates for STA-QS-SVM and SensGru is presented in Figures10 and 11. Assuming that the probability of all the sensors being faulty at the same time instant at a node Si is negligible and that the spatial correlations of erroneous measurements indicate an event, our technique identifies a measurement as an event if it has temporal-attribute deviation with itself and a strong correlation with a majority of sensors deployed at the node.Figure 10
Event detection rates for STA-QS-SVM and TA-QS-SVM (nodes = 7).Figure 11
Event detection rates for STA-QS-SVM and TA-QS-SVM (nodes = 10).


### 5.1. Discussion on Results

Figures10 and 11 show that SensGru always gives equal or better performance than STA-QS-SVM at a small cost of slightly increasing the sensing range rs and increasing the number of sensors per node. Communication overhead gets totally eliminated and node density gets greatly reduced. Since the spatial correlations are only used to determine an event and temporal-attribute correlations determine outliers, TA-QS-SVM based SensGru exploits the temporal and attribute correlations to identify outliers and invoke a consensus of all the k sensor arrays to identify an event, without using spatial correlations of neighboring nodes. The consensus of k sensor arrays at a node Si is thus equivalent to the spatial information of k neighboring nodes of Si in a region and thus makes the outlier and event detection process free of communication cost and highly energy efficient. Since increasing the sensing range is cost effective as compared to the communication cost, SensGru is much more communicationally and computationally effective as compared to STA-QS-SVM approach. However, there is a trade-off associated with the increase in the sensing range and detection probabilities of event in STA-QS-SVM and TA-QS-SVM based SensGru. The trade-off can be explained in terms of Figures 4, 5, and 3. The figures show that on choosing the optimal value of k=kopt=7 the sensing range for STA-QS-SVM and SensGru will be rs. However, the detection probabilities for both the approaches (Figures 4 and 5) are less than ideal 100%. If we increase the number of sensors k, the sensing range of sensors for STA-QS-SVM can be maintained equal to rs, and an increase in p(ESTA∣Ea) is obtained. However, in order to obtain the corresponding increase in p(ETA∣Ea), an increase in the sensing range of sensor is required. However, reduction in sensor node density outweighs this increase in the sensing range and the overall computation cost is reduced. A more involved reader might come across the thought that using the optimal value of k=kopt for both STA-QS-SVM and SensGru, the sensor node density will become the same. However, as evident from (28), when the sensing ranges are the same, the distance between the nodes in SensGru will still be twice that of the distance between the nodes in STA-QS-SVM. Hence, the sensor density will still increase quadratically with b for SensGru and cubically with b for STA-QS-SVM.


## 5.1. Discussion on Results

Figures10 and 11 show that SensGru always gives equal or better performance than STA-QS-SVM at a small cost of slightly increasing the sensing range rs and increasing the number of sensors per node. Communication overhead gets totally eliminated and node density gets greatly reduced. Since the spatial correlations are only used to determine an event and temporal-attribute correlations determine outliers, TA-QS-SVM based SensGru exploits the temporal and attribute correlations to identify outliers and invoke a consensus of all the k sensor arrays to identify an event, without using spatial correlations of neighboring nodes. The consensus of k sensor arrays at a node Si is thus equivalent to the spatial information of k neighboring nodes of Si in a region and thus makes the outlier and event detection process free of communication cost and highly energy efficient. Since increasing the sensing range is cost effective as compared to the communication cost, SensGru is much more communicationally and computationally effective as compared to STA-QS-SVM approach. However, there is a trade-off associated with the increase in the sensing range and detection probabilities of event in STA-QS-SVM and TA-QS-SVM based SensGru. The trade-off can be explained in terms of Figures 4, 5, and 3. The figures show that on choosing the optimal value of k=kopt=7 the sensing range for STA-QS-SVM and SensGru will be rs. However, the detection probabilities for both the approaches (Figures 4 and 5) are less than ideal 100%. If we increase the number of sensors k, the sensing range of sensors for STA-QS-SVM can be maintained equal to rs, and an increase in p(ESTA∣Ea) is obtained. However, in order to obtain the corresponding increase in p(ETA∣Ea), an increase in the sensing range of sensor is required. However, reduction in sensor node density outweighs this increase in the sensing range and the overall computation cost is reduced. A more involved reader might come across the thought that using the optimal value of k=kopt for both STA-QS-SVM and SensGru, the sensor node density will become the same. However, as evident from (28), when the sensing ranges are the same, the distance between the nodes in SensGru will still be twice that of the distance between the nodes in STA-QS-SVM. Hence, the sensor density will still increase quadratically with b for SensGru and cubically with b for STA-QS-SVM.


## 6. Conclusion

This paper proposes an energy efficient event detection and identification approach for cyber physical systems. A thorough analysis on the impact of grouping multiple sensors on a single node has been conducted where each node runs an event detection and identification algorithm based on quarter-sphere SVM formulation. Huge power savings are guaranteed in the proposed scheme as it gets rid of the communication overhead before declaring an event with a node density reduced by 75%. Furthermore, all these gains are achieved while maintaining the same performance as power inefficient STA-QS-SVM formulation.



---

*Source: 259508-2014-11-04.xml*