Optimizing deployment of Internet gateway in Wireless Mesh Networks

In a Wireless Mesh Network (WMN), Mesh Routers (MRs) are interconnected by wireless links and constitute a wireless backbone to provide ubiquitous high-speed Internet connectivity for mobile clients (MCs). The wireless backbone is tightly integrated with the Internet by some selected nodes called as Internet Gateways (IGWs). An IGW has more capabilities than a simple MR and is more expensive. In this paper, we address the IGW deployment problem which is shown to be NP-hard. We first formulate it as a linear program (LP) issue, then develop two heuristic algorithms: Degree based Greedy Dominating Tree Set Partitioning (Degree based GDTSP) and Weight based Greedy Dominating Tree Set Partitioning (Weight based GDTSP), for the purpose of cost-effective IGW deployment. We evaluate the effectiveness of these two algorithms by extensive simulations and comparisons with two major approaches.