臺灣博碩士論文加值系統

在無線感測器網路中，以往所提出的容錯時間同步協定只能夠容忍有限的錯誤節點。當錯誤節點的數目隨著時間而增多，不正確的時間資訊會使得同步整個網路變得更加困難。這篇論文提出了一種診斷錯誤的時間同步機制，其能夠偵測並且排除潛在的錯誤節點。錯誤診斷機制避免了錯誤節點的影響進而讓時間同步協定達到更好的效能。實驗結果顯示診斷錯誤的時間同步協定比起容錯時間同步協定，能夠較長時間的同步整個網路。

Previous fault-tolerant time synchronization protocols are vulnerable to the number of misbehaved nodes in a sensor network. With the increasing number of faulty sensor nodes, more erroneous data are exchanged, so it becomes more difficult to synchronize time accurately for all working nodes. This thesis develops a fault diagnosis mechanism for time synchronization, called Partitioned Sample Time Diagnosis (PSTD), that can locate potential misbehaved sensor nodes and then exclude them from future rounds of synchronization. Due to the diagnosis capability, PSTD avoids interference of the identified faulty nodes and thus achieves better performance. The simulation results reveal that PSTD improves the operational period compared to the previous protocols.

1 Introduction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1
2 Related Work : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3
2.1 Time Synchronization in Sensor Networks . . . . . . . . . . . . . . . . . 3
2.2 Fault-Tolerant Time Synchronization in Sensor Networks . . . . . . . . . 4
3 System Model : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6
4 Partitioned Sample Time Diagnosis : : : : : : : : : : : : : : : : : : : : : 8
4.1 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.2 Extension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5 Analysis : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 13
5.1 Determining the value of phi . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.2 Determining the value of x . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6 Evaluation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 16
7 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 28
References : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 29
Vita : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 31

[1] J. Elson and K. Romer, “Wireless Sensor Networks: A New Regime for Time Synchronization,” ACM SIGCOMM Computer Communication Review, vol. 33, no. 1, pp. 149–154, Jan. 2003.
[2] J. Elson, L. Girod, and D. Estrin, “Fine-Grained Network Time Synchronization using Reference Broadcasts,” ACM SIGOPS Operating Systems Review, vol. 36, no. SI, pp. 147–163, Dec. 2002.
[3] S. Ganeriwal, R. Kumar, and M. B. Srivastava, “Timing-sync Protocol for Sensor Networks,” in Proceedings of International Conference on Embedded Networked Sensor Systems, Nov. 2003, pp. 138–149.
[4] M. Mar’oti, B. Kusy, G. Simon, and ’A. L’edeczi, “The Flooding Time Synchronization Protocol,” in Proceedings of International Conference on Embedded Networked Sensor Systems, Nov. 2004, pp. 39–49.
[5] M. L. Sichitiu and C. Veerarittiphan, “Simple, Accurate Time Synchronization for Wireless Sensor Networks,” in Proceedings of IEEE Wireless Communications and Networking Conference, Mar. 2003, pp. 1266–1273.
[6] W. Su and I. F. Akyildiz, “Time-Diffusion Synchronization Protocol for Wireless Sensor Networks,” IEEE Transactions on Networking, vol. 13, no. 2, pp. 384–397, Apr. 2005.
[7] Q. Li and D. Rus, “Global Clock Synchronization in Sensor Networks,” IEEE Transactions on Comupters, vol. 55, no. 2, pp. 214–226, Feb. 2006.
[8] G. Werner-Allen, G. Tewari, A. Patel, M. Welsh, and R. Nagpal, “Firefly-Inspired Sensor Network Synchronicity with Realistic Radio Effects,” in Proceedings of International Conference on Embedded Networked Sensor Systems, Nov. 2005, pp. 142–153.
[9] M. Manzo, T. Roosta, and S. Sastry, “Time Synchronization Attacks in Sensor Networks,” in Proceedings of ACM workshop on Security of Ad Hoc and Sensor Networks, Nov. 2005, pp. 107–116.
[10] K. Sun, P. Ning, and C. Wang, “Fault-Tolerant Cluster-Wise Clock Synchronization for Wireless Sensor Networks,” IEEE Transations on Dependable and Secure Computing, vol. 2, no. 3, pp. 177–189, July–Sept. 2005.
[11] H. Song, S. Zhu, and G. Cao, “Attack-Resilient Time Synchronization for Wireless Sensor Networks,” in IEEE International Conference on Mobile Ad-hoc and Sesnor Systems, Nov. 2005, pp. 765–772.
[12] S. Ganeriwal, S. Capkun, C.-C. Han, and M. B. Srivastava, “Secure Time Synchronization Service for Sensor Networks,” in Proceedings of ACM workshop on Wireless Security, Sept. 2005, pp. 97–106.
[13] K. Sun, P. Ning, and C. Wang, “Secure and Resilient Clock Synchronization in Wireless Sensor Networks,” IEEE Journal on Selected Areas in Communications, vol. 24, no. 2, pp. 395–408, Feb. 2006.
[14] K. Sun, P. Ning, C. Wang, A. Liu, and Y. Zhou, “TinySeRSync: Secure and Resilient Time Synchronization in Wireless Sensor Networks,” in Proceedings of ACM Conference on Computer and Communications Security, Oct.–Nov. 2006, pp. 264–277.
[15] B. Rosner, “Percentage Points for Generalized ESD Many-Outlier Procedure,” Technometrics, vol. 25, no. 2, pp. 165–172, May 1983.
[16] A. Perrig, J. D. Tygar, D. Song, and R. Canetti, “Efficient Authentication and Signing of Multicast Streams over Lossy Channels,” in Proceedings of IEEE Symposium on Security and Privacy, May 2000, pp. 56–73.
[17] A. Perrig, R. Szewczyk, J. D. Tygar, V. Wen, and D. E. Culler, “SPINS: Security Protocols for Sensor Networks,” in Proceedings of International Conference on Mobile Computing and Networks, July 2001, pp. 521–534.
[18] M. Abramson and W. O. J. Moser, “More Birthday Surprises,” in American Mathematical Monthly, Oct. 1970, vol. 77, pp. 856–858.
[19] The Network Simulator—ns-2. [Online]. Available: http://www.isi.edu/nsnam/ns/