Appianamento del grafo di routing in una rete domotica

Spesso un algoritmo di routing, all’interno di una rete wireless di sensori, presente ad esempio in un ambiente domotico, viene realizzato elidendo alcuni dei collegamenti presenti nella rete stessa al fine di rendere il grafo che identifica le modalità di comunicazione all’interno della rete un grafo planare, per cui sono previsti algoritmi di routing relativamente semplici ed efficaci.

Si definisce planare un grafo per il quale, connettendo con una linea tutte le coppie di punti tra cui è definito un legame di comunicazione, non si realizzino intersezioni di linee. Il piano di comunicazione risulta a questo punto suddiviso in più parti, schematizzabili come poligoni.

Immaginando anche che ciascuno di tali poligoni sia convesso, può essere adottato l’algoritmo di “convex perimeter routing”. Ovvero si procede lungo il perimetro del poligono a cui appartiene il nodo sorgente s fino a che non si raggiunge il nodo destinazione d o viene attraversato il segmento che unisce il nodo sorgente al nodo destinazione.

In questo caso si passa al poligono successivo lungo la linea ideale sd. Da notare anche però come le prestazioni dell’algoritmo siano difficilmente valutabili in un caso generale; persino la scelta di procedere in senso orario o antiorario può risultare determinante.

Le prestazioni risultano però notevolmente migliorate considerando che ciascun vertice del percorso ottimo da s a d giace in L, con L definita come l’ellisse di foci s e d. Qualora venga toccato o varcato il bordo dell’ellisse, è opportuno invertire il senso di percorrenza del perimetro, ad esempio da orario ad antiorario. Tale algoritmo è detto “adaptive perimeter routing”.