Browse Theses

The dynamic and lossy nature of wireless communication poses major challenges to reliable, self-organizing multihop networks. Non-ideal link characteristics are especially problematic with the primitive, low-power radio transceivers found in sensor networks and raise new issues that routing protocols must address. We redefine the basic notion of wireless connectivity in terms of probabilistic links, and demonstrate that link statistics can be captured dynamically through an efficient yet adaptive link estimator. This probabilistic notion of connectivity changes the usual concept of a neighbor and introduces new problems with neighborhood management: the neighbor table on a sensor node is of fixed size and cannot always be used to gather link statistics about all neighbors, yet the process of selecting the most competitive neighbors requires a comparison with the link statistics of those neighbors that are not in the table. Together, link estimation and neighborhood management build a probabilistic connectivity graph which can be exploited by a routing algorithm to increase reliability. Together, these three processes constitute our holistic approach to routing. We study and evaluate link estimation, neighborhood table management, and reliable routing protocol techniques, focusing on the many-to-one, periodic data collection workload commonly found in sensor network applications today. Our final system uses a variant of an exponentially weighted moving average estimator, frequency based table management, and minimum transmission cost-based routing. Our analysis ranges from large-scale, high-level simulations to in-depth empirical experiments and emphasizes the intricate interactions between the routing topology and the underlying connectivity graph, which underscores the need for a whole-system approach to the problem of routing in wireless sensor networks.