Algorithmic aspects of throughput-delay performance for fast data collection in wireless sensor networks

Convergecast, namely the many-to-one flow of data from a set of sources to a common sink over a tree-based routing topology, is a fundamental communication primitive in wireless sensor networks. For real-time, mission-critical, and high data-rate applications, it is often critical to maximize the aggregated data collection rate (throughput) at the sink node, as well as minimize the time (delay) required for packets to get there. In this thesis, we look into the algorithmic aspects of jointly optimizing both throughput and delay for aggregated data collection in sensor networks. Our contributions are in designing efficient algorithms with provably good, worst-case performance bounds for arbitrarily deployed networks. To the best of our knowledge, we are the first ones to address these two mutually conflicting performance objectives -- throughput and delay -- under the same optimization framework and develop techniques to meet the stringent requirements for fast data collection.;Our approach in addressing the throughput-delay performance trade-off comprises three techniques: (i) multi-channel scheduling, (ii) routing over optimal topologies, and (iii) transmission power control. We exploit the benefits of multiple frequency channels to design efficient TDMA scheduling algorithms, both under the graph-based and the SINR-based interference models. In particular, by decoupling the joint frequency and time slot assignment problem into two separate subproblems of frequency assignment and time slot assignment, we show that our scheduling algorithms have constant factor and logarithmic approximation ratios on the optimal throughput for random geometric graphs as well as for SINR-based models.;In order to further enhance the data collection rate and bound the maximum delay, we study the degree-radius trade-off in spanning trees and propose algorithms under the bicriteria optimization framework. In particular, we construct bounded-degree-minimum-radius spanning trees that have constant factor approximations on the maximum node degree as well as the tree radius. We also show that our multi-channel scheduling algorithms perform much better on such trees in maximizing the aggregated throughput and minimizing the maximum delay, thus achieving the best of both worlds. Lastly, we design efficient, distributed power control schemes for sensor networks deployed in 3-D, where very high density of nodes causes high interference resulting in low network throughput. Our proposed algorithms have low computational overhead compared to the state-of-the-art, and by using local geometric information and tools from computational geometry produce sparse yet connected topologies in 3-D, thus reducing interference and allowing for high throughput.