Algoritmo A* para planejamento de arquitetura de redes em cenários heterogêneos

Abstract

The growing demand for capacity in communication systems requires a holistic approach which optimizes the use of the available resources. We can solve part of the capacity problems by using clustering techniques in network structure planning (a non-hierarchical structure suffers from problems as scalability and capacity, therefore a hierarchical structure conduces improvement in the network performance). Then, for this reason, usually clustering techniques are used in telecommunications network projects. Nevertheless, typically the clustering process is unable to take into account the presence of obstacles in the scenario. Then, in this work we integrated the A* and Lloyd’s algorithm as a way of producing a new algorithm which is able to perform the clustering process in a scenario that has obstacles. It is worth mentioning that we couldn’t find back in the literature integration of A* and K-means. Now, through this new algorithm it is possible to perform the clustering process in more complex scenarios (i.e., scenarios with obstacles). Our proposed method consists in changing the Euclidian or Manhattan distances in the Lloyds algorithm to the distances calculated through a Brute-force search with A* algorithm. Our results show that the algorithm we attained as final product made the total mean distance change, from 4,7 to 3,0833 when compared with Lloyd’s algorithm in the presence of obstacles in the clustering scenario to the specific case we considered.

A crescente demanda por capacidade nos sistemas de comunicação requer uma abordagem holística que otimize o uso dos recursos disponíveis. Podemos solucionar parte dos problemas de capacidade utilizando técnicas de clusterização no planejamento da estrutura das redes (uma estrutura sem hierarquia sofre com problemas de escalabilidade e capacidade, portanto uma estrutura hierarquizada conduz melhorias na performance da rede). Então, por esta razão, usualmente são utilizadas técnicas de clusterização no projeto de redes de telecomunicações. No entanto, tipicamente o processo de clusterização não é capaz de levar em conta a presença de obstáculos presentes no cenário. Assim, neste trabalho integramos os algoritmos de A* e Lloyds como forma de produzir um novo algoritmo que tem a capacidade de efetuar o processo de clusterização em cenários que possuem obstáculos. Cabe mencionar que não encontramos anteriormente na literatura a integração de A* com K-means. Agora, por meio deste novo algoritmo é possível efetuar o processo de clusterização em cenários mais complexos (i.e., cenários com obstáculos). Nosso método proposto consiste em mudar as medidas de distância euclidiana ou distância Manhattan no algoritmo de Lloyds para as distâncias calculadas por meio de uma busca exaustiva com o algoritmo A*. Nossos resultados mostram que o algoritmo que obtivemos como produto final fez a distância média total mudar, de 4,7 para 3,0833 quando comparado ao algoritmo de Lloyds com a presença de obstáculos no cenário de clusterização para o caso específico que consideramos.