Raffaele CERULLI | Progetti

EURISTICHE COSTRUTTIVE E SENSORS NETWORKS

Relativamente al potenziamento degli algoritmi costruttivi per problemi di ottimizzazione combinatoria, una domanda chiave che ci si pone è la seguente: c'è una via di mezzo tra algoritmi greedy e le metaeuristiche? In altre parole, possiamo identificare una classe di euristiche che si comporta quasi come metaeuristiche rispetto alla precisione, ma richiede un tempo (ed una semplicità implementativa), che sono simili a agli approcci greedy?In questo lavoro di ricerca cercheremo di rispondere a queste domande. In particolare, progetteremo un algoritmo greedy migliorato. Il nuovo algoritmo greedy sarà più efficace nel senso che, rispetto ad un classico algoritmo greedy, esaminerà uno spazio più ampio di possibili soluzioni con un piccolo e prevedibile aumento dello sforzo computazionale.Per quanto riguarda il problema sulle reti di sensori wireless (WSN) progetteremo ed implementeremo un approccio basato sulla generazione ritardata di colonne (column generation) che tenga conto di stabilire una struttura di connessione tra i sensori attivi e la base station. In particolare svilupperemo un algoritmo genetico che avrà il compito di fornire le colonne da inserire nell'algoritmo di generazione ritardata di colonne. In questo modo, garantendo comunque di ottenere la soluzione ottima, speriamo di ridurre drasticamente i tempi di computazione necessari per la convergenza.Inoltre verrà introdotta, nell’ambito di reti wireless eterogenee, una variante del problema in cui l’obiettivo è quello di produrre cover in grado di resistere a guasti o altri inconvenienti che potrebbero portare al mancato funzionamento di uno o più sensori della rete. Se non preso in considerazione, in casi reali questo fattore può avere gravi conseguenze sulla validità della soluzione finale individuata, dal momento che il mancato funzionamento anche solo di un singolo sensore porterebbe al fallimento di tutte le cover che lo contengono. L’approccio classico a queste problematiche consiste nell’assicurare in ogni cover una copertura multipla a tutti i target (k-coverage). Una controindicazione di questo approccio è legata all’ovvio spreco di energia necessario per garantire questo livello di ridondanza in qualsiasi momento della fase di monitoraggio. Si formulerà una variante del problema in cui si vogliono individuare cover, nell’ambito di rete eterogenee, che in caso di guasto di uno qualsiasi dei propri sensori siano in grado di ristabilire la copertura aumentando il livello di copertura degli altri (o, se è necessario, modificando il tipo di copertura di qualche sensore), a discapito di una diminuzione del tempo di copertura ottenibile.