Proiect tehnici de Rutare în Reţelele de Senzori Wireless

3.2 Nivelul legăturii de date (protocoale MAC)

Protocoalele de control al accesului la mediu coordonează timpii în care un număr de noduri accesează un mediu comun de comunicaţie. Vom prezenta căteva aspecte fundamentale ale protocoalelor MAC şi problemele specifice pe care le întâmpină în reţelele de senzori wireless.

În mod tradiţional, cele mai importante cerinţe de performanţă ale protocoalelor MAC sunt: eficienţă, stabilitate, echidistanţă, întârziere mică la acces (timpul între sosirea pachetului şi prima încercare de transmisie), debit şi încărcare mică. Suplimentul de date introdus de protocoalele MAC se compune din suplimentul introdus per pachet (headerele şi trailerele MAC), coliziuni sau schimbul de pachete suplimentare de control. Coliziunile pot apărea dacă protocolul permite două sau mai multor staţii să emită simultan şi au ca rezultat incapacitatea receptorilor de a decoda corect pachetul. Apariţia unui astfel de eveniment semnalizează protocoalelor de nivel superior din stivă să iniţieze o retransmisie.

Funcţionarea şi performanţele acestor protocoale este influenţată puternic de proprietăţile nivelului fizic. Deoarece reţelele de senzori folosesc de obicei un mediu deschsi de comunicaţii, se pot observa cu uşurinţă rate ridicate de eroare, variabile în timp, cauzate de fenomene ca fadingul rapid/lent, atenuare, pierderi pe canal, zgomot termic sau introdus.

Deoarece atenuarea pe canal face ca puterea la recepţie să scadă drastic, un transceiver poate demodula un semnal numai până la o putere minimă de prag, deci există o rază maximă pe care nodul o poate acoperi pentru o putere de emisie dată. Acest fapt generează 2 probleme specifice protocoalelor CSMA (detecţia coliziunulor, CD, nu este aplicabilă într-o reţea wireless de senzori):

• 
  Problema terminalului ascuns: specifică protocoalelor CSMA. Considerăm cazul a 3 noduri, A şi B sunt în raza de comunicaţii, B şi C la fel, dar A şi C nu sunt în rază, vezi figura de mai jos:
  

Fig. 7 Scenariul terminal ascuns/expus (cercurile indică raza de emisie)

Dacă A şi C decid simultan să trimită un pachet către B, utilizând protocoale CSMA simple, vor detecta mediul liber, şi pachetele vor fi filtrate de nodul B la recepţie, rezultând în coliziuni nenecesare.

• 
  Problema terminalului expus: B începe să transmită un pachet către A şi după un interval mic de timp, C încearcă să transmită un pachet către D. Deşi pachetele ar ajunge la destinaţie fără distorsiuni, protocolul CSMA inhibă la nodul C începerea transmisiunii, deci banda este irosită.
  

Soluţii ale acestor probleme sunt cea a tonului “ocupat” şi handshake-ul RTS/CTS utilizat de protocoalele MACA/MACW.

Protocoalele MAC pot fi clasificate în 3 clase: asignare fixă, asignare la cerere şi cu acces aleator.

Protocoalele cu asignare fixă împart resursele disponibile între noduri pe o perioadă temporală considerabil mai întinsă decât cea necesară unui burst de date. Pentru a putea urmări fenomene ca schimbările de topologie (noduri cu baterii epuizate sau noduri noi introduse în reţea), sunt necesare mecanisme de semnalizare pentru a renegocia asignarea resurselor. Din această cauză, aceste protocoale nu sunt scalabile.

Protocoalele tipice ale acestei clase sunt TDMA, FDMA, CDMA şi SDMA. TDMA necesită o bună sincronizare, pentru ca semnalele din sloturi temporale învecinate să nu se suprapună, FDMA necesită filtre trece bandă înguste pentru o bună separare a canalelor şi sincronizare de frecvenţă, CDMA necesită un bun management al codurilor iar SDMA, deoarece necesită sisteme de antene şi tehnici de procesare sofisticate este exclusă ca metodă de acces pentru WSN.

Protocoalele cu asignare la cerere pot fi împărţite în centralizate şi distribuite: nodurile iniţiază cereri de alocare de resurse către nodul central care le acceptă sau respinge. În cazul acceptului, o confirmare le este transmisă de la nodul central incluzând descrierea resursei alocate (de ex. nr. şi poziţia slotului tempoaral în TDMA). Dealocarea resurselor se face implicit, pentru a evita transmiterea de semnale suplimentare de eliberare. Nodul central efcetuează multe sarcini care necesită menţinerea lui în permanentă activitate. Acest lucru este posibil doar în cazul accesului la o sursă continuă de energie. De aceea, pentru WSN este mai convenabilă utilizarea clasei de protocoale distribuite, în care rolul de nod central este asumat pe rând de toate nodurile, de ex. protocolul LEACH.

Protocoalele cu acces aleator se utilizează în reţelele de senzori numai sub variaţii ale formei CSMA, în care se implementează soluţii problemelor terminalului ascuns şi a terminalului expus.

Rezolvarea iniţială a problemei s-a făcut utilizând un canal de trafic şi unul de control. Simultan cu începerea recepţiei unui pachet, nodul transmite o frecvenţă nemodulată pe canalul de control până la sfârşitul recepţiei. Înainte de transmisie, nodul ascultă canalul de control. În lipsa semnalului ocupat începe transmisiunea, dacă se detectează semnal de ocupat, porneşte un algoritm “backoff” (aştepată un interval aleator până la reîncercare).

Handshake-ul RTS/CTS utilizează un singur canal şi 2 tipuri de pachete de control: B iniţiază comunicaţia trimiţând Request To Send nodului C (după ce a verificat lipsa traficului pe canal), incluzând un câmp de durată estimată a transmisiunii. La recepţia corectă a RTS, C emite un Clear To Send însoţit de un câmp de durată. La recepţia CTS B începe să emită, iar la finalul transmisiunii C răspunde cu un acknowledgement. Staţiile A şi D ce recepţionează pachetul RTS sau CTS setează un contor intern (Network Allocation Vector) de durata indicată de câmpul respectiv şi nu trimit pachete până la expirarea contorului.

Fig. 8 Handshake-ul RTS/CTS IEEE 802.11

Problemele RTS/CTS sunt figurate mai jos:

Fig 9. Două probleme ale RTS/CTS

În stânga: nodurile A şi B rulează secvenţa RTS-CTS-Date-Ack iar pachetul CTS de la B ajunge şi la C. În acelaşi moment, nodul D trimite un RTS către C, urmează o coliziune şi C nu poate sa-şi seteze NAV adecvat. D retransmite RTS, C răspunde cu CTS şi pachetul creează o coliziune la recepţia datelor de către B. În dreapta, problema e cauzată de C trimiţând pachetul RTS către D imediat înainte de a detecta pachetul CTS de la B, care nu mai poate fi decoadat corect. O soluţie la problemă este ca pachetul CTS să fie mai lung decât pachetele RTS. Desigur, handshake-ul RTS/CTS generează mult trafic suplimentar, deci, dacă dimensiunea pachetelor de date este mică, avantajele metodei scad considerabil şi este mai convenabilă utilizarea CSMA.

3.2.1 Probleme de consum la nivelul MAC

În cazul WSN, cerinţele impuse protocolului diferă de reţelele tradiţionale de comunicaţii. Performanţa nu se mai măsoară în oportunitate, acces şi întârziere (care joacă un rol minor) ci în scalabilitate şi robusteţe la schimbări dese de topologie, cauzate de introducerea sau dispariţia nodurilor, de opririle pentru reîncărcare etc.

Din analiza arhitecturii hardware se poate deduce că: transmisiunile sunt costisitoare, costurile de recepţie sunt deseori la fel de mari, standby-ul este semnificativ mai ieftin, dar costul energetic creşte la intrarea şi ieşirea din standby, iar hibernarea aproape nu consumă resurse, dar produce ca rezultat noduri nefuncţionale. Putem astfel defini următoarele cerinţe pentru protocoalele MAC implementabile la nivelul WSN:

• 
  Coliziunile: acestea produc penalităţi de cost la recepţie la nodul destinaţie, şi presupun cheltuielo energetice suplimentare pentru retransmisia pachetelor. Este deci recomandabil evitarea lor, fie prin proiectare ( protocoale cu asignare fixă sau la cerere TDMA) sau prin proceduri CSMA adecvate. Dacă se poate garanta pentru o aplicaţie particulară un volum de date suficient de mic, coliziunile nu constituie o problemă.
  
• 
  Recepţia de pachete nedorite: mediul de transmisiune radio e de tip broadcast, deci toţi vecinii sursei recepţionează mesajul şi aruncă pachetul pe interfaţă când nu le e destinat. În cazul reţelelor dense, evitarea recepţiei pachetelor nedorite constituie un avantaj energetic semnificativ. Câteodată însă acest fenomen est dezirabil în special la construirea tabelelor topologice sau la estimarea încărcării curente în scopuri de management.
  
• 
  Overheadul protocolului: este introdus de cadre de control de nivel 2, cum ar fi pachetele RTS/CTS sau pachetele de cerere în protocoalele cu asignare de resurse, precum şi de trailerele şi headerele introduse în pachet.
  
• 
  Ascultarea idle: un nod în stare de repaus este gata să primească şi să proceseze un pachet dar se află într-o pauză de trafic. Faptul că este pregătit de procesare fără a avea date de prelucrat consumă cantităţi semnificative de energie. Oprirea transceiverului este o soluţie , dar trebuie luat în considerare costul opririi/pornirii. În concluzie, acest ciclu de porniri/opriri trebuie menţinut la un nivel minim. Sunt deci avantajoase protocoalele bazate pe TDMA, deoarece trancseiverul poate fi oprit pe durata sloturilor tempoarale necorespunzătoare.
  

Complexitatea redusă este o cerinţă de proiectare, deoarece se intenţionează obţinerea unui cost minim per nod. Trebuie deci evitaţi algoritmii complecşi de sincronizare (iar TDMA cu sloturi temporale mici necesită o sincronizare de bună calitate, ceea ce se traduce în resincronizări frecvente între nodurile învecinate, şi duce la un consum energetic sporit.
În continuare vom prezenta pe scurt principalele protocoale de nivel 2 utilizate în reţelele de senzori.
Protocolul STEM
Protocolul pentru topologie disparată cu management energetic oferă o soluţie ascultării în mod de repaus. Este implementat în reţele amplasate pentru raportarea comportării unui fenomen rar. În acest scop sunt utilizate 2 stări: monitor şi transfer, necesitând 2 transceivere separate, unul pentru canalul de activare şi unul pentru canalul de transfer date. Transceiverul de transfer date este în hibernare până în momentul în care trebuie să transfere sau să primească pachete de date. Protocolul MAC e executat numai pe canalul de date în timpul stărilor de transfer. Pe canalul de activare sunt alocate perioade fixe de activare de lungime T, subîmpărţite în perioadă de ascultare Trx << T şi perioada de hibernare, în care transceiverul de pe canalul monitor se opreşte. Când un nod intră în perioada de ascultare, porneşte transceiverul canalului de activare şi aşteaptă semnale. Dacă nu se receptionează nimic în Trx, nodul reintră în hibernare. În cazul recepţiei, se iniţiază transferul de pachete pe canalul de date. Există 2 variante prin care nodul emiţător captează atenţia nodului destinaţie:

STEM-B (beacon) transmite semnale baliză pe canalul de activare periodic în perioadele de activitate. Când receptorul primeşte semnalul baliză (şi îşi recunoaşte propria adresă MAC ca destinaţie), trimite o confirmare, emiţătorul opreşte semnalul baliză, se deschid canalele de transfer şi se iniţiază protocolul MAC (de ex. un handshake RTS/CTS).

STEM-T (tone) transmite pe canalul de activare un ton de ocupat pe o perioadă suficient de întinsă pentru a acoperi o perioadă de ascultare a nodului destinaţie. Toate nodurile învecinate pornesc canalul de transfer şi pachetul de date primit e filtrat de toate în afară de nodul destinaţie.

Figura de mai jos prezintă stările protocolului STEM

Fig. 10 Ciclul STEM pentru un singur nod

Protocolul S-MAC
Protocolul Senzor-MAC oferă mecanisme de prevenire a ascultării în mod idle, a coliziunilor şi a recepţionării de pachete nedorite. Nu necesită 2 canale separate.

Se adoptă o schemă periodică de activare (nodul baleiază între o perioadă fixă de hibernare şi una de activitate). Perioada de ascultare se poate utiliza la recepţia şi transmisia pachetelor. Se încearcă sincronizarea perioadelor de ascultare între nodurile învecinate. Perioada de ascultare e împărţită în 3 faze: faza de sincronizare, în care nodul acceptă pachete de sicronizare de la vecini (în pachet se descrie propria configuraţie a fazelor), pe care le stochează în tabela de sincronizare. Din motive de sincronizare şi de actualizare a topologiei, pachetele de sincronizare se trimit periodic. Faza RTS, în care nodul aşteaptă pachete RTS de la vecini. Vecinii interesaţi concurează la acces utilizând o alocare CSMA cu backoff. Faza CTS, în care nodul transmite un pachet CTS dacă a recepţionat un pachet CTS în faza precedentă. După aceasta continuă transmisia datelor propriu-zise.

Fig. 11 Principiul S-MAC
Prin transmiterea pachetelor de sincronizare şi menţinerea informaţiei în tabele, S-MAC permite formarea de clustere virtuale, regiuni ale reţelei care au aceaşi planificare a ferestrelor se ascultare/hibernare. Aceste regiuni sunt bordate de noduri care au în tabelă 2 sau mai multe planificări ale traficului, şi trebuie să emită în concordanţă pentru toate zonele (se creşte astfel timpul de activitate al acelor noduri şi deci se scade durata lor de viaţă). Structura de cluster este limitată la sincronizări, şi nu interferă cu transferul de date. Deoarece protocolul ascultă periodic după mesaje de sincronizare, formarea de clustere virtuale este robustă şi rezistentă la erori.

S-MAC adoptă şi un mod de fragmetare a pachetelor lungi. O serie de fragmente este transmisă în urma unui singur schimb de mesaje RTS/CTS dinter nodul emiţător A şi receptorul B. După fiecare fragment, B răspunde cu un acknowledgement. Toate pachetele de control au un câmp al duratei, şi nodul vecin C e obligat sa-şi seteze contorul NAV în concordanţă. Dacă un fragment necesită retransmisie, contorul e incrementat cu lungimea pachetului plus lungimea ack-ului.

Fig. 12 Fragmentarea S-MAC şi setarea NAV

Problemele S-MAC sunt latenţa mare (aproximativ egală cu media perioadei de hibernare oentru toate nodurile dintr-o regiune de planificare) şi nevoia de adaptare a lungimii ferestrei de ascultare funcţie de necesităţile variabile de trafic.
Protocolul dispozitivului de mediere
Acest protocol e compatibil cu standardul peer-to-peer cu rată mică de transfer 802.15.4 WPAN. Se permite fiecărui nod din WSN să intre periodic în stare de hibernare şi să fie activ o scurtă perioadă pentru a recepţiona pachete de la nodurile învecinate. Nu există referinţă temporală globală. La fiecare trezire periodică, nodurile transmit semnale indicând adresa proprie şi disponibilitatea de a primi pachete. Nodul rămâne activ o scurtă perioadă după semnalul baliză. Dacă nici un pachet nu e primit în această fereastră, acesta se întoarce în starea de hibernare.

Când un nod vrea să transmită un pachet trebuie să se sincronizeze cu vecinul. În mod ideal, se presupune existenţa unui nod activ în permanenţă, numit dispozitiv de mediere, care primeşte toate semnalele baliză şi află timpul de activare al fiecărui nod. Dacă nodul A vrea să transmită un pachet, trimite în perioadele de activitate un cadru RTS. Nodul MD aşteaptă semnalul baliză de la nodul B şi îi trimite un cadru răspuns indicând adresa nodului A şi offsetul temporal necesar pentru ca CTS-ul emis de B să ajungă la momentul oprtun, în fereastra de recepţie. B învaţă perioadele de activitate ale nodului A şi transmite pachetul şi semnalul ack. După încheierea transmisiunii nodurile se decuplează şi revin la planificarea originală.

Fig. 13 Protocolul cu mediere în prezenţa mediatorului fără constrângeri

Un astfel de protocol are avantajul lipsei necesităţii sincronizării între noduri, această sarcină revenind MD. Desigur, cazul ideal nu poate fi folosit în situaţia unei WSN. Protocolul distribuit cu dispozitiv de mediere rezolvă această problemă printr-o metodă probabilistică: noduri aleatoare sunt pornite şi setate ca nod MD pentru o perioadă de timp, după care li se permite întoarcerea la starea iniţială.

Protocolul PAMAS
Protocolul de multiacces cu semnalizare şi management de putere prezintă un mecanism de evitare a recepţiei cadrelor nedorite utilizând 2 canale: de date şi de control. Toate pachetele de semnalizare sunt transmise pe canalul de control în timp ce canalul de date e rezervat traficului de pachete între nodurile senzor.

Funcţionare: un nod inactiv doreşte să transmită un pachet unui nod vecin. Nodul trimite un pachet RTS pe canalul de control fără să facă detecţia de purtătoare, ce conţine adresele MAC ale nodului sursă şi destinaţie. Dacă nodul vecin primeşte pachetul, răspunde cu un cadru CTS şi se poate începe transferul de date. Când nodul începe să primească pacjetul emite un ton de ocupat pe canalul de control. Dacă nodul sursă nu primeşte un pachet CTS utilizează un mecanism de backoff înainte de a aştepta un nou CTS.

Protocolul LEACH

A fost discutat pe larg vezi referinţa [24]

Protocolul SMACS
Protocolul cu întreţinere automată a accesului la mediu în reţelele de senzori este parte a unei stive de protocoale pentru reţelele de senzori care înglobează nivelul MAC, descoperirea vecinilor, ataşarea nodurilor mobile, un protocol de rutare multihop şi unul local pentru procesări cooperative. Combină descoperirea reţelei cu asignarea de planificări TDMA nodurilor. Se bazează pe următoarele presupuneri:

• 
  Spectrul disponibil este divizat în multe canale şi fiecare nod îşi poate acorda transceiverul pe un canal arbitrar (sau sunt dispnoibile mai multe coduri CDMA)
  
• 
  Majoritatea nodurilor sunt fixe şi această stare durează un timp îndelungat
  

Scopul SMACS este detecţia vecinilor şi stabilirea de legături dedicate cu aceştia, legătura ocupând un slot TDMA la fiecare dispozitiv. Din perspectiva unui nod se consumă 2 sloturi, unul pentru recepţie şi unul pentru transmisie. Pentru a se asigura că nu apar coliziuni la recepţie, SMACS alocă sloturi temporale nesuprapuse pentru fiecare legătură la fiecare dispozitiv (prin rularea unui algoritm greedy). După stabilirea legăturii, nodurile trec periodic în stări de activitate (odată per supercadru).

Nodul ascultă într-o bandă fixă pentru uninterval aleator. Daca nu primeşte nici un pachet, iniţiază un mesaj de invitaţie. Tipurile de mesaje schimbate sunt: Type1(x, neataşat), indică ID-ul nodului şi numărul de vecini ataşaţi (0 în cazul fig. 14). Dacă un nod z primeşte pachetul, răspunde după o perioadă aleatoare cu Type2(x,z,n), unde n e numărul de vecini ataşaţi. Nodul y va răspunde cu Type2(x,y,neataşat), iar nodul x iniţiază formarea unei legături trimiţând numai identificarea nodului câştigător, Type3(y,--). Y va răspunde cu mesaj Type4(x,y,specificaţii link), în care se alocă sloturile temporale şi frecvenţa sau codul.

Protocolul permite conexiuni statice între noduri. Deoarece descoperirea vecinilor rulează periodic, acesta se poate adapta la schimbări de topologie. O problemă critică o constituie alegerea lungimii supercadrului, care trebuie să fie suficient de mare pentru a putea suporta cea mai mare densitate de noduri vecine din sistem, altfel unele noduri nu ar putea comunica şi nu ar fi vizibile celorlalte noduri.

Protocolul TRAMA
Protocolul MAC adaptiv la trafic crează o planificare ce permite nodurilor să acceseze un singur canal fără coliziuni. Acestea sunt construite într-o manieră distribuită şi sunt disponibile la cerere.

Protocolul este constituit din 3 elemente: protocolul de topologie, protocolul de sincronizare a planificărilor şi algoritmul adaptiv de elecţie. Protocolul de topologie e executat în faza de acces aleator, subdivizată în sloturi temporale mici. Un nod alege aleator un număr de ferestre temporale şi transmite pachete de identificare conţinând adresa proprie şi informaţii incrementale despre topologie, numai informaţiile despre vecinii identificaţi între slotul actual şi cel precednt fiind incluse în pachet. Toate transceiverele trebuie să fie active în perioada de acces aleator.

Protocolul de sincronizare a planificărilor transmite planificarea curentă a transmisiunilor nodului şi acceptă planificările vecinilor. Alocarea sloturilor se face calculând prioritatea slotului cu o funcţie hash de forma P = h(x+t).

Nodurile pot astfel sa-şi identifice sloturile câştigătoare de transmisie şi oportunităţile. O situaţie complicată apare când, într-o vecinătate de 2 hopuri apar 2 noduri cu priorităţi mai mari decât a nodului inclus în ambele domenii. Algoritmul adaptiv de elecţie poate rezolva această situaţie şi permite reutilizarea sloturilor câştigătoare de către vecini.

Fig. 15 TRAMA – situaţie de conflict

Protocolul TRAMA are nevoie de resurse importante de procesor şi memorie, în special în cazul topologiilor dense, unde vecinătăţile de 2 hopuri ale unui nod au tendinţa să fie mari. În concluzie, TRAMA este o soluţie fezabilă numai dacă nodurile senzor au suficiente resurse.

Protocol	Cluster/Simplu	Nr. de canale necesare	Evitarea ascultării idle	Evitarea recepţie pachete nedorite	Evitarea coliziunilor	Date suplimentare (overhead)
LEACH	Clustere rotative	1	Prin TDMA	Prin TDMA	Prin TDMA	Alegerea/formarea clusterului
STEM	Ambele	2	Hibernare periodică	STEM-B	Depinde de MAC	Depinde de MAC şi de semnalele baliză
S-MAC	Simplu	1	Hibernare periodică	Prin NAV	RTS/CTS	RTS/CTS, SYNCH, iniţierea clusterelor virtuale
Mediation Device	Simplu	1	Hibernare periodică	Implicit	Nu	Serviciul periodic de mediator, semnalele de intergogare, RTS/CTS
Wakeup radio	Simplu	>2	Semnal de activare	Semnal de activare	CSMA multicanal	Radio suplimentar
CSMA	Simplu	1	-	Hibernare în timpul backoff-ului	RTS/CTS	RTS/CTS
PAMAS	Simplu	2	-	Da	RTS/CTS cu ton ocupat	Canalul de semnalizare
SMACS	Simplu	Multe	Prin TDMA	Prin TDMA	Prin TDMA	Descoperirea vecinilor, setup-ul canalului
TRAMA	Simplu	1	Prin planificare	Prin planificare	Prin planificare	Protocolul de vecinătate/planificare/transmisie

Tabel 4 Protocoalele MAC semnificative pentru WSN – sumar