ANALISE DE DESEMPENHO E COMPLEXIDADE DOS ... - uel.br · 6.3 Curva de complexidade e desempenho do algoritmo PSO em função do par ametroˆ φ2. 31 6.4 Gráfico do comportamento

UNIVERSIDADE ESTADUAL DE LONDRINA

CENTRO DE TECNOLOGIA E URBANISMO

DEPARTAMENTO DE ENGENHARIA EL ETRICA

ANALISE DE DESEMPENHO E COMPLEXIDADE DOS

ALGORITMOS SWARM E SWARM QU ANTICO

APLICADOS A DETECCAO MULTIUSU ARIO EM

SISTEMAS DS-CDMA

Trabalho submetido aoDepartamento de Engenharia Eletrica,da Universidade Estadual de Londrina,

como parte dos requisitos para aobtencao do grau de Engenheiro Eletricista.

LEONARDO DAGUI DE OLIVEIRA

Londrina, Dezembro de 2005.

LEONARDO DAGUI DE OLIVEIRA

ANALISE DE DESEMPENHO E COMPLEXIDADE

DOS ALGORITMOS SWARM E SWARM QU ANTICO


SISTEMAS DS-CDMA

LONDRINA

2005




SISTEMAS DS-CDMA

Leonardo Dagui de Oliveira

‘Este trabalho foi julgado adequado para a conclusao do curso de Engenharia Eletrica e aprovado emsua forma final pelo Departamento de Engenharia Eletrica da Universiade Estadual de Londrina.’

Prof. Dr. Taufik AbraoOrientador

Banca Examinadora:

Prof. Dr. Taufik Abrao

Prof. Dr. Robinson Hoto

Prof. MSc. Luis Carlos Kakimoto

i

Resumo do trabalho apresentada ao DEEL-CTU-UEL como parte dos requisitos necessarios paraobtencao do grau de Engenheiro Eletricista.




SISTEMAS DS-CDMA


Dezembro/2005

Orientador: Prof. Dr. Taufik AbraoArea de Concentracao: TelecomunicacoesPalavras-chave: deteccao multiusuario, algoritmo de otimizacao atraves de nuvem de partıculas,programacao evolucionaria, complexidade computacionalNumero de Paginas: 76

Neste trabalho sao analisadas, avaliadas e comparadas duas tecnicas heurısticas evolucionarias deotimizacao baseadas no movimento bulicoso de partıculas (Swarm), aplicado ao problema da deteccaomultiusuario (MuD –Multiuser Detection) em sistemas DS/CDMA (Direct Sequence/Code DivisionMultiple Access). Compara-se a eficiencia do algoritmo de otimizacao Swarmaplicadoa deteccaomultiusuario DS/CDMA (SWARM-MUD) atraves do compromisso desempenhoversuscomplexi-dade computacional, sendo a complexidade expressa em termos do numero de operacoes necessariaspara se alcancar o desempenho obtido atraves do detectorotimo ou de maxima-verossimilhanca, ML(Maximum Likelihood).

A comparacao e realizada entre os algoritmos genetico, programacao evolucionaria com clona-gem, versao original e versao quantica doSwarm, sob uma mesma base de simulacao. Adicional-mentee proposta uma analise de complexidade para os algoritmos MuD-heurısticos mais precisaque as encontradas atualmente na literatura, expressando-a atraves do numero de operacoes computa-cionais e tempo consumido. Finalmente,e feita uma analise dos parametros de entrada do algoritmode otimizacao Swarm na tentativa de se encontrar parametros otimizados (ou quase-otimos) para oalgoritmo aplicado ao problema MuD.

ii

Abstract of report presented to DEEL-CTU-UEL as a partial fulfillment of the requirements for thedegree of Electrical Engineer.

TRADEOFF PERFORMANCE AND COMPLEXITY

ANALYSIS OF SWARM AND QUANTUM SWARM

OPTIMIZATION ALGORITHMS APPLIED TO MUD

DS-CDMA SYSTEMS


December/2005

Advisor: Prof. Dr. Taufik AbraoArea of Concentration: TelecommunicationsKey words: Mud detection, Swarm, Quantum Swarm, Evolutionary Programming, ComputationalComplexityNumber of Pages: 76

In this monography, the particles swarm optimization and quantum particles swarm optimizationtechniques, recently published in the literature, and applied to Direct Sequence/Code Division Mul-tiple Access systems (DS/CDMA) with multiuser detection (MuD) is analyzed, evaluated and com-pared. The Swarm algorithm efficiency when applied to the DS-CDMA multiuserdetection (Swarm-MuD) is compared through the tradeoff performance versus computational complexity, being thecomplexity expressed in terms of the number of necessary operations to be reached the performanceobtained through the optimum detector or the Maximum Likelihood detector (ML).The compari-son is accomplished among the genetic algorithm, evolutionary programming with clone and originalSwarm and Quantun Swarm versions algorithm under a same simulation basis.Additionally, it is pro-posed an heuristics-MuD complexity analysis more precise than that found inthe literature, express-ing it through the number of computational operations. Finally, an analysis is made for the Swarmalgorithm’ input parameters in the attempt to find the optimum parameters (or almost-optimum) forthe algorithm applied to the MuD problem.

iii

Conteudo

Lista de Figuras vi

Lista de Tabelas viii

Lista de Sımbolos e Abreviacoes ix

1 Introduc ao 1

2 CDMA 4

2.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.2 Espalhamento Espectral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 4

2.2.1 Espalhamento por Sequencia Direta . . . . . . . . . . . . . . . . . . . . . . 5

2.2.2 Espalhamento por Salto de Frequencia . . . . . . . . . . . . . . . . . . . . . 7

2.3 Modelos de Canais e o sistema DS/CDMA Convencional . . . . . . . . . . . . .. . 7

2.3.1 Canal AWGN Sıncrono . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.3.2 Canal com Desvanecimento Plano Sıncrono . . . . . . . . . . . . . . . . . . 9

3 Deteccao Multiusuario 10

3.1 Descorrelacionador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 11

3.2 MMSE - Mınimo Erro Quadratico Medio . . . . . . . . . . . . . . . . . . . . . . . 12

3.3 DetectorOtimo (ML) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

4 Tecnicas Heurısticas de Busca 14

4.1 Programacao Evolucionaria (EP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

4.2 Programacao Evolucionaria com Clonagem (EP-C) . . . . . . . . . . . . . . . . . . 16

4.3 Algoritmo Genetico (GA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

5 Algoritmo Swarm 19

5.1 Historico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

5.2 AlgoritmoSwarm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

5.2.1 Princıpio do Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

5.2.2 SwarmAplicadoa Deteccao Multiusuario . . . . . . . . . . . . . . . . . . . 22

5.2.3 Estrutura do Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

5.3 AlgoritmoSwarmQuantico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

5.3.1 Princıpios do Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

5.3.2 Estrutura do Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

iv

6 Resultados Numericos 27

6.1 Swarmem Canal AWGN Sıncrono . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

6.1.1 Otimizacao dos Parametros do PSO para Canal AWGN Sıncrono . . . . . . 28

6.1.2 Otimizacao dos Parametros do QPSO para Canal AWGN Sıncrono . . . . . . 33

6.1.3 Resultados para canal AWGN Sıncrono . . . . . . . . . . . . . . . . . . . . 34

6.2 Swarm em Canal com Desvanecimento Plano Sıncrono . . . . . . . . . . . . . . . . 40

6.2.1 Otimizacao dos parametros do PSO para Canal com Desvanecimento PlanoSıncrono . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

6.2.2 Resultados para Canal com Desvanecimento Plano Sıncrono . . . . . . . . . 43

6.3 Complexidade Computacional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

6.3.1 Complexidade Computacional do PSO em Canal AWGN Sıncrono . . . . . . 47

6.3.2 Complexidade Computacional do QPSO em Canal AWGN Sıncrono . . . . . 48

6.3.3 Complexidade do PSO e QPSO em Canal com Desvanecimento Sıncrono . . 49

6.3.4 Comparacao da Complexidade entre os Algoritmos . . . . . . . . . . . . . . 49

6.4 Compromisso ComplexidadeversusDesempenho . . . . . . . . . . . . . . . . . . . 52

7 Conclusao 54

7.1 Perspectivas de Estudo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 56

A Estrutura do Programa em MATLAB 57

A.1 Bloco Principal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

A.1.1 PSO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

A.1.2 QPSO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

Referencias Bibliograficas 60

v

Lista de Figuras

2.1 Comparacao temporal e espectral entre as tecnicas de multiplo acesso CDMA, TDMAe FDMA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2 Espalhamento esectral do sinal atraves de sequencia direta, visto no domınio do tempo. 6

2.3 Espalhamento espectral obtido por um chip retangular.M(f) eC(f) sao as respecti-vas transformadas de Fourier dem(t) e c(t) da figura 2.2. . . . . . . . . . . . . . . . 6

2.4 Comunicacao por Salto de frequencia. . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.5 Modelo de transmissao do sistema DS/CDMA sıncrono em canal AWGN. . . . . . . 8

3.1 Diagrama do detector Descorrelacionador. . . . . . . . . . . . . . . . . . .. . . . . 11

3.2 Diagrama do receptor MMSE. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12

4.1 Exemplos de operadores geneticos: a)mutacao; b)clonagem; c)crossover. . . . . . . . 15

5.1 Representacao vetorial da insercao de velocidade em uma partıcula no instante detempot. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

5.2 Representacao grafica da funcao sigmoide. . . . . . . . . . . . . . . . . . . . . . . . 22

6.1 Curva para otimizacao deVmax. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

6.2 Grafico utilizado para otimizacao do parametroφ2. . . . . . . . . . . . . . . . . . . 30

6.3 Curva de complexidade e desempenho do algoritmo PSO em funcao do parametroφ2. 31

6.4 Grafico do comportamento do PSO em funcao da variacao do parametroω. . . . . . 31

6.5 Verificacao da variacao conjunta das tres ponderacoes do calculo da velocidade, noPSO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

6.6 Curvas de convergencia do algoritmo QPSO para varios valores deα. . . . . . . . . 33

6.7 Curvas de convergencia do algoritmo QPSO para varios valores dec1. . . . . . . . . 34

6.8 Curva de convergencia para carregamentoL = 0, 3125 em canal AWGN sıncrono. . 36

6.9 Curva de convergencia para carregamentoL = 0, 50 em canal AWGN sıncrono, comcontrole perfeito de potencia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

6.10 Curva de convergencia para carregamentoL = 0, 5 em canal AWGN sıncrono, comefeito near-far, onde 8 us. sao considerados com potencia de 0dB e 8 usuarios estaocom potencia 8dB acima. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

6.11 Curva de convergencia para carregamentoL = 0, 75 em canal AWGN sıncrono, comcontrole perfeito de potencia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

6.12 Curva de convergencia da funcao custo para carregamentoL = 1, 00 em canalAWGN sıncrono, com controle perfeito de potencia. . . . . . . . . . . . . . . . . . . 38

vi

6.13 Curva de convergencia da funcao custo para carregamentoL = 0, 75 em canalAWGN sıncrono, com controle perfeito de potencia. . . . . . . . . . . . . . . . . . . 39

6.14 Curva do comportamento da convergencia dos algoritmos em funcao da RelacaoEb/N0 do sistema, em canal AWGN sıncrono. . . . . . . . . . . . . . . . . . . . . . 39

6.15 Curva do comportamento da convergencia dos algoritmos no ponto de convergenciado PSO, em funcao da relacaoEb/N0, em canal AWGN sıncrono. . . . . . . . . . . 40

6.16 Curva de convergencia para algoritmo PSO, comω = 1, φ1 = 2 e Vmax = 4 e φ2

variando entre 0 e 10. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

6.17 Comportamento do algoritmo PSO em funcao do fatorω, para canal com desvaneci-mento plano sıncrono. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

6.18 Curva de convergencia dos algoritmos para canal com desvanecimento planosıncrono, comφ2 = 10, carregamentoL = 0, 5 eEb/N0 = 12dB. . . . . . . . . . . 44

6.19 Curva de convergencia dos algoritmos para canal com desvanecimento planosıncrono, com 16 usuarios,Eb/N0 = 12dB e efeitonear-far. . . . . . . . . . . . . . 44

6.20 Curva de convergencia dos algoritmos para canal com desvanecimento planosıncrono, com 16 usuarios eEb/N0 = 18dB. . . . . . . . . . . . . . . . . . . . . . 45



6.23 Curva do comportamento da convergencia dos algoritmos em funcao da RelacaoEb/N0 do sistema, para canal com desvanecimento plano sıncrono. . . . . . . . . . . 47

6.24 Curva de convergencia dos algoritmos do tempo relativo ao PSO, comEb/N0 =12dB e numero de usuariosK = 16, para canal com desvanecimento plano sıncrono. 52



vii

Lista de Tabelas

1.1 Aplicacoes e requisitos para a tecnologia 3G . . . . . . . . . . . . . . . . . . . . . . 2

5.1 Probabilidade mınima de troca de bit com o uso deVmax. . . . . . . . . . . . . . . . 23

6.1 Simulacoes realizadas para otimizacao dos parametros do PSO em canal comdesvanecimento plano sıncono. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

6.2 Complexidade dos detectores multiusuario em termos de operacoes, em canal AWGNsıncrono. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

6.3 Numero de operacoes para os algoritmos atingirem a convergencia, em canal AWGNsıncrono. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

6.4 Tempo demandado para execucao dos algoritmos heurısticos em canal AWGN sıncrono. 51

6.5 Complexidade dos detectores multiusuario em termos de operacoes, em canal comdesvanecimento plano sıncrono. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

6.6 Tempo demandado para execucao dos algoritmos heurısticos em canal com desvanec-imento plano sıncrono. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

viii

Lista de Sımbolos e Abreviacoes

1G, 2G, 3G Sistemas de comunicacao com tecnologia da primeira, segunda e terceira geracoes, res-pectivamente.

AWGN Ruıdo Branco Aditivo Gaussiano (Additive White Gaussian Noise).

BW Largura de banda (Bandwidth) do espectro de frequencia utilizada para transmissao deinformacao.

BER Taxa de Erro de Bit (Bit Error Rate).

BPSK Modulacao por chaveamento de fase binario (Binary Phase Shift Keying).

CD Detector convencional (Convencional Detector).

CDMA Sistema de Comunicacao de Acesso Multiplo por Divisao de Codigo (Code DivisionMultiple Acess).

DS Sequencia Direta (Direct Sequence).

DS/CDMA Sistema de Multiplo Acesso por Divisao de Codigo com Espalhamento Espectral porSequencia Direta (Direct Sequence/Code Division Multiple Acess).

DSP Processo Digital de Sinais (Digital Signal Processing).

EP Programacao Evolucionaria (Evolutionary Programming).

EP-C Programacao Evolucionaria com Clonagem.

FDMA Multiplo Acesso por Divisao de Frequencia (Frequency Division Multiple Acess).

FH Tecnica de espalhamento espectral que utiliza salto de frequencia (Frequency Hopping).

FH/CDMA Sistema de Multiplo Acesso por Divisao de Codigo com Espalhamento Espectral porSalto de Frequencia (Frequency Hopping/Code Division Multiple Acess).

FLAT Canal com Desvanecimento Plano Sıncrono.

FSK Modulacao por Chaveamento de Frequencia (Frequency Shift Keying).

GA Algoritmo Genetico (Genetic Algorithm).

GP Ganho de Processamento (Tb

Tc).

HIC Canceladores de Interferencia Hıbridos (Hybrid Interference Cancellation).

MAI Interferencia de Multiplo Acesso (Multiple Acess Interference).

MF Filtro Casado (Matched Filter).

ix

ML Detector de Maxima Verossimilhanca (Maximum Likelihood) ou otimo.

MMSE Detector multiusuario de mınimo erro quadratico medio (Minimum Mean Square Er-ror).

MSK Modulacao por frequencia com fase contınua (Minimum-Shift Keying).

MuD Deteccao Multiusuario (Multiuser Detection).

NFR Efeitonear-far.

OFDM Multiplexagem por Divisao de Frequencia Ortogonal (Orthogonal Frequency DivisionMultiplexing).

OOK Modulacao digital binaria por amplitude (On-Off Keying).

PIC Canceladores de Interferencia em Paralelos (Parallel Interference Cancelation) .

PN Sequencias pseudo aleatorias (pseudonoise).

PSO Otimizacao atraves de nuvem de partıculas (Particle Swarm Optimization).

QPSO Otimizacao atraves de nuvem de partıculas quanticas (Quantum Particle Swarm Opti-mization).

SA Recozimento Simulado (Simulated Annealing).

SIC Canceladores de Interferencia SucessivosSucessive Interference Cancellation.

SS Espalhamento Espectral (Spread Spectrum).

SuB Limiar de desempenho para a transmissao de umunico usuario (Single-user Bound).

TDMA M ultiplo Acesso por Divisao de Tempo (Time Division Multiple Acess).

x

α Parametro de controle do QPSO, representa o degrau para a funcaoQ.

Ak Amplitude do sinal transmitido pelo k-esimo usuario em um sistema DS/CDMA.

A Matriz diagonal com a amplitude de todos os usuarios.

β Parametro de controle do QPSO, representa o degrau para a funcaoQ.

β(t) Modulo do coeficiente complexo para o canal com desvanecimento plano sıncrono, comdistribuicao Rayleigh.

bk(i) I-esimo bit estimado para o k-esimo usuario.

cc(t) Coeficiente complexo para o canal com desvanecimento plano sıncrono.

c1 Ponderacao referentea primeira parcela no calculo da energia no QPSO.

c2 Ponderacao referentea segunda parcela no calculo da energia no QPSO.

c3 Ponderacao referentea terceira parcela no calculo da energia no QPSO.

ch(t) Codigo de espalhamento utilizado no sistema CDMA com espalhamento por salto defrequencia.

ck(t) Codigo (sequencia) de espalhamento utilizado no sistema DS/CDMA para o k-esimousuario.

cn Pulso formatado de uma sequencia de espalhamento, com valor +1 ou -1.

C Matriz diagonal formada pelos coeficientes complexos do canal com desvanecimentoplano sıncrono.

D Populacao utilizada pelos algoritmos heurısticos.

Eb/N0 Relacao energia de bit recebido e densidade espectral de potencia.

φ1 Ponderacao aplicada na parcela da velocidade referentea melhor posicao individual(PSO).

φ2 Ponderacao aplicada na parcela da velocidade referentea melhor posicao global (PSO).

g Numero de iteracoes realizadas por um algoritmo heurıstico.

(.)H Operador hermitiano, correspondea transposicao da matriz, seguida da conjugacaocomplexa.

Ic Numero de clones gerados para cada indivıduo selecionado no EP-C.

ic Percentagem dos indivıduos selecionados para clonagem no EP-C.

im Indice de mutacao utilizado no GA.

K Numero de usuarios do sistema DS/CDMA adotado.

Kc Comprimento da sequencia do codigo de espalhamento no espalhamento por salto defrequencia.

L Carregamento do canal (KN ).

µ Media do fator de mutacao, considerada zero.

xi

M Numero de clones gerados para cada indivıduo selecionado no EP-C.

Mh Numero de frequencia selecionaveis para codificar o sinal em um sistema FH/CDMA.

mk(t) Informacao transmitida na modulacao BPSK, assumindo valores +1 ou -1, para o k-esimo usuario.

N Comprimento da sequencia de espalhamento, em numero de chips.

n(t) Ruıdo Branco Gaussiano adicionado pelo canal.

Nj(µ, σ2) Representa uma variavel aleatoria, com varianciaσ2 e mediaµ.

ω Ponderacao para a velocidade anterior no calculo da velocidade presente, no PSO.

p(i)k [t] Elemento discreto referente aq(i)

k [t].

pc Probabilidade decrossover.

pbestgd [t] Melhor posicao global encontrada pelo algoritmo PSO, na d-esima dimensao.

pid[t] Posicao na d-esima dimensao da i-esima partıcula.

pbestid [t] Melhor posicao individual encontrada por cada partıcula no algoritmo PSO, na d-esima

dimensao.

PeDecorrk Probabilidade de erro de sımbolo para o k-esimo usuario, utilizando o Descorrela-

cionador.

PeMMSE1 Probabilidade de erro de sımbolo para um usuario, utilizando o MMSE, com controle

perfeito de potencia e sinais equicorrelacionados.

P[t] Matriz discretizada das energias quanticas contidas emQ[t].

p(i)[t] Vetor discretizado referente aq(i)[t].

pmg[t] Melhor posicao global encontrada ate o instante de tempot, no caso contınuo.

pmi[t] Melhor posicao individual encontrada ate o instante de tempot, no caso contınuo.

Q(.) Funcao Q, definida porQ(x) = 1 − P (x), que representa a integral dex a ∞ de

Z(x) = exp[(−x2)/2]sqrt(2∗pi) , sendoZ(x) a Funcao Probabilidade Gaussiana de variancia 1 e

media 0.

q(i)k [t] Energia quantica, contida no intervalo[0, 1], referente ao k-esimo ponto do i-esimo

usuario.

Q[t] Matriz com as energias quanticas das partıculas.

q(i)[t] Vetor de energia quantica para a i-esima partıcula.

Qmg[t] Parcela do calculo da energia quantica futura da partıcula referentea melhor posicaoglobal.

Qmi[t] Parcela do calculo da energia quantica futura da partıcula referentea melhor posicaoindividual.

R Taxa de transmissao de dados.

xii

r(t) Sinal recebido em banda base, para K usuarios, em canal com desvanecimento planosıncrono.

rand() Numero aleatorio com distribuicao uniforme entre[0, 1].

R Matriz de correlacao dos codigos utilizados no sistema DS/CDMA.

R+ Matriz Pseudo-inversa deR.

σ2 Variancia do fator mutacao utilizado em EP, EP-C e GA.

σ2r Variancia do ruıdo Gaussiano branco.

s(t) Sinal em banda base para informacao com modulacao BPSK.

S(x) Funcao sigmoide dex, definida por 11+e−x .

sT (t) Soma de todos os sinais transmistidos em banda base, em um sistema DS/CDMA.

si ou s(i) Representa um indivıduo nos algoritmos evolucionarios.

τk Atraso na transmissao para o k-esimo usuario.

θ(t) Fase do coeficiente complexo para o canal com desvanecimento plano sıncrono, comdistribuicao uniforme entre 0 e 2π.

Tb Perıdo de bit.

Tc Perıodo de Chip.

T Transformacao utilizada nos detectores MuD lineares.

tk k-esima linha da matriz de transformacao linear utilizada no descorrelacionador.

T Numero de melhores indivıduos selecionados, no GA.

vid[t] Velocidade na d-esima dimensao da i-esima partıcula.

Vmax Estabelece os limites superior e inferior que a velocidade de uma partıcula pode assumirno PSO.

y Vetor com o sinal recebido apos transmissao em canal AWGN ou com desvanecimentoplano sıncrono.

zk Sinaly apos passagem pelo detector MuD Descorrelacionador.

xiii

CAPITULO 1

I NTRODUCAO

Inicialmente os engenheiros de telecomunicacoes precursores encontraram varias dificuldades

para concretizar o conceito da telefonia movel. Equipamentos grandes e que possuıam grande

consumo inviabilizavam a sua criacao. Porem, com o avanco da eletronica, a comunicacao sem fio

comecou a se tornar tangıvel e despertar o interesse de varias empresas e instituicoes, que iniciaram

pesquisas nesta novaarea tecnologica. Como resultado dessas pesquisas, foram sendo desenvolvidos

equipamentos menores e mais economicos, viabilizando a implantacao, no mercado, deste novo

“produto”.

Aproveitando o contexto gerado pela globalizacao, a comunicacao movel se espalhou de forma

rapida pelo mundo, atingindo numeros comparaveis aos numeros da telefonia fixa. Atraıdos pela

mobilidade e pela variedade de servicos oferecidos pela telefonia celular, empresas a incorporaram

em seu cotidiano, assim como pessoas mudaram seu modo de vida apos a sua implantacao.

A primeira geracao (1G) da telefonia celular era analogica, mas ja em sua segunda geracao (2G),

com o avanco tecnologico e, principalmente, com o aumento da demanda do mercado e a necessidade

de privacidade, a telefonia celular se tornou digital, o que ampliou a gama de servicos ofertados e a

qualidade dos mesmos.

Atualmente, na implantacao da terceira geracao (3G), estao previstos para o sistema transmissoes

a multiplas taxas, diferentes nıveis de qualidade, podendo ser transmitidos voz, dados e multimıdia.

A tabela 1.1 apresenta uma ideia dos servicos oferecidos pela3a geracao, Stancanelli (2004).

Observando o novo mercado consumidor, nota-se uma maior exigencia de servicos e de

qualidade, criando assim a necessidade de estudos que otimizem a comunicac¸ao movel neste novo

cenario heterogeneo. Varias linhas de estudos tem sido adotadas, como por exemplo: exploracao

da diversidade espacial, temporal, de frequencia, algoritmos heurısticos aplicadosa deteccao

multiusuario ea estimacao de parametros, entre outros.

2

Tabela 1.1: Aplicacoes e requisitos para a tecnologia 3GTAXA DE

APLICAC AO BITS T IPICA BER INTOLER ANCIA[kbps] maxima A ATRASOS

voz 8 - 64 10−2

V

mensagens curtas 1,2 - 2,4 10−6

e-mail 1,2 - 64 10−6

acesso a 2,4 - 768 10−6

base de dadosdados 64 - 1920 10

−6

vıdeo telefonia 64 - 384 10−7

V

Em um sistema DS-CDMA (Direct Sequence/Code Division Multiple Acess), a deteccao e feita

atraves do detector convencional (CD -Convencional Detector), constituıdo de um filtro casado (MF

- Matched Filter) seguido de um decisor abrupto. Este detector nao garante uma recepcao otima,

pois o sinale afetado pela interferencia de multiplo acesso (MAI -Multiple Acess Interference) e nao

possui nenhum princıpio para eliminar a mesma, implicando em um sistema com capacidade muito

inferior a capacidade do canal, definida como sendo a probabilidade de erro para umunico usuario

(SuB -Single-user Bound).

Nosultimos 20 anos, foram propostos na literatura especializada varios detectores multiusuarios

(MuD - Multiuser Detector) que visam diminuir ou ate mesmo eliminar o efeito nocivo da MAI,

melhorando o desempenho do sistema ou mesmo buscando atingir o limiar de desempenho do canal,

alcancando assim uma melhoria de desempenho e minimizando custos de implantac¸ao dos sistemas

CDMA.

Sao encontrados na literatura varias publicacoes acerca da deteccao MuD, comprovando a

importancia do detector multiusuario para a viabilidade de um sistema CDMA. Em Abrao (2001),

sao destacados os MuD lineares de Mınimo Erro Quadratico Medio (MMSE - Minimum Mean

Square Error) e Descorrelacionador (Decorrelator), Canceladores de Interferencia em Paralelo

(PIC), Sucessivos (SIC) e Hıbridos (HIC). Ha tambem o detectorotimo, proposto por Verdu (1984),

Verdu (1998), e a utilizacao de tecnicas heurısticas sobre esse detector, para a diminuicao de sua

complexidade.

Devido aos bons resultados obtidos via simulacao computacional, os algoritmos heurısticos

tem se mostrado uma boa ferramenta para melhoria de desempenho dos detectores convencionais,

apresentando ainda um baixo custo de implementacao atraves de DSP.

Visualizando este cenario e as boas perspectivas deste instrumento, no presente trabalho optou-se

por estudar os algoritmos heurısticos, e de forma mais aprofundada o algoritmo baseado no movi-

mento bulicoso de partıculas (Swarm), quee uma tecnica apresentada primeiramente por Kennedy

e Eberhart (1995) e se mostrou promissora na sua versao discreta, conforme visto em Kennedy e

3

Eberhart (1997), Zhen-su Lu (2004), Zhao e Zeng (2004) e Shuyuan Yang (2004).

Neste trabalho sera realizado uma analise criteriosa do algoritmoSwarmaplicado ao problema

MuD, buscando descrever o comportamento em relacao aos seus parametros de entrada e uma

relacao otimizada dos mesmos com os parametros do sistema, verificando assim a viabilidade de

implementacao.

Esta monografia esta dividida do seguinte modo:

X Capıtulo 2 - Descreve-se neste capıtulo o sistema DS-CDMA, o quale utilizado como base de

analise para este trabalho. Sao expostos tambem os canais utilizados nas simulacoes computa-

cionais.

X Capıtulo 3 - Neste capıtulo e apresentado a deteccao MuD em um sistema DS-CDMA. Sao

exibidos tambem alguns receptores que intentam eliminar a MAI.

X Capıtulo 4 - Algumas tecnicas heurısticas de busca sao apresentadas, como programacao evolu-

cionaria e algoritmo genetico, utilizadas posteriormente como comparacao para o desempenho

do algoritmo Swarm.

X Capıtulo 5 - E apresentado aqui, de maneira detalhada, o algoritmo baseado no movimento

bulicoso de partıculas (PSO -Particle Swarm Optimization) e o algoritmoSwarmQuantico

(QPSO -Quantum Particle Swarm Optimization).

X Capıtulo 6 - Sao mostrados os resultados obtidos via simulacao Monte-Carlo do funcionamento

dos algoritmos PSO e QPSO, comparado-os com alguns outros algoritmos heurısticos e com a

deteccao otima. E apresentada tambem uma analise sobre os parametros de entrada do algo-

ritmo.

X Capıtulo 7 - Neste capıtulo de conclusao sao apresentadas as consideracoes finais sobre o algo-

ritmo PSO e algumas possibilidades de trabalhos futuros.

CAPITULO 2

CDMA

§2.1 Introducao

A tecnologia de Multiplo Acesso por Divisao de Codigo e baseada no espalhamento espectral

(SS -Spread Spectrum), Simon et al. (1994), utilizando uma banda para o sinal transmitido (BW )

muitas vezes maior que a taxa de transmissao de dados (R) de qualquer usuario. Caracteriza-se por

apresentar uma excelente capacidade de rejeicao a ruıdo, alta toleranciaa interferencia intencional

(jamming) e uma boa privacidade do sinal transmitido, conforme apresentado em Viterbi (1995).

Ao contrario das tecnologias TDMA (Time Division Multiple Acess), em que cada usuario acessa

o canal em um dado instante de tempo e FDMA (Frequency Division Multiple Acess), onde cada

usuario possui uma sub-banda da banda total do sistema, no sistema CDMA a banda total do sitema

e utilizada integralmente por todos os usuarios e nos mesmos intantes de tempo. Pode-se observar o

uso temporal e espectral do canal pelos tres metodos de comunicacao multiusuario atraves da figura

2.1.

No sistema CDMA, o que permite aos varios usuarios utilizem a mesma banda no mesmo perıodo

de tempoe a insercao de um codigo de espalhamento no sinal de cada usuario. Esse codigoe exclusivo

para cada usuario, implicando que apenas o usuario que tiver conhecimento dele podera codificar e

decodificar sua informacao. Esta caracterıstica resulta em privacidade e segurancaa comunicacao de

todos os usuarios CDMA.

§2.2 Espalhamento Espectral

O espalhamento espectral, como o proprio nome diz,e o espalhamento de um sinal no domınio

da frequencia. Isso implica no emprego de uma banda para um sinal transmitido (BW ) muito maior

2.2. Espalhamento Espectral 5

Figura 2.1: Comparacao temporal e espectral entre as tecnicas de multiplo acesso CDMA, TDMA eFDMA.

do que a banda necessaria, referentea taxa real de transmissao (R) de dados do sinal original. Basi-

camente existem dois metodos utilizados para se obter o espalhamento espectral: espalhamento por

sequencia direta e por salto de frequencia (FH -Frequency Hopping).

2.2.1 Espalhamento por Sequencia Direta

Detalhadamente mostrado em Proakis (1995), o espalhamento espectral por sequencia direta (DS -

Direct Sequence) e o mais estudado e mais utilizado atualmente nas tecnologias ja implementadas no

mercado.

Existem varias famılias de sequencias que vem sendo utilizadas para realizar o espalhamento

espectral, entre elas as pseudo-aleatorias (PN -pseudonoise), Gold, Kasami, Hadamard e algumas

outras. O proposito do estudo e da elaboracao das varias famılias de sequencias de espalhamento

e encontrar sequencias que sejam ortogonais ou apresentem uma correlacao cruzada com um valor

muito baixo.

A tecnica de espalhamento por sequencia direta baseia-se no uso de um codigo de espalhamento

c(t) quee multiplicado ao sinal modulado. Adotando-se uma modulacao BPSK, o sinal em banda

base gerado sera:

s(t) = A · m(t) · c(t) (2.1)

ondeA e a amplitude do sinal,m(t) e o bit transmitido ec(t) e o codigo (sequencia) de espalhamento,

que esta contido no intervalo[0, Tb), definido como:

c(t) =∑

n

p(t − nTc)cn (2.2)

2.2. Espalhamento Espectral 6

ondecn ∈ [+1,−1] e o pulso formatado, tambem denominado chip, cada um com duracao de Tc,

chamado perıodo dechip.

O ganho de processamento oriundo do espalhamento espectral do sinal,GP , e definido porGP =Tb

Tc. O espalhamento espectral sera proporcionalaGP , que sera maior quanto menor for o perıodo de

chip, dado um perıodo de bit constante.

t

t

t

T b

T c

c ( t )

m ( t )

s bb ( t )

Figura 2.2: Espalhamento esectral do sinal atraves de sequencia direta, visto no domınio do tempo.

Analisando a resposta espectral, figura 2.3, verifica-se que apos o espalhamento feito pela

sequenciac(t) a banda do sinale aumentada pelo fatorGP , e a amplitudee reduzida pelo mesmo

fator.

−3 −2 −1 0 1 2 30

0.5

1

1.5

2

2.5

3

3.5

4

4.5

5

Freq [Hz]

Am

plitu

de

Espalhamento Espectral

M(f)

M(f)*C(f)

Figura 2.3: Espalhamento espectral obtido por um chip retangular.M(f) e C(f) sao as respectivastransformadas de Fourier dem(t) e c(t) da figura 2.2.

No recetor opera-se o o caminho inverso: o desespalhamento do sinal transmitido atrave s de

um canal AWGN ou com desvanecimento. O sinal de dadose recuperado da forma original, porem

ruıdos AWGN e de banda estreita(jamming) e a MAI sao espalhados espectralmente, criando o efeito

de rejeicao a ruıdo.

2.3. Modelos de Canais e o sistema DS/CDMA Convencional 7

2.2.2 Espalhamento por Salto de Frequencia

O espalhamento atraves do salto de frequencia (FH -Frequency Hopping) ocorre com o uso do codigo

de espalhamentoch(t), o qual possuiKc chips. Dependendo da combinacao dosKc chips, sera

selecionada uma frequencia proveniente de um conjunto com ate Mh = 2Kc opcoes pre-definidas.

Assim, para cada perıodo total do codigo sera utilizada uma frequencia diferente.

Dados ( m ( t )) Modulador BPSK

Sintetizador de Freqüência

Seletor de Freqüência

Código de Espalhamento

Canal

Sintetizador de Freqüência

Seletor de Freqüência

Código de Espalhamento

Demodulador BPSK

Dado Estimado m ( t ) ^

Figura 2.4: Comunicacao por Salto de frequencia.

A figura 2.4 exibe como ocorre a comunicacao atraves desse metodo. O bloco Dados(m(t)) gera

a informacao a ser transmitida. O modulador BPSK modula a informacao atraves de chaveamento

digital binario de fase, assumindo o sinal ora fase0o, ora 180o. Essa informacao moduladae

multiplicada temporalmente por uma frequencia gerada atraves do sintetizador de frequencia, sendo

a frequencia sintetizada proveniente de um seletor de frequencia, que fornece uma frequencia a

sua saıda dado um codigo de espalhamento em sua entrada. O sinal multiplicado passa por um

filtro passa-alta, onde sao retiradas as frequencias que nao serao transmitidas. Apos transmissao

atraves do canal, o sinale multilicado novamente pela frequencia selecionada atraves do codigo de

espalhamento. O sinal passa por um filtro passa-baixa, selecionando-se apenas a sua componente

DC. Esse sinale entao demodulado e estimado atraves do demodulador BPSK, obtendo-se o dado

estimadom(t).

A seguir sao apresentados os dois modelos de canal utilizados para simulacoes computacionais,

o modelo de canal AWGN sıncrono e o modelo de canal com desvanecimento plano sıncrono.

§2.3 Modelos de Canais e o sistema DS/CDMA Convencional

2.3.1 Canal AWGN Sıncrono

O sinal em banda base transmitido, levando em conta todos os usuarios DS/CDMA, em um dado

instante de tempo te dado por:


sT (t) =K

∑

i=1

Ak · mk(t) · ck(t − τk) (2.3)

ondeAk e a amplitude do sinal para cada usuario k, mk(t) e o bit transmitido pelo usuario k,

ck(t − τk) e o codigo (sequencia) de espalhamento com atrasoτk para o k-esimo usuario. Neste

modelo,e observado que nao ocorre atraso entre as transmissoes de usuarios diferentes,τk = 0,∀k,

caracterizando uma transmissao sıncrona.

O sinal de todos os usuarios e entao transmitido atraves do canal, sendo adicionado a ele o

ruıdo Gaussiano branco (AWGN -Additive White Gaussian Noise), n(t). Esse ruıdo possui uma

distribuicao Gaussiana, com media igual a zero e varianciaσ2r = No

2 . O sinal recebido em banda base

contendo a soma dos sinais de todos os usuarios,e da forma:

r(t) =K

∑

k=1

Ak · mk(t) · ck(t) + n(t) (2.4)

O esquematico para a transmissao-canal-recepcaoe mostrado na figura 2.5:

c 1 ( t - iT )

c 2 ( t - iT )

c K ( t - iT )

y 1 ( i )

y 2 ( i )

y K ( i )

b 1 ( i ) ^

b 2 ( i ) ^

b K ( i ) ^

m 1 ( t )

c 1 ( t - iT )

c 2 ( t - iT )

c K ( t - iT )

m 2 ( t )

m K ( t )

cos( w c t )

cos( w c t )

cos( w c t )

s( t ) Canal AWGN

s( t )+ n ( t )

cos( w c t )

cos( w c t )

cos( w c t )

Figura 2.5: Modelo de transmissao do sistema DS/CDMA sıncrono em canal AWGN.

Na figura 2.5, ve-se a informacao mk(t) do k-esimo usuario, sendo espalhada espectralmente

atraves do produto com a sequencia de espalhamentock(t − iT ). O sinale entao transformada para

banda passante atraves do produto comcos(wct). Ocorre entao a soma de todos os sinais, quee

transmitido atraves do canal AWGN. O sinale entao transformado em banda base, ocorre novamente

o produto pela sequencia de espalhamento, o sinal obtidoe integrado durante um perıodo de bit e o

bit estimadobk(t) e obtido atraves de um decisor abrupto.


2.3.2 Canal com Desvanecimento Plano Sıncrono

Considerando um canal Rayleigh plano, ha tambem o efeito de atenuacao e distorcao do sinal, que

sera inserido atraves do coeficiente complexocc(t), definido por:

cc(t) = β(t, f) · ejθ(t,f) (2.5)

Atraves da equacao acima,e constatado que o coeficiente complexoe responsavel por alterar a

amplitude e tambem a fase do sinal recebido. Quando a comunicacao caracteriza-se ela ausencia

de linha de visada (NLOS -non-light of sight), o modulo decc(t) e obtido atraves de um gerador

de numeros aleatorios com distribuicao Raileigh, e a fasee obtida com um gerador de numeros

aleatorios com distribuicao uniforme, Silva (2004).

Adicionalmente, considerando que o canale lento, ou sejaTb << (∆t)c do canal,β(t, f) e

θ(t, f) serao assumidos constantes durante o intervalo de sımbolo,Tb. (δt)c e o tempo de coerencia

do canal, Abrao (2001), Proakis (1995), sendo um indicativo do intervalo temporal em que as

caracterısticas de canal nao sofrem alteracoes.

Considerando ainda que o canale plano (flat), logo BW = 1Tc

< (∆Bc) do canal,β(t, f)

e θ(t, f) serao considerados constantes para a banda de transmissao utilizada. ∆Bc e a banda

de coerencia do canal, Abrao (2001), Proakis (1995), sendo um indicativo da banda em que as

caracterısticas de canal nao sofrem mudancas.

Adicionando-se entao esse efeito, juntamente com o AWGN, tem-se a expressao para o sinal

recebido, em banda base:

r(t) =K

∑

k=1

Ak · mk(t) · cck(t) · ck(t) + n(t) (2.6)

ondecck(t) = βk(t) + ejθk(t).

CAPITULO 3

DETECCAO M ULTIUSU ARIO

A capacidade de um sistema DS/CDMAe limitada pelos efeitos do canal e ainda pelo interferencia

multiusuario (MAI). O detector convencional possui um princıpio de funcionamento que elimina

apenas os efeitos do canal, ee muito susceptıvel ao efeitonear-far (NFR), nao possuindo meios para

amenizar o efeito da MAI. Considerando esse problema, foi previsto uma melhoria do desempenho

do sistema atraves do uso das demais informacoes atraves dos sinais enviados pelos outros usuarios.

O ganho evidente de desempenho dos sistemas apos o uso de um detector multiusuario e

muito atrativo, e varias linhas de pesquisa tem sido seguidas. Os detectores subotimos lineares

de Descorrelacao e MMSE (baseado no mınimo erro quadratico) apresentaram bons resultados.

Algumas tecnicas de cancelamento subtrativo (SIC, PIC, DF-ZF) tambem se mostraram eficientes,

porem requerem o conhecimento dos usuarios de interesse e dos interferentes do sistema. O detector

de maxima verossimilhanca (otimo), Verdu (1984) e Verdu (1998), e metodos de busca heurısticos

tambem vem sendo estudados e tem mostrado resultados passıveis de implementacao no atraves dos

recentes avancos da tecnica DSP.

E essencial, porem, considerar o compromisso DesempenhoversusComplexidade para os varios

detectores projetados. Por exemplo, tem-se um bom desempenho do detector de descorrelacao para

sistemas sem controle de potencia, porem se o sistema possuir muitos usuarios, a complexidade de

sua realizacaoe inviavel devidoa inversao da matriz de correlacaoR. Para os receptores PIC e SIC,

embora nao se utilize a matrizR−1, o que implica numa menor complexidade, deve-se analisar o

grau de conhecimento dos usuarios interferentes, para verificar see possıvel obter algum ganho de

desempenho.

Neste capıtulo sera abordado a deteccao MuD para canais AWGN, ou seja, o canale constituıdo

apenas do efeito do ruıdo gaussiano branco e tambem a MuD para canal com desvanecimento plano

(Rayleigh).

3.1. Descorrelacionador 11

§3.1 Descorrelacionador

A deteccao atraves da descorrelacao depende do sinal recebido pelo filtro casado, ao quale apli-

cado uma transformacao linear. A decisao do bite realizada atraves da equacao:

b = sgn(y · T) (3.1)

ondey e o sinal obtidoa saıda do banco de filtros casados eT e a transformacao linear do receptor.

No caso do Descorrelacionador, a transformacao lineare dada porT = R−1.

Um aspecto importante desse metodo e a independencia em relacao ao conhecimento das

potencias transmitidas pelos usuarios interferentes. Ha, porem, a necessidade, em canais com

desvanecimento, do conhecimento das estatısticas de canal. Assim, a decisao do sımbolo sera dada

por:

b = sgn(zk ∗ cck(i)) (3.2)

ondecck e o coeficiente complexo do canal para o k-esimo usuario ezk = tk · y, comtH

k = k−esima

linha da matriz de transformacao linear e o operador Hermitiano(.)H corresponde a uma transposicao

seguida de conjugacao complexa. O diagrama do detector de descorrelacaoe

r ( t )

c 1 ( t - iT )

c 2 ( t - iT )

c K ( t - iT )

y 1 ( i )

y 2 ( i )

y K ( i )

z 1 b 1 ( i ) ^

z 2 b 2 ( i ) ^

z 1 b K ( i ) ^

R -1

Figura 3.1: Diagrama do detector Descorrelacionador.

A probabilidade de erro de sımbolo para o k-esimo usuario e dada por:

PeDecork = Q

(

Ak

σ√

[R+]kk

)

(3.3)

onde[R+]kk denota selecao do kk-esimo elemento da matrizR+, σn e o desvio padrao do ruıdo

AWGN eR+ e a matriz pseudo-inversa deR, Verdu (1998).

3.2. MMSE - Mınimo Erro Quadr atico Medio 12

§3.2 MMSE - Mınimo Erro Quadr atico Medio

O detector MuD baseado no criterio de minimizacao do erro quadratico medio considera nao

apenas a correlacao cruzada dos usuarios interferentes, como faz o Descorrelacionador, mas tambem a

potencia do canal AWGN e dos usuarios interferentes. A desvantagem desse receptore a necessidade

de conhecimento das potencias dos usuarios interferentes do canal AWGN.

T = [R + σ2n · A−2]−1 (3.4)

comσ2n · A−2 = diag

{

σ2n

A2

1

, σ2n

A2

2

, ..., σ2n

A2

K

}

.

O esquematico do detector pode ser visto na figura 3.2.

r ( t )

c 1 ( t - iT )

c 2 ( t - iT )

c K ( t - iT )

y 1 ( i )

y 2 ( i )

y K ( i )

z 1 b 1 ( i ) ^

z 2 b 2 ( i ) ^

z K b K ( i ) ^

(R+ σ 2 A -2 ) -1

Figura 3.2: Diagrama do receptor MMSE.

A decisao do sımbolo ou bite feita por

bk = sgn(

[R + σ2n · A−2]−1 · y

)

k(3.5)

Considerando o caso particular de sinais equicorrelacionados (ρij = ρjk = ρ, ∀i, j) e controle

erfeito de potencia (Ai = Aj = A, ∀i, j), a probabilidade de erro do detector MMSE simplifica-se,

Verdu (1998):

PeMMSE1 = Q

(

A

σ

√

1 − ρ2(K − 1)

1 +(

σA

)2+ ρ(K − 2)

)

(3.6)

§3.3 DetectorOtimo (ML)

O detectorotimo (ML - Maximum Likelihood) baseia-se na funcao de maxima verossimilhanca

para a obtencao da deteccao otima, mostrado em Verdu (1984) e Verdu (1998). O detector ML

3.3. DetectorOtimo (ML) 13

consiste de um detector de maxima verossimilhanca, precedido por um banco de filtros casados, que

fornecera o vetor de amplitudesy. A funcao de maxima verossimilhancae dada por:

b = arg

{

maxb∈{+1,−1}K

2Re{yTCHAb} − bTCARACHb

}

(3.7)

comb ∈ {+1,−1}K sendo os possıveis vetores solucoes para o problema, ondeC e uma matriz

diagonal que possui os coeficientes complexos do canal,A e uma matriz diagonal com a amplitude

dos sinais de todos os usuarios,y e o sinal recebido. O vetor solucao sera aquele que maximizar a

expressao acima. Em canal AWGN sıncrono, a equacao 3.7 se reduz a:

b = arg

{

maxb∈{+1,−1}K

2Re{yTAb} − bTARAb

}

(3.8)

O incoveniente deste detectore o aumento da sua complexidade com o aumento do numero de

usuarios, dado que o conjunto de vetoresb a serem avaliados na funcao de maxima verossimilhanca

cresce exponencialmente com o numero de usuarios, da forma2K . Isso torna a implementacao desse

detector inviavel por esse ponto de vista, embora o seu desempenho sejaotimo.

Buscando melhorar o compromisso proposto, vem sendo estudado o uso de tecnicas heurısticas

de otimizacao para tentar minimizar a complexidade, diminuindo o universo de busca das possıveis

solucoes, e ainda manter um bom desempenho, proximo ao detectorotimo.

CAPITULO 4

T ECNICAS HEURISTICAS DE BUSCA

Os algoritmos heurısticos sao metodos de otimizacao baseados na aproximacao progressiva de um

dado problema. Consiste basicamente no uso de uma funcao objetivo (custo) que avalia possıveis

solucoes para o problema. O que diferencia os diversos metodos heurısticose o modo comoe inserido

disturbios nas possıveis solucoes e comoe criado um novo grupo de candidatos a serem avaliados.

A seguir sao explicados alguns algoritmos heurısticos de busca, baseados na teoria evolucionaria de

Darwin, sendo exibidos os fatores responsaveis pela diferenciacao entre as geracoes. Esses fatores

sao a mutacao, a clonagem e ocrossover, mostrados em de Castro e Fernando J. Von Zuben (2002),

H.S. Lim e Chuah (2003), Ergum e Hacioglu (2000), Ciriaco et al. (2004) e Abedi (2001).

§4.1 Programacao Evolucionaria (EP)

Primeiramente serao definidos alguns conceitosuteis para um melhor entendimento do algoritmo

aplicadoa deteccao MuD.

X Indivıduo: E um vetor de bits pertencente ao universo de possıveis solucoes para o problema;

X Populacao (D): E um conjunto de indivıduos, presentes em uma geracao. Para definir o numero

de indivıduos da populacao inicial, e utilizada a equacao encontrada por e R.S. Ramakrishna

(2002):

D = 10 ·⌊

0.3454(√

πK + 2)⌋

(4.1)

onde o operador⌊·⌋ retorna o maior valor inteiro contido no argumento.

X Geracao: E a iteracao em que se encontra a busca.

X Funcao Objetivo/Custo:E a funcao utilizada para avaliar o desempenho de cada indivıduo.

4.1. Programacao Evolucionaria (EP) 15

A programacao evolucionaria (EP -Evolutionary Programming), H.S. Lim e Chuah (2003) e

Ciriaco et al. (2004),e baseada na teoria evolucionaria de Darwin. Os indivıduos se alteram de uma

geracao para a proxima atraves apenas do operador mutacao. Nota-se, neste algoritmo, a presenca

apenas de um fator de diversificacao, nao se utilizando nenhum fator de intensificacao. No problema

de deteccao multiusuario e utilizado como indivıduo inicial a saıda do banco de filtros casados, uma

vez que esse detector ja apresenta uma possıvel solucao, melhor que um primeiro indivıduo aleatorio.

A populacao inicial e obtida atraves da aplicacao do operador mutacao sobre o indivıduo inicial,

figura 4.1.a.

1 1 0 1 0 0 1 1 0 0 0 1 1 1

1 1 0 1 1 1 0

1 0 1 1 0 0 0

1 1 0 1 1 1 1 1 0 0 0 0 0 1

crossover

1 1 0 1 1 1 0 1 1 0 1 1 1 0

0 0 1 1 0 1 0 mutação

clonagem

Geração g Geração g + 1

(a)

(b)

( c )

Figura 4.1: Exemplos de operadores geneticos: a)mutacao; b)clonagem; c)crossover.

O algoritmo EPe implementado do seguinte modo:

1. Gera-se a populacao inicial, contendoD indivıduos. Cada indivıduoe um vetor da forma:

si = Si ∼ U{−1, +1}K . i = 1, 2, ..., D

ondeSi e um vetor aleatorio esi e a saıda do vetor aleatorio

si = [si,1...si,K ]T

sendo queU{−1, +1}K representa um vetor binario de dimensao K com valores discretos±1

equiprovaveis. Em alguns casos, costuma-se utilizar, como indivıduo da populacao inicial a

saıda do detector convencional:

s1 = bCD = sign(y)

2. Cada indivıduoe avaliados atraves da funcao custo, dada, para o caso AWGN sıncrono, por:

f(

s(i))

={

2Re{yTCHAs(i)} − s(i)T

CARACHs(i)}

(4.2)

3. Os indivıduos sao alterados pelo operador mutacao:

si+D,j = sign{si,j + Nj(0, σ2)}. j = 1, 2, ..., K

4.2. Programacao Evolucionaria com Clonagem (EP-C) 16

sendo quesi,j representa o j-esimo elemento do i-esimo indivıduo. Nj(µ, σ2) representa uma

variavel aleatoria Gaussiana com mediaµ e varianciaσ2, sendo este numero gerado para cada

elementoj de cada indivıduoi.

O aumento da variancia da variavel aleatoria Gaussiana indica um aumento na diferenciacao

dos indivıduos gerados em relacao aos seus predecessores.

4. Em seguida,e calculado o valor da funcao custo para todos os novos indivıduos gerados:

f(

s(i+D))

={

2Re{yTCHAs(i+D)} − s(i+D)T

CARACHs(i+D)}

(4.3)

5. Entre a geracao antecessora e os indivıduos modificados atraves da mutacao sao selecionados

para a proxima geracao osD indivıduos que apresentarem o maior desempenho em termos da

funcao custo. Os outros sao descartados.

6. Finalmente, retorna-se ao passo 3, repetindo-se os passos subsequentes esses passos ate que

um numero de geracoes pre-definido seja atingido. O numero de geracoes necessarias ira variar

conforme a complexidade do sistema, istoe, numero de usuarios, relacao sinal-ruıdo, controle

ou nao de potencia.

§4.2 Programacao Evolucionaria com Clonagem (EP-C)

Este algorimtoe semelhante ao de programacao evolucionaria, todavia ele utiliza o operador

clonagem, figura 4.1.b, que se trata de um operador de intensificacao, juntamente com o operador

mutacao, para analisar o universo de busca. Esse operadore inserido da seguinte forma no algoritmo,

durante a etapa de selecao:

5.b Realiza-se a selecao de uma percentagemic dos indivıduos, atraves do criterio do maior valor

de funcao custo. Cada um desses indivıduos selecionados sera clonadoIc vezes, de modo que

Ic = M = D.ic. Ao final da clonagem tem-se novamente p indivıduos para a proxima geracao.

Esse operador ajuda a produzir uma geracao futura mais evoluıda em relacaoa geracao anterior.

§4.3 Algoritmo Genetico (GA)

O algoritmo genetico (GA -Genetic Algorithm) aplicado ao problema MuD foi apresentado em

Ergum e Hacioglu (2000) e Ciriaco et al. (2004); trata-se de um algoritmo semelhante aos dois algo-

ritmos ja apresentados, baseado na teoria evolucionaia de Darwin. Alem dos operadores mutacao e

4.3. Algoritmo Genetico (GA) 17

clonagem, ele utiliza ainda o operadorcrossover, figura 4.1.c, buscando tambem diversificar o uni-

verso de busca.

Assim como na genetica, o operadorcrossovere responsavel por criar indivıduos com carac-

terısticas mescladas entre os seus predecessores. Isso produz uma geracao que apresentara uma

selecao das melhores caracterısticas de cada indivıduo da geracao passada inserida nela, aumentando

assim o grau de evolucao da populacao.

O algoritmo geneticoe elaborado a partir dos seguintes passos:

1. Cria-se a populacao inicial, gerada de forma aleatoria. Para o caso MuD, pode-se utilizar

tambem como populacao inicial o primeiro indivıduo sendo a saıda do detector convencional e

o restante dos indivıduos gerados aleatoriamente, conforme mostrado abaixo:

s(i)1 = b(i) (4.4)

Cada um dos outrosp − 1 indivıduose um vetor da forma:

si = Si ∼ U{−1, +1}K . i = 1, 2, ..., D

ondeSi e um vetor aleatorio esi e a saıda do vetor aleatorio

si = [si,1...si,K ]T

sendo queU{−1, +1}K representa um vetor binario de dimensao K com valores discretos±1

equiprovaveis.

2. E avaliada a funcao custo para todos essesD indivıduos, atraves da equacao (4.2).

3. E feita uma selecao deM indivıduos entre a populacaoD atraves da analise da funcao custo.

O valor deM deve ser escolhido obedecendo alguns criterios:

(a) Deve-se selecionar um numeroM de indivıduos na faixa2 ≤ M ≤ D.

(b) A escolha de um numero muito pequeno de indivıduos implica em uma geracao posterior

mais evoluıda, porem existe a possibilidade de se encontrar uma maximo local da funcao

custo, implicando em uma solucao nao otimizada.

(c) A escolha de um numero muito grande paraM pode implicar na presenca de indivıduos

com caracterısticas nao tao boas nas geracoes futuras, implicando em uma demora na

busca pela solucaootima (convergencia lenta).

4. E aplicado o operadorcrossoveraosM indivıduos selecionados. Observa-se que a aplicacao

desse fator implica na transmissao de caracterısticas dominantes para as geracoes futuras. O

operador utilizado neste trabalhoe crossover uniforme. Esse operadore realizado da seguinte

forma:

4.3. Algoritmo Genetico (GA) 18

(a) Seleciona uma alta probabilidade decrossover(pc proximo a 0,9).

(b) Seleciona-se dois indivıduos entre osM previamente escolhidos.

(c) E gerado uma vetor aleatorio de bits, com dimensaoK, possuindo apenas os valores+1

e0. E considerado que cada genee um possıvel ponto decrossover.

(d) Avalia-se o vetorcrossover, se o bit for1, ocorrera troca de genes entre os genitores, caso

o bit seja 0, nao se realiza a troca.

(e) Sao gerados novos indivıduos ate que se atinja um numero deD descendentes.

5. Aplica-se o operador mutacao sobre os indivıduos gerados na etapa anterior. Esse operador

e mais eficiente para uma probabilidade de atuacao, im, inferior a 0,1. Elee implementado

atraves da geracao de um vetor aleatorio comK elementos, responsavel por inserir perturbacoes

no genes; caso o valor gerado seja suficientemente grande para provocar uma troca do sinal

do gene, entao ocorrera a mutacao. Caso a perturbacao seja muito pequena, nao ocorrera a

mutacao.

descendente = sign(

genitor + N(

0, σ2))

(4.5)

ondeN(

0, σ2)

indica uma distribuicao Gaussiana com media0 e varianciaσ2.

6. Avalia-se os indivıduos atraves da funcao custo, equacao (4.3) para todos os indivıduos gerados

apos o processo de mutacao.

7. Seleciona-se osD melhores indivıduos entre os genitores e os descendentes obtidos na geracao

atual e na geracao genitora para compor a proxima geracao.

8. Retorna-sea etapa 3 e repete-se o processo ate que um numero de geracoes pre-definido seja

atingido.

CAPITULO 5

ALGORITMO Swarm

§5.1 Historico

Observando o comportamento dos passaros, alguns pesquisadores ficaram intrigados com o

comportamento em bando desses animais. Embora esses passaros parecesem voar aleatoriamente,

com o decorrer do tempo, eles apresentavam a tendencia a se agrupar, formando os bandos. Chamou

a atencao o modo como todos os integrantes do grupo sao capazes de mudarem a sua direcao de

movimento quando ocorre a mudanca repentina na direcao de apenas um integrante, mantendo uma

sincronia no movimento do grupo. Eles se favorecem do conjunto para obterem maior sucesso em

sua busca por alimentos e em possıveis fugas de predadores, e o fato de um integrante do bando ter

mudado de direcao, significa que ele encontrou algo de interesse proprio, porem que interessaas

outras aves do bando.

Observou-se a grande vantagem adquirida pelo bando, devido ao seunorteamento para a

trajetoria do integrante do grupo que esta em melhor situacao comparado aos outros, aumentando

assim a chance de sucesso para o objetivo do grupo.

Esse mesmo comportamento tambem foi observado e estudado por E. O. Wilson, Kennedy e

Eberhart (1995), para o caso dos cardumes de peixes.E visıvel que com este metodo, cada indivıduo

em particular pode aproveitar da descoberta feita por qualquer integrante do cardume, aumentando a

chance de sobrevivencia para todos.

Comparando-se o desempenho entre os grupos de animais e os animais sozinhos, observa-se que

existe uma grande vantagem evolucionaria para os indivıduos que conseguem interagir com seus

semelhantes para trocar informacoes. Atraves deste princıpio, foi entao imaginado a otimizacao

baseada no movimento bulicoso de partıculas (Swarm).

5.2. Algoritmo Swarm 20

§5.2 Algoritmo Swarm

5.2.1 Princıpio do Algoritmo

O algoritmoe baseado no movimento de um grupo de partıculas, distribuıdas aleatoriamente no

espaco, cada uma possuindo uma posicao e uma velocidade proprias. Essa velocidadee responsavel

por inserir um movimento na partıcula, alterando a sua posicao no espaco em busca de um melhor

desempenho. A equacao para a posicao da partıculae dada pela expresscao:

pid[t] = pid[t − 1] + vid[t − 1] (5.1)

ondepid[t] e a posicao do i-esimo usuario na d-esima dimensao e instante de tempot, evid[t− 1] e a

velocidade do i-esimo usuario na d-esima dimensao, no instante de tempot − 1.

A interacao entre as partıculas, quee a base do algoritmoSwarm, e inserida no calculo da ve-

locidade das partıculas. O conhecimento da melhor posicao encontrada por qualquer partıcula no

conjunto, chamadapbestgd [t], e adicionadaa velocidade de todas as partıculas, criando uma compo-

nente que ira na direcao da posicao dessa partıcula. A velocidade parcial, relacionada a esse conceito

e dada por:

Sepid > pbestgd [t] entao vid[t] = vid[t − 1] − rand() · φ2 (5.2)

Sepid < pbestgd [t] entao vid[t] = vid[t − 1] + rand() · φ2

onderand() e um numero aleatorio contido no intervalo [0,1] eφ2 e a constante de intensidade de

deslocamento em direcaoa melhor posicao global.

Outro fator que influencia na busca da melhor posicao, sendo inserido no calculo da velocidadee

o conhecimento da melhor posicao encontrada pela partıcula individualmente(pbestid [t]). A velocidade

referente a esse fatore

Sepid > pbestid [t] entao vid[t] = vid[t − 1] − rand() · φ1 (5.3)

Sepid < pbestid [t] entao vid[t] = vid[t − 1] + rand() · φ1

ondeφ1 e uma constante de intensidade de deslocamento em direcao a melhor posicao encontrada

pela partıcula.

O terceiro fator que afeta o calculo da nova velocidade da partıcula e a velocidade previa da

propria partıcula, que deve ser inserida no calculo da velocidade futura. Considerando que o peso

da velocidade previa no calculo da velocidade presentee 1, deve-se ajustar os valores deφ1 e φ2 de

modo que suas expressoes tambem possuam peso 1. Como o termorand() possui uma media igual


a 0,5, serao utilizados os valoresφ1 = φ2 = 2.

A figura 5.1 mostra de forma grafico o calculo da velocidade de uma partıcula, exibindo o vetor

v[t] = v[t − 1] + v(pid) + v(pdg), responsavel por causar uma perturbacao na partıcula.

v ( t -1)

v ( pid )

v ( pgd )

v( t )

Figura 5.1: Representacao vetorial da insercao de velocidade em uma partıcula no instante de tempot.

A expressao final para a velocidade, adicionando-se os tres fatores responsaveis pela mudanca de

direcao, dada pelas contribuicoes da velocidade anterior, direcao de sua melhor posicao e direcao da

melhor posicao encontrada pelo conjunto,e:

vid[t + 1] = ω ∗ vid[t] + φ1 · randid()(pbestid [t] − pid[t]) + φ2 · randid2

()(pbestgd [t] − pid[t]) (5.4)

ondevid[t] e a velocidade do i-esimo usuario na d-esima dimensao no instantet, ω e o peso da

velocidade anterior no calculo da velocidade presente erandid() erandid2() sao numeros aleatorios

gerados para uma dimensaod de uma partıculai.

Ajustes ao sistema devem ser realizados de modo que o algoritmo possua um melhor desem-

penho. Promover variacoes entre os coeficientesω, φ1 eφ2 e o metodo mais eficiente para se atingir

este resultado. Analises podem ser realizadas, buscando encontrar valoresotimos para os diversos

parametros, dependendo da aplicacao. Isso pode ser feito de modo empırico, admitindo nao possuir

nenhum conhecimento do funcionamento do algoritmo, variando de forma aleatoria os valores desses

tres parametros e obtendo a situacao que apresenta o melhor desempenho. Poreme mais conveniente

que se estude o algoritmo primeiramente, entendendo o funcionamento do mesmo ebuscando,

atraves de uma analise detalhada de cada fator, prever os valores que apresentem uma maior chance

de sucesso, diminuindo assim consideravelmente o tempo dispendido.


5.2.2 SwarmAplicado a Deteccao Multiusuario

A aplicacao do algorimto Swarm estudada nesse trabalhoe a deteccao multiusuario. Esta aplicacao

implica na adaptacao do algoritmo a um modelo discreto, adotando alguns metodos probabilısticos.

Primeiramente, deve-se considerar o numero de dimensoes (D), como sendo o numero de usuarios

do sistema, implicando assim que cada partıculai sera representada por um vetor da forma

pi = [pi,1, pi,2, ..., pi,K ] (5.5)

Para esse modelo, cada elemento do vetor (pid) podera assumir apenas os valores “0” ou “1”, que

sao os possıveis valores enviados pelos usuarios do sistema. Isso implica na necessidade da inclusao

de um modo de escolha da posicao de modo discreto. Issoe realizado inserindo no algoritmo um

comando de escolha dependente da velocidade. Porem, a velocidade precisa entao ser ajustada ao

modo probabilıstico. Varias funcoes matematicas possuem essa caracterıstica, sendo adotado neste

trabalho a funcao sigmoide, definida da forma:

S(vid) =1

1 + e−vid

(5.6)

Essa funcao possui a caracterıstica de ser limitada no intervalo [0,1], atendendoa necessidade do

nosso problema. A figura 5.2 mostra o comportamento grafico da funcao:

−6 −4 −2 0 2 4 60

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

x

S(x

)

Figura 5.2: Representacao grafica da funcao sigmoide.

Visualizando o grafico, observa-se que a funcao possui a convergencia para 0 quandox → −∞e 1 parax → ∞, conforme descrito previamente.

A selecao da posicao futura da partıculae realizada do seguinte modo:

SeS(vid) > ρid, entaoxid = 1, senaoxid = 0, (5.7)


ondeρid e um vetor de numeros aleatorios distribuıdos uniformemente no intervalo [0,1].

Um possıvel problema para algoritmos desse tipoe a incapacidade de fugir de maximos

(ou mınimos) locais, causando possıveis falhas na otimizacao. Partindo desta necessidade de

diversificacao maior do universo de busca (fuga de maximos locais),e adicionado ao modelo do

algoritmo o fatorVmax, que e responsavel por limitar a velocidade, equacao (5.4), no intervalo

[−Vmax, Vmax]. Isso insere no calculo da velocidade uma probabilidade mınima de que, ainda

que a chance de troca do bit e consequente melhoria do desempenho seja mınima, que isso ocorra,

possibilitando a saıda de possıveis maximos locais. Neste trabalho, valores entre 3 e 4 mostraram-se

bons para para o tipo de aplicacao analisado.

Partindo dos conceitos basicos de um algoritmo heurıstico, se faz necessario realizar uma analise

comportamental do algoritmo. Advem a necessidade de distinguir os fatores de intensificacao e de

diversificacao para a obtencao de melhores resultados. Analisando a equacao (5.4), ve-se que ha

dois fatores de intensificacao. Um delese o termo referentea velocidade anterior, que ira implica

na tendencia da partıcula seguir na mesma direcao indicada pela sua velocidade anterior. Outro

fator de intensificacao e o termo referentea melhor posicao global obtida, implicando em uma

busca de todas as partıculas sobre umunico maximo. Assim como os fatores de intensificacao,

os fatores de diversificacao tambem sao dois. Um delese o termo referentea melhor posicao

individual encontrada ate aquele momento, nao importando em que instante ocorreu, o que implica

em alta probabilidade das partıculas efetuarem a busca pelo valorotimo em locais diferentes. O

outro fator responavel pela diversificacao e a constanteVmax, responsavel por garantir uma chance

mınima de troca, dada por1 − S(Vmax), tanto para o bit “0” como para o bit “1”. A tabela 5.1

mostra a probabilidade mınima de troca de bit em funcao do valor deVmax. Essa probabilidade

ira ocorrer toda vez que a velocidade da partıcula ultrapassar o limite estabelecido por[−Vmax, Vmax].

Tabela 5.1: Probabilidade mınima de troca de bit com o uso deVmax.Vmax 100 · {1 − S(Vmax)}[%]

1 26, 902 11, 923 4, 744 1, 805 0, 67

5.2.3 Estrutura do Algoritmo

O algorimto pode ser elaborado seguindo os seguintes passos:

1. E gerado uma populacao inicial contendoD partıculas, cada partıcula contendo uma posicao

representada por K-dimensoes, representadas de forma binaria. Admitindo que o detector con-

vencional possui um desempenho valido, pode-se adotar a partıcula incial da populacao como

5.3. Algoritmo SwarmQuantico 24

sendo a saıda do detector convencional, e as outras geradas de forma aleatoria a partir dessa

partıcula.

2. Deve-se avaliar cada partıcula (posicao) atraves da funcao custo:

f (pi) = 2Re{yTCHApi} − pTi CARACHpi (5.8)

com i = 1, 2, ..., D. Encontra-se o melhor desempenho global armazenando-o empbestg e o

melhor desempenho de cada partıculae armazenado empbesti .

3. Calcula-se a velocidade de cada partıcula atraves da equacao (5.4).

4. Atualiza-se a posicao de cada partıcula atraves de (5.7).

5. Volta-se para o passo 2 ate se alcancar o numero de iteracoes previamente estabelecido.

§5.3 Algoritmo SwarmQuantico

Recentemente publicado na literatura por Shuyuan Yang (2004), esse algoritmo foi apresentado

como possuindo um melhor desempenho que outros algoritmos heurısticos e ainda possuir uma baixa

complexidade, o que torna importante a analise do mesmo neste trabalho.

No contexto atual da ciencia, observa-se a comunicacao entre diversasareas de pesquisa e a

importancia desse fator para o desenvolvimento mais rapido da tecnologia. Essee o caso da fısica,

que vem fornecendo um conhecimento mais aprofundado da natureza e vice-versa. Observando o

mecanismo de evolucao das especies, foi desenvolvido varios algoritmos heurısticos, e um deles, o

Recozimento Simulado (SA - Simulated Annealing)e o exemplo classico de interacao entre difer-

entesareas de estudo, uma vez que se baseia na teoria evolucionaria e tambem na termodinamica.

O objetivo do algoritmo Swarm quantico consiste em utilizar o princıpio biologico do algoritmo

Swarm, baseado no comportamento de grupo de diversos animais, com o princıpio fısico da mecanica

quantica.

5.3.1 Princıpios do Algoritmo

Na teoria quantica, umqubit e definido como sendo a menor unidade que carrega informacao, as-

sumindo qualquer valor no intervalo[0, 1]. Neste algoritmo, as partıculas com energia quantica sao

definidas do seguinte modo:

Q[t] = [q(1)[t],q(2)[t], ...,q(D)[t]], (q(i)[t] = [q(i)1 [t], q

(i)2 [t], ..., q

(i)K ][t]) (5.9)


ondeK e o comprimento da partıcula (igual ao numero de usuarios no caso MuD),D e o tamanho da

populacao eq(i)j [t] deve estar dentro do intervalo0 < q

(i)j [t] < 1.

Para o problema MuD, o termoq(i)j [t] indica a probabilidade de um bit ser0, necessitando esse

termo ser discretizado. No algoritmoSwarmoriginal, e utilizada a funcao sigmoide, por apresentar

boas caracterısticas. No caso do algoritmo quantico, sera utilizado apenas uma observacao aleatoria.

Para cadaq(i)j [t], sera gerado um numero aleatorio com distribuicao uniforme,rand(i, j), que sera

discretizado da seguinte forma:

Se rand(i, j) > q(i)j [t] entao (5.10)

p(i)j [t] = 1

Senao

p(i)j [t] = 0

ondep(i)j [t] e a j-esima componente da i-esima partıcula discretizada correspondente aq

(i)j [t].

Como noSwarmoriginal, o algoritmo QPSO possui memoria para armazenar os valores de mel-

hor posicao ja encontrada para cada partıcula e a melhor posicao global. Neste caso, sao calculados

valores de energia quantica, a partir desses valores de memoria, para provocar a alteracao na posicao

das partıcula.

Qmg[t] = α × pmg[t] + β × (1 − pmg[t]) (5.11)

Qmi[t] = α × p(i)mi[t] + β × (1 − p

(i)mi[t]) (5.12)

ondepmg[t] representa a melhor posicao ja encontrada ate aquele momento ep(i)mi[t] e a melhor

posicao de cada partıcula ate aquele instante de tempo. Os parametrosα eβ sao de controle que irao

representar o degrau para a funcaoQ, devendo obedecer o compromissoα + β = 1, 0.

A mudanca de posicaoe controlada pela funcaoQ, definida por:

Q[t + 1] = c1 × Q[t] + c2 × Qmi[t] + c3 × Qmg[t] (5.13)

onde c1 + c2 + c3 = 1, 0. Os termosc1, c2, c3 representam os pesos para cada componente,

implicando na possibilidade de aumentar a importancia da melhor posicao ja encontrada ate aquele

instante (Qmg[t]) ou da melhor posicao encontrada individualmente (Qmi[t]) ou ainda o fator da

energia contida no instante de tempo passado.

5.3.2 Estrutura do Algoritmo

O algoritmo pode ser implementado do seguinte modo:


1. Define-se as variaveis de entradaα, β, c1, c2, c3, comα + β = 1, 0; c1 + c2 + c3 = 1, 0 e

α, β, c1, c2, c3 ∈ R+.

2. Inicializa-se os valores deQ[t] em (5.9) de forma aleatoria. Obtem-se tambem os valo-

res deP[t], atraves da decisao por observacao aleatoria, citada anteriormente.P[t] =

[p(1)[t],p(2)[t], ...,p(D)[t]] ep(i)[t] = [p(i)1 [t], p

(i)2 [t], ..., p

(i)K [t]].

3. Avalia-sep(i)[t] atraves da funcao custo

f(

p(i))

= 2Re{yTCHAp(i)} − p(i)TCARACHp(i) (5.14)

4. Armazena na memoria as melhores posicoes individual e global (p(i)mi[t] e pmg[t]), obtidas

atraves da avaliacao das partıculas pela funcao custo.

5. Altera-se a energia das partıculas,Q[t], discretizando-as em seguida para obterP[t], atraves de

(5.10).

6. Avalia-seP [t] atraves da funcao custo.

7. Atualiza os valores das melhores posicoes na memoria.

8. Volta-se ao passo 5, repetindo esse processo ate que se atinja o numero de iteracoes pre-

estabelecido.

CAPITULO 6

RESULTADOS NUM ERICOS

Foram realizadas inumeras simulacoes computacionsis visando a otimizacao e confirmacao da

eficacia dos algoritmos PSO e QPSO discretos, mais especificamente para o problema de deteccao

multiusuario em sistemas DS-CDMA.

A analise do algoritmoe apresentado inicialmente de forma isolada e, posteriormente, realizadas

comparacoes entre os resultados obtidos com o PSO e o QPSO e resultados obtidos com os algorit-

mos EP-C e GA. Esses resultados estao divididos entre sistema com canal AWGN sıncrono e com

canal com desvanecimento plano sıncrono. Os parametros utilizados no sistema sao apresentados

previamente aos resultados exibidos.

Os resultados comparativos sao exibidos de tres formas, sendo elas: curva de convergencia da

taxa de erros, curva de convergencia da funcao custo e desempenho do sistema em funcao da relacao

sinal-ruıdo. E analisada tambem a complexidade dos algoritmos, sendo as mesmas comparadas com

a complexidade dos algorimtos GA e EP-C.

Para as simulacoes, foi utilizado o software matematico MATLAB, em um computador com um

processador de 3,2GHz e memoria de 1Gb. A descricao sucinta, em termos de variaveis de entrada e

de saıda, do algoritmo PSO e QPSOe apresentada no apendice A.

§6.1 Swarmem Canal AWGN Sıncrono

Nas simulacoes de otimizacao dos parametros do PSO e QPSO em canal AWGN sıncrono, o

sistemae caracterizado por:

6.1. Swarmem Canal AWGN Sıncrono 28

X Eb/N0 = 5dB;

X near − far = 0 (potencia equalizada entre todos os usuarios);

X Sequencias aleatorias de comprimentoN = 32;

X Numero de usuariosK = 16;

X Populacao dada pela equacao (4.1);

X Numero de erros por ponto da simulacao monte-carlo igual ou superior a 30;

6.1.1 Otimizacao dos Parametros do PSO para Canal AWGN Sıncrono

O primeiro sistema adotado para a analise de desempenho com algoritmo Swarm foi o sistema

DS/CDMA em canal AWGN sıncrono.

O metodo de otimizacao dos parametros utilizado consistiu em uma busca entre os valores

possıveis de uma variavel, estando as outras fixas nos valores assumidos nas simulacoes em Zhao e

Zeng (2004) e Zhen-su Lu (2004).

Primeiramente, buscou-se o valorotimo deVmax, estando fixos os parametrosφ1 = 2, φ2 = 2

e ω = 1. Foram analisados os valores para varios carregamentos e algunsEb/N0. A figura 6.1

mostra o comportamento do desempenho em funcao da variacao doVmax para o canal AWGN

sıncrono. A curva foi obtida para um valor deEb/N0 = 5dB, numero de usuarios K = 16,

com ganho de processamentoN = 32, efeito near-far igual a zero (potencias iguais para todos

os usuarios). A velocidade inicial das partıculas foi considerada igual a zero para todas as simulacoes.

Foi adotado para comparacao o ponto referentea 20a iteracao, que corresponde ao ponto onde o

PSO tende a convergir com os melhores valores deVmax.

Observa-se, atraves da figura, que o comportamento do algoritmo em funcao deVmax e de au-

mento de desempenho e converge para valores deVmax ≥ 2. Em Zhen-su Lu (2004),e mencionado

a importancia de manter uma chance mınima de mudanca de bit, possibilitando a fuga de possıveis

maximos locais.

Para verificar o comportamento para outros valores deEb/N0, foram realizadas simulacoes entre

4 e 7dB para esse fator, e foram obtidos resultados semelhantes, todaviaa convergencia foi atingida

de forma definitiva quandoVmax ≥ 3.


0 1 2 3 4 5 6 7 8

10−2

10−1

Vmax

BE

Rav

g

Figura 6.1: Curva para otimizacao deVmax.

Observando a funcao sigmoide (veja figura 5.2), utilizada para discretizar o algoritmo, nota-se

que apos o valor dev = 4, a funcao ja esta na regiao assintotica, implicando em uma variacao muito

pequena no resultado da mesma. Isso levanta a questao da viabilidade do uso doVmax, que causa

um aumento da complexidade do algoritmo e atinge resultados praticamente iguais ao algoritmo sem

esse fator. Foi optado, porem, por utilizar o parametroVmax = 4 no algoritmo, por adicionar uma

diversificacao maior, atraves de uma chance mınima fixa de troca de bit independente do valor da

velocidade da partıcula de 1,8%.

Adotou-se entaoVmax = 4 e buscou-se otimizar os valores deφ1 e φ2. Para isso, foi realizado

o mesmo metodo descrito anteriormente. Os parametros do sistema foram mantidos fixos em

Vmax = 4, φ1 ∨ φ2 = 2 eω = 1.

Notou-se que em relacao aφ1 existem duas situacoes a serem analisadas. Para valores altos de

φ1, o algoritmo tende a convergir mais lentamente, contudo atinge melhores desempenhos. Valores

Inferiores a 3 implicaram em um desempenho pior, entretanto a convergencia foi atingida mais

rapidamente.

O comportamento do parametroφ2 foi o oposto deφ1, conforme pode ser visto na figura 6.2. O

aumento deφ2 implica em uma maior velocidade de convergencia. Issoe explicado pelo fato desse

fator ser responsavel pela velocidade parcial relativaa melhor posicao global, porem a ponderacao

alta para essa parcela da velocidade implica em diminuicao da diversificacao do algoritmo, uma vez

que todas as partıculas tendem para a mesma posicao. Isso implica na obtencao de maximos locais

ao inves de maximos globais, diminuindo a eficiencia do algoritmo.


0 5 10 15 20 25 30

10−2

Iterações

BE

RA

vg

CDφ

2 = 0,5

φ2 = 1,5

φ2 = 2

φ2 = 3

φ2 = 5

φ2 = 8

SuB (BPSK)

Figura 6.2: Grafico utilizado para otimizacao do parametroφ2.

Outro comportamento a ser destacadoe que a diminuicao deφ2 implica em um maior tempo

de convergencia (lentidao), atingindo no entanto melhor desempenho. Ha, contudo, o problema do

tempo gasto para atingir o valor de maximo da funcao custo. Uma vez queφ2 se torna menor que

φ1, as partıculas tenderao a seguir uma busca mais detalhada proximos a seus maximos individuais,

aumentando a chance de fuga de maximos locais, porem atrasando o encontro do maximo global.

Essa analise implica no compromisso desempenhoversuscomplexidade, devendo ser analisado o

caso que satisfaca a exigencia da aplicacao.

Buscando mostrar de forma mais elucidativa o modo de escolha deφ2, foi elaborado um grafico

na figura 6.3 mostrando juntamente o desempenho e a complexidade em funcao da variacao deφ2.

Nota-se atraves do grafico 6.3 que existem alguns pontos selecionaveis para otimizar o algoritmo,

dependendo do seu uso. Para o caso MuD,e conveniente manter um bom desempenho e uma baixa

complexidade, o que direciona a escolha para valores proximosa interseccao entre as duas curvas.

Foi escolhido o pontoφ2 = 2.

O ultimo parametro a ser analisado foi a ponderacao da parcela referentea velocidade anterior da

partıcula,ω. A analise realizada para o algoritmo contınuo, em Kennedy e Eberhart (1995), considera

como situacao inicial as ponderacoes iguais. Sabe-se que os parametrosφ1 eφ2 sao multiplicados

por um numero aleatorio com distribuicao uniforme, com media igual a0, 5. Assim, a selecao de


0 1 2 3 4 5 6 7 810

20

30

Itera

ções

par

a co

nver

gir

0 1 2 3 4 5 6 7 87

8

9x 10

−3

φ2

BE

RA

vg

Figura 6.3: Curva de complexidade e desempenho do algoritmo PSO em funcao do parametroφ2.

0 5 10 15 20 25 30 35 40

10−2

Iterações

BE

RA

vg

CDω = 0,25ω = 0,5ω = 0,75ω = 1ω = 1,25ω = 1,5ω = 2SuB (BPSK)

Figura 6.4: Grafico do comportamento do PSO em funcao da variacao do parametroω.

φ2 = 2, implicaria na escolha deω = 1, para se manter a relacao entre os pesos. Para a figura 6.4

foram fixadosVmax = 4 eφ1 = φ2 = 2.

Na figura 6.4 foram tracadas varias curvas, variando-se entre elas apenas o valor deω entre

[0, 5; 2, 5]. Foi verificado que seu comportamento corresponde ao esperado, como algoritmo onde

ω = 1 acarretando o melhor desempenho. Aumentando-se o valor deω, o algoritmo apresentou uma

tendencia de deterioracao do desempenho. Isso tambem foi verificado para valores deω menores que

1, onde o desempenho foi muito prejudicado.


Selecionadosω = 1, φ2 = 2, optou-se por utilizarφ1 = 2 para manter a relacao entre as

ponderacoes das parcelas da velocidade.

Como esses tres parametros funcionam como ponderacoes das tres velocidades parciais, verificou-

se ainda o comportamento do algoritmo em funcao da variacao conjunta dos tres fatores. Na figura

6.5 e mostrado o desempenho do algoritmo para uma variacao deω no intervalo[0, 5; 5], sempre

respeitando a relacaoω = φ1

2 = φ2

2 . O parametroVmax foi fixado em 4.

0.5 1 1.5 2 2.5 3 3.5 4 4.5 510

−3

10−2

10−1

ω ; φ1 / 2 ; φ

2 / 2

BE

RA

vg

Figura 6.5: Verificacao da variacao conjunta das tres ponderacoes do calculo da velocidade, no PSO.

Na figura 6.5 visualiza-se o melhor desempenho para a variacao dos tres pesos simultaneamente.

A curvaBERAvg versusω plotada apresentou um ponto de mınimo paraω = 1, confirmando que se

trata do melhor ponto para o sistema quando os pesos das parcelas da velocidade sao iguais. Note

que, devido ao comportamento da funcao sigmoide, utilizada para discretizar o algoritmo, o PSO

tende a apresentar uma convergencia ruim apos o pontoω = 3.

Foram selecionados os seguintes valores otimizados para os parametros do PSO, em qualquer

sistema AWGN sıncrono:

X Vmax = 4, implicando em chance mınima de troca de bit de 1,8%;

X φ1 = 2

X φ2 = 2

X ω = 1

Nas simulacoes subsequentes utilizando o PSO foram adotados esses parametros.


6.1.2 Otimizacao dos Parametros do QPSO para Canal AWGN Sıncrono

Os parametros a serem otimizados saoc1, c2, c3 e α e β. Sao conhecidas previamente duas relacoes

que fazem parte do sistema de discretizacao do algoritmo QPSO:

X c1 + c2 + c3 = 1, 0;

X α + β = 1, 0;

Na analise seguinte, sao mostradas variacoes de um parametro do algoritmo, devendo-se entender

que ha variacoes em outros parametros para se manter as duas igualdades mencionadas acima. Para

seguir o metodo apresentado em Shuyuan Yang (2004), sera utilizado semprec1 = c21.

Observando os resultados obtidos no artigo Shuyuan Yang (2004), notou-se que o algoritmo se

mostrou mais eficiente para valores deα inferiores a0, 2 e c1 = c2 < 0, 2. Esses resultados foram

confirmados em simulacoes realizadas com o algoritmo QPSO implementado. A seguir estao dois

graficos sintetizando o comportamento do algoritmo em funcao dessas ponderacoes. Inicialmente foi

analisado o comportamento em funcao deα, mantendo-se fixoc1 = c2 = 0, 1 e c3 = 0, 8, figura 6.6.

0 5 10 15 20 25 30 35 40 45 50

10−2

Iterações

BE

RA

vg

CDα = 0α = 0,10α = 0,15α = 0,20α = 0,25α = 0,35SuB (BPSK)

Figura 6.6: Curvas de convergencia do algoritmo QPSO para varios valores deα.

Atraves do grafico 6.6, pode-se admitir que o desempenho do QPSOe superior para valores

deα proximos a 0,1. Fixou-se este fator emα = 0, 1 e β = 0, 9 e foi examinadoc1, buscando-se

otimiza-lo. Para essa analise foi obtido o grafico 6.7.

1Foram realizdas algumas simulacoes comc1 6= c2, nao se obtendo resultados superiores


0 5 10 15 20 25 30 35 40 45 50

10−2

Iterações

BE

RA

vg

CDc

1 = 0

c1 = 0,1

c1 = 0,15

c1 = 0,20

c1 = 0,25

c1 = 0,30

c1 = 0,35

SuB (BPSK)

Figura 6.7: Curvas de convergencia do algoritmo QPSO para varios valores dec1.

Observa-se que a hipotese dec1 = 0, 1 apresentada previamente condiz com o melhor de-

sempenho do algoritmo. Notou-se tambem que a medida que se diminuic1, o algoritmo tende a

apresentar uma convergencia inicial mais rapida. Assim, considerando a analise realizada sobre os

graficos 6.6 e 6.7, sera adotado para as demais simulacoes em canal AWGN sıncronoα = 0, 1 e

β = 0, 9, c1 = c2 = 0, 1 e c3 = 0, 8.

6.1.3 Resultados para canal AWGN Sıncrono

Foram comparados os algoritmos PSO, QPSO, GA (Ergum e Hacioglu (2000) e Ciriaco et al. (2004))

e EP-C (H.S. Lim e Chuah (2003) e Ciriaco et al. (2004)).

Para analisar a robustez do algoritmo em relacao as caracterısticas do canal, foi analisado o seu

desempenho para algumas relacoes sinal ruıdo no receptor. Considerou-se a mesma entre 6dB e 8dB.

O codigo de espalhamento foi definido como sendo uma sequencia aleatoria de comprimento

N = 32 Tc, e o carregamento, da formaL = KN variou entre 0,3125 e 1, visando verificar se

o algoritmo suporta um aumento do numero de usuarios, sem piorar o desempenho. Foi ainda

analisado os resultados do algoritmo para usuarios com potencias diferentes (efeitonear-far),

utilizando desbalancos de potencia de 8dB.

Por se tratar de simulacoes pelo metodo Monte-Carlo, foi definido o mınimo de 30 erros/ponto

para se obter um resultado confiavel.


Os parametros dos algoritmos genetico e programacao evolucionaria foram adotados como

otimizados, atraves de pesquisa em Ciriaco et al. (2004). Os parametros dos algoritmos PSO e QPSO

foram obtidos com base nos artigos Zhao e Zeng (2004), Shuyuan Yang (2004) e atraves da analise

de refinamento desses fatores, onde foram confirmados os valores maiseficazes desses parametros

do algoritmo.

Os parametros do sistema utilizados foram:

X Eb/N0 = 7dB;

X near − far = 0 (potencia equalizada entre todos os usuarios) ou NFR com 8 usuarios com

potencia de 0dB e 8 usuarios com potencia 8dB acima;


X Numero de usuariosK = 10, K = 16, K = 24, K = 32;


X Numero de erros da simulacao monte-carlo igual ou superior a 30;

Os parametros dos algoritmos foram:

X PSO:Vmax = 4, φ1 = φ2 = 2 eω = 1;

X QPSO:c1 = c2 = 0, 1, c3 = 0, 8, α = 0, 1 eβ = 0, 9;

X GA: T = D/10 = 2 (numero de melhores indivıduos selecionados),ic = 50 epm = 100/K

X EP-C:iporc = 10 e IC = p ∗ iporc/100 = 2.

O resultado mostrado na figura 6.8 compreende as curvas de convergencia para os algoritmos

PSO, QPSO, EP-C e GA. Como meio de melhorar a contextualizacao e comprovar o desempenho

dos algoritmos, sao mostrados ainda o desempenho do detector convencional (CD), do caso isento de

interferencia de multiplo acesso (SuB) e o resultado obtido pelo detectorotimo (ML).

O grafico da figura 6.8 mostra que os algoritmos QPSO e GA apresentaram um desempenho

inicial superior ao EP-C e PSO, porem, apos algumas iteracoes, o desempenho do PSO se torna

superior aos demais, convergindo de forma muito mais eficiente. A convergencia do PSO ocorre na

11a iteracao, enquanto que os demais algoritmos convergem por volta da30a iteracao. O algoritmo

QPSO, que foi apresentado com desempenho muito bom no artigo Shuyuan Yang (2004)2, nao

demonstrou a mesma eficiencia.

2exibido atraves da maximizacao da funcao custo


0 5 10 15 20 25 30 35 40

10−3

10−2

Iterações

BE

RA

vg

ML

CD

EP−C

GA

QPSO

PSO

SuB (BPSK)

Figura 6.8: Curva de convergencia para carregamentoL = 0, 3125 em canal AWGN sıncrono.

Pretendendo-se verificar a robustez dos algoritmos em funcao do efeitonear-far, foram realizadas

duas simulacoes com carregamento igual aL = 0, 5, sendo a primeira, figura 6.9, com controle

perfeito de potencia e a segunda com 8 usuarios com 0dB e 8 usuarios com potencia 8dB acima,

ou seja, com potencia 6,31 vezes superior aos 8 primeiros usuarios, figura 6.10. A deteccao nesse

segundo casoe realizada apenas para os 8 usuarios com menor potencia, que sao os mais afetados

por esse efeito.

0 10 20 30 40 50 60 70 80

10−3

10−2

Iterações

BE

RA

vg

CD

EP−C

GA

QPSO

PSO

SuB (BPSK)

Figura 6.9: Curva de convergencia para carregamentoL = 0, 50 em canal AWGN sıncrono, comcontrole perfeito de potencia.

Novamente, observa-se que o algoritmo PSO, embora tenha um comportamentoinicial mais

lento, atinge a convergencia final mais rapidamente. Isso demonstra novamente a eficiencia desse


algoritmo para o canal AWGN sıncrono. Quanto ao controle de potencia, observa-se nas figuras

6.9 e 6.10 que o PSO nao se mostrou imune a esse efeito. A inclusao de disparidades de potencia

no sistema, com metade dos usuarios apresentando potencias 8dB acima dos restantes implicou

em uma degradacao de desempenho por parte do algoritmo PSO. Estae uma analise que deve ser

aprofundada, pois uma queda de desempenho pode ser muito prejudicial se o sistema nao possuir

controle algum de potencia. O algoritmo QPSO tambem apresentou uma perda de desempenho,

todavia elae menos significativa.E importante ressaltar que, embora o algoritmo “demora” a

convergir, deve-se analisar a complexidade de cada iteracao por ele realizada para avaliar o seu

compromisso desempenhoversuscomplexidade.

0 10 20 30 40 50 60 70 80

10−3

10−2

10−1

Iterações

BE

RA

vg

CD

EP−C

GA

QPSO

PSO

SuB (BPSK)

Figura 6.10: Curva de convergencia para carregamentoL = 0, 5 em canal AWGN sıncrono, comefeito near-far, onde 8 us. sao considerados com potencia de 0dB e 8 usuarios estao com potencia8dB acima.

Pretendendo-se verificar a robustez dos algoritmos em funcao do carregamento do sistema, foram

realizadas simulacoes com carregamento deL = 0, 75 (K = 24) eL = 1, 00 (K = 32), figuras 6.11

e 6.12, respectivamente.

Observa-se claramente que a diferenca de desempenho entre os algoritmos fica evidenciada

quando o numero de usuarios cresce, apresentando o PSO um desempenho muito superior aos demais

quando NFR=0. Atraves dos graficos exibidos, foi verificado um atraso para o inıcio da convergencia

no algoritmo PSO, que aumentaa medida que se adiciona usuarios ao sistema. Isso foi confirmado

realizando-se simulacoes para sistemas comK = 64 eK = 128, com carregamento constante.

E apresentado na figura 6.13 o desempenho dos algoritmos atraves da maximizacao da funcao

custo. Nota-se que o desempenho inicial do algoritmo GAe superior, porem o algoritmo PSO atinge

a convergencia final mais rapidamente. Embora o algoritmo QPSO tenha se mostrado lento nesse


0 10 20 30 40 50 60 70 80 90

10−3

10−2

Iterações

BE

RA

vg

CD

EP−C

GA

QPSO

PSO

SuB (BPSK)

Figura 6.11: Curva de convergencia para carregamentoL = 0, 75 em canal AWGN sıncrono, comcontrole perfeito de potencia.

0 20 40 60 80 100 120

10−3

10−2

10−1

Iterações

BE

RA

vg

CD

EP−C

GA

QPSO

PSO

SuB (BPSK)

Figura 6.12: Curva de convergencia da funcao custo para carregamentoL = 1, 00 em canal AWGNsıncrono, com controle perfeito de potencia.

aspecto, todos os algoritmos atingiram um alto valor da funcao custo. Para o problema MuD, este

nao e o melhor metodo3 para se avaliar o desempenho de algoritmos heurısticos, pois pequenas

diferencas sao pouco vısiveis nesse grafico e podem implicar em diferencas consideraveis na BER.

Para finalizar a analise de desempenho do sistema DS/CDMA em canal AWGN sıncrono, e

mostrado na figura 6.14 a curva de desempenho dos quatro algoritmos em funcao da relacao sinal-

ruıdo no receptor.E apresentado tambem, para fins de comparacao e confirmacao, o desempenho do

3esse metodo foi utilizado em Shuyuan Yang (2004)


5 10 15 20 25 30 35 40 45 50

20

20.5

21

21.5

22

22.5

23

23.5

24

Iterações

Fun

ção

Cus

to

EP−CGAQPSOPSO

Figura 6.13: Curva de convergencia da funcao custo para carregamentoL = 0, 75 em canal AWGNsıncrono, com controle perfeito de potencia.

detector convencional e do caso de transmissao com umunico usuario. Foi considerado como ponto

de convergencia onde o valor da BER se estabiliza.

2 3 4 5 6 7 810

−4

10−3

10−2

10−1

GAEP−CPSOQPSOCDSuB (BPSK)

Figura 6.14: Curva do comportamento da convergencia dos algoritmos em funcao da RelacaoEb/N0

do sistema, em canal AWGN sıncrono.

Ja as curvas apresentadas na figura 6.15, foram obtidas considerando o numero de iteracoes em

cadaEb/N0 necessarias para atingir a convergencia o algoritmo PSO. Embora todos os algoritmos

possuam a possibilidade de convergir para o mesmo ponto, esse grafico e destinado a exibir a

eficiencia do PSO em relacao aos demais, no que diz respeito ao compromisso complexidadeversus

desempenho. Notou-se a tendencia do algoritmos perderem eficiencia se comparados ao PSO, sendo

6.2. Swarm em Canal com Desvanecimento Plano Sıncrono 40

que oultimo continua a atingir a convergencia para qualquer relacaoEb/N0. Convem ressaltar que

o numero de iteracoes para a convergencia poderia ser aumentado para os dois graficos (figuras

6.14 e 6.15), implicando em uma melhor BER para os algoritmos. Todavia, como a convergencia

se mostrou muito lenta apos os pontos adotados, optou-se por nao utiliza-los porque o ganho de

desempenho nao seria viavel devidoa alta complexidade (tempo) envolvida.

2 3 4 5 6 7 810

−4

10−3

10−2

10−1

GAEP−CPSOQPSOCDSuB (BPSK)

Figura 6.15: Curva do comportamento da convergencia dos algoritmos no ponto de convergencia doPSO, em funcao da relacaoEb/N0, em canal AWGN sıncrono.

§6.2 Swarm em Canal com Desvanecimento Plano Sıncrono

Para o canal com desvanecimento plano sıncrono, serao apresentados os testes otimizacao dos

parametros apenas do PSO. Os parametrosotimos encontrados para o canal sao utilizados para as

simulacoes comparativas. A velocidade inicial das partıculas foi considerada igual a zero em todas

as simulacoes. Para o QPSO, o comportamento do algoritmo em funcao dos parametros de controle

foi semelhante ao obtido em canal AWGN sıncrono, para as varias condicoes de sistema. Com isso,

foi adotado para o QPSO os mesmos parametros otimizados encontrados para o canal AWGN.

6.2.1 Otimizacao dos parametros do PSO para Canal com Desvanecimento PlanoSıncrono

Para a otimizacao dos parametros, foram realizadas inumeras simulacoes, ordenadas na tabela 6.1 de

acordo com o parametro:


Tabela 6.1: Simulacoes realizadas para otimizacao dos parametros do PSO em canal com desvaneci-mento plano sıncono.

Parametro Variacao do Parametro Eb/N0[dB] K

Vmax 3 a5, 5 8, 12, 16 10, 16, 24, 32φ1 1 a4 8, 12, 16 10, 16, 24, 32φ2 1 a4 8, 12, 16 10, 16, 24, 32ω 0, 5 a2 8, 12, 16 10, 16, 24, 32

O primeiro parametro analisado foi oVmax. Embora tenham ocorrido pequenas variacoes de

desempenho devidoa mudanca emVmax, viu-se que nao ocorre nenhum padrao para o desempenho

atingido pelo algoritmo em funcao desse parametro, podendo-se concluir que as diferencas se devem

ao fator aleatorio do metodo de simulacao Monte Carlo. Observou-se ainda a ocorrencia de um

atraso na convergencia a medida que se diminuiVmax, para valores deVmax < 3, 5. Esse atrasoe

mais significativoa medida que se aumenta o numero de usuarios do sistema e a relacao Eb/N0.

Valores deVmax > 3, 5 nao apresentaram atrasos em nenhuma simulacao, optando-se entao por

utilizar Vmax = 4.

O parametroφ1 apresentou comportamento semelhante ao da analise em canal AWGN sıncrono.

a medida que se aumenta o seu valor, ocorre uma partida lenta do PSO, porem o algoritmo tende a

apresentar um desempenho superior. Essa caracterıstica, entretanto,e pouco evidente, sendo tanto o

ganho de desempenho quanto o atraso inicial pouco consideraveis para se concluir o valor otimizado

deφ1. A caracterıstica de atraso mostrou-se mais clara para um alto numero de usuarios no sistema,

optando-se assim por adotar um valor nao muito alto, comφ1 = 2.

O parametroφ2 tambem apresentou um comportamento semelhante ao verificado em canal

AWGN. O aumento deφ2 implica em uma convergencia mais rapida, devidoa intensificacao da

busca sobre a melhor posicao global, todavia a diferenca de desempenho verificada no canal AWGN

nao se repete, apresentando o algoritmo desempenhos praticamente iguais para os variosφ2 testados.

Analisando o compromisso complexidadeversusdesempenho observa-se que o atraso incluıdo no

algoritmo devido a baixos valores deφ2 nao sao compensados pelo ganho de desempenho esperado,

concluindo-se quee mais viavel adotar altos valores para o canal com desvanecimento plano.

Nas simulacoes de comparacao entre os algoritmos utilizou-seφ2 = 10. O grafico da figura 6.16

apresenta o comportamento do algoritmo em funcao da variacao deφ2, simulado em um sistema

com numero de usuariosK = 16, sequencias aleatorias de comprimentoN = 32, Eb/N0 = 22dB

e NFR = 0. Os outros parametros do PSO foram:ω = 1, φ1 = 2 e Vmax = 4, com a populacao

inicial sendo dada por (4.1).

Para todosEb/N0 e numero de usuarios simulados (veja tabela 6.1), foram obtidos sempre numero

menor de iteracoes para convergencia e desempenho superior para o PSO comω = 1. O aumento deω

implica em uma velocidade muito alta, tendendo semprea velocidade dada porVmax ou−Vmax, im-

plicando em uma baixa probabilidade de troca de bit, uma consequente diversificacao menor, porem


0 10 20 30 40 50 60

10−2

10−1

Iterações

BE

RA

vg

CDφ

2=0

φ2=0,5

φ2=1,0

φ2=2,0

φ2=4,0

φ2=10,0

SuB (BPSK)

Figura 6.16: Curva de convergencia para algoritmo PSO, comω = 1, φ1 = 2 e Vmax = 4 e φ2

variando entre 0 e 10.

para possıveis maximos locais (apresenta capacidade de escape de maximos locais pouco eficientes).

A diminuicao deω implica em uma velocidade muito lenta da partıcula, adicionando muitas trocas

de bits e atrasando a convergencia. O grafico 6.17 mostra o comportamento acima explicado.

0 10 20 30 40 50 60 70 80 90 100

10−1

Iterações

BE

RA

vg

CDω = 0.5ω = 0.75ω = 1ω = 1.25ω = 1.5ω = 2SuB (BPSK)

Figura 6.17: Comportamento do algoritmo PSO em funcao do fatorω, para canal com desvaneci-mento plano sıncrono.

Para as simulacoes comparativas entre os quatro algoritmos, GA, EP-C, PSO e QPSO, em canal

com desvanecimento plano sıncrono serao adotados os seguintes parametros do PSO:Vmax = 4,

φ1 = φ2 = 10 eω = 1.


6.2.2 Resultados para Canal com Desvanecimento Plano Sıncrono

Os parametros do sistema utilizados foram:

X Eb/N0 = 10dB a25dB;

X NFR = 0 (potencia equalizada entre todos os usuarios) ou NFR com 8 usuarios com potencia

de 0dB e 8 usuarios com potencia 8dB acima;


X Numero de usuariosK = 16 eK = 32;


X Numero de erros da simulacao Monte-Carlo igual ou superior a 30;

Os parametros dos algoritmos foram:

X PSO:Vmax = 4, φ1 = 2, φ2 = 10 eω = 1;

X QPSO:c1 = c2 = 0, 1, c3 = 0, 8, α = 0, 1 eβ = 0, 9;

X GA: T = D/10 = 2 (numero de melhores indivıduos selecionados),ic = 50 epm = 100/K

X EP-C:iporc = 10 e IC = p ∗ iporc/100 = 2.

O primeiro grafico exibido para canal com desvanecimento plano sıncrono considera uma razao

Eb/N0 = 12dB e todos os parametros restantes conforme mencionado anteriormente.

No sistema comEb/N0 = 12dB, figura 6.18, ve-se claramente que os algoritmos QPSO e

GA apresentaram uma partida boa, obtendo o primeiro uma rapida convergencia para uma baixa

BER, apos9 iteracoes, enquanto oultimo apresentou uma demora maior de convergencia, entretanto

tambem atingindo a mesma BER, apos um numero de iteracoes igual a 15. Sobre o algoritmo EP-C,

pode-se verificar que ele demorou um pouco mais no inıcio, porem atingindo a mesma BER do GA

apos 20 iteracoes. O algoritmo PSO, como no caso AWGN sıncrono, tambem apresentou um atraso

para o inıcio da convergencia, porem atingiu uma baixa BER, equivalentea do GA, 2 iteracoes apos

o ultimo, mostrando-se, apesar disto, ainda muito eficiente.

A figura 6.19 foi obtida atraves de simulacao, semelhante ao sistema da figura 6.18, alterando-se

apenas o NFR, estando 8 usuarios com potencia de 0dB e 8 usuarios 8dB acima. O grafico mostra

que o algoritmo QPSO e PSO sao suscetıveis ao efeitonear-farem canal com desvanecimento plano


0 5 10 15 20 25 30

10−1

Iterações

BE

RA

vgCDEP−CGAPSOQPSOSuB (BPSK)

Figura 6.18: Curva de convergencia dos algoritmos para canal com desvanecimento plano sıncrono,comφ2 = 10, carregamentoL = 0, 5 eEb/N0 = 12dB.

0 5 10 15 20 25 30

10−1

Iterações

BE

RA

vg

CDEP−CGAPSOQPSOSuB (BPSK)

Figura 6.19: Curva de convergencia dos algoritmos para canal com desvanecimento plano sıncrono,com 16 usuarios,Eb/N0 = 12dB e efeitonear-far.

sıncrono, o que se mostrou mais evidente com o aumento dos desbalancos depotencia.

Foram simulados tambem, para os mesmos 16 usuarios, o desempenho do algoritmo para

situacoes de media e alta relacao sinal-ruıdo,18dB e25dB, respectivamente.

Alterando-se apenas a relacao Eb/N0, observou-se que o comportamento dos algoritmos

mantiveram-se semelhantes, atingindo a convergencia primeiramente o GA, seguido por PSO, QPSO


0 5 10 15 20 25 30 35 40 45 50

10−2

10−1

Iterações

BE

RA

vg

CD

EP−C

GA

PSO

QPSO

SuB (BPSK)

Figura 6.20: Curva de convergencia dos algoritmos para canal com desvanecimento plano sıncrono,com 16 usuarios eEb/N0 = 18dB.

e EP-C.

0 5 10 15 20 25 30 35 40

10−3

10−2

10−1

Iterações

BE

RA

vg



O algoritmo EP-C nao atingiu o ponto alcancado pelos algoritmo PSO e GA e QPSO, veja figura

6.21, exibindo que pode apresentar fracas estrategias de diversificacao. Tambem o algoritmo QPSO

apresentou uma pequena perda de desempenho inicial, demorando mais para igualar o nıvel atingido

pelo GA e pelo PSO.

6.3. Complexidade Computacional 46

Aumentando-se o numero de usuarios paraK = 32 e mantendo-se os outros parametros utiliza-

dos no sistema simulado na figura 6.18, foi obtida a figura 6.22, que mostra que os algoritmos GA,

PSO e EP-C sao robustos quanto ao aumento do numero de usuarios, porem o QPSO apresentou-se

muito vulneravel a esse aumento, com uma convergencia muito lenta, repetindo o comportamento

observado em canal AWGN sıncrono.

0 5 10 15 20 25 30 35 40 45 50

10−1

Iterações

BE

RA

vg



O ultimo grafico para canal com desvanecimento plano sıncrono, figura 6.23, exibe o compor-

tamento dos algoritmos em funcao da relacao Eb/N0, para um numero de usuarios K = 16. E

observado que todos os algoritmos apresentaram desempenho equivalente, atingindo valores de BER

proximos a transmissao com umunico usuario (SuB). Convem mencionar que embora os quatro

algoritmos comparados tenham atingido praticamente o mesmo desempenho, ve-se atraves das

figuras 6.18, 6.20 e 6.21 que o numero de iteracoes para convergencia possui diferencas significativas

entre os algoritmos, sendo da forma GA<PSO<QPSO<EP-C. Ha ainda o problema observado para

o QPSO, que para carregamentoL = 1 mostrou-se ineficiente e nao convergiu para o ML.

§6.3 Complexidade Computacional

Varias aplicacoes de tecnicas heurısticas envolve sistemas estaticos ou lentos, que nao priorizam

o tempo gasto por elas. Nas aplicacoes de deteccao multiusuario DS-CDMA, a complexidade

computacionale um fator essencial para a analise da viabilidade de um algoritmo. Conforme

mencionado anteriormente nesse trabalho, o compromisso desempenhoversuscomplexidadee o que

avalia o algoritmo, por isso a importancia da analise de complexidade dos metodos apresentados


8 10 12 14 16 18 20 22 24

10−3

10−2

10−1

Eb/N

0 [dB]

BE

RA

vgGA

EP−C

PSO

QPSO

CD

SuB (BPSK)

Figura 6.23: Curva do comportamento da convergencia dos algoritmos em funcao da RelacaoEb/N0

do sistema, para canal com desvanecimento plano sıncrono.

nesse trabalho, PSO e QPSO.

A complexidade computacional do algoritmo PSO sera definida atraves do numero de operacoes

realizadas, somando-se multiplicacoes, geracao de numeros aleatorios, comparacoes e selecoes.

Primeiramente sera apresentada a complexidade para o caso de transmissao em sistema DS/CDMA

em canal AWGN sıncrono, tanto para o PSO quanto para o QPSO. Em seguida sao exibidas as

alteracoes necessarias para se obter a complexidade em canal com desvanecimento plano sıncrono.

Como metodo adicional, foi medido ainda o tempo computacional gasto pelo algoritmo agirna

deteccao, atingindo um numero de iteracoes pre-definido.

6.3.1 Complexidade Computacional do PSO em Canal AWGN Sıncrono

Inicialmente sera contabilizado o numero de operacoes realizadas, somando todos os produtos,

geracoes de numeros aleatorios, comparacoes e selecoes. Considereg igual ao numero de iteracoes,

K sendo o numero de usuarios eD a populacao necessaria para solucionar de forma otimizada4 o

problema.

A geracao de numeros aleatorios ocorre de forma mais evidente na definicao da populacao inicial,

na velocidade inicial, no calculo da velocidade e na discretizacao da velocidade. O total de numeros

4a populacao otimizadae fornecida pela equacao (4.1)


geradose [(5D + 2)g + 2D − 1]K.

Uma selecaoe realizada a cada geracao, sendo entao somadasgK operacoes. Ocorrem tambem

(2D + 1)g comparacoes de ordemK, sendo comparados as posicoes das partıculasa melhor posicao

global ea melhor posicao individual.

Os calculos realizados pela funcao custo sao descritos a seguir. Dois termos podem ser calculados

fora do laco de iteracoes, por nao variarem:

f1 = 2 · A · yT

f2 = ARA (6.1)

Assim, o calculo da funcao custo, em canal AWGN sıncrono, sera dado por

f (pi) = 2Re{f1pi} − pTi f2pi (6.2)

O numero de operacoes da primeira parcela para cada partıcula e K; pois ha um produto de duas

matrizes de ordem1 × K e K × 1. A segunda parcela apresenta dois produtos matriciais, um entre

matrizes de ordem1 × K e K × K, o que implica emK2 operacoes e o outro entre matrizes de

1 × K eK × 1, acarretando novamenteK calculos. Aplicando-se esses fatores para asD partıculas

e g iteracoes do algoritmo, ha um total deDg(K2 + 2K). Deve-se adicionar ainda o calculo inicial

da funcao custo, fora do laco de iteracoes.

Assim, o total de operacoes realizadas pelo algoritmoe Dg(

K2 + 9K)

+

K (D(K + 4) + 4g − 1) operacoes.

6.3.2 Complexidade Computacional do QPSO em Canal AWGN Sıncrono

A complexidade do QPSO sera analisada do mesmo modo realizado para o PSO.

O calculo da funcao custoe identica ao mostrado para o PSO, portanto deve-se considerar

(Dg + D)(K2 + 2K) operacoes. O numero de comparacoes tambeme semelhante ao PSO, sendo

necessario realizar a atualizacao das melhores posicoes individuais e global. A geracao de numeros

se mostraram a grande vantagem do QPSO, uma vez que ela ocorre apenas uma vez durante o laco

de iteracoes, para discretizar o vetor de energia de bit.

O numero total de operacoes do QPSO pode ser expresso porDg(K2 + 5K) + K(D(K + 3) +

g − 1).


6.3.3 Complexidade do PSO e QPSO em Canal com DesvanecimentoSıncrono

A alteracao de canal AWGN sıncrono para canal com desvanecimento plano ocorre no calculo da

funcao custo, ondee incluıda a matriz de coeficientes complexos do canal,C. A funcao custo para

esse canale dada por:

f (b) = arg{

2Re{yTCHAb} − bTCARACHb}

(6.3)

Observa-se a matrizC possui ordemK × K. O produtoy · CH realizaK2 operacoes de

multiplicacao e mais uma transposicao, devido ao operador hermitiano. O produtoC · A implica

em K3 operacoes, assim como tambem o termoA · CH , que possui o acrescimo apenas de uma

transposicao da matrizC. Assim, o numero de operacoes total para o calculo da funcao custoe dado

por2 ·(

K3 + K2 + K)

.

6.3.4 Comparacao da Complexidade entre os Algoritmos

Para efeito de comparacao, serao apresentados tambem a complexidade do detectorotimo (ML), GA

e EP-C.

Para o detector ML, o numero de operacoes cresce exponencialmente com o numero de usuarios.

Sao necessarias2K geracoes de bits de ordemK e 2K calculos da funcao custo para a deteccao

simultanea de 1 bit dosK usuarios.

O numero de operacoes no algoritmo EP-C cresce dependente principalmente das operacoes da

funcao custo, sendo necessarias tambemDg +D− 1 geracoes de bits de ordemK, Dg +D calculos

da funcao custo,2Dg ordenacoes de ordemK, Dg/IC selecoes de ordemK e gIC clonagens de

ordemK.

A complexidade computacional para o algoritmo GA tambem cresce dependendo da relacao

pgK2, sendo necessariaspg +p−1 geracoes de bits de ordemK, Dg selecoes de ordemK, Dg +D

calculos da funcao custo,2Dg ordenacoes de ordemK eDg comparacoes de ordemK.

A tabela 6.2 exprime, de forma literal, a complexidade dos algoritmos.E importante ressaltar

que a primeira parcelae o termo mais significativo da complexidade, pois implica em maior tempo

de processamento, devido ao grau de suas variaveis.

Embora a tabela 6.2 mostre inicialmente que o algoritmo PSO seja mais complexo, convem

lembrar que o numero de iteracoes (g) necessarias para a convergencia do algoritmo varia para


Tabela 6.2: Complexidade dos detectores multiusuario em termos de operacoes, em canal AWGNsıncrono.

Detector Numero de OperacoesML 2K

(

K2 + 3K)

EP-C Dg(

K2 + 6K + K/IC

)

+ K (D(K + 4) + gIC − 1)GA Dg

(

K2 + 7K)

+ K (D(K + 3) − 1)PSO Dg

(

K2 + 9K)

+ K (D(K + 4) + 4g − 1)QPSO Dg

(

K2 + 5K)

+ K (D(K + 3) + g − 1)

os metodos heurısticos analisados. A tabela 6.3 mostra o numero de operacoes realizadas para

o caso da transmissao em canal AWGN sıncrono, ate os algoritmos atingirem a convergencia

(individualmente), exibidos nas simulacoes comparativas entre os metodos heurısticos.

Tabela 6.3: Numero de operacoes para os algoritmos atingirem a convergencia, em canal AWGNsıncrono.

Detector K=10 K=16 K=24 K=32ML 133.103 19, 9.106 10, 87.109 4, 8.1012

EP-C 96.103 655.103 1, 773.106 6, 92.106

GA 97.103 671.103 2, 251.106 9.106

PSO 45.103 287.103 974.103 4.106

QPSO 89.103 715.103 2, 946.106 X

Assumindo agora o segundo metodo de analise da complexidade, o tempo consumido, foi

verificado que os valores obtidos para o numero de operacoes nao condiz com o tempo gasto na

simulacao. Para essa analise, utilizou-se um sistema com numero de usuariosK = 16, numero de

iteracoesg = 30 e populacaoD = 30, em canal AWGN sıncrono. Simulou-se todo o sistema, desde

a transmissao ate a recepcao do sinal, passando entao pelo detector MuD composto pelo algoritmo

heurıstico, e verificou-se o tempo gasto. Esse processo foi repetido tres vezes para cada algoritmo,

buscando obter uma media do tempo gasto.

Convem lembrar que todos os algoritmos foram simulados com o mesmo numero de iteracoes,

o que, na pratica, nao ocorre, pois o algoritmo PSO converge antes para o caso AWGN sıncrono.

Atraves dos valores exibidos na tabela 6.4, podem ser calculadas relacoes entre as iteracoes dos

algoritmos heurısticos. Para exibir essa comparacao de forma mais elucidativa, sao considerados os

tempos relativos ao tempo gasto pelo algoritmo PSO.

A transmissao, deteccao da informacao foram realizadas 51768 vezes para cada simulacao.

Como foi realizada uma media de tres simulacoes para cada algoritmo, chega-se a um valor de

155304 atuacoes de cada algoritmo, obtendo-se assim uma media confiavel do tempo gasto pelo

algoritmo.


Tabela 6.4: Tempo demandado para execucao dos algoritmos heurısticos em canal AWGN sıncrono.Detector Tempo Consumido [min] RelacaoCD 4, 11 0, 11EP-C 45, 68 1, 24GA 67, 96 1, 90PSO 37, 65 1, 00QPSO 22, 36 0, 54

Assumindo agora os detectores MuD heurısticos funcionando em canal com desvanecimento

plano sıncrono, o numero de operacoes realizadas, conforme calculado anteriormente,e mostrado na

tabela 6.5.

Tabela 6.5: Complexidade dos detectores multiusuario em termos de operacoes, em canal comdesvanecimento plano sıncrono.

Detector Numero de OperacoesML 2K

(

2K3 + 2K2 + 3K)

EP-C Dg(

2K3 + 2K2 + 6K + K/IC

)

+ K (D(K + 4) + gIC − 1)GA Dg

(

2K3 + 2K2 + 7K)

+ K (D(K + 3) − 1)PSO Dg

(

2K3 + 2K2 + 9K)

+ K (D(K + 4) + 4g − 1)QPSO Dg

(

2K3 + 2K2 + 5K)

+ K (D(K + 3) + g − 1)

Repetindo-se a analise realizada para o caso AWGN sıncrono, sera medido o tempo computa-

cional demandado para se aplicar os algoritmos heurısticos no problema MuD. A tabela 6.6 exprime

o tempo consumido pelos quatro algoritmos testados, considerando que cadaalgoritmo agiu 51984

vezes, com populacaoD = 30 e um total de30 iteracoes em cada acao do mesmo. Esse processo

foi realizado tres vezes, para se obter uma media mais confiavel da complexidade do algoritmo. A

coluna relacao da tabela mostra o tempo gasto pelo algoritmo heurıstico em relacao ao PSO.

Tabela 6.6: Tempo demandado para execucao dos algoritmos heurısticos em canal com desvaneci-mento plano sıncrono.

Detector Tempo Consumido [min] RelacaoCD 6, 35 0, 16EP-C 47, 49 1, 26GA 70, 52 1, 96PSO 39, 09 1, 00QPSO 23, 97 0, 54

Foi observado que embora ocorreu um aumento no numero de operacoes realizadas, o tempo

computacional foi praticamente o mesmo, provavelmente com aumento devidoa geracao dos

coeficientes complexos com distribuicao Rayleigh para a amplitude. A relacao entre os algoritmos e

o PSO se manteve tambem semelhante.

6.4. Compromisso ComplexidadeversusDesempenho 52

§6.4 Compromisso ComplexidadeversusDesempenho

Visando unir as analises de desempenho e complexidade dos algoritmos, foi realizado o calculo

da BER em funcao do tempo gasto, considerando as relacoes apresentadas na tabela 6.6. Sera exibido

adiante apenas o caso de sistema DS/CDMA em canal com desvanecimento plano sıncrono, devido

primeiramentea evidencia de que em canal AWGN sıncrono o PSO foi claramente superior aos

outros e devido, principalmente,a maior importancia de uma analise em canal com desvanecimento

plano, por se tratar de um canal mais realista e com mais aplicacoes praticas.

Os graficos 6.24 e 6.25 mostram o desempenho, em termos de BER, dos algoritmos emfuncao

do tempo consumido. O eixo das abscissas esta normalizada em funcao do numero de iteracoes do

algoritmo PSO. Os graficos foram gerados com base nas figuras 6.18 e 6.21, utilizando as relacoes

fornecidas pela tabela 6.6.

0 5 10 15 20 25 30

10−1

Tempo Relativo

BE

RA

vg

CD

EP−C

GA

PSO

QPSO

SuB (BPSK)

Figura 6.24: Curva de convergencia dos algoritmos do tempo relativo ao PSO, comEb/N0 = 12dBe numero de usuariosK = 16, para canal com desvanecimento plano sıncrono.

E observado que, mantendo-se fixo o numero de usuarios, o desempenho dos algoritmos se

mantem para as varias relacoesEb/N0 em canal com desvanecimento plano sıncrono. Contabi-

lizando o tempo consumido, o algoritmo QPSO se mostrou mais eficiente para o carregamento em

L = 0, 5. O PSO apresentou um bom desempenho, sendo apenas superado peloQPSO, devido a

baixa complexidade doultimo. O algoritmo GA, que inicialmente se mostrou mais eficiente, obteve

desempenho inferiores ao QPSO e ao PSO. O algoritmo EP-C foi inferior a todos, para qualquer

relacao sinal-ruıdo, apresentando uma convergencia lenta e pouco eficiente.

A figura 6.26 mostra o desempenho real dos algoritmos, para um numero de usuariosK = 32,

buscando verificar o comportamento dos algoritmos com o aumento de carregamento. Observou-se

6.4. Compromisso ComplexidadeversusDesempenho 53

0 5 10 15 20 25 30 35

10−3

10−2

10−1

Iterações

BE

RA

vg



que o PSOe mais eficiente, convergindo mais rapidamente, sendo seguido pelo GA, EP-C e QPSO,

sendo que oultimo nao atingiu a convergencia apos 50 iteracoes.

0 5 10 15 20 25 30

10−1

Iterações

BE

RA

vg

CD

EP−C

GA

PSO

QPSO

SuB (BPSK)


CAPITULO 7

CONCLUSAO

A analise do PSO e do QPSO mostrou que estes algoritmos sao promissores do ponto de vista da

deteccao MuD. O estudo para otimizacao dos parametros do PSO em canal AWGN sıncrono foi

eficaz, e apresentou um resultado importante, concluindo que o desempenho do algoritmoe estavel

para valores fixos deVmax, φ1, φ2 eω. Os valores otimizados encontrados foramVmax ≥ 4, φ1 = 2,

φ2 = 2 e ω = 1. E importante ressaltar que esses valores dos parametros apresentaram bom

desempenho e baixa complexidade, entretanto foi observado que valores deφ1 > 2 apresentaram

resultados para a BER sempre melhores do que o valor alcancado porφ1 = 2, com um pequeno au-

mento da complexidade. Uma avaliacao da aplicacao pode definir melhor qual o valor deφ1 a utilizar.

As simulacoes em canal com desvanecimento plano sıncrono indicaram que os parametros

otimizados para AWGN sıncrono sao razoaveis para esse tipo de canal, sendo alterado apenas o

parametroφ2, que assumiu o valor 10. Algumas simulacoes foram realizadas, adotando-se varias

relacoes sinal-ruıdo, apresentando o PSO um bom desempenho e sendo robusto em relacao a essa

variacao.

Para o algoritmo QPSO, notou-se que elee muito sensıvel aos parametros analisados,c1, c2, c3,

α e β. Os valores encontrados que apresentaram melhores desempenhos, tanto para canal AWGN

sıncrono como para canal com desvanecimento plano sıncrono, foramc1 = c2 = 0, 1 e c3 = 0, 8,

α = 0, 1 eβ = 0, 9.

Analisando o comportamento dos algoritmos em relacao ao aumento do numero de usuarios,

notou-se que o PSO se mostra mais eficiente em relacao aos outros a medida que ocorre esse

acrescimo, convergindo de forma mais rapida, apesar do aumento do atraso nas primeiras iteracoes.

Quanto ao QPSO, o algoritmo se mostrou menos eficiente com o aumento de K, chegando a nao

convergir para o valor deK = 32. Isso pode ser explicado devido a uma fraca estrategia de

diversificacao do QPSO, que pode ser analisada em uma otimizacao futura.

55

Para a condicao de diferentes nıveis de potencia no sistema (efeitonear-far), notou-se que o

desempenho do algoritmo PSO apresentou degradacao. Isso mostra que o algoritmo PSO, embora

seja muito eficiente para sistemas com controle de potencia, naoe tao robusto ao efeitonear-far. Em

sistemas sem controle de potencia, como os utilizados atualmente, a falta de robustez em relacao ao

efeitonear-far pode prejudicar a aplicacao do PSO. Isso requer uma outra estrategia de otimizacao

dos parametros que leve em conta o impacto das disparidades de potencia sobre o comportamento

das partıculas.

As simulacoes em canal com desvanecimento plano sıncrono mostrou que os algoritmos PSO

e QPSO continuam convergindo para baixos valores de carregamento (L), porem a vantagem de

desempenho, principalmente do PSO, nao e mais tao evidente devido ao melhor desempenho do

algoritmo GA. Para carregamentoL > 0, 5 o QPSO se mostrou novamente ineficiente, enquanto o

PSO apresentou um bom desempenho, convergindo praticamente junto ao GA.

A complexidade foi analisada por dois metodos. O primeiro procedimento consistiu em prever o

numero de operacoes que os algoritmos heurısticos realizavam, e os algoritmos apresentaram numeros

semelhantes, com uma ordem de complexidade dada porQPSO < EP − C < GA < PSO. A

segunda analise ocorreu em funcao do tempo gasto para detectar um numero fixo de bits recebidos,

estabelecendo-se um numero fixo de execucoes do algoritmo. Foi medido o tempo gasto pelos

quatro algoritmos analisados e atraves desse metodo observou-se que a complexidade obtida entre

os algoritmose QPSO < PSO < EP − C < GA. A primeira analise considerou algumas

operacoes diferentes (produto, selecao, comparacao) como sendo iguais, o que pode ser uma

razao para a diferenca de complexidade obtida numericamente atraves do tempo consumido e do

valor equacionado para os mesmos. Outra possıvel explicacao e o fato do software utilizado para

simulacoes, MATLAB, nao possuir as rotinas basicas otimizadas, podendo influir no tempo final de

simulacao do algoritmo.

A analise comparativa dos algoritmos mostrou-se muito eficiente no intuito de esclarecer quais os

nıveis esperados para os algoritmos heurısticos e qual apresentou melhor relacao desempenhoversus

complexidade. Focando-se no compromisso desempenhoversuscomplexidade para canal AWGN

sıncrono, o algoritmo PSO apresentou melhor qualidade, atingindo nao so um otimo desempenho

(baixa BER), como tambem uma baixa complexidade em relacao ao ML, verificada atraves do tempo

computacional consumido. O algoritmo QPSO apresentou um desempenho um pouco abaixo do

esperado para valores de carregamentoL > 0, 5, nao atingindo nıveis otimos como mostrado em

Shuyuan Yang (2004). Todavia o QPSO apresentou uma complexidade muitoreduzida, o que pode

ser um fator relevante dependendo das necessidades do sistema. Paracanal com desvanecimento

plano sıncrono, foi observado que para carregamentos inferiores aL = 0, 5, o algoritmo QPSO se

mostrou superior aos demais, seguido pelo PSO, GA e EP-C. Para carregamentos maiores, o QPSO

nao atingiu a convergencia, se mostrando inviavel para implementacao. Admitindo a robustez em

canal com desvanecimento plano sıncrono, o desempenho foi melhor para o PSO, seguido pelo GA,

EP-C e QPSO.

7.1. Perspectivas de Estudo 56

Como consideracoes finais acerca dos algoritmos PSO e QPSO pode-se dizer:

X O PSO se mostrou robusto em relacao ao aumento do numero de usuarios eas variacoes na

relacao sinal-ruıdo, porem apresentou susceptibilidade ao efeitonear-far. Possui uma baixa

complexidade computacional, cerca de 2 vezes menor que a do GA. Mostrou-se ainda exce-

lente no compromisso desempenhoversuscomplexidade, implicando em boas perspectivas de

aperfeicoamento e implementacao.

X O QPSO mostrou-se interessante principalmente pela sua menor complexidade,porem seu de-

sempenho, principalmente para alto numero de usuariose ruim, tornando-o impraticavel.

§7.1 Perspectivas de Estudo

Apos a analise apresentada nesse trabalho, existem algumas vertentes de pesquisaque se mostram

atrativas e podem ser seguidas futuramente:

X Avaliacao o comportamento dos algoritmos para canais mais realistas, incluido assincronismo

entre os usuarios e multipercurso;

X Avaliar o algoritmo para sistemas com falhas nas estimativas dos parametros do canal;

X Verificacao da aplicacao do QPSO e PSO discreto para outros fins, como definicao de

parametros do canal e selecao otimizada de sequencias;

X Buscar uma otimizacao mais abrangente dos parametros do algoritmo;

X Realizar a otimizacao dos parametros para sistemas com NFR.

X Verificar a influencia da velocidade inicial, adotada zero nas simulacoes, no desempenho do

PSO;

X Procurar diminuir a complexidade do algoritmo PSO, atraves da eliminacao da geracao de

alguns numeros aleatorios, eliminacao do parametroVmax e utilizacao de outras funcoes para

discretizar as posicoes das partıculas.

X Avaliar o uso de algoritmos hıbridos, buscando unir tecnicas que apresentem uma boa partida de

busca, como o GA e o QPSO, ao PSO, que apresentou excelente convergencia apos as iteracoes

iniciais;

APENDICE A

ESTRUTURA DO PROGRAMA EMMATLAB

O escopo a seguir procura explicar alguns passos a se seguir para a obtencao dos resultados exibidos

nesse trabalho e demonstrar o metodo de simulacao Monte Carlo utilizado nas simulacoes computa-

cionais.

§A.1 Bloco Principal

Carrega os parametros iniciais do sistema:

(K, EbNo-dB, NFR-dB, N, Ns, Tip-seqs, ERRORS, p, iteracoes)

Carrega os parametros iniciais dos algoritmos heurısticos

i-porc (EP-C); Vmax, fi-1, fi-2, w(PSO); alfa, beta, c1, c2, c3 (QPSO); T, p-c, p-m (GA);

Inicio da Simulacao monte-carlo

Definicao do numero de transmissoes atraves do calculo de SuB e do numero de erros.

Selecao das sequencias de espalhamento

[Seqs, N] = sel-seqs(Tip-seqs, K, N);

Calculo da matriz de correlacao

R = Seqs * transpose(Seqs)/N;

Geracao do sinal transmitido

[A, sgma, Rx, b, FiCar, n-bits, Dly, Ck] = Tx-Ass-flat2(EbNo-dB, Seqs, NFR-dB, Ns);

Deteccao atraves do Detector Convencional

A.1. Bloco Principal 58

[b-conv, Z-conv, y] = conv-as-n-bits2(Rx, N, Seqs, Dly, n-bits, FiCar, Ns, fase);

Passagem pelos detectores MUD heurısticos

[errors-ep, K, ML-epc] = EP-CD-Clone(b-m, b-conv, R, p, A, FiCar, y, iteracoes, I-C, sgma-eb-no,

sgma-nfr);

[errors-sw, K, ML-sw] = Swarm-s(b-m, b-conv, R, FiCar, y, iteracoes, p, A, Vmax, fi-1, fi-2);

[errors-sw2, K, ML-qsw] = Swarm-q(b-m, b-conv, R, FiCar, y, iteracoes, p, A, alfa, beta, c1, c2, c3);

[errors-ga, K, ML-ga] = GA(b-m, b-conv, R, p, A, FiCar, y, iteracoes, p-c, T, p-m);

Verificacao do fim da simulacao Monte-Carlo.

Calculo da BER media

BER-avg-Trial-ep

BER-avg-Trial-sw

BER-avg-Trial-sw2

BER-avg-Trial-ga

A.1.1 PSO

————-FUNCAO DO ALGORITMO SWARM (PSO)————

function [errors-sw, K] = Swarm-s(b-m, b-conv, R, FiCar, y, It, P, A, Vmax, fi-1, fi-2);

—————–ENTRADAS————————-

— b-m = Sequencia de bits tranmitida (coluna com Kx1)(0 ou 1);

— b-conv = Sequencia do receptor convencional (-1 ou 1);

— R = Matriz de correlacao cruzada entre os codigos (dim. = K x K);

— FiCar = Fase do sinal (uma por bit);

— y = Vetor com o sinal recebido

— It = Numero de geracoes (iteracoes);

— P = populacao de partıculas a cada geracao;

— A = Amplitude do sinal;

— Vmax = Maximo valor admitido para vid

—————–SAIDAS—————————

— errors = erros obtidos na simulacao Swarm;

— K = Numero de usuarios;

A.1. Bloco Principal 59

A.1.2 QPSO

————-FUNCAO DO ALGORITMO SWARM————

function [errors-sw-q, K,ML-qsw] = Swarm-q(b-m, b-conv, R, FiCar, y, It, P, A , alfa, beta, c1, c2, c3);

—————–ENTRADAS————————-

— b-m = Sequencia de bits tranmitida (coluna com Kx1)(0 ou 1);

— b-conv = Sequencia do receptor convencional (-1 ou 1);

— R = Matriz de correlacao cruzada entre os codigos (dim. = K x K);

— FiCar = Fase do sinal (uma por bit);

— y = Vetor com o sinal recebido

— It = Numero de geracoes (iteracoes);

— P = populacao de partıculas a cada geracao;

— A = Amplitude do sinal;

—————–SAIDAS—————————

— errors = erros obtidos na simulacao Swarm;

— K = Numero de usuarios;

———VARIAVEIS DO ALGORITMO——————-

— q(i) = matriz quantica de todas as partıculas (P), cada uma com um

vetor de K energias quanticas

— p(i) = partıculas binarias referente aos vetores q(i)

— alfa = parametro de controle

— beta = parametro de controle (alfa + beta = 1)

— c1, c2, c3 = parametros equivalentes a w, fi-1 e fi-2

— c1 + c2 + c3 = 1;

Referencias Bibliograficas

Abedi, S., T. R. (2001). Gmd: A new cdma multiuser detection technique using an evolutionary

algorithm. IEE Proc. Communications, 148(6):393–399.

Abrao, T. (2001). Canceladores de Inteferencia Multiusuario Aplicados a Sistemas DS/CDMA de

Multipla Taxa. Tese de Doutorado, Escola Politecnica da Universidade de Sao Paulo, Brasil.

Ciriaco, F., Abrao, T., e Jeszensky, P. J. E. (2004). Algoritmos heurısticos evolucionarios aplicadosa

deteccao multiusuario ds-cdma.XXI Simposio Brasileiro de Telecomunicacoes, SBT2004.

de Castro e Fernando J. Von Zuben, L. N. (2002). Learning and optimization using the clonal selection

principle. IEEE Transactions on Evolutionary Computation, 6(3):239–251.

e R.S. Ramakrishna, C. W. A. (2002). A genetic algorithm for shortest path routing problem and the

sizing of populations.IEEE Transactions on Evolutionary Computation, 6(6):566–578.

Ergum, C. e Hacioglu, K. (2000). Multiuser detection using a genetic algorithm in cdma communi-

cations systems.IEEE Transactions Communications, 48(8):1374–1383.

H.S. Lim, M.V.C. Rao, A. W. T. e Chuah, H. (2003). Multiuser detection for ds-cdma systems using

evolutionary programming.IEEE Communications Letters, 7(3):101–103.

Kennedy, J. e Eberhart, R. (1995). Particle swarm optimization. EmIEEE International Conference

on Neural Networks, pp. 1942–1948.

Kennedy, J. e Eberhart, R. (1997). A discrete binary version of the particle swarm algorithm. Em

IEEE international conference on Systems, pp. 4104–4108.

Proakis, J. G. (1995).Digital Communications. McGraw-Hill.

Shuyuan Yang, Min Wang, L. J. (2004). A quantum particle swarm optimization. Em IEEE, pp.

320–324.

Silva, V. A. (2004). Modelagem computacional de canais de comunicacao movel. Dissertacao de

Mestrado, Escola Politecnica da Universidade de Sao Paulo, Brasil.

Simon, M. K., Omura, J. K., e Scholtz, Robert A.and Levitt, B. K. (1994).Spread Spectrum Commu-

nications Handbook. McGraw-Hill.

Referencias Bibliograficas 61

Stancanelli, E. M. G. (2004). Receptores rake em canais com desvanecimentos rapidos e seletivos em

frequencia para sistemas ds-cdma. Dissertacao de Mestrado, Escola Politecnica da Universidade

de Sao Paulo, Brasil.

Verdu, S. (1984).Optimum Multiuser Signal Detection. Tese de Doutorado, University of Illinois at

Urbana, champaign, United States.

Verdu, S. (1998).Multiuser Detection. Cambridge Univ. Press.

Viterbi, A. J. (1995). CDMA - Principles of Spread Spectrum Communication. Addison Wesley

Longman.

Zhao, Y. e Zeng, J. (2004). Particle swarm optimization algorithm in signal detection and blind

extraction. Em7th International Symposium on Parallel Architectures, Algorithms and Networks

(ISPAN’04).

Zhen-su Lu, S. Y. (2004). Multiuser detector based on particle swarm algorithm. Em IEEE, pp.

783–786.

Documents

ANALISE DE DESEMPENHO E COMPLEXIDADE DOS ... - uel.br · 6.3 Curva de complexidade e desempenho do algoritmo PSO em função do par ametroˆ φ2. 31 6.4 Gráfico do comportamento