適應性室內無線區域網路定位技術

Adaptive Location Estimation Techniques for Indoor Wireless Local Area Networks

邱奕世(Yih-Shyh Chiou)

指導教授 ： 王晉良

國立清華大學/電機資訊學院/通訊工程研究所/博士(2010年)

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

摘要

摘 要
隨著無線通訊的快速發展，使得以定位與追踪演算法為基礎的定位技術在室內環境的監督、導引、避開障礙等等的適地性型服務(LBS，location-based service)博得青睞。戶外環境對移動端(MT, mobile terminal)定位的方法通常是以全球定位系統(GPS，global positioning system)為基礎的定位系統或是以蜂巢式網路系統(cellular network system)為基礎的定位系統，然而仍會因為這些系統或方法在室內定位的準確度不足而無法將其運用在室內的環境。對室內的定位而言，基本上有兩大挑戰：一個是定位的準確度，另一個是定位的運算複雜度。為達到更好的適地性型服務，在室內環境發展更好定位準確度與(或)更低運算複雜度的定位技術是必須的。
在本論文中，我們探討如何提高定位準確度的不同定位方法。在室內無線區域網路(WLAN, wireless local area network)的系統下，我們所提出的適應性演算法是以電波傳遞模型(RPM，radio propagation modeling)、卡爾曼濾波(KF, Kalman filtering)以及射頻識別(RFID, radio-frequency identification)輔助為基礎。在RPM的定位方法中我們採用一些特定多項式函數迴歸法(Polyfit, polynomial fitting functions)得到移動端的定位結果，與訊號紋定位法(FP, fingerprinting )的結果相比較，RPM的定位方法可以減少訓練的資料點數量。因為使用FP與RPM的定位方法會造成有些估測位置不合理的情形，所以我們使用KF演算法減緩不合理的估測結果以提高定位的準確度，其中KF追蹤法所需的觀測資料(也就是移動端的位置資料)可以藉由FP或RPM的定位法取得。為了進一步提高定位的準確度，我們還利用移動端的速度資訊發展成擴展型卡爾曼濾波(EKF, estanded KF)追蹤法，在此方法中移動端的估測位置是透過等速的軌跡和電波傳遞模型的計算得到。在沒有藉由RPM的定位方法取得觀測位置的資訊的情況下，EKF演算法的複雜度較KF演算法低。與FP的定位方法相比較，KF及EKF的追蹤方法可以減緩訊號紋定位法在訊號空間量測所產生的 aliasing現象(誤解信號量測與位置關係的現象)。除此之外，為了修正KF演算法在轉角定位不夠準確的情形，我們採用RFID輔助的方法提高定位的準確度；使用RFID為輔助的KF追蹤方法同時具有校準估測位置的特性以及修正轉角效應的好處。實驗的結果顯示，在額外硬體的需求下，以RFID為輔助的KF的定位技術能夠達到相當好的定位準確度。
以KF觀念為基礎的定位技術往往需要較高的運算複雜度，運算複雜度過高的方法並不適合直接應用到實際的定位系統之中，所以我們也發展兩種有效降低追蹤演算法的運算複雜度的方法。因為α-β (Alpha-Beta)的追蹤方法可歸結為一個簡化形式的KF追蹤方法，所以首先我們使用α-β的演算法取代KF演算法的決定模式(decision mode)以避免重複計算卡爾曼增益(Kalman gain)，而且α-β的演算法不像KF演算法需要提供狀態雜訊以及測量(觀測)雜訊的參數資訊。模擬的結果顯示，在穩定的環境下，我們所提出的α-β追踪方法的效能非常接近KF追踪方法的效能，所以α-β的追蹤方法不但具有不錯的定位準確度，而且能夠有效降低運算複雜度。然而α-β追蹤方法是以固定係數濾波法為基礎，所以不夠靈活。為了避免這種情況的缺點，我們以Bayesian 濾波法為基礎，藉由前進式的因式圖形(FG, factor graphs)演算法來取代KF演算法的運算複雜度。FG的演算法是根據變數點(variable node)與因式點(factor node)之間傳遞可靠資料，這種固有的資訊傳遞性質對位置的追踪有很大的助益。與KF追蹤法相比較，我們所提出的FG方法，在可與KF追蹤法演算法相媲美的準確度下，FG運算複雜度遠低於KF追蹤法的運算複雜度。我們所提出的FG追踪方法具有定位準確度和較低的運算複雜度的兩個良好特性，對室內無線區域網路的應用而言，具有相當的吸引力。

關鍵字

位置追蹤 ； 定位技術 ； 電波傳遞模型法 ； 卡爾曼濾波 ； α-β濾波 ； 貝式濾波 ； 因式圖形 ； 和積演算法

並列摘要

Abstract
With the rapid progress in wireless communications, location estimation techniques, including positioning and tracking algorithms, have received a great deal of attention for location-based services (LBSs) in indoor environments, such as surveillance, guidance, obstacle avoidance, etc. The common methods of determining a location of mobile terminal (MT) in outdoor environments are using the global positioning system or cellular networks. However, such approaches usually could not provide enough location accuracy for indoor applications. Basically, there are two major challenging issues in indoor location estimation; one is the location accuracy, and the other is the computational complexity. To have better indoor LBSs, it is necessary to develop indoor location estimation techniques with good location accuracy and/or low computational complexity.
In this dissertation, we investigate how to improve the location accuracy of different location estimation schemes. We present adaptive algorithms based on radio propagation modeling (RPM), Kalman filtering (KF), and radio-frequency identification (RFID) assistance for indoor wireless local area networks (WLANs). In the RPM scheme, we use some specific polynomial fitting functions to determine the location of an MT, which can reduce the number of training data points in comparison with the fingerprinting (FP) method. To improve the location accuracy, we then use the KF algorithm to smooth the location estimation results obtained from the FP and the proposed RPM method. To enhance the location accuracy further, we also use the velocity information of an MT to develop an extended KF (EKF) tracking scheme. In this scheme, the estimated location of an MT is calculated from the constant-speed trajectory and the radio propagation model. Without using the RPM method to obtain the location information, the complexity of the EKF scheme is less than that of the KF scheme. As compared to the FP scheme, both the KF and EKF tracking schemes can alleviate the problem of aliasing, which is the phenomenon of misinterpretation of signal measurements. Furthermore, to overcome the inaccuracy problem around corners, RFID is applied to assist the KF tracking algorithm. The RFID-assisted KF tracking scheme can calibrate the location estimation results and correct the corner effects. Experimental results show that it can achieve excellent location accuracy at the expense of high computational complexity.
To reduce the computational complexity of the KF tracking algorithm, we develop two efficient methods for location tracking. First, we replace the decision mode of the KF tracking algorithm with an Alpha-Beta (α-β) algorithm, which is a degenerate form of the KF algorithm, to avoid repeatedly calculating the Kalman gain. With α-β tracking, the exact information of the state and measurement noise parameters used in the KF algorithm is not required. Simulation results show that the performance of the α-β tracking method is close to that of the KF algorithm under a stationary environment. Nevertheless, the α-β tracking scheme is based on a fixed-coefficient filtering, so it is not flexible enough. To avoid this disadvantage, we use a forward factor graph (FG) algorithm, instead of the KF algorithm, to simplify the implementation of Bayesian filtering. The FG algorithm is based on passing the data reliability information between the variable nodes and the factor nodes, and this inherent message-passing nature is helpful to location tracking. As compared to the KF tracking scheme, the proposed FG approach achieves close location accuracy with much lower computational complexity. With both features of good location accuracy and low computational complexity, the proposed FG tacking scheme is attractive for use in indoor WLAN applications.

並列關鍵字

Location Tracking ； Location-Estimation Techniques ； Radio Propagation Modeling ； Kalman Filtering ； Alpha-Beta Filtering ； Bayesian Filtering ； Factor Graphs ； Sum-Product Algorithm

參考文獻

[1] K. Pahlavan, X. Li, and J. P. Makela, “Indoor geolocation science and technology,” IEEE Commun. Mag., vol. 40, pp. 112-118, Feb. 2002.

[2] I. K. Adusei, K. Kyamakya, and K. Jobmann, “Mobile positioning technologies in cellular networks: an evaluation of their performance metrics,” in Proc. 2002 IEEE Military Communications Conference ( MILCOM 2002), vol. 2, Oct. 2002, pp.1239-1244.

[7] P. Bahl, V. N. Padmanabhan, and A. Balachandran, “Enhancements to the RADAR user location and tracking system,” Technical Report. MSR-TR-200-12, Microsoft Research, Feb. 2000.

[8] A. Hills, J. Schlegel, and B. Jenkins, “Object tracking through RSSI measurements in wireless sensor networks,” IEE Electr. Lett., vol. 44, pp. 653-654, May 2008.

[10] M. J. Hossain, O. Chae, Md. Mamun-Or-Rashid, and C. S. Hong, “Cost-effective maximum lifetime routing protocol for wireless sensor networks,” in Proc. 2005 IEEE Advanced Industrial Conference on Telecommunications/Service Assurance with Partial and Intermittent Resources Conference/E-Learning on Telecommunications Workshop (AICT/SAPIR/ELETE 2005), Jul. 2005, pp. 314-319.