Search

We consider the problem of tracking quantiles and range countings in wireless sensor networks. The quantiles and range countings are two important aggregations to characterize a data distribution. Let S ( t ) = ( d 1 , … , d n ) denote the multi-set of sensory data that have arrived until time t , which is a sequence of data orderly collected by nodes s 1 , s 2 , … , s k . One of our goals is to continuously track ϵ -approximate ϕ -quantiles ( 0 ≤ ϕ ≤ 1 ) of S ( t ) for all ϕ 's with efficient total communication cost and balanced individual communication cost. The other goal is to track ( ϵ , δ ) -approximate range countings satisfying the requirement of arbitrary precision specified by different users. In this paper, a deterministic tracking algorithm based on a dynamic binary tree is proposed to track ϵ -approximate ϕ -quantiles, whose total communication cost is O ( k / ϵ ⋅ log ⁡ n ⋅ log 2 ⁡ ( 1 / ϵ ) ) , where k is the number of the nodes in a network, n is the total number of the data, and ϵ is the user-specified approximation error. For range countings, a Bernoulli sampling based algorithm is proposed to track ( ϵ , δ ) -approximate range countings, whose total communication cost is O ( 2 ϵ 2 ln ⁡ 2 1 − 1 − δ + n c ) , where δ is the user-specified error probability, n c is the number of clusters. [ABSTRACT FROM AUTHOR]