MODELLO

nº	Cognome	Nome	Dipartimento	Qualifica	Settore Disc.	Mesi Uomo
1° anno	2° anno
1.	MALUCELLI	Federico	Dip. ELETTRONICA E INFORMAZIONE	Prof. Ordinario	MAT/09	6	7
2.	MAFFIOLI	Francesco	Dip. ELETTRONICA E INFORMAZIONE	Prof. Ordinario	MAT/09	5	5
3.	AMALDI	Edoardo	Dip. ELETTRONICA E INFORMAZIONE	Prof. Associato	MAT/09	5	5
4.	BORGONOVO	Flaminio	Dip. ELETTRONICA E INFORMAZIONE	Prof. Ordinario	ING-INF/03	2	2
	TOTALE					18	19

nº	Cognome	Nome	Università	Dipartimento	Qualifica	Settore Disc.	Mesi Uomo
1° anno	2° anno
1.	TARDELLA	Fabio	ROMA "La Sapienza"	Dip. MATEMATICA PER LE DECISIONI ECONOMICHE, FINANZIARIE E ASSICURATIVE	PO	MAT/09	1	1
	TOTALE						1	1

nº	Cognome	Nome	Dipartimento	Anno di inizio borsa	Durata (in anni)	Tipologia	Mesi Uomo
1° anno	2° anno
1.	Bruglieri	Maurizio	Dip. ELETTRONICA E INFORMAZIONE	2003	3	Post-doc	2	2
2.	Belotti	Pietro	Dip. ELETTRONICA E INFORMAZIONE	2003	3	Post-doc	4	4
3.	Cesana	Matteo	Dip. ELETTRONICA E INFORMAZIONE	2004	2	Post-doc	4	4
4.	Liberti	Leo	Dip. ELETTRONICA E INFORMAZIONE	2003	3	Post-doc	4	4
5.	Bosio	Sandro	Dip. MATEMATICA	2003	3	Dottorato	6	6
	TOTALE						20	20

nº	Qualifica	Costo previsto	Mesi Uomo	Note
1° anno	2° anno
1.	Borsista	19.000		11	Dottore di ricerca esperto in ottimizzazione da dedicare all'implementazione degli algoritmi e alla sperimentazione
2.	Borsista	19.000	11		Dottore di ricerca esperto in ottimizzazione
	TOTALE	38.000	11	11

Negli ultimi 10 anni l'influenza dei sistemi di comunicazione senza fili nella vita di tutti i giorni è cresciuta esponenzialmente. Pensiamo ad esempio alla diffusione della telefonia cellulare. Questo settore ha attirato notevole attenzione da parte dell'industria e dell'università sia per gli interessanti problemi legati alla nuova technologia, sia per i rilevanti interessi economici. I sistemi di comunicazione senza fili hanno indotto significativi miglioramenti nell'efficienza di molti ambienti lavorativi, soprattutto quelli in cui la flessibilità e la mobilità giocano un ruolo fondamentale.
Anche l'importanza delle reti locali (LAN) è ben noto: queste infrastrutture, in cui una rete cablata copre capillarmente l'area da servire e alla quale i singoli computer sono collegati via cavo, sono diventate essenziali nella maggior parte degli ambienti lavorativi. Per andare incontro alle esigenze di flessibilità e mobilità, l'accesso via cavo alle LAN viene sostituito da una connessione radio, dando luogo alle cosiddette Wireless LAN (WLAN). La domanda di WLAN è cresciuta vertiginosamente negli ultimi due anni grazie anche alla crescente diffusione dei computer portatili. Le WLAN possono fornire connettività e sostituire i cavi in una vasta gamma di contesti come ad esempio uffici, aeroporti, stazioni ferroviarie, bar e ristoranti [3].
Addirittura si può ipotizzare che, sostituendo le tradizionali LAN "indoor" e fornendo un accesso flessibile alla rete "outdoor", le WLAN possano competere con i sistemi cellulari (GSM, GPRS, UMTS, etc.) nel fornire servizi di comunicazione mobile. Il successo delle WLAN è anche basato sul fatto che la realizzazione pratica di una piccola rete è relativamente semplice e poco costosa se paragonata alla varietà di servizi che può fornire [4].
In ambito ospedaliero la flessibilità delle WLAN potrebbe permettere una notevole razionalizzazione di varie procedure di esercizio e gestione della sanità. Tra i tanti benefici possiamo citare una riduzione dei rischi di errori nell'assistenza sanitaria grazie a una rapida diffusione delle informazioni tra il personale ospedaliero [9]. Idealmente le WLAN dovrebbero poter sostenere la comunicazione di grandi quantità di dati multimediali, facendo così un passo verso la completa sostituzione di documenti cartacei, lastre radigrafiche e altri documenti grafici [10].

A causa delle particolarità del protocollo di accesso, pianificare anche solo una piccola rete WLAN considerando requisiti di qualità del servizio e di efficienza delle comunicazioni solleva una serie di questioni non banali. Innanzitutto il canale di comunicazione che connette alla rete è soggetto a interferenze e a errori. In secondo luogo, il canale di comunicazione è condiviso e le risorse radio sono spesso scarse. Questi due aspetti, che diventano cruciali quando la dimensione della rete cresce, devono essere affrontati con opportuni modelli di ottimizzazione e metodologie che possano aiutare nel processo di decisione.
Pianificare delle WLAN in ambienti ospedalieri risulta essere anche più complicato a causa della presenza di apparecchiature elettromedicali che utilizzano la stessa frequenza di trasmissione delle WLAN. Queste apparecchiature possono quindi interferire sulle trasmissioni e viceversa le trasmissioni possono compromettere il corretto funzionamento delle apparecchiature. In [11] è stato osservato che le comunicazioni delle WLAN non causano malfunzionamenti in vari apparati elettronici anche quando sono posti a stretto contatto di una antenna di trasmissione, mentre alcuni apparecchi elettromedicali possono ridurre la ricezione delle WLAN del 40%. Sebbene queste interferenze non sembrino mettere in pericolo il corretto funzionamento degli apparecchi biomedicali, devono essere considerate attentamente se si vuole pianificare una rete efficientemente.

Tra i vari standard di comunicazione senza fili, lo IEEE802.11b [1,2], noto commercialmente come WiFi, è quello che vanta la maggiore diffusione. Il livello fisico del Wifi si basa sulla frequenza di 2.4 GHz che non necessita di licenza. Gi organismi di standardizzazione hanno recentemente approvato una nuova versione che permette di elevare la massima velocità di trasmissione fino a 54 Mbps sia nella frequenza di 2.4 GHz (802.11g) [6] che in quella di 5GHz (802.11a) [7]. All'interno della banda disponibile l'Unione Europea permette l'uso di tre canali separati di trasmissione. L'accesso alla risorsa condivisa è regolato da un protocollo di tipo "Carrier Sensing Multiple Access with Collision Avoidance mechanism" (CSMA/CA) [8], secondo cui ogni comunicazione prima di inviare dati sul canale verifica che questo sia libero. In caso contrario, per evitare le collisioni, il tentativo viene ritardato di un tempo casuale.

Pianificare una WLAN con il protocollo 802.11b richiede di individuare i punti di accesso (AP) alla rete cablata in cui verrà piazzata una antenna. Inoltre per ogni antenna bisogna determinare il livello di potenza della trasmissione e assegnare una delle tre frequenze a disposizione a ciascun canale di comunicazione. A causa delle peculiarità del protocollo di accesso descritto sopra, il problema di pianificare una WLAN risulta particolarmente interessante e diverso dai problemi di pianificazione per altri tipi di reti senza fili. Infatti, mentre il costo di installazione non è un fattore di importanza decisiva a causa del costo esiguo delle antenne, la questione principale diventa trovare una configurazione di rete con un elevato livello di efficienza e capacità massima. Anche per reti di piccole dimensioni un piazzamento inadeguato dei punti di accesso può dar luogo a una rete dalle prestazioni molto degradate. È facile mostrare, anche su piccoli esempi, come una pianificazione più accurata può condurre a reti con un minor numero di punti di accesso e con una capacità superiore. Una pianificazione efficiente deve quindi basarsi su opportuni modelli di ottimizzazione e algoritmi che forniscano un valido supporto alla presa di decisioni.

In letteratura il problema di pianificare una WLAN è generalmente affrontato dal punto di vista qualitativo come in [21]. La maggior parte degli approcci quantitativi si concentrano sulla minimizzazione del numero di punti di accesso [20], senza considerare la capacità della rete, ed utilizzano modelli di tipo "set covering" [30]. Questo approccio è quello tipicamente utilizzato per la pianificazione di reti della seconda generazione [22] in cui problemi di grandi dimensioni sono risolti con euristiche randomizzate. Tutti questi modelli, poiché affrontano il vero e proprio dimensionamento della rete separatamente, nella fase di assegnamento di frequenze [28,29], non considerano aspetti legati all'interferenza e alla qualità del segnale. Questi aspetti non possono essere trascurati nella pianificazione di sistemi più complessi come i sistemi cellulari della terza generazione (es. UMTS) [27] o reti WLAN di grandi dimensioni [31], includendo il particolare meccanismo di accesso basato sul Carrier Sensing Multiple Access con l'eliminazione dei conflitti. Un tentativo di considerare la qualità del segnale nel caso delle WLAN è fatto in [24] in cui l'obiettivo è quello di minimizzare l'area coperta da un segnale di scarsa qualità. In [25] il problema è formulato con un modello di programmazione intera in cui si intende massimizzare la qualità del segnale nelle aree coperte, in base a una specifica funzione di priorità. In [26] si può trovare un primo tentativo di considerare la capacità della rete in un modello matematico.

Un altro aspetto da considerare nella pianificazione e nella realizzazione di una rete WLAN, specialmente in un ospedale, è la sicurezza dei dati [15]. Le comunicazioni radio sono per definizione vulnerabili agli attacchi esterni che possono minare la sicurezza delle trasmissioni e compromettere le prestazioni dell'intera rete. Le questioni riguardanti la sicurezza possono essere suddivise in due classi: autenticazione e protezione dei dati. La fase di autenticazione dovrebbe permettere l'accesso ai servizi della rete solo al personale autorizzato. In particolare solamente il personale medico o paramedico può accedere e/o modificare i dati della cartella clinica di un paziente e solo nei campi di competenza. L'altro aspetto di protezione dei dati riguarda lo scambio sicuro di informazioni a mezzo radio. Lo standard 802.11 definisce un algoritmo di crittografia chiamato WEP (Wireless Equivalent Protocol) per proteggere l'informazione [16]. Dato che la sicurezza è un aspetto cruciale per determinare il successo delle WLAN sia organi di standardizzazione sia gruppi di ricerca stanno lavorando per migliorare il livello di sicurezza da tutti i punti di vista [17,18,19].
In ogni caso gli aspetti di sicurezza devono venire considerati anche per poter dimensionare adeguatamente la rete con l'obiettivo di massimizzarne le prestazione.

The impact of wireless networks in everyday life has been growing dramatically during the last decade, in particular with the widespread diffusion of cellular telephone systems. Industry and academia have been attracted to this area by the challenging technological and research issues as well as by the large market revenues. Wireless systems have led to considerable efficiency improvements in many working environments in which mobility and flexibility play a fundamental role. Also the importance of Local Area Networks (LANs) is well known: these infrastructures in which a backbone cabled network span the service area and single computers are directly linked to the network with a cable became essential in most working environments. In order to meet flexibility and mobility requirements, the wired access to the network can be substituted with a wireless (radio) connection, giving rise to the so called Wireless Local Access Networks (WLANs). Demand for WLANs has grown at an impressive pace over the past couple of years due to the ever wider diffusion of laptops and personal mobility products. WLANs can provide connectivity and cable replacement in a variety of settings such as office buildings, airports, railway stations, and bars [3]. By replacing traditional indoor wired local networks and allowing flexible access outdoor, WLANs could eventually even compete with classical cellular systems (GSM, GPRS, UMTS, etc.) in the provision of wireless services. The success of WLANs also relies on the fact that the deployment of a small network is relatively simple and inexpensive compared to the variety of services it can provide [4]. In hospital environments the flexibility of WLANs would help in rationalizing various health care processes and reducing the risk of medical errors thanks to a rapid spread of information among hospital personnel [9]. Ideally WLANs in hospital should support the transmission of large amount of data, involving also multimedia [10], making a step towards a so-called paperless and filmless hospital.

Due to the wireless local access mechanism, planning even a small size WLAN while taking into account important quality and efficiency requirements raises a number of challenging issues. Indeed, the radio channel is prone to errors and temporary failures due to interference which are not encountered in the wired case. Moreover, the channel is shared and radio resources are often scarce. These two aspects, which become crucial when the network dimension increases, require appropriate optimization models and methodologies to support planning decisions. Planning WLANs in hospital environments turns out to be even more involved since electronic biomedical devices, which work in the same range of frequency of WLANs, may interfere with the wireless transmissions and vice versa. In [11] it is observed that WLAN communications does not trigger malfunction on some electronic equipments even in the proximity of an access point and that the medical devices can reduce the reception rate of the access point by up to 40%. Although these interferences do not critically affect the operation of the medical devices and WLAN, they need to be carefully considered in order to plan the network efficiently while guaranteeing correct operation of biomedical electronic devices.

Among the numerous standards for wireless communications, the IEEE802.11b [1,2], which is commercially known as WiFi, is the most used. The IEEE802.11b physical layer works in the unlicensed 2.4 GHz band. The standardization bodies have recently approved new versions which allow to increase the maximum speed to 54 Mbps both in the 2.4 (802.11g) [6] and 5 GHz bands (802.11a) [7]. Within the available bandwidth, the European Community allows the usage of three non overlapping frequency channels. The access to the shared resource is driven by a Carrier Sensing Multiple Access with Collision Avoidance mechanism (CSMA/CA) [8], that is each communication aiming at transmitting senses the channel before pushing data and initiates the real transmission if and only if the channel is sensed as idle. Furthermore, in order to avoid collisions, after the sensing phase, if the channel is sensed as idle the station willing to transmit starts its transmission phase after a random drawn back-off.

Planning a WLAN with 802.11b standard amounts to locating the radio access points ("hot spots") in suitable positions of the cabled network, selecting the emission power for each access point and assigning a frequency to each transmission channel. Due to the peculiarities of the access protocol, planning WLAN turns out to be particularly challenging and to differ from analogous wireless network planning problems. Indeed, while the installation cost is usually not a primary concern due to the very low costs of the access points, the main issue is to plan a network having high capacity and efficiency. Even for medium size networks an inadequate placement of the access points can give rise to a very poorly performing network. It is easy to show, even on some small examples, that a more accurate planning yields a network with a smaller number of access points but a much higher capacity. Efficient planning must be based on suitable optimization models and algorithms that support quantitatively the planner decisions.

In the literature the problem of planning WLAN has mainly been addressed from a qualitative point of view as in [21]. The few quantitative approaches for planning WLANs [20] focus on minimizing the number of APs like for GSM cellular systems (see e.g. [22]) in which large scale problems are solved by means of randomized heuristics [23]. In these cases, the models and methods do not consider interference and signal quality, since these aspects are accounted for in the subsequent network dimensioning phase, namely in the frequency assignment problem [28,29]. When planning systems with more complex access mechanisms such as UMTS [27] or large-scale WLANs [31], these aspects cannot be neglected including the explicit consideration of the peculiarities of the Carrier Sensing Multiple Access (CSMA) with collision avoidance mechanism. An attempt to consider signal quality in WLAN planning is made in [24] where the objective is to maximize the area covered with an adequate signal level, while minimizing the area with poor signal. In [25] an integer programming formulation of the problem that maximizes the signal quality in the covered areas according to a given priority parameter is proposed. A first attempt to account for the network capacity in a mathematical model can be found in [26].

Security is another aspect to be considered when planning and deploying a WLAN, especially in a hospital [15]. The wireless media is by definition vulnerable to external attacks which can undermine the security of each transmission and eventually impair the performances of the whole networks. Security issues can be roughly divided into authentication and data protection. The authentication phase should allow only specific users to access the services provided by the network. For example, in a medical environment only doctors should be allowed to access the online patients clinical records service, therefore an effective authentication process is needed. On the other hand, data protection specifically deals with the secure exchange of information on the wireless medium. The 802.11 standard defines a data encryption algorithm named WEP (Wireless Equivalent Protocol) in order to protect the information [16]. Since security is a crucial point to determine the success of WLANs, both the research community and the standardization bodies are still working to enhance the security level of both the authentication and the data protection phase [17,18,19]. In any case security aspects must also be considered when dimensioning the network so as to maximize its performance.

[1] http://grouper.ieee.org/groups/802/11/

[2] IEEE Standard 802.11, "Wireless LAN media access control (MAC) and physical layer (PHY) specifications", 1999.

[3] http://www.eweek.com/article2/0,3959,485099,00.asp

[4] http://www.pcworld.com/news/article/0,aid,111418,00.asp

[5] Haitao Wu, Shiduan Cheng, Yong Peng, Keping Long, Jian Ma, "Does the IEEE 802.11 MAC protocol work well in multihop wireless ad hoc networks?, IEEE Communication Magazine, Volume 39, Issue 6, June 2001.

[6] IEEE 802.11g , Wireless LAN Medium Access Control 15 (MAC) and Physical Layer (PHY) specifications: Further Higher Data Rate Extension in the 2.4 GHz Band, 2003.

[7] 802.11 a

[8] L. Kleinrock and F. Tobagi, Packet Switching in Radio Channels. I. Carrier Sense Multiple Access Models and Their Throughput Delay Characteristics, IEEE Transanctions on Communications, vol. COM23, no. 12, pp. 1400-1416, Dec. 1975.

[9] R. A. Wilcox and E. M. Whitham "Reduction of medical error at the point-of-care using electronic clinical information delivery", Internal Medicine Journal (2003), 33: 538-541.

[10] U. Engelmann, A. Schröter, E. Borälv, T. Schwitzer, H.-P. Meinzer, "Mobile teleradiology: all images everywhere", International Congress Series 1230 (2001) 844-855.

[11] E. Hanada, Y. Hoshino, H. Oyama, Y Watanabe, Y. Nose, "Negligible electromagnetic interaction between medical electronic equipment and 2.4 GHz Wireless LAN", Journal of Medical Systems (2002) v. 26 no. 4, 301-308.

[12] S. Hurley, Planning Effective Cellular Mobile Radio Networks}, IEEE Transactions on Vehicular Technology, vol. 51, no. 2, March 2002, pp. 243-253.

[13] A. Hills, Large-Scale Wireless LAN Design, IEEE Communications Magazine, vol. 39, no. 11, Nov. 2001, pp. 98-107.

[14] N.R. Prasad, IEEE 802.11 system design, IEEE International Conference on Personal Wireless Communications, 2000, Page(s): 490 -494.

[15] J.C. Frenzel "Data security issues arising from integration of wireless access into healthcare networks" Journal of Medical Systems (2003) V. 27, No. 2 163-175.

[16] WEP basic

[17] J. Walker, "Unsafe at any key size: an analysis of WEP encapsulation", IEEE 802.11-00/362, IEEE Press, 2000.

[18] IEEE Std 802.11i/D4.1, draft 802.11i version 4.1, IEEE, July 2003.

[19] Cyrus Peikari, Seth Fogie, "Maximum Wireless Security", Sams, 2002.

[20] A. Hills, Large-Scale Wireless LAN Design, IEEE Communications Magazine, vol. 39, no. 11, Nov. 2001, pp. 98-107.

[21] N.R. Prasad, IEEE 802.11 system design, IEEE International Conference on Personal Wireless Communications, 2000, Page(s): 490 494.

[22] K. Tutschku, Demand-based radio network planning of cellular mobile communication systems, IEEE INFOCOM 1998, pp. 1054–1061.

[23] S. Hurley, Planning Effective Cellular Mobile Radio Networks, IEEE Transactions on Vehicular Technology, vol. 51, no. 2, March 2002, pp. 243-253.

[24] M. Kamenetsky, M. Unbehaun, Coverage planning for outdoor wireless LAN systems, 2002 International Zurich Seminar on Broadband Communications Access, Transmission, Networking, 2002, Page(s): 491 -496.

[25] R.C. Rodrigues, G.R. Mateus, A.A.F. Loureiro, On the design and capacity planning of a wireless local area network, Network Operations and Management Symposium, 2000. NOMS 2000, Page(s): 335348.

[26] Y. Lee, K. Kim, Y. Choi, Optimization of AP placement and Channel Assignment in Wireless LANs, IEEE Conference on Local Computer Networks, 2002. LCS 2000.

[27] E. Amaldi, A. Capone A., F. Malucelli "Planning UMTS base station location: optimization models with power control and algorithms" IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS. (2003). vol. 2 pp. 939-952.

[28] K.I. Aardal, S.P.M. Van Hoesel, A.M.C.A. Koster, C. Mannino, A. Sassano "Models and solutions techniques for frequency assignment problem" 4OR, vol.1 n. 4 (2003) 261-317.

[29] FAP web: www.fap.zib.de

[30] S. Ceria, P. Nobili, A. Sassano , "Set Covering Problem", in Annotated bibliographies in Combinatorial Optimization, Dell'Amico M., F. Maffioli, S. Martello eds, John Wiley and Sons - Chichester.

[31] A. Hills, J. Schlegel, "Rollabout: a wireless design tool", IEEE Communications Magazine, February 2004, 132-138.

I principali obiettivi di questa Unità di Ricerca consistono nel definire le caratteristiche operative di una rete WLAN operante in ambiente ospedaliero, individuare modelli di ottimizzazione e sviluppare algoritmi di ottimizzazione e strumenti software per aiutare le decisioni nel processo di progetto e realizzazione di WLAN. In ambiti complessi come gli ospedali le prestazioni della rete devono essere tali da garantire un supporto adeguato ai servizi previsti e le interferenze elettromagnetiche sono particolarmente critiche.

La maggior parte dei componenti dell'unità di Ricerca di Milano lavorano congiuntamente dal 1998 affrontando problemi sia dal punto di vista delle reti di telecomunicazione sia dal punto di vista dell'ottimizzazione. Recentemente hanno sviluppato ricerche riguardanti la pianificazione di reti cellulari della seconda e della terza generazione curando in particolare aspetti relativi all'interferenza e alla qualità del segnale, così come vari problemi di ottimizzazione emergenti nel progetto di reti ottiche. La loro esperienza copre i campi delle reti di telecomunicazione, la programmazione matematica, l'ottimizzazione combinatoria e gli algoritmi.

I problemi di pianificazione di copertura radio vengono affrontati classicamente discretizzando il problema ovvero considerando un insieme di siti candidati ove è possibile installare i punti di accesso ("access point" AP) e un insieme di possibili posizioni dei terminali degli utenti ("test point" TP) nell'area da coprire. Gli AP sono quindi installati in un sottoinsieme di siti candidati in modo che il livello di potenza del segnale ricevuto/inviato da tutti i TP sia sufficiente. I livelli del segnale, che dipendono dalla propagazione del canale tipica delle varie zone considerate e delle frequenze utilizzate, possono venire misurati sul campo o stimati utilizzando appositi simulatori elettromagnetici. I TP assegnati a un medesimo AP definiscono una cella. Una volta che gli AP sono stati posizionati e le celle individuate, a ogni AP viene assegnata una frequenza di canale in base a vari criteri che considerano tipicamente le interferenze tra AP che utilizzano lo stesso canale. Le soluzioni di copertura radio (caratterizzate dalla posizione degli AP e la loro configurazione e dalla definizione delle celle) sono valutate in base a vari obiettivi che includono il costo di installazione, la capacità della rete (garantendo un determinato livello di qualità di trasmissione del segnale) e la complessiva esposizione di aree protette alle emissioni elettromagnetiche. Questo tipo di approccio modellistico è tipicamente adottato per la pianificazione di reti wireless di grandi dimensioni, come nel caso della telefonia cellulare di seconda e terza generazione, o nel caso di reti di diffusione audio-video terrestre digitale e analogica.

In linea di principio una simile impostazione potrebbe venire adottata anche nel caso delle WLAN. Tuttavia, siccome il protocollo IEEE802.11b è stato inizialmente adottato nel caso di un solo AP, l'attenzione è stata dedicata principalmente a replicare via radio il funzionamento di una rete locale LAN cablata, piuttosto che concentrarsi sulle problematiche della pianificazione di reti di grandi dimensioni. Infatti, in presenza di un solo AP, l'interferenza è trascurabile e il protocollo si dimostra essere molto efficace fornendo una banda elevata agli utenti. Al contrario, la situazione diventa più critica quando l'802.11.b è usato in situazioni in cui l'interferenza è significativa, come in reti strutturate a celle con differenti AP cooperanti. Quando un gran numero di AP devono venire piazzati e le celle risultanti si intersecano causando interferenze e conflitti negli accessi, approcci banali basati sull'esperienza e sul buon senso (come per esempio quelli che tendono a minimizzare il numero di AP) o semplici estensioni del caso di reti con un solo AP possono generare soluzioni in cui la rete ha bassissime prestazioni in termini di capacità e qualità del servizio. Le peculiarità del meccanismo di accesso 802.11b deve venire considerato esplicitamente dato che contribuiscono notevolmente ad influenzare il processo di pianificazione. Oltre agli aspetti menzionati sopra che sono comuni al progetto di qualsiasi rete wireless, le interferenze e i conflitti di accesso dovuti alla sovrapposizione di celle devono venire considerati in modo esplicito. In ambienti ospedalieri, l'interferenza tra gli AP 802.11b e apparati elettromedicali è altrettanto cruciale. Da una parte gli apparati elettromedicali devono venire preservati nei confronti di interferenze provenienti dalla rete WLAN che possono pregiudicarne il corretto funzionamento. Dall'altra parte l'interferenza prodotta da apparati elettromedicali potrebbe influenzare significativamente la qualità della comunicazione e le prestazioni della rete. Il problema di pianificazione diventa ancora più complicato se si tengono conto di vincoli atti a limitare le emissioni di onde elettromagnetiche in certe aree dell'ospedale come le sale operatorie o le zone in cui i pazienti stazionano permanentemente.
Le caratteristiche tipiche delle WLAN e dell'ambiente ospedaliero spingono allo sviluppo di nuovi modelli matematici, alla realizzazione di algoritmi e strumenti software per poter generare soluzioni di reti ad alta capacità ed efficienti da un punto di vista dei costi.

Il programma di ricerca è organizzato nelle quattro fasi seguenti.

Fase 1

Sebbene la letteratura scientifica scarseggi di contributi sulla pianificazione delle WLAN, principalmente a causa del fatto che studi sistematici riguardanti l'argomento sono iniziati solo recentemente, in questa prima fase de progetto verrà condotta una approfondita analisi dello stato dell'arte coinvolgendo anche settori affini. In particolare verranno analizzate le analogie e le differenze con problemi di pianificazione di reti wireless di altro tipo, come per esempio quelle della telefonia cellulare, e verranno considerate le possibili estensioni dei modelli e degli algoritmi al caso delle WLAN.

In questa fase l'Unità di Ricerca di Milano collaborerà anche con le Unità di Reggio Emilia e di Ferrara per definire le specifiche tecnologiche per la realizzazione di una WLAN in un ospedale, in modo da soddisfare le esigenze delle applicazioni che si baseranno sulla rete. In base alle specifiche applicazioni individuate dal personale sanitario e al tipo di interfaccia uomo-macchina, l'unità di Milano individuerà le soluzioni tecnologiche più adeguate per fornire un supporto sufficientemente capace alle comunicazioni tenendo conto delle varie tipologie di dati che verranno trasmesse (ad esempio, dati numerici, immagini ad alta risoluzione, filmati, voce). Oltre a considerare normali comunicazioni di tipo client-server, verranno anche presi in esame possibili modi di implementare comunicazioni di tipo peer-to-peer.

Altri aspetti importanti trattati in questa fase riguardano l'analisi di modelli di propagazione in ambienti chiusi e in presenza di ostacoli, curando gli aspetti tecnici riguardanti la presenza di apparati elettromedicali. Questi ultimi aspetti verranno curati dal punto di vista dell'influenza sulle trasmissioni (in particolare di come il funzionamento di alcuni apparati elettromedicali possa degradare la qualità della trasmissione) e dal punto di vista del corretto funzionamento degli apparati elettromedicali (cioè, come le trasmissioni di una WLAN possono compromettere il funzionamento degli apparati elettromedicali). In particolare questi aspetti verranno studiati nel caso delle sale operatorie e nel caso di vicinanza di pazienti portatori di pacemaker o altri apparati di vitale importanza. Questa parte di lavoro verrà condotta in stretto contatto con le unità di Lecce e Ferrara che hanno il compito di studiare e mettere a punto modelli di propagazione, simulatori e di verificarne i risultati sul campo.

Durata: 4 mesi
Risultati attesi:
1. Rassegna della letteratura e analisi di analogie e differenze del problema di pianificazione di WLAN e quelli di pianificazione di altri tipi di reti wireless.
2. Definizione delle specifiche tecnologiche di una WLAN in ospedale, includendo i tipi di trasmissione da realizzare (client-serve e peer-to-peer), la capacità media della rete e i possibili vincoli di qualità del servizio (QoS).
3. Definizione del tipo e del formato dei dati di propagazione e dei requisiti di sicurezza.

Fase 2

L'obiettivo principale di questa fase è quello di costruire modelli di ottimizzazione che possano catturare ad un adeguato livello di dettaglio gli aspetti più significativi che emergono nella pianificazione di reti WLAN, con particolare attenzione alle particolarità degli ambienti ospedalieri. In primo luogo verranno definiti opportune modalità di misurare le prestazioni di una rete (funzioni obiettivo), in collaborazione con le unità di Lecce e Ferrara. Particolare attenzione verrà prestata non solo ai costi di installazione e della rete cablata ma soprattutto all'effetto dovuto alla sovrapposizione delle celle che dovrebbe quantificare l'impatto delle interferenze sulla qualità delle comunicazione e dell'esposizione ai campi elettromagnetici. Verranno approfonditi anche vari modi di misurare la capacità della rete.

Come accennato in precedenza, i modelli di ottimizzazione dovrebbero estendere i modelli classici di localizzazione in cui gli AP da attivare vengono scelti da un insieme di siti candidati. Due classi di modelli sembrano essere di particolare interesse. Nella prima classe vengono considerati dei vincoli espliciti di copertura, ovvero si impone che ongi TP appartenga ad almeno una cella. Nella seconda classe invece questi vincoli vengono rilassati. Al contrario dei classici casi di localizzazione, nel caso delle WLAN anche questi problemi risultano particolarmente interessanti quando si considera la massimizzazione della capacità della rete.

Un aspetto cruciale da considerare nei modelli di ottimizzazione è l'effetto delle interferenze sulla qualità della soluzione. Se l'obiettivo è massimizzare la capacità della rete, si dovrebbero privilegiare soluzioni (quindi insiemi di siti candidati in cui installare degli AP) che danno luogo a celle piccole e non sovrapposte. Considerando l'effetto delle sovrapposizioni le formulazioni matematiche dovrebbero dare luogo a problemi di ottimizzazione combinatoria non lineare. Questo conduce a una nuova e interessante classe di problemi di copertura che lascia intravedere un fertile e stimolante filone di ricerca nell'ambito dell'ottimizzazione e degli algoritmi. Verranno anche studiate le connessioni e le analogie con altri problemi classici per cogliere possibili estensioni. In particolare, mentre il problema che impone la copertura totale è una generalizzazione del noto problema del "set covering" [30], i modelli che non richiedono la copertura totale potrebbero avere qualcosa in comune con i problemi di ottimizzazione di funzioni submodulari.

Un altro aspetto del problema che merita indubbiamente attenzione è quello riguardante l'assegnamento di frequenze. Sebbene i problemi di assegnamento di frequenze siano stati approfonditamente esplorati per i sistemi di telefonia cellulare di seconda generazione come il GSM [28,29], questi problemi sono stati sempre affrontati separatamente e solo in pochi casi sono stati considerati durante la pianificazione della copertura radio. A differenza del caso del GSM, sembra che nel caso delle WLAN, la pianificazione della copertura e l'assegnamento di frequenze siano strettamente collegate, specialmente in un ospedale dove sono presenti altre fonti di onde elettromagnetiche.

Infine verrà analizzata la complessità computazionale di questi problemi e istanze test di piccole dimensioni verranno affrontate mediante l'utilizzo di solutori commerciali di problemi di ottimizzazione come ad esempio CPLEX.

Durata: 6 mesi.
Risultati attesi:
1. Vari modelli di ottimizzazione con diverse funzioni obiettivo e vincoli. Studio della loro complessità computazionale.
2. Risultati computazionali preliminari su piccole istanze.

Fase 3

Verranno sviluppati opportuni metodi di soluzione per i modelli di ottimizzazione forniti e studiati nella fase 2, considerando diverse funzioni obiettivo e tipi di vincoli. La struttura di questi problemi verrà analizzata approfonditamente e verranno considerati vari metodi di soluzione. Inoltre verranno individuati, ove possibile, casi speciali dei problemi che risultino essere più semplici da risolvere. Per questi casi semplici verranno forniti metodi di soluzione esatta basati sul rilassamenti, Branch & Bound e Branch & Cut. Quando possibile, i rilassamenti faranno riferimento a algoritmi efficienti per l'ottimizzazione di flussi su reti, per poter rendere più efficienti i metodi di soluzione. La possibilità di sfruttare la particolare natura geometrica del problema verrà anche studiata.
A causa dei numerosi aspetti pratici che fanno parte della pianificazione di una WLAN descritti in precedenza, i modelli più realistici dovrebbero risultare estremamente difficili da risolvere anche per istanze di piccole dimensioni. Sarà quindi necessario sviluppare algoritmi euristici efficienti. Questi aspetti del lavoro veranno curati in collaborazione con l'Unità di Ferrara.
Oltre ai dati relativi alla posizione degli AP e dei TP, le euristiche devono prendere in input i dati relativi alla propagazione elettromagnetica e devono interfacciarsi adeguatamente con i simulatori elettromagnetici. Questi aspetti verranno curati in collaborazione con l'Unità di Lecce.

Durata: 9 mesi
Risultati attesi:
1. Analisi della struttura dei modelli, includendo lo studio di eventuali casi di più semplice soluzione.
2. Algoritmi esatti ed euristici.
3. Risultati sperimentali su dati realistici

Fase 4

In questa fase il lavoro verrà dedicato all'integrazione del software prototipale sviluppato dall'Unità di Milano con quello sviluppato dalle altre unità. Verranno individuati i modelli matematici più appropriati e i metodi di soluzione più efficaci, in base ai risultati di una approfondita campagna sperimentale su dati reali. Verranno anche introdotti opportuni parametri di calibrazione per poter variare di volta in volta l'influenza dei vari fattori, quali costi, capacità della rete e esposizione ai campi elettromagnetici.

Verrà anche condotta una analisi degli esistenti sistemi di sicurezza nelle comunicazioni senza fili e verranno individuati i protocolli più adatti ad un utilizzo in ambente ospedaliero in base alle indicazioni derivanti dalle applicazioni messe a punto dall'Unità di Reggio Emilia.

Durata: 5 mesi
Risultati attesi:
1. Sistema integrato di pianificazione di reti WLAN
2. Specifiche per la sicurezza dei dati e l'accesso alla rete
3. Campagna sperimentale su dati reali.

The main objectives of this Research Unit (RU) are to define the technical characteristics of a WLAN in a hospital, to construct optimization models and to develop optimization algorithms as well as software tools for supporting decisions when planning and deploying a WLAN. In complex environments such as hospitals, the network must guarantee various type of services and the electromagnetic interferences are particularly critical.

Most of the members of the Milan RU have been collaborating since 1998 on telecommunication systems, covering networking as well as optimization aspects. Recent projects have, for instance, been devoted to planning second and third generation cellular networks planning (considering interference and signal quality aspects) and to several problems arising in designing optical networks. Their fields of expertise include telecommunication networking and simulation, as well as mathematical programming, combinatorial optimization and algorithms.

Classical approaches to radio coverage planning consider a set of candidate sites where Access Points (APs) can be installed and a set of possible user terminals positions (Test Points, TP) in the service area. APs are then installed in a subset of candidate sites so that the power level of the signal received/sent from/to all considered TPs is high enough. The signal levels, which depend on the channel propagation, can be measured on the field or can be predicted by using suitable electromagnetic simulators. The TPs assigned to the same AP define a cell. Once the APs have been positioned and the cells of the network have been identified, each AP is assigned a frequency channel according to several criteria which usually take into account the interference among APs using the same channel. Radio coverage solutions (characterized by the AP locations and configurations, the assignment of TPs to APs and the assignment of frequencies to APs) are evaluated according to different objectives, including installation cost, network capacity (guaranteeing a certain level of transmission quality), and the overall exposition of protected areas to electromagnetic emissions. This type of modeling approach is usually adopted for planning large wireless networks such as second (third) generation cellular systems, or analogical or digital audio-video broadcasting networks.

In principle a similar planning approach could also be considered for WLANs. However, since the IEEE802.11b protocol was originally devised for single AP settings, attention was devoted more to replicate the Local Area Network access mechanism and management in a wireless environment, than to make efficient planning of large-scale networks easy. Indeed, in the presence of a single AP, the interference is negligible and the protocol is shown to be highly effective in providing bandwidth to the mobile users. On the contrary, many problems arise when 802.11b is used in a setting where interference is relevant, such as in infrastructured cellular-like networks with different APs cooperating to provide connectivity. When a large number of APs must be positioned and the cells (corresponding to the possible AP locations) overlap causing interference and access conflicts, naive approaches based on experience and rules of thumb (aiming for example at installing the minimum number of APs) or simple extensions of the single AP case may yield very poor planning solutions in terms of network capacity. The peculiarities of the 802.11b access mechanism must be explicitly considered since they can substantially affect the coverage planning process. Besides the "standard" above-mentioned aspects of the problem, the interferences and access conflicts due cell overlaps need to be taken into account. In hospital environments, the interference between IEEE802.11 APs and biomedical devices is also crucial. On the one hand, biomedical electronic devices must be highly protected against any possible disruptive interference coming from the APs of the wireless networks. On the other hand, the interference produced by these devices could substantially affect the communication quality and the network capacity. The planning problem becomes even more complex if electromagnetic emissions must be limited in certain areas such as those where patients are permanently hosted. The peculiar characteristics of WLANs and of the specific setting under consideration call for novel models, algorithms and software tools to determine high capacity and cost efficient solutions to WLAN coverage planning.

The research program is organized into the four following phases.

Phase 1

Although the literature on planning WLANs seems rather poor, mainly due to the fact that systematic work on this type of planning problems started recently, a thorough analysis of the state of the art will be carried out. In particular, the similarities and differences with respect to the problems of planning other types of wireless networks, such as for instance cellular systems, will be investigated. Possible extensions of classical models and algorithms to the case of WLANs will be considered.

In this phase, Milan Research Unit will collaborate with the Reggio Emilia and Ferrara units to specify the technological requirements of the WLAN to be deployed in a hospital so as to meet the needs of the applications requested by the medical personnel. Depending on the specific applications and the way the human-machine interface can be implemented, we will identify the most suitable technological solutions to provide fast enough communications for the various type of data (e.g., numerical data, images, streaming video, voice). Besides considering client-server communications, we will also assess whether peer-to-peer communications has to be supported.

Other important aspects to be addressed at this stage concern the analysis of propagation models for indoor environments and the technical issues related with the interference of biomedical electronic devices. The latter aspects will be considered both from the transmission point of view (how biomedical devices can affect the transmission quality of the APs or of the user terminals?) and from the correct operation of biomedical devices point of view (how WLAN transmissions can disturb the operations of biomedical devices?), with particular attention to the operating rooms. Safety requirements in terms to EM emissions will be also identified for patients carrying pacemakers or other vital devices whose operation can be affected by WLAN transmissions. Milan RU will collaborate on these issues with the Lecce and Ferrara RUs, which are in charge of developing the propagation models, simulators and verify on the field the obtained results.

Time span: 4 months
Expected results:
1. Literature review and thorough analysis of the difference and similarities between the problem of planning WLANs and those of planning other types of wireless systems.

2. Specification of the WLAN technological requirements, including typeof transmissions (centralized and peer-to-peer), bandwidth requirements, average capacity, possible Quality of Service (QoS) constraints.

3. Definition of the type/format of propagation data and of the safety requirements.

Phase 2

The main objective of this phase is to construct optimization models that capture the relevant aspects of WLAN planning problems at an appropriate level of detail, with particular attention to the peculiarities of hospital environments. First, suitable measures of network performance (objective functions) will be defined in collaboration with the Lecce and Ferrara RUs. Attention will be devoted not only to installation costs and possibly backbone cabled network costs but also to the effect of "cell" overlapping, which should quantify the impact of interference on the communication quality, and to the exposure to electromagnetic fields. Various ways to evaluate the network capacity will be investigated.

As previously mentioned, the optimization models should extend standard location models where APs must be selected from a set of candidate sites. Two main classes of models seem to be of interest. The first one could contain explicit covering constraints imposing that each TP is served, namely that it belongs to at least one cell. But in the WLANs setting these covering constraints could also be relaxed at least for a subset of TPs, giving rise to equally interesting problems.

A crucial aspect that the optimization models must take into account is the effect of interferences on the solution quality. If the aim is to maximize the network capacity, one should select solutions (i.e., sets of candidate sites in which to install APs) in which small non-overlapping cells are privileged. In order to account for cell overlaps, mathematical formulations yield nonlinear combinatorial optimization problems. This gives rise to an interesting new class of covering problems which seems to open a relevant line of research from the mathematical and algorithmic point of views. Connections and analogies with other classical problems will be investigated to see whether known solution approaches can be exploited or extended. In particular, while the model with explicit covering constraints clearly generalizes the well-known set covering problems [30], models without explicit covering constraints may share some similarities with the problem of minimizing submodular functions.

Another important aspect of the problem that certainly needs to be considered is that of frequency assignment. Although frequency assignment problems have been extensively studied for second generation cellular systems such as GSM [28,29], they have usually been addressed as stand alone problems, and they have seldom been tackled jointly with the coverage planning problem. Unlike for GSM systems, it seems that when planning WLANs the covering and frequency assignment issues are strictly related, especially in a hospital environment where other electromagnetic sources are present.

Finally, the computational complexity of these models will be investigated and small-size instances will be tackled with state-of-the-art Integer Programing solvers such as CPLEX.

Time span: 6 months
Expected results:
1. Several alternative optimization models with different objectives and constraints. Study of their computational complexity.
2. Preliminary computational results on small test instances.

Phase 3

Suitable solution methods will be developed for the optimization models constructed and studied in phase 2, taking into account different objective functions and types of constraints. The structure of these problems will be thoroughly analyzed and different solution approaches will be considered. Special cases of the problems, which may be easier to solve, will be identified. For these special cases, exact solution methods based on relaxations and Branch and Bound or Branch and Cut will be devised. Whenever possible, relaxations will rely on efficient network flow algorithms. The possibility of exploiting the geometric nature of the problem will be investigated.
Since the more realistic models accounting for the many above-mentioned practical aspects of the WLAN planning problem are expected to be very challenging computationally, efficient heuristic algorithms will also be developed. This part of the work will be carried out in collaboration with the Ferrara Research unit.

Besides the data related to APs and TPs, the heuristic algorithms will also take as input the electromagnetic propagation data provided by the electromagnetic simulators developed by the Lecce Research unit.

Time span: 9 months

Expected results:
1. Thorough analysis of the models structure, including possibly easier special cases.
2. Exact and heuristic algorithms.
3. Computational experience on realistic data.

Phase 4

In this phase a special effort will be made to integrate the software prototype developed by the Milan Research unit with the software tools provided by the other units. The most appropriate model and solution method will be selected based on extensive computational experiments.
Trade-off parameters will be included so that the importance of the deployment cost, the network capacity and the electromagnetic exposition can be tuned.

The existing approaches to data security in wireless systems will be reviewed and the most adequate protocol will be identified taking into account the particular applications defined by the Ferrara and Reggio Emilia Research units.

Time span: 5 months

Expected results:

1. Integrated WLAN planning software prototype.
2. Specifications for the data security and network access.
2. Extensive computational experience on real data.

		Numero	Mesi uomo 1° anno	Mesi uomo 2° anno	Totale mesi uomo
Personale universitario dell'Università sede dell'Unità di Ricerca	4	18	19	37
Personale universitario di altre Università	1	1	1	2
Titolari di assegni di ricerca	0
Titolari di borse	Dottorato	1	6	6	12
Post-dottorato	4	14	14	28
Scuola di Specializzazione	0
Personale a contratto	Assegnisti	0
Borsisti	2	11	11	22
Dottorandi	0
Altre tipologie	0
Personale extrauniversitario	0
TOTALE		12	50	51	101

Voce di spesa	Spesa in Euro	Descrizione
Materiale inventariabile	8.500	libri e personal computer stampante schede di connessione alla rete wireless
Grandi Attrezzature
Materiale di consumo e funzionamento	3.500	spese postali e cancelleria e manutenzione computer licenze software
Spese per calcolo ed elaborazione dati
Personale a contratto	38.000	borse post dottorato
Servizi esterni	3.000	seminari e invitati stranieri
Missioni	35.000	spese di viaggio per visite e convegni
Pubblicazioni
Partecipazione / Organizzazione convegni	5.000	organizzazione di un convegno
Altro
TOTALE	93.000

Voce di spesa	Spesa in Euro	Descrizione
Materiale inventariabile	8.500	books and personal computers printer wireless connection cards
Grandi Attrezzature
Materiale di consumo e funzionamento	3.500	postal and stationery expenses computers maintenace software licenses
Spese per calcolo ed elaborazione dati
Personale a contratto	38.000	post doctoral grants
Servizi esterni	3.000	seminars and visiting researchers
Missioni	35.000	travel expenses for short visits and congresses
Pubblicazioni
Partecipazione / Organizzazione convegni	5.000	congress organization
Altro
TOTALE	93.000

		Descrizione
Costo complessivo del Programma dell'Unità di Ricerca	93.000
Fondi disponibili (RD)	4.800	FONDI DI ATENEO 2002 MAFFIOLI (271.00) FONDI PROGETTO TUTSI (RESP. FRATTA 4529.00)
Fondi acquisibili (RA)	23.100	Contrato Alcatel (Resp. Malucelli 18585.00) e fondi di Ateneo 2005 (Amaldi, Maffioli, Malucelli 1515.00)
Cofinanziamento di altre amministrazioni
Cofinanziamento richiesto al MIUR	65.100

(per la copia da depositare presso l'Ateneo e per l'assenso alla diffusione via Internet delle informazioni riguardanti i programmi finanziati e la loro elaborazione necessaria alle valutazioni; legge del 31.12.96 n° 675 sulla "Tutela dei dati personali")

MALUCELLI	FEDERICO	malucell@elet.polimi.it
MAT/09 - Ricerca operativa
Politecnico di MILANO
Facoltà di INGEGNERIA dell'INFORMAZIONE
Dipartimento di ELETTRONICA E INFORMAZIONE

MALUCELLI	FEDERICO
Professore Ordinario	07/04/1962	MLCFRC62D07D548Z
MAT/09 - Ricerca operativa
Politecnico di MILANO
Facoltà di INGEGNERIA dell'INFORMAZIONE
Dipartimento di ELETTRONICA E INFORMAZIONE
02/23993460 (Prefisso e telefono)	02/23993412 (Numero fax)	malucell@elet.polimi.it (Email)

1.	AMALDI E; CAPONE A; MALUCELLI F. (2003). Planning UMTS base station location: optimization models with power control and algorithms IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS. (vol. 2 pp. 939-952)
2.	DELL'AMICO M; MAFFIOLI F; MALUCELLI F. (2003). The base-matroid and inverse combinatorial optimization problems DISCRETE APPLIED MATHEMATICS. (vol. 128 pp. 337-353)
3.	TARRICONE L.; MALUCELLI F. (2000). Efficient linear system solution in moment methods using wavelet expansions IEEE TRANSACTIONS ON ANTENNAS AND PROPAGATION. (vol. 48(8) pp. 1257-1259)
4.	ESPOSITO A.; CATALANO M. S.; MALUCELLI F.; TARRICONE L. (1999). A new matrix bandwidth reduction algorithm OPERATIONS RESEARCH LETTERS. (vol. 23(3-5) pp. 99-107)
5.	CARRARESI P; FARINACCIO F.; MALUCELLI F. (1999). Testing optimality for quadratic 0-1 problems MATHEMATICAL PROGRAMMING. (vol. 85(2) pp. 407-421)