CAPITOLO VI PROTOCOLLO PER LO SCHEDULING DELLA COMUNICAZIONE TRA NODI SENSORE

CAPITOLO VI

PROTOCOLLO PER LO

SCHEDULING DELLA

COMUNICAZIONE TRA NODI

SENSORE

Prima di proporre un metodo per ridurre l’energia di comunicazione è ra-gionevole capire se l’interfaccia network contribuisca significativamente al consumo energetico totale di un sistema mobile.

[Feeney] Dai test effettuati risulta che l’interfaccia network rappresenta una frazione significativa dell’energia consumata da un PC laptop e che addirittura è la causa predominante del consumo di energia in alcuni PDA. Studi recenti hanno dimostrato che, in un device basato su tecnologia Bluetooth, il costo di comunicazione copre più del 40% del consumo ener-getico totale.

Ci possiamo aspettare che il costo della comunicazione andrà ad inci-dere sempre di più sul consumo totale energetico man mano che i pro-gressi tecnologici porteranno a creare hardware low-power, sistemi ope-rativi e applicazioni efficienti dal punto di vista energetico.

La progettazione e la valutazione di protocolli di comunicazione efficienti richiede perciò la comprensione del comportamento dal punto di vista del consumo energetico dell’hardware addetto alla comunicazione. Il consumo energetico di una interfaccia dipende dalla sua modalità di funzionamento: nello stato di sleep non è possibile ne ricevere ne trasmettere dati, perciò il consumo energetico risulta molto limitato. Per essere capace di

tra-sulta perciò superiore in quanto devono essere alimentati un numero di circuiti decisamente maggiore rispetto a quando il device è nello stato sleep. La Tabella 6.1 mostra il consumo energetico di alcune interfacce che si trovano in commercio: da una prima analisi è facile notare che tra-smettere richiede più energia che ricevere ma la differenza è minore di un fattore due. Il consumo energetico di una interfaccia che si trova nello stato Idle è abbastanza alto e paragonabile a quello speso nel ricevere mentre risulta essere inferiore di un ordine di grandezza rispetta a quello speso nello stato sleep. In generale, il consumo energetico quando un’interfaccia trasmette, riceve o elimina un pacchetto, può essere suddi-viso in una parte proporzionale alla dimensione del pacchetto più una componente fissa che comprende il meccanismo di accesso al canale ed alcuni overhead (come ad esempio, nel protocollo 802.11, l’header del pacchetto e l’handshake tramite i pacchetti RTS/CTS/ACK).

La conclusione che deve essere tratta da queste considerazioni risulta ov-via: per ridurre il consumo energetico di una interfaccia network è neces-sario trovare il modo per permettere all’interfaccia di spendere il maggior tempo possibile nello stato sleep e ridurre il tempo speso nello stato Idle.

Interface Transmit Receive Idle Sleep Mbps

IEE 802.11 Interfaces (2.4 GHz) Aironet PC4800 1.4-1.9 W 1.3-1.4 W 1.34 W 0.075 W 11 Lucent Bronze 1.3 W 0.97 W 0.84 W 0.066 W 2 Lucent Silver 1.3 W 0.90 W 0.74 W 0.048 W 11 Cabletron Roamabout 1.4 W 1.0 W 0.83 W 0.13 W 2 Other Interfaces Lucent WaveLan 3.10 W 1.52 W 1.5 W - -

Come già descritto, il protocollo IEE 802.11 IBSS prevede un meccanismo di power saving che risulta molto efficiente nel modello delle reti ad hoc in cui in modo esplicito ogni nodo si associa direttamente con un IBSS. Infatti i test effettuati su una rete ad hoc completamente connessa ad un IBSS hanno dimostrato che questo meccanismo risulta molto efficiente com-portando un considerevole risparmio energetico. Le simulazioni effettuate in [Chen] sono volte a misurare le performance del meccanismo di power saving del protocollo IEEE 802.11 su una rete ad hoc multi-hop. I risultati indicano che la riduzione del consumo energetico in un ambiente ad hoc multi hop non risulta molto rilevante. Questa cosa, come osservato dagli autori, è dovuta al problema della gestione del traffico broadcast che co-stringe tutti i nodi a rimanere svegli per tutto il Beacon Interval in cui viene annunciato il broadcast.

6.1 Modello di Scheduling

Nel protocollo di scheduling progettato si è cercato di sfruttare la topolo-gia della rete ed in particolare l’organizzazione gerarchica ad albero che viene stabilita all’interno della rete stessa.

Infatti, i nodi della rete si organizzano in modo da coordinarsi tra loro e stabilire dei meeting point in cui scambiarsi messaggi. Negli altri istanti i nodi possono essere messi nello stato di sleep con conseguente risparmio dal punto di vista energetico.

La comunicazione padre-figlio avviene periodicamente ed è concentrata in un intervallo temporale prestabilito. Il periodo di comunicazione tra due nodi è definito Communication Period e a sua volta viene suddiviso in due intervalli temporali: Silence Interval e Talk Interval. Il Silence Interval

Talk Interval è l’intervallo di tempo in cui i nodi possono scambiarsi infor-mazioni (Figura 6.1). 1 3 COMMUNICATION PERIOD SILENCE INTERVAL TALK INTERVAL

Figura 6.1 Talk Interval e Silence Interval

Il nodo padre stabilisce le durate del Silence Interval e del Talk Interval e le comunica ai propri figli. A loro volta, i figli considerano il Silence Interval indicato dal padre come nuovo Communication Period e indicano ai rela-tivi figli il nuovo silent interval e Talk Interval (Figura 3). Questo accade solo in una versione semplificata dell’algoritmo in quanto non è detto che si riesca a far transitare le informazioni dai nodi foglia dell’albero fino al Sink in un solo Communication Period (Figura 6.2-a). In alcuni casi è quindi necessario ricorrere ad un approccio a pipeline (Figura 6.2-b). Come è possibile vedere dalla figura 2 e dalla figura 3 il Talk Interval tra un nodo e il proprio figlio è adiacente a quello tra il nodo stesso e il padre: questo per ridurre il numero di volte che un nodo cambia il proprio stato di funzionamento (awake->sleep, sleep->awake) e quindi per ridurre al mi-nimo la dissipazione di energia.

(a)

(b)

Figura 6.2- Approccio Standard vs Pipeline

Il nodo Sink varia col tempo il valore del Communication Period in base alle proprie esigenze e a quelle dei nodi della rete sottostante. Inoltre ogni nodo può variare la durata del Talk Interval con i propri figli.

Il Communicatio Period rappresenta essenzialmente il periodo di ricezione dei risultati delle interrogazioni da parte del Sink. Il nodo Sink ha cioè la necessità (dettata dall’applicazione) di ricevere risultati ‘freschi’ ogni Communication Period. 1 3 4 SILENCE INTERVAL TALK INTERVAL

Il Talk Interval è proporzionale al numero di messaggi che un nodo si aspetta di ricevere nel Communication Period successivo e quindi dipende dal numero e tipo (aggregato, event-based-query, selettività dei predicati) di interrogazioni attive sulla rete e dal numero di nodi presenti nel sottoal-bero del nodo padre.

Analizziamo adesso in dettaglio come avviene lo scambio di informazioni riguardanti il Communication Period tra i nodi appartenenti all’albero di Routing. Una volta terminata la costruzione dell’albero di Routing ciascun nodo è a conoscenza del proprio padre e degli eventuali nodi figlio. Le in-formazioni utili per permettere un corretto scheduling padre-figlio sono contenute in un particolare frame che periodicamente viene inviato dal pa-dre ai nodi figlio. Tale frame è detto Beacon Frame. In generale il Beacon Frame inviato durante l’m-esimo Communication Period contiene le infor-mazioni utili per lo scheduling nel m+1-esimo Communication Period. Tali informazioni sono:

• Durata CP del Communication Period • Durata SI del Silent interval successivo • Durata TI del Talk Interval successivo

Inoltre in un Beacon Frame possono essere presenti i seguenti campi op-zionali:

• Durata NCP del nuovo Communication Period • Durata NSI del nuovo Silent interval

• Durata NTI del nuovo Talk Interval

• Numero COUNT_CP di Communication Period mancanti al cambio di Impostazioni

Tali parametri risultano significativi soltanto in caso di cambio di durata del Communication Period e saranno presi in considerazione nel paragrafo 6.6 .

Sempre nel Beacon Frame vengono inserite anche delle informazioni utili per la procedura di aggancio di un nuovo nodo alla rete (descritta nel Ca-pitolo 7) come:

• Livello dell’albero a cui appartiene il nodo • Energia rimanente del nodo

Questi ultimi due parametri non verranno considerati nel seguito della de-scrizione in quanto non strettamente necessari al protocollo di scheduling. Come schematizzato in Figura 6.4 prendiamo in considerazione un gene-rico nodo j della rete che ha come padre il nodo i e come figlio il nodo k. Il Beacon Frame inviato dal nodo i al nodo j durante l’m-esimo Communica-tion Period da ora in poi verrà indicato con (BFij)m.

Inoltre, da ora in poi indicheremo con (Xij)m il valore del parametro X in-viato nel Beacon Frame dal nodo i al nodo j durante l’m-esimo Communi-cation Period mentre, più semplicemente, con Xij il valore del parametro X inviato nel Beacon Frame dal nodo i al nodo j .

. i j k (BF_ij)_m (BF_jk)_m

Figura 6.4 Schematizzazione invio Beacon Frame

In generale la procedura per lo scheduling dei nodi della rete risulta la se-guente (e mostrata in Figura 6.5):

( ){ ( ){ ( )

(

)

{ ( )

(

)

} = = 1 2 3 4 5 6 0 sin cr _rete while if time.talkFiglio true BF crea _RBF

send ,BF ,nodi _figlio ( )

(

)

{ ( )

(

)

( )

(

)

(

( )

)

(

)

( ) = = = = 7 8 9 10 11 if time.talkPadre true if radio.receive message

if message.type BF & & message.sorg ID _ padre set _timer } ( ) } 12 13 14 else sleep

Ciascun nodo cioè, durante il Talk Interval con i figli, invia un Beacon Frame ai propri figli (righe 3-6) mentre durante il Talk Interval con il padre riceve il Beacon Frame (righe 7-11). In seguito, in base alle informazioni contenute nei due Beacon Frame, viene impostato il timer di sistema e il nodo viene messo nello stato di sleep (riga 12) per poi risvegliarsi nel Communication Period successivo.

Naturalmente, durante i Talk Interval, i nodi si scambiano anche messaggi relativi alle applicazioni (Interrogazioni, risultati) che sono in esecuzione sulla rete. Questo tipo di comunicazione non viene considerata nella trat-tazione del protocollo.

i j k

Beacon Frame _{Sleep Talk}

Ogni nodo deve decidere la durata del Talk Interval con il proprio figlio . La condizione che deve essere rispettata è che la durata della comunicazione con i nodi figli sommata a quella con il padre non superi la durata del Communication Period, cioè, sempre in relazione alla Figura 6.4:

ij jk

TI +TI ≤CP (6.1)

Questa condizione risulta necessaria in quanto ogni Communication Pe-riod ciascun nodo deve essere capace di ricevere i dati dai figli e di reca-pitarli al padre. Nel caso in cui questa condizione non risulti soddisfatta è necessario limitare la durata di uno dei due Talk Interval e avvisare il pa-dre di questa situazione anomala tramite un messaggio di tipo SINCR_ERROR. Nel messaggio SINC_ERROR viene indicato il tempo extra di cui avrebbe bisogno il nodo figlio. Il padre può decidere, se possi-bile, di diminuire le pretese dal figlio (ad esempio diminuendo il numero di risultati richiesti al figlio per ogni Communication Period) oppure di inol-trare verso l’alto dell’albero il messaggio SINC_ERROR. Il problema può essere risolto in modo analogo a quanto appena descritto nei livelli supe-riori dell’albero oppure dal nodo Sink che può decidere di aumentare la durata del Communication Period.

Dopo aver inviato il Beacon Frame (BFjk)m al nodo k e ricevuto il Beacon Frame (BFij)m dal nodo i, il nodo j setta il proprio timer e cade nello stato sleep per risvegliarsi al successivo Talk Interval.

Le informazioni utili per la programmazione del timer sono le seguenti: • TSTART_FIGLIO= Istante temporale in cui ha inizio il prossimo Talk Interval

con il nodo figlio

• DURATAFIGLIO = durata del prossimo Talk Interval con il nodo Figlio • TSTART_PADRE= Istante temprale in cui ha inizio il prossimo Talk Interval

con il nodo Padre

La procedura che calcola i parametri appena elencati è la seguente: ( ){

( )

( )

(

)

( )

} = + = = + = 1 2 3 4 5 6 ij START_PADRE END _ PADRE _m

ij

PADRE _m

START_FIGLIO END _ FIGLIO jk _m FIGLIO _{jk m} set _ parameters T T SI DURATA TI T T SI DURATA TI

Infatti gli intervalli SI sono tutti riferiti a partire dall’istante in cui termina il Talk Interval corrente (cioè, in riferimento alla Figura 3, (SIij)m è da inten-dersi come intervallo di tempo a partire dalla fine del Talk Interval corrente con il padre e, analogamente, (SIjk)m a partire dalla fine del Talk Interval corrente con il nodo figlio). Nel protocollo di sopra le variabili TEND_PADRE e TEND_FIGLIO rappresentano gli istanti in cui terminano, rispettivamente, il Talk Interval con il padre e quello con il figlio nel Communication Period corrente.

I Beacon Frame vengono creati dal nodo padre tenendo conto di alcune semplici regole.

Un generico nodo della rete:

( )

(

) ( )

• • + = jk m jk jk _m jk _m Sceglie TI Calcola SI t.c. SI TI CP (6.2) Infatti un nodo padre deve poter comunicare con i figli una volta ogni Communication Period.

Quindi al procedura per creare un Beacon Frame è la seguente:

( ){

(

)

( )

} = − 1 2 3 jk _m jk _m crea _BF SI CP TI

Tale procedura non è la stessa inserita nel protocollo sincr_rete( ) sopra descritto in quanto i campi (SIjk)m e (TIjk)m possono essere modificati prima

dell’invio del Beacon Frame ai figli. La modifica di tali valori viene illustrata nei paragrafi successivi.

6.2 Diminuzione Talk Interval

Analizziamo il caso in cui un nodo decida di diminuire il Talk Interval con il figlio. Nella Figura 6.7 è rappresentato un esempio pratico di tale situa-zione (la rete di riferimento è quella di Figura 6.6). Il nodo 1 decide di dimi-nuire la durata del Talk Interval con i propri nodi figlio (2 e 3). Il nodo 3 si accorge di questo quando riceve, durante il quarto Communication Period, un Beacon Frame in cui i valori SI e TI sono cambiati rispetto a quelli dell’ultimo Beacon Frame ricevuto (TI diminuito e SI aumentato in base alla (6.2)). Il nodo 3 non può comunicare il cambiamento al proprio figlio fino al cammunication period successivo e quindi, durante il quinto Com-munication Period si ritrova ad avere uno slot di pausa tra il Talk Interval con il nodo padre e quello con il nodo figlio (nella figura indicato con un rettangolo celeste). In generale,durante gli slot di pausa, il nodo può deci-dere di spengersi oppure di rimanere nello stato Idle a seconda del nu-mero di slot di pausa che deve attendere ( il nunu-mero di slot di pausa è pari alla variazione del Talk Interval apportata dal nodo 1). Questo perché è comunque necessario considerare che il passaggio da un modo di funzio-namento ad un altro comporta un overhead di consumo e di latenza.

2 1

3

4

5

1 2 3 4 5

Comm. Period 3 Comm. Period 4 Comm. Period 5 Comm. Period 6 Comm. Period 7

=Beacon Frame =Talk interval =slot di pausa Figura 6.7 Diminuzione Talk Interval

In generale, quando si ha una diminuzione della durata del Talk Interval, viene effettuato uno shift verso destra di tutte le comunicazioni tra i di-scendenti del nodo che ha effettuato il cambiamento (come mostrato in Figura 6.8). Tale shift viene realizzato aumentando la durata del Silence Interval.

Lo shift avviene però gradualmente, infatti ad ogni Communication Period viene interessato un livello dell’albero.

A fronte di una diminuzione della durata del Talk Interval un nodo può de-cidere di aumentare a sua volta la durata del Talk Interval con il proprio fi-glio di un numero di slot al massimo pari all’ampiezza dello shift. In questo caso si riduce o eventualmente si annulla l’entità dello shift a destra dello scheduling con i figli.

Riassumendo ogni nodo, dopo aver inviato il Beacon Frame ai figli e dopo aver ricevuto il BF dal padre, è in grado di capire gli istanti temporali che caratterizzano il Communication Period successivo. In particolare alla fine di ogni Communication Period ogni nodo si calcola:

• TEND_FIGLIO: istante in cui, nel Communication Period successivo, ter-mina il Talk Interval con i nodi figlio (cioè TSTART_FIGLIO+DURATAFIGLIO) • TSTART_PADRE: instante in cui, nel Communication Period successivo,

Quando questi due istanti non coincidono siamo nella situazione descritta in precedenza in cui è necessario traslare la comunicazione con il figlio per fare in modo che TEND_FIGLIO e TSTART_PADRE vengano a coincidere. Questa cosa può essere ottenuta in due modi:

• Aumentando la durata del Silence Interval con i figli. • Aumentando la durata del Talk Interval con i nodi figlio.

2 1

3

4

5

SCHEDULAZIONE CHE NON DEVE SHIFTARE

SCHEDULAZIONE CHE DEVE SHIFTARE ENTITA' DELLO SHIFT

Figura 6.8 Diminuzione Talk Interval

In seguito è riportato la procedura che viene svolta da ogni nodo per con-trollare se è necessario effettuare uno shift a destra della comunicazione con i figli.

La variabile ∆TI rappresenta la variazione della durata del Talk Interval con il nodo figlio, cioè:

( ) ( )

₋

Il protocollo eseguito da ciascun nodo della rete per controllare se è ne-cessario effettuare uno shift a destra nella comunicazione con i figli è il seguente: ( ){

(

)

(

)

(

)

{ 1 2 3

START _ PADRE END _ FIGLIO

check_shiftDown

SHIFT _DOWN T T if SHIFT _DOWN & & TI>0∆

= − >0

(

)

{ 4 5 6 if TI SHIFT _DOWN TI SHIFT _DOWN SHIFT _DOWN =0 ∆ ∆ > − = } { } }

(

) (

)

} ∆ ∆ − = 7 8 9 10 11 12 13 14 jk _m jk _m else SHIFT _DOWN TI TI=0

SI = SI +SHIFT _DOWN //Aumento il Silince Interval

Alla riga 2 viene calcolata l’entità dello shift da effettuare. In seguito viene controllato se tale shift può essere compensato con un aumento dal Talk Interval con il figlio (righe 3-11 3). Infine viene aumentata la durata del Si-lence Interval della quantità opportuna (riga 13).

6.3 Aumento Talk Interval

Nel caso di aumento della durata del Talk Interval commentiamo l’esempio riportato in

Figura 6.9. Il nodo 3 decide di aumentare il proprio Talk Interval con il figlio e lo comunica ai figli durante il Communication Period m. A questo punto, per non avere sovrapposizioni tra i Talk Interval dei nodi discendenti, è necessario shiftare verso destra le comunicazioni tra i nodi che si trovano nei livelli inferiori dell’albero ( nodi 1,2,3). In pratica si ha, nel primo

Communication Period in cui si effettua l’aumento (Comm. Period m+1), un aumento della durata del Communication Period (pari all’incremento del Talk Interval) che poi però ritorna regolare nei Communication Period successivi (Comm. Period m+2).

=Beacon Frame =Talk interval 1

2 3 4 5

Comm. Period m Comm. Period m+1 Comm. Period m+2

=Aumento Talk interval

Figura 6.9 Aumento Talk Interval

Quindi , rispetto alla diminuzione della durata del Talk Interval, viene ef-fettuato uno shift in avanti della comunicazione tra i nodi antenati come mostrato in Figura 6.10. A differenza del caso precedente questa trasla-zione risulta molto più veloce.

Ogni volta che un nodo effettua un aumento della durata del Talk Interval è possibile che un figlio non rispetti più la (6.1). Relativamente alla Figura 9 questo problema potrebbe verificarsi quando il nodo 3 comunica al figlio 4 che il Talk Interval è aumentato di un valore ∆TI rispetto ai Communica-tion Period precedenti. Potrebbe accedere però cioè che:

34 45 Communication Period

2 1

3

4

5

SCHEDULAZIONE CHE NON DEVE SHIFTARE

SCHEDULAZIONE CHE DEVE SHIFTARE ENTITA' DELLO SHIFT

Figura 6.10 Aumento Talk Interval

È quindi necessario un meccanismo che informi il nodo padre dell’aumento massimo ( ∆TIMAX ) che è possibile effettuare. Per questo motivo, in ogni messaggio contentenente i risultati delle interrogazioni in-viato dai figli al nodo padre è presente una informazione aggiuntiva, che chiameremo FREE, che indica il massimo aumento ∆t che può essere supportato dal figlio. In pratica il nodo j calcola FREEj da inviare al padre i (in relazione alla Figura 4)

( ) ( )

j ij _m jk _m

FREE =Communication Period TI− − TI (6.4) Il nodo padre i, una volta ricevuto un pacchetto da almeno ogni figlio, è in grado di rilevare il valore del ∆TIMAX :

(

)

∆TI_MAX =MIN_{FIGLI j} FREE_j (6.5) Quindi, un nodo che ha intenzione di aumentare la durata del Talk Interval con i propri figli di un tempo ∆TI, attende per prima cosa di ricevere al-meno un messaggio da ciascun figlio e calcola, in base alla (6.5), il valore di ∆TIMAX e:

• se ∆TI ≤ ∆TIMAX aumenta di ∆TI il Talk Interval con i figli (Figura

• se ∆TI > ∆TIMAX aumenta di un tempo ∆TIMAX il Talk Interval con i figli e,

nel Talk Interval successivo con il proprio padre invia un frame SINC_ERROR contenente il valore ∆TI-∆TIMAX. (Figura 6.11-b)

SINCR_ERROR FRAME BEACON FRAME MSG 2 1 3 4 5 FREE =5 FREE =2 FR EE₌ 8 ∆t=2 2 1 2 3,4,5 ∆t=4 (b) ∆t=2 1 2 3,4,5 ∆t=2 (a)

Figura 6.11 Uso del campo FREE per aumentare la durata del Talk Interval

In seguito è riportata la procedura che deve essere eseguita da ogni nodo che ha intenzione di aumentare la durata del Communication Period con i propri nodi figlio di un tempo ∆TI.

La variabile FREE inizialmente contiene l’incremento massimo che può effettuare il nodo stesso che ha intenzione di aumentare il Talk Interval. Nel caso in cui non sia possibile effettuare l’intero aumento previsto è ne-cessario modificare i campi (SIjk)m e (TIjk)m in quanto si supone che siano già stati calcolari con la procedura crea_BF( ) descritta in precedenza.

( ){ ≠ 1 2 3 4 _i inc _ TI

//FREE inizialmente contiene l'aumento massimo che può supportare il nodo

for_each(nodo_figlio i)

if(FREE NULL) //cioè se ho già ∆

(

)

{ 6 if TI> TI∆ ∆ _MAX

(

) (

)

(

)

(

)

7 8 MAX jk _m jk _m MAX SI = SI + TI TI SINC_ERR=create_SE TI TI ∆ ∆ ∆ ∆ − −

( ) ( )

(

)

} } 9 10 11 12 MAX MAX jk _m jk _m TI= TI TI = TI TI TI ∆ ∆ ∆ ∆ − −

Come detto in precedenza, a fronte di un aumento della durata del Talk Interval vi è una shft a destra dello scheduling tra i nodi dei livelli superiori dell’albero. È quindi necessario che il nodo che ha effettuato l’aumento in-dichi al padre l’entità di tale shift. È per questo che, in ogni pacchetto in-viato da un nodo al padre è presente, oltre al campo FREE, anche il campo SHIFT.

Quindi ogni nodo, prima di inviare il Beacon Frame ai propri figli, attende di ricevere almeno un messaggio dai propri figli e calcola lo shift (SHIFT_UP) da effettuare sullo scheduling con il figlio stesso.

(

)

= _{FIGLI i}

SHIFT UP MAX_ _i SHIFT (6.6)

Quindi, il Beacon Frame che viene inviato ai figli presenterà un Silence Interval aumentato di una quantità pari a SHIFT_UP (vedi Figura 6.12 ). La procedura check_ShiftUP( ) effettua proprio questo controllo ed eventual-mente modifica il campo (SIjk)m.

( ){ ≠ = 1 2 3 4 5 i check _ShiftUP SHIFT_UP=0 for_each(nodo_figlio i)

if(SHIFT NULL) //cioè se ho già ricevuto un msg dal figlio i SHIFT _UP MAX SHIFT _UP ,S

(

)

(

) (

)

} 6 7 i jk _m jk _m HIFT _UP SI = SI +SHIFT _UP

BEACON FRAME MSG 2 1 3 4 5 SHIFT =0 SH IFT= 2 SH IF T= 1 SI+2 SHIFT=2 1 2 3,4,5

Figura 6.12 Aumento Talk Interval. Uso del campo SHIFT_UP

Ogni nodo calcola la quantità SHIFT da inviare al nodo padre nel se-guente modo: ( ){

(

)

} ∆ ∆ 1 2 3 4 5 Calcola _SHIFT SHIFT=SHIFT_UP if TI>0 SHIFT=SHIFT+ TI

In generale un nodo decide di aumentare o meno la durata del Talk Inter-val con i nodi figlio in base al numero di risultati che ha ricevuto dai figli durante il Talk Interval. Se, ad esempio, durante l’m-esimo Talk Interval, il generico nodo j ha ricevuto dal figlio k un numero di messaggi inferiore a quanto richiesto è necessario aumentare il tempo di comunicazione con il nodo. Per permettere di effettuare questo aumento a partire dal Commu-nication Period successivo (m+1) è necessario che il padre invii il Beacon Frame solo alla fine del Talk Interval del Communication Period m (se il Beacon Frame viene inviato all’inizio del Talk Interval il nodo j non è in grado di sapere se nel prossimo Communication Period avrà bisogno di un tempo maggiore per comunicare con i figli).

6.4 Fase di Startup

Allo startup della rete il protocollo di scheduling dei nodi risulta diverso da quello descritto fino ad ora. Infatti, una volta terminata la costruzione dell’albero di Routing tutti i nodi rimangono in ascolto del mezzo fino a quando non ricevono un Beacon Frame dal nodo padre. Descriviamo la procedura di scheduling facendo riferimento al segmento dell’albero di Routing riportato in Figura 6.13-a .

Ciascun nodo compie le seguenti azioni:

• Si mette in attesa di ricevere un Beacon Frame (BFij)0, che chiame-remo Zero-Beacon Frame, dal nodo padre.

• In seguito invia lo Zero-Beacon Frame (BFjk)0 al nodo figlio.

• Viene messo nello stato sleep fino al Communication Period succes-sivo

Quindi, come schematizzato in Figura 6.13-b il nodo 3 riceve il Beacon Frame dal nodo 1 ed in seguito lo invia al figlio 4.

Dunque la fase di startup risulta anomala rispetto alle altre fasi del proto-collo di scheduling in quanto vengono invertite le fasi di comunicazione con il padre e con il figlio.

1

2

3

4

5

(a) (b) =Zero-Beacon Frame =Talk interval 2 1 3 4 5 Comm. Period 0

Naturalmente lo Zero-Beacon Frame viene immesso per primo nella rete dal nodo Sink che decide la durata del Communication Period, cioè ogni quanto tempo nuovi risultati delle interrogazioni devono essere recapitati.

Nello Zero Beacon Frame il nodo padre (nodo i) stabilisce le durate del Silence Interval e del Talk Interval e le comunica ai propri figli (nodo j). A loro volta, i figli considerano il Silence Interval indicato dal padre come nuovo Communication Period e indicano ai relativi figli (nodo k) il nuovo silent interval e Talk Interval (Figura 13).

i j k SILENCE INTERVAL TALK INTERVAL ZERO BEACON FRAME

Figura 6.14 Comunicazione padre-figlio

Quindi, anche rispettando la condizione (6.1), può capitare che la durata del Communication Interval tra due nodi risulti maggiore del Silence Inter-val indicato dal padre.

(a) 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 9 10 8 10 9 (b)

Figura 6.15 Approccio a Pipeline

In questo caso è necessario fare ricorso ad un approccio a pipeline come mostrato in Figura 14). L’approccio a pipeline introduce comunque un ri-tardo nella consegna dei risultati al nodo Sink.

Allo startup della rete, quando viene usato l’approccio a pipeline, alcuni nodi non saranno attivi durante il primo Commnication Period ma entre-ranno in funzione in seguito (nella Figura 6.15 sono i nodi 6,7,8,9,10).

Riportiamo adesso la procedura eseguita dai nodi dopo aver terminato la costruzione dell’albero di Routing:

( ){ ( )

(

)

{ ( )

(

)

(

( )

)

(

)

{

( )

( )

( )

(

)

(

)

{ = = = + > 0 0 0 1 2 3 4 5 6 jk ij jk startup_rete if radio.receive message

if message.type BF & & message.sorg ID _ padre decidi TI if TI TI Communication _Period

(

( )

)

( )

( )

} = − 0 0 0 7 8 jk ij jk SINCR_ERR=create_SE Communication_Period- TI TI Communicatio _Period TI

( ) ( )

(

)

} } 9 10 11 12 13 set_SUparameters BF=crea_SUBF send 0,BF,nodi_figlio

Una volta ricevuto il Beacon Frame dal padre (righe 2-3) il nodo prima de-cide la durata del Talk Interval con il nodo figlio (riga 4) ed in seguito con-trolla se la condizione (6.1) è verificata. In caso negativo (riga 5) viene cre-ato un messaggio SINCR_ERROR che verrà invicre-ato al nodo padre du-rante il Comunicaiton Period successivo. La procedura set_SUparameters( ) ha il compito di calocolare gli istanti significativi per il prossimo Commu-nication Period ( TSTART_FIGLIO, DURATAFIGLIO, TSTART_PADRE, DURATAPADRE ):

( ){

( )

( )

( )

(

)

(

)

= + = = − < = 1 2 3 4 5 6 0 0 0 ij START _ PADRE RICEZIONE _ BF

ij PADRE

FIGLIO jk

FIGLIO

START _ PADRE ATTUALE

START _ FIGLIO ST set _SUparameters T T SI DURATA T DURATA T if T DURATA T T T } − = − + 7 8 9 FIGLIO ART _ PADRE FIGLIO START _ FIGLIO START _ PADRE

DURATA else

T T DURATA

Communnication _Period

La procedura crea_SUBF( ) ha il compito di creare il Beacon Frame che verrà poi inviato ai nodi figlio (riga 11):

( ){

( ) ( )

(

)

( )

} = = − − + 1 2 3 4 ij jk SP jk jk ATTUALE _CP crea _SUBF CP CP SI T T T CP 0 0 0 0

Il calcolo della durata del Silence Interval viene fatto prendendo in consi-derazione il caso in cui, in un approccio a pipeline, la comunicazione con il figlio debba essere rimandata di un Communication Period (riga 3)

6.5 Protocollo Generale di Scheduling

dei Nodi

Alla luce delle considerazione effettuate fino a questo momento e in base alle sotto-procedure elencate il protocollo per lo scheduling dei nodi di una Rete di Sensori organizzati in una struttura ad albero è il seguente:

( ){ ( ){

(

)

( ) { ( )

(

)

{ = = 1 2 3 4 5 6 7 sincronizza_nodi while true

if m //startup della rete startup_rete

else

while clock.awakeFigli true 0 ( )

(

)

{

( )

( ) ( )

( ) ∆ − = − 8 9 10 11 jk m jk _m jk _m if TI.finale true decidi TI

TI= TI TI //calcola variazione Talk crea_BF 1 ( ) ( )

(

)

( ) ∆ ∆ 12 13 14 15 Check_shiftDOWN Check_shiftUP if TI>0 inc_ TI se

(

)

( ) } } 16 17 18 nd 0,Beacon,nodi_figlio calcola_SHIFT ( )

(

)

{

(

)

(

)

19 20 21 22

while clock.awakePadre true

send_risu 0,..., SHIFT,FREE,nodo_padre if SINCR_ERROR frame ready

=

(

)

( )

(

)

23 send 0,SINCR_ERROR,nodo_padre if message=radio.receive ( )

(

)

(

)

(

)

( ) 24 25

if message.type BF & & message.ID _mit ID padre set_parameters = = − } ( ) ( ) 26 27 set_clock sleep

Da notare che la creazione e l’invio del Beacon Frame al nodo figlio (8-16) avviene solo alla fine del Talk Interval (riga 7) per permettere, come già descritto, un cambiamento del Talk Interval nel Communication Period successivo.

La sotto procedura set_clock( ) ha il compito di impostare il timer del nodo im modo che il nodo sia risvegliato all’inizio del Talk Interval con il figlio nel Communicaiton Period successivo.

( ){

(

)

} < = = 1 2 3 4 5 6

START_FIGLIO START _ PADRE START _ FIGLIO WAKE_UP

WAKE_UP START _ PADRE

set _clock if T T T T else T T

TWAKE_UP è l’istante in cui il nodo deve essere svegliato. Durante la fase di startup è possibile che per il primo Communication Period il nodo debba comunicare solo con il padre e che il Talk Interval con il figlio sia postici-pato al secondo Communication Period (righe2-5).

6.6 Cambio Communication Period

Passiamo ora ad analizzare il caso in cui c’è un cambiamento della durata del Communication Period.

Per effettuare questa operazione risultano importanti i campi NCP, NSI, NTI e COUNT_CP presenti nel Beacon Frame e introdotti in precedenza. Una situazione di questo tipo è riportata nella figura 6.16: il Communica-tion Period viene portato da 8 unità di tempo a 5 ed è il nodo Sink a co-mandare questo cambiamento (mentre la modifica della durata di un Talk Interval può essere effettuata da qualsiasi nodo della rete).

Le modifiche non avvengano immediatamente nel Communication Period successivo all’invio del Beacon Frame ma, per evitare sovrapposizioni di Talk Interval tra nodi a livelli diversi, è necessario attendere, prima di atti-vare il nuovo scheduling, un numero di epoch pari al numero di livelli che compongono l’albero di Routing per permettere a tutti i nodi di ricevere l’informazione prima che le modifiche siano messe in atto.

Quindi, parallelamente all’algoritmo di schedulazione descritto in prece-denza, vengono usati altri campi del Beacon Frame:

• NCP: analogo del campo CP • NSI: analogo del campo SI • NTI: analogo del campo TI

• COUNT_CP : numero di Communication Period mancanti al cambio di Communication Period. Questo contatore viene decrementato da ogni nodo prima di inviare il Beacon Frame al figlio.

Il Beacon Frame che viene introdotto nella rete dal nodo Sink ha le se-guenti caratteristiche: • = • = • = − • = − • = sr sr sr sr

NCP Nuovo Communicaiton Period NTI Nuovo Talk Interval

NSI NCP NT

NRI NCP NT

COUNT_CP livelli albero di routing

I nodi che ricevono un Beacon Frame che indica un cambiamento del Communication Period inoltrano tale pacchetto ai propri figli apportando delle modifiche al Beacon Frame precedentemente ricevuto:

(

) (

)

(

)

(

) (

) (

)

(

) (

)

(

)

(

) (

)

− − − • = • = • = − • = − • = − jk _m ij _m jk m jk _m jk _m jk _m jk _m ij _m jk _m jk _m ij _m NCP NCP

NTI Nuovo Talk Interval

NSI NCP NTI

NRI NRI NTI

COUNT_CP COUNT_CP 1 1 1 1 (6.8) NCP=5 COUNT_CP=3 NTI=2 NSI=3 NCP=5 COUNT_CP=2 NTI=1 NSI=4 NCP=5 COUNT_CP=1 NTI=1 NSI=4 1 2 3 4 5

Comm. Period m Comm. Period m+1 Comm. Period m+2 Comm. P. m+3

=Beacon Frame vecchio Comm.Period

=Talk interval =Beacon Frame nuovo Comm. Period

Figura 6.16 Cambio Communication Period (Diminuzione)

La procedura per calcolare i parametri del Beacon Frame da inviare al fi-glio è la seguente: ( ){

(

)

(

(

)

)

(

)

(

)

(

)

− − ≤ = − 1 2 3 1 1 ij jk _{m m} ij jk _{m m} jk _m crea _NBF decidi NTI NCP NSI NCP NTI

(

)

(

)

} − = − 4 5 1 1 ij jk _{m m} Count_CP Count_CP

In questa fase la durata del Communication Interval con il nodo figlio viene scelta in modo da rispettare la (6.1). L’invio di un eventuale messaggio SINCR_ERROR al padre verrà effettuato durante il primo Communication Period del Nuovo Communication Period.

In seguito riportiamo la procedura completa per lo scheduling dei Nodi Sensore. Rispetto alla procedura sincronizza_nodi( ) descritta in prece-denza sono state apportate poche modifiche (evidenziate in rosso)

( ){ ( ){

(

)

( ) { ( )

(

)

{ = = 1 2 3 4 5 6 sincronizza_nodi while true

if m //startup della rete startup_rete

else

while clock.awakeFigli true

0

(

)

( ) 7 10 8 9 COUNT_DOWN=COUNT_DOWN-1 if COUNT_DOWN=1 change_parametersFigl

// inizio TI con figlio

io el { ( )

(

)

{

( )

( ) ( )

∆ − = − 11 12 13 14 jk m jk _m jk _m se if TI.finale true decidi TI

TI= TI TI //calcola variazione Talk ( ) 1 ( ) ( )

(

∆

)

15 16 17 18 crea_BF Check_shiftDOWN Check_shiftUP if TI>0 ( ) ( ) } ∆ 19 20 inc_ TI calcola_SHIFT

(

)

} 22 23 send 0,BeaconFrame,nodi_figlio ( )

(

)

{

(

)

24 25

while clock.awakePadre true // inizio TI con padre send_risu 0,..., SHIFT,FREE,nodo_padre =

(

)

(

)

( )

(

)

( 26 27 28 29

if SINCR_ERROR frame ready

send 0,SINCR_ERROR,nodo_padre if message=radio.receive if

(

mess ( )

)

(

)

){

(

)

{ = = ≠ 30 31 if m

age.type BF & & essage.NCP NULL message Count_ .ID _mit ID _ p DOWN=messa adre ge.C ( ) } ( ) } ( ) 33 32 34 35 36 OUNT_CP set_paramete rs crea_NB F set _c lock ( ) } } 37 38 39 sleep

Rispetto all’altro protocollo è stato inserito un controllo (riga 30) per vedere se nel Beacon Frame ricevuto dal nodo padre è annunciato il cambio di Communication Period. In caso affermativo viene inizializzato un contatore (COUNT_DOWN) che tiene memoria del numero di Communication Pe-riod mancanti al cambio di impostazioni; infatti tale contatore viene decre-mentato all’inizio di ogni Communication Period (riga 7).

Nel Communication Period che precede il cambio di impostazioni (COUNT_DOWN=1, riga 8) viene spedito al nodo figlio un Beacon Frame contenente, nei campi CP, TI e SI, le nuove impostazioni. Infatti nella riga 9 viene invocata la sotto-procedura change_parametersFiglio( ):

( ){

( )

( )

(

)

} = = jk m jk _m jk jk _m jk change _ parametersFiglio CP =NCP TI NTI SI NSI 1 2 3 4 5