Cooperative Medium Access Control Policies in Wireless Networks

Broadly speaking, wireless ad hoc networks are permeated by cooperative behaviors. In such systems, indeed, nodes have to continuously pool their resources to achieve goals that are of general interest, such as routing packets towards a destination that would otherwise be out of reach for an information source, or coordinating medium access so as to successfully share a common spectrum. Recently, however, the idea of collaboration has gathered a renewed and increasing deal of attention in the research community thanks to the development of innovative concepts, most notably the idea of cooperative relaying, that have been shown to unleash significant improvements, going beyond some intrinsic limitations that affect wireless communications systems. While these emerging solutions have been thoroughly studied from a theoretical perspective, the advantages they offer can be reaped in real world implementations only if additional coordination among nodes is provided, so that cooperating terminals are allowed to offer their help obeying the rules that control medium access, and without disrupting the normal activity of the network. Along this line of reasoning, this thesis focuses on the design and study of link layers that implement cooperation in ad hoc networks. The contribution of our work is twofold. On the one hand, we introduce novel and beneficial collaborative strategies, while on the other hand we investigate how the intrinsic nature of different medium access control policies can be more or less beneficial to cooperative behaviors. In the first part, we present an innovative approach to cooperation in networks with multi-antenna equipped nodes that rely on directional transmissions and receptions. Our solution proposes terminals to share information on ongoing communications to better coordinate medium access at the link layer, and manages to overcome issues such as node deafness that typically hamper the potential of large scale directional wireless systems. The central part of this work, conversely, concentrates on the simpler ad hoc scenario where omnidirectional communications are in place, and tackles some inefficiencies of the cooperative relaying paradigm. In particular, we introduce the novel concept of hybrid cooperative-network coded ARQ, which allows a relay to code data of its own together with a corrupted packet during a retransmission at no additional cost in terms of bandwidth. Such a solution encourages nodes to cooperate, since they are offered the possibility to pursue a goal of their interest while helping surrounding terminals. Moreover, the capability of exploiting retransmissions to serve additional traffic, achieved by smartly taking advantage of network coding techniques, triggers beneficial effects also at a network level in terms of sustainable throughput and reduced congestion. The potential of the proposed approach is first investigated by means of mathematical analysis, while subsequently extensive simulation campaigns test the effectiveness of link layers that implement it in a variety of networking environments. Taking the cue from a reasoned comparison of the results achieved by relaying schemes in different scenarios, we devote the final part of the thesis to the investigation of the impact that distinct spectrum control policies can have on collaborative behaviors. Combining once again mathematical analysis and simulations, we consider how the characteristics of completely distributed, e.g., carrier sense based, and centralized, e.g., time division based, systems influence the effectiveness of a given cooperative strategy. Not only does our study shed light on the relations that exist between cooperation and medium access, but also it provides important hints on how to efficiently design link layers capable of supporting such techniques. Finally, the appendix of this thesis reports the outcome of a research activity, carried out in collaboration with the IBM Zurich Research Laboratory (Switzerland), whose focus falls out of the topic of cooperative link layers and covers the design of energy-efficient routing protocols for wireless sensor networks.

Le reti wireless ad hoc presentano in generale moltissimi comportamenti di natura cooperativa, nei quali i nodi condividono le loro risorse per perseguire un interesse di utilità comune. Basti pensare, in tal senso, alle procedure di routing per la consegna di traffico multihop, o allo scambio di informazioni tra terminali necessario per riuscire a gestire in modo efficace uno spettro condiviso. Recentemente, inoltre, è progressivamente emerso un rinnovato e crescente interesse nella comunità di ricerca per il concetto di collaborazione tra nodi, grazie allo sviluppo di nuovi paradigmi, tra i quali in primis l'idea del relaying cooperativo, che si sono dimostrati in grado di mitigare brillantemente alcuni problemi tipici dei sistemi wireless, rendendo possibili significativi miglioramenti delle prestazioni. Sebbene tali soluzioni innovative siano state oggetto di notevole attenzione in letteratura, gli studi su di esse si sono concentrati principalmente su trattazioni di natura analitica, atte a dimostrarne le potenzialità e i vantaggi nell'ottica della teoria dell'informazione. Approcci di questo tipo tendono chiaramente a considerare, ai fini della trattabilità matematica, topologie semplificate quali reti a tre soli nodi, e spesso assumono un accesso al mezzo idealizzato. Nel momento in cui queste idee vogliano essere implementate in scenari reali, tuttavia, si rende necessario un profondo raffinamento della coordinazione a livello di rete, dal momento che i nodi cooperanti devono comunque sottostare alle regole che caratterizzano la gestione del canale (link layer), di modo da offrire il loro contributo senza ostacolare la normale attività della rete. Prendendo spunto da tale riflessione, questa tesi si concentra sulla definizione e l'analisi di link layer che implementino soluzioni cooperative in reti ad hoc. Due sono i principali contributi del lavoro. Se da un lato, infatti, sono introdotti paradigmi innovativi ed efficaci, dall'altro viene presentato uno studio articolato e completo su come diverse politiche di accesso al mezzo possano influenzare tali comportamenti cooperativi. La prima parte della tesi si focalizza sullo sviluppo di un nuovo approccio collaborativo per reti i cui terminali, dotati di sistemi multiantenna, siano in grado di effettuare trasmissioni e ricezioni direzionali. L'idea proposta prevede che i nodi condividano, tramite scambio di brevi pacchetti di controllo, informazioni sulle comunicazioni attive di cui sono a conoscenza, per poter favorire la maggior distribuzione possibilie di una percezione corretta dello stato del sistema al fine di garantire una migliore coordinazione nell'accesso al mezzo. Studi dedicati dimostrano come tale soluzione sia in grado di superare problemi, quali la sordità di nodo (deafness), che spesso limitano l'efficacia delle trasmissioni direzionali in reti con numero elevato di dispositivi, portando a importanti guadagni in termini di prestazione complessive. La parte centrale del lavoro, al contrario, prende in considerazione reti ad hoc con comunicazioni omnidirezionali, e affronta alcune inefficienze che caratterizzano il paradigma di relaying cooperativo. In particolare, viene introdotto per la prima volta il concetto innovativo di ARQ ibrido cooperativo-network coded, che permette a nodi che agiscano da relay di utilizzare le ritrasmissione di un pacchetto in vece di una sorgente, non in grado di consegnarlo, al fine di servire anche del proprio traffico. Tale approccio, a differenza del comportamento puramente altruistico richiesto dal relaying semplice, incoraggia i terminali a cooperare, offrendo loro la possibilità di perseguire un loro interesse contingente nell'atto stesso di aiutare altri nodi in difficoltà. Inoltre, la capacità di sfruttare il meccanismo di ritrasmissione per servire traffico addizionale, resa possibile dall'utilizzo di tecniche di combinazione lineare sui dati caratteristiche del network coding, getta le basi per benefici anche a livello di rete, quali un incremento del throughput sostenibile e una riduzione della congestione nell'utilizzo della banda. Le potenzialità della soluzione identificata sono dapprima studiate per mezzo di modelli matematici, seguendo le modalità tipicamente riscontrabili in letteratura. Successivamente sono proposti l'implementazione e lo studio simulativo di diversi link layer in grado di supportare tale forma di ARQ ibrido in contesti differenti, quali reti completamente distribuite e reti maggiormente strutturate. Traendo spunto da un confronto ragionato dei risultati ottenibili da schemi di relaying in scenari di rete diversi, la parte finale di questa tesi è dedicata alla discussione dell'impatto che politiche di accesso al mezzo distinte possono avere su comportamenti di natura cooperativa. Combinando ancora una volta analisi matematica e studi simulativi, viene affrontato il problema di come le caratteristiche intrinseche di sistemi basati su carrier sensing e su condivisione del mezzo a multiplazione di tempo influenzino l'efficacia di meccanismi di collaborazione tra nodi. Le osservazioni ottenute tramite questo approccio non solo mettono in luce la stretta relazione esistente tra politiche di gestione dello spettro e cooperazione, ma al tempo stesso forniscono importanti suggerimenti sulla progettazione di link layer in grado di supportare in modo efficace tali strategie. In appendice, infine, vengono riportati i risultati di attività di ricerca svolte in collaborazione con i laboratori di ricerca IBM di Zurigo (Svizzera) e incentrate su tematiche che si discostano leggermente dal fulcro della tesi, quali la progettazione di teniche di routing per reti wireless di sensori, con particolare attenzione all'efficienza energetica.