I detta dokument studerar vi problemet med trådlös synkronisering som kräver att enheter som aktiveras vid olika tidpunkter på ett överbelastat en-hop radionätverk för att synkronisera sin runda numrering. Vi antar en samling av n synkrona enheter med tillgång till ett delat band av radiospektrum, uppdelade i F smalbandsfrekvenser. Vi antar att kommunikationsmediet lider av oförutsägbara, kanske till och med skadliga störningar, som vi modellerar av en motståndare som kan störa upp till t frekvenser per runda. Enheter börjar köra i olika omgångar och det exakta antalet deltagare är inte känt i förväg. Vi visar först en lägre gräns, vilket visar att minst " log 2 n (F − t) log n + F t F − t log n " rundor behövs för att synkronisera. Vi beskriver sedan två algoritmer. Den första algoritmen matchar nästan den nedre gränsen, vilket ger en körtid för O "logg n " rundor. Den andra algoritmen är adaptiv, som avslutas i O't log 3 n ́rounds i bra utföranden, det vill säga, när enheterna börjar köra samtidigt, och det finns aldrig mer än t frekvenser störs i någon given runda, för vissa t < t. I alla utföranden, även de som inte är bra, det slutar i O`F log 3 n påounds.
Det senaste arbetet REF fokuserar också på problemet med trådlös synkronisering som kräver att enheter aktiveras vid olika tidpunkter på ett överbelastat enhopsradionät för att synkronisera deras runda numrering medan en motståndare kan störa ett visst antal frekvenser per runda.
The wireless synchronization problem
{'venue': "PODC '09", 'journal': None, 'mag_field_of_study': ['Computer Science']}