Link schemaläggning är avgörande för att förbättra genomströmningen i trådlösa nätverk och det har studerats i stor utsträckning under olika interferens modeller. I detta dokument studerar vi problemet med länkschemaläggning enligt modellen för fysisk störning där alla avsändare av länkarna sänder med en given effekt P och en länk kan överföra framgångsrikt om och endast om signal-till-interference-plus-Noise-Ratio (SINR) vid motsvarande mottagare är minst en viss tröskel. Länken schemaläggning problem är att hitta en maximal "oberoende uppsättning" (MIS) av länkar, dvs. det maximala antalet länkar som kan överföra framgångsrikt i ett tidsparti, med tanke på en uppsättning inmatningslänkar. Detta problem har visat sig vara NP-hard [10]. Här föreslår vi den första länk schemaläggning algoritm med en konstant approximation förhållande för godtycklig bakgrundsbuller N ≥ 0. När varje länk l har en vikt w(l) > 0, föreslår vi en metod för viktad MIS med approximationsförhållande O(min(log, log max l på l min l på l )), där l är Euclideans längd av en länk l.
Xu och al. I REF föreslogs en konstant approximationsalgoritm för schemaläggning av oneslot-länkar i godtyckliga nät enligt SINR-interferensmodellen, där en överföring lyckas om det mottagna SINR-värdet är högre än ett visst tröskelvärde.
A constant approximation algorithm for link scheduling in arbitrary networks under physical interference model
{'venue': "FOWANC '09", 'journal': None, 'mag_field_of_study': ['Mathematics']}