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

Cooperation among nodes of a wireless ad hoc network has been shown to be effective in improving the efficiency of resource usage, e.g., increasing the network throughput or reducing the energy consumption. In recent years, cooperation has been widely studied both from an information theoretic point of view and from an implementation perspective. However, there are different scenario that have still not been addressed. In this thesis, we consider wireless cooperative multi-hop networks, where nodes cooperate to deliver messages from sources to destinations. The term cooperation assumes different connotations throughout the thesis. We consider situations in which nodes cooperate in the transmission of a message, realizing a distributed space-time coding scheme or using the recent concept of “spectrum leasing via cooperation”, and the case of distributed data gathering, where source nodes reduce their acquisition rates (and costs) taking advantage of the spatial and temporal correlation between measures. The first scenario considers wireless cooperative multi-hop networks, where nodes that have decoded the message at the previous hop cooperate in the transmission towards the next hop, realizing a distributed space-time coding scheme. Our objective is to find optimal cooperator selection policies for arbitrary topologies with a single source-destination pair, with links affected by path loss and multipath fading. To this end, we model the network behavior through a suitable Markov chain and we formulate the cooperator selection process as a stochastic shortest path problem (SSP). Further, we reduce the complexity of the SSP through a novel pruning technique that, starting from the original problem, obtains a reduced Markov chain which is finally embedded into a solver based on focused real time dynamic programming (FRTDP). Our algorithm can find cooperator selection policies for large state spaces and has a bounded (and small) additional cost with respect to that of optimal solutions and allows to obtain performance bounds that can be useful for the design of practical protocols. Starting from the results of the centralized solution, we looked at the problem from a different angle, devising three online and fully distributed algorithms which only exploit local interactions for the selection of the cooperators. The proposed techniques are numerically compared against the optimal centralized strategy and competing algorithms from the literature, showing their improvement upon existing distributed approaches and achieving close-to-optimal performance. The positive results obtained for the single source-destination scenario, lead us to study the behavior of wireless networks in the presence of multi-user interference and cooperative transmissions. In this case, our focus is to assess the impact of interference among distinct data flows on optimal routing paths and related transmission schedules. In our reference scenario, all nodes have a single antenna and can cooperate in the transmission of packets. Given that, we first model the cooperative transmission problem using linear programming (LP). Thus, for an efficient solution, we reformulate the joint routing and scheduling problem as a single-pair shortest path problem, which is solved using the A∗ search algorithm through specialized heuristics. Simulation results of the obtained optimal policies confirm the importance of avoiding interfering paths and that interference-aware routing can substantially improve the network performance in terms of throughput and energy consumption, even when the number of interfering paths is small. Once again, our models provide useful performance bounds for the design of distributed cooperative transmission protocols in ad hoc networks. We then move our attention to a cognitive radio scenario and we consider a spectrum leasing strategy for the coexistence of a licensed multihop network and a set of unlicensed nodes. The primary network consists of a source, a destination and a set of additional primary nodes that can act as relays. In addition, the secondary nodes can be used as extra relays and hence potential next hops following the principle of opportunistic routing. Secondary cooperation is guaranteed via the “spectrum leasing via cooperation” mechanism, whereby a cooperating node is granted spectral resources subject to a Quality of Service (QoS) constraint. The objective of this work is to find optimal as well as efficient heuristic routing policies based on the idea outlined above of spectrum leasing via cooperative opportunistic routing. To this end, we start by formulating the problem as a Markov decision process (MDP) and we show that, in particular, the problem can be casted in the framework of stochastic routing. Based on the structure of the optimal policies we derive two heuristic routing schemes that we then numerically compare with the optimal policies. The two proposed heuristic routing policies are shown to perform close to optimal solutions and they are as well tunable in terms of end-to-end throughput vs primary energy consumption. Finally, we address the problem of distributed data gathering in a wireless sensor network powered by energy harvesting. In particular, we consider a scenario in which wireless nodes cooperatively acquire spatial correlated measurements and route the information through the network in order to reach a sink node. Before the transmission, the acquired data is compressed via adaptive lossy source coding by leveraging the spatial correlation of the measurements. By assuming that the acquisition/compression, as well as the transmission, entails energy consumption, we propose an algorithm that minimizes the global distortion level introduced by the distributed source coding technique. At the same time, the proposed algorithm achieves network data queues stability and consumes energy, either for acquisition/compression or transmission, only if it is available. By approaching the problem using the Lyapunov optimization technique, we show that the proposed algorithm determines, in an online fashion, efficient acquisition/compression and routing policies with bounded performance guarantees with respect to the optimal performance.

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.