Dovoľujeme si oznámiť, že dňa
22. 8. 2018 o 14.00 hod.
sa uskutoční na Fakulte informatiky a informačných technológií STU v Bratislave
Ilkovičova 2, v miestnosti 5.08 obhajoba dizertačnej práce
Ing. Dušana Bernáta
Názov dizertačnej práce:
Odhad počtu smerovačov v ad hoc sieťach
On the Estimation of Number of Routers in an Ad Hoc Network
Odbor: 9.2.9 Aplikovaná informatika
Školiteľ: prof. Ing. Pavel Čičák, PhD. - FIIT STU v Bratislave
Oponenti dizertačnej práce:
doc. Ing. František Jakab, PhD. – FEI TU v Košiciach
prof. Ing. Pavol Horváth, PhD. - CVT STU v Bratislave
Abstrakt:
Táto práca sa zaoberá určením odhadu počtu smerovačov v ad hoc sieťach na základe ich grafového modelu. Využíva k tomu pojem dominujúcej množiny uzlov a to dvoma spôsobmi. V prvom rade sa zameriava na teoretické určenie dolného odhadu strednej hodnoty veľkosti minimálnej dominujúcej množiny (MDS) pre náhodné grafy, ktorých podkladový graf je karteziánsky súčin cyklov, ako napríklad dvojrozmerný torus. Vyhodnotenie presnosti odhadu a porovnanie s odhadom založeným na spočítavaní stupňov vrcholov s využitím simulácií ukázalo, že navrhovaný odhad je presnejší pre interval nižších hodnôt parametra pravdepodobnosti p.
Druhým cieľom je praktická realizácia heuristického algoritmu pre hľadanie MDS. Zamerali sme sa na grafy ktoré majú distribúciu stupňov vrcholov v tvare mocninového zákona, ktoré dobre modelujú reálne siete. Navrhovaný algoritmus je založený na pridávaní vrcholov ktoré majú susedov s minimálnym stupňom. Na testovacích dátach sa prejavilo zväčšenie dominujúcej množiny oproti minimálnej v najhoršom prípade o 15.7 % a v prípade redukcie nadbytočných prvkov o necelých 5 %. Čas vykonávania bol však rádovo menší než pri greedy algoritme. To môže v prípade väčších grafov umožniť urobiť odhad MDS aj tam, kde by použitie iných metód nebolo únosné.
The aim of this thesis is to give an estimated number of routers in an ad hoc network, assuming its graph model is provided. There are two approaches proposed, both utilising the notion of dominating set of nodes. Firstly it is concerned with theoretical derivation of a new lower bound for the expectation of domination number for random graphs with base graph being a Cartesian product of cycles, such as, e.g. a two-dimensional torus. Evaluation of accuracy and comparison to the lower bound based on the vertex degree counting was realised by simulations. The proposed new lower bound is more precise than the other one in the interval of lower values of the probability parameter p. The second objective was practical realisation of a heuristic algorithm for finding a MDS. We focused on the graphs with power law degree distribution which present a good model of real world networks. Proposed algorithm is based on adding the vertices which have neighbours of minimum degree. On our test sample the worst case increase in dominating set size compared to the minimum one was 15.7% and when the reduction of unnecessary vertices was used, it was below 5%. But the execution time was by few orders shorter than it was in the case of greedy algorithm. This can make significant difference in the case of large graphs and allows for MDS size estimation even when.
Autoreferát dizertačnej práce 
zaslaný do vedeckého časopisu Information Sciences and Technologies - Bulletin of ACM Slovakia.
Dizertačná práca je k nahliadnutiu na Študijnom oddelení FIIT STU.
