Advanced
Location Estimation Method Employing Fingerprinting Scheme based on K-Nearest Neighbor Algorithm under WLAN Environment of Ship
Location Estimation Method Employing Fingerprinting Scheme based on K-Nearest Neighbor Algorithm under WLAN Environment of Ship
Journal of the Korea Institute of Information and Communication Engineering. 2014. Oct, 18(10): 2530-2536
Copyright © 2014, The Korea Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License(http://creativecommons.org/li-censes/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : July 24, 2014
  • Accepted : September 12, 2014
  • Published : October 31, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
범무 김
Department of Electronics Engineering, Mokpo National University, Muan 534-729, Korea
민아 정
Department of Computer Engineering, Mokpo National University, Muan 534-729, Korea
성로 이
Department of Information & Electronics Engineering, Mokpo National University, Muan 534-729, Korea
srlee@mokpo.ac.kr

Abstract
GPS 신호가 도달하지 않는 실내 환경에서 위치를 추정하는 연구는 지금까지 많이 이루어져 왔다. 또한 추정 기법도 여러 가지 기법들이 제안되었다. 본 논문에서는 다층 구조의 선박에서 위치를 추정하는 문제를 심도있게 고찰하였고 K-최근접 이웃 알고리즘 기반 Fingerprint 기법에 의한 위치 추정 방법에 대해 알아보았다. Fingerprint 기법을 쓰기 위해 39개의 RP 에서 각각 N =100회의 수신신호를 측정함으로써 신뢰성 있는 DB를 구축하였고 이를 토대로 임의의 위치에 있는 단말기의 위치를 추정하는 모의실험을 하였다. 모의실험을 통해 Fingerprint 기법에 의한 위치 추정 성능은 아주 우수함을 알 수 있었다.
Keywords
Ⅰ. 서 론
그림 1 과 같이 GPS 신호가 도달하지 않는 선박의 실내 환경에서 단말기의 위치를 추정하는 문제를 생각해 보자. 첫째는 실내 네트워크 환경을 어떤 통신방식으로 구성해야 할 것인가와 그에 따른 장비의 간소화는 어떠한가를 생각해 보야 한다. 둘째는 위치 추정의 정확도는 어느정도 수준인가를 생각해 보아야 한다. 셋째는 선박의 환경에서 위치 추정은 평면상의 추정문제인가 아니면 공간상의 추정문제인가를 생각해 보아야 한다.
PPT Slide
Lager Image
선박내 구조 및 위치 추정에 대한 개념도 Fig. 1 Diagram of the structure and location estimation in a ship.
첫째의 관점에서 보면 선박의 실내 환경에서는 IEEE 802. 11의 표준인 WLAN으로 네트워크를 구성하는 것이 좋다는 것을 알 수 있다. 그 이유는 WLAN은 AP(Access Point)와 NIC 카드만으로 네트워크를 구성할 수 있다는 장점이 있기 때문이다 [1 - 4] . 둘째의 관점에서 보면 실내 측위의 방법은 AOA(Angle of Arrival), TOA(Time of Arrival), RSS(Received Signal Strength), TDOA(Time Difference of Arrival), Fingerprint 방식이 있는데 선박환경에서 가장 효과적인 방법이 무엇인가를 선택해야 한다는 것이다 [5 - 8] . 선박의 실내 환경은 도심지 건물의 실내 환경에 비해 상대적으로 환경정보의 변화가 적다고 할 수 있다.
이러한 이유 때문에 주변정보의 DB화에 의해 단말의 위치를 추정하는 Fingerprint 방식을 선택하는 것이 타당성이 있다고 할 수 있다. 셋째의 관점에서는 선박은 여러개의 층으로 구성되어 있고 각 층은 두꺼운 철판으로 막혀있는 공간이 상대적으로 많다는 특성을 갖고 있기 때문에 이러한 다층 구조의 환경에서 단말기의 위치 추정은 매우 어려운 문제로 생각할 수 있다는 것이다. 이를 정확하게 보면 각 층마다 평면상의 추정이 아닌 공간상의 3차원 추정 문제로 접근해야 한다는 것이다. 그러나 공간상의 추정문제는 상대적으로 많은 계산량을 필요로 하기 때문에 평면상의 추정문제로 접근하는 것이 현실적으로 타당성이 있다고 할 수 있다. 이는 선박내에서 단말기의 위치에 대한 의미가 정확히 어느 지점에 있는가가 아니라 어느 공간에 있는가가 중요하기 때문이다. 따라서, 본 논문에서 Fingerprint 방법을 쓴 평면상의 위치를 추정하는 문제를 다룬다.
Ⅱ. 관련기술
위치를 추정하는 일반적인 방법은 GPS(Global Positioning System)를 이용하는 방법이다. GPS는 3개 이상의 위성을 이용하여 삼각측량법에 의해 추정하는 방법이다. 그런데 GPS 신호가 도달하지 않는 환경에서는 무선신호를 이용하여 위치를 추정한다. 도심지의 실내 환경이거나 밀폐된 환경에서 이루어지는 위치추정 방법으로는 AOA(Angle of Arrival), TOA(Time of Arrival), TDOA(Time Difference of Arrival), RSS (Received Signal Strength), Fingerprint 방식이 있다. AOA 기법은 두 개 이상의 AP를 써서 단말기로부터 들어오는 신호의 방향, 즉, θ 1 , θ 2 ,⋯, θn 를 추정하여 위치를 찾는 방법이고. TOA 기법은 AP를 중심으로 반지름 r 1 , r 2 ,⋯, rn 을 갖는 원을 그려 모든 원들이 교차하는 지점을 추정하는 방법이다. 또한, TDOA 기법은 AP와 단말기 간의 신호의 전달 시간차인 t 1 , t 2 ,⋯, tn 를 구해 위치를 찾는 방법이며, RSS 기법은 신호의 세기를 이용하여 거리를 추정하는 방법이다. 마지막으로 Fingerprint 기법은 위치를 추정하고자 하는 구역을 격자 모양의 셀로 나누어 각 교차점에 RP를 배치하여 사전에 수신신호의 정보를 DB로 만들어 놓고, 임의의 위치에서 오는 신호에 대한 정보와 비교하여 가장 가까운 RP를 위치로 결정하는 방법이다.
일반적으로 선박의 환경은 육지의 실내 환경에 비해 위치를 추정하기 위한 별도의 무선 장비를 설치하는 것이 어렵다고 볼 수 있다. 육지의 환경은 여러 가지 네트워크 구성이 상대적으로 잘 되어 있는 반면, 선박의 환경은 네트워크의 구성이 비교적 열악하다. 따라서, 선박내 환경에서는 WLAN를 이용한 Fingerprint 기법을 적용하여 위치를 추정하는 방법이 다른 방법에 비해 현실적으로 더 적합하다고 할 수 있다 [9 - 18] .
Ⅲ. K-최근접 이웃 알고리즘 기반 Fingerprint 방법을 적용한 위치 추정 방법
그림 1 과 같은 선박의 실내 환경에서 2개 이상의 AP 를 써서 Fingerprint 방식에 의해 단말의 위치를 추정하는 문제를 생각해 보자. 먼저 고찰해야 하는 점은 하나의 AP 를 써서 직선상의 거리를 추정하는 것이 가능하다는 것을 생각해 보아야 한다. AP 로부터 r 만큼 떨어진 지점에서 수신신호의 세기 P ( r )은 (1)과 같다.
PPT Slide
Lager Image
여기서, P ( r 0 )는 기준거리에서 이전에 측정된 신호세기이며 n 은 경로손실 지수이고 m AP 와 단말사이에 존재하는 벽 감쇄 계수를 나타낸 것이다. 경로 손실지수는 AP 와 단말 사이의 장애물의 종류에 따라 다르며, LOS( Line of Sight)인 경우 n = 2이며 장애물이 있는 경우 2에서 4사이의 값을 갖는다.
식(1)의 의미는 거리를 추정하기 전에 기준거리에서 신호의 세기에 대한 사전 정보가 있다면 이를 토대로 AP 로부터 r 만큼 떨어진 지점에서의 수신신호를 측정하여 거리 r 를 구할 수 있다는 것이다. 이는 직선을 x 축상에 놓으면 r x 가 되기 때문에 AP 가 원점에 있다고 가정하면 x 의 거리를 추정하는 문제로 생각할 수 있다. 이제 직선상의 추정 문제를 평면상의 추정문제로 확대해 보자. 이는 임의의 ( x,y )지점에서 두 개의 AP 로부터 거리를 변수 r ′과 r ″ 으로 표기하면 (2)와 (3)을 얻을 수 있다. 직관적으로 (2)와 (3)에 의해 ( x,y )의 추정값
PPT Slide
Lager Image
를 구할 수 있다는 것으로 알 수 있다.
PPT Slide
Lager Image
PPT Slide
Lager Image
더 구체적으로 두 개 이상의 AP 를 써서 AP 로부터 단말로 전파되어 오는 신호의 세기를 측정하여 위치를 추정하는 방법을 알아보자. Fingerprint 추정은 두단계로 이루어지는데 첫 번째 단계는 Database Correlation을 구축하는 과정이고 두 번째 단계는 임의의 위치에 있는 단말의 위치를 추정하는 Estimation 과정이다. 먼저 Database Correlation 과정을 보자. 선박에서 위치를 추정하고자 하는 공간을 n × m 격자 모양으로 그리고 모든 교차점에 RP (1,1) , RP (1,2) , ⋯, RP (n,m) 을 둔다. 그런 다음 각 RP 에서 N 회 만큼 L 개의 AP , 즉, AP 1, AP 2, ⋯, APL 로부터 오는 신호의 세기를 측정한다. 마지막으로 각 RP 에서 측정된 값을 평균하여 이를 DB화 한다. 그러면 DB화된 값은 (4)와 같다. 여기서
PPT Slide
Lager Image
APj 에서 들어오는 신호를 N 번 측정한 값의 평균값으로
PPT Slide
Lager Image
가 된다.
PPT Slide
Lager Image
이제 Database Correlation 과정에서 구축된 DB를 토대로 하여 임의의 위치에 있는 단말의 위치를 추정하는 문제를 그림 2 를 보면서 생각해 보자. 이는 단말이 있는 위치에서 L 개의 AP , 즉, AP 1, AP 2, ⋯, APL 로부터 오는 신호의 세기를 측정하여 측정된 값인 ( SNR 1, SNR 2, ⋯, SNRL )로부터 추정값
PPT Slide
Lager Image
를 구하는 문제가 된다.
PPT Slide
Lager Image
Fingerprint 기법에 의한 위치 추정 Fig. 2 Location estimation by the fingerprint scheme
이를 단순히 생각하면 측정된 값 ( SNR 1, SNR 2, ⋯, SNRL )를 DB에 있는 각 RP 의 값과 비교하여 Distance가 가장 작은 것을 택해 그 RP 의 위치를 단말의 위치로 결정하는 것으로 생각할 수 있다. 그러나 이러한 방법은 단말의 위치 P ( x,y )가 격자점에 있지 않기 때문에 근본적으로 추정에러를 내포하고 있다는 문제점이 있다.
그러면 이러한 문제를 해결하기 위한 방법은 무엇일까를 생각해보자. 하나의 해결방법으로 K-최근접 이웃 알고리즘을 쓰는 것을 생각할 수 있다. K-최근접 이웃 알고리즘은 최근접하는 K 개의 이웃을 이용한다는 의미를 뜻한다. 이 방법은 학습 데이터 집합에 있는 표본들 간의 유사도에 따라 라벨이 붙여져 있지 않는 표본들을 분류하는 매우 직관적인 방법이라고 할 수 있다. 즉, 라벨이 없는 표본 xu RDD 가 주어질 경우, 학습 데이터 집합에서 K 개의 가장 가까운 라벨이 있는 표본을 찾아내고 K 개의 부분 집합 내에 가장 빈도가 많이 나타나는 클래스에 xu 를 할당하는 방법이다. K-최근접 이웃 알고리즘은 단지 상수 K , 라벨이 있는 학습 데이터 집합의 표본, 거리 척도 만이 필요하다.
위치 추정이라는 측면에서 K-최근접 이웃 알고리즘을 보면 단말의 위치 P ( x,y )에서 측정된 값 ( SNR 1, SNR 2, ⋯, SNRL )과 DB에 있는 n × m 개수의 값을 비교해 보았을 때 유사도가 근접하는
PPT Slide
Lager Image
의 수는 몇 개인가를 결정하는 것이다. 여기서, Distance를 유클리드로 쓸 때 유사도는 (5)와 같이 된다.
PPT Slide
Lager Image
여기서, Di P ( x,y )에서 측정된 값 ( SNR 1, SNR 2, ⋯, SNRL )과 DB에 저장된 RP (1,1) , RP (1,2) , ⋯, RP(n,m) i 째 값
PPT Slide
Lager Image
과의 유사도이고, sj P ( r )에서 APj 로부터 들어오는 신호의 측정값이며
PPT Slide
Lager Image
는 DB의 i RP 에서 APj SNR 의 평균값이다.
식 (5)에 의해 계산된 유사도 값 중에서 가장 가까운 K 개 값을 결정할 수 있기 때문에 (6)을 이용하여 단말의 위치에 대한 추정값
PPT Slide
Lager Image
를 구할 수 있다.
PPT Slide
Lager Image
즉, 단말이 있는 위치에서 측정된 신호세기의 값과 가장 가까운 K 개의 RP 를 결정하여, x 방향으로 평균값과 y 방향으로의 평균값을 구해
PPT Slide
Lager Image
PPT Slide
Lager Image
를 구한다.
Ⅳ. 모의실험
선박의 실내 환경에서 Fingerprint 기법을 적용하여 위치를 추정하는 문제를 모의실험을 통해 검증하였다. 선박의 실내 환경과 유사하게 가로 25m × 세로 4m인 공간을 만들고 1m간격으로 39개의 RP 를 배치하고 두개의 AP 가 설치되어 있는 장소에서 단말로 Samsung 노트북 R530을 써서 실험을 하였다.
- [ SNR DB 구축 ]
WLAN 환경에서 AP 1과 AP 2로부터 각 RP 로 들어오는 신호의 세기를 Netstumbler를 써서 1초 단위로 100회를 측정하였다. 각 RP 에서 측정된 값으로부터
PPT Slide
Lager Image
PPT Slide
Lager Image
를 구하여 표 1 과 같이 DB화 하였다.
AP1과 AP2에 대한 각 RP에서의 수신 SNR의 평균값과 거리값Table. 1Average values of the SNRs of signals received at each of RPs from AP1 and AP2 and Distance
PPT Slide
Lager Image
AP1과 AP2에 대한 각 RP에서의 수신 SNR의 평균값과 거리값 Table. 1 Average values of the SNRs of signals received at each of RPs from AP1 and AP2 and Distance
- [ Example ]
그림 3 의 Test Point 위치인 (7.5, 0.7)에 단말이 있을때, 그 지점에서 AP 1과 AP 2로부터 들어오는 신호의 세기를 측정하여 측정된 값으로부터 단말의 위치를 추정하는 모의실험을 하였다.
PPT Slide
Lager Image
Fingerprint 기법에 의한 위치 추정 [Test Point 위치 (x,y) = (7.5,0.7)] Fig. 3 Location estimation by the fingerprint scheme: the location (x,y) of the test point is (7.5,0.7)
단말이 있는 지점에서 신호의 SNR 를 측정하였는데 SNR 1 = 5이고, SNR 2 = 3 나타난다. AP 1로부터 수신된 신호와 DB의 각 RP 에 구축되어 있는 값과의 차이인
PPT Slide
Lager Image
AP 2로부터 수신된 신호와 DB의 각 RP 에 구축되어 있는 값과의 차이인
PPT Slide
Lager Image
를 구하여 각 RP 에서 Distance
PPT Slide
Lager Image
를 구하였는데 표1 에서 그 결과를 보여주고 있다. 그런 후 K-최근접 이웃 알고리즘을 적용하기 위해 K 값을 구하였다. 그림 4 에서 보면 알 수 있듯이 K = 10일 때 Mean Error 값이 최소가 되기 때문에 K 를 10으로 결정하였다.
PPT Slide
Lager Image
K에 따른 Mean Error (K = 10일 때 최소값) Fig. 4 Mean error versus K (minimum at K=10)
표 1 에서 Distance Di 가 작은 순으로 10개의 RP 를 선택하였고
PPT Slide
Lager Image
PPT Slide
Lager Image
를 구하였다. 즉, K =10일 때의 선택된 RP 의 좌표값은 ( x,y ) = {(0,0), (4,2), (6,0), (6,2), (8,1), (8,2), (10,0), (11,1), (11,2) (12,1)}이 되기 때문에 x 방향의 추정값은
PPT Slide
Lager Image
=7.6이고, y 방향의 추정값은
PPT Slide
Lager Image
=0.8됨을 알 수 있었다.
Ⅴ. 결 론
본 논문에서는 GPS 신호가 도달하지 않는 선박의 실내 환경에서 위치를 추정하는 문제를 고찰하였다. 추정 방법으로는 K-최근접 이웃 알고리즘 기반 Fingerprint 기법에 의한 위치 추정 방법을 적용하였다. Fingerprint 기법을 쓰기 위해 가로 25m × 세로 4m인 공간을 만들고 1m간격으로 39개의 RP 를 배치하고 두 개의 AP 가 설치되어 있는 장소에서 단말로 Samsung 노트북 R530을 써서 실험을 하였다. 39개의 RP 에서 각각 N =100회의 수신신호를 측정함으로써 신뢰성 있는 DB를 구축하였고 이를 토대로 (7.5, 0.7)위치에 단말기가 있을 때 위치를 추정하는 모의실험을 하였다. 모의실험 결과 x 방향의 추정값은
PPT Slide
Lager Image
=7.6이었고, y 방향의 추정값은
PPT Slide
Lager Image
=0.8이었다.
모의실험을 통해 알 수 있는 사실은 선박의 환경에서는 정확한 위치보다는 어느 공간에 단말을 갖고 있는 선원이 있는가를 아는 것이 중요하기 때문에, 이런 관점에서 보았을 때 추정 성능은 대체적으로 우수함을 알 수 있었고, 비교적 적은 무선 장비를 사용하는 Fingerprint 기법을 적용하여 위치를 추정하는 것에 대한 타당성을 검증할 수 있었다.
Acknowledgements
이 논문은 한국연구재단의 기초연구사업(대학중점연구소: NRF-2009-0093828)과 미래창조과학부 및 정보통신산업진흥원의 IT융합 고급인력과정 지원사업의 연구결과로 수행되었음(NIPA-2014-H0401-14-1009).
BIO
김범무(Beom-mu Kim)
2012년 2월 : 목포대학교 정보전자공학과 학사(공학인증)
2014년 2월 : 목포대학교 전자공학과 석사
2014년 3월 ~ 현재 : 목포대학교 전자공학과 박사과정
※관심분야 : LBS, WSN, IoT
정민아(Min A Jeong)
1992년 2월 : 전남대학교 이학사
1994년 2월 : 전남대학교 이학석사
2002년 2월 : 전남대학교 이학박사
2002년 4월 ~ 2003년 2월 : 광주과학기술원정보통신공학과 Post-Doc
2003년 4월 ~ 2005년 2월 : 전남대학교 전자통신기술연구소 Post-Doc
2011년 9월 ~ 2013년 2월 : Cleveland Clinic Research
2005년 3월 ~ 현재 : 목포대학교 컴퓨터공학과 부교수
※관심분야 : 데이터베이스/데이터마이닝, 생체인식시스템, 무선통신응용분야, 임베디드시스템
이성로(Seong Ro Lee)
1987년 2월 : 고려대학교 전자공학과 학사
1990년 2월 : 한국과학기술원 전기 및 전자공학과 석사
1996년 8월 : 한국과학기술원 전기 및 전자공학과 박사
1997년 ~ 현재 : 목포대학교 정보전자공학과 교수
※관심분야 : Digital Communication System, 위성통신, 해양텔레매틱스, USN
References
Lee Jang-Jae , Kwon Jang-Woo , Jung Min-A , Lee Seong-Ro 2010 “Fingerprinting Bayesian Algorithm for Indoor Location Determination,” The Journal of Korea Information and Communications Society 35 (6) 888 - 894
Lee Jang-Jae , Jung Min-A , Lee Seong-Ro , Song Iick-Ho 2011 “KNN/ANN Hybrid Location Determination Algorithm for Indoor Location Base Service,” The Journal of Institute Of Electronics And Information Engineers 48 (2) 109 - 115
Lee Jang-Jae , Song Lick-Ho , Kim Jong-Hwa , Lee Seong-Ro 2011 “Optimized KNN/IFCM Algorithm for Efficient Indoor Location,” The Journal of Institute Of Electronics And Information Engineers 48 (2) 125 - 133
Lee Jang-Jae , Jung Min-A , Lee Seong-Ro 2010 “KNN/PFCM Hybrid Algorithm for Indoor Location Determination in WLAN,” The Journal of Institute Of Electronics And Information Engineers 47 (6) 146 - 153
Jo Hyeong-Gon , Jeong Seol-Young , Kang Soon-Ju 2012 “Enhanced Accurate Indoor Localization System Using RSSI Fingerprint Overlapping Method in Sensor Network,” The Journal of Korea Information and Communications Society 37C (08) 731 - 740    DOI : 10.7840/kics.2012.37C.8.731
Kim Taehoon , Tak Sungwoo 2013 “Modeling and Performance Evaluation of AP Deployment Schemes for Indoor Location-Awareness,” Journal of the Korea Institute of Information and Communication Engineering 17 (4) 847 - 856    DOI : 10.6109/jkiice.2013.17.4.847
Cha Jae-Young , Kong Young-Bae , Choi Jeung-Won , Ko Jong-Hwan , Kwon Young-Goo 2012 "IEEE 802.15.4a based Localization Algorithm for Location Accuracy Enhancement in the NLOS Environment," Journal of the Korea Institute of Information and Communication Engineering 16 (8) 1789 - 1798    DOI : 10.6109/jkiice.2012.16.8.1789
Son Sanghyun , Choi Hoon , Cho Hyuntae , Baek Yunju 2013 "Location Information Reliability-Based Precision Locating System Using NLOS Condition Estimation," The Journal of Korea Information and Communications Society 38C (1) 97 - 108    DOI : 10.7840/kics.2013.38C.1.97
Amundson I. , Sallai J. , Koutsoukos X. , Lédeczi Á. , Maróti M. 2011 “RF angle of arrival-based node localisation,” Int. J. Sensor Networks 9 (3/4) 209 - 224
Ravindra S , Jagadeesha S N 2013 “TIME OF ARRIVAL BASED LOCALIZATION IN WIRELESS SENSOR NETWORKS: A LINEAR APPROACH,” Signal & Image Processing : An International Journal (SIPIJ) 4 (4) 13 - 30
Cong L. , Weihua Zhuang 2001 “Non-line-of-sight error mitigation in TDOA mobile location,” IEEE Global Telecommunications Conference 1 680 - 684
Kamol K. , Prashant K. “Properties of Indoor Received Signal Strength for WLAN Location Fingerprinting,” IEEE First Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services (Mobi Quitous’04)
Lim Yujin , Park Jaesung , Ahn Sanghyun 2008 “A Geometric Approach for the Indoor Localization System,” The Journal of Institute Of Electronics And Information Engineers 45TC 1058 - 1065
Ahn Daye , Ha Rhan 2014 “Indoor Localization Methodology Based on Smart Phone in Home Environment,”'14-04 The Journal of Korea Information and Communications Society 39C (04) 315 - 325    DOI : 10.7840/kics.2014.39C.4.315
Woo Sung-Hyun , Jeon Hyun-Sik , Park Hyun-Ju 2006 “A Study on NLOS Error Solution Method in Indoor Location Estimate,” Korea Computer Conference 33 (1(D)) 178 - 180
Chan Solomon , Sohn Gunho “INDOOR LOCALIZATION USING WI-FI BASED FINGERPRINTING AND TRILATERATION TECHIQUES FOR LBS APPLICATIONS,” International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences May 16-17, 2012 XXXVIII-4/C26
Jun MA , Xuansong LI , Xianping TAO , Jian LU “Cluster Filtered KNN:A WLAN-Based Indoor Positioning Scheme,” WOWMOM '08 Proceedings of the 2008 International Symposium on a World of Wireless, Mobile and Multimedia Networks 23-26 June 2008
Papadopoulos S. , Bakiras S. , Papadias D. “Nearest Neighbor Search with Strong Location Privacy,” The 36th International Conference on Very Large Data Bases September 13,2010 619 - 629