Wielkoskalowy, energooszczędny routing sieci czujników przy użyciu procesora kwantowego

Summary

To badanie dostarcza metody wykorzystania procesora kwantowego do obliczania tras dla różnych dynamik ruchu, które działają skuteczniej niż klasyczne metody w literaturze, aby zmaksymalizować żywotność sieci.

Abstract

Metoda oszczędzania energii w sieci czujników, która jest hybrydą klasycznego komputera i procesora kwantowego, okazała się działać lepiej niż algorytm heurystyczny wykorzystujący klasyczny komputer. W niniejszej pracy przedstawiono i uzasadniono kontekst techniczny znaczenia metody. Następnie etapy eksperymentalne są demonstrowane w sekwencji operacyjnej z ilustracjami, jeśli zajdzie taka potrzeba. Metoda została zwalidowana pozytywnymi wynikami w losowo wygenerowanym zestawie topologii sieci. Udane wyniki eksperymentalne tej metody zapewniły lepsze podejście do problemów związanych z maksymalizacją żywotności sieci czujników i wykazały, że obecny stan techniki procesor kwantowy jest w stanie rozwiązać duże praktyczne problemy inżynieryjne z zaletami, które zastępują obecne metody w literaturze. Innymi słowy, przewaga kwantowa może być wykorzystana w najlepszy możliwy sposób. Wyszedł poza etap dowodu koncepcji do dowodu wykonalności.

Introduction

Oszczędność energii w sieciach czujników była bardzo krytyczną kwestią w projektowaniu¹. Klasyczne metody zwykle rozwiązują problem za pomocą podejścia ad hoc^2,3,4,5^,6. To powiedziawszy, metody te emulują węzły czujników jako indywidualnie zarządzane inteligentne zasoby, które mogą również współpracować, aby służyć zarówno interesom jednostki, jak i społeczności. Ze względu na zmienne środowisko, w którym działają czujniki, w niektórych pracach wprowadza się algorytmy losowe w celu wychwycenia niepewności środowiskowych, podczas gdy w innych biointeligencja jest zapożyczana do opracowania algorytmów heurystycznych, które mogłyby osiągnąć akceptowalne dla zdrowego rozsądku wyniki⁷. Aby zilustrować to dalej, w przypadku tych algorytmów losowych, z jednej strony, niepewności środowiskowe mogą nie być tak losowe, jak sekwencja losowa generowana przez klasyczny procesor, z drugiej strony, nawet jeśli niepewności środowiskowe są absolutnie losowe, nie można ich uchwycić za pomocą symulatora procesów losowych generowanego przez klasyczny procesor; W przypadku tych algorytmów biointeligencji, po pierwsze, nie przeprowadzono rygorystycznej analizy matematycznej, aby dowód koncepcyjny był skuteczny, po drugie, zbieżność do prawdy lub granica tolerancji błędu mogą być skonfigurowane tylko przy podstawie świadomej prawdy podstawowej - chociaż znaczna liczba prac w literaturze wykazała w pewnym stopniu działanie tych algorytmów heurystycznych. Po pierwsze, algorytmy te są analizowane (a nie symulowane) pod kątem dobrze zdefiniowanych scenariuszy przypadków użycia, zatrzymują się na pewnych kryteriach, które nadal są warte rozważenia w dalszych badaniach, po drugie, jak wspomniano wcześniej, większość algorytmów nie została zweryfikowana pod kątem symulacji oprogramowania, które można łatwiej wdrożyć w mikroprocesorach, które sprawiają, że czujnik staje się jego bytem⁸.

Nie bierzemy tutaj pod uwagę uczenia maszynowego (ML), ponieważ wymaga ono analizy danych, która wymaga stosunkowo dużej mocy obliczeniowej, która nie jest przenośna w urządzeniach sensorowych⁹.

Aby rozwiązać wyżej wymienione problemy, udostępniamy hybrydowy algorytm kwantowy. Algorytm jest hybrydowy w tym, że mechanizm wyboru głowicy klastra jest implementowany przy użyciu klasycznego algorytmu losowego podczas obliczeń routingu przeprowadzanych przy użyciu procesora kwantowego po skonfigurowaniu topologii sieci. Metodę uzasadnia się w następujący sposób: (1) Jak omówiono w pierwszym akapicie dotyczącym niepewności środowiskowej, nie chcemy dalej próbować zastosować generatora sekwencji kwantowych do uchwycenia dynamiki środowiska, ponieważ może on być historycznie identyfikowalny. Dynamika środowiskowa, którą można historycznie prześledzić, została uzasadniona przez różne prace badawcze w zakresie uczenia maszynowego w dziedzinie nauk o sieciach. Na obecnym etapie pozostajemy przy klasycznym podejściu. (2) Dokładna metoda, która bazuje na abstrakcyjnej analizie matematycznej, gwarantuje dojście do podstawowej prawdy. Kwantowa fizyka doświadczalna była do tej pory w wyrafinowany sposób wspierana przez matematykę fizyczną. Co więcej, istnieją aplikacje algorytmiczne, takie jak Shor algorithm¹⁰, aby udowodnić tę zaokrągloną teorię.

Poniżej znajduje się odpowiednia ilość ankiety literatury dla porównania. Protokół HEESR zaproponowany przez ¹¹ ma wyraźne zalety w wynikach, ale autorzy dobrze określili parametry konfiguracji symulacji, na przykład dokładną funkcję rozkładu losowego pozycji węzła, prawidłowe uzasadnienie procentu głowy klastra p (0,2%) oraz parametr skalowania dla rozkładu poziomu energii (1-2 dżule) między węzłami a_i. Zabronił on autorowi dalszego powielania eksperymentów i przeprowadzania porównania. Mechanizm routingu mocy¹² wykorzystuje metodę dopasowania krzywej do przybliżania zbieżnych funkcji ciągłych z dyskretnych zestawów danych uzyskanych z nieokreślonej przestrzeni próbkowania dla determinantów, które wpływają na proces decyzyjny optymalnego routingu sieci. Metoda dopasowania krzywej¹³ wymaga uprzednich informacji na temat topologii sieci. Rzeczywista sytuacja może nie sprawiać, że wcześniejsze informacje są łatwo dostępne. Nawet jeśli istnieją wcześniejsze informacje, topologia sieci może nie być wystarczająco regularna, aby można ją było odwzorować na krzywe dopasowania, które są w stanie ułatwić obliczenia możliwe do wyprowadzenia. Kierując się tą samą logiką, DORAF protocol¹⁴ nie uzasadnił, jak i dlaczego zapożyczyć funkcję Boltzmanna i funkcję logistyczną do przybliżenia determinantów sieciowych. Ismail i in.¹⁵ dostarczyli solidnego punktu odniesienia dla przyszłych przedsięwzięć badawczych nad energooszczędnym projektowaniem protokołów routingu w sieci podwodnej.

Protocol

1. Konfiguracja środowiska Ocean Dwave

1. Pobierz i zainstaluj narzędzia oceaniczne z linku: https://docs.ocean.dwavesys.com/en/stable/overview/install.html
   1. W terminalu wpisz python -m venv ocean.
   2. W terminalu wpisz . ocean/bin/activate, jak pokazano na Rysunek 1.
   3. W terminalu wpisz git clone https://github.com/dwavesystems/dwave-ocean-sdk.git
      Następnie wpisz cd dwave-ocean-sdk, jak pokazano w Rysunek 2.
      Następnie wpisz python setup.py install

Rysunek 1: Aktywacja wirtualnego środowiska oceanu. Pakiet Ocean, jako zintegrowany interfejs API D-wave, zapewnia chmurowe środowisko użytkownika na własnym komputerze użytkownika do siedziby maszyny D-wave. Kliknij tutaj, aby zobaczyć większą wersję tego rysunku.

Rysunek 2: Instalacja Ocean SDK. Pakiet Ocean zawiera niezbędne zestawy narzędzi dla programistów, w tym przydatną instalację Cplex. Kliknij tutaj, aby zobaczyć większą wersję tego rysunku.

2. Instalacja interfejsu API Cplex Python

1. Pobierz i zainstaluj Cplex: https://pypi.org/project/cplex/
   1. W terminalu wpisz install cplex.

3. Parametry konfiguracji eksperymentu

1. Skonfiguruj parametry konfiguracji eksperymentu wymienione w tabeli 1 przy użyciu notacji programowania w języku Python w skrypcie, jak pokazano na rysunku uzupełniającym 1. Po uruchomieniu i wykonaniu skryptu język bazowy będzie przetwarzał zmienne w pamięci RAM. Załączony jest zrzut ekranu kodów Pythona, w których parametrom przypisano odpowiednie wartości (rysunek uzupełniający 1).

powiedział:

d0	87,7085 mln
E	50 * 1 x 10-09 dżuli
epson_fs	1 * 10-12 * 10 dżuli
epson_mp	0,0013 * 1 * 10-12 dżuli
Rozmiar paczki	4000 bitów

Tabela 1: Ustawienia parametrów modelu energetycznego i rozmiaru pakietu.

Uzupełniający Rysunek 1: Skrypt1. Skrypt do ustawiania parametrów eksperymentu. Kliknij tutaj, aby pobrać ten plik.

4. Skrypty Pythona

1. Przygotuj skrypty Pythona, aby wygenerować 198 pozycji 2D węzłów czujników, które są równomiernie rozproszone w sześciu sektorach, które dzielą okrągły obszar o promieniu 50 m.
   UWAGA: Wykres kołowy jest podzielony na 6 sektorów. W każdym sektorze pozycja każdego węzła jest traktowana za pomocą dwóch odpowiadających im zmiennych. Jeden to kąt, a drugi to promień. Przypisz wartości zarówno do kąta, jak i promienia za pomocą generatora jednolitego rozkładu losowego. Szczegółową procedurę przedstawiono na rysunku uzupełniającym 2 i rysunku uzupełniającym 3.
2. W każdym sektorze upewnij się, że 33 węzły czujników są rozmieszczone losowo w rozkładzie normalnym. Zapisz pozycje 2D w plikach tekstowych według każdego sektora pod regułą pisowni nazwy jako 'posdata'+sector_no+'.txt' (Rysunek 3 i Rysunek 4).
   1. Podziel okrągły obszar o promieniu 50 m na sześć sektorów. Początkowe wartości kątowe dla tych sześciu sektorów tworzą wektor A= [60,120,180,240,300,360].
      1. Załóżmy, że indeks sektora wynosi i, ustaw długość bieguna dla węzła czujnika j jako l_{i,j}=50*random.random()
      2. Załóżmy, że indeks sektora wynosi i, ustaw wartość kątową dla węzła czujnika j jako ang_{i,j}=(60*random.random() + A_i - 60) * 2 * pi / 360
      3. Ustaw współrzędne kartezjańskie węzła czujnika j th w^i-tym sektorze jako
         x_{i,j}=l_{i,j}*cos(ang_{i,j})
         y_{i,j}=l_{i,j}*sin(ang_{i,j})

Uzupełniające Rysunek 2: Skrypt2. Skrypt do konfigurowania dwóch lokalizacji pozycji wymiarów dla każdego węzła według sektora. Kliknij tutaj, aby pobrać ten plik.

Uzupełniający Rysunek 3: Skrypt3. Skrypt do konfiguracji wartości pozycji każdego węzła w obrębie 1 sektora. Kliknij tutaj, aby pobrać ten plik.

Rysunek 3: Pozycje węzłów wygenerowane i przechowywane podzielone na 6 plików, z których każdy odpowiada jednemu sektorowi. Dwuwymiarowe lokalizacje pozycji są zapisywane w 6 plikach posdata+'idx'. Każdy z nich przedstawia inny sektor. Kliknij tutaj, aby zobaczyć większą wersję tego rysunku.

Rysunek 4: Pozycje węzłów przechowywane w sektorze 0. Pozycje są w dwóch wymiarach i generowane za pomocą jednolitego generatora losowego. Pierwsza kolumna to lokalizacje poziome, a druga kolumna to lokalizacje pionowe. Kliknij tutaj, aby zobaczyć większą wersję tego rysunku.

5. Przygotowanie początkowych poziomów energii

1. Przygotuj początkowe poziomy energii dla wszystkich 198 węzłów czujników. Przypisz połowie z nich energię początkową na poziomie 0,5 J, a drugiej połowie energię początkową na poziomie 1 J. Utwórz tablicę do przechowywania poziomu energii każdego węzła i użyj pętli, aby przypisać komórkom sekwencjonowanym w liczbach parzystych wartość 1, a tym sekwencjonowanym w liczbach nieparzystych wartość 0,5. Rysunek uzupełniający 4 przedstawia kody Pythona, a wynik jest pokazany w Rysunek 5.

Uzupełniający Rysunek 4: Skrypt4. Skrypt przypisujący połowę energii węzła wynoszącą 1 dżul, a pozostałe 0,5 dżuli. Kliknij tutaj, aby pobrać ten plik.

Rysunek 5: Energy_buffer początkowe przypisanie. Połowie węzłów przypisuje się energię 1 dżul, podczas gdy pozostałym połówkom przypisuje się 0,5 dżula. Kliknij tutaj, aby zobaczyć większą wersję tego rysunku.

6. Przygotowanie skryptu algorytmu Advanced_Leach (Rysunek 6 i Rysunek 7)

1. Przygotuj skrypt funkcjonalny, w którym wybierany jest nagłówek klastra i tworzony jest klaster.
   UWAGA: Klaster jest wybierany za pomocą pętli pod warunkiem, że liczba wybranych głowic klastrów jest mniejsza niż całkowita liczba węzłów podzielona przez 6. Warunek polega na tym, aby upewnić się, że w każdym klastrze ilość węzła źródłowego jest równa lub mniejsza niż 6. W pętli każdemu węzłowi przypisana jest losowa liczba z zakresu [0,1]. Te mniejsze niż dana liczba kryteriów stają się głowicą klastra, podczas gdy inne stają się węzłami źródłowymi. Szczegółową procedurę przedstawiono na rysunku uzupełniającym 5. Następnie, biorąc pod uwagę stałą pulę głowic klastra, pozostałe węzły źródłowe wybierają swoje głowice klastra w najkrótszej odległości, biorąc pod uwagę, że głowica klastra nie hostowała jeszcze więcej niż 6 węzłów źródłowych. Szczegółową procedurę przedstawiono na rysunku uzupełniającym 6.
   1. Ustaw T_n=P/(1-P*(liczba%(1/P))), gdzie P = 0,2 (proporcjonalny stosunek liczby głowic klastra do całkowitego rozmiaru sieci), a liczba to ilość transmisji zaokrąglona do tej pory.
   2. Dla każdego węzła czujnika uzyskaj liczbę losową z przedziału [0,1] threshold_rm = random.random()
      1. Jeśli threshold_rm jest mniejsza niż T_n, wybierz ten węzeł czujnika jako głowicę klastra.
   3. Dla każdego węzła innego niż cluster_head wybierz najbliższy węzłowi czujnika głowicy klastra jako jego nagłówek klastra. Biorąc pod uwagę stałą pulę głowic klastra, pozostałe węzły źródłowe wybierają głowice klastra w najkrótszej odległości, biorąc pod uwagę, że głowica klastra nie hostowała jeszcze więcej niż 6 węzłów źródłowych. Szczegółową procedurę przedstawiono na rysunku uzupełniającym 6.
2. Przygotuj wiersze poleceń do obliczenia procesu wyczerpywania się energii w całej sieci dla tej rundy. Dla każdego uruchomienia algorytmu, który zakończy jedną partię dostaw pakietów z węzłów źródłowych do zlewu, przygotowana tablica magazynowania energii zostanie zaktualizowana w celu zmniejszenia wartości komórka po komórce. Zużycie energii wzdłuż ścieżki będzie sumą zużycia energii na trasę między węzłami, która jest obliczana zgodnie z modelem energetycznym¹. Szczegółową procedurę przedstawiono na rysunku uzupełniającym 7.
3. Oblicz wymagane metryki rundy transmisji.
   UWAGA: Dla każdego uruchomienia algorytmu w celu zakończenia jednej partii dostarczania pakietów, aktualizowana jest tablica energii, zliczana jest ilość przebiegu i liczba opróżnionych węzłów. Jeśli wartość jest większa lub równa 1, FND (kość pierwszego węzła) jest równa bieżącej wartości przebiegu. Jeśli wartość jest większa lub równa połowie ilości węzła, to HND (połowa kości węzła) jest równa bieżącej ilości uruchomienia. Jeśli wartość jest równa całkowitej ilości węzła, to AND (matryca wszystkich węzłów) jest równa bieżącej ilości uruchomienia. Szczegółową procedurę przedstawiono na rysunku uzupełniającym 8.

Rysunek 6: Tablica głowicy klastra. Numery sekwencyjne węzłów, które zostały wybrane jako głowice klastrów. Kliknij tutaj, aby zobaczyć większą wersję tego rysunku.

Rysunek 7: Tablica indeksów głowicy klastra. Ponieważ w tablicy indeksów głowicy klastra znajduje się sześć sektorów, z których każdy ma 33 węzły czujnika, liczba wskazuje numer sekwencyjny głowicy klastra, do której należy odpowiedni węzeł czujnika. Indeks pozycji tablicy odpowiada numerowi sekwencyjnemu każdego węzła czujnika. W przypadku węzła czujnika, który jest wybrany jako głowica klastra, numer przypisany do jego miejsca w tablicy jest numerem sekwencyjnym samego siebie. Kliknij tutaj, aby zobaczyć większą wersję tego rysunku.

Uzupełniający Rysunek 5: Skrypt5. Skrypt do wybierania głowicy klastra. Kliknij tutaj, aby pobrać ten plik.

Uzupełniający Rysunek 6: Skrypt6. Skrypt służący do przypisywania węzłów źródłowych do klastrów. Kliknij tutaj, aby pobrać ten plik.

Uzupełniający Rysunek 7: Skrypt7. Skrypt do aktualizacji bufora energii dla wszystkich węzłów źródłowych poprzez zmniejszenie ilości energii zużywanej przez transmisję. Kliknij tutaj, aby pobrać ten plik.

Uzupełniający Rysunek 8: Skrypt8. Skrypt do obliczania liczby zaokrągleń, do których umiera pierwszy węzeł, a połowa węzłów umiera. Kliknij tutaj, aby pobrać ten plik.

7. Przygotowanie skryptu hybrydowego algorytmu kwantowego

1. Przygotuj działający skrypt, w którym wybierany jest nagłówek klastra i tworzony jest nagłówek grupy.
   1. Ponieważ maksymalny rozmiar klastra wynosi 6 w tym eksperymencie¹, upewnij się, że liczba głowic klastrów jest nie mniejsza niż current_valid_node_amount/6, procedura wyboru będzie przebiegać w pętli, dopóki to kryterium nie zostanie spełnione.
      UWAGA: Jeśli current_valid_node_amount nie jest większa niż 6, te prawidłowe węzły tworzą jeden i tylko klastry.
   2. Dla każdego z węzłów niebędących cluster_head_valid oblicz jego odległość od każdego z wybranych głowic klastra i przypisz do niego nagłówek klastra, którego rozmiar klastra nie przekroczył 6, gdzie wartość odległości jest najmniejsza.
      UWAGA: W Rysunek 8, obliczane są odległości wszystkich węzłów niebędących cluster_head_valid do wybranej głowicy klastra 24, a cała wybrana głowica klastra jest wyświetlana w Rysunek 9. Rysunek 10 przedstawia wszystkie węzły przypisane do odpowiadającego im nagłówka klastra, a Rysunek 11 pokazuje grupowanie węzłów członkowskich każdego klastra w tablicę wektorową.
2. Przygotuj skrypt podfunkcji, w którym tworzony jest problem optymalizacji routingu dla każdego klastra i przesyłany do interfejsu API D-wave (Rysunek 12). Ścieżki routingu są obliczane klaster po klastrze.
3. Korzystając ze skryptu Pythona, oblicz proces wyczerpywania się energii w całej sieci, aby ilościowo ocenić algorytm według czasu życia sieci pod względem liczby rund transmisyjnych.
   UWAGA: Dla każdego uruchomienia algorytmu, który kończy jedną partię dostarczania pakietów z węzłów źródłowych do zlewu, przygotowana tablica magazynowania energii zostanie zaktualizowana w celu zmniejszenia wartości komórka po komórce. Zużycie energii wzdłuż ścieżki będzie sumą zużycia energii na trasę między węzłami, obliczoną zgodnie z modelem energetycznym¹. Szczegółową procedurę przedstawiono na rysunku uzupełniającym 7.
4. Za pomocą skryptu Pythona nagraj moment, w którym pierwszy węzeł jest opróżniany i kiedy połowa węzłów jest opróżniana. Szczegółową procedurę przedstawiono na rysunku uzupełniającym 8.

Rysunek 8: Tablica toClusterHeadDistance dla węzła innego niż cluster_head o indeksie 24. Pierwsza kolumna to odległość, a druga kolumna to numer indeksu głowicy klastra Kliknij tutaj, aby wyświetlić większą wersję tego rysunku.

Rysunek 9: CHID_buff tablica. Numery sekwencyjne węzłów czujnika, które są wybrane jako głowice klastrów. Kliknij tutaj, aby zobaczyć większą wersję tego rysunku.

Rysunek 10 CHIdx_buff tablicy. Przypisano numer sekwencyjny węzłów czujnika głowicy klastra do każdego odpowiedniego węzła czujnika. Kliknij tutaj, aby zobaczyć większą wersję tego rysunku.

Rysunek 11: CH_BUFF tablica. Grupa klastrów na węzły czujnika głównego klastra odpowiadające CHID_buff macierzy. Każda grupa klastrów składa się z 0 lub więcej niż 0 węzłów czujników. Każda tablica grup klastrów wyświetla numery sekwencyjne węzłów czujników, które się w niej znajdują. Kliknij tutaj, aby zobaczyć większą wersję tego rysunku.

Rysunek 12: Obliczanie ścieżki routingu dla każdego sektora. Dla każdego sektora obliczane są ścieżki routingu dla wszystkich węzłów źródłowych. Kliknij tutaj, aby zobaczyć większą wersję tego rysunku.

Results

Wyniki z jednej próbki są pokazane w Tabeli 2, Tabeli 3 i Tabeli 4. Szczegółowe zestawy danych dla trzech partii danych są dostępne w folderze Dane uzupełniające 1.

Zestaw danych 1
198 węzłów w obszarze kołowym o promieniu 50m	Hybrydowy algorytm kwantowy	Algor...

Discussion

Obecny najnowocześniejszy komercyjny procesor kwantowy może być używany w problemach obliczeniowych dowolnej topologii sieci¹. Aplikacja procesora kwantowego nie jest ograniczona przez liczbę fizycznych qbitów, które którykolwiek z procesorów kwantowych był w stanie zaimplementować.

Wyniki projektu przedłużenia żywotności sieci czujników wskazują na postęp w metodzie osiągania jeszcze dłuższej żywotności sieci przy użyciu procesora kwantowego. Wyniki sugerują, że przew...

Materials

List of materials used in this article

Name	Company	Catalog Number	Comments
Laptopy Dell		Nie dotyczy
Ubuntu 18.04.6 LTS	Canonical Ltd	18.04.6 LTS
Python3.8	Python Software Foundation	3.8.0
Dwave QPU	Dwave	https://docs.ocean.dwavesys.com/en/stable/overview/install.html