In this paper, an adaptive random access strategy is presented for multi-channel relaying networks to address the issue of random access of the non-real-time (NRT) services. In the proposed scheme, NRT services access the base station (BS) by first accessing the nearest relay node (RN). When collision occurs, for the sake of fast and efficient access, the user will begin a frequency domain backoff rather than randomly retry in time domain. A remarkable feature of this scheme is that the RN will adaptively determine the maximum allowed frequency backoff window at each access period. This is achieved according to the new arrival rate as well as the number of available access channels. Moreover, to alleviate the interference caused by sub-channel reuse among RNs, a fractional frequency reuse scheme is also considered. The analysis and numerical results demonstrate that our scheme achieves higher throughput, lower collision probability and lower access delay than conventional slotted Aloha as well as the scheme without frequency backoff window adaptation. In this paper, an adaptive random access strategy is presented for multi-channel relaying networks to address the issue of random access of the non-real-time (NRT) services. In the proposed scheme, NRT services access the base station (BS) by first accessing the nearest relay node (RN). When collision occurs, for the sake of fast and efficient access, the user will begin a frequency domain backoff rather than randomly retry in time domain. A remarkable feature of this scheme is that the the RN will adaptively determine the maximum allowed frequency backoff window at each access period. As is to alleviate the interference caused by sub-channel reuse among RNs, a fractional The analysis and numerical results demonstrate that our scheme achieves higher throughput, lower collision probability and lower access delay than conventional slotted Aloha as well as the scheme without frequency backoff window adaptation.