Deterministic distributed network coding

• US 9,979,666 B2
• Filed: 05/31/2017
• Issued: 05/22/2018
• Est. Priority Date: 07/16/2012
• Status: Active Grant

• Current Assignee: Code On Network Coding, LLC
• Original Assignee: Code On Network Coding, LLC
• Inventors: Ho, Tracey C., Effros, Michelle
• Primary Examiner(s): Lai, Andrew
• Assistant Examiner(s): Andrews, Hoyet H
• Application Number:
  US15/609,856
• Publication Number:
  US 20170264561A1
• Time in Patent Office: 356 Days
• CPC Class Codes: H04L 1/0041 Arrangements at the transmitter end
• 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 47/38 by adapting coding or compression rate
• CPC Class Codes: H04W 4/38 for collecting sensor information

Abstract

A network and a communication method are described. The network comprises: source nodes, receiver nodes, and coding nodes. The coding nodes are connected with input links for communication of input signals to the coding nodes and output links for communication of output signals from the coding nodes. The output signals are a linear combination of the input signals. The coefficients of the linear combination are deterministically chosen based on local information available locally at the coding node.

Claims

1. A network comprising:

one or more source nodes;

one or more receiver nodes; and

coding nodes, allowing communication of source data to each receiver node, the coding nodes being connected with input links for communication of input signals to the coding nodes and output links for communication of output signals from the coding nodes, wherein the output signals from the coding nodes are a linear combination of the input signals,

wherein

a plurality of said coding nodes are configured to generate coefficients of the linear combination using local node numbers or alternatively local link numbers as inputs to a deterministic mapping from the local node numbers or alternatively from local link numbers to the coefficients of the linear combination.

2. The network of claim 1, wherein the linear combination of data transmitted from the one or more source nodes present

in each signal in the network is specified as a vector of the coefficients, each coefficient corresponding to data to be transmitted from one or more source nodes, and

said coding nodes are configured to update and to transmit the vector of coefficients by applying to the vector of coefficients linear combinations, wherein the linear combinations applied to the vector of coefficients are the same as the linear combinations applied to data transmitted through the network.

3. The network of claim 2, wherein said mapping is a modular operation, said coding nodes being configured to generate said coefficients as a linear combination mod q of the local node numbers or alternatively of the local link numbers, wherein q is a constant.

4. The network according to claim 3, wherein said linear combination is obtained by summing said local node numbers, or alternatively said local link numbers, multiplied by deterministic constant elements chosen from a finite code alphabet, wherein the constant q is a size of said code alphabet.

5. The network according to claim 2, wherein said plurality of coding nodes are further configured to generate deterministically coefficients of the linear combination also on a local counter or clock signal.

6. The network according to claim 2, wherein said node numbers and/or link numbers are obtained from physical characteristics associated to the coding nodes or the node numbers and/or the link numbers are assigned in any deterministic order.

7. The network according to claim 2, wherein the network further comprises bidirectional and/or reverse links and wherein the mapping is adjustable through feedback from the receiver nodes.

8. The network according to claim 2, further comprising routing nodes, the routing nodes being connected with input links for communication of input signals to the routing nodes and output links for communication of output signals from the routing nodes, wherein the output signals from a routing node are obtained through routing without coding of the input signals to the routing node.

9. The network according to claim 2, wherein at least some deterministically chosen coefficients of an output signal of a first coding node along a first outgoing link of the first coding node are linearly independent from deterministically chosen coefficients of an output signal of the first coding node along a second outgoing link of the first coding node.

10. The network according to claim 2, wherein at least some deterministically chosen coefficients of an output signal of a first coding node along an outgoing link of the first coding node are linearly independent from deterministically chosen coefficients of an output signal of a second coding node along an outgoing link of the second coding node.

11. The network according claim 2, wherein at least some deterministically chosen coefficients from a first output signal of a first coding node along an outgoing link of the first coding node at a first time are linearly independent from deterministically chosen coefficient from a second output signal of the first coding node along the outgoing link of the first coding node at a second time.

12. A method for transmitting data from one or more sources to each receiver of one or more receivers in a network, the method comprising:

providing coding nodes between the one or more sources and the one or more receivers;

providing, for each coding node, input links for transmitting input signals to the coding node, and output links for transmitting output signals from the coding node, the output signals being a linear combination of the input signals; and

generating at a plurality of said coding nodes coefficients of the linear combination using local node numbers or alternatively local link numbers as inputs to a deterministic mapping from the local node numbers or alternatively from local link numbers to the coefficients of the linear combination.

13. The method according to claim 12, wherein the linear combination of data transmitted from the one or more source nodes present

in each signal in the network is specified as a vector of the coefficients, each coefficient corresponding to data to be transmitted from the one or more source nodes, and

the vector of coefficients is transmitted through the network and updated at said coding nodes by applying to the vector of coefficients linear combinations, wherein the linear combinations applied to the vector of coefficients are the same as the linear combinations applied to data transmitted through the network.

14. The method according to claim 13, wherein said mapping is a modular operation, said coding nodes being configured to generate said coefficients as a linear combination mod q of the local node numbers or alternatively of the local link numbers, wherein q is a constant.

15. The method according to claim 14, wherein said linear combination is obtained by summing said local node numbers, or alternatively said local link numbers, multiplied by deterministic constant elements chosen from a finite code alphabet, wherein the constant q is a size of said code alphabet.

16. The method according to claim 13, comprising the step of generating deterministically, at said plurality of coding nodes, coefficients of the linear combination also on a local counter or clock signal.

17. The method according to claim 13, wherein said node numbers and/or link numbers are obtained from physical characteristics associated to the coding node or the node numbers and/or the link numbers are assigned in any deterministic order.

18. The method according to claim 13, wherein the network further comprises bidirectional and/or reverse links and wherein the mapping is adjustable through feedback from the receiver nodes.

19. The method according to claim 13, further comprising providing routing nodes, the routing nodes being connected with input links for communication of input signals to the routing nodes and output links for communication of output signals from the routing nodes, wherein the output signals from a routing node are obtained through routing without coding of the input signals to the routing node.

20. The method according to claim 13, wherein at least some deterministically locally generated coefficients of an output signal of a first coding node along a first outgoing link of the first coding node are linearly independent from deterministically locally generated coefficients of an output signal of the first coding node along a second outgoing link of the first coding node.

21. The method according to claim 13, wherein at least some deterministically locally generated coefficients of an output signal of a first coding node along an outgoing link of the first coding node are linearly independent from deterministically locally generated coefficients of an output signal of a second coding node along an outgoing link of the second coding node.

22. The method according to claim 13, wherein at least some deterministically locally generated coefficients from a first output signal of a first coding node along an outgoing link of the first coding node at a first time are linearly independent from deterministically locally generated coefficient from a second output signal of the first coding node along the outgoing link of the first coding node at a second time.

23. A method for transmitting data from one or more sources to each receiver of one or more receivers in a distributed network, the distributed network including i) one or more source nodes wherein source data are observable at the source nodes, ii) one or more receivers nodes wherein the source data are observable at the receiver nodes and iii) a plurality of coding nodes allowing communication of the source data to each receiver node;

the method providing for a coding node of the plurality of coding nodes;

i) one or more input links for communication of input data to the coding node from the plurality of coding nodes and/or from one or more source nodes, and

ii) one or more output links for communication of output data from the coding node to the plurality of coding nodes and/or to one or more receiver nodes, wherein the output data from the coding node are a linear combination of the input data to the coding node, and wherein coefficients of the linear combination are deterministically locally generated at the coding node based on local information available locally at the coding node.