Providing low average latency communication in wireless mesh networks

• US 7,787,427 B1
• Filed: 01/09/2007
• Issued: 08/31/2010
• Est. Priority Date: 01/09/2007
• Status: Active Grant

• Current Assignee: Analog Devices International Unlimited Company (Analog Devices, Inc.)
• Original Assignee: Dust Networks Incorporated (Analog Devices, Inc.)
• Inventors: Doherty, Lance R., Simon, Jonathan
• Primary Examiner(s): Yao; Kwang B
• Assistant Examiner(s): BOKHARI, SYED M
• Application Number:
  US11/651,921
• Time in Patent Office: 1,330 Days
• Field of Search: 370/328, 370/280, 370/335, 370/351, 370/235, 370/338, 370/238, 370/349, 370/314, 370/437, 455/445
• US Class Current: 370/338
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing

Abstract

Communicating using a wireless mesh network is disclosed. A route is determined from a first node to each other node in the wireless mesh network including one or more intermediate nodes that receive and transmit the packet. A frame length used for communicating a packet is selected based on the routes from the first node to each other node in the wireless mesh network. Node to node communications are selected within the frame along the route such that a predetermined average communication latency time is achieved.

Claims

1. A method for communicating using a wireless mesh network, comprising:

determining a plurality of routes from a first node to each other node in the wireless mesh network including one or more intermediate nodes that receive and transmit the packet;

selecting a frame length used for communicating a packet based on the plurality of routes from the first node to each other node in the wireless mesh network; and

selecting node to node communications within the frame along one or more routes of the plurality of routes such that a predetermined average communication latency time is achieved, wherein the low average communication latency time is achieved using a predetermined number of retries of a communication between two nodes that are part of a communication route between the first node and the second node, wherein the predetermined number of retires is based at least in part on a stability of a node to node communication, and wherein selecting node to node communications includes selecting node to node communications for two or more routes from a parent node, wherein the frame comprises a matrix of time slots and channels, wherein the frame repeats in a cycle, wherein a channel associated with a particular link in the frame changes from frame to frame within the cycle according to a predefined sequence, wherein node to node communications in at least one route from the first node to a second node in the wireless mesh network is selected such that the first node communicates to an intermediate node in a first time slot of the frame and the intermediate node communicates to a third node in a second time slot of the frame, wherein the second time slot in the frame is subsequent in time to the first time slot in the frame.

2. A method as in claim 1, wherein the low average communication latency time is achieved using a predetermined number of retries of a communication between two nodes that are part of a communication route between the first node and the second node.

3. A method as in claim 2, wherein the predetermined number of retires is based at least in part on a stability of a node to node communication.

4. A method as in claim 1, wherein the second node is farther from a gateway node than the first node.

5. A method as in claim 1, wherein the low average communication latency time is achieved at least in part by selecting the route that reduces a maximum route length between the first node and the second node in network.

6. A method as in claim 1, wherein the low average communication latency time is achieved at least in part by selecting the route that reduces an expected number of transmissions along the route from the first node and the second node in network.

7. A method as in claim 1, wherein the frame length is equal to n times the maximum number of hops from the first node to each other node.

8. A method as in claim 7, wherein n equals 1.

9. A method as in claim 7, wherein n equals 2.

10. A method as in claim 1, wherein the frame length is equal to n times the maximum number of expected transmissions from the first node to each other node.

11. A method as in claim 10, wherein n equals 1.

12. A method as in claim 10, wherein n equals 2.

13. A method as in claim 1, wherein the node to node communications within the frame are selected such that in one frame a message can get from the first node to each other node.

14. A method as in claim 1, wherein the node to node communications within the frame are selected such that there are batches of communications along each of the paths wherein each batch includes attempts of a predetermined node to node communication.

15. A method as in claim 1, further comprising activating a node in a route from the first node to a second node to use the frame for communicating by sending a source routed packet along the route.

16. A method as in claim 1, further comprising receiving an acknowledgement that a prior node to node communication was successfully received and not transmitting a communication retry based on receiving the acknowledgement.

17. A method as in claim 1, further comprising sending an acknowledgement that a prior node to node communication was successfully received and not receiving during a communication retry based on sending the acknowledgement.

18. A system for communicating using a wireless mesh network, comprising:

a processor; and

a memory coupled with the processor, wherein the memory is configured to provide the processor with instructions which when executed cause the processor to;

determine a plurality of routes from a first node to each other node in the wireless mesh network including one or more intermediate nodes that receive and transmit the packet;

select a frame length used for communicating a packet based on the plurality of routes from the first node to each other node in the wireless mesh network; and

select node to node communications within the frame along one or more routes of the plurality of routes such that a predetermined average communication latency time is achieved, wherein the low average communication latency time is achieved using a predetermined number of retries of a communication between two nodes that are part of a communication route between the first node and the second node, wherein the predetermined number of retires is based at least in part on a stability of a node to node communication, and wherein selecting node to node communications includes selecting node to node communications for two or more routes from a parent node, wherein the frame comprises a matrix of time slots and channels, wherein the frame repeats in a cycle, wherein a channel associated with a particular link in the frame changes from frame to frame within the cycle according to a predefined sequence, wherein node to node communications in at least one route from the first node to a second node in the wireless mesh network is selected such that the first node communicates to an intermediate node in a first time slot of the frame and the intermediate node communicates to a third node in a second time slot of the frame, wherein the second time slot in the frame is subsequent in time to the first time slot in the frame.

19. A computer program product for communicating using a wireless mesh network, the computer program product being embodied in a non-transitory computer readable medium encoded with computer executable instructions for:

determining a route from a first node to each other node in the wireless mesh network including one or more intermediate nodes that receive and transmit the packet;

selecting a frame length used for communicating a packet based on the routes from the first node to each other node in the wireless mesh network; and

selecting node to node communications within the frame along one or more routes of the plurality of routes such that a predetermined average communication latency time is achieved, wherein the low average communication latency time is achieved using a predetermined number of retries of a communication between two nodes that are part of a communication route between the first node and the second node, wherein the predetermined number of retires is based at least in part on a stability of a node to node communication, and wherein selecting node to node communications includes selecting node to node communications for two or more routes from a parent node, wherein the frame comprises a matrix of time slots and channels, wherein the frame repeats in a cycle, wherein a channel associated with a particular link in the frame changes from frame to frame within the cycle according to a predefined sequence, wherein node to node communications in at least one route from the first node to a second node in the wireless mesh network is selected such that the first node communicates to an intermediate node in a first time slot of the frame and the intermediate node communicates to a third node in a second time slot of the frame, wherein the second time slot in the frame is subsequent in time to the first time slot in the frame.