Distributed multi-scale data processing for sensor networks

Wireless sensor networks provide a challenging application area for signal processing. Sensor networks are collections of small, battery-operated devices called sensor nodes, each of which is capable of sensing data, processing data with an onboard microprocessor, and sharing data with other nodes by forming a wireless, multi-hop network. Since communication power consumption in nodes typically dominates over sensing and processing power consumption by orders of magnitude, it is often more efficient to pose questions on measured data in a distributed fashion within the network than it is to collect data at a single location for centralized processing. Under this model, nodes collaborate with each other in some neighborhood using localized communications and in-network processing to compute answers to users' questions, which are then sent over more costly, long-haul links to a data sink. In this thesis, our contributions to distributed data processing in sensor networks fall into two main categories. First, we develop a new class of multi-scale distributed data processing algorithms based on distributed wavelet analysis. Specifically, we formulate and analyze a novel, distributed wavelet transform (WT) suited to the irregular-grid data samples expected in real-world sensor network deployments. The WT replaces node measurements with a set of wavelet coefficients that are more sparse than the original data and enable subsequent distributed processing. We then develop and analyze protocols for wavelet-based processing, including distributed, lossy compression and distributed de-noising of node measurements. Our second main contribution is the development of a network application programming interface (API) for distributed data processing in sensor networks. Guided by our experience in implementing the distributed WT in a real sensor network, we realize that a fundamental set of communication patterns underlie the bulk of distributed algorithms. Expanding our scope past the distributed WT, we survey all such algorithms proposed in the proceedings of the Information Processing in Sensor Networks (IPSN) conference to extract the communication patterns. Using the survey results, we design a network API composed of four main families of calls. Its implementation, in ongoing work, will enable easy and invaluable prototyping of distributed processing algorithms in real sensor network hardware