A Fast and Scalable Algorithm for Calculating the Achievable Capacity of a Wireless Mesh Network
MIT Lincoln Laboratory Lexington United States
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, including quickly visualizing capacity limits of a wireless network, benchmarking the performance of wireless protocols, and rapidly determining the instantaneous capacity of various network topologies or different snapshots of a mobile network. 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 present a new algorithm to rapidly determine the maximum concurrent flow for an arbitrary number of unicast and multicast connections subject to general interference constraints, and provide a feasible route and schedule for those flows. The solution provided by our algorithmis within Odelta of the optimal maximum flow, where delta is the maximum number of users that are blocked from receiving due to interference from a given transmission. We then use our algorithm to perform a network capacity analysis comparing different wireless technologies, including omni-directional, directional, and multi-beam directional networks.
- Numerical Mathematics
- Computer Systems