An Energy-Efficient Outlier Detection Based on Data Clustering in WSNs

Abstract

Sensor nodes in wireless sensor networks are prone to malfunction because they are exposed to the nearby environment directly. Consequently, wrong sensor readings occurred from sensor nodes and these readings are called an outlier. Commonly, since an outlier deviates from normal sensor readings and it can bring about some problems, various techniques to detect the outliers have been proposed. In this paper, we propose an efficient outlier detection technique based on data clustering. In order to decide the width of the cluster that consists of the sensor readings, we applied the Pigeonhole Principle and then detected the outliers based on clusters. In experiments, we demonstrate the efficiency of our proposed technique compared to other outlier detection techniques.

1. Introduction

Recently, since development of the integrated circuit, the size of the sensor is gradually reduced and various sensors are built in the sensor node in a wireless sensor network (WSN). Sensor nodes detect the various and huge information (e.g., temperature, humidity, and light) around their environments and they communicate to the base station and others using radio transmission. Accordingly, WSNs are used in various applications such as environment and habitat monitoring [1, 2], combat field surveillance [3], security [4], or health care [5] applications.

Commonly, sensor nodes are severely constrained in terms of the computation power, communication bandwidth, and battery power. Among these limitations, the power is of utmost importance, since replacing the battery of sensor nodes is too either expensive or impossible [6, 7]. Thus, the energy preservation is a major research issue since it directly impacts the life time of the network. Recently, much research has shown that the radio communication is more expensive than the computation or the sensing. Thus, many techniques [8–13] have been proposed in order to reduce the communication overhead.

Particularly, since sensor nodes are placed outdoor for the applications such as the disaster monitoring [14] and habitat monitoring, the sensor nodes can be malfunctioned or the sensor readings may be incorrect due to external impact such as the severe external environments [15]. In addition, due to sudden changes in external environments, some sensor readings may deviate significantly from the normal sensor readings. These abnormal sensor readings are called the outliers. For example, assume that several sensor nodes are deployed in a mountain to monitor forest fires. When an outlier value is detected and sent to a forest guard, the forest guard can identify the actual forest fires or he/she can initialize the sensor node if the outlier is generated by the malfunctioned sensor. Thus, the outlier detection is a quite important task to detect an event or to maintain sensor networks harmoniously.

In this paper, we focus on an energy-efficient outlier detection technique in WSNs based on data clustering. To construct data clusters, we use the Pigeonhole Principle. By applying cluster width, called the permission range, obtained by the Pigeonhole Principle, we partition the data space into several clusters. However, if we partition the data space evenly, some sensor readings are identified as outliers although similar sensor readings of them are detected by sensor nodes. Thus, we partition the domain of data unevenly based on the location of sensor readings. Then, we identify the outliers according to the user-defined threshold θ which is related to the number of sensor readings in a cluster.

The remainder of the paper is organized as follows. Section 2 discusses related work. In Section 3, we present the background of our work. Section 4 introduces the proposed outlier detection technique in WSNs. Section 5 presents an empirical evaluation. Section 6 summarizes the paper.

2. Related Work

In WSNs, a lot of outlier detection techniques have been proposed. In [16], an outlier detection technique was proposed to collect the outliers with respect to the neighbor sensor nodes. Each sensor node calculates the median of the sensor readings received from the neighbors and its readings. Each sensor node computes the mean μ and the standard deviation σ of the differences between its sensor readings and the calculated median. If the standardized value $(=(v-\mu )/\sigma )$ of a sensor reading v is greater than or equal to the user-defined threshold, it is regarded as an outlier.

Palpanas et al. proposed an outlier detection technique based on the the Epanechnikov kernel function [17]. Given a value v, each sensor node estimates the number of values around v using the kernel function. If the number of values around value v is less than a user-defined threshold p, a value v is regarded as an outlier. However, to make the kernel function, each sensor node transmits the required information to the base station along the routing path. Thus, it wastes a lot of energy.

In [18], an outlier detection technique based on data clustering, called DC, was proposed. Given a user-defined threshold ε, if the distance between any two sensor readings is less than ε, they become a cluster. When the distance between a pair of cluster centers is less than ε, they are merged. The intercluster distance (ICD) of a cluster to k-nearest clusters is computed to detect the outlier clusters. When ICD of a cluster is quite different from the mean of ICDs, it is regarded as an outlier cluster. Then, the information of outlier clusters is broadcasted into WSNs. Thus, it consumes much energy.

In [19], an outlier detection technique based on an ellipsoid was proposed. Each sensor node constructs an ellipsoid boundary of sensor readings using the mean and the covariance of sensor readings and transmits its ellipsoid boundary to the base station. The base station merges all received ellipsoids, computes the global ellipsoid boundary, and broadcasts the global ellipsoid to all sensor nodes. Then, with respect to the global ellipsoid boundary, each sensor node identifies the outliers among its sensor readings.

Recently, an outlier detection technique based on the distance between sensor readings and the estimation deviation was proposed [20]. Each sensor node computes the expected deviation and the average distance between pairs of sensor readings detected within recent time interval. If the average distance is greater than the expected deviation, the sensor reading at the current time becomes an outlier. However, when the expectation model is frequently updated, the communication overhead increases.

3. Preliminary

In this section, we present the basic model of sensor networks briefly.

3.1. Sensor Networks

We consider a sensor network consisting of n stationary sensor nodes $\{S_{\mathrm{1}},S_{\mathrm{2}},...,S_n\}$ deployed in a field of interest and the powered base station serving as an access point for users to pose ad hoc queries. We use a routing tree [9] which is frequently used as a primitive to collect sensor nodes. Two nodes capable of bidirectional wireless communication directly are referred to as the neighbors for each other. Each sensor node can broadcast a message to all of its neighbors (or from a parent to its child nodes) at a time. A simple sensor network using a tree routing is shown in Figure 1. In Figure 1, $S_{\mathrm{1}}$ to $S_{\mathrm{3}}$ are the intermediate sensor nodes that have the child sensor nodes, and $S_{\mathrm{4}}$ to $S_{\mathrm{9}}$ are the leaf sensor nodes that have no child node.

Figure 1

A simple sensor network.

Each sensor node generates its readings periodically. A sampling period is known as an epoch [21]. To agree on a global time base that allows sensor nodes to start and finish each epoch simultaneously, each sensor node executes the SMACS protocol [22] or a global time synchronization protocol [23]. Based on global time synchronized, nodes sleep for a certain period of time in each epoch to minimize energy consumption and each sensor node awakes to sample and receive results when its neighbors try to propagate a message.

4. Outlier Detection Based on Clustering

In this section, we present our proposed outlier detection technique which is based on data clustering in WSNs. In addition, we introduce an efficient data transmission scheme for our outlier detection technique.

4.1. Clustering Technique

Generally, in the outlier detection techniques based on data clustering, the width of clusters is the most important, since the number of sensor readings in each cluster is affected by the width of clusters. If the width of clusters is too large, all sensor readings may belong to a single cluster. Otherwise, each cluster may have only a single sensor reading. Thus, the outliers cannot be identified in these cases.

To solve the above problem, in this paper, we applied the Pigeonhole Principle to determine the width of clusters. We regard that pigeonholes and pigeons are the domain of sensor readings and the sensor readings, respectively. Thus, when we partition this domain into x number of subdomains, where x is less than the number of sensor readings, at least one subdomain contains more than two sensor readings.

Given a set of sensor readings $R=\{r_{\mathrm{1}},r_{\mathrm{2}},\dots ,r_n\}\hspace{0.17em}\hspace{0.17em}(|R|=n)$ , we can acquire the domain of R as [ $\text{MAX}(R),\text{MIN}(R)$ ]. Then, we obtain the permission range ( $\text{PR}$ ) as follows:

$$\begin{array}{cc}& \text{PR}=\left(\frac{\text{MAX}\left(R\right)-\text{MIN}\left(R\right)}{n-\mathrm{1}}\right).\end{array}$$

(1)

We use PR as the width of clusters and identify the outliers. For instance, given a set of sensor readings R shown in Figure 2, PR of R is obtained as $\mathrm{1.7}=(\text{MAX}(R)-\text{MIN}(R))/(n-\mathrm{1})=(\mathrm{19}-\mathrm{2})/(\mathrm{11}-\mathrm{1})$ . If the number of sensor readings in a cluster is less than or equal to the user-defined threshold θ, the cluster is the outlier cluster and the sensor readings in the outlier clusters are considered as the outliers.

Figure 2

Equipartitioning based on permission range.

In Figure 2, the clusters represented by dotted lines are presented when we partition the domain of   R evenly. Assume that the user-defined threshold θ is $\mathrm{1}$ . In Figure 2, $C_{\mathrm{2}}$ , $C_{\mathrm{4}}$ , and $C_{\mathrm{8}}$ are the outlier clusters (denoted by ellipses) and the sensor readings in each outlier cluster are regarded as the outliers. Although a sensor reading $r_{\mathrm{4}}$ in the cluster $C_{\mathrm{4}}$ is definitely an outlier, since a sensor reading which is similar to $r_{\mathrm{4}}$ does not exist, the sensor readings $r_{\mathrm{3}}$ and $r_{\mathrm{7}}$ are not the outliers since there are $r_{\mathrm{2}}$ and $r_{\mathrm{8}}$ which are similar to $r_{\mathrm{3}}$ and $r_{\mathrm{7}}$ , respectively. In other words, although the difference between a pair of sensor readings is less than the differences of the others, these sensor readings may belong to separated clusters if we partition the domain of R evenly.

To solve this drawback, we propose the nonequipartitioning based on the permission range (PR). In the nonequipartitioning, a set of clusters is constructed with respect to Definition 1.

Definition 1.

If the difference between a pair of sensor readings $r_i$ and $r_j$ in R is less than or equal to the permission range PR obtained by (1), we say $r_i$ is close to $r_j$ .

In our proposed technique, if $r_i$ and $r_j$ are close to each other, a single cluster contains $r_i$ and $r_j$ . For instance, as shown in Figure 3, since the difference between sensor readings $r_{\mathrm{1}}$ and $r_{\mathrm{2}}$ is close, a cluster $C_{\mathrm{1}}$ for them is constructed. And then, a sensor reading $r_{\mathrm{3}}$ is inserted into $C_{\mathrm{1}}$ , since the difference between $r_{\mathrm{2}}$ and $r_{\mathrm{3}}$ is less than PR. But $r_{\mathrm{4}}$ is not inserted into $C_{\mathrm{1}}$ . The result of nonequipartitioning is presented in Figure 3. Each cluster consists of   $C_{\mathrm{1}}=\{r_{\mathrm{1}},r_{\mathrm{2}},r_{\mathrm{3}}\}$ , $C_{\mathrm{2}}=\{r_{\mathrm{4}}\}$ , $C_{\mathrm{3}}=\{r_{\mathrm{5}},r_{\mathrm{6}}\}$ , and $C_{\mathrm{4}}=\{r_{\mathrm{7}},r_{\mathrm{8}},r_{\mathrm{9}},r_{\mathrm{10}},r_{\mathrm{11}}\}$ , respectively. Consequently, when a user-defined threshold θ is 1, a cluster $C_{\mathrm{2}}$ is an outlier cluster and a sensor reading $r_{\mathrm{4}}$ in $C_{\mathrm{2}}$ is an outlier.

Figure 3

Nonequipartitioning based on permission range.

4.2. Clustering Scheme for WSNs

If each sensor node transmits its readings to the base station blindly at each epoch and the base station computes the outliers, each sensor node consumes much energy. In this section, we present an efficient data transmission scheme for our outlier detection algorithm. We assume that all sensor nodes take sensor readings periodically and keep these readings into their local storage for a time window w. Note that when w is 1, each sensor node transmits data to the base station at each epoch.

At first, according to the Definition 1, each sensor node constructs clusters using its sensor readings detected within w. If the number of sensor readings in a cluster is greater than a user-defined threshold θ, all sensor readings in this cluster cannot be the outliers (i.e., nonoutlier cluster (NOC)). Otherwise, all sensor readings in a cluster may be the outliers, and then we call such clusters the outlier candidate clusters (OCCs).

Along the routing path to the base station, each sensor node transmits NOCs and OCCs. For NOCs, cluster ranges (CRs) are transmitted only where CR consists of minimum and maximum values of sensor readings in a NOC. In contrast, for OCCs, the sensor readings in OCC are transmitted to the parent node.

When a parent node p received CRs of NOCs and OCCs from its child nodes, p attempts to merge them with its clusters. To merge the clusters, we use the following definition.

Definition 2.

Given two cluster ranges ${\text{CR}}_i=[{\min }_i,{\max }_i]$ and ${\text{CR}}_j=[{\min }_j,{\max }_j]$ , where $({\min }_i<{\min }_j)$ , if ${\min }_j-{\max }_i\le \text{PR}$ , we say ${\text{CR}}_i$ and ${\text{CR}}_j$ overlap within $\text{PR}$ .

If a pair of cluster ranges overlap within PR, there are at least two sensor readings which are close and contained in different clusters. Thus, if two cluster ranges ${\text{CR}}_i$ (= $[{\min }_i,{\max }_i]$ ) and $\text{C}{\text{R}}_j$ (= $[{\min }_j,{\max }_j]$ ) of clusters $C_i$ and $C_j$ overlap within the permission range $\text{PR}$ , two clusters $C_i$ and $C_j$ are merged into a new cluster whose $\text{CR}$ is $[\text{MIN}(\{{\min }_i,{\min }_j\}),\text{MAX}(\{{\max }_i,{\max }_j\})]$ .

Note that, when two clusters are merged into a new cluster where at least one of them is a NOC, the merged cluster cannot be an OCC, since the number of sensor readings in a NOC is already greater than θ. Thus, when a sensor node transmits a NOC, we do not need to transmit all sensor readings in the NOC and it only needs the cluster range CR of the NOC. Thus, each sensor node reduces the energy consumption when it transmits the NOCs since the volume of the transmitted data from each sensor decreases.

In contrast, when two OCCs are merged into a new cluster, we check whether the number of sensor reading in the new cluster is greater than θ or not. Since each sensor node sends all sensor readings in each OCC, we can easily count the number of sensor readings in the new cluster.

Along the routing path from each sensor node to the base station, CRs of NOCs and OCCs are merged and transmitted gradually. Finally, the base station can determine the outliers among the received OCCs. Recall that the cluster ranges (CRs) rather than all senor readings in NOCs are transmitted along the routing paths. Thus, we can reduce the energy consumption of each sensor node.

For example, given a WSN with 11 sensor nodes in Figure 4 where the user-defined threshold θ is 1 and the domain of a set of sensor readings is $[\mathrm{2,19}]$ , each sensor node constructs the clusters using its sensor readings. Then, a cluster of each sensor node becomes the outlier candidate cluster (OCC), since threshold θ is $\mathrm{1}$ . As shown in Figure 5, the leaf nodes (i.e., $S_{\mathrm{8}}:S_{\mathrm{11}}$ ) transmit their clusters to their parents, respectively. In Figure 5, $S_{\mathrm{4}}$ merges its OCCs and the received OCCs coming from $S_{\mathrm{8}}$ and $S_{\mathrm{9}}$ based on Definition 2, and then $S_{\mathrm{4}}$ obtains a ${\text{NOC}}_{\mathrm{1}}$ : $[\mathrm{15,17}]$ . Similarly, $S_{\mathrm{6}}$ obtains the OCCs (i.e., ${\text{OCC}}_{\mathrm{1}}$ : $[3]$ , ${\text{OCC}}_{\mathrm{2}}$ : $[8]$ , and ${\text{OCC}}_{\mathrm{3}}$ : $[18]$ ).

Figure 4

Acquisition sensor readings.

Figure 5

Clustering in $S_{\mathrm{4}}$ and $S_{\mathrm{6}}$ .

In Figure 6, $S_{\mathrm{2}}$ receives the NOCs and OCCs from its child nodes ( $S_{\mathrm{4}}$ , $S_{\mathrm{5}}$ , and $S_{\mathrm{6}}$ ), and then $S_{\mathrm{2}}$ merges the received clusters. Since the cluster range of $\text{OC}{\text{C}}_{\mathrm{1}}$ coming from $S_{\mathrm{6}}$ overlaps the sensor readings of $S_{\mathrm{2}}$ and $S_{\mathrm{5}}$ within $\text{PR}$ , $S_{\mathrm{2}}$ generates a new cluster $\text{NO}{\text{C}}_{\mathrm{2}}$ . Similarly, $S_{\mathrm{2}}$ merges ${\text{NOC}}_{\mathrm{1}}$ and ${\text{OCC}}_{\mathrm{3}}$ to $\text{NO}{\text{C}}_{\mathrm{3}}$ . But $\text{OC}{\text{C}}_{\mathrm{2}}$ is not merged since it does not overlap with other clusters. And another sensor node $S_{\mathrm{3}}$ generates the clusters $\text{OC}{\text{C}}_{\mathrm{3}}$ and $\text{OC}{\text{C}}_{\mathrm{4}}$ .

Figure 6

Clustering in $S_{\mathrm{2}}$ and $S_{\mathrm{3}}$ .

A sensor node $S_{\mathrm{1}}$ receives the clusters from its child nodes as shown in Figure 7. $S_{\mathrm{1}}$ merges $\text{NO}{\text{C}}_{\mathrm{3}}$ and $\text{OC}{\text{C}}_{\mathrm{4}}$ into $\text{NO}{\text{C}}_{\mathrm{4}}$ , and it merges its sensor reading and $\text{OC}{\text{C}}_{\mathrm{3}}$ into $\text{NO}{\text{C}}_{\mathrm{5}}$ . Finally, $S_{\mathrm{1}}$ transmits the clusters to the base station, and then the base station detects the outlier cluster using the outlier candidate cluster $\text{OC}{\text{C}}_{\mathrm{8}}$ .

Figure 7

Clustering in $S_{\mathrm{1}}$ .

4.3. Multidimensional Clustering Scheme

Generally, since the sensor nodes in WSNs are equipped with several sensor devices, sensor readings are multidimensional. For instance, when a sensor node obtains the weather information, it detects temperature as well as other parameters such as humidity and light. Thus, we propose the clustering scheme for a set of multidimensional data.

Let a set of d-dimension sensor readings $R^d$ be $\{r_{\mathrm{1}}^d,r_{\mathrm{2}}^d,...,r_n^d\}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}(|R^d|=n)$ . A d-dimensional sensor reading $r_i^d$ is represented as $〈r_i[\mathrm{1}],\dots ,r_i[d]〉$ , where $r_i^d[k]$ denotes the kth dimensional value of $r_i^d$ . On each dimension k such that $\mathrm{1}\le k\le d$ , we obtain the permission range ${\text{PR}}_k=(\text{MAX}(\{r_{\mathrm{1}}^d[k],\dots ,r_n^d[k]\})-\text{MIN}(\{r_{\mathrm{1}}^d[k],\dots ,r_n^d[k]\}))/(n-\mathrm{1})$ derived from (1). To merge the clusters, we extend Definition 2 as follows:

Definition 3.

Let a d-dimensional cluster range of a cluster $C_i$ be ${\text{CR}}_i^d$ , where the kth dimensional ranges of ${\text{CR}}_i^d$ are denoted as ${\text{CR}}_i^d[k]=[{\min }_i^d[k],{\max }_i^d[k]]$ with $\mathrm{1}\le k\le d$ . Given two d-dimensional cluster ranges ${\text{CR}}_i^d$ and ${\text{CR}}_j^d$ , if ${\min }_i^d[k]<{\min }_j^d[k]$ and ${\min }_j^d[k]-{\max }_i^d[k]\le {\text{PR}}_k$ on a dimension k, we say ${\text{CR}}_i^d$ and ${\text{CR}}_j^d$ overlap within ${\text{PR}}_k$ on the kth dimension.

Based on Definition 3, For every dimension k with $\mathrm{1}\le k\le d$ ,   ${\text{CR}}_i^d$ and ${\text{CR}}_j^d$ overlap within ${\text{PR}}_k$ ; we merge the clusters $C_i$ and $C_j$ into a new cluster.

For example, given three cluster ranges ${\text{CR}}_{\mathrm{1}}^d$ , ${\text{CR}}_{\mathrm{2}}^d$ , and ${\text{CR}}_{\mathrm{3}}^d$ where $d=\mathrm{2}$ , $n=\mathrm{7}$ , $\text{P}{\text{R}}_{\mathrm{1}}=\mathrm{1}$ , and $\text{P}{\text{R}}_{\mathrm{2}}=\mathrm{1.5}$ in Table 1, we merge ${\text{CR}}_{\mathrm{1}}^d$ and ${\text{CR}}_{\mathrm{2}}^d$ based on Definition 3. On the first dimension, since ${\min }_{\mathrm{1}}^d[\mathrm{1}]<{\min }_{\mathrm{2}}^d[\mathrm{1}]$ and ${\min }_{\mathrm{2}}^d[\mathrm{1}]-{\max }_{\mathrm{1}}^d[\mathrm{1}](=\mathrm{5}-\mathrm{4})$ are less than or equal to ${\text{PR}}_{\mathrm{1}}(=\mathrm{1})$ , ${\text{CR}}_{\mathrm{1}}^d$ and ${\text{CR}}_{\mathrm{2}}^d$ overlap within ${\text{PR}}_{\mathrm{1}}$ . ${\text{CR}}_{\mathrm{1}}^d$ and ${\text{CR}}_{\mathrm{2}}^d$ also overlap within ${\text{PR}}_{\mathrm{2}}$ on the second dimension. Thus, ${\text{CR}}_{\mathrm{1}}^d$ and ${\text{CR}}_{\mathrm{2}}^d$ are merged into a new cluster. However, ${\text{CR}}_{\mathrm{3}}^d$ is not merged into other clusters since ${\text{CR}}_{\mathrm{3}}^d$ is not overlapped with any clusters on the second dimension such as ${\min }_{\mathrm{3}}^d[\mathrm{2}]-{\max }_{\mathrm{1}}^d[\mathrm{2}](=\mathrm{18}-\mathrm{13})>{\text{PR}}_{\mathrm{2}}(=\mathrm{1.5})$ .

Table 1

Example of CRs on 2 dimensions.

Cluster ranges	$k=\mathrm{1}$	$k=\mathrm{2}$
$\text{C}{\text{R}}_{\mathrm{1}}^d$	$\text{C}{\text{R}}_{\mathrm{1}}^d[k]=[\mathrm{3,4}]$	$\text{C}{\text{R}}_{\mathrm{1}}^d[k]=[\mathrm{12,13}]$
$\text{C}{\text{R}}_{\mathrm{2}}^d$	$\text{C}{\text{R}}_{\mathrm{2}}^d[k]=[\mathrm{5,6}]$	$\text{C}{\text{R}}_{\mathrm{2}}^d[k]=[\mathrm{10,11}]$
$\text{C}{\text{R}}_{\mathrm{3}}^d$	$\text{C}{\text{R}}_{\mathrm{3}}^d[k]=[\mathrm{7,9}]$	$\text{C}{\text{R}}_{\mathrm{3}}^d[k]=[\mathrm{18,19}]$

5. Experiments

5.1. Experimental Environments

To evaluate the performance of our proposed algorithm compared with the state-of-the-art algorithm, we used a set of real-life data which is provided by Intel Berkeley Research Lab [24]. A sensor network consists of 54 sensor nodes, and each sensor node is deployed in $40.5\times 31$  (m²) area as shown in Figure 8. The base station is located at the center of the area. We set the default communication distance 7 m. The maximum depth and the maximum width of a routing tree in sensor network are 5 and 3, respectively. Sensor readings consist of temperature (Celsius), humidity (%), and illumination (Lux).

Figure 8

Placement of sensor nodes [24].

As competitors, we implemented the Brute-Force ( $\text{BF}$ ) and an outlier technique based on data clustering ( $\text{DC}$ ) [18]. In $\text{BF}$ , each sensor node transmits its readings to the base station at each epoch.

In $\text{DC}$ , each sensor node in a network transmits a set of intercluster distances (ICDs) in respect of sensor readings along the routing paths to the base station. The intercluster distance is the distance of centers in any two data clusters in each sensor node. If the intercluster distance is less than the user-defined threshold ε, two data clusters are merged. When the base station receives ICDs from all sensor nodes, it computes the ICDs of the k-nearest clusters. And then, the base station broadcasts the means of ICDs in order to identify the outliers in each sensor node. We set ε and k for $\text{DC}$ are 0.26 and 4, respectively. We called our proposed algorithm $\text{PC}$ .

To compute the energy consumption, we use the free space channel model [25]. Under this model, to transmit an l-bits message and a distance c, a sensor expends

$$\begin{array}{l}{E}_T\left(l,c\right)=E_{T\text{-elec}}\left(l\right)+E_{T\text{-amp}}\left(l,c\right)\\ =l*E_{\text{elec}}+{\xi }_{\text{amp}}*l*c^{\mathrm{2}}.\end{array}$$

(2)

And, to receive this message, a sensor expends

$$\begin{array}{cc}& E_R\left(l\right)=E_{R\text{-elec}}\left(l\right)=l*E_{\text{elec}}.\end{array}$$

(3)

In this experiment, we set 50 nJ/bit to the electronic circuit constant ( $E_{\text{elec}}$ ) and 100 pJ/bit/m² to the transmit amplifier constant ( ${\xi }_{\text{amp}}$ ). We set the size of packet as 40 bytes. The parameters used in our experiment are summarized in Table 2.

Table 2

Parameters.

Parameter	Default value	Range
Packet size (p)	40	40
Window size (w)	8	2, 5, 8, 11, 14
Threshold (θ)	2	1, 2, 3, 4, 5
Dimension (d)	1	1, 2, 3

5.2. Experimental Result

To evaluate the energy consumption of each outlier detection algorithm, we run our own simulator for 1000 epoches and plot the total energy consumption.

Figure 9 shows the energy consumption varying the window size w. When the size of a window is small (i.e., $w=\mathrm{2}$ ), $\text{BF}$ shows the best performance since $\text{BF}$ transmits sensor readings, but $\text{DC}$ and $\text{PC}$ transmit the information of clusters.

Figure 9

Varying the window size (w).

However, as w increases, the performance of $\text{PC}$ and $\text{DC}$ is improved since the cluster information rather than sensor readings is transmitted. Furthermore, the performance gap between $\text{PC}$ and $\text{DC}$ increases with increasing w. As w increases, the number of nonoutlier clusters (NOCs) increases in $\text{PC}$ . Thus, the size of data to be transmitted decreases. In $\text{DC}$ , the energy consumption is reduced since $\text{DC}$ is also based on data clustering as $\text{PC}$ . However, our proposed $\text{PC}$ is better than $\text{DC}$ because $\text{PC}$ used the permission range to determine the cluster width. Additionally, in $\text{DC}$ , the mean of   ICDs needs to be broadcasted to obtain the outliers in each sensor node. Our proposed algorithm $\text{PC}$ is better than the $\text{DC}$ about 58% on the average.

Figure 10 shows the energy consumption varying θ. As shown in Figure 10, the performances of all techniques are stable in spite of varying θ. The energy consumption of $\text{DC}$ is constant, since the intercluster information has a fixed size. But the energy consumption of $\text{PC}$ increases slightly, since the number of sensor readings in an outlier candidate cluster increases slightly. Nonetheless, our proposed technique $\text{PC}$ shows the best performance in terms of energy efficiency. In this experiment, our proposed technique is better than the $\text{DC}$ about 51%.

Figure 10

Varying the threshold size (θ).

Figure 11 shows the energy consumption varying the dimension d. The energy consumption of all techniques is increased according to varying d, because the packet of the sensor nodes on multidimension contains more information as compared with that on 1 dimension. The energy consumption of $\text{PC}$ is less than other techniques $\text{BF}$ and $\text{DC}$ . In other words, our proposed technique is better than the $\text{DC}$ about $\mathrm{48}\%$ .

Figure 11

Varying the dimension (d).

6. Conclusion

In this paper, we present an efficient outlier detection technique in WSNs. To obtain the appropriate width of clusters, we applied the Pigeonhole Principle. In our proposed technique, each sensor node in WSNs constructs and merges the clusters based on the permission range PR. Then, our proposed technique uses two kinds of clusters (NOC and OCC) in order to detect the outliers and reduce the energy consumption of each sensor. In our experiments with a set of real-life data, we show that our proposed technique outperforms existing techniques significantly.