Date Added: Oct 2011
In this paper, the authors investigate the cost-constrained incremental network planning problem in multi-hop wireless networks. Given an existing wireless network, they 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, they introduce a performance metric, which represents the tradeoff between throughput improvement and deployment cost. They then propose a Greedy Link Deployment (GLiD) algorithm using the limited-enumeration and greedy searching methods. Finally, through extensive simulations, they evaluate the performance of their algorithm in comparison with other solutions. The results show that their algorithm can perform much better than random deployment and purely greedy deployment methods.