Services in Sensor Networks

Jana van Greunen, M.S. Thesis

This research presents algorithms for three sensor network services. The services are localization, synchronization, and power management (duty-cycling). The algorithms were developed with the following design principles in mind: low energy consumption, robustness to changing environment, adaptation and optimization to dynamically varying network configurations and requirements. For the first service, localization, several existing localization methods are evaluated in accordance with the design principles. A particular method, the start-up and refinement algorithm, is extended to include a real-time estimate of location error. Second, the algorithm developed for synchronization relies on the construction of a spanning tree across the network. Once the spanning tree structure is constructed, nodes perform pair-wise synchronization along the edges of this tree. The tree-structure reduces the number of pair-wise synchronizations that need to be performed and is thus energy-efficient. The tree can be constructed in a centralized (reference node initiated) or distributed (sensor node initiated) fashion. Last, the power management algorithm utilizes randomization and equivalence (nodes in the network can all perform the same functionality) to reduce the coordination between nodes and thus the communication overhead of the algorithm. The power management algorithm is presented in the context of a routing problem. That is, the nodes perform duty cycling (sleeping) and wake up to route packets. Equivalent nodes need to wake up often enough to ensure that the packets do not experience large routing delays. The randomization of the nodes' sleeping patterns provides robustness to changes in the environment (node density and fading channels). The randomization also allows equivalent nodes to estimate the aggregate wake-up rate and adapt their individual wake-up rates to the current network configuration.