Energy-Aware Gateway Placement in Green Wireless Mesh Networks

In this letter, we address the following problem: given a mesh network deployment and $|\mathbb{G}|$ gateways to be added, what is the optimal gateway placement with the constraint of energy-minimization for green wireless mesh networks. Unlike previous research, which focuses on throughput optimization, we contribute by developing a mixed-integer linear programming (MILP) formulation, which satisfies the given flow demands while minimizing the global energy consumption of the network. The proposed solution is NP-hard; therefore, we also propose a heuristic-based greedy algorithm to efficiently solve large instances of this problem. To capture interference in the mesh network, we use the physical-interference model but employ a greedy algorithm to reduce the computation time for finding maximal independent sets. We implement both the MILP formulation and the greedy solution along with three other contemporary solutions in the area. Numerical results show that the proposed exact scheme provides the optimal result, while the greedy solution provides a solution within 5% of the optimal solution with just 1% computation time for green wireless mesh networks.