PREFACE page XI
1 INTRODUCTION page 1
1.1 Wireless Sensor Networks 1
1.2 Time Synchronization 2
1.3 Importance of Time Synchronization 3
1.4 History of Clock Synchronization 4
1.5 Outline 6
2 SIGNAL MODELS FOR TIME SYNCHRONIZATION page lO
2.1 Definition of Clock lo
2.2 Design Considerations 11
2.3 Delay Components in Timing Message Delivery 13
3 TIME SYNCHRONIZATION PROTOCOLS page 15
3.1 Pairwise Synchronization - 16
3.1.1 Timing-Sync Protocol for Sensor Networks （TPSN） 16
3.1.2 Tiny-Sync and Mini-Sync 8
3.1.3 Reference Broadcast Synchronization （RBS） 19
3.1.4 Flooding Time Synchronization Protocol （FTSP） 21
3.2 Network-Wide Synchronization 21
3.2.1 Extension of TPSN 22
3.2.2 Lightweight Time Synchronization （LTS） 22
3.2.3 Extension of RBS 23
3.2.4 Extension of FTSP 23
3.2.5 Pairwise Broadcast Synchronization （PBS） 24
3.2.6 Time Diffusion Protocol （TDP） 24
3.2.7 Synchronous and Asynchronous Diffusion Algorithms 26
3.2.8 Protocols Based on Pulse Transmissions - 27
3.3 Adaptive Time Synchronization 28
3.3.1 Rate-Adaptive Time Synchronization （RATS） 28
3.3.2 RBS-based Adaptive Clock Synchronization 29
3.3.3 Adaptive Multi-Hop Time Synchronization （AMTS） 30
4 FUNDAMENTAL APPROACHES TO TIME SYNCHRONIZATION page 32
4.1 Sender-Receiver Synchronization （SRS） 33
4.2 Receiver-Only Synchronization （ROS） 36
4.3 Receiver-Receiver Synchronization （RRS） 39
4.4 COmparisons 41
5 MINIMUM VARIANCE UNBIASED ESTIMATION （MVUE）OF CLOCK OFFSET page 42
5.1 The System Architecture - 43
5.2 Best Linear Unbiased Estimation Using Order Statistics（BLUE-OS） 45
5.2.1 Symmetric Link Delays 47
5.2.2 Asymmetric Link Delays - 48
5.3 Minimum Variance Unbiased Estimation （MVUE） 51
5.3.1 Asymmetric Link Delays 5
5.3.2 Symmetric Link Delays 55
5.4 Explanatory Remarks 57
6 CLOCK OFFSET AND SKEW ESTIMATION page 62
6.1 Gaussian Delay Model 63
6.1.1 Maximum Likelihood （ML） Clock Offset Estimation - 63
6.1.2 Cramer-Rao Lower Bound （CRLB） for Clock Offset 64
6.1.3 Joint Maximum Likelihood Estimation （JMLE） of Clock Offset and Skew 64
6.1.4 Cramer-Rao Lower Bound （CRLB） for Clock Offset and Skew 67
6.2 Exponential Delay Model. 69
6.2.1 Cramer-Rao Lower Bound （CRLB） for Clock Offset - 70
6.2.2 Joint Maximum Likelihood Estimation （JMLE） of Clock Offsetand Skew 73
7 COMPUTATIONALLY SIMPLIFIED ScHEMEs FOR ESTIMATION OF CLOCK OFFSET AND SKEW page 90
7.1 Using the First and the Last Data Sample 91
7.1.1 Gaussian Delay Model 91
7.1.2 Exponential Delay Model 92
7.1.3 Combination of Clock Offset and Skew Estimation 95
7.1.4 Simulation Results 96
7.2 Fitting the Line Between Two Points at Minimum Distance Apart 99
7.2.I Simulation Results lol
7.2.2 Computational Complexity Comparison lo2
8 PAIRWISE BROADCAST SYNCHRONIZATION （PBS） - page lo4
8.1 Synchronization for Single-Cluster Networks lo5
8.2 Comparisons and Analysis lo5
8.3 Synchronization for Multi-Cluster Networks - lo7
8.3.1 Network-Wide Pair Selection Algorithm （NPA） lO8
8.3.2 Group-Wise Pair Selection Algorithm （GPA） - 1io
8.4 Comparisons and Analysis 114
9 ENERGY-EFFICIENT ESTIMATION OF CLOCK OFFSET FOR INACTIVE NODES page 118
9.1 Problem Formulation 119
9.2 Maximum Likelihood Estimation （MLE） 121
9.3 Cramer-Rao Lower Bound （CRLB） 132
9.3.1 CRLB for the Clock Offset of Inactive Node q 133
9.3.2 CRLB for the Clock Offset of Active Node t' 137
9.4 Simulation Results 138
10 SOME IMPROVED AND GENERALIZED ESTIMATION SCHEMES FOR CLOCK SYNCHRONIZATION OF INACTIVE NODES page 14o
10.1 Asymmetric Exponential Link Delays 141
10.1.1 Best Linear Unbiased Estimation Using Order Statistics （BLUE-OS） 142
10.1.2 Minimum Variance Unbiased Estimation （MVUE） 145
10.1.3 Minimum Mean Square Error （MMSE） Estimation 149
10.2 Symmetric Exponential Link Delays - 151
10.2.1 Best Linear Unbiased Estimation Using Order Statistics（BLUE-OS） 15I
10.2.2 Minimum Variance Unbiased Estimation （MVUE） 153
10.2.3 Minimum Mean Square Error （MMSE） Estimation 155
11 ADAPTIVE MULTI=HOP TIME SYNCHRONIZATION （AMTS） page I57
11.1 Main Ideas - 158
11.2 Level Discovery Phase 159
11.3 Synchronization Phase 159
11.4 Network Evaluation Phase 16o
11.4.1 Synchronization Mode Selection 16o
11.4.2 Determination of Synchronization Period 162
11.4.3 Determination of the Number of Beacons 164
11.4.4 Sequential Multi-Hop Synchronization Algorithm （SMA） 164
11.5 Simulation Results - 167
12 CLOCK DRIFT ESTIMATION FOR ACHIEVING LONG-TERM SYNCHRONIZATION - page 169
12.1 Problem Formulation 17o
12.2 The Estimation Procedure 271
13 JOINT SYNCHRONIZATION OF CLOCK OFFSET AND SKEW IN a RECEIVER-REcEIVER PROTOCOL page 177
13.1 Modeling Assumptions 177
13.2 Joint Maximum Likelihood Estimation （JMLE）of the Offset and Skew 178
13.3 Application of the Gibbs Sampler 179
13.4 Performance Bounds and Simulations 181
14 ROBUST ESTIMATION OF CLOCK OFFSET page 185
14.1 Problem Modeling and Objectives - 187
14.2 Gaussian Mixture Kalman Particle Filter （GMKPF） 189
14.3 Testing the Performance of GMKPF - 192
14.4 Composite Particle Filtering （CPF） with Bootstrap Sampling （BS） 196
14.5 Testing the Performance of CPF and CPF with BS 204
15 CONCLUSIONS AND FUTURE DIRECTIONS page 211
ACRONYMS page 214
REFERENCES page 218
INDEX page 227
