Abstract
Multihop relay (MR) technology is one of the most promising technologies that provide performance enhancement to the existing network systems. To achieve the maximal system performance, most current research allocates resources in a dynamic manner. However, in MR networks, the issues of path selection and spatial reuse will massively increase the complexity of resource scheduling. As a result, the majority of dynamic scheduling schemes might be not applicable in practical implementation due to high computation complexity. In this paper, to reduce the scheduling complexity while achieving near-optimal system throughput, we propose a constant-time repacking and borrowing-based resource scheduling (RBRS) algorithm for IEEE 802.16j MR networks. In the repacking phase of RBRS, the connection which served with high-cost path can be handed off to low-cost path and thus increase the number of available resources. In the borrowing phase, the overloaded cells are capable of borrowing resources from the under-loaded cells and thus the resource utilization can be further improved. Since both the repacking and borrowing processes are executed only with computation overhead of the selection operation, RBRS can make each scheduling decision in constant time. Simulation models are developed to investigate the performance of RBRS. The simulation results indicate that RBRS is at least 8.91 times faster than the state-of-the-art dynamic scheduling scheme while yielding near-optimal throughput. Even in the asymmetric environments, RBRS strikes an excellent balance between the system throughput and scheduling computation time.