65492

Математичне та програмне забезпечення обчислювальних машин і систем

Автореферат

Информатика, кибернетика и программирование

Одним із основних напрямків розвитку інформаційних технологій є територіально розподілене опрацювання даних в комп’ютерній мережі що пов’язано з необхідністю інтеграції розподілених...

Украинкский

2014-07-30

363.5 KB

3 чел.

1

Національний університет Львівська політехніка

Тичковський Роман Олександрович

УДК 004.75

Математичне та програмне забезпечення оптимального розподілу ресурсів серед вузлів комп’ютерних мереЖ

Спеціальність 01.05.03 – математичне та програмне

забезпечення обчислювальних машин і систем

Автореферат

дисертації на здобуття наукового ступеня

кандидата технічних наук

Львів – 2010


Дисертацією є рукопис

Робота виконана у Львівському національному університеті імені Івана Франка

Міністерства освіти і науки України

Науковий керівник:

доктор фізико-математичних наук, професор

Цегелик Григорій Григорович, 

Львівський національний університет імені Івана Франка, завідувач кафедри математичного моделювання соціально-економічних процесів

Офіційні опоненти:

доктор технічних наук, доцент

Пелещишин Андрій Миколайович,

Національний університет “Львівська політехніка”,

проф. кафедри інформаційних систем та мереж

кандидат технічних наук, доцент

Томашевський Олег Михайлович,

Львівська філія Європейського університету,

завідувач кафедри математики та комп’ютерних дисциплін

Захист відбудеться “17” червня 2010р. о 1400 годині на засіданні спеціалізованої вченої ради Д 35.052.05 у Національному університеті “Львівська політехніка” (79013, м. Львів, вул. С. Бандери, 12).

З дисертацією можна ознайомитися у науково-технічній бібліотеці Національного університету “Львівська політехніка” (79013, м. Львів, вул. Професорська, 1)

Автореферат розісланий  14 травня 2010 р.

Вчений секретар

спеціалізованої вченої ради,

доктор технічних наук, професор       Р. А. Бунь


Загальна характеристика роботи

Актуальність теми. Одним із основних напрямків розвитку інформаційних технологій є територіально розподілене опрацювання даних в комп’ютерній мережі, що пов’язано з необхідністю інтеграції розподілених ресурсів серед її вузлів. Для реалізації інформаційної інтеграції все більшого поширення набувають розподілені бази даних, які функціонують у комп’ютерній мережі та обчислювальні кластери, грід-системи, які сумісно використовують обчислювальні ресурси вузлів комп’ютерної мережі.

Головна концепція проектування таких систем – забезпечення високої їх продуктивності. Одним із напрямів реалізації вказаної концепції є удосконалення технології опрацювання інформації у комп’ютерних мережах. Оскільки основу сучасних інформаційних технологій складають розподілені бази даних, кластери, грід-системи, то удосконалення технології опрацювання інформації передбачає у першу чергу розв’язання проблеми доступу користувачів до ресурсів та реакції системи на запити користувачів за мінімально допустимий час, і у значній мірі визначається організацією розподілу інформаційних та обчислювальних ресурсів як у локальних, так і глобальних комп’ютерних мережах.

Дисертаційна робота присвячена дослідженню основних технологій розподіленої обробки даних, розробці математичних моделей оптимального розподілу обчислювальних ресурсів серед вузлів комп’ютерних мереж, і алгоритмів реалізації цих математичних моделей, розробці математичних моделей оптимального доступу користувачів до інформації інтернет-серверів і методів їх реалізації, які враховують імовірності звертання до сторінок. Розроблені математичні моделі є задачами математичного програмування, які належать до класу NP-повних і для яких не існує ефективних алгоритмів розв’язування. Тому актуальною є розробка алгоритмів, які б мали поліноміальну складність, і давали змогу знаходити оптимальні розв’язки або близькі до оптимальних. Запропоновані у роботі евристичні алгоритми дають змогу отримати такі розв’язки.

Глобальна система Інтернет є унікальним інформаційним ресурсом, який об’єднує величезні обсяги інформації. Основними складовими цього ресурсу є сторінки – атомарні одиниці інформації з унікальним наповненням, об’єднані між собою логічними зв’язками. Найпопулярнішим методом навігації користувача по системі Інтернет є використання пошукових серверів (пошукових систем). Однак ефективність пошуку потрібної інформації користувачем в значній мірі залежить від вибраної стратегії пошуку. Можна послідовно переглядати сторінки, а можна певним чином прискорити пошук, розбивши сторінки на блоки або організувавши спеціальний каталог. Тому актуальною є проблема оптимальної організації доступу до інформації інтернет-серверів з боку користувачів.

Теоретичною та методологічною основою дослідження стали праці таких вчених, як Р. Касі, В. Чу, Д. Кнута, Дж. Мартіна, Г. Г. Цегелика, О.В. Демидовича, Я. Фостера, К. Кессельмана, А.М. Пелещишина та ін., а також аналіз існуючих систем опрацювання інформації, в основі яких лежить концепція розподілених баз даних та розподілених обчислень. При проведенні дослідження використано підхід, запропонований керівником дисертаційної роботи Г. Г. Цегеликом.

Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася у рамках науково-дослідних тем кафедри математичного моделювання соціально-економічних процесів Львівського національного університету імені Івана Франка:

  1.  “Побудова та аналіз математичних моделей оптимальної організації та доступу до інформації баз даних для однопроцесорних та багатопроцесорних ЕОМ”, № держ. реєстрації 0103U001083 (1999 – 2005рр.). Автором проаналізовано деякі математичні моделі оптимального розподілу файлів розподіленої бази даних серед вузлів обчислювальних мереж та розроблено евристичний метод реалізації однієї з моделей, досліджена ефективність використання евристичного і генетичного алгоритмів для розв’язування задачі оптимального розподілу інформаційних ресурсів серед вузлів комп’ютерних мереж.
  2.  “Математичне моделювання природничих, інформаційних та соціально-економічних процесів”, № держ. реєстрації 0106U005905 (2006-2008рр.). Автором досліджена ефективність доступу користувачів до інформації інтернет-серверів для різних законів розподілу ймовірностей звертання до сторінок.
  3.  “Математичне та комп’ютерне моделювання природничих, інформаційних та соціально-економічних процесів. Розробка інтелектуальних систем підтримки прийняття рішень”, № держ. реєстрації 0109U004325 (2009 – 2011рр.). Автором проведено дослідження ефективності еволюційних алгоритмів при розв’язуванні задач дискретної оптимізації.

Мета і завдання дослідження. Метою дисертаційної роботи є розробка математичних моделей оптимального розподілу інформаційних та обчислювальних ресурсів серед вузлів комп’ютерних мереж, оптимального доступу до інформації інтернет-серверів, та алгоритмів їх реалізації, дослідження ефективності розроблених алгоритмів та проведення порівняльного аналізу їх із вже відомими алгоритмами.

Мета дисертаційної роботи визначає необхідність розв’язання таких завдань:

  •  розробити математичні моделі розподілу обчислювальних ресурсів серед вузлів комп’ютерних мереж, які можна звести до задач дискретної оптимізації, та евристичні алгоритми відшукання оптимального або близького до оптимального розподілу;
  •  адаптувати генетичний алгоритм для відшукання оптимального розподілу обчислювальних ресурсів серед вузлів комп’ютерних мереж, застосувавши кодування, яке дає змогу автоматично врахувати обмеження, які накладаються на розподіл;
  •  адаптувати алгоритм гілок і меж для реалізації розроблених математичних моделей, встановити його працездатність та провести аналіз ефективності розроблених алгоритмів;
  •  розробити евристичний алгоритм реалізації математичної моделі визначення оптимальної кількості копій файлів, їх розподілу серед вузлів комп’ютерних мереж, який би давав можливість за певну кількість кроків відшукати оптимальний або близький до оптимального розподіл;
  •  розробити математичні моделі оптимального доступу користувачів до інформації інтернет-серверів, які враховують розподіл ймовірностей звертання до сторінок серверу і вивести співвідношення для знаходження параметрів, за яких математичне сподівання загального часу необхідного для пошуку інформації, досягає мінімуму.

Об’єктом дослідження є розподіл ресурсів серед вузлів комп’ютерних мереж.

Предметом дослідження є математичні моделі оптимального розподілу ресурсів серед вузлів комп’ютерних мереж і алгоритми їх реалізації.

Методи дослідження. В основі досліджень лежить підхід, запропонований керівником дисертаційної роботи Г. Г. Цегеликом для розв’язання задач в рамках проблеми оптимізації сучасних інформаційних технологій. Результати дослідження одержані при використанні теорії організації баз даних, чисельних методів аналізу, методів теорії ймовірностей, математичної статистики, дослідження операцій та системного аналізу, а також експериментальних методів досліджень.

Наукова новизна одержаних результатів. В результаті проведених досліджень в дисертації отримано такі нові наукові результати:

  •  вперше побудовано математичні моделі задач оптимізації розподілу обчислювальних ресурсів серед вузлів комп’ютерних мереж, які зводяться до задач дискретної оптимізації, розроблено евристичні алгоритми реалізації моделей, які мають поліноміальну складність, що дало змогу знаходити оптимальні або близькі до оптимальних розподіли;
  •  адаптовано генетичний алгоритм для відшукання оптимального розподілу обчислювальних ресурсів серед вузлів комп’ютерних мереж, застосувавши представлення розподілу двійковими рядкам, яке дає змогу врахувати обмеження, що накладаються на розподіл та суттєво скоротити час виконання алгоритму;
  •  адаптовано алгоритм гілок і меж для реалізації математичних моделей оптимального розподілу файлів та обчислювальних потужностей серед вузлів комп’ютерних мереж, завдяки чому вдалося зменшити розмірність задачі оптимізації;
  •  розроблено евристичний алгоритм визначення оптимальної кількості копій файлів та їх розподіл серед вузлів комп’ютерних мереж, який дає можливість за певну кількість кроків знайти оптимальний або близький до оптимального розподіл файлів серед вузлів комп’ютерних мереж;
  •  вперше розроблено математичні моделі для задачі оптимізації доступу користувачів до інформації інтернет-серверів, які враховують розподіл ймовірностей звертання до сторінок серверу, де за критерій оптимальності вибрано математичне сподівання загального часу, необхідного для пошуку інформації, що дало змогу вивести співвідношення для знаходження параметрів, за яких математичне сподівання загального часу, необхідного для пошуку інформації, досягає мінімуму.

Практичне значення одержаних результатів. Результати дослідження є внеском у розвиток практики створення систем розподіленої обробки даних та розробки алгоритмів розв’язування задач дискретної оптимізації На основі досліджень спроектовано та реалізовано програмний комплекс оптимального розподілу файлів розподіленої бази даних серед вузлів комп’ютерної мережі, у якій використано евристичні і генетичні алгоритми для знаходження розподілу файлів, що підвищило швидкість отримання інформації із бази даних, не модернізуючи комунікаційне обладнання та робочі станції.

Основні результати, отримані при виконанні дисертаційної роботи, використано для розробки програмного комплексу оптимального навантаження вузлів кластера Львівської філії відкритого акціонерного товариства “Укртелеком” (м. Львів), оптимального розподілу файлів серед вузлів комп’ютерної мережі закритого акціонерного товариства “УВТК” (м. Львів), Львівської філії Промінвестбанку” (м. Львів), використані у НДР, виконаних на кафедрі математичного моделювання соціально-економічних процесів Львівського національного університету імені Івана Франка, а також впроваджені у навчальний процес на факультеті прикладної математики та інформатики Львівського національного університету імені Івана Франка: вони використовуються при читанні курсів “Основи інформаційних технологій” та “Сучасні інформаційні технології”, при написанні курсових та дипломних робіт.

Особистий внесок здобувача. Усі наукові результати, подані у дисертації, одержані здобувачем особисто. У друкованих працях, опублікованих у співавторстві, здобувачу належать: [, ] – евристичний алгоритм реалізації математичних моделей визначення оптимальної кількості копій кожного файлу та їх розподілу серед вузлів комп’ютерних мереж; [, ] – розробка математичних моделей використання процесорних потужностей вузлів комп’ютерних мереж; [, ] – знаходження оптимальних значень параметрів моделі оптимального доступу до інформації інтернет-серверів; [] – опис запропонованого підходу до розробки математичних моделей оптимального розподілу ресурсів серед вузлів комп’ютерних мереж; [, ] – розробка математичної моделі оптимального доступу до інформації інтернет-серверів; [, ] – проаналізовано ефективність двох математичних моделей оптимального доступу до інформації серверів з боку користувача; [, ] – запропоноване кодування у генетичному алгоритмі, яке враховує структуру розв’язків задачі оптимізації розподілу копій файлів; [, , ] – евристичний метод знаходження оптимального розподілу задач серед вузлів кластера; [, ] – адаптація генетичного алгоритму до розв’язування узагальненої задачі про призначення; [, ] – порівняльний аналіз ефективності евристичного і генетичного алгоритмів; [] – реалізація мурашиного алгоритму розв’язування задачі оптимізації розподілу копій файлів; [, ] – використання методики штрафних функцій для врахування структури розв’язків задачі оптимізації розподілу копій файлів; [, ] – виведення співвідношень для визначення значень параметрів, за яких математичне сподівання досягає мінімуму.

Апробація результатів дисертації. Основні результати дисертаційної роботи представлялися та обговорювалися на:

Всеукраїнській науковій конференції “Сучасні проблеми прикладної математики та інформатики” (Львів, 2002 – 2007 рр.), Всеукраїнській науковій конференції молодих науковців “Інформаційні технології в науці, освіті і техніці” (Черкаси, 2002 – 2006 рр.), П’ятій Всеукраїнській науково-практичній конференції “Комп’ютерне моделювання та інформаційні технології в науці, економіці та освіті” (Черкаси, 2003), Міжнародній науково–практичній конференції “Сучасні інформаційні технології в освіті та промисловості” (Миколаїв. 2003), Міжнародній науковій конференції “Dynamical system modeling and stability investigation” (Київ, 2003 – 2005 рр.), Міжнародній науково–практичній конференції “Інтелектуальні системи прийняття рішень та інформаційні технології” (Чернівці, 2004), Міжнародній науково-практичній конференції “Шевченківська весна” (Київ, 2005), конференції молодих учених, із сучасних проблем механіки і математики імені Я. С. Підстригача (Львів, 2005), Міжнародній науково–практичній конференції “Розвиток наукових досліджень - 2005” (Полтава, 2005), Всеукраїнській науковій конференції “Актуальні проблеми аналізу та моделювання складних систем” (Черкаси, 2007), Міжвузівській науково–практичній конференції “Сучасні інформаційні технології в економіці, менеджменті та освіті” (Львів, 2009), а також на семінарах кафедри математичного моделювання соціально-економічних процесів (2002 – 2010 рр.).

Публікації. Результати дисертаційного дослідження опубліковані у 27 наукових публікаціях, у тому числі 9 працях у фахових наукових виданнях, (6 статей у фахових виданнях з технічних наук і 3 статті у фахових збірниках з фізико-математичних наук) та 18 публікаціях у матеріалах та тезах доповідей наукових конференцій.

Структура та обсяг роботи. Дисертація складається зі вступу, чотирьох розділів, висновків, додатків та списку використаної літератури. Загальний обсяг дисертації 152 сторінки, на яких представлено 10 таблиць, 18 рисунків, 5 додатків, 142 найменування літературних джерел, що розміщені на 16 сторінках.

Основний зміст роботи

У вступі наведено загальну характеристику роботи, обґрунтовано її актуальність, сформульовано мету та основні задачі дослідження, наукову новизну роботи та практичну цінність одержаних результатів, її апробацію та публікації.

У першому розділі здійснено огляд існуючих засобів оптимізації комп’ютерних мереж, проаналізовано математичний апарат, що використовується у цих засобах. Сформульовано загальну постановку задачі оптимального розподілу інформаційних та обчислювальних ресурсів серед вузлів комп’ютерних мереж. Аргументовано вибір керованих змінних при оптимізації. Досліджено взаємозалежності між різними числовими критеріями, які використовуються при оптимізації комп’ютерних мереж.

Проведено числовий аналіз середнього обсягу даних, що пересилається по каналах зв’язку при виконанні запитів. У процесі обслуговування запитів на пошук і корегування протягом деякої одиниці часу по каналах зв’язку пересилається деякий обсяг даних, який залежить від розподілу копій файлів серед вузлів мережі. Чим менший обсяг даних, що пересилається по каналах зв’язку за одиницю часу, тим більша швидкість опрацювання запитів.

У процесі роботи системи для кожного файлу виконується певна кількість запитів на пошук і корегування. Опрацювання пошукових запитів породжує передачу по каналах зв’язку відповідей на них, і для зменшення обсягів пересилок доцільно розміщувати файли у кожному вузлі мережі. Обсяг даних, що пересилається у цьому випадку дорівнює 0. З іншого боку, виходячи з того, що при корегуванні файлу відповідний запит передається у всі вузли, де є копії цього файлу, доцільно мати у мережі по одній копії цього файлу. Обсяг пересилок корегування у цьому випадку мінімальний. Очевидно, і це показано на рис.1, що оптимальна кількість копій кожного файлу більша за 1, але менша кількості вузлів мережі.

У роботі розглядаються питання паралельної обробки інформації у комп’ютерних мережах. Основними передумовами створення ефективних систем паралельної обробки є: велика кількість вузлів мережі; висока швидкість передачі інформації між вузлами; незалежне функціонування кожного із вузлів мережі. Не дивлячись на те, що питанням паралельного опрацювання інформації в комп’ютерних мережах посвячено багато публікацій, ця проблема ще потребує серйозних теоретичних і прикладних досліджень.

У другому розділі розглянуто розробку математичних моделей визначення оптимальної кількості копій файлів та їх розподілу серед вузлів комп’ютерних мереж, математичних моделей оптимального використання обчислювальних ресурсів вузлів комп’ютерних мереж (кластерів, грід-систем) та математичних моделей оптимального доступу до інформації інтернет-серверів. Математичні моделі визначення оптимальної кількості копій файлів та їх розподілу серед вузлів комп’ютерних мереж розробляються в залежності від набору факторів, які впливають на структуру і функціонування мережі. 

У результаті розробки математичних моделей визначення оптимальної кількості копій файлів та їх розподілу серед вузлів комп’ютерних мереж, після зведення до вигляду зручного для реалізації та з урахуванням обмежень математична модель задачі має вигляд:

 ()

за умов

 ()

 ()

 ()

де  – невід’ємні цілі сталі, які в кожному конкретному випадку мають певний фізичний зміст;

–шукані величини,

n – кількість вузлів комп’ютерної мережі;

m – кількість файлів бази даних, які необхідно розмістити серед вузлів мережі;

j-й вузол мережі;

i-й файл бази даних;

– кількість можливих варіантів розподілу копій файлу ;

– максимальна кількість копій і-го файлу.

У роботі розроблено математичні моделі оптимального (з погляду певного критерію) використання обчислювальних ресурсів вузлів комп’ютерних мереж. Треба так розподілити задачі між комп’ютерами у мережі, щоб сумарний час розв’язування задач був мінімальний.

Для випадку виконання однієї задачі одного типу математична модель виглядає так:

 ()

за умов

 ()

 ()

 ()

де n – кількість вузлів комп’ютерної мережі;

m – кількість різних задач, призначених до розв’язування;

j-й вузол комп’ютерної мережі;

і-та задача;

– час виконання задачі  на комп’ютері вузла ;

– час, протягом якого можна використати комп’ютер вузла ;

–шукані величини,

Для випадку виконання кількох задач одного типу математична модель виглядає так:

 ()

за умов

 ()

 ()

 ()

де – кількість задач -го типу;

– кількість задач i-го типу, які планують розв’язати на комп’ютері .

Для відшукання оптимальних або близьких до оптимальних розподілів задач запропоновано евристичний алгоритм. Також використовується модифікований генетичний алгоритм.

Глобальна система Інтернет є унікальним інформаційним ресурсом, який об’єднує величезні обсяги інформації. Основними складовими цього ресурсу є сторінки. Ефективність пошуку потрібної інформації користувачем в значній мірі залежить від вибраної стратегії пошуку. Можна послідовно переглядати сторінки, а можна певним чином прискорити пошук, розбивши сторінки на блоки або організувавши спеціальний каталог. Тому актуальною є проблема оптимальної організації доступу до інформації інтернет-серверів з боку користувачів. Розглянуто таку організацію і перегляд сторінок серверу при заданих ймовірностях звертання до сторінок, коли досягається мінімум математичного сподівання загального часу, необхідного для пошуку потрібної сторінки користувачем. При цьому вважається, що всі сторінки розбиті на блоки сторінок і пошук користувачем потрібної сторінки відбувається шляхом послідовного читання блоків сторінок і їх послідовного перегляду.

Припустимо, що інформація, яка зберігається на віддаленому сервері, розміщена на N сторінках. Вважатимемо, що всі сторінки розбиті на n блоків по m сторінок у кожному () і пошук користувачем потрібної сторінки відбувається шляхом послідовного читання блоків сторінок і їх послідовного перегляду. Нехай – ймовірність звертання до i-ої сторінки;

– час читання блоку сторінок, де  –деякі сталі;

– середній час перегляду однієї сторінки користувачем;

E – математичне сподівання загального часу, необхідного для пошуку сторінки. Тоді Е виражається формулою

.

Знайдено явний вираз для Е як у випадку рівномірного розподілу ймовірностей звертання до сторінок, так і для таких законів нерівномірного розподілу ймовірностей як:

– закон Зіпфа

– узагальнений закон розподілу

де  (при с=0,8614 частковим випадком узагальненого закону є розподіл, який наближено задовольняє правило “80–20”);

– “бінарний” розподіл

Виведено співвідношення для знаходження значень параметрів n i m, за яких математичне сподівання Е досягає мінімуму.

У третьому розділі розглядаються алгоритми знаходження оптимального або близького до оптимального розподілу ресурсів серед вузлів комп’ютерних мереж такі як евристичний, генетичний та гілок і меж.

Пропонується новий евристичний алгоритм реалізації математичної моделі визначення оптимальної кількості копій файлів та їх розподіл серед вузлів комп’ютерної мережі, проводиться оцінка складності алгоритму.

Проведено адаптацію алгоритму гілок і меж для розв’язування узагальненої задачі про призначення.

Запропоновано модифікацію генетичного алгоритму, у якій за рахунок спеціально вибраного кодування вдалося скоротити довжину хромосоми і врахувати умови, що накладаються на розв’язки задач.

Розроблений евристичний алгоритм відшукання оптимальних або близьких до оптимальних розподілів задач чи файлів серед вузлів комп’ютерних мереж. Алгоритм складається з двох етапів. На першому етапі знаходимо початковий розподіл, який завжди буде оптимальним, якщо не враховувати умови (). На другому етапі проводиться перерозподіл файлів, якщо для початкового розподілу існує хоча б один індекс  такий, що умова () не виконується.

Другий етап складається із ряду кроків, причому на кожному кроці здійснюється перерозподіл одного файлу із переповненого вузла таким чином, щоб досягти мінімального збільшення значення цільової функції. Виконання другого етапу алгоритму продовжується доти, доки не буде знайдено розподіл, що задовольняє умову (). Блок-схема алгоритму приведена на рис.2

Рис.. Блок-схема евристичного алгоритму визначення оптимальної кількості копій файлів та їх розподілу серед вузлів комп’ютерної мережі.

Зауважимо, що в загальному випадку евристичний алгоритм не дає гарантії одержання оптимального розподілу. Отриманий у результаті виконання алгоритму розподіл може бути оптимальним або близьким до оптимального.

У запропонованій модифікації генетичного алгоритму розподіл ресурсів зображається двійковою послідовністю (кодується), за рахунок цього скорочується довжина представлення розподілу і враховуються умови, накладені на ці розподіли. Блок-схему модифікованого генетичного алгоритму наведено на рис.3.

Рис.. Блок-схема модифікованого генетичного алгоритму.

Розподіл ресурсів за визначенням є двійковим, який, крім мінімізації цільової функції, повинен ще задовольняти додаткові умови (на кількість копій файлу, які можуть використовуватись у комп’ютерній мережі; на обсяг пам’яті, відведеної для зберігання файлів у кожному вузлі; кількість задач різного типу; на час використання кожного комп’ютера). Однак, якщо допустимий розподіл ресурсів представити у вигляді вектора , де  означає, що копії і-го файла розподілені по -му варіанту або і-та задача розподілена по -му варіанту, –кількість різних варіантів розподілу копії і-го файлу (задачі) і кодувати вектор R, а не масив , додаткові умови задачі будуть задовольнятись автоматично. Закодований вектор R має двійкове зображення  довжини , де  обчислюють з такої нерівності:

.

Таким чином, довжина двійкового зображення, яке представляє потенційний розв’язок задачі оптимізації скоротиться від  до , що дає можливість суттєво скоротити час роботи генетичного алгоритму.

Обернене перетворення двійкового вектора S у десяткові значення виконують за такою формулою:

.

Для врахування умови на обсяг пам’яті, відведеної для зберігання файлів у кожному вузлі, використано методику штрафних функцій, тобто функцію корисності в генетичному алгоритмі задано в такому вигляді:

.

де –коефіцієнти масштабування.

Критерієм зупинки генетичного алгоритму, зазвичай, вибирають максимальну кількість ітерацій. Однак експерименти свідчать, що критерієм зупинки для задачі оптимізації розподілу ресурсів серед вузлів комп’ютерних мереж доцільно вибирати такий:

,

де  – максимальне значення функції корисності,  – середнє значення функції корисності для всієї множини розподілів ресурсів.

У четвертому розділі описано роботу спроектованого програмного комплексу оптимального розподілу файлів серед вузлів комп’ютерної мережі. Комплекс протягом певного часу проводить збір статистичного матеріалу про запити до файлів та розповсюдження оновлень, обчислює інтенсивності звертань до файлів і виробляє рекомендації адміністратору системи щодо оптимального розподілу файлів серед вузлів комп’ютерної мережі. Що дозволяє зменшити обсяг даних, що пересилаються по каналах зв’язку при виконанні запитів, зменшити час відгуку системи на запити користувачів не витрачаючи додаткові кошти на модернізацію обладнання.

У додатках подано відомості про результати впровадження дисертаційного дослідження.

ВИСНОВКИ

У роботі розв’язано наукову задачу розробки математичного та програмного забезпечення оптимального розподілу інформаційних та обчислювальних ресурсів серед вузлів комп’ютерних мереж. У процесі виконання цієї роботи одержано наступні результати:

  1.  Досліджено та розроблено алгоритми для реалізації математичної моделі визначення оптимальної кількості копій файлів та їх розподілу серед вузлів комп’ютерних мереж, які мають поліноміальну складність і дають можливість за певну кількість кроків знайти оптимальний або близький до оптимального розподіл.
  2.  Сформульовано задачу оптимального розподілу обчислювальних ресурсів серед вузлів комп’ютерних мереж, побудовано математичні моделі цих задач, які призводять до задач дискретної оптимізації, і розроблено евристичні алгоритми їх реалізації. Також моделі були реалізовані генетичним алгоритмом та алгоритмом гілок і меж. Проведено порівняльний аналіз ефективності використаних алгоритмів.
  3.  Запропоновано модифікацію генетичного алгоритму, яка, за рахунок спеціально вибраного кодування скорочує довжину хромосоми і враховує умови, що накладаються на розв’язки задач.
  4.  Розроблено математичні моделі задачі оптимального доступу до інформації інтернет-серверів. За критерій оптимальності прийнято математичне сподівання загального часу, необхідного для пошуку сторінки. Знайдено явний вираз математичного сподівання для різних законів розподілу ймовірностей звертання до сторінок і виведені співвідношення для знаходження параметрів, за яких математичне сподівання досягає мінімуму.
  5.  На базі створених математичних моделей розроблено програмний комплекс визначення оптимальної кількості копій файлів та їх розподілу серед вузлів комп’ютерної мережі, який протягом певного часу проводить збір статистичного матеріалу про запити до файлів та повідомлення корекції і виробляє рекомендації щодо оптимізації розподілу файлів серед вузлів комп’ютерної мережі.

СПИСОК ОпублікОВАНИХ ПРАЦЬ за темою дисертації

  1.  Тичковський Р. О. Математичні моделі оптимального розподілу файлів серед вузлів обчислювальних мереж і методи їх реалізації / Р. О. Тичковський, Г. Г. Цегелик // Вісник Національного Університету “Львівська Політехніка” : Інформаційні системи та мережі. – 2002. –№464. – С.312-318.
  2.  Тичковський Р. О. Математичне моделювання оптимального розподілу потужностей ЕОМ в обчислювальних мережах / Р. О. Тичковський, Г. Г. Цеге-лик // Фізико-математичне моделювання та інформаційні технології. – 2005. –Вип. 2. – С.179-184.
  3.  Цегелик Г. Г. Моделювання оптимального доступу до інформації серверів зі сторони користувачів / Г .Г. Цегелик, Р. О. Тичковський // Відбір і обробка інформації. – 2004. – №21. – С.196-200.
  4.  Тичковський Р. О.  / Р. О. Тичковський, Г. Г. Цегелик // Восточно-европейский журнал передовых технологий. – 2009. –№6/4(42). – С.49-52.
  5.  Цегелик Г. Г. Математичне моделювання та оптимізація доступу до інформації Інтернет-серверів з боку користувачів / Г. Г. Цегелик, Р. О. Тичковський // Відбір і обробка інформації. – 2008. – №24. – С.143-148.
  6.  Тичковський Р. О. Методи оптимальної організації доступу до інформації Інтернет-серверів з боку користувачів та їх ефективність / Р. О. Тичковський, Г. Г. Цегелик // Вісник Національного Університету “Львівська Політехніка” : Інформаційні системи та мережі. – 2008. –№621. – С.221-230.
  7.  Тичковський Р. О. Використання генетичного алгоритму для розв’язування задачі оптимального розподілу копій файлів серед вузлів обчислювальної мережі / Р. О. Тичковський, Г. Г. Цегелик // Вісн. Львів. ун-ту. Сер. прикл. матем. та інформ. – 2004. –№8. – С.190-195.
  8.  Цегелик Г. Г. Математичне моделювання оптимального використання потужностей ЕОМ в обчислювальних мережах / Г. Г. Цегелик, Р. О. Тичковський // Вісн. Львів. ун-ту. Сер. прикл. матем. та інформ. – 2003. – №6. – С.178-181.
  9.  Тичковський Р. О. Застосування методу гілок і меж для розв’язування узагальненої задачі про призначення / Р. О. Тичковський // Вісн. Львів. ун-ту. Сер. прикл. матем. та інформ. – 2003. – №7. – С.97-102.
  10.  Тичковський Р. О. Математичні моделі оптимального розподілу файлів серед вузлів обчислювальних мереж і методи їх реалізації / Р. О. Тичковський, Г. Г. Цегелик // Матеріали третьої Всеукр. наук. конф. молодих науковців “Інформаційні технології в науці, освіті і техніці – 2002”, – Черкаси: ЧДУ, 2002. – С. 262-265.
  11.  Цегелик Г. Г. Математичне моделювання оптимального використання потужностей ЕОМ в обчислювальних мережах / Г. Г. Цегелик, Р. О. Тичковський // Тези доп. Дев’ятої всеукр. наук. конф. “Сучасні проблеми прикладної математики та інформатики. – Львів, 2002. – С. 130-131.
  12.  Тичковський Р. О. Математичне моделювання оптимального доступу до інформації серверів зі сторони користувачів. / Р. О. Тичковський, Г. Г. Цегелик // Матеріали П’ятої всеукр. наук.-практ. конф. “Комп’ютерне моделювання та інформаційні технології в науці, економіці та освіті”. – Черкаси: Брама-ІСУЕП, 2003. – С. 150-151.
  13.  Тичковський Р. О. Використання генетичного алгоритму для розв’язування задачі оптимального розподілу копій файлів серед вузлів обчислювальної мережі / Р. О. Тичковський, Г. Г. Цегелик // Матеріали Десятої всеукр. наук. конф. “Сучасні проблеми прикладної математики та інформатики”. – Львів, 2003. – С. 117-118.
  14.  Тичковський Р. О. Використання генетичного алгоритму для розв’язування задачі оптимального розподілу копій файлів серед вузлів обчислювальної мережі / Р. О. Тичковський, Г. Г. Цегелик // Матеріали Другої міжнар. наук.-техн. конф. “Сучасні інформаційні технології в освіті та промисловості”. – Миколаїв, 2003. – С. 51-53.
  15.  Цегелик Г. Г. Математичне моделювання оптимального використання потужностей ЕОМ в обчислювальних мережах / Г. Г. Цегелик, Р. О. Тичковський // Тези доп. Десятої міжнар. наук. конф. “Dynamical system modeling and stability investigation”. – Київ, 2003. – С. 414.
  16.  Тичковський Р. О. Адаптація генетичного алгоритму для розв’язування задач оптимального розподілу інформаційних ресурсів серед вузлів обчислювальних мереж. / Р. О. Тичковський, Г. Г. Цегелик // Матеріали Четвертої всеукр. наук. конф. молодих науковців “Інформаційні технології в науці, освіті і техніці – 2004”. – Черкаси: ЧДУ, 2004. – С. 155-156.
  17.  Тичковський Р. О. Математичне моделювання оптимального доступу до інформації серверів зі сторони користувачів / Р. О. Тичковський, Г. Г. Цегелик // Тези доп. Міжнар. наук.-практ. конф. “Інтелектуальні системи прийняття рішень та інформаційні технології”.– Чернівці, 2004. – С. 202-203.
  18.  Тичковський Р. О. Порівняльний аналіз ефективності евристичного і генетичного алгоритмів для розв’язування одного типу задач дискретної оптимізації / Р. О. Тичковський, Г. Г. Цегелик // Тези доп. Одинадцятої всеукр. наук. конф. “Сучасні проблеми прикладної математики та інформатики”. – Львів, 2004. – С. 130-131.
  19.  Тичковський Р. О. Математичне моделювання та оптимізація розподілу інформаційних ресурсів серед вузлів обчислювальних мереж / Р. О. Тичковський, Г. Г. Цегелик // Матеріали Міжнар. наук.-практ. конф. “Інформаційні технології в сучасній економіці, менеджменті та освіті”. – Львів, 2005. – С. 87-88.
  20.  Тичковський Р. О. Використання евристичних і генетичних алгоритмів для розв’язування задач дискретної оптимізації / Р. О. Тичковський, Г. Г. Цегелик // Матеріали міжнар. наук.-практ. конф. “Шевченківська весна”. – Київ, 2005. – С. 298 - 299.
  21.  Цегелик Г. Г. Математичне моделювання та оптимізація доступу до інформації інтернет-серверів з боку користувачів / Г. Г. Цегелик, Р. О. Тичковський // Тези доп. Десятої міжнар. наук. конф. “Dynamical system modeling and stability investigation”. – Київ, 2005. – С. 399.
  22.  Тичковський Р. О. Порівняльний аналіз ефективності евристичного і генетичного алгоритмів для розв’язування одного типу задач дискретної оптимізації / Р. О. Тичковський // Тези доп. Конф. молодих учених із сучасних проблем механіки і математики імені академіка Я. С. Підстригача. – Львів, 2005. – С. 169-170.
  23.  Тичковський Р. О. Порівняльний аналіз ефективності евристичного і генетичного алгоритмів для розв’язування одного типу задач дискретної оптимізації / Р. О. Тичковський, Г. Г. Цегелик // Тези доп. Дванадцятої всеукр. наук. конф. “Сучасні проблеми прикладної математики та інформатики”. – Львів, 2005. – С. 149-151.
  24.  Тичковський Р. О. Математичне моделювання оптимального доступу до інформації серверів зі сторони користувачів. / Р. О. Тичковський, Г. Г. Цегелик // Матеріали Міжнар. наук.-практ. конф. “Розвиток наукових досліджень 2005”. – Полтава, 2005. – С. 27-29.
  25.  Тичковський Р. О. До математичного моделювання оптимального доступу до інформації інтернет-серверів зі сторони користувачів. / Р. О. Тичковський, Г. Г. Цегелик // Матеріали П’ятої всеукр. конф. молодих науковців “Інформаційні технології в науці, освіті і техніці – 2006”. – Черкаси: ЧНУ, 2006. – С.64.
  26.  Тичковський Р. О. Математичне моделювання оптимального використання потужностей ЕОМ в обчислювальних мережах. / Р. О. Тичковський, Г. Г. Цегелик // Тези доп. Всеукр. наук. конф. Актуальні проблеми аналізу та моделювання складних систем”. – Черкаси, 2007. – С.39.
  27.  Тичковський Р. О. Порівняльна характеристика евристичного та еволюційних методів розв’язування задач дискретної оптимізації // Р. О. Тичковський, Г. Г. Цегелик // Матеріали наук.-практ. конф. “Сучасні інформаційні технології в економіці, менеджменті та освіті 2009”. – Львів, 2009. – С. 72-77.

Анотації

Тичковський Р. О. . – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.03 – „Математичне та програмне забезпечення обчислювальних машин і систем”. – Національний університет Львівська політехніка, Львів, 2010.

Дисертація присвячена дослідженню оптимізації розподілу інформаційних та обчислювальних ресурсів серед вузлів комп’ютерних мереж, розробці математичних моделей розподілу ресурсів та алгоритмів знаходження оптимальних або близьких до оптимальних розподілів. Розроблено математичні моделі та алгоритми знаходження оптимального розподілу обчислювальних ресурсів серед вузлів обчислювальних кластерів. Запропоновано евристичний алгоритм, модифікований генетичний алгоритм та алгоритм гілок і меж для визначення оптимального або близького до оптимального розподілу ресурсів серед вузлів комп’ютерних мереж. Розроблено математичні моделі оптимізації доступу користувачів до інформації інтернет-серверів, які враховують розподіл ймовірностей звертання до сторінок серверу, виведено співвідношення для знаходження параметрів, за яких математичне сподівання загального часу, необхідного для пошуку інформації, досягає мінімуму. Розроблено програмний комплекс, у якому використано розроблені математичні моделі, евристичні і генетичні алгоритми відшукання оптимального розподілу файлів розподіленої бази даних серед вузлів комп’ютерної мережі.

Ключові слова: комп’ютерні мережі, кластер, база даних, евристичний алгоритм, генетичний алгоритм, розподіл ресурсів, математичне сподівання.

Тычковський Р. О. сетей. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.03 – «Математическое и программное обеспечение вычислительных машин и систем». – Национальный университет ”Львовская политехника”, Львов, 2010.

Диссертация посвящена исследованию оптимизации распределения информационных и вычислительных ресурсов среди узлов компьютерных сетей, разработке математических моделей распределения ресурсов и алгоритмов нахождения оптимальных или близких к оптимальным распределений. В диссертационной работе разработаны математические модели и алгоритмы нахождения оптимального распределения вычислительных ресурсов среди узлов вычислительных кластеров. Разработан эвристический алгоритм, предложен модифицированный генетический алгоритм и алгоритм веток і границ для определения оптимального или близкого к оптимальному распределения ресурсов среди узлов компьютерных сетей. Разработаны математические модели оптимизации доступа пользователей к информации интернет-серверов, которые учитывают распределение вероятностей обращения к страницам сервера, выведено соотношения для нахождения параметров, при которых математическое ожидание общего времени, необходимого для поиска информации, достигает минимума. Разработан программный комплекс, у котором использовано разработанные математические модели, эвристические и генетические алгоритмы отискания оптимального распределения файлов распределённой базы данных среди узлов компьютерной сети.

Ключевые слова: компьютерные сети, кластер, база данных, эвристический алго-ритм, генетический алгоритм, распределение ресурсов, математическое ожидание.

Tychkovskiy R. O. Mathematical and software support the optimal resources distribution amongst nodes of computer networks. – Manuscript.

A thesis for a Ph. D. sciences degree by speciality 01.05.03 - „Mathematical and software support of computer machines and systems”. – Lviv Polytechnic National University, Lviv, 2010.

The thesis deals with the substantial optimization of the distribution of information and computing resources among units of computer networks, developing mathematical models of resource allocation algorithms and finding the optimal or near optimal distributions. Mathematical models and algorithms sharing computing resources among nodes computing clusters are developed. A heuristic algorithm, the modified genetic algorithm and branch and bound algorithm for determining optimal or near optimal allocation of resources among units of computer networks are proposed. A mathematical model to optimize user access to Internet information servers, which take into account the probability distribution reference to pages server is developed. The ratio to find the parameters under which the expectation of the total time required to search for information, reaches a minimum is found. The software system on the basis of mathematical models mentioned, heuristics and genetic algorithms for finding the optimal distribution of files among distributed database of computer network nodes is developed.

The first chapter deals with a review of existing means of optimization of computer networks, analyzis of the mathematical apparatus used. General problem of optimal information and computational resources among nodes networks is formulated. The choice of controlled variables and parameters of optimization is arguments. The interdependence between different numerical criteria used in the optimization of computer networks is investigated.

The second chapter considers the development of following mathematical models: model of optimal distribution of copies of files among network nodes, where the optimality criterion selected amount of data that is sent via communication channels per unit time; model of optimal utilization of computing resources in network nodes (clusters, grid systems) where time of problems solving should be minimize; model of optimal information access on internet servers where the optimality criterion is the expectation of the total time required to search page. Mathematical models are developed regarding on a set of factors that affect the structure and functioning of the network.

The third chapter discusses the algorithms for optimal or near optimal allocation of resources among units of computer networks such as heuristic, genetic and branch and bound algorithms.

New heuristic algorithm on the basis of mathematical model determining the optimal number of copies of files and their distribution among the nodes of computer networks is proposed. The estimation complexity of the algorithm is made. The developed heuristic algorithm to find optimal or near optimal distribution of files among network nodes. The algorithm consists of two stages. In the first stage the initial distribution, which will be the best, if not take into account the restrictions imposed on the distribution is found. The second stage consists of several steps. With each step a file from crowded nodes so as to achieve the minimum objective function value increase. The second stage of the algorithm continues until it finds the optimal or close to the optimal distribution.

The adaptation of branch and bound algorithm for solving generalized assignment problem is performed.

A modification of the genetic algorithm, which, due to specially selected encoding reduces the chromosome length and takes into account the conditions imposed on the solutions of problems is proposed. Thus, the length of the binary image that represents a potential solution for the problem of optimization to shrink from to  enabling significantly reduce the time needed for the genetic algorithm to complete the task.

The fourth chapter the work of software system designed for optimal distribution of files among computer network nodes is described. The system collects statistical material on requests for files and correction messages, calculates the intensity of traffic and makes recommendations concerning the optimal allocation of files among computer network nodes.

Keywords: computer networks, cluster, database, heuristic algorithm, genetic algorithm, distribution of resources, mathematical expectation.


Підписано до друку 11.05.2010р.

Формат 60x90/16. Папір офсетний. Друк на різографі.

Наклад 100 прим. Замовлення №10224.

Надруковано в Національному університеті "Львівська політехніка"

79013, м. Львів, вул. С. Бандери, 12.


1        опт                   
n

Кількість копій файлу

бсяг даних, які пересилаються

П

К

Рис. . Залежність обсягу даних, що пересилається по каналах зв’язку при виконанні запитів на пошук і корегування: П – пошук; К – корегування; опт – оптимальне значення кількості копій файлу; n – кількість копій файлу, рівна кількості вузлів мережі.


 

А также другие работы, которые могут Вас заинтересовать

10407. Современная система международных отношений: проблемы и противоречия 37.5 KB
  Современная система международных отношений: проблемы и противоречия. Международные отношения более сложное явление чем внешняя политика Это совокупность экономических политических идеологических правовых военных информационных дипломатических и других
10408. Глобальный и региональный аспекты международной безопасности в мире 42 KB
  Глобальный и региональный аспекты международной безопасности в мире. В наши дни в условиях все возрастающей взаимозависимости и взаимосвязи государств на мировой арене становится необходимым изучение не только политических систем отдельно взятых государств но и м...
10409. Понятие национального интереса. Приоритеты внутренней и внешней политики РФ. 40 KB
  Понятие национального интереса. Приоритеты внутренней и внешней политики РФ. Современный мир характеризуется переходом к многополярному мироустройству. Растет многообразие политического экономического и культурного развития стран идет поиск на национальном и ре...
10410. Проблемы политической социализации личности 26 KB
  Проблемы политической социализации личности. Среди множества факторов способствующих сохранению политической системы социализация индивида занимает важное место поскольку ни одна система не сможет достигнуть достаточного уровня интеграции и стабильности если ...
10411. Политическое поведение личности как категория в политологии 35.5 KB
  Политическое поведение личности как категория в политологии. В самом общем виде действие социальных норм состоит: а в установлении типов образцов общественно значимого поведения; б в установлении границ в пределах которых индивидуальное поведение служит осуществл...
10412. Проблемы политического лидерства в обществе. Основные типы политических лидеров 29 KB
  Проблемы политического лидерства в обществе. Основные типы политических лидеров. Понятие лидер€ происходит от английского leader что означает ведущий управляющий другими людьми. Становление и функционирование лидеров объективное и универсальное явление. С понят...
10413. Социально-политические и этнические конфликты 51.5 KB
  Социальнополитические и этнические конфликты. Конфликты в современных условиях отличаются остротой и частым применением насилия. На основе углубления кризисного состояния общества приводящего к столкновениям различных сил и общностей обостряются социальные проти
10414. Социальная дифференциация общества: классовая теория, теория социальной стратификации 23.5 KB
  Социальная дифференциация общества: классовая теория теория социальной стратификации. Социально-классовая стр. Маркса: Появление классов связано с историческими определениями фазами развития производства Классовая борьба ведет к диктатуре пролеториата ...
10415. Общественно-политические движения и организации и формы проявления плюрализма интересов 34.5 KB
  Общественнополитические движения и организации и формы проявления плюрализма интересов. Общественные движения и организации добровольные формирования возникшие в результате свободного волеизъявления граждан объединяющихся на основе общих интересов и целей. Общ