GLOBALLY AWARE ROUTING IN MULTI-HOP WIRELESS NETWORKS: A FORMULATION AND ANALYSIS

Routing in multi-hop wireless networks is typically greedy, with every connection attempting to establish a path with the smallest number of hops. However, interference plays a major role in limiting the capacity of such networks. While recent protocols have attempted to account for interference, they do so reactively and without coordination. Approaches that coordinate routing to account for mutual interference 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. We also show that the pattern of interference experienced by a link plays an important role in defining capacity. The model is directly useful in traffic engineering, provisioning and QoS admission control for mesh networks. In addition, it provides a tool for analyzing effective operation in MHWN providing insight into developing effective distributed protocols for them. We evaluate the formulation against routes obtained using a conventional routing algorithm under several scenarios and show that better performance is achieved in terms of throughput, goodput, and end-to-end delay.