一個新的可用於無線感測網路之分散式協作且對衝突友善之定位演算法

A New Distributed, Collaborative, Conflict-Friendly Localization Algorithm for Wireless Sensor Networks

姚欣豪(Hsin-Hao Yao)

指導教授 ： 陳秋媛

國立交通大學/理學院/應用數學系暨研究所/碩士(2015年)

https://doi.org/10.6842/NCTU.2015.00276

摘要

定位問題是無線感測網路中最重要的問題之一。兩個常用的評估定位演算法的標準為：精確度及覆蓋率，其中精確度是經由測量平均位置誤差而來，而覆蓋率則是定位成功的感測器佔全體感測器的比例。在文獻[16]中，劉等人使用三種可定位協作體單元來提升覆蓋率並減少定位誤差。在文獻[7]中，Bu等人提出對衝突友善的定位演算法來增加精確度及覆蓋率。在本論文中，我們將給出一個新的可定位協作體單元，並提出一個新的分散式協作且對衝突友善之定位演算法，此演算法同時擁有文獻[16]及文獻[7]中演算法的優點。實驗數據顯示：我們的演算法改進了文獻[16]中的圖4的覆蓋率，由89%提升到97%。此外，我們的演算法確切給出了每個已定位的感測器的位置，而不是只記錄該感測器已被定位。

關鍵字

無線感測網路 ； 定位 ； 演算法 ； 覆蓋率 ； 可定位協作體

並列摘要

Localization problem is one of the most important problems in wireless sensor networks (WSNs). Two commonly used criteria for evaluating localization algorithms are accuracy and coverage. Accuracy is measured by using the average of position errors, and coverage is the percentage of sensors which are localized. In 2005, Liu et al. [16] presented a protocol that uses three types of unit localizable collaborative body (ULCB) to enhance the coverage and to decrease the localization error. In 2012, Bu et al. [7] presented a conflict-friendly localization algorithm to increase localization accuracy and coverage. In this thesis, we will propose a new ULCB and propose a new distributed, collaborative, conflict-friendly localization algorithm, which has the advantages of both the algorithms in [16] and [7]. Simulation results show that our algorithm improves the coverage of Figure 4 in [16] from 85% to 98%. Moreover, for each localized sensor node, our algorithm reports its location instead of just mentioning that this sensor node is localized.

並列關鍵字

wireless sensor network ； localization ； algorithm ； coverage ； localizable collaborative body

參考文獻

[1] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, Wireless sensor networks: a survey, Computer Networks, vol. 38, pp. 393-422, 2002.

Anderson, and P.N. Belhumeur, A theory of network localization, IEEE Transactions on Mobile Computing, vol. 5, no. 12, pp. 1-15, 2006.

[5] A. F. Assis, L. F. M. Vieira, M. T. R. Rodrigues, and G. L. Pappa, A genetic algorithm for the minimum cost localization problem in wireless sensor networks, in Proceeding of the IEEE Congress on Evolutionary Computation, 2013.

[6] F. Barsi, A. A. Bertossi, C. Lavault, A. Navarra, S. Olariu, M. Cristina Pinotti, and V. Ravelomanana, Efficient location training protocols for heterogeneous sensor and actor networks, IEEE Transcations on Mobile Computing, vol. 10, no. 3, pp. 377-391, 2011.

[7] K. Bu, Q. Xiao, Z. Sun, and B. Xiao, Toward collinearity-aware and conflict-friendly localization for wireless sensor networks, Computer Communications, vol. 35, pp. 1549-1560, 2012.