Scheduling algorithms for multi-hop radio networks
Authors:
- S. RamanathanSRS. Ramanathan
- Errol L. LloydELErrol L. Lloyd
Open Access
- 1 October 1992
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in ACM SIGCOMM Computer Communication Review
- Vol. 22 (4) , 211-222
Abstract
New algorithms for transmission scheduling in multihop broadcast radio networks are presented. Both link scheduling and broadcast scheduling are considered. In each instance scheduling algorithms are given that improve upon existing algorithms both theoretically and experimentally. Theoretically, it is shown that tree networks can be scheduled optimally, and that arbitrary networks can be scheduled so that the schedule is bounded by a length that is proportional to a function of the network thickness times the optimum. Previous algorithms could guarantee only that the schedules were bounded by a length no worse than the maximum node degree, the algorithms presented here represent a considerable theoretical improvement. Experimentally, a realistic model of a radio network is given and the performance of the new algorithms is studied. These results show that, for both types of scheduling, the new algorithms (experimentally) perform consistently better than earlier methods.Keywords
This publication has 7 references indexed in Scilit:
- Multiple communication in multi-hop radio networks1989
- Distributed scheduling of broadcasts in a radio network1989
- Forests, frames, and games: algorithms for matroid sums and applications1988
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- The NP-completeness column: An ongoing guideJournal of Algorithms, 1986
- Some complexity results about packet radio networks (Corresp.)IEEE Transactions on Information Theory, 1984
- Improving the performance guarantee for approximate graph coloringJournal of the ACM, 1983