Method and system for providing routing protocols in a frequency hopping spread spectrum network

• US 20080310377A1
• Filed: 06/15/2007
• Published: 12/18/2008
• 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, Vaswani, Raj, McKernan, Daniel, Flammer, George
• Granted Patent: US 8,072,951 B2
• Time in Patent Office: Days
• US Class Current: 370/338
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update

Abstract

A method and system for providing a network and routing protocol for utility services are disclosed. In one embodiment, a computer-implemented method comprises discovering a utility network, wherein a utility device (for example, a constant powered meter) sends network discovery messages to find the utility network. Neighboring meters are discovered and the device listens for advertised routes for one or more networks from the neighbors. The device is then registered with one or more utility networks, receiving a unique address for each network registration. Also illustrated in this invention disclosure is how each device of a class of devices (for example, battery powered meter) finds and associates itself with another device (for example, constant powered meter). The constant powered meter also registers its associate battery powered meter with the utility networks. The constant powered meter registers itself with the access points and the upstream nodes in the path out of each network. 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 constant powered meter can sense transient link problems, outage problems, and traffic characteristics. It uses the information to find the best route out of and within each network. Each network device thus maintains multi-egress, multi-ingress network routing options both for itself and the device(s) associated with it.

Claims

1. A computer implemented method of a source node, comprising:

discovering neighboring nodes in a wireless FHSS communication network by broadcasting at least one discovery frame to the nodes in the wireless FHSS communication network;

receiving information on at least one egress node of the wireless FHSS communication network via an acknowledgement route advertisement messages received from the discovered neighbor nodes in response to the broadcast at least one discovery frame;

receiving information on at least one egress node of the wireless FHSS communication network via routing update messages and new routing advertisement messages received in response to a node'"'"'s keepalive messages; and

selecting a neighboring node for forwarding a packet to the egress node from the discovered neighboring nodes.

2. The method of claim 1, further comprising:

calculating a priority list of neighboring nodes, the priority list of sending nodes for use in selecting a neighboring node for forwarding a packet to the egress node,

wherein calculating the priority list is based on path costs for at least one hop between nodes along a segment of a route to the egress point using the corresponding neighboring node, and

wherein the egress node information including path cost for at least one hop between nodes along a segment of a route to the egress point is received in response to route discovery and keep alive messages of the source node.

3. The method of claim 2, wherein the broadcast message is sent using a link layer broadcast frame transmitted to a predetermined address which may be recognized by a plurality of nodes in the wireless FHSS communication network as indicating a broadcast message.

4. The method of claim 3, wherein the link layer broadcast frame is transmitted on a predefined frequency and time slot.

5. The method of claim 1, further comprising:

sending a timing update message to at least one other node in the wireless FHSS communications network using an FHSS beacon.

6. The method of claim 2, further comprising:

registering with at least one egress node.

7. The method of claim 6, further comprising:

registering with at least one intermediate node in the communications network, the intermediate node along a segment of a route to the egress point using the corresponding neighboring node.

8. The method of claim 6, further comprising:

reporting a network address associated with the registering node with a DNS server.

9. The method in claim 1, further comprising:

receiving a registration message from a node in the wireless FHSS communications network; and

registering the node in a list of nodes for receiving egress route information.

10. A method of routing in a wireless FHSS communications network, comprising:

discovering next hop nodes in the wireless FHSS communication network by broadcasting at least one discovery frame to the nodes in the wireless FHSS communication network;

discovering at least one access point to the wireless FHSS communications network from the broadcast at least one discovery frame to the nodes in the wireless FHSS communication network;

registering with the at least one access point to the wireless FHSS communications network;

selecting a plurality of nodes as next hop nodes for communicating with at least one access point;

receiving routing information from at least one of the discovered next hop nodes; and

constructing a routing table from the routing information received from the discovered next hop nodes, wherein the routing table includes at least one alternate path to a given destination node in the communications network.

11. The method of claim 10, wherein routing information received from the at least one of the discovered next hop nodes is in response to a route discovery message.

12. The method of claim 10, wherein routing information received from at least one of the discovered next hop nodes is in response to a keepalive message from the source node;

13. The method of claim 12, wherein the response from discovered next hop nodes are updates to previously received route advertisement messages.

14. The method of claim 10, wherein the routing table further includes preference information specifying the preferred order of alternate paths to a given destination node in the communications network.

15. The method of claim 10, further comprising:

forwarding routing table information including preference information specifying the preferred order of alternate paths to a given destination node in the communications network to at least one other node in the wireless FHSS communication network.

16. The method of claim 10, further comprising:

receiving a packet intended for a specified destination node in the wireless FHSS communication network;

selecting a next hop appropriate for transmitting the received packet to the specified destination node; and

forwarding the packet to the selected next hop.

17. The method of claim 12, further comprising:

receiving a packet intended to a specified destination node in the wireless FHSS communication network;

selecting a next hop appropriate for transmitting the received packet to the specified destination node, wherein selection of the next hop appropriate for transmitting the received packet is made according to the preference information that specifies preferred order of alternate paths;

forwarding the packet to the selected next hop.

18. The method of claim 10, wherein discovery of next hop nodes includes broadcasting at least one discovery frame to the nodes in the wireless FHSS communication network.

19. The method of claim 18, further comprising:

receiving network egress advertisement messages in responses to the broadcasting at least one discovery frame to the nodes in the wireless FHSS communication network, the network egress advertisement messages including the information on at least one egress node of the wireless FHSS communication network.

39. The method of claim 10, wherein the nodes register with a DNS server after egress point discovery and receipt of network address ID from the associated access point.

40. The method of claim 39 wherein the network address of the FHSS-based wireless network may be one of IPv4 or IPv6.

20. A method of communicating in a wireless FHSS network, comprising:

receiving a packet at a forwarding node in the wireless FHSS network, the received packet including a destination address corresponding to a destination node in the wireless FHSS network and at least a partial route to the destination node;

determining whether a preferred route exists for transmitting the packet to the destination address, and in the event the determination is that the preferred route exists, replacing the received route from the packet with the preferred route; and

forwarding the packet to another node in the wireless FHSS network according to the route included in the packet.

21. The method of claim 20, wherein the at least partial route included in the received packet originated from an access point.

22. The method of claim 21, wherein the at least partial route is a complete route specifying the nodes the packet is to traverse between the access point and the destination node.

23. The method of claim 20, wherein the preferred route is determined from at least two routes in a routing table of the forwarding node, the at least two routes from the forwarding node to the destination node.

24. The method of claim 23, wherein the determination between the at least two routes is based upon a preference value associated with a route of the at least two routes.

25. The method of claim 20, further comprising:

discovering next hop nodes in the wireless FHSS communication network;

receiving routing information from at least one of the discovered next hop nodes in a keep alive message included in an FHSS timing update message;

constructing a routing table from the routing information received from the discovered next hop nodes, wherein the routing table includes at least one alternate route to a given destination node in the communications network.

26. The method of claim 25, wherein the given destination node is an access point.

27. The method of claim 25, wherein calculating an alternate route is based on the path costs from the forwarding node to the destination node.

28. The method of claim 27, wherein the path cost includes a link cost for at least one hop between nodes along a segment of an alternate route.

29. The method of claim 28, wherein a preferred list of next-hop neighbor nodes is created for use in sending or receiving packets.

30. The method of claim 29, wherein the preference value associated with the route is based on the path cost of the associated route.

31. The method of claim 28, wherein the path cost is based upon at least one of:

ink quality, link reliability, or a success rate of transmission of packets along at least a segment of the route associated with the path cost.

32. The method of claim 31, wherein a weighted criterion is used among the path cost components in determining the preference value for a candidate route.

33. The method of claim 20, further comprising:

transmitting the route used in forwarding the packet to at least one other node in the wireless FHSS communications network in a keep alive message included in an FHSS timing update message.

34. The method of claim 33, wherein transmitting the route used in forwarding the packet to at least one other node in the wireless FHSS communications network is performed in the event the determination is that the preferred route exists.

35. The method of claim 34, wherein the route is transmitted to an access point.

36. The method of claim 33, wherein information transmitted with the transmitted route includes at least one of the preference value associated with the transmitted route or the path cost of the transmitted route.

37. The method of claim 33, wherein the neighboring nodes in a wireless FHSS communication network are discovered by broadcasting at least one discovery frame to the nodes in the wireless FHSS communication network.

38. The method of claim 20, wherein the nodes maintain timing synchronization and frequency hopping synchronization by sending periodic timing beacons and timing alignment broadcast messages.