Topologikontroll

Topologikontroll är en teknik som används i distribuerad beräkning för att ändra det underliggande nätverket (modellerat som en graf) för att minska kostnaderna för distribuerade algoritmer om de körs över de resulterande graferna. Det är en grundläggande teknik i distribuerade algoritmer. Till exempel används ett (minsta) spännande träd som en ryggrad för att minska kostnaden för sändning från O(m) till O(n), där m och n är antalet kanter respektive hörn i grafen.

Termen "topologikontroll" används mest av forskarsamhället för trådlösa ad hoc- och sensornätverk. Huvudsyftet med topologikontroll i denna domän är att spara energi, minska störningar mellan noder och förlänga nätverkets livslängd. Men på senare tid har termen också vunnit dragkraft när det gäller kontroll av nätverksstrukturen för elkraftsystem .

Topologi konstruktion och underhåll

På senare tid har topologikontrollalgoritmer delats upp i två delproblem: topologikonstruktion , som ansvarar för den initiala reduktionen, och topologiunderhåll , som ansvarar för underhållet av den reducerade topologin så att egenskaper som anslutning och täckning bevaras.

Detta är det första steget i ett topologikontrollprotokoll. När den initiala topologin väl är utplacerad, speciellt när nodernas placering är slumpmässig, har administratören ingen kontroll över nätverkets utformning; t.ex. kan vissa områden vara mycket täta och visa ett stort antal redundanta noder, vilket kommer att öka antalet meddelandekollisioner och kommer att tillhandahålla flera kopior av samma information från liknande belägna noder. Administratören har dock kontroll över vissa parametrar i nätverket: nodernas överföringseffekt, nodernas tillstånd (aktiva eller vilande), nodernas roll (klusterhuvud, gateway, reguljär) etc. Genom att modifiera dessa parametrar kan topologin av nätverket kan ändras.

Samtidigt som en topologi reduceras och nätverket börjar tjäna sitt syfte, börjar de valda noderna att spendera energi: Reducerad topologi börjar förlora sin "optimalitet så snart full nätverksaktivitet utvecklas. Efter en tid att ha varit aktiva kommer vissa noder att börja köra slut på energi. Speciellt i trådlösa sensornätverk med multihopping gör intensiv paketbefordran att noder som är närmare diskbänken spenderar större mängder energi än noder som är längre bort. Topologikontroll måste utföras periodiskt för att bevara de önskade egenskaperna såsom anslutning, täckning, densitet.

Topologikonstruktionsalgoritmer

Det finns många sätt att utföra topologikonstruktion:

• Optimera nodplatserna under driftsättningsfasen
• Ändra överföringsområdet för noderna
• Stäng av noder från nätverket
• Skapa en kommunikationsryggrad
• Klustring
• Lägger till nya noder i nätverket för att bevara anslutningen ( federerade trådlösa sensornätverk)

Några exempel på topologikonstruktionsalgoritmer är:

Tx-intervallbaserat

• Geometribaserad: Gabriel-graf (GG), relativ grannskapsgraf (RNG), Voronoi-diagram
• Spännande trädbaserat: LMST, iMST
• Riktningsbaserad: Yao-graf och närmaste granne-graf , konbaserad topologikontroll (CBTC), distribuerad RNG
• Grannbaserad: KNeigh, XTC
• Routningsbaserad: COMPOW

Hierarkisk

• CDS-baserad: A3, EECDS, CDS-regel K
• Klusterbaserad: Low Energy Adaptive Clustering Hierarki (LEACH), HEED

Grafiska exempel

• 

  Full power nätverkstopologi

• 

  Minskad nätverkstopologi via Minimal Spanning Tree (ändring i Tx Range)

• 

  Minskad nätverkstopologi via Connected Dominating Set (Välj en delmängd av noder som täcker hela nätverket och stäng av icke-valda noder)

Topologi underhållsalgoritmer

På samma sätt som topologikonstruktion finns det många sätt att utföra topologiunderhåll:

• Global vs. Lokal
• Dynamisk vs. Statisk vs. Hybrid
• Utlöst av tid, energi, densitet, slumpmässigt, etc.

Några exempel på topologiunderhållsalgoritmer är:

Global

• DGTRec (Dynamic Global Topology Recreation) :

Väck med jämna mellanrum alla inaktiva noder, återställ den befintliga reducerade topologin i nätverket och tillämpa ett topologikonstruktionsprotokoll.

• SGTRot (Static Global Topology Rotation) :

Inledningsvis måste topologikonstruktionsprotokollet skapa mer än en reducerad topologi (förhoppningsvis så osammanhängande som möjligt). Väck sedan med jämna mellanrum alla inaktiva noder och ändra den nuvarande aktiva reducerade topologin till nästa, som i en julgran.

• HGTRotRec (Hybrid Global Topology Rotation and Recreation)

Arbeta som SGTRot, men när den nuvarande aktiva reducerade topologin upptäcker en viss nivå av frånkoppling, återställ den reducerade topologin och anropa topologikonstruktionsprotokollet för att återskapa just den reducerade topologin.

Lokal

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

Detta protokoll, baserat på routingalgoritmen Dynamic Source Routing (DSR), återskapar vägarna för frånkopplade noder när en nod misslyckas.

I alla ovanstående protokoll finns i. I Atarraya är två versioner av vart och ett av dessa protokoll implementerade med olika utlösare: en efter tid och den andra med energi. Dessutom tillåter Atarraya sammankoppling av alla protokoll för topologikonstruktion och topologiunderhåll för att testa den optimala underhållspolicyn för ett visst konstruktionsprotokoll; det är viktigt att nämna att många artiklar om topologikonstruktion inte har utfört några studier i detta avseende.

Vidare läsning

Många böcker och uppsatser har skrivits i ämnet:

• Topologikontroll för trådlösa sensornätverk. ACM MobiCom 2003.
• Topologikontroll i trådlösa sensornätverk: med ett kompletterande simuleringsverktyg för undervisning och forskning. Miguel Labrador och Pedro Wightman. Springer. 2009.
• Topologikontroll i trådlösa ad hoc- och sensornätverk. Paolo Santi. Wiley. 2005.
• Protokoll och arkitekturer för trådlösa sensornätverk. Holger Karl och Andreas Willig. Wiley-Interscience. 2007.
• Kapacitetsoptimerad topologikontroll för MANET med kooperativ kommunikation. 2011.
• Robust topologikontroll för trådlösa sensornätverk inomhus. 2008 .

Simulering av topologikontroll

Det finns många nätverkssimuleringsverktyg, men det finns ett specifikt designat för att testa, designa och lära ut topologikontrollalgoritmer: Atarraya.

Atarraya är en händelsedriven simulator utvecklad i Java som presenterar ett nytt ramverk för att designa och testa topologikontrollalgoritmer. Det är en öppen källkodsapplikation, distribuerad under GNU V.3-licensen. Det utvecklades av Pedro Wightman, en Ph.D. kandidat vid University of South Florida, i samarbete med Dr. Miguel Labrador. Ett papper med den detaljerade beskrivningen av simulatorn presenterades i SIMUTools 2009 . Tidningen hittar du i denna länk .