DIKUL - logo
(UL)
  • Uporaba teorije grafov za naloge dodeljevanja frekvenc : magistrsko delo
    Šparl, Petra, 1975-2016
    Cilj magistrskega dela je pregled rezultatov pri nalogah dodeljevanja frekvenc na heksagonalnih grafih. V prvem poglavju je opisana ena glavnih nalog v omrežjih mobilne telekomunikacije in sicer ... dodeljevanje frekvenc oddajnikom, znotraj omejenega frekvenčnega spektra, pri danih interferenčnih omejitvah. Naloga je z leti postajala vedno pomembnejša in vedno težja, saj se je mobilna telekomunikacija v zadnjem času zelo hitro razvijala. Omejeno množico frekvenc je namreč potrebno dodeliti velikemu številu mobilnih uporabnikov, pri čemer poljubni dve dodeljeni frekvenci ne smeta povzročati nedovoljene interference. V praksi se veliko uporablja celični koncept, kjer velika področja razdelimo na manjša, imenovana celice. S tem se poveča izraba frekvenčnega spektra, saj lahko različnim celicam dodelimo enake množice frekvenc, če so le te dovolj medsebojno oddaljene. V drugem poglavju je predstavljena uporaba teorije grafov za naloge dodeljevanja frekvenc. Celične mreže so ponavadi predstavljene kot uteženi heksagonalni grafi, kjer točke predstavljajo območja oziroma celice, povezave predstavljajo možnosti interference med frekvencami, vektor uteži pa zahteve posamezne celice oziroma število klicev, ki morajo biti oskrbljeni v celici, ki jo dana točka predstavlja. Naloga dodeljevanja frekvenc v jeziku teorije grafov je ustrezno pobarvati utežen heksagonalen graf, pri čemer je potrebno upoštevati interferenčne omejitve, ki povedo katerim točkam grafa ne smemo dodeliti enakih barv. Interferenčne omejitve predstavimo z zaporedjem naravnih števil ▫$c_0\geq, \ge c_1\geq, \ge c_2\geq, \ge c_3...,$▫ kjer ▫$c_1$▫ pomeni minimalno razliko med frekvencama dodeljenima klicema iz celic, ki sta na radalji i v mreži. Če barve, ki jih imamo na razpolago za omenjeno večbarvanje označimo z zaporednimi naravnimi števili, potem omejitev ▫$c_i$▫ pomeni, da se morajo barve dodeljene točkama na razdalji i razlikovati najmanj za ▫$c_i$▫. Na začetku tretjega poglavja je podan optimalen algoritem za večbarvanje ciklov. V nadaljevanju so podrobno analizirani in primerjani trije konstruktivni dokazi zgornjih mej za uteženo kromatično število heksagonalnih grafov v odvisnosti od uteženega kličnega števila [26, 18, 20]. Izkazalo se je, da prva dva dokaza podajata enaki zgornji meji za kromatično število poljubnega heksagonalnega grafa G in sicer ▫$X_w(G)\le \lfloor\frac{4\omega_w(G)+1}{3}\rfloor$▫.Prvi dokaz ima eno pomembno lastnost, ki je drugi dokaz nima. Algoritem dobljen na osnovi prvega dokaza je namreč porazdeljen, medtem ko algoritem, ki ga dobimo s pomočjo drugega dokaza, ni. Porazdeljena izvedba prvega algoritma je podana na koncu tretjega poglavja. Za tretji dokaz se je izkazalo, da ima napako, kar je pokazano v razdelku 3.2.2, kjer je podan tudi ustrezen protiprimer. V četrtem poglavju je obravnavano večbarvanje heksagonalnih grafov brez trikotnikov. Najprej je predstavljen algoritem za 5-[2]-barvanje heksagonalnih grafov brez trikotnikov, s pomočjo katerega je v nadaljevanju podan dokaz zgornje meje za uteženo kromatično število heksagonalnih grafov brez trikotnikov v odvisnosti od uteženega kličnega števila [10]: ▫$X_w(G)\le \lceil\frac{5\omega_w(G)}{4}\rceil+3$▫. V drugem delu četrtega poglavja je predstavljen algoritem za 7-[3]-barvanje heksagonalnih grafov brez trikotnikov. Omenjeni algoritem je imel v originalu [8] napako, ki je v delu popravljena. V petem poglavju so obravnavana večbarvanja heksagonalnih grafov z omejitvami. Na začetku je predstavljeno večbarvanje z omejitvami ▫$c_o\g 1$▫, ▫$c_1=1$▫ in ▫$c_i=0$▫ za ▫$ i\geq, \ge 2 [27]$▫ v nadaljevanju pa večbarvanje z omejitvami ▫$c_o=c_1=c_2$▫ in ▫$c_i=0$▫, za ▫$i\geq, \ge 3[4]$▫. V obeh primerih so podani dokazi za zgornje meje kromatičnega števila v odvisnosti od kličnega števila. V šestem in sedmem poglavju so opisani sorodni rezultati oziroma odprti problemi iz področja dodeljevanja frekvenc
    Type of material - master's thesis ; adult, serious
    Publication and manufacture - Maribor : [P. Šparl], 2001
    Language - slovenian
    COBISS.SI-ID - 10787336

Library Call number – location, accession no. ... Copy status
National and University Library, Ljubljana GS II 524997 glavno skladišče available - reading room
loading ...
loading ...
loading ...

Shelf entry