A Fast and Scalable Algorithm for Calculating the Achievable Capacity of a Wireless Mesh Network
Abstract
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 O(omega) 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 09, 2016
- Accession Number
- AD1034004
Entities
People
- Aradhana Narula-tam
- Gregory Kuperman
- Jun Sun
- Nathaniel M. Jones
Organizations
- MIT Lincoln Laboratory