Algoritmos Distribuídos
MANGO
Mobile Ad Hoc Networks
for Group Operations
Algoritmos Distribuídos
MANGO
•Podem ser criadas rapidamente
•Adequadas para dar apoio de
comunicação a:
•Operações militares
•Operações de resgate
Algoritmos Distribuídos
Roteiro
•Introdução
•Definição do problema
•Ãlgoritmo
•Conclusão
Algoritmos Distribuídos
Introdução
Algoritmos distribuídos
X
Gerenciamento de Grupos
Consistência de informações
Comunicação em grupo
Falhas ou entrada de processos
Algoritmos Distribuídos
Grupo de operações — rede Ad Hoc
Algoritmos Distribuídos
Grupo de operações — rede Ad Hoc
NÓS
Algoritmos Distribuídos
Grupo de operações — rede Ad Hoc
TERMINAIS
Algoritmos Distribuídos
Grupo de operações — rede Ad Hoc
Dois tipos de dispositivos distintos
•Nós
•Terminais
•Menos mobilidade
•Carga mais longa
X
•Maior alcance
•Mais mobilidade
•Carga mais curta
•Menor alcance
Multihopping
Algoritmos Distribuídos
Grupo de operações — rede Ad Hoc
Algoritmos Distribuídos
Grupo de operações — rede Ad Hoc
Algoritmos Distribuídos
Grupo de operações — rede Ad Hoc
Algoritmos Distribuídos
Grupo de operações — rede Ad Hoc
•Para uma entrega de mensagens mais
eficiente, é necessário saber para que nó
deve ser enviada uma mensagem para um
dado terminal
Localização do nó
Algoritmos Distribuídos
Grupo de operações — rede Ad Hoc
Manutenção das informações de localização
de centenas de usuários exige grande troca
de mensagens
Arquitetura hierárquica
Grupos representados por líderes
Algoritmos Distribuídos
Arquitetura Hierárquica — Grupos
Algoritmos Distribuídos
Arquitetura Hierárquica — Grupos
Algoritmos Distribuídos
Arquitetura Hierárquica — NP’s
NP
Algoritmos Distribuídos
Arquitetura Hierárquica — NS’s
Algoritmos Distribuídos
Arquitetura Hierárquica — NS’s
Algoritmos Distribuídos
Arquitetura Hierárquica — NS’s
NS
Área de localização
Algoritmos Distribuídos
Arquitetura Hierárquica — NT’s
Algoritmos Distribuídos
Arquitetura Hierárquica — NT’s
Arquitetura Hierárquica — NT’s
Algoritmos Distribuídos
NT
Área geográfica
Algoritmos Distribuídos
Arquitetura Hierárquica
NT
NS
NP
líderes
participantes
Algoritmos Distribuídos
Arquitetura Hierárquica
•Participante
•ID do líder
Algoritmos Distribuídos
Arquitetura Hierárquica
•Participante
•ID do líder
•Líder
•ID do nó responsável (NP)
Algoritmos Distribuídos
Arquitetura Hierárquica
•Participante
•ID do líder
•Líder
•ID do nó responsável (NP)
•NP
•Tabela [ ID terminais X ID Grupos ]
Algoritmos Distribuídos
Arquitetura Hierárquica
•Participante
•Líder
•ID do líder
•ID do nó responsável (NP)
•NP
•Tabela [ ID terminais X ID Grupos ]
•NS
•Tabela [ ID terminais X ID Grupos ]
•Tabela [ ID Grupos X ID Nó responsável ]
Algoritmos Distribuídos
Arquitetura Hierárquica
•Participante
•Líder
•ID do líder
•ID do nó responsável (NP)
•NP
•Tabela [ ID terminais X ID Grupos ]
•NS
•Tabela [ ID terminais X ID Grupos ]
•Tabela [ ID Grupos X ID Nó responsável ]
•NT
•Tabela [ ID terminais X ID área de localização ]
Algoritmos Distribuídos
Informações de localização
Arquitetura hierárquica
•Localidade de chamada
•Localidade de movimentação
Diminui o número de atualizações
Algoritmos Distribuídos
Informações de localização
Grupos de terminais
•Líder responsável por atualização
•Característica de movimento em grupo
Diminui o número de mensgens
Algoritmos Distribuídos
Manutenção de Grupos
•Revezamento de líder
•Interrogação de grupo
•Fusão de grupo
•Associação a grupo
•Formação de novo grupo
•Movimentação de grupo
Algoritmos Distribuídos
Revezamento de Líder
Dentro de um grupo, periodicamente, cada
terminal tenta assumir papel de líder
•Maior gasto de energia
•Critério de justiça
Algoritmos Distribuídos
Revezamento de Líder
Ta
Tj
Tb
Tc
Algoritmos Distribuídos
Revezamento de Líder
Ta
Tj
Tb
Tc
Algoritmos Distribuídos
Revezamento de Líder
Ta
Tj
Tb
Tc
Algoritmos Distribuídos
Revezamento de Líder
Ta
Tj
Tb
Tc
Responde se d < dth !
Algoritmos Distribuídos
Revezamento de Líder
Ta
Tj
Tb
Tc
Algoritmos Distribuídos
Revezamento de Líder
Ta
Tj
Tb
Tc
Algoritmos Distribuídos
Revezamento de Líder
Ta
Tj
Tb
Nenhuma resposta:
Interrogação de grupo
Tc
Algoritmos Distribuídos
Interrogação de grupo
Operação iniciada por terminal que deseja
saber quais terminais se encontram em
sua vizinhança
Algoritmos Distribuídos
Interrogação de grupo
Ta
Tj
Tb
Tc
Algoritmos Distribuídos
Interrogação de grupo
Ta
Tj
Tb
Tc
Algoritmos Distribuídos
Interrogação de grupo
Ta
Tj
Tb
Tc
Responde informando d
Algoritmos Distribuídos
Interrogação de grupo
Ta
Tj
Tb
Se seu líder atual não
responde, ou está muito
longe:
Associação a grupo
Tc
Algoritmos Distribuídos
Interrogação de grupo
Ta
Tj
Tb
Se ninguém responde:
Forma novo grupo
Tc
Algoritmos Distribuídos
Fusão de grupo
Operação iniciada quando terminal líder
percebe um líder de grupo na sua
vizinhança
Fusão de grupo
Algoritmos Distribuídos
NP
Ta
Tj
Tb
Tc
Responde informando d
Fusão de grupo
Algoritmos Distribuídos
NP
Ta
Tj
Tb
Tc
Se tem mais componentes,
anuncia
Fusão de grupo
Algoritmos Distribuídos
NP
Ta
Tj
Tb
Tc
Se tem menos componentes,
solicita fusão
Fusão de grupo
Algoritmos Distribuídos
NP
Ta
Tj
Tb
Tc
Nó responsável recebe
solicitação
Fusão de grupo
Algoritmos Distribuídos
NP
Ta
Tj
Tb
Tc
Envia mensagem
confirmando
Algoritmos Distribuídos
Associação a grupo
Operação iniciada por terminal que deseja
se associar a um grupo em sua vizinhança,
cujo líder está mais proximo
Associação a grupo
Algoritmos Distribuídos
NP
Ta
Tj
Tb
Se seu líder atual não
responde, ou está muito
longe:
Associação a grupo
Tc
Associação a grupo
Algoritmos Distribuídos
NP
Ta
Tj
Tb
Tc
Nó responsável recebe
solicitação
Associação a grupo
Algoritmos Distribuídos
NP
Ta
Tj
Tb
Tc
Envia mensagem
confirmando
Algoritmos Distribuídos
Associação a grupo
Ta
Tj
Tb
O antigo líder será notificado
pelo novo líder
Tc
Algoritmos Distribuídos
Formação de novo grupo
Operação iniciada por terminal que deseja
se tornar um grupo e convidar integrantes
Algoritmos Distribuídos
Formação de novo grupo
Ta
Tj
Tb
Se ninguém responde:
Forma novo grupo
Tc
Formação de novo grupo
Algoritmos Distribuídos
NP
Ta
Tj
Tb
Tc
NP
Formação de novo grupo
Algoritmos Distribuídos
NP
Ta
Tj
Nós oferecem um ID de grupo
Tb
Tc
NP
Formação de novo grupo
Algoritmos Distribuídos
NP
Ta
Tj
Tb
Seleciona o mais próximo
Tc
NP
Formação de novo grupo
Algoritmos Distribuídos
NP
Ta
Tj
Tb
Tc
NP
Formação de novo grupo
Algoritmos Distribuídos
NP
Ta
Tj
Tb
Tc
NP
Algoritmos Distribuídos
Movimentação de grupo
Grupo de terminais se move e
se afasta do nó responsável
•Nós transmitem sinal continuamente
•Líder calcula distância
Movimentação de grupo
Algoritmos Distribuídos
NP
Ta
Tj
Tb
Tc
NS
NP
Movimentação de grupo
Algoritmos Distribuídos
NP
Ta
Tj
Tb
Tc
NS
NP
Movimentação de grupo
Algoritmos Distribuídos
NP
Ta
Tj
Tb
Nós de segundo nível é
responsével por atualizar
informações
Tc
NS
NP
Movimentação de grupo
Algoritmos Distribuídos
NP
Ta
Tj
Tb
Nós de segundo nível é
responsével por atualizar
informações
Tc
NS
NP
Algoritmos Distribuídos
Conclusão
Gerenciamento de grupos de terminais
com líderes responsáveis por atualização
de informações e arquitetura hierárquica
foi capaz de reduzir a 20% o total de
mensagens de atulização para
deslocamento em grupo