Accession Number:



A Fast and Scalable Algorithm for Calculating the Achievable Capacity of a Wireless Mesh Network

Descriptive Note:

Technical Report

Corporate Author:

MIT Lincoln Laboratory Lexington United States

Report Date:


Pagination or Media Count:



This paper considers the problem of rapidly determining the maximum achievable capacity of a multi-hop wireless mesh network subject to interference constraints. Being able to quickly determine the maximum supported flow in a wireless network has numerous practical applications for network planners and researchers. Current approaches for determining network capacity either provide asymptotic results that are not necessarily achievable, are computationally intractable and cannot be computed quickly, or are not generalizable to different interference constraints for emerging technologies. In this paper, we presenta new algorithm to rapidly determine the maximum concurrent flow for an arbitrary number of unicast and multicast connections subject to arbitrary binary interference constraints, and provide a feasible route and schedule to support those flows. The solution provided by our algorithm is within Oomega of the optimal maximum flow, where is the maximum number of links that cannot be activated due to interference from some particular transmission. We use our algorithm to perform a network capacity analysisfor emerging wireless technologies. We compare the achievable capacity of omni-directional, single-beam and multi-beam directional networks operating at different frequencies.

Subject Categories:

  • Radio Communications

Distribution Statement: