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 |
| Summary: | 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. |
|---|