Effektiv kommunikation i trådlösa nätverk utmanas vanligtvis av möjligheten till störningar mellan flera sändande noder. Mycket viktig forskning har investerats i att minska antalet kollisioner för att få snabbare algoritmer för kommunikation i sådana nätverk. I detta dokument föreslås ett nytt tillvägagångssätt för trådlös kommunikation, som omfattar kollisioner snarare än att undvika dem, över en additiv kanal. Det introducerar en kodningsteknik som kallas Bounded-Contention Coding (BCC) som gör det möjligt att framgångsrikt avkoda kollisioner av de mottagande noderna i de ursprungliga sändningarna och vars komplexitet beror på en bunden på tvisten mellan sändare. BCC möjliggör deterministisk lokal sändning i ett nätverk med n noder och som mest en sändare med information om l bitar varje inom O(a log n + al) bitar av kommunikation med full-duplex radio, och O((a log n + al) (log n)) bitar, med hög sannolikhet, med halv-duplex radio. I kombination med slumpmässig linjär nätverkskodning ger BCC global sändning inom O((D + a + log n)(a log n + l)) bitar, med hög sannolikhet. Detta gäller även dynamiska nätverk som med tiden kan förändras godtyckligt av en motståndare i värsta fall. När det inte finns någon koppling till tvisten, visas det hur man på ett probabilistiskt sätt kan uppskatta den och få en global sändning som är anpassad till det verkliga innehållet i nätverket.
REF:s arbete förutsätter ett begränsat a på innehållet i systemet, dvs. det finns högst en initial insats totalt i nätverket.
Bounded-Contention Coding for Wireless Networks in the High SNR Regime
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}