Satellite networks still are subject of study and research, both in relation to the network itself and to the traffic demand, because it must be resilient to failures and capable of routing with low delay. Therefore, it is important to examine satellite network topologies and their properties. In this work we propose to model a satellite network, the Spaceway NGSO, using twin graphs, since this graph class has important properties such as fault tolerance, performance, cost and scalability.
e penetração geográfica [Net88].
Devido às funcionalidades e capacidade de comunicação mencionadas, os satélites artificiais se tornaram cruciais com o advento da globalização. Porém, com o indispensável acesso a redes de computadores e internet, houve o surgimento da latência como fator limitante na comunicação. Outro fator interligado com atrasos e que compromete a comunicação são as falhas. Logo, essas redes ainda precisam de melhorias.
Portanto, vale a pena examinar a topologia de redes satélites a fim de otimizá-las. É com esse objetivo que surge a ideia de modelagem das redes de satélites por grafos. 1.1
A rede de satélites Spaceway (Non-Geostationary Orbit) NGSO Dentre diversas redes de satélites destacamos a rede Spaceway NGSO (Non-Geostationary Orbit) para modelagem [Woo01]. A escolha se baseou no fato de que seu número de satélites é consideravelmente inferior quando comparado com outras redes existentes.
Essa rede possui 20 satélites distribuídos igualmente em 4 órbitas, classificadas como MEO (Medium Earth Orbits ). Estas órbitas podem permitir uma cobertura total da Terra com menor quantidade de satélites de maior tamanho. Nessa classificação, os satélites têm uma cobertura maior em relação às redes LEO (Low Earth Orbits ), devido ao aumento da altitude. Porém, por possuir menos satélites, pelos caminhos serem maiores e por se movimentarem a uma velocidade menor, o atraso resultante é maior [Woo01].
A Figura 1 apresenta a topologia da rede Spaceway NGSO em um dado momento do tempo, sendo as ligações intra-plano (mesmo plano orbital) representadas pelas linhas pretas e as ligações interplano (diferentes planos orbitais) representadas pelas linhas azuis. (a) Projeção equidistante azimutal (b) Projeção longitude x latitude A Teoria dos grafos propicia a modelagem e resolução de diversos tipos de problemas. Um grafo é composto basicamente por um conjunto de vértices e um conjunto de arestas, onde os vértices representam os objetos de algum tipo de problema e as arestas representam as relações entre esses objetos. Diante disso, podemos representar os satélites por vértices e a comunicação entre eles pelas arestas. Com a modelagem da rede de comunicação por grafos, podemos calcular diversos invariantes (em grafos, são parâmetros numéricos que não levam em conta a forma como os nós estão rotulados) extraídos da teoria dos grafos. Assim, com a análise dos invariantes (como por exemplo, o número de arestas, o grau máximo, distância média, diâmetro, etc), podemos descobrir quais são importantes para determinar caminhos mais eficientes, de maior confiabilidade, robustez e menor custo, dentro de suas limitações.
Dentre as inúmeras métricas, destacamos betweenness centrality de arestas, conectividade algébrica, índice de Estrada, resistência e closeness centrality. A betweenness centrality de arestas quantifica o número de vezes que uma aresta participa do caminho mais curto entre cada par de vértices [Fre77]. A conectividade algébrica é o segundo menor autovalor da matriz Laplaciana do grafo [Fie73]. O índice de Estrada de um grafo G de n nós e autovalores 1; :::; n é EE(G) = Pin=1 e 1 [dlPGR07]. A distância de resistência entre dois nós se assemelha a comparar um grafo como uma grade de resistência, onde calcula-se a resistência entre esses dois nós [Vos16]. A métrica closeness centrality refere-se à soma das distâncias geodésicas de um nó a todos os outros n 1 nós da rede [BH14].
Dentro do universo dos grafos, os grafos gêmeos se destacam devido a suas propriedades de tolerância a falhas, desempenho, custo e escalabilidade. Por definição, os grafos gêmeos são grafos 2geodesicamente-conexos minimais, ou seja, para cada par de nós não adjacentes do grafo, existem no mínimo 2 geodésicas (menores caminhos) disjuntas que os interligam e, além disso, são os grafos com o menor número de arestas a possuírem tal propriedade [Pai12]. Dessa forma, caso ocorra uma falha em qualquer nó ou aresta, a comunicação entre dois nós não adjacentes não é comprometida, pois a ligação entre eles pode ser substituída por outra geodésica, sem prejuízo algum. A Figura 2 exemplifica um grafo gêmeo de 14 nós e 24 arestas. Observe que, a cada par de nós não adjacentes, há pelo menos duas geodésicas disjuntas os conectando.
Grafos gêmeos também garante escalabilidade, uma vez que, ao adicionar um nó a um grafo gêmeo de n nós, podemos gerar um outro grafo gêmeo de n + 1 nós, além de podermos gerar um grafo gêmeo a partir de dois outros.
Pensando nessas propriedades apresentadas de grafos gêmeos, podemos associar os satélites e suas ligações de uma rede de satélites mais simples, como a Spaceway NGSO, aos nós e arestas de grafos gêmeos. Dessa forma, ao trabalhar com modelagem matemática em grafos, buscamos otimizar a rede de satélites. 2
Este trabalho tem como objetivo geral verificar se os grafos gêmeos são uma boa alternativa para o projeto de topologias de redes de satélites.
Como objetivo específico buscaremos modelar uma rede de comunicação via satélites de pequeno porte, a rede Spaceway NGSO, com um grafo gêmeo correspondente e analisar quais invariantes de grafos estão relacionadas ao bom desempenho da rede citada. Como a rede Spaceway NGSO possui 20 satélites, buscamos relacioná-la aos grafos gêmeos de 20 nós, que ao todo são 1770 grafos. Baseado na observação de características topológicas de outras redes de satélites, optamos por limitar nossa análise a grafos gêmeos com grau máximo entre 4 e 6. Assim, o conjunto inicial de 1770 grafos foi reduzido para 510.
A fim de restringir ainda mais nosso conjunto de busca, utilizamos o algoritmo Nearest Neighbors para selecionar os k = 30 grafos gêmeos mais semelhantes à rede Spaceway [CH67]. As variáveis de entrada consideradas para a aplicação desse algoritmo foram métricas de grafos calculadas para os 510 grafos gêmeos e para a rede original. As 23 métricas calculadas inicialmente passaram por um processo de seleção de variáveis que consistiu na exclusão de métricas cujo valor obtido para a Spaceway era considerado um outlier no conjunto. Após esse processo, apenas as métricas máximo e média da betweenness centrality de arestas, conectividade algébrica, índice de Estrada, resistência mínima e closeness centrality máximo e mínimo foram utilizadas como entrada do algoritmo.
Por fim, depois da seleção desses 30 grafos gêmeos, foi preciso associar os nós de cada grafo gêmeo aos nós da rede Spaceway NGSO. Para isso, foi aplicado o chamado Algoritmo Genético (AG) [Mit98].
O AG parte de uma população inicial constituída por alguns indivíduos (primeiras soluções). No nosso caso, cada indivíduo da população foi representado por um vetor com o tamanho igual a quantidade de nós, ou seja, 20. O valor contido no vetor representa os satélites, e o valor do índice representa a posição fixa de cada satélite, que indica quais são suas coordenadas. Também é criado um vetor com os satélites e suas respectivas posições da rede original. O vetor original é inalterável, servindo como base de comparação do vetor indivíduo.
Esses indivíduos são submetidos a uma avaliação Fitness, ou seja, a função objetivo, que calcula a aptidão de cada um. A aptidão ainda está em estudo, sendo decidida pelo número de arestas em comum entre as duas redes (quanto maior, mais apto), ou pela soma do cálculo da distância de cada ligação entre cada par de satélite (quanto menor, mais apto).
Após, é feita uma seleção dos progenitores da próxima população, onde os mais aptos possuem maior probabilidade de cruzamento. No cruzamento, os indivíduos são combiandos entre si, aumentando a probabilidade de gerarem indivíduos ainda melhores que a população anterior. Em seguida, alguns indivíduos são escolhidos aleatoriamente para terem seus genes modificados, a fim de aumentar a diversidade da população. Após todo esse processo, se o critério de parada for atendido, o indivíduo mais apto é a solução. Caso contrário, o processo continua até atingir o critério de parada. O critério de parada utilizado é o número de ciclos que o melhor indivíduo da população não melhora a sua aptidão. Assim, com o indivíduo solução sabemos as coordenadas de cada nó do grafo gêmeo, permitindo desenharmos a nova rede de maneira similar à ilustrada na Figura 1 para a rede original.
Após a conclusão da modelagem, serão realizadas comparações entre métricas de desempenho da rede original encontrada na literatura e das topologias selecionadas a partir da etapa de modelagem. 4
Após a conclusão destes estudos iniciais, pretende-se expandir as análises utilizando modelos de grafos variantes no tempo, que permitam incorporar o comportamento dinâmico característico das redes de satélites.
Este trabalho foi parcialmente financiado pelo CNPq, FAPES e Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) - Finance Code 001. [BH14] [CH67]
pattern classification. IEEE Transactions on Information Theory, 13(1):21–27, 1967. [dlPGR07] J. A. de la Peña, I. Gutman, and J. Rada.
Estimating the estrada index. Linear Algebra and its Applications, 427(1):70 – 76, 2007. [Fie73]
M. Fiedler. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(98):298 – 305, 1973.
na teoria (espectral) de grafos no projeto e análise de topologias físicas para redes ópticas. Doutorado, Universidade Federal do Espírito Santo, 2012. Lloyd Wood. Internetworking with satellite constellations. Doutorado, University of Surrey, 2001.