Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10]


Journal of Information Science and Engineering, Vol. 28 No. 6, pp. 1105-1128 (November 2012)

Localized and Incremental Monitoring of Reverse Nearest Neighbor Queries in Wireless Sensor Networks*

Department of Computer Science
Korea Advanced Institute of Science and Technology
Daejeon, 305-701 Korea
E-mail: {mhthanh,mhkim}

Reverse nearest neighbor (RNN) monitoring queries are useful in many object tracking scenarios using wireless sensor networks. However, there is still no research work addressing RNN monitoring queries in this environment. In addition, even though some algorithms have been proposed to process RNN monitoring queries in other environments, they are not quite appropriate for wireless sensor networks. The reason is that these algorithms all adopt centralized processing which requires all object locations sent to a central server to be processed further, thus exhausts quickly the sensor nodes' limited power. Therefore, in this paper, we study the problem of processing RNN monitoring queries in wireless sensor networks. We consider both two cases of RNN monitoring queries, namely monochromatic and bichromatic, and develop for each case a localized and incremental monitoring algorithm. Our main ideas are to localize the searching task to only relevant sensor nodes near the query point and to establish and incrementally maintain some restricted monitoring areas for each query. During the major part of the query lifetime, only object location updates from these areas instead of the whole space need to be collected and processed. Extensive experimental results show that the proposed algorithms are scalable and an order of magnitude more efficient than the centralized ones in terms of energy consumption.

Keywords: distributed database, wireless sensor network, continuous query processing, reverse nearest neighbor query, monitoring algorithm

Full Text () Retrieve PDF document (201211_08.pdf)

Received December 8, 2010; revised March 9, 2011; accepted April 13, 2011.
Communicated by Chung-Ta King.
* This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MEST) (No. 2010-0018865).