Decomposition for Low-Complexity Near-Optimal Routing in Multi-Hop Wireless Networks

Network flow models serve as a popular mathematical framework for the analysis and optimization of multi-hop wireless networks. They also serve to provide the understanding necessary to derive effective distributed protocols. However, the high computational complexity of realistic models restrict the translation of theoretical insights into distributed protocols. In this paper, we consider an NP-hard, mixed integer linear programming based routing model that computes single-path routes in a wireless network. We propose an efficient, polynomial time algorithm that applies domain specific heuristics to reduce the complexity. We employ a decomposition based approach to break the monolithic problem into several sub-problems that cooperate to find near-optimal routes. The sub-problem structure is chosen such that it captures the optimal route discovery process between a source and destination; this is a design principle that can be directly used in distributed routing protocols. We show that the resulting formulation achieves orders of magnitude improvement in the run-time. Simulation results show that the routes derived from the model are effective even in practical wireless networks with commonly used protocol stack.