Abstract: | In this paper, the coverage problem of network planning in mobile multi‐hop relay networks is defined on the basis of integer linear programming. In order to provide desired utilities and also meet deployment limitations for network planning, we propose a supergraph tree algorithm to place base stations and relay stations at the lowest cost position. Furthermore, another algorithm for avoiding the interference between base stations, which is called interference aware tree algorithm is also proposed. Both the proposed algorithms are formulated on the basis of a graph theoretic technique and analyzed in the simulation results. The results show that the supergraph tree algorithm provides the lowest construction cost with different network scenarios, and the interference aware tree algorithm provides the highest communication quality for mobile multi‐hop relay infrastructure‐based communication network planning. Copyright © 2013 John Wiley & Sons, Ltd. |