RICERCA ITALIANA     

Modelli e algoritmi di ottimizzazione per il progetto di reti wireless

Università degli Studi di Roma "La Sapienza"

Abstract

Lo sviluppo di nuove tecnologie di trasmissione radio e la conseguente istallazione degli apparati sul territorio richiedono la soluzione di complessi problemi di progettazione e di pianificazione di reti.
Il progetto si propone di affrontare, con le metodologie proprie dell’ottimizzazione, la pianificazione, la gestione e l’integrazione di vecchie e nuove reti di trasmissione: le reti che utilizzano tecnologie assestate dovranno infatti convivere (e cooperare) a lungo con reti a nuova tecnologia, attingendo da una comune riserva di risorse (scarse).
Le nuove tecnologie investigate in questo progetto sono quelle per la diffusione radio-televisiva digitale, quali Terrrestrial Digital Audio Broadcasting (DAB-T) e Terrestrial e Handheld Digital Video Broadcasting (DVB-T/H); la tecnologia WiFi; la tecnologia WiMax.
Gli algoritmi di soluzione per i problemi di pianificazione di reti wireless coinvolgono spesso la soluzione di varianti di classici problemi di ottimizzazione combinatoria.
Tuttavia, a causa della grande estensione geografica delle reti coinvolte e della complessità dei modelli matematici per la rappresentazione delle nuove tecnologie, i modelli di ottimizzazione che ne derivano presentano un grandissimo numero di vincoli e di variabili continue e intere. Inoltre, vincoli e funzione obiettivo possono risultare non lineari. Ciò comporta che le istanze di interesse pratico dei problemi di pianificazione non possono essere risolte utilizzando le tecniche allo stato dell'arte. E' evidente quindi l'esigenza di sviluppare nuove metodologie per la soluzione di istanze di grande dimesione di questi problemi che possono spesso essere noti problemi di ottimizzazione o loro naturali variazioni.
Il progetto si pone quindi un duplice obiettivo. Da un lato, lo studio di nuove metodologie nell'ambito della programmazione matematica e dell'ottimizzazione combinatoria. Dall'altro lato, la modellazione e la soluzione di fondamentali e attualissimi problemi di pianificazione di reti radio. Il progetto prevede inoltre un elevato grado di integrazione fra i compiti delle diverse unità. Nello sviluppo degli algoritmi è infatti stipulato un approccio "bottom-up"; i metodi sviluppati dalle singole unità dovranno neccessariamente integrarsi per realizzare gli algoritmi conclusivi. I modelli per le tecnologie studiate da un'unità, infine, potranno essere esportati alle tecnologie d'interesse per altre unità. <<<

Coordinatore Scientifico del Programma di Ricerca

Antonio Sassano Università degli Studi di ROMA "La Sapienza"

Obiettivo del Programma di Ricerca

L’introduzione e l’affermazione di nuove tecnologie di trasmissione radio richiedono la soluzione di complessi problemi di progettazione di apparati e pianificazione di reti tramite l'applicazione di modelli e algoritmi opportuni.
Il progetto si propone di affrontare, con le metodologie proprie dell’ottimizzazione, la pianificazione, la gestione e l’integrazione di vecchie e nuove reti di trasmissione: le reti che utilizzano tecnologie assestate dovranno infatti convivere (e cooperare) a lungo con quelle a nuova tecnologia, attingendo da una comune riserva di risorse (scarse). Il principale obiettivo è quello di fornire avanzamenti metodologici sia nel settore delle telecomunicazioni che, conseguentemente, in quello della programmazione matematica e dell'ottimizzazione combinatoria.
Le nuove tecnologie investigate in questo progetto quelle per la diffusione radio-televisiva digitale, in particolare Terrrestrial Digital Audio Broadcasting (DAB-T), Terrestrial e Handheld Digital Video Broadcasting (DVB-T/H), la tecnologia WiFi e il WiMax.

Nell'ambito del settore delle telecomunicazioni, il progetto si propone i seguenti obiettivi:

1. Formulazioni di modelli di ottimizzazione per i problemi di pianificazione e ripianificazione. Formulazione dei problemi di routing su reti ad hoc magliate. Classificazione dei problemi e dei modelli.

2. Sviluppo di algoritmi per la pianificazione di reti di nuova tecnologia. Questa classe di problemi include la pianificazione di reti WLAN, la pianificazione di reti broadcasting digitali e lo studio di algoritmi di routing per reti multi-hop magliate.

3. Ripianificazione di reti esistenti. Si intende mettere a punto
un modello matematico che consenta l'ottimizzazione simultanea delle potenze di emissione e delle frequenze.
L'ottimizzazione simultanea supera i limiti dell'approccio decompositivo e appare come l'unico modo per ottenere soluzioni di buona qualità per problemi di grandi dimensioni. Obiettivo del progetto è ottenere formulazioni di Programmazione Lineare Intera migliori di quelle attualmente esistenti, utilizzando la decomposizione di Dantzig e Wolfe. Infine, si intende validare sperimentalmente queste formulazioni in un'esperienza computazionale.
Sviluppo di algoritmi di "detection" delle configurazioni attuali delle reti analogiche; algortimi di ripianificazione e ottimizzazione delle risorse.

Nell'ambito delle metodologie di ottimizzazione, gli obiettivi principali sono:

1. Algoritmi e Modelli di Set Covering
Per il caso di set covering non lineare verranno sviluppate nuove
metodologie basate su linearizzazioni, rilassamenti Lagrangiani e column generation. Verrà inoltre analizzata la complessità computazionale e la approssimabilità nel caso generale del problema e in alcuni casi particolari.

2. Estensioni del problema del massimo insieme soddisfacibile di vincoli lineari. Per questo problema si intendono sviluppare nuove tecniche di identificazione dei sottosistemi inammissibili e di separazione di vincoli associati violati.

3. Tecniche di column generation
3.1 Nel caso delle WLAN e nel caso del routing reti magliate ad hoc la
particolarità degli approcci di column generation risiede nella non
linearità del sottoproblema di pricing. Nel caso delle WLAN verranno
applicate tecniche di linearizzazione. Nel caso delle reti magliate ad hoc verrà esplorata una combinazione delle tecniche di ricerca operativa con quelle di constraint programming.
3.2 Per le formulazioni di tipo set-packing si intende sviluppare algoritmi per la soluzione di problemi di grandi dimensioni di tipo branch-and-price. Infine, si vuole dare un contributo sulle regole di branching.

Integrazione degli obiettivi a livello nazionale.

Infine, le diverse unità si propongono di studiare cooperativemente modelli di integrazione delle diverse tecnologie di trasmissione. Possibili obiettivi dell’integrazione sono (i) la scelta dell’opportuno mix di tecnologie per assicurare i servizi richiesti in una data area , (ii) realizzazione di servizi di boradcast interattivi, che cioè prevedano canali di ritorno single-cast, (iii) reti di trasmissione broadcast ad elevata mobilità (DVB-H). <<<

Durata

24 mesi

Base di partenza scientifica nazionale o internazionale

Una Rete di Telecomunicazione Wireless è caratterizzata da un insieme di trasmettitori ed un insieme molto vasto di ricevitori distribuiti sul territorio. Dato il grande numero di ricevitori e le loro caratteristiche di mobilità, per valutare una rete si divide l’area di interesse in piccole aree quasi quadrate dette testpoint, ciascuno dei quali riassume il comportamento di tutti i ricevitori presenti al suo interno. Il servizio offerto dai trasmettitori viene valutato al centro del quadrato (testpoint) che si dirà coperto se la qualità del segnale presente supera una certo valore di soglia (Amaldi et al. 2001)

Una delle esigenze più pressanti dei moderni sistemi di telecomunicazione è quella di far fronte alla richiesta di crescente flessibilità garantendo nel contempo la copertura e la qualità del servizio ad un costo competitivo. Inoltre l'insieme dei possibili servizi si sta allargando, andando dalla connessione internet, al video su domanda, alle comunicazioni in video e voce, alla diffusione. Un esempio è dato dalle reti Wireless LAN (WLAN) che stanno sostituendo le tradizionali reti cablate in molti ambienti lavorativi (uffici, ospedali, etc.) e in altri ambienti commericali (hotel, aeroporti, etc.). La presenza di vaste aree coperte da un serivzio wireless (come per esempio una Metro-web), oltre ad offrire a costi bassi gli abituali servizi web, può anche fornire supporto a una serie di nuovi servizi come il monitoraggio sanitario o di altri servizi pubblici, il controllo di accesso ad aree riservate, il sostegno a servizi di mobilità "intelligente". Questo tipo di reti non deve venire realizzato necessariamente utilizzando un solo tipo di tecnologia, ma può sfruttare differenti tecnologia (WLAN, trasmissione digitale, Wimax, reti "ad hoc" di tipo magliato, etc.) che si intregrano in base ai servizi richiesti e all'area da coprire.

Le reti wireless multihop magliate si stanno rivelando come una delle più promettenti soluzioni per la fornitura di una connessione wireless ad un costo competitivo. Le reti Wireles Magliate (WMN) includono una combinazione di nodi fissi e mobili connessi tramite link radio che formano una rete "ad hoc" magliata multihop. I dispositivi che compongono una WMN sono organizzati gerarchicamente in termini di funzionalità di connessione e caratteristiche hardware. Il successo dell'architettura WMN è principalmente dovuta alla sua flessibilità, al suo costo affrontabile e al fatto cheal suo interno possono coesistere e cooperare varie tecnologie. D'altro lato, questa flessibilità intrinseca pone interrogativi di ricerca interessanti a vari livelli. Sono vari i parametri che concorrono all'efficienza di una WMN: il numero di interfacce radio per ogni dispositivo, il numero di canali radio per interfaccia, il meccanismo di accesso, le strategie di routing e la specifica tecnologia wireless adottata per implementare il paradigma mesh, per citarne alcuni. Tutti questi parametri sono di fatto gradi di liberta che il progettista può sfruttare per realizzare una WMN efficiente, quindi un supporto da parte di strumenti quantitativi di ottimizzazione appare indispensabile. In letteratura sono apparsi molti lavori riguardanti l'ottimizzazione dei protocolli per le WMN (So and Vaidya. 2004; Das et al. 2005). A prescindere dal contesto applicativo, la WMN utilizzata dovrebbe avere buone caratteristiche in termini di copertura e throughput sia in uplink sia in downlink. A questo scopo una accurata pianificazione della posizione di routers e punti di accesso è di fondamentale importanza per determinare l'efficacia dell'intera rete. Il problema di decidere la posizione dei transceivers è stata ampiamente studiata in letteratura per diverse tecnologie wireless e sistemi cellulari di seconda e terza generazione, e in parte per le WLAN. Tuttavia la pianificazione di una WMN è differente rispetto a tutti gli altri casi già studiati. Infatti nei sistemi menzionati prima i transceiver radio (stazioni radio base, punti di accesso etc.) sono anche gateway verso la rete backbone cablata e la decisione riguardante la loro posizione è in qualche modo guidata dai requisiti di connettività locale, cioè la connettività da fornire a ciascun utente mobile e il più vicino transceiver. D'altro canto, nella pianificazione di una WMN due vincoli di connettività devono essere soddisfatti: il primo riguarda la connettività tra gli MC e il più vicino MR, il secondo riguarda la connettività multihop tra ogni MC e un MAP. In particolare il traffico da/a la rete cablata deve essere instradato su un cammino che connette l'MR a un MAP, almeno. In questo contesto, i limiti di capacità dei link radio tra i vari MR e tra MR e MAP gioca un ruolo fondamentale. Pertanto le decisioni su dove installare i nodi della rete e di che tipo (MAP o MR) dipende su vari aspetti tra cui la copertura degli utenti, la connettività radio tra MR e MAP e il flusso di traffico. Il problema di pianificazione risultante è completamente nuovo dato che deve considerare contemporaneamente la copertura radio degli utenti, come nei problemi classici di pianificazione di reti di accesso radio, e la gestione del flusso di traffico come nei problemi di progetto di reti cablate.

Il progetto di reti wireless singola frequenza (abbreviato in SF-WND) consiste nel determinare le potenze ottime emesse dai trasmettitori quando tutti gli altri parametri sono fissati. Questo problema appare in un gran numero di applicazioni e come "building block" per la soluzione di problemi multi-frequenza. Fra le applicazioni singola frequenza ricordiamo le reti cellulari con tecnologia W-CDMA di tipo UMTS (Amaldi et al. 2001; Eisenblätter et al. 2004) e le reti diffusione radio-televisive (Mannino et al. 2006; Rossi et al. 2001). Anche le reti GSM pur essendo reti multi-frequenza, sono spesso progettate in prima istanza risolvendo un problema a singola frequenza (Touhami et al, 2005). Un esempio di applicazione meno immediato è la ricostruzione di diagrammi di antenna in caso di informazione carente. Questa applicazione è di interesse per organismi di controllo statali, i quali vogliano monitorare la situazione interferenziale dei trasmettitori sul territorio nazionale (ad esempio per valutare l'inquinamento elettromagnetico) ma non dispongono di dati accurati nè di strumenti legislativi adatti al loro reperimento. L'applicazione di maggiore interesse per questo progetto nazionale è tuttavia l'utilizzo di un solutore per problemi singola frequenza all'interno di un algoritmo di soluzione di tipo "generazione di colonne" per i problemi multi-frequenza tipici della pianificazione di reti radio-televisive. Specificamente, la fase di generazione delle colonne corrisponderà esattamente alla soluzione di istanze opportune di (SF-WND). Il processo di ottimizzazione consiste nello stabilire valori opportuni dei parametri radioelettrici dei trasmettitori e dei ricevitori. In genere, un certo numero di parametri radioelettrici può assumere un solo valore prestabilito. I diversi problemi di ottimizzazione (e di pianificazione) che si presentano in letteratura (e in natura) possono essere classificati proprio in base all'insieme di parametri fissati e di parametri liberi. Quasi sempre, l'obiettivo consiste nel massimizzare il numero dei testpoint serviti, o la popolazione ad essi associata.

Nella pratica corrente, la pianificazione di rete avviene stabilendo il valore di ciascuno dei parametri (per ogni trasmettitore) indipendentemente dagli altri, che sono fissati ad un valore di riferimento. In accordo con tale decomposizione, anche la gran parte della letteratura scientifica si riferisce a problemi a singolo parametro. In effetti, i due filoni principali riguardano il problema di assegnamento delle frequenze (FAP) ed il problema di assegnamento delle potenze di emissione (ed un suo caso speciale in cui le potenze sono fissate e si chiede di decidere lo stato di attivazione di ciascun trasmettitore, Antenna Siting Problem (ASP)). Per quanto riguarda FAP molti degli articoli sono basati sul modello del grafo di interferenza (Aardal et al 2003; Leese et al. 2002), in cui i nodi corrispondono a trasmettitori e gli archi rappresentano coppie di trasmettitori che interferiscono su almeno un testpoint. Questo ha il vantaggio di ricondurre FAP a problemi di partizione di grafi (colorazione di un grafo, minimo k-taglio). Un’eccezione è rappresentata dal lavoro di Capone e Trubianin (1999) cui i testpoint non sono trattati in modo aggregato (come nel grafo d’interferenza), ma rappresentati esplicitamente nel modello. Al contrario, questo tipo di modello è tipico della letteratura riguardante il problema dell’assegnamento di potenze. In particolare, si introduce per ogni testpoint un vincolo di copertura dipendente dalla tecnologia della rete e spesso di struttura complessa (per ogni standard, la definizione di copertura di un testpoint è elaborata da organismi internazionali, quali la International Telecommunication Union). Di conseguenza, i contributi in letteratura propongono in gran parte tecniche generali di ottimizzazione, sia euristiche, come simulated annealing (Ligeti e Zander, 1999), tabu search (Amaldi et al. 2003), metodi quasi-Newton o gradiente coniugato (Sherali et al. 1996), che esatte, basate su formulazioni di programmazione intera (Mannino et al. 2006; Eisenblätter et al. 2004; Mathar e Schmeinck, 2001). Queste ultime, dette formulazioni SIR (Signal to Interference Ratio) sono derivate con tecniche di linearizzazione che permettono di esprimere la condizione di copertura con una disuguaglianza lineare nella potenza dei segnali ricevuti. La decomposizione del problema generale di pianificazione in problemi a singolo parametro porta spesso a risultati scadenti, soprattutto quando le risorse a disposizione (trasmettitori, frequenze) sono scarse. Questo è stato da noi sperimentato nell’ambito di diversi progetti applicati al progetto del sistema televisivo italiano (ad esempio si veda il Libro Bianco per la televisione digitale terrestre, 2001).

La maggior parte degli approcci risolutivi al problema di progettazione di reti wireless si basano sull'utilizzo di modelli di Programmazione Lineare Intera Mista . In particolare, diversi problemi presentati possono essere formulati in ultima analisi come problemi di Set Covering di grandi dimensioni. Una volta che il problema è stato formulato come un problema di Set Covering, la ricerca di una soluzione ottima o vicina all’ottimo di tale problema NP-hard rimane un problema di difficile soluzione. Questa osservazione è tanto più vera se si osserva che i problemi relativi al progetto di reti wireless sono in generale problemi di grandi dimensioni con un numero estremamente elevato di variabili. Per istanze di grandi dimensioni del problema sono stati sviluppate tecniche euristiche, riformulazioni e procedure esatte basate sulla struttura del problema.
Per quanto riguarda gli approcci euristici, si può affermare che praticamente tutti gli approcci euristici per la soluzione di problemi generali di programmazione intera sono stati applicati al Set Covering. In letteratura sono stati proposti sia algoritmi greedy (Fisher e Wolsey, 1982) che di ricerca locale (Jacobs e Brusco, 1995) così come algoritmi genetici (Beasley e Chu, 1996) e approcci basati sulle reti neurali (Aourid e Kaminska, 1994). Sfortunatamente nessun lavoro ha mai effettuato test comparativi tra tali metodi per stabilire sotto quali condizioni uno specifico approccio fornisce risultati migliori di altri. Inoltre è possibile inserire algoritmi euristici all’interno di algoritmi esatti per migliorare iterativamente il valore dell’upper bound e nello stesso tempo fornire una buona stima del lower bound del problema. Gli approcci esatti per risolvere problemi di Set Covering richiedono la generazione sia buoni limiti superiori ed inferiori al valore della soluzione ottima (Balas e Carrera, 1996). E’ possibile usare diverse euristiche tra quelle elencate per ottenere buoni upper bound per questi problemi. In generale, un lower bound al valore della soluzione ottima si ottiene risolvendo un rilassamento del problema di ottimizzazione (Balas e Carrera, 1996; Balas e Ho, 1980). In altre parole, si risolve un nuovo problema di ottimizzazione il cui insieme di soluzioni ammissibili contiene l’insieme ammissibile per il problema originario e il cui valore di funzione obiettivo calcolato nei punti ammissibili è più basso del valore di funzione obiettivo del problema originario. Un approccio alternativo per la soluzione di problemi di set covering è l’approccio Branch-and-Cut (Cornuejols e Sassano, 1989; Hoffman e Padberg 1993). Tale metodo risolve inizialmente il rilassamento continuo del problema originario e successivamente rafforza la formulazione aggiungendo nuove disequazioni valide all’insieme originario dei vincoli. In particolare esso richiede di individuare disuguaglianze lineari che sono violate dalla soluzione frazionaria corrente ma che sono soddisfatte da tutte le soluzioni ammissibili intere. Nonostante questo grande interesse suscitato dal problema, al momento non esistono ancora algoritmi esatti che riescano a trattare istanze del problema di grandi dimensioni quali ad esempio quelle che nascono dal problema di progetto di reti wireless. Obiettivo della ricerca sarà tentate di utilizzare i diversi risultati presenti in letteratura allo scopo di sviluppare un efficiente algoritmo di enumerazione di tipo Branch-and-Cut-and-Price che per permetta di risolvere in maniera esatta istanze di Set Covering di grandi dimensioni. <<<