喻歆

(中國西南電子技術(shù)研究所，成都 610036)

1 引言

隨著微機(jī)電系統(tǒng)和無線通信技術(shù)的不斷發(fā)展，無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)在人體、動(dòng)植物和環(huán)境監(jiān)控，生化威脅探測，國土安全，以及諸多軍事應(yīng)用領(lǐng)域已經(jīng)開始發(fā)揮出重要的功用［1－2］。網(wǎng)絡(luò)時(shí)間同步指的是將網(wǎng)絡(luò)中的所有時(shí)鐘校正到同一個(gè)時(shí)間標(biāo)準(zhǔn)的過程，其對(duì)WSNs諸多操作和功能的正常運(yùn)轉(zhuǎn)起到了至關(guān)重要的作用［2］。

全球?qū)Ш叫l(wèi)星系統(tǒng)(Global Navigation Satellite Systems，GNSS)能夠很容易地解決時(shí)間同步問題，并且獲得較高的精度［3］。但該方法對(duì)每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的硬件配置提出了額外要求，增加了成本，并且滿足硬件配置要求的節(jié)點(diǎn)也無法與缺少相關(guān)硬件配置的網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行時(shí)間同步。此外，即使所有網(wǎng)絡(luò)節(jié)點(diǎn)都具備了通過GNSS進(jìn)行時(shí)間同步的硬件配置，受通信系統(tǒng)所處環(huán)境(如室內(nèi)、地下、森林等)影響，GNSS也無法總是提供可靠的網(wǎng)絡(luò)時(shí)鐘參考。因此，必須設(shè)計(jì)額外的網(wǎng)絡(luò)時(shí)間同步機(jī)制。

過去十多年間，學(xué)者們提出了許多有效的時(shí)間同步算法［4－10］，這些算法大致可以分為中心式和分布式兩類。中心式方法中，網(wǎng)絡(luò)中存在一個(gè)參考時(shí)鐘或稱為主時(shí)鐘，網(wǎng)絡(luò)中的其他時(shí)鐘都以主時(shí)鐘為基準(zhǔn)進(jìn)行校正，而分布式方法則不需要參考時(shí)鐘。較為流行的中心式方法包括TPSN(Time－synchronization Protocol for Sensor Networks)［6］、FTSP(Flooding Time Synchronization Protocol)［7］和 RBS(Reference Broadcast Synchronization)［8］。TPSN 和 FTSP中，當(dāng)節(jié)點(diǎn)失效或者在移動(dòng)環(huán)境中，選擇新的根節(jié)點(diǎn)需要額外的通信開銷。此外，葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的距離會(huì)直接影響其同步精度。RBS中，主節(jié)點(diǎn)的選擇和網(wǎng)絡(luò)分簇的過程中都會(huì)引入較大的通信開銷。分布式時(shí)間同步方法沒有主時(shí)鐘節(jié)點(diǎn)，因此不受單點(diǎn)失效的影響，具有較強(qiáng)的健壯性。同時(shí)，沒有對(duì)主時(shí)鐘節(jié)點(diǎn)的選擇、管理和維護(hù)也使得這類時(shí)間同步方法具備較小的開銷。

近年來，一種基于時(shí)鐘采樣的網(wǎng)絡(luò)時(shí)間互同步(Clock－Sampling Mutual Network Synchronization，CS－MNS)［9］算法因其簡單有效的特性備受關(guān)注，并且已經(jīng)被用于實(shí)際系統(tǒng)當(dāng)中［10］。CS－MNS算法中，每個(gè)節(jié)點(diǎn)與其1跳鄰居周期交互同步消息，并基于該信息修正調(diào)整時(shí)鐘偏移和時(shí)鐘頻率偏移的校正因子。CS－MNS算法具有諸多優(yōu)點(diǎn)，例如無需直接訪問物理時(shí)鐘，無需主時(shí)鐘，實(shí)現(xiàn)簡單，同步精度較高等［9］。然而，CS－MNS并沒有考慮各種時(shí)延對(duì)其性能的影響，這可能導(dǎo)致其在某些場景尤其是在具有較大地理覆蓋范圍的網(wǎng)絡(luò)中性能不能滿足要求。因此，本文首先簡單介紹CS－MNS算法并分析其性能，然后對(duì)其進(jìn)行改進(jìn)，以期提高該算法在覆蓋更大地理范圍和處于更復(fù)雜環(huán)境中的Ad Hoc網(wǎng)絡(luò)中的性能。

2 CS－MNS算法簡介及分析

2.1 時(shí)鐘定義及問題描述

一個(gè)包含N個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)的時(shí)鐘都有不同的時(shí)鐘頻率偏移和初始時(shí)間，即第i個(gè)節(jié)點(diǎn)時(shí)鐘的時(shí)間過程Ti(t)表示為

式中，t為真實(shí)時(shí)間，βi表示第i個(gè)時(shí)鐘相對(duì)于真實(shí)時(shí)間的時(shí)鐘頻率偏移，Ti(0)為第 i個(gè)時(shí)鐘的初始時(shí)間。

時(shí)間同步算法的目標(biāo)是使網(wǎng)絡(luò)中的所有時(shí)鐘的時(shí)間過程滿足:對(duì)于任意的i≠j，都有

其中，tc表示算法的收斂時(shí)間，ΔT表示容忍的同步誤差。

2.2 CS－MNS 算法簡介

CS－MNS對(duì)虛擬時(shí)鐘進(jìn)行同步，虛擬時(shí)戳由真實(shí)時(shí)戳乘上校正因子獲得;CS－MNS根據(jù)收到的虛擬時(shí)戳消息對(duì)校正因子進(jìn)行修正，從而達(dá)到同步虛擬時(shí)鐘的目的［9］。虛擬時(shí)戳和校正因子的修正表達(dá)式分別為

式中，τ為采樣周期，常數(shù)kp稱為控制增益為第i個(gè)節(jié)點(diǎn)收到的發(fā)送時(shí)鐘發(fā)送的時(shí)戳消息。

從公式(3)可以看出，每個(gè)節(jié)點(diǎn)發(fā)送時(shí)戳消息時(shí)只需包含發(fā)送該消息時(shí)本地的虛擬時(shí)戳;一個(gè)節(jié)點(diǎn)一旦接收到一條有效的時(shí)戳消息，就能立即獨(dú)立地對(duì)時(shí)鐘偏移和時(shí)鐘頻率偏移進(jìn)行校正。

需要注意的是，CS－MNS不能為網(wǎng)絡(luò)提供統(tǒng)一的絕對(duì)參考時(shí)間，但是統(tǒng)一的虛擬時(shí)鐘能夠保證如TDMA類協(xié)議的正常運(yùn)轉(zhuǎn)。

2.3 CS－MNS 算法的仿真分析

2.3.1 仿真環(huán)境設(shè)置

文獻(xiàn)［9］在只有兩個(gè)節(jié)點(diǎn)的場景中理論證明了CS－MNS的穩(wěn)定性和收斂性，并通過仿真分析了CS－MNS在較大的網(wǎng)絡(luò)規(guī)模(節(jié)點(diǎn)數(shù)60～140)、不同的控制增益kp(取值0.1～1.95)和不同的晶振穩(wěn)定性(時(shí)鐘偏移頻率在某個(gè)時(shí)間段內(nèi)發(fā)生突變)時(shí)的性能。為了更深入地分析和理解CS－MNS在不同場景中的性能，并考慮到本研究的應(yīng)用場景，本文針對(duì)相對(duì)較小規(guī)模和較稀疏的網(wǎng)絡(luò)展開一系列研究和分析。

每一次仿真時(shí)，算法每完成一次同步迭代操作，我們就記錄當(dāng)前網(wǎng)絡(luò)中所有節(jié)點(diǎn)虛擬時(shí)間之間的最大差值的絕對(duì)值;針對(duì)每一組參數(shù)，我們都執(zhí)行了100次仿真，最終仿真結(jié)果由100次仿真的平均值得到。算法使用MATLAB編碼實(shí)現(xiàn)，開發(fā)環(huán)境為MATLAB Version 7.1.0.246(R14)Service Pack 3，平臺(tái)環(huán)境為Windows XP Professional SP 3操作系統(tǒng)，Intel Core 2 Quad CPU Q8400@ 2.66 GHz 2.66 GHz的 CPU，以及1.96 GB 的內(nèi)存。

2.3.2 仿真結(jié)果及分析

本文一共進(jìn)行了5組仿真，每組仿真采用的公共參數(shù)設(shè)置如表1所示。

5組仿真中，仿真1研究網(wǎng)絡(luò)節(jié)點(diǎn)密度，即節(jié)點(diǎn)的平均單跳鄰居數(shù)目的影響;仿真2研究消息交互周期的影響;仿真3研究消息接收成功率的影響;仿真4研究不同拓?fù)浣Y(jié)構(gòu)(體現(xiàn)在網(wǎng)絡(luò)節(jié)點(diǎn)密度和網(wǎng)絡(luò)覆蓋范圍)的影響;仿真5綜合研究各種因素包括網(wǎng)絡(luò)覆蓋范圍、網(wǎng)絡(luò)節(jié)點(diǎn)密度、網(wǎng)絡(luò)動(dòng)態(tài)性以及消息傳播時(shí)延的影響。每組仿真各自的仿真參數(shù)如表2所示。

表1 每組仿真采用的公共參數(shù)設(shè)置Table 1 Common parameters setting of all simulations

表2 每組仿真采用的參數(shù)設(shè)置(區(qū)間符號(hào)表示取區(qū)間內(nèi)的隨機(jī)值)Table 2 Other parameters setting of each simulation(interval notation means random values within the range)

圖1 仿真4中測試的3種拓?fù)浣Y(jié)構(gòu):鏈?zhǔn)?、環(huán)式和網(wǎng)格Fig.1 Three network topologies tested in the fourth simulation:tandem，ring and grid

根據(jù)仿真結(jié)果可以觀察到的現(xiàn)象以及得出的結(jié)論分析如下:

首先，在消息接收成功率100%的前提下，網(wǎng)絡(luò)節(jié)點(diǎn)密度越大，算法的收斂速度越快。網(wǎng)絡(luò)節(jié)點(diǎn)密度較小時(shí)(2個(gè)節(jié)點(diǎn)和4個(gè)節(jié)點(diǎn))，算法甚至?xí)冉?jīng)歷一個(gè)發(fā)散的過程，最終才會(huì)收斂到一個(gè)穩(wěn)定狀態(tài)。網(wǎng)絡(luò)節(jié)點(diǎn)密度越大，每個(gè)節(jié)點(diǎn)修正自己時(shí)間時(shí)，就能參考網(wǎng)絡(luò)中更多節(jié)點(diǎn)的折衷時(shí)間信息，從而加速了收斂的過程;

其次，消息交互周期越長，算法收斂速度越慢;消息接收成功率越低，算法收斂速度越慢。原因很直觀，因?yàn)橄⒔换ブ芷诘淖冮L和消息接收成功率的降低都會(huì)導(dǎo)致節(jié)點(diǎn)之間時(shí)戳消息交互次數(shù)的減少，從而減少了算法的成功迭代次數(shù)。對(duì)于一些基于競爭的MAC(Media Access Control)層接入?yún)f(xié)議，網(wǎng)絡(luò)節(jié)點(diǎn)密度的增大將增加節(jié)點(diǎn)之間碰撞的概率，導(dǎo)致消息接收成功率降低［11］，所以使用此類MAC協(xié)議的網(wǎng)絡(luò)中，節(jié)點(diǎn)密度的增大并不總是會(huì)加快CS－MNS的收斂過程。此外，雖然縮短消息交互周期可以提高算法收斂速度，但是增加了網(wǎng)絡(luò)開銷。還需注意的是，即使在消息接收成功率只有20%時(shí)，算法仍然能夠收斂;

第三，仿真網(wǎng)格拓?fù)浣Y(jié)構(gòu)收斂最快，鏈?zhǔn)酵負(fù)浣Y(jié)構(gòu)收斂最慢。仔細(xì)分析各拓?fù)浣Y(jié)構(gòu)，鏈?zhǔn)浇Y(jié)構(gòu)中，節(jié)點(diǎn)之間最小間隔跳數(shù)的最大值為7，節(jié)點(diǎn)平均鄰居數(shù)約為1.78;環(huán)式結(jié)構(gòu)中，節(jié)點(diǎn)之間最小間隔跳數(shù)的最大值為4，節(jié)點(diǎn)平均鄰居數(shù)為2;網(wǎng)格結(jié)構(gòu)中，節(jié)點(diǎn)之間最小間隔跳數(shù)的最大值為3，節(jié)點(diǎn)平均鄰居數(shù)為2.67。由前面分析結(jié)果，在100%的消息接收成功率前提下，節(jié)點(diǎn)平均鄰居數(shù)越多，收斂越快;此外，節(jié)點(diǎn)之間間隔跳數(shù)越多，單跳之間時(shí)間相互修正的結(jié)果傳播到全網(wǎng)就需要越長的時(shí)間，因此算法在網(wǎng)格結(jié)構(gòu)中收斂最快，鏈?zhǔn)浇Y(jié)構(gòu)中收斂最慢;

最后，仿真網(wǎng)絡(luò)動(dòng)態(tài)性越高(節(jié)點(diǎn)移動(dòng)速度越快)，算法收斂越快。這是因?yàn)?，?dòng)態(tài)性越高的網(wǎng)絡(luò)，節(jié)點(diǎn)的平局鄰居數(shù)在時(shí)間軸上作平均后大于動(dòng)態(tài)性較低的網(wǎng)絡(luò)中對(duì)應(yīng)的值。此外，可以發(fā)現(xiàn)由于考慮了傳播時(shí)延，雖然算法能夠收斂，但是同步精度受到了較大的影響。

綜上，CS－MNS算法具有很強(qiáng)的健壯性，其在不同場景和環(huán)境中都能夠保證收斂。但是該算法受消息傳播時(shí)延影響較大，同步精度性能較差(達(dá)到了1 ms左右)。

3 CS－MNS算法的改進(jìn)

3.1 基于傳播時(shí)延修正的CS－MNS算法

從對(duì)CS－MNS的仿真分析中可以發(fā)現(xiàn)傳播時(shí)延對(duì)其同步精度的性能影響較大，而在實(shí)際的應(yīng)用場景中，尤其是在節(jié)點(diǎn)之間間距較遠(yuǎn)時(shí)傳播時(shí)延是不能忽略的。因此，本文設(shè)計(jì)了一種基于傳播時(shí)延修正的 CS－MNS算法，記為 CS－MNS－d，以改進(jìn)算法在實(shí)際應(yīng)用場景中的同步精度性能。

具體地，CS－MNS－d根據(jù)傳播時(shí)延對(duì)公式(3)所示CS－MNS的校正因子遞歸控制規(guī)則進(jìn)行了修正。新的校正因子遞歸控制規(guī)則如下所示:

根據(jù)真實(shí)時(shí)戳計(jì)算節(jié)點(diǎn)間傳播時(shí)延原理如圖2所示。計(jì)算時(shí)，忽略了節(jié)點(diǎn)i和j之間的時(shí)鐘頻率偏移差別。

圖2 傳播時(shí)延計(jì)算原理圖Fig.2 The principle of calculating propagation delay

令ΔTij表示之間的時(shí)鐘偏差，則有

由公式(5)和公式(6)可得

注意，T1和T4為節(jié)點(diǎn)i的真實(shí)時(shí)戳，T2和T3為節(jié)點(diǎn)j的真實(shí)時(shí)戳。因此，每個(gè)節(jié)點(diǎn)發(fā)送的同步消息中需要同時(shí)包含虛擬和真實(shí)時(shí)戳。

3.2 仿真性能對(duì)比

采用與上一節(jié)仿真5完全一樣的場景和算法參數(shù)設(shè)置，經(jīng)過100次仿真后，CS－MNS－d的仿真結(jié)果如圖3所示。

圖3 CS－MNS－d在仿真5場景中的仿真結(jié)果Fig.3 Results of the CS－MNS－d algorithm in the scenario of the fifth simulation

由圖3所示結(jié)果可以看出，CS－MNS－d在3種動(dòng)態(tài)場景中都能快速收斂，即使在最慢的情況下(節(jié)點(diǎn)移動(dòng)時(shí)間間隔∈［11，15］s)，算法在不到40s的時(shí)間內(nèi)同步誤差能夠達(dá)到100μs以下，在不到60s的時(shí)間內(nèi)同步誤差能夠達(dá)到50μs以下，而CS－MNS在最好情況下在30s左右就接近收斂，并且最終收斂時(shí)的同步誤差也在1000μs以上。因此，相對(duì)于 CS－MNS，CS－MNS－d 更適用于傳播時(shí)延不能忽略的覆蓋了較大地理范圍的實(shí)際無線通信網(wǎng)絡(luò)中。

4 結(jié)語

本文通過仿真分析，說明了CS－MNS算法具有較強(qiáng)的健壯性，以及其在不同場景和環(huán)境中具有較好的收斂性，但是該CS－MNS算法受消息傳播時(shí)延影響較大?；诖?，本文提出了一種基于傳播時(shí)延修正的改進(jìn)算法，仿真結(jié)果表明，改進(jìn)后的算法在不能忽略傳播時(shí)延的環(huán)境中同步精度大大提高，具有一定的實(shí)際應(yīng)用價(jià)值。CS－MNS還存在一些需要進(jìn)一步改善的地方，例如算法迭代初期，網(wǎng)絡(luò)中的時(shí)鐘會(huì)有一個(gè)發(fā)散的過程，因此增加了算法收斂的時(shí)間;再如，如果網(wǎng)絡(luò)初始時(shí)間相差非常大時(shí)CS－MNS會(huì)不穩(wěn)定等，這些都是進(jìn)一步研究的重點(diǎn)。

［1］任豐原，黃海寧，林闖.無線傳感器網(wǎng)絡(luò)［J］.軟件學(xué)報(bào)，2003，14(7):1282－1291.REN Feng－yuan，HUANG Hai－ning，LIN Chuang.Wireless Sensor Networks［J］. Journal of Software，2003，14(7):1282－1291.(in Chinese)

［2］Wu Y－C，Chaudhari Q，Serpedin E.Clock Synchronization of Wireless Sensor Networks［J］.IEEE Signal Processing Magazine，2011，28(1):124－138.

［3］黃琳，馬文杰，李國軍，等.基于GNSS的通信星座系統(tǒng)的時(shí)間同步研究［J］.航天器工程，2010，19(6):67－74.HUANG Lin，MA Wen－jie，LI Guo－jun，et al.Study on GNSS－based Time Synchronization for a Communications Satellite Constellation System［J］.Spacecraft Engineering，2010，19(6):67－74.(in Chinese)

［4］Sivrikaya F，Yener B.Time Synchronization in Sensor Networks:A Survey［J］.IEEE Network，2004，18(4):45－50.

［5］易勝藍(lán).嵌入式Linux下IEEE 1588時(shí)間同步的實(shí)現(xiàn)［J］.電訊技術(shù)，2012，52(5):800－803.YI Sheng－lan.Implementation of IEEE 1588 Time Synchronization under Embedded Linux［J］.Telecommunication Engineering，2012，52(5):800－803.(in Chinese)

［6］Ganeriwal S，Kumar R，Srivastava M B.Timing－sync Protocol for Sensor Networks［M］.New York:ACM Press，2003:138－149.

［7］Maroti M，Kusy B，Simon G，et al.The Flooding Time Synchronization Protocol［M］.New York:ACM Press，2004:39－49.

［8］Elson J，Girod L，Estrin D.Fine－grained Network Time Synchronization Using Reference Broadcasts［C］//Proceedings of the Fifth Symposium on Operating System Design and Implementation.Boston，MA:IEEE，2002:163－167.

［9］Rentel C H，Kunz T.A Mutual Network Synchronization Method for Wireless Ad Hoc and Sensor Networks［J］.IEEE Transactions on Mobile Computing，2008，7(5):633－646.

［10］Kunz T，MacNeil M.Implementing Clock Synchronization in WSN:CS－MNS vs.FTSP［C］//Proceedings of the 2011 IEEE 7th International Conference on Wireless and Mobile Computing，Networking and Communications.Wuhan:IEEE，2011:157－164.

［11］蹇強(qiáng)，龔正虎，朱培棟，等.無線傳感器網(wǎng)絡(luò)MAC協(xié)議研究進(jìn)展［J］.軟件學(xué)報(bào)，2008，19(2):389－403.JIAN Qiang，GONG Zheng－h(huán)u，ZHU Pei－dong，et al.Overview of MAC Protocols in Wireless Sensor Networks［J］.Journal of Software，2008，19(2):389 －403.(in Chinese)