Gateway placement optimization in wireless mesh networks with QoS constraints

In a wireless mesh network (WMN), the traffic is aggregated and forwarded towards the gateways. Strategically placing and connecting the gateways to the wired backbone is critical to the management and efficient operation of a WMN. In this paper, we address the problem of gateways placement, consisting in placing a minimum number of gateways such that quality-of-service (QoS) requirements are satisfied. We propose a polynomial time near-optimal algorithm which recursively computes minimum weighted Dominating Sets (DS), while consistently preserving QoS requirements across iterations. We evaluate the performance of our algorithm using both analysis and simulation, and show that it outperforms other alternative schemes by comparing the number of gateways placed in different scenarios.