Energy Efficient In-Network Data Indexing and Query Processing for Wireless Sensor Networks

Advances in miniaturization of devices equipped with sensing, computing and communication capabilities have spurred significant interest in Wireless Sensor Networks (WSNs) as a tool for distributed data gathering, field estimation, and query processing. WSNs provide the capability of monitoring any given physical phenomena, reporting up to date information to interested users, and reacting to the observed phenomenon using predetermined trigger mechanisms. Energy efficiency has been one of the main concerns in the design and use of WSN based applications, as replenishing power to sensor nodes is impractical or not possible, particularly when they are deployed in harsh environments hostile terrains, or human-unfriendly locations. The focus of this dissertation is the problem of organizing sensed information (also referred to as data indexing) for efficient in-network query processing in context of static as well as mobile networks. Existing solutions for the data indexing problem can be classified from several dimensions. Some of these solutions rely on a centralized approach, where data across the network is transmitted to one sink node, and it is organized at that node. Subsequently, all the queries are processed at this sink node. Such an approach suffers from its poor scalability to large networks and inherent highly non-linear increase in its traffic towards sink node. Decentralized solutions rely on in-network organization of the data. Data organization in these solutions is either optimized for processing of queries related to: 1) the sensed values; or 2) the locations of the sensed values. Therefore application that entertain both types of queries face disparity in efficiency. As for the maintenance of the data-indexing system is concerned, some of the existing solutions rely on transmitting data in raw form across the network, while other solutions construct data models, in order to decrease the amount of transmitted information. The former method gives WSNs the capability of answering queries with same accuracy across the indexing hierarchy, at the cost of a significant increase in the data traffic. The latter category of solutions, however, supports approximate response to queries, providing the benefit of low maintenance cost for the system. In this dissertation, we present an energy and time efficient distributed data indexing system, which supports approximate querying, relying on novel data models that represent the sensed values and sensor nodes locations independently. The presented system is capable of answering different query types with equal efficiency. It also requires minimal maintenance cost, as it employs fixed size update messages across the indexing hierarchy. Our solution does not create traffic congestion around the sink node, and hence, prolongs network life time. The presented abstraction techniques are data structure independent, which gives the flexibility of building the indexing system on a set of widely used binary space partitioning data structures. Our experiments show the efficiency of the presented methods to capture different types of phenomena and answer queries in a better way, compared to the existing state of the art. The presented distributed data indexing system is capable of handling mobility of sensor nodes within the sensed field, without incurring any significant overhead on the energy cost, or query processing performance. It is capable of handling the majority of sensor nodes mobility within their own localities. We also present a novel energy and time efficient methodology for managing the sensor nodes mobility, in order to redistribute resources within the sensed field in response to occurrence of specific events.