INDICE
INTRODUZIONE ... 5
-CAPITOLO 1
WIRELESS AD HOC NETWORKS... 7
-1.1
CARATTERISTICHE GENERALI ... - 7 -
1.2
APPLICAZIONI ... 9
-1.2.1 SCENARI APPLICATIVI... - 9 -
1.2.2 VANTAGGI VS SVANTAGGI ... - 13 -
1.3 ASPETTI DI RICERCA ... 15
-1.3.1 MEDIUM ACCESS CONTROL ... - 15 -
1.3.2 ROUTING... - 15 -
1.3.3 SICUREZZA... - 17 -
1.3.4 VALUTARE LE PRESTAZIONI DI UNA RETE AD HOC ... - 19 -
1.3.5 SCALABILITA’ ... - 19 -
CAPITOLO 2
POWER CONTROL ... 25
2.1 CDMA AD HOC NETWORKS: POWER CONTROL ... 25
2.2 TEORIA DEI GIOCHI... 26
-2.2.1 CONCETTI... - 27 -
2.2.2 CLASSIFICAZIONE DEI GIOCHI ... - 28 -
2.2.3 SOLUZIONE ... - 28 -
2.2.4 EQUILIBRIO DI NASH... - 29 -
2.2.5 EFFICIENZA DI PARETO ... - 29 -
2.3 TEORIA DEI GIOCHI PER RETI WIRELESS... 30
2.4 TEORIA DEI GIOCHI PER RETI AD HOC ... 31
-2.4.1 ALGORITMO AGGIORNAMENTO DELLE POTENZE... - 31 -
2.4.2 FUNZIONE UTILITA’... - 32 -
2.4.3 TRAFFICO: DATI VS VOCE... - 33 -
2.4.4 COSTRUZIONE... - 34 -
2.4.5 FORMALIZZAZIONE GIOCO: EQUILIBRIO DI NASH ... - 35 -
2.4.6 UTILITA’: SCELTA PARAMETRI ... - 38 -
2.4.7 ALGORITMO... - 41 -
CAPITOLO 3
MODELLO UTILIZZATO NELLE SIMULAZIONI ... 43
3.1 PARAMETRI FISICI E MODELLO DEL CANALE ... 43
3.2 MOTO ... 46
-3.2.1 MODELLI DI MOTO... - 46 -
3.2.2 MODELLO DI MOBILITA’ IMPLEMENTATO ... - 51 -
INDICE
CAPITOLO 4
RISULTATI SIMULAZIONI... 55
4.1 DESCRIZIONE... 55
4.2 EVOLUZIONE NEL TEMPO DELLA SIMULAZIONE ... 57
-4.3 EFFETTO DELLO SHADOWING SULLE PRESTAZIONI
DELL’ALGORITMO ... 62
4.4 EFFETTO DEL MOTO SULLE PRESTAZIONI DELL’ALGORITMO ... 66
4.5 STUDIO DEI PARAMETRI AL VARIARE DELLA DENSITA’ ... 78
-4.6 STUDIO DEI PARAMETRI AL VARIARE DELLA POTENZA INIZIALE IN
TRASMISSIONE ... 83
CONCLUSIONI... 89
BIBLIOGRAFIA... 91
-INTRODUZIONE
Nel corso dell’ultimo decennio hanno cominciato ad affermarsi ed a prender piede le cosiddette tecnologie wireless (“senza fili”) che, attualmente, si ritiene abbiano un enorme potenziale, tale addirittura da farle essere il mezzo delle telecomunicazioni del futuro.
La novità e la principale caratteristica di tale tecnologia è la possibilità di lavorare libera dai vincoli imposti dalle infrastrutture fisse delle reti di tipo wired. Tale peculiarità va a soddisfare l’esigenza sempre più sentita della mobilità, basta vedere ad esempio come sono aumentate negli anni le vendite di notebook e di PDA (Personal Digital Assistant).
Il primo obiettivo nello sviluppo di questa tecnologia è quello di rendere fruibile ad un PC mobile le applicazioni ed i servizi già disponibili per quello fisso (su tutti quelli classici di accesso al web e la posta elettronica). Successivamente, visto il successo dei sistemi senza fili (i.e. cellulari e WLAN), ci si è orientati verso la creazione e lo sviluppo di applicazioni pensate esclusivamente per tali sistemi, magari sevizi che vanno oltre la sola voce (videoconferenza, media interattivi, giochi real-time…).
La sfida per il futuro è dunque la ricerca di architetture di rete atte a soddisfare i bisogni diversi e a volte anche contrastanti di applicazioni eterogenee. La soluzione a tale sfida, almeno per ora, appare però abbastanza lontana: esistono infatti delle differenze enormi tra i PC mobili e quelli fissi. Tali differenze risiedono soprattutto nei limiti di autonomia, di capacità computazionale e di memoria dei dispositivi mobili. Proprio questi limiti hanno costretto i ricercatori a ripensare le soluzioni adottate nel caso fisso. Dal punto di vista degli obiettivi da perseguire la sfida più grande che viene presentata è quella della gestione delle risorse energetiche: i dispositivi mobili, rispetto a quelli fissi collegati alla rete elettrica, hanno una batteria di durata limitata che impone dei vincoli anche su altri aspetti del sistema.
D’altra parte, almeno fino ad ora, la tecnologia delle batterie non ha fatto progressi così significativi da liberarci da tale limitazione, quindi dobbiamo impegnarci a risparmiare ed a gestire al meglio
questa risorsa scarsa, pur garantendo prestazioni adeguate. Questo campo di ricerca, relativo ai sistemi energy-efficient, coinvolge diversi aspetti della rete, come vedremo meglio analizzandoli uno ad uno.
In questo elaborato viene trattata una particolare tecnologia wireless, quella delle Ad hoc Networks, che necessita ancora di molta ricerca. Questa tipologia di reti, infatti, ha delle caratteristiche peculiari che la rendono diversa da tutte le altre tecnologie senza fili, e dunque bisognosa di uno studio di soluzioni nuove rispetto agli standard già affermati. L’aspetto che caratterizza tale tecnologia è la completa assenza di infrastrutture di rete, e ciò comporta un’instabilità che complica tutti gli aspetti di rete e la loro gestione.
In questo lavoro di tesi viene ripreso inoltre un algoritmo di gestione efficiente delle risorse sviluppato per questo ambiente, il Power Control: esso viene testato studiando l’impatto sulle prestazioni dell’ambiente fisico e del moto.
La struttura della tesi è questa: nel Capitolo uno viene introdotto il concetto di rete Ad Hoc, spiegandone requisiti e dando uno sguardo generale alle problematiche principali, delle quali vengono analizzati gli aspetti più bisognosi di ricerca, nonché le soluzioni proposte fino ad oggi. Nel Capitolo due viene spiegato l’algoritmo di Power Control implementato, introducendo la Teoria dei Giochi su cui esso si basa e spiegandone i vari aspetti. Nel Capitolo tre, infine, viene descritto il lavoro simulativo che sta alla base dell’elaborato: in esso infatti vengono descritti l’ambiente che si è inteso simulare dal punto di vista fisico ed il modello di moto usato per simulare gli utenti mobili. Nel Capitolo conclusivo, il quattro, vengono proposti i grafici che rappresentano i risultati delle simulazioni effettuate.
CAPITOLO 1
Wireless Ad Hoc Networks
Innanzitutto la prima domanda che ci viene in mente è: cosa è una rete ad hoc?
Una rete ad hoc è semplicemente un insieme di dispositivi che stanno in uno spazio limitato e che sono in grado di comunicare fra loro in modo wireless, senza che per questo sia presente un’infrastruttura di rete. D’altra parte il nome “ad hoc” in latino vuol dire “per questo”, con l’accezione “appropriato al contesto” , dandoci un’idea del funzionamento di questo tipo di sistemi di comunicazione.
Per completezza riportiamo anche la definizione di rete ad hoc che viene fornita dall’IETF:
“A ‘mobile ad hoc network’ (MANET) is an autonomous system of mobile routers (and associated hosts) connected by wireless links – the union of which forms an arbitrary graph. The routers are free to move randomly and organize themselves arbitrarily; thus, the network’s wireless topology may change rapidly and unpredictably. Such a network may operate in a standalone fashion, or may be connected to the larger Internet.”
(“Una MANET é un sistema autonomo di router mobili e dei loro host associati, connessi con collegamenti di tipo wireless che sono uniti formando un grafo di forma arbitraria. Tali router sono liberi di muoversi casualmente e di auto organizzarsi arbitrariamente, sebbene la topologia wireless vari rapidamente ed in modo imprevedibile. Tale rete può operare da sola oppure essere connessa alla rete Internet”)
1.1
CARATTERISTICHE GENERALI
Le reti ad hoc, o anche MANET (Mobile Ad hoc NETworks), possono essere essenzialmente di due tipi: “pure” o ibride. Nel primo caso si intende un gruppo di terminali disposti casualmente, eventualmente liberi di muoversi, indipendenti, che comunicano tra loro; nel secondo caso, invece, si intende un sistema come quello di cui sopra, ma nel quale uno o più nodi sono connessi ad un sistema cellulare oppure ad uno cablato. Ad ogni modo, l’assenza di infrastruttura costringe i nodi
stessi ad occuparsi in modo distribuito dei vari aspetti della rete quali, ad esempio, il controllo e la gestione e, soprattutto, dei vari collegamenti (istaurazione, mantenimento e routing).
Uno dei vantaggi di questi tipo di reti è che i terminali possono fungere non solo da end-system (trasmettitore o ricevitore), ma anche da relayer (cioè da nodi intermedi) che inoltrano i pacchetti quando il trasmettitore ed il ricevitore non sono in grado di comunicare direttamente. Questo importante ed interessante aspetto consente ad una coppia di nodi di comunicare anche se essi sono l’uno fuori dal range trasmissivo dell’altro. Proprio per quest’ultima caratteristica le reti ad hoc vengono chiamate anche “multi-hop wireless networks”, introducendo ulteriori problematiche, come quella della scelta del percorso ottimo tra sorgente e destinazione ed i criteri sui quali basare tale scelta.
La caratteristica che rende unica questa tecnologia è la completa assenza di un’unità amministrativa centrale, a differenza delle reti cellulari nelle quali sono presenti le base station: questo aspetto le rende particolarmente flessibili ed adattabili alle variazioni, sia del traffico, sia delle condizioni fisiche. In particolare si vede come questo tipo di reti può essere formato in qualsiasi momento e condizione e che l’eventuale perdita di un nodo non ne inficia la connettività, i.e. la capacità per un nodo qualsiasi della rete di istaurare una connessione con un altro nodo qualsiasi. Si capisce anche perché, grazie a tali caratteristiche di robustezza, flessibilità, facilità di formazione e supporto alla mobilità, tali reti vengano considerate adatte a situazioni nelle quali, altrimenti, non sarebbe possibile comunicare per ragioni di complessità, costo e tempo.
WIRELESS AD HOC NETWORKS
1.2
APPLICAZIONI
Come spesso accade, le prime applicazioni delle tecnologie ad hoc si sono avute in campo militare: esse infatti soddisfano, con le proprie qualità, i bisogni più immediati delle comunicazioni sul campo di battaglia, di natura prettamente dinamica.
Oggi, invece, la ricerca si sta concentrando su ambiti diversi. In particolare lo scopo degli studi è quello di trovare un’alternativa e/o un’estensione della rete wired già presente. Una rete ad hoc, infatti, può risultare utile nei casi nei quali, per motivi economici, non è conveniente costruire un’infrastruttura, oppure l’infrastruttura è presente ma non accessibile, o ancora non è proprio necessaria. Un altro aspetto interessante è la possibilità di creare un sistema simil cellulare. Le reti ad hoc, infatti, possono essere usate in combinazione delle WLAN, per range estesi, ma anche di tecnologie con range più ridotti, come il Bluetooth e quelle basate sullo standard 802.11.
Una naturale applicazione per queste reti può essere in contesti di comunicazione “spontanea”, quando gruppi di persone, dotate di terminali come PC portatili, PDA, smartphone, si trovano fisicamente nello stesso luogo e hanno l'esigenza di comunicare tra loro, senza doversi necessariamente appoggiare su un'infrastruttura di rete esistente fornita da terzi. Se ci vogliamo spingere un po' più in là con l'immaginazione, si arriva agli scenari di ubiquitous computing, in cui sistemi ed applicazioni che si trovano in un certo luogo si possono organizzare e gestire autonomamente per offrire servizi in modo trasparente agli utenti.
1.2.1
SCENARI APPLICATIVI
Andiamo ora a fare una breve rassegna degli scenari per i quali le reti ad hoc risultano particolarmente adatte e nei quali perciò vengono impiegate e sviluppate.
• Reti di sensori: sono reti formate da un insieme di sensori, usati solitamente per la raccolta dati (metereologici, geografici, ambientali, etc.) oppure per l’automazione, in grandissimo numero, collegati ad un’unità centrale che elabora i dati ricevuti;
• Reti per servizi d’emergenza: in genere hanno la funzione di sostituire la rete fissa in caso d’emergenza, cioè nelle occasioni nelle quali essa viene danneggiata a causa di qualche disastro, oppure vengono impiegate in operazioni di salvataggio e ricerca;
• Applicazioni di tipo commerciale: essenzialmente per il pagamento elettronico della merce da qualsiasi punto della rete e/o per l’accesso alle informazioni sulla merce esposta;
• Reti interveicolari: in questo caso i nodi sono sia i veicoli che transitano sulle strade, sia le strutture fisse che si trovano lungo di esse: la funzione di questo tipo di reti è quella di dare ai guidatori informazioni sulle condizioni del traffico sulla strada e di consigliare loro eventuali percorsi alternativi in caso di congestioni.
• Home networks: danno all’utente l’opportunità di svincolarsi dai limiti di accessibilità, offrendogli la possibilità di accedere alla rete da qualsiasi punto della casa. Un’interessante potenzialità per questo tipo di rete è quella di collegare fra loro tutti i dispositivi elettronici presenti nella casa che in tal modo potrebbero essere programmati e comandati a distanza (si parla di home automation);
• Enterprise networks: vengono istallate nelle aziende in uno o più edifici per facilitare l’istaurazione di comunicazioni fra i dipendenti in modo economico e che supporta la mobilità;
• Applicazioni didattiche: sfruttano la capacità dei nodi delle MANET di comunicare e scambiarsi i dati in ambienti limitati. Sono dunque perfette per il contesto di una lezione dove una rete ad hoc potrebbe permettere al docente di inviare dati e materiale didattico agli studenti, i quali, a loro volta, possono interagire con lui, magari facendogli delle domande.
WIRELESS AD HOC NETWORKS
Figura 1.3: Rete per servizi di emergenza
Figura 1.4: Rete per applicazioni commerciali
Figura 1.6: Home Network
Figura 1.7: Enterprise Network
WIRELESS AD HOC NETWORKS
1.2.2
VANTAGGI VS SVANTAGGI
Sviluppando i sistemi di tipo ad hoc nei vari ambienti e nelle varie situazioni si devono avere chiari i vantaggi e gli svantaggi apportati dall’uso di tale tecnologia.
Per quanto riguarda i vantaggi bisogna anche considerare da che punto di vista si guarda la tecnologia, cioè se la si guarda dal punto di vista dell’utente che ne deve fruire o del fornitore che la deve progettare ed istallare.
Dal punto di vista degli utenti i vantaggi sono:
• Supporto alla mobilità, con la possibilità di comunicare always and everywhere;
• Minima richiesta di infrastrutture che permette un allestimento semplice ed economico; • Opportunità, per un insieme di utenti, di condividere risorse;
• Facilità di organizzazione dei soccorsi in caso d’emergenza. I vantaggi per i fornitori, inoltre, sono:
• Semplicità ed economicità per estendere la rete laddove e/o quando portare le infrastrutture risulta complesso e costoso;
• Riduzione dei costi dovuta all’assenza di infrastrutture che, oltre ad essere allestite, richiedono anche una certa manutenzione;
• Efficienza incrementata delle infrastrutture già presenti, dato che esse risultano alleggerite dal carico di lavoro del trasporto locale, con migliori prestazioni (sopratutto a livello di capacità);
• Efficienza anche semplicemente come soluzione temporanea, in vista di un eventuale estensione dell’infrastruttura.
Esistono, però, diversi svantaggi, dovuti soprattutto alla diversità di tale tecnologia rispetto a quelle sulle quali si è lavorato sino ad ora.
Tali svantaggi sono tutt’ora oggetto di ricerca e ci costringono ad elaborare soluzioni diverse rispetto a quelle consolidate e vincenti nell’ambito di Internet. L’approccio layered proprio del protocollo IP, che si è dimostrato adatto ed efficiente e che ci ha permesso di creare protocolli robusti e scalabili, si è dimostrato fallimentare e perdente di fronte alla sfida delle MANET. Questa sconfitta si spiega con la difficoltà (diciamo pure l’impossibilità) di isolare le varie funzionalità in un solo livello protocollare. L’ambiente wireless in generale, la struttura e la tecnologia delle reti ad hoc in particolare, ci suggeriscono, anzi, di seguire proprio la strada opposta: far agire in modo congiunto e coordinato i vari livelli e sfruttarne al meglio le interdipendenze.
• Assenza di infrastruttura: rende del tutto inadeguati approcci e protocolli sviluppati per altre reti;
• Topologia dinamica: la rete può cambiare topologia e riconfigurarsi in modo e velocità non prevedibili a priori. Questo implica la perdita di pacchetti (spreco di risorse) e necessita di un routing che in qualche modo insegua le variazioni della rete;
• Limiti del livello fisico: le reti ad hoc sfruttano la banda intorno ai 2.4 GHz, nota anche come ISM2, che non ha bisogno di licenza per trasmettervi (unlicensed): il problema risiede essenzialmente nel fatto che l’interfaccia radio di ogni nodo trasmette in modalità broadcast, incrementando così il numero delle collisioni, le quali causano un aumento nello spreco di potenza e riducono la capacità. E’ opportuno aggiungere anche che il canale di comunicazione presenta nel nostro caso effetti che non esistono o sono meno drammatici nelle reti cablate, cioè fading, shadowing, interferenza e ovviamente il rumore;
• Caratteristiche diverse dei nodi: non si deve dimenticare che stiamo trattando sistemi formati da un insieme di nodi eterogeneo. I nodi possiedono infatti capacità diverse in trasmissione ed in ricezione, a volte addirittura trasmettono su bande diverse e molto spesso hanno potenza di calcolo e processing diverse;
• Sicurezza: le MANET, sotto questo aspetto, non fanno eccezione rispetto alle altre reti wireless, presentando problemi dovuti alla debolezza intrinseca del mezzo di comunicazione radio, soprattutto la facilità di intercettarne le comunicazioni. Tali debolezze, oltretutto, sono acuite dalla particolarità di questi sistemi, cioè l’assenza di strutture centrali che gestiscano la sicurezza;
• Robustezza e affidabilità della rete: la peculiarità di queste reti, cioè l’assenza di una struttura centralizzata, garantisce una flessibilità unica a questo tipo di sistemi. Tale vantaggio viene pagato con una minore robustezza e un’affidabilità inferiore dovute all’assenza di un’unità centrale che si occupi del monitoraggio della rete;
• Scalabilità: il problema della scalabilità si pone nelle situazioni nelle quali il numero dei nodi della rete cresce notevolmente, come nel caso delle sensor network;
• Potenza limitata: come accennato all’inizio della trattazione delle MANET, uno degli aspetti maggiormente limitanti è proprio la ristretta riserva di energia disponibile per i nodi. Questo aspetto è particolarmente sentito poiché i nodi, oltre che funzionare da end-system, partecipano attivamente al routing.
WIRELESS AD HOC NETWORKS
Abbiamo ora ben chiari gli aspetti vantaggiosi e svantaggiosi delle reti ad hoc. Nell’osservare gli svantaggi e le problematiche ci si accorge che essi richiedono soluzioni che o non sono state trovate, o non sono del tutto soddisfacenti.
1.3 ASPETTI DI RICERCA
Ci rivolgiamo adesso verso gli aspetti delle MANET che, ad oggi, sono oggetto di ricerca e studio al fine di permetter a questa tecnologia di affermarsi definitivamente e soprattutto di diffondersi su ampia scala.
1.3.1 MEDIUM ACCESS CONTROL
La problematica del controllo di accesso al mezzo per le reti ad hoc è stata attaccato sfruttando l’esperienza acquisita nella creazione dello standard 802.11 (b e anche g), il quale sfrutta proprio la stessa banda delle ad hoc networks, e che si basa su un protocollo a contesa di tipo CSMA (Carrier
Sense Multiple Access).
Solamente in tempi più recenti si è iniziato a pensare a soluzioni diverse per l’accesso al mezzo. In questo elaborato, ad esempio, vengono prese in considerazioni e studiate reti basate sul CDMA (Code Division Multiple Access) ed in letteratura sono disponibili esempi e proposte di protocolli innovativi basati sul CDMA, si vedano [38] [39] [40].
1.3.2 ROUTING
La diversità del tipo di rete che andiamo a trattare ci porta inevitabilmente ad affrontare con occhi nuovi il problema del routing: è proprio questo l’aspetto della rete sul quale ricadono le conseguenze maggiori della mobilità e delle limitate risorse energetiche. Affrontare questi due aspetti, oltretutto, richiede due opposti comportamenti: la mobilità, e quindi la topologia dinamica, richiede uno scambio di informazioni costante, che insegua tali variazioni, mentre la limitatezza delle risorse richiede che tale scambio venga il più possibile limitato.
Riassumendo, gli obiettivi che devono essere raggiunti dal nostro protocollo sono: - Approccio distribuito;
- Routing aggiornato; - Overhead limitato;
- Ritardo end-to-end limitato;
- Possibilità di entrare nello stato Sleep; - Sicurezza;
Anche in questo caso si è cercato di adattare l’esperienza pregressa per risolvere questi problemi, ossia si è tentato di adeguare gli algoritmi già creati per le reti wired al nuovo contesto.
Una prima classificazione degli algoritmi che viene fatta è in base alla modalità con la quale vengono ottenute e mantenute le informazioni sul routing: gli algoritmi possono essere di tipo proattivo, di tipo reattivo oppure misto [2] [5] [12] [14] [21] [22] [31].
• Proattivi: questo approccio presuppone che ogni nodo abbia una tabella, aggiornata
costantemente, con le informazioni sui collegamenti verso tutti gli altri nodi (table driver). E’ evidente che questo approccio comporta un impiego elevato di risorse, eccessivo in questo caso, che va limitato in qualche modo. Il vantaggio nell’uso di questo tipo di protocolli sta nel limitato ritardo end-to-end e nell’immediatezza dell’istaurazione della connessione. Fra i più importanti e sviluppati protocolli di questa categoria abbiamo Destination Sequenced Distance Vector (DSDV) e Optimized Link State Routing (OLSR) (vedi RFC 3626);
• Reattivi: questo approccio, invece, è opposto, in quanto i nodi ignorano totalmente la
posizione del destinatario fin quando non devono comunicarci, quindi il routing viene stabilito su richiesta (on demand). Tale approccio introduce un ritardo end-to-end maggiore dovuto alla fase di route discovery, ma ha il vantaggio non da poco di limitare le risorse impiegate. A questo genere di protocolli appartengono Dynamic Source Routing (DSR) e Ad hoc On demand Distance Vector (AODV) (vedi RFC 3561);
• Ibridi: questo approccio cerca di ottimizzare i precedenti due, usando il primo per i nodi
“vicini” e il secondo per quelli “lontani”. In questo caso resta comunque da dare una soddisfacente definizione della caratteristica vicino/lontano. Il rappresentante più noto di questa classe di protocolli è Zone Routing Protocol (ZRP).
Questa classificazione, pur essendo quella principale, non è unica. Esistono infatti altre classi di protocolli, magari in base a delle migliorie apportate ai precedenti protocolli:
• Geografici: in questi protocolli si sfrutta la conoscenza della posizione geografica del nodo
che deve trasmettere e quella del nodo che deve ricevere per limitare il flooding, cioè l’inondazione di messaggi di segnalazione verso tutta la rete per scoprire il percorso verso il ricevitore [3] [7] [9] [15] [18] [23]. Un modo per conoscere le posizioni dei nodi può essere l’uso del GPS . Un esempio di protocollo geografico è Location-Aided Routing (LAR); • Gerarchici: in questi protocolli i nodi vengono raggruppati in cluster e viene eletto un nodo
che va a svolgere un ruolo analogo a quello della Base Station nelle reti cellulari [4] [11]. In questo modo, sacrificando parte della flessibilità della rete ad hoc, si ottiene una struttura
WIRELESS AD HOC NETWORKS
centralizzata, che rende più semplice la gestione dei vari aspetti della comunicazione e che consente inoltre di implementare protocolli maggiormente scalabili. Fra questo tipo di approcci vale la pena citare Hierarchical State Routing (HSR) e Global State Routine (GSR);
• Power-Aware: in questi protocolli i nodi sono coscienti della limitatezza delle loro risorse
energetiche e questa consapevolezza permette loro di decidere quando stare accesi, cioè idle oppure spenti oppure di scegliere il percorso meno dispendioso da un punto di vista della potenza [10] [19] [56]. Il più importante fra questo tipo di protocolli è Power-Aware Routing Optimized (PARO).
Fra le varie altre migliorie proposte per il routing ci sono quelle di associarlo al MAC [10], cioè un approccio di tipo Cross-Layer [26] [27], oppure l’uso di antenne di tipo beamforming per migliorare le prestazioni del protocollo [16]. Sono state proposte anche delle soluzioni che associano direttamente il routing al Power Control [19] [25] [28].
Oltre al tentativo di limitare il flooding [8] di cui abbiamo già parlato, vale la pena sottolineare un altro nuovo aspetto del routing che non è ancora emerso: la scelta delle opportune metriche nella scelta del percorso ottimo [10] [17] [29] [32] [33]. Quest’ultimo aspetto risulta nuovo rispetto all’ambiente wired, nel quale l’unico criterio di minimizzazione del percorso è il cosiddetto
hop-count. Ora, infatti, i percorsi non sono tutti uguali e ottimizzare il percorso trasmettitore-ricevitore
non vuol dire più scegliere quello a minimo numero di salti. Un esempio di questo approccio è l’algoritmo di Dijkstra “pesato” dove gli hop non valgono più tutti 1, ma assumono valori diversi a seconda delle loro caratteristiche e dell’aspetto che si vuole ottimizzare.
1.3.3 SICUREZZA
Trattiamo ora, come già detto, un problema molto sentito per tutte le tecnologie di tipo wireless. Ripassiamo velocemente gli aspetti specifici della sicurezza:
• Confidentiality: non deve essere in alcun modo possibile intercettare le comunicazioni tra due nodi;
• Access Control: l’accesso alla rete deve essere consentito ai soli nodi autorizzati;
• Data Integrity: non deve essere assolutamente possibile modificare i dati delle comunicazioni altrui;
• Denial of Service: non deve essere possibile per nessuno interrompere il servizio offerto dalla rete.
Vediamo ora come e perché le reti wireless in generale, e quelle ad hoc in particolare, sono così vulnerabili:
• Vulnerabilità del canale radio: il canale è per sua natura “broadcast”, e ciò rende facile sia intercettarne le comunicazioni, sia immettervi dati maligni;
• Vulnerabilità dei nodi: i nodi non godono di alcuna protezione fisica, quindi sono facilmente attaccabili;
• Assenza infrastruttura: la struttura “piatta” della rete è causa dell’assenza di autorità centrali che garantiscano le fasi di autenticazione e certificazione. Quest’ultima, a differenza delle altre, è una debolezza esclusiva delle reti ad hoc;
• Topologia dinamica: acuisce le difficoltà di gestione degli aspetti della sicurezza;
• Limitate risorse computazionali: precludono ai nodi l’utilizzo di algoritmi di security troppo complessi dal punto di vista del calcolo.
Per finire facciamo ora una breve descrizione dei possibili tipi di attacchi alla sicurezza. La prima distinzione da fare è quella tra attacchi attivi ed attacchi passivi. I primi sono più facilmente rilevabili dal momento che consistono nell’immissione di dati fasulli e/o malvagi nella rete. A questa categoria appartengono gli attacchi di spoofing, modification, fabrication ed il disclosure attack. Gli altri, quelli passivi, sono molto più difficili da rilevare (come ci si accorge ad esempio se una comunicazione viene spiata senza essere alterata?). In questi casi, oltre a spiare la comunicazione, il nodo potrebbe tenere un comportamento scorretto, rifiutando per esempio di inoltrare le informazioni sulla rete, inficiandone così il funzionamento.
In questi casi, più che parlare di nodo malicious (malevolo), è opportuno parlare di nodo selfish (egoista), che risparmia le risorse, non con l’intenzione di danneggiare la rete, ma per usarle solo per sé stesso. Chiaramente si devono elaborare meccanismi atti ad arginare comportamenti del genere che, se adottati da ogni nodo, impedirebbero alla rete stessa di esistere. Un paio di possibili approcci per evitare questi comportamenti sono un meccanismo di controllo tra nodi, dove ogni nodo viene controllato da tutti i propri vicini, ed un meccanismo di reputazione che, facendo uso di incentivi e disincentivi, va a favorire chi si comporta bene e sfavorire chi si comporta male.
Dal punto di vista della crittografia classica per la protezione dei dati si deve considerare, oltre alla limitatezza delle risorse computazionali, anche l’assenza di un’autorità centrale che si occupi della distribuzione delle chiavi segrete. Per ovviare a questa assenza si è pensato alla formazione di una self-organized public-key infrastructure.
Un ultimo aspetto da considerare, inoltre, è quello della sicurezza abbinata al routing, ovvero del
WIRELESS AD HOC NETWORKS
hoc sia ancora una volta quella di una visone complessiva dei vari aspetti della rete, piuttosto che di una visone separata e stratificata.
1.3.4 VALUTARE LE PRESTAZIONI DI UNA RETE AD HOC
Un limite attuale, nello studio e nella progettazione delle MANET, è la difficoltà che si incontra nel valutarne effettivamente le prestazioni, e di capire come quest’ultime dipendano da certi parametri e grandezze variabili della rete e dell’ambiente.
In generale, per misurare le prestazioni di una rete, si seguono due strade: si possono effettuare delle misurazioni sul sistema reale oppure si possono usare modelli che ne simulano il comportamento. Nella scelta tra queste due possibilità si devono ponderare gli aspetti vantaggiosi e quelli svantaggiosi delle due vie. La scelta di effettuare delle misure dirette sulla rete presenta numerosi limiti: innanzitutto effettuare le misure su di un nodo introduce delle perturbazioni che possono alterare il comportamento dell’intera rete. Tale approccio, inoltre, risulta estremamente più costoso di quello simulativo, non permette di valutare l’impatto effettivo dei singoli parametri sulla rete ed è per forza di cose spazialmente limitato. Si deve comunque tenere di conto del fatto che le misurazioni, però, trattano e lavorano su un modello reale, comprendendo quindi aspetti che nei modelli simulativi vengono per forza di cose trascurati, ma che condizionano anch’essi il comportamento della rete.
Un discorso opposto va fatto su l’uso dei modelli nel calcolo delle prestazioni. Tale approccio, infatti, permette sicuramente di isolare meglio i vari aspetti del problema ma, per contro, è costretto ad introdurre delle semplificazioni per alcuni aspetti della rete, e ciò li discosta dalla realtà. Andiamo dunque a pagare la maggiore flessibilità offerta dal modello con una qualità delle misure inferiore.
La simulazione delle MANET ha indubbiamente conseguito un buon grado di maturità anche se, andando a confrontare i risultati ottenuti con l’uso dei simulatori più comuni in commercio (GloMoSim, opnet, ns2), ci accorgiamo dell’assenza di univocità, anzi, in alcuni casi, essi sono persino opposti.
Un altro aspetto rilevante, inoltre, è quello della scelta delle metriche per misurare le prestazioni della rete ed anche in questo caso esistono in letteratura esempi di scelte diverse, mirate ad evidenziare particolari aspetti della rete in esame.
1.3.5 SCALABILITA’
La scalabilità è la capacità del sistema di “crescere”, ovvero la capacità che il sistema ha di fornire le stesse prestazioni al crescere del numero di nodi. Nel nostro caso è immediato notare come una
grandezza poco scalabile è la capacità complessiva della rete. Per esempio, se prendiamo una rete non cooperativa dove tutti i nodi usano antenne isotropiche, il throughput decresce come ο
(
1 / N)
( N = numero complessivo dei nodi) [90]. Per spiegarlo con un esempio numerico, se ho 100 nodi, ognuno di essi avrà un throughput pari ad 1/10 di quello teorico. Un modo per alleviare questo problema è l’uso di antenne direttive o, ancora meglio, di tipo smart.Un’altra problematica è quella legata al routing, il quale, sia esso di tipo proattivo che reattivo, non scala facilmente, basti pensare alla quantità di risorse necessarie per avere una conoscenza totale ed aggiornata della rete nel primo caso o ai ritardi introdotti dalla fase di route discovery nel secondo. Una possibilità per rendere il routing scalabile può essere quella di introdurre delle gerarchie: l’uso di un routing gerarchico, come nel caso degli algoritmi di clustering [42], dove i nodi sono raggruppati in sottoinsiemi, permette di limitare il consumo di risorse impiegate per la conoscenza della rete e per il suo update continuo. In questo modo, dunque, si sceglie di sacrificare una parte della flessibilità della rete per aumentare l’efficienza energetica del routing, anche per reti di grandi dimensioni e, soprattutto, con un elevatissimo numero di nodi.
1.3.6 RISPARMIO DI POTENZA
Come detto in apertura si deve sempre tenere di conto del fatto che i dispositivi mobili che stiamo trattando hanno a disposizione una riserva energetica piuttosto limitata. Ogni algoritmo per queste reti, di qualsiasi aspetto si occupi, deve contemplare questo vincolo. Si ricordi, inoltre, che, poiché il nodo, oltre che trasmettere e ricevere, partecipa al routing, il nostro obiettivo è un compromesso tra la durata della vita del nodo (da massimizzare minimizzando il consumo di energia) e le prestazioni complessive della rete (da massimizzare coinvolgendo il nodo nelle attività legate al routing).
Ogni considerazione che possiamo fare sul risparmio energetico deve partire dalla coscienza del fatto che esso è perseguibile solo tramite uno sforzo congiunto di più livelli protocollari. Andiamo ora a descrivere le dinamiche del consumo di potenza nelle reti ad hoc: le due operazioni che richiedono consumo di potenza sono il processing dei dati e la fase di comunicazione radio. Se, però, andiamo a vedere la percentuale di potenza consumata dalle due operazioni, notiamo come l’energia viene spesa quasi tutta nelle operazioni di comunicazione e che quella spesa per il processing risulta dunque trascurabile. Ci dobbiamo perciò sforzare di ridurre i consumi sull’aspetto di radiocomunicazione. Ovviamente non è possibile adottare soluzioni che apparirebbero scontate per una rete dotata di infrastrutture, come tenere spenti o inattivi i terminali a potenza limitata e riversare l’onere computazionale e comunicativo sull’infrastruttura, libera da vincoli energetici, proprio perché quest’ultima è assente!
WIRELESS AD HOC NETWORKS
La ricerca sul risparmio energetico si concentra fondamentalmente su due aspetti: il routing e il protocollo di accesso al mezzo (Medium Access Control) [43] [45] [61] [62]. Proprio studiando il MAC possiamo classificare quattro possibili stati per il nodo: oltre a quelli di trasmissione e ricezione ci sono quelli di idle listening, nel quale il nodo “ascolta” la rete, e quello di sleep, nel quale è completamente inattivo. Se, poi, misuriamo il consumo energetico del nodo in ogni stato, scopriamo che nello stato di idle listening esso è paragonabile a quello degli stati di trasmissione e ricezione. Si veda per questo la tabella 1.1 [35].
Tabella 1.1: Consumo energetico per nodo misurato.
Abbiamo scoperto dunque che semplicemente “ascoltare” il canale per sentire se ci sono messaggi da ricevere comporta un notevole dispendio di energia per il nodo. Da ciò segue che per massimizzare la vita del nodo occorre massimizzare il tempo in cui esso resta nello stato sleep, tenendo però presente che un nodo in quello stato non può partecipare all’attività di routing della rete, inficiandone la connettività (fig. 1.9). Il nostro obiettivo, per questo, deve essere la ricerca di un trade-off fra la durata della vita del nodo e le prestazioni della rete, senza trascurare il fatto che quando un nodo esaurisce la propria batteria, esso non è più in grado di aiutare il funzionamento della rete, cioè che massimizzare la durata della vita ogni nodo implica massimizzare la durata della vita dell’intera rete.
I protocolli per il MAC devono andare proprio in questa direzione: limitato consumo di energia senza abbassare eccessivamente le prestazioni della rete. Sono disponibili in letteratura molti protocolli che si dirigono verso questo scopo.
Figura 1.9 : Possibili stati del nodo
Le principali sfide, per chi prova a progettare il protocollo, sono quelle di minimizzare il numero di collisioni (esse causano ritrasmissioni, quindi sprecano energie), l’overhead (la trasmissione di dati non informativi) ed il cosiddetto overhearing, cioè l’avvio delle dispendiose procedure di ricezione per pacchetti che non sono destinati al nodo, ma che gli arrivano a causa della natura del mezzo. Le prime proposte che sono state fatte con l’obiettivo di limitare il numero delle collisioni sono:
• Evitare di trasmettere in caso di canale congestionato: se un nodo sta trasmettendo tutti i suoi vicini non devono trasmettere;
• Sincronizzare fra loro le comunicazioni;
• Stabilire per quali intervalli non è necessario per un nodo ascoltare la rete.
Gli ultimi due aspetti vanno incontro al problema dell’overhearing e, insieme, potrebbero far parte di un approccio MAC di tipo TDMA (Time Division Multiple Access) finalizzato al risparmio di energia.
Si deve ricordare che fino ad ora nella nostra trattazione abbiamo trascurato l’energia spesa nella transizione da uno stato all’altro che invece andrebbe considerata.
Oltre agli approcci di tipo individuale che abbiamo visto fino ad ora esistono proposte di tipo globale (soprattutto nei casi nei quali la densità dei nodi è molto elevata), con le quali si cerca di massimizzare il numero dei nodi spenti (o meglio inattivi), mantenendo le stesse prestazioni da parte della rete.
Esiste anche un altro modo di ridurre la potenza consumata dal nodo, che ha anche effetti positivi su tutta la rete. Se si considera che la potenza del segnale trasmesso è proporzionale a quella che verrà spesa dall’amplificatore di potenza (HPA) per trasmetterlo, si può pensare di ridurre la potenza in trasmissione. Questa mossa, oltre ad allungare la vita del nodo, come volevamo, ha come effetto positivo quello di ridurre l’interferenza globale: se, infatti, tutti i nodi trasmettono alla minima potenza indispensabile, ci sarà minore interferenza (col beneficio ulteriore di favorire il riuso spaziale delle frequenze), con conseguente aumento del throughput della rete [61] [62]. Tutti questi
WIRELESS AD HOC NETWORKS
aspetti positivi, tuttavia, hanno un prezzo da pagare: diminuendo la potenza in trasmissione si diminuisce il range trasmissivo dei nodi, costringendoci ad instaurare più frequentemente collegamenti di tipo multi-hop, con un maggiore consumo energetico complessivo per la rete. Per ovviare a quest’ultimo inconveniente sono stati sviluppati e proposti opportuni protocolli di routing detti energy-efficient oppure power-aware, che hanno come scopo la scelta del percorso sorgente-destinatario a minimo consumo energetico. [56]
La loro efficienza si basa sulle metriche che vengono utilizzate per il calcolo del percorso a minimo consumo e su come l’aspetto del routing a minimo costo si combina con la gestione degli aspetti fisici della rete (i.e. shadowing, fading, interferenza e path loss).
Per implementare le strategie di power saving è possibile agire a diversi livelli, oltre a quello fisico. A livello di Sistema Operativo, ad esempio, è possibile inserire, a livello di politica di scheduling, delle considerazioni sulla banda disponibile per le comunicazioni, inserendo meccanismi che danno priorità alta alle operazioni di networking se la banda è grande e bassa se invece è piccola. A livello di Applicazione, invece, è possibile sfruttare la conoscenza del profilo del traffico generato ed altri stratagemmi per ridurre il tempo di trasmissione per il nodo: tali soluzioni, pur garantendo buoni risultati, mancano tuttavia di flessibilità, dal momento che prevedono che ogni applicazione abbia un piano di Power Saving apposito, cosa decisamente scomoda. A livello di Trasporto è stato proposto un protocollo per il risparmio di potenza nel quale il nodo sospende le comunicazioni periodicamente per un tempo arbitrario, cercando un compromesso tra i ritardi di comunicazione introdotti da questa interruzione e il risparmio di potenza ottenuto [36].
CAPITOLO 2
Power Control
2.1 CDMA AD HOC NETWORKS: POWER CONTROL
Ad oggi, pur non esistendo una standardizzazione del protocollo di accesso al mezzo (MAC) per le reti ad hoc, esiste un standard de facto, cioè l’ 802.11b. Il protocollo di tale standard è di tipo CSMA (Carrier Sensing Multiple Access), basato su di una DCF (Distributed Coordination Function) con ascolto del mezzo (physical sensing) abbinato ad un meccanismo di prenotazione fondato su uno scambio di pacchetti RTS/CTS per risolvere il problema del terminale nascosto. In questo modo, però, si può avere una sola trasmissione alla volta nel range di entrambi i nodi che si sono riservati il mezzo. Un tale meccanismo, inoltre, può non avere successo, in quanto la trasmissione può essere comunque disturbata dalle comunicazioni fra nodi che stanno fuori dal range trasmissivo dei pacchetti RTS/CTS.
Il meccanismo di Collision Avoidance è per tanto causa di una limitazione del throughput complessivo della rete, dal momento che preclude la trasmissione all’interno della suddetta area. Questa carenza del protocollo di cui sopra può essere risolta usando un approccio diverso, di tipo DS/CDMA [38]. Esso, infatti, consente la trasmissione contemporanea di più utenti (in un numero che dipende essenzialmente dalla lunghezza della sequenza di spreading) senza interferenza mutua (sarebbe più corretto, in realtà, dire “con interferenza limitata”, poiché, per non avere interferenza, i segnali dovrebbero essere perfettamente sincronizzati e le sequenze di codice perfettamente ortogonali).
Il problema che si pone, nel caso di reti decentralizzate come le nostre, è quello della distribuzione dei codici. Tale problema, inoltre, presenta due aspetti: il criterio col quale distribuire i codici e come usare tali codici nella comunicazione [48] [49] [50] [51] [52].
Il problema che si pone per primo è quello che il numero dei codici disponibili è molto inferiore al numero dei nodi presenti, e ciò richiede un riuso spaziale dei codici, assegnando codici ortogonali a nodi vicini e riusando gli stessi codici per nodi lontani.
Un altro problema è l’approccio con il quale tali codici vengono assegnati. Esistono al riguardo diversi approcci:
• Comune: si usa lo stesso codice di espansione per ogni nodo, le informazioni sull’indirizzo del nodo sono poste all’inizio del pacchetto in modo tale che il nodo possa leggerle subito e capire se il pacchetto è indirizzato a lui;
• Receiver based: si usa un unico codice per trasmettere pacchetti allo stesso ricevitore. Lo svantaggio di questo approccio è che esso non evita le cosiddette collisioni primarie, i.e. quando più nodi trasmettono verso lo stesso nodo;
• Transmitter based: ogni nodo trasmette con un proprio codice quindi senza interferire con gli altri. In questo caso il problema risiede nel fatto che il ricevitore non conosce a priori quale nodo gli ha trasmesso il pacchetto e quindi quale codice di despreading usare;
• Pairwise: ogni coppia di nodi usa un proprio codice per comunicare. Intuitivamente, il limite di tale approccio sta nella quantità di codici che esso richiede;
• Misto: usa combinazioni degli approcci precedenti, ad esempio trasmettendo l’header in modo receiver based o pairwise ed il corpo del pacchetto in modo transmitter based.
Un ulteriore vantaggio della tecnica CDMA è quello che essa permette di implementare un meccanismo di Power Control il quale ha un duplice effetto positivo: facendo abbassare la potenza trasmissiva di ogni dispositivo fino al minimo indispensabile, ne allunga la durata di vita e riduce l’interferenza complessiva nella rete.
Nel nostro caso abbiamo implementato per i nodi un particolare algoritmo basandoci su [69] e apportandovi delle migliorie.
2.2 TEORIA DEI GIOCHI
Prima di trattare questa teoria è bene fare il punto e ricordare l’ambiente che stiamo trattando: il canale sul quale trasmettiamo, cioè quello radio, è di tipo broadcast. Ciò vuol dire che la trasmissione di un nodo raggiunge tutti i suoi vicini, intendendo con tale termine tutti i nodi situati all’interno del suo range trasmissivo, e che, viceversa, tale nodo riceve le trasmissioni dei vicini stessi. Chiaramente tale fenomeno necessita di essere tenuto in qualche modo sotto controllo in sistemi che, come il nostro, servono per trasmissioni di tipo unicast.
A peggiorare ulteriormente il già difficile ambiente radio (con i suoi effetti di fading, shadowing, path loss e rumore) c’è l’interferenza prodotta dai nodi, che va gestita attraverso un sapiente Radio Resource Managment (RRM). Questo ultimo aspetto può venire affrontato in modo statico o dinamico, intendendo in questo caso l’approccio col quale vengono gestiti i parametri d’interesse. Un’altra distinzione è quella tra RRM centralizzato e distribuito, intendendo con ciò da chi viene
POWER CONTROL
effettivamente svolta l’attività di gestione, cioè un’autorità centrale o tutti i nodi. Nel nostro caso specifico la strada da percorrere è ovviamente unica, cioè quella di una gestione distribuita.
La teoria dei giochi è una scienza matematica, sviluppata originariamente in ambito microeconomico, la quale serve per l’analisi di situazioni di conflitto e ne ricerca soluzioni competitive e cooperative usando modelli, cioè uno studio delle decisioni individuali in situazioni nelle quali ci sono interazioni tra i vari soggetti, tali che le decisioni di un soggetto possono influire sui risultati conseguibili da parte di un rivale, secondo un meccanismo di retroazione.
Pur essendo nata e pensata in ambito economico, tale teoria si è dimostrata valida anche per i sistemi di telecomunicazioni. Anzi, essa, si rivela più adatta ad un ambiente nel quale le decisioni vengono prese da macchine, poiché esse, a differenza degli umani, agiscono in modo perfettamente razionale, cioè congruente col perseguimento dell’obiettivo. Proprio per mezzo di essa si può cercare un modo per risolvere i problemi di ottimizzazione distribuita del consumo di risorse di cui sopra: grazie ad essa possiamo decentralizzare gli algoritmi elaborati, cioè farli eseguire ai singoli nodi senza la supervisione di un ente centrale. Lo scopo finale dell’applicazione di tale teoria alle MANET, quindi, è quello di far sì che ogni singolo nodo della rete, in quanto giocatore, agisca in modo egoista, cercando di perseguire il proprio obiettivo (senza bisogno di informazioni sugli altri), ma al contempo permetta il raggiungimento di un bene comune, cioè anche quello di tutte le altre entità. L’ottimizzazione che cerchiamo, dunque, consiste nella situazione nella quale il singolo cerca ed ottiene il massimo profitto per sé e, allo stesso tempo, per la comunità [66].
2.2.1 CONCETTI
Definiamo ora i concetti di base della teoria dei giochi che useremo per modellare la situazione da analizzare:
• Insieme dei giocatori, comunità oggetto di studio, i.e. l’insieme dei nodi;
• Insieme delle azioni Ai , set delle possibili azioni che possono essere svolte dal giocatore (nodi) i esimo− ;
• Strategia, azione scelta ed intrapresa dal giocatore (nodo); • Profilo di strategia, insieme delle strategie intraprese; • Funzione Utilità, mappa il profilo utilità in numeri R ;
• Spazio azione gioco, indicato con A , rappresenta l’insieme delle strategie di tutti i giocatori (è dato dal loro prodotto cartesiano).
Ogni profilo di strategia dà come risultato un guadagno ad ogni giocatore, e tale guadagno, per mezzo della funzione utilità, viene espresso con un numero reale.
Una funzione f :A→R (riceve in ingresso un insieme di azioni e restituisce un numero reale) è una funzione utilità se per ogni coppia ,i j∈A (per ogni coppia di profili di strategia):
il profilo i è da preferirsi a quello j ⇔ f i( )≥ f j( )
Il giocatore ha come scopo la massimizzazione della propria funzione utilità (noi la chiameremo “u”), la quale dipende da un set di variabili che comprende sì la strategia del giocatore, ma anche quelle degli altri.
Le osservazioni su cui baseremo il nostro ragionamento sono essenzialmente due:
1) Ognuno sa che gli altri giocatori devono risolvere lo stesso problema di ottimizzazione della loro u;
2) Ognuno risolve tale problema agendo coerentemente all’attuazione del proprio fine, e ciò è noto agli altri.
Proprio per queste due ipotesi di lavoro, la teoria dei giochi riesce ad essere uno strumento più utile per studiare la nostra situazione, dove le decisioni sono prese da macchine razionali, piuttosto che quelle nelle quali le decisioni sono prese da esseri umani.
2.2.2 CLASSIFICAZIONE DEI GIOCHI
Essenzialmente le caratteristiche in base alle quali classifichiamo il gioco sono 3:
• Cooperativo/Non cooperativo: intuitivamente ci dice se i giocatori collaborano o no;
• Ad informazione perfetta/imperfetta: ci indica il grado di conoscenza che il giocatore ha delle strategie altrui;
• Ripetuto/Simultaneo (Statico): ci dice se il giocatore decide osservando e prevedendo le decisione degli altri oppure se le ignora (simultaneo, infatti, perché tutti decidono contemporaneamente ed indipendentemente)
2.2.3 SOLUZIONE
La soluzione, secondo la teoria dei giochi, è data dal profilo di strategie che sarà scelto dai giocatori con probabilità maggiore. In particolare, come premesse, si deve:
1) Definire un set di condizioni necessarie che devono essere soddisfatte da una strategia per poterla considerare tale;
2) Capire se esiste una soluzione, cioè se c’è una conclusione più probabile. Analizzando i due punti si possono fare delle considerazioni.
Per stabilire se la soluzione effettivamente esiste servono informazioni tali che non si può fare un ragionamento generale, ma si deve analizzare caso per caso.
POWER CONTROL
Considerando ora il primo punto e tenendo in mente le idee sviluppate nel paragrafo precedente, si può dimostrare che, se esiste, la soluzione del gioco è data dal cosiddetto Equilibrio di Nash.
2.2.4 EQUILIBRIO DI NASH
La soluzione del gioco che prende questo nome presuppone innanzitutto che i giocatori ragionino tutti seguendo lo stesso principio. Un profilo di strategie è una soluzione di equilibrio di Nash se per ogni giocatore dà il massimo della funzione utilità, in risposta alla combinazione dei profili strategia degli altri.
Si tratta di una soluzione di equilibrio proprio perché, se tutti i nodi perseguono la stessa strategia, nessuno ha interesse a cambiare la propria.
In termini matematici definiamo: i
u = funzione utilità giocatore i;
i
x , xi ' = strategie del giocatore i; i
x− = vettore delle strategie di tutti i giocatori, a parte i; i
x = Equilibrio Nash ⇔u x xi( ,i −i)≥u xi( ',i x−i) ∀ ∈xi' Ai,∀ =i 1,...,N.
Che in sintesi significa: “se gli altri nodi stanno fermi, xi è la strategia migliore (nel senso di massimizzazione di ui)”, e proprio per questo si parla di equilibrio.
Vale la pena precisare, infine, che la soluzione di Nash: • NON esiste necessariamente;
• NON è unica (se esiste);
• NON è la migliore possibile (in termini assoluti).
2.2.5 EFFICIENZA DI PARETO
Proprio per l’ultimo punto di cui sopra, la valutazione della bontà dell’equilibrio, si introduce il concetto di efficienza Paretiana.
Un profilo complessivo di strategie è detto Pareto efficiente/ottimo se non esiste un altro profilo in grado di migliorare contemporaneamente il risultato per ogni giocatore. In una situazione del genere, se se cerca di migliorare il risultato di un giocatore, si ha inevitabilmente un peggioramento di quella di un altro.
Matematicamente: p
u xi( )>u xi( p)per almeno un i . Prima di andare oltre sono necessarie delle precisazioni:
• Non tutti le soluzioni di equilibrio di Nash sono Pareto ottime, dal momento che in un profilo Pareto ottimo si va a risolvere un problema di ricerca di un massimo vincolato, ovvero la soluzione ottima nei limiti imposti dalle strategie altrui;
• Un profilo Pareto ottimo non è necessariamente una soluzione di equilibrio, ed in tal caso, anche scegliendo tale profilo, il gioco si dovrà concludere con una soluzione di equilibrio, se essa esiste.
Un altro concetto è quello di strategia Pareto dominante: “x Pareto domina 1 x ” 2 ⇔ u xi( )1 ≥u xi( 2) ∀ =i 1,...,N e u xi( )1 >u xi( 2) per almeno un i .
2.3 TEORIA DEI GIOCHI PER RETI WIRELESS
Una rete wireless, o meglio il suo modello, per poter essere studiato come un gioco, richiede certe condizioni:
1) Condizioni di Razionalità:
- I processi di decisione devono essere ben definiti, ovvero la scelta delle azioni, cioè la decisone, deve essere soggetta ad un set di regole deterministico;
- Ad un cambiamento di strategia corrisponde la ricerca (motivata) di un miglioramento.
La soddisfazione di queste condizioni si ottiene facendo sì che un nodo abbia come obiettivo la massimizzazione della propria funzione utilità.
2) Condizioni di gioco NON banale:
- Le decisioni devono essere prese da più di un nodo (i.e. deve esserci più di un giocatore);
- Almeno due giocatori devono avere un insieme di strategie che contenga più elementi.
Anche se queste regole possono sembrare (ed in effetti lo sono) banali, esse servono a determinare le situazioni nelle quali possiamo far ricorso alla teoria dei giochi. In uno schema ad un solo giocatore, infatti, ci riconduciamo ad un problema di ottimizzazione (non vincolato, almeno non nel senso in cui lo intendiamo in questo contesto), e se un giocatore non ha un gruppo di azioni fra le quali decidere, esso non è più un giocatore.
POWER CONTROL
2.4 TEORIA DEI GIOCHI PER RETI AD HOC
Comprese ora le condizioni precedenti ci domandiamo ora se le nostre reti ad hoc possono essere effettivamente considerate un gioco nella gestione delle risorse e, se sì, come ciò possa essere fatto. Se andiamo ad analizzare l’aspetto del Power Control, tenendo conto della struttura delle MANET e delle condizioni da soddisfare, la risposta alla prima domanda è affermativa. Per quanto riguarda il tipo di gioco esso è:
• Non cooperativo: i nodi non conoscono le scelte degli altri nodi e le loro condizioni, né possono collaborare tra loro;
• Ad informazione imperfetta: i nodi hanno solo una conoscenza parziale, locale ed incompleta della rete;
• Ripetuto.
In uno schema del genere ogni utente ha come obiettivo la massimizzazione delle prestazioni, di solito rappresentate dal livello del rapporto segnale-interferenza (SIR), unita al massimo risparmio energetico: lo spazio delle sue decisioni è l’insieme (discreto e finito) delle sue potenze trasmissive. Come già accennato, diminuire la potenza in trasmissione ha un effetto positivo per il nodo stesso, in termini di durata della vita, ma è vantaggioso anche per gli altri che subiranno un’interferenza minore e quindi sperimenteranno un SIR maggiore senza aumentare la propria potenza trasmissiva e, per tanto, saranno portati ad abbassarla, con la creazione di un circolo virtuoso. Tale algoritmo è particolarmente appropriato per il CDMA.
2.4.1 ALGORITMO AGGIORNAMENTO DELLE POTENZE
Ci riferiamo ora ad un algoritmo di tipo distribuito fra i più noti. [53].
Prima di descriverlo, però, occorre fare delle ipotesi di lavoro. Dal momento che tale algoritmo si basa su di una comunicazione, da parte del nodo ricevitore a quello trasmettitore, su come variare la potenza trasmessa per massimizzare la propria funzione utilità, esso presuppone che il ricevitore sia in grado di ricavarsi tali informazioni e di farle conoscere al trasmettitore (pena la non implementabilità in maniera distribuita).
L’equazione di aggiornamento che governa l’algoritmo è: ( ) ( 1) ( ) i i i i p k p k SNIR k γ ⋅ + = ,
dove
γ
i è il SNIR desiderato per ogni i = 1,…,N.Per prima cosa tale algoritmo ha una natura autonoma e distribuita che lo rende adatto alla tipologia di rete. Un’altra interessante proprietà è che, se lo condizioni lo permettono, esso converge all’assegnazione delle potenze Pareto ottimale. La condizione “se le condizioni lo permettono” vuol
dire “se i vincoli sul SNIR (o sul parametro di interesse) permettono la realizzazione di questo sistema”, quindi se esiste una distribuzione di potenze che rispetta tali limiti. Il problema e il limite di tale algoritmo è proprio questo: se non esiste la distribuzione di potenze cercata, l’algoritmo diverge a causa del limite rigido che abbiamo imposto. In una situazione nella quale la soluzione non è realizzabile, infatti, gli utenti trasmettono col sol obiettivo di avere SNIR superiore alla soglia imposta, ignorando l’irrealizzabilità di una situazione dove tutti raggiungono il proprio obiettivo: il risultato di tutto ciò è una crescita smisurata delle potenze trasmissive (circolo vizioso).
La causa può sembrare quindi il fatto che i nodi non capiscono quando il Power Control è realizzabile o meno. In realtà un nodo non dovrebbe avere difficoltà a capire, vedendo il livello di interferenza ricevuta, che la soluzione è irrealizzabile.
Un modo per evitare l’irrealizzabilità è quello di inserire, per ogni utente che vuole trasmettere, una specie di Admission Control fondato su informazioni locali e su requisiti non rigidi di QoS.
E’ proprio su questo aspetto che entra in ballo la teoria dei giochi: anziché ammettere utenti che abbiano SNIRi ≥
γ
i, ogni utente, in modo distribuito, si calcola il SNIR che massimizza la propria funzione utilità e usa tale SNIR come soglia, decidendo autonomamente se trasmettere o no,2.4.2 FUNZIONE UTILITA’
La funzione utilità rappresenta il grado di soddisfazione sperimentato da ogni utente. Ovviamente ne possono esistere di diverso tipo in ogni situazione, ognuna con un proprio insieme di regole di preferenza. Nel nostro caso, oltre a mediare tra soddisfazione dell’utente e buona gestione della rete, deve avere presenti anche le prestazioni globali del sistema.
Nel nostro caso, cioè un sistema di tipo wireless, la soddisfazione dell’utente è legata alla QoS che, a sua volta, dipende dal BER (Bit Error Rate) o dalla P(e) (probabilità di errore), funzioni del SNIR. Esiste anche un parametro di qualità alternativo, la capacità informativa, funzione anch’essa del SNIR
2
log (1 )
C= ⋅B +SNIR ( B = Banda)
La funzione utilità, inoltre, deve tenere conto, in qualche modo, della potenza spesa in trasmissione, visto che il grado di soddisfazione dipende anche dalla minimizzazione della potenza spesa (risorsa scarsa e limitata).
Possiamo quindi riassumere le caratteristiche desiderate:
1) Per ipotesi u deve essere funzione non negativa del i SNIR e deve essere nulla se i
0 i
SNIR = . Si assume nulla se la potenza trasmissiva è nulla (condizione sensata ed intuitiva);
POWER CONTROL
2) Fissata la potenza trasmissiva, u cresce con i SNIR : i
( , ) 0 i i i i u p SNIR SNIR ∂ > ∂ ∀SNIR pi, i (sensato
ed intuitivo, se fisso la potenza le prestazioni crescono con SNIR);
3) Fissata la potenza trasmissiva, al crescere di SNIR la derivata di u tende a 0: i
( , ) lim 0 i i i i SNIR i u p SNIR SNIR →∞ ∂ =
∂ (sensato ed intuitivo, al crescere del SNIR le prestazioni tendono ad un valore costante);
4) Fissato SNIR , i u decresce al crescere della potenza trasmessa: i i( i, i) 0 i u p SNIR p ∂ < ∂ , i i SNIR p
∀ (sensato ed intuitivo, a parità di prestazioni la soddisfazione decresce al crescere della potenza trasmessa. Tale condizione è importante per evitare il circolo vizioso);
5) Se la potenza trasmissiva pi → ∞, ui →0 (intuitivo, segue dal punto 4).
2.4.3 TRAFFICO: DATI VS VOCE
Prima di andare a costruire la funzione utilità per il nostro algoritmo dobbiamo avere chiare quali sono le esigenze, in termini di prestazioni, dei due tipi di traffico che ci interessano: voce e dati.
• Voce = richiede ritardi limitati e stringenti ma tollera una certa P(e);
• Dati = non ha esigenze stringenti in termini di delay, ma vuole una P(e) più bassa possibile (ovvio, se cresce la P(e), aumentano le ritrasmissioni e dunque diminuisce il throughput). Da queste esigenze ci si può ricavare una funzione utilità opportuna (e. g. figura 2.1).
Da notare che nel caso voce se SNIR è maggiore della soglia si ha una soddisfazione sufficiente (gradino), mentre nel caso dati la funzione utilità è una funzione continua del SNIR.
2.4.4 COSTRUZIONE
Esistono molti modi per costruire la funzione utilità adatta allo sviluppo dell’algoritmo, ma non ne esiste uno che si sia dimostrato superiore agli altri, almeno per ora. Nel nostro sviluppo siamo partiti dal metodo di Goodman [69].
Dal momento che si è ipotizzato un accesso al mezzo di tipo CDMA con N link attivi (= N giocatori, i ricevitori che, attraverso il Power Control, comunicano ai propri trasmettitori come regolare la propria potenza in trasmissione) a rate R [bit/s] e banda W [Hz], allora:
, 2 1 , i i i i N j i j j N j i
G
p
W
SN IR
R
=G
p
σ
≠⋅
=
⋅
⋅
+
∑
Dove: , x yG = perdita (guadagno) tra il trasmettitore x ed il ricevitore y; x
p = potenza trasmissiva del nodo x; 2
N
σ = potenza rumore.
E’ il rapporto al ricevitore i-esimo e la ( )P e =q SNIR( i), dove ( )q i è una funzione di altre variabili,
oltre che del SNIR . i
Noi abbiamo scelto come funzione utilità quella chiamata sigmoide
( ) 1 ( ) 1 i i i i a x b U SN IR x e− ⋅ − = = + Dove: i
a = pendenza della funzione, se cresce cresce la pendenza.
i
b = centro, cioè U bi( )i =0.5.
Variando a varia anche la funzione utilità (la posso variare a seconda che io tratti dati o voce) i
Quindi xi =SNIRi (se voglio massimizzare la capacità xi =Ci) Si noti che se xi =0 allora (0) 1 0
1 a bi i U
e ⋅
= ≠
+ . Chiaramente se a bi⋅ i ≫ allora (0) 00 U ≈ . Se vogliamo risolvere il problema in modo rigoroso basta fare la trasformazione lineare
( )
1
1
1
1
(
)
1
1
1
a x b a b a be
e
U
x
e
− ⋅ − ⋅ ⋅
−
+
+
=
−
+
POWER CONTROL 1.0 0.8 0.6 0.4 0.2 0.0 U ti lit à 20 15 10 5 0 SIR (dB) a=1 b=10 a=10 b=10
Figura 2.2: Esempi di sigmoide
Un’altra incongruenza alla quale dobbiamo ovviare (più importante) è che fissato SNIR allora ( )
U x non tende a 0 se la potenza trasmissiva cresce, come invece dovrebbe succedere. Ciò può
causare il feedback negativo di cui si parlava sopra. Perciò è stato introdotto, al fine di aggiustare la funzione U x , il concetto di pricing [67] [68], cioè la cosiddetta funzione costo, monotona ( ) crescente con la potenza trasmissiva e nulla nell’origine:
( )
i i i i
C p = ⋅α p ,
dove αi è il coefficiente di prezzo indipendente da p , ma variabile con l’ambiente e la situazione. i
Tale funzione elimina il problema del circolo vizioso ed incoraggia la collaborazione tra gli utenti. Otteniamo così la funzione Utilità Netta
( ) ( )
i i i i i i
NU p =U SNIR − ⋅α p .
N.B.: Fissato SNIR , se i pi → ∞, allora NU pi( i)→ −∞ (accettabile).
2.4.5 FORMALIZZAZIONE GIOCO: EQUILIBRIO DI NASH
Esprimendo dunque il problema in modo matematico:
m ax ( )
i
i
p N U p ∀ ∈pi Ai, ∀ =i 1,...,N.
Dove p=[p1,...,pN] è il vettore delle strategie, Ai lo spazio delle strategie, cioè l’insieme delle possibili potenze [0,Pmax] e N il numero dei nodi.
