施吉昇臺灣大學：資訊工程學研究所李國良Li, Guo-LiangGuo-LiangLi2007-11-262018-07-052007-11-262018-07-052006http://ntur.lib.ntu.edu.tw//handle/246246/54024現今已有許多的感測網路佈建在環境中，在感測網路的應用裡，資料伺服器需要得知各感測器所傳回的資料流的相對關係，來得知某些發生在環境裡的資訊或事件；為了達到這些目的，我們必須能在可容忍的網路傳遞延遲下重建資料流的時間關係，或讓所有感測器遵守一個全域時間。然而網路中的感測器並不一定擁有計時器，一般應用在分散式系統下的同步協定也不一定適用，所以我們發展了一個重建資料流時態的方法，使得感測器不必遵守一個全域時間。我們提出的方法使用了感測器內部的計數器，加上外部的同步訊號以達成時態重建；我們使用了固定或變動頻率的同步訊號，使伺服器能辨別訊號所代表的不同資訊。由於同步訊號的傳遞只用到單向通訊，因此當應用在大規模感測網路時，可以較傳統方法大幅減少頻寬的浪費。最後，我們在本論文中分析了感測器的啟用及關閉時間與可容忍的傳遞時間延遲與可容忍的訊號遺失量。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 . . . . . . . . . . . . . . . . . . . . . . . . . . 57491681 bytesapplication/pdfen-US感測網路資料流同步sensor networkdata streamsynchronizationalignmentthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/54024/1/ntu-95-R93922065-1.pdf