| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font
First page > Show document

Show document Help

Title:UČINKOVITA HEVRISTIKA ZA GRADNJO NAJMANJ UTEŽENE TRIANGULACIJE V PREKRIVNEM OMREŽJU
Authors:ID Pipan, Gregor (Author)
ID Žalik, Borut (Mentor) More about this mentor... New window
Files:.pdf DR_Pipan_Gregor_2010.pdf (2,05 MB)
MD5: E07155BD283BB7A94AB1196CCB78CBF7
PID: 20.500.12556/dkum/d058f832-8f2b-4ed7-9687-7f5f5179c71e
 
Language:Slovenian
Work type:Dissertation
Organization:FERI - Faculty of Electrical Engineering and Computer Science
Abstract: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.
Keywords:najmanj utežena triangulacija, porazdeljeno drevo, prekrivno omrežje, omrežje po meri, porazdeljeni algoritem
Place of publishing:Maribor
Publisher:[G. Pipan]
Year of publishing:2010
PID:20.500.12556/DKUM-16693 New window
UDC:004.92:514.113(043.2)
COBISS.SI-ID:253310464 New window
NUK URN:URN:SI:UM:DK:V3UCC6XF
Publication date in DKUM:06.01.2011
Views:3255
Downloads:222
Metadata:XML DC-XML DC-RDF
Categories:KTFMB - FERI
:
Copy citation
  
Average score:(0 votes)
Your score:Voting is allowed only for logged in users.
Share:Bookmark and Share



Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Secondary language

Language:English
Title:An efficient heuristic for building minimum weight triangulation in an overlay networks
Abstract: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.
Keywords:minimum weight triangulation, distributed tree, overlay network, ad hoc network, distributed algorithm


Comments

Leave comment

You must log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica