Maximizing Network Capacity in Multihop Wireless MIMO Networks

Synopsis

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.

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

Discoveries

Maximizing the MAC-layer capacity in multihop wireless MIMO networks

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:

  1. Half-Duplex Constraint: Each node cannot transmit and receive signals at the same time.
  2. Sender Constraint: At each sender, the number of its transmitting streams is no more than its number of antennas.
  3. 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 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:

  1. 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.
  2. 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:

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.

Maximizing the cross-layer capacity in multihop wireless MIMO 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. 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.

Flow-based feasibility test of linear interference alignment with arbitrary interference topology

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.

Shortest Link scheduling in multihop wireless MIMO networks

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.
 

Educational Activities

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.

Publications & Outreach

The following papers  were published and presented at ACM Mobihoc 2014 and IEEE Infocom 2015 rspctively:

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

Broader Impact

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.