Provided is a relay station relaying wireless signals between a base station and a mobile station, the relay station including: a communication unit configured to relay the wireless signals; a determination unit configured to determine whether or not it is necessary to change a cell ID of the relay station in order to avoid a collision between a cell ID of the relay station and a cell ID of the base station due to a movement of the relay station; and a control unit configured to cause a cell ID of an access point of the mobile station belonging to the relay station to be changed from a first cell ID of the relay station to a second cell ID of the relay station when the determination unit determines that it is necessary to change the cell ID.