IoE devices signal association requests to relay devices during association slots. An IoE device receives a discovery broadcast from a relay device, listing available tones for association. The IoE device sends a first association request to the relay device using a tone selected from the list. The relay device returns a first response. The IoE device randomly selects a tone from a channel and sends a second request to the relay device with it. A second response is sent to the IoE device after contention. The IoE device creates a list of available tones and sends it to the relay device. An overlapping tone is selected. The relay device sends the selected tone to the IoE device for subsequent data communication. If there is no overlap, the relay device may suggest available tones for use in a subsequent association request. Other aspects, embodiments, and features are also claimed and described.