Estudo do artigo Dynamic Labeling in Wireless Mesh Networks

Prévia do material em texto

Sistemas Complexos
Lucas Brant Vilanova Alves
lucasbrant@yahoo.com.br
Programa de Pós-Graduação em Engenharia Elétrica
Mestrado em Engenharia Elétrica e Computacão
Estudo do artigo “Dynamic Labeling in Wireless Mesh
Networks” - D. A. Guedes, A. Ziviani e K. V. Cardoso, 
publicado no IEEE Latin America Transactions, Vol. 11, No. 
3, Maio de 2013
Sumário
• Apresentação do Artigo
• Introdução a Wireless Mesh Networks (WMN)
• Medidas de Centralidades baseadas em topologia
• Centralidade LBC
• Centralidade LLBC
• Classificação Dinâmica das redes
• Centralidade DyLan
• Análise da Rede Dart-Mesh
• Análise da Rede Wireless Leiden
• Conclusão
2
Apresentação do Artigo
• Dynamic Labeling in Wireless Mesh Networks
– D. A. Guedes, A. Ziviani e K. V. Cardoso
– IEEE Latin America Transactions, Vol. 11, No. 3, Maio de 2013
• O artigo apresenta duas formas de identificar e classificar 
dinamicamente os nós mais importantes das redes em 
malha sem fio (Wireless Mesh Network - WMN) de grande 
porte.
Introdução a Wireless Mesh Networks 
(WMN)
• Redes Locais sem Fio (WLAN – Wireless Local Area
Networks) que seguem o padrão IEEE 802.11 estão 
bastante difundidas.
• Existe interesse por uma comunicação por múltiplos saltos 
em redes sem fio.
– Podem ser expandidas.
– Modo ad-hoc ou auto-configuração.
– Estende o alcance dos pontos de acesso sem 
necessidade de infra-estrutura adicional.
Introdução a Wireless Mesh Networks 
(WMN)
• Backbones sem fio com múltiplos saltos podem ser 
implementados utilizando roteadores sem fio. São 
chamados de Redes em malha sem fio (WMN – Wireless 
Mesh Networks).
Introdução a Wireless Mesh Networks 
(WMN)
• Desafios para as redes Mesh sem fio:
– Variação na topologia (Adição, remoção e 
movimentação dos nós).
– Variação nas condições do meio de transmissão.
– Mudanças frequentes na qualidade do enlace.
– Assimetria dos enlaces.
• Alternância da importância de cada nó na rede.
Medidas de Centralidades
• Formas de se mensurar a importância dos nós de uma rede.
– Qual é o nó mais central da rede.
– Qual é o nó que, se eliminado, causa mais danos à rede.
• Centralidade de Grau
• Centralidade de Proximidade
• Centralidade de Intermediação
• Centralidade de Autovetor
• Centralidade de Ponte
• Centralidade LBC
• Centralidade LLBC
• Centralidade DyLan
Centralidade de Ponte 
(Brindging Centrality - BC)
• Nó ponte é aquele que interliga componentes densamente 
conectados em um grafo.
• BC(i) = β(i)*Cin(i)
– β(i): Coeficiente que classifica o nó, baseado no grau de seus 
vizinhos:
β(i) =
𝑑(𝑖)−1
σ𝑁(𝑖)
1
𝑑(𝑖)
Onde, d(i) é o grau do nó i e N(i) é o conjunto de vizinhos do nó i.
Centralidade LBC
(Localized Bridging Centrality)
• A centralidade de ponte precisa de informações sobre 
todos os nós da rede, pois necessita da calcular a 
centralidade de intermediação.
• A métrica LBC equivale funcionalmente à centralidade de 
ponte, porém tomando apenas os nós que sejam vizinhos a 
i.
• BC(i) = β(i)*Cego(i)
– Cego(i): Centralidade de intermediação egocêntrica 
(egocentric betweenness centrality), que consiste na 
Centralidade de intermediação, porém, considerando 
apenas os nós que sejam vizinhos a i.
Centralidade LLBC
(Localized Load-aware Bridging Centrality)
• Para levar em consideração o tráfego na rede, foi proposto 
em outro trabalho a métrica LLBC (Localized Load-aware
Bridging Centrality)
• O coeficiente de ponte β(i) deixa de ser calculado com base 
no grau dos seus vizinho e passa a ser calculado com base 
na carga de tráfego dos seus vizinhos.
Centralidade LLBC
(Localized Load-aware Bridging Centrality)
• βt(i) =
𝐿𝑜𝑎𝑑(𝑖)
σ𝑁(𝑖) 𝐿𝑜𝑎𝑑(𝑖)
– Load (i) = In(i) + Out (i) + 2 * Fwd (i)
Onde,
• Load(i): Carga no nó i
• In(i): Representa os bytes destinados ao nó i
• Out(i): Representa os bytes originados em i
• Fwd(i): Representa os bytes que foram reencaminhados por i. Tem peso dois 
pelo fato dos bytes reencaminhados chegarem e saírem do nó v
• LLBC(i) = β t(i)*Cego(i)
Classificação Dinâmica das redes
• Premissa 1: a posição topológica de um nó e o tráfego atual 
de pacotes nesse nó são os principais elementos para 
definir o nível de importância relativa do nó na rede;
• Premissa 2: a função de encaminhar pacotes de outros nós 
deve afetar o nível de importância do nó, mas o tamanho 
do impacto deve ser adaptável;
– Load (i) = In(i) + Out (i) + WF * Fwd (v)
Onde WF representa um peso adaptável para pacotes encaminhados.
• Premissa 3: o histórico do cálculo da importância relativa 
do nó deve ser levado em consideração.
Centralidade DyLan
(Dynamic Labeling of Nodes)
• De forma a lidar com o comportamento dinâmico de 
WMNs e fornecer uma informação estável sobre as 
centralidades dos nós, foi proposta uma métrica utilizando 
uma média móvel ponderada exponencial (exponentially
weighted moving average – EWMA).
• Lt(i) = Lt-1(i) * WH + β t(i) * Cego(i) * (1 – WH)
Onde,
• L0(i) = 0
• Lt-1(i) = Cálculo anterior da centralidade DyLan
• WH = Peso do cálculo anterior (0 ≤ WH ≤ 1)
Rede Dart-Mesh
• Dart-Mesh é uma WMN construída e implantada no 
Departamento de Ciência da Computação da Dartmouth
College e possui 16 nós.
• Utilizada como uma plataforma de experimentação para 
pesquisas em redes sem fio
Conclusão
Comparativo com centralidades 
baseadas em topologia
Nó Cg Cp Cin Ca
50 0.6667 0.7500 0.2222 -0.2980
30 0.7778 0.8182 0.3889 0.7693
80 0.6667 0.7500 0.2222 -0.2980
1 0.5556 0.6923 0 -0.0469
2 0.5556 0.6923 0 -0.0469
20 0.5556 0.6923 0 -0.0469
160 0.2222 0.5000 0 -0.2851
90 0.2222 0.5000 0 -0.2851
Cg: Centralidade de Grau
Cp: Centralidade de Proximidade
Cin: Centralidade de Intermediação
Ca: Centralidade de Autovetor
Conclusão
Comparativo com centralidades 
baseadas em topologia
Nó Cg Cp Cin Ca
50 0.6667 0.7500 0.2222 0.4031
30 0.8889 0.9000 0.5556 0.4385
80 0.5556 0.6923 0 0.3904
1 0.5556 0.6923 0 0.3904
2 0.5556 0.6923 0 0.3904
20 0.5556 0.6923 0 0.3904
160 0.2222 0.5294 0 0.1055
90 0.2222 0.5294 0 0.1055
Cg: Centralidade de Grau
Cp: Centralidade de Proximidade
Cin: Centralidade de Intermediação
Ca: Centralidade de Autovetor
Rede Wireless Leiden
• A Wireless Leiden é uma rede aberta implantada em Leiden 
na Holanda.
• Foi uma das pioneiras na utilização de dispositivos 802.11b 
para construção de uma WMN.
• Núcleo composto por mais de 100 nós, tornando-a uma das 
maiores WMNs do mundo.
Rede Wireless Leiden
• Foi selecionado um subconjunto de 17 nós operando como 
roteadores e pontos de acesso, sendo que 3 deles têm 
conexão externa à Internet.
• A cada 10 minutos, os valores de In(i) , Out(i) e Fwd(i) são 
coletados e as métricas LLBC e DyLaN são atualizadas.
Classificação dinâmica das centralidades 
Métrica LLBC
Classificação dinâmica das centralidades 
Métrica DyLan, com WH = 0,9
Comparativo com centralidades 
baseadas em topologia
Nó Cg Cp Cin Ca
A 0.1053 0.2923 0.1053 0.0918
B 0.1053 0.2794 0.1053 0.0940
C 0.1053 0.3115 0.1053 0.1239
D 0.2105 0.3878 0.2938 0.2505
E 0.1053 0.3167 0.0423 0.1190
F 0.1053 0.3393 0.0580 0.1616
G 0.1053 0.3333 0.0508 0.1133
H 0.2105 0.3878 0.1645 0.2436
I 0.1053 0.3065 0.0238 0.1364
J 0.1053 0.3333 0.0391 0.1732
K 0.2105 0.4318 0.3057 0.3932
L 0.1579 0.3878 0.1392 0.3520
M 0.2105 0.4222 0.1823 0.4261
N 0.1053 0.3455 0.0207 0.2191
O 0.1579 0.3654 0.2169 0.2566
P 0.2105 0.4222 0.3300 0.3383
Q 0.1579 0.3958 0.1924 0.2274
Conclusão
• A métrica DylaN trouxe melhores resultados quanto a 
classificação.
• A métrica DyLan fornece uma classificação dinâminca mais 
estável. 
• A métrica LLBC não atende as premissas 2 e 3.
• As centralidades baseadas em topologia não atendem as 
premissas 1, 2 e 3
Obrigado
Lucas Brant Vilanova Alves
lucasbrant@yahoo.com.br