Multicommodity flows, or multiflows in short, are central topics in all types of communication networks, whether wired or wireless. Computing a maximum (concurrent) multiflow in multihop wireless networks is particularly challenging because the capacities of the communication links, rather than being fixed, vary with the underlying link schedule. A unique challenge is thus how to compute a link schedule subject to the wireless interference constraint which induces a link capacity function supporting a maximum (concurrent) multiflow. This project establishes both the computational hardness and approximation hardness of computing maximum (concurrent) multiflows in multihop wireless networks, and develops practical approximation algorithms with provably good performance. A polyhedral approach is taken by the project to construct various polynomial approximate capacity subregions of multihop wireless networks. These approximate capacity subregions not only are the algorithmic foundation of the computing maximum (concurrent) multiflows, but also serve as a basis for interesting future projects on network capacity and cross-layer design and optimizations in multihop wireless networks. They are also of independent interest to the theoretical computer science community at large. This project provides scholarships to graduate students and offers research topics for strong dissertation works on multihop wireless networks. The outcome of this project will not only be disseminated to the professional researchers through journals and conference proceedings, but also be integrated into the lecture notes targeted for senior undergraduate students and graduate students.
