Cooperative subspace multiplexing in communication networks

A source node selects a plurality of transmitting nodes to cooperatively encode a set of original packets to transfer to a destination node. Encoding produces a plurality of coded packets and a corresponding code matrix of coefficients. The coded packets and the corresponding code matrix comprise a set of independent equations of independent variables in a system of linear equations, wherein the independent variables comprise the original packets. A destination node may select a set of receiving nodes to cooperatively receive the transmissions. The destination node collects the coded packets and code matrix from the receiving nodes, which provide a sufficient number of independent equations for decoding the original packets. Decoding comprises calculating a solution for the system of linear equations.

BACKGROUND

1. Field of the Invention

Subject matter disclosed herein relates generally to data communications, and more particularly, to techniques, systems, and protocols for use in employing cooperative subspace processing when transferring data between locations.

Limited storage of mobile devices is driving cloud services in which data and software are stored on the network. However, in wireless networks, limited wireless bandwidth, variable reliability of the communication channels, and mobility of the client devices discourages off-site data storage and produces significant challenges to media distribution.

Wireless communication devices (e.g., smart phones and other handheld communicators, tablet computers with communication functionality, etc.) often possess multiple network interfaces for use with different network technologies having different connectivity characteristics. The different network technologies may each have, for example, different delay, throughput, and reliability characteristics. A mobile device that is connected to a remote source node through both a cellular network (i.e., a wireless wide area network (WWAN)) and an IEEE 802.11 wireless local area network (i.e., a WLAN) may, for example, observe different usage costs and quality of service through each interface. It would be desirable to be able to utilize multiple available network resources to carry out a data transfer operation for a communication device to, for example, increase throughput, decrease data transit time, and/or make efficient use of available resources. It would also be desirable if this could be done in a reliable and efficient manner that takes advantage of already existing communication techniques and protocols.

Accordingly, content delivery mechanisms need to adapt to highly variable network topologies and operating conditions in order to provide reliable media and data services. These and other needs in the field may be addressed by aspects of the present invention.

SUMMARY

Techniques, devices, systems, and protocols are described herein that support efficient and reliable data transfer between communication nodes via multiple different paths, such as subchannels, channels, and network channels involving different network technologies. In aspects of the disclosure, subspace coding generates linear combinations of original data sets for multiplexing the original data sets into subspace-coded data sets, which are transmitted over the multiple paths. Subspace decoding is provided for demultiplexing received subspace-coded data sets. In some aspects, multiple transmitting nodes are configured to cooperatively perform subspace coding to build the dimension spanned by the subspace of the transmitted signals. In some aspects, multiple receiving nodes are configured to cooperatively perform subspace decoding, such as to build the dimension of the subspace spanned by the received signals.

The solution set to any homogeneous system of linear equations with n variables is a subspace in the coordinate space Kn, wherein the coordinate space Knis the prototypical example of an n-dimensional vector space over a field K. Every subspace of Kncan be described as the null space of some matrix. For example, in a finite-dimensional space, a homogeneous system of linear equations can be written as a single matrix equation: Ax=0, wherein the set of solutions to this equation is the null space of the matrix A. Given a set of n independent functions, the dimension of the subspace in Kkwill be the dimension of the null set of A, the composite matrix of the n functions.

In accordance with one aspect of the concepts, systems, circuits, and techniques described herein, a machine implemented method for use in transferring data from a source node to a destination node comprises selecting a plurality of original packets to transfer to a destination node; selecting a plurality of transmitting nodes to perform cooperative encoding; cooperatively encoding the original packets for generating a plurality of coded packets and a corresponding code matrix of coefficients, the coded packets and the corresponding code matrix comprising a plurality of independent equations having a plurality of independent variables in a system of linear equations, wherein the independent variables comprise the original packets; and transmitting the plurality of coded packets and corresponding code matrix to a destination node.

In one aspect of the disclosure, the code matrix comprises a matrix of random coefficients. For example, the coded packets may comprise random linear combinations of the original packets. The coefficients may comprise scalar and/or complex coefficients. Coding may employ sliding window and/or block codes. In another aspect of the disclosure, the code matrix is an invertible transform matrix, such as a block transform or a sliding window transform. For example, CI codes may be employed.

Aspects of the disclosure describe methods for ensuring that the number of independent equations is sufficient for enabling the destination node to decode the plurality of independent variables. Methods are also disclosed for ensuring the corresponding code matrix is well-conditioned.

In accordance with some aspects of the disclosure, coding is provided to the coded packets and corresponding code vectors of the code matrix at intermediate nodes, such as by applying linear coding to the coded packets and the code vectors.

In accordance with another aspect of the concepts, systems, circuits, and techniques described herein, a machine implemented method for use in processing coded packets received from a source node comprises: selecting a plurality of receiving nodes for cooperatively receiving a transmission from the source node, the plurality of receiving nodes being selected to provide a sufficient number of independent equations for decoding a plurality of original packets encoded in the transmission; collecting a plurality of coded packets and a corresponding code matrix from the receiving nodes; and decoding the packets, wherein decoding comprises calculating a solution for a system of linear equations comprising the independent equations having a plurality of independent variables, the independent equations comprising the plurality of coded packets and the corresponding code matrix, and the plurality of independent variables comprising the plurality of original packets.

In one aspect of the disclosure, the coded packets are encoded by the source node. In another aspect, encoding is provided by transmitting signals in a multipath channel. In a wireless channel, selecting the transmitting and/or receiving nodes may comprise any adaptive array processing techniques. In some aspects, it is disclosed how selecting the nodes can build the rank of the code matrix and/or improve the conditioning of the code matrix. For example, as the destination node collects code vectors, it may build up the dimension of the subspace spanned by the received code vectors.

In one aspect of the disclosure, the solution can be calculated when the number of degrees of freedom received at least equals the number of original packets. In another aspect of the disclosure, the solution may be calculated when the number of degrees of freedom received is less than the number of original packets, such as when a CI code matrix is employed for coding. In accordance with certain aspects, a destination node determines whether coded packets are linearly independent, such as by performing a row-reduction operation (or other algorithms for solving systems of linear equations) on the code matrix.

In accordance with another aspect of the concepts, systems, circuits, and techniques described herein, a machine implemented method for use in transferring data from a source node to a destination node comprises: selecting a plurality of original packets to transfer to the destination node; selecting a plurality of transmitting nodes to cooperatively encode the original packets for generating a plurality of coded packets and a corresponding code matrix; and providing for transmitting from each of the transmitting nodes a subset of the plurality of coded packets and corresponding code matrix, wherein at least one of the transmitting nodes has a rank that is insufficient for decoding the plurality of coded packets.

In some aspects of the disclosure, cooperative encoding is configured to ensure that the code matrix has sufficient rank and is sufficiently well-conditioned to enable the destination node to decode the coded packets. In some aspects, at least one intermediate node provides additional encoding to the plurality of coded packets and corresponding code matrix. For example, additional subspace coding may be provided to the coded packets and the code vector at each intermediate node by applying linear coding to the coded packets and the code vector.

In some aspects of the disclosure, the transmitting nodes may retransmit coded packets, such as when an acknowledgement has not been received from the destination node after a predetermined amount of time. In some aspects, new linear combinations of the original packets are transmitted, such as when retransmission occurs after a delay that at least equals the coherence time of the channel.

In accordance with another aspect of the concepts, systems, circuits, and techniques described herein, a machine implemented method for use in processing coded packets received from a source node comprises: selecting a plurality of receiving nodes to cooperatively receive a plurality of linearly coded packets and a plurality of corresponding code vectors, wherein the rank of at least one of the receiving nodes is insufficient for decoding the coded packets; building up a dimension of a subspace spanned by code vectors received at the destination node by collecting the coded packets and the corresponding code vectors from the plurality of receiving nodes; and decoding the coded packets.

In one aspect of the disclosure, when the receiving nodes transmit their received signals to the destination node, they provide additional linear encoding to the coded packets and the corresponding code vectors. In some aspects, the destination node (and/or the receiving nodes) transmit an acknowledgement to the source node upon at least one of receiving a coded packet and decoding an original packet. In some aspects, building up the dimension of the subspace spanned by the code vectors may further comprise collecting at least one additional coded packet and corresponding code vector transmitted by the source node during a later time interval.

In accordance with some aspects of the disclosure, the plurality of receiving nodes is configured to cooperatively receive the linearly coded packets and corresponding code vectors transmitted over a plurality of different network channels. The different network channels may comprise different multiple-access channels on the same network and/or channels on different networks. The destination node and/or the receiving nodes may employ different network technologies.

In accordance with another aspect of the concepts, systems, circuits, and techniques described herein, a machine implemented method for use in processing coded packets received from a source node comprises: determining a required number of degrees of freedom for decoding a plurality of linearly coded packets received from a source node; based on the required number of degrees of freedom, selecting at least one additional receiving node for cooperatively receiving at least one coded packet and associated code vector; collecting a plurality of coded packets and associated code vectors from a plurality of cooperating receiving nodes, including the at least one additional receiving node; and decoding the plurality of coded packets.

In some aspects of the disclosure, determining the required number of degrees of freedom comprises counting the number of collected code vectors, determining the number of collected linearly independent code vectors, and/or determining the rank of a matrix comprising the collected code vectors. Selecting additional receiving nodes and collecting coded packets and/or associated code vectors therefrom may be performed until the number of received linearly independent coded packets is at least equal to the required number of degrees of freedom. In some aspects, decoding comprises arranging the associated code vectors in a matrix, and then performing at least one matrix operation on the plurality of coded packets.

In accordance with another aspect of the concepts, systems, circuits, and techniques described herein, a machine implemented method for transmitting a file between a server and a client comprises: generating a plurality of linearly coded packets from a plurality of original packets; selecting a plurality of transmitting nodes to perform cooperative subspace processing; and coordinating the plurality of transmitting nodes to increase a dimension of a subspace spanned by the linearly coded packets to provide the client with a sufficient number of linearly independent coded packets from which to retrieve the plurality of original packets.

In accordance with certain aspects of the disclosure, the plurality of transmitting nodes comprises a plurality of intermediate nodes between the server and the client, the intermediate nodes being configured to receive and retransmit the coded packets.

In accordance with another aspect of the concepts, systems, circuits, and techniques described herein, a machine implemented method for transmitting data from a source node via multiple different network channels comprises: encoding a plurality of original packets for generating a plurality of linearly coded packets and corresponding code vectors for transfer to a destination node; selecting a first network channel and at least a second network channel to simultaneously employ in the transfer; and distributing a first subset of the plurality of linearly coded packets and corresponding code vectors to the first network channel and distributing a second subset of the plurality of linearly coded packets and corresponding code vectors to the at least second network channel, wherein at least one of the first subset and the second subset has a rank that is insufficient for decoding the plurality of coded packets, and wherein a sum of ranks of the first subset and the second subset is sufficient for decoding the plurality of coded packets.

In one aspect of the disclosure, the first network channel resides on a first network and the second network channel resides on a second network that is different than the first network. In some aspects, distributing comprises network load balancing whereby a lesser number of packets is distributed to a network channel having a lesser capacity and a greater number of packets is distributed to a network channel having a greater capacity. Aspects of the disclosure provide for coordinating a plurality of transmitting nodes to cooperatively transmit the linearly coded packets and/or coordinating a plurality of receiving nodes to cooperatively receive the linearly coded packets. The linearly coded packets may comprise random linearly coded packets with coefficients generated at random and/or deterministically.

An aspect of the disclosure further comprises monitoring at least one real-time property of the first network channel and the second network channel, and encoding and/or distributing may be adjusted based on the monitoring to provide for network load balancing.

In some aspects, encoding comprises selecting a plurality of transmitting nodes to build the dimension of the subspace of a transmitted signal comprising the coded packets. Similarly, a plurality of cooperating receiving nodes may be selected to build the dimension of the subspace of a received signal. In some aspects of the disclosure, encoding and distributing are performed such that the destination node needs to receive coded packets from a plurality of network channels in order to have a sufficient number of degrees of freedom to decode the coded packets.

In accordance with another aspect of the concepts, systems, circuits, and techniques described herein, a machine implemented method for use in processing data to be transmitted from a source node on multiple different paths comprises: selecting a plurality of original packets for subspace coding to generate a plurality of linearly coded packets from a plurality of original packets; selecting a plurality of nodes to cooperatively perform subspace processing, whereby the plurality of nodes employs a plurality of transmission paths for transmitting the plurality of linearly coded packets and associated code vectors to a destination node, each of the plurality of transmission paths providing a linearly independent combination of the original packets to the destination node; and coordinating the plurality of nodes to produce a sufficient number of the plurality of transmission paths to enable the destination node to perform decoding to retrieve the plurality of original packets.

In some aspects of the disclosure, the above-recited plurality of nodes comprises one or more intermediate nodes. In an aspect of the disclosure, the method above further comprises transmitting new linear combinations until the destination node decodes the coded packets.

In accordance with another aspect of the concepts, systems, circuits, and techniques described herein, a machine implemented method for use in processing and distributing data comprises: generating a plurality of sub-space coefficients to encode a plurality of original data packets; generating a plurality of subspace-encoded data packets by employing the plurality of sub-space coefficients to produce linear combinations of the original data packets; and distributing the sub-space coefficients and the subspace-encoded data to a plurality of transmitting nodes for transmission to a destination node.

In some aspects of the disclosure, the plurality of transmitting nodes may comprise edge servers in a content delivery network. The sub-space coefficients and subspace-encoded data packets may be stored on the transmitting nodes before being served to the destination node.

In accordance with another aspect of the concepts, systems, circuits, and techniques described herein, a machine implemented method for use in processing and distributing data comprises: selecting a plurality of receiving nodes for cooperatively receiving a plurality of subspace-encoded data packets and corresponding subspace codes; distributing the plurality of subspace-encoded data packets and the subspace codes collected by the plurality of receiving nodes to a destination node; and decoding the subspace-encoded data packets to retrieve a plurality of original data packets encoded in the subspace-encoded data packets.

In some aspects of the disclosure, the plurality of receiving nodes may comprise edge servers in a content delivery network. The sub-space coefficients and subspace-encoded data packets may be stored on the receiving nodes before being collected by the destination node.

In accordance with another aspect of the concepts, systems, circuits, and techniques described herein, at least one source node is configured to transmit a plurality of original data packets; and a plurality of coding nodes are configured to output a plurality of coded packets comprising linear combinations of the original data packets. The coding nodes are configured to provide a sufficient number of degrees of freedom to enable a destination node to decode the coded packets. The coefficients of the linear combinations may be randomly chosen. A deterministic process may be employed for generating random coefficients. In some aspects, an invertible transform matrix may be employed for generating the coefficients.

In accordance with another aspect of the concepts, systems, circuits, and techniques described herein, a machine implemented method for use in distributing subspace-encoded data comprises: selecting a plurality of nodes to cooperatively function as a subspace multiplexing process; separating a data set into a plurality N of original components; generating a plurality of subspace-coded components by generating at least N linear combinations of the original components; and distributing the plurality of subspace-coded components and a plurality of associated subspace code vectors to the plurality of nodes, such that at least one of the plurality of nodes has a number of coded components that is less than a number of required degrees of freedom to decode the plurality of subspace-coded components.

In accordance with an aspect of the disclosure, the above method further comprises: at a destination node, collecting a plurality of the subspace-coded components and associated subspace code vectors from a plurality of the nodes until a sufficient number of linearly independent code vectors have been collected to decode the coded components; and decoding the subspace-coded components.

In some aspects of the disclosure, the selected nodes are nearby a destination node in a peer-to-peer network. In some aspects, the plurality of nodes comprises end nodes in a content delivery network. The physical wireless channel may provide the required statistical randomness for the coding. Codes may be based on measurements of the physical wireless channel. Codes may be generated deterministically. In some aspects, coding may comprise employing a sliding coding window.

In another aspect of the disclosure, a method for transmitting data from a source node to a destination node comprises forming linear combinations of original packets from a source node to produce subspace-coded packets, and delivering the subspace-coded packets to the destination node over one or more network paths. Based on the responsiveness of the destination node, the source node may produce new linear combinations of the original packets, and deliver the new subspace-coded packets to the destination node. This adaptive technique can be used to select the number of transmitting antennas and/or receiving antennas in a wireless network.

DETAILED DESCRIPTION

In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the invention. It should be understood, however, that the particular aspects shown and described herein are not intended to limit the invention to any particular form, but rather, the invention is to cover all modifications, equivalents, and alternatives falling within the scope of the invention as defined by the claims.

FIG. 1is a diagram illustrating one possible aspect of a cooperative-MIMO system in which multiple nodes are employed at both the transmitter side and the receiver side of a WWAN (i.e., long-haul) transmission link. This figure and the figures that follow are for demonstrative purposes only and are not intended to limit the scope of the pending claims.

A node, as used herein, is an active electronic device that is communicatively connected to a network via one or more connectors and is configured for sending, receiving, and/or forwarding information over a communication channel. A device may have multiple network connectors for a given network. For example, a device may have multiple antennas. However, a single device with multiple network connectors is a single node. In a distributed network, nodes are clients, servers, or peers. A peer may sometimes serve as a client and sometimes as a server. Nodes may include super nodes, which route data for other networked devices as well as themselves.

On the transmit side, a first local group110comprises a plurality Ntof transmitting nodes111.1,111.2, . . . ,111.Nt. Each node111.1,111.2, . . . ,111.Ntmay employ a WLAN (i.e., local transmissions101-103) to broadcast its data to one or more of the other transmitting nodes111.1,111.2, . . . ,111.Nt. Thus, the local group110of transmitting nodes may comprise all nodes111.1,111.2, . . . ,111.Ntthat are communicatively coupled together by a WLAN.

In alternative aspects, the nodes111.1,111.2, . . . ,111.Ntdo not share their data with the other transmitting nodes111.1,111.2, . . . ,111.Nt. In such aspects, the local group110may comprise transmitting nodes111.1,111.2, . . . ,111.Ntthat self organize or that are configured by a WWAN controller (not shown) to simultaneously employ the same WWAN channel (e.g., frequency band, time slot, and/or code space).

Each transmitting node111.1,111.2, . . . ,111.N, transmits at least a respective WWAN signal115.1,115.2, . . . ,115.M, into a WWAN channel99. In some aspects of the invention, one or more of the transmitting nodes111.1,111.2, . . . ,111.N, may comprise a plurality of (Mt) antennas. In such aspects, the transmitting nodes111.1,111.2, . . . ,111.N, may generate a number up to Mtof simultaneous transmissions that exceeds the number Ntof nodes.

On the receiver side, a second local group120comprises a plurality Nrof receiving nodes121.1,121.2, . . . ,121.N, that join together for cooperative reception. Each of the receiving nodes121.1,121.2, . . . ,121.Nrreceives at least a respective WWAN signal125.1,125.2, . . . ,125.Mrfrom the WWAN channel99. In some aspects of the invention, one or more of the receiving nodes121.1,121.2, . . . ,121.Nrmay comprise multiple antennas. Thus, the receiving nodes121.1,121.2, . . . ,121.N, may receive a number Mrof received signals that exceeds the number Nrof receiving nodes. However, signals received on multiple antennas at a single node may be combined, such as may be performed for diversity combining, especially when the received signals are correlated. Thus, the number of spatial subchannels (e.g., the effective number Mrof received signals) may be less than the total number of antennas, Mr, employed by the receiver array depending on whether or not received signals are diversity combined prior to spatial processing.

One or more of the receiving nodes121.1,121.2, . . . ,121.Nrmay be designated as a destination node. For example, the local group120comprises nodes121.1,121.2, . . . ,121.Nr, which are communicatively coupled together via a WLAN, and wherein node121.1and node121.Nrcommunicate their received WWAN data to node121.2(which, in this case, is designated as the destination node) for further processing. In such aspects of the invention, peer-to-peer or multi-hop communications are a natural part of cooperative-MIMO processing.

The receiving nodes121.1,121.2, . . . ,121.Nrmay perform any of various combining techniques to provide MIMO subspace demultiplexing of the received signals, including EGC, MRC, Minimum Mean Squared Error Combining, other types of optimal combining, Successive Interference Cancellation, and other matrix-reduction/matrix diagonalization techniques. Some aspects may employ Cholesky triangularization (or other matrix decomposition approaches), overlapped subspace detection, maximum likelihood detection, and/or maximum a posteriori probability detection. Gaussian elimination, also known as row reduction, is a well-known algorithm for solving systems of linear equations. Using row operations to convert a matrix into reduced row echelon form is sometimes called Gauss-Jordan elimination. Some authors use the term Gaussian elimination to refer to the process until it has reached its upper triangular, or (non-reduced) row echelon form. For computational reasons, when solving systems of linear equations, it is sometimes preferable to halt row operations before the matrix is completely reduced.

This MIMO-based system may require additional energy for local communication between the transmitting nodes111.1,111.2, . . . ,111.Ntand the receiving nodes121.1,121.2, . . . ,121.Nr, but simultaneously introduces important gains for the long-haul (i.e., WWAN) communication. Based on the richness of the scattering environment, there is a critical distance between the transmitter and receiver above which MIMO transmission is more energy efficient than single-input, single output (SISO), e.g., purely multi-hop peer-to-peer transmission.

The following mathematical explanation shows why a rich scattering environment in the WWAN channel produces capacity gains for MIMO subspace processing.

The time-invariant WWAN channel is described by:
y=Hx+w,
where y is a vector of length Mrof baseband data symbols received by the receiver array having Mrantennas, x is a vector of length Mtof transmitted baseband data symbols from the transmitter array having Mtantennas, H is the Mr×MtWWAN channel matrix, and w is a vector of length Mrof white Gaussian noise.

In some aspects of the invention, nodes transmit random linear combinations of the packets they receive by virtue of a rich scattering environment. In a MIMO system, a rich scattering environment typically provides a full rank, well-conditioned channel matrix H, which indicates that the system may exploit the maximum number of spatial degrees of freedom (d=min(Mt, Mr)). In some aspects, the dimension of the subspace spanned by the system of linear equations (such as may be indicated by H) is the number of spatial degrees of freedom.

If the spatial subchannels are sufficiently uncorrelated, the probability that the receiver array will obtain linearly independent combinations (and therefore obtain innovative information) approaches 1. However, if a receiver obtains an insufficient number of linearly independent combinations of the transmitted data symbols, it may be unlikely that it can recover the original packets. For example, the receiver array may comprise fewer operable antennas than the number of spatial degrees of freedom employed by the transmitter. Specifically, the receiver may comprise fewer than the required minimum number of antennas (Mr<d), and/or some of the spatial subchannels may be correlated. In such cases, some aspects of the invention provide additional linear combinations until the receiver obtains a sufficient amount of information to perform spatial demultiplexing.

The capacity may be computed by decomposing the vector channel into a set of parallel independent scalar Gaussian sub-channels. From basic linear algebra, every linear transformation can be represented as a composition of three operations: a rotation operation, a scaling operation, and another rotation operation. In the notation of matrices, the matrix H has a singular value decomposition (SVD):
H=UΛV*,
where U and V are unitary matrices, and Λ is an Mr×Mtrectangular matrix whose diagonal elements are non-negative real numbers and whose off-diagonal elements are zero. The diagonal elements λ1≧λ2≧ . . . λM(min)are the ordered singular values of matrix H, where M(min)is the smaller of Mrand Mt.

Since HH*=UΛΛtU*, the squared values λi2are the eigenvalues of the matrix HH* and also H*H.

H can be rewritten as: H=Σi=1Mminλiuivi*, which is the sum of rank-one matrices λiuivi*. Thus, the rank of H is the sum of non-zero singular values λi. Each value λicorresponds to an eigenmode of the channel (i.e., an eigenmode corresponds to an eigen-channel, or subspace channel). Each non-zero eigenmode can support a data stream. Thus the MIMO channel can support k subspace channels, where k is the number of non-zero eigenvalues λi.

In the case where the SNR is high, and equal amounts of power are allocated to the non-zero eigenmodes, the channel capacity is expressed by:

C≈∑i=1k⁢⁢log⁡(1+P⁢⁢λi2k⁢⁢N0)≈k⁢⁢log⁢⁢SNR+∑i=1k⁢⁢log⁡(λi2k)⁢⁢bits⁢/⁢s⁢/⁢Hz
where P is the total transmit power of the transmitter array, N0is the noise power, so the signal-to-noise ratio is SNR=P/N0, and k is the number of non-zero eigenvalues λi, which is the number of spatial degrees of freedom per second per hertz. This is equal to the rank of matrix H. If H has full rank, the MIMO channel provides M(min)spatial degrees of freedom. However, the rank of H is just a crude measure of channel capacity. To better characterize channel capacity, one can consider the individual values of λi, particularly, the log of the values of λi2, which are summed in the above capacity equation.

In the above analysis, since the same amount of power is transmitted in each eigenmode, the channel H whose eigenvalues are all equal has the highest capacity. More generally, the less spread out the singular values, the greater the channel capacity is. This relates to the condition number of the matrix H, which is the ratio: (max λi/min λi). The matrix is said to be well-conditioned when the condition number is close to 1.

This means that in a MIMO system with a sufficient SNR, a well-conditioned channel matrix H facilitates communication. However, one of the problems with antenna arrays employed on portable transceivers, such as cellular handsets or other wireless mobile devices, is that the antennas cannot be sufficiently separated to guarantee uncorrelated spatial sub-channels, even in rich scattering environments. Therefore, aspects of the invention, when implemented in a WWAN, employ a WLAN to communicatively couple together multiple nodes and configure the nodes to cooperatively function as a MIMO system. Typically, the separation between the mobile nodes is sufficient to ensure uncorrelated spatial structure for MIMO processing.

FIG. 2is a block diagram that depicts a configuration of receiver nodes in relation to methods, devices, and systems employed for cooperative-MIMO processing in accordance with certain aspects of the invention. A local group120comprises a plurality Nrof wireless nodes121.1-121.N, communicatively coupled together by a WLAN (depicted as WLAN links105and107). At least one of the nodes121.1-121.N, (such as node121.2) is a destination for a transmitted signal in a WWAN. At least one of the nodes121.1-121.N, that is not a destination node assists the destination in receiving WWAN signals. Although the WWAN transmission source(s) is (are) not shown, any type of WWAN transmission source may be employed, such as a conventional antenna array configured for transmitting WWAN signals, a plurality of WWAN base stations or access points, a plurality of cooperative-MIMO transmitters, and/or any type of WWAN peer-to-peer or multi-hop network. Accordingly, some aspects of the invention may employ techniques and structure referred to as Coordinated Multi-Point (CoMP) transmission and/or reception.

In the diagram shown inFIG. 2, a plurality Mrof WWAN signals125.1-125.M, are received by the Nrnodes121.1-121.Nr. However, for simplicity of the following discussion, Mr=Nr. In a WWAN that employs cooperative MIMO, a WWAN source node (not shown) having a number of original data packets to transfer to the destination node121.2may combine the packets together into a “coded packet” that is transmitted in the WWAN. In one aspect of the invention, the rich scattering channel naturally “encodes” the packets. In another aspect of the invention, the source node (not shown) encodes the packets by employing channel pre-coding. In another aspect of the invention, the source node (not shown) employs an invertible transform that maps original data symbols to a pseudo-random constellation of code symbols.

The destination node121.2receives the coded packet and may then store the packet for eventual decoding. The destination node121.2will typically require a particular number of coded packets before it decodes the coded packets to extract the original data packets. The decoding process may involve, for example, the solution of a system of linear equations having a number of independent variables (i.e., the original packets) and a number of independent equations (such as represented by the coded packets and their associated codes (e.g., code matrix)). Before the destination node121.2can reliably solve for the original data packets, the number of degrees of freedom received must typically equal or exceed the number of original packets. However, in some special cases, such as when certain combining techniques are employed, when certain types of error correction are employed, or when the CI invertible transform is employed, the original data packets may be recovered without requiring the number of degrees of freedom to at least equal the number of independent variables. The following methods described herein may be adapted to these and other special cases.

In some aspects of the invention, the missing degrees of freedom may be defined as the number of unknown independent variables of a system of equations less the number of independent equations. In some implementations, each coded packet successfully received at a destination node (assuming the coded packet is linearly independent of previously received coded packets) may provide another equation for use in decoding (such as in MIMO subspace demultiplexing). Thus, each linearly independent combination (e.g., uncorrelated subspace) reduces the number of degrees of freedom needed for decoding by one.

In the cooperative-MIMO receiver120shown inFIG. 2, the nodes121.1-121.Nr. start collecting linear combinations of the transmitted messages, xi, i={1, . . . , k}. For example, a signal r1received by the first node121.1can be expressed by the following linear combination:

r1=∑i=1k⁢⁢α1,i⁢xi
where k typically equals the number of transmitted subspaces (e.g., spatial subchannels), Mt, from a transmitter array (not shown), and α1,i denotes the ithrandom channel coefficient corresponding to the first node121.1. The set of coefficients α1,ii={1, . . . , k} may be regarded as the ithsubspace code, or subspace code vector.

A signal rnrreceived by an nrthnode (e.g., node121.Nr) is expressed by:

rnr=∑i=1k⁢⁢αnr,i⁢xi
where the coefficient αnrthdenotes the ithrandom channel coefficient corresponding to the nrthnode121.Nr. The set of coefficients αnrii={1, . . . , k} is regarded as the nrthsubspace code, or subspace code vector.

If all Nrspatial subchannels are uncorrelated, then the set of receiving nodes121.1-121.Nrprovides a well-conditioned channel matrix H having rank Nrto the destination node121.2. In one aspect of the invention, each of the nodes121.1-121.N, calculates its own code vector by estimating its channel coefficients αi. In such aspects, the subspace code matrix determined at the destination node121.2may be the estimated channel matrix H. Channel estimation may be performed by measuring known transmitted symbols, such as known training symbols, pilot tones, and the like. In some aspects of the invention, nodes may estimate a channel's impulse response. These code vectors, along with the received signals riare coupled to the destination node, such as via a WLAN (e.g., WLAN links105and107).

As the destination node121.2collects code vectors, it builds up the dimension of the subspace spanned by the received code vectors. The dimension of the subspace spanned by the code vectors received at any receiving node, such as the destination node121.2, is also referred to as the “dimension of the node” or “rank of the node.” Similarly, the dimension of the subspace spanned by the code vectors corresponding to a transmission from a transmitting node is also referred to as the “dimension of the node” or “rank of the node.”

In some aspects of cooperative MIMO, one of the functions of a network controller (e.g., one of the nodes121.1-121.Nr) comprises selecting nodes in the local group120to cooperatively transmit and/or receive WWAN signals. Adaptive array processing may be coordinated by the network controller, such as to perform “antenna selection” in which the nodes121.1-121.Nrare selected based on their channel conditions to provide a sufficiently well-conditioned channel matrix H having sufficient rank to demultiplex (i.e., decode) the transmitted signals xi. For example, adaptive array processing may comprise adapting the selection of nodes121.1-121.Nruntil there are Nr≧Mtuncorrelated subchannels (i.e., a sufficient number of independent linear combinations of the transmitted signals xito permit the receiver to demultiplex the signals xi). Once there are Nr≧Mtreceived independent linear combinations, the destination node121.2can recover all the messages xisuccessfully.

In one aspect of the invention, only the destination node121.2decodes the received signals ri. For example, the destination node121.2may begin a decoding process by constructing an estimated channel matrix H. Since the component channel vectors may be determined by measuring known transmissions (e.g., pilots, training signals, other known transmitted signals, etc.), the cooperative-MIMO system may include relays that simply forward received signals (e.g., signals r1and rnr) to the destination node121.2.

In accordance with some aspects of the invention, node121.1relays its received WWAN signal r1to the destination node121.2via WLAN link105. A relay channel, such as the WLAN channel, may produce linear combinations of r1:

If the relay channel105comprises only one channel (i.e., J12=1), then the effective code vector values γimay equal the α1,ivalues scaled by a constant β.

The destination node121.2does not need to know the values of α and β. Rather, in some aspects of the invention, the node121.2directly estimates the effective channel values, γ. In some aspects of the invention, the node121.1relays the unequalized signal r1, which comprises unequalized known transmissions (e.g., pilots, known symbols, etc.) in addition to unequalized data portions. In some aspects, the node121.1does not need to estimate its WWAN channel coefficients. Upon receiving the unequalized known transmissions, the destination node121.1calculates an effective channel vector (i.e., γ values). This effective channel vector may then be used with other estimated channel vectors to construct the estimated cooperative-MIMO channel matrix, H, prior to decoding.

In some aspects, the node121.1estimates its WWAN channel and transmits those estimates in the WLAN link105. For example, the node121.1may employ its estimated WWAN channel coefficients as weights on pilot tones, or it may otherwise synthesize “distortions” on known transmission signals based on its WWAN channel estimates. When the relayed signal is received at the destination node121.2, any WLAN distortions are imparted onto the synthesized distortions. Then the node121.2calculates the aggregate (i.e., effective) channel vector.

The cooperative-MIMO protocol employed in aspects of the invention does not depend on the underlying communication model. The protocol can be applied to any environment where multiple messages are to be simultaneously demultiplexed over a bandwidth-limited environment.

FIG. 3is a flowchart illustrating a method for use in processing coded packets received at a destination node from a source node via multiple different WWAN paths in accordance with an aspect of the invention. The method comprises receiving coded packets at a receiver via multiple transmission paths301. The receiver also receives one or more code vectors302corresponding to the codes that encode the packets. The number of degrees of freedom required to decode the message are determined in step303. A plurality of receiver nodes are selected to provide the required number of degrees of freedom in step304.

As described above, the coded packets comprise random linear combinations of original packets that are input to at least one transmitting node (not shown). In the discussion above, this random coding may be achieved by transmitting the original packets in a scattering-rich channel. However, other techniques can be employed to achieve this random coding, including, but not limited to, employing coding at the transmitter (not shown), such as channel precoding based on estimates of a random channel. In some aspects, which are described below, the coding employed at the transmitter (not shown) may employ an invertible transform, such as a CI transform, which may include block transforms and/or sliding transforms.

The multiple transmission paths may comprise a plurality of WWAN subchannels, such as the WWAN subchannels described above. The multiple transmission paths may comprise non-WWAN transmission paths, such as WLAN paths105and107, and/or waveguide (i.e., wired) transmission paths. In some aspects of the invention, which are described below, the multiple transmission paths comprise parallel transmission paths employed by different networks (i.e., network channels).

The steps of receiving the coded packets301and receiving the code vectors302may be performed simultaneously, as the coded vectors may be transmitted with the coded packets. For example, in some aspects wherein the channel is employed for encoding the transmitted packets, pilot tones and/or other known transmitted signals may provide information about the channel, and, thus, the codes. In some aspects of the invention, the receiver may perform channel estimation to determine (i.e., receive) the code vectors.

The term, receiver, as used with reference toFIG. 3may include one or more of the receiving nodes121.1-121.Nrcommunicatively coupled together in the local group120. The receiver may comprise a destination node, such as node121.2and/or one or more intermediate nodes, such as nodes121.1and121.Nr. A receiver may denote the collection of receiving nodes121.1-121.Nr.

In some aspects of the invention, intermediate nodes (such as relay nodes) in the transmission path(s) may provide encode the packets. In accordance with some aspects, intermediate nodes may convey code vectors to the receiver. In other aspects, the intermediate nodes modify the coding of the transmissions they receive, as well as the corresponding code vectors. In such aspects, the intermediate nodes may provide linear coding to linearly coded transmissions they receive such that the aggregate coding seen by the destination node is also a linear combination of the original data packets. Intermediate nodes may convey channel estimates to other nodes in the transmission path, either directly (such as by transmitting those estimates as data), or indirectly, such as by imparting the channel estimate values on pilot signals and/or other known transmission signals used for channel estimation.

In patent application Ser. No. 10/145,854, to which the present application claims priority, and which is hereby incorporated by reference in its entirety, linear coding applied to a transmission encapsulates (i.e., masks) the network address in the packet header. In one aspect, this problem is remedied by appending a “message address” and header. Acknowledgements are returned upon receiving either or both the encapsulating message and the individual “network” packets. The message may be retransmitted until an acknowledgement is received from the destination node or after a predetermined number of retransmissions. In some aspects of the invention, the message address may be changed as the message propagates (e.g., hops) through the network. This is described in the '854 application with respect to each peer providing its own linear coding to the packets it receives before forwarding the packets.

As described above, in some aspects of the invention, either or both steps301and302may comprise transmitting an acknowledgement in response to receiving each coded combination of packets and/or upon decoding the original packets.

In step303, the receiver determines if there are a sufficient number of degrees of freedom to decode the encoded transmission. Specifically, the receiver determines if there are a sufficient number of linearly independent packets at the destination node to allow for recovering the original data packets. For example, if there are MTuncorrelated transmitted subspaces bearing MTtransmitted packets, then at least MR=MTuncorrelated WWAN receiving paths are selected to provide the necessary degrees of freedom to decode the transmission. Spatial subchannels that have different spatial structure (e.g., subspaces that have minimal eigenspace alignment) are said to be uncorrelated. Step303may comprise measuring the correlation between receiver nodes and then adapting the selection of WWAN-active nodes when receiver nodes become correlated.

One method for determining if receiver nodes are uncorrelated comprises determining if their received signals are linearly independent. For example, a Gaussian-Jordan elimination operation (or similar process) may be performed on a coefficient matrix associated with received packets. If a packet from a receiving node is not linearly independent with respect to other received packets, the packet may be discarded (or diversity combined with correlated packets). The network controller may proceed to look for new coded packets, such as by selecting another receiving node, thus building the dimension of the subspace spanned by the set of received coded packets.

In accordance with one aspect of the invention, a destination node in a cooperative-MIMO system determines that it has an insufficient number of degrees of freedom to decode a received coded message303. Then selecting an additional receiver node304comprises receiving from at least one additional receiver node at least one linearly independent combination of original packets. New coded packets may be added until the destination node can decode the coded message. In some aspects of the invention, selecting304may be performed by the destination node, at least one other receiver node functioning as a network controller, or by the WWAN.

In one aspect of the invention, if an acknowledgement is not returned to the transmitter after a predetermined amount of time, then the transmitter retransmits the message. If the interval between transmissions is at least equal to the channel coherence time, then the retransmitted messages provide additional degrees of freedom at the receiver. Thus, a step of retransmitting the message with a different linear combination of original data packets (not shown) may be performed instead of, or in addition to step304.

If a sufficient number of linearly independent packets have been received to decode the coded packets, then decoding305may be performed.

FIG. 4is a flowchart illustrating a method for use in processing coded packets received at a destination node from a plurality of intermediate nodes in accordance with an aspect of the invention. The method comprises collecting code vectors from at least one peer401. The collected code vectors may be arranged as a matrix402. A processing step403determines if a dimension of the matrix (e.g., the number of collected code vectors) is equal to a predetermined number (e.g., the number of degrees of freedom required to decode the packets). When the dimension of the matrix does not equal the predetermined number, the method calls for repeating413the collecting step401, the arranging step402, and the processing step403until the dimension of the matrix equals the predetermined number. Then the original data packets are decoded404using the collection of code vectors in the matrix.

As described above, information about the code vectors may be transmitted with the coded packets. For example, transmissions in a wireless network typically include known control information (such as pilot tones, training sequences, etc.) that can be used for channel estimation. Generating the code matrix402may comprise estimating a MIMO channel matrix H. Comparing the matrix dimension403may comprise determining the rank of H, determining the number of code vectors, or determining the number of linearly independent code vectors. In some aspects of the invention, step403may comprise performing an eigenvalue decomposition of the Mt×Mtcorrelation matrix R=HHH.

In a MIMO communication system, signals transmitted from Mttransmit sources interfere with each other at a receiver comprising the receiving nodes121.1-121.M. Thus, interference cancellation (such as matrix inversion and/or various forms of adaptive filtering) may be employed by one or more MIMO combiners to separate the signals. The received signal is expressed by:
y=Hx+n
where the received signal, y, is a vector with Mrterms {yi, i=1, . . . , Mr} corresponding to signals received by Mrreceiver elements (i.e., receiving nodes121.1-121.Nr); x represents the transmitted signal, which is a vector having Mtterms {xi, i=1, . . . , Mt} corresponding to signals transmitted by Mttransmitter elements (i.e., transmitting nodes111.1-111.Nr); H is an Mr×Mtchannel-response matrix that characterizes the complex gains (i.e., transfer function, or spatial gain distribution) from the Mttransmission elements to the Mrreceive elements; and n represents AWGN having zero mean and zero variance.

In the case where the channel is characterized by flat fading, such as when a narrowband signal is employed (e.g., a sub-carrier of a multi-carrier signal), the elements in matrix H are scalars. Thus, some aspects of the invention that provide for generating linear combinations of the data may provide for generating scalar coefficients. For example, pre-coding or spatial multiplexing based on the matrix H performed on the transmit side of a link may comprise generating linear combinations of signals in which the signal values are multiplied by scalar coefficients. Simultaneously transmitting multiple signals in a flat-fading environment can produce linear combinations in which the signals are scaled by scalar coefficients. Spatial demultiplexing performed on the receive side of the link may employ the scalar matrix H values, and, thus, comprise generating linear combinations of the received signals.

In one aspect of the invention, the channel-response matrix H may be diagonalized by performing an eigenvalue decomposition of the Mt×Mtcorrelation matrix R, where R=HHH. Eigenvalue decomposition is expressed by:
R=EDEHR
where E is an Mt×Mtunitary matrix with columns corresponding to the eigenvectors eiof R, and D is an Mt×Mtdiagonal matrix wherein the diagonal elements are eigenvalues λiof R. The diagonal elements of D indicate the channel gain for each of the independent MIMO channels. Alternatively, other eigenvalue-decomposition approaches, such as singular value decomposition, may be employed.

One process for diagonalizing the MIMO channel response is initiated by multiplying a data vector d with the unitary matrix E to produce the transmitted vector x: x=Es. This requires the transmitter to have some information corresponding to the channel-response matrix H, or related information thereof. The received vector y is then multiplied with EHHHto provide an estimate of data vector s, which is expressed by:
ŝ=EHHHy=EHHHHEs+EHHHn=Ds+{circumflex over (n)}
where {circumflex over (n)} is AWGN having a mean vector of 0 and a covariance matrix of Λn=σ2D.

The data vector s is transformed by an effective channel response represented by the diagonal matrix D. Thus, there are Ns, non-interfering subchannels, wherein each subchannel i has a power gain of λi2and a noise power of σ2λi. Subchannels with higher SNR are able to support higher information flows. Thus, some aspects of the invention provide for bit loading. Bit loading assigns bits to subchannels based on subchannel quality, which means that it allows more bits to be transmitted in higher-quality (i.e., higher-capacity) subchannels and fewer bits to be transmitted in lower-quality subchannels.

In the case where MIMO subspace processing is performed on a multicarrier (e.g., OFDM) signal or some other wideband signal that is spectrally decomposed into narrowband components, eigenmode decomposition may be performed for each frequency bin fn.

If multicarrier spreading codes are employed (e.g., orthogonal DFT, or CI codes), the channel-response matrix H can cause inter-symbol interference between spread data symbols, even in a SISO arrangement. Accordingly, the eigenmode decomposition technique described above is applicable to multicarrier spreading and despreading. In one aspect of the invention, eigenmode decomposition may be applied across two or more dimensions (e.g., both spatial and frequency dimensions). In another embodiment of the invention, eigenmode decomposition may be applied across a single dimension (e.g., spatial or frequency dimensions). For example, multicarrier spreading codes (for example, orthogonal codes for data multiplexing in a given multiple-access channel) may be generated and processed via eigenmode decomposition.

Any of various water-filling or water-pouring schemes may be employed to optimally distribute the total transmission power over the available transmission channels, such as to maximize spectral efficiency. For example, water-filling can be used to adapt individual node transmission powers such that channels with higher SNRs are provided with correspondingly greater portions of the total transmit power. A transmission channel, as defined herein, may include a spatial sub-space channel, a space-frequency channel, or some other channel defined by a set of orthogonalizing properties. Similarly, water filling may be used at a physically connected (i.e., wired) antenna array. The transmit power allocated to a particular transmission channel may be determined by some predetermined channel-quality measurement, such as SNR, SINR, BER, packet error rate, frame error rate, probability of error, etc. However, different or additional criteria may be employed with respect to power allocation, including, but not limited to, wireless terminal battery life, load balancing, spatial reuse, power-control instructions, and near-far interference.

In conventional water filling, power allocation is performed such that the total transmission power PTis some predetermined constant:

The aggregate spectral efficiency for the NsNftransmission channels is expressed by:

The modulation and channel coding for each transmission channel may be adapted with respect to the corresponding SNR. Alternatively, transmission channels may be grouped with respect to their data-carrying capability. Thus, groups of transmission channels may share common modulation/coding characteristics. Furthermore, transmission channels having particular SNRs may be used for particular communication needs. For example, voice communications may be allocated to channels having low SNRs, and thus, low data-carrying capabilities. In some cases, transmission channels that fail to achieve a predetermined threshold SNR may be eliminated. In one embodiment of the invention, water filling is employed such that the total transmission power is distributed over a plurality of selected transmission channels such that the received SNR is approximately equal for all of the selected channels.

An aspect of the invention may employ reliability assessment for determining required processing and virtual-array size (e.g., the number of active nodes functioning as WWAN receiver elements). Received bits or symbols that have low reliability may require more processing. Bits or symbols with high reliability may be processed with fewer elements (e.g., nodes) or provided with lower processing requirements. More information typically needs to be combined for data streams having less reliability and less information may need to be combined for data streams having more reliability. Also, nodes with good channel quality may share more information via the WLAN than nodes with poor channel quality. Optimization algorithms, such as water-filling algorithms may be employed in the reliability domain.

FIG. 5is a flow diagram depicting a method of distributing data across a plurality of subchannels in a cooperative network, such as a communication network wherein at least a portion of the network employs multiple inputs and multiple outputs associated with a link between a server (i.e., a source node) and a client (i.e., a destination node). Aspects of the invention associated withFIG. 5, as well as with the other figures of the disclosure, are described in the '107 application and the '829 application (both of which are incorporated by reference in their entireties, and to which this disclosure claims priority). For example, in some aspects of the invention, disclosures in '107 and '829 relating to adaptive array processing, bit loading, soft handoff, antenna switching, antenna selection, and simultaneously employing multiple network channels (including channels from different WANs) are pertinent to methods and devices associated withFIG. 5.

Referring now toFIG. 5, a client-server system comprises a server coupled to a client through at least one communication link. Portions of the link may include at least one WWAN channel. A plurality of network channels are established501for transmitting a data block (e.g., a file, one or more data packets, etc.) from the server to the client. In one aspect of the invention, the plurality of network channels may comprise a plurality of spatial subchannels in a cooperative-MIMO system, such as depicted inFIG. 1. In another aspect of the invention, the network channels may comprise multiple WANs, such as depicted in FIG. 1J of the '107 application.

When step501comprises establishing a plurality of spatial subchannels in a WWAN, a number of transmitting antennas Mtand a number of receiving antennas Mrmay be determined. In a cooperative-MIMO system, a plurality of nodes may be employed at the transmitting side and/or at the receiving side in a wireless network. Step501may further comprise selecting which antennas are employed. Such antenna selection may be part of adaptive-array (e.g., smart antenna) processing performed by either or both the client and the server, and/or by one or more intermediate nodes in the link. In some aspects, antenna selection may comprise node selection in a cooperative-MIMO system.

Multiple sub-flows are established502, wherein each sub-flow comprises a portion of the data to be transmitted. In one aspect of the invention, the sub-flows are established by determining amounts of data (e.g., number of packets) to be allocated to each of a plurality of channels and distributing the allocated amounts to the channels. Each channel may be provided with a predetermined number of packets to transmit in a particular unit time.

In one aspect, the channel quality of each subspace may be determined (such as by employing any of the eigenmode processes described above), followed by a bit-loading process. Various adaptive antenna array techniques may be employed. The basic idea is to use channel information to adaptively vary the transmission scheme. This adaptation may comprise varying the number of spatial subchannels and the sub-flow rate of each subchannel in a precoded spatial multiplexing system. In some aspects, a water-filling process, such as described above, may be employed for bit loading. For example, as a higher-quality subchannel is allocated more power, this increases the subchannel's SNR, which allows larger modulation constellations, higher coding rates, etc. to be employed. A higher-quality subchannel may also have fewer retransmissions. In some aspects of the invention, step502may be performed concurrently with step501, or it may follow step501.

Since subspace encoding employed in aspects of the invention produces an aggregate signal in which the original data portions (i.e., components) are encapsulated, if the original data portions comprise packets, then header information in those original packets, such as addresses, sequence numbers, and the like are similarly masked. Step503assigns an identifier to the aggregate signal. For example, the identifier may comprise a WWAN identifier (e.g., WWAN-access information) that distinguishes WWAN messages from each other. The WWAN-access information typically identifies a particular destination node to which the message is addressed. The WWAN-access information may comprise channel-access information for a WWAN channel to which the destination node is assigned. Similarly, the WWAN identifier may comprise a network address. The '854 application discloses a message address appended to a message encoded to encapsulate an aggregation of linearly encoded packets in which the network addresses of the individual component packets are hidden by the encapsulation. A receiving node may acknowledge receipt of the encapsulating message and/or receipt of the component (i.e., original) packets once they have been decoded.

In step504, linear combinations of the component packets are generated. These linear combinations are distributed across the previously determined sub-flows based on the amounts of data (e.g., number of packets) allocated to each sub-flow in step502. When the linear combinations are transmitted, they are provided with the identifier provided in step503.

In one aspect of the invention, step504comprises sub-space coding that employs an invertible transform. For example, in the case of a linear transform from Rnto Rmgiven by y=Ax, where A is an m×n matrix, the transformation is invertible if Ax=y has a unique solution. If m=n, the system Ax=y has a unique solution if the rank of A equals n.

In one aspect of the invention, parallel transmissions (i.e., simultaneous, same-band transmissions) of the original data packets in a rich scattering environment produce linear combinations of the original data packets. Each “encoded” packet received at a receiving antenna comprises a random superposition of the original packets, wherein the randomness is provided by the random scattering channel. In accordance with one aspect of the invention, step504comprises coordinating a plurality of transmitting nodes to cooperatively transmit the original data packets. Step504may comprise antenna selection and/or node selection at the transmitting side, such as to produce an m×m channel matrix H with rank m in which the m subchannels are sufficiently decorrelated from each other. In accordance with another aspect of the invention, step504comprises coordinating a plurality of receiving nodes to receive the transmitted signals. Step504may comprise antenna selection and/or node selection at the receiving side, such as to produce an n×n channel matrix H with rank n in which the n subchannels are sufficiently decorrelated from each other.

In another aspect of the invention, pre-coding applied to the original data on the transmitting side produces linear combinations of the original data packets. Each “encoded” packet transmitted by a transmitting antenna comprises a random superposition of the original packets, wherein the randomness is provided by estimations of the random scattering channel. Aspects of the invention comprise either or both coordinating a plurality of transmitting nodes to cooperatively transmit the linear combinations of original packets and coordinating a plurality of receiving nodes to cooperatively receive the transmitted signals.

The linear combinations can be generated at random or deterministically involving all or any subset of the original packets. The coding strategy may affect the decoding complexity at the receiver. A particularly efficient coding method is to form linear combinations of packets using a CI transform, which is explained below.

In order to decode the received coded packets, the receiver needs a predetermined number of linearly independent combinations of the original packets, denoted as degrees of freedom. The effects of losing coded packets can be mitigated by providing for redundant transmissions across the subspaces. Similarly, a failure to return an acknowledgement for the original packets can naturally cause retransmission of the coded packets until the receiver can decode the encoded packets and acknowledge receipt of the original packets.

FIG. 6is a flow diagram depicting a method of distributing data across a plurality of subchannels in a cooperative network, such as a network in which a plurality of transmitting nodes, a plurality of intermediate nodes, and/or a plurality of receiving nodes cooperatively function together to perform subspace processing.

Step601comprises determining a plurality of linear combinations of original packets to transmit from at least one source node to at least one destination node. For example, packets in a transmit queue may partitioned into sets, each set comprising a plurality of packets. In one aspect of the invention, the number of packets in each set equals the number of transmitted subchannels. In another aspect of the invention, responsive to feedback from one or more receiving nodes, the number of packets in each set equals the number of received subchannels. In one aspect, the linear combinations comprise coding provided to the original packets by one or more transmitting nodes. In another aspect, step601comprises which packets are transmitted simultaneously into a multipath channel, and the channel produces random linear combinations of the transmitted packets.

Step602comprises selecting a plurality of nodes to cooperatively perform subspace processing. In one aspect of the invention, a plurality of transmitting nodes is selected by a source node to transmit the linear combinations. For example, each transmitting node may transmit a different linear combination. In some aspects, each transmitting node may generate a different linear combination of original packets. In another aspect of the invention, a plurality of intermediate nodes is selected to cooperatively perform subspace processing. For example, intermediate nodes may combine signals they receive and then transmit those linear combinations. Intermediate nodes may share signals with each other before forwarding their received signals. In another aspect of the invention, a plurality of receiving nodes is selected to cooperatively perform subspace processing. For example, a destination node may select one or more receiving nodes to provide a requisite number of independent linear combinations so the destination node can decode the received signals to recover the original packets.

Step603comprises transmitting the linear combinations. In one aspect of the invention, step603comprises employing multiple transmission paths for transmitting original packets and/or coded packets, wherein the multiple transmission paths provide for mixing the transmitted signals. In one aspect, intermediate nodes that have multiple simultaneous inputs may combine the input signals. In another aspect of the invention, step603may employ transmission paths from a plurality of networks. In such aspects, transmitting603may employ similar bit-loading and/or water-filling techniques employed for subspaces, as described above.

Since many aspects of the invention employ data communication protocols that typically employ some type of acknowledgement mechanism, step603may be repeated until the destination node acknowledges receipt of the original packets. Thus, in some aspects, the destination node will ordinarily not be able to return acknowledgements for the original packets until after it decodes its received signals. Thus, the ordinary retransmission process may generate new linear combinations604until the destination node can return an acknowledgement. For example, new linear combinations will be generated if the retransmission is delayed by an amount equal to or greater than the channel coherence time. Similarly, new linear combinations will typically be generated if the transmission channel is changed in other ways, such as if a different set of transmitting nodes, intermediate nodes, and/or receiving nodes is (are) employed. Alternatively, new linear combinations can be generated if new precoding values are selected.

FIG. 7is a block diagram depicting a cooperative system of nodes configured to simultaneously employ a plurality of different WWAN connections, such as to deliver a data stream or data file to (or from) a destination (source) node. In one aspect of the invention, a local group710of nodes701-706employs connections to a plurality of different WWANs716,717, and719to transfer data to or from one of the nodes701-706. In accordance with some aspects of the invention, the destination (or source node), i.e., one of the nodes701-706may simultaneously employ a plurality of WWAN user channels, including at least one of the user channels allocated to at least one of the other nodes701-706, to transmit and/or receive data.

In some aspects of the invention, one or more nodes depicted in the figures may comprise an edge of a content delivery network. For example, an edge server may comprise one or more of the WWAN terminals716,717, and719. In some aspects, one or more of the nodes701-706may be configured to perform edge-server functions.

In some aspects of the invention, a source or destination node may employ one or WANs to which it does not have direct access, but that one of the cooperating nodes701-706in the group710may access. For example, node701is shown with a communication to an IEEE 802.16 access-point terminal716in an IEEE 802.16 network, node102is shown with access capabilities to a 3G-cellular terminal719, and node703has connectivity to an IEEE 802.11 access point717. Connectivity between the nodes701-706, such as via WLAN links709, enables any of the nodes701-706in the group710to access any of the plurality of WAN (802.16, 3G, and 802.11) services.

A WAN-access controller (not shown), which may take the form of software residing on a physical device, such as one or more nodes701-706, may be provided for managing access to the WAN services, including partitioning information flows across multiple WAN services, user channels within those WAN services, and/or subspace channels. Such access may be performed with respect to a combination of technical rules and business rules. For example, WAN access is typically managed using technical rules, such as network load balancing. For example, network load balancing may comprise balancing traffic across two or more WAN links. This capability can balance network sessions, such as Web, email, streaming media, etc., over multiple connections in order to spread out the amount of bandwidth used by each node701-706, thus increasing the total amount of bandwidth available.

In some aspects of the invention, WAN access can also be influenced by business rules, such as employing cost/service ratios when determining whether and how to different WAN services. For example, the WAN-access controller (not shown) can anticipate the economic cost of particular WAN services to the user, as well as user communication needs, when assigning WAN access to individual nodes701-706. A destination or source node701-706may provide the WAN-access controller (not shown) with a cost tolerance, which can be updated relative to the type of communication link desired. For example, high-priority communication needs (such as particular voice communications or bidding on an online auction) may include permissions to access more expensive WAN services in order to ensure better reliability.

The overall goal of WAN access may be to achieve optimal connectivity with minimum cost. Accordingly, WAN-access algorithms may include optimization techniques, including stochastic search algorithms (like multi-objective genetic algorithms). Multi-objective optimization are well known in the art, such as described in E. Zitzler and L. Thiele, “Multi objective evolutionary algorithms: A comparative case study and the strength pareto approach,” IEEE Tran. on Evol. Comput., vol. 3, no. 4, November 1999, pp. 257-271 and J. D. Schaffer, “Multiple objective optimization with vector evaluated genetic algorithms,” Proceedings of 1st International Conference on Genetic Algorithms, 1991, pp. 93-100, both of which are incorporated by reference.

Some aspects of the invention may employ the multiple WANs depicted inFIG. 7to perform subspace processing, as described throughout this disclosure. As shown, a first node (e.g., one of the nodes701-706) may wish to exchange information with a second node, such as a server (not shown) via a plurality of WAN services. As is known, WAN access may comprise multiple different routes or paths that data packets can traverse between the first and second nodes. In addition, some of the different routes may involve different network technologies.

In one aspect, a first path between the first and second nodes may comprise a WiFi-based network (i.e., based on the IEEE 802.11 family of wireless networking standards), such as depicted by the path to the 802.11 access point717. A second path may comprise a 4G cellular network, such as a Long term Evolution (LTE) based cellular network or an 802.16 WiMax network, depicted by the path to the 802.16 access-point terminal716. To use either of these different WAN paths the first node701-706comprises (or has access to) appropriate hardware and software to be able to communicate according to the corresponding standards. Many modern communication devices (e.g., cell phones, smart phones, handheld communicators, computers or servers with communication functionality, network gateways, wireless access points, audio/video devices with communication functionality, appliances with communication functionality, wearable communication devices, etc.) include network adapters for multiple different network technologies. Nodes701-706configured to cooperatively perform subspace processing in a MIMO system can also enable the first node (i.e., one of the nodes701-706) to access WAN services that it would otherwise not be able to access.

Some aspects of the invention employ multiple different network technologies to support a single data transfer operation (or a single connection) between communication nodes. The use of multiple different network technologies associated with multiple different communication paths to support a single data transfer operation or other function may be referred to as “heterogeneous networking” Thus, cooperative subspace processing, such as subspace coding and/or subspace decoding, may employ heterogeneous networking.

FIG. 8is a block diagram of a plurality M of transmitting nodes806.1-806.M configured in accordance with aspects of the invention. A data source800is coupled to a sub-space coder, such as a MIMO processor802. The nodes806.1-806.M are in close proximity to each other and are communicatively coupled together, such as by a WLAN899. The MIMO processor802provides sub-space coding to the data. Sub-space coding may comprise spreading codes and/or channel codes, such as block channel codes, which spreads each data symbol over multiple code symbols (i.e., coded data symbols). The resulting coded data is then grouped by the MIMO processor802and distributed to the plurality of nodes806.1-806.M, which may comprise wireless terminals (denoted as WTs) configured to communicate in a WWAN.

In one aspect of the invention, each node806.1-806.M comprises a WLAN interface807.1-807.M configured to receive and/or transmit coded data from/to the MIMO processor802. The MIMO processor802may comprise one or more of the nodes806.1-806.M. For example, the MIMO processor802may reside in one of the nodes806.1-806.M that is a source node.

In one aspect of the invention, each of the nodes806.1-806.M is configured to transmit signals into a WWAN, and, thus, each comprises a modulator808.1-808.M and a WWAN interface809.1-809.M. Modulation may include channel coding. In one aspect of the invention, modulation808.1-808.M comprises employs WWAN channel weights, such as may be used for sub-space processing. The channel weights may be provided by the MIMO processor802. Thus, in some aspects of the invention, the MIMO processor802couples coded data symbols and sub-space codes to the each of the nodes806.1-806.M.

FIG. 9Aillustrates software components residing on a non-transitory computer-readable memory950. A subspace coding source-code segment951is configured to generate a plurality of sub-space coefficients to encode a plurality of original data packets. The subspace coding source-code segment951is configured to accept as input at least one of a set of information inputs, including data signals (e.g., original data packets), training signals (e.g., known symbols), WWAN channel estimates, and WWAN-control information.

The subspace coding source-code segment951is configured to provide as output at least one of a set of signals, including coefficients for subspace coding and subspace-encoded data. In one aspect of the invention, a distribution source code segment952is provided for distributing the coefficients for subspace coding and the subspace-encoded data received from source-code segment951to a plurality of nodes. The distribution source code segment952may optionally function to couple at least one of a set of information inputs to the source-code segment951, including data packets from other nodes.

FIG. 9Billustrates software components of a receiver residing on a non-transient computer-readable memory960. A subspace code source-code segment961is configured to acquire subspace code coefficients from a plurality of cooperating receiving nodes. These coefficients are subsequently used to decode received subspace-coded data. In one aspect of the invention, the source-code segment961may estimate subspace coefficients from measurements of the propagation channel. For example, pilot tones and/or other control information in a received signal may convey code vectors that encode the original packets. For an antenna array comprising a plurality of wireless terminal nodes, the subspace coefficients may comprise space-frequency codes (e.g., subcarrier/antenna array weight vectors) and/or space-time codes (e.g., weighted Rake taps). The subspace code source-code segment961is configured to accept at least one of a set of inputs, including signals that convey code vectors (including received signals in which known symbol values are scaled by subspace code coefficients), coded data, channel estimates, and WWAN-control information.

The subspace code source-code segment961is configured to provide as output at least one of a set of information signals, including subspace coefficients, encoded data packets (such as to be distributed to one or more nodes), combined data packets (e.g., data packets received from a plurality of nodes and then combined, wherein the data received may comprise encoded data), and estimates of original data packets after decoding. A distribution source code segment962is provided for distributing at least one of a set of signals, including subspace coefficients (used for subspace coding and/or decoding), encoded data packets, combined data packets, and estimates of original data packets following decoding. The distribution source code segment1962may optionally function to couple at least one of a set of information inputs to the source-code segment961, including data packets received by other WTs, training signals (including code vectors) received by other nodes, channel estimates (either of both locally estimated and received from other nodes), WWAN-control information, code vectors (including decoding values) received from at least one other node, and decoded data received from at least one other node. Accordingly, the source code segment1962may select which WTs to receive information from to cooperatively perform subspace demultiplexing.

Since software implementations of the invention may reside on one or more computer-readable memories, the term computer-readable memory is meant to include more than one memory residing on more than one node.

Aspects of the invention described herein may employ subspace processing methods (including software implementations) and apparatus implementations employing cooperative antenna arrays in a WWAN. While in some aspects of the invention, nodes in a cooperating group share the same WWAN access, other aspects of the invention provide for nodes with access to different WWANs. In some aspects, one or more nodes may have access to a plurality of WWANs and WWAN services. In some cases, one or more nodes may not be able to directly access any WWAN.

FIG. 10is a network diagram of a cooperative subspace processing system in accordance with aspects of the invention. For example, some aspects described with reference toFIG. 1are depicted inFIG. 10. A method for transmitting data from at least one source node, such as node131.2, to at least one destination node, such as node141.2, may comprise employing one or more coding nodes, such as nodes131.1,131.Nt,141.1, and141.Nr. In one aspect of the invention, coding nodes on the transmitting side (e.g., nodes131.1and131.Nt) are employed. In another aspect, coding nodes on the receiving side (e.g., nodes141.1and141.Nr) are employed. In yet another aspect, coding nodes at both sides (e.g., a transmitting group130and a receiving group140) of the link are employed (e.g., nodes131.1,131.Nt,141.1, and141.Nr). The aforementioned aspects, as well as other aspects of the invention, may employ intermediate nodes (not shown) in the communication link.

In one aspect depicted inFIG. 10, the source node131.2is communicatively coupled to a plurality Ntof transmitting nodes131.1and131.Nt. For example, the nodes131.1-131.Ntmay comprise a local group130communicatively coupled together via WLAN links151-153. A plurality of data packets at the source node131.2are coupled to one or more of the other nodes (e.g., nodes131.1and131.Nt) in the group130for transmission to a receiving group140that includes the destination node. For example, nodes131.1and131.Ntmay transmit signals into a scattering-rich WWAN channel (such as depicted by the channel99inFIG. 1). An equivalent network path model for the scattering-rich channel is depicted by network links117.1,117.N−1,119.1, and119.N−1.

To simplify the discussion of this aspect of the invention, Ntand Nrare equal (denoted by the value N). Another simplification that characterizes this particular aspect is that there are no network paths directly from the source node131.2to the receiving group140, and there are no network paths from the transmitting group130that go directly to the destination node141.2. In other aspects of the invention, the communication scheme may include network paths directly from the source node131.2to the receiving group140and/or network paths from the transmitting group130directly to the destination node141.2.

The destination node141.2may be communicatively coupled to other nodes (e.g., nodes141.1and141.Nr) in the receiving group140. For example, a WLAN (depicted by WLAN links155and157) may couple the destination node141.2to other receiving nodes141.1and141.Nr, such as to assist the destination node141.2in subspace de-multiplexing (i.e., decoding) linear combinations of the signals transmitted from the transmitting group130.

As depicted inFIG. 10, the receiving node141.1receives a linear combination of transmitted signals from network paths117.1and119.1originating at nodes131.1and131.Nt, respectively. The receiving node141.N, receives a linear combination of transmitted signals from network paths117.N−1 and119.N−1 transmitted by nodes131.1and131.Nt, respectively. For example, when the transmissions reside in the same band and time interval, the resulting aggregate signal (i.e., superposition) comprises a linear combination of the transmitted signals, typically referred to as interfering signals. In a MIMO system, subspace demultiplexing (i.e., subspace decoding) may be employed to separate the interfering signals at the receiver. This requires the linear combinations of signals received at nodes141.1and141.Nrto be linearly independent (i.e., uncorrelated). Depending on the type of signaling protocol, the linear combinations may comprise scalar and/or complex coefficients.

In one aspect of the invention, the randomness of a scattering-rich WWAN channel encodes the transmitted signal such that the coefficients of the linear combinations are random. In another aspect of the invention, subspace multiplexing is performed by the transmitting group130, which may comprise precoding and/or other subspace coding. When the subspace multiplexing coefficients are based on channel measurements, as they typically are when performing precoding, the coefficients of the linear combination are randomly chosen by virtue of the randomness of the channel. In some aspects of the invention, the transmitting group130may employ an invertible transform to spread data packets across multiple subcarriers and/or subspaces. Such invertible transforms may include CI transforms, as will be discussed below. A CI transform maps a set of data points with discrete values into a pseudo-random (i.e., statistically random) set of coded data points.

In one aspect of the invention, the coding nodes131.1,131.Nt,141.1, and/or141.Nrare selected to build up the dimension of the subspace spanned by the received coded signals. For example, in a multipath channel, the transmitting nodes131.1and131.Ntmay be selected to ensure a set of uncorrelated subchannels (e.g., spatially separated nodes131.1and131.Ntare selected, or the nodes131.1and131.Ntmay be provided with different antenna polarizations or directivity). The receiving nodes141.1and141.Nrmay be selected to provide a sufficient number (e.g., at least N) of uncorrelated subchannels. In other aspects of the invention, coding nodes may include intermediate nodes (not shown) in the transmission path. The intermediate nodes may be selected to provide sufficient degrees of freedom at the receiving group140.

In one aspect of the invention, a network comprises one or more source nodes, one or more destination nodes, and one or more coding nodes. The source nodes are configured to transmit a plurality of original data packets. The coding nodes are configured to output linear combinations of the original data packets wherein coefficients of the linear combinations are randomly chosen. The coding nodes are selected to provide a sufficient number of degrees of freedom to enable the one or more destination nodes to decode the linear combinations.

In one aspect of the invention, a vector of subspace coefficients accompanies the linear combinations. For example, pilot tones (and/or other control data) may convey channel information used to encode the data packets. Precoding coefficients may be distributed to the transmitting nodes (e.g., nodes131.1and131.Nt) along with coded data. Channel estimates used for decoding may be conveyed by the receiving nodes141.1and141.Nrto the destination node141.2along with received linear combinations.

In some aspects of the invention, signals are relayed through the network. The channel of each relay link (i.e., hop) introduces its own channel distortions equally to the data payload and any pilots and/or other signals used to convey the vector of coefficients. For example, the naturally occurring linear combinations produced on each relay link are applied to the data payload and the pilot signals in an OFDM signal. The values of the received pilot tones in an OFDM signal may constitute the vector of coefficients. In other types of signals, overhead signals, such as known sequences used for synchronization and/or known values used for other control purposes, sometimes reside in packet headers. Measurements of these control values at a receiver may constitute the vector of coefficients. At each relay node, the linear combinations applied to the vector of coefficients are the same as the linear combinations applied to the data.

FIG. 11Ais a flow diagram illustrating a method for performing cooperative subspace multiplexing in accordance with some aspects of the invention. A plurality of transmitting nodes is selected to receive a plurality of subspace-coded components1101. A data set (e.g., a data file) is separated into a plurality N of original components1102, where N equals a number of required degrees of freedom to decode the subspace-coded components. The number N may be determined based on the number of transmitting nodes to which the subspace-coded components will be distributed. An optional step (not shown) may comprise determining a number of the coded components to be distributed to each transmitting node (such as may be determined by each node's storage capacity, processing capability, and/or its number of uncorrelated transmitting antennas). The subspace-coded components are produced1103by generating at least N random linear combination of the original components. The coded components and any associated code vectors are distributed to the selected transmitting nodes1104such that at least one of the selected transmitting nodes has a number of coded components that is less than the number of required degrees of freedom. The selected transmitting nodes store the coded components and any associated code vectors before transmitting this data. In some aspects of the invention, the selected transmitting nodes comprise edge nodes of a content delivery network.

In one aspect of the invention, selecting the transmitting nodes1101comprises selecting one or more nodes nearby a source node in a peer-to-peer network. If a selected node can transmit a unique linear combination of the original data components (relative to the other selected nodes), then that node builds up the dimension of the subspace spanned by the transmitted coded signals until the dimension of the subspace equals the number of the original components. Therefore, in some aspects of the invention, if there are N original components (e.g., step1102) to be transmitted simultaneously, then at least N coded components comprising unique linear combinations of the original components are generated (e.g., step1103), such that the transmission subspace is provided with a dimension of at least N. If the dimension of the transmission subspace is greater than the dimension of the subspace spanned by the coded signals (e.g., in a WWAN, if the number of transmitting antennas is greater than the number of original data components), then there is at least one unused dimension in the transmission subspace. This can be regarded as redundancy in the transmission, and, in a wireless network, it may serve to increase gain.

In another aspect of the invention, selecting the transmitting nodes1101comprises selecting one or more nodes nearby a destination node in a peer-to-peer network. If each selected node receives a unique linear combination of the original data components and then retransmits its received data to the destination node, then each selected node builds up the dimension of the subspace spanned by the coded signals received at the destination node until the dimension of the subspace equals the number of the original components. In a wireless network, any additional linear combinations of the original data components may be used to increase gain.

In other aspects of the invention, selecting the transmitting nodes1101comprises selecting one or more intermediate nodes of the communication path(s) in a peer-to-peer network.

In aspects of the invention, the source node, the transmitting nodes, and/or the channel may encode the original components1103. For example, the source node and/or the transmitting nodes may provide subspace coding, such as precoding, to the original data components. Nodes in between the source node and the destination node may provide subspace coding, such as by combining received signals and then retransmitting the combined signals. Signals that are transmitted in a wireless channel are typically received by more than one receiver. Thus, if the channel is characterized by rich scattering, then the linear combinations received by different receivers are more likely to be independent. Thus, selected transmitting nodes nearby the destination node employed for receiving signals may forward the received coded signals to the destination node for decoding.

FIG. 11Bis a flow diagram illustrating a method for performing cooperative subspace multiplexing in accordance with some aspects of the invention. The method comprises receiving at a node in a peer to peer network, at least one of a set of subspace-coded components1111comprising a linear combination of original data components characterized by a number of degrees of freedom required to decode the set of subspace-coded components. The method further comprises receiving at said node, at least one code vector associated with the at least one subspace-coded component1112; and storing at said node, the subspace coded component(s) and the code vector(s)1113to provide a stored set, the stored set having a number of the subspace coded component(s) that is less than the required number degrees of freedom. The method may optionally comprise transmitting the subspace-coded component(s) and the code vector(s) from the node to a destination node1114, which collects a sufficient number of the subspace-coded components and code vectors to decode the coded components. For example, the destination node may collect the code vectors, which are then used to construct a code matrix. When the rank of the matrix equals the number of original components, then matrix operations employing the collection of code vectors can decode the subspace-coded components. In some aspects of the invention, nodes that store the coded components and the code vectors comprise edge servers in a content delivery network.

In one aspect of the invention, a Cooperative-MIMO system configured to operate in a WWAN efficiently stores data in a distributed manner. For example, multiple components (i.e., original components) of a data set (e.g., a data file) may be transmitted in parallel (i.e., at the same time in the same channel). Each antenna of a receiver receives a single coded piece, which comprises a linear combination of the transmitted components. In a cooperative-MIMO receiver, a plurality of nodes may be configured to cooperatively process received signals. A node with more than one antenna may receive more than one coded piece. For example, if the antennas (specifically, their channels) are not correlated, then each antenna receives a unique linear combinations of the original components. Signals that are correlated may simply be combined, which may provide certain diversity benefits.

With reference toFIG. 11A, in one aspect of the invention, the number of original components in step1102is related to the number of spatial subchannels. For example, the number of original components may be less than or equal to the number of uncorrelated spatial subchannels, the number of transmit antennas, and/or the number of receive antennas. In some aspects, higher-quality subchannels (e.g., those associated with greater eigenvalues) may carry more data, such as by employing higher modulation schemes. Thus, multiple coded components may be allocated to a single subchannel.

In one aspect of the invention, the number of wireless nodes selected to store components (e.g., step1101) may depend on a number of factors, including (but not limited to) the total number of transmit antennas, the number of antennas on each node, the quality of subspace channels, network topology, the number of nodes near the destination node, etc.

In some aspects of the invention, step1103may comprise determining a random combination of original components to store at a particular node. In one aspect, the physical wireless channel provides the required statistical randomness for the coding, since temporal and spatial variations of the channel are random. Channel reciprocity (i.e., radio waves propagating in both directions of a radio link between a pair of transceivers experience the same multipath channel distortions at the same time and frequency), may be exploited by the transceivers at opposite ends of a wireless link to agree on a random code, which depends on their common channel. For example, each transceiver may estimate the common channel from known control signals (such as pilot tones in an OFDM signal) received from the other transceiver. Thus, in some aspects, the code vector can be determined from channel estimation.

In one aspect of the invention, there is no coordination between the selected nodes to decide which nodes store which components of the file. Rather, in a wireless network, each node's channel(s) may determine what combination(s) of components it receives.

In some aspects of the invention, a central controller is not required to maintain a state of the contents of all the nodes and differentiate between the nodes. A selected node may not know exactly what the other selected nodes have stored. For example, each node can estimate its own channel, from which it derives information about the linear combination(s) that it receives. However, if the node's channel is not correlated with any other node's channel, the node cannot directly estimate channels employed by the other nodes. Thus, the node does not know what linear combinations other nodes receive unless that information is shared by the other nodes.

In some aspects, the selected nodes do not coordinate for storing components. Rather, a destination node or a WLAN controller accesses the selected nodes to download the linear combinations and channel estimates (e.g., subspace weights) until a sufficient amount of information is obtained to decode the coded components. The destination node completes its download once it has enough information to recover the original components of the data set.

FIG. 11Cis a diagram depicting processing methods and processing devices in accordance with aspects of the invention. A file is partitioned into a plurality of original components in processing block1121. Each original component may comprise one or more data packets. In processing block1122, each of a plurality of nodes in a peer-to-peer network is assigned to receive one or more of the original components and/or subspace-coded versions of the components. In processing block1123, subspace-coded components and the associated subspace code vectors are generated. The components and, optionally, their subspace code vectors are distributed to the assigned nodes (from block1122)1124.

In processing block1122, the nodes assigned to receive the components may be selected based on their locations in the network. In one aspect of the invention, nodes that are nearby a source node are selected as transmitting nodes. In another aspect, nodes nearby the destination node are selected as receiving nodes. Since these so-called receiving nodes convey their received signals to the destination node, they may be referred to as transmitting nodes. In other aspects, intermediate nodes are selected to the components.

In block1122, the number of components assigned to each peer may be related to a combination of various factors, including (but not limited to) the bandwidth to the peer (which may include subchannel quality and the number of subschannels), the bandwidth from the peer to the destination node, and the peer's storage and/or processing capability.

In processing block1123, code vectors may be generated from channel measurements. For example, pilot tones and/or other known signals accompanying a data transmission may be used to estimate the channel. When coding comprises the effects of scattering, then the code vector may comprise channel estimates. When precoding is performed, and the precoding is based on channel measurements, then a receiver may employ channel estimates to estimate the precoding values. In some aspects, handshaking between two peers may be employed to determine code vectors. For example, such handshaking is commonly used to ensure key match by two parties employing the randomness in the channel for key generation. In other aspects, a transmitter may employ a code matrix based on an invertible transform, such as a CI transform.

In block1123, each coded component rnrreceived at an nrthnode may be expressed by

rnr=∑i=1k⁢⁢αnr,i⁢xi
where the coefficient αnr,idenotes the ithrandom coefficient corresponding to the nrthassigned node, and xiis the ithoriginal component. The set of coefficients αnr,i, i={1, . . . , k} is regarded as the nrthsubspace code, or subspace code vector.

In some aspects of the invention, block1123precedes block1124. In one aspect, signals distributed to an assigned node comprise transmitted original components that are linearly coded by the communication channel. For example, the source node may comprise an antenna array for transmitting the original components to the assigned nodes. However, in order to achieve this linear coding and ensure the codes are uncorrelated, the transmitters and receivers are selected to provide uncorrelated subchannels.

In another aspect of the invention, block1124may precede block1123. The coefficients αnr,imay comprise subspace antenna array weights, such as precoding weights, distributed to the assigned nodes. The assigned nodes may then apply the weights to the original components and/or previously coded components to generate coded components. In one aspect of the invention, the subspace code vector and the coded components are generated (1123) by scattering in the channel after the original components (and/or previously coded components) are distributed (1124) to the assigned nodes.

In one aspect of the invention, the coded components and/or original components are stored at their assigned nodes, which do not transmit the data until directed to do so. The recipient(s) of the transmitted data may comprise other coding nodes and/or the destination node.

Processing blocks1131-1133depict a method for decoding the file that was encoded and distributed to a plurality of nodes, such as in the manner described with respect to processing blocks1121-1124. In processing block1131, code vectors are collected from at least one peer. The coded components may also be collected in this step1131, or in a subsequent step1132and/or1133. In processing block1132, a determination is made if a sufficient number of linearly independent code vectors have been collected to decode the coded components. If a sufficient number of code vectors have been collected, then decoding is performed (i.e., processing block1133). If not, then more code vectors may be selected (e.g., control returns to block1131).

In accordance with one aspect of the invention, processing block1132may provide for assembling the collected code vectors as a matrix. The matrix may comprise a ((Σn=1nrkn)×N matrix wherein knis the number of coded components stored at an nthpeer, nris the number of peers, and N is the number of original components.

In one aspect, a determination is made regarding whether the dimension Σn=1nrknis sufficient to decode the coded components collected from the peers. For example, if (Σn=1nrkn)=N, then it may be possible to decode the N equations (e.g., the coded components) having N unknowns (i.e., the original components). Processing block1132may be configured to calculate the rank of the matrix. For example, if the rank=N, then the matrix may be diagonalized.

Processing block1132may be configured to determine how well-conditioned the matrix is. For example, the eigenmodes may be evaluated, which may comprise calculating the corresponding eigenvalues. If the matrix is sufficiently well-conditioned, then decoding1133is performed. In some aspects of the invention, a requirement for what constitutes well-conditioned may depend on the SNR of the received signals. Thus, block1132may provide for measuring SNR (or some similar measure of link quality), determining a threshold of what constitutes a well-conditioned matrix (e.g., threshold eigenvalues), and then determining if the matrix is sufficiently well-conditioned to decode the subspace-coded components. If the matrix is not sufficiently well-conditioned, block1132may discard one or more highly correlated code vectors (and the associated coded component(s), if relevant), or combine at least some of the correlated code vectors. Then control passes back to block1131, whereby one or more additional code vector(s) are collected.

In some aspects of the invention, block1131comprises adaptive array processing to dynamically select (and/or de-select) transmitting and/or receiving antennas, such as to increase the rank and/or improve the conditioning of the channel matrix, H. Such array processing may comprise changing the number N of simultaneously transmitted original components. In cooperative-MIMO processing, adaptive array processing may comprise dynamically selecting and/or de-selecting peers (transmitting nodes and/or receiving nodes) employed to perform cooperative subspace processing. Adaptive array processing may include changing the antenna array weights at the transmitting and/or receiving array, such as to change the rank and/or improve the subspace channels. When the processing of block1131is repeated, block1131may provide for selecting code vectors (and, thus, coded components) from new nodes.

In some aspects of the invention, upon failure of the destination node (or its cooperative receiving nodes) to acknowledge transmitted packets, the packets are retransmitted. In response to the requirement to retransmit the data, the source node may adapt the subspace processing provided to the transmitted signals (such as by providing adaptive array processing). If a wireless channel is employed in the link, and the delay between transmission and retransmission is equal to or greater than the wireless channel's coherence time, then new linear combinations of the original components are generated. Thus, block1131may collect new code vectors from the same nodes, which are then processed with previously received code vectors in block1132.

FIG. 12is a diagram depicting processing methods and processing devices in accordance with aspects of the invention. In a network, a method of transmitting data from a source node to a destination node comprises forming linear combinations of original packets from a source node to produce subspace-coded packets (processing block1201), and delivering the subspace-coded packets to the destination node over one or more network paths (processing block1202). The destination node transmits feedback (such as acknowledgements) back to the source node (processing block1203). Based on the responsiveness of the destination node (which includes a failure to respond), the source node causes new linear combinations of the original packets to be formed (processing block1204) to generate new subspace-coded packets, and delivers the new subspace-coded packets to the destination node (processing block1205).

In one aspect of the invention, a cooperative-MIMO system is employed whereby cooperating nodes are configured to perform subspace processing, such as subspace multiplexing (e.g., on the transmitting side of a link) and/or subspace demultiplexing (e.g., on the receiving side of a link). The processing block1201may perform array processing, such as selecting antennas of a fixed array and/or nodes of a cooperative-MIMO array to transmit signals in a wireless channel. The block1201may select subspace antenna weights for encoding the transmitted signals.

In some aspects of the invention, parallel transmissions in a multipath channel produce random combinations of the transmitted signals. In one aspect, precoding applied to the transmitted signals may be selected such that propagation in the multipath channel provides at least some degree of decoding. In such aspects, the channel (and, thus, processing block1202) does not encode the transmitted signals.

In one aspect of the invention, block1203comprises providing acknowledgements from the destination node to the source node upon receipt of a container packet (i.e., coded packet, which effectively encapsulates the original packets) and/or upon decoding the encapsulated packets (i.e., the original packets), such as described in the '854 application, which is incorporated by reference in its entirety. In another aspect of the invention corresponding to block1203, feedback from the destination node may comprise control signals (e.g., pilot tones), which are employed by the source node for channel estimation, and, subsequently, encoding the original packets. In accordance with some aspects of the disclosure, adaptive array processing performed by at least the source node relies on feedback from the destination node, such as to select an appropriate subspace dimension and/or optimize the subspace channels.

With reference to block1204, adaptive array processing at the transmit side of the link may reselect the transmitting nodes, add new nodes, and/or adapt precoding and/or antenna array weights. This generates new subspace codes, thus providing new linear combinations of the original packets. In some aspects, block1204may comprise performing adaptive array processing at the receive side of the link. At the receive side, cooperating receiver nodes may be reselected and/or added. In some aspects, the antenna array weights and/or other subspace coding weights at the receive side may be adapted. Thus, adaptive array processing in a cooperative network may comprise adapting the degrees of freedom spanned by the subspace signals.

In one aspect of the invention, the receiver may convey to the transmitter how many degrees of freedom it has received and/or is capable of receiving. This technique can be used to select the number of transmitting antennas (Mt) and/or receiving antennas (Mr) in a cooperative-MIMO system. Similarly, communicating information about degrees of freedom in either or both directions in a link can be used to select transmitting and/or receiving nodes in a cooperative-MIMO system. In some aspects of the invention, the source node may respond to feedback (including the absence thereof) from the destination node by transmitting new linear combinations of the original packets.

As described with respect toFIG. 7, the network links117.1,117.N−1,119.1, and119.N−1 depicted inFIG. 10may comprise two or more different WANs.

FIG. 13is a diagram depicting processing methods in accordance with aspects of the invention. In one aspect of the invention, a communication device comprises at least a first WAN interface configured for communicating in a first WAN, and has access to a second WAN interface configured for communicating in a second WAN, the first WAN being different than the second WAN. A network controller (such as a processor) manages data transfer between the communication device and a destination node using multiple different network routes, such as the first WAN and the second WAN. The network controller may be configured to perform the steps shown inFIG. 13.

In accordance with one aspect of the invention, the network controller produces a plurality of original packets1301to be transferred to the destination node. A plurality of subspace-coded packets is generated1302from the original packets by employing subspace coding to linearly combine the original data packets. The coded packets are distributed across the plurality of different WANs to the destination node1303. Optionally, additional subspace coding may be provided to the coded packets while they are en-route to the destination node1304.

In one aspect of the invention, the number of original packets is selected to be less than or equal to the total dimension of the subspace between the source and destination nodes. For example, the total dimension of the subspace may equal the sum of subspaces in each of the different WANs. The total dimension of the subspace may be used to select subspace codes. In some aspects, the dimensions of subspaces in one or more of the different networks may be used to select subspace codes. For example, in one aspect, first subspace code(s) corresponding to a first WAN may encode a first set of packets, and second subspace code(s) corresponding to a second WAN may encode a second set of packets. Furthermore, a universal code(s) may be employed for encoding values transmitted over both first and second WANs. In such an aspect, one or more receivers at the destination would perform WWAN-specific subspace decoding and universal subspace decoding.

In some aspects of the invention, step1302comprises generating subspace codes corresponding with the subspace coded packets. In step1303, the subspace codes may be distributed with the coded packets. In some aspects of the invention, step1302and/or1303comprises selecting at least one set of transmitting nodes, coding nodes, and/or receiving nodes to cooperatively perform subspace coding. Such selection(s) may depend on the dimension of the codes (and the coded packets). In some aspects of the invention, the selection(s) may be based on adaptive array processing algorithms, which may adapt either or both the number of nodes and the subspace codes based on the degrees of freedom at the receiver.

In some aspects of the invention, if packets are lost or the bit-error rate is high, it may be desirable to decrease the transmission rate, such as by removing one or more low-quality subchannels, adapting the coding to increase the processing gain, or otherwise introducing more redundancy in the transmitted information.

In one aspect of the invention, subspace codes are generated at the destination node. In another aspect of the invention, subspace codes are generated by a plurality of transmitting nodes communicatively coupled to the source node. In another aspect of the invention, subspace codes are generated by transmitting a plurality of known signals from a transmitting array through a scattering-rich channel to a receiving array. In another aspect of the invention, a MIMO processor coupled to a receiving array is configured to produce subspace codes. Subspace codes may be produced and/or modified by intermediate nodes in a link between the source node and the destination node.

Since subspace multiplexing and subspace demultiplexing are coordinated between the source and destination node (respectively), different networks may be employed simultaneously without requiring those networks' servers to coordinate data transfers with each other.

FIG. 14is a diagram depicting processing methods in accordance with aspects of the invention. In one aspect of the invention, a method for transmitting a file between a server and a client through one or more network paths comprises generating a plurality of linearly coded packets from a plurality of original packets1401, and performing cooperative subspace processing to increase a dimension of a subspace spanned by the linearly coded packets1402. The linearly coded packets are sent to the client1403, which, upon reception of at least one of the coded packets, provides feedback to the server1404. Based on the feedback, new linearly coded packets may be transmitted to the client1405.

In one aspect of the invention, the linearly coded packets are generated1401as linear combinations of the original packets. If a scattering channel is employed (directly or indirectly) for generating coefficients of the linear combinations, then such linear combinations may be random. In other aspects, a deterministic process may be employed for generating the coefficients. The deterministic process may employ an invertible transform characterized by a mapping of original data packets into a set of pseudo-random coded packets.

In processing block1402, cooperative subspace processing is performed by a plurality of nodes to build the dimension of the subspace spanned by the linearly coded packets. For example, the plurality of nodes may cooperate to produce parallel (i.e., simultaneously transmitted) transmissions of the coded packets. In one aspect, the plurality of nodes is selected to receive a plurality of coded packets (e.g., precoded packets) from the server (e.g., a source node) and then simultaneously transmit the coded packets to the client (e.g., a destination node). In another aspect, the plurality of nodes is selected to receive the original packets and then encode the original packets to produce the coded packets before coordinating a simultaneous transmission of the coded packets to the client. In another aspect, the plurality of nodes comprises multiple transmitting nodes selected to transmit original packets and/or coded packets into a multipath channel, which linearly encodes the transmitted packets. In another aspect, the plurality of nodes comprises one or more intermediate nodes between the server and the client, the intermediate node(s) configured to receive and retransmit the coded packets. Intermediate nodes may optionally provide additional linear coding to the packets they receive. In other aspects, the plurality of nodes comprises one or more receiving nodes communicatively coupled to the client and configured to cooperatively receive transmitted coded packets and forward the received packets to the client. In such aspects, the receiving node(s) are selected to build the dimension of the subspace of signals received by the client. In some aspects of the invention, processing blocks1401and1402may be combined.

In some aspects of the invention, the processing block1403comprises sending the linearly coded packets to the client over a plurality of different networks. In these aspects, packets to be transmitted are distributed over the different network paths. Subspace multiplexing (e.g., coding) may comprise interleaving the coded packets over the different networks, and subspace de-multiplexing (e.g., decoding) may comprise collecting the coded packets received from the different networks, followed by a combining process in which the received coded packets are combined and decoded to retrieve the original packets.

In some aspects of the invention, interleaving the linearly coded packets to the client over a plurality of different networks may comprise network load balancing (e.g., bit loading) the multiple channels employed in the link, such as distributing more packets to channels able to support higher bandwidth and fewer packets to channels that support relatively lower bandwidth. In some aspects of the invention, these channels may comprise channels on different networks (e.g., WANs), such as channels employed by block1403.

In block1404, upon reception of any of the coded packets at the client, the client may provide feedback. For example, the client may transmit an acknowledgement to the server upon retrieving each of the original packets after decoding the received coded packets. However, as described in the '879 application (which is incorporated by reference in its entirety), the coded packets encapsulate the original packets, thus concealing header information in the original packets. Thus, the coded packets may comprise their own headers and employ different protocols than those used with the original packets.

Different acknowledgement protocols may be employed depending on the message layer (i.e., original packet, and coded (or encapsulating) packet). For example, TCP may be employed for the original packet, whereas the acknowledgement mechanism employed with the coded packets may be similar to mechanisms employed to coordinate adaptive antenna array processing. As mentioned in the '107 application (which is incorporated by reference in its entirety), latency can severely impede TCP. Thus, in links with high latency, such as satellite links, it is common to automatically transmit TCP acknowledgements whether packets are received or not, and then utilize a different type of transmission control protocol that tolerates latency. In aspects of the invention, the receiver, or even the transmitter, may automatically send acknowledgements for each transmission, thus, effectively short-circuiting the TCP mechanism. Then any of the adaptive array mechanisms employed in MIMO may be used as a substitute control protocol.

In processing block1405, based upon the feedback, the server (and/or any intermediate nodes) may transmit at least one new linearly coded packet to the client. For example, absence of an acknowledgement after a predetermined amount of time may trigger retransmission of the coded packet(s).

In some aspects of the invention, network load balancing may be employed for distributing data loads across different network channels. For example, when data is to be interleaved over multiple channels (e.g., subchannels and/or network channels, including network channels in different networks), bit loading may be employed for loading more data into higher-bandwidth channels and less data into lower-bandwidth channels. In related discussions, more error correction (such as lower code rates) may be employed in lower-quality channels, which essentially reduces the amount of information transmitted in those channels. With respect to subchannels, more data may be loaded on subchannels with higher eigenvalues, such as discussed above. Various techniques for distributing data over multiple channels with respect to the effective channel bandwidth are described throughout the '107 application, which is incorporated by reference in its entirety. Similarly, reliability assessments of all the individual channels (which may be based on BER, SNR, and/or other qualitative measures of a channel) may provide a basis for allocating processing resources, such as the number of nodes employed to perform subspace processing.

FIG. 15Ais a diagram depicting processing methods in accordance with aspects of the invention. In one aspect of the invention, a method is provided to manage data interleaving in a communication network that simultaneously employs multiple network channels to transmit data from a source node to a destination node. As used herein, a network channel may comprise a user channel separated from other user channels by at least one of the following multiple-access schemes: frequency division multiple access (e.g., OFDMA), time division multiple access (TDMA), and code division multiple access (e.g., CDMA). For example, a first CDMA channel may be encoded with a first Walsh code and a second CDMA channel may be encoded with a second Walsh code, wherein the first and second Walsh codes are orthogonal to each other. In the '107 application, which is incorporated by reference in its entirety, the user channels are also referred to as physical channels. If the first and second Walsh codes are orthogonal, then the first user channel is a network channel, and the second user channel is a different network channel. In one aspect of the invention, the multiple network channels may comprise a plurality of different networks, such as depicted inFIG. 7.

In one aspect of the invention, multiple network channels are established1501to provide a connection from a single source node to each of at least one destination node. At least one real-time property of each network channel is monitored1502. Subspace processing is performed to interleave data across the network channels1503. Based on variations of the monitored property (or properties), network load balancing (e.g., bit loading, or interleaving) may be adjusted1504.

As described above with respect toFIG. 7, processing block1501may employ multiple network technologies (e.g., different WANs) to simultaneously transmit data from a source node to a destination node. In some aspects, the processing block1501interleaves data across different non-interfering user channels.

In processing block1502, at least one channel quality parameter is measured and/or determined for each of the network channels. For example, BER, probability of error, SNR, and/or any other quality metric may be determined.

In processing block1503, subspace processing may comprise subspace coding to spread data across the non-interfering network channels. Optionally, one or more of the network channels may comprise a plurality of subspaces. In one aspect, the subspace-coded data is distributed across the network channels such that the destination node needs to receive coded data from a plurality of the network channels in order to have a sufficient number of degrees of freedom to decode the received data. In another aspect of the invention, subspace processing1503comprises de-multiplexing the received subspace-coded data.

In some aspects of the invention, subspace processing1503comprises employing a plurality of transmitting nodes to cooperatively perform subspace processing, such as described above. In such aspects, selecting the cooperating transmit nodes may effectively build the dimension of the subspace of the transmitted signal. In some aspects of the invention, subspace processing1503comprises employing a plurality of receiving nodes to cooperatively perform subspace processing, such as described above. In such aspects, selecting the cooperating receiving nodes may effectively build the dimension of the subspace of the received signal. In some aspects of the invention, a local group of cooperating nodes may provide a source and/or destination node with access to network interfaces, and, thus, network channels that it would otherwise not have.

In processing block1504, multiple network channels may be employed for transmitting data from a single source node to a single destination node. For example, in one aspect of the invention, a source node (e.g., one of the nodes701-706shown inFIG. 7) may employ at least one other node to simultaneously provide multiple network channels that reside on different networks (e.g., networks716,717, and719) for communicating a data stream to a destination node. Similarly, one of the nodes701-706may employ the multiple network channels for receiving a data stream from a remote source. In some aspects of the invention, the servers in the networks716,717, and719are not required to coordinate with each other to manage data flows on the network channels to/from any of the nodes701-706. Rather, each node (e.g., any of the nodes701-706) having a WAN interface manages its own connection(s) with its respective network(s) (e.g., networks716,717, and719). The source/destination node amongst the nodes701-706, or one of the nodes701-706configured to function as a network controller manages data flow across the network channels. Such management may comprise selecting and/or adapting data interleaving (e.g., bit loading, network load balancing) across the network channels. Channels that can support higher data rates may be allocated more coded data than channels that support only lower data rates.

FIG. 15Bis a diagram depicting processing methods in accordance with aspects of the invention. In one aspect of the invention, a method is provided to manage quality of service in a node, such as a mobile wireless device. In the mobile wireless device, an application service connection is established1511between an application processor and a remote device through a wireless communication network. A transceiver monitors at least one real-time property1512of a radio frequency access link between the mobile wireless device and the wireless communication network. The transceiver provides the application processor with updated values of the monitored at least one real time property1513of the radio frequency access link. The application processor adjusts packet data generation in response to the updated values1514to manage a quality of service property of the application service connection.

In one aspect of the invention, establishing the connection1511comprises employing a plurality of nodes to establish a plurality of network channels and/or subchannels. The real-time property that is monitored1512may comprise a channel estimate, a data rate, a BER, an SNR, and/or any other link-quality metric.

In some aspects of the invention, processing block1514may comprise adaptive array processing, which is sometimes performed in coordination with monitoring link quality1512. In some aspects of the invention, processing block1514may comprise performing network load balancing (e.g., bit loading across network channels) when multiple network channels are employed, and/or bit loading across subchannels when multiple subchannels are employed.

In some aspects of the invention, block1514may comprise adjusting subspace coding. If the node is a receiving node (e.g., a destination node), the receiver may adjust the rate over each network channel by the way it responds to receiving packets. For example, sending acknowledgements (or failing to send acknowledgements) can change the data rates. This can also affect the coding and redundancy of the data transmissions.

FIG. 16is a block diagram depicting communications between a WWAN node1619and a cooperating group of nodes1610(such as a plurality of wireless terminal nodes1601-1603) employing a plurality of different, yet complementary, code spaces c1, c2, and c3. In one aspect of the invention, the term complementary means that the coded transmissions corresponding to the code spaces c1, c2, and c3can sum to produce at least one predetermined WWAN coded data sequence. This may be a weighted sum (i.e., a random linear combination), such as due to the given channel99conditions. A predetermined WWAN coded data sequence may employ a code that would ordinarily (in view of the prior art) be employed in whole. That is, it would not ordinarily be partitioned into sub-codes to be transmitted by different transmitters or received by different receivers.

In one aspect of the invention, the code spaces c1, c2, and c3correspond to direct-sequence codes, such as may be used to provide for spreading and/or multiple access. A superposition of signals transmitted across the code spaces c1, c2, and c3may provide at least one predetermined WWAN coded data sequence received by at least one WWAN node1619. Similarly, a superposition of signals received by nodes1601-1603and mapped onto the code spaces c1, c2, and c3may provide at least one predetermined WWAN coded data sequence that would ordinarily (in view of the prior art) be intended for a single node1601-1603. Some aspects of the invention may provide for channel corrections (e.g., pre-distortion and/or receiver-side channel compensation) by either or both the cooperating group1610and the WWAN node1619. Accordingly, the code spaces c1, c2, and c3may be adapted to account for channel conditions.

In another aspect of the invention, the code spaces cl, c2, and c3may correspond to direct-sequence codes having predetermined spectral characteristics. It is well known that different time-domain data sequences may be characterized by different spectral distributions. Some aspects of the invention may provide for selecting complementary codes cl, c2, and c3having predetermined spectral characteristics with respect to WWAN channel conditions affecting the links between the nodes1601-1603and the WWAN node1619. Thus, in some aspects, the codes c1, c2, and c3may be selected according to the same criteria employed for selecting OFDM subcarriers.

A direct-sequence code may comprise a pseudo random noise code, such as is known in the art. Pseudo-random noise is a deterministic set of values or signals that satisfies one or more tests for statistical randomness. A direct sequence code may comprise an orthogonal code, such as a Walsh code, such as is known in the art. Direct sequence is a type of signaling in which each data symbol is modulated (or otherwise impressed) onto (or represented by) a sequence of code symbols. Thus, information about each data symbol resides on a plurality of coded data symbols. In this respect, each data symbol is “spread” across multiple code symbols, and the resulting coded data symbols are transmitted in sequence. Furthermore, each coded data symbol may contain information about a plurality of data symbols.

A receiver that receives the sequence of coded data symbols may decode the received signals if it knows the direct-sequence code and if a sufficient number of the coded data symbols are received. In one aspect of the invention, if Mtcode spaces c1, c2, . . . , cMtcomprise Mtlinear combinations of up to Mtdata symbols, then the coded transmissions provide a sufficient number of degrees of freedom for decoding the data symbols. In another aspect, the code spaces c1, c2, . . . , cMtmay indicate codes produced by an invertible transform. In some instances, if the number of coded data symbols is less than the number of data symbols, decoding produces a certain amount of inter-symbol interference that can be corrected.

The distribution of the inter-symbol interference to each estimated data symbol can depend on the type of coding employed. In some aspects, of the invention, CI codes may be employed, such as described in U.S. Patent Application Publication No. 20040086027, which is incorporated by reference in its entirety. The '107 application incorporates by reference U.S. Patent Application Publication Nos. 20040086027 and 20030147655, which are hereby incorporated by reference in their entireties. CI codes may comprise either or both block-type codes and sliding transform codes. Block codes often uniformly distribute inter-symbol interference due to each data symbol across all the other data symbols encoded by the block code, whereas sliding transform codes may non-uniformly distribute inter-symbol interference of each data symbol across the other symbols in the sliding transform window.

In one aspect of the invention, transmitting a sequence of symbols into a multipath channel produces a sliding transform of those symbols. A random channel produces a random sliding transform. For example, in a multipath channel, some paths are longer (and, thus, introduce more delay) than other paths. Inter-symbol interference occurs when earlier-transmitted symbols arrive at a receiver at the same time that later-transmitted symbols are received. In some aspects of the invention, the length of this sliding transform window equals the delay spread of the channel.

In some aspects, the coding window may be the number of resolvable multipath delays. A time-domain receiver typically employs a Rake receiver having a number of taps. For example, the number of Rake taps in an efficient receiver may equal the number of resolvable delays. The coding window may be increased by employing a larger number of transmitters and/or receivers. Increasing the coding window may comprise increasing the number of transmit and/or receive directions. In some aspects, the angle of the transmitted and/or received signals may be increased. In multipath environments, paths received at higher angles relative to line-of-sight (i.e., zero incidence) between a transmitter and receiver often have greater delays than paths received closer to the line-of-sight.

In another aspect of the invention, a sliding window transform is synthesized by a transmitter, such as by deliberately time-offsetting signals transmitted from antennas of an array. In such aspects, one or more of a node's transmissions may be provided with time-varying complex weights (e.g., amplitudes and/or phases), such as described in S. A. Zekavat, C. R. Nassar and S. Shattil, “Combined Directionality and Transmit Diversity via Smart Antenna Spatial Sweeping,” proceedings of 38thAnnual Allerton Conference on Communication, Control, and Computing, University of Illinois in Urbana-Champaign, pp. 203-211, Urbana-Champaign, Ill., USA, October 2000, S. A. Zekavat, C. R. Nassar and S. Shattil, “Smart antenna spatial sweeping for combined directionality and transmit diversity,”Journal of Communications and Networks(JCN),Special Issue on Adaptive Antennas for Wireless Communications, Vol. 2, No. 4, pp. 325-330, December 2000, and S. A. Zekavat, C. R. Nassar and S. Shattil, “Merging multi-carrier CDMA and oscillating-beam smart antenna arrays: Exploiting directionality, transmit diversity and frequency diversity,”IEEE Transactions on Communications, Vol. 52, No. 1, pp. 110-119, January 2004, which are incorporated by reference herein.

In some aspects of the invention, a Rake receiver performs sliding-transform processing. For example, a kthdirect-sequence transmission signal sk(t) that includes N code symbols {bk[n]}n=1Nis given by:

ak⁡(t)=∑i=0G-1⁢⁢Cik⁢gTc⁡(t-iTc),
Cikis the Direct Sequence spreading signal, G represents processing gain, Tcis the chip duration, Tbis the bit duration, and gTc(t), gTb(t), and gτ(t) represent the chip, bit, and transmitted pulse shapes, respectively.

A plurality M of nodes linked together by a WLAN comprises elements of an M-element antenna array capable of receiving K transmission channels. In a frequency-selective channel, the received signal at the array is:

r⁡(t)=∑k=1K⁢⁢∑l=0Lk-1⁢⁢∑n=0N-1⁢⁢αlk⁢V→⁡(ϑlk)⁢bk⁡[n]⁢g⁡(t-τlk-nTb)⁢cos⁡(2⁢⁢π⁢⁢fc⁢t+φlk)+υ⁡(t)
where {right arrow over (V)}(θ) is an array-response vector, K is the number of received transmission channels, Lkis the number of distinct fading paths corresponding to the kthuser, αikis the fade amplitude associated with path l and user k, φlk=U[0,2π] represents the associated fade phase, τlkis the path time-delay (which occurs below a predetermined duration threshold Tmax), and θlkdenotes angle of arrival. The array response vector {right arrow over (V)}(θ) is expressed by:
{right arrow over (V)}(θ)=[1e−2πdlcos θ/λ. . . e−2πdM-1cos θ/λ]
where dmis the antenna separation, and λ is the wavelength corresponding to carrier frequency fc.

For a jthuser's lthpath, the nthbit at the beamformer output is given by:
zlj[n]=WH(θlj)∫+(n−1)Tb+nTbr(t)cos(2πfct+φij)aj(t−τlj−(n−1)Tb)dt
where W(θlk) is the weighting vector of the beamforming system. zlk[n] can be expressed by four components:
zlk[n]=Sij[n]+ISIij[n]+IXIij[n]+νij[n]
where S is the desired signal, ISI is inter-symbol interference, IXI is cross interference (i.e., multiple-access interference), and v is the AWGN contribution. These components can be expressed as follows:

Maximal ratio combining produces an output:

zj⁡[n]=∑l=0L-1⁢⁢αlj⁢zlj⁡[n]
which can be processed by a decision processor. In this case, the BER is given by:
Pe=∫0∞Q(2ro)f(ro|ro)dro
whererois the mean value of the instantaneous SINR, ro, and Q( ) represents the complementary error function.

It should be appreciated that the nodes may be adapted to perform either or both time-domain (e.g., Rake) or frequency-domain processing as part of a receiver operation. Signals received by a plurality of nodes may be combined with respect to any combining technique, including EGC, MRC, Minimum Mean Squared Error Combining, other types of optimal combining, Successive Interference Cancellation, and other matrix-reduction/matrix diagonalization techniques. Successive Interference Cancellation may be particularly useful for decoding signals encoded with a sliding transform.

FIG. 17is a diagram depicting processing methods in accordance with aspects of the invention. In one aspect of the invention, a method is provided in which a transmitting node determines a linear combination of original packets to transmit1701, transmits the linear combination of packets across a network using a sliding window protocol1702, and receives an acknowledgement when a receiving node receives the linear combination of packets1703.

In one aspect, the process of transmitting1702and/or a process of receiving the transmitted linear combination (not shown) comprises at least one of the transmitting node and the receiving node enlisting at least one cooperating node to increase the dimension of the subspace spanned by the linear combination. For example, the at least one cooperating node may increase the rank of the coding matrix generated at the receiver and/or may improve the conditioning of the matrix.

In one aspect of the invention, the receiving node retrieves coding coefficients (i.e., at least one code vector) from the linear combination of packets1704. The receiver may produce a code matrix from the coding coefficients. The coding coefficients (which may be appended to a code matrix) are employed in a decoding process for decoding the received linear combinations1705. Since the coding comprises a sliding transform, decoding1705may comprise successive interference cancellation, or some other matrix-reduction process.

In accordance with still another aspect of the systems, circuits, and techniques described herein, a communication device comprises a first network interface unit configured for communication in a first network, a second network interface unit configured for communication in a second network that is different from the first network, and at least one processor to manage data transfer between the communication device and a destination node using multiple different channels.

In one aspect of the invention, a method depicted inFIG. 18is provided in which the at least one processor employs a plurality of cooperating nodes to generate first coded packets and/or second coded packets. In one aspect of the invention, first coded packets are generated by linearly combining original data packets1801. Coding1801may employ subspace codes and/or codes derived from an invertible transform, such as a CI code matrix. The first coded packets are distributed to multiple different channels1802, such as different network channels and/or different subchannels, for transmission to a destination node. Second coded packets are generated within the different channels1803, such as by linearly combining first coded packets distributed to the channels, and/or by employing codes derived from an invertible transform, such as a CI code matrix. In some aspects of the invention, intermediate nodes in a multi-hop path may perform second coding1803, and/or the destination node may provide second coding1803when combining signals received from its local group.

In one aspect of the disclosure, the at least one processor is configured to generate first coded packets by linearly combining original data packets within a sliding coding window. In another aspect, a first of the multiple different channels is associated with the first network interface unit and a second of the multiple different channels is associated with the second network interface unit. In some aspects of the invention, the first and second network interface units reside on different nodes that are communicatively coupled together (such as by a WLAN) and configured to cooperatively process the first coded packets.

Aspects of the invention may employ CI coding for direct sequence coding, spread-OFDM coding, and/or coding across subspaces, such as described throughout the '854 application, which is incorporated by reference in its entirety.

In OFDM, the transmission bandwidth is partitioned into a plurality N (which typically equals 2 raised to some integer power) of orthogonal subcarrier frequencies. Multicarrier spread-spectrum employs spreading across the subcarriers to produce a transmit signal expressed by x=F−1Sb, where F−1is an inverse discrete Fourier transform (DFT), S is a spread-OFDM code matrix, and b is the transmitted symbol vector. The inverse DFT typically employs an over-sampling factor, so its dimension is K×N (where K>N is the number of time-domain samples per OFDM symbol block), whereas the dimension of the spread-OFDM code matrix is N×N.

At the receiver, the received spread-OFDM signal is expressed by r=HF−1Sb, where H is a channel matrix for the transmission channel. A cyclic prefix in OFDM changes the Toeplitz-like channel matrix into a circulant matrix. The circulant channel matrix H is expressed by
H=F−1ΛHF,
wherein ΛHis a diagonal matrix whose diagonal elements correspond to the first column of the circulant channel matrix H.

Thus, the received signal is represented by
r=F−1ΛHFF−1Sb,
which is
r=F−1ΛHSb.

The receiver processes r with a DFT to produce
y=ΛHSb.

In order to facilitate the estimation of b, it is advantageous to employ a spreading code matrix S that commutes with ΛH. For example, the matrix S=ΛCF may be employed, wherein Λcis the diagonal matrix of the circulant matrix C, which is defined by C=F−ΛCF.

In this case, the received signal, r, is expressed as
r=F−1ΛHFF−1(ΛCF)b,
which can be written as

Following DFT processing, but prior to equalization, the signal, y, is expressed by y=ΛC−1Fr.

In the simplest case, the spreading matrix S=ΛCF may be implemented with ΛC=I, such that the spreading matrix S is just an N×N DFT matrix. Since OFDM's over-sampled DFT is K×N, the spreading matrix S may partially resemble a sin c pulse-shaping filter, except that it maps each data symbol to a cyclically shifted (and orthogonally positioned) superposition of OFDM subcarriers. In this case, the transmitter employs the spreading matrix C for spreading the data vector b: C=F−1ΛCF.

Since each spread symbol comprises a linear combination of the data vector's b values, if a spread symbol is lost during transmission, that loss is mitigated because it is effectively distributed across all the data values of b. Thus, spreading permits accurate estimation of a received signal despite substantial losses, even before error-correction coding is employed. Furthermore, this type of spreading permits a receiver to decode a transmission without requiring all of the spread symbols. For example, a receiver may accurately decode N data values by employing M<N spread symbols.

Since the spread symbols employ predetermined linear relationships between the data symbols of b, techniques typically employed in multi-user detection (such as, but not limited to, successive interference cancellation and mixed-decision symbol estimation) can enhance performance at the receiver. Thus, in some aspects of the invention, orthogonality of the spreading codes is not required if the spreading coefficients are known at the receiver. Rather, the code spaces processed by the receiver may simply need to be sufficiently de-correlated from each other to estimate the data symbols b.

In one aspect of the invention, the above-mentioned spreading matrix S is employed as an invertible transform to produce a sequence of coded data symbols x from an input data vector b: x=Sb. This implementation of the invertible transform matrix S takes the form of direct-sequence coding.

FIG. 19illustrates an invertible transform matrix that may be employed in some aspects of the invention. In one aspect, the invertible transform matrix S is an N×N matrix. Each row (e.g., row1901) of the matrix S multiplies original data vector b (which comprises N values) to produce a coded data symbol xi. Specifically, each coded data symbol xicomprises a linear combination of the original data symbols b, wherein the coefficients of the linear combination are values of the invertible transform matrix S.

To estimate an ithvalue biof the original data vector b, a decoding vector sicomprising an ithrow or column of a decoding matrix may be used to multiply the vector of coded data symbols x to produce an inner product, from which the estimated valueis derived. The vector simay be regarded as corresponding to an ithsubspace of the decoding matrix. Since the inner product requires vectors of equal length, if the number of coded data symbols x is deficient relative to the rank of the decoding matrix, then the decoding vector simay be reduced accordingly. For example, a jthvalue of the decoding vector sicorresponding to a jthmissing coded data symbol xjmay be omitted from the vector sibefore the multiplication. The decoding vector Sifunctions as a matched filter. In one aspect, the corresponding decoding matrix may comprise the complex conjugate of the matrix S. However, other aspect of the invention may employ different types of invertible CI matrices, including scalar code matrices and other complex code matrices. Gauss-Jordan elimination can be used to determine whether a given matrix is invertible and to find the inverse. An alternative is LU decomposition, which generates upper and lower triangular matrices, which are easier to invert.

The first element of each matrix row (indicated by the first column1910of matrix S) multiplies the first data symbol b0of the data vector b. In this case, all the values in the first column1910equal one. The corresponding decoding vector s0also has all of its values equal to one, so to retrieve the first data symbol b0, all the coded data symbols {x0, x1, . . . , xN-1} are summed. This can be regarded as a “baseband” matched filter. One of the advantages of employing the type of CI coding matrix shown inFIG. 19is that data mapped to this baseband subspace can be retrieved regardless of the order in which the coded data symbols {x0, x1, . . . , xN-1} are summed. Thus, in some aspects of the invention, certain control information may be included in packets that are encoded to this subspace. In some aspects of the invention, a decoding matrix may be included in the baseband subspace. In some aspects, information relating to the order and/or identity of the coded data symbols may be included in the baseband subspace.

To retrieve original data from a non-baseband subspace, a decoding vector may effectively map its corresponding subspace to baseband so the information in the other subspaces cancels out. For example, the data encoded in the target subspace combines coherently while data in all the other subspaces cancel. The decoding process may comprise an inner product of the coded data packets with one or more vectors of decoding coefficients. In some aspects, information about the intended order of the coded data (such as may be used for decoding) may be included in the baseband subspace such that the coded data can be arranged correctly if it is received out of order. In some aspects, information in the baseband subspace may be used to identify missing coded data such that decoding can be adapted accordingly. For example, in one aspect, values of the decoding vector(s) may be removed with respect to which coded data is missing.

Some advantages of employing these types of CI codes are that information can be decoded using fast transforms, such as processes that employ fast Fourier transforms, the codes can have any code length, and information can be re-encoded by intermediate nodes without requiring decoding. In some aspects of the invention, intermediate nodes participate in the coding process. For example, intermediates nodes may combine received packets and generate new packets. The encoded packets encapsulate the original packets, thus, sequence numbers and other control information in the original packets can remain concealed until they are decoded. Decoding only requires that a specified number of the coded packets be received. The order in which those packets are received is inconsequential. This permits a client to simultaneously employ multiple channels, even multiple different networks, with different bandwidths, latencies, and/or channel conditions to download a file or receive streaming media without requiring network servers to coordinate their transmissions. The destination node needs only to assemble a sufficient number of received packets in order to decode the flow. Since the code is either already known at the receiver or it is conveyed in the baseband subspace, the packets are interchangeable and the arrival order is irrelevant. No scheduling or route coordination is necessary at the source. Such advantages are particularly relevant in cloud networks.

As described above, some aspects of the invention may employ an invertible transform matrix Ŝ=F−1S, where F−1is a K×N inverse DFT (where K>N is the number of time-domain samples per OFDM symbol block), and S is an N×N spread-OFDM code matrix. In this case, the vector of coding coefficients that multiply OFDM subcarriers constitute a random linear mapping of the data vector b, as will be described with respect toFIGS. 20A and 20B.

FIG. 20Ais a constellation plot of original data values b, which clearly have a 64-QAM structure. In conventional OFDM, these data values would ordinarily modulate the OFDM subcarriers.FIG. 20Bis a constellation plot of subcarrier coefficients produced by employing a CI code matrix, such as the code matrix depicted inFIG. 19. The coded symbols comprise linear combinations of the original data determined by the invertible CI transform matrix.

The constellation plot inFIG. 20Bis a Gaussian distribution that is statistically random. In accordance with one aspect of the invention, a sequence of coded data symbols is generated from the operation x=F−1Sb and transmitted into one or more channels. In some aspects of the invention, the aforementioned subcarrier coefficients may instead be employed as coefficients in random linear combinations of the original data values. In such aspects, the coefficients may be derived from an invertible transform matrix (such as a CI matrix) and information about the original data symbols. Decoding may employ an iterative process for estimating the original data.

FIG. 21Ais a flowchart illustrating a method for transmitting data from a source node to a destination node via multiple different channels in accordance with an aspect of the invention. As described previously, the multiple different channels may be associated with different communication technologies.

First coded data packets are generated by combining original data packets using an invertible transform, such as a CI transform2101. The first coded packets may be generated using a block and/or sliding CI transform by forming a linear combination of the original packets currently within a coding window. For example, coded data may be generated by multiplying a vector of original data with a CI code matrix. Thus, each coded data packet comprises a different linear combination of the original data packets, and, thus, constitutes a degree of freedom. If a sliding transform is employed, as each new original packet is added to the coding window, an oldest original packet in the window may be shifted out. In some aspects, a new first coded packet may be generated for each new original packet added to the coding window. The size of the first coding window may be fixed or variable.

The multiple different channels may be monitored2102to identify one or more channels to insert a new first coded packet at a particular time. This monitoring process may continue until all of the data has been successfully transferred to and decoded at the destination node. When a channel is identified, one or more first coded packets may be distributed to the identified channel2103. Different first coded packets may be injected into different channels using the above-described technique. For example, in one aspect of the invention, a first coded packet is transmitted on a first channel and at least a second coded packet is transmitted on at least a second channel, wherein the first coded packet and the at least second coded packet together are necessary to provide a sufficient number of degrees of freedom to decode the original packet.

For each channel, one or more second coded packets may be generated2104by linearly combining the first coded packets that currently reside within a corresponding second coding window using an invertible transform, such as a CI transform. In some aspects, CI coefficients may comprise statistically random coefficients may be used to perform the linear combination.

FIG. 21Bis a flowchart illustrating a method for receiving data at a destination node via multiple different channels in accordance with an aspect of the invention. Upon receiving a coded packet at a destination node, the destination node may send an acknowledgement message to the source node2111. The destination node determines if a sufficient number of coded packets have been received to allow the receiver to decode the packets2112. If an invertible transform is employed for coding, a sufficient number of coded packets may be less than the number of original packets. Packets may need to be retransmitted until a sufficient number of packets are received. In some cases, the coding may be adapted (e.g., the coding window may be adjusted, the code rate may be adjusted, etc.) based on feedback from the destination node. Upon decoding, the receiver may send an acknowledgement for each original packet received2113.

FIG. 22Ais a flowchart illustrating a method for employing an invertible transform, such as CI coding, for distributing data from a source node to be received by a destination node via multiple routes through at least one network. The method comprises selecting a set of original data, such as original data packets, for encoding2201. The selected data is encoded using an invertible transform2202, such as a CI transform. A multiple distribution nodes are selected to distribute the coded data2203, and the coded packets are distributed to the selected nodes2204.

Selecting the original data2201may comprise partitioning the data into a predetermined number of data sections, such as packets or other data sets, wherein the predetermined number may comprise the dimension of the invertible transform used for coding. The predetermined number may comprise the length of a coding window employed, such as when a sliding CI transform is employed. In some aspects, the predetermined number may be related to a number of distribution nodes to which the coded data will be distributed2203, the storage capability of each distribution node, network conditions (e.g., traffic load, latency, bandwidth, link quality, etc.) in the vicinity of each node, demand for the original data, and/or other factors that can affect the flow and timely delivery of the original data to one or more clients. In some aspects, the predetermined number may be related to a number of network paths or channels used for delivering data to the destination node.

Coding2202may comprise employing a block transform or a sliding transform, or some combination thereof. In some aspects of the invention, the coded packets and the corresponding code matrix comprise a plurality of independent equations having a plurality of independent variables in a system of linear equations, wherein the independent variables comprise the original packets. In some aspects of the invention, control information may be encoded into the baseband subspace of the coded data. For example, the control information may help a receiver identify individual coded packets such that if a coded packet is lost, decoding can be adapted accordingly. The control information may identify a preferred sequence of the coded packets, so a receiver can correctly arrange received packets such as to facilitate decoding of the non-baseband subspaces.

Selecting the distribution nodes2203may comprise selecting nodes that are nearby the destination node. The distribution nodes may comprise edge servers in a content delivery network. In some aspects, the selection of distribution nodes2203may be based on anticipated and/or actual demand for the original data. The distribution nodes may be selected2203to best serve requesting clients, such as to offload network loads from the network backbone to the network edges, reduce latency when serving data to the clients, and/or reduce distribution costs for content providers. In peer-to-peer networks, some of the clients may be selected as distribution nodes. For example, a client requesting the original data may be directed to retain a set of coded packets containing the original data such that the client may serve other clients requesting the same original data.

Distributing the coded packets to the distribution nodes2204may comprise determining how much data to store on each node. In one aspect, distributing may first comprise determining storage capability of each candidate distribution node. Distributing2204may comprise calculating a cost per unit flow on each link, and/or determining link capacity, link traffic, and/or other factors affecting how data is distributed. Distributing2204may comprise determining demand topology in a network, such as to determine how much and where coded data is distributed.

In some aspects of the invention, distributing2204comprises providing each of a plurality of the distribution nodes with a number of coded components that is less than a number of required degrees of freedom to decode the coded components. A destination node can acquire a sufficient number of the coded components to perform decoding by collecting coded components from more than one distribution node. This can reduce the amount of data stored on each distribution node while still being able to serve the clients. Thus, distributing2204may comprise determining a network demand topology to use for calculating which coded packets to distribute to which nodes in a manner that serves the requesting client(s) while reducing network traffic and storage requirement on the distribution nodes. In other aspects, distributing2204may be based on network bandwidth, latency, link quality, and/or other link metrics pertaining to each of a plurality of channels employed by the distribution nodes serving a client.

FIG. 22Bis a flowchart illustrating a method for employing an invertible transform, such as CI coding, for receiving data from a plurality of routes through at least one network. The method comprises a destination node selecting a plurality of distribution nodes from which to receive coded packets2211, collecting the coded packets from the selected distribution nodes2212, and determining if a sufficient number of unique coded packets have been collected to decode the packets2213. If the destination node determines that a sufficient number of degrees of freedom are available with respect to the collected packets, then it performs decoding2214. Otherwise, control returns to processing block2211, and at least one more distribution node is selected. In some aspects, one of the distribution nodes may request additional coded packets (not shown), such as from other distribution nodes and/or a source node.

In one aspect of the invention, the nodes are selected2211to provide a sufficient number of coded packets (e.g., which, along with their respective code matrix, represent linearly independent equations) for decoding the original packets (e.g., unknown variables). In some aspects, the invertible transform matrix is known at the receiver, so the coding matrix is not transmitted to the distribution nodes. However, information about the relation of each coded packet to the coding matrix may be provided to the distribution nodes and transmitted to the destination node.

In one aspect, decoding2214comprises calculating a solution for a system of linear equations comprising the independent equations and their independent variables. In this aspect, the independent equations comprise the coded packets and the corresponding invertible transform matrix, and the independent variables comprise the plurality of original packets.

As described throughout the '107 application, distributing data on network routes may be performed in a manner that achieves one or more cost objectives, including cost objectives related to combinations of technical and business objectives. Such aspects of the invention may be applied to communication systems in which multiple different networks are simultaneously employed for transmitting data from a source to a destination.

In one aspect of the invention, a method of providing minimum-cost routing comprises modeling a network between a source node and a destination node as a trellis graph, wherein each state node of the trellis corresponds to a network node, and each transition between states corresponds to a communication link between network nodes. A cost is associated with each link, and then a path is calculated through the trellis that minimizes the total cost for routing data between the source and destination nodes. The cost for each link may be based on various combinations of factors, including link capacity, available storage at each node, network traffic loads, link latency, quality of service, etc. In some aspects, coding is part of the routing operation, and it may directly affect the cost associated with the links. As a route for each data set (e.g., coded data packet) is determined, the cost for each link may be updated, and then the process is repeated for the next data set (e.g., coded packet). This process may be repeated for a plurality of coded packets, such as to determine an optimal number of coded packets, code rate, code matrix, and/or other coding parameters prior to encoding and routing the coded data.

Additional aspects of the invention include a computerized device configured to process all the method operations disclosed herein. In such aspects, the computerized device may include a memory system, a processor, communications interface in an interconnection mechanism connecting these components. The memory system may be encoded with a process that provides the coding techniques as explained herein that, when performed (e.g. when executing) on the processor, operates as explained herein within the computerized device to perform methods and operations explained herein as aspects of the invention.

Other aspects of the invention that are disclosed herein may include software programs to perform the methods and operations described above. More particularly, a computer program product is one aspect that has a non-transient computer-readable medium including computer program logic encoded thereon that when performed in a computerized device provides associated operations providing the functions explained herein. The computer program logic, when executed on at least one processor with a computing system, causes the processor to perform the operations (e.g., the methods) indicated herein as aspects of the invention. Such aspects are typically provided as software, code and/or other data structures arranged or encoded on a non-transient computer readable medium such as an optical medium (e.g., CD-ROM), floppy or hard disk or other a medium such as firmware or microcode in one or more ROM or RAM or PROM chips or as an Application Specific Integrated Circuit (ASIC) or as downloadable software images in one or more modules, shared libraries, etc. The software or firmware or other such configurations can be installed onto a computerized device to cause one or more processors in the computerized device to perform the techniques explained herein. Software processes that operate in a collection of computerized devices, such as in a group of data communications devices or other entities can also provide a system in accordance with aspects of the invention. The system can be distributed between many software processes on several data communications devices, or all processes could run on a small set of dedicated computers, or on one computer alone.

For clarity of explanation, the illustrative system and method aspects is presented as comprising individual functional blocks. The functions these blocks represent may be provided through the use of either shared or dedicated hardware, including, but not limited to, hardware capable of executing software. For example the functions of one or more blocks may be provided by a single shared processor or multiple processors. Use of the term “processor” should not be construed to refer exclusively to hardware capable of executing software. Illustrative aspects may comprise microprocessor and/or digital signal processor (DSP) hardware, read-only memory (ROM) for storing software performing the operations discussed below, and random access memory (RAM) for storing results. Very large scale integration (VLSI), field-programmable gate array (FPGA), and application specific integrated circuit (ASIC) hardware aspects may also be provided.

The methods and systems described herein merely illustrate particular aspects of the invention. It should be appreciated that those skilled in the art will be able to devise various arrangements, which, although not explicitly described or shown herein, embody the principles of the invention and are included within its scope. Furthermore, all examples and conditional language recited herein are intended to be only for pedagogical purposes to aid the reader in understanding the principles of the invention. This disclosure and its associated references are to be construed as being without limitation to such specifically recited examples and conditions. Moreover, all statements herein reciting principles and aspects of the invention, as well as specific examples thereof, are intended to encompass both structural and functional equivalents thereof. Additionally, it is intended that such equivalents include both currently known equivalents as well as equivalents developed in the future, i.e., any elements developed that perform the same function, regardless of structure.