| Wireless Sensor Networks (WSNs) are an ever growing technology with a wide range of applications in civilian and military domains. In 2009, for instance, HP announced a project that aims to be a "Central Nervous System for the Earth (CeNSE)" [34] which consists in a research and development program to build a planetwide sensing network, using billions of "tiny, cheap, tough and exquisitely sensitive detectors".;Minimizing energy expenditure without compromising the quality of essential services such as area coverage and efficient routing remain, however, a major design challenge that needs to be overcome for this technology to gain more ground in the real world.;In this thesis, we study these problems in WSNs. Specifically, for a dense deployment of sensors modeled as a random geometric graph of minimum degree delta, we introduce efficient algorithms both centralized and distributed for selecting (delta + 1) backbones with disjoint node sets that are each independent and fully (or nearly) dominating. A backbone consists in a subset of nodes of the network which are responsible of relaying messages throughout the network. The backbone sets are first determined by graph coloring employing either topology or geometry, then to support efficient routing, each set is extended to constitute a connected, constant density, planar backbone by using localized 2-hop relay and Gabriel Graph rules. For large networks, the resulting backbones are shown to each cover typically over 99% of the nodes, with at least 1 5 of the sets being fully dominating. We propose a backbone model, derived from the properties of triangulated planar graphs, to characterize the connectivity quality of the resulting partitions. We also show that the relatively few vertices not covered by all (delta + 1) backbones are covered by most of the backbones, therefore, backbone rotation in a wireless sensor network would reach all sensors sufficiently frequently for data gathering. The proposed distributed algorithms are shown to be inherently localized with constant convergence times. We further propose a novel method of pairing up backbones to obtain multiple efficient network routing structures with the following desirable properties: 2-colorability, sparseness, planarity, and bounded degree. We confirm the effectiveness of our solution through analysis and extensive simulation. Finally, we study experimentally several useful properties of "domination" in random geometric graphs by means of integer linear programs and coloring heuristics.;In this thesis, we establish several interesting theoretical results and bounds for these problems which we further validate by comprehensive simulations of the proposed algorithms. These empirical results indicate that the algorithms may be implemented in real-world applications with certain practical guarantees in terms of solution optimality and balanced energy consumption among the sensors. |
