Sensor networks, that consist of potentially several thousands of nodes each with sensing (heat, sound, light, magnetism, etc.) and wireless communication capabilities, provide great opportunities for monitoring spatial information about a region of interest. Although spatial query execution has been studied extensively in the context of database systems (e.g., indexing technologies), these solutions are not directly applicable in the context of sensor networks due to the decentralized nature of the sensor networks and the limited computational power and energy scarcity of individual sensor nodes.

In this paper, we present a peer-to-peer indexing structure, namely peer-tree, in order to address the problem of energy- and time-ef.cient execution of spatial queries (such as nearest-neighbor queries) in sensor networks. Loosely speaking, our peer-tree structure can be interpreted as a peer-to-peer version of the centralized R-tree index structure. Using the peer-tree as a building block, we present a peer-to-peer query processing model where a query can be posed in any node of the network without the need of a central server. For achieving minimal energy consumption and minimal response time, our query processing model ensures that only the relevant nodes for the correct execution of a query are involved in the query execution.