無線傳感器網絡時間同步概率誤差研究
2009-01-01 00:00:00田賢忠陳長軍胡同森
計算機應用研究 2009年6期
摘 要：研究WSNTS(無線傳感器網絡時間同步)誤差，旨在分析影響WSNTS誤差的因素，揭示WSNTS誤差的分布規律。在分析了傳統的NTP時間同步策略的基礎上建立了WSNTS誤差的數學模型，給出了單跳WSNTS誤差分布規律（正態分布），同時還給出了多跳WSNTS誤差的隨機過程模型及其均值和方差，并給出了多跳WSNTS誤差的上、下限曲線。仿真實驗證明這些結果是正確的。
關鍵詞：無線傳感器網絡；時間同步；誤差分析；隨機過程
中圖分類號：TP309文獻標志碼：A
文章編號：1001-3695(2009)06-2199-03
doi:10.3969/j.issn.1001-3695.2009.06.060
Research of probability errors on wireless sensor networks time synchronization
TIAN Xian-zhong， CHEN Chang-jun，HU Tong-sen
(College of Information Engineering， Zhejiang University of Technology， Hangzhou 310032， China)
Abstract:The purpose of this paper on the errors on WSNTS was to analyze influencing factors of WSNTS（WSN time synchronization） errors， and revealed its distributing rules.Analysed time synchronization method of traditional NTP and built a mathematical model of WSN errors.Also presented the distributing rules of one-hop WSNTS errors(normal distributing)，gave the random-process model of muti-hop WSNTS errors and its mean and standard deviation. At last，presented top-bottom curve of muti-hop WSNTS errors. This results are correct testified by emulational experiment.
Key words:wireless sensor networks（WSN）; time synchronization; error analysis; random process
無線傳感器網絡（WSN）是由傳感器、微處理器和無線通信接口組成的網絡。它已日益引起人們的研究興趣，成為國內外學者的研究熱點，同時也是當前IT領域最具挑戰性的方向之一[1，2]。時間同步是WSN的一項重要支撐技術。傳感器網絡自身協議的運行及基于其上的應用（如標記數據采集時間、時分多址接入、協同休眠、定位、數據融合等）都需要網絡中節點的時間保持同步。所以，時間同步已經成為傳感器網絡技術能否在各種領域有效應用的關鍵問題[3，4]。
WSN的時間同步(WSN time synchronization，WSNTS)主要是通過在一段時間內不斷重復地直接調整節點本地時鐘偏差以維持這段時間內的時間同步。然而，計算時間偏差是通過信息的交換為基礎。信息從產生到被正確接收的過程中存在著多種時延，這些時延的不確定性導致了接收信息的節點無法精確地比較與發送節點的本地時間偏差。因此任何同步協議都有一定的誤差，只是不同的時間同步協議減少誤差所用方法不同，提高精度也就不同罷了。
針對WSNTS誤差無法避免的事實，本文研究WSNTS誤差，旨在分析和揭示WSNTS誤差的產生原因和分布規律。本文在分析了傳統的NTP[5]時間同步策略的基礎上建立了WSNTS誤差的數學模型。目前專門針對WSNTS誤差的研究還很少，大都是針對某種協議的誤差分析[6~8]，用隨機過程的方法來研究WSNTS誤差目前也鮮有發現。
1 傳統的NTP時間同步策略
NTP最早由美國Delaware大學的Mills教授于1982年提出，其目的是在互聯網上傳遞統一、標準的時間。由于時間同步工作是通過網絡實現的，而網絡傳輸是需要時間的，這樣客戶機接收到服務器的時間信息并不是當前的準確時間，而是一段時間之前的時間信息，這一段時間就是網絡傳送所花費的時間。因此，要獲得準確的當前時間就必須考慮網絡延遲造成的影響。NTP是通過計算報文的來回程時間來實現時間同步。
NTP基本原理如圖1所示。客戶A通過與服務器B的時間請求與回復完成與服務器B的時鐘同步。其中各參數含義如下：T1為客戶A發送查詢時間請求（T1 以客戶A 系統時間為準)；T2為服務器B接收查詢時間請求（T2 以服務器B 系統時間為準）；T3為服務器B回復時間請求（T3以服務器B系統時間為準）；T4為客戶A接收回復時間請求（T4 以客戶A 系統時間為準）；U1為查詢時間請求在網上傳播所消耗的時間；U2為回復時間請求在網上傳播所消耗的時間。
現在已知T1、T2、T3 和T4，需要求得客戶方Ａ與服務器方Ｂ的時間差θ以調整客戶方Ａ的時間。有以下方程組：
T2=T1+U1+θT4=T3+U2-θ(1)
解式（1）得到
θ=[(T2-T1)-(T4-T3)+(U2-U1)]/2(2)
2 WSNTS單跳誤差分析
2.1 WSNTS的單跳誤差
從式（2）中可以看出，兩節點的時間差θ與T1、T2、T3、T4、U1、U2這六個量有關，但是六個量本身也存在誤差，導致時間同步算法也有誤差。在WSN中，這六個量的誤差是由傳感器節點數據包在傳輸過程中六種時延[7]產生的（圖2）。把初始化消息分組的節點稱為發送者，對這個消息作出回應的節點稱為接收者。
a）發送時間。在應用層上構造分組，并把分組傳遞到MAC層的時間。
b）訪問時間。在分組到達MAC層之后，分組等待網絡傳輸信道空閑的時間。
c）傳輸時間。在物理層傳輸分組的時間，其中還包括了對分組的編碼和把分組轉換成電磁波的時間。
d）傳播時間。分組以電磁波的方式從發送端到接收端的時間，這個時間依賴于節點之間的距離。
e）接收時間。接收端將分組按比特方式進行接收，并且把分組傳到MAC層的時間，其中還包括把接收到的電磁波轉換并譯碼成二進制數據的時間。接收時間和傳輸時間是有重疊的。
f）接收處理時間。把接收到的比特還原成發送者發送的分組，然后把分組傳送到應用層的時間。
本文假設T1、t1為傳感器節點A準備發送和已經發送查詢時間請求的兩個時刻（它們均以傳感器節點A的系統時間為準)；T2、t2為傳感器節點B剛接收到和處理完接收查詢時間請求的兩個時刻（它們均以傳感器節點B的系統時間為準）；T3、t3為傳感器節點B準備發送和已經發送查詢時間請求的兩個時刻（它們均以傳感器節點B的系統時間為準)；T4、t4為傳感器節點A剛接收到和處理完接收查詢時間請求的兩個時刻（它們均以傳感器節點A的系統時間為準）；U1為查詢時間請求在網上傳播所消耗的時間；U2為回復時間請求在網上傳播所消耗的時間；SA、SB分別表示節點A、B作為發送方時的發送方時延（發送時間+訪問時間+傳輸時間）；RA、RB分別表示節點A、B作為接收方時的接收方時延（接收時間+接收處理時間）；PA→B、PB→A分別表示節點A到B、節點B到A的傳播時間。
這樣有
T1=t1-SAT2=t2+RBT3=t3-SBT4=t4+RAU1=PA→BU2=PB→A(3)
把式（3）代入（2）得
θ={[(t2+RB)-(t1-SA)]-[(t4+RA)-(t3-SB)]+(PB→A-PA→B)}/2=[(t2-t1)-(t4-t3)]/2+[(SA-SB)-(RA-RB)+(PB→A-PA→B)]/2(4)
所以兩傳感器節點時間差的誤差為
Δθ=[(SA-SB)-(RA-RB)+(PB→A-PA→B)]/2(5)
從式（5）中可以看出，WSNTS單跳的誤差與發送方時延差、接收方時延差和傳播時延差有關。如果傳感器節點A與B的發送時延、接收時延相等，節點A到B的傳播時延與B到A的傳播時延相等，則時間同步誤差為零。其實在WSN中，節點的類型大都相同，所以兩節點的發送時延和接收時延可以認為相等，即SA-SB=0，RA-RB=0。而傳播時間由于無線傳感器網絡多跳的無線環境存在有非對稱鏈路，前向鏈路和反向鏈路往往具有不同的時延，兩傳感器節點時間差的誤差主要與數據包的傳播時延有關，這樣式（5）可以簡化為
Δθ=(PB→A-PA→B)/2(6)
2.2 WSNTS誤差的分布規律
根據實驗[9]知道傳感器節點間傳播時延符合正態分布，這里假設節點傳播時延PA→B和PB→A均服從正態分布N(μ，σ2)，其中μ和σ分別是均值和標準差。那么WSNTS誤差是否也符合正態分布呢？答案是肯定的。
定理 假設傳感器節點傳播時延PA→B和PB→A是兩個互相獨立的隨機變量，它們服從正態分布N(μ，σ2)，其中μ和σ分別是均值和標準差。那么WSNTS誤差服從正態分布N(0，（1/2σ)2)。
證明 由式（6）知，Δθ=(PB→A-PA→B)/2。為方便起見，把傳感器節點傳播時延PA→B和PB→A分別記做X、Y，Δθ記做Z。先證明Z=X-Y服從正態分布。
因為X、Y是兩個互相獨立的隨機變量，它們服從正態分布N（μ，σ2），即
fX(x)=1/（2πσ）e-(x-μ)2/2σ2，-∞＜x＜∞
fY(y)=1/（2πσ)e-(y-μ)2/2σ2，-∞＜y＜∞
由概率知識可知
fZ(z)=∫+∞-∞fX(x)fY(z+x)dx=1/（2πσ2）
∫+∞-∞e-(x-μ)2/（2σ2）×e-(z+x-μ)2/（2σ2）dx=1/（2πσ2）∫+∞-∞e[(x-u)2+(z+x-u)2]/（2σ2）dx=1/（2πσ2）∫+∞-∞e-z2/（4σ2）×
e(x-u+1/2z)2/（2σ2）dx=1/（2πσ2）e-z2/（4σ2）
∫+∞-∞e-(x-u+z/2)2/（2σ2）dx
令t=(x-u+z/2)/σ，則
fZ(z)=1/（2πσ2）e-z2/（4σ2）∫+∞-∞
σe-t2dt=1/（2πσ2）e-z2/（4σ2）σπ=1/（2πσ）e-z2/（4σ2）=1/[2π(2σ)]e-z2/[2(2σ)2]
即Z=X-Y服從正態分布N(0，2σ)2)。所以Δθ=(PB→A-PA→B)/2服從正態分布N(0，（1/2σ)2)。證畢。
由定理知，WSN單跳時間同步誤差服從正態分布，它的均值是0，方差為（1/2σ)2。
3 WSNTS的多跳誤差分析
從第2章的分析可以知道，WSN的每相鄰兩個節點之間單跳的同步誤差服從正態分布，但是對于多跳的情況，實際上它是一個非平穩的隨機過程。如圖3所示，第一跳的同步誤差為Δθ，第二跳的同步誤差為2Δθ，依次類推，第n跳的同步誤差為nΔθ。所以設多跳同步誤差為隨機過程{X(t)=tΔθ|t=1，2，…，n}。下面給出這一隨機過程的均值、方差和誤差的上下曲線。因為均值能反映WSNTS誤差的平均值，而方差能反映誤差偏離均值的震蕩幅度，上、下限曲線則反映了WSNTS誤差的變化范圍。
3.1 WSNTS誤差隨機過程的均值與方差
由定理可知，Δθ~N（0，（1/2σ）2），那么可以證明tΔθ~N(0，t/2σ)2)。所以第t跳同步誤差的均值為0，方差為(t/2σ)2，其中σ為傳感器節點傳播時延PA→B和PB→A的標準差。故同步誤差隨機過程X(t)的均值為
μX(t)=E[X(t))=0；t=1，2，…，n(7)
同步誤差隨機過程X(t)的方差為
σ2X（t）=E{[X(t)-μX(t)]2}=t/2σ)2；t=1，2，…，n(8)
3.2 WSNTS誤差隨機過程的上、下限曲線
因為X(t)的均值為0，可以設同步誤差隨機過程X(t)的變化范圍在(-Y(t)，Y(t)]，而p是隨機過程X(t)在[-Y(t)，Y(t)]的概率。由于每相鄰兩個節點之間的同步誤差服從正態分布X(t)~N(0，t/2σ) 2），有
P{-Y(t)＜X(t)≤Y(t)}=P{[-Y(t)-0]/t/2σ＜(X(t)-0)/t/2σ＜(Y(t)-0)/t/2σ}=Φ(Y(t)/t/2σ)-Φ(-Y(t)/t/2σ)=2Φ(Y(t)/t/2σ)-1=p
得Y(t)=t/2σΦ-1[(1+p)/2]
其中：Φ(x)=1/2π∫x-∞e-t2/2dt；Φ-1是Φ的逆函數。
所以同步誤差隨機過程的上、下限曲線為
XU(t)=+Y(t)=0+t/2σΦ-1[(1+p)/2]=t/2σΦ-1[(1+p)/2](9)
XL(t)=-Y(t)=0-t/2σΦ-1[(1+p)/2]=-t/2σΦ-1[(1+p)/2](10)
4 仿真實驗
隨機產生30個服從正態分布N(0，1/2σ)2)的隨機變量作為一跳WSNTS誤差隨機變量，這里設σ=0.001。在此基礎上產生30個二跳誤差，它們分別是以一跳誤差為均值，也以1/2σ為標準差的正態分布隨機變量。在二跳基礎上再產生30個三跳誤差，它們分別是以二跳誤差為均值，也以1/2σ為標準差的正態分布隨機變量。具體數值如表1所示。用MATLAB工具函數檢驗，二跳、三跳中的樣本均符合正態分布。
a）對一跳、二跳和三跳的這些樣本再求均值與標準差，與式（7）（8）計算的結果進行比較。表2中的均值1是用樣本計算的結果，均值2是用式（7）計算的結果；標準差1是用樣本計算的結果，標準差2是用式（8）計算的結果。用MATLAB工具函數檢驗，二跳、三跳中的樣本都符合均值為0、標準差為t/2σ的正態分布。
表2 WSNTS誤差的均值與標準差
跳數一跳二跳三跳
均值均值11.0527e-0047.4916e-004-0.001 5均值2000
標準差標準差10.006 60.007 80.010 4
標準差20.007 10.010.012 2
b）對一跳、二跳和三跳的這些樣本再求上、下限，與式（9）（10）計算的結果進行比較，式（9）（10）中的p=0.99。表3中的上限1是用樣本計算的結果，上限2是用式（9）計算的結果；下限1是用樣本計算的結果，下限2是用式（10）計算的結果。從表3可以看出，式（9）（10）計算的上、下限能完全包含樣本中的數據。
表3 WSNTS誤差的上、下限
跳數一跳二跳三跳
上限
上限10.012 00.013 60.020 7
上限20.019 80.028 10.034 4
下限
下限1-0.015 3-0.016 1-0.021 9
下限2-0.019 8-0.028 1-0.034 4
5 結束語
本文主要分析了影響WSNTS誤差的因素及其分布規律。首先在分析了傳統的NTP時間同步策略的基礎上分析了影響WSNTS誤差的因素，建立了數學模型；其次給出并證明了單跳WSNTS誤差分布規律，它是服從正態分布的；最后給出了多跳WSNTS誤差的隨機過程模型，計算出了其均值和方差，并給出多跳WSNTS誤差的上、下限曲線。仿真實驗證明這些結果是正確的。
參考文獻：
［1］AKYILDIZ I F，SU Wei-lian，SANKARASUBRAMANIAM Y，et al.Wireless sensor networks:a survey[J].Computer Networks，2002，38（4）：393-422.
[2]STANKOVIC J A，ABDELZAHER T F，LU Chen-yang，et al.Real-time communication and coordination in embedded sensor networks[J].Proceedings of the IEEE，2003，91(7):1002-1022.
[3]SU Wei-lian，AKYYILDIZ I F.Time-diffusion synchronization protocol for wireless sensor network[J].IEEE/ACM Trans on Networking，2005，13(2):384-397.
[4]董超，田暢，倪明放.Ad hoc網絡時鐘同步研究[J].通信學報，2006，27（9）：110-117.
[5]MILLS D L.Internet time synchronization: the network time protocol[J].IEEE Trans on Communication，1991，39(10):1482-1493.
[6]ELSON J，ESTRIN G L.Fine-grained network time synchronization using reference broadcasts[C]//Proc of the 5th Symposium on Ope-rating Systems Design and Implementation.2002:147-163.
[7]GANERIWAL S，KUMAR R，SRIVASTAVA M B.Timing- sync protocol for sensor network[C]//Proc of the 1st International Conference on Embedded Networked Sensor Systems.2003:138-149.
[8]SU Ping.Delay measurement time synchronization for wireless sensor networks，IR-TR-2003-64[R].[S.l.]:Intel Research Center，2003.
[9]楊博， 廖明宏.基于統計的無線傳感器網絡時鐘同步協議[J].哈爾濱工業大學學報，2007，39（1）:98-101.
