Approximating Maximum Directed Flow in a Large Wireless Network

We study the maximum forwarding capacity for the relay traffic that can be transmitted through a wireless multihop network in a single direction. The problem appears as the microscopic level problem in a dense multihop network where the routing and forwarding tasks can be considered independently (separation of scales). Ultimately, the problem of finding the maximum forwarding capacity involves solving a max-flow problem in an infinite plane with an infinite dimensional scheduling vector as an additional parameter to be optimized. In this paper, we approximate the infinite network by a finite but large network consisting of nodes distributed as a spatial Poisson process, and give the problem an LP formulation assuming a Boolean interference model. The computational complexity is further reduced by relaxing the necessary and sufficient constraints and solving the LP problem with a reduced set of necessary clique constraints. This gives a new significantly tighter upper bound on the achievable forwarding capacity compared with our previous (non-achievable) upper bound corresponding to the maximum capacity in one time slot.