Exact Capacity of Wireless Multihop Networks

Finding the maximum flow, or capacity, of wireless multihop networks received a considerable attention by the research community due to its importance from theoretical and practical standpoints. However, since it is NP-hard, only bounds can be found using different heuristics. In this poster we find an upper bound on the maximum flow supported by static wireless multihop networks for any load matrix and arbitrary topology in a polynomial time, via a Linear Program, by exploiting only a local interference conflict graph. By noting that interference is local, we replace the optimization problem condition of listing maximal independent sets by listing maximal cliques which improves computational complexity of the solution. Doing this, we had a quadratic programming problem to calculate the exact maximum flow, and not bounds, for any network which is polynomial for some interference models such as the Unit Disk Graph. We applied our model to an example network in the work of Jain et. al (2003) and obtained the exact maximum network flow, while Jain et. al (2003) suggests only a solution to calculate bounds for the network. The model was also applied to other networks such that the conflict-graph is not perfect, where other models fail to calculate the capacity, and we were able of obtaining the exact capacity.