Optimal placement of a multi-sensor system

We consider the mathematical models for underwater acoustic sensors, the algorithm for threat detection by a multisensory system, optimization problems for placement of such systems. The mathematical methods for optimal sensor placement have been developed. The limit theorem on optimality of sensor...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2018
Автор:	Pashko, S.V.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут програмних систем НАН України 2018
Теми:	sensor multisensory system algorithm for threat detection optimal sensor placement asymptotic optimality UDC 519.1
Онлайн доступ:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/276
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Problems in programming
Завантажити файл:

Репозитарії

Problems in programming

id	pp_isofts_kiev_ua-article-276
record_format	ojs
resource_txt_mv	ppisoftskievua/5a/7f342f17daf2abf2abf5a5e71372405a.pdf
spelling	pp_isofts_kiev_ua-article-2762024-04-28T11:37:23Z Optimal placement of a multi-sensor system Оптимальное размещение многосенсорной системы Оптимальне розміщення багатосенсорної системи Pashko, S.V. sensor; multisensory system; algorithm for threat detection; optimal sensor placement; asymptotic optimality UDC 519.1 сенсор; многосенсорная система; алгоритм детектирования угрозы; оптимальное размещение сенсоров; асимптотическая оптимальность УДК 519.1 сенсор; багатосенсорна система; алгоритм детектування загрози; оптимальне розміщення сенсорів; асимптотична оптимальність УДК 519.1 We consider the mathematical models for underwater acoustic sensors, the algorithm for threat detection by a multisensory system, optimization problems for placement of such systems. The mathematical methods for optimal sensor placement have been developed. The limit theorem on optimality of sensor placement has been proved. Numerical experiments have demonstrated that the algorithm outperformsexisting mathematical method for optimal sensor placement.Problems in programming 2018; 2-3: 140-148 Описан алгоритм детектирования подводной угрозы с помощью системы акустических сенсоров, а также экстремальные задачи размещения сенсоров. Рассмотрены методы решения таких задач, доказана теорема об асимптотической оптимальности построенных планов размещения сенсоров. Из результатов численных экспериментов следует, что построенный метод превосходит известный метод решения задач размещения сенсоров.Problems in programming 2018; 2-3: 140-148 Описано алгоритми детектування підводної загрози за допомогою системи акустичних сенсорів, екстремальні задачі розміщування сенсорів. Розглянуто методи розв’язання таких задач та теореми про асимптотичну оптимальність побудованих планів розміщення сенсорів. З результатів числових експериментів випливає, що побудований метод перевершує відомий метод розв’язання задачрозміщування сенсорів.Problems in programming 2018; 2-3: 140-148 Інститут програмних систем НАН України 2018-11-05 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/276 10.15407/pp2018.02.140 PROBLEMS IN PROGRAMMING; No 2-3 (2018); 140-148 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2018); 140-148 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2018); 140-148 1727-4907 10.15407/pp2018.02 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/276/270 Copyright (c) 2018 PROBLEMS OF PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2024-04-28T11:37:23Z
collection	OJS
language	Ukrainian
topic	sensor multisensory system algorithm for threat detection optimal sensor placement asymptotic optimality UDC 519.1
spellingShingle	sensor multisensory system algorithm for threat detection optimal sensor placement asymptotic optimality UDC 519.1 Pashko, S.V. Optimal placement of a multi-sensor system
topic_facet	sensor multisensory system algorithm for threat detection optimal sensor placement asymptotic optimality UDC 519.1 сенсор многосенсорная система алгоритм детектирования угрозы оптимальное размещение сенсоров асимптотическая оптимальность УДК 519.1 сенсор багатосенсорна система алгоритм детектування загрози оптимальне розміщення сенсорів асимптотична оптимальність УДК 519.1
format	Article
author	Pashko, S.V.
author_facet	Pashko, S.V.
author_sort	Pashko, S.V.
title	Optimal placement of a multi-sensor system
title_short	Optimal placement of a multi-sensor system
title_full	Optimal placement of a multi-sensor system
title_fullStr	Optimal placement of a multi-sensor system
title_full_unstemmed	Optimal placement of a multi-sensor system
title_sort	optimal placement of a multi-sensor system
title_alt	Оптимальное размещение многосенсорной системы Оптимальне розміщення багатосенсорної системи
description	We consider the mathematical models for underwater acoustic sensors, the algorithm for threat detection by a multisensory system, optimization problems for placement of such systems. The mathematical methods for optimal sensor placement have been developed. The limit theorem on optimality of sensor placement has been proved. Numerical experiments have demonstrated that the algorithm outperformsexisting mathematical method for optimal sensor placement.Problems in programming 2018; 2-3: 140-148
publisher	Інститут програмних систем НАН України
publishDate	2018
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/276
work_keys_str_mv	AT pashkosv optimalplacementofamultisensorsystem AT pashkosv optimalʹnoerazmeŝeniemnogosensornojsistemy AT pashkosv optimalʹnerozmíŝennâbagatosensornoísistemi
first_indexed	2024-09-16T04:08:26Z
last_indexed	2024-09-16T04:08:26Z
_version_	1818568425789718528
fulltext	Моделі та засоби систем баз даних і знань © С.В. Пашко, 2018 140 ISSN 1727-4907. Проблеми програмування. 2018. № 2–3. Спеціальний випуск УДК 519.1 ОПТИМАЛЬНЕ РОЗМІЩЕННЯ БАГАТОСЕНСОРНОЇ СИСТЕМИ С.В. Пашко Описано алгоритми детектування підводної загрози за допомогою системи акустичних сенсорів, екстремальні задачі розміщування сенсорів. Розглянуто методи розв’язання таких задач та теореми про асимптотичну оптимальність побудованих планів розміщення сенсорів. З результатів числових експериментів випливає, що побудований метод перевершує відомий метод розв’язання задач розміщування сенсорів. Ключові слова: сенсор, багатосенсорна система, алгоритм детектування загрози, оптимальне розміщення сенсорів, асимптотична оптимальність. Описан алгоритм детектирования подводной угрозы с помощью системы акустических сенсоров, а также экстремальные задачи размещения сенсоров. Рассмотрены методы решения таких задач, доказана теорема об асимптотической оптимальности построенных планов размещения сенсоров. Из результатов численных экспериментов следует, что построенный метод превосходит известный метод решения задач размещения сенсоров. Ключевые слова: сенсор, многосенсорная система, алгоритм детектирования угрозы, оптимальное размещение сенсоров, асимптотическая оптимальность. We consider the mathematical models for underwater acoustic sensors, the algorithm for threat detection by a multisensory system, optimization problems for placement of such systems. The mathematical methods for optimal sensor placement have been developed. The limit theorem on optimality of sensor placement has been proved. Numerical experiments have demonstrated that the algorithm outperforms existing mathematical method for optimal sensor placement. Key words: sensor, multisensory system, algorithm for threat detection, optimal sensor placement, asymptotic optimality. Вступ В роботі розглядається система акустичних сенсорів, призначена для виявлення підводної загрози в деякій обмеженій акваторії, що прилягає до важливих народногосподарських об’єктів. Описуються екстремальні задачі та методи їх розв’язання для пошуку оптимального розміщення сенсорів у межах заданої акваторії. Очевидно, такі задачі є актуальними у зв’язку із зростанням терористичних небезпек. Під час конструювання багатосенсорних систем виникають різноманітні екстремальні задачі, що вирішуються за допомогою відповідних математичних методів. В роботі [1] задача розміщування підводних акустичних сенсорів формулюється у вигляді задачі стохастичного програмування, в якій шум є випадковою величиною. Описано алгоритм обробки сигналів та тест для визначення кількості порушників-дайверів. Для виявлення числа дайверів застосовується теорія прихованих ланцюгів Маркова. В роботі [2] задача оптимального розміщування підводних сенсорів вирішується за допомогою генетичного алгоритму. Враховуються різноманітні характеристики оточуючого середовища: глибина, температура, солоність води, pH. В роботі [3] для розміщування вузлів сенсорної мережі на морському дні використовується самоорганізаційна карта Кохонена, що являє собою нейронну мережу з навчанням. Побудований на основі самоорганізаційної карти метод дозволяє відсіювати неефективні вузли мережі. В роботі [4] розглянуто задачу розміщування сенсорів, у якій оптимізується покриття деякої області. Запропоновано два жадібних алгоритми для оптимізації середнього значення покриття або покриття у найгіршому випадку. В роботі [5] розглядається час роботи сенсорної системи, що залежить від енергетичних обмежень. Запропоновано алгоритм розміщування сенсорів, що враховує допустимий час їх роботи. Для системи мобільних сенсорів в роботах [6, 7] побудовано алгоритм покращення розміщення сенсорів після випадкового розміщування. Алгоритм оптимізує покриття території сенсорами за умов обмеженості відстаней, які можуть бути ними пройдені. В роботі [8] сформульовано задачі розміщування підводних сенсорів, розглянуто методи їх розв’язання та наведено численний список використаної літератури. В роботі [9] розглядаються способи розміщування сенсорів, що є близькими до регулярного. Область спостереження покривається множиною правильних геометричних фігур (правильних трикутників, квадратів, правильних шестикутників), сенсори як правило розміщуються у вершинах цих фігур. Сенсори вважаються однотипними. Оскільки область спостереження є зашумленою, для надійного тестування потрібна велика щільність сенсорів. Доведено теорему про те, що при зростанні кількості сенсорів вказаний спосіб розміщення наближується до оптимального. Числові експерименти демонструють, що запропонований алгоритм розміщування перевершує алгоритм, побудований в [4], навіть якщо оптимальне число сенсорів відносно мале. На відміну від роботи [9], в даній статті розглядаються сенсори з різними можливостями. У відповідності з цим формулюються екстремальні задачі та будуються їх розв’язки. 1. Математичні моделі сенсорів і алгоритми детектування загрози Припустимо, область спостереження W є мілководною; в такому разі її можна вважати двовимірною. Вважаємо, що може бути тільки одна можлива загроза, тобто один порушник. Позначимо 0H гіпотезу, яка Моделі та засоби систем баз даних і знань 141 стверджує, що в області W не існує порушника. Нехай 1H – гіпотеза, яка стверджує, що в області W існує один порушник. Позначимо )(1 YH гіпотезу про те, що порушник знаходиться в точці .WY Припустимо, в області W розміщені n сенсорів у точках .,...,1 nXX Нехай jS – дійсна випадкова величина, що є результатом обробки сигналу сенсором j, ),...,( 1 nSSS  – випадковий вектор. Позначимо ),...,( 1 nsss  спостереження вектора S в деякий момент часу. Вважаємо, що існує агент, який посилає запити на всі сенсори, отримує від них інформацію у вигляді вектора ),,...,( 1 nsss  на основі якої приймає рішення про справедливість гіпотези 0H або гіпотези ).(1 YH Позначимо )( jSP розподіл ймовірностей величини jS у випадку, якщо jS є дискретною випадковою величиною. Якщо jS неперервна, то )( jSP являє собою щільність розподілу ймовірностей для jS (в такому випадку вважаємо, що щільність розподілу існує). Аналогічно позначимо )(SP розподіл ймовірностей випадкового вектора S. Для кожного значення s та Y розглянемо умовні ймовірності (щільності) для кожної з гіпотез ),\|( 0HsPS )).(\|( 1 YHsPS Вважаючи, що випадкові величини jS є незалежними за умов 0H або ),(1 YH отримуємо ,)\|()\|( 1 00    n j jSS HsPHsP j .))(\|())(\|( 1 11    n j jSS YHsPYHsP j Математична модель сенсора j повністю визначається розподілами ),\|( 0HsP jS j )),(\|( 1 YHsP jS j (1) які залежать від статистичних властивостей шуму оточуючого середовища, інтенсивності сигналу, технічних характеристик сенсора, метода обробки сигналу. Нехай ),,( jjj yxX  ),,( yxY  22 )()( yyxxYXd jjjj  – відстань між ціллю та j-м сенсором. Розглянемо дві математичні моделі сенсора, що конкретизують модель (1). Символом P далі позначається ймовірність. МОДЕЛЬ 1. Вихідний сигнал сенсора j являє собою бінарну випадкову величину, }.1,0{jS Величина jS приймає значення 1, якщо сенсор детектує загрозу, та 0 в іншому випадку. Ймовірності детектування порушника для гіпотез )(, 10 YHH визначаються формулами ),())(\|1( 11 jj dfYHSP  ,)\|1( 0  HSP j (2) де )(1 jdf – монотонно незростаюча функція, .1)(0 1  jdf МОДЕЛЬ 2. Вихідний сигнал сенсора j являє собою нормально розподілену випадкову величину,      ,умовиза ),(умовиза)( 0 12 H YHdf S j j   (3) де       ,/,0 ,/, )(2 jjj jjjjjj j bad baddba df (4) 0,0  jj ba – константи, що залежать від технічних характеристик сенсора, )(2 jdf – сигнал від цілі,  – шум, ).,(~ 2 N В роботі [10] описані закони розповсюдження сигналів у водному середовищі з врахуванням шумів, на основі яких побудовано наведені моделі. Опишемо одноперіодний алгоритм детектування загрози, що використовує сигнали сенсорів, отримані в деякий момент часу t. Почнемо з простого випадку, коли або порушника немає в області W, або він знаходиться в точці .WY Для виявлення загрози застосуємо тест Неймана – Пірсона, що використовує відношення правдоподібності Моделі та засоби систем баз даних і знань 142 . )\|( ))(\|( ),( 0 1 HsP YHsP YsR S S Приймається гіпотеза ),(1 YH якщо )(),( YYsR  для деякого значення ),(Y і гіпотеза 0H в іншому випадку. Поріг детектування )(Y визначається величинами ймовірностей помилок першого та другого родів, 0 та 1 відповідно. Обмеження на ймовірності помилок першого та другого роду приймають форму ,)\|)(),(( 00   HYYSRP .))(\|)(),(( 11   YHYYSRP (5) Припустимо, розподіл величини ),( YSR як за умови ,0H так і за умови )(1 YH є неперервним. Позначимо 0q квантиль рівня 01  розподілу величини ),( YSR за умови ;0H нехай 1q означає квантиль рівня 1 розподілу величини ),( YSR за умови ).(1 YH Співвідношення (5) можуть бути записані у вигляді .)( 10 qYq   Якщо ,10 qq  виберемо .2/)()( 10 qqY  Нерівність 10 qq  означає, що система не має удосталь сенсорів для виконання умов (5). Розглянемо випадок, коли або порушника немає в області W, або про нього відомо тільки те, що він знаходиться в області W. В такому випадку застосовуємо тест Неймана – Пірсона до кожної точки W (звичайно, під час числових розрахунків мова може йти тільки про скінчену множину точок, яка досить щільно покриває W). Обмеження (5), які стосуються помилок першого та другого родів, повинні виконуватись для всіх .WY Зауважимо, що в такому разі виникає наступна проблема. Ймовірність детектування загрози за умови її відсутності (тобто ймовірність помилки першого роду) може перевищити число ,0 що фігурує в (5). Ця ймовірність, ),\|)(),(:( 00 HYYsRWYP   може бути знайдена методом Монте-Карло. Величина 0 залежить від вибору числа .0 Припустимо, за умов справедливості гіпотез 0H або )(1 YH випадкові величини ,jS ,,...,2,1 nj  незалежні. Маємо    n j jj YSRYSR 1 ),,(ln),(ln де . )\|( ))(\|( ),( 0 1 HSP YHSP YSR jS jS jj j j  Для моделей сенсорів 1 і 2 величини ))(\|( 1 YHSP jS j та )\|( 0HSP jS j визначаються формулами (2) – (4). Для використання тесту Неймана – Пірсона необхідно знати розподіл випадкової величини    n j jj YSRYSR 1 ),(ln),(ln за умови справедливості гіпотез 0H та ).(1 YH З центральної граничної теореми теорії ймовірностей [11] випливає, що за умови Ліндеберга для досить великих значень n розподіл величини ),(ln YSR є близьким до нормального. У випадку використання сенсорної моделі 2 величина ),(ln YSR має нормальний розподіл, оскільки нормально розподіленими є величини .jS Модель 2 акустичного сенсора описана в роботі [9]. Там же описано багатоперіодний алгоритм детектування загрози. Такий алгоритм використовує дані, що надходять від сенсорів у послідовні моменти часу; водночас застосовується метод послідовного статистичного аналізу [12]. 2. Задачі оптимального розміщування сенсорів Припустимо, існує K типів сенсорів. Нехай kn – кількість сенсорів k-го типу, які планується розмістити в області W, kc – ціна сенсора k-го типу, kjX – вектор координат j-го сенсора k-го типу, ,WXkj  ,,...,2,1 Kk  .,...,2,1 knj  Розглянемо наступну задачу оптимального розміщення сенсорів: ,min 1 ,0    K k kk WXn nc kjk (6) Моделі та засоби систем баз даних і знань 143   ., 1 1 WYIXY K k n j kjk k     (7) Тут функція )(k характеризує надійність детектування загрози одним сенсором k-го типу, величина I означає задану надійність детектування системою сенсорів. Надійність може вимірюватись за допомогою різних величин, таких як кількість інформації, що надходить до сенсорів з точки Y тощо. Далі розглянемо формулювання задачі (6), (7) у випадку використання описаних вище моделей і алгоритмів виявлення загрози. Нехай використовується одноперіодний алгоритм детектування. Розглянемо задачу мінімізації вартості сенсорної системи за обмежень (5) на ймовірності помилок першого та другого роду ,min 1 ,0    K k kk WXn nc kjk (8) ,,)\|)(),(( 00 WYHYYSRP   (9) .,))(\|)(),(( 11 WYYHYYSRP   (10) Припустимо, в якості математичної моделі сенсора використовується модель 2. Нехай загальне число сенсорів дорівнює n і всі вони ідентичні. Нехай також  означає  -квантиль нормального розподілу ймовірностей. В роботі [9] показано, що задачу (8) – (10) можна записати у вигляді ,min n WX j (11) .,)()( 22 11 1 2 2 10 WYdf n j j       (12) Задача (11), (12) – окремий випадок задачі (6), (7), де )()( 2 2 dfdk  та .)( 22 11 10    I Цю задачу можна узагальнити на випадок існування кількох типів сенсорів. Якщо використовується багатоперіодний алгоритм детектування, то задача мінімізації вартості сенсорної системи за обмежень на середній час виявлення загрози та на ймовірність помилки першого роду записується у вигляді ,min 1 ,0    K k kk WXn nc kjk (13) ,)( maxTTE  (14) де T – кількість часу, що проходить від моменту, коли порушник з’явився в області W, до моменту його виявлення. В роботі [9] задача (13), (14) за деяких умов зведена до задачі (6), (7). Отже, розглянуті задачі є окремими випадками задачі (6), (7), яку можна звести до задачі булевого програмування наступним чином. Нехай },...,,{ 21 MZZZZ  – множина точок з області W таких, що для кожної точки WY  справедлива нерівність ,min ,...,1   m Mm ZY де .0 Нехай ,1mkjz якщо в точці ZZm  встановлюється сенсор типу k з номером };,...,2,1{ kNj 0mkjz в іншому випадку. Тут kN – максимально можливе число сенсорів типу k. Замість задачі (6), (7) розглянемо задачу ,min 1 1 1     M m K k N j mkjk z k mkj zc (15)   ,, 1 1 1      M m K k N j mkjmk k ZYIzZY (16) Моделі та засоби систем баз даних і знань 144 ,1 1   M m mkjz ,,...,2,1 Kk  ,,...,2,1 kNj  (17) },1,0{mkjz ,,...,2,1 Mm  ,,...,2,1 Kk  .,...,2,1 kNj  (18) Нерівності (17) гарантують, що кожен сенсор може знаходитись тільки в одній точці або може не бути задіяним. В одній точці дозволяється розміщувати один або кілька сенсорів. Задача (15) – (18) може бути розв’язана одним з числових методів булевого програмування. Далі розглянемо задачі, для розв’язання яких можна застосувати більш прості методи у порівнянні з методами загального призначення. Для таких задач вдається не тільки побудувати близькі до оптимальних розв’язки у вигляді числових векторів, але й дослідити їх властивості. Зокрема, розглянемо задачу ,min 1 ,,   n j j Xun uc jj (19)   ,, 1 WYIuXY n j jj    (20) ,,0,1 WXun jj  .,...,2,1 nj  (21) Тут ju – дійсне число, що характеризує ”потужність” j-го сенсора, n – кількість сенсорів, c – ціна одиниці ”потужності”, jX – вектор координат j-го сенсора. Якщо ,1ju отримуємо задачу ,min n jX (22)   ,, 1 WYIXY n j j    (23) ,,1 WXn j  .,...,2,1 nj  (24) В цій задачі вимагається мінімізувати кількість однотипних сенсорів, що розміщені в області W та забезпечують виконання нерівностей (23). 3. Регулярний спосіб розміщення сенсорів Розглянемо спосіб розміщення сенсорів у області W, який полягає в тому, що сенсори знаходяться в вершинах регулярної сітки, утвореної правильними трикутниками, квадратами або правильними шестикутниками (рисунок). Рисунок. Регулярні сітки для розміщування сенсорів Припустимо, для задачі (19) – (21) виконуються наступні умови. Функція ,0),( dd є незростаючою неперервною Ліпшицевою з константою 0L та приймає невід’ємні значення. Існує число 0r таке, що Моделі та засоби систем баз даних і знань 145 0)( d для ,0 rd  0)( d для ,rd  br)0( для деякої константи .0b Число r означає радіус дії сенсора. Припустимо, область W являє собою многокутник, всі кути якого не менші за .2/ Виконання останньої умови можна забезпечити, “зрізаючи” гострі кути, якщо вони є, та збільшуючи число сторін многокутника. Вважаємо, що .0I Наступний метод будує допустимий розв’язок ),...,,( 21 nXXXG  задачі (19) – (21), близький до оптимального. Розглянемо регулярну сітку S, сформовану правильними трикутниками, квадратами або правильними шестикутниками з довжиною сторони s (рисунок). Вважаємо, що .rs  Позначимо ,,)(:min            CYIXYuuu SYX  де SY – множина всіх вершин регулярної сітки S, C – регулярна фігура сітки (трикутник, квадрат або шестикутник). Позначимо )(1 rW множину точок ,WX  для яких відстань до межі множини W не менша за r. Нехай  ,,...,, 00 2 0 1 0nS XXXWYG   ),()( 11 rWGrG  ).(\)( 10 rGGrG  Виберемо число 4h та розглянемо розв’язок задачі (19) – (21), що визначається співвідношеннями ,0nn  ,0 jj XX  (25) .,...,2,1 ),(, ),(, 0 0 10 nj rGXuh rGXu uu j j jj        (26) Оскільки кути многокутника W не менші 2/ і ,4h то розв’язок (25), (26) – допустимий для задачі (19) – (21) за умови, що величини r та rs / досить малі. Позначимо ),(0 srf значення цільової функції задачі (19) – (21) для розв’язку (25), (26), .),( 0 1 00    n j jucsrf Нехай )(rf  – оптимальне значення цільової функції задачі (19) – (21). Наступна теорема стверджує, що розв’язок (25), (26) – асимптотично оптимальний. Теорема 1. Нехай LIW ,, залишаються незмінними, br)0( для деякої константи ,0b справедливі співвідношення .0/,0,0  rssr Тоді .1 )( ),(0   rf srf Доведення цієї теореми міститься в роботі [13]. З теореми 1 випливає, що розміщення сенсорів однакової “потужності” у вершинах регулярної сітки приводить до близьких до оптимальних розв’язків задачі (19) – (21). Тому далі вважаємо, що ,1ju та розглянемо задачу (22) – (24). 4. Числовий метод побудови близького до оптимального розміщення сенсорів В даному розділі розглянемо задачу (22) – (24) та відповідний числовий метод розміщування сенсорів у області W. Результатом роботи методу є план розміщення однотипних сенсорів, що задовольняє умовам (23), (24), та є асимптотично оптимальним розв’язком. Вважаємо, що область W, величина I та функція ,0),( dd задовольняють умовам, описаним у попередньому розділі. Ідея методу полягає в тому, що сенсори розміщуються в вершинах регулярної сітки, а на межі області W розміщуються додаткові сенсори. Розглянемо тільки регулярну сітку, утворену квадратами (рисунок). Числові методи для регулярних сіток, утворених правильними трикутниками або шестикутниками, будуються подібним способом. Позначимо Q регулярну сітку, утворену квадратами з довжиною сторони q, де .2/3qr  Нехай  QY – множина всіх вершин сітки Q,  QC – множина всіх квадратів C сітки Q, для яких виконується співвідношення ,int CW  де Cint – внутрішня частина множини C, Моделі та засоби систем баз даних і знань 146  QY ~ – множина всіх вершин сітки Q, що належать квадратам з множини .QC Позначимо )(00 rWW  множину точок ,WX  для яких відстань до межі множини W не більша за r. Нехай  0 QC – множина всіх квадратів C сітки Q, для яких виконується співвідношення ,int0 CW   0~ QY – множина всіх вершин сітки Q, що належать квадратам з множини .0 QC Подібним чином розглянемо сформовану квадратами із стороною s регулярну сітку S, для якої величина s визначається алгоритмом. Позначимо SY множину вершин сітки S. Вважаємо, що лінії сітки S паралельні або перепендикулярні лініям сітки Q і що множина вершин сітки S належить множині вершин сітки Q, тобто qs / є цілим числом. Наступний метод [9] будує допустимий розв’язок ),...,,( 21 nXXXG  задачі (22) – (24), близький до оптимального. 1) вирішимо задачу ,max s (27)   ,,2/ Q YX YCYIqXY S    (28) ,...},,...,2,1{/ nqs  (29) де змінна s є довжиною сторони квадрату сітки S і C є квадратом сітки S. Фіксуємо оптимальне значення змінної s і далі вважаємо, що сітка S утворена квадратами з довжиною сторін s. Виберемо .WYG S  (30) 2) якщо виконуються нерівності   , ~ ,2/ 0 Q GX YYIqXY    (31) роботу зупиняємо. 3) виберемо точку , ~ 0 QYY  що максимізує вираз  .2/   GX qXYI  Включимо в розв’язок G проекцію )(YW точки Y на множину W. Переходимо до 2). Зауважимо, що метод 1) – 3) скінчений. Дійсно, оскільки 2/3qr  і для кожної точки Y з множини 0~ QY справедлива нерівність ,2)( qYY W  значення     GX qXYI 2/ на кроці 3) для вибраної точки 0~ QYY  зменшується як мінімум на величину     .02/32/2  qqq  Оскільки множина 0~ QY скінчена, то нерівність (31) буде справедливою після скінченого числа ітерацій. Легко довести, що побудований методом 1) – 3) розв’язок ),...,,( 21 nXXXG  є допустимим розв’язком задачі (22) – (24), тобто   ., 1 WYIXY n j j    (32) Дійсно, для кожної точки WY  найближча до цієї точки вершина QYY  належить множині . ~ QY Якщо Моделі та засоби систем баз даних і знань 147 , ~ 0 QYY  то з (27) – (30) випливає   .2/ 1 IqXY n j j    (33) Якщо , ~ 0 QYY  то (33) випливає з (31). Оскільки функція )(d незростаюча та ,2/qYY  маємо     ,2/ 11 IqXYXY n j j n j j     звідки випливає (32). Зауважимо, що в задачі (22) – (24) не приймаються до уваги перешкоди, що можуть бути між сенсорами та ціллю в області W. Тому побудований розв’язок G можна вважати досить якісним тільки для випадків, коли область W є близькою до опуклої. Справедлива теорема про асимптотичну оптимальність побудованого методом 1) – 3) розв’язку G. Нехай )(rf  – оптимальне значення цільової функції задачі (22) – (24), Gnqrf ),(0 – значення цільової функції цієї задачі для розв’язку G. Теорема 2. Нехай LIW ,, залишаються незмінними, br)0( для деякої константи ,0b справедливі співвідношення .0/,0,0 2/3  rqqr Тоді .1 )( ),(0   rf qrf Доведення теореми міститься в [9]. Теорема про асимптотичну оптимальність не гарантує якісної роботи метода 1) – 3) у випадку, коли величини qr, не є близькими до нуля. В [9] описані числові експерименти, за допомогою яких метод 1) – 3) порівнюється з евристичним методом роботи [4]. Ідея останнього методу полягає в наступному. Виберемо точку ,WY  в якій нерівність (23) має найбільшу похибку, та розмістимо сенсор у точці Y. Повторюємо цей крок до тих пір, поки обмеження не будуть задоволені. Числові експерименти показали, що в середньому метод 1) – 3) будує приблизно на 25% кращий за цільовою функцією розв’язок, ніж метод з роботи [4]. Висновки В роботі описано математичні моделі підводних акустичних сенсорів та алгоритми колективного розпізнавання загрози, екстремальні задачі розміщування сенсорів. Запропоновано математичні методи розв’язання таких задач. Наведено теореми про асимптотичну оптимальність побудованих планів розміщення сенсорів. Показано, що досить розглянути випадок, коли всі сенсори мають однакові характеристики. З числових експериментів випливає, що побудований метод перевершує відомий метод розв’язання задач розміщування сенсорів. Література 1. Molyboha, A. and Zabarankin, M., 2012. Stochastic optimization of sensor placement for diver detection. Operations Research, 60(2), P. 292–312. 2. Iyer, S. and Rao, D.V., 2015, February. Genetic algorithm based optimization technique for underwater sensor network positioning and deployment. In Underwater Technology (UT), 2015 IEEE (P. 1–6). IEEE. 3. Hua, Cheng Bing, Zhao Wei, and Chang Zi Nan. "Underwater Acoustic Sensor Networks Deployment Using Improved Self-Organize Map Algorithm." Cybernetics and Information Technologies 14.5 (2014): 63–77. 4. Dhillon, Santpal Singh, and Krishnendu Chakrabarty. "Sensor placement for effective coverage and surveillance in distributed sensor networks." In Wireless Communications and Networking, 2003. WCNC 2003. 2003 IEEE, Vol. 3, P. 1609–1614. IEEE, 2003. 5. Mhatre, V.P., Rosenberg, C., Kofman, D., Mazumdar, R. and Shroff, N., 2005. A minimum cost heterogeneous sensor network with a lifetime constraint. IEEE Transactions on Mobile Computing, 4(1), P. 4–15. 6. Zou, Y. and Chakrabarty, K., 2003, March. Sensor deployment and target localization based on virtual forces. In INFOCOM 2003. Twenty- Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies (Vol. 2, P. 1293–1303). IEEE. 7. Zou, Yi, and Krishnendu Chakrabarty. "Sensor deployment and target localization in distributed sensor networks." ACM Transactions on Embedded Computing Systems (TECS) 3.1 (2004): 61–91. Моделі та засоби систем баз даних і знань 148 8. Felemban, M., 2011. Optimal Node Placement in Underwater Acoustic Sensor Network (Doctoral dissertation). 9. Pashko, S., Molyboha, A., Zabarankin, M. and Gorovyy, S., 2008. Optimal sensor placement for underwater threat detection. Naval Research Logistics (NRL), 55(7), P. 684–699. 10. Burdic, William S. Underwater acoustic system analysis. Prentice Hall, 1991. 452 p. 11. Ширяев А.Н. Вероятность. – Москва.: Наука, 1980. 574 с. 12. А. Вальд. Последовательный анализ. Москва., Мир, 1960. 328 с. 13. Пашко С.В. Оптимальне розміщення багатосенсорної системи для виявлення загрози // Кібернетика і системний аналіз. 2018. № 2. С. 85–94. References 1. Molyboha, A. and Zabarankin, M., 2012. Stochastic optimization of sensor placement for diver detection. Operations research, 60(2), P. 292–312. 2. Iyer, S. and Rao, D.V., 2015, February. Genetic algorithm based optimization technique for underwater sensor network positioning and deployment. In Underwater Technology (UT), 2015 IEEE (P. 1–6). IEEE. 3. Hua, C.B., Wei, Z. and Nan, C.Z., 2014. Underwater Acoustic Sensor Networks Deployment Using Improved Self-Organize Map Algorithm. Cybernetics and Information Technologies, 14(5), P. 63–77. 4. Dhillon, S.S. and Chakrabarty, K., 2003, March. Sensor placement for effective coverage and surveillance in distributed sensor networks. In Wireless Communications and Networking, 2003. WCNC 2003. 2003 IEEE (Vol. 3, P. 1609–1614). IEEE. 5. Mhatre, V.P., Rosenberg, C., Kofman, D., Mazumdar, R. and Shroff, N., 2005. A minimum cost heterogeneous sensor network with a lifetime constraint. IEEE Transactions on Mobile Computing, 4(1), P. 4–15. 6. Zou, Y. and Chakrabarty, K., 2003, March. Sensor deployment and target localization based on virtual forces. In INFOCOM 2003. Twenty- Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies (Vol. 2, P. 1293–1303). IEEE. 7. Zou, Y. and Chakrabarty, K., 2004. Sensor deployment and target localization in distributed sensor networks. ACM Transactions on Embedded Computing Systems (TECS), 3(1), P. 61–91. 8. Felemban, M., 2011. Optimal Node Placement in Underwater Acoustic Sensor Network (Doctoral dissertation). 9. Pashko, S., Molyboha, A., Zabarankin, M. and Gorovyy, S., 2008. Optimal sensor placement for underwater threat detection. Naval Research Logistics (NRL), 55(7), P. 684–699. 10. Burdic, W.S., 1991. Underwater acoustic system analysis. Prentice Hall. 11. Shiryaev, A.N., 1980. Probability [in Russian]. 12. Wald, A., 1973. Sequential analysis. Courier Corporation. 13. Pashko, S., 2018. Optimal placement of multisensory system for threat detection. Cybernetics and Systems Analysis, 54(2), P. 85–94. Про автора: Пашко Сергій Володимирович, кандидат фізико-математичних наук, старший науковий співробітник. Кількість наукових публікацій в українських виданнях – понад 30. Кількість наукових публікацій в зарубіжних виданнях – 2. Індекс Хірша (SCOPUS) – 3. http://orcid.org/0000-0002-0453-4128. Місце роботи автора: Інститут програмних систем НАН України, 03187, Київ-187, проспект Академіка Глушкова, 40. E-mail: pashko55@yahoo.com mailto:pashko55@yahoo.com

Optimal placement of a multi-sensor system

Репозитарії

Схожі ресурси