Conectividade de redes mesh

Ricardo Andrade Dalla Bernardina

Redes mesh podem ser estudadas pela teoria dos grafos [1]. Para seu correto funcionamento é necessário que qualquer AP (Acess Point) tenha comunicação com qualquer outro. Por isso, é natural a relação entre a conectividade entre um AP e todos outros de uma rede mesh, e o fato do grafo associado a eles ser conexo ou não [2]. Com esta finalidade criou-se o programa connect.g [3] para avaliar se o grafo de uma rede mesh é conexo, utilizando a linguagem gvpr [4]. o programa é mostrado a seguir:

BEGIN {
     graph_t comp;
}
N {
     comp = compOf ($G, $);
     printf ("%s\n", $G.name);
     if (comp.n_nodes < $G.n_nodes) {
          printf("'%s' is not a connected graph.\n", $G.name);
     }
     else{
          printf("'%s' is a connected graph.\n", $G.name);
     }
     exit(0);
}

No passo BEGIN é declarado o grafo comp. Este grafo é usado no passo N para receber o valor da chamada de compOf() do grafo de que se deseja verificar a conectividade. A função compOf() verifica, dado um grafo g e um nó n deste grafo, quais nós de g estão conectados com o nó n. A resposta de uma chamada a compOf() é um subgrafo com os nós que estão em ligados a n, sem as arestas em g.

No programa é feita a chamada compOf ($G, $), onde $G significa o grafo sendo atualmente processado, e $ o nó atual no passo N. Como em um grafo conexo, qualquer nó deve estar ligado com todos os outros nós, o número de nós do resultado do compOf() deve ser igual ao número de nós do grafo original. Por isso, comparação

if (comp.n_nodes < $G.n_nodes)

Nela é avaliado se o número de nós do resultado de compOf() é menor que o número de nós do grafo original. Se a resposta for positiva, o grafo não é conexo. Então, é exibida na tela a mensagem de não conexão do grafo. Caso a resposta seja negativa, o número de nós do resultado do compOf() é igual ao número de nós do grafo original, pois não há possibilidade de haver maior número de nós no grafo do compOf() em comparação com o grafo original. Desse modo, a tela exibirá mensagem informando que o grafo é conexo.

É feita logo a seguir, uma chamada exit(0), para que o programa não exiba a mesma resposta até serem analisados todos os nós -- pois se o grafo não for conexo, a chamada a compOf() para qualquer um dos nós gerará um componente conexo com menos vértices do que o grafo original.

Assim, basta testar um único nó -- portanto, este é um método bastante eficiente.

Referências

[1] Redes mesh e grafos
http://tecnologiassemfio.wordpress.com/2010/01/22/redes-mesh-e-grafos/
Acessado em 25/03/2010

[2] Teoria dos grafos
https://secure.wikimedia.org/wikipedia/pt/wiki/Teoria_dos_grafos
Acessado em 25/03/2010

[3] connect.g
http://sites.google.com/site/hgfernan/arquivos/connect.g?attredirects=0
Acessado em 25/03/2010

[4] Apresentação do gvpr
http://tecnologiassemfio.wordpress.com/2010/02/05/apresentacao-do-gvpr/
Acessado em 25/03/2010