鄭顧平 馬粵

摘 要：無線傳感網(wǎng)絡(luò)的時間同步算法中，DMTS算法簡單，能耗小，但其精度和穩(wěn)定性不好。在DMTS的基礎(chǔ)上，分析數(shù)據(jù)傳輸中時延構(gòu)成，采用高斯模型對時延建模，利用最大似然估計法得到時間偏差的無偏估計。提出EDMTS算法，使用CC2430進行物理實驗，實驗表明EDMTS相比DMTS具有更高的精度和穩(wěn)定性。

關(guān)鍵詞：無線傳感網(wǎng)絡(luò) 時間同步 高斯分布 延遲時間測量

中圖分類號：TN915.9 文獻標(biāo)識碼：A 文章編號：1007-3973（2013）009-125-03

1 引言

無線傳感網(wǎng)絡(luò)（WSN，Wireless Sensor Networks）是一種分布式的無線自組織網(wǎng)絡(luò)，時間同步對于無線傳感網(wǎng)絡(luò)的應(yīng)用具有極其重要的意義。如，信息傳輸調(diào)度需要時分多址 （Time division multiple access，TDMA）技術(shù)支撐；在功率管理中，傳感器網(wǎng)絡(luò)中的節(jié)點大部分時間處于休眠狀態(tài)，協(xié)同處理任務(wù)時需要同步激活，同步采樣等；定位、安全和跟蹤協(xié)議等需要節(jié)點在數(shù)據(jù)包中添加時間戳。

目前，無線傳感器網(wǎng)絡(luò)時間同步方法的研究，概括起來可以分為以下四類：（1）基于發(fā)送者的同步模型，典型算法有基于延遲測量的DMTS（Delay Measurement Time Synchronization，延遲測量時間同步）算法和基于泛洪的FTSP算法；（2）基于發(fā)送者、接受者交互的同步模型，典型的如NTP、TPSN算法；（3）基于接收者、接受者交互的同步模型，典型的是RBS算法和Adaptive RBS；（4）基于仿生結(jié)構(gòu)的算法，典型的如螢火蟲同步算法。

較之四類時間同步方法，DMTS算法簡單，能量效率高，它使用一個單向的數(shù)據(jù)包即可完成同步，但是它的同步精度較低，穩(wěn)定性不好，本文在DMTS算法基礎(chǔ)上引入高斯時延，利用最大似然估計得到時鐘偏差的估計。提出改進的EDMTS算法，實驗證明，本算法較DMTS算法具有更高的精度和更好的穩(wěn)定性，點對點誤差在1微秒至3微秒。雙跳網(wǎng)絡(luò)中，同步誤差在1微秒至4微秒之間。相較其它類同步算法，本算法具有同步信息量少的優(yōu)點。

2 DMTS算法原理

DMTS算法的原理為，發(fā)送節(jié)點在發(fā)送信道空閑時，在MAC層給廣播分組加上時間戳t0。發(fā)送正式數(shù)據(jù)分組前，發(fā)送節(jié)點先發(fā)送前導(dǎo)碼和起始字符，以便接收節(jié)點進行同步，根據(jù)發(fā)送的信息位個數(shù)n和發(fā)送每比特位所需要的時間n ，可以估計發(fā)送前導(dǎo)碼和起始字符的時間為n 。接收節(jié)點在數(shù)據(jù)分組接收完成時刻加上時間戳t1，在接收的數(shù)據(jù)分組經(jīng)過MAC層和應(yīng)用層處理后，獲得時間戳t2，這樣接收端的接收處理延遲就是t2-t1。若忽略無線信號的傳播延遲，接收節(jié)點從t0時刻計算的話，在調(diào)整自身時鐘前的處理延遲為n +（t2-t1）。因此接收節(jié)點為了與發(fā)送節(jié)點時鐘同步，就調(diào)整其時鐘為t0+n +（t2-t1）。

對于多跳網(wǎng)絡(luò)，需要進行分層并進行主節(jié)點選舉。假設(shè)網(wǎng)絡(luò)分為n層，分層結(jié)構(gòu)為（L0，L1，…，Ln），其中L0僅包含主節(jié)點。先同步L0至L1，再讓L1構(gòu)成L2的主節(jié)點，同步L1至L2，以此類推，直到Ln同步完成。

3 無線網(wǎng)絡(luò)時延分析

無線網(wǎng)絡(luò)中的時延可以分為幾個不同部分：

發(fā)送時延：應(yīng)用層建立信息的時間，能夠達到數(shù)百微秒量級。

接入時延：應(yīng)用層信息用于接入信道的等待時間，一般在微秒到秒之間變化。

傳輸時延：與信息長度和在介質(zhì)中無線電傳播速度相關(guān)，一般為幾十微秒的量級。

傳播時延：無線信道中從發(fā)送端到接收端的時間，一般少于1 s，可忽略不計。

物理層接收時延：接收端物理層接受信息的時間，一般和傳輸時延相同。

上層接收時延：上層接收處理的時延。

這些延時部分又可分為固定時延和可變時延。可變時延取決于各種網(wǎng)絡(luò)參數(shù)，人們已經(jīng)提出了多個隨機時延的概率密度函數(shù)，其中最廣泛應(yīng)用的是高斯、伽馬、指數(shù)和韋氏概率密度函數(shù)。一般認為時延和測量誤差由大量獨立隨機過程構(gòu)成，根據(jù)中心極限定理，總的時延和各種誤差之和適合選用高斯模型，延時的可變部分能以99.8%的可信度被建模為高斯分布隨機變量。實際無線網(wǎng)絡(luò)環(huán)境中存在許多干擾或碰撞，必定會有各種延遲。DMTS忽略這些時間延遲從而導(dǎo)致同步算法精度較低和不穩(wěn)定。為了提高精度和穩(wěn)定性，同時利用DMTS的簡單、能量效率高的優(yōu)勢，在DMTS中引入時間延遲參數(shù)，對其采用高斯模型建模，由此提出EDMTS算法。

4 EDMTS算法

4.1 EDMTS算法原理

加入時間延遲后的同步模型為：t1= t0+n + +X，其中，n 為前導(dǎo)碼和起始字符的發(fā)送時間， 為兩個時鐘節(jié)點之間的時鐘偏移，X為時間延遲，服從高斯分布。t0為主節(jié)點發(fā)送時刻，t1為從節(jié)點MAC層數(shù)據(jù)接受完成時刻。

假設(shè)主節(jié)點和從節(jié)點之間同步了N次，則第i次交換的時間關(guān)系如下：t1i= t0i+n + +Xi，其中，n 為前導(dǎo)碼和起始字符的發(fā)送時間， 為兩個節(jié)點之間的時鐘偏移，Xi為第i次同步時的隨機延遲，服從高斯分布。t0i為第i次同步時主節(jié)點發(fā)送時刻，t1i為第i次同步時從節(jié)點MAC層數(shù)據(jù)接受完成時刻。

（3）獲取本地時間t2，設(shè)置自身時鐘為t0N + y + （t2-t1N），其中，t0N和t1N是最后一個同步包內(nèi)t0和t1時刻的信息，補償（t2-t1N）是為了消除算法計算時間導(dǎo)致的誤差。

本算法的時間復(fù)雜度為 （n）。需要總數(shù)為N*M （M為t0和t1存儲長度）的存儲空間。假設(shè)采用64位二進制表示時間，則M為128位。無線傳感網(wǎng)絡(luò)節(jié)點能量有限，同步數(shù)據(jù)包不宜過多，實踐中N一般小于20。故需要的最大存儲空間為160字節(jié)，現(xiàn)代嵌入式系統(tǒng)完全能夠滿足這個空間需求。

5 實驗

首先，使用Matlab仿真分析同步次數(shù)N與誤差的關(guān)系。仿真采用一個主節(jié)點與50個從節(jié)點，仿真參數(shù)為 =13， =1， =5000（ s），n =50（ s）。統(tǒng)計各從節(jié)點時鐘偏移計算結(jié)果的誤差均值，結(jié)果如圖1所示，橫坐標(biāo)為同步次數(shù)N，縱坐標(biāo)為誤差的絕對值。試驗結(jié)果表明，同步次數(shù)增加使得誤差呈指數(shù)型減小。

然后仿真分析EDMTS與DMTS的準(zhǔn)確度關(guān)系，同樣采用上述參數(shù)，分別仿真DMTS、同步3個、5個、7個數(shù)據(jù)包的情況。仿真結(jié)果與圖1一致的，即隨著同步次數(shù)的增加，誤差快速減小?？梢钥闯?，DMTS誤差較大。加入時延參數(shù)進行統(tǒng)計分析后，精度快速提升。當(dāng)同步5個數(shù)據(jù)包時，誤差僅為DMTS算法的1/2。

在CC2430平臺上對本算法進行驗證。CC2430是德州儀器（TI）公司的無線傳感網(wǎng)絡(luò)產(chǎn)品，在工程應(yīng)用中非常廣泛，TI公司提供了完整的說明文檔和開發(fā)包，可以很方便地實現(xiàn)硬件級功能，如在數(shù)據(jù)包經(jīng)過MAC后添加時間戳。

采用兩個節(jié)點，每個節(jié)點采用STM32F103ZE主控芯片，CC2430為無線收發(fā)器。STM32F10系列芯片為ARM Cortex-M3架構(gòu)，主頻72MHz，具有很高的處理速度和中斷響應(yīng)速度。節(jié)點A作為主節(jié)點，連接GPS，接收高精度時間信號，在GPS的1PPS（秒脈沖）信號控制下，按照預(yù)定同步間隔發(fā)送同步信息。節(jié)點B為從節(jié)點，同樣連接GPS，用于同步測量兩個節(jié)點時間偏差，作為從節(jié)點計算結(jié)果的參考標(biāo)準(zhǔn)。兩個節(jié)點距離為室內(nèi)20米。分別對DMTS，使用5個同步數(shù)據(jù)包的EDMTS進行測試，各測試1000次。其詳細誤差分布如圖2所示。

實際測量結(jié)果略多于1000次，此處按順序選取1000組進行統(tǒng)計。通過圖2可以看到，EDMTS精度和穩(wěn)定性都優(yōu)于DMTS。DMTS的測量結(jié)果波動很大，大部分位于2～8微秒之間，平均誤差為5.3微秒。EDMTS大部分誤差位于0～2微秒，平均誤差1.2微秒。EDMTS精度的優(yōu)勢主要來自于在對多個測量值平均化，所以可以有效地排除誤差，但是相對增大了信息交換量，能量消耗大于DMTS。

測試多跳網(wǎng)絡(luò)中本算法的性能。采用3個節(jié)點，配置同前述實驗，共分為3層，節(jié)點A為主節(jié)點，處于L0層。節(jié)點B和節(jié)點C分別處于L1和L2層。首先同步節(jié)點A和節(jié)點B，然后同步節(jié)點B和節(jié)點C。統(tǒng)計節(jié)點C和節(jié)點A的誤差。詳細誤差分布如圖3所示。

DMTS兩跳平均誤差為6微秒，EDMTS平均誤差為1.5微秒，雙跳誤差并不大，理論上多跳網(wǎng)絡(luò)中誤差會隨著跳數(shù)的增加而線性增長，然而在實際網(wǎng)絡(luò)環(huán)境中，誤差會相互抵消。穩(wěn)定性方面，EDMTS仍然優(yōu)于DMTS，雙跳網(wǎng)絡(luò)中，DMTS誤差范圍集中在3～9微秒，而EDMTS誤差范圍集中在0～3微秒。

6 結(jié)語

本文針對DMTS算法精度不高，穩(wěn)定性不好的問題，分析了DMTS算法中忽略的時間延遲參數(shù)，對延遲采用高斯分布建模，利用最大似然估計法對時間偏差進行估計，提出EDMTS算法。

本算法在STM32F103+CC2430平臺下的性能為，點對點同步誤差平均為1.2微秒，多跳網(wǎng)絡(luò)中平均同步誤差為1.5微秒，同步誤差波動不大，穩(wěn)定性較好。EDMTS算法增加了同步包的數(shù)量，能量消耗量較DMTS更大，仍然保持了DMTS算法簡潔的特性。

參考文獻：

[1] 肖琳，程利娟，王福豹，等.一種低功耗無線傳感器網(wǎng)絡(luò)時間同步算法[J].計算機研究與發(fā)展，2008，45（1）：126-130.

[2] 張白樺.基于TPSN的時間同步改進算法[J].計算機工程，2010，36（9）：109.

[3] 沈明玉，艾治雄.無線傳感網(wǎng)絡(luò)低能耗時間同步的研究[J].計算機工程與應(yīng)用，2012，48（8）：112-115.

[4] 王瑜，張繼榮.無線傳感器網(wǎng)絡(luò)的時間同步[J].西安郵電學(xué)院學(xué)報，2010，15（1）：143-147.

[5] 荊琦，唐禮勇，陳洲峰，等.無線傳感器網(wǎng)絡(luò)應(yīng)用支撐技術(shù)研究[J].計算機科學(xué)，2008，35（3）：22-27.

[6] 劉翠蘋，張海濤，白舸.基于螢火蟲群優(yōu)化算法的無線傳感器節(jié)點部署[J].計算機應(yīng)用，2013，33（4）：905-907.

[7] 徐朝農(nóng)，徐勇軍，李曉維.無線傳感器網(wǎng)絡(luò)時間同步新技術(shù)[J].計算機研究與發(fā)展，2008，45（1）：138-145.