Zadania 5 i 6

W niniejszym zadaniu został zaprojektowany algorytm rozszerzający otrzymane dotychczasowe wyniki dotyczące protokołów rozgłaszania w mikrosieciach. Algorytm RBO (patrz niżej) został dostosowany do warunków wysokiej zmienności zbioru stacji. Zostały przeanalizowane strategie zapewniające dużo lepsze zachowanie algorytmu w przypadku stacji przychodzących i odchodzących. W tej chwili algorytm RBO był badany tylko dla statycznych sieci (liczba stacji nie zmieniała się w czasie trwania rozgłaszania). Jednak celem naszym jest wykorzystanie algorytmu na przykład w sieciach, które pomimo pracy w własnym trybie, co pewien czas otrzymują aktualizacje od stacji rozgłaszającej. Problem jest w tym, że stacje mają właśnie swój tryb pracy, więc nie mogą cały czas nasłuchiwać, czy jest już dla nich odpowiednia aktualizacja. RBO pozwala nam zaplanować tak transmisję, aby czas w którym stacja musi spędzić na nasłuchiwaniu był minimalny. A dodanie strategii na przychodzące i odchodzące wiadomości dla stacji pozwala nam na dostosowanie algorytmu do warunków praktycznych. Ponadto, jeśli czas pracy w innym trybie jest długi stacje mogą dodatkowo oszczędzać energię potrzebną na nasłuchiwanie stacji rozgłaszającej.

Opis algorytmu RBO

Na początku rozważony zostanie naiwny algorytm rozgłaszania, który lepiej pokaże jaki problem należy rozwiązać. Załóżmy, że mamy zbiór kluczy np. są to hasze 128-bitowe. Rozgłaszanie odbywać będzie się w ustalonej liczbie slotów. Każda wiadomość składa z klucza i danych oraz wysyłane są w porządku rosnącym kluczy, czyli

Slot$_1$		Slot$_2$			Slot$_{n-1}$		Slot$_n$
Klucz$_1$	Data$_1$	Klucz$_2$	Data$_2$		Klucz$_{n-1}$	Data$_{n-1}$	Klucz$_{n}$	Data$_{n}$

Zakładając, że interesujący jest dla nasz pewien przedział kluczy, to wtedy stacja musi słuchać cały czas do momentu, kiedy odebrany klucz jest większy od kluczy w naszym przedziale. Widzimy, że w tej strategii w najgorszym przypadku musimy słuchać aż cały przedział. Poniżej opisany zostanie algorytm nazwany RBO, który poprawia znacząco przedstawiony wcześniej algorytm naiwny. Niech $rev_k\colon \{0,1\}^k \to \{0,1\}^k$ będzie funkcją, która po podaniu liczby $k$-bitowej, wraca tą samą liczbę, ale zapisując ją dokładnie w odwrotnej kolejności np $rev_5(00001) = 10000$. Rozważmy stacje która nadaje wiadomości. Na początku wiadomości $a_1, a_2, \ldots, a_k$ zostają posortowane po kluczach i wysyłane w taki sposób, że wiadomość z kluczem $a_i$ wysyłana jest w slocie $rev_k(i)$. Klucze wysyłane przez stacje nadawczą są nieznane dla stacji odbiorczych. Dlatego wyzwaniem jest zaprojektowanie tak algorytmu dla stacji odbiorczych, aby na podstawie odebranych wcześniej wiadomości można było ustalić które sloty można opuścić. Pomysł polega na tym aby stacja odbiorcza przetrzymywała dolne $lb$ i górne $ub$ ograniczenia na klucze i odpowiednio je aktualizowała.

  W slocie $t$, jeśli $lb \leqslant rev_k(t) \leqslant ub$, wtedy stacja odbiorcza aktywuje antenę i odbiera wiadomość z kluczem $k = k_{rev_k(t)}$
  
  Aktualizacja $lb$ i $ub$ na podstawie wartości $k$:
      jeśli $k<k'$, to $ln = rev_k(t)+1$
      jeśli $k''< k$, to $ub =rev_k(t)-1$
      jeśli $k'\leqslant k \leqslant k''$, to odbieramy odpowiednie wiadomości

Powyżej przedstawiony został cały algorytm. Na początku stacja sprawdza, w którym slocie ma odebrać wiadomość i dalej odpowiednio aktualizuje dolne i górne ograniczenia.

Nowa stratega dla dynamicznej liczby wiadomości dla stacji

Na początku sprawdzimy co stanie się, jeśli pojawia się nowa wiadomość dla już pracującej sieci. W tym przypadku można zauważyć, że jeśli stacje „nauczyły”, się już swoich przedziałów w których będą słuchać przychodzących wiadomości, to wystarczy, że stacja rozgłaszająca na początku następnego cyklu lub nawet w każdej transmisji wysyła informację o aktualnej liczbie rozgłaszanych wiadomości (liczbie aktualizacji). Wtedy każda stacja dowiaduje się, że liczba stacji do aktualizacji zmieniła się i odpowiednio dostosowuje swoje przedziały. Zauważmy, że strategia ta działa również dla większej liczby wiadomości wysyłanych jak i odrzucanych. Nie trzeba wtedy aby po zmianie liczby wiadomości stacje musiały od nowa uczyć się ograniczeń dolnych i górnych. Robione są tylko drobne przesunięcia zależne od liczby dodanych lub usuniętych wiadomości. W ten sposób znacząco oszczędzamy czas jaki stację muszą spędzić na nasłuchiwaniu stacji rozgłaszającej i oszczędzić zużycie energii. Następnym krokiem dla tej strategii jest optymalizacja dla uczestników, którzy „spodziewają się” aktualizacji. Zauważmy, że stacje te muszą też odpowiednio słuchać i ustawiać swoje przedziały na odpowiednie zakresy, ale wiadomości do nich może po prostu nie być. Nie jesteśmy w stanie tego przewidzieć w jednym cyklu, ale w następnych już tak. Jeśli stacja dla której nie było wcześniej wiadomości zobaczy, że w następnych cyklach liczba rozgłaszanych wiadomości nie zmieni się lub zmniejszy to może pominąć cały cykl. Nasłuchiwać, musi tylko wtedy jeśli ta liczba się zwiększy.

Implementacja

W mikrosieciach bezprzewodowych jednym z kluczowych elementów jest zużycie energii przez węzły sieci. Oczywistym jest, że wydatek energetyczny związany z transmisją danych powinien być minimalizowany, należy jednak zauważyć, że istotnym elementem wpływającym na energochłonność urządzeń jest wydatek związany z odbiorem informacji. W zadaniu 6. zbadano symulacyjnie właściwości algorytmu opracowanego w zadaniu 5, które mają bezpośredni wpływ na zużycie energii urządzeń. Prace składały się z poniższych etapów:

1. Implementacja algorytmu rozgłaszania informacji w mikrosieci (RBO), opracowanego w ramach zadania 5 przez Politechnikę Wrocławską. Algorytm został zaimplementowany w symulatorze modelującym mikrosieć, w której wyróżniony zostaje jeden węzeł pełniący rolę węzła rozgłaszającego informacje przeznaczone dla węzłów odbiorczych działających w ramach mikrosieci. Węzły, zgodnie z algorytmem RBO, po odsłuchaniu klucza przesłanego przez węzeł pośredniczący, podejmowały decyzję na temat tego kiedy ponownie włączyć nasłuch lub też zaczynały odczytywać dane ze strumienia wysyłanego przez węzeł pośredniczący, jeśli odebrały klucz równy własnemu kluczowi.
2. Symulacje działania algorytmu, wraz z oceną jego właściwości. Symulacje algorytmu RBO przeprowadzono w sieci przedstawionej na poniższym schemacie:
   

   Zasymulowana mikrosieć. Cyfrą 1 oznaczono stację bazową sieci komórkowej, która komunikuje się z węzłem pośredniczącym (2). Węzeł pośredniczący rozgłasza informacje do węzłów mikrosieci (3). W symulacjach pominięto komunikację ze stacją (1) jako nieistotną dla badanego algorytmu.

   Rozważono szereg przypadków ilości węzłów oraz zasymulowano odbiór z różną jakością sygnału. Algorytm RBO porównano z algorytmem w którym węzły cały czas nasłuchiwały nadawanych informacji, a więc działały podobnie jak obecnie działają terminale w sieciach komórkowych WCDMA i LTE. Ocenie podlegały m.in. następujące parametry:
   • Średnia ilość odbiorów wykonanych przez węzeł
   • Rozkład ilości przeczytanych kluczy
   • Rozkład czasu oczekiwania na klucz
   Badany algorytm zapewniał znacznie mniejszą (nawet o ponad 95% dla 512 węzłów) ilość odczytów ze strumienia danych, zapewniającą odnalezienie przez dany węzeł interesującego go miejsca w strumieniu danych wysyłanym przez węzeł pośredniczący. Błędy odczytu klucza, w przypadku algorytmu RBO powodowały mniejszy wzrost liczby odczytanych kluczy, co prowadzi do konkluzji, że badany algorytm lepiej radzi sobie z błędami transmisji. Wyniki zostały zaprezentowane w poniższej tabeli.

   	Centyl 95, st. błędu 0	CCentyl 95, st. błędu 0,1	CWzrost liczby odczytanych kluczy	CCentyl 98, st. błędu 0	CCentyl 98, st. błędu 0,1	CWzrost liczby odczytanych kluczy
   TDM, 32 węzły	31	50	61%	32	64	100%
   RBO, 32 węzły	7	11	57%	8	13	63%
   TDM, 256 węzłów	245	405	65%	252	491	95%
   RBO, 256 węzłów	11	16	45%	12	18	50%

   Co istotne, w przypadku algorytmu RBO, stacja jest w stanie tak samo szybko odnaleźć interesujący ją punkt w strumieniu danych, jak w przypadku odczytywania wszystkich kluczy po kolei, włączając się tylko w niektórych momentach transmisji. Wynik został zobrazowany poniższym wykresem.
   

   Dystrybuanta czasu pomiędzy włączeniem węzła a odczytaniem klucza [w liczbie ramek]

   Biorąc pod uwagę, że każdy odbiór pociąga za sobą pewien wydatek energetyczny, można stwierdzić, że algorytm RBO jest algorytmem energooszczędnym, gdyż wymaga znacznie mniejszej ilości odbiorów niż nasłuchiwanie wszystkich kluczy, a przy tym nie powoduje wydłużenia czasu przeszukiwania strumienia danych w celu dosynchronizowania się węzła mikrosieci do węzła pośredniczącego.
3. Ocena przydatności algorytmu w realnych zastosowaniach W ramach zadania przeprowadzono również analizę przydatności algorytmu w realnych zastosowaniach. Stwierdzono, że algorytm RBO wpisuje się obraz najnowszej komunikacji komórkowej, w której można dostrzec kilka trendów:
   • Forum 3GPP (3rd Generation Partnership Programme) skupiające producentów sprzętu sieciowego i terminali abonenckich, w 10-tym wydaniu swojego standardu (tzw. Release 10) zaczęło pracę nad wsparciem dla nowego typu urządzeń w sieciach komórkowych – MTD (Machine Type Device), czyli terminali, które będą przesyłać w większości niewielkie porcje danych, często z urządzeń pomiarowych, niebędących urządzeniami bezpośrednio sterowanymi przez ludzi. Przykładem takich urządzeń mogą być np. mierniki zużycia prądu, sensory temperatury lub maszyny w fabrykach.
   • W ramach projektu WINNER+ konsorcjum prowadzące badania rozważało bezpośrednią komunikację między terminalami, tzw. D2D (Device-to-Device). Tryb bezpośredniej komunikacji między terminalami abonenckimi jest korzystny zarówno z punktu widzenia urządzenia końcowego, jak i całej sieci, gdyż z jednej strony pozwala na podwyższenie przepływności sieci, z drugiej strony nie powoduje wzrostu interferencji dzięki spadkowi mocy z jaką terminal transmituje.
   • Kolejnym stadium w planowanym rozwoju architektury sieci komórkowej jest połączenie dwóch wspomnianych wyżej technik. Hybryda taka może znaleźć zastosowanie np. w sieciach sensorycznych działających pod kontrolą urządzeń podłączonych do sieci komórkowej. Urządzenia (sensory) nie kontaktują się bezpośrednio ze stacją bazową, ale z urządzeniem pośredniczącym, którym może być telefon komórkowy, inny terminal, lub jeden wyselekcjonowany sensor. Modele takie rozważane są w ramach projektowanych obecnie rozwiązań 5G. Ograniczenie łączności sensorów z siecią może wynikać z braku bezpośredniej łączności przy ograniczonej mocy transmisyjnej lub też z chęci oszczędzania energii w ramach mikrosieci. W takim modelu ograniczenie zużycia energii często jest priorytetem, szczególnie, gdy sensory są niewielkie, mają zasilanie bateryjne i każdy wydatek energetyczny powinien być przemyślany.

Zastosowanie algorytmu RBO w ramach sieci komórkowych piątej generacji zostało opisane w raporcie [1]. Bibliografia: [1] ,,Mikrosieci urządzeń M2M w sieciach piątej generacji'' - raport projektu ODOKRIM