A Multi-Commodity Flow Approach for Globally Aware Routing in Multi-Hop Wireless Networks

Abstract

Routing in multi-hop wireless networks is typically greedy, with every connection attempting to establish a path that minimizes its number of hops. However, interference plays a major role in limiting the capacity of such networks; this effect is ignored by most existing protocols. It is likely that approaches that coordinate routing to account for mutual interference would be able to achieve better performance than traditional approaches. Modeling routing with interference constraints is a complex non-linear optimization problem. We approach the problem using a multi commodity flow (MCF) formulation. We analyze the interaction of multiple routes and propose effective objective functions which attempt to maximize interference separation while limiting path inflation. Initial experimental results show significant improvement in performance over a traditional routing protocol. We evaluate the formulation against routes obtained using DSR under several scenarios and show that better performance is achieved in terms of throughput, goodput, and end-to-end delay