Воронезький Науково-дослідний Інститут Зв'язку

Отримано 17 травня 2001 р

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

Вступ

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

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

При послідовному пошуку область невизначеності розбивається на осередки, величина яких визначається вимогами до точності визначення параметра шуканого сигналу (об'єкта). Потім виконується послідовна перевірка гіпотез про наявність об'єкта пошуку в одній з комірок області невизначеності. По завершенні перевірки гіпотези виноситься рішення щодо двох альтернатив: значення параметра відповідає перевіряється гіпотези чи ні, і в другому випадку здійснюється перехід до наступної гіпотези і т.д. Перевірка простої гіпотези називається кроком пошуку. У зв'язку з тим, що рішення на кожному кроці виноситься щодо саме двох альтернатив, пошук отримав назву довічного [ 1 ].

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

Обидві описані пошукові процедури можуть бути однопрохідними або циклічними. Однопрохідні пошукові процедури передбачають проведення пошуку без повторних циклів сканування області невизначеності, в той час як циклічні допускають повернення до попередніх кроків пошуку. Однопрохідні процедури характеризуються двома параметрами: ймовірністю успішного завершення Q і середнім часом пошуку ТСР. Причому в [ 2 ] Показано, що завдання максимізації ймовірності Q при фіксованому часу ТСР і мінімізації ТСР при фіксованому Q мають спільне рішення, тобто обидва завдання призводять до однієї і тієї ж оптимальної сукупності часів аналізу на кожному кроці пошуку і порогів виявлення Vi (в разі пошуку з двухпорогового вирішальним пристроєм Вальда порогів V 0 i і V 1 i). Для вирішення завдання максимізації ймовірності успіху Q при фіксованому середньому часу застосуємо метод динамічного програмування.

Основним завданням даної роботи є дослідження підходів до оптимізації послідовного і дихотомічного пошуку методом динамічного програмування. Метою оптимізації є знаходження потенційних характеристик даних процедур і їх порівняльний аналіз. Оптимізація проведена на прикладі пошуку сигналу має постійну огибающую (ФМ або ЧС сигнал) з шириною спектра D f 0 в частотному діапазоні А D f 0, в допущенні що пошук проводиться за допомогою однопорогового обнаружителя без пам'яті, тобто вхідний сигнал не може бути записаний і для кожного нового кроку пошуку потрібно його нова реалізація.

1. Оптимізація послідовного пошуку

Пряме використання методу динамічного програмування передбачає одночасну оптимізацію часу аналізу осередки області невизначеності і порога виявлення. Уявімо процедуру послідовного пошуку в вигляді деревовидного графа, вершиною якого є вузол, що відповідає першому вимірюванню (див. Рис.1).

Мал. 1. Дерево однопрохідного послідовного пошуку.

Імовірність успішного завершення пошуку з вузла А-1 дорівнює

, (1)

де - час аналізу i -й осередку області невизначеності, Vi - поріг виявлення, - апостериорная ймовірність присутності сигналу в А-1 осередку області невизначеності. Якщо припустити, що сигнал равновероятно може перебувати в будь-який з осередків і на i -1 попередніх кроках не було пропуску сигналу, то ймовірність присутності сигналу при аналізі i -й осередку дорівнює

. (2)

Дане значення є верхньою межею ймовірності p (xi) при здійсненні пошуку. Нижньою межею є нуль - випадок пропуску сигналу на попередніх кроках.

У загальному випадку ймовірність успішного пошуку з i -го вузла дорівнює

, (3)

де Ti - час, виділений на пошук з i -го вузла. Часи Ti, Ti +1 і ti пов'язані наступним виразом

(4)

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

. (5)

Ймовірності присутності сигналу на поточному та попередньому кроках пошуку пов'язані виразом

, (6)

де - ймовірність того, що при винесенні рішення "сигналу немає" його дійсно немає, рівна

. (7)

У теорії динамічного програмування [ 3 ] Вираз ( 5 ) Називається функцією Беллмана. Таким чином, функція Беллмана, розрахована для першого вузла від аргументів T 1 = T СР і , Є максимально досяжна ймовірність успішного пошуку при заданому часу пошуку T НГ. Повторний прохід по дереву пошуку, але вже від першого вузла до останнього, дозволяє відновити значення порогів часів аналізу і Vi, що призвели до знайденої ймовірності успіху.

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

, (8)

де р i - ймовірність того, що пошук дійде до i-го кроку пошуку, одержувана рекурентним чином, починаючи з кроку номер один.

Розглянемо випадок, коли час аналізу на всіх етапах пошуку однаково, тобто . На рис.2 представлені залежності середнього часу послідовного пошуку, оптимізованого методом динамічного програмування, від відносини сигнал / шум для А = 32-128 і ймовірностей успіху Q = 0,9. Передбачається, що шуканий сигнал має постійну огибающую, а час пошуку представлено щодо інтервалу часу T 0 = 1 / D f 0. На тому ж малюнку наведено залежності середнього часу пошуку для випадку, коли при перевірці частотних каналів поріг і час аналізу були фіксованими.

Мал. 2. Порівняння послідовної пошукової

процедури з фіксованим і змінним порогом

Середній час пошуку завжди нижче при перебудовувати порозі, і також ймовірність успішного пошуку Q завжди дещо краще, проте виграш не є суттєвим.

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

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

2. Оптимізація дихотомічного пошуку

Мал. 3. Дерево дихотомічного пошуку

Однопрохідний дихотомический пошук вузькосмугового сигналу в частотному діапазоні передбачає виконання N = log 2 A кроків, де на першому кроці весь аналізований частотний діапазон розбивається на дві частини і визначається, в якій половині знаходиться шуканий сигнал. На другому кроці ділиться навпіл поддиапазон, знайдений на попередньому кроці і т.д. В результаті на останньому кроці вибір здійснюється між піддіапазонами, що містять по одній клітинці. Фінальна ймовірність успішного пошуку Q в даному випадку буде дорівнює добутку ймовірностей винесення правильного рішення на кожному кроці Qi, де i = 1, N. Якщо задано деякий час ТСР, протягом якого необхідно провести пошук, то одним з варіантів розподілу наявного загального часу між кроками є такий, при якому ймовірності винесення правильного рішення на кожному кроці будуть рівні, тобто . Назвемо цей підхід першим.

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

Припустимо, що шуканий сигнал має постійну огибающую і час аналізу на етапі пошуку T >> 1 / D f 0 і при цьому пошук здійснюється за допомогою двох фільтрів з перебудовувати смугою і центральною частотою. Обчислюється різниця вихідних сигналів фільтрів, детектування і некогерентного накопичення. Рішення на користь одного або іншого піддіапазону виноситься за допомогою вирішального пристрою (РУ), що порівнює отриману величину з нульовим порогом. У такому випадку ймовірність винесення правильного рішення за допомогою однопорогового РУ на i-му кроці пошуку дорівнює

, (9)

де - функція крамп; - відношення сигнал / шум по входу РУ на i-му кроці пошуку в відсутності накопичення, залежне від номера кроку пошуку та відносини сигнал / шум в елементарній комірці ; - число накопичуваних відліків на інтервалі часу 1 / D f 0, залежне від номера кроку дихотомічного пошуку; Т - час аналізу на етапі пошуку, представлене щодо інтервалу 1 / D f 0. Слід зазначити, що в залежності від номера кроку пошуку на інтервалі часу 1 / D f 0 може бути різне число накопичуваних відліків n, оскільки на різних етапах аналізуються частотні піддіапазони різної ширини.

Якщо на пошук з вузла, що знаходиться на останньому рівні, виділено час t і попередні кроки були безпомилковими, то ймовірність правильного завершення пошуку дорівнює

. (10)

Та ж ймовірність для передостаннього рівня дорівнює

, (11)

де - час відводиться на (N -1) -й крок, а - на наступний.

У загальному випадку для i -го кроку маємо

. (12)

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

. (13)

вираз ( 13 ) Являє собою функцію Беллмана і її значення, розраховане для першого кроку від аргументу ТСР, є максимально досяжна ймовірність успіху при заданому часу пошуку ТСР. Повторний прохід по дереву пошуку, але вже від першого рівня до останнього, дозволяє відновити значення часів аналізу Ti, що призвели до знайденої ймовірності успіху. Виходячи з відомих Ti можна визначити ймовірності правильного рішення на кожному з кроків пошуку Qi.

на Мал. 4 представлені залежності часу пошуку сигналу в частотному діапазоні при (Перший підхід) і пошуку, оптимізованого методом динамічного програмування (другий підхід).

Мал. 4. Порівняння двох підходів до побудови дихотомічного пошуку

Як випливає з малюнка, метод динамічного програмування дозволяє найкращим чином розподілити загальний час пошуку між кроками. При цьому розподіл часу призводить до того, що на перших кроках ймовірність правильного рішення нижче, ніж на останніх. В результаті спостерігається виграш перед першим підходом, причому виграш зростає з ростом величини частотного діапазону А і зі зниженням відносини сигнал / шум.

3. Порівняння послідовного і дихотомічного пошукових алгоритмів

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

Спочатку визначимо верхню і нижню межі відносини середніх часів пошуку. При великому відношенні сигнал / шум для винесення рішення на кроці пошуку, незалежно від пошукового алгоритму, потрібно один відлік. При послідовному пошуку максимальне число кроків одно A-1 і при равновероятном знаходженні сигналу в межах частотного діапазону середнє число кроків одно (A-1) / 2, а мінімальне середнє час пошуку одно

. (14)

При дихотомії середній час одно

. (15)

В результаті поділу ( 14 ) На ( 15 ) Виходить R = A / 4. Таким чином, граничний виграш дихотомії пропорційний величині області невизначеності А.

Аналіз поведінки кривих рис.2 і рис.4 в області низьких відносин сигнал / шум h 0 2, представлених в логарифмічному масштабі, дає підстави апроксимувати їх такими функціями:

, (16)

, (17)

де відношення сигнал / шум h02 виражено в децибелах, а kа - коефіцієнт визначається величиною області невизначеності А. Так для послідовного пошуку при Q = 0.9 і А = 32; 64; 128 коефіцієнт kа = 2,678; 3,01; 3,346 відповідно. Для дихотомії kа = 2,39; 2,704; 3,01. Виходячи з виразів ( 16 ), ( 17 ) Можна визначити величину h02, нижче якої послідовний пошук буде швидше дихотомічного:

. (18)

Для А = 32; 64; 128 дана величина дорівнює відповідно h02 = -18; -19.1; -21 дБ.

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

Мал. 5. Ставлення середніх часів послідовного і дихотомічного пошуку

висновок

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

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

література

1. Канівський З.М., Литвиненко В.П. Теорія скритності. - Воронеж: Изд-во ВДУ, 1991. - 144с.

2. Василенко О.О. Автореферат дисертаційної роботи "Оптимізація пошуку сигналів зв'язку і управління в задачах аналізу скритності". Воронеж, ВГТУ 1999.

3. Беллмана Р. Процеси регулювання адаптацією. М., 1964.

Автор:

Філатов Анатолій Геннадійович, е-mail: filatov @kodofon .vrn .ru ,

Воронезький Науково-дослідний Інститут Зв'язку