KR101203232B1

KR101203232B1 - 이동 장치의 로케이션 역학을 결정하는 시스템 및 방법, 이동 장치를 추적하는 것을 용이하게 하는 머신 구현 시스템, 무선 장치 로케이션 시스템, 및 컴퓨터 판독가능 기록 매체

Info

Publication number: KR101203232B1
Application number: KR1020120070859A
Authority: KR
Inventors: 존 씨. 크룸; 에릭 제이. 호르비츠
Original assignee: 마이크로소프트 코포레이션
Priority date: 2003-06-30
Filing date: 2012-06-29
Publication date: 2012-11-21
Anticipated expiration: 2024-05-31
Also published as: CN1578530A; US20050270236A1; EP1494397A3; KR101203261B1; US7053830B2; KR20050004701A; KR101203228B1; US20050258957A1; US7250907B2; US20050270235A1; CN1578530B; JP5165181B2; KR20120093114A; JP2005024540A; US20040263388A1; EP1494397A2; US7532113B2; US7199754B2; KR20120093116A; KR101292870B1

Abstract

본 발명은 무선 장치의 위치를 정하고 이동 상태(motion) 및 속도를 결정하기 위한 로케이션 시스템에 관한 것이다. 방법들은 시간에 따른 무선 신호 강도들의 변화(variation)의 통계 분석을 근거로 장치의 이동 상태 대 정지 상태에 대한 직접 추론을 포함한다. 시스템은 신호 강도들이 측정되는 식별된 로케이션들의 산재 집합에 따라 훈련된다. 시스템은 무선 장치의 새로운 로케이션에 대해 보간(interpolate)하기 위해 식별된 로케이션들의 신호 특성들을 사용한다. 시스템은 확률 그래프(probabilistic graph)를 사용하는데, 평면도의 식별된 로케이션들, 보행자의 예상 걷기 속도, 및 장치 이동 여부와 무관한 독립적 추론이 장치의 새로운 로케이션을 결정하는데 사용된다.

Description

이동 장치의 로케이션 역학을 결정하는 시스템 및 방법, 이동 장치를 추적하는 것을 용이하게 하는 머신 구현 시스템, 무선 장치 로케이션 시스템, 및 컴퓨터 판독가능 기록 매체{SYSTEM AND METHODS FOR DETERMINING THE LOCATION DYNAMICS OF A PORTABLE COMPUTING DEVICE}

본 출원은 2003년 4월 25일에 출원된 "무선 신호 강도를 사용하는 장치 로케이션 측정 시스템의 교정(CALIBRATION OF A DEVICE LOCATION MEASUREMENT SYSTEM THAT UTILIZES WIRELESS SIGNAL STRENGTHS)"라는 제목의 계류중인 미국 특허 출원 일련 번호 제10/423,093호와 관련된다.

본 발명은 장치 로케이션 시스템에 관한 것으로, 특히, 무선 신호 강도들을 사용해서 장치 로케이션 및 이동 상태를 결정하는 확률 로케이션 시스템에 관한 것이다.

무선 네트워크 액세스가 도처에서 발생됨에 따라 무선 신호 강도 측정을 근거로 무선 클라이언트의 로케이션을 식별하는 것을 목적으로 하는 수개의 방법들이 생성되어 왔다. 로케이션-베이스 시스템들이 정확성 및 사용하기 편리함이라는 점에서 계속해서 향상되어 왔지만, 아직까지 종래의 노력들로는 주위의 무선 기본 시스템을 사용해서 이동 및 속도와 같은 클라이언트의 역학들을 직접적인 방식으로 식별한다고 생각되지 않는다. 로케이션을 추론하는데 사용된 동일한 신호들은 역학을 추론하는데 사용될 수 있다. 일반적으로, 역학에 대한 정보는 클라이언트 로케이션 및 문맥을 모두 추론하는 것을 돕는데 유용하다. 클라이언트 이동 정보에 대한 직접 액세스는 시간에 따라 수신된 신호 시리즈를 연합하는 최상의 방법과 관련된다. 예를 들어, 클라이언트가 이동 상태가 아니다라는 정보는 로케이션 알고리즘이 현 로케이션 추정값들의 집합을 보다 확실하게 단일 추정값으로 연합하게 한다. 예를 들어, 이동 장치(및 이동 클라이언트와 관련된 사용자)가 이동 상태인지에 대한 정보는 사용자에게 중요한 메시지로 경고해 줄지의 여부와 경고하는 방법에 대한 신호를 제공하는데 유용할 수도 있다. 사용자가 로케이션에 도착할 때까지 메시지들을 보류하거나, 또는 사용자가 이동중일 때 가장 중요한 메시지들만을 통과시키는 것이 양호할 수도 있다. 다른 일례로서, 사용자가 이동중일 때 메시지를 압축해서 요약 또는 절단하거나, 또는 경고 양식 볼륨을 올리거나, 또는 디스플레이 텍스트 크기를 증가하는 것이 양호할 수도 있다.

로케이션 정보는 관심 있는 사람, 장소 및 객체들을 찾는데 사용될 수도 있다. 사람 및 아이템들의 현 상태에 대한 액세스를 제공하는 것 외에도, 로케이션 정보는 존재-예측 서비스들을 지원할 수 있으며, 상기 서비스들은 사용자의 차후 존재 또는 가용성(availability)에 대한 정보를 제공한다. 다른 애플리케이션들에서, 장치 가용성 및 상이한 문맥들과 관련된 인터럽션 비용이 주어지면, 로케이션은 또한 사용자로의 통지 사항들을 릴레이하는 최상의 방법을 식별하는데 유용하다. 로케이션 정보는 또한 주변 장치들 또는 장치 컴포넌트들의 집합을 정렬하는데 사용될 수도 있다.

아웃도어 애플리케이션들은 고 신뢰성(high-confidence) 로케이션 정보를 획득하기 위해 GPS(Global Positioning Service) 또는 GLONASS(Global Navigation Satellite System) 위성 네비게이션 시스템들로부터의 타이밍 신호 디코딩에 의존할 수 있다. 불행히도, 인도어 애플리케이션들에 유용한 동등하게 편재하는 로케이션 측정 수단은 없다. 액티브 배지 또는 무선 주파수 식별(RFID) 태그와 같은 특정 시스템이 인도어에서 양호하게 작동할 수 있더라도, 설치 비용이 비쌀 수도 있으며 - 사용자들에게 여분의 장치를 소지할 것을 요구한다.

특정 로케이션시스템을 의존하는 유명한 다른 대안은 빌딩의 현존 IEEE 802.11 무선 기본 시스템(이후부터는 "Wi-Fi"로 기재됨)에 의해 생성된 신호들에 액세스함으로써 로케이션을 추론하는 것이다. Wi-Fi 설치는 개인 공간 또는 공중 공간으로 재빨리 확산되어 왔다. 동시에, IEEE 802.11 네트워크 인터페이스 하드웨어 또는 내장형 Wi-Fi가 장치된 이동 장치들의 수가 증가되어 유용하게 사용되고 있다. Wi-Fi 기본 시스템이 보다 도처에 존재하게 됨에 따라, Wi-Fi가 결코 로케이션 추론을 목적으로 하지 않았음에도 불구하고, 주위 무선 신호들을 이용하는 로케이션 기술들이 발전할 수 있다.

현존 IEEE 802.11 네트워킹 기본 시스템으로부터 장치 정보에 액세스하기 위한 생성중인 방법들은 주위 신호들을 사용할 때 흥미로우며 수신기들은 특정 브로드캐스팅 및 센싱 하드웨어에 대한 요구 사항을 무시한다. IEEE 802.11 무선 신호들로부터 로케이션을 확인하려는 종래의 노력은 신호들을 로케이션으로 매핑하는 것을 목적으로 하는 송신 및 성가시게 교정 수고가 필요한 상세한 모델들의 구성에 의존해 왔다.

다수의 IEEE 802.11 액세스 포인트들로부터 신호 강도들을 측정함으로써 인도어에서 무선 클라이언트들의 로케이션을 식별하는 기능은 이제 새로운 것이 아니다. RADAR라고 하는 기술을 포함해서, 신호 강도 기호(signature) 매칭은 모든 로케이션-802.11 기술들이 사용하는 동일한 기본 기술이다. 신호 강도 수동 교정표를 사용해서, RADAR 가장 가까운 이웃 알고리즘은 대략 2.94 미터의 중간 공간 에러를 제공했다. 잇따르는 작업에서, 비터비-유사(Viterbi-like) 알고리즘을 사용해서 약 2.37 미터로 에러가 감소되었다. 다른 연구는 무선 전파 모델 및 빌딩의 평면도를 사용해서 신호 강도 기호들을 미리 계산했다. 이는 중간 로케이션 에러를 4.3 미터로 증가시키는 댓가로 교정 노력을 감소시켰다.

다른 종래의 시스템, 및 아마도 가장 정확한 IEEE 802.11 로케이션 시스템은 베이스 추론(Bayesian reasoning) 및 HMM(hidden Markov model)을 사용했다. 상기 시스템은 신호 강도 뿐만 아니라 소정의 로케이션으로부터 액세스 포인트를 볼 확률도 고려했다. 다른 작업에서처럼, 수동 교정을 근거로 했다. 시스템은 명백하게 방위(orientation)를 모델링했고 복도에서 대략 1.5 미터(5 피트) 마다 취해진 교정 샘플들을 사용해서 대략 1 미터의 중간 공간 에러를 달성했다. 예를 들어, 보다 흔하게 사용되는 생 신호 강도들 대신 신호 대 잡음 비율들을 사용하고, 신호 강도의 함수로서 액세스 포인트까지의 거리를 어림잡는데 사용된 공식을 사용하는 다수의 추가 종래 시스템들이 사용되어 왔다.

Wi-Fi-중심 시스템들은 로케이션 정보 프라이버시를 포함해서 수개의 매력적인 기능들을 가지고 있다. 모든 로케이션 계산들은 클라이언트 디바이스에서 실행될 수 있으며, 디바이스는 유선망으로의 무선 인터페이스에 사용자 아이덴티티 또는 다른 정보를 공개할 필요가 없다. 편재하는 Wi-Fi 기본 시스템, 현존 유능한 클라이언트 디바이스, 및 프라이버시 솔루션들을 결합해서 로케이션을 식별하는 강제적인 IEEE 802.11 방법을 생성한다.

그러나, 로케이션 역학에 대한 추가 정보를 제공하면서 동시에 교습 시간을 덜 필요로 하는 Wi-Fi 로케이션-베이스 시스템이 여전히 요구된다.

이제부터 본 발명의 몇몇 양상들에 대한 기본 이해를 돕기 위해 본 발명의 간단한 요약이 제공된다. 본 요약은 본 발명의 광대한 개요가 아니다. 본 발명의 주요한 요소들을 정의하거나 본 발명의 범위를 서술하려는 것이 아니다. 단지 후술되는 보다 상세한 설명에 대한 서두로서 간단한 형태로 본 발명의 소정의 개념들을 제시하는 것을 목적으로 한다.

본 명세서에서 기술되고 청구된 본 발명은, 한 양상으로, 무선망에서 무선 신호들의 강도들을 분석함으로써 휴대형 컴퓨팅 디바이스의 이동 상태 및 로케이션을 결정하기 위한 아키텍처를 포함한다. 사용자에게 경고를 해주기 위한 가장 적합한 시간 및 장치에 대한 결정을 하는 시스템들을 포함해서 다양한 애플리케이션들을 위해 이동 대 비이동에 대한 정보 및 보다 정확한 로케이션 정보가 제공되는 것이 유용하다. 본 발명은 무선망에서 사용자에게 관련 정보(예를 들면, 추론된 차후 상태 뿐만 아니라 상태를 근거로 함)를 제공할 뿐만 아니라 개인들 및/또는 컴포넌트들의 추적을 용이하게 해준다. 본 발명은 또한 통신 최적화, 예를 들어, 통신 및 데이터 처리 능력 유지를 용이하게 해준다.

특히, 본 발명은 신호 강도들 및 가시적 액세스 포인트들의 코히런트 확률 해석을 소개하고, HMM 표현을 사용한다. 그러나, 본 발명은 상태 전이 확률들의 추정값들을 제공하기 위해 종래의 시스템들 보다 더 정교한 모델들을 사용한다는 점에서 독특하며, 교정 수고를 감소시킨다. 신규 시스템은 빌딩 층(floor)의 이산 (x,y) 고밀도 로케이션 노드들의 연결 그래프로부터 동작한다. 신호 강도 집합을 수신할 때, HMM은 장치가 로케이션 노드들 각각에 있을 확률을 계산하는데 사용된다. 알맞은 때에 각각의 포인트에서, 로케이션 노드들의 각각의 쌍은 장치가 쌍의 제1 멤버로부터 제2 멤버로 이동할 확률을 제공하는 관련된 전이 확률을 갖는다. 전이 확률들은 최종 신호 강도 판독 이래로 경과된 시간, 한 쌍의 노드들 간의 거리, 및 장치가 현재 이동 상태일 확률의 함수이다. 한 쌍의 노드들 간의 거리를 유클리드 거리로 생각하는 대신, 최단 경로 거리는 경로들이 벽들을 통과할 수 없도록 빌딩 평면도의 벽들을 고려하는 제약-민감(constraint-sensitive) 경로-계획 알고리즘을 근거로 한다.

본 발명은 주위 IEEE 802.11 기본 시스템을 근거로 한 로케이션 서비스들과 관련된 견고함을 강화하고 교습(또는 교정) 노력을 감소시키기 위한 확률 방법들을 포함한다. 본 아키텍처는 확률 그래프를 사용하는데, 로케이션들은 노드들이고 노드들 간의 전이 확률들은 빌딩(또는 평면도) 레이아웃, 보행자의 예상 걷기 속도, 및 장치가 이동 상태인지의 여부에 대한 독립적 추론의 함수로서 유도된다. 본 타입의 다른 시스템들에 비해 신호 강도 교정은 비교적 쉽다. 본 발명은 드문 드문 샘플링된 교정 노드들의 집합으로부터의 신호 강도의 보간을 포함함으로써 교정 수고를 최소화하고, 빌딩 인테리어 구조(예를 들면, 벽, 문)에 의해 부과된 경로 제약을 이용하고, 사람 보행 속도 고려 사항들을 통합하고, 클라이언트 디바이스가 이동 중인 지를 독립적으로 추론하며, 상기 추론들로 로케이션 분석을 하는 비교적 정확한 로케이션 센싱 시스템을 제공한다. 따라서, 이동 클라이언트는 획득하기 지루할 수도 있는 산재된 교정 데이터에도 불구하고 정확성을 유지하기 위해 가능한 한 스마트(smart)해야 한다. 본 발명은 전형적으로 시끄러운 생 신호 데이터로부터 귀중한 데이터를 추출하기 위해 중요한 경로, 시간 및 레이트 제약 사항들을 포함함으로써 정확성과 교정 수고 간의 뛰어난 협상을 나타내는 원칙 프레임워크를 제공한다.

본 시스템은 교정을 위해 종래의 시스템들 보다 훨씬 더 산재하는 로케이션 노드들의 집합을 방문하는 것을 용이하게 해준다. 보다 낮은 밀도의 교정 노드들로부터 고밀도 로케이션 노드들에서의 관측 확률들을 추정하기 위해 보간이 사용된다. 이는 필요한 교정 수고를 상당히 감소시킨다. 로케이션 노드, 전이 확률, 및 관측 확률의 그래프는 시스템의 실제 동작 중에 획득된 모든 관측 신호 강도 집합으로부터 고밀도 노드들에 대한 확률 분포를 계산하기 위해 비터비 알고리즘과 결합된다. 장치 로케이션의 예상값은 최종 결과로서 보고되며, 중간 에러가 약 1.53 미터임을 나타낸다.

상술된 목적들 및 관련 목적들을 달성하기 위해, 본 발명의 특정 일례의 양상들이 이하의 설명 및 첨부된 도면들을 참조해서 본 명세서에 기술된다. 그러나, 본 양상들은 본 발명의 원칙들이 사용될 수도 있는 다양한 방법들 중 단지 소수의 방법들만을 나타내는 것이며, 본 발명은 모든 양상들 및 동등물을 포함한다. 본 발명의 다른 장점들 및 신규한 특징들은 도면을 참조해서 고려될 때 본 발명의 이하의 상세한 설명으로부터 명백해질 것이다.

본 발명은 무선망에서 사용자에게 관련 정보를 제공할 뿐만 아니라 개인들 및/또는 컴포넌트들의 추적을 용이하게 해준다. 본 발명은 또한 통신 최적화, 예를 들어, 통신 및 데이터 처리 능력 유지를 용이하게 해준다.

본 발명은 상태 전이 확률들의 추정값들을 제공하기 위해 종래의 시스템들 보다 더 정교한 모델들을 사용한다는 점에서 독특하며, 본 발명에 따라, 교정 수고가 감소된다.

도 1은 본 발명의 로케이션 역학 결정을 용이하게 하기 위한 시스템의 블록도.
도 2는 본 발명의 확률 컴포넌트의 프로세스들의 순서도.
도 3a는 시스템을 셋업한 사람에 의해 그려진 평면도에서 저밀도 노드들을 그래픽적으로 표현한 도면.
도 3b는 평면도에서 저밀도 노드들에 자동으로 추가된 고밀도 노드들을 그래픽적으로 표현한 도면.
도 3c는 본 발명의 데이터 수집 시스템에 의해 제공된, 신호 강도 판독(readings)을 획득하는데 사용된 평면도의 교정 노드들을 그래픽적으로 표현한 도면.
도 4는 본 아키텍처의 컴퓨터 드로잉 또는 매핑 프로그램에 의해 사용되기 위한 저밀도 노드들 및 고밀도 노드들을 설정하기 위한 프로세스의 순서도.
도 5a는 시간에 따른 장치의 이동 여부에 대한 생 비평활화 이후 확률들(raw unsmoothed a posteriori probabilities)을 도시한 도면.
도 5b는 시간에 따른 장치의 이동 여부에 대한 평활화 이후 확률들(smoothed a posteriori probabilities)을 도시한 도면.
도 5c는 도 5a 및 도 5b와 관련된 장치의 실제 이동 상태를 도시한 도면.
도 6은 장치의 동적 상태를 결정하는데 사용된 2상 마르코프 모델(2-state Markov model)의 상태도.
도 7은 정지 경우 및 이동 경우에 대한 편차(variance)들의 히스토그램.
도 8은 본 발명에 따라 사용된 사람 걷기 속도들의 종래의 분포를 도시한 도면.
도 9는 교정 데이터의 신호 강도 로깅을 용이하게 하기 위한 데이터 수집 프로그램의 그래픽 사용자 인터페이스의 스크린샷.
도 10은 본 아키텍처를 실행하기 위해 동작할 수 있는 컴퓨터의 블록도.
도 11은 본 발명에 따른 일례의 컴퓨팅 환경의 개략 블록도.

본 발명은 이제부터 도면들을 참조해서 기술될 것이며, 도면에서, 유사한 참조 부호들은 유사한 소자들을 나타내는데 사용된다. 이하의 설명에서, 다수의 특정 세부 사항들은 본 발명의 이해를 돕기 위해 설명을 목적으로 기재된 것이다. 그러나, 본 발명이 특정한 세부 사항 없이 실현될 수도 있음이 명백하다. 다른 일례들에서, 널리 공지된 구조들 및 장치들이 본 발명의 설명을 돕기 위해 블록도 형태로 도시되어 있다.

본 애플리케이션에서 사용되는 바와 같이, 용어 "컴포넌트" 및 "시스템"은 컴퓨터-관련 엔티티, 하드웨어, 하드웨어와 소프트웨어의 결합물, 소프트웨어, 또는 실행중인 소프트웨어를 나타낸다. 예를 들어, 컴포넌트는 프로세서에서 실행중인 프로세스, 프로세서, 객체, 실행 가능, 실행 스레드, 프로그램, 및/또는 컴퓨터일 수도 있지만, 제한의 의미는 아니다. 예를 들어, 서버에서 실행되는 애플리케이션 및 서버는 모두 컴포넌트일 수 있다. 하나 이상의 컴포넌트들은 실행 프로세스 및/또는 스레드 내에 존재할 수도 있으며, 컴포넌트는 하나의 컴퓨터로 집중될 수도 있으며 또는 2개 이상의 컴퓨터들에 분산될 수도 있다.

본 명세서에서 사용된 용어 "추론"은 일반적으로 이벤트 및/또는 데이터를 통해 포착된 관측 사항 집합으로부터 시스템, 환경, 및/또는 사용자의 상태를 추론하는 프로세스를 말한다. 추론은, 예를 들어, 특정 문맥 또는 액션을 식별하는데 사용될 수 있으며, 또는 상태들에 대한 확률 분포를 생성할 수 있다. 추론은 확률일 수 있다 - 즉, 데이터 및 이벤트 고려 사항을 근거로 관심 있는 상태들에 대한 확률 분포의 계산일 수 있다. 추론은 또한 이벤트 및/또는 데이터 집합으로부터 보다 높은 레벨의 이벤트들을 구성하는데 사용되는 기술들을 말할 수도 있다. 이러한 추론은 관측 이벤트들 및/또는 기억된 이벤트 데이터 집합, 이벤트들이 임시로 가깝게 근접해서 상관되는지의 여부, 및 이벤트들 및 데이터가 하나의 또는 수개의 이벤트 및 데이터 소스들로부터 온 것인지의 여부로부터 새로운 이벤트 또는 액션들을 구성하게 한다.

도 1을 참조하면, 본 발명의 로케이션 및 순간 역학 결정을 용이하게 해주는 시스템(100)의 블록도가 도시되어 있다. 측정 컴포넌트(102)는 액세스 포인트(AP)들이라고 하는, 다수의 무선 네트워크 인터페이스들과 관련된 무선 신호들로부터 유도된 신호 강도(104)를 하나의 입력으로서 수신한다. 측정 컴포넌트(102)는 생 신호들을 수신해서, 생 신호들을 처리해서 신호 강도 데이터를 획득하도록 구성될 수도 있음을 주지하라. 임의의 경우에, 신호 강도 데이터(104)는 처리되어, 휴대형 장치가 현재 이동 상태일 확률 뿐만 아니라 로케이션에 있을 예상값(108)을 확률 프로세싱 컴포넌트(106)가 최종적으로 출력으로서 보고하는데 사용된다.

보다 상세히 후술된 바와 같이, 확률 프로세싱 컴포넌트(106)는 확률 그래프를 사용하는데, 로케이션들은 로케이션 노드들로 표현되며, 로케이션 노드들 간의 전이 확률들은 빌딩(또는 평면도) 레이아웃, 보행자의 예상 걷기 속도, 및 장치가 이동 상태인지의 여부에 대한 독립적인 추론의 함수로서 유도된다.

확률 컴포넌트(106)는 상태 전이 확률들의 추정값들을 제공하기 위해 종래의 시스템들 보다 더 정교한 모델들을 사용해서, 교정 노력을 감소시킨다. 특히, 시스템(100)은 신호 강도들 및 가시적 액세스 포인트들의 확률 해석을 제공하며, HMM(hidden Markov model) 표현을 사용한다. 신호 강도(104) 집합 수신시, HMM은 휴대형 장치가 로케이션 노드들 각각에 있을 확률을 계산하는데 사용된다. 알맞은 때에 각각의 포인트에서, 노드들의 각각의 쌍은 장치가 쌍의 제1 멤버로부터 제2 멤버로 이동할 확률을 제공하는 관련된 전이 확률을 갖는다. 전이 확률들은 최종 신호 강도 판독 이래로 경과된 시간, 한 쌍의 노드들 간의 거리, 및 장치가 현재 이동 상태일 확률의 함수이다. 한 쌍의 노드들 간의 거리를 유클리드 거리로 생각하는 대신, 최단 경로 거리는 경로들이 벽들을 통과할 수 없도록 빌딩 평면도의 벽들을 고려하는 제약-민감 경로-계획 알고리즘을 근거로 한다.

시스템(100)은 드문 드문 샘플링된 집합으로부터의 신호 강도의 보간을 포함함으로써 교정 수고를 최소화하고, 빌딩 인테리어 구조(예를 들면, 벽, 문)에 의해 부과된 경로 제약을 이용하고, 사람 보행 속도 고려 사항들을 통합하고, 클라이언트 디바이스가 이동 중인 지를 독립적으로 추론하며, 상기 추론들로 로케이션 분석을 하는 비교적 정확한 로케이션 센싱 시스템을 제공한다. 따라서, 이동 클라이언트는 획득하기 지루할 수도 있는 산재된 교정 데이터에도 불구하고 정확성을 유지하기 위해 가능한 한 스마트해야한다. 본 발명은 전형적으로 시끄러운 생 신호 데이터로부터 귀중한 데이터를 추출하기 위해 중요한 경로, 시간 및 레이트 제약 사항들을 포함함으로써 정확성과 교정 수고 간의 뛰어난 협상을 나타내는 원칙 프레임워크를 제공한다.

확률 컴포넌트(106)는 보다 낮은 밀도의 교정 노드들로부터 고밀도 로케이션 노드들에서의 관측 확률들을 추정하기 위해 보간함으로써 회귀를 사용해서 교정 수고를 상당히 감소시킨다. 로케이션 노드, 전이 확률, 및 관측 확률의 그래프는 모든 관측 신호 강도 집합으로부터 로케이션 노드들에 대한 확률 분포를 계산하기 위해 비터비 알고리즘과 결합된다. 로케이션의 예상값은 최종 결과로서 보고되며, 중간 에러가 약 1.53 미터임을 나타낸다.

휴대형 장치의 적합한 속도는 장치가 이동중일 가능성(likelihood)을 추론함으로써 명백하게 고려된다. 이동 추론 모델은 보다 상세히 후술된다. 휴대형 장치의 속도는 사람 보행 속도의 확률 분포를 고려하고 장치가 이동중인 지에 대한 추론을 근거로 예상 속도로서 계산된다.

로케이션 노드들, 전이 확률들, 및 관측 확률들의 그래프는 모든 관측 신호 강도 집합으로부터 로케이션 노드들에 대한 확률 분포를 계산하기 위해 비터비 알고리즘과 결합된다. 본 발명은 로케이션의 예상값을 최종 결과로서 보고한다.

이제부터, 도 2를 참조하면, 본 발명의 확률 컴포넌트의 프로세스들의 순서도가 도시되어 있다. 설명 편의상, 예를 들어, 순서도 형태로, 본 명세서에 도시된 하나 이상의 방법들은 액션 시리즈로 도시 및 기술되어 있지만, 본 발명이 액션 순서로 제한되지 않으며, 본 발명에 따라 몇몇 액션들이 도시 및 기재된 순서들과 상이한 순서들로 실행될 수도 있으며 다른 액션들과 동시에 실행될 수도 있음을 알게 될 것이다. 예를 들어, 본 기술 분야에 숙련된 자들은 대안으로 방법이 상태도에서와 같이 서로 관련된 상태들 또는 이벤트들의 시리즈로서 표현될 수 있음을 알 것이다. 또한, 본 발명에 따른 방법을 구현하기 위해 도시된 액션들이 모두 필요한 것은 아니다.

본 아키텍처는 휴대형 장치의 로케이션을 추정하고 이동을 추론하기 위해 IEEE 802.11 신호 강도들을 사용한다. 신호들은 이동 장치들과 유선망 간의 무선 링크를 제공하는 통계적으로 배치된 IEEE 802.11 액세스 포인트들로부터 온다.

다른 타입들의 무선 RF 송신기들이 액세스 포인트들을 대신해서 또는 액세스 포인트들과 협력해서 사용될 수도 있기에, 신규 아키텍처가 액세스 포인트들을 사용하는 것으로만 제한되지 않음을 주지하라. 예를 들어, 자산 관리 로케이션 시스템에서, RTLS(Real Time Locating System)은 본 발명의 장점들을 사용할 수도 있다. RTLS은 자산 및/또는 개인 로케이션을 계속해서 모니터하는 총 자동화 시스템이며, 통상 배터리-동작 무선 태그들을 사용하며, 태그 존재 및 로케이션을 검출하기 위해 셀룰러 로케이팅 시스템을 사용한다. 로케이팅 시스템은 50 내지 천 피트의 공간의 임의의 장소에 설치된 로케이팅 디바이스의 행렬로서 통상 배치된다. 상기 로케이팅 디바이스들은 무선 태그들의 로케이션들을 결정하며, 태그들은 임의의 아이템 또는 사람에게 배치될 수도 있다. 따라서, 아이템이 위치한 장소, 또는 사람의 로케이션 및/또는 이동을 결정하기 위해 트랜스폰더 태그들을 활성화하는 RF 송신기들로부터 신호 강도들이 수신된다. 이점에 있어서, RTLS 시스템은 동일한 방법으로 교정 및 분석될 수도 있다.

초기에, 교정될 지역의 평면도가 저밀도 노드들을 생성하는데 사용된다. 저밀도 노드들은 휴대형 장치 사용자가 통상 사용하는 보행 경로들을 추정하는 평면도의 로케이션들의 산재한 네트워크를 정의하는 노드들의 집합이다. 평면도를 사용해서 보간 프로세스에서 사용되는 노드들의 선택을 용이하게 해준다. 저밀도 노드들은 네트워크의 직선 세그먼트들의 엔드포인트들이고, 장치 이동 및 로케이션을 추론하는데 결국 사용될 전체 노드들의 부집합이다. 저밀도 노드들이 생성되면, 고밀도 노드들은 사용자 정의 공간 기준들에 따라 저밀도 노드들의 평면도에서 컴퓨터에 의해 자동으로 산재된다.

평면도의 다양한 로케이션들에서 신호 강도들을 측정하는 것은 모든 고밀도 노드에서 다수의 확률 분포 함수들을 산출하는 교정 프로세스이다. 각각의 확률 분포 함수는 고밀도 노드에서 소정의 액세스 포인트로부터 소정의 신호 강도를 "볼" 확률을 제공한다. 소정의 고밀도 노드의 확률 분포들은 해당 노드에 대한 관측 확률들이라고 한다. 평면도의 각각의 로케이션을 방문하고 신호 강도들을 기록하는 것이 비실용적이기 때문에, 교정을 위해 훨씬 더 산재하는 로케이션 노드들의 집합이 방문을 받는다. 그 후 교정 노드들로부터 고밀도 노드들의 관측 확률들을 추정하기 위해 보간이 사용된다. 이는 필요한 교정 수고를 상당히 감소시킨다.

따라서, (200)에서, 평면도의 컴퓨터 생성 및 프로세스 가능 맵이 저밀도 및 고밀도 로케이션 노드들을 모두 설정하기 위해 생성된다. (200)에서 결합되더라도, 저밀도 노드들은 먼저 수동 입력으로 생성되며, 이어서, 평면도에서 자동으로 고밀도 노드들이 저밀도 노드들 중에 산재된다. (202)에서, 시스템은 한 집합의 교정 노드들 각각에서 신호 강도들을 측정 및 기록하는 교정 프로세스에 의해 훈련된다. 교정 노드들의 로케이션은 저밀도 및/또는 고밀도 노드 로케이션들과 반드시 동일하게 선택될 필요는 없으며, 우연히 그렇게 될 수는 있다. 교정 프로세스는 각각의 교정 노드에 대한 신호 강도 분포 유도를 용이하게 해준다. (204)에서, 관측 확률들이 교정 노드의 관측 신호 강도들을 근거로 생성되어 각각의 고밀도 노드에 할당된다.

(206)에서, 경로 제약 정보, 이동/정지 확률 정보, 및 각각의 쌍의 고밀도 노드들 간의 속도 분포 데이터를 사용해서 고밀도 노드들의 각각의 쌍에 대해 전이 확률들이 생성되어 할당된다. (208)에서, 모든 관측 신호 강도들에 대한 모든 고밀도 노드들의 확률 집합을 생성하기 위해 HMM의 요소들을 결합하는데 비터비 알고리즘이 사용된다. 다른 알고리즘들이 또한 사용될 수도 있다. 그 후, (210)에 도시된 바와 같이, 각각의 고밀도 노드는 휴대형 장치가 해당 노드에 있을 로케이션 확률 값을 할당 받는다. (212)에 도시된 바와 같이, 장치가 고밀도 노드에 있거나 근처에 있을 가능성을 결정하기 위해 고밀도 데이터를 근거로 보간이 사용된다. 그 후 프로세스는 정지 블록에 도달한다.

도 3a를 참조하면, 평면도(300)의 저밀도 로케이션 노드들의 그래픽 표현이 도시되어 있다. 평면도 구조(300)(예를 들면, 벽 및 문)에 의해 부과된 경로 제약들을 용이하게 하기 위해, 본 로케이션 시스템은 이산 로케이션 노드들의 그래픽 표현을 제공한다. 처음에, 도 3a에 도시된 바와 같이, 사용자는 교정될 지역의 모든 로케이션들 간의 유사 보행 경로들(302)을 나타내는 선들을 수동으로 그리기 위해 교정될 지역의 평면도(300)를 사용한다. 이는 저밀도 노드들(304)의 네트워크(엔드포인트 노드들 및 중간 직선 세그먼트 엔드포인트 노드들을 포함함)를 평면도(300)에 삽입한다.

도 3b는 저밀도 노드들 중에 자동으로 산재된 고밀도 노드들을 포함하는 평면도의 그래픽 표현을 도시한 것이다. 데이터 수집 알고리즘은 사용자가 입력한 공간 기준에 따라 저밀도 로케이션 노드들의 집합 중에 고밀도 노드들의 집합을 자동으로 계산해서 분산시킨다. 따라서, 도 3b는 평면도(300)에 매핑된 이산 노드들의 총 집합을 도시한 것으로, 고밀도 노드들에서 장치 로케이션을 추론하는데 사용된 저밀도 로케이션 노드들을 모두 포함한다. 굵은 선(308)은 2개의 로케이션 노드들(310 및 312) 간의 최단 경로를 도시한 것이다. 에지 웨이트들(즉, 노드들 간의 커넥션들)은 임의의 2개의 인접 노드들 간의 거리들로 정의된다. 도 3c는 신호 강도 판독들을 측정하기 위한 평면도 교정 노드 로케이션들(314)의 그래픽 표현을 도시한 것이다.

모든 데이터가 비터비 알고리즘을 통해 처리되면, 그 결과는 장치가 로케이션에 있거나 근처에 있을 확률이 주어진 상황에서 각각의 로케이션 노드(304 및 306)에 첨부된 수이다.

이제부터 도 4를 참조하면, 본 아키텍처의 컴퓨터 드로잉 또는 매핑 프로그램에 의해 사용될 저밀도 및 고밀도 노드들을 설정하기 위한 프로세스의 프롤우챠트가 도시되어 있다. (400)에서, 교정될 평면도의 컴퓨터-베이스 그래픽 비트맵 표현이 생성된다. 빌딩 평면도의 비트맵을 배경으로 디스플레이하는 드로잉 프로그램이 제공된다. 평면도의 전자 데이터베이스로부터 또는 스캔된 청사진으부터 평면도 비트맵이 획득될 수도 있다. 픽셀들 및 평면 좌표들 간의 변환(transformation)은 비트맵의 대응 포인트들 및 실제 평면도를 근거로 변환 행렬에 적합한 간단한 최소 제곱법으로 계산된다.

(402)에서, 저밀도 노드들을 배치하기 위해, 걷게 될 수도 있는 보도들을 추정하는 인간 경로선들 또는 트랙들의 집합은 도 3a에 도시된 바와 같이 매핑 프로그램 인터페이스를 통해 평면도에 수동으로 그려진다. 이러한 트랙들은 사용자가 평면도 지역 도처를 이동함에 따라 수반될 수도 있는 사용자 및 휴대형 장치의 알맞은 보행 경로들을 나타낸다. 드로잉 프로그램은 사용자가 평면도에 직선들을 그릴 수 있게 해주는데, 엔드포인트들은 특정 로케이션에 부착되거나 이전에 그려진 선상의 임의의 장소로 정해질 수 있다. 프로그램은 또한 선들 및 엔드포인트들의 이동을 위해 간단한 편집 컨트롤들을 제공한다. 모든 경로선들이 그려지면, 프로그램은 (404)에 도시된 바와 같이 로케이션 노드로서 각각의 경로 직선 엔드포인트를 처리함으로써 선들을 저밀도 노드들로 변환한다.

(406)에서, 매핑 프로그램은 사용자가 제공한 공간 기준에 따라 평면도 비트맵 도처에서 저밀도 노드들 중에 고밀도 노드들을 자동으로 분산시킨다. 예를 들어, 간격이 1 미터인 경우, 도 3b에 도시된 바와 같이, 평면도에서 총 317개의 저밀도 및 고밀도 노드들이 생성된다.

고밀도 노드들은 각각의 노드 모두가 각각의 다른 노드와 연결되도록 전체적으로 연결된 양방향 그래프인 그래프를 나타낸다. (408)에서, 인접 고밀도 노드들로의 최단 경로들은 유클리드 거리로 계산되어 기억된다. 도 3b에 도시된 에지들은 단지 인접 노드들 간의 에지들이며, 에지 웨이트는 노드들 간의 유클리드 거리이다. (410)에서, 비인접 고밀도 노드들의 최단 경로는 최단-경로 알고리즘에 따라 계산되어 기억된다. 최단 경로들은 유명한 과학자 Edsger W. Dijkstra의 최단 경로 알고리즘을 사용해서 계산된다. 비인접 노드들의 경우, 에지 웨이트는 인접 노드들의 시퀀스에 걸친 최단 경로 거리이다. 모든 거리들은 차후에 HMM에 의해 사용되도록 기억된다.

최단 경로 거리들은 평면도 구조에 의해 부과된 경로 제약 사항들을 포함한다. 예를 들어, 도 3b는 2개의 사무실들의 대략 중심들을 연결하는 최단 경로를 굵은 선(312)으로 도시한다. 이는 2개의 엔드포인트들(310 및 312) 간의 최단 경로이며, 2개의 포인트들 간에 어떤 것이 훨씬 더 짧은지를 알기 위해서는, 직접 유클리드 거리와 대립해서, 장치가 적어도 최단 경로만큼은 이동해야만 한다는 사실을 의미한다. 공식상, 노드들 i 및 j 간의 거리는 d_ij라고 한다. 상기 거리들은 후에 그래프의 모든 노드들 간의 실제 전이 확률들을 계산하는데 사용된다. 전이 확률들은 보다 상세히 후술된다.

노드들의 이산 속성은 로케이팅될 장치가 선정된 저밀도 또는 고밀도 노드들 중 임의의 노드에 정확하게 있을 것 같지 않다는 점에서 약간의 문제점을 야기한다. 이러한 문제는 노드들이 함께 꽤 밀접해 있다(인접 노드들이 1 미터 이상은 떨어져 있지 않음)는 사실과, 마지막에 연속 위치 추정값이 노드 좌표들 전체에 대한 이산 확률 분포의 예상값을 근거로 계산된다는 사실에 의해 완화된다. 다양한 잠정적 로케이션-지정 애플리케이션들의 경우, 통상 상기 해결 방안으로 충분하다.

로케이션 확률들을 계산할 때, HMM에 사용된 비터비 알고리즘은 측정된 신호 강도들의 히스토리와 관련하여 노드들에 걸친 모든 가능한 경로들에 대해 최적화함으로써 최상 위치를 찾는다. 과거 측정에 대한 상술된 점을 달성하는 다른 방법은 연속성이라는 장점을 갖는 칼만 필터(Kalman filter)를 사용하는 것이다. 그러나, 칼만 필터는, 보다 일반적인 HMM 공식이 허용하는 바와 같은, 본 명세서에서 부과된 경로 제약 종류를 허용하지 않으며 로케이션에 대한 다양한 형식의 확률 분포들을 표현하는 기능도 허용하지 않는다. HMM 공식에 대한 다른 대안은 로봇 집중화(localization)에 사용되어 온 파티클 필터이다. 파티클 필터는 동일한 종류의 경로 제약을 포함할 수 있지만, 계산을 위해 보다 많은 비용이 지출될 우려가 있다.

휴대형 장치의 이동 결정

상술된 바와 같이, 로케이션 추론은 장치의 이동 상태에 대한 추론을 고려한다. 즉, 고밀도 노드들의 쌍들 간의 전이 확률들을 사용하기 위해, 휴대형 장치의 이동 또는 결여가 고려돼야만 한다. 따라서, 장치가 이동중이거나 휴지 상태일 가능성이 결정될 필요가 있다. 다수의 AP들 및 장치들 간의 영역들에서 사람들이 걷는 것을 포함해서, 다수의 요인들로 인해, 시스템이 휴지 상태일 때라도, 다수의 AP들로부터의 IEEE 802.11 신호들의 강도가 무질서하게 변함에 따라 장치의 이동 상태 대 정지 상태에 대한 판별이 요구된다. 휴지 상태에서 상이한 AP들로부터의 신호의 "반짝임(twinkling)"이라는 점에서, 본 명세서에 기술된 방법들은 단 시간 윈도에 대해 상이한 AP들로부터의 신호들의 깜박거림 특성 및 정도를 검사함으로써 장치가 이동 상태인지 정지 상태인지에 대한 귀중한 추론들을 제공한다. 본 방법 이면의 핵심 사항은 장치가 정지 상태일 때 보다는 이동 상태일 때 통계 분석이 AP들로부터의 신호 강도들의 보다 큰 변화를 이용할 수 있다는 점이다; 신호 강도들은 통상 장치가 정지 상태일 때 보다는 이동 상태일 때 상이하게 변한다.

이제부터 도 6을 참조하면, 장치의 동적 상태를 결정하는데 사용되는 2상 마르코프 모델(600)의 상태도가 도시되어 있다. 도시된 바와 같이, 모델(600)은 이동 상태(602) 및 정지 상태(604)를 포함한다. 이동 상태에서 정지 상태로의 전이(606)는 a_MS로 정의되며, 정지 상태에서 이동 상태로의 전이(608)는 a_SM으로 정의된다. 장치가 이동 상태일 때는 a_MM으로 정의된 루프백 경로(610)로 표현된다. 유사하게, 장치가 정지 상태일 때는 a_SS로 정의된 루프백 경로(612)로 표현된다. 장치의 동적 상태(이동 대 정지)에 대한 HMM은 장치 로케이션에 대한 HMM과 상이함을 주지하라.

비평활화 상태 확률

이제부터, 도 5a를 참조하면, 시간에 따라 이동중인 장치의 비평활화 이후 확률 도면이 도시되어 있다. 상기 확률은 시간에 따른 신호 강도의 변화를 포착한 특징을 근거로 계산된다. 즉, 임의의 소정의 시간에, 가장 강한 신호를 갖는 액세스 포인트가 감지되고, 소정의 시간에 끝나는 짧은 기간동안 액세스 포인트의 신호의 편차가 계산된다. 휴대형 컴퓨터 측정 시스템은 사무실 내에서 측정 신호 강도들을 번갈아 검토 및 정지함으로써 라벨링된 신호 강도들의 집합을 수집함으로써 훈련된 데이터 수집 프로그램을 사용한다. 상기 프로세스는 신호 강도들을 기록하면서 30분 동안 실행된다. 데이터 수집 프로그램은 또한 무선 연결 랩탑이 이동중이었는지 아니었는지를 기록한다. 편차는 20-샘플 윈도로 계산되며, 3.16Hz의 샘플링 레이트에서 대략 63 판독/액세스 포인트로 해석된다.

이제부터 도 7을 참조하면, 상술된 바와 같이, 정지 및 이동 경우들에 대한 편차들의 히스토그램 도면(700)이 도시되어 있다. 최대 현 신호 강도의 윈도 편차(windowed variance)를 나타내기 위해 σ² _max를 사용해서, 히스토그램은 조건 확률 분포들 p(σ² _max│still) 및 p(σ² _max│moving)을 나타내는데 사용된다. σ² _max의 값이 주어지면, 이동 확률, p(moving│σ² _max), 및 정지 확률, p(still│σ² _max) = 1 - p(moving│σ² _max)에 대한 추정값들이 구해진다. 베이즈 규칙 분류기를 사용해서, 클라이언트 이동 이후의 확률은 다음과 같다고 할 수 있다.

여기서, p(still) 및 p(moving)은 장치의 동적 상태의 이전 확률들이다. 이전 확률들에 대한 임의의 다른 정보를 대신해서, 상기 확률들은 모두 0.5로 설정된다.

훈련 데이터 후에 수일 동안 취해진 3200개의 테스트 판독들의 집합에 대한 히스토그램들을 사용해서, 장치가 "정지 상태"였는지 "이동 상태"였는지에 대한 범주 분류는 대략 데이터의 85%가 정확하게 실행되었다. 이러한 방식으로 계산된 시간에 따른 이후 확률들은 도 5a에 도시되어 있다.

베이즈 규칙 분류기를 사용하는 대신, 본 발명은 본 발명의 다양한 양상들을 실행하기 위해 다양한 통계 분석들을 사용할 수 있음을 주지하라. 예를 들어, 동기 프로세스를 위해 어떤 행선이 선택될지를 결정하기 위한 프로세스는 자동 분류 시스템 및 프로세스를 통해 용이하게 실행될 수 있다. 이러한 분류는 사용자가 자동으로 실행되기를 희망한다는 액션을 예지 또는 추론하기 위해 확률 및/또는 통계-근거 분석(예를 들면, 분석 유틸리티들 및 비용들로 인수 분해함)을 사용할 수 있다. 예를 들어, 베이즈 네트워크 모델 또는 SVM(support vector machine) 분류기가 사용될 수 있다. 다른 분류 기법은 결정 트리들을 포함한다. 본 명세서에서 사용된 분류는 또한 우선 순위 모델들을 생성하는데 사용되는 통계 회귀를 포함한다. 상기 모델들은, 최대 신호 및 다른 신호들 간의 관계에 대한 고려 사항들, 시간에 따른 신호에 대한 상이한 분포 모드들, 및 관련 강도들의 통지들과 같이, 다수의 AP들로부터의 신호들에 대한 분포 구조 세부 사항들을 포함해서, 총 편차 이면의 다수의 관측 사항들을 고려한다.

평활화 상태 확률

이제부터, 도 5b를 참조하면, 시간에 따라 이동하는 장치의 평활화된 이후 확률들을 도시한 도면이 도시되어 있다. 3200 테스트 포인트들에 대한 시간 함수로서 비평활화 이동 확률, p(moving│σ² _max)의 도면은 도 5a에 도시되어 있다. 명백하게, 비평활화 이후 확률은 프로세스가 모델링되면 너무 자주 하이에서 로우로 점프한다. 사람들 및 그들의 장치들은 정지 상태에서 이동 상태로 자주 전이하지 않기에, 정지 상태 및 이동 상태를 관리하는 명확한 전이 확률들을 부과함으로써 이후 확률들을 평활하하는 것이 바람직하다. 도 5c는 도 5a 및 도 5b의 평활화 및 비평활화 확률 도면들에 대한 실제 데이터를 도시한 것이다.

시간 T의 상태 q_T의 확률을 해당 시간의 싱글 피처(single feature) σ² _max _.T로부터 간단히 추정하는 대신, 상태들 Q = q₁, q₂, ... q_T의 가장 유사한 시퀀스가 관측 사항들 O = σ² _max _.1, σ² _max _.2, ..., σ² _max _.T의 시퀀스로부터 구해진다. 이러한 경우에, 오직 2개의 가능한 상태들, 즉, 정지 상태 및 이동 상태가 존재한다. 따라서, q_t ∈ {S,M} 이다. 편의상, 먼저, 상태들 간의 전이를 관리하기 위해 마르코프 가정이 사용되는데, 이는 현 상태 확률이 가장 최근의 상태를 제외한 모든 상태들로부터 독립적임을 의미한다. 따라서, P(q_t ₊₁ = j│q_t = i) = a_ij이며, a_ij는 전이 확률이고 i,j ∈ {S,M} 이다.

전이 확률들은 사람 동작에 대한 가정들로부터 추정될 수 있다. 사람이 s초 동안 m만큼 이동한다고 제안된다. 신호 강도 샘플링 레이트가 r이면, 해당 시간 기간에 총 s/r개의 샘플들이 될 것이다. 상기 샘플들 중 한 샘플에서 발생하는 이동 확률은 mr/s 이다. 각각의 정지 상태-이동 상태 전이(SM)는 결국 이동 상태-정지 상태 전이(MS)에 의해 수반된다고 생각된다.

min() 함수는 범위 내에서 전이 확률을 유지한다. a_SS 및 a_MM에 대한 이 수학식은 a_SS + a_SM = a_MM + a_MS =1이라는 제약으로부터 나온다.

일반적인 회사원에 대해서, 10 이동(즉, m=10)은 하루 8시간에 한번, s=28,800초에 일어난다. 라디오 신호 강도 지시자(RSSI) 샘플링 레이트 3.16 Hz에서, a_SM 및 a_MS의 값들은 다음으로 계산된다.

마르코프 모델의 또 다른 요소는 정지 또는 이동 상태, 각각 π_S 및 π_M에 있을 초기 확률이다. 다른 정보가 부족하기 때문에, 양자는 0.5로 설정된다.

상태들이 바로 관찰될 수 없기 때문에, 마르코프 모델은 실제로 "히든(hidden)"이다. 각 샘플 시간 t에서 관찰되는 것은 σ² _max _.t이고, p(σ² _max _.t│q_t = still) 및 p(σ² _max _.t│q_t = moving)를 통해 실제 상태와 확률적으로 연결되어 있다.

HMM에 필요한 모든 요소들, 즉 상태, 전이 확률, 초기 상태 확률, 및 관찰 확률이 이제 결정된다. 비터비 알고리즘이 현재 시간 T에서 이후의 상태 확률 P( q _t = still│O) 및 P( q _t = moving│O)을 계산하기 위해서 사용된다. 비터비 알고리즘은 모든 과거 관찰 O =σ² _max _.1, σ² _max _.2,...,σ² _max _.T에 근거한 상태 확률를 계산하는 효율적인 방법을 제시한다. 이 알고리즘은 회귀적이어서 이전 관찰의 스토리지를 요구하지 않는다. 그러므로, T에서의 관찰 중에 이 알로리즘을 구동함으로써, 모든 이전 관찰들이 절대적으로 고려하게 된다. 이 효율성 때문에, 비터비 알고리즘이 매 새로운 관찰마다 재구동된다.

HMM을 사용하는 전체 효과는 전이 확률이 상태-조건 확률 밀도들 p(σ² _max _.t│q_t = still) 및 p(σ² _max _.t│q_t = moving)의 약간의 변화로 인한 상태 변경을 시스템이 더 싫어하게 만드는 경향이 있다는 점이다. 그러나, σ² _max의 몇몇 값들의 경우, 상기 밀도들 중 하나 또는 둘 다가 0으로 되는데, 그 이유는 σ² _max의 히스토그램 저장소가 훈련 중에 다 채워지지 않았기 때문이다. 밀도들 중 단지 하나만 0이면, 반대 상태에 대한 증거가 약하더라도, 또한 반대 상태로 전이될 확률이 매우 낮더라도, 해당 상태일 확률도 0이 된다. 덜 완전한 훈련 데이터로 인해 상기 경우의 상태 변동에 대한 평활화를 돕기 위해, 상태-조건 확률들에 약간의 오프셋을 추가하는 표준 수학적 조치가 사용된다. 특히, 다음과 같다.

α는 α= 0.01로 선택되며, p'(.)는 HMM의 p(.) 대신 사용된다. 오프셋이 확률 밀도들(통계가 1임)의 가장 기본적인 특징들 중 하나를 위반해도, 훨씬 더 양호하게 평활화 작업을 달성한다.

상기와 같이 계산된 전이 확률들 및 α-오프셋을 사용해서, 상태-조건 밀도 P(q_t = moving│O)가 3200-포인트 테스트 데이터 집합의 각각의 샘플에 대해 계산된다. 도 5b는 결과 도면을 도시한 것이다. 이는 전이 확률들 및 과거 상태 감지를 사용해서 어떻게 훨씬 덜 급변하는 상태 확률들을 달성하는지를 보여준다. HMM 평활화를 사용해서 분류 에러율은 대략 15.5%에서 12.6%로 떨어진다. 분류 정확성의 이득은 작고, 실제 이득은 거짓으로 보고된 상태 전이들을 감소시킨다. 테스트 집합에서는 실제로 14번 전이되었다. 비평활화 분류는 172 전이(158-너무 많음)를 보고하며, 평활화 분류는 24 전이(10개만 너무 많음)를 보고한다. 무선 장치의 집중화(본 아키텍처에서 중요한 양상) 및 사용자 문맥 추론을 돕기 위해서는 거짓 전이들을 감소시키는 것이 중요하다. 문맥이라는 점에서, 장치가 이동중이라고 판정되면, 장치를 휴대한 사람이 로케이션들 간에서 이동중이어서, 회의중이 아니고 사무실에 있지 않을 수 있음을 의미한다.

로케이션 전이 확률

이전 섹션은 Wi-Fi 장치가 이동 상태일 확률을 계산하는 방법을 보여주었다. 이는 로케이션 노드들 간의 전이 확률들을 계산하는 인자들 중 하나이며, 결국 HMM이 로케이션을 계산하는데 사용된다. 실제로, 주변 노드들로의 전이 확률들은 너무 멀리 있는 노드들로의 전이 확률들 보다 더 큰 것이 바람직하다. 이동을 양자화 하기 위해, 상술된 최단 경로 거리들이 사람 보행 속도들의 확률 분포와 함께 사용된다. 보다 정확한 속도 분포를 위해, HMM-평활화 추정값 p(moving│σ² _max)이 상술된 설명으로부터 사용된다.

노드들 간의 속도

사람 보행 속도들의 확률 분포가 이제부터 유도될 것이다. 사무실 빌딩에서, 사람들은 대부분 여기저기 걸어 다닌다. 보행 속도 분포는 종래의 연구들로부터 획득될 수도 있는 사람 보행 속도들의 분포, 도 8의 도면을 사용해서 추정될 수 있다. 보행 속도 분포는 수학적으로 P(walking speed│moving)로 표시된다. 또한, 사람들은 종종 발을 끌며 천천히 여기저기 다니기도 하며, 때때로 전력 질주하기도 한다. 이러한 행동은 0 내지 최대 대략 10.22미터/초(사람들의 최대 뛰는 속도의 추정값)의 일정 속도 분포로 모델링되며, 수학적으로 P(other speed│moving)로 표시된다. 사람이 이동중일 때, 사람들은 걷는데 ω를 소비하고, 몇몇 다른 속도로 나머지 시간을 소비한다고 가정된다. 사람이 이동중이면, 속도 분포는 다음과 같다.

여기서 s는 미터/초의 속도를 나타내고, ω는 0.9이다.

절대적 P(s)는 이전 섹션의 동적 추론으로부터 유래된 사람이 이동 상태이거나 정지 상태일 확률을 고려한다. 이들을 간단히 P(moving) 및 P(still)이라고 하며, P(s)는 다음과 같이 정의된다.

여기서, 사람 보행 속도가 정지 상태일 때 0이기 때문에, P(s│ still) = δ(0)이다. 여기서, δ(x)는 디락 델타 함수(Dirac delta function)이다. 이는 사람이 이동중이라고 생각되는지의 여부를 근거로, 또한, 이동중이라고 생각되면, 보행 속도 분포 및 최대 가능 뛰는 속도를 근거로, 사람 보행 속도들의 확률 분포를 제공한다.

전이 확률

2개의 로케이션 노드들 간의 전이 확률은 노드들 간의 거리를 횡단하는데 필요한 속도로 사람이 이동하는 확률에 비례한다. 장치가 노드 i에서 노드 j로 이동했으면, 속도는 rd_ij이어야만 했다. 여기서, 상술된 바와 같이, r은 RSSI 샘플링 레이트(예를 들어, 본 일례에서는 3.16 Hz)이고, d_ij는 2개의 노드들 간의 최단 경로 거리이다. 상기 속도를 관측할 확률은 p_ij = P(s = rd_ij)이다. 노드로부터 발산하는 모든 전이 확률들의 합계가 1이 되도록 상기 확률들은 정규화되어야만 한다. 따라서, 전이 확률은 다음과 같다.

여기서, N = 317이며, 로케이션 노드들의 수이다. 이는 노드들에 걸친 가장 알맞은 경로를 계산하는데 사용되는 전이 확률이다. 상기 확률은 평면도 레이아웃 및 장치 속도에 대해 인식된 바를 요약한다. a_ij가 시간에 따라 변하는 P(moving)의 함수이기 때문에, a_ij는 매 시간 단계마다 다시 계산돼야만 한다. 가장 알맞은 경로를 계산하는데 사용되는 비터비 알고리즘은 과거 전이 확률들을 기억할 필요가 없어서, 갱신이 요구된다고 메모리 필요성이 증가되는 것은 아니다.

신호 강도 관측 가능성

로케이션을 추론할 때, 장치의 신호 강도들이 빌딩의 상이한 로케이션 노드들에서 교정 중에 미리 결정된 신호 강도 확률 분포들에 대해 비교된다. 미리 결정되는 신호 강도 분포들은 장치를 물리적으로 소지하는 것으로부터 인식된 교정 노드들의 집합까지의 데이터를 근거로 추정된다. 정직한 방법은 교정을 위해 N = 317개의 모든 고밀도 로케이션 노드들을 모두 방문하는 것이다. 각각의 교정 포인트에서 약 60초가 소비되기 때문에, 각각의 로케이션 노드에서의 교정은 무제한적이다. 대신, 훨씬 적은 수의(본 일례에서는 63개의) 로케이션들에서 교정 판독이 이루어져서, 고밀도 로케이션 노드들에서 보간하는데 사용된다. 이는 고밀도 로케이션 노드 그래프에서 사용되는 포인트들의 수의 약 20%에 대해 교정이 달성되었음을 의미한다.

신호 강도 분포 수집

이제부터 평면도에 따라 신호 강도들이 어떻게 수집되며 신호 강도 확률 분포들이 어떻게 모든 고밀도 로케이션 노드들에 보간되는지가 설명된다.

이제부터 도 9를 참조하면, 교정 데이터의 신호 강도 로깅을 용이하게 하기 위한 데이터 수집 프로그램의 그래픽 사용자 인터페이스(GUI; 900)의 스크린샷이 도시되어 있다. GUI(900)는 도 3a의 평면도 및 룸(room)들의 그래픽 표현(902) 디스플레이를 용이하게 해준다. 사용자는 마우스, 키보드, 또는 다른 종래의 입력 장치를 통해 평면 표현(902)으로부터 (x,y) 로케이션을 선택함으로써 휴대형 수신 장치의 로케이션을 나타낸다. 추가로, 주변 송신기들로부터 측정된 신호 강도들의 표현을 디스플레이하는 신호 강도 지시자 도면(905)을 제공하기 위한 신호 강도 서브윈도(905)가 제공된다. 예를 들어, 제1 바(906)는 교정되는 현 층의 송신기로부터 신호가 수신되었음을 나타내는 제1 컬러 또는 채움 패턴을 포함한다. 신호 강도 데이터, 룸이 위치한 층, 및 송신기의 룸 번호를 나타내는 데이터(908)(예를 들어, 113/3/3327)는 바(906)와 관련된다. 특정한 본 일례에서, 송신기는 빌딩 번호(113), 3층(3)의 룸 번호 3327(또는 그래픽적으로 (910)으로 표시됨)의 송신기였다.

제2 바 식별(912)은 교정되는 현 층이 아닌 다른 층들의 송신기들로부터 수신된 측정들을 나타내는데 사용될 수 있다. 바(912)는 빌딩 113의 4층의 룸 4327인 룸 113/4/4327과 관련된다. GUI는 인터페이스 특징들을 제공하는데 흔히 유용한 발광 바, 및 텍스트, 오디오 출력 신호들 등을 포함해서, 신호들을 측정하기 위해 아주 다양한 그래픽 응답들을 제공하도록 프로그램될 수 있음을 알 것이다.

인터페이스(900)는 또한 사용자가 맵 줌 서브윈도를 통해 층 맵에 줌인해서, 층 선택 서브윈도를 통해 교정을 위한 층을 선택할 수 있게 해주는 로케이션 입력 서브윈도(914)를 포함한다.

인터페이스(900)는 신호 검출을 위한 스캔률(Hz)을 선택하기 위해 스캔 제어 서브윈도(916)를 더 포함한다. 사용자는 또한 로깅 경로 필드(918)를 통해 수신 장치에서 데이터가 로케이션에 로깅하게 할 수 있다. 사용자는 또한 경로 필드(918)에서 대응 네트워크 경로를 입력함으로써 원격 네트워크 기억 로케이션을 선택할 수도 있다. 입력되면, 모든 데이터는 지정된 파일 로케이션에 자동으로 기억된다.

IEEE 802.11 신호 강도 분포들이 무선 연결 랩탑 컴퓨터를 가지고 빌딩의 상이한 저밀도 교정 노드들로 가서 상기 로케이션들의 신호 강도들을 측정함으로써 수집되었다. 63-저밀도 노드 로케이션들은 도 3a에 도시되어 있다. 휴대형 컴퓨터는 로케이션들 및 신호 강도들을 모두 기록하기 위해 데이터 수집 프로그램을 실행했다. 도 9에 도시된 한 인터페이스 윈도, 프로그램은 사용자가 모든 "가시적" IEEE 802.11 액세스 포인트들로부터 신호 강도들을 기록하는 동시에 평면도 맵에서 클릭함으로써 자신의 로케이션을 나타낼 수 있게 해준다. 맵은 교정을 위해 장치의 근접 로케이션을 나타내는 것을 쉽게 해준다. 이처럼 맵을 사용하는 다른 대안은 해당 층에서 포인트들을 측정하는 것이다. 그러나, 이는 큰 빌딩에서 교정하는데 드는 시간이 무제한적이 된다. 따라서, 맵의 위치들은 맵에서 식별하기 쉬운 로케이션들, 예를 들어, 사무실 중심들 및 보도 교차점들에서 서 있음으로써 추정되었다. 교정 로케이션들은 맵에서 위치들을 선택함으로써 결정될 수 있는 한 정확하게 결정되었다. 그러나, 이는 실제로 보다 큰 지역에 대한 교정 노력을 감소시키기 위해 필요한 타협책이다.

각각의 교정 로케이션 노드에서, 도 3c에 도시된 바와 같이, 신호 강도 판독들은 60초 동안 취해졌으며, 장치는 제자리에서 천천히 회전했다. 회전 양상은 방위 결과의 요인이 되었다. 이는 방위를 명확하게 모델링 및 기록하는 종래의 시스템과 대조된다. 이러한 데이터의 경우, 각각의 교정 포인트에 대해, 소정의 액세스 포인트를 볼 확률 및 해당 액세스 포인트로부터의 신호 강도들의 확률 분포를 기술하는 이산 확률 분포들이 구성되었다. 수학적 관점에서, 교정 포인트들은 x _i ^(c)이고, i = 1...N_c 이며, 빌딩의 액세스 포인트들은 AP_i로 지정되며, i = 1...N_AP 이다. 교정 로케이션 x _j ^(c)으로부터 액세스 포인트 AP_i를 검출할 확률은 p(AP_i│x _j ^(c))이다. 상기 확률은 액세스 포인트가 검출된 횟수 대 소정의 교정 노드에서 교정 중에 모든 액세스 포인트들이 스캔된 횟수의 비율에 의해 간단히 추정되었다. (3.16Hz 스캔률로 60초 동안 스캐닝한 것은 매 로케이션으로부터 모든 액세스 포인트들을 대략 190회 질의한 것으로 해석됨을 주지하라.) 상기 확률은 액세스 포인트 범위 밖에 있는 경우는 0으로 예상되며, 액세스 포인트 범위 내에 있는 경우는 0으로 예상될 수 있다. 본 실험은, 도 7에 도시된 바와 같이, 확률이 0 내지 1 사이의 값들을 취함을 보여 준다. 도 7은 모든 액세스 포인트들 및 모든 교정 노드 로케이션들에 대한 관측 값들, p(AP_i│x _j ^(c))의 히스토그램을 도시한 것이다. 이러한 편차가 제공되면, 상기 효과를 모델링하는 것이 중요하다.

액세스 포인트로부터의 신호들이 소정의 로케이션으로부터 측정 가능했으면, 신호 강도들의 정규화 히스토그램도 또한 p(s_k≤s<s_k ₊₁│AP_i,x _j ^(c))을 나타내는 것으로구성되었다. 여기서 s는 신호 강도이며 s_k는 히스토그램 저장소의 에지들이다. 본 구현에 있어서, s_k는 30개의 단계들에서 -120 dBm 내지 0 dBm 범위이다. (dBm은 데시벨 밀리와트를 표기한 것이며, IEEE 802.11 신호 강도를 위한 통상의 단위임을 주지하라.) 교정의 총 결과는 얼마나 자주 소정의 액세스 포인트가 소정의 로케이션으로부터 관측될 수 있었는지와, 관측될 수 있는 경우, 신호 강도들의 분포를 모두 획득했다. 상기 확률들은 관측한 신호 강도들로부터 장치의 로케이션을 추론하는데 사용되는 신호 강도 기호들을 구현한다.

신호 강도 분포 보간

63개의 교정 포인트들은 대략 평균 2.64 미터들로 각각의 포인트의 가장 가까운 이웃으로부터 비교적 넓게 간격을 두고 있다. 교정 노드들 보다 더 밀접한 간격을 갖는 로케이션 노드들의 집합으로 보다 높은 공간 해상도를 달성하는 것이 바람직하다. 도 3a에 도시된 바와 같이, 고밀도 로케이션 노드들은 교정 노드들 보다 훨씬 더 밀접하다. 밀접한 집합의 로케이션 노드들에 대해서 로케이션을 추론하기 위해, 신호 강도 기호들은 고밀도 로케이션 노드들 각각에서 계산될 필요가 있다. 이는 교정 노드들의 산재 집합의 확률 분포들이 고밀도 노드들의 보다 밀접한 집합으로 확장될 필요가 있음을 의미한다. 이는 방사 기초 함수들을 사용해서 보간에 의해 달성된다.

교정 노드들에서 취해진 교정 측정값들로부터, 교정 포인트들의 확률들이 구해진다: p(AP_i│x _j ^(c))는 교정 포인트 x _j ^(c)로부터 소정의 액세스 포인트를 볼 확률을 나타내며, p(s_k≤s<s_k ₊₁│AP_i,x _j ^(c))는 교정 포인트 x _j ^(c)에서 액세스 포인트 AP_i로부터 본 신호 강도들의 분포를 나타낸다. 원하는 바는 고밀도 로케이션 노드들, x _i ^(l)에서의 확률들이다. 액세스 포인트 확률들은 교정 포인트들에서 샘플링된 연속 함수로 간주될 수도 있다. 이처럼, 신호 강도 분포의 이산 확률들은 2차원 공간에 대한 연속 함수로 간주될 수도 있다. 보간을 용이하게 하기 위해, 각각의 교정 포인트의 신호 강도 특징들은 벡터 d _j ^(c)로 표현되며, d _j ^(c)는 액세스 포인트 확률들 및 교정 포인트 x _j ^(c)로부터의 신호 강도 분포의 이산 확률들로 구성된다. 보다 정밀하게 말하면, N_AP개의 액세스 포인트들이 있으면, 또한, 신호 강도들이 K개의 저장소들(즉, s_k, k = 1...K)로 이산화되면, 벡터 d _j ^(c)는 소정의 액세스 포인트를 볼 확률을 나타내는 N_AP개의 요소들을 가지며 추가로 각각의 액세스 포인트에 대한 신호 강도 분포들을 나타내는 KN_AP개의 요소들을 갖는다. (액세스 포인트가 교정 포인트 x _j ^(c)로부터 보이지 않았으면, 신호 강도 분포는 모두 0으로 설정된다.) 따라서, 목적은 교정 쌍들(x _j ^(c), d _j ^(c)), j = 1...N_c로부터 고밀도 로케이션 노드들 (x _i ^(l), d _i ^(l)), i = 1...N_l에 대한 확률들까지 보간하는 것이다.

상기 보간은 상기 태스크들을 위한 공통 선택 사항인 정규화된 방사 기초 함수를 사용해서 실행된다. 방사 기초 함수 공식은 선택된 포인트 x에 대한 d 벡터의 k번째 컴포넌트를 생성하기 위해 교정 포인트들에 집중된 2차원 기초 함수들의 집합의 가중된 합계를 달성하는 것이다.

커널 함수 K(r)의 경우, K(r) = exp(-r²/σ²)로 선택된다. 몇몇 실험후에, 시그마는 양호한 결과들을 산출한 파라미터로서 σ= 1.0으로 선택되었다. 웨이트들 β_jk은 교정 포인트들에 적합한 표준 최소 제곱법들로 계산되었다.

방사 기초 함수들은 매 로케이션 노드 x _i ^(l)마다 평가되었고, 확률 파라미터들의 대응 백터 d _i ^(l)를 산출한다. 파라미터들은 그 후 추출되어 액세스 포인트 확률들 p(AP_i│x _j ^(l)) 및 신호 강도 확률들 p(s_k≤s<s_k ₊₁│AP_i,x _j ^(l))을 형성하고, 비교적 드문 집합의 교정 포인트들에서의 확률들로부터 보다 밀접한 집합의 로케이션 노드들에서의 확률들이 추정되었다. 정규화 방사 기초 함수는 범위 [0,1] 에서 확률들을 산출할 것을 보장하지도 않으며, 확률 분포들의 통계가 1이 될 것을 보장하지도 않는다. 실제로, 적합한 범위를 복구하기 위해서 약간의 클램핑(clampping) 및 정규화가 필요하다.

HMM 을 사용한 로케이션 추론

HMM의 기본 인자들은 다음과 같이 요약되었다: 상태, 초기 상태 확률, 전이 확률, 및 관측 확률. 로케이션에 대한 HMM의 상태들은 드로잉 프로그램에 의해 산출된 고밀도 로케이션 노드들 x _i ^(l), i = 1...N_l이다. 장치가 위치한 장소에 대한 다른 데이터가 없을 때, 초기 상태 확률들 π_i, i = 1...N_l는 로케이션 노드들에 대해 균일하게 분포된다. 즉, π_i= l/N_l 이다. 전이 확률들은 상술된 바와 같으며, 빌딩의 레이아웃, 예상 보행 속도, 및 장치가 이동중인지에 대한 추론에 민감하다. 관측 확률들은 상술된 보간 확률들로부터 유래된다.

시간 T일 때 로케이션을 추론하는 경우, 장치는 모든 액세스 포인트들로부터의 신호 강도들에 대해 스캔한다. 결과는 액세스 포인트가 검출되었는지를 나타내는 N_AP개의 액세스 포인트들 각각에 대해 하나의 불 요소(Boolean element)를 갖는 지시자 벡터 I _T이다. 다른 결과는 각각의 검출된 액세스 포인트에 대한 신호 강도를 제공하는 신호 강도들의 벡터 s _T이다. 두 벡터들의 대응 요소들은 동일한 액세스 포인트에 대응한다. 액세스 포인트가 검출되지 않았으면, 액세스 포인트에 대한 신호 강도 값은 사용되지 않기에 임의의 값일 수 있다. 본 스캔을 볼 확률은 로케이션 x _i ^(l)에서 다음과 같다.

여기서, I_Tj는 I _T의 j번째 요소를 의미하고, s_Tj는 s _T의 j번째 요소를 의미한다. 상기 적(product)의 각각의 피승수(multiplicand)는 하나의 액세스 포인트를 나타내며, 각각의 액세스 포인트에 대한 스캔 결과가 다른 액세스 포인트들에 독립적임을 의미한다. j번째 액세스 포인트가 보여졌으면(I _Tj = true), 피승수는 관측 신호 강도 s_Tj에서 상기 액세스 포인트를 볼 확률을 나타낸다. j번째 액세스 포인트가 보이지 않았으면(I _Tj = false), 피승수는 상기 액세스 포인트를 보지 않을 확률을 나타낸다.

HMM 요소들은 고밀도 로케이션 노드들에 대한 상태 확률들의 집합, 즉, p_T(x _i ^(l))을 산출하기 위해 비터비 알고리즘과 결합된다. 최종 로케이션 추정의 경우, 로케이션의 예상 값은 다음과 같다:

평면도 일례에 대항해서 사용될 때 본 아키텍처는 교정 노력을 감소시키면서 동시에 정확성을 향상시킴으로써 종래의 시스템들에 대해 중요하게 개선된 사항들을 제공한다. 로케이션 노드들의 제약 및 역학이 주의 깊게 모델링되었기 때문에, 본 타입의 종래의 시스템들에 비해 교정이 감소되었음에도 불구하고 고 정확성이 유지된다. 본 일례에 대한 애플리케이션은 귀찮은 교정 수고 없이 대략 1.53미터의 중간 에러를 보여주었다. 로케이션 외에, 시스템은 또한 사용자 문맥의 중요한 지시자일 수 있는 장치가 이동중인지의 여부를 추론한다.

다수의 사무실 지역 공간들이 이미 IEEE 802.11 액세스 포인트들과 유선으로 연결되어 있으며, 보다 더 많은 이동 장치들이 무선 네트워크 하드웨어 장치를 가지게 될 것이기 때문에, IEEE 802.11 신호 강도들로부터 로케이션들을 계산하는 것은 흥미로운 일이다. IEEE 802.11 신호에 적용되었지만, 신규 아키텍처는, 센서 융합을 위한 플랫폼으로서 작용할 뿐만 아니라, 상술된 바와 같이, 다른 타입들의 로케이션 센싱에도 쉽게 적용될 수 있다.

이제부터, 도 10을 참조하면, 본 아키텍처를 실행하기 위해 동작할 수 있는 컴퓨터의 블록도가 도시되어 있다. 본 발명의 다양한 양상들을 위한 추가 문맥을 제공하기 위해, 도 10 및 이하의 설명은 본 발명의 다양한 양상들이 구현될 수도 있는 적합한 컴퓨팅 환경(1000)을 간단하고 일반적으로 설명하는 것을 목적으로 한다. 본 발명이 하나 이상의 컴퓨터들에서 실행될 수도 있는 컴퓨터 실행 가능 명령들의 일반적인 문맥으로 상술되었지만, 본 기술 분야에 숙련된 자들은 본 발명이 또한 다른 프로그램 모듈들과 결합해서 및/또는 하드웨어 및 소프트웨어의 결합물로서 구현될 수도 있음을 알 것이다. 일반적으로, 프로그램 모듈은 특정 태스크들을 실행하거나 특정 추상 데이터 타입들을 구현하는 루틴, 프로그램, 컴포넌트, 데이터 구조 등을 포함한다. 또한, 본 기술 분야에 숙련된 자들은 본 방법들이, 각각 하나 이상의 관련 디바이스들과 동작적으로 결합될 수도 있는 퍼스널 컴퓨터, 핸드헬드 컴퓨팅 디바이스, 마이크로프로세서-베이스 또는 프로그래머블 컨수머 일렉트로닉스 뿐만 아니라 싱글-프로세서 또는 멀티프로세서 컴퓨터 시스템, 미니컴퓨터, 메인프레임 컴퓨터 등을 포함하는 다른 컴퓨터 시스템 구성들로 구현될 수도 있음을 알 것이다. 본 발명의 일례의 양상들은 또한 통신망을 통해 연결된 원격 프로세싱 디바이스들에 의해 특정 태스크들이 실행되는 분산 컴퓨팅 환경들에서 구현될 수도 있다. 분산 컴퓨팅 환경에서, 프로그램 모듈은 국부적 및 원격 메모리 기억 장치들에 모두 위치할 수도 있다.

도 10을 다시 참조하면, 본 발명의 다양한 양상들을 구현하기 위한 일례의 환경(1000)이 프로세싱 유닛(1004), 시스템 메모리(1006) 및 시스템 버스(1008)를 포함하는 컴퓨터(1002)를 포함하는 것으로 도시되어 있다. 시스템 버스(1008)는 시스템 메모리(1006)를 포함하지만 이로만 제한되지 않는 시스템 컴포넌트들을 프로세싱 유닛(1004)에 결합시킨다. 프로세싱 유닛(1004)은 상업적으로 유용한 다양한 프로세서들 중의 임의의 프로세서일 수 있다. 듀얼 마이크로프로세서들 및 다른 멀티프로세서 아키텍처들이 또한 프로세싱 유닛(1004)으로서 사용될 수 있다.

시스템 버스(1008)는 메모리 버스 또는 메모리 컨트롤러, 상업적으로 유용한 다양한 버스 아키텍처들 중 임의의 아키텍처를 사용하는 주변 버스 및 로컬 버스를 포함하는 수개의 타입들의 버스 구조 중 임의의 구조일 수 있다. 시스템 메모리(1006)는 판독 전용 메모리(ROM; 1010) 및 랜덤 액세스 메모리(RAM; 1012)를 포함한다. 시동 중과 같이 컴퓨터(1002) 내의 소자들 간의 정보 전송을 돕는 기본 루틴들을 포함하는 기본 입출력 시스템(BIOS)은 ROM(1010)에 기억된다.

컴퓨터(1002)는 하드 디스크 드라이브(1014), 자기 디스크 드라이브(1016)(예를 들어, 제거 가능 디스크(1018) 판독 또는 기록) 및 광 디스크 드라이브(1020)(예를 들어, CD-ROM 디스크(1022) 판독 또는 다른 광 미디어 판독 또는 기록)를 더 포함한다. 하드 디스크 드라이브(1014), 자기 디스크 드라이브(1016) 및 광 디스크 드라이브(1020)는 각각 하드 디스크 드라이브 인터페이스(1024), 자기 디스크 드라이브 인터페이스(1026) 및 광 디스크 드라이브 인터페이스(1028)에 의해 시스템 버스(1008)에 연결될 수 있다. 드라이브들 및 관련 컴퓨터 판독 가능 매체들은 데이터, 데이터 구조, 컴퓨터 실행 가능 명령들 등의 비휘발성 스토리지를 제공한다. 컴퓨터(1002)의 경우, 드라이브들 및 매체들은 적합한 디지털 형태로 방송 프로그래밍 스토리지를 수용한다. 상술된 컴퓨터 판독 가능 매체들에 대한 설명은 하드 디스크, 제거 가능 자기 디스크 및 CD를 언급하지만, 본 기술 분야에 숙련된 자들은 컴퓨터에 의해 판독될 수 있는 다른 타입들의 매체들, 예를 들어, 집 드라이브, 자기 카셋트, 플래시 메모리 카드, 디지털 비디오 디스크, 카트리지 등이 본 일례의 운영 환경에서 사용될 수도 있으며, 임의의 매체들이 본 발명의 방법들을 실행하기 위한 컴퓨터 실행 가능 명령들을 포함할 수도 있음을 알 것이다.

오퍼레이팅 시스템(1030), 하나 이상의 애플리케이션 프로그램들(1032), 다른 프로그램 모듈들(1034) 및 프로그램 데이터(1036)를 포함하는 다수의 프로그램 모듈들이 드라이브들 및 RAM(1012)에 기억될 수 있다. 본 발명이 상업적으로 유용한 다양한 오퍼레이팅 시스템들 또는 오퍼레이팅 시스템들의 결합물들로 구현될 수 있음을 알 것이다.

사용자는 키보드(1038) 및 마우스(1040)와 같은 포인팅 디바이스를 통해 컴퓨터(1002)에 커맨드 및 정보를 입력할 수 있다. 다른 입력 장치들(도시되지 않음)은 마이크로폰, IR 리모트 컨트롤, 조이스틱, 게임 패드, 위성 접시, 스캐너 등을 포함할 수도 있다. 여타 입력 장치들은 종종 시스템 버스(1008)에 결합된 직렬 포트 인터페이스(1042)를 통해 프로세싱 유닛(1004)에 연결되어 있는데, 병렬 포트, 게임 포트, USB(universal serial bus), IR 인터페이스 등과 같은 다른 인터페이스들에 의해 연결될 수도 있다. 모니터(1044) 또는 다른 타입의 디스플레이 장치가 또한 비디오 어댑터(1046)와 같은 인터페이스를 통해 시스템 버스(1008)에 연결된다. 모니터(1044) 외에, 컴퓨터는 통상 스피커, 프린터 등과 같은 다른 주변 출력 장치들(도시되지 않음)을 포함한다.

컴퓨터(1002)는 원격 컴퓨터(들)(1048)와 같은 하나 이상의 원격 컴퓨터들로의 로지컬 커넥션들을 사용해서 네트워크 환경에서 동작할 수도 있다. 원격 컴퓨터(들)(1048)는 워크스테이션, 서버 컴퓨터, 루터, 퍼스널 컴퓨터, 휴대형 컴퓨터, 마이크로프로세서-베이스 엔터테인먼트 애플리케이션, 피어 디바이스 또는 다른 공통 네트워크 노드일 수도 있으며, 통상 편의상, 메모리 기억 장치(1050) 만이 도시되어 있지만, 컴퓨터(1002)와 관련되어 기술된 모든 소자들 또는 다수의 소자들을 통상 포함한다. 도시된 로지컬 커넥션들은 LAN(local area network; 1052) 및 WAN(wide area network; 1054)을 포함한다. 이러한 네트워크 환경들은 사무실에서 흔히 볼 수 있으며, 기업간 컴퓨터 네트워크, 인트라넷 및 인터넷이다.

LAN 네트워크 환경에서 사용될 때, 컴퓨터(1002)는 네트워크 인터페이스 또는 어댑터(1056)를 통해 로컬 네트워크(1052)에 연결된다. 어댑터(1056)는 무선 어댑터(1056)와 통신하기 위해 배치된 무선 액세스 포인트를 포함할 수도 있는 LAN(1052)으로의 유선 또는 무선 통신을 용이하게 해줄 수도 있다. WAN 네트워크 환경에서 사용될 때, 컴퓨터(1002)는 통상 모뎀(1058)을 포함하거나, LAN의 통신 서버에 연결되거나, 또는 인터넷과 같은 WAN(1054)을 통한 통신을 설정하기 위한 다른 수단을 갖는다. 내장될 수도 있고 외부에 설치될 수도 있는 모뎀(1058)은 직렬 포트 인터페이스(1042)를 통해 시스템 버스(1008)에 연결된다. 네트워크 환경에서, 컴퓨터(1002)와 관련해서 기술된 프로그램 모듈들, 또는 그 일부분들은 원격 메모리 기억 장치(1050)에 기억될 수도 있다. 도시된 네트워크 커넥션들은 일례의 것으로 컴퓨터들 간의 통신 링크를 설정하기 위한 다른 수단이 사용될 수도 있음을 알 것이다.

이제부터 도 11을 참조하면, 본 발명에 다른 일례의 컴퓨팅 환경(1100)의 개략 블록도가 도시되어 있다. 시스템(1100)은 하나 이상의 클라이언트(들)(1102)를 포함한다. 클라이언트(들)(1102)는 하드웨어 및/또는 소프트웨어(예를 들어, 스레드, 프로세스, 컴퓨팅 디바이스)일 수 있다. 클라이언트(들)(1102)는, 예를 들어, 본 발명을 사용함으로써 쿠키(들) 및/또는 관련 문맥 정보를 수용할 수 있다. 시스템(1100)은 또한 하나 이상의 서버(들)(1104)를 포함한다. 서버(들)(1104)는 또한 하드웨어 및/또는 소프트웨어(예를 들어, 스레드, 프로세스, 컴퓨팅 디바이스)일 수 있다. 서버들(1104)은, 예를 들어, 본 발명을 사용함으로써 변환을 실행하는 스레드를 수용할 수 있다. 클라이언트(1102)와 서버(1104) 간에 한가지 가능한 통신은 2개 이상의 컴퓨터 프로세스들 간에 송신되도록 적응된 데이터 패킷 형태일 수도 있다. 데이터 패킷은, 예를 들어, 쿠키 및/또는 관련 문맥 정보를 포함할 수도 있다. 시스템(1100)은 클라이언트(들)(1102) 및 서버(들)(1104) 간의 통신을 용이하게 하는데 사용될 수 있는 통신 프레임워크(1106)(예를 들어, 인터넷과 같은 글로벌 통신 네트워크)를 포함한다. 통신은 유선(광 섬유 포함) 및/또는 무선 기술을 통해 용이하게 될 수도 있다. 클라이언트(들)(1102)는 클라이언트(들)(1102)에 국부적인 정보(예를 들어, 쿠키(들) 및/또는 관련 문맥 정보)를 기억하는데 사용될 수 있는 하나 이상의 클라이언트 데이터 스토어(들)(1108)에 동작 가능하게 연결된다. 유사하게, 서버(들)(1104)는 서버들(1104)에 국부적인 정보를 기억하는데 사용될 수 있는 하나 이상의 서버 데이터 스토어(들)(1110)에 동작 가능하게 연결된다.

본 발명의 일례들이 상술되었다. 물론, 본 발명을 설명할 목적으로 컴포넌트들 및 방법들의 모든 가능한 결합을 다 기술할 수는 없지만, 본 기술 분야에 숙련된 자들 본 발명의 다수의 다른 결합들 및 변경들이 가능함을 알 수 있다. 따라서, 본 발명은 첨부된 청구항들의 원리 및 범위 내에 속한 모든 대안물, 수정물 및 변경물을 포함한다. 더나아가, '구비하는' 이라는 용어가 상세한 설명 또는 청구범위에서 사용된 의미 정도에 관해서는, 그 의미가 '포함하는' 이라는 용어가 청구범위에서 전이 단어로서 채택될 때 해석되는 것과 유사하게 포함할 수 있다는(inclusive) 뜻으로 의도한 것이다.

100 : 시스템 102 : 측정 컴포넌트
104 : 신호 강도 106 : 확률 프로세싱 컴포넌트
108 : 예상 로케이션 값 600 : 2상 마르코프 모델
602 : 이동 상태 604 : 정지 상태
900 : 그래픽 사용자 인터페이스

Claims

무선 장치의 로케이팅(locating)을 용이하게 하는 로케이션 시스템으로서,
특정 지역 내의 식별된 로케이션들을 하나 이상의 로케이션 노드들에 매핑하고, 상기 특정 지역의 그래픽 표현을 그래픽 사용자 인터페이스에 디스플레이하는 컴퓨터-베이스 매핑 컴포넌트(computer-based mapping component);
신호 강도를 측정하고 상기 하나 이상의 로케이션 노드들에 관련된 신호 강도 데이터를 저장하는 측정 컴포넌트; 및
소정의 한 쌍의 로케이션 노드들 간에, 상기 특정 지역과 연관된 적어도 부분적으로 경로 제약들의 함수로서 상기 무선 장치와 연관된 전이 확률을 자동으로 산출하고,
상기 신호 강도 데이터를 근거로 한 회귀 함수(regression function)를 사용하여 상기 무선 장치의 로케이션을 결정하는 것, 및 특정 시간 간격에 따른 상기 신호 강도 데이터의 편차를 적어도 부분적으로 측정함으로써 상기 무선 장치의 이동을 결정하는 것 중 적어도 하나를 행하는 확률 프로세싱 컴포넌트 - 상기 회귀 함수는 상기 신호 강도 데이터를 근거로 하여 새로운 로케이션들을 추정함 -
를 포함하는, 무선 장치의 로케이팅을 용이하게 하는 로케이션 시스템.
제1항에 있어서,
상기 매핑 컴포넌트는 상기 무선 장치가 상기 식별된 로케이션들로 이동할 수 있는 가능한 경로들의 표현을 제공하는, 무선 장치의 로케이팅을 용이하게 하는 로케이션 시스템.
제1항에 있어서,
상기 매핑 컴포넌트는 상기 무선 장치가 이동할 수 있는 모든 식별된 로케이션들, 및 상기 무선 장치가 상기 식별된 로케이션들로 이동할 수 있는 가능한 경로들의 그래픽 표현을 제공하는, 무선 장치의 로케이팅을 용이하게 하는 로케이션 시스템.
제1항에 있어서,
상기 매핑 컴포넌트는 인접 로케이션 노드들 및 비인접 로케이션 노드들에 에지 웨이트(edge weights)들을 할당하는 기능을 제공하는, 무선 장치의 로케이팅을 용이하게 하는 로케이션 시스템.
제1항에 있어서,
상기 매핑 컴포넌트는 상기 식별된 로케이션들로의 경로들을 표현하고 각각의 경로의 엔드포인트(endpoint)를 로케이션 노드(location node)의 한 타입인 엔드 노드(end node)로 자동으로 변환하는, 무선 장치의 로케이팅을 용이하게 하는 로케이션 시스템.
제5항에 있어서,
상기 매핑 컴포넌트는 선정된 공간 기준에 따라 이전에 위치된 로케이션 노드들 중에 하나 이상의 중간 로케이션 노드를 자동으로 분산시키는, 무선 장치의 로케이팅을 용이하게 하는 로케이션 시스템.
제1항에 있어서,
상기 무선 장치의 예상 속도는 사람 보행 속도들의 확률 분포에 대한 고려, 및 상기 무선 장치가 이동 중인지의 여부에 대한 추론을 근거로 하여 계산되는, 무선 장치의 로케이팅을 용이하게 하는 로케이션 시스템.
제1항에 있어서,
상기 매핑 컴포넌트는, 두 개의 대응되는 식별된 로케이션들 간의 물리적 장벽을 고려하는 제약-민감 경로-계획 알고리즘을 근거로 하여, 상기 로케이션 노드들 중 두 로케이션 노드들 간의 최단 경로를 유도하는, 무선 장치의 로케이팅을 용이하게 하는 로케이션 시스템.
제1항에 있어서,
상기 측정 컴포넌트는 상기 식별된 로케이션들을 포함하는 지역 도처에 배치된 네트워크로 연결된 송신 장치들의 신호 강도들을 측정하는, 무선 장치의 로케이팅을 용이하게 하는 로케이션 시스템.
제1항에 있어서,
상기 확률 프로세싱 컴포넌트는 각각의 로케이션 노드에서 수신된 신호 강도들을 근거로 하여 로케이션 노드들 각각에 대한 관측 확률을 산출하는, 무선 장치의 로케이팅을 용이하게 하는 로케이션 시스템.
제1항에 있어서,
상기 확률 프로세싱 컴포넌트는 경로 제약, 이동 확률 데이터, 및 속도 분포 데이터를 사용하여 전이 확률 데이터를 자동으로 산출하고 상기 로케이션 노드들과 연관시키는, 무선 장치의 로케이팅을 용이하게 하는 로케이션 시스템.
제1항에 있어서,
상기 확률 프로세싱 컴포넌트는 관측된 신호 강도들의 모든 집합에 대해 모든 로케이션 노드들에 대한 확률 분포를 산출하기 위해 비터비 알고리즘을 사용하는, 무선 장치의 로케이팅을 용이하게 하는 로케이션 시스템.
제1항에 있어서,
상기 회귀 함수는 상기 로케이션 노드들의 확률 분포를 새로운 로케이션들로 확장하는 보간 함수인, 무선 장치의 로케이팅을 용이하게 하는 로케이션 시스템.
제1항에 있어서,
상기 확률 프로세싱 컴포넌트는 측정된 신호 특성들의 히스토리에 관련하여 식별된 로케이션들 간의 모든 가능한 경로들에 걸쳐 최적화하기 위해 최대-가능성 디코딩 알고리즘을 사용하는, 무선 장치의 로케이팅을 용이하게 하는 로케이션 시스템.
제1항에 있어서,
상기 확률 프로세싱 컴포넌트는 최대 강도 신호를 가지는 무선 송신기를 감지함으로써 무선 송신기의 신호 강도의 편차를 양적으로 포착하고, 시간에 따른 최대 강도 신호의 편차를 계산하는, 무선 장치의 로케이팅을 용이하게 하는 로케이션 시스템.
그래픽 사용자 인터페이스에 특정 지역의 그래픽 표현을 디스플레이하기 위한 수단;
무선 장치와 연관되고 상기 특정 지역 내에 위치된 식별된 로케이션들과 관련된 신호 특성들을 측정하기 위한 수단;
상기 무선 장치의 이동 추론을 결정하기 위한 수단; 및
상기 특정 지역과 연관된 경로 제약, 상기 이동 추론, 및 상기 무선 장치와 연관된 상기 신호 특성들의 함수로서 전이 확률들을 근거로 하여 상기 무선 장치의 로케이션을 추정하기 위한 수단
을 포함하는, 무선 장치 로케이션 시스템.
이동 장치의 로케이션 역학을 결정하는 방법으로서,
그래픽 사용자 인터페이스에 지역에 대한 그래픽 표현을 제공하는 단계;
이동 장치와 연관되고 식별된 로케이션들에 관련된 신호 특성들을 평가하는 단계;
시간에 따른 상기 신호 특성들의 편차를 근거로 하여 상기 이동 장치의 이동 추론을 계산하기 위해 확률 데이터를 사용하는 단계; 및
상기 지역과 연관된 경로 제약, 상기 이동 추론, 및 상기 이동 장치와 연관된 신호 특성들의 함수로서 전이 확률을 근거로 하여 상기 이동 장치의 로케이션을 추정하는 단계
를 포함하는, 이동 장치의 로케이션 역학을 결정하는 방법.