Controllo della topologia

Il controllo della topologia è una tecnica usata principalmente nelle Wireless sensor network al fine di ridurre la topologia di rete e risparmiare energia, diminuire le interferenze ed estendere la vita della rete. L'obiettivo principale è ridurre il numero di nodi e collegamenti attivi, preservando le risorse risparmiate per usi futuri.

Costruzione e manutenzione della topologia

Recentemente, il controllo della topologia è stato diviso in due sottoproblemi: "costruzione della topologia", ovvero la riduzione iniziale della topologia, e "manutenzione della topologia", cioè la gestione e il mantenimento della topologia ridotta ottenuta in fase di costruzione in modo che siano preservate caratteristiche come copertura e connettività.

Questo è la prima fase di un protocollo per il controllo della topologia. Una volta che la topologia iniziale è instaurata, specialmente quando la posizione dei nodi è casuale, l'amministratore non ha più il controllo su di essa; ad esempio, alcune aree potrebbero essere molto dense, ovvero con un alto numero di nodi ridondanti. Questo potrebbe causare l'incremento di collisioni di pacchetti e la conseguente necessità di frequenti ritrasmissioni. Ciononostante, l'amministratore ha il controllo su alcuni parametri della rete: la potenza di trasmissione dei nodi, lo stato dei nodi (attivo o sleep) e il ruolo dei nodi (regolare, gateway, clusterhead, etc.). Grazie alla modifica di questi parametri, la topologia della rete può cambiare.

Appena finita la fase di riduzione della topologia e la rete comincia a funzionare, i nodi cominciano a trasmettere e quindi a spendere energia. In questo istante la topologia "ottimale" che si era ottenuta cessa di essere tale. Specialmente nelle Wireless sensor network con multi-hop, i nodi che sono più vicini al sink consumano maggiore energia rispetto a quelli periferici. Questo problema è conosciuto in letteratura col nome di hot-spot problem. La rete deve quindi ricostruire periodicamente la sua topologia al fine di preservare la connettività, la copertura, la densità dei nodi e qualunque altra metrica l'applicazione richieda.

Algoritmi per la costruzione della topologia

Ci sono molti modi per eseguire la costruzione della topologia, e l'uno non esclude l'altro:

• Cambio del raggio di trasmissione dei nodi;
• Spegnimento di alcuni nodi della rete;
• Creazione di una dorsale;
• Clustering, ecc.

Alcuni esempi di algoritmi di costruzione della topologia sono:

Basati sul raggio di trasmissione

• Basati sulla geometria: Grafo di Gabriel (GG), Grafo di vicinanza relativa (RNG), Diagramma di Voronoi
• Basati sullo Spanning Tree: LMST^[1], iMST^[2], ipercubo incompleto dinamico scalabile-Hypercast^[3]
• Basati sulla direzione: Grafo di Yao, Grafo del vicino più prossimo, Cone Based Topology Control (CBTC), RNG distribuito
• Basati sui vicini: KNeigh^[4], XTC^[5]
• Basati sul routing: COMPOW^[6]

Gerarchici

• CDS-based: A3^[7], EECDS^[8], CDS-Rule K^[9]
• Cluster-based: Low Energy Adaptive Clustering Hierarchy (LEACH), HEED^[10]

Esempi grafici

• 
  Topologia di rete a piena potenza di trasmissione
• 
  Topologia di rete ridotta in accordo al Minimal Spanning Tree grazie alla modifica del raggio di trasmissione.
• 
  Topologia di rete ridotta in accordo al Connected Dominating Set (Scelta di un sottoinsieme di nodi tali che coprano tutta la rete e spegnimento dei nodi non scelti)

Algoritmi per la manutenzione della topologia

Analogamente alla costruzione della topologia, ci sono molti metodi per effettuare la manutenzione della topologia:

• Globali o locali
• Dinamici, statici o ibridi
• Innescati in base a timer, in base all'energia, alla densità, causali, ecc.

Alcuni esempi di algoritmi per la manutenzione della topologia sono:

Globali

• DGTRec (Dynamic Global Topology Recreation):

Periodicamente, si attivano i nodi inattivi, si azzera la topologia corrente e si applica un algoritmo di costruzione della topologia.

• SGTRot (Static Global Topology Rotation):

Inizialmente, l'algoritmo di costruzione della topologia deve creare più di una topologia ridotta. In seguito, periodicamente, si attivano i nodi inattivi e si usa la topologia successiva, ciclicamente, come i ritmi delle luci in un albero di natale.

• HGTRotRec (Hybrid Global Topology Rotation and Recreation)

Funziona come SGTRot, ma quando la topologia corrente rileva un certo livello di disconnessione, azzera la topologia e invoca l'algoritmo di costruzione della topologia per ricostruire quella particolare topologia.

Locali

• DL-DSR (Dynamic Local DSR-based TM)

Questo protocollo, basato sul Dynamic Source Routing (un algoritmo di routing), ricrea i percorsi dei nodi disconnessi quando un nodo si spegne.

In Atarraya^[11], sono implementate due versioni di ognuno di questi protocolli mediante inneschi differenti: uno temporale, l'altro energetico. In aggiunta, Atarraya permette l'associazione di ogni algoritmo per la costruzione della topologia con qualsiasi algoritmo per la manutenzione della stessa, al fine di testare le scelte migliori per un particolare protocollo di costruzione della topologia.

Strumenti di simulazione

Pur esistendo molti strumenti di simulazione per le reti, solo Atarraya^[11] è progettato specificatamente per la progettazione e l'analisi di protocolli per il controllo della topologia.

Note

1. [1], Local Minimal Spanning Tree
2. [2], Iterative Minimum Spanning Tree
3. [3], HyperCast: A Protocol for Maintaining Multicast Group Members in a Logical Hypercube Topology, J. Liebeherr, Tyler K. Beam, July 1999.
4. [4]^{[collegamento interrotto]}, KNEIGH
5. Copia archiviata (PDF), su dcg.ethz.ch. URL consultato il 30 aprile 2009 (archiviato dall'url originale il 5 luglio 2007)., XTC
6. [5], COMPOW
7. [6], A3: A topology construction protocol for WSN
8. [7], EECDS
9. [8], CDS-Rule K
10. [9], HEED
11. [10], Atarraya, a simulator for topology control in wireless sensor networks

Bibliografia

• Topology Control in Wireless Sensor Networks: with a companion simulation tool for teaching and research. Miguel Labrador and Pedro Wightman. Springer. 2009.
• Topology Control in Wireless Ad Hoc and Sensor Networks. Paolo Santi. Wiley. 2005.
• Protocols and Architectures for Wireless Sensor Networks. Holger Karl and Andreas Willig. Wiley-Interscience. 2007.