Algoritmi di pathfinding cooperativo per reti wireless ad hoc

Negli ultimi anni le problematiche di progettazione ed implementazione di reti wireless ad hoc hanno acquistato crescente attenzione nel campo delle telecomunicazioni. Una rete ad hoc è una rete wireless decentralizzata che non si appoggia su strutture preesistenti come router o access point, ma è gestita con la partecipazione dei dispositivi di cui è composta. Per sua natura una rete ad hoc deve garantire la cooperazione e la collaborazione dei nodi ed è progettata con approccio multiutente. In particolare i vari dispositivi saranno tenuti ad unire le proprie forze per instradare i pacchetti di dati che devono essere scambiati da un nodo all’altro della rete. In questa tesina ci concentreremo sulle problematiche che riguardano il pathfinding cooperativo, cioè quella fase preliminare o parallela alla trasmissione in cui si cercano dei percorsi ammissibili per tutti i pacchetti che simultaneamente viaggiano nella rete ad hoc. Per prima cosa si cercherà un modello per la rete e il problema verrà ricondotto alla teoria dei grafi, successivamente sarà introdotto l’algoritmo A*, utile per cercare cammini di costo minimo. In seguito analizzeremo alcuni lavori nati nell’ambito dell’Intelligenza Artificiale e si cercherà di capire in che modo si possano adattare a problematiche di pathfinding nelle reti ad hoc. Particolare rilievo sarà riservato all’overhead di ogni soluzione proposta e alle complicazioni provocate dall’interferenza dei dispositivi. I metodi studiati vengono raggruppati in base alla quantità di informazione condivisa tra i dispositivi: distingueremo tra approcci centralizzati in cui il pathfinding viene gestito globalmente con un’azione unitaria di tutti i nodi, e soluzioni distribuite che si prefiggono di raggiungere la cooperazione tra i nodi senza appesantire ulteriormente l’overhead