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

Synopsis

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.

Personnel

PI: Dr. Peng-Jun Wan, email: wan@cs.iit.edu.

Graduate students at IIT:

Collaborators

Prof. Ophir Frieder, Dept. of Computer Science, Georgetown University, email: ophir@ir.cs.georgetown.edu.

Prof. Sai Ji, Nanjing University of Information Science And Technology, email: jisai@nuist.edu.cn.

Prof. Lei Wang, Dalian University of Technology, email: lei.wang@ieee.org.

Prof. Huaqiang Yuan, Dongguan University of Technology, email: hyuan66@163.com.

 

Discoveries

Maximizing the multiflows in general multihop wireless networks

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 boarder 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.

Shortest link scheduling and polynomial approximate capacity regions of multihop wireless networks

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.

In the next year, the project will devise more efficient and yet effective algorithms for multiflow problems in wireless networks by exploiting the polynomial approximate capacity regions constructed above. We expect that  the algorithms will involve only the computation of shortest paths without computing the approximate maximum weighted independent sets.

 

Educational Activities

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:

Publications & Outreach

The following paper was published and presented at IEEE Infocom 2015, ACM Mobihoc 2016, and WASA 2016:

In addition, the PI has given seminar talks on the results described above.

Broader Impact

 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.