無線感測網路中使用遞增式子梯度演算法之分散式定位與追蹤技術

A Decentralized Positioning and Tracking Scheme Based on the Incremental Subgradient Algorithm for Wireless Sensor Networks

管建豪(Jian-Hao Guan)

指導教授 ： 王晉良

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

摘要

在這篇論文中我們利用信號強度和距離的關係，提出了一個新的演算法來解決在無線感測網路中定位及追蹤物體的問題。首先我們將這個定位及追蹤的問題，視為一個非線性最小平方差之最佳化的問題。一般來說，梯度搜尋類的演算法非常適合使用在解決非線性最小平方差之最佳化問題。在文獻中已經有人使用過分散式遞增子梯度演算法來對於無線感測網路中未知位置的物體進行定位與追蹤，而我們所提出的新演算法即是以分散式遞增子梯度演算法為基礎，提出加以修正變化的演算法。首先，我們增加了一個判斷的機制在原始的分散式遞增子梯度演算法中，由這個判斷機制來決定我們是否進行梯度搜尋的動作，而這個加入判斷機制的演算法我們稱之為修正型的分散式遞增子梯度演算法。藉由數學的證明以及模擬的結果，當對於一個靜止未知位置的物體位置進行估計時，修正型的分散式遞增子梯度演算法比原始的分散式遞增子梯度演算法能夠達到更準確的估計值，也就是說利用這個修正型的分散式遞增子梯度演算法所估計出來靜止物體的位置可以更加的接近真實物體的位置。而為了讓我們提出的這個修正型的分散式遞增子梯度演算法可以適用於實際的環境中，我們更進一步的提出了一個估計物體移動速度的方法，而使用這個估計的物體移動資訊於我們所提出的修正型分散式遞增子梯度演算法中，可以使得我們所提出的定位演算法不僅可以適用於靜態物體的定位上，對於追蹤一個在移動的物體，也可以達到不錯的追蹤能力。

關鍵字

分散式 ； 遞增式子梯度 ； 定位 ； 追蹤 ； 無線感測網路

並列摘要

This thesis introduces a decentralized positioning and tracking method for wireless sensor networks by utilizing the received signal strength (RSS) measurements to estimate the unknown location of an emitted source. We formulate the problem of positioning as a nonlinear least-squares optimization problem and our new approach is based on the decentralized incremental subgradient (IG) optimization methods to estimate the location of a source iteratively. At first, we add an extra step to determine whether the IG algorithm is executed to estimate the location of the source or not. By this way, a more accurate estimation can be achieved by using this modified IG algorithm to estimate the location of a stationary source. Furthermore, in order to apply the modified IG algorithm to track a moving source in practice, we present a method to estimate the velocity of the moving source and then exploit this estimation of velocity to make the convergence behavior of the modified IG algorithm associate with this estimation. Computer simulation results demonstrate that our proposed decentralized positioning and tracking method has better convergence accuracy than other decentralized positioning and tracking methods.

參考文獻

[1] X. Sheng and Y. H. Hu, “Maximum likelihood multiple-source localization using acoustic energy measurements with wireless sensor networks,” IEEE Trans. Signal Processing, vol. 53, no. 1, pp. 44-53, Jan. 2005.

[2] M. G. Rabbat and R. D. Nowak, “Decentralized source localization and tracking,” in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing, Montreal, Canada, May 2004, pp. 921-924.

[4] M. G. Rabbat and R. D. Nowak, “Quantized incremental algorithms for distributed optimization,” IEEE J. Select Areas Commun., vol. 23, no. 4, pp. 798-808, Apr. 2005.

[5] A. Nedic and D. Bertsekas, Stochastic Optimization: Algorithms and Application, chapter Convergence Rate of Incremental Sub-gradient Algorithms, pp.263-304, Kluwer Academic Publishers, 2000.

[6] A. O. Hero and D. Blatt, “Sensor network source localization via projection onto convex sets (POCS),” IEEE Trans. Signal Processing, vol. 23, no. 4, pp. 3614-3619, Sep. 2006.