A Multimodel Based Range Query Processing Algorithm for Information Collection in CPS

Abstract

A multimodel based range query processing algorithm is proposed to solve the information collection task for the CPSs, which utilizes multiple probability models to depict the data distribution of a sensor node. The execution of the multimodel based algorithm consists of two phases, which are the preprocessing phase and the query processing phase. During the preprocessing phase, multiple models are constructed for each node according to their historical data. During the query processing phase, a suitable model is selected from the multiple models with the help of a sampling based algorithm, which is used to process the query. As the multimodel based algorithm needs to sample data from the network, it can waste energy more than that of the single model based algorithm in some cases, which does not sample data from the network. The cost of the multimodel based and single model based algorithm is analyzed. A cost model based algorithm is proposed to select a better algorithm to process a query from the two algorithms. Experimental results show that the cost model based algorithm can save 13.3% energy consumption more than that of the single model based algorithm.

1. Introduction

Cyber-physical systems (CPSs), which consist of computing devices and embedded systems such as distributed sensors and actuators, integrate computation, communication, and control with the physical world [1]. The tasks, running on the CPSs, involve close interactions between the cyber world and the physical world. Extracting knowledge from the physical world is an important task for the CPSs. Some useful information is collected from the physical world firstly and then analyzed to extract knowledge. Wireless sensor networks (WSNs) [2–5] are usually used to fulfill the information collection task, which is transformed into some kinds of queries for the WSNs [6–10].

The range query is one of the most important types of queries to collect information from the WSNs. For instance, a range query is sent to the sensor network distributed in a forest, asking for the places where the temperature lies in $[r_{\mathrm{1}},r_{\mathrm{2}}]$ . The sensors, whose temperature lies in this range, return their locations or IDs to the sink. If the sensors return their IDs, the sink transforms the IDs to locations and returns the locations.

Some existing methods have been proposed to solve the range query in the WSN, which can be classified into two classes. The first class is the data centric storage based algorithms, such as GHT [11], DIM [12], comb-needle [13], double ruling [14], and energy-aware algorithm [15]. The data centric storage algorithms define different types of events for the data collected by sensors. Each type of events is stored in a particular node called event storage node in the WSN. When a node detects an event, it transmits the data of the event to the event storage node. A range query, transformed to a query for an event, is sent directly to the event storage node and answered by the node. The event defined in the data centric storage algorithm is very rigid, which means the users can only ask for the result of a range defined by the event. So these algorithms do not fit for the query asking for the result of any range.

The second class is the local storage based algorithms, such as [16–19]. For the traditional local storage based algorithms [16, 17], the data collected by a sensor is stored in its local storage. The queries are sent to each node and the nodes satisfying the query return their results to the user. The problem of the traditional algorithm is that all nodes need to return their results to the sink whether they satisfy the query or not, which consumes a lot of energy. In [19], a probability model is used to process the range query. The probability model is used to estimate the probability that each node satisfies the query. Only if the probability of a node, satisfying the query, is above a threshold, the node is considered as a result. With the help of the probability model, nodes do not return any result to the sink for a range query. There are two problems for the algorithm. The first one is the algorithm can only give an approximate answer to a query. The second one is it is hard to determine a threshold balancing the efficiency of energy consumption and the accuracy of the query result.

In this paper, we propose a multimodel based algorithm to solve the range query in the WSN, which is a local storage based algorithm. Compared with the other local storage based algorithms, our algorithm has the following advantages. First, our algorithm constructs multiple probability models. With the help of these probability models, only the most relevant nodes among all nodes need to transmit their results to the sink, which saves more energy than the traditional local storage algorithms. Second, our algorithm can give the precise answer to the range query with minimum energy consumption. The multimodel based range query processing algorithm proposed in this paper is composed of 3 steps:

• (1)

probability model construction;

(2)

sampling based model selection;

(3)

model based query processing.

The probability model construction algorithm first constructs multiple probability models for each node in the WSN. By clustering the historical data collected by the nodes, m subclasses are constructed and each node builds a probability model according to the data of its own in a subclass. With the help of the multiple probability models, the query processing algorithm can select the more accurate model to describe the data distribution for the current condition than that of the single model based algorithm.

Multiple probability models have been constructed for each node in the WSN. For a particular range query, there must be a method to select a suitable probability model for each node to process the query. In this paper, a sampling based algorithm is proposed to fulfill this task. Some typical nodes are selected by a preprocessing algorithm. Then the sampling based algorithm collects the data from these typical nodes to determine a suitable model for a query.

Combining the model selected by the sampling based model selection algorithm with the real data sensed by a node, the model based query processing algorithm can minimize the energy consumption of processing a range query. While the performance of the multimodel based algorithm is not the best in all cases, we analyze the cost of the multimodel based algorithm and propose a range query processing algorithm augmented with the cost model, which selects a suitable query processing algorithm for a range query according to the cost model. Experimental results show that the cost model based algorithm can provide the accurate answer with 13.3% energy consumption less than that of the single model based algorithm.

The contributions of this paper are as follows. First, a multimodel based algorithm is proposed to solve the range query in the WSN, which utilizes multiple probability models to improve the accuracy of the data distribution function and saves the energy consumption of the algorithm. Second, the energy consumption of the multimodel based algorithm is analyzed and a query processing algorithm augmented with the cost model is proposed to save energy in most cases. Third, extensive experiments were done to verify the efficiency of the proposed algorithms.

The rest of the paper is organized as follows. Section 2 introduces the multimodel based range query processing algorithm. Section 3 analyzes the cost model of the multimodel based algorithm and proposes the query processing algorithm augmented with the cost model. Section 4 evaluates the performance of the proposed algorithms on real dataset. Section 5 briefly discusses the related work and in Section 6 we draw the conclusion.

2. The Model Based Range Query Processing Algorithm

2.1. Probability Model Construction

First, multiple probability models are constructed for each node in the WSN based on the historical data collected from each node. Let N be the set of all nodes in the WSN and let $\left|N\right|$ be the number of nodes in the WSN. Each node collects data, such as the temperature and humidity, from the environment at a certain rate. The data from all nodes at a given timestamp t consists of a vector $V_t=(v_t^{\mathrm{1}},v_t^{\mathrm{2}},\dots ,v_t^{\left|N\right|})$ , where $v_t^j$ represents the data collected by the jth node $n^j$ at the timestamp t. The historical data set H is composed of a set of vectors $V_t$ at different timestamps. Given the historical data set H, the vectors in H can be clustered into many subclasses. If the vectors in H are clustered into m subclasses, represented as $H_{\mathrm{1}},H_{\mathrm{2}},\dots ,H_m$ , a probability model can be constructed for each node based on the vectors contained in a subclass. For convenience, we list the notations used throughout this paper in the Notations section shown at the end of the paper.

The data collected by a node is a random variable, which can be described by a probability distribution function (PDF). The PDF of a random variable is usually hard to calculate, but it can be estimated by a histogram. A histogram is a representation of tabulated frequencies, erected over discrete intervals (bins), with an area equal to the frequency of the observations in the interval. The total area of the histogram is equal to the amount of data.

The vectors belonging to the ith subclass $H_i$ can be used to construct a histogram for each node in the WSN. For $H_i$ , all data belonging to the node $n^j$ forms a data set represented as $D_i^j=\{v_t^j\hspace{0.17em}|\hspace{0.17em}\forall V_t\in H_i,v_t^j\in V_t\}$ . Let $v_{t\mathrm{1}}^j=\mathrm{m}\mathrm{a}\mathrm{x}\{D_i^j\}$ and $v_{t\mathrm{2}}^j=\mathrm{m}\mathrm{i}\mathrm{n}\{D_i^j\}$ , which means $v_{t\mathrm{1}}^j$ and $v_{t\mathrm{2}}^j$ are the maximum and minimum value of node $n^j$ in $D_i^j$ . The range $[⌊v_{t\mathrm{2}}^j⌋,⌈v_{t\mathrm{1}}^j⌉)$ can be equally divided into $(⌈v_{t\mathrm{1}}^j⌉-⌊v_{t\mathrm{2}}^j⌋+\mathrm{1})$ bins, whose length is 1. $f_x^j$ represents the number of data falling into the interval $[x,x+\mathrm{1})$ . If the range $[⌊v_{t\mathrm{2}}^j⌋,⌈v_{t\mathrm{1}}^j⌉)$ is smaller than $\mathrm{1}$ , we can enlarge the range multiple times to make it larger than 1. If the range is enlarged, the data sampled from a sensor must be enlarged by the same times.

In the same way, a probability model can be constructed for each node based on the vectors in each subclass. If the historical data set H is divided into m subclasses, m probability models are constructed for each node. The ith probability model of a node $n^j$ is represented by $M_i^j$ . There is one special probability model for each node, called general model, which is constructed based on all the historical data collected by a node instead of a subset of data. The construction method of the general model is the same as that of the other models. The general model of a node $n^j$ is represented as $M_g^j$ . There are altogether $m+\mathrm{1}$ probability models for each node, which can be classified into two classes $M^j=\{M_{\mathrm{1}}^j,M_{\mathrm{2}}^j,\dots M_m^j\}$ and $M_g^j$ .

Given a range $[a,b]$ , the probability of the data falling in $[a,b]$ calculated by $M_i^j$ is represented as ${\mathrm{p}\mathrm{r}}_i^j\{[a,b]\}$ , which can be estimated by formula (1) based on the histogram. The ratio of the area of the histogram of the range $[⌊a⌋,⌈b⌉)$ to the total area of the histogram of the range $[⌊v_{t\mathrm{2}}^j⌋,⌈v_{t\mathrm{1}}^j⌉)$ is used to estimate ${\mathrm{p}\mathrm{r}}_i^j\{[a,b]\}$ in

$$\begin{array}{cc}& {\mathrm{p}\mathrm{r}}_i^j\left\{\left[a,b\right]\right\}=\frac{{\sum }_{x=⌊a⌋}^{⌈b⌉-\mathrm{1}}{f}_x^j}{{\sum }_{y=⌊v_{t\mathrm{2}}^j⌋}^{⌈v_{t\mathrm{1}}^j⌉-\mathrm{1}}{f}_y^j}.\end{array}$$

(1)

2.2. The Typical Node Selection Algorithm

Multiple probability models have been constructed for each node in the WSN. For a particular range query, there must be a method to select a probability model for each node to process the query. In this paper, a sampling based method is proposed to fulfill this task.

Firstly, some typical nodes are selected from the WSN. Before sending a range query to the WSN, the sink samples data from the typical nodes. Based on the data sampled from the typical nodes, a suitable probability model $M_i^j\in M^j$ is selected to make the query processing algorithm be carried out efficiently. Before giving the typical node selection algorithm, we present some definitions.

Let ${\mu }_i^j$ represent the mean of $D_i^j$ of the node $n^j$ . ${\mu }_i^j$ can be calculated by formula (2), where $\left|H_i\right|$ represents the number of vectors in the subclass $H_i$ :

$$\begin{array}{cc}& {\mu }_i^j=\frac{{\sum }_{\forall v_t^j\in D_i^j}^{}{v}_t^j}{\left|H_i\right|}.\end{array}$$

(2)

Definition 1 (data range).

The data range of a node $n^j$ , whose data belongs to $D_i^j$ , is defined as $R_i^j=[⌊{\mu }_i^j⌋-x,⌈{\mu }_i^j⌉+y]$ and ${\mathrm{p}\mathrm{r}}_i^j\{R_i^j\}\ge \sigma$ , where σ ( $\mathrm{0}<\sigma <\mathrm{1}$ ) is called the coverage threshold.

The range $R_i^j$ is a subrange of the total range of the model $M_i^j$ . The ratio of the area of $R_i^j$ of the histogram and the total area of the histogram is not less than a threshold σ.

Theorem 2.

The x and y of a data range are integers.

Proof.

$R_i^j$ of a node $n^j$ is constructed as follows. ${\mu }_i^j$ is calculated according to formula (2), which falls into the bin $[⌊{\mu }_i^j⌋,⌈{\mu }_i^j⌉]$ of the model $M_i^j$ of the node $n^j$ . Initially, we set $R_i^j=[⌊{\mu }_i^j⌋,⌈{\mu }_i^j⌉]$ and check whether the ratio of the area of current $R_i^j$ of the model $M_i^j$ and the total area of the model $M_i^j$ is not less than σ. If not, we add all adjacent bins of the current $R_i^j$ to it, which means one or two bins are added to the current $R_i^j$ . The $R_i^j$ is expanded until the coverage threshold σ is reached. As the interval of the histogram is 1, the final $R_i^j$ is $[⌊{\mu }_i^j⌋-x,⌈{\mu }_i^j⌉+y]$ where x and y are integers.

As there are m subclasses, the node $n^j$ has m data ranges, represented by $R_{\mathrm{1}}^j,R_{\mathrm{2}}^j,\dots ,R_m^j$ . The intersection between the lth and the kth data range of the node $n^j$ is represented as $R_{lk}^j=R_l^j\cap R_k^j$ . There are altogether $C(m,\mathrm{2})$ intersections between any two data ranges of a node, where $C(m,\mathrm{2})$ represents the number of the 2 combinations from integer $\mathrm{1}$ to m.

Definition 3 (candidate node).

If an intersection $R_{lk}^j$ of the node $n^j$ satisfies the condition $\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(R_{lk}^j)=\mathrm{m}\mathrm{i}\mathrm{n}\{\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(R_{lk}^x)\hspace{0.17em}|\hspace{0.17em}x=\mathrm{1,2},\dots ,|N|\}$ , the node $n^j$ is called a candidate node. The pair $(l,k)$ is called distinguishable by the candidate node $n^j$ . $\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{h}(·)$ is a function, representing the length of the intersection.

For example, in Figure 1, there are two nodes $n^{\mathrm{1}}$ and $n^{\mathrm{2}}$ in the WSN. The data collected by them is clustered into two subclasses. The data ranges of $n^{\mathrm{1}}$ are $R_{\mathrm{1}}^{\mathrm{1}}=[v_{\mathrm{1}}^{\mathrm{1}},v_{\mathrm{2}}^{\mathrm{1}}]$ for subclass 1 and $R_{\mathrm{2}}^{\mathrm{1}}=[v_{\mathrm{3}}^{\mathrm{1}},v_{\mathrm{4}}^{\mathrm{1}}]$ for subclass 2. The data ranges of $n^{\mathrm{2}}$ are $R_{\mathrm{1}}^{\mathrm{2}}=[v_{\mathrm{1}}^{\mathrm{2}},v_{\mathrm{2}}^{\mathrm{2}}]$ for subclass 1 and $R_{\mathrm{2}}^{\mathrm{2}}=[v_{\mathrm{3}}^{\mathrm{2}},v_{\mathrm{4}}^{\mathrm{2}}]$ for subclass 2.

Figure 1

Illustration to data range and candidate node.

In Figure 1(a), the intersection $R_{\mathrm{12}}^{\mathrm{1}}=[v_{\mathrm{1}}^{\mathrm{1}},v_{\mathrm{2}}^{\mathrm{1}}]\cap [v_{\mathrm{3}}^{\mathrm{1}},v_{\mathrm{4}}^{\mathrm{1}}]=\varnothing$ and the intersection $R_{\mathrm{12}}^{\mathrm{2}}=[v_{\mathrm{1}}^{\mathrm{2}},v_{\mathrm{2}}^{\mathrm{2}}]\cap [v_{\mathrm{3}}^{\mathrm{2}},v_{\mathrm{4}}^{\mathrm{2}}]=[v_{\mathrm{3}}^{\mathrm{2}},v_{\mathrm{2}}^{\mathrm{2}}]$ . As $\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(R_{\mathrm{12}}^{\mathrm{1}})=\mathrm{0}<\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(R_{\mathrm{12}}^{\mathrm{2}})=v_{\mathrm{2}}^{\mathrm{2}}-v_{\mathrm{3}}^{\mathrm{2}}$ , according to the definition of the candidate node, $n^{\mathrm{1}}$ is the candidate node and it can distinguish the subclass 1 from the subclass 2. If we sample data $v_t^{\mathrm{1}}$ from the node $n^{\mathrm{1}}$ and find $v_t^{\mathrm{1}}\in R_{\mathrm{1}}^{\mathrm{1}}$ , at this time, the models for every node ( $M_{\mathrm{1}}^{\mathrm{1}}$ and $M_{\mathrm{1}}^{\mathrm{2}}$ ) constructed from the subclass 1 are better than those ( $M_{\mathrm{2}}^{\mathrm{1}}$ and $M_{\mathrm{2}}^{\mathrm{2}}$ ) constructed from the subclass 2 to process the query.

In Figure 1(b), $\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(R_{\mathrm{12}}^{\mathrm{1}})=v_{\mathrm{2}}^{\mathrm{1}}-v_{\mathrm{3}}^{\mathrm{1}}<\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(R_{\mathrm{12}}^{\mathrm{2}})=v_{\mathrm{2}}^{\mathrm{2}}-v_{\mathrm{3}}^{\mathrm{2}}$ , which means $n^{\mathrm{1}}$ is the candidate node. When data sampled from $n^{\mathrm{1}}$ falls in $[v_{\mathrm{1}}^{\mathrm{1}},v_{\mathrm{3}}^{\mathrm{1}}]$ or $[v_{\mathrm{2}}^{\mathrm{1}},v_{\mathrm{4}}^{\mathrm{1}}]$ , the probability models constructed by subclass 1 or subclass 2 are selected. But when the data from $n^{\mathrm{1}}$ falls in $[v_{\mathrm{3}}^{\mathrm{1}},v_{\mathrm{2}}^{\mathrm{1}}]$ , the models cannot be determined directly. We propose a Euclidean distance based method to solve this problem in the next section. Compared with the length of $[v_{\mathrm{3}}^{\mathrm{2}},v_{\mathrm{2}}^{\mathrm{2}}]$ of $n^{\mathrm{2}}$ , the length of $[v_{\mathrm{3}}^{\mathrm{1}},v_{\mathrm{2}}^{\mathrm{1}}]$ of $n^{\mathrm{1}}$ is much smaller, which means the probability, that a model cannot be determined, is minimized. That is why $n^{\mathrm{1}}$ is selected as the candidate node.

The typical node selection algorithm needs to prepare some parameters with the help of a preprocessing algorithm. The preprocessing algorithm first calculates the m data ranges $R_i^j\hspace{0.17em}\hspace{0.17em}(i=\mathrm{1},\dots ,m)$ for each node. Then the preprocessing algorithm calculates the $C(m,\mathrm{2})$ intersections $R_{lk}^j$ for each node. As there can be multiple nodes satisfying the definition of candidate node for an intersection $R_{lk}^j$ , the preprocessing algorithm calculates a candidate node set ${\mathrm{C}\mathrm{N}}_{lk}$ for each intersection, which is composed of all the candidate nodes of the intersection. Finally, the preprocessing algorithm merges the candidate nodes in the candidate node sets of all nodes into a merged candidate node (MCN) set. Each element in $\mathrm{M}\mathrm{C}\mathrm{N}$ has two attributes, which are a counter and a list. If multiple intersections have the same candidate node in their candidate node sets, these candidate nodes are merged into a unique one, called merged candidate node. The counter of the merged candidate node is the number of ${\mathrm{C}\mathrm{N}}_{lk}$ containing the merged candidate node. The list of the merged candidate node is all the pairs $(l,k)$ of ${\mathrm{C}\mathrm{N}}_{lk}$ containing the merged candidate node. Let I be a set of the pairs $(l,k)$ , which contains the $C(m,\mathrm{2})$ 2 combinations of the m subclasses. The preprocessing algorithm is given in Algorithm 1.

Algorithm 1: The preprocessing algorithm.

Input: $N,H_i\hspace{0.17em}(\mathrm{1}\le i\le m)$ , I

Output: MCN

(1) for each node $n^j\in N$ do

(2)  calculate the m Data Ranges $R_i^j$ for a node $n^j$

(3) end for

(4) for each node $n^j\in N$ do

(5)  calculate all the intersections $R_{lk}^j=R_l^j\cap R_k^j$ for a node $n^j$

(6) end for

(7) for each pair of $(l,k)\in I$ do

(8)  find the node $n^j$ with the minimum $R_{lk}^j$ among all nodes

(9)  put $n^j$ into the candidate node set $\text{C}{\text{N}}_{lk}$

(10) end for

(11) construct the MCN by selecting the unique nodes from all $\text{C}{\text{N}}_{lk}$

(12) for each node $n^j$ in the MCNdo

(13)  $n^j\to$ counter = the number of $\text{C}{\text{N}}_{lk}$ containing $n^j$

(14)  $n^j\to$ list = all the pairs $(l,k)$ of $\text{C}{\text{N}}_{lk}$ containing $n^j$

(15) end for

(16) return MCN

For example, Figure 2 shows that there are two nodes $n^{\mathrm{1}}$ and $n^{\mathrm{2}}$ in the WSN. The data collected by the two nodes are clustered into three subclasses. The data ranges of $n^{\mathrm{1}}$ for the three subclasses are $R_{\mathrm{1}}^{\mathrm{1}}=[v_{\mathrm{1}}^{\mathrm{1}},v_{\mathrm{2}}^{\mathrm{1}}]$ for subclass 1, $R_{\mathrm{2}}^{\mathrm{1}}=[v_{\mathrm{3}}^{\mathrm{1}},v_{\mathrm{4}}^{\mathrm{1}}]$ for subclass 2, and $R_{\mathrm{3}}^{\mathrm{1}}=[v_{\mathrm{5}}^{\mathrm{1}},v_{\mathrm{6}}^{\mathrm{1}}]$ for subclass 3. The data ranges of $n^{\mathrm{2}}$ for the three subclasses are $R_{\mathrm{1}}^{\mathrm{2}}=[v_{\mathrm{1}}^{\mathrm{2}},v_{\mathrm{2}}^{\mathrm{2}}]$ for subclass 1, $R_{\mathrm{2}}^{\mathrm{2}}=[v_{\mathrm{3}}^{\mathrm{2}},v_{\mathrm{4}}^{\mathrm{2}}]$ for subclass 2, and $R_{\mathrm{3}}^{\mathrm{2}}=[v_{\mathrm{5}}^{\mathrm{2}},v_{\mathrm{6}}^{\mathrm{2}}]$ for subclass 3. Also $R_{\mathrm{12}}^{\mathrm{1}}=R_{\mathrm{1}}^{\mathrm{1}}\cap R_{\mathrm{2}}^{\mathrm{1}}=\varnothing$ . In the same way, we can calculate $R_{\mathrm{13}}^{\mathrm{1}}=\varnothing$ , $R_{\mathrm{23}}^{\mathrm{1}}=\varnothing$ , $R_{\mathrm{12}}^{\mathrm{2}}=[v_{\mathrm{5}}^{\mathrm{2}},v_{\mathrm{2}}^{\mathrm{2}}]$ , $R_{\mathrm{13}}^{\mathrm{2}}=[v_{\mathrm{3}}^{\mathrm{2}},v_{\mathrm{4}}^{\mathrm{2}}]$ , and $R_{\mathrm{23}}^{\mathrm{2}}=\varnothing$ . Based on the results, the candidate node set ${\mathrm{C}\mathrm{N}}_{\mathrm{12}}=\{n^{\mathrm{1}}\}$ , because $\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(R_{\mathrm{12}}^{\mathrm{1}})=\mathrm{0}<\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(R_{\mathrm{12}}^{\mathrm{2}})=v_{\mathrm{5}}^{\mathrm{2}}-v_{\mathrm{2}}^{\mathrm{2}}$ . Moreover ${\mathrm{C}\mathrm{N}}_{\mathrm{13}}=\{n^{\mathrm{1}}\}$ and ${\mathrm{C}\mathrm{N}}_{\mathrm{23}}=\{n^{\mathrm{1}},n^{\mathrm{2}}\}$ . The $\mathrm{M}\mathrm{C}\mathrm{N}$ contains two nodes $\{n^{\mathrm{1}},n^{\mathrm{2}}\}$ . After merging, the counter of $n^{\mathrm{1}}$ is $\mathrm{3}$ , because all of the candidate node sets contain $n^{\mathrm{1}}$ . The list of $n^{\mathrm{1}}$ contains $\{(\mathrm{1,2}),(\mathrm{1,3}),(\mathrm{2,3})\}$ . The counter of $n^{\mathrm{2}}$ is $\mathrm{1}$ . The list of $n^{\mathrm{2}}$ only contains $\{(\mathrm{2,3})\}$ .

Figure 2

Illustration to the preprocessing algorithm.

Based on the definitions and the $\mathrm{M}\mathrm{C}\mathrm{N}$ calculated by the preprocessing algorithm, we propose a greedy based algorithm to select the typical nodes from the WSN. The greedy algorithm sorts all the merged candidate nodes in the $\mathrm{M}\mathrm{C}\mathrm{N}$ according to their counters in descending order. Then it selects the candidate node with the largest counter as the typical node and removes the selected node from the $\mathrm{M}\mathrm{C}\mathrm{N}$ . Then the entries in the list of the selected node are removed from I and the list of the other merged candidate nodes is left in the $\mathrm{M}\mathrm{C}\mathrm{N}$ . When an entry is removed from the list of a merged candidate node left, the counter of the node is subtracted by 1. The greedy based algorithm repeats this process until the set I is empty, which means any two models can be distinguished by a candidate node selected. All the candidate nodes are selected from the typical node set T. The jth typical node $n^j$ in T has an attribute represented as ${\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}}^j$ , which is the number of intersections $n^j$ can distinguish. The greedy based typical node selection algorithm is given in Algorithm 2.

Algorithm 2: The typical node selection algorithm.

Input: MCN

output: T

(1) while  $I\ne \mathrm{\varnothing }$  do

(2)  sort the nodes in the MCN according to their counters in descending order

(3)  select the node with maximum counter from MCN

(4)  add the selected node $n^j$ to the typical node set T

(5)  set $n^j\to counte{r}^j$ to the current counter of $n^j$ in MCN

(6)  remove the selected node from MCN

(7)  remove all the pairs in the list of the selected node from I

(8)  remove all the pairs in the list of the selected node from the list of the other candidate nodes

(9)  subtract the counter of a candidate node in MCN by 1 when a pair is removed from the node's list

(10) end while

(11) return  T

For example, after sorting, $n^{\mathrm{1}}$ is selected into the typical node set, because its counter is $\mathrm{3}$ , which is bigger than the counter of $n^{\mathrm{2}}$ . The pairs in the list of $n^{\mathrm{1}}$ are removed from $I=\{(\mathrm{1,2}),(\mathrm{1,3}),(\mathrm{2,3})\}$ and the list of $n^{\mathrm{2}}$ . After removing, $n^{\mathrm{2}}\to \mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}=\varnothing$ , $n^{\mathrm{2}}\to \mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}=\mathrm{0}$ , and $I=\varnothing$ . As $I=\varnothing$ , Algorithm 2 finished. Otherwise, the candidate nodes left in $\mathrm{M}\mathrm{C}\mathrm{N}$ are sorted and the process is repeated again. In our example, the typical node set T is $\{n^{\mathrm{1}}\}$ . It is obvious in Figure 2 that the data collected from $n^{\mathrm{1}}$ can distinguish the models constructed by the three subclasses.

2.3. Sampling Based Model Selection and Model Based Query Processing Algorithms

The model based query processing algorithm for a range query works as follows. A node $n^j$ in the WSN stores the m models $M^j$ and a general model $M_g^j$ in its local storage. After receiving a range query from a user, the sink samples data from the typical nodes in T selected by Algorithm 2. According to the data sampled, a probability model is selected. The sink sends the range query together with the index of the model selected to all nodes in the WSN. A node processes the query with the help of the probability model selected. In this section, we will introduce the algorithm selecting a suitable probability model based on the sampled data and the model based query processing algorithm.

To save energy, the model selection algorithm does not sample data from all typical nodes at the same time. We sort the nodes in T according to their counters in descending order. The model selection algorithm samples data from one node in the typical node set at a time from the beginning. Only when the sampled data cannot determine a model, the data of the next typical node is sampled. Initially, the candidate model set, represented as $\mathrm{C}\mathrm{M}$ , is set to $\{\mathrm{1,2},\dots ,m\}$ . For data $v_t^j$ , sampled from a typical node $n^j$ , the model selection algorithm checks whether $v_t^j\in R_i^j$ for all m data ranges of $n^j$ . If the $v_t^j\notin R_i^j$ , the model selection algorithm removes the number i from $\mathrm{C}\mathrm{M}$ . If there is only one number left in $\mathrm{C}\mathrm{M}$ , the corresponding model is selected as the suitable model. Otherwise, there will be no number or multiple numbers in $\mathrm{C}\mathrm{M}$ . In this case, the model selection algorithm uses a distance based method to select the suitable model. The data sampled from the typical nodes forms a vector. As each subclass is composed of a lot of vectors, the center of each subclass also forms a vector. The vector formed by the data of the typical nodes is part of the center vectors of the subclasses. The data corresponding to the typical nodes is drawn from each center vector of the subclasses, which forms a partial center vector for each subclass. The model selection algorithm calculates the Euclidean distance d between the typical node vector and the partial center vector of each subclass and selects the subclass with the minimum distance as the suitable model. The model selection algorithm is given in Algorithm 3.

Algorithm 3: The model selection algorithm.

Input: $T,R_i^j(\mathrm{1}\le i\le m,\mathrm{1}\le j\le |N|)$

Output: index of the selected model

(1) set the candidate model set CM to $\{\mathrm{1,2},\dots ,m\}$

(2) sort the nodes in T according to their counters in descending order

(3) for each node $n^j\in T$  do

(4) sample data $v_t^j$ from $n^j$

(5) for each $R_i^j$ of $n^j$  do

(6)  if  $v_t^j\notin R_i^j$  then

(7)   remove i from CM

(8)  end if

(9) end for

(10)  if  $|\text{CM}|==\mathrm{0}$   or   $|\text{CM}|==\mathrm{1}$  then

(11)   break

(12)  end if

(13) end for

(14) if  $|\text{CM}|==\mathrm{1}$  then

(15)   $index=$ the element in CM

(16) else

(17)  construct the vector $V_s$ containing data sampled from the typical nodes

(18)  construct a partial center vector $V_i$ for each subclass

(19)  set the $d_{\min }=\mathrm{\infty }$

(20)  for  $\mathrm{1}\le i\le m$  do

(21)    $d=$ the Euclid distance between $V_s$ and $V_i$

(22)   if  $d\le d_{\min }$  then

(23)     $d_{\min }=d$

(24)     $index=i$

(25)   end if

(26)  end for

(27) end if

(28) return  $index$

After the sink selects a suitable probability model for a range query, it sends the index of the model together with the range query to all the nodes in the WSN. When a node $n^j$ receives the query, it calculates two probabilities. Firstly, it gets the index of the probability model and calculates the probability that the data of the node satisfies the range query according to the selected probability model. Secondly, it calculates the probability according to the general probability model. We represent the first probability as ${\mathrm{p}\mathrm{r}}_{\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}}^j$ and the second probability as ${\mathrm{p}\mathrm{r}}_g^j$ . The larger one of the two probabilities is chosen as the final probability represented as ${\mathrm{p}\mathrm{r}}_{\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{l}}^j$ . If ${\mathrm{p}\mathrm{r}}_{\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{l}}^j$ is larger than a threshold ρ, which is called the probability threshold, but the data really collected by the node does not satisfy the range query, the node returns a negative answer to the sink. If ${\mathrm{p}\mathrm{r}}_{\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{l}}^j\le \rho$ , while the data really collected by the node satisfies the range query, the node returns a positive answer to the sink. The node does not return any answer to the sink in other cases.

We calculate two probabilities that the data of the node satisfies the range query and use the larger one as the final probability, because the model constructed by a subclass of data of a node is not more accurate than the general model. For example, the multimodel based range query processing algorithm uses two models and a general model to depict the temperature of a room. One model depicts the distribution of the temperature from 7:00 A.M. to 9:00 A.M. and another model depicts the distribution of temperature from 9:00 A.M. to 11:00 A.M. The general model depicts the distribution of the temperature from 7:00 A.M. to 11:00 A.M. If the query range is from 8:00 A.M. to 10:00 A.M., neither of the two models can depict the distribution of the temperature more accurately than the general model. By comparing the probabilities calculated by the selected model and the general model, we guarantee that the final probability is not worse than that of the general model.

When ${\mathrm{p}\mathrm{r}}_{\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{l}}^j>\rho$ , it means that the data sampled by the node has a large probability to satisfy the query. The event, that the real data collected by the node does not satisfy the query, is a small probability event. Only if the small probability event happens, the node needs to send the answer to the sink, which minimizes the number of messages transmitted between the node and the sink. The same reason is for the other two cases. The model based range query processing algorithm is a distributed algorithm. The algorithm executed by the sink is given in Algorithm 4. The algorithm executed by an ordinary node is given in Algorithm 5.

Algorithm 4: The model based query processing algorithm for the sink.

Input: query range $[r_{\mathrm{1}},r_{\mathrm{2}}]$ , index of the selected model $index$

Output: the result node set Q

(1) $index=$ value returned by Algorithm 3

(2) for  $\forall n^j\in N$  do

(3)   $\text{p}{\text{r}}_{index}^j=$ the probability of the node satisfying the received range query calculated by the $index$ model

(4)   $\text{p}{\text{r}}_{general}^j=$ the probability of the node satisfying the received range query calculated by the general model

(5)  if  $\max \{\text{p}{\text{r}}_{index}^j,\text{p}{\text{r}}_g^j\}>\rho$  then

(6)   put $n^j$ into the result set Q

(7)  end if

(8) end for

(9) broadcast the query and the $index$ throughout the sensor network

(10) collect answers from the nodes in the network

(11) if receive a positive answer from a node $n^j$  then

(12)  put ID of node $n^j$ into the result set Q

(13) else if receive a negative answer from a node $n^j$  then

(14)  remove the ID of node $n^j$ from the result set Q

(15) end if

(16) return Q

Algorithm 5: The model based query processing algorithm for an ordinary node.

Input: $[r_{\mathrm{1}},r_{\mathrm{2}}]$ , $index$ , $v_t^j$

Output: $NULL$

(1) extract the $index$ and query range $[r_{\mathrm{1}},r_{\mathrm{2}}]$ from the packet received

(2) $\text{p}{\text{r}}_{index}^j=$ the probability of the node satisfying the received range query calculated by the $index$ model

(3) $\text{p}{\text{r}}_{general}^j=$ the probability of the node satisfying the received range query calculated by the general model

(4) if  $(\max \{\text{p}{\text{r}}_{index}^j,\text{p}{\text{r}}_{general}^j\}>\rho )$ & $(v_t^j\notin [r_{\mathrm{1}},r_{\mathrm{2}}])$  then

(5)  send a negative answer containing the ID of the current node to the sink

(6) else if  $(\max \{\text{p}{\text{r}}_{index}^j,\text{p}{\text{r}}_{general}^j\}\le \rho )$ & $(v_t^j\in [r_{\mathrm{1}},r_{\mathrm{2}}])$  then

(7)  send a positive answer containing the ID of the current node to the sink

(8) end if

3. Cost Analysis of the Multimodel Based Range Query Processing Algorithm

The multimodel based query processing algorithm is not always efficient for all range queries, because it must sample data from the typical nodes first and then collects the results from these nodes. While the single model based algorithm directly collects data from the nodes, the multimodel based algorithm may consume more energy than that of the single model based algorithm. We construct the cost model to estimate the energy consumed by the multimodel based algorithm and the single model based algorithm. By comparing the cost consumed by the two algorithms, we can select a better one to process a query. In this paper, we use the number of messages transmitted by an algorithm to represent the energy consumption.

3.1. Cost Analysis of the Single Model Based Algorithm

Before analyzing the cost of the multimodel based algorithm, we present a single model based algorithm. In the single model based algorithm, a node $n^j$ in the WSN only stores its general model $M_g^j$ in its local storage. After receiving a query from a user, the sink directly broadcasts the query throughout the WSN. A node calculates the probability ${\mathrm{p}\mathrm{r}}_g^j$ that its data satisfies the query with $M_g^j$ . If ${\mathrm{p}\mathrm{r}}_g^j>\rho$ , but the data really collected by the node does not satisfy the range query, the node returns a negative answer to the sink. If ${\mathrm{p}\mathrm{r}}_g^j\le \rho$ , but the data really collected by the node satisfies the range query, the node returns a positive answer to the sink. The node does not return any answer to the sink in other cases.

The energy cost for the single model based query processing algorithm $C_s$ can be estimated by formula (3), in which ${\mathrm{p}\mathrm{r}}_g^j$ is the probability that a node $n^j$ satisfies a query. The first part of formula (3) is the energy cost of broadcasting the query throughout the network. The second part of formula (3) is the expectation of the energy cost that the sink receives answers from the nodes in the WSN:

$$\begin{array}{cc}& C_s=\left|N\right|+{\displaystyle \sum }_{\begin{array}{c}{n}^j\in N\\ {\mathrm{p}\mathrm{r}}_g^j>\rho \end{array}}^{}\left(\mathrm{1}-{\mathrm{p}\mathrm{r}}_g^j\right)\ast {\mathrm{p}\mathrm{l}}^j+{\displaystyle \sum }_{\begin{array}{c}{n}^j\in N\\ {\mathrm{p}\mathrm{r}}_g^j\le \rho \end{array}}^{}{\mathrm{p}\mathrm{r}}_g^j\ast {\mathrm{p}\mathrm{l}}^j.\end{array}$$

(3)

3.2. Cost Analysis of the Multimodel Based Algorithm

We analyze the cost consumed by the multimodel based algorithm. The cost of the multimodel based algorithm is composed of two parts. The first part is the energy cost by the sampling phase, represented by $E_s$ . The second part is the energy cost by the query processing, represented by $E_q$ .

$E_s$ can be estimated as follows. Define an event as follows: “after sampling data from the first j typical nodes, the model selection algorithm can choose the probability model used by the query processing algorithm.” The probability of the event is $(\mathrm{1}-\mathrm{p}\mathrm{r}\hspace{0.17em}{t}^{\mathrm{1}})(\mathrm{1}-\mathrm{p}\mathrm{r}\hspace{0.17em}{t}^{\mathrm{2}})\cdots (\mathrm{1}-\mathrm{p}\mathrm{r}\hspace{0.17em}{t}^{(j-\mathrm{1})})\mathrm{p}\mathrm{r}\hspace{0.17em}{t}^j$ , where $\mathrm{p}\mathrm{r}\hspace{0.17em}{t}^j$ is the probability that the jth typical node can determine the probability model. $\mathrm{p}\mathrm{r}\hspace{0.17em}{t}^j$ can be estimated by

$$\begin{array}{cc}& \mathrm{p}\mathrm{r}\hspace{0.17em}{t}^j=\frac{{\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}}^j}{C\left(m,\mathrm{2}\right)}.\end{array}$$

(4)

If there are m models in the multimodel based range query processing algorithm, there are altogether $C(m,\mathrm{2})$ pairs of models to be distinguished by the typical nodes, where $C(m,\mathrm{2})$ represents the number of 2 combinations of $\{\mathrm{1,2},\dots ,m\}$ . In the typical node selection algorithm (Algorithm 2), ${\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}}^j$ is used to record the number of pairs of models that node $n^j$ can distinguish. Formula (4), which divides ${\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}}^j$ by $C(m,\mathrm{2})$ , is the probability that the jth typical node can distinguish a model from other models, which is used to estimate the probability that the jth typical node can determine a probability model.

The probability that a model is determined by the jth typical node is ${\prod }_{i=\mathrm{1}}^j‍(\mathrm{1}-\mathrm{p}\mathrm{r}\hspace{0.17em}{t}^{i-\mathrm{1}})\mathrm{p}\mathrm{r}\hspace{0.17em}{t}^i$ and the energy cost is $({\sum }_{i=\mathrm{1}}^j‍{\mathrm{p}\mathrm{l}}^i)$ , where ${\mathrm{p}\mathrm{l}}^j$ represents the path length between the sink and the jth typical node. As there are $\left|T\right|$ typical nodes altogether and the sampling process is composed of sending and collecting data, the expectation of the energy consumption of the model selection algorithm $E_s$ is given by

$$\begin{array}{cc}& E_s=\mathrm{2}{\displaystyle \sum }_{j=\mathrm{1}}^{\left|T\right|}‍\left(\left({\displaystyle \prod }_{i=\mathrm{1}}^j‍\left(\mathrm{1}-\mathrm{p}\mathrm{r}\hspace{0.17em}{t}^{i-\mathrm{1}}\right)\mathrm{p}\mathrm{r}\hspace{0.17em}{t}^i\right)\left({\displaystyle \sum }_{i=\mathrm{1}}^j‍{\mathrm{p}\mathrm{l}}^i\right)\right).\end{array}$$

(5)

Let $\mathrm{p}\mathrm{r}\hspace{0.17em}{m}_i$ be the probability that the ith model is chosen by the model selection algorithm and let $E_i$ be the energy consumption of the query processing algorithm of the chosen model. The expectation of the energy cost of the query processing algorithm $E_q$ is given by

$$\begin{array}{cc}& E_q=\left|N\right|+\left({\displaystyle \sum }_{i=\mathrm{1}}^m‍\mathrm{p}\mathrm{r}\hspace{0.17em}{m}_i\ast E_i-\frac{E_s}{\mathrm{2}}\right).\end{array}$$

(6)

The first part of formula (6) is the number of messages by which the sink broadcasts the range query throughout the network. The second part of formula (6) is the expectation of the energy cost by which the sink receives answers from the nodes in the WSN. As the sink has received the data from the typical nodes at the sampling phase, the typical nodes do not transmit their data to sink at the query processing phase and $E_s/\mathrm{2}$ is subtracted from ${\sum }_{i=\mathrm{1}}^m‍\mathrm{p}\mathrm{r}\hspace{0.17em}{m}_i\ast E_i$ . We analyze the estimations for $\mathrm{p}\mathrm{r}\hspace{0.17em}{m}_i$ and $E_i$ next.

As each model is constructed by the vectors contained by a subclass, the number of vectors belonging to a subclass can be used to estimate the probability that the corresponding model is chosen. The larger the number of vectors contained by a subclass is, the higher the probability, that data sampled from the typical nodes belongs to the data range of the subclass, is. Let $\left|H\right|$ be the total number of vectors contained by all subclasses and let $\left|H_i\right|$ be the number of vectors contained by the subclass $H_i$ . The $\mathrm{p}\mathrm{r}\hspace{0.17em}{m}_i$ can be estimated by

$$\begin{array}{cc}& \mathrm{p}\mathrm{r}\hspace{0.17em}{m}_i=\frac{\left|H_i\right|}{\left|H\right|}.\end{array}$$

(7)

Let $A^j$ be the random variable that a node $n^j$ returns answer to the sink. If the answer is yes, $A^j=\mathrm{1}$ . Otherwise, $A^j=\mathrm{0}$ . The expectation of $A^j$ is $(\mathrm{1}-\mathrm{m}\mathrm{a}\mathrm{x}\{{\mathrm{p}\mathrm{r}}_i^j,{\mathrm{p}\mathrm{r}}_g^j\})$ when $\mathrm{m}\mathrm{a}\mathrm{x}\{{\mathrm{p}\mathrm{r}}_i^j,{\mathrm{p}\mathrm{r}}_g^j\}>\rho$ , where ${\mathrm{p}\mathrm{r}}_i^j$ and ${\mathrm{p}\mathrm{r}}_g^j$ are the probabilities calculated by the ith model $M_i^j$ and the general model $M_g^j$ , because the node $n^j$ returns answer only when its real data does not satisfy the query at this time. The expectation of $A^j$ is $\mathrm{m}\mathrm{a}\mathrm{x}\{{\mathrm{p}\mathrm{r}}_i^j,{\mathrm{p}\mathrm{r}}_g^j\}$ when $\mathrm{m}\mathrm{a}\mathrm{x}\{{\mathrm{p}\mathrm{r}}_i^j,{\mathrm{p}\mathrm{r}}_g^j\}\le \rho$ . The number of messages transmitted by the ith model can be calculated in formula (8), where N represents all node sets in the sensor network:

$$\begin{array}{ll}{E}_i& ={\displaystyle \sum }_{\begin{array}{c}{n}^j\in N\\ \max \left\{{\mathrm{p}\mathrm{r}}_i^j,{\mathrm{p}\mathrm{r}}_g^j\right\}>\rho \end{array}}‍\left(\mathrm{1}-\mathrm{m}\mathrm{a}\mathrm{x}\left\{{\mathrm{p}\mathrm{r}}_i^j,{\mathrm{p}\mathrm{r}}_g^j\right\}\right)\ast {\mathrm{p}\mathrm{l}}^j\\ & \hspace{1em}+{\displaystyle \sum }_{\begin{array}{c}{n}^j\in N\\ \max \left\{{\mathrm{p}\mathrm{r}}_i^j,{\mathrm{p}\mathrm{r}}_g^j\right\}\le \rho \end{array}}‍\mathrm{m}\mathrm{a}\mathrm{x}\left\{{\mathrm{p}\mathrm{r}}_i^j,{\mathrm{p}\mathrm{r}}_g^j\right\}\ast {\mathrm{p}\mathrm{l}}^j.\end{array}$$

(8)

The energy cost of the multimodel based query processing algorithm $C_m$ is given by

$$\begin{array}{cc}& C_m=E_s+E_q.\end{array}$$

(9)

3.3. Range Query Processing Algorithm Augmented with the Cost Model

The query processing algorithm augmented with the cost model, given in Algorithm 6, works as follows. The sink estimates the costs $C_m$ and $C_s$ for a particular range query according to formulas (9) and (3). If $C_m<C_s$ , the multimodel based algorithm is adopted. Otherwise, the single model based algorithm is used.

Algorithm 6: The range query processing algorithm augmented with cost model.

Input: $[r_{\mathrm{1}},r_{\mathrm{2}}]$

Output: Q returned by the called algorithm

(1) estimate the cost $C_m$ for the multi-model based query processing algorithm

(2) estimate the cost $C_s$ for the single model query processing algorithm

(3) if  $C_m<C_s$  then

(4)  return Q = call the multi-model based algorithm

(5) else

(6)  return Q = call the single model based algorithm

(7) end if

4. Performance Evaluation

In this section, four experiments were done to verify the performance of the algorithms proposed in this paper. There are three factors that influence the performance of the multimodel based range query processing algorithm, which are the probability threshold ρ, the number of models m, and the coverage threshold σ. In the first three experiments, we test the influence of these factors on the multimodel based algorithm. In the last experiment, we compare the performance of the single model based algorithm, the multimodel based algorithm, and the query processing algorithm augmented with the cost model. The performance of the algorithms is measured by the energy consumption of these algorithms, which is the number of messages transmitted. We adopt the data set collected from 34 sensors deployed in the Intel Berkeley Research lab [20] in our experiments. There are 54 sensors in the data set. As a lot of data of some sensors is lost in the data set and our algorithm needs plenty of historical data to construct probability model, we only select 34 sensors from them. We randomly assign an integer number to each node as its number of hops to the sink, which is used to calculate the energy consumption of each of query processing algorithms.

4.1. Evaluation of the Probability Threshold

In this subsection we evaluate the influence of the probability threshold ρ on the performance of the single model based algorithm (SMA) and the multimodel based range query processing algorithms (MMAs). In this experiment, we change the probability threshold ρ of the algorithms from 0.5 to 0.8. The number of models m and the coverage threshold σ of the MMA are fixed to 4 and 0.8. The sink sends queries with different ranges to the WSN. 10 queries are generated for each range. Figure 3 shows the energy consumption of the SMA and MMA corresponding to different ρ, respectively. The x-axis is the query range sent by a user and y-axis is the number of messages transmitted by the query processing algorithm, which is the average of the number of the messages to process the ten queries for each range.

Figure 3

Influence of ρ on the different algorithms.

The experimental results in Figure 3(a) show that, with the increasing of the ρ, the cost of the SMA increases. The SMA with $\rho =\mathrm{0.5}$ consumes the least energy. The energy consumption of the MMAs with different ρ is shown in Figure 3(b). The results show that the MMA with $\rho =\mathrm{0.6}$ consumes the least energy among all cases. Compared with the SMA, the MMA consumes more energy when the query range is small. For example, the query range is 2, while MMA saves more energy when the query range is large. When the query range is small, the number of nodes satisfying the query is small. The MMA needs to sample data from the typical nodes, so it consumes more energy than the SMA. When the query range is large, the number of nodes satisfying the range query is large and the MMA can select a suitable model to process the query. The saved energy of query processing for MMA is much more than the energy consumed by the data sampling, so the MMA is more efficient than the single based algorithm.

4.2. Evaluation of the Number of Models

In this subsection we evaluate the influence of the number of models m on the performance of the MMA. In this experiment, we set the number of models m of the MMA to 4, 6, and 8. The probability threshold ρ and the coverage threshold σ of the MMA are fixed to 0.6 and 0.8. The sink sends queries with different ranges to the WSN. 10 queries are generated for each range. Figure 4 shows the energy consumption of the MMAs corresponding to different m. The x-axis is the query range sent by a user and y-axis is the number of messages transmitted by the MMA, which is the average of the number of the messages to process the ten queries for each range.

Figure 4

Influence of m on MMA.

The experimental results show that the algorithm with $m=\mathrm{6}$ is the most energy efficient one among all cases. When the number of models is small ( $m=\mathrm{4}$ ), the granularity of the model is coarse. It means that the models constructed when $m=\mathrm{4}$ are not more accurate than those constructed when $m=\mathrm{6}$ , which causes the energy waste. When the number of models is large ( $m=\mathrm{8}$ ), the granularity of the model is too sensitive to the sampled noisy data to select a suitable model for the query, which cause the energy waste.

4.3. Evaluation of the Coverage Threshold

In this subsection we evaluate the influence of the coverage threshold σ on the performance of the MMA. In this experiment, we set the coverage threshold σ of the MMA to 0.8, 0.7, and 0.6, respectively. The probability threshold ρ and the number of models m of the MMA are fixed to 6 and 0.6. The sink sends queries with different ranges to the WSN. 10 queries are generated for each range. Figure 5 shows the energy costs of the MMA corresponding to different σ. The meaning of the x-axis and the y-axis is the same as the first two experiments.

Figure 5

Influence of σ on MMA.

The experimental results show that the energy consumption of the algorithm with $\sigma =\mathrm{0.8}$ consumes the most energy among all cases. If the coverage threshold is large, the data range of a model is large and the intersection of the data ranges for different models becomes large. The probability to select a suitable model is decreased. The energy consumption of the algorithm with $\sigma =\mathrm{0.4}$ is better than that of the algorithm with $\sigma =\mathrm{0.6}$ .

4.4. Comparisons of Energy Consumption

In this subsection we evaluate the performance of the query processing algorithm augmented with the cost model, represented as CMA. In this experiment, we first evaluate which algorithm the CMA selects for different query ranges. Figure 6 shows the results. When the query range is 2, CMA selects the SMA to process the query with $\mathrm{100}\%$ . When the query range is 3, CMA selects SMA with $\mathrm{60}\%$ . With the increasing of the query range, the percent of the SMA selected by CMA decreases. When the query range is 6, the percent of SMA selected by CMA is only $\mathrm{10}\%$ .

Figure 6

Per. of algorithm selected by CMA.

In the second experiment, we compare the energy consumption among the three kinds of algorithms. The parameter for the SMA is $\rho =\mathrm{0.5}$ , which consumes the least energy among all ρs for the SMAs. The parameters for the MMA1 and the CMA1 are $\rho =\mathrm{0.6}$ , $\sigma =\mathrm{0.8}$ , and $m=\mathrm{6}$ . The parameters for the MMA2 and CMA2 are $\rho =\mathrm{0.6}$ , $\sigma =\mathrm{0.4}$ , and $m=\mathrm{6}$ . The results are shown in Figure 7. The meaning of the x-axis and the y-axis is the same as the first two experiments.

Figure 7

Comparison among SMA, MMA, and CMA.

The experimental results show that, when the query range is 2, the MMA1 consumes more energy than SMA. The CMA1 selects SMA as the algorithm to process the query, while the MMA2 consumes less energy than SMA when query range is 2. The CMA2 also selects SMA as the algorithm to process the query, which wastes the energy. For other kinds of query range, the energy cost of the CMA is less than that of the corresponding MMA. Compared with the SMA, the MMA1 can save about $\mathrm{5.8}\%$ energy and the CMA1 can save about $\mathrm{8.7}\%$ energy. The MMA2 can save about $\mathrm{13.6}\%$ energy and CMA2 can save about $\mathrm{13.3}\%$ energy. The results show that the CMA is the energy efficient algorithm on average among all algorithms. Even though the energy consumption of the CMA is not better than the MMA when the MMA is optimal, the energy consumption of the two algorithms is very close. In other cases, the energy consumption of CMA is much better than that of the MMA, so CMA is the best algorithm to be used in reality.

5. Related Work

The DIM [12] divides the whole network into a lot of zones and embeds a k-d tree-like index in the network. There is only one node in each zone, which acts as the index node of the zone. With the k-d tree-like index, events with comparable attribute values are stored nearby and the DIM can fulfill the range query easily. In the comb-needle algorithm [13], when a sensor detects an event, it distributes the data of the events to the nodes in the vertical direction within h hops around it. If a query is sent to the sensor network along multiple lines in the horizontal direction and the distance between any two neighboring lines is smaller than h hops, the query will be transmitted to the event storage node and get the results. The double ruling algorithm [14] distributes the data of the events around the network in a circle. The query also traverses the network in a circle. The double ruling algorithm guarantees that the circle of the query can intersect with all circles of the queried events. The work in [21] constructs a single dimensional address space of sensor nodes through a zigzag traversing such that geographically near nodes are located near in the linear address space. The multidimensional query is transformed into a single dimensional data space using Hilbert space-filling curves. The work in [22] builds a distributed k-d tree based index structure over sensor network and proposes a dynamic programming based methodology to control the granularity of the index tree in an optimized approach. The work in [23] proposes a bloom filter based algorithm to reduce the number of messages transmitted during the procedure of query processing. The work in [24] proposes the bloom filter based approximate algorithms, which can save the energy even further. The work in [25, 26] considers the security problem of the range query. The work in [25] presents a novel spatiotemporal cross-check approach to ensure secure range queries in event-driven two-tier sensor networks. The work in [26] employs the order-preserving symmetric encryption and a novel data structure called authenticity and integrity tree to preserve authenticity and integrity of query results.

6. Conclusions

In this paper, a multimodel based query processing algorithm is proposed to solve the range query problem. The cost model of the multimodel based query processing algorithm is analyzed and a range query processing algorithm augmented with cost model is proposed to save energy even further. The experimental results show that the cost model based algorithm can save $\mathrm{13.3}\%$ energy consumption more than that of the single model based algorithm.