Robust gateway placement in wireless mesh networks

Wireless mesh networks (WMNs) are communication networks that provide wireless Internet access over areas with limited infrastructure. Each node in a WMN serves several clients in its coverage area and transfers their traffic over wireless media to a few gateway nodes that have wired connections to the Internet. In this paper, we consider the Internet gateway placement (IGP) problem along with operational problems such as routing and wireless transmission capacity allocation. To eliminate wireless interference, we adopt the spatial reuse time division multiple access (TDMA) method, in which wireless transmissions are scheduled to occur at different time slots. We also employ destination-based single path routing for its ease of implementation. We present two mixed integer linear programming (MILP) formulations, both of which jointly determine the minimum number of gateway nodes needed to support forecasted demand, the locations of these gateway nodes, the routing trees, and the time slot allocations to wireless links. These formulations differ in the flow constraints. We also present a set of valid inequalities for the formulation with the multi-commodity flow constraints. In most cases, the solution to the IGP problem is not unique. Therefore, we also introduce a local search algorithm to select the most robust solution against any demand forecast errors. On example networks, we compare the proposed formulations with and without the valid inequalities in terms of the exact solution performances and the linear programming (LP) relaxations. We also demonstrate our local search algorithm to improve robustness against forecast errors on these example networks.