Location aware peak value queries in sensor networks

In the applications of wireless sensor networks, the peak values, such as largest sensed values and their locations, are very useful for detecting abnormal events happened in the monitored region. Although the results returned by the traditional top-k queries provide k largest sensed values, they ignore the spatial-correlation of the sensed data so that the locations of the returned values are very close to each other and only tell a small area being abnormal or few number of abnormal events happening. Due to this reason, the Location Aware Peak Value Query, denoted by LAP-(D,k) query, is proposed in this paper. For any given D and k, the LAP-(D,k) query returns k largest sensed values and their locations, and the distance between the any two locations is larger than D. The problem of processing LAP-(D,k) query is proved to be NP-hard, and two distributed approximation algorithms are proposed to solve this problem. One is a distributed greedy algorithm with ratio bound 5.8. The other one is a region partition based algorithm with ratio bound 3. The theoretical analysis and experimental results show that the proposed algorithms have high performance in terms of accuracy and energy consumption.