Design of cooperative networking protocols in wireless networks through stochastic optimization techniques

La cooperazione tra i nodi di una rete radio distribuita è stata dimostrata essere efficace nel migliorare l’efficienza dell’utilizzo delle risorse, e.g., aumentare il throughput della rete o ridurre il consumo energetico. Negli ultimi anni, la cooperazione è stata ampiamente studiata sia da un punto di vista teorico che da un punto di vista implementativo. Ciò nonostante, ci sono diversi scenari che non sono ancora stati analizzati. In questa tesi, consideriamo reti radio distribuite cooperative e multi-salto, dove i nodi cooperano per consegnare messaggi da sorgenti a destinazioni. All’interno della tesi, il termine cooperazione assume significati diversi. Consideriamo situazioni nelle quali i nodi cooperano nella trasmissione di un messaggio, realizzando un schema distribuito di codifica spazio-tempo o utilizzando il concetto recente di “spectrum leasing via cooperation”, e il caso di acquisizione distribuita di dati, dove nodi sensori riducono la quantità di dati acquisiti (e il costo) sfruttando la correlazione spaziale e temporale delle misure. Il primo scenario considera una reta radio cooperativa multi-salto, dove i nodi che hanno decodificato il messaggio cooperano nella trasmissione dello stesso, realizzando un sistema di codifica distribuita a codici spazio-tempo. Il nostro obiettivo è quello di trovare politiche ottime di selezione dei cooperatori per topologie arbitrarie nel caso di singola coppia sorgente-destinazione, con link affetti da path loss e multipath fading. A tal fine, modellizziamo il comportamento della rete attraverso una appropriata catena di Markov e formuliamo il processo di selezione dei cooperatori come un problema di cammino minimo stocastico. Inoltre, riduciamo la complessità del problema di cammino minimo stocastico attraverso una tecnica di taglio innovativa che, a partire dal problema originale, ottiene una catena di Markov ridotta che è infine integrata all’interno di un risolutore basato sulla programmazione dinamica in tempo reale. Il nostro algoritmo è in grado di determinare delle politiche di selezione dei cooperatori per problemi con grandi spazi degli stati, raggiungendo una soluzione con costo confinato (e piccolo) rispetto al costo della soluzione ottima. In questo modo il risolutore permette di ottenere dei limiti sulle prestazioni della rete che possono essere utilizzati per lo sviluppo di protocolli pratici. A partire dai risultati della soluzione centralizzata, guardiamo il problema da un punto di vista diverso, sviluppando tre algoritmi completamente distribuiti e che operano in tempo reale, sfruttando nella selezione dei cooperatori solo informazioni locali. Le prestazioni delle tecniche proposte sono confrontate numericamente con quelle della strategia ottima centralizzata e con quelle di algoritmi simili presenti in letteratura, mostrando un miglioramento rispetto alle soluzioni già esistenti e raggiungendo prestazioni vicine all’ottimo. I risultati positivi ottenuti per lo scenario a singola sorgente-destinazione, ci hanno portato a studiare il comportamento di reti radio cooperative in presenza di interferenza multi-utente. In questo caso, il nostro obiettivo è quello di valutare l’impatto dell’interferenza tra flussi di dati distinti nella determinazione del cammino di instradamento ottimo e nell’ordine con cui avvengono le trasmissioni. Nello scenario che stiamo considerando, tutti i nodi hanno una singola antenna e possono cooperare nella trasmissione dei pacchetti. Dati questi presupposti, per prima cosa modellizziamo il problema delle trasmissioni cooperative utilizzando la programmazione lineare (LP). Dopodichè, per ottenere una soluzione efficiente, formuliamo il problema congiunto dell’instradamento e della pianificazione delle trasmissioni come un problema di cammino minimo a singola coppia, che è poi risolto utilizzando l’algoritmo di ricerca A∗ ed euristiche specializzate. I risultati simulativi delle politiche ottime così ottenute, confermano l’importanza di evitare percorsi di instradamento interferenti e confermano che una pianificazione dei percorsi che tenga conto dell’interferenza può migliorare le prestazioni della rete in modo sostanziale sia in termini di throughput che di energia spesa per la trasmissione, anche quando il numero di flussi che possono interferire è piccolo. Ancora una volta, i nostri modelli forniscono limiti sulle prestazioni della rete che posso essere utilizzati per sviluppare in modo efficiente protocolli di trasmissione cooperativi in reti radio distribuite. Spostiamo poi la nostra attenzione ad uno scenario di reti radio cognitive ed in particolare consideriamo una strategia di spectrum leasing (leasing dello spettro) per la coesistenza di reti multi-salto proprietarie dello spettro con insiemi di nodi senza licenza. La rete primaria consiste di una sorgente, una destinazione e un insieme di nodi primari aggiuntivi che possono essere utilizzati come ripetitori. In aggiunta, i nodi secondari possono essere utilizzati come ripetitori aggiuntivi e quindi come potenziali salti successivi, seguendo il principio dell’instradamento opportunistico. La cooperazione dei nodi secondari è garantita dal meccanismo di “spectrum leasing via cooperation”, dove un nodo che coopera ha la garanzia di poter utilizzare risorse spettrali soggette a vincoli di Qualità del Servizio (QoS). L’obiettivo di questo lavoro è trovare politiche di instradamento ottime ed euristiche, basate sull’idea dello spectrum leasing attraverso l’instradamento cooperativo ed opportunistico. A tal fine, inizialmente formuliamo il problema come un processo decisionale di Markov (MDP) e mostriamo come, in particolare, il problema possa essere trattato come un’istanza del problema di instradamento stocastico. Basandoci sulla struttura delle politiche ottime, deriviamo due schemi di instradamento euristici che confrontiamo poi con le politiche ottime. Le due politiche di instradamento euristiche che abbiamo proposto dimostrano di raggiungere prestazioni vicine alla soluzione ottima e possono essere modificate per ottenere un particolare rapporto tra il throughput sorgente-destinazione ed il consumo di energia primaria. Infine, trattiamo il problema dell’acquisizione di dati distribuita in reti radio di sensori alimentati da fonti di energia rinnovabile. In particolare, consideriamo lo scenario nel quale i nodi radio acquisiscono in modo cooperativo una misura spazialmente correlata ed instradano le informazioni acquisite all’interno della rete al fine di raggiungere un nodo collettore. Prima della trasmissione, i dati acquisiti sono compressi utilizzando una tecnica di codifica di sorgente adattiva e con perdita dell’informazione, utilizzando la correlazione spaziale delle misure. Assumendo che l’acquisizione/compressione, oltre alla trasmissione, abbiano un consumo energetico, proponiamo un algoritmo che minimizzi il livello di distorsione globale introdotto dalla tecnica di codifica di sorgente distribuita. Allo stesso tempo, l’algoritmo proposto garantisce la stabilità delle code di dati e consuma energia, per acquisizione/compressione o trasmissione, solo quando questa è disponibile. Affrontando il problema utilizzando la tecnica di ottimizzazione di Lyapunov, mostriamo come l’algoritmo proposto determini, in tempo reale, politiche di acquisizione/compressione ed instradamento con prestazioni entro limiti stabiliti dalle prestazioni ottime.