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

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

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

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

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

Аналіз існуючих засобів імітаційного моделювання показав, що найбільш придатним математичним апаратом, для опису моделей протоколів інформаційного обміну є Е-мережі. Як апарат імітаційного моделювання Е-мережі дозволяють легко моделювати рівнобіжні взаємодіючі асинхронні процеси. Допускають будь-яку змістовну інтерпретацію своїх складових, що дозволяє одночасно моделювати як інформаційні потоки, так і апаратну частину. Допускають різне трактування своїх елементів за рівнем абстракції (деталізації), що дозволяє будувати ієрархічні моделі, у яких перехід може транслюватися в підмережу більш низького рівня деталізації. Зазначені особливості Е-мереж значно знижують суперечливість вимог до простоти й адекватності моделі. По моделюючим можливостям Е-мережі значно перевершують кінцеві автомати і наближаються до абстрактних машин. Моделюючі можливості формалізовані в понятті “виразна потужність”. Відомо, що Е-мережі по виразній потужності однакові з машинами Тьюринга. Графи Е-мереж мають високу ілюстративність і дають наочне представлення про протікання процесу.

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

Досвід використання Е-мереж як засобу розробки моделей протоколів інформаційного обміну виявив їх деякі недоліки. Для їх усунення, а також спрощення процесу розробки моделей у дисертації були введені доповнення в апарат Е-мереж. Множина переходів доповнена переходами J', F', М2, M2', для яких умови збудження мають вигляд:

J': ,

де L - пряма функція інцидентності; D - зворотня функція інцидентності; М(р_i) - розмітка місця р_i, m - кількість вхідних місць.

F': ,

де n - 1 - кількість вихідних місць.

M2:р₁L(M2){M(p₁)=1}р₂L(M2){M(p₂)=1} р₃D(M2){M(p₃)=0}.

M2':(р₁L(M2){M(p₁)=1}р₂L(M2){M(p₂)=1}) р₃D(M2){M(p₃)=0}.

Процедура переходів М2 і М2':

_Rij={M(p₁(R(i)) M(p₂R(i))):= M(p₃R(i))},

відповідає операції додавання по mod2 для елементів i вектора атрибутів міток, які знаходяться у вхідних місцях р₁ і р₂.

Множина місць доповнена макромісцем-чергою з пріоритетною дисципліною обслуговування. Розширено можливості визначення предикатів МХ і MY-переходів.

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

Відповідно до рекомендацій МККТТ на етапах специфікації і проектування протоколи повинні бути представлені у виді SDL-діаграм або схем алгоритмів. Отже, дані засоби і були прийняті як джерела початкових даних для розроблювальної методики. При формуванні Е-мережі, коли в якості вихідних даних використовуються схеми алгоритмів роботи, за основу прийнята відома методика, розроблена для апарата мереж Петрі. У дану методику внесено зміни, що дозволяють врахувати специфіку Е-мереж (наявність розходжень у топології й описі апарата і т.п.). Порівняльний аналіз SDL-діаграм і Е-мереж як засобів формального опису протоколів інформаційного обміну показав, що безпосередній перехід неможливий. Для усунення даного недоліку запропонована послідовність дій, що дозволяє здійснити перехід від SDL-діаграми до Е-мереж.

1. По елементах множини вершин “стан і рішення” (sr) утворити місця.

2. По відношенням предшествовання і проходження станів утворити переходи мережі:

f:(S I {0;1}) ((I О Р) (О S R Р) {0;1})

(R (О S R Р) {0;1});

g: ( I S {0;1}),

де f -- функція проходження; g -- функція предшествування; I - кінцева множина символів ВХІД; О - кінцеву множину символів ВИХІД; S - кінцева множина символів СТАН; R - кінцева множина символів РІШЕННЯ; Р - кінцева множина символів ЗАДАЧА.

3. Встановити між ними відношення інцидентності:

F(sr_i) = f^m(sr_i) = {sr_i}; G(sr_j) = g^m(sr_j) = {sr_j}.

4. Вершинам ВХІД та ВИХІД, що знаходяться між сусідніми вершинами “стан і рішення”, утворити дуги до підмережі зовнішнього середовища:

L(b_i,h_k)=1; D(h_k,b_i)=1,

де L - пряма функція інцидентності; D - зворотна функція інцидентності; h_k H - перехід Е-мережі; b_i B - периферійне місце.

5. Присвоїти атрибути і визначити процедури переходів мережі.

6. Визначити вектор атрибутів мітки.

7. Встановити початкову розмітку.

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

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

Для рішення задач аналізу динаміки функціонування протоколів інформаційного обміну і СОД у цілому проводиться імітаційне моделювання. Запропонована методика моделювання припускає сполучення стохастичної (зовнішнього середовища) і детермінованої частини (алгоритм, ресурси). Отримання значень показників якості на імітаційній моделі виробляється шляхом аналізу кількості міток у місцях-поглиначах та динаміки їх переміщення по мережі. Оцінка точності та вірогідності результатів імітаційного моделювання визначається за допомогою оцінки довірчого значення погрішності. Довірчу імовірність () і припустиму величину відносної помилки () запропоновано встановити: = 0,8 і = 0,5%. Обчислення вироблялися в припущенні, що частоти появи аналізованих подій розподілені по нормальному закону. Для забезпечення заданої точності параметри експерименту встановлене: k=100, m=10000, де k - число дослідів, m - число реалізацій у досліді (переданих пакетів).

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

Розробка моделей протоколів інформаційного обміну відбувається відповідно до 7-ми рівневої структури взаємодії відкритих систем (ВВС) (для розробки моделі протоколу (N+1)-го рівня використовуються результати, отримані на моделі протоколу N рівня). Даний підхід враховує взаємодію протоколів різних рівнів, а також знижує протиріччя між вимогами до адекватності і простоти моделей.

При розробці моделей каналу зв'язку топологія і склад Е-мережі визначається типом помилок, які виникають у каналі зв'язку. Розроблено методики моделювання для двох типів каналів зв'язку: з корельованими і некорельованими помилками.

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

Для перевірки адекватності введеного розширення Е-мереж розроблена модель найбільш розповсюдженого протоколу канального рівня LAP-B у режимах встановлення з'єднання і передачі кадрів. На розроблених моделях отримані залежності часу встановлення з'єднання і часу доведення двох пакетів від рівня помилок у каналі зв'язку. Графічно ці залежності представлені на рис. 1 і 2.

Рис. 1. Графік часу встановлення з'єднання

Аналіз приведених залежностей показує, що розбіжність між результатами імітаційного (крива И. М.) і аналітичного (крива А. М.) моделювання не перевищує 5% на всьому інтервалі при описаних вище параметрах імітаційного моделювання. Отже, можна зробити висновок про адекватність введеного розширення Е-мереж.

Рис. 2. Графік часу доведення двох кадрів

За одиницю часу моделювання прийнята тривалість пакета (Т_п). Отже, - середній відносний час встановлення з'єднання (рис.1) і середній відносний час доведення двох кадрів (рис. 2).

Розробка моделей відбувалася для наступних умов: імовірність помилки в каналі зв'язку р_о= 10^-3 - 10^-5; помилки в каналі зв'язку некорельованні; у якості завадостійкого використовується циклічний код з поліномом, що породжує, х¹⁶+х¹²+х⁵+1; кількість перезапитів не обмежений; довжина кадру 128 біт. Інтервал зміни імовірності помилок у каналі зв'язку обумовлений характеристиками реальних каналів.

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

Часткова методика моделювання протоколів транспортного рівня дозволяє врахувати різні механізми боротьби з пакетами, що затрималися в підмережі; методи управління потоком, які використовувались; методи підвищення вірогідності переданої інформації. З метою перевірки працездатності запропонованої методики і введеного розширення Е-мереж розроблена модель протоколу ТСР для режимів встановлення з'єднання й обміну сегментами. На моделі отримані залежності часу й імовірності встановлення з'єднання і передачі ТСР - сегмента від імовірності помилок на мережевому рівні і кількості перезапитів, що показують погодженість з відомими результатами.

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

Запропонована методика дозволяє:

розробляти моделі відповідно до належності протоколу до визначеного рівня ВВС та особливостей функціонування;

для розробленої Е-мережі виконати перевірку її коректності й імітаційне моделювання;

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

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

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

У четвертому розділі визначено, що для реалізації методики моделювання протоколів інформаційного обміну необхідна розробка відповідного програмного комплексу. Розроблені вимоги, до таких засобів і визначено задачі, які розв'язуються з їхньою допомогою. Описано принципи їхньої реалізації. Розроблено і програмно реалізовано алгоритми, які дозволяють зробити побудову, аналіз моделей протоколів з використанням Е-мереж і ЙЧГ.

Для розширення області застосування ЙЧГ розроблено метод аналізу графів, для яких неможливе застосування методу еквівалентних перетворень.

З огляду на специфіку використаних математичних апаратів (Е-мережі та ЙЧГ), прийняте рішення про необхідність розробки двох окремих програм: “Е-мережа” і “ЙЧГ”.

За допомогою програми “Е-мережа” реалізується можливість: побудови графа Е-мережі (моделі досліджуваної системи); автоматичного визначення функцій інцидентності для переходів сформованої Е-мережі; визначення параметрів (тимчасових характеристик, процедур переходів, предикатів для МХ- і MY-переходів) переходів; визначення параметрів взаємодії з зовнішнім середовищем (потоки пакетів (біт), які надходять із суміжного рівня чи каналу зв'язку); забезпечення можливості побудови ієрархічної структури моделей (аналогічно концепції побудови протоколів обміну даними); визначення параметрів імітаційного експерименту (тривалості моделювання, умов припинення моделювання, режиму роботи моделі); збору статистики; визначення алгоритмічних властивостей шляхом аналізу графа Е-мережі (оцінка якісних показників функціонування об'єкта, що моделюються).

За допомогою програми “ЙЧГ” реалізується можливість: побудови ймовірносно-часового графа, що описує систему, яка моделюється; формування матриць суміжності і інцидентності графа по графічному зображенню; проведення еквівалентних перетворень графа; за результатами перетворень формування результуючих функцій, що описують перехід системи з початкових станів у кінцеві чи задані.

Крім того в даному розділі розроблений метод аналізу так званих “графів, що не приводяться” (графи, топологію яких не вдається методом еквівалентних перетворень привести до виду, що містить тільки початковий і кінцевий стан). Розроблений метод передбачає на першому етапі за допомогою апарата ланцюгів Маркова розрахунок кількості тактів роботи системи, через яке вона виявиться в одному з кінцевих станів:

,

де Р - матриця перехідних імовірностей на k-м кроці;

N - вектор початкової розмітки;

С_к - вектор розподілу імовірностей між станами моделюємої системи на k-м кроці.

Обчислення вектора проводиться доти, поки сума імовірностей перебування системи в кінцевих станах не буде більше встановленого дослідником граничного значення, номер кроку на який виконається дана умова і приймається за кінцевий - n:

,

де i, j, l - номера кінцевих вершин; g - граничне значення сум імовірностей.

На другому етапі знаходиться значення середнього часу, необхідного для досягнення кінцевих станів за визначене (n) число кроків.

ВИСНОВКИ ПО РОБОТІ

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

2. У ході аналізу засобів, що застосовуються для розробки моделей протоколів інформаційного обміну, було з'ясовано, що найбільш прийнятними інструментами є Е-мережі (як апарат імітаційного моделювання) і ЙЧГ (як апарат аналітичного моделювання). Такий вибір дозволив сформулювати загальну концепцію розробленої методики: засоби аналізу - Е-мережі і ЙЧГ; предметна область - структура протоколів інформаційного обміну, канали зв'язку, які використовуються; вважаються відомими - алгоритми роботи протоколів, параметри використовуваної апаратури, каналів зв'язку.

3. Відповідно до поставленої задачі розглянуті методи розробки й опису графів Е-мереж при різних вихідних даних. У якості вихідних даних, використовуваних у розробленії методиці, обрані схеми алгоритмів і SDL-діаграми.

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

5. Як методи кількісного аналізу моделей основним прийняте імітаційне й аналітичне моделювання. Для даного методу обрані показники якості протоколів різних рівнів ВОС, а так само описані способи їхнього одержання на Е-мережах і ЙЧГ.

6. Для підвищення точності моделей в апарат Е-мереж введені доповнення. Розширені: множина переходів введенням переходів J', F', M2 і M2'; множина місць - макромісцями-чергами Q і Q'; розширені можливості опису предикатів MX-, MY-переходів.

7. Розроблено метод аналізу ЙЧГ, що дозволяє отримувати значення показників якості на графах, для яких неможливе застосування методу еквівалентних перетворень. Розробка даного методу розширює область застосування апарата ЙЧГ.

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

9. При розробці моделі протоколу LAP-B зроблена перевірка адекватності введеного розширення Е-мереж. Отримані у ході моделювання значення показників якості функціонування показують узгодженість з відомими результатами.

10. Для реалізації методики моделювання розроблений програмний комплекс, що дозволяє робити побудову й аналіз моделей за допомогою апаратів Е-мереж і ЙЧГ. При рішенні даної задачі сформульовані вимоги, що ставляться перед такими системами, а також принципи їх функціонування. Специфіка обраних апаратів моделювання визначила необхідність розробки двох програм:

програма розробки й аналізу моделей, представлених Е-мережею, а так само проведення імітаційного моделювання;

програма побудови, перетворення й аналізу ЙЧГ.

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

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

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

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

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ

1. Лосев Ю.И., Шматков С.И., Дуравкин Е.В. Применение Е-сетей для моделирования процесса функционирования СОД// Радиотехника: Всеукр. межвед. науч.-техн. сб. 2001. Вып. 123. С. 99-103.

2. Лосев Ю.И., Дуравкин Е.В. Применение методов анализа Е-сетей к моделям СОД// Радиотехника 2002. Вып 132. С. 189-202.

3. Лосев Ю.И., Польщиков К.А., Дуравкин Е.В. Адаптивная маршрутизация в телекоммуникационных сетях// Радиотехника 2002. Вып 128. С. 74-79.

4. Лосев Ю.И., Шматков С.И., Дуравкин Е.В. Методика моделирования протоколов канального и сетевого уровней с использованием Е-сетей и вероятностно-временных графов// Сборник научных трудов 1-го Междунароного радиоэлектронного форума “Прикладная радиоэлектроника. Состояние и перспективы развития” (МРФ-2002). - Часть 1. - Харьков: АН ПРЭ. - 2002. С. 409-412.

5. Лосев Ю.И., Дуравкин Е.В. Программная среда разработки и анализа моделей протоколов информационного обмена// Труды УННИРТ - 1. 2003г. с. 13-15.

АНОТАЦІЯ

Дуравкін Є. В. Методика моделювання протоколів інформаційного обміну з використанням Е-мереж та ймовірносно-часових графів. - Рукопис. Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.12.02 - Телекомунікаційні системи та мережі. Українська державна академія залізничного транспорту. Харків, 2003.

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

Для підвищення точності моделей у апарат Е-мереж введені доповнення: розширені множини переходів, місць.

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

Розроблена загальна методика моделювання базується на узагальнені часткових методик окремих рівній та дозволяє:

зробити розробку моделі відповідно належності протоколу до визначеного рівня ВВС і особливостями функціонування;

для розробленої Е-мережі провести перевірку її коректності та імітаційне моделювання;

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

Адекватність методики моделювання преревірялась шляхом порівняння результатів моделювання з відомими.

Для реалізації запропонованої методики моделювання розроблений програмний комплекс, до складу якого входять програми побудови і аналізу моделей, що наведені у вигляді Е-мереж та ЙЧГ.

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