Հայաստանի ատենախոսությունների բաց մատչելիության պահոց = Open Access Repository of the Armenian Electronic Theses and Dissertations (Armenian ETD-OA) = Репозиторий диссертаций Армении открытого доступа

Անլար ցանցերի մաթեմատիկական մոդելներում ալգորիթմական խնդիրների հետազոտում

Ասլանյան , Հակոբ Լևոնի (2010) Անլար ցանցերի մաթեմատիկական մոդելներում ալգորիթմական խնդիրների հետազոտում. PhD thesis, ԵՊՀ.

[img]
Preview
PDF (Abstract)
Available under License Creative Commons Attribution.

Download (162Kb) | Preview

    Abstract

    Ներկայացվող աշխատանքը նվիրված է ժամանակակից համակարգչային ցանցերի նորագույն մաթեմատիկական մոդելների և ալգորիթմական խնդիրների ուսումնասիրմանը: Ինֆորմացիոն տեխնոլոգիաները, որոնք բիո և նանոտեխնոլոգիաների հետ մեկտեղ համարվում են տնտեսության զարգացման ներկայիս կարևորագույն գործոնները, բնութագրվում են այնպիսի ձեռքբերումներով, ինչպիսիք են նորագույն ցանցերը (ինտերնետ, բջջային ցանց, գլոբալ տեղադրվածության համակարգեր, շարժական և ռադիո կապի ցանցեր), բարձր արդյունավետության և էլեկտրոնային սարքերը և համակարգերը (տերաբիթանոց կապ, GRID համակարգեր, անհատական օգտագործման սարքերի նոր սերունդ), էլեկտրոնային բովանդակության համակարգերը (սոցիալական ցանցեր, էլեկտրոնային գրադարաններ) և այլն: Տիրույթի հաջողությունները պայմանավորված են միկրոէլեկտրոնիկայի զարգացմամբ և, համամասնորեն, մաթեմատիկական նոր գիտելիքի ձևավորմամբ: Վերջիններիս թվում են բազմանդամային նորանգույն ալգորիթմները` գծային ծրագրավորում և թվի պարզության ստուգում, հայտնի դասական խնդիրների լուծման նոր ալգորիթմներ, ստորին գնահատականների բարելավում` մոնոտոն սխեմաների բարդություն, հոմոմորֆիկ կրիպտոմոդելի ստեղծում, ապրոքսիմացիոն ալգորիթմների ստացում և այլն: Այս ամենին զուգահեռ առաջանում են նոր մաթմատիկական մոդելներ, որոնց ուսումնասիրումն առաջ է բերում նոր ալգորիթմական խնդիրներ: Նման առանձնահատուկ օրինակ է անլար սենսորային ցանցերի գիտատեխնիկական տիրույթը: Սենսորային ցանցի հանգույցները ինքնավար սարքեր են, կազմված զարգացած տեխնիկական համակարգերից` սենսորներ, ռադիո կապի հնարավորություն, հաշվող սարք և սնուցում: Սրանք լինելով միկրո-սարքեր, ունեն սահմանափակ ռեսուրսներ և պահանջում են օպտիմալ կառավարում երկարաժամկետ գործունեության ապահովման համար: Երկրորդ կարևորագույն առանձնահատկությունը ինքնակառավարման կարգընթացների անհրաժեշտությունն է այն կապակցությամբ, որ ցանցի կառուցվածքը ի սկզբանե անհայտ է և որ այն կարող է կազմվել լոկալ գործընթացների արդյունքում, ինչն ինքնակառավարման դասական սցենար է: Работа посвящена исследованию моделей беспроводный сенсорный сетей. Этот новый тип сетей имеет важные приложения в критически системаx мониторинга и управления. Сенсоры являются автономными звеньями сетей и обладают измерительными, вычислительными и коммуникационными функциями при значительно ограниченом обьеме питания. Сенсоры, случайным образом распределенные на территории, снабжены протоколами, которые упавляют процессом конфигурации пар связанный вершин в сети, снабжают вершины секретными ключами коммуникации и следят за тем, чтобы снизить ненужное проникновение радиоволн коммуникации (интерференция) при минимальной используемой энергии. Рассматриваются здачи связности и покрытия целевой области, которые в математической формулировке сводятся к задачам поиска связного подграфа с некоторыми ограничениями, задачам минимального покрытия множества подмножествами и построении легких криптомоделей, например на основе простыгх алгебраически алгоритмов. Одна группа основный резултатов посвящена минимизации интерференции, для которой построен алгоритм, основанный на итеративном обращении к задаче частичного покрытия с частичным участием. Доказывается NP полната этой задачи. Проводится анализ построенного алгоритма доказывая, что число шагов является логарифмом от числа вершин графа и, что полученная интерференция не превосходит квадрата минимума и логарифма числа вершин. Из группы задач покрытия целевой области рассматривается модель, где информацию собирают автономные агенты, равномерно блуждающие по сети. Рассмотрен ряд таки моделей, доказывается и эквивалентность и выводятся формулы вероятностей, эквивалентные комбинаторным числам Стирлинг второго рода. Рассматривается также задача защиты коммуникации в сети. Строится “легкая” схема симметичной криптографии основанная на сильный порождающи множествах. Основным выводом является то, что применение комбинаторной, алгебраической и вероятностной теорий позволяет построить эффективные алгоритмы проектирования оптимальных беспроводных сетей, решив основные задачи связности сети и покрытия целевой области при учете требования минимизации используемой энергии.

    Item Type: Thesis (PhD)
    Additional Information: Исследование алгоритмических проблем в математических моделях беспроводных сетей. Studies on algorithmic problems of wireless sensor network mathematical models.
    Uncontrolled Keywords: Асланян Акоб Левонович․ Aslanyan Hakob L.
    Subjects: Mathematics and Cybernetics
    Divisions: UNSPECIFIED
    Depositing User: NLA Circ. Dpt.
    Date Deposited: 01 Dec 2015 12:31
    Last Modified: 13 Mar 2017 11:03
    URI: http://etd.asj-oa.am/id/eprint/70

    Actions (login required)

    View Item