Scheduling algorithms for multihop radio networks
- 1 April 1993
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 1 (2) , 166-177
- https://doi.org/10.1109/90.222924
Abstract
Aew algorithms for transmission scheduling in multi- hop broadcast radio networks are presented. Both link scheduling and broadcast scheduling are considered. In each instance, sched- uling 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 times optimum. Since the thickness is typically several orders of magnitude less 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 thaq for both types of scheduling, the new algorithms (experimentally) perform consistently better than earlier methods.Keywords
This publication has 17 references indexed in Scilit:
- Distributed algorithm for efficient and interference-free broadcasting in radio networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Multiple communication in multi-hop radio networksPublished by Association for Computing Machinery (ACM) ,1989
- Forests, frames, and games: algorithms for matroid sums and applicationsPublished by Association for Computing Machinery (ACM) ,1988
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- Issues in packet radio network designProceedings of the IEEE, 1987
- A design concept for reliable mobile radio networks with frequency hopping signalingProceedings of the IEEE, 1987
- On the np-completeness of certain network testing problemsNetworks, 1984
- Improving the performance guarantee for approximate graph coloringJournal of the ACM, 1983
- The NP-completeness column: An ongoing guideJournal of Algorithms, 1981
- Graph Theory with ApplicationsPublished by Springer Nature ,1976