3.3 Nivelul de reţea
Într-o reţea multihop, nodurile intermediare trebuie să transmită pachete de la sursă la destinaţie. Nodurile intermediare trebuie să decidă cărui vecin de ordin 1 i sa va transmite informaţia, dacă nodul intermediar nu este destinaţia. Se folosesc tabele de rutare care enumeră vecinii cei mai semnificativi pentru retransmisia de pachete. Construcţia şi întreţinerea acestor tabele este sarcina protocoalelor de rutare.
Deoarece acest subiect a fost discutat pe larg într-o lucrare precedentă [24], vom face numai câteva consideraţii de ordin general.
Fig. 16 Exemplu simplu de tabele de rutare într-o topologie posibilă de WSN (S->D)
Cea mai simplă cale de transmitere a pachetelor este inundare reţelei prin transmiterea pachetului la toţi vecinii. Cât timp sursa şi destinaţia sunt în aceeaşi componentă interconectată a reţelei, pachetul va ajunge cu siguranţă la destinaţie. Pentru a evita circularea continuă a pachetelor şi broadcast stormurile, nodul trebuie să retransmită pachetul o singură dată, necesitând prezenţa unor mecanisme de identificare a sursei şi a secvenţei pachetului. Este de asemenea necesară implemantarea unei forme de expirare la nivelul pachetului (gen câmpul TTL la reţelele IP), pentru a evita propagarea nenecesară dacă destinaţia nu este disponibilă..
O alternativă la propagarea către toţi vecinii este transmisia pachetului către un vecin arbitrar. Această metodă, cunoscută în literatura de specialitate ca “gossiping” rezultă într-o traversare aleatoare a pachetului prin reţea către destinaţie. În mod clar, întârzierile sunt mari în acest caz. De fapt, floodingul şi gossiping-ul sunt două modalităţi extreme ale spaţiului de proiectare. Alternativ, sursa ar putea transmite mai multe copii ale pachetului pe căi aleatoare, sau fiecare nod intermediar ar înainta mai multe copii unui subset de vecini, utilizând un protocol de control topologic. Ultima modalitate se mai numeşte şi flooding controlat.
Aceste metode, deşi simplu de implementat produc performanţe foarte slabe, cauzate de ignorararea topologiei reţelei. Din această cauză se preferă utilizarea de protocoale de rutare complexe, a căror sarcină o constituie construcţia tabelei de rutare, identificarea vecinilor favorabili pe baza costurilor, şi forwardarea în consecinţă.
Construirea tabelelor de rutare e realizată de algoritmi specifici (în reţelele fixe, protocoalele sunt în general distance vector sau link-state Bellman-Ford/Dijkstra). Reţelele wireless necesită o abordare diferită: protocoale de rutare distribuite, cu overhead mic, autoconfigurabile şi rezistente la schimbări dese de topologie.
Rutarea ad-hoc a primit o atenţie ştiinţifică considerabilă, şi un număr mare de protocoale a fost conceput. Aceste protocoale se pot împărţi în protocoale conservatoare table-driven, proactive, care încearcă să menţină o informaţie corectă în tabelele de rutare şi protocoalele on-demand care construiesc tabela numai când pachetul e transmis unei destinaţii necunoscute. Graniţa între cele două tipuri nu este foarte strictă, şi o serie de protocoale hibride au fost implementate.
Protocoale table-driven: DSDV (Destination-Sequenced Distance Vector) [25]; CGSR (Clusterhead Gateway Switch Routing) [26] şi WRP (Wireless Routing Protocol) [27].
Protocoale on-demand: DSR (Dynamic Source Routing) [28]; AODV [29], TORA (Temporally Ordered Routing Algorithm) [30]; ABR (Associativity-Based Routing) [31] şi SSR (Signal Stability Routing) [32].
O problemă comună protocoalelor ad-hoc este necesitatea floodingului de mesaje de control pentru explorarea topologiei reţelei şi identificarea nodurilor destinaţie.
Desigur, protocoalele menţionate mai sus au ca obiectiv principal în implementare eficienţa energetică şi pornesc de la presupunerea că traficul de date nu are constrângeri legate de livrarea pachetelor. Creşterea interesului în aplicaţii care necesită o performanţă end-to-end garantată şi introducerea de senzori video pun probleme serioase protocoalelor actuale. Transmiterea cu succes a datelor în acest caz necesită un amangement al reţelei atât din punct de vedere al consumului energetic cât şi QoS.
3.3.1 QoS în reţelele de senzori
Protocoalele ce implementează scheme de asigurare a QoS-ului în reţelele de senzori au aplicaţii numeroase, incluzând urmărirea ţintelor în timp real, apariţia de evenimente importante în aplicaţia de monitorizare etc. Livrarea acestor tipuri de date necesită o lăţime minimă de bandă, cu întârzieri cât mai mici posibil. Este deci nevoie de un mecanism de diferenţiere al traficului pentru a se putea garanta un anumit tip de serviciu.
În literatura de specialitate, problema prioritizării traficului în reţelele de senzori este foarte puţin atinsă. Vom preciza pe scurt problemele puse de funcţionarea WSN în condiţiile aplicării unor protocoale ce ţin cont de QoS. În continuare, se enumeră câteva probleme ale arhitecturii nodului senzor cu scoaterea în evidenţă a implicaţiilor:
-
Dinamica reţelei: există 3 elemnte la baza reţelelor de senzori, mai exact nodurile, centrele de colectare şi evenimentele monitorizate. Majoritatea arhitecturilor constau din noduri senzor staţionare. Este câteodată necesar implementarea suportului pentru mobilitatea centrelor de colectare, dar stabilitatea devine o problemă, din cauza necesităţii rutării între noduri mobile. Evenimentul urmărit de reţeaua de senzori poate fi static (monitorizare) sau dinamic (detecţie şi urmărire). Monitorizarea evenimentelor statice permite reţelei o desfăşurare reactivă, generând trafic în momentul raportării. Monitorizarea evenimentelor dinamice necesită o raportare periodică şi generează un volum semnificativ de trafic ce trebuie rutat spre nodul colector.
-
Amplasarea nodurilor: desfăşurarea topologică este dependentă de aplicaţie şi afectează performanţele protocolului de rutare. Este deterministă (în cazul plasării manuale a nodurilor, se pot minimiza coliziunile şi se pot construi rute predeterminate) sau cu auto-organizare. În cazul formării topologiei în urma unei amplasări aleatoare, poziţia nodului colector sau a nodurilor de agregare este crucială dpdv energetic şi al performanţei. În special când distribuţia nodurilor nu este uniformă, optimizarea formării clusterelor devine crucială pentru o funcţionare eficientă energetic.
-
Comunicaţia inter nod: procesul de stabilire a rutelor este puternic influenţat de considerente energetice. Deoarece transmisia directă pe distanţe mari nueste oportună, de cele mai multe ori datele sunt transmise prin mai multe hopuri, ceea ce introduce un overhead seminificativ pentru managementul topologiei şi controlul accesului la mediu. Rutarea directă ar fi suficientă dacă nodurile s-ar afla în proximitate de nodul colector, dar de cele mai multe ori rutarea multi-hop este inevitabilă.
-
Modelul de transfer al datelor: depinzând de aplicaţia în care este folosită reţeaua de senzori, datele pot fi transferate către nodul colector în mod continuu, la apariţia unui eveniment, la cerere şi hibrid. În modelul continuu, fiecare nod transmite date periodic . În modelelel de transmisie la cerere şi la apariţie, transmisia de date e declanşată de apariţia unui eveniment sau de lansarea unei interogări de către nodul colector. Unele reţele aplică o combinaţie între cele două metode.protocolalele de rutare şi cele de nivel MAC sunt influenţate de modelul de livrare, în special în privinţa minimizării consumului şi stabilitatea rutelor.
-
Capabilităţile nodului: într-o reţea de senzori, fiecărui nod i se poate asocia cu o funcţionalitate specifică. În implementări timpurii, nodurile erau omogene din punct de vedere al resurselor energetice, puterii de calcul şi al capacităţilor de comunicaţie. Depinzând de aplicaţie, de cele mai multe ori un nod va fi dedicat unei funcţii particulare, cum ar fi retransmisie, analiză sau agregare, deoarece angajarea în mai multe sarcini distincte poate avea un impact major asupra consumului. Există două implementări care abordează problema: alegerea prin software a nodurilor centrale în urma rulării unui algoritm specific sau amplasarea de noduri superioare dpdv al sursei de alimentare, benzii şi memoriei disponibile, care vor asuma sarcinile liderilor de cluster.
-
Agregarea datelor: deoarece nodurile senzor pot genera o cantitate semnificativă de informaţii redundante, se poate implementa un sistem care să accepte pachete similare de la mai multe noduri şi să retransmită numai o copie, reducând astfel durata şi numărul de transmisiuni. Agregarea datelor este rezultatul utilizării de funcţii specifice, cum ar fi suprimarea duplicatelor, minim, maxim sau funcţii de mediere. Unele din aceste funcţii pot fi executate parţial sau total de orice nod senzor, permiţând nodurilor să reducă traficul din reţea. Având în vedere discuţiile din capitolul 2, şi anume faptul că este mai scump dpdv energetic să comunici decât să efectuezi calcule, se pot obţine optimizări ale consumului energetic la nivelul reţelei utilizând agregarea de date. Această tehnică a fost deja folosită într-un număr seminificativ de protocoale de rutare. Există şi implementări în care sarcina agregării este atribuită unor noduri specializate. Din păcate, agregarea complică protocolul MAC, deoarce eliminarea pachetelor redundante necesită arbitraj instantaneu la accesul la mediu. Din această cauza, sunt aplicabile numai protocoale bazate pe CSMA sau CDMA, ducând la o creştere în consum.
În continuare voi analiza problemele tehnice ale implementării QoS în reţelele de senzori.
Problemă de proiectare
|
Factori principali
|
Dinamica reţelei
|
Mobilitatea nodului, ţintei şi nodului colector
|
Amplasarea nodurilor
|
Deterministă sau ad-hoc
|
Comunicaţia inter-nod
|
Directă sau multi-hop
|
Modele de transfer a datelor
|
Continuă, declanşată de eveniment, la cerere, hibridă
|
Agregarea datelor
|
Internă reţelei (parţial/total) sau extern reţelei
|
Tabel 5. Problemele proiectării unei arhitecturi de reţea
3.3.2 Problemele implementării QoS în reţelele de senzori
În vreme ce abordările contemporane ale protocoalelor de rutare nu adresează congestiile traficului, rutarea cu QoS se face uzual prin rezervare de resurse într-o comunicaţie conecţie orientată, pentru a face faţă cerinţelor fiecărei conexiuni individuale. Deşi multe mecanisme de rutare a datelor prioritare prin mecanisme QoS au fost propuse şi implementate în reţelele terestre, acestea nu pot fi aplicate direct în reţelele fără fir din cauza caracteristicilor inerente ale mediului de propagare, care afectează calitatea legăturii şi resursele de bandă limitate. Din această cauză sunt necesare protocoale de rutare cu QoS pentru reţele ad Hoc, ce ţin cont de natura dinamică a reţelei.
Deşi reţelele de senzori au aceleaşi probleme de calitate a serviciului ca reţelele de date radio de uz general, caracteristicile specifice ridică probleme ce trebuiesc luat în calcul în momentul proiectării:
-
Limitările de bandă: o problemă tipică pentru reţele radio de uz general o reprezintă asigurarea lăţimii de bandă necesare pentru atingerea nivelului dorit de calitate. Limitările de bandă sunt o problemă presantă pentru reţelele de senzori. Traficul caracteristic e constituit dintr-o serie de pulsuri de pachete atăt cu necesitate de procesare în timp real cât şi fără. Alocarea benzii disponibile doar pentru traficul prioritar nu este o soluţie viabilă. Va fi deci necesar un compromis în calitatea audio/video pentru a putea transmite şi traficul neprioritar. Va fi necesar suplimentar utilizarea de rute multiple independente, pentru a împărţi fluxul de date şi a permite realizarea impunerilor de calitate. Construcţia de rute independente pentruu acelaşi flux este o problemă complicată în reţelele de senzori datorită limitărilor energetice, a puterii de calcul reduse precum şi datorită creşterii potenţiale a numărului de coliziuni pe rutele pe care se transmite informaţia.
-
Îndepărtarea redundanţei: după cum am precizat anterior, reţelele de senzori se caracterizează prin redundanţa multiplă a datelor generate. În cazul traficului nerestricţionat, îndepărtarea redundanţei este facilă, putând fi realizată cu funcţii similare celor de agregare. Agregarea datelor pentru traficul cu QoS este dificilă. Compararea pachetelor ce formează o imagine sau un stream video nu este o sarcină ce se poate executa cu puţine instrucţiuni, iar accesarea intensă a procesorului duce la creşterea consumului. Un set de reguli la nivel de senzor şi la nivel de sisem sunt necesare pentru a face agregarea datelor cu QoS fezabilă dpdv al puterii de calcul necesare. De exemplu, agregarea datelor ce formează un stream de imagini poate fi efectuată selectiv pe traficul generat de senzorii care au aceeaşi orientare, deoarece se poate considera că imaginile sunt foarte similare. Alt factor de considerat este volumul traficului prioritar într-un anumit moment. În cazul unui volum mic, poate fi mai eficientă oprirea agregării, deoarece suplimentul de trafic generat de aceasta poate ocupa o lăţime de bandă mai mare decât fluxul efectiv. În ciuda complexităţii agregării pachetelor de imagine şi video, recompensele în sensul performanţei reţelei, având în vedere dimensiunea pachetelor şi frecvenţei transmiterii acestora pot fi majore.
-
Compromisul între energia consumată şi întârziere: deoarece puterea de transmisie este proporţională cu pătratul distanţei (sau chiar mai mare în cazul unui mediu zgomotos sau în prezenţa terenului accidentat), reţelele wireless utilizează aproape exclusiv tehnici de rutare multi-hop. Deşi adăugarea de staţii intermediare scade semnificativ puterea consumată pentru colectarea datelor, are ca efect secundar creşterea întârzierilor cumulative ale pachetelor. Întârzierea introdusă de trecerea pachetului prin memoria tampon este de obicei mai mare decât întârzierea cauzată de propagare. Creşterea numărului de staţii intermediare face ca întârzierea să crească, şi complică analiza şi tratarea traficului prioritar. Este de aşteptat ca rutarea în reţelele de senzori ţinând cont de QoS să sacrifice eficienţa energetică pentru a satisface cererea de serviciu. În plus, este inevitabilă rutarea redundantă (împărţirea traficului în mai multe fluxuri distincte şi transmiterea pe mai multe căi) pentru a face faţă cu succes ratelor relativ ridicate de eroare din comunicaţiile radio. Acest dezavantaj complică suplimentar ajungerea la un compromis între consumul de energie şi întârzierea în livrarea pachetului.
-
Mărime limitată a memoriei tampon: nodurile senzor sunt de obicei limitate în resursele disponibile de stocare şi procesare. Rutarea multi-hop se bazează pe funcţionarea unor noduri intermediare pe post de releu. Nodul intermediar încarcă pachetul în memoria tampon în vederea analizei. Dacă se constată că pachetul nu este destinat senzorului, ci unui nod distant, este încărcat în coadă pentru retransmisie. Pachetele din reţelele de senzori sunt de obicei de mici dimensiuni, şi în consecinţă nodurile au o memorie tampon a cărei dimensiune variază funcţie de aplicaţie (stocarea mai multor pachete în memoria tampon înainte de transmisie facilitează agregarea datelor în interiorul reţelei şi poate reduce consumul emiţătorului, prin transmiterea unui singur burst în loc de mai multe bursturi scurte). Deoarece rutarea în condiţiile asigurării QoS pentru o clasă de trafic necesită stocarea în memoria tampon a unei cantităţi mari de date (în special când se doreşte controlul jitterului), trebuie să se asigure din proiectare disponibilitatea unei memorii suficiente, altfel această limitare va introduce o creştere a variaţiei întârzierii pachetelor ce sosesc pe rute distincte (sau chiar pe aceeaşi rută). Astfel de problemă complică programarea accesului la mediu şi îngreunează atingerea nivelului de tratare a traficului prioritar.
-
Suport pentru mai multe tipuri de trafic: formarea unui set heterogen de senzori ridică probleme multiple legate de rutare. Se poate imagina o aplicaţie complexă, care utilizează un set foarte diversificat de senzori pentru supravegherea temperaturii, presiunii, umidităţii mediului, detecţia de mişcare (cu senzori acustici, de exemplu) şi captură de imagine, sau chiar urmărirea video a ţintei în mişcare. Aceşti senzori sunt fie amplasaţi independent, fie se folosesc noduri care includ mai multe platforme de achiziţie, care se pot folosi la alegere de către un operator. Informaţiile generate de senzorii unei astfel de reţele complexe pot avea rate diferite atât de achiziţie cât şi de transfer, sunt supuse unor cerinţe diferite de QoS şi pot urma modele distincte de livrare. O astfel de topologie heterogenă complică implementarea protocoalelor de rutare atât la nivel soft cât şi la nivel hard (necesitatea unor procesoare mai puternice, eventual ASICuri specializate pentru tratarea QoS, rezultând o creştere a consumului energetic al nodului, şi deci o scădere a duratei de funcţionare –vezi fig. 17).
Fig. 17 Deservirea mai multor cozi de prioritate
3.3.3 Exemple de protocoale de rutare cu QoS
Dezvoltarea de protocoale de rutare ce pot funcţiona în medii cu constrângeri QoS a intrat în interesul mediului de crecetare în ultimii ani, ca răspuns la apariţia de noduri senzor mai performante, capabile să răspundă cerinţelor crescute de putere de procesare.
Se pot identifica două categorii de protocoale: prima categorie se concentrează pe echilibrarea compromisului energie consumată – întârziere, fără a lua în considerare celelalte probleme, iar cea de-a doua categorie încearcă optimizarea ocupării benzii disponibile şi micşorarea întârzierii prin împărţirea traficului prin mai multe noduri.
SAR (Sequential Assignement Routing) este primul protocol implementat pentru reţele de senzori care include QoS în deciziile de rutare. Se încearcă creşterea eficienţei consumului de energie şi toleranţa la erori prin identificarea în tabela de rutare a mai multor noduri către care se poate transmite fluzul de date.
Protocolul SAR creează arbori cu rădăcina aleasă dintre vecinii de ordinul unu al nodului colector, luând în considerare metrici QoS, resurse energetice disponibile pe fiecare cale şi nivelul de prioritate al fiecărui pachet. Arborii astfel creaţi, se calculează căi multiple de la nodul colector către senzori (numai o cale este folosită efectiv pentru trafic, celelalte se păstrează ca rezerve). Recuperarea la pierderea unei legături se face prin menţinerea consistenţei tabelei de rutare în ambele sensuri. Orice pierdere locală a legăturii porneşte automat o procedură de restaurare a căii.
Dezavantajele SAR: deşi menţinerea căilor multiple în tabela de rutare permite o recuperare rapidă în cazul pierderii unei rute, protocolul are un overhead sporit din cauza necesităţii menţinerii tabelelor (în special când numărul de noduri este foarte mare). În plus, rutele redundante nu sunt folosite simultan pentru transmiterea traficului.
EAQRP (Energy-Aware QoS Routing Protocol), propus de Akkaya şi Younis funcţionează prin identificarea căii cu cel mai mic cost şi cu eficienţă energetică maximă, ce respectă un criteriu de întârziere end-to-end în timpul stabilirii conexiunii. Costul legăturii este o funcţie ce înglobează rezerva de energie disponibilă nodului, energia necesară pentru emisie, rata erorii şi alţi parametri.
Pentru a acomoda traficul prioritar şi cel normal simultan se foloseşte un sistem de coadă cu clasificator, ce permite servirea simultană a celor două clase de trafic. Procentul din bandă alocat comunicaţiilor prioritare se defineşte de către nodul gateway ca valoare iniţială, şi va fi folosit per conexiune în caz de congestie. Acelaşi procent din bandă se alocă şi traficului normal, ceea ce permite traficului neprioritar sa traverseze nodul. Modelul cozii este prezentat în fig. 18.
Fig. 18 Configuraţia cozii protocolului EAQRP
Dezavantajul protocolului îl constituie lipsa de flexibilitate în alegerea procentului de bandă alocat pentru legături diferite, pentru a permite o utilizare mai eficientă a conexiunilor.
SPEED este un protocol de rutare cu QoS pentru reţele de senzori care oferă garanţia livrării în timp real end-to-end. Protocolul necesită ca fiecare nod să menţină o tableă cu informaţii despre vecini şi utilizează retransmisia geografică pentru a găsi căile optime. Suplimentar, SPEED încearcă să asigure o anumită viteză pentru fiecare pachet din reţea astfel ca fiecare aplicaţie să poată estima întârzierea totală a pachetului cunoscând distanţa către destinaţie şi viteza pachetului înainte de a lua o decizie si poate oferi evitarea congestiilor dacă reţeaua este supraîncărcată.
Modulul de rutare al SPEED este SNGF (Stateless Geographic Non-Deterministic Forwarding) şi funcţionează cu alte 4 module la nivelul reţea după cum se vede în fig. 20. Mecanismul semafor colectează informaţii despre noduri şi locaţia acestora. Estimarea întârzierii la fiecare nod se face prin calcularea perioadei scurse de la transmitera unui pachet până la recepţia unui mesaj ACK de la vecin. Analizând întârzierile din reţea, SNGF selectează nodul care îndeplineşte necesităţile de viteză. Dacă un astfel de nod nu poate fi găsit, se verifică rata de releu a nodulu. Această rată este obţinută de la modulul de verificare a vecinilor, care calculează câte din nodurile vecine nu satisfac cerinţele de viteză. Rata este apoi introdusă în SNGF. Dacă aceasta e mai mică decât un număr aleator între 0 şi 1, pachetul este ignorat. Modulul de rerutare este utilizat în prevenirea situaţiilor când nodul nu poate găsi următorul hop, precum şi a congestiilor, trimiţând mesaje la nodurile sursă pentru ca acestea să caute rute alternative.
Fig. 20 Componentele de rutare ale protocolului SPEED
În concluzie, vasta majoritate a protocoalelor de rutare disponibile pentru reţelele de senzori au ca obiectiv final obţinerea eficienţei energetice maxime. Având în vedere însă introducerea de sisteme de achiziţe video/captură de imagini, volumul traficului în reţea creşte, şi sunt necesare protocoale specializate, capabile să facă faţă cu succes nu numai optimizării consumului de energie, dar şi acces efectiv la măsurătorile efectuate.
Dostları ilə paylaş: |
