Localizzazione di utenti in reti cellulari.

L'obiettivo delle reti senza fili è quello di fornire ad un largo numero di utenti, per lo più mobili, connessioni ad alta banda, connessioni sempre e ovunque (senza limitazioni strutturali), e connessioni arricchite da informazioni legate al contesto (ossia legate al profilo dell'utente, o alla zona geografica da cui si connette, etc.). Il modello di architettura senza fili più diffuso fino a oggi prevede un livello di infrastruttura fissa, le cossiddette stazioni di base connesse tra loro da una rete a larga banda e distribuite su una vasta area geografica, a cui si connettono tanti e diversi dispositivi (telefonini, palmari, laptop, dispositivi per il rilevamento della posizione, dispositivi ad infrarossi, etc.) Un importante problema da affrontare è il disegno e l'analisi delle strategie di tracking, o localizzazione, degli utenti mobili. Le strategie più comuni sono Always-Update and Never-Update. La prima informa la stazione di base ogni volta che l'utente mobile si muove ed ha ovviamente alti costi di gestione, ma localizza velocemente l'utente mobile al tempo della chiamata. La seconda strategia paga l'assenza totale di rendez-vous fra l'utente e la stazione di base con un alto costo per localizzare l'utente mobile. Recentemente è stato proposta una nuova strategia di notifica Reporting Center Strategy. Il problema dei reporting centers è quindi definito come il problema di localizzare i reporting centers sulla rete cellulare in modo che il loro numero sia minimo e che il numero massimo di comunicazioni necessarie per rintracciare l'utente mobile sia limitato superiormente da una costante $Z$. In [A6], il reporting center problem, che in generale è NP-hard, è risolto ottimamente con tecniche greedy e con tecniche di programmazione dinamica quando: (1) la rete cellulare è modellata da grafi di intervalli e $Z$ è fissato a $2$, (2) la rete cellulare è modellata da grafi propri di intervalli e $Z$ assume un qualsiasi valore intero.