Skip to main content
placeholder image

A distributed maximal link scheduler for multi Tx/Rx wireless mesh networks

Journal Article


Abstract


  • The capacity of Wireless Mesh Networks (WMNs)

    has significantly increased with the recent addition of multiple

    transmit (Tx) and receive (Rx) (MTR) capability or smart antennas.

    This increase however is predicated on an effective link

    scheduler. The aim of any scheduler is to derive a superframe

    comprising the smallest number of slots that affords each link one

    or more transmission opportunities. In particular, the scheduler

    is required to solve an instance of the NP-complete, MAX-CUT

    problem, in each time slot. To this end, there are a number of centralized

    schedulers, but only a handful of distributed schedulers.

    However, each of these distributed schedulers has its own drawbacks;

    either they do not guarantee maximal activated links or do

    not guarantee all links are activated. Henceforth, in this paper, we

    add to the state-of-the-art by proposing a novel distributed scheduler,

    called Algo-d, which approximates the MAX-CUT problem

    in a distributed manner using only local information. In fact, this

    is the first distributed solution for MAX-CUT problem. Through

    theoretical analysis and simulation, we show that Algo-d achieves

    the following performance: 1) Algo-d schedules on average 12%

    fewer and 46.5% more links in each time slot than two centralized

    algorithms, and 2) Algo-d schedules 28% more links than ROMA

    and 270% more links than JazzyMAC; both state-of-the-art distributed

    schedulers for MTR WMNs.

Publication Date


  • 2015

Citation


  • H. Wang, K. Chin, S. Soh & R. Raad, "A distributed maximal link scheduler for multi Tx/Rx wireless mesh networks," IEEE Transactions on Wireless Communications, vol. 14, (1) pp. 520-531, 2015.

Scopus Eid


  • 2-s2.0-84921419214

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers/5603

Has Global Citation Frequency


Number Of Pages


  • 11

Start Page


  • 520

End Page


  • 531

Volume


  • 14

Issue


  • 1

Place Of Publication


  • United States

Abstract


  • The capacity of Wireless Mesh Networks (WMNs)

    has significantly increased with the recent addition of multiple

    transmit (Tx) and receive (Rx) (MTR) capability or smart antennas.

    This increase however is predicated on an effective link

    scheduler. The aim of any scheduler is to derive a superframe

    comprising the smallest number of slots that affords each link one

    or more transmission opportunities. In particular, the scheduler

    is required to solve an instance of the NP-complete, MAX-CUT

    problem, in each time slot. To this end, there are a number of centralized

    schedulers, but only a handful of distributed schedulers.

    However, each of these distributed schedulers has its own drawbacks;

    either they do not guarantee maximal activated links or do

    not guarantee all links are activated. Henceforth, in this paper, we

    add to the state-of-the-art by proposing a novel distributed scheduler,

    called Algo-d, which approximates the MAX-CUT problem

    in a distributed manner using only local information. In fact, this

    is the first distributed solution for MAX-CUT problem. Through

    theoretical analysis and simulation, we show that Algo-d achieves

    the following performance: 1) Algo-d schedules on average 12%

    fewer and 46.5% more links in each time slot than two centralized

    algorithms, and 2) Algo-d schedules 28% more links than ROMA

    and 270% more links than JazzyMAC; both state-of-the-art distributed

    schedulers for MTR WMNs.

Publication Date


  • 2015

Citation


  • H. Wang, K. Chin, S. Soh & R. Raad, "A distributed maximal link scheduler for multi Tx/Rx wireless mesh networks," IEEE Transactions on Wireless Communications, vol. 14, (1) pp. 520-531, 2015.

Scopus Eid


  • 2-s2.0-84921419214

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers/5603

Has Global Citation Frequency


Number Of Pages


  • 11

Start Page


  • 520

End Page


  • 531

Volume


  • 14

Issue


  • 1

Place Of Publication


  • United States