Methods and apparatus to utilize network coding in a wireless network

1. A method for network coding in a wireless network, the method comprising:

receiving a first packet flow at a first node from a second node that is one-hop away from the first node, the first packet flow originating at a first source;

receiving a second packet flow at the first node from a third node that is one-hop away from the first node, the second packet flow originating at a second source;

generating, for the first packet flow, first intra-session parity packets using intra-session network coding and generating, for the second packet flow, second intra-session parity packets using intra-session network coding, the first and second intra-session parity packets being generated based on loss rates of links between the first and second nodes and the first and third nodes, and between the first node and a fourth node and between the first node and a fifth node, the fourth and fifth nodes being one-hop away from the first node; and

combining, at the first node, the first and second packet flows and the first and second intra-session parity packets into a combined packet flow using inter-session network coding.

2. The method as defined in claim 1 , further comprising transmitting the combined packet flow to the fourth and fifth nodes.

3. The method as defined in claim 1 , further comprising determining, at the first source, a number of packets in the first packet flow and third intra-session parity packets using intra-session network coding based on a number of original packets received from a transport layer and loss rates of links within the wireless network.

4. The method as defined in claim 1 , further comprising:

transmitting the first packet flow from the fifth node to a destination;

using intra-session network coding to decode the first packet flow into the original packets; and

transmitting, from the destination to the first source, an acknowledgement message for each original packet received.

5. The method as defined in claim 4 , wherein the intra-session network coding employs adaptation to generate the first and second intra-session parity packets.

6. The method as defined in claim 1 , wherein combining the first and second packet flows includes at least one of summing and XORing a packet at a first position in a virtual queue within the packet flow with a packet from the second packet flow at the same position in the virtual queue.

7. The method as defined in claim 1 , further comprising:

decoding the combined packet flow at the fourth node using the combined packet flow and the first packet flow overheard at the fourth node to determine the second packet flow; and

decoding the combined packet flow at the fifth node using the combined packet flow and the second packet flow overheard at the fifth node to determine the first packet flow.

8. The method as defined in claim 1 , wherein the first and second intra-session parity packets are generated based on which packets of the first and second packet flows are overheard by the fourth and fifth nodes.

9. The method as defined in claim 1 , wherein the first and second intra-session parity packets are determined based on a function that reduces a queue size of the first and second packet flows while ensuring there are enough packets to enable the fourth and fifth nodes to decode the combined packet flow.

10. A first node in a wireless network, the first node comprising:

a network coding processor to:

receive a first packet flow from a second node that is one-hop away from the first node, the first packet flow originating at a first source; and

receive a second packet flow from a third node that is one-hop away from the first node, the second packet flow originating at a second source;

an intra-session processor to:

determine, for the first packet flow, first intra-session parity packets using intra-session network coding;

determine, for the second packet flow, second intra-session parity packets using intra-session network coding, the first and second intra-session parity packets being determined based on loss rates of links between the first and second nodes and the first and third nodes, and between the first node and a fourth node and between the first node and a fifth node, the fourth and fifth nodes being one-hop away from the first node;

add the first and second packet flows to a virtual queue within the first node; and

add the first and second intra-session parity packets to the first and second packet flows.

11. The first node as defined in claim 10 , further comprising an inter-session processor to:

combine the first and second packet flows and the first and second intra-session parity packets into a combined packet flow using inter-session network coding; and

transmit the combined packet flow to the fourth and fifth nodes.

12. The first node as defined in claim 10 , wherein the first, second, third, fourth, and fifth nodes are wireless network routers.

13. The first node as defined in claim 10 , wherein the intra-session processor is to determine the first and second intra-session parity packets based on which packets of the first and second packet flows were overheard at the fourth and fifth nodes.

14. The first node as defined in claim 11 , wherein the inter-session processor is to combine the first and second packet flows by at least one of summing and XORing a packet at a position in the virtual queue within the first packet flow with a packet from the second packet flow at the same position in the virtual queue.

15. The first node as defined in claim 10 , wherein the intra-session processor is to determine the first and second intra-session parity packets based on a function that reduces a queue size of the first and second packet flows while ensuring there are enough packets to enable the fourth and fifth nodes to decode the combined packet flow.

16. The first node as defined in claim 10 , wherein the intra-session processor is to determine the first and second intra-session parity packets to compensate for the loss rates in the wireless network.

17. A tangible computer readable medium comprising instructions that, when executed, cause a first node to at least:

receive a first packet flow from a second node that is one-hop away from the first node, the first packet flow originating at a first source;

receive a second packet flow from a third node that is one-hop away from the first node, the second packet flow originating at a second source;

generate, for the first packet flow, first intra-session parity packets using intra-session network coding and generate, for the second packet flow, second intra-session parity packets using intra-session network coding, the first and second intra-session parity packets being generated based on loss rates of links between the first and second nodes and the first and third nodes, and between the first node and a fourth node and between the first node and a fifth node, the fourth and fifth nodes being one-hop away from the first node; and

combine the first and second packet flows and the first and second intra-session parity packets into a combined packet flow using inter-session network coding.

18. The tangible computer readable medium as defined in claim 17 , wherein the instructions, when executed, cause the first node to transmit the combined packet flow to the fourth and fifth nodes.

19. The tangible computer readable medium as defined in claim 17 , wherein the instructions, when executed, cause the first node to determine the first and second intra-session parity packets based on a function that reduces a queue size of the first and second packet flows while ensuring there are enough packets to enable the fourth and fifth nodes to decode the combined packet flow.

20. The tangible computer readable medium as defined in claim 17 , wherein the instructions, when executed, cause the first node to combine the first and second packet flows by at least one of summing and XORing a packet at a first position in the virtual queue within the packet flow with a packet from the second packet flow at the same position in the virtual queue.