(19) 대한민국특허청 (KR) (12) 등록특허공보 (B1) (45) 공고일자 2013년03월12일 (11) 등록번호 10-1242808 (24) 등록일자 2013년03월06일 (51) 국제특허분류 (Int. Cl.) H04L 12/28 (2006.01) H04L 12/26 (2006.01) H04W 8/08 (2009.01) H04W 84/18 (2009.01) (21) 출원번호 10-2009-7019179 (22) 출원일자 ( 국제 ) 2008 년 02 월 14 일 심사청구일자 2011 년 02 월 24 일 (85) 번역문제출일자 2009 년 09 월 14 일 (65) 공개번호 10-2009-0122235 (43) 공개일자 2009 년 11 월 26 일 (86) 국제출원번호 PCT/US2008/002067 (87) 국제공개번호 WO 2008/100604 국제공개일자 (30) 우선권주장 2008 년 08 월 21 일 11/725,794 2007 년 03 월 20 일미국 (US) 60/901,909 2007 년 02 월 16 일미국 (US) (56) 선행기술조사문헌 (73) 특허권자 티티아이인벤션스씨엘엘씨 미국델라웨어윌밍톤스위트 400 센터빌로드 2711 ( 우 : 19808) (72) 발명자 러스하난 미국뉴저지 07746 말보로트루먼드라이브 14 (74) 대리인 특허법인코리아나 KR100296293 B1 전체청구항수 : 총 22 항 심사관 : 김대성 (54) 발명의명칭광역감시를위한제한된개수의센서들의공정한배치방법 (57) 요약 제한된개수의센서들이감시될필요가있는모든위치에공정한커버리지레벨들을달성하기위해선택된위치에배치된다. 어떤특정위치에제공된커버리지레벨은객체검출확률과오류경보의확률을포함하며, 상기위치를감시하는모든센서들과상기센서들의속성에의존한다. 이들확률들은감시하는그리고감시되는위치들에의존한다. 모든위치에대한공정한커버리지레벨들중사전편찬식으로가장큰벡터를찾음으로써얻어진다. 여기서, 이들커버리지레벨들은증가하는순서로소팅된다. 방법은솔루션이공정한커버리지레벨들을제공하는사전편찬식의맥시민모델을생성한다. 계산을수행하기위하여, 솔루션이사전편찬식의맥시민최적화모델로서같은커버리지레벨들을제공하는비선형정수최적화모델이생성된다. 대표도 - 도 3-1 -
특허청구의범위청구항 1 특정영역에서제한된개수의센서들의배치를결정하는방법으로서, 상기센서들의배치가상기영역내에있는모든위치들에게커버리지레벨들을제공하고, 상기방법은, 노드들및지향된링크들을포함하는특정영역의네트워크표현을생성하는단계로서, 각노드는감시될서브영역또는센서가배치될수도있는서브영역을나타내거나감시될서브영역및센서가배치될수도있는서브영역양자모두를나타내며, 각각의지향된링크는노드쌍들 (node-pairs) 중에서감시관계를나타내며, 노드쌍은센서가배치될수도있는노드들의집합내의제1 노드와, 감시될노드들의집합내의관련된제2 노드를포함하는, 상기특정영역의네트워크표현을생성하는단계 ; 객체검출의확률들과오류경보의확률들을포함하는센서들의속성들로센서들을특징화하는단계로서, 상기확률들은다른노드쌍들에대하여상이할수도있는, 상기센서들의속성들로센서들을특징화하는단계 ; 감시될각노드들을감시하는센서들의위치의함수로서감시될각노드들에제공되는커버리지레벨에대한감시수행함수들을생성하는단계 ; 사전편찬식의맥시민최적화모델로서센서위치모델을생성하는단계로서, 상기사전편찬식의맥시민최적화모델의솔루션은사전편찬식으로가장큰정렬된벡터를제공하며, 상기벡터의요소들은증가하는순서로정렬된, 감시되는노드들에제공되는커버리지레벨들이며, 상기사전편찬식의맥시민최적화모델의솔루션은커버리지레벨들을제공하는, 상기센서위치모델을생성하는단계 ; 및비선형정수최적화모델로서사전편찬식의맥시민최적화모델을생성하는단계로서, 상기비선형정수최적화모델의솔루션은커버리지레벨들을모든노드들에게제공하며, 상기비선형정수최적화모델의솔루션은기존의최적화방법들에의해계산되는, 상기사전편찬식의맥시민최적화모델을생성하는단계를포함하는것을특징으로하는특정영역에서제한된개수의센서들의배치를결정하는방법. 청구항 2 특정영역에서제한된개수의센서들의배치를결정하는방법으로서, 상기센서들의배치는상기영역내에있는모든위치들에게커버리지레벨들을제공하고, 상기방법은, 노드들및지향된링크들을포함하는특정영역의네트워크표현을생성하는단계로서, 각노드는감시될서브영역또는센서가배치될수도있는서브영역을나타내거나감시될서브영역및센서가배치될수도있는서브영역양자모두를나타내며, 각각의지향된링크는노드쌍들중에서감시관계를나타내며, 노드쌍은센서가배치될수도있는노드들의집합내의제1 노드와, 감시될노드들의집합내의관련된제2 노드를포함하는, 상기특정영역의네트워크표현을생성하는단계 ; 감시될각노드들을감시하는센서들의위치의함수로서감시될각노드들에제공되는커버리지레벨에대한감시수행함수들을생성하는단계 ; 사전편찬식의맥시민최적화모델로서센서위치모델을생성하는단계로서, 상기사전편찬식의맥시민최적화모델의솔루션은사전편찬식으로가장큰정렬된벡터를제공하며, 상기제공된벡터의요소들은증가하는순서로정렬된, 감시되는노드들에제공되는커버리지레벨들이며, 상기사전편찬식의맥시민최적화모델의솔루션은커버리지레벨들을제공하는, 상기센서위치모델을생성하는단계 ; 및실행가능한센서위치모델을포함하는비선형정수최적화모델로서사전편찬식의맥시민최적화모델을생성하는단계로서, 비선형정수최적화모델의솔루션은커버리지레벨들을상기영역내에서감시될필요가있는모든위치들에제공하는, 상기사전편찬식의맥시민최적화모델을생성하는단계를포함하는것을특징으로하는특정영역에서제한된개수의센서들의배치를결정하는방법. 청구항 3-2 -
제2항에있어서, 객체함수가사전편찬식으로가장큰벡터를특정하며, 상기특정된벡터의요소들은증가하는순서로정렬된, 감시되는서브영역들에대한커버리지레벨들이며, 제약조건들은배치된센서의개수에대한제한을특정하며, 결정변수들은센서배치결정들을나타내는것을특징으로하는특정영역에서제한된개수의센서들의배치를결정하는방법. 청구항 4 제2항에있어서, 상기노드들은감시될서브영역들을나타내는노드집합 N을포함하며, 노드집합 S는센서들이배치될수있는위치들을나타내며, 집합 S 내의노드로부터집합 N 내의관련된노드까지의링크는집합 S내의노드가노드쌍으로집합 N에있는관련된노드를감시할수있는것을표시하는것을특징으로하는특정영역에서제한된개수의센서들의배치를결정하는방법. 청구항 5 제4항에있어서, 감시수행함수들은집합 N 내의임의의특정된노드에제공되는커버리지레벨을집합 N 내의상기특정된노드를감시할수있는집합 S 내의노드들에배치된모든센서들의함수로서계산하는것을특징으로하는특정영역에서제한된개수의센서들의배치를결정하는방법. 청구항 6 제5항에있어서, 객체검출의확률들과오류경보의확률들을포함하는센서들의속성들로센서들을특징화하는단계를더포함하며, 상기확률들은노드들의집합 N과 S 내의각노드쌍에대하여서로다를수도있으며, 상기감시수행함수들은센서들의속성들을입력으로이용하는것을특징으로하는특정영역에서제한된개수의센서들의배치를결정하는방법. 청구항 7 제2항에있어서, 실행가능한센서위치모델을포함하는상기비선형정수최적화모델은상기센서위치모델로부터생성되며, 상기실행가능한센서위치모델의최적솔루션은감시되는모든노드들에커버리지레벨들을제공하는것을특징으로하는특정영역에서제한된개수의센서들의배치를결정하는방법. 청구항 8 제7항에있어서, 상기실행가능한센서위치모델의최적솔루션은알려진최적화방법들을적용함으로써생성되는것을특징으로하는특정영역에서제한된개수의센서들의배치를결정하는방법. 청구항 9 노드들의집합 N 내의노드들에커버리지레벨들을제공하는노드들의집합 S 내의제한된개수의센서들의배치를결정하는방법으로서, 객체검출의확률들과오류경보의확률들을포함하는센서들의속성들로센서들을특징화하는단계로서, 각노드쌍은그것의관련된확률들을가지는, 상기센서들을특징화하는단계 ; 집합 N 내의관련된노드를감시하는집합 S 내의노드들에배치된센서들의함수로서집합 N 내의노드들의각각에제공된커버리지레벨을위해감시수행함수들을생성하는단계 ; 사전편찬식의맥시민최적화모델로서센서위치모델을생성하는단계로서, 상기사전편찬식의맥시민최적화모델의솔루션은사전편찬식으로가장큰정렬된벡터를제공하며, 상기제공된벡터의요소들은증가하는 - 3 -
순서로정렬된, 집합 N 내의노드들에제공되는커버리지레벨들이며, 상기사전편찬식의맥시민최적화모델의솔루션은커버리지레벨들을집합 N 내의모든노드들에제공하는, 상기센서위치모델을생성하는단계 ; 및실행가능한센서위치모델을생성하는단계로서, 상기실행가능한센서위치모델의솔루션은집합 N 내의모든노드들에커버리지레벨들을제공하는기존의최적화방법에의해계산되는, 상기실행가능한센서위치모델을생성하는단계를포함하는것을특징으로하는센서들의배치를결정하는방법. 청구항 10 제9항에있어서, 적어도하나의센서들의위치는한주기로부터다음주기사이에변경되는것을특징으로하는센서들의배치를결정하는방법. 청구항 11 제10항에있어서, 각주기에서, 상기실행가능한센서위치모델은가능한센서위치들의수정된집합을이용하여해가구해지는것을특징으로하는센서들의배치를결정하는방법. 청구항 12 특정영역에서제한된개수의센서들의배치를결정하는시스템으로서, 상기센서들의배치가상기영역내에있는모든위치들에게커버리지레벨들을제공하고, 상기시스템은, 노드들및지향된링크들을포함하는특정영역의네트워크표현을생성하는수단으로서, 각노드는감시될서브영역또는센서가배치될수도있는서브영역을나타내거나감시될서브영역및센서가배치될수도있는서브영역양자모두를나타내며, 각각의지향된링크는노드쌍들중에서감시관계를나타내며, 노드쌍은센서가배치될수도있는노드들의집합내의제1 노드와, 감시될노드들의집합내의관련된제2 노드를포함하는, 상기특정영역의네트워크표현을생성하는수단 ; 객체검출의확률들과오류경보의확률들을포함하는센서들의속성들로특징화된복수의센서들로서, 상기확률들은다른노드쌍들에대하여상이할수도있는, 상기복수의센서들 ; 감시될각노드들을감시하는센서들의위치의함수로서감시될각노드들에제공되는커버리지레벨에대한감시수행함수들을생성하는수단 ; 사전편찬식의맥시민최적화모델로서센서위치모델을생성하는수단으로서, 상기사전편찬식의맥시민최적화모델의솔루션은사전편찬식으로가장큰정렬된벡터를제공하며, 상기벡터의요소들은증가하는순서로정렬된, 감시되는노드들에제공되는커버리지레벨들이며, 상기사전편찬식의맥시민최적화모델의솔루션은커버리지레벨들을제공하는, 상기센서위치모델을생성하는수단 ; 및비선형정수최적화모델로서사전편찬식의맥시민최적화모델을생성하는수단으로서, 상기비선형정수최적화모델의솔루션은커버리지레벨들을모든노드들에게제공하며, 상기비선형정수최적화모델의솔루션은기존의최적화방법들에의해계산되는, 상기사전편찬식의맥시민최적화모델을생성하는수단을포함하며, 상기복수의센서들은상기사전편찬식의최적화모델의솔루션에따라배치되는것을특징으로하는특정영역에서제한된개수의센서들의배치를결정하는시스템. 청구항 13 특정영역에서제한된개수의센서들의배치를결정하는시스템으로서, 상기센서들의배치는상기영역내에있는모든위치들에게커버리지레벨들을제공하고, 상기시스템은, 노드들및지향된링크들을포함하는특정영역의네트워크표현을생성하는수단으로서, 각노드는감시될서 - 4 -
브영역또는센서가배치될수도있는서브영역을나타내거나감시될서브영역및센서가배치될수도있는서브영역양자모두를나타내며, 각각의지향된링크는노드쌍들중에서감시관계를나타내며, 노드쌍은센서가배치될수도있는노드들의집합내의제1 노드와, 감시될노드들의집합내의관련된제2 노드를포함하는, 상기특정영역의네트워크표현을생성하는수단 ; 감시될각노드들을감시하는센서들의위치의함수로서감시될각노드들에제공되는커버리지레벨에대한감시수행함수들을생성하는수단 ; 사전편찬식의맥시민최적화모델로서센서위치모델을생성하는수단으로서, 상기사전편찬식의맥시민최적화모델의솔루션은사전편찬식으로가장큰정렬된벡터를제공하며, 상기제공된벡터의요소들은증가하는순서로정렬된, 감시되는노드들에제공되는커버리지레벨들이며, 상기사전편찬식의맥시민최적화모델의솔루션은커버리지레벨들을제공하는, 상기센서위치모델을생성하는수단 ; 및실행가능한센서위치모델인비선형정수최적화모델로서사전편찬식의맥시민최적화모델을생성하는수단으로서, 상기비선형정수최적화모델의솔루션은커버리지레벨들을모든노드들에제공하며, 상기비선형정수최적화모델의솔루션은기존의최적화방법들에의해계산되는, 상기사전편찬식의맥시민최적화모델을생성하는수단을포함하며, 상기영역내의감시될필요가있는모든위치들에커버리지레벨들을제공하기위해상기실행가능한센서위치모델의솔루션에따라복수의센서들이배치되는것을특징으로하는특정영역에서제한된개수의센서들의배치를결정하는시스템. 청구항 14 제13항에있어서, 객체함수가사전편찬식으로가장큰벡터를특정하며, 상기특정된벡터의요소들은증가하는순서로정렬된, 감시되는서브영역들에대한커버리지레벨들이며, 제약조건들은배치되는센서들의개수에대한제한을특정하며, 결정변수들은센서배치결정들을나타내는것을특징으로하는특정영역에서제한된개수의센서들의배치를결정하는시스템. 청구항 15 제13항에있어서, 상기노드들은감시될서브영역들을나타내는노드집합 N을포함하며, 노드집합 S는센서들이배치될수있는위치들을나타내며, 집합 S 내의노드로부터집합 N 내의관련된노드까지의링크는집합 S내의노드가노드쌍으로집합 N 내의관련된노드를감시할수있는것을표시하는것을특징으로하는특정영역에서제한된개수의센서들의배치를결정하는시스템. 청구항 16 제15항에있어서, 감시수행함수들은집합 N 내의임의의특정된노드에제공되는커버리지레벨을집합 N 내의상기특정된노드를감시할수있는집합 S 내의노드들에배치된모든센서들의함수로서계산하는것을특징으로하는특정영역에서제한된개수의센서들의배치를결정하는시스템. 청구항 17 제16항에있어서, 상기복수의센서들은객체검출의확률들과오류경보의확률들을포함하는센서들의속성들로특징화되며, 상기확률들은상이한노드쌍들에대해상이할수도있으며, 상기감시수행함수들은상기복수의센서들의속성들을입력으로서이용하는것을특징으로하는특정영역에서제한된개수의센서들의배치를결정하는시스템. 청구항 18 제13항에있어서, - 5 -
비선형정수최적화모델인상기실행가능한센서위치모델은상기센서위치모델로부터생성되며, 상기실행가능한센서위치모델의최적솔루션은감시될모든노드들에커버리지레벨들을제공하는것을특징으로하는특정영역에서제한된개수의센서들의배치를결정하는시스템. 청구항 19 제18항에있어서, 상기실행가능한센서위치모델의최적솔루션은알려진최적화방법들을적용함으로써생성되는것을특징으로하는특정영역에서제한된개수의센서들의배치를결정하는시스템. 청구항 20 노드들의집합 N 내의노드들에커버리지레벨들을제공하는노드들의집합 S 내의제한된개수의센서들의배치를결정하는시스템으로서, 객체검출의확률들과오류경보의확률들을포함하는센서들의속성들로특징화되는복수의센서들로서, 각노드쌍은그것의관련된확률들을가지는, 상기복수의센서들 ; 집합 N 내의관련된노드를감시하는집합 S 내의노드들에배치된센서들의함수로서집합 N 내의노드들의각각에제공된커버리지레벨을위해감시수행함수들을생성하는수단 ; 사전편찬식의맥시민최적화모델로서센서위치모델을생성하는수단으로서, 상기사전편찬식의맥시민최적화모델의솔루션은사전편찬식으로가장큰정렬된벡터를제공하며, 상기제공된벡터의요소들은증가하는순서로정렬된, 집합 N 내의노드들에제공되는커버리지레벨들이며, 상기사전편찬식의맥시민최적화모델의솔루션은커버리지레벨들을집합 N 내의모든노드들에제공하는, 상기센서위치모델을생성하는수단 ; 및실행가능한센서위치모델을생성하는수단으로서, 상기실행가능한센서위치모델의솔루션은집합 N 내의모든노드들에커버리지레벨들을제공하는기존의최적화방법들에의해계산되는, 상기실행가능한센서위치모델을생성하는수단을포함하며, 상기복수의센서들은상기실행가능한센서위치모델의솔루션에따라배치되는것을특징으로하는센서들의배치를결정하는시스템. 청구항 21 제20항에있어서, 적어도하나의센서들의위치는한주기로부터다음주기사이에변경되는것을특징으로하는센서들의배치를결정하는시스템. 청구항 22 제21항에있어서, 각주기에서, 상기실행가능한센서위치모델은가능한센서위치들의수정된집합을이용하여해가구해지는것을특징으로하는센서들의배치를결정하는시스템. 명세서 [0001] 기술분야 본출원은 2007 년 2 월 16 일에제출된미국예비특허출원번호 60/901,909 의우선권을주장하고, 그내용을여 기에원용한다. [0002] 배경기술 본발명은모든위치들에적절한보호를제공하기위하여선택된위치들에서제한된개수의센서들을최적배치 하는것에관한것이다. - 6 -
[0003] [0004] [0005] [0006] [0007] [0008] 발명의상세한설명광범위한영역들에대하여효과적인감시 (surveillance) 를하는센서들의사용은점차보편화되어가고있다. 폭약들, 생물학적약품들, 또는화학물질과같은위험한객체들이배치될수도있는특정영역을고려해보자. 고정된개수의센서들이그영역전체에걸쳐설치되며, 이들각각의센서들은그영역내의하나이상의위치들에대한관찰을제공한다. 이들센서들의관찰들은하나이상의관찰된위치에서객체가실질적으로존재하는지의여부를평가하기위하여데이터융합프로세스를통하여결합된다. 배치될수있는센서들의개수가제한되기때문에, 이들센서들에대한최적의위치들을결정하는것이매우중요하다. 일부애플리케이션들에서는많은센서들이설치될수도있으나, 이들센서들의제한된수량만이동시에활성화될수있다. 센서들은또한침입검출을위해사용된다. 침입에대한방어는국가들간의국경, 기름과가스파이프라인, 핵원자로와같은전략시설들, 산업단지, 군사기지들등과같은큰영역을보호하기위해필요할수도있다. 부언하면, 센서들을최적으로배치하는것은상이한방향들로부터보호된영역에접근할수도있는침입자에대한적절한보호를달성하기위하여극히중요하다. 관련된주제는비상룸, 소방서및경찰서와같은비상시설의최적의위치결정에대하여초점이맞추어져있다. 각노드가이웃을나타내는예컨대, 100 100미터치수의정사각형을나타내는네트워크에의해영역을나타내는것은편리하다. 한쌍의노드를서로연결하는링크는한노드로부터다른노드로가능한움직임을나타내며, 링크메트릭 (metric) 은말단노드들간의거리 ( 또는이동시간 ) 를나타낸다. 전형적인문제는임의의노드에서가장가까운시설까지거리 ( 또는이동시간 ) 가최소가되도록이들노드들의부분집합 (subset) 에제한된개수의비상시설을배치하는것이다. 이것은문헌에잘알려진문제이며, 네트워크미니맥스위치결정문제 (network minimax location problem) 또는정점중심문제 (vertex center problem) 라고불린다. 집합커버링문제 (set covering problem) 로서문헌에알려진관련된문제는각각의노드가최근접시설로부터특정거리 ( 또는이동시간 ) 내에있도록노드들의부분집합에설비를설치하는비용을최소화한다. L. V. Green 과 P. J. Kolesar, " 경영과학으로긴급사태응답성을개선하는것 (Improving Emergency Responsiveness with Management Science)", Management Science, 50, 1001-1014, 2004년문헌은최신의긴급사태응답모델을제시한다. 네트워크미니맥스위치결정문제하에서비상시설의최적위치들은가장좋은가능한서비스를최악의경우가없는위치에제공하는많은솔루션 (solution) 들이있을수도있기때문에고유하지않다. 그러므로, 모든미니맥스솔루션들중에서어느솔루션이선택되어야하는지를알아내는것은흥미로운일일것이다. W. Ogryczak, " 위치결정문제에대한사전편찬식의미니맥스접근법에대하여 (On the Lexicographic Minimax Approach to Location Problems)", European Journal of Operational Research, 100, 566-585, 1997년의문헌은위치결정문제에대한사전편찬식의미니맥스솔루션을발견하기위한알고리즘을제시한다. 미니맥스네트워크위치결정문제에서와같이, 임의의특정위치는단일시설구체적으로는그위치에가장가까운시설에의해서비스된다. 사전편찬식의미니맥스솔루션은최악의경우로부터최선의경우까지 ( 최근접시설로부터의거리또는이동시간의관점에서 ) 위치들에게제공되는서비스를순서화할때, 결과적으로정렬된벡터는사전편찬식으로가장작은가능한정렬된벡터라는점에있어서, 최선의미니맥스솔루션이다. 그러한솔루션은공정한 (equitable) 솔루션으로불린다. K. Chakrabarty, S.S.Iyengar, H.Qi 그리고 E.Cho, " 분산된센서네트워크에서의감시와표적위치를위한그리드커버리지 (Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks)", IEEE Transactions on Computers, 51, 1448-1453, 2002년문헌은각노드가특정된개수의센서들로부터특정된거리 ( 또는이동시간 ) 내에위치하도록, 노드들의부분집합에서센서설치비용을최소화하는집합커버링문제로서센서위치문제를공식화한다. 본발명은사전편찬식맥시민개체 (lexicographic maxmin objective) 를이용하여모든위치들의공정한커버리지를달성하기위해제한된개수의센서를배치하는데중점을두고있다. 임의의특정위치에제공되는커버리지레벨이위치를감시하는다중센서들의위치와센서들의속성에의존할수도있다. 이것은 W. Ogryczak에의한상기문헌의중요확장이며, 거기에사용된방법은본발명에의해제기된문제들을해결하기위해확장될수없다. H. Luss, " 공정한리소스할당문제에대하여 (On Equitable Resource Allocation Problems): 사전편찬식미니맥스접근 (A Lexicographic Minimax Approach)", Operations Research, 47, 361-378, 1999 문헌은다양한공정한리소스할당모델들과해결방법들을제시한다. 그러나, 이들중어느것도본발명에적용될수없다. - 7 -
발명의요약 [0009] [0010] [0011] 본발명은감시 (monitor) 될필요가있는모든위치들에대하여공정한커버리지레벨들을달성하기위해선택된위치들에서제한된개수의센서들을배치하는데초점을두고있다. 감시하에있는영역은네트워크로서표현되며, 노드는위치를표시하고, 연결하는링크는감시관계들을나타낸다. 노드 j에있는센서를고려하자. 노드 j를감시하는것에부가하여, 노드 j로부터노드 i까지의링크는노드 j에있는센서가노드 i를또한감시할수있다는것을의미한다. 임의의특정한위치에제공된커버리지레벨은그위치를감시하는모든센서들과그센서들의속성에의존한다. 센서의속성은표적이특정위치에존재할때그특정위치에서표적을검출할확률 (probability) 과, 표적이그곳에존재하지않을때동일한위치에서표적을잘못검출할확률을포함한다. 이확률은각 (i,j) 노드쌍 (node-pair) 에대하여상이할수도있다. 센서들의위치들이특정된다고가정하자. 이위치들이주어지면, 각위치에제공된커버리지레벨이계산된다. 각위치들에제공된커버리지레벨들의벡터를고려하기로한다. 이위치들에서이벡터의요소들 ( 즉, 커버리지레벨들 ) 은증가하는순서 (nondecreasing order) 로정렬된다. 모든위치에대한공정한커버리지레벨들은커버리지레벨들의사전편찬식으로가장큰그러한정렬된벡터로서정의된다. 모든위치에대해공정한커버리지레벨이달성되도록본발명은제한된개수의센서들의최적의위치들을결정한다. 본발명은사전편찬식의맥시민최적화한모델 (lexicographic maximin optimization model ) 로서공정한센서위치모델을생성하고, 상기사전편찬식의맥시민최적화한모델의솔루션은모든위치에공정한커버리지레벨을제공한다. 현재의최신최적화솔루션수단은상기한사전편찬식의맥시민최적화모델을직접해결할수없다. 본발명은비선형정수최적화모델을생성하며, 이모델의솔루션은또한모든위치에공정한또는거의공정한커버리지레벨들을제공한다. 상기비선형정수최적화모델의솔루션은모의어닐링 (simulated annealing) 과타부서치 (tabu search) 를포함하는다이내믹프로그래밍과다양한메타-발견적지도법 (meta-heuristics) 과같은알려진최적화방법들을적용하여얻어질수있다. 센서위치모델은정적인 ( 한번 ) 상황또는동적인 ( 다중기간 ) 상황에서사용되는시스템의일부일수있다. 동적인상황에, 적에의한위치에대한학습을방지하기위해센서위치들은주기적으로변경된다. 본발명은다음설명이첨부도면과관련하여읽힐때명료하게이해될것이다. [0015] [0016] 실시예도면들과특히도 1을참조하면, 감시하에있는영역을나타내는네트워크 (100) 의예가도시되어있다. 영역은 6개의노드 (101-106) 에의해표시된다. 블랙노드 (101, 104, 106) 에의해표시된것과같이 3개의센서가위치한다. 센서들의최적의위치는본발명에의한교시에따라결정될것이다. 지향된링크들 (107 내지 115) 은감시관계 (surveillance relation) 를나타낸다. 예를들면, 107은노드 (101) 로부터노드 (102)( 지향된 (directed) 굵은선링크에의해표시됨 ) 까지그리고노드 (102) 로부터노드 (101)( 지향된점선링크에의해표시됨 ) 까지의감시관계를표시한다. 지향된굵은선링크는노드 (101) 가노드 (102) 를감시하는센서를가진다는것을나타낸다. 지향된점선링크는센서가노드 (102) 에위치한다면, 노드 (102) 가노드 (101) 를감시할수있다는것을나타낸다. 예컨대, 노드 (101) 에위치한센서는노드 (101, 102, 105, 106) 를감시하고, 노드 (101) 는노드 (101) ( 센서는그것이위치한노드를항상감시한다.) 와노드 (106) 에있는센서에의해감시된다는것을주목해야한다. 다음표기법이사용되어진다. [0017] N = 감시될필요가있는노드의집합. N에서의노드는 i에의해색인된다. 도 1에서 N = {101, 102, 103, 104, 105, 106}. 실제적인상황에서, N은클수도있으며, 여기서그특정값은노드에의해표현된영역과영역사이즈에의존한다. 예를들면, 만일감시하에있는영역이 10km x 10km의정사각형이고, 각노드가 100m x 100m의정사각형을나타낸다면, N = 10,000이된다. [0018] S= 센서들이위치할수있는노드들의집합. S 에있는노드들은 j 에의해색인된다. 예컨대, 네트워크 (100) 에서 S = N 이라고가정될지라도, N 과 S 집합들은동일하지않을수도있다. - 8 -
[0019] J(i)= 노드 i 를감시할수있는 S 에서노드들의부분집합. 집합 J(i) 가노드 i 플러스로지향된링크를가지는 모든노드를포함하며, 만약 i S 인경우에는노드 i 자체가된다. 예컨대, 도 1 에서, J(101) = {101, 102, 105, 106} 그리고 J(102) = {101, 102, 103, 106} 이다. [0020] 본발명은가용센서의개수가제한될때최적의위치를결정하는방법을제공한다. 비록센서들이동일한것으 로가정될지라도노드 j 에위치한센서가노드 i 에제공하는커버리지레벨은센서속성과특정노드들 i 와 j 에 의존한다. 센서속성들은전형적으로다음의확률들에의해특정된다. [0021] p ij = 노드 i 에객체가있는경우, 노드 j 에있는센서가노드 i 에있는객체를검출할확률. [0022] q ij = 노드 i 에객체가없는경우, 노드 j 에있는센서가노드 i 에있는객체를잘못검출할확률 ( 오류경보 ). 우리는 q ij < p ij 로가정한다. [0023] 위치 i 에제공되는커버리지레벨은집합 J(i) 에있는노드들에위치한모든센서들에기초하여결정된다. 센서 위치문제에대한최적솔루션은 N 에서모든노드들에공정한커버리지를제공하는솔루션일것이다. 공정한커 버리지솔루션은나중에정의될것이다. [0024] 도 2에서센서위치모델의다른네트워크 (200) 표현의예가도시되어있으며, 여기서모델은상호간의네트워크로도시되어있다. 노드 (201-206) 는센서가위치할수있는노드 S의집합이다. 이노드들은네트워크 (100) 에서노드 (101-106) 에대응한다. 센서들은네트워크 (200) 에서노드 (201, 204, 206)( 블랙노드 ) 에위치하며, 네트워크 (100) 에서노드 (101, 104, 106) 에있는센서위치와대응한다. 노드 (201-206) 의각각은네트워크 (200) 의우측에복제된다. 따라서, 노드 (207) 는노드 (201) 의복제이며, 노드 (208) 는노드 (202) 의복제이다. 노드 (207-212) 는감시될필요가있는노드들 N의집합을나타낸다. 이예에서, 집합들 N과 S는동일한노드들 ( 네트워크 (100) 에서이루어진것과같은가정 ) 을포함할지라도, 이것은그경우일필요는없다. S와 N이동일하지않다면, S에서의일부노드들은 N에서복제노드들을갖지않을수도있으며, N에서의일부노드들은 S에서의대응된노드를갖지않을수도있다. 네트워크 (200) 의링크는감시관계를표시한다. 그러므로, 예컨대, 노드 (201) 는노드 (207, 208, 211, 212) 에대한각각의링크들 (213a-d) 을가지며, 노드 (202) 는노드 (207, 208, 209, 212) 에대한각각의링크들 (216a-d) 을가진다. 이링크들은집합 S의노드로부터집합 N에있는그것의복제노드까지의링크를추가하여네트워크 (100) 에서링크들에대한명백한일대일대응을가진다. 굵은선링크들은하나의센서를갖는한노드와 N에있는관련노드들을연결시키고, 점선링크들은센서가없는한노드와 N에있는관련노드들을연결시킨다는것을주목해야한다. 집합들 J(i) 는네트워크 (200) 로부터쉽게유도되며, 예를들면 J(207) = {201, 202, 205, 206} 이된다. 그러므로, 이예에서노드 (207) 는노드 (201, 206) 에있는 2개의센서에의해감시된다. 노드 (101) 가노드 (101, 106) 에있는 2개의센서에의해감시되는네트워크 (100) 에서 J(207) 가 J(101) = {101, 102, 105, 106} 에유일하게대응한다는것에주목해야한다. [0025] 도 3 은모든위치에공정한커버리지레벨들을제공하는센서위치를결정하는방법 (300) 의흐름도를도시한다. [0026] 방법에대한입력준비 ( 단계 301 과 302) [0027] 도 1, 2 을참조하여상술된바와같이특정영역의네트워크표현이생성된다 (301). 네트워크에서노드들의개 수는영역크기와단일노드에의해표시되는영역에의존한다. 요구되는정확도는특정애플리케이션들에의존 한다. 감시의품질에영향을미칠수있는센서들의속성의특징화가명시된다 (302). 이들속성은확률 p ij 와 q ij 를포함할수도있지만, 이에한정되지는않는다. 모든센서들이동일타입이라고가정될지라도, 이들확률들 은센서위치와감시되는위치에의존한다는점에주목해야한다. 상이한센서위치들로부터의상이한확률들은 - 9 -
이들위치들로부터노드 i 까지의상이한거리들또는이들위치와노드 i 간의일부장애물에기인할수도있다. 네트워크표현 ( 도 1 의네트워크 (100) 또는도 2 의네트워크 (200)) 과센서들의속성은센서위치모델에대한주 된입력들이다. [0028] 감시수행함수들의생성 ( 단계 303) [0029] [0030] 이방법의목적은제한된개수의가용센서들에대한최적의위치를결정하기위한것이다. x j = 결정변수. 만일센서가노드 j 에위치하면 x j = 1 이고, 그렇지않으면 x j = 0 이된다. x 는모든결정변 수들 x j 의벡터, j S 로하자. [0031] f i (x) = 노드 i 에대한감시수행함수이며, i N 이다. 벡터 x 의특정값에대하여, 이함수의결과값은또한 노드 i 에제공되는커버리지레벨로서불리운다. f i (x) 에영향을미치는유일한결정변수 x j 는 j J(i) 에대한 결정변수임을주목하자. [0032] [0033] [0034] 가능한감시수행함수들에대하여아래 2가지예들이제공된다. 본발명은이들특정수행함수들에한정되지않는다. 예 1 모든확률들이 q ij =0 및 0<p ij <1임을가정하자. 그러면, x의함수로서, 노드 i에대한감시수행함수는노드 i 에위치한객체가적어도하나의센서에의해검출될것이라는확률에대해설정될수있다. 이것은다음수학 식 1 로나타낼수있다. 수학식 1 [0035] [0036] [0037] 단, 특정된 x 에대한 f i (x) 의값은노드 i 에제공되는커버리지레벨로서불리운다 ; f i (x) 의값이보다클수록노드 i 에제공되는커버리지레벨은더좋아진다. 수학식 1 은또한 질수있다. 로쓰여 [0038] [0039] 예 2 모든확률 q ij 는 0<q ij <p ij 를만족한다고가정한다. 그러면, 위치 i 에서객체를검출하기위한위치 j 에있는센 서의효율성은비율 (1-p ij )/(1-q ij ) 에의해추정될수있다 ; 이비율이작을수록센서는더효율적이다. 명백히, q ij 와 p ij 가거의동일하다면, 노드 i 를감시하기위해노드 j 에서센서를배치하는것은그센서로부터 수집된정보가어떠한의미가있는정보도제공하지않을것이기때문에소용없다. 드 i 에서의객체가있는경우, 노드 i 를감시하는어떠한센서들도노드 i 에있는객체를검출하지못할조건부 는노 의확률이며, 는노드 i에서의객체가없는경우, 노드 i를감시하는어떠한센서들도노드 i에서객체를잘못검출하지않을조건부의확률임을주목해야한다. 수학식 1과유사하게, 1 마이너스이들조건부확률의비는다음수학식 2와같은감시수행함수를형성하기위해선택될수있다. - 10 -
수학식 2 [0040] [0041] 단, [0042] [0043] 수학식 2 는또한과같이쓰여질수있다. 다양한다른감시함수들이사용될수있다. 특정 i 를고려하고, x 1 과 x 2 를 2 개의벡터로하고, 단모든 j J(i) 에대하여적어도하나의 j J(i) 에대해이라고하자. 감시수행함수들은다음특징을 만족해야한다 : [0044] [0045] [0046] [0047] 속성 (i) 함수 f i (x) 는변수 j J(i), 즉 f i (x 1 )<f i (x 2 ) 와함께증가한다. 속성 (ii) x 1 및 x 2 에서 0이되는몇몇변수 j J(i) 가양쪽 x 1 및 x 2 에서 1로설정되며, 결과적으로벡터들 x 1+ 및 x 2+ 를 각각초래함을가정하자. 그러면, f i (x 1+ )-f i (x 1 ) f i (x 2+ )f i (x 2 ); 즉 f i (x) 는 j J(i) 에대한 x j 의정수값들에대 해오목하다. 속성 (i) 및속성 (ii) 는수학식 1 및수학식 2 에대해유지된다는것에주목해야한다. [0048] [0049] [0050] [0051] 공정한센서위치모델-ESLM(Equitable Sensor Location Model) 의생성 ( 단계 304) 모델은 i N에대한감시수행함수 f i (x) 를이용하여공식화된다. 다음과같이설정한다. f (n) (x)= 증가하는순서로소팅된모든 f i (x) 들의벡터. 즉, 수학식 3a [0052] [0053] 수학식 3a 에서수학식 3b 의조건을만족한다. 수학식 3b [0054] [0055] P= 가용한센서의개수로서,. 이들센서들은노드들 S 의집합에있는노드의부분집합에노드당많아야 하나의센서가배치된다. 로고려할필요가없다. 인경우는센서가집합 S 에있는각노드에위치되는사소한문제가초래되므 [0056] 공정한솔루션은사전편찬식의가장큰벡터 f (n) (x) 를제공하는솔루션이다. ESLM 이라고불리는공정한센서 위치모델은사전편찬식의맥시민최적화모델로서공식화된다. - 11 -
[0057] ESLM 수학식 4a [0058] [0059] 단, 다음수학식들을만족한다. 수학식 4b [0060] 수학식 4c [0061] 수학식 4d [0062] 수학식 4e [0063] [0064] 객체함수인수학식 4a 는사전편찬식의가장큰벡터 V f 를찾는다. 여기서, 스테이트먼트수학식 4b 및 4c 에 의해이벡터는감소되지않은순서로소팅된모든감시수행함수 f i (x) 를포함한다. 제약조건수학식 4d 및 4e 는배치된센서의개수를 P 로제한하며, 집합 S 의각노드에는많아야한개의센서가배치된다. 위에서논의 된바와같이, 감시수행함수의예는수학식 1, 2 로주어진다. ESLM 은이함수들이증가하는한 ( 단계 303 에서 속성 (i)), 감시수행함수들을위해사용되는특정형식과는상관없다. [0065] 실행가능한공정한센서위치모델의생성 ( 단계 305) [0066] [0067] ESLM 이공정한솔루션을계산하기위해완전하고정확한공식을제공할지라도, 이공식은알려진최적화방법 에의해직접적으로해가구해질수없다. 위에서논의한바와같이, i N 에대한감시수행함수 f i (x) 의각각이증가하는함수이고 ( 단계 303 에서속성 (i) 과속성 (ii) 에의해정의된바와같이 ) j J(i) 에대한 x j 의정수값에대하여오목하다라고가정되기때문에, 공정한솔루션 ( 사전편찬식의맥시민솔루션 ) 은관련된비선형정수최적화모델을푸는것에의해얻어질것이다. 수학식 1 및수학식 2에서정의된감시수행함수들은단지설명을위한목적을위해주어진다 ; 요구되는모든것은함수들이단계 303에서정의된속성 (i) 와 (ii) 를만족시키는것이다. K는임의로큰매개변수인것으로하자. 다음비선형정수최적화모델의솔루션은 ESLM에의해공식화된것과같이공정한위치센서모델에대한공정한솔루션을제공할것이다. 새로운모델은실행가능한공정한센서위치모델 (ESLM-EX) 로서언급된다. [0068] ESLM-EX - 12 -
수학식 5a [0069] [0070] 수학식 5a 는수학식 5b 와 5c 를만족시킨다. 수학식 5b [0071] [0072] [0073] 수학식 5c x j = 0, 1, j S 단, ε는객체함수수학식 5a에서무한항들을피하기위하여계산적목적을위해도입된임의적으로작은매개변수이다. K가매우클때, ESLP-EX가공정한솔루션또는동등하게사전편찬식의맥시민솔루션을제공할것이다. f 1 (x) < f 2 (x) 라고가정하자. 그러면, 단계 303에서의속성 (i) 은큰 K에대하여객체함수인수학식 5a 에서 i=1에대한항이객체함수인수학식 5a에서 i=2에대한항보다현저히크다는것을암시한다. 이모든요지는 N에있는모든노드쌍에적용된다. 단계 303에서의속성 (ii) 은객체함수인수학식 5a에서 i번째항에서의향상은 x 2 가 x 2+ 까지증가되었을때실현된향상보다 x l 이 x l+ 로증가되었을때에더크다는것을암시한다. 따라서, 충분히큰값 K에대하여 ESLM-EX의최적의솔루션은증가하는순서로소팅된수행함수값들의사전편찬식으로가장큰가능한벡터일것이다. K의심지어작은값 ( 예를들면, K 4) 에서도 ESLM-EX의솔루션은근접된공정한솔루션을제공할것으로예상된다는점을주목해야한다. K의적절한값은실험을통하여결정될수있다. [0074] 공정한솔루션의계산 ( 단계 306) [0075] 본발명은모델 ESLM-EX를생성하며, 그모델의솔루션은공정한센서위치모델에대한공정한솔루션을제공한다. 여기서, 솔루션은다양한기존의최신의최적화방법들에의해계산될수있다. 이방법들은모의어닐링과타부서치와같은동적프로그래밍과메타-발견적지도법을포함하지만, 이에한정되지는않는다. T. Ibaraki 및 N. Katoh의책은, " 리소스할당문제 : 알고리즘적접근 (Resource Allocation Problems:Algorithmic Approaches)", MIT Press, Cambridge, Massachusetts, 1988의문헌은섹션 3.2에서 ESLM-EX의해를구하는동적프로그래밍알고리즘을제공한다. C. R. Reeves ( 편집자 ), " 조합의문제들을위한현대의발견적지도법기술 (Modern Heuristic Techniques for Combinatorial Problems) Halsted Press an imprint of John Wiley, New York, 1993년, 은그의책지도서들에서모의어닐링및타부서치를포함하는다양한메타-발견적지도법에대하여제시하고있다. [0076] ESLM-EX는정적 ( 단일주기 ) 이거나동적 ( 다중주기 ) 환경에서사용될수도있다. 예를들면, 데이터가 15분마다모든센서로부터수집되고, 데이터분석이객체가어떠한위치에서도출현하지않는다는것을반복적으로제안하는동적환경을고려해야한다. 더욱이, 얼마지난후, 예컨대, 하루지난후에, 적이어디에센서가위치하는지습득하지못하도록센서위치의일부를변경하는것이바람직하다. 예컨대, 이것은가능한센서위치의집합 S를변경하고, ESLM-EX의해를구함으로써이루어질수있다. 집합 S에서변경들은어떤랜덤화된선택계획을이용하여선택될수도있다. 일부애플리케이션들에서, 센서들은 S에있는모든노드에서설치되며, 하지만, 모든시점에서단지이들센서들의는동작의제약조건에기인하여할성화된다. 그러한애플리케이션들에서, 할성화된센서들의위치들은 ESLM-EX의해를구함으로써주기적으로변경될것이며, 집합 S는어떤랜덤화된선택계획을사용하여변경된다. - 13 -
[0077] 마지막으로, 데이터분석이객체들이그위치들의부분집합에서, 일명노드들 N present 의부분집합에서, 존재할 우려가있음을암시하고있다고가정하자. 그러면, ESLM-EX 는새로운네트워크의각노드가원래의네트워크에 서보다훨씬더작은영역을표시하도록 N present 에서노드들의급격한증가를포함하는새로운네트워크표현에적용될수있다. 그후, ESLM-EX는혐의가있는영역의보다정확한감시를수집하기위해, 새로운네트워크에의해표시된영역에서제한된개수의제2 타입센서예컨대, 모바일센서들을배치할공정한솔루션을발견할것이다. [0078] [0079] [0080] 상술된알고리즘과모델링은연산장치와같은명령어실행시스템, 장치또는디바이스에서수행될수있다. 알고리즘그자체는컴퓨터와같은명령어실행시스템, 장치또는디바이스에의한사용또는그것들과관련된사용을위해프로그램을포함또는저장, 통신, 전파, 전송할수있는어떠한수단도될수있는컴퓨터로판독가능한매체상에포함될수도있다. 모든위치에대하여공정한커버리지레벨을달성하기위해, 선택된위치들에서제한된개수의센서들의최적의배치를위한방법을기술하고설명하였으나, 그것은단지본원에첨부된청구항들의범위에의해제한되는본발명의넓은교시와범위로부터일탈함이없이변형과변경이가능함은당업자에게명백할것이다. [0012] [0013] [0014] 도면의간단한설명도 1은센서위치모델의네트워크표현을도시한다. 도 2는센서위치모델의상호간의네트워크표현을도시한다. 도 3은모든위치에공정한커버리지레벨을제공하는센서위치를결정하는방법의흐름도이다. 도면 도면 1-14 -
도면 2 도면 3-15 -