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:

- Fahad Al-dhelaan, email: faldhela@hawk.iit.edu.
- Chao Ma (graduated), email: cma3@hawk.iit.edu.
- Zhu Wang (graduated), email: zwang59@hawk.iit.edu.
- Boliu Xu, email: bxu8@hawk.iit.edu.
- Haohua Du, email: hdu4@hawk.iit.edu.
- Ting Ma (graduated), email: tma11@hawk.iit.edu.

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:

**Half-Duplex Constraint**: Each node cannot transmit and receive signals at the same time.**Sender Constraint**: At each sender, the number of its transmitting streams is no more than its number of antennas.**Receiver Constraint**: At each receiver, the number of interfering streams is no more than its number of antennas.

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

- Even restricted to fully conflicting streams with
sufficiently many antennas per node so that both the
**Sender Constraint**and the**Receiver Constraint**are trivially satisfied, the {0,1}-weighted variant of the problem**MWISS**is APX-hard. Such APX-hardness is due to the**Half-Duplex Constraint**. In contrast, finding a maximum independent set of links among fully conflicting links without MIMO capability is trivially tractable. - Even restricted to node-disjoint streams which
trivially satisfies the
**Half-Duplex Constraint**and**Sender Constraint**, the problem**MWISS**remains NP-hard. Thus, the**Receiver Constraint**alone is the major source of such NP-hardness.

** Approximation Algorithms**: We have developed three efficient
constant-approximation algorithms for this problem under the following three
settings respectively:

- Constant bounded number of antennas at each node.
- Uniform interference radii but arbitrary number of
antennas.
- Uniform number of antennas but arbitrary interference
radii.

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.

- In case of uniform interference radii, we found an
intrinsic relation between maximum weakly independent set of streams and
the
*partition matroid*. Based on such relation, we designed a constant approximation algorithm adopting the divide-and-conquer framework together with the matroid greedy algorithm. - In case of uniform number of antennas, we found that
the
**Sender Constraint**is redundant with respect to the**Receiver Constraint**and thus can be dismissed. With only the**Receiver Constraint**, we were able to compute a constant-approximate weakly independent set using the linear programming relaxation and a powerful and general rounding method.

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.