최근 PDA, 휴대폰과 같은 모바일 기기 및 GPS와 같은 무선 통신 기술의 발달로 인하여 위치 기반 서비스의 이용이 확산되었다. 하지만 이러한 서비스는 사용자가 도로 네트워크에서 이동하면서 자신의 위치정보를 통해 LBS 서버에 질의를 요청하기 때문에, 심각한 개인 정보 누출의 위협이 될 수 있다. 따라서 모바일 사용자의 안전하고 편리한 위치기반 서비스 사용을 위한 개인 정보 보호 기법이 필요하다. 이를 위해 본 논문에서는 위치 기반 서비스에서 사용자 정보 보호를 지원하는 도로 네트워크 거리 기반 클로킹 기법을 제안한다. 제안하는 기법은 도로 네트워크에서 효율적이고 안전한 위치기반 서비스를 지원하기 위하여, 도로 네트워크의 거리를 고려하여 클로킹 영역을 설정한다. 아울러, 성능평가를 통해서 제안하는 기법이 클로킹 영역 및 서비스 시간 측면에서 기존 연구보다 우수함을 보인다.
최근 PDA, 휴대폰과 같은 모바일 기기 및 GPS와 같은 무선 통신 기술의 발달로 인하여 위치 기반 서비스의 이용이 확산되었다. 하지만 이러한 서비스는 사용자가 도로 네트워크에서 이동하면서 자신의 위치정보를 통해 LBS 서버에 질의를 요청하기 때문에, 심각한 개인 정보 누출의 위협이 될 수 있다. 따라서 모바일 사용자의 안전하고 편리한 위치기반 서비스 사용을 위한 개인 정보 보호 기법이 필요하다. 이를 위해 본 논문에서는 위치 기반 서비스에서 사용자 정보 보호를 지원하는 도로 네트워크 거리 기반 클로킹 기법을 제안한다. 제안하는 기법은 도로 네트워크에서 효율적이고 안전한 위치기반 서비스를 지원하기 위하여, 도로 네트워크의 거리를 고려하여 클로킹 영역을 설정한다. 아울러, 성능평가를 통해서 제안하는 기법이 클로킹 영역 및 서비스 시간 측면에서 기존 연구보다 우수함을 보인다.
Recent development in wireless communication technology like GPS as well as mobile equipments like PDA and cellular phone makes location-based services (LBSs) popular. However, because users request a query to LBS servers by using their exact locations while moving on the road network, users' privac...
Recent development in wireless communication technology like GPS as well as mobile equipments like PDA and cellular phone makes location-based services (LBSs) popular. However, because users request a query to LBS servers by using their exact locations while moving on the road network, users' privacy may not be protected in the LBSs. Therefore, a mechanism for users' privacy protection is required for the safe and comfortable use of LBSs by mobile users. For this, we, in this paper, propose a road network distance based cloaking scheme supporting user privacy protection in location-based services. The proposed scheme creates a cloaking area by considering road network distance, in order to support the efficient and safe LBSs on the road network. Finally, we show from our performance analysis that our cloaking scheme outperforms the existing cloaking scheme in terms of cloaking area and service time.
Recent development in wireless communication technology like GPS as well as mobile equipments like PDA and cellular phone makes location-based services (LBSs) popular. However, because users request a query to LBS servers by using their exact locations while moving on the road network, users' privacy may not be protected in the LBSs. Therefore, a mechanism for users' privacy protection is required for the safe and comfortable use of LBSs by mobile users. For this, we, in this paper, propose a road network distance based cloaking scheme supporting user privacy protection in location-based services. The proposed scheme creates a cloaking area by considering road network distance, in order to support the efficient and safe LBSs on the road network. Finally, we show from our performance analysis that our cloaking scheme outperforms the existing cloaking scheme in terms of cloaking area and service time.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
하지만, n4, n6와 같이 도로 네트워크 상으로 가까운 노드가 고려되지 않거나, n8과 같이 비효율적으로 먼 노드가 후보로 고려될수 있다. 따라서 본 논문에서는 도로 네트워크의 거리를 고려하여 효율적으로 위치기반 서비스를 지원할 수 있는 클로킹 영역 설정 기법을 제안한다.
따라서 본 논문에서는 이러한 문제점을 해결하기 위해, 위치 기반 서비스에서 도로 네트워크의 거리 정보를 이용한 사용자 정보 은닉 기법을 제안한다. 이를 위해, 첫째, 질의 요청자를 교차 노드에 할당할 때 각 노드와 교차하는 도로의 거리를 고려하여, 설정되는 총 클로킹 영역이 작은 노드에 질의 요청 자가 할당될 확률을 높인다.
이때 하나 이상의 도로를 할당하고 있는 노드만이 병합 대상이 된다. 병합을 통해 구성된 슈퍼스타가 해당 영역에 속한 모든 사용자의 Kanonymity 및 L-diversity 요구 수준을 만족하면, 해당 슈퍼스타가 사용자들이 요구하는 D-tolerance 를 만족하는지 검사한다. 만약, 설정된 슈퍼스타가 사용자들의 D-tolerance 요구 조건을 만족하면, 해당 슈퍼스타가 포함하는 도로의 집합이 최종 클로킹 영역으로 설정된다.
본 논문에서는 위치 기반 서비스에서 사용자 정보 보호를 지원하는 도로 네트워크 거리 기반 클로킹 기법을 제안하였다. 제안하는 기법은 사용자가 속한 도로의 교차 노드 선택 시 실제 네트워크 거리를 고려하고, 서비스 사용자가 실제 거리를 위배 조건으로 설정할 수 있도록 한다.
본 절에서는 위치 기반 서비스에서 사용자 정보보호를 지원하는 도로 네트워크 거리 기반 클로킹 기법을 제안한다. 알고리즘은 크게 질의 요청자를 교차 노드에 할당하는 교차노드 선택 단계와, 해당 교차 노드가 질의 요청자의 service profile을 충족 하지 못 할 경우 인접 교차노드와 병합하여 슈퍼스타를 구성하는 슈퍼스타 구성 단계로 수행된다.
제안 방법
본 장에서는 위치 기반 서비스에서 사용자 정보보호를 지원하는 도로 네트워크 거리 기반 클로킹 기법(이하 DStar)의 우수성을 검증하기 위하여 성능 평가를 수행한다. 본 연구는 도로 네트워크에서 지속적으로 이동하는 사용자를 고려하여 클로킹 영역 설정하기 때문에, 기존 기법 중 해당 환경을 고려하여 연구된 XStar와 성능평가를 수행한다. 한편, E.
본 장에서는 위치 기반 서비스에서 사용자 정보보호를 지원하는 도로 네트워크 거리 기반 클로킹 기법(이하 DStar)의 우수성을 검증하기 위하여 성능 평가를 수행한다. 본 연구는 도로 네트워크에서 지속적으로 이동하는 사용자를 고려하여 클로킹 영역 설정하기 때문에, 기존 기법 중 해당 환경을 고려하여 연구된 XStar와 성능평가를 수행한다.
즉, 사용자의 이동 패턴에 따라 DStar와 병행하여 사용할 수 있는 기법이기 때문에 해당 기법과의 성능비교는 수행하지 않는다. 성능 평가 항목으로는 L-diversity, K-anonymity, D-tolerance의 변화에 따른 클로킹 영역의 총 길이, 클로킹 영역 내에 포함된 도로의 수, 총 서비스 시간, 그리고 클로킹 영역 설정 성공률을 측정한다. 여기에서 총 서비스 시간은 클로킹 영역 설정 시간과 설정된 클로킹 영역에 대한 영역 질의 처리 시간을 합한 시간이다.
본 논문에서는 위치 기반 서비스에서 사용자 정보 보호를 지원하는 도로 네트워크 거리 기반 클로킹 기법을 제안하였다. 제안하는 기법은 사용자가 속한 도로의 교차 노드 선택 시 실제 네트워크 거리를 고려하고, 서비스 사용자가 실제 거리를 위배 조건으로 설정할 수 있도록 한다. 이를 통해, 사용자의 위치정보를 보호하면서 효율적으로 위치기반 서비스를 수행할 수 있다.
대상 데이터
아울러, 이동객체 데이터는 Network-based Generator[1]를 사용하여 미국 샌프란시스코의(600㎢) 실제 도로 네트워크를 기반으로 10,000건을 생성하였다. 또한 XStar의 홉(hop)과 제안하는 기법의 거리 간의 비교를 위해 샌프란시스코의 도로 정보를 분석하여, 1 홉 당 평균 거리인 약 410m를 제안하는 기법의 표준 거리로 사용하였다. 표 2는 성능 평가에 사용된 매개변수들이다.
아울러, 이동객체 데이터는 Network-based Generator[1]를 사용하여 미국 샌프란시스코의(600㎢) 실제 도로 네트워크를 기반으로 10,000건을 생성하였다. 또한 XStar의 홉(hop)과 제안하는 기법의 거리 간의 비교를 위해 샌프란시스코의 도로 정보를 분석하여, 1 홉 당 평균 거리인 약 410m를 제안하는 기법의 표준 거리로 사용하였다.
이론/모형
본 논문에서는 클로킹 영역을 설정하는 주체가 anonymizer인 중앙 집중 방식을 사용하며, 시스템 구조는 그림 3과 같다. 시스템 구조는 크게 모바일 사용자와 anonymizer, 그리고 LBS 서버로 구성된다.
성능/효과
그림 12는 K 변화에 따른 총 서비스 시간을 나타낸 것이다. K 값이 증가할수록 두 기법 모두 총 서비스 시간이 증가함을 알 수 있다. K가 15일 때, XStar는 1.
만약 선택된 교차 노드를 지나는 도로의 집합이 해당 영역에 속한 모든 사용자의 K- anonymity 및 L-diversity 요구 수준을 만족한다면, 선택된 도로의 집합이 클로킹 영역으로 설정된다. 둘째, 선택된 교차 노드가 할당된 사용자의 요구 조건을 만족하지 못할 경우, 해당 노드는 인접한 교차 노드와의 병합을 통해 슈퍼스타를 구성한다. 만약 구성된 슈퍼스타가 해당 영역에 속한 모든 사용자의 K-anonymity 및 L-diversity 요구 수준을 만족한다면, 해당 슈퍼스타가 사용자들이 요구하는 S- tolerance를 만족하는지 검사한다.
한편, n1 노드가 선택되었을 경우 설정되는 클로킹 영역은 그림의 굵은 실선으로 표시된 도로와 같다. 둘째, 슈퍼스타를 구성할 때 제약 조건으로 hop만을 고려하기 때문에, 실제 도로 네트워크 상으로 가까운 노드가 슈퍼스타 구성의 후보로 고려되지 않거나, 비효율적으로 먼 노드가 슈퍼스타 구성에 포함될 수 있다. 그림 2에서 질의 요청자 N이 n1 노드에 할당되었고 n1 노드만으로는 사용자 N의 질의를 충족할 수 없다고 가정할 때, n1은 슈퍼스타 구성을 위해 인접한 교차 노드를 탐색한다.
첫째, 만약 s가양 끝 교차 노드 중 이미 어느 한 교차 노드에 할당 되어 있다면, 질의 요청자를 해당 교차 노드에 할당한 후, 알고리즘을 종료한다. 둘째, 양 끝 교차 노드가 다른 도로를 할당하고 있지만, s가 할당되어 있지 않다면, 각 교차 노드에서의 질의 처리 비용을 고려하여 s를 한 교차 노드에 할당한다. 셋째, s를 할당하고 있지 않더라도, 어느 한 교차 노드만이 다른 도로를 할당하고 있다면, s를 해당 교차 노드로 할당한다.
이를 통해, 사용자의 위치정보를 보호하면서 효율적으로 위치기반 서비스를 수행할 수 있다. 또한, 기존 연구인 XStar와의 성능 비교를 통해 제안하는 기법이 사용자 위치정보 보호와 서비스 시간 측면에서 우수함을 검증하였다.
둘째, 양 끝 교차 노드가 다른 도로를 할당하고 있지만, s가 할당되어 있지 않다면, 각 교차 노드에서의 질의 처리 비용을 고려하여 s를 한 교차 노드에 할당한다. 셋째, s를 할당하고 있지 않더라도, 어느 한 교차 노드만이 다른 도로를 할당하고 있다면, s를 해당 교차 노드로 할당한다. 넷째, 양 끝 교차 노드 모두 어떠한 도로도 할당하고 있지 않다면, 각 교차 노드에서의 질의 처리 비용을 고려하여 s를 한 교차노드에 할당한다.
셋째, 선택된 노드가 사용자가 요구한 K-anonymity와 L-diversity를 만족하면, 해당 노드를 지나는 도로의 집합을 클로킹 영역으로 반환하고 알고리즘을 종료한다(line 13∼15).
따라서 본 논문에서는 이러한 문제점을 해결하기 위해, 위치 기반 서비스에서 도로 네트워크의 거리 정보를 이용한 사용자 정보 은닉 기법을 제안한다. 이를 위해, 첫째, 질의 요청자를 교차 노드에 할당할 때 각 노드와 교차하는 도로의 거리를 고려하여, 설정되는 총 클로킹 영역이 작은 노드에 질의 요청 자가 할당될 확률을 높인다. 둘째, 슈퍼스타 구성시 인접한 노드까지의 도로 네트워크 거리를 고려 하여, 비효율적인 클로킹 영역이 설정되는 것을 방지한다.
이는 DStar가 실제 도로 네트워크 거리를 고려하여 클로킹 영역을 설정하기 위한 도로를 선택하기 때문이다. 이를 통해 DStar는 클로킹 영역 내에서 질의 요청자가 존재하는 도로의 노출 확률을 감소시키며, 따라서 DStar가 XStar에 비해 사용자 프라이버시 보호 측면에서 우수함을 알 수 있다.
다음으로 질의 요청자와 질의 요청자가 속한 도로(s)를 이 중 한 노드에 할당하며, 할당 알고리즘은 다음과 같다. 첫째, 만약 s가양 끝 교차 노드 중 이미 어느 한 교차 노드에 할당 되어 있다면, 질의 요청자를 해당 교차 노드에 할당한 후, 알고리즘을 종료한다. 둘째, 양 끝 교차 노드가 다른 도로를 할당하고 있지만, s가 할당되어 있지 않다면, 각 교차 노드에서의 질의 처리 비용을 고려하여 s를 한 교차 노드에 할당한다.
그러나 이러한 클로킹 기법들은 유클리디언 공간 상의 사용자 위치를 고려하여 클로킹 영역을 설정하기 때문에 다음과 같은 문제점을 보인다. 첫째, 설정된 클로킹 영역이 도로 네트워크 상으로 연결되어 있지 않은 도로 혹은 가깝지 않은 도로 상의 사용자를 포함할 수 있기 때문에, 질의 결과의 정확도가 낮아질 수 있다는 문제를 지닌다. 예를 들어, 질의를 요청한 사용자(N)가 k=3를 요청한다고 가정할때, 그림 1(a)는 이러한 문제점을 보여준다.
그러나 이와 같은 기법은 유클리디언 공간 상의 사용자 위치를 고려하여 클로킹 영역을 설정하기 때문에, 실제 도로 네트워크를 고려한 환경에서는 다음과 같은 문제점을 보인다. 첫째, 설정된 클로킹 영역이 도로 네트워크 상으로 연결되어 있지 않은 도로, 혹은 가깝지 않은 도로상의 사용자를 포함할 수 있기 때문에, 질의 결과의 정확도가 감소될 수 있다. 둘째, 설정된 클로킹 영역이 포함하는 도로의 수가 적을 수 있기 때문에, 사용자가 존재하는 도로 정보와 이를 통한 사용자의 이동 경로 및 위치정보(e.
그러나 XStar는 클로킹 영역을 설정할 때 도로 네트워크의 실제 거리를 고려하지 않기 때문에 다음과 같은 문제점을 지닌다. 첫째, 질의 요청자가 할당될 교차 노드를 선택하기 위해 교차 노드의 degree만을 고려하기 때문에, 설정되는 클로킹 영역의 크기가 커져, 질의 처리 비용이 증가할 수 있다. 그림 2에서 질의 요청자 N이 (l, k, s)=(4, 2, 1)을 요청했다고 가정할 때, n1 노드는 degree가 3, n2 노드는 degree가 4 이기 때문에, N은 n1 노드에 할당될 확률이 높다.
후속연구
향후 연구는 중앙 집중 방식에서 발생할 수 있는 병목 현상 등의 문제를 해결하기 위해, 분산 환경으로 본 연구를 확장하는 것이다.
질의응답
핵심어
질문
논문에서 추출한 답변
LBS란 무엇인가?
최근 PDA, 휴대폰과 같은 모바일 기기 및 GPS와 같은 무선 통신 기술의 발달로 인하여 위치 기반 서비스(Location-Based Service : LBS)의 이용이 확산되었다. LBS란 유무선 통신망을 통해 얻은 위치정보를 부가적인 정보와 결합하여 사용자가 필요로 하는 유용한 응용 서비스를 제공하는 것이다[2, 4]. 모바일 사용자는 자신의 위치정보를 LBS 서버에 보내어 교통 정보, 친구 찾기, 인접한 POI(Point Of Interest) 찾기 등 다양한 종류의 위치 기반 서비스를 이용할 수 있다.
모바일 사용자는 자신의 위치정보를 LBS서버에 보내어 무엇을 이용할 수 있는가?
LBS란 유무선 통신망을 통해 얻은 위치정보를 부가적인 정보와 결합하여 사용자가 필요로 하는 유용한 응용 서비스를 제공하는 것이다[2, 4]. 모바일 사용자는 자신의 위치정보를 LBS 서버에 보내어 교통 정보, 친구 찾기, 인접한 POI(Point Of Interest) 찾기 등 다양한 종류의 위치 기반 서비스를 이용할 수 있다. 그러나 이와 같이 사용자의 정확한 위치정보를 통해 LBS 서버에 위치 기반 서비스를 요청하는 것은 심각한 개인 정보 누출의 위협이 될 수 있다.
XStar는 어떤 문제점을 해결하기 위해 제안되었는가?
그러나 이와 같은 기법은 유클리디언 공간 상의 사용자 위치를 고려하여 클로킹 영역을 설정하기 때문에, 실제 도로 네트워크를 고려한 환경에서는 다음과 같은 문제점을 보인다. 첫째, 설정된 클로킹 영역이 도로 네트워크 상으로 연결되어 있지 않은 도로, 혹은 가깝지 않은 도로상의 사용자를 포함할 수 있기 때문에, 질의 결과의 정확도가 감소될 수 있다. 둘째, 설정된 클로킹 영역이 포함하는 도로의 수가 적을 수 있기 때문에, 사용자가 존재하는 도로 정보와 이를 통한 사용자의 이동 경로 및 위치정보(e.g., 건물)가 노출될수 있다. 이러한 문제점을 해결하기 위한 대표적인 연구로 Ting Wang et al.
참고문헌 (13)
T. Brinkhoff, "A Framework for Generating Network-Based Moving Objects", GeoInformatica, Vol.6, No.2, pp.153-180, 2002.
D. Cho, "A Study on the State-of-the-Art of LBS through Patent Analysis", Journal of Korea Spatial Information System Society, Vol.9, No.3, pp.65-75, 2007.
M. Gruteser and D. Grunwald, "Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking," In Proc. of the International Conference on Mobile Systems, Applications and Services, pp. 31-42, 2003.
G. Ghinita, P. Kalnis and S. Skiadopoulos, "MobiHide: A Mobilea Peer-to-Peer System for Anonymous Location-Based Queries," In Proc. of SSTD, Vol.4605, pp. 221-238, 2007.
A. Lee, H. Kim, and J. Chang, "Grid-based Cloaking Area Creation Scheme supporting Continuous Location-Based Services", Journal of Korea Spatial Information System Society, Vol.11, No.3, pp. 19-30, 2009.
M. Mokbel, W. Aref, S. Hambrusch, and S. Prabhakar, "Towards Scalable Location-aware Services : Requirements and Research Issues", In Proc. of the 11th ACM-GIS, pp. 110-117, 2003.
M. Mokbel, C. Chow, W. Aref, "The New Casper: Query Processing for Location Services without Compromising Privacy", VLDB, pp.763-774, 2006.
B. Palanisamy and L. Liu, "MobiMix: Protecting Location Privacy with Mix-zones over Road Networks," In Proc. ICDE, pp. 494-505, 2011
J. Voelcker, "Stalked by Satellite: An Alarming Rise in GPS-enabled Harassment", IEEE Spectrum, Vol.47, NO.7, 2006, pp.15-16
J. Warrior, E. McHenry, and K. McGee, "They Know Where You Are", IEEE Spectrum, Vol.40, No.7, pp. 20-25, 2003.
T. Wang and L. Liu, "Privacy-Aware Mobile Services over Road Networks", PVLDB, pp. 1042-1053, 2009.
T. Xu and Y. Cai, "Location Anonymity in Continuous Location-based Services", ACMGIS, pp. 221-238, 2007.
E. Yigitoglu, M. Damiani, O. Abul and C. Silverstri, "Privacy-preserving sharing of sensitive semantic locations under road-network constraints," In Proc. MDM, 2012.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.