Abstract — Ad hoc-nätverk är självorganiserande enheter som är utplacerade på begäran till stöd för olika evenemang, inklusive datasamverkan, multimediaklassrum, katastroflösning, sök-och-räddning, interaktiv uppdragsplanering och brottsbekämpning. En av de grundläggande uppgifter som måste tas upp när man inrättar ett ad hoc-nätverk (AHN, kort sagt) är initiering. Detta innebär att tilldela var och en av n-stationerna i AHN ett tydligt ID-nummer (t.ex. en lokal IP-adress) i intervallet från I till n. Vårt huvudsakliga bidrag är att föreslå effektiva randomiserade initialiseringsprotokoll för AHN. Vi börjar med att visa att om antalet n stationer är känt i förväg, en n-station, enkanal AHN kan initieras med sannolikhet överstiger I À I n, i en y n log n p tider, oavsett om AHN har kollisionsdetektering förmåga. Vi fortsätter sedan att visa att även om n inte är känd i förväg, en n-station, enkanal AHN med kollisionsdetektering kan initieras med sannolikhet överstiger I À I n, i IHn Q y n n n p tider. Med detta protokoll som en språngbräda presenterar vi sedan ett initieringsprotokoll för n-stationen, kchannel AHN med kollisionsdetektering som slutar med sannolikhet överstigande I À I n, i IHn Qk y n n k q time slots. Slutligen tittar vi på det fall där det inte finns någon förmåga att upptäcka kollisioner. Vårt första resultat i denna riktning är att visa att uppgiften att välja en ledare i en n-station, enkanal AHN kan slutföras med sannolikhet överstiger I À I n, i färre än IIXQUlog n P PXQW log n time slots. Detta ledarval protokoll tillåter oss att utforma en initiering protokoll för n-station, enkanal AHN utan kollision upptäckt som slutar med sannolikhet överstiger I À I n, i färre än SXTUn y n n n p tider, även om n inte är känd i förväg. Vi diskuterar sedan ett initieringsprotokoll för n-station, k-kanal AHN utan kollisionsdetektering som avslutas med sannolikhet överstiger I À I n, i färre än SXTU n k y n inn k q time slots, när k n log n Q.
En liknande mekanism används i REF, med skillnaden att sannolikheten är beroende av antalet stationer i nätverket och undersökningsmeddelandet skickas oavsett kanaltillstånd.
Randomized Initialization Protocols for Ad Hoc Networks
{'venue': 'IEEE Transactions on Parallel and Distributed Systems', 'journal': None, 'mag_field_of_study': ['Computer Science']}