Dynamic routing in a mesh network

• US 9,565,620 B2
• Filed: 09/02/2014
• Issued: 02/07/2017
• Est. Priority Date: 09/02/2014
• Status: Active Grant

• Current Assignee: Mueller International LLC (Mueller Water Products Incorporated)
• Original Assignee: Mueller International LLC (Mueller Water Products Incorporated)
• Inventors: Dukes, Brent, Splitz, David, Magley, Dale McLeod, Grady, Robert Henry
• Primary Examiner(s): Acolatse, Kodzovi
• Application Number:
  US14/475,050
• Publication Number:
  US 20160066249A1
• Time in Patent Office: 889 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Technologies are described herein for dynamically determining and assigning parent nodes and routes for nodes in a mesh network. A host sends a command message to one or more nodes of the mesh network. The command message is configured to cause the nodes to collect communication parameters regarding neighboring nodes and to upload neighbor lists containing the communication parameters regarding the neighboring nodes to the host. The host then calculates a link score for the pairs of neighboring nodes in the mesh network based on the communication parameters in the uploaded neighbor lists and assigns one or more parent nodes to at least one of the nodes based on the calculated link scores. The host then sends a command message to the node causing the node to reconfigure based on the command message and begin communicating through the newly assigned one or more parent nodes.

Claims

1. A method comprising steps of:

entering, by a first node in a mesh network, an orphan mode;

broadcasting, by the first node, an orphan notice over the mesh network;

receiving, at a second node in the mesh network, the orphan notice;

adding, by the second node, information regarding the first node from the orphan notice to a neighbor list, the information comprising a node ID of the first node specified in the orphan notice, a receive signal strength indicator (RSSI) measurement associated with the orphan notice from the first node, and an indication that the first node is in orphan mode;

uploading, by the second node, the neighbor list to a host communicatively coupled to the mesh network; and

receiving, at the first node, an assignment of one or more parent nodes in the mesh network from the host, the assignment of the one or more parent nodes determined based on a link score calculated for the first node and the second node from the information regarding the first node in the uploaded neighbor list.

2. The method of claim 1, wherein the orphan notice is broadcast over a plurality of defined communication channels of the mesh network.

3. The method of claim 1, wherein the orphan notice is broadcast over all 50 available hailing channels of the mesh network, and wherein the first node listens for neighbor notices on the 50 available hailing channels.

4. The method of claim 1, wherein, in response to receiving the orphan notice, the second node further sends a neighbor notice to the first node, the first node adding information regarding the second node from the neighbor notice to its neighbor list.

5. The method of claim 4, wherein the first node further uploads its neighbor list to the host to be utilized in the assignment of the one or more parent nodes for the first node.

6. The method of claim 1, wherein the link score is calculated from at least the RSSI measurement specified in the information regarding the first node.

7. The method of claim 1, wherein the orphan mode is entered by the first node upon determining that the first node has not communicated successfully with an assigned parent node for some duration of time.

8. The method of claim 7, wherein the first node is a repeater in the mesh network with a valid parent assignment.

9. The method of claim 1, wherein the orphan mode is entered by the first node upon receiving an orphan mode command message from the host.

10. A non-transitory computer-readable storage medium having processor-executable instructions stored thereon that, when executed by a processor, cause the processor to:

send a first command message from a host computer to one or more nodes of a mesh network, the first command message configured to cause each of the one or more nodes to collect communication parameters regarding neighboring nodes in the mesh network and to upload a neighbor list containing the communication parameters to the host computer;

calculate a link score for at least one pair of neighboring nodes in the mesh network based on the communication parameters in the uploaded neighbor lists;

assign one or more parent nodes to at least one of the one or more nodes based on the calculated link scores; and

send a second command message to at least one of the one or more nodes, the second command message configured to cause the node to reconfigure based on the second command message and begin communicating through the newly assigned one or more parent nodes.

11. The non-transitory computer-readable storage medium of claim 10, wherein the first command message comprises an orphan mode command message, and wherein at least one node of the mesh network is configured to, upon receiving the orphan mode command message, broadcast an orphan notice over the mesh network, receive a neighbor notice from a neighboring node, and add information regarding the neighboring node from the neighbor notice to the neighbor list.

12. The non-transitory computer-readable storage medium of claim 11, wherein the neighboring node is configured to, upon receiving the orphan notice, add information regarding the at least one node to its neighbor list, and upload the neighbor list to the host computer.

13. The non-transitory computer-readable storage medium of claim 10, wherein the first command message comprises a discovery mode command message, and wherein at least one node of the mesh network is configured to, upon receiving the discovery mode command message, listen for communications between neighboring nodes on the mesh network, and, upon detecting a communication between neighboring nodes, add information regarding a source node of the communications to the neighbor list.

14. The non-transitory computer-readable storage medium of claim 10, wherein the communication parameters regarding a neighboring node comprises a node ID of the neighboring node and an receive signal strength indicator (RSSI) measurement of a communications from the neighboring node.

15. The non-transitory computer-readable storage medium of claim 14, wherein the communication parameters regarding a neighboring node further comprises a hop count and a load factor for the neighboring node.

16. The non-transitory computer-readable storage medium of claim 15, wherein calculating the link score for the at least one pair of neighboring nodes in the mesh network comprises calculating the link score based on weighted factors comprising one or more of the RSSI measurement, the hop count, and the load factor from the neighboring node in the neighbor list.

17. A system comprising:

a device operably configured in an advanced metering infrastructure (“

AMI”

) network; and

an RF communication component operably connected to the device, the RF communication component comprising a processor and a memory containing a firmware, the firmware configured to cause the processor to

receive a discovery mode command message from a host in the AMI network,

listen for communications between neighboring nodes on the AMI network,

upon detecting a communication between neighboring nodes, add information regarding a source node of the communications to a neighbor list, the information comprising a node ID of the source node and a receive signal strength indicator (RSSI) measurement of the detected communication,

upload the neighbor list to the host, and

receive from the host an assignment of one or more parent nodes in the AMI network;

wherein the assignment of the one or more parent nodes defines a route through the AMI network for uploading data from the device to the host, and wherein the assignment of the one or more parent nodes is determined based on a link score calculated for each source node from the information regarding the source node in the uploaded neighbor list.

18. The system of claim 17, wherein the RF communication component is configured to listen for communications between neighboring nodes on a plurality of defined communication channels of the AMI network for a defined period time.

19. The system of claim 17, wherein the link score is calculated from at least the RSSI measurement specified in the information regarding the source node.

20. The system of claim 17, wherein the device comprises an advanced metering device for measuring usage of a utility, and wherein the data uploaded from the device to the host comprises usage data regarding the usage of the utility.