Wireless sensor networks find many interesting and important applications in both civilian and military domains. A key functionality of such networks is to monitor the environment in which they are deployed, gather relevant data, and report them to end-users. In this thesis, we design communication-efficient protocols for gathering and fusing data in wireless sensor networks for the convergecasting problem in which data from all sensors are destined to a common end-user or sink.
We model problems of maximizing the quality of data (information) received by the sink under various communication constraints as combinatorial optimization problems. We first investigate the problem of maximizing information under energy constraints. When the information resulting from fusing data from multiple sensors is a general function of the information obtained from individual sensors, we develop an optimal solution based on determining a Maximum Weight Independent Set in appropriately constructed graphs.
We then study the class of information functions for which the information resulting from fusing data from multiple sensors is a weighted sum of the information obtained from individual sensors. We investigate this problem in sensor networks with a tree topology, and explicitly model energy, delays, in-network computation for fusing data, channel unreliability, and interference. We develop a distributed, low-complexity optimal solution using a dynamic programming approach when the system has only energy constraints, and no delay constraints. We show that when a deadline constraint is also included, the problem becomes NP-Hard in the strong sense. We develop an approximation algorithm by finding a mapping to a Maximum Weight Increasing Independent Set problem in rectangle graphs.
Finally, we study the problem of minimizing the sum of the queue lengths of all the nodes in a wireless network at each time slot, and for any sample-path traffic arrival pattern under hop-based interference models. We completely characterize the existence of causal sample-path optimal policies in tree structures under a K-hop interference model, and in forest structures under a one-hop interference model. Specifically, we develop causal sample-path optimal scheduling policies in structures in which they exist, and also show that for any other structure, there exists a traffic arrival pattern such that no causal sample-path optimal policy can exist.
We learn that (a) compared to conventional convex optimization models, combinatorial optimization can precisely model general information functions, general error-recovery mechanisms for unreliable channels, and yet result in distributed, low-complexity solutions in a number of cases; (b) explicitly taking channel unreliability and interference into account is crucial in improving the performance of a sensor network; and (c) even though sample-path optimal policies exist for many tree and forest structures, they also do not exist in a large class of trees and forests, and hence it is important to study other metrics for delay.