Affiliations: Department of Computer Science, University of Delaware, Newark, DE 19716, USA, elloyd@udel.edu | Systems and Technologies, Bolt, Beranek and Newman (BBN) Inc., Cambridge, MA 02138, USA, ramanath@bbn.com
Note: [] Partially supported by the National Science Foundation under grant CCR-9120731.
Abstract: We present new distributed algorithms for the channel assignment or ‘scheduling’ problem in a radio network using TDMA. Both link and broadcast scheduling are addressed. As in [23], the algorithms are based on ordering the nodes of the corresponding graph on the basis of a criterion related to the ‘reach’ of the nodes. However, while [23] is inherently centralized, the algorithms given in this paper use a novel technique of partitioning into classes to yield efficient distributed implementations. Further, there is no compromise (in fact, for link scheduling there is an improvement) on the worst-case performance in comparison with the centralized algorithms of [23] which themselves represented a significant improvement over prior algorithms. In particular, the performance guarantee of our distributed algorithms is bounded by a constant times the graph thickness. Experimentally too, the performance is comparable to those of [23] and remains better than algorithms prior to it. A useful feature of our algorithms is that they are parameterized in a way that allows for the selection of a tradeoff between the schedule quality and efficiency. Also, the distributed algorithms are easy to implement and have low communication overhead. Finally, while only TDMA is discussed, it is highly possible that our ‘class’ based approach is applicable to CDMA and FDMA schemes as well.
Keywords: Radio Network, Scheduling, Distributed Algorithm
