Maximum MIMO Flow in wireless networks under the SINR model
Eyjólfur Ingi Ásgeirsson, Magnús M. Halldórsson, Pradipta Mitra · 2014
We present a framework for the maximum flow problem in wireless networks using the SINR interference model in combination with MIMO nodes. The performance ratio of our algorithm matches the best O(log n) approximation factor known for the pure flow problem, but avoids the impractical dependence on the ellipsoid method and features both simpler and more intuitive analysis. The objective of a maximum flow in wireless networks is to get as much information from a sender to a receiver using intermediate nodes in a multi-hop environment. The algorithm is based on an LP formulation of the flow problem, and handles gracefully all additional linear constraints. The set of constraints that can be included contains, among other, power limits, fairness between source-sink pairs, capacity limits and bounds, and the use of Multi-Input Multi-Output nodes for the source and the sink nodes, which are often the bottlenecks in a wireless flow.