Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



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

Скачати 287.67 Kb.

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




Скачати 287.67 Kb.
Сторінка2/3
Дата конвертації13.04.2017
Розмір287.67 Kb.
ТипАвтореферат
1   2   3

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

Всеукраїнській науковій конференції “Сучасні проблеми прикладної математики та інформатики” (Львів, 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, але менша кількості вузлів мережі.

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

Комуніка́ція (від лат. communicatio - єдність, передача, з'єднання, повідомлення, пов'язаного з дієсловом лат. communico - роблю спільним, повідомляю, з'єдную, похідним від лат. communis - спільний) - це процес обміну інформацією (фактами, ідеями, поглядами, емоціями тощо) між двома або більше особами, спілкування за допомогою вербальних і невербальних засобів із метою передавання та одержання інформації.

Прикладні́ науко́ві дослі́дження - наукова і науково-технічна діяльність, спрямована на одержання і використання знань для практичних цілей - розробка нових виробів, нових матеріалів, технологій та технологічного обладнання, нових методів лікування хвороб, медичних препаратів та медичного обладнання, нових сільгоспкультур, нових порід свійських тварин та промислових риб, нових технологій сільгоспвиробництва, пошук покладів корисних копалин.



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

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

(1)

за умов


(2)

(3)

(4)

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



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





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

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

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

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

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

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

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

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

(5)

за умов

(6)



(7)

(8)

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

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

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

і-та задача;

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

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

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

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

(9)

за умов


(10)

(11)

(12)

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



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

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

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

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



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

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

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

.

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

– закон Зіпфа

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



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

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

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

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

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

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

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

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

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

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

Цільова функція - функція, що зв'язує мету (змінну, що оптимізується) з керованими змінними в задачі оптимізації.

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

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

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

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

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

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

.

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

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

.

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



.

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

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

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

,

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

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

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

ВИСНОВКИ

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



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

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

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

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

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


Скачати 287.67 Kb.

  • Структура та обсяг роботи.
  • Основний зміст роботи У вступі
  • У першому розділі
  • У д ругому розділі
  • У додатках