無線感測網路中用戶定位應用之次最佳逐步佈建演算法

Sub-optimal Step-by-step Deployment Algorithm for User Localization in Wireless Sensor Networks

蔡元鈞(Yuan-Jiun Tsai)

指導教授 ： 蔡育仁

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

摘要

在本篇論文中，我們提出了一個以最小化待定位物件絕對位置的平均方差 (mean-square error)為目標的佈建演算法，用以佈建無線感測器網路中的基準用感測器 (reference sensors)，而待定位物件可以適用於仍未定位完成的感測器 (blind-folded sensors)或使用RSS (Received Signal Strength)定位系統的使用者，而基準用感測器本身的絕對位置，可由全球定位系統 (Global Positioning System)等方式得到。佈建演算法本身被設計成具有低複雜度與對非均勻 (non-homogeneous)環境的高適應性兩個特性。
為簡化已佈建網路的效能計算，我們採用克拉美-羅界 (Cramér-Rao Bound) 以替代定位演算法的平均方差，藉此避免執行特定演算法的龐大計算量，且毋須針對特訂的定位演算法。
我們藉由對演算法算出的效能與特定的基準做比較。當基準用感測器的數量較少時，我們取用完全探索後的最佳結果為基準以作比較。而當基準用感測器的數量增多時，我們根據佈建本身的特性設計有力的基準並比較之。由這些比較中，我們可以發現演算法的性能在很少的基準用感測器時就能逼近最佳性能。我們調整原先提出的演算法，以降低其複雜度，再與原先的演算法做性能上的比較。
在本篇論文的最後，我們實際執行了一個普遍性很高的定位演算法 - 最大似然法 (maximum-likelihood estimations)，以檢證用克拉美-羅界替代定位演算法的平均方差的實際效果。由模擬結果可以看出，克拉美-羅界可以確實的契合呈現定位演算法的執行效果

關鍵字

無線感測網路

並列摘要

In this article, we propose a step-by-step deployment algorithm of the localization reference sensors in wireless sensor networks, in order to minimize the mean-square error of the physical coordinates of the located objects, for both cases of users and blind-folded sensors those use received- signal strength applications. The physical coordinates of reference sensors can be obtained by global positioning system, etc. The deployment algorithm is designed to have low complexity and high flexibility to non-homogeneous environment.
To simplify the performance calculation of a deployed network, we apply Cramér-Rao Bound as a substitute of the mean-square error of localization algorithms, in order to avoid the large amount of calculation and obtain generality to localization algorithms.
The main object of this article is to verify the performance of the deployment algorithm, and this is done by making comparison between the result of proposed algorithm and some significant benchmarks. The short-term characteristics of the proposed algorithm with respect to the numbers of reference nodes are proved by comparing with exhausted search. Moreover, the long-term characteristics of the proposed algorithm with respect to the numbers of reference nodes are proved by comparing with many other benchmarks, those are designed in consideration of the nature of deployment. By these comparisons, we find that the performance of the proposed algorithm converges to the best performance very fast. Then, we modify the deployment algorithm, in order to lower down the complexity of the original algorithm, and do performance comparisons.
Last, we apply a very general localization algorithm – maximum likelihood estimations to confirm if it is suitable to substitute the performance of localization algorithm by Cramér-Rao Bound. We obtain that Cramér-Rao Bound can be treated as an accurate substitute of the performance of localization algorithms

並列關鍵字

Wireless sensor networks

參考文獻

[1] N. Patwari, A.O. Hero III, M. Perkins, N. S. Correal, and R. J. O’Dea, “Relative location estimation in wireless sensor networks,” in IEEE Trans. Signal Processing, vol. 51, no. 8, pp. 2137–2148, 2003.

[3] N. Patwari, J. N. Ash, Spyros Kyperountas, A. O. Hero III, R. L. Moses, and N.S. Correal, “Locating the nodes [Cooperative localization in wireless sensor networks],” in IEEE Signal Processing Magazine, vol. 54, 2005.

[4] Q. Shi, S. Kyperountas, N. S. Correal, F. Niu, “Performance analysis of relative location estimation for multi-hop wireless sensor network,” in IEEE Journal on Selected Areas In Communications, vol. 23, no. 4, pp. 830-838, 2005.

[6] E. G. Larsson, “Cramér-Rao bound analysis of distributed positioning in sensor networks,” in IEEE Signal Processing Letter, vol. 11, no. 3, pp. 334–337, 2004.

[7] Y. Shang, W. Ruml, Y. Zhang, and M. P. J. Fromherz, “Localization from mere connectivity,” in Proceedings Mobihoc, vol.03, pp. 201–212, 2003.