Network coding in automatic receipt request
Network coding in automatic receipt request (ARQ) functionality is disclosed. A compatible transmitter configures a new transmission period, in which the set of data for transmission is transmitted, and a retransmission period, after the new transmission period, in which a number of network coded data is retransmitted based on the acknowledgement feedback received from the receivers receiving the transmitted set of data. The acknowledgement feedback identifies one or more data requested for retransmission by one or more of the receivers. The transmitter determines a number of network coded data that could be transmitted to accommodate each of the requesting receivers and the data requested by such receivers for retransmission. These network coded data would then be retransmitted by the transmitter during the retransmission period.
1 . A method of wireless communication, comprising:
transmitting, by a transmitter, a set of data to a plurality of receivers over a predetermined transmission period;
receiving, by the transmitter, acknowledgement feedback from the plurality of receivers for the set of data transmitted, wherein the acknowledgement feedback identifies one or more data segments of the set of data requested for retransmission by one or more requesting receivers of the plurality of receivers;
determining, by the transmitter, one or more combinations of data segments of the set of data, individual data segments of the one or more combinations of data segments corresponding to a data segment of the one or more data segments identified for retransmission by the acknowledgement feedback, a combination of data segments of the one or more combinations of data segments is determined in accordance with corresponding acknowledgement feedback of the acknowledgement feedback received from a corresponding receiver of the one or more requesting receivers, wherein the determining of the one or more combinations of data segments includes:
generating, by the transmitter, a retransmission matrix, A, wherein individual rows of the retransmission matrix represent vectors identifying:
the one or more data segments of the set of data requested for retransmission by a corresponding receiver of the one or more requesting receivers, and
one or more decoded data of the set of data successfully decoded by the corresponding receiver identified in the acknowledgement feedback;
reducing, by the transmitter, the retransmission matrix to a reduced retransmission matrix having a lower rank, r, than an original rank of the retransmission matrix, A; and
determining, by the transmitter, a row basis of the reduced retransmission matrix, wherein individual row basis vectors of the reduced retransmission matrix correspond to individual combinations of data segments of the one or more combinations of data segments, and entries of the individual row basis vectors correspond to the individual data segments of the one or more combinations of data segments, and wherein the row basis of the reduced retransmission matrix includes r row basis vectors;
encoding, by the transmitter, the combination of data segments of the one or more combinations of data segments into a corresponding network coded data segment; and
transmitting, by the transmitter, the corresponding network coded data segment for the combination of data segments of the one or more combinations of data segments during a predetermined retransmission period after the predetermined transmission period.
2 . The method of claim 1 , wherein the encoding the combination of data segments further includes:
including an original packet identifier (ID) associated with transmission of the data segment of the one or more data segments corresponding to the individual data segments of the one or more combinations of data segments to the individual data segments of the combination of data segments encoded into the corresponding network coded data segment.
3 . The method of claim 1 , further including:
determining a transmission duration of the predetermined transmission period and a retransmission duration of the predetermined retransmission period based on one of:
a delay budget and a buffer budget of the plurality of receivers; or
a delay sensitivity of the set of data.
4 . The method of claim 3 , further including:
receiving, by the transmitter, a budget report signal from the plurality of receivers, wherein the budget report signal includes identification of the delay budget and the buffer budget of the plurality of receivers.
5 . The method of claim 1 , wherein the retransmission matrix is an n×m matrix, where a number of rows, n, is equal to a total number of receivers of the plurality of receivers, and a number of columns, m, is equal to a total number of data segments in the set of data.
6 . The method of claim 1 , wherein the reducing the retransmission matrix to a reduced retransmission matrix includes:
defining a reduced intermediate matrix, C K×K , of the retransmission matrix, A K×K , such that:
C
(
i
,
i
)
=
1
,
for
0
≤
i
≤
K
;
and
C
(
i
,
j
)
=
0
,
if
A
(
i
,
j
)
=
0
;
and
replacing any nonzero non-diagonal entries of the reduced intermediate matrix with 0, when the replacing results in a further lower rank of the reduced intermediate matrix than the lower rank; and
setting the reduced retransmission matrix equal to the reduced intermediate matrix after the defining and the replacing.
7 . The method of claim 6 , wherein the further lower rank includes a minimum rank, r min .
8 . The method of claim 1 , wherein the generating the retransmission matrix, A, includes:
defining a size of the retransmission matrix, A, as an n×m matrix, according to:
n
=
(
∑
u
=
0
U
-
1
❘
"\[LeftBracketingBar]"
X
u
❘
"\[RightBracketingBar]"
)
,
and
m
=
F
,
or more requesting receivers, U represents a receiver index of U, X u represents the one or more data segments requested for retransmission of the corresponding receiver, |X u | represents a number of the one or more data segments requested for retransmission of the corresponding receiver, and F represents a total number of the one or more data segments requested for retransmission by the one or more requesting receivers;
inputting the one or more data segments requested for retransmission into the retransmission matrix, A, according to:
for an m-th data in X u , set A (i,j) =1, where:
i
=
∑
v
u
-
1
❘
"\[LeftBracketingBar]"
X
v
❘
"\[RightBracketingBar]"
-
1
+
m
,
and
j=an index of the m-th data in X u ;
inputting the one or more decoded data into the retransmission matrix, A, according to:
for the m-th data in W u , set
A
(
∑
v
=
0
u
-
1
❘
"\[LeftBracketingBar]"
X
v
❘
"\[RightBracketingBar]"
:
∑
v
=
0
u
❘
"\[LeftBracketingBar]"
X
v
❘
"\[RightBracketingBar]"
-
1
,
j
)
=
1
,
when u>0, and A (0:|x 0 |−1,j) =1, when u=0 where:
W u represents a number of the one or more decoded data, and
j=an index of the m-th data in W u ; and
setting all other entries of the retransmission matrix, A, to 0.
9 . The method of claim 1 , further including:
receiving, by the transmitter, subsequent acknowledgement feedback from the plurality of receivers for the corresponding network coded data segment for the combination of data segments of the one or more combinations of data segments transmitted, wherein the subsequent acknowledgement feedback includes identification of one or more additional data segments transmitted in the corresponding network coded data segment of the one or more combinations of data segments requested for retransmission by one or more additional requesting receivers of the plurality of receivers;
determining, by the transmitter, a remaining retransmission budget based on one or more of: a delay budget and a buffer budget of the one or more additional requesting receivers;
retransmitting, by the transmitter, the one or more additional data segments in response to a time for retransmission falling within the remaining transmission budget; and
adding, by the transmitter, the one or more additional data segments requested for retransmission to a subsequent predetermined transmission period in response to the time for immediate retransmission exceeding the remaining retransmission budget.
10 . The method of claim 9 , wherein the adding the one or more additional data segments requested for retransmission includes:
transmitting, by the transmitter, a new set of data to the plurality of receivers over a subsequent predetermined transmission period, the new set of data including the one or more additional data segments requested for retransmission;
receiving, by the transmitter, additional acknowledgement feedback from the plurality of receivers for the new set of data transmitted, wherein the additional acknowledgement feedback identifies one or more new data segment of the new set of data requested for retransmission by one or more subsequent requesting receivers of the plurality of receivers;
determining, by the transmitter, one or more new combinations of data segments of the new set of data, individual new data segments of the one or more new combinations of data segments correspond to a new data segment of the one or more new data segments identified for retransmission by the additional acknowledgement feedback, a new combination of data segments of the one or more new combinations of data segments is determined in accordance with corresponding additional acknowledgement feedback of the additional acknowledgement feedback received from the corresponding receiver of the one or more subsequent requesting receivers;
encoding, by the transmitter, the new combination of data segments of the one or more new combinations of data segments into a corresponding subsequent network coded data segment; and
transmitting, by the transmitter, the corresponding subsequent network coded data segment for the new combination of data segments of the one or more new combinations of data segments during a subsequent predetermined retransmission period after the subsequent predetermined transmission period.
11 . An apparatus configured for wireless communication, the apparatus comprising:
at least one processor; and
a memory coupled to the at least one processor,
wherein the at least one processor is configured:
to transmit, by a transmitter, a set of data to a plurality of receivers over a predetermined transmission period;
to receive, by the transmitter, acknowledgement feedback from the plurality of receivers for the set of data transmitted, wherein the acknowledgement feedback identifies one or more data segments of the set of data requested for retransmission by one or more requesting receivers of the plurality of receivers;
to determine, by the transmitter, one or more combinations of data segments of the set of data, individual data segments of the one or more combinations of data segments corresponding to a data segment of the one or more data segments identified for retransmission by the acknowledgement feedback, a combination of data segments of the one or more combinations of data segments is determined in accordance with corresponding acknowledgement feedback of the acknowledgement feedback received from a corresponding receiver of the one or more requesting receivers;
to encode, by the transmitter, the combination of data segments of the one or more combinations of data segments into a corresponding network coded data segment;
to transmit, by the transmitter, the corresponding network coded data segment for the combination of data segments of the one or more combinations of data segments during a predetermined retransmission period after the predetermined transmission period;
to receive, by the transmitter, subsequent acknowledgement feedback from the plurality of receivers for the corresponding network coded data segment for the combination of data segments of the one or more combinations of data segments transmitted, wherein the subsequent acknowledgement feedback includes identification of one or more additional data segments transmitted in the corresponding network coded data segment of the one or more combinations of data segments requested for retransmission by one or more additional requesting receivers of the plurality of receivers;
to determine, by the transmitter, a remaining retransmission budget based on one or more of: a delay budget or a buffer budget of the one or more additional requesting receivers;
to retransmit, by the transmitter, the one or more additional data segments in response to a time for retransmission falling with the remaining transmission budget; and
to add, by the transmitter, the one or more additional data segments requested for retransmission to a subsequent predetermined transmission period in response to the time for retransmission exceeding the remaining retransmission budget.
12 . The apparatus of claim 11 , wherein the configuration of the at least one processor to encode the combination of data segments further includes configuration of the at least one processor:
to include an original packet identifier (ID) associated with transmission of the data segment of the one or more data segments corresponding to the individual data segments of the one or more combinations of data segments to the individual data segments of the combination of data segments encoded into the corresponding network coded data segment.
13 . The apparatus of claim 11 , further including configuration of the at least one processor to determine a transmission duration of the predetermined transmission period and a retransmission duration of the predetermined retransmission period based on one of:
a delay budget and a buffer budget of the plurality of receivers; or
a delay sensitivity of the set of data.
14 . The apparatus of claim 13 , further including configuration of the at least one processor to receive, by the transmitter, a budget report signal from the plurality of receivers, wherein the budget report signal includes identification of the delay budget and the buffer budget of the plurality of receivers.
15 . The apparatus of claim 11 , wherein the configuration of the at least one processor to determine the one or more combinations of data segments includes configuration of the at least one processor:
to generate, by the transmitter, a retransmission matrix, A, wherein individual rows of the retransmission matrix represent a vector identifying the one or more data segments of the set of data requested for retransmission requested by a corresponding receiver of the one or more requesting receivers and one or more decoded data of the set of data successfully decoded by the corresponding receiver identified in the acknowledgement feedback;
to reduce, by the transmitter, the retransmission matrix to a reduced retransmission matrix having a lower rank, r, than an original rank of the retransmission matrix, A; and
to determine, by the transmitter, a row basis of the reduced retransmission matrix, wherein individual row basis vectors of the reduced retransmission matrix correspond to individual combinations of data segments of the one or more combinations of data segments and entries of the individual row basis vectors correspond to the individual data segments of the one or more combinations of data segments, and wherein the row basis of the reduced retransmission matrix includes r row basis vectors.
16 . The apparatus of claim 15 , wherein the retransmission matrix is an n×m matrix, where a number of rows, n, is equal to a total number of receivers of the plurality of receivers, and a number of columns, m, is equal to a total number of data segments in the set of data.
17 . The apparatus of claim 15 , wherein the configuration of the at least one processor to reduce the retransmission matrix to a reduced retransmission matrix includes configuration of the at least one processor:
to define a reduced intermediate matrix, C K×K , of the retransmission matrix, A K×K , such that:
C
(
i
,
i
)
=
1
,
for
0
≤
i
≤
K
;
and
C
(
i
,
j
)
=
0
,
if
A
(
i
,
j
)
=
0
;
and
to replace any nonzero non-diagonal entries of the reduced intermediate matrix with 0, when the configuration of the at least one processor to replace results in a further lower rank of the reduced intermediate matrix than the lower rank; and
to set the reduced retransmission matrix equal to the reduced intermediate matrix after execution of the configuration of the at least one processor to define and configuration of the at least one processor to replace.
18 . The apparatus of claim 17 , wherein the further lower rank includes a minimum rank, r min .
19 . The apparatus of claim 15 , wherein the configuration of the at least one processor to generate the retransmission matrix, A, includes configuration of the at least one processor:
to define a size of the retransmission matrix, A, as an n×m matrix, according to:
n
=
(
∑
u
=
0
U
-
1
❘
"\[LeftBracketingBar]"
X
u
❘
"\[RightBracketingBar]"
)
,
and
m
=
F
,
or more requesting receivers, u represents a receiver index of U, X u represents the one or more data segments requested for retransmission of the corresponding receiver, |X u | represents a number of the one or more data segments requested for retransmission of the corresponding receiver, and F represents a total number of the one or more data segments requested for retransmission by the one or more requesting receivers;
to input the one or more data segments requested for retransmission into the retransmission matrix, A, according to:
for an m-th data in X u , set A (i,j) =1, where:
i
=
∑
v
u
-
1
❘
"\[LeftBracketingBar]"
X
v
❘
"\[RightBracketingBar]"
-
1
+
m
,
and
j=an index of the m-th data in X u ;
to input the one or more decoded data into the retransmission matrix, A, according to:
for the m-th data in W u , set
A
(
∑
v
=
0
u
-
1
❘
"\[LeftBracketingBar]"
X
v
❘
"\[RightBracketingBar]"
:
∑
v
=
0
u
❘
"\[LeftBracketingBar]"
X
v
❘
"\[RightBracketingBar]"
-
1
,
j
)
=
1
,
when u>0, and A (0:|x 0 |-1,j) =1, when u=0 where:
W u represents a number of the one or more decoded data, and
j=an index of the m-th data in W u ; and
to set all other entries of the retransmission matrix, A, to 0.
20 . The apparatus of claim 11 , wherein the configuration of the at least one processor to add the one or more additional data segments requested for retransmission includes configuration of the at least one processor:
to transmit, by the transmitter, a new set of data to the plurality of receivers over a subsequent predetermined transmission period, the new set of data including the one or more additional data segments requested for retransmission;
to receive, by the transmitter, additional acknowledgement feedback from the plurality of receivers for the new set of data transmitted, wherein the additional acknowledgement feedback identifies one or more new data segment of the new set of data requested for retransmission by one or more subsequent requesting receivers of the plurality of receivers;
to determine, by the transmitter, one or more new combinations of data segments of the new set of data, individual new data segments of the one or more new combinations of data segments corresponding to a new data segment of the one or more new data segments identified for retransmission by the additional acknowledgement feedback, a new combination of data segments of the one or more new combinations of data segments is determined in accordance with corresponding additional acknowledgement feedback of the additional acknowledgement feedback received from the corresponding receiver of the one or more subsequent requesting receivers;
to encode, by the transmitter, the new combination of data segments of the one or more new combinations of data segments into a corresponding subsequent network coded data segment; and
to transmit, by the transmitter, the corresponding subsequent network coded data segment for the new combination of data segments of the one or more new combinations of data segments during a subsequent predetermined retransmission period after the subsequent predetermined transmission period.
21 . A method of wireless communication, comprising:
transmitting, by a transmitter, a set of data to a plurality of receivers over a predetermined transmission period;
receiving, by the transmitter, acknowledgement feedback from the plurality of receivers for the set of data transmitted, wherein the acknowledgement feedback identifies one or more data segments of the set of data requested for retransmission by one or more requesting receivers of the plurality of receivers;
determining, by the transmitter, one or more combinations of data segments of the set of data, individual data segments of the one or more combinations of data segments corresponding to a data segment of the one or more data segments identified for retransmission by the acknowledgement feedback, a combination of data segments of the one or more combinations of data segments is determined in accordance with corresponding acknowledgement feedback of the acknowledgement feedback received from a corresponding receiver of the one or more requesting receivers;
encoding, by the transmitter, the combination of data segments of the one or more combinations of data segments into a corresponding network coded data segment;
transmitting, by the transmitter, the corresponding network coded data segment for the combination of data segments of the one or more combinations of data segments during a predetermined retransmission period after the predetermined transmission period;
receiving, by the transmitter, subsequent acknowledgement feedback from the plurality of receivers for the corresponding network coded data segment for the combination of data segments of the one or more combinations of data segments transmitted, wherein the subsequent acknowledgement feedback includes identification of one or more additional data segments transmitted in the corresponding network coded data segment of the one or more combinations of data segments requested for retransmission by one or more additional requesting receivers of the plurality of receivers;
determining, by the transmitter, a remaining retransmission budget based on one or more of: a delay budget and a buffer budget of the one or more additional requesting receivers;
retransmitting, by the transmitter, the one or more additional data segments in response to a time for retransmission falling within the remaining transmission budget; and
adding, by the transmitter, the one or more additional data segments requested for retransmission to a subsequent predetermined transmission period in response to the time for immediate retransmission exceeding the remaining retransmission budget.