Overhearing-aware joint routing and rate selection in multi-hop multi-rate UWB-based WPANs

Ultra-wideband (UWB) communications has emerged as a promising technology for high data rate wireless personal area networks (WPANs). In this paper, we address a key issue that impacts the performance of multi-hop, multi-rate UWB-based WPANs, namely joint routing and rate selection. Arbitrary selection of routes (including direct links) and transmission rates along these routes results in unnecessarily long channel reservation time and high blocking rate for prospective reservations, and leads to low network throughput. To remedy this situation, we propose a novel overhearing-aware joint routing and rate selection (ORRS) scheme, which improves the network throughput by exploiting the dependence between the channel reservation time and the multi-rate capability of an UWB system. At the same time, ORRS takes advantage of packet overhearing, a typical characteristic of broadcast communications. For a given source-destination pair, ORRS aims at selecting a path and its transmission rates that achieve the minimum reservation time, leading to low blocking rate for prospective reservations and high network throughput. We show that achieving this goal while simultaneously exploiting packet overhearing and satisfying a target packet delivery probability over the selected route leads to an NP-hard problem. Accordingly, ORRS resorts to approximate solutions (proactive and reactive) to find a near-optimal result with reasonable computational/ communication overhead. We further propose other variants that exploit packet overhearing in different ways to improve ORRS performance.