A novel scheduler for concurrent Tx/Rx wireless mesh networks with weighted links
This paper considers the NP-hard problem of scheduling weighted links in concurrent transmit/receive wireless mesh networks. The problem generalizes existing works to links with weight wij ≥ 1. We propose an O(|V|2) algorithm, where V is the set of routers, that is orders of magnitude faster than co...
| Main Authors: | , , |
|---|---|
| Format: | Journal Article |
| Published: |
IEEE Communications Society
2012
|
| Online Access: | http://hdl.handle.net/20.500.11937/37051 |
| _version_ | 1848754940358426624 |
|---|---|
| author | Chin, Kuek Soh, Sieteng Meng, C. |
| author_facet | Chin, Kuek Soh, Sieteng Meng, C. |
| author_sort | Chin, Kuek |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | This paper considers the NP-hard problem of scheduling weighted links in concurrent transmit/receive wireless mesh networks. The problem generalizes existing works to links with weight wij ≥ 1. We propose an O(|V|2) algorithm, where V is the set of routers, that is orders of magnitude faster than computationally intensive approaches that use the well-known Goemans-Williamson (GWA)'s maximum cut algorithm and also brute-force. Our algorithm generates schedules, on average, with at most 3% and 9% fewer links than the GWA and brute-force approaches respectively. |
| first_indexed | 2025-11-14T08:48:23Z |
| format | Journal Article |
| id | curtin-20.500.11937-37051 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T08:48:23Z |
| publishDate | 2012 |
| publisher | IEEE Communications Society |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-370512018-03-29T09:08:11Z A novel scheduler for concurrent Tx/Rx wireless mesh networks with weighted links Chin, Kuek Soh, Sieteng Meng, C. This paper considers the NP-hard problem of scheduling weighted links in concurrent transmit/receive wireless mesh networks. The problem generalizes existing works to links with weight wij ≥ 1. We propose an O(|V|2) algorithm, where V is the set of routers, that is orders of magnitude faster than computationally intensive approaches that use the well-known Goemans-Williamson (GWA)'s maximum cut algorithm and also brute-force. Our algorithm generates schedules, on average, with at most 3% and 9% fewer links than the GWA and brute-force approaches respectively. 2012 Journal Article http://hdl.handle.net/20.500.11937/37051 10.1109/LCOMM.2011.122211.112264 IEEE Communications Society restricted |
| spellingShingle | Chin, Kuek Soh, Sieteng Meng, C. A novel scheduler for concurrent Tx/Rx wireless mesh networks with weighted links |
| title | A novel scheduler for concurrent Tx/Rx wireless mesh networks with weighted links |
| title_full | A novel scheduler for concurrent Tx/Rx wireless mesh networks with weighted links |
| title_fullStr | A novel scheduler for concurrent Tx/Rx wireless mesh networks with weighted links |
| title_full_unstemmed | A novel scheduler for concurrent Tx/Rx wireless mesh networks with weighted links |
| title_short | A novel scheduler for concurrent Tx/Rx wireless mesh networks with weighted links |
| title_sort | novel scheduler for concurrent tx/rx wireless mesh networks with weighted links |
| url | http://hdl.handle.net/20.500.11937/37051 |