臺灣博碩士論文加值系統

無線感測網路為具有資源有限與自我組織能力特性的網路系統，其通常佈建於人類不易到達的環境，用以偵測環境中現象的資料。但由於其製造成本低與有限電力的特性，使得感測節點在進行環境偵測時，容易發生錯誤。因此，感測節點的錯誤偵測與容錯便成為了無線感測網路中一個重要的議題。在多數已提出的容錯機制中，皆將焦點置於感測節點發生當機錯誤與電力錯誤的狀況，而較少為感測節點發生任意錯誤的拜占庭錯誤。因此，本論文將提出一個以遮罩法團系統為基礎的容錯式資料收集演算法，以容忍無線感測網路中感測節點所發生的拜占庭錯誤。此演算法將利用遮罩法團系統的特性，遮罩可能錯誤的感測資料，進而找出正確的資料值。我們的模擬結果證明，本演算法可有效地容忍拜占庭錯誤，並在不造成過多的通訊負擔下找出正確的資料。而且，在極端的環境下，即節點錯誤率達50%時，本演算法依然有48%的機率可成功地收集到正確資料值。

The wireless sensor network is a resource-constrained self-organizing system that con-sists of a large number of tiny sensor nodes. Due to the low-cost and low-power essence of sensor nodes, sensor nodes may be failure-prone when sensing and processing data. Most presented fault-tolerant researches for wireless sensor networks focused on crash faults or power faults, but less on Byzantine faults, where sensor nodes are assumed to be faulty arbi-trarily. Hence, in this paper, we propose a fault-tolerant data aggregation algorithm for Byzan-tine faults in wireless sensor networks. The algorithm utilizes the concept of Byzantine mask-ing quorum systems to mask the values which may be faulty, and find out the correct value finally. Our simulation results demonstrate that the algorithm can tolerate Byzantine faults ef-ficiently. When the fault rate of sensor nodes is up to 50%, our algorithm can still be opera-tional correctly with the success rate 48%, whereas other fault-tolerant algorithms are almost failed.

誌謝 .................... i
中文摘要 .................... ii
Abstract .................... iii
Contents .................... iv
List of Tables .................... v
List of Figures .................... vi
1. Introduction .................... 1
2. Related works .................... 4
3. Fault-tolerant data aggregation algorithm for Byzantine faults .................... 8
3.1. System model and assumptions .................... 8
3.2. Fault-tolerant data aggregation algorithm .................... 9
4. Simulation .................... 15
4.1. Simulation environment .................... 15
4.2. Simulation results .................... 15
5. Conclusion .................... 20
References .................... 21

[1] I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A Survey on Sensor Net-works,” IEEE Communication Magazine, vol. 40, no. 8, pp. 102-114, August 2002.
[2] L. Alvisi, D. Malkhi, E. Pierce, and M.K. Reiter, “Fault Detection for Byzantine Quorum Systems,” IEEE Transactions on Parallel and Distributed Systems, vol. 12, no. 9, pp. 996-1007, September 2001.
[3] M. Barborak, M. Malek, and A. Dahbura, “The Consensus Problem in Fault-Tolerant Computing,” ACM Computing Surveys, vol. 25, no. 2, pp. 171-220, June 1993.
[4] I. Chatzigiannakis and A. Kinalis, “Fault-tolerant and Efficient Data Propagation in Wire-less Sensor Networks Using Local, Additional Network Information,” Journal of Parallel and Distributed Computing, vol. 67, no. 4, pp. 456-473, 2007.
[5] J.Y. Chen, G. Pandurangan, and D.Y. Xu, “Robust Computation of Aggregates in Wireless Sensor Networks: Distributed Randomized Algorithms and Analysis,” IEEE Transactions on Parallel and Distributed Systems, vol. 17, no. 9, pp. 987-1000, 2006.
[6] S. Chessa and P. Santi, “Crash Faults Identification in Wireless Sensor Networks,” Com-puter Communications, vol. 25, no. 14, pp. 1273-1282, 2002.
[7] T. Clouqueur, Kewal K. Saluja, and P. Ramanathan, “Fault Tolerance in Collaborative Sensor Networks for Target Detection,” IEEE Transactions on Computers, vol. 53, no. 3, March 2004.
[8] D. Culler, D. Estrin, and M. Srivastava, “Overview of Sensor Networks,” IEEE Computer, vol. 37, no. 8, pp.41-49, 2004.
[9] M. Ding, F. Liu, A. Thaeler, D. Chen, and X. Cheng, “Fault-Tolerant Target Localization in Sensor Networks,” EURASIP Journal on Wireless Communication and Networking, vol. 2007, no. 1, 2007.
[10] M.J. Fischer, “The Consensus Problem in Unreliable Distributed Systems (a Brief Sur-vey),” Fundamentals of Computation Theory, pp. 127-140, 1983.
[11] B. Krishnamachari, “Distributed Bayesian Algorithms for Fault-Tolerant Event Region Detection in Wireless Sensor Networks,” IEEE Transactions on Computers, vol. 53, no. 3, March 2004.
[12] Y.C. Kuo and S.T. Huang, “A Geometric Approach for Constructing Coteries and k-Coteries,” IEEE Trans. Parallel and Distributed Systems, vol. 8, no. 4, pp. 402-411, April 1997.
[13] Y.C. Kuo and S.T. Huang, “Recognizing Nondominated Coteries and wr-Coteries by Avaibility,” IEEE Trans. Parallel and Distributed Systems, vol. 9, no. 8, pp. 721-728, August 1998.
[14] L. Lamport, R. Shostak, and M. Pease, “The Byzantine Generals Problem,” ACM Trans. Programming Languages and Systems, vol. 4, no. 3, pp. 382-401, July 1982.
[15] D. Malkhi and M. Reiter, “Byzantine Quorum Systems,” The Journal of Distributed Computing, vol. 11, no. 4, pp. 203-213, 1998.
[16] K. Martinez, J.K. Hart, and R. Ong, “Sensor Network Applications,” IEEE Computer, vol. 37, no. 8, pp. 50-56, 2004.
[17] L. Paradis and Q. Han, “A Survey of Fault Management in Wireless Sensor Networks,” Journal of Network and Systems Management, vol. 15, no. 2, pp. 171-190, 2007.
[18] K.F. SSu, C.H. Chou, H.C. Jiau, and W.T. Hu, “Detection and Diagnosis of Data Incon-sistency Failures in Wireless Sensor Networks,” Computer Networks, vol. 50, pp. 1247-1260, 2006.
[19] O. Younis, S. Fahmy, and P. Santi, “An Architecture for Robust Sensor Network Com-munications,” International Journal of Distributed Sensor Networks, vol. 1, pp. 305-327, 2005.
[20] Y.I. Zou and K. Chakrabarty, “Redundancy Analysis and A Distributed Self-organization Protocol for Fault-tolerant Wireless Sensor Networks,” International Journal of Distributed Sensor Networks, vol. 3, no. 3, pp. 243-272, 2007.