Calcul mobil

Si problemele specifice

Limitarile dispozitivelor mobileImplicatiile portabilitatii pentrudispozitivele mobile sunt

marimile

greutatile reduse

dependenta de puterea bateriei.

Memoria limitata

Bateriile sunt printre cele mai mari dispozitivein greutate intr-un nod mobil.

Consumul de putere este proportional cu CV2f,

C este capacitanta dispozitivelor si conexiunlorinter-dispozitive,

V este variatia voltajului,

f este frecventa de ceas.

Puterea poate fi economisita

(1) crescand nivelul de integrare VLSI astfelincat sa scada C,

(2) reproiectand cip-urile sa lucreze la unvoltaj V mai redus

(3) reducand frecventa de ceas dinamicpentru a negocia viteza de calcul pentrueconomia de putere.

Transmisia wireless, receptia,retransmisia si operatiile deavertizare, toate acestea consumaputere.

Multe protocoalele de routareexistente folosesc transmisiiperiodice ale mesajelor de updatare arutei pentru a mentine acurateteatabelei de rutare.

Proprietatile sistemului distribuit mobil

Disponibilitate

confidentialitate

De asemenea, este necesara o a treia parte, de ex.Certificatin Authority, pentru managementul cheii saucheile trebuie sa fie transmise anticipat.

Integritatea.

Securitatea.

Contextul

In retelele cablate, adresarea clasica acomunicatiei se face ascunzand layer-ulde inferior al comunicatiei, pe caremajoritatea metodelor de tratare aerorilor nu l-ar lua in considerare(reamintim ca petru retelele cablate,erorile de legatura si host suntconsiderate a fi evenimente foarte rare).

Astfel, a aparut o tendinta opusa, de ex.,expunerea evenimentelor unei retele mobileaplicatiei, care trebuie sa fie responsabila cutratarea evenimentelor.

Mergand mai departe, aplicatiile si-au datseama de mediul inconjurator in carefunctioneaza si trebuie sa fie capabile sa seadapteze la el.

Retele senzor

Retele senzor reprezinta o categorie aparte aretelelor ad hoc.

Perceperea datelor inconjuratoare esterealizata prin efortul comun al unui numar marede noduri senzor, effort ce consta in perceperea,procesarea datelor si comunicareacomponentelor.

Pot fi amplasate aleator pe terenuriinaccesibile, precum operatiuni pe terenaccidentat, deci protocoalele si algoritmiiretelei trebuie sa detina capacitate de auto-organizare.

Diferente intre R. Senzor si R. Clasice

1.Numarul de noduri senzor intr-o reteasenzor poate fi mai cu magnitudine maimare de cateva ori.

2.Nodurile senzor sunt amplasatecompact.

5. Nodurile senzor pot sa nu aibaidentificare globala.

6. Mobilitatea senzorului poate fi limitata.

In timp ce retelele traditionale tind saatinga calitate a dispozitii ale serviciilorfoarte inalte (high quality of serviceQoS), protocoalele de retea senzortrebuie sa se concentreze in principalpe conservarea puterii.

Modele de mobilitate

Cercetatorii au propus mai multe schemepredictive de mobilitate pentru a preziceviitoarea disponibilitate a link-urilorwireless.

Ca istoric, primele modele demobilitate utilizate pentru retelele adhoc au fost variante ale modeluluirandom-walk, care defineste miscarileindividuale ale nodului si este bazat pedirectii si viteze intamplatoare(random).

Intr-un muzeu, vizitatorii merg cupasi diferiti si pe traiectorii diferite,varind in functie de obiectele lor deinteres, dar mobilitatea paternurilortinde sa se focalizeze in punctelecomune de interes, cum ar fipictura.

Se poate observa ca miscarile nodurilorbazate pe grup (group-based) cauzeazapartitionarea retelei.

Sa consideram o retea ad hoc formatadin mai multe miscari de grup, a careinoduri sunt initial dispersate siamestecate; paternul de miscare distinctal fiecarui grup cauzeaza separareagrupurilor si in final, partitionarea retelei.

in timp ce miscarile independente ale unuisingur nod pot cauza doar rupereasporadica si la intamplare a link-urilor.

S-a aratat ca atitudinea mobilitatii de grupa utilizatorilor mobili cauzeaza partitionareafrecventa a retelelor, iar partitiile rezultatesunt miscari separate de grup.

De exemplu, la timpul t , locatia unui nod iintr-un grup j este data de urmatorii vectoride pozitie: 1. loc de referinta Yj(t);

2. dizlocare locala Zji(t);

3. locul nodului Xji(t)=Yj(t)+Zji(t).

Modeluil RPGM genereaza locatia fizica a nodurilor mobile, dar utilizarea ei poate sa nu identifice cu acuratete grupurile mobile.

De exemplu, sa consideram o topologie a reteleigenerata de modelul RPGM unde exista catevagrupuri mobile cu punct de referinta comun si cu arii de acoperire suprapuse.

Protocoale de routare ad-hoc

Datorita gradului limitat de transmisie alinterfatelor retelelor wireless, pot finecesare mai multe hop-uri pentru aschimba date intre noduri in cadrulaceleiasi retele.

Protocoale proactive

In protocoalele proactive, fiecare nodmentine unul sau mai multe tabele petru astoca informatii de routare.

Aceste informatii sunt tinute up-to-date cuajutorul schimbului de mesaje periodic. .

Destination-Sequenced (DSDV)

Protocoloul de routare vector-distanta sebazeaza pe mecanismul de routare Bellman-Ford, care a fost imbunatatit pentru a evitabuclele in tabelele de routare.

Fiecare nod din reteaua mobila mentine otabela de routare pentru toate destinatiileposibile din retea.

Clusterhead Gateway Swich Routing (CGSR)

Protocolul se bazeaza pe DSDV, darsolicita o structura a retelei inghesuita(clustered) si foloseste catevascheme de routare euristice.

In fiecare cluster un nod este ales casi cluster head initialinzand unalgoritm de selectie a cluster head-ului.

Protocoale reactive

Protocoalele reactive presupun o abordarediferit , crend rute doar la cererea noduluisurs .

Atunci cnd un nod doreste o rut ctre odestinaie , iniiaz un proces dedescoperire a rutei, care este terminatatunci cnd este gsit o rut sau toatepermutrile dintre rute au fost examinate .

Protocolul Dynamic Source Routing (DSR)

Este bazat pe pe conceptul rutrii sursei .

Cnd nodul primete un pachet de cerere arutei (coninnd adresele nodurilor surs idestinaie) , acesta verific dac tie dejacalea spre destinaie , i , dac nu , adaugpropria adres la route record-ul coninut npachet i nainteaz pachetul spre celelatelink-uri ale sale .

Un dezavantaj al acestui protocol este csufer o problem de scalabilitate datoratnaturii procesului de source routing .

Odat ce reeaua devine mai mare ,pachetele de control ..

Ad Hoc On-Demand Distance Vector(AODV )

Protocolul de rutare se bazeaz pealgoritmul DSDV i minimizezredundana acestuia crend rutenumai la cerere .

n locul rutrii sursei , AODV sebazeaz pe intrrile din tabelelegenerate dinamic n nodurileintermediare.

Un pachet unidirecional(RREP) estetrimis ctre surs permind fiecruinod din cale s stabilesc un forwardpointer ctre nodul de la caresosete pachetul RREP .

Algoritmul Temporally Ordered Routing (TORA)

Algoritmul este bazat pe conceptul deinversare a link-ului i opereaz ntr-oreea cu un grad nalt de mobilitate .

Conceptul cheie al TORA estelocalizarea mesajelor de control la unset mic de noduri din apropierealocului n care se produce omodificare topologic .

Associativity-Based Routing (ABR)

Protocolul folosete ca unitate de msurgradul stabilitii asociativittii .

Fiecare nod genereaz periodic un semnalde control pentru a indica vecinilor prezenasa .

Pentru fiecare semnal primit , contorulasociativ al nodului curent este incrementat.

Toate nodurile care primesc mesajulde interogare i asociaz propriaadres i contorul de asociativitate lamesaj .

Un nod succesor va terge contorulvecinului su din aval cu excepiaintrrii referitoare la el nsui .

Signal Stability-Based Adaptive Routing (SSR)

Protocolul selecteaz ruta pe bazaputerii semnalului ntre noduri istabilitatea locaiilor nodurilor pentru aalege ruta cu cea mai puternicconectivitate .

Puterea semnalului este stabilit printestarea link-urilor cu nodurile vecine .

Protocoale hibride

Protocoalele de rutare ad-hoc hibridecombin rutarea local proactiv curutarea global reactiv pentruatingerea unor eficiene i scalabilitimai nalte .

n cadrul Zone Routing Protocol (ZRP), procesul de descoperire a rutei esteiniiat la cerere .

Protocoale bazate pe pozitie

Protocoalele bazate pe poziie necesitdisponibilitatea informaiei desprepoziionarea fizic a nodurilor ad-hoc.

Fiecare nod i poate determina propriapoziie prin GPS sau o alt metod delocalizare.

Rutarea bazat pe poziie nu necesitstabilirea sau meninerea rutelor.

Un avantaj n plus este c acesterutine suport trimiterea pachetelorctre toate nodurile dintr-o zongeografic dat.

LAR presupune c transmitorulcunoate localizarea destinaiei iviteza de transmitere .

Pe baza acestei informaii se poatedefini o zon estimat a destinaiei .

De exemplu n proiectul Terminodesse combin rutarea ierarhic i rutareabazat pe poziie ntr-o ierarhie pedou niveluri.

Pachetele sunt rutate conform unuivector de distan proactiv pentrudistane mici i printr-o abordarereactiv greedy-position pentrudistane mari (Anchored GeodesicPacket Forwarding).

Fiecrui nod i se cere s-icunoasc propria poziie .

Pentru cazul n care nu estedisponibil un serviciu GPS , sepropune un Self PositioningAlgorithm(SPA).

De aceea, dac toate nodurile nuaparin unei aceleiai entitiadministrative, utilizatorii tind s fieegoiti : folosesc serviciile oferite de aliidar nu ofer la rndul lor serviciicomuitii.

Protocoale care in cont de consumul de energie

Trebuiesc eliminate pe ct posibilcoliziunile cu stratul MAC carepresupun efectuarea unorretransmisii cu consecine asupraconsumului de energie.

Un exemplu n acest sens esteprotocolul EC-MAC .

Rutarea n reele deconectate

O abordare a tratrii reelelordeconectate ad-hoc este de a lsagazda mobil s atepte pasivreconectarea la reea.

Acest lucru poate duce la ntrzieriinacceptabile propunndu-se nacest sens limitarea acestora prinexploatarea i controlareamobilitii nodului .

Vahdat i Becjer propun unprotocol epidemic pentru reeleledeconectate.

Mecanismul de rutare deriv dinalgoritmii epidemici care oferconsiten bazelor de datereplicate fr a fi nevoie dedisponibilitatea unei anumite replicila un anumit moment de timp.

Un dezavantaj al acestei abordri estenecesitatea unei capaciti sporite debuffer-izare.

Chatzigiannakis propune un protocolarpe , n care o secven de purttorimperecheai de mesaje asemnatoriunui arpe se mic ntr-un moddeterminat de capul arpelui.

Rutarea bazat pe ageni n reele ad-hoc

Amin i Mikler propun un algoritmnumit Agent-based Distance VectorRouting (ADVR) .

Pentru fiecare sesiune , numrul demesaje schimbate n reea estelimitat de numrul de ageni prezenin reea.

Aceast strategie de migrarefolosete o combinaie de deStigmergy , ca form de comunicareindirect , i o cutare n adncime .

Stigmergy este un mecanism princare insectele comunic ntre ele nfuncie de schimbrile de mediu.

Broadcasting i multicasting deficitar

Protocoale pentru problemabroadcasting-ului i multicasting-uluideficitar.

Acestea nu ofer siguran n sensulc un mesaj poate fi pierdut dactopologia reelei se schimb ntimpul unui proces multicasting

Simple Flooding

Probability Based Methods

Area Based Methods

Neighbor Knowledge Methods

Zhou i Sing propun o varianta numitContent Based Multicasting (CBM)pentru reelele ad-hoc.

In CBM , coninutul datelor care suferun proces multicasting mpreun cumobilitatea receptorilor determin setulmulticasting.

Receptorii trag apoi informaia dela nodurile din calea acesteia.

Protocolul presupune maparea imprirea zonei de operaii nregiuni .

Serviciul de apartenenta la grup

Un protocol de apartenenta la grup seocupa cu formarea si intretinerea unuiset de procese care formeaza un grup.

In general, un proces poate parasi ungrup din cauza ca a esuat, din cauza caa cerut sa paraseasca grupul sau dincauza ca a fost eliminat fortat de catrealti membri ai grupului. In mod similar,un proces poate deveni membru al unuigrup

(ex: in urma unei selectii pentru a jucarolul de replica pentru un alt proces dingrup).

Problema Consensului

Aceasta problema nu poate firezolvata in mod deterministic insisteme asincrone, chiar in cazul incare comunicarea este buna, unsingur proces poate esua, iar aceastase poate intampla numai prin aparitiaunei erori.

1. in apartenenta la grup,

2. consensul

Totusi, pentru pentru cazul serviciilorapartenente la grup care urmaresc samentina o imagine unica in acord acomponentei curente a grupului, s-ademonstrat ca apartenenta la grup nu esterezolvabila deterministic in sistemeasincrone in care comunicarea este fiabilasi in care cel mult un proces poate terminaanormal

Pentru a evita acest rezultat deimposibilitate, au fost propuseasa numitele servicii deapartenenta la gruppartitionabile.

Astfel de servicii de apartenenta lagrup admit separarea grupului(ex: cand reteaua se partitioneaza)si reunirea grupului (ex: candcomunicarea intre partitii esterestaurata).

Cristian propune trei specificatii deapartenenta la grup pentru modelulasincron temporizat cu trei garantiide consistenta diferite:

intelegerea in grup,

intelegerea majoritatii si

intelegerea stricta.

Procesele schimba mesaje prinintermediul unui sistem de comunicarede tip datagrama.

Mesajele se pot pierde si intarzierilemesajelor sunt nemarginite, dar, cele maimulte mesaje ajung la destinatie intr-oconstanta de intarziere bine definitapentru comunicare uni-directionala, d.

Pentru ceasurile hardware sepresupune modelul de defectareaprin terminare anormala si, in plus,un proces care nu s-a incheiat eronatare un ceas hardware corect.

Cand intarzierile de programaredepasesc s, serverele sufera de scaderide performanta.

Astfel, serverele au un model dedefectare de tip eroare/performanta.

sDs

Doua procese p si q sunt conectate intr-un interval de timp [t, t] daca sunt corecte(ex: nu au terminat anormal si sunttermporizate) si orice mesaj trimis intre elein [t, t - ] ajunge la destinatie in limita a unitati de timp.

De remarcat, ca orice pereche de procesese poate afla in unul si numai unul dinmodurile anterioare.

Un set de procese care sunt conectate douacate doua formeaza o partitie fizica.

De remarcat ca un sistem stabil constain una sau mai multe partitii fiziceseparate.

Se presupune ca sistemul alterneazaintre lungi perioade de stabilitate siperioade comparativ scurte deinstabilitate, ex: comunicarea asincronapoate fi stabilita in marea majoritate atimpului.

Perioadele de instabilitate tranzitionalasau mai multe perioade de deconectareintre diferite parti ale retelei pot rezultain crearea mai multor grupuri paralele.

Doua grupuri G si G sunt considerate paraleledaca nici unul dintre ele nu este succesorulceluilalt. Procesele p si q sunt partitionate (logic)la momentul t daca intra in componenta a douagrupuri paralele diferite la momentul t.

Un grup G este un grup majoritar daca setulmem(G) al membrilor sai contine majoritateamembrilor echipei P, adica

2)(

PGmem

Generic vorbind, cand un grup Geste instalat pe un proces p, peste informat asupra grupuluiprecedent pred(q, G) al fiecaruiproces q care este membru al lui

In acest caz, ei ar fi putut aplicaupdate-uri conflictuale asupra starilorlor locale si astfel, ar fi putut devia.

Daca se detecteaza devierea destare, starea initiala a noului grup Gtrebuie sa rezolve update-urileconflictuale.

Probleme de autostabilizare

Dolev and Schiller propun unalgoritm aleator pentruimplementarea unui serviciu deapartenenta la grup auto-stabilizant in sisteme asincrone.

Un proces poate trimite un mesajcatre toti vecinii lui intr-o singuraoperatie de comunicare.

Procesele pot sa termine anormalsi sa isi revina in timpul executiei.

Problema partitionariiPrin natura lor, aplicatiile de retea pentrucalcul mobil implica o cooperare intre maimulte situri.

Pentru aceste aplicatii, caracterizate decerinte fiabilitate si reconfigurabilitate,posibila partitionare a retelei decomunicare este un aspect extrem deimportant al mediului.

In mod intuitiv, partitiile corespund unuinumar maximal de componente conectateale grafului logic care reprezinta relatiade accesibilitate intre procese.

Astfel, ele pot fi definite doar in contextulunor primitive de comuncatie specifice.

Natura partitionarii vadetermina calitatea aplicatiei infunctie de ce servicii suntdisponibile, unde si la ce nivelede performanta.

Reducerea si degradarea serviciilordepind in mod esential de semanticaaplicatiei.

Pentru anumite clase de aplicatii cuconstrangeri severe de consistenta, sepoate ajunge la cazul in care toateserviciile sa fie suspendate complet intoate partitiile, cu exceptia uneia.