wireless ad ampio raggio, integrando vari tipi di reti come Internet, la rete cellulare, IEEE 802.11, IEEE 802.15 [25] e IEEE 802.16 [26

Testo completo

(1)1. Introduzione Recentemente, le Wireless Mesh etwork o WM [1] (Figura 1) hanno attratto sempre più i ricercatori a causa della disponibilità di tecnologie wireless a basso costo (ad esempio gli standard IEEE 802.11 [24] e IEEE 802.15.1 noto come Bluetooth [23]) e del grande numero di applicazioni che queste reti possono supportare, che vanno dalla pubblica sicurezza, alla video sorveglianza, alla tecnologia di accesso last-mile per Internet [1].. Figura 1 - Esempi di WM. Sebbene esistano vari tipi di WMN, come riportato in [1], noi faremo riferimento all’architettura Infrastructure/Backbone WM (Figura 2) il cui scopo è fornire agli utenti una connettività wireless ad ampio raggio, integrando vari tipi di reti come Internet, la rete cellulare, IEEE 802.11, IEEE 802.15 [25] e IEEE 802.16 [26].. 6.

(2) Figura 2 - Infrastructure/Backbone WM. Una WMN è una rete wireless che, tramite una comunicazione multihop, inoltra il traffico da e per Internet attraverso i gateway della rete fissa wired. Mentre le reti ad-hoc sono flat, le WMN introducono una gerarchia a tre livelli in cui possiamo distinguere il Wired Internet Backbone, il Wireless Mesh Backbone e varie tipologie di reti che connettono i clienti a quest’ultimo. I mesh client, nodi utenti della WMN, sono caratterizzati da energia e potenza di calcolo limitate e da forte eterogeneità soprattutto dal punto di vista hardware in quanto rientrano in questa categoria dispositivi quali laptop, smartphone, sensori e altri ancora. I mesh router compongono il Wireless Backbone e hanno, solitamente, minori problemi di energia o di limitata capacità di calcolo. Alcuni di essi, chiamati gateway, sono connessi alla rete fissa wired ed hanno lo scopo di fare da intermediari tra i mesh router, che ricevono il traffico generato dai mesh client, e Internet. Utilizzando le WMN abbiamo il vantaggio di poter creare un Backbone anche quando il piazzamento di una infrastruttura cablata non è possibile, a causa delle condizioni avverse dell’area o semplicemente per gli elevati costi di cablaggio. Tuttavia, le tecnologie wireless sviluppate fino ad oggi (ad esempio: IEEE 802.11 a/b/g , IEEE 802.16) hanno una capacità nominale inferiore a quella raggiungibile con le tecnologie wired (ad esempio: Ethernet a 1Gbps [27]). 7.

(3) Un settore attivo di ricerca ha come scopo quello di cercare di ridurre questo divario il più possibile. Nel resto della trattazione i mesh router saranno riferiti anche come nodi. In particolare, inizialmente proporremo un modello di WMN in cui una entità centrale coordina le trasmissioni dei router e solo in seguito ci preoccuperemo di estendere tale modello per un ambiente distribuito al fine di ridurre il tempo e la quantità di calcoli necessari. Questo renderà possibile l’applicazione del nostro algoritmo anche al di fuori delle WMN e più precisamente in quelle reti in cui si hanno vincoli di energia e capacità di calcolo. Per il momento abbiamo parlato delle Infrastructure/Backbone WMN, tuttavia c’è da fare una precisazione in quanto, durante la nostra analisi, tratteremo un’estensione di queste reti chiamata Multi-Channel WM (MC-WMN [28]). Una MC-WMN è un insieme di router wireless stazionari, in cui ognuno di essi è equipaggiato con varie interfacce di rete o NIC operanti su frequenze diverse o canali. Gli standard esistenti (ad esempio IEEE 802.11 a/b/g , IEEE 802.16) hanno già la capacità di operare su più risorse radio, quindi questo non comporterà nessuna loro modifica. Se in assenza di interferenza da altre sorgenti radio, un nodo m può trasmettere via radio ad un altro nodo n, diciamo che esiste il link fisico (m,n) e che i due nodi sono vicini o neighbour. L'esistenza di un link fisico non garantisce di per sé che questo poi venga sfruttato per la trasmissione, questo accade se esiste il link logico (m,n). Affinché due router stabiliscano un link logico è necessario che esista un link fisico tra di loro e che siano sintonizzati su una stessa frequenza in almeno una delle loro interfacce. I collegamenti wireless sono supposti essere half-duplex [31], cioè ogni router può alternativamente trasmettere o ricevere dati, ma non le due cose contemporaneamente (vincolo half-duplex o transceiver constraint), perché un modello full-duplex [31] può essere ottenuto solo attraverso l’utilizzo di risorse aggiuntive (ad esempio usando delle antenne multiple o canali multipli [32]). Una volta definite opportune variabili che rappresentano le interfacce possedute da ciascun nodo e opportune etichette per indicare i canali e i nodi, formuleremo il nostro algoritmo seguendo un approccio cross-layer, cioè affronteremo congiuntamente vari problemi, tra cui:. 8.

(4) • Formazione della topologia logica : data la topologia fisica e alcuni vincoli, quanti link logici dovrebbero essere assegnati tra una coppia di nodi vicini? • Assegnamento delle interfacce : data la topologia logica, come dovremmo assegnare i link logici alle interfacce? • Allocazione dei canali (Channel Assignment o CA): data la topologia logica e l’assegnamento delle interfacce, come dovremmo allocare le frequenze alle interfacce? • Routing : data la topologia logica, l’assegnamento delle interfacce e l’allocazione dei canali, attraverso quali link logici dovremmo inoltrare i pacchetti?. Questo approccio, sebbene sia già stato proposto in letteratura [2--7], è relativamente nuovo per quanto riguarda la sua applicazione al networking. L’approccio tradizionale è basato sul principio della layer transparency, il quale afferma che ogni layer agisce indipendentemente dagli altri, in modo tale da poter modificare diversi protocolli dello stesso layer senza toccare quelli degli altri, fintantoché forniscono lo stesso servizio agli strati soprastanti. Il vantaggio dell’approccio tradizionale è che lo sviluppo di un protocollo diventa più semplice e scalabile, tuttavia ha lo svantaggio di degradare le performance del throughput, perché dovremmo, inizialmente, (problema del routing) trovare il percorso ottimo per ogni utente della rete (con questa terminologia intenderemo un flusso di traffico tra una sorgente e una destinazione della WMN), e in seconda battuta, assegnare le frequenze alle interfacce (problema di CA) in modo da ridurre le interferenze, imponendo le route decise precedentemente. Così facendo non troveremmo la soluzione ottima. Al contrario, considerando quanto sopra come un unico problema, saremmo in grado di ottenere un throughput aggregato maggiore. Inizialmente proporremo (nel Capitolo 2) la formulazione Integer Linear Programming (ILP) proposta in [2], per definire i vincoli, le variabili ed i parametri del problema, dopodiché la modificheremo per modellare le interferenze con il physical interference model, piuttosto che con il protocol interference model. Il primo [5], [8], [9], [19], [29] calcola il Rapporto Segnale-Interferenza o SIR (Signal-toInterference Ratio) a ogni nodo e lo compara con una soglia appropriata, mentre il secondo. 9.

(5) è basato su considerazioni geometriche ed è più semplice, ma meno performante e flessibile [9], [19], [29]. Al momento il physical interference model è poco impiegato in letteratura. Un esempio è dato dal [20], in cui gli autori lo utilizzano nella progettazione di un algoritmo di scheduling per le WMN, al fine di aumentare il throughput ottenibile. La nostra è pertanto una proposta piuttosto originale, perché sfrutta il modello fisico per risolvere il problema congiunto dell’assegnazione delle frequenze e del routing. Una volta formulato il problema, ci preoccuperemo (nel Capitolo 3) di formalizzarlo con il linguaggio di descrizione matematica AMPL [10], [11] e di risolverlo con CPLEX [12], un risolutore di sistemi lineari con metodologia branch and bound (vedere Appendice B, [12] e [13]). Istanzieremo il problema per alcuni scenari di interesse e risolveremo il sistema ottenuto, andando poi a confrontare i valori della funzione obiettivo al variare del modello interferenziale utilizzato. Il problema di assegnare le frequenze alle interfacce in modo da soddisfare le esigenze di traffico e controllare le interferenze è NP-completo [20], perché può essere ricondotto al graph coloring problem [14]. Questo ci impedirà di risolvere il sistema per topologie troppo complesse, a meno che non usiamo metodi meta-euristici efficienti per trovare soluzioni sub-ottimali [15], ma ciò esula dagli scopi di questa tesi. Una alternativa potrebbe essere quella di trovare una formulazione analoga per un ambiente distribuito, in modo da evitare i problemi intrinseci delle soluzioni centralizzate :. Scalabilità : il nodo che deve eseguire l’algoritmo centralizzato, o Designed Router (DR), ha una visione globale della rete e quindi una quantità enorme di dati da gestire e di calcoli da effettuare; Affidabilità : il DR rappresenta un single-point-of-failure, pertanto, in caso di fallimento, la rete non potrebbe più aggiornare l’allocazione delle frequenze. Il DR, generalmente, è un router più potente degli altri e quindi non può essere sostituito da qualunque altro nodo, ma si necessitano delle tecniche di recovery e ridondanza ben pianificate.. 10.

(6) Lo scopo della tesi è quello di progettare e valutare un algoritmo distribuito per il Channel Assignment, che superi i limiti degli algoritmi centralizzati. Questo è quello che faremo nel Capitolo 4, mentre nel Capitolo 5 ci preoccuperemo di testare la bontà di una tale formulazione facendo delle simulazioni e commentandone i risultati. Alla fine dell’analisi discuteremo alcuni punti che si prestano ad uno sviluppo ulteriore e proporremo, nel Capitolo 6, una serie di possibili espansioni per migliorarlo e generalizzarlo. Nel Capitolo 7 esporremo le conclusioni di questa tesi.. 11.

(7)