Особливості математичних моделей мереж зв’язку
Вступ
Мережа зв'язку це складнасистема більш високого ієрархічного рівня порівняно з окремою системою зв'язку,математичні моделі якої розглядалися у попередніх підрозділах.
Структура мережі, тобто їїтопологія, визначається сукупністю пунктів (кінцевих і вузлів комутації) таканалів (ліній) зв'язку, що їх з’єднують. Призначення мережі полягає упередаванні повідомлень від джерел до споживачів інформації.
Характерним для мережі зв'язкує значна кількість джерел та споживачів інформації, а також можливих маршрутівпередавання повідомлень.
Тому важливим для мережі єуправління процесами передавання повідомлень із оптимальними показниками якості. Модель мережі зв'язку визначаєтьсяматематичним описом структури мережі,а також процесів надходження заявок до кінцевих пунктів та процесів їхобслуговування у мережі. Облуговування включає процеси розподілу інформації увузлах комутації та процеси доставки повідомлень до споживачів визначеними маршрутами.
При цьому через значнукількість заявок, а також обмежені фізичні можливості систем комутації таканалів (ліній) зв'язку мають місцерізні способи обслуговування заявок на вузлах комутації: з втратами (колизаявка одержує відмову на обслуговування), з очікуванням (коли заявка очікуєзвільнення лінії чи комутуючого пристрою), з обмеженим очікуванням (колиобмежено або число заявок, що очікують, або час очікування).
Таким чином, дляматематичного опису мереж зв'язкувикористовують інший математичний аппарат порівняно з описуванням просто системзв'язку, які у згаданій структурімережі часто використовуються для з'єднування різнихвузлів.
1.Математичний опис структури мережізв'язку
Розглянемо особливостіматематичного опису структури мережі зв'язку з використанням мережної математичної моделі.
При цьому як модельвикористовується граф />, де />/> -сукупність вершин графа, які ставляться у відповідність пунктам мережі(кінцевим пунктам, вузлам комутації), а /> -сукупність ребер графа, які ставляться у відповідність лініям, каналам зв'язку.Відповідно до того, що канали зв’язку можуть бутиоднобічними та двобічними, ребра графа можуть бути орієнтованими танеорієнтованими.
Таким чином, як модельмережі зв'язку можуть бути використані орієнтовані, неорієнтовані, мішаніграфи, а також мультиграфи. Мережнімоделі широко використовуються на практиці при проектуванні системелектрозв'язку, систем космічного та радіозв'язку, телетрансляційних мереж,обчислювальних комплексів, транспортних мереж.
Мережний аналіз відіграє всебільше зростаючу роль, тому що задопомогою графів можна досить просто побудувати модель нетільки мережі зв’язку, але й іншихскладних системи.
Розширення сферивикористання мережної моделіпов'язане з тим, що методи мережногоаналізу дають можливість: побудуватимодель складної системи як сукупність простих; скласти формально процедури длявизначення якісних та кількісних характеристик системи; показати механізмвзаємодії компонентів системи з метою опису останньої в термінах її основних характеристик; визначити, якідані необхідні для дослідження системи.
При побудові моделей мережзручно користуватися алгебраїчним зображенням графів, щовизначається топологічними матрицями та матрицями характеристик ребер графа(гілок мережі).
Топологічні матриця, що визначає структуру мережі, може задаватисяу вигляді матриці суміжності та структурної матриці. Матриця суміжності(сполучення) графа /> - це квадратнаматриця /> розміру /> (/> - кількістьвершин графа). Вона визначаться таким чином:
/> (1)
Елементи головної діагоналіматриці /> звичайно покладають рівними нулеві />, за винятком випадків,коли в деяких вершинах є «петлі». Матриця /> дляopiєнтoванro графа несиметричнавідносно головної діагоналі, симетричною вона буде лише для нeopiєнтованoго графа.
Структурна матрицявикористовується для спрощення запису структури мережі, коли ребрам графаприсвоюються спеціальні позначення, наприклад, />.
Ці позначеннявикористовуються як елементи структурної матриці. Структурна матриця графа /> це — квадратна матрицярозміру />, яка визначається так:
/> (2)
Kpiмрозглянутих топологічних матриць, можутьбути використані матриці інциденцій «вершини-дуги»,«дуги-дуги».
Матриця кількісниххарактеристик ребер графа використовується для різних кількісних оцінок мережі.При цьому кожному ребру графа приписується певна вага — число, яке характеризує яку-небудь властивістъ даного ребра,наприклад, довжину, вартість,пропускну здатність, канальну ємність, час передачі іформації, надійність тощо.
Зазначені характеристикиребер графа подаються у формі відповідних квадратних матриць розміру /> - довжин, вартостей. Якщо /> - неорієнтований граф, то yсі матриці симетричні відносно головноїдіагоналі.
Наприклад, для побудовиматриці довжин шляхів /> користуютьсятаким правилом:
/> (3)
Матрицю канальних ємностейребер /> отримують за правилом:
/> (4)
Аналогічно отримують і іншіматриці характеристик ребер графа. Вказані характеристики мережі можуть бути використані при розв’язанні різних задач синтезута аналізу мереж зв'язку, зокрема,для пошуку оптимальних шляхів передавання повідомлень.
Оскільки призначення мережізв'язку полягає у тому, щоб надавати абонентам з'єднувальні шляхи для передавання повідомлень відповідно до адреси та заданих показників якості, тому необхідноздійснювати оптимальний вибір з'єднувальних шляхів.
При цьому має здійснюватисявибір таких шляхів, щоб забезпечити найефективніше використанняобладнання мережі, або забезпечити мінімально можливі довжину шляхів та кількість транзитних ділянок у шляхах, абозабезпечити необхідну кількість каналів у шляхах чи максимальну швидкістьпередавання.
Так, при розв'язанні задач проектування мереж зв'язку виникає необхідністьу пошуку множини шляхів, які існують між заданою парою вузлів зв'язку (вершинграфа).
Bcі методипошуку множини шляхів у мережі можнаподілити на два класи: матричні та мережні. Матричні методи грунтуються наперетворенні різних матриць — топологічних чи матриць характеристик реберграфа, а мережні методи — на присвоєнні вершинам графа позначень, щоназиваються позначками (чи індексами).
Мережні методи визначеннямножини шляхів між заданими вузлами мережі є графічним еквівалентом матричних методів. Визначення множини шляхів базуєтьсяна побудові дерева шляхів із фіксованої вершини-витоку (кореня дерева) до рештивершин-стоків графа.
2.Математичні моделі потоків заявок та процесів обслуговування у мережах зв'язку
мережазв'язок математичний заявка
Окрім структури, математичнамодель мережі зв'язку повинна описувати потоки заявок та їх обслуговування умережі. Ці процеси мають стохастичний характер. Розглянемо їх математичнімоделі, що будуються на основі теорії випадкових процесів та теорії масовогообслуговування.
Основні характеристикивипадкових потоків заявок. Випадковий потік заявок розглядається якпослідовність випадкових величин, яка може бути задана різними способами,зокрема у вигляді:
— послідовності випадковихмоментів часу появи заявки />;
-послідовністю випадковихінтервалів часу між заявками
/>;
-послідовністю випадковихчисел />, що визначають кількістьзаявок на заданих інтервалах часу />.
При перших двох способахзадання потік заявок розглядається як випадковий точковий процес, а притретьому — як випадковий цілочисельний процес /> ізпочатковим значенням />.
Імовірнісний опис такихвипадкових процесів використовує такі характеристики: закон розподілу абовідповідну щільність ймовірності моментів часу появи заявок чи інтервалів часуміж заявками, а також закон розподілу кількості заявок на заданих інтервалахчасу.
В залежності відвластивостей цих характеристик розглядаються різні типи потоку заявок:ординарний та неординарний, стаціонарний та нестаціонарний, без післядії та зпіслядією.
Зокрема, для стаціонарногопотоку закон розподілу кількості заявок не залежить від початкового моментучасу. Ординарність означає неможливість одночасного надходження двох і більшезаявок. Відсутність післядії означає взаємну незалежність кількостей появизаявок на інтервалах часу, що не перекриваються.
Кількісний опис заявоквикористовує три основні характеристики:
- провідну функцію потоку, що являє собою середнюкількість заявок за інтервал часу />;
- інтенсивність потоку, що являє собою середнюкількість заявок за одиницю часу;
- параметр потоку, що визначається імовірністю появихоча б однієї завки на малому інтервалі часу /> (/>).
Однорідний стаціонарнийпотік без післядії називається найпростішим потоком. Інтервали часу міжзаявками в ньому є незалежними випадковими величинами з показниковим розподілом,для якого щільність ймовірності має вигляд
/>, (5)
де /> — параметр потоку.
Найпростіший потік заявокназивається також пуасоновим, бо кількість заявок /> наінтервалі часу тривалістю /> розподіленаза законом Пуасона
/> (6)
При застосуванні донайпростішого потоку з параметром /> операціїпроріджування (вилучення із нього частини заявок), одержується рекурентнийпотік з відновленням. Якщо при цьому /> заявокпідряд втрачається, а залишається тільки кожна />,то проріджений потік має параметр /> тащільність ймовірності для інтервалів часу між заявками
/> (7)
Такий розподіл носить назвурозподілу Ерланга />-го порядку, авідповідні потоки називаються ерлангівськими. За допомогою розподілу Ерланга єможливість опису широкого класу потоків — від найпростішого (при />) до детермінованого зпостійною тривалістю інтервалів між заявками (при />).
Основні характеристикисистем масового обслуговування з втратами. Дисципліною обслуговування з явнимивтратами називається така, при якій заявка, що надходить у систему, отримавши відмовув обслуговуванні, покидає систему.
При обслуговуванні потокузаявок системою кожна з них займає обслуговуючий прилад (канал зв’язку) надеякий інтервал часу. Для систем розподілу інформації як одного із класівсистем масового обслуговування важливе значення має сумарний час зайняттяканалів при обслуговуванні заявок.
Тому дослідження цих системпроводиться на основі сумарного часу обслуговування заявок, що називаєтьсянавантаженням. Як правило, розрізняють навантаження, що обслуговується, щонадходить і що втрачається.
Навантаження />, що обслуговуєтьсясистемою за інтервал часу /> являєсобою сумарний час зайняття всіх каналів системи обслуговування потоку заявок,які надходять на її входи за цей інтервал часу
/>, (8)
де /> - сума інтервалів часу,протягом яких /> - й канал бувзайнятий обслуговуванням на інтервалі часу />;/> — кількість каналівобслуговування.
Під інтенсивністюнавантаження розуміється навантаження за одиницю часу. Інтенсивністьнавантаження, що обслуговується, при заданій якості обслуговування характеризуєпропускну здатність системи розподілу інформації.
Кількісно вона оцінюєтьсявеличиною середньої пропускної здатності або середнього часу використанняодного каналу
/> (9)
Під навантаженням />, що надходить у систему заінтервал часу />, розумієтьсятаке навантаження, яке може бути обслужене нею за цей інтервал в умовахнегайного надання обслуговування кожній заявці, яка надходить.
Навантаження />, що втрачається системоюпротягом інтервалу часу />, являєсобою різницю між навантаженнями /> та />.
Для кількісної оцінки якостіобслуговування з втратами на інтервалі /> використовуютьсятакі характеристики: втрати за часом, як частина часу на цьому інтервалі,протягом якого всі доступні канали системи зайняті обслуговуванням; втрати зазаявками, як відношення числа втрачених за цей відрізок часу заявок дозагальної кількості заявок, що надійшли до системи; втрати за навантаженням, яквідношення навантаження, що втрачається, до навантаження, що надходить за тойже інтервал часу.
Стани системи обслуговування/> визначаються кількістюзаявок, які знаходяться у системі на обслуговуванні. Для дисципліниобслуговування з втратами ця кількість збігається з кількістю зайнятих каналівсистеми.
При цьому процесобслуговування системою заявок /> можеприймати різні значення в залежності від стану системи: стан />, коли вільні всі /> каналів; стан />, коли зайнятий один канал,а інші вільні; стан />, коли зайнято /> каналів, а інші вільні; />, коли зайняті всі /> каналів.
В разі найпростішого потокузаявок з параметром /> і показниковим розподіломтривалості обслуговування з функцією розподілу /> фінальніймовірності вказаних станів системи /> визначаютьсяпершою формулою Ерланга
/>, (10)
де /> - інтенсивністьнавантаження, що надходить.
Динаміка станів системи обслуговуванняз втратами для найпростішого або примітивного потоку та показниковорозподіленої тривалості обслуговування описується дискретними марківськимипроцесами народження та загибелі.
При їх імітаційномумоделюванні на ЕОМ використовуються ланцюги Маркова із />-м станом />, що створюються наінтервалі часу спостереження у вигляді послідовності відліків у моменти часу />. У цих ланцюгахрозглядаються переходи між станами через одиничні моменти часу.
Аналогічно на основі теоріїмасового обслуговування будуються математичні моделі складніших системобслуговування з очікуванням. Дисципліною обслуговування з очікуванням називаєтьсятака, при якій заявка, що надходить у систему за відсутністю вільнихобслуговуючих приладів (каналів), не втрачається, а ставиться до черги,очікуючи звільнення будь якого з них.
Наряду із показникамизавантаження каналів система обслуговування з очікуванням додатково описуєтьсятакими характеристиками: ймовірність умовних втрат за часом, яка визначаєтьсясередньою часткою часу, коли всі канали зайняті обслуговуванням; ймовірністьзатримки (очікування початку обслуговування) заявки понад заданий час; середнійчас очікування обслуговування; ймовірність того, що довжина черги перевищитьзадану величину; середня довжина черги.
Процес обслуговуванняописується випадковим процесом, що приймає дикретні значення і визначаєтьсякількістю заявок, які присутні у системі обслуговування.
При цьому характерні такістани системи: стан />, коли вільні всі/> каналів; стан />, коли зайнятий один канал,а інші вільні; стан />, коли зайнято /> каналів, а інші вільні;стан />, коли зайняті всі /> каналів; стан />, коли зайняті всі /> каналів та одна заявкастоїть у черзі; стан />, коли зайнятівсі /> каналів та /> заявок стоїть у черзі.
Довжина черги будескінченною, якщо інтенсивність навантаження, що надходить, буде меншою закількість каналів обслуговування у системі. Динаміка станів системиобслуговування з чергами описується дикретними марківськими процесами, зокремаланцюгами Маркова.