A Distributed and Deterministic TDMA Algorithm for Write-All-With-Collision Model - Computer Science > Operating SystemsReport as inadecuate




A Distributed and Deterministic TDMA Algorithm for Write-All-With-Collision Model - Computer Science > Operating Systems - Download this document for free, or read online. Document in PDF available to download.

Abstract: Several self-stabilizing time division multiple access TDMA algorithms areproposed for sensor networks. In addition to providing a collision-freecommunication service, such algorithms enable the transformation of programswritten in abstract models considered in distributed computing literature intoa model consistent with sensor networks, i.e., write all with collision WACmodel. Existing TDMA slot assignment algorithms have one or more of thefollowing properties: i compute slots using a randomized algorithm, iiassume that the topology is known upfront, and-or iii assign slotssequentially. If these algorithms are used to transform abstract programs intoprograms in WAC model then the transformed programs are probabilisticallycorrect, do not allow the addition of new nodes, and-or converge in asequential fashion. In this paper, we propose a self-stabilizing deterministicTDMA algorithm where a sensor is aware of only its neighbors. We show that theslots are assigned to the sensors in a concurrent fashion and starting fromarbitrary initial states, the algorithm converges to states wherecollision-free communication among the sensors is restored. Moreover, thisalgorithm facilitates the transformation of abstract programs into programs inWAC model that are deterministically correct.



Author: Mahesh Arumugam

Source: https://arxiv.org/







Related documents