Процедури керування множинним доступом до каналу з паралельною пакетною обробкою

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Вступ

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

Існуючі системи множинного доступу Multiple access (МА) мають обмеження на кількість вимог, що одночасно обслуговуються, порушення якого породжує конфлікти. Так саме наявність конфліктів у системах зв'язку з кодовим поділом каналу (CDMA) призводить до того, що ефективність використання робочої смуги частот є низькою. Тому пропонується оптимізувати їхню роботу за рахунок механізмів, що реалізовані в процедурах впорядкування множинного доступу одного з альтернативних напрямків часового поділу (TDMA). Аналізу систем на основі цих протоколів присвячені класичні дослідження Ерланга, Клейнрока та Тобаги. Напрямки сучасних досліджень відображають роботи Цибакова, Михайлова, Буніна, Войтера.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пропонуються відповідні протоколи множинного доступу.

Процедура керування множинним доступом організує процес інформаційної взаємодії у системі , де множина вузлів (абонентів) системи, а обслуговуючий пристрій (ретранслятор), з метою перетворення інформаційного потоку Р1 у потік Р2.

Алгоритм А, що реалізує процедуру розподілу, задає відображення:

. (1)

При відсутності додаткових обмежень, алгоритм А визначається наступними факторами:

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

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

Характером інформації щодо вхідного потоку.

Для обґрунтування доцільності використання в системах зв'язку з СDMA протоколів множинного доступу, що здійснюють розподіл часу, розглядається множина 1 протоколів, що реалізовані в системах зв'язку із простими сигналами, тобто з k = 1. З точки зору системного аналізу, задача полягає у відшуканні в множині всіх можливих протоколів цього класу 1 1 такого протоколу, під час реалізації якого величина пропускної здатності системи, буде максимальною в порівнянні з відповідними величинами, що можуть бути отримані при реалізації всіх інших протоколів:

. (2)

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

. (3)

Визначається клас протоколів, кожен з яких модифікує деякий з існуючих протоколів ТDMA, для використання в системах зв'язку із складними сигналами (k 1):

. (4)

Для протоколів класу k можна припустити справедливість наступних умов:

1. Для кожного протоколу класу 1 відповідний йому протокол класу k має кращу пропускну здатність:

. (5)

2. Будьякий протокол класу k забезпечує значення пропускної здатності, що перевищує ефективність передачі в системі СDMA без розподілу часу.

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

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

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

синхронний протокол МДСЗ,

асинхронний протокол МДСЗ,

асинхронний протокол МДСЗ із розв'язанням конфліктів,

протокол із резервуванням.

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

Формулюються та доводяться наступні твердження :

Твердження 1. Тривалість фінальної фази обмежена зверху числом 2+2а.

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

. (6)

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

. (7)

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

3. Дослідження ефективності систем з паралельною обробкою на основі запропонованих протоколів керування

Для цього визначається середня швидкість передач фінальної фази в каналі:

,

де NF середнє число успішних передач, а ТF середня тривалість фінальної фази циклу, а далі SР середня швидкість передач, що досягається в початковій фазі. Cередня швидкість передач повного циклу з урахуванням довжини початкової фази ТР, визначається рівнянням:

, (8)

де Т, повна тривалість циклу, задовольняє умові (5).

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

Для простих асинхронних та синхронних протоколів МДСЗ середнє число успішних передач у фінальній фазі не повинно перевищувати k. Єдина відмінність полягає в умові успішності передач поточного циклу. В синхронному протоколі після приходу (k1) го пакету, коли настає інтервал вразливості, причиною конфлікту можуть стати тільки ті пакети, що надходять в першій його половині, тому інтервал вразливості, по суті, зменшується в два рази. Середнє число успішних передач фінальної фази в асинхронному та синхронному протоколах дорівнює, відповідно:

 (9)

. (10)

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

, (11)

. (12)

Середня тривалість фінальної фази задається сумою:

в асинхронному протоколі , (13)

в синхронному протоколі . (14)

Остаточні формули для середньої швидкості передач в асинхронному та синхронному протоколах:

 (15)

. (16)

При знаходженні пропускної здатності каналу у фінальній фазі циклу для асинхронного протоколу МДСЗ із процедурою вирішення конфліктів враховується додаткова кількість передач, що реалізуються у фазі розв'язку конфліктів N1, та тривалість фази.

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

, (17)

, (18)

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

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

. (19)

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

. (20)

Момент TL приходу останньої в кожному з одиничних відрізків, що розглядаються, і не більш ніж kї за номером вимоги, вже було знайдено в (11) та (12), отже:

. (21)

Для асинхронного та синхронного протоколів вираз (21 ) прийме вигляд:

(22)

, (23)

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

Пропускна здатність у системах із резервуванням знаходиться для повного циклу роботи, оскільки він, за визначенням, має скінчену тривалість. Успішна передача основних пакетів відбувається в двох випадках : якщо число i резервуючих пакетів, які надійшли, не перевищує k, тоді число передач в циклі дорівнює i; або передача основних пакетів відбувається аналогічно фазі розв'язку конфліктів в МДСЗ із ПРК. Середнє по всім i значення числа передач, які реалізовані в основному кадрі, дорівнює:

(24)

Середній час повного циклу:

,

де ТR визначається як середнє число черговостей в інтервалі передачі даних:

. (25)

отриманий вираз дає рекурентну залежність для знаходження середньої тривалості nго циклу. При обчисленні значення Тn розглядалася Nа скінчена сума TR, де:

, (26)

та припустима похибка при обчисленні TR, приймалась рівною 0,05. Ітераційний процес для знаходження TR є збіжним для довільного початкового значення Т0 із відрізка [а, [G/к]+1]. Таким чином, отриманий вираз середньої швидкості передач у циклі:

може бути обчислений для будьякого заданого значення інтенсивності трафіку G. Результати обчислень для випадків, коли допустимою є одночасна передача k = 3 та k = 5 пакетів, довжина інтервалу резервування = 0.1, а тривалість захисного інтервалу.

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

4. Розгляд системи, що реалізує визначені протоколом процедури, з точки зору масового обслуговування

Визначаються параметри моделі масового обслуговування для систем зв'язку, робота яких основана на використанні раніш описаних протоколів.

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

Тривалість обслуговування.

Для систем із синхронним та асинхронним протоколами МДСЗ, процедура обслуговування займає однаковий для всіх вимог час. Тобто, тривалість обслуговування має детермінований характер D.

Для протоколів резервування та МДСЗ із ПРК описана тривалість обслуговування залежить від його дисципліни та кількості учасників конфлікту. Тобто, тривалість обслуговування має довільний розподіл G.

Кількість обслуговуючих приладів. З врахуванням можливості паралельної обробки вимог в системах CDMA, навіть коли система має в розпорядженні один реальний обслуговуючий пристрій (ретранслятор), пропонується розглядати модель з k конфліктно залежними обслуговуючими приладами. Поки кількість заявок не перевищує k, кожна вимога обслуговується незалежно, як у ситуації обробки її окремим приладом. Але, під час конфлікту, поведінка системи направлена на його централізоване вирішення (протоколи резервування та МДСЗ із ПРК), або на запобігання його повторного виникнення (синхронний та асинхронний протоколи МДСЗ), тому обслуговування в кожному з віртуальних приладів підкоряється загальній дисципліні.

Затримка. Системи, що розглядаються, є системами з очікуванням. Його тривалість - випадкова величина, яка залежить від механізму здійснення затримки. Цей механізм є спільним для всіх протоколів МДСЗ, які ми розглядаємо. Він використовується для того, щоб зменшити ймовірність втрати пакетів, які надходять у систему в момент зайнятості каналу або поточного конфлікту, або пошкоджуються при виникненні конфлікту після їхньої передачі. Затримка є випадковою величиною з експоненціальним розподілом Р{ < 1 + t} = 1e- t із середнім значенням 1+1/.

Отже, розглядаються моделі масового обслуговування M/D/k (M/D/k/) для систем з синхронним та асинхронним протоколами МДСЗ, та M/G/k для систем МДСЗ із ПРК й систем із резервуванням (k вказує максимально допустиме число вимог, які обслуговуються одночасно).

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

Стан систем обслуговування на основі запропонованих протоколів МДСЗ у деякий момент часу повністю визначається парою [M, N], де N число вимог, що обслуговуються системою в цей момент часу, а M кількість відкладених пакетів.

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

,

,

, , (28)

де:

.

.

ймовірність приходу вимог, які раніш не передавалися, та повторного надходження вимог, які були відкладені раніш, відповідно. Для визначення стаціонарних ймовірностей записано систему різностних рівнянь, що зв'язує ймовірності в моменти часу t та t+ h. Якщо , отримаємо в лівій частині рівнянь похідні ймовірностей станів , в стаціонарному режимі вони обертаються в нуль, що дозволяє отримати систему однорідних рівнянь для знаходження стаціонарних імовірностей:

, (29)

де параметри системи:

, .

Аналітичний розв'язок отриманої нелінійної нескінченновимірної однорідної системи рівнянь не виглядає можливим, тому, вважаючи m та S параметрами, розглядаємо ітераційний процес, який задано системою. При наявності стаціонарного розв'язку він має бути збіжним.

При проведенні чисельного аналізу моделі для k =1 було розглянуто скінченну кількість рівнянь системи. Отримано залежність середньої кількості відкладених пакетів від трафіка. Її вигляд свідчить про те, що зростання заборгованості зі збільшенням трафіка обмежено зверху лише числом відкладених пакетів, котрі розглядаються. Вказаний результат є наслідком обрізання системи рівнянь. При збільшенні максимального числа відкладених пакетів, що розглядаємо характер графіків не змінюється, що дозволяє припустити наявність необмеженого зростання заборгованості.

Твердження 3. У випадку k = 1 виконується: .

Відомі аналогічні результати, що отримані з аналізу стійкості синхронної Aloha. Стійкість має місце лише за умов "відсутності буферізації". Тобто в припущенні, що кожний новий пакет, котрий з'являється у абонента, перша вимога якого досі знаходиться у системі, втрачається. При цьому існує точка стійкої рівноваги системи, тобто значення трафіку, при якому швидкість виходу вимог з системи співпадає із швидкістю їхнього надходження в систему. Розглянута в роботі модель включає припущення "про нескінченну кількість абонентів". Вважається, що кожний новий пакет, котрий надходить до вузла зі старим пакетом, що не залишив систему, належить новому, віртуальному вузлу. Як відомо, для системи Aloha це спричиняє втрату стійкості, стан заборгованості необмежено зростає. У випадку, що розглядається в роботі, стійкість також відсутня, про що свідчить твердження 3.

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

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

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

, (30)

де події tij відповідає ймовірність:

.

Середній час перебування вимоги в системі W є зваженою сумою:

.

Ймовірності подій зайнятості каналу, успішної передачі та конфлікту є відповідно:

,

та:

.

Отже, отримано середній час перебування вимоги в системі у вигляді:

(31)

Аналогічним чином виконується аналіз синхронного протоколу МДСЗ та протоколу з розв'язанням конфліктів. Вирази середньої тривалості перебування вимоги у системі для них є відповідно:

(32)

. (33)

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

. (34)

В наслідок детермінованого характеру обслуговування, його тривалість TS є постійною для протоколу, що розглядається, величиною. Тому з отриманої величини W знаходимо затримку очікування TQ = WTS, відтак (застосовуючи теорему Літла) середню кількість вимог, що перебувають у системі N =W та очікують обслуговування NQ =TQ.

Таким чином, при значеннях трафіка близьких до k , оптимальним вибором є протоколи МДСЗ, для менших значень МДСЗ с ПРК.

множинний пакетний ретранслятор

Висновки

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

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

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

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

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

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

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

Література

Бунин С.Г., Гонтаренко И.С., Смирнов С.А. Исследование гибкого протокола множественного доступа с контролем несущей для пакетных сетей связи с шумоподобными сигналами // Проблемы управления и информатики. - 2000. -№ 5. - С. 119-123.

Бунин С.Г., Гонтаренко И.С. Разрешение конфликтов в гибком протоколе множественного доступа для широкополосных систем передачи данных // Управляющие системы и машины. - 2000. -№ 5/6. - С. 108-112.

Гонтаренко И.С., Смирнов С.А. Оценка производительности гибкого протокола множественного доступа в пакетных сетях связи с использованием ШПС // Міжнародна конференція з автоматичного управління “Автоматика - 2000”, Львів, 11-15 вересня 2000: - Праці в 7 томах. - Т 3. - С. 107.

Гонтаренко И.С., Механизм резервирования на основе шумоподобных сигналов в системах спутниковой связи // Проблемы управления и информатики. - 2001. -№ 4. - С. 95-100.

Мульгина И.С., Самойленко Ю.И., Смирнов С.А. Группы Галуа полиномов и аналитические формулы для корней // 3-я Украинская конференция по автоматическому управлению “Автоматика-96”, - Севастополь, - 1996, - Праці, - Т.1. - С. 73.

Размещено на Allbest.ru

...