臺灣博碩士論文加值系統

現今已有許多的感測網路佈建在環境中，在感測網路的應用裡，資料伺服器需要得知各感測器所傳回的資料流的相對關係，來得知某些發生在環境裡的資訊或事件；為了達到這些目的，我們必須能在可容忍的網路傳遞延遲下重建資料流的時間關係，或讓所有感測器遵守一個全域時間。然而網路中的感測器並不一定擁有計時器，一般應用在分散式系統下的同步協定也不一定適用，所以我們發展了一個重建資料流時態的方法，使得感測器不必遵守一個全域時間。我們提出的方法使用了感測器內部的計數器，加上外部的同步訊號以達成時態重建；我們使用了固定或變動頻率的同步訊號，使伺服器能辨別訊號所代表的不同資訊。由於同步訊號的傳遞只用到單向通訊，因此當應用在大規模感測網路時，可以較傳統方法大幅減少頻寬的浪費。最後，我們在本論文中分析了感測器的啟用及關閉時間與可容忍的傳遞時間延遲與可容忍的訊號遺失量。

Lots of sensor networks have been deployed in the field. In several sensor network applications, the data server may need to co-relate the data streams sampled by the sensors to discover certain information or event in the field, or locate the events of interests. To do so, it is required that the data streams are aligned with acceptable timing errors or the sensors agree on a global time. However, the sensors in the networks may not have any real-time clock or the computation capability to implement complex distributed clock synchronization protocols. We develop a data alignment mechanism for sensor networks. The mechanism allows the sensor data streams to be aligned without real-time clocks or virtual clocks. The developed mechanism makes use of the built-in counters on sensors and external (out-of-channel) synchronization signals to align data streams. The proposed approach uses constant or variable time intervals between synchronization signals to allow the data server to distinguish different synchronization signals. It greatly reduces clock synchronization overhead on sensor nodes. In addition, the developed mechanism is highly scalable because there are only one-way communication between sensors and servers. Our analysis also shows the required awake time for sensors to tolerate different clock drifts and signal lost.

List of Tables . . . . . . . . . . . . . . . .. . . . . vii
List of Figures . . . . . . . .. . . . . . . . . . . . viii
List of Algorithms . . . . . . . . . . . . . . . . . . . ix
Chapter 1 Introduction . . . . . . . . . . . . . . . . . 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . 1
1.2 Objectives and Contributions . . . . . . . . . . . . 4
1.3 Organization . . . . . . . . . . . . . . . . . . . . 5
Chapter 2 Background and FormalModel .. . . . . . . . . . 7
2.1 Background . .. . . . . . . . . . . . . . . . . . . . 7
2.1.1 Clock Synchronization for Distributed Systems . . . 7
2.1.2 Clock Synchronization for Sensor Networks . . . . . 9
2.2 Formal Model . . . . . . . . . . . . . . . . . . . . 10
Chapter 3 Clock Free Data Streams Alignment . . . . . . 17
Chapter 4 Constant Interval Synchronization Signals . . 22
4.1 Simple Constant Interval . . . . . . . . . . . . . . 23
4.1.1 Period Assignment for Known Maximum Transmission Delay . . . . . . . . . . . . . . . . . . . . . . . . . .23
4.1.2 Period Assignment for Known Maximum Clock Drift . 26
4.2 Constant Interval with Different Signals . . . . . . 29
Chapter 5 Variable Interval Synchronization Signals . . 34
5.1 Synchronization Signal Schedule Design . . . . . . . 35
5.1.1 Determining Synchronization Set and Identifier Length . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.1.2 Determining Synchronization Round . . . . . . . . .42
5.2 Data Stream Alignment . . . . . . . . . . . . . . . .43
5.3 Error Detection . . . . . . . . . . . . . . . . . . .44
5.4 Error Recovery . . . . . . . . . . . . . . . . . . . 45
Chapter 6 Summary . . . . . . . . . . . . . . . . . . . .54
References . . . . . . . . . . . . . . . . . . . . . . . 55
Vita . . . . . . . . . . . . . . . . . . . . . . . . . . 57

[1] L. Lamport, “Time, clocks, and the ordering of events in a distributed system,” Communications of the ACM, vol. 21, no. 7, pp. 558 – 565, 1978.
[2] A. Cerpa, J. Elson, D. Estrin, L. Girod, M. Hamilton, and J. Zhao, “Habitat monitoring: Application driver for wireless communications technology,” in Proceedings of the 2001 ACMSIGCOMMWorkshop onData Communications in Latin America and the Caribbean, April 2001.
[3] R. Orr and G. Abowd, “The smart floor: A mechanism for natural user identification and tracking,” in Conference on Human Factors in Computing Systems, The
Hague, (The Hague, Netherlands), April 2000.
[4] Q. Wang, R. Zheng, A. Tirumala, X. Liu, and L. Sha, “Lightning: A fast and lightweight acoustic localization protocol using low-end wirelessmicro-sensors,” in The 25th IEEE International Real-Time Systems Symposium (RTSS’04), pp. 371 – 381, 2004.
[5] K. S. J. Pister, J. M. Kahn, and B. E. Boser, “Smart dust: Wireless networks of millimeter-scale sensor nodes,” in Highlight Article in 1999 Electronics Research Laboratory Research Summary, 1999.
[6] N. Kurata, B. F. Spencer, Jr., and M. Ruiz-Sandoval, “Application of wireless sensor network mote for building risk monitoring.”
[7] N. Ukita and T. Matsuyama, “Real-time multi-target tracking by cooperative distributed active vision agents,” in AAMAS, (Bologan, Italy), pp. 829 – 838, July
2002.
[8] D. L. Mills, “Precision synchronization of computer network clocks,” ACM/IEEE Transactions on Networking, vol. 6, no. 5, pp. 505 – 514, 1998.
[9] C. Liao, M. Martonosi, and D. W. Clark, “Experience with an adaptive globallysynchronizing clock algorithm,” in ACM SPAA, pp. 106–114, June 1999.
[10] F. Cristian, “Probabilistic clock synchronization,” Distributed Computing, vol. 3, no. 146 – 158, 1989.
[11] A. Ramanathan, K. G. Shin, and R. W. Butler, “Fault-tolerant clock synchronization in distributed systems,” IEEE Computer, pp. 33 – 42, October 1990.
[12] F. Mattern, “Virtual time and global states of distributed systems,” in Porceedings of the International Workshop on Parallel and Distributed Algorithms, 1988.
[13] D. L. Mills., “Internet time synchronization: The network time protocol.,” in Global States and Time in Distributed Systems., 1994.
[14] J. Y. Halpern and I. Suzuki, “Clock synchronization and the power of broadcasting,” in Distributed Computing, 1991.
[15] K. Romer, “Time synchronization in ad hoc networks,” in ACM MobiHoc, October 2001.
[16] J. Elson and K. Romer, “Wireless sensor networks: A new regime for time synchronization,” in In Proceedings of First Workshop on Hot Topics In Networks (HotNets-I), (Princeton, New Jersey), 2002.
[17] J. Elson, L. Girod, and D. Estrin, “Fine-grained network time synchronization using reference broadcasts,” in ACM OSDI, (Boston, MA), December 2002.
[18] J. V. Greunen and J. Rabaey, “Lightweight time synchronization for sensor network,” in nternationalWorkshop onWireless Sensor Networks and Applications, 2003.
[19] H. Dai and R. Han, “Tsync: A lightweight bidirectional time synchronization service for wireless sensor networks,” in ACM SIGMOBILE Mobile Computing and
Communications Review, 2004.
[20] J. Elson and E. Estrin, “Time synchronization for wireless sensor network,” in International Parallel and Distributed Processing Symposium,Workshop on Parallel and
Distributed Computing Issues in Wireless Networks and Mobile Computing, 2001.
[21] Q. Li and D. Rus, “Global clock synchronization in sensor network,” in INFOCOM, 2004.
[22] A. Rowe, R.Mangharam, and R. Rajkumar, “RT-Link: A Time-Synchronized Link Protocol for Energy Constrained Multi-hop Wireless Networks,” tech. rep., Department
of Electrical and Computer Engineering, Carnegie Mellon University, August 2005.
[23] P. Richardson, L. Seih, and P. Haniak, “A real-time control network protocol for embedded systems using controller area network(CAN),” in IEEE Elestronics and
Information Technology Conference, June 2001.
[24] H. Mori, Y. Mano, H. Takada, and K. Sakamura., “μITRON bus: a real-time control lan for open network environment.,” pp. 227–234, 1996.