Evaluating the effects of clustering and routing algorithms in satellite and HAPS networks

Abstract

Non-Terrestrial Networks (NTN) applications have gained notoriety over the years, especially solutions using technologies such as satellite networks and High-Altitude Platform Station (HAPS). In the pace of technological expansion, numerous challenges are encountered, mainly due to the high density of possible links between these two technologies. Therefore, ways of reducing the complexity of these networks have been the focus of many studies, as there are many problems related to routing and the computing power involved in carrying out these operations in large-scale networks. This dissertation investigates the impact of clustering techniques on routing efficiency in two critical network environments: Low Earth Orbit (LEO) satellite constellations and HAPS networks. LEO satellite constellations are highly mobile and thus have time-varying network topologies. Consequently, many routing algorithms that work well on the terrestrial Internet may not be suitable for LEO constellations. The provided study analyses not only link-state routing algorithms, as used in well-known routing protocols for LEO constellations such as Contact Graph Routing (CGR), which follows a Software Defined Networking (SDN) approach, but also distance-vector algorithms, as well as the potential combination of link-state and distance-vector algorithms when network clusters are used in an LEO constellation. After proving that dividing the LEO network into clusters can significantly improve the performance of routing algorithms, in a second scenario with HAPS constellations, to diversify the usage scenarios, the aim was to understand the impact that using different types of clustering algorithms can have on the network and impact the routing algorithms. For this scenario, the study compares three clustering methods - Spectral Clustering, K-Means, and Agglomerative Clustering by evaluating their computational efficiency and impact on routing performance across various network configurations. The scientific findings indicate that clustering can significantly improve the routing efficiency of the Dijkstra algorithm, reducing execution time by at least 89.8%, depending on the clustering technique and network density. While Spectral Clustering, although computationally intensive, proved to be more effective for routing, K-Means and Agglomerative Clustering showed better execution time in forming clusters. This research provides valuable insights into selecting the best clustering strategies for enhanced routing in HAPS networks, highlighting the trade-offs between computational complexity and clustering quality.

As aplicações de Redes Não Terrestres (NTN) têm ganhado notoriedade ao longo dos anos, nomeadamente as soluções que recorrem a tecnologias como as redes de satélites e a High-Altitude Platform Station (HAPS). Por conseguinte, as formas de reduzir a complexidade destas redes têm sido alvo de muitos estudos, dado que existem muitos problemas relacionados com o encaminhamento e com o poder de computação envolvido na realização destas operações em redes de grande escala. No ritmo da expansão tecnológica, inúmeros desafios são encontrados, principalmente devido à alta densidade de possíveis conexões entre essas duas tecnologias. Esta dissertação investiga o impacto das técnicas de clusterização na eficiência do roteamento em dois cenários críticos de redes de telecomunicações: Constelações de satélites de órbita terrestre baixa (LEO) e redes HAPS. As constelações de satélites LEO são altamente móveis, portanto, têm topologias de rede variáveis no tempo. Consequentemente, muitos algoritmos de roteamento que funcionam bem na Internet terrestre podem não ser adequados para constelações LEO. O presente estudo analisa não só os algoritmos de roteamento link-state, tal como utilizados em protocolos de roteamento amplamente conhecidos para constelações LEO, como o Contact Graph Routing (CGR), que segue uma abordagem de rede definida por software (SDN), mas também os algoritmos de distance-vector, bem como a potencial combina- ção de algoritmos link-state e de distance-vector quando são combinados com técnicas de clusterização em uma constelação LEO. Depois de provar que a divisão da rede LEO em clusters pode melhorar significativamente o desempenho dos algoritmos de roteamento, um segundo cenário, com constelações HAPS foi utilizado para diversificar os cenários de aplicação do estudo. O objetivo foi compreender o impacto de diferentes algoritmos de clusterização na rede que podem afetar os algoritmos de roteamento. Para este cenário, o estudo compara três métodos de clusterização - Espectral, K-Means e Aglomerativa - avaliando a sua eficiência computacional e o impacto no desempenho do roteamento em várias configurações de rede. Os resultados científicos indicam que a clusterização pode melhorar significativamente a eficiência do rotemaneto do algoritmo Dijkstra, reduzindo o tempo de execução em até 89,8%, dependendo da técnica de clusterização e da densidade de nós da rede. Enquanto a clusterização Espectral, embora computacionalmente intensivo, provou ser mais eficaz para o roteamento, a clusterização K-Means e Aglomerativa apresentaram melhor tempo de execução na formação de clusters. Esta investigação fornece informações valiosas sobre a seleção das melhores estratégias de clusterização para melhorar o roteamento em redes HAPS, destacando as soluções de compromisso entre a complexidade computacional e a eficiência da técnica de clusterização.