基於三維虛擬基地台轉換與加權凸型最佳化之行動定位系統

Mobile Positioning System Based on 3D Virtual Base Station Transformation and Weighted Convex Optimization

蔡昇佑(Sheng-Yu Tsai)

指導教授 ： 黃元豪

國立清華大學/電機資訊學院/電機工程學系/碩士(2012年)

https://doi.org/10.6843/NTHU.2012.00704

摘要

由於FCC發布了E-911的文件，並要求在下一代移動設備的定位能力，移動定位因此吸引了許多研究關注。為了提高LOS和NLOS無線環境中的定位精度，本研究提出了一種強大的行動定位演算法來追蹤一個行動基地台（MS）的位置。本論文在3D環境中針對移動定位系統提出了新的定位技術。粒子過濾器和凸型最佳化的方法被採用來完成估計。對於行動定位，這項研究使用粒子濾波器來解決非線性通道的影響，這個動作在一個真實通道環境中成功地解決非線性問題以及對抗非理想的效果。這個技術在室內和室外的條件下提高了定位精度。此外，本研究也進行來自不同基地台距離和不同粒子過濾器的加權估計，用以提高定位性能。為了處理NLOS問題，我們提出了兩個3D虛擬基地台轉換演算法來估計在2D或3D環境中行動設備的位置。在測試實驗中，跟傳統的粒子過濾器來做比較，所提出權重虛擬基地台轉換演算法的性能可以改善約40％，而無加權虛擬基地台轉換演算法可以改善約2％到20％。然後，凸型最佳化被執行用來獲得不同基地台之間的最佳位置。由於凸型最佳化的問題過於複雜以及混合規範(mixed norm)是不可微分的，所以我們採用子梯度法來降低最佳化問題的複雜性。首先分析地圖因子來確定歐幾里得距離(Euclidean distance)，曼哈頓距離(Manhattan distance) 或混合距離(mixed distance)，然而在不同地圖中確定方法來分配地圖因子。此外，為了提高性能，我們提出了一個動態的地圖因子來取代固定的地圖因子。動態地圖因子的方法可以比固定地圖因子的方法改善約 5 ％左右。最後，本研究顯示了提出的演算法與傳統的方法來做比較的一些模擬。

關鍵字

接收訊號強度 ； 粒子濾波器 ； 虛擬演算法 ； 凸型最佳化 ； 行動定位

並列摘要

Since the FCC released the E-911 document and required the positioning capability in next generation mobile devices, the mobile positioning has attracted many research attentions. In order to enhance localization accuracy in line-of-sight (LOS) and non-line-of-sight (NLOS) wireless environments, this research presents a robust mobile positioning algorithm to track the position of a mobile station (MS). This thesis proposes new positioning techniques for the mobile positioning system in 3D environments. Particle filter and convex optimization are adopted to complete the estimation. For the mobile positioning, this work uses particle filter for solving the effect of non-linear channel, successfully addresses the non-linearity issue, and combats the non-ideal effect in a real channel environment. The technique improves the positioning accuracy in both indoor and outdoor conditions. Moreover, this research also proposes to improve the positioning performance by weighting the estimated distances of different particle filters from different base stations. To handle the non-light-of-sight (NLOS) problem, we propose two 3D virtual base station transformation (VBST) algorithms to estimate the position of mobile devices in 2D or 3D environments. Compare the traditional particle filter, the performance of proposed weighted VBST algorithm can improve about 40% and no weighted VBST algorithm can improve about 2% to 20% in the experiments. Then, the convex optimization is performed to obtain the optimal location among different base stations. Due to the convex optimization problem is too complicated and the mixed norm is non-differential, we also adopt subgradient method to reduce complexity of the optimization problem. The first analyzes the map factor that determines the Euclidean distance, Manhattan distance, or mixed distance, and then determines the methods to assign the map factor in different maps. Furthermore, we propose a dynamic map factor to replace the fixed map factor in order to enhance the performance. The dynamic map factor approach can improve about 5% than the fixed map factor approach. Finally, this study shows some simulations of the proposed algorithms and compares with the traditional approaches.

並列關鍵字

received signal strength (RSS) ； particle filter ； virtual algorithm ； convex optimization ； mobile position

參考文獻

[2] W.-Y. Chiu and B.-S. Chen, “Mobile location estimation in urban areas using mixed manhattan/euclidean norm and convex optimization,” IEEE Trans. Wireless Comm., vol. 8, no. 1, pp. 414 –423, jan. 2009.

[3] H. Ren, M.-H. Meng, and L. Xu, “Indoor patient position estimation using particle filtering and wireless body area networks,” in Proc. of 29th IEEE Annual International Conference of the EMBS, aug. 2007, pp. 2277 –2280.

and Networking, vol. 2011, no. 1, p. 17, 2011. [Online]. Available:

[5] J. Jung and H. Myung, “Range-based indoor user localization using reflected signal path model,” in Proc. of 5th IEEE International Conference on Digital Ecosystems

[6] T. Kerr, “A critical perspective on some aspects of gps development and use,” in Proc. of 16th AIAA/IEEE Digital Avionics Systems Conference (DASC), vol. 2, oct 1997, pp. 9.4 –9–9.4–20 vol.2.