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

Research Article

Oriented Edge Colorings and Link Scheduling in Sensor Networks

  • @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 Herman1,2,*, Sriram Pemmaraju1,2,*, Imran Pirwani1,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