Urban Wireless Mesh Network Planning: The Case of Directional Antennas

As more and more cities plan to deploy municipal wireless mesh networks to provide publicly-accessible infrastructure, it becomes critical to come up with a deployment plan that provides sufficient accessibility with financial and technological constraints. In this paper, we consider deploying the mesh routers that are equipped with directional antennas to form the mesh backbone. We propose GPSR, an efficient and near-optimal algorithm that maximizes the profit of the deployment, ensures the deployment cost is under budget, and guarantees connectivity and system robustness. Furthermore, GPSR is general enough to address many practically-encountered variants of the mesh network planning problem. Our performance evaluation shows that GPSR almost always generates the deployment plan within 95% of the optimal for all of our experiments