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, 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 O(delta) 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 10, 2016
- Accession Number
- AD1034762
Entities
People
- Aradhana Narula-tam
- Gregory Kuperman
- Jun Sun
Organizations
- MIT Lincoln Laboratory