ROUTE AND LINK EVALUATION IN WIRELESS MESH COMMUNICATIONS NETWORKS

• US 20090003232A1
• Filed: 06/27/2008
• Published: 01/01/2009
• 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
• Granted Patent: US 7,940,669 B2
• Time in Patent Office: Days
• US Class Current: 370/252
• 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 route evaluation in a network, comprising:

sending, from a source node to a receiving node, a number of packets;

calculating, by the source node, a link cost based on the number of packets received by the receiving node;

sending, by the source node to the receiving node, the link cost; and

acknowledging, by the receiving node, each packet received from the source node.

2. The method of claim 1, wherein the number of sent packets is 20.

3. The method of claim 1, wherein the step of acknowledging by the receiving node comprises sending the link cost from the receiving node.

4. The method of claim 1, wherein the receiving node is selected for evaluation from among a number of nodes with the best received signal strength indicator.

5. The method of claim 4, wherein the number of nodes is 5.

21. The method of claim 1, wherein the nodes are part of a frequency-hopping spread spectrum wireless utility network.

6. A method of route evaluation in a network, comprising:

sending, by a source node, a packet to an upstream node; and

sending, by the upstream node to the source node, an acknowledgment of the packet, wherein the acknowledgement comprises a link cost from the upstream node to the source node.

7. The method of claim 6, wherein the sending, by the source node, a packet to the upstream node, occurs approximately every ten minutes.

8. The method of claim 6, wherein the sending, by the source node, a packet to the upstream node, notifies the upstream node that it is not to select the source node for elimination from the upstream node'"'"'s list of nodes.

9. The method of claim 8, wherein the downstream node sends a keep notification to the source node along with latest link cost information

10. 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, an acknowledgement of the polling communication from the second node;

sending, from the first node, data to the second node upon receipt of the acknowledgement; and

receiving, by the first node, an acknowledgement of receipt of the data by the second node.

11. The method of claim 10, 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 the acknowledgement from the second node of the polling communication or the data.

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

13. The method of claim 10, wherein the polling communication and response transaction time is 20 milliseconds.

14. The method of claim 10, comprising calculating a success percentage between the first and second nodes when the first node receives the acknowledgement or when the first node fails to receive the acknowledgement.

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

16. The method of claim 14, comprising constructing a look-up table comprising the calculated success percentage and link evaluation transaction time.

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

18. The method of claim 16, 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.

19. The method of claim 17, 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.

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