A heuristic algorithm for optimum transmission schedule in broadcast packet radio networks

Goutam Chakraborty; Debasish Chakraborty; Norio Shiratori

doi:10.1016/j.comcom.2004.06.009

A heuristic algorithm for optimum transmission schedule in broadcast packet radio networks

Goutam Chakraborty^*, Debasish Chakraborty, Norio Shiratori

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

6 Citations (Scopus)

Abstract

Packet Radio networks are to provide data communications among a set of nodes distributed over a wide region. Transmission from nodes is broadcast in nature. Where direct communication between two nodes is not possible, connection is established in multiple hops. A time division multiple access (TDMA) protocol is adopted for conflict free communication among different nodes. The goal is to find a conflict free transmission schedule for different nodes at different time-slots of a fixed length time frame, called TDMA cycle. The optimization criterion is primarily to (1) minimize the TDMA cycle length, and then to (2) maximize the number of transmissions. The problem is proved to be NP-complete. A randomized algorithm is proposed, which is very efficient to achieve the first optimization criterion. The results are shown to be superior compared to other recently reported competitive algorithms.

Original language	English
Pages (from-to)	74-85
Number of pages	12
Journal	Computer Communications
Volume	28
Issue number	1
DOIs	https://doi.org/10.1016/j.comcom.2004.06.009
Publication status	Published - 2005 Jan 31

Keywords

Optimum transmission schedule
Packet radio network
Time division multiple access

ASJC Scopus subject areas

Computer Networks and Communications
Electrical and Electronic Engineering

Access to Document

10.1016/j.comcom.2004.06.009

Cite this

@article{f751472bac80425fa355686598540361,

title = "A heuristic algorithm for optimum transmission schedule in broadcast packet radio networks",

abstract = "Packet Radio networks are to provide data communications among a set of nodes distributed over a wide region. Transmission from nodes is broadcast in nature. Where direct communication between two nodes is not possible, connection is established in multiple hops. A time division multiple access (TDMA) protocol is adopted for conflict free communication among different nodes. The goal is to find a conflict free transmission schedule for different nodes at different time-slots of a fixed length time frame, called TDMA cycle. The optimization criterion is primarily to (1) minimize the TDMA cycle length, and then to (2) maximize the number of transmissions. The problem is proved to be NP-complete. A randomized algorithm is proposed, which is very efficient to achieve the first optimization criterion. The results are shown to be superior compared to other recently reported competitive algorithms.",

keywords = "Optimum transmission schedule, Packet radio network, Time division multiple access",

author = "Goutam Chakraborty and Debasish Chakraborty and Norio Shiratori",

year = "2005",

month = jan,

day = "31",

doi = "10.1016/j.comcom.2004.06.009",

language = "English",

volume = "28",

pages = "74--85",

journal = "Computer Communications",

issn = "0140-3664",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - A heuristic algorithm for optimum transmission schedule in broadcast packet radio networks

AU - Chakraborty, Goutam

AU - Chakraborty, Debasish

AU - Shiratori, Norio

PY - 2005/1/31

Y1 - 2005/1/31

N2 - Packet Radio networks are to provide data communications among a set of nodes distributed over a wide region. Transmission from nodes is broadcast in nature. Where direct communication between two nodes is not possible, connection is established in multiple hops. A time division multiple access (TDMA) protocol is adopted for conflict free communication among different nodes. The goal is to find a conflict free transmission schedule for different nodes at different time-slots of a fixed length time frame, called TDMA cycle. The optimization criterion is primarily to (1) minimize the TDMA cycle length, and then to (2) maximize the number of transmissions. The problem is proved to be NP-complete. A randomized algorithm is proposed, which is very efficient to achieve the first optimization criterion. The results are shown to be superior compared to other recently reported competitive algorithms.

AB - Packet Radio networks are to provide data communications among a set of nodes distributed over a wide region. Transmission from nodes is broadcast in nature. Where direct communication between two nodes is not possible, connection is established in multiple hops. A time division multiple access (TDMA) protocol is adopted for conflict free communication among different nodes. The goal is to find a conflict free transmission schedule for different nodes at different time-slots of a fixed length time frame, called TDMA cycle. The optimization criterion is primarily to (1) minimize the TDMA cycle length, and then to (2) maximize the number of transmissions. The problem is proved to be NP-complete. A randomized algorithm is proposed, which is very efficient to achieve the first optimization criterion. The results are shown to be superior compared to other recently reported competitive algorithms.

KW - Optimum transmission schedule

KW - Packet radio network

KW - Time division multiple access

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

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

U2 - 10.1016/j.comcom.2004.06.009

DO - 10.1016/j.comcom.2004.06.009

M3 - Article

AN - SCOPUS:12344250745

SN - 0140-3664

VL - 28

SP - 74

EP - 85

JO - Computer Communications

JF - Computer Communications

IS - 1

ER -

A heuristic algorithm for optimum transmission schedule in broadcast packet radio networks

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this