Accession Number:

ADA455715

Title:

Self-Stabilizing Deterministic TDMA for Sensor Networks

Descriptive Note:

Corporate Author:

MICHIGAN STATE UNIV EAST LANSING DEPT OF COMPUTER SCIENCE/ENGINEERING

Report Date:

2006-01-01

Pagination or Media Count:

22.0

Abstract:

An algorithm for time division multiple access TDMA is desirable in sensor networks for energy management, as it allows a sensor to reduce the amount of idle listening. Also, TDMA has been found to be applicable in converting existing distributed algorithms into a model that is consistent with sensor networks. Such a TDMA service needs to be self-stabilizing so that in the event of corruption of assigned slots and clock drift, it recovers to states from where TDMA slots are consistent. Previous self-stabilizing solutions for TDMA are either randomized or assume that the topology is known upfront and cannot change. Thus, the question of feasibility of self-stabilizing deterministic TDMA algorithm where topology is unknown remains open. In this paper, we present a self-stabilizing, deterministic algorithm for TDMA in networks where a sensor is aware of only its neighbors. We derive this algorithm by systematically reusing a graph traversal algorithm. Furthermore, we also discuss the optimizations to improve bandwidth utilization and recovery from corrupted slots.

Subject Categories:

  • Theoretical Mathematics
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE