Multiflow problems are one of the most fundamental problems in both wired networks and wireless networks. Due to the cross-layer nature, multiflow problems in wireless networks are significantly harder than their counterparts in wired networks and have received much research interest over the past decade. Common to most other early-staged research, the characterization of computational hardness and the "war" on achievable approximation bounds have been the priority to the existing studies of multiflow problems in wireless networks while their practical feasibility in both running time and memory requirement is ignored as long they are polynomial. In fact, state-of-the-art approximation algorithms for multiflow problems in wireless networks are all centralized and resorted to the traditional linear programming (LP) methods exclusively. However, those traditional LP methods can 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 makes it hopeless to develop distributed network protocols from them. This project explores a completely new paradigm for multiflow problems in multi-channel multi-radio wireless networks which is radically different from the prevailing LP-based paradigm, and develops practical algorithmic solutions which are much faster and simpler.
PI: Dr. Peng-Jun Wan, email: wan@cs.iit.edu.
Graduate students at IIT:
Prof. Ophir Frieder, Dept. of Computer Science, Georgetown University, email: ophir@ir.cs.georgetown.edu.
Prof. Lei Wang, Dalian University of Technology, email: lei.wang@ieee.org.
Prof. Huaqiang Yuan, Dongguan University of Technology, email: hyuan66@163.com.
Link scheduling is the MAC-layer subproblem of the multiflow problems in wireless networks. The prevailing approach for shortest link scheduling is based on a reduction to the maximum-weighted independent set problem, which itself may not admit efficient approximation algorithms. In addition, except for the wireless networks under the protocol interference model, none of the existing scheduling algorithms can produce a link schedule with explicit upper bounds on its length in terms of the link demands. As the result, the polynomial approximate capacity regions in these networks remain blank. In this project, we developed a purely combinatorial paradigm for link scheduling in wireless networks. In addition to the superior efficiency, it is able to provide explicit upper bounds on the lengths of the produced link schedule. By exploiting these upper bounds, polynomial approximate capacity regions are derived.
The effectiveness of this new paradigm is demonstrated by its applications in wireless networks under both the protocol interference model and the physical interference model, and wireless MIMO networks under the protocol interference model.
We developed a completely new paradigm for multiflow problems in general wireless networks, which reduces the multiflow problems to sequence of a sequence of computations of shortest paths and independent sets. Such paradigm offers nice trade-off between accuracy in terms the approximation bound and efficiency in terms of the running time, and are much simpler and faster. Specifically, let A be a μ-approximation algorithm for the MAC-layer problem Maximum-Weighted Independent Set (MWIS), and ε be an accuracy-efficiency trade-off parameter. The paradigm makes O(ε-2) calls to the algorithm A and Dijkstra's shortest path algorithm, and hence is faster and simpler. On the other hand, it achieves an approximation bound (1+2ε)μ, which is slightly more than the approximation bound of the algorithm A for MWIS. The broarder applicability of these algorithms are demonstrated by their applications to multiflow problems in wireless networks under the physical interference model and wireless multi-input multi-output (MIMO) networks with receiver-side interference suppression under the protocol interference model.
For various wireless networks which have explicit polynomial approximate capacity regions, this project devises a more efficient and yet effective paradigm for multiflow problems. This paradigm involves only the computation of shortest paths without computing the approximate maximum weighted independent sets.
Two former PhD student participating in this project have graduated. One became
a tenure-track assistant professor at The State University of New York at
Oneonta, and the other became a researcher at Facebook. One ongoing PhD student
and one ongoing MS student have been participating in the research. The PI
has also been volunteering for supervising a senior high school female student
from Illinois Mathematics and Science Academy on the Student Inquiry and
Research (SIR) program.
In addition, two lecture notes and the presentation slides on the project discovery
have been developed for the course "CS547-Wireless Networking" taught by the PI
at IIT:
The following paper was published and presented at IEEE Infocom 2015--2018 ACM Mobihoc 2016, and WASA 2016-2017:
P.-J. Wan, B. Xu, L. Wang, S. Ji, and O. Frieder, A New Paradigm for Multiflow in Wireless Networks: Theory And Applications. IEEE INFOCOM 2015: 1706 - 1714. (slides)
P.-J. Wan, Joint Selection And Transmission Scheduling of Point-to-Point Communication Requests in Multi-Channel Wireless Networks, ACM Mobihoc 2016: 231-240. (slides)
F. Al-Dhelaan, P.-J. Wan, and H.Q. Yuan, A New Paradigm for Shortest Link Scheduling in Wireless Networks: Theory And Applications, WASA 2016: 24-36. (slides)
P.-J. Wan, F. Al-Dhelaan, H.Q. Yuan, and S. Ji, Fractional wireless link scheduling and polynomial approximate capacity regions of wireless networks, IEEE INFOCOM 2017. (slides)
P.-J. Wan, H.Q. Yuan, X. Jia, J. Wang, and Z. Wang, Maximum-weighted subset of communication requests schedulable without spectral splitting, IEEE INFOCOM 2017. (slides)
P.-J. Wan, H.Q. Yuan, X.F. Mao, J.L. Wang, and Z. Wang, Maximum-Weighted \lambda-Colorable Subgraph: Revisiting And Applications, WASA 2017. (slides)
P.-J. Wan, H.Q. Yuan, J.L. Wang, J. Ren, and Y.-X. Zhang, Joint Selection And Scheduling of Communication Requests in Multi-Channel Wireless Networks under SINR Model, IEEE INFOCOM 2018.
In addition, the PI has given seminar talks on the results described above.
This project develops a completely new paradigm for multiflow problems in general wireless networks which is radically different from the prevailing linear programming based paradigm. Such paradigm offers nice trade-off between accuracy in terms the approximation bound and efficiency in terms of the running time, and are much simpler and faster. It has wide applications to maximizing wireless network capacity in broader classes of wireless networks.We expect our research to lead to original results that will be of interest to a number of research communities such as algorithms, information theory, and networking, and to serve as a basis for interesting future projects on multihop wireless networks. In general, this project this project addresses problems which are at the heart of technologies capable of solving very concrete needs of our society. Multihop wireless networks are expected to play a key role in solving problems such as securing our homeland, protecting our critical infrastructure, monitoring conditions in our biosphere, or in the diagnosis and treatment of illnesses. Our project is aimed at building a solid algorithmic foundation on which the transport capacity of such networks can be maximized.