Томський державний університет
Факультет прикладної математики і кібернетики
Кафедра теорії ймовірності та математичної статистики
ДОПУСТИТИ ДО ЗАХИСТУ В
ДАК
Зав. каф. ТВ і МС, д-р тих. наук, професор
____________
В«__В» ________ 2002р.
асимптотичних методів ДОСЛІДЖЕННЯ НЕСТАЦІОНАРНИХ РЕЖИМІВ У МЕРЕЖАХ ВИПАДКОВОГО ДОСТУПУ
(Дипломна робота)
Науковий керівник
д-р тех. наук, професор
__________
Автор роботи
__________
Томськ 2002
Зміст
3
1. Дослідження нестаціонарної мережі випадкового доступу з динамічним протоколом в умовах великого завантаження ................. 6
2. Дослідження неоднорідною нестационарной мережі випадкового
доступу з динамічним протоколом в умовах перевантаження ............ 19
3. Дослідження нестаціонарної мережі випадкового доступу з
статичним протоколом в умовах великої затримки .................. 28
4. Дослідження стаціонарного режиму в мережі з динамічним протоколом випадкового множинного доступу для кінцевого
числа станцій ...................................................................... 41
4.1. Асимптотичний аналіз розподілу ймовірностей станів мережі ............................................................................ 45
4.2. Чисельний метод аналізу розподілу ймовірностей .......... 52
4.3. Визначення області застосовності асимптотичних формул 55
60
Список використаної літератури .................................................. 62
Введення
Останнім часом у багатьох областях виробництва виникає необхідність використання процесів розподіленої обробки інформації, причому на самих різних рівнях: від окремої установи до цілої мережі підприємств, охоплює величезні відстані. Тому цілком природно спостережуване нині бурхливий розвиток мереж зв'язку, що дозволяють з'єднувати в єдині системи різні пристрої обчислювальної техніки. При цьому наукові дослідження, спрямовані на поліпшення функціонування мереж, ведуться в двох напрямках: підвищення фізичних характеристик каналу передачі і створення ефективних мережевих протоколів, що дозволяють використовувати фізичні можливості каналу оптимальним чином.
При оптимізації і проектуванні мереж передачі даних найбільш дієвим інструментом є використання математичного моделювання. Для того щоб дослідити вже існуючі мережі зв'язку фахівці по мережах використовують різні аналізатори протоколів, але такі методи не дозволяють отримувати імовірнісно-часові характеристики для ще не існуючих мереж, знаходяться на стадії проектування. У цих випадках необхідно використовувати засоби моделювання, за допомогою яких розробляються адекватні моделі, описують процеси, що протікають в мережах, і проводиться всебічний аналіз цих процесів.
Дослідження поведінки систем зв'язку через випадкових впливів можливо тільки за допомогою випадкових процесів [1]. Вибір випадкових процесів, використовуваних для опису й аналізу систем, залежить від структури та типу системи, від припущень про незалежність чи залежності випадкових величин, від виду їх функцій розподілу. Тому для дослідження таких систем часто використовується апарат теорії масового обслуговування [2]. Використання цього апарату дозволяє побудувати математичні моделі досліджуваної мережі зв'язку [3] та провести теоретичні дослідження параметрів функціонування реальної системи.
У класичній літературі розрізняють два основні класи систем масового обслуговування [2]: системи з втратами (без черги) і системи з очікуваннями, а також комбінація цих двох типів - система з очікуванням і втратами (наприклад, система з обмеженим числом місць для очікування в бункері) [4]. Математичні моделі супутникових мереж зв'язку з протоколами випадкового множинного доступу формують третій клас СМО - системи з повторними викликами. Розвиток мереж з множинним доступом почалося з появи роботи Абрамсона, в якій описано функціонування територіально-розподілених терміналів, з'єднаних центральної ЕОМ по радіоканалах. Ця система отримала назву ALOHA. Особливістю протоколів множинного доступу є те, що на безлічі станцій не вводиться початкової суворої черговості. Кожна станція після появи у неї готового пакету вправі його передавати відразу ж, як тільки виявить канал вільним. При цьому не виключена можливість, що вона потрапить у конфлікт, то є її пакет зіткнеться з пакетом іншої станції. У подібних випадках станція припиняє передачу і генерує випадкову затримку, після якої знову намагається зайняти канал.
Асимптотичні методи [5] відіграють важливу роль при дослідженні різних математичних моделей, у тому числі таких, якими описується функціонування різних типів систем масового обслуговування. Точні формули для рішень вдається отримати, як правило, лише у виняткових ситуаціях, що характеризуються накладенням обмежень на статистичну природу процесів, керуючих системою (такими звичайно є вхідний потік вимог і процес обслуговування). Однак часто, застосовуючи різні асимптотичні методи можна отримати задовільний для практики наближене (асимптотичне) рішення задачі при вельми широких припущеннях щодо входу та обслуговування навіть при відсутності явного виду розподілів характеристик.
Говорячи про асимптотичних методах, асимптотичному вирішенні і т. д., ми припускаємо, що досліджувана система (або досліджуваний процес, пов'язаний з функціонуванням системи) характеризується наявністю (одного або декількох) параметра s , що має певний фізичний зміст, значення якого близько до деякого В«КритичногоВ» значенням. В кожному конкретному випадку параметр s , його граничне значення і характер наближення s до мають цілком певний сенс, який випливає з постановки завдання. Часто таким параметром вважають час t , і нас цікавить поведінка тих чи інших характеристик СМО в достатньо віддалений від початку моменту функціонування системи момент часу. У СМО істотне значення має поведінка завантаження системи, особливо коли завантаження прагне до критичної. Асимптотичний метод застосовується, якщо інтенсивність повторення заявки в системах з повторними викликами прагне до нулю. У всіх випадках можна знайти асимптотичну щільність розподілу ймовірностей основних стохастичних параметрів, що обумовлюють функціонування досліджуваної системи.
В якості граничних процесів в теорії масового обслуговування частіше інших виникають дифузійні марківські процеси [6].
Запропонований метод аналізу марковізіруемих систем [7] зазвичай має два етапи. На першому етапі вдається визначити асимптотичне середнє досліджуваних характеристик системи, а на другому - розподіл ймовірностей значень відхилень розглянутих характеристик від їх асимптотичних середніх.
1. Дослідження нестаціонарної мережі випадкового доступу з динамічним протоколом в умовах великого завантаження
Розглянемо супутникову мережу зв'язку, керовану динамічним протоколом випадкового множинного доступу з оповіщенням про конфлікт. Архітектура такої мережі складається з великої кількості територіально-розподілених абонентських станцій (АС), які передають повідомлення через геостаціонарний супутник-ретранслятор. Так як супутниковий канал зв'язку спільно використовують всі АС, то можливо збіг часу ретрансляції повідомлень від двох або більше АС, при цьому повідомлення спотворюються і вимагають повторної передачі. Така ситуація називається конфліктом. Передбачається, що супутник-ретранслятор має можливість виявлення виникаючих конфліктів і реалізації сигналу оповіщення. Абонентські станції здатні сприймати (ідентифікувати) сигнал оповіщення про конфлікт, так, щоб в кожній АС після заданого часу поширення сиг...
