Route and link evaluation in wireless mesh communications networks

• US 7,969,889 B2
• Filed: 03/03/2010
• Issued: 06/28/2011
• Est. Priority Date: 06/15/2007
• Status: Active Grant

• Current Assignee: Itron Networked Solutions, Inc. (Itron, Inc.)
• Original Assignee: Silver Spring Networks, Inc. (Itron, Inc.)
• Inventors: van Greunen, Jana, Hughes, Sterling, San Filippo, William E. III, Vaswani, Raj, Flammer, George III
• Primary Examiner(s): Rao; Seema S
• Assistant Examiner(s): Russell; Wanda Z
• Application Number:
  US12/716,678
• Publication Number:
  US 20100157838A1
• Time in Patent Office: 482 Days
• Field of Search: 370/241
• US Class Current: 370/238
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/08 based on transmission power
• CPC Class Codes: H04W 40/246 Connectivity information discovery

Abstract

Methods and systems for providing a network and routing protocol for utility services are disclosed. A method includes discovering a utility network. Neighboring nodes are discovered and the node listens for advertised routes for networks from the neighbors. The node is then registered with one or more utility networks, receiving a unique address for each network registration. Each upstream node can independently make forwarding decisions on both upstream and downstream packets, i.e., choose the next hop according to the best information available to it. The node can sense transient link problems, outage problems and traffic characteristics. Information is used to find the best route out of and within each network. Each network node maintains multi-egress, multi-ingress network routing options both for itself and the node(s) associated with it. The node is capable of several route maintenance functions utilizing the basic routing protocol and algorithms.

Claims

1. A method of communicating data between nodes in a network, comprising:

sending, from a first node to a second node, a polling communication to determine if the second node is available;

receiving, by the first node, a first acknowledgement, the first acknowledgement indicating receipt of the polling communication by the second node and further indicating that the second node is available and listening for evaluation data to be sent from the first node;

based on receiving the first acknowledgement, which indicates that the second node is available and listening for the evaluation data to be sent from the first node, sending, from the first node, the evaluation data to the second node;

receiving, by the first node, a second acknowledgement, indicating that the second node has received the evaluation data sent from the first node;

calculating a success percentage between the first and second nodes based on whether the first node receives the second acknowledgement or whether the first node fails to receive the second acknowledgement; and

using the calculated success percentage to determine a link cost between the first node and the second node and, further, using the determined link cost in making routing decisions within the network.

2. The method of claim 1, comprising generating a random backoff time after which a re-transmission of the polling communication occurs in the event the first node fails to receive at least one of the first acknowledgement and the second acknowledgment from the second node.

3. The method of claim 2, wherein the random backoff time is generated in a geometrically increasing window.

4. The method of claim 1, wherein the step of calculating the success percentage comprises calculating an exponentially weighted moving average.

5. The method of claim 1, comprising constructing a look-up table comprising the calculated success percentage and a link evaluation transaction time corresponding to the amount of elapsed time from sending the polling communication to receiving the second acknowledgment by the first node.

6. The method of claim 5, wherein the look-up table is kept in increments of 4% of calculated success percentage.

7. The method of claim 5, comprising calculating a one-directional link cost from the first node to the second node based on the link evaluation transaction time for a given success percentage.

8. The method of claim 7, comprising calculating a final link cost based on the one-directional link cost and a link cost from the second node to the first node based on the link evaluation transaction time for a given success percentage.

9. The method of claim 8, comprising calculating a path cost by adding together the final link cost for each of a plurality of links over a path.

10. The method of claim 1, wherein the calculation of the success percentage is performed by the first node.

11. The method of claim 10, wherein the first node calculates a success percentage for each neighbor node with which it has a direct communication link.

12. The method of claim 1, wherein each node in the network calculates a success percentage for communications with at least one neighbor node with which it has a direct communication link.

13. A method of communicating data between nodes in a network, comprising:

sending, from a first node to a second node, a polling communication to determine if the second node is available;

receiving, by the first node, a first acknowledgement, the first acknowledgement indicating receipt of the polling communication by the second node and further indicating that the second node is available and listening for evaluation data to be sent from the first node;

based on receiving the first acknowledgement, which indicates that the second node is available and listening for the evaluation data to be sent from the first node, sending, from the first node, the evaluation data to the second node;

receiving, by the first node, a second acknowledgement, indicating that the second node has received the evaluation data sent from the first node;

calculating a success percentage between the first and second nodes based on whether the first node fails to receive at least one of the first and second acknowledgements; and

using the calculated success percentage and a transaction time to determine a link cost between the first node and the second node, wherein the transaction time is indicative of a time difference between a time at which the polling communication is sent from the first node and a time at which the second acknowledgment is received by the first node, and, further, using the determined link cost to make routing decisions within the network.

14. The method of claim 13, further including the step of generating a table that contains a plurality of success percentages and a respective transaction time for each of the success percentages.

15. The method of claim 13, further including:

generating a back-off time when the first node fails to receive at least one of the first and second acknowledgments; and

when the back-off time expires, repeating the steps of sending the polling communication, and sending the evaluation data if the first acknowledgment is received in response to the re-sent polling communication.

16. The method of claim 15, wherein, for each successive failure of the first node to receive at least one of the first and second acknowledgments, generating a successively larger back-off time and repeating the sending steps after the back-off time expires.

17. The method of claim 16, further including the step of generating a table that contains a plurality of success percentages and a respective transaction time for each of the success percentages.

18. The method of claim 17, wherein each of the respective transaction times includes a back-off time that is associated with the corresponding success percentage for that transaction time.