Abstrakt. Orthogonal Variabel Spridningsfaktor (OVSF) koder används i UMTS för att dela radiospektrumet bland flera anslutningar av möjligen olika bandbreddskrav. Den kombinatoriska kärnan i OVSF-kodtilldelningsproblem är att tilldela några noder av ett komplett binärt träd av höjd h (koden träd) till n samtidiga anslutningar, så att inga två tilldelade noder (koder) är på samma rot-till-blad sökväg. En anslutning som använder en 2 – d-fraktion av den totala bandbredden kräver någon kod på djup d i trädet, men denna kodtilldelning tillåts ändras över tid. Begäran om anslutningar som skulle överskrida den totala tillgängliga bandbredden avslås. Vi överväger problemet med enstegskodtilldelning: Med ett uppdrag, flytta det minsta antalet koder för att tjäna en ny begäran. Minn och Siu föreslår den så kallade DCA-algoritmen för att lösa problemet optimalt. Däremot visar vi att DCA inte alltid returnerar en optimal lösning och att problemet är NP-hård. Vi ger en exakt n O(h) -tid algoritm, och en polynom-tid girig algoritm som uppnår approximation förhållande (h). En mer praktiskt relevant version är problemet med online-kodtilldelning, där framtida förfrågningar inte är kända i förväg. Vårt mål är att minimera det totala antalet omplacerade koder. Vi presenterar en (h)-konkurrenskraftig online-algoritm, och visar att ingen deterministisk online-algoritm kan uppnå ett konkurrensförhållande bättre än 1.5. Vi visar att den giriga strategin (att minimera antalet omplaceringar i varje steg) inte är bättre än (h) konkurrenskraftig. Vi ger en 2-resursförstärkt online-algoritm som uppnår ett amorterat konstant antal (åter)uppdrag. Slutligen visar vi att problemet är en fast parameter som går att styra.
I REF tar författarna upp problemet med OVSF-kodtilldelning.
An Algorithmic View on OVSF Code Assignment
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Computer Science', 'Mathematics']}