Oriented Edge Colorings and Link Scheduling in Sensor Networks

T Herman; S Pemmaraju; I Pirwani

doi:10.1109/COMSWA.2006.1665226

Back

Conference proceeding

Oriented Edge Colorings and Link Scheduling in Sensor Networks

T Herman, S Pemmaraju and I Pirwani

2006 1st International Conference on Communication Systems Software & Middleware, pp.1-6

2006

DOI: 10.1109/COMSWA.2006.1665226

View Online

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

Access protocols

Computer networks

Distributed algorithms

Distributed computing

edge-coloring

Intelligent networks

Processor scheduling

Radio broadcasting

TDMA

Time division multiple access

Unicast

wireless networks

Wireless sensor networks

Details

Title: Subtitle: Oriented Edge Colorings and Link Scheduling in Sensor Networks
Creators: T Herman - University of Iowa
S Pemmaraju - University of Iowa
I Pirwani - University of Iowa
Resource Type: Conference proceeding
Publication Details: 2006 1st International Conference on Communication Systems Software & Middleware, pp.1-6
DOI: 10.1109/COMSWA.2006.1665226
Publisher: IEEE
Language: English
Date published: 2006
Academic Unit: Computer Science; Internal Medicine
Record Identifier: 9984259424902771

Metrics

10 Record Views