Algoritmos de alocação dinâmica de
recursos rádio para sistemas 4G
baseados em MC-CDMA
Valdemar Celestino Monteiro
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
Resumo
•
•
•
•
•
•
•
•
Motivação
Definição do cenário da 4ª geração
Modelo de simulação a nível de sistema
Algoritmos de scheduling
Cenário de simulação
Resultados numéricos
Conclusões
Sugestões para trabalho futuro
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
2
Motivação
• Comunicações móveis evoluem para a 4ª geração
– Rede core baseada em pacotes (All-IP)
– Componente de banda larga
• Elevada largura de banda (da ordem das fornecidas actualmente pelas LANs)
• Suporta ambientes de grandes velocidades
• MC-CDMA (TDD) tecnologia candidata
– Flexibilidade no domínio Tempo-Código-Frequência
– Desafio: Optimizar a gestão de recursos para reagir a variações
instantâneas
• No canal rádio
• No tráfego dos utilizadores
• Arquitectura de Alocação Dinâmica de Recursos (DRA)
– Que pacote a servir?
– Que recurso rádio deve ser utilizado? (Potência, Modulação etc.)
Scheduling de Pacotes
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
3
Cenário da 4ª Geração
Múltiplos sub-sistemas
• Tentativa de definição
do cenário da 4ª
geração considera:
– Rede de sistemas onde
qualquer utilizador terá
ligação a qualquer
sistema a qualquer hora
de forma eficiente em
termos do custo
Serviços e
Aplicações
Canal de
Download
Novas Interf.
Rádio
Difusão
Digital
Rede Core baseada
em Pacotes
Móveis
2ª Ger.
Ligação por fio
xDSL
WLAN
IMT-2000
outras
entidades
Conectividade à
Curta Distência
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
4
Sistemas móveis da 4ª Geração
Sistema do projecto MATRICE
•
Tecnologia baseada em MC-CDMA
–
Técnicas avançadas de processamento
•
•
•
•
•
Alocação Dinâmica de Recursos na
camada MAC
Na fase inicial a cobertura não será
completa como esperada com o UMTS
–
•
•
•
Cancelamento de interferência
Estimação de canal
Detecção multi-utilizador
Grupo de
Sub-Portadoras
Inter-operabilidade com o UMTS-TDD
LB=50Mhz, adaptável (múltiplo de 5MHz)
Banda dos 5GHz
Trama MC-CDMA
–
23
3 slots (mesma duração do UMTS)
23 grupos de 32 subportadoras
Símbolo de dados espalhado num grupo de
subportadoras em um de 32 códigos
ortogonais de comprimento 32
2
Id dos Slots
deTempo
3
Códigos 3 a 32 (DL)
Código 2 (DL)
Código 1 (DL)
Tempo-código-frequência
•
•
•
1
Slot de tempo
usado para o UL
1
32
3
2
1
Id dos Códigos
de Espalhamento
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
5
Simulação a nível de sistema
Requisitos, desafios e soluções
• Avaliação fiável da capacidade do sistema
– Desempenho do sistema a nível da físico deverá ser levado em
conta
• Complexidade elevada (tempos de simulação) quando
plataformas heterogéneas são usados em simultâneo
– Simulação simultânea de transmissão a nível de bit (nível físico) e a
nível de trama (nível de sistema) deverá ser evitada
• Avaliação da capacidade de sistema deve explorar
interfaces simplificadas
– Interfaces com a camada ligação – Tabelas de acesso directo
– Mapeamento de SIR ao BLER (bloco)
• Interfaces implementadas
– Interface de valor médio
– Interface de valor actual
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
6
Simulação a nível de sistema
Interface de valor médio
• Aplicações do tipo tempo real
– Tempo de chamada/sessão longo
– Avaliação da qualidade da ligação em período
relativamente longo quando comparado com o tempo de
coerência do canal
• Tabelas obtidas segundo as seguintes condições
– Durante o período de avaliação do sistema (Tqos)
•
•
•
•
Ligação encontra-se activa
Tráfego é estacionário
Atribuição de potência constante
Número de desvanecimentos rápidos deve ser suficientemente
grande de modo que seja aplicada a lei dos grandes números
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
7
Simulação a nível de sistema
Interface de valor actual
• Ligações do tipo comutação de pacotes
– Tempo de chamada/sessão relativamente curto
– Período associado à transmissão de pacote curto
(duração do slot) da ordem de grandeza do tempo de
coerência do canal
• Tabelas obtidas nas seguintes condições
– Perdas por propagação e desvanecimento lento
considerados constantes durante o período Tslot
– Os percursos associados ao desvanecimento rápido são
mutuamente independentes
– Cancelamento perfeito de interferência
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
8
Simulação a nível de sistema
Interface IP (I)
• Interface do simulador de sistema
com tráfego IP da rede
• Baseada na rede IPv6
– Características bem definidas de
QoS
• Acesso através de ficheiros de
captura
• Parâmetros de tráfego extraídos de
cada pacote (armazenados em
ficheiros de texto)
–
–
–
–
–
Configuração
Ficheiro de
Captura da
rede
Saída 2
Simulador
de Sistema
Módulo da Inteface IP
Endereço de origem
Endereço de destino
Instante de chegada
Tamanho
Classe de serviço (DSCP de
DiffServ)
Saída 1
Ficheiros
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
9
Simulação a nível de sistema
Interface IP (II)
• Ficheiro de texto
– Um ficheiro por parâmetro
– Parâmetros organizados
por Streams
Stream
de Pacotes
Pacote
Pacote
Pacote
Stream = comb[End_origem,
End_destino, Id_fluxo]
• Alterações pouco significativas se mais
parâmetros forem necessários (indexação etc.)
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
10
Pacote
Algoritmos de scheduling
Redes Cabladas
• Canal praticamente invariante
comparado com tempo de
sessão
• Políticas de scheduling de
pacotes ditadas essencialmente
por
– Limites de atraso
– Largura de banda imposta para
classe de serviço e/ou utilizador
Nó 1
Nó 2
Router
Router
Camadas
superiores
• Três grandes categorias
– Fair queuing
– Baseados em deadline
– Baseados no ritmo de
transmissão
Scheduler
Camada
física
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
11
Algoritmos de scheduling
Redes rádio móvel
• Dinâmica inerente
• Utilizadores “entram” e “saem”
do sistema
• Movem-se durante as sessões
(variação do canal rádio)
• Pacotes com destinos
diferentes estão associados a
diferentes níveis de sinal e
interferência
• O Scheduler que não tem em
conta o estado do canal terá
um fraco desempenho
Estação Base
Camadas
superiores
Scheduler
Camada
física
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
12
Algoritmos de scheduling
Algoritmo de Projecto (I)
• Prioritização de pacotes com
base em
– Informação da camada física
Camadas
superiores
• Fiabilidade da transmissão
– Informação de camada superior
• SIR alvo
• Limites de atraso da aplicação
Scheduler
Camada
física
• Função de prioridade combina
pesos associados a
– Fiabilidade, W1
– Time_out, W2
– Número de transmissões
efectuadas, W3
Priority  W1 ( type , SIR )( W2 ( type , time _ out )  W3 ( type ,# attempTx ))
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
13
Algoritmos de scheduling
Algoritmo de Projecto (II)
• Função da fiabilidade da transmissão
~ 0 se SIR  Alvo

W1 ( Serviço, SIR )  1 se Alvo  SIR  Alvo  Limiar
2 se SIR  Alvo  Limiar

W(SIR)
3
W(SIR)
2
1
0
Alvo +
Limiar
Th
Ta
re
sh
ol
d
rg
et
Alvo
SIR
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
14
Algoritmos de scheduling
Algoritmo de Projecto (III)
T im eTempo
- Ou t W e igde
h t Fu
n ct io n do pacote
Função
espera
• Função do tempo de espera
W(tempoDeEspera)
W (T im e_O u t)
W2 ( Serviço,TempoDeEspera )  k( MaxAtraso  TempoDeEspera )
2.5
2
1.5
1
0.5
0
0
5
10
15
MaxAtraso
Max
A lloableDelay
20
25
Tempo de
T imespera
e -o u t
• Função do numero de tentativas de
transmissão
3
W(tempoDeEspera)
W(Attem pTx)
0 if Attemp Tx  0

W3 (Type , AttempTx )  1 if Attemp Tx  1
2 if Attemp Tx  2

Atte
m pte d Tra
nsm ission WTx
e ight
Função
tentativas
2
1
0
0
1
2
Tentativas
Atte m pte d Tx Tx
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
15
Algoritmos de scheduling
DRA Implementado
• Estrutura do DRA baseado
no HSDPA do UMTS
• Inclui
– Codificação e modulação
adaptativa
– ARQ Híbrido com Chase
combining
• 30 dos 32 códigos
alocados para dados
• BS transmite com a
potência máxima
Alocação Dinâmica de Recursos
Priorida W1 (type, SIR)(W2 (type, time _ out )  W3 (type, # attempTx))
Fontes
Recursos
Fonte
1,1
Fonte
1, 2
Fonte
2,1
Schedule
r
TTI
Fonte
Slot
Codigo MCS
MC1
Fonte I ,j
Adaptação Link
QoS
Fonte W1(SIR )
W2(time -out)
W3(nTx)
MCN
Lista
ARQ
ARQ 1, 1
ARQ 1, 2
ARQ 2 ,1
ARQ 2 ,2
ARQ n ,1
ARQ n ,2
IQS
– 70% da potência total
alocada para dados, dividida
igualmente pelos códigos
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
MC2
MC3
16
nBits
ARQ
Algoritmos de scheduling
Cenário de simulação
Ambiente de simulação
Urbano
Raio da célula
300 m
Tipo de célula
(Omni ou sectorizada)
Omni
Velocidade do móvel
3km/h
Modelo de canal – Perdas por propagação e desvanecimento lento
Modelo de canal urbano
Modelo de canal
- desvanecimento rápido
ETSI BRAN E
(18 taps e Atraso max. 1.76µs)
Interface com camada física MATRICE
Interface de Valor Actual
Serviços
Voz e Web simultaneamente
Número de utilizadores de voz
20
Número de utilizadores de Web
9
Duração da trama
10 ms
Número de slots de tempo alocados para DL
1
Número de códigos de espalhamento alocados para dados
30
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
17
Algoritmos de scheduling
Simulação – Métricas de desempenho
• Utilizador (utilizador satisfeito)
– BLER
– Atraso de transferência
• Célula
– Throughput sobre a Interface Ar
– Throughput de serviço
– Serviço satisfeito
• Algoritmo proposto comparado com max(C/I)
Priority  arg( Max( SIRUser _ i ))
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
18
Algoritmos de scheduling
Resultados (I)
Scheduling de prioridade – Parâmetros de referência
CDF BLER e Atraso de Transferência
SIR – Alvo
-13.5 dB (Web)
-13.9 dB (Voz)
SIR – Limiar (sobre o alvo)
15 dB
Factor de prioritização do
atraso
0.75
H-ARQ Número de
transmissões
1 Tx p/ Voz
3 Tx p/ Web
Serviço de voz
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
19
Algoritmos de scheduling
Resultados (II)
Scheduling de prioridade – Parâmetros de referência
Serviço de Voz
Pacotes que atingiram deadline
vs. recebidos erradamente
Serviço de Web
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
20
Algoritmos de scheduling
Resultados (III)
Scheduling de referência: max(C/I)
Serviço de Voz
Serviço de Web
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
21
Algoritmos de scheduling
Resultados (IV) Throughput da célula
Métrica
(media por célula)
Prioridade
Parâmetros de
referência
SIR Máximo
OTA
566 kbps
588 kbps
Th. de Serviço
400 kbps
426 kbps
Razão
Th. Serv/OTA
0.707
0.724
270 kbps
277 kbps
Razão
ServSatisf /ThServ
0.676
0.650
Número médio de Tx p/
bloco (Web)
1.13
1.39
Serviço Satisfeito
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
22
Algoritmos de scheduling
Análise de resultados
• Melhores resultados de Throughput da célula para
Scheduler max(C/I)
– 72.4% de eficiência (Service/OTA) comparado com 70.7% com
scheduling de prioridade
• Melhores resultados de QoS (Serv_Satisf/Th_serv) com
scheduling de prioridade
– 66.7% de eficiência comparado com 65% com max(C/I)
• Resultados mostram que aumento da quantidade de tráfego
com qualidade de serviço é obtido à custa da diminuição do
Throughput da célula;
• Resultados obtidos sem inclusão de política de admissão de
utilizadores, o que levaria de certo a melhores resultados de
desempenho
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
23
Conclusões (I)
• Foi proposto e avaliado um algoritmo de atribuição de
recursos a pacotes com o objectivo de maximizar o
Throughput da célula mantendo o QoS dos utilizadores;
• O algoritmo proposto revela.se mais adequado para
scheduling de pacotes quando requisitos de serviço devem
ser levados em conta;
• Resultados mostram que aumento de cerca de 2.5% na
satisfação de utilizadores (Th_satisfeito/Th_serviço) é
obtido com a diminuição de 1.7% no Throughput da célula
(Th_serviço/OTA)
• O algoritmo proposto fornece um compromisso entre
qualidade de serviço e Throughput do sistema
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
24
Conclusões (II)
• O principal benefício do algoritmo proposto reside na
flexibilidade que permite ‘afinar’ o Scheduler com
parametrização adequada para o controlo do Throughput do
sistema
• A alocação dinâmica de recursos é um processo complexo
em que o Throughput final depende não só das políticas de
scheduling como também de adaptação da ligação e
processo de ARQ;
• Simulação é um processo delicado e as interfaces utilizadas
para o efeito foram apresentadas
– Interfaces com a camada física: de valor médio e valor actual
– Apresentou-se igualmente uma interface relativamente simples que
permite ao simulador operar com tráfego IP da rede
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
25
Sugestões para trabalho futuro
• Avaliação dos algoritmos de scheduling com
inclusão Controlo de Admissão de Utilizadores
• Análise optimizada do número de blocos com
pacotes de cada serviço em simultâneo num slot
de tempo
• Analise da complexidade na sinalização inerente à
flexibilidade associada ao recurso elementar
• Estudo do desempenho do DRA com técnicas
alternativas de HARQ, como por exemplo
Redundância Incrementada
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
26
Agradecimentos
Este trabalho foi financiado pelo Projecto MATRICE (IST-2001-32620).
O autor gostaria de agradecer à Universidade de Surrey pela utilização do
simulador de sistema e à France Telecom R&D pelas melhorias
introduzidas no módulo de DRA do mesmo
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
27
Obrigado
Algoritmos de alocação dinâmica de recursos rádio para sistemas 4G baseados em MC-CDMA
Valdemar Monteiro
Provas de Mestrado - Universidade de Aveiro, 21 de Julho de 2005
28