NODE DISCOVERY AND CULLING IN WIRELESS MESH COMMUNICATIONS NETWORKS

• US 20090003356A1
• Filed: 06/27/2008
• Published: 01/01/2009
• Est. Priority Date: 06/15/2007
• Status: Abandoned Application

• 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
• Application Number:
  US12/163,918
• Publication Number:
  US 20090003356A1
• Time in Patent Office: Days
• US Class Current: 370/400
• 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/34 Source routing
• CPC Class Codes: H04L 45/66 Layer 2 routing, e.g. in Ethernet based MAN's
• CPC Class Codes: H04L 47/745 Reaction in network
• CPC Class Codes: H04L 47/788 Autonomous allocation of resources
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04L 47/824 Applicable to portable or mobile terminals
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• 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 discovering neighbor nodes in a network, comprising:

sending a query, by a first node, to a second node previously discovered;

sending a response to the query of the first node, by the second node, wherein the response comprises information about active neighbor nodes of the second node.

2. The method of claim 1, wherein the information sent to the first node comprises MAC address and hopping sequence.

3. The method of claim 1, wherein the query by the first node is not sent if the first node has more than a predetermined number of nodes in the first node'"'"'s list of nodes.

4. The method of claim 3, wherein the predetermined number of nodes is 90% of a desired number of nodes.

5. The method of claim 1, wherein in the event the first node receives information that a neighbor node is unreachable, the first node is prevented from communicating with the unreachable node until a predetermined event has occurred.

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

6. A method of eliminating nodes from a source node'"'"'s list of other nodes with which the source node communicates, comprising:

selecting an upper limit and a lower limit for a number of nodes on the list of nodes;

categorizing nodes on the list of nodes as nodes to eliminate and nodes not to eliminate; and

determining if the upper limit of nodes has been exceeded, and in the event the upper limit has been exceeded, eliminating nodes categorized as nodes to eliminate until the lower limit is reached.

7. The method of claim 6, wherein the category of nodes not to eliminate comprises nodes that the source node uses to send traffic upstream, nodes that route traffic upstream to the source node and infrastructure nodes.

8. The method of claim 7, wherein infrastructure nodes comprise relays, gateways and Field Service Units.

9. The method of claim 6, wherein eliminating nodes comprises making a series of passes through the list of nodes to select nodes to eliminate, wherein each pass selects nodes according to link quality.

10. The method of claim 9, wherein the series of passes comprises:

a first pass to select nodes that have routes to a predetermined destination that are independent of the source node;

a second pass to select nodes that do not have routes to a predetermined destination independent of the source node or if fewer than the difference between the upper limit and lower limit of nodes were selected during the first pass; and

a third pass to select nodes if fewer nodes than the difference between the upper limit and lower limit of nodes were selected during the first and second passes.

11. The method of claim 6, wherein when a node has been eliminated from the source node'"'"'s list of nodes, the source node notifies the eliminated node that it is no longer on the list of nodes.