Title :
Oriented Edge Colorings and Link Scheduling in Sensor Networks
Author :
Herman, Ted ; Pemmaraju, Sriram ; Pirwani, Imran
Author_Institution :
Dept. of Comput. Sci., Iowa Univ., Iowa City, IA
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 :
graph colouring; probability; radio links; scheduling; time division multiple access; wireless sensor networks; TDMA slot assignment; distributive computing; link scheduling; n-node acyclic network; oriented edge coloring; probability; sensor network; time division multiple access; unicast communication; wireless network; Access protocols; Computer networks; Distributed algorithms; Distributed computing; Intelligent networks; Processor scheduling; Radio broadcasting; Time division multiple access; Unicast; Wireless sensor networks; TDMA; edge-coloring; wireless networks;
Conference_Titel :
Communication System Software and Middleware, 2006. Comsware 2006. First International Conference on
Conference_Location :
New Delhi
Print_ISBN :
0-7803-9575-1
DOI :
10.1109/COMSWA.2006.1665226
