Route selection for capacity maximization in multi-rate TDMA-based wireless ad hoc networks

In this paper we address the issue of designing a routing scheme for ad hoc networks, which aims at maximizing the number of flows with satisfied bandwidth demands. In general, selecting a multi-hop wireless path for bandwidth-guaranteed flows is challenging because of the broadcast nature of the wireless medium. Thus, in this study we formulate the route selection problem by considering a synchronized multi-rate TDMA access scheme. Once the route is found, the radio resources are reserved as time slots in the TDMA frames along the path the flow takes. We demonstrate that selecting routes so as to maximize the number of accepted flows is an APX-complete problem (i.e., there are no polynomial-time approximation schemes), even under simplified rules for bandwidth reservation. This result is stronger than previously established in other studies. Guided by our analysis, we propose a new cumulated available resources and Topology Aware (CARTA) routing heuristic, which selects routes bypassing heavily loaded and highly interfered network regions. Simulations performed with random topologies of up to 100 nodes and various traffic configurations show that CARTA obtains a more balanced utilization of the network resources, and up to 25% capacity increase than the second best metric from the literature we tested, at the cost of a limited increase in path lengths.