Багатофакторна оптимізація просторово-часової структури телекомунікаційних мереж

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

Державний університет інформаційно-комунікаційних технологій

Спеціальність 05.12.02 - Телекомунікаційні системи та мережі

Автореферат

дисертації на здобуття наукового ступеня доктора технічних наук

Багатофакторна оптимізація просторово-часової структури телекомунікаційних мереж

Гайворонська Галина Сергіївна

Київ - 2007

Дисертацією є рукопис

Роботу виконано в Державному університеті інформаційно-комунікаційних технологій Міністерства транспорту та зв'язку України

Науковий консультант: заслужений діяч науки і техніки України,

доктор технічних наук, професор

Кривуца Володимир Георгійович,

Державний університет інформаційно-комунікаційних технологій, ректор

Офіційні опоненти: доктор технічних наук, професор

Сундучков Костянтин Станіславович,

Інститут телекомунікаційних систем НТУУ „КПІ”,

заступник директора з наукових питань

доктор технічних наук, професор

Лучук Андрій Михайлович,

Державний університет інформаційно-комунікаційних

технологій Міністерства транспорту та зв'язку України

професор кафедри інформаційних технологій

доктор технічних наук, професор

Князєва Ніна Олексіївна,

Український науково-дослідний інститут радіо та телебачення Міністерства транспорту та зв'язку,

провідний науковий співробітник, завідувач лабораторії

Провідна установа - Національний авіаційний університет Міністерства освіти та науки України

Захист відбудеться 20.06.2007 р. о 14 годині на засіданні

спеціалізованої ради Д 26.861.01 Державного університету інформаційно-комунікаційних технологій за адресою: 03110, Київ, вул. Солом'янська, 7

З дисертацією можна ознайомитися в бібліотеці Державного університету

інформаційно-комунікаційних технологій за адресою

03110, Київ, вул. Солом'янська, 7

Автореферат розісланий 19.05.2007року

Вчений секретар спеціалізованої вченої ради к.т.н., доцент Кунах Н. І

Загальна характеристика роботи

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

Це підтверджується тим, що питанням розвитку ТМ приділяють велику увагу міжнародні організації та уряд України. У Постанові Верховної Ради України «Про затвердження завдань Національної програми інформатизації на 2006-2008 роки» виділено напрямки пріоритетного розвитку, що передбачають: «впровадження на мережах зв'язку України нових технологій; побудову мереж наступного покоління шляхом послідовної цифровізації телефонної мережі,… заміною транзитних і міжміських, а надалі й кінцевих АТС на обладнання доступу до пакетної мережі; забезпечення доступу громадян України до ІКП…»

Проблемою розвитку та оптимізації ТМ займалося багато вітчизняних та закордонних вчених, зокрема: Давидов Г. Б., Рогінський В. Н., Нейман В. І., Харкевич А. Д., Аджемов С. А., Лазарєв В. Г., Клейнрок Л., Захаров Г. П., Варакін Л. Е., Совєтов Б. Я., Яковлєв С. А., Умріхін Ю. Д., Ченцов В. М., Соколов Н. А. та багато інших. Виконаний аналіз опублікованих праць показав, що існує аналітичний апарат для оптимізації мереж, але за останні роки ситуація у сфері інфокомунікацій кардинально змінилася, йде процес створення мереж нового покоління, однак продовжують використовуватися методи розрахунку та планування мереж, що були запропоновані в минулому столітті.

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

Зв'язок роботи з науковими програмами, планами, темами. Робота направлена на оптимізацію сценаріїв розвитку ТМ і тісно пов'язана з основними напрямками розвитку телекомунікацій України, визначених в основних діючих нормативних документах, а також із реальними проблемами галузі зв'язку й інформатизації та сформульована згідно з Постановами Верховної Ради України «Про затвердження завдань Національної програми інформатизації на 2006-2008 роки» та «Про основні завдання щодо впровадження новітніх інформаційних технологій», а також Законами України «Про Концепцію Національної програми інформатизації» та «Про Національну програму інформатизації».

Обраний у роботі напрямок досліджень тісно пов'язаний з виконанням ряду науково-дослідних робіт, у реалізації яких брав участь автор, а саме модель представлення класів послуг та рівнева модель надання послуг, а також алгоритмічна процедура розв'язання задачі оптимізації еволюції ТМ та програмний продукт, призначений для визначення оптимального сценарію еволюції мережі, були використані при виконанні НДР «Векторний синтез телекомунікаційних мереж» (№ ДР 0103U002500) та НДР «Розробка методичного посібника «Алгоритм автоматизованого обліку і контролю трафіку в умовах багатооператорської діяльності» (замовник ВАТ «Укртелеком, № ДР 0103U002497).

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

Для досягнення мети необхідно вирішення наступних задач:

вибір та обґрунтування методу порівняння альтернатив вирішення проблеми оптимізації модернізації ТМ;

формулювання проблеми оптимізації модернізації ТМ;

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

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

класифікація існуючих і майбутніх ІКП та розробка вимог до мережі й обладнання для надання цих послуг;

формалізація опису модернізації ТМ разом у часі та просторі;

просторово-часове подання навантаження, яке поступає на мережу, міжвузлового тяжіння, та оцінка чутливості характеристик мережі до варіації навантаження, яке прогнозується;

розробка методу взаємозв'язаного розташування двох типів комутаційного обладнання: опорного та виносного;

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

формулювання загальної задачі оптимізації ТМ за критерієм мінімальної величини поточних витрат;

розробка алгоритмічної процедури вирішення проблеми модернізації ТМ;

програмна реалізація алгоритмічної процедури оптимізації ТМ.

Об'єкт дослідження - просторово-часова структура ТМ при її модернізації.

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

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

Наукова новизна результатів, отриманих у дисертаційній роботі:

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

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

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

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

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

Вперше сформульовано та вирішено задачу оптимізації просторово-часової структури ТМ за критерієм мінімальної поточної вартості мережі на кожному етапі модернізації.

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

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

Розроблена алгоритмічна процедура розв'язання задачі оптимізації еволюції ТМ.

Отримала подальший розвиток багатопараметрична класифікація ІКП.

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

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

Практичне значення отриманих результатів:

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

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

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

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

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

Реалізація результатів роботи. Результати дисертаційної роботи знайшли застосування при плануванні ТМ низки регіонів Україні, а саме: Республіки Крим, Одеської, Вінницької, Кіровоградської, Івано-Франківської областей, що дозволило зменшити витрати часу на оптимізацію мережі практично на порядок у порівнянні з найкращими із відомих існуючих засобів автоматизованого проектування (акт впровадження Державного департаменту з питань зв'язку та інформатизації від 15.02.2007). Крім цього, на замовлення Одеської філії ВАТ «Укртелеком» з використанням методів, запропонованих у дисертації проведена оцінка впливу навантаження інших операторів зв'язку на якість роботи Одеської МТМ (акт впровадження від 30.10.2006), а при плануванні процесу розвитку ТМ автономної республіки Крим, використано дослідження впливу помилок прогнозу вхідних даних на результати планування ТМ, що дозволило спростити процес прийняття рішень при проектуванні, виконана оцінка використання методів прогнозування сезонних коливань навантаження, що підвищує ефективність планування мереж за рахунок не співпадаючих сезонних піків та дозволяє знизити витрати на створення мережі до 30% при використанні динамічної маршрутизації викликів (акт впровадження від 30.01.2007).

Результати роботи знайшли застосування в розробках науково-аналітичного центру «Телеком». (акт впровадження від 20.12.06) та викладені в підручнику «Сети и системы телекоммуникаций» та чотирьох навчальних посібниках. Теоретичні і практичні положення дисертаційної роботи використовуються в навчальному процесі Державного університету інформаційно-комунікаційних технологій (акт впровадження від 28.11.06) та інституту інформаційних технологій Одеської державної академії холоду (акт впровадження від 12.01.07).

Особистий внесок здобувача. Дисертаційне дослідження є самостійно виконаною роботою, в якій відображено особистий авторський підхід та особисто отримані теоретичні та прикладні результати, які відносяться до методів оптимізації просторово-часової структури телекомунікаційних мереж (ПЧСТМ). У монографії «Сети и системы телекоммуникаций» здобувачем особисто написані передмова, вступ, розділи 3, 7 та 8, що складає 114 сторінок тексту, а в решті підрозділів здобувач була співавтором. У роботах, опублікованих у співавторстві, автору дисертації належить: аналіз існуючого стану та напрямків розвитку основних сегментів архітектури ТМ, а також дослідження впливу цих факторів на принципи планування ТМ в сучасних умовах [2]; формулювання та вирішення задач оптимального розміщення цифрових систем комутації на місцевій телефонній мережі методами цілочисельного лінійного програмування [6]; загальна постановка задачі, методів дослідження та аналіз отриманих результатів [14, 16, 19, 21, 25, 38].

Апробація результатів дисертації. Основні результати дисертації доповідались та обговорювались на міжнародних та національних конференціях: професорсько-викладацької НТК Одеської національної академії зв'язку ім. О. С. Попова та Київського інституту зв'язку (зараз ДУІКТ) (2000-03), IV-VII Міжнародних НПК «Системи та засоби передачі й обробки інформації», Одеса, 2000-2003; V Міжнародній НТК «Телеком-2001»; II Міжнародній НПК «Сучасні інформаційні та електронні технології» Одеса, 2001; НТК «Телекомунікації на порозі третього тисячоліття», Одеса, 2002; I-III Міжнародних НПК «Проблеми управління мережами та послугами телекомунікацій в умовах конкурентного ринку», УНДІЗ, Крим, 2003-2005; на V-VIII Міжнародних НПК «Еволюція транспортних мереж телекомунікацій. Проблеми побудування, розвитку та управління», УНДІЗ, Крим, 2003-2006; III-ІV семінарах «Інформаційні системи та технології», ОДАХ, Одеса, 2005-2006; I-II Міжнародних НТК «Сучасні інформаційно-комунікаційні технології», Київ-Кацивелі, 2005-2006 та ін.

Публікації. Основні результати дисертації та її наукових положень опубліковані в підручнику для вузів, навчальних посібниках, статтях у науково-технічних журналах, працях міжнародних конференцій. Усього по темі дисертації опубліковано 42 роботи (у співавторстві 9), із них у науково-технічних журналах, що відповідають переліку ВАК - 22 (у співавторстві 6). Загальний список наукових праць - 78 найменувань.

Структура дисертації. Робота складається з вступу, семи розділів, висновку, списку використаних джерел та додатку. Робота містить 289 сторінок тексту, 81 малюнок, 7 таблиць та список використаних джерел в 265 найменувань. У додатку містяться 6 актів впровадження результатів дослідження.

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

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

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

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

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

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

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

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

Виконаний аналіз методів розв'язання задач, які були сформульовані під час декомпозиції загальної проблеми дослідження, виявив, що використання в цьому випадку безумовних критеріїв переваги, таких як р-критерій Парето чи S-критерій Слейтера, ускладнюється тим, що множина альтернатив вибору, тобто можливих стратегій розвитку мережі, хоча і скінчена та завчасно відома, але є дуже великою. Використання умовних критеріїв, таких як лексикографічний L-критерій та Д-критерій з поступками, спряжено з проведенням одразу декількох досліджень, кожне з яких за складністю може бути порівняне зі складністю оптимізації стратегії розвитку за одним критерієм. Крім того, Д-критерій передбачає наявність завчасно заданих «поступок», які є суб'єктивними. Якщо припустити, що послідовне звуження вихідної множини альтернатив здійснене, то розв'язання задачі оптимізації еволюції мережі за одним критерієм втрачає сенс через вузькість множини альтернатив вибору. Тому проблема, що досліджується, позиціонована як проблема вибору, для якої недоцільно використовувати багатокритеріальні постановки.

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

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

Аналіз впливу факторів на процес еволюції ТМ дозволив виявити найбільш значущі з них, а саме: характеристики вимог користувачів до обслуговування мережею; характеристики ІКП, що визначають вимоги до мережі; навантаження, тяжіння між вузлами мережі, технічні та економічні характеристики мережного обладнання. Ці параметри використані як вхідні дані при розробці моделі дослідження, решта факторів введені в якості умов, обмежень і припущень.

У третьому розділі виконано дослідження найбільш важливих факторів, а саме: вимог користувачів щодо підключення до мережі, параметрів ІКП та вимог до мережі для їх надання, а також дослідження параметрів навантаження та тяжіння в ТМ. Формалізація інших факторів здійснена в розділі 4.

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

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

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

На основі сукупності матриць інтенсивності потоків повідомлень між вузлами та матриць тяжіння між ними, запропонована процедура формалізації опису просторово-часового (ПЧ) представлення навантаження.

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

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

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

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

Виділено класи СК та введені їх формалізовані описи у вигляді відображення , де - булеан множини типів СК, А - клас типів СК існуючих технологій; В - клас типів опорного обладнання нових технологій; R - клас типів ВК нових технологій. Вартісні параметри СК кожного типу задані у вигляді наступних функцій: - річні видатки на обслуговування одиниці ємності СК; - видатки на нову СК при накладанні; - видатки на СК при заміні; - видатки на одиничний приріст ємності існуючої СК; - видатки на одиничний приріст ємності нової СК при накладанні; - видатки на одиничний приріст ємності СК при заміні; - вартість одиниці довжини кабелю.

Запропоновано модифіковане подання дисконтного коефіцієнта для приведення значень майбутніх грошових потоків до поточної вартості у вигляді де C* - поточна вартість майбутніх витрат; Ct - величина майбутніх витрат; i - дисконтна ставка; - модифіковане подання дисконтного коефіцієнту; t - момент часу, що відповідає періоду, в якому розглядаються майбутні витрати. Для врахування можливості повторного використання обладнання, що виводиться з експлуатації, введена чиста залишкова вартість одиниці існуючого обладнання .

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

На основі часової структури задачі оптимізації ТМ за рівнем складності розділено на 4 класи: : структура підключень мережі строго стаціонарна ; : структура підключень узагальнено стаціонарна ; : допустима будь-яка структура, але без змін підключень ; : допустима довільна структура підключень. Ці класі складають ланцюг включень , де задачі виключають можливість введення ВК.

У п'ятому розділі виконано дослідження оптимізації еволюції ТМ. Для задачі еволюції вузла розглянуто динаміку зміни витрат на його модернізацію та обслуговування. На рис. 2 через и та r позначені відповідно моменти накладання та заміни СК. На рисунку виділені області, що відповідають поточним витратам на СК, встановлені на вузлі, який досліджується: 1 відповідає існуючому обладнанню, встановленому на момент початку дослідження; 2 - СК існуючої технології, що вводиться для підвищення ємності вузла; 3 - новому обладнанню, використаному для заміни існуючого; 4 - визначає нові СК, що будуть застосовуватись для підвищення ємності вузла; 5 - відповідає існуючому обладнанню, збереженому до заміни. Цим областям рис. 5 відповідають деякі капітальні та експлуатаційні витрати. Кожна складова експлуатаціонних витрат виражена функцією:

(1)

де ; .

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

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

Аналогічно виражені поточні значення капітальних витрат в кожен момент часу

Після перетворень подібних до виконаних для експлуатаційних витрат отримаємо повне представлення капітальних витрат

Після підсумування та групування отримуємо повну величину витрат на еволюцію вузла при накладанні обладнання в момент та заміні в момент

, (3)

де ; ;

; .

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

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

Аналітичне розв'язання задачі визначення оптимальної стратегії еволюції вузла можливе за умов, що оптимальна стратегія еволюції є «чистою», тобто якщо вона інваріантна та детермінована на проміжку часу дослідження [0; h]. З цього визначення витікає три типи чистих стратегії еволюції: а) невідкладна заміна існуючих систем новими на початку періоду дослідження (и=r=0); б) невідкладне накладання (и=0; r=h); в) тривале зростання, тобто розширення вузла за допомогою існуючого обладнання (и=r=h). Вартість еволюції вузла для кожної із стратегій визначається як: а) ; б) ; в) .

Зв'язок між оптимальною та чистою стратегіями еволюції встановлює теорема 1: нехай - вартість еволюції вузла, що відповідає стратегії , при , а ; . Тоді вірні твердження: оптимальна стратегія еволюції вузла є чистою тоді і тільки тоді, коли виконана одна з умов: а); б); в); Якщо , то оптимальною є відкладена заміна .

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

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

.

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

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

Нехай . Позначимо вартість еволюції вузла : - відповідає стратегії тривалого росту; - невідкладне накладання ВМ та підключення його до вузла ; - невідкладна заміна існуючого обладнання на ВМ та підключення його до вузла ; - невідкладне накладання опорного обладнання; - невідкладна заміна існуючого обладнання на нове опорне. Для величин та врахована вартість прокладки кабелю між та .

;

,

де - функція вартості для опорного обладнання; - функція вартості для ВК; - вартість прокладки одиниці довжини кабелю.

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

, .

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

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

(4)

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

відносно , за умов: , , ; , .

Не розв'язуючи задачу, на основі лише її формулювання випливає, що:

; ; .

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

відносно , , за умов , , , , .

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

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

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

Виразивши вартість еволюції мережі через вартість еволюції кожного вузла як: - вартість еволюції за стратегією , () - вартість еволюції за стратегією (), отримаємо вартість еволюції мережі в цілому .

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

відносно

, за умов , , ,

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

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

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

відносно за умов ; ; ; .

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

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

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

відносно , за умов

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

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

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

за умов ; .

де - бінарна величина, що визначає, чи підключається винос до вузла .

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