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

Authors: Guilin Li; Xing Gao; Longjiang Guo; JunCong Lin; Ying Gao; Minghong Liao
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

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


---

## Body

## 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[r1,r2]. 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. Section2 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. LetN be the set of all nodes in the WSN and let |N| 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 Vt=(vt1,vt2,…,vt|N|), where vtj represents the data collected by the jth node nj at the timestamp t. The historical data set H is composed of a set of vectors Vt 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 H1,H2,…,Hm, 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 theith subclass Hi can be used to construct a histogram for each node in the WSN. For Hi, all data belonging to the node nj forms a data set represented as Dij={vtj∣∀Vt∈Hi,vtj∈Vt}. Let vt1j=max{Dij} and vt2j=min{Dij}, which means vt1j and vt2j are the maximum and minimum value of node nj in Dij. The range [vt2j,vt1j) can be equally divided into (vt1j-vt2j+1) bins, whose length is 1. fxj represents the number of data falling into the interval [x,x+1). If the range [vt2j,vt1j) is smaller than 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 setH is divided into m subclasses, m probability models are constructed for each node. The ith probability model of a node nj is represented by Mij. 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 nj is represented as Mgj. There are altogether m+1 probability models for each node, which can be classified into two classes Mj={M1j,M2j,…Mmj} and Mgj.Given a range[a,b], the probability of the data falling in [a,b] calculated by Mij is represented as prij{[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 [vt2j,vt1j) is used to estimate prij{[a,b]} in (1)prija,b=∑x=ab-1fxj∑y=vt2jvt1j-1fyj.


### 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 modelMij∈Mj is selected to make the query processing algorithm be carried out efficiently. Before giving the typical node selection algorithm, we present some definitions.Letμij represent the mean of Dij of the node nj. μij can be calculated by formula (2), where |Hi| represents the number of vectors in the subclass Hi:(2)μij=∑∀vtj∈DijvtjHi.Definition 1 (data range).
The data range of a nodenj, whose data belongs to Dij, is defined as Rij=[μij-x,μij+y] and prij{Rij}≥σ, where σ (0<σ<1) is called the coverage threshold.The rangeRij is a subrange of the total range of the model Mij. The ratio of the area of Rij of the histogram and the total area of the histogram is not less than a threshold σ.Theorem 2.
Thex and y of a data range are integers.Proof.
R
i
j of a node nj is constructed as follows. μij is calculated according to formula (2), which falls into the bin [μij,μij] of the model Mij of the node nj. Initially, we set Rij=[μij,μij] and check whether the ratio of the area of current Rij of the model Mij and the total area of the model Mij is not less than σ. If not, we add all adjacent bins of the current Rij to it, which means one or two bins are added to the current Rij. The Rij is expanded until the coverage threshold σ is reached. As the interval of the histogram is 1, the final Rij is [μij-x,μij+y] where x and y are integers.As there arem subclasses, the node nj has m data ranges, represented by R1j,R2j,…,Rmj. The intersection between the lth and the kth data range of the node nj is represented as Rlkj=Rlj∩Rkj. There are altogether C(m,2) intersections between any two data ranges of a node, where C(m,2) represents the number of the 2 combinations from integer 1 to m.Definition 3 (candidate node).
If an intersectionRlkj of the node nj satisfies the condition length(Rlkj)=min{length(Rlkx)∣x=1,2,…,|N|}, the node nj is called a candidate node. The pair (l,k) is called distinguishable by the candidate node nj. lengh(·) is a function, representing the length of the intersection.For example, in Figure1, there are two nodes n1 and n2 in the WSN. The data collected by them is clustered into two subclasses. The data ranges of n1 are R11=[v11,v21] for subclass 1 and R21=[v31,v41] for subclass 2. The data ranges of n2 are R12=[v12,v22] for subclass 1 and R22=[v32,v42] for subclass 2.Figure 1
Illustration to data range and candidate node.
(a)
Case 1
(b)
Case 2In Figure1(a), the intersection R121=[v11,v21]∩[v31,v41]=∅ and the intersection R122=[v12,v22]∩[v32,v42]=[v32,v22]. As length(R121)=0<length(R122)=v22-v32, according to the definition of the candidate node, n1 is the candidate node and it can distinguish the subclass 1 from the subclass 2. If we sample data vt1 from the node n1 and find vt1∈R11, at this time, the models for every node (M11 and M12) constructed from the subclass 1 are better than those (M21 and M22) constructed from the subclass 2 to process the query.In Figure1(b), length(R121)=v21-v31<length(R122)=v22-v32, which means n1 is the candidate node. When data sampled from n1 falls in [v11,v31] or [v21,v41], the probability models constructed by subclass 1 or subclass 2 are selected. But when the data from n1 falls in [v31,v21], 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 [v32,v22] of n2, the length of [v31,v21] of n1 is much smaller, which means the probability, that a model cannot be determined, is minimized. That is why n1 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 them data ranges Rij(i=1,…,m) for each node. Then the preprocessing algorithm calculates the C(m,2) intersections Rlkj for each node. As there can be multiple nodes satisfying the definition of candidate node for an intersection Rlkj, the preprocessing algorithm calculates a candidate node set CNlk 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 MCN 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 CNlk containing the merged candidate node. The list of the merged candidate node is all the pairs (l,k) of CNlk containing the merged candidate node. Let I be a set of the pairs (l,k), which contains the C(m,2) 2 combinations of the m subclasses. The preprocessing algorithm is given in Algorithm 1.Algorithm 1:The preprocessing algorithm.
Input: N,Hi(1≤i≤m), I
Output: MCN
(1)for each node nj∈Ndo
(2)  calculate them Data Ranges Rij for a node nj
(3)end for
(4)for each node nj∈Ndo
(5)  calculate all the intersectionsRlkj=Rlj∩Rkj for a node nj
(6)end for
(7)for each pair of (l,k)∈Ido
(8)  find the nodenj with the minimum Rlkj among all nodes
(9)  putnj into the candidate node set CNlk
(10)end for
(11) construct the MCN by selecting the unique nodes from allCNlk
(12)for each node nj in the MCNdo
(13)nj→ counter = the number of CNlk containing nj
(14)nj→ list = all the pairs (l,k) of CNlk containing nj
(15)end for
(16)return MCNFor example, Figure2 shows that there are two nodes n1 and n2 in the WSN. The data collected by the two nodes are clustered into three subclasses. The data ranges of n1 for the three subclasses are R11=[v11,v21] for subclass 1, R21=[v31,v41] for subclass 2, and R31=[v51,v61] for subclass 3. The data ranges of n2 for the three subclasses are R12=[v12,v22] for subclass 1, R22=[v32,v42] for subclass 2, and R32=[v52,v62] for subclass 3. Also R121=R11∩R21=∅. In the same way, we can calculate R131=∅, R231=∅, R122=[v52,v22], R132=[v32,v42], and R232=∅. Based on the results, the candidate node set CN12={n1}, because length(R121)=0<length(R122)=v52-v22. Moreover CN13={n1} and CN23={n1,n2}. The MCN contains two nodes {n1,n2}. After merging, the counter of n1 is 3, because all of the candidate node sets contain n1. The list of n1 contains {(1,2),(1,3),(2,3)}. The counter of n2 is 1. The list of n2 only contains {(2,3)}.Figure 2
Illustration to the preprocessing algorithm.Based on the definitions and theMCN 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 MCN 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 MCN. 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 MCN. 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 nj in T has an attribute represented as counterj, which is the number of intersections nj 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≠∅ 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 nodenj to the typical node set T
(5)  setnj→counterj to the current counter of nj in MCN
(6)  remove the selected node from MCN
(7)  remove all the pairs in the list of the selected node fromI
(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  TFor example, after sorting,n1 is selected into the typical node set, because its counter is 3, which is bigger than the counter of n2. The pairs in the list of n1 are removed from I={(1,2),(1,3),(2,3)} and the list of n2. After removing, n2→list=∅, n2→counter=0, and I=∅. As I=∅, Algorithm 2 finished. Otherwise, the candidate nodes left in MCN are sorted and the process is repeated again. In our example, the typical node set T is {n1}. It is obvious in Figure 2 that the data collected from n1 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 nodenj in the WSN stores the m models Mj and a general model Mgj 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 inT 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 CM, is set to {1,2,…,m}. For data vtj, sampled from a typical node nj, the model selection algorithm checks whether vtj∈Rij for all m data ranges of nj. If the vtj∉Rij, the model selection algorithm removes the number i from CM. If there is only one number left in CM, the corresponding model is selected as the suitable model. Otherwise, there will be no number or multiple numbers in CM. 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,Rij(1≤i≤m,1≤j≤|N|)
Output: index of the selected model
(1) set the candidate model set CM to{1,2,…,m}
(2) sort the nodes inT according to their counters in descending order
(3)for each node nj∈T do
(4) sample datavtj from nj
(5)for each Rij of nj do
(6)if vtj∉Rij then
(7)   removei from CM
(8)end if
(9)end for
(10)if |CM|==0  or  |CM|==1 then
(11)   break
(12)end if
(13)end for
(14)if |CM|==1 then
(15)index= the element in CM
(16)else
(17)  construct the vectorVs containing data sampled from the typical nodes
(18)  construct a partial center vectorVi for each subclass
(19)  set thedmin⁡=∞
(20)for 1≤i≤m do
(21)d= the Euclid distance between Vs and Vi
(22)if d≤dmin⁡ then
(23)dmin⁡=d
(24)index=i
(25)end if
(26)end for
(27)end if
(28)return indexAfter 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 nodenj 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 prindexj and the second probability as prgj. The larger one of the two probabilities is chosen as the final probability represented as prfinalj. If prfinalj 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 prfinalj≤ρ, 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.Whenprfinalj>ρ, 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 [r1,r2], index of the selected model index
Output: the result node set Q
(1)index= value returned by Algorithm 3
(2)for ∀nj∈N do
(3)prindexj= the probability of the node satisfying the received range query calculated by the index model
(4)prgeneralj= the probability of the node satisfying the received range query calculated by the general model
(5)if max⁡{prindexj,prgj}>ρ then
(6)   putnj into the result set Q
(7)end if
(8)end for
(9) broadcast the query and theindex throughout the sensor network
(10) collect answers from the nodes in the network
(11)if receive a positive answer from a node nj then
(12)  put ID of nodenj into the result set Q
(13)else if receive a negative answer from a node nj then
(14)  remove the ID of nodenj from the result set Q
(15)end if
(16)return QAlgorithm 5:The model based query processing algorithm for an ordinary node.
Input: [r1,r2], index, vtj
Output: NULL
(1) extract theindex and query range [r1,r2] from the packet received
(2)prindexj= the probability of the node satisfying the received range query calculated by the index model
(3)prgeneralj= the probability of the node satisfying the received range query calculated by the general model
(4)if (max⁡{prindexj,prgeneralj}>ρ) & (vtj∉[r1,r2]) then
(5)  send a negative answer containing the ID of the current node to the sink
(6)else if (max⁡{prindexj,prgeneralj}≤ρ) & (vtj∈[r1,r2]) then
(7)  send a positive answer containing the ID of the current node to the sink
(8)end if


## 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. LetN be the set of all nodes in the WSN and let |N| 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 Vt=(vt1,vt2,…,vt|N|), where vtj represents the data collected by the jth node nj at the timestamp t. The historical data set H is composed of a set of vectors Vt 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 H1,H2,…,Hm, 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 theith subclass Hi can be used to construct a histogram for each node in the WSN. For Hi, all data belonging to the node nj forms a data set represented as Dij={vtj∣∀Vt∈Hi,vtj∈Vt}. Let vt1j=max{Dij} and vt2j=min{Dij}, which means vt1j and vt2j are the maximum and minimum value of node nj in Dij. The range [vt2j,vt1j) can be equally divided into (vt1j-vt2j+1) bins, whose length is 1. fxj represents the number of data falling into the interval [x,x+1). If the range [vt2j,vt1j) is smaller than 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 setH is divided into m subclasses, m probability models are constructed for each node. The ith probability model of a node nj is represented by Mij. 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 nj is represented as Mgj. There are altogether m+1 probability models for each node, which can be classified into two classes Mj={M1j,M2j,…Mmj} and Mgj.Given a range[a,b], the probability of the data falling in [a,b] calculated by Mij is represented as prij{[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 [vt2j,vt1j) is used to estimate prij{[a,b]} in (1)prija,b=∑x=ab-1fxj∑y=vt2jvt1j-1fyj.


## 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 modelMij∈Mj is selected to make the query processing algorithm be carried out efficiently. Before giving the typical node selection algorithm, we present some definitions.Letμij represent the mean of Dij of the node nj. μij can be calculated by formula (2), where |Hi| represents the number of vectors in the subclass Hi:(2)μij=∑∀vtj∈DijvtjHi.Definition 1 (data range).
The data range of a nodenj, whose data belongs to Dij, is defined as Rij=[μij-x,μij+y] and prij{Rij}≥σ, where σ (0<σ<1) is called the coverage threshold.The rangeRij is a subrange of the total range of the model Mij. The ratio of the area of Rij of the histogram and the total area of the histogram is not less than a threshold σ.Theorem 2.
Thex and y of a data range are integers.Proof.
R
i
j of a node nj is constructed as follows. μij is calculated according to formula (2), which falls into the bin [μij,μij] of the model Mij of the node nj. Initially, we set Rij=[μij,μij] and check whether the ratio of the area of current Rij of the model Mij and the total area of the model Mij is not less than σ. If not, we add all adjacent bins of the current Rij to it, which means one or two bins are added to the current Rij. The Rij is expanded until the coverage threshold σ is reached. As the interval of the histogram is 1, the final Rij is [μij-x,μij+y] where x and y are integers.As there arem subclasses, the node nj has m data ranges, represented by R1j,R2j,…,Rmj. The intersection between the lth and the kth data range of the node nj is represented as Rlkj=Rlj∩Rkj. There are altogether C(m,2) intersections between any two data ranges of a node, where C(m,2) represents the number of the 2 combinations from integer 1 to m.Definition 3 (candidate node).
If an intersectionRlkj of the node nj satisfies the condition length(Rlkj)=min{length(Rlkx)∣x=1,2,…,|N|}, the node nj is called a candidate node. The pair (l,k) is called distinguishable by the candidate node nj. lengh(·) is a function, representing the length of the intersection.For example, in Figure1, there are two nodes n1 and n2 in the WSN. The data collected by them is clustered into two subclasses. The data ranges of n1 are R11=[v11,v21] for subclass 1 and R21=[v31,v41] for subclass 2. The data ranges of n2 are R12=[v12,v22] for subclass 1 and R22=[v32,v42] for subclass 2.Figure 1
Illustration to data range and candidate node.
(a)
Case 1
(b)
Case 2In Figure1(a), the intersection R121=[v11,v21]∩[v31,v41]=∅ and the intersection R122=[v12,v22]∩[v32,v42]=[v32,v22]. As length(R121)=0<length(R122)=v22-v32, according to the definition of the candidate node, n1 is the candidate node and it can distinguish the subclass 1 from the subclass 2. If we sample data vt1 from the node n1 and find vt1∈R11, at this time, the models for every node (M11 and M12) constructed from the subclass 1 are better than those (M21 and M22) constructed from the subclass 2 to process the query.In Figure1(b), length(R121)=v21-v31<length(R122)=v22-v32, which means n1 is the candidate node. When data sampled from n1 falls in [v11,v31] or [v21,v41], the probability models constructed by subclass 1 or subclass 2 are selected. But when the data from n1 falls in [v31,v21], 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 [v32,v22] of n2, the length of [v31,v21] of n1 is much smaller, which means the probability, that a model cannot be determined, is minimized. That is why n1 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 them data ranges Rij(i=1,…,m) for each node. Then the preprocessing algorithm calculates the C(m,2) intersections Rlkj for each node. As there can be multiple nodes satisfying the definition of candidate node for an intersection Rlkj, the preprocessing algorithm calculates a candidate node set CNlk 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 MCN 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 CNlk containing the merged candidate node. The list of the merged candidate node is all the pairs (l,k) of CNlk containing the merged candidate node. Let I be a set of the pairs (l,k), which contains the C(m,2) 2 combinations of the m subclasses. The preprocessing algorithm is given in Algorithm 1.Algorithm 1:The preprocessing algorithm.
Input: N,Hi(1≤i≤m), I
Output: MCN
(1)for each node nj∈Ndo
(2)  calculate them Data Ranges Rij for a node nj
(3)end for
(4)for each node nj∈Ndo
(5)  calculate all the intersectionsRlkj=Rlj∩Rkj for a node nj
(6)end for
(7)for each pair of (l,k)∈Ido
(8)  find the nodenj with the minimum Rlkj among all nodes
(9)  putnj into the candidate node set CNlk
(10)end for
(11) construct the MCN by selecting the unique nodes from allCNlk
(12)for each node nj in the MCNdo
(13)nj→ counter = the number of CNlk containing nj
(14)nj→ list = all the pairs (l,k) of CNlk containing nj
(15)end for
(16)return MCNFor example, Figure2 shows that there are two nodes n1 and n2 in the WSN. The data collected by the two nodes are clustered into three subclasses. The data ranges of n1 for the three subclasses are R11=[v11,v21] for subclass 1, R21=[v31,v41] for subclass 2, and R31=[v51,v61] for subclass 3. The data ranges of n2 for the three subclasses are R12=[v12,v22] for subclass 1, R22=[v32,v42] for subclass 2, and R32=[v52,v62] for subclass 3. Also R121=R11∩R21=∅. In the same way, we can calculate R131=∅, R231=∅, R122=[v52,v22], R132=[v32,v42], and R232=∅. Based on the results, the candidate node set CN12={n1}, because length(R121)=0<length(R122)=v52-v22. Moreover CN13={n1} and CN23={n1,n2}. The MCN contains two nodes {n1,n2}. After merging, the counter of n1 is 3, because all of the candidate node sets contain n1. The list of n1 contains {(1,2),(1,3),(2,3)}. The counter of n2 is 1. The list of n2 only contains {(2,3)}.Figure 2
Illustration to the preprocessing algorithm.Based on the definitions and theMCN 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 MCN 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 MCN. 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 MCN. 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 nj in T has an attribute represented as counterj, which is the number of intersections nj 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≠∅ 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 nodenj to the typical node set T
(5)  setnj→counterj to the current counter of nj in MCN
(6)  remove the selected node from MCN
(7)  remove all the pairs in the list of the selected node fromI
(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  TFor example, after sorting,n1 is selected into the typical node set, because its counter is 3, which is bigger than the counter of n2. The pairs in the list of n1 are removed from I={(1,2),(1,3),(2,3)} and the list of n2. After removing, n2→list=∅, n2→counter=0, and I=∅. As I=∅, Algorithm 2 finished. Otherwise, the candidate nodes left in MCN are sorted and the process is repeated again. In our example, the typical node set T is {n1}. It is obvious in Figure 2 that the data collected from n1 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 nodenj in the WSN stores the m models Mj and a general model Mgj 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 inT 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 CM, is set to {1,2,…,m}. For data vtj, sampled from a typical node nj, the model selection algorithm checks whether vtj∈Rij for all m data ranges of nj. If the vtj∉Rij, the model selection algorithm removes the number i from CM. If there is only one number left in CM, the corresponding model is selected as the suitable model. Otherwise, there will be no number or multiple numbers in CM. 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,Rij(1≤i≤m,1≤j≤|N|)
Output: index of the selected model
(1) set the candidate model set CM to{1,2,…,m}
(2) sort the nodes inT according to their counters in descending order
(3)for each node nj∈T do
(4) sample datavtj from nj
(5)for each Rij of nj do
(6)if vtj∉Rij then
(7)   removei from CM
(8)end if
(9)end for
(10)if |CM|==0  or  |CM|==1 then
(11)   break
(12)end if
(13)end for
(14)if |CM|==1 then
(15)index= the element in CM
(16)else
(17)  construct the vectorVs containing data sampled from the typical nodes
(18)  construct a partial center vectorVi for each subclass
(19)  set thedmin⁡=∞
(20)for 1≤i≤m do
(21)d= the Euclid distance between Vs and Vi
(22)if d≤dmin⁡ then
(23)dmin⁡=d
(24)index=i
(25)end if
(26)end for
(27)end if
(28)return indexAfter 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 nodenj 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 prindexj and the second probability as prgj. The larger one of the two probabilities is chosen as the final probability represented as prfinalj. If prfinalj 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 prfinalj≤ρ, 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.Whenprfinalj>ρ, 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 [r1,r2], index of the selected model index
Output: the result node set Q
(1)index= value returned by Algorithm 3
(2)for ∀nj∈N do
(3)prindexj= the probability of the node satisfying the received range query calculated by the index model
(4)prgeneralj= the probability of the node satisfying the received range query calculated by the general model
(5)if max⁡{prindexj,prgj}>ρ then
(6)   putnj into the result set Q
(7)end if
(8)end for
(9) broadcast the query and theindex throughout the sensor network
(10) collect answers from the nodes in the network
(11)if receive a positive answer from a node nj then
(12)  put ID of nodenj into the result set Q
(13)else if receive a negative answer from a node nj then
(14)  remove the ID of nodenj from the result set Q
(15)end if
(16)return QAlgorithm 5:The model based query processing algorithm for an ordinary node.
Input: [r1,r2], index, vtj
Output: NULL
(1) extract theindex and query range [r1,r2] from the packet received
(2)prindexj= the probability of the node satisfying the received range query calculated by the index model
(3)prgeneralj= the probability of the node satisfying the received range query calculated by the general model
(4)if (max⁡{prindexj,prgeneralj}>ρ) & (vtj∉[r1,r2]) then
(5)  send a negative answer containing the ID of the current node to the sink
(6)else if (max⁡{prindexj,prgeneralj}≤ρ) & (vtj∈[r1,r2]) 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 nodenj in the WSN only stores its general model Mgj 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 prgj that its data satisfies the query with Mgj. If prgj>ρ, but the data really collected by the node does not satisfy the range query, the node returns a negative answer to the sink. If prgj≤ρ, 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 algorithmCs can be estimated by formula (3), in which prgj is the probability that a node nj 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:(3)Cs=N+∑nj∈Nprgj>ρ1-prgj∗plj+∑nj∈Nprgj≤ρprgj∗plj.


### 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 byEs. The second part is the energy cost by the query processing, represented by Eq.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 (1-prt1)(1-prt2)⋯(1-prt(j-1))prtj, where prtj is the probability that the jth typical node can determine the probability model. prtj can be estimated by(4)prtj=counterjCm,2.If there arem models in the multimodel based range query processing algorithm, there are altogether C(m,2) pairs of models to be distinguished by the typical nodes, where C(m,2) represents the number of 2 combinations of {1,2,…,m}. In the typical node selection algorithm (Algorithm 2), counterj is used to record the number of pairs of models that node nj can distinguish. Formula (4), which divides counterj by C(m,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 thejth typical node is ∏i=1j‍(1-prti-1)prti and the energy cost is (∑i=1j‍pli), where plj represents the path length between the sink and the jth typical node. As there are |T| 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 Es is given by (5)Es=2∑j=1T‍∏i=1j‍1-prti-1prti∑i=1j‍pli.Letprmi be the probability that the ith model is chosen by the model selection algorithm and let Ei be the energy consumption of the query processing algorithm of the chosen model. The expectation of the energy cost of the query processing algorithm Eq is given by (6)Eq=N+∑i=1m‍prmi∗Ei-Es2.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 Es/2 is subtracted from ∑i=1m‍prmi∗Ei. We analyze the estimations for prmi and Ei 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|H| be the total number of vectors contained by all subclasses and let |Hi| be the number of vectors contained by the subclass Hi. The prmi can be estimated by (7)prmi=HiH.LetAj be the random variable that a node nj returns answer to the sink. If the answer is yes, Aj=1. Otherwise, Aj=0. The expectation of Aj is (1-max{prij,prgj}) when max{prij,prgj}>ρ, where prij and prgj are the probabilities calculated by the ith model Mij and the general model Mgj, because the node nj returns answer only when its real data does not satisfy the query at this time. The expectation of Aj is max{prij,prgj} when max{prij,prgj}≤ρ. 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:(8)Ei=∑nj∈Nmax⁡prij,prgj>ρ‍1-maxprij,prgj∗plj+∑nj∈Nmax⁡prij,prgj≤ρ‍maxprij,prgj∗plj.The energy cost of the multimodel based query processing algorithmCm is given by (9)Cm=Es+Eq.


### 3.3. Range Query Processing Algorithm Augmented with the Cost Model

The query processing algorithm augmented with the cost model, given in Algorithm6, works as follows. The sink estimates the costs Cm and Cs for a particular range query according to formulas (9) and (3). If Cm<Cs, 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: [r1,r2]
Output: Q returned by the called algorithm
(1) estimate the costCm for the multi-model based query processing algorithm
(2) estimate the costCs for the single model query processing algorithm
(3)if Cm<Cs then
(4)return Q = call the multi-model based algorithm
(5)else
(6)return Q = call the single model based algorithm
(7)end if


## 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 nodenj in the WSN only stores its general model Mgj 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 prgj that its data satisfies the query with Mgj. If prgj>ρ, but the data really collected by the node does not satisfy the range query, the node returns a negative answer to the sink. If prgj≤ρ, 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 algorithmCs can be estimated by formula (3), in which prgj is the probability that a node nj 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:(3)Cs=N+∑nj∈Nprgj>ρ1-prgj∗plj+∑nj∈Nprgj≤ρprgj∗plj.


## 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 byEs. The second part is the energy cost by the query processing, represented by Eq.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 (1-prt1)(1-prt2)⋯(1-prt(j-1))prtj, where prtj is the probability that the jth typical node can determine the probability model. prtj can be estimated by(4)prtj=counterjCm,2.If there arem models in the multimodel based range query processing algorithm, there are altogether C(m,2) pairs of models to be distinguished by the typical nodes, where C(m,2) represents the number of 2 combinations of {1,2,…,m}. In the typical node selection algorithm (Algorithm 2), counterj is used to record the number of pairs of models that node nj can distinguish. Formula (4), which divides counterj by C(m,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 thejth typical node is ∏i=1j‍(1-prti-1)prti and the energy cost is (∑i=1j‍pli), where plj represents the path length between the sink and the jth typical node. As there are |T| 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 Es is given by (5)Es=2∑j=1T‍∏i=1j‍1-prti-1prti∑i=1j‍pli.Letprmi be the probability that the ith model is chosen by the model selection algorithm and let Ei be the energy consumption of the query processing algorithm of the chosen model. The expectation of the energy cost of the query processing algorithm Eq is given by (6)Eq=N+∑i=1m‍prmi∗Ei-Es2.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 Es/2 is subtracted from ∑i=1m‍prmi∗Ei. We analyze the estimations for prmi and Ei 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|H| be the total number of vectors contained by all subclasses and let |Hi| be the number of vectors contained by the subclass Hi. The prmi can be estimated by (7)prmi=HiH.LetAj be the random variable that a node nj returns answer to the sink. If the answer is yes, Aj=1. Otherwise, Aj=0. The expectation of Aj is (1-max{prij,prgj}) when max{prij,prgj}>ρ, where prij and prgj are the probabilities calculated by the ith model Mij and the general model Mgj, because the node nj returns answer only when its real data does not satisfy the query at this time. The expectation of Aj is max{prij,prgj} when max{prij,prgj}≤ρ. 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:(8)Ei=∑nj∈Nmax⁡prij,prgj>ρ‍1-maxprij,prgj∗plj+∑nj∈Nmax⁡prij,prgj≤ρ‍maxprij,prgj∗plj.The energy cost of the multimodel based query processing algorithmCm is given by (9)Cm=Es+Eq.


## 3.3. Range Query Processing Algorithm Augmented with the Cost Model

The query processing algorithm augmented with the cost model, given in Algorithm6, works as follows. The sink estimates the costs Cm and Cs for a particular range query according to formulas (9) and (3). If Cm<Cs, 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: [r1,r2]
Output: Q returned by the called algorithm
(1) estimate the costCm for the multi-model based query processing algorithm
(2) estimate the costCs for the single model query processing algorithm
(3)if Cm<Cs 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.
(a)
On the SMA
(b)
On the MMAThe experimental results in Figure3(a) show that, with the increasing of the ρ, the cost of the SMA increases. The SMA with ρ=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 ρ=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 modelsm 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 ofm on MMA.The experimental results show that the algorithm withm=6 is the most energy efficient one among all cases. When the number of models is small (m=4), the granularity of the model is coarse. It means that the models constructed when m=4 are not more accurate than those constructed when m=6, which causes the energy waste. When the number of models is large (m=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σ=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 σ=0.4 is better than that of the algorithm with σ=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. Figure6 shows the results. When the query range is 2, CMA selects the SMA to process the query with 100%. When the query range is 3, CMA selects SMA with 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 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ρ=0.5, which consumes the least energy among all ρs for the SMAs. The parameters for the MMA1 and the CMA1 are ρ=0.6, σ=0.8, and m=6. The parameters for the MMA2 and CMA2 are ρ=0.6, σ=0.4, and m=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 about5.8% energy and the CMA1 can save about 8.7% energy. The MMA2 can save about 13.6% energy and CMA2 can save about 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.


## 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.
(a)
On the SMA
(b)
On the MMAThe experimental results in Figure3(a) show that, with the increasing of the ρ, the cost of the SMA increases. The SMA with ρ=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 ρ=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 modelsm 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 ofm on MMA.The experimental results show that the algorithm withm=6 is the most energy efficient one among all cases. When the number of models is small (m=4), the granularity of the model is coarse. It means that the models constructed when m=4 are not more accurate than those constructed when m=6, which causes the energy waste. When the number of models is large (m=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σ=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 σ=0.4 is better than that of the algorithm with σ=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. Figure6 shows the results. When the query range is 2, CMA selects the SMA to process the query with 100%. When the query range is 3, CMA selects SMA with 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 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ρ=0.5, which consumes the least energy among all ρs for the SMAs. The parameters for the MMA1 and the CMA1 are ρ=0.6, σ=0.8, and m=6. The parameters for the MMA2 and CMA2 are ρ=0.6, σ=0.4, and m=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 about5.8% energy and the CMA1 can save about 8.7% energy. The MMA2 can save about 13.6% energy and CMA2 can save about 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 save13.3% energy consumption more than that of the single model based algorithm.



---

*Source: 403267-2015-08-30.xml*