1

Universitatea “Politehnica” din Bucureşti

Facultatea de Electronică, Telecomunicaţii şi Tehnologia Informaţiei

Proiect Reţele de Calculatoare

Retele Mobile Ad Hoc multi-hop

Profesor coordonator Masterand

Conf. Dr. Ing. Ştefan STĂNCESCU Manole-Ştefan NICULESCU

2012

2

Cuprins

Capitolul 1. Introducere ..................................................................................................... 3

Capitolul 2. Retele fara fir bazate pe infrastructura si Ad Hoc ....................................... 4

Capitolul 3. Sisteme de Control ale Retelei ..................................................................... 7

3.1. Intarzierile intr-un Sistem de Control al Retelei ..................................................................... 8

3.1.1.Intarzierea totala ............................................................................................................. 8

3.1.2. Intarzierea introdusa de retea ........................................................................................ 8

3.2. Stabilitatea sistemului NCS .................................................................................................. 8

3.3. Algoritmul de intarziere specific MANET ............................................................................... 9

Capitolul 4. Teoria teletraficului cu coada de asteptare ............................................... 10

4.1. Adaptarea procesului Poisson la retelele MANET multi-hop ............................................... 11

4.2. Intarzierea medie din coada ............................................................................................... 12

4.3. Intarzierea medie de conexiune .......................................................................................... 13

Capitolul 5. Simularea modelului MANET multi-hop ..................................................... 13

5.1. Simularea modelului Poisson cu un singur proces .............................................................. 13

5.2. Simularea modelului Poisson cu 3 procese concurente ...................................................... 16

5.3. Simularea unui model multi-nod ......................................................................................... 19

Concluzii ........................................................................................................................... 22

Bibliografie ....................................................................................................................... 23

3

Capitolul 1. Introducere

O retea mobila ad-hoc (MANET) este o infrastructura de retea de dispozitive mobile conectate intre ele folosind tehnologie fara fir care se auto-organizeaza. Termenul de ad-hoc se refera la faptul ca reteaua se creeaza pentru un anume scop. [1] Fiecare dispozitiv din reteaua MANET poate fi deplasat in orice directie de catre utilizator si astfel, va insemna ca acesta isi va schimba des conexiunea cu celelalte dispozitive. Fiecare dintre dispozitive trebuie sa directioneze traficul care nu ii este destinat si inseamna ca echipamentul conectat la retea va indeplini si functia de router. Principala provocare in proiectarea unei retele MANET o reprezinta echiparea fiecarui dispozitiv cu o functie speciala care este necesara pentru a directiona traficul. Astfel de retele pot opera independent sau pot fi conectate pe scara larga la internet. Motivele care au determinat implementarea acestui tip de retea l-a constat in primul rand numarul de echipamente care au fost introduse pe piata de consum electronic. Cresterea numarului de calculatoare mobile si standardul de retea fara fir 802.11/Wi-Fi au facut ca problema cercetarii in ceea ce priveste reteua MANET sa existe de la inceputul anilor 1990. Numeroase documente academice evalueaza protocoalele si performantele lor, constand in varierea unghiului de mobilitate intr-un anumit spatiu delimitat, in general cu toate nodurile la distanta de cateva hopuri unele de celelalte. Diferite protocoale sunt evaluate folosind metode de masurare, cum ar fi rata de pierdere a pachetelor, suprasarcina introdusa de protocolul de rutare folosit, intarzierea pachetelor de la un nod initial si unul terminal, debitul retelei, etc. Revenind la definitia de baza, retelele MANET sunt entitati care se auto-organizeaza. Pornind de la aceasta premisa, a fost nevoie de introducerea unui sistem care sa realizeze aceasta functie si care sa controleze starea retelei in orice moment al ei si sa realizeze conexiunea in mod sigur si eficient pentru un bun trafic de date. Sistemul care se auto-organizeaza trebuie sa contina niste traductoare ce acumuleaza informatie din lumea exterioara, dupa care le prelucreaza si, dupa aceea retransmite informatia prelucrata mediului. Aceasta arhitectura de sistem a pus bazele proiectarii unui sistem de control si pentru retelele MANET. Sistemul rezultat se numeste NCS (Networked Control System) [2] si este un sistem cu bucla inchisa in care traductorii schimba date cu controlerul de comunicatie la intervale de timp regulate (Yang T 2005) intr-un mediu de comunicatie in timp real. Aceste intervale sunt cunoscute sub numele de perioade de esantionare a traductorilor ( ). Traductorii trimit starea curenta controlerului, care compara starea lor cu

un model de referinta si dupa aceea controlerul retransmite traductorilor informatia actualizata la fiecare moment . Aplicand un sistem de control mecanismului de

comunicatie se imbunatateste flexibilitatea si puterea intregului sistem de comunicatie. Retelele mobile ad-hoc sunt retele fara fir care nu se bazeaza pe o infrastructura fixa care sa le asigure utilizatorilor comunicarea printr-o retea fizica. Astfel, fiecare nod are drept sarcina rutarea si redirectionarea pachetelor, furnizand comunicatie de-a lungul retelei. In general, NCS-ul se bazeaza pe o retea cu fir care permite comunicarea dintre traductori si controler. Aceasta retea este bazata pe sisteme sincronizate si temporizate necesitand retele de comunicatie care garanteaza transmiterea semnalelor de control ale actuatoarelor, senzorilor si a altor dispozitive, cu o rata fixa de intarziere (Murray, 2003). Cercetarile recente au condus la investigarea infrastructurii MANET cu ajutorul sistemului NCS. Folosind mediul de comunicatie al MANET-ului in timp real au aparut o gramada de probleme. Din moment ce echipamentele sunt dinamice, au o retea proprie ce le contin si este alcatuita dintr-un numar de noduri fara fir, trebuie sa existe niste

4

protocoale care sa guverneze comunicarea pe retea. Aceste protocoale au suprasarcina proprie si permit echipamentelor sa directioneze pachete si in acelasi timp sa mentina o tabela de rutare pentru noduri. Protocolul NSC schimba un numar mare de pachete de dimensiune redusa intre traductor si controler, iar fiecare pachet fie contine starea traductorului, fie contine informatie actualizata de la controler. Exista totusi conditia ca fiecare pachet sa ajunga la destinatie cu cea mai mica intarziere posibila. Cu cat aceasta este mai mare, posibilitatea ca traductorul sa devina instabil este mai ridicata sau se produc rezultate nedorite. Retelele MANET introduc intarzieri suplimentare specifice protocoalelor de rutare, rate de pierdere a pachetelor specifice mediului fara fir si instabilitate a semnalului. Toate acestea pot influenta starea sitemului NCS (Walsh 2000).

Capitolul 2. Retele fara fir bazate pe infrastructura si Ad Hoc

Comunicatia intre retele fara fir bazate pe infrastructura are loc intre nodul wireless si punctul de acces, nu intre noduri direct conectate intre ele. O astfel de situatie este ilustrata in figura 1.

Punctele de acces permit comunicarii sa se efectueze intre echipamentele wireless si reteaua cu fir, aceastea fiind niste cai de conexiune intre diferite retele. Figura 1 ilustreaza o retea cu fir backbone proiectata pentru a stabili conexiunea intre echipamentele mobile si serverele de mail, internet si printare. Acele trei puncte de acces furnizeaza echipamentelor fara fir o cale catre serviciile disponibile retelei cu fir. Punctul de acces suporta diferite metode de criptare si ajuta la securizarea retelei. Orice punct de acces deschis (fara parola) poate periclita atat siguranta retelei ethernet cat si a echipamentelor conectate la punctul de acces respectiv.

Fig. 1 – Structura unei retele fara fir bazate pe infrastructura

5

Proiectarea unei retele bazate pe infrastructura este in general mai simpla decat a unei retele ad-hoc deorece functionalitatea se bazeaza pe existenta unor puncte intermediare de acces. Aceasta structura este similara cu cea a unei retele ethernet conectata prin switch-uri sau a oricarei retele stea in care elementul central (cum ar fi un switch) controleaza fluxul de date al retelei [3]. Retelele bazate pe infrastrucura pierd o parte din flexibilitatea retelelor fara fir, ceea ce inseamna ca ele nu pot sa stabileasca niste conexiuni atunci cand infrastructura nu este disponibila. De asemenea, datorita problemei de adresare este foarte dificil ca un echipament fara fir sa paraseasca un punct de acces si sa se conecteze la altul in timpul in care acesta transmite sau receptioneaza date. O retea fara fir trebuie sa aiba aceleasi cerinte la fel ca o retea cu fir tipica LAN. Cele mai importante cerinte ale unei retele LAN fara fir sunt:

1. Capacitatea – protocolul de control al mediului de acces imbunatateste eficient utilizarea mediului fara fir, marind capacitatea acestuia.

2. Numarul de noduri – o retea LAN fara fir trebuie sa suporte sute de noduri de-a lungul unor celule multiple.

3. Conectarea la magistrala (backbone) LAN – necesitatea existentei suportului de interconexiune a retelei cu fir si a statiilor wireless.

4. Aria de acoperire – acoperirea unei arii radiale de aproximativ 100-300m, 5. Consumul de energie – echipamentele mobile sunt conditionate de un

acumulator ce limiteaza utilizarea acestuia pe o durata finita si de aceea trebuie sa existe niste protocoale ce maximizeaza durata de viata a bateriei in mod eficient.

Retelele MANET sunt retele care nu sunt limitate de necesitatea unei infrastructuri, exact ca in cazul prezentat anterior si sunt alcatuite din noduri care comunica prin legaturi fara fir fara ajutorul unui element central de control. Structura unei astfel de retele este prezentata in figura 2.

MANET mostenesc problemele traditionale ale comunicatiilor fara fir bazate pe infrastructura, cum ar fi controlul energiei consumate, optimizarea benzii si calitatea transmisiunii. Pe langa acestea se mai insumeaza si probleme specifice, precum stabilirea rutelor, descoperirea rutelor si adresarea. Acestea necesita o solutie de rutare care sa fie capabila sa faca fata unor retele de mari dimensiuni care sa aiba conectivitate dinamic schimbabila si o colaborare ridicata intre noduri.

Fig. 2 – Structura unei retele fara fir MANET

6

Cu cat numarul de noduri ale retelei MANET este mai numeros, cu atat mai mare devine intarzierea pe parcursul rutarii, transmisiei de date si a mentinerii rutelor. La fel de bine, un volum mare de date trebuie sa poata fi suportat de tabele, iar nodurile trebuie sa tina evidenta rutelor si a intregii topologii de retea. MANET trebuie sa indeplineasca cerinte similare cu cele care se gasesc la WLAN-uri, printre care:

1. Capacitatea – utilizarea protocoalelor bazate pe MAC ce imbunatatesc efectiv capacitatea mediului de transmisiune wireless.

2. Rutarea – folosirea unor protocoale potrivite pentru a guverna rutarea de-a lungul retelei intr-o maniera eficienta.

3. Numarul de noduri – abilitatea de a permite informatiei sa fie rutata in jurul unui numar mare de noduri de-a lungul unor retele multiple.

4. Consumul de baterie – obtinerea unui consum bun pentru o baterie cu durata de viata finita.

5. Aria de acoperire – capacitatea de a acoperi o arie mare fara a avea impact asupra celorlalte domenii de utilizare radio si nici asupra consumului de energie. Acoperirea trebuie sa fie de aproximativ 100-150m radial.

Calitatea serviciului (QoS) defineste caracteristicile non-functionale ale sistemului care afecteaza calitatea perceputa a rezultatului. Intr-o retea cu fir, aceste caracteristici sunt: largimea de banda garantata, procesarea speciala a anumitor tipuri de pachete si garantarea rutelor intre nodurile retelei.

Calitatea serviciului pe o retea MANET este mult mai dificil de implementat decat cel intr-o retea traditionala deoarece topologia retelei este dinamica, iar semnificatia expresiei „garantarea rutelor” capata un alt inteles. Acest lucru inseamna ca QoS-ul trebuie sa garanteze existenta rutelor intre noduri, chiar daca echipamentul va deveni mobil, si in aceste conditii, largimea de banda va fi astfel greu de prezis si de mentinut.

Intr-o retea MANET, garantarea nu se va face doar pentru o transmisiune de tipul salt-simplu (hop), ci si pentru transmisiuni concurente de tipul salt-multiplu (multi-hop).

Dupa cum s-a discutat mai sus, QoS-ul, in cazul retelelor wireless este mult mai dificil de implementat decat in cazul retelelor fixe si de telefonie mobila datorita naturii dinamice a retelei care face ca informatia de stare sa fie mai putin precisa. Daca aceasta informatie de stare se schimba prea repede, atunci este posibil ca serviciile QoS sa nu poata fi asigurate. Acest lucru conduce la implementarea unui QoS soft care lucreaza in perioada cand QoS-ul cerut nu poate transmite din cauza unor legaturi intrerupte sau a partitionarii retelei.

Cercetarea in acest domeniu s-a extins considerabil, alocandu-se foarte mult tip si foarte multe resurse materiale. Lucrarile au fost conduse de catre Chen, care a propus o schema de rutare distribuita care selecteaza calea cu resursele suficiente care satisfac conditiile unei intarzieri acceptabile sau a unei benzi de latime suficienta disponibila in mediul dinamic multi-hop.

Nodurile din MANET au toate o caracteristica ce este comuna: toate sunt noduri mobile care se folosesc de o sursa de alimentare cu energie finita. Atunci cand bateria este incarcata la maxim este posibil ca datele sa se poata transmite la distanta maxima, iar in cazul in care nivelul bateriei scade, domeniul de acoperire in care se poate transmite informatie este restrans.

Reducand puterea de transmisie si domeniul in care se transmite, durata de viata a bateriei echipamentului wireless poate fi imbunatita. Efectul reducerii razei de transmitere creste posibilitatea de cadere a retelei si de asemenea, daca se mareste numarul de hopuri, aria de acoperire este redusa si se schimba topologia retelei.

Protocoalele de rutare au propriile lor probleme in ceea ce priveste consumul de energie. Cu cat latimea benzii si suprasarcina de semnalizare se mareste datorita actualizarilor de ruta, cu atat mai multa energie este necesara pentru a face fata

7

numeroaselor tranzactii. Astfel, echipamentele mobile trebuie sa-si cunoasca limitele din punct de vedere energetic si sa aiba abilitatea de a ajusta setarile protocoalelor, a puterii de transmisie pentru a scadea cantitatea de energie consumata specifica fiecarui dispozitiv.

Capitolul 3. Sisteme de Control ale Retelei

Sistemul de Control al Retelei (NCS) este definit drept un sistem de control in bucla

inchisa care foloseste o retea de comunicatie in timp real care permite informatiei sa se

transmita de la Agent la Controler. Agentul este o grupare de traductori (senzori si

actuatori) care au rolul de a realiza interfata controlerului cu mediul de transmisiune. O

schema bloc tipica sistemului NCS este ilustrata in figura 3.

Senzorul detecteaza starea curenta a agentului si trimite aceasta informatie

controlerului, iar controlerul compara starea curenta a agentului cu o valoare de referinta,

calculand o lege specifica de control care este utilizata de agent pentru a actiona

actuatorul.

Intarzierea reprezinta timpul consumat de agent pe parcursul comunicarii dintre

acesta si controler, este timpul care ii este necesar controlerului pentru a calcula

informatia ce se doreste a fi actualizata si intarzierea este timpul consumat pentru

transmiterea actualizarii de la controler la agent.

In general, modelul dinamic al agentului (sau a sistemului de control) este descris

de urmatoarea ecuatie:

∫( ) ( ) ( ), in care x este vectorul de stare al

agentului, u este intrarea de control a agentului, iar y este valoarea masurata la iesirea

agentului.

Daca agentul este liniar, ecuatia (1) se poate scrie ( ), unde A,B,C sunt matrici sau vectori care descriu agentul.

Fig. 3 – Schema bloc tipica sistemului NCS

8

3.1. Intarzierile intr-un Sistem de Control al Retelei

Senzorii si actuatorii au limitat capacitatile computationale si foloseste astfel perioade de esantionare scurte pentru a permite un bun control al agentului, conform lui Walsh [4]. Exista un anumit numar de intarzieri care sunt inerente in cadrul NCS. Acestea conduc la formarea unei intarzierieri totale in comunicatia dintre agent si controler.

3.1.1.Intarzierea totala

Intarzierea totala este o mare problema in NCS. Aceasta presupune ca reteaua de comunicatie NCS introduce intarzieri diferite intre controler si agent. Intarzierea rezultata este inevitabila si poate cauza deteriorarea performantelor sistemului. Aceasta se numeste intarzierea totala a sistemului deoarece reprezinta timpul total care ii ia unui pachet sa ajunga de la agent la controler, la care se adauga timpul de intoarcere de la controler la agent, incluzand si timpul destinat procesarii informatiei de catre controler. Ecuatia pentru intarzierea totala este descrisa mai jos:

( )

Referitor la diagrama bloc NCS din figura 3, reprezinta intarzierea de la senzor la controler, intarzierea de calcul la nivelul controlerului, iar este intarzierea de la controler la actuator.

Considerand ca intarzierea introdusa de prelucrarea informatiei la nivelul controlerului este neglijabila in raport cu celelalte doua intarzieri, ecuatia (3) se rescrie:

( ) Este de asemenea posibil ca intarzierea totala din cadrul NCS, din cauza ca in

general, si sunt similare in conditiile in care nu exista trafic aditional sau calea dintre

controler si agent a ramas nemodificata, sa fie egala cu dublul lui .

( )

3.1.2. Intarzierea introdusa de retea

Exista in situatiile reale si intarzieri introduse de retea in sistemul NCS. Acestea

includ incarcarea traficului din managementul retelei si suprasarcina protocoalelor de

rutare. O astfel de intarziere poate avea efect detrimental asupra performantelor totale ale

sistemului NCS.

Exista doua cai pentru a preintampina intarzierea transmisiunii. Una dintre acestea

este de a imbunatati calitatea transmisiunii pe retea optimizand protocoalele de

comunicatie si adoptand dispozitive hardware cu performante foarte mari astfel incat

intarzierea indusa sa fie ignorata. Cealalta cale presupune contracararea efectului

intarzierilor de retea induse in sistem folosind argumente de control teoretice, cum ar fi

compensarea timp-intarziere, controlul optim stohastic, controlul predictiv si controlul

robust.

3.2. Stabilitatea sistemului NCS

Stabilitatea este definita drept mentinerea constanta a traficului atat pentru retea cat

si pentru sistemul de control. Premisele de la care porneste mentinerea stabila a

sistemului NCS sunt:

Determinarea si mentinerea nivelelor de congestie din cadrul retelei la un nivel tolerabil;

Calcularea si mentinerea unor rate de pierdere a pachetelor acceptabile;

9

Compensarea datelor incomplete sau intarziate primite de la senzor; Implementarea unui controler optim de planificare de sarcini in timp real; Compensarea esantionarii neregulate; Adoptarea dinamica a intervalului de esantionare si a intarzierii medii a

pachetului. Majoritatea sistemelor de control nu sunt sisteme de procesare hard in timp real.

Astfel, procesele de control care nu ajung la final nu sunt critice pentru perfomanta sau

stabilitatea sistemului deoarece pot fi reluate din memorie.

Stabilitatea unui sistem NCS fara fir are un set problemele proprii care depind de:

proprietatile intrinseci ale mediului wireless, posibilitatea existentei unei topologii dinamice

ale retelei, sursa de alimentare finita si raza limitata de transmisie.

Pentru a asigura stabilitatea NCS-ului, esantionul de la agentul k trebuie sa ajunga

la controler inainte de esantionul k+1. Astfel, sistemul NCS trebuie sa se conformeze

ecuatiei de mai jos:

( ), unde este intarzierea totala a retelei

si este perioada de esantionare curenta a agentului. Intarzierile mai mari decat

perioada de esantionare pot provoca rezultate instabile si nedorite in ceea ce priveste

agentul.

3.3. Algoritmul de intarziere specific MANET Una dintre caracteristicile MANET o reprezinta natura multi-hop a retelei, iar problema acesteia o constituie intarzierile care sunt introduse. Algoritmul multi-hop permite retelelor MANET sa isi exercite caracterul lor de comunicare multipla. Dezvoltarea algoritmului trebuie sa inceapa cu investigarea metodei in care nodurile retelei MANET trimit pachete de-a lungul acesteia. Timpul de transmisie dintre doua noduri vecine trebuie sa fie modelat intr-o anume maniera astfel incat o valoare potrivita sa poata fi folosita pentru a calcula timpii de transmisie utilizati in algoritmul de intarziere multi-hop. Ruta pe care un pachet o strabate de la sursa la destinatie poate fi considerata printr-un numar intermediar de noduri, depinzand astfel de protocolul utilizat, distanta dintre noduri si mobilitatea acestora. Timpul de transmisie dintre fiecare nod se adauga la intarzierea totala. Astfel, este posibil ca aceasta crestere a intarzierii totale sa poata fi calculata cu ajutorul formulei urmatoare, presupunand ca numarul de hopuri dintre controler si agent este cunoscut, ruta este stabila si nu se schimba, iar traficul extern nu creeaza intarzieri suplimentare:

∑ ( ) ( ), unde h este numarul de hopuri

dintre sursa si destinatie, iar ( )reprezinta timpul mediu de transmisie dintre noduri.

Timpul de transmisie este considerat ca fiind timpul necesar transmiterii unui pachet complet (de exemplu: starea unui agent sau actualizarea transmisa de controler) de la un nod si receptia completa la vecinul sau. Aceasta ecuatie poate fi utila considerand ca numarul de noduri dintre sursa si destinatie este cunoscut si ca ruta dintre controler si agent este aceeasi si pentru ramura de intoarcere. Pentru un protocol proactiv, stiind ca ruta dintre sursa si destinatie este mentinuta de protocolul de rutare, se poate presupune ca ruta dintre agent si controler este cunoscuta si este data de ecuatia (7) in care se calculeaza intarzierea totala, dar pentru un protocol reactiv, in care ruta dintre sursa si destinatie nu este cunoscuta, ecuatia se schimba deoarece se mai adauga si timpul suplimentar datorat descoperirii rutei pe langa timpul transmisiei dintre controler si agent. Astfel ecuatia (7), in acest caz, devine:

10

{

∑ ( )

⏞

∑ ( )

⏞

∑ ( )

( )

Capitolul 4. Teoria teletraficului cu coada de asteptare

Teoria cozii de asteptare [5] reprezinta un studiu matematic al unui model de

asteptare in rand sau in coada/stiva care permite analiza matematica a unor numeroase

procese asociate. Acestea includ sosirea la intrarea cozii, asteptarea in coada si servirea

primului din element la iesirea din coada.

Atunci cand se foloseste comunicatie de tip pereche-la-pereche in cadrul unei

retele, timpul care ii ia unui pachet sa traverseze conexiunea este dependent de o

sumedenie de factori de intarziere:

( ), unde este intarzierea

introdusa de coada si este intarzierea dintre agent si controler in cazul in care

exista noduri intermediare in interiorul acestora. Pentru a rezolva problema concurentei

mai multor surse in retelele MANET, se poate calcula latenta pachetului prin insumarea

tuturor intarzierilor fiecarei legaturi si a intarzierilor prin fiecare coada:

∑ ( ( ) ( )) ( ), unde i este o

legatura anume dintre nodurile vecine si m este numarul total de noduri dintre controler si

agent, in care intotdeauna exista cu o conexiune mai putin fata de numarul total de noduri.

Teoria teletraficului presupune un proces Poisson [5] de modelare a traficului, cum

este ilustrat in figura 4. Fiecare proces genereaza un pachet care are o rata exponentiala

de sosire si o dimensiune specifica, toate acestea stocandu-se intr-o coada de tipul FIFO.

Fig. 4 – Proces Poisson de modelare a teletraficului

11

Spre deosebire de acest tip de proces, un sistem NCS creeaza pachete la o rata

constanta ( ) si de dimensiune constanta ( ).

4.1. Adaptarea procesului Poisson la retelele MANET multi-hop

Nodurile conectate intr-o retea MANET trebuie sa directioneze pachetele care sunt

receptionate de la alte noduri ale retelei spre destinatie. De asemenea, este necesar sa se

transmita actualizari periodice ale rutelor si a mesajelor de mentenanta de-a lungul retelei,

folosind un protocol de rutare potrivit.

Pornind de la acest model si de la premisele enumerate mai sus, acest tip de

proces se poate adapta la retelele MANET in cazul salturilor multiple. La fiecare nod

intermediar, traficul extern este adaugat cozii, cum este ilustrat si in figura 5.

Modelul din figura 5 are n procese constante ale agentilor care furnizeaza fiecare

dintre acestea pachete/s la o rata constanta in coada, fiecare cu un mesaj de lungime

constanta de biti/mesaj si astfel, timpul total de inter-sosire si dimensiunea medie a

pachetelor care sosesc in fata bufferului infinit este dat de ecuatiile:

∑

∑

( )

Atunci cand fiecare proces constant are aceeasi perioada de esantionare ( )

, iar atunci cand fiecare proces are aceeasi dimensiune a pachetelor,

egalitatea este satisfacuta in conditiile in care este inversul

dimensiunii pachetului.

Capacitatea serviciului sistemului descris de teoria teletraficului este:

( ) , unde este rata de transmitere a

datelor, iar in exemplul pe care l-am descris, rata de transmitere a datelor este specifica

standardului wireless 802.11b (11 Mb/s).

Fig. 5 – Procesul de modelare a teletraficului pentru o retea MANET

multi-mod cu multi-legaturi

12

4.2. Intarzierea medie din coada

Intarzierea medie din coada furnizata de teoria tele-traficului pentru un proces

Poisson este:

( )

Aceasta intarziere medie din coada este o aproximare ce presupune ca pachetele

Poisson care sosesc si dimensiunea acestora creeaza o supraestimare a intarzierii

traficului din NCS. Daca se presupun n surse cu perioade de esantionare egale intre ele

( ) atunci inseamna ca aceste n pachete ajung simultan la fiecare perioada .

Fiecare pachet va fi

introdus in coada si va fi

servit dupa o intarziere

minima de proces cum

este ilustrat in graficul 6.

Intarzierea pentru

proces poate fi

calculata folosind

urmatoarea formula:

( ) , in care este rata de

date pentru standardul

802.11 al retelelor fara fir

egala cu 11 Mb/s.

Astfel, al n-lea pachet va introduce cozii o intarziere de . Este de dorit sa se

programeze sosirea pachetelor pe rand la destinatie pentru ca astfel va rezulta o intarziere

minima de timp . Acest lucru se poate obtine prin decalarea timpilor de start ale

surselor astfel incat timpul de start al sursei a “i”-a sa fie dat de ecuatia:

( ) ( )

( ) pentru presupunand ca toate

perioadele de esantionare sunt egale.

Din cele aratate mai sus reiese ca exista o limita a numerelor de pachete care pot fi

servite de coada in orice perioada de esantionare data. Daca timpul dintre sosiri

consecutive este mai mic decat atunci nu va aparea nicio eroare. Aceasta limita

poate fi calculata folosind inegalitatea:

( )

Daca aceasta conditie nu este satisfacuta atunci va aparea congestie datorita

faptului ca nu va exista suficient timp pentru eliberarea cozii inainte de sosirea urmatorului

Fig. 6 – Dependenta numarului de pachete din coada

in timp

13

pachet, crescand astfel intarzierea. Atunci cand timpii de sosire sunt decalati, timpul de

asteptare in coada va creste si el, dar nu la fel ca in cazul in care se folosesc timpi de start

nedecalati.

Concluzionand cazul generarii pachetelor de la n surse, putem afirma ca cele n

pachete vor fi generate simultan si vor ajunge tot simultan in coada. Un pachet va suferi o

intarziere maxima in coada de , iar intarzierea medie a pachetului atunci cand

conditia (16) este indeplinita va fi:

∑ ( )( ( )) ( )

4.3. Intarzierea medie de conexiune

Atunci cand se modeleaza coada in cazul unui singur nod, natura multi-hop a

retelelor MANET nu este luata in calcul. Astfel, pentru cazul cand exista mai multe noduri,

timpul pe care-l consuma un pachet care se propaga printr-o legatura intre nodurile vecine

trebuie sa fie luat in considerare atunci cand se calculeaza intarzierea totala.

Aceasta intarziere de legatura poate fi calculata astfel:

(

) (

) ( ) , unde este distanta dintre

legaturi exprimata in metri, c este viteza luminii ( ), iar µ este dimensiunea

pachetului.

Atunci cand exista legaturi multiple intre sursa si destinatie, intarzierea totala a

conexiunii este:

∑ (

) (

)

( ), unde m este numarul de legaturi dintre sursa si

destinatie.

Capitolul 5. Simularea modelului MANET multi-hop

5.1. Simularea modelului Poisson cu un singur proces

Modelul Poisson cu un singur proces a fost simulat in utilitarul OPNET. Procesul

Poisson a fost modelat de o sursa simpla care transmite pachete la un interval fix de 0.02

secunde ceea ce inseamna ca va transmite 50 de pachete (λ) pe secunda. Fiecare pachet

are dimensiunea ( ) de 1024 de biti.

Sursa transmite pachete catre o coada, care este de tip acb_fifo. Acest lucru

inseamna ca primul element sosit iese primul din coada, iar prescurtarea “acb” se refera

la:

- A (actioneaza ca un server propriu); - C (concentreaza fluxurile multiple de pachete care sosesc intr-o coada simpla

interna); - B (timpul de servire depinde de numarul de biti din pachet). Rata de transmitere din coada (C) a fost fixata de 11Mb/s conform standardului

802.11b.

Serverul a fost simulat printr-un procesor de acumulare, a carui functie este doar de

a receptiona pachete, nefiind nevoie de o configurare a parametrilor sai.

14

Pentru a calcula intarzierea de la sursa la controler (simulat prin server), se

utilizeaza formula (9):

Datorita faptului ca aceasta simulare s-a facut pentru un singur nod si astfel,

neexistand conexiune intre mai multe noduri, intarzierea este nula.

( )

Intarzierea medie din coada se calculeaza cu ajutorul formulei (17).

∑ ( )( ( ))

Numarul de procese este n=1 deoarece simularea se face pentru un model Poisson

cu un singur proces, iar inlocuindu-se n in formula de mai sus, va rezulta ca:

( ) ( )

Inlocuind in formula (14) valorile alese anterior va rezulta:

Daca se va inlocui in formula (21) va rezulta ca timpul mediu de

intarziere prin coada va fi de .

Schema bloc a procesului Poisson simulat este reprezentata in figura 7,

amplasarea nodului in spatiu este ilustrata in figura 8, iar graficul rezultat experimental

pentru intarzierea medie prin coada in figura 9.

S-a obtinut in urma simularii o intarziere .

Diferenta dintre rezultatul teoretic si cel simulat este de:

( ).

Eroarea relativa este de:

( )

15

Fig. 7 – Modelul Poisson pentru cazul unei singure

surse, cu coada simpla si server unic

Fig. 8 – Localizarea in spatiu a nodului 1

16

5.2. Simularea modelului Poisson cu 3 procese concurente

Cele trei procese concurente au fost modelate de trei surse simple care transmit

pachete la un interval fix de 0.02 secunde ceea ce inseamna ca fiecare dintre aceastea va

transmite 50 de pachete (λ) pe secunda. Fiecare pachet are dimensiunea ( ) de 1024

de biti.

Sursele transmit pachete catre o coada, care este de tip acb_fifo, ce are rata de

transmitere din coada (C) fixa si egala cu 11Mb/s conform standardului 802.11b.

Serverul a fost simulat printr-un procesor de acumulare, a carui functie este doar de

a receptiona pachete, nefiind nevoie de o configurare a parametrilor sai.

Pentru a calcula intarzierea de la sursa la controler (simulat prin server), se

utilizeaza formula (9):

Datorita faptului ca aceasta simulare s-a facut pentru un singur nod si astfel,

neexistand conexiune intre mai multe noduri, intarzierea este nula.

( )

Intarzierea medie din coada se calculeaza cu ajutorul formulei (17).

∑ ( )( ( ))

Numarul de procese in acest caz este 3, iar inlocuindu-se in formula de mai sus

n=3, va rezulta ca:

∑ ( )( ( ))

[ ( ( )) ( ( )) ( ( ))] ( )

Fig. 9 – Intarzierea medie prin coada

17

In acest caz intarzierea corespunzatoare fiecarui proces este egala cu cea din cazul

prezentat anterior, unde exista doar o singura sursa pentru ca rata de transmitere si

dimensiunea pachetului sunt aceleasi.

Daca se va inlocui in formula (24) pentru fiecare dintre procese va

rezulta ca timpul mediu de intarziere prin coada va fi:

( )

Schema bloc a procesului Poisson simulat este reprezentata in figura 10,

amplasarea nodului in spatiu este ilustrata in figura 11, iar graficul rezultat experimental

pentru intarzierea medie prin coada in figura 12.

S-a obtinut in urma simularii o intarziere .

Inlocuind valorile rezultate pentru acest caz in formula (22) se obtine o diferenta de:

.

Eroarea relativa este de:

( )

Fig. 10 – Modelul Poisson pentru cazul a trei surse

concurente, cu coada simpla si server unic

18

Fig. 11 – Localizarea in spatiu a nodului 2

Fig. 12 – Intarzierea medie prin coada

19

5.3. Simularea unui model multi-nod

Pentru a simula un model multi-nod se vor inlantui trei noduri intermediare intre

agent si controler. Astfel, agentul va fi constituit din 3 surse simple care vor modela

procesele Poisson si acestea vor fi transmise prin intermediul unui bloc de transmitere

spre nodul urmator (figura 13a)). Transmiterea din nod in nod se va realiza folosind

receptori si transmitatori. In fiecare nod intermediar va exista o coada simpla ce va stoca

pachetele generate de sursele simple si acesta va fi conectata la intrare cu un receptor, iar

la iesire cu un transmitator, cum este ilustrat in figura 14. Controlerul va fi format dintr-un

bloc de receptie si un procesor de acumulare, unde vor fi receptionare pachetele

transmise de agent (figura 13 b)).

Fig. 13 a) – Modelul agentului Fig. 13 b) – Modelul controlerului

Fig. 14 – Modelul nodului intermediar

20

In cadrul modelului multinod cu 3 noduri intermediare, plasarea nodurilor s-a

realizat intr-un spatiu de dimensiune 500mx500m, in care distanta dintre noduri va fi de

50m. In figura 15 este ilustrata topologia retelei multi-nod considerate pentru

exemplificare.

In exemplul considerat, agentul este compus din 3 surse simple, exact ca si in cazul

5.2. Astfel, intarzierea prin coada va fi egala cu cea calculata in formula (25), adica

.

Pentru a calcula intarzierea totala de la agent la controler va fi nevoie de intarzierea

introdusa de legaturi. Aceasta se calculeaza cu ajutorul formulei (19).

Intarzierile introduse de legaturi sunt egale deoarece atat rata de transmitere a

pachetelor, cat si distanta dintre noduri sunt respectiv egale. Este necesar sa calculam

intarzierea doar pentru o linie, cu ajutorul formulei (18), dupa care valoarea rezultata se va

introduce in formula (19) care va multiplica aceasta valoare cu numarul de legaturi din

topologie.

Fig. 15 – Topologia retelei multi-nod

21

( ) (

) (

) (

) (

)

Introducand timpul mediu de intarziere prin coada si intarzierea totala prin legaturi,

se obtine astfel intarzierea totala de la agent la controler, care este egala cu intarzierea

totala de la controler la agent.

( )

In urma simularii, utilitarul OPNET a simulat cu o intarziere pe legatura de

aproximativ 45µs, rezultand o intarziere totala pe linie de 160µs. Daca inlocuim in formula

(27) aceasta intarziere va rezulta:

Intarzierea agent-controler rezultata in urma simularii topologiei este de

.

Eroarea relativa este de:

Fig. 16 – Intarzierea totala agent-controler si

intarzierea totala de linie

22

Concluzii

In retelele cu fir exista legaturi specializate care se ocupa de controlul proceselor de

retea. Acestea presupun o corectie de eroare si retransmisie mai scazuta decat in cazul

retelelor wireless, furnizand astfel o largime de banda mai mare pentru date. Totusi,

neajunsul acestor retele este acela ca nu prezinta portabilitate, ci este in permanenta

nevoie de o legatura fizica intre echipamente.

In cazul retelelor fara fir bazate pe infrastructura aceasta limitare de conexiune

dispare pentru echipamentele care se conecteaza la cel mai apropiat punct de acces, dar

ramane constrangerea ca punctele de acces trebuie sa fie conectate intre ele printr-o

legatura fizica.

Retele MANET elimina aceasta constrangere, nemaifiind nevoie de un punct de

acces deoarece in cazul unei conexiuni de tipul ad-hoc, unul dintre dispozitive preia rolul

de punct de acces si gestioneaza traficul de date intre celelalte echipamente sau intre

echipamente si dispozitivul gazda.

Pentru a controla traficul de pe retea, retelele MANET se folosesc de modelul NCS,

care presupune existenta unui agent care interactioneaza cu mediul si care transmite

datele pe care le primeste unui controler care le prelucreaza.

In cazul datelor receptionate de la mai multe surse, pentru a putea fi prelucrate de

catre controler si pentru a nu se pierde nicio informatie, agentul le va organiza intr-o coada

de tip FIFO (first in first out – primul intrat primul iesit). Astfel, controlerul le va prelucra pe

rand in ordinea sosirii lor in coada.

In urma simularilor si a calculelor, s-a observat ca daca nu ar fi existat coada

respectiva, ar fi rezultat congestia traficului sau pierderea informatiilor. In cazul unei

singure surse s-a obtinut o intarziere totala de 93.09 µs. Faptul ca informatiile de la mai

multe surse concurente (3 surse) au fost organizate intr-o coada care le transmite decalat

controlerului a rezultat o intarziere mult mai mica (186. 18µs) decat daca acestea ar fi fost

transmise controlerului rand pe rand (pentru 3 noduri in care intarzierea fiecarui pachet

este de 93.09 µs ar rezulta o intarziere totala de 3*93.09 µs=279.27 µs).

Intarzierea totala pentru cazul multi-nod ( in care exista 3 noduri intermediare intre

agent si controler) rezultata a fost de . Daca ar fi fost transmise rand pe rand,

de la un nod la altul, fara a folosi o structura de tip coada FIFO, s-ar fi obtinut congestie

sau ar fi rezultat un timp minim de 279.27 µs multiplicat cu numarul de noduri intermediare

(279.27 µs*3= 837.81µs, mult mai mare decat 320 µs).

Distanta dintre noduri este un factor important deoarece intarzierea prin legatura va

creste in cazul in care va creste si distanta dintre noduri. O distanta mult prea mare intre

noduri va rezulta o legatura foarte slaba.

23

Bibliografie

[1] http://en.wikipedia.org/wiki/Mobile_ad_hoc_network

[2] M. Murray, An introduction to Network Control Systems, California Institute of

Technology, 2006, pp. 6-11

[3] A. Tanenbaum, Computer networks 4th ed, Ed. PrenticeHall, Indianapolis, 2002, pp

235-241

[4] T. Walsh, J. DiCelie, M. Young, B. Peet, Concordia: An infrastructure forcollaborating

mobile agents, Ed. LNCS, Berlin, 1997, pp. 86-97

[5] M. Zukerman, Introduction to Queueing Theory and Stochastic Teletraffic Models, 2000

pp. 16-30, 50-52, 59-64.

[6] Documentatia utilitarului OPNET ,Tabelul 6.5 – Modele de procese care au loc in

coada, v.14.5