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

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

Рубрика Программирование, компьютеры и кибернетика
Вид автореферат
Язык украинский
Дата добавления 27.08.2015
Размер файла 87,9 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

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

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

Дослідження моделей процесів обслуговування викликів у мережах стільникового зв'язку
Автореферат
дисертації на здобуття наукового ступеня кандидата технічних наук
Загальна характеристика роботи
Актуальність теми дослідження. На рубежі ХХ - ХХІ століть почалася і продовжується конвергенція телекомунікаційних, комп'ютерних та інформаційних технологій, а також взаємне проникнення і злиття відповідних галузей промисловості та сегментів ринку. Все це дозволило значно збільшити продуктивність і пропускну спроможність всіх видів мереж і створити багато нових видів послуг. Відбулося різке підвищення попиту на надання інтегральних послуг - передача мови, даних, зображень, мультимедійної інформації - у межах однієї мультисервісної мережі зв'язку.
Інтернет і GSM (глобальна система мобільного зв'язку) є найяскравішими представниками другого, а UMTS (універсальна мобільна телекомунікаційна система) - третього покоління мультисервісних технологій.
Мультисервісна мережа надає інтегральні послуги, які суттєво відрізняються за складом і величиною потрібних для них мережевих ресурсів, особливо з використання ширини смуги пропускання (ШСП) лінії зв'язку. Наприклад, користувач може запросити трансляцію телевізійного каналу (велика ШСП), потім - доставку веб-документа або телефонне з'єднання (невелика ШСП).
Користувач породжує робоче навантаження, що складається із запитів на різні послуги, для виконання яких потрібне одночасне надання кількох сітьових ресурсів, кількість і пропускна спроможність котрих завжди обмежені. Тому виникають затримки, а також відмови у наданні послуги користувачеві. Це може потягнути за собою як погіршення стандартної договірної якості обслуговування для користувачів, так і втрату потенційного прибутку для операторів мережі.
При проектуванні, модернізації, розвитку й експлуатації мережі постійно виникають складні задачі оптимізації структури мережі та застосованих алгоритмів керування, а також прогнозу продуктивності мережі й оцінки якості обслуговування для послуг різних видів. Для кількісних відповідей на ці запитання з урахуванням вартісних параметрів застосовуються методи низки математичних дисциплін - теорії масового обслуговування (ТМО) або, як говорять в англомовних країнах, теорії черг; комбінаторики і теорії графів; дослідження операцій та інших. Широко застосовуються числові методи та імітаційне моделювання, створені й доступні багато спеціалізованих пакетів прикладних програм. ТМО органічно доповнюється математичною теорією телетрафіку, що зародилася на початку ХХ сторіччя у середовищі телефонних компаній і переживає зараз новий етап розвитку й адаптації до сучасних запитів інженерної практики. Поняття «телетрафік» розуміють зараз не тільки як класичні телефонні й телеграфні повідомлення, але й як потоки повідомлень у нових інформаційно-обчислювальних і телекомунікаційних мережах.
Зараз ми спостерігаємо період експоненціального зростання кількості абонентів стільникових мереж, яка вже перевищила кількість стаціонарних телефонів. При цьому дуже важливо, що приблизно третина абонентів мереж стільникового мобільного зв'язку (МСМЗ) живе у сільській місцевості, де з урахуванням протяжності території суцільна стаціонарна телефонізація є особливо складною. Розвиток МСМЗ ставить перед теорією телетрафіку, яка розвивалася раніше під впливом запитів дротового зв'язку, багато нових цікавих і складних завдань. Традиційні задачі телетрафіку - обчислення ймовірностей блокування та інших характеристик якості обслуговування - розв'язуються за допомогою математичної моделі стільника, кластера і більш складних фрагментів МСМЗ. Разом із стандартними підходами і методиками теорії телетрафіку в нових моделях виникає потреба враховувати низку особливостей мобільних радіосистем, зокрема такого явища, як хендовер (handover, handoff), тобто процедури переходу мобільного користувача (МК) із каналу даного стільника у канал сусіднього стільника, причому виклик, який породжує цю процедуру, називається h-викликом, на відміну від нового виклику, який називається о-викликом. Для розв'язання можливих конфліктних ситуацій, які виникають в процесі обслуговування h-викликів і о-викликів, залучаються методи пріоритетних систем масового обслуговування (СМО) і систем підтримки прийняття рішень (СППР).
Різні аспекти проблеми, яка досліджується, висвітлювалися у наукових працях вітчизняних і зарубіжних учених H. Akimaru, А. Andreadis, В.В. Афанасьева, Г.П. Башаріна, В.Е. Бенеша, Л.Н. Беркман, П.П. Бочарова, В.М. Вишневського, Б.М. Герасимова, Ю.М. Горностаева, В.І. Гостєва, О.В. Гофайзена, G. Giambene, R. Guerin, В.А. Ершова, О.Ю. Зайченко, Ю.П. Зайченка, D. Hong, V.B. Iversen, T. Janevski, В.С. Лагутіна, В.М. Локазюка, Y.-B. Lin, К. Каwashima, I. Chlamatac, Л. Клейнрока, J. Korhonen, Ю.Н. Корнишева, Б.П. Креденцера, Н.А. Кузнецова, R. Prasad, А.П. Пшеничникова, S.S. Rapoport, М.В. Ратинського, К.W. Ross, К.Є. Самуйлова, С.Н. Степанова, А.Д. Харкевича, М. Шварца, J. Schiller, М.А. Шнепс-Шнеппе, C.K. Un, C.H. Yoon та багатьох інших.
Водночас, у науковій літературі недостатньо висвітлені інтегровані результати досліджень з проблематики розробки і застосування ефективних числових методів аналізу й оптимізації систем телетрафіку. Найефективніший математичний апарат аналізу розроблено для систем, функціонування яких описується однорідними ланцюгами або процесами Маркова. Намагання досягти максимальної точності опису функціонування реальних складних систем призводить до того, що відповідні математичні моделі стають все складнішими і складнішими. При цьому ускладнюється їх математичний аналіз, апарат такого аналізу стає громіздким і часто недоступним у інженерній практиці. Основні труднощі при моделюванні й аналізі складних телекомунікаційних систем проявляються у непомірному зростанні кількості їх можливих станів, що призводить до практичної неосяжності моделі. Одним із актуальних завдань теорії складних систем, зокрема, відносно нової математичної теорії телетрафіку, є саме переборення цих головних труднощів - великої розмірності фазового простору станів моделі системи. Найрадикальнішим підходом до переборення складності аналізу реальних систем є побудова більш простої укрупненої системи, аналіз якої є більш простим, ніж аналіз реальної системи, а основні характеристики можуть бути прийнятими в якості досить точних оцінок характеристик останньої.
Усе наведене вище обумовлює актуальність проблеми розроблення концептуальних науково-методологічних основ, методів, моделей і алгоритмів аналізу й оптимізації систем телетрафіку за допомогою математичних методів укрупнення станів складних систем, що й визначило мету і головні завдання дослідження. Математичну основу теоретичної частини дисертації складають граничні теореми, розроблені у свій час академіками В.С. Королюком, І.М. Коваленком і професором А.Ф. Турбіним.
Об'єктом дослідження у дисертаційній роботі є процеси обслуговування викликів різних типів в мережах бездротового стільникового зв'язку.
Предметом дослідження є теоретичні, методичні й практичні проблеми оптимізації характеристик процесів обслуговування викликів у мережах стільникового зв'язку.
Зв'язок роботи із науковими програмами, планами, темами. Робота виконувалась відповідно до планів науково-дослідних робіт Державної науково-виробничої корпорації «Київський інститут автоматики» Міністерства промислової політики України стосовно розробки методів ситуаційного пріоритетного обслуговування в СМО та їх використання у виробничих системах, планів підприємств ВАТ «Укртелеком», ВАТ «Фарлеп-Інвест», ТОВ «Астеліт» (ТМ life:)) щодо наукового обґрунтування технічних рішень і організаційних заходів, спрямованих на удосконалення процесів обслуговування клієнтів у бездротових мережах стільникового зв'язку.
Мета і завдання дослідження. Метою роботи є розроблення концептуальних науково-методологічних основ і методичних положень, моделювання, створення та використання систем підтримки прийняття рішень з метою підвищення ефективності процесів обслуговування викликів різного типу в мережах бездротового стільникового зв'язку.
При досягненні мети дослідження була поставлена і розв'язана така сукупність науково-технічних завдань, що мають наукову новизну:
- розробка і порівняльний аналіз схем оптимізації комп'ютерних мереж за методом підсумовування та за алгоритмом згортки;
- розробка наближених методів розрахунку багатовимірних моделей систем телетрафіку на основі алгоритмів фазового укрупнення;
- визначення шляхів застосування марковських процесів прийняття рішень (МППР) у класичній постановці у задачах оптимізації моделей систем телетрафіку;
- розробка ієрархічного алгоритму фазового укрупнення (АФУ) станів системи телетрафіку для застосування МППР при оптимізації систем телетрафіку;
- розробка методів розрахунку й оптимізації характеристик бездротових мереж стільникового зв'язку;
- розробка математичної моделі стільника із резервуванням каналів для хендовер-викликів у мережах без черг;
- розробка математичної моделі стільника із індивідуальними каналами для хендовер-викликів у мережах без черг;
- розробка математичних моделей процесів обслуговування викликів у бездротових мережах із чергами хендовер-викликів;
- розробка математичних моделей процесів обслуговування викликів у бездротових мережах із чергами нових викликів;
- розробка алгоритмів та проведення розрахунку головних характеристик всіх названих вище моделей при різних значенням навантажувальних і структурних параметрів;
- дослідження ефективності розроблених методів і алгоритмів відносно класичних методів розрахунку параметрів моделей телетрафіку.
Методи досліджень. Теоретичні дослідження при розробленні математичних моделей процесів обслуговування викликів у мережах мобільного зв'язку базуються на фундаментальних положеннях кібернетики, дискретної математики, теорії ймовірностей, на наукових працях вітчизняних і зарубіжних фахівців з проблем теорії телетрафіку, складних імовірнісних систем, теорії укрупнення фазового стану систем, пріоритетних систем масового обслуговування. В процесі дослідження використані методи моделювання, системного аналізу, лінійної та нелінійної оптимізації, загальної теорії СППР, інформаційних технологій.
Наукова новизна одержаних результатів полягає у поглибленні існуючих та розробленні нових теоретичних положень щодо підвищення ефективності прийняття рішень при обслуговуванні різнотипних викликів в мережах бездротового стільникового зв'язку, зокрема, особистим внеском здобувача є те, що в ній:
Вперше:
- розроблено ефективний з точки зору надійності та швидкості обчислень наближений метод визначення головних характеристик багатовимірних систем телетрафіку, які описуються моделями оборотних марковських процесів;
- розроблено числовий метод та відповідний алгоритм розрахунку та оптимізації систем телетрафіку, що описуються двовимірними марковськими процесами, які є строго неперервними за першою компонентою та слабко неперервними за другою компонентою;
- досліджена модель ізольованого стільника, в якій прийнята стратегія управління доступом різнотипних викликів в канали базового стільника, заснована на виділенні індивідуальних каналів для хендовер-викликів, із такими узагальненнями: вводиться верхня межа кількості хендовер-викликів у загальній зоні каналів з метою захисту нових викликів від частих втрат;
- виконано порівняльний аналіз різних стратегій управління доступом викликів і визначено області параметрів системи, в яких та чи інша стратегія є найбільш прийнятною з точки зори якості обслуговування;
- розроблено математичні моделі з використанням алгоритмів фазового укрупнення і числові методи розрахунку характеристик моделей базового багатоканального стільника, який містить буфер скінченого розміру для очікування у черзі терплячих чи нетерплячих хендовер-викликів або нових викликів;
Удосконалено:
- методику застосування фазового укрупнення станів керованого ланцюга Маркова для дослідження й реалізації на практиці алгоритмів марковських процесів прийняття рішень;
- ієрархічний наближений алгоритм типу фазового укрупнення, який одночасно використовує принцип декомпозиції та не накладає обмежень на структуру перехідних матриць відповідних керованих ланцюгів Маркова;
- модель процесу обслуговування викликів у бездротових мережах зв'язку зі стратегією доступу викликів, заснованій на резервуванні каналів для хендовер-викликів.
Знайшли подальший розвиток:
- оцінка точності скінченновимірного марковського процесу прийняття рішень із необмеженим горизонтом планування і без дисконтування;
- модель роботи ізольованого стільника бездротової стільникової комунікаційної мережі із N каналами, на які надходять пуасоновські потоки нових викликів і хендовер-викликів, зі стратегією доступу h-викликів лише за наявності хоча б одного вільного каналу, а о-викликів - за наявності не менше g+1 вільних каналів.
Розроблено:
- обчислювальні алгоритми і програми експериментальної реалізації запропонованих стратегій доступу викликів різних типів до телекомунікаційної системи на алгоритмічній мові високого рівня Object Pascal в інтегрованому середовищі розробки Delphi 6.
Обґрунтованість і достовірність наукових положень, висновків і рекомендацій. Наукові положення, висновки і рекомендації дисертації обґрунтовані коректним використанням математичного апарату, успішною програмною реалізацією розроблених алгоритмів та ефективним практичним упровадженням результатів дисертаційних досліджень у практику, яке продемонструвало збіг теоретичних положень із реальними спостереженнями.
Практичне значення отриманих результатів полягає у комплексній прикладній спрямованості теоретичних розробок. Розроблені математичні моделі, методи і алгоритми ґрунтуються на аналізі реальних процесів телетрафіку, вони дозволяють підвищити ефективність і дієвість роботи мереж стільникового мобільного зв'язку (МСМЗ).
Теоретико-концептуальні засади, методологічні та методичні положення, сформульовані у дисертації, є внеском у науково-практичну систему знань щодо методів і принципів керування МСМЗ.
Безпосередню практичну цінність, зокрема, мають розроблені в дисертації інженерні методики визначення тих інтервалів зміни параметрів реальних систем мобільного зв'язку, в яких та чи інша стратегія управління доступом викликів до мережі є найбільш прийнятною з точки зори якості обслуговування, алгоритми і обчислювальні програми реалізації запропонованих в дисертації стратегій обслуговування потоків викликів різного типу.

Апробація результатів дисертаційних досліджень. Основні положення й результати дисертаційної роботи доповідались та обговорювалися на VI міжнародній науково-технічній конференції «Электронные информационные ресурсы: проблемы, формирования, обработки, распространения, защиты и пользования ЭИР-2006» (17 жовтня 2006 р., м. Київ); Науково-практичній конференції «Інноваційно-інвестиційні проблеми розвитку економіки України» (21 грудня 2006 р., м. Київ); Міжнародній науково-технічній конференції «Комп'ютерні системи та мережні технології» (17-19 березня 2008 р., м. Київ), 4-й молодіжній науково-технічній конференції «Современные проблемы радиотехники и телекоммуникаций» (21-25 квітня 2008 р., м. Севастополь), Міжнародній конференції молодих вчених і спеціалістів «Инновационные технологии в проектировании» (10-15 травня 2008 р., м. Пенза, Росія), IV міжнародній науково-практичній конференції «Сучасні проблеми і досягнення в галузі радіотехніки, телекомунікацій та інформаційних технологій» (24-26 вересня 2008 р., м. Запоріжжя), на засіданнях постійно діючого семінару Наукової ради з проблеми «Кібернетика» НАН України «Організація програмного забезпечення АСУ» (2006-2008 рр.), наукових семінарах Інституту математики НАН України під керівництвом академіка НАН України В.С. Королюка (2006, 2007 рр.), а також на семінарах та виробничих нарадах підрозділів ВАТ «Укртелеком», ВАТ «Фарлеп-Інвест», ТОВ «Астеліт» (ТМ life:)), присвячених обговоренню проблем підвищення якості прийому/передачі сигналів, удосконалення організації процесів переходу абонента від стільника до стільника (явище хендовер), а також порядку взаємодії дротових мереж зв'язку із бездротовими.

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

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

Структура та обсяг роботи. Дисертаційна робота містить вступ, чотири розділи, висновки, список використаних літературних джерел на 10 сторінках, що містить 111 найменувань, та додатки на 2 сторінках, де наведені документи щодо практичного використання результатів дисертаційних досліджень.

Основний зміст роботи викладено на 178 сторінках. Робота містить 7 таблиць, 59 рисунків.

Основний зміст роботи

марковський мережа телетрафік бездротовий

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

У першому розділі «Методи розрахунку багатовимірних моделей систем телетрафіку» розглянуто різні аспекти застосування методів і моделей теорії багатопотокових СМО в системах телетрафіку.

Враховуючи те, що адекватним математичним апаратом для побудови аналітичних моделей систем телетрафіку є теорія систем і мереж масового обслуговування (ММО), доцільно використати для аналізу систем телетрафіку досвід, накопичений при дослідженні комп'ютерних мереж. Розглянуті такі задачі оптимізації мереж: 1) Мінімізація вартості системи при заданій пропускній спроможності; 2) Максимізація пропускної спроможності при обмеженні на вартість системи; 3) Мінімізація часу реакції при обмеженні на вартість системи.

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

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

Точні методи розрахунку багатовимірних моделей систем телетрафіку проілюстровані на прикладі розімкнених моделей типу MK|MK|N|0.

На вхід СМО, що містить N 1 каналів, надходить K-вимірний пуасоновський потік заявок першого роду, при цьому i-й потік має параметр i, i = 1,…, K. Функція розподілу (ф.р.) часу обслуговування заявок i-го типу (i-заявок) є експонентою з параметром i. Якщо в момент надходження заявки будь-якого типу в системі є хоча б один вільний канал, то ця заявка приймається на обслуговування. У протилежному випадку заявка, що надійшла, втрачається й надалі не впливає на роботу системи.

Функціонування цієї системи описується K-вимірним ланцюгом Маркова (ЛМ). У стаціонарному режимі стан системи у довільний момент часу відображається вектором n = (n1, n2,, nK), де ni - число i-заявок у системі. Існування стаціонарного режиму випливає зі скінченності й незвідності відповідного ЛМ. Тоді множина всіх можливих станів системи, тобто фазовий простір станів (ФПС) системи визначається наступним чином:

. (1)

Оскільки зміни станів системи відбуваються лише в моменти надходження заявок і/або завершення їхнього обслуговування, то у ФПС (1) можливі лише переходи n n+ei і n+ei n, де ei - i-й ортвектор K-вимірного евклідового простору, i = 1, 2,…, K.

Інтенсивності цих переходів q (n, n); n, n S, визначаються виразом:

(2)

На підставі виразу (2) складаємо систему рівнянь глобальної рівноваги (СРГР) щодо стаціонарних імовірностей станів p(n), n S. З використанням (2) легко отримати явний вигляд цієї СРГР:

(3)

(4)

Тут і надалі Рівняння (4) є умовою нормування.

Розв'язок СРГР має мультиплікативний вигляд:

, (5)

де i:= i/i, G (N, K) - нормуюча константа, яка забезпечує виконання умови (4):

(6)

Із (5) визначаємо, що

p(0) = G-1(N, K). (7)

З метою доведення справедливості (5) складається система рівнянь локальної рівноваги (СРЛР) щодо співвідношення (3). Зазначена СРЛР має такий вигляд:

q (n, n) p(n) = q (n, n) p (n), n, n S. (8)

Із використанням виразу (2) СРЛР (8) у явному вигляді записується так:

ip(n) = (ni+1)ip (n+ei), n, n+ei S. (9)

Тепер легко показати, що (5) є розв'язком СРЛР (8). Дійсно, із виразів (5) і (9) знаходимо, що або, іншими словами, (5) є розв'язком СРЛР (9) і, відповідно, розв'язком СРГР (3), (4).

Важливою характеристикою даної моделі є стаціонарна ймовірність втрати (блокування) заявок (Probability of Blocking, PB). З урахуванням теореми PASTA підсумовуємо, що вона є однаковою для всіх трафіків і визначається формулою:

(10)

де - множина діагональних станів.

Проте обчислення стаціонарного розподілу даної моделі за допомогою класичних формул пов'язане з величезними труднощами для моделей з багатьма каналами й різними типами трафіків. Це пояснюється тим, що пряме обчислення значення нормуючого коефіцієнту G (N, K) супроводжується переповненням (при величині коефіцієнту завантаження - і > 1) і зникненням порядку (при i 0).

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

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

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

Крок 1. Розглядається деяке розщеплення ФПС X

X = Xv, Xv Xv?=Ш, v ? v?. (11)

Крок 2. Всі мікростани, що входять до підмножини Xv, об'єднуються в один укрупнений стан (УС), який позначається щv, v = 1, 2, …, V. Всі одержані таким шляхом УС складають деякий простір Щ:= {щ1, щ2, …, щV}.

Крок 3. На підставі розщеплення (11) будуються функції укрупнення Uv: X > , де := X Щ\{щv}, v = 1, 2, …, V, які визначаються таким чином:

(12)

Функції укрупнення (12) визначають V укрупнених (відносно вихідної) моделей, при цьому v-а укрупнена модель (УМ) має ФПС , v = 1, 2, …, V.

Крок 4. Визначається множина допустимих рішень Dv для v-ї УМ. Вона шукається як проекція множини D на множину Xv.

Dv:= Dx.

Крок 5. Визначаються елементи перехідної матриці v-ї укрупненої моделі Pv = ||Pvd(x, x')||, x, x' :

. (13)

Оскільки стаціонарний розподіл початкової моделі невідомий, то при дослідженні v-ї укрупненої моделі неможливо користуватися значеннями що визначаються за допомогою формули (13). Отже, необхідно, використовуючи різні схеми апроксимації, оцінити значення невідомих елементів перехідної матриці зверху або знизу.

Крок 6. Елементи вектора середніх втрат (для v-ї укрупненої моделі vCdx - втрати за один крок, якщо у стані x прийняте управління d Dv відповідно до формули (13)) визначаються через невідомий стаціонарний розподіл початкової моделі. Тому тут виникає необхідність апроксимації значення цих величин, які для випадків оцінки зверху й знизу визначаються відповідно наступними формулами (14) і (15).

. (14)

. (15)

Крок 7. Для апроксимації значень критерію якості використовуються оцінки зверху і знизу, що визначаються відповідно формулами (16) і (17).

, (16)

, (17)

де ; .

Крок 8. Якщо в усіх УМ всі параметри (елементи перехідної матриці й критерії якості) оцінюються зверху, то одержимо V «мажорантних» задач відносно початкової задачі оптимізації. В іншому випадку, тобто якщо в усіх УМ названі параметри оцінюються знизу, то одержимо V «мінорантних» задач відносно початкової задачі оптимізації. Після розв'язання задачі оптимізації v-ї УМ («мажорантної» чи «мінорантної») знаходяться наближені оптимальні значення бdk, xk Xv, і, таким чином, після паралельного розв'язку всіх V аналогічних задач знаходяться наближено оптимальні значення всіх бdk, де xk X.

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

Другий розділ «Методи дослідження характеристик бездротових стільникових мереж зв'язку» присвячено дослідженню організації викликів у бездротових мережах стільникового зв'язку, розробці методів розрахунку й оптимізації характеристик таких мереж. Організацію процесів обробки викликів у бездротових стільникових мережах зв'язку описано на прикладі архітектури GSM мережі.

У бездротових стільникових мережах зв'язку окрім ініційованих потоків нових викликів (о-викликів) існує й додатковий клас викликів, які вимагають особливого підходу. Це так звані хендовер-виклики (h-виклики). Причинами такого фундаментального явища як хендовер є рухомість абонентів і стільниковий принцип побудови мережі. Сутність цього явища полягає в тому, що мобільна станція (MS), яка вже встановила зв'язок із мережею (коли новий виклик успішно зайняв певний ресурс мережі, бездротовий канал), пересуваючись, проходить зони між стільниками і опиняється в області дії іншого стільника. З точки зору нового стільника - це хендовер-виклик і, через те, що зв'язок з MS вже встановлений, перехід обслуговування MS на новий стільник має відбутися непомітно для неї. Таким чином, ми спостерігаємо більш пріоритетне обслуговування хендовер-виклику в новому стільнику стосовно нових викликів у цьому стільнику. Розглянемо більш докладно це явище на прикладі GSM мережі.

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

З точки зору мережі, визначення моменту, коли необхідний хендовер та його оперативне здійснення, є досить складним завданням. Часові помилки на каналах між MS і BS можуть виникати і всередині одного стільника. Це означає, що необхідний певний час, поки BS заздалегідь зможе визначити за зменшенням потужності сигналу, що абонент віддаляється від BS. З іншого боку, якщо дійсно є необхідність у хендовері, то процес має бути ініційованим якомога скоріше, інакше обірветься вже встановлений зв'язок, тобто відбудеться вимушене переривання розмови. Для того, щоб визначити необхідність хендовера, MS повинна проводити вимірювання якості каналу, яким вона зараз користується, а також широкомовних каналів сусідніх стільників. Різні стандарти стільникових мереж визначають різні процедури такого вимірювання.

У стандарті GSM мобільна станція постійно вимірює якість сигналів і періодично передає ці дані BS. У свою чергу, BS отримує або лише дані щодо вимірювань, які вона має оцінити і прийняти рішення стосовно необхідності хендовера, або ж дані щодо вимірювань і кандидатури нової BS, вибраної самою MS. У першому випадку BS ініціює запит на хендовер, якщо це необхідно, і посилає цей запит центру комутації. Потім центр комутації вибирає найбільш придатну BS для продовження обслуговування виклику. У другому випадку базова станція просто посилає MSC запит на хендовер до конкретної нової BS. В обох випадках MSC повідомляє нову BS про запит хендовера. Нова BS, залежно від застосованої стратегії доступу, може цей хендовер-виклик або прийняти, або блокувати, або поставити у чергу. Вона інформує MSC про статус цього запиту. Залежно від відповіді, MSC дозволяє, затримує або вимушено перериває хендовер-виклик (рис. 1). Рух від BS1 до BS2 вважається прямолінійним. Хендовер має відбутися у період [t0, t1].

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

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

У третьому розділі «Дослідження моделей процесів обслуговування викликів у мережах без черг» досліджуються моделі процесів обслуговування викликів у бездротових мережах зв'язку при різних стратегіях доступу. Спочатку вивчаються моделі, у яких використовується найбільш відома стратегія управління доступом, заснована на GC-схемі (схемі з резервуванням каналів) доступу до загальних каналів базової станції стільника. Далі досліджується модель ізольованого стільника, у якій прийнята стратегія керування доступом різнотипних викликів у канали базового стільника, заснована на виділенні індивідуальних каналів для h-викликів. Запропоноване також узагальнення цієї стратегії доступу до каналів. У ній запроваджується гранична межа кількості h-викликів у загальній зоні каналів з метою захисту о-викликів від частих втрат. Розроблено алгоритми розрахунку характеристик системи при всіх досліджуваних стратегіях доступу й показана висока точність запропонованих залежностей.

Виконано порівняльний аналіз характеристик стільника при використанні різних стратегій доступу різнотипних викликів. Показано, що стратегія одного типу дозволяє поліпшити деякі характеристики, при цьому погіршуються інші характеристики стільника. У зв'язку із цим, відзначається актуальність проведення серйозних досліджень щодо вибору відповідної стратегії з метою задоволення заданих вимог на показники якості обслуговування (QoS - Quality of Service) різнотипних викликів.

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

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

Запропоновано алгоритм розрахунку характеристик системи при використанні індивідуальних каналів для h-викликів, що дозволяє захистити о-виклики від частих втрат внаслідок обмеження доступу h-викликів у загальну зону. Наведено алгоритм для обчислення характеристик системи при використанні узагальненої стратегії використання індивідуальних каналів для h-викликів.

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

де функція Ph - імовірність втрати h-викликів, функція Po - імовірність втрати о-викликів; - середнє число зайнятих каналів; WPB (N, r) - зважена сума ймовірностей втрат різнотипних викликів:, верхні індекси «grd» і «ind» позначають відповідні характеристики GC-стратегії й стратегії на базі індивідуальної зони для h-викликів, відповідно.

Діапазони зміни ймовірностей блокування / втрат для різнотипних викликів для обох стратегій доступу є дуже близькими, однак швидкості їхньої зміни істотно відрізняються одна від одної. Так, наприклад, при N = 100, 1 = 50 ерл, 2 = 35 ерл діапазони зміни характеристик системи визначаються так:

Стратегія GC використовує загальну пропускну спроможність гірше, ніж стратегія на базі індивідуальних каналів для h-викликів. Так, наприклад, при тих же вихідних даних (N = 100, 1 = 50 ерл, 2 = 35 ерл) лише для 1 g 33 при стратегії GC утилізація каналів ледве більше 40%, а вже для g 40 утилізація каналів стає навіть меншої 30%; проте при використанні стратегії доступу на базі індивідуальних каналів h-викликів для цих вихідних даних утилізація каналів перебуває між 35% і 85%. Іншими словами, при будь-яких вихідних даних стратегія доступу на базі індивідуальної зони для h-викликів виявляється кращою, ніж стратегії на базі GC у сенсі утилізації каналів стільника.

Ці висновки показують актуальність проблеми вибору оптимальної (у заданому сенсі) стратегії доступу в канали стільника різнотипних викликів, тобто при тих самих значеннях числа каналів стільника, навантаженнях і бажаних діапазонах зміни значень показників QoS, одна із цих стратегій може задовольняти їх, а інша - ні. Так, наприклад, для N = 100, 1 = 50 ерл, 2 = 35 ерл і заданих вимог стратегія на базі GC ні при якому значенні параметра g не задовольняє зазначеним обмеженням, у той час як стратегія на базі індивідуальної зони для h-викликів задовольняє зазначеним обмеженням при . Разом з тим, при тих же вихідних даних і заданих обмеженнях , стратегія на базі GC задовольняє цим обмеженням при ; у той же час стратегія на базі індивідуальної зони для h-викликів ні при якому значенні параметра r не задовольняє цим обмеженням.

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

Четвертий розділ «Методи розрахунку характеристик моделей процесів обслуговування викликів у бездротових мережах із чергами» присвячено дослідженню моделей процесів обслуговування викликів у бездротових мережах стільникового зв'язку, в яких передбачається організація черги нових і/або хендовер-викликів.

Оскільки h-виклики є більш чутливими до можливих втрат і затримок, ніж нові о-виклики, то в літературі відомі різні схеми надання пріоритетів h-викликам. Ці схеми, головним чином, мають на увазі використання резервних або індивідуальних каналів для h-викликів і/або організації. їх черги у BS. Час, протягом якого MS перетинає хендовер-зону, називається інтервалом деградації. Коли MS надходить до хендовер-зони, перевіряється наявність вільних каналів у новому стільнику. Якщо у новому стільнику є вільний канал, то h-виклик відразу займає його, і процедура хендовер вважається закінченою успішно на даному етапі; в іншому випадку канал попереднього стільника продовжує використовувати даний h-виклик і одночасно цей виклик стає у чергу для очікування звільнення будь-якого каналу нового стільника. Якщо до завершення інтервалу деградації у новому стільнику вільний канал не стає доступним, то відбувається вимушене переривання розмови h-виклику.

З метою поліпшення показників якості обслуговування о-викликів і компенсації їх шансів необхідна також організація черги і для цього типу викликів. Тому виникає необхідність дослідження моделей обслуговування, в яких поряд із використанням резервних каналів для h-викликів вводиться буфер скінченого чи нескінченого розміру для о-викликів. При використанні схеми з буферизацією викликів передбачається, що при вивільненні каналу нового стільника черга викликів (нових або хендовер) обслуговується згідно з дисципліною FIFO (First In - First Out).

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

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

Запроновані у даному розділі алгоритми на відміну від відомих методів розрахунку характеристик моделей стільникового зв'язку враховують неідентичність різнотипних викликів (за тривалістю часу зайняття каналів).

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

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

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

Висновки

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

У дисертації одержані такі основні теоретичні й прикладні результати.

1. На прикладі розімкнених моделей типу MK|MK|N|0 показано, що обчислення стаціонарного розподілу моделей з багатьма каналами й різними типами трафіків за допомогою класичних формул пов'язане з величезними труднощами, для подолання яких доцільно застосувати підхід, заснований на принципах укрупнення фазового простору системи. Цей підхід виявляється більш ефективним, ніж класичний алгоритм Бузена, який ґрунтується на двовимірних рекурентних формулах. Він легко поширюється на клас моделей багатошвидкісних систем обслуговування, де виклики вимагають одночасно більшої від одиниці кількості каналів.

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

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

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

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

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

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

8. Доведено, що стратегія GC використовує загальну пропускну спроможність гірше, ніж стратегія на базі індивідуальних каналів для h-викликів. Це підтверджує актуальність проблеми вибору оптимальної стратегії доступу в канали стільника різнотипних викликів, бо при тих самих значеннях числа каналів стільника, навантаженнях і бажаних діапазонах зміни значень показників QoS, одна із цих стратегій може задовольняти їх, а інша - ні.


Подобные документы

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.