Archive for the ‘teoria dos grafos’ Category

Conectividade de redes mesh

26 de março de 2010

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 os 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 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, a 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
https://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
https://tecnologiassemfio.wordpress.com/2010/02/05/apresentacao-do-gvpr/
Acessado em 25/03/2010

Licença Creative Commons
Esta obra foi licenciada com uma Licença Creative Commons – Atribuição – Partilha nos Mesmos Termos 3.0 Não Adaptada.

Apresentação do gvpr

5 de fevereiro de 2010

Ricardo Andrade Dalla Bernardina

DOT [1] é uma linguagem que permite definir grafos [2]. Ela foi usada inicialmente no programa de mesmo nome dot, hoje parte do pacote graphviz [3], que tem muitas ferramentas para visualização e manipulação de grafos.

Um exemplo de arquivo para construção de grafos é explicado aqui. A primeira coisa que deve ser feita é dar uma nome para o grafo, e depois de escolhido (supondo que seja g para o exemplo ) colocar:

    graph g {}

Tudo que virá depois no arquivo estará dentro das chaves após graph g.

Após isso é necessário criar os nós e para isso escrevemos:
X [label="node"]; — sendo X o identificador do nó e node o nome do nó.

Podem ser incluídos tantos nós quanto forem necessários.

Após isso, para se colocar as arestas deve-se escrever os identificadores dos nós que estão ligados pela aresta (não está sendo considerado grafo dirigido) e entre eles colocar “--“; isto é: dois hífens seguidos. Por ex.: X -- Y; é a aresta que conecta os nós X e Y.

Após isso é só salvar o arquivo, rodar um programa de visualização como o dot [4] e o grafo estará pronto — por exemplo, na forma de uma imagem JPEG.

Abaixo encontra-se uma figura do código [5]:
41.jpg

No pacote graphviz encontra-se a ferramenta gvpr [6], muito poderosa, mas pouco conhecida, que permite manipular e — de forma geral — reescrever grafos.

Agora será mostrada uma pequena apresentação do programa descstat.g [7], que usa a ferramenta gvpr para calcular o maior grau e menor grau de um grafo qualquer, além de calcular a média, variância, desvio padrão e coeficiente de variação dos graus dos nós dos grafos.

Antes de tudo vale lembrar que o gvpr só interpreta grafos na linguagem DOT, sendo inútil para outras linguagens de definição de grafos. No ambiente gvpr, é definida uma linguagem de programação, que possui os seguintes elementos

  • BEGIN, que é realizado apenas uma vez no começo da programa;
  • END que é realizado apenas no final do programa e uma única vez também;
  • existe também o BEG_G, que é realizado para todos os grafos no começo de cada um;
  • e o END_G, que do mesmo modo é realizado para todos os grafos, só que no final deles;
  • por último tem o N que entra em todos os nós do grafo.

BEG_G e END_G devem estar entre BEGIN e END. Por sua vez, N deve estar entre BEG_G e END_G. A sintaxe de comandos e declarações é bastante similar, quando não igual, àquela do C [8].

Assim no programa descstat.g foram declaradas as variáveis no BEGIN, os valores delas foram inicializados no BEG_G, pois eles devem ser reinicializados no início de cada grafo. Dentro do N são totalizados os graus de todos os nós de cada grafo. O grau de um nó é obtido pela expressão $.degree, onde $ significa o nó atual e degree é o grau do nó. Por sua vez, $G significa o grafo atual. Esses graus são necessários para os cálculos que são o objetivo do programa. Todos eles são finalizados no END_G, que também apresenta os valores na tela. O trecho em N é apresentado a seguir:

N {
    if ($.degree > maxd) {
        maxd = $.degree;
    }

    if ($.degree < mind) {
        mind = $.degree;
    }

    mean += $.degree;
    var  += $.degree * $.degree;
}

Referências

[1] The DOT Language
Acessado em 29/01/2010

[2] Teoria dos grafos
Acessado em 29/01/2010

[3] Graphviz – Graph Visualization Software
Acessado em 29/01/2010

[4] Drawing graphs with dot
Acessado em 02/02/2010

[5] 4.dot
Acessado em 29/01/2010

[6] gvpr(1) – Linux man page
Acessado em 29/01/2010

[7] descstat.g
Acessado em 02/02/201

[8] C (linguagem de programação)
Acessado em 02/02/2010

Redes mesh e grafos

22 de janeiro de 2010

Hilton Garcia Fernandes

As redes sem fio do tipo mesh (a expressão em português “redes sem fio em malha” não tem sido usada no Brasil) [1] conectam entre si pontos de acesso (AP) [2] diretamente por rádio, evitando assim a necessidade de conexões cabeadas e ampliando a cobertura da rede sem fio para não apenas um AP, mas vários.

O conceito é muito amplo, mas normalmente é aplicado apenas a redes sem fio locais, as chamadas WLAN, principalmente do tipo Wi-Fi [3].

Os computadores clientes de um AP sem conexão direta à Internet podem obter essa conexão através de um outro AP que a possua, pelo processo chamado de hopping, ou pulo: o AP sem conexão com a Internet repassa os pacotes de informação para aquele que a possui. Depois, o AP conectado repassa os pacotes da resposta da Internet para aquele AP que sem conexão direta, que por sua vez, repassa ao cliente que solicitou a conexão.

As redes sem fio em malha podem ser estudadas de várias formas. Uma das mais interessantes, com certeza é a via dos grafos [4].

A teoria dos grafos é baseada em conceitos simples e poderosos. Um grafo pode ser simplesmente descrito como um conjunto de objetos que se conecta em pares. Os objetos são chamados vértices (ou nós) e as conexões entre eles são chamadas arestas.

Em termos das redes mesh, cada AP seria um nó e cada conexão entre eles seria uma aresta. Grafos que modelam redes mesh podem ser considerados não dirigidos, pois se há conexão de um primeiro AP para um segundo, com certeza há do segundo para o primeiro.

Grafos podem ser conexos, quando de um nó é possível chegar a qualquer outro, mesmo que seja necessário passar por mais de uma aresta. Grafos com o mínimo de arestas necessário para serem conexos são chamados árvores [5]. Em termos matemáticos, se n é o número de nós de uma árvore, o número de arestas dela será n – 1.

Ora, redes mesh têm como propriedade interessante a tolerância a falhas. Em outras palavras, isto significa que há vários caminhos entre um AP e outro. Por exemplo, entre um AP sem conexão com a Internet e outro conectado. Se um dos caminhos não for mais possível, haverá outra alternativa, eventualmente menos rápida, mas ainda assim capaz de permitir o acesso à Internet.

Por isso, uma rede mesh tem que ter mais do que o mínimo de conexões possível, para que haja redundância em pelo menos uma conexão. Ou seja: nestes termos, a rede mesh do grafo mencionado teria que ter pelo menos n arestas. Uma rede totalmente conectada [6] é uma rede com
n*(n – 1)/2
conexões, o que não é viável para redes maiores.

Outro ponto que favorece a qualidade de uma rede mesh é que a quantidade de conexões seja o melhor distribuída possível, sem que um único nó contenha todas conexões redundantes — pois este nó será um ponto de falha da rede; se ele cair, cairá parte importante da rede. O número de conexões de um dado nó é chamado grau desse nó.

O programa descstat.g [7] calcula estatísticas básicas dos nós de um dado grafo — uma das mais importantes é chamada coeficiente de variação [8], e mede a disparidade dos graus dos vértices de um grafo. Idealmente, o coeficiente de variação seria zero para uma rede onde todos nós tivessem o mesmo número de conexões.

O programa connect.g [9] avalia se um dado grafo é ou não conexo. No caso de redes mesh, identifica se todos pontos da rede se vêem ou não.

Tanto descstat.g [7] quanto connect.g [9] foram escritos usando-se o ambiente de programação gvpr, desenvolvido por Emden R. Gansner, disponível no pacote graphviz [10], um Software Livre poderoso, flexível e muito usado para visualização de grafos.

Referências

[1] Wireless mesh network

[2] Wireless access point

[3] Wi-Fi

[4] Teoria dos grafos

[5] Árvore (teoria dos grafos)

[6] Fully-connected network

[7] descstat.g

[8] Coeficiente de variação

[9] connect.g

[10] graphviz

Licença Creative Commons
Esta obra foi licenciada com uma Licença Creative Commons – Atribuição – Partilha nos Mesmos Termos 3.0 Não Adaptada.