WIMAX? A case study on minimizing construction cost for IEEE 802.16j multi-hop relay networks

The telecommunication service providers regard the fixed WiMAX (Worldwide Interoperability for Microwave Access) as a solution of last mile problem, but its coverage range is not ideal. The current placement of fixed infrastructure and mobile 802.16 networks still exists many problems, such as non-light-of-sight (NLOS) connections, low signal to noise ratio (SNR) and coverage holes which bring shadowing effects. In order to solve the above-mentioned embarrassed problems, the IEEE 802.16j is proposed and aimed to extend the transmitting area by using relay technologies. Relay Station (RS) can be thought as a lightweight base station (BS) in 802.16j networks. The coverage problem in IEEE 802.16j networks is defined based on integer linear programming. We also propose the Supergraph Tree algorithm to deploy the base stations and relay stations at the lowest cost position to support desired utilities and constrained by deployment limitations. The proposed algorithm is formulated based on graph theoretic technique, and analyzed with the simulation results. The results show the proposed algorithm provides the lowest construction cost with different network topologies.