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 journalArticlepeer-review

    6 Citations (Scopus)


    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 languageEnglish
    Pages (from-to)74-85
    Number of pages12
    JournalComputer Communications
    Issue number1
    Publication statusPublished - 2005 Jan 31


    • Optimum transmission schedule
    • Packet radio network
    • Time division multiple access

    ASJC Scopus subject areas

    • Computer Networks and Communications
    • Electrical and Electronic Engineering


    Dive into the research topics of 'A heuristic algorithm for optimum transmission schedule in broadcast packet radio networks'. Together they form a unique fingerprint.

    Cite this