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.
- Hai Wang, email: hwang143@hawk.iit.edu.
- Ting Ma, 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, EECS Department, University of Toledo, email: xiaohua.xu@utoledo.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.

__ 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**.

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 was 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)

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.