本篇論文提出適用於行用通訊系統下多輸入多輸出特徵定位之粒子濾波器。我們提出的技術從兩個觀點來改善在室內與室外的定位精準度。以系統的觀點，於空間通道模型(TR25.996)下使用多輸入多輸出系統特徵增進定位精準度。以訊號處理的觀點，粒子濾波器可以成功地對抗非線性問題。應用於2x2多輸入多輸出系統，我們提出的多輸入多輸出特徵定位之粒子濾波器比傳統的多輸入多輸出粒子濾波器減少約66%乘法運算。就我們所知，唯一假設通道資訊非完美已知僅有我們所提出的多輸入多輸出特徵定位之粒子濾波器。模擬結果顯示多輸入多輸出特徵定位之粒子濾波器有很好的定位精準度，於Spacing為4公尺情形下平均時間的均方根誤差約為5公尺。

對於硬體架構方面，我們提出兩種方法加速現有的處理單元-核心單元(PE-CU)架構並且減少粒子間的交換。首先，PE使用臨限取樣/權重(threshold sampling/weighting)藉由忽略小於界限的粒子運算來降低處理時間。再者，在沒有粒子間交換的情形下平均權重核心單元(weight-balanced CU)避免了效能下降。除此之外，我們應用Independent Metropolis Hasting重新取樣(IMH resampling)管線化處理重新取樣步驟。模擬結果顯示我們提出的架構相較於最大概似取樣-區域重新取樣(ML-LR) PE架構不僅提升了14.8倍的速度，同時均方根誤差也優於ML-LE PE架構約9公尺當PE個數為2。總結此論文，在通道資訊並非完美已知的情形下多輸入多輸出系統特徵定位粒子濾波器增進了精準度，同時我們提出的架構也改善了速度與精準度。

This thesis proposes the multiple input multiple output (MIMO) fingerprinting positioning particle filter (PF) for cellular system.
The proposed technique improves the positioning accuracy both indoor and outdoor from two perspectives.
For the system perspective, the MIMO system with fingerprinting improves the accuracy in the spatial channel model (TR25.996).
For the digital signal processing perspective, particle filter can successfully address the non-linearity issue.
For the 2x2 MIMO system, the proposed MIMO fingerprinting positioning particle filter can reduce about 66% multiplications of the traditional MIMO positioning particle filter in [1]. To our best knowledge, the proposed MIMO fingerprinting particle filter is the only one based on the assumption that the channel information is not perfectly known.
The simulation results show that the proposed method has the good positioning accuracy, an over-time mean RMSE about 5 m when
$Spacing$ is equal to 4m.

In the hardware architecture, we propose two techniques to speed up the current processing element-central unit (PE-CU) architecture and reduce the particle communications.
First, PE uses the threshold sampling/weighting to reduce the latency by passing over the computation of particles having difference smaller than threshold.
Second, weight-balanced CU avoids the performance degradation under the situation of no particle communications.
Moreover, we pipeline the resampling step by applying IMH resampling.
The simulation results show that the proposed architecture not only speeds up to 14.8 times faster than ML-LR PE architecture
but also achieves better RMSE about 9m than maximum likelihood prior sampling-localized resampling (ML-LR) PE architecture when the number of PEs is two.
To conclude this work, the proposed MIMO fingerprinting positioning particle filter improves accuracy based on the assumption that the channel information is not perfectly known in the spatial channel model,
and the proposed architecture improves both accuracy and latency.

1 Introduction 1
1.1 Positioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Particle Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Research Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Organization of This Thesis . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Review of Positioning Technique and Particle Filter 7
2.1 Positioning Technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.1 TOA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.2 TDOA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.3 Angle Of Arrival (AOA) . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.4 RSSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Particle Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Architecture for Particle Filter . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.1 PE-CU Architecture . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.2 Parallel PE Architecture . . . . . . . . . . . . . . . . . . . . . . . 18
3 MIMO Channel Model 23
3.1 3GPP Spatial Channel Model . . . . . . . . . . . . . . . . . . . . . . . . 24
3.1.1 BS and MS Array Topologies . . . . . . . . . . . . . . . . . . . . 24
3.1.2 General definitions and parameters . . . . . . . . . . . . . . . . . 24
3.1.3 Environments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.1.4 Channel Coefficients . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Additive White Gaussian Noise . . . . . . . . . . . . . . . . . . . . . . . 28
4 Proposed MIMO Fingerprinting Positioning Particle Filter 29
4.1 RSSI Fingerprinting Technique . . . . . . . . . . . . . . . . . . . . . . . 29
4.2 MIMO Fingerprinting Positioning Particle Filter . . . . . . . . . . . . . . 31
4.2.1 Sampling and Particle Mapping . . . . . . . . . . . . . . . . . . . 32
4.2.2 Weight Updating with Fingerprinting . . . . . . . . . . . . . . . . 34
4.2.3 Normalization and Output Estimation . . . . . . . . . . . . . . . 35
4.2.4 Systematic Resample . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2.5 Complexity Reduction . . . . . . . . . . . . . . . . . . . . . . . . 37
4.3 Simulation Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.3.1 RMSE versus Different Spacing . . . . . . . . . . . . . . . . . . . 40
4.3.2 RMSE versus Different Run . . . . . . . . . . . . . . . . . . . . . 45
4.3.3 Tracking Trajectory . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5 Proposed Weight-Balanced Architecture with Threshold Sampling/Weighting,
and IMH Resampling 53
5.1 Weight-Balanced Architecture . . . . . . . . . . . . . . . . . . . . . . . . 53
5.2 Threshold Sampling/Weighting . . . . . . . . . . . . . . . . . . . . . . . 55
5.3 IMH resampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.4 Simulation Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.4.1 RMSE versus different loops/Burn-in particles . . . . . . . . . . . 61
5.4.2 Latency versus different loops . . . . . . . . . . . . . . . . . . . . 62
6 Conclusion 77

[1] S. Bizjajeva, T. Ryden, and O. Edfors, “Mobile Positioning in MIMO System Using Particle Filtering,” in Proc. IEEE 66th Veh. Technol. Conference, Sep. 2007,pp.792–798.
[2] P. D. et al., “Particle Filtering,” in Proc. IEEE Signal Processing Magazine, Sep.2003, pp. 19–38.
[3] M. Bolic, Implementation of Particle filters: Algorithms and Hardware Architectures. VDM Verlag Dr. Muller, 2008.
[4] M. A. Chao, C. Y. Chu, C. H. Chao, and A. Y. Wu, “Efficient Parallelized Particle Filter Design on Cuda,” in Proc. IEEE Workshop on Signal Processing Systems
(SiPS-2010), San Francisco, USA, Oct. 2010, p. 1-4.
[5] Spatial channel model for Multiple Input Multiple Output(MIMO) simulations(Rel.7), 3GPP Std. TR 25.996, Rev. 7.0.0, Jun. 2007.
[6] A. Sankaranarayanan, R. Chellappa, and A. Srivastava, “Algorithmic and architectural design methodology for particle filters in hardware,” in Proc. Int. Conf.Computer Design, Oct. 2005, pp. 275–280.
[7] H. Ren, M. Meng, and L. Xu, “Indoor Patient Position Estimation Using Particle Filtering and Wireless Body Area Networks,” in Proc. of 29th Annual International78 BIBLIOGRAPHY Conference of the IEEE EMBS, Cite Internationale, Lyon, France, Aug. 2007, pp.2277 –2280.
[8] 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.
[9] H. L. Chang, J. B. Tian, T. T. Lai, H. H. Chu, and P. Haung, “Spinning beacons for precise indoor localization,” in Proc. of the 6th ACM conference on Embedded network sensor systems, Raleigh, NC, USA, Nov. 2008, pp. 127–140.
[10] M. Vossiek, L. Wiebking, P. Gulden, J. Wieghardt, and C. Hoffmann, “Wireless local positioning - Concepts, solutions, applications,” in Proc. IEEE Radio and Wireless Conference - RAWCON03, Aug. 2003, pp. 219–224.
[11] E. Hepsaydir, “Mobile Positioning in CDMA Cellular Networks,” in Proc. IEEE 66th Veh. Technol. Conference, Sep. 2007, pp. 792–798.
[12] C. Mensing, S. Sand, A. Dammann, and W. Utschick, “Interference-Aware Location Estimation in Cellular OFDM Communications Systems,” in Proc. IEEE International Conference on Communications, June 2009, pp. 1–6.
[13] T. Wigren, “Adaptive Enhanced Cell-ID Fingerprinting Localization by Clustering of Precise Position Measurements,” IEEE Trans. Veh. Technol., vol. 56, no. 5, pp.3199–3209, Sep. 2007.
[14] H. Liu, H. Darabi, P. Banerjee, and J. Liu, “Survey of Wireless Indoor Positioning Techniques and Systems,” IEEE Trans. Systems, Man, and Cybernetics, Part C: Applications and Reviews, vol. 37, no. 6, pp. 1067 – 1080, Nov. 2007.
[15] C. H. Chao, C. Y. Chu, and A. Y.Wu, “Location-Constrained Particle Filter human positioning and tracking system,” in Proc. IEEE Workshop on Signal Processing Systems (SiPS-2008), DC, USA, Oct. 2008, pp. 73–76.
[16] N. Ristic, S. Arulampalam, and N. Gordon, Beyond the Kalman Filter: particle filters for tracking. VDM Verlag Dr. Muller, 2009.
[17] B. Anderson and J. Moore, Optimal Filtering. Dover Publications, 2005.
[18] V. Cevher and J. McClellavn, “Fast initialization of particle filters using a modified metropolis-Hastings algorithm: mode-hungry approach,” in Proc. Int. Conf.
Acoustics, Speech, and Signal Processing, May 2004, pp. 1520–6149.
[19] B. Fang, “Simple solution for hyperbolic and related position fixes,” IEEE Trans. Aerosp. Electron. Syst., vol. 36, no. 4, pp. 748–753, Sep. 1990.
[20] J. Salo and G. Del Galdo and J. Salmmi, et al., “MATLAB implementation of the 3GPP Spatial Channel Model(3GPP TR 25.996),” Online, Jan. 2005, available: http://www.tkk.fi/Units/Radio/scm.
[21] D. B. Rubin, J. M. Bernardo, M. H. D. Groot, D. V. Lindley, and A. F. M. Smith,“Using the SIR algorithm to simulate posterior distributions. In Bayesian Statistics
3,” Oxford Univ. Press., pp. 395–402, 1988.
[22] L. Chen, H. Zou, L. Wu, and H. Hu, “Modified Particle Filtering for Wireless Tracking in Digital Broadcasting System,” in Proc. IEEE 4th WiCOM International Conference, Dalian, Oct. 2008, pp. 1–4.