適用於定位系統之分散式粒子濾波器設計與實作

Design and Implementation of Distributed Particle Filter for Positioning Systems

羅翊豪(Yi-Hao Lo)

指導教授 ： 黃元豪

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

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

摘要

本篇論文結合了特徵技術與粒子濾波器，傳統的RSSI技術存在的非視距（NLOS）和多路徑的影響。學者有提出了一種方法，稱為特徵技術改善RSSI技術的缺點，但它仍然沒有良好的表現。因此，本研究使用的過濾器來優化輸出。
然而，傳統的粒子過濾器是在ASIC架構過於複雜而難以實現。因此，這篇論文主要是在修改粒子濾波器的架構。以通訊系統角度來看，特徵定位技術可以處理多路徑和屏蔽效應的影響;而以信號處理的角度來看，粒子濾波器可以處理非線性和非高斯特性。
　　對於粒子濾波器，本篇論文修改了取樣和重新取樣的方法並且將粒子濾波器改為中央單元－處理單元的架構使處理速度變得更快。傳統的取樣方法是隨機移動粒子而造成分散的效果，本篇論文提出了一種稱為選擇性取樣的方法，它提供了一個門檻決定哪些粒子應該被移動。模擬結果顯示出該發法可以加速收斂時間，提高了精度。而傳統的重新取樣方法是以每顆粒子的權重比例來計算該粒子應該被重新取樣成幾顆單位粒子，但是這個方法需要等待所有粒子的權重都計算出來後才能做重新取樣的動作，等待的時間便會浪費掉，造成硬體的使用效率不好。所以有學者提出一種名為IMH的重新取樣方式，那就可以將硬體做成pipeline的架構，但這方法會降低準確度，所以我們提出一種名為界限型IMH的重新取樣方法，不僅可以做到pipeline的架構而且也可以維持準確度。
　　而對於行動定位來說，當目標移動時我們定位晶片所運算的時間便是目標移動的時間，所以運算時間越短代表目標移動的距離越短，也就是準確度會越高，所以我們提出了類似平行化的架構：中央單元-處理單元架構，我們有4塊處理單元是處理取樣、權重和估算結果；中央單元主要就是處理重新取樣的步驟，藉此架構我們可以將運算時間縮短為4倍但面積只需要2倍。
　　我們的實現方法是採用TSMC 18um的製程，面積為6.95mm2，功率為193mW。

關鍵字

分散式 ； 粒子濾波器 ； 定位 ； 特徵

並列摘要

This thesis combines the RSSI fingerprinting technique in MIMO system with the particle
filter to perform positioning. The traditional RSSI technique suffers from effects
of NLOS and multi-paths. The rsearchers proposed a method called fingerprinting
technique to improve the disadvantages of the RSSI technique, but it still suffers the
multi-modal effects. Therefore, this study use the particle filter to optimize the output.
However, the tradtional particle filter is too complex to implement in ASIC architecture.
Therefore, this work is to modify the particle filter architecture. In the system domain,
the MIMO fingerprinting technique can deal with the effects of multi-paths and shadowing;
In the signal processing domain, the particle filter can handle the the non-linearity
and non-Gaussian properties.
The Spacing and Run is the key points while building the fingerprinting map. The
Spacing is the resolution of the map, and the Run is the ability against the time-varying
channel. The Spacing is smaller, the accuracy is better. The Run is larger, the ability
is better. However, there is also a trade-off between the performance and cost.
For the particle filter, this work modify the sampling and resampling strategy. The
traditional sampling strategy is to add random noise to scatter the particles, and this
work proposed a method called selective sampling which offers a ThresholdS to decide
which particle should be added by random noise. The simulation shows that this strategy
can accelerate the convergence time and improve the accuracy.
Because the efficiency of the traditional systematic resampling strategy is too low,
researcher proposed the independent metropolis hasting(IMH) resample which can be
pipelined. However the performance fo the IMH resample is not good enough. Therefore,
based on the IMH resample, this work proposed the threshold IMH(T-IMH) resample
which offers a ThresholdR to be compared to the weights of the particles. When the
ThresholdR is larger, it means that the present particle is not reliable, so we replace
the present particle with the previous particle; Otherwise, we keep the present particle.
This architecture can be still pipelined, and the simulation shows that the accuracy is
better.
For the mobile positioning, the processing period is smaller, the accuracy is better.
Moreover for the base station(BS), the processing period is smaller, the more number
of users that the BS can afford. Therefore, this work propose the distributed particle
filter which is a kind of parallel processing to increase the processing speed. This work
perform the sample and weight in each processing element(PE), and the resample in
a central unit(CU). This work uses the ARM-3.2 TSMC 0.18 um cell library for logic
synthesis and the Artisan memory compiler for the memory elements. The simulation
shows that this proposed distributed architecture has smaller area throughput (AT)
product. To conclude this work, this work modify the particle filter architecture so that
we can implement the particle filter and shorten the processing period.

並列關鍵字

distributed ； particle filter ； position ； fingerprint ； IMH

參考文獻

[4] Spatial channel model for Multiple Input Multiple Output(MIMO) simula-

[1] P. D. et al., “Particle Filtering,” in Proc. IEEE Signal Processing Magazine, Sep.

design methodology for particle filters in hardware,” in Proc. Int. Conf.

[5] H. Ren, M. Meng, and L. Xu, “Indoor Patient Position Estimation Using Particle

Filtering and Wireless Body Area Networks,” in Proc. of 29th Annual International