Спосіб розподілу частотних каналів в багатоканальній mesн-мережі стандарту іеее 802.11 для забезпечення їх структурної самоорганізації

Реферат: Спосіб розподілу частотних каналів в багатоканальних mesh-мережах стандарту IEEE 802.11 для забезпечення їх структурної самоорганізації включає розподіл частотних каналів в meshмережах рахунок використання керуючої булевої змінної. Виділяють радіоінтерфейси на meshстанціях. Закріплюють за ними частотні канали. При цьому ураховують кількість використовуваних частотних каналів та кількість підтримуваних mesh-станцією радіоінтерфейсів. Здійснюють балансування mesh-станцій за доменами колізій. UA 71765 U (54) СПОСІБ РОЗПОДІЛУ ЧАСТОТНИХ КАНАЛІВ В БАГАТОКАНАЛЬНІЙ MESH-МЕРЕЖІ СТАНДАРТУ ІЕЕЕ 802.11 ДЛЯ ЗАБЕЗПЕЧЕННЯ ЇХ СТРУКТУРНОЇ САМООРГАНІЗАЦІЇ UA 71765 U UA 71765 U 5 10 15 20 25 30 35 40 45 50 Корисна модель належить до технологій управління мережними ресурсами (частотним ресурсом) безпроводових мереж і може знайти застосування на вузлах (маршрутизаторах, клієнтських станціях та ін.) безпроводової мережі. Відомий спосіб [див. Лемешко А. В., Гоголева М. А. Трехиндексная математическая модель распределения частотных каналов в многоканальных mesh-сетях // Збірник наукових праць «Моделювання та інформаційні технології» - К., 2009. - № 54. - С. 94-103], який дозволяє забезпечити узгоджене розв'язання задач виділення радіоінтерфейсів на mesh-станціях та закріплення за ними каналів, які не перекриваються; враховує кількість використовуваних каналів та кількість підтримуваних mesh-станцією радіоінтерфейсів тощо. Однак даний спосіб не враховує технологічні особливості мережі, які визначають дальність зв'язку, так як в даному способі вважається, що всі станції знаходяться в одній зоні стійкого прийому, в результаті цього не враховується територіальна розподіленість mesh-станцій та ефект «прихованої станції», який виникає для станцій, що знаходяться на перетині кількох зон стійкого прийому та є важливим фактором при побудові безпроводових мереж, а також в його основу покладена триіндексна математична модель, яка вимагає достатньо високої розрахункової потужності. Найбільш близьким по сукупності ознак є спосіб [див. Лемешко А. В., Гоголева М. А. Модель структурной самоорганизации многоканальной mesh-сети стандарта IEEE 802.11 [Электронный ресурс] // Проблеми телекомунікацій. - 2010. - № 1 (1). - С. 83-95. - Режим доступа к журн.: http://pt.joumal.kh.ua/2010/1/1/101_lemeshko_mesh.pdf.], який вже дозволяє провести узгоджене розв'язання задач виділення радіоінтерфейсів на mesh-станціях, закріплення за ними каналів, які не перекриваються, з урахуванням таких особливостей мережі, як кількість використовуваних каналів та кількість підтримуваних mesh-станцією радіоінтерфейсів; здійснити балансування mesh-станцій за доменами колізій з урахуванням їх територіальної розподіленості; позбавитись ефекту «прихованої станції». Однак в основу даного способу покладена триіндексна математична модель, для забезпечення роботи якої в режимі реального часу необхідно забезпечити високу розрахункову потужність, а також не повною мірою забезпечується зв'язність між собою створюваних доменів колізій, що в результаті вирішення задачі розподілу частотних каналів може привести до створення декількох підмереж не зв'язних між собою. В основу корисної моделі поставлена задача розподілу частотних каналів між окремими радіоінтерфейсами станцій в багатоканальних mesh-мережах шляхом отримання рішення комплексного характеру щодо декомпозиції багатоканальної мережі на зв'язні між собою домени колізій, в рамках яких mesh-станції працюють на одному частотному каналі, з урахуванням територіальної розподіленості mesh-станцій. Поставлена задача вирішується тим, що у способі розподілу частотних каналів в багатоканальних mesh-мережах стандарту IEEE 802.11 для забезпечення їх структурної самоорганізації, що полягає в узгодженому вирішенні задачі розподілу частотних каналів в mesh-мережах в сукупності, тобто одночасно здійснюється комплексне вирішення таких задач, як виділення радіоінтерфейсів на mesh-станціях, закріплення за ними частотних каналів, які не перекриваються, з урахуванням таких особливостей мережі, як кількість використовуваних частотних каналів та кількість підтримуваних mesh-станцією радіоінтерфейсів, здійснює балансування mesh-станцій за доменами колізій з урахуванням їх територіальної розподіленості, позбавляє від ефекту «прихованої станції в мережі», що сприяє мінімізації кількості станцій, які працюють на одному частотному каналі, тобто знаходяться в одному домені колізій, що відповідно до корисної моделі дозволяє вирішувати задачу розподілу частотних каналів в mesh-мережі за рахунок використання керуючої булевої змінної, яка включає два індекси: номер станції та номер частотного каналу, для зменшення розрахункової складності математичної моделі, гарантує зв'язність створюваних доменів колізій між собою. Спосіб можна реалізувати наступний чином. У рамках запропонованої корисної моделі буде використано поняття зони стійкого прийому (Transmission Range, TR), яка утворюється безліччю mesh-станцій максимальної потужності, які можуть обмінюватися інформацією (пакетами) з використанням вибраної в mesh-мережі технології безпроводового зв'язку. У рамках запропонованої корисної моделі будуть використані наступні вихідні дані: Rn, n  1, N - безліч mesh-станцій, де N - їх загальна кількість в mesh-мережі; K - загальна кількість ЧК, що не перекриваються, які використовуються в mesh-мережі (у технології IEEE 802.11b/g таких ЧК , 3  4 , а в технології IEEE 802.11a - 12); Gz , z  1 Z - безліч зон стійкого прийому, де Z - загальна  55    кількість зон стійкого прийому в mesh-мережі, Gz - потужність одного з підмножин, тобто число 1 UA 71765 U 5 mesh-станцій входять до складу z-ϊ TR; m - цілочисельний параметр, що характеризує n мінімально необхідну кількість ЧК, що не перекриваються, виділених для n-ї mesh-станції (як правило цей параметр дорівнює одиниці); mn - число підтримуваних РІ на n-й mesh-станції, яке, як правило, дорівнює 1 3 . В математичну модель введено поняття матриці зон стійкого прийому або TR-матриці, що дозволяє здійснювати облік територіальної віддаленості mesh-станцій у мережі. TR-матриця є прямокутної форми, кількість рядків якої відповідає числу зон стійкого прийому Z , а число стовпців відповідає загальному числу mesh-станцій N у мережі, і має вигляд   D  dz,n , z  1 Z, n  1 N , , , 10 15 , 1 якщо n  та станціяналежить z  й TR; 0, в іншому випадку.  де dz,n   Задача розподілу частотних каналів, у вказаному способі, представлена у вигляді оптимізаційної задачі балансування числа mesh-станцій за числом створюваних кластерів, якими відповідно до використовуваної технології безпроводового зв'язку та використовуваного номера частотного каналу визначають відповідні домени колізій. В рамках запропонованої моделі, як керуюча використовується булева змінна xn,k  0,1 n  1 N, k  1 K , (1) , ,   ує ; 0, якщо n  та станціяне використов k  й канал  де xn,k   1, якщо k  й канал на n  й станції закреплений  тільки за одним з PI.  20 Структура розроблюваної математичної моделі буде визначатись за рахунок виконання наступних умов обмежень: 1. Умова включення n-ї станції в мережу:  xn,k  m n  1,N, (2) n K k 1 K де 1  m  mn,  xn,k - кількість ЧК виділених для роботи однієї станції. n k 1 2. Умова виділення n-й станції кількості ЧК, що не перевищує кількості РІ:  xn,k  mn n  1,N. (3) K k 1 25 3. Умова роботи двох mesh-станцій одна з одною не більше ніж на одному ЧК (в рамках однієї зони стійкого прийому):  xn,k xs,k   1 , (для (n,s)-пари станцій, K k 1 30 n, s  1 N, n, s  Gz , z  1 Z ), (4) , , яке вводиться для усунення небажаної структурної збитковості. 4. Умова того, що довільна mesh-станція на використовуваному на ній ЧK працює хоча б з однією станцією своєї TR: xn,k   xs,k n, s  Gz , z  1, Z, k  1,K  , (5) N s 1 s n N де  x s,k - число станцій у зоні стійкого прийому Gz (без врахування n-ї станції), які s 1 s n 35 працюють на k-му каналі. 5. Умова відсутності ефекту «прихованої станції», тобто станція, яка належить одночасно до кількох зон стійкого прийому, не повинна працювати на одному і тому ж ЧК із станціями різних зон стійкого прийому: N N s1 r 1 dz,ndq,nxn,k  xs,k  xr,k  0 , (6) при умові, що n  1, N, k  1, K, z, q  1, Z, s  Gz , r  Gq, s  Gq, r  Gz , n  s  r. 6. Умова зв'язності mesh-мережі (доменів колізій) в кожній зоні стійкого прийому: 2 UA 71765 U K N   k 1nGz n 1   xn,k  Gz  K  1  b z  1 Z , (7) ,  K  N, якщо K  Gz ; 0, в протилежному випадку.  де b   5 Так як кількість використовуваних ЧК у зоні стійкого прийому не може перевищувати число станцій, що входять до її складу, параметр b дозволяє зменшити це число ЧК до допустимого значення. 7. Умова роботи однієї з mesh-станцій, що знаходяться на перетині декількох зон стійкого прийому на двох ЧК:   dz,ndq,nxn,k    dz,ndq,n   1 z, q  1, Z, z  q , (8) K N k 1n1 K N де N n1   dz,ndq,nxn,k  - число ввімкнених РІ на mesh-станціях, які знаходяться на перетині зон k 1n1 10 стійкого прийому z та q ;  dz,ndq,n  - число mesh-станцій, що знаходяться на перетині зон стійкого прийому N z та q . n1 8. Умова того, що одна зі станцій, що знаходиться на перетині двох зон стійкого прийому та працює на двох ЧК, повинна працювати на цих каналах в різних зонах стійкого прийому: N N N  N dz,ndq,nxn,k xn,h   dz,s xs,k    dz,s xs,h  dq,r xr,k   dq,r xr,h   s 1 r 1  s1  r 1  15      0 (9)   при умові, що dz,sdq,s  0, dz,r dq,r  0, k, h  1, K, k  h, z  q, n  s  r ; dz,s  dq,s  0 - станція s не знаходиться на перетині зон стійкого прийому z та q . 20 25 Виконання цієї умови спільно з (4)-(8) гарантує, що кількість включених РІ з урахуванням числа mesh-станцій і підтримуваних в технології безпроводового зв'язку ЧК, що не перекриваються, забезпечить зв'язність багатоканальної mesh-мережі. У зв'язку з тим, що продуктивність безпроводової mesh-мережі буде залежати від розмірів доменів колізій (кількості mesh-станцій, що входять до їх складу), доцільно провести балансування кількості станцій по створюваним доменам колізій, з метою забезпечення їх рівномірного розподілу. 9. Умова балансування числа mesh-станцій за доменами колізій у залежності від їх територіального розподілу та кількості зон cтійкого прийому має вигляд:  dz,nxn,k    (для кожної (z,k)-пари, N z  1 Z, k  1 K , (10) , , n1 30 де в лівій частині нерівності представлено число mesh-станцій в z-й зоні стійкого прийому, що працюють на k-му ЧК,  - верхній динамічно керований поріг числа mesh-станцій в довільно вибраному домені колізій в багатоканальній mesh-мережі. В результаті цього, в рамках запропонованої математичної моделі (1)-(9), вирішення оптимізаційної задачі буде здійснюватись з використанням наступного критерію: min (11) x, 35 40 45 Сформульована задача з точки зору фізики процесів, які відбуваються у багатоканальних mesh-мережах, належить до класу задач балансування мережних ресурсів - балансування числа mesh-станцій по створюваним доменам колізій, а з математичної точки зору вона відноситься до задач змішаного цілочисельного нелінійного програмування (Mixed Integer Nonlinear Programming, MINLP). В рамках запропонованої моделі забезпечується узгодженість вирішення задач кластеризації, виділення радіоінтерфейсів і закріплення за ними каналів, відсутність ефекту «прихованої станції», а також гарантується зв'язність створюваних доменів колізій. Таким чином, запропоновано корисну модель розподілу частотних каналів у багатоканальних mesh-мережах стандарту IEEE 802.11 на основі двоіндексної математичної моделі, яка дозволяє провести балансування mesh-станцій з урахуванням їх територіального розподілу, новизна якої полягає у забезпеченні більш низької розрахункової складності, у порівнянні з відомими способами, а також гарантії зв'язності створюваних доменів колізій. 3 UA 71765 U ФОРМУЛА КОРИСНОЇ МОДЕЛІ 5 10 15 Спосіб розподілу частотних каналів в багатоканальних mesh-мережах стандарту IEEE 802.11 для забезпечення їх структурної самоорганізації полягає в узгодженому вирішенні задачі розподілу частотних каналів в mesh-мережах в сукупності, тобто одночасно здійснюється комплексне вирішення таких задач, як виділення радіоінтерфейсів на mesh-станціях, закріплення за ними частотних каналів, які не перекриваються, з урахуванням таких особливостей мережі, як кількість використовуваних частотних каналів та кількість підтримуваних mesh-станцією радіоінтерфейсів, здійснює балансування mesh-станцій за доменами колізій з урахуванням їх територіальної розподіленості, позбавляє від ефекту "прихованої станції в мережі", що сприяє мінімізації кількості станцій, які працюють на одному частотному каналі, тобто знаходяться в одному домені колізій, який відрізняється тим, що дозволяє вирішувати задачу розподілу частотних каналів в mesh-мережі за рахунок використання керуючої булевої змінної, яка включає два індекси: номер станції та номер частотного каналу, для зменшення розрахункової складності математичної моделі, гарантує зв'язність створюваних доменів колізій між собою. Комп’ютерна верстка M. Мацело Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 4