Описано алгоритми детектування підводної загрози за допомогою системи акустичних сенсорів, екстремальні задачі розміщування сенсорів. Розглянуто методи розв'язання таких задач та теореми про асимптотичну оптимальність побудованих планів розміщення сенсорів. З результатів числових експериментів випливає, що побудований метод перевершує відомий метод розв'язання задач розміщування сенсорів. Ключові слова: сенсор, багатосенсорна система, алгоритм детектування загрози, оптимальне розміщення сенсорів, асимптотична оптимальність. Описан алгоритм детектирования подводной угрозы с помощью системы акустических сенсоров, а также экстремальные задачи размещения сенсоров. Рассмотрены методы решения таких задач, доказана теорема об асимптотической оптимальности построенных планов размещения сенсоров. Из результатов численных экспериментов следует, что построенный метод превосходит известный метод решения задач размещения сенсоров. Ключевые слова: сенсор, многосенсорная система, алгоритм детектирования угрозы, оптимальное размещение сенсоров, асимптотическая оптимальность. 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.
1. Математичні моделі сенсорів і алгоритми детектування загрози порушник. Позначимо H1(Y ) гіпотезу про те, що порушник знаходиться в точці Y W .
Припустимо, в області W розміщені n сенсорів у точках X1,..., X n . Нехай S j – дійсна випадкова величина, що є результатом обробки сигналу сенсором j, S (S1,..., Sn ) – випадковий вектор. Позначимо s (s1,..., sn ) спостереження вектора S в деякий момент часу. Вважаємо, що існує агент, який посилає запити на всі сенсори, отримує від них інформацію у вигляді вектора s (s1,..., sn ), на основі якої приймає рішення про справедливість гіпотези H 0 або гіпотези H1(Y ).
Позначимо PS j () розподіл ймовірностей величини S j у випадку, якщо S j є дискретною випадковою величиною. Якщо S j неперервна, то PS j () являє собою щільність розподілу ймовірностей для S j (в такому випадку вважаємо, що щільність розподілу існує). Аналогічно позначимо PS () розподіл ймовірностей випадкового вектора S.
Для кожного значення s та Y розглянемо умовні ймовірності (щільності) для кожної з гіпотез PS (s | H 0 ), PS (s | H1(Y )). Вважаючи, що випадкові величини S j є незалежними за умов H 0 або H1(Y ), отримуємо n n PS (s | H 0 ) PS j (s j | H 0 ), PS (s | H1(Y )) PS j (s j | H1(Y )).
j1 j1 Математична модель сенсора j повністю визначається розподілами
PS j (s j | H 0 ), PS j (s j | H1(Y )), які залежать від статистичних властивостей шуму оточуючого середовища, інтенсивності сигналу, технічних характеристик сенсора, метода обробки сигналу.
Нехай X j (x j , y j ), Y (x, y), d j X j Y (x j x)2 ( y j y)2
– відстань між ціллю та j-м
сенсором. Розглянемо дві математичні моделі сенсора, що конкретизують модель (
МОДЕЛЬ 1. Вихідний сигнал сенсора j являє собою бінарну випадкову величину, S j {0,1}. Величина S j приймає значення 1, якщо сенсор детектує загрозу, та 0 в іншому випадку. Ймовірності детектування порушника для гіпотез H 0 , H1(Y ) визначаються формулами де f1(d j ) – монотонно незростаюча функція, 0 f1(d j ) 1.
P(S j 1| H1(Y )) f1(d j ),
P(S j 1| H 0 ) , МОДЕЛЬ 2. Вихідний сигнал сенсора j являє собою нормально розподілену випадкову величину, де
S j f 2 (d j ) за умови H1(Y ), за умови H 0 ,
a j b j d j , d j a j /b j , f2 (d j )
0, d j a j /b j , a j 0, b j 0 – константи, що залежать від технічних характеристик сенсора, f2 (d j ) – сигнал від цілі, – шум, ~ N ( , 2 ).
В роботі [10] описані закони розповсюдження сигналів у водному середовищі з врахуванням шумів, на основі яких побудовано наведені моделі.
Опишемо одноперіодний алгоритм детектування загрози, що використовує сигнали сенсорів, отримані в
деякий момент часу t. Почнемо з простого випадку, коли або порушника немає в області W, або він знаходиться
в точці Y W . Для виявлення загрози застосуємо тест Неймана – Пірсона, що використовує відношення
правдоподібності
(
Розглянемо випадок, коли або порушника немає в області W, або про нього відомо тільки те, що він
знаходиться в області W. В такому випадку застосовуємо тест Неймана – Пірсона до кожної точки W (звичайно,
під час числових розрахунків мова може йти тільки про скінчену множину точок, яка досить щільно покриває
W). Обмеження (
0 P(Y W : R(s,Y ) (Y ) | H 0 ), може бути знайдена методом Монте-Карло. Величина 0 залежить від вибору числа 0.
Припустимо, за умов справедливості гіпотез H 0 або H1(Y ) випадкові величини S j , j 1,2,..., n, незалежні. Маємо
n ln R(S,Y ) ln R j (S j ,Y ),
j1
PS j (S j | H1(Y )) де R j (S j ,Y )
PS j (S j | H 0 )
визначаються формулами (
Для використання тесту Неймана – Пірсона необхідно знати розподіл випадкової величини n ln R(S,Y ) ln R j (S j ,Y ) за умови справедливості гіпотез H 0 та H1(Y ). З центральної граничної теореми j1 теорії ймовірностей [11] випливає, що за умови Ліндеберга для досить великих значень n розподіл величини ln R(S,Y ) є близьким до нормального. У випадку використання сенсорної моделі 2 величина ln R(S,Y ) має . Для моделей сенсорів 1 і 2 величини PS j (S j | H1(Y )) та PS j (S j | H 0 ) нормальний розподіл, оскільки нормально розподіленими є величини S j .
Модель 2 акустичного сенсора описана в роботі [9]. Там же описано багатоперіодний алгоритм детектування загрози. Такий алгоритм використовує дані, що надходять від сенсорів у послідовні моменти часу; водночас застосовується метод послідовного статистичного аналізу [12]. 2. Задачі оптимального розміщування сенсорів
Припустимо, існує K типів сенсорів. Нехай nk – кількість сенсорів k-го типу, які планується розмістити в області W, ck – ціна сенсора k-го типу, X kj – вектор координат j-го сенсора k-го типу, X kj W , k 1,2,..., K , j 1,2,..., nk . Розглянемо наступну задачу оптимального розміщення сенсорів:
K
min ck nk ,
nk 0, X kj W k 1
(
Нехай використовується одноперіодний алгоритм детектування. Розглянемо задачу мінімізації вартості
сенсорної системи за обмежень (
Якщо використовується багатоперіодний алгоритм детектування, то задача мінімізації вартості сенсорної
системи за обмежень на середній час виявлення загрози та на ймовірність помилки першого роду записується у
вигляді
де T – кількість часу, що проходить від моменту, коли порушник з’явився в області W, до моменту його
виявлення. В роботі [9] задача (
Отже, розглянуті задачі є окремими випадками задачі (
min Y Z m , де 0. Нехай zmkj 1, якщо в точці Z m Z
m1,...,M
встановлюється сенсор типу k з номером j {1,2,..., N k }; zmkj 0 в іншому випадку. Тут N k – максимально
можливе число сенсорів типу k. Замість задачі (
K min ck nk , nk 0, XkjW k1
P(R(S,Y ) (Y ) | H 0 ) 0 , Y W , P(R(S,Y ) (Y ) | H1(Y )) 1, Y W .
min n,
X jW n f22 (d j ) ( 1 0 11 )2 2 , Y W . j 1
K min ck nk , nk 0, XkjW k1
E(T ) Tmax ,
M K Nk min ck zmkj , zmkj m1k 1 j 1 M K Nk k Y Zm zmkj I , Y Z , m1k1 j1
M zmkj 1, k 1,2,..., K , j 1,2,..., Nk , m1 zmkj {0,1}, m 1,2,..., M , k 1,2,..., K , j 1,2,..., Nk . Нерівності (17) гарантують, що кожен сенсор може знаходитись тільки в одній точці або може не бути задіяним. В одній точці дозволяється розміщувати один або кілька сенсорів. Задача (15) – (18) може бути розв’язана одним з числових методів булевого програмування.
Далі розглянемо задачі, для розв’язання яких можна застосувати більш прості методи у порівнянні з методами загального призначення. Для таких задач вдається не тільки побудувати близькі до оптимальних розв’язки у вигляді числових векторів, але й дослідити їх властивості. Зокрема, розглянемо задачу Тут u j – дійсне число, що характеризує ”потужність” j-го сенсора, n – кількість сенсорів, c – ціна одиниці ”потужності”, X j – вектор координат j-го сенсора. Якщо u j 1, отримуємо задачу
n min cu j , n, u j , X j j 1 n Y X j u j I , Y W , n 1, u j 0, X j W , j 1,2,..., n.
min n,
X j n Y X j I , Y W , В цій задачі вимагається мінімізувати кількість однотипних сенсорів, що розміщені в області W та забезпечують виконання нерівностей (23). 3. Регулярний спосіб розміщення сенсорів
Розглянемо спосіб розміщення сенсорів у області W, який полягає в тому, що сенсори знаходяться в вершинах регулярної сітки, утвореної правильними трикутниками, квадратами або правильними шестикутниками (рисунок).
Рисунок. Регулярні сітки для розміщування сенсорів Припустимо, для задачі (19) – (21) виконуються наступні умови. Функція (d ), d 0, є незростаючою неперервною Ліпшицевою з константою L 0 та приймає невід’ємні значення. Існує число r 0 таке, що (d ) 0 для 0 d r, (d ) 0 для d r, (0) br для деякої константи b 0. Число r означає радіус дії сенсора. Припустимо, область W являє собою многокутник, всі кути якого не менші за / 2. Виконання останньої умови можна забезпечити, “зрізаючи” гострі кути, якщо вони є, та збільшуючи число сторін многокутника. Вважаємо, що I 0.
Наступний метод будує допустимий розв’язок G ( X1, X 2 ,..., X n ) задачі (19) – (21), близький до оптимального. Розглянемо регулярну сітку S, сформовану правильними трикутниками, квадратами або правильними шестикутниками з довжиною сторони s (рисунок). Вважаємо, що s r. Позначимо u minu : u ( Y X ) I , Y C,
X YS Нехай G YS W X10 , X 20 ,..., X n00 , розглянемо розв’язок задачі (19) – (21), що визначається співвідношеннями де YS – множина всіх вершин регулярної сітки S, C – регулярна фігура сітки (трикутник, квадрат або шестикутник). Позначимо W1(r) множину точок X W , для яких відстань до межі множини W не менша за r.
G1(r) G W1(r),
G0 (r) G \ G1(r). Виберемо число h 4 та n n0 , X j X 0j , u , X j G1(r), u j u 0j hu , X j G0 (r),
j 1,2,..., n0.
j1 стверджує, що розв’язок (25), (26) – асимптотично оптимальний. Оскільки кути многокутника W не менші / 2 і h 4, то розв’язок (25), (26) – допустимий для задачі (19) – (21) за умови, що величини r та s / r досить малі.
Позначимо f 0 (r, s) значення цільової функції задачі (19) – (21) для розв’язку (25), (26), n0 f 0 (r, s) c u 0j . Нехай f (r) – оптимальне значення цільової функції задачі (19) – (21). Наступна теорема Теорема 1. Нехай W , I , L залишаються незмінними, (0) br для деякої константи b 0, справедливі співвідношення r 0, s 0, s / r 0. Тоді (25) (26)
1.
Доведення цієї теореми міститься в роботі [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 Нехай – внутрішня частина множини C, ~
YQ – множина всіх вершин сітки Q, що належать квадратам з множини CQ . Позначимо W0 W0 (r) множину точок X W , для яких відстань до межі множини W не більша за r.
CQ0 – множина всіх квадратів C сітки Q, для яких виконується співвідношення W0 int C , Y~Q0 – множина всіх вершин сітки Q, що належать квадратам з множини CQ . 0 Подібним чином розглянемо сформовану квадратами із стороною s регулярну сітку S, для якої величина s визначається алгоритмом. Позначимо YS множину вершин сітки S. Вважаємо, що лінії сітки S паралельні або перепендикулярні лініям сітки Q і що множина вершин сітки S належить множині вершин сітки Q, тобто s / q є цілим числом.
Наступний метод [9] будує допустимий розв’язок G ( X1, X 2 ,..., X n ) задачі (22) – (24), близький до оптимального.
1) вирішимо задачу де змінна s є довжиною сторони квадрату сітки S і C є квадратом сітки S. Фіксуємо оптимальне значення змінної s і далі вважаємо, що сітка S утворена квадратами з довжиною сторін s. Виберемо 2) якщо виконуються нерівності
max s, Y X q / 2 I , Y C YQ , X YS s / q {1,2,..., n,...},
G YS W .
XG Y X q / 2 I , Y Y~Q0 , (27) (28) (29) (30) (31) (32) роботу зупиняємо.
3) виберемо точку Y Y~Q0 , що максимізує вираз
I Y X q / 2 .
XG Включимо в розв’язок G проекцію W (Y ) точки Y на множину W. Переходимо до 2).
Зауважимо, що метод 1) – 3) скінчений. Дійсно, оскільки r 3q / 2 і для кожної точки Y з множини Y~Q0 справедлива нерівність Y W (Y ) 2q, значення I Y X q / 2 на кроці 3) для вибраної точки X G Y Y~Q0 зменшується як мінімум на величину 2q q / 2 3q / 2 0. Оскільки множина Y~Q0 скінчена, то нерівність (31) буде справедливою після скінченого числа ітерацій.
Легко довести, що побудований методом 1) – 3) розв’язок G ( X1, X 2 ,..., X n ) є допустимим розв’язком задачі (22) – (24), тобто n Y X j I , Y W . j 1 співвідношення 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]. Висновки
В роботі описано математичні моделі підводних акустичних сенсорів та алгоритми колективного розпізнавання загрози, екстремальні задачі розміщування сенсорів. Запропоновано математичні методи розв’язання таких задач. Наведено теореми про асимптотичну оптимальність побудованих планів розміщення сенсорів. Показано, що досить розглянути випадок, коли всі сенсори мають однакові характеристики. З числових експериментів випливає, що побудований метод перевершує відомий метод розв’язання задач розміщування сенсорів. (33) Література 10. 11. 12. 13.