Algoritmi per la localizzazione.

Le reti di sensori considerate sono costituite da una stazione base ed un insieme di sensori wireless distribuiti casualmente e densamente in uno spazio piano. I sensori sono sprovvisti di GPS, sono anonimi, e non sono manutenibili. Hanno energia limitata non rinnovabile e possono transire fra stato attivo (sveglia) e passivo (sonno). Essi possono comunicare fra loro solo entro un raggio limitato. La stazione base ha energia illimitata, è provvista di un'antenna isotropica il cui raggio massimo di trasmissione delimita l'area controllata dalla stazione stessa. La stazione base può variare il raggio di trasmissione e raggiungere in un solo hop tutti i sensori attivi la cui distanza dalla stazione base sia minore o uguale al raggio della trasmissione corrente. In questo modello, un sensore si dice localizzato quando conosce la propria posizione nel piano rispetto ad un sistema di coordinate polari, con origine nella stazione base, che divide l'area controllata in settori equiangolari e corone concentriche. In [A1, C3] si forniscono due protocolli sincroni per l'apprendimento della corona concentrica a cui appartiene il sensore. I protocolli proposti consistono di una fase centralizzata, gestita completamente dalla stazione base, seguita da una fase distribuita. Le computazioni di entrambi i protocolli possono essere viste come particolari visite di alberi. Nel primo protocollo si tratta di un albero binario, nel secondo di un albero $q$-ario. Le prestazioni dei protocolli sono misurate in termini del tempo complessivo richiesto per completare per tutti i sensori l'apprendimento della posizione e in termini dell'energia spesa da ciascun sensore durante l'apprendimento. Entrambi i protocolli migliorano le prestazioni di un algoritmo per la localizzazione nello stesso modello, precedentemente presentato in letteratura. In particolare, il secondo protocollo può richiedere un numero costante (e quindi ottimo) di transizioni fra lo stato attivo e passivo del sensore, senza peggiorare il tempo totale necessario affinchè tutti i sensori apprendano la loro posizione. In [C1, C2], si propongono, per lo stesso modello di reti di sensori, protocolli asincroni per la localizzazione. Tali protocolli sono asincroni nel senso che ciascun sensore diventa attivo `at random' e per tutta la durata del protocollo alterna periodi di sveglia a periodi di sonno di prefissata lunghezza, senza nessuna esplicita sincronizzazione con la stazione base. Durante l'algoritmo di apprendimento, la stazione base ciclicamente trasmette con raggio di trasmissione decrescente, iniziando il ciclo con il raggio della corona più esterna e terminando con quello della corona più interna. Precisamente, ad ogni trasmissione, la stazione trasmette l'identificatore della corona concentrica il cui raggio coincide con il raggio della trasmissione corrente. Il processo è ripetuto fino a che tutti i sensori non abbiano appreso. Le prestazioni in tempo ed energia dei protocolli asincroni sono state valutate sia analiticamente che sperimentalmente. Dato il comportamento ciclico sia dei sensori che della stazione base, i risultati analitici della complessità nel caso pessimo sono ottenuti sfruttando proprietà dell'aritmetica modulare. Infine, è studiata la complessità nel caso medio dei protocolli. Tale analisi è inclusa nella versione completa dei risultati sui protocolli asincroni per reti di sensori correntemente sottomessa a rivista [T3].