A relay device can perform high-quality communication even in a wireless mesh network where relay devices are densely arranged and interference of wireless packets is caused. The relay device includes: a representative node determining unit (605) which determines the channel used in its own cluster for intra-cluster communication to be a channel different from the channel used in neighboring cluster for intra-cluster communication, when the communication quality of its own relay device does not meet predetermined quality and no representative node exists among neighboring nodes; a joining and removal notifying unit (607) which allows a neighboring node which is not associated with any cluster to join to its own associated cluster; and a frequency channel changing unit (609) which changes the channel used for intra-cluster communication to the channel determined by the representative node determining unit (605) of the representative node.