nach oben

EURASIP Journal on Wireless Communications and Networking

Erschienen in:

Open Access 01.12.2013 | Research

Network-coded retransmissions in wireless demodulate-and-forward relay channels

verfasst von: Ye Liu, Chi Wan Sung

Erschienen in: EURASIP Journal on Wireless Communications and Networking | Ausgabe 1/2013

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Patentsuche

Aus

Abstract

Consider the case where a source wishes to reliably deliver a number of data packets to the destination with the help of a demodulate-and-forward relay. We discuss two retransmission schemes, each of which can ensure that the packets from the source will be delivered to the destination without error. We first discuss a scheme that combines signals from the source and the relay at the destination using a weighed combiner. The use of network coding which facilitates the retransmission process is then proposed. The generation of network-coded retransmission packets takes the qualities of previously erroneously received packets at the destination into account, and we show that such network coding scheme can make the retransmission process more efficient even if there is only one destination, unlike the existing approaches where the gain of network coding must come from coding opportunities across multiple destinations. Simulation results show that while the first retransmission scheme performs well in the low signal-to-noise ratio (SNR) region, the second scheme has good performance in both low and high SNR regions, thanks to the use of network coding. Moreover, the second scheme induces smaller packet decoding delay than the first scheme.

Authors’ original file for figure 1

Authors’ original file for figure 2

Authors’ original file for figure 3

Authors’ original file for figure 4

Authors’ original file for figure 5

Authors’ original file for figure 6

Authors’ original file for figure 7

Authors’ original file for figure 8

Electronic supplementary material

The online version of this article (doi:10.1186/1687-1499-2013-136) contains supplementary material, which is available to authorized users.

Competing interests

Both authors declare that they have no competing interests.

1 Introduction

1.1 Motivation and contribution

Relay has found itself becoming part of the long term evolution-advanced (LTE-A) due to its ability to extend coverage area and increase users’ throughput [1]. Forming a virtual antenna array with the source, works have been done (e.g., [2‐4]) so that maximum possible diversity gain can be obtained when the relay works in different modes, namely decode-and-forward (DF), amplify-and-forward, and demodulate-and-forward (DmF). It has been demonstrated that with the help of relays, lower outage error probability can be achieved.

When multiple packets are to be routed to multiple destinations, network coding [5] has been proven to be an efficient solution in many network models. Works have been done to study the advantages of network coding in broadcast channels, including linear network coding [6‐9] and non-linear network coding [10]. In DF relay channels, outage analysis was performed in DF relay channels with two destinations in [11], where the use of network coding achieves full diversity with less bandwidth and energy. Retransmission schemes are then designed in [12] for the same type of network, and network coding opportunities of different lost packets are exploited among destinations, which greatly improves the throughput of the proposed schemes. A network-coded retransmission scheme of multiple sources multiple destinations with the help of a single relay is designed in [13], where the relay performs binary linear network coding on packets from different sources to increase throughput. The use of network coding in DmF multi-user multi-relay channels is also proposed in [14], where a relay is selected to forward network-coded packets by the realized channel gains of the source-to-relay links and relay-to-destination links, and a diversity of two is observed for each source.

In this paper, we discuss the retransmissions of multiple packets in wireless DmF relay channels shown in Figure 1, where the relay is limited to perform demodulation and re-modulation to mitigate the large decoding delay in DF relays. We first design a retransmission scheme based on weighted combining. In this particular scheme, the destination will use a weighted combiner in [3] to combine signals from the source and relay after applying different weights on them. We then demonstrate how a network-coded packet generated by a DmF relay can help the destination to decode the erroneous packets previously received from the source and propose a retransmission scheme using both network coding and weighted combiner. We seek for possibilities for the relay to perform network coding based on the signal-to-noise ratios (SNRs) of packets in error at the destination. Rules of forming network-coded packets are very easy to implement. Unlike [6‐8] and [12], where the gain of network coding must have come from employing multiple destinations, our approach can make use of network coding to achieve better performance even if there is only one intended destination. The attractive feature of the proposed network-coded retransmission scheme has a high potential to be extended to systems with multiple destinations, which will be a topic for future investigations. Simulation results show that for different relay positions, the second retransmission scheme using network coding requires less retransmissions and has smaller packet decoding delay than the first scheme.

The rest of the paper is organized as follows. In Section 2, the system model will be set up and the weighted combiner will be briefly summarized. In Section 3, retransmission schemes based on the weighted combiner and network coding will be discussed. After that, algorithms for finding network-coded packets will be proposed in Section 4. Simulation results will be given in Section 5. Finally, conclusion and future works will be the content of Section 6.

1.2 Notations

Throughout the paper, we use boldface to represent a column vector (e.g. A for vector A) and math calligraphy to represent a set (e.g.,

ℬ

for set

ℬ

). ∥·∥ denotes the Euclidean norm. (·)^∗ means the conjugate, (·)^T means the transpose, and (·)^H means conjugate transpose. ⌊ x ⌋ takes the floor of a real number x. ⊕ denotes the bit-wise exclusive OR operation. Q (·) is the Q-function, and

Q (x) : = \frac{1}{\sqrt{2 π}} \int_{x}^{\infty} exp (- t^{2} / 2) dt

2 System model

Consider the relay channel displayed in Figure 1, where the source wishes to transmit its data to the destination via the help of relay. Transmissions are equally slotted in time, and the communication link between any two nodes in the network is modeled as block Rayleigh fading channel, where the real and imaginary parts of the channel coefficients are i.i.d. zero mean Gaussian random variables with variance 0.5 and remain unchanged in a time slot. The received signals at the relay and destination are also corrupted by additive white Gaussian noise with zero mean and σ² variance. The relay and the destination have full knowledge of the channel state information of the source-to-relay channel and the source-to-destination channel, respectively, so that coherent detection can be performed. Assume the transmission power of the source and the relay is the same and is normalized to 1. With the realized complex channel coefficient to be h for a communication link, the SNR of a transmitted packet at receiver side is given by

\frac{| h |^{2}}{σ^{2}}

. We will use h_SD, h_SR, and h_RD to indicate the channel coefficient of the source-to-destination link, the source-to-relay link, and the relay-to-destination link, respectively. The relay is placed somewhere between the source and the destination, and the effect of path loss is taken into consideration.

The source has K source packets of equal number of bits to be transmitted reliably to the destination. All transmissions, either from the source or from the relay, are assigned to different time slots of the same duration. We assume that a fixed-rate ideal channel coding scheme and binary phase-shift keying (BPSK) modulation is applied before sending a packet, where the channel coding scheme is ideal in the sense that decoding error is arbitrarily close to zero if the code rate is less than or equal to the channel capacity. Given a realized SNR Γ at the receiver, the rate log(1 + Γ) bits/s/Hz can be achieved [15]. For a given modulation scheme, the bit error rate (BER) after demodulation is directly related to Γ. Therefore, to correctly receive a packet, the BER after demodulation must be smaller or equal to a threshold value ε_th, so that the destination can correctly decode the packet.

The transmission of the K packets can be divided into two phases. In the initial phase, the K source packets are broadcasted to both the relay and the destination. Retransmission phase will start if not all of the K packets are received correctly by the destination. We assume that the control signals, i.e., acknowledgements (ACKs) and negative acknowledgements (NACKs), indicating reception success and failure of the corresponding packets, respectively, can be reliably received by intended receivers.

When there is no relay, the source can start the retransmission using chase combining-automatic repeat-request (CC-ARQ) scheme [16], where erroneous packets are repeatedly transmitted by applying the same channel coding and modulation scheme. For a packet P_i that is in error after the initial phase, all available observations at destination are processed by maximal ratio combining (MRC) [17] so that the SNR values of the observations can be added. Once the sum of the SNR values exceeds the threshold value T, where

T = Q^{- 1} {(ε_{th})}^{2},

(1)

the retransmission of P_i will be halted as P_i is now reliably received.

If a relay is present, the relay can overhear the transmissions in the initial phase and it may be helpful in the retransmission phase. Limited by its functionality, however, the relay is not able to decode the original data packets from the source; hence, errors will be propagated to the destination if time slots are allocated to the relay in the retransmission phase. Nevertheless, if P_i is received at the relay with high SNR, then after demodulation and re-modulation, the BER of the re-modulated signal will be small. In that case, the relay is still able to provide useful information on the source packets and help achieve higher retransmission efficiency. A DmF relaying scheme is proposed in [3], where the destination applies a weighted combiner to the incoming signals from the source and the relay, such that a diversity of 2 is achieved. We now describe the relay scheme in [3] for future references.

Consider a symbol vector X transmitted from the source in the first time slot. Denote the received signals at the relay and the destination as Y_SR and Y_SD, respectively. The relay performs coherent maximal-likelihood demodulation on Y_SR. Denote the re-modulated signal vector at the relay as

\hat{X_{R}}

. For BPSK, the i th symbol of

\hat{X_{R}}

satisfies the following relation:

\hat{X_{R}} (i) = \{\begin{array}{l} 1, & Y_{SR} (i) \geq 0, \\ - 1, & Y_{SR} (i) < 0 . \end{array}

(2)

In the second time slot, the relay transmits

\hat{X_{R}}

, and the destination receives Y_RD from the relay. Let Γ_SD, Γ_SR, and Γ_RD be the SNRs of Y_SD, Y_SR, and Y_RD, respectively. The combined symbol vector Y_D can be written as [3]:

Y_{D} = w_{SD} Y_{SD} + w_{RD} Y_{RD},

(3)

where

w_{SD} = h_{SD}^{*},

(4)

and

w_{RD} = \frac{{Q^{- 1} [ε_{eq} (Γ_{SR}, Γ_{RD})]}^{2}}{Γ_{RD}} h_{RD}^{*}

(5)

are the weights applied to Y_SD and Y_RD, respectively. In (5), ε_eq(Γ_SR,Γ_RD) is the equivalent BER of a signal at the destination after going through the source-to-relay link, being demodulated and re-modulated at the relay, and going through the relay-to-destination link. The expression of ε_eq is given as

\begin{array}{l} ε_{eq} (Γ_{SR}, Γ_{RD}) & = [1 - Q (\sqrt{Γ_{SR}})] Q (\sqrt{Γ_{RD}}) \\ + [1 - Q (\sqrt{Γ_{RD}})] Q (\sqrt{Γ_{SR}}) . \end{array}

(6)

The BER of Y_D is given as

\begin{align} ε_{D} & = [1 - Q (\sqrt{Γ_{SR}})] \int_{0}^{\infty} \frac{1}{\sqrt{2 π σ_{D}^{2}}} \\ \times exp {- \frac{{[x + (w_{SD} h_{SD} + w_{RD} h_{RD})]}^{2}}{2 σ_{D}^{2}}} dx \\ + Q (\sqrt{Γ_{SR}}) \int_{0}^{\infty} \frac{1}{\sqrt{2 π σ_{D}^{2}}} \\ \times exp {- \frac{{[x + (w_{SD} h_{SD} - w_{RD} h_{RD})]}^{2}}{2 σ_{D}^{2}}} dx, \end{align}

(7)

where

σ_{D}^{2} = (| w_{SD} |^{2} + | w_{RD} |^{2}) σ^{2}

It was shown in [3] that the above scheme can achieve the highest possible diversity. In the next section, we will design retransmission schemes based on the above weighted combiner.

3 Proposed retransmission schemes

In this section, we will discuss two retransmission schemes. One is based on the weighted combiner introduced in Section 2, and the other one uses both weighted combiner and network coding.

3.1 Cooperative retransmission

From (7), we can say that when ε_D ≤ ε_th, X can be correctly decoded. To maximize the efficiency of retransmissions when a relay is available, it is crucial to determine when the relay should retransmit. Also, in order to make sure that a retransmission scheme can always work, the source should delegate the retransmissions to relay only if the relay possesses good enough observations of the source packets. To achieve this robustness, the SNR of a packet received by the relay should exceed T, so that a packet can still be delivered to the destination via the relay in a finite number of retransmissions without knowing the SNR of the packet at the destination. Let the SNR threshold value at relay be T_R, where packets received by the relay are considered good enough to be forwarded if their SNRs are larger than or equal to T_R. It is clear that T_R should be set larger than T. After the initial phase, the following threshold-based cooperative retransmission (TCR) scheme will be initiated if there are packets at the destination that are not decoded correctly. Let Γ_1,SD,Γ_2,SD,...,Γ_K,SD be the SNRs of packets 1, 2,..., K at the destination after the initial phase, respectively. Let Γ_1,SR,Γ_2,SR,...,Γ_K,SR be the SNRs of packets 1, 2,..., K at the relay after the initial phase, respectively. The TCR scheme can be described as follows:

(1)

For the i th packet, i∈[1,K]: If Γ _i,SD≥T, increment i by 1. If Γ _i,SD<T, check the following conditions:

(a)

Γ _i,SR<T _R,

(b)

Γ _i,SR≥T _R.

(2)

If condition (a) is satisfied: The source retransmits X _i. The relay and the destination combine all different copies of X _i they received from the source using MRC, so that Γ _i,SR and Γ _i,SD are improved. The source stops retransmission until either Γ _i,SR ≥T _R or Γ _i,SD ≥ T. Go back to step 1.

If condition (b) is satisfied: The destination finds the required SNR of the receiving signal on the relay-to-destination link, namely Λ _i, such that ε _D = ε _th. The calculation of Λ _i can be done by applying bisection method to (7), after setting ε _D = ε _th, Γ _SR = Γ _th,R, w _SD h _SD = σ ² Γ _i,SD,

w_{RD} h_{RD} = \frac{{Q^{- 1} [ε_{eq} (Γ_{i, SR}, Λ_{i})]}^{2}}{σ^{2}}

. The relay keeps retransmitting

\hat{X_{i, R}}

until the destination has combined enough observations of

\hat{X_{i, R}}

by MRC such that the SNR of the combined copies of

\hat{X_{i, R}}

, denoted as

Γ_{\hat{X_{i}}}

, is larger than or equal to Λ _i. Go back to step 1.

To implement the TCR scheme, a counting-down method similar to [18] can be adopted. The destination will send ACKs and NACKs sequentially after the source broadcasts all its packets. If the destination sends an ACK for packet i, it will continue sending the control signal (either ACK or NACK) for packet i+1. If the destination sends a NACK for packet i, it will stop and wait for retransmissions of packet i until it can issue an ACK for it. The source and relay can setup their own timers, and the timers are started upon receiving a NACK signal from the destination. The initial value of the timer at the relay can be set according to Γ_i,SR. There will be two situations:

(1)

If Γ _i,SR < T _R, the source’s timer will expire first. The source then starts retransmitting the i th packet until either an ACK signal is received from the destination when Γ _i≥T or an ACK signal is received from the relay when Γ _i,SR≥ T _R. In the former case, the retransmission of the i th packet is done. In the latter case, the relay will send an ACK to the source, and the retransmission of the i th packet will be performed by the relay. The retransmission of the i th packet finishes until the destination issues an ACK.

(2)

If Γ _i,SR≥ T _R, the relay’s timer will expire first. The relay sends an ACK to the source so that the source will not perform retransmission and then retransmits the i th packet until it receives an ACK from the destination.

Good values of T_R under different channel settings will be obtained via simulations.

3.2 Network-coded cooperative retransmission

In this subsection, we first discuss how network-coded retransmission can be realized with the assumption that the relay has the correct versions of the packets that the source wishes to deliver to the destination. We will then extend the idea to DmF relays, where the relay may not have exact copies of the source’s packets.

3.2.1 Network-coded retransmission

Assume that the source wishes to deliver P₁ and P₂ to the destination, and the relay has the two packets. After the initial phase, the destination cannot correctly decode the two packets. The two packets’ SNRs at the destinations are Γ_1,SD and Γ_2,SD, respectively, where Γ_1,SD + Γ_2,SD ≥ T. Denote the received signals of P₁ and P₂ at destination after the initial phase as Y_1,SD and Y_2,SD, respectively. We have

\begin{align} Y_{2, SD} & = h_{2, SD} X_{2} + z \\ \Rightarrow \frac{h_{2, SD}^{H}}{h_{2, SD}^{H} h_{2, SD}} Y_{2, SD} & = X_{2} + \frac{h_{2, SD}^{H}}{h_{2, SD}^{H} h_{2, SD}} z, \end{align}

(8)

where h_2,SD is the channel coefficient of the source-to-destination link when P₂ is sent by the source. We further assume that P₁ ⊕ P₂ is transmitted by the relay and is correctly received by the destination. For ease of further development, we give the following definition of element-by-element multiplication between two vectors of equal length.

Definition 1.

Let ⋆ denote the element-by-element multiplication between two equal length vectors A and B, where A⋆B = C, A = [a₁,a₂,...,a_L], B = [b₁,b₂,...,b_L], C = [c₁,c₂,...,c_L], such that c_i = a_ib_i,i ∈ [1,L].

After correctly receiving P₁ ⊕ P₂, the destination can perform the following: First, it encodes P₁ ⊕ P₂ into X_{1 ⊕ 2} using the same channel coding and modulation schemes as the source’s, and then performs element-by-element multiplication between X_{1 ⊕ 2} and

\frac{h_{2, SD}^{H}}{h_{2, SD}^{H} h_{2, SD}} Y_{2, SD}

. Since BPSK modulation is applied and X_{1 ⊕ 2} is equal to X₁ ⋆ X₂, we have

\begin{align} X_{1 \oplus 2} ⋆ \frac{h_{2, SD}^{H}}{h_{2, SD}^{H} h_{2, SD}} Y_{2, SD} \\ = & X_{1} ⋆ X_{2} ⋆ X_{2} + X_{1} ⋆ X_{2} ⋆ \frac{h_{2, SD}^{H}}{h_{2, SD}^{H} h_{2, SD}} z \\ = & X_{1} + X_{1} ⋆ X_{2} ⋆ \frac{h_{2, SD}^{H}}{h_{2, SD}^{H} h_{2, SD}} z . \end{align}

(9)

We can see from (9) that by such a process, we come up with another noisy observation of P₁. The SNR of this observation is equal to Γ_2,SD, since the magnitude of each component of X₁ ⋆ X₂ is equal to one, and the noise term’s power is unchanged. Next, the destination combines

X_{1 \oplus 2} ⋆ \frac{h_{2, SD}^{H}}{h_{2, SD}^{H} h_{2, SD}} Y_{2, SD}

and Y_1,SD together using the MRC principle, and a noisy observation of P₁ with SNR Γ_1,SD + Γ_2,SD is formed. By the previous channel coding assumption, P₁ is now correctly received as Γ_1,SD + Γ_{2,S D}≥ T. With P₁ and P₁ ⊕ P₂, P₂ can be derived by the exclusive OR operation. From this example, it is illustrated that instead of simply repeating the two packets that the destination needs, the relay has an alternative: to transmit the network coded packet, under the condition that the sum SNRs of the two packets at destination is larger than T. The number of retransmitted packets is then reduced from two to one. The idea can also be extended to situations when higher modulation schemes are used, which is discussed in Appendix 1.

In general, if Γ_1,SD + Γ_2,SD + ⋯ + Γ_m,SD ≥ T, the relay can send P₁ ⊕ P₂, P₁ ⊕ P₃,..., P₁ ⊕ P_m to the destination. The destination will have m−1 more copies of P₁ with SNRs Γ_2,SD,Γ_3,SD,...,Γ_m,SD once it receives all the network-coded packets correctly. Combining all the m copies of P₁ (the underlying assumption is that the relay gets P₁ correctly in the initial transmission) with MRC will lead to successful decoding of P₁, and then P₂,P₃,...,P_m can be derived. We term such a combination of m packets’ SNRs as a valid m-wise combination.

3.2.2 Network-coded retransmission in DmF relay networks

In a DmF relay, as decoding is not performed, the re-modulated signal may contain errors. Nevertheless, it is still possible for a DmF relay to forward network-coded packets, and it is also possible for the destination to decode the network-coded packets from the relay correctly, which is demonstrated in the following:

Consider the transmission of two packets P₁ and P₂. After the initial phase, the destination has P₁ ’s SNR Γ_1,SD and P₂’s SNR Γ_2,SD, where Γ_1,SD < T, Γ_2,SD < T, and Γ_1,SD + Γ_2,SD ≥ T. The relay has observations of P₁ and P₂ with SNRs Γ_1,SR and Γ_2,SR, respectively. After demodulation and re-modulation, the relay has

\hat{X_{1, R}}

and

\hat{X_{2, R}}

, and then the network-coded symbol vector

\hat{X_{1, R}} ⋆ \hat{X_{2, R}}

can be formed. Note that

\hat{X_{1, R}} ⋆ \hat{X_{2, R}}

is essentially a noisy observation of P₁⊕P₂, with BER P^ma t h r m b_eq (Γ_1,SR,Γ_2,SR) (see (6)). Let

\begin{align} Γ_{eq} (Γ_{1, SR}, Γ_{2, SR}) \\ = & {Q^{- 1} [ε_{eq} (Γ_{1, SR}, Γ_{2, SR})]}^{2} \\ = & {Q^{- 1} {[1 - Q (\sqrt{Γ_{1, SR}})] Q (\sqrt{Γ_{2, SR}}) + [1 \\ - Q (\sqrt{Γ_{2, SR}})] Q (\sqrt{Γ_{1, SR}})}}^{2} . \end{align}

(10)

The above equation indicates that now the relay has a noisy observation of P₁ ⊕ P₂ with SNR Γ_eq (Γ_1,SR,Γ_2,SR). The relay retransmits

\hat{X_{1, R}} ⋆ \hat{X_{2, R}}

, and the destination gets a noisy observation of it with SNR Γ_RD. At this point, we can also say that the destination has a noisy observation of P₁ ⊕ P₂ with SNR Γ_eq (Γ_eq (Γ_1,SR,Γ_2,SR),Γ_RD). If Γ_eq (Γ_eq (Γ_1,SR,Γ_2,SR),Γ_RD) ≥ T, then we can say that P₁ ⊕ P₂ is correctly received by the destination.

In order to ensure that the network-coded packet

\hat{X_{1, R}} ⋆ \hat{X_{2, R}}

can be decoded correctly by the destination, the BER of

\hat{X_{1, R}} ⋆ \hat{X_{2, R}}

at the relay must be smaller than or equal to ε_th; otherwise, the BER of the packet received by the destination will never be smaller than or equal to ε_th, even if the relay-to-destination is noise-free. Therefore, Γ_eq (Γ_1,SR,Γ_2,SR) in (10) must be no smaller than T. This imposes the following constraint on Γ_1,SR and Γ_2,SR:

\begin{align} Γ_{1, SR} > T, \\ Γ_{2, SR} > T, \end{align}

(11)

due to the reason that for finite Γ_1,SR and Γ_2,SR,

Γ_{eq} (Γ_{1, SR}, Γ_{2, SR}) < min (Γ_{1, SR}, Γ_{2, SR}) .

(12)

To see why (12) is the case, with some abuse of notations, one realizes that if Γ_2,SR = +∞, then

\begin{align} Γ_{eq} (Γ_{1, SR}, + \infty) & = {Q^{- 1} [P_{eq}^{b} (Γ_{1, SR}, + \infty)]}^{2} \\ = {Q^{- 1} {[1 - Q (\sqrt{Γ_{1, SR}})] Q (\sqrt{+ \infty}) \\ + [1 - Q (\sqrt{+ \infty})] Q (\sqrt{Γ_{1, SR}})}}^{2} \\ = {Q^{- 1} [Q (\sqrt{Γ_{1, SR}})]}^{2} \\ = Γ_{1, SR} . \end{align}

(13)

Also, if we fix Γ_1,SR to be c and further reduce (10), we have

\begin{align} Γ_{eq} (c, Γ_{2, SR}) & = {Q^{- 1} {[1 - Q (\sqrt{c})] Q (\sqrt{Γ_{2, SR}}) + [1 \\ - Q (\sqrt{Γ_{2, SR}})] Q (\sqrt{c})}}^{2} \\ = {Q^{- 1} {[1 - 2 Q (\sqrt{c})] Q (\sqrt{Γ_{2, SR}}) \\ + Q (\sqrt{c})}}^{2} . \end{align}

(14)

Since

Q (\sqrt{c}) < 0.5

[1 - - 2 Q (\sqrt{c})] Q (\sqrt{Γ_{2, SR}}) + Q (\sqrt{c})

will be a monotonic decreasing function of Γ_2,SR. Furthermore, because Q⁻¹ (x) is a monotonic decreasing function of x, where 0 ≤ x ≤ 0.5, Γ_eq (c,Γ_2,SR) will be a monotonic increasing function of Γ_2,SR. We can then infer (12) from (13) and the monotonicity of (14).

Inspired by (10), to ensure that the relay can provide any necessary network-coded packet that can be ultimately received by the destination correctly, it is desirable to set a threshold value at the relay, namely T_R,NC, and make sure that each requested packet by the destination has SNR larger or equal to T_R,NC at the relay. The value of T_R,NC must be larger than T by (11). After setting T_R,NC, the required realized SNR of a network-coded packet at the destination, namely Λ_NC, can be found by

\begin{align} Γ_{eq} (Λ_{NC}, T_{R, NC}) = T \\ \Rightarrow & {Q^{- 1} {[1 - Q (\sqrt{Λ_{NC}})] Q (\sqrt{T_{R, NC}}) + [1 \\ - Q (\sqrt{T_{R, NC}})] Q (\sqrt{Λ_{NC}})}}^{2} = T \\ \Rightarrow & Λ_{NC} = {Q^{- 1} [ \\ \frac{Q (\sqrt{T}) - Q (\sqrt{T_{R, NC}})}{1 - 2 Q (\sqrt{T_{R, NC}})}]}^{2} . \end{align}

(15)

In the situations where Γ_1,SD + Γ_2,SD < T, sending

\hat{X_{1, R}} ⋆ \hat{X_{2, R}}

will not be able to help the destination decode P₁ or P₂ correctly. However, as

Q (\sqrt{Γ_{1, SR}}) \leq Q (\sqrt{T_{R, NC}}) < ε_{th}

, the relay has a good enough observation of P₁ and thus able to help the destination correctly receiving P₁ by retransmitting the demodulated and re-modulated version of P₁ (i.e.,

\hat{X_{1, R}}

). In general, the relay can help the destination correctly receiving P_i by retransmitting

\hat{X_{i, R}}

, if Γ_i,SR ≥ T_R,NC. The required SNR of received

\hat{X_{i, R}}

at the destination, namely Λ_i, can be calculated by applying bisection method to (7) as in the TCR scheme. Good T_R,NC values under different channel settings will be obtained via simulations.

In general, if Γ_1,SD + Γ_2,SD + ⋯+ Γ_m,SD≥T and Γ_i,SR ≥ T_R,NC, i ∈ [1,m], the relay can retransmit

\hat{X_{1, R}} ⋆ \hat{X_{2, R}}

\hat{X_{1, R}} ⋆ \hat{X_{2, R}}

,...,

\hat{X_{1, R}} ⋆ \hat{X_{m, R}}

, each of which must be received by the destination with SNR larger than or equal to Λ_NC.

We now propose the threshold-based network-coded cooperative retransmission (TNCCR) scheme, which will be initiated if there are packets that are not correctly received by the destination after the initial phase:

(1)

For P _i, i ∈ [1,K] such that Γ _i,SD < T, if Γ _i,SR < T _R,NC, then the source retransmits P _i until Γ _i,SD ≥ T or Γ _i,SR ≥ T _R,NC. Let

(Γ_{a_{1}}, Γ_{a_{2}}, ..., Γ_{a_{k}})

be the k-tuple consisting of all the SNRs at the destination that are less than T, where k≤K.

(2)

Find valid combinations in

(Γ_{a_{1}}, Γ_{a_{2}}, ..., Γ_{a_{k}})

. Let VC_m be the number of m-wise valid combinations found, where m ∈ [2, ω ] (i.e., there exists a ω-wise valid combination that is formed by the sum of most SNRs among all valid combinations). Starting from the smallest m, where VC_m > 0, the relay retransmits the network-coded packets corresponding to one of the m-wise valid combinations. Each of the network-coded packets is repeatedly retransmitted until its SNR exceeds Λ _NC.

(3)

For P _i, i ∈ [1,K] that are neither involved in any valid combinations nor received reliably at the destination, the relay retransmits

\hat{P_{i}}

until the SNR of

\hat{P_{i}}

exceeds Λ _i.

The implementation of TNCCR can be done as follows:

(1)

For P _i that is not correctly received at the destination, do the following: the destination broadcasts a NACK for the packet. Upon receiving the NACK of P _i, the relay checks whether Γ _i,SR<T _R,NC. If it is the case, then the relay sends a NACK, and the source will start retransmitting P _i. The source stops sending P _i if it receives an ACK from the relay (when Γ _i,SR≥T _R,NC) or an ACK from the destination (when Γ _i,SD≥T).

(2)

If there are still packets not correctly decoded at the destination, the destination will look for valid combinations. For the i th valid combination, the destination sends a signal requesting the corresponding network-coded packet(s) with specific indices to the relay. The relay will retransmit the corresponding network-coded packet until the SNR of that packet exceeds Λ _NC.

(3)

After receiving all the required network-coded packets correctly, the destination requests the relay for each of the packets that is neither involved in a valid combination nor received correctly.

3.2.3 Delay consideration

We now consider the average packet decoding delay[19] of different retransmission schemes, which is an important measure for applications where the sequence of decoding packets does not matter (i.e., multiple-description coding). We first give the definition of packet decoding delay:

Definition 2

The packet decoding delay of a source packet is the number of retransmissions before it is correctly decoded at the receiver.

The following example demonstrates how packet decoding delay is computed.

Example 1

Consider a relay network using TNCCR as its retransmission scheme, where K = 6, Γ₁ = Γ₂ = 0.5, Γ₃ = Γ₄ = Γ₅ = 1/3, Γ₆ = 0, and T = 1. Assume Γ_i,SR≥T_R,NC,∀i∈[1,6] and the retransmissions are error-free. The relay will retransmit the following packets in sequence: P₁ ⊕ P₂, P₃ ⊕ P₄, P₃ ⊕ P₅, and P₆. After the first retransmission, P₁ and P₂ can be decoded; therefore, the packet decoding delay for P₁ and P₂ is 1. To decode P₃, P₄, and P₅, the destination has to wait for 3 retransmissions (i.e., the retransmission of P₁ ⊕ P₂, P₃ ⊕ P₄, and P₃ ⊕ P₅), so the packet decoding delays for P₃, P₄, and P₅ are all equal to 3. The packet decoding delay for P₆ is 4.

In general, let the destination request retransmission of P 1 ′, P 2 ′,..., P n′, where P i′, i∈ [1,n] can be a source packet (i.e., P_r, r ∈ [1,K]) or a network-coded packet (i.e., P_r⊕P_k, r,k ∈ [1,K]). Upon reception of P i′, i ∈ [1,n], l_i source packets can be decoded. Let P i′, i∈ [1,n] requires μ_i retransmissions before being correctly received by the destination. Starting from i = 1, the destination will only request P i + 1 ′ if P i′ is received correctly. The total packet decoding delay is given as

l_{1} μ_{1} + l_{2} (μ_{1} + μ_{2}) + \dots + l_{n} \sum_{i = 1}^{n} μ_{i},

(16)

and the average packet decoding delay is

\frac{l_{1} μ_{1} + l_{2} (μ_{1} + μ_{2}) + \dots + l_{n} \sum_{i = 1}^{n} μ_{i}}{\sum_{i = 1}^{n} l_{i}},

(17)

where

\sum_{i = 1}^{n} l_{i}

is the number of source packets that can be decoded after receiving P 1 ′, P 2 ′,..., P n′.

Example 2.

Following Example 1, the average packet decoding delay of retransmitting P₁ ⊕P₂, P₃ ⊕P₄, P₃ ⊕P₅, and P₆ through error-free channels can be calculated as

\frac{2 \times 1 + 0 \times 2 + 3 \times 3 + 1 \times 4}{2 + 0 + 3 + 1} = 2.5,

suggesting that, on average, the receiver needs to wait for 2.5 retransmissions before decoding a packet.

Next, we show that under some specific conditions, the scheduling of retransmitting network-coded packets in TNCCR is optimum.

Proposition 1.

Assume that for each i ∈ 1,K, where Γ_i < T, Γ_i,SR ≥ T_R,NC, and only pairwise and three-wise valid combinations are considered. When the retransmissions are error-free, the scheduling of retransmitting packets in step 2 of TNCCR leads to the minimum average packet decoding delay.

Proof.

See Appendix 2. □

The general scheduling problem that minimizes the average packet decoding delay is however involved and is out of the scope of this paper. In the next section, we will discuss algorithms for finding valid combinations at the destination. The problem is in general hard and requires high computational complexity. We will show the complexity of the problem and then propose some efficient algorithms.

4 Algorithms searching for valid combinations

After step 1 in TNCCR, we still have k packets yet to be decoded at the destination. Without loss of generality, we assume P₁, P₂,..., P_k are still in error at the destination. The problem of finding the maximum number of valid combinations can be stated as follows:

\begin{align} given & W = {1, 2, ..., k}, Γ_{i} < T, i \in [1, k] \\ max & t, \\ subject to & t \in Z^{+}, \\ S_{1} \cup S_{2} \cup ... \cup S_{t} \cup ℬ = W, \\ S_{i} \cap S_{r} = \emptyset, 1 \leq i < r \leq t, \\ S_{k} \cap ℬ = \emptyset, 1 \leq k \leq t, \\ \sum_{i \in S_{r}} Γ_{i} \geq T, 1 \leq r \leq t, \end{align}

(18)

where

ℬ

is the set that contains indices of packets which cannot find themselves involved in any valid combinations. To illustrate an instance of the above problem, suppose Γ₁ = 1.5, Γ₂ = 1.2, Γ₃ = 0.8, Γ₄ = 0.5, Γ₅ = 0.2, and T = 2. One solution can be

S_{1} = {1, 4}

S_{2} = {2, 3}

, and

ℬ = {5}

, so that t = 2. This means that instead of retransmitting P₁, P₂,..., P₅, we can retransmit P₁ ⊕ P₄, P₂ ⊕ P₃, and P₅, such that t = 2 transmissions are saved.

The problem in (18) is actually equivalent to the bin-covering problem (or dual bin-packing problem) [20], where the bin-covering problem is defined as packing items of various sizes from a given set into bins so that the maximum number of bins are used, subject to the constraint that each bin must be filled to at least a given threshold. The problem is NP-hard, which means there is no polynomial-time algorithm available to solve it. The upper bound on t in (18) is

{Upperbound}_{# Valid_Comb.} = ⌊\frac{\sum_{i \in W} Γ_{i}}{T}⌋ .

(19)

It is easy to see that (19) gives the maximum number of valid possible combinations and sometimes overestimates it. For example, let Γ₁ = Γ₂ = 1.8, Γ₃ = 0.4, Γ₄ = 0.1, and t = 2. In this case, only one valid combination can be found in

W = {1, 2, 3, 4}

, while (19) gives the value 2.

Next, we develop polynomial-time algorithms for two simpler versions of the problem. We will demonstrate later that the number of valid combinations found in the simpler problems is not significantly smaller than the upper bound in (19).

4.1 Pairwise combinations only

We reduce the complexity of (18) by adding one more constraint, namely, we only concentrate on finding combinations of SNRs that involve two elements. The formal statement of the simpler problem is the following:

\begin{align} given & W = {1, 2, ..., k}, Γ_{i} < T, i \in [1, k], v = 2, \\ max & t, \\ subject to & S_{1} \cup S_{2} \cup ... \cup S_{t} \cup ℬ = W, \\ S_{i} \cap S_{r} = \emptyset, 1 \leq i < r \leq t, \\ S_{k} \cap ℬ = \emptyset, 1 \leq k \leq t, \\ \sum_{i \in S_{r}} Γ_{i} \geq T, 1 \leq r \leq t, \\ 1 < | S_{i} | \leq v, \forall i \in [1, t] . \end{align}

(20)

Before we develop algorithms for finding valid combinations, we first present a lemma that can help design efficient algorithms.

Lemma 1.

There is an optimum solution for (20), where

arg max_{i} {Γ_{i} | i \in W}

is involved in a valid combination, if there exists at least one valid combination.

Proof.

Let

l = arg max_{i} {Γ_{i} | i \in W}

. If there is an optimum solution that does not use l in any valid combination, then swapping l with any element involved in any valid combination found will not affect the optimality of the solution. □

Inspired by Lemma 1, we may first find a valid pairwise combination involving the largest element in

W

. If such a valid combination is found, we can start looking at the second largest element in

W

and try to find a valid combination involving it. The details of the algorithm are the following:

Algorithm 1 Find pairwise valid combinations

https://static-content.springer.com/image/art%3A10.1186%2F1687-1499-2013-136/MediaObjects/13638_2013_Article_713_Equb_HTML.gif

At the end of Algorithm 1, we can represent

W

W = S_{1} ⋃ S_{2} ⋃ ... ⋃ S_{c} ⋃ ℬ

, where

S_{i}, i \in [1, t_{1}]

is a set that contains indices of packets involved in a pairwise valid combination, and

| S_{i} | = 2

ℬ

is the set that contains indices of packets not involved in any pairwise valid combination.

Theorem 1.

Algorithm 1 maximizes t in (20).

Proof.

Assume that for a given

W

, there is at least one valid combination. Also, assume that

{Γ_{a_{1}}, Γ_{a_{q}}}

is found as a valid pairwise combination by Algorithm 1.

From Lemma 1, we know there is an optimum solution, where

Γ_{a_{1}}

is involved in a valid combination. Let

{Γ_{a_{1}}, Γ_{a_{p}}}

be a valid combination in the optimum solution. If a_p = a_q, then Algorithm 1 has found the valid combination in the optimum solution. Otherwise, if a_p ≠ a_q, from the mechanism of Algorithm 1,

Γ_{a_{q}}

will be the smallest element, such that

{Γ_{a_{1}}, Γ_{a_{q}}}

can form a valid combination, so that

Γ_{a_{p}} \geq Γ_{a_{q}}

. In this case, swapping

Γ_{a_{p}}

with

Γ_{a_{q}}

will not affect the optimality of the solution.

The analysis above is carried over to other valid combinations found by Algorithm 1 after

{Γ_{a_{1}}, Γ_{a_{q}}}

Since each valid combination chosen by Algorithm 1 does not affect the optimality of its final solution, we conclude that Algorithm 1 can find an optimum solution of (20) when v = 2. □

The complexity of Algorithm 1 is O (K logK), since the sorting in the second step has complexity of O (K logK) and other steps has complexity of O (K). It should be noted that when the retransmission is error-free and only pairwise valid combinations are considered, TNCCR with Algorithm 1 will have the least number of retransmissions it can ever achieve. The design of an optimum scheme when the retransmissions are subject to fading in terms of number of retransmissions is, however, involved and out of the scope of this work.

4.2 Pairwise and three-wise valid combinations

Now, we focus on the case where v = 3 in (20), which means we consider pairwise and three-wise combinations. We first prove that the decision version of the problem is NP-complete by reduction from a NP-complete problem called three-partition [21], and then discuss a heuristic algorithm for it.

The decision version of (20) can be stated as follows:

Instance: k numbers Γ₁,Γ₂,...,Γ_k and the corresponding indices set

W = {1, 2, ..., k}

, where Γ_i < T, i ∈ [1,k].

Question: Can we find at least

⌊ \frac{N}{v} ⌋

disjoint subsets of

W

such that the sum of the corresponding real numbers of each subset is larger or equal to T, where each subset consists at most v elements?

For future reference, we call this problem v-cardinality-constrained bin-covering (v-CCBC). The three-partition problem is described for ease of reference [21]:

Instance: A finite set

A

of 3m elements, a bound

B \in Z^{+}

, and a ‘size’

s (a) \in Z^{+}

for each

a \in A

, such that each s(a) satisfies

\frac{B}{4} < s (a) < \frac{B}{2}

and such that

\sum_{a \in A} s (a) = mB

Question: Can

A

be partitioned into m disjoint sets S₁,S₂,...,S_m, such that for

1 \leq i \leq m, \sum_{a \in S_{i}} s (a) = B

Theorem 2.

3-CCBC is NP-complete.

Proof.

We wish to solve the three-partition problem instance using the algorithm solving 3-CCBC. Let

W = 1, 2, ..., 3 m

, and Γ_i be s (a), where 1 ≤ i ≤ 3 m and

a \in A

. Also, let T = B. Then, solve the 3-CCBC problem. If the answer is YES, then we find m subsets of

W

\frac{B}{4} < Γ_{i} < \frac{B}{2}

, which implies that we can find m subsets of

A

of the three-partition problem satisfying the respective constraints. Similarly, if the answer is NO, then we cannot find m subsets of

A

that satisfy the constraints. The reduction from three-partition to 3-CCBC is obviously in polynomial time, so that 3-CCBC is NP-hard.

As an output of the algorithm of 3-CCBC can be verified in polynomial time, 3-CCBC is in NP. Thus, 3-CCBC is NP-complete. □

The above theorem implies that achieving the minimum number of retransmissions using TNCCR when the retransmissions are error-free and if pairwise and three-wise valid combinations are allowed would have exponential complexity, which is impractical to implement.

We now focus on solving 3-CCBC by a heuristic. The idea of the algorithm is the following: First, apply Algorithm 1 to find pairwise combinations. Then, let

U^{'}

be a set that contains elements in

W

that are not involved in any pairwise combinations, search for three-wise combinations in

U^{'}

. The searching for three-wise combinations similar to Algorithm 1 is as follows: We first search for a valid combination involving the largest element in

U^{'}

. Then, find two other elements Γ_i and Γ_r, such that the sum SNR of these two elements is the smallest, while the sum SNR of Γ_i, Γ_r, and the largest element is larger than or equal to T. The same approach is carried out until no more valid three-wise combinations can be found. The details of the algorithm for v = 3 is presented in Algorithm 2.

Algorithm 2 Find pairwise and three-wise valid combinations

https://static-content.springer.com/image/art%3A10.1186%2F1687-1499-2013-136/MediaObjects/13638_2013_Article_713_Equc_HTML.gif

In step 7 of Algorithm 2, Algorithm 1 can be used to find x₁ and x₂, such that

Γ_{x_{1}} + Γ_{x_{2}} \geq T - Γ_{b_{1}^{'}}

by changing the while-loop condition to ‘no valid combination found yet’ and T to

T - Γ_{b_{1}^{'}}

. After running Algorithm 2, we have

S_{1}, S_{2}, ..., S_{t_{1}}

, where each of them has indices of SNRs that form a valid pairwise combination.

S_{1}^{'}, S_{2}^{'}, ..., S_{t_{2}}^{'}

, where each of them has indices of SNRs that form a valid three-wise combination.

ℬ

contains indices that the corresponding SNRs are not involved in any valid combinations.

The complexity of the first step in Algorithm 2 is O (K logK). The complexity of the other steps is O (K²), since for each

Γ_{b_{i}^{'}}

, it takes a number of steps linear to K to complete step 7; step 7 can be executed for at most

⌊ \frac{K}{3} ⌋

times. So, in total, the complexity of Algorithm 2 is O (K²).

Figure 2 shows the number of valid combinations found by Algorithms 1 and 2, where K = 16. The upper bound on the number of valid combinations is also plotted. It can be seen that by executing Algorithm 1 or Algorithm 2, which are of very low complexity, near-upper bound performance can already be achieved.

Figure 3 displays the performance of TNCCR when the source-to-relay link and relay-to-destination link are noise-free. ε_th is set to be 10⁻³. Again, TNCCR with Algorithm 2 attains most of the gains which resulted from network coding.

In Figure 4, the upper bound on reduction of number of retransmissions using TNCCR is plotted when ε_th is still 10⁻³, and the transmission power over noise power is 12 dB. The upper bound on reduction of number of retransmissions can be calculated as

\frac{k - {Upperbound}_{# Valid_Comb.}}{k}

. It can be seen that the gain of TNCCR increases with the number of packets from the source.

5 Simulation results

In this section, we compare the performance of TCR and TNCCR by simulations. For TNCCR, Algorithm 2 is applied to search for valid combinations. We simulate the retransmission performance in two scenarios:

Scenario 1 (Scn-1): The relay is positioned closer to the source, as displayed in Figure 5a.

Scenario 2 (Scn-2): The relay is positioned at the middle point between the source and the destination, as displayed in Figure 5b.

In the simulations, we take path loss into account. The path loss (in dB) can be calculated as 10α log10(d), where α is the path loss exponent and is set to be 4, and d is the distance between the sender and the receiver. We set the distance between the source and the destination to be 1, and the relative distances of source-to-relay and relay-to-destination in the two scenarios are shown in Figure 5. In Scn-1, the average channel gain power of the source-to-relay channel is 20.915 dB larger than that of the source-to-destination channel, and the average channel gain power of the relay-to-destination channel is 6.196 dB larger than that of the source-to-destination channel. In Scn-2, the average channel gain power of the source-to-relay channel and the relay-to-destination channel are both 12.04 dB larger than that of the source-to-destination channel.

Figure 6 shows the performance comparisons between TCR and TNCCR in the aforementioned scenarios, where the percentages of reduction on the number of retransmissions using different relay retransmission schemes compared to the CC-ARQ scheme without relay are plotted. ε_th is set to be 10⁻³ and 10⁻⁴. Good threshold values for TCR and TNCCR in different situations, obtained through extensive simulations, are listed in Table 1. It can be seen that when the SNR is low, TCR and TNCCR have about the same performance. On the other hand, TNCCR has better performance when SNR is relatively high (7 dB or above). The implication of the observations is two-fold:

(1)

At low SNRs, where there are few valid combinations (as implied by Figure 2), there will be few retransmission of network-coded packets from the relay. In this case, TCR and TNCCR are more or less the same.

(2)

At high SNRs, the relay in TNCCR starts retransmitting more network-coded packets as there are more valid combinations. The results suggest that network-coded retransmissions are more efficient than non-network-coded retransmissions in the SNR region concerned.

Table 1

Threshold values at relay of different retransmission schemes in different scenarios

Threshold value	Scenario	Retransmission scheme	Threshold at relay
	Scn-1	TCR	12.10
ε_th=10⁻³		TNCCR	11.15
	Scn-2	TCR	10.20
		TNCCR	10.35
	Scn-1	TCR	15.48
ε_th=10⁻⁴		TNCCR	15.08
	Scn-2	TCR	14.38
		TNCCR	13.98

Figure 7 shows the performance of TNCCR scheme when the number of packets from the source varies. It can be seen that TNCCR can save more retransmissions if more packets from the source are to be transmitted, which is similar to the observation of Figure 4.

Figure 8 shows the average packet decoding delay of TCR and TNCCR schemes in Scn-2, where ε_th is set to be 10⁻³. The results indicate that TNCCR scheme has less average packet decoding delay than the TCR scheme, which means that the destination experiences smaller delay in the retransmission phase before decoding a source packet using TNCCR.

6 Conclusions

In this paper, we addressed the retransmission issue in DmF relay channels. We first designed a retransmission scheme based on a weighted combiner. By forwarding high-quality observations, the relay was able to help the system achieve high retransmission efficiency in low SNR region. Then, on top of the weighted combiner, another retransmission scheme based on both weighted combiner and network coding was proposed. The network-coded packets were formed according to the qualities of the previously erroneously received packets at the destination, and they were able to boost the retransmission efficiency at high SNR region.

A possible future direction based on this work may consider a more sophisticated retransmission scheme that is based on incremental-redundancy hybrid automatic repeat request or IR-HARQ, i.e., by considering whether or not the qualities of the packets at the destination can help the relay to decide how parity bits should be generated from which source packets so that system throughput can be increased.

The proposed scheme also has the potential to be applied in wireless broadcast channels. As it has been demonstrated in 3.2, a network-coded packet generated by considering the SNRs of the received packets at the destination can be used to decode two packets. If the SNRs of the received packets at the destination is not considered (i.e., treat packets in error as erasures), then a network-coded packet can only be used to decode one packet if it is instantly decodable [8]. It is therefore expected that the proposed network-coded retransmission scheme can result in higher throughput if the network-coded retransmissions are restricted to be instantly decodable. It is also interesting to investigate the possible performance improvement brought by the proposed scheme if a retransmitted packet is not required to be instantly decodable but innovative [9].

Appendices

Appendix 1

Extension to higher modulation schemes

We first demonstrate that network-coded retransmission can be applied when M-PSK modulation is used. We will see that the idea of network-coded retransmission presented in Section 3.2.1 is applicable when the signal constellation of the applied modulation scheme forms a group. From this observation, we can say that network-coded retransmission can also be applied to QAM, as the signals of QAM form a group [22].

M-PSK

Consider the following signal constellation of M-PSK, where each point in the constellation is given by e^{j 2π β/M} (where β∈ [0,M−1] and j² = −1).

Assume that two signals (namely

X_{1} = e^{j 2 π β_{1} / M}

and

X_{2} = e^{j 2 π β_{2} / M}

) are transmitted, where β₁, β₂ ∈ [0,M − 1]. The two signals are corrupted with additive noise (unlike the other sections where fading is present in the channel, here we only assume there is additive noise for simplicity) and the received signals are Y₁ = X₁ + n₁ and Y₂ = X₂ + n₂, respectively. We now wish to send a network-coded signal that can provide information about x₁ and x₂.

The M-PSK signal constellation can be related to the following finite Abelian group [23]:

U_{M} ≜ {e^{j 2 πβ / M}, β \in [0, M - 1]},

(21)

which is closed under the operation of complex multiplication. Let the inverse of x₁ and x₂ be −X₁ = e^{j 2π β 1 ′/M} and − X₂ = e^{j 2π β 2′/M}, respectively, where −a means the inverse of element a in a group and β 1 ′, β 2 ′ ∈ [0,M−1]. Denote • as complex multiplication. If the signal X₃ = (−X₁) • (−X₂) is delivered to the receiver without noise, then at the receiver we can have

\begin{align} X_{3} ∙ Y_{1} & = e^{j 2 π β_{1}^{'} / M} ∙ e^{j 2 π β_{2}^{'} / M} ∙ (e^{j 2 π β_{1} / M} + z_{1}) \\ = e^{j 2 π β_{2}^{'} / M} + e^{j 2 π β_{1}^{'} / M} ∙ e^{j 2 π β_{2}^{'} / M} ∙ z_{1} \\ = (- X_{2}) + e^{j 2 π β_{1}^{'} / M} ∙ e^{j 2 π β_{2}^{'} / M} ∙ z_{1} . \end{align}

(22)

We can see from (22) that an extra observation of x₂ can be obtained from X₃•Y₁. Similarly, an extra observation of x₁ can be obtained from X₃•Y₂. The MRC principle can then be applied to combine multiple noisy observations.

QAM

From the above discussion, it is evident that the network-coded retransmission scheme can be applied to a modulation scheme if the signals form a group. In [22], it has been proven that the signal constellation of

2^{2^{n}}

-QAM is given by the group of units in the quotient ring

Z [i] / 2^{n} + 2^{n} i

, where n is a positive integer and

Z [i]

means Gaussian integers ring. Similar derivations to (22) can be used to show that the network-coded retransmission is applicable to QAM signals.

Appendix 2

Proof of proposition 1

Let the relay retransmit P 1′, P 2′,..., P x′ through an error-free channel to the destination, where upon receiving P i′, i∈[1,x], l_i source packets can be decoded at the destination. Since we only consider pairwise and three-wise valid combinations, l_i∈{0,1,2,3}.

Lemma 2.

Let Γ_α,SD, Γ_β,SD, and Γ_γ,SD form a three-wise valid combination and, in order to decode source packets, P_α, P_β, P_γ, P i′, and P r′ should be retransmitted, where i, r∈[1,x]. Then, a retransmission sequence which retransmits P i′ followed by P r′ has smaller average packet decoding delay than a retransmission sequence which retransmits other packets in between P i′ and P r′.

Proof.

Let i, r, a₁, a₂,..., a_n∈ [1,x]. Consider the following three retransmission sequences:

(1)

P i′,

P_{a_{1}}^{'}

P_{a_{2}}^{'}

,...,

P_{a_{n}}^{'}

, P r ′

(2)

P i ′, P r ′,

P_{a_{1}}^{'}

P_{a_{2}}^{'}

,...,

P_{a_{n}}^{'}

(3)

P_{a_{1}}^{'}

P_{a_{2}}^{'}

,...,

P_{a_{n}}^{'}

, P i ′, P r ′

Let the total packet decoding delay of sequences (1), (2), and (3) be d₁, d₂, and d₃, respectively. We have

\begin{align} d_{1} & = 1 \times 0 + 2 l_{a_{1}} + 3 l_{a_{2}} + \dots + (a_{n} + 1) l_{a_{n}} + (a_{n} \\ + 2) 3, \\ d_{2} & = 1 \times 0 + 2 \times 3 + 3 l_{a_{1}} + 4 l_{a_{2}} + \dots + (a_{n} + 2) l_{a_{n}} \\ = 2 \times 3 + 2 l_{a_{1}} + 3 l_{a_{2}} + \dots + (a_{n} + 1) l_{a_{n}} + l_{a_{1}} \\ + l_{a_{2}} + \dots + l_{a_{n}}, \\ d_{3} & = l_{a_{1}} + l_{a_{2}} + \dots + l_{a_{n}} + (a_{n} + 1) \times 0 + (a_{n} + 2) 3 . \end{align}

It is obvious that d₃ ≤ d₁. To see d₂ ≤ d₁, observe that

d_{1} - d_{2} = 3 a_{n} - (l_{a_{1}} + l_{a_{2}} + \dots + l_{a_{n}}) .

Since l_i∈ {0,1,2,3}, ∀i ∈ {a₁,a₂,...,a_n},

l_{a_{1}} + l_{a_{2}} + \dots + l_{a_{n}} \leq 3 a_{n}

. Therefore, d₁ − d₂ ≥ 0.

As the number of source packets that can be decoded after receiving each of the three sequences is the same, sequence (1) gives the largest average packet decoding delay. □

Lemma 3.

Let

l_{a_{1}} = 2

and

l_{a_{2}} = 1

, where a₁,a₂ ∈ [1,x]. Then, retransmitting

P_{a_{1}}^{'}

followed by

P_{a_{2}}^{'}

has smaller average packet decoding delay than retransmitting

P_{a_{2}}^{'}

followed by

P_{a_{1}}^{'}

Proof.

The average packet decoding delay of retransmitting

P_{a_{1}}^{'}

followed by

P_{a_{2}}^{'}

can be calculated as

\frac{1 \times 2 + 2 \times 1}{2 + 1} = \frac{4}{3}

. The average packet decoding delay of retransmitting

P_{a_{2}}^{'}

followed by

P_{a_{1}}^{'}

can be calculated as

\frac{1 \times 1 + 2 \times 2}{1 + 2} = \frac{5}{3}

. The lemma then follows. □

Lemma 4.

Let

l_{a_{1}} = 2

l_{a_{2}} = 0

, and

l_{a_{3}} = 3

so that three source packets can be decoded upon receiving

P_{a_{2}}^{'}

and

P_{a_{3}}^{'}

. Then, retransmitting

P_{a_{1}}^{'}

first gives smaller average packet decoding delay than retransmitting

P_{a_{2}}^{'}

and

P_{a_{3}}^{'}

first.

Proof.

The average packet decoding delay of sending

P_{a_{1}}^{'}

first is

\frac{1 \times 2 + 2 \times 0 + 3 \times 3}{2 + 0 + 3} = 2.2

. The average packet decoding delay of sending

P_{a_{2}}^{'}

and

P_{a_{3}}^{'}

first is

\frac{1 \times 0 + 2 \times 3 + 3 \times 2}{0 + 3 + 2} = 2.4

. The lemma then follows. □

Lemma 5.

Let

l_{a_{1}} = 0

l_{a_{2}} = 3

, and

l_{a_{3}} = 1

so that three source packets can be decoded upon receiving

P_{a_{1}}^{'}

and

P_{a_{2}}^{'}

. Then, retransmitting

P_{a_{1}}^{'}

and

P_{a_{2}}^{'}

first gives smaller average packet decoding delay than retransmitting

P_{a_{3}}^{'}

first.

Proof.

The average packet decoding delay of sending

P_{a_{1}}^{'}

and

P_{a_{2}}^{'}

first is

\frac{1 \times 0 + 2 \times 3 + 3 \times 1}{0 + 3 + 1} = 2.25

. The average packet decoding delay of sending

P_{a_{3}}^{'}

first is

\frac{1 \times 1 + 2 \times 0 + 3 \times 3}{0 + 3 + 1} = 2.5

. The lemma then follows. □

The above lemmas together suggest the following: To minimize the average packet decoding delay in error-free retransmissions, network-coded packets (each of which can be used to decode two source packets) should be retransmitted first, followed by pairs of network-coded packets (each of which can be used to decode three source packets), followed by source packets. Therefore, TNCCR gives the minimum average packet decoding delay when the retransmissions are error-free and for each Γ_i,SD < T, Γ_i,SR ≥ T_R,NC, where i ∈ [1,K]. That proves Proposition 1.

Acknowledgements

This work was partially supported by a grant from the University Grants Committee of the Hong Kong Special Administrative Region, China (Project No.: AoE/E-02/08). Part of the work was presented in Wireless Advanced 2011.

Open AccessThis article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Competing interests

Both authors declare that they have no competing interests.

Vorheriger Artikel Exploring random access and handshaking techniques in underwater wireless acoustic networks

Nächster Artikel Mobile multicast source support in PMIPv6 networks

Authors’ original submitted files for images

Below are the links to the authors’ original submitted files for images.

Authors’ original file for figure 1

Authors’ original file for figure 2

Authors’ original file for figure 3

Authors’ original file for figure 4

Authors’ original file for figure 5

Authors’ original file for figure 6

Authors’ original file for figure 7

Authors’ original file for figure 8

Akyildiz IF, Gutierrez-Estevez DM, Reyes EC: The evolution to 4G cellular systems: Lte-advanced. Phys. Commun 2010, 3(4):217-244. 10.1016/j.phycom.2010.08.001CrossRef

Laneman J, Tse D, Wornell G: Cooperative diversity in wireless networks: efficient protocols and outage behavior. IEEE Trans. Inf. Theory 2004, 50(12):3062-3080. 10.1109/TIT.2004.838089MathSciNetCrossRef

Wang TR, Cano A, Giannakis GB, Laneman JN: High-performance cooperative demodulation with decode-and-forward relays. IEEE Trans. Commun 2007, 55(7):1427-1438.CrossRef

Borade S, Zheng L, Gallager R: Amplify-and-forward in wireless relay networks: rate, diversity, and network size. IEEE Trans. Inf. Theory 2007, 53(10):3302-3318. 10.1109/TIT.2007.904774MathSciNetCrossRef

Ahlswede R, Cai N, Li SYR, Yeung RW: Network information flow. IEEE Trans. Inf. Theory 2000, 46(4):1204-1216. 10.1109/18.850663MathSciNetCrossRef

Nguyen D, Tran T, Nguyen T, Bose B: Wireless broadcast using network coding. IEEE Trans. Vehicular Technol 2009, 58(2):914-925. 10.1109/TVT.2008.927729CrossRef

Keller L, Drinea E, Fragouli C: Online Broadcasting with Network Coding. Fourth Workshop on NetCod 2008, 1-6. NETCOD.2008.4476183

Sadeghi P, Shams R, Traskov D: An optimal adaptive network coding scheme for minimizing decoding delay in broadcast erasure channels. Eurasip J.Wireless Commun. Netw 2010. 10.1155/2010/618016

Kwan HY, Shum K, Sung CW: Generation of innovative and sparse encoding vectors for broadcast systems with feedback. IEEE ISI Proc 2011, 1161-1165. ISIT.2011.6033715

10.

Li QA, Ting SH, Ho CK: Nonlinear network code for high throughput broadcasting with retransmissions. IEEE ISIT 2009, 2853-2857. ISIT.2009.5205268

11.

Zhi C, Wei C, Fan PY, Ben Letaief K: Relay Aided Wireless Multicast Utilizing Network Coding: Outage Behaviour and Diversity Gain. IFIP International Conference on NPC 2008, 358-364. 10.1109/NPC.2008.22

12.

Fan PY, Zhi C, Wei C, Ben Letaief K: Reliable relay assisted wireless multicast using network coding. IEEE J. Selected Areas Commun 2009, 27(5):749-762.CrossRef

13.

Vien QT, Tran LN, Hong EK: Network coding-based retransmission for relay aided multisource multicast networks. Eurasip J. Wireless Commun. Netw 2011, 2011: 643920.CrossRef

14.

Yune TW, Kim D, Im GH: Opportunistic network-coded cooperative transmission with demodulate-and-forward protocol in wireless channels. IEEE Trans. Commun 2011, 59(7):1791-1795. TCOMM.2011.050911.090660CrossRef

15.

Tse D, Viswanath P: Fundamentals of Wireless Communication. New York: Cambridge University Press; 2005.CrossRef

16.

Chase D: Code combining–a maximum-likelihood decoding approach for combining an arbitrary number of noisy packets. IEEE Trans. Commun 1985, 33(5):385-393. TCOM.1985.1096314MathSciNetCrossRef

17.

Proakis JG: Digital Communications. New York: McGraw-Hill; 1995.

18.

Bletsas A, Khisti A, Reed DP, Lippman A: A simple cooperative diversity method based on network path selection. IEEE J. Selected Areas Commun 2006, 24(3):659-672.CrossRef

19.

Sadeghi P, Yu M: Instantly decodable versus random linear network coding: a comparative framework for throughput and decoding delay performance. CoRR 2012. arXiv:1208.2387v1

20.

Assmann SF, Johnson DS, Kleitman DJ, Leung JYT: On a dual version of the one-dimensional bin packing problem. J. Algorithms 1984, 5(4):502-525. 10.1016/0196-6774(84)90004-XMathSciNetCrossRef

21.

Garey MR, Johnson DS: Computers and intractability : a guide to the theory of NP-completeness. San Francisco: W.H. Freeman; 1979.

22.

Rifa J: Groups of complex integers used as qam signals. IEEE Trans. Inf. Theory 1995, 41(5):1512-1517. 10.1109/18.412699MathSciNetCrossRef

23.

Kschischang FR, Debuda PG, Pasupathy S: Block coset codes for m-ary phase-shift keying. IEEE J. Selected Areas Commun 1989, 7(6):900-913. 10.1109/49.29613CrossRef

Titel: Network-coded retransmissions in wireless demodulate-and-forward relay channels
verfasst von: Ye Liu
Chi Wan Sung
Publikationsdatum: 01.12.2013
Verlag: Springer International Publishing
Erschienen in: EURASIP Journal on Wireless Communications and Networking / Ausgabe 1/2013
Elektronische ISSN: 1687-1499
DOI: https://doi.org/10.1186/1687-1499-2013-136

Springer Professional

Abstract

Electronic supplementary material

Competing interests

1 Introduction

1.1 Motivation and contribution

1.2 Notations

2 System model

3 Proposed retransmission schemes

3.1 Cooperative retransmission

3.2 Network-coded cooperative retransmission

3.2.1 Network-coded retransmission

Definition 1.

3.2.2 Network-coded retransmission in DmF relay networks

3.2.3 Delay consideration

Definition 2

Example 1

Example 2.

Proposition 1.

Proof.

4 Algorithms searching for valid combinations

4.1 Pairwise combinations only

Lemma 1.

Proof.

Algorithm 1 Find pairwise valid combinations

Theorem 1.

Proof.

4.2 Pairwise and three-wise valid combinations

Theorem 2.

Proof.

Algorithm 2 Find pairwise and three-wise valid combinations

5 Simulation results

6 Conclusions

Appendices

Appendix 1

Extension to higher modulation schemes

M-PSK

QAM

Appendix 2

Proof of proposition 1

Lemma 2.

Proof.

Lemma 3.

Proof.

Lemma 4.

Proof.

Lemma 5.

Proof.

Acknowledgements

Competing interests

Authors’ original submitted files for images

Weitere Artikel der Ausgabe 1/2013

A context-aware framework for the efficient integration of femtocells in IP and cellular infrastructures

Coordinated TDD-Underlay for Self-organizing Femtocells in Two-Tier Coexistence Scenarios

Throughput analysis of buffer-constrained wireless systems in the finite blocklength regime

A PAPR reduction scheme with residue number system for OFDM

Improved differential fault analysis on lightweight block cipher LBlock for wireless sensor networks

Automated uplink power control optimization in LTE-Advanced relay networks

Premium Partner