Efficient and fast distributed top-k query protocol in wireless sensor networks
Shaojie Tang, Xufei Mao, Xiangyang Li · 2011
In this paper, we focus on designing efficient query of top-k data produced by sensor nodes in a wireless sensor network (WSN). Assume that we are given a connected WSN of diameter D, consisting of n nodes with maximum node degree Δ. Two different models are studied. In the first model, each node holds a numeric element, the goal is to determine the top-k smallest (or biggest) of these elements from all nodes. In the second model, there are m objects in set ℒ, each node vi, 1 ≤ i ≤ n holds a numeric value Sj(vi) for each object Lj∈ ℒ,1 ≤ j ≤ m, the goal is to find the k objects in ℒ with the k smallest (or biggest) aggregated values /(sj(u1), Sj(v2), ..., Sj(vn)), where f is an aggregation function given in advance. We propose both fast and message efficient methods for conducting top-k queries in the two aforementioned models. Following that we study the minimum delay and messages required by any distributed method for top-k queries in both models. Our analysis shows that our methods are almost optimum. We conducted extensive experiments in both testbed and simulations to study the practical performances of our methods.