A relay node in a mesh network receives a plurality of broadcasted path request (PREQ) messages. The relay node updates cluster information in a cluster table of the relay node based on the received PREQ messages. This cluster information identifies a cluster transmitter node and a list of cluster receiver nodes that describes a path from the cluster transmitter node to the relay node via the cluster receiver nodes. The relay node receives a Path Reply (PREP) message, and in response, transmits a modified PREP message created based on the received PREP message.