Methods and apparatus for forming and maintaining an ad hoc mesh network suitable for reliable voice and data communications in underground, industrial and other hazardous environments. This invention includes support for cooperative negotiation of dedicated transmission bandwidth for all fixed network nodes, determination of network time synchronization without a pre-determined time master, discovery and merging of adjacent ad hoc mesh networks, and routing techniques for voice, data and network status packets which react instantaneously to network topology changes. Furthermore this invention provides a reliable communication network for mobile nodes carried by personnel and sensor nodes that are fixed or mobile that supports voice, data and tracking/situation awareness. A current application for this technology is a coal mine communication system with an operations center to dispatch, monitor and control coal mine operation including communication and location of mine personnel, and environmental conditions in the mine.