Collision-free communication in sensor networks.

摘要

Sensors networks are often constrained by limited power and limited communication range. If a sensor receives two messages simultaneously then they collide and both messages become incomprehensible. In this thesis, we present a simple time division multiple access (TDMA) algorithm for assigning time slots to sensors and show that it provides a significant reduction in the number of collisions incurred during communication. We present TDMA algorithms customized for different communication patterns that occur commonly in sensor networks. Our solution deals with several difficulties, e.g., unidirectional links, unreliable links, long links, failed sensors, sensors that are sleeping in order to save energy, and location errors. Our algorithms are self-stabilizing, i.e., TDMA is restored even if the system reaches an arbitrary state where the sensors are corrupted or improperly initialized. Further, we show that our algorithms ensure collision-freedom whereas collision-avoidance protocols like carrier sense multiple access (CSMA) suffer significant number of collisions. Moreover, as an application to our TDMA algorithms, in this thesis; we present transformation algorithms for the sensor network model of computation, called, write-all-with-collision model. Using the transformation algorithms, we transform programs written in this model into programs in other models considered in the literature, and vice versa.