Universitatea Politehnic Timioara

Proiect Comunicatii Fara Fir

Reele de comunicaii ad-hoc

Jieanu Loredana Adriana LoleaCoord: Sl. Dr. Ing. Cornel Balint

IRT 3.1

Timisoara 2011

1. IntroducereComunicaiile wireless ntre utilizatori mobili au devenit din ce n ce mai populare. Acest fapt se datoreaz avansului tehnologic pe care l-au nregistrat laptopurile i dispozitivele de transfer de date wireless, precum i modem-urile wireless sau LAN-urile wireless.Toate astea au dus la preuri sczute i rate de transfer mai ridicate, acestea fiind i principalele motive pentru care comunicaiile mobile se bucur de o cretere rapid. Exist dou variante de realizare a comunicaiei wireless ntre dou staii. Prima ar fi s apelm la infrastructura reelei de telefonie mobil existent pentru a transmite date la fel cum transmitem voce. Marea problem o reprezint lipsa de ndemanare, conexiunea ar trebui manevrat uor, de la o staie la alta, far delay notabil sau pierdere de pachete. O alta problem este c reelele bazate pe infrastructur celular sunt limitate la spaiile unde exist o astfel de infrastructur. O a doua variant de abordare este aceea de a crea o reea ad-hoc ntre toi utilizatorii care vor s comunice ntre ei. Asta presupune c toi utilizatorii ce particip la reeaua ad-hoc trebuie s trimit mai departe pachetele de date, astfel nct acestea s ajung de la surs la destinaie. Aceast form de comunicare este limitat ca rat de ratele nodurilor individuale i este n general mai mic comparativ cu gradul de complexitate al reelelor celulare. Reelele ad-hoc au cteva avantaje fa de sistemul tradiional al reelei celulare. Printre acestea amintim: Crearea la cerere Toleran la erori Conectivitate nelimitat

Reelele ad-hoc nu se bazeaz pe nicio infrastructur prestabilit, i pot fi astfel folosite n locuri far infrastructur existent. Asta poate fi util de exemplu n situaii de revenire n urma dezastrelor, sau n locuri cu infrastructur de comunicaii inexistent sau afectat, unde dezvoltarea rapid a unei reele de comunicaii este necesar. Reelele ad-hoc pot fi deasemenea folosite n conferine la care participanii pot forma o reea temporal far a angaja serviciile unei reele pre-existente.

Deoarece nodurile trimit mai departe pachetele, un anumit protocol de rutare este necesar pentru a face deciziile privind traseul. Numeroase probleme au trebuit soluionate inaintea stabilirii oricrui standard.2.

Generaliti

O reea ad-hoc wireless este o colecie de noduri mobile sau semi-mobile far o infrastructur prestabilit, ce formeaz o reea temporar. Fiecare nod are o interfa wireless iar nodurile comunic ntre ele fie prin unde radio, sau inflarou. Computere Laptop sau Notebook-uri digitale ce comunic direct ntre ele pot fi astfel de noduri ntr-o reea ad-hoc. Nodurile dintr-o reea ad-hoc sunt adesea mobile, dar pot fi i noduri staionare, precum puncte de acces (access point) la Internet. Figura 1 arat o reea wireless ad-hoc simpl cu trei noduri. Primul i ultimul nod nu sunt n aria de transmisie a celuilalt. Nodul din mijloc poate fi astfel folosit pentru a transmite pachetele ntre nodurile marginale. Nodul din mijloc se comport ca un router, i cele trei formeaz o reea adhoc.

Fig. 1: Exemplu de reea ad-hoc simpl cu trei noduri participante O reea ad-hoc nu folosete o administrare centralizat. Acest lucru asigur fiabilitatea reelei atunci cnd unul dintre nodurile mobile se deplaseaz n afara razei de transmisie a celorlalte noduri. Nodurile ar trebui s poat intra i iei din reea aa cum vor. Din cauza razei limitate de transmitere a nodurilor ar putea fi necesar rutarea multi-hop pentru a ajunge la nodul dorit. Fiecare nod ce particip la o reea ad-hoc trebuie s transmit pachete mai departe ctre celelalte noduri, prin urmare fiecare nod se comport att ca host ct i ca router. Un nod poate fi vzut n mod abstract ca o entitate constituit dintr-un router i un set de host-uri mobile afiliate.(fig 2) Un ruter este o entitate care ruleaz un protocol de rutare. Un host mobil este o entitate adresabil IP n sensul tradiional.

O reea ad-hoc este deasemenea capabil de manevrarea schimbrilor de topologie, sau a nodurilor disfuncionale. Astfel de probleme se rezolv prin reconfigurarea reelei. De exemplu, n cazul n care un nod parasete reeaua i cauzeaz ruperea legturilor, nodurile afectate pot foarte uor s cear noi legturi i problema va fi rezolvat. Acest lucru va crete puin delay-ul, dar reeaua va fi operaional. Fig. 2 Diagrama bloc a unui nod mobil ce se comport att ca host ct i ca router

Reelele ad-hoc profit de pe urma mediului de comunicare wireless. Cu alte cuvinte, ntr-o reea bazat pe cablu, cablarea se realizeaz apriori, ceea ce restricioneaz topologia conexiunii precum i poziionarea nodurilor. Aceasta restricie nu exist n cadrul wireles i, de fiecare dat cnd dou noduri se afl unul n aria de transmisie a celuilalt o legtur instantanee poate fi creat. Diferitele utilizri ale acestor reele variaz de la sharing de documente la conferine, creterea infrastructurii i aplicaii militare. In zone fr infrastructur n care internetul este accesibil, o reea ad-hoc wireless poate fi folosit de un grup de host-uri mobile. Acesta poate fi cazul unor zone n care o infrastructur de reea nu este dezirabil din motive de cost sau convenien. Alte exemple includ asociaii unei afaceri ce vor s fac schimb de fiiere n aeroport, sau o clas de studeni ce doresc s interacioneze n timpul lecturii. Dac fiecare host mobil ce dorete s comunice este echipat cu o interfa wireless local, grupul de host-uri mobile pot forma o reea ad-hoc. Accesul la Internet sau accesul la resursele din reea precum imprimante sunt caracteristici deasemenea permise. Reelele ad-hoc sunt adesea caracterizate printr-o topologie dinamica datorat faptului c nodurile i schimb locaia fizic adesea. Asta favorizeaz protocoalale de rutare ce descoper n

mod dinamic rutele, bazate pe algoritmi de rutare convenionali precum Vectorul Distana (Distant Vector) i Starea Legturii (Lik State). O alt caracteristic ar fi aceea c hostul/nodul are o capacitate limitat a procesorului, capacitate de stocare deasemenea limitat, puterea bateriei, banda-toate limitate. Se inelege c puterea limitat conduce la o raz de transmisie limitat. Mediul de acces, mediul radio prezint caracteristici speciale de care trebuie tinut cont atunci cnd se stabilesc protocoalele pentru reelele ad-hoc. Un astfel de exemplu poate fi legtura unidirecional. Acest tip de legturi se ntlnesc de exemplu atunci cnd dou noduri au putere diferit a transmitoarelor, permind ca doar unul dintre host-uri s il aud pe celalalt, sau poate fi cauzat deasemenea de perturbaiile mediului nconjurator. Tehnica multi-hop n mediul radio poate conduce la o capacitate de transmisie mai mare, sau la un ctig de putere. Folosind multihopul, nodurile pot transmite pachete folosind o putere de ieire mult mai sczut.

3.RoutareaDatorit faptului c un pachet poate trece pe la mai multe noduri (multi-hop) nainte de a ajunge la destinaie, un proces de rutare este necesar. Protocolul de rutare are dou funcii principale: selectarea rutelor (cailor) pentru diferitele perechi sursa-destinaie i livrarea pachetelor la destinaia corect. 3.1. Protocoale Convenionale Dac este necesar utilizarea unui protocol de rutare, de ce sa nu folosim unul conveional, precum Starea Legturii, sau Vectorul Distan? Sunt bine testate, i majoritatea computerelor folosite pentru comunicare inter uman sunt familiare cu ele. Cea mai important problem a acestora este ns faptul c sunt proiectate pentru o topologie static, ceea ce nseamn c ar putea aprea probleme cnd vine vorba de o topologie frecvent schimbtoare. Protocoalele Starea Legturii i Vectorul Distan ar funciona probabil foarte bine n cazul unei reele ad-hoc cu o mobilitate sczut (o reea a crei topologie nu se schimb foarte des). O alt problem este aceea c aceste protocoale sunt n foarte mare masur dependente de mesajele de control periodice. Cum numrul nodurilor reelei poate fi mare, numrul potenial al adreselor destinaie poate deasemenea fi foarte mare. Aceast situaie cere un schimb de informaii frecvent i destul de ridicat ntre nodurile reelei, ceea ce vine n contradicie cu faptul c ntr-o reea wireless ad-hoc informaiile sunt transmise prin intermediul aerului, i prin urmare sunt costisitoare n ceea ce privete resursele de band, putere a bateriei, i CPU. Att Starea Legturii ct i Vectorul Distan menin rutele ctre toate destinaiile posibile, ceea ce deasemenea irosete resurse importante.

O alt caracteristic a protocoalelor convenionale este c acestea presupun legturi bidirecionale, adic transmisia ntre dou host-uri funcioneaz n mod simetric n ambele direcii. n cadrul reelelor wireless, adic a mediului radio aceast situaie nu este mereu ntlnit.

Starea Legturii n cadrul protocolului Starea legturii , fiecare nod pstreaz informaii n legtur cu topologia complet a costurilor fiecrei legturi. Pentru a pstra consistena acestor costuri, fiecare nod n mod periodic difuzeaz costurile legturilor sale exterioare ctre toate nodurile folosind flooding-ul (inundare). Cum fiecare nod primete aceste informaii, i actualizeaz informaiile sale n legtur cu reeaua, i aplic un algoritm de tip cel mai scurt drum pentru a alege urmtorul nod n cazul fiecrei adrese destinaie. Unele costuri ale legturilor pot fi eronate, datorit ntrzierilor de propagare, partiionrilor reelei,etc. Aceste inconsistene pot duce la formarea unor bucle de rutare, acestea nu au totui o durat de via foarte mare, ele dispar n timpul necesar unui mesaj s parcurg diametrul reelei. Vectorul Distan In cadrul Vectorului Distan, fiecare nod monitorizeaz doar costul necesar legturilor sale exterioare, dar n loc de difuzarea acestei informaii ctre toate nodurile, trimite n mod periodic vecinilor si o estimare a celei mai scurte distane ctre oricare alt nod din reea. Nodurile ce primesc aceasta informaie o folosesc pentru a recalcula tabelele de rutare folosind un algoritm de tipul cel mai scurt drum. Comparativ cu Starea Legturii, Vectorul Distan este din punct de vedere al calcului mai eficient, mai uor de implementat i solicit un spaiu de stocare mult mai mic. Vectorul Distan poate duce la formarea de bucle de rutare cu durata de via mare sau mic. Cauza primar a apariiei acestor bucle este aceea c nodurile aleg urmatorul hop ntr-o manier complet distribuit, bazat pe informaii ce pot fi neactualizate. Rutarea La Surs Rutarea la Surs presupune ca fiecare pachet s poarte informaia complet a cii pe care acesta trebuie s o urmeze n reea. Decizia rutrii are deci loc la surs, evitndu-se astfel destul de uor apariia buclelor la rutare. Dezavantajul este evident antetul ce se adaug tuturor pachetelor ca o informaie suplimentar ce trebuie transmis. Floodingul (Inundarea) Multe protocoale de rutare folosesc broadcasting-ul pentru a distribui informaii de control, iar acesta presupune trimiterea acestor informaii de la nodul origine ctre toate celelalte noduri. O metod de brodcasting foarte larg rspndit este flooding-ul (inundarea) i presupune: nodul

origine trimite informaia ctre vecinii si(n cazul reelelor wireless tuturor nodurilor din raza sa de transmisie). Vecinii trimit la rndul lor la nodurile nvecinate lor, i aa mai departe, pn cnd pachetul a ajuns la toate nodurile reelei. Un nod trimite pachetul o singur dat la un grup de noduri , i se utilizeaz o anumit secven numeric ce poate fi folosit. Aceast secven este incrementat la fiecare nou pachet pe care nodul il trimite. Clasificare a protocoalelor de rutare Protocoalele de rutare pot fi clasificate n diferite categorii, n funcie de proprietile lor. Centralizate sau Distribuite Statice sau Adaptive Reactive sau Proactive

O clasificare a protocoalelor de rutare este aceea ce le mparte n funcie de algoritm n centralizate, sau distribuite. n cazul algoritmilor centralizai, toate hotrrile n legtur cu calea pachetului sunt luate de un nod central, n timp ce n cazul celor distribuite alctuirerea rutei este mprit ntre nodurile unei reele. O alt clasificare a protocoalelor de rutare se refer la schimbarea rutei ca rspuns la caracteristicile traficului. n cazul algoritmilor statici ruta surs-destinaie este fix, indiferent de condiiile de trafic, aceasta se poate schimba doar ca raspuns la eecul unei legturi. Acest tip de algoritmi nu poate obine un randament ridicat n raport cu varietatea traficului. Majoritatea pachetelor transmise n reea folosesc o anumit form de rutare adaptiv, unde calea poate fi schimbat ca rspuns la cazurile de congestie. O a treia clasificare, cea care prezint relevan pentru reelele ad-hoc este aceea care clasific protocoalele de rutare ca fiind fie proactive, fie reactive. Protocoalele proactive ncearc s evalueze n mod constant rutele din cadrul reelei, ca atunci cnd un pachet trebuie trimis mai departe, ruta este deja cunoscut i poate fi imediat utilizat. Familia protocoalelor VectorDistan sunt exemple de protocoale proactive. Protocoalele reactive, pe de alta parte apeleaz la realizarea unei proceduri de determinare a rutei doar la cerere. Familia algoritmilor ce folosesc flooding-ul aparin acestui grup reactiv.Algoritmii proactivi au avantajul c prezint un delay relativ mic din momentul n care o rut este necesar pn n momentul n care pachetele pot fi efectiv trimise. Pe de alta parte, acetia necesit timp pentru un stadiu de pregtire. n cazul n care topologia este frecvent schimbtoare pot aprea probleme. 3.2. Protocoale de rutare ad-hoc Proprieti dezirabile

Dac protocoalele de rutare convenionale nu ndeplinesc ntru totul cerinele unei reele ad-hoc wireless, sunt necesare noi protocoale. Care sunt de fapt aceste proprieti dezirabile, pe care un astfel de protocol trebuie s le aib?

Distributiv operaional. Protocolul ar trebui s fie evident de tip distribuit, nu trebuie s depind de un nod de control central. Aceasta este o cerin dezirabil pn i pentru reelele staionare. Diferena ar fi c nodurile ntr-o reea ad-hoc pot intra/iesi din reea foarte uor datorit mobilitii, i astfel reeaua ar putea fi partiionat. Fr bucle de rutare. Pentru mbuntirea performanelor generale, se vrea ca protocolul de rutare s garanteze c traseele alese nu prezint bucle. Asta elimin consumul inutil de band i deasemenea CPU. Operaii la cerere. Pentru a minimiza datele de control care circul n rea, i pentru a nu irosi resurse ale reelei n mod inutil i nenecesar, protocolul ar trebui s fie reactiv. Asta nseamn c acesta reacioneaz atunci cnd este necesar, i nu se difuzeaz informaii de control n rea n mod periodic. Suport al legturii unidirecional. Mediul radio poate cauza crearea de legturi unidirecionale. Utilizarea acestui tip de legtur, i nu doar a celor de tip bi-direcional mbuntete performanele protocolului de rutare. Securitate. Mediul radio n mod deosebit este vulnerabil la atacuri, deci pentru a asigura comportamentul dorit din partea protocolului de rutare sunt necesare unele msuri preventive de securitate. Autentificare i criptare ar fi o metod de rezolvare a problemei, i ar mai rmne doar distribuirea cheilor ntre nodurile reelei ad-hoc. Se discut deasemenea folosirea securitii IP, i aici se folosete tunelling-ul pentru transportul tuturor pachetelor. Conservarea puterii. Nodurile unei reele ad-hoc pot fi laptop-uri, sau PDA, dispozitive limitate ca putere a bateriei, i este folosit o metod de stand-by pentru economia de energie. Este important ca protocolul de rutare s tie a manevra aceste stri inactive. Mai multe trasee. Pentru a reduce efectele schimbrilor frecvente ale topologiei sau efectele congestiei s-ar putea utiliza multi-routing-ul. Dac un traseu devine invalid,este posibil ca o alt cale salvat sa funcioneze, nefiind necesar iniializarea unei noi proceduri de rutarea de ctre protocolul de rutare. Calitatea serviciului. Este necesar i o metod de asigurare a calitii serviciului ncorporat n protocolul de ruatre. Aceasta depinde foarte tare de utilizarea pe care reeua respectiv o va avea. Am putea vorbi de exemplu despre suport al traficului n timp real.

Niciunul dintre protocoalele propuse pentru retele de tip MANET nu ntrunete totalitatea acestor proprieti, dar este necesar s amintim c aceste protocoale sunt nca n curs de dezvoltare, i vor fi n mod cert extinse cu numeroase alte funcionaliti. Principala lor funcie este aceea de a gsi o cale ctre destinatar, nicidecum de a gasi calea cea mai bun/optim/cea mai scurt.

MANET-Mobile Ad-hoc Networks n prezent exist o multitudine de protocoale n curs de dezvoltare pentru astfel de reele. Se vor detalia o parte dintre cele enumerate mai jos, acestea fiind i cele pe care se bazeaz i dezvoltrile ulterioare.

AODV (Ad-hoc On Demand Distance Vector) Vector Distan pentru reele ad-hoc la Cerere ZRP (Zone Routing Protocol) Protocol Zonal de Rutare TORA/IMEP (Temporally Ordered Routing Algoritm/ Internet MANET Encapsulation Protocol) Algoritm Ordonat Temporal de Rutare/ Protocolul de ncapsulare pentru reele de tip MANET DSR (Dynamic Source Routing) Rutarea Dinamic la Surs CBRP (Cluster Based Routing Protocol) Protocol de Rutare Bazat pe Grupuri de Noduri CEDAR (Core Extraction Distributed Ad hoc Routing) Protocol de Rutare Distribuit bazat pe Extragerea Nucleului. AMRoute(Ad-hoc Multicast Routing Protocol ) Protocol de Rutare Multicast pentru reele de tip Ad-hoc OLSR (Optimized Link State Routing Protocol) Protocolul de Rutare Starea Legturii Optimizat

DSDV (Destination Sequenced Distance Vector) DSDV este un protocol de rutare nod-cu-nod care pstreaz la fiecare nod cte un tabel de rutare ce conine pentru toate destinaiile disponibile adresa urmtorului hop i numrul de noduri pn la destinaie. La fel ca Vectorul Distan, DSDV cere ca fiecare nod s difuzeze n mod periodic informaii de rutare updatate. Avantajul acestuia fa de protocolul traditional este acela c elimin apariia buclelor de rutare.

Pentru a garanta eliminarea buclelor, DSDV folosete o secven numeric pentru a identifica fiecare rut. Secvena numeric arat vechimea rutei, iar rutele cu secven numeric mare sunt nefavorabile. Ruta A ctre R este considerat favorabil lui R dac secvena sa numeric este mai mic, sau dac acestea sunt la fel i R are contorul de bucl mai mic. Secvena numeric este incrementat atunci cnd nodul A detecteaz c o cale ctre destinaia D a devenit indisponibil. Din acest punct mai departe A noteaz ruta ctre D cu un contor de bucl infinit i o secven numeric mult mai mare dect nainte. DSDV are la baz protocolul Vestorul Distan cu cteva mici ajustri, care l fac mai fiabil pentru reelele ad-hoc. Aceste ajustri const n update-uri declanate pentru a avea grij de schimbrile de topologie la timp pentru difuzarea informaiilor de control corecte. Pentru reducerea cantitii de informaii n cadrul acestor pachete se definesc dou tipuri de mesaje de update: tren de informaii complet, i tren incremental. Cel complet poart toate informaiile de rutare disponibile, iar cel incremental poart doar informaiile ce s-au schimbat de la ultimul tren de informaii. Datorit faptului c DSDV-ul depinde de broadcast-ul informaiilor de control necesit un timp de convergen nainte ca o cale s poat fi folosit. Acest timp de convergen (pregtire) poate fi considerat neglijabil ntr-o reea static, unde topologia nu se schimb frecvent. ntr-o reea ad-hoc, pe de alta parte, unde topologia este de asteptat s fie dinamic, acest timp de convergen nseamn probabil cteva pachete pierdute nainte ca o legtur valid s fie detectat. Acest broadcast periodic adaug la reea i o suprancrcare nedorit n cadrul reelelor de tip ad-hoc. Ad-hoc OnDemand Distance Vector-AODV Protocolul de rutare Vector Distan ad-hoc la Cerere valideaz rutarea multi-hop ntre nodurile mobile participante la crearea i meninerea unei reele ad-hoc. AODV se bazeaz pe algoritmul Vectorului Distan. Diferena este c AODV este un protocol reactiv, n timp ce DV este un protocol proactiv, AODV cere o cale doar atunci cnd este necesar, i nu necesit ca nodurile s rein ci ctre destinaii ce nu sunt n mod activ utilizate n comunicare. Caracteristici ale acestui protocol includ absena buclelor de rutare, i faptul c legturile pierdute sunt imediat anunate ctre setul de noduri interesate, dar numai respectivului set. n mod adiional AODV prezint suport pentru ruatrea multicast, i evit problema numrrii la infinit a algoritmului Bellman Ford. Folosirea secvenei numerice pentru destinaie garanteaz c o rut este fresh(updatat). Algoritmul folosete diferite mesaje pentru a descoperi i a menine legturi. Atunci cnd un nod ncearc i gsete o rut ctre un alt nod, acesta difuzeaz o Cerere de Legtur (RREQ) ctre toi vecinii si. Cererea de Legtur este propagat n reea pn cnd atinge destinaia

sau un nod cu o rut fresh ctre destinaie. Apoi legtura devine disponibil prin unicast RREP inapoi ctre nodul surs. Algoritmul folosete mesaje hello(RREP special) ce sunt difuzate n mod periodic ctre vecinii imediai. Aceste mesaje sunt advertismente locale n legtur cu prezena nodului n reea, i a vecinilor, folosind legturi ctre nodul ce difuzeaz vor continua s marcheze aceste legturi ca valide. Dac mesajele de hello nu mai sosesc de la un anumit nod, vecinii si vor presupune ca nodul s-a mutat n afara reelei, s marcheze legturile ctre acesta ca invalide, s trimit informaia mai departe la nodurile interesate printr-un mesaj de tip legtur ntrerupt(RREP special). Managementul tabelelor de rutare AODV necesit reinerea urmatoarelor informaii pentru fiecare cale:

Adresa IP a destinatarului (a nodului destinaie). Secvena numeric a destinatarului. Numrul de hop-uri pn la destinaie. Urmtorul hop: nodul ce urmeaz s trimit pachetele la destinaie pentru aceast cale. Timpul de via: timpul n care legtura este considerat valid. Lista vecinilor activi: vecinii ce folosesc legtura n reea Buffer de request: se asigur c o cerere este procesat o singur data.

Crearea legturii Un nod difuzeaz un mesaj RREQ atunci cnd are nevoie de o cale ctre o destinaie, i nu exist una disponibil. Asta se poate ntmpla dac acea cale ctre destinaie este necunoscut, sau dac o legatur valid anterior expir. Dup difuzarea RREQ, nodul ateapt mesajul RREP. Dac raspunsul nu este primit ntr-o anumit perioad de timp, nodul poate s redifuzeze mesajul RREQ sau s presupun c nu exist o rut ctre acea destinaie. Nodul ce primete cererea creeaz o cale temporal ctre IP-ul sursei, i se pstreaz astfel ruta ctre nodul original care a fcut Cererea. Atunci cnd mesajul RREQ ajunge fie la destinaie, fie la un nod cu o rut valid ctre destinaie se genereaz un mesaj RREP i trimis napoi ctre nodul care a fcut Cererea. Ct timp mesajul RREP este forwardat n reea se realizeaz legtura ntre surs i destinaie, pentru c odat acesta ajuns la nodul ce a emis Cererea s existe o legatur valid ntre surs i destinaie. Meninerea legturii

Atunci cnd un nod detecteaz o legtur invalid ctre unul dintre vecinii si va elimina respectiva intrare i va trimite un mesaj de legtura ntrerupt ctre toi vecinii ce utilizeaz n mod activ acel traseu. n acest scop AODV pstreaz o list cu vecinii activi ce utilzeaz o anumit legatur. Nodurile ce primesc acest mesaj repet la rdul lor procedura. Mesajul va ajunge la un moment dat la sursa care poate alege s opreasc trimiterea de date, sau s cear o nou legatur. Avantajul AODV fa de protocoalele tradiionale de rutare este acela c reduce dramatic numrul mesajelor trimise n reea, prin folosirea abordrii reactive. AODV prezint deasemenea o abordare tradiional comparativ cu DSR (protocoale bazate pe rutarea la surs), lucru care faciliteaz legatura dintre reelele ad-hoc wireless i cele cablate precum Internetul de exemplu. Secvena numeric pe care AODV o folosete d informaii n legtur cu gradul de prospeime a unei anumite legturi. Aceasta elimin posibilitatea formrii buclelor, dar poate provoca la rndul ei probleme (n cazul n care nu este sincronizat cu reeaua de exemplu-n cazul partiionrii reelei). AODV suport o singur rut ctre o destinaie anume. Ar fi totui o mbuntire dezirabil, ca de fiecare dat cnd o legatur devine invalid s nu mai fie necesar cautarea unei noi rute, una deja existent s o inlocuiasc. Cu toate c mesajele n cazul invalidrii unei legturi sunt relativ reduse, trimindu-se exclusiv la nodurile implicate, la nivel de reea acelai nod poate primi informaia de mai multe ori(de la destinatari diferii) dac nodul indisponibil era implicat n mai multe legturi. O soluie de agregare ar putea mbunti protocolul. Protocolul AODV nu suport legturi unidirecionale. La primirea unui mesaj RREQ va stabili o legtur n sens invers ctre sursa folosind nodul care a generat Cererea. Dynamic Source Routing DSR Rutarea Dinamic la Surs face parte din clasa protocoalelor reactive, i permite nodurilor s descopere un traseu n mod dinamic n cadrul unei reele cu mai multe noduri ctre orice destinaie. Rutarea la surs presupune c fiecare pachet conine n header lista complet i ordonat a nodurilor pe care acesta trebuie s le parcurg. DSR nu folosete transmiterea periodic de mesaje, i obine astfel economie a puterii bateriei precum i evitarea ncrcrii reelei. n schimb, protocolul DSR are nevoie de suport din partea nivelului Mac (acesta i furnizeaz informaii n legtur cu legturile invalide). Stabilirea legturii Mecanismul prin care un nod X dorete s trimit un pachet nodului Y, i obine traseul ctre nodul Y. X cere o legtur prin difuzarea unui mesaj RREQ. Toate nodurile ce primesc acest pachet caut o rut ctre destinaia cerut n cache. DSR pstreaz toate rutele cunoscute n

cache. Dac nu se gsete nicio rut, pachetul(mpreuna cu adresa nodului) este trimis mai departe la nodurile vecine. Procedura contin pn cnd pachetul ajunge fie la un nod ce cunoate o legtur disponibil ctre destinaie, fie chiar la destinatar. Odat ajuns la destinaie este trimis napoi un pachet ce conine secvena de noduri din reea prin care se poate ajunge la destinaie. Calea ctre expeditor poate fi gsit n mai mute moduri. Cea mai simpl metod ar fi adoptarea cii inverse. Aceasta metod prezint dezavantajul c presupune legturile simetrice. Pentru rezolvarea acestui neajuns DSR verific cache-ul nodului ce trimite rspunsul. Dac se gsete o rut aceasta este folosit. O alt metod ar fi trimiterea unui mesaj(piggyback) ctre surs. Asta nseamn c protocolul DSR poate realiza rute corecte n prezena legturilor asimetrice(unidirecionale). O rut odat gasit este salvat n cahe cu o tampil de timp adecvat. Meninerea legturii. Mecanismul prin care un expeditor S detecteaz dac topologia reelei s-a schimbat i astfel nu mai poate folosi ruta ctre destinaia D. Asta s-ar putea ntmnpla dac un nod parsete reeaua sau este momentan nchis, invalidnd traseul. O legtur ntrerupt este detectat fie n mod activ monitoriznd reeaua, sau n mod pasiv prin informaii de la nodurile vecine care forwardeaz pachetul n locul nodului din cadrul traseului. Cnd se detecteaz o problem cu o rut utilizat, un pachet de eroare este trimis napoi la destinaie, iar nodul indisponibil este eliminat din cache-ul sursei, i toate rutele care l conin vor fi astfel trunchiate. DSR folosete avantajul rutrii la surs, nodurile intermediare nu necesit mentinerea informaiilor de rutare updatate pentru a ruta pachetul primit. Nu este necesar transmiterea de mesaje periodic, ceea ce reduce ncrcarea. Puterea bateriei este deasemenea conservat att prin netrimiterea de pachete cu informaii de control ct i prin neprimirea lor. Protocolul prezint avantajul c afl rutele prin scanarea pachetelor de informaii deja primite. O rut de la A la C prin nodul B presupune ca A s afle despre ruta ctre C, dar i despre ruta ctre B. Deasemenea B va afla de ruta ctre A si C, iar C despre ruta ctre A si B. DSR ofer deasemena suport pentru legturile unidirecionale, prin folosirea mesajelor piggyback, dar este necesar ca nivelul MAC s suporte asta. n cazul unei reele cu multe legturi uni-direcionale performanele pot fi dramatic mbunatite. Zone-Routing Protocol ZRP Protocolul de Rutare Zonal este un protocol hibrid- att reactiv ct i proacvtiv. Acesta mparte reeaua n zone de rutare diferite i specific dou protocoale de rutare complet diferite care opereaza n interiorul sau intre zonele de rutare.

Protocolul de Rutare Intrazonal(IARP) opereaz n interiorul zonelor de rutare, i cunoate distana minim i rutele ctre toate nodurile din acea zona. Protocolul nu este definit, i poate include orice tip de protocol tradiional, sau oricte numere de protocoale tradiionale precum Vectorul Distan sau Starea Legturii. O schimbare a topologiei nseamn propagarea informaiei aferente doar n interiorul zonei implicate, i nu afecteaz intreaga reea. Al doilea protocol, Protocolul de Rutare Interzonal(IERP) este un tip de protocol reactiv i este folosit la gsirea traseelor ntre diferitele zone de rutare. Acesta este folositor dac nodul destinaie nu se afl n zona de rutare. Protocolul difuzeaz o Cerere de rutare ctre toate nodurile de grani din zona de rutare, iar acestea trimit cererea mai departe dac nodul destinaie nu se afl n zona lor de rutare. Procedura se repet pn cnd este gasit nodul destinaie i un pachet este trimis napoi de la destinaie ctre surs indicnd traseul disponibil. Zona de Rutare O zon de rutare este definit ca un set de noduri aflate la o distan maxim fat de nodul discutat(distanta ca numr de hop-uri). Aceast distant este definit ca raza zonei. Nodurile periferice sunt noduri a cror distan fa de nodul discutat este egal cu raza zonei.. n figur nodurile B i F sunt noduri de grani pentru S. Considernd reeaua din figur, Nodul S vrea s trimit un pachet nodului D. Cum D nu se afl n zona de rutare a nodului S acesta trimite o Cerere de rutare ctre nodurile de grania B si F. Fiecare nod (B si F) verific dac D se afl n zona lor de rutare, altfel trimit mai departe cererea de rutare ctre nodurile lor de grani. F trimite cererea ctre S,B,Csi H n timp ce B trimite cererea ctre S,F,E si G. Nodul cerut D se afl n zona de rutare att a nodului C ct i a nodului E, se genereaza astfel rspunsul ctre nodul surs S.

Fig. 3: Protocolul de rutare ZRP-grupuri de noduri

Pentru a preveni situaia n care Cererea ar ajunge din nou la noduri la care a fost deja se foloseste o lista a Procesrilor Cererilor. Acesta list conine cererile procesate anterior, iar dac un nod primete o cerere ce a mai fost procesat, aceasta este pur i simplu ignorat. ZRP este un protocol foarte interesant care poate fi adaptat la condiiile reelei n care se opereaz(se poate schimba diametrul zonei de rutare). Din pcate aceast alegere nu poate fi fcut dinamic(se alege de administrator sau de producator), iar performanele protocolului depind foarte mult de acest parametru. Datorit faptului c acest protocol este unul hibrid, se bucur de avantaje multiple: rutele sunt gsite repede n interiorul zonelor de rutare, iar n afara zonelor de rutare cutarea poate fi eficientizat prin alegerea inspirat a nodurilor interogate. ZRP limiteaz propagarea informaiilor n legtur cu modificarea topologiei la vecinii direct implicai(nu este ncrcat ntreaga reea cu informaii atunci cnd o schimbare se produce), cu toate c o schimbare a topologiei poate afecta mai multe zone. Temporally Ordered Routing Algoritm TORA Algoritmul de Rutare Ordonat Temporal este un algoritm de rutare distribuit.TORA a fost conceput pentru a minimiza reaciile la schimbrile frecvente de topologie. Un concept ce st la baza design-ului su este acela c mesajele de control implic n general un numar mic de noduri. Garanteaz c nicio rut nu prezint bucle (bucle temporare s-ar putea totui forma), i n general asigur mai multe rute pentru o pereche surs-destinaie. Acest protocol furnizeaz doar mecanismul de rutare, i depinde de IMEP(Internet MANET Encapsulation Protocol) pentru alte funcii. TORA poate fi separat n trei funcii principale: crearea traseelor, meninerea legturilor , i stergerea legturilor. Crearea rutelor se bazeaz pe asignarea de direcii legturilor, ntr-o reea unidirecional (sau sub-reea unidirecional), construind un graf aciclic direcionat (DAG) cu destinaia ca rdcin.

Fig 4: Graf aciclic direcionat pentru un anumit nod din rea

TORA asociaz un grad fiecarui nod din reea. Toate mesajele n reea circul de la un nod cu rang mai mare ctre un nod cu rang mai mic. Rutele sunt descoperite flosind pachete de tip Query sau Update. Cnd un nod fr legturi inferioare necesit o legatur ctre destinatie, acesta va difuza un pachet Query. Pachetul QRY va circula n reea pn cnd va ajunge la un nod ce are o rut ctre destinaie, sau chiar la destinaie. Acel nod va difuza apoi un pachet Update ce conine gradul nodului. Orice nod primete acest pachet ii va seta gradul la o valoare mai mare dect a nodului de la care provine pachetul. Nodul va difuza apoi propriul pachet UPD. Procedura va conduce la crearea unui numar de legturi directe surs-destinaie. Internet MANET Encapsulation Protocol-IMEP IMEP este un protocol conceput s suporte operarea mai multor protocoale n cadrul reelelor adhoc. Ideea ar fi s existe un protocol comun general de care toate protocoalele de rutare s se pat folosi.Acesta ncorporeaz mai multe mecanisme comune de care un protocol de nivel superior ar putea avea nevoie. Dintre acestea:

Sesizarea strii legturii Agregarea i ncapsularea mesajelor de control Fiabilitatea difuzrii Proceduri de securitate prin autentificarea inter-router

IMEP furnizeaz deasemenea o arhitectur pentru identificarea routere-lor n cadrul reelelor MANET, identificarea interfeei i adresare. Scopul acestui protocol este acela de a imbunati per total performanele prin reducerea numrului de mesaje de control i punerea unei funcionaliti comune ntr-un protocol unificat, generic folosit n cadrul tuturor protocoalelor de rutare de nivel superior.

Fig 4: IMEP integrat n cadrul unui protocol de rutare

Dintre protocoalele prezentate doar TORA i OLSR folosesc IMEP, dar trebuie precizat c aceste protocoale au fost dezvoltate de acelai autor. IMEP genereaz o suprancrcare semnificativ n principal datorit mecanismului de descoperire a vecinilor care trimite cel putin un mesaj hello pe secund, dar i datorit fiabilitii pe care o ofer n ceea ce privete livrarea pachetelor. Cluster Based Routing Protocol CBRP Ideea ce st n spatele CBRP este aceea de a mpri nodurile unei reele ad-hoc ntr-un numr de grupuri disjuncte sau nedisjuncte. Un nod este ales liderul unei astfel de grupri. Liderul grupului menine informaia n legtur cu grupul respectiv. Rutele inter-grup(n interiorul grupului) sunt gsite n mod dinamic folosind informaia respectivului grup. CBRP este bazat pe rutarea la surs, similar cu DSR. Rutarea intra-grupuri(intre diferitele grupuri) se face prin inundarea reelei (flooding) cu mesaje de tip RREQ, i asta presupune ca grupurile de noduri s nu fie foarte mari, altfel ncarcarea ar putea fi semnificativ. CBRP este un protocol n ntregime distribuit, lucru necesar datorit topologiei foarte dinamice a reelelor ad-hoc. Ba mai mult, acest protocol ia n considerare existena legturilor unidirecionale. Sesizarea strii legturii Fiecare nod i cunoate legturile bi-direcionale ctre vecinii si, precum i legturile unidirecionale ale vecinilor ctre el. Pentru asta, fiecare nod trebuie s menin un tabel al vecinilor precum cel prezentat:ID vecin Vecin1 Vecin 2 .... Vecin n Starea legturii Legtura bi/unidirecionala ctre mine Legtura bi/unidirecionala ctre mine ... Legtura bi/unidirecionala ctre mine Rol Este Vecinul 1 un membru sau capul unui grup Este Vecinul 1 un membru sau capul unui grup .... Este Vecinul 1 un membru sau capul unui grup

Tabel 1: Tabelul cu informatii detinut de fiecare nod in cadrul protocolului CBRP Fiecare nod difuzeaz n mod periodic tabelul su ctre vecini ntr-un mesaj hello. Mesajul hello conine Id-ul nodului, rolul nodului(membru, lider sau indecis) i tabelul de vecini. Aceste mesaje sunt folosite pentru a updata tabelele fiecrui nod. Dac din partea unui nod nu se primeste mesaj hello, acea intrare asociat lui va fi eliminat din tabel.

Grupurile

Algoritmul de formare a grupurilor este foarte simplu: nodul cu cel mai mic ID este ales ca lider al grupului. Nodurile folosesc informaiile din mesajele hello pentru a sti dac sunt sau nu lider de grup. Un lider de grup consider membrii ai grupului toate nodurile ce au legturi bidirecionale cu el. Un nod se vede ca membru al unui anumit grup dac are o legtur bidirecional cu liderul grupului. Este posibil ca un nod s aparin mai multor grupuri.

Fig. 5: Grupuri conectate bidirecional Grupurile sunt identificate prin liderii lor. Algoritmul cel mai mic ID nu este unul strict, un membru al grupului nu va revendica niciodat poziia de lider, dac exist un lider al grupului. Doar dac doi lideri devin apropiai geografic unul dintre ei va pierde poziia de lider. Routarea n CBRP se bazeaz pe rutarea la Surs, iar stabilirea traseului se face prin inundarea retelei cu mesaje ROUTE Request (RREQ). Noiunea de grup presupune totui c puine noduri vor fi deranjate, asta pentru c doar liderii vor primi mesajele difuzate.Daca nodul X necesit o legtur ctre nodul Y acesta trimite o cerere RREQ cu o list de rutare ce l include doar pe el iniial. Orice nod trimite pachetul mai departe adaug propriud ID la cererea de ruatre. Fiecare nod trimite cererea mai departe o singur dat, i niciodat unui nod care apare deja n lista de rutare. Protocolul are trsturi comune protocoalelor discutate anterior. Procedeul de stabilire a traseului i eliminare a unei anumite rute asemantoare cu protocoalele DSR i AODV. Soluia gruprii este una mai scalabil dect a altor protocoale, datorit limitrii numrului de mesaje ce trebuie trimise. CBRP mai prezint i importantul avantaj c utilizeaz legturi unidirecionale. Singura ntrebare ce rmne este ct de mare o grupare de noduri poate fi, acest parametru fiind critic pentru funcionarea protocolului.

3.3.

Comparaie

Dup cum se vede din tabelul comparativ niciunul dintre protocoale nu suport conservarea de putere, sau QoS. Aceste protocoale sunt ns n curs de dezvoltare, deci asemenea funcionaliti vor fi probabil adugate ulterior. Toate protocoalele discutate sunt distribuite, niciunul dintre ele nu depind de un nod central, ceea ce nseamna c se pot n mod facil reconfigura n cazul schimbrilor de topologie. DSDV Far bucle de rutare Mai multe cai Distribuit Reactiv Suport pentru legturi unidirecionale Suport QoS Multicast Securitate Conservare a puterii Broadcast periodic Fiabilitatea datelor transmise DA NU DA NU NU AODV DA NU DA DA NU DSR DA DA DA DA DA ZRP DA NU DA Partial NU TORA/IMEP Cu bucle de rutare temporale DA DA DA NU CBRP DA DA DA DA DA

NU NU NU NU DA NU

NU DA NU NU DA NU

NU NU NU NU NU NU

NU NU NU NU DA NU

NU NU NU NU DA(IMEP) DA

NU NU NU NU DA NU

Aceste protocoale au fost mbunataite n timp, iar la ele se adauga mult altele. Reelele ad-hoc sunt un domeniu n plin dezvoltare datorit saltului tehnologic al dispozitivelor de tip laptop sau PDA, iar mediul radio i experimentele numeroase desfaurate conduc la imbuntirea permanenta a acestor protocoale dezvoltate n mod deosebit pentru astfel de retele. Pentru retelele wireless s-a stabilit standarul IEEE 802.11 care reda parametrii sub care functioneaza acest tip de retele. Standardul IEEE 802.11 face parte din grupul standardelor 802.x LAN (ex: 802.3 Ethernet sau 802.5 Token Ring). Acesta specific nivelul fizic i de acces la mediu adaptat cerinelor speciale ale WLAN.

Scop: specificarea unui WLAN simplu i robust care s ofere servicii asincrone limitate n timp Nivelul MAC(Medium Access Control)trebuie s fie capabil s opereze cu niveluri fizice multiple. La nivelul fizic se pot utiliza tehnicile de transmisie IrDA i radio cu spectru mprtiat Caracteristici adiionale ale WLAN: suport al managementului puterii pentru a economisi baterie manipularea nodurilor ascunse i posibilitatea operrii globale banda ISM de 2,4 GHz a fost aleas pentrustandardul iniial debitele avute n vedere iniial au fost de 1 2 Mbii/s mbuntiri: 802.11a (54 Mbii/s 5 GHz), 802.11b (11 Mbii/s)

4.

Concluzii

Domeniul reelelor wireless este unul n plin dezvoltare. Bazat pe avantajele pe care aceste tipuri de reele le prezint se identific interesul clar n dezvoltarea lor. AVANTAJE: Flexibilitatea Undele radio pot penetra pereii, dispozitivele de emisie i recepie putnd fi plasate oriunde, chiar fr vizibilitate ntre ele. Planificare Reelele wireless permit comunicarea fr un plan prestabilit, atta timp ct utilizeaz aceleai standarde, n timp ce reelele ce folosesc cabluri au nevoie de o schi a cablrii, cabluri, uniti de interconectare etc. Proiectare reelele wireless permit proiectarea i realizarea de dispozitive de dimensiuni mici (de buzunar) Robustee reelele wireless pot rezista dezastrelor (cutremure), oamenii vor putea comunica i n condiii dificile dac dispozitivele wireless rezist. Costul accesul unui utilizator nou la infrastructura unei reele WLAN deja format nu mai implicnici un cost suplimentar

DEZAVANTAJE Calitatea serviciului WLAN ofer de obicei o calitate mai slab dect reelele cablate, banda mai ngust datorit limitrilor din transmisiile radio (1 10 Mbii/s fade 100 1.000 Mbii/s), rata erorilor ridicat datorit interferenelor (104 fa de 1012la fibr optic),timp de ntrziere mai mare datorit mecanismelor de detecie i corecie a erorilor. Soluii particulare Datorit procesului lent de standardizare, multe companii au venit cu idei proprii oferind funcionaliti standard, dezvoltnd n acelai timp funcionaliti noi (un debit superior folosind tehnologii de codare patentate). mbuntirile astfel aduse sunt utilizabile doar dac toate adaptoarele din nodurile wireless provin de la acelai productor. Sigurana i securitatea Undele radio utilizate pentru transmisiile de date pot interfera cu alte componente hightech(aparatur medical din spitale), receptorul i transmitorul pot fi utilizate de nespecialiti, deci radiaiile trebuie s fie sczute. Toate standardele trebuie s ofere soluii de criptare, suport pentru anonimat Restricii Toate produsele wireless trebuie s corespund regulamentelor naionale. WLAN sunt limitate de puterea emitorului i de benzile de frecvene cu acces liber, care nu sunt aceleai peste tot n lume

Scopul retelelor wireless este acela de a nlocui cablurile, de a permite accesul fr limite la internet si de a permite o flexibilitatea mai mare a reelelor ad-hoc. Aceast pia n plin dezvoltare introduce tehnologia wireless n birouri, case sau medii de producie. WLAN sunt restricionate la perimetrul cldirilor, al unui campus sau chiar al unei camere ele funcioneaz independent, nu necesit o reea la scara larg.

5.

Bibliografie

I.

Tony Larsson, Nicklas Hedman, Routing Protocols in Wireless Ad-hoc Networks- A Simulation Study, -Masters Thesis 2008 Yih-Chun Hu, David B. Johnson, Adrian Pering, SEAD: Secure efficient Distance Vector Routimg for mobile wireless ad hoc networks, Elsevier 2003 Zygmunt j. Haas, Articolul Secure Routing for Mobile Ad-hoc Networks, ianuarie 2002 Elisabeth M. Royer, Charles E. Perkins, Articolul Ad-hoc On-Demand Distance Vector Routing, www.elsevier.com/locate/adhoc J. P. Macker, M. S. Corson, An Overview of the IEEE 802.11 Standard, Mobcom 2000 Jie Wu, Ivan Stojmenovic, Ad-hoc Networks IEEE Computer Society , februarie 2004

II.

III.

IV.

V.VI. VII.