A Distributed Maximal Link Scheduler for Multi Tx/Rx Wireless Mesh Networks
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 com...
| Main Authors: | , , , |
|---|---|
| Format: | Journal Article |
| Published: |
IEEE
2015
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/46732 |
| _version_ | 1848757642335354880 |
|---|---|
| author | Wang, H. Chin, K. Soh, Sieteng Raad, R. |
| author_facet | Wang, H. Chin, K. Soh, Sieteng Raad, R. |
| author_sort | Wang, H. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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 centralised 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 centralised 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. |
| first_indexed | 2025-11-14T09:31:20Z |
| format | Journal Article |
| id | curtin-20.500.11937-46732 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T09:31:20Z |
| publishDate | 2015 |
| publisher | IEEE |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-467322017-09-13T14:08:48Z A Distributed Maximal Link Scheduler for Multi Tx/Rx Wireless Mesh Networks Wang, H. Chin, K. Soh, Sieteng Raad, R. Distributed algorithms wireless mesh networks time division multiplexing scheduling algorithms 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 centralised 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 centralised 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. 2015 Journal Article http://hdl.handle.net/20.500.11937/46732 10.1109/TWC.2014.2353046 IEEE restricted |
| spellingShingle | Distributed algorithms wireless mesh networks time division multiplexing scheduling algorithms Wang, H. Chin, K. Soh, Sieteng Raad, R. A Distributed Maximal Link Scheduler for Multi Tx/Rx Wireless Mesh Networks |
| title | A Distributed Maximal Link Scheduler for Multi Tx/Rx Wireless Mesh Networks |
| title_full | A Distributed Maximal Link Scheduler for Multi Tx/Rx Wireless Mesh Networks |
| title_fullStr | A Distributed Maximal Link Scheduler for Multi Tx/Rx Wireless Mesh Networks |
| title_full_unstemmed | A Distributed Maximal Link Scheduler for Multi Tx/Rx Wireless Mesh Networks |
| title_short | A Distributed Maximal Link Scheduler for Multi Tx/Rx Wireless Mesh Networks |
| title_sort | distributed maximal link scheduler for multi tx/rx wireless mesh networks |
| topic | Distributed algorithms wireless mesh networks time division multiplexing scheduling algorithms |
| url | http://hdl.handle.net/20.500.11937/46732 |