In one embodiment, a particular node in a shared media computer network may determine a set of network parameters for the network, and a timing of super-frames in the network, each super-frame having one or more frames, each frame divided into a plurality of timeslots. In addition, the particular node computes a discovery scheduling function using its own identification to determine in which particular timeslot of the frames to transmit a network discovery packet. Accordingly, the particular node may transmit the network discovery packet in the particular timeslot of the frames. In an additional or alternative embodiment, the particular node may receive a network discovery request from a requesting node. In response, the particular node determines whether it is free to reply to the network discovery request based on parameters in the network discovery request, and if free to reply, may transmit a network discovery packet to the requesting node.