Optimal broadcast scheduling in packet radio networks using mean field annealing

Gangsheng Wang, Nirwan Ansari

Research output: Contribution to journalArticlepeer-review

131 Scopus citations


Packet radio (PR) is a technology that applies the packet switching technique to the broadcast radio environment In a PR network, a single high-speed wideband channel is shared by all PR stations. When a time-division multi-access protocol is used, the access to the channel by stations' transmissions must be properly scheduled in both time and space domains in order to avoid collisions or interferences. It is proven in this paper that such a scheduling problem is NP-complete. Therefore, an efficient polynomial algorithm rarely exists, and a mean field annealing-based algorithm is proposed to schedule the stations' transmissions in a frame consisting of certain number of time slots. Numerical examples and comparisons with some existing scheduling algorithms have shown that the proposed scheme can find near-optimal solutions with reasonable computational complexity. Both time delay and channel utilization are calculated based on the found schedules.

Original languageEnglish (US)
Pages (from-to)250-259
Number of pages10
JournalIEEE Journal on Selected Areas in Communications
Issue number2
StatePublished - Feb 1997

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Optimal broadcast scheduling in packet radio networks using mean field annealing'. Together they form a unique fingerprint.

Cite this