Collision-free Communication in Sensor Networks

Sandeep S. Kulkarni, Mahesh Arumugam

June, 2003

Image credit: Unsplash

Abstract

In this paper, we provide a stabilizing solution for collision-free diffusion in sensor networks. Such diffusions are often necessary in sensor networks when information from one sensor needs to be communicated to other sensors that satisfy certain geographic properties. Our solution deals with several difficulties, e.g., unidirectional links, unreliable links, long links, failed sensors, and sensors that are sleeping in order to save energy, that occur in sensor networks. It also ensures that there are no collisions during the diffusion and that the time required for the diffusion is O(D) where D is the diameter of the network. Moreover, while the solution can be applied to an arbitrary topology, it is more suitable for a commonly occurring topology, a two-dimensional grid. We show how our solution for collision-free diffusion can be used for time-division multiplexing (TDM) in sensor networks. TDM ensures that the message communication (other that the messages sent by diffusion) among sensors are collision-free. While collision-free diffusion and time-division multiplexing are interdependent, we show how both these properties can be achieved simultaneously. Our algorithms are stabilizing fault-tolerant, i.e., collision-free diffusion and time-division multiplexing are restored even if the system reaches an arbitrary state where the sensors are corrupted or improperly initialized.

Type

Conference

Publication

In proceedings of the Symposium on Self-Stabilizing Systems