UČINKOVITA HEVRISTIKA ZA GRADNJO NAJMANJ UTEŽENE TRIANGULACIJE V PREKRIVNEM OMREŽJUPipan, Gregor (Avtor) Žalik, Borut (Mentor) najmanj utežena triangulacijaporazdeljeno drevoprekrivno omrežjeomrežje po meriporazdeljeni algoritemDisertacija 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.[G. Pipan]20102010-11-10 08:56:47Doktorska disertacija16693sl