Download PDF
ads:
Universidade de Pernambuco
Escola Politécnica de Pernambuco
Departamento de Sistemas e Computação
Programa de Pós-Graduação em Engenharia da Computação
Robson Alcântara Santana
Roteamento em Redes Ópticas Transparentes
Utilizando Redes Neurais de Hopfield
Dissertação de Mestrado
Recife, março de 2010
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
UNIVERSIDADE DE PERNAMBUCO
DEPARTAMENTO DE SISTEMAS E COMPUTAÇÃO
PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA DA COMPUTAÇÃO
ROBSON ALCÂNTARA SANTANA
Roteamento em Redes Ópticas
Transparentes Utilizando Redes Neurais de
Hopfield
Dissertação apresentada como requisito parcial
para a obtenção do grau de Mestre em
Engenharia da Computação
Prof. Dr. Carmelo J. A. Bastos Filho
Orientador
Prof. Dr. Joaquim Ferreira Martins Filho
Co-orientador
Recife, março de 2010
ads:
CIP – CATALOGAÇÃO NA PUBLICAÇÃO
S232r Santana, Robson Alcântara
Roteamento em Redes Ópticas Transparentes Utilizando
Redes Neurais de Hopfield / Robson Alcântara Santana. –
Recife: PPGEC da UPE, 2010.
103 f.: il., 41 fig., 24 tab.
Dissertação (mestrado) – Universidade de Pernambuco.
Programa de Pós-Graduação em Engenharia da Computação,
Recife, BR–PE, 2010. Orientador: Carmelo J. A. Bastos Fi-
lho; Co-orientador: Joaquim Ferreira Martins Filho.
1. Redes neurais de hopfield. 2. Redes ópticas. 3. RWA.
4. Otimização multi-objetiva. 5. Inteligência computacional
de enxames. I. Bastos Filho, Carmelo J. A.. II. Martins
Filho, Joaquim Ferreira. III. Título.
CDU 658.51:007.52
“Não existe sempre,
existe apenas o agora.
Não existe certo ou errado,
apenas as consequências das suas ações.”
— Hank Moody
Agradecimentos
À Deus, a quem posso chamar de amigo.
Aos meus pais Roberto Santana e Maria José Alcântara por terem me dado apoio
e principalmente tranquilidade para a realização deste trabalho.
Ao Professor e orientador Carmelo José Albanez Bastos Filho pelos ensinamen-
tos, conselhos, tarefas, condições de trabalho, confiança, perdão e cooperação nestes
quatro anos de parceria.
Ao Professor e co-orientador Joaquim Ferreira Martins Filho pelas orientações e
oportunidades oferecidas.
Ao Professor Fernando Buarque de Lima Neto pelas orientações, aulas, debates
e oportunidades.
Ao aluno de iniciação científica Dennis Rodrigo pela cooperação nas realizações
das simulações computacionais feitas neste trabalho e pelas missões.
À minha família pelo apoio, disposição para qualquer eventualidade e por ter
que suportar esta faculdade que não acaba nunca. E que não acaba agora.
À Escola Politécnica de Pernambuco pela contribução na minha formação e por
ter me recebido de braços abertos no retorno e à FACEPE pelo suporte financeiro.
Aos parceiros de QG da qual não tenho palavras para dimensionar a ordem de
grandeza destes homens, outro patamar. Salomão Madeiro pelas lições de moral,
Marcos Álvares por ter dado um novo gás ao QG, Murilo Pontes pela parceira (XP)
no MOPSO-CDR e George Silva pelo respeito. Minhas sinceras desculpas a vocês
por me aguentar e meu muito obrigado.
Ao quarteto do projeto de arquitetura, por ter aprendido com eles que existe
diversão e encanto após horas de batalha no desenvolvimento de um hardware. O
que eu falo sobre Nadilma Nunes? Não dá. Nara Portela é um ponto MUITO
distante da reta, Redes está aí para validar minha afirmação. Danilo Costa, grande!
Aos colegas de mestrado, principalmente Júlio Taveira (também colega de gra-
duação e amigo), Moisés Danziger, Cristiane Queiroz, Rogério Tibúrcio, Marcelo
Diniz e Marcelo Teixeira pela amizade e cooperação.
Aos colegas adotivos Abraham Licoln, Samuel Martins e Carlos Alberto pelos
passeios de bike, sucos, debates sobre o MC68000 e desculpas por ter alugado vocês.
Aos amigos da IC Adson Matoso, Marcos Oliveira, Débora Oliveira e Caio Duarte
pelos momentos de descontração conversando sobre PSP, hardware e negócios.
A Nara Campos e Maria Goreth, se não me falhe a memória, únicas pessoas do
mundo real (nem tanto) que me incentivaram a fazer este mestrado.
Aos Professores de graduação, ao Professor Marinho, ao Professor Feitosa e à
Professora Rosemaria pro contribuírem com minha formação.
À família Miranda pelo respeito e admiração mútuos.
Aos amigos Hamilton Estima, João Ferreira, Eliano Rodrigues e Antonio Cle-
mente pelos momentos de lazer.
Sumário
LISTA DE ABREVIATURAS E SIGLAS . . . . . . . . . . . . . . . vii
LISTA DE SíMBOLOS . . . . . . . . . . . . . . . . . . . . . . . . . . ix
LISTA DE FIGURAS . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv
LISTA DE TABELAS . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi
RESUMO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xviii
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xx
1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Organização da dissertação . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 REDES ÓPTICAS . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1 Dispositivos da camada óptica . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Transimissores ópticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.2 Fibras ópticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.3 Amplificadores ópticos . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.4 Comutadores/switchs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Principais formas de degradação do sinal na camada física . . . . . . . . 9
2.2.1 Atenuação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.2 Dispersão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.3 Ruído . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.4 Interferência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 Medições quantitativas de qualidade do sinal e de qualidade de rede . . 11
2.3.1 Relação sinal ruído . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.2 Fator de ruído e Figura de ruído . . . . . . . . . . . . . . . . . . . . . . 12
2.3.3 Taxa de erro de bit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3.4 Interferência intersimbólica . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3.5 Diagrama de olho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3.6 Probabilidade de bloqueio . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4 Sistemas Ópticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4.1 Técnicas de multiplexação . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4.2 Geração das redes ópticas . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4.3 Classificação das Redes Ópticas segundo transparência . . . . . . . . . . 15
2.4.4 Restrição da continuidade obrigatória de comprimento de onda . . . . . 16
2.5 Roteamento e Alocação de Comprimento de Onda (RWA - Routing and
Wavelength Assignment) . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.5.1 Tipos de roteamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.5.2 Algoritmos de roteamento . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.5.3 Algoritmos de atribuição de comprimentos de onda . . . . . . . . . . . . 20
2.6 Modelo da Camada Física . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 REDES NEURAIS DE HOPFIELD . . . . . . . . . . . . . . . . . 26
3.1 Redes Neurais Artificiais . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.1.1 Neurônio biológico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.2 Neurônio artificial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Redes Neurais de Hopfield . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3 Redes Neurais de Hopfield aplicadas ao problema de roteamento . . . . 32
3.3.1 Modelo de Ali e Kamoun . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3.2 Execução do algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3.3 Modelo de Bastos-Filho et al. . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4 Redes Neurais de Hopfield aplicadas ao problema de RWA . . . . . . . . 38
4 UMA ABORDAGEM PARA PROBLEMAS MULTI-OBJETIVOS
BASEADA EM PARTICLE SWARM OPTIMIZATION UTI-
LIZANDO CROWDING DISTANCE E ROULETTE WHEEL 39
4.1 Conceitos básicos de Otimização Multiobjetivo . . . . . . . . . . . . . . 40
4.2 Particle Swarm Optimization . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2.1 PSO básico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.2.2 Técnicas de controle e atualização da velocidade do PSO . . . . . . . . 46
4.2.3 Estruturas da rede social . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.3 Propostas prelimiares de PSO para problemas multiobjetivo . . . . . . . 49
4.3.1 m-DNPSO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3.2 MOPSO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3.3 CSS-MOPSO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.3.4 MOPSO-CDLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.4 Multiple Objective Particle Swarm Optimization with Crowding Dis-
tance e Roulette Wheel (MOPSO-CDR) . . . . . . . . . . . . . . . . . . 53
4.4.1 Seleção do líder social . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.4.2 Seleção do líder cognitivo . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.4.3 Turbulência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.4.4 Arquivo externo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.5 Configurações das Simulações . . . . . . . . . . . . . . . . . . . . . . . 55
4.5.1 Funções de teste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.5.2 Métricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.5.3 Configurações dos Parâmetros . . . . . . . . . . . . . . . . . . . . . . . 58
4.6 Comparativos entre as técnicas MOPSO selecionadas . . . . . . . . . . 58
4.7 Conclusões relacionadas à técnica MOPSO-CDR . . . . . . . . . . . . . 59
5 UM ALGORITMO DE ROTEAMENTO PARA REDES ÓP-
TICAS USANDO REDES NEURAIS DE HOPFIELD . . . . . 66
5.1 Modelo baseado na distância, carga dos enlaces e casamento de canais
entre enlaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.2 Arranjo experimental para análise de µ
6
e µ
7
. . . . . . . . . . . . . . . 70
5.3 Análise da influência de µ
6
e µ
7
. . . . . . . . . . . . . . . . . . . . . . 74
6 OTIMIZAÇÃO MULTI-OBJETIVA USANDO INTELIGÊNCIA
DE ENXAMES DO ALGORITMO DE ROTEAMENTO BA-
SEADO EM REDES NEURAIS DE HOPFIELD ADAPTADO
PARA REDES ÓPTICAS . . . . . . . . . . . . . . . . . . . . . . 81
6.1 Otimização de parâmetros utilizando MOPSO-CDR . . . . . . . . . . . 81
7 CONCLUSÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.1 Complexidade do algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . 92
7.2 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
APÊNDICE A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
REFERÊNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
Lista de Abreviaturas e Siglas
ACO Ant Colony Optimization
ANN Artificial Neural Networks
ASE Amplified Spontaneous Emission
BER Bit Error Rate
BF Best Fit
C Coverage
CI Computational Inteligence
CSI Computational Swarm Inteligence
DLE Dynamic Lightpath Estabilishment
EDFA Erbium Dopped Fiber amplifier
F Noise Factor
FF First Fit
FWM Four Wave Mixing
GA Genetic Algorithm
HNN Hopfield Neural Networks
HV Hypervolume
IM/DD Intensity Modulation/Direct Detection
ISI Intersymbol Interference
JE Just Enough
LASER Light Amplification by Stimulated Emission of Radiation
LED Light Emitting Diode
LRW Least Resistance Weight
LU Least Used
MCP Modelo de McCulloch-Pitts
MH Minimum Hops
MOPSO-CDR Objective Particle Swarm Optimization with Crowding Distance and
Roulette Wheel
MS Maximum Spread
MU Most Used
NF Noise Figure
OADM Optical Add/drop Multiplexers
O-E-O Óptico-Eletrônico-Óptico
OpFF Optimized First Fit
OSNR Optical Signal to Noise Ratio
OSNR-R Optical Signal to Noise Ratio Routing
OXC Optical Cross-connect
PIAWF Physical Impairments Aware Adaptive Weight Function
PMD Polarization Mode Dispersion
PON Passive Optical Network
PSO Particle Swarm Optimization
PSR Power Series Routing
QoS Quality of Service
QoT Quality of Transmission
R Random
RFA Raman Fiber Amplifiers
RWA Routing and Wavelength Assignment
S Spacing
SA Simulated Annealing
SDH Synchronous Digital Hierarchy
SE Stimulated Emission
SLE Static Lightpath Estabilishment
SONET Synchronous Optical Network
SP Shortest Path
SPM Self Phase Modulation
SRS Stimulated Raman Scattering
SSE Source Spontaneous Emission
TDM Time Division Multiplexing
TSP Traveling Salesman Problem
WDM Wavelength Division Multiplexing
XPM Cross-Phase Modulation
Lista de Símbolos
α Constante de atenuação da fibra
β Coeficiente multiplicativo para cálculo do µ
6
γ Média do intervalo de tempo entre chamadas
δ Função Delta de Kronecker
δt Passo incremental de tempo
δ
%
Representa o alargamento temporal do pulso óptico, em percenta-
gem
δ
%QoT
Alargamento temporal máximo permitido
∆t
P MD
Alargamento do pulso óptico, devido ao efeito de PMD
∆t
RD
Alargamento do pulso óptico, devido ao efeito da dispersão residual
∆V
th
Limiar de estabilidade da HNN
, η, υ Expoentes para os cálculos de A, B, C
ε Fator de isolação entre as portas do switch
θ ângulo entre a linha datum e o ponto datum
λ Comprimento de onda
λ Grau de inclinação da função de ativação
λ
a
xi
Número de canais ativos no enlace entre nós x e i
λ
T
Número total de comprimentos de onda
µ
1
Valor de µ
1
alterado
µ
1
, µ
2
, µ
3
, µ
4
, µ
5
Constantes da equação de energia
µ
6
Peso dado ao percentual dos canais ativos no enlace
µ
7
Peso dado ao percentual de comprimentos de onda casados entre
enlaces
ρ Matriz de conexão dos enlaces
ρ
xi,k
onde utilização do canal k do enlace entre nós x e i
φ
c
xi,yj
Número de canais casados entre os enlaces xi e yj
ϕ
xi,yj,k
Casamento do canal k entre os enlaces xi e yj
χ Fator de constrição
ω Termo de inércia
τ Constante de tempo da equação de atualização da entrada do
neurônio do modelo de Hopfield
A Conjunto de enlaces
A Constante da equação de atualização do neurônio do modelo de
Schuler et al.
A
1
Parâmetro obtido por meio de ajuste em curvas experimentais
A
2
Parâmetro obtido por meio de ajuste em curvas experimentais
B Constante da equação de atualização do neurônio do modelo de
Schuler et al.
b
k
polarização do neurônio
B
o
Largura de banda do filtro óptico
c
1
Coeficiente de aceleração cognitivo
c
2
Coeficiente de aceleração social
C Constante da equação de atualização do neurônio do modelo de
Schuler et al.
C Coverage
C
ij
Custo de um enlace
C
T
ij
Quantidade de comprimentos de onda livres de um enlace
C
T
Quantidade total de comprimentos de onda de um enlace
C
bloqueadas
Número de chamadas bloqueadas pela rede
C
total
Número total de chamadas solicitadas à rede
D
λref
DCF
Coeficiente de dispersão cromática da fibra de compensação
d
j
Comprimento do j-ésimo enlace pertecente à rota
D
P MD
Coeficiente de PMD
D
λref
T F
Coeficiente de dispersão cromática do comprimento de onda refe-
renciado
E Função de energia
F
Amp
Fator de ruído dinâmico do amplificador
F
0
Amp
Fator de ruído do amplificador quando potências baixas são consi-
deradas
f
fwm
Frequência em que ocorre a mistura de quatro ondas (FWM - Four
Wave Mixing)
f
i
Funções objetivos
f(.) Função de ativação do neurônio
G Grafo não orientado
G
Amp
Ganho dinâmico linear
G
0
Amp
Ganho não-saturado do amplificador
G
Amp1
Ganho dinâmico linear do booster
G
Amp2
Ganho dinâmico linear do pré-amplificador
g
i
, h
j
Funções de restrições dos problemas multi-objetivos
gBest Líder social da partícula
h Constante de Planck
H Tempo, em média, que uma chamada fica ativa na rede óptica
HV Hypervolume
I
i
Polarização externa do modelo de Hopfield
K
xi
Utilização dos canais do enlace entre nós x e i
L Comprimento da fibra
L
Dx
Perda do demultiplexador
L
Mx
Perda do multiplexador
L
Sw
Perda do switch
L
DCF
j
Comprimento da fibra de compensação no enlace j
L
T F
j
Comprimento da fibra óptica no enlace j
L
xi,yj
Termo que inclui casamento de comprimentos de onda entre o en-
lace xi
L
sd
Custo da rota
MS Maximum Spread
N Conjunto de nós da rede de comunicação
n
1
Índice de refração do núcleo da fibra
n
2
Índice de refração da casca da fibra
N
Amp
(λ) Ruído ASE adicionado pelos amplificadores
N
in
Ruído na entrada do sistema
N
out
Ruído na saída do sistema
N
Sw
j
(λ) Potência de ruído óptica gerada por crosstalk
OSNR Relação sinal ruído óptica
OSNR
in
Relação sinal ruído óptica na entrada de um dispositivo
OSNR
out
Relação sinal ruído óptica na entrada de um dispositivo
OSNR
Qot
Limiar de OSNR para garantir a qualidade de transmissão
p
i
(t) Melhor posição encontrada pela partícula i durante o processo de
busca
P
∗
Pareto-ótimo
PF
∗
Pareto front
P (L) Potência do pulso óptico a uma distância de L
P (R) Sensibilidade de receptor
P (T ) Potência do transmissor
P B Probabilidade de bloqueio
pBest Líder cognitivo da partículas
P
λin
Potência óptica de entrada por canal
P
out
Potência óptica do sinal na saída do sistema
P
in
Potência óptica do sinal na entrada do sistema
P
sat
Potência de saturação
P
sinal
Potência média do sinal óptico recebido
P
Sw
j
(λ) Potência óptica do sinal
P
ruido
Potência do ruído óptico recebido
P
sd
Rota para a fonte s e destino d
r
1
, r
2
Números aleatórios gerados por uma distribuição uniforme no in-
tervalo [0, 1]
S Spacing
SiO
2
Sílica
S
DCF
Inclinação da curva de dispersão
S
T F
Inclinação da curva de dispersão
T
ij
Peso sináptico do modelo de Hopfield
U
i
Entrada do neurônio do modelo de Hopfield
u
k
Resultado da função soma
V
i
Saída do neurônio do modelo de Hopfield
v
i
(t + 1) Vetor de velocidade da partícula i
V
max,j
Velocidade máxima permitida para a partícula j
w
ij
Função de custo do enlace (i, j)
w
k1
, w
k2
, ..., w
km
Pesos sinápticos do neurônio
x Vetor de variáveis de decisão do espaço de busca
x
1
, x
2
, ..., x
m
Sinais de entradas do neurônio
x
i
Posição da partícula i
x
max,j
Valor de máximo do domínio de x na dimensão j
x
min,j
Valor de máximo do domínio de x na dimensão j
y
k
Saída do neurônio k
Y
xi
Matriz de saída da HNN binarizada
Lista de Figuras
2.1 Ilustração da secção de corte transversal de um exemplo de fibra
óptica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Ilustração de um OXC. . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Atenuação da silica em função do comprimento de onda. . . . . . 9
2.4 Dispersão de pulsos em função da distância percorrida dentro da
fibra. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5 Principais parâmetros em um diagrama do olho óptico. . . . . . . 13
2.6 Configuração do enlace contendo os dispositivos considerados na
modelagem apresentada. . . . . . . . . . . . . . . . . . . . . . . . 22
2.7 Ganho e figura de ruído do amplificador em função da potência
de entrada por canal, ambos obtidos de resultados experimentais
(pontos) e modelo empírico (curvas sólidas) [73]. . . . . . . . . . . 24
3.1 Componentes de um neurônio biológico. . . . . . . . . . . . . . . 27
3.2 Neurônio artificial de McCulloch e Pitts. . . . . . . . . . . . . . . 28
3.3 Funções de ativação mais utilizadas em redes neurais artificiais. . 29
3.4 Exemplo de uma HNN com atratores armazenados na memória
como pontos de equilíbrio. . . . . . . . . . . . . . . . . . . . . . . 30
3.5 Arquitetura da rede neural de Hopfield. . . . . . . . . . . . . . . . 31
3.6 Representação de uma rede de comunicação com as matrizes de
custos e topologia. . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.1 Relação de dominância para um espaço de dois objetivos . . . . . 41
4.2 O Pareto front de um conjunto de soluções para um espaço de
dois objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.3 Representação do “vôo” de duas partículas: (a) no instante t e (b)
no instante t + 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.4 Exemplos de estruturas da rede social. . . . . . . . . . . . . . . . 50
4.5 Representação gráfica do adaptive grid utilizado no MOPSO. . . . 51
4.6 Escolha do g
Best1
para cada partícula. . . . . . . . . . . . . . . . 52
4.7 Escolha do g
Best2
para cada partícula em relação ao objetivo f
i
. . 52
4.8 Cálculo do crowding distance. . . . . . . . . . . . . . . . . . . . . 53
4.9 Pareto front encontrado pelas abordagens para a função ZDT1. . 60
4.10 Pareto front encontrado pelas abordagens para a função ZDT2. . 61
4.11 Pareto front encontrado pelas abordagens para a função ZDT3. . 63
4.12 Pareto front encontrado pelas abordagens para a função ZDT4. . 64
4.13 Pareto front encontrado pelas abordagens para a função ZDT6. . 65
5.1 Exemplo para ilustrar o conceito de casamento de canais em redes
ópticas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.2 Topologia de rede usada nas simulações. . . . . . . . . . . . . . . 70
5.3 Fluxograma do algoritmo de RWA. . . . . . . . . . . . . . . . . . 73
5.4 Probabilidade de bloqueio em função da carga da rede para con-
figurações da HNN, considerando diferentes valores para µ
6
. . . . 75
5.5 Probabilidade de bloqueio em função da carga da rede para con-
figurações da HNN, considerando diferentes valores para µ
7
. . . . 76
5.6 Probabilidade de bloqueio em função da carga da rede para confi-
gurações da HNN, considerando β = 0, 7 e diferentes valores para
µ
7
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.7 Probabilidade de bloqueio em função da carga da rede para HNN
considerando os melhores casos. . . . . . . . . . . . . . . . . . . . 79
5.8 Probabilidade de bloqueio em função da carga da rede para dife-
rentes abordagens de roteamento. . . . . . . . . . . . . . . . . . . 80
6.1 Evolução do Pareto front para a simulação considerando a otimi-
zação de todos os parâmetros da HNN modificada. . . . . . . . . 83
6.2 Evolução do Pareto front para a simulação considerando a otimi-
zação dos parâmetros da HNN modificada exceto µ
6
. . . . . . . . 84
6.3 Evolução do Pareto front para a simulação considerando a otimi-
zação dos parâmetros da HNN modificada exceto µ
7
. . . . . . . . 86
6.4 Evolução do Pareto front para a simulação considerando a otimi-
zação dos parâmetros da HNN do modelo de Schuler et al. . . . . 87
6.5 Paretos fronts da iteração final das simulações efetuadas. . . . . . 87
6.6 Probabilidade de bloqueio em função da carga da rede para as
configurações otimizadas da HNN. . . . . . . . . . . . . . . . . . 89
6.7 Probabilidade de bloqueio em função da carga da rede para dife-
rentes abordagens de roteamento. . . . . . . . . . . . . . . . . . . 90
Lista de Tabelas
3.1 Valores dos parâmetros µ
i
s. . . . . . . . . . . . . . . . . . . . . . 36
4.1 Relações de dominância entre soluções. . . . . . . . . . . . . . . . 41
4.2 Valor médio e desvio padrão – ZDT1. . . . . . . . . . . . . . . . . 59
4.3 Valor médio e desvio padrão – ZDT2. . . . . . . . . . . . . . . . . 59
4.4 Valor médio e desvio padrão – ZDT3. . . . . . . . . . . . . . . . . 62
4.5 Valor médio e desvio padrão – ZDT4. . . . . . . . . . . . . . . . . 62
4.6 Valor médio e desvio padrão – ZDT6. . . . . . . . . . . . . . . . . 62
5.1 Valores dos parâmetros da HNN utilizado nas simulações. . . . . 71
5.2 Valores dos parâmetros da rede óptica utilizado nas simulações. . 72
5.3 Tempo de simulação para cada requisição de chamada na rede
óptica para diferentes valores de β. . . . . . . . . . . . . . . . . . 75
5.4 Tempo de simulação para cada requisição de chamada na rede
óptica para vários valores de µ
7
. . . . . . . . . . . . . . . . . . . . 77
5.5 Tempo de simulação para cada requisição de chamada na rede
óptica para diferentes configurações de HNN considerando β =
0, 7 e diferentes valores para µ
7
. . . . . . . . . . . . . . . . . . . . 78
5.6 Tempo de simulação para cada requisição de chamada na rede
óptica para os melhores casos de configurações da HNN. . . . . . 78
5.7 Tempo de simulação para cada requisição de chamada na rede
óptica para diferentes abordagens de roteamento. . . . . . . . . . 80
6.1 Intervalos das posições e velocidades assumidas pelas partículas
do MOPSO-CDR para cada dimensão. . . . . . . . . . . . . . . . 82
6.2 Valores dos parâmetros do MOPSO-CDR. . . . . . . . . . . . . . 83
6.3 Valores das métricas de convergência e diversidade para a simu-
lação considerando a otimização de todos os parâmetros da HNN
modificada. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.4 Valores das métricas de convergência e diversidade para a simu-
lação considerando a otimização dos parâmetros da HNN modifi-
cada exceto µ
6
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.5 Valores das métricas de convergência e diversidade para a simu-
lação considerando a otimização dos parâmetros da HNN modifi-
cada exceto µ
7
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.6 Valores das métricas de convergência e diversidade para a simula-
ção considerando a otimização dos parâmetros da HNN do modelo
de Schuler et al. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.7 Valor do Coverage entre o front da última iteração da simulação
que considera todos os parâmetros da HNN e os fronts da última
iteração das outras simulações. . . . . . . . . . . . . . . . . . . . 88
6.8 Valores dos parâmetros da HNN utilizado nas simulações. . . . . 88
6.9 Tempo de simulação para cada requisição de chamada na rede
óptica para as quatro possíveis abordagens de HNN. . . . . . . . 89
6.10 Tempo de simulação para cada requisição de chamada na rede
óptica para diferentes abordagens de roteamento. . . . . . . . . . 90
Resumo
A necessidade em transmitir dados em alta velocidade, assim como o crescimento
acentuado das redes de comunicações, principalmente da Internet, requerem a uti-
lização de redes com alta capacidade de transmissão. As Redes Eletrônicas atuais
não são capazes de suprir esta demanda por velocidade e número de usuários. Re-
des Ópticas utilizando multiplexação por comprimento de onda (WDM - Wavelength
Division Multiplexing), são capazes de prover a capacidade de transmissão exigida
pela demanda atual.
Com o intuito de minimizar o desperdício dos recursos das redes ópticas e ma-
ximizar a quantidade e qualidade das conexões estabelecidas é necessário um bom
par de abordagens de roteamento e atribuição de comprimentos de onda (RWA -
Routing and Wavelength Assignment). Porém a obtenção destas informações são
custosas em tempo de processamento.
Outra possibilidade é utilizar informações triviais dos enlaces em conjunto com
algoritmos baseados em técnicas de Inteligência Computacional (CI - Computatio-
nal Intelligence), já que estas abordagens são capazes de adequar-se aos objetivos
desejados a partir de entradas que não necessariamente mapeie os objetivos.
Redes Neurais de Hopfield (HNN - Hopfield Neural Networks) é uma técnica de
CI que pode ser utilizada como algoritmo de roteamento em Redes Ópticas. Porém,
para que informações específicas sobre carga dos enlaces possam ser inseridas na
rede neural, torna-se necessário modificações nas entradas da rede neural. Estas
modificações são as principais propostas desta dissertação.
As HNN possuem parâmetros com valores padrões, porém estes parâmetros po-
dem ser modificados com o objetivo de acelerar a resposta ou melhorar o desempe-
nho. Técnicas baseadas em Inteligência Computacional de Enxames (CSI - Compu-
tational Swarm Intelligence) podem ser utilizadas para buscar e definir um conjunto
de parâmetros que tenham como compromisso atender os diversos objetivos solici-
tados, este que é outro objetivo deste trabalho. A técnica aplicada foi Multiple
Objective Particle Swarm Optimization with Crowding Distance and Roulette Wheel
(MOPSO-CDR).
A técnica MOPSO-CDR é uma nova abordagem baseada em uma proposta já
existente (MOPSO-LS). Esta abordagem tornou possível encontrar parâmetros da
HNN de forma mais eficaz e com maior qualidade. As modificações foram na forma
de escolha dos líderes sociais das partículas (gBest) e atualização da mémoria das
partículas (pBest).
Experimentos foram feitos com as novas propostas das HNN, os resultados en-
contrados foram satisfatórios quando comparados com o modelo de Schuler et al.,
mostrando a viabilidade do modelo proposto.
Os resultados dos experimentos com os parâmetros encontrados pelo MOPSO-
CDR mostraram que a proposta deste trabalho é superior na eficácia do uso dos
recursos da rede em comparação com outras abordagens da literatura.
Palavras-chave: Redes neurais de hopfield, redes ópticas, RWA, otimização multi-
objetiva, inteligência computacional de enxames.
Abstract
The need to transmit data at high speed, as well as the accelerated growth of
communications networks, especially the Internet, require the use of networks with
high transmission capacity. Computer Networks nowadays are not able to meet
this demand for speed and number of users. Optical Networks using Wavelength
Division Multiplexing (WDM), are more lively to provide the transmission capacity
required by current demand.
In order to minimize the waste of resources of optical networks and maximizing
the quantity and quality of established connections, a suitable pair of approaches
of Routing and Wavelength Assignment (RWA) is needed. However obtaining this
information is costly in terms of processing time.
Another possibility is to use trivial information of the links together with al-
gorithms based on techniques of Computational Intelligence (CI), since these ap-
proaches are able to adjust to the desired goals from entries that do not necessarily
map the objectives.
Hopfield Neural Networks (HNN) is a technique of CI that can be used as the
routing algorithm in optical networks. But for the specific information about load
of links to be inserted into the neural network, requires modifications in the existing
models. These changes are precisely the main proposal of this dissertation.
The HNN have parameters with default values, but these parameters can be
modified in order to speed up the response or to improve the network performance.
Techniques based on Computational Swarm Intelligence (CSI) can be used to seek
and define a set of parameters that are committed to meet the various objectives,
this is another objective of this work. The technique used was Multiple Objective
Particle Swarm Optimization with Crowding Distance and Roulette Wheel (MOPS-
CDR).
The technique MOPSO-CDR is a new approach based on an existing proposal
(MOPSO-LS). This approach made it possible to find the HNN parameters more
efficiently and with better quality. The changes were in the form of choice for social
leaders of the particles (gBest) and update the memory of the particle (pbest).
Experiments were carried out with the new proposals of HNN, the results were
satisfactory when compared with the model of Schuler et al., demonstrating the
feasibility of the proposed model.
The results of experiments with the parameters found by MOPSO-CDR showed
that this proposal is more effective to use the network resources compared to other
approaches to literature.
Keywords: Hopfield neural networks, optical networks, RWA, multi-objective op-
timization, computational swarm intelligence.
Capítulo 1
Introdução
O crescimento da Internet e aplicações multimídia de alto volume de dados implicam
em enormes necessidades de banda de transmissão [84], [85], [106] consequentemente.
Para fornecer alta capacidade de comunicação são necessárias redes de comunica-
ção de alta velocidade. Redes ópticas utilizando multiplexação por comprimento
de onda (WDM – Wavelength Division Multiplexing) são candidatas atrativas para
suprir esta demanda [42], [93] pois aumentam a capacidade de transmissão, já que
a fibra é dividida em várias “fibras virtuais” [77]. A tecnologia WDM oferece alta
capacidade com baixas taxas de erros, subdividindo a capacidade da fibra em múl-
tiplos canais, onde cada canal pode operar na atual velocidade de transmissão das
redes em funcionamento.
Redes ópticas podem ser opacas ou transparentes (totalmente ópticas). Nas re-
des opacas cada nó regenera o sinal (conversão óptico-eletrônico e eletrônico-óptico)
para realizar suas funções, o que acarreta relativa baixa capacidade de transmissão
devido às limitações na transmissão de dados dos equipamentos eletrônicos em com-
paração com a capacidade da fibra óptica. Nestas redes, as funções de transmissão
e comutação são independentes e a acumulação da degradação do sinal é menos
importante, por causa da regeneração do sinal nos nós. Nas redes transparentes não
há regeneração, o sinal continua no domínio óptico do nó fonte ao nó destino. Es-
tas redes operam independente de taxa de transmissão, protocolo e formato. Além
disso, são mais fáceis de atualizar e podem suportar diferentes tipos de tráfegos.
Em redes ópticas transparentes, um caminho é chamado de lightpath. Ele repre-
senta o caminho óptico que pode atravessar enlaces sem sofrer qualquer conversão
de/para meio eletrônico. Neste caso, existem três principais restrições relacionadas
com o comprimento de onda: restrição de continuidade de comprimento de onda
(WCC - Wavelength Continuity Constraint), restrição da atribuição de comprimen-
tos de onda distintos (DWAC - distinct wavelength assignment constraint) e restrição
da não continuidade de comprimento de onda (NWCC - Non Wavelength Continuity
Constraint). No WCC, o mesmo comprimento de onda deve ser usado em todos os
enlaces (lightpath) ao longo da rota escolhida. No DWAC, dois lightpaths não po-
dem ser atribuídos com o mesmo comprimento de onda. E no NWCC, diferentes
comprimentos de onda podem ser usados nos enlaces através da rota, porém os nós
devem ter a capacidade de converter os comprimentos de onda. Conversão de com-
primento de onda é a capacidade de converter a informação oriunda de um enlace
em um comprimento de onda para outro comprimento de onda que será enviado
no próximo enlace do lightpath. Eliminando da rede esta capacidade de conversão,
2
o custo dos comutadores é significativamente reduzido, a desvantagem é a redução
da eficiência da rede porque mais comprimentos de onda são necessários. Estudos
mostram que o aumento de eficiência por usar conversão de comprimento de onda
é pequena comparado com o aumento de custo da rede [87], [102]. Este trabalho
abordará redes ópticas com restrições WCC.
O problema algorítmico central das redes ópticas é o processo de roteamento e
atribuição de comprimento de onda (RWA - Routing and Wavelength Assignment).
Para uma dada topologia de rede e um conjunto de pares origem-destino, existem:
atribuição de rota, obtido calculando uma rota para um lightpath entre cada par
origem-destino, e; atribuição de comprimento de onda, determina o comprimento de
onda a ser alocado para o lightpath sobre o determinado enlance.
Para redes ópticas com tráfego dinâmico, um lightpath requisitado deve ser es-
tabelecido e ter comprimentos de onda atribuído independentemente dos outros
lightpaths que já tenham sido atribuídos ou que venham a ser atribuídos no futuro.
O objetivo é minimizar o número de comprimentos de onda utilizados e a probabili-
dade de bloqueio das chamadas para maximizar o número de conexões estabilizadas
pela rede.
O processo de roteamento tem significante impacto no desempenho da rede.
Alguns algoritmos usam heurísticas baseadas em métricas predefinidas. Algumas
destas métricas são: menor caminho (SP - Shortest Path), Menor número de saltos
(MH - Minimum Hops), Least Resistance Weight (LRW) [103], Optical Signal to
Noise Ratio Routing (OSNR-R) [62], Physical Impairments Aware Adaptive Weight
Function (PIAWF) [19], Power Series Routing (PSR) [64]. Dentre os algoritmos
de roteamento usados que utilizam estas métricas, pode-se destacar o algoritmo de
Dijkstra (Estado do Enlace) [31] e o algoritmo de Bellman-Ford (Vetor Distância)
[13], [37].
Algumas técnicas de inteligência computacional estão sendo utilizadas para so-
lucionar o problema de RWA: Otimização por Colônia de Formigas (ACO – Ant
Colony Optimization) [69], [38], [70], [9], Algoritmos Algoritmos Genéticos (GA -
Genetic Algorithm) [5], [61] e Redes Neurais de Hopfield (HNN - Hopfield Neural
Networks) [57], [58].
Um algoritmo de roteamento deve selecionar uma rota em tempo real e tam-
bém deve ser adaptativo (para que possa se adequar às alterações da topologia da
rede óptica), assim como deve manter uma qualidade de serviço (QoS – Quality of
Service) estipulada.
Redes Neurais Artificiais (ANN – Artificial Neural Network) são ótimas can-
didatas para solucionar o problema devido a sua alta velocidade computacional,
possibilidade de trabalhar com dados incertos, robustez e capacidade de processa-
mento paralelo de dados. Características importantes para a adaptação em relação
às alterações nas topologias das redes.
Hopfield e Tank [45], [46], [47], descreveram uma ANN com configuração re-
cursiva adequada para solucionar problemas de otimização, como por exemplo o
Problema do Caixeiro Viajante (TSP – Traveling Salesman Problem) [47]. Este
tipo de ANN é chamada de Redes Neurais de Hopfield (HNN – Hopfield Neural
Networks). O uso das HNN para solucionar o problema do menor caminho (SP –
Shortest Path) foi iniciado por Rauch e Winarske [81]. Outras abordagens das HNN
para o problema SP foram apresentadas, mostrando que esta técnica pode ser uti-
lizada como algoritmo de roteamento para redes de computadores tradicionais [98],
3
[3], [7], [88], [89] [8], [72], [2], [94], [55], [56].
O problema de alocação de rotas em redes ópticas transparentes é similar ao
problema de roteamento em redes tradicionais quando para cada comprimento de
onda é considerada uma rede individual.
Baseado neste fato, é possível utilizar as HNN para alocar rotas em redes óp-
ticas transparentes, utilizando as métricas que foram citadas. Neste trabalho são
utilizadas como métricas: informações de topologia (comprimento dos enlaces) e
informações de carga (utilização dos comprimentos de onda dos enlaces e casamento
dos comprimentos de onda entre os elances). Esta é a primeira abordagem a utilizar
a métrica casamento dos comprimentos de onda entre os elances.
Utilizando-se as métricas citadas como entrada para o algoritmo, será necessária
uma escolha de coeficientes multiplicativos para os termos das equações que levam
em consideração estas métricas (a HNN possui equações da qual algumas delas
estão relacionadas com a função de custo). A variação destes coeficientes implica em
variação no desempenho da rede. Otimizar os parâmetros de entrada do algoritmo de
roteamento pode fazer com que o algoritmos encontrem rotas de forma mais rápida,
e/ou diminua a probabilidade de bloqueio, e/ou distribua a carga na rede. Estes
requisitos de problemas a resolverpropriedades da rede caracterizam um problema
de otimização multi-objetivo.
Problemas de otimização que tem mais que uma função objetivo são comuns em
diversos campos ou áreas de conhecimento. Nestes problemas, os objetivos a serem
otimizados normalmente estão em conflito uns com os outros, o que significa que
não existe uma única solução para estes problemas. Existe um conjunto de soluções
com compromisso em balancear o conjunto de objetivos, conhecido como Pareto.
Existem técnicas de inteligência computacional que podem resolver este tipo de
problema, como abordagens multi objetivas de enxame de partículas (MOPSO -
Multi Objective Particle Swarm Optimization) [82], [26] [48], [99].
O objetivo desta dissertação é o de utilizar HNN para melhorar o processo de
roteamento em redes ópticas transparentes levando em consideração a alocação de
canais corrente. Este algoritmo mostrou ser capaz de encontrar rotas a partir de
uma métrica ou um conjunto de métricas que terão importância variável, de acordo
com a característica da rede.
1.1 Organização da dissertação
O capítulo 2 é dedicado às Redes Ópticas. Neste capítulo são apresentados os prin-
cipais dispositivos da camada óptica, descritas as principais formas de degradação
do sinal na camada física, também são descritas as principais medições quantitati-
vas de qualidade do sinal e de qualidade de rede. Em relação aos sistemas ópticos
são apresentadas as técnicas de multiplexação do sinal óptico, classificação quanto
à transparência, alguns exemplos de algoritmos de roteamento e atribuição de com-
primentos de onda e o modelo de rede utilizado nas simulaçãoes.
O capítulo 3 é dedicado ao modelo de Redes Neurais de John Hopfield. Este
capítulo inicia com um resumo sobre as Redes Neurais Artificiais, em seguida, a
descrição das HNN e sua aplicação para o problema do menor caminho (SP - Shortest
Path), finalmente são apresentados as otimizações, variações e aplicações do modelo
aplicado ao problema do roteamento.
4
No capítulo 4 é apresentada um técnica proposta neste trabalho chamada de
Multiple Objective Particle Swarm Optimization with Crowding Distance and Rou-
lette Wheel (MOPSO-CDR) que é uma abordagem baseada no PSO para encontrar
soluções para problemas de otimização multiobjetivo, e que será utilizada para oti-
mizar os parâmetros da HNN. Neste capítulo são apresentados a abordagem Particle
Swarm Optimization (PSO) e os conceitos de otimização multi-objetivo. Também
neste capítulo, são apresentado os resultados da aplicação desta abordagem em al-
gumas das principais funções de teste.
O capítulo 5 descreve o algoritmo de roteamento baseado em HNN aplicado às re-
des ópticas. É apresentado sua formulação, forma de execução, arranjo experimental
dos termos inseridos para validação e resultados da influência dos termos.
O capítulo 6 é dedicado à apresentação dos resultados dos experimentos reali-
zados com a otimização dos termos da HNN, incluindo os novos termos, utilizando
o MOPSO-CDR. São apresentados resultados da evolução da convergência da exe-
cução do MOPSO-CDR. Também neste capítulo é feita uma comparação entre o
algoritmo proposto com uma configuração de parâmetros otimizada e algoritmos
conhecidos pela literatura em redes de comunicação.
O capítulo 7 é dedicado a finalização da dissertação com conclusões e propostas
para trabalhos futuros.
Capítulo 2
Redes Ópticas
De forma geral as fibras ópticas são as principais responsáveis pela enorme largura
de banda disponível hoje em dia. Atualmente, os sistemas de comunicação ópticos
estão tendendo a evoluir para sistemas mais flexíveis e dinâmicos. O caminho natural
para isto é que estes sistemas sejam dotados de funcionalidades de redes, como a
capacidade de roteamento. Devido a isto, torna-se necessário o desenvolvimento de
algoritmos de roteamento eficientes para otimizar a utilização de recursos da rede
óptica.
Neste capítulo, são abordados brevemente conceitos básicos de redes ópticas, seus
componentes, os efeitos causados na camada física, algumas formas de mensurar
qualidade de transmissão e de rede, classificação quanto à transparência, alguns
exemplos de algoritmos de roteamento e atribuição de comprimentos de onda e o
modelo da camada física utilizado nas simulações.
Na seção 2.1 são apresentados os principais componentes de uma rede óptica.
Na seção 2.2 são descritas as principais formas de degradação do sinal causados
por efeitos da camada física como atenuação, dispersão, ruído e interferência. Na
seção 2.3 são definidos alguns critérios que podem ser utilizados para mensurar a
qualidade do sinal óptico, entre os quais pode-se citar: relação sinal ruído, fator e
figura de ruído, taxa de erro de bit, interferência intersimbólica, diagrama do olho e
probabilidade de bloqueio. Em seguida, na seção 2.4 são abordadas as técnicas de
multiplexação, aspectos sobre a evolução das redes ópticas e os conceitos de redes
transparentes, opacas e translúcidas. Também é abordada nesta seção a restrição
da continuidade obrigatória de comprimento de onda. Finalmente, na última seção
é definido o problema de roteamento e atribuição de comprimentos de onda (RWA
- Routing and Wavelength Assignment), as formas de roteamento, exemplos de al-
goritmos de roteamento e exemplos de algoritmos de alocação de comprimentos de
onda para redes ópticas.
2.1 Dispositivos da camada óptica
Esta seção visa apresentar uma breve introdução a alguns dos componentes básicos
de uma rede óptica. Será apresentada uma visão geral dos transmissores ópticos,
fibras ópticas, amplificadores ópticos e comutadores/switchs ópticos.
6
2.1.1 Transimissores ópticos
Os transmissores ópticos utilizados em comunicações ópticas são os diodos emissores
de luz (LED - Light Emitting Diode) e os LASERS (LASER - Light Amplification
by Stimulated Emission of Radiation) [77].
Os LEDs são mais baratos e, portanto, eles são usados principalmente em redes
locais e de menor número de usuários. A principal desvantagem dos LEDs é que sua
luz tem uma ampla largura espectral, que provoca uma dispersão elevada no feixe
de luz que se propaga na fibra. Devido a este fato, os LEDs não devem ser usados
para longa distância ou para altas taxas de transmissão. LASERs, por outro lado,
têm uma largura espectral muito mais estreita, sendo eles geralmente preferidos para
altas taxas de transmissão ou enlaces de longo alcance.
Um LASER é essencialmente um emissor de radiação coerente e consiste ba-
sicamente em um meio opticamente ativo, que pode ser sólido, liquido ou gasoso,
excitado convenientemente e confinado em uma cavidade ressonante. A radiação
coerente é obtida mediante a amplificação de luz devido ao processo de emissão
estimulada de radiação (SE - Stimulated Emission) [86].
2.1.2 Fibras ópticas
Uma fibra óptica é um guia de onda cilíndrico capaz de conduzir luz. É fabricado
a partir de sílica (SiO
2
) ou materiais poliméricos transparentes. Uma fibra consiste
de um núcleo dielétrico cilíndrico de índice de refração n
1
, envolvido por uma casca
concêntrica, também de material dielétrico, com índice de refração n
2
ligeiramente
menor que n
1
. A secção de corte transversal de em exemplo de fibra óptica está
exibido na figura 2.1. Tanto o núcleo quanto a casca são feitos basicamente de
sílica, que tem um índice de refração de aproximadamente 1, 45.
Figura 2.1: Ilustração da secção de corte transversal de um exemplo de fibra óptica.
A diferença entre o índice de refração da casca e do núcleo faz com que a luz ao
ser inserida na fibra seja guiada por reflexões sucessivas até o receptor.
As fibras têm como característica a largura de banda disponível, que é muito
maior que os dos meios de comunicação tradicionais baseados em fios de cobre ou
rádio frequência.
7
Por outro lado, as fibras ópticas apresentam propriedades que degradam a qua-
lidade do sinal (informação) transmitido. A primeira é a atenuação que é medida
pela perda de potência do sinal durante a transmissão. A subseção 2.2.1 abordará
o efeito de atenuação com mais detalhes.
Outra característica degradante das fibras ópticas é a dispersão [4]. Em geral,
a dispersão refere-se ao alargamento dos pulsos que viajam ao longo da fibra. A
subseção 2.2.1 abordará o fenômeno da dispersão em fibras ópticas.
Outros efeitos que ocorrem nas fibras e que degradam o sinal são: espalhamento
Raman (SRS - Stimulated Raman Scattering) [77], dispersão por modo de polariza-
ção (PMD - Polarization Mode Dispersion) [68], mistura de quatro ondas (FWM -
Four Wave Mixing) [77], auto modulação de fase (SPM - Self Phase Modulation)
[77] e modulação de fase cruzada (XPM - Cross-Phase Modulation) [77].
2.1.3 Amplificadores ópticos
A luz propagada em uma fibra óptica sempre sofre atenuação, limitando o compri-
mento máximo do enlace. A princípio, existem duas formas de compensar a ate-
nuação do sinal. Uma das formas é detectar o sinal óptico antes que a degradação
interfira na capacidade de recepção e convertê-lo para o domínio elétrico, tratá-lo,
e em seguida reconverte-lo para o domínio óptico. A vantagem dessa abordagem
é que uma vez que o sinal é convertido para o domínio elétrico, diversos processa-
mentos de alto nível podem ser realizados no sinal. Uma desvantagem é que esta
conversão limita a taxa de transmissão devido ao uso de equipamentos eletrônicos.
Outra forma de resolver o problema da atenuação é utilizar um amplificador óptico.
Um amplificador óptico pode amplificar o sinal no domínio óptico sem a necessidade
de convertê-lo para o domínio elétrico. Os amplificadores ópticos podem ser usados
como amplificadores de linha com o intuito de compensar a atenuação dos sinais
ópticos, podem ser usados como pré-amplificadores de receptores ópticos para me-
lhorar a sensibilidade do receptor ou podem ser usados como um booster de potência
para aumentar a potência de saída do transmisor óptico.
Os amplificadores ópticos têm como desvantagem o fato de degradarem o sinal
de diversas formas, a principal é adição de ruído ASE (ver subseção 2.2.3) [77],
[41], [50], [12]. Os amplificadores mais comumente utilizados são os de fibra dopada
com Érbio (EDFA - Erbium Dopped Fiber amplifier) [4], [77] e os amplificadores
ópticos Raman (RFA - Raman Fiber Amplifiers) [68]. O período de maior desen-
volvimento destes amplificadores ocorreu entre o final dos anos 80 e início dos anos
90. O EDFA consiste basicamente de uma fibra óptica com comprimento de dezenas
de metros, dopado com o elemento Érbio. Os átomos de Érbio na fibra são bom-
beados do seu estado fundamental para um estado excitado utilizando uma fonte
de bombeamento. Um fóton do sinal óptico é absorvido por um átomo de Érbio
fazendo com que o átomo volte ao seu estado fundamental. Neste processo, cada
átomo emite um fóton. Assim, os fótons do sinal de entrada provocam a emissão
de fótons adicionais, resultando em uma amplificação do sinal. Os amplificadores
Raman são utilizados pricipalmente para sistemas ópticos de longa distância e sis-
temas de ultra longa distância. Estes amplificadores foram desenvolvidos no início
da década de 80, porém seu uso ficou restrito à laboratórios de pesquisa, devido
à grande aplicação dos amplificadores EDFA. Em meados dos anos 90, ressurgiu o
interesse pelos amplificadores RFA, devido ao desenvolvimento de bombas de alta
8
potência adequadas.
2.1.4 Comutadores/switchs
Devido à grande capacidade de transferência de dados das redes ópticas, as falhas
de transferência que ocorrem causam enormes perdas de dados para um grande
número de usuários. Portanto, as redes ópticas devem prover, dentre outros aspectos,
transferência confiável de dados. Os comutadores ópticos (OXC - Optical Cross-
connect) são componentes chave porque tornam as redes ópticas reconfiguráveis,
fazendo com que lightpaths possam ser criados e/ou eliminados quando necessário,
eliminando a necessidade de uma configuração estática. Lightpaths são conexões
ópticas realizadas a partir de um nó origem até um nó destino (fim-a-fim) sobre um
determinado comprimento de onda. A figura 2.2 mostra um exemplo de OXC.
Figura 2.2: Ilustração de um OXC.
Um OXC provê alguns serviços às rede ópticas, da qual pode-se citar:
• Gerenciamento - Um OXC pode ser utilizado para gerenciar lightpaths em
uma grande rede de forma automática, sem ter que recorrer à conexões manuais
nos paineis de controle.
• Proteção - Proteção de lightpaths contra quebras nas fibras e falhas de equi-
pamentos da rede é uma outra importante função dos OXCs. Um OXC é capaz
de detectar falhas na rede e realocar lightpaths que sofreram alguma falha.
• Transparência de dados - A habilidade de rotear sinais com taxas de trans-
ferências e formatos de quadros arbitrários é um atributo desejável de um
OXC.
• Monitoramento - Um OXC provê a capacidade de mensurar o desempenho
de parâmetros do sinal em nós intermediários. Eles permitem que um equi-
pamento de teste possa ser conectado à uma porta de teste onde o sinal que
passa pelo OXC possa ser monitorado de um forma não-intrusiva.
• Conversão do comprimento de onda - Assim como os OXCs podem rotear
sinais ópticos entre as portas, eles podem conter a funcionalidade de converter
comprimento de ondas (porém esta funcionalidade aumenta a complexidade
da arquitetura e o custo do equipamento).
9
2.2 Principais formas de degradação do sinal na ca-
mada física
Em redes ópticas transparentes (ver seção 2.4) não existe regeneração do sinal óptico
nos nós intermediários. Isto faz com que a qualidade do sinal se degrade à medida
que o sinal trafega pela rede.
Nesta seção é feita uma descrição de algumas das penalidades físicas existentes
nas redes ópticas.
2.2.1 Atenuação
A atenuação na fibra óptica é um efeito que leva a uma redução da potência do sinal
ao longo da transmissão, reduzindo a amplitude do mesmo [68]. Para se determinar
a distância máxima que um sinal pode se propagar para uma dada potência do
transmissor e sensibilidade do receptor, deve-se considerar o efeito da atenuação. A
sensibilidade do receptor é a potência mínima exigida por um receptor para detectar
o sinal. Seja P (L) a potência do pulso óptico a uma distância de L km a partir do
transmissor e α a constante de atenuação da fibra (em dB/km).
P (L) = 10
−αL/10
P (T ), (2.1)
onde P (T ) é a potência do transmissor. Para um enlace de comprimento L km,
P (L) precisa ser maior ou igual a P (R) (sensibilidade do receptor). A partir da
equação (2.1) define-se:
L
max
=
10
α
log
10
P (T )
P (R)
. (2.2)
A figura 2.3 mostra a atenuação típica da silica em função do comprimento de
onda. Atualmente, as fibras ópticas apresentam coeficiente de atenuação inferior a
0, 2 dB/km na janela de 1550 nm.
Figura 2.3: Atenuação da silica em função do comprimento de onda.
2.2.2 Dispersão
Dispersão é a alteração do formato do pulso que viaja através de uma fibra óptica
[68]. Como um pulso se alarga, esta ampliação pode ser suficiente para interferir
10
com pulsos vizinhos (bits) sobre a fibra, levando a uma interferência intersimbólica.
A dispersão, portanto, limita a taxa máxima de transmissão em uma fibra óptica.
Uma forma de dispersão é a dispersão intermodal. Isso é causado quando múltiplos
modos do mesmo sinal propagam em diferentes velocidades ao longo da fibra. Dis-
persão intermodal não ocorre em fibra monomodo. Outra forma de dispersão é a
dispersão cromática. Esta forma de dispersão decorre do fato de que as cores (ou
comprimentos de ondas) viajam a velocidades diferentes, mesmo dentro do mesmo
modo. Em um meio dispersivo, o índice de refração varia em função do comprimento
de onda. Assim, se o sinal transmitido é constituído por mais de um comprimento
de onda, certos comprimentos de onda irão propagar-se mais rapidamente que ou-
tros. A dispersão cromática total de uma fibra óptica resulta de duas contribuições:
a dispersão do material e a dispersão de guia de onda. A dispersão do material
é intrínseca à sílica, cujo índice de refração varia com o comprimento de onda. A
dispersão de guia de onda é decorrente das características da fibra, como dimensões
do núcleo e perfil de índice de refração ao longo da fibra óptica.
Como nenhum laser pode criar um sinal constituído por um único comprimento
de onda exato, qualquer sinal carregando informação terá uma largura espectral
diferente de zero.
A figura 2.4 ilustra o alargamento de pulsos no caminho percorrido ao longo da
fibra devido a dispersão. É fácil perceber no exemplo que à medida que o sinal
óptico se propaga, os pulsos se misturam, até chegar ao ponto onde é impossível
distinguir qual informação foi enviada.
Figura 2.4: Dispersão de pulsos em função da distância percorrida dentro da fibra.
2.2.3 Ruído
O ruído é um sinal cujo valor instantâneo é imprevisível [92]. O ruído sempre acom-
panha os sinais físicos, e quando um sinal é detectado ou amplificado, o ruído que
11
acompanha também é amplificado. Além disso, qualquer dispositivo eletrônico adi-
ciona algum ruído ao sinal. Alguns dos mais importantes para as comunicações
ópticas são o ruído de emissão espontânea que ocorre em LASERs (SSE - Source
Spontaneous Emission) [44]; o ruído de emissão espontânea amplificada (ASE - Am-
plified Spontaneous Emission) [77] que ocorre em amplificadores ópticos; o ruído
balístico, também conhecido como o ruído quântico, que ocorre nos receptores ópti-
cos, e origina-se da natureza estatística da conversão de um fóton para um elétron
e o ruído térmico que é uma propriedade intrísseca de qualquer circuito elétrico que
é conectado a um receptor óptico [4].
2.2.4 Interferência
Interferência é a adição de sinais indesejados de outros sistemas que alteram, mo-
dificam ou interrompem um sinal útil que viaja ao longo de um canal entre uma
fonte e um destino. Além disso, o sinal útil pode sofrer a influência indesejada do
próprio sinal ou de um sinal que está no mesmo sistema do sinal de interesse. Em
sistemas ópticos, existe diversos tipos de interferência, onde cada uma se manifesta
de forma única. Algumas das mais importantes são: o crosstalk que é causado pela
interferência de sinais que estão na mesma fibra e em canais diferentes (crosstalk
interbanda), ou por sinais no mesmo canal (crosstalk intrabanda) [68], que ocorre
nos comutadores e multiplexadores; a modulação de fase cruzada (XPM - Cross
Phase Modulation) que é a mudança de fase de um sinal causado pela mudança na
intensidade de um sinal propagado em comprimento de onda diferente, ocorre nas
fibras; a auto modulação de fase (SPM - Self Phase Modulation) é causada pela
variação na potência do sinal óptico e resulta na variação da fase do sinal, ocorre
nas fibras ópticas; a mistura de quatro ondas (FWM - Four Wave Mixing) ocorre
quando três pulsos em três diferentes frequências viajam lado a lado por uma longa
distância na mesma fibra. Se as frequências ópticas destes pulsos são f
i
, f
j
e f
k
,
elas tendem a se misturar e gerar ondas em uma nova frequência, (f
fwm
), dada pela
equação (2.3). A interferência FWM ocorre nas fibras:
f
fwm
= f
i
+ f
j
− f
k
. (2.3)
onde i, j e k são comprimentos de onda de um enlace da fibra óptica.
2.3 Medições quantitativas de qualidade do sinal e
de qualidade de rede
Existem alguns critérios que podem ser utilizados para avaliar a qualidade do sinal
de um lightpath ou o desempenho de rede. Os mais importantes serão definidos a
seguir.
2.3.1 Relação sinal ruído
Um vez que o nível de ruído na entrada de um receptor óptico é considerável, é
possível analisar a relação sinal ruído óptica (OSNR - Optical Signal to Noise Ratio).
É importante monitorar este ruído, principalmente se o objetivo for qualificar o sinal
monitorado. Quanto maior a OSNR melhor a qualidade do sinal. A degradação da
12
OSNR em redes ópticas transparentes é devida principalmente ao acúmulo de ruído
de emissão espontânea amplificada (ASE - Amplified Spontaneous Emission) [112],
crosstalk e efeitos não-lineares. Para calcular a OSNR, os dois parâmetros que são
medidos (normalmente nos receptores) são a potência média do sinal óptico recebido
(P
sinal
) e a potência do ruído óptico recebido (P
ruido
). A OSNR pode ser calculada,
em unidades de dB [77], como mostra a equação (2.4).
OSNR = 10log
P
sinal
P
ruido
. (2.4)
2.3.2 Fator de ruído e Figura de ruído
O fator de ruído (F - Noise Factor) e a figura de ruído (NF - Noise Figure) são
parâmetros usados para medir o ruído inserido pelos amplificadores e componentes
ópticos [77]. O fator de ruído é usado para quantificar a degradação da relação sinal-
ruído devido ao ruído inserido pelos amplificadores e pelos diversos componentes
ópticos dispostos ao longo do caminho óptico. Em termos quantitativos, se OSNR
in
é a relação sinal ruído na entrada do dispositivo e OSNR
out
é a relação sinal ruído
na saída do dispositivo, ambas em escala linear, o fator de ruído é definido como
sendo a razão entre a OSNR
in
e a OSNR
out
[77]:
F =
OSNR
in
OSNR
out
. (2.5)
A figura de ruído é o fator de ruído expresso em unidades de decibéis (dB) [77]:
NF = 10logF. (2.6)
2.3.3 Taxa de erro de bit
A taxa de erro de bit (BER - Bit Error Rate) quantifica o desempenho do sistema
de comunicação (transmissão e recepção). Geralmente é utilizado como uma medida
de qualidade de serviço (QoS - Quality of Service). Nos sistemas de comunicações
digitais, as informações são codificadas em um conjunto de símbolos, e estes são
transmitidos através do canal de comunicação.
Os receptores têm o importante papel de amostrar os pulsos ópticos na chegada e
decidir qual é o sinal recebido. Por exemplo, em sistemas que utilizam a transmissão
do tipo IM/DD (Intensity Modulation/Direct Detection) o sinal recebido representa
um 0 ou um 1. A tomada de decisão se dá basicamente definindo um nível limite
para o sinal recebido. Sempre que o sinal recebido estiver acima desse nível, o bit
será considerado como bit 1; e quando estiver abaixo do nível, será considerado como
sendo o bit 0.
Se o sinal recebido não tiver potência suficiente no momento da detecção, devido
às perdas (devido à atenuação), ou a quantidade de ruído inserido no sinal for muito
grande, poderá ocorrer erros na tomada de decisão. Por exemplo, para o caso em
que o transmissor envie o bit 0, o receptor ao invés de detectar o bit 0 irá detectar
o bit 1 e vice-versa.
Uma BER de 2 × 10
−6
significa 2 bits errados em um milhão (10
6
) de bits
transmitidos. Em sistemas ópticos, a exigência é que se tenha BER mínima de 10
−9
ou 10
−12
, dependendo do tipo de aplicação.
13
2.3.4 Interferência intersimbólica
Um valor ou o símbolo em um canal pode corromper um outro símbolo que viaja no
mesmo canal em um momento posterior. Este efeito é conhecido como interferência
intersimbólica (ISI - Intersymbol Interference) [28]. A ISI é um limitante para os
sistemas de comunicações de dados, porque limita o alcance e a capacidade da rede.
A ISI pode ter diversas fontes, incluindo não-linearidade do laser, receptores com
respostas em frequência não-ideais, dispersão cromática e dispersão do modo de
polarização (PMD - Polarization Mode Dispersion) [68].
2.3.5 Diagrama de olho
A forma mais comum de avaliar a qualidade de transmissão dos sinais digitais é
através do diagrama de olho [4]. No entanto, no caso de um sinal óptico, existe
um maior interesse devido a certas características que não são necessariamente tão
importante em outros sistemas. Em um diagrama de olho, alguns ciclos do sinal
são sobrepostos, destacando algumas características que de outra forma não seriam
facilmente visíveis. Os principais parâmetros de um sinal que caracterizam um
diagrama de olho são ilustrados na figura 2.5.
Figura 2.5: Principais parâmetros em um diagrama do olho óptico.
2.3.6 Probabilidade de bloqueio
A probabilidade de bloqueio da rede é uma medida estatística relativa às requisições
de chamadas que não puderam ser estabelecidas devido a falta de recursos da rede.
Isso significa que quanto maior a probabilidade de bloqueio da rede menos usuários
são atendidos e, conseqüentemente, pior é o desempenho da mesma. A probabilidade
de bloqueio P B pode ser estimada por:
P B =
C
bloqueadas
C
total
, (2.7)
onde C
bloqueadas
é o número de chamadas bloqueadas pela rede e C
total
é o número
total de chamadas solicitadas à rede.
14
2.4 Sistemas Ópticos
Atualmente as rede ópticas são consideradas as mais promissoras para prover a
largura de banda necessária nesta nova era das telecomunicações. A fibra óptica
tem como algumas características: grande banda passante (algo em torno de 50 T b/s
[67]), baixa atenuação do sinal (≈ 0, 2 dB/Km), baixa dispersão, baixo custo de
implantação e baixa latência. Em comparação com os cabos de cobre, a fibra óptica
oferece largura de banda muito maior do que os cabos de cobre e é menos suscetíveis
a vários tipos de interferências eletromagnéticas e outros efeitos indesejáveis. Como
as fibras oferecem largura de banda em uma ordem de grandeza maior que os fluxos
de dados atuais, é interessante multiplexar diversos fluxos em uma única fibra com
o objetivo de maximizar o uso da mesma.
2.4.1 Técnicas de multiplexação
Multiplexação é o processo que permite a transmissão de dois ou mais canais de
informação simultaneamente no mesmo meio físico. Nas fibras ópticas pode-se uti-
lizar a multiplexação por divisão no tempo (TDM – Time Division Multiplexing) e
multipexação por divisão em comprimento de onda (WDM – Wavelength Division
Multiplexing).
• Multiplexação por divisão no tempo (TDM – Time Division Multi-
plexing) - Através do método TDM a multiplexação dos sinais (voz, dados,
imagem) ocorre no domínio do tempo. A multiplexação se faz com o envio
sincronizado de partes dos dados. O tempo é dividido em pequenos intervalos
nos quais cada fonte transmite uma quantidade pré-determinada de seus dados
por vez. A intercalação dos dados é realizado pelo multiplexador. O demul-
tiplexador tem a função de separar (de forma sincronizada) os dados. O uso
dessa técnica em redes ópticas encontra uma limitação que é o custo elevado
das partes eletrônicas e eletro-óptica (transmissores, receptores, regeneradores)
para operação com taxas de transmissão acima de 10 Gb/s [77].
• Multipexação por divisão em comprimento de onda (WDM – Wa-
velength Division Multiplexing ) - WDM é uma técnica que permite que
múltiplos sinais ópticos, de diferentes comprimentos de onda, sejam multiple-
xados em uma única fibra e, portanto, possam ser transmitidos em paralelo
nesta fibra. Seu princípio é essencialmente o mesmo da multiplexação por
divisão em frequência (FDM). Isto é, vários sinais são transmitidos usando
diferentes portadoras, ocupando partes que não se sobrepõem no espectro de
frequências. A WDM multiplexa “cores” (comprimentos de onda) de luz em
uma única fibra óptica, utilizando várias fontes de vários comprimentos de
onda. Com a abordagem WDM é possível que um sinal passe pela rede sem
que haja a conversão O-E-O (óptico-elétrico-óptico), assim eliminando o gar-
galo na velocidade de trasmissão imposto pelos circuitos eletrônicos.
2.4.2 Geração das redes ópticas
As redes ópticas podem ser divididas em três gerações: na primeira geração, a fibra
óptica foi utilizada essencialmente para substituir os cabos de cobre; na segunda
15
geração algumas funções de roteamento passaram a ser executadas pela camada
óptica; na terceira geração, a comutação é feita por pacotes.
• Redes ópticas de primeira geração - Devido as vantagens das fibras ópticas
em relação ao cabos de cobre, os sistemas de comunicações começaram a uti-
lizar fibras ópticas como meio de transmissão em substituição ao cabos. Essa
revolução das fibras ópticas fez uso de diversos padrões de transmissão, como é
o caso do SONET (Synchronous Optical Network) nos Estados Unidos e SDH
(Synchronous Digital Hierarchy) na Europa. Nestas redes, apenas os enlaces
de transmissão passaram a pertencer ao domínio óptico. Todas as tarefas de
comutação, processamento e roteamento continuaram a ser desempenhadas no
domínio eletrônico.
• Redes ópticas de segunda geração - Neste caso, redes ópticas são capazes
de fornecer mais funções do que apenas substituir cabos de cobre em enlaces.
As redes de segunda geração incorporaram algumas das funções de comutação
e roteamento que eram efetuadas pelos equipamentos eletrônicos. Quando os
dados são roteados no domínio óptico, o gargalo de tempo do processamento
eletrônico é eliminado.
Nos nós intermediários da rede, os lightpaths são roteados entre um enlace e
outro (com ou sem conversão de comprimento de onda). Diferentes lightpaths
podem utilizar o mesmo comprimento de onda em uma mesma rede, desde
que não tenham enlaces em comum. Assim como diferentes lightpaths podem
utilizar um mesmo enlace, desde que utilizem comprimentos de onda diferentes.
Os principais equipamentos necessários para viabilizar o funcionamento das
redes ópticas foram os OADM’s (OADM - Optical Add/drop Multiplexers)
[77] e os OXCs. As principais topologias utilizadas por estas redes são anel e
mesh. Os principais aspectos referentes ao desenvolvimento das redes de se-
gunda geração e que são alvo de pesquisa são: o desenvolvimento de OADM’s
e OXCs, conversão de comprimento de onda, roteamento e atribuição de com-
primento de onda (RWA - Routing and Wavelength Assignment) (ver seção
2.5), interoperabilidade entre redes WDM, gerenciamento e controle da rede,
etc.
• Redes ópticas de terceira geração - Espera-se que as redes WDM de
terceira geração possam suportar conexões orientadas à datagramas. Dentre os
principais aspectos referentes ao desenvolvimento das redes de terceira geração
e que são alvo de pesquisa pode-se citar o desenvolvimento das redes ópticas de
acesso (como as Passive Optical Network (PON)) e tecnologias de roteamento
e comutação de pacotes.
2.4.3 Classificação das Redes Ópticas segundo transparência
As redes ópticas podem ser classificadas em três categorias segundo critério de trans-
parência.
• Redes Opacas - Em uma rede óptica opaca cada enlace óptico é isolado
dos nós (eletrônicos ou ópticos) através de transponders. Para o caso de nós
eletrônicos, existe uma conversão O-E-O (óptico-eletrônico-óptico) do sinal.
16
Algumas das vantagens das redes ópticas são: não acumulação da degradação
do sinal óptico, interoperabilidade entre redes, conversão de comprimentos de
onda, enlaces ponto-a-ponto de longa distância, etc [15]. Como desvantagens
pode-se citar: limitação nos formatos de dados, limitação na taxa de trans-
missão, custo elevado relacionado aos equipamentos dos nós [15].
• Redes Transparentes - As redes ópticas transparentes transportam os sinais
ópticos da origem até o destino no domínio óptico, ou seja, sem conversão O-E-
O. Desta forma, os núcleos de uma rede transparente de segunda geração não
obtém acesso aos dados transportados pelos sinais ópticos. As redes transpa-
rentes têm como vantagens em relação às redes opacas: economia de energia,
menor custo, maior taxa de transmissão, independência do formato dos da-
dos, etc [15]. Suas desvantagens são: custo alto para incluir a capacidade de
conversão de comprimento de onda, uso mais ineficiente dos comprimentos de
onda (para redes sem conversão), acúmulo da degradação do sinal, interope-
rabilidade entre redes, etc [15].
• Redes Translúcidas - Estas redes são uma composição das redes opacas e
transparentes. Os nós são compostos de uma parte transparente e uma opaca.
Um sinal que entra em algum nó pode passar pela parte transparente ou pela
parte opaca. Sinais degradados são candidatos a passar pela parte opaca e
serem regenerados. Redes translúcidas permitem que conexões permaneçam
transparentes enquanto a qualidade do sinal for aceitável, após um limiar de
aceitabilidade o sinal é regenerado. Estas redes têm algumas das vantagens das
redes transparentes enquanto elimina algumas das desvantagens das mesmas
(como permitir conversão de comprimento de onda e regeneração do sinal).
Regeneração esparsa pode ser utilizada para que nem todos os nós da rede
tenham a capacidade de regeneração. Problemas como roteamento em redes
translúcidas [104] e escolha de nós translúcidos [90] tem sido alvo de pesquisas
pela comunidade científica.
2.4.4 Restrição da continuidade obrigatória de comprimento
de onda
Em redes ópticas de segunda geração sem conversão de comprimento de onda, para
uma chamada ser estabelecida com sucesso, um lightpath entre a origem e o destino
precisa alocar um determinado comprimento de onda em todos os enlaces do cami-
nho. Esta restrição é referenciada como continuidade obrigatória de comprimento
de onda. Pode-se citar como desvantagens desta restrição, uma maior probabilidade
de bloqueio em comparação com redes que não têm esta restrição e algoritmos de
roteamento e atribuição de comprimentos de onda mais complexos. A vantagem está
no custo menor da rede (conversores são caros) e projeto de rede mais simples, pois
a escolha de nós e comprimentos de onda que podem ser convertidos são parâmetros
a mais no projeto.
17
2.5 Roteamento e Alocação de Comprimento de Onda
(RWA - Routing and Wavelength Assignment)
Dada uma topologia de rede e um conjunto de solicitações para formação de light-
paths, o problema de determinar uma rota e um comprimento de onda para as soli-
citações usando o número mínimo possível de comprimentos de onda é referenciado
como o problema de roteamento e atribuição de comprimentos de onda (RWA - Rou-
ting and Wavelength Assignment) [76]. Normalmente, as requisições de chamadas
podem ser de três tipos: estática, incremental e dinâmica [40].
Com o tráfego estático, todo o conjunto de conexões é conhecido previamente, e o
problema está em configurar os lightpaths para estas conexões de forma que minimize
a utilização dos recursos da rede, tais como o número de comprimentos de onda ou
o número de fibras ópticas da rede. O problema de RWA para tráfego estático
é conhecido como Estabelecimento de lightpath estático (SLE - Static Lightpath
Estabilishment).
Para o caso do tráfego incremental, as requisições de chamadas chegam sequen-
cialmente, um lightpath é estabelecido para cada chamada, e o lighpath permanece
ativo na rede indefinidamente.
Para o uso de tráfego dinâmico, um lightpath é estabelecido para cada requisi-
ção de chamadas quando ela chega, e o lightpath é liberado após um certo tempo.
O objetivo no caso dos tráfegos incremental e dinâmico é estabelecer lighpaths e
alocar comprimentos de onda de maneira que minimize o número de chamadas blo-
queadas, ou que maximize o número de conexões que são estabelecidas na rede a
qualquer momento. Este problema é conhecido como Estabelecimento de lightpath
dinâmico (DLE - Dynamic Lightpath Estabilishment). As simulações apresentadas
neste trabalho são para redes com tráfego dinâmico.
Devido à complexidade do problema de RWA, este pode ser particionado em
dois subproblemas: roteamento e atribuição de comprimentos de onda, onde cada
sub-problema pode ser solucionado independentemente de forma eficiente utilizando
técnicas adequadas.
2.5.1 Tipos de roteamento
Em relação aos algoritmos de roteamento, existem três maneiras básicas de classificá-
los em relação ao tipo: roteamento fixo, roteamento fixo-alternativo e roteamento
adaptativo.
• Roteamento fixo - A abordagem mais simples para o roteamento de uma cha-
mada é sempre escolher o mesmo caminho para um determinado par origem-
destino (ou seja, não leva em conta o estado da rede). Esta abordagem de
roteamento é muito simples, porém como desvantagem tem-se que, se os re-
cursos (comprimentos de onda) ao longo do caminho já estiverem alocados,
a tendência é que não haja flexibilidade para atender uma dada requisição e
com isso aumente a probabilidade que esta chamada seja bloqueada; outra
desvantagem é que pode ocorrer uma alocação dos comprimentos de onda de-
sordenada; também como desvantagem tem-se que o roteamento fixo pode ser
incapaz de lidar com situações de falhas (queda de enlaces).
18
• Roteamento fixo-alternativo - Uma abordagem de roteamento que con-
sidera múltiplas rotas é o roteamento fixo-alternativo. No roteamento fixo-
alternativo, para cada nó na rede é necessário manter uma tabela de rotea-
mento que contém uma lista ordenada de um número de rotas fixas para cada
nó destino. Por exemplo, estas listas podem incluir a rota com o caminho mais
curto, a segunda rota de menor caminho, a terceira, etc.
Quando uma requisição de conexão chega, o nó de origem tenta estabelecer a
conexão utilizando uma das rotas que estão na tabela de rotas (em sequência),
até que uma rota com um comprimento de onda livre em todos os enlaces seja
encontrado. Caso nenhuma das rotas encontradas esteja disponível na lista
de rotas alternativas, então a requisição da conexão é bloqueada e perdida.
Na maioria dos casos, a tabela de roteamento de cada nó está ordenada pelo
número de saltos até o destino. O roteamento fixo-alternativo provê simplici-
dade de controle para para a criação e encerramento de chamadas, fornecendo
um certo grau de tolerância a falhas. Esta abordagem de roteamento pode
reduzir significativamente a probabilidade de bloqueio da conexão em relação
ao roteamento fixo.
• Roteamento adaptativo - No roteamento adaptativo, a rota de um nó ori-
gem para um nó de destino é escolhido dinamicamente, dependendo do estado
da rede. O estado de rede é determinado pelo conjunto de todas as conexões
estabelecidas. Uma vantagem do roteamento adaptativo sobre as outras abor-
dagens é uma menor probabilidade de bloqueio. A desvantagem é que torna
necessário um maior controle da rede e protocolos de gerenciamento que devem
manter as tabelas de rotas atualizadas. O algoritmo proposto neste trabalho
utiliza a abordagem de roteamento adaptativo.
2.5.2 Algoritmos de roteamento
• Algoritmo de Dijkstra [31] - O algoritmo de Dijkstra, cujo nome se ori-
gina de seu inventor, o cientista da computação Edsger Dijkstra, soluciona o
problema do menor caminho, ou seja, é capaz de encontrar rotas em redes
ópticas. Diversas abordagens de roteamento utilizam como “engine” o algo-
ritmo de Dijkstra. O que diferencia as abordagens são as métricas de custo
dos enlaces. Pode-se citar como métricas simples:
– Menor Caminho (SP - Shortest Path) - Esta é a métrica clássica, as
informações que são passadas para o algoritmo são as distâncias geográfi-
cas dos enlaces. O caminho encontrado pelo algoritmo é o que percorre a
menor distância. A vantagem desta métrica é que os valores são estáticos,
eliminando o atraso e sobrecarga de troca de informações sobre o estado
da rede. Como desvantagem, tem-se que a resposta encontrada é a de
menor caminho, porém não necessariamente esta é uma boa resposta para
um outro objetivo, como por exemplo, minimização da probabilidade de
bloqueio.
– Menor número de saltos (MH - Minimum Hops) - Esta é a métrica
mais simples. Para cada enlace é atribuído o custo 1. O caminho escolhido
é o que contêm o menor número de enlaces, consequentemente o menor
19
número de saltos. A vantagem em utilizar o número de saltos é que
os lightpaths escolhidos tenderão a passar por um número menor de nós
ópticos, com isto acumularão menos ruído originados por equipamentos
dos nós, consequetemente estes lightpaths terão maior probabilidade de
sucesso na sua aceitação. Porém, esta métrica pode ter resultados ruins.
Não há controle sobre a distância da rota, já que caminhos longos podem
ser escolhidos, degradando assim a qualidade do sinal.
Outra possibilidade é utilizar métricas contendo informações da camada física
da rede e/ou do estado atual da rede (roteamento adaptativo). Dentre as
abordagens que utilizam informações da camada física da rede e/ou do estado
atual da rede como métricas pode-se citar:
– Least Resistance Weight (LRW) [103] - A abordagem proposta por
Wen et al. é uma função de custo de enlaces que incorpora informações
sobre a utilização de comprimentos de onda. A função de peso de enlace
w
ij
é calculada para cada enlace (i, j) da rede. As seguintes notações são
utilizadas no cálculo da função: C
A
ij
indica a quantidade de comprimentos
de ondas livres no enlace (i, j). C
T
representa a quantidade total de
comprimentos de ondas de qualquer enlace da rede. A função de custo é
dada por:
w
ij
=
C
T
C
A
ij
, ∀(i, j). (2.8)
– Optical Signal to Noise Ratio Routing (OSNR-R) [62] - Abor-
dagem proposta por Martins-Filho et al., encontra rotas usando como
métrica penalidades associadas à camada física, incluindo diversos fa-
tores como: acúmulo de ruído e ganho, saturação dos amplificadores e
ganhos e perdas relacionados ao próprio lightpath. Diferentemente de ou-
tras abordagens que utilizam apenas custos dos enlaces, esta proposta
também considera o custo dos nós, fazendo necessário uma pequena al-
teração no algoritmo de Dijkstra. Esta abordagem tem como vantagem
diminuir a probabilidade de bloqueio das chamadas em comparação com
o algoritmo de Dijkstra utilizando a métrica de custo dos enlaces. Como
desvantagem está a necessidade de um maior custo computacional para
calcular a relação sinal ruído total dos lightpaths.
– Physical Impairments Aware Adaptive Weight Function (PI-
AWF) [19] - Abordagem proposta por Chaves et al. onde a função de
custo é composta por comprimento dos enlaces, carga dos enlaces e dois
parâmetros ajustáveis, que são dependentes da degradação da camada
física. A obtenção dos parâmetros é feita utilizando algum algoritmo
inteligente de busca de parâmetros. Os autores mostraram que esta pro-
posta supera as outras que foram utilizadas nas simulações ou, no pior
caso é similar a uma das abordagens utilizadas nas comparações, e tem
um tempo computacional 6 vezes menor que a abordagem que utiliza
informações da camada física. A desvantagem desta abordagem é que é
preciso encontrar os coeficientes da função a partir de um treinamento
prévio ao funcionamento da rede.
20
– Power Series Routing (PSR) [64] - Proposição de Chaves et al. que
utiliza como métrica para o algoritmo de roteamento uma função de custo
que é baseada em uma série de potências. Para compor a função de custo
utiliza informações de carga, distância dos enlaces e número de saltos.
Para escolher os coeficientes da série, utiliza-se a técnica de otimização
por exame de partículas (PSO - Particle Swarm Optimization) [53], [32].
Como vantagem, está o fato de que a probabilidade de bloqueio é menor
ou similar que a probabilidade de bloqueio do algoritmo NF, porém com
resposta 8 vezes mais rápida. Isto porque esta abordagem não utiliza
informações da camada física. A desvantagem desta abordagem é que
é preciso encontrar os coeficientes da série a partir de um treinamento
prévio ao funcionamento da rede.
• Otimização por colônia de formigas (ACO - Ant Colony Optimi-
zation) - Alguns algoritmos baseados em ACO têm sido propostos para o
problema de RWA em redes WDM. Navarro-Varela et al., [69] aplicaram ACO
para tráfego estático como o intuito de minimizar o número total de com-
primentos de onda utilizados. Porém esta abordagem não pode ser aplicada
diretamente para tráfego dinâmico. Garlick e Barr [38] propuseram um al-
goritmo para RWA dinâmico utilizando ACO. Nesta abordagem, para cada
chamada um conjunto de formigas irão encontrar rotas. Na abordagem de
Ngo et al., [70] ao contrário da abordagem de Garlick e Barr, as formigas
estão continuamente atualizando as tabelas de rotas dos nós, com o intuito
de encontrar rotas para novas requisições de forma eficaz. A abordagem de
Bastos-Filho et al., [9] utiliza informações das distâncias físicas dos enlaces
e carga dos enlaces. As métricas são ponderadas por pesos que são achados
utilizando PSO. É necessário uma etapa de treinamento para que o algoritmo
adapte-se às condições da rede.
• Algoritmos Genéticos (GA - Genetic Algorithm) - Banerjee et al., [5]
formularam uma abordagem multi-objetivo utilizando algoritmos genéticos
aplicada ao problema de roteamento em redes ópticas com tráfego estático.
Para tráfego dinâmico, Le et al., [61] propuseram uma abordagem que adota
uma nova função de fitness que considera os custos dos enlaces e o número de
comprimento de onda na estimativa de custo da rota.
• Redes Neurais de Hopfield (HNN - Hopfield Neural Networks) - Kojic
et al., [57], [58] utilizaram redes neurais de Hopfield para o problema de RWA
dinâmico e sem conversão de comprimento de onda, nestes trabalhos a função
de custo é composta apenas por informações de uso dos comprimentos de onda
dos enlaces (roteamento adaptativo). Nestas abordagens, as informações da
camada física não são consideradas.
2.5.3 Algoritmos de atribuição de comprimentos de onda
A atribuição de comprimentos de onda pode ser realizada de várias formas. Para
enlaces com apenas uma fibra pode-se citar os seguintes algoritmos: Atribuição
aleatória, First-fit, Least Used, Most used, etc. Para enlaces com mais de uma fibra
tem-se as seguintes abordagens: Maximal sum, Relative capacity loss, etc [67].
21
• Atribuição aleatória (R - Random) - Neste esquema, a partir da rota
encontrada, é montada uma lista com os comprimentos de onda que estão
disponíveis na rota. Em seguida, um dos comprimentos de onda da lista é es-
colhido aleatoriamente, seguindo uma distribuição uniforme de probabilidade.
• First fit (FF) - Neste método, todos os comprimentos de onda são indexados,
e o primeiro comprimento de onda livre é escolhido. Similarmente ao esquema
de Atribuição aleatória, este método não requer nenhuma informação do estado
da rede, ou seja, é adequado para controle descentralizado. Além disso, o baixo
custo computacional fazem de ambos métodos adequados para implementações
práticas.
• Least used (LU) - Nesta forma de atribuição, escolhe-se o comprimento de
onda que é o menos usado na rede, a partir do conjunto de comprimentos de
onda livres. A idéia deste algoritmo é que é mais provável que uma rota mais
curta seja encontrada no comprimento de onda menos utilizado do que um
comprimento de onda que esteja mais utilizado. Isto pode resultar em uma
rede com mais enlaces livres facilitando a alocação de chamadas posteriores.
• Most used (MU) - Este algoritmo utiliza uma lógica oposta em relação ao
LU. O MU escolhe o comprimento de onda que é o mais usado na rede. Foi
mostrado em [96] que este método supera os método LU de forma significativa.
Ambos os métodos, LU e MU, requerem informações sobre o estado global da
rede, sendo adequado para redes com controle contralizado.
• Optimized First Fit (OpFF) - Proposta de Bastos-Filho et al., [10] em
que o First Fit é modificado para receber uma lista otimizada de canais. A
otimização da lista é feita utilizando um algoritmo evolucionário que utiliza um
arquivo externo (repositório que armazena boas soluções encontradas durante
a execução do algoritmo). Simulações mostraram que esta abordagem é melhor
ou equivalente do que outras abordagens clássicas da literatura. A otimização
da lista é executada apenas na etapa offline. Na etapa online esta abordagem
tem as mesmas características que o FF.
• Best Fit (BF) - Zulkifli et al., [111] propuseram uma modificação do First
Fit, onde os comprimentos de onda são ordenados de acordo com a dispersão
residual do menor para o maior valor. Este algoritmo funciona bem para redes
onde o maior problema é a dispersão.
• Just Enough (JE) - Zulkifli et al., [111] também propuseram uma abordagem
similar ao BF, onde novamente os comprimentos de onda são ordenados em
relação à dispersão residual, porém do maior para o menor valor. Soluções que
tenham valor de dispersão residual maior que um limiar de QoS são eliminadas
da lista (as primeiras). Desta forma, esta abordagem preserva canais com
menores valor de dispersão residual para os casos em que seu uso é realmente
necessário.
22
2.6 Modelo da Camada Física
Este trabalho utiliza o modelo analítico da camada física proposto por Pereira et
al., [73] para executar as simulações. Este modelo leva em consideração o efeito da
mistura de quatro ondas (FWM - Four Wave Mixing) [1] em fibras ópticas, o ruído
ASE emitido pelos amplificadores, o efeito de saturação na saída dos amplificadores
ópticos, a atenuação na fibra óptica, a interferência coerente nos comutadores óp-
ticos, a atenuação nos multiplexadores, assim como o alargamento do pulso óptico,
devido ao efeito de PMD. O efeito de FWM não será considerado neste trabalho
e o alargamento do pulso óptico, devido ao efeito da dispersão residual, que não é
proposto no modelo de Pereira et al., será considerado.
A figura 2.6 mostra os componentes considerados neste trabalho em cada en-
lace. O enlace contêm os seguintes componentes: transmissor, switch, multiplexa-
dor, amplificador óptico de potência (booster), fibra óptica, pré-amplificador óptico,
demultiplexador e receptor.
Figura 2.6: Configuração do enlace contendo os dispositivos considerados na mode-
lagem apresentada.
Na figura 2.6, de a até h têm-se pontos de avaliação nos quais tanto a potência
do sinal quanto a do ruído podem ser determinadas no domínio óptico. No ponto a,
tem-se as potências ópticas de sinal (P
in
) e de ruído (N
in
) na entrada do sistema.
A relação entre P
in
e N
in
define a OSNR (equação 2.4) do transmissor ou OSNR
da entrada do sistema (OSNR
in
). Considerando uma rota composta de i enlaces,
os dispositivos entre b e h são repetidos i − 1 vezes antes do sinal óptico alcançar o
receptor no nó destino.
Nos pontos b e h, considera-se o crosstalk adicionado na saída do switch. Isso
ocorre porque uma pequena quantidade da potência proveniente de outros canais no
mesmo comprimento de onda do canal de interesse é adicionada pelo switch devido
ao isolamento não-ideal do dispositivo.
A potência de ruído produzida por esse efeito, em cada comprimento de onda λ,
é dada por [77]:
N
Sw
(λ) = ε
M+1
j=1
P
Sw
j
(λ), (2.9)
onde P
Sw
j
(λ) é a potência óptica do sinal presente na j-ésima porta de entrada no
comprimento de onda λ, ε representa o fator de isolação entre as portas do switch e
M + 1 o número total de sinais presentes nas portas de entrada do switch no mesmo
comprimento de onda do sinal propagante.
Nos pontos c e g,considera-se que os multiplexadores e demultiplexadores apenas
atenuam os sinais propagantes no domínio óptico.
Nos pontos d e f, tanto se considera o ruído adicionado pelos amplificadores
ópticos, como o efeito de saturação do ganho. O batimento entre o sinal óptico e
23
o ruído ASE representa a principal fonte de ruído, de forma que o ruído pode ser
quantificado como [6]:
N
Amp
(λ) = P
ASE
=
hν(λ)B
o
G
Amp
F
Amp
2
, (2.10)
onde h é a constante de Planck, ν(λ) representa a frequência do sinal no comprimento
de onda λ, B
o
a largura de banda do filtro óptico, G
Amp
o ganho dinâmico linear e
F
Amp
o fator de ruído dinâmico do amplificador.
O efeito de saturação do ganho é considerado por meio da seguinte expressão
[62], [63]:
G
Amp
=
G
0
Amp
1 +
P
out
P
sat
, (2.11)
onde G
0
Amp
representa o ganho não-saturado do amplificador, P
out
a potência óptica
e P
sat
a potência de saturação, ambas consideradas na saída do amplificador.
Pode-se perceber por meio da equação (2.11), que o ganho do amplificador de-
pende da potência óptica na entrada do mesmo. Uma vez que F
Amp
também de-
pende da potência de sinal [11], a seguinte expressão, obtida empiricamente, ajusta
o comportamento real de F
Amp
como função da potência óptica de entrada [75]:
F
Amp
= F
0
Amp
1 + A
1
−
A
1
1 +
P
in
A
2
, (2.12)
onde F
0
Amp
representa o fator de ruído do amplificador quando potências baixas
são consideradas, A
1
e A
2
são parâmetros obtidos por meio de ajuste em curvas
experimentais.
A figura 2.7 ilustra o ganho e a figura de ruído do amplificador em função da
potência óptica de entrada por canal (P
λ
in
), considerando-se um EDFA montado
em laboratório. Os resultados experimentais são típicos dos EDFAs e estão re-
presentados por pontos, enquanto que as curvas obtidas utilizando-se as equações
(2.11) e (2.12) estão representados por curvas sólidas na figura 2.7. Os parâme-
tros utilizados, que ajustam as curvas aos resultados experimentais, são os seguin-
tes: G
0
Amp
= 1000 (30 dB), F
0
Amp
= 3 (4, 77 dB), P
sat
= 15 dBm, A
1
= 500 e
A
2
= 2 W .
Nos amplificadores ópticos, tanto o ruído ASE quanto o ganho diminuem com
o aumento da potência de entrada [11]. É interessante perceber que apesar da
potência de ASE adicionada pelo EDFA se tornar menor com o aumento da potência
de entrada, sua figura de ruído aumenta. Isso ocorre porque, com o aumento da
potência de entrada, o ganho do amplificador diminui a uma taxa maior do que a
diminuição da potência de ASE, ou seja, a potência de sinal amplificado diminui
mais rapidamente do que a diminuição da potência de ruído ASE, resultando assim
em um ruído relativamente maior na saída do amplificador e, conseqüentemente,
numa figura de ruído maior.
Finalmente, no ponto h, pode-se calcular as potências ópticas do sinal (P
out
) e
do ruído (N
out
) na saída do enlace. O termo P
out
depende dos ganhos e das perdas
24
Figura 2.7: Ganho e figura de ruído do amplificador em função da potência de
entrada por canal, ambos obtidos de resultados experimentais (pontos) e modelo
empírico (curvas sólidas) [73].
presentes ao longo da propagação do sinal e pode ser calculado da seguinte forma
[74]:
P
out
=
G
Amp
1
e
−αd
G
Amp
2
L
Mx
L
Dx
L
2
Sw
P
in
, (2.13)
onde G
Amp
1
e G
Amp
2
representam os ganhos dinâmicos lineares do booster e do pré-
amplificador. L
Sw
, L
Mx
e L
Dx
representam as perdas do switch (ambos os switches
do enlace são considerados com as mesmas perdas), multiplexador e demultiplexador,
respectivamente e α a constante de atenuação da fibra.
O termo N
out
é calculado no nó destino e inclui as potências de ruído adicionadas
em cada ponto, vistos anteriormente, da seguinte forma:
N
out
(λ) =
G
Amp
1
e
−αd
G
Amp
2
L
Mx
L
Dx
L
2
Sw
N
in
+
G
Amp
1
e
−αd
G
Amp
2
L
Mx
L
Dx
L
Sw
ε
M+1
j=1
P
Sw
1,j
(λ)+
+
G
Amp
1
e
−αd
G
Amp
2
L
Dx
L
Sw
hν(λ)B
o
2
F
Amp
1
+
F
Amp
2
e
−αd
G
Amp
1
+
+ ε
M+1
j=1
P
Sw
2,j
(λ).
(2.14)
Dividindo P
out
por N
out
, pode-se obter o valor da OSNR no nó destino (OSNR
out
).
Um limiar da OSNR pode ser estabelecido de modo a garantir a qualidade de trans-
missão (Qot) dos lightpaths estabelecidos na rede (OSNR
QoT
).
Considerando uma rota com i enlaces, tem-se que [73]:
P
out
i
=
G
Amp
i,1
e
−αd
i
G
Amp
i,2
L
Mx
L
Dx
L
Sw
P
out
i−1
(2.15)
25
e
N
out
i
(λ) =
G
Amp
1,i
e
−αd
i
G
Amp
2,i
L
Mx
L
Dx
L
Sw
N
out
i−1
+
+
G
Amp
1,i
e
−αd
i
G
Amp
2,i
L
Dx
L
Sw
hν(λ)B
o
2
F
Amp
1,i
+
F
Amp
2,i
e
−αd
i
G
Amp
1,i
+
+ ε
M+1
j=1
P
Sw
i+1,j
(λ),
(2.16)
onde P
out
0
=
P
in
L
Sw
e N
out
0
=
N
in
L
Sw
+ ε
M+1
j=1
P
Sw
1,j
(λ).
O alargamento do pulso óptico, devido ao efeito da dispersão residual, é consi-
derado por meio da seguinte expressão [9], [111]:
∆t
RD
= ∆λ
T X
i
j=1

D
λ
ref
T F
+ (∆λ
j
S
T F
)
L
T F
j
+
D
λ
ref
DCF
+ (∆λ
j
S
DCF
)
L
DCF
j
,
(2.17)
onde ∆λ
T X
representa a largura de linha do transmissor, D
λ
ref
T F
o coeficiente de
dispersão cromática do comprimento de onda referenciado, S
T F
a inclinação da curva
de dispersão, L
T F
j
o comprimento da fibra óptica no enlace j, D
λ
ref
DCF
o coeficiente
de dispersão cromática da fibra de compensação, S
DCF
a inclinação da curva de
dispersão da fibra de compensação e L
DCF
j
o comprimento da fibra de compensação.
L
DCF
j
é dado por:
L
DCF
j
=
L
T F
j
D
λ
ref
T F
D
λ
ref
DCF
, (2.18)
O alargamento do pulso óptico, devido ao efeito de PMD, é considerado por meio
da seguinte expressão [95]:
∆t
P MD
=
i
j=1
(D
P MD
)
2
d
j
, (2.19)
onde D
P MD
representa o coeficiente de PMD e d
j
o comprimento do j-ésimo enlace
pertencente à rota.
δ
%
representa o alargamento temporal do pulso óptico, em percentagem, e pode
ser expresso por:
δ
%
= 100B (∆t
RD
+ ∆t
P MD
) , (2.20)
onde B representa a taxa de transmissão. O parâmetro δ
%
deve ser menor que o
alargamento máximo permitido (δ
%QoT
).
Capítulo 3
Redes Neurais de Hopfield
Algoritmos de roteamento têm um enorme impacto sobre o desempenho das redes
de comunicação. Por esta razão, eles têm sido muito discutidos na comunidade ci-
entífica. Um algoritmo de roteamento deve calcular um caminho entre uma origem
e um destino de nós, objetivando o melhor desempenho da rede. Alguns algoritmos
determinam as rotas baseados no menor caminho, dentre eles pode-se citar o algo-
ritmo de Dijkstra [31] e o algoritmo de Bellman-Ford [13], [37]. Algumas técnicas
de inteligência computacional têm sido testadas e utilizadas para encontrar rotas.
Entre as técnicas mais comuns para esta tarefa pode-se citar Redes Neurais de Hop-
field (HNN - Hopfield Neural Networks) [81] [98], [3], Otimização por Colônia de
Formigas (ACO - Ant Colony Optimization) [14] [30] e Algoritmos Genéticos (GA -
Genetic Algorithm) [60].
Uma das principais características das Redes Neurais Artificiais (ANN - Artificial
Neural Networks) é que elas permitem que o algoritmo de roteamento seja adaptativo
em relação às mudanças na topologia da rede e nos custos dos enlaces.
Este capítulo tem como objetivo demonstrar como Redes Neurais de Hopfield
resolvem o problema do menor caminho, assim como mostrar as variações das abor-
dagens já propostas na literatura.
Na seção 3.1 são apresentados os conceitos sobre Redes Neurais, o neurônio bio-
lógico e o neurônio artificial, que é uma representação matématica da funcionalidade
do neurônio biológico. Na seção 3.2 é explicado o modelo proposto por John Hopfield
e suas aplicações. Na seção 3.3 é apresentada a aplicação do modelo de Hopfield ao
problema do menor caminho, assim como variações e otimizações do modelo padrão.
3.1 Redes Neurais Artificiais
Redes Neurais Artificiais são sistemas de computação que visam trabalhar no pro-
cessamento de dados de maneira semelhante ao cérebro humano [43]. Devido a
essa similaridade, as RNA’s devem ser capazes de aprender e tomar decisões ba-
seadas na aprendizagem. As Redes Neurais representam uma tentativa de superar
as limitações da computação convencional utilizando algumas vantagens do cérebro
humano, como: alto grau de paralelismo, tolerância à falhas, robustez, capacidade
de adaptação, auto-organização, etc.
O sistema nervoso humano é constituído de um conjunto de neurônios unidos
entre si, tendo como função principal coordenar os mecanismos internos e adaptar o
organismo às condições externas. O sistema nervoso é responsável pelo controle das
27
atividades vitais do corpo, as funções sensoriais, a memória, a inteligência, dentre
outras funções. O neurônio é responsável por processar as informações e rapassá-las
para outros neurônios através das sinapses nervosas. Sinapses nervosas são os pontos
onde as extremidades de neurônios vizinhos se encontram e o estímulo passa de um
neurônio para o seguinte por meio de mediadores químicos, os neurotransmissores.
3.1.1 Neurônio biológico
O neurônio é a unidade básica de processamento de informação do cérebro. O
cérebro humano contém entre 70 e 80 bilhões de neurônios e cada um pode ter em
torno de 10.000 ou mais sinapses [71].
O neurônio é constituído pelos seguintes componentes: corpo celular, dendritos,
axônio e sinapses, como exibido na figura 3.1.
Figura 3.1: Componentes de um neurônio biológico.
Dendritos são os principais receptores de sinais neurais para a comunicação entre
os neurônios. O axônio é o canal para a condução de mensagens para os terminais
pré-sinápticos, onde cada neurônio está em contato sináptico com outros neurônios
e, portanto, faz parte da rede que constitui o sistema nervoso. O corpo celular é
o centro metabólico do neurônio que processa as informações recebidas pelos den-
dritos e produz um impulso nervoso no axônio. A sinapse é o local do contato de
um neurônio com outro. Elas controlam a transmissão dos impulsos e podem ser
excitatórias ou inibitórias à passagem de informação dependendo dos sinais enviados
pelos axônios [71].
3.1.2 Neurônio artificial
Em 1943, McCulloch and Pitts [65], apresentaram um modelo que combina neuro-
fisiologia e lógica matemática, usando a propriedade do tudo ou nada de disparo
do neurônio, que é um elemento binário de tempo discreto. Eles mostraram como
excitação, inibição e limiar podem ser usados para construir uma grande variedade
de “neurônios”. Foi o primeiro modelo que amarrou o estudo de redes neurais dire-
tamente à ideia de computação em seu sentido moderno. Este neurônio artificial,
apresentado na figura 3.2, é chamado de modelo MCP (modelo de McCulloch-Pitts)
em reconhecimento ao trabalho pioneiro realizado por McCulloch e Pitts.
Neste modelo, os dendritos do neurônio biológico k são representados pelas m
entradas (x
i
) e o axônio é representado pela saída (y
k
). As sinapses nervosas são
28
Figura 3.2: Neurônio artificial de McCulloch e Pitts.
representadas por um peso (w
ki
) associado a cada entrada, podendo este ser exci-
tatório (valor positivo) ou inibitório (valor negativo). O corpo celular é responsável
por processar os sinais de entrada e transformá-lo em um sinal de saída.
A saída do neurônio é o resultado da aplicação da função de ativação, responsável
pelo limiar de disparo do neurônio, sobre a soma dos sinais de entradas ponderados
pelos seus respectivos pesos sinápticos somados à polarização externa (bias) b
k
. Esse
processo pode ser descrito pelas seguintes equações:
u
k
=
m
i=1
x
i
w
ki
, (3.1)
y
k
= f(u
k
+ b
k
), (3.2)
onde x
1
, x
2
, ..., x
m
são os sinais de entradas; w
k1
, w
k2
, ..., w
km
são os pesos sinápticos
do neurônio k; u
k
é o resultado da função soma; b
k
é o bias que tem o efeito
de aumentar ou diminuir a polarização na função de ativação; f(.) é a função de
ativação do neurônio e y
k
é a saída do neurônio k.
Os tipos de funções de ativação mais utilizadas em redes neurais artificiais são:
Função Degrau, Função Linear, Função Logística e Função Tangente Hiperbólica.
A função logística é utilizada na maioria das redes neurais, sendo utilizada inclusive
nas redes neurais de Hopfield, que serão apresentadas mais adiante. Os gráficos e
equações correspondentes a cada uma destas funções de ativação estão apresentados
na figura 3.3.
3.2 Redes Neurais de Hopfield
As Redes Neurais de Hopfield (HNN – Hopfield Neural Networks) [45], desenvolvidas
em 1982, geraram um grande avanço na fronteira do conhecimento de ANN’s, e
ajudou no ressurgimento do interesse pela área que passava por um período de crise
que durava 15 anos, desde a publicação de Minsky e Papert que mostrou que o
Perceptron [19] só resolvia problemas linearmente separáveis [20].
O grande avanço proporcionado pelo trabalho de Hopfield foi o fato de ter mos-
trado que um valor de energia pode ser associado a cada estado da rede neural e
que esta energia decresce de maneira monotônica à medida que uma trajetória é
descrita no espaço de estados em direção a um ponto fixo. Estes pontos fixos são
pontos estáveis de energia mínima criados através do processo de treinamento. Cada
um dos pontos fixos corresponde a um atrator e os pontos do espaço ao seu redor que
29
Linear Degrau ou Sinal Logística Tangente Hiperbólica
f(s) = s
f(s) =
+1 se s ≥ 0
−1 se s < 0
f(s) =
1
1 + e
−s
f(s) =
1 − e
−2s
1 + e
−2s
Figura 3.3: Funções de ativação mais utilizadas em redes neurais artificiais.
resultam na estabilização da rede nestes atratores em tempo finito correspondem às
suas bacias de atração. Com isto, Hopfield associou o seu modelo recorrente a siste-
mas físicos e criou subsídios para que as teorias correntes da Física/Termodinâmica
fossem aplicadas diretamente para estudar as características do seu modelo.
A rede de Hopfield também é conhecida como o padrão das redes neurais ar-
tificiais que apresentam realimentação [21]. Estas redes são constituídas por uma
única camada de neurônios simples totalmente interconectados; cada neurônio j
conectando-se a todos os outros e podendo receber estímulos de entrada 0 e 1 ou -1
e 1. No entanto, afim de evitar prováveis resultados espúrios na rede, J. J. Hopfield
afirma em [22] que na forma mais simétrica de uma coleção de memórias em uma
rede neural dinâmica, cada neurônio j tem dois estados, e são descritos por uma
variável i = ±1. A saída de cada neurônio depende dos valores prévios de sua pró-
pria ativação, de forma que neurônios individuais têm comportamento dependente
do tempo.
Esse tipo de rede neural é também chamado de rede auto-associativa, pois as
informações armazenadas na etapa de aprendizagem são utilizadas para associações
com os novos padrões de entrada na etapa de reconhecimento. Com a entrada de um
padrão incompleto na rede, por exemplo, os dados já armazenados são associados a
esses estímulos de entrada, de forma que a rede converge para o ponto de energia
mínimo e assim localiza onde o padrão completo esteja armazenado.
A figura 3.4 apresenta uma ilustração do princípio de memória exibido pelo mo-
delo de Hopfield, onde as demarcações em “x” representam os atratores que figuram
como os itens de memória armazenados. O conjunto de setas ao redor de cada atra-
tor representam as bacias atratoras, responsáveis em atrair possíveis soluções para
um dos estados da rede. As setas representam o caminho percorrido a partir do
estado inicial da rede (usadas como chave de busca na recuperação da informação)
até o ponto de equilíbrio.
As redes de Hopfield podem ser utilizadas como:
• Memórias associativas – A rede é capaz de “armazenar” informações baseada
em alguns de seus estados. A recuperação da informação é baseada no con-
teúdo da mesma, ou seja, com fragmentos da informação a ser buscada. O
armazenamento das informações é feito de forma distribuída na rede. Não
30
Figura 3.4: Exemplo de uma HNN com atratores armazenados na memória como
pontos de equilíbrio.
existe o conceito de endereçamento que é utilizado nas memórias de computa-
dores digitais.
• Problemas de otimização combinatória – A rede de Hopfield possui uma fun-
ção de energia que provê uma medida de desempenho para um determinado
problema de otimização que possui um conjunto grande, mas finito, de pos-
síveis soluções. Hopfield e Tank [23] foram os primeiros a utilizar a HNN
para resolver problemas de otimização combinatória. Eles demonstraram o
poder computacional deste tipo de rede aplicando-as ao problema do caixeiro
viajante (TSP – Traveling Salesman Problem).
As redes neurais de Hopfield são formadas por neurônios de McCulloch e Pitts.
Esta rede possui uma arquitetura do tipo recorrente na qual cada neurônio possui um
somatório do conjunto de entradas ponderadas U
i
, uma saída V
i
que é o resultado
da aplicação de uma função de ativação sobre a entrada U
i
(uma típica função
de ativação utilizada nas redes de Hopfield é a função Logística apresentada na
equação (3.3)). A saída V
i
após um atraso de tempo, é aplicada à entrada dos
outros neurônios ponderada por um peso sináptico T
ij
somado a uma polarização
externa (bias) I
i
, modificando posteriormente a entrada do neurônio, e alterando
assim o estado da rede neural. As saídas dos neurônios podem ser calculadas usando
a equação (3.3).
V
i
= g
i
(U
i
) =
1
1 + e
−λ
i
U
i
. (3.3)
A equação (3.3) é uma função de ativação, monótona crescente, que limita a
saída de cada neurônio para um intervalo pré-definido. É responsável por calcular a
saída do neurônio a partir da entrada do mesmo. O coeficiente λ determina o grau
de inclinação da função, quanto maior o valor de λ, mais a função sigmóide tende a
ter a forma da função degrau.
A figura 3.5 mostra a arquitetura da rede neural de Hopfield para o problema do
roteamento.
A dinâmica da rede de Hopfield para a proposição inicial aplicada a problemas
de roteamento é descrita pela equação (3.4) [46]:
31
Figura 3.5: Arquitetura da rede neural de Hopfield.
dU
i
dt
= −
U
i
τ
+
n
j=1
T
ij
V
j
+ I
i
. (3.4)
onde τ é a constante de tempo.
A equação diferencial (3.4) determina a dinâmica de atualização da entrada do
neurônio i (U
i
).
A atualização dos neurônios da rede de Hopfield, para cada iteração, pode ser
feito de duas formas:
• Forma síncrona - Todos neurônios são atualizados ao mesmo tempo (utilizada
em implementaçãoes em hardware e arquiteturas paralelas).
• Forma assíncrona - Os neurônios são atualizados em tempos diferentes (utili-
zada em arquiteturas sequenciais). Existem duas formas comuns de escolher
o neurônio a ser atualizado: escolha aleatória e escolha sequencial.
A dinâmica de qualquer sistema do tipo Hopfield como uma matriz de conexão
simétrica é governada por uma função de energia (de Lyapunov)[27], [46]. Esta
função é definida por:
E = −
1
2
N
i=1
N
j=1
T
ij
V
i
V
j
−
N
i=1
I
i
V
i
. (3.5)
De fato, a função de energia dada em (3.9) é uma função de Lyapunov [101]
e, neste caso, a estabilidade assintótica da rede pode ser demonstrada utilizando
o segundo método de Lyapunov, isto é, mostrando que o sistema dissipa energia
com o passar do tempo. Para tanto, basta mostrarmos que as derivadas parciais da
equação (3.9) são não crescentes. Esta condição é alcançada quando a matriz de
pesos é simétrica.
O segundo e o terceiro termo da equação (3.4) representam a variação de energia
da rede de Hopfield. Assim, a dinâmica do i-ésimo neurônio da rede de Hopfield
pode ser descrita em termos da função de energia.
32
dU
i
dt
= −
U
i
τ
−
∂E
∂V
i
. (3.6)
3.3 Redes Neurais de Hopfield aplicadas ao pro-
blema de roteamento
O problema do roteamento consiste em encontrar o menor caminho a partir de um
nó fonte s até um nó de destino d em uma rede de comunicação.
A topologia desta rede de comunicação pode ser representa por um grafo não-
orientado G = (N, A), onde N é o conjunto de nós da rede (vértices) e A é o
conjunto de enlaces (arestas), com n nós e l arcos. Considerando que para cada
arco (i, j) é relacionado um valor não-negativo C
ij
que representa o custo do enlace
(podendo ser o valor do comprimento do enlace, largura de banda, tempo de atraso
ou qualquer outra métrica), define-se um caminho dirigido P
sd
como uma sequência
ordenada de nós conectando s à d.
P
sd
= (s, i, j, k, ..., r, d). (3.7)
O custo do caminho será L
sd
= C
si
+C
ij
+C
jk
+...+C
rd
. O problema é encontrar
o caminho que tenha o menor custo L
sd
.
O uso de redes neurais artificiais para solucionar o problema do menor caminho
a partir de um determinado par origem-destino foi iniciado por Rauch e Winarske
[81]. Eles propuseram uma arquitetura de HNN baseada em uma matriz de tamanho
n × m, onde n é o número de nós da rede e m é o número de nós formando o caminho.
Uma limitação clara desta abordagem consiste na necessidade de saber a priori o
número de nós que formam o caminho. Este algoritmo acha apenas soluções sub-
ótimas para o problema SP, já que o menor caminho pode não ter m nós. Esta
configuração foi feita a partir do uso das HNN para o problema TSP modificando
as restrições.
Para corrigir esta falha, Zang e Thomopoulos [98] ao invés de usar m como o
número total de nós do caminho, utilizaram o número total de nós da rede (n).
A matriz de custos desta arquitetura é configurada da seguinte forma: atribuíram
custo zero aos enlaces recorrentes (loopback) de cada nó e custo elevado para enla-
ces inexistentes. Com estas alterações, conexões recorrentes podem fazer parte do
caminho encontrado sem aumentar o custo do caminho. Apesar desta formulação
encontrar o menor caminho, ela tem inconvenientes. Para cada par origem-destino
que se deseje encontrar o menor caminho ou qualquer alteração na topologia/custos,
é necessário modificar a configuração da rede neural porque estas informações estão
mapeadas nas sinapses dos neurônios, aumentando o tempo de resposta.
Com o objetivo de superar esta limitação, Ali e Kamoun [3] propuseram um
novo algoritmo adaptativo, onde a matriz de peso apenas leva consigo informações
de convergência. As informações sobre custo dos enlaces e topologia é informada
pela polarização externa dos neurônios.
3.3.1 Modelo de Ali e Kamoun
Para formular o problema do menor caminho em termos do modelo de Hopfield, é
necessário um esquema de representação adequado para que o menor caminho possa
33
ser decodificado a partir do estado final da rede neural. O modelo proposto por Ali
e Kamoun [3] é organizado em uma matriz (n × n), sem os elementos da diagonal
principal, já que eles não são necessários. Note que não tem sentido um nó estar
conectado a ele mesmo na busca pelo menor caminho. Cada elemento na matriz é
representado por um neurônio que é referenciado pela dupla de índices(x, i), onde
x é o índice da linha e i é o índice da coluna. O número de neurônios da rede de
Hopfield para este problema é de n(n − 1).
O custo do nó x ao nó i é denotado por C
xi
que assume valores reais positivos e
normalizados entre (0, 1]. Para enlaces não existentes, o valor do custo atribuído a
este enlace é setado em zero.
Uma matriz de conexão ρ
xi
é responsável por informar a existência dos enlaces
e é definido por:
ρ
xi
=
1, se o arco do nó x ao nó i não existe.
0, caso contrário
(3.8)
A figura 3.6 apresenta uma pequena rede de comunicação representada por um
grafo e pelas matrizes de custos e topologia.
Rede de Comunicação
Matriz de custos (C
xi
)
Nó 1 2 3 4 5
1 0 0,35 0,4 0 0
2 0,35 0 0,6 0,8 0,9
3 0,4 0,6 0 0,5 0,85
4 0 0,8 0,5 0 0,3
5 0 0,9 0,85 0,3 0
Matriz de top ologia (ρ
xi
)
Nó 1 2 3 4 5
1 1 0 0 1 1
2 0 1 0 0 0
3 0 0 1 0 0
4 1 0 0 1 0
5 1 0 0 0 1
Figura 3.6: Representação de uma rede de comunicação com as matrizes de custos
e topologia.
Para resolver o problema de roteamento em redes de comunicação utilizando
a rede neural de Hopfield, uma função de energia deve ser definida. A função de
energia tem o objetivo de definir o processo que induz a rede neural ao mais baixo
estado de energia. Quando a rede alcançar esse estado de menor energia significa
que a rede de Hopfield encontrou o menor caminho. A função de energia faz com que
a rede neural tenda a encontrar o menor caminho, porém não garante encontrar o
menor caminho, ou até mesmo encontrar um caminho válido. A equação de energia
de Ali e Kamoun [3] é definida por:
E = E
1
+ E
2
+ E
3
+ E
4
+ E
5
, (3.9)
34
onde:
E
1
=
µ
1
2
n
x=1
(x,i)=(d,s)
n
i=1
i=x
C
xi
V
xi
, (3.9a)
E
2
=
µ
2
2
n
x=1
(x,i)=(d,s)
n
i=1
i=x
ρ
xi
V
xi
, (3.9b)
E
3
=
µ
3
2
n
x=1
n
i=1
i=x
V
xi
−
n
i=1
i=x
V
ix
2
, (3.9c)
E
4
=
µ
4
2
n
x=1
n
i=1
i=x
V
xi
(1 − V
xi
) , (3.9d)
E
5
=
µ
5
2
(1 − V
ds
), (3.9e)
onde µ
1
, µ
2
, µ
3
, µ
4
e µ
5
são constantes.
O termo 3.9a minimiza o custo total do caminho, levando em consideração o
custo dos enlaces existentes. O termo 3.9b previne que enlaces inexistentes façam
parte do caminho encontrado. O termo 3.9c é zero se para todo nó na solução, o
número de enlaces de entrada é igual ao número de enlaces de saída. O termo 3.9d
leva a rede neural a convergir para um dos 2
n
2
−2
estados estáveis. O termo 3.9e
é zero quando a saída do neurônio de índice (d, s) dispara o valor 1, onde d é o
destino e s a fonte. Embora o enlace de d para s não faça parte da topologia, ele é
introduzido para garantir que os nós de origem e de destino façam parte da solução.
Smeda e Hawary [94] usaram a mesma equação de energia que Ali e Kamoun,
porém sem o quinto termo, que força um enlace (abstrato) a partir do destino até a
origem produzindo um ciclo. Neste trabalho eles pensaram que este enlace abstrato
era desnecessário.
Park e Choi [72] afirmaram que o modelo de Ali e Kamoun não converge para
redes com mais de 20 nós. Então, eles propuseram uma nova abordagem que afirma-
ram ser adequada para redes com muitos nós. Nesta mesma abordagem monstraram
bons resultados para roteamento multicast. Eles trocaram o quinto termo da equa-
ção de energia proposta por Ali e Kamoun, utilizando um termo que refere-se a
unidirecionalidade dos enlaces.
Ahn et al., [2] baseado na abordagem de Park e Choi [72], propuseram um al-
goritmo que evita ciclos, resultando em uma convergência mais rápida que as abor-
dagens anteriores. Inseriram dois termos à equação de energia de Park e Choi para
eliminar a possibilidade de ciclos ou partições no caminho. Estes termos também
auxiliam na velocidade e precisão de convergência da rede.
Além disso, cada neurônio pode ser externamente excitado por uma polarização
(bias) em uma entrada externa I
xi
. Este sistema de entradas é utilizado neste
modelo para ajustar o nível de excitação da rede inteira e repassar os dados sobre
a topologia da rede, assim como origem e destino, para à rede neural. A expressão
para a polarização é definida por:
35
I
xi
= −
µ
1
2
C
xi
(1 − δ
xd
δ
is
) −
µ
2
2
ρ
xi
(1 − δ
xd
δ
is
) −
µ
4
2
+
µ
5
2
δ
xd
δ
is
, (3.10)
∀ (x = i) , ∀ (y = i) ,
onde δ é função delta de Kronecker que é definida por:
δ
ab
=
1, se a = b
0, caso contrário
. (3.11)
A matriz de sinapses T
xi,yj
é definida por:
T
xi,yj
= µ
4
δ
xy
δ
ij
− µ
3
δ
xy
− µ
3
δ
ij
+ µ
3
δ
jx
+ µ
3
δ
iy
. (3.12)
O primeiro termo da equação (3.12) representa uma excitação de conexões rea-
limentáveis, o segundo e o terceiro termo representa uma inibição de conexões entre
neurônios da mesma linha e mesma coluna, respectivamente. Os últimos dois termos
representam uma excitação entre neurônios com conexão cruzada.
Uma vantagem do modelo proposto por Ali e Kamoun [3] é que as informações
de topologia (custo dos enlaces e conectividade entre os nós) estão mapeadas na
matriz de polarização em vez de estarem presentes na matriz de pesos sinápticos.
Neste caso, não é necessário modificar os parâmetros internos da arquitetura de
rede neural. O algoritmo proposto pode se adaptar rapidamente às mudanças na
topologia da rede e nos custos dos enlaces. Isso faz com que este algoritmo seja mais
atraente para operar em tempo real.
Outra vantagem deste modelo, é que matriz de conexão é menos complexa (nem
todos os neurônios são conectados). O total de conexões é de (n
2
− n)(4n − 6),
enquanto a abordagem de Zang e Thomopoulos [98] contém (n
4
) conexões.
Reescrevendo as Equações (3.3), (3.4) e (3.6) da dinâmica da rede neural de
Hopfield levando em consideração a representação do neurônio com duplo índice,
aplicado ao problema de roteamento, tem-se:
V
xi
=
1
1 + e
−λ
xi
U
xi
, (3.13)
∀ (x, i) ∈ N × N / x = i,
dU
xi
dt
= −
U
xi
τ
+
n
y=1
n
j=1
j=y
T
xi,yj
V
yj
+ I
xi
, (3.14)
dU
xi
dt
= −
U
xi
τ
−
∂E
∂V
xi
. (3.15)
Sem perda de generalização e para maior simplicidade assume-se que na equação
(3.13), λ
xi
= λ para todos os neurônios.
36
3.3.2 Execução do algoritmo
Um importante parâmetro na simulação são os valores iniciais dos neurônios U
xi
.
Uma vez que a rede neural não deve favorecer qualquer caminho específico, todos
os valores de U
xi
devem ser inicializados com zero. Porém um pouco de ruído
inicial ajuda a quebrar a simetria da arquitetura da rede neural e também dará
a possibilidade da rede neural encontrar mais que um caminho. O valor do ruído
sugerido por Ali e Kamoun [3] foi de −0.0002 ≤ U
xi
≤ +0.0002.
Dados os valores iniciais dos neurônios (U
xi
) no tempo t = 0, a evolução do
estado da rede neural com o passar do tempo é simulada resolvendo numericamente
a equação (3.14). Isto corresponde a solucionar um sistema de n(n − 1) equações
diferencias não-lineares, onde as variáveis são as saídas dos neurônios V
xi
. Para
solucionar este sistema, os autores utilizaram o método de quarta ordem de Runge-
Kutta [18], já que ele é suficientemente preciso e fácil de implementar. A simulação
consiste em observar e atualizar a saída do neurônio em passos incrementais de
tempo δt. Ali e Kamoun [3] mostraram em suas simulações, que um bom valor para
δt é 10
−5
. Reduzindo este valor, aumenta-se o número de iterações sem ganho nos
resultados. Os autores escolheram para a constante de tempo τ de cada neurônio o
valor 1.
Embora exista a possibilidade da rede em se estabilizar em um mínimo local
do hiperplano, os autores mostraram que, com um bom ajuste dos coeficientes µ
i
s,
essa possibilidade pode ser minimizada senão excluída. Os autores em seus estudos
tiraram algumas conclusões em relação a estes parâmetros. O parâmetro µ
2
deve
ser igual a µ
5
e este valor deve ser elevado. O valor de µ
1
deve ser bem menor que
µ
2
e maior que µ
4
. O valor do parâmetro µ
3
deve ser maior que µ
1
/2 e menor que
µ
2
. Baseado nestas restrições, os autores escolheram os seguintes valores para os
parâmetros
1
:
Tabela 3.1: Valores dos parâmetros µ
i
s.
Parâmetro Valor
µ
1
950
µ
2
2500
µ
3
1500
µ
4
475
µ
5
2500
Experimentalmente, os autores descobriram que há um compromisso entre a
escolha de um alto ou baixo valor para o parâmetro λ. Embora um λ com valor
alto faça com que a rede neural tenha uma resposta rápida, a solução encontrada
nem sempre é um mínimo global. Por outro lado, um λ com valor baixo faz com
que a rede neural tenha uma resposta lenta mas que garante uma solução ótima.
De fato, observou-se que a capacidade do algoritmo de separar entre uma solução
ideal e uma solução muito boa também é reforçado pela suavidade da função de
limiarização. Isto é explicado pelo fato de que um λ com valor alto (como 10 ou
1
Simulações efetuadas neste trabalho com redes de médio porte, mostraram que o valor proposto
pelos autores para o parâmetro µ
3
torna a rede neural incapaz de encontrar caminhos válidos para
determinados pares de fonte e destino, como correção foi utilizado o valor 2500 nas simulações.
37
100) pode não dar tempo suficiente para que um neurônio otimize seu desempenho.
A fim de permitir que a rede neural convirja equilibrando velocidade e precisão, os
autores utilizaram λ = 1.
A simulação é encerrada quando o sistema atinge um estado final estável. Este
estado é considerado final quando a variação entre todas as saídas dos neurônios não
ultrapassa o limiar de ∆V
th
= 10
−5
entre uma iteração e outra.
Quando a rede atinge o estado final, calcula-se a matriz Y
xi
, definida por:
Y
xi
=
1 se V
xi
≥ 0.5
0 se V
xi
< 0.5
. (3.16)
Se o enlace entre o nó x e o nó i tem o valor de Y
xi
= 1, então este enlace
faz parte do menor caminho. Caso Y
xi
= 0, este enlace não faz parte do menor
caminho.
O pseudocódigo do algoritmo de Ali e Kamoun [3] e abordagens similares é
apresentado no Algoritmo 1:
Algoritmo 1: Pseudocódigo do algoritmo de roteamento utilizando redes neu-
rais de Hopfield.
Recebe parâmetros;1
Determina T
xi,yj
;2
Recebe C
xi
;3
Calcula ρ
xi
;4
Recebe fonte e destino;5
Calcula I
xi
;6
Insere ruído inicial em U
xi
;7
Calcula V
xi
(limiar de U
xi
);8
repita9
Repassa histórico de U
xi
e V
xi
;10
Atualiza os neurônios (U
xi
e V
xi
);11
até ∆V
xi
< limiar ;12
Calcula Y
xi
(binarização de V
xi
);13
Obtem caminho a partir de Y
xi
;14
3.3.3 Modelo de Bastos-Filho et al.
Para simplificar e acelerar a convergência da rede, Bastos-Filho et al., [7] propuse-
ram uma simples equação de diferença finita e discreta em substituição à equação
diferencial proposta por Ali e Kamoun [3], como descrito a seguir:
U
xi
[n + 1] = U
xi
[n] − AU
xi
[n − 1] − BU
xi
[n − 2] + C
n
y=1
n
j=1
j=y
T
xi,yj
V
yj
[n] + I
xi
.
(3.17)
onde, U
xi
[n + 1] é a próxima entrada do neurônio xi calculado com base nos valores
da sua própria entrada em instantes passados U
xi
[n], U
xi
[n − 1] e U
xi
[n − 2], na saída
38
de todos os neurônios da rede V
yj
[n], na matriz de pesos sinápticos T
xi,yj
e na matriz
de polarização I
xi
[n]. Esta equação insere novas constantes ao algoritmo (A, B e
C), e os valores das constantes apresentados neste trabalho são empíricos.
Schuler et al., [88] aplicaram a técnica Simulated Annealing (SA) para otimizar
os parâmetros da HNN com o objetivo de reduzir o número de iterações e erros
quando a HNN tenta encontrar o menor caminho. Em seguida Schuler et al., [89]
propuseram uma versão modificada da equação de tempo discreto proposta por
Bastos-Filho et al., [7] e usaram SA para otimizar os parâmetros da HNN. A nova
equação é mostrada abaixo:
U
xi
[n + 1] = U
xi
[n] − AU
xi
[n − 1] + B
n
y=1
n
j=1
j=y
T
xi,yj
V
yj
[n] + CI
xi
. (3.18)
As modificações efetuadas na equação consistem em remover as entradas prévias
U
xi
[n − 2] da equação (3.17) e atribui diferentes parâmetros para o somatório (pesos
× saídas) e para o termo do bias como mostrado na equação (3.18). Schuler et al.,
[89] afirmaram que com esta equação, espera-se reduzir o custo computacional, o
número de iterações e a percentagem de erro.
A nova formulação proposta reduz o custo computacional da HNN. Porém a
técnica SA não mostrou-se confiável para otimizar os parâmetros da HNN. Então,
Schuler et al., [8] propuseram usar a técnica Particle Swarm Optimization (PSO)
para achar o melhor conjunto de parâmetros para a HNN encontrar o menor cami-
nho.
Utilizando a mesma dinâmica de atualização do neurônio proposta por Ali e
Kamoun [3], porém modificando a equação de energia, outros trabalhos mostraram
que a rede atinge a estabilidade com um menor número de iterações.
Kojic et al., [55], [56] modificaram a equação de polarização do modelo de Ali
e Kamoun, para que nesta nova abordagem informações de carga da rede também
fossem consideradas como métrica na composição do custo dos enlaces.
3.4 Redes Neurais de Hopfield aplicadas ao pro-
blema de RWA
Em pesquisas recentes, Kojic et al. utilizaram modelos baseados em Redes Neu-
rais de Hopfield [57], [58], [59] para solucionar o problema de roteamento em redes
ópticas. No trabalho em lide [57] foram utilizadas duas abordagens: na primeira a
rede óptica é dividida em sub-redes (uma para cada comprimento de onda) e dos
caminhos encontrados nas sub-redes escolhe-se o com menor número de saltos; na
segunda é utilizado como métrica de custo, informações de uso dos enlaces, porém
não foi informado a estratégia de alocação de canais. Na proposta em lide [58] nova-
mente o uso dos comprimentos de onda dos enlaces foram utilizados como métrica,
porém neste trabalho, a conversão de comprimento de onda foi utilizada, assim
como diversas abordagens de alocação de canais. O trabalho em lide [59] é uma
proposta para modelar redes ópticas com conversão de comprimento de onda, para
cada possível conversão existe um custo associado (um tipo de “enlace”). Em todas
a propostas, o algoritmo de roteamento é uma HNN (modelo de Ali e Kamoun [3]).
Capítulo 4
Uma abordagem para problemas
multi-objetivos baseada em Particle
Swarm Optimization utilizando
Crowding Distance e Roulette
Wheel
As Redes Neurais de Hopfield utilizadas no problema de roteamento e atribuição
de comprimento de onda (RWA - Routing and Wavelength Assignment) possuem
diversos parâmetros cujos valores precisam ser definidos previamente. Estes valores
podem ser dependentes do cenário para o qual o algoritmo está sendo aplicado e
influenciam diretamente no desempenho dele. Definir qual a melhor combinação de
parâmetros por tentativa e erro para este problema pode ser uma tarefa um tanto
tediosa. Devido a este fato, técnicas de Inteligência Computacional de Enxames (CSI
- Computational Swarm Intelligence) podem ser aplicadas para tornar a seleção dos
valores dos parâmetros um trabalho mais efetivo.
A otimização que está sendo tratada possui mais que um objetivo conflitante
a ser otimizado. Neste caso, o problema não terá uma única solução. Em vez
disso, existirão várias soluções ótimas com o compromisso de balancear os diferentes
objetivos. A utilização de algoritmos evolucionários e algoritmos de inteligência de
enxames tem aumentado nos últimos anos, resultando em uma ampla variedade de
algoritmos efetivos.
Particle Swarm Optimization (PSO), é uma classe de algoritmos concebida para
resolver problemas de otimização e busca. PSO foi proposto por Kennedy e Eberhart
em 1995 [53], [32], inspirado no comportamento social de um bando de pássaros.
Em geral, PSO é usado para solucionar problemas com um objetivo num espaço
hiperdimensional onde as variáveis são contínuas. Apesar do PSO ter sido concebido
para resolver problemas monobjetivos, devido à sua simplicidade, alguns trabalhos
têm proposto a adaptação do PSO para solução de problemas multiobjetivos.
Este capítulo tem como objetivo apresentar mais uma nova abordagem baseada
no PSO para encontrar soluções para problemas de otimização multiobjetivo.
Na seção 4.1 são descritos os conceitos básicos de Otimização Multiobjetivo, dos
quais pode-se destacar o conceito de Pareto front e as variações do conceito de do-
minância. Na seção 4.2 é descrito o modelo do PSO, detalhando seu funcionamento,
40
parâmetros e variações. Na seção 4.3 são apresentadas outras abordagens basea-
das em PSO para problemas multiobjetivos. Estas abordagens são utilizadas na
comparação entre as mesmas e a abordagem proposta. Na seção 4.4 é apresentada
a abordagem proposta, assim como as alterações nos operadores. Em seguida, na
seção 4.5 são demonstradas as configurações das simulações que são as seguintes: as
funções de teste que serão utilizadas, as métricas utilizadas para comparações e os
parâmetros internos de cada algoritmo. Finalmente na seção 4.6 são apresentados
os resultados e conclusões das simulações.
4.1 Conceitos básicos de Otimização Multiobjetivo
Um problema geral de otimização multiobjetivo pode ser definido como
1
:
minimize
f(x) := [f
1
(x), f
2
(x), ..., f
k
(x)], (4.1)
sujeito à:
g
i
(x) ≤ 0 i = 1, 2, ..., m, (4.2)
h
j
(x) = 0 j = 1, 2, ..., p, (4.3)
onde x = [x
1
, x
2
, ..., x
n
]
T
∈ R
n
é o vetor de variáveis de decisão do espaço de busca,
f
i
: R
n
→ R, i = 1, ..., k são as funções objetivos e g
i
, h
j
: R
n
→ R são as funções
de restrições do problema.
Para descrever o conceito de otimalidade abaixo são fornecidas algumas defini-
ções.
Definição 1. Dado dois vetores x, y ∈ R
k
, define-se que x ≤ y se x
i
≤ y
i
para
i = 1, ..., k, e que x domina y (denotado por x ≺ y) se x ≤ y e x = y.
Definição 2. Um vetor de variáveis de decisão no espaço de busca x ∈ X ⊂ R
n
é não dominado em relação à X , se não existe outro x
∈ X tal que
f(x
) ≺
f(x).
Definição 3. Um vetor de variáveis de decisão no espaço de busca x
∗
∈ F ⊂ R
n
(F é a região factível) é Pareto-ótimo se ele é não dominado em relação à F.
Definição 4. O conjunto Pareto-ótimo P
∗
é definido por:
P
∗
= {x ∈ F|x é Pareto-ótimo}.
Definição 5. O Pareto front PF
∗
é definido por:
PF
∗
= {
f(x) ∈ R
k
|x ∈ P
∗
}.
Duas soluções podem ser comparadas de diversas formas, a tabela 4.1 define os
operadores de relação de dominância entre soluções.
A figura 4.1 mostra o caso de relação de dominância para um espaço de dois
objetivos. Supondo um problema de minimização em todos os objetivos, as soluções
claras são soluções piores que a solução escura em pelo menos um objetivo. A solução
escura não é pior que as soluções claras em todos os objetivos, e melhor que todas
as outras em pelo menos um objetivo. Isso faz com que as soluções claras sejam
classificadas com soluções dominadas e a solução escura como não-dominada.
A figura 4.2 mostra o Pareto front formado pelo conjunto de soluções não-
dominadas (soluções escuras). As soluções do Pareto front são ditas incomparáveis.
1
Sem perder a generalização, pode-se assumir apenas problemas de minimização.
41
Tabela 4.1: Relações de dominância entre soluções.
relação soluções
dominância forte x
1
 x
2
x
1
é melhor que x
2
em todos os objetivos
dominância x
1
x
2
x
1
não é pior que x
2
em todos os objetivos
e melhor em pelo menos um objetivo
dominância fraca x
1
x
2
x
1
não é pior que x
2
em todos os objetivos
incomparável x
1
|| x
2
nem x
1
domina fracamente x
2
, nem
x
2
domina fracamente x
1
Figura 4.1: Relação de dominância para um espaço de dois objetivos
Um vetor de variáveis de decisão no espaço de busca x
∗
∈ F ⊂ R
n
(F é a região
factível) é Pareto-ótimo se ele é não dominado em relação à F.
O objetivo é determinar o conjunto Pareto-ótimo a partir do conjunto F de todos
os vetores de variáveis de decisão do espaço de busca que satisfaça (4.2) e (4.3). Na
prática, nem todo o conjunto Pareto-ótimo encontrado é o desejável (por exemplo,
pode não ser desejável ter diferentes soluções que mapeiem os mesmos valores no
espaço de funções objetivos) ou realizável.
4.2 Particle Swarm Optimization
Particle Swarm Optimization é um algoritmo de busca baseado em populações ins-
pirado no comportamento social de pássaros. A intenção inicial do PSO foi simular
graficamente a coreografia graciosa e imprevisível de um bando de pássaros [53] e
balancear pesos de redes neurais [34]. PSO logo se tornou um otimizador global
muito popular, principalmente em problemas nos quais as variáveis de decisão são
número reais
2
[36], [35].
2
É importante frisar que existem propostas que usam codificações alternativas para o PSO (por
exemplo, binário [54] e inteiro [49]), porém nenhuma foi tão popular quanto a proposta original
42
Figura 4.2: O Pareto front de um conjunto de soluções para um espaço de dois
objetivos
No PSO, indivíduos, são chamados de partículas que “voam” através do espaço
de busca hiperdimensional. Mudanças nas posições das partículas no espaço de
busca são baseadas na tendência psico-social dos indivíduos em simular o sucesso de
outros indivíduos. As mudanças de uma partícula dentro do enxame são, portanto,
influenciada pela experiência, ou conhecimento dos seus vizinhos.
4.2.1 PSO básico
O algoritmo PSO mantém um enxame de partículas, onde cada partícula repre-
senta uma potencial solução. Fazendo analogia com os paradigmas de computação
evolutiva, um enxame é semelhante a uma população, enquanto uma partícula é
semelhante a um indivíduo.
Em termos simples, as partículas “voam” dentro de um espaço de busca multidi-
mensional, onde a posição de cada partícula é ajustada de acordo com sua própria
experiência e a experiência de seus vizinhos. x
i
(t) representa a posição da partícula
i, no instante de tempo t. A posição de i no instante de tempo t + 1 é representada
por x
i
(t + 1) e é alterada pela adição da velocidade v
i
(t + 1):
x
i
(t + 1) = x
i
(t) + v
i
(t + 1). (4.4)
v
i
(t + 1) é o vetor velocidade que guia o processo de otimização, e reflete tanto
a experiência da partícula quanto a troca de informação social com a vizinhança
da partícula. A experiência de uma partícula é geralmente referenciada como o
componente cognitivo, que é proporcional à distância da atual posição da partícula
e sua melhor posição encontrada (líder cognitivo) desde o início do processo de busca.
A troca de informação social é referenciada como o componente social da equação
de velocidade, que é proporcional à distância da atual posição da partícula e uma
desenvolvida para vetores de números reais.
43
partícula do enxame designada como líder social. O vetor da velocidade é definido
da seguinte forma:
v
i
(t + 1) = v
i
(t) + c
1
r
1
(p
i
(t) − x
i
(t)) + c
2
r
2
(p
ig
(t) − x
i
(t)), (4.5)
onde i = 1, ..., N e N é o tamanho do enxame; p
i
(t) é a melhor posição encontrada
pela partícula durante o processo de busca até o momento; p
ig
(t) é a melhor solução
encontrada pelas partículas que formam a vizinhança da partícula; c
1
é o coeficiente
de aceleração cognitivo e c
2
é o coeficiente de aceleração social. São estes parâmetros
que determinam a relativa influência dos componentes sociais e cognitivos; r
1
e r
2
são dois números aleatórios gerados por uma distribuição uniforme no intervalo [0,1].
• Ilustração Geométrica: O efeito da equação de velocidade das partículas
(4.5) pode ser facilmente ilustrado em um plano de bidimensional. Na figura
4.3, são mostradas duas partículas (x
e x

) pertencentes a um enxame com
outras partículas. O objetivo das partículas é encontrar posições no espaço de
busca que otimizem uma função. O espaço de busca de cada dimensão está
definido no intervalo [−1, 1] e o melhor valor está em (0,0). Os vetores nas
partículas representam as componentes de velocidade.
(a) (b)
Figura 4.3: Representação do “vôo” de duas partículas: (a) no instante t e (b)
no instante t + 1.
Para cada partícula, existem vetores que representam componentes de veloci-
dade: o vetor tracejado representa a velocidade que guia a partícula em direção
à melhor posição da vizinhança (componente social), o vetor com linha cheia
representa a velocidade que guia a partícula em direção à melhor posição já en-
contrada (componente cognitivo), o vetor pontilhado representa a velocidade
que a partícula já possuia na iteração anterior.
A velocidade resultante de cada partícula é a soma das componentes. No
instante (t) o maior componente de velocidade, tanto de x
quanto de x

, é o
44
que aponta para o componente social, portanto, o próximo valor de velocidade
v
i
(t + 1) terá uma maior influência desta componente. Isto faz com que as
partículas movam-se no sentido da melhor posição da vizinhança. A figura 4.3b
mostra a mudança de posição das partículas em relação à figura 4.3a. Neste
passo, as melhores posições das partículas foram alteradas, mudando assim os
componentes de velocidade que apontam para as memórias das partículas.
A movimentação das partículas é influenciada pela experiência individual e
pela experiência do grupo. Isto faz com que as partículas tendam a encontrar
posições melhores do que as posições que elas se encontram, fazendo com que
naturalmente elas tomem a(s) direção(ões) do(s) ótimo(s) da função.
• Parâmetros e definições utilizadas no PSO: O PSO básico é influenciado
por um número de parâmetros de controle que são: número de dimensões do
problema, tamanho do enxame, tamanho da vizinhança (será discutido na
seção 4.2.3), coeficientes de aceleração, fator de inércia, número de iterações,
coeficientes de aceleração e valores aleatórios que multiplicam a contribuição
dos coeficientes de aceleração.
A influência do limite de velocidade, fator de inércia e coeficiente de constrição
será discutido na seção 4.2.2. O restante dos parâmetros será discutido abaixo:
– Tamanho do Enxame: É o número de partículas representado por N.
Quanto mais partículas tiver o enxame, maior a diversidade na inicia-
lização das partículas (desde que seja utilizado um bom mecanismo de
inicialização das partículas) e também será dada uma maior cobertura do
espaço de busca no dercorrer das iterações. Como desvantagem, quanto
maior o número de partículas, maior o custo de comunicação (para um
mesmo número de iterações). Estudos empíricos mostram que o PSO
consegue achar boas soluções com um enxame que contenha entre 10 e
30 partículas [16], [100].
– Inicialização do Enxame: Suponha que um ótimo esteja localizado
dentro do domínio definido pelos dois vetores, x
max
e x
min
, que respecti-
vamente representam os limites mínimos e máximos em cada dimensão.
Um eficiente método de inicialização para as posições da partícula é:
x(0) = x
min,j
+ r
j
(x
max,j
− x
min,j
) ∀j = 1, ..., n
x
, ∀i = 1, ..., n
s
(4.6)
onde r
j
∼ U(0, 1).
As velocidades iniciais podem ser zero, mas isso atrasa a convergência do
algoritmo.
Se as partículas forem inicializadas com velocidades diferente de zero,
elas iniciarão a simulação em movimento. Se estes valores iniciais forem
aleatórios, a direção das partículas também serão aleatórias inicialmente.
Se os valores iniciais da velocidade forem relativamente altos, a varia-
ção da posição no início do algoritmo também será. Com isso, aumenta
probabilidade das partículas atingirem as fronteiras do espaço de busca,
atrasando a convergência da simulação.
45
Na inicialização, o valor considerado para a melhor posição de cada par-
tícula é a posição da mesma no instante t = 0
p
i
(0) = x
i
(0). (4.7)
Embora seja importante inicializar as partículas uniformimente ao longo
do espaço de busca em aplicações para resolver problemas do mundo
real, para estudos empíricos de diferentes algoritmos esta distribuição
não é desejável. Este método de inicialização pode dar falsas impresssões
em relação ao desempenho relativo do algoritmo. Em estudos empíricos
recomenda-se utilizar áreas que não contenha(m) o(s) ótimo(s), com ob-
jetivo de validar a habilidade do algoritmo para localizar soluções fora do
espaço de inicialização [39].
– Critérios de parada: Alguns critérios de parada são usados e propostos
pela literatura. Entre eles, pode-se citar:
∗ Número de iterações: O PSO para a execução quando o número
máximo de iterações (ou chamadas da função objetivo) é alcançado.
O valor a ser escolhido é dependente do problema. Um valor baixo
pode fazer com que o PSO encerre a busca de forma prematura. Um
valor alto pode causar custo computacional desnecessário. É comum
utilizar este critério em composição com outros critérios de parada.
∗ Solução aceitável: Um valor de limiar é escolhido. Em problemas
de minimização, por exemplo, este limiar é um pouco maior que o
mínimo absoluto. Se o limiar for muito maior que o mínimo absoluto,
o PSO irá parar encontrando uma solução subótima. Se o limiar for
pouco maior que o mínimo absoluto, talvez o PSO nunca encontre
uma solução.
∗ Convergência estagnada: Existem diferentes formas de medir a
melhora do PSO. Por exemplo, se as velocidades das partículas estão
próximas de zero, as partículas se movem pouco. Se este fenômeno
ocorre durante uma certa quantidade de iterações, a simulação pode
ser encerrada. Dois novos parâmetros são acrescentado para este
critério de parada: o tamanho da janela de iterações (ou chamadas
da função objetivo) e o limiar que indica que não houve melhora
significativa durante a avaliação da janela de iteração.
– Coeficientes de aceleração: Os coeficientes de aceleração, c
1
e c
2
, em
conjunto com os termos aleatórios r
1
e r
2
controlam a influência estocás-
tica dos componentes cognitivos e componentes sociais sobre a velocidade
global da partícula. As constantes c
1
e c
2
são referenciadas como parâ-
metros de confiança, onde c
1
expressa o quanto a partícula “confia” nela
mesma, enquanto c
2
expressa o quanto a partícula “confia” na vizinhança.
– Espaço de busca: É definido pela combinação do número de dimen-
sões que o problema possui e o intervalo de busca em cada uma delas.
Representa o conjunto de todas as possíveis soluções cujos valores em
cada dimensão podem variar dentro de um intervalo pré-definido. Cada
partícula i assume uma posição dentro deste espaço de busca. A posição
das partículas está dentro dos seguintes limites:
46
x
i
(t) = (x
i1
(t), x
i2
(t), ..., x
iD
(t)),
∀x
id
∈ {min(x
d
), max(x
d
)}|d ∈ {1, 2, ..., D}, (4.8)
onde D é o número de dimensões do problema, e min(x
d
) e max(x
d
) são
os limites do intervalo de busca para a dimensão d.
• Processo de execução do algoritmo: O processo de execução do PSO é
representado pelo Algoritmo 2
Algoritmo 2: Pseudocódigo do PSO
Inicialize o enxame;1
Avalie o fitness de cada partícula do enxame;2
Determine líder(es) social(is);3
g = 0;4
enquanto g < gmax faça5
para cada partícula faça6
Atualize velocidade e posição;7
Avalie o fitness;8
Atualize pBest;9
fim10
Atualize líder(es) social(is);11
g++;12
fim13
solução = melhor partícula do enxame;14
Na linha 1, o exame é inicializado. Na linha 2, é calculado o fitness de todas
as partículas do enxame. Em seguida é(são) escolhido(s) o(s) líder(es) das
partículas.
O PSO executa enquanto o critério de parada não for satisfeito (no pseudo-
código, o critério de parada é o número máximo de iterações gmax). Cada
partícula do enxame tem sua velocidade e posição atualizadas seguindo as
equações 4.5 e 4.4 respectivamente. Em seguida, é feita a chamada da função
objetivo para atualizar o valor do fitness na nova posição. Na linha 9 é feita
a atualização da melhor posição da partícula.
Quando o critério de parada é atingido, a simulação é encerrada. A solução
do enxame que tiver o melhor valor de fitness é a solução final.
4.2.2 Técnicas de controle e atualização da velocidade do
PSO
Uma série de modificações básicas para o PSO básico têm sido desenvolvidas para
melhorar a velocidade de convergência e a qualidade das soluções encontradas pelo
PSO. Pode-se citar como modificações principais o controle da velocidade e variações
na atualização da velocidade (fator de inércia e coeficiente de constrição).
47
• Limite de velocidade: Existe um problema no PSO básico que é a explosão
do valor de velocidade, principalmente para partículas que estão distantes do
líder e de sua melhor posição. Isto faz com que as partículas ultrapassem os
limites do espaço de busca. Para controlar este problema, as partículas têm
sua velocidade limitada (V
max,j
representa a velocidade máxima permitida na
dimensão j). A velocidade da partícula é reajustada antes de alterar a posição
seguindo a seguinte equação:
v
ij
(t + 1) =
v
ij
(t + 1) se v
ij
(t + 1) < V
max,j
V
max,j
se v
ij
(t + 1) ≥ V
max,j
. (4.9)
O valor de V
max,j
é muito importante pois controla a granularidade da pesquisa,
controlando a velocidade. Usar valores elevados de V
max,j
facilita a exploração
global, porém existe o risco das partículas não focarem a busca em torno de
boas regiões. Valores baixos favorecem a exploração local. Como desvantagem,
talvez o enxame não consiga alcançar locais além das boas regiões que o mesmo
se encontra, isto faz com que o enxame fique preso em mínimos locais. Outra
desvantagem é o aumento do número de iterações para encontrar o mínimo.
Usualmente, o valor do V
max,j
é escolhido como uma fração do espaço de busca
em cada dimensão como mostrado na equação (4.10):
V
max,j
= δ(x
max,j
− x
min,j
), (4.10)
onde x
max,j
e x
min,j
, são respectivamente os valores de máximo e de mínimo
do domínio de x na dimensão j, e δ ∈ (0, 1]. O valor de δ é dependente do
problema, e pode ser encontrado usando técnicas empíricas como por exemplo
validação cruzada.
• Fator de inércia: O peso de inércia foi introduzido por Shi e Eberhart [91]
e é um mecanismo para controlar as habilidades de exploração em busca e
em profundidade também serve para eliminar a necessidade de limitação da
velocidade [33]. A equação de atualização da velocidade com o termo de inércia
é a seguinte:
v
i
(t + 1) = ωv
i
(t) + c
1
r
1
(p
i
(t) − x
i
(t)) + c
2
r
2
(p
ig
(t) − x
i
(t)). (4.11)
O valor de ω é extremamente importante para garantir o comportamento con-
vergente, e para otimizar o balanceamento entre busca em amplitude e busca
em profundidade. Para ω ≥ 1, a velocidade aumenta ao longo da simulação,
acelerando até atingir a velocidade máxima (caso o limite de velocidade esteja
sendo utilizado), fazendo com que o enxame divirja. Para ω < 1, as partículas
desaceleram suas velocidades até chegar a zero (dependendo dos valores dos
coeficientes de aceleração). O valor de ω pode ser fixo ou variável. Abordagens
que alteram dinamicamente os valores de inércia utilizam:
– Ajuste aleatório;
– Decrescimento linear;
48
– Decrescimento não-linear;
– Inércia adaptativa por lógica Fuzzy;
– Inércia crescente.
• Coeficiente de constrição: Clerc desenvolveu uma abordagem muito similar
ao peso de inércia para balancear as habilidades de exploração em largura
e em profundidade, onde as velocidades são inibidas por uma constante χ,
referenciado como fator de constrição [23], [24]. A equação de atualização da
velocidade com o coeficiente de constrição é a seguinte:
v
i
(t + 1) = χ[v
i
(t) + c
1
r
1
(p
i
(t) − x
i
(t)) + c
2
r
2
(p
ig
(t) − x
i
(t))], (4.12)
onde
χ =
2κ
|2 − ϕ −
ϕ
2
− 4ϕ|
, onde ϕ = c
1
+ c
2
. (4.13)
Sob as condições ϕ ≥ 4 e κ ∈ [0, 1], essa abordagem garante a convergência
natural do enxame. Fazendo uso desses valores, o coeficiente de constrição χ
assume um valor entre 0 e 1, induzindo uma redução de velocidade a cada itera-
ção. O parâmetro κ controla diretamente a relação entre busca em amplitude
e busca em profundidade do enxame. Valores κ ≈ 1 são usados com o intuito
de prover um alto grau de busca em amplitude, mas com convergência lenta.
Para se conseguir uma rápida convergência usando busca em pronfundidade,
valores baixos de κ são utilizados (κ < 1).
4.2.3 Estruturas da rede social
Uma característica que guia o PSO para o objetivo desejado é a interação social.
Partículas dentro do enxame aprendem umas com as outras e, com base no conheci-
mento obtido, movem-se para se tornar mais semelhantes a seus “melhores” vizinhos.
A estrutura social do PSO é determinada pela formação de vizinhanças sobrepostas,
onde partículas dentro de uma vizinhança influenciam umas às outras.
Com uma rede social altamente conectada, a maioria dos indivíduos podem se
comunicar uns com os outros. Como consequência, a informação sobre o melhor
membro encontrado é rapidamente transmitido através da rede social. Em termos
de otimização, isso significa uma convergência mais rápida para uma solução do que
em redes menos conectadas. No entanto, para redes altamente conectadas, a alta ve-
locidade de convergência geram uma maior susceptibilidade das partículas a ficarem
presas em mínimos locais, principalmente porque existe aumento da capacidade das
partículas serem influenciadas pelas outras partículas do enxame. Diferentes estru-
turas de redes sociais tem sido desenvolvidas pelo PSO e estudadas empiricamente
[34], [51], [52], [66] das quais pode-se citar:
• Estrela;
• Anel;
49
• Roda;
• Pirâmide;
• Clusters;
• Von Neumann.
As topologias citadas estão ilustradas na figura 4.4.
4.3 Propostas prelimiares de PSO para problemas
multiobjetivo
Algumas abordagens foram propostas para extender o PSO para problemas mul-
tiobjetivos. Nesta seção, são apresentadas algumas abordagens prévias que foram
utilizadas para comparar com a abordagem proposta nesta dissertação.
4.3.1 m-DNPSO
O m-DNPSO foi proposto por Hu e Eberhart et. al, [48]. Neste algoritmo, apenas um
objetivo é otimizado a cada passo de tempo usando um esquema similar à ordenação
lexográfica [25].
Os múltiplos objetivos são divididos em dois grupos: f
1
e f
2
. f
1
é definido como
o objetivo da vizinhança, f
2
é definido como objetivo de otimização. A seleção de
f
1
e f
2
é arbitrária.
Para selecionar o líder social, o algoritmo tem que avaliar a distância da partí-
cula atual para as outras partículas considerando f
1
. Usando esta informação, as
próximas m partículas são escolhidas (m é o tamanho da vizinhança). Finalmente,
o líder social é definido pela melhor solução em termos dos valores de f
2
entre os m
vizinhos.
O líder cognitivo é atualizado apenas quando uma nova solução domina a solução
atual. Um arquivo externo (chamado de “memória externa”) é usado para armazenar
as soluções não-dominadas.
Esta abordagem tem dois grandes inconvenientes:oOrdenação lexográfica tende
a ser útil apenas para dois objetivos e o desempenho pode ser sensível à ordem dos
objetivos.
4.3.2 MOPSO
Este algoritmo foi proposto por Coello Coello et. al, [26]. Ele é baseado em um
arquivo externo em que cada partícula irá depositar sua experiência após cada ite-
ração. O arquivo externo é atualizado considerando um sistema baseado na posição
geográfica da partícula. Esta posição é definida em termos dos valores das funções
objetivo para cada partícula. Nesta abordagem, o espaço de objetivos explorado é
dividido em hipercubos como ilustrado na figura 4.5 . Cada hipercubo recebe um
valor de fitness que depende do número de partículas dentro do hipercubo. Uma
seleção por roleta é usada para escolher um líder para cada partícula do enxame.
Uma vez que um hipercubo é escolhido, uma das partículas dentro do hipercubo é
50
(a) Estrela (b) Anel
(c) Roda (d) Pirâmide
(e) Clusters (f) Von Neumann
Figura 4.4: Exemplos de estruturas da rede social.
aleatoriamente escolhida para ser líder. Esta abordagem usa um operador de muta-
ção nas posições das partículas com os objetivos de acelerar a convergência e fugir
de Pareto fronts locais. Este algoritmo pode ter o desempenho comprometido se o
51
grid não foi bem escolhido para o problema.
Figura 4.5: Representação gráfica do adaptive grid utilizado no MOPSO.
4.3.3 CSS-MOPSO
Este algoritmo foi proposto por Chiu et. al, [22]. Neste algoritmo, não existe um
líder cognitivo, existem dois líderes sociais.
A seleção do g
Best1
é realizada baseada no ângulo θ entre a linha datum, que
conecta membros do arquivo externo e o ponto datum, e a linha que conecta a
partícula e o membro do arquivo externo como mostra a figura 4.6. O membro
do arquivo externo que apresenta o menor ângulo com a enésima partícula irá ser
atribuída como guia local g
Best1
.
A seleção do g
Best2
é feita de acordo com o valor do fitness de um objetivo f
i
escolhido randomicamente em cada iteração. Todas as partículas são ordenadas
pelo seu valor de fitness f
i
. O CSS-MOPSO irá atribuir o g
Best2
usando a seguinte
regra: Para as partículas com índices pares, os membros dos arquivos cujo valores de
fitness f
i
são os mais próximos e maiores irão ser atribuídos a g
Best2
. Para partículas
com índices ímpares, os membros dos arquivos cujo valores de fitness f
i
são os mais
próximos e menores irão ser atribuídos a g
Best2
. A figura 4.7 ilustra a escolha do
g
Best2
.
4.3.4 MOPSO-CDLS
Este algoritmo foi proposto por Tsou et. al, [99] e é baseado na abordagem proposta
por Raquel et. al, [80].
O valor de crowding distance (CD) de uma solução provê uma estimativa da
densidade das soluções em comparação com as outras soluções [29]. A figura 4.8
ilustra o cálculo do crowding distance do ponto i que é uma estimativa do tamanho
do maior cubóide em torno de i sem incluir qualquer outro ponto.
Nesta proposta, o CD é usado como um mecanismo para escolher a partir do
arquivo externo. Existe duas possíveis situações: O líder social da partícula é esco-
lhido aleatoriamente entre as 10% soluções menos densas, se a partícula é dominada
por estas soluções; o líder é aleatoriamente escolhido a partir de todo o arquivo
externo, caso contrário.
52
Figura 4.6: Escolha do g
Best1
para cada partícula.
Figura 4.7: Escolha do g
Best2
para cada partícula em relação ao objetivo f
i
.
O líder cognitivo de cada partícula é atualizado se a nova posição domina o líder
cognitivo atual. Se as soluções são incomparáveis, o líder cognitivo é aleatoriamente
escolhido entre estas duas opções.
Esta abordagem usa um mecanismo de busca local no arquivo externo. Este
mecanismo desempenha um papel na adição de um componente de busca em pro-
fundidade. Esta característica leva à uma rápida convergência com uma menor carga
computacional.
53
Figura 4.8: Cálculo do crowding distance.
4.4 Multiple Objective Particle Swarm Optimi-
zation with Crowding Distance e Roulette
Wheel (MOPSO-CDR)
O algoritmo proposto, que uma das contribuições deste trabalho, é baseado na
abordagem de Tsou et. al, [99]. Contudo, ele incorpora os mecanismos de crowding
distance e roulette wheel para escolher o líder social (gBest) e para evitar um número
excessivo de soluções não dominadas no arquivo externo. Além disso, MOPSO-
CDR apresenta um novo procedimento para atualizar o líder cognitivo (pBest). O
pseudocódigo da abordagem é apresentado no algoritmo 3.
Algoritmo 3: Pseudocódigo para o MOPSO-CDR
Inicialize o enxame;1
Determine os líderes iniciais do arquivo externo;2
Qualifique os líderes por crowding distance;3
enquanto critério de parada não é atingido faça4
para cada partícula faça5
Aplique turbulência [26];6
Selecione líder (usando crowding distance e roleta);7
Atualize velocidade e posição;8
Avalie o fitness;9
Atualize pBest (torneio binário);10
fim11
Atualize líderes do arquivo externo;12
Qualifique os líderes por crowding distance;13
fim14
Resultados finais (arquivo externo);15
4.4.1 Seleção do líder social
Para problemas com múltiplos objetivos, uma boa escolha do líder social (gBest)
é crucial. Ele afeta a capacidade de convergência e a distribuição de soluções não
54
dominadas em torno do Pareto front. Os candidatos para líderes sociais estão no
arquivo externo. Cada partícula tem habilidade para procurar por um guia diferente.
No MOPSO-CDR, o arquivo externo é ordenado por crowding distance antes de
cada iteração. Para cada partícula, o líder social é escolhido aplicando o método da
roleta no arquivo externo. Com isso, soluções em regiões menos densas têm mais
chances de serem escolhidas.
4.4.2 Seleção do líder cognitivo
A regra de atualização do líder cognitivo (pBest) também é importante para a
convergência e eficiência do algoritmo. No MOPSO-CDR, o líder cognitivo de cada
partícula é atualizado se a nova posição da partícula domina o pBest. Se a nova
posição e o pBest são incomparáveis, a escolha é feita usando o arquivo externo. O
algoritmo busca no arquivo externo por soluções com a menor distância euclidiana
para o pBest e para a nova posição. Se a solução mais próxima para da nova posição
que está no arquivo externo está em uma região menos populosa do que a solução
mais próxima do atual pBest no arquivo externo, a nova posição irá ser escolhida
como o novo pBest. Senão o velho pBest continua.
4.4.3 Turbulência
PSO é conhecido por ter alta velocidade de convergência. Contudo, este aspecto
pode ser prejudicial para otimização multiobjetivo, porque um algoritmo baseado
em PSO pode convergir para um falso Pareto front (ótimo local). Portanto, um
operador de mutação pode ajudar a evitar este problema aumentando a capacidade
exploratória das partículas.
O operador de turbulência usado na nossa abordagem é o mesmo utilizado no
MOPSO [26] e ele é aplicada a cada iteração com uma influência limitada. No início,
todas as partículas da população são afetadas pelo operador de mutação. Quando
o número de iterações aumenta, o percentual de partículas afetadas diminui.
4.4.4 Arquivo externo
O objetivo principal do arquivo externo é armazenar soluções não dominadas en-
contradas ao longo do processo de busca.
O algoritmo tem que decidir se uma certa solução pode ser adicionada para o
arquivo ou não. O processo de controle usado no MOPSO-CDR funciona da seguinte
forma: inicialmente soluções não-dominadas são adicionadas para o arquivo externo.
Após cada iteração, soluções não-dominadas do enxame são comparadas com as
soluções do arquivo externo. As soluções candidatas que são não-dominadas pelas
soluções do arquivo externo são adicionadas a ele. Então, as soluções dominadas
são removidas do arquivo externo.
O arquivo externo tem um número máximo de soluções. Se o número é excedido
após o final de cada iteração, soluções em regiões mais populosas são removidas do
arquivo externo (ou seja, as que tiverem menor crowding distance).
55
4.5 Configurações das Simulações
4.5.1 Funções de teste
Zitzler et. al, [108] propuseram um conjunto de funções de teste que podem ser
usadas para comparar abordagens de otimização multiobjetivas. Foram utilizadas
as seguintes funções de teste para comparações ZDT1, ZDT2, ZDT3, ZDT4 e ZDT6.
A função ZDT5 não foi usada porque que ela foi desenvolvida para lidar com strings
de números binários e o PSO não é adequado, a princípio, para este tipo de aplicação.
• Função de teste ZDT1: Este problema tem um Pareto front convexo
f
1
(x
1
) = x
1
, (4.14)
g(x
2
, ..., x
n
) = 1 +
9
n − 1
n
i=2
x
i
, (4.15)
h(f
1
, g) = 1 −
f
1
g
, (4.16)
com n = 30 e x
i
∈ [0, 1].
• Função de teste ZDT2: Este é um Pareto front côncavo complementar ao
do ZDT1
f
1
(x
1
) = x
1
, (4.17)
g(x
2
, ..., x
n
) = 1 +
9
n − 1
n
i=2
x
i
, (4.18)
h(f
1
, g) = 1 −
f
1
g
2
, (4.19)
com n = 30 e x
i
∈ [0, 1].
• Função de teste ZDT3: Este Pareto front consiste de diversas regiões con-
vexas
f
1
(x
1
) = x
1
, (4.20)
g(x
2
, ..., x
n
) = 1 +
9
n − 1
n
i=2
x
i
/(n − 1), (4.21)
h(f
1
, g) = 1 −
f
1
g
−
f
1
g
sin (10πf
1
), (4.22)
com n = 30 e x
i
∈ [0, 1].
56
• Função de teste ZDT4: Este problema tem 21
9
Pareto fronts locais:
f
1
(x
1
) = x
1
, (4.23)
g(x
2
, ..., x
n
) = 1 + 10(n − 1)
n
i=2
(x
2
i
10 cos (4πx
i
)), (4.24)
h(f
1
, g) = 1 −
f
1
g
, (4.25)
com n = 10 e x
1
∈ [0, 1], e x
2
, ..., x
n
∈ [−5, 5].
• Função de teste ZDT6: Este problema tem duas dificuldades causadas
por não-uniformidades do espaço de busca: primeiro, as soluções do Pareto-
ótimo são distribuídas não-uniformimente em torno do Pareto front (o front é
polarizado para soluções que estão próximas de f
1
(x)); segundo, a densidade
de soluções é menor próxima do Pareto front e maior quando distante do front:
f
1
(x
1
) = 1 − exp (−4x
1
) sin
6
(6πx
1
), (4.26)
g(x
2
, ..., x
n
) = 1 + 9

n
i=2
x
i
/ (n − 1)
0.25
, (4.27)
h(f
1
, g) = 1 −
f
1
g
2
, (4.28)
com n = 10 e x
i
∈ [0, 1]
4.5.2 Métricas
Estas são algumas métricas que podem ser usadas para quantificar a qualidade do
Pareto front obtido pelos algoritmos. As seguintes métricas foram usadas neste
trabalho: Hypervolume, Spacing, Maximum spread e Coverage. Cada métrica realça
um diferente aspecto do Pareto front.
• Hypervolume (HV): O Hypervolume foi proposto por Zitzler e Thiele [107].
A fim de explicar este conceito, considere um problema de otimização com dois
objetivos. O Hypervolume é definido pela área no espaço de objetivos coberta
pelo Pareto front (P
∗
a
) (a área abaixo da curva).
Considere o retângulo delimitado pelo ponto (f
1
(x); f
2
(x)) que pertence ao
Pareto front e a origem. Suponha que cada ponto no Pareto front gera um
retângulo no espaço de objetivos. O Hypervolume corresponde pela área for-
mada pela união de todos os retângulos.
É também possível generalizar este conceito para problemas com n-objetivos,
usando a seguinte equação:
57
HV =
i
a
i
| x
i
∈ P
∗
a
, (4.29)
onde x
i
é um vetor não-dominado em (P
∗
a
) e a
i
é o Hypervolume determinado
pelos componentes de x
i
e a origem.
• Spacing (S): Métrica proposta por Schott [83]. O objetivo é medir o espa-
lhamento (distribuição) de soluções não-dominadas por todo o Pareto front.
Esta métrica mede a variância das distâncias entre a solução não-dominada
adjacente e a distância média entre todas as soluções adjacentes, como mostra
a equação (4.30).
S =
1
n − 1
n
i=1
(
¯
d − d
i
)
2
, (4.30)
onde d
i
= min
j
(|f
i
1
(x) − f
j
1
(x)| + |f
i
2
(x) − f
j
2
(x)|), i, j = 1, ..., n,
¯
d é a
distância média entre todas as soluções adjacentes e n é o número de soluções
não-dominadas no Pareto front.
Um valor igual a zero significa que todas as soluções são equidistantes no
Pareto front.
• Maximum Spread (MS): Esta métrica foi proposta pro Zitzler et. al, [107]
e avalia a máxima extensão coberta por soluções não-dominadas no Pareto
front. Em problemas com dois objetivos, o Maximum Spread corresponde à
distância Euclidiana entre as duas soluções mais afastadas.
MS =
M
m=1
(max
n
i=1
f
i
m
− min
n
i=1
f
i
m
)
2
, (4.31)
onde n é o número de soluções no Pareto front e M é o número de objetivos em
um determinado problema. Valores mais altos indicam melhor desempenho.
• Coverage (C): Quando deseja-se comparar dois conjuntos de soluções obtidos
por diferentes otimizadores, pode-se utilizar o Coverage proposto por Zitzler
et. al, [109], [110], [107]. Esta métrica mapeia o par ordenado (A,B) no
intervalo usando a seguinte equação:
C(A, B) =
| {b ∈ B; ∃a ∈ A : a b} |
|B|
. (4.32)
O valor C(A, B) = 1 implica dizer que todas as soluções em B são fracamente
dominadas por A. Por outro lado, C(A, B) = 0 implica que nenhuma das
soluções em B são fracamentes dominadas por A.
Note que ambos C(A, B) e C(B, A) devem ser avaliados, desde que C(A, B)
não é necessariamente igual a 1 − C(B, A).
Se 0 < C(A, B) < 1 e 0 < C(B, A) < 1, então nem A domina fracamente
B nem B domina fracamente A. Pode-se dizer que os conjuntos A e B são
incomparáveis ou que A não é pior que B.
58
4.5.3 Configurações dos Parâmetros
Cada algoritmo tem suas configurações de parâmetros.
No MOPSO, a taxa de mutação é 0,5, o número de divisões do adaptive grid é
30 e o fator de inércia decresce linearmente de 0,4 até 0,0 [26].
No MOPSO-CDLS, σ é igual a 0,2 na operador de busca local e o fator de inércia
decresce linearmente de 0,9 até 0,4 [99].
No m-DNPSO, a função objetivo mais simples é atribuída à f
1
e a mais complexa
para f
2
. m = 10 e a fator de inércia é aleatoriamente gerado a cada iteração no
intervalo [48].
No CSS-MOPSO, o desvio padrão para a mutação Gaussiana é de 0,01 e o fator
de inércia decresce linearmente de 0,9 até 0,4 [22].
MOPSO-CDR usa uma taxa de mutação de 0,5. Apesar do fato de que esta pro-
posta é baseada no MOPSO-CDLS, era de se esperar que o MOPSO-CDR utiliza-se
a mesma inércia que o MOPSO-CDLS e um fator de inércia que decresce linearmente
de 0,4 até 0,0.
Em todos os casos, foram utilizadas 20 partículas, um máximo de 200 soluções
no arquivo externo. 20.0000 avaliações de fitness foram executadas em cada expe-
rimento. O valor dos parâmetros de aceleração cognitiva e social foram de 1,49445.
Cada experimento foi executado 30 vezes. Os resultados são apresentados em termos
de valores médios e desvio padrão.
4.6 Comparativos entre as técnicas MOPSO seleci-
onadas
As tabelas 4.2 a 4.6 mostram os resultados das simulações para todas as técnicas
MOPSO considerando as 4 métricas de desempenho. As figuras 4.9 a 4.13 mostram
os Pareto fronts encontrados pelos algoritmos.
Pode-se notar que nas tabelas 4.2 e 4.3 o MOPSO-CDR e o CSS-MOPSO supera-
ram o m-DNPSO, MOPSO e o MOPSO-CDLS em termos do Hypervolume, Spacing,
e Maximum Spread para os problemas ZDT1 e ZDT2, respectivamente. m-DNPSO
alcançou um Maximum Spread um pouco melhor.
Comparando o Coverage do CSS-MOPSO e MOPSO-CDR, pode-se observar que
a maior parte das soluções não-dominadas do MOPSO-CDR domina as soluções
não-dominadas do CSS-MOPSO, porém nenhuma das soluções não-dominadas do
MOPSO-CDR são dominadas pelas não-dominadas do CSS-MOPSO.
A tabela 4.4 mostra os resultados das simulações para o problema ZDT3. Pode-se
notar que o MOPSO-CDR supera os outros algoritmos em termos de Hypervolume,
Spacing e Coverage. m-DNPSO alcançou um Maximum Spread um pouco melhor.
A tabela 4.5 mostra os resultados das simulações para o problema ZDT4. MOPSO-
CDR supera os outros algoritmos em termos de Hypervolume e Spacing. CSS-
MOPSO alcançou um melhor Maximum Spread. Para os resultados do Coverage,
pode-se concluir que o MOPSO-CDR e MOPSO alcançam os melhores conjuntos
de soluções não-dominadas. Contudo, as soluções não-dominadas do MOPSO-CDR
são um pouco melhor.
A tabela 4.6 mostra os resultados das simulações para o problema ZDT6. MOPSO-
CDR supera os outros algoritmos em termos de Spacing. CSS-MOPSO alcançou um
59
melhor Maximum Spread. MOPSO e m-DNPSO alcançaram os melhores Hypervo-
lume. Em relação aos resultados do Coverage, pode-se concluir que os resultados do
MOPSO-CDR são melhores quando comparado com outros algoritmos.
Tabela 4.2: Valor médio e desvio padrão – ZDT1.
Algoritmo Hypervolume Spacing Max. Spread Coverage Coverage
MOPSO-CDR,* *,MOPSO-CDR
MOPSO 0,36 0,0046 1,425 1,0 0,0
(0,002) (5E-4) (0,005) (0,0) (0,0)
m-DNPSO 0,713 0,0457 1,54 1,0 0,0
(0,053) (0,014) (0,065) (0,0) (0,0)
MOPSO 0,39 0,0042 1,44 1,0 0,0
CDLS (0,003) (6E-4) (0,005) (0,0) (0,0)
CSS 0,34 0,0023 1,42 0,99 0,0
MOPSO (0,002) (1E-4) (0,002) (0,003) (0,0)
MOPSO 0,33 0,0033 1,41 - -
CDR (3E-5) (2E-4) (0,0) - -
Tabela 4.3: Valor médio e desvio padrão – ZDT2.
Algoritmo Hypervolume Spacing Max. Spread Coverage Coverage
MOPSO-CDR,* *,MOPSO-CDR
MOPSO 0,69 0,006 1,396 1,0 0,0
(0,001) (0,001) (0,015) (0,0) (0,0)
m-DNPSO 0,94 0,054 1,29 1,0 0,0
(0,06) (0,017) (0,037) (0,0) (0,0)
MOPSO 0,716 0,006 1,39 1,0 0,0
CDLS (0,0035) (0,001) (0,004) (0,0) (0,0)
CSS 0,674 0,0035 1,41 0,978 0,0
MOPSO (0,001) (7E-4) (8E-4) (0,021) (0,0)
MOPSO 0,66 0,0032 1,41 - -
CDR (3E-5) (1E-4) (0,0) - -
4.7 Conclusões relacionadas à técnica MOPSO-CDR
Neste capítulo foi apresentada uma técnica de Inteligência de Enxames adaptada
para manipular problemas multiobjetivos. Os métodos de escolha do gBest e pBest
desta abordagem, fazem com que o Pareto front encontrado seja bem distribuído.
O operador de mutação do MOPSO acelera a convergência e melhora a capacidade
de busca em amplitude. Outra vantagem desta abordagem é o uso de poucos parâ-
metros, apenas parâmetros do PSO básico são necessários.
O resultado indica que o método proposto pode simultaneamente encontrar so-
luções com baixo Hypervolume, baixo Spacing, bom Maximum Spread e vence as
outras abordagens relacionadas em relação ao Coverage.
60
(a) m-DNPSO (b) CSS-MOPSO
(c) MOPSO (d) MOPSO-CDLS
(e) MOPSO-CDR
Figura 4.9: Pareto front encontrado pelas abordagens para a função ZDT1.
61
(a) m-DNPSO (b) CSS-MOPSO
(c) MOPSO (d) MOPSO-CDLS
(e) MOPSO-CDR
Figura 4.10: Pareto front encontrado pelas abordagens para a função ZDT2.
62
Tabela 4.4: Valor médio e desvio padrão – ZDT3.
Algoritmo Hypervolume Spacing Max. Spread Coverage Coverage
MOPSO-CDR,* *,MOPSO-CDR
MOPSO 0,950 0,005 1,976 1,0 0,0
(0,004) (4E-4) (0,008) (0,0) (0,0)
m-DNPSO 1,296 0,045 2,068 1,0 0,0
(0,088) (0,016) (0,146) (0,0) (0,0)
MOPSO 1,006 0,006 1,988 1,0 0,0
CDLS (0,009) (9E-4) (0,015) (0,0) (0,0)
CSS 0,953 0,003 1,983 0,999 0,0
MOPSO (0,008) (7E-4) (0,006) (8E-4) (0,0)
MOPSO 0,920 0,003 1,967 - -
CDR (1E-4) (2E-4) (2E-5) - -
Tabela 4.5: Valor médio e desvio padrão – ZDT4.
Algoritmo Hypervolume Spacing Max. Spread Coverage Coverage
MOPSO-CDR,* *,MOPSO-CDR
MOPSO 0,631 0,006 1,54 0,51 0,4
(0,526) (0,0014) (0,18) (0,429) (0,49)
m-DNPSO 2,157 0,04 1,94 0,97 0,03
(0,935) (0,037) (0,29) (0,18) (0,18)
MOPSO 4,82 0,005 2,70 1,0 0,0
CDLS (2,174) (9E-4) (0,46) (0,0) (0,0)
CSS 5,38 0,005 2,80 1,0 0,0
MOPSO (2,54) (0,0012) (0,525) (0,0) (0,0)
MOPSO 0,57 0,003 1,52 - -
CDR (0,26) (3E-4) (0,109) - -
Tabela 4.6: Valor médio e desvio padrão – ZDT6.
Algoritmo Hypervolume Spacing Max. Spread Coverage Coverage
MOPSO-CDR,* *,MOPSO-CDR
MOPSO 1,261 0,129 3,180 0,432 0,072
(0,386) (0,122) (1,400) (0,294) (0,073)
m-DNPSO 1,279 0,126 3,203 0,731 0,065
(0,506) (0,108) (1,732) (0,153) (0,064)
MOPSO 1,717 0,186 4,632 0,741 0,102
CDLS (0,519) (0,145) (1,816) (0,150) (0,086)
CSS 2,051 0,234 5,571 0,121 0,013
MOPSO (0,697) (0,153) (2,046) (0,053) (0,049)
MOPSO 1,670 0,088 4,636 - -
CDR (0,300) (0,056) (1,053) - -
63
(a) m-DNPSO (b) CSS-MOPSO
(c) MOPSO (d) MOPSO-CDLS
(e) MOPSO-CDR
Figura 4.11: Pareto front encontrado pelas abordagens para a função ZDT3.
64
(a) m-DNPSO (b) CSS-MOPSO
(c) MOPSO (d) MOPSO-CDLS
(e) MOPSO-CDR
Figura 4.12: Pareto front encontrado pelas abordagens para a função ZDT4.
65
(a) m-DNPSO (b) CSS-MOPSO
(c) MOPSO (d) MOPSO-CDLS
(e) MOPSO-CDR
Figura 4.13: Pareto front encontrado pelas abordagens para a função ZDT6.
Capítulo 5
Um Algoritmo de Roteamento para
Redes Ópticas Usando Redes
Neurais de Hopfield
As atuais abordagens de roteamento para redes ópticas utilizam como algoritmo
central a proposta de Dijkstra [31], principalmente, que é um algoritmo determi-
nístico de complexidade relativamente baixa O([m + n]log n), onde m é o número
de arestas e n o número de nós. Kojic et al., [57], [58] utilizaram como algoritmo
central Redes Neurais de Hopfield (HNN - Hopfield Neural Networks), este que é um
algoritmo não-determinístico e de complexidade dependente da arquitetura compu-
tacional (ver seção 7.1). Estas diferenças entre os algoritmos podem ser exploradas
para satisfazer algumas necessidades das redes ópticas.
Este capítulo apresenta uma nova abordagem para as HNN como algoritmo de
roteamento, considerando como métricas para a função de custo: a distância dos
enlaces e a ocupação dos enlaces que são enviadas ao algoritmo pela entrada de
custo tradicional (matriz de polarização dos neurônios); e um novo conceito de
métrica que é o casamento de comprimentos de ondas entre enlaces adjacentes que
é enviada através da matriz de sinapses dos neurônios. Matriz que este trabalho
considera como uma nova entrada de informações para o algoritmo.
Na seção 5.1 são descritos a nova formulação da matriz de polarização para con-
siderar tanto a distância quanto a carga dos enlaces, o conceito de casamento de
canais, a nova formulação da equação de pesos sinápticos para considerar o casa-
mento de canais entre enlaces adjacentes e a equação de energia de Lyapunov [21]
modificada.
5.1 Modelo baseado na distância, carga dos enlaces
e casamento de canais entre enlaces
O custo que serve como entrada para o algoritmo de roteamento é dado por uma
métrica ou um conjunto de métricas. Métricas como comprimento e utilização de ca-
nais dos enlaces têm alta correlação com o ruído acumulado ao longo do lightpath. O
aumento do comprimento de um enlace implica na necessidade de mais amplificado-
res ópticos na extensão da fibra ou amplificadores ópticos com ganhos maiores para
compensar a atenuação do sinal causada pela maior extensão da fibra. De forma
67
geral, quanto maior o ganho do amplificador ou quantidade de amplificadores, maior
o ruído de emissão espontânea amplificada (ASE - Amplified Spontaneous Emission)
gerado no enlace [77]. O grau de utilização de canais em um enlace também tem
impacto na saturação dos amplificadores e na quantidade de ruído ASE gerado [77].
Devido a estes fatos, pode-se utilizar o comprimento e utilização de canais dos
enlaces como métricas para compor o custo do algoritmo de roteamento, em vez
de utilizar métricas baseadas em informações da camada física, e ainda assim obter
rotas que atinjam os objetivos a serem alcançados.
Como foi citado na subseção 3.3.1, o custo das HNN é mapeado na matriz C
xi
,
que é a matriz de custo dos enlaces. Caso o custo seja composto por mais que uma
métrica, pode-se fazer um pré-processamento das métricas para compor o custo, ou
mapear cada métrica em um termo distinto da equação de polarização da HNN que
está mostrado na equação (3.10).
Algoritmos de roteamento adaptativo geralmente apresentam menor probabili-
dade de bloqueio que algoritmos de roteamento fixo e fixo-alternativo. Uma métrica
que pode ser utilizada como entrada para um algoritmo de roteamento adaptativo é
a carga dos enlaces, porém a distância dos enlaces tem grande importância como in-
formação para roteamento. Para incluir também a questão da utilização dos canais,
é proposta neste trabalho a seguinte equação de polarização externa dos neurônios:
I
xi
= −
µ
1
2
C
xi
(1−δ
xd
δ
is
)−
µ
2
2
ρ
xi
(1−δ
xd
δ
is
)−
µ
4
2
+
µ
5
2
δ
xd
δ
is
−
µ
6
2
K
xi
(1−δ
xd
δ
is
), (5.1)
∀ (x = i) , ∀ (y = i) ,
onde C
xi
é o custo do enlace entre nós x e i, que neste trabalho é utilizado como
distância física do enlace, K
xi
expressa a utilização dos canais do enlace entre nós x
e i e µ
6
é um peso dado ao percentual dos canais ativos no enlace. K
xi
é definido
como:
K
xi
=
λ
a
xi
λ
T
, se ρ
xi
= 0
0, caso contrário
, (5.2)
onde λ
a
xi
e λ
T
são, respectivamente, o número de canais ativos no enlace entre nós
x e i e o número total de comprimentos de onda. λ
a
xi
é definido por:
λ
a
xi
=
λ
T
k=1
ρ
xi,k
, (5.3)
onde ρ
xi,k
é a utilização do canal k do enlace entre nós x e i e é definido por:
ρ
xi,k
=
1, se o comprimento de onda k está ocupado
0, caso contrário
. (5.4)
Para que a HNN continue estável no sentido de Liapunov é importante encontrar
um valor adequado para o parâmetro µ
6
(ver seção 5.2).
Outra inovação que este trabalho propõe é a utilização da informação sobre o
casamento de comprimentos de onda entre enlaces adjacentes. Esta métrica tem seu
valor devido ao fato que ela mensura a afinidade de enlaces com enlaces adjacentes.
Um comprimento de onda casado é um comprimento de onda que está disponível
68
em dois enlaces adjacentes. A figura 5.1 mostra um exemplo da disponibilidade de
comprimentos de onda em uma rede óptica.
Figura 5.1: Exemplo para ilustrar o conceito de casamento de canais em redes
ópticas.
Suponha que para a rede ilustrada na figura 5.1 a atribuição de lightpaths seja
baseada na distância, carga dos enlaces e no casamento de comprimentos de onda
entre enlaces. Caso o nó de borda C deseje estabelecer uma conexão com o nó B,
existem várias possíveis rotas, dentre elas: 3 − 1 − 2 e 3 − 4 − 2. Ambas as rotas
têm distância total de 80 km e cada enlace possui 2 comprimentos de onda livres.
Caso não se utilize o casamento de canal entre enlaces, a escolha da rota para este
exemplo será arbitrária, porém, se a métrica de casamento de canal for utilizada
a escolha não será arbitrária, será baseada na relação entre os enlaces. Entre os
enlaces 3 − 1 e 1 − 2 existe um comprimento de onda em comum livre e entre os
enlaces 3 − 4 e 4 − 2 existem dois comprimentos de onda em comum livres. Se no
projeto de métricas de entrada para o algoritmo de roteamento, encontrar enlaces
que tenham afinidade com outros enlaces seja um aspecto desejável para a escolha
de rotas, então a rota escolhida no exemplo citado será 3 − 4 − 2. Porém se enlaces
que tenham pouca afinidade com outros enlaces é o objetivo do algoritmo, então a
rota escolhida será 3 − 1 − 2.
Um fato importante sobre casamento de canais é que, mesmo que dois enlaces
adjacentes tenham comprimentos de onda livres, pode existir o caso em que seja
impossível estabelecer um lightpath. Isto pode ser demonstrado no caso em que o
nó A deseje estabelecer uma chamada com o nó D, as rotas possíveis são 1 − 4 − 5,
1 − 3 − 4 − 5, 1 − 2 − 4 − 5 e 1 − 2 − 5. Os enlaces 1 − 2 e 2 − 5 possuem
comprimentos de onda livres, porém nenhum comprimento de onda que atenda a
restrição de continuidade de comprimento de onda no lightpath, impossibilitando
a rota 1 − 2 − 5. Por razões similares, também não é possível estabelcer a rota
69
1 − 2 − 4 − 5.
O casamento de canais dos enlaces é uma relação entre enlaces, portanto não pode
ser inserido como custo (ou parte do custo) dos enlaces. Os atuais algoritmos de
roteamento da literatura não permitem incluir esta relação entre canais no cálculo da
rota. Entretanto, a matriz T
xi,yj
da HNN se refere aos pesos sinápticos entre as saídas
e entradas dos neurônios. Como os neurônios no problema de roteamento mapeiam
os enlaces, pode-se utilizar os pesos sinápticos para incluir a relação entre enlaces.
A equação de pesos sinápticos alterada para receber informações dos casamento de
canais entre enlaces é a seguinte:
T
xi,yj
= µ
4
δ
xy
δ
ij
− µ
3
δ
xy
− µ
3
δ
ij
+ µ
3
δ
jx
+ µ
3
δ
iy
+ µ
7
L
xi,yj
, (5.5)
onde µ
7
é um parâmetro e L
xi,yj
é o termo que inclui casamento de comprimentos
de onda entre o enlace xi (entre os nós x e i) e o enlace yj (entre os nós y e j) é e
definido por:
L
xi,yj
=
φ
c
xi,yj
λ
T
, se δ
iy
= 1 e δ
xj
= 0 e ρ
xi
= 0 e ρ
yj
= 0
0, caso contrário
, (5.6)
onde φ
c
xi,yj
é o número de canais casados entre os enlaces xi e yj, onde i e y refereciam
o mesmo nó. φ
c
xi,yj
é definido por:
φ
c
xi,yj
=
λ
T
k=1
ϕ
c
xi,yj,k
, (5.7)
onde ϕ
xi,yj,k
é o casamento do canal k entre os enlaces xi e yj e é definido por:
ϕ
c
xi,yj,k
=
1, se ρ
xi,k
= 0 e ρ
yj,k
= 0
0, caso contrário
. (5.8)
O valor do parâmetro µ
7
pode ser positivo caso se queira priorizar o uso de
enlaces que apresentem alto casamento de canais entre enlaces adjacentes. Caso
seja utilizado um valor negativo para o µ
7
, enlaces que estejam com canais desen-
contrados com seus enlaces adjacentes terão maior chance de fazer parte da rota
escolhida.
A equação de energia de Lyapunov proposta por Ali and Kamoun [3] é modificada
com as alteração propostas anteriomente e fica definida por:
E = E
1
+ E
2
+ E
3
+ E
4
+ E
5
+ E
6
+ E
7
, (5.9)
onde:
E
1
=
µ
1
2
n
x=1
(x,i)=(d,s)
n
i=1
i=x
C
xi
V
xi
, (5.9a)
E
2
=
µ
2
2
n
x=1
(x,i)=(d,s)
n
i=1
i=x
ρ
xi
V
xi
, (5.9b)
E
3
=
µ
3
2
n
x=1
n
i=1
i=x
V
xi
−
n
i=1
i=x
V
ix
2
, (5.9c)
70
E
4
=
µ
4
2
n
x=1
n
i=1
i=x
V
xi
(1 − V
xi
) , (5.9d)
E
5
=
µ
5
2
(1 − V
ds
), (5.9e)
E
6
=
µ
6
2
n
x=1
(x,i)=(d,s)
n
i=1
i=x
K
xi
V
xi
, (5.9f)
E
7
= −
µ
7
2
n
x=1
n
i=1
n
j=1
j=x=i
L
xi,ij
V
xi
V
ij
. (5.9g)
5.2 Arranjo experimental para análise de µ
6
e µ
7
Os parâmetros propostos neste trabalho, µ
6
e µ
7
, assim como os outros parâmetros,
são de extrema importância para o desempenho das Redes Neurais de Hopfield no
problema de roteamento e atribuição de comprimento de onda (RWA - Routing and
Wavelength Assignment). Valores corretos de µ
6
e/ou µ
7
podem fazer com que o
algoritmo de roteamento minimize a quantidade de chamadas perdidas (bloqueadas)
em comparação com o caso em que o modelo de Schuler et al., [88] seja usado como
algoritmo de roteamento.
Para as simulações em redes ópticas foi utilizado o software de simulação SIM-
TON desenvolvido na linguagem C++ [20] com uma modificação para inserção do
algoritmo de roteamento baseado em HNN. O modelo de rede utilizado no simulador
é o modelo descrito na seção 2.6. A topologia de rede utilizada nas simulações foi
uma topologia similar à tradicional NSFNET (backbone americano), ilustrada na
figura 5.2, mas com enlaces menores que os enlaces originais. Esta aproximação foi
feita para analisar o desempenho do algoritmo proposto em cenário metropolitano.
Figura 5.2: Topologia de rede usada nas simulações.
71
Em simulações prévias, para a rede NSFNet (ver figura 5.2) foi detectado que
a HNN era incapaz de encontrar caminhos válidos para determinados pares de nós
fonte e destino. Para que a HNN encontrasse rotas para qualquer par de origem-
destino foi necessário uma alteração no parâmetro µ
3
. Os valores dos parâmetros
utilizados no modelo Schuler et al. foram os apresentados na tabela 5.1.
Tabela 5.1: Valores dos parâmetros da HNN utilizado nas simulações.
Parâmetro Valor
µ
1
950
µ
2
2500
µ
3
2500
µ
4
475
µ
5
2500
A 10
−3
B 10
−3
C 10
−3
∆V
th
10
−5
λ 1
Onde os parâmetros µ
i
s
, ∆V
th
e λ são dados por Ali e Kamoun [3]. A, B e C
foram obtidos experimentalmente.
Na camada óptica foi assumido que para cada enlace existia uma fibra óptica
para cada direção de comunicação (conexões bidirecionais). Assumiu-se que os nós
(OXCs) não possuem a capacidade de conversão de comprimento de onda, ou seja,
um lightpath é transmitido em um comprimento de onda por todo seu percurso.
Para a rede óptica, a alocação de recursos para transferência de informação foi do
tipo comutação por circuito. Na comutação por circuito, o software de controle
primeiro tenta alocar os recursos necessários para estabelecer uma chamada, para
então estabelecer a chamada e começar a enviar os dados [97].
Os valores dos parâmetros da rede óptica utilizados nas simulações são exibidos
na tabela 5.2
O software de simulação utilizado segue o fluxograma ilustrado na figura 5.3
para tentar estabelecer as chamadas solicitadas. Quando uma chamada é solicitada
à rede, primeiro é definida a rota pelo algoritmo de roteamento baseado em HNN.
Em seguida, seleciona-se um comprimento de onda disponível utilizando-se o algo-
ritmo de alocação First fit (FF). Se não houver comprimento de onda livre para a
rota encontrada a chamada é bloqueada, caso contrário, será avaliada a dispersão
para o lightpath pré-estabelecido. Se o alargamento do pulso for maior que o má-
ximo tolerável, então a chamada será bloqueada. Se a dispersão do lightpath estiver
aceitável, será avaliada a OSNR do lightpath. Se a OSNR for menor que a mínima
tolerável, a chamada será bloqueada, caso contrário a chamada será estabelecida na
rota e no comprimento de onda selecionados.
A dispersão é composta pela dispersão do modo de polarização (PMD - Pola-
rization Mode Dispersion) e pela dispersão residual. Os ruídos considerados neste
trabalho para o cálculo da OSNR são: os ruídos de ASE, saturação de ganho e
saturação do ruído ASE além do crosstalk coerente gerado no OXC.
No software de simulação as requisições de chamadas à rede óptica chegam de
forma dinâmica (DLE - Dynamic Lightpath Estabilishment), sendo assim, o processo
72
Tabela 5.2: Valores dos parâmetros da rede óptica utilizado nas simulações.
Parâmetro Valor Definição
P
sat
16 dBm Potência de saturação na saída do amplificador.
P
in
0 dBm Potência de entrada por canal considerada.
OSNR
in
40 dB Relação sinal-ruído óptica na entrada.
OSNR
QoT
23 dB Relação sinal-ruído óptica adotada como critério
de qualidade de transmissão.
B 40 Gbps Taxa de transmissão.
B
o
100 GHz Largura de banda do filtro óptico.
W 36 Número de comprimentos de onda em cada enlace
da rede.
∆f 100 GHz Espaçamento na frequência entre canais.
λ
i
1528.77 nm Menor comprimento de onda pertencente à grade.
λ
0
1450 nm Comprimento de onda cujo valor do coeficiente de
dispersão é igual a zero.
λ
0DCF
1550 nm Comprimento de onda cujo valor do coeficiente de
dispersão é igual a zero na fibra de compensação.
α 0, 2 dB/km Coeficiente de atenuação da fibra.
L
Mx
3 dB Perda do multiplexador.
L
Dx
3 dB Perda do demultiplexador.
L
Sw
3 dB Perda do switch.
F
0
Amp
3, 162 Fator de ruído do amplificador para baixos
valores de potência do sinal (NF = 5 dB).
ε −40 dB Fator de isolação do switch.
A
1
100 Parâmetro de ajuste do modelo da figura de ruído
dinâmica.
A
2
4 W Parâmetro de ajuste do modelo da figura de ruído
dinâmica.
∆λ
T X
0, 02 nm Largura de linha do transmissor.
D
T F
0 ps/km.nm Coeficiente de dispersão cromática da fibra de
transmissão (@1528, 77 nm).
S
T F
45 ps/km.nm
2
Inclinação da curva de dispersão cromática da
fibra de transmissão (@1528, 77 nm).
D
DCF
−110, 0 ps/km.nm Coeficiente de dispersão cromática da fibra de
compensação (@1528, 77 nm).
S
DCF
−1, 87 ps/km.nm
2
Inclinação da curva de dispersão cromática da
fibra de compensação (@1528, 77 nm).
D
P MD
0, 05 ps/km
1/2
Coeficiente de PMD.
δ
%QoT
10 % Alargamento máximo do pulso adotado como
qualidade de transmissão.
Carga [20, 200] Erlang Carga da rede.
de geração de chamadas é um processo estocástico. Para cada chamada, a partir
de todos os nós, é escolhido pseudo-aleatoriamente um nó origem e, a partir dos
nós restantes, é escolhido também de forma pseudo-aleatória, o nó destino. Pode-se
afirmar que todos os nós da rede têm a mesma probabilidade de serem sorteados.
O processo de chegada de solicitação de conexões segue um processo de Poisson: o
73
Figura 5.3: Fluxograma do algoritmo de RWA.
intervalo de tempo entre chamadas é exponencialmente distribuído com média γ e a
duração de cada chamada também segue uma distribuição exponencial, porém com
média 1/H. Com estes parâmetros, pode-se definir a carga L
rede
da rede por [79]:
L
rede
= γH, (5.10)
onde H é o tempo, em média, que a chamada fica ativa e γ é a taxa, em média, com
que as chamadas chegam à rede. Apesar de L
rede
ser adimensional, na literatura é
comum se atribuir a unidade Erlang à carga da rede. A carga da rede é uma medida
de quanto a rede está sendo utilizada. Alta carga significa que existem muitas
conexões em curso através de rede, enquanto que baixa carga significa que existe
um número pequeno de conexões ativas na rede simultaneamente. Os parâmetros γ
e H medem quantitativamente este uso. Se, em média, as conexões ficam por muito
tempo ativas (H grande), obviamente a rede ficará mais ocupada. Se por outro lado
as conexões ficam, em média, por pouco tempo ativas (H pequeno), a rede ficará
menos ocupada. Além disso, se os pedidos de conexão chegam à rede em intervalos
de tempo pequenos (γ grande) a rede ficará mais ocupada do que se os mesmos
chegassem em intervalos de tempo maiores (γ pequeno).
A probabilidade de bloqueio da rede (ver subseção 2.3.6) é uma medida utilizada
para quantificar o desempenho de um algoritmo de roteamento. Um algoritmo de
roteamento também deve fornecer probabilidades de bloqueio em função da carga
da rede (espera-se que a probabilidade de bloqueio da rede seja menor para baixas
74
cargas do que para altas cargas). Por isso, um grafico que é amplamente utilizado
para avaliar o desempenho de algoritmos de roteamento é o da probabilidade de
bloqueio em função da carga na rede [78], [105], [17].
Para verificar a influência positiva da carga da rede no processo de roteamento
utilizando HNN é necessário determinar um valor para o parâmetro µ
6
. Um valor
adequado é importante para manter a HNN estável no sentido de Lyapunov. Na
composição das polarizações dos neurônios como mostrado em (5.1), tanto o termo
relacionado à distância dos enlaces quanto o termo relacionado à carga dos enlaces
compõe o custo dos enlaces. Os parâmetros citados na tabela 5.1 tornam a HNN
estável no sentido de Lyapunov, sendo que o valor do parâmetro (µ
1
) para o termo
relacionado com o custo dos enlaces é 950.
Será considerado na análise realizada na seção 5.3 que na abordagem da HNN
modificada o µ
1
será substituído pelo µ
1
. Para a validação do termo que leva em
conta a carga dos enlaces, decidiu-se que µ
1
+ µ
6
fosse igual a 950, onde µ
1
é o
valor de µ
1
alterado. Desta forma, o custo dos enlaces continuará tendo a mesma
influência na HNN proposta, mantendo a estabilidade da rede.
5.3 Análise da influência de µ
6
e µ
7
Simulações foram efetuadas para observar a influência da carga e da distância dos
enlaces na probabilidade de bloqueio da rede óptica. De forma analítica, diversas
composições de µ
6
e µ
1
foram utilizadas como parâmetros para a HNN. Como µ
1
+
µ
6
= µ
1
, então µ
6
= β.µ
1
e µ
1
= (1 − β).µ
1
, onde β está no intervalo (0, 1], ou
seja µ
6
é um percentual de µ
1
. Os valores de β utilizados nas simulações foram:
(0,05; 0,1; 0,2; 0,35; 0,4; 0,45; 0,5; 0,65; 0,7; 0,8), porém, apenas os resultados mais
representativos foram considerados (0,1; 0,5; 0,7; 0,8).
As simulações foram efetuadas com carga inicial de 20 Erlangs e final de 200
Erlangs, com passo de 5 Erlangs. Em cada ponto de simulação foram efetuadas
20.000 chamadas na rede óptica. Para as simulações, foram utilizados computadores
Intel Core2 Quad CPU Q6600 2, 40 GHz com 4 GB de memória RAM.
Com os resultados obtidos e ilustrados na figura 5.4 é possível perceber que a
probabilidade de bloqueio das configurações propostas para altas cargas da rede
(acima de 120 Erlangs), são iguais ou menores que a da proposta de Schuler et
al. Os resultados mostram também que para β = 0, 7, a HNN modificada tem um
resultado melhor (em termos de probabilidade de bloqueio) em relação à HNN com
os outros valores de β, e para altas cargas tem um resultado melhor que o modelo
de Schuler et al. Pode-se afimar que, para este cenário de simulação, levar em conta
a taxa de utilização de comprimentos de onda no processo de roteamento da HNN,
melhora o desempenho das requisições de chamadas aceitas para a situação em que
a rede óptica esteja com carga elevada.
Os tempos de resposta exibidos na tabela 5.3 mostram que existe um pequeno
ganho de desempenho no tempo de resposta do algoritmo de roteamento com a
inserção do termo que leva em conta a carga da rede óptica. Isto porque a rede
neural converge mais rápido
Com o objetivo de validar do termo que leva em conta o casamento de canais dos
enlaces, também é necessário determinar um valor para o parâmetros µ
7
. Um valor
arbitrário para este parâmetro pode desestabilizar a HNN. Como levar em conta o
casamento de canais como entrada para um algoritmo de roteamento é um conceito
75
Figura 5.4: Probabilidade de bloqueio em função da carga da rede para configurações
da HNN, considerando diferentes valores para µ
6
.
Tabela 5.3: Tempo de simulação para cada requisição de chamada na rede óptica
para diferentes valores de β.
Abordagem Tempo de chamada (s)
HNN (Schuler et al.) 5, 274 × 10
−2
HNN (β = 0, 1) 4, 702 × 10
−2
HNN (β = 0, 5) 4, 14 × 10
−2
HNN (β = 0, 7) 3, 798 × 10
−2
HNN (β = 0, 8) 4, 583 × 10
−2
novo, e os parâmetros do modelo de Schuler et al. não servem como referência
para determinar o parâmetro µ
7
, foi necessário determinar valores experimentais
para validar a influência positiva deste termo. Nos experimentos foram escolhidos
valores positivos e negativos para µ
7
, onde valores positivos implicam em favorecer
a escolha de enlaces (para compor a rota) que estejam com muitos comprimentos de
onda casados, e valores negativos tende a escolher enlaces que estejam com poucos
comprimentos de onda casados. Os valores de µ
7
utilizados nas simulações foram:
(-750, -500, -300, -150, -120, -100, -75, -50, -20, -10, 10, 20, 50, 75), porém apenas
os resultados mais representativos foram considerados (-500, -150, -100, -10, 50,
75). Em cada ponto de simulação foram efetuadas 100.000 chamadas na rede óptica
para cargas entre 20 Erlangs e 140 Erlangs para evitar problemas de significância
estatística. Para os valores de cargas entre 145 e 200 Erlangs foram efetuadas 20.000
chamadas na rede óptica. A figura 5.5 ilustra os resultados das simulações.
Os resultados obtidos e ilustrados na figura 5.5 indicam que para valores positi-
76
Figura 5.5: Probabilidade de bloqueio em função da carga da rede para configurações
da HNN, considerando diferentes valores para µ
7
.
vos de µ
7
, a probabilidade de bloqueio tanto para cargas altas quanto para cargas
baixas (principalmente em cargas baixas), foi maior que a probabilidade de bloqueio
do modelo de Schuler et al. As simulações efetuadas com valores negativos de µ
7
,
mostraram que, até um certo limiar, houve uma considerável diminuição da proba-
bilidade de bloqueio (mais de uma ordem de grandeza para a carga de 80 Erlangs).
Para este cenário, o valor de µ
7
= −150, gerou os melhores resultados em termos
de aceitação das chamadas requisitadas. Então, para este cenário de simulação,
levar em conta poucos comprimentos de onda casados no processo de roteamento
da HNN, implica em uma diminuição da probabilidade de bloqueio, principalmente
para a situação em que a rede óptica esteja com carga baixa. A hipótese para este
comportamento é que o algoritmo favorece a implementação de lightpaths que utili-
zarão alguns recursos da rede óptica de forma que preserve outros recursos necessário
para aumentar a taxa de aceitação de lightpaths no futuro.
A partir dos tempos de resposta exibidos na tabela 5.4 é possivel perceber que
apesar do termo que leva em conta o casamento de comprimentos de onda modificar
a matriz de conexões dos neurônios da HNN, não observa-se variação no tempo de
resposta da HNN.
Com as validações experimentais do termo que leva em conta o ocupação dos
enlaces e do termo que considera o casamento dos comprimentos de onda dos en-
laces, é possível realizar experimentos considerando ambos os termos com o intuito
de verificar a influência dos mesmos na probabilidade de bloqueio. Para este experi-
mento foi decidido fixar o valor de µ
6
e variar o valor de µ
7
. O valor de β escolhido
foi o que fez a HNN apresentar melhor resposta em termos de probabilidade de
bloqueio para maior parte dos valores de carga (β = 0, 7). Os valores de µ
7
utili-
77
Tabela 5.4: Tempo de simulação para cada requisição de chamada na rede óptica
para vários valores de µ
7
.
Abordagem Tempo de chamada (s)
HNN (Schuler et al.) 5, 274 × 10
−2
HNN (µ
7
= −500) 6, 454 × 10
−2
HNN (µ
7
= −150) 5, 406 × 10
−2
HNN (µ
7
= −100) 6, 135 × 10
−2
HNN (µ
7
= −10) 5, 092 × 10
−2
HNN (µ
7
= 50) 4, 818 × 10
−2
HNN (µ
7
= 75) 4, 892 × 10
−2
zados nas simulações foram: (-750, -500, -300, -150, -120, -100, -75, -50, -20, -10,
10, 20, 50, 75), porém apenas os resultados mais representativos foram considerados
(−750, −50, −10, 10, 20 50). Em cada ponto de simulação foram efetuadas 100.000
chamadas na rede óptica para evitar problemas de significância estatística.
Figura 5.6: Probabilidade de bloqueio em função da carga da rede para configurações
da HNN, considerando β = 0, 7 e diferentes valores para µ
7
.
A partir dos resultados obtidos percebe-se que para valores positivos e acima de
um limiar do parâmetro µ
7
, a HNN torna-se instável e não encontra rotas válidas.
Esta situação é ilustrada na figura 5.6 para o caso onde β = 0, 7 e µ
7
= 50. Percebe-
se também que para cargas altas (acima de 110 Erlangs), exceto para o caso citado
anteriormente, todas as configurações da HNN modificada têm melhor desempenho
em termos da probabilidade de bloqueio que o modelo de Schuler et al. (devido
ao termo que leva em conta a ocupação dos enlaces) . Valores negativos para µ
7
e
maiores que um limiar fazem com que a resposta da HNN modificada seja melhor
78
que a HNN de Schuler et al., principalmente para cargas baixas. Para maior parte
das situações simuladas, os parâmetros que obtiveram melhores resultados para a
probabilidade de bloqueio foram β = 0, 7 e µ
7
= −50
Tabela 5.5: Tempo de simulação para cada requisição de chamada na rede óptica
para diferentes configurações de HNN considerando β = 0, 7 e diferentes valores
para µ
7
.
Abordagem Tempo de chamada (s)
HNN (Schuler et al.) 5, 274 × 10
−2
HNN (β = 0, 7 e µ
7
= −750) 6, 21 × 10
−2
HNN (β = 0, 7 e µ
7
= −50) 3, 813 × 10
−2
HNN (β = 0, 7 e µ
7
= −10) 3, 906 × 10
−2
HNN (β = 0, 7 e µ
7
= 10) 4, 182 × 10
−2
HNN (β = 0, 7 e µ
7
= 20) 4, 841 × 10
−2
HNN (β = 0, 7 e µ
7
= 50) 7, 064 × 10
−2
A partir dos tempos de resposta ilustrados na tabela 5.5 é possível perceber que
quando o desempenho das abordagens mostrados na figura 5.6 melhora, o tempo de
resposta diminue.
A figura 5.7 ilustra os melhores resultados obtidos nos experimentos anteriores.
Com os resultados é possível verificar que a HNN modificada tem melhor desempe-
nho que a HNN de Schuler et al. para qualquer combinação de termos considerados
(ocupação de enlaces e casamento de comprimentos de onda). A HNN modificada
considerando a ocupação dos enlaces e sem considerar o casamento de comprimen-
tos de onda tem um melhor desempenho para o cenário utilizado para cargas acima
de 135 Erlangs. Pode-se concluir também que a HNN modificada considerando o
casamento de comprimentos de onda e sem levar em conta a ocupação dos enlaces
tem uma menor probabilidade de bloqueio que as outras abordagens para cargas
abaixo de 135 Erlangs. A abordagem que alcançou uma melhor relação para a pro-
babilidade de bloqueio em todas as cargas foi a que considerou tanto a ocupação
dos enlaces quanto o casamento de comprimentos de onda.
Tabela 5.6: Tempo de simulação para cada requisição de chamada na rede óptica
para os melhores casos de configurações da HNN.
Abordagem Tempo de chamada (s)
HNN (Schuler et al.) 5, 274 × 10
−2
HNN (β = 0, 7) 3, 798 × 10
−2
HNN (µ
7
= −150) 5, 406 × 10
−2
HNN (β = 0, 7 e µ
7
= −50) 3, 813 × 10
−2
A partir dos tempos de simulação para cada chamada na rede óptica ilustrados
na tabela 5.6, observa-se que, utilizar o termo que leva em conta a carga dos enla-
ces, gera uma pequena melhora no tempo de resposta do algoritmo de roteamento.
Também é possível observar que o termo que leva em conta o casamento de canais
não tem influência significativa no tempo de resposta do algoritmo.
79
Figura 5.7: Probabilidade de bloqueio em função da carga da rede para HNN con-
siderando os melhores casos.
Para verificar o desempenho da HNN proposta, comparou-se a melhor configu-
ração encontrada (HNN (β = 0, 7 e µ
7
= −50)) com abordagens de roteamento
conhecidos na literatura e discutidos na seção 2.5.2, são eles: o SP que usa como
função de custo a distância entre enlaces, o MH que usa como função de custo a
ocupação do enlace, a HNN de Schuler et al. que usa como função de custo a dis-
tância entre enlaces e Optical Signal to Noise Ratio Routing (OSNR-R) que usa a
OSNR
de saida
do lightpath como função de custo.
A figura 5.8 mostra a probabilidade de bloqueio em função da carga da rede
para as cinco abordagens de roteamento. Pode-se observar a partir dos resultados
ilustrados na figura 5.8 que a abordagem de Schuler et al. tem um desempenho
similar mas não idêntico ao SP. Isto deve-se ao fato que, apesar de ambos utilizarem
as mesmas métricas de custos, as HNN tem a propriedade de encontrar diferentes
rotas para um mesmo conjunto de custos, nó origem e nó destino. O desempenho
do algoritmo MH para este cenário de rede não foi satisfatório. O algoritmo que
obteve melhor desempenho foi o OSNR-R com probabilidade de bloqueio menor que
os outros algoritmos para todos os pontos de simulação. A HNN proposta com a
configuração β = 0, 7 e µ
7
= −50 obteve melhores resultados que os algoritmos MH,
SP e HNN (Schuler et al.), validando para este cenário de rede a aplicabilidade das
Redes Neurais de Hopfield como algoritmo de roteamento e confirmando a influência
dos termos que considera a carga dos enlaces e o casamento de canais entre enla-
ces. Porém, a abordagem proposta utilizando esta metodologia para escolha dos
parâmetros β e µ
7
não mostrou-se concorrente ao algoritmo OSNR-R.
Os tempos de resposta das abordagens de roteamento estão ilustrados na tabela
5.7. Os tempos de execução para cada chamada das abordagens MH e SP é da
80
Figura 5.8: Probabilidade de bloqueio em função da carga da rede para diferentes
abordagens de roteamento.
ordem de dezenas de microssegundos, devido a suas métricas simples e ao algoritmo
de Dijkstra que é eficiente para a arquitetura considerada. O algoritmo OSNR-R
tem tempo de resposta na ordem de centenas de microssegundos, porque utiliza o
algoritmo de Dijkstra e cálculo da função de custo requer um tempo considerável. As
abordagens de roteamento baseadas nas HNN têm tempo de resposta na ordem de
dezenas de milissegundos, com uma pequena vantagem para a abordagem proposta
com a configuração β = 0, 7 e µ
7
= −50. O tempo de resposta superior destas
abordagens em comparação ao das outras abordagens, deve-se ao tempo necessário
para que a rede neural realmente convirja e encontre uma rota. Porém este tempo de
processamento pode ser reduzido utilizando uma arquitetura adequada para cálculos
matriciais ou paralelos (ver seção 7.1).
Tabela 5.7: Tempo de simulação para cada requisição de chamada na rede óptica
para diferentes abordagens de roteamento.
Abordagem Tempo de chamada (s)
SP 5, 405 × 10
−5
HNN (β = 0, 7 e µ
7
= −50) 3, 813 × 10
−2
MH 3, 972 × 10
−5
OSNR-R 7, 729 × 10
−4
HNN (Schuler et al.) 5, 274 × 10
−2
81
Capítulo 6
Otimização Multi-Objetiva usando
Inteligência de Enxames do
algoritmo de Roteamento baseado
em Redes Neurais de Hopfield
adaptado para Redes Ópticas
Neste capítulo é feita uma otimização multiobjetiva das Redes Neurais de Hopfield
(HNN - Hopfield Neural Networks) utilizando Multiple Objective Particle Swarm Op-
timization with Crowding Distance and Roulette Wheel (MOPSO-CDR) visando en-
contrar um balanceamento entre minimização da probabilidade de bloqueio e tempo
de convergência médio do algoritmo de roteamento baseado em HNN.
Como a HNN é uma abordagem baseada em uma heurística, o caminho encon-
trado (saída do algoritmo) não necessariamente será o caminho de menor custo para
a métrica dada. Dependendo da aplicação, este fato pode ser uma desvantagem,
porém a capacidade de encontrar outros caminhos (não o melhor), pode ser útil
para encontrar caminhos que tenham compromisso em otimizar uma determinada
característica que não seja fácil de mapear diretamente.
6.1 Otimização de parâmetros utilizando MOPSO-
CDR
Para encontrar os coeficientes das HNN aplicadas ao problema de RWA para o ce-
nário de rede utilizado na seção 5.2, com o intuito de minimizar a probabilidade de
bloqueio e reduzir o tempo médio de convergência da HNN, foi utilizado a técnica
de Inteligência Computacional de Enxames (CSI - Computational Swarm Intelli-
gence) MOPSO-CDR descrita no capítulo 4. O MOPSO-CDR foi acrescentado ao
simulador SIMTON [20] para determinar os parâmetros utilizados pela HNN. Fo-
ram consideradas duas funções objetivo: a probabilidade de bloqueio da rede óptica
para o cenário citado e número médio de iterações necessários para a convergên-
cia da HNN (apenas para as situações onde a HNN encontrou rotas válidas). Os
parâmetros ilustrados na tabela 6.1 foram mapeados nas dimensões das partículas
82
do MOPSO-CDR. A tabela 6.1 também ilustra os intervalos dos valores iniciais
1
,
posições e velocidades. Utilizando a lógica proposta por Ali and Kamoun [3] para
o cálculo dos parâmetros µ
i
s
foram determinados alguns dos intervalos dos espaços
de busca e das velocidades das dimensões das partículas. Os limites estáticos foram
definidos experimentalmente. Como os parâmetros A, B e C podem assumir valores
de diferentes ordens de grandeza ([10
−5
; 10
−2
]) e a equação de atualização da veloci-
dade do PSO foi concebida para cálculos de valores na mesma ordem da grandeza.
Então, para evitar problemas de má distribuição das partículas, decidiu-se mapear
nas respectivas dimensões das partículas os índices , η e υ que são expoentes para
os cálculos: A = 10
−5
, B = 10
η−5
e C = 10
υ−5
. Como os índices são da mesma
ordem de grandeza, tornam-se adequados para o MOPSO-CDR.
Tabela 6.1: Intervalos das posições e velocidades assumidas pelas partículas do
MOPSO-CDR para cada dimensão.
Dimensão Valores iniciais Intervalo de posição Intervalo de velocidade
µ
1
[300; µ
2
] [300; µ
2
] [−1350; 1350]
µ
2
e µ
5
[1000; 2700] [1000; 2700] [−1350; 1350]
µ
3
µ
4
2, 0
; µ
2
µ
4
2, 0
; µ
2
[−1350; 1350]
µ
4
[100; µ
1
] [100; µ
1
] [−1350; 1350]
µ
6
[0; 200] [0; 2700] [−1350; 1350]
µ
7
[−200; 200] [−2700; 2700] [−1350; 1350]
[0; 3] [0; 3] [−1, 5; 1, 5]
η [0; 3] [0; 3] [−1, 5; 1, 5]
υ [0; 3] [0; 3] [−1, 5; 1, 5]
λ [1; 5] [1; 5] [−2; 2]
A busca dos parâmetros foi feita para o cenário citado com uma carga de 115
Erlangs. Neste ponto, a rede tem valores similares para bloqueio por indisponibili-
dade de comprimentos de onda, bloqueio por alargamento de pulso acima do limiar
e bloqueio por OSNR abaixo do limiar. Desta forma, o MOPSO-CDR poderá oti-
mizar a HNN para minimizar também a probabilidade de bloqueio do três tipos de
bloqueio de forma equivalente. O número de chamadas da rede óptica foi de 10.000.
Para acelerar o processo de convergência do MOPSO-CDR, foi otimizado o pro-
cesso do cálculo das funções objetivos. Se após 10% chamadas na rede óptica (1.000
chamadas), a HNN não encontrar nenhuma rota válida, é encerrado o processo de
cálculo das funções objetivos para a partícula corrente na iteração corrente.
Foram realizadas 4 simulações simultâneas: otimizando todos os parâmetros da
HNN, otimizando os parâmetros da HNN exceto µ
6
, otimizando os parâmetros da
HNN exceto µ
7
e otimizando os parâmetros do modelo de Schuler et al., [88].
A tabela 6.2 ilustra os parâmetros utilizados no algoritmo MOPSO-CDR.
A figura 6.1 ilustra a evolução do Pareto front para a simulação considerando a
otimização de todos os parâmetros da HNN. O conjunto de pontos para um dada
iteração, representa o arquivo externo naquela iteração. Cada ponto representa uma
1
Em simulações prévias, observou-se que utilizar os valores pseudo-aleatórios nos intervalos
citados tornava a convergência impraticável, então decidiu-se utilizar para as partículas pares do
enxame, valores de parâmetros obtidos experimentalmente.
83
Tabela 6.2: Valores dos parâmetros do MOPSO-CDR.
Parâmetro Valor Definição
P 20 Número de partículas.
S
EA
200 Número máximo de soluções do arquivo externo.
I 200 Número de iterações.
c
1
e c
2
1, 49445 Coeficientes de aceleração cognitivo e social.
ω [0, 4; 0, 32] Inércia (linearmente decrescente).
d 10 Número de dimensões das partículas.
o 2 Número de objetivos.
MR 0, 5 Taxa de mutação.
solução do arquivo externo corrente. Uma solução contêm os parâmetros otimizados
da HNN. Na 10
a
iteração, o arquivo externo já contêm soluções com configurações
para HNN com probabilidade de bloqueio próximas as das configurações apresen-
tadas na 200
a
iteração. Observa-se regiões com pequena diversidade de soluções.
Isto pode estar sendo causado por um quantidade de épocas insuficiente para um
convergência adequada do algoritmo MOPSO-CDR.
Figura 6.1: Evolução do Pareto front para a simulação considerando a otimização
de todos os parâmetros da HNN modificada.
A tabela 6.3 exibe os valores das métricas de convergência e diversidade para a
simulação considerada. Para este problema, quanto menor o valor do Hypervolume
mais próximo tende estar o Pareto front do Pareto real. Apesar do Hypervolume ser
utilizado também como um critério de convergência, é possível observar um aumento
do valor do mesmo entre a 1
a
e a 10
a
iteração, isto é explicado pelo aumento da
amplitude do Pareto front como mostram os valores do Maximum Spread. Observa-
se também uma estabilidade nos valores das métricas entre a iteração 150 e a 200.
84
Isto é um sinal de que ou Pareto front está próximo do Pareto real ou está preso em
um Pareto front local. A baixa diversidade das soluções sobre o front é mostrado
pelos valores relativamente elevados do Spacing.
Tabela 6.3: Valores das métricas de convergência e diversidade para a simulação
considerando a otimização de todos os parâmetros da HNN modificada.
Iteração Hypervolume Spacing Maximum Spread
1 20,578 36,467 109,567
10 33,407 11,346 186,781
20 32,922 28,434 190,743
50 28,689 13,307 174,222
100 29,507 11,535 174,222
150 12,624 14,904 174,866
200 12,408 15,766 175,211
A figura 6.2 ilustra a evolução do Pareto front para a simulação considerando a
otimização dos parâmetros da HNN exceto µ
6
. Observa-se uma convergência mais
rápida que a da simulação anterior. Uma suposição para este fato é o menor número
de dimensões das partículas (9). É possivel notar também uma melhor distribuição
das soluções sobre o Pareto front em comparação com a simulação anterior. Supõe-se
também que seja devido ao menor número de dimensões.
Figura 6.2: Evolução do Pareto front para a simulação considerando a otimização
dos parâmetros da HNN modificada exceto µ
6
.
Os valores das métricas de convergência e diversidade para a simulação conside-
rada estão ilustradas na tabela 6.4. A partir dos valores do Hypervolume dos fronts
85
considerados, é possível perceber que, a otimização aparentemente não chegou a con-
vergir. Porque entre a 150
a
iteração e 200
a
houve uma significante variação do valor
o Hypervolume. A relativamente boa diversidade é observada a partir dos valores de
Spacing.
Tabela 6.4: Valores das métricas de convergência e diversidade para a simulação
considerando a otimização dos parâmetros da HNN modificada exceto µ
6
.
Iteração Hypervolume Spacing Maximum Spread
1 23,569 - 30,718
10 23,464 3,231 40,968
20 21,102 3,726 51,836
50 16,714 15,288 108,963
100 17,679 9,026 145,867
150 17,962 11,057 202,789
200 13,914 4,752 135,155
Os resultados obtidos e ilustrados na figura 6.3 mostram a evolução do Pareto
front para a simulação considerando a otimização dos parâmetros da HNN exceto µ
7
.
Entre a 100
a
e a 150
a
iteração é possível observar uma total mudança das soluções
com probabilidade de bloqueio abaixo de 10
−2
. Uma possível explicação é que o
Pareto front da 100
a
iteração (e os fronts das iterações anteriores e possivelmente
algumas posteriores) seja um Pareto local. Na 200
a
iteração, a solução que fez a
HNN ter a menor probabilidade de bloqueio, tem um número médio de iterações
relativamente baixo, assim como boas soluções para otimização levando em conta
todos os parâmetros. Isto pode ser explicado pelo uso de termo que leva em conta
a carga dos enlaces, que na seção 5.3 foi observado um ganho no tempo de resposta
da HNN em comparação a configurações que não utilizam este termo.
A partir dos valores ilustrados na tabela 6.5, observa-se baixos valores para o
Hypervolume. A explicação é que para esta simulação, as soluções com relativamente
alta probabilidade de bloquerio têm de uma forma geral um baixo número médio
iterações para a HNN. Observa-se também uma diminuição gradual dos valores
do Spacing e uma estabilização dos valores do Hypervolume, dando uma possível
indicação de que o Pareto front está próximo do Pareto real.
Tabela 6.5: Valores das métricas de convergência e diversidade para a simulação
considerando a otimização dos parâmetros da HNN modificada exceto µ
7
.
Iteração Hypervolume Spacing Maximum Spread
1 9,636 - 47,940
10 18,328 29,462 198,13
20 15,227 22,650 255,602
50 15,024 18,283 396,849
100 12,288 22,200 254,807
150 10,955 7,234 78,997
200 10,620 2,642 78,997
A figura 6.4 ilustra a evolução do Pareto front para a simulação considerando a
86
Figura 6.3: Evolução do Pareto front para a simulação considerando a otimização
dos parâmetros da HNN modificada exceto µ
7
.
otimização dos parâmetros da HNN do modelo Schuler et al. Observa-se uma rápida
convergência do algoritmo MOPSO-CDR. Novamente, a suposição para este fato é
o menor número de dimensões das partículas (8). Também é possível observar uma
boa distribuição das soluções sobre o Pareto front.
A partir dos valores das métricas de convergência ilustrados na tabela 6.6 é
possível observar os valores decrescentes do Hypervolume e do Spacing (para os três
últimos fronts) indicando uma possível convergência.
Tabela 6.6: Valores das métricas de convergência e diversidade para a simulação
considerando a otimização dos parâmetros da HNN do modelo de Schuler et al.
Iteração Hypervolume Spacing Maximum Spread
1 2,747 - -
10 24,426 7,900 68,074
20 19,776 1,562 69,722
50 15,698 3,367 79,442
100 13,420 17,428 158,707
150 12,102 15,121 159,533
200 11,684 5,527 160,508
A figura 6.5 ilustra os Paretos fronts da iteração final das 4 simulações efetuadas.
É possível perceber que a simulação que encontrou a melhor solução em termos de
minimização da probabilidade de bloqueio foi a que considerou todos os parâme-
tros da HNN. Pode-se observar que as regiões sombreadas são as mais povoadas de
soluções.
87
Figura 6.4: Evolução do Pareto front para a simulação considerando a otimização
dos parâmetros da HNN do modelo de Schuler et al.
Figura 6.5: Paretos fronts da iteração final das simulações efetuadas.
A tabela 6.7 exibe o resultado das comparações dos entre o front da última
iteração da simulação que considera todos os parâmetros da HNN e os fronts da
última iteração das outras simulações. Pode-se afimar que nenhum front domina o
88
front da simulação com todos os parâmetros e que este mesmo front não domina
algum outro.
Tabela 6.7: Valor do Coverage entre o front da última iteração da simulação que
considera todos os parâmetros da HNN e os fronts da última iteração das outras
simulações.
Abordagem Coverage((µ
6
, µ
7
),*) Coverage(*,(µ
6
, µ
7
))
µ
6
= 0, µ
7
0,6 0,086
µ
6
, µ
7
= 0 0,181 0,478
µ
6
= 0, µ
7
= 0 0,272 0,521
A partir das soluções dos fronts da última iteração, escolheu-se para cada si-
mulação efetuada, uma solução que tinha um bom compromisso em minimizar a
probabilidade de bloqueio e minimizar o número de médio de iterações para a con-
vergência da HNN. As soluções escolhidas estão exibidas na tabela 6.8.
Tabela 6.8: Valores dos parâmetros da HNN utilizado nas simulações.
Parâmetro HNN (µ
6
, µ
7
) HNN (µ
6
= 0 µ
7
) HNN (µ
6
µ
7
= 0) HNN (µ
6
= µ
7
= 0)
µ
1
363, 641 300 300 300
µ
2
2462, 73 2254, 24 2100, 8 1848, 29
µ
3
1763, 71 1746, 02 1501, 55 1729, 25
µ
4
259, 757 240, 112 300 195, 081
µ
5
2462, 73 2254, 24 2100, 8 1848, 29
µ
6
971, 086 0 724, 826 0
µ
7
38, 9139 73, 989 0 0
A 1, 265 × 10
−4
4, 978 × 10
−5
3, 137 × 10
−5
5, 068 × 10
−5
B 5, 53 × 10
−4
3, 773 × 10
−4
8, 899 × 10
−4
9, 006 × 10
−4
C 1 × 10
−3
7, 395 × 10
−4
1, 550 × 10
−3
1, 152 × 10
−3
λ 3, 283 2, 866 2, 5 2, 110
P B 4, 7 × 10
−3
4, 8 × 10
−3
4, 8 × 10
−3
4, 9 × 10
−3
N
o
médio de 93, 186 141, 413 85, 816 166, 198
iterações
A figura 6.6 mostra a probabilidade de bloqueio em função da carga da rede para
as configurações da HNN com os parâmetros otimizados. É possível perceber que
todas as configurações consideradas da HNN tiveram resultados estatisticamente
idênticos, ou seja, para este cenário de rede, com o número de iterações utilizados
no MOPSO-CDR, a arquitetura da HNN utilizada não foi um fator determinante
na minimização da probabilidade de bloqueio. Os parâmetros já existentes da HNN
podem ter sido suficientes para obter a minimização da probabilidade de bloqueio
alcançada neste cenário. Em trabalhos futuros, outros cenários de rede e um maior
número de iterações serão considerados para que seja possível uma afirmação sobre
influência da arquitetura utilizada.
A partir dos tempos de simulação para cada chamada na rede óptica ilustrados
na tabela 6.9, observa-se que, para os parâmetros otimizados aplicados ao modelo
de Schuler et al. minimizarem a probabilidade de bloqueio para o mesmo patamar
89
Figura 6.6: Probabilidade de bloqueio em função da carga da rede para as configu-
rações otimizadas da HNN.
das outras arquiteturas, torna-se necessário um maior tempo de resposta da HNN.
É possível observar também que, as arquiteturas que utilizam o termo que leva em
conta a carga da rede, têm uma resposta um pouco mais eficiente quando comparado
com as outras arquiteturas.
Tabela 6.9: Tempo de simulação para cada requisição de chamada na rede óptica
para as quatro possíveis abordagens de HNN.
Abordagem Tempo de chamada (s)
HNN (µ
6
= µ
7
= 0) 6, 075 × 10
−2
HNN (µ
6
= 0, µ
7
) 5, 482 × 10
−2
HNN (µ
6
, µ
7
= 0) 4, 56 × 10
−2
HNN (µ
6
, µ
7
) 4, 961 × 10
−2
A figura 6.7 ilustra os resultados da probabilidade de bloqueio em função da
carga da rede para a abordagem da HNN proposta com os parâmetros otimizados
e para outras abordagens consolidadas pela literatura. É possível observar que a
abordagem proposta obteve resultados estatiscamente idênticos ao da abordagem
Optical Signal to Noise Ratio Routing (OSNR-R) e resultados melhores que os das
outras abordagens. Observa-se também que para este cenário de rede para cargas
na rede óptica entre 90 e 110 Erlangs a redução na probabilidade de bloqueio na
comparação da abordagem proposta com a abordagem de Schuler et al. com os
parâmetros ilustrados na tabelas 5.1 é superior a uma ordem de grandeza.
Os tempos de resposta das abordagens de roteamento estão ilustrados na tabela
90
Figura 6.7: Probabilidade de bloqueio em função da carga da rede para diferentes
abordagens de roteamento.
6.10. Pode-se observar uma pequena melhora no tempo de resposta da abordagem
proposta com os parâmetros otimizados em comparação com a abordagem de Schuler
et al. com os parâmetros ilustrados na tabelas 5.1.
Tabela 6.10: Tempo de simulação para cada requisição de chamada na rede óptica
para diferentes abordagens de roteamento.
Abordagem Tempo de chamada (s)
SP 5, 405 × 10
−5
MH 3, 972 × 10
−5
HNN (Schuler et al.) 5, 274 × 10
−2
HNN (µ
6
, µ
7
) 4, 961 × 10
−2
OSNR-R 7, 729 × 10
−4
91
Capítulo 7
Conclusão
Neste trabalho foram aprofundadas as alternativas para tópicos importantes referen-
tes às redes ópticas: algoritmos de roteamento e atribuição de comprimento de onda
(RWA - Routing and Wavelength Assignment). Como foi visto, estes algoritmos têm
o objetivo de minimizar o desperdício dos recursos das redes ópticas e maximizar
a quantidade e qualidade das conexões estabelecidas. Para o adequado funciona-
mento dos algoritmos de RWA, são utilizadas informações do atual estado da rede
óptica. Estas informações podem ser obtidas a partir dos efeitos ópticos oriundos
da camada física. Porém, algoritmos que consideram estes efeitos têm alto custo
computacional, pois têm que calcular equações complexas que modelam a camada
óptica durante o processo de definição de rotas.
A proposta desta dissertação foi descrever uma nova abordagem de roteamento
para redes ópticas transparentes baseada nas Redes Neurais de Hopfield (HNN -
Hopfield Neural Networks) que foi uma segunda contribuição desta dissertação. Esta
abordagem utilizou como métricas para compor a função de custo o comprimento
dos enlaces, a ocupação de comprimentos de onda dos enlaces e o casamento de com-
primentos de onda entre enlaces adjacentes. O cálculo da função de custo proposta
no algoritmo utilizando estas métricas requer baixo custo computacional.
Os modelos das HNN aplicados ao problema do roteamento, assim como os outros
algoritmos de roteamento existentes na literatura não são capazes de considerar o
novo conceito de métrica que considera o casamento de comprimentos de onda entre
canais. Devido a isto, tornou-se necessário modificar um dos modelos existentes
das HNN. O modelo escolhido como base foi o de Schuler et al., [88] devido a
menor complexidade da equação de atualização dos neurônios. Para que o modelo
proposto pudesse considerar o casamento de comprimentos de onda entre canais e
as outras métricas, tornou-se necessário modificações nas formulações das matrizes
de polarização e sinapses dos neurônios.
Para isto, foram inseridos novos termos nas equações de energia e atualização dos
neurônios da HNN. Tais termos exigiam parâmetros multiplicativos que precisavam
ser definidos. Com o intuito de validar as equações foi realizada uma análise dos
parâmetros µ
6
e µ
7
. Simulações foram efetuadas em uma topologia similar à NSF-
NET utilizando um modelo de rede óptica consolidado. Os resultados da análise
mostraram que as modificações propostas nas formulações influenciaram de forma
positiva na diminuição da probabilidade de bloqueio para o cenário considerado sem
impor um aumento considerável no custo computacional.
Os valores dos termos definidos de forma empírica, não foram suficientes para
92
que fizesse a HNN atingir o desempenho desejado. Para definir os parâmetros pro-
postos e outros coeficientes da HNN com o intuito de minimizar a probabilidade
de bloqueio e reduzir o tempo médio de convergência da HNN tornou-se também
necessário a utilização de uma técnica de otimização multi-objetiva. Técnicas ba-
seadas em Inteligência Computacional de Enxames (CSI - Computational Swarm
Intelligence) podem ser utilizadas para buscar e definir este conjunto de parâme-
tros. A técnica aplicada foi Multiple Objective Particle Swarm Optimization with
Crowding Distance and Roulette Wheel (MOPSO-CDR) que é uma nova aborda-
gem proposta e validada nesta dissertação baseada no Particle Swarm Optimization
(PSO) para encontrar soluções para problemas de otimização multiobjetivo, sendo
esta uma terceira contribuição deste trabalho.
A abordagem de otimização multi-objetiva proposta é uma modificação de uma
proposição consolidada na literatura. As modificações são: incorporação dos meca-
nismos de crowding distance e roulette wheel na escolha do líder social (gBest) e um
novo procedimento na atualização do líder cognitivo (pBest). Estas modificações fi-
zeram com que os Paretos fronts encontrados fossem bem distribuídos. Assim como
o uso de poucos parâmetros necessários para a execução do algoritmo.
Um conjunto de simulações foi efetuado com variações na arquitetura da HNN
com o intuito de encontrar um conjunto de soluções que tinham como compromisso
minimizar a probabilidade de bloqueio e reduzir o tempo médio de convergência da
HNN. Cada solução representava um conjunto de parâmetros para a HNN. Foi rea-
lizada uma análise da evolução das simulações e constatou-se que a quantidade de
iterações não chegou a ser suficiente para gerar Paretos fronts com uma quantidade
de soluções desejável, assim como soluções bem distribuídas. Porém, as soluções
encontradas até então, fizeram com que as arquiteturas das HNN utilizadas obti-
vessem desempenhos equivalentes ao da abordagem Optical Signal to Noise Ratio
Routing (OSNR-R) [62].
7.1 Complexidade do algoritmo
A complexidade do algoritmo é dependente da arquitetura utilizada:
• Arquitetura sequencial - a complexidade é da ordem de n
3
, onde n é o número
de nós da rede de comunicação. Isto porque cada neurônio (n
2
) deve ser com-
putado por vez, e cada neurônio utiliza informações de neurônios adjacentes
(n) a cada iteração.
• Arquitetura paralela - Supõe-se que a complexidade seja da ordem de n, já
que as operações de atualização dos neurônios seriam feitas em núcleos distin-
tos, porém a complexidade do termo referente ao somatório dos pesos pelas
entradas dos outros neurônios (equação 3.18) não poderia ser simplificada (n).
Isto mostra que se a HNN for paralelizada, o tempo de convergência pode dimi-
nuir consideravelmente. Com isto, as HNN podem apresentar tempo para cálculo
de rota comparável aos outros algoritmos.
93
7.2 Trabalhos Futuros
A abordagem MOPSO-CDR não obtêm os melhores resultados para a função de teste
ZDT6 e eventualmente é superada na função de teste ZDT4. Melhorias no algoritmo
podem ser feitas com um estudo das variações do PSO, valores dos parâmetros do
PSO e dos parâmetros referentes à otimização multi-objetiva. Simulações com uma
variedade maior de técnicas e funções de teste podem reforçar os benefícios atingidos
pelas conclusões obtidas a partir dos experimentos realizadas neste trabalho.
Para o algoritmo de roteamento baseado em HNN proposto, como melhorias
pode-se citar:
• Simulações para outros cenários de redes, para confirmar os benefícios da abor-
dagem proposta em contrapartida ao modelo de Schuler et al. e outras abor-
dagens.
• Simulações considerando outros efeitos de penalidades da camada óptica como
mistura de quatro ondas (FWM - Four Wave Mixing).
• Dividindo a rede óptica em camadas, uma para cada comprimento de onda,
atribuindo uma HNN para cada camada, cada uma teria um valor de energia
associado que seria utilizado no processo de atribuição de comprimentos de
onda.
• Considerando uma HNN para cada camada e inserindo novas sinapses (mape-
adas para comprimentos de onda no mesmo enlace) para os neurônios. Seria
possível considerar o efeito de FWM com maior detalhamento.
• Utilizando a arquitetura citada anteriormente, a HNN poderia rotear e atribuir
comprimentos de onda em apenas uma etapa. Apenas os neurônios da rota e
do comprimento de onda escolhidos seriam disparados.
• Esta mesma arquitetura poderia ser aplicada a redes ópticas com a capacidade
de conversão de comprimentos de onda.
• Implementação do algoritmo em arquitetura paralela para reduzir a complexi-
dade do mesmo. Os benefícios serão uma maior escalabilidade do algoritmo,
diminuição do tempo de resposta e convergência mais rápida na busca por
parâmetros.
• Implementação do algoritmo em hardware. Os benefícios seriam diminuição
do tempo de resposta e complexidade em relação às arquiteturas sequenciais
e paralelas e possibilidade de implementação em dispositivos de comutação de
redes ópticas.
94
APÊNDICE A
Artigo Publicado
• R. A. Santana, M. R. Pontes e C. J. A. Bastos-Filho. A Multiple Objective Par-
ticle Swarm Optimization Approach Using Crowding Distance and Roulette
Wheel. ISDA ’09: Proceedings of the 2009 Ninth International Conference on
Intelligent Systems Design and Applications, 2009, Pisa, Itália.
95
Referências
[1] G. Agrawal. Fiber-Optic Communication Systems. Wiley, New York, 1997.
[2] C. W. Ahn, R. S. Ramakrishna, C. G. Kang, and I. C. Choi. Shortest path rou-
ting algorithm using hopfield neural network. Electronics Letters, 37(19):1176–
1178, Sep 2001.
[3] M. K .M. Ali and F. Kamoun. Neural networks for shortest path computation
and routing in computer networks. Neural Networks, IEEE Transactions on,
4(6):941–954, Nov 1993.
[4] M. Azadeh. Fiber Optics Engineering. Springer, Berlin, 2009.
[5] N. Banerjee, V. Mehta, and S. Pandey. A genetic algorithm approach for
solving the routing and wavelength assignment problem in wdm networks.
Proceedings of 3rd IEEE/IEE International Conference on Networking, pages
70–78, 2004.
[6] D. M. Baney, P. G. Allion, and R. S. Tucker. Theory and measurement te-
chniques for the noise figure of optical amplifiers. Optical Fiber Technology,
6(12):122–154, April 2000.
[7] C. J. A. Bastos-Filho, R. A. Santana, and A. L. I. Oliveira. A novel approach
for a routing algorithm based on a discrete time hopfield neural network. In
Foundations of Computational Intelligence, 2007. FOCI 2007. IEEE Sympo-
sium on, pages 363–369, April 2007.
[8] C. J. A. Bastos-Filho, W. H. Schuler, and A. L. I. Oliveira. A fast and relia-
ble routing algorithm based on hopfield neural networks optimized by particle
swarm optimization. In Neural Networks, 2008. IJCNN 2008. (IEEE World
Congress on Computational Intelligence). IEEE International Joint Confe-
rence on, pages 2777–2783, June 2008.
[9] C. J. A. Bastos-Filho, R. M. F. Silva, D. F. Carvalho, G. M. Cavalcanti Jr.,
D. A. R. Chaves, and J. F. Martins-Filho. Intelligent impairment aware routing
algorithm for all-optical networks based on ant colony optimization trained by
particle swarm optimization. In XXVII Simpósio Brasileiro de Telecomunica-
ções, 2009, volume 1, 2009.
[10] C.J.A. Bastos-Filho, D.A.R. Chaves, F.S.F. e Silva, R.V.B. Carvalho, H.A.
Pereira, and J.F. Martins-Filho. Impairment aware wavelength assignment
for all-optical networks based on evolutionary computation. pages 1 –4, 28
2009-july 2 2009.
96
[11] P. Becker. Erbium-Doped Fiber Amplifiers. Academic Press, Boston, 1999.
[12] P. C. Becker, N. A. Olsson, and J. R. Simpson. Erbium-Doped Fiber Amplifiers:
Fundamentals and Technology (Optics and Photonics). Academic Press, 1999.
[13] R. Bellman. On a routing problem. Quarterly of Applied Mathematics,
16(1):87–90, 1958.
[14] E. Bonabeau, F. Henaux, S. Gurin, D. Snyers, P. Kuntz, and G. Theraulaz.
Routing in telecommunications networks with "smart"ant-like agents. In In
Proceedings of IATA’98, Second Int. Workshop on Intelligent Agents for Tele-
communication Applications. Lectures Notes in AI. Springer Verlag, 1998.
[15] E. Bouillet, G. Ellinas, J. F Labourdette, and R. Ramamurthy. Path Routing
in Mesh Optical Networks. Wiley-Interscience, 2007.
[16] R. Brits, A. P. Engelbrecht, and F. Van Den Bergh. A niching particle swarm
optimizer. In In Proceedings of the Conference on Simulated Evolution And
Learning, pages 692–696, 2002.
[17] R. Cardillo, V. Curri, and M. Mellia. Considering transmission impairments
in configuring wavelength routed optical networks. In Optical Fiber Com-
munication Conference, 2006 and the 2006 National Fiber Optic Engineers
Conference. OFC 2006, pages 3 pp.–, March 2006.
[18] J. H. E. Cartwright and O. Piro. The dynamics of runge-kutta methods. Int.
J. Bifurcation and Chaos, 2:427–49, 1992.
[19] D. A. R. Chaves, D. O. Aguiar, H. A. Pereira, C. J. A. Bastos-Filho, and J. F.
Martins-Filho. Novel physical impairments aware adaptive weight function for
routing in all optical networks. In Microwave and Optoelectronics Conference,
2007. IMOC 2007. SBMO/IEEE MTT-S International, pages 194–198, 29
2007-Nov. 1 2007.
[20] D. A. R. Chaves, J. F. Martins-Filho, and C. J. A. Bastos-Filho. Ferramenta
computacional para simulação de redes ópticas transparentes. In MOMAG
2008 - evento congregando o 13
o
SBMO Simpósio Brasileiro de Microondas
e Optoeletrônica e o 8
o
CBMag Congresso Brasileiro de Eletromagnetismo,
Florianópolis, 2008.
[21] C. T. Chen. Linear System Theory and Design. Oxford University Press,
Oxford Oxfordshire, 1999.
[22] S. Y. Chiu, T. Y. Sun, S. T. Hasieh, and C. W. Lin. Cross-searching stra-
tegy for multi-objective particle swarm optimization. In IEEE Congress on
Evolutionary Computation, pages 3135–3141. IEEE, 2007.
[23] M. Clerc. The swarm and the queen: towards a deterministic and adaptive
particle swarm optimization. In Congress on Evolutionary Computation, vo-
lume 3, pages 1951–1957, 1999.
97
[24] M. Clerc and J. Kennedy. The particle swarm - explosion, stability, and
convergence in a multidimensional complex space. Evolutionary Computation,
IEEE Transactions on, 6(1):58–73, 2002.
[25] Coello, G. B. Lamont, and D. A. Van Veldhuizen. Evolutionary Algorithms
for Solving Multi-Objective Problems. Genetic and Evolutionary Computation.
Springer, New York, 2nd edition, 2007.
[26] C. A. C. Coello, G. T. Pulido, and M. S. Lechuga. Handling multiple objec-
tives with particle swarm optimization. IEEE Transactions on Evolutionary
Computation, 8(3):256–279, 2004.
[27] M. A. Cohen and S. Grossberg. Absolute stability of global pattern formation
and parallel memory storage by competitive neural networks. pages 70–81,
1988.
[28] W. J. Dally and J. W. Poulton. Digital Systems Engineering. Cambridge
University Press, 1998.
[29] K. Deb, S. Agrawal, A. Pratap, and T Meyarivan. A fast elitist non-dominated
sorting genetic algorithm for multi-objective optimization: Nsga-ii. pages 849–
858. Springer, 2000.
[30] G. Di Caro and M. Dorigo. Antnet: Distributed stigmergetic control for
communications networks. Journal of Artificial Intelligence Research, 9:317–
365, 1998.
[31] E. Dijkstra. A note on two problems in connection with graphs. Numerische
Mathematik, 1:269–271, 1959.
[32] R. Eberhart and J. Kennedy. A new optimizer using particle swarm theory.
pages 39–43, 1995.
[33] R. Eberhart and Y. Shi. Particle swarm optimization: developments, appli-
cations and resources. In Evolutionary Computation, 2001. Proceedings of the
2001 Congress on, volume 1, pages 81–86 vol. 1, 2001.
[34] R. Eberhart, P. Simpson, and R. Dobbins. Computational intelligence PC
tools. Academic Press Professional, Inc., San Diego, CA, USA, 1996.
[35] R. C. Eberhart, Y. Shi, and J. Kennedy. Swarm Intelligence. The Morgan
Kaufmann Series in Artificial Intelligence. Morgan Kaufmann, 1st edition,
March 2001.
[36] A. P. Engelbrecht. Computational Intelligence: An Introduction. Wiley Pu-
blishing, 2007.
[37] L. R. Ford and D. R. Fulkerson. Flows in Networks (Rand Corporation Rese-
arch Studies Series). Princeton Univ Pr, 1962.
[38] R. M. Garlick and R. S. Barr. Dynamic wavelength routing in wdm networks
via ant colony optimization. In ANTS ’02: Proceedings of the Third Inter-
national Workshop on Ant Algorithms, pages 250–255, London, UK, 2002.
Springer-Verlag.
98
[39] D. K. Gehlhaar and D. B. Fogel. Tuning evolutionary programming for con-
formationally flexible molecular docking. In Evolutionary Programming, pages
419–429, 1996.
[40] O. Gerstel and S. Kutten. Dynamic wavelength allocation in all-optical ring
networks. In Communications, 1997. ICC 97 Montreal, ’Towards the Kno-
wledge Millennium’. 1997 IEEE International Conference on, volume 1, pages
432–436 vol.1, Jun 1997.
[41] A. Ghatak and K. Thyagarajan. An Introduction to Fiber Optics. Cambridge
University Press, 1998.
[42] P. Green. Progress in optical networking. Communications Magazine, IEEE,
39(1):54–61, Jan 2001.
[43] S. Haykin. Neural Networks: A Comprehensive Foundation. Macmillan, New
York, 1994.
[44] P. G. Hewitt. Conceptual Physics (9th edition). Addison Wesley, 2001.
[45] J. J. Hopfield. Neural networks and physical systems with emergent collective
computational abilities. Proceedings of the National Academy of Sciences of
the United States of America, 79(8):2554–2558, April 1982.
[46] J. J. Hopfield. Neurons with graded response have collective computational
properties like those of two-state neurons. Proceedings of the National Academy
of Sciences of the United States of America, 81(10):3088–3092, May 1984.
[47] J. J. Hopfield and D. W. Tank. “neural” computation of decisions in optimi-
zation problems. Biological Cybernetics, 52(3):141–152, July 1985.
[48] X. Hu, R. C. Eberhart, and Y. Shi. Particle swarm with extended memory for
multiobjective optimization. In Swarm Intelligence Symposium, 2003. SIS’03.
Proceedings of the 2003 IEEE, pages 193–197, 2003.
[49] X. Hu, R. C. Eberhart, and Y. Shi. Swarm intelligence for permutation opti-
mization: Case study of n-queens problem, 2003.
[50] I. P. Kaminow and T. Li. Optical Fiber Telecommunications IV-B, Volume
B, Fourth Edition: Systems and Impairments (Optics and Photonics) (v. IV).
Academic Press, 2002.
[51] J. Kennedy. Small worlds and mega-minds: effects of neighborhood topology
on particle swarm performance. In Evolutionary Computation, 1999. CEC 99.
Proceedings of the 1999 Congress on, volume 3, pages –1938 Vol. 3, 1999.
[52] J. Kennedy. Population structure and particle swarm performance. In In:
Proceedings of the Congress on Evolutionary Computation (CEC 2002, pages
1671–1676. IEEE Press, 2002.
[53] J. Kennedy and R. Eberhart. Particle swarm optimization. volume 4, pages
1942–1948 vol.4, 1995.
99
[54] J. Kennedy and R. C. Eberhart. A discrete binary version of the particle swarm
algorithm. In Systems, Man, and Cybernetics, 1997. ’Computational Cyber-
netics and Simulation’., 1997 IEEE International Conference on, volume 5,
pages 4104–4108 vol.5, 1997.
[55] N. Kojic, I. Reljin, and B. Reljin. Neural network for finding optimal path
in packet-switched network. In Neural Network Applications in Electrical En-
gineering, 2004. NEUREL 2004. 2004 7th Seminar on, pages 91–96, Sept.
2004.
[56] N. Kojic, I. S. Reljin, and B. D. Reljin. Optimal routing in packet switching
network by using neural network. In Computer as a Tool, 2005. EUROCON
2005.The International Conference on, volume 2, pages 1750–1753, Nov. 2005.
[57] N. S. Kojic, I. S. Reljin, and B. D. Reljin. Routing in optical networks by using
neural network. In Neural Network Applications in Electrical Engineering,
2006. NEUREL 2006. 8th Seminar on, pages 65–68, Sept. 2006.
[58] N. S. Kojic, I. S. Reljin, and B. D. Reljin. Different wavelength assignment te-
chniques in all-optical networks controlled by neural network. In Telecommuni-
cations in Modern Satellite, Cable and Broadcasting Services, 2007. TELSIKS
2007. 8th International Conference on, pages 401–404, Sept. 2007.
[59] N. S. Kojic, I. S. Reljin, and B. D. Reljin. All-optical network with simulta-
neous in-node routing and wavelength assignment. In Telfor Journal, volume
Vol. 1, 2009.
[60] V. T. Le, X. Jiang, S. H. Ngo, and S. Horiguchi. Dynamic rwa based on
the combination of mobile agents technique and genetic algorithms in wdm
networks with sparse wavelength conversion. IEICE - Trans. Inf. Syst., E88-
D(9):2067–2078, 2005.
[61] V. T. Le, S. H. Ngo, X. H. Jiang, S. Horiguchi, and M. Y. Guo. A genetic
algorithm for dynamic routing and wavelength assignment in wdm networks.
pages 893–902.
[62] J. F. Martins-Filho, C. J. A. Bastos-Filho, E. A. J. Arantes, S. C. Oliveira,
L. D. Coelho, J. P. G. de Oliveira, R. G. Dante, E. Fontana, and F. D. Nunes.
Novel routing algorithm for transparent optical networks based on noise figure
and amplifier saturation. In Microwave and Optoelectronics Conference, 2003.
IMOC 2003. Proceedings of the 2003 SBMO/IEEE MTT-S International, vo-
lume 2, pages 919–923 vol.2, Sept. 2003.
[63] J. F. Martins-Filho, C. J. A. Bastos-Filho, S. C. Oliveira, E. A. J. Arantes,
E. Fontana, and F. D. Nunes. Novel routing algorithm for optical networks
based on noise figure and physical impairments. In European Conference and
Exhibition on Optical Communication – ECOC, Optical Society of America,
volume 3, pages 856–857, 2003.
[64] J. F. Martins-Filho, D. Chaves, C. Bastos-Filho, and D. O. Aguiar. Intelligent
and fast irwa algorithm based on power series and particle swarm optimiza-
tion. In Transparent Optical Networks, 2008. ICTON 2008. 10th Anniversary
International Conference on, volume 3, pages 158–161, June 2008.
100
[65] W. Mcculloch and W. Pitts. A logical calculus of the ideas immanent in
nervous activity. Bulletin of Mathematical Biology, 5(4):115–133, December
1943.
[66] R. Mendes, P. Cortez, M. Rocha, and J. Neves. Particle swarms for feedforward
neural network training. In Neural Networks, 2002. IJCNN ’02. Proceedings
of the 2002 International Joint Conference on, volume 2, pages 1895–1899,
2002.
[67] B. Mukherjee. Optical Communication Networks. Mcgraw-Hill (Tx), 1997.
[68] M. Mukherjee. Optical WDM Networks (Optical Networks). Springer, 2006.
[69] G. Navarro-Varela and M. C. Sinclair. Ant colony optimization for virtual-
wavelength-path routing and wavelength allocation. in Proc.CEC‘99, July
1999.
[70] S. H. Ngo, X. Jiang, and S. Horiguchi. Adaptive routing and wavelength
assignment using ant-based algorithm. In Networks, 2004. (ICON 2004). Pro-
ceedings. 12th IEEE International Conference on, volume 2, pages 482–486
vol.2, Nov. 2004.
[71] C. R. Noback, D. A. Ruggiero, R. J. Demarest, and N. L. Strominger. The
Human Nervous System: Structure and Function. Humana Press, March 2005.
[72] D. C. Park and S. E. Choi. A neural network based multi-destination routing
algorithm for communication network. In Neural Networks Proceedings, 1998.
IEEE World Congress on Computational Intelligence. The 1998 IEEE Inter-
national Joint Conference on, volume 2, pages 1673–1678 vol.2, May 1998.
[73] H. Pereira, D. Chaves, C. J. A. Bastos-Filho, and Joaquim Martins-Filho. Osnr
model to consider physical layer impairments in transparent optical networks.
Photonic Network Communications, 18(2):137–149, 2008.
[74] H. A. Pereira. Análise sistêmica das penalidades de ruído na redes ópticas
transparentes. PhD thesis, Programa de Pós-graduação em Engenharia Elé-
trica, Universidade Federal de Pernambuco, Novembro 2007.
[75] H. A. Pereira, D. A. R. Chaves, C. J. A. Bastos-Filho, and J.F. Martins-Filho.
Physical impairments modeling for the performance evaluation of transparent
optical networks. In Anais do XXV Simpósio Brasileiro de Telecomunicações
– SBrT, volume 1, pages 1–6, Sept. 2007.
[76] R. Rajiv and K. N. Sivarajan. Routing and wavelength assignment in all-
optical networks. IEEE/ACM Trans. Netw., 3(5):489–500, 1995.
[77] R. Rajiv and K. N. Sivarajan. Optical networks: a practical perspective. Mor-
gan Kaufmann Publishers, San Francisco, 2nd ed edition, 2002.
[78] B. Ramamurthy, D. Datta, H. Feng, J. P. Heritage, and B. Mukherjee. Im-
pact of transmission impairments on the teletraffic performance of wavelength-
routed optical networks. J. Lightwave Technol., 17(10):1713, 1999.
101
[79] T. S. Rappaport. Wireless Communications. Prentice Hall PTR, Upper Saddle
River, 1996.
[80] C. R. Raquel and P. C. Naval Jr. An effective use of crowding distance in
multiobjective particle swarm optimization. In GECCO ’05: Proceedings of
the 2005 conference on Genetic and evolutionary computation, pages 257–264,
New York, NY, USA, 2005. ACM.
[81] H. E. Rauch and T. Winarske. Neural networks for routing communication
traffic. Control Systems Magazine, IEEE, 8(2):26–31, Apr 1988.
[82] M. Reyes-sierra and C. A. Coello Coello. Multi-objective particle swarm op-
timizers: A survey of the state-of-the-art. International Journal of Computa-
tional Intelligence Research, 2:2006.
[83] José L. Risco-Martín, Saurabh Mittal, David Atienza, J. Ignacio Hidalgo, and
Juan Lanchares. Optimization of dynamic data types in embedded systems
using devs/soa-based modeling and simulation. In InfoScale ’08: Proceedings
of the 3rd international conference on Scalable information systems, pages 1–
11, ICST, Brussels, Belgium, Belgium, 2008. ICST (Institute for Computer
Sciences, Social-Informatics and Telecommunications Engineering).
[84] G. N. Rouskas and H. G. Perros. A tutorial on optical networks. pages 155–
193, 2002.
[85] S. Rowe. Computer Networking. Pearson/Prentice Hall, Upper Saddle River,
2005.
[86] B. E. A. Saleh and M. C. Teich. Fundamentals of Photonics. Wiley, New York,
1991.
[87] K. I. Sato. Advances in Transport Network Technologies. Artech House, Bos-
ton, 1996.
[88] W. H. Schuler, C. J. A. Bastos-Filho, and A. L. I. Oliveira. A hybrid hopfield
network-simulated annealing approach to optimize routing processes in tele-
communications networks. In Intelligent Systems Design and Applications,
2007. ISDA 2007. Seventh International Conference on, pages 58–63, Oct.
2007.
[89] W. H. Schuler, C. J. A. Bastos-Filho, and A. L. I. Oliveira. A novel hybrid
training method for hopfield neural networks applied to routing in communi-
cations networks. Int. J. Hybrid Intell. Syst., 6(1):27–39, 2009.
[90] G. Shen, W. D. Grover, T. H. Cheng, and S. K. Bose. Sparse placement of
electronic switching nodes for low-blocking in translucent optical networks.
Journal of Optical Networking, 1:424–441, 2002.
[91] Y. and Shi. A modified particle swarm optimizer. In Evolutionary Computation
Proceedings, 1998. IEEE World Congress on Computational Intelligence., The
1998 IEEE International Conference on, pages 69–73, May 1998.
102
[92] J. Singh. Semiconductor Optoelectronics: Physics and Technology (Electronics
and Vlsi Circuits). McGraw-Hill Companies, 1995.
[93] K. Sivalingam. Optical Wdm Networks. Kluwer Academic Publishers, Boston,
2000.
[94] A. A. Smeda and M. E. El-Hawary. Application of hopfield neural network in
routing for computer networks. In Electrical and Computer Engineering, 1999
IEEE Canadian Conference on, volume 1, pages 145–149 vol.1, 1999.
[95] J. Strand, A. L. Chiu, and R. Tkach. Issues for routing in the optical layer.
Communications Magazine, IEEE, 39(2):81–87, Feb 2001.
[96] S. Subramaniam and R. A. Barry. Wavelength assignment in fixed routing
wdm networks. In Communications, 1997. ICC 97 Montreal, ’Towards the
Knowledge Millennium’. 1997 IEEE International Conference on, volume 1,
pages 406–410 vol.1, Jun 1997.
[97] A. S. Tanenbaum. Computer Networks. Prentice Hall PTR, Upper Saddle
River, 2003.
[98] S. C. A. Thomopoulos, L. Zhang, and C. D. Wann. Neural network imple-
mentation of the shortest path algorithm for traffic routing in communication
networks. In Neural Networks, 1991. 1991 IEEE International Joint Confe-
rence on, pages 2693–2702 vol.3, Nov 1991.
[99] C. S. Tsou, S. C. Chang, and P. W. Lai. Using crowding distance to improve
multi-objective pso with local search.
[100] F. Van Den Bergh and A. P. Engelbrecht. Effects of swarm size on cooperative
particle swarm optimisers, 2001.
[101] M. Vidyasagar. Improved neural networks for analog to digital conversion.
In Neural Networks, 1990., 1990 IJCNN International Joint Conference on,
pages 517–522 vol.3, Jun 1990.
[102] N. Wauters and P. Demeester. Design of the optical path layer in multiwave-
length cross-connected networks. IEEE Journal on Selected Areas in Commu-
nications, 14(5):881–892, 1996.
[103] Bo Wen, R. Shenai, and K. Sivalingam. Routing, wavelength and time-
slot-assignment algorithms for wavelength-routed optical wdm/tdm networks.
Lightwave Technology, Journal of, 23(9):2598–2609, Sept. 2005.
[104] X. Yang and B. Ramamurthy. Dynamic routing in translucent wdm optical
networks. In in Proceedings IEEE ICC 2002, pages 955–971, 2002.
[105] H. Zang, J. P. Jue, and B. Mukherjee. A review of routing and wavelength
assignment approaches for wavelength-routed optical wdm networks, 2000.
[106] K. Zhu, H. Zhu, and B. Mukherjee. Traffic Grooming in Optical Wdm Mesh
Networks. Springer, Berlin, 2005.
103
[107] E. Zitzler. Evolutionary Algorithms for Multiobjective Optimization: Methods
and Applications. PhD thesis, ETH Zurich, Switzerland, 1999.
[108] E. Zitzler, K. Deb, and L. Thiele. Comparison of multiobjective evolutionary
algorithms: Empirical results. Evolutionary computation, 8(2):173–195, 2000.
[109] E. Zitzler and L. Thiele. Multiobjective Optimization Using Evolutionary
Algorithms - A Comparative Case Study. In Conference on Parallel Problem
Solving from Nature (PPSN V), pages 292–301, Amsterdam, 1998.
[110] E. Zitzler and L. Thiele. Multiobjective evolutionary algorithms: a compa-
rative case study and the strength Pareto approach. IEEE transactions on
Evolutionary Computation, 3(4):257–271, 1999.
[111] N. Zulkifli, R. C. Almeida, and K. M. Guild. Efficient resource allocation
of heterogeneous services in transparent optical networks. J. Opt. Netw.,
6(12):1349–1359, 2007.
[112] N. Zulkifli, C. Okonkwo, and K. Guild. Dispersion optimised impairment
constraint based routing and wavelength assignment algorithms for all-optical
networks. In Proceedings, International Conference on Transparent Optical
Networks, volume 3, pages 177–180, June 2006.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo