SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Search the digital library catalog Help

Query: search in
search in
search in
search in
* old and bologna study programme

Options:
  Reset


1 - 10 / 178
First pagePrevious page12345678910Next pageLast page
1.
2.
3.
4.
5.
Prometno uravnoteženi usmerjevalni algoritmi za brezžična senzorska omrežja : doktorska disertacija
Karl Benkič, 2010, dissertation

Abstract: Brez i ne komunikacije, kot na primer GSM tehnologija, WiFi vstopne točke, digitalna televizija in drugo postajajo v naših ž ivljenjih vedno bolj prisotna. Cenovna dostopnost komponent in nagel industrijski razvoj je vzpodbudil uporabo brezžičnih komunikacij tudi v osebne namene (kot primer podajmo samo GSM telefon in BlueTooth slušalko). Ljudje smo vedno bolj vpeti v svet komunikacij pa se često tega niti ne zavedamo. Vedno manjše, cenejše in zmogljivejše komponente so pripomogle k uporabi brezžičnih komunikacij v prej nepredstavljivih aplikacijah. Eno izmed takšnih aplikacij predstavljajo tudi brezžična senzorska omrežja (BSO). Brezžična senzorska omrežja so omrežja, sestavljena iz majhnih, baterijsko napajanih, pametnih senzorjev sposobnih brezžične komunikacije. Njihova radijska vidljivost je ponavadi majhna, cena pa tako nizka, da senzorske enote po uporabi preprosto zavržemo. Namenjena so spremljanju različnih fenomenov (sezmiologija, spremljanje habitata, spremljanje požarov, vojaške aplikacije... ). Med intenzivnejše raziskave brežičnih senzorskih omrežij že od vsega začetka spadajo raziskave usmerjevalnih algoritmov. Standardni usmerjevalni algoritmi uporabljeni v standardih IEEE 802.11x zaradi posebnosti BSO niso uporabni ali pa je njihova uporaba v BSO nesmiselna (zaradi velike potrošnje procesorskih ali spominskih virov ter energije). Posledično so raziskave usmerjene v za brezžična senzorska omrežja posebej prilagojene protokole usmerjanja prometa. V tezi smo se omejili na raziskave prometno uravnote enih algoritmov, ki sporočila pošiljajo po najkrajši možni poti (minimalno število etap). Raziskovali smo usmerjanje v statičnih BSO, kjer senzorji s časom ne spreminjajo svoje lege ali pa jo spreminjajo v intenziteti, ki ni bistvena za delovanje algoritmov. Predlagan usmerjevalni protokol je sestavljen iz dveh algoritmov: BFS algoritma in optimalnega polprirejanja. Algoritem za izra un minimalnega števila potrebnih etap, da je sporočilo poslano od vozlišča do bazne postaje je v bistvu dodelan BFS algoritem. Z BFS algoritmom izračunamo nivo vsakega vozlišča (nivo predstavlja oddaljenost od bazne postaje v etapah) v omrežju. Vozlišča iz dveh sosednjih nivojev za potrebe algoritma iskanja optimalnega polprirejanja predstavimo kot virtualni dvodelni graf. Teh virtualnih grafov je za ena manj kot število nivojev vozlišč (n -1). Na vsak kem virtualnem dvodelnem grafu posebej izračunamo optimalno polprirejanje. Cilj optimalnega polprirejanja je uravnotežitev prometa med vozlišči. Skupen rezultat obeh algoritmov je topologija imenovana topologija prirejanja. Topologija prirejanja je v bistvu vpeto drevo, ki ga uporablja protokol usmerjanja. Kvaliteto uravnotežitve na vseh nivojih vpetega drevesa ocenimo po metriki faktorja uravnotežitve (Chebyshevo sumo). V delu predlagamo tudi nov, hitrejši algoritem za izračun optimalnega polprirejanja. Eksperimenti so pokazali, da je izvajanje algoritma vsaj 15 % hitrejše kot pri ostalih, do sedaj znanih algoritmih. Za testiranje in simuliranje usmerjevalnega protokola smo uporabili standardni MAC protokol (IEEE 802.15.4), temelje na CSMA-CA izmikanju kolizij, kateremu smo dodali e RTS/CTS kontrolne okvirje. Za potrditev teze smo uporabili simulacijsko okolje OPNET kjer smo razvili model prototipa brezžičnega senzorskega vozlišča SPaRCMosquito razvitega v laboratoriju. Rezultati simulacij so potrdili, da protokol zaradi svojega načina delovanja pripomore k manj i porabi energije celotnega senzorskega omre ja in kraj im latentnim časom sporočil poslanih od senzorskih vozlišč do bazne postaje. Predlagan usmerjevalni algoritem
Keywords: brezžična senzorska omrežja, protokoli usmerjanja, teorija grafov, uravnoteževanje obremenitev
Published: 12.10.2010; Views: 2302; Downloads: 202
.pdf Full text (8,60 MB)

6.
HAMILTONSKE PRIZME
Žan Močivnik, 2012, undergraduate thesis

Abstract: obstoja hamiltonske prizme v grafu leži med problemoma obstoja Hamiltonove poti in obstoja 2-sprehoda v grafu, kar v diplomskem delu podrobneje osvetlimo. Pri dokazovanju obstoja hamiltonskih prizem nad grafi si pomagamo s posebnim barvanjem povezav grafa. V prvem poglavju so opisane osnovne definicije in rezultati, povezani z grafi, prizmami in hamiltonskostjo. V drugem poglavju podrobneje obravnavamo prizme nad dvodelnimi grafi, kubičnimi grafi, posplošenimi Halinovimi grafi in grafi povezav ter predstavimo nekatere rezultate, ki se nanašajo na iskanje njihovih Hamiltonovih prizem.
Keywords: Teorija grafov, prizma, kartezični produkt, Hamiltonov cikel, Hamiltonov graf, Hamiltonova prizma, k-sprehod, k-drevo, k-faktor.
Published: 27.02.2012; Views: 2038; Downloads: 170
.pdf Full text (2,17 MB)

7.
PALIČNO ŠTEVILO GRAFA
Barbara Mikelj, 2011, undergraduate thesis

Abstract: Diplomsko nalogo tvori šest poglavij. Po uvodu sledi poglavje z osnovnimi pojmi teorije grafov, ki so uporabljeni v diplomski nalogi. V drugem poglavju so predstavljene osnovne lastnosti igre s palicami ter definirani pojmi palično število, optimalno palično število, palična poteza, dvopalična poteza, odstranitvena poteza, razporeditev na grafu, dobra (multi) razporeditev na grafu, cilj poteze in izid razporeditve. V tretjem poglavju sta podana palično in optimalno palično število poti, ciklov in spojev grafov. Prikazani so tudi primeri razporeditve za nekatere poti in cikle manjšega reda. V četrtem poglavju sta podani palično in optimalno palično število kartezičnega produkta polnih grafov ter določeni spodnja in zgornja meja paličnega števila kartezičnega produkta $G \square K_n$, ki temelji na dvopaličnem številu. V petem poglavju je določeno palično število hiperkock. Poleg tega sta določeni še spodnja in zgornja meja za optimalno palično število hiperkock. V šestem poglavju pa so določene spodnje in zgornje meje za palično in optimalno palično število grafov z majhnim premerom.
Keywords: teorija grafov, igre na grafih, igra s palicami, palično število grafa
Published: 09.11.2011; Views: 1116; Downloads: 43
.pdf Full text (457,36 KB)

8.
9.
RETRAKTI KREPKIH GRAFOVSKIH SVEŽNJEV
Maša Dukarić, 2012, undergraduate thesis

Abstract: V diplomskem delu so obravnavani retrakti krepkih grafovskih produktov ter krepkih grafovskih svežnjev, ki so osrednja tema tega diplomskega dela. Obravnavan je tudi pojem kanonične retrakcije, tako krepkih grafovskih produktov kot tudi krepkih grafovskih svežnjev. Uvodno poglavje je namenjeno spoznavanju osnovnih definicij teorije grafov in krepkih grafovskih produktov, ki so potrebne pri razumevanju diplomskega dela. Nato so obravnavani retrakti krepkih grafovskih produktov, njihove lastnosti ter potrebni pogoji, da je retrakcija kanonična. V zadnjem poglavju definiramo krepke grafovske svežnje, obravnavamo njihove retrakte ter lastnosti le-teh. Povedano je tudi kako retrakcija preslika določen sloj vlakna ter kdaj je retrakcija krepkih grafovskih svežnjev kanonična.
Keywords: teorija grafov, krepki grafovski produkt, krepki grafovski sveženj, retrakt, kanonična retrakcija
Published: 16.07.2012; Views: 1762; Downloads: 67
.pdf Full text (567,69 KB)

10.
Razdaljno magično označevanje grafov
Nika Švaljek, 2013, undergraduate thesis

Abstract: Razdaljno magično označevanje grafa je bijekcija f : V -> {1, 2,...,n}, z lastnostjo, da obstaja taka konstanta k, da za vsako vozlišče x grafa velja, f(x_1)+f(x_2)+...+f(x_j)= k, kjer je y_i (i = 1,...,j) iz odprte okolice vozlišča x. Diplomsko delo obravnava razdaljno magično označevanje polnih dvodelnih in polnih tridelnih grafov. V prvem poglavju so predstavljeni osnovni pojmi teorije grafov s poudarkom na polnih večdelnih grafifih in barvanjih grafa. V drugem delu najprej predstavimo potreben pogoj za obstoj razdaljno magičnega označevanja. Glavni rezultat tega poglavja je karakterizacija polnih dvodelnih in polnih tridelnih grafov, za katere obstaja razdaljno magično označevanje. Delo zaključimo s seznamom različnih družin grafov, za katere razdaljno magično označevanje ne obstaja.
Keywords: teorija grafov, razdaljno magično označevanje, k - regularni graf, večdelni graf, polni dvodelni graf, polni tridelni graf
Published: 27.03.2013; Views: 1388; Downloads: 130
.pdf Full text (1,86 MB)

Search done in 0.28 sec.
Back to top
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica