6.3. Показатели и оценка эффективности циклических процедур поиска

Как отмечалось выше, назначением подсистемы синхронизации является введение СРС в работоспособное состояние и поддержание этого состояния в течение передачи сообщения. Исходя из назначения подсистемы синхронизации, определяются показатели эффективности и их характеристики.

Рассмотрим эффективность циклических процедур поиска с поочередным алгоритмом обзора поискового пространства . Правила функционирования таких процедур поиска подробно описаны в [56,57,59,65,66] и имеющейся в них библиографии. Далее используются модель, терминология и обозначения, принятые в [66].

Будем рассматривать упрощенную математическую модель, когда случайный процесс , аппроксимируется дискретным марковским процессом  с конечным числом состояний из дискретного множества , полагая  при  - длительность одного шага поиска (рис.6.13).

Рис. 6.13.

При этом на каждом шаге поиска анализируется только одна точка из . Диаграмма циклического поиска для этого случая изображена на рис.6.14, где пунктиром показан процесс , а сплошной линией - траектория сканирования поисковой системы;  - правило обзора точек : если  то на  шаге анализируется точка .

Рис. 6.14.

В общем случае [67] статистические характеристики дискретного марковского процесса , задаются вектором вероятностей начальных состояний

                             (6.15)

и совокупностью матриц переходных вероятностей состояний процесса  от  шага к  шагу

   (6.16)

где  обозначает транспонирование;

       (6.17)

Здесь и далее символом  обозначается вероятность события , а символом  - условная вероятность.

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

.

Кроме того, исключим возможность перехода процесса  через траекторию обзора  на каждом цикле  без совпадения горизонтальных участков (см. рис.6.14), а также - возможность многократных пересечений на одном цикле процесса  с траекторией обзора ,  и - возможность «скольжения» по ней. Для дискретных марковских процессов такого типа элементы матриц  должны удовлетворять внутри цикла , например, следующей системе ограничений:

, ,                          (6.18)

при

Элементы матриц  могут быть любыми, удовлетворяющими обычным ограничениям (6.17). Решение о наличии (отсутствии) сигнала на каждом шаге поиска (т.е. в каждой точке ) выносится по правилу бинарного обнаружения, оптимальному в смысле критерия Неймана-Пирсона [54]. При этом вероятности  - пропуска сигнала в точках , содержащих сигнал, и вероятности  - ложного обнаружения в точках , не содержащих сигнал, полагаем постоянными на всех шагах и циклах поиска. Наблюдаемые реализации помех полагаем статистически независимыми на разных шагах поиска [68].

Эффективность поиска при гипотезе   - о наличии сигнала, будем характеризовать вероятностями  - правильных и - ошибочных решений о значении параметра сигнала и средним временем поиска  при гипотезе  - об отсутствии сигнала - вероятностью  - ложного обнаружения (ложных тревог) за циклов обзора и средним временем  до окончания поиска ложным обнаружением [68].

Определим вероятности  и . Вероятность окончания поиска на первых  циклах правильным обнаружением равна

               (6.19)

где  -  событие правильного обнаружения на -м цикле; ,  - событие - пройти без остановки -й цикл;

Вероятность окончания поиска на первых циклах ошибочным решением -

                                              (6.20)

где .

Поскольку наблюдаемые реализации предполагаются статистически независимыми, а  и  - постоянными на всех шагах и циклах поиска,  для

        (6.21)

Вероятности  в (6.19) можно представить как

                         (6.22)

где  - событие правильною обнаружения на  шаге  цикла обзора, .

Пусть  - событие остановки на  шаге  цикла. Тогда

 (6.23)

где для  вероятность

      (6.24)

Используя известные соотношения [67,69], получим для вероятностей

               (6.25)

где  - элементы матрицы

                                            (6.26)

переходных вероятностей процесса  на  шаге -гo цикла;  - единичная матрица |69];

                                   (6.27)

координаты вектора

                                    (6.28)

вероятностей начального состояния процесса  на  цикле,

                                                                                   (6.29)

Подставляя (6.26), (6.27) в (6.25) и (6.23)-(6.25) в (6.22), получим для (6.19)

           (6.30)

где  - матрица, обратная к ;

                                            (6.31)

Финальные вероятности  и  равны пределам

                  (6.32)

Поскольку, как это следует из (6.21), , то из (6.20) имеем

                                                 (6.33)

и, следовательно, поиск всегда заканчивается с вероятностью единица. Из (6.30), (6.32) и (6.33) окончательно получим

               (6.34)

В отсутствие сигнала (гипотеза ) вероятность ложных тревог  первых циклов равна [68]

                                      (6.35)

Определим среднее время поиска. Если условия регулярности  при обнаружении выполнены, то среднее время поиска  можно представить как условное (при  и ) математическое ожидание

                                  (6.36)

суммы случайного числа  случайных величин - длительностей циклов , где  - математическое ожидание по .

В рассматриваемой поисковой модели (см. рис.6.14) целочисленная случайная величина  - число циклов - не зависит от будущего и . Тогда, согласно теореме Колмогорова-Смирнова [70], имеет место тождество

           (6.37)

которым воспользуемся для вычисления (6.36).

Определим среднее время поиска  при гипотезе . Среднюю длительность  произвольного  цикла можно представить как

    (6.38)

где

                      (6.39)

  - вероятность остановки поиска на  шаге  цикла при условии, что  и пройдено без остановки  циклов.

Можно показать, что вероятность  не зависит от события  и определяется следующим выражением:

                                               (6.40)

Подставляя (6.40) в (6.39), получим для (6.38)

    (6.41)

Выражение в квадратных скобках в (6.41) равно среднему числу поисковых шагов на  цикле, которое обозначим . Тогда

                                                                    (6.42)

Используя (6.25)-(6.28), получим

  (6.43)

Для вероятности  в (6.37) имеем с учетом (6.31)

     (6.44)

Подстакляя (6.42)-(6.44) в (6.37), получим для среднего времени поиска

                (6.45)

где

                                                (6.46)

- среднее число поисковых шагов длительностью  (среднее нормированное время поиска) при наличии сигнала [68]. Подставляя (6.43) в (6.46), окончательно получим

   (6.47)

Сопоставляя выражения (6.34) и (6.43), можно видеть, что при  среднее время поиска  и вероятность правильного обнаружения  связаны простыми соотношениями

,

которые удобны при оптимизации параметров  циклических процедур поиска.

Вычислим среднее время  до окончания поиска ложным обнаружением. Средняя длительность одного цикла обзора при гипотезе

,

где среднее число шагов на одном цикле -

.

Среднее нормированное время

                                            (6.48)

и, следовательно,

                                                   (6.49)

Если на каждом шаге поиска используется несмещенное правило обнаружения [54], т.е. когда

                                                      (6.50)

то при  выполняется неравенство

 или   .                          (6.51)

Следовательно,  является верхней границей для  при всех возможных значениях параметров несмещенных алгоритмов обнаружения (6.50); в частности, при любых значениях отношения сигнал-помеха. Доказательство этого факта дано в приложении П.6.1.

Рассмотрим конкретные примеры использования соотношений (6.34), (6.47). Выражения (6.36) и (6.48) для  и  остаются неизменными для всех рассматриваемых ниже примеров.

Пример 1. Пусть параметры обнаруживаемого сигнала  не изменяются в процессе поиска  и с вероятностью , могут находиться в одной из точек множества  (рис.6.15).

Рис. 6.15.

Выражения для  и  в этом случае получим из (6.34), (6.47), подставляя в них матрицы переходных вероятностей (6.16), заданные в форме:  для . После соответствующих преобразований получим

                                             (6.52)

                                                  (6.53)

Для случая равномерного распределения  на , когда , получим из (6.52), (6.53) соотношения:

;                                    (6.54)

                          (6.55)

Пример 2. Пусть процесс , не изменяется в течение одного цикла обзора, но изменяется как марковская последовательность от цикла к циклу, т.е.  при  (рис.6.16).

Рис. 6.16.

Требование постоянства процесса  внутри цикла формально означает, что  для . Тогда из (6.26), (6.29) имеем: . Будем полагать, что процесс , однородный [67,69], т.е.

Подставляя  и  (6.34), (6.47), получим для  и  следующие выражения:

         (6.56)

.                                     (6.57)

Соотношения (6.56), (6.57) являются более общими по сравнению с (6.34), (6.47), поскольку в данном случае на элементы матриц переходных вероятностей  никаких ограничений, кроме обычных (6.16), не накладывается. Для иллюстрации этого факта рассмотрим следующие примеры.

Пример 3. Пусть случайный процесс , , флуктуирует независимо от цикла к циклу. Это означает [67], что элементы матрицы  удовлетворяют условию. Тогда и из (6.56), (6.57) получим, что выражения для и  в этом случае совпадают с (6.52), (6.53). Таким образом, эффективность циклического поиска оказывается одинаковой как в случае неизменяющегося параметра сигнала, так и при независимых флуктуациях от цикла к циклу.

Пример 4. Процесс , независимо флуктуирует от шага к шагу поиска. Это означает [67], что элементы матрицы  (6.16) внутри цикла  должны удовлетворять условию . Получить в этом случае выражения для  и  непосредственно из (6.34),(6.47) нельзя, поскольку ограничения (6.18), при которых справедливы (6.34), (6.47), теперь не выполняются.

Определим вероятности  и. Из (6.19)-(6.30), с учетом статистической независимости флуктуации процесса , после преобразований, аналогичных тем, которые описаны в примере 3, получим для  (6.19)

                                                                            (6.58)

где  и  для .

Тогда из (6.32), (6.33) для рассматриваемого случая (6.58) имеем

                                                 (6.59)

Вероятность пройти без остановки один цикл обзора -

                                                            (6.60)

где

                                   (6.61)

   (6.62)

Подставляя в (6.62) для рассматриваемого случая   получим

.                  (6.63)

Вероятность  определяется выражением (6.25), где, с учетом независимости флуктуации процесса  и из (6.26) имеем

;

 - событие: пройти без остановки  шагов одного цикла обзора.

Представляя  в форме, аналогичной (6.23), можно показать, что

,

и, следовательно, вероятность  определяется из (6.25) в виде:

.             (6.64)

Подставляя (6.60), (6.63) и (6.64) в (6.59), получим для

.                     (6.65)

Определим среднее время поиска  при гипотезе . В рассматриваемом случае распределения числа шагов в цикле одинаковы на всех циклах обзора, так что  для . Тогда равенство (6.37) переходит в тождество Вальда [70] и среднее время поиска

,               (6.66)

где  - среднее число циклов [68].

Из (6.38)-(6.41) получим

.                       (6.67)

Подставляя (6.60), (6.63) в (6.67), имеем для

. (6.68)

В частном случае равномерного распределения значений случайного процесса  на , т.е.  получим из (6.65), (6.68)

;                     (6.69)

.                  (6.70)

И в этом случае при выполнении условия несмещенности (6.50) для  справедливо неравенство  (6.51).

Для случая равномерного распределения значений случайного процесса сравним показатели эффективности (6.54), (6.55) при постоянном (нефлуктуирующем) параметре сигнала (пример 3) с показателями эффективности (6.69), (6.70) при независимых флуктуациях процесса  (пример 4).

Сначала рассмотрим асимптотический случай  (очень большое отношение сигнал-помеха). Обозначим через  показатели эффективности (6.54), (6.55) при постоянном параметре сигнала, а через  - для случая независимых флуктуации (6.69), (6.70). Устремляя  и  к нулю, получим из (6.54), (6.55) и (6.69), (6.70)

Таким образом, в этом предельном случае при одинаковых вероятностях правильного обнаружения среднее время поиска при нефлуктуирующем параметре сигнала в два раза меньше, чем при флуктуирующем (для ).

Сравнение в этом частном случае для произвольных  показывает (см. приложение П.6.2), что всегда

 и .

Другими словами, флуктуации параметра , по которому осуществляется поиск сигнала , приводит к уменьшению вероятности правильного обнаружения и возрастанию среднего времени поиска, т.е. - к снижению эффективности циклических процедур поиска рассмотренного вида.