Throughput-Delay Trade-off in Wireless Multi-hop Networks via Greedy Hyperbolic Embedding

Real time applications over wireless multihop networks, demand routing/scheduling algorithms that achieve desirable delay-throughput trade-offs, with high throughput and low end-to-end delay. The backpressure algorithm, has received much attention by the research community in the past few years, as it satisfies the throughput optimal requirement. The backpressure algorithm performs routing and scheduling based on congestion gradients, by allowing transmission to the links that maximize the differential backlog between neighboring nodes. However, by deploying routing without using any information about the position or distance to the destination, it explores all possible source-destination paths leading to undesirable high delays. In this paper, we propose a method of restricting the number of paths used by the backpressure algorithm, with the aid of the greedy embedding of a network in the hyperbolic space. We propose two algorithms, the “Greedy” backpressure and the “Greediest” backpressure for both static and dynamic networks, which consider the network embedded in the hyperbolic space and combine the greedy routing in hyperbolic coordinates with the backpressure scheduling. We prove analytically their throughput optimality and study through simulations the induced improvement in the delay-throughput trade-off compared with the backpressure algorithm.