Latency controlled redundant routing

• US 20060002368A1
• Filed: 07/01/2004
• Published: 01/05/2006
• Est. Priority Date: 07/01/2004
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Budampati, Ramakrishna S., Gonia, Patrick S., Kolavennu, Soumitri N.
• Granted Patent: US 8,929,228 B2
• Time in Patent Office: Days
• US Class Current: 370/351
• 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 signal between a source node and a destination node in a network of nodes, the method comprising:

discovering more than one path between the source node and the destination node wherein at least one of the paths contains at least one intermediate node, the intermediate node being capable of receiving and re-transmitting messages from other nodes; and

sending a message over more than one of the paths between the source node and the destination node.

2. The method of claim 1, wherein at least two of the paths between the source node and the destination node are non-overlapping.

3. The method of claim 1 wherein the paths are selected from a group of all possible paths based on measured qualification criteria.

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

5. The method of claim 4, 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.

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

7. The method of claim 6 and further comprising:

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

continuing to use paths from the source node to the destination node 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 that does not increase the latency beyond the specified limits for the selected paths between all pairs of source and destination nodes in the network of nodes.

9. The method of claim 6, wherein at least two of the selected paths are non-overlapping.

10. The method of claim 9 and further comprising:

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

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

11. The method of claim 10 and further comprising discovering a new path from the source node to the destination node that does not increase the latency beyond the specified limits for the selected paths between all pairs of source and destination nodes in the network of nodes.

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

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

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

15. The method of claim 3, wherein the path selection is recurring.

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

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

18. A method of communicating a message from a source node to more than one destination node, the method comprising:

discovering a plurality of paths from the source node to each of the destination nodes wherein the paths may or may not contain intermediate nodes, and wherein the intermediate node is capable of receiving and re-transmitting messages from other nodes; and

sending the message over one or more paths from the source node to each of the destination nodes.

19. The method of claim 18, wherein for any given destination node, there is at least one path from the source node to the given destination node that is non-overlapping with at least one path from the source node to each of the other destination nodes.

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

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

22. The method of claim 21, 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.

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

24. The method of claim 23 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.

25. The method of claim 24 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.

26. The method of claim 23, 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.

27. The method of claim 26 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.

28. The method of claim 27 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.

29. The method of claim 28 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.

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

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

32. The method of claim 20, wherein the path selection is recurring.

33. The method of claim 18, wherein a subset of the nodes use wireless communications.

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

35. A method of communicating a signal between a central control and a node in a network of nodes, the method comprising:

selecting non-overlapping first and second paths between the node and the central control;

sending the signal over the first path;

sending the signal over the second path such that the signals from both paths arrive at the central control or the node within a maximum latency time.

36. The method of claim 35 wherein each path comprises multiple hops.

37. The method of claim 36 wherein each path comprises multiple wireless infrastructure nodes.

38. The method of claim 35 wherein the signal is generated by a wireless leaf node in a wireless network.

39. A system comprising:

multiple wireless leaf nodes;

multiple wireless infrastructure nodes, wherein each leaf node communicates signals with two infrastructure nodes;

a central control that receives and sends communications from selected infrastructure nodes;

wherein the leaf nodes provide signals to the infrastructure nodes that are forwarded to the central control via the infrastructure nodes over non-overlapping paths; and

wherein the control center provides signals to the infrastructure nodes that are forwarded to the leaf nodes via the infrastructure nodes over non-overlapping paths.

40. The system of claim 39 wherein the infrastructure nodes provide the signal to the central control over the paths within a desired time.

41. The system of claim 39 wherein the infrastructure nodes provide the signal to the leaf node over the paths within a desired time.

42. The system of claim 39, wherein the central control is wired to the selected infrastructure nodes.

43. The system of claim 39, wherein the one of the selected infrastructure nodes is the central control.

44. The system of claim 39, wherein a given infrastructure node provides signals that are forwarded to the central control via other infrastructure nodes over non-overlapping paths.

45. A system for communicating a signal to a central control, the system comprising:

means for sending the signal over a first path to the central control;

means for sending the signal over a second path that is non-overlapping with the first path; and

means for selecting the each path such that the signal arrives at the central control within a specified time.

46. The system of claim 45 wherein each path comprise multiple hops.

47. The method of claim 45 wherein each path comprise multiple wireless infrastructure nodes.

48. The system of claim 45 wherein the signal is generated by a wireless leaf node in a wireless network.

49. A method of selecting communication paths in a wireless mesh network having leaf nodes, infrastructure nodes and a central control, the method comprising:

adding a leaf node to the network;

discovering routes between the new leaf node through infrastructure nodes to the central control;

calculating a performance metric for multiple discovered routes; and

selecting non-overlapping routes based on the performance metrics.

50. The method of claim 49 wherein the performance metrics include number of hops in the routes, a cumulative RF link quality of an entire path, and a cumulative bandwidth utilization percentage.

51. A method of selecting routes in a multi-tier wireless network having wireless leaf nodes and multiple infrastructure nodes, the method comprising:

detecting a signal transmitted from a leaf node at multiple infrastructure nodes;

passing information related to detected signals to a central control;

determining non-overlapping routes from the leaf node to the central control;

calculating performance metrics for the non-overlapping routes; and

selecting two non-overlapping routes as a function of the performance metrics.

52. A computer readable medium having instructions stored thereon for execution on a computer to perform a method comprising:

receiving routing information from infrastructure nodes related to signals detected from a leaf node;

determining non-overlapping routes from the leaf node to the central control;

calculating performance metrics for the non-overlapping routes; and

selecting two non-overlapping routes as a function of the performance metrics.

53. A system comprising:

multiple wireless leaf nodes;

multiple wireless infrastructure nodes, wherein each leaf node communicates signals with one or more infrastructure nodes;

a central control that receives and sends communications from selected infrastructure nodes;

wherein the leaf nodes provide signals to the infrastructure nodes that are forwarded to the central control by one of the one or more infrastructure nodes via other infrastructure nodes over non-overlapping paths; and

wherein the control center provides signals to the infrastructure nodes that are forwarded to the leaf nodes via the infrastructure nodes over non-overlapping paths.

54. The system of claim 53 wherein the infrastructure nodes provide the signal to the central control over the paths within a desired time.

55. The system of claim 53 wherein the infrastructure nodes provide the signal to the leaf node over the paths within a desired time.