Enabling multi-hop wireless mesh networks with multi-input multi-output (MIMO) functionality boosts network throughput by transmitting over multiple orthogonal spatial channels (spatial multiplexing) and by performing interference cancellation, to allow links within interference range to be concurrently active. Furthermore, if the channel is in a deep fade, then multiple antenna elements at the transmitter and/or receiver can be used to transmit a single stream, thereby improving signal quality (diversity gain).

However, there is a fundamental trade-off between boosting individual link performance and reducing interference, which must be modeled in the process of optimizing network throughput. This is called the diversity-multiplexing-interference suppression trade-off. Optimizing network throughput therefore, requires optimizing the trade-off between the amounts of diversity employed on each link, the number of streams multiplexed on each link and the number of interfering links allowed to be simultaneously active in the network.

We present a set of efficient heuristics for one-shot link scheduling and stream allocation that approximately solve the problem of optimizing network throughput in a single time slot. We identify the fundamental problem of verifying the feasibility of a given stream allocation. The problems of general link scheduling and stream allocation are very closely related to the problem of verifying feasibility.

We present a set of efficient heuristic feasibility tests which can be easily incorporated into practical scheduling schemes. We show for some special MIMO network scenarios that feasibility is of polynomial complexity. However, we conjecture that in general, this problem, which is a variation of Boolean Satisfiablility, is NP-Complete.