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

Анотація наукової статті з математики, автор наукової роботи - Терехов Олександр Вікторович, Шуригін Юрій Олексійович


Область наук:
  • Математика
  • Рік видавництва: 2010
    Журнал: Доповіді Томського державного університету систем управління і радіоелектроніки

    Наукова стаття на тему 'Алгоритм оптимізації висот підвісу антен в мережах з топологією «Дерево»'

    Текст наукової роботи на тему «Алгоритм оптимізації висот підвісу антен в мережах з топологією« Дерево »»

    ?УДК 621.396.4

    А.В. Терехов, Ю.А. Шуригін

    Алгоритм оптимізації висот підвісу антен в мережах з топологією «дерево»

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

    У статті «Алгоритм оптимізації висот підвісу антен в мережах з топологією« зірка »[1] були розглянуті особливості оптимізації висот підвісу антен різними методами. При проектуванні нових і оптимізації існуючих мереж радіозв'язку топологія «зірка» є окремим випадком топології мережі. Більш загальною є топологія «дерево». Завдання оптимізації висот підвісу антен при топології «дерево» є найбільш актуальною при проектуванні мереж зв'язку для протяжних об'єктів, наприклад нафтопроводів і газопроводів. Топологію «дерево» можна уявити як суперпозицію топологій «зірка». В даний час при проектуванні і оптимізації мереж зв'язку в мережах з топологією «зірка», як і в мережах з топологією «дерево», оптимізація висот підвісу антен виробляється вручну окремо для кожного профілю місцевості, що призводить до втрати цілісності картини і, отже, помилок обчислень. У науковій літературі розглядаються алгоритми оптимізації висот підвісу антен для многоінтервальних РРЛ [2, 3]. При проектуванні і оптимізації мереж зв'язку з топологією «зірка», як і мережі з топологією «дерево», в багатьох сучасних САПР ( «Radio Planning System-2» [4], «Територія» [5]) оптимізація висот підвісу антен виробляється автоматично для кожного профілю місцевості, що призводить до знаходження рішень оптимальних для кожного інтервалу, а не мережі в цілому. Метою даної статті є створення, тестування і реалізація спеціалізованого алгоритму оптимізації висот підвісу антен в мережах з топологією «дерево».

    Початкові умови

    Введемо наступні позначення:

    N - число інтервалів даної системи зв'язку;

    M - кількість станцій системи зв'язку;

    hm - висота підвісу антени m e1 ... M станції системи;

    Hi, 2,3 ... M = (hi, h2, h3 ... Hm) - послідовність висот підвісу антен для системи зв'язку, що складається з M станцій;

    S (Hm) - цільова функція для m e1 ... M станції системи;

    SCуM (Hl ... м) - сумарна цільова функція для системи зв'язку, що складається з М станцій;

    І * = (Н *, Н |, Н * ... НМ) - послідовність висот підвісу антен для системи зв'язку,

    що складається з M станцій, при якій досягається мінімум цільової функції;

    Pml, m2 (Hmi) - функція висоти підвісу антени для станції системи m2 е1 ... М від

    висоти підвісу антени для станції системи m1 е1 ... М. Алгоритм розрахунку функції Pm1, m2 (Hm1) було розглянуто в [1].

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

    м

    S ^ H) = Х S (Hi). (1)

    i = 1

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

    S ^ H *) = min. (2)

    Варто відзначити, що при проектуванні і експлуатації радіосистем до висот підвісу антен пред'являються дві групи вимог [6]:

    • висоти підвісу антен повинні забезпечувати перекриття зони Френеля перешкодами на величину не більше заданого значення;

    • витрати на розміщення або будівництво АМС повинні бути мінімальні.

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

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

    Математична модель

    Введемо основні визначення. Позначимо п-мірне евклідів простір через єп. Простий незамкненою кривої в просторі єп називається безперервна, самонепересекающаяся крива, що з'єднує дві різні точки з єп [7].

    Геометричний граф в просторі єп є безліч V = (V) точок простору

    єп і безліч Е = (ег) простих кривих, які відповідають таким умовам:

    Кожна замкнута крива в Е містить тільки одну точку V безлічі V.

    Кожна незамкнутая крива в Е містить одно дві точки безлічі V, які є її граничними точками.

    Криві в Е не мають спільних точок, за винятком точок з безлічі V.

    Граф будемо позначати через Про або (V, Е). Якщо V і Е - кінцеві безлічі, то Про називається кінцевим графом. Кінцева послідовність ребер графа е1, е2, ез ... єп називається маршрутом. Якщо все ребра, складові маршрут, різні, то такий маршрут називається ланцюгом, якщо вона не замкнута, і циклом, якщо вона замкнута. Граф Про називається зв'язаним, якщо кожна його пара різних вершин може бути з'єднана принаймні одним ланцюгом [8].

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

    Ребра еi і е ^ називаються суміжними, якщо вони мають загальну граничну точку. Число ребер, інцидентних вершині V, називається ступенем вершини V і позначається 8 (і). Кажуть, що вершина ізольована, якщо 8 (і) = 0. Якщо 8 (і) = 1, то вершина називається висячої [7].

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

    Розглянемо топологію мережі (рис. 1) з точки зору теорії графів:

    Мал. 1. Мережа топології «дерево»

    Будемо вважати, що вузлу РС-1 відповідають висота підвісу антени Ну і вершина; вузлу РС-2 - h2, V2; ..., вузлу РС-6 -

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

    кінцівка

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

    зв'язаність

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

    Для неорієнтованих графів можна визначити матрицю суміжності вершин. Матриця суміжності графа Про з кінцевим числом вершин М (пронумерованих від одиниці до М) - це квадратна матриця Асмежності розміру М х М, в якій значення елемента ту дорівнює числу ребер, проведених з вершини Ь в вершину] [7, 8]. матриця

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

    На рис. 2 приведена матриця суміжності, відповідна топології мережі, зображеної на рис. 1.

    Перетворимо матрицю A

    суміжності

    Du

    , на основі наступних правил:

    d0 = 0; d0 • = ж, якщо немає ребра між вершинами.

    Матриця D0 для графа, зображеного на рис. 1, наведена на рис. 3.

    A

    суміжності

    'І 1 0 0 0 0

    1 0 1 1 0 0

    10 110 0

    0 1 0 0 0 0

    0 0 0 1 0 0

    v0 0 0 1 0 0,

    Мал. 2. Матриця A суміжності графа зображеного на рис. 1

    f 0 1

    D0

    Ю Ю Ю Ю

    Л

    10 1 + 1 ю Ю

    Ю 1 0 Ю Ю Ю Ю 1 Ю 0 11

    Ю Ю Ю 1 Ю Ю

    Ю Ю Ю 1 Ю 0

    Мал. 3. Матриця D0 для графа, зображеного на рис. 1

    Побудуємо матрицю D1, тобто Dm + 1, обчислюючи її елементи в такий спосіб:

    4j = min (dk, 4s +!) + D (k + 1) j), (3)

    де dfi = 0; k - номер кроку обчислення k = 1 .. .M .

    Повторимо обчислення матриці Dk, k = 1 ... M (пункт 3) M раз.

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

    Матриця DM для графа, зображеного на рис. 1, наведена на рис. 4:

    M

    f0 1 2 2 3 31

    1 1 1 2 2

    2 1 2 3 3

    2 1 2 1 1

    3 2 3 1 2

    ,3 2 3 1 2

    D

    Мал. 4. Матриця DM для графа, зображеного на рис. 1

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

    4 = про.

    ациклічності

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

    Кожне дерево з N вершинами має в точності N -1 ребро. Отже, перевіривши кінцівку і зв'язаність графа, досить кількість ребер порівняти з кількістю вершин графа [7].

    Для отримання кількості ребер в графі необхідно порахувати кількість одиничних елементів в матриці суміжності графа вище або нижче головної діагоналі. Для розглянутого прикладу топології мережі (див. Рис. 1) і матриці суміжності M (див. Рис. 2) число ребер графа становить п'ять.

    програмна реалізація

    На основі виконаних досліджень була доопрацьована динамічно підключається LibProfil.dll, розглянута в [1]. Динамічна бібліотека реалізує можливість створення модульних програм, коли код додатка розподіляється між різними динамічними бібліотеками dll. Такий поділ дозволяє оперативно змінювати необхідні частини програмного коду. Динамічна бібліотека також має можливість підключення до різнотипним додатків.

    В динамічну бібліотеку LibProfil.dll додані наступні функції:

    - створення і редагування топології мережі;

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

    - вибір типових рішень при симетричних профілях інтервалів;

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

    Варто відзначити, що в разі симетричних профілів функція Sс|уM (Hl ^ м) має мінімум на інтервалі, що призводить до виникнення інтервалу значень висот підвісу антен, при яких досягається мінімум функції Sj ^ Hi.m). У бібліотеці

    LibProfil.dll реалізований алгоритм вибору середніх значень висот підвісу антен з допустимого інтервалу.

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

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

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

    - задавати довільну кількість станцій системи;

    - задавати допустимий відсоток зони закриття зони Френеля;

    - задавати частоту роботи мережі;

    - на основі станцій системи створювати різні топології мережі (без наявності кілець);

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

    - виробляти оптимізацію висот підвісу антен по сумарній висоті необхідних АМС або за сумарною вартістю необхідних АМС;

    - виводити проміжні та кінцеві результати роботи в зовнішні файли.

    висновки

    В рамках даної статті були твори розробка і тестування алгоритму розрахунку оптимальних висот підвісу антен для мережі топології «дерево».

    Розглянемо основні переваги та недоліки розробленого алгоритму.

    Розроблений алгоритм дозволяє виробляти оптимізацію висот підвісу антен на основі цільової функції S. В якості цільової функції у вигляді сумарно ви-

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

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

    На основі динамічно підключається бібліотеки LibProfil.dll була розроблена комп'ютерна програма «оптимізатор висот антен» по оптимізації висот підвісу антен.

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

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

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

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

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

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

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

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

    література

    1. Терехов А.В. Алгоритм оптимізації висот підвісу антен в мережах з топологією «зірка» // Доповіді ТУСУРа. - 2010. - № 2 (22), ч. 1. - С. 236-243.

    2. Данилович О.С. Комплексна оптимізація вибору антен і висоти підвісу на многоінтервальних цифрових РРЛ / О.С. Данилович, Д.А. Сартбаев, А.Ю. Гумбіанс // Електрозв'язок. - 2003. - № 6. - С. 35-37.

    3. Данилович О.С. Оптимізація висот підвісу антен на многоінтервальних цифрових РРЛ / О.С. Данилович, М.А. Сіверс, С.П. Зайцев // Електрозв'язок. - 2008. - № 7. -С. 36-38.

    4. Система планування радіозв'язку RPS-2: Керівництво користувача. - М .: ЦКТ Силікон Телеком Софт, 2001. - 80 с.

    5. Програмний комплекс «Територія». Інструкція користувача. - СПб .: ЗАТ Ін-формаційний космічний центр «Північна Корона», 2009. - 72 с.

    6. Тіміщенко М.Г. Проектування радіорелейних ліній: навч. посібник для технікумів. - М .: Связь, 1976. - 240 с.

    7. Басскер Р. Кінцеві графи і мережі / Р. Басскер, Т. Сааті. - М .: Наука, 1974. -367 с.

    8. Берж К. Теорія графів та її застосування. - М .: Изд-во іноземної літератури, 1962. - 320 с.

    Терехов Олександр Вікторович

    Аспірант кафедри. комп'ютерних систем в управлінні і проектуванні (КСУП) ТУСУРа

    Тел .: 8-960-973-58-24

    Ел. пошта: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    Шуригін Юрій Олексійович

    Д-р техн. наук, проф., ректор, зав. каф. КСУП, директор НДІ автоматики та електромеханіки ТУСУРа Тел .: (382-2) 51-05-30 / факс: (382-2) 51-32-62 Ел. пошта: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    Terehov A.V., Shurygin Yu.A.

    An optimization algorithm of antennas heights in the star topology networks

    The synthesis problems of an algorithm intended for the optimum antennas heights calculation in the star topology radio communication networks are discussed in two ways: by total height of the antenna construction and by its total cost.

    Keywords: star topology radio communication networks, optimization of antennas heights, total height optimization, total cost of the antenna construction.


    Ключові слова: мережі радіозв'язку топології "дерево" /оптимізація висот підвісу антен /оптимізація за сумарною висоті і вартості антенно-щоглового споруди /графи /зв'язаність

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

    Завантажити