Multiple-input multiple-output (MIMO) technology provides a means of boosting network capacity without requiring additional spectrum by exploiting spatially multiplexing, interference suppression, and spatial diversity. It has received widespread attention over the past decade from both industry and academic researchers, now forming a key component of nearly all emerging wireless standards. Despite the huge promise and considerable attention, a rigorous algorithm-theoretic framework for maximizing network capacity in multihop wireless MIMO networks is missing in the state of the art. One major technical obstacle is due to the complicated trade-off between spatial multiplexing and interference suppression with the limited number of antennas at each node; something which appears intractable with existing methods. This project aims at establishing a comprehensive algorithm-theoretic framework for maximizing network capacity in multihop wireless MIMO networks, including the full characterization of computational hardness, the polynomial time approximation schemes, and the practical approximation algorithms with provable performance guarantees. We shall develop new techniques and tools to effectively capitalizing the benefits of both spatial multiplexing and interference suppression.
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.
Sai Ji, Nanjing University of Information Science And Technology, email: jisai@nuist.edu.cn.
Prof. Xiaohua Jia, City University of Hong Kong, email: csjia@cityu.edu.hk.
Prof. Lei Wang, Dalian University of Technology, email: lei.wang@ieee.org.
Prof. Xiaohua Xu, Kennesaw State University, email: xxu6@kennesaw.edu.
Prof. Huaqiang Yuan, Dongguan University of Technology, email: hyuan66@163.com.
Problem Description: With the receiver-side interference suppressions, a set of streams is independent (i.e. can successfully transmit at the same time) if all the following three constraints are satisfied:
Suppose
that each stream has a non-negative weight. Our objective is to seek an
independent set of streams with maximum total weight. This problem is known as Maximum
Weighted Independent Set of Streams (MWISS).
Computational Hardness: The problem MWISS is notoriously hard due to its complicated constraints. The approximation bounds of all existing approximation algorithms developed for this problem grow linearly with the product of maximum number of antennas at individual nodes, maximum number of links incident to a node, and maximum number of links conflicting with individual links. The present significant knowledge gap between maximizing network capacity in multihop wireless MIMO networks and maximizing network capacity in multihop wireless networks without MIMO capability motivates us to address the following question: While it is expected that maximizing network capacity in multihop wireless MIMO networks is NP-hard, what are the major technical obstacles that have prevented the progress so far? This question is fully answered with the following two discoveries:
Approximation Algorithms: We have developed three efficient constant-approximation algorithms for this problem under the following three settings respectively:
The Half-Duplex Constraint is a major technical obstacle in achieving constant approximation bounds. We discovered a relaxation and extraction technique to overcome this obstacle. We introduced a notion of weak independence, which is the relaxation of independence by ignoring the Half-Duplex Constraint. An essential discovery is that from any weakly independent set, we can effectively extract an independent set of at least one quarter of its weight. An algorithmic implication by this discovery is that we only need to develop constant-approximation algorithms for maximum weakly independent set of streams.
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. By applying this paradigm to wireless MIMO networks with receiver-side interference suppression and utilizing the approximation algorithms for the MAC-layer problem of selecting a set of independent set of streams with maximum total weight, we obtained the very first constant-approximation algorithms for maximizing multiflow problems.
For the special setting of wireless multi-packet reception (MPR) networks, we also developed practical polynomial-time approximation algorithms for variants of capacity optimization problems in MPR-capable wireless networks which achieve constant approximation bounds for the first time ever. In addition, polynomial-time approximation schemes are developed for those variants in wireless networks with constant-bounded MPR capabilities.
Linear interference alignment (LIA) is one of the key interference
mitigation techniques to enhance the wireless MIMO network capacity. The
generic LIA feasibility amounts to whether or not a well-structured random
matrix with entries drawn from a continuous distribution has full row-rank almost
surely. Recently, a randomized algebraic test of feasibility was proposed in
the literature. It is a pseudo-polynomial bounded-error probabilistic algorithm
in nature, and has intrinsic limitations of requiring an inordinate amount of
running time and memory even for a moderate sized input and being prone to
round-off errors in floating-point computations. This project developed the
first deterministic combinatorial feasibility tests which are fast and robust.
We discovered necessary conditions and sufficient conditions of the generic
feasibility and develops effective and efficient tests of them based on network
flow. In certain setting, these conditions are both necessary and sufficient,
and their flow-based tests yield efficient algorithm for exact feasibility
test.
Given an instance of wireless MIMO networks and a set of link demands, the problem Shortest link scheduling (SLS) seeks a minimum-length transmission schedule of the streams along the links such that all links demands can be satisfied. Almost all of the state-of-the-art approximation algorithms for SLS in wireless networks are resorted to the ellipsoid method for linear programming exclusively. However, the ellipsoid method can require an inordinate amount of running time and memory even for a moderate sized input, and consequently is often unusable in practice. In this project, we developed a completely new paradigm for SLS in general wireless networks, which reduces the multiflow problems to sequence of a sequence of computations of 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. By applying this paradigm to wireless MIMO networks with receiver-side interference suppression and utilizing the approximation algorithms for the MAC-layer problem of selecting a set of independent set of streams with maximum total weight, we obtained the effective and efficient constant-approximation algorithms for SLS.
This project also develops another purely combinatorial paradigm for SLS
in general wireless networks. Instead of a reduction to MWIS as in the prevailing paradigm, it is based on a reduction to a
much simpler problem of selecting a cost-efficient independent subset, which
can be computed efficiently. 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 power of this paradigm was demonstrated by its applications in
single-channel single radio wireless networks under the physical interference
model, multichannel multi-radio wireless networks under the physical
interference model, and MIMO wireless networks under the protocol interference
model respectively. In these three networks, our new paradigm leads to very
efficient link scheduling algorithms, with matchable
approximations bounds. The produced link schedules by these algorithms have
explicit upper-bounds on their lengths. Such attractive feature is exploited to
construct polynomial approximate capacity regions in these three networks.
Five PhD students have been participating in the research. They read and presented a number of papers in the weekly research group meetings. Two of them have graduated: one became a tenure-track assistant professor at The State University of New York at Oneonta, and the other worked as a research scientist at Motorola. The PI has also been volunteering for supervising a senior high school student from Illinois Mathematics and Science Academy on the Student Inquiry and Research (SIR) program. In addition, the PI collaborated with Paine College at Augusta, Georgia, a historically black college and university (HBCU). During the past summers, two minority undergraduate students together with their faculty advisor from Paine College were hosted by the PI for two weeks in each summer. The research team-members introduced to them our ongoing research works on this project.
The following papers were published and presented at ACM Mobihoc 2014 and IEEE Infocom 2015 rspctively:
·
P.-J.
Wan, B. Xu, O. Frieder, S. Ji, and B. Wang, X. Xu, Capacity maximization in wireless MIMO networks with
receiver-side interference suppression. ACM MobiHoc
2014: 145-154. (slides)
· 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, F. Al-dhelaan, S. Ji, L. Wang, and O. Frieder, Flow-Based Feasibility Test of Linear Interference Alignment with Arbitrary Interference Topology. IEEE INFOCOM 2015: 1526 - 1534. (slides)
· P.-J. Wan, F. Al-dhelaan, X. Jia, B. Wang, and G. Xing. Maximizing Network Capacity of MPR-Capable Wireless Networks. IEEE INFOCOM 2015: 1805 - 1813. (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)
In addition, the PI has given seminar talks on the results described above.
The MAC-layer problem of computing an independent set of streams with maximum total weight in multihop wireless MIMO networks is notoriously hard due to its complicated constraints. All existing algorithms and protocols for this problem have poor approximation bounds growing linearly with the product of maximum number of antennas at individual nodes, maximum number of links incident to a node, and maximum number of links conflicting with individual links. The algorithms developed in this project are efficient and the first ones with constant approximation bounds. Thus, they fundamentally advance the state of the art of capacity maximization in multihop wireless MIMO networking. 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 MIMO networks. In general, this project address problems which are at the heart of technologies capable of solving very concrete needs of our society. MIMO technology provides a means of achieving extraordinary capacity growth without requiring additional spectrum to meet the ever-increasing consumer demands for higher data rates and even better performance. Our project aims at building a solid algorithmic foundation on which the fundamental benefits of MIMO technology can be capitalized.