I detta dokument presenterar vi AFR, en ny geometrisk mobil adhoc routingalgoritm. Algoritmen är helt distribuerad; noder behöver bara kommunicera med direkta grannar i sitt sändningsområde. Vi visar att om en bästa rutt har kostat c, AFR hittar en rutt och slutar med kostnad O(c 2 ) i värsta fall. AFR är den första algoritmen med kostnader som begränsas av en funktion av den optimala rutten. Vi ger också en tight lägre gräns genom att visa att någon geometrisk routing algoritm har värsta-fall kostnad. (c 2 ). På så sätt är AFR asymptotiskt optimalt. Vi ger en icke-geometrisk algoritm som också matchar den nedre gränsen, men behöver lite minne vid varje nod. Detta etablerar en spännande avvägning mellan geometri och minne.
Den första algoritmen som ger värsta tänkbara garantier är Kuhn et al. Hoppa över det.
Asymptotically optimal geometric mobile ad-hoc routing
{'venue': "DIALM '02", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}