Distributed scheduling of broadcasts in a radio network

Rajiv Ramaswami, Keshab K. Purhi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

150 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationIEEE INFOCOM'89, Proceedings of the 8th Annual Joint Conference of the IEEE Computer and Communications Societies
Pages497-504
Number of pages8
DOIs
StatePublished - Dec 1 1989
Event8th Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM'89 - Ottawa, ON, Canada
Duration: Apr 23 1989Apr 27 1989

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X

Other

Other8th Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM'89
CountryCanada
CityOttawa, ON
Period4/23/894/27/89

Fingerprint Dive into the research topics of 'Distributed scheduling of broadcasts in a radio network'. Together they form a unique fingerprint.

  • Cite this

    Ramaswami, R., & Purhi, K. K. (1989). Distributed scheduling of broadcasts in a radio network. In IEEE INFOCOM'89, Proceedings of the 8th Annual Joint Conference of the IEEE Computer and Communications Societies (pp. 497-504). [101493] (Proceedings - IEEE INFOCOM). https://doi.org/10.1109/INFCOM.1989.101493