UČINKOVITA HEVRISTIKA ZA GRADNJO NAJMANJ UTEŽENE TRIANGULACIJE V PREKRIVNEM OMREŽJU

Pipan, Gregor

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	UČINKOVITA HEVRISTIKA ZA GRADNJO NAJMANJ UTEŽENE TRIANGULACIJE V PREKRIVNEM OMREŽJU
Avtorji:	ID Pipan, Gregor (Avtor) ID Žalik, Borut (Mentor) Več o mentorju...
Datoteke:	DR_Pipan_Gregor_2010.pdf (2,05 MB) MD5: E07155BD283BB7A94AB1196CCB78CBF7 PID: 20.500.12556/dkum/d058f832-8f2b-4ed7-9687-7f5f5179c71e
Jezik:	Slovenski jezik
Vrsta gradiva:	Doktorska disertacija
Organizacija:	FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
Opis:	Disertacija obravnava problem gradnje najmanj utežene triangulacije v prekrivnem omrežju. Prekrivna omrežja uvrščamo v skupino omrežij po meri, ki predstavljajo smer raziskav in razvoja omrežij v zadnjih letih. Poglavitni značilnosti teh omrežij sta decentralizirano upravljanje in povečevanje odpornosti omrežja na napake. Osnovni cilji doktorske disertacije so zasnova K-drevesa in hevristike najmanj utežene triangulacije ter izvedba storitve iskanja virov v prekrivnem omrežju. Algoritem K-drevesa smo zasnovali tako, da minimiziramo njegov evklidski premer in skupno dolžino povezav. Tako drevo omogoča učinkovito iskanje virov v prekrivnem omrežju. Pri hevristiki najmanj utežene triangulacije smo se osredotočili na časovno učinkovitost algoritma, ki mora omogočati tudi sprotno gradnjo in izvedbo porazdeljenega algoritma. Izvedbo storitve iskanja virov smo zasnovali na prekrivnem omrežju. Le-to združuje podomrežje povezav drevesa in podomrežje povezav triangulacije. S tem smo združili prednosti triangulacije, odpornost na napake in učinkovito preiskovanje okolice z možnostjo iskanja oddaljenih virov preko povezav drevesa. Primer uporabe storitve iskanja virov so na primer senzorska omrežja, ki se v zadnjih letih hitro širijo zaradi množice cenenih, prostorsko lociranih senzorjev, sposobnih povezovanja v brezžična omrežja. Z izvedbo eksperimentov v simulacijskem okolju smo potrdili prej omenjene trditve. Rezultati eksperimentov tako potrjujejo, da ima K-drevo bistveno krajši evklidski premer kot najmanjše vpeto drevo ob sprejemljivi skupni dolžini povezav. Rezultati eksperimentov gradnje triangulacije primerjajo skupno dolžino povezav tu predlaganega algoritma z dobro poznanim algoritmom gradnje najmanj utežene triangulacije. Algoritma gradnje K-drevesa in hevristike triangulacije smo izvedli tudi v obliki porazdeljenega algoritma. Lastnosti algoritma smo preverili s pomočjo testov časa izvajanja algoritmov v simuliranem porazdeljenem okolju. Delo zaključimo z jedrnatim in kritičnim pregledom opravljenega dela in poskusimo ovrednotiti naš prispevek na raziskovalnem področju. Na koncu nakažemo še vedno odprte probleme, možne razširitve in dodatne izboljšave algoritmov.
Ključne besede:	najmanj utežena triangulacija, porazdeljeno drevo, prekrivno omrežje, omrežje po meri, porazdeljeni algoritem
Kraj izida:	Maribor
Založnik:	[G. Pipan]
Leto izida:	2010
PID:	20.500.12556/DKUM-16693
UDK:	004.92:514.113(043.2)
COBISS.SI-ID:	253310464
NUK URN:	URN:SI:UM:DK:V3UCC6XF
Datum objave v DKUM:	06.01.2011
Število ogledov:	3259
Število prenosov:	222
Metapodatki:
Področja:	KTFMB - FERI
:	Kopiraj citat

Skupna ocena:	(0 glasov)
Vaša ocena:	Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Sekundarni jezik

Jezik:	Angleški jezik
Naslov:	An efficient heuristic for building minimum weight triangulation in an overlay networks
Opis:	In our work we address the problem of constructing an overlay network based on a minimum weight triangulation. The overlay networks belong to the group of ad hoc networks and have been extensively researched over the past decade. Amongst the most dominant characteristics of these networks are undoubtedly the decentralized management and improvement of the fault tolerance. The main purpose of this thesis is to devise a tree algorithm and algorithm of the minimum weight triangulation, and an implementation of the resource discovery service. The tree algorithm, called K-tree, will be designed so that the Euclidean diameter as well as total length of the edges will be minimized. At minimal weight triangulation algorithm we will focus on time efficiency of the algorithm. In addition, it should also allow an online construction and implementation of a distributed algorithm. The implementation of the resource discovery service will be designed for an overlay network, that combines the tree and the triangulation edges. In this way we combine the benefits of triangulation, fault tolerance, and effective proximity search capabilities with efficient finding distant resources through tree edges. An example of the use of resource discovery service are, for example, sensor networks, which are expanding rapidly in recent years due to large sets of cheap, spatially located sensors, capable of connecting to wireless networks. By conducting experiments in a simulation environment, we confirmed prepositions mentioned before. The results of the experiments confirm that K-tree has substantially smaller Euclidean diameter than the minimum spanning tree at an acceptable total length of connections. The results of experiments of triangulation construction compare the total length edges of the here proposed algorithm with the well-known algorithm of the minimum weight triangulation. We also implemented the algorithms of K-tree and triangulation construction in the form of a distributed algorithm. Properties of the algorithms were tested for a time complexity in the simulated environment. The thesis is concluded by a brief and critical overview of the performed work and evaluation of our work in the research field. In the end we list the problems that still remain open, possible extensions and additional improvements of the algorithms.
Ključne besede:	minimum weight triangulation, distributed tree, overlay network, ad hoc network, distributed algorithm

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)

0 - 0 / 0

Ni komentarjev!

Nazaj