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

Анотація наукової статті з комп'ютерних та інформаційних наук, автор наукової роботи - Качанов Сергій Олексійович, Медведєв Микола Вікторович


Article offers algorithm of leveling loading of mobile information and communication centers net which will help to increase quality and reliability of the communication system functioning in conditions of emergency situation.


Область наук:
  • Комп'ютер та інформатика
  • Рік видавництва: 2011
    Журнал: Технології громадянської безпеки
    Наукова стаття на тему 'Алгоритм вирівнювання завантаження вузлів мобільного інформаційно-телекомунікаційної мережі'

    Текст наукової роботи на тему «Алгоритм вирівнювання завантаження вузлів мобільного інформаційно-телекомунікаційної мережі»

    ?УДК 621.865.8

    Алгоритм вирівнювання завантаження вузлів мобільного інформаційно-телекомунікаційної мережі

    С.А. Качанов, Н.В. Медведєв

    Анотація

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

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

    Algorithm of Leveling Loading of Mobile Information and Communication Centers Net

    S. Kachanov, N. Medvedev

    Abstract

    Article offers algorithm of leveling loading of mobile information and communication centers net which will help to increase quality and reliability of the communication system functioning in conditions of emergency situation.

    Key words: loading balancing, information stream, communication traffic, information graph, optimal loading rate, communication center.

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

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

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

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

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

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

    1 QoS - Quality of Service.

    до * до

    мість балансування якого дорівнює ф (ф) = ф .

    Технології громадянської безпеки, том 8, 2011, № 1 (27)

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

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

    / 27

    оп .

    Вартість балансування про о! про сл з 11111

    ) 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 Навантаження

    Мал. 1. Приклад функції вартості балансування

    ходять через даний вузол. Повний потік / (т) через вузол т визначається за формулою

    / (Т) = Vm еб.

    (1)

    Кек г = 1

    до, /

    де ат -

    1, їсть 1-ий маршрут для до потоку проходить через ребро т 0, якщо

    / - частка до -потока, Маршрутізірованний по / -Маршрут з відповідного безлічі маршрутів.

    Е - безліч гілок графа.

    Повний потік, що проходить через вузол т, повинен задовольняти обмеження / (т) < с (т) \ / т е Е, де с (т) - пропускна спроможність вузла т.

    простір можливих розподілів до -потока за маршрутами, тоді

    ф (Ок) = {ф (фк): фк ЕОК}.

    Визначимо тепер простір спільного розподілу потоків Про як підпростір твори просторів розподілів окремих потоків О1 х ... х ОК, на якому виконується умова:

    Завантаження на вузол т дорівнює Я (т) =

    / (Т) з (т)

    (2)

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

    Вартісна функція ф (-) залежить від способу розподілу потоків по маршрутам відповідаю-

    О = {(ф ', ..., фК): фг е Ог, г = 1, К, / (I) <с (!)}. відповідно,

    ф (О) = {ф (ф \ ..., ф К): (ф \ ..., ф К) ЄВ}

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

    ф! ... до: = ф (ф ', ..., фК).

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

    Г

    ф1 'К о ф (О), при якому

    ф1 ... До < ф1 ... К, Уф1 ... К о ф (О)

    (3)

    -потоку,

    щих класів. Нехай фк - частка до |

    г / к

    Маршрутізірованний по / -шляху. Тоді розподіл до -потока за маршрутами безлічі РР до можна

    записати у вигляді вектора фк = (фк, ф?, -, фкпк), вар-

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

    '^ Ф (т) (4)

    Ш1П

    ті Б

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

    Крок 1. Завдання вихідних даних.

    1.1. безліч класів

    К = [до: к = е), s, е е V ,, 5 ^ е}

    1.2. Пропускні спроможності вузлів

    з (/), / = \ Е.

    1.3. Потоки / к, к = 1, К .

    1.4. Безліч маршрутів Рг .

    1.5. ф (О) = 0 .

    Крок 2. Знаходження мінімальної вартості

    Ф / ... До .

    2.1. Побудувати простір спільних розподілів потоків Про.

    2.2. Вибрати (ф \ ..., ф К) ЄВ.

    2.3. Визначити потоки на вузли / (/), / = 1, Е за формулою (2.3).

    2.4. Обчислити вартість балансування ф (/) для кожного вузли за формулою (2.5).

    2.5. Знайти вартість ф1 До спільного розподілу, змінити безліч ф (О) = ф (О) У ^ До}

    і покласти 0 = 0 \ {(ф1, ..., ф K)}.

    2.6. Знайти min {ф1 K} і завершити роботу алгоритму. ф1-к еф (П)

    Використання даного алгоритму дозволяє підвищити якість і надійність роботи систем зв'язку в умовах НС.

    література

    1. W. Szeto, R. Boutaba, and Y. Iraqi. Dynamic Online Routing Algorithm for MPLS Traffic Engineering // Department of Computer Science, University of Waterloo, Waterloo, ON, Canada, 2002.

    2. Самуйлов К.Є. Методи аналізи і розрахунку мереж ОКС 7. М .: Изд-во РУДН, 2002.

    3. Крістофідес Н. Теорія графів. Алгоритмічний підхід. М .: Мир, 1978.

    4. S.C. Erbas and C. Erbas. A multiobjective offline routing model for MPLS networks. In J. Charzinski, R. Lehnert, and P. Tran-Gia, editors, Providing Quality of Service in Heterogenious Environments - Proc. Of the 18th International Teletraffic Congress (ITC-18), pages 471-480, Berlin, Germany, August-September 2003.

    5. S.C. Erbas and R. Mathar. An offline traffic engineering model for MPLS networks. In Proceedings of the 27th Conference on Local Computer Networks LSN 2002 pages 166-174, Tampa, Florida, November 2002. IEEE Computer Society.

    6. Оліфер В.Г., Оліфер Н.А. Комп'ютерні мережі: принципи, технології, протоколи. СПб .: Питер, 2001.

    Відомості про авторів

    Качанов Сергій Олексійович: д.т.н., професор, ФДМ ВНДІ ГОЧС (ФЦ), заст. начальника інституту з наукової роботи.

    Сто двадцять одна тисяча триста п'ятьдесят два, г. Москва, ул. Давидковской, 7. Медведєв Микола Вікторович: к.т.н., доцент, МГТУ ім. Н.е. Баумана, начальник науково-дослідної лабораторії.

    105005, г. Москва, 2-я Бауманська вул., 5, стр. 1.

    Розробки ФГУ ВНДІ ГОЧС (ФЦ)

    / 29

    УДК 62-022.53 ББК 30

    Соколов Ю.І. Ризики високих технологій / МНС Росії. - М .: ФГУ ВНДІ ГОЧС (ФЦ), 2009. - 312 с .: іл.

    ISBN 978-5-93970-039-2

    У книзі дана характеристика техногенного суспільства як суспільства ризику і його зв'язку з появою принципово нових технологій, які отримали назву «високі технології».

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

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

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

    © Ю.І. Соколов 2009

    © ФГУ ВНДІ ГОЧС (ФЦ), 2009

    ЗМІСТ

    ВСТУП

    ГЛАВА 1. Техногенна цивілізація

    1.1. типи цивілізацій

    1.2. постіндустріальне суспільство

    1.3. Суспільство ризику

    1.4. Високі технології постіндустріального суспільства

    ГЛАВА 2. Високі технології і еволюція людини

    2.1. Вплив високих технологій на людину

    2.2. Високі технології і антропний матерія

    2.3. Проблема антропогенного сингулярності

    2.4. Проблеми виживання людства

    2.5. Питання моральної відповідальності за майбутнє

    2.6. Роль науки і технології в сучасному світі

    2.7. Прискорення темпів науково-технологічного прогресу

    2.7. Прискорення темпів біологічної і суспільної еволюції

    ГЛАВА 3. Інформаційно-комунікаційні технології

    3.1. Інформаційні технології

    3.2. Розвиток інформаційного суспільства в Російській Федерації

    3.3. Роль і значення Інтернету

    3.4. Військове застосування інформаційно-комунікаційних технологій

    3.5. «Великий Брат дивиться на тебе»

    3.6. Кіберзлочинність і кібертероризм

    ГЛАВА 4. Біотехнології

    4.1. Основні поняття біотехнології

    4.2. Загальна схема біотехнологічного виробництва

    4.3. Можливості та напрямки біотехнології

    ГЛАВА 5. Генна інженерія

    5.1. Структурна організація генного речовини

    5.2. спадкова інформація

    5.3. Проект «Геном людини»

    5.4. Стовбурові клітини

    5.5. Проект «Протеом людини»

    ГЛАВА 6. Штучний інтелект

    6.1. Поняття «штучний інтелект»

    6.2. Рішення проблеми штучного інтелекту

    6.3. Штучні нейронні мережі

    6.4. Філософські аспекти штучного інтелекту

    6.5. робототехніка

    ГЛАВА 7. Нанотехнології

    7.1. Введення в нанотехнології

    7.2. Техніка нанонауки і нанотехнологій

    7.3. наноматеріали

    7.4. Філософія нанообщества

    ГЛАВА 8. Використання високих технологій у військових цілях

    8.1. Використання біотехнологій

    8.2. генетичне зброя

    8.3. Міжнародні зусилля з контролю за біотехнологіями

    8.4. військові роботи

    8.5. Військове використання нанотехнологій ВИСНОВОК

    ВИКОРИСТАНІ ДЖЕРЕЛА

    Електронна версія книги в форматі PDF

    http://elibrary.ru/item.asp?id=15017749


    Ключові слова: балансування завантаження / інформаційний потік / трафік повідомлень / інформаційний граф / оптимальне значення завантаження / вузол мережі / loading balancing / information stream / communication traffic / information graph / optimal loading rate / communication center

    Завантажити оригінал статті:

    Завантажити