Zadania 16 i 17

Aby zweryfikować przydatność narzędzia, jakim jest symulator sieci bezprzewodowej opracowany w ramach tego projektu, zaimplementowano algorytm przesyłania wiadomości, który nie był uprzednio rozważany. Mechanizm weryfikacji poprawności można zatem nazwać ślepą próbą. Zgodnie z założeniami prac wykonanych w zadaniach 13, 14 i 15, należało się spodziewać następujących efektów:

• przekład opisu algorytmu z pseudokodu na funkcje symulatora (jego API) powinien być relatywnie łatwy;
• wyniki uzyskane analitycznie powinny znajdować odzwierciedlenie w symulacjach.

Algorytm

Zaimplementowano algorytm przesyłania wiadomości wzdłuż linii (tj. stacje rozmieszczone są na trasie źródło-cel zgodnie z pewnym rosnącym porządkiem, dla ustalenia uwagi: od lewej do prawej). Badano rozmieszczenie losowe jednostajnie na całej długości linii, oraz rozmieszczenie równomierne - ze stałymi odległościami między stacjami. Parametrami algorytmu były $N$ - ilość wszystkich stacji, oraz $L$ - długość linii. Ustalono odnośną moc nadawania $P$, a każdej stacji przydzielono moc z zakresu $[0.9P, 1.1P]$. Wykorzystano model strat energetycznych zgodny z 3GPP dla przestrzeni zamkniętych ([1]). Szczegóły algorytmu przedstawia następujący pseudokod:

  Algorytm Algorytm propagacji wiadomości po linii
1:  loop
2:    repeat
3:      repeat słuchaj na kanale until odebrano wiadomość $m$
4:      if $s$ była wcześniej odebrana
5:        zignoruj $s$, powróć do słuchania
6:      ustal $x$ - szacunkową odległość od stacji wysyłającej wiadomość
7:      dodaj $(s,x)$ do kolejki wiadomości
8:    until koniec slotu czasowego
9:    for all $(s,x)$ w kolejce wiadomości
10:     zwiększ licznik prób wysłania wiadomości $s$
11:     if decyzja nadawania = TAK  // decyzja na podstawie licznika i $x$
12:       spróbuj wysłać $s$ : wykonaj algorytm CSMA
13:       if udało się wysłać
14:         usuń $s$ z kolejki   // symulator zapisuje $x$ wiadomości $s$

W linii 11. algorytmu jest podejmowana decyzja ``TAK'' o transmisji z prawdopodobieństwem $p$, gdzie \[ p = \begin{cases} x^{n-1},& \text{jeśli } licznik \leq M \\ \frac{1}{n},& \text{w p.p.} \end{cases} \] dla parametru algorytmu $M$, oraz $n$ - estymacji ilości stacji w zasięgu rozpatrywanej stacji. Należy zauważyć, że jeśli $M<0$, to decyzja transmisji jest zwykłą próbą ethernetową - wszystkie stacje rozważające daną wiadomość $s$ w tym momencie mają jednakową szansę jej propagowania. Dla $M\geq0$ faworyzowane do dalszego propagowania wiadomości są stacje o większym $x$ - które jest znormalizowaną odległością ``skoku'' wiadomości między stacją nadającą a odbierającą. Zatem parametr $M>0$ powinien zwiększać średnią wartość $x$ powyżej $\frac12$. Dodatkowe obostrzenia dla algorytmu, takie jak identyfikacja, czy nadchodząca wiadomość pochodzi ``z lewej'' strony linii, oraz warunki początku (stacja skrajnie lewa rozpoczyna transmisję wiadomości) oraz końca (stacja skrajnie prawa otrzymuje wiadomość) nie zostały ujęte w pseudokodzie.

Implementacja w symulatorze

Poniżej przedstawiamy implementację omawianego algorytmu w języku Python dla symulatora. Linie kodu (technicznego) zostały pominięte w celu uwypuklenia podobieństw do pseudokodu.

 def run_experiment(self, log, experiment):    
        txp = experiment.nodes[0].transmitPower
        maxPL = txp - experiment.nodes[0].antenna.receiverSensitivity  
        maxDist  = 10**( (maxPL - 15.3) / 37.6)                       
        for node in experiment.nodes:
            ...
            # indywidualnie ustaw moc nadawania
            node.setTxPower( ... )
            # zarejestruj obsługę zdarzenia - nadejście wiadomości
            node.setOnMessageReceive(partial(self.receive, node))

    def receive(self, node, msg, *arg):
        # warunek końca symulacji
        if node.node_idx == node.N - 1:   
            self.experiment.simulation.breakSimulation()
        ...
        # moc odebranej wiadomości
        msg.rxp = node.antenna.rxBuffer[msg.sender][-1].rxp   
        node.propagatedMsgsBuf.append(msg)
        self.decidePropagation(node)

    def decidePropagation(self, node, *arg):
        for msg in node.propagatedMsgsBuf:
            if msg.confirmed:
                continue
            if self.TXdecision(node, msg)  == True:
               # wykonaj CSMA
               if node.antenna.is_free():
                  # jednolity interfejs wysyłania wiadomości
                  node.send(Message(
                     sender = node.node_idx, time = node.antenna.sim.now, 
                     value = ... ))
                  msg.confirmed = True
            msg.attempts += 1
        # ponów próbę wysłania w następnej rundzie
        node.schedule(partial(self.decidePropagation, node), 5.0)

    def TXdecision(self, node, msg):
        rxp = msg.rxp                           
        x = self.distEstimation(node, rxp)
        n = self.nEstimation(node, rxp)
        decision = 1/n if msg.attempts > node.M else x ** (n-1)

        if np.random.rand() < decision: 
            return True
        return False

Należy zaznaczyć że nie jest to pełny kod implementujący omawiany algorytm - usunięto z niego oczywiste konstrukcje takie jak inicjowanie zmiennych czy funkcje pomocnicze distEstimation i nEstimation, które wykonują jedynie obliczenia matematyczne. W szkieletowym listingu widać natomiast, że uzyskano spodziewany efekt relatywnie łatwego przekładania pseudokodu opisującego algorytm na kod wykonywalny przez symulator. Co do drugiego elementu testu spójności, czyli poprawności wyników, odpowiedź jest również pozytywna. Na rysunkach poniżej przedstawiono średnią wartość $x$ (znormalizowany rozmiar ``skoku'' wiadomości) dla różnych zagęszczeń stacji, dla dwóch scenariuszy rozłożenia stacji na linii - jednostajnie losowym i równomiernym.

                 

Wyniki symulacji algorytmu propagacji wiadomości na linii

Jak widać, dla przypadku $M=-1$, czyli dla $p=\frac{1}{n}$ (czerwony przebieg) oczekiwany średni postęp wiadomości szybko zbiega do wartości $\approx 0,6$, co jest zgodne z wynikami analitycznymi: skoro wszystkie stacje w zasięgu wiadomości mają jednakowe prawdopodobieństwo transmisji, to średnio ``postęp'' wiadomości będzie wynosił około $\frac{1}{2}$ jej zasięgu. Ta właściwość jest szczególnie widoczna przy równomiernym rozłożeniu stacji. Z drugiej strony, dla $M \geq 0$, czyli tam, gdzie co najmniej pierwsza próba retransmisji faworyzuje stację najdalszą od źródła wiadomości - widzimy wyraźnie większy ``skok''. Warto dodać, że wraz ze wzrostem zagęszczenia stacji w zasięgu wiadomości (na wykresach zasięg nie jest znormalizowany - w symulacjach, zasięg wyliczony na podstawie bazowej mocy transmisji $P$ wynosił 130), efektywność metody wyboru stacji retransmitującej na podstawie estymatora $x^{n-1}$ rośnie w porównaniu do próby ethernetowej, z tendencją wskazującą na dążenie do optymalnej wartości 1. Na podstawie tego przykładu algorytmu i jego implementacji dla symulatora stwierdzono, że:

1. symulator umożliwia relatywnie łatwą symulację algorytmów sieciowych opisywanych pseudokodem zwyczajowo używanym w analitycznych opisach;
2. możliwe jest łączenie różnych technik/algorytmów w jednej symulacji: w omawianym przypadku mechanizm CSMA jest niezależnym blokiem, wykorzystywanym do realizacji procesu propagacji wiadomości;
3. uzyskiwane wyniki pokrywają się z wyliczeniami, a należy zauważyć że symulator jest programem implementującym rzeczywiste (fizyczne, mechaniczne) właściwości sieci, zatem zachodzi zgodność dwóch niezależnych dróg osiągania tego samego rezultatu.

Implementacja

Jak opisano w [1], schemat działania sieci rozpatrywanej w ramach projektu można podzielić na 3 fazy:

• Konfiguracja sieci, w czasie której następuje organizacja sieci w taki sposób, aby zapewnić możliwość optymalnego nadawania i odbioru w ramach zbioru rozpatrywanych stacji.
• Nadawanie, czyli faza właściwa działania sieci, w której następuje wymiana danych pomiędzy poszczególnymi elementami sieci.
• Rekonfiguracja, której celem jest dostosowanie sieci do zmian zaistniałych od czasu ostatniej konfiguracji.

Nadawanie było przedmiotem rozważań przedstawionych w raportach z zadań 2, 6, 10. Ponieważ założono, że poszczególne tryby transmisji, jeśli mają wystąpić jednocześnie, to mogą być realizowane za pomocą innych zasobów np. częstotliwościowych, nie ma konieczności przeprowadzania dodatkowych testów operacyjnych poza tymi, które zostały przeprowadzone w poprzednich zadaniach. Spośród powyższych, najważniejszym elementem jest konfiguracja sieci, której poprawne działanie jest kluczowe. W skład części konfiguracyjnej sieci wchodzą następujące elementy:

• Zliczanie stacji nadających, realizowane za pomocą algorytmu opisanego w zadaniach 3-4.
• Obliczanie przez zbiór stacji tłumienia kanału radiowego i rozsyłanie tej informacji do pozostałych węzłów. Do obu tych czynności używany będzie algorytm z zadań 1-2. Dobór charakterystyk algorytmu $\lambda$-CSMA dokonywany będzie na podstawie informacji z kroku poprzedniego.
• Organizacja sieci typu multi-hop. Na podstawie wyliczonych tłumień kanału pomiędzy węzłami, sieć zostaje zorganizowana w taki sposób, żeby czas jej życia był wydłużony. Szczegóły algorytmu opisano w zadaniu 8.
• Rozsyłanie informacji dotyczącej organizacji sieci, realizowane za pomocą algorytmu z zadań 5-6.

Krytycznym elementem w powyższym łańcuchu jest styk pomiędzy punktami 1 i 2. Wynik zliczania stacji jest jednocześnie elementem wejściowym przy konfiguracji algorytmu $\lambda$-CSMA, wpływającym na stopień wykorzystania kanału radiowego jak i ilość kolizji. Algorytm $\lambda$-CSMA jest wykorzystywany na dwa sposoby:

• Wykorzystując fakt, że algorytm $\lambda$-CSMA dąży do sytuacji, w której nadaje tylko jedna stacja, węzły nasłuchujące mogą obliczyć tłumienie sygnału radiowego ze stacji nadającej.
• Za pomocą protokołu $\lambda$-CSMA realizowana jest transmisja informacji na temat tłumienia trasy radiowej pomiędzy węzłem nadającym a wszystkimi węzłami, które słyszy dany węzeł nadający. Innymi słowy, punkt drugi można podzielić na dwie fazy:
• Każda stacja, działając zgodnie z protokołem $\lambda$-CSMA, wysyła swój identyfikator (jednokrotnie lub kilkukrotnie). Każda stacja nasłuchuje także transmisji od innej stacji i w przypadku odbioru informacji oblicza tłumienie kanału radiowego na trasie od stacji aktualnie nadającej. Zapamiętuje tłumienie przypisane do danej stacji nadającej.
• Po przesłaniu swojego identyfikatora i odebraniu identyfikatorów innych stacji, stacja przystępuje do wysłania, zgodnie z protokołem $\lambda$-CSMA, informacji o tłumieniu kanału radiowego pomiędzy nią o innymi stacjami.

Różnica pomiędzy dwiema powyższymi fazami ogranicza się jedynie do typu informacji, którą rozsyła węzeł. Bez wnikania w rodzaj przesyłanej informacji nie widać więc różnicy pomiędzy tymi fazami. Tak więc algorytm $\lambda$-CSMA, oprócz swojego podstawowego celu, jakim jest organizacja nadawania, ułatwia też badanie środowiska radiowego przez węzły sieci. Wobec powyższego, bardzo istotnym staje się zapewnienie takich warunków transmisji, aby z jednej strony ograniczyć ilość kolizji w kanale radiowym, ale też zapewnić szybką konfigurację sieci. Po zakończeniu drugiego etapu konfiguracji wszystkie węzły powinny posiadać informacje na temat tłumień kanału radiowego pomiędzy dowolną parą węzłów. Jeden wyróżniony węzeł przystępuje do obliczania ścieżek nadawania transmisji wg wybranego algorytmu. Jakość zaproponowanego rozwiązania była przedmiotem badań w ramach zadania 8. W ostatnim etapie konfiguracji sieci następuje rozsyłanie informacji konfiguracyjnych. Właściwości tej części zostały opisane w raporcie z zadania 6. W fazie rekonfiguracji sieci, w pierwszej kolejności sprawdzany jest zbiór aktywnych stacji, wg algorytmu opisanego w zadaniu 11-12. W następnym kroku następuje ewentualne rozesłanie, przy pomocy algorytmu z zadania 5-6, nowych informacji ścieżek nadawania. Przy odpowiednim doborze parametrów algorytmu identyfikacji węzłów, można założyć, że stacje zostaną poprawnie zidentyfikowane. Jeśli by się tak nie stało, sieć może zostać rekonfigurowana w sposób suboptymalny, ale nadal będzie wykonywać swoje zadania. Z tego powodu część rekonfiguracyjna nie była objęta dogłębną analizą w ramach tego zadania, chociaż przeprowadzono testy współdziałania odpowiednich elementów.

Testy

W ramach zadania 17 wykonano testy operacyjne. Wykonano testy współdziałania algorytmów, w tym całości złożonej ze wszystkich komponentów opracowanych w poprzednich zadaniach. W kodzie źródłowym symulatora umieszczono przykład eksperymentu, w którym wykorzystuje się wszystkie zaimplementowane algorytmy. Prowadzono także testy działania z różnymi ustawieniami, w tym w szczególności w różnych warunkach radiowych. Pozwoliło to wyeliminować pewne niewielkie błędy, które nie miały jednak wpływu na wnioski uzyskiwane we wcześniejszych częściach. Najważniejszymi testami były testy współdziałania algorytmów z zadań 3-4 i 1-2. Zbadano jaki wpływ ma realistyczne szacowanie ilości nadających stacji na stabilność działania algorytmu $\lambda$-ciągłego CSMA. Symulacje miały następujący przebieg:

Schemat testów

W pierwszej fazie uruchamiany był algorytm zliczania węzłów, a następnie każdy z węzłów rozsyłał $m=10$ wiadomości. Rozpatrzono dwa przypadki:

• referencyjny, w którym parametry algorytmu $\lambda$-ciągłego CSMA obliczane były na podstawie realnej liczby węzłów w sieci
• realny, w który, w którym parametry algorytmu $\lambda$-ciągłego CSMA obliczane były na podstawie liczby węzłów sieci estymowanej w kroku poprzednim.

Taki podział zapewniał sprawdzenie współdziałania rozpatrywanych algorytmów.\\ Analizie poddano dwa czynniki :

• Długość czasu działania sieci w trybie CSMA. Czas ten liczony była jako różnica pomiędzy momentem, w którym pierwszy węzeł rozpoczyna transmisję w trybie CSMA do czasu, w którym ostatni węzeł wykonuje swoją ostatnią transmisję w tym trybie. Im krótszy czas działania algorytmu, tym mniejszy jest koszt energetyczny dla węzła.
• Liczba konfliktów transmisji. Konflikty rozumiane są jako sytuacje, w których jednocześnie nadaje więcej niż jeden węzeł. Przyczyn takiej sytuacji może być kilka, np.:
  • Węzły zaczęły nadawać w tym samym czasie
  • Jeden podjął decyzję o nadawaniu, podczas gdy drugi już zaczął nadawać, ale mechanizmy wykrycia fali nośnej jeszcze nie zdążyły jej wykryć
  • Jeden z węzłów nadaje, ale warunki radiowe powodują, że drugi węzeł nie ma świadomości tej transmisji

Testy wykonano dla szeregu przypadków, których podsumowanie znajduje się w poniższej tabeli:

ID	Liczba węzłów	Kres górny liczby węzłów (zliczanie)	Ilość punktów transmisji (CSMA)
1	10	12	2
2	10	12	5
3	10	20	5
4	10	12	10
5	10	40	5
6	10	40	10
7	10	40	2

W każdym z powyższych przypadków założono, że w fazie rozsyłania informacji, każdy z węzłów wyśle 10 wiadomości.

Wyniki

Na poniższym wykresie przedstawiono zmianę ilości konfliktów oraz czasu działania sieci w trybie CSMA, w stosunku do przypadku referencyjnego.

Wyniki testów

Widać więc, że wprowadzenie rzeczywistego zliczania węzłów nie wpływa na działanie algorytmu CSMA w znaczący sposób. Każdy węzeł autonomicznie oblicza ile węzłów znajduje się w jego otoczeniu, a następnie dokonuje inicjalizacji algorytmu dostępu do kanału za pomocą obliczonej liczby węzłów. Oznacza to, że każdy węzeł w sieci może zainicjalizować swój algorytm dostępu do kanału nieco inną wartością (ponieważ każdy węzeł będzie widział nieco inną liczbę stacji, wynika to ze specyfiki algorytmu). Okazuje się więc, że nawet w przypadku, gdy węzły dobierają parametry nieco inaczej, nie jest to przeszkodą do efektywnego działania. W związku z powyższym przeprowadzono dodatkowe testy mające sprawdzić, jak sieć zachowa się w warunkach szczególnych: \begin{itemize}

Każda stacja przeszacowuje liczbę węzłów sieci dwukrotnie

Każda stacja niedoszacowuje liczby stacji i przyjmuje 50\% wartości rzeczywistej \end{itemize}

                 

Wyniki testów w przypadkach szczególnych

Przeszacowanie liczby węzłów prowadzi do mniejszej liczby konfliktów, ale czas potrzebny na wysłanie 10 wiadomości wydłuża się. Odwrotny efekt obserwowany jest w przypadku niedoszacowania liczby węzłów. W ramach zadania udzielano też wsparcia partnerom z Politechniki Wrocławskie w celu umożliwienia porównania wyników testów wybranych algorytmów z wynikami uzyskanymi metodami analitycznymi.

Bibliografia

1. ``Mikrosieci urządzeń M2M w sieciach piątej generacj'' – raport projektu ODOKRIM