OBJECT TRACKING APPARATUS AND METHOD, AND SENSOR POSITION DESIGNATING METHOD

도 1은 본 발명의 일 실시예에 따른 심볼릭 공간을 나타내는 도면,

도 2는 본 발명의 일 실시예에 따른 심볼릭 공간에서 RFID 리더기를 설치하는 방법과 관련된 도면,

도 3은 도 2의 공간에 대응되는 접근성 그래프,

도 4는 첫 번째 조건을 위반하여 추적가능한 심볼릭 공간이 될 수 없는 접근성 그래프,

도 5는 두 번째 조건을 위반하여 추적가능한 심볼릭 공간이 될 수 없는 접근성 그래프,

도 6은 본 발명의 일 실시예에 따른 추적가능한 심볼릭 공간을 구현하기 위해 센서의 위치를 지정하는 위치 지정 서버의 블록도,

도 7은 본 발명의 일 실시예에 따른 심볼릭 공간이 추적 가능한 공간이 되도록 센서의 위치를 지정하는 방법과 관련된 흐름도,

도 8은 본 발명의 일 실시예에 따른 추적가능한 심볼릭 공간에서 객체를 추적하는 객체 추적 장치,

도 9는 본 발명의 일 실시예에 따른 추적가능한 심볼릭 공간에서 객체를 추적하는 방법을 설명하는 흐름도,

도 10은 제1 저장부에 저장되어 있는 태그와 리더기 정보,

도 11은 제2 저장부에 저장되어 있는 인접성 그래프,

도 12는 도 11의 인접성 그래프에 대응되는 공간과 관련된 도면이다

[실시예]

이하에서는 도면을 참조하여 본 발명을 보다 상세하게 설명한다.

본 발명에 적용되는 심볼릭 공간이라 함은 공간의 위치를 좌표 정보가 아닌 기호 정보로 나타내는 공간을 의미한다. 주소로 만들어진 공간 및 방 번호로 구별되는 공간은 심볼릭 공간에 해당한다. 심볼릭 공간에서 객체가 이동할 때 관리자는 객체가 특정 공간에 있는지 여부에 관하여 관심이 있을 뿐 객체의 정확한 좌표 정보에 대해서 관심이 없다. 이와 같이 관리자의 관심에 대응하여 객체를 추적하기 위해 센서를 적절히 설치하는 방법 및 상기한 센서들이 설치된 공간에서 객체를 추적하는 방법이 필요하다.

상기한 센서 중 일 예가 RFID 리더기이지만 이에 한정되지 않고 객체의 위치를 추적할 수 있으면 어떠한 센서라도 무방하다. 본 실시예에서는 설명의 편의를 도모하기 위해 센서로서 RFID 리더기와 RFID 태그에 관하여 설명한다.

도 1은 본 발명의 일 실시예에 따른 심볼릭 공간을 나타내는 도면이다. 도 1에 도시된 바와 같이, 심볼릭 공간에서 객체의 위치를 파악하기 위해 RFID 리더기의 커버리지를 그리드의 크기로 정하고, 공간을 리드로 분할한 뒤 상기한 그리드의 중앙에 RFID 리더기를 설치하는 방법이 있다. 그러나, 이와 같이 RFID 리더기를 설치하게 되면 리더기의 개수가 많이 필요하게 되어 비용 낭비가 발생하게 된다.

도 2는 본 발명의 일 실시예에 따른 심볼릭 공간에서 RFID 리더기를 설치하는 방법과 관련된 도면이다. 도 2에 도시된 바와 같이, 공간과 공간을 연결하는 통로 양단에 RFID 리더기를 설치하고, 객체가 특정 공간에서 다른 공간으로 진입하게 되면, 적어도 두 개의 RFID 리더기가 이를 인식하게 된다. 인식된 RFID 리더기의 순서에 따라 객체의 이동 경로를 파악할 수 있고, 현재 객체의 위치를 파악할 수 있다.

설명의 편의를 도모하기 위해 공간 중 RFID 리더기를 이용하여 객체를 감지할 수 있는 영역을 화이트 셀(White Cell:Wi)이라고 칭하고, RFID 리더기를 이용하여 객체를 감지할 수 없는 영역을 블랙 셀(Black Cell:Bj)이라고 칭한다. 결국 화이트 셀은 RFID 리더기의 커버리지 영역인 것이고, 블랙 셀은 RFID 리더기의 커버리지 외 영역인 것이다.

도 2에 도시된 바와 같이, RFID 리더기의 위치를 중심으로 하여 객체를 감지할 수 있는 영역을 화이트 셀(White Cell:Wi, 여기서 i는 1 내지 8중 어느 하나이다)로 표현하고, 그렇지 않은 영역을 모두 블랙 셀(Black Cell:Bj, 여기서 j는 1 내지 4 중 어느 하나이다)로 표현한다. 이와 같이 블랙 셀(Black Cell)과 화이트 셀(White Cell)이 실내에 적절히 배치되면 객체의 위치를 용이하게 파악할 수 있다.

한편, 심볼릭 공간에서 서브 공간들의 관계를 용이하게 파악하기 위해 심볼릭 공간을 접근성 그래프(Accessibility Graph)로 변환시킬 수 있다. 접근성 그래프는 노드와 링크를 구성요소로 하며, 노드는 블랙 셀에 대응되는 블랙 노드, 화이트 셀에 대응되는 화이트 노드가 있으며, 링크는 서브 공간과 서브 공간을 연결하는 통로에 대응된다.

도 3은 도 2의 공간에 대응되는 접근성 그래프이다. 도 3에 도시된 접근성 그래프를 이용하면 관측자는 공간의 기하학적 구조를 정확히 알고 있지 않더라도 객체의 위치를 용이하게 파악할 수 있다.

한편, RFID 태그를 소지한 객체가 RFID 리더기의 커버리지내에 있으면 객체의 위치는 그 커버리지의 영역이 된다. 반면에 RFID 리더기가 커버리지를 벗어나면 객체의 위치를 파악할 수 없다. 즉, RFID 리더기로 측정된 값을 함수 p로 표현하면 하기 수학식 1과 같다.

수학식 1

수학식 1은 p(m, t)의 값이 화이트 셀이면 객체 m이 시간 t에 화이트 셀에 있다는 것을 의미하고, p(m, t)이 NULL이라면 객체 m이 시간 t에 화이트 셀에 존재하지 않아 추적의 과정이 추가로 필요하다는 것을 의미한다.

즉, 시간 t에서 객체 m의 위치 pos (m,t)는 하기 수학식 2와 같다.

수학식 2

수학식 2와 같이 시간 t에서 객체 m의 위치 pos (m,t) 가 화이트 셀 에 존재하지 않는 경우, 별도의 추적이 필요하다.

도 2 및 도 3을 참조하여 객체의 이동 경로를 추적하면 다음과 같다. 예를 들어, 만일 t1<t2<t3의 시간에 대하여 p(m, t1) = w1이고 p(m, t3)=w3이면 p(m, t2)=NULL이라고 한다면 pos(m, t2)= =b1일 수밖에 없다. 이 예에서와 같이 특정한 조건에서는 위치를 결정적으로 추정할 수 있다. 반면 t3<t4<t5의 시간에서 p(m,t3)=NULL, 이고 p(m,t5)=NULL 이라면 p(m, t4)를 결정적으로 추적하는 것은 불가능하다.

따라서, 객체를 용이하게 추적하기 위해 RFID 리더기를 적절히 배치할 필요가 있으며, 결정적으로 객체의 위치를 추정할 수 있으면 이러한 공간을 추적가능한 심볼릭 공간(Trackable Symbolic Space:TSS)라고 칭한다.

추적가능한 심볼릭 공간이 성립되기 위해서는 하기 두 가지 조건을 만족하여야 한다.

제1 조건:

화이트 셀(또는 화이트 노드)에 이웃하는 블랙 셀(또는 블랙 노드)이 하나 이하여야 한다.

제2 조건:

블랙 셀(또는 블랙 노드)의 이웃 셀(또는 노드)은 반드시 화이트 셀(또는 화이트 노드)이여야 한다.

도 4는 첫 번째 조건을 위반하여 TTS가 될 수 없는 접근성 그래프이고, 도 5는 두 번째 조건을 위반하여 TSS가 될 수 없는 접근성 그래프이다. 도 4에서 p(m, t1) = w3이고, p(m, t2)= NULL일 때, t3시간에서 객체의 위치는 b1 혹은 b4일 수 있다. 따라서 화이트 노드에 이웃한 블랙 노드가 둘 이상일 경우 이동객체의 위치를 결정할 수 없다. 도 5에서 p(m, t1) = w2이고, p(m, t2) = NULL일 때, t3에서 이동객체의 위치는 b3이거나 혹은 b4일 수 있다. 따라서, 블랙 노드의 이웃 노드가 화이트 노드가 아닌 경우 이동 객체의 위치를 결정할 수 없다.

결국, 공간에서 객체 추적을 하기 위해 접근성 그래프가 TSS가 되어야 한다. 이러한 TSS를 만들기 위해서 많은 수의 화이트 셀을 설치하여야 한다. 그러나 화이트 셀은 하나의 RFID 리더기에 해당된다. 따라서, 경제적인 측면에서 정확도를 유지하면서 화이트 셀의 수를 줄이는 것은 중요하다. 즉, 주어진 블랙 셀의 집합에 대하여 최소의 화이트 셀을 배치하여 TSS로 만든다는 것은 유용한 작업이다.

도 6은 본 발명의 일 실시예에 따른 추적가능한 심볼릭 공간을 구현하기 위해 센서의 위치를 지정하는 위치 지정 서버의 블록도이다.

도 6에 도시된 바와 같이, 제1 인터페이스(610)를 통해 심볼릭 공간에 대한 정보가 입력되면, 공간 구분부(620)는 심볼릭 공간에서 공간의 성격에 따라 복수 개의 기본 공간으로 구분한다. 기본 공간은 방, 통로 및 센서 영역이 있을 수 있다. 서브 공간은 벽 등으로 둘러싸여 있어 하나의 독립된 공간으로 인식되는 공간이며, 통로는 서브 공간과 서브 공간을 연결시켜 주는 공간으로서, RFID 리더기의 커버리지에 포함되는 공간이다. 센서 영역은 심볼릭 공간에 기설치되어 있는 센서가 설치되어 있는 공간으로서, 엄밀한 의미로 센서의 커버리지 영역을 의미한다.

접근성 그래프 생성부(630)는 공간 구분부(620)에서 구분되는 기초 공간을 기초로 접근성 그래프를 생성한다. 구체적으로, 서브 공간을 블랙 노드, 통로를 노드와 노드를 연결하는 링크 및 센서 영역을 화이트 노드로 하여 접근성 그래프를 생성한다.

센서 지정부(640)는 접근성 그래프 생성부(630)에서 생성된 접근성 그래프를 이용하여 심볼릭 공간이 추적 가능한 공간이 되도록 하기 위해 센서의 위치를 지정하여 준다.

도 7은 본 발명의 일 실시예에 따른 심볼릭 공간이 추적 가능한 공간이 되도록 센서의 위치를 지정하는 방법과 관련된 흐름도이다.

접근성 그래프 생성부(630)가 접근성 그래프를 생성하면(S710), 센서 지정부(640)는 접근성 그래프에서 화이트 노드에 이웃하는 블랙 노드가 두 개 이상인지 판단한다(S720). 화이트 노드에 이웃하는 블랙 노드가 두 개 이상이라는 의미는 서브 공간과 서브 공간 사이에 센서가 하나가 설치되어 있다는 것을 의미한다. 이는 센서 영역에 있던 객체가 서브 공간으로 이동하였을 때 어느 서브 공간에 있는지 확인할 수 없는 경우로서, TSS의 제1 조건을 위반한 것이다.

센서 지정부(640)는 화이트 노드에 이웃하는 블랙 노드가 두 개 이상인 경우(S720-Y), 화이트 노드와 블랙 노드 사이에 화이트 노드를 삽입한다(S730). 즉, 서브 공간과 서브 공간 사이에 기존재하는 센서 영역와 일부 중첩되도록 센서를 하나 더 설치하는 것을 의미한다.

한편, 센서 지정부(640)는 인접하는 블랙 노드가 있는지 판단한다(S740). 인접하는 블랙 노드가 있다는 의미는 서브 공간과 서브 공간을 연결하는 통로에 센서가 설치되어 있지 않다는 것을 의미하는 것으로, TSS의 제2 조건을 위반한 것이다.

그리하여 센서 지정부(640)는 인접하는 블랙 노드 사이에 화이트 노드를 삽입한다(S750). 즉, 통로에 센서를 지정한다는 것을 의미한다.

S720 내지 S750를 반복수행하여, 화이트 노드에 이웃하는 블랙 노드가 하나 이하 존재하고, 블랙 노드에 이웃하는 노드가 화이트 노드이면 센서 지정부(640)에 의해 업그레이드된 접근성 그래프는 추적가능한 심볼릭 공간을 표현한 것이다.

그리하여 센서 지정부(640)는 추적가능한 심볼릭 공간을 나타내는 접근성 그래프를 인터페이스를 통해 외부로 출력한다. 그러면 관리자는 새로 생성된 화이트 노드에 대응되는 공간에 RFID 리더기와 같은 센서를 설치함으로써 적절한 수의 센서로 공간을 추적할 수 있다.

도 8은 본 발명의 일 실시예에 따른 추적가능한 심볼릭 공간에서 객체를 추적하는 객체 추적 장치이다.

객체 추적 장치는 RFID 리더기로부터 수신된 RFID 태그의 식별 정보 및 리더기의 위치 정보를 이용하여 태그가 위치를 추적하는 장치로서, 제2 인터페이스(810), 제1 저장부(820), 제2 저장부(830), 위치 결정부(850), 입력부(850) 및 출력부(840)를 포함한다.

제2 인터페이스(810)는 리더기와 통신하여 리더기의 식별 정보 및 태그의 식별 정보를 수신하여 제1 저장부(820)로 인가한다.

제1 저장부(820)는 RFID 태그 정보를 기준으로 시간 경과에 따른 RFID 리더기 정보를 저장한다. 구체적으로, RFID 태그를 소지한 객체는 공간을 이동하고 있다. 객체가 RFID 리더기의 커버리지내에 있으면, RFID 리더기는 RFID 태그 정보를 수신하여 RFID 태그 정보 및 RFID 리더기 정보를 객체 추적 장치에 전송한다. 그러면, 제1 저장부(820)는 시간 순에 기초하여 RFID 리더기 정보를 저장한다.

제2 저장부(830)는 심볼릭 공간에 대한 정보가 저장된다. 특히 제2 저장부(830)에는 추적 가능한 심볼릭 공간의 접근성 그래프가 저장되어 있는 것이 바람직하다.

위치 결정부(850)는 RFID 리더기 정보 및 접근성 그래프를 이용하여 특정 시간에 RFID 태그를 소지한 객체가 존재하는 위치 또는 객체의 이동 경로를 추적한다. 그리고, 출력부(840)는 객체의 위치 또는 이동 경로를 출력한다.

도 9는 본 발명의 일 실시예에 따른 추적가능한 심볼릭 공간에서 객체를 추적하는 방법을 설명하는 흐름도이다.

입력부(850)를 통해 특정 RFID 태그를 갖는 객체의 추적 명령이 입력되면(S910-Y), 위치 결정부(850)는 객체가 화이트 노드에 있는지 판단한다(S920). 구체적으로, 현재 RFID 태그를 갖는 객체가 화이트 셀에 존재하면, 해당 화이트 셀내의 RFID 리더기는 RFID 태그의 식별 정보 및 RFID 리더기의 식별 정보를 객체 추적 장치에 전송하고, RFID 태그의 식별 정보, RFID 리더기의 식별 정보 및 전송 시간이 제1 저장부(820)에 저장된다. 그러면 위치 결정부(850)는 현재 수신된 RFID 리더기의 식별 정보를 제1 저장부(820)에서 독출하고, 상기한 RFID 리더기에 대응되는 화이트 노드를 제2 저장부(830)에서 독출함으로서 객체가 화이트 노드에 있다고 판단한다.

객체가 화이트 노드에 있다고 판단되면(S920-Y), 위치 결정부(850)는 화이트 노드의 위치를 객체의 위치로 결정하고, 그 결과를 출력한다(S930).

한편, 위치 결정부(850)가 현재 객체가 화이트 노드에 있지 않다고 판단되면(S920-Y), 위치 결정부(850)는 가장 최근의 화이트 노드를 독출한다(S940). 즉, 현재 RFID 리더기로부터 식별 정보를 수신받지 못하여 제1 저장부(820)에 RFID 리더기의 식별 정보가 저장되어 있지 않으면, 위치 결정부(850)는 현재 객체가 화이트 노드에 있지 않다고 판단한다. 그리고 제1 저장부(820)에 기저장되어 있는 가장 최근의 화이트 노드에 대응되는 RFID 리더기의 식별 정보를 독출한다.

그리고, 위치 결정부(850)는 독출된 RFID 리더기의 식별 정보에 대응되는 화이트 노드를 제2 저장부(830)에서 탐색한 후, 화이트 노드와 인접하는 블랙 노드를 객체의 현재 위치로 결정한다(S950). 그리고, 그 결과가 출력된다.

도 10은 제1 저장부(820)에 저장되어 있는 태그와 리더기 정보이고, 도 11은 제2 저장부(830)에 저장되어 있는 인접성 그래프이며, 도 12는 도 11의 인접성 그래프에 대응되는 공간과 관련된 도면이다. 도 10에서 ts와 te는 RFID 태그가 RFID 리더기의 커버리지에 머물러 있는 시간을 의미한다.

도 10 및 도 11를 이용하여 위치 결정부(850)는 태그 1(tag1)의 이동 경로를 추적할 수 있는 것이다. 즉, 1<t<3에서 리더기 3(reader3)이 태그를 인식하였고, 3<t<5에서 리더가 4(reader4)가 태그를 인식하였기 때문에 태그를 갖는 객체는 공간 6(b6)에서 공간 3(b3)으로 이동하였다는 것을 알 수 있다. 또한, 9<t<11에서 리더기 9(reader9)가 태그를 인식하고, 11<t<13에서 리더기 10(reader10)이 태그를 인식하였기 때문에 객체는 공간 3(b3)에 머물렀다가 공간 5(b5)로 이동하였다는 것을 알 수 있다. 그리고 나서 30<t<32에서 리더기 10(reader10)이 태그를 인식하고, 32<t<34에서 리더기 9가 태그를 인식하였기 때문에 객체는 공간 5(b5)에 머물렀다가 공간 3(b3)으로 이동하였다는 것을 알 수 있다. 즉, 도 12의 공간에서 객체의 이동 경로를 위치 결정부(850)는 태그와 리더기 정보 및 인접서 그래프만으로도 파악할 수 있다.

특히, 도 11 및 도 12에 도시된 바와 같이, 화이트 영역 9(W9)는 하나의 RFID 리더기의 커버리지에 포함되기 때문에 하나의 RFID 리더기만을 설치하여도 무방하다. 이는 RFID 리더기를 설치하는 자에 의해 인접성 그래프가 수정될 수 있음을 의미한다.

이와 같이 적절한 수의 센서만을 공간에 설정하더라고 객체의 이동 경로 추적이 가능함을 확인할 수 있다.

또한, 이상에서는 본 발명의 바람직한 실시예에 대하여 도시하고 설명하였지만, 본 발명은 상술한 특정의 실시예에 한정되지 아니하며, 청구범위에서 청구하는 본 발명의 요지를 벗어남이 없이 당해 발명이 속하는 기술분야에서 통상의 지식을 가진자에 의해 다양한 변형실시가 가능한 것은 물론이고, 이러한 변형실시들은 본 발명의 기술적 사상이나 전망으로부터 개별적으로 이해되어져서는 안될 것이다.