Communication and message route optimization and messaging in a mesh network

• US 8,780,763 B2
• Filed: 01/13/2012
• Issued: 07/15/2014
• Est. Priority Date: 11/25/2007
• Status: Expired due to Fees

• Current Assignee: Trilliant Networks Incorporated
• Original Assignee: Trilliant Networks Incorporated
• Inventors: Veillette, Michel
• Primary Examiner(s): Rutkowski, Jeffrey M
• Application Number:
  US13/349,779
• Publication Number:
  US 20120140678A1
• Time in Patent Office: 914 Days
• Field of Search: 370217-220, 370/227, 370/228, 370/238, 370/395.2, 370/395.21, 370/395.32, 370255-256, 709239-241
• US Class Current: 370/255
• 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 a first mesh device, a second mesh device and an access point, the mesh devices each including a neighbor information table and a temporary path table;

receiving registration information and periodically transmitted information by the access point from each mesh device, wherein the periodically transmitted information comprises the neighbor information table associated with a respective mesh device;

storing the received registration information and the periodically transmitted information in an accessible memory of the access point;

responsive to a predetermined trigger, calculating, by the access point, an optimal path from the first mesh device to the access point, wherein the optimal path is calculated using the received periodically transmitted information and includes a set of mesh device addresses corresponding to a set of intermediate mesh devices along which a message can be forwarded; and

transmitting the calculated optimal path by the access point to the first mesh device and the set of intermediate mesh devices;

the method further comprising;

transmitting a first message from the first mesh device to the access point, wherein each of the first mesh device and a set of intermediate mesh devices forward the first message to a respective next mesh device selected from the neighbor information table as being closer to the access point;

storing, by each of the mesh devices receiving the first message from a transmitting mesh device, an entry in the temporary path table including the respective transmitting mesh device; and

transmitting a second message from the access point to the first mesh device by forwarding the second message according to the entries in the respective temporary path tables of the mesh devices that received the first message.

2. The method according to claim 1, wherein transmitting the calculated optimal path by the access point to the first mesh device and the set of intermediate mesh devices uses source routing, comprising:

reversing the optimal path from the first mesh device to the access point to arrive at an optimal path from the access point to the first mesh device, and

transmitting a third message from the access point to the first mesh device including the optimal path from the access point to the first mesh device.

3. The method according to claim 2, further comprising:

executing a route discovery routine including broadcasting a request for determining at least one path from the first mesh device to the second mesh device;

transmitting a fourth message from the first mesh device to the second mesh device using a path determined by the route discovery routine;

storing, by each of the mesh devices receiving the fourth message from a transmitting mesh device, an entry in the temporary path table including the respective transmitting mesh device; and

transmitting a fifth message from the second mesh device to the first mesh device by forwarding the fifth message according to the entries in the respective temporary path tables of the second mesh device and of the intermediate mesh devices that received the third message.

4. The method according to claim 3, using mesh routing, wherein executing the route discovery routine comprises:

broadcasting the request by the first mesh device to neighboring mesh devices;

checking, by each of the neighboring mesh devices, if it is the second mesh device;

if a neighboring mesh device is the second mesh device, answering to the first mesh device with route information, and

if a neighboring mesh device is not the second mesh device, re-broadcasting the request.

5. The method according to claim 4, wherein re-broadcasting the request comprises re-broadcasting by signal quality, wherein the neighboring mesh devices not being the second mesh device only re-broadcast to their neighbors where a signal exceeds a first threshold.

6. The method according to claim 3, wherein the first mesh device, before transmitting the fourth message, selects a path from the first mesh device to the second mesh device from the at least one path determined by the route discovery routine, particularly wherein the path is selected based on a path score.

7. The method according to claim 1, wherein transmitting the first message from the first mesh device to the access point, using tree routing, comprises:

receiving, at an intermediate mesh device, the first message from the first mesh device for forwarding to the access point, wherein the request to transmit the first message to the access point is indicated in a header of the first message;

receiving neighbor information from a set of neighboring mesh devices;

selecting the next mesh device from the set of neighboring mesh devices, wherein the next mesh device is closer to the access point;

storing an entry in the temporary path table in an accessible memory of the intermediate mesh device, wherein the entry includes an address of the first mesh device and an address of the next mesh device;

the method further comprising;

receiving, at the intermediate mesh device, an answer from the next mesh device;

retrieving the entry in the temporary path table from the accessible memory; and

forwarding the answer toward the first mesh device using the retrieved entry.

8. The method according to claim 7, wherein the neighbor information includes at least one of:

a best parent field, a best five parents field, an access point load field, a path signal quality field, and a number of hops to the access point field.

9. The method of claims 7, further comprising:

responsive to a failure to receive an acknowledgement for the transmitted first message, selecting, by the intermediate mesh device, another next mesh device from the set of neighboring mesh devices and transmitting the first message to the another next mesh device.

10. The method of claim 7, further comprising:

responsive to receiving the neighbor information, updating the neighbor information table in the accessible memory of the intermediate mesh device.

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 a first mesh device, a second mesh device and an access point, the mesh devices each including a neighbor information table and a temporary path table;

receiving registration information and periodically transmitted information by the access point from each mesh device, wherein the periodically transmitted information comprises the neighbor information table associated with a respective mesh device;

storing the received registration information and the periodically transmitted information in an accessible memory of the access point;

responsive to a predetermined trigger, calculating, by the access point, an optimal path from the first mesh device to the access point, wherein the optimal path is calculated using the received periodically transmitted information and includes a set of mesh device addresses corresponding to a set of intermediate mesh devices along which a message can be forwarded; and

transmitting the calculated optimal path by the access point to the first mesh device and the set of intermediate mesh devices;

the method further comprising;

transmitting a first message from the first mesh device to the access point, wherein each of the first mesh device and a set of intermediate mesh devices forward the first message to a respective next mesh device selected from the neighbor information table as being closer to the access point;

storing, by each of the mesh devices receiving the first message from a transmitting mesh device, an entry in the temporary path table including the respective transmitting mesh device; and

transmitting a second message from the access point to the first mesh device by forwarding the second message according to the entries in the respective temporary path tables of the mesh devices that received the first message.

12. The non-transitory computer readable storage medium of claim 11, wherein transmitting the calculated optimal path by the access point to the first mesh device and the set of intermediate mesh devices uses source routing, comprising:

reversing the optimal path from the first mesh device to the access point to arrive at an optimal path from the access point to the first mesh device, and

transmitting a third message from the access point to the first mesh device including the optimal path from the access point to the first mesh device.

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

executing a route discovery routine including broadcasting a request for determining at least one path from the first mesh device to the second mesh device;

transmitting a fourth message from the first mesh device to the second mesh device using a path determined by the route discovery routine;

storing, by each of the mesh devices receiving the fourth message from a transmitting mesh device, an entry in the temporary path table including the respective transmitting mesh device; and

transmitting a fifth message from the second mesh device to the first mesh device by forwarding the fifth message according to the entries in the respective temporary path tables of the second mesh device and of the intermediate mesh devices that received the third message.

14. The non-transitory computer readable storage medium of claim 11, wherein transmitting the first message from the first mesh device to the access point, using tree routing, comprises:

receiving, at an intermediate mesh device, the first message from the first mesh device for forwarding to the access point, wherein the request to transmit the first message to the access point is indicated in a header of the first message;

receiving neighbor information from a set of neighboring mesh devices;

selecting the next mesh device from the set of neighboring mesh devices, wherein the next mesh device is closer to the access point;

storing an entry in the temporary path table in an accessible memory of the intermediate mesh device, wherein the entry includes an address of the first mesh device and an address of the next mesh device;

the method further comprising;

receiving, at the intermediate mesh device, an answer from the next mesh device;

retrieving the entry in the temporary path table from the accessible memory; and

forwarding the answer toward the first mesh device using the retrieved entry.

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

responsive to a failure to receive an acknowledgement for the transmitted first message, selecting, by the intermediate mesh device, another next mesh device from the set of neighboring mesh devices and transmitting the first message to the another next mesh device.

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

responsive to receiving the neighbor information, updating the neighbor information table in the accessible memory of the intermediate mesh device.

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

a mesh network including a first mesh device, a second mesh device, at least one intermediate mesh device and an access point,

wherein the mesh devices each comprise;

a transceiver for transmitting signals to the mesh network or for receiving signals from the mesh network, and a memory for storing a neighbor information table and a temporary path table, and

wherein the access point comprises;

a receiver receiving registration information and periodically transmitted information from each mesh device, wherein the periodically transmitted information comprises the neighbor information table associated with the respective mesh device;

a memory storage for storing the received registration information and the received periodically transmitted information in an accessible memory;

a processor logic, responsive to a predetermined trigger, for calculating an optimal path from the first mesh device to the access point using the received periodically transmitted information, wherein the optimal path includes a set of mesh device addresses corresponding to a set of intermediate mesh devices along which a message can be forwarded; and

a transmitter for transmitting the calculated optimal path to the first mesh device and to the set of intermediate mesh devices,

and wherein the mesh devices each include a processor operative to control the transceiver and to execute instructions;

(a) to transmit a first message from the first mesh device to the access point, wherein each of the first mesh device and the set of intermediate mesh devices forward the first message to a respective next mesh device selected from the neighbor information table as being closer to the access point;

(b) to store, by each of the mesh devices receiving the first message from a transmitting mesh device, an entry in the temporary path table including the respective transmitting mesh device; and

(c) to transmit a second message from the access point message according to the entries in the respective temporary path tables of the mesh devices that received the first message.

18. The system according to claim 17, wherein the processor of the mesh devices is further operative to execute instructions to execute a route discovery routine including broadcasting a request for determining at least one path from the first mesh device to the second mesh device;

(d) to transmit a third message from the first mesh device to the second mesh device using a path determined by the route discovery routine;

(e) to store, by each of mesh devices receiving the third message from a transmitting mesh device, an entry in the temporary path table including the respective transmitting mesh device; and

(f) to transmit a fourth message from the second mesh device to the first mesh device by forwarding the fourth message according to the entries in the respective temporary path tables of the second mesh device and of the intermediate mesh devices that received the third message.

19. The system according to claim 17, 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.

20. The system according to claim 17, wherein the optimal path is calculated, in part, based on:

a next hop to the access point, a path signal quality, and a number of hops to the access point, wherein each criteria is assigned a predefined weight.

21. The system according to claim 17, wherein the processor of the mesh devices is further operative to execute instructions:

(d) to transmit the first message from the first mesh device to the access point, using tree routing, comprising;

i) receiving, at an intermediate mesh device, the first message from the first mesh device for forwarding to the access point, wherein the request to transmit the first message to the access point is indicated in a header of the first message;

ii) receiving neighbor information from a set of neighboring mesh devices;

iii) selecting the next mesh device from the set of neighboring mesh devices, wherein the next mesh device is closer to the access point;

iv) storing an entry in the temporary path table in an accessible memory of the intermediate mesh device, wherein the entry includes an address of the first mesh device and an address of the next mesh device;

and the processor of the mesh devices is further operable to execute instructions;

(e) to receive, at the intermediate mesh device, an answer from the next mesh device;

(f) to retrieve the entry in the temporary path table from the accessible memory; and

(g) to forward the answer toward the first mesh device using the retrieved entry.