鄭顧平 馬粵

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

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

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

1 引言

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

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

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

2 DMTS算法原理

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

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

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

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

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

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

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

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

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

上層接收時(shí)延：上層接收處理的時(shí)延。

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

4 EDMTS算法

4.1 EDMTS算法原理

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

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

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

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

5 實(shí)驗(yàn)

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

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

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

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

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

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

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

6 結(jié)語(yǔ)

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

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

參考文獻(xiàn)：

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

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

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

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

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

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

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