Distributed scheduling of broadcasts in a radio network

Rajiv Ramaswami; Keshab K. Purhi

doi:10.1109/INFCOM.1989.101493

Distributed scheduling of broadcasts in a radio network

Rajiv Ramaswami, Keshab K. Purhi

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

163 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 language	English (US)
Title of host publication	IEEE INFOCOM'89, Proceedings of the 8th Annual Joint Conference of the IEEE Computer and Communications Societies
Pages	497-504
Number of pages	8
DOIs	https://doi.org/10.1109/INFCOM.1989.101493
State	Published - 1989
Event	8th Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM'89 - Ottawa, ON, Canada Duration: Apr 23 1989 → Apr 27 1989

Publication series

Name	Proceedings - IEEE INFOCOM
ISSN (Print)	0743-166X

Other

Other	8th Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM'89
Country/Territory	Canada
City	Ottawa, ON
Period	4/23/89 → 4/27/89

Publisher link

10.1109/INFCOM.1989.101493

Find It

Find It at U of M Libraries

Cite this

Ramaswami, R & Purhi, KK 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., 101493, Proceedings - IEEE INFOCOM, pp. 497-504, 8th Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM'89, Ottawa, ON, Canada, 4/23/89. https://doi.org/10.1109/INFCOM.1989.101493

@inproceedings{062ab2ef3368403b967ad560e50eaaba,

title = "Distributed scheduling of broadcasts in a radio network",

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.",

author = "Rajiv Ramaswami and Purhi, {Keshab K.}",

year = "1989",

doi = "10.1109/INFCOM.1989.101493",

language = "English (US)",

isbn = "0818619201",

series = "Proceedings - IEEE INFOCOM",

pages = "497--504",

booktitle = "IEEE INFOCOM'89, Proceedings of the 8th Annual Joint Conference of the IEEE Computer and Communications Societies",

note = "8th Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM'89 ; Conference date: 23-04-1989 Through 27-04-1989",

}

TY - GEN

T1 - Distributed scheduling of broadcasts in a radio network

AU - Ramaswami, Rajiv

AU - Purhi, Keshab K.

PY - 1989

Y1 - 1989

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0024860918&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024860918&partnerID=8YFLogxK

U2 - 10.1109/INFCOM.1989.101493

DO - 10.1109/INFCOM.1989.101493

M3 - Conference contribution

AN - SCOPUS:0024860918

SN - 0818619201

SN - 9780818619205

T3 - Proceedings - IEEE INFOCOM

SP - 497

EP - 504

BT - IEEE INFOCOM'89, Proceedings of the 8th Annual Joint Conference of the IEEE Computer and Communications Societies

T2 - 8th Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM'89

Y2 - 23 April 1989 through 27 April 1989

ER -

Distributed scheduling of broadcasts in a radio network

Abstract

Publication series

Other

Publisher link

Find It

Other files and links

Fingerprint

Cite this