Route and link evaluation in wireless mesh communications networks

• US 7,940,669 B2
• Filed: 06/27/2008
• Issued: 05/10/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: Hughes, Sterling, Flammer, George III, van Greunen, Jana, San Filippo, William E. III, Vaswani, Raj
• Primary Examiner(s): Rao; Seema S
• Assistant Examiner(s): Russell; Wanda Z
• Application Number:
  US12/163,904
• Publication Number:
  US 20090003232A1
• Time in Patent Office: 1,047 Days
• Field of Search: 370/252
• 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 route evaluation in a network, comprising:

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

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

calculating, by the source node, a link cost value based on the number of packets, from among the packets comprising said predetermined number of packets, that are acknowledged by the receiving node;

averaging successively calculated link cost values to determine a link cost; and

sending, by the source node to the receiving node, the link cost.

2. The method of claim 1, wherein the predetermined 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, further including the step of selecting a designated number of nodes with the best received signal strength indicator as receiving nodes to which said predetermined number of packets are to be sent.

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

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

7. The method of claim 1, wherein the steps of sending the predetermined number of packets and calculating a link cost are performed by the source node during an evaluation phase in which the source node determines the quality of a link to a neighbor node.

8. The method of claim 7, wherein the evaluation phase occurs during the process of discovering the neighbor node.

9. The method of claim 7, wherein the evaluation phase includes the steps of selecting a preset number of nodes with the best received signal strength indicator as receiving nodes, and sending the predetermined number of packets to the selected receiving nodes.

10. The method of claim 1, further comprising:

periodically sending, by the source node, a keep packet to an upstream node, notifying the upstream node to maintain the source node on a list of nodes for which the upstream node forwards packets; and

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

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

12. The method of claim 10, wherein the keep packet includes link cost from the source node to the upstream node.

13. The method of claim 10, further including the following steps:

transmitting a message from the upstream node to the source node when the source node is removed from said list; and

in response to receipt of said message at the source node, selecting a new upstream node to which said keep packets are periodically transmitted.

14. The method of claim 10, further including the following steps:

transmitting an acknowledgement from the upstream node to the source node when a keep packet is received at the upstream node; and

in response to a lack of receipt, at the source node, of an acknowledgement for a keep packet transmitted by the source node, selecting a new upstream node to which said keep packets are periodically sent.

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

discovering, at a first node, a neighbor node in the wireless network;

transmitting a predetermined number of packets from the first node to the neighbor node;

acknowledging, by the neighbor node, each packet successfully received from the first node;

calculating, by the first node, a link cost value based, at least in part, on the number of said predetermined number of packets that are acknowledged by the neighbor node;

averaging successively calculated link cost values to determine a link cost; and

transmitting the calculated link cost from the first node to the neighbor node.

16. The method of claim 15, wherein the first node discovers a plurality of neighbor nodes in the wireless network, and wherein the method includes the following steps:

selecting, from among said plurality of discovered neighbor nodes, a preset number of the neighbor nodes having the highest signal strength;

transmitting said predetermined number of packets from the first node to each of the selected neighbor nodes;

calculating, for each of the selected neighbor nodes, a link cost based on the number of said predetermined number of packets that are successfully received by that neighbor node; and

transmitting the link cost calculated for each of the selected neighbor nodes from the first node to the respective neighbor nodes.