Grannarnas upptäckt är ett av de första stegen i initieringen av ett trådlöst ad hoc-nätverk. I den här artikeln designar och analyserar vi praktiska algoritmer för nästa upptäckt i trådlösa nätverk. Vi överväger först en ALOHA-liknande granne upptäckt algoritm i ett synkront system, föreslås i ett tidigare arbete. När noder inte har en kollision upptäckt mekanism, visar vi att denna algoritm minskar till den klassiska Coupon Collector problem. Följaktligen visar vi att varje nod upptäcker alla sina n grannar i en förväntad tid lika med ne (ln n+c), för vissa konstant c. När noder har en kollision detektionsmekanism, föreslår vi en algoritm baserad på mottagarens status feedback som ger en ln n förbättring över den ALOHA-liknande algoritmen. Våra algoritmer kräver inte noder för att ha någon uppskattning av antalet grannar. I synnerhet visar vi att inte veta n resulterar i mer än en faktor av två avmattning i algoritmens prestanda. I avsaknad av nodsynkronisering, utvecklar vi asynkrona granne upptäckt algoritmer som bara är en faktor av två långsammare än deras synkrona motsvarigheter. Vi visar att våra algoritmer kan uppnå granne upptäckt trots att tillåta noder att börja utförande vid olika tidpunkter. Dessutom låter våra algoritmer varje nod upptäcka när man ska avsluta grannens upptäcktsfas.
Vasudevan m.fl. omfattande analyserade ALOHA-liknande granne upptäckt algoritmer och föreslog en kollision upptäckt mekanism för att förbättra prestanda i REF.
Neighbor discovery in wireless networks and the coupon collector's problem
{'venue': "MobiCom '09", 'journal': None, 'mag_field_of_study': ['Computer Science']}