The IEEE 802.16j standard proposes a multihop relay network architecture that introduces relay stations aiming at increasing the network throughput or coverage. The deployment of the relay stations is one of the most important issues that determine the network throughput. In literature, some deployment strategies have been proposed. However, none of them follows the frame structure designed in IEEE 802.16j standard. Furthermore, they did not consider the fact that the bandwidth constraints of a base station, relay stations, and mobile stations (MSs) are highly related to the locations of relays. Given a base station, $k$ relay stations, and a region that can be fully covered by the base station, this paper proposes a relay deployment mechanism aiming to determine the best deployed locations for relays so that the bandwidth requirement of MSs can be satisfied while the network throughput can be significantly improved. Performance study reveals that the proposed relay deployment mechanism can improve the network throughput as compared with the existing approaches.
