СПОСОБ КООРДИНАЦИИ МНОЖЕСТВА ДАТЧИКОВ
METHOD OF COORDINATING MULTIPLE SENSORS

Настоящее изобретение относится к способу для координации множества датчиков согласно преамбуле пункта 1 формулы изобретения.
Изобретение также относится к системе датчиков, в частности к системе обнаружения, содержащей множество датчиков, которые координируются друг с другом для того, чтобы исполнять один или более сервисов, требующихся системе обнаружения.
В частности, изобретение может быть предпочтительным образом и с пользой применено к системе видеонаблюдения, в которой множество видеокамер и датчиков различных типов (например, инфракрасных или микроволновых датчиков) позволяет обнаруживать такие события, как присутствие нарушителей или пожар, и сигнализировать о них одной или более станциям контроля, где человек-оператор может принять соответствующие меры, зависящие от обнаруженного события; например, оператор может взять на себя управление видеокамерой для того, чтобы снимать ею определенную область, где были обнаружены нарушитель или пожар.
Таким образом, через станцию контроля оператор может посылать команды различным видеокамерам или, в более общем случае, запрашивать сервисы у системы видеонаблюдения, например, последовательное представление всех изображений, полученных видеокамерами (эта функция обычно именуется как «патрулирование»), или функции автоматического отслеживания, в которых видеокамеры координируются станцией контроля с целью слежения за определенным объектом.
Согласно известным решениям задача оператора упрощается путем выполнения сценариев на уровне станции контроля, каковые сценарии могут, например, в ответ на сигнал тревоги, подаваемый датчиком, располагать видеокамеры в определенных предварительно заданных положениях (предварительно определенных при установке системы).
В этих известных системах датчики координируются централизованно некоторым центральным блоком, посылающим команды на датчики.
Однако такие системы страдают тем недостатком, что они не используют алгоритмы упреждающей координации и, следовательно, не могут надлежащим образом справляться со сложными ситуациями, которые требуют динамического поведения системы.
В этих системах координация различных устройств не принимает во внимание все требующиеся сервисы, поскольку она просто выполняет сервис за сервисом; например, если сигнал видеокамеры потребуется для двух различных сервисов, то центральный терминал будет пытаться исполнять оба сервиса так, как будто не было никакого конфликта вообще, заботясь о выделении видеокамеры только приоритетному сервису; сервис же, имеющий меньший приоритет, таким образом, будет исполнен не полностью.
Более того, эти системы также страдают тем недостатком, что, если система обнаружения используется множеством операторов, то могут возникать конфликты между запросами различных операторов.
Кроме того, эти системы сталкиваются с аналогичными проблемами конфликта, когда имеют место множественные события или множественные объекты, подлежащие отслеживанию.
Вообще говоря, известно, что, в качестве альтернативы централизованному управлению, координируемые устройства могут быть снабжены "агентами", способными координироваться автономно путем согласования единых задач, подлежащих выполнению для достижения определенного командного результата.
Это решение, которое обычно применяется в очень специфических областях техники, таких как робототехника (смотри, например, US 6636781), не оказалось очень эффективным в системах обнаружения (в частности, в системах видеонаблюдения), где наиболее важными являются реактивность и стабильность.
Время, необходимое для согласования задач, проводимого среди различных устройств, может быть фактически очень длительным, когда имеется большое количество устройств и их возможных конфигураций; как следствие, система этого вида, в которой координация основана на согласовании, проводимом среди устройств, оказывается не очень реактивной и потенциально нестабильной.
Например, рассмотрим случай пожара: в ответ на сигнал тревоги агенты, управляющие различными устройствами, начнут согласовывать задачи, выполняемые каждым из них.
Если время, требуемое для координации, слишком велико, будет существовать риск того, что видеокамеры скоординируются и покажут область пожара только тогда, когда пожар уже широко распространится.
К тому же, по мере распространения пожара другие датчики будут передавать сигнал пожарной тревоги в других областях, примыкающих к первой области, где пожар начался; таким образом, будут иметь место дополнительные запросы о показе упомянутых других областей. Если процесс принятия решений будет медленнее, чем распространение пожара, то агенты продолжат согласовывать подлежащие выполнению задачи (которые будут меняться в соответствии с затребуемыми сервисами), фактически не выполняя запросы; следовательно, система станет нестабильной.
Аналогичные или худшие проблемы с реактивностью могут возникать в случае, если требуются длительные согласования между агентами, которые должны исполнять сервис. Когда объект выходит из поля зрения датчика, соседние датчики скоординируются таким образом, чтобы охватывать те области, где может быть расположен этот объект. Следовательно, датчики должны охватывать упомянутые области быстро и надлежащим образом так, чтобы сервис по отслеживанию мог продолжаться. Если объект выходит из зоны действия датчика, который его отслеживает, то до тех пор, пока агенты не придут к соглашению в отношении того, какие задачи должны быть выполнены, сервис по отслеживанию далее продолжаться не может.
Из этого следует, что системы обнаружения остро нуждаются в эффективной координации датчиков, которая позволяет оптимизировать ресурсы системы, выполняя требуемые сервисы наилучшим образом, например, реактивным образом восполняя невозможность использования определенной видеокамеры для данного сервиса путем использования других видеокамер в соответствующих местах расположения.
Задача настоящего изобретения заключается в том, чтобы решить проблемы предшествующего уровня техники, предложив альтернативный способ для координации множества датчиков, так же как и связанную с ним систему наблюдения.
Эта задача решается посредством способа и системы, имеющие признаки, изложенные в прилагаемой формуле изобретения; подразумевается, что они составляют неотъемлемую часть настоящего описания.
Настоящее изобретение основано на общей идее использования множества сетевых компьютеров для управления множеством датчиков в ответ на один или более запросов на сервис, принимаемых по сети.
Компьютеры обмениваются информацией, так что каждый компьютер знает характеристики других компьютеров и сервисы ими предоставляемые; таким образом, все компьютеры знают фактическое состояние системы и, в частности, какие компьютеры принадлежат к какой группе, назначенной исполнять данный сервис.
Для того чтобы координироваться друг с другом, компьютеры, участвующие в одном и том же сервисе, исполняют один и тот же алгоритм конфигурирования, который выдает в качестве результата задачи, подлежащие выполнению каждым компьютером.
Поскольку все компьютеры, принадлежащие некоторой группе, исполняют один и тот же алгоритм конфигурирования, то все они определят одну и ту же оптимальную конфигурацию датчиков и будут управлять датчиками соответствующим образом.
Де-факто, координацию датчиков получают, таким образом, посредством распределенной логики без необходимости прибегать к длительным, сложным согласованиям, проводимым среди различных компьютеров.
Согласно предпочтительному и выгодному варианту реализации изобретения компьютеры исполняют алгоритм конфигурирования периодически; таким образом, система может динамически переконфигурироваться и принимать во внимание любые изменения в наборе требуемых сервисов или в наборе датчиков, готовых к использованию системой для исполнения различных сервисов. Это оказывается очень выгодным, потому что в случае неисправности датчика или вмешательства в работу датчика, будут скоординированы другие датчики для того, чтобы восполнить утрату этого датчика.
В дополнение к этому, предпочтительно, чтобы компьютеры могли исполнять алгоритм в ответ на новый запрос, обеспечивая, таким образом, хорошую реактивность в ответ на запрос сервиса.
Другие задачи и преимущества настоящего изобретения станут очевидны из нижеследующего описания и из прилагаемых чертежей, которые приводятся в качестве неограничивающего примера:
на фиг.1 показана система видеонаблюдения, соответствующая настоящему изобретению;
фиг.2 представляет собой блок-схему алгоритма способа для координации множества датчиков, соответствующего настоящему изобретению;
на фигурах 3а, 3b и 3с показана модель окружающей среды, используемая системой для активирования видеокамер;
на фигурах 4а и 4b показана модель окружающей среды, используемая системой для активирования видеокамер.
На фиг.1 ссылочная позиция (1) в схематичном виде обозначает окружающую среду, подлежащую контролю. Окружающая среда (1) состоит из здания (11) и находящегося на открытом воздухе внутреннего двора (12).
В пределах окружающей среды (1) идентифицированы следующие области, представляющие особый интерес:
вход в здание - область (С 1);
место (Р 1) стоянки автотранспорта-область (С 2);
место (Р 2) стоянки автотранспорта - область (С 3);
входные ворота - область (С 4);
Окружающая среда (1) контролируется посредством системы видеонаблюдения, содержащей пару станций (3) контроля и множество датчиков (S 1)-(S 5), при помощи которых операторы системы могут контролировать окружающую среду (1).
В данном описании термин «датчик» будет относиться к любому устройству, которое позволяет обнаруживать физическую величину (например, интенсивность электромагнитных сигналов, таких как световые или радиоволны) и обрабатывать соответствующий электронный сигнал.
В этом смысле датчики могут включать в себя индикаторы задымленности (например, индикаторы задымленности, основанные на эффекте Тиндаля, используют фотодиод для обнаружения светового сигнала, распространяющегося в камере обнаружения в присутствии дыма), так же как и видеокамеры, которые передают видеосигнал, пропорциональный электромагнитному излучению, поступающему в линзу объектива и попадающему в прибор с зарядовой связью (ПЗС-прибор).
В примере, показанном на фиг.1, области (С 1)-(С 4) контролируются четырьмя видеокамерами (S 1)-(S 4) и одним волюметрическим датчиком (S 5), расположенным в пределах окружающей среды, подлежащей контролю.
Количество областей, на которые разделена окружающая среда, и количество датчиков (видеокамер и других датчиков) не являются факторами, ограничивающими изобретение, но зависят от выбора установщика оборудования.
Видеокамеры (S 1)-(S 4) могут быть неподвижными или подвижными, в частности, типа PTZ (с возможностью поворота / наклона / трансфокации).
В примере, показанном на фиг.1, видеокамеры (S 1) и (S 3) представляют собой неподвижные видеокамеры и снимают только соответствующие области (С 1) и (С 3), тогда как видеокамеры (S 2) и (S 4) представляют собой видеокамеры PTZ-типа, способные снимать, соответственно, области (С 1)-(С 2) и (С 3)-(С 4).
Волюметрический датчик (S 5) представляет собой неподвижный датчик и посылает сигнал тревоги в случае, когда он обнаруживает движение внутри здания (11), например, потому что дверь на входе (С 1) открывается.
Датчиками управляет множество компьютеров, способных поддерживать связь друг с другом по сети (2) передачи данных таким образом, чтобы посылать информацию на другие компьютеры или станцию (3) контроля или принимать информацию от них.
С этой целью компьютеры снабжены соответствующим "агентом"; ниже этот термин относится к объекту программного обеспечения или аппаратно реализованного программного обеспечения, способному действовать автономно вместо пользователя и принимать решения о задачах, подлежащих выполнению.
Агент, следовательно, представляет собой программное обеспечение или аппаратно реализованное программное обеспечение, которое исполняется в компьютерах, управляющих датчиками, и которое де-факто определяет то, какие данные посылаются компьютером по сети или на управляемые датчики; по этой причине, в данном описании ссылка будет делаться без проведения различия как на сетевые агенты, так и на сетевые компьютеры.
Компьютеры могут быть встроены в датчики, как в случае видеокамер (S 3) и (S 4), или, в ином случае, быть серверными блоками (4), с которым соединены датчики.
Серверные блоки (4) оснащены сетевым интерфейсом (41), который позволяет агенту принимать и отправлять данные по сети (2), и управляющим интерфейсом (42) для поддержания связи с одним или более датчиками, подлежащими управлению.
Когда компьютер и связанный с ним агент встроены в датчик, этот датчик будет также снабжен сетевым интерфейсом, позволяющим агенту поддерживать связь по сети (2).
Сеть (2) передачи данных может представлять собой проводную LAN-сеть (локальную сеть), но, конечно же, упомянутая сеть передачи данных может также содержать беспроводные элементы, которые могут облегчать установку датчиков.
В предпочтительном варианте реализации, каждый узел сети (станции (3) контроля или компьютеры, которые управляют датчиками (S 1)-(S 5)) может поддерживать связь с любым другим узлом сети; сеть (2) может также подразделяться на множество виртуальных сетей (VPN-сеть, виртуальная частная сеть), и связь между двумя узлами, принадлежащими различным виртуальным частным сетям, может быть подчинена ограничениям.
Станция (3) контроля содержит компьютер (31), который принимает изображения от видеокамер и отображает их на соответствующих средствах (32) визуализации, приспособленных для того, чтобы отображать множество изображений (33) одновременно.
Предпочтительно, чтобы упомянутые средства визуализации содержали множество экранов или единственный экран, отображающий несколько изображений рядом друг с другом (это решение известно как мультиплексирование).
Станция (3) контроля также содержит другие известные по своей сути компоненты, такие как клавиатура (34), мышь (35) и джойстик (36), используемые оператором для того, чтобы управлять видеокамерами PTZ-типа, изменяя углы их поворота, наклона и трансфокации.
Как и средства визуализации, эти компоненты также соединены с компьютером (31), который оснащен соответствующими интерфейсами, например, интерфейсом для джойстика (36), видеоинтерфейсами для отправки изображений, принятых от видеокамер (S 1)-(S 4), средствам (32) визуализации и сетевым интерфейсом, через который управляющие данные отправляются видеокамерам.
Этот пользовательский интерфейс, наряду с клавиатурой, джойстиком и мышью, позволяет пользователю выбирать и управлять видеокамерами, активируя, таким образом, передачу изображения от одной или более видеокамер средствам (32) визуализации.
Когда выбрана какая-либо из областей (С 1)-(С 4), например место стоянки (Р 2) автотранспорта, то изображение передается от видеокамеры, например (S 2), которая автоматически ассоциативно связана с выбранной областью согласно предварительно заданному критериальному нацеливанию, которое описано ниже, при максимизации вероятности обнаружения аномального события внутри представляющей интерес области.
Для того чтобы исполнять сервисы, запрашиваемые для системы оператором (например, управление видеокамерой (S 2) или охват ячейки (С 3)), станция контроля отправляет по сети запрос на обслуживание, каковой запрос затем обрабатывается агентами компьютеров согласно стратегии, которая описана ниже, которая приведет к определению того, какие компьютеры должны участвовать в сервисе и как такие компьютеры должны управлять соответствующими датчиками для того, чтобы выполнить запросы оператора.
Следовательно, для обеспечения координации система наблюдения, показанная на фиг.1, использует распределенную архитектуру без центрального узла координации: все узлы сети (компьютеры, управляющие датчиками, и станции контроля) представляют собой одноранговые узлы, то есть узлы, состоящие в равноправных отношениях друг с другом.
Для того чтобы координироваться друг с другом (а следовательно, также координировать датчики), все агенты, соединенные с сетью (2), обмениваются информацией, так что каждый агент знает состояние системы видеонаблюдения.
В частности, от каждого агента сделана доступной для других агентов информация о состоянии компьютера и действиях, выполняемых в текущий момент этим агентом; например:
- общие данные, касающиеся функционирования компьютера: например, наличие выполняемых действий, загрузка центрального процессора, количество обращений к этому компьютеру и т.д.;
- данные, касающиеся сервисов, над которыми в текущий момент работает этот агент: например, тип сервиса, идентификатор станции контроля, которая запрашивала этот сервис, состояние сервиса, состояние датчика, используемого для исполнения этого сервиса, и т.д.;
- обнаруженные события.
В предпочтительном варианте реализации изобретения запросы отправляются без разбора всем узлам сети (2), хотя возможны также и другие решения, что будет более подробно описано ниже.
Запросы на сервисы могут быть отправлены либо агентами, управляющими датчиками, либо станциями (3) контроля; таким образом, агенты, управляющие датчиками, будут отвечать на запросы оператора так же, как и на запросы от других агентов.
Например, если агент, который управляет волюметрическим датчиком (S 5), отправляет запрос охватить видеокамерами область, где было обнаружено проникновение, агенты, которые управляют видеокамерами (S 1)-(S 4), скоординируются таким образом, чтобы охватить упомянутую область, допуская при этом другие ожидающие сервиса запросы.
Периодически или когда получен запрос, агенты осуществляют стратегию координации, описанную ниже, согласно которой агенты, участвующие в одном и том же сервисе, осуществляют один и тот же алгоритм конфигурирования, который выдает оптимальную конфигурацию агентов, задействованных в исполнение сервиса; эта конфигурация представляет собой конфигурацию, которая позволяет исполнять запрашиваемые сервисы наилучшим образом, возможно, путем оптимизации использования ресурсов системы.
Поскольку агенты осуществляют один и тот же алгоритм, начиная с одних и тех же входных переменных (относящихся к состоянию системы), они придут к одним и тем же заключениям в отношении оптимальной конфигурации управляемых датчиков; в частности, агенты знают, например, то, как должна быть расположена данная видеокамера и на какую величину трансфокации она должна быть настроена, какая видеокамера должна передавать полученное видео на данную станцию контроля, какая видеокамера должна сохранять полученный видеосигнал в памяти и т.д.
Стратегия
Предпочтительная стратегия координации осуществляется периодически всеми агентами и имеет структуру, состоящую из двух этапов:
- формирование групп агентов, которые участвуют в исполнении различных сервисов, запрашиваемых в сети;
- определение и применение групповой стратегии для данного сервиса. Упомянутую стратегию выполняют, обращаясь к алгоритму, именуемому «алгоритм координации», первая часть которого (формирование группы) идентична для всех сетевых агентов, тогда как вторая часть (определение стратегии группы) идентична для всех агентов, принадлежащих одной группе.
Теперь со ссылкой на фиг.2 будет описан этот алгоритм координации (то есть набор операций, которые следует выполнять для того, чтобы достигнуть координации датчиков).
После начала исполнения алгоритма (этап 100) агент, который исполняет алгоритм координации, сначала проверяет (этап 101), может ли одно из управляемых им устройств быть задействовано в исполнение одного или более сервисов, запрашиваемых у системы.
Согласно примеру, показанному на фиг.1, если имеется только один запрос, требующий контролировать вход в здание (11) (ячейка (С 1)), то агент, который управляет видеокамерой (S 4), определяет, что он не может участвовать в запрашиваемом сервисе, потому что видеокамера (S 4) не может снимать эту область ни из какого положения.
Если агент не участвует ни в каком сервисе, то он отправит по сети информацию, указывающую его состояние и то, что он не будет участвовать ни в каком сервисе (этап 105).
В противоположность этому, если агент может быть задействован в исполнение одного или более сервисов, то он определит (этап 102), имеет ли он достаточно ресурсов для исполнения всех сервисов, в которых он может быть задействован; если "да", то он проинформирует других сетевых агентов, отправив обновленную информацию о своем состоянии, указывая, что он не будет участвовать ни в каком сервисе (этап 105).
Если имеющиеся в распоряжении агента ресурсы будут не достаточны, то он будет сортировать запрашиваемые сервисы (этап 103), в которых он может быть задействован, в соответствии с соответствующим планом приоритетов.
Такого рода план приоритетов может, например, относиться к уровням приоритетов, присвоенным операторам, станциям (3) контроля, различным сервисам и т.д.
Таким образом, для уже обслуживаемых операторов, имеющих один и тот же приоритет и запрашивающих различные сервисы, отсылка будет сделана на приоритет, присвоенный различным типам сервисов. Например, сервисы, требующие охвата областей, будут иметь более низкий приоритет, чем другие сервисы, требующие управления определенным датчиком. И в самом деле, первые из упомянутых сервисов могут быть обеспечены с большей легкостью другими подмножествами агентов, тогда как последние из упомянутых сервисов не дают никакой свободы выбора (запрос касается конкретного датчика).
После того, как сортировка завершена, агент выбирает (этап 104) сервисы, в которых он будет участвовать, начиная с сервиса, имеющего самый высокий приоритет до тех пор, пока имеющиеся в распоряжении этого агента ресурсы не будут израсходованы.
Набор сервисов, выбранный, таким образом, агентом, затем делают доступным для всех других сетевых средств (105).
Алгоритм координации затем выжидает предварительно заданный промежуток (Т) времени (этап 106) до тех пор, пока он не примет обновленную информацию о состоянии других агентов в сети.
В конце этого первого этапа алгоритма координации каждый агент знает, какие агенты были назначены на те же самые сервисы, что и он, то есть, знает компоненты группы.
Здесь следует отметить, что в этом варианте реализации изобретения процесс формирования группы (этапы 100-106) не требуют никакого взаимодействия среди агентов, так как каждый агент выбирает сервисы в соответствии с планом приоритетов, независимо от других агентов.
На самом деле, второй этап этой стратегии выполняется только теми агентами, которые участвуют в сервисе некоторого типа.
На этапе 107 проверяется, должен ли агент участвовать в некотором сервисе или нет.
Если "нет", то агент завершает алгоритм взаимодействия (этап 110); в ином случае каждый агент, участвующий, по меньшей мере, в одном сервисе, будет исполнять конкретный алгоритм конфигурирования (этап 108) для каждого сервиса, в котором он должен участвовать.
Например, все те агенты, которые должны участвовать в сервисе по охвату, запрашиваемом для конкретной области окружающей среды, будут исполнять один и тот же алгоритм для оптимального охвата, который, используя в качестве входных данных характеристики агентов, принадлежащих группе, выдаст в качестве результата оптимальную конфигурацию группы, определяющую задачи, которые каждый агент должен будет выполнять для того, чтобы обеспечить наилучший охват данной области.
Таким образом, агенты группы придут к одним и тем же заключениям и будут управлять соответствующими датчиками скоординированным образом, в соответствии с логикой (определенной алгоритмом конфигурирования), которая является общей для всех агентов.
Некоторые примеры алгоритмов конфигурирования будут представлены в конце данного описания.
После того, как были исполнены различные алгоритмы конфигурирования (например, алгоритмы оптимального охвата или избрания лидера), выходные данные которого представляют собой набор задач, подлежащих выполнению каждым агентом, агенты будут соответствующим образом управлять соответствующими датчиками (этап 109); алгоритм координации тогда закончится (этап 110).
Хотя в вышеописанном варианте реализации изобретения алгоритм координации выполняется периодически (например, каждый раз, когда переключается таймер), согласно другому возможному варианту реализации изобретения алгоритм также (или только в качестве альтернативы) исполняется в ответ на изменение в наборе сервисов, запрашиваемых у системы. Упомянутое изменение известно всем агентам, которые всегда знают обо всех сервисах, запрашиваемых у системы.
Способы передачи данных по сети
В предпочтительном варианте реализации изобретения для передачи данных между узлами сети используются различные протоколы связи в зависимости от типа пересылаемой информации, в частности:
- для информации, которая будет совместно использоваться всеми узлами сети (например, информация о состоянии агентов и запросы сервисов), используется пульсирующая широковещательная передача данных;
- для информации, касающейся конкретной станции контроля (например, потока аудио-/видеоданных и потока управляющих данных), используется двухточечная или радиально-узловая многоточечная передача данных;
Пульсирующая передача данных
При этом типе пульсирующей передачи данных, пакеты данных отправляются одновременно и неоднократно во множество узлов; такие пакеты данных именуются «сердцебиение» (потому что повторение / пульсация данных напоминает сердцебиение).
Пульсирующая передача пакетов "сердцебиения" обычно происходит по сети с заданной частотой в диапазоне нескольких Герц, без необходимости в каком бы то ни было синхронизме между "сердцебиениями" различных агентов.
Частоту определяют во время этапа планирования системы наблюдения и устанавливают во время этапа настройки системы наблюдения.
Значение частоты влияет на то, как быстро сетевые агенты будут принимать информацию о состоянии каждого другого агента: например, с частотой 0,1 Гц, изменение состояния, происходящее непосредственно после генерации пакета "сердцебиения", то есть не сообщенное посредством этого пакета "сердцебиения", будет сообщено по сети только, когда будет сгенерирован следующий пакет "сердцебиения", то есть с задержкой, составляющей почти десять секунд.
С чисто теоретической точки зрения, если пакеты "сердцебиения" передавались бы в пульсирующем режиме с очень высокой частотой, теоретически с бесконечной частотой, информация о состояния сети обновлялась бы в режиме реального времени; однако, с практической точки зрения, в реальной системе наблюдения высокая частота передачи вызвала бы чрезмерное увеличение количества переданных пакетов, что имеет два отрицательных последствия:
- увеличенную рабочую нагрузку каждого узла сети, который, с одной стороны, должен генерировать более высокое количество пакетов "сердцебиения", а с другой стороны, должен принимать и анализировать намного больше пакетов (узел, принимает пакеты "сердцебиения" различных других узлов, которые в свою очередь генерируют намного больше пакетов "сердцебиения" в течение той же самой единицы времени);
- увеличенный сетевой трафик.
Экспериментальные тесты показали, что для вариантов применения в видеонаблюдении, при которых состояние сети также включает в себя положение панорамирующих устройств, перемещающихся со скоростью нескольких градусов в секунду, хорошая частота пульсации находится между 1 и 5 Гц, более предпочтительно между 1 и 2 Гц.
При пульсирующей передаче данных согласно изобретению агент может генерировать асинхронные пакеты "сердцебиений", то есть пакеты, которые добавляются к тем, которые обычно многократно передавались бы в пульсирующем режиме агентом.
Асинхронные пакеты особенно важны тем, что они гарантируют, что критически важные данные, такие как данные об обнаружении аномальных событий, передаются по сети своевременно.
Предпочтительно, чтобы такого рода процесс для асинхронной генерации пакетов "сердцебиения" запускался только по мере необходимости (например, когда обнаружено некоторое событие) так, чтобы на систему не влияли проблемы, наподобие тех, что вызваны чрезмерной частотой генерации пакетов "сердцебиения".
Будучи основанной на повторной передаче данных, пульсирующая передача данных устойчива к ошибкам передачи.
Предпочтительно, чтобы пульсирующая передача данных также включала в себя широковещательную передачу пакетов "сердцебиения" всем узлам сети.
Эта широковещательная передача данных позволяет сети одноранговых узлов достигнуть информационной избыточности на множественных узлах: отбор полезной информации, подлежащей анализу или записи, входит в обязанности каждого отдельного узла. Этот процесс обеспечивает оптимизированную избыточность данных. В случае широковещательной передачи данных можно даже оставить сведения о структуре сети и сетевых адресах других узлов, так же как и обработку данных сложного отбора в узле с избыточностью и стратегии передачи данных полностью без рассмотрения.
Информация, отправляемая посредством пульсирующей передачи данных
Посредством пульсирующей передачи данных отправляется следующая информация:
1. информация о состоянии сети: она содержит информацию о состоянии каждого агента и обнаруженных событиях; этот тип информации должен быть всегда обновленным, то есть он должен касаться текущего состояния узла; следовательно, пульсирующая передача данных о состояния продолжается на протяжении всего срока службы системы;
2. обращенный к сети запрос на сервисы: пульсирующая передача этого типа информации начинается в момент, когда сервис должен быть предоставлен, и заканчивается в момент, когда сервис должен быть завершен;
3. выборки аудио-/видеоинформации, отправляемые агентом другим узлам сети.
Эта информация закодирована внутри пакетов "сердцебиений".
Что касается информации о состоянии сети, то связь, основанная на пульсирующей передаче, делает возможным распространение обновленной информации, не требуя при этом от узла отправлять специальные запросы для того, чтобы обновить свои собственные сведения о сети.
С другой стороны, что касается запросов на сервисы, то пульсирующая передача данных позволяет реализовать протокол связи, который не включает в себя никаких сообщений останова: сервис начинается с первого пакета запроса и затем завершается, как только прекращается пульсирующая передача соответствующего запроса. Протокол, в котором завершение сервиса основывается на передаче сообщения останова, не был бы очень устойчивым к ошибкам связи, требуя, таким образом, создания блоков управления передачей данных для обеспечения повторной передачи в случае потери пакета: такие управляющие блоки часто очень сложны и требуют, чтобы адресат сообщения останова был известен.
В дополнение к этому, пульсирующая передача запроса на обслуживание дает то преимущество, что запрос становится настойчивым: агент, который не может ответить немедленно на запрос, будет в состоянии сделать это впоследствии, присоединившись к тем агентам, которые уже работают над запрашиваемым сервисом.
Среди запросов на сервис особого упоминания заслуживают запросы на управление датчиком (например, запрос на управление видеокамерами) и запросы информации (запросы данных из базы данных, например, информации о регистрационном имени (логине) оператора системы).
Процесс пульсирующей передачи данных также используется для того, чтобы передавать выборки аудио-/видеосигнала, которые подходят для частичной реконструкции исходного сигнала (но не для воспроизведения); такие выборки поэтому получают посредством низкочастотной выборки аудио-/видеосигнала.
Этот последний тип информации был добавлен для того, чтобы позволять другим агентам записывать его так, чтобы видеосигнал мог быть восстановлен, даже в случае, когда агент, от которого он берет начало, необратимым образом поврежден или удален.
Низкая частота осуществления выборки и передачи данных по сети согласуется с необходимостью минимизации полосы частот, используемой каждым агентом, так же как и рабочей нагрузки по приему и сохранению выборки.
Протокол для запросов на сервис
Как было упомянуто выше, запросы на сервис отправляются посредством пульсирующей передачи данных.
В этом случае протокол связи включает в себя нижеследующие этапы.
Узел сети (клиент) передает пульсирующим образом по сети всем другим узлам сети запрос на сервис (задачу) в широковещательном режиме.
Упомянутый запрос содержит только информацию, которая описывает, какая задача должна быть получена, без необходимости знать, какой агент ответит на запрос:
информация, предоставляемая клиентом, определяет только получаемую задачу.
Как было описано выше в отношении фиг.2, агенты, которые удовлетворяют потребностям клиента и могут исполнить сервис, примут запрос и сообщат о своем приеме запроса на сервис через пакет "сердцебиения".
Вот таким образом реализована «запускающаяся» команда для рассматриваемого сервиса.
Поскольку протокол не предусматривает явную команду останова, клиент будет поддерживать пульсирующую передачу одного и того же запроса на сервис до тех пор, пока он в этом сервисе заинтересован.
Когда клиент хочет остановить сервис, он остановит пульсирующую передачу соответствующего запроса.
Агенты, анализирующие пакеты пульсирующей передачи, запишут время прибытия (временную метку) каждого принятого пакета и удалят все пакеты, имеющие временную метку (TimeStamp), которая не является достаточно недавней в соответствии с нижеследующей формулой:
если (t - TimeStamp)>TimeOut, то задача будет удалена,
где t представляет собой текущее время, и TimeOut ("тайм-аут") представляет собой некоторое предварительно заданное значение времени.
Следовательно, агент будет продолжать участвовать в сервисе в течение времени, по меньшей мере, равного TimeOut от последнего переданного пульсирующим образом запроса.
Этот процесс не дает никаким проблемам связи, которые могут вызвать потерю некоторых пакетов запроса, привести к прерыванию сервиса. Предпочтительно, чтобы значение TimeOut было обратно пропорционально частоте пульсации согласно нижеследующей формуле:
TimeOut=К / f,
где f представляет собой частоту пульсации.
Это подразумевает, что, когда передача данных происходит нормальным образом в течение интервала времени, равного TimeOut, на сервер должно прибыть количество (К) пакетов; сервис, следовательно, будет остановлен только в том случае, если ни один из упомянутых К пакетов не достигнет пункта назначения.
Чем выше значение К, тем менее вероятно, что из-за ошибок связи будет иметь место неудачный прием всех пакетов: следовательно, агент может сделать вывод, что это намеренный останов, команда на который отдана клиентом.
Отметим, что TimeOut прямо пропорционально К: из этого следует, что увеличенное значение К вызовет увеличение минимального времени, в течение которого агент остается в распоряжении клиента после последней пульсации, что не дает, таким образом, этому агенту выполнять другие задачи.
Следовательно, выбор К и, таким образом, TimeOut включает в себя компромисс между устойчивостью к ошибкам связи и временем освобождения ресурса.
Экспериментальные тесты показали, что К=3 является хорошим значением, которое особенно подходит для систем наблюдения.
Протокол для запросов на управление
В этом случае, протокол связи включает в себя нижеследующие этапы.
Станция контроля передает в пульсирующем режиме запрос для получения по сети прямого управления конкретным устройством.
Упомянутый запрос содержит только информацию, которая описывает датчик, подлежащий управлению, без необходимости знать, какой агент ответит на запрос: станция контроля должна только предоставить идентификатор датчика, такой как метка (например «ВИДЕОКАМЕРА 5»), введенная при настройке системы.
Запрос принимается всеми другими сетевыми агентами, которые исполняют вышеописанный алгоритм координации.
Следуя упомянутому алгоритму, только тот агент, который управляет датчиком, определяет способность участвовать в сервисе (этап 101, показанный на фиг.2) и сообщает о своем принятии запроса на сервис посредством пакета "сердцебиения" (этап 105).
Поскольку запрашиваемый сервис представляет собой управление данным датчиком, группа, участвующая в сервисе, состоит из единственного агента, чья единственная функция заключается в том, чтобы разблокировать (этапы 108 и 109, показанные на фиг.2) нормально заблокированный специализированный модуль связи для того, чтобы установить канал для поддержания связи со станцией контроля.
Анализируя пакеты "сердцебиения", принятые от каждого агента, станция контроля может определить, какой агент разблокирован и может извлечь информацию, которая полезна для установления двухточечного соединения с таким агентом. В этот момент протокол требует от станции контроля установить двухточечное соединение с выбранным агентом, которое примет по вновь установленному каналу связи управляющий сигнал.
Пока оператор управляет датчиком, агент будет продолжать получать из сети пакеты "сердцебиения"; когда клиент останавливает пульсирующую передачу запроса на управление, агент прекратит соединение с клиентом.
Протокол ответа на информационный запрос
В этом случае протокол связи включает в себя нижеследующие этапы. Клиент (то есть запрашивающий узел) осуществляет пульсирующую передачу информационного запроса по сети.
Упомянутый запрос содержит только указания на информацию о состоянии, которую желает получить клиент, без необходимости знать, какой агент будет отвечать на запрос.
Агенты оценивают то, могут ли они ответить на запрос ответа на информационный запрос, и сообщают по сети свои решения другим агентам.
Благодаря алгоритму избрания лидера определяется агент - лидер, который разблокирует нормально заблокированный специализированный модуль связи.
Анализируя принятые пакеты "сердцебиения", клиент может определить, какой агент разблокировал специализированный модуль связи и может извлечь информацию, которая полезна для установления двухточечного соединения с таким агентом. В этот момент протокол требует от клиента установить двухточечное соединение с выбранным агентом. По вновь установленному каналу связи будут направлены конкретные информационные запросы и связанные с ними ответы.
Когда клиент останавливает пульсирующую передачу информационного запроса, агент прекратит соединение с клиентом.
Радиально-узловая многоточечная передача данных
Этот тип передачи данных используется для того, чтобы передавать информацию от агента только одному или более предварительно заданным агентам или станциям контроля; в этом разделе адресаты такой информации будут именоваться клиентами.
Этот тип информации используется для отправки сигналов наподобие потока битов, который кодирует поток аудио-/видеоданных для того, чтобы он подходил для воспроизведения исходного сигнала.
В этом случае каждый сетевой агент действует в качестве аудио-/видеосервера, так что один или более клиентов могут установить соединение с агентом и запросить передачу упомянутого потока битов.
В этом случае протокол связи включает в себя нижеследующие этапы.
Клиент осуществляет пульсирующую передачу запроса на получение по сети аудио-/видеосигнала; упомянутый запрос содержит только информацию, которая описывает то, какой сигнал подлежит получению, без необходимости знать, какой агент будет отвечать на запрос.
Поскольку каждый агент соединен с областями контроля аудио- и/или видеодатчиками, информация, предоставляемая клиентом, представляет собой идентификатор датчика, с которым следует войти в контакт, или области, подлежащей контролю.
Запрос принимается всеми агентами, которые затем примут решение (в зависимости от характеристик соответствующих датчиков и на основе соответствующих планов приоритетов), участвовать ли в запрашиваемом сервисе или нет (этапы 101-104, показанные на фиг.2).
Те агенты, которые соответствуют потребностям клиента, ответят на этот запрос на сервис и сообщат о своем принятии этого запроса посредством пакета "сердцебиения" (этап 105, показанный на фиг.2).
Если запрос касается конкретного датчика, то сможет откликнуться только один агент; в ином случае, если запрос касается получения изображения данной области, то смогут откликнуться несколько датчиков, и для того, чтобы определить, какой датчик должен использоваться для наилучшего обслуживания оператора, следует исполнить алгоритм оптимального охвата (этап 108).
Агент, управляющий выбранным таким образом датчиком, затем разблокирует нормально заблокированный модуль связи, приспособленный к потоку битов аудио-/видеоданных.
Анализируя принятые пакеты "сердцебиения", клиент может определить, какой агент (какие агенты) разблокировали специализированный модуль передачи потока битов и может извлечь информацию, которая полезна для установления двухточечного соединения с такими серверами. В этот момент протокол требует от клиента установить двухточечное соединение с выбранными серверами, которые отправят по вновь установленному каналу связи поток битов аудио-/видеоданных.
Когда клиент прекращает пульсирующую передачу запроса на потоковую передачу данных, сервер остановит поток битов и прекратит соединение с клиентом.
Варианты
Согласно предпочтительному решению пульсирующая передача данных используется для широковещательной передачи информации узлам сети.
Однако это решение подразумевает значительную нагрузку на сеть как в том, что касается рабочей нагрузки, выпадающей на долю каждого узла (например, прием и анализа поступающих пакетов "сердцебиения"), так и в том, что касается сетевого трафика.
Эта проблема особенно чувствуется в случае, когда количество узлов (агентов и станций контроля) и запрашиваемых сервисов является очень большим.
В альтернативном варианте реализации изобретения агенты группируются на основе их характеристик близости или родственности для выполнения конкретного сервиса.
В этом варианте реализации изобретения агенты из группы отправляют свою информацию о состоянии только другим агентам, принадлежащим той же самой группе, используя, таким образом, многоадресную пульсирующую передачу данных или, выражаясь более обобщенно, радиально-узловую многоточечную передачу данных.
В этом случае пакет "сердцебиения" также содержит информацию об адресах целевых агентов.
Согласно этому варианту реализации изобретения агент может принадлежать нескольким смежным группам, что позволяет, таким образом, информации об обнаруженном событии распространяться от одной группы к другой: агент из группы, которая обнаружила событие, сообщит одну и ту же информацию всем группам, к которым он принадлежит, что позволяет, таким образом, агентам смежной группы приготовиться, например, контролировать область, смежную области, в которой было обнаружено событие.
Ясно, что можно также предусмотреть и другие варианты вышеописанной системы наблюдения и способа взаимодействия между агентами.
Например, процесс формирования группы (первый этап вышеописанной стратегии, относящейся к примеру предпочтительного варианта реализации изобретения) может быть также основанным на взаимодействии, вместо того, чтобы выполняться независимо каждым агентом, так что каждый компьютер знает, какие другие компьютеры также выполняют определенный сервис.
В этом варианте реализации изобретения каждый компьютер (благодаря соответствующему агенту) оценивает набор запросов на сервис, полученных по сети, и выбирает тот сервис, в котором он может принять участие. Вслед за этим, каждый компьютер информирует другие компьютеры о сервисах, в которых он будет участвовать, и принимает по сети список сервисов, которые могут исполняться каждым компьютером.
В этот момент каждый компьютер имеет полный список сервисов, которые способны исполняться каждым сетевым компьютером, и исполняет алгоритм назначения сервиса, который выдает в качестве результата те сервисы, в которых должен участвовать каждый агент.
Поскольку каждый агент исполняет один и тот же алгоритм, то все агенты различных компьютеров придут к одним и тем же заключениям в отношении сервисов, подлежащих исполнению каждым из них; затем будет выполнен второй этап стратегии, на котором исполняется алгоритм конфигурирования, который описан выше со ссылкой на фиг.2.
Согласно изобретению предпочтительно задачу совместного выбора сервисов решать как своего рода задачу оптимального охвата (смотри алгоритм, описанный ниже), цель которого заключается в том, чтобы вместо того, чтобы определять оптимальные положения датчиков для охвата данной области окружающей среды, определить, какой сервис (какие сервисы) должен (должны) быть выбраны каждым агентом для того, чтобы обеспечить наилучший охват для набора сервисов.
Алгоритм назначения сервиса будет, таким образом, своего рода алгоритмом для оптимального охвата, входными данными которого является набор запрашиваемых сервисов (вместо области, подлежащей контролю) и набора датчиков.
Для завершения аналогии с алгоритмом для оптимального охвата отметим, что вероятность обнаружения события посредством датчика в некоторой данной области соответствует вероятности (равной 1 или 0) того, что датчик выполнит заданную задачу.
На основе этой информации алгоритм будет, таким образом, оптимизировать вероятность выполнения набора задач с использованием готовых к работе датчиков.
Примеры алгоритмов конфигурирования
Избрание лидера
В алгоритме «избрания лидера» агенты выбирают представителя (лидера) для ответа на информационные запросы оператора, то есть запросы на получение информации, содержащейся в банке данных сети,
Избрание агента-лидера основано на критерии минимальной загрузки центрального процессора и приводит к однозначному выбору.
Алгоритм «избрания лидера» использует в качестве входных данных информацию о загрузке центрального процессора агентов, участвующих в избрании лидера (которым по большому счету могут быть все сетевые агенты); эту информацию делают доступной в сети посредством пакетов "сердцебиения", отправляемых по сети в конце первого этапа вышеописанного алгоритма координации (формирование группы).
После этого алгоритм проводит сравнение загрузки центральных процессоров всех компьютеров, участвующих в избрании лидера, и выбирает в качестве лидера тот компьютер, который имеет самую низкую загрузку центрального процессора.
Если имеется несколько компьютеров, имеющих одну и ту же самую низкую загрузку центрального процессора, то алгоритм выберет в качестве лидера компьютер с самым низким значением идентификатора: это означает, что при наличии двух компьютеров (А 1) и (А 2), имеющих одну и ту же загрузку центрального процессора, алгоритм выберет в качестве лидера компьютер (А 1).
Предпочтительно, чтобы алгоритм также сравнивал самую низкую загрузку центрального процессора с загрузкой центрального процессора компьютера, который был лидером перед исполнением алгоритма, и выбирал компьютер, имеющий самую низкую загрузку, только если эта самая низкая загрузка центрального процессора ниже, чем загрузка предыдущего лидера на предварительно заданную пороговую величину.
В идеальном случае, при котором все компьютеры принимают одну и ту же информацию и исполняют алгоритм одновременно, выходные данные всех компьютеров будут идентичны.
Однако на практике информация о состоянии сети распространяется асинхронно, и алгоритм исполняется агентами независимо, то есть в разные моменты времени; это может потенциально привести различных агентов к различным заключениям.
Для того чтобы сделать алгоритм устойчивым, предпочтительно, чтобы входные данные были предварительно обработаны посредством нахождения скользящего среднего значения по интервалу времени:
τ=k/f,
где k представляет собой некоторое целое число, a f представляет собой частоту, с которой каждый агент исполняет алгоритм избрания лидера.
Экспериментальное моделирование показало, что оптимальный диапазон, обеспечивающий надлежащее функционирование алгоритма составляет 5<k<10.
Алгоритмы охвата
Алгоритмы охвата, описанные ниже, требуют, чтобы контролируемая окружающая среда была подразделена на смежные ячейки, связанные с датчиками (и, следовательно, с агентами, ими управляющими), которые позволяют контролировать упомянутые ячейки.
Основанная на ячейках модель окружающей среды сохраняется в каждом компьютере и каждой станции контроля в конце стадии установки системы.
Ниже описан пример настройки системы, хотя также возможны несколько других решений по конфигурированию системы наблюдения.
Настройка системы
Согласно изобретению во время стадии настройки системы наблюдения создается модель окружающей среды путем определения представляющих интерес областей (С 1)-(С 4) этой окружающей среды и их смежности.
В нижеследующем описании области упомянутой модели будут именоваться «ячейками» для того, чтобы избежать какой-либо путаницы с физическими областями окружающей среды.
Вслед за этим каждая ячейка (С 1)-(С 4) ассоциативно связывается с одним или более датчиками, способными контролировать, по меньшей мере, участок области, соответствующей этой ячейке.
В частности, поскольку видеокамеры PTZ могут принимать множество положений, то каждая ячейка ассоциативно связывается не только с видеокамерой, но с видеокамерой в некотором данном положении (именуемом «предварительно настроенный»).
Конечно, для неподвижных видеокамер или датчиков имеется только одно предварительно определенное положение, которое задается при установке датчика.
Во время стадии настройки датчики последовательно активируются.
Для каждой подвижной видеокамеры или датчика оператор определяет предварительно настраиваемые положения подвижного датчика, которые наилучшим образом удовлетворяют потребностям оператора при наблюдении.
Для каждого предварительно настроенного положения оператор ассоциативно связывает посредством средства выбора датчик с областью окружающей среды и присваивает оценки контроля (например, выраженные как значение между 0 и 1), представляющие качество полученного изображения.
Оценки контроля соответствуют оценке вероятности обнаружения, посредством упомянутого датчика, события, происходящего в пределах ячейки, с которой этот датчик был ассоциативно связан в определенном предварительно настроенном положении.
На рабочей стадии это позволяет управлять датчиками, помещая их в эти предварительно настроенные положения, что максимизирует возможность контроля окружающей среды.
Примеры, показанные на фигурах 3а-3с и 4а-4b, иллюстрируют две различные модели окружающей среды, которые используются пользовательским интерфейсом для показа окружающей среды, подлежащей контролю, установщику оборудования и для того, чтобы позволить ему выбрать область.
Согласно примеру, показанному на фигурах 3а, 3b и 3с, программа, обеспечивающая пользовательский интерфейс, позволяет определять список ячеек и их соединений посредством графического интерфейса, который позволяет построить граф, в котором ячейки представлены как узлы, соединенные дугами.
Предпочтительно, чтобы пространственное расположение узлов было свободным, так чтобы во время стадии настройки оператор мог располагать их таким образом, чтобы отразить географическое расположение областей, подлежащих контролю, что позволяет наблюдателю немедленно находить область, подлежащую контролю, во время рабочей стадии.
Согласно альтернативному решению, которое является менее сложным с вычислительной точки зрения, но немного менее удобным для пользователя, определение областей и их соединений может быть выполнено в текстовом режиме.
Вновь обратимся к примеру, показанному на фигурах 3а-3с, согласно которому на стадии настройки оператор создает модель окружающей среды и затем последовательно активирует датчики (например, циклы видеокамер). Для каждого датчика оператор проверяет контролируемую область (например, он видит изображение, полученное видеокамерой, на экране) и создает соединение с областями модели, присваивая при этом оценки контроля.
Соединение датчика/области может быть выполнено вычерчиванием связи между значком, представляющим датчик, и блоком, представляющим заключенную в рамку область.
Таким образом, создается граф "ячейки/датчики", аналогичный графу, показанному на фиг.3с.
Предварительную настройку датчика и оценку контроля программное обеспечение сохраняет в базе данных системы управления.
В примере, показанном на фиг.4а-4b, модель окружающей среды состоит из карты (схемы) области, подлежащей контролю.
Карта, показанная на фиг.4а, может быть построена оператором электронным образом с использованием обычных графических программ, или она может представлять собой импортированный графический файл.
В решении, показанном на фиг.4а-4b, во время стадии настройки оператор выбирает датчик и, для каждого предварительно настроенного положения, отмечает контролируемую область на карте, как это показано на фиг.4b, и ассоциативно связывает с ней оценку контроля, например, печатая значение на клавиатуре (34) или выбирая с помощью мыши (35) отображаемое значение.
Когда выбрана совокупность пикселей, соответствующая области, контролируемой датчиком, программное обеспечение автоматически создаст ячейки модели и соответствующие смежности.
В варианте реализации изобретения каждый выбор пикселей соответствует одной ячейке модели.
Соседние совокупности пикселей представляют собой смежные ячейки.
В предпочтительном варианте реализации изобретения совокупности пикселей, перекрывающие друг друга в достаточной мере, группируются в единственную ячейку.
Критерий, используемый для принятия решения о том, должны ли две совокупности пикселей быть сгруппированы в единственную ячейку или нет, определяется во время стадии программирования: если две совокупности пикселей только соприкасаются, то, на самом деле, может быть предпочтительным сохранить эти две ячейки раздельными.
Геометрическая информация, связанная с каждой ячейкой, (площадь, форма) и информация о направлении перехода между ячейками извлекается автоматически.
В карту могут быть включены барьеры, которые будут учтены при расчете смежностей; например, два несообщающихся между собой помещения не являются смежными друг другу.
После того как модель построена, пользователем может быть добавлена и другая информация (метки ячеек, подвижность области, зависящие от времени барьеры, ориентация дуг и т.д.).
Когда настройка закончена, система управления вычертит граф "ячейки / датчики", аналогичный графу, показанному на фиг.3с.
Эвристика для охвата
Первый пример алгоритма охвата использует эвристики, которые позволяют определять оптимальную конфигурацию датчиков при ограниченном вычислительном усилии.
Сначала эвристика выбирает тот датчик, который имеет самое низкое количество степеней свободы (самое низкое количество возможных положений); если количество степеней свободы будет равным, то будет выбран датчик, имеющий самое низкое значение идентификатора.
Среди возможных положений этого датчика эвристика выбирает положение, имеющее наилучший обзор; если обзор будет одинаковым, то выбранное положение будет таким, при котором видна ячейка, имеющая самое низкое значение идентификатора, например ячейка (С 1) будет иметь предпочтение по отношению к (С 2).
После того как первый датчик в соответствующем положении был выбран, будут повторно рассчитаны степени свободы невыбранных датчиков без учета уже назначенных ячеек.
Предыдущие этапы будут повторяться до тех пор, пока все датчики не будут назначены на соответствующие ячейки.
Алгоритм для оптимального охвата
Алгоритм для оптимального охвата получает в качестве входных данных представляющую интерес область (получаемую из запроса на сервис) и набор датчиков (получаемый из пактов "сердцебиения"), а выдает оптимальную конфигурацию датчиков для охвата этой представляющей интерес области.
Это выливается в максимизацию вероятности обнаружения аномального события, происходящего в пределах данной представляющей интерес области.
В частности, предположим, что представляющая интерес область является набором, состоящим из N ячеек модели окружающей среды, построенной во время стадии настройки.
i
C обозначает аномальное событие, происходящее в ячейке i.
j
Система наблюдения содержит M датчиков, при этом x обозначает положение
датчика j.
В частности для датчиков PTZ (с возможностью поворота/наклона/ трансфокации) положение может принимать значения в пределах конечного дискретного набора значений, именуемых предварительными настройками.
Неподвижный датчик можно рассматривать как особенный датчик PTZ лишь с одной предварительной настройкой.
В общем случае положение датчика может принимать значения в пределах непрерывной области значений и может содержать географические координаты для датчиков, расположенных на подвижных средствах (патрульных автомашинах, роботах, и т.д.).
Для обнаружения события, обозначенного D, выражение
<mrow><mi>p</mi><mo stretchy="false">(</mo><mi>D</mi><mrow><mo>|</mo><mrow><msub><mi>C</mi><mn>1</mn></msub><mo>∪</mo><msub><mi>C</mi><mn>2</mn></msub><mo>∪</mo><mo>…</mo><mo>∪</mo><msub><mi>C</mi><mi>N</mi></msub><mo>,</mo><msub><mi>x</mi><mn>1</mn></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>x</mi><mi>M</mi></msub></mrow></mrow><mo stretchy="false">)</mo><mtext> </mtext><mtext> </mtext><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow>
j
указывает вероятность обнаружения аномального события при том условии, что это событие происходит только в одной из N ячеек, ассоциативно связанных с участком окружающей среды, подлежащим контролю, и что M датчиков имеют определенную предварительную настройку x.
Задача оптимального охвата данной области, следовательно, выливается в обнаружение оптимальной конфигурации датчиков, которая максимизирует упомянутую вероятность. Упомянутая конфигурация может быть выражена следующим образом:
<mrow><msub><mover accent="true"><mi>x</mi><mo>^</mo></mover><mn>1</mn></msub><mo>,</mo><msub><mover accent="true"><mi>x</mi><mo>^</mo></mover><mn>2</mn></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mover accent="true"><mi>x</mi><mo>^</mo></mover><mi>M</mi></msub><mo>=</mo><munder><mrow><mi>arg</mi><mi>max</mi></mrow><mrow><msub><mi>x</mi><mo>,</mo></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>x</mi><mi>M</mi></msub></mrow></munder><mi>p</mi><mo stretchy="false">(</mo><mi>D</mi><mrow><mo>|</mo><mrow><msub><mi>C</mi><mn>1</mn></msub><mo>∪</mo><msub><mi>C</mi><mn>2</mn></msub></mrow></mrow><mo>∪</mo><mo>…</mo><mo>∪</mo><msub><mi>C</mi><mi>N</mi></msub><mo>,</mo><msub><mi>x</mi><mn>1</mn></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>x</mi><mi>M</mi></msub><mo stretchy="false">)</mo><mtext> </mtext><mtext> </mtext><mo stretchy="false">(</mo><mn>2</mn><mo stretchy="false">)</mo></mrow>
Вероятность обнаружения может быть выражена следующим образом:
<mrow><mi>p</mi><mo stretchy="false">(</mo><mi>D</mi><mrow><mo>|</mo><mrow><msub><mi>C</mi><mn>1</mn></msub><mo>∪</mo><msub><mi>C</mi><mn>2</mn></msub><mo>∪</mo><mo>…</mo><mo>∪</mo><msub><mi>C</mi><mi>N</mi></msub><mo>,</mo><msub><mi>x</mi><mn>1</mn></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>x</mi><mi>M</mi></msub></mrow></mrow><mo stretchy="false">)</mo><mo>=</mo><mfrac><mrow><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover><mrow><mi>p</mi><mo stretchy="false">(</mo><mi>D</mi><mrow><mo>|</mo><mrow><msub><mi>C</mi><mi>i</mi></msub><mo>,</mo><msub><mi>x</mi><mn>1</mn></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>x</mi><mi>M</mi></msub></mrow></mrow><mo stretchy="false">)</mo><mo>⋅</mo><mi>p</mi><mo stretchy="false">(</mo><msub><mi>C</mi><mi>i</mi></msub><mo stretchy="false">)</mo></mrow></mstyle></mrow><mrow><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover><mrow><mi>p</mi><mo stretchy="false">(</mo><msub><mi>C</mi><mi>i</mi></msub><mo stretchy="false">)</mo></mrow></mstyle></mrow></mfrac><mtext> </mtext><mtext> </mtext><mo stretchy="false">(</mo><mn>3</mn><mo stretchy="false">)</mo></mrow>
i
1
M
i
Вышеприведенное выражение получено с использованием того непосредственного наблюдения, что наличие события в ячейке i не зависит от положения М датчиков, то есть, р(C|х,…x)=р(C).
i
Вероятность p(C) того, что событие происходит в данной ячейке i, может быть пропорциональна размеру соответствующей области и важности, которая характеризует ячейку с точки зрения наблюдения.
Для простоты, ниже будет принято, что все области модели имеют одинаковые вероятности; таким образом, выражение вероятности обнаружения примет вид:
<mrow><mi>p</mi><mo stretchy="false">(</mo><mi>D</mi><mrow><mo>|</mo><mrow><msub><mi>C</mi><mn>1</mn></msub><mo>∪</mo><msub><mi>C</mi><mn>2</mn></msub><mo>∪</mo><mo>…</mo><mo>∪</mo><msub><mi>C</mi><mi>N</mi></msub><mo>,</mo><msub><mi>x</mi><mn>1</mn></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>x</mi><mi>M</mi></msub></mrow></mrow><mo stretchy="false">)</mo><mo>=</mo><mfrac><mrow><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover><mrow><mi>p</mi><mo stretchy="false">(</mo><mi>D</mi><mrow><mo>|</mo><mrow><msub><mi>C</mi><mi>i</mi></msub><mo>,</mo><msub><mi>x</mi><mn>1</mn></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>x</mi><mi>M</mi></msub></mrow></mrow><mo stretchy="false">)</mo></mrow></mstyle></mrow><mi>N</mi></mfrac><mtext> </mtext><mtext> </mtext><mo stretchy="false">(</mo><mn>4</mn><mo stretchy="false">)</mo></mrow>
i
1
M
j
где p(D|C, x,…x) представляет собой вероятность обнаружения события, причем последнее происходит в ячейке i, а датчики имеют некоторую предварительную настройку x.
Теперь рассмотрим случай, при котором за данной ячейкой наблюдает один датчик системы наблюдения, например датчик (1).
i
1
M
i
1
Таким образом, получается, что p(D|C, x,…x)=p(D|C, x), то есть обнаружение в ячейке i не зависит от положения тех датчиков, которые не контролируют ячейку i.
i
M
1
Принимается, что p(D|C, x) представляет собой оценку контроля, присвоенную установщиком оборудования, при настройке системы наблюдения. Если описать это более подробно, то упомянутая оценка контроля представляет собой оценку, которая была присвоена датчику (1) в положении x, когда он был ассоциативно связан с ячейкой i.
1
Вполне разумно предположить, что если оценка контроля является высокой, то вероятность обнаружения события в данной области модели также будет высокой. Наоборот, если бы оценка составляла ноль, то было бы невозможным (нулевая вероятность) добиться обнаружения в данной ячейке посредством датчика (1) с предварительной настройкой x.
Теперь рассмотрим случай, при котором за ячейкой i наблюдают множественные датчики с соответствующей предварительной настройкой.
В целях помощи установщику оборудования вышеописанная процедура настройки не предусматривает сводную информацию контроля.
По этой причине в отсутствие такой информации будет учтен самый плохой случай: определяется датчик, имеющий самый хороший обзор, и предполагается, что другие датчики не могут добавить никакой информации, которая может улучшить обзор данной области модели. Таким образом, получают:
<mrow><mi>p</mi><mo stretchy="false">(</mo><mi>D</mi><mrow><mo>|</mo><mrow><msub><mi>C</mi><mi>i</mi></msub><mo>,</mo><msub><mi>x</mi><mn>1</mn></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>x</mi><mi>M</mi></msub></mrow></mrow><mo stretchy="false">)</mo><mo>=</mo><munder><mrow><mi>max</mi></mrow><mrow><mi>j</mi><mo>=</mo><mn>1,</mn><mo>…</mo><mo>,</mo><mi>M</mi></mrow></munder><mi>p</mi><mo stretchy="false">(</mo><mi>D</mi><mrow><mo>|</mo><mrow><msub><mi>C</mi><mi>i</mi></msub><mo>,</mo><msub><mi>x</mi><mi>j</mi></msub></mrow></mrow><mo stretchy="false">)</mo><mtext> </mtext><mtext> </mtext><mo stretchy="false">(</mo><mn>5</mn><mo stretchy="false">)</mo></mrow>
1
2
i
Теперь рассмотрим следующий пример. Два датчика (s 1) и (s 2), располагающиеся в х и х, наблюдают данную ячейку C оценками обзора, составляющими 0,8 и 0,6, соответственно.
Предполагается, что другие датчики не видят данную ячейку ни при какой предварительной настройке, или что они имеют предварительные настройки, при которых они не могут видеть данную ячейку.
i
1
i
2
i
j
i
1
2
M
Таким образом, получается что p(D|C, x)=0.8, p(D|C, x=0.6, p(D|C, x)=0 j>2, и что из предшествующего выражения, p(D|C, x, x,…,x)=0.8.
При преобразовании (4) на основе этого предположения будет, таким образом, получено:
<mrow><mi>p</mi><mo stretchy="false">(</mo><mi>D</mi><mrow><mo>|</mo><mrow><msub><mi>C</mi><mn>1</mn></msub><mo>∪</mo><msub><mi>C</mi><mn>2</mn></msub><mo>∪</mo><mo>…</mo><mo>∪</mo><msub><mi>C</mi><mi>N</mi></msub><mo>,</mo><msub><mi>x</mi><mn>1</mn></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>x</mi><mi>M</mi></msub></mrow></mrow><mo stretchy="false">)</mo><mo>=</mo><mfrac><mrow><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover><mrow><munder><mrow><mi>max</mi></mrow><mrow><mi>j</mi><mo>=</mo><mn>1,</mn><mo>…</mo><mo>,</mo><mi>M</mi></mrow></munder><mi>p</mi><mo stretchy="false">(</mo><mi>D</mi><mrow><mo>|</mo><mrow><msub><mi>C</mi><mi>i</mi></msub><mo>,</mo><msub><mi>x</mi><mi>j</mi></msub></mrow></mrow><mo stretchy="false">)</mo></mrow></mstyle></mrow><mi>N</mi></mfrac><mtext> </mtext><mtext> </mtext><mo stretchy="false">(</mo><mn>6</mn><mo stretchy="false">)</mo></mrow>
i
j
j
i
где p(D|C, x) представляет собой оценку контроля, с которой датчик j при предварительной настройке x контролирует ячейку C. Вышеупомянутое выражение строгим образом количественно определяет качество охвата данной области, позволяя, таким образом, сравнивать различные конфигурации датчиков, используемых для этой цели.
<mrow><msub><mover accent="true"><mi>x</mi><mo>^</mo></mover><mn>1</mn></msub></mrow>
<mrow><msub><mover accent="true"><mi>x</mi><mo>^</mo></mover><mn>2</mn></msub></mrow>
<mrow><msub><mover accent="true"><mi>x</mi><mo>^</mo></mover><mi>M</mi></msub></mrow>
Оптимальную конфигурацию
,
,…,
можно искать среди всех возможных конфигураций таким образом, как это разъясняется ниже.
Алгоритм, который позволяет найти оптимальную конфигурацию, начинается с информации, содержащейся в графе "ячейки/датчики" (фиг.2с), построенном при настройке системы наблюдения.
Для каждой ячейки имеется одна или более дуг, которые связывают ячейку с датчиками, которые ее контролируют.
Для каждой дуги имеется порция информации, указывающая предварительную настройку датчика. Принимая во внимание все ячейки области, подлежащей охвату, можно построить набор датчиков, используемых для получения упомянутого охвата, с соответствующей предварительной настройкой.
<mrow><msub><mover accent="true"><mi>x</mi><mo>^</mo></mover><mn>1</mn></msub></mrow>
<mrow><msub><mover accent="true"><mi>x</mi><mo>^</mo></mover><mn>2</mn></msub></mrow>
<mrow><msub><mover accent="true"><mi>x</mi><mo>^</mo></mover><mi>M</mi></msub></mrow>
Оптимальной конфигурацией
,
,…,
датчиков является конфигурация, которая максимизирует вероятность обнаружения; следовательно, в предпочтительном решении алгоритм продолжается вычислением (6) для каждой комбинации датчиков и затем выбирает комбинацию датчиков, имеющую самую высокую вероятность обнаружения.
1
2
3
1
2
3
<mrow><msubsup><mi>x</mi><mn>1</mn><mn>1</mn></msubsup></mrow>
<mrow><msubsup><mi>x</mi><mn>2</mn><mn>1</mn></msubsup></mrow>
<mrow><msubsup><mi>x</mi><mn>2</mn><mn>2</mn></msubsup></mrow>
<mrow><msubsup><mi>x</mi><mn>2</mn><mn>2</mn></msubsup></mrow>
Это станет понятно из нижеследующего примера: даны три ячейки C, C, C; ячейка C видна датчику (1) при предварительной настройке
, ячейка C видна датчику (2) при предварительной настройке
и при предварительной настройке
, и ячейка Cвидна датчику (2) при предварительной настройке
.
<mrow><msubsup><mi>x</mi><mn>1</mn><mn>1</mn></msubsup></mrow>
<mrow><msubsup><mi>x</mi><mn>2</mn><mn>1</mn></msubsup></mrow>
<mrow><msubsup><mi>x</mi><mn>1</mn><mn>1</mn></msubsup></mrow>
<mrow><msubsup><mi>x</mi><mn>2</mn><mn>2</mn></msubsup></mrow>
Диапазон возможных конфигураций состоит из пар (
,
) и (
,
).
<mrow><msubsup><mi>x</mi><mn>1</mn><mn>1</mn></msubsup></mrow>
<mrow><msubsup><mi>x</mi><mn>2</mn><mn>1</mn></msubsup></mrow>
<mrow><msubsup><mi>x</mi><mn>2</mn><mn>2</mn></msubsup></mrow>
Конечно же, конфигурация наподобие (
,
,
) не допустима, потому что в любой момент времени некоторый данный датчик может находиться только в одном положении.
После того как были определены две возможных конфигурации, алгоритм рассчитывает вероятности обнаружения, соответствующие упомянутым двум конфигурациям.
<mrow><msubsup><mi>x</mi><mn>2</mn><mn>2</mn></msubsup></mrow>
Предположим теперь, что все оценки контроля равны 1, за исключением оценки для предварительной настройки
, которая составляет 0,8 (при этой предварительной настройке видны 2 ячейки, но с более низким качеством).
<mrow><msubsup><mi>x</mi><mn>1</mn><mn>1</mn></msubsup></mrow>
<mrow><msubsup><mi>x</mi><mn>2</mn><mn>1</mn></msubsup></mrow>
<mrow><mi>p</mi><mo stretchy="false">(</mo><mi>D</mi><mrow><mo>|</mo><mrow><msub><mi>C</mi><mn>1</mn></msub><mo>∪</mo><msub><mi>C</mi><mn>2</mn></msub><mo>∪</mo><msub><mi>C</mi><mn>3</mn></msub><mo>,</mo><msubsup><mi>x</mi><mn>1</mn><mn>1</mn></msubsup><mo>,</mo><msubsup><mi>x</mi><mn>2</mn><mn>1</mn></msubsup></mrow></mrow><mo stretchy="false">)</mo><mo>=</mo><mfrac><mn>2</mn><mn>3</mn></mfrac></mrow>
В этих условиях первая конфигурация (
,
) имеет вероятность обнаружения аномального события, происходящего в пределах этой окружающей среды, которая равна
<mrow><msubsup><mi>x</mi><mn>1</mn><mn>1</mn></msubsup></mrow>
<mrow><msubsup><mi>x</mi><mn>2</mn><mn>1</mn></msubsup></mrow>
<mrow><mi>p</mi><mo stretchy="false">(</mo><mi>D</mi><mrow><mo>|</mo><mrow><msub><mi>C</mi><mn>1</mn></msub><mo>∪</mo><msub><mi>C</mi><mn>2</mn></msub><mo>∪</mo><msub><mi>C</mi><mn>3</mn></msub><mo>,</mo><msubsup><mi>x</mi><mn>1</mn><mn>1</mn></msubsup><mo>,</mo><msubsup><mi>x</mi><mn>2</mn><mn>2</mn></msubsup></mrow></mrow><mo stretchy="false">)</mo><mo>=</mo><mfrac><mrow><mn>2.6</mn></mrow><mn>3</mn></mfrac></mrow>
Тогда как вторая конфигурация (
,
) имеет вероятность обнаружения аномального события, происходящего в пределах этой окружающей среды, которая равна
<mrow><msubsup><mi>x</mi><mn>1</mn><mn>1</mn></msubsup></mrow>
<mrow><msubsup><mi>x</mi><mn>2</mn><mn>1</mn></msubsup></mrow>
Алгоритм затем сравнивает эти две рассчитанные вероятности обнаружения и выбирает конфигурацию (
,
), то есть конфигурацию, которая максимизирует вероятность обнаружения события в данной области, которая в этом случае соответствует всей этой окружающей среде.
Из вышеприведенного описания очевидно, что, если количество возможных конфигураций является большим, то поиск оптимальной конфигурации может представлять собой тяжелую вычислительную задачу.
В таком случае могут быть применены способы исследования операций для того, чтобы получить субоптимальное решение.
Эти способы, хотя и основываются на оценках контроля и на графе "ячейки / датчики", минимизируют соответствующую функцию стоимости, получаемую из вероятности обнаружения.
В качестве альтернативы, вычислительная сложность может также быть уменьшена путем введения эвристических методик; например, можно принять решение устанавливать каждый датчик в положение, которое имеет самую высокую оценку контроля так, чтобы контролировать одну или более ячеек, которые видны только этому датчику.
Будучи установленными, эти эвристические методики являются независимыми от вычисления вероятности обнаружения, даже притом, что эта вероятность может при разработке алгоритма использоваться для сравнения эффективности различных эвристических методик: если предлагается несколько эвристических методик, то вычисление вероятности обнаружения позволит установить, какая конфигурация из числа тех, что предложены согласно эвристическим методикам, является наиболее подходящей для обнаружения событий.
Оптимальный охват с самым низким количеством датчиков
Задача оптимального охвата, обсуждаемая в предшествующем разделе, может быть дополнена ограничением, состоящем в необходимости использовать наименьшее возможное количество датчиков.
Алгоритм для вычисления оптимального охвата с самым низким количеством датчиков также основывается на предположении, что вероятность обнаружения события в ячейке не увеличивается с количеством датчиков, используемых для охвата этой ячейки. Таким образом, предполагается:
<mrow><mi>p</mi><mo stretchy="false">(</mo><mi>D</mi><mrow><mo>|</mo><mrow><msub><mi>C</mi><mi>i</mi></msub><mo>,</mo><msub><mi>x</mi><mn>1</mn></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>x</mi><mi>M</mi></msub></mrow></mrow><mo stretchy="false">)</mo><mo>=</mo><munder><mrow><mi>max</mi></mrow><mrow><mi>j</mi><mo>=</mo><mn>1,</mn><mo>…</mo><mo>,</mo><mi>M</mi></mrow></munder><mi>p</mi><mo stretchy="false">(</mo><mi>D</mi><mrow><mo>|</mo><mrow><msub><mi>C</mi><mi>i</mi></msub><mo>,</mo><msub><mi>x</mi><mi>j</mi></msub></mrow></mrow><mo stretchy="false">)</mo><mtext> </mtext><mtext> </mtext><mo stretchy="false">(</mo><mn>7</mn><mo stretchy="false">)</mo></mrow>
Следовательно, алгоритм рассматривает только датчик, имеющий самую высокую оценку контроля среди всех тех датчиков, которым видна та же самая ячейка.
Датчики, имеющие более низкую оценку, рассматриваются как избыточные. Хотя с практической точки зрения может быть полезно добавлять информацию от большего количества датчиков (например, добавлять кадры области) для того, чтобы до некоторой степени улучшить эффективность контроля, тем не менее, существуют ситуации, в которых важно, чтобы не принималась никакая избыточная информация: оператор, получающий избыточную информацию будет оценивать то, что происходит в контролируемой сцене более медленно и с большей трудностью.
Не менее важно и то, что использование минимального количества ресурсов в многопользовательской и многозадачной системе увеличит возможность одновременного обслуживания большего количества операторов и задач.
Оптимальное решение при наличии вышеупомянутого ограничения находят, рассматривая все возможные подмножества глобального множества датчиков, подлежащих использованию для оптимального охвата.
Для каждого подмножества оптимальную предварительно настраиваемую конфигурацию находят таким образом, как это описано в предшествующем разделе "Алгоритм для оптимального охвата".
Решение данной задачи представлено множеством минимальной мощности, имеющим самую высокую вероятность обнаружения.
Следует отметить, что нет необходимости принимать во внимание все возможные подмножества датчиков: когда вероятность обнаружения для оптимального решения, отыскиваемого в подмножествах датчиков, имеющих количество (N) элементов, равна оптимальной вероятности обнаружения, отыскиваемой в подмножествах, имеющих количество (N-1) элементов, то оптимальное решение будет представлять собой конфигурацию с N-1 датчиками.
Следовательно, предпочтительно, чтобы способ предусматривал поиск решения задачи оптимального охвата в подмножествах датчиков с увеличивающимся количеством элементов.
Оптимальный охват границ
Системы наблюдения обеспечивают функцию, именуемую "отслеживание объекта", то есть отслеживание движущегося объекта в пределах контролируемой окружающей среды.
Ячейка, занятая этим объектом, называется "активной ячейкой", в то время как смежные ячейки называются "пограничные ячейки".
Смежности между ячейками определены в графе "ячейки/датчики", построенном при настройке системы.
Для того чтобы не потерять объект, в то время как датчик спозиционирован на активную ячейку, другие датчики сконфигурированы таким образом, чтобы обеспечивать оптимальный охват пограничной области.
Цель алгоритма оптимального охвата границ заключается в том, чтобы максимизировать нижеследующую вероятность:
<mrow><mi>p</mi><mo stretchy="false">(</mo><mi>D</mi><mrow><mo>|</mo><mrow><msub><mover accent="true"><mi>C</mi><mo>¯</mo></mover><mi>k</mi></msub><mo>,</mo><msub><mi>C</mi><mn>1</mn></msub><mo>∪</mo><msub><mi>C</mi><mn>2</mn></msub><mo>∪</mo><mo>…</mo><mo>∪</mo><msub><mi>C</mi><mi>N</mi></msub><mo>,</mo><msub><mi>x</mi><mn>1</mn></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>x</mi><mi>M</mi></msub></mrow></mrow><mo stretchy="false">)</mo><mtext> </mtext><mtext> </mtext><mo stretchy="false">(</mo><mn>8</mn><mo stretchy="false">)</mo></mrow>
i
j
Упомянутая вероятность соответствует вероятности обнаружения события при условии, что событие исходит из ячейки k и происходит в одной из N ячеек C, пограничных по отношению к ячейке k, и что М датчиков находятся в определенных положениях x.
При условиях, подобных описанным для вычисления оптимального охвата, вероятность обнаружения определяется следующим соотношением:
<mrow><mi>p</mi><mo stretchy="false">(</mo><mi>D</mi><mrow><mo>|</mo><mrow><msub><mover accent="true"><mi>C</mi><mo>¯</mo></mover><mi>k</mi></msub><mo>,</mo><msub><mi>C</mi><mn>1</mn></msub><mo>∪</mo><msub><mi>C</mi><mn>2</mn></msub><mo>∪</mo><mo>…</mo><mo>∪</mo><msub><mi>C</mi><mi>N</mi></msub><mo>,</mo><msub><mi>x</mi><mn>1</mn></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>x</mi><mi>M</mi></msub></mrow></mrow><mo stretchy="false">)</mo><mo>=</mo><mfrac><mrow><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover><mrow><munder><mrow><mi>max</mi></mrow><mrow><mi>j</mi><mo>=</mo><mn>1,</mn><mo>…</mo><mo>,</mo><mi>M</mi></mrow></munder><mi>p</mi><mo stretchy="false">(</mo><mi>D</mi><mrow><mo>|</mo><mrow><msub><mi>C</mi><mi>i</mi></msub><mo>,</mo><msub><mi>x</mi><mi>j</mi></msub></mrow></mrow><mo stretchy="false">)</mo><mo>⋅</mo><mi>p</mi><mo stretchy="false">(</mo><msub><mi>C</mi><mi>i</mi></msub><mrow><mo>|</mo><mrow><msub><mover accent="true"><mi>C</mi><mo>¯</mo></mover><mi>k</mi></msub></mrow></mrow><mo stretchy="false">)</mo></mrow></mstyle></mrow><mrow><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover><mrow><mi>p</mi><mo stretchy="false">(</mo><msub><mi>C</mi><mi>i</mi></msub><mrow><mo>|</mo><mrow><msub><mover accent="true"><mi>C</mi><mo>¯</mo></mover><mi>k</mi></msub></mrow></mrow><mo stretchy="false">)</mo></mrow></mstyle></mrow></mfrac><mtext> </mtext><mtext> </mtext><mo stretchy="false">(</mo><mn>9</mn><mo stretchy="false">)</mo></mrow>
i
j
j
j
<mrow><mi>p</mi><mo stretchy="false">(</mo><msub><mi>C</mi><mi>i</mi></msub><mrow><mo>|</mo><mrow><msub><mover accent="true"><mi>C</mi><mo>¯</mo></mover><mi>k</mi></msub></mrow></mrow><mo stretchy="false">)</mo></mrow>
где p(D|C, x) представляет собой оценку контроля для датчика j с предварительной настройкой x, наблюдающего за ячейкой C, в то время как
представляет собой вероятность того, что объект движется из активной ячейки в предположительно существующую пограничную ячейку i.
Согласно предпочтительному варианту реализации изобретения, при создании модели окружающей среды во время стадии настройки необходимо определить вероятности перехода из одной ячейки в другую.
<mrow><mi>p</mi><mo stretchy="false">(</mo><msub><mi>C</mi><mi>i</mi></msub><mrow><mo>|</mo><mrow><msub><mover accent="true"><mi>C</mi><mo>¯</mo></mover><mi>k</mi></msub></mrow></mrow><mo stretchy="false">)</mo></mrow>
Эти вероятности соответствуют экземплярам
в вышеупомянутой формуле.
Если информация о вероятности перехода из одной ячейки в смежную ячейку не указана, как в примере варианта реализации изобретения, описанном со ссылкой на
<mrow><mi>p</mi><mo stretchy="false">(</mo><msub><mi>C</mi><mi>i</mi></msub><mrow><mo>|</mo><mrow><msub><mover accent="true"><mi>C</mi><mo>¯</mo></mover><mi>k</mi></msub></mrow></mrow><mo stretchy="false">)</mo></mrow>
Фигуры 2а-2с и 3а-3b, то все экземпляры
равны и соотношение для вычисления вероятности обнаружения события в пограничной ячейке будет определяться формулой:
<mrow><mi>p</mi><mo stretchy="false">(</mo><mi>D</mi><mrow><mo>|</mo><mrow><msub><mover accent="true"><mi>C</mi><mo>¯</mo></mover><mi>k</mi></msub><mo>,</mo><msub><mi>C</mi><mn>1</mn></msub><mo>∪</mo><msub><mi>C</mi><mn>2</mn></msub><mo>∪</mo><mo>…</mo><mo>∪</mo><msub><mi>C</mi><mi>N</mi></msub><mo>,</mo><msub><mi>x</mi><mn>1</mn></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>x</mi><mi>M</mi></msub></mrow></mrow><mo stretchy="false">)</mo><mo>=</mo><mfrac><mrow><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover><mrow><munder><mrow><mi>max</mi></mrow><mrow><mi>j</mi><mo>=</mo><mn>1,</mn><mo>…</mo><mo>,</mo><mi>M</mi></mrow></munder><mi>p</mi><mo stretchy="false">(</mo><mi>D</mi><mrow><mo>|</mo><mrow><msub><mi>C</mi><mi>i</mi></msub><mo>,</mo><msub><mi>x</mi><mi>j</mi></msub></mrow></mrow><mo stretchy="false">)</mo></mrow></mstyle></mrow><mi>N</mi></mfrac><mtext> </mtext><mtext> </mtext><mo stretchy="false">(</mo><mn>10</mn><mo stretchy="false">)</mo></mrow>
Оптимальный охват посредством кластеров агентов
Возможная стратегия для того, чтобы уменьшить вычислительную сложность алгоритма для оптимального охвата, предусматривает формирование совокупности агентов (кластера) и то, что каждый кластер решает задачу оптимального охвата независимо от всех других кластеров.
Следовательно, алгоритм оптимального охвата посредством кластеров агентов включает в себя первый этап, на котором агенты должны принять совместное решение о составе этих совокупностей.
В первом варианте реализации изобретения каждый агент определяет совокупность агентов своего кластера, выбирая предварительно заданное количество соседних агентов, термин "соседние агенты" относится к агентам, которые управляют датчиками, которые охватывают те же самые области окружающей среды, что охватываются датчиками под его собственным управлением.
Другими словами, два агента являются соседними агентами, если они имеют два соответствующих датчика, охватывающих одну и ту же область.
На основе этого принципа данный агент может сформировать кластер, выбирая своих соседей и затем соседей своих соседей, и так далее, вплоть до кластера с максимальным количеством элементов.
В качестве альтернативы, для того, чтобы сформировать кластеры, каждый агент выбирает соседних агентов, начиная с агента, имеющего самое низкое значение идентификатора (например, метки), и затем определяет, к какому кластеру он принадлежит.
В другом варианте реализации изобретения формирование кластеров агентов может быть выполнено на соответствующем взвешенном графе, в котором узлы являются агенты, а дуги связывают друг с другом агентов, которые имеют общие ячейки. Вес дуг указывает количество общих ячеек. Кластеры получаются путем использования "минимальных отрезаний", которые проходят по дугам с минимальным весом, для того, чтобы отделить агентов, «почти» не имеющих общих ячеек, друг от друга.
После того как определены агенты, принадлежащие кластеру, каждый агент применит вышеописанный алгоритм для оптимального охвата.
Этот подход в вычислительном отношении выгоден и устойчив.