Algoritmos de amostragem por rejeição dinâmica aplicados a busca descentralizada em redes de mundo pequeno com topologia fractal.
Nome: LEONARDO AGUIAR DO AMARAL
Tipo: Tese de doutorado
Data de publicação: 23/11/2021
Orientador:
Nome |
Papel |
|---|---|
| HUMBERTO BELICH JUNIOR | Orientador |
Banca:
| Nome |
Papel |
|---|---|
| ANTÔNIO CANAL NETO | Examinador Interno |
| CÁSSIO CECATO FAVARATO | Examinador Externo |
| HUMBERTO BELICH JUNIOR | Orientador |
| THALES COSTA SOARES | Examinador Externo |
| VINÍCIUS CÂNDIDO MOTA | Examinador Interno |
Páginas
Resumo: Nesta pesquisa estudamos a navegação de Kleinberg em redes de mundo pequeno através do algoritmo de amostragem por rejeição dinâmica, proposto por Mathieu e Comte. Ao contrário das técnicas convencionais, esta abordagem dispensa a utilização de condições de contorno periódicas que deformam a rede e a converte em toroide. Ao invés disso, utiliza-se máscaras de aceitação sobrepostas a rede quadrada estudada como intuito de oferecer um critério de aceitação adicional para aquisição de links de longo alcance, sem contudo, violar os preceitos fundamentais que regem a distribuição estatística dessas conexões, resultando numa queda drástica da complexidade do algoritmo. O objetivo deste trabalho é estender a abordagem de Mathieu e Comt e a redes com topologia fractal (Quadrado de Sierpinski), sso é feito através do desenvolvimento de uma rotina computacional auxiliar (fractal_search) que torna a geometria fractal detectável às máscaras de aceitação. Esta é uma etapa de grande relevância para a totalidade do processo no que diz respeito a complexidade do algoritmo, uma vez que o conhecimento acumulado em literatura na última década indica que a emergência de roteamento em redes fractais exige que estas possuam tamanhos extremamente elevados. Nossa rotina foi projetada para operar deforma recursiva e harmônica com a autossimilaridade fractal, o que lhe garante desempenho compatível com as tarefas que irá desempenhar durante a simulação. A abordagem adotada na condução
desse trabalho se mostrou consistente com as previsões e resultados já consolidados e publicados em periódicos especializados na área de ciência de rede, tais como: a existência de um expoente de clusterização que minimiza o tempo de entrega, quando este assume
valores idênticos ao da dimensão da rede analisada (αmin = df ), além do surgimento da proporcionalidade do tempo de entrega em relação ao logaritmo do comprimento da rede (T ~ ln2L). Também ficou demonstrado que o número de realizações (R), utilizado para compor o espaço amostral das análises estatísticas da simulação, e o comprimento da rede (L), possuem interdependência e causam impacto expressivo no tempo de processamento.
Finalmente, realizamos um teste de desempenho tomando como parâmetro comparativo o tempo de execução, em que ficou demonstrada a superioridade do método proposto em comparação aos métodos tradicionais.
