Providing bounded latency communication in wireless mesh networks

• US 8,139,554 B1
• Filed: 01/03/2007
• Issued: 03/20/2012
• Est. Priority Date: 01/03/2006
• Status: Active Grant

• Current Assignee: Analog Devices International Unlimited Company (Analog Devices, Inc.)
• Original Assignee: Dust Networks Incorporated (Analog Devices, Inc.)
• Inventors: Simon, Jonathan, Doherty, Lance R.
• Primary Examiner(s): Afshar, Kamran
• Assistant Examiner(s): Behnamian, Shahriar
• Application Number:
  US11/649,342
• Time in Patent Office: 1,903 Days
• Field of Search: 370222-228, 370/230, 370/230.1, 370/231, 370/235, 370351-430
• US Class Current: 370/349
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality

Abstract

Communicating using a mesh network is disclosed. A frame length used for communicating a packet between a first node and a second node of a wireless mesh network is selected. A route from the first node to the second node is determined including one or more intermediate nodes that receive and transmit the packet. Node to node communications within the frame along the route is selected such that a communication latency time is below a predetermined limit time for a predetermined percentage of communications between the first node and the second node.

Claims

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

selecting a frame length of a frame used for communicating a packet between a first node and a second node of a wireless mesh network, wherein the frame comprises a plurality of time slots, and wherein a transmitter node transmits a packet to a receiver node during one of the plurality of time slots of the frame, and wherein the frame length is selected based at least in part on a predetermined limit time for communicating the packet between the first node and the second node;

determining a route from the first node to the second node including one or more intermediate nodes that receive and transmit the packet; and

selecting node to node communications within the frame along the route such that a communication latency time is below the predetermined limit time for a predetermined percentage of communications between the first node and the second node, wherein the 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 retries is based at least in part on the predetermined percentage of communications between the first node and the second node, wherein a retry slot comprises a time slot subsequent to a time slot assigned to the one node to node communication, wherein a first node to node communication is made using a first communication channel and a retry of the first node to node communication is made using a second communication channel, wherein the frame includes a set of retries for each hop along the route between the first node and the second node, wherein the set of retries for each hop is based at least in part on a reliability of communication between the first node and the second node, and wherein each retry uses a communication channel different from a communication channel used in a preceding retry or preceding communication.

2. A method as in claim 1, wherein the second node is downstream from the first node.

3. A method as in claim 1, wherein the route is one of a plurality of routes that covers all of the wireless mesh network nodes.

4. A method as in claim 1, wherein the 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.

5. A method as in claim 1, wherein the 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.

6. A method as in claim 1, wherein the frame length is equal to the predetermined limit time.

7. 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 the second node.

8. 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 retries of a predetermined node to node communication.

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

10. 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.

11. 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.

12. A system for communicating using a 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;

select a frame length of a frame used for communicating a packet between a first node and a second node of a wireless mesh network, wherein the frame comprises a plurality of time slots, and wherein a transmitter node transmits a packet to a receiver node during one of the plurality of time slots of the frame, and wherein the frame length is selected based at least in part on a predetermined limit time for communicating the packet between the first node and the second node;

determine a route from the first node to the second node including one or more intermediate nodes that receive and transmit the packet; and

select node to node communications within the frame along the route such that a communication latency time is below the predetermined limit time for a predetermined percentage of communications between the first node and the second node, wherein the 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 retries is based at least in part on the predetermined percentage of communications between the first node and the second node, wherein a retry slot comprises a time slot subsequent to a time slot assigned to the one node to node communication, wherein a first node to node communication is made using a first communication channel and a retry of the first node to node communication is made using a second communication channel, wherein the frame includes a set of retries for each hop along the route between the first node and the second node, wherein the set of retries for each hop is based at least in part on a reliability of communication between the first node and the second node, and wherein each retry uses a communication channel different from a communication channel used in a preceding retry or preceding communication.

18. A system as in claim 12, wherein the second node is downstream from the first node.

19. A system as in claim 12, wherein the route is one of a plurality of routes that covers all of the wireless mesh network nodes.

20. A system as in claim 12, wherein the 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.

21. A system as in claim 12, wherein the 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.

22. A system as in claim 12, wherein the frame length is equal to the predetermined limit time.

23. A system as in claim 12, 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 the second node.

24. A system as in claim 12, 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 retries of a predetermined node to node communication.

25. A system as in claim 12, wherein the memory is further configured to provide the processor with instructions which when executed cause the processor to activate a node in a route between the first node and the second node to use the frame for communicating by sending a source routed packet along the route.

26. A system as in claim 12, wherein the memory is further configured to provide the processor with instructions which when executed cause the processor to receive an acknowledgement that a prior node to node communication was successfully received and not transmitting a communication retry based on receiving the acknowledgement.

27. A system as in claim 12, wherein the memory is further configured to provide the processor with instructions which when executed cause the processor to send an acknowledgement that a prior node to node communication was successfully received and not receiving during a communication retry based on sending the acknowledgement.

13. A computer program product for communicating using a mesh network, the computer program product being embodied in a non-transitory computer readable medium and comprising computer instructions executed by a processor for:

selecting a frame length of a frame used for communicating a packet between a first node and a second node of a wireless mesh network, wherein the frame comprises a plurality of time slots, and wherein a transmitter node transmits a packet to a receiver node during one of the plurality of time slots of the frame, and wherein the frame length is selected based at least in part on a predetermined limit time for communicating the packet between the first node and the second node;

determining a route from the first node to the second node including one or more intermediate nodes that receive and transmit the packet; and

selecting node to node communications within the frame along the route such that a communication latency time is below the predetermined limit time for a predetermined percentage of communications between the first node and the second node, wherein the 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 retries is based at least in part on the predetermined percentage of communications between the first node and the second node, wherein a retry slot comprises a time slot subsequent to a time slot assigned to the one node to node communication, wherein a first node to node communication is made using a first communication channel and a retry of the first node to node communication is made using a second communication channel, wherein the frame includes a set of retries for each hop along the route between the first node and the second node, wherein the set of retries for each hop is based at least in part on a reliability of communication between the first node and the second node, and wherein each retry uses a communication channel different from a communication channel used in a preceding retry or preceding communication.

14. A device for communicating using a mesh network, comprising:

a transmitter;

a receiver;

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;

transmit a packet in a first slot of a frame using a first channel for a mesh network, wherein the frame comprises a plurality of time slots, and wherein a transmitter node transmits a packet to a receiver node during one of the plurality of time slots of the frame, wherein a frame length is selected based at least in part on a predetermined limit time for communicating the packet between the first node and the second node, wherein a communication latency time that is below the predetermined limit time for a predetermined percentage of communications between the first node and the second node 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, and wherein the predetermined number of retries is based at least in part on the predetermined percentage of communications between the first node and the second node;

in the event that an acknowledgement that the packet was received after being sent in the first slot of the frame is not received, retry transmitting the packet in a second slot of the frame using a second channel designated for retrying the transmission of the first slot, wherein the frame includes a set of retries for each hop along a route between a first node and a second node, wherein the set of retries for each hop is based at least in part on a reliability of communication between the first node and the second node, and wherein each retry uses a communication channel different from a communication channel used in a preceding retry or preceding communication.

15. A device as in claim 14, further comprising in the event that the acknowledgement that the packet was received after being sent in the first slot of the frame is received, sleeping for the second slot of the frame designated for retrying the transmission of the first slot.

16. A device for communicating using a mesh network, comprising:

a transmitter;

a receiver;

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;

in the event that a packet was not received in a first slot of a frame on a first channel, retry listening for the packet in a second slot of the frame on a second channel designated for retrying the reception of the first slot, wherein the frame comprises a plurality of time slots, and wherein a transmitter node transmits a packet to a receiver node during one of the plurality of time slots of the frame, wherein a frame length is selected based at least in part on a predetermined limit time for communicating the packet between the first node and the second node, wherein a communication latency time that is below the predetermined limit time for a predetermined percentage of communications between the first node and the second node 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 retries is based at least in part on the predetermined percentage of communications between the first node and the second node, wherein the frame includes a set of retries for each hop along a route between a first node and a second node, wherein the set of retries for each hop is based at least in part on a reliability of communication between the first node and the second node, and wherein each retry uses a communication channel different from a communication channel used in a preceding retry or preceding communication.

17. A device as in claim 16, further comprising in the event that a packet was received in a first slot of the frame, transmitting an acknowledgement that the packet was received and sleeping for a second slot of the frame designated for retrying the reception of the first slot.