Vi presenterar nya övre gränser för grundläggande problem i flerkanaliga trådlösa nätverk. Dessa gränser tar upp fördelarna med dynamisk spektrumtillgång, dvs. i vilken utsträckning flera kommunikationskanaler kan användas för att förbättra prestandan. Mer detaljerat studerar vi en flerkanalig generalisering av den vanliga grafbaserade trådlösa modellen utan kollisionsdetektering, och antar att nätverkstopologin uppfyller polynomiskt avgränsat oberoende. Vårt kärntekniska resultat är en algoritm som konstruerar en maximal oberoende uppsättning (MIS) i O ( log 2 n F ) + Õ(log n) rundor, i nätverk av storlek n med F-kanaler, där thin O-notation döljer polynomiska faktorer i log log n. Dessutom använder vi denna MIS algoritm som en subrutin för att bygga en konstant-gradig ansluten dominerande set i samma asymptotic tid. Med hjälp av denna struktur kan vi lösa globala utsändningar och ledarval inom +Õ(log n) rundor, där D är diametern på grafen, och k-meddelande multi-meddelande utsändning i +Õ(log n) rundor för obegränsad meddelandestorlek (med en långsam av bara en loggfaktor på k-termen under antagandet av begränsad meddelandestorlek). I samtliga fem fall ovan bevisar vi: a) våra resultat håller med hög sannolikhet (dvs. minst 1 − 1/n); b) våra resultat ligger inom polylog-faktorerna för de relevanta lägre gränserna för flerkanalsnätverk; och c) våra resultat slår de relevanta lägre gränserna för enkanalsnätverk. Dessa nya (nära) optimala algoritmer utökar avsevärt antalet problem som nu är kända för att kunna lösas snabbare i flerkanaliga jämfört med trådlösa enkanalsnätverk.
Dessutom, i ett mycket färskt dokument REF, Daum et al. gav ett slumpmässigt protokoll med tids komplexitet O(k log n + log 2 n F + log n log log n) när det finns F tillgängliga kanaler.
Maximal independent sets in multichannel radio networks
{'venue': "PODC '13", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}