Оптимальне розміщення багатосенсорної системи для виявлення загрози

Описано алгоритм детектування підводної загрози за допомогою системи акустичних сенсорів, а також екстремальні задачі розміщування сенсорів. Розглянуто методи розв’язання таких задач, доведено теорему про асимптотичну оптимальність побудованих планів розміщення сенсорів. З результатів числових експе...

Full description

Saved in:

Bibliographic Details
Published in:	Кибернетика и системный анализ
Date:	2018
Main Author:	Пашко, С.В.
Format:	Article
Language:	Ukrainian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2018
Subjects:	Системний аналіз
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/144854
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Оптимальне розміщення багатосенсорної системи для виявлення загрози / С.В. Пашко // Кибернетика и системный анализ. — 2018. — Т. 54, № 2. — С. 85–94. — Бібліогр.: 12 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-144854
record_format	dspace
spelling	Пашко, С.В. 2019-01-05T19:29:44Z 2019-01-05T19:29:44Z 2018 Оптимальне розміщення багатосенсорної системи для виявлення загрози / С.В. Пашко // Кибернетика и системный анализ. — 2018. — Т. 54, № 2. — С. 85–94. — Бібліогр.: 12 назв. — укр. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/144854 519.1 Описано алгоритм детектування підводної загрози за допомогою системи акустичних сенсорів, а також екстремальні задачі розміщування сенсорів. Розглянуто методи розв’язання таких задач, доведено теорему про асимптотичну оптимальність побудованих планів розміщення сенсорів. З результатів числових експериментів випливає, що побудований метод перевершує відомий метод розв’язання задач розміщування сенсорів. Описан алгоритм детектирования подводной угрозы с помощью системы акустических сенсоров, а также экстремальные задачи размещения сенсоров. Рассмотрены методы решения таких задач, доказана теорема об асимптотической оптимальности построенных планов размещения сенсоров. Из результатов численных экспериментов следует, что построенный метод превосходит известный метод решения задач размещения сенсоров. We consider the mathematical models for underwater acoustic sensors, the algorithm for threat detection by a multisensory system, and optimization problems for placement of such systems. The mathematical methods for optimal sensor placement is developed. The limit theorem on the optimality of sensor placement is proved. The numerical experiments demonstrate that the algorithm outperforms the available mathematical method for optimal sensor placement. uk Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системний аналіз Оптимальне розміщення багатосенсорної системи для виявлення загрози Оптимальное размещение многосенсорной системы для обнаружения угрозы Optimal placement of multisensor system for threat detection Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Оптимальне розміщення багатосенсорної системи для виявлення загрози
spellingShingle	Оптимальне розміщення багатосенсорної системи для виявлення загрози Пашко, С.В. Системний аналіз
title_short	Оптимальне розміщення багатосенсорної системи для виявлення загрози
title_full	Оптимальне розміщення багатосенсорної системи для виявлення загрози
title_fullStr	Оптимальне розміщення багатосенсорної системи для виявлення загрози
title_full_unstemmed	Оптимальне розміщення багатосенсорної системи для виявлення загрози
title_sort	оптимальне розміщення багатосенсорної системи для виявлення загрози
author	Пашко, С.В.
author_facet	Пашко, С.В.
topic	Системний аналіз
topic_facet	Системний аналіз
publishDate	2018
language	Ukrainian
container_title	Кибернетика и системный анализ
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
format	Article
title_alt	Оптимальное размещение многосенсорной системы для обнаружения угрозы Optimal placement of multisensor system for threat detection
description	Описано алгоритм детектування підводної загрози за допомогою системи акустичних сенсорів, а також екстремальні задачі розміщування сенсорів. Розглянуто методи розв’язання таких задач, доведено теорему про асимптотичну оптимальність побудованих планів розміщення сенсорів. З результатів числових експериментів випливає, що побудований метод перевершує відомий метод розв’язання задач розміщування сенсорів. Описан алгоритм детектирования подводной угрозы с помощью системы акустических сенсоров, а также экстремальные задачи размещения сенсоров. Рассмотрены методы решения таких задач, доказана теорема об асимптотической оптимальности построенных планов размещения сенсоров. Из результатов численных экспериментов следует, что построенный метод превосходит известный метод решения задач размещения сенсоров. We consider the mathematical models for underwater acoustic sensors, the algorithm for threat detection by a multisensory system, and optimization problems for placement of such systems. The mathematical methods for optimal sensor placement is developed. The limit theorem on the optimality of sensor placement is proved. The numerical experiments demonstrate that the algorithm outperforms the available mathematical method for optimal sensor placement.
issn	1019-5262
url	https://nasplib.isofts.kiev.ua/handle/123456789/144854
citation_txt	Оптимальне розміщення багатосенсорної системи для виявлення загрози / С.В. Пашко // Кибернетика и системный анализ. — 2018. — Т. 54, № 2. — С. 85–94. — Бібліогр.: 12 назв. — укр.
work_keys_str_mv	AT paškosv optimalʹnerozmíŝennâbagatosensornoísistemidlâviâvlennâzagrozi AT paškosv optimalʹnoerazmeŝeniemnogosensornoisistemydlâobnaruženiâugrozy AT paškosv optimalplacementofmultisensorsystemforthreatdetection
first_indexed	2025-11-26T01:42:57Z
last_indexed	2025-11-26T01:42:57Z
_version_	1850605578868490240
fulltext	ÓÄÊ 519.1 Ñ.Â. ÏÀØÊÎ ÎÏÒÈÌÀËÜÍÅ ÐÎÇÌ²ÙÅÍÍß ÁÀÃÀÒÎÑÅÍÑÎÐÍÎ¯ ÑÈÑÒÅÌÈ ÄËß ÂÈßÂËÅÍÍß ÇÀÃÐÎÇÈ Àíîòàö³ÿ. Îïèñàíî àëãîðèòì äåòåêòóâàííÿ ï³äâîäíî¿ çàãðîçè çà äîïîìîãîþ ñèñòåìè àêóñòè÷íèõ ñåíñîð³â, à òàêîæ åêñòðåìàëüí³ çàäà÷³ ðîçì³ùóâàííÿ ñåíñîð³â. Ðîçãëÿíóòî ìåòîäè ðîçâ’ÿçàííÿ òàêèõ çàäà÷, äîâåäåíî òåîðåìó ïðî àñèìïòîòè÷íó îïòèìàëüí³ñòü ïîáóäîâàíèõ ïëàí³â ðîçì³ùåííÿ ñåíñîð³â. Ç ðå- çóëüòàò³â ÷èñëîâèõ åêñïåðèìåíò³â âèïëèâàº, ùî ïîáóäîâàíèé ìåòîä ïåðå- âåðøóº â³äîìèé ìåòîä ðîçâ’ÿçàííÿ çàäà÷ ðîçì³ùóâàííÿ ñåíñîð³â. Êëþ÷îâ³ ñëîâà: ñåíñîð, áàãàòîñåíñîðíà ñèñòåìà, àëãîðèòì äåòåêòóâàííÿ çà- ãðîçè, îïòèìàëüíå ðîçì³ùåííÿ ñåíñîð³â, àñèìïòîòè÷íà îïòèìàëüí³ñòü. Ïðîáëåìà ðîçì³ùóâàííÿ àãåíò³â áàãàòîàãåíòíî¿ ñèñòåìè º âàæëèâîþ çàäà÷åþ, â³ä ÿêîñò³ ðîçâ’ÿçàííÿ ÿêî¿ çàëåæèòü óñï³øí³ñòü ä³é ö³º¿ ñèñòåìè. Ó ñòàòò³ ðîç- ãëÿíóòî ñèñòåìó àêóñòè÷íèõ ñåíñîð³â, ïðèçíà÷åíó äëÿ âèÿâëåííÿ ï³äâîäíî¿ çà- ãðîçè â äåÿê³é îáìåæåí³é àêâàòîð³¿, ïðèëåãë³é äî âàæëèâèõ íàðîäíîãîñïîäàð- ñüêèõ îá’ºêò³â. Îïèñàíî åêñòðåìàëüí³ çàäà÷³ òà ìåòîäè ¿õíüîãî ðîçâ’ÿçàííÿ äëÿ îïòèìàëüíîãî ðîçì³ùåííÿ ñåíñîð³â ó ìåæàõ çàäàíî¿ àêâàòîð³¿. Âî÷åâèäü, òàê³ çàäà÷³ º àêòóàëüíèìè ç îãëÿäó íà çðîñòàííÿ òåðîðèñòè÷íèõ çàãðîç. Ï³ä ÷àñ êîíñòðóþâàííÿ áàãàòîñåíñîðíèõ ñèñòåì âèíèêàþòü ð³çíîìàí³òí³ åêñòðåìàëüí³ çàäà÷³, ùî ðîçâ’ÿçóþòüñÿ çà äîïîìîãîþ â³äïîâ³äíèõ ìàòåìàòè÷íèõ ìåòîä³â. Â [1] çàäà÷ó ðîçì³ùóâàííÿ ï³äâîäíèõ àêóñòè÷íèõ ñåíñîð³â ñôîðìóëüî- âàíî ÿê çàäà÷ó ñòîõàñòè÷íîãî ïðîãðàìóâàííÿ, â ÿê³é øóì º âèïàäêîâîþ âåëè÷è- íîþ. Îïèñàíî àëãîðèòì îáðîáëåííÿ ñèãíàë³â òà òåñò äëÿ âèçíà÷åííÿ ê³ëüêîñò³ ïîðóøíèê³â-äàéâåð³â ³ç çàñòîñóâàííÿì òåîð³¿ ïðèõîâàíèõ ëàíöþã³â Ìàðêîâà. Ó [2] çàäà÷ó îïòèìàëüíîãî ðîçì³ùåííÿ ï³äâîäíèõ ñåíñîð³â ðîçâ’ÿçàíî çà äîïîìî- ãîþ ãåíåòè÷íîãî àëãîðèòìó. Âðàõîâàíî ð³çíîìàí³òí³ õàðàêòåðèñòèêè íàâêîëèø- íüîãî ñåðåäîâèùà: ãëèáèíó, òåìïåðàòóðó, ñîëîí³ñòü âîäè, pH. Ó ðîáîò³ [3] äëÿ ðîçì³ùóâàííÿ âóçë³â ñåíñîðíî¿ ìåðåæ³ íà ìîðñüêîìó äí³ âèêîðèñòàíî ñàìîîð- ãàí³çàö³éíó êàðòó Êîõîíåíà, ùî ÿâëÿº ñîáîþ íåéðîííó ìåðåæó ç íàâ÷àííÿì. Ïî- áóäîâàíèé íà îñíîâ³ ñàìîîðãàí³çàö³éíî¿ êàðòè ìåòîä äîçâîëÿº â³äñ³þâàòè íå- åôåêòèâí³ âóçëè ìåðåæ³. Â [4] äîñë³äæåíî çàäà÷ó ðîçì³ùóâàííÿ ñåíñîð³â, ó ÿê³é îïòèì³çóºòüñÿ ïîêðèòòÿ äåÿêî¿ îáëàñò³ òà çàïðîïîíîâàíî äâà æàä³áíèõ àëãîðèòìè äëÿ îïòèì³çàö³¿ ñåðåäíüîãî çíà÷åííÿ ïîêðèòòÿ àáî ïîêðèòòÿ ó íàéã³ðøîìó âèïàä- êó. Â [5] ðîçãëÿíóòî ÷àñ ðîáîòè ñåíñîðíî¿ ñèñòåìè, ùî çàëåæèòü â³ä åíåðãåòè÷- íèõ îáìåæåíü, çàïðîïîíîâàíî àëãîðèòì ðîçì³ùóâàííÿ ñåíñîð³â, ùî âðàõîâóº ìîæëèâèé ÷àñ ¿õíüî¿ ðîáîòè. Äëÿ ñèñòåìè ìîá³ëüíèõ ñåíñîð³â ó ðîáîòàõ [6, 7] ïî- áóäîâàíî àëãîðèòì ïîêðàùåííÿ ðîçì³ùåííÿ ñåíñîð³â ï³ñëÿ âèïàäêîâîãî ðîçì³ùóâàííÿ, ùî îïòèì³çóº ïîêðèòòÿ òåðèòîð³¿ ñåíñîðàìè çà óìîâ îáìåæåíîñò³ â³äñòàíåé, ÿê³ ìîæóòü áóòè íèìè ïðîéäåí³. Â [8] ñôîðìóëüîâàíî çàäà÷³ ðîçì³ùóâàííÿ ï³äâîäíèõ ñåíñîð³â, îáãîâîðåíî ìåòîäè ¿õíüîãî ðîçâ’ÿçàííÿ òà íà- âåäåíî ÷èñëåííèé ñïèñîê âèêîðèñòàíî¿ ë³òåðàòóðè. Ó ðîáîò³ [9] ðîçãëÿíóòî ñïîñîáè ðîçòàøóâàííÿ ñåíñîð³â, ùî º íàáëèæåíèìè äî ðåãóëÿðíîãî. Îáëàñòü ñïîñòåðåæåííÿ ðîçáèâàþòü íà ìíîæèíó ïðàâèëüíèõ ãå- îìåòðè÷íèõ ô³ãóð (ïðàâèëüíèõ òðèêóòíèê³â, êâàäðàò³â, øåñòèêóòíèê³â), ñåíñîðè ïåðåâàæíî ðîçì³ùóþòü ó âåðøèíàõ öèõ ô³ãóð. Ñåíñîðè ââàæàþòü îäíîòèïíèìè. Îñê³ëüêè îáëàñòü ñïîñòåðåæåííÿ º çàøóìëåíîþ, äëÿ íàä³éíîãî òåñòóâàííÿ ïîòð³áíà âåëèêà ù³ëüí³ñòü ñåíñîð³â. Äîâåäåíî òåîðåìó ïðî òå, ùî çà óìîâè ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 2 85 © Ñ.Â. Ïàøêî, 2018 çá³ëüøåííÿ ê³ëüêîñò³ ñåíñîð³â âêàçàíèé ñïîñ³á ðîçì³ùåííÿ íàáëèæóºòüñÿ äî îïòèìàëüíîãî. ×èñëîâ³ åêñïåðèìåíòè äåìîíñòðóþòü, ùî çàïðîïîíîâàíèé àëãî- ðèòì ðîçì³ùóâàííÿ ïåðåâåðøóº àëãîðèòì, ïîáóäîâàíèé â [4], íàâ³òü ÿêùî îïòè- ìàëüíà ê³ëüê³ñòü ñåíñîð³â â³äíîñíî ìàëà. Íà â³äì³íó â³ä ðîáîòè [9] äàë³ ðîçãëÿíó- òî ñåíñîðè ç ð³çíèìè ìîæëèâîñòÿìè. Â³äïîâ³äíî äî öüîãî ñôîðìóëüîâàíî åêñòðå- ìàëüí³ çàäà÷³ òà ïîáóäîâàíî ¿õí³ ðîçâ’ÿçêè. ÌÀÒÅÌÀÒÈ×Í² ÌÎÄÅË² ÑÅÍÑÎÐ²Â ² ÀËÃÎÐÈÒÌÈ ÄÅÒÅÊÒÓÂÀÍÍß ÇÀÃÐÎÇÈ Ïðèïóñòèìî, ùî îáëàñòü ñïîñòåðåæåííÿ W º ì³ëêîâîäíîþ (ó òàêîìó âèïàäêó ¿¿ ìîæíà ââàæàòè äâîâèì³ðíîþ) ³ ùî ³ñíóº ò³ëüêè îäíà ìîæëèâà çàãðîçà, òîáòî îäèí ïîðóøíèê. Ïîçíà÷èìî H 0 ã³ïîòåçó, ÿêà ñòâåðäæóº, ùî â îáëàñò³ W íåìàº ïîðóøíèêà. Íåõàé H1 — ã³ïîòåçà, ÿêà ñòâåðäæóº, ùî â îáëàñò³ W º îäèí ïîðóø- íèê. Ïîçíà÷èìî H Y1 ( ) ã³ïîòåçó ïðî òå, ùî ïîðóøíèê ïåðåáóâàº â òî÷ö³ Y W� . Ïðèïóñòèìî, ùî â îáëàñò³ W ðîçòàøîâàíî n ñåíñîð³â ó òî÷êàõ X X n1, ,� . Íåõàé S j — ä³éñíà âèïàäêîâà âåëè÷èíà, ùî º ðåçóëüòàòîì îáðîáëåííÿ ñèãíàëó ñåíñîðîì j, S S S n� ( , , )1 � — âèïàäêîâèé âåêòîð. Ïîçíà÷èìî s s sn� ( , , )1 � ñïîñòåðåæåííÿ âåêòîðà S ó äåÿêèé ìîìåíò ÷àñó. Ââàæàºìî, ùî ³ñíóº àãåíò, ÿêèé ïîñèëàº çàïèòè íà âñ³ ñåíñîðè, îòðèìóº â³ä íèõ ³íôîðìàö³þ ó âèãëÿä³ âåêòîðà s s sn� ( , , )1 � , íà îñíîâ³ ÿêî¿ ïðèéìàº ð³øåííÿ ïðî ñïðàâåäëèâ³ñòü ã³ïîòåçè H 0 àáî ã³ïîòåçè H Y1 ( ). Ïîçíà÷èìî PS j ( )� ðîçïîä³ë éìîâ³ðíîñòåé âåëè÷èíè S j ó âèïàäêó, ÿêùî S j º äèñêðåòíîþ âèïàäêîâîþ âåëè÷èíîþ. ßêùî S j íåïåðåðâíà, òî PS j ( )� — ù³ëüí³ñòü ðîçïîä³ëó éìîâ³ðíîñòåé äëÿ S j (ó òàêîìó âèïàäêó ââàæàºìî, ùî ù³ëüí³ñòü ðîçïîä³ëó ³ñíóº). Àíàëîã³÷íî ïîçíà÷èìî PS ( )� ðîçïîä³ë éìîâ³ðíîñòåé âèïàäêîâîãî âåêòîðà S . Äëÿ êîæíîãî çíà÷åííÿ s òà Y ðîçãëÿíåìî óìîâí³ éìîâ³ðíîñò³ (ù³ëüíîñò³) äëÿ êîæíî¿ ã³ïîòåçè P s HS ( \| )0 , P s H YS ( \| ( ))1 . Ââàæàþ÷è, ùî âèïàäêîâ³ âåëè÷èíè S j º íåçàëåæíèìè çà óìîâ H 0 àáî H Y1 ( ), îòðèìóºìî P s H P s HS j n S jj ( \| ) ( \| )0 1 0� � � , P s H Y P s H YS S j j n j ( \| ( )) ( \| ( ))1 1 1 � � � . Ìàòåìàòè÷íà ìîäåëü ñåíñîðà j ïîâí³ñòþ âèçíà÷àºòüñÿ ðîçïîä³ëàìè P s HS jj ( \| )0 , P s H YS jj ( \| ( ))1 , (1) ÿê³ çàëåæàòü â³ä ñòàòèñòè÷íèõ âëàñòèâîñòåé øóìó íàâêîëèøíüîãî ñåðåäîâèùà, ³íòåíñèâíîñò³ ñèãíàëó, òåõí³÷íèõ õàðàêòåðèñòèê ñåíñîðà, ìåòîäó îáðîáëåííÿ ñèãíàëó. Íåõàé X x yj j j� ( , ), Y x y� ( , ), d X Y x x y yj j j j� � � � � �\| \| \| \| ( ) ( )2 2 — â³äñòàíü ì³æ ö³ëëþ òà j-ì ñåíñîðîì. Ðîçãëÿíåìî äâ³ ìàòåìàòè÷í³ ìîäåë³ ñåíñîðà, ùî êîíêðåòèçóþòü ìîäåëü (1). Ñèìâîëîì P äàë³ ïîçíà÷àºìî éìîâ³ðí³ñòü. Ìîäåëü 1. Âèõ³äíèé ñèãíàë ñåíñîðà j — á³íàðíà âèïàäêîâà âåëè÷èíà S j �{ }0 1, . Âåëè÷èíà S j ìàòèìå çíà÷åííÿ 1, ÿêùî ñåíñîð äåòåêòóº çàãðîçó, òà 0 â ³íøîìó âèïàäêó. Éìîâ³ðíîñò³ äåòåêòóâàííÿ ïîðóøíèêà äëÿ ã³ïîòåç H H Y0 1, ( ) âèçíà÷àþòü ôîðìóëàìè P S H Y f dj j( \| ( )) ( )� �1 1 1 , P S Hj( \| )� �1 0 �, (2) äå f d j1 ( ) º ìîíîòîííî íåçðîñòàþ÷îþ ôóíêö³ºþ, 0 11� �� f d j( ) . Ìîäåëü 2. Âèõ³äíèé ñèãíàë ñåíñîðà j — íîðìàëüíî ðîçïîä³ëåíà âèïàäêîâà âåëè÷èíà, S f d H Y H j j� � � � 2 1 0 ( ) ( ), , � � çà óìîâè çà óìîâè (3) äå f d a b d d a b d a b j j j j j j j j j j 2 0 ( ) , / , , / , � � � � � (4) 86 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 2 a j � 0, b j � 0 — êîíñòàíòè, ùî çàëåæàòü â³ä òåõí³÷íèõ õàðàêòåðèñòèê ñåíñîðà, f d j2 ( ) — ñèãíàë â³ä ö³ë³, � — øóì, � � �~ ( , )N 2 . Ó ðîáîò³ [10] îïèñàíî çàêîíè ðîçïîâñþäæåííÿ ñèãíàë³â ó âîäíîìó ñåðåäî- âèù³ ç óðàõóâàííÿì øóì³â, íà îñíîâ³ ÿêèõ ïîáóäîâàíî íàâåäåí³ ìîäåë³. Îïèøåìî îäíîïåð³îäíèé àëãîðèòì äåòåêòóâàííÿ çàãðîçè, ùî âèêîðèñòîâóº ñèãíàëè ñåíñîð³â, îòðèìàí³ â äåÿêèé ìîìåíò ÷àñó t . Ïî÷íåìî ç ïðîñòîãî âèïàäêó, êîëè àáî ïîðóøíèêà íåìàº â îáëàñò³ W , àáî â³í ïåðåáóâàº â òî÷ö³ Y W� . Äëÿ âè- ÿâëåííÿ çàãðîçè çàñòîñóºìî òåñò Íåéìàíà–Ï³ðñîíà, ùî âèêîðèñòîâóº â³äíîøåííÿ ïðàâäîïîä³áíîñò³ R s Y P s H Y P s H S S ( , ) ( \| ( )) ( \| ) � 1 0 . Ïðèéìàþòü ã³ïîòåçó H Y1 ( ), ÿêùî R s Y Y( , ) ( ) � äëÿ äåÿêîãî çíà÷åííÿ � ( )Y , ³ ã³ïîòåçó H 0 â ³íøîìó âèïàäêó. Ïîð³ã äåòåêòóâàííÿ � ( )Y âèçíà÷àºòüñÿ âåëè÷è- íàìè éìîâ³ðíîñòåé ïîìèëîê ïåðøîãî òà äðóãîãî ðîä³â: � 0 òà �1 â³äïîâ³äíî. Îáìåæåííÿ íà éìîâ³ðíîñò³ ïîìèëîê ïåðøîãî òà äðóãîãî ðîä³â ìàòèìóòü âèãëÿä P R S Y Y H( ( , ) ( ) \| ) � �0 0 , P R S Y Y H Y( ( , ) ( ) \| ( ))� � �1 1. (5) Ïðèïóñòèìî, ùî ðîçïîä³ë âåëè÷èíè R S Y( , ) ÿê çà óìîâè H 0 , òàê ³ çà óìîâè H Y1 ( ) º íåïåðåðâíèì. Ïîçíà÷èìî q0 êâàíòèëü ð³âíÿ 1 0�� ðîçïîä³ëó âåëè÷èíè R S Y( , ) çà óìîâè H 0 , à q1 — êâàíòèëü ð³âíÿ �1 ðîçïîä³ëó âåëè÷èíè R S Y( , ) çà óìîâè H Y1 ( ). Ñï³ââ³äíîøåííÿ (5) ìîæíà çàïèñàòè ó âèãëÿä³ q Y q0 1 � ( ) . ßêùî q q0 1 , âèáåðåìî � ( ) ( ) /Y q q� �0 1 2. Íåð³âí³ñòü q q0 1� îçíà÷àº, ùî ñèñ- òåìà íå ìàº äîñòàòíüî ñåíñîð³â äëÿ âèêîíàííÿ óìîâ (5). Ðîçãëÿíåìî âèïàäîê, êîëè àáî ïîðóøíèêà íåìàº â îáëàñò³ W, àáî ïðî íüîãî â³äîìî ò³ëüêè òå, ùî â³í ïåðåáóâàº â îáëàñò³ W. Ó öüîìó âèïàäêó çàñòîñîâóºìî òåñò Íåéìàíà–Ï³ðñîíà äî êîæíî¿ òî÷êè W (çâè÷àéíî, ï³ä ÷àñ ÷èñëîâèõ ðîçðàõóíê³â éäåòüñÿ ò³ëüêè ïðî ñê³í÷åííó ìíîæèíó òî÷îê, ÿêà äîñèòü ù³ëüíî ïîêðèâàº W). Îáìåæåííÿ (5), ÿê³ ñòîñóþòüñÿ ïîìèëîê ïåðøîãî òà äðóãîãî ðîä³â, ïîâèíí³ âèêîíó- âàòèñü äëÿ âñ³õ Y W� . Çàóâàæèìî, ùî â òàêîìó âèïàäêó âèíèêàº ïðîáëåìà: éìîâ³ðí³ñòü äåòåêòóâàííÿ çàãðîçè çà óìîâè ¿¿ â³äñóòíîñò³ (òîáòî éìîâ³ðí³ñòü ïîìèë- êè ïåðøîãî ðîäó) ìîæå ïåðåâèùèòè ÷èñëî � 0 (5). Öþ éìîâ³ðí³ñòü � �0 0� � � P Y W R s Y Y H( : ( , ) ( ) \| ) ìîæíà çíàéòè ìåòîäîì Ìîíòå-Êàðëî. Âåëè÷èíà � 0 çàëåæèòü â³ä âèáîðó ÷èñëà � 0 . Ïðèïóñòèìî, ùî çà óìîâ ñïðàâåäëèâîñò³ ã³ïîòåç H 0 àáî H Y1 ( ) âèïàäêîâ³ âå- ëè÷èíè S j , j n�1 2, , ,� , íåçàëåæí³. Ìàºìî ln ( , ) ln ( , )R S Y R S Y j n j j� � � 1 , äå R S Y P S H Y P S H j j S j S j j j ( , ) ( \| ( )) ( \| ) � 1 0 . Äëÿ ìîäåëåé ñåíñîð³â 1 ³ 2 âåëè÷èíè P S H YS jj ( \| ( ))1 òà P S HS jj ( \| )0 âèçíà÷àþòü ôîðìóëàìè (2)–(4). Äëÿ âèêîðèñòàííÿ òåñòó Íåéìàíà–Ï³ðñîíà íåîáõ³äíî çíàòè ðîçïîä³ë âèïàäêî- âî¿ âåëè÷èíè ln ( , ) ln ( , )R S Y R S Yj j j n � � � 1 çà óìîâè ñïðàâåäëèâîñò³ ã³ïîòåç H 0 , àáî H Y1 ( ). Ç öåíòðàëüíî¿ ãðàíè÷íî¿ òåîðåìè òåîð³¿ éìîâ³ðíîñòåé [11] âèïëèâàº, ùî çà óìîâè Ë³íäåáåðãà äëÿ äîñòàòíüî âåëèêèõ çíà÷åíü n ðîçïîä³ë âåëè÷èíè ln ( , )R S Y º áëèçüêèì äî íîðìàëüíîãî. Ó âèïàäêó âèêîðèñòàííÿ ñåíñîðíî¿ ìîäåë³ 2 âåëè÷èíà ln ( , )R S Y ìàº íîðìàëüíèé ðîçïîä³ë, îñê³ëüêè íîðìàëüíî ðîçïîä³ëå- íèìè º âåëè÷èíè S j . ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 2 87 Ìîäåëü 2 àêóñòè÷íîãî ñåíñîðà îïèñàíî â ðîáîò³ [9], äå òàêîæ íàâåäåíî áàãà- òîïåð³îäíèé àëãîðèòì äåòåêòóâàííÿ çàãðîçè. Òàêèé àëãîðèòì âèêîðèñòîâóº äàí³, ùî íàäõîäÿòü â³ä ñåíñîð³â ó ïîñë³äîâí³ ìîìåíòè ÷àñó; äëÿ äåòåêòóâàííÿ çàñòîñî- âóþòü ìåòîä ïîñë³äîâíîãî ñòàòèñòè÷íîãî àíàë³çó [12]. ÇÀÄÀ×² ÎÏÒÈÌÀËÜÍÎÃÎ ÐÎÇÌ²ÙÅÍÍß ÑÅÍÑÎÐ²Â Ïðèïóñòèìî, ùî ³ñíóº K òèï³â ñåíñîð³â. Íåõàé nk — ê³ëüê³ñòü ñåíñîð³â k-ãî òèïó, ÿê³ ïëàíóºòüñÿ ðîçì³ñòèòè â îáëàñò³ W, ck — ö³íà ñåíñîðà k-ãî òèïó, X kj — âåêòîð êîîðäèíàò j-ãî ñåíñîðà k-ãî òèïó, X Wkj � , k K�1 2, , ,� , j nk�1 2, , ,� . Ðîçãëÿíåìî íàñòóïíó çàäà÷ó îïòèìàëüíîãî ðîçì³ùåííÿ ñåíñîð³â min ,n X W k k k K k kj c n � � � 0 1 , (6) � k kj j n k K Y X I Y W k (\| \| \| \| )� � � �� 11 . (7) Ôóíêö³ÿ � k ( )� õàðàêòåðèçóº íàä³éí³ñòü äåòåêòóâàííÿ çàãðîçè îäíèì ñåíñîðîì k-ãî òèïó, âåëè÷èíà I îçíà÷àº çàäàíó íàä³éí³ñòü äåòåêòóâàííÿ ñèñòåìîþ ñåí- ñîð³â. Íàä³éí³ñòü ìîæå âèì³ðþâàòèñü çà äîïîìîãîþ ð³çíèõ âåëè÷èí, òàêèõ ÿê ê³ëüê³ñòü ³íôîðìàö³¿, ùî íàäõîäèòü äî ñåíñîð³â ç òî÷êè Y , òà ³í. Äàë³ ðîçãëÿ- íåìî ôîðìóëþâàííÿ çàäà÷³ (6), (7) ó âèïàäêó âèêîðèñòàííÿ îïèñàíèõ ìîäåëåé ³ àëãîðèòì³â âèÿâëåííÿ çàãðîçè. Íåõàé âèêîðèñòîâóºòüñÿ îäíîïåð³îäíèé àëãîðèòì äåòåêòóâàííÿ. Ðîçãëÿíåìî çàäà÷ó ì³í³ì³çàö³¿ âàðòîñò³ ñåíñîðíî¿ ñèñòåìè çà îáìåæåíü (5) íà éìîâ³ðíîñò³ ïî- ìèëîê ïåðøîãî òà äðóãîãî ðîä³â min ,n X W k k k K k kj c n � � � 0 1 , (8) P R S Y Y H Y W( ( , ) ( ) \| ) � �� 0 0 , (9) P R S Y Y H Y Y W( ( , ) ( ) \| ( ))� � �� 1 1 . (10) Ïðèïóñòèìî, ùî ÿê ìàòåìàòè÷íó ìîäåëü ñåíñîðà âèêîðèñòîâóþòü ìîäåëü 2. Íåõàé çàãàëüíà ê³ëüê³ñòü ñåíñîð³â äîð³âíþº n ³ âñ³ âîíè ³äåíòè÷í³. Íåõàé òà- êîæ � îçíà÷àº �-êâàíòèëü íîðìàëüíîãî ðîçïîä³ëó éìîâ³ðíîñòåé. Ó ðîáîò³ [9] ïîêàçàíî, ùî çàäà÷ó (8)–(10) ìîæíà çàïèñàòè ó âèãëÿä³ min X Wj n � , (11) f d Y Wj j n 2 2 1 1 1 2 2 0 1 ( ) ( ) � � �� . (12) Çàäà÷à (11), (12) º îêðåìèì âèïàäêîì çàäà÷³ (6), (7), äå � k d f d( ) ( )� 2 2 òà I � �� ( ) �� 1 1 2 2 0 1 . Öþ çàäà÷ó ìîæíà óçàãàëüíèòè íà âèïàäîê ³ñíóâàííÿ ê³ëüêîõ òèï³â ñåíñîð³â. ßêùî âèêîðèñòîâóâàòè áàãàòîïåð³îäíèé àëãîðèòì äåòåêòóâàííÿ, òî çàäà÷ó ì³í³ì³çàö³¿ âàðòîñò³ ñåíñîðíî¿ ñèñòåìè çà îáìåæåíü íà ñåðåäí³é ÷àñ âèÿâëåííÿ çà- ãðîçè òà íà éìîâ³ðí³ñòü ïîìèëêè ïåðøîãî ðîäó ìîæíà çàïèñàòè ó âèãëÿä³ min ,n X W k k k K k kj c n � � � 0 1 , (13) E T T( ) max , (14) äå T — ê³ëüê³ñòü ÷àñó, ùî ïðîõîäèòü â³ä ìîìåíòó, êîëè ïîðóøíèê ç’ÿâèâñÿ â îáëàñò³ W, äî ìîìåíòó éîãî âèÿâëåííÿ. Â [9] çàäà÷à (13), (14) çà äåÿêèõ óìîâ çâåäåíà äî çàäà÷³ (6), (7). Îòæå, ðîçãëÿíóò³ çàäà÷³ º îêðåìèìè âèïàäêàìè çàäà÷³ (6), (7), ÿêó ìîæíà çâåñòè äî çàäà÷³ áóëåâîãî ïðîãðàìóâàííÿ òàê. Íåõàé Z Z Z Z M� { }1 2, , ,� — ìíî- 88 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 2 æèíà òî÷îê ç îáëàñò³ W òàêèõ, ùî äëÿ êîæíî¿ òî÷êè Y W� ñïðàâåäëèâà íåð³âí³ñòü min \| \| \| \| , , ,m M mY Z � � 1 � � äå �� 0. Íåõàé zmkj �1, ÿêùî â òî÷ö³ Z Zm � âñòàíîâëåíî ñåíñîð òèïó k ç íîìåðîì j N k�{ }1 2, , ,� ; zmkj � 0 â ³íøîìó âèïàäêó. Òóò N k — ìàêñèìàëüíî ìîæëèâà ê³ëüê³ñòü ñåíñîð³â òèïó k. Çàì³ñòü çàäà÷³ (6), (7) ðîçãëÿíå- ìî çàäà÷ó min z j N k mkj k K m M mkj k c z �� 111 , (15) m M k K k m mkj j N Y Z z I Y Z k � � � � � � � � � 1 1 1 � (\| \| \| \| ) , (16) zmkj m M � � 1 1, k K�1 2, , ,� , j N k�1 2, , ,� , (17) zmkj �{ }0 1, , m M�1 2, , ,� , k K�1 2, , ,� , j N k�1 2, , ,� . (18) Íåð³âíîñò³ (17) ãàðàíòóþòü, ùî îäèí ñåíñîð ìîæå áóòè ðîçì³ùåíèé ò³ëüêè â îäí³é òî÷ö³, àáî â³í ìîæå íå âèêîðèñòîâóâàòèñÿ. Â îäí³é òî÷ö³ äîçâîëÿºòüñÿ ðîçì³ùóâàòè îäèí àáî ê³ëüêà ñåíñîð³â. Çàäà÷ó (15)–(18) ìîæíà ðîçâ’ÿçàòè îäíèì ç ÷èñëîâèõ ìåòîä³â áóëåâîãî ïðîãðàìóâàííÿ. Äàë³ ðîçãëÿíåìî çàäà÷³, äëÿ ðîçâ’ÿçàííÿ ÿêèõ ìîæíà çàñòîñóâàòè ïðîñò³ø³ ìåòîäè ó ïîð³âíÿíí³ ç ìåòîäàìè çàãàëüíîãî ïðèçíà÷åííÿ. Äëÿ òàêèõ çàäà÷ âäàºòüñÿ íå ò³ëüêè ïîáóäóâàòè áëèçüê³ äî îïòèìàëüíèõ ðîçâ’ÿçêè ó âèãëÿä³ ÷èñ- ëîâèõ âåêòîð³â, àëå é äîñë³äèòè ¿õí³ âëàñòèâîñò³. Çîêðåìà, ðîçãëÿíåìî çàäà÷ó min , ,n u X j j n j j c u � � 1 , (19) �(\| \| \| \| )Y X u I Y Wj j j n � � � � � 1 , (20) n u X Wj j �1 0, , , j n�1 2, , ,� , (21) äå uj — ä³éñíå ÷èñëî, ùî õàðàêòåðèçóº «ïîòóæí³ñòü» j-ãî ñåíñîðà, n — ê³ëüê³ñòü ñåíñîð³â, c — ö³íà îäèíèö³ «ïîòóæíîñò³», X j — âåêòîð êîîðäèíàò j-ãî ñåíñîðà. ßêùî u j �1, îòðèìóºìî çàäà÷ó min X j n, (22) �(\| \| \| \| )Y X I Y Wj j n � � � � � 1 , (23) n X Wj �1, , j n�1 2, , ,� . (24) Ó ö³é çàäà÷³ âèìàãàºòüñÿ ì³í³ì³çóâàòè ê³ëüê³ñòü îäíîòèïíèõ ñåíñîð³â, ùî ðîçì³ùåí³ â îáëàñò³ W òà çàáåçïå÷óþòü âèêîíàííÿ íåð³âíîñòåé (23). ÐÅÃÓËßÐÍÈÉ ÑÏÎÑ²Á ÐÎÇÌ²ÙÓÂÀÍÍß ÑÅÍÑÎÐ²Â Ðîçãëÿíåìî ñïîñ³á ðîçì³ùóâàííÿ ñåíñîð³â ó îáëàñò³ W, ÿêèé ïîëÿãàº â òîìó, ùî ñåíñîðè ðîçòàøîâóþòüñÿ ó âåðøèíàõ ðåãóëÿðíî¿ ñ³òêè, óòâîðåíî¿ ïðàâèëü- íèìè òðèêóòíèêàìè, êâàäðàòàìè àáî ïðàâèëüíèìè øåñòèêóòíèêàìè (ðèñ. 1). Ïðèïóñòèìî, ùî äëÿ çàäà÷³ (19)–(21) âèêîíóþòüñÿ òàê³ óìîâè. Ôóíêö³ÿ �( ),d d 0, º íåçðîñòàþ÷îþ íåïåðåðâíîþ Ë³ïøèöåâîþ ç êîíñòàíòîþ L � 0 òà íà- áóâàº íåâ³ä’ºìíèõ çíà÷åíü. ²ñíóº ÷èñëî r � 0 òàêå, ùî �( )d � 0 äëÿ 0 �d r, �( )d � 0 äëÿ d r , �( )0 br äëÿ äåÿêî¿ êîíñòàíòè b� 0. ×èñëî r îçíà÷àº ðàä³óñ ä³¿ ñåíñîðà. Ïðèïóñòèìî, ùî îáëàñòü W — ìíîãîêóòíèê, óñ³ êóòè ÿêîãî íå ìåíø³ çà / 2. Âèêîíàííÿ îñòàííüî¿ óìîâè ìîæíà çàáåçïå÷èòè, «çð³çàþ÷è» ãîñòð³ êóòè, ÿêùî âîíè º, òà çá³ëüøóþ÷è ê³ëüê³ñòü ñòîð³í ìíîãîêóòíèêà. Ââàæàºìî, ùî I � 0. ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 2 89 Îïèøåìî ìåòîä, ùî áóäóº äîïóñòèìèé ðîçâ’ÿçîê G X X X n� ( , , , )1 2 � çàäà- ÷³ (19)–(21), áëèçüêèé äî îïòèìàëüíîãî. Ðîçãëÿíåìî ðåãóëÿðíó ñ³òêó S , ñôîðìî- âàíó ïðàâèëüíèìè òðèêóòíèêàìè, êâàäðàòàìè àáî ïðàâèëüíèìè øåñòèêóòíèêàìè ç äîâæèíîþ ñòîðîíè s (äèâ. ðèñ. 1). Ââàæàºìî, ùî s r . Ïîçíà÷èìî u u u Y X I Y C X YS � � � � � � � � �� min : (\| \| \| \| )� , äå YS — ìíîæèíà âñ³õ âåðøèí ðåãóëÿðíî¿ ñ³òêè S , C — ðåãóëÿðíà ô³ãóðà ñ³òêè (òðèêóòíèê, êâàäðàò àáî øåñòèêóòíèê). Ïîçíà÷èìî W r1 ( ) ìíîæèíó òî÷îê X W� , äëÿ ÿêèõ â³äñòàíü äî ìåæ³ ìíîæèíè W íå ìåíøà çà r. Íåõàé G Y W X X XS n � � � ( , , , )1 0 2 0 0 0 � , G r G W r1 1( ) ( )� � , G r G G r0 1( ) \ ( )� . Âèáåðå- ìî ÷èñëî h� 4 òà ðîçãëÿíåìî ðîçâ’ÿçîê çàäà÷³ (19)–(21), ÿêèé ìîæíà çàäàòè ñï³ââ³äíîøåííÿìè n n� 0 , X Xj j� 0 , (25) u u u X G r hu X G r j j j j � � � � � � 0 1 0 , ( ), , ( ), j n�1 2 0, , ,� . (26) Îñê³ëüêè êóòè ìíîãîêóòíèêà W íå ìåíø³ çà / 2 ³ h� 4, ðîçâ’ÿçîê (25), (26) º äî- ïóñòèìèì äëÿ çàäà÷³ (19)–(21) çà óìîâè, ùî âåëè÷èíè r òà s r/ äîñòàòíüî ìàë³. Ïîçíà÷èìî f r s0 ( , ) çíà÷åííÿ ö³ëüîâî¿ ôóíêö³¿ çàäà÷³ (19)–(21) äëÿ ðîçâ’ÿçêó (25), (26), f r s c u j j n 0 0 1 0 ( , ) � � � . Íåõàé f r* ( ) — îïòèìàëüíå çíà÷åííÿ ö³ëüîâî¿ ôóíê- ö³¿ çàäà÷³ (19)–(21). Íàñòóïíà òåîðåìà ñòâåðäæóº, ùî ðîçâ’ÿçîê (25), (26) º àñèì- ïòîòè÷íî îïòèìàëüíèì. Òåîðåìà 1. Íåõàé W I L, , çàëèøàþòüñÿ íåçì³ííèìè, �( )0 br äëÿ äåÿêî¿ êîí- ñòàíòè b� 0, ñïðàâåäëèâ³ ñï³ââ³äíîøåííÿ r � 0, s� 0, s r/ � 0. Òîä³ f r s f r 0 1 ( , ) ( )� � . Äîâåäåííÿ. Ðîçãëÿíåìî òàêó çàäà÷ó ë³í³éíîãî ïðîãðàìóâàííÿ min u j j n j c u � � 1 0 , (27) a u I i nij j j n � � � 1 0 0 1 2, , , ,� , (28) u j 0, j n�1 2 0, , ,� , (29) äå a X X X X Gij i j i j� � ��(\| \| \| \| ), , . Äâî¿ñòîþ äî çàäà÷³ (27)–(29) º çàäà÷à 90 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 2 Ðèñ. 1. Ðåãóëÿðí³ ñ³òêè äëÿ ðîçì³ùóâàííÿ ñåíñîð³â max � � i I i i n � � 1 0 , (30) a c j nij i i n � � � � 1 0 0 1 2, , , ,� , (31) � i 0, i n�1 2 0, , ,� . (32) Íåõàé ðîçâ’ÿçêè ( , , , )u u u n1 2 0� òà ( , , , )� � �1 2 0� n º äîïóñòèìèìè äëÿ çàäà÷ (27)–(29) òà (30)–(32) â³äïîâ³äíî. ²ç âçàºìíî¿ äâî¿ñòîñò³ öèõ çàäà÷ âèïëèâàº íåð³âí³ñòü c u Ij j n i i n � � � � 1 1 0 0 � . (33) Ïîçíà÷èìî J X j j n X X rj( ) : , , , , \| \| \| \|� � � { { } }1 2 0 0 � . Îñê³ëüêè �( )d � 0 äëÿ d r� , íåð³âíîñò³ (28), (31) çàì³íèìî íåð³âíîñòÿìè j J X ij j i a u I � � ( )0 , i n�1 2 0, , ,� , òà i J X ij i j a c � � ( )0 � , j n�1 2 0, , ,� , â³äïîâ³äíî. Äëÿ äîñòàòíüî ìàëî¿ âåëè÷èíè r âåêòîð U u u u n 1 1 1 2 1 1 0 � ( , , , )� , âèçíà÷åíèé ôîðìóëàìè u u X G r hu X G r j j j 1 1 1 1 0 � � � � � �� , ( ), , ( ), j n�1 2 0, , ,� , äå u I a j J X ij i 1 0 � � � ( ) , X G ri 0 1� ( ), º äîïóñòèìèì ðîçâ’ÿçêîì çàäà÷³ (27)–(29). Çíà÷åííÿ ö³ëüîâî¿ ôóíêö³¿ äëÿ öüîãî âåêòîðà ñòàíîâèòü f r s c u cu G r h G r cu n h j n j 1 1 1 1 1 0 1 0 0 ( , ) (\| ( ) \| \| ( ) \| ) ( (� � � � � � � �1 0) \| ( ) \| )G r , äå \| \|G îçíà÷àº ê³ëüê³ñòü åëåìåíò³â ìíîæèíè G . Ó ñâîþ ÷åðãó, âåêòîð ( , , , )� � �1 2 0� n , äå � i cu I� 1 / , º äîïóñòèìè ðîçâ’ÿçêîì äâî¿ñòî¿ çàäà÷³ (30)–(32), çíà÷åííÿ ö³ëüîâî¿ ôóíêö³¿ ÿêî¿ äëÿ öüîãî âåêòîðà äîð³âíþº cu n1 0 . Âèêîðèñòîâóþ÷è íåð³âí³ñòü (33), îö³íþºìî îïòèìàëüíå çíà÷åííÿ f r s� ( , ) ö³ëüîâî¿ ôóíêö³¿ çàäà÷³ (27)–(29): cu n f r s f r s cu n h G r1 0 1 1 0 01 � � �� ( , ) ( , ) ( ( ) \| ( ) \| ). Îòæå, f r s h G r n f r s1 0 0 1 1( , ) ( ) \| ( ) \| ( , )* � � � � �� . (34) Ç äîïóñòèìîñò³ ðîçâ’ÿçêó (25), (26) äëÿ çàäà÷³ (19)–(21) âèïëèâàº íåð³âí³ñòü f r f r s� ( ) ( , )0 . (35) Çà äîïîìîãîþ åëåìåíòàðíèõ ì³ðêóâàíü ç (34) òà (35) âèâîäèìî íåð³âíîñò³ f r f r s f r� � �( ) ( , ) ( ) ( )0 1 � , äå � � 0 çà óìîâè, ùî r � 0. ²ç öèõ ñï³ââ³äíîøåíü âèïëèâàº ñïðàâåäëèâ³ñòü òåîðåìè. Òåîðåìó äîâåäåíî. Ç òåîðåìè 1 âèïëèâàº, ùî ðîçì³ùóâàííÿ ñåíñîð³â îäíàêîâî¿ «ïîòóæíîñò³» ó âåðøèíàõ ðåãóëÿðíî¿ ñ³òêè ïðèçâîäèòü äî áëèçüêèõ äî îïòèìàëüíèõ ðîçâ’ÿçê³â çàäà÷³ (19)–(21). Òîìó äàë³ ââàæàºìî, ùî u j �1, òà ðîçãëÿíåìî çàäà÷ó (22)–(24). ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 2 91 ×ÈÑËÎÂÈÉ ÌÅÒÎÄ ÏÎÁÓÄÎÂÈ ÁËÈÇÜÊÎÃÎ ÄÎ ÎÏÒÈÌÀËÜÍÎÃÎ ÐÎÇÌ²ÙÅÍÍß ÑÅÍÑÎÐ²Â Ðîçãëÿíåìî çàäà÷ó (22)–(24) òà â³äïîâ³äíèé ÷èñëîâèé ìåòîä ðîçì³ùóâàííÿ ñåí- ñîð³â â îáëàñò³ W. Ðåçóëüòàòîì ðîáîòè ìåòîäó º ïëàí ðîçì³ùåííÿ îäíîòèïíèõ ñåíñîð³â, ùî çàäîâîëüíÿº óìîâè (23), (24), òà º àñèìïòîòè÷íî îïòèìàëüíèì ðîç- â’ÿçêîì. Ââàæàºìî, ùî îáëàñòü W, âåëè÷èíà I òà ôóíêö³ÿ �( ),d d 0, çàäîâîëü- íÿþòü óìîâè, ùî îïèñàí³ â ïîïåðåäíüîìó ðîçä³ë³. ²äåÿ ìåòîäó ïîëÿãàº â òîìó, ùî ñåíñîðè ðîçì³ùóþòü ó âåðøèíàõ ðåãóëÿðíî¿ ñ³òêè, à íà ìåæ³ îáëàñò³ W ðîçì³ùóþòü äîäàòêîâ³ ñåíñîðè. Ðîçãëÿíåìî ò³ëüêè ðåãóëÿðíó ñ³òêó, óòâîðåíó êâàäðàòàìè (äèâ. ðèñ. 1). ×èñëîâ³ ìåòîäè äëÿ ðåãóëÿðíèõ ñ³òîê, óòâîðåíèõ ïðà- âèëüíèìè òðèêóòíèêàìè àáî øåñòèêóòíèêàìè, áóäóþòü ïîä³áíèì ñïîñîáîì. Ïîçíà÷èìî Q ðåãóëÿðíó ñ³òêó, óòâîðåíó êâàäðàòàìè ç äîâæèíîþ ñòîðîíè q , r q� 3 2/ . Íåõàé YQ — ìíîæèíà âñ³õ âåðøèí ñ³òêè Q ; CQ — ìíîæèíà âñ³õ êâàä- ðàò³â C ñ³òêè Q , äëÿ ÿêèõ âèêîíóºòüñÿ ñï³ââ³äíîøåííÿ W C� !int , äå int C — âíóòð³øíÿ ÷àñòèíà ìíîæèíè C ; ~ YQ — ìíîæèíà âñ³õ âåðøèí ñ³òêè Q , ùî íàëåæàòü êâàäðàòàì ç ìíîæèíè CQ . Ïîçíà÷èìî W W r0 0� ( ) ìíîæèíó òî÷îê X W� , äëÿ ÿêèõ â³äñòàíü äî ìåæ³ ìíîæèíè W íå á³ëüøà çà r. Íåõàé C Q 0 — ìíîæèíà âñ³õ êâàäðàò³â C ñ³òêè Q, äëÿ ÿêèõ âèêîíóºòüñÿ ñï³ââ³äíîøåííÿ W C0 � !int ; ~ Y Q 0 — ìíîæèíà âñ³õ âåðøèí ñ³òêè Q, ùî íàëåæàòü êâàäðàòàì ç ìíîæèíè C Q 0 . Òàê ñàìî ðîçãëÿíåìî ñôîðìîâàíó êâàäðàòàìè ³ç ñòîðîíîþ s ðåãóëÿðíó ñ³òêó S , äëÿ ÿêî¿ âåëè÷èíà s âèçíà÷àºòüñÿ àëãîðèòìîì. Ïîçíà÷èìî YS ìíîæèíó âåðøèí ñ³òêè S . Ââàæàºìî, ùî ë³í³¿ ñ³òêè S ïàðàëåëüí³ àáî ïåðåïåíäèêóëÿðí³ ë³í³ÿì ñ³òêè Q ³ ùî ìíîæèíà âåðøèí ñ³òêè S íàëåæèòü ìíîæèí³ âåðøèí ñ³òêè Q , òîáòî s q/ º ö³ëèì ÷èñëîì. Ðîçãëÿíåìî ìåòîä [9], ùî áóäóº äîïóñòèìèé ðîçâ’ÿçîê G X X X n� ( , , , )1 2 � çàäà÷³ (22)–(24), áëèçüêèé äî îïòèìàëüíîãî. Êðîê 1. Ðîçâ’ÿæåìî çàäà÷ó max s, (36) X Y Q S Y X q I Y C Y � � � � � � ��(\| \| \| \| / )2 , (37) s q n/ , , , , ...�{ }1 2 � , (38) äå çì³ííà s — äîâæèíà ñòîðîíè êâàäðàòó ñ³òêè S ³ C — êâàäðàò ñ³òêè S . Ô³êñóºìî îïòèìàëüíå çíà÷åííÿ çì³ííî¿ s ³ äàë³ ââàæàºìî, ùî ñ³òêà S óòâîðåíà êâàäðàòàìè ç äîâæèíîþ ñòîð³í s. Âèáåðåìî G Y WS� � . (39) Êðîê 2. ßêùî âèêîíóþòüñÿ íåð³âíîñò³ X G Q Y X q I Y Y � � � � � ��(\| \| \| \| / ) ~ 2 0 , (40) ðîáîòó ìåòîäó çóïèíÿºìî. Êðîê 3. Âèáåðåìî òî÷êó Y Y Q � ~ 0 , ùî ìàêñèì³çóº âèðàç I Y X q X G � � � � � �(\| \| \| \| / )2 . Âêëþ÷èìî â ðîçâ’ÿçîê G ïðîåêö³þ "W Y( ) òî÷êè Y íà ìíîæèíó W. Ïåðåõîäè- ìî äî êðîêó 2. Çàóâàæèìî, ùî îïèñàíèé ìåòîä ñê³í÷åííèé. Ä³éñíî, îñê³ëüêè r q� 3 2/ ³ äëÿ êîæíî¿ òî÷êè Y ç ìíîæèíè ~ Y Q 0 ñïðàâåäëèâà íåð³âí³ñòü \| \| ( ) \| \|Y Y qW� " 2 , çíà- 92 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 2 ÷åííÿ I Y X q X G � � � � � �(\| \| \| \| / )2 íà êðîö³ 3 äëÿ âèáðàíî¿ òî÷êè Y Y Q � ~ 0 çìåí- øóºòüñÿ ÿê ì³í³ìóì íà âåëè÷èíó � �( / ) ( / )2 2 3 2 0q q q� � � . Îñê³ëüêè ìíî- æèíà ~ Y Q 0 ñê³í÷åííà, íåð³âí³ñòü (40) áóäå ñïðàâåäëèâîþ ï³ñëÿ ñê³í÷åííî¿ ê³ëüêîñò³ ³òåðàö³é. Ëåãêî äîâåñòè, ùî ïîáóäîâàíèé ðîçãëÿíóòèì ìåòîäîì ðîçâ’ÿçîê G X X X n� ( , , , )1 2 � º äîïóñòèìèì ðîçâ’ÿçêîì çàäà÷³ (22)–(24), òîáòî j n jY X I � � � 1 �(\| \| \| \| ) � �Y W. (41) Ä³éñíî, äëÿ êîæíî¿ òî÷êè Y W� íàéáëèæ÷à äî ö³º¿ òî÷êè âåðøèíà # �Y YQ íà- ëåæèòü ìíîæèí³ ~ YQ . ßêùî # $Y Y Q ~ 0 , òî ç (36)–(39) âèïëèâàº j n jY X q I � � # � � 1 2�(\| \| \| \| / ) . (42) ßêùî # �Y Y Q ~ 0 , òî (42) âèïëèâàº ç (40). Îñê³ëüêè ôóíêö³ÿ �( )d íåçðîñòàþ÷à òà \| \| ' \| \| /Y Y q� 2, ìàºìî � �(\| \| \| \| ) (\| \| \| \| / )Y X Y X q Ij j n j j n � # � � � � � � 1 1 2 , çâ³äêè âèïëèâàº (41). Çàóâàæèìî, ùî â çàäà÷³ (22)–(24) íå áåðóòü äî óâàãè ïåðåøêîäè, ùî ìîæóòü áóòè ì³æ ñåíñîðàìè òà ö³ëëþ â îáëàñò³ W. Òîìó ïîáóäîâàíèé ðîçâ’ÿçîê G ìîæíà ââàæàòè äîñòàòíüî ÿê³ñíèì ò³ëüêè äëÿ âèïàäê³â, êîëè îáëàñòü W º áëèçüêîþ äî îïóêëî¿. Ñïðàâåäëèâîþ º òåîðåìà ïðî àñèìïòîòè÷íó îïòèìàëüí³ñòü ïîáóäîâàíîãî ðîçãëÿíóòèì ìåòîäîì ðîçâ’ÿçêó G . Íåõàé f r* ( ) — îïòèìàëüíå çíà÷åííÿ ö³ëüîâî¿ ôóíêö³¿ çàäà÷³ (22)–(24), f r q n G0 ( , ) \| \|� � — çíà÷åííÿ ö³ëüîâî¿ ôóíêö³¿ ö³º¿ çà- äà÷³ äëÿ ðîçâ’ÿçêó G . Òåîðåìà 2. Íåõàé W, I , L çàëèøàþòüñÿ íåçì³ííèìè, �( )0 br äëÿ äåÿêî¿ êîí- ñòàíòè b� 0, ñïðàâåäëèâ³ ñï³ââ³äíîøåííÿ r � 0, q � 0, q r/ /3 2 0� . Òîä³ f r q f r 0 1 ( , ) ( )� � . Äîâåäåííÿ òåîðåìè íàâåäåíî â [9]. Òåîðåìà ïðî àñèìïòîòè÷íó îïòèìàëü- í³ñòü íå ãàðàíòóº ÿê³ñíî¿ ðîáîòè ìåòîäó ó âèïàäêó, êîëè âåëè÷èíè r q, íå º áëèçü- êèìè äî íóëÿ. Â [9] îïèñàíî ÷èñëîâ³ åêñïåðèìåíòè, çà äîïîìîãîþ ÿêèõ íàâåäå- íèé ìåòîä ïîð³âíþþòü ç åâðèñòè÷íèì ìåòîäîì ç ðîáîòè [4]. Ðîçãëÿíåìî ³äåþ ìå- òîäó, íàâåäåíîãî â [4]. Âèáåðåìî òî÷êó Y W� , â ÿê³é íåð³âí³ñòü (23) ìàº íàéá³ëüøó ïîõèáêó, òà ðîçì³ñòèìî ñåíñîð ó òî÷ö³ Y . Ïîâòîðþºìî öåé êðîê äî òèõ ï³ð, äîêè îáìåæåííÿ íå áóäóòü âèêîíàí³. ×èñëîâ³ åêñïåðèìåíòè ïîêàçàëè, ùî â ñåðåäíüîìó îïèñàíèé ìåòîä áóäóº çà ö³ëüîâîþ ôóíêö³ºþ ðîçâ’ÿçîê ïðè- áëèçíî íà 25 % êðàùèé, í³æ ìåòîä ç ðîáîòè [4]. ÑÏÈÑÎÊ Ë²ÒÅÐÀÒÓÐÈ 1. Molyboha A., Zabarankin M. Stochastic optimization of sensor placement for diver detec- tion. Operations Research. 2012. Vol. 60, N 2. P. 292–312. 2. Iyer S., Rao D.V. Genetic algorithm based optimization technique for underwater sensor network positioning and deployment. Proc. of the IEEE Underwater Technology (UT’15). Chennai, India, February 2015. P. 1–6. ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 2 93 3. Hua Cheng Bing, Zhao Wei, Chang Zi Nan. Underwater acoustic sensor networks deployment using improved self-organize map algorithm. Cybernetics and Information Technologies. 2014. Vol. 14, N 5. P. 63–77. 4. Dhillon S.S., Chakrabarty K. Sensor placement for effective coverage and surveillance in distributed sensor networks. Wireless Communications and Networking. 2003. Vol. 3. P. 1609–1614. 5. Mhatre V.P., Rosenberg C., Kofman D., Mazumdar R., Shroff, N. A minimum cost heterogeneous sensor network with a lifetime constraint. IEEE Transactions on Mobile Computing. 2005. Vol. 4, N 1. P. 4–15. 6. Zou Y., Chakrabarty K. Sensor deployment and target localization based on virtual forces. Twenty-second annual joint conference of the IEEE computer and communications (INFOCOM 2003). IEEE Societies. 2003. Vol. 2. P. 1293–1303. 7. Zou Y., Chakrabarty K. Sensor deployment and target localization in distributed sensor networks. ACM Transactions on Embedded Computing Systems. 2004. Vol. 3, N 1. P. 61–91. 8. Felemban M. Optimal node placement in underwater acoustic sensor network: Doctoral dissertation. King Abdullah University of Science and Technology. Thuwal, Kingdom of Saudi Arabia. October 2011. 9. Pashko S., Molyboha A., Zabarankin M., Gorovyy S. Optimal sensor placement for underwater threat detection. Naval Research Logistics. 2008. Vol. 55, N 7. P. 684–699. 10. Burdic W.S. Underwater acoustic system analysis. New York: Prentice Hall, 1991. 452 p. 11. Øèðÿåâ À.Í. Âåðîÿòíîñòü. Ìîñêâà: Íàóêà, 1980. 574 ñ. 12. Âàëüä À. Ïîñëåäîâàòåëüíûé àíàëèç. Ìîñêâà: Ìèð, 1960. 328 ñ. Íàä³éøëà äî ðåäàêö³¿ 15.08.2017 Ñ.Â. Ïàøêî ÎÏÒÈÌÀËÜÍÎÅ ÐÀÇÌÅÙÅÍÈÅ ÌÍÎÃÎÑÅÍÑÎÐÍÎÉ ÑÈÑÒÅÌÛ ÄËß ÎÁÍÀÐÓÆÅÍÈß ÓÃÐÎÇÛ Àííîòàöèÿ. Îïèñàí àëãîðèòì äåòåêòèðîâàíèÿ ïîäâîäíîé óãðîçû ñ ïî- ìîùüþ ñèñòåìû àêóñòè÷åñêèõ ñåíñîðîâ, à òàêæå ýêñòðåìàëüíûå çàäà÷è ðàç- ìåùåíèÿ ñåíñîðîâ. Ðàññìîòðåíû ìåòîäû ðåøåíèÿ òàêèõ çàäà÷, äîêàçàíà òåî- ðåìà îá àñèìïòîòè÷åñêîé îïòèìàëüíîñòè ïîñòðîåííûõ ïëàíîâ ðàçìåùåíèÿ ñåíñîðîâ. Èç ðåçóëüòàòîâ ÷èñëåííûõ ýêñïåðèìåíòîâ ñëåäóåò, ÷òî ïîñòðîåí- íûé ìåòîä ïðåâîñõîäèò èçâåñòíûé ìåòîä ðåøåíèÿ çàäà÷ ðàçìåùåíèÿ ñåíñî- ðîâ. Êëþ÷åâûå ñëîâà: ñåíñîð, ìíîãîñåíñîðíàÿ ñèñòåìà, àëãîðèòì äåòåêòèðîâà- íèÿ óãðîçû, îïòèìàëüíîå ðàñïîëîæåíèå ñåíñîðîâ, àñèìïòîòè÷åñêàÿ îïòè- ìàëüíîñòü. S.V. Pashko OPTIMAL PLACEMENT OF MULTISENSOR SYSTEM FOR THREAT DETECTION Abstract. We consider the mathematical models for underwater acoustic sensors, the algorithm for threat detection by a multisensory system, and optimization problems for placement of such systems. The mathematical methods for optimal sensor placement is developed. The limit theorem on the optimality of sensor placement is proved. The numerical experiments demonstrate that the algorithm outperforms the available mathematical method for optimal sensor placement. Keywords: sensor, multisensor system, algorithm for threat detection, optimal sensor placement, asymptotic optimality. Ïàøêî Ñåðã³é Âîëîäèìèðîâè÷, êàíäèäàò ô³ç.-ìàò. íàóê, ñòàðøèé íàóêîâèé ñï³âðîá³òíèê ²íñòèòóòó ïðîãðàìíèõ ñèñòåì ÍÀÍ Óêðà¿íè, Êè¿â, e-mail: pashko55@yahoo.com. 94 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 2

Оптимальне розміщення багатосенсорної системи для виявлення загрози

Institution

Similar Items