Method, apparatus, and protocol for improving performance in a wireless network

• US 9,860,022 B2
• Filed: 02/27/2014
• Issued: 01/02/2018
• Est. Priority Date: 02/28/2013
• Status: Active Grant

• Current Assignee: Aalborg Universitet
• Original Assignee: Aalborg Universitet
• Inventors: Krigslund, Jeppe, Hansen, Jonas, Hundebll, Martin, Lucani, Daniel E., Fitzek, Frank H. P.
• Primary Examiner(s): Duong, Duc
• Application Number:
  US14/647,611
• Publication Number:
  US 20150358118A1
• Time in Patent Office: 1,405 Days
• Field of Search: None
• CPC Class Codes: H04L 1/0076 Distributed coding, e.g. network coding, involving channel coding coding in both space and time H04L1/0618; cooperative diversity H04B7/022
• CPC Class Codes: H04L 2001/0097 Relays
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04W 28/021 in wireless networks with changing topologies, e.g. ad-hoc networks self-organizing networks H04W84/18
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing

Abstract

A wireless network protocol (CORE) and related methods, systems, and circuits are disclosed that are capable of enhancing network performance. The protocol uses random linear network coding (RLNC) for intra-session coding in the network, while allowing nodes in the network to set up inter-session coding regions where flows intersect. Within the inter-session coding regions, combinations of coded packets associated with different unicast sessions are permitted. However, packets associated with multiple different unicast sessions are not allowed to be transmitted outside of the coding regions.

Claims

1. A machine implemented method for use in a wireless network having a plurality of wireless nodes, comprising:

determining routes through the wireless network for different unicast sessions;

analyzing routes in the wireless network for the different unicast sessions to identify one or more inter-session coding regions in the network, each inter-session coding region including at least one wireless relay node that is associated with multiple unicast sessions;

combining network coded packets associated with multiple unicast sessions within the wireless relay nodes of the inter-session coding regions includes exclusive-ORing (XORing) random linear network coded (RLNC) packets associated with different unicast sessions and transmitting the resulting combined packets from the wireless relay nodes to other nodes within the corresponding inter-session coding regions, wherein combining the network coded packets associated with multiple unicast sessions includes coding through linear combinations over a finite field; and

within a first node of a first inter-session coding region;

over hearing and storing transmissions of other nodes within the first inter-session coding region that are associated with different unicast sessions than the first node;

receiving and storing combined network coded packets received from a first relay node of the first inter-session coding region;

jointly using combined network coded packets and overheard transmissions stored in the first node to generate a coded packet that is associated with a single specific unicast session; and

transmitting the coded packet that is associated with the single unicast session from the first node to a node outside the first inter-session coding region;

wherein;

combining network coded packets associated with multiple unicast sessions within the wireless relay nodes of the inter-session coding regions includes, for the first relay node of the first inter-session coding region;

determining whether a new RLNC packet has been received by the first relay node for each of a plurality of unicast sessions associated with the first relay node;

if new RLNC packets have been received by the first relay node for each of the plurality of unicast sessions, XORing the new RLNC packets together; and

if a new RLNC packet has not been received by the first relay node for one of the plurality of unicast sessions, generating an RLNC packet for the unicast session using data from a local buffer and then XORing the new RLNC packet(s) with the generated RLNC packet.

2. A machine implemented method for use in a wireless network having a plurality of wireless nodes, the method comprising:

determining routes through the wireless network for different unicast sessions;

analyzing routes in the wireless network for the different unicast sessions to identify one or more inter-session coding regions in the network, each inter-session coding region including at least one wireless relay node that is associated with multiple unicast sessions;

combining network coded packets associated with multiple unicast sessions within the wireless relay nodes of the inter-session coding regions and transmitting the resulting combined packets from the wireless relay nodes to other nodes within the corresponding inter-session coding regions, wherein each unicast session in the network has an associated network coding generation size indicative of the number of data packets that are combined together in each network coded packet of the unicast session and wherein combining the network coded packets associated with multiple unicast sessions includes coding through linear combinations over a finite field;

within a first node of a first inter-session coding region;

over hearing and storing transmissions of other nodes within the first inter-session coding region that are associated with different unicast sessions than the first node;

receiving and storing combined network coded packets received from a first relay node of the first inter-session coding region;

jointly using combined network coded packets and overheard transmissions stored in the first node to generate a coded packet that is associated with a single specific unicast session; and

transmitting the coded packet that is associated with the single unicast session from the first node to a node outside the first inter-session coding region; and

sending a feedback message from a relay node of an inter-session coding region of the network to an upstream node transmitting network coded packets associated with a first unicast session to the relay node in response to receipt of a sufficient number of degrees of freedom from the upstream node to enable reliable decoding of a present generation of the first unicast session; and

ceasing transmission of network coded packets associated with the current generation of the first unicast session from the upstream node in response to the feedback message.

3. The method of claim 2, wherein:

determining routes through the wireless network for different unicast sessions is performed without coordination between the unicast sessions.

4. The method of claim 2, further comprising:

combining network coded packets associated with the same unicast session within wireless nodes both inside and outside of the inter-session coding regions and transmitting the resulting combined packets to other nodes in the network.

5. The method of claim 2, wherein:

combining network coded packets associated with multiple unicast sessions within the wireless relay nodes of the inter-session coding regions includes exclusive-ORing (XORing) random linear network coded (RLNC) packets associated with different unicast sessions.

6. The method of claim 2, wherein:

using combined network coded packets received from the first relay node of the first inter-session coding region and overheard transmissions stored in the first node to generate a coded packet that is associated with a single unicast session includes performing partial decoding of a combined network coded packet to remove effects of all unicast sessions other than the single specific unicast session.

7. The method of claim 2, wherein:

the wireless network is a wireless mesh network.

8. The method of claim 2, further comprising:

re-coding the coded packet associated with the single unicast session before transmitting the coded packet from the first node to a node outside the first inter-session coding region.

9. The method of claim 2, wherein:

determining routes through the wireless network for different unicast sessions includes identifying either a single path or multiple paths through the wireless network for each unicast session.

10. The method of claim 2, further comprising:

coordinating coding activities between different inter-session coding regions that are associated with the same unicast sessions.

11. A machine implemented method for use in a wireless network having a plurality of wireless nodes, the wireless network being capable of supporting multiple simultaneous unicast sessions, the method comprising:

defining a first inter-session coding region in the wireless network that includes a first relay node and a plurality of other nodes in a vicinity of the first relay node, the first relay node being associated with at least two different unicast sessions;

receiving new network coded packets at the first relay node for each of the at least two unicast sessions;

combining the new network coded packets using an exclusive-OR (XOR) operation to generate a combined packet in the first relay node;

transmitting the combined packet from the first relay node to at least one other node within the first inter-session coding region;

repeating receiving, combining, and transmitting at the first relay node for a number of iterations; and

if a new network coded packet is not received at the first relay node for one or more of the at least two unicast sessions during receiving for an iteration, generating a network coded packet for the corresponding unicast session(s) using data from a local buffer within the first relay node before combining;

wherein an inter-session coding region is a region of a wireless network that allows inter-session packet combinations within the coding region, but nodes within the inter-session coding region cannot transmit inter-session packet combinations to nodes outside the coding region.

12. The method of claim 11, wherein:

defining a first inter-session coding region in the wireless network includes defining a region having one of the following topologies;

an X topology, a cross topology, and an Alice and Bob topology.

13. The method of claim 11, further comprising:

transmitting a feedback message from the first relay node to an upstream transmitting node associated with a first unicast session if a sufficient number of degrees of freedom have been received at the first relay node to reliably decode a current generation of the first unicast session.

14. The method of claim 11, further comprising:

coordinating coding activities in the first inter-session coding region and another inter-session coding region in the wireless network from the first relay node.

15. The method of claim 11, wherein:

combining the new network coded packets using an XOR operation to generate a combined packet in the first relay node includes combining random linear network coded (RLNC) packets.

16. A machine implemented method for use in a wireless network having a plurality of wireless nodes, the wireless network having one or more inter-session coding regions defined around relay nodes at which routes associated with different unicast sessions intersect, the method comprising:

at a first node of a first inter-session coding region;

overhearing and storing transmissions of other nodes within the first inter-session coding region that are associated with different unicast sessions than the first node;

receiving and storing combined packets from a relay node of the first inter-session coding region at the first node, the combined packets each including a linear combination over a finite field of network coded packets associated with multiple different unicast sessions;

jointly using the combined packets and overheard transmissions stored in the first node to generate a network coded packet that is associated with a single specific unicast session; and

transmitting the network coded packet that is associated with the single unicast session from the first node to a node outside the first inter-session coding region; and

wherein the combined packets received from the relay node of the first inter-session coding region include a combination of random linear network coding (RLNC) packets associated with different unicast sessions that are exclusive ORed (XORed) together.

17. A communication device for use in a wireless mesh network, the communication device comprising:

a wireless transceiver;

digital storage;

circuitry configured to analyze routes associated with different unicast sessions within the wireless mesh network and establish at least one inter-session coding region within the wireless mesh network within which combinations of network coded packets associated with different unicast sessions are permitted, each inter-session coding region including at least one relay node that is associated with multiple unicast sessions in the network and a plurality of other nodes in a vicinity of the at least one relay node, wherein combinations of network coded packets associated with different unicast sessions are not permitted in portions of the wireless mesh network outside of inter-session coding regions;

circuitry configured to, if the communication device is acting as a non-relay node within an inter-session coding region, overhear and store transmissions of other non-relay nodes within the inter-session coding region;

circuitry configured to, if the communication device is acting as a non-relay node within an inter-session coding region, receive and store combined packets from a relay node of the inter-session coding region, the combined packets including linear combinations over a finite field of network coded packets associated with different unicast sessions;

circuitry configured to, if the communication device is acting as a non-relay node within an inter-session coding region, jointly process combined packets and overheard transmissions stored in the communication device to generate network coded packets associated with only a single unicast session, wherein the communication device only transmits packets that are associated with a single unicast session to nodes outside of the inter-session coding region;

circuitry configured to, if the communication device is acting as a relay node within an inter-session coding region, receive random linear network coded (RLNC) packets associated with different unicast sessions from other nodes within the inter-session coding region, combine the RLNC packets using an exclusive OR (XOR) operation, and transmit the combined packet to another node of the inter-session coding region; and

circuitry configured to, if the communication device is acting as a relay node within an inter-session coding region and if a new random linear network coded (RLNC) packet is not received for one or more of the different unicast sessions, generate an RLNC packet for the unicast session(s) using data stored locally within the communication device before the RLNC packets are combined.

18. A communication device for use in a wireless mesh network, the communication device comprising:

a wireless transceiver;

digital storage;

circuitry configured to analyze routes associated with different unicast sessions within the wireless mesh network and establish at least one inter-session coding region within the wireless mesh network within which combinations of network coded packets associated with different unicast sessions are permitted, each inter-session coding region including at least one relay node that is associated with multiple unicast sessions in the network and a plurality of other nodes in a vicinity of the at least one relay node, wherein combinations of network coded packets associated with different unicast sessions are not permitted in portions of the wireless mesh network outside of inter-session coding regions;

circuitry configured to, if the communication device is acting as a non-relay node within an inter-session coding region, overhear and store transmissions of other non-relay nodes within the inter-session coding region;

circuitry configured to, if the communication device is acting as a non-relay node within an inter-session coding region, receive and store combined packets from a relay node of the inter-session coding region, the combined packets including linear combinations over a finite field of network coded packets associated with different unicast sessions;

circuitry configured to, if the communication device is acting as a non-relay node within an inter-session coding region, jointly process combined packets and overheard transmissions stored in the communication device to generate network coded packets associated with only a single unicast session, wherein the communication device only transmits packets that are associated with a single unicast session to nodes outside of the inter-session coding region; and

circuitry configured to, when the communication device is acting as a relay node within an inter-session coding region, send a feedback message to an upstream transmitting node associated with a first unicast session when a sufficient number of degrees of freedom have been received from the upstream node to decode a current RLNC generation.

19. The communication device of claim 18, further comprising:

circuitry configured to, if the communication device is acting as a relay node within an inter-session coding region, receive random linear network coded (RLNC) packets associated with different unicast sessions from other nodes within the inter-session coding region, combine the RLNC packets using an exclusive OR (XOR) operation, and transmit the combined packet to another node of the inter-session coding region.

20. The communication device of claim 18, further comprising:

circuitry configured to, if the communication device is acting as a non-relay node within an inter-session coding region, jointly process combined packets and overheard transmissions stored in the communication device to generate network coded packets associated with only a single unicast session, wherein jointly processing combined packets includes performing partial decoding of a combined network coded packet to remove effects of all unicast sessions other than the single specific unicast session.

21. The communication device of claim 18, further comprising:

circuitry configured to, if the communication device is acting as a relay node within an inter-session coding region and if a new random linear network coded (RLNC) packet is not received for one or more of the different unicast sessions, generate an RLNC packet for the unicast session(s) using data stored locally within the communication device before the RLNC packets are combined.

22. The communication device of claim 18, further comprising:

circuitry configured to, if the communication device is acting as a non-relay node within an inter-session coding region, re-code the coded packet associated with the single unicast session before transmitting the coded packet from the communication device to at least one node outside the inter-session coding region.

23. A machine implemented method for use in a wireless network having a plurality of wireless nodes, comprising:

determining routes through the wireless network for different unicast sessions;

analyzing routes in the wireless network for the different unicast sessions to identify one or more inter-session coding regions in the network, each inter-session coding region including at least one wireless relay node that is associated with multiple unicast sessions;

combining network coded packets associated with multiple unicast sessions within the wireless relay nodes of the inter-session coding regions and transmitting the resulting combined packets from the wireless relay nodes to other nodes within the corresponding inter-session coding regions, wherein combining the network coded packets associated with multiple unicast sessions includes coding through linear combinations over a finite field; and

within a first node of a first inter-session coding region;

over hearing and storing transmissions of other nodes within the first inter-session coding region that are associated with different unicast sessions than the first node;

receiving and storing combined network coded packets received from a first relay node of the first inter-session coding region;

jointly using combined network coded packets and overheard transmissions stored in the first node to generate a coded packet that is associated with a single specific unicast session; and

transmitting the coded packet that is associated with the single unicast session from the first node to a node outside the first inter-session coding region;

and wherein;

performing partial decoding of a combined network coded packet to remove effects of all unicast sessions other than the single specific unicast session includes performing partial decoding using a matrix of network coding coefficients; and

using combined network coded packets received from the first relay node of the first inter-session coding region and overheard transmissions stored in the first node to generate a coded packet that is associated with a single unicast session includes performing partial decoding of a combined network coded packet to remove effects of all unicast sessions other than the single specific unicast session.

24. A machine implemented method for use in a wireless network having a plurality of wireless nodes, the wireless network having one or more inter-session coding regions defined around relay nodes at which routes associated with different unicast sessions intersect, the method comprising:

at a first node of a first inter-session coding region;

overhearing and storing transmissions of other nodes within the first inter-session coding region that are associated with different unicast sessions than the first node;

receiving and storing combined packets from a relay node of the first inter-session coding region at the first node, the combined packets each including a linear combination over a finite field of network coded packets associated with multiple different unicast sessions;

jointly using the combined packets and overheard transmissions stored in the first node to generate a network coded packet that is associated with a single specific unicast session; and

transmitting the network coded packet that is associated with the single unicast session from the first node to a node outside the first inter-session coding region;

and wherein using the combined packets and overheard transmissions stored in the first node to generate a coded packet that is associated with a single specific unicast session includes performing partial decoding, using a matrix of network coding coefficients, of a combined coded packet to remove effects of all unicast sessions other than the single specific unicast session.

25. The method of claim 24, wherein no inter-session coded packets are transmitted from nodes within the first inter-session coding region to nodes outside the first inter-session coding region in the wireless network.

26. The method of claim 24, further comprising:

re-coding the network coded packet associated with the single unicast session before transmitting the network coded packet from the first node to the node outside the first inter-session coding region.