Latency controlled redundant routing

• US 8,929,228 B2
• Filed: 07/01/2004
• Issued: 01/06/2015
• Est. Priority Date: 07/01/2004
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Kolavennu, Soumitri N., Budampati, Ramakrishna S, Gonia, Patrick S
• Primary Examiner(s): Hailu, Kibrom T
• Application Number:
  US10/882,561
• Publication Number:
  US 20060002368A1
• Time in Patent Office: 3,841 Days
• Field of Search: 370/400, 370/408, 370/216, 370/256, 370/351, 370/389, 370/252, 370/338, 370/254, 370/238
• US Class Current: 370/252
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04W 40/246 Connectivity information discovery

Abstract

Redundant, non-overlapping paths or routes for a sensor signal in a mesh network are selected based on predetermined metrics. In one embodiment, a wireless sensor transmits a signal that is received by two separate infrastructure nodes. The signal is retransmitted by the two intermediate nodes via the selected non-overlapping routes to a controller node. Routes are identified for at least two infrastructure nodes that receive signals from an added sensor. Performance metrics are calculated for each route. The two routes with the best performance metrics are selected in one embodiment.

Claims

1. A method of communicating a message from a source node to destination nodes, the method comprising:

discovering a plurality of paths from the source node to the destination nodes wherein the paths contain intermediate nodes, and wherein the intermediate nodes are configured for of receiving and re-transmitting messages from other nodes; and

simultaneously sending the message over two or more completely non-overlapping paths from the wireless source node to the destination nodes;

wherein for any given destination node, there is at least one path from the source node to the given destination node that is completely non-overlapping with at least one other path; and

wherein the message from the source node is sent to each destination node using non-overlapping paths for each destination node;

wherein the paths to each destination node are selected from all possible paths based on performance metrics that correspond to a quality of the paths wherein the performance metrics comprise a number of hops in the paths, a cumulative RF (Radio Frequency) link quality of the paths, and a cumulative bandwidth utilization percentage;

wherein two paths comprising overall top performance metrics are selected as a primary path and a secondary path;

wherein the two paths are selected to minimize latency between a same message arriving by non-overlapping paths; and

wherein the latency is minimized by selecting the two paths based on a first best performance metric and a second best performance metric;

wherein the communicating of the message further comprising discovering a new path, from the source node to the given destination node to which the path has failed, that does not increase the latency beyond specified limits for the selected paths between the source node and all the destination nodes.

2. The method of claim 1, wherein the paths to each destination node are selected from all possible paths based on measured qualification criteria.

3. The method of claim 2, wherein the same paths are used for one or more subsequent messages between the source node and each of the destination nodes.

4. The method of claim 3, wherein the qualification criteria are comprised of combinations of measured latency, number of hops, link quality of one or more hops, and resource utilization at one or more nodes along the path.

5. The method of claim 4, wherein the selected paths have end to end latency values within specified limits.

6. The method of claim 5 and further comprising:

detecting a failure in a path from the source node to one of the destination nodes; and

continuing to use paths from the source node to each of the destination nodes that are not affected by the failure.

7. The method of claim 1 and further comprising:

detecting a failure in a path from the source node to one of the destination nodes; and

continuing to use paths from the source node to each of the destination nodes that are not affected by the failure.

8. The method of claim 7 and further comprising discovering a new path, from the source node to the destination node to which the path has failed, that does not increase the latency beyond the specified limits for the selected paths between the source node and all destination nodes.

9. The method of claim 8 wherein the discovered new path is non-overlapping with the prior selected paths from the source node to each of the destination nodes that are not affected by the failure.

10. The method of claim 4, wherein qualification criteria are measured recurrently for each of the selected paths.

11. The method of claim 10, wherein if the measured qualification criteria fail for a given selected path, a new path is determined.

12. The method of claim 2, wherein the path selection is recurring.

13. The method of claim 1, wherein a subset of the nodes use wireless communications.

14. The method of claim 1 wherein the method is repeated upon incremental.

15. The method of claim 1, wherein the source comprise a wireless node, and the destination comprises a control center, and wherein the wireless node is coupled to the control center via a gateway.

16. A method of communicating a message from a source node to a destination node, the method comprising:

discovering a plurality of paths from the source node to the destination node wherein the paths contain intermediate nodes, and wherein the intermediate nodes are configured for of receiving and re-transmitting messages from other nodes;

simultaneously sending the message over more than one completely non-overlapping path from the source node to the destination node;

wherein for any given destination node, there is at least one path from the source node to the given destination node that is completely non-overlapping with at least one other path;

wherein the paths to each destination node are selected from all possible paths based on performance metrics that correspond to a quality of the paths wherein the performance metrics comprise a number of hops in the paths, a cumulative RF (Radio Frequency) link quality of the paths, and a cumulative bandwidth utilization percentage;

wherein two paths comprising overall top performance metrics are selected as a primary path and a secondary path;

wherein the two paths are selected to minimize latency between a same message arriving by non-overlapping paths; and

wherein the latency is minimized by selecting the two paths based on a first best performance metric and a second best performance metric;

wherein the communicating of the message further comprising discovering a new path, from the source node to the given destination node to which the path has failed, that does not increase the latency beyond specified limits for the selected paths between the source node and all the destination nodes.

17. The method of claim 16, wherein the same paths are used for one or more subsequent messages between the source node and each of the destination nodes.

18. The method of claim 17, wherein the selected paths have end to end latency values within specified limits.

19. The method of claim 18 and further comprising:

detecting a failure in a path from the source node to one of the destination nodes; and

continuing to use paths from the source node to each of the destination nodes that are not affected by the failure.

20. The method of claim 19, wherein:

the message from the source node is sent to each destination node using one path; and

the paths from the source node to each of the destination nodes are non-overlapping.

21. The method of claim 20 and further comprising:

detecting a failure in a path from the source node to one of the destination nodes; and

continuing to use paths from the source node to each of the destination nodes that are not affected by the failure.

22. The method of claim 21 and further comprising discovering a new path, from the source node to the destination node to which the path has failed, that does not increase the latency beyond the specified limits for the selected paths between the source node and all destination nodes.

23. The method of claim 22 wherein the discovered new path is non-overlapping with the prior selected paths from the source node to each of the destination nodes that are not affected by the failure.

24. The method of claim 21, wherein qualification criteria are measured recurrently for each of the selected paths.

25. The method of claim 24, wherein if the measured qualification criteria fail for a given selected path, a new path is determined.

26. The method of claim 16, wherein the path selection is recurring.

27. The method of claim 16, wherein a subset of the nodes use wireless communications.

28. The method of claim 16 wherein the method is repeated upon incremental addition of a new source or destination node.