Ricerca | Progetti Finanziati

RETI DI SENSORI ETEROGENEE E SOTTOSTRUTTURE ETEROGENEE DI UN GRAFO.

Nel progetto di ricerca, relativamente al primo problema, intendiamo studiare alcune importanti varianti per il problema della massimizzazione del tempo di durata di una rete wireless in scenari di tipo eterogenei, di notevole interesse sia applicativo che teorico. Problematiche di questo tipo sono state finora scarsamente trattate dalla letteratura.Nello specifico, intendiamo considerare il caso in cui siano presenti sensori di tipologia differente, in grado di rilevare diverse metriche della area in oggetto. Questo fattore e' di rilevanza pratica in molti scenari reali. Ad esempio, nel caso di rilevazioni ambientali la WSN può essere composta da sensori per la rilevazione della temperatura, dell'umidità, di particolari tipi di gas, delle intrusioni e di molti altri fattori. Intendiamo studiare il problema di attivare combinazioni di sensori corrispondenti alle varie tipologie presenti nella rete, in grado di assicurare sia la copertura totale del territorio di interesse il più a lungo possibile, sia di garantire livelli di copertura minimi che possono essere richiesti per ciascuna delle diverse tipologie.Considereremo sia il caso in cui tutti i sensori abbiano aree di rilevamento di forma simile, sia il caso in cui siano presenti sensori circolari e angolari. Inoltre, modelleremo l'esistenza di dispositivi hardware contenenti vari sensori di tipo diverso, connessi ad una unica batteria. Tali dispositivi sono normalmente presenti in commercio e adoperati in molte applicazioni reali, e possono attivare i propri sensori indipendentemente o insieme, presentando quindi anche in questo caso varie possibili configurazioni.Per tutte le varianti proposte presenteremo approcci di tipo esatto basati su metodi a generazione di colonne, comprensivi di euristiche (in particolare metaeuristiche di tipo genetico) per l'inizializzazione del metodo stesso e per una risoluzione più efficiente del sottoproblema.Per il secondo problema proporremo approcci esatti ed euristici (greedy) per la sua soluzione.La maggior parte dei lavori in letteratura per il raimbow tree (albero ricoprente eterocromatico) si è concentrata sull'individuazione di upper bound quanto più vicini possibili alla soluzione ottima. La qualità dei bound spesso dipende anche dalla tipologia di grafo utilizzato; infatti in alcune tipologie di grafi tali strutture possono fornire delle informazioni in grado di rendere più "stringenti" tali bound. Non sono stati tuttavia proposti ne algoritmi esatti, per l'individuazione della soluzione ottima su piccole dimensioni, ne euristiche, in grado di calcolare velocemente buone soluzioni anche per istanze di grandi dimensioni. Nel progetto di ricerca intendiamo colmare tali mancanze proponendo una modello matematico ed un approccio greedy (euristico). Il modello matematico sarà reso più performante attraverso l'introduzione di "tagli a priori" basati sulle caratteristiche del problema e dell'istanza ricevuta in input. Un altro contributo riguarderà la progettazione ed implementazione di un algoritmo greedy multistart che sia in grado di calcolare velocemente buone soluzioni su qualsiasi tipologia di grafi. L'efficacia di questo algoritmo verrà certificata confrontando le soluzioni prodotte con la soluzione ottima fornita dal modello matematico sulle piccole istanze. Sulle grandi dimensioni invece si farà riferimento al gap tra la soluzione dell'algoritmo greedy ed i lower bound conosciuti.