Prejsť na obsah
dizertácie

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. – KPI 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.