Tematem badań w zadaniu 9 była adaptacja algorytmów opracowanych wcześniej do
wersji modelu sieci wieloskokowych (ang.
mutlihop network), w
szczególności dla 2 i 3 skoków. Przeprowadzono rachunki dla przypadku strategii
przekazywania wiadomości przez sensory w modelu asynchronicznym.
Odwrotnie niż dla sieci jednoskokowej (ang.
single hop) gdzie wszystkie
stacje znajdują się w swoim bezpośrednim zasięgu, w sieci typu
multihop
stacje, aby przesłać wiadomość do pewnych innych stacji, muszą korzystać z
węzłów pośredniczących. Jest to zatem naturalne rozszerzenie modelu
komunikacyjnego, które pociąga za sobą potrzebę wprowadzania algorytmów
trasowania (ang.
routing).
Dla analizy w tym zadaniu przyjęto, że odpowiedni algorytm określił trasę
pakietu od nadawcy do odbiorcy jako zbiór stacji pośredniczących z tym, że nie
wszystkie stacje w tym zbiorze muszą pośredniczyć w przekazywaniu
wiadomości. Dla jasności rozumowania, trasę można przedstawić jako linię, na
której rozmieszczono stacje pośredniczące. Dla ustalenia uwagi załóżmy, że wiadomość przekazywana
jest od stacji skrajnie lewej do stacji na drugim końcu.
Przeanalizujmy drogę wiadomości w takim przypadku. Stacja inicjująca rozpoczyna
nadawanie, które jest odebrane przez \emph{pewną grupę} stacji znajdującej się w zasięgu.
\underline{Dokładnie jedna} z nich powinna przejąć funkcję stacji pośredniczącej
i przekazać wiadomość dalej. Ten scenariusz jest powtarzany do momentu
dostarczenia wiadomości do stacji docelowej. Pomysł, że tylko jedna stacja
przejmuje rolę pośrednika można uzasadnić wielorako:
- oszczędność energii sieci jako całości - tylko jedna stacja wystarczy
by przekazać wiadomość, zatem powielanie stacji pośredniczących jest zbędne z
punktu widzenia celu algorytmu;
- wzajemne zagłuszanie stacji pośredniczących - zauważmy, że jeśli dwie
stacje odbiorą wiadomość od źródła (tj. stacji ,,bardziej na lewo'' na
ścieżce), to z pewnością obie są w swoim wzajemnym zasięgu; jeśli rozpoczną
nadawanie wiadomości dalej, może wystąpić kolizja i strata wiadomości, zatem
potrzebny jest dodatkowy mechanizm wyboru lidera (tj. określenia rozłącznych
momentów nadawania dla obu stacji)'
- ograniczenie przestrzenne zasięgu wiadomości - dajmy na to, że algorytm
zezwala na to, by dwie stacje, które usłyszały wiadomość, przekazały
ją dalej (pomijając problemy z punktu powyżej); wtedy, w drugim skoku, stacje
usłyszą już dwie kopie oryginalnej wiadomości, a postępując zgodnie z
algorytmem już cztery stacje będą mogły przekazać wiadomość dalej (po
dwie stacje na każdą kopię); w ten sposób ilość wiadomości w sieci będzie rosła
wykładniczo, co spowoduje problemy z odbiorem wiadomości w stacji docelowej
(por. prace z mechanizmu covergecast z zadania 7).
W opisywanym scenariuszu określono dodatkowy wymóg, aby wiadomość została
dostarczona
najszybciej jak to możliwe. Oczywiście, wiąże się to z
takim doborem stacji pośredniczącej, która znajduje się najdalej na prawo od
źródła wiadomości. W tym celu można wykorzystać siłę sygnału stacji nadającej,
aby estymować odległość od stacji źródłowej i następnie tą estymację wykorzystać
do takiego wyboru prawdopodobieństwa nadawania, że najbardziej odległa stacja
ma największe szanse nadawania.
Opisany pomysł został sformalizowany w pseudokodzie algorytmu 1.
Dla ustalenia uwagi, opiszemy mechanizm jego działania z punktu widzenia stacji ``A''.
Zaproponowany algorytm działa następująco. W pierwszym stanie, ``A'' oraz inne
stacje w zasięgu próbują odebrać wiadomość od stacji nadającej ``N''. Jeśli odbiór się
powiedzie (bez straty ogólności: przez ``A'') to estymowana jest odległość $x$
do stacji nadającej oraz z prawdopodobieństwem $g(x)$ ``A'' wysyła wiadomość
dalej. W tym samym czasie, pozostałe stacje (w tym ``N'') nasłuchują kanał.
Jeśli usłyszą że wiadomość od ``A'' nie została
zagłuszona (kolizja może się zdarzyć, gdyż inne stacje, prócz ``N'', również nadają z
prawdopodobieństwem $g(x)$), to nie będą
próbowały dalej wysyłać, jeśli jednak nastąpi kolizja, lub ``A'' nie nada
(zdarza się to z prawdopodobieństwem $1 - g(x)$), ``N'' ponowi swoją transmisję.
Naturalnie, przy sukcesie nadawania, stacja ``A'' przejmuje rolę stacji ``N'' i
algorytm powtarza się w innej (dalszej od ``N'') części sieci.
Celem naszym jest taki dobór funkcji $g$, aby prawdopodobieństwo, że tylko
jedna stacja nadawała było jak największe i jednocześnie, aby większe
prawdopodobieństwo wyboru miała stacja znajdująca się jak najdalej od stacji
nadającej. Uzasadnienie wyboru funkcji $g$ przedstawimy teoretycznie, zakładając
że stacje zostały rozrzucone w odległościach z rozkładem jednostajnym.
Algorytm 1: OnePassRouting
Inicjalizacja:
$g(x)$ - funkcja zdefiniowana w opisie
Główny algorytm:
if received message $M$
$x \gets$ estymacja odległości bazująca na SNR
if rand$(0,1) < g(x)$
wyślij wiadomość $M$ w następnym slocie
Formalnie, modelujemy naszą sieć jako linię o długości $L$ na której
rozmieszczone jest $n$ stacji. Pozycje tych stacji opisują niezależne zmienne
losowe $X_1, \ldots, X_n$ z rozkładu jednostajnego na odcinku $[0,1]$ tzn. $X_i
\sim \mathcal{U}(0,1)$ dla $i=1, \ldots, n$. Niech $S^1(X_1,\ldots,X_n)$
będzie zmienną losową przyjmującą wartości w zbiorze $\{1, \ldots, n\}$ oraz
reprezentującą numer stacji która wysyłała wiadomość w następnym slocie.
Zatem, prawdopodobieństwo, że dana stacja $i$ wysyła wiadomość
$P(S^1(X_1,\ldots,X_n)=i)$ wynosi
\begin{eqnarray*}
\int_{[0,L]^n} P(S^1(x_1,\ldots, x_n)=i) \cdot
f_{(X_1,\ldots,X_n)}(x_1,\ldots, x_n) d(x_1\ldots x_n),
\end{eqnarray*}
gdzie $f_{(X_1,\ldots,X_n)}$ jest gęstością prawdopodobieństwa zmiennych losowych
$X_1,\ldots,X_n$.
Bez straty ogólności ustalmy $i$ i obliczmy prawdopodobieństwo że $i$-ta stacja
przesyła wiadomość (patrz algorytm 1). Zauważmy, że w
tym przypadku stacja ma pozycję $x_i$ i decyduje czy wysłać wiadomość z
prawdopodobieństwem $g(x_i)$, stąd
\begin{equation}
\label{eq:prob-single-rand}
P(S^1(x_1,\ldots,x_n)=i) = g(x_i) \prod_{j\neq i} (1-g(x_j)).
\end{equation}
Powyższe prawdopodobieństwo opisuje zatem sytuacje, kiedy $i$-ta stacja
wysyła wiadomość poprawnie oraz pozostałe stacje wstrzymują się z transmisją.
Korzystając z twierdzenia Fubiniego i z założenia że zmienne losowe $X_i$ są niezależne,
otrzymujemy $f_{(X_1,\ldots,X_n)}(x_1,\ldots,x_n) = f_{X_1}(x_1) \cdot \ldots \cdot
f_{X_n}(x_n)$ oraz
\begin{equation}
\label{eqn:ps1f}
P(S^1(X_1,\ldots,X_n)=i) = \int_0^L g(x_i) f_{X_i}(x_i) dx_i \prod_{j\neq i} \int_0^L (1-g(x_j))f_{X_j}(x_j)dx_j~.
\end{equation}
Celem algorytmu jest przesłanie wiadomości na jak najdalszą odległość w jednym
hopie. Zatem wprowadźmy zmienną losową, która będzie opisywała odległość
na którą zostanie przesłana wiadomość. Niech
$X_{S^1(X_1,\ldots,X_n)}$ będzie zmienną losową która przedstawia odległość
na którą przesłana zostanie wiadomość w jednym hopie. Ponieważ chcemy
wysłać wiadomość na jak najdalszą odległość to będziemy maksymalizować
ją ze względu na funkcję decyzyjną $g(x)$.
Na początek możemy udowodnić następujące twierdzenie:
Twierdzenie 1
Oczekiwana odległość $E[X_{S^1(X_1,\ldots,X_n)}]$ na którą możemy wysłać wiadomość w jednym hopie
wynosi
\begin{eqnarray*}
\displaystyle \sum_{i=1}^n \int_0^L x_i P(S^1(X_1,\ldots,x_i,\ldots,X_n)=i) f_{X_i}(x_i) dx_i
\end{eqnarray*}
Przeprowadzając podobne rozumowanie wykorzystane przy wyprowadzaniu
równania (\ref{eqn:ps1f}) oraz korzystając z Twierdzenia 1,
otrzymujemy formulę na wartość oczekiwaną
\begin{eqnarray*}
\label{eqn:exp-rand}
\sum_{i=1}^n \int_0^L x_i g(x_i)f_{X_i}(x_i) dx_i \displaystyle\prod_{j\neq i} \int_0^L
(1-g(x_j)) f_{X_j}(x_j)dx_j~.
\end{eqnarray*}
Tak jak wspomnieliśmy wcześniej, funkcja $g(x_i)$ wprowadzona w algorytmie 1
pozwala na sterowanie wartością oczekiwaną odległości na którą możemy wysłać wiadomość
oraz Twierdzenie 1 dostarcza nam zatem sposobu na optymalizację.
Idealnie byłoby optymalizować po wszystkich możliwych funkcjach $g(x_i)$.
Jednakże, w tym przypadku udało nam się znaleźć zwarte postacie dla
kilku wybranych funkcji:
-
Niech $X_i \sim \mathcal{U}(0,1)$ będą niezależnymi zmiennymi losowymi.
Rozważmy wtedy przypadek jeśli funkcja $g(x)$ jest stała. W tym przypadku (patrz
[1]) optymalna funkcja ma postać $g(x) = 1/n$.
Podstawiając ją do równania (\ref{eqn:ps1f}) otrzymujemy
\begin{equation*}
P[S^1(X_1,\ldots,X_n)=i] = \frac{1}{n}\left(1-\frac{1}{n} \right)^{n-1}.
\end{equation*}
Wtedy, korzystając z Twierdzenia 1 mamy
\begin{equation*}
E[X_{S^1(X_1,\ldots,X_n)}] = \frac{1}{2}\left(1-\frac{1}{n} \right)^{n-1}~.
\end{equation*}
-
Z innej strony, rozważmy funkcję $g$ której wartość zależy od odległości
tak, że stacje które są dalej mają większe prawdopodobieństwo że będą
wysyłać wiadomość w następnym slocie. Dalej zakładamy,że $X_i \sim
\mathcal{U}(0,1)$. Bazując na symulacjach wybraliśmy $g(x)=x^{n-1}$. W tym
przypadku możemy obliczyć wartość oczekiwaną
\begin{equation*}
E[X_{S^1(X_1,\ldots,X_n)}] = \frac{n}{n+1}\left(1-\frac{1}{n} \right)^{n-1}~.
\end{equation*}
Wyraźnie te dwa przypadki pokazują nam że możemy znacząco poprawić wartość
oczekiwaną na którą zostanie wysłana wiadomość. Dokładnie z $1/(2 e)$
dla stałej funkcji $g(x)=1/n$ do $n/((n+1)e)$ dla naszej wybranej $g(x) = x^{n-1}$.
Widać więc, że asymptotycznie mamy podwójną poprawę. Jednakże, w jednej próbie
mamy duże ograniczenie co do prawdopodobieństwa sukcesu nadania, dlatego
dalej wprowadzimy algorytm który dodatkowo rozwiąże i ten problem.
Rozszerzmy teraz algorytm 1 do wersji
wieloetapowej, patrz algorytm 2.
Naszym celem jest zwiększenie prawdopodobieństwa osiągnięcie stacji docelowej.
Chcielibyśmy to osiągnąć przez powtarzanie transmisji dopóki przesyłana wiadomość
zostanie poprawie wysłana.
Algorytm 2 MultiPassRouting
Inicjalizacja:
$g^m(x)$ - funkcja zdefiniowana w opisie
Główny algorytm:
if received message $M$
$x \gets$ estymacja odległości bazująca na SNR
$m \gets 0$
repeat
if rand$(0,1) < g^m(x)$
wyślij wiadomość $M$ w następnym slocie
$m \gets m + 1$
until pewnej stacji wysłała poprawnie wiadomość
Dla tak uogólnionego algorytmu obliczmy teraz prawdopodobieństwo, że wybrana
stacja $i$ wyśle poprawie wiadomość. Obliczmy $P(S^\infty(x_1,\ldots,x_n)=i)$,
gdzie $S^{\infty}(x_1,\ldots,x_n)$ jest zmienną losową zwracającą numer stacji
która poprawie wysłała wiadomość. Pozycje stacji oznaczmy przez $x_i$ oraz
prawdopodobieństwo retransmisji przez $g^m(x_i)$ w $m$-tym etapie. Otrzymujemy
uogólnione równanie (\ref{eq:prob-single-rand}) na prawdopodobieństwo
\begin{equation*}
P(S^\infty(x_1,\ldots,x_n)=i) = \sum_{m=0}^\infty g^m(x_i) \prod_{j\neq i} (1-g^m(x_j)) \cdot
\Bigl(1 - \sum_k g^m(x_k) \prod_{j\neq k} (1-g^m(x_j)) \Bigr)^m~.
\end{equation*}
W szczególnym przypadku, gdy funkcja $g^m(x)$ jest taka sama dla każdego etapu
tzn. dla każdego $m$ mamy $g^m(x) = g(x)$. Wtedy otrzymujemy nieskończony
szereg geometryczny, który możemy zapisać w postaci
\begin{eqnarray*}
P(S^\infty(x_1,\ldots,x_n)=i) = \frac{\displaystyle g(x_i) \prod_{j\neq i}
(1-g(x_j))}{ \displaystyle \sum_{k=1}^n g(x_k) \prod_{j\neq k} (1-g(x_j)) }.
\end{eqnarray*}
Możemy, także udowodnić następujące twierdzenie:
Twierdzenie 2
\begin{equation}
E[X_{S^\infty(X_1,\ldots,X_n)}] =
\displaystyle \sum_{i=1}^n \int_0^L x_i
P(S^{\infty}(X_1,\ldots,x_i,\ldots,X_n)=i) f_{X_i}(x_i) dx_i
\end{equation}
Podobnie jak w poprzednim algorytmie znajdziemy zwarte formuły wartości
oczekiwanej dla kilku wybranych funkcji:
-
Rozważmy $g^m(x) = p$, co oznacza że wszystkie stacje które odebrały
wiadomość będą nadawały ze stałym takim samym prawdopodobieństwem bez
względu na estymację odległości. Wtedy prawdopodobieństwo
$P(S^1(x_1,\ldots,x_n)=i)=p (1-p)^{n-1}$, zatem
\begin{equation*}
P(S^\infty(x_1,\ldots,x_n)=i) =
\frac{\displaystyle p (1-p)^{n-1}}{\displaystyle \sum_{k=1}^n p
(1-p)^{n-1}} = \frac{1}{n}.
\end{equation*}
Stąd przez wybór stałego prawdopodobieństwa dla wszystkich stacji otrzymujemy
jednostajne prawdopodobieństwo odebrania wiadomości. Zakładając, że
$X_i \sim \mathcal{U}(0,1)$, możemy łatwo obliczyć, że
\begin{equation*}
E[X_{S^\infty(X_1,\ldots,X_n)}] = \frac12~.
\end{equation*}
-
\label{itm:multistep-hyb}
W tym przypadku rozważmy następującą funkcję
\begin{equation*}
g^m(x) = \left\{\begin{array}{lcl}
x^{n-1} & \mbox{ dla } & m=0 \\
p & \mbox{ dla } & m \geq 1
\end{array} \right.~.
\end{equation*}
Zatem, w pierwszym etapie wykorzystujemy funkcje $x^{n-1}$, w następnych
etapach stałe prawdopodobieństwo $p$. Wtedy możemy obliczyć
\begin{equation*}
P(S^{\infty}(x_1,\ldots,x_n)=i) =
x^{n-1}_i \prod_{j \neq i} (1-x^{n-1}_j) + \frac1n
\bigl(1-\sum_{k=1}^n x^{n-1}_k \prod_{j\neq k} (1-x^{n-1}_j)\bigr)~.
\end{equation*}
Natomiast, oczekiwana odległość na którą możemy wysłać wiadomość wynosi
\begin{equation*}
E[X_{S^{\infty}(X_1,\ldots,X_n)}] = \frac12 \bigl( 1 + \frac{n}{n+1}(1-\frac1n)^n\bigr)
\end{equation*}
Asymptotycznie poprawiamy więc odległość z $1/2$ to $1/2 + 1/2e$.
Zauważmy, że przedstawiony scenariusz jest rozwiązaniem
hybrydowym tzn. łączy on dwa poprzednio badane rozwiązania. Rozwiązanie to ma dwie
ważne zalety. Dostajemy rozwiązanie, które jest bardziej stabilne i symulacje pokazują,
że sprawdza się również w przypadkach nie tylko rozkładu jednostajnego stacji.
Po drugie możliwe było znalezienie zwartej postaci analitycznej wartości oczekiwanej.
[1] Koji Nakano and Stephan Olariu, A Survey on Leader Election Protocols for Radio
Networks, Proc. International Symposium on Parallel Architectures, Algorithms,
and Networks (I-SPAN), pp. 71--76, May, 2002