Апарат мереж Петрі та його використання під час моделюванняінтелектуальніх мереж (ІМ)
Мережа Петрі – цеграфічний і математичний засіб моделювання систем і процесів. Базова мережаПетрі складається з позицій, переходів, дуг і фішок. Позицією моделюютьсяумови, при цьому наявність фішки на відповідній позиції вказує на виконанняумови. Перехід у мережі Петрі моделює подію, тобто дію, що відбувається всистемі. Виникнення події відповідає спрацьовуванню (або запуску) переходу.Розміщення фішок на відповідних позиціях мережі Петрі називають розміткоюмережі, вона визначає стан системи. Спрацьовування переходів змінює розміткумережі, що відповідає зміні стану системи при реалізації будь-якої події, азміна розмітки приводить до можливості спрацювання нових переходів, тобтовиникненню нових подій у системі, що змінила свій стан.
Графічна модельсистеми у вигляді мережі Петрі є орієнтованим графом із двома типами вершин,з'єднаних між собою спрямованими дугами. Позиція графічно позначається кружкомабо еліпсом, а перехід – бар'єром або прямокутником (рис.1), дуги можутьз'єднувати вершини тільки різних типів: позицію з переходом або перехід ізпозицією.
/>
/>
/>
/> Позиція Перехід Дуга Фішка
Рисунок1 – Основні елементи мережі Петрі
Перехіддозволений (збуджений) якщо всі його вхідні позиції мають фішки. Спрацьовуєдовільний перехід з безлічі дозволених. При спрацьовуванні перехід вилучаєфішки з усіх своїх вхідних позицій і поміщає в усі свої вихідні позиції.Спрацьовування переходу відбувається миттєво. Графічна інтерпретаціяспрацьовування переходів показана на рис.2.
/>
/>
/> a) перехід не дозволений б) перехід дозволений в) після спрацьовування
Рисунок 2 –Правила спрацьовування переходу
Збезлічі дозволених спрацьовує лише один перехід, який обирається довільно. Цеобумовлює недетермінований характер функціонування мережі. Таким чином, мережаПетрі описує безліч різних припустимих варіантів функціонування систем іпроцесів, що моделюються.
Длямоделювання реальних об'єктів використовують кратні дуги, для яких умовазбудження має виконуватися в кожному екземплярі дуги. Графічно, як правило,зображують одну дугу, підписуючи над нею кратність (рис.3).
/>
/> а) до спрацьовування переходу б) після спрацьовування переходу
Рисунок 3 –Розмітка мережі Петрі із кратними дугами
У класичніймережі Петрі всі фішки мають тип булевих даних, тому не відрізняються одна відодної. Одним з найбільш відомих і популярних розширень базових мереж Петрі єрозфарбовані мережі Петрі (Coloured Petri Nets, CPN), у яких використовують фішкискладного типу. Тип фішки іноді називають її кольором. Такий підхід робить модельбільш лаконічною в порівнянні з еквівалентною моделлю у вигляді базової мережіПетрі, оскільки одна позиція в такому випадку може моделювати безліч умов. Нарис.4 наведено модель системи розподілу ресурсів у вигляді базової (рис.4, а) тарозфарбованої (рис.4, б) мережі Петрі.
Декларація типів,змінних і функцій CPN-моделі системи розподілу ресурсів (рис.4, б), має такийвигляд:
/>
Для моделюваннясистем і процесів, за аналізом яких необхідно враховувати не тільки порядоквиконання дій, але й часові характеристики, часто використовують часові мережіПетрі, які також є одним з відомих розширень базових мереж Петрі.
/>
/> а) б)
Рисунок 4 – Модельсистеми розподілу ресурсів
Для врахуваннячасових характеристик вводяться поняття модельного часу і часової мітки фішки />, яка показуємомент часу, у який дана фішка може бути використана. На графічній моделічасові мітки фішок відображається написом />, розміщеним поруч із фішкою.Кожному переходу або його вихідній дузі можна присвоїти деяку затримку />, що графічновідображається на моделі написом />, розміщеним поруч із відповіднимпереходом або дугою. Під час спрацювання переходів без затримок часовій мітціфішки, що поміщається в його вихідну позицію, присвоюється поточне значеннямодельного часу. Якщо подія, що моделюється переходом, вносить затримку впроцес, що моделюється, мітці присвоюється значення, що дорівнює сумі поточногомодельного часу та часової затримки даного переходу. На рис.5 наведено часовуCPN-модель системи розподілу ресурсів, що пояснює правила спрацьовуванняпереходів у часових мережах Петрі.
Ще однимрозширенням базових мереж Петрі є ієрархічні мережі Петрі, які дозволяютьмоделювати дуже великі системи за модульним принципом, при цьомувикористовуються методи опису системи як «зверху вниз», так і «знизу вгору».Існуючі модулі можна використовувати в моделі кілька разів, крім того, на їхнійоснові можна створювати нові модулі.
Під часпроектування інтелектуальних мереж одним з етапів є розрахунок навантаження тавибір необхідної ємності обладнання. При цьому важливо враховувати той факт, щонавантаження на ресурси IМ істотно залежить від того, які саме послугинадаються мережею.
Важкоспрогнозувати, які саме послуги IМ будуть розроблятися та впроваджуватися вмайбутньому, але в багатьох із них взаємодія з користувачем буде відігравативажливу роль. При цьому в багатьох послугах IМ має місце ситуація, колиодночасно з утриманням ресурсів інтелектуальної периферії (Intelligent Peripheral, IP) відбувається звертання до базиданих, розташованої у вузлі зберігання даних послуг (Service Data Point, SDP), наприклад, при аутентифікаціїкористувача або перерахуванні логічного номера абонента, якого визивають, уфізичний. Таким чином, процес взаємодії з користувачем має наступні фази:
– обслуговуваннязапиту в IP до звертання до зовнішньої бази даних протягом часу />;
– звертання доSDP з одночасним утриманням зайнятого ресурсу IP протягом часу />;
– продовженняобслуговування в IP після одержання необхідних додаткових даних від SDPпротягом часу />.
/>
а) до спрацювання переходу Т4
/>
б) після спрацювання переходуТ4
Рисунок 4 –Часова CPN-модель системи розподілу ресурсів
Таким чином,ресурси IP займаються користувачем протягом всіх трьох фаз обслуговування, аSDP – тільки протягом другої фази. Вважається, що всі три фази можутьповторюватися довільне число разів, залежно від логіки послуги, кількістьциклів визначається параметром />.
На рис.5 наведеномережу Петрі, що описує захват користувачем ресурсів двох різних типів /> і />, щовідповідають ресурсам вузлів IP і SDP відповідно.
Припустимо, що IМнадає /> різнихвидів послуг, при цьому запити на послугу типу /> надходять із інтенсивністю /> і утворюютьчергу до групи ресурсів вузла IP />. Чергу до вузла SDP /> утворюютьзапити, які надходять на обслуговування у вузол SDP після першої та третьоїфази обслуговування.
Під часрозрахунку вважається, що всі потоки запитів є пуасонівськими, а тривалостіобслуговування на всіх трьох фазах />, /> і /> – експоненціально розподіленими зінтенсивностями />, /> і /> відповідно, довжина черги необмежена. Позначимо число ресурсів вузлів IP і SDP як /> і /> відповідно.
Група ресурсіввузла SDP і черга до них може бути апроксимована системою масовогообслуговування (СМО) />, а інтенсивність потоку викликів,що надходить на обслуговування у вузол SDP визначається виразом
/> , (1)
навантаження нагрупу ресурсів вузла SDP становить
/> . (2)
/>
Рисунок 5
Імовірністьочікування в системі /> може бути визначена за формулоюЕрланга:
/>(3)
При дисциплініобслуговування FIFO час очікування є експоненціально розподіленим з інтенсивністю/>.
Тоді при /> середній часочікування в черзі /> складе
/> . (4)
У загальномувипадку час обслуговування користувача послуги класу /> у вузлі IP складається з декількохфаз, як показано на рис.6./> />
Рисунок 6
Для визначеннясереднього часу очікування в черзі /> можна використати наступнеспіввідношення:
/>,(5)
де /> – інтенсивністьнадходження заявок на групу ресурсів вузла IP,
/> – середній часобслуговування запиту на послугу IМ,
/> – середній часобслуговування запиту на послугу класу /> (див. рис.6).
Позначимокількість повторів трьох фаз обслуговування як />, тоді
/> , (6)
/> , (7)
/> , (8)
/> . (9)
Значення /> є сумоювипадкової кількості /> випадкових величин /> і може бути визначене знаступних виразів:
/>, (10)
/> (11)
/> ,
/> . (12)
Середній час перебування заявки вСМО визначаємо за формулою
/> , (13)
мережа петрімоделювання математичне
а навантаження нагрупу ресурсів вузла IP складе
/>. (14)
Подану методикуаналізу характеристик обслуговування запитів на послуги IМ можна застосовуватипри великій кількості типів послуг і невеликому рівні загального навантаження.
Размещено на www.