In a wireless mesh network (WMN), gateways act as the bridges between the mesh backbone and the Internet, and significantly affect the performance of the whole network. Hence, how to determine the optimal number and positions of gateways, i.e., gateway deployment, is one of the most important and challenging topics in practical and theoretical research on designing a WMN. Although several approaches have been proposed to address this problem, few of them take load balancing and interference minimization into account. In this paper, we study the Load-balancing and Interference-minimization Gateway Deployment Problem (LIGDP), which aims to achieve four objectives, i.e. minimizing deployment cost, minimizing MR-GW path length, balancing gateway load and minimizing link interference. We formulate it as a multi-objective integer linear program (ILP) issue first, and then propose an efficient gateway deployment approach, called LIGDP Heuristic. The approach joints two heuristic algorithms, i.e., MSC-based location algorithm (MLA) and load-aware and interference-aware association algorithm (LIAA), to determine gateway positions and construct GW-rooted trees. Simulation results not only show that the trade-off between deployment cost and network performance can be achieved by adjusting R-hop, GW throughput and MR throughput constraints, but also demonstrate that, compared with other existing approaches, LIGDP Heuristic performs better on MR-GW path, load balancing and interference minimization without deploying more gateways.

wireless mesh networks, gateway deployment, load balancing, interference minimization