Connectivity of mesh networks

Ricardo Andrade Dalla Bernardina

Mesh networks, and particularly wireless mesh networks, can be studied using the graph theory [1]. If they’re to work correctly, any AP (or “Access Point”) should have communication with any other, even if not directly. Due to that, it is natural the relationship between the connectivity in a mesh network and the connectivity of the graph associated to it [2]. With that in mind, connect.g [3], a small program, was developed to evaluated whether a graph, eventually associated with a mesh network, is connected or not, using the gvpr programming language [4]. Here follows the program:

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);
}

In the BEGIN block, the graph comp is declared. This graph is used in the N block, where it receives the return of a call to compOf() over the graph the connectivity is evaluated. Given a graph g and a node n in this graph, he function compOf() evaluates which nodes of g are connected, directly or not, to n. This function yields a subgraph of g with only the nodes connected to n. This subgraph has not the edges in g, and if they are needed, one should issue a call to induce() onto that subgraph.

The program issues a call to compOf($G, $), where $G means the graph currently being processed, and $ the current node in the context of N. In a connected graph, any node is, by definition, connected to each other, the number of nodes of the subgraph resulting from this call to compOf() should be equal to the number of nodes in the original graph. So, the comparison

if (comp.n_nodes < $G.n_nodes)

It evaluates whether the number of nodes in the result of compOf() is smaller than the number of nodes in the original graph. If the answer is positive, the graph is not connected. Then, the program displays on screen a message stating the graph is not connected. In case the answer is negative, the number of nodes in compOf() result is equal to the number of nodes in the original graph, since it’s not possible that a subgraph has a larger number of nodes than its parent graph. So the program will display a message informing the graph is connected.

Then in the program is issued a call to exit(0) so that the program doesn’t issue the same message for all the nodes — for if the node is not connected, the call compOf() for each of the nodes will generate a connected component with less vertices than the original graph.

So, it is necessary to test a single node — what means this is a rather efficient method.

Referências

[1] Wireless mesh networks and graphs
https://wirelesstechnol.wordpress.com/2010/01/25/wireless-mesh-networks-and-graphs/
Visited on 03/29/2010

[2] Graph theory
https://secure.wikimedia.org/wikipedia/pt/wiki/Teoria_dos_grafos
Visited on 03/29/2010

[3] connect.g
http://sites.google.com/site/hgfernan/arquivos/connect.g?attredirects=0
Visited on 03/29/2010

[4] Introducing gvpr
https://wirelesstechnol.wordpress.com/2010/02/22/presenting-gvpr/
Visited on 03/29/2010

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.