Collaborative information processing and query evaluation in wireless sensor networks

Data-centric is one of the most important features that make wireless sensor networks distinct from other types of communication networking systems. A sensor network usually generates massive amount of data, but users only query quite high-level summarized information. Thus, information processing and query evaluation become fundamental problems in sensor networks. The goal of this dissertation is to explore the potentials of sensor networks as collaborative data processing engines. It is expected that in the near future, sensor networks will reactively impact the physical world and interact with end users, who stay in the same physical domain and query the sensor network anytime anywhere. In that context, it requires that sensor nodes collaboratively process information in an ad hoc manner rather than resorting to a centralized base station for post-processing. We investigate essential grand challenges of collaborative processing and query evaluation in wireless sensor networks, and aim to improve the accessibility, interactivity and shareability of sensor data. The first key problem of information processing is how to link users’ selective queries with relevant information. It is challenging because both queries and related data can appear anytime anywhere in the network. Furthermore, a complex query may depend on multi-dimensional data collected by different types of sensors, which themselves can be distributed far apart. Thus, how to match those different types of data is the other aspect of this brokerage problem we need to handle. We proposed algorithms for in-network join of multiple data streams in a sensor network, based on the observation that a sensor network can be viewed as a distributed database system. One of our proposed approaches, viz., the Perpendicular Approach, is load-balanced, and results in substantially prolonging the network lifetime. The Perpendicular Approach is further extended to a general double ruling scheme for information brokerage. The second challenge of information processing comes from the diversity of queries. Some queries request explicit information, e.g., temperature at a particular location. Some may ask for more implicit information, e.g., is there a traffic-free path. Different queries request different processing techniques. Queries for implicit information is especially challenging to be answered, since they usually require global knowledge that is hard to be obtained through sensor’s local view. We investigated on a group tracking problem as a specific example of processing implicit queries. We proposed a light-weight contour tracking algorithm to process implicit contour information and its topological features. This algorithm performs a foundation for further information processing of spatial sensor data. Thirdly, the underlying deployment environment has fundamental effects on high level tasks. Designing protocols for a specific deployment is expensive and time-consuming. Thus, it is highly desirable to have a generic approach to handle sensor fields with complex shapes, and make the design of new protocols transparent to the deployment specifics. We proposed a segmentation algorithm that partitions an irregular sensor field into nicely shaped pieces such that existing algorithms and protocols can be reusable inside each piece. Across the segments, problem dependent structures specify how the segments and data collected in these segments are integrated. The ultimate goal of information processing is to return useful information to users. Thus, it is essential to provide friendly programming paradigm. We propose a deductive framework for programming and querying sensor networks. In this framework, sensor networks work as collaborative data processing engines and allow users to specify with ease the high-level functionality of an application, while hid from the low-level details. All of the above proposed collaborative processing techniques can be fundamentalblocks and integrated into this framework.