Communication and message route optimization and messaging in a mesh network

• US 8,144,596 B2
• Filed: 11/21/2008
• Issued: 03/27/2012
• Est. Priority Date: 11/25/2007
• Status: Active Grant

• Current Assignee: Trilliant Networks Incorporated
• Original Assignee: Trilliant Networks Incorporated
• Inventors: Veillette, Michel
• Primary Examiner(s): Rutkowski, Jeffrey M
• Application Number:
  US12/275,238
• Publication Number:
  US 20090135716A1
• Time in Patent Office: 1,222 Days
• Field of Search: 370217-220, 370/221, 370/254, 370/255, 370/351, 370/389, 370/390, 370/395.2, 370/395.21, 370/395.3, 370227-228, 370/238, 370/395.32, 709238-244, 398/126
• US Class Current: 370/238
• CPC Class Codes: G01D 4/004 Remote reading of utility meters to a fixed location
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04Q 3/66 Traffic distributors
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: Y02B 90/20 Smart grids as enabling technology in buildings sector smart grids supporting the management or operation of end-user stationary applications in general, or like technologies with no associated climate change mitigation effect Y04S20/00
• CPC Class Codes: Y02D 30/70 in wireless communication networks
• CPC Class Codes: Y04S 20/30 Smart metering, e.g. specially adapted for remote reading

Abstract

A method and system facilitate communications between an unassociated device and a server via a mesh network and a wide area network. The method may include receiving transmissions from candidate proxy devices, wherein each candidate proxy device is associated with a mesh network. The method may include selecting a proxy device from the candidate proxy devices. The method may include communicating with a server via the proxy device and the associated mesh network.

Claims

1. A method of optimizing communication paths within a mesh network, comprising:

initiating a mesh network, the mesh network including at least one mesh device;

receiving registration information from each mesh device of the mesh network;

storing mesh device information in an accessible memory;

responsive to a predetermined trigger, calculating an optimal path from each mesh device, wherein the optimal path includes a set of mesh device addresses corresponding to a set of mesh devices along which a message can be forwarded;

transmitting the calculated optimal path to each mesh device;

receiving, by the at least one mesh device, a request to transmit a message to a next mesh device; and

identifying, by the at least one mesh device, the next mesh device from among a plurality of neighbor mesh devices, wherein identifying the next mesh device further comprises calculating, by the at least one mesh device, a score for a next mesh device according to the calculated optimal path, and a score for an alternative next mesh device according to an alternate optimal path based on at least a link quality index corresponding to signal quality of the alternate optimal path, the link quality index included in neighbor information received in a neighbor exchange from at least one neighbor mesh device and selecting, based on a comparison of the calculated scores, one of the next mesh device according to the calculated optimal path and the alternative next mesh device according to the alternate optimal path.

2. The method of claim 1, wherein the predetermined trigger is selected from the set consisting of a time, a period, the occurrence of an event, the non-occurrence of an event, or any combination of two or more of these.

3. The method of claim 1, further comprising:

storing the associated optimal path in the accessible memory for each mesh device.

4. The method of claim 1, further comprising:

receiving a message from a mesh device transmitted along the associated optimal path.

5. The method of claim 1, wherein the optimal path is calculated, in part, based on:

a next hop to an access point, a path signal quality, and a number of hops to the access point.

6. A system for optimizing communication paths within a mesh network, comprising:

a mesh network including at least one mesh device;

a receiver receiving registration information from each mesh device of the mesh network;

a memory storage for storing mesh device information in an accessible memory;

a processor logic, responsive to a predetermined trigger, for calculating an optimal path from each mesh device, wherein the optimal path includes a set of mesh device addresses corresponding to a set of mesh devices along which a message can he forwarded;

a transmitter for transmitting the calculated optimal path to each mesh device; and

a processor logic for the at least one mesh device, responsive to receiving a request to transmit a message to a next mesh device, for identifying the next mesh device from among a plurality of neighbor mesh devices, wherein identifying the next mesh device further comprises calculating a score for a next mesh device according to the calculated optimal path and a score for an alternative next mesh device according to an alternate optimal path based on at least a link quality index corresponding to signal quality of the alternate optimal path, the link quality index included in neighbor information received in a neighbor exchange from at least one neighbor mesh device and selecting, based on a comparison of the calculated scores, one of the next mesh device according to the calculated optimal path and the alternative next mesh device according to the alternate optimal path.

7. The system of claim 6, wherein the predetermined trigger is selected from the set consisting of a time, a period, the occurrence of an event, the non-occurrence of an event, or any combination of two or more of these.

8. The system of claim 6, further comprising:

a memory control logic for storing the associated optimal path in the accessible memory for each mesh device.

9. The system of claim 6, wherein:

the receiver is adapted for receiving a message from a mesh device transmitted along the associated optimal path.

10. The system of claim 6, wherein the optimal path is calculated, in part, based on:

a next hop to an access point, a path signal quality, and a number of hops to the access point.

11. A non-transitory computer readable storage medium with an executable program stored thereon, wherein the program instructs a processor to perform the following steps of a method for optimizing communication paths within a mesh network, comprising:

initiating a mesh network, the mesh network including at least one mesh device;

receiving registration information from each mesh device of the mesh network;

storing mesh device information in an accessible memory;

responsive to a predetermined trigger, calculating an optimal path from each mesh device, wherein the optimal path includes a set of mesh device addresses corresponding to a set of mesh devices along which a message can be forwarded;

transmitting the calculated optimal path to each mesh device; and

responsive to receiving a request to transmit a message to a next mesh device, identifying the next mesh device from among a plurality of neighbor mesh devices, wherein identifying the next mesh device further comprises calculating a score for a next mesh device according to the calculated optimal path and a score for an alternative next mesh device according to an alternate optimal path based on at least a link quality index corresponding to signal quality of the alternate optimal path, the link quality index included in neighbor information received in a neighbor exchange from at least one neighbor mesh device and selecting, based on a comparison of the calculated scores, one of the next mesh device according to the calculated optimal path and the alternative next mesh device according to the alternate optimal path.

12. The non-transitory computer readable storage medium of claim 11, wherein the predetermined trigger is selected from the set consisting of a time, a period, the occurrence of an event, the non-occurrence of an event, or any combination of two or more of these.

13. The non-transitory computer readable storage medium of claim 11, further comprising:

storing the associated optimal path in the accessible memory for each mesh device.

14. The non-transitory computer readable storage medium of claim 11, further comprising:

receiving a message from a mesh device transmitted along the associated optimal path.

15. The non-transitory computer readable storage medium of claim 11, wherein the optimal path is calculated, in part, based on:

a next hop to an access point, a path signal quality, and a number of hops to the access point.

16. A method for transmitting a message over a mesh network via a routing, the method comprising:

associating a first mesh device with a mesh network, the mesh network managed by an access point;

identifying a next mesh device from among a plurality of neighbor mesh devices;

wherein identifying the next mesh device further comprises calculating, by the first mesh device, a score for the next mesh device according to a stored calculated optimal path and a score for an alternative next mesh device according to an alternate optimal path based on at least a link quality index corresponding to signal quality of the alternate optimal path, the link quality index included in neighbor information received in a neighbor exchange from at least one neighbor mesh device and selecting, based on a comparison of the calculated scores, one of the next mesh device according to the calculated optimal path and the alternative next mesh device according to the alternate optimal path; and

transmitting the message to the identified next mesh device.

17. The method in claim 16, wherein the identifying a next mesh device from among a plurality of neighbor mesh devices comprises:

receiving neighbor information from a set of neighboring mesh devices; and

identifying the next mesh device by selecting a next mesh device from the set of neighboring mesh devices in response to a request to transmit a message to the access point, wherein the next mesh device is closer to the access point.

18. The method in claim 16, further comprising optimizing communication paths within a mesh network, comprising:

initiating a mesh network, the mesh network including at least one mesh device;

receiving registration information from each mesh device of the mesh network;

storing mesh device information in an accessible memory;

responsive to predetermined trigger, calculating an optimal path from each mesh device, wherein the optimal path includes a set of mesh device addresses corresponding to a set of mesh devices along which a message can be forwarded; and

transmitting the calculated optimal path to each mesh device.

19. A method for transmitting a message over a mesh network via a routing, the method comprising:

associating a first mesh device with a mesh network, the mesh network managed by an access point;

identifying a next mesh device from among a plurality of neighbor mesh devices, the next mesh device being identified by one of;

(i) using tree routing comprising;

receiving neighbor information from a set of neighboring mesh devices; and

identifying the next mesh device by selecting a next mesh device from the set of neighboring mesh devices in response to a request to transmit a message to the access point, wherein the next mesh device is closer to the access point;

(ii) using source routing comprising;

identifying the next mesh device by receiving a next mesh device address from the access point, wherein the next mesh device is part of an optimal path to the access point;

or

(iii) using mesh routing comprising;

broadcasting an optimal path query to neighboring mesh devices in response to a request to transmit a message to a receiving mesh device;

receiving replies from the neighboring mesh devices; and

identifying the next mesh device by selecting a next mesh device by calculating an optimal path, the optimal path including an address of a next mesh device; and

wherein identifying the next mesh device further comprises calculating, by the first mesh device, a score for the next mesh device according to a stored calculated optimal path and a score for an alternative next mesh device according to an alternate optimal path based on at least a link quality index corresponding to signal quality of the alternate optimal path, the link quality index included in neighbor information received in a neighbor exchange from at least one neighbor mesh device and selecting, based on a comparison of the calculated scores, one of the next mesh device according to the stored calculated optimal path and the alternative next mesh device according to the alternate optimal path.

20. The method in claim 19, further comprising transmitting the message to the identified next mesh device.

21. The method in claim 19, further comprising optimizing communication paths within a mesh network, comprising:

initiating a mesh network, the mesh network including at least one mesh device;

receiving registration information from each mesh device of the mesh network;

storing mesh device information in an accessible memory;

responsive to predetermined trigger, calculating an optimal path from each mesh device, wherein the optimal path includes a set of mesh device addresses corresponding to a set of mesh devices along which a message can be forwarded; and

transmitting the calculated optimal path to each mesh device.

22. A system for transmitting a message over a mesh network, the system comprising:

means for associating a first mesh device with a mesh network, the mesh network managed by an access point;

means for identifying a next mesh device from among a plurality of neighbor mesh devices, the next mesh device being identified by one of;

(i) using tree routing comprising;

receiving neighbor information from a set of neighboring mesh devices; and

identifying the next mesh device by selecting a next mesh device from the set of neighboring mesh devices in response to a request to transmit a message to the access point, wherein the next mesh device is closer to the access point;

(ii) using source routing comprising;

identifying the next mesh device by receiving a next mesh device address from the access point, wherein the next mesh device is part of an optimal path to the access point;

or

(iii) using mesh routing comprising;

broadcasting an optimal path query to neighboring mesh devices in response to a request to transmit a message to a receiving mesh device;

receiving replies from the neighboring mesh devices at the first mesh device; and

identifying the next mesh device by selecting a next mesh device by calculating an optimal path, the optimal path including an address of a next mesh device; and

wherein the means for identifying the next mesh device further comprises means for calculating, by the first mesh device, a score for the next mesh device according to a stored calculated optimal path and a score for an alternative next mesh device according to an alternate optimal path based on at least a link quality index corresponding to signal quality of the alternate optimal path, the link quality index included in neighbor information received in a neighbor exchange from at least one neighbor mesh device and selecting, based on a comparison of the calculated scores, one of the next mesh device according to the stored calculated optimal path and the alternative next mesh device according to the alternate optimal path.

23. The system in claim 22, further comprising a transmitter for transmitting the message to the identified next mesh device.

24. The system in claim 22, further comprising means for optimizing communication paths within the mesh network comprising:

a receiver receiving registration information from each mesh device of the mesh network;

a memory storage for storing mesh device information in an accessible memory;

a processor logic, responsive to predetermined trigger, for calculating an optimal path from each mesh device, wherein the optimal path includes a set of mesh device addresses corresponding to a set of mesh devices along which a message can be forwarded; and

a transmitter for transmitting the calculated optimal path to each mesh device.

25. A non-transitory computer readable storage medium with an executable program stored thereon, wherein the program instructs a processor to perform the following steps of a method for transmitting a message over a mesh network, the method comprising:

associating a first mesh device with a mesh network, the mesh network managed by an access point;

identifying a next mesh device from among a plurality of neighbor mesh devices, the next mesh device being identified by one of;

(i) using tree routing comprising;

receiving neighbor information from a set of neighboring mesh devices; and

identifying the next mesh device by selecting a next mesh device from the set of neighboring mesh devices in response to a request to transmit a message to the access point, wherein the next mesh device is closer to the access point;

(ii) using source routing comprising;

identifying the next mesh device by receiving a next mesh device address from the access point, wherein the next mesh device is part of an optimal path to the access point;

or

(iii) using mesh routing comprising;

broadcasting an optimal path query to neighboring mesh devices in response to a request to transmit a message to a receiving mesh device;

receiving replies from the neighboring mesh devices; and

identifying the next mesh device by selecting a next mesh device by calculating an optimal path, the optimal path including an address of a next mesh device; and

wherein identifying the next mesh device further comprises calculating by the first mesh device, a score for the next mesh device according to a stored calculated optimal path and a score for an alternative next mesh device according to an alternate optimal path based on at least a link quality index corresponding to signal quality of the alternate optimal path, the link quality index included in neighbor information received in a neighbor exchange from at least one neighbor mesh device and selecting, based on a comparison of the calculated scores, one of the next mesh device according to the stored calculated optimal path and the alternative next mesh device according to the alternate optimal path.

26. The non-transitory computer readable storage medium in claim 25, further wherein the method further comprising transmitting the message to the identified next mesh device.

27. The non-transitory computer readable storage medium in claim 25, wherein the method further comprising optimizing communication paths within a mesh network comprising:

receiving registration information from each mesh device of the mesh network;

storing mesh device information in an accessible memory;

responsive to predetermined trigger, calculating an optimal path from each mesh device, wherein the optimal path includes a set of mesh device addresses corresponding to a set of mesh devices along which a message can be forwarded; and

transmitting the calculated optimal path to each mesh device.

28. A method for transmitting a message over a mesh network via tree routing, comprising:

associating a first flesh device with a mesh network, the mesh network managed by an access point;

receiving neighbor information at the first mesh device from a set of neighboring mesh devices;

responsive to a request to transmit a message to the access point, selecting a next mesh device from the set of neighboring mesh devices, wherein the next mesh device is closer to the access point;

wherein selecting the next mesh device further comprises calculating, by the first mesh device, a score for the next mesh device according to a stored calculated optimal path and a score for an alternative next mesh device according to an alternate optimal path based on at least a link quality index corresponding to signal quality of the alternate optimal path, the link quality index included in neighbor information received in a neighbor exchange from at least one neighbor mesh device and selecting, based on a comparison of the calculated scores, one of the next mesh device according to the calculated optimal path and the alternative next mesh device according to the alternate optimal path; and

transmitting the message to the next mesh device.

29. The method of claim 28, further comprising:

receiving a message from a sending mesh device for forwarding, wherein the request to transmit the message to the access point is indicated in a header of the message; and

replying to the sending mesh device with an acknowledgement after the message has been transmitted.

30. The method of claim 29, further comprising:

storing a temporary path in an accessible memory, wherein the temporary path includes an address of the sending mesh device and an address of the next mesh device.

31. The method of claim 30, further comprising:

receiving a reply from the next mesh device;

retrieving the temporary path from the accessible memory; and

forwarding the reply to the sending mesh device.

32. The method of claim 29, wherein the neighbor information includes:

a next hop to the access point, a path signal quality, and a number of hops to the access point.

33. The method of claim 29, further comprising:

responsive to a failure to receive an acknowledgement for the transmitted message, selecting a second best mesh device from the set of neighboring mesh devices and transmitting the message to the second best mesh device.

34. The method of claim 29, further comprising:

responsive to receiving the neighbor information, updating a neighbor information table in accessible memory.

35. A system for transmitting a message over a mesh network via tree routing, comprising:

an association logic unit for associating a first mesh device with a mesh network, the mesh network managed by an access point;

a receiver for receiving neighbor information from a set of neighboring mesh devices;

a selection logic unit responsive to a request to transmit a message to the access point, selecting a next mesh device from the set of neighboring mesh devices, wherein the next mesh device is closer to the access point;

the selection logic unit, further calculating a score for the next mesh device according to a stored calculated optimal path and a score for an alternative next mesh device according to an alternate optimal path based on at least a link quality index corresponding to signal quality of the alternate optimal path, the link quality index included in neighbor information received in a neighbor exchange from at least one neighbor mesh device and selecting, based on a comparison of the calculated scores, one of the next mesh device according to the calculated optimal path and the alternative next mesh device according to the alternate optimal path; and

a transmitter for transmitting the message to the next mesh device.

36. The system of claim 35, wherein:

the receiver is adapted for receiving a message from a sending mesh device for forwarding, wherein the request to transmit the message to the access point is indicated in a header of the message; and

the receiver of the sending mesh device being adapted to receive a reply with an acknowledgement after the message to the next mesh device has been transmitted.

37. The system of claim 36, further comprising:

a memory storage for storing a temporary path in an accessible memory, wherein the temporary path includes an address of the sending mesh device and an address of the next mesh device.

38. The system of claim 37, further comprising:

a memory control logic for retrieving the temporary path from the accessible memory; and

the receiver is adapted to receive a reply from the next mesh device, retrieve the temporary path from the accessible memory; and

forward the reply to the sending mesh device.

39. The system of claim 35, wherein the neighbor information includes:

a next hop to the access point, a path signal quality, and a number of hops to the access point.

40. The system of claim 35, further comprising:

means responsive to a failure to receive an acknowledgement for the transmitted message, for selecting a second best mesh device from the set of neighboring mesh devices and transmitting the message to the second best mesh device.

41. The system of claim 35, further comprising:

means responsive to receiving the neighbor information, for updating a neighbor information table in accessible memory.

42. A non-transitory computer storage medium with an executable program stored thereon, wherein the program instructs a processor to perform the following steps of a method for transmitting a message over a mesh network via tree routing, the method comprising:

associating a first mesh device with a mesh network, the mesh network managed by an access point;

receiving neighbor information at the first mesh device from a set of neighboring mesh devices;

responsive to a request to transmit a message to the access point, selecting a next mesh device from the set of neighboring mesh devices, wherein the next mesh device is closer to the access point;

wherein selecting the next mesh device further comprises calculating a score for the next mesh device according to a stored calculated optimal path and a score for an alternative next mesh device according to an alternate optimal path based on at least a link quality index corresponding to signal quality of the alternate optimal path, the link quality index included in neighbor information received in a neighbor exchange from at least one neighbor mesh device and selecting, based on a comparison of the calculated scores, one of the next mesh device according to the calculated optimal path and the alternative next mesh device according to the alternate optimal path; and

transmitting the message to the next mesh device.

43. The non-transitory computer readable storage medium of claim 42, wherein the method further comprising:

receiving a message from a sending mesh device fur forwarding, wherein the request to transmit the message to the access point is indicated in a header of the message; and

replying to the sending mesh device with an acknowledgement after the message has been transmitted.

44. The non-transitory computer readable storage medium of claim 43, wherein the method further comprising:

storing a temporary path in an accessible memory, wherein the temporary path includes an address of the sending mesh device and an address of the next mesh device.

45. The non-transitory computer readable storage medium of claim 44, wherein the method further comprising:

receiving a reply from the next mesh device;

retrieving the temporary path from the accessible memory; and

forwarding the reply to the sending mesh device.

46. The non-transitory computer readable storage medium of claim 42, wherein the neighbor information includes:

a next hop to the access point, a path signal quality, and a number of hops to the access point.

47. The non-transitory computer readable storage medium of claim 42, further comprising:

responsive to a failure to receive an acknowledgement for the transmitted message, selecting a second best mesh device from the set of neighboring mesh devices and transmitting the message to the second best mesh device.

48. The non-transitory computer readable storage medium of claim 42, further comprising:

responsive to receiving the neighbor information, updating a neighbor information table in accessible memory.

49. A system for transmitting a message over a mesh network via tree routing, comprising:

means for associating a first mesh device with a mesh network, the mesh network managed by an access point;

means for receiving neighbor information at the first mesh device from a set of neighboring mesh devices;

means responsive to a request for transmitting a message to the access point, selecting a next mesh device from the set of neighboring mesh devices, wherein the next mesh device is closer to the access point;

wherein the selection means further comprises means for calculating a score for the next mesh device according to a stored calculated optimal path and a score for an alternative next mesh device according to an alternate optimal path based on at least a link quality index corresponding to signal quality of the alternate optimal path, the link quality index included in neighbor information received in a neighbor exchange from at least one neighbor mesh device and selecting, based on a comparison of the calculated scores, one of the next mesh device according to the calculated optimal path and the alternative next mesh device according to the alternate optimal path; and

means for transmitting the message to the next mesh device.

50. The system of claim 49, further comprising:

means for receiving a message from a sending mesh device for forwarding, wherein the request to transmit the message to the access point is indicated in a header of the message; and

means for replying to the sending mesh device with an acknowledgement after the message has been transmitted.

51. The system of claim 50, further comprising:

means for storing a temporary path in an accessible memory, wherein the temporary path includes an address of the sending mesh device and an address of the next mesh device.

52. The system of claim 51, further comprising:

means for receiving a reply from the next mesh device;

means for retrieving the temporary path from the accessible memory; and

means for forwarding the reply to sending mesh device.

53. The system of claim 49, wherein the neighbor information includes:

a next hop to the access point, a path signal quality, and a number of hops to the access point.

54. The system of claim 49, farther comprising:

means for responsive to a failure to receive an acknowledgement for the transmitted message, for selecting a second best mesh device from the set of neighboring mesh devices and transmitting the message to the second best mesh device.

55. The system of claim 49, further comprising:

means for responsive for receiving the neighbor information, updating a neighbor information table in accessible memory.