A Clustering Approach to Planning Base Station and Relay Station Locations in IEEE 802.16j Multi-Hop Relay Networks

In this paper, a clustering approach to solve a network planning problem for 802.16J relay networks is considered. Our clustering approach consists of three basic steps: (1) divide the nodes into k distinct clusters, (2) solve the planning problem separately for each cluster, and (3) perform a final optimization to reduce issues arising at cluster boundaries. Simulation results show that our approach is more efficient than existing approaches: solutions of equivalent quality can be found in 40% of the time. Thus our technique can be used to solve larger problems with similar hardware, or similar size problems in less time.