CAPITOLO VII
PROTOCOLLO DI ROUTING
In una Rete di Sensori ciascun nodo comunica con i propri vicini formando così una rete multi-hop. In un ambiente di questo tipo il routing assume un’importanza fondamentale a causa della mancanza di un controllo cen-tralizzato e della grande dinamicità della rete. Il vincolo stringente di una Rete Sensoriale è che i Nodi Sensore hanno limitate capacità energetiche in quanto normalmente sono alimentati da delle batterie non sostituibili. Quindi, un protocollo di routing che cerca di minimizzare la latenza proba-bilmente riesce a minimizzare anche il consumo energetico in quanto una latenza minima comporta un numero di hop minimo da attraversare. Co-munque, un protocollo di questo tipo porta a non rispettare la ‘fairness’ nella rete. Ad esempio, un routing basato sullo ‘shortest path’ finisce con l’utilizzare sempre lo stesso set di hop per recapitare pacchetti dalla sor-gente al nodo destinatario. Questi nodi finiranno con lo scaricarsi preco-cemente rispetto agli altri e conseguentemente si spengeranno creando così dei buchi nella rete.È quindi necessario cercare di minimizzare il numero di hop che deve per-correre un messaggio per arrivare dalla sorgente a destinazione ma al tempo stesso cercare di far rimanere omogeneo il livello energetico tra i nodi della rete.
Nel protocollo da noi ideato cerchiamo di centrare questi obbiettivi impo-nendo, tra i nodi, un’organizzazione ad albero ma prevedendo anche delle
7.1
Costruzione Albero di Routing
Prendiamo in considerazione un gruppo di Nodi Sensore disposti in modo random. Tra tutti i nodi è presente il nodo SINK che agisce come nodo gateway e che si suppone con capacità energetiche infinite.
7.1.1 CREAZIONE ALBERO
Allo startup della rete tutti i nodi sono attivi e nello stato di ricezione. La procedura per la costruzione dell’albero di Routing viene avviata dal Sink che invia in broadcast un messaggio RTREQ.
Il messaggio RTREQ contiene le seguenti informazioni:
IDMIT :Identificativo del nodo mittente
HC : hop count
E : energia del nodo mittente
Nel messaggio inviato dal nodo Sink il valore di HC è settato 0 mentre l’informazione E risulta non significativa. Il campo HC indica il livello dell’albero a cui appartiene il mittente del messaggio.
Quando un generico nodo j della rete riceve il primo messaggio di tipo RTREQ a sua volta inoltra il messaggio in broadcast inserendo, però, il
pro-prio identificativo, il propro-prio livello energetico e come hop count il valore dell’hop count del pacchetto RTREQ ricevuto aumentato di una unità.
Riassumendo, se il nodo j riceve il seguente pacchetto dal nodo i (ed è il primo che ha ricevuto):
− −(RTREQ i) Packet − − MIT ID =i HC x= i E E=
MIT
ID = j
HC x= +1 (7.1)
j
E E=
Ogni nodo, a partire dall’istante di ricezione del primo messaggio RTREQ
attende, per un intervallo di tempo TWFF (WFF=wait for Fathers), altri
even-tuali messaggi RTREQ . Se l’intervallo TWFF risulta relativamente piccolo
al-lora, in base al meccanismo di invio dei messaggi RTREQ spiegato in
se-guito, è considerevole pensare che i messaggi ricevuti siano transitati su path equivalenti. A questo punto il nodo può scegliere il proprio padre in modo random tra la lista dei mittenti dei messaggi RTREQ ricevuti.
Eventuali altri messaggi RTREQ ricevuti dopo lo scadere del tempo di
atte-sa TWFF vengono automaticamente ignorati dal nodo.
La ritrasmissione in broadcast del pacchetto RTREQ da parte del nodo j
viene schedulata al termine del tempo di attesa TWFF attendendo però un
ulteriore tempo inversamente proporzionale al livello energetico del nodo j stesso. Viene inserito cioè un ritardo (Delay) nell’effettuare l’inoltro del messaggio RTREQ:
j
1
Delay Tx E∝ (7.2) Questo perché ogni nodo sceglie come padre uno dei nodi da cui riceve i primi messaggi di tipo RTREQ. Poiché il protocollo di costruzione dell’albero
di routing viene avviato dal nodo Sink e poiché il protocollo di accesso al mezzo di trasmissione è fair è possibile presupporre che i primi messaggi di tipo RTREQ che arriva ad un nodo siano anche quelli che sono transitati
sulle route che contano un numero di hop minore. Nel nostro protocollo vogliamo però anche prendere in considerazione il livello energetico dei nodi e questo viene effettuato tramite il Delay della (7.2). In particolare, nel caso in cui un nodo possa scegliere tra più di una possibile route minima (dove con minima si intende con un numero minimo di hop da attraversare
per raggiungere il nodo Sink), è necessario agevolare quella in cui il livello medio di energia dei nodi che la compongono è maggiore.
Ad esempio, nella Figura 7.1, il nodo 6 sceglie come padre il nodo 4 in quanto si trova ad un livello energetico migliore del nodo 5.
4
5
6
10
9
LIVELLO X E=100% E=60%Figura 7.1 Scelta del nodo Padre
Il Delay di trasmissione deve essere impostato in modo che sia superiore alla durata del tempo di Backoff iniziale imposto dal protocollo MAC ma inferiore al tempo che occorre ad un messaggio RTREQ a precorrere un
hop della rete . Ad esempio, in Figura 7.2-a è mostrato che, anche se la route blu ha un nodo (nodo 6) con il cui livello energetico è inferiore agli altri nodi, alla fine il messaggio RTREQ che arriva per primo al nodo 8 è
quello proveniente dalla route blu e non da quella verde. Comunque, se nella route è presente un nodo con un livello energetico molto basso (co-me in Figura 7.2-b), oppure ci sono diversi nodi con energia bassa, allora è da preferirsi un path più lungo ma i cui nodi siano in grado di garantire il funzionamento.
6 5 4 8 7 E=100% E=100% E=100% A B C E D A B C E D Delay t A B C E D Delay t E6=60% E6=5% (a) (b)
Figura 7.2 Delay nell’invio del messaggio RTREQ
Una volta effettuato l’inoltro del messaggio RTREQ il nodo si registra presso
il padre tramite un messaggio RTREG. Tale messaggio contiene
l’identificativo del nodo.
Ogni nodo, dopo aver effettuato l’inoltro del messaggio RTREQ e dopo
es-sersi registrato presso il padre rimane in ascolto, per un tempo TWFS, di
eventuali messaggi RTREG che sono inviati dai nuovi figli. Se un nodo,
terminato il periodo TWFS, non ha ricevuto nessun messaggio di
registra-zione si rende conto di occupare il ruolo di foglia nell’albero di routing che è stato creato.
Il valore dell’intervallo di tempo TWFS deve essere maggiore del ritardo (
Delay ) massimo che può attendere un nodo prima di effettuare l’inoltro del pacchetto RTREQ in quanto un nodo si registra presso il padre solo
7.1.2 DYNASTY DISCOVER PHASE
Questa fase ha due utilità: la prima è quella di far scoprire a ciascun nodo le caratteristiche dei nodi discendenti mentre la seconda è quella di far capire al Sink quando può essere considerata conclusa la costruzione dell’albero di routing. Questa fase parte dai nodi foglia e si propaga fino al Sink. I nodi si scambiano messaggi di tipo RTUPD. Ciascun pacchetto
RTUPD contiene le seguenti informazioni:
NC: Node count LC: level count
I pacchetti RTUPD vengono inviati a partire dai nodi foglia dell’albero con i
valori di NC e LC entrambi settati a 1.
I nodi intermedi restano in attesa di pacchetti RTUPD per un tempo
massi-mo pari a TWAIT. Quando un nodo ha ricevuto le registrazioni da tutti i figli
oppure è terminato il tempo utile per la ricezione, a sua volta il nodo inoltra al proprio padre il messaggio RTUPD.
Le informazioni riguardanti il Node count e il Level count sono calcolate da ciascun nodo nel seguente modo (e mostrata anche in Figura 7.3):
(
)
= + = +∑
UPD FIGLI UPD NC RT NC LC RT LC 1 [ ] 1 max [ ] (7.3) Alla fine di questa ultima fase la struttura dell’albero di routing è definita: ogni nodo è a conoscenza del nodo a cui deve fare riferimento per inviare e ricevere i dati verso il Sink (nodo padre) e, analogamente, degli eventua-li nodi di cui si deve far carico ( nodi figeventua-lio).Inoltre ogni nodo è a conoscenza delle caratteristiche (numero di nodi NC e numero di livelli HC) dei sottoalberi individuati da ciascuno dei nodi figlio. Infatti un nodo padre deve recapitare al Sink i risultati di tutti i discendenti dell’albero di routing e non solo quelli dei nodi figlio.
Da notare che la procedura di costruzione dell’albero di routing appena descritta non presenta il rischio che si formino eventuali cicli tra i nodi in quanto ogni nodo inoltra il messaggio RTREQ solo dopo che ha scelto il
4
5
6
9
(a) (b)4
5
6
9
HC=1 LC=1 HC=1 LC=1 HC=3 LC=2 N=1 L=1 N=1 L=1 (c)4
5
6
9
N=3 L=27.1.3 PROTOCOLLO PER LA COSTRUZIONE DELL’ALBERO DI ROUTING
Riportiamo adesso l’algoritmo eseguito dal nodo Sink per la costruzione dell’albero di routing: ( ){ ( ) { 1 2 3 4 5 6 SEND REQ SEND REQ WFS END END CREA_SinkROUTINGTREE RT crea _RT
send(0,RT ,broadcast ) //invio RT frame figli=0 T localTime T While(localTime<T ) = = + ( ) 7 8 9 10 REG //attesa registrazioni if(message=radio.receive()) if(message.type =RT ) if(message.ID_DEST=local_id) } { ( )
(
)
( ) 11 12 13 14 WAIT END END UPD figli++; T localTime T While(localTime<T ) if message=radio.receiveif message.type RT && message 15 = + =
(
)
{ ( )(
)
18 .ID_dest= local_ID update_value message.NC ,message.LCif figli=0 br 16 17 19 } } 20 eak 21
Il nodo Sink non deve far altro che eseguire le seguenti azioni: • Inviare il pacchetto RTSEND (righe 2-3)
• Aspettare le registrazioni dai nodi figli (righe 5-11)
• Attendere i messaggi di tipo RTUPD da tutti i figli (righe13-20)
In seguito è invece riportato il protocollo che descrive le operazioni ese-guite dagli altri nodi della rete per costruire l’albero di routing:
{ ( ){ ( )
(
)
(
)
{ = + 1 2 3 4 5 7 8 REQ WFF END CREA_ROUTINGTREE() while true padri=0; if message=radio.receive if message.type()=RT T localTime T(
)
{ ( )(
)
( )(
)
9 10 11 12 END REQ REQWhile localTime<T //Attesa RT if message=radio.receive if message.type =RT padri++; } ( ) ( )
(
)
(
)
= 13 14 15 16 SEND REQ SEND Scegli_Padre ; Delay=calcola_delay RT crea _RT message send Delay,RT ,broadcast( ) } = 17 18 19 20 21 REQ SEND REG SEND REG //invio RT frame RT crea _RT
send(0 ,RT ,message.ID _mit ) //invio RT frame break; figli=0;
(
)
{ ( )(
)
( )(
)
= + 22 23 24 25 26 WFS END END REG T localTime TWhile localTime<T //attesa registrazioni if message=radio.receive if message.type =RT
(
)
} 27 28 if message.ID_DEST=local_id figli++;// inizio Dynasty Discover Phase
(
)
{(
)
(
)
} = =1 =1 29 30 31 32 UPD SEND SENDif figli=0 // NODO FOGLIA RT crea _RT NC ; LC ; send 0,RT ,ID _PADRE
{
(
)
{ ( )(
)
= + 33 34 35 36 UPD WAIT END ENDelse //attesa RT dai nodi filgio T localTime T While localTime<T if message=radio.receive ( )
(
)
{(
)
= 37 38 39 40 UPDif message.type RT && message.ID_dest= local_ID update_value message.NC ,message.LC
(
)
}(
)
(
)
= = = 41 43 44 45 42 UPD SEND SEND if figli=0 breakRT crea _RT NC value.NC ; LC value.LC send 0,RT ,ID _ padre
} }
46
LocalTime è il valore corrente dell’orologio del nodo.
crea_RTREQ è una funzione che prende come parametro di ingresso il messaggio RTREQ ricevuto dal nodo e che crea, in base alle specifiche
e-lencate in (7.1), il pacchetto RTREQ da inoltrare.
update_value() è una funzione che, in base alle specifiche elencate in (7.3) e, aggiorna i valori di NC e LC.
crea_RTREG è una funzione che crea il pacchetto RTREG per la
registra-zione con il nodo padre.
La funzione send( ) è una funzione bloccante che permette l’invio di un pacchetto sul mezzo trasmissivo. Il primo parametro della funzione rap-presenta il ritardo con cui il livello MAC deve schedulare la trasmissione di tale pacchetto.
Righe 2-20: il nodo attende un messaggio di tipo RTREQ ed in seguito,per
un tempo TWFF altri eventuali RTREQ. Dopo aver scelto il padre inoltra in
broadcast il messaggio RTREQ aspettando un eventuale ritardo (delay) in
baso all’attuale livello energetico. In seguito invia un messaggio RTREG al
Righe21-28: il nodo riceve i messaggi di registrazione dai nodi figli. Il nodo rimane in questa fase per un tempo TRTD.
Righe 29-32:FASE DYNASTY DISCOVER: se il nodo è foglia dell’albero di routing allora invia al padre il messaggio RTUPD.
Righe 33-42: FASE DYNASTY DISCOVER: se il nodo non è foglia allora attende, al massimo per un tempo TWAIT i messaggi RTUPD dai nodi figli
Righe 43-44: FASE DYNASTY DISCOVER :il nodo invia il messaggio RTUPD al nodo padre.
7.2 Mantenimento Albero di Routing
La struttura dell’albero di routing è dinamica cioè può variare nel tempo. Le cause che possono portare alla modifica dell’albero di routing sono l’aggiunta di un nuovo nodo alla rete, la caduta di un nodo e la bassa di-sponibilità energetica di un nodo all’interno della Rete di Sensori. Queste cause portano alla modifica parziale dell’albero di routing cercando di limi-tare i cambiamenti solo ad una parte dell’albero. Esiste anche un mecca-nismo che porta ad una completa riorganizzazione dell’albero.
In generale, quando un nodo padre viene a conoscenza di un cambiamen-to delle caratteristiche (numero di nodi o numero di livelli ) del proprio sot-toalbero è necessario propagare queste informazioni ai nodi dei livelli su-periori.
Ogni nodo tiene memorizzate le informazioni riguardanti il proprio sottoal-bero ed in particolare per ogni nodo figlio i è a conoscenza:
NCi = numero nodi del sottoalbero che ha come radice il nodo figlio i
LCi = numero livelli del sottoalbero che ha come radice il nodo figlio i
Inoltre ciascun nodo mantiene:
NC= numero nodi del sottoalbero che ha come radice il nodo stesso. LC= numero livelli del sottoalbero che ha come radice il nodo stesso.
(
)
= + = +∑
i FIGLI i NC NC LC LC 1 1 max (7.4)Quando una delle due informazioni (NC o LC) cambia, le modifiche ven-gono propagate ai nodi superiori tramite dei messaggi di tipo RTUPD che
contengono i nuovi valori di NC e di LC.
Ogni nodo che riceve un messaggio RTUPD aggiorna i valori NC e LC e li
inoltra, se necessario, verso la radice dell’albero.
In seguito è riportato il protocollo di trasmissione e di propagazione delle modifiche dell’albero: { { } ( ) UPD SEND SEND RT _UPDATE () if(NC o LC change) RT crea _RT ( NC ,LC ) send(0,RT ,ID _PADRE ) if(message=radio.receive ) if(message.ty = 1 2 3 4 5 6 7 { } } UPD pe()=RT ) update(NC,LC) RT_UPDATE(); 8 9 10 11
dove update(NC,LC) ha il compito di aggiornare i valori di NC e LC me-morizzati nel nodo (come riportato in (7.4))
7.2.1 AGGIUNTA DI UN NODO ALLA RETE
Nel caso in cui nuovi nodi vengano dislocati all’interno dell’area di sensing è necessario che questi, per poter comunicare con il Sink, siano integrati nell’albero di routing.
Ogni nodo aggiunto entra nella fase Wait for Beacon. 7.2.1.1 Wait For Beacon Phase
Questa fase, di durata TWFB, serve a far sì che il nodo collezioni i Beacon
Frame che periodicamente sono inviati dai nodi padre verso i figli.
Se però, durante la fase Wait for Beacon, il nuovo nodo rileva un messag-gio di tipo RTREQ o RTRST, allora capisce che la rete è nella fase di refresh
periodico (vedi paragrafo successivo) e quindi esce dalla fase Wait for Beacon e partecipa, insieme agli altri nodi, alla riconfigurazione totale dell’albero di routing.
Negli altri casi il nodo colleziona i Beacon Frame inviati dai nodi verso i propri figli. Inoltre, fino alla ricezione del primo Beacon Frame, il nodo ne-cessariamente deve prendere in considerazione anche i messaggi inviati dai nodi figlio verso il nodo padre ed in particolare l’identificatore di almeno uno di questi nodi.
Al termine della fase Wait for Beacon il nodo sceglie il padre a cui asso-ciarsi.
La durata della fase Wait for Beacon dovrebbe essere tale che il nuovo nodo possa rimanere in ascolto di beacon Frame per almeno un commu-nication period.
La scelta del nuovo padre viene fatta seguendo il seguente procedimento: • Se durante la fase Wait for Beacon il nodo non ha rilevato nessun
beacon Frame allora il padre viene scelto in modo random tra gli ID prelevati dai messaggi trasmessi dai nodi figlio verso il nodo padre oppure, più semplicemente, viene scelto come padre il mittente del primo messaggio ricevuto. Siamo cioè nel caso in cui il nodo inseri-to ha nel proprio raggio di sensing solo nodi che nella configurazio-ne attuale dell’albero di routing hanno il ruolo di foglia (Figura 4-b)
• Se invece il nodo ha ricevuto almeno un Beacon Frame allora sce-glie come nodo padre un nodo che nella configurazione attuale dell’albero occupa già un ruolo di padre ( Figura 7.4-a).Se il nodo ha la possibilità di scegliere tra più possibili padri allora ,tra tutti i nodi che si trovano sul livello minore dell’albero (cioè più vicino al Sink), seleziona quello con una energia maggiore ma che comun-que deve essere superiore ad una certa soglia minima (es 5%). In questo caso l’algoritmo per la scelta del padre risulta il seguente:
( ){
(
)
(
)
scegli _ padre
ordina lista_padri by livello albero //dal minore al maggiore for_each level
ordina by energia //dal maggiore al minore 1
2 3 4
(
)
for_each(padre) //scorro la lista ordinata if padre.energia>soglia return padre.ID return 1lista.ID 5 6 7 8
In pratica, data una lista di possibili padri, per prima cosa (riga 2) viene ordinata per livello di appartenenza nell’albero (a partire dai nodi più vicini al Sink). Dopo (righe 3,4) , per ogni livello, i nodi ven-gono ordinati in basa al livello energetico (partendo da quelli ad e-nergia maggiore). A questo punto (righe 5-7) la lista viene scorsa da cima e viene scelto come nodo padre il primo nodo che ha ener-gia maggiore della soglia.
Nel caso in cui tutti i nodi hanno energia inferiore alla soglia allora si ritorna in cima alla lista e si sceglie il primo nodo (riga 8).
4
5
6
9
N
4
5
6
9
N
Raggio ricezione nodoN
Nodo InseritoFigura 7.4 Aggiunta di un nodo alla rete
Una volta scelto il nodo padre è necessario effettuare la registrazione. Se il nodo padre scelto è stato rilevato tramite un Beacon Frame allora il nodo, in base alle informazioni di sincronizzazione contenute nel Beacon Frame stesso, viene messo nello stato di sleep e si riaccende solo quan-do inizia il Talk Interval del nodo prescelto. Durante il Talk Interval il nodo invia al padre un messaggio di tipo RTREG contenente il proprio
identificati-vo e le informazioni riguardanti il proprio sottoalbero (in questo caso NC=1 e LC=1).
Se invece il padre prescelto è un nodo foglia allora il nodo rimane sveglio in stato di ricezione fino a quando non rileva sul mezzo un messaggio in-viato dal futuro padre. A questo punto viene inin-viato il messaggio RTREG.
Il nodo che, alla ricezione di un messaggio RTREG, rileva la presenza di un
nuovo figlio costruisce, in base alle specifiche descritte nel paragrafo 5.2, un messaggio di tipo RTUPD e lo propaga verso il Sink.
L’algoritmo che deve essere eseguito dal nodo che deve agganciarsi al all’albero di Routing è il seguente:
{ { ( ) { ( ) 2 3 4 5 6 7 WFB END END RT_AggiungiNodo msg=0 T localTime T while(localTime<T ) if(message=radio.receive ) if(message.type =BF) = + 1 { 8 9 10 11 MIT
aggiungi message.ID a lista_padri else if(lista_padri=vuota && msg=0) msg++ ID=message.ID } } 12 13 14 15 16 MIT if(lista_padri=vuota) ID_PADRE=ID else } 17 18 19 SEND REG SEND ID_PADRE=scegli_padre(lista_padri)
RT crea _RT ( send _to ID _PADRE ,NC ,LC ) send(0,RT ,ID _PADRE )
= =
20
Per tempo TWFB (righe 3-4) il nodo si mette in ascolto dei messaggi che
transitano sul mezzo di trasmissione (riga 5). Se il messaggio ricevuto è un Beacon Frame allora il mittente viene aggiunto alla lista dei possibili padri (righe6-7), altrimenti viene memorizzato il mittente del messaggio ri-cevuto solo se ancora non sono stati ricevuti né Beacon Frame né altri messaggi (righe 9-11). Se, scaduto il tempo di ascolto la lista ei possibili padri è vuota allora viene scelto come padre il mittente del messaggio ri-cevuto (righe 14-15), altrimenti il padre viene scelto in base al criterio de-scritto in precedenza (riga 17). Infine viene prima creato e poi inviato il messaggio di registrazione al nuovo padre (righe 18-19).
Invece il nodo che riceve il messaggio RTREG dal nuovo nodo compie le seguenti operazioni: { ( ) ( ) { ( ) } } 2 3 4 5 6 7 REG Aggiungi _nodo if(message=radio.receive ) if(message.type =RT ) update(NC,LC) RT_update 1 7.2.2 CADUTA DI UN NODO
Un nodo può smettere di funzionare o per un fallimento interno oppure perché esaurisce la propria carica energetica. In questi casi l’albero deve essere aggiornato più velocemente possibile per limitare il tempo in cui una parte della rete rimane scollegata dal Sink.
La caduta di un nodo viene rilevata dal nodo figlio quando non riceve il Beacon Frame per k Communication Period successivi (ad esempio k=2). Il nodo che rileva la scomparsa del padre si trova ora nelle stesse condi-zioni di un nuovo nodo che viene aggiunto alla rete con l’unica differenza che questo può essere a sua volta padre di altri nodi.
Quindi, il nodo si mette alla ricerca di un nuovo padre seguendo la proce-dura elencata in precedenza con l’unica differenza che nel messaggio RTREG che viene spedito al padre risulta specificato anche il numero di
nodi e il numero di livelli del sottoalbero che ha come radice il nodo stes-so. Il nuovo nodo padre propagherà la modifica dell’albero inviando verso il Sink un messaggio RTUPD opportunamente costruito in base alle
specifi-che elencate in (7.4).La procedura seguita dal nodo specifi-che rileva la caduta del padre è la seguente:
{ 2 for_each(communication period) 3 if(BF.received()=false) 4 5 CPNBF++ else 6 CPNBF=0 { ( )
( )
}
} } 7 8 10 11 12 if(CPNBF=k) RT_AggiungiNodo anti_loop 9CPNBF (Communication Period No Beacon Frame) è una variabile che tiene di conto il numero di Communicatio Period consecutivi in cui il nodo non ha ricevuto un Beacon Frame dal Padre (righe 3-6).
La procedura anti_loop() ha il compito di verificare se nella scelta di un nuovo padre si è creato un ciclo tra alcuni nodi della rete. Come mostrato in Figura 7.5, quando un nodo che a sua volta è padre di altri nodi cerca un nuovo padre potrebbe registrarsi presso un proprio nodo discendente: in questo modo alcuni nodi della rete risultano scollegati dal nodo Sink ed è quindi necessaria una procedura per rilevare ed eliminare eventuali lo-op. 10 5 11 9 12 10 5 11 9 12 (a) (b)
7.2.3 MECCANISMO ANTI LOOP
Nei protocolli per il mantenimento dell’albero di routing appena descritti, esiste la possibilità che si vengano a creare dei cicli tra i nodi della rete. In particolare, questa cosa può accadere durante le operazioni di scelta di un nuovo padre da parte di un nodo che a sua volta svolge la funzione di pa-dre per altri sensori della rete ( causa caduta di un nodo oppure nodo a basso livello energetico).
Un tipico ciclo che può formarsi è quello in cui un nodo sceglie come pa-dre un nodo che contemporaneamente è anche un proprio discendente come mostrato nella Figura 7.6-a. Altro caso è quello illustrato in Figura 7.6-b in cui il nodo 10 sceglie come nuovo padre un discendente del nodo 6 ed il nodo 6 sceglie come padre un discendente del nodo 10.
10 11 12 10 11 12 (b) (a) 7 6 8 9 Figura 7.6 loop
Ogni volta che un nodo x ( nella Figura 7.6 il nodo 10) , che ha più di un livello nel proprio sottoalbero (LC>1) e che si trova nel livello x-level dell’attuale albero di routine, sceglie come nuovo padre un nodo y che si trova ad un livello dell’albero y-level inferiore a x-level (cioè y-level < x-level) è necessario che il nodo x verifichi se ha creato un loop all’interno della rete.
chetto lo inoltra immediatamente al proprio figlio. In caso di loop l’ LT-Packet deve ritornare al nodo x mittente. Il nodo x può assumere che non si siano creati cicli se non riceve l’ LT-Packet entro un numero k di Com-munication Period pari al salto di livello che ha effettuato nel cambio del padre. Cioè:
(
y-level 1) (
x-level)
k = + − (7.5) Se durante il periodo di attesa, il nodo x (nodo 10) cambia nuovamente il proprio livello nell’albero (perché ad esempio, come in Figura 7.6-b, il no-do 6 cambia di livello sceglienno-do come padre il nono-do 12), allora deve ag-giornare il periodo utile di attesa.
In seguito è riportato il protocollo per la rilevazione di cicli nella rete. ( ){
(
)
(
)
(
)
{ ( ) SEND anti _loop//x-level= vecchio livello; y-level=nuovo livello if NC>1 && y-level<x-level // verifica loop RT crea _LT-packet C = 1 2 3 4 5 6
(
) (
)
(
)
(
)
{(
)
SENDounter y-level x-level send 0,RT ,nodi _figlio for_each Communicatio_Period
if cambio livello //aggiorno Contatore = − 7 8 9 10
(
(
) (
)
)
(
)
Counter= Counter+ new-level old-level Counter Counter
if Counter 0
return //NO LOOP if ricevut − = ≤ 11 12 13 14 1
(
)
( ) } } o LT-packet RT_Cerca_NuovoPadre //LOOP 15 16 177.2.4 NODO A BASSO LIVELLO ENERGETICO
Quando l’energia di un nodo scende al di sotto di una certa soglia è consi-gliabile riorganizzare l’albero in modo che il nodo con un basso livello e-nergetico diventi un nodo foglia o almeno diminuisca l’attività di inoltro che sta svolgendo. L’obbiettivo è quello di ridurre il consumo energetico del nodo in difficoltà con conseguente incremento del tempo di vita del nodo stesso. Tutto questo viene fatto per uniformare il consumo della rete e per cercare di non ritrovarsi nella situazione in cui ci sono nodi scarichi mentre contemporaneamente altri nodi siano con grandi capacità energetiche. Quindi, un nodo padre il cui livello energetico scende al di sotto di una cer-ta soglia, invia un messaggio RTFNF ai propri figli per spronarli a ricercare
un nuovo padre.
Un nodo che, durante il Talk Interval, riceve un messaggio RTFNF si mette
alla ricerca di un nuovo nodo padre (come mostrato in Figura 7.7); co-munque, durante il Talk Interval corrente, continua ad inviare i risultati del-le interrogazioni al vecchio padre mentre, nel Silence Interval successivo, invece di andare nella modalità sleep, rimane acceso e si mette alla ricer-ca di un nuovo padre seguendo la procedura di aggancio di un nuovo no-do alla rete descritta nel paragrafo 5.2.1.
Una volta che il nodo si è registrato con il nuovo padre è necessario che si deregistri con il vecchio. La deregistrazione viene fatta inviando, durante il Talk Interval con il vecchio nodo padre, un messaggio RTDE contenente
l’identificativo del nodo che si vuole deregistrare.
Sia il nuovo padre che il vecchio padre comunicano le variazioni del pro-prio sottoalbero inoltrando un messaggio RTUPD.
La soglia di energia sotto la quale un nodo decide di inviare un messaggio RTFNF ai propri figli viene settata staticamente ad un valore basso (ad
e-sempio il 5% di energia totale del nodo). Viene usata una soglia stabilita in modo statico perché comunque, periodicamente, l’albero di routing viene ricostruito totalmente (refresh periodico) e quindi si riesce a distribuire il consumo sui vari nodi.
4
5
6
10
9
4
5
6
10
9
RTFNF (a) (b)Figura 7.7 Nodo a Basso Livello Energetico
Il protocollo che viene eseguito dal padre quando rileva che il proprio livel-lo energetico è inferiore alla soglia di allerta è il seguente:
{ { } ( ) { ( ) 5 7 8 9 SOGLIA FNF SEND SEND DE RT _LowPower() if(E E ) RT crea _RT () send(0,RT ,Figli ) if(message=radio.receive ) if(message.type =RT ) ≤ = 2 3 4 1 } } 10 11 12 update(NC,LC) RT_update()
In seguito sono invece riportate le azioni intraprese da un nodo quando ri-ceve un messaggio RTFNF:
{ ( ) ( ) { ( )
( )
1 5 2 3 4 7 FNF RT _FNF () if(message=radio.receive ) if(message.type =RT ) RT_CercaNuovoPadre anti_loop}
} 5RT_CercaNuovoPadre() è un algoritmo che ricerca un eventuale nuovo padre e naturalmente risulta molto simile a RT_AggiungiNodo() con l’unica differenza che il nodo deve scegliere come nuovo padre un nodo diverso dal suo attuale padre ed eventualmente deregistrarsi dal vecchio padre. Anche in questa situazione potrebbe crearsi un ciclo tra alcuni nodi della rete e quindi risulta necessaria la procedura anti_loop().
{ { { = + 1 2 3 4 5 6 END END RT_CercaNuovoPadre() msg=0 T localTime CP while(localTime<T ) if(message=radio.receive())
if(message.type()=BF && message.ID
{ ≠ 7 8 9 10 11 MIT MIT MIT ID_PADRE) aggiungi ID a lista_padri else if(lista_padri=vuota && msg=0) ID=message.ID } } ≠ 12 13 14 15 if(ID ID_PADRE) msg++ if(lista_padri=vuot 15 17 a) ID_NPADRE=ID else { 18 19 20 21 22 SEND REG SEND ID_NPADRE=scegli_padre(lista_padri,ID_PADRE)) if(ID_NPADRE NULL)
RT crea _RT ( send _to ID _NPADRE ,NC ,LC ) send(0,RT ,ID _PADRE )
≠ = = ( ) } } 23 25 SEND DE SEND RT crea _RT
send(0,RT ,ID _PADRE ) ID_PADRE=ID_NPADRE = 24 26
7.2.5 REFRESH PERIODICO
Come è possibile notare tutti i cambiamenti della struttura dell’albero di Routing appena descritti portano ad una modifica parziale dell’albero che alla lunga può produrre degli sbilanciamenti dell’albero stesso. È quindi necessario prevedere un meccanismo che permetta una riconfigurazione totale dell’albero di routing.
Il momento in cui effettuare il refresh totale dell’albero viene deciso dal nodo Sink e viene fatto periodicamente con periodo TR. La durata
dell’intervallo TR può essere anche considerevole in quanto le operazioni
di mantenimento sopra descritte risultano molto simili a quelle di ricostru-zione totale dell’albero. Quindi, anche un accumularsi di modifiche parziali dell’albero, non porta ad uno sconvolgimento di quest’ultimo.
1 3 2 4 5 6 7 8 9 10 1 3 2 4 5 6 7 8 9 10 (b) (a)
= messaggio RTRST = messaggio RTREQ
Come mostrato in Figura 7.8-a, quando il nodo Sink decide che è il mo-mento di riorganizzare completamente l’albero di routing, inietta nella rete un messaggio di tipo RTRST .
Questo messaggio ha un contatore COUNT_CP che inizialmente viene settato dal Sink pari al numero di livelli dell’albero corrente di routing. Ogni nodo che riceve un messaggio RTRST inoltra tale messaggio ai propri
figli decrementando il contatore COUNT_CP. Inoltre ciascun nodo imposta un contatore interno che viene decrementato ad ogni Communication Pe-riod. Quando tale contatore diventa nullo il nodo abbandona lo schedule corrente e rimane nello stato awake in quanto inizia la procedura di crea-zione dell’albero. (Figura 7.8-b).
La procedura eseguita dal nodo Sink è la seguente: ( ){
(
)
{ ( )(
)
{(
)
RST SEND SEND RT _SinkRefreshPeriodico for_each Communication_Period if time.refresh trueRT crea _RT COUNT _CP Livelli _albero send 0,RT ,NO = = = 1 2 3 4 5
(
)
}(
)
( ) } } DI _FIGLIO COUNT_CP=COUNT_CP-1 if COUNT_CP=0 CREA_SinkROUNTINGTREE 6 7 8 9 10 11( ){
(
)
{ ( )(
)
( )(
RST)
{ RT _RefreshPeriodico for_each Communication_Period if message radio.receive if message.type RT COUNT_CP=message.count_CP = = 1 2 3 4 5 6(
)
}(
)
send 0,message,COUNT _CP COUNT _CP ,NODI _FIGLIO COUNT_CP=COUNT_CP-1 if COUNT_CP=0 CREA_ROUN = − 7 8 9 10 1 ( ) } } TINGTREE 11 12
In base al numero medio di messaggi scambiati nella rete prima della ri-costruzione dell’albero è possibile che tale riconfigurazione avvenga paral-lelamente alla normale attività della rete. I risultati delle interrogazioni ven-gono sempre recapitati al nodo Sink tramite il vecchio albero di routing e solo quando è pronto il nuovo albero viene utilizzata la vecchia configura-zione. In questo modo il flusso di dati verso il nodo Sink non viene interrot-to.
