Skip to main content
placeholder image

Novel joint routing and scheduling algorithms for minimizing end-to-end delays in multi Tx-Rx wireless mesh networks

Journal Article


Abstract


  • Multiple transmit (Tx) or receive (Rx) capability is a significant advance in wireless communications. This so called MTR capability allows the creation of wireless mesh networks (WMNs) that are ideal for use as a high-speed wireless backbone that spans vast geographical areas. A fundamental problem, however, is deriving a minimal transmission schedule or superframe that yields low end-to-end delays, with the primary constraint that routers are not allowed to Tx and Rx simultaneously. In this paper, we consider a joint routing and link scheduling approach that addresses two fundamental issues that influence end-to-end delays: superframe length and transmission slot order. Shortening the superframe length, in terms of slots, is expected to minimize the inter-link activation time while reordering transmission slots increases the likelihood that links on a path are activated consecutively. We propose two algorithms. The first called JRS-Multi-DEC uses a novel metric to minimize the load of each link while the second, called JRS-BIP, uses a Binary Integer Program approach. Both algorithms aim to minimize the overall delay and use slot re-ordering on the resulting schedule to further reduce delay. Numerical results show both algorithms are able to reduce the average end-to-end delay by approximately 50% as compared to a non joint routing algorithm.

Publication Date


  • 2015

Citation


  • L. Wang, K. Chin, S. Soh & R. Raad, "Novel joint routing and scheduling algorithms for minimizing end-to-end delays in multi Tx-Rx wireless mesh networks," Computer Communications, vol. 72, pp. 63-77, 2015.

Scopus Eid


  • 2-s2.0-84931051514

Ro Metadata Url


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

Has Global Citation Frequency


Number Of Pages


  • 14

Start Page


  • 63

End Page


  • 77

Volume


  • 72

Place Of Publication


  • Netherlands

Abstract


  • Multiple transmit (Tx) or receive (Rx) capability is a significant advance in wireless communications. This so called MTR capability allows the creation of wireless mesh networks (WMNs) that are ideal for use as a high-speed wireless backbone that spans vast geographical areas. A fundamental problem, however, is deriving a minimal transmission schedule or superframe that yields low end-to-end delays, with the primary constraint that routers are not allowed to Tx and Rx simultaneously. In this paper, we consider a joint routing and link scheduling approach that addresses two fundamental issues that influence end-to-end delays: superframe length and transmission slot order. Shortening the superframe length, in terms of slots, is expected to minimize the inter-link activation time while reordering transmission slots increases the likelihood that links on a path are activated consecutively. We propose two algorithms. The first called JRS-Multi-DEC uses a novel metric to minimize the load of each link while the second, called JRS-BIP, uses a Binary Integer Program approach. Both algorithms aim to minimize the overall delay and use slot re-ordering on the resulting schedule to further reduce delay. Numerical results show both algorithms are able to reduce the average end-to-end delay by approximately 50% as compared to a non joint routing algorithm.

Publication Date


  • 2015

Citation


  • L. Wang, K. Chin, S. Soh & R. Raad, "Novel joint routing and scheduling algorithms for minimizing end-to-end delays in multi Tx-Rx wireless mesh networks," Computer Communications, vol. 72, pp. 63-77, 2015.

Scopus Eid


  • 2-s2.0-84931051514

Ro Metadata Url


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

Has Global Citation Frequency


Number Of Pages


  • 14

Start Page


  • 63

End Page


  • 77

Volume


  • 72

Place Of Publication


  • Netherlands