Kontrola topologii

Sterowanie topologią to technika stosowana w obliczeniach rozproszonych do zmiany podstawowej sieci (modelowanej jako graf) w celu zmniejszenia kosztów algorytmów rozproszonych, jeśli są one uruchamiane na wynikowych grafach. Jest to podstawowa technika w algorytmach rozproszonych. Na przykład (minimalne) drzewo rozpinające jest używane jako szkielet w celu zmniejszenia kosztu transmisji z O (m) do O (n), gdzie m i n to odpowiednio liczba krawędzi i wierzchołków grafu.

Termin „kontrola topologii” jest używany głównie przez społeczność badawczą bezprzewodowych sieci ad hoc i czujników. Głównym celem sterowania topologią w tej dziedzinie jest oszczędność energii, zmniejszenie zakłóceń pomiędzy węzłami oraz wydłużenie czasu życia sieci. Jednak w ostatnim czasie pojęcie to zyskuje na znaczeniu również w odniesieniu do sterowania strukturą sieci systemów elektroenergetycznych .

Budowa i utrzymanie topologii

Ostatnio algorytmy sterowania topologią zostały podzielone na dwa podproblemy: budowa topologii , odpowiedzialna za początkową redukcję, oraz utrzymanie topologii , odpowiedzialne za utrzymanie zredukowanej topologii, tak aby zachowane zostały takie cechy, jak łączność i zasięg.

Jest to pierwszy etap protokołu kontroli topologii. Po wdrożeniu początkowej topologii, zwłaszcza gdy lokalizacja węzłów jest losowa, administrator nie ma kontroli nad projektem sieci; na przykład niektóre obszary mogą być bardzo gęste, wykazując dużą liczbę nadmiarowych węzłów, co zwiększy liczbę kolizji komunikatów i dostarczy kilka kopii tych samych informacji z podobnie zlokalizowanych węzłów. Jednak administrator ma kontrolę nad niektórymi parametrami sieci: mocą transmisyjną węzłów, stanem węzłów (aktywne lub uśpione), rolą węzłów (Clusterhead, gateway, zwykły) itp. Modyfikując te parametry, topologia sieci może ulec zmianie.

W tym samym czasie topologia zostaje zredukowana, a sieć zaczyna spełniać swoje zadanie, wybrane węzły zaczynają zużywać energię: Zredukowana topologia zaczyna tracić swoją „optymalizację”, gdy tylko rozwinie się pełna aktywność sieci. Po pewnym czasie aktywności niektóre węzły zaczną działać brak energii, szczególnie w bezprzewodowych sieciach czujników z multihoppingiem, intensywne przekazywanie pakietów powoduje, że węzły znajdujące się bliżej ujścia zużywają większe ilości energii niż węzły znajdujące się dalej.Kontrola topologii musi być wykonywana okresowo w celu zachowania pożądanych właściwości takie jak łączność, zasięg, gęstość.

Algorytmy konstrukcji topologii

Istnieje wiele sposobów wykonywania konstrukcji topologii:

• Optymalizacja lokalizacji węzłów podczas fazy wdrażania
• Zmień zasięg transmisji węzłów
• Wyłącz węzły z sieci
• Stwórz szkielet komunikacyjny
• Grupowanie
• Dodawanie nowych węzłów do sieci w celu zachowania łączności ( sieci czujników Federated Wireless )

Niektóre przykłady algorytmów konstrukcji topologii to:

Oparte na zakresie Tx

• Oparte na geometrii: wykres Gabriela (GG), wykres sąsiedztwa względnego (RNG), diagram Woronoja
• Oparte na drzewie opinającym: LMST, iMST
• W oparciu o kierunek: wykres Yao i wykres najbliższego sąsiada , sterowanie topologią stożkową (CBTC), rozproszone RNG
• Sąsiednie: KNeigh, XTC
• Oparte na routingu: COMPOW

Hierarchiczny

• Oparte na CDS: A3, EECDS, CDS-Rule K
• Oparte na klastrach: Hierarchia klastrów adaptacyjnych o niskim zużyciu energii (LEACH), HEED

Przykłady graficzne

• 

  Topologia sieci pełnej mocy

• 

  Zredukowana topologia sieci dzięki minimalnemu drzewu rozpinającemu (zmiana zakresu Tx)

• 

  Zredukowana topologia sieci dzięki połączonemu zestawowi dominującemu (wybierz podzbiór węzłów obejmujący całą sieć i wyłącz niewybrane węzły)

Algorytmy utrzymania topologii

Podobnie jak w przypadku konstruowania topologii, istnieje wiele sposobów przeprowadzania konserwacji topologii:

• Globalne vs. Lokalny
• Dynamiczne vs. Statyczne vs. Hybrydowy
• Wyzwalane przez czas, energię, gęstość, przypadkowość itp.

Niektóre przykłady algorytmów utrzymania topologii to:

Światowy

• DGTRec (odtwarzanie dynamicznej globalnej topologii) :

Okresowo wybudź wszystkie nieaktywne węzły, zresetuj istniejącą zredukowaną topologię w sieci i zastosuj protokół budowy topologii.

• SGTRot (statyczny globalny obrót topologii) :

Początkowo protokół konstrukcji topologii musi utworzyć więcej niż jedną zredukowaną topologię (mam nadzieję, że możliwie jak najbardziej rozłączną). Następnie okresowo wybudzaj wszystkie nieaktywne węzły i zmieniaj obecną aktywną zredukowaną topologię na następną, jak na choince.

• HGTRotRec (Hybrid Global Topology Rotation and Recreation)

Pracuj jako SGTRot, ale gdy bieżąca aktywna zredukowana topologia wykryje pewien poziom rozłączenia, zresetuj zredukowaną topologię i wywołaj protokół konstruowania topologii, aby odtworzyć tę konkretną zredukowaną topologię.

Lokalny

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

Ten protokół, oparty na algorytmie routingu Dynamic Source Routing (DSR), odtwarza ścieżki rozłączonych węzłów, gdy węzeł ulegnie awarii.

We wszystkich powyższych protokołach można znaleźć m.in. W Atarraya zaimplementowane są dwie wersje każdego z tych protokołów z różnymi wyzwalaczami: jedna na czas, a druga na energię. Ponadto Atarraya umożliwia parowanie wszystkich protokołów budowy topologii i konserwacji topologii w celu przetestowania optymalnej polityki konserwacji dla określonego protokołu budowy; należy wspomnieć, że w wielu artykułach na temat konstrukcji topologii nie przeprowadzono żadnych badań w tym zakresie.

Dalsza lektura

Na ten temat napisano wiele książek i artykułów:

• Kontrola topologii dla bezprzewodowych sieci czujników. ACM MobiCom 2003.
• Kontrola topologii w bezprzewodowych sieciach czujników: z towarzyszącym narzędziem symulacyjnym do nauczania i badań. Miguela Labradora i Pedro Wightmana. Skoczek. 2009.
• Kontrola topologii w bezprzewodowych sieciach ad hoc i sensorowych. Paolo Santi. Wileya. 2005.
• Protokoły i architektury dla bezprzewodowych sieci czujników. Holgera Karla i Andreasa Williga. Wiley-Interscience. 2007.
• Sterowanie topologią zoptymalizowaną pod kątem wydajności dla sieci MANET z komunikacją kooperacyjną. 2011.
• Solidna kontrola topologii dla wewnętrznych bezprzewodowych sieci czujników. 2008 .

Symulacja sterowania topologią

Istnieje wiele narzędzi do symulacji sieci, ale jedno jest specjalnie zaprojektowane do testowania, projektowania i uczenia algorytmów sterowania topologią: Atarraya.

Atarraya to sterowany zdarzeniami symulator opracowany w Javie, który przedstawia nowe ramy do projektowania i testowania algorytmów sterowania topologią. Jest to aplikacja typu open source, dystrybuowana na licencji GNU V.3. Został opracowany przez Pedro Wightmana, doktora. kandydat na University of South Florida, we współpracy z dr Miguelem Labradorem. Artykuł ze szczegółowym opisem symulatora został przedstawiony w SIMUTools 2009 . Dokument można znaleźć pod tym linkiem .