We propose a novel preamble allocation scheme for mobile relay stations (MRS) in order to reduce the occurrence of preamble collision. We calculate the probability of preamble collision based on trajectory information of MRSs. Then, we select a preamble considering not only the probability of preamble collision but also interference from other base stations (BS) and relay stations (RS). Simulation results show that the proposed scheme significantly reduces the occurrence of preamble collision.