Home

초기의 SRS는 센서 데이터를 상호운용성 향상 및 끊김 없는 서비스 제공을 위해 제안되었다[9]. SRS는 센서에 대한 메타데이터를 서버에 등록하고 관리하기 위한 시스템이며, 사용자는 센서로부터 직접 받은 데이터에 대하여 어떤 의미를 지니는지와 같은 정보를 SRS로부터 받는다. 이후 사물인터넷 환경을 적용하기 위해 시맨틱 센서 네트워크 온톨로지를 접목시킨 연구도 진행되었다[10].

하지만 SRS는 활용성 저하 및 네트워크 지연과 같은 문제가 존재한다. 즉, 기존의 SRS는 사용자가 센서로부터 데이터를 받은 후에 SRS로 접근하여 해당 센서에 대한 메타데이터를 받는 구조로, SRS로부터 받은 메타데이터가 사용자의 상호운용성 향상 및 끊김없는 서비스로 이어지기 위해서는 어느 정도 시간이 지연되는 문제점을 지닌다. 따라서 사용자의 위치 정보를 이용하여 위치 주변의 센서들을 미리 받기 위한 연구가 진행되었다[8][11].

PP-SRS는 사용자의 현재 위치로부터 이동 경로를 예측하고 예측된 경로 주변의 센서 정보들을 사용자에게 미리 제공한다[8]. 이는 사용자 주변에 존재할 수 있는 많은 센서와 이에 기반한 정보들 중 사용자가 활용할 수 있을 만한 정보만을 추출하는 효율적인 센서 필터링 방식이다.

한편, NC-SRS는 PP-SRS가 모바일 네트워크가 불안정한 지역에서는 안정적인 센서 정보 제공이 불가능하다는 문제를 해결하기 위하여 제안되었다[11]. PP-SRS는 기본적으로 모바일 디바이스를 이용한 연구이기 때문에 지역에 따라 네트워크 자체의 문제로 인해 SRS의 접속이 불안정한 경우에는 사용자가 해당 지역으로 접근할 경우 해당 지역의 센서 정보들을 모두 받아온다. 네트워크 접속의 안정성 판별을 위하여 모바일 네트워크 커버리지 정보를 이용한다. 네트워크 커버리지 정보는 모바일 크라우드 센싱(Mobile Crowd-sensing)을 이용한 OpenSignal[12]에서 제공하는 공개 정보를 활용하였다.

CRPM은 격자 경로 표현기반의 개인화 경로예측 시스템을 제안하였다[13]. 이 시스템은 사용자 위치 정보(GPS)와 학습데이터를 저장한다. CRPM은 ROI(Regions-Of-Interest) 기반으로 사용자 위치의 격자를 식별한다. SubSyn은 격자 기반으로 사용자의 경로를 단편화하여 저장한다[14]. 그리고 Markov 모델을 이용하여 최종 경로를 예측하는 방법을 제공한다.

[15]는 사용자의 GPS 기반의 개인 경로 모델 학습 및 이동 경로 예측을 제안하였다. 스마트폰의 GPS 정보를 이용하여 격자로 사상한 후 개인 경로 모델을 학습한다. 격자 공간에 투영된 격자가 연속되지 않을 때 중간 지점을 생성하여 격자를 연결하며 이동 궤적을 추출한다. 추출된 경로의 패턴을 학습하여 개인 경로 모델을 생성한다. 생성된 모델에 학습하여 경로 예측으로 활용하였다.

[16]은 격자 기반 위치 예측 알고리즘에 의해 제공되는 예측 된 각 위치에 대해 신뢰 영역을 제공하는 방법을 제안했다. 신뢰 영역은 사용자가 있을 수 있는 예상 위치(격자) 주변의 반경으로 정의된 확장 영역과 사용자가 예측 영역에 있을 것이라는 확신 수준으로 정의한다. 세 가지 알고리즘(frequent cells, Markov chain model, matrix factorization)을 적용하고 예측 정확도가 높은 것을 동적으로 적용했다.

[17]은 기존의 격자 기반 알고리즘의 성능을 높이고 오프라인에서 사용을 위하여 격자를 재구성하는 방법을 제안했다. 초기화, 병합, 개량을 반복하여 사용자가 오프라인에서 사용할 때 정확도를 높이는 격자 모양을 만든다.

[18]은 두 단계로 구성된 시공간적 의미 신경망 알고리즘(STS-LSTM)을 제안하였다. 사용자의 이동궤적을 도로 네트워크에서 고정 점과 이산 점을 갖는 위치 시퀀스로 변환하기 위해 시공간적 의미 신경망(spatial-temporal-semantic neural network algorithm)을 사용했다. 그리고 장시간 위치 시퀀스를 더 잘 처리하기 위하여 LSTM(Long Short-Term Memory) 기반 모델을 구성했다.

제안하는 격자 기반의 경로 예측 방법은 사용자의 GPS 정보를 격자에 사상한다. SRS는 사용자가 이동한 이동 경로의 데이터를 이용하여 가중치를 연산하여 저장한다. SRS는 새로운 사용자가 SRS를 이용할 때 저장된 가중치를 이용한 탐욕(Greedy) 알고리즘기반으로 사용자에게 다음 이동 격자의 센서정보를 송신한다.

기존의 PP-SRS는 경로 예측을 위하여 경로 단편을 이용한다. 경로 단편은 도로를 교차로 단위로 단편화하여 사용자의 이동 경로를 사상한다. PP-SRS는 경로 단편에 사상되어있는 가중치를 이용한 탐욕 알고리즘 기반으로 사용자에게 다음 이동 경로 단편의 센서 정보를 송신한다. 하지만 PP-SRS는 제약사항이 있다.

① PP-SRS를 이용하기 위해서는 반드시 도로를 경로 단편으로 구축한 후 경로 예측이 가능하다.

② PP-SRS를 운영할 때 구축한 경로 단편을 무시하는 이동이 빈번히 발생한다.

PP-SRS는 사용자의 GPS 정보를 가장 근접한 경로 단편으로 사상한다. 경로 단편이 구성되지 않은 지역은 PP-SRS는 사용자의 위치를 식별하지 못한다. 경로 단편은 단위 면적이 증가할수록 구축대상도로의 개수가 기하급수적으로 증가한다. 이는 PP-SRS의 운용비용을 증가시킨다.

PP-SRS를 운영할 때 경로 단편으로 사상하여 이동 경로를 측정결과 때때로 이상한 경로가 발생했다. 사용자의 GPS 정보를 분석결과 사용자는 주어진 경로 단편을 이동 경로가 발생한다. 이상 이동 발생은 PP-SRS의 정확도를 하락시키는 원인이다.

이 두 가지 제약사항은 경로 단편이 지니고 있는 문제이다. 위의 문제를 해결하기 위하여 격자 기반의 경로 예측 방법을 제안한다.

사용자의 이동 경로를 예측하기 위하여 대표적으로 경로 단편과 격자 기반 방법이 사용된다. 경로 단편 방법은 도로를 세분화하여 교차로를 중심으로 저장한다. 그리고 사용자의 GPS 정보를 이용하여 가장 가까운 경로 단편으로 사상한다. 그 이후 경로 단편을 기준으로 사용자의 경로를 예측한다. 격자 기반 방법은 지도를 일정한 크기의 격자로 나누어 구분하여 관리한다. 그리고 사용자의 GPS 정보를 이용하여 가장 가까운 격자로 사상한다. 그 이후 현재 격자를 기준으로 다음 격자로의 이동 경로를 예측한다. 경로 단편 방법을 사용하기 위해서는 도로의 단편을 구분하여 저장하는 전처리 과정이 필요하다. 하지만 격자 방법은 전처리 과정 없이 이용할 수 있는 장점이 있다.

그림 1은 격자 기반 방법에 대한 개요도이다. 사용자의 이동 경로(p)를 일정한 시간 간격으로 수집한 후 연속된 선 개념으로 고려한다. 그리고 사용자의 이동 경로를 연속된 격자 번호로 표현한다. 이 방법은 실제 도로 및 건물 등의 위치와 관계없이 표현할 수 있다. 시스템은 사용자의 이동 경로를 격자의 연속된 패턴으로 저장한다. 격자의 크기는 상황에 따라 다르게 설정하여 예측 성능을 높일 수 있다.

Fig. 1. 
Overview of grid method

그림 2는 PP-SRS의 경로 단편 표현 방법(a)과 제안하는 격자 기반의 표현방법(b)이다. 격자란 지도를 일정한 크기로 나눈 구역을 말한다. 격자는 적용하는 도메인과 목적에 따라 크기와 구조가 달라진다. 일반적으로 GPS의 측정오류를 고려하여 격자의 크기는 최소 50m² ~ 최대 수 km² 구성가능하다. 경로예측의 정확도를 높이기 위하여 인근 격자를 상황에 따라 통합하여 GPS 정보가 격자 사이에 위치하여 격자 이동을 반복하는 문제를 해결할 수 있다.

Fig. 2. 
Examples of PP-SRS and our proposed method

제안 방법은 SRS의 특성을 고려하여 격자의 크기를 500m² 이상으로 구성한다. 또한 지역을 일정한 크기의 정사각형 형태의 격자로 나눈다. SRS는 구분한 격자에 고유한 번호를 할당하여 관리한다. 시스템의 서버는 사용자의 위치 정보를 수신하여 가까운 격자로 사상한다. 사용자들이 이용한 정보를 이용하여 경로 예측하여 센서 정보를 사용자에게 제공한다.

그림 3은 제안하는 격자 기반 경로 예측 프로세스이다. 제안하는 프로세스의 목적은 SRS가 격자기반 방법을 이용하여 사용자의 위치를 파악하여 다음 이동 경로를 예측하여 센서 정보를 미리 보내주는 것이다.

Fig. 3. 
Our proposed process of grid-based path prediction

첫 번째 사용자의 GPS 정보를 수신합니다. SRS는 사용자의 위치를 격자의 위치로 사상시킨다. 사용자의 격자 이동 경로를 이용하여 격자 기반 예측 알고리즘을 적용한다. 그리고 사용자의 다음 이동 격자를 결정한다. SRS는 사용자의 다음 이동 격자에 포함되어있는 센서 정보를 취합하여 사용자에게 송신한다. 사용자의 격자 이동이 발생할 경우 프로세스를 반복하여 수행한다.

그림 4는 제안 방법이 적용된 격자 기반 경로 표현방법의 예제이다. 사용자는 군산대학교의 인문대학건물에서 학교 앞 커피숍으로 이동하였다. SRS는 사용자가 이동하는 GPS 정보를 수신한다. 수신한 정보는 빨간색 점으로 표시되며 이 점을 이은 선은 실제 이동 동선이다. 사용자의 GPS 위치 정보를 이용하여 가장 속해있는 격자로 사상하며 이동 경로의 집합을 저장한다. 새로운 사용자가 SRS를 이용 할 때 경로 예측의 기반 자료로 사용된다.

Fig. 4. 
An example of grid-based path prediction

기존의 PP-SRS는 사용자의 GPS 정보를 가까운 경로 단편으로 사상한 후 경로 단편을 기준으로 다음 경로를 예측한다. 시스템은 실시간 근거리 사용자 이동 경로 예측을 하며, 사용자의 기존 이동에 대한 정보가 부재한 상황을 고려한다. 과거 정보가 없는 환경에서 사용자의 이동 경로를 예측하기 위하여 탐욕 전략 기반의 알고리즘을 사용하였다. 탐욕 전략은 경험 지식을 바탕으로 해결하는 알고리즘으로서, 최적화된 해를 구하기 위해 후보 집단에서 최적의 해법을 선택하여 문제 해결 연산을 단순화한다. 사용자의 개인정보가 부족한 상황에서 예측은 모든 상황을 고려해야 하기 때문에 높은 비용을 요구한다. 이 문제를 해결하기 위하여 후보 집단 중에서 단순하게 지역적 해를 선택함으로써 높은 처리 성능을 지원하는 특성을 이용한다. 제안 방법에서는 경로 단편 대신 격자를 이용하여 사용자의 위치에서 최적의 격자를 예측한다.

경로 단편을 이용한 예측방법과 제안하는 격자를 이용한 방법은 유사성을 가지고 있다. 사용자의 위치를 f0라고 했을 때 임의의 교차점에서 사용자가 이동 가능한 경로 단편 집합 F={f1, f2, f3}일 때, 가장 많은 사용자가 이동한 경로 단편이 f1이라면 임의의 사용자 u1은 해당 교차점에서 f1으로 이동할 확률이 높다고 예측한다. SRS는 사용자 u1에게 f1에 속해있는 센서 정보를 송신한다. 격자를 이용한 예측 방법은 비슷한 예측방법을 진행한다. 사용자의 현재 위치를 G0이라고 가정하면 이동할 수 있는 경로는 G={Ge, Gw, Gn, Gs, Gse, Gne, Gnw, Gsw} 즉, 현재 위치한 격자위치에서 동, 서, 남, 북, 북동, 남동, 남서, 북서에 위치한 격자로 이동할 수 있다. 격자 기반의 예측방법에서는 가장 많은 사용자가 이동한 격자가 Gn일 때, 임의의 사용자가 이동할 확률은 Gn이 가장 높다. SRS는 사용자 u1에게 Gn에 속해있는 센서 정보를 송신한다.

제안방법은 사용자의 GPS 정보를 수신하고 근접 경로를 예측하여 다음 격자의 센서 정보를 사용자에게 송신한다. SRS는 사용자의 과거 이동정보 정보 없이 근거리 예측을 한다. SRS는 근거리 예측을 위하여 과거의 SRS를 이용한 사용자들의 패턴을 이용한다. 제안하는 예측방법은 사용자의 이동 경로를 방향성을 가진 가중치를 측정하여 근접경로 예측의 알고리즘에 사용한다. 시스템을 이용하는 사용자가 증가함에 따라 시스템의 정확도는 점차 증가할 수 있다.

제안방법은 사용자의 데이터가 없는 환경을 고려하여 근거리 예측을 위하여 탐욕 전략 기반의 알고리즘을 사용한다. PP-SRS의 근거리 예측 알고리즘은 경로 단편을 사용하지만, 제안방법에서는 격자를 고려한 알고리즘을 제안한다. 기존 알고리즘과 다른 점은 가중치 측정 부분이다. 제안 방법은 사용자의 GPS 정보를 수신하면 해당 격자로 사상한다. 식별한 격자를 기반으로 다음 경로를 예측하여 다음 격자에 해당하는 센서 정보를 사용자에게 송신한다. 다음 격자를 예측할 때 이전 사용자들이 이동한 경로를 참고한 가중치를 이용한다. 하지만 이는 개인화 예측이 아니기 때문에 정확도가 필연적으로 낮다. 사용자의 개인정보 없는 환경에서 예측 정확도를 높이기 위해서 가중치에 대한 지속적인 관리가 필요하다. 그래서 SRS는 운영하면서 측정한 정보를 이용해 가중치가 실시간으로 변경된다.

제안방법은 사용자의 가중치를 저장하기 위하여 2단계를 진행한다. 1단계는 사용자의 이동 경로를 가공 없이 방향성을 고려하여 저장한다. 2단계는 사용자의 최종 출발지와 도착지를 고려하여 최적 경로에 추가 가중치를 저장한다.

그림 5는 제안방법의 1단계 사용자 GPS 정보기반 가중치 측정방법이다. (a)는 사용자의 GPS 정보를 지도에 표시한 것이다. (b)는 사용자의 GPS 정보를 이용하여 격자로 사상한다. (c)는 사용자의 이동 격자를 이용하여 가중치를 측정한다.

Fig. 5. 
STEP 1 : Weight estimate based on user GPS information

그림 6은 제안방법의 2단계 이동 궤적기반 가중치 측정 방법을 보인다. (a)는 지도에 표시된 사용자의 격자 이동 경로이다. (b)는 격자 정보를 세선화 알고리즘을 이용하여 사용자의 이동경로를 두께 1을 가지도록 한다. 세선화란 대상 물체의 표면을 조금씩 벗겨내어 최종적으로 두께1을 가지도록 하는 것이다. 대표적인 세선화 알고리즘으로 Zhang Suen 세선화 알고리즘을 사용한다. (c)는 세선화알고리즘으로 측정된 경로를 가중치로 표현한 것이다.

Fig. 6. 
Movement path based on a weight estimate

(d)는 세선화를 거친 가중치 정보와 1단계의 가중치와 합한다. 두 단계를 거친 가중치 정보는 최종적으로 서버의 가중치 정보에 업데이트된다.