Abstrakt. Informationsutbyte är en grundläggande kommunikation primitiv i radionät. Vi studerar detta problem i flerkanaliga singlehop-nätverk. I synnerhet, med tanke på k bitar av information, ursprungligen lagrad i k noder respektive, uppgiften är att sända dessa informationsbitar till hela nätverket via en uppsättning F- kanaler. Vi utvecklar effektiva distribuerade algoritmer för denna uppgift för scenariot där både identiteter och antal k av de ursprungliga informationsinnehavarna är okända för de deltagande noderna. Om vi antar noder med kollisionsdetektering, presenterar vi en effektiv randomiserad algoritm för obegränsat informationsutbyte, där flera informationsobjekt kan kombineras till ett enda meddelande. Algoritmen sprider alla informationsobjekt inom O( k F + F log 2 n) gånger med hög sannolikhet. Såvitt vi vet är detta den första algoritmen som bryter ned den nedre gränsen för obegränsat informationsutbyte om endast en kanal är tillgänglig. Detta resultat etablerar flera kanalers överlägsenhet när det gäller uppgiften om obegränsat informationsutbyte. Dessutom, för begränsat informationsutbyte, där varje meddelande kan bära endast ett informationsobjekt, vi utformar en randomiserad algoritm som slutför uppgiften i O(k + log 2 n F + log n) timeslots. När k är stor, är båda algoritmerna asymptotiskt optimala, eftersom de kan nå de triviala nedre gränserna för  på ( k F ) och (k) för obegränsat och begränsat informationsutbyte, respektive.
Sedan med kollisionsdetektering, Wang et al. REF föreslog ett protokoll som med stor sannolikhet sprider alla paket i O(k/F + F · log 2 n).
Information exchange with collision detection on multiple channels
{'venue': None, 'journal': 'Journal of Combinatorial Optimization', 'mag_field_of_study': ['Mathematics', 'Computer Science']}