A New Paradigm for Multiflow in MC-MR Wireless Networks: Theoretic Foundations And Practical Algorithms

Illinois Institute Of Technology, Chicago IL

Investigators

Abstract

The multiflow problems in wireless networks address the transportation of traffic demands by multiple end-to-end communication requests at the maximum capacity. State-of-the-art methods of solving the multiflow problems require an excessive amount of computational resources, and consequently often prove unusable in practice. This project explores a completely new paradigm for multiflow problems in multi-channel multi-radio wireless networks and develops much faster and simpler practical algorithmic solutions that offer quantified trade-off between accuracy and efficiency. The new paradigm has wide applications in domains beyond wireless networks, and serves as a basis for interesting future projects on network capacity and cross-layer design and optimizations in wireless networks. Due to the cross-layer nature, multiflow problems in wireless networks pose unique and significant challenges. Characterizing computational hardness and strategies for resolving achievable approximation bounds have been the priority in existing studies of multiflow problems in wireless networks. In fact, state-of-the-art approximation algorithms for multiflow problems in wireless networks are all centralized and rely upon traditional linear programming (LP) methods exclusively. However, these traditional LP methods require an inordinate amount of running time and memory even for a moderate sized input, and consequently they often prove unusable in practice. Furthermore, the centralized nature of traditional LP methods make them unsuitable for developing distributed network protocols. This project explores a new paradigm for multiflow problems in multi-channel multi-radio wireless networks that is different from the prevailing LP-based paradigm, and develops practical algorithmic solutions that are much faster and simpler.