Approximate dynamic programming for link scheduling in wireless mesh networks

Katerina Papadaki, Vasilis Friderikos

    Research output: Contribution to journalArticlepeer-review

    29 Citations (Scopus)

    Abstract

    In this paper a novel interference-based formulation and solution methodology for the problem of link scheduling in wireless mesh networks is proposed. Traditionally, this problem has been formulated as a deterministic integer program, which has been shown to be NP-hard. The proposed formulation is based on dynamic programming and allows greater flexibility since dynamic and stochastic components of the problem can be embedded into the optimization framework. By temporal decomposition we reduce the size of the integer program and using approximate dynamic programming (ADP) methods we tackle the curse of dimensionality. The numerical results reveal that the proposed algorithm outperforms well-known heuristics under different network topologies. Finally, the proposed ADP methodology can be used not only as an upper bound but also as a generic framework where different heuristics can be integrated. (c) 2007 Elsevier Ltd. All rights reserved.

    Original languageEnglish
    Pages (from-to)3848-3859
    Number of pages12
    JournalCOMPUTERS AND OPERATIONS RESEARCH
    Volume35
    Issue number12
    DOIs
    Publication statusPublished - Dec 2008

    Fingerprint

    Dive into the research topics of 'Approximate dynamic programming for link scheduling in wireless mesh networks'. Together they form a unique fingerprint.

    Cite this