Novel scheduling algorithms for concurrent transmit/receive wireless mesh networks
Recently, in an effort to increase the capacity of Wireless Mesh Networks (WMNs), researchers have begun equipping routers with multiple interfaces/radios, and connecting each one to a directional or smart antenna. A key feature of these routers is their ability to transmit or receive from multiple...
| Main Authors: | , , |
|---|---|
| Format: | Journal Article |
| Published: |
Elsevier
2012
|
| Online Access: | http://hdl.handle.net/20.500.11937/34432 |
| _version_ | 1848754220855984128 |
|---|---|
| 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 | Recently, in an effort to increase the capacity of Wireless Mesh Networks (WMNs), researchers have begun equipping routers with multiple interfaces/radios, and connecting each one to a directional or smart antenna. A key feature of these routers is their ability to transmit or receive from multiple neighbors simultaneously. Hence, they have orders of magnitude higher capacity than their omni-directional counterparts. This significant capacity increase, however, is predicated upon a link scheduling algorithm that maximizes the number of active links at any given point in time. This paper proposes a number of link activation algorithms that derive maximal bipartite graphs from general topologies. These algorithms provide different trade-offs in terms of computation time and optimality. A key highlight is a greedy algorithm that has a time complexity of O(∣V∣2), where V is the set of routers. Apart from that, we outline two algorithms that use an approximation to the well known maximum cut problem, and also a brute force algorithm, which is capable of deriving an optimal link activation schedule. The output from our algorithms can then be used by a spatial Time Division Multiple Access (TDMA) Medium Access Control (MAC) protocol to schedule concurrent transmitting and receiving links. We have verified our algorithms on various topologies with increasing node degrees as well as node numbers. From extensive simulation studies, we find that our algorithms have good performance in terms of number of links activated, superframe length, and end-to-end packet delay. |
| first_indexed | 2025-11-14T08:36:57Z |
| format | Journal Article |
| id | curtin-20.500.11937-34432 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T08:36:57Z |
| publishDate | 2012 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-344322017-09-13T15:12:58Z Novel scheduling algorithms for concurrent transmit/receive wireless mesh networks Chin, Kuek Soh, Sieteng Meng, C. Recently, in an effort to increase the capacity of Wireless Mesh Networks (WMNs), researchers have begun equipping routers with multiple interfaces/radios, and connecting each one to a directional or smart antenna. A key feature of these routers is their ability to transmit or receive from multiple neighbors simultaneously. Hence, they have orders of magnitude higher capacity than their omni-directional counterparts. This significant capacity increase, however, is predicated upon a link scheduling algorithm that maximizes the number of active links at any given point in time. This paper proposes a number of link activation algorithms that derive maximal bipartite graphs from general topologies. These algorithms provide different trade-offs in terms of computation time and optimality. A key highlight is a greedy algorithm that has a time complexity of O(∣V∣2), where V is the set of routers. Apart from that, we outline two algorithms that use an approximation to the well known maximum cut problem, and also a brute force algorithm, which is capable of deriving an optimal link activation schedule. The output from our algorithms can then be used by a spatial Time Division Multiple Access (TDMA) Medium Access Control (MAC) protocol to schedule concurrent transmitting and receiving links. We have verified our algorithms on various topologies with increasing node degrees as well as node numbers. From extensive simulation studies, we find that our algorithms have good performance in terms of number of links activated, superframe length, and end-to-end packet delay. 2012 Journal Article http://hdl.handle.net/20.500.11937/34432 10.1016/j.comnet.2011.12.001 Elsevier restricted |
| spellingShingle | Chin, Kuek Soh, Sieteng Meng, C. Novel scheduling algorithms for concurrent transmit/receive wireless mesh networks |
| title | Novel scheduling algorithms for concurrent transmit/receive wireless mesh networks |
| title_full | Novel scheduling algorithms for concurrent transmit/receive wireless mesh networks |
| title_fullStr | Novel scheduling algorithms for concurrent transmit/receive wireless mesh networks |
| title_full_unstemmed | Novel scheduling algorithms for concurrent transmit/receive wireless mesh networks |
| title_short | Novel scheduling algorithms for concurrent transmit/receive wireless mesh networks |
| title_sort | novel scheduling algorithms for concurrent transmit/receive wireless mesh networks |
| url | http://hdl.handle.net/20.500.11937/34432 |