簡易檢索 / 詳目顯示

回結果列表
研究生： 胡偉德
Hu, Wei-Te
論文名稱： 在無線感測網路上偵測及診斷故障非靜止之錯誤
Detection and Diagnosis for Non-silent Faults in Wireless Sensor Networks
指導教授： 斯國峰
Ssu, Kuo-Feng
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 電機工程學系
Department of Electrical Engineering
論文出版年： 2004
畢業學年度： 92
語文別： 英文
論文頁數： 38
中文關鍵詞： 繞路協定 、多重路徑 、無線感測網路 、錯誤診斷 、容錯
外文關鍵詞： routing, fault tolerance, wireless sensor networks, fault diagnosis
相關次數： 點閱：105  下載：1 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 　　許多在無線感測器網路上提出的容錯機制均專注於處理能量故障(power failures) 或停機故障 (crash failures)，僅少數考慮故障非靜止的錯誤 (non-silent failures)。一旦此類錯誤發生，感測器會不斷地產生不正確結果，並且將這些錯誤的資訊傳送給其他的感測器，進而影響整個網路系統，使蒐集器 (sink nodes) 做出不正確的判斷。本篇論文描述一種繞送機制並能偵測無線感測器網路上之故障非靜止的錯誤。這個機制以建立節點不相交的路徑及使用投票方法來找出故障的感測器。這個機制成功地實作在NS2 網路模擬器(NS2 simulator)，實驗結果顯示這個機制僅需些許的負擔便可以有效地檢測故障的感測元件。此外，蒐集器可辨認99.99% 的錯誤資料。

    　　Most　fault-tolerant schemes proposed for wireless sensor networks are concentrated on power failures or crash faults. Little attention has been devoted to non-silent failures. A non-silent faulty sensor produces incorrect results and transmits them to other sensors so the errors are propagated to the whole network. The sink may make wrong decisions due to the erroneous data received. This thesis describes a routing mechanism that can tolerate and locate non-silent failures in the sensor networks. The mechanism uses node disjoint paths and voting to detect faults. Failed nodes are identified based on a set/clear technique. The mechanism was successfully implemented with the NS2 simulator. The experimental results show that the mechanism can discover faulty nodes effciently and only incur little overhead. Moreover, the sink avoided receiving more than 99.99% erroneous data.

    Table of Contents Chapter 1 Introduction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1 2 Related Work : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4 2.1 Fault-Tolerance for Wireless Sensor Networks . . . . . . . . . . . . . . 4 2.2 Voting Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3 Reliable Routing Schemes in Wireless Sensor Networks . . . . . . . . . . 6 2.4 System Diagnosis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3 System Model : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 8 3.1 Protocol Architecture . . . . . . . . . . . .. . . . . . . . . . . . . . 8 3.2 System Model and Assumptions . . . . . . . . . . . . . . . . . . . . . . 8 3.3 Fault Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4 Fault Detection and Diagnosis : : : : : : : : : : : : : : : : : : : : : : 12 4.1 Construction for Node-Disjoint Paths . . . . . . . . . . . . . . . . . 12 4.1.1 Neighbor discovery . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.1.2 Node disjoint path strategy . . . . . . . . . . . . . . . . . . . . . 14 4.2 Diagnosis Protocol . . . . . . . . . . . . .. . . . . . . . . . . . . . 15 4.2.1 Voting policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.2.2 Diagnosis strategy . . . . . . . . . . . .. . . . . . . . . . . . . . 19 5 Performance Evaluations : : : : : : : : : : : : : : : : : : : : : : : : : 25 5.1 Simulation Environment . . . . . . . . . . .. . . . . . . . . . . . . . 25 5.2 Fault Injection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5.3 Simulation Results . . . . . . . . . . . . .. . . . . . . . . . . . . . 27 5.3.1 Failures occur during execution . . . . . . . . . . . . . . . . . . . 28 5.3.2 All failures occur at the beginning . . . . . . . . . . . . . . . . . 31 6 Conclusion and Future Work : : : : : : : : : :: : : : : : : : : : : : : : 34 6.1 Conclusion . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 34 6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 References : : : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : 36 Vita : : : : : : : : : : : : : : : : : : : : : :: : : : : : : : : : : : : : 38

    [1] S. Chessa and P. Santi, "Crash Faults Identifcation in Wireless Sensor Networks," Computer Communications, vol. 25, no. 14, pp. 1273-1282, Aug. 2002.

    [2] S. Chessa and P. Santi, "Comparison-Based System-Level Fault Diagnosis in Ad Hoc Networks," Proceedings of 20th IEEE Symposium on Reliable Distributed Systems, pp. 257-266, Oct. 2001.

    [3] D. Ganesan, R. Govindan, S. shenker, and D. Estrin, "Highly-Resilient, Energy-Effcient Multipath Routing in Wireless Sensor Networks," ACM SIGMOBILE Mobile Computing and Communications Review, vol. 1, no. 2, pp. 11-25, Oct. 2001.

    [4] A. S. Tanenbaum, Computer Networks, 3rd Edtion. Prentice-Hall, 1996.

    [5] D. P. Siewiorek and R. S. Swartz, Reliable Computer System: Design and Evaluation,2rd Edtion. Digital Press, 1992.

    [6] J. Seguin, G. Sergeant, and P. Wilms, "A Majority Consensus Algorithm for the
    Consistency of Duplicated and Distributed Information," Proceedings of the 1st International Conference on Distributed Computing Systems, pp. 617-624, Nov. 1979.

    [7] S. S. Iyengar, D. N. Jayasimha, and D. Nadig, "A Versatile Architecture for the Distributed Sensor Integration Problem," IEEE Transactions on Computers, vol. 43, pp. 175-185, Feb. 1994.

    [8] L. Prasad, S. S. Iyengar, R. L. Kashyap, and R. N. Madan, "Functional Char-
    acterization of Fault Tolerant Integration in Distributed Sensor Networks," IEEE
    Transactions on Systems, Man, and Cybernetics, vol. 21, pp. 1082-1087, Sept./Oct.
    1991.

    [9] K. Chakrabarty, S. S. Iyengar, H. Qi, and E. C. Cho, "Grid Coverage of Surveillance and Target Location in Distributed Sensor Networks," IEEE Transactions on Computers, vol. 51, pp. 1448-1453, Dec. 2002.

    [10] D. N. Jayasimha, "Fault Tolerance in Multi-Sensor Networks," IEEE Transactions on Reliability, vol. 45, pp. 308-315, June 1996.

    [11] I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "A Survey on Sensor Networks," IEEE Communication Magazine, vol. 40, no. 8, pp. 102-114, Aug. 2002.

    [12] D. K. Gifford, "Weighted Voting for Replicated Data," Proceedings of the seventh ACM symposium on Operating systems principles, pp. 150-161, Nov. 1979.

    [13] K. Ishida, Y. Kakuda, and T. Kikuno, "A Routing Protocol for Finding Two Node-Disjoint Paths in Computer Networks," In International Conference on Network
    Protocols, pp. 340-347, Nov. 1992.

    [14] C. Intanagonwiwatand, R. Govindan, D. Estrin, J. Heidemann, and F. Silva, "Directed Diffusion for Wireless Sensor Networking," IEEE/ACM Transactions on Networking, vol. 11, pp. 2-16, Feb. 2003.

    [15] E. P. D. Jr. and T. Nanya, "A Hierarchical Adaptive Distributed System-Level
    Diagnosis Algorithm," IEEE Transactions on Computers, vol. 47, pp. 34-45, Jan.
    1998.

    [16] P. Maestrini and P. Santi, "Self Diagnosis of Processor Arrays Using a Comparison Model," Proceedings of 14th IEEE Symposium on Reliable Distributed Systems,pp. 218-228, Sept. 1995.

    [17] S. Rangarajan, A. Dahbura, and E. Ziegler, "A Distributed System-Level Diagnosis Algorithm for Arbitrary Network Topologies," IEEE Transactions on Computers,vol. 44, pp. 312-334, Feb. 1995.

    [18] R. Bianchini and R. Buskens, "Implementation of On-Line Distributed System-Level Diagnosis Theory," IEEE Transactions on Computers, vol. 41, pp. 616-626, May 1992.

    [19] D. Blough and H. Brown, "The Broadcast Comparison Model for On-Line Fault
    Diagnosis in Multicomputer Systems: Theory and Implementation," IEEE Transac-
    tions on Computers, vol. 48, pp. 470-493, May 1999.

    [20] W. Hurwood, "Ongoing Fault Diagnosis," Proceedings of 15th IEEE Symposium on
    Reliable Distributed Systems, pp. 108-117, Oct. 1996.

    [21] T. Clouqueur, K. K. Saluja, and P. Ramanathan, "Fault Tolerance in Collaborative Sensor Networks for Target Detection," IEEE Transactions on Computers, vol. 53, no. 3, pp. 320-333, Mar. 2004.

    [22] B. krishnamachari and S. lyengar, "Distributed Bayesian Algorithms for Fault-Tolerant Event Region Detection in Wireless Sensor Networks," IEEE Transactions on Computers, vol. 53, no. 3, pp. 241-249, Mar. 2004.

    [23] M. del Rey, "Internet Protocol," RFC 791, Sept. 1981.

    [24] B. Sklar, "A Primer on Turbo Code Concepts," IEEE Communication Magazine,
    pp. 94-102, Dec. 1997.

    [25] The Network Simulator - ns-2. URL http://www.isi.edu/nsnam/ns/.

    下載圖示 校內：2005-07-20公開
    校外：2005-07-20公開
    QR CODE