IEEE LATIN AMERICA TRANSACTIONS, VOL. 8, NO. 4, AUG. 2010
417
Hybrid ARQ with Partial Retransmissions and
LDPC codes and its Impact on TCP
André Gustavo Degraf Uchôa, Member, IEEE, Richard Demo Souza
and Marcelo Eduardo Pellenz
Abstract— The design of a novel HARQ scheme using LDPC
codes, partial retransmissions, and diversity combining is
presented. The theoretical throughput of the proposed scheme is
estimated by means of EXIT charts. It is shown that the proposed
method outperforms the classical equal gain combining (EGC)
method while requiring few more overall decoding iterations.
The transmission control protocol (TCP) performance when the
proposed method is used in the physical layer is also investigated.
Simulation results show that the gains with respect to the
classical EGC scheme can be as large as 3.5 dB.
Keywords—
Hybrid
ARQ,
LDPC
Retransmissions, Diversity Combining, TCP.
P
codes,
Partial
I. INTRODUÇÃO
ADRÕES modernos de comunicação sem fio estão
incluindo o suporte a mecanismos de HARQ [1]. HARQ
combina sistemas convencionais de pedido de retransmissão
automático (ARQ) com códigos corretores de erros (FEC). Em
sistemas ARQ, quando houver uma transmissão que tenha
sido corrompida, o receptor poderá fazer um pedido de
retransmissão para obter a informação livre de erros.
Mecanismos de ARQ utilizam apenas um código detector de
erros, por exemplo, um código de verificação de redundância
cíclica (CRC). Num sistema com ARQ, o transmissor envia
uma nova palavra apenas após receber um acknowledgement
(ACK) do receptor. Caso a palavra recebida pelo receptor
estiver errada, este enviará um negative acknowledgement
(NACK), o qual fará com que o transmissor reenvie a mesma
palavra. Geralmente é utilizado um limite máximo de
retransmissões [1]. Os métodos de ARQ puros apenas
consideram o uso de um código detector de erros como, por
exemplo, um CRC. No entanto, ao adicionar um código FEC
para corrigir ou minimizar os erros no pacote recebido obtémse um mecanismo do tipo HARQ. Esta técnica apresenta um
ganho substancial de desempenho, pois diminui a quantidade
de retransmissões, e é denominada de HARQ Tipo I [1]. Em
aplicações tais como transmissões de pacotes de dados em
dispositivos móveis e sistemas via satélite, os mecanismos de
HARQ mostram ser vantajosos [2]. Alguns exemplos de
Este trabalho foi parcialmente financiado pelo CNPq (Brasil), sobre os
projetos de número 562164/2008-1, 143460/2008-0 e 303181/2007-9.
André Gustavo Degraf Uchôa e Richard Demo Souza, Programa de PósGraduação em Engenharia Elétrica e Informática Industrial – CPGEI da
Universidade Tecnológica Federal do Paraná – UTFPR, Curitiba, Paraná,
Brasil (e-mail.: [email protected], [email protected]).
Marcelo Eduardo Pellenz, Programa de Pós-Graduação em Informática –
PPGIa da Pontifícia Universidade Católica do Paraná – PUCPR, Curitiba,
Paraná, Brasil (e-mail.: [email protected]).
padrões modernos de comunicação sem fio que usam HARQ
são, IEEE 802.16e (WiMax) [3], IEEE 802.11n (WiFi) [4].
Padrões recentes de comunicação celular também estão
utilizando esquemas HARQ. Uma das mais importantes
características do CDMA2000 1xEV-DO é a inclusão de
esquemas HARQ, tanto no canal de transmissão direto como
no canal de retorno [2,5,6]. Outros dois padrões de
comunicação celular que utilizam HARQ são High Speed
Downlink Packet Access (HSDPA) [7] e o Long Term
Evolution (LTE) [8].
Existem três tipos de esquemas HARQ. No HARQ Tipo I
os pacotes codificados dos dados são tratados como num ARQ
convencional [1], [9]. O código FEC aumenta a probabilidade
de uma transmissão com sucesso, e assim a vazão
(throughput) total. Além disso, combinação por diversidade
(DC) pode ser aplicada entre os pacotes recebidos de modo a
aumentar o throughput [1], num método conhecido também
como Chase combining [10]. HARQ Tipo II é um esquema de
ARQ com redundância incremental (IR) que transmite
diferentes bits codificados em diferentes transmissões. O
HARQ Tipo II atinge um alto desempenho em termos de
throughput pelo fato de adaptar a redundância do FEC
conforme a variação das condições do canal [2]. HARQ Tipo
III é outro tipo de esquema de IR ARQ, também chamado de
IR Parcial. As diferenças entre HARQ Tipo II e Tipo III é que
no Tipo III as informações de redundância são autodecodificáveis [1], [9]. Além do mais, também é possível
projetar métodos que combinem características de ambos DC
e IR, como o esquema proposto em [11] o qual trabalha como
um método Tipo II na primeira retransmissão e como um
esquema Tipo I nas outras retransmissões.
Existem muitas comparações entre IR e DC que podem ser
encontradas na literatura, tais como [8], [12] - [17]. É
esperado que métodos de IR deveriam superar técnicas de DC,
uma vez que DC's são apenas uma forma de código de
repetição. Entretanto, tais comparações demonstram que sobre
várias condições práticas DC possui desempenho próximo ao
IR. Em [13], [17] vários cenários considerando HSDPA foram
investigados. Foram considerados cenários que comparavam o
IR com o DC para FEC de baixa e alta taxa, e modulações de
baixa e alta ordem. Os autores concluem que para canais
estáticos, utilizar códigos de alta taxa e alta modulação com
IR, apresenta um desempenho melhor que o DC. Contudo,
para cenários onde a mobilidade dos dispositivos móveis é alta
(canais com desvanecimento) o IR apresenta um desempenho
marginalmente superior ao DC. Além disso, quando utilizam
modulações de baixa ordem e códigos de taxa baixa,
novamente o DC torna-se mais vantajoso que o IR.
418
Os autores de [17] ainda ressaltam que para dispositivos
que utilizem o HSDPA em cenários reais o DC é melhor que o
IR, uma vez que o DC requer uma complexidade de circuito
menor e também um uso de memória menor que para o IR.
Em [12], cenários considerando LTE utilizando Orthogonal
Frequency Division Multiplexing Access (OFDM) são
investigados, onde se observa que para casos de modulações
de baixa ordem e FEC com taxa baixa a diferença entre IR e
DC é reduzida significativamente. Além disso, os autores
argumentam que para cenários onde o custo de memória e
complexidade de decodificação são considerados, o uso do
DC torna-se mais vantajoso que o IR pela facilidade de
implementação em dispositivos móveis.
Em [14], é apresentado que no caso de canais com
desvanecimento, técnicas de DC podem ser uma melhor
solução do que IR. Esta conclusão ocorre quando se considera
um canal com uma variação muito grande de relação sinal
ruído (SNR). Se os bits sistemáticos forem corrompidos pelo
canal, as retransmissões dos bits de redundância não ajudarão
no desempenho do sistema. No entanto, no DC os bits
sistemáticos são enviados em todas as retransmissões, assim,
em tal cenário o DC se torna melhor que o IR. Em [15], [16] o
impacto de utilizar IR e DC em sistemas sem fio usando
Multiple-Input Multiple-Output (MIMO) é investigado. Os
autores concluem que em alguns casos esquemas DC podem
superar métodos de IR.
De forma geral, um decodificador IR requer um buffer
maior e opera sempre na menor taxa de código FEC
suportada, que resulta em um aumento de complexidade
computacional quando comparado com métodos DC. Como
resultado, um buffer de tamanho grande e um FEC com taxa
muito baixa implicará num circuito grande, requerendo mais
consumo de energia do que em esquemas DC. Tanto para
dispositivos móveis como para dispositivos de comunicação
portáteis, tais tipos de características são indesejáveis.
Padrões modernos de comunicação sem fio tendem a incluir
o uso dos códigos LDPC como FEC, como o caso do padrão
IEEE 802.16e. Os códigos LDPC foram propostos por
Gallager em 1960 na sua dissertação de doutorado [18]. Em
1981 Tanner desenvolveu um método que permitia visualizar
os códigos LDPC através de grafos [19]. Na década de 90 os
códigos LDPC foram redescobertos por Mackay [20], [21],
demonstrando que estes códigos poderiam ser excelentes
códigos corretores de erros em aplicações práticas. Muitas
técnicas para construir códigos LDPC foram propostas desde
então e elas podem ser encontradas na literatura [9].
Muitos trabalhos foram feitos em HARQ usando códigos
LDPC. Por exemplo, em [22] um método que considera os
graus de distribuição de um código LDPC é proposto. Antes
da retransmissão ser requisitada, todo o pacote é reordenado
em ordem decrescente dos graus dos nós. Este pacote
reordenado é dividido em vários sub-pacotes com
comprimento igual. Quando as retransmissões se fazem
necessárias, o transmissor envia um sub-pacote de cada vez
em ordem decrescente dos graus, enquanto que o receptor
combina os sub-pacotes retransmitidos. Por sua vez, em [23]
os nós são também divididos em vários sub-pacotes baseados
na distribuição de graus. Entretanto, cada sub-pacote contém
IEEE LATIN AMERICA TRANSACTIONS, VOL. 8, NO. 4, AUG. 2010
apenas nós com o mesmo grau, o qual é diferente da estratégia
em [22]. Se retransmissões são requeridas, o transmissor envia
sub-pacotes em ordem decrescente do maior grau para o
menor grau. Como resultado, ambos throughput e atraso
foram melhorados com respeito à [22]. Em [24] um esquema
de HARQ baseado em confiabilidade foi proposto. Se uma
decodificação errada é detectada, o receptor analisa a
confiabilidade de cada símbolo através de suas razões de
verossimilhança logarítmica (LLR's). Se alguns símbolos
estão abaixo de um limiar, então o receptor requisita a
retransmissão destes símbolos. A principal desvantagem deste
método é que a mensagem para requisitar uma retransmissão
deve ter o mesmo comprimento que a palavra codificada
original, que é muito mais do que uma mensagem normal de
ACK ou NACK. Em [25] um método baseado na média da
confiabilidade de cada linha da matriz de check de paridade é
proposto. Se uma retransmissão é necessária, o receptor
requisita apenas os símbolos da linha da matriz com menor
confiabilidade. Por meio disso, o método proposto melhora o
throughput e também o atraso com respeito à proposta em
[24]. Todas estas propostas [22] - [25] aplicam DC no
receptor. Outra área de estudo em técnicas de HARQ usando
códigos LDPC como FEC são os métodos baseados em IR,
como por exemplo [26].
Neste artigo nós consideramos uma restrição de projeto que
é manter o receptor HARQ tão simples quanto possível, mas
com um bom desempenho. Tomando como base os resultados
de [12], [13] e [17], esta restrição pode ser descrita como um
decodificador operando sobre uma taxa fixa e com um buffer
de mesmo tamanho do pacote inicial transmitido.
Entretanto, o foco deste artigo é em esquemas DC. Assim
sendo, o objetivo deste artigo foi projetar um método DC que
utilize códigos LDPC o qual supere um receptor que é
baseado em EGC, que também pode ser chamado no receptor
de DC Típico [1]. No decorrer das análises e estudos obtevese um método mais eficiente em termos de throughput do que
o EGC.
O método apresentado neste trabalho é baseado em
retransmissões parciais e combinação por diversidade (DC).
Análises de Extrinsic Information Transfer charts (EXIT
charts) mostram que a estratégia proposta supera métodos DC
convencionais. Simulações computacionais verificam os
resultados obtidos através das análises de EXIT charts, e
demonstram um bom desempenho no canal AWGN. Nas
simulações utilizaram-se códigos LDPC do padrão IEEE
802.16e [3], mas o método também pode ser usado com outros
códigos LDPC. Uma análise cross layer, considerando o uso
do método proposto e o TCP, mostra os potenciais ganhos
práticos da nossa proposta.
O restante deste artigo está organizado da seguinte forma.
Na Seção II, nós definimos o modelo do sistema, enquanto na
Seção III é discutido o uso das EXIT charts para analisar
esquemas de HARQ com DC. A Seção IV descreve o método
proposto. Resultados numéricos baseados em simulações
computacionais e análises de EXIT charts são apresentados na
Seção V. O desempenho do TCP, quando o método proposto é
usado na camada física, é investigado na Seção VI.
Finalmente, a Seção VII conclui o artigo.
UCHÔA et al.: LATINCON09 - HYBRID ARQ WITH PARTIAL
419
Considere um sistema de comunicação com um canal direto
e de retorno. Nas simulações considerou-se que o canal direto
é modelado como um canal AWGN com uma densidade
. O canal de retorno é considerado
espectral de potência
sem ruído. A Fig. 1 mostra graficamente o canal direto e de
retorno. No modelo proposto, o objetivo é transmitir um bloco
de tamanho
bits equiprováveis e independentes,
, usando modulação Binary Phase-Shift
Keying (BPSK), através do canal. Os bits são codificados por
um codificador LDPC antes da transmissão, assim
. A taxa do código é definida como
R = k / n . O receptor estima a saída dos bits de informação
transmitidos .
é definido como
, onde
O throughput
é o valor esperado, e
é o número total de bits transmitidos,
tal que os
bits de informação são corretamente
decodificados [1]. Note que, para o caso de não haver erros
depois da decodificação da primeira transmissão, o throughput
é igual à taxa do código
, uma vez que bits foram
aceitos depois da transmissão de
bits. Sem perda de
generalidade, os esquemas ARQ simulados utilizam o
protocolo stop-and-wait. Assume-se que os erros podem ser
perfeitamente detectados pelo receptor.
u
Transmissor
AWGN
Receptor
û
Canal de Retorno
Figura 1: Modelo do Sistema
III. EXIT CHARTS E COMBINAÇÃO POR DIVERSIDADE
As EXIT charts caracterizam a operação iterativa do
decodificador e foram primeiramente propostas por Stephan
Ten Brink [27], construindo assim o conceito de informação
extrínseca. Defina
como a informação a priori dos nós
variáveis,
a informação extrínseca provinda dos nós
variáveis,
a informação a priori dos nós de check de
paridade, e
como a informação extrínseca dos nós de
check de paridade. Então, para o caso de um código LDPC
irregular e um canal AWGN e modulação BPSK, as funções
EXIT são definidas como [27]:
(1)
SNR observada no receptor
, o qual por sua vez aumenta
. Além disso, para o caso de esquemas HARQ Tipo I com
combinação, a retransmissão tem o efeito de aumentar o valor
de
visto pelo receptor. Para um código LDPC irregular
que é parte de um esquema de HARQ Tipo I em um canal
AWGN usando um método ótimo de DC no receptor, o qual
neste caso é o EGC,
pode ser escrita como:
(3)
é o número de transmissões de um dado pacote (por
onde
significa que a primeira transmissão e duas
exemplo,
retransmissões foram feitas para este pacote). A função EXIT
não muda uma vez que não depende de
.
Através da Fig. 2, que considera um código LDPC de taxa
do
padrão
IEEE
802.16e,
considerando o método EGC no receptor
dB e
. Para este código em particular
,
,
,
, e
. Pode-se
ver claramente que o desempenho do decodificador aumenta
com o número de transmissões, tal que a curva
,
está
,
depois da terceira transmissão.
sempre acima da curva
Tal condição corresponde a uma decodificação com sucesso de
um pacote para aquele valor de
[27]. Além do mais, uma
vez que as análises de EXIT charts mostram que a curva
,
está sempre acima da curva
,
apenas depois da
terceira transmissão, então pode-se estimar o throughput para
este valor de
como
. Note que
através das equações (2) e (3) pode-se determinar o valor
mínimo de
para um dado número de transmissões
de forma que a curva
,
está sempre acima da curva
,
. Assim, pode-se estimar o throughput sem recorrer a
simulações computacionais que exijam um tempo muito grande.
Pelo que se conhece tal estimação de throughput teórico usando
EXIT charts não é encontrada na literatura.
1
0.9
0.8
0.7
0.6
Iev,Iac
II. MODELO DO SISTEMA
IEv TX=3
0.5
IEv TX=2
0.4
IEv TX=1
0.3
(2)
e
representam a fração de arestas incidentes nos nós
onde
variáveis e nos nós de check de paridade de graus
e ,
respectivamente,
e
são o grau máximo dos nós variáveis
e de check,
,e
é a energia por bit de
informação. As funções e
são detalhadas em [27].
é melhorado pelo aumento da
De (1) pode-se ver que
IAc
0.2
0.1
0
0
0.1
0.2
0.3
0.4
0.5
Iav,Iec
0.6
0.7
0.8
0.9
1
Figura 2: Curvas Exit para o IEEE 802.16e código LDPC taxa 1/2 com o EGC
em canal AWGN,
e
dB.
420
IEEE LATIN AMERICA TRANSACTIONS, VOL. 8, NO. 4, AUG. 2010
A Fig. 3 apresenta o throughput previsto através de EXIT
charts e o throughput simulado. Nas simulações realizadas, foi
(4)
considerado um máximo de 50 iterações de decodificação, e no
máximo 8 retransmissões. As diferentes regiões com
throughput constante na curva teórica da Fig. 3 são associadas
com diferentes números de transmissões requeridas, como
apresentado na figura. Por exemplo, na segunda região da
direita para a esquerda, a qual corresponde à um throughput de
0.25, as análises de EXIT charts estimaram que
transmissões são necessárias para aquela faixa de
para
que o pacote seja decodificado corretamente (assim, o valor
teórico de throughput é
). Observa-se
que, existe uma boa correlação entre o throughput estimado e o
simulado. Existem algumas pequenas diferenças entre os
resultados teóricos e simulados apenas na transição entre os
diferentes valores de throughput estimados. Isto ocorre porque
nestes pontos, embora a análise de EXIT charts mostre que
seria possível conseguir aquele throughput (ou que um
determinado número
de transmissões seria suficiente), nas
simulações de computador, em alguns casos, os pacotes foram
decodificados com
transmissões e algumas outras vezes
com
transmissões.
Percebemos
que
esse
comportamento é afetado tanto pela taxa do código como pelo
comprimento do bloco.
EGC - Teórico
EGC - Simulado
0.5
Throughput
0.4
0.3
Note que a partir do passo 2 o comprimento dos pacotes
retransmitidos é constante, tanto quanto o fator de ganho de
magnitude, e estes parâmetros não dependem da taxa do código.
Além do mais, os sub-pacotes recebidos são sempre
combinados com os pacotes previamente recebidos.
A função EXIT
para o método proposto CRL é definida
em (4), onde
são as frações dos nós com grau i que
estão na primeira, segunda e terceira retransmissão,
respectivamente. A Tab. I lista os valores de
para o
código do IEEE 802.16e de taxa
.
TABELA I
0.2
VALORES DE
USADOS NO MÉTODO PROPOSTO.
R = 5/6
0.1
0
-7
,
,
e
.
Este método envia a cada retransmissão um terço dos
símbolos originais . Controle de potência e combinação por
diversidade são aplicados. Por exemplo, considere o caso de um
código com
e modulação BPSK. O método segue os
seguintes passos:
1. Na primeira transmissão o sistema opera como usual,
transmitindo todo o pacote de símbolos;
2. Se uma segunda retransmissão é necessária, então o
transmissor envia os primeiros 768 símbolos com
um fator de ganho de magnitude de
;
3. Se uma segunda retransmissão é requerida, o método
envia os próximos 768 símbolos com o mesmo fator
de ganho;
4. Se uma terceira retransmissão for necessária, o
transmissor envia os últimos 768 símbolos
novamente com o mesmo fator de ganho;
5. Se mais retransmissões se fizerem necessárias, o
método repete à partir do passo 2.
i
-6
-5
-4
-3
-2
Eb/N0 (dB)
-1
0
1
2
Figura 3: Throughput estimado e simulado para o IEEE 802.16e código de taxa
1/2 com o EGC em canal AWGN.
IV. MÉTODO PROPOSTO
Nesta seção determina-se as funções EXIT, num canal
AWGN, para o esquema proposto de HARQ e compara o seu
desempenho em termos de throughput, com o objetivo de
projetar um esquema que supere o EGC. Nos resultados
numéricos utilizou-se o código LDPC irregular do IEEE
802.16e com taxa
. Para este código em particular
4
0
0.636
0.364
3
0.8
0.1
0.1
2
0
0
1
Uma desvantagem que o método proposto apresenta com
respeito ao EGC é que, para qualquer taxa de código, a potência
do amplificador do transmissor deve ser capaz de aumentar a
sua saída instantânea de potência sem distorcer o sinal. Assim,
o output back-off do amplificador tem que ser maior do que o
usual. Se ocorrer distorção, os ganhos sobre outros esquemas
serão menores. Assim, o esquema proposto pode ser melhor
para o downlink onde uma estação base serve vários usuários, e
UCHÔA et al.: LATINCON09 - HYBRID ARQ WITH PARTIAL
421
então a maior limitação no projeto do amplificador de potência
é limitada à estação base. Entretanto, o limitante imposto ao
amplificador de potência é menor do que o limitante imposto
pela modulação 16-QAM, onde a maior diferença de energia
entre os símbolos é próxima de 10 dB.
450
400
Método Proposto
EGC
HARQ Tipo I
350
Nesta seção utilizaram-se simulações computacionais para
verificar os resultados de throughput apresentados na seção
anterior, e também para investigar o desempenho do método
proposto e do EGC em termos de throughput número médio
total de iterações. Nas seguintes simulações considerou-se um
máximo de 50 iterações de decodificação, 8 retransmissões,
tamanho do bloco
bits, 1000 blocos para cada valor
de
, taxa do código
, modulação BPSK, para o
fixo
canal AWGN. Além do mais, consideramos um
para todas as retransmissões, que é igual ao valor de
na
primeira transmissão.
A Fig. 4 apresenta o throughput teórico e simulado para o
método proposto e o EGC versus
, onde o canal direto é
o AWGN. Na figura é apresentado também, como uma
referência, o throughput do HARQ Tipo I sem combinação por
diversidade. Através da figura, pode-se notar que o throughput
estimado fica muito próximo dos resultados da simulação. Os
casos das outras taxas (
e
) foram também
testados e obtiveram resultados similares aos apresentados na
Fig. 4.
Os resultados apresentados na Fig. 4 mostram que o método
proposto supera o EGC. Entretanto, uma vez que foi utilizada
retransmissão parcial, pode ocorrer que no método proposto
mais transmissões sejam necessárias para uma decodificação
correta de um pacote do que no EGC. Por exemplo, na Fig. 4
em
dB, de
transmissões são necessárias
)
para o EGC (assim obtendo um throughput de
enquanto que
transmissões são necessárias para o
). Estes
método proposto (obtendo um throughput de
resultados corroboram os resultados teóricos, de (4), da seção
IV.
Iterações
300
V. RESULTADOS DA SIMULAÇÃO
250
200
150
100
50
0
-5
-4
-3
-2
-1
0
E b/N0 (dB)
1
2
3
4
Figura 5: Número médio do total de iterações para o método proposto e o
EGC em canal AWGN. Na figura é apresentado também para o HARQ Tipo I
sem combinação por diversidade. O código LDPC é do IEEE 802.16e taxa
com
.
Finalmente, na Fig. 5 mostramos o número total de
iterações de decodificação necessária para decodificar um
pacote com sucesso para o caso do método proposto, EGC e
HARQ tipo I. O número total de iterações de decodificação
considera que a transmissão original e todas as seguintes
retransmissões. Por exemplo, se um pacote requer duas
retransmissões para ser decodificado com êxito, o número
total de iterações é entre 101 e 150, uma vez que se limita o
número máximo de iterações por tentativa de decodificação a
50. A partir da figura podemos ver que o método proposto
requer um pouco mais iterações de decodificação do que o
clássico EGC. No entanto a partir da figura, podemos ver que
a diferença não é em geral superior a 50 iterações, o que
parece ser um aumento muito pequeno em comparação com
os ganhos obtidos em termos de throughput, como mostrado
na Fig. 4. Os resultados referentes ao throughput, atraso e
número total de iterações de decodificação para os casos de
outras taxas (
e
) apresentam conclusões
semelhantes às do caso da taxa
, e são omitidos aqui
por questão de brevidade.
0.9
0.8
0.7
0.6
Throughput
VI. ANÁLISE DE CROSS LAYER
Método Proposto Teórico
Método Proposto Simulado
EGC Teórico
EGC Simulado
HARQ Tipo I Simulado
0.5
0.4
0.3
0.2
0.1
0
-5
-4
-3
-2
-1
0
Eb/N0 (dB)
1
2
3
4
Figura 4: Throughput teórico e simulado para o método proposto e o EGC em
canal AWGN. Na figura é apresentado também o throughput do HARQ Tipo
I sem combinação por diversidade. O código LDPC é do IEEE 802.16e taxa
com
.
O TCP [28] é um protocolo de transporte orientado por
conexão. O TCP é responsável por adaptar a taxa de
transmissão conforme a largura de banda disponível, evitando
o congestionamento da rede e criando uma conexão confiável
através da retransmissão de pacotes perdidos. A
confiabilidade é alcançada através de mensagens ACK
transmitidas pelo receptor em resposta aos segmentos de
dados de entrada. Um pacote é considerado perdido quando
três ACKs repetidos para o mesmo pacote chegarem à origem,
ou quando um ACK não for recebido na origem dentro de um
período específico de tempo (tempo limite de retransmissão).
Quando um segmento chega fora de ordem no receptor este
faz com que ACKs duplicados sejam gerados e não é
considerada como uma perda. Um segmento é retransmitido
geralmente depois de três ACKs duplicados mesmo que o
422
A. Desempenho de Métodos HARQ Sobre o TCP
O desempenho do throughput do TCP foi simulado usando
o pacote NS-2 [30], onde o aplicativo que estava operando
sobre TCP era o protocolo de transferência de arquivos
(FTP). A topologia da simulação é mostrada na Fig. 6, onde
N0 é o nó de origem. Os nós N1 e N2 representam os
roteadores, enquanto o N3 é o nó de destino. Os nós (N0 N1) e (N2 - N3) são conectados através de um link
bidirecional que tem 10 ms de atraso de propagação e
capacidade de 10 Mbps. Os nós (N1 - N2) também estão
conectados através de um link bidirecional que tem 10 ms de
atraso de propagação, mas com capacidade de 1Mbps.
Supomos uma alta capacidade de link entre os nós (N0 - N1) e
nós (N2 - N3) é livre de erros. Estes podem ser links de fibra
óptica, por exemplo. Assumimos que a ligação entre os nós de
baixa capacidade (N1 - N2) é menos confiável. Esta conexão
poderia ser uma conexão sem fio.
N0
10 Mbps
10 ms
Canal AWGN
Métodos de HARQ
N1
N3
10 Mbps
10 ms
N2
1 Mbps
10 ms
Figura 6: Cenário de rede que foi implementado no simulador NS-2.
Uma vez que o TCP permite algumas retransmissões da
camada física, considerar os casos em que o atraso máximo
permitido corresponde à duração de dois ou três
quadros da camada física, que por sua vez, é considerado
como 288 bytes (2304 bits) de comprimento. Portanto, se a
ligação entre nós (N1, N2) é utilizado o método clássico
EGC, então uma (
) ou duas retransmissões (
)
são permitidos. No entanto, se considerarmos o uso do
método proposto, logo, três retransmissões (
) ou seis
retransmissões (
) são permitidas. Observe que
quando se utiliza o método proposto podemos permitir mais
retransmissões porque são realizadas retransmissões parciais,
com
do comprimento do bloco de cada retransmissão do
esquema clássico EGC.
0
10
EGC TX=3
EGC TX=2
Proposto TX=7
Proposto TX=4
-1
10
FER
timer de retransmissão não tenha expirado.
A fim de controlar a taxa de transmissão e evitar o
congestionamento da rede, o número de pacotes que podem
ser transmitidos sem receber um ACK é delimitado por um
parâmetro chamado de janela de congestionamento (CW). O
tamanho de CW é controlado dinamicamente de acordo com o
estado da rede [29]. Para uma nova conexão, ou quando a
retransmissão é gerada pelo timeout de ACK, a CW é
configurada como na fase de início lento (slow start phase).
Cada vez que um ACK é recebido, o CW é incrementado em
um segmento.
Durante a slow start phase, a CW aumenta até que um
valor limite seja atingido, ou um tempo limite ocorra. Quando
isso acontece, a slow start phase termina e uma segunda fase
inicia chamada de (congestion avoidance phase). Nesta fase,
a CW tem um crescimento linear. Um mecanismo adicional
denotado de retransmissão rápida e de rápida recuperação
também é empregado. Neste caso, uma perda de segmento é
detectada e a recuperação de erro realizada antes que o timer
de transmissão expire. Entretanto, a taxa de transmissão não é
reduzida mesmo depois do tempo limite, porque há uma
detecção de perda e de retransmissão inicial, aumentando o
desempenho do TCP.
O protocolo TCP foi inicialmente projetado para operar em
redes com fio sem perdas. Seu desempenho em redes com
perdas, como uma rede sem fio, pode ser severamente
reduzido, pois as perdas de pacotes adicionais são induzidas
pelo canal rádio. O TCP interpreta essas perdas como
causadas pelo congestionamento da rede. Neste caso, o TCP
requer mecanismos de controle de congestionamento que se
destinam a reduzir o congestionamento da rede, reduzindo
também a taxa de transferência de conexão e aumentando o
atraso de transferência de dados fim – a – fim. Uma estratégia
para minimizar a redução de throughput do TCP, em
conexões sem fios, é empregar um mecanismo de
retransmissão na camada de enlace de rádio, a fim de evitar
que o TCP reinicialize na slow start phase. Retransmissões na
camada de enlace são possíveis porque o valor de timeout do
TCP é longo o suficiente para permitir a retransmissão de
alguns quadros perdidos.
IEEE LATIN AMERICA TRANSACTIONS, VOL. 8, NO. 4, AUG. 2010
-2
10
-3
10
-6
-5
-4
-3
-2
E b/N0 (dB)
-1
0
1
Figura 7: Taxa de erro de quadro (FER) versus
para o código IEEE
802.16e LDPC com uma taxa de 5/6, para o método proposto e o clássico
EGC, considerando os dois atrasos máximos permitidos na camada física.
A Fig. 7 mostra a taxa de erro de quadro (FER), versus
da ligação entre os nós (N1, N2), considerando o
método proposto e o esquema clássico EGC, para os dois
atrasos máximos permitidos na camada física. Os resultados
na Fig. 7 são usados para modelar o desempenho de erro do
link nas simulações do NS-2.
UCHÔA et al.: LATINCON09 - HYBRID ARQ WITH PARTIAL
423
Finalmente, a Fig. 9 mostra a taxa de perda de pacotes do
TCP, considerando o esquema proposto e o EGC, para os
atrasos máximos permitidos na camada física. Como se
poderia esperar, dado o resultado na Fig. 8, a taxa de perda de
pacotes do TCP quando se considera o esquema proposto é
consideravelmente menor do que quando se utiliza o clássico
EGC.
700
Throughput (kbps)
600
EGC TX=3
EGC TX=2
Proposto TX=7
Proposto TX=4
500
400
VII. CONCLUSÃO
300
200
100
0
-6
-5
-4
-3
-2
Eb/N0 (dB)
-1
0
1
Figura 8: Desempenho de throughput no TCP considerando um código LDPC
do IEEE 802.16e com uma taxa de 5/6, para o método proposto e o clássico
EGC, considerando os dois atrasos máximos permitidos na camada física.
A Fig. 8 apresenta o desempenho de throughput do TCP,
considerando que a conexão entre os nós da camada física
(N1, N2) é modelada segundo o método clássico EGC e nosso
método proposto. Os dois atrasos máximos permitidos são
considerados. No caso de um atraso máximo igual a dois
quadros da camada física o esquema proposto supera em
torno de 2.5 dB melhor do que o clássico EGC (curvas EGC e Proposto na figura). Para o caso de um
atraso máximo igual ao de três quadros da camada física,
então a vantagem do esquema proposto é maior, sendo em
torno de 3.5 dB. Além disso, é interessante notar que,
considerando que o desempenho do esquema proposto é
melhor do que do clássico EGC mesmo se considerarmos um
atraso máximo de dois quadros de camada física para o
esquema proposto, e três quadros para o EGC (curvas EGC e Proposto ). A vantagem do método
proposto seria ainda de 1 dB.
100
90
80
Perda de Pacote (%)
70
60
EGC TX=3
EGC TX=2
Proposto TX=7
Proposto TX=4
50
40
30
20
10
0
-6
-5
-4
-3
-2
Eb/N0 (dB)
-1
0
1
Figura 9: Perda de pacotes no TCP para o código LDPC do IEEE 802.16e
com uma taxa de 5/6, para o método proposto e o método clássico EGC, e
para os dois atrasos máximos admissíveis na camada física.
Este artigo apresentou um novo esquema de HARQ usando
códigos LDPC, retransmissões parciais, controle de potência e
diversidade por combinação. O projeto foi baseado em
análises das EXIT charts, bem como o método proposto
mostrou superar o método clássico de HARQ com EGC. O
EGC é considerado na literatura ser o melhor esquema de DC
até agora para o canal AWGN. O método proposto, que
divide as retransmissões em sub-pacotes de comprimento
iguais, apresentou um desempenho de throughput melhor,
exigindo para isso apenas um pouco mais iterações de
decodificação. Além disso, uma análise do desempenho do
TCP quando utiliza o método proposto na camada física
resultou em melhorias significativas em termos de throughput
e taxa de perda de pacotes, demonstrando assim a
aplicabilidade do método proposto.
REFERÊNCIAS BIBLIOGRÁFICAS
[1]
S. B. Wicker, Error Control Systems for Digital Communication and
Storage, 1st ed. Englewood Clifs: Prentice-Hall, July 1994.
[2] C. Lott, O. Milenkovic, and E. Soljanin, “Hybrid ARQ: Theory, state
of the art and future directions,” in Proc. IEEE ITW’07, Jul. 2007, pp.
1–5.
[3] (2008) IEEE-WiMax 802.16e Standard for local and metropolitan
area networks Part 16: Air Interface for Fixed and Mobile Broadband
Wireless Access Systems. [Online]. Available: [Online]. Available:
http://standards.ieee.org/getieee802/802.16.html
[4] (2007, Feb.) IEEE-WiFi P802.11n/D2.00: Draft standard for local and
metropolitan area networks, specific requirements part 11: Wireless
LAN Medium Access Control (MAC) and Physical Layer (PHY)
specifications: enhancements for higher throughput.
[5] N. Bhushan, C. Lott, P. Black, R. Attar, Y. C. Jou, M. Fan, D. Ghosh,
and J. Au, “CDMA2000 1xEV-DO revision A: a physical layer and
MAC layer overview,” IEEE Commun. Mag., vol. 44, no. 2, pp. 37–
49, Feb. 2006.
[6] M. Fan, D. Ghosh, N. Bhushan, R. Attar, C. Lott, and J. Au, “On the
reverse link performance of CDMA2000 1xEV-DO Revision A
system,” in Proc. IEEE ICC’05, May 2005, pp. 2244–2250.
[7] 3GPP TS 25.308, “3rd generation partnership project,” Technical
Specification Group Radio Access Network; High Speed Downlink
Packet Access (HSDPA); Overall description; Stage 2 (Release 5),
Tech. Rep., Mar. 2002.
[8] 3GPP TR 25.814, “3rd generation partnership project,” Technical
Specification Group Radio Access Network; Physical layer aspects
for evolved Universal Terrestrial Radio Access (UTRA) (Release 7),
Tech. Rep., Jun. 2006.
[9] S. Lin and D. J. Costello, Error Control Coding: Fundamentals and
Applications, 2nd ed. New Jersey: Prentice-Hall, June 2004.
[10] D. Chase, “Code combining - a maximum-likelihood decoding
approach for combining an arbitrary number of noisy packets,” IEEE
Trans. Commun., vol. 33, no. 5, pp. 385–393, May 1985.
[11] R. D. Souza, M. E. Pellenz, and T. Rodrigues, “Hybrid ARQ scheme
based on recursive convolutional codes and turbo decoding,” IEEE
Trans. Commun., vol. 57, no. 2, pp. 315–318, Feb. 2009.
[12] K. C. Beh, A. Doufexi, and S. Armour, “Performance evaluation of
hybrid ARQ schemes of 3GPP LTE OFDMA system,” in Proc. IEEE
PIMRC’07, Sept. 2007, pp. 1–5.
424
IEEE LATIN AMERICA TRANSACTIONS, VOL. 8, NO. 4, AUG. 2010
[13] Motorola, “Performance comparison of hybrid-ARQ schemes,” 3GPP
input paper TSGR1#17(00)1396, Tech. Rep., Oct. 2000.
[14] J.-F. Cheng, “Coding performance of hybrid ARQ schemes,” IEEE
Trans. Commun., vol. 54, no. 6, pp. 1017–1029, Jun. 2006.
[15] D. Toumpakaris, J. Lee, A. Matache, and H.-L. Lou, “Performance of
MIMO HARQ under receiver complexity constraints,” in Proc. of the
IEEE Globecom’08, 2008, pp. 1–5.
[16] J. Lee, H. L. Lou, D. Toumpakaris, E. Jang, and J. Cioffi,
“Transceiver design for MIMO wireless systems incorporating hybrid
ARQ,” IEEE Commun. Magazine, vol. 47, no. 1, pp. 32–40, Jan.
2009.
[17] P. Frenger, S. Parkvall, and E. Dahlman, “Performance comparison of
HARQ with Chase combining and incremental redundancy for
HSDPA,” in Proc. IEEE VTC Fall’01, vol. 3, Oct. 2001, pp. 1829–
1833.
[18] R. G. Gallager, “Low-Density Parity-Check Codes,” IRE Trans.
Inform. Theory, no. IT-8, pp. 21–28, Jan. 1962.
[19] R. M. Tanner, “A recursive approach to low complexity codes,” IEEE
Trans. Inform. Theory, vol. 27, pp. 533–547, Sep. 1981.
[20] D. J. C. Mackay and R. Neal, “Good codes based on very sparse
matrices,” LNCS, vol. 1025, pp. 100–111, 1995.
[21] D. J. C. Mackay, “Good error-correcting codes based on very sparse
matrices,” IEEE Trans. Inform. Theory, vol. 45, no. 2, pp. 399–431,
1999.
[22] Y. Cao, J. Gu, L. Qi, and D. Yang, “Degree distribution based HARQ
for irregular LDPC,” IEEE Electron. Lett., vol. 42, no. 6, pp. 363–
364, Mar. 2006.
[23] X. Li, Y. Cao, and D. Yang, “An improved degree distribution based
HARQ for LDPC,” in Proc. IEEE WiCOM’06, Sep. 2006, pp. 1–4.
[24] F. Huang, X. Yi, and T. Wang, “Reliability-based selective repeat
hybrid ARQ protocol on low density parity check codes,” in ACM
ACE ICAT’06, Nov. 2006, pp. 576–579.
[25] Y. Inaba, T. Saito, and T. Ohtsuki, “Reliability-based hybrid ARQ
(RB-HARQ) schemes using low-density parity-check (LDPC) codes,”
IEICE Trans. Commun., vol. E89-B, no. 4, pp. 1170–1177, Apr.
2006.
[26] J. Kim, W. Hur, A. Ramamoorthy, and S. W. McLaughlin, “Design of
rate-compatible irregular LDPC codes for incremental redundancy
hybrid ARQ systems,” in Proc. IEEE ISIT’06, Jul. 2006, pp. 1139–
1143.
[27] S. ten Brink, G. Kramer, and A. Ashikhmin, “Design of Low-Density
Parity-Check Codes for modulation and detection,” IEEE Trans.
Commun., vol. 52, no. 4, pp. 670–678, Apr. 2004.
[28] W. Stevens, “TCP Slow Start, Congestion Avoidance, Fast
Retransmit and Fast Recovery Algorithm,” RFC 2001, Jan. 1997.
[29] M. Allman, S. Floyd, and C. Partridge, “Increasing TCP’s initial
window,” RFC 3390, Aug. 2002.
[30] NS-2. (2009) Network Simulator 2. [Online]. Available: http://www.isi.edu.edu/nsnam/ns
André Gustavo Degraf Uchôa (M’08)
nasceu em Cianorte, Brasil, 1980. Ele
recebeu o título de Engenheiro Eletricista
(com honras) em 2004 e o título de Mestre
em Ciências da Computação em 2007,
ambos
pela
Pontifícia
Universidade
Católica do Paraná (PUCPR), Curitiba,
Brasil. Atualmente ele está trabalhando para
obter o título de Doutor em Engenharia
Elétrica pela Universidade Tecnológica
Federal do Paraná (UTFPR), Brasil. Suas
áreas de interesse incluem sistemas de
comunicação sem fio, códigos corretores de erros, HARQ, criptografia e
sistemas operacionais.
Richard
Demo
Souza
nasceu
em
Florianópolis, Brasil, 1978. Ele recebeu o título
de Engenheiro Eletricista e o título de Doutor
em
Engenharia
Elétrica,
ambos,
pela
Universidade Federal de Santa Catarina
(UFSC),
Brasil,
em
1999
e
2003,
respectivamente.
De Março 2003 à Novembro de 2003 ele foi
Pesquisador Visitante no Department of
Electrical and Computer Engineering na
Universidade de Delaware, USA. Desde Abril
de 2004 ele está na Universidade Tecnológica
Federal do Paraná (UTFPR), Curitiba, Brasil,
onde ele é atualmente Professor Adjunto.
Suas áreas de interesse incluem sistemas de comunicação sem fio, códigos
corretores de erros.
Marcelo Eduardo Pellenz recebeu o título de
Engenheiro Eletricista pela Universidade
Federal de Santa Maria (UFSM), Santa Maria,
Brasil, em 1993. Ele recebeu os títulos de
Mestre e Doutor em Engenharia Elétrica, pelo
Departamento de Comunicações (DECOM),
pela Universidade Estadual de Campinas
(UNICAMP), Campinas, Brasil, em 1996 e
2000, respectivamente. Pontifícia Universidade
Católica do Paraná, Curitiba, Brasil.
Atualmente ele está como Professor em
Dedicação
Exclusiva
na
Pontifícia
Universidade Católica do Paraná (PUCPR), Curitiba, Brasil.
Suas áreas de interesse incluem transmissão digital, codificação de canal e
fonte, redes sem fio, desempenho e modelamento de tráfico de rede.