ISSN : 1796-2056
Volume : 1    Issue : 3    Date : July 2006

Gateway Deployment optimization in Cellular Wi-Fi Mesh Networks
Rajesh Prasad and Hongyi Wu
Page(s): 31-39
Full Text:
PDF (532 KB)

With the standardization of IEEE 802.11, there has been an explosive growth of wireless local area
networks (WLAN). Recently, this cost effective technology is being developed aggressively for
establishing metro-scale “cellular Wi-Fi” network to support seamless Internet access in the urban
area. We envision a large scale WLAN system in the future where Access Points (APs) will be
scattered over an entire city enabling people to use their mobile devices ubiquitously. The problem
addressed in this paper involves finding the minimum number of gateways and their optimal
placement so as to minimize the network installation costs while maintaining reliability, flexibility
and an acceptable grade of service. The problem is modeled taking a network graph, where the
nodes represents either the Access Points of IEEE 802.11 or wired backbone gateways. In this
paper, we present two methods (1) an innovative approach using integer linear programming (ILP)
for gateway selection in the cellular Wi-Fi network, and (2) a completely new heuristic
(OPEN/CLOSE) to solve the gateway selection problem. In the ILP model, we developed a set of
linear inequalities based on various constraints. The ILP model is solved by using lp-solve, a
simplex-based software for linear and integer programming problems. The second approach
is an OPEN/CLOSE heuristic, tailored for cellular Wi-Fi, which arrives at a sub-optimal solution. Java
programming language is used for simulation in OPEN/CLOSE heuristic. Extensive simulations are
carried out for performance evaluation. Simulation results show that the proposed approaches can
effectively identify a set of gateways at optimal locations in a cellular Wi-Fi network, resulting in an
overall cost reduction of up to 50%. The technique presented in this paper is generalized and can
be used for gateway selection for other networks as well.

Index Terms
Cellular Wi-Fi, IEEE 802.11, gateway selection, gateway placement, linear programming, wireless
mesh network.