A method for establishing and maintaining a wireless ad hoc network comprising backbone nodes which forward packets through the network and non-backbone nodes which are capable of using the network, but do not forward packets. Signaling packets containing one or more protocol support records are periodically generated and transmitted by each node to neighboring nodes and are forwarded through the network by backbone nodes. Non-network nodes are initially selected to become backbone members during a SELECTION process based on an assessment of the node's connectivity relative to its neighbors. Link quality between nodes is monitored and used during an EXPANSION process in which additional non-network nodes may become backbone members. Disconnected backbone segments are interconnected during a CONNECTION process and the network is maintained during a MAINTENANCE process by periodically assessing the value of a backbone node's membership in the backbone. Efficient multicast routing is supported over the backbone by dynamically establishing and maintaining multicast trees. Signaling packets are periodically and frequently generated, thereby facilitating rapid adaptation to network changes. Further, the signaling packets are efficiently forwarded only by backbone nodes, thereby reducing bandwidth associated with establishing and maintaining the network.