Є.В. Нікітенко, канд. фіз.-мат. наук

Чернігівський державний технологічний університет, м. Чернігів, Україна

АЛГОРИТМ АВТОМАТИЗОВАНОГО ПЛАНУВАННЯ БЕЗДРОТОВОЇ СЕНСОРНОЇ МЕРЕЖІ З ВРАХУВАННЯМ ЗАЙНЯТИХ ДІЛЯНОК ПРОСТОРУ

Досліджено методи позиціонування вузлів бездротової сенсорної мережі (БСМ). Розглянуто існуючі алгоритми планування БСМ. Запропоновано алгоритм автоматизованого планування БСМ із врахуванням ділянок, де неможливо або дуже складно розмістити вузли мережі.

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

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

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

Аналіз досліджень і публікацій. Як відомо, вузол у мережі ZigBee може виконувати одну із трьох ролей: кінцевого пристрою, ретранслятора або координатора [1].

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

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

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

Проектування системи моніторингу вимагає автоматизованого планування топологічної структури БСМ. Відомі сьогодні підходи до проектування топологічної структури бездротових сенсорних мереж із використанням математичного моделювання базуються на використанні апарату комбінаторного аналізу та обтяжені значними затратами ресурсів, які збільшуються за експонентою під час зростання числа вузлів БСМ [2; 3]. Це обтяжує використання таких методів для проектування мереж великої розмірності. Разом з тим, простий розрахунок позицій ретрансляторів на базі тривимірної геометрії і динамічного програмування [4] виявляється малоефективним у тих випадках, де треба враховувати зайняті ділянки простору.

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

Основні аналітичні залежності. Умови задачі оптимального розміщення ретрансляторів мережі подібні до умов транспортної задачі. За критерій оптимальності взято мінімальну кількість ретрансляторів, що здатні забезпечити передачу даних від кінцевих пристроїв до координатора БСМ. Для вирішення подібних задач зазвичай використовується підхід динамічного програмування [5; 6], оскільки він має ітеративний характер та дозволяє розбивати задачу на підзадачі меншого розміру, рішення яких можна використати для рішення основної задачі.

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

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

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

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

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

Далі треба знайти для кожної із сукупностей точок стартову точку . Стартова точка – це точка координатної сітки, де можна встановити ретранслятор, який буде знаходитися близько від сукупності кінцевих точок у напрямку координатора мережі (рис. 1).

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

, (1)

де - координата стартової точки для пошуку позиції ретранслятора;

- мінімальна координата серед усіх елементів множини ;

- максимальна координата серед усіх елементів множини ;

та - квантовані мінімальні і максимальні значення координат точок множини відповідно;

- координата координатора мережі.

Рис. 1. Визначення координат ретранслятора

Аналогічні формули можна записати для координат та .

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

(2)

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

Наближення координати направляючої осі ретранслятора до координати координатора БСМ на величину відбувається постійно до того часу, доки:

1) відстань між будь-якою точкою із множини і ретранслятором не більша за ;

2) відстань між і стане меншою, ніж ;

3) на шляху руху точки трапиться зайнята ділянка.

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

З рисунка 1 видно, що

. (3)

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

. (4)

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

 

Рис. 2. Алгоритм обходу зайнятих ділянок простору

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

Висновки. На основі аналізу існуючих методів позиціонування вузлів бездротових сенсорних мереж та підходу динамічного програмування розроблено алгоритм планування позицій ретрансляторів БСМ із врахуванням зайнятих ділянок простору. Цей алгоритм полягає в поступовому наближенні ретранслятора до своєї ідеальної позиції і не використовує прямих формул тривимірної геометрії для обчислення позиції вузла мережі [4].

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

Список використаних джерел

1. Интеллектуальные системы на базе сенсорных сетей // Институт точной механики и вычислительной техники им. С. А. Лебедева РАН, 2009. – 10 c.

2. Акимов Е. В. Сравнение топологий беспроводных сенсорных сетей (БСС) / Е. В. Акимов // Вестник компьютерных и информационных технологий. – М.: Машиностроение, 2008. – № 8, С. 43-49.

3. Акимов Е. В. Проектирование рациональной топологии беспроводных сенсорных сетей: автореф. дис. канд. техн. наук Е. В. Акимов. – М., 2010. – 22 с.

4. Нікітенко Є. В. Система автоматизованого проектування бездротових систем моніторингу / Є. В. Нікітенко, Д. В. Стрелок // Вісник Чернігівського державного технологічного університету. – 2010. – № 45. – С. 152-158.

5. Беллман Р. Динамическое программирование / Р. Беллманн. - М.: Изд-во иностранной литературы, 1960. – 401 с.

6. Щербина О. А. Методологические аспекты динамического программирования / О. А. Щербина // Динамические системы. - 2007. - Вып. 22. – С. 21-36.