During route discovery in an ad-hoc communication network, an overlay transceiver (104) determines a plurality of "seed" nodes that lie between the source and the destination node. The seed nodes are notified of the desire to discover a route between the source and the destination node. Once notified, the seed nodes immediately broadcast route discovery messages. All nodes (101) within the underlay communication system (110) periodically listen for route discovery messages. If any node within the underlay communication system (110) receives a route discovery message having the same route identification, route information between the two seeds will be provided to the overlay transceiver (104), giving the overlay communication system a "path" between the seeds. Once the overlay transceiver (104) receives route information between all seeds, it then determines an appropriate route between source and destination devices, and broadcasts this information to the source and the destination devices.