Journal of Positioning, Navigation, and Timing (J Position Navig Timing; JPNT)
Sanghyun Kim
, Jiwon Seo†
School of Integrated Technology, Yonsei University, Incheon 21983, South Korea
†Corresponding Author: Jiwon Seo, E-mail: jiwon.seo@yonsei.ac.kr
Citation: Kim, S., & Seo, J., 2024, Performance Analysis of Zonotope Shadow Matching Algorithm According to Various Urban Environments, Journal of Positioning, Navigation, and Timing, 13, 215-220.
Journal of Positioning, Navigation, and Timing (J Position Navig Timing) 2024 September, Volume 13, Issue 3, pages 215-220. https://doi.org/10.11003/JPNT.2024.13.3.215
Received on May 13, 2024, Revised on Jun 01, 2024, Accepted on Jun 13, 2024, Published on Sep 15, 2024.
License: Creative Commons Attribution Non-Commercial License (https://creativecommons.org/licenses/by-nc/4.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
In urban areas, signals can be blocked and reflected by buildings, reducing the reliability of global navigation satellite systems (GNSS). To address this, the zonotope shadow matching (ZSM) algorithm has been proposed to estimate the set-valued receiver position by calculating the GNSS shadow based on the zonotope. However, the existing study only analyzed the performance of ZSM in dense urban areas where GNSS shadows occur frequently, and the performance analysis in various urban environments was insufficient. Therefore, in this paper, we analyzed the performance of the ZSM algorithm in four urban environments with different characteristics. The results showed that the receiver position estimation performance of ZSM was relatively poor in environments where buildings were not densely populated, and the performance of ZSM was shown to be effective in urban environments with narrow roads and tall buildings.
global navigation satellite system, urban areas, zonotope shadow matching
위성항법시스템(Global Navigation Satellite System; GNSS)은 운송 수단 및 위치기반서비스(Location-Based Service; LBS)의 기본이 되는 기술로, 최근 자율주행자동차 등의 미래 모빌리티 기술이 부각되면서 그 중요성이 더욱 높아지고 있다 (Lee et al. 2022a, Yun et el. 2022, Kim & Seo 2023). 그러나, 건물이 밀집된 도심 지역에서는 신호가 건물에 의해 차단되거나, 건물에 의해 반사되는 다중경로 현상에 의해 위성항법시스템의 신뢰성이 저하될 수 있다 (Jia et al. 2021, Lee et al. 2022b, Kim et al. 2023). 이러한 문제를 해결하기 위한 방법으로, 3차원 도시 모델을 사용하여 위치 추정 성능을 향상시키는 3D-mapping-aided (3DMA) GNSS가 제안된 바 있다 (Groves & Adjrad 2019).
3DMA GNSS의 대표적인 기법 중 하나로 shadow matching이 있다 (Groves 2011). 이 기법은 건물에 가로막혀 위성의 가시선(Line-of-Sight; LOS) 신호가 수신되지 않는 shadow 영역을 이용하는 방식이다. 일반적인 shadow matching은 사용자의 위치 후보 영역을 격자화 한 뒤, 이들 중 사용자가 위치할 가능성이 가장 높은 격자 영역을 선택하여 위치를 결정한다. 그러나 격자 기반의 shadow matching은 격자의 해상도에 따른 trade-off 문제를 고려해야 한다는 한계가 있다 (Groves et al. 2015). 격자의 해상도를 높일수록 위치 결정의 정밀도가 증가하지만, 연산 시간이 증가하는 문제가 발생한다.
이 문제를 해결하기 위해, 최근에는 위치 후보를 여러 개의 격자가 아닌 하나의 세트(set)로 설정하는 세트 기반 shadow matching 방식이 제안되었다. Bhamidipati et al. (2022)은 사용자 위치 후보 영역과 3D 도시 모델 등 shadow matching 알고리즘에 사용되는 모든 요소를 zonotope으로 표현하는 zonotope shadow matching (ZSM) 기법을 개발하였다 (Bhamidipati et al. 2022). Zonotope은 볼록 대칭 형태의 polytope으로, 다양한 선행 연구에서 세트를 표현하는 데 사용되었으며 빠른 벡터 연산이 가능하다는 장점이 있다 (Althoff et al. 2010). 이를 통해 ZSM은 기존 기법의 trade-off 문제를 해결했을 뿐 아니라, 연산 시간은 크게 줄이면서도 도심 지역에서의 뛰어난 위치 추정 성능을 증명하였다.
그러나 ZSM은 건물에 의해 발생하는 신호의 shadow를 직접 계산하여 이를 기반으로 위치를 추정하는 방식으로, 주변 건물의 높이나 밀집도 같은 도심 환경의 특징에 따라 성능이 달라질 수 있다. 예를 들어, 건물의 높이나 밀집도가 낮은 도심 환경에서는 발생하는 shadow 영역이 제한되므로 ZSM의 위치 추정 성능이 저하될 수 있다. 기존 연구에서는 많은 건물이 밀집된 두 개의 정적 환경에서만 ZSM의 성능을 분석하였을 뿐, 다양한 도심 환경에서의 ZSM 성능 분석이 미흡하였다.
따라서 본 논문에서는 다양한 특징을 가지는 도심 환경에서 수집된 Global Positioning System (GPS) 신호를 기반으로, 도심 환경에 따른 ZSM 알고리즘의 성능을 분석하였다. 본 논문의 2장에서는 ZSM 알고리즘에 대해 설명하며, 3장에서는 다양한 도심 환경에서의 GPS 신호 수집을 다룬다. 4장에서는 ZSM 알고리즘의 성능 분석을 다루며, 마지막으로 5장에서는 결론을 제시한다.
ZSM 알고리즘은 기본적으로 다음의 가정에 기반한다 (Bhamidipati et al. 2022). 사용자는 지면 위에 위치한다고 가정하며, 3D 도시 모델의 부정확성과 건물의 재질이 GPS 신호에 미치는 영향은 무시한다. 또한, 위성 신호의 수신 환경 정보가 주어져 있다고 가정한다. 즉, 각 위성 신호가 가시선 신호가 수신되는 LOS 신호인지, 비가시선(Non-Line-of-Sight; NLOS) 신호만 수신되는 NLOS 신호인지 알고 있다고 가정한다.
ZSM 알고리즘의 수신기 위치 추정 과정은 Fig. 1과 같다. ZSM 알고리즘의 입력으로는 3D 도시 모델, 신호의 ephemeris로부터 계산된 위성의 위치, 그리고 수신기 위치를 포함하는 위치 후보 영역인 area of interest (AOI)가 있다. 이를 통해 ZSM은 각 위성건물 쌍별로 LOS 신호가 수신되지 않는 GNSS shadow 영역을 계산한다. 임의의 세 개 위성에서 계산된 GNSS shadow 영역 예시는 Figs. 2a-c에 나타나 있다. 이후, 계산된 GNSS shadow와 주어진 위성 신호의 수신 환경 정보를 바탕으로 수신기 위치를 추정한다. 자세한 위치 추정 과정은 Fig. 2d에 나타나 있다.
먼저 AOI 전체를 수신기의 위치 후보 세트로 설정한다 (Fig. 2d의 분홍색 영역). 그런 다음, 각 위성에서 계산된 GNSS shadow와 수신기 위치 후보 세트 사이의 연산을 통해 위치 후보 세트를 점차 줄여 나간다. 이때, 위성의 수신 환경 정보에 따라 다른 연산 방법이 적용된다. 만약 위성이 LOS 신호라면, 수신기는 해당 위성에 의해 계산된 GNSS shadow의 외부 영역에 위치할 것이므로, 수신기 위치 후보와 GNSS shadow 사이의 subtraction 연산을 적용한다. 반면, 위성이 NLOS 신호라면, 수신기는 GNSS shadow 내부에 위치할 것이므로, 수신기 위치 후보와 GNSS shadow 사이의 intersection 연산을 적용한다. 모든 위성에 대해 연산을 진행한 후 최종적으로 남은 수신기 위치 후보 영역이 최종 수신기 위치 세트로 결정된다.
Fig. 1. Set-valued receiver position estimation process of ZSM algorithm.
Fig. 2. Simulation for estimating receiver position set using ZSM algorithm.
본 논문에서는 다양한 도심 환경에서 ZSM의 성능을 분석하기 위해 Fig. 3의 하드웨어를 사용하여 GPS 신호를 수집하였다. GPS 신호 수집은 Antcom 3G1215RL-AA-XT-1 안테나와 NovAtel PwrPak7 수신기를 통해 이루어졌으며, 수신기의 위치 참값(ground truth)은 NovAtel GPS-703-GGG 안테나 및 NovAtel SPAN-SE, NovAtel UIMU-H58에서 획득한 GNSS/INS 데이터를 Inertial Explorer 소프트웨어로 후처리하여 얻었다. ZSM 알고리즘을 적용하기 위해 필요한 위성 신호의 수신 환경 정보는 3D 도시 모델과 수신기의 위치 참값을 기반으로 생성하였다. 신호의 ephemeris로부터 계산된 위성의 위치와 수신기 위치 참값을 잇는 LOS 벡터가 3D 도시 모델의 건물과 교차하면 NLOS 신호, 교차하지 않으면 LOS 신호로 분류하였다. 또한 본 논문에서 사용된 3D 도시 모델은 ONEGEO 사에서 제공한 상용 모델이다 (ONEGEO 2024).
본 논문에서는 Fig. 4에 나타난 네 개의 서로 다른 도심 환경에서 GPS 신호를 수집하였다. 각 도심 환경의 3D 도시 모델을 시각화한 결과는 Fig. 5에, 각 환경에서 수집된 GPS 위성의 skyplot 결과는 Fig. 6에 제시되어 있다. 또한, 각 도심 환경의 특징은 Table 1에 요약되어 있다. 첫 번째 환경은 도로의 한쪽 면에만 건물이 존재하는 환경으로, 이 경우 다중경로 현상이 다른 환경들에 비해 적게 발생할 것으로 예상된다. 두 번째는 낮은 건물로 둘러싸인 light urban 환경으로, 7개의 LOS 위성이 수신되었다. 세 번째는 높은 건물로 둘러싸인 medium urban 환경으로, 5개의 LOS 위성과 1개의 NLOS 위성이 수신되었다. 네 번째 환경은 더욱 밀집된 높은 건물로 둘러싸인 deep urban 환경으로, 가장 많은 3개의 NLOS 신호가 수신되었다. 또한 각 도심 환경에 대해 수신기가 위치하는 도로의 폭 대비 주변 건물의 높이를 계산한 결과, deep urban 환경에서 가장 높은 2.06의 값을 나타냈다.
Fig. 3. GPS signal collection hardware.
Fig. 4. Four urban environments where GPS signal collection experiments were conducted.
Fig. 5. 3D city model for each urban environment.
Fig. 6. GPS satellite skyplot.
Table 1. Characteristics of four urban environments.
| Environment | Number of LOS satellites | Number of NLOS satellites | Building height to street width ratio | |
|---|---|---|---|---|
| 1 | One side building | 9 | 0 | 0.63 |
| 2 | Light urban | 7 | 0 | 1.36 |
| 3 | Medium urban | 5 | 1 | 1.90 |
| 4 | Deep urban | 5 | 3 | 2.06 |
다음으로, ZSM 알고리즘의 성능 분석을 진행하였다. 본 논문에서는 기존의 일반적인 shadow matching (SM) 기법 (Wang et al. 2013)과 ZSM 알고리즘의 성능을 비교하고, 네 개의 서로 다른 도심 환경에서 ZSM 알고리즘의 성능이 어떻게 달라지는지 분석하였다.
본 논문에서 사용한 ZSM 알고리즘의 AOI는 Fig. 7에 나타난 것과 같이 한 변의 길이가 120 m인 정사각형으로, 수신기가 위치한 도로의 along-street 방향과 cross-street 방향에 AOI의 각 변이 평행하도록 설정하였다. 또한 AOI가 수신기 위치를 반드시 포함하도록 하기 위해 수신기 위치 참값을 AOI의 중심으로 설정하였다. SM 기법에서도 ZSM과 동일한 크기의 AOI를 사용하였으며, AOI 내 격자 크기는 3 m로 설정하였다.
ZSM 알고리즘 및 SM 기법의 성능 분석 지표로는 alongstreet position bound와 cross-street position bound를 사용하였다 (Bhamidipati et al. 2022). ZSM 알고리즘의 경우, Fig. 7에 나타난 것과 같이 최종 수신기 위치 세트를 기반으로 along-street 방향과 cross-street 방향에 따른 position bound 크기를 측정하였다. 이때 최종 수신기 위치 세트의 position bound가 작게 구해질수록 수신기의 위치를 더욱 정밀하게 추정할 수 있어 ZSM 알고리즘의 성능이 효과적인 것으로 판단할 수 있다. 그런데 Fig. 7에서 볼 수 있듯, ZSM 알고리즘의 결과로 여러 개의 분리된 수신기 위치 세트가 발생할 수 있다. 본 논문에서는 네 개의 도심 환경에서의 결과를 동등하게 비교하기 위해, 여러 개의 수신기 위치 세트가 발생한 경우, 수신기 위치 참값이 포함된 세트를 선택하여 position bound 분석을 진행하였다. SM 기법의 경우 각 격자에서의 visibility score가 결과로 얻어지며, 이에 대한 position bound 계산은 Bhamidipati et al. (2022)에서 사용한 weighted empirical covariance (Martens et al. 2003) 기반의 방법을 이용하였다.
Fig. 7. Our AOI setting method and depiction of validation metrics (i.e., along-street position bound, cross-street position bound).
Fig. 8은 네 개의 도심 환경에 대해 진행한 ZSM 알고리즘의 결과를 나타낸다. One side building 환경에서는 건물이 없는 면에서 수신기 위치가 제대로 추정되지 않는 것을 확인할 수 있다. 또한, 낮은 건물이 많은 light urban 환경에서도 여전히 넓은 영역의 수신기 위치 세트가 나타난다. 반면 medium urban 환경에서는 높은 건물로 인해 GNSS shadow 영역 크기가 증가하여 수신기 위치 세트를 더욱 좁게 추정할 수 있었고, deep urban 환경에서는 이전 환경들보다 현저히 작은 수신기 위치 세트를 추정할 수 있었다.
Fig. 8. Results of ZSM algorithm in four urban environments.
네 개의 도심 환경에 대한 SM 기법의 결과는 Fig. 9에 나타나 있다. 각 격자에 표시된 visibility score 값이 클수록 수신기가 위치할 가능성이 높으며, 가장 큰 visibility score를 가지는 격자의 집합이 ZSM의 최종 수신기 위치 세트 결과와 유사한 것을 확인할 수 있다.
Fig. 9. Results of SM algorithm in four urban environments.
Fig. 10은 각 환경에서의 ZSM 알고리즘과 SM 기법의 결과를 기반으로 along-street position bound와 cross-street position bound를 비교한 그래프이다. SM 기법의 결과로는 모든 환경에서 200 m가 넘는 position bound가 구해졌다. 이는 기존 연구에서도 관찰된 바와 같이, 비선형적이고 multimodality 특징을 가지는 shadow matching 분포를 단순히 Gaussian 분포로 근사화하여 position bound를 계산하였기 때문이다 (Bhamidipati et al. 2022). 반면 ZSM 알고리즘은 SM에 비해 작은 수준의 position bound를 추정할 수 있었다. 동일한 환경에서 ZSM 알고리즘의 결과를 살펴보면, cross-street position bound가 along-street position bound보다 작게 나타났다. 이는 일반적으로 위성과 건물 사이의 GNSS shadow가 cross-street 방향으로 발생하기 때문이다. 또한, 서로 다른 환경에서 ZSM 알고리즘의 결과를 비교해 보면, 높은 건물로 밀집된 도심 환경일수록 좁은 position bound를 보임을 확인하였다. 이는 주로 밀집된 도심 환경에서 많은 NLOS 위성이 발생하기 때문으로 보인다. NLOS 위성은 수신기의 위치 후보를 GNSS shadow 내부로 제한할 수 있어 ZSM 알고리즘의 수신기 위치 세트 업데이트 과정에서 좁은 position bound를 형성하는 데 유리하다. 결과적으로, ZSM 알고리즘은 밀집된 도심 환경에서 효과적인 성능을 보인다는 것을 증명하였다.
Fig. 10. Comparison of along-street position bound and cross-street position bound in four urban environments for ZSM and SM.
건물이 밀집된 도심 지역에서는 신호가 건물에 의해 차단되고 반사되어 GNSS의 신뢰성이 저하될 수 있다. 이를 해결하기 위해 zonotope을 기반으로 GNSS shadow를 계산하여 수신기를 추정하는 ZSM 알고리즘이 제안되었다. 그러나 기존 연구에서는 GNSS shadow가 많이 발생하는 밀집된 도심 지역에서만 ZSM의 성능을 분석했으며, 다양한 도심 환경에서의 성능 분석은 미흡하였다. 따라서 본 논문에서는 서로 다른 특징을 가진 네 개의 도심 환경을 설정하고, 해당 환경에서 GPS 신호를 수집하여 ZSM 알고리즘의 성능을 분석하였다. 그 결과, 건물이 밀집되지 않은 환경에서는 ZSM의 위치 추정 성능이 상대적으로 떨어졌으며, 좁은 도로와 높은 건물이 있는 도심 환경에서는 ZSM의 성능이 더욱 효과적임을 확인할 수 있었다. 다만, 본 연구에서는 Fig. 6에서처럼 도심 환경 간에 위성의 기하학적 배치가 동일하지 않음을 볼 수 있는데, 향후 동일한 위성 배치 상황에서 각 도심 환경의 성능을 분석하면 더욱 정확한 분석이 가능할 것이다. 또한, 향후에는 ZSM 알고리즘과 GPS 기반 측위 알고리즘을 결합한 하이브리드 기법을 개발하여 주변 환경에 따라 최적의 측위 방식을 적용하는 연구가 가능할 것으로 보인다. 아울러, 최근 활발히 연구되고 있는 기계 학습 및 딥러닝 기반의 위성 신호 수신 환경 탐지 기법을 활용하여, 위성 신호 수신 환경 정보가 제공되지 않는 상황에서도 ZSM 알고리즘의 성능을 분석할 수 있을 것이다.
본 연구는 과학기술정보통신부의 재원으로 한국연구재단, 무인이동체원천기술개발사업단의 지원을 받아 수행되었음 (2020M3C1C1A01086407). 또한, 이 연구는 정부(과학기술정보통신부)의 재원으로 한국연구재단의 지원을 받아 수행된 연구임 (RS-2024-00358298).
Conceptualization, S. Kim and J. Seo; methodology, S. Kim and J. Seo; software, S. Kim; validation, S. Kim; formal analysis, S. Kim; writing—original draft preparation, S. Kim; writing—review and editing, J. Seo; visualization, S. Kim.
The authors declare no conflict of interest.
Althoff, M., Stursberg, O., & Buss, M. 2010, Computing reachable sets of hybrid systems using a combination of zonotopes and polytopes, Nonlinear analysis: hybrid systems, 4, 233-249. https://doi.org/10.1016/j.nahs.2009.03.009
Bhamidipati, S., Kousik, S., & Gao, G. 2022, Set-valued shadow matching using zonotopes for 3D-map-aided GNSS localization, Navigation: Journal of the Institute of Navigation, 69, navi.547. https://doi.org/10.33012/navi.547
Groves, P. D. 2011, Shadow matching: A new GNSS positioning technique for urban canyons, The Journal of Navigation, 64, 417-430. https://doi.org/10.1017/S0373463311000087
Groves, P. D. & Adjrad, M. 2019, Performance assessment of 3D-mapping-aided GNSS part 1: Algorithms, user equipment, and review, Navigation, 66, 341-362. https://doi.org/10.1002/navi.288
Groves, P. D., Wang, L., Adjrad, M., & Ellul, C. 2015, GNSS shadow matching: The challenges ahead, in Proc. 28th International Technical Meeting of the Satellite Division of The Institute of Navigation, 14-18 Sept 2015, Tampa, FL, USA, pp.2421-2443. https://www.ion.org/publications/abstract.cfm?articleID=12866
Jia, M., Lee, H., Khalife, J., Kassas, Z. M., & Seo, J. 2021, Ground vehicle navigation integrity monitoring for multi-constellation GNSS fused with cellular signals of opportunity, in Proc. ITSC, 19-22 Sept 2021, Indianapolis, IN, USA, pp.3978-3983. https://doi.org/10.1109/ITSC48978.2021.9564686
Kim, S. & Seo, J. 2023, Machine learning-based classification of GPS signal reception conditions using a dual polarized antenna in urban areas, in Proc. IEEE/ION Position, Location, and Navigation Symposium, 24-27 Apr 2023, Monterey, CA, USA, pp.113-118. https://doi.org/10.1109/PLANS53410.2023.10140036
Kim, S., Park, S., & Seo, J. 2023, Single antenna based GPS signal reception condition classification using machine learning approaches, Journal of Positioning, Navigation, and Timing, 12, 149-155. https://doi.org/10.11003/JPNT.2023.12.2.149
Lee, H., Pullen, S., Lee, J., Park, B., Yoon, M., et al. 2022a, Optimal parameter inflation to enhance the availability of single-frequency GBAS for intelligent air transportation, IEEE Transactions on Intelligent Transportation Systems, 23, 17801-17807. https://doi.org/10.1109/TITS.2022.3157138
Lee, H., Seo, J., & Kassas, Z. 2022b, Urban road safety prediction: A satellite navigation perspective, IEEE Intelligent Transportation Systems Magazine, 14, 94106. https://doi.org/10.1109/MITS.2022.3181557
Martens, H., Høy, M., Wise, B. M., Bro, R., & Brockhoff, P. B. 2003, Pre-whitening of data by covariance-weighted pre-processing, Journal of Chemometrics, 17, 153-165. https://doi.org/10.1002/cem.780
ONEGEO [Internet], cited 2024 May 7, available from: https://onegeo.co
Wang, L., Groves, P. D., & Ziebart, M. K. 2013, GNSS shadow matching: Improving urban positioning accuracy using a 3D city model with optimized visibility scoring scheme, Navigation, 60, 195-207. https://doi.org/10.1002/navi.38
Yun, J., Kim, G., Cho, M., Park, B., Seo, H. et al. 2022, Vehicle reference dynamics estimation by speed and heading information sensed from a distant point, Journal of Positioning, Navigation, and Timing, 11, 209-215. https://doi.org/10.11003/JPNT.2022.11.3.209