Method and apparatus to enhance routing protocols in wireless mesh networks

• US 10,028,198 B2
• Filed: 03/12/2014
• Issued: 07/17/2018
• Est. Priority Date: 03/14/2013
• Status: Active Grant

• Current Assignee: Aalborg Universitet
• Original Assignee: Aalborg Universitet
• Inventors: Fitzek, Frank H. P., Lucani, Daniel E., Pahlevani, Peyman
• Primary Examiner(s): Mian, Omer S
• Application Number:
  US14/775,102
• Publication Number:
  US 20160021599A1
• Time in Patent Office: 1,588 Days
• CPC Class Codes: H04L 12/6418 Hybrid transport
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A protocol for use in wireless mesh networks (PlayNCool) uses helper nodes to improve data flow in the network. The protocol is compatible with traditional mesh network routing algorithms. Techniques, systems, devices, and circuits for implementing the protocol are described.

Claims

1. A machine implemented method for use in a wireless mesh network, the method comprising:

acquiring data packets at a source node that need to be delivered to a remote destination node through the wireless mesh network;

determining at least one route through the wireless mesh network from the source node to the destination node to support a data flow for the acquired data packets;

for a link between the source node and a first relay node in a route, automatically activating, based on channel conditions within the network, a helper node to assist the link in transferring data from the source node to the first relay node;

generating random linear network coded (RLNC) packets at the source node for a first group of original packets of the data flow;

initiating transmission of RLNC packets from the source node to the first relay node for the first group of original packets;

overhearing RLNC packets transmitted by the source node for the first group of original packets at the helper node;

re-coding overheard RLNC packets at the helper node for the first group of original packets to create re-coded RLNC packets comprising linear combinations of the RLNC packets;

determining a delay that corresponds to a determined amount of time, calculated via delay calculation circuitry, which the helper node will have to wait before transmitting re-coded versions of RLNC packets overheard from the source node and wherein calculating the delay is based, at least in part, on channel conditions in the wireless mesh network or other active users or nodes in the wireless mesh network;

after the delay, initiating transmission of the re-coded RLNC packets from the helper node to the first relay node for the first group of original packets of the data flow; and

continuing to transmit RLNC packets from at least one of the source node and the helper node until the first relay node has received a sufficient number of degrees-of-freedom (DOFs) to decode the first group of original packets.

2. The method of claim 1 further comprising:

repeating generating, initiating transmission, and overhearing of RLNC packets, re-coding of overheard RLNC packets, initiating transmission of re-coded RLNC packets, and continuing for each subsequent group of original packets after the first group of original packets.

3. The method of claim 1, further comprising:

for a second link between the first relay node and a second relay node in the route, activating a second helper node to assist the second link in transferring data from the first relay node to the second relay node;

generating re-coded RLNC packets at the first relay node for the first group of original packets;

initiating transmission of re-coded RLNC packets from the first relay node to the second relay node for the first group of original packets;

overhearing RLNC packets or linear combinations thereof transmitted by the first relay node for the first group of original packets at the second helper node;

re-coding overheard RLNC packets at the second helper node for the first group of original packets;

after a second delay, initiating transmission of re-coded RLNC packets from the second helper node to the second relay node for the first group of original packets; and

continuing to transmit RLNC packets from at least one of the first relay node and the second helper node until the second relay node has received a sufficient number of degrees-of-freedom (DOFs) to decode the first group of original packets.

4. The method of claim 3, wherein:

generating re-coded RLNC packets at the first relay node for the first group of original packets includes using a variable parameter to control timing of re-coding operations in the first relay node.

5. The method of claim 1,

wherein:

the delay of the helper node is expressed as a number of RLNC packets that the helper node has to overhear from the source node before initiating transmission of re-coded RLNC packets.

6. The method of claim 1, further comprising:

estimating, at the source node, a number of RLNC packets that will need to be transmitted from the source node for the first group of original packets, wherein generating RLNC packets includes generating the estimated number of packets.

7. The method of claim 1, further comprising:

estimating a number of re-coded packets that will be transmitted from the helper node for the first group of original packets.

8. The method of claim 1, further comprising:

transmitting an ACK message from the first relay node after the first relay node has received the sufficient number of DOFs to decode the first group of original packets, wherein at least one of the source node and the helper node will cease to transmit RLNC packets for the first group of original packets in response to the ACK message.

9. The method of claim 1, wherein:

re-coding overheard RLNC packets at the helper node for the first group of original packets includes using a variable parameter to control timing of re-coding operations and/or transmissions in the helper node.

10. The method of claim 1, further comprising:

at a helper node associated with one link in the route, overhearing packets or linear combinations thereof transmitted by a helper node associated with another, different link in the route.

11. A machine implemented method for use in a wireless mesh network, the method comprising:

acquiring a group of data packets at a first wireless node for transmission to a second wireless node via a direct wireless link;

automatically activating, based on channel conditions within the network, a helper node to assist in transmission of data from the first wireless node to the second wireless node;

generating random linear network coded (RLNC) packets at the first wireless node by linearly combining the group of data packets;

initiating transmission of the RLNC packets from the first wireless node to the second wireless node through the direct wireless link;

overhearing RLNC packets or linear combinations thereof transmitted by the first wireless node at the helper node;

re-coding overheard RLNC packets within the helper node to generate re-coded RLNC packets comprising linear combinations of the overheard RLNC packets;

after a determined finite delay, initiating transmission of re-coded RLNC packets from the helper node to the second wireless node;

wherein the determined finite delay corresponds to a determined amount of time calculated, via delay calculation circuitry, which the helper node will have to wait before transmitting re-coded versions of RLNC packets overheard from the first wireless node and wherein the calculated delay is based, at least in part, on channel conditions in the wireless mesh network or other active users or nodes in the wireless mesh network; and

continuing to transmit RLNC packets from at least one of the first wireless node and the helper node until the second wireless node has received a sufficient number of degrees-of-freedom (DOFs) to decode the group of data packets.

12. The method of claim 11, wherein:

automatically activating a helper node includes determining at the first wireless node that a helper node is needed and sending a request to another node in the wireless mesh network requesting that the other node serve as a helper node for the link between the first wireless node and the second wireless node.

13. The method of claim 11, wherein:

calculating the delay of the helper node is performed at either the first wireless node or the helper node.

14. The method of claim 11, wherein:

the delay of the helper node is expressed as a number of RLNC packets that the helper node has to overhear from the source node before transmission of re-coded RLNC packets is initiated.

15. The method of claim 11, further comprising:

transmitting an ACK message from the second wireless node after the second wireless node has received the sufficient number of DOFs to decode the group of data packets, wherein at least one of the first wireless node and the helper node will cease to transmit RLNC packets associated with the group of data packets in response to the ACK message.

16. The method of claim 11, wherein:

activating a helper node to assist in transmission of data from the first wireless node to the second wireless node includes activating a first helper node; and

the method further comprises activating at least one additional helper node to assist in transmission of data from the first wireless node to the second wireless node.

17. The method of claim 16, wherein:

the at least one additional helper node includes a secondary helper node that is configured to overhear RLNC packets transmitted by the first helper node.

18. The method of claim 11, wherein:

the group of data packets is representative of a single group of original packets of a data transfer between a source node and a destination node via a route that includes the first and second wireless nodes.

19. The method of claim 11, wherein:

the group of data packets includes RLNC packets; and

generating RLNC packets at the first wireless node includes re-coding RLNC packets in the group of data packets.