UC San Diego

This dissertation considers the problem of routing multi- commodity data over a multi-hop wireless ad-hoc network. The few well-known throughput optimal routing algorithms in literature are all based on backpressure principle, which shows poor delay performance under many network topologies and traffic conditions. In contrast, heuristic routing algorithms which incorporated information of closeness to destination are either not throughout optimal or the thoughts optimality was unknown (e.g. opportunistic routing policy with congestion diversity aka. ORCD). The primary goal of this dissertation is to find routing policies beyond backpressure type that not only ensure throughput optimality but also maintain satisfactory average delay performance. In the single commodity scenario, by considering a class of continuous, differentiable, and piece-wise quadratic Lyapunov functions, we propose a large class of throughput optimal routing policies called K policies, which include both backpressure algorithm and ORCD as special cases. The proposed class of Lyapunov functions allow the routing policies to control the traffic along short paths for a large portion of state-space while ensuring a negative expected drift, hence, enabling the design of routing policies with much improved delay performances. We then extend K-policy to multi-commodity case by considering nonquadric Lyapunov functions. A multi-commodity version of ORCD algorithm is proposed based on the generalized K- policy and is shown to be throughput optimal under mild conditions. Interestingly, the algorithm selects the commodity that has the maximum backlogs ratio instead of the maximum difference of backlogs as in the original backpressure algorithm. Simulation results show that the proposed algorithms have better delay performances in all scenarios we considered