Cost-Constrained Incremental Network Planning in Multi-Hop Wireless Networks

In this paper, we investigate the cost-constrained incremental network planning problem in multi-hop wireless networks. Given an existing wireless network, we study the problem of how to add new wireless links to improve the network performance under the deployment cost constraint. After formulating the problem as COst-constrained Incremental Network (COIN) problem, we introduce a performance metric, which represents the tradeoff between throughput improvement and deployment cost. We then propose a Greedy Link Deployment (GLiD) algorithm using the limited-enumeration and greedy searching methods. Finally, through extensive simulations, we evaluate the performance of our algorithm in comparison with other solutions. The results show that our algorithm can perform much better than random deployment and purely greedy deployment methods.