AKADEMIA TECHNICZNO-ROLNICZA

W

BYDGOSZCZY

SIECI TELEKOMUNIKACYJNE i SYGNALIZACJA

Temat projektu: Analiza ruchowa hierarchicznej sieci

telekomunikacyjnej z pojedynczym węzłem

tranzytowym.

Prowadzący: Opracowali:

dr inż. Ireneusz Olszewski studenci IX sem.

WTiE SKC:

Wojciech Albrecht

Marek Matyjasek

ATR BYDGOSZCZ 1999

Dla danych macierzy ruchu oraz wektora liczności wiązek należy przeprowadzić analizę ruchową sieci hierarchicznej w sposób analityczny (wykorzystując model jednoparametrowy) oraz symulacyjny.

Struktura analizowanej sieci.

W zadanym zadaniu projektowym należy:

1. Wyznaczyć analitycznie globalne prawdopodobieństwo blokady w funkcji globalnego przeciążenia. Przyjąć zakres przeciążenia od 0 - 100% (co 10%).

2. Wyznaczyć globalne prawdopodobieństwo blokady w funkcji globalnego przeciążenia (zakres przeciążeń j.w.), korzystając z modelu symulacyjnego.

Uzyskane wyniki z punktu 1 i 2 przedstawić na wspólnym wykresie.

3. Wyznaczyć indywidualne prawdopodobieństwo blokady dla losowo wybranej relacji w funkcji globalnego przeciążenia, korzystając z modelu analitycznego i symulacyjnego. Wyniki przedstawić na wspólnym wykresie.

4. Wyznaczyć ruch przenoszony przez sieć w funkcji globalnego przeciążenia na podstawie zależności analitycznych oraz wyników uzyskanych na drodze symulacji. Wyniki przedstawić na wspólnym wykresie.

5. Wyznaczyć efektywność ruchową sieci w funkcji globalnego przeciążenia (zakres przeciążeń analogicznie jak w pkt.1) na podstawie zależności analitycznych oraz wyników uzyskanych na drodze symulacji. Wyniki umieścić na wspólnym wykresie.

Dane wejściowe

1. Macierz ruchu [A_ij]

2. Macierz liczności wiązek [n_ij]

1. Wstęp teoretyczny.

1.1. Globalne prawdopodobieństwo blokady (GPB) w funkcji globalnego przeciążenia.

Założenia.

1. Przyjmujemy poissonowski potok zgłoszeń w poszczególnych relacjach sieci, z wykładniczym rozkładem czasów obsługi tych zgłoszeń;

2. Rozkłady liczb zajętych łączy w wiązkach są statystycznie niezależne;

3. Węzły są nieblokowalne;

4. Zgłoszenia napotykające na blokadę są tracone i nie powracają do ponownej obsługi;

5. Sieć jest w równowadze statystycznej;

6. Czas zestawiania połączenia jest pomijalnie mały w stosunku do średniego czasu obsługi zgłoszenia;

7. Ruch oferowany wiązkom bezpośrednim i finalnym w rozważanej sieci ma charakter poissonowski.

Prawdopodobieństwo blokady w rozpatrywanej relacji wyraża się wzorem:

B_ij = b_ij • (1 - (1 - b_it) • (1 - b_tj)) (1)

gdzie:

b_ij - prawdopodobieństwo blokady wiązki bezpośredniej w relacji i-j

b_it - prawdopodobieństwo blokady wiązki finalnej (dla relacji i-t) „w górę”

b_tj - prawdopodobieństwo blokady wiązki finalnej (dla relacji t-j) „w dół”

Prawdopodobieństwa b_ij dla każdej grupy bezpośredniej można obliczyć z PWE (Pierwszego Wzoru Erlanga) na podstawie ruchu oferowanego danej relacji i liczbie jej łączy.

Pierwszy wzór Erlanga określa nam rozkład prawdopodobieństwa zajęcia n-łączy telefonicznych dla danego ruchu a oferowanego grupie łączy oraz dla danej liczności wiązki w rozpatrywanej relacji.

(2)

PWE spełnia następującą zależność rekurencyjną:

(3)

Właściwość rekurencyjna jest szczególnie przydatna w przypadku wykorzystania jej do obliczania wartości funkcji Erlanga w programie komputerowym, gdzie znacznym utrudnieniem lub wręcz niemożliwością jest obliczenie wartości silni dla dużych liczb (liczności wiązek).

Rozkład Erlanga ma tą właściwość, że jest prawdziwy dla dowolnego rozkładu czasu trwania obsługi zgłoszenia. Kolejną własnością PWE jest możliwość obliczenia z tego wzoru prawdopodobieństwa blokady zgłoszeń (tzw. współczynnika blokady). Wystarczy podstawić do wzoru k = n (mamy wówczas zajęte wszystkie łącza w danej wiązce, a więc blokadę). Wartość a nazywamy natężeniem ruchu oferowanego grupie łączy, wartość a*(1 - b) natężeniem ruchu przenoszonego przez grupę łączy, a a*b - natężeniem ruchu przelewanego z grupy.

Aby obliczyć globalne prawdopodobieństwo blokady musimy znać prawdopodobieństwa blokady w poszczególnych relacjach.

We wzorze (1) prawdopodobieństwo b_ij obliczamy bezpośrednio na podstawie danych w zadaniu, natomiast prawdopodobieństwa b_it oraz b_tj obliczone zostały z następujących wzorów:

ruch oferowany „w górę” w relacji i-t

(4)

ruch oferowany „w dół” w relacji t-j

(5)

Gdy mamy już obliczony ruch dla wiązek finalnych możemy wyznaczyć prawdopodobieństwo blokady dla wiązek finalnych b_it oraz b_tj korzystając z PWE. Teraz mamy już wszystkie dane do obliczenia współczynnika strat B_ij (prawdopodobieństwa odrzucenia zgłoszenia).

Globalne prawdopodobieństwo blokady GPB występuje wówczas gdy nie może zostać zrealizowane żadne połączenie w rozpatrywanej sieci, tzn. wszystkie łącza w wiązkach są zajęte.

GPB możemy wyznaczyć z następującego wzoru:

(6)

, gdzie: GPB to globalne prawdopodobieństwo blokady tej sieci,

B_ij otrzymano wcześniej z (1).

Ruch przenoszony możemy obliczyć ze wzoru ogólnego: A_p = (1−B)⋅A, który dla analizowanej sieci przyjmie postać:

, i
j (7)

Z kolei efektywność ruchowa sieci została policzona następująco:

, i
j (8)

gdzie n_ij jest liczbą łączy (wiązką łączy) relacji (i, j) - z danej macierzy liczności wiązek [N].

Globalne przeciążenie sieci o n % jest rozumiane jako wzrost wszystkich indywidualnych wartości ruchu oferowanego w macierzy ruchu o n %

1.2. Indywidualne prawdopodobieństwo blokady w funkcji globalnego przeciążenia.

Indywidualne prawdopodobieństwo blokady występuje wówczas gdy nie można zrealizować żadnego połączenia w rozpatrywanej relacji, co oznacza, że bezpośrednia droga połączeniowa (tzw. wiązka wysokiego wykorzystania) jest niedostępna, czyli wszystkie łącza w wiązce są zajęte i jednocześnie co najmniej jedna wiązka na drodze obejściowej, prowadzącej przez węzeł tranzytowy, jest w stanie blokady (czyli identycznie jak dla drogi bezpośredniej wszystkie łącza są zajęte). Indywidualne prawdopodobieństwo blokady obliczamy ze wzoru (1).

1.3. Ruch przenoszony przez sieć w funkcji globalnego przeciążenia.

Ruch przenoszony przez sieć jest to. Ruch przenoszony przez sieć można obliczyć ze wzoru (7)

1.4. Efektywność ruchowa sieci w funkcji globalnego przeciążenia.

Efektywność ruchowa sieci jest to stosunek ruchu przenoszonego przez sieć do sumy liczności wiązek w całej sieci. Efektywność ruchowa wyraża się wzorem (8)

Metoda symulacyjna.

W omawianym zadaniu projektowym symulację sieci wykonano za pomocą tzw. metody Monte Carlo. Została ona wybrana ze względu na swoją skuteczność oraz prostą implementację.

W metodzie Monte Carlo numerujemy relacje w sieci kolejnymi liczbami naturalnymi od 1 do K. Tworzymy wektor stanu W(*), który składa się z dwóch części. Część pierwsza o stałej długości M(m) =  reprezentuje sumę intensywności w poszczególnych relacjach oraz część druga o zmiennej długości m reprezentująca liczbę trwających rozmów. W chwili rozpoczęcia symulacji wektor W(*) ma długość M(m) = . W rzeczywistości wektor stanu jest 10 razy dłuższy, gdyż w warunkach przeciążenia mamy możliwość odwzorowania przeciążenia o zadany procent, np. dla intensywności  = 5 Erl wzrost przeciążenia o 10% powoduje wzrost długości wektora stanu z 50 do 55 jednostek. Następnie obserwujemy długość wektora W(*), która po pewnym czasie zaczyna oscylować wokół pewnej wartości. Jest to spowodowane tym, że w symulowanej sieci jest obsługiwana ciągle pewna liczba zgłoszeń, a intensywność napływu nowych zgłoszeń i ich obsługi wyrównuje się (liczba połączeń jest tego samego rzędu co liczba rozłączeń).

Jeżeli zostanie wylosowana liczba j z przedziału 0 ÷  wówczas, jeżeli jest wolne łącze w wiązce, w relacji W(j), to realizowane jest połączenie bezpośrednie i wydłużany jest wektor stanu W(*) o 10 jednostek. Jeżeli nie ma wolnego łącza bezpośredniego to sprawdzane są łącza na drodze tranzytowej. Gdy można zestawić połączenie to zwiększany jest wektor stanu o 10 i jednocześnie zapamiętywana jest informacja o tym, że jest to połączenie tranzytowe. Natomiast jeżeli nie ma wolnych łączy na drodze tranzytowej wówczas połączenie jest odrzucone.

Jeżeli zostanie wylosowana liczba j z przedziału  ÷ m wówczas wykonuje się procedura rozłączenia danego połączenia. W miejsce 10 rekordów rozłączanej relacji jest wstawianych 10 rekordów z końca wektora, wektor jest skracany o 10 jednostek i zwalniane jest odpowiednie łącze (połączenie bezpośrednie) lub łącza (w przypadku połączenia tranzytowego).

Dla metody symulacyjnej konieczne jest dokonanie estymacji otrzymanych wyników.

2. Algorytmy programów do obliczania wyników metodą analityczną i symulacyjną.

Metoda symulacyjna:

for IloscProb=1 to 10 do

begin

for LiczbaWywolan=1 to 100000 do

begin

Krok 1: (losowanie)

j := random(M(n)); (M(m) =  + m)

if  < j ≤ M(m) then Krok 3

Krok 2 (nawiązywanie połązczenia)

k := W[j]; (k - numer relacji)

x,y := Konwersja (k);

if n[x,y] > 0 then (n[x,y] - macierz liczności wiązek)

begin (połączenie bezpośrednie)

dec(n[x,y]);

inc(LicznikZgloszenPrzyjetych);

end

else

if (n[x,6] > 0) and (n[6,y] >0) then

begin (połączenie tranzytowe)

dec(n[x,6]);

dec(n[6,y]);

inc(LicznikZgloszenPrzyjetych);

end

else (zgłoszenie odrzucone)

inc(LicznikZgloszenOdrzuconych);

Krok 3 (rozłączenie)

W[j] := W[M(m)];

dec(M(m));

end;

Oblicz GPBi;

end;

Oblicz GPB;

Oblicz Ap;

Oblicz ;

Metoda analityczna:

function Erlang(Aof:real;n:integer):real;

var

rekurencja:real;

begin

if n=0 then Erlang:=1 else

begin

rekurencja:=Erlang(Aof,n-1);

Erlang:=Aof*rekurencja/(n+1+Aof*rekurencja);

end;

end;

procedure Obliczenia;

var

i,j,k:byte;

begin

for i:=1 to 5 do

for j:=1 to 5 do

begin

Blok[i,j]:=Erlang(A[i,j],n[i,j]); (p-stwo blokady wiązek bezpośrednich)

Aof[i,j]:=A[i,j];

end;

(Aof w górę------------------------------------------)

for i:=1 to 5 do

for j:=1 to 5 do

begin

Aof[i,6]:=0;

for k:=1 to 5 do

Aof[i,6]:=Aof[i,6]+A[i,k]*Blok[i,k];

Blok[i,6]:=Erlang(Aof[i,6],n[i,6]);

end;

(Aof w dół-------------------------------------------)

for i:=1 to 5 do

for j:=1 to 5 do

begin

Aof[6,i]:=0;

for k:=1 to 5 do

Aof[6,i]:=Aof[6,i]+A[k,i]*Blok[k,i];

Blok[6,i]

:=Erlang(Aof[6,i],n[6,i]);

end;

{----------------------------------------------------}

for i:=1 to 5 do

for j:=1 to 5 do

begin

Bij[i,j]:=Blok[i,j]*(Blok[i,6]+Blok[6,i]);

end;

end;

function GPB:real;

var

licznik,mianownik:real;

i,j:byte;

begin

licznik:=0;

mianownik:=0;

for i:=1 to 5 do

for j:=1 to 5 do

begin

licznik:=licznik+A[i,j]*Bij[i,j];

mianownik:=mianownik+A[i,j];

end;

SAof:=mianownik;

GPB:=licznik/mianownik;

end;

var

i,j:byte;

begin

Sn:=0; (Sn - suma wszystkich wiązek)

for i:=1 to 6 do for j:=1 to 6 do Sn:=Sn+n[i,j];

Obliczenia;

write('przeciążenie sieci=');write((p-1)*100:3:1);writeln(' %');

write('GPB= ');writeln(GPB:10:8);

write('Ap= ');writeln(SAof*(1-GPB):10:8); (Ap - ruch przenoszony)

write('n= ');writeln(SAof*(1-GPB)/Sn:10:8); (n - efektywność ruchowa)

write('Bindywid dla rel.3-4= ');writeln(Bij[3,4]:10:8);

end.

3. Uzyskane wyniki.

Wyniki obliczone analitycznie.

Przeciążenie	GPB [%]	B3-4 [%]	Ap [Erl]	 [%]
0 %	0,026	0,028	97,97	48,03
10 %	0,208	0,265	107,58	52,73
20 %	0,979	1,263	116,45	57,08
30 %	2,960	3,676	123,63	60,60
40 %	6,476	7,654	128,32	62,90
50 %	11,345	12,842	130,32	63,88
60 %	17,119	18,744	129,96	63,70
70 %	23,354	24,955	127,69	62,59
80 %	29,721	31,202	123,97	60,77
90 %	36,011	37,321	119,15	58,41
100 %	42,101	43,222	113,48	55,63

Wyniki uzyskane metodą symulacyjną.

Przeciążenie	GPB [%]	B3-4 [%]	Ap [Erl]	 [%]
0 %	2,190 ± 0,079	1,826 ± 0,079	95,85	46,99
10 %	4,325 ± 0,096	3,306 ± 0,054	103,13	50,56
20 %	6,971 ± 0,134	5,645 ± 0,164	109,40	53,63
30 %	10,219 ± 0,178	7,951 ± 0,105	114,80	56,07
40 %	13,611 ± 0,171	10,384 ± 0,062	118,53	58,10
50 %	17,091 ± 0,143	13,888 ± 0,245	121,87	59,74
60 %	20,446 ± 0,145	16,760 ± 0,265	124,74	61,15
70 %	23,812 ± 0,168	19,175 ± 0,160	126,93	62,22
80 %	26,749 ± 0,142	22,042 ± 0,146	129,21	63,34
90 %	29,738 ± 0,127	24,798 ± 0,197	130,83	64,13
100 %	32,362 ± 0,178	27,119 ± 0,347	132,57	64,99

4. Analiza uzyskanych wyników.

1

3

2

5

4

6

---