Oriented Edge Colorings and Link Scheduling in Sensor Networks

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