Comunicatii cu acces multiplu

Comunicatii cu acces multiplu

1. Distributia Poisson.

Fie expresia probabilitatii de a avea k mesaje in decursul duratei τ:

cu λ _t rata totala de aparitie a mesajelor.

a) Sa se verifice ca expresia de mai sus este o functie densitate de probabilitate corect definita a unei variabile aleatoare discrete.

b) Sa se determine valoarea medie a variabilei aleatoare discrete avand functia densitate de probabilitate prezentata mai sus.

c) Sa se verifice consistenta rezultatului prezentat la punctul b).

Rezolvare.

a)     Pentru simplificare se considera ca parametrul a este dat de a = λ _t τ si se rescrie expresia probabilitatii anterior definita ca fiind:

b)    

Se poate verifica faptul ca P(k) este o functie densitate de probabilitate a unei variabile aleatoare discrete calculand suma de mai jos a carei valoare trebuie sa fie 1. Se obtine:

Se observa ca s-a utilizat dezvoltarea in serie Taylor a functiei exponentiale.

b) Valoarea medie a variabilei aleatoare discrete x avand densitatea de probabilitate P(k) este

c) Asa cum s-a precizat, numarul mediu de mesaje ce pot exista la un moment dat este λ _t τ . Pe de alta parte, din modul in care au fost definite marimile λ _t si τ: λ _t - rata de aparitie a mesajelor, iar τ - durata unui mesaj, rezulta ca produsul λ _t τ  reprezinta chiar valoarea numarului mediu de mesaje care pot sa apara la un moment dat (traficul). Ca urmare consistenta rezultatului de la punctul anterior este justificata.

2. Comunicatiile in cadrul sistemelor Alloha ca procese Poisson.

Se presupune ca transmiterea si retransmiterea pachetelor pot fi decrise ca avand o distributie statistica de tip Poisson, cu alte cuvinte probabilitatea de a sosi k mesaje in intervalul t este

unde cu λ _t s-a notat rata totala de aparitie a mesajelor. Se considera o retea care foloseste pentru accesul multiplu algoritmul Alloha cu segmente temporale (Slotted - Alloha) la care rata totala de transfer a pachetelor este λ _t = 10 pachete / secunda, iar durata unui pachet τ = 10 ms. Se cere:

a) sa se calculeze probabilitatea ca un pachet transmis:

- sa nu intre in coliziune cu vreun un alt pachet, P

- sa intre in coliziune cu un singur pachet, P

- sa intre in coliziune cu cel putin un pachet, P

b) daca in caz de coliziune, statia incearca transferul pachetului dupa T  = n τ , unde n = 9, sa se determine probabilitatea ca dupa T = m τ , cu m = 100, pachetul sa nu fie inca transmis. Dupa cat timp probabilitatea ca pachetul sa fi fost transmis este de 0,9999 ?

c) sa se compare rezultatele obtinute pentru acest algoritm cu performantele algoritmului Pure - Alloha caracterizat prin aceeasi parametri.

Rezolvare.

a)     Probabilitatea ca un pachet sa fie transmis cu succes se exprima ca probabilitatea ca in intervalul τ ales sa nu se transmita vreun alt pachet, deci valoarea expresiei (09.02.01) in punctul k = 0. De asemenea, probabilitatea ca un pachet sa intre in coliziune cu un singur pachet, respectiv cu cel putin un pachet, se exprima ca valoarea expresiei (09.02.01) in punctul k = 1, respectiv complementul valorii expresiei (09.02.01) in punctul k = 0. Pentru sistemul S-Alloha expresiile probabilitatilor cerute sunt:

b)

Pentru sistemul P-Alloha, deoarece pachetele sunt transmise aleator, probabilitatea de aparitie simultana a unui numar de k mesaje se calculeaza pe durata 2τ, expresia acesteia fiind

Valorile probabilitatilor cerute sunt:

c) Algoritmul incercarilor de reluare a transmisiei pachetului dupa coliziune poate fi sintetizat ca mai jos:

1. Incercarea i = 1.

- Δt = 0 (timpul scurs de la inceputul transmisiei);

- probabilitatea ca dupa i incercari sa apara coliziune este P

2. Incercarea i = 2.

- Δt = (n + 1) τ (timpul scurs de la inceputul transmisiei este τ - durata emisiei pachetului plus nτ - timpul de asteptare);

- probabilitatea de insucces dupa i = 2 incercari este P

i. Incercarea i .

- Δt = (n + 1) τ (i - 1);

- probabilitatea de insucces dupa i incercari este P ⁱ

Ca urmare, timpul scurs dupa i incercari  este (n + 1) (i - 1) τ + τ. Impunand conditia ca dupa T = m τ operatia sa aiba insucces, rezulta:

m τ = (n + 1) τ (i - 1) + τ ,

deci numarul incercarilor de retransmisie a pachetului este dat de

Daca raportul este irational numarul incercarilor disponibile in intervalul T este

unde cu [x] s-a notat partea intreaga a lui x. In cazul de fata, i = 10 si probabilitatea ca dupa T pachetul sa fie netransmis este P ⁱ, deci

Pentru a determina durata dupa care probabilitatea de transfer a pachetului este superioara valorii p = 0,9999 se impune conditia

P ⁱ  1 - p ,

si rezulta

Deci

3. Probabilitatea ca un pachet sa nu poata fi transmis intr-un interval T cand intarzierea este o variabila aleatoare.

Se considera o retea P-Alloha caracterizata prin rata totala de transfer λ _t = 10 pachete / secunda si faptul ca o statie reia transmisia pachetului rejectat dupa o durata T  , durata T fiind o variabila aleatoare avand distributia f(x), cu f(x) = 0 pentru x < 0.

Sa se determine probabilitatea ca dupa T = m τ , cu m = 5 mesajul sa fie inca netransmis.

Sa se particularizeze rezultatul pentru distributia uniforma a variabilei aleatoareT

Rezolvare.

In problema precedenta s-a aratat ca probabilitatea ca un pachet sa fie rejectat in sistemul P-Alloha este

P  = 1 - exp [ - 2 τ λ _t

Procesul de retransmisie poate fi modelat dupa cum urmeaza:

1. Incercarea i = 1.

- cu probabilitatea P mesajul nu este transmis.

1.1. Cu probabilitatea P  P durata t dupa care se incearca retransmiterea unui pachet nu se incadreaza in durata alocata ( t  > T - 2 τ ; se scade durata primului mesaj si durata unui eventual mesaj a carui transmisie ar putea incepe, dar nu s-ar termina in cadrul duratei T). Deci:

P  = P (t  > T - 2 τ) .

Ca urmare, cu probabilitatea P  P dupa transmiterea primului pachet retransmiterea nu se mai incadra in durata alocata.

1.2. Cu probabilitatea P  (1 - P  ) se acorda a doua incercare in timp util.

2. Incercarea i = 2

 - cu probabilitatea P  nici a doua oara nu se reuseste transferul.

2.1. Cu probabilitatea P  P durata t dupa care se incearca retransmiterea pachetului nu permite transferul (se poate scrie t  + t  > T - 3τ ), deci:

unde cu f(x) am notat distributia duratei de asteptare si

2.2.Cu probabilitatea P  (1 - P  ) se acorda a treia incercare in timp util.

i. Incercarea i

- cu probabilitatea P ⁱ nici a 'i' - a oara mesajul nu este acceptat.

i.1. cu probabilitatea P ⁱ P_i durata t _i dupa care se incearca retransmiterea pachetului nu permite transferul; valoarea probabilitatii P _i se calculeaza pentru

deci expresia sa este

unde

i.2. cu probabilitatea P ⁱ ( 1 - P_i ) se acorda a 'i' - a incercare in timp util.

Numarul maxim de incercari este egal cu cel mai mare intreg mai mic strict decit T / τ, deci

in cazul de fata avem τ = 4. Deci probabilitatea ca dupa durata T pachetul sa fie retransmis este

P_N = P  P  + P  P  +  + P ^q - 1 P_q - 1 + P ^q

(dupa incercarea q nu mai exista posibilitatea retransmisiei pachetului in timp util, deci P_q = 1 si P ^q+1(1 - P_q ) = 0), deci

Pentru cazul particular al problemei se obtine:

Intrucat x  + x  > T - 3 τ , rezulta x  > t - 3 τ - x , deci x  > max . De asemenea x , x I [ 0, 5τ ] si x  _ 5τ , deci

Deci x  > T - 4 τ - x  - x  = τ - ( x  + x  ) si se calculeaza integrala tripla definita

mai sus:

Se face schimbarea de variabila t = x  + x , cu t I [ x , x  + 5τ ] si se obtine:

De asemenea

unde

deci U este discontinua intr-un singur punct ( x , x , x , x ) = (0, 0, 0, 0), in rest fiind constanta si egala cu 1. Intrucat acest punct de discontinuitate este o multime de marime nula, integrala P este unitara. Ca urmare valorile probabilitatilor calculate sunt:

P  = 0,4 , P  = 0,92 , P  = 0,99867 , P

deci probabilitatea ca dupa durata T mesajul sa nu fie inca transmis este

P_N

In mod similar se poate rezolva problema pentru sistemele S - Alloha, singura deosebire fiind ca in acest caz se va lucra cu variabile aleatoare discrete.

4. Eficienta in utilizarea canalului.

Fie un sistem cu acces multiplu care foloseste un canal avand rata maxima R = 50 kbiti / secunda. In sistem opereaza cu M = 10 statii de sol. Fiecare statie poate sa transmita λ  = 2 pachete / secunda. Sistemul lucreaza cu b = 1350 biti / pachet.

Se cere:

a)     sa se calculeze traficul util normat ρ;

b)    sa se precizeze care din algoritmii P-Alloha, S-Alloha sau R-Alloha poate fi utilizat; Sistemul Alloha cu rezervare (Reservation-Alloha) disponibil foloseste 2 segmente temporale pentru receptia pachetelor si unul pentru subdiviziunile temporale in decursul carora se fac rezervarile.

Rezolvare.

a.      Traficul util normat este dat de relatia:

b. Se compara traficul util normat cu traficul maxim acceptat de fiecare algoritm:

. Sistemul P-Alloha

. Sistemul S-Alloha

ρ _max pentru sistemul S-Alloha:

. Sistemul R-Alloha

ρ _max = 2 / 3 = 0,67, si intrucat ρ _max > 0,54;

5. Numarul maxim de statii ce pot partaja un canal P-Alloha.

Un grup de M statii la sol utilizeaza un canal avand rata maxima de transfer de R = 56 kbiti / s pentru transferul unor pachete de date pe baza unui algoritm de acces S-Alloha. Fiecare statie incearca transferul unui pachet la un interval mediu de 10 secunde, indiferent daca pachetul anterior a fost sau nu transmis. Fiecare pachet contine b = 3000 biti. Se cere determinarea numarului maxim de statii care pot utiliza canalul in ipoteza ca procesul de transfer al mesajelor poate fi modelat ca proces Poisson.

Rezolvare.

 _max = ( e )

Deci:

cu λ  = 0,1 pachete / s.

Rezulta:

M_max

6. Un grup de M = 3 statii utilizeaza prin acces multiplu un canal avand capacitatea maxima de transfer R = 56 kbiti / s pe baza algoritmului P-Alloha. Ratele totale medii de transmitere a informatiei de catre cele 3 statii sunt: R  = 7,5 kbiti / s, R  = 10 kbiti / s si R  = 20 kbiti / s.

Dimensiunea fiecarui pachet este b = 100 biti / pachet. Sa se determine:

a)     traficul total normat G;

b)    traficul util normat ρ;

c)     rata de transfer corect a pachetelor, λ;

d)    probabilitatea de transfer corecta a unui mesaj P si

Se presupune ca procesul de transfer poate fi modelat ca un proces Poisson.

Rezolvare

a. Traficul total este:

rezulta

 _t = 375 pachete / s .

Se observa

R  + R  + R  < R .

Traficul total este:

G = λ _t unde τ = b / R .

Deci:

b. Traficul util normat:

c.

Rata pachetelor transmise corect se deduce din relatia ρ = λ τ ,

d. Probabilitatea de transfer corect a unui mesaj este

7. Tratarea algoritmului P-Alloha in termenii densitatii comune de probabilitate.

Se considera un sistem de comunicatie care lucreaza pe baza algoritmului P-Alloha, in care mesajele apar ca in figura 09.07.01, unde:

- sagetile reprezinta momentele de aparitie a pachetelor;

- N _n , respectiv N _n + 1 , este numarul pachetelor sosite in intervalul ( T _n - 1 , T _n ] , respectiv ( T _n , T _n + 1

- τ durata unui pachet in s.

Rata totala de transfer este λ _t . Se presupune ca incercarile de transmitere a 2 mesaje oarecare reprezinta fenomene independente.

Se cere:

a) sa se scrie expresia densitatii comune de probabilitate, f ( N _n , N _n + 1 ) , ca in intervalul ( T _n - 1 , T _n ] sa soseasca N _n mesaje, iar in intervalul ( T _n , T _n + 1 ] N _n + 1 pachete;

b) fie T_n momentul la care soseste pachetul utilizatorului A. Sa se exprime, in termenii densitatii comune de probabilitate f ( N _n , N _n + 1 ) , probabilitatea ca transmisia utilizatorului A sa nu intre in coliziune cu o alta;

c) in ipotezele anterioare, sa se exprime, in termenii densitatii comune de probabilitate f ( N _n , N _n + 1 ) , probabilitatea ca transmisia utilizatorului A sa intre in coliziune cu un numar p > 0 de alte transmisiuni.

Rezolvare.

a) Fie doua variabile aleatoare u si v. Atunci si sunt evenimente avand probabilitatile P(u   x) = F _u (x) si P(v   y) = F _v (y) , unde F _u (x), F _v (y) sunt functiile de distributie ale variabilelor aleatoare u, v. In mod evident produsul   =  este constituit din multimea realizarilor ξ astfel incat u(ξ)   x _i v(ξ)   y si, in conditiile in care si sunt procese Poisson, produsul   reprezinta de asemenea un proces Poisson. Probabilitatea de realizare a produsului   este functie de x si y, cunoscuta sub numele de functie de distributie comuna de probabilitate a variabilelor aleatoare u si v, definita ca F _u v (x , y) = P(u   x ; v   y).

O proprietate remarcabila a acestei functii este aceea ca

P(x  < u   x  ; y  < v   y

= F(x  , y ) - F(x  , y ) - F(x  , y ) + F(x  , y

Pe baza inegalitatii (09.07.01) si in ipoteza ca F(x , y) are derivate partiale pana la ordinul 2 inclusiv, se defineste densitatea comuna de probabilitate f(x , y) ca fiind:

In cazul de fata u si v sunt variabile aleatoare discrete ce iau valori naturale cu probabilitatile:

Functiile de distributie asociate u, v sunt

iar densitatea de probabilitate este o secventa de impulsuri Dirac:

Ca urmare, functia de distributie comuna de probabilitate a variabilelor aleatoare u si v, tinand seama de independenta acestora, va fi:

iar densitatea comuna de probabilitate a variabilelor aleatoare u si v devine:

Densitatea comuna de probabilitate ca in intervalele ( T _n - 1 , T _n ] si ( T _n , T _n + 1 ] sa soseasca N _n , respectiv N_n + 1 pachete, este:

b)Se impune conditia ca in intervalele ( T_n - 1 , T_n ] si ( T_n , T_n + 1 ] sa nu soseasca nici un mesaj, deci N_n = 0 si N_n + 1 = 0. Ca urmare, probabilitatea de transfer corect a mesajului devine:

valoare ce coincide cu cea calculata in problemele anterioare:

c) Pachetul transmis de utilizatorul A intra in coliziune cu p alte pachete in conditiile in care in intervalul ( T _n - 1 , T _n ] se transmit i = N _n pachete, iar in ( T _n , T _n + 1 ] se transmit j = N _n + 1 pachete, cu i + j = p. Deci probabilitatea de coliziune cu p pachete este

si din nou se constata coincidenta cu valoarea calculata in problemele anterioare:

8. Tratarea algoritmului de acces multiplu P-Alloha in termenii densitatii comune de probabilitate.

Fie N = N _n + N _n + 1 unde N _n , N _n + 1 sunt marimile definite in problema 7. Sa se scrie expresia functiei densitate de probabilitate corespunzatoare marimii N si sa se dea o interpretare pentru aceasta functie.

Rezolvare.

Expresia densitatii de probabilitate a variabilei aleatoare N este, in mod similar cu ultimul punct al problemei precedente, data de suma densitatilor comune de probabilitate f ( i , j ) cu conditia i + j = N, cu i, j 

Se remarca faptul ca densitatea de probabilitate a lui N constituie probabilitatea

de aparitie a N mesaje in intervalul 2 τ .

La acelasi rezultat se ajunge folosindu-se teorema fundamentala a convolutiei:

'Daca x si y sunt variabile aleatoare independente, atunci densitatea de probabilitate a variabilei aleatoare z = x + y este egala cu convolutia respectivelor densitati de probabilitate:

Rezulta:

cu

Se obtine

Produsul de impulsuri Dirac de mai sus este nenul doar pentru z = k + i , k = j , deci, folosind proprietatea distributiei δ, rezulta

Se obtine expresia

care introdusa in formula de calcul a probabilitatii duce la

si se remarca faptul ca s-a obtinut acelasi rezultat cu cel prezentat in (09.08.01).

9. Suma a doua distributii Poisson.

Sa se demonstreze ca suma a doua procese Poisson cu ratele λ si λ  , este tot un proces Poisson cu rata λ = λ

Rezolvare.

Fie u si v doua variabile aleatoare distribuite Poisson si avand ratele λ si λ . Fie w o variabila aleatoare definita ca suma celor doua variabile anterioare w = u + v. Atunci, folosind teorema fundamentala a convolutiei, densitatea de probabilitate a lui w va fi

f _w = f _u A f _v

unde

Deci

Ca urmare probabilitatea ca variabila aleatoare w sa ia valoarea k este

Generalizarea rezultatului se poate demonstra prin inductie matematica sau folosind formula binomului lui Newton generalizat:

10. Tratarea algoritmului S-Alloha in termenii densitatii comune de probabilitate.

Se considera scenariul de sosire a pachetelor prezentat in figura 09.07.01 corespunzator unui algoritm P-Alloha. Localizarea momentelor de sosire a pachetelor este valabila in conditiile sistemului P-Alloha, dar nu si in cele ale sistemului S-Alloha, unde sosirile sunt permise numai la momente discrete de timp T _i , cu i I N. Se presupune ca rata totala a mesajelor transferate este λ _t

a) Cum se modifica figura 1 pentru a se prezenta scenariul de aparitie a mesajelor in cazul sistemului S - Alloha? Care sunt noile valori ale functiilor densitate de probabilitate pentru variabilele aleatoare N _n , N _n +1

b) Daca pachetul utilizatorului A soseste la momentul T _n , care este probabilitatea efectuarii unei transmisii corecte?

Rezolvare.

a) Avand in vedere faptul ca mesajele pot fi transmise doar la momente fixe de timp, iar la un astfel de moment pot sa apara mai multe mesaje, se redefineste semnificatia sagetilor verticale din scenariul dat in figura 1. Sagetile verticale au dimensiuni diferite, proportionale cu N _i - numarul mesajelor ce apar la momentul T _i. Scenariul de aparitie a mesajelor poate fi, in acest caz, schematizat ca in figura 1.

Probabilitatea ca la momentul T sa se transmita N mesaje este

Notand a = λτ, functia de distributie a probabilitatii este

iar densitatea de probabilitate este o suma de distributii δ:

b) Probabilitatea de transmisie corecta a mesajului utilizatorului A este

P (x = 0) = exp [ - λ τ ] .

11. Traficul total normat.

Un numar de M = 6000 statii utilizeaza in comun o resursa de comunicatie pe baza algoritmului de acces S - Alloha. In medie fiecare statie lanseaza 30 de cereri pe ora, fiecare pachet avind o durata τ = 500 μs. Sa se calculeze traficul util normat.

Rezolvare.

Se constata ca fiecare utilizator transmite

deci, pentru toti utilizatorii, traficul util normat este

12. Caracteristicile canalului de comunicatie partajat pe baza algoritmului S - Alloha.

Masuratorile efectuate asupra unui canal S - Alloha indica faptul ca p = 20 % din segmentele temporale (slot-uri) sunt ocupate. Se cere:

a) traficul util normat;

b) traficul total normat;

c) sa se verifice daca este vorba de un canal suprasolicitat.

Rezolvare.

a)     Probabilitatea ca o fereastra temporala in sistemul S - Alloha sa fie ocupat este

deci

unde λ _t reprezinta rata totala de aparitie a mesajelor, iar τ durata ferestrei temporale ocupata de un pachet.

Traficul total normat este

b)     Traficul util normat se determina din:

c) Intrucat ρ _max = 0,3679 se obtine pentru G _opt = 1 si G < G _opt = 1 se deduce ca sistemul S - Alloha este subsolicitat.

13. Caracteristicile canalului de comunicatie partajat pe baza algoritmului S - Alloha.

Un grup de M statii lucrand pe baza algoritmului S - Alloha genereaza un total de 120 cereri pe secunda, incluzand atat pachetele originale, cat si retransmisiile. Fiecare cerere ocupa o fereastra temporala de 12,5 ms. Se cere sa se determine:

a) traficul total normat pe canal;

b) probabilitatea de transfer corect a unui mesaj din prima incercare;

c) probabilitatea de coliziune cu alte 2 pachete inaintea transferului corect.

Rezolvare.

a) In conditiile in care λ_t = 120 pachete / s si τ = 12,5 ms, traficul total normat pe canal este G = λ _t

b)Probabilitatea de transfer corect a unui pachet din prima incercare este

c) Probabilitatea de coliziune cu 2 pachete inaintea transferului corect este

14. Relatia intre traficul util normat ρ si traficul total normat G.

Se considera un canal de comunicatie partajat pe baza algoritmului P - Alloha. Traficul util normat este ρ = 0,1 . Se cere determinarea traficului total normat G. Aceeasi problema pentru canalul de comunicatie partajat pe baza algoritmului S - Alloha.

Rezolvare.

Relatia existenta intre traficul util normat si cel total este ρ = G e ^- 2 G pentru canalul P - Alloha, respectiv ρ = G e ^- G pentru canalul S - Alloha.

Utilizand aceasta ecuatie, se pune problema determinarii traficului total normat, determinare ce nu poate fi facuta prin rezolvarea directa a ecuatiei. Se poate apela la metoda aproximarilor succesive sau la metoda iterativa. In cele ce urmeaza se foloseste metoda iterativa.

Asa cum se observa din figura 1, ecuatia transcendenta care trebuie rezolvata are in general doua solutii. Prima solutie, x  , se afla in domeniul ( 0 , G _max ) , cea de-a doua, x  , in domeniul ( G _max  ) . Exista si situatii in care ecuatia nu are decat o singura solutie si anume atunci cand a = 0 (solutia banala x = 0) si a = ρ_max (solutie x = G_max ). Ca urmare vor trebui gasite 2 siruri convergente catre una dintre cele doua solutii.

Pentru convergenta catre x se considera sirul  _n  de numere reale pozitive intre care exista relatia de recurenta

x _n + 1 = a exp [ b x _n ) n   0 , x

cu b = 1 , a I [ 0 , e pentru S - Alloha, respectiv

b = 2 , a I [ 0 , ( 2 e ) pentru P - Alloha.

Se remarca faptul ca s-a impus domeniul de existenta al parametrului a din conditia ρ I _max

Daca sirul  _n  este convergent, atunci limita sa, x, verifica ecuatia x = a e ^b x , deci x este solutie a ecuatiei generice intre traficul util normat si cel total a = x e ^- b x . Este utila determinarea conditiilor in care sirul  _n  converge.

In continuare se demonstreaza ca sirul  _n  este convergent.

. Valoarea marginii superioare a sirului  _n  se gaseste prin inductie matematica dupa n. Se arata ca

x _n  G _max = 1 / b , ( ) n 

si se tine cont de faptul ca

. Marginirea inferioara a sirului  _n  este evidenta intrucat x_n ) n 

. Monotonia sirului  _n  se demonstreaza prin inductie matematica dupa n, tinand cont de faptul ca x  = a > x  = 0 si

In conditiile in care x_n  x_n - 1 , evident exista si x_n + 1  x_n

Deci sirul  _n  dat de relatia (09.14.01) este convergent catre x  - traficul total normat G, in conditiile subsolicitarii canalului.

Cu aceste observatii se pot efectua calculele cerute:

1. Pentru canalul P - Alloha se scrie

x _n + 1 = ρ exp [ 2 x _n ) n   0 , x

si se obtin termenii

x x x

x x x

x x

Dupa n = 15 iteratii rezulta o valoare pentru traficul total normat cu o eroare sub 10

G = 0,129585551 .

2. Pentru canalul S - Alloha relatia de recurenta

x _n + 1 = ρ exp [ x _n ) n   0 , x

conduce la

x x

Dupa n = 10 iteratii rezulta

G = 0,111832559 .

Ramane de determinat solutia x corespunzatoare traficului total normat G in cazul canalului Alloha suprasolicitat. Pentru aceasta se foloseste sirul  _n  precizat prin relatia de recurenta:

Intrucat:

. sirul  _n  este monoton crescator - se demonstreaza prin inductie matematica dupa n tinand seama ca

. sirul  _n  este marginit inferior de x

. sirul  _n  este marginit superior daca

x  exp [ b x  a ,

ceea ce este evident;

atunci  _n  este convergent catre x

Se calculeaza:

Pentru canalul P - Alloha pe baza relatiei de recurenta

rezulta succesiv

x x x

x x x

si dupa n = 23 iteratii avem, cu o eroare de sub 10  , G = 1,271320678.

Pentru canalul S - Alloha relatia de recurenta

dupa n = 18 iteratii permite sa se determine G = 3,577152064.

15. Comparatie intre interogarea directa si dupa un arbore binar.

Pentru a identifica cererile de transmisie impunand o anumita ordine se poate folosi interogarea de catre un controller a terminalelor. Dintre procedeele cele mai cunoscute de interogare se mentioneaza:

- interogarea directa;

- cautarea dupa un arbore binar.

Se poate arata ca interogarea prin arbore binar reduce timpul de acces in cazul ca populatia de terminale este mare si nu exista prea multe cereri simultane.

Se considera un sistem format dintr-un satelit si o populatie de N = 8192 terminale. Dintre acestea un numar M = 560 solicita la un moment dat intrarea in comunicatie. Considerand ca timpul necesar unei interogari directe este τ = 1 ms, acelasi cu timpul necesar luarii unei decizii in cazul cautarii prin arborele binar, se cere:

a) sa se determine si sa se compare timpul necesar pentru aplicarea celor doua procedee pentru determinarea celor M statii care solicita intrarea in comunicatie;

b) sa se determine numarul maxim de terminale N` care pot fi gasite prin cautare binara in timpul necesar interogarii directe a intregii populatii de N terminale.

Rezolvare.

a) Timpul necesar interogarii directe a populatiei de N terminale este:

T = N τ = 8192 ms.

Cautarea binara necesita n = log N decizii pentru fiecare interogare a populatiei. Ca urmare, cautarea binara a M = 560 terminale care cer permisiunea de transfer necesita M = 560 treceri prin cadrul arborelui binar:

Se remarca faptul ca interogarea directa este prohibitiva ca timp atunci cand accesul este cerut de un numar M mic de statii.

c)     Notand cu N' - numarul maxim de statii care pot fi gasite in timpul T necesar unei interogari directe complete a populatiei, din conditia

rezulta

de unde, in cazul de fata N' = 630. Deci, daca numarul M al statiilor care cer accesul este sub N' (M   N' ) se recomanda cautarea binara, altfel este preferabila interogarea directa.

16. Tehnica de acces multiplu cu diviziune in frecventa (FDMA).

Sa se proiecteze un sistem de multiplexare a semnalelor cu diviziune in frecventa (FDMA) destinat prelucrarii unui numar de 5 canale vocale, fiecare avand spectrul situat in domeniul 300 - 3400 Hz. Semnalul multiplex ocupa domeniul spectral 30 50 kHz, iar semnalele individuale sunt preluate sub forma unei benzi laterale inversate.

Se cere determinarea spectrului semnalului de iesire (precizandu-se spectrele individuale ale fiecarui canal si largimea benzii de garda alocata) si schema bloc a multiplexorului (indicandu-se si detaliile legate de filtre si valorile oscilatoarelor locale).

Rezolvare.

In figura 09.16.01 este prezentata schema de principiu utilizata pentru multiplexarea celor n = 5 canale. S-au utilizat urmatoarele notatii:

S (ω) - spectrul semnalului vocal in banda de baza [ f _m m , f _m M ] cu f _m m = 300 Hz, f _m M = 3400 Hz;

f _h k - frecventa semnalului sinusoidal generata de oscilatorul local k (cu k = 1  5), semnal aplicat modulatorului k;

FTB _k - filtrul trece banda k (cu k = 1  5) caracterizat prin frecventa centrala f _c k si banda B _k 

S' (ω) - spectrul semnalului rezultat la iesirea modulatorului k; spectrul este nenul pentru:

f I [ f _h k - f _m M ; f _h k - f _m m  [ f _h k + f _m m ; f _h k + f _m M

S _k - spectrul semnalului rezultat la iesirea FTB _k; spectrul este nenul pentru

f I [ f _h k - f _m M ; f _h k - f _m m

S _MUX - spectrul semnalului multiplex rezultat.

Filtrul FTB _k este destinat rejectiei benzii laterale superioare a semnalului BLD-PS rezultat in urma modularii. De mentionat ca s-a optat pentru mentinerea benzii laterale inferioare din considerente ce tin de construirea filtrului trece banda (este necesar un factor de calitate mai mic), consideratiile ce tin de stabilitatea montajului fiind nesemnificative in cazul gamei de fata. Filtrul trece-banda FTB _k va avea frecventa centrala data de:

iar banda va fi aceeasi indiferent de indicele k:

De asemenea se remarca faptul ca spectrul semnalului multiplex rezultat S _MUX (ω) este nenul pentru

Avand in vedere structura spectrului semnalului multiplex, trebuie impuse conditiile de nesuprapunere a benzilor si, mai mult, ca ecartul dintre doua benzi sa fie acelasi. Deci:

f _h k - f _m m < f _{h , k + 1} - f _m M ) k = 1 n - 1 ,

si, mai mult,

( f _h k + 1 - f _m M ) - ( f _h k - f_m m ) = f _B ) k = 1 n - 1 ,

deci

f _h k + 1 - f _h k = ( f _m M - f _m m ) + f _B ) k = 1 n - 1 ,

unde cu f _B am notat ecartul intre 2 benzi laterale (largimea benzii de garda alocata). Ca urmare, frecventele oscilatoarelor locale vor fi in progresie aritmetica:

f _h k = f _h 1 + ( k - 1 ) ( f _B + f _m M - f _m m ) k = 1 n - 1 .

Alegerea frecventelor f _h k se poate face in doua moduri:

1. impunand conditia de maximizare a ecartului intre 2 benzi laterale f _B

2. plecand de la premiza ca cele n = 5 canale vocale sunt inglobate in cadrul unui sistem complex de multiplexare in frecventa, sistem ce include grupuri primare, secundare, tertiare etc. In cadrul unui astfel de sistem, unui canal vocal ii este alocat un domeniu spectral de 4 kHz, singura cerinta care se impune relativ la localizarea spectrului semnalului vocal fiind aceea ca toate canalele vocale vor fi mixate astfel incat ocuparea benzii alocate de 4 kHz sa fie facuta in mod similar.

Cazul 1.

Pentru maximizarea ecartului f _B impunem urmatoarele conditii:

f _h 1  - f _m M =  f _S m ,  cu f _S m = 30 kHz ,

deci limita inferioara a benzii primului canal mixat se situeaza la limita inferioara a domeniului spectral 30 50 kHz;

f _h 5  - f _m m =  f _S M ,  cu f _S m = 50 kHz ,

deci limita superioara a benzii ultimului canal mixat se situeaza la limita superioara a domeniului spectral 30 50 kHz.

Ca urmare:

f _S M  - f _S m =   ( n - 1) f _B + n ( f _m M - f _m m

(in domeniul spectral 30 50 kHz avem n semnale vocale si n - 1 benzi de garda, fiecare de lungime f _B ), deci largimea benzii de garda este

Cu aceasta rezulta cele 5 frecvente purtatoare:

f _h 1  =  f _S m + f_m M = 30 kHz + 3,4 kHz = 33,4 kHz ;

f _h 2  =  f _h 1  + ( f _B  + f_m M - f_m m ) = 33,4 kHz + 4,225 kHz = 37,625 kHz ;

f _h 3  =  f _h 2  + ( f _B  + f_m M - f_m m ) = 37,625 kHz + 4,225 kHz = 41,850 kHz ;

f _h 4  =  f _h 3  + ( f _B  + f_m M - f_m m ) = 41,850 kHz + 4,225 kHz = 46,075 kHz ;

f _h 5  =  f _h 4  + ( f _B  + f_m M - f_m m

= 46,075 kHz + 4,225 kHz = 50,3 kHz ;

si se remarca faptul ca este indeplinita si conditia (09.06.11).

Frecventele centrale f _c k ale filtrelor FTB _k sunt date de:

deci:

f _c 1  =  31,7 kHz ;  f _c 2  =  35,925 kHz ;

f _c 3  =  40,150 kHz ;  f _c 4  =  44,375 kHz ;

f _c 5  =  48,600 kHz . 

Cazul 2.

In acest caz largimea benzii de garda este

Pentru a realiza simplu grupul primar de multiplexare, se opteaza pentru repartizarea benzii de garda astfel incat valorile f _h k sa fie numere intregi. Deci se impune o rezerva la stanga egala cu:

si la dreapta

f _B 2 = f _m m = 0,3 kHz .

Ca urmare, primul canal vocal va fi transferat in zona 30,6 33,7 kHz folosind frecventa purtatoare f _h 1  =  34 kHz; celelalte frecvente purtatoare sunt:

f _h 2  =  f _h 1  + ( f _B  + f _m M - f_m m ) = f _h 1 + 4 kHz = 38 kHz ;

f _h 3  =  f _h 2  + ( f _B  + f _m M - f_m m ) = f _h 2 + 4 kHz = 42 kHz ;

f _h 4  =  f _h 3  + ( f _B  + f _m M - f_m m ) = f _h 3 + 4 kHz = 46 kHz ;

f _h 5  =  f _h 4  + ( f _B  + f _m M - f_m m ) = f _h 4 + 4 kHz = 50 kHz . 

Frecventele centrale f _c k ale filtrelor FTB _k sunt date de:

f _c 1  =  32,3 kHz ;  f _c 2  =  36,3 kHz ;

f _c 3  =  40,3 kHz ;  f _c 4  =  44,3 kHz ;

f _c 5  =  48,3 kHz . 

Observatie:

Mixarea conform valorilor calculate in cazul 1 conduce la o marire relativ nesemnificativa a largimii de banda de garda in comparatie cu adoptarea valorilor rezultate in cel de-al doilea caz.

Alegerea variantei 2 de implementare are ca avantaje:

- utilizarea unor valori rezonabile pentru f _h k ceea ce permite sinteza mai simpla a acestora prin utilizarea unui singur oscilator cu cristal cu cuartz si a unor bucle PLL;

- mentinerea ecartului f _B 1 la marginea inferioara ( f _S m ) si f _B 2 la marginea superioara ( f _S M ) a domeniului spectral, ceea ce permite ca un astfel de montaj sa fie inglobat in cadrul unui sistem complex de multiplexare in frecventa de tipul celui schitat in figura 3.

17. Intarzierea medie a pachetelor de date transferate prin tehnicile TDMA sau FDMA.

Definind intarzierea medie a unui pachet prin

t _D = t _W + t _T

unde t _W este durata medie de asteptare a unui mesaj (asteptare anterioara transmisiei), iar t _T durata de transmisie a pachetului, sa se demonstreze ca tehnica TDMA este superioara tehnicii FDMA considerand o retea formata din N = 30 statii ce transmit pachete formate din b = 1350 biti. Rata de transfer maxima a canalului este aceeasi in ambele cazuri, R = R _TDMA = R _FDMA = 50 kbiti /s. Se va considera ca posibilitatile canalului de comunicatie sunt folosite in proportie de 100 % , adica nu exista benzi sau intervale de garda sau transmisiuni auxiliare. De asemenea, se presupune ca pachetele ce urmeaza a fi transmise in intervalul k sunt disponibile la inceputul intervalului pentru toate statiile. Sa se discute raportul dintre cele doua intarzieri medii.

Rezolvare.

. Tehnica FDMA.

In acest caz, la o proiectare corecta, canalul alocat unei statii asigura transmiterea pachetului in perioada T si este disponibil la inceputul urmatorului interval pentru a prelua un nou pachet. Deci nu exista timp de asteptare:

t _W FDMA

Datele sunt disponibile la destinatie odata cu receptia ultimului bit; deci intarzierea datorata transmisiei este

t _T FDMA = T .

Din expresiile (09.17.01) si (09.17.02) rezulta

. Tehnica TDMA.

In acest caz, pachetul provenit de la sursa m nu va fi transmis in segmentul temporal m din perioada T. Durata de a_teptare este

interval care variaz_ de la 0 (pentru m = 1) la (N - 1) T / N (pentru m = N). Durata medie de a_teptare t _W TDMA este:

(09.17.05)

Pentru TDMA fiecare pachet este transferat pe durata a T / N secunde, deci

t _T FDMA = T / M = b / R ,  (09.17.06)

datorit_ faptului c_, dac_ pentru FDMA banda alocat_ este divizat_ in N subbenzi ortogonale, in cazul TDMA secven_a de date este divizat_ in N durate ortogonale. Din expresiile (09.17.05) _i (09.17.06) rezult_

Ca urmare

_i, in concluzie, se remarc_ superioritatea tehnicii TDMA relativ la FDMA din punct de vedere al intarzierii medii a mesajelor. Raportul intre t _T FDMA _i t _T TDMA este:

Se remarc_ faptul c_ raportul ia valori intre 1 (pentru N = 1) _i 2 (pentru N  ), fiind strict descresc_tor relativ la N. Deci, pe m_sur_ ce num_rul de surse de semnal cre_te, raportul intarzierilor medii tinde spre 2.

18. Eficien_a utiliz_rii resurselor de comunica_ie.

Un sistem TDMA opereaz_ cu o rat_ de transfer R = 100 Mbi_i / s , fiecare cadru avand o durat_ T = 2 ms; intre dou_ secven_e exist_ un interval de gard_ de T  = 1 μs. Se cere:

a) s_ se calculeze eficien_a comunica_iei pentru situa_iile in care o secven__ este constituit_ din 1 cadru, respectiv 2, 5, 10, 20, 50, 100 cadre;

b) s_ se recalculeze eficien_a comunica_iei in condi_iile in care la inceputul fiec_rei secven_e este necesar un preambul de b = 100 bi_i;

c) s_ se reprezinte grafic rezultatele ob_inute la punctele a) _i b).

Indica_ie:

Eficien_a utiliz_rii resurselor de comunica_ie η _CR se calculeaz_ ca fiind raportul intre informa_ia util_ transmis_ relativ la informa_ia total_ transmis_.

Rezolvare.

a) Fie N - num_rul de cadre ce constituie o secven__. Atunci eficien_a utiliz_rii canalului este:

Cu aceast_ rela_ie se ob_in, succesiv, valorile: 0,9995 , 0,99975 , 0,9999 , 0,99995 , 0,999975 , 0,99999 , 0,999995 .

b) In condi_iile in care la inceputul fiec_rei secven_e este necesar un preambul de b = 100 bi_i, eficien_a utiliz_rii resursei devine:

unde b / R este durata necesar_ preambulului. Se ob_in astfel, succesiv, valorile: 0,999 , 0,9995 , 0,99975 , 0,9999 , 0,99995 , 0,999975 , 0,99999 .

c) Se remarc_ faptul c_:

deci utilizandu‑se aproximarea

rezult_

(09.18.05)

Pentru a reprezenta η _{CR k  CR k} (N) s-a ales scal_ logaritmic_ pe axa Ox.

Deci cre_terea num_rului de cadre intr-o secven__ nu duce la imbun_t__irea remarcabil_ a eficien_ei utiliz_rii resursei. De asemenea nici includerea unui preambul de sincronizare nu conduce la inr_ut__irea sensibil_ a eficien_ei utiliz_rii resursei.

20. Sateli_i cu fascicule multiple _i comutarea TDMA a satelitului.

Pentru un satelit destinat comunica_iei intre 2 grupuri de sta_ii la sol, sta_ii emi__toare, respectiv receptoare, o modalitate de func_ionare eficient_ const_ in interconectarea ciclic_ a sta_iilor pentru transmiterea TDMA a datelor.

Interconectarea sta_iilor emi__toare _i receptoare deservite de unii sateli_i de comunica_ie se face prin intermediul unei matrici de comutare in microunde localizate pe satelit _i programat_ de la sol. Matricea descrie interconexiunile stabilite _i duratele acestora, nefiind fix_, ea reconfigurandu-se dinamic in ideea optimiz_rii utiliz_rii resurselor _i servirii eficiente a utilizatorilor.

Matricea de trafic

Se folosesc nota_iile:

N - num_rul sta_iilor emi__toare, evident egal cu num_rul sta_iilor receptoare;

t _ij - volumul traficului de la emi__torul i c_tre receptorul j;

- volumul traficului provenit de la emi__torul i:

- volumul traficului c_tre receptorul j:

Cand traficul in cadrul sistemului SS - TDMA este controlat de un comutator neblocabil (care permite transmisia tuturor mesajelor, f_r_ semnaliz_ri 'busy'), va fi asignat_ fiec_rui canal o secven__. Pentru o utilizare eficient_ a canalului, traficul total trebuie transmis in decursul unui cadru T care va trebui minimizat. Valoarea minim_ a duratei unui cadru in ideea asigur_rii unei conectivit__i f_r_ st_ri de blocare poate fi exprimat_ prin:

Rela_ia (09.19.03) permite evaluarea valorii duratei minime necesare transferului in totalitate a traficului din matricea de trafic, in condi_iile aceleia_i l_rgimi de band_ alocate fiec_rui canal.

Se cere:

a) s_ se analizeze eficien_a utiliz_rii resursei de comunica_ie, η _CR , in condi_iile in care to_i parametrii S _i _i R _j sunt egali.

b) s_ se analizeze cazul in care cateva valori S_i sau R_j sunt mult mai mari decat celelalte.

Rezolvare.

a) Eficien_a utiliz_rii resursei de comunica_ie, η _CR , se calculeaz_ ca raportul intre informa_ia util_ transmis_ relativ la informa_ia total_ transmis_. Intr-o prim_ faz_, pentru simplificare, se consider_ c_ pachetele nu sunt transmise cu preambul de sincronizare, iar intre pachete nu exist_ intervale de gard_.

Ca urmare, durata necesar_ transferului informa_iei utile este

Totodat_, durata necesar_ transferului informa_iei este T_n = N T_min , deci eficien_a utiliz_rii canalului va fi:

In condi_iile in care S _i = R _j = T _min ) i , j = 1  N , se ob_ine η _CR = 1. Considerand c_ preambulul con_ine b = 6 bi_i, in condi_iile in care rata de transfer pe canal este R, durata necesar_ transmiterii prembulului este b / R. Se ia in considerare _i o durat_ de gard_ egal_ cu T . In aceste condi_ii valoarea minim_ a duratei unui cadru devine:

iar eficien_a utiliz_rii canalului:

unde cu S s-a notat valoarea comun_ a parametrilor S _i _i R _j, cu i , j = 1  N.

b) Se presupune c_ in sistemul analizat traficul dintre 2 sta_ii este predominant:

S _m >> S _i ) i I 1  N , i   m ;

R _n >> R _j ) j I 1  N , j   n ;

S _m _ R _n (09.19.08)

In aceste condi_ii, neglijand preambulul _i intervalul de gard_, rezult_

iar eficien_a utiliz_rii canalului devine

_i se remarc_ sc_derea dramatic_ a eficien_ei η _CR . Rezultate similare se ob_in _i in condi_iile in care nu se neglijeaz_ duratele de gard_ _i cele alocate transmisiei preambulului.

20. Sateli_i cu fascicule multiple _i comutarea TDMA a satelitului.

In condi_iile problemei 19, s_ se propun_ o modalitate de imbun_t__ire a eficien_ei utiliz_rii resursei de comunica_ie.

Pentru imbun_t__irea eficien_ei η _CR a canalului trebuie ajustat_ durata unui cadru:

Pentru aceasta se poate propune un sistem de transfer a datelor similar cu algoritmul Reservation - Alloha:

1. Durata unei secven_e este divizat_ in M + 1 cadre.

2. Primele M cadre sunt utilizate pentru transferul de mesaje.

3. Ultimul cadru este divizat in subcadre in care se pot face cererile de rezervare.

4. Sta_iile transmit mesaje doar in por_iunea asignat_ din cele M cadre.

In esen__, pentru M >> N, se poate asigna unei sta_ii la sol un num_r K _S cadre pentru emisie, respectiv K _R cadre pentru recep_ie, care s_ indeplineasc_ rela_iile de aproximare a timpului necesar deservirii fiec_rei sta_ii:

( K _S - i - 1 ) T  < S _i  K _S - i T ) i = 1  N , (09.20.02)

respectiv

( K _R - j - 1 ) T  < R _j  K _R - j T ) j = 1  N , (09.20.03)

unde cu T s-a notat durata unui cadru. Indicii K _S - i _i K _R - j indeplinesc condi_ia ca traficul celor N sta_ii s_ se incadreze in durata unei secven_e.

deci

Se calculeaz_ eficien_a utiliz_rii canalului:

_i, folosind rela_iile de calcul ale coeficien_ilor K _S - i _i K _R - j , (09.20.02) _i (09.20.03), se ob_ine:

(09.20.07)

_i

(09.20.08)

_i similar pentru R_j. Deci

Ca urmare, pentru o utilizare cat mai eficient_ a canalului se recomand_ M >> N, _i in aceste condi_ii eficien_a utiliz_rii tinde spre maxim.

21. Lungimea minim_ a unei re_ele locale 'inel cu jeton'.

In cadrul unei re_ele in inel (engl. 'token-ring') este definit_ o structur_ de N bi_i denumit_ 'jeton' (engl. 'token') (de exemplu '11111111') care circul_ in permanen__ in re_ea atunci cand sta_iile nu sunt active. Pentru ca mesajele de date s_ nu con_in_ aceast_ structur_, sistemul utilizeaz_ tehnica 'bit stuffing' (algoritmul insereaz_ un bit '0' in _irul de date dup_ fiecare secven__ de N-1 bi_i '1' consecutivi; la recep_ie se utilizeaz_ un algoritm similar pentru refacerea secven_ei originale). Re_eaua in inel trebuie s_ asigure ins_ o intirziere suficient_ pentru a permite jetonului s_ circule atunci cand toate sta_iile nu sunt active.

O m_rime major_ in proiectarea unei re_ele in inel este distan_a de propagare sau 'lungimea' unui bit. Dac_ rata datelor este R Mbi_i / s, atunci se emite un bit la fiecare R  μs.

In condi_iile in care viteza de propagare este v_P = 200 m / μs, rata R = 5 Mbi_i / s, jetonul are N = 8 bi_i, s_ se determine lungimea minim_ necesar_ a inelului.

Rezolvare.

Timpul necesar emisiei unui bit este t _b = R  , iar pentru emisia celor N bi_i din _irul de bi_i speciali ai jetonului este necesar_ o durat_

t _t = N t _b = N R (09.21.01)

Distan_a de propagare necesar_ este:

22. Caracteristicile re_elelor locale in inel cu jeton ('token-ring').

Se consider_ o re_ea 'token-ring' operand la o rat_ de transfer a datelor R = 10 Mbi_i / s _i la o vitez_ de propagare v_P = 200 m / μs. Se cere:

a) s_ se calculeze lungimea cablului echivalent_ cu intirzierea de un bit care este introdus_ de fiecare interfa__ de re_ea;

b) dac_ jetonul are N = 10 bi_i _i in decursul nop_ii se inchid toate sta_iile cu excep_ia a M = 3 dintre ele, care este lungimea minim_ a cablului.

Rezolvare.

a) Timpul necesar emisiei unui bit este t _b = R  , deci lungimea cablului echivalent_ cu intarzierea de 1 bit ce are loc la interfa_a de re_ea este

d _b = t _b v _p = v _p R  = 20 m .  (09.22.01)

b) Lungimea cablului necesar_ in condi_iile in care toate sta_iile ar fi inchise este, conform problemei anterioare:

avand in vedere c_ un num_r de M = 3 sta_ii func_ioneaz_, interfe_ele corespunz_toare vor introduce un defazaj corespunz_tor de M bi_i, echivalent_ cu o lungime de M d _b . Ca urmare lungimea minim_ a re_elei va fi: