Search

Path selection in multihop wireless networks is a hard problem. Given a performance goal, the best approach remains unclear. In hardwired networks, network flow may be maximized by using shortest path over link weights that are determined by a linear program to a multicommodity flow formulation. In this poster we generalize this linear program to include interference and mobility. We show that "In a static wireless multihop network If we route packets using any other algorithm than shortest path with links weights determined by the solution of the dual problem of maximizing the minimum spare capacity after adding the interference constraints, then the network flow saturates before reaching the maximum when we increase the demands, while we can always increase demands until we reach the maximum flow supported by the network, if we use shortest path with links weights determined as stated above. The same is true for mobile wireless multi-hop networks under protocol interference model if nodes are available within each other transmission, interference ranges within constant probabilities".

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 [1] and obtained the exact maximum network flow, while [1] 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.