Achieving Minimum-Routing-Cost Maximum-Flows in Infrastructure Wireless Mesh Networks
A multi-commodity Minimum-Cost Maximum-Flow algorithm for routing multiple unicast traffic flows in infrastructure wireless mesh networks, represented as commodities to be routed in an undirected or directed graph, is presented. The routing-cost per edge can be any metric, i.e., a delay, a SNR, etc. To minimize resource-usage and transmission power, the routing-cost is formulated as a Bandwidth-Distance product, where high-bandwidth backhaul flows are routed over shorter distance paths. The routing algorithm requires the formulation of two Linear-Programming (LP) problems. The first LP performs constrained multi-commodity flow maximization, where the traffic flowing between any source/destination pair is constrained to a sub-graph of the original graph to enforce distance constraints.