20.500.12556/DKUM-16693 UČINKOVITA HEVRISTIKA ZA GRADNJO NAJMANJ UTEŽENE TRIANGULACIJE V PREKRIVNEM OMREŽJU An efficient heuristic for building minimum weight triangulation in an overlay networks 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. 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. najmanj utežena triangulacija porazdeljeno drevo prekrivno omrežje omrežje po meri porazdeljeni algoritem minimum weight triangulation distributed tree overlay network ad hoc network distributed algorithm true true false [G. Pipan] Slovenski jezik Angleški jezik Doktorska disertacija 2010-11-10 08:56:47 2011-01-06 13:27:33 2022-04-13 08:49:54 2022-04-19 03:26:15 2010 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.92:514.113(043.2) 253310464 URN:SI:UM:DK:V3UCC6XF DR_Pipan_Gregor_2010.pdf DR_Pipan_Gregor_2010.pdf 1 E07155BD283BB7A94AB1196CCB78CBF7 be2ac7c35de069391198874fd745c40f460365677c316c00017d505b889cd3c3 b4d320f8-7c04-11eb-bb7a-00155d0001ca 20.500.12556/dkum/d058f832-8f2b-4ed7-9687-7f5f5179c71e https://dk.um.si/Dokument.php?lang=slv&id=19051 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0