20.500.12556/DKUM-62964 Optimalna dodelitev frekvenčnih kanalov v brezžičnih omrežjih Optimal channel assignment in wireless networks Magistrsko delo obravnava problem dodeljevanja frekvenčnih kanalov v brezžičnih omrežjih. Na začetku je predstavljen izvor problema in njegovo teoretično ozadje. Sledi opis osnovnih pojmov iz teorije grafov, ki so potrebni za nadaljnje razumevanje tega dela. Problem je predstavljen z matematičnim modelom iz teorije grafov, ki je soroden problemom barvanja vozlišč grafa. Opisane so metode za reševanje problemov barvanja vozlišč grafa: linearno programiranje in njegova posplošitev semidefinitno programiranje ter nadalje kombinatorični algoritmi, aproksimacijski algoritmi in hevristični algoritmi. Opisan je alternativni pristop k problemu dodeljevanja frekvenčnih kanalov s področja teorije iger. Teorija iger obravnava modele, kjer igralci med seboj sodelujejo za dosego skupnega cilja, ali pa med seboj tekmujejo za dosego lastnega cilja. Zadnja poglavja so namenjena empiričnemu delu raziskovanja problema. Najprej je opisan matematični model dodeljevanja frekvenčnih kanalov iz teorije telekomunikacij. Sledita mu dve družini optimizacijskih primerov na podlagi konkretnih podatkov. Empirični del zaključujejo rezultati optimizacije ter njihova analiza. V vseh optimizacijskih primerih je bila dosežena izboljšava v učinkovitosti brezžičnega omrežja. The thesis considers the problem of channel assignment in wireless networks. In the begining it presents origin of the problem and its theoretical background. It follows introducing the basic concepts that are necessary for further understanding of this thesis. The problem is represented by the mathematical model from graph theory, which is akin to the vertex coloring problems. Described are methods for solving vertex coloring problems: linear programming and its generalization semmidefinite programming, and further combinatorial algorithms, approximation algorithms and heuristic algorithms. It is described an alternative approach to the channel assignment problem from game theory. Game theory considers models where players cooperate with each other to achieve a common goal, or compete with each other to achieve their own objectives. Subsequent chapters are intended to empirical research of the problem. The first describes a mathematical model for channel assignment problem from telecommunication theory. Followed by two families of optimization cases based on the use of realistic data. After that, the results and their analysis are presented. In all of the optimization cases was achieved improvement in efficiency of wireless network. dodeljevanje frekvenčnih kanalov teorija grafov operacijske raziskave matematično programiranje teorija iger. frequency channel assignment graph theory operation research mathematical programming generalized graph colorings game theory. true true false [J. Dolšak] Slovenski jezik Angleški jezik Magistrsko delo/naloga 2016-09-04 13:22:36 2016-09-16 16:39:44 2022-06-30 03:08:34 2019-07-11 13:12:17 2016 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.85(043.2) 22530312 URN:SI:UM:DK:TXG0RDRB MAG_Dolsak_Janez_2016.pdf MAG_Dolsak_Janez_2016.pdf 1 FEF423DE9C89A7E5023F94BBF6E2E56F 0d6e030a246dd5fcfb90f0d971c78edfd45e73f44b07b28649a1a9b80235873c c6be321d-7c0d-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=107504 Fakulteta za naravoslovje in matematiko 0 0 0