Optimale algoritmer for dynamisk frekvensbruk i DSL systemer

Abstract

Denne masteroppgaven er en fortsettelse av en prosjektoppgave gjennomført høsten 2007. Den går ut på å sette seg inn i problemet med krysstale i DSL (Digital Subscriber Lines), og da spesielt en av de beste løsningene på dette problemet, dynamisk frekvensbruk (DSM Dynamic Spectral Management). Dette kan løses på tre nivåer, med økende kompleksitet og økende datarater ved høyere implementering. Nivå 1 omfatter distribuerte systemer, der hver bruker justerer sitt eget effektspektrum for å oppnå ønskede rater. I nivå 2 er det en sentralisert kontroller som beregner spektra for flere brukere over samme kabel. Nivå 3 trenger også en kontroller, men her blir hele kanalen undersøkt for å finne kanalmatrisen. Denne kan benyttes til å fjerne og i beste fall utnytte krysstalen. I prosjektoppgaven høsten 2007 ble en av de enkleste formene for DSM sammenlignet med optimale løsninger for krysstalekoordinering (OSM Optimal Spectrum Management). OSM er den beste løsningen for DSM uten å ta i bruk krysstalekansellering. Søket for å finne den optimale løsningen ble gjort ved hjelp av Exhaustive search, som går igjennom alle mulige kombinasjoner og finner den beste. Konklusjonen var da at store forbedringer, spesielt med OSM, var mulige med innføring av DSM. Ulempen med Exhaustive search er at den blir veldig kompleks med økende antall delbånd og brukere, O(eKN). Derfor ble kun to brukere og tre delbånd benyttet. Dette klarte allikevel å vise hvilken effekt OSM har. Siden Exhaustive search var så kompleks ble det vurdert at andre algoritmer eventuelt måtte benyttes for implementering. Masteroppgaven tok derfor for seg Dual decomposition. Denne avanserte algortimen optimaliserer for hvert delbånd i stedet for på tvers av alle PSD. Fordelen med dette er at kompleksiteten blir vesentlig mindre fordi den blir lineær med hensyn på antall delbånd som blir benyttet, og ikke eksponentiell. På grunn av innføringen av Lagrangemultiplikatorer vil kompleksiteten stige noe på grunn av dette, men det er uvesentlig sammenlignet med Exhaustive search. Den eneste støyen som eksisterte i systemet var hvit støy og krysstale fra trafikk med samme retning (FEXT Far End Crosstalk). Det ble vist at beregningstidene for Dual decomposition var vesentlig mye mindre for økende bitloading og delbånd enn for Exhaustive search. Med Dual decomposition var det mulig å øke både bitloading og delbånd for å oppnå store rateregioner innen relativt kort tid. Da rateregionene ble sammenlignet var det mulig å observere at Dual decomposition ikke alltid klarte å finne absolutt alle optimale punkter. Dette vil gjerne være uvesentlig tatt i betraktning at den er såpass mye mer effektiv. Ulempen med Dual decomposition er at kompleksiteten fremdeles er eksponentiell med hensyn på antall brukere. Derfor vil også Dual decomposition bli vanskelig å innføre i de systemene som blir benyttet av mange brukere. Fremtidig arbeid vil derfor være å se på andre metoder som er mer lineære med hensyn på antall brukere.