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

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

Preview

PDF (Abstract) Available under License Creative Commons Attribution. Download (162Kb) | Preview

Abstract

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

Actions (login required)