Հայաստանի ատենախոսությունների բաց մատչելիության պահոց = 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 (173Kb) | Preview

    Abstract

    Առանց լարի ցանցերը կապի` ներկայումս μուռն զարգացում ապրող համակարգերից են, որոնց կիրառությունների քանակը անընդհատ ավելանում է: Այդ ցանցերի` տեղեկույթ տեղափոխելու քանակական և ալգորիթմական հատկությունները տեսականորեն ուսումնասիրելն ու ցանցերն այդ տեսանկյունից առավել արդյունավետ օգտագործելը հիմնական խնդիրներից մեկն է, որից կախված են ցանցի արագագործությունն ու կյանքի տևողությունը (սենսորային ցանցերի դեպքում): Այս խնդիրը մեծ մասամμ ուսումնասիրված է գրաֆային մոդելներում, որոնք փաստորեն μավականաչափ ճշգրիտ չեն ներկայացնում իրական ցանցերի հատկությունները: Այդ պատճառով վերջին տարիներին կատարվող հետազոտություններում դիտարկվում է ֆիզիկական մոդելը, որն ավելի ադեկվատ է ներկայացնում առանց լարի ցանցերում ազդանշանների հեռարձակման ու համադրման μնույթը: Ատենախոսության աշխատանքի հիմնական նպատակն առանց լարի ցանցերի` տեղեկույթ տեղափոխելու հնարավորությունների տեսական ուսումնասիրումն է և ցանցերն այդ տեսակետից արդյունավետ օգտագործող ալգորիթմների մշակումը: Դիտարկվում են սևեռված գծային հզորություններով հերթագրման, ինչպես նաև հզորությունների նշանակմամμ հերթագրման խնդիրները: Քանի որ գծային հզորությունների նշանակումը, որպես էներգա-արդյունավետ նշանակում, համասեռ հզորությունների նշանակման պես ներկայումս հաճախ դիտարկվում է տարμեր խնդիրներում, որոնցից կարևորագույններից են հերթագումը և ուղեգծումը, այս աշխատանքում փորձ է արված ուսումնասիրել այդ նշանակման տեսական-ալգորիթմական հնարավորությունները հերթագրման տեսանկյունից: Մյուս կողմից, քանի որ գծային և համասեռ հզորությունները ցանցերի որոշ կառուցվածքների համար հեռու են օպտիմալ լինելուց, դիտարկվում է հզորությունների նշանակման և հերթագրման խնդիրը: Ատենախոսությունում դիտարկվում են նաև «փոքր աշխարհ» ցանցերի` էվկլիդյան հարթության վրա ոչ ուռուցիկ տիրույթներում μաշխված մոդելներ և հետազոտվում է ուղեգծման հարցն այդպիսի մոդելներում: Ատենախոսությունը հետազոտում է առանց լարի ցանցերը, դրանցում հաղորդակցությունների պահանջների μազմությունները, ինչպես նաև «փոքր աշխարհ» ցանցերը: В лиссертации рассмотрены проблемы составления расписаний с линейными мощностями в беспроволных сетях, составления расписаний с контролем мощностей в беспроволных сетях, а также проблема трассировки в сетях “маленький мир”. Получены слелующие основные результаты: лля залачи составления расписаний с линейными мощностями лля беспроволных сетей, расположенных в метрических пространствах, которые являются некоторым обобщением евклиловых пространств, получен аппроксимационный алгоритм с константным коэффициентом, а также получен порялок ллины оптимальной очерели, опрелелены назначения мощностей, соответствующие ллине, и получена верхняя оценка ллин оптимальных расписаний, соответствующих этим назначениям, используя алгоритм лля составления расписаний с линейными мощностями, получен вероятностный алгоритм лля аппроксимации проблемы межуровневой минимизации, показано, что в некоторых метрических пространствах проблема составления расписаний с линейными мощностями не может быть аппроксимирована с коэффициентом, меньшим 1.5, если P Ф NP, лля проблемы составления расписаний с управлением мощностей рассмотрено назначение срелних мощностей и показано, что при направленной молели трансляции ллина оптимальной очерели при срелнем назначении аппроксимирует залачу с коэффициентом 0(log n loglog Л) в угасающих метриках, лля лвусторонней молели трансляции получен алгоритм лля срелнего назначения мощностей, который на выхоле лает расписание, которое аппроксимирует залачу составления расписаний с управлением мощностей с коэффициентом 0(log n) в угасающих метриках, ввелено понятие “запрещенной области” лля некоторой молели сетей “маленький мир”, таким образом рассмотрена невыпуклая молель таких сетей, привелен “ограниченно жалный” алгоритм, с помощью которого сообщение эффективно лоставляется при “хорошей” расстановке узла-источника и целевой точки, а также показано, что если запрещенные области лостаточно лалеки от границы сети и лруг от лруга, то можно построить лецентрализованный алгоритм, который эффективно лоставляет сообщение с произвольного узла-источника в окрестность произвольной целевой точки, что означает, что такое семейство сетей “трассируемо”.

    Item Type: Thesis (PhD)
    Additional Information: Оптимизационные проблемы в беспроводных сетях. Optimization problems in wireless networks
    Uncontrolled Keywords: Тоноян Тигран Андраникович, Tonoyan Tigran
    Subjects: Mathematics and Cybernetics
    Physics
    Divisions: UNSPECIFIED
    Depositing User: NLA Thesis Dissertations
    Date Deposited: 01 Dec 2015 14:08
    Last Modified: 13 Mar 2017 14:28
    URI: http://etd.asj-oa.am/id/eprint/86

    Actions (login required)

    View Item