Distributed ad hoc mesh network protocol for underground mine and hazardous area communications

• US 9,179,475 B2
• Filed: 03/20/2009
• Issued: 11/03/2015
• Est. Priority Date: 03/20/2009
• Status: Active Grant

• Current Assignee: Innovative Wireless Technologies Inc.
• Original Assignee: Innovative Wireless Technologies Inc.
• Inventors: Koleszar, Luke, Harrison, Steve, Dechant, Tim, Carpenter, Paul, Schmidt, Paul
• Primary Examiner(s): Rutkowski, Jeffrey M
• Assistant Examiner(s): Ohri, Romani
• Application Number:
  US13/257,378
• Publication Number:
  US 20120008542A1
• Time in Patent Office: 2,419 Days
• Field of Search: 370/312, 370328-336, 370/345, 370/352, 370/437, 370/445, 370447-448, 370/461, 370/468, 455/41.2, 455/447, 713/168
• US Class Current: 1/1
• CPC Class Codes: H04L 45/32 Flooding denial of service attacks H04L63/1458
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 74/02 Hybrid access
• CPC Class Codes: H04W 84/22 with access to wired networks

Abstract

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.

Claims

1. A method for implementing a communications network protocol suitable for reliable voice and data communications in an underground, industrial, or hazardous area comprising:

providing a wireless mesh network (WMN) comprising ad hoc mesh nodes that automatically form and re-form in clusters to provide wireless network communications to support voice, data, text and network service for personnel working in the hazardous area;

wherein the wireless mesh network (WMN) comprises fixed mesh nodes (FMNs) and mobile nodes and each FMN provides creation and maintenance of the WMN by coordinating individual clusters within the WMN and routing data through the WMN between mobile nodes and a Gateway node for access to and/or from a remote Network Operations Center;

establishing dedicated bandwidth transmission opportunities for each FMN in a given cluster to forward packets to a neighbor node in the cluster and to establish contention-based transmission opportunities for the FMNs and the mobile nodes to join the cluster;

establishing contention-free transmission opportunities by providing a two-way medium for each node with a bonded frequency pair and associated contention-free time slot to provide a guaranteed time period during which an FMN transmits network packets to neighboring FMN(s) and to mobile units using the FMN as a parent to, wherein format for the contention-free time slot depends on voice or data dedication;

establishing contention-based transmission opportunities to join the cluster by providing a two-way medium for each node with a bonded frequency pair and associated contention-based time slot, wherein format for the contention-based time slot depends on voice or data dedication;

wherein distributing application layer packets is performed with high reliability and low latency to maintain reliable voice and data communications with mobile nodes carried by personnel and fixed or mobile sensors within the hazardous area and also with remote operation;

providing an intelligent flood routing technique with dynamic packet routing to ensure that at least one mobile node can seamlessly roam within the ad hoc mesh network;

wherein the intelligent flood routing technique immediately reacts to a mobile node roaming freely through the ad hoc mesh network and to removal of one or more FMNs with minimal or no loss of data since it does not establish static or semi-static routes for communication packets from a given source to a given destination;

wherein the intelligent flood routing technique eliminates circular loops and duplicate voice packets by storing a history of data packet sequence numbers and voice packet timestamps to remove large amounts of redundant traffic associated with flood routing wherein each FMN and each mobile node contains a communications network protocol for automatically forming an association with one or more neighbor FMNs, and wherein the ad hoc mesh network is based on cooperative negotiation and a dynamic parent-child relationship between nodes for 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 to network topology changes, such that when a communications link in the ad hoc mesh network degrades or fails, another FMN is automatically designated;

wherein when quality of a link between a mobile node and a parent FMN has degraded such that it is below a programmable threshold of acceptable operation, the mobile node seeks another parent which can provide a higher quality communication link;

wherein each fixed node and mobile node is monitored and managed at the remote Network Operations Center for dispatch, remote supervision, and tracking of personnel, as well as, monitoring, asset control, and management of wireless sensors and equipment;

wherein the ad hoc mesh network comprises at least one node cluster with (i) a plurality of peer-to-peer fixed mesh nodes (FMNs), one of which is a time master node, and (ii) at least one mobile mesh radio node;

establishing a super-frame time interval for all nodes in a cluster, wherein the super-frame time interval is time synchronized with the time master node for the cluster based on node ID ranking, and wherein child nodes will synchronize to their respective parent nodes'"'"' slot timing thus inheriting the time master'"'"'s timing with some offset due to propagation delay;

wherein when a communications link in the ad hoc mesh network degrades or fails, another FMN is automatically designated as time master node based on node ID ranking;

establishing at least two time slots in a primary channel and secondary channel within the super-frame time interval;

assigning at least one of the time slots as a contention-based time slot for transmitting data to form parent-child associations to join the ad hoc mesh network by one or more of the plurality of FMNs and/or the at least one mobile mesh radio node;

assigning at least one of the time slots as an FMN to FMN contention-free time slot for transmitting network packets from one or more of the FMNs to a neighboring FMN that will use a transceiver to tune to frequencies associated with a transmitting FMN and receive packets and/or to any mobile mesh radio node associated with an FMN that will use a transceiver to tune to frequencies associated with a transmitting FMN and receive packets;

wherein for an FMN-to-FMN time slot not assigned to a neighbor, a node will use both transceivers to scan for other clusters to provide an improved time metric; and

wherein each FMN will periodically puncture its own FMN-to-FMN time slot as well as a neighbors'"'"' assigned time slot(s) and contention access time slot to perform a scan operation for other clusters to provide an improved time metric.

2. The method of claim 1, wherein each of the at least one FMN to FMN time slots creates a reliable wireless digital communication to one or more neighbor nodes consisting of:

at least one pre-guard time slot to allow for clock drift between nodes;

at least one power amplifier ramp time slot to allow the FMN to reach full output power;

at least one primary time slot to transmit network packets to one or more listening neighbors;

at least one idle time slot for FMN power down of the FMN'"'"'s transmitter to conserve power;

at least one sync time slot to aid scanning FMNs or mobile nodes to find and synchronize with the ad hoc mesh network; and

at least one post-guard time slot to turn off the FMN'"'"'s transmitter and switch to receive mode.

3. The method of claim 1, wherein each fixed mesh node (FMN) transmits and receives over a pair of bonded, time-synchronized RF channels, one of which is designated as a digital voice channel and a second of which is designated as a digital data channel to provide quality of service mechanism and prevent an FMN from attempting to receive on one channel while the FMN is transmitting on the second channel.

19. The method of claim 1, further comprising of a periodic scanning operation to discover active nodes of another node cluster having overlapping time slots to obtain different associations between nodes to re-form the at least one node cluster such that individual nodes change from one node cluster to another node cluster and wherein the periodic scanning operation is performed during unused time slots, or by capturing a time slot of one of the at least one fixed or at least one mobile mesh radio nodes and replacing the operation otherwise assigned to a captured time slot with the periodic scanning operation.

20. The method of claim 1, further comprising of seamless data packet routing within the ad hoc mesh network, each packet having a packet header, with the seamless packet routing comprising of:

analyzing each of the packet headers including timestamp and sequence number;

recording a history of packet sequence numbers and packet timestamps;

determining based on the packet header whether to forward the packet to adjacent nodes;

discarding packets with the same sequence number before a programmable timeout period to eliminate circular loops and duplicate packets; and

flood routing non-redundant packets to adjacent nodes in the ad hoc mesh network.

21. The method of claim 1, further comprising of seamless roaming by one or more of the at least one mobile mesh radio nodes by measuring quality of a channel link between the mobile mesh radio node and a parent FMN to which the mobile mesh radio node is connected as compared with quality of available channel link with other FMNs, such that the mobile mesh radio node automatically selects and connects to a different FMN having a better quality channel link available as the mobile mesh radio node travels through the ad hoc mesh network.

4. A method for implementing a wireless digital communications network protocol for critical voice, data and real-time monitoring of conditions and equipment in an underground hazardous environment, the method comprising:

providing an ad hoc mesh network with a reliable two-way medium based on cooperative negotiation for establishing dedicated transmission opportunities to forward packets in an efficient manner as well as contention-based transmission opportunities to join;

wherein the ad hoc mesh network comprises at least one node cluster having a plurality of peer-to-peer fixed mesh nodes (FMN) and at least one mobile mesh radio node wherein each FMN and the at least one mobile mesh radio node contains the said communications network protocol to automatically form an association with one or more neighbor FMN'"'"'s;

providing an intelligent de-centralized flood routing technique with dynamic routing to ensure that the at least one mobile mesh radio node can seamlessly roam throughout the ad hoc mesh network;

providing uni-cast and multi-cast voice, text and data packet transmissions;

providing a combined wireless and wired emergency communications system, including the ad hoc mesh network adapted for use with the communications network protocol;

establishing at least one super-frame time interval within the communications network protocol, each of which is of equal duration and each of which is time synchronized with a designated FMN time master for each cluster using a dynamic parent-child relationship among the FMNs that is not pre-determined;

establishing at least two time slots within each said super-frame time interval;

assigning at least one of said at least two time slots as a contention access period (CAP) time slot for transmitting data to form associations into the ad hoc mesh network by one or more of the plurality of FMN'"'"'s and/or the at least one mobile mesh radio node;

assigning at least one of said at least two time slots as an FMN to FMN contention-free time slot for transmitting network packets from one or more of the plurality of FMN'"'"'s to neighboring FMN'"'"'s of the plurality of FMN'"'"'s and/or to any mobile mesh radio nodes with which the FMN is associated;

wherein each of the at least one CAP time slots is formatted into at least one CAP data time slot or at least one CAP voice time slot to receive packets from transmitting mobile mesh radio nodes or other FMNs which are attempting to join the at least one node cluster, or scan for other node clusters wherein each CAP time slot further comprises;

at least one data TX on guard time slot for a radio transmitting in the CAP time slot to turn the radio'"'"'s transmit circuitry on;

at least one data physical layer (PHY) frame time slot to transmit network packets to one or more listening neighbors;

at least one voice PHY frame time slot;

at least one data idle time slot after the transmitting radio has transmitted a last bit of variable length data; and

at least one data TX off time slot for a radio transmitting in the CAP time slot to turn the radio'"'"'s transmit circuitry off.

5. The method of claim 4, wherein each said data PHY frame time slots and each said voice PHY frame time slots further comprises:

at least one PHY header frame for bit synchronization of the data packet; and

at least one media access control (MAC) frame to provide control and error correction functions.

6. The method of claim 5, wherein each said PHY header frame further comprises:

at least one preamble frame encoded as a set of alternating 1 and 0 bits to provide a means for receiving radios to reliably obtain bit synchronization on an incoming bit stream;

at least one sync frame consisting of a unique bit pattern which is preconfigured into all devices which is used by a receiving radio to obtain slot synchronization; and

at least one length frame which indicates to a receiver a number of bytes to expect in the MAC frame.

7. The method of claim 5, wherein each said MAC frame further comprises:

at least one frame control frame which informs the receiving radio of a purpose and format of a remainder of the MAC frame;

at least one sequence number frame which allows for acknowledgement of individual MAC packets and for filtering of duplicate packets where the sequence number frame is set by a transmitter of the packet;

at least one destination address frame that specifies a network address of an intended recipient of the packet;

at least one source address frame that specifies a network address of a transmitting unit;

at least one extended header frame to provide a mechanism by which a sender can dynamically expand a MAC header with additional network information when needed;

at least one MAC payload frame which is context dependent; and

at least one cyclic redundancy check (CRC) frame which provides the receiver with a method for detecting bits errors that occurred in demodulation of data bits in other frames.

8. The method of claim 7, wherein each said frame control frame further comprises:

at least one MAC frame type frame that indicates a purpose of the MAC frame and a format of the MAC payload frame, wherein MAC frame types are selected from single data frames, concatenated data frames, and sync frames;

at least one security enabled frame which indicates whether or not MAC layer security is enabled;

at least one frame pending frame which indicates whether a sending unit has additional frames to send to the same destination address;

at least one acknowledge (ACK) request frame which indicates whether the sending unit is requesting a MAC layer acknowledgement of this frame;

at least one intra-PAN frame which is reserved for future intra-PAN communications;

at least one extended header indication flag frame which, when set to true, indicates whether or not one or more extended header frames follows the Source Address frame;

at least one scan notify frame which indicates whether or not the transmitter will be performing a scan operation in the next time slot or will be performing a normal transmission in the next time slot;

at least one retry frame which indicates whether or not the frame is a first transmission or a subsequent transmission;

at least one destination mode frame which indicates a number of bits in the Destination Address frame;

at least one power control frame indicates a power level at which the transmitter is transmitting the packet; and

at least one source mode frame which indicates a number of bits in the Source Address frame.

9. The method of claim 8, wherein if a flag of said extended header indication flag frame is set to true, each said extended header frame further comprises at least one extended header frame type selected from the group consisting of:

slot info header frame,

piggyback ACK header frame which is used by the transmitting unit to acknowledge a previously received unicast packet,

piggyback grant header frame which is used by the transmitting unit to indicate which nodes are allowed to transmit in a next first level CAP time slot,

power control header frame which is used to communicate a current power setting of the transmitter, and

future grant header frame which is used to reserve CAP time slots for the upstream two slots in the future.

10. The method of claim 9, wherein each said slot info header frame further comprises:

at least one ACK map frame used to acknowledge multicast packets which have been received by the FMN transmitting a Slot Info Extended Header;

at least one channel frame which indicates a logical channel on which the frame is being transmitted, the at least one channel frame, in combination with slot and super-frame numbers, can be used to synchronize to a transmitting unit hopping sequence if frequency hopping is used;

at least one cycle slot number or foster rotation frame consisting of a parent slot number frame, a foster rotation number frame, and a slot rotation cycle frame;

at least one long slot number frame indicating a current value of a 16 bit slot number;

at least one time master frame indicating an ID of the time master FMN of the node cluster to which the transmitting unit is a member; and

at least one time hops frame indicating a number of hops to the time master of the node cluster.

11. The method of claim 10, wherein each cycle slot number or foster rotation frame further comprises:

at least one parent slot number frame which advertises whether the transmitting unit is a fostering mobile mesh radio node or an FMN;

at least one foster rotation number frame which advertises a future position of the voice and data CAP time slots for a mobile mesh radio node which is being fostered; and

at least one cycle slot rotation cycle frame which is used by a fostering mobile mesh radio node to advertise which slot rotation schedule the fostering mobile mesh radio node is currently employing.

12. The method of claim 9, wherein each said piggyback ACK header data frame further comprises:

at least one sequence number frame indicating a sequence number of a packet being acknowledged;

at least one address frame indicating a Source ID which was received in the packet being acknowledged; and

at least one received signal strength indication (RSSI) frame with a received signal strength at which the packet being acknowledged was received.

13. The method of claim 9, wherein each piggyback grant header frame is configured to reserve bandwidth for any one of the nodes having multiple packets to send and wherein each piggyback grant header frame further comprises at least four address frames to specify either a unicast address if a corresponding upstream time slot is reserved for a unicast transmission or a special broadcast address if a corresponding upstream time slot is to be used as a CAP slot.

14. The method of claim 9, wherein each future grant header frame is configured to prevent an FMN from transmitting in a next CAP time slot and missing the FMN'"'"'s guaranteed grant coming up in a time slot after that and wherein each future grant header frame further comprises at least four address frames to specify either a unicast address if a corresponding time slot is reserved for a unicast transmission or a special broadcast address if the corresponding time slot is to be used as a CAP slot.

15. The method of claim 7, wherein each said MAC payload frame is one type selected from the group consisting of single data frame type, concatenated data frame type, and sync frame type where:

the single data frame type is used to transfer one and only one network packet between units;

the concatenated data frame type is used to transfer zero, one or more network packet frames between units; and

the sync frame type is sent during an FMN-to-FMN time slot to facilitate adjacent FMNs and mobile mesh radio nodes in finding the ad hoc mesh network.

16. The method of claim 15, wherein said single data frame type of said MAC payload frame comprises a single network packet.

17. The method of claim 15, wherein said concatenated data frame type of said MAC payload frame further comprises:

at least one length frame indicating a number of octets in a corresponding network packet frame; and

at least one network packet frame containing an actual application layer information being transferred.

18. The method of claim 15, wherein said sync frame type of said MAC payload frame further comprises:

at least one time master frame which is set to a network ID of a current time master FMN of the transmitting unit;

at least one slot number frame which is set to a current slot number for a cluster to which the transmitting unit belongs; and

at least one channel number frame which is set to a logical channel number on which the sync frame type is being transmitted.

22. A method for implementing a communications network protocol comprising:

providing a combined wireless and wired emergency communications system with an ad hoc mesh network with two-way medium for establishing contention-free dedicated transmission opportunities to forward packets as well as contention-based transmission opportunities to join;

wherein the ad hoc mesh network comprises at least one node cluster with (i) a plurality of peer-to-peer fixed mesh nodes (FMNs), one of which is a time master node, and (ii) at least one mobile mesh radio node;

wherein each FMN and each mobile mesh radio node contains a communications network protocol for automatically forming an association with one or more neighbor FMNs, and wherein the ad hoc mesh network is based on cooperative negotiation and a dynamic parent-child relationship between nodes, such that when a communications link in the ad hoc mesh network degrades or fails, another FMN is automatically designated as the time master node;

providing an intelligent flood routing technique with dynamic packet routing to ensure that the at least one mobile mesh radio node can seamlessly roam throughout the ad hoc mesh network formed by the FMNs;

establishing a super-frame time interval for all nodes in a cluster, wherein the super-frame time interval is time synchronized with the time master node for the cluster;

establishing at least two time slots within the super-frame time interval;

assigning at least one of the time slots as a contention-based time slot for transmitting data to form associations to join the ad hoc mesh network by one or more of the plurality of FMNs and/or the at least one mobile mesh radio node; and

assigning at least one of the time slots as an FMN to FMN contention-free time slot for transmitting network packets from one or more of the FMNs to a neighboring FMN and/or to any mobile mesh radio node with which an FMN is associated;

wherein each of the at least one FMN to FMN time slots creates a reliable wireless digital communication to one or more neighbor nodes consisting of;

at least one pre-guard time slot to allow for clock drift between nodes;

at least one power amplifier ramp time slot to allow the FMN to reach full output power;

at least one primary time slot to transmit network packets to its listening neighbors;

at least one idle time slot for FMN power down of its transmitter to conserve power;

at least one sync time slot to aid scanning FMNs or mobile nodes to find and synchronize with the ad hoc mesh network; and

at least one post-guard time slot to turn off its transmitter and switch to receive mode.