Distributed scheduling of broadcasts in a radio network
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. sac 2, 497-504 vol.2
- https://doi.org/10.1109/infcom.1989.101493
Abstract
A distributed algorithm is presented for obtaining an efficient and conflict-free broadcasting schedule in a multi-hop packet radio network. The inherent broadcast nature of the radio channel enables a node's transmission to be received by all other nodes within range. Multiple transmissions can be scheduled simultaneously because of the multi-hop nature of the network. It is first shown that the construction of a broadcasting schedule of minimum length is NP-complete, and then a centralized algorithm based on a sequential graph-coloring heuristic is presented to construct minimal-length schedules. A distributed implementation of this algorithm is then proposed, which is based on circulating a token through the nodes in the network.Keywords
This publication has 9 references indexed in Scilit:
- Distributed algorithm for efficient and interference-free broadcasting in radio networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Distributed assignment algorithms for multi-hop packet-radio networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Link scheduling in polynomial timeIEEE Transactions on Information Theory, 1988
- Tree-Based Broadcasting in Multihop Radio NetworksIEEE Transactions on Computers, 1987
- A design concept for reliable mobile radio networks with frequency hopping signalingProceedings of the IEEE, 1987
- On Broadcasting in Radio Networks--Problem Analysis and Protocol DesignIEEE Transactions on Communications, 1985
- Some complexity results about packet radio networks (Corresp.)IEEE Transactions on Information Theory, 1984
- The Design and Simulation of a Mobile Radio Network with Distributed ControlIEEE Journal on Selected Areas in Communications, 1984
- The Complexity of Optimal Addressing in Radio NetworksIEEE Transactions on Communications, 1982