=Paper=
{{Paper
|id=Vol-2139/140-148
|storemode=property
|title=Оптимальне розміщення багатосенсорної системи
Optimal placement of a multi-sensor system
|pdfUrl=https://ceur-ws.org/Vol-2139/140-148.pdf
|volume=Vol-2139
|authors=Serhei Pashko
|dblpUrl=https://dblp.org/rec/conf/ukrprog/Pashko18
}}
==Оптимальне розміщення багатосенсорної системи
Optimal placement of a multi-sensor system==
https://ceur-ws.org/Vol-2139/140-148.pdf
УДК 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 є мілководною; в такому разі її можна вважати двовимірною.
Вважаємо, що може бути тільки одна можлива загроза, тобто один порушник. Позначимо H 0 гіпотезу, яка
140
стверджує, що в області W не існує порушника. Нехай H1 – гіпотеза, яка стверджує, що в області W існує один
порушник. Позначимо H1 (Y ) гіпотезу про те, що порушник знаходиться в точці Y W .
Припустимо, в області W розміщені n сенсорів у точках X 1 ,..., X n . Нехай S j – дійсна випадкова
величина, що є результатом обробки сигналу сенсором j, S ( S1 ,..., S n ) – випадковий вектор. Позначимо
s ( s1 ,..., s n ) спостереження вектора S в деякий момент часу. Вважаємо, що існує агент, який посилає запити
на всі сенсори, отримує від них інформацію у вигляді вектора s ( s1 ,..., s n ), на основі якої приймає рішення
про справедливість гіпотези H 0 або гіпотези H 1 (Y ).
Позначимо PS j () розподіл ймовірностей величини S j у випадку, якщо S j є дискретною випадковою
величиною. Якщо S j неперервна, то PS j () являє собою щільність розподілу ймовірностей для S j (в такому
випадку вважаємо, що щільність розподілу існує). Аналогічно позначимо PS () розподіл ймовірностей
випадкового вектора S.
Для кожного значення s та Y розглянемо умовні ймовірності (щільності) для кожної з гіпотез PS ( s | H 0 ),
PS ( s | H 1 (Y )). Вважаючи, що випадкові величини S j є незалежними за умов H 0 або H 1 (Y ), отримуємо
n n
PS ( s | H 0 ) PS (s j | H 0 ), PS (s | H1 (Y )) PS (s j | H1 (Y )).
j j
j 1 j 1
Математична модель сенсора j повністю визначається розподілами
PS j ( s j | H 0 ), PS j ( s j | H 1 (Y )), (1)
які залежать від статистичних властивостей шуму оточуючого середовища, інтенсивності сигналу, технічних
характеристик сенсора, метода обробки сигналу.
Нехай X j ( x j , y j ), Y ( x, y ), d j X j Y ( x j x) 2 ( y j y ) 2 – відстань між ціллю та j-м
сенсором. Розглянемо дві математичні моделі сенсора, що конкретизують модель (1). Символом P далі
позначається ймовірність.
МОДЕЛЬ 1. Вихідний сигнал сенсора j являє собою бінарну випадкову величину, S j {0,1}. Величина
S j приймає значення 1, якщо сенсор детектує загрозу, та 0 в іншому випадку. Ймовірності детектування
порушника для гіпотез H 0 , H 1 (Y ) визначаються формулами
P ( S j 1 | H 1 (Y )) f1 (d j ), P( S j 1 | H 0 ) , (2)
де f1 (d j ) – монотонно незростаюча функція, 0 f1 (d j ) 1.
МОДЕЛЬ 2. Вихідний сигнал сенсора j являє собою нормально розподілену випадкову величину,
f (d ) за умови H 1 (Y ),
Sj 2 j (3)
за умови H 0 ,
де
a j b j d j , d j a j /b j ,
f 2 (d j ) (4)
0, d j a j / b j ,
a j 0, b j 0 – константи, що залежать від технічних характеристик сенсора, f 2 (d j ) – сигнал від цілі, –
шум, ~ N ( , 2 ).
В роботі [10] описані закони розповсюдження сигналів у водному середовищі з врахуванням шумів, на
основі яких побудовано наведені моделі.
Опишемо одноперіодний алгоритм детектування загрози, що використовує сигнали сенсорів, отримані в
деякий момент часу t. Почнемо з простого випадку, коли або порушника немає в області W, або він знаходиться
в точці Y W . Для виявлення загрози застосуємо тест Неймана – Пірсона, що використовує відношення
правдоподібності
141
PS ( s | H 1 (Y ))
R ( s, Y ) .
PS ( s | H 0 )
Приймається гіпотеза H 1 (Y ), якщо R ( s, Y ) (Y ) для деякого значення (Y ), і гіпотеза H 0 в іншому випадку.
Поріг детектування (Y ) визначається величинами ймовірностей помилок першого та другого родів, 0 та 1
відповідно. Обмеження на ймовірності помилок першого та другого роду приймають форму
P ( R ( S , Y ) (Y ) | H 0 ) 0 , P( R ( S , Y ) (Y ) | H 1 (Y )) 1 . (5)
Припустимо, розподіл величини R ( S , Y ) як за умови H 0 , так і за умови H 1 (Y ) є неперервним. Позначимо
q 0 квантиль рівня 1 0 розподілу величини R ( S , Y ) за умови H 0 ; нехай q1 означає квантиль рівня 1
розподілу величини R ( S , Y ) за умови H 1 (Y ). Співвідношення (5) можуть бути записані у вигляді
q 0 (Y ) q1 . Якщо q 0 q1 , виберемо (Y ) (q 0 q1 ) / 2. Нерівність q 0 q1 означає, що система не має
удосталь сенсорів для виконання умов (5).
Розглянемо випадок, коли або порушника немає в області W, або про нього відомо тільки те, що він
знаходиться в області W. В такому випадку застосовуємо тест Неймана – Пірсона до кожної точки W (звичайно,
під час числових розрахунків мова може йти тільки про скінчену множину точок, яка досить щільно покриває
W). Обмеження (5), які стосуються помилок першого та другого родів, повинні виконуватись для всіх Y W .
Зауважимо, що в такому разі виникає наступна проблема. Ймовірність детектування загрози за умови її
відсутності (тобто ймовірність помилки першого роду) може перевищити число 0 , що фігурує в (5). Ця
ймовірність,
0 P(Y W : R( s, Y ) (Y ) | H 0 ),
може бути знайдена методом Монте-Карло. Величина 0 залежить від вибору числа 0 .
Припустимо, за умов справедливості гіпотез H 0 або H 1 (Y ) випадкові величини S j , j 1,2,..., n,
незалежні. Маємо
n
ln R ( S , Y ) ln R (S , Y ),
j 1
j j
PS j ( S j | H 1 (Y ))
де R j ( S j , Y ) . Для моделей сенсорів 1 і 2 величини PS j ( S j | H 1 (Y )) та PS j ( S j | H 0 )
PS j ( S j | H 0 )
визначаються формулами (2) – (4).
Для використання тесту Неймана – Пірсона необхідно знати розподіл випадкової величини
n
ln R ( S , Y ) ln R (S , Y ) за умови справедливості гіпотез H та H (Y ). З центральної граничної теореми
j 1
j j 0 1
теорії ймовірностей [11] випливає, що за умови Ліндеберга для досить великих значень n розподіл величини
ln R( S , Y ) є близьким до нормального. У випадку використання сенсорної моделі 2 величина ln R( S , Y ) має
нормальний розподіл, оскільки нормально розподіленими є величини S j .
Модель 2 акустичного сенсора описана в роботі [9]. Там же описано багатоперіодний алгоритм
детектування загрози. Такий алгоритм використовує дані, що надходять від сенсорів у послідовні моменти
часу; водночас застосовується метод послідовного статистичного аналізу [12].
2. Задачі оптимального розміщування сенсорів
Припустимо, існує K типів сенсорів. Нехай nk – кількість сенсорів k-го типу, які планується розмістити в
області W, c k – ціна сенсора k-го типу, X kj – вектор координат j-го сенсора k-го типу, X kj W , k 1,2,..., K ,
j 1,2,..., nk . Розглянемо наступну задачу оптимального розміщення сенсорів:
K
min
n k 0, X kj W
c k nk , (6)
k 1
142
k Y X kj I , Y W .
K nk
(7)
k 1 j 1
Тут функція k () характеризує надійність детектування загрози одним сенсором k-го типу, величина I означає
задану надійність детектування системою сенсорів. Надійність може вимірюватись за допомогою різних
величин, таких як кількість інформації, що надходить до сенсорів з точки Y тощо. Далі розглянемо
формулювання задачі (6), (7) у випадку використання описаних вище моделей і алгоритмів виявлення загрози.
Нехай використовується одноперіодний алгоритм детектування. Розглянемо задачу мінімізації вартості
сенсорної системи за обмежень (5) на ймовірності помилок першого та другого роду
K
min
n 0, X W
c k nk , (8)
k kj k 1
P ( R ( S , Y ) (Y ) | H 0 ) 0 , Y W , (9)
P( R ( S , Y ) (Y ) | H1 (Y )) 1 , Y W . (10)
Припустимо, в якості математичної моделі сенсора використовується модель 2. Нехай загальне число сенсорів
дорівнює n і всі вони ідентичні. Нехай також означає -квантиль нормального розподілу ймовірностей. В
роботі [9] показано, що задачу (8) – (10) можна записати у вигляді
min n, (11)
X j W
n
f 22 (d j ) ( 1 1 ) 2 2 , Y W .
0 1
(12)
j 1
Задача (11), (12) – окремий випадок задачі (6), (7), де k (d ) f 22 (d ) та I ( 1 0 1 1 ) 2 2 . Цю задачу
можна узагальнити на випадок існування кількох типів сенсорів.
Якщо використовується багатоперіодний алгоритм детектування, то задача мінімізації вартості сенсорної
системи за обмежень на середній час виявлення загрози та на ймовірність помилки першого роду записується у
вигляді
K
min
n 0, X W
c k nk , (13)
k kj k 1
E (T ) Tmax , (14)
де T – кількість часу, що проходить від моменту, коли порушник з’явився в області W, до моменту його
виявлення. В роботі [9] задача (13), (14) за деяких умов зведена до задачі (6), (7).
Отже, розглянуті задачі є окремими випадками задачі (6), (7), яку можна звести до задачі булевого
програмування наступним чином. Нехай Z {Z 1 , Z 2 ,..., Z M } – множина точок з області W таких, що для кожної
точки Y W справедлива нерівність min Y Z m , де 0. Нехай z mkj 1, якщо в точці Z m Z
m 1,..., M
встановлюється сенсор типу k з номером j {1,2,..., N k }; z mkj 0 в іншому випадку. Тут N k – максимально
можливе число сенсорів типу k. Замість задачі (6), (7) розглянемо задачу
M K Nk
min ck z mkj , (15)
z mkj
m 1k 1 j 1
M K Nk
k Y Z m zmkj I , Y Z , (16)
m1k 1 j 1
143
M
z mkj 1, k 1,2,..., K , j 1,2,..., N k , (17)
m 1
z mkj {0,1}, m 1,2,..., M , k 1,2,..., K , j 1,2,..., N k . (18)
Нерівності (17) гарантують, що кожен сенсор може знаходитись тільки в одній точці або може не бути
задіяним. В одній точці дозволяється розміщувати один або кілька сенсорів. Задача (15) – (18) може бути
розв’язана одним з числових методів булевого програмування.
Далі розглянемо задачі, для розв’язання яких можна застосувати більш прості методи у порівнянні з
методами загального призначення. Для таких задач вдається не тільки побудувати близькі до оптимальних
розв’язки у вигляді числових векторів, але й дослідити їх властивості. Зокрема, розглянемо задачу
n
min cu j , (19)
n, u j , X j
j 1
Y X j u j I , Y W ,
n
(20)
j 1
n 1, u j 0, X j W , j 1,2,..., n. (21)
Тут u j – дійсне число, що характеризує ”потужність” j-го сенсора, n – кількість сенсорів, c – ціна одиниці
”потужності”, X j – вектор координат j-го сенсора. Якщо u j 1, отримуємо задачу
min n, (22)
Xj
Y X j I , Y W ,
n
(23)
j 1
n 1, X j W , j 1,2,..., n. (24)
В цій задачі вимагається мінімізувати кількість однотипних сенсорів, що розміщені в області W та забезпечують
виконання нерівностей (23).
3. Регулярний спосіб розміщення сенсорів
Розглянемо спосіб розміщення сенсорів у області W, який полягає в тому, що сенсори знаходяться в
вершинах регулярної сітки, утвореної правильними трикутниками, квадратами або правильними
шестикутниками (рисунок).
Рисунок. Регулярні сітки для розміщування сенсорів
Припустимо, для задачі (19) – (21) виконуються наступні умови. Функція (d ), d 0, є незростаючою
144
неперервною Ліпшицевою з константою L 0 та приймає невід’ємні значення. Існує число r 0 таке, що
(d ) 0 для 0 d r , (d ) 0 для d r , (0) br для деякої константи b 0. Число r означає радіус дії
сенсора. Припустимо, область W являє собою многокутник, всі кути якого не менші за / 2. Виконання
останньої умови можна забезпечити, “зрізаючи” гострі кути, якщо вони є, та збільшуючи число сторін
многокутника. Вважаємо, що I 0.
Наступний метод будує допустимий розв’язок G ( X 1 , X 2 ,..., X n ) задачі (19) – (21), близький до
оптимального. Розглянемо регулярну сітку S, сформовану правильними трикутниками, квадратами або
правильними шестикутниками з довжиною сторони s (рисунок). Вважаємо, що s r. Позначимо
u min u : u ( Y X ) I , Y C ,
X YS
де YS – множина всіх вершин регулярної сітки S, C – регулярна фігура сітки (трикутник, квадрат або
шестикутник). Позначимо W1 (r ) множину точок X W , для яких відстань до межі множини W не менша за r.
Нехай G YS W X 10 , X 20 ,..., X n00 , G1 (r ) G W1 (r ), G0 (r ) G \ G1 (r ). Виберемо число h 4 та
розглянемо розв’язок задачі (19) – (21), що визначається співвідношеннями
n n 0 , X j X 0j , (25)
u , X j G1 (r ),
u j u 0j j 1,2,..., n 0 . (26)
hu , X j G0 (r ),
Оскільки кути многокутника W не менші / 2 і h 4, то розв’язок (25), (26) – допустимий для задачі
(19) – (21) за умови, що величини r та s / r досить малі.
Позначимо f 0 (r , s) значення цільової функції задачі (19) – (21) для розв’язку (25), (26),
0
n
f 0 (r , s ) c u . Нехай f (r ) – оптимальне значення цільової функції задачі (19) – (21). Наступна теорема
j 1
0
j
стверджує, що розв’язок (25), (26) – асимптотично оптимальний.
Теорема 1. Нехай W , I , L залишаються незмінними, (0) br для деякої константи b 0, справедливі
співвідношення r 0, s 0, s / r 0. Тоді
f 0 (r , s )
1.
f (r )
Доведення цієї теореми міститься в роботі [13]. З теореми 1 випливає, що розміщення сенсорів однакової
“потужності” у вершинах регулярної сітки приводить до близьких до оптимальних розв’язків задачі (19) – (21).
Тому далі вважаємо, що u j 1, та розглянемо задачу (22) – (24).
4. Числовий метод побудови близького до оптимального розміщення сенсорів
В даному розділі розглянемо задачу (22) – (24) та відповідний числовий метод розміщування сенсорів у
області W. Результатом роботи методу є план розміщення однотипних сенсорів, що задовольняє умовам (23),
(24), та є асимптотично оптимальним розв’язком. Вважаємо, що область W, величина I та функція (d ), d 0,
задовольняють умовам, описаним у попередньому розділі. Ідея методу полягає в тому, що сенсори
розміщуються в вершинах регулярної сітки, а на межі області W розміщуються додаткові сенсори. Розглянемо
тільки регулярну сітку, утворену квадратами (рисунок). Числові методи для регулярних сіток, утворених
правильними трикутниками або шестикутниками, будуються подібним способом.
Позначимо Q регулярну сітку, утворену квадратами з довжиною сторони q, де r 3q / 2 . Нехай
YQ – множина всіх вершин сітки Q,
CQ – множина всіх квадратів C сітки Q, для яких виконується співвідношення W int C , де int C
145
– внутрішня частина множини C,
~
YQ – множина всіх вершин сітки Q, що належать квадратам з множини CQ .
Позначимо W0 W0 (r ) множину точок X W , для яких відстань до межі множини W не більша за r.
Нехай
CQ0 – множина всіх квадратів C сітки Q, для яких виконується співвідношення W0 int C ,
~
YQ0 – множина всіх вершин сітки Q, що належать квадратам з множини CQ0 .
Подібним чином розглянемо сформовану квадратами із стороною s регулярну сітку S, для якої величина
s визначається алгоритмом. Позначимо YS множину вершин сітки S. Вважаємо, що лінії сітки S паралельні або
перепендикулярні лініям сітки Q і що множина вершин сітки S належить множині вершин сітки Q, тобто s / q є
цілим числом.
Наступний метод [9] будує допустимий розв’язок G ( X 1 , X 2 ,..., X n ) задачі (22) – (24), близький до
оптимального.
1) вирішимо задачу
max s, (27)
Y X q / 2 I , Y C YQ , (28)
X YS
s / q {1,2,..., n,...}, (29)
де змінна s є довжиною сторони квадрату сітки S і C є квадратом сітки S. Фіксуємо оптимальне значення
змінної s і далі вважаємо, що сітка S утворена квадратами з довжиною сторін s. Виберемо
G YS W . (30)
2) якщо виконуються нерівності
Y X q / 2 I , Y Y ,
~0
Q (31)
X G
роботу зупиняємо.
~
3) виберемо точку Y YQ0 , що максимізує вираз
I Y X q / 2 .
X G
Включимо в розв’язок G проекцію W (Y ) точки Y на множину W. Переходимо до 2).
~
Зауважимо, що метод 1) – 3) скінчений. Дійсно, оскільки r 3q / 2 і для кожної точки Y з множини YQ0
справедлива нерівність Y W (Y ) 2 q, значення I Y X q / 2 на кроці 3) для вибраної точки
X G
~
Y YQ0 зменшується як мінімум на величину 2q q / 2 3q / 2 0. Оскільки множина Y~ скінчена,
Q
0
то нерівність (31) буде справедливою після скінченого числа ітерацій.
Легко довести, що побудований методом 1) – 3) розв’язок G ( X 1 , X 2 ,..., X n ) є допустимим розв’язком
задачі (22) – (24), тобто
Y X j I , Y W .
n
(32)
j 1
146
~
Дійсно, для кожної точки Y W найближча до цієї точки вершина Y YQ належить множині YQ . Якщо
~
Y YQ0 , то з (27) – (30) випливає
Y X q / 2 I.
n
j (33)
j 1
~
Якщо Y YQ0 , то (33) випливає з (31). Оскільки функція (d ) незростаюча та Y Y q / 2 , маємо
Y X Y X q / 2 I ,
n n
j j
j 1 j 1
звідки випливає (32).
Зауважимо, що в задачі (22) – (24) не приймаються до уваги перешкоди, що можуть бути між сенсорами
та ціллю в області W. Тому побудований розв’язок G можна вважати досить якісним тільки для випадків, коли
область W є близькою до опуклої.
Справедлива теорема про асимптотичну оптимальність побудованого методом 1) – 3) розв’язку G. Нехай
f (r ) – оптимальне значення цільової функції задачі (22) – (24), f 0 (r , q) n G – значення цільової функції
цієї задачі для розв’язку G.
Теорема 2. Нехай W , I , L залишаються незмінними, (0) br для деякої константи b 0, справедливі
співвідношення r 0, q 0, q / r 3 / 2 0. Тоді
f 0 (r , q)
1.
f (r )
Доведення теореми міститься в [9]. Теорема про асимптотичну оптимальність не гарантує якісної роботи
метода 1) – 3) у випадку, коли величини r, q не є близькими до нуля. В [9] описані числові експерименти, за
допомогою яких метод 1) – 3) порівнюється з евристичним методом роботи [4]. Ідея останнього методу полягає
в наступному. Виберемо точку Y W , в якій нерівність (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.
147
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.
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
148