Abstract
Quantifying the end-to-end delay performance in multihop wireless networks is a well-known challenging problem. In this paper, we propose a new joint congestion control and scheduling algorithm for multihop wireless networks with fixedroute flows operated under a general interference model with interference degree K. Our proposed algorithm not only achieves a provable throughput guarantee (which is close to at least 1=K of the system capacity region), but also leads to explicit upper bounds on the end-to-end delay of every flow. Our end-to-end delay- and throughput-bounds are in simple and closed forms, and they explicitly quantify the tradeoff between throughput and delay of every flow. Further, the per-flow end-to-end delay bound increases linearly with the number of hops that the flow passes through, which is order-optimal with respect to the number of hops. Unlike traditional solutions based on the backpressure algorithm, our proposed algorithm combines windowbased flow control with a new rate-based distributed scheduling algorithm. A key contribution of our work is to use a novel stochastic dominance approach to bound the corresponding perflow throughput and delay, which otherwise are often intractable in these types of systems. Our proposed algorithm is fully distributed and requires a low per-node complexity that does not increase with the network size. Hence, it can be easily implemented in practice.
Keywords
Window-based flow control, rate-based scheduling algorithms, low-complexity and distributed algorithms, supermodular ordering, order-optimal delay bound
Date of this Version
8-7-2012