Improved robustness of topology control and routing algorithms for ad-hoc wireless sensor networks

An ad-hoc wireless sensor network (WSN) consists of small autonomous devices embedded in some metric space that can sense their environment, communicate via radio broadcast, and perform local computations. The resources available to each network device are severely limited, which has spawned much research into designing topology control algorithms that produce network topologies that support algorithm execution while requiring low resource utilization. Due to the lack of centralized control, memoryless routing algorithms are commonly used on WSNs. These are algorithms in which routing decisions are made individually by each network node based on the source and destination of a message and on information gathered from other nearby nodes.;Many of the current topology control and rnemoryless routing algorithms make strong assumptions about the amount of geographic information that is known to each network device and are extremely sensitive to even arbitrarily small violations of these assumptions. A common graph theoretic model of a WSN is the Unit Disk Graph (UDG) G = (V,E), where V is the set of network nodes embedded in the Euclidean plane and E represents the set of communication channels between pairs of nodes that are at most distance one apart. This model is popular because of its simplicity and tractability, but it makes several unrealistic assumptions and it cannot model errors in geographic information. The Quasi Unit Disk Graph (QUDG) model alleviates many of the shortcomings of the UDG and provides a more realistic model for WSNs.;The contributions of this dissertation are indicated below. (1) We provide a metric to gauge the sensitivity of topology control algorithms to errors in geographic information. (2) We develop local distributed topology control and routing algorithms that perform correctly under both the UDG and QUDG models. (3) We develop topology control algorithms that use randomness to compensate for errors in geographic information. (4) We develop topology control algorithms that require no geographic information whatsoever to operate correctly. (5) We provide experimental evaluation of several current topology control algorithms as well as a selection of our own algorithms.