Oriented Edge Colorings and Link Scheduling in Sensor Networks

Ted  Herman; Sriram  Pemmaraju; Imran Pirwani

1st International IEEE/ACM Workshop on Software for Sensor Networks

Research Article

Oriented Edge Colorings and Link Scheduling in Sensor Networks

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.1109/COMSWA.2006.1665226,
    author={Ted  Herman and Sriram  Pemmaraju and Imran Pirwani},
    title={Oriented Edge Colorings and Link Scheduling in Sensor Networks},
    proceedings={1st International IEEE/ACM Workshop on Software for Sensor Networks},
    publisher={IEEE},
    proceedings_a={SENSORWARE},
    year={2006},
    month={8},
    keywords={edge-coloring TDMA wireless networks},
    doi={10.1109/COMSWA.2006.1665226}
}

Ted Herman
Sriram Pemmaraju
Imran Pirwani
Year: 2006
Oriented Edge Colorings and Link Scheduling in Sensor Networks
SENSORWARE
IEEE
DOI: 10.1109/COMSWA.2006.1665226

Ted Herman^1,2^,*, Sriram Pemmaraju^1,2^,*, Imran Pirwani^1,2^,*

1: Department of Computer Science, The University
2: of Iowa, Iowa City, IA 52240-1419.

*Contact email: herman@cs.uiowa.edu , pirwani@cs.uiowa.edu , sriram@cs.uiowa.edu

Abstract

This paper shows that TDMA slot assignment for unicast communication in a wireless network can be distributively computed for an n-node acyclic network in O(polylog(n)) time, with high probability. The best previous distributed algorithm for this problem requires O(n) time and obtains a TDMA schedule using 2Delta time slots. The new algorithm uses (1+epsiv)middot2Delta time slots where epsiv is a tunable fraction

Keywords: edge-coloring TDMA wireless networks

Published: 2006-08-07
Publisher: IEEE

: http://dx.doi.org/10.1109/COMSWA.2006.1665226