徐世武

（福建師范大學(xué) 協(xié)和學(xué)院 信息技術(shù)系，福州350117）

引 言

無線傳感器網(wǎng)絡(luò)是由密集型、低成本、隨機(jī)分布的節(jié)點(diǎn)組成，集成了傳感器技術(shù)、計(jì)算機(jī)技術(shù)和通信技術(shù)，能夠協(xié)同地實(shí)時(shí)監(jiān)測、感知并采集各種環(huán)境的數(shù)據(jù)，適用于戰(zhàn)場通信、搶險(xiǎn)救災(zāi)和公共集會等突發(fā)性、臨時(shí)性場合[1]。保持節(jié)點(diǎn)之間時(shí)間上的同步在無線傳感器網(wǎng)絡(luò)中非常重要，它是保證可靠的數(shù)據(jù)傳輸、精確的節(jié)點(diǎn)定位、可靠的數(shù)據(jù)融合、準(zhǔn)確的目標(biāo)跟蹤與檢測的前提。如利用波的到達(dá)時(shí)間差測距，就需要高精度的時(shí)間同步。無線傳感器網(wǎng)絡(luò)中，由于頻率漂移，各個(gè)節(jié)點(diǎn)之間必然會產(chǎn)生一定的時(shí)鐘偏移，因此有效的時(shí)間同步技術(shù)對保證各個(gè)節(jié)點(diǎn)之間的時(shí)鐘同步非常重要[2]。

2002年，Elson等人在影響未來網(wǎng)絡(luò)研究發(fā)展方向的國際權(quán)威學(xué)術(shù)會議Hot Nets上，首次提出無線傳感器網(wǎng)絡(luò)時(shí)間同步的研究課題，至今已有相當(dāng)多的典型時(shí)間同步算法?；诎l(fā)送者-接收者的雙向同步算法中，比較典型的如TPSN（Timing-sync Protocol for Sensor Networks）算法[3]。TPSN算法分成兩個(gè)階段，第一階段為層次發(fā)現(xiàn)階段，第二階段為同步階段。在同步階段采用發(fā)送者-接收者的雙向成對同步算法，MAC層采用加入時(shí)間戳的技術(shù)，進(jìn)而估算出節(jié)點(diǎn)之間的傳輸延遲與時(shí)鐘偏移。該作者在Mica節(jié)點(diǎn)上測試過，TPSN平均單跳誤差為17.61μs?；诎l(fā)送者-接收者的單向時(shí)間同步算法中，比較典型的如 FTSP（Flooding Time Synchronization Protocol）算法[4]、DMTS（Delay Measurement Time Synchronization）算法[5]?；诮邮照?接收者的同步算法，典型的有RBS（Reference Broadcast Synchronization）算法[6]。近幾 年，也有作者提出了協(xié)作同步機(jī)制[7]。協(xié)作同步的核心思想仍然是屬于集中式協(xié)議，要求整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)密度較高。參考文獻(xiàn)[8]中，作者提出了分步式同步機(jī)制，整個(gè)網(wǎng)絡(luò)無需構(gòu)造由根節(jié)點(diǎn)發(fā)起的生成樹，只需要每個(gè)節(jié)點(diǎn)之間使用分布式廣播同步機(jī)制。

傳統(tǒng)的同步機(jī)制只是簡單地修正節(jié)點(diǎn)之間的時(shí)鐘偏移，傳感器節(jié)點(diǎn)時(shí)鐘由晶體振蕩器驅(qū)動(dòng)。晶體振蕩器的實(shí)際頻率通常與它標(biāo)定的頻率之間存在一定的偏移，即存在時(shí)鐘頻率的漂移。傳統(tǒng)的同步算法為了提高同步精度，節(jié)點(diǎn)就必須頻繁地重復(fù)時(shí)間同步算法，以消除時(shí)鐘偏移的影響。頻繁地交換消息，必然給功耗受限的節(jié)點(diǎn)帶來額外的負(fù)擔(dān)，因此考慮節(jié)點(diǎn)之間的時(shí)鐘漂移也是非常重要的[9]。

1 CDCO時(shí)鐘同步算法設(shè)計(jì)

1.1 時(shí)鐘模型

本同步算法采用的是發(fā)送者-接收者的雙向同步算法，同時(shí)考慮了時(shí)鐘漂移與偏移對同步精度的影響。在無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)中，如果采用的是時(shí)鐘速率恒定模型，那么節(jié)點(diǎn)的硬件時(shí)鐘Ci（t）與真實(shí)時(shí)間Ck（t）的關(guān)系可以表示為Ci（t）＝aik·Ck（t）＋mik。式中，aik為節(jié)點(diǎn)之間的相對漂移量，mik為節(jié)點(diǎn)之間的相對偏移量。如果兩個(gè)節(jié)點(diǎn)之間完全同步，則相對漂移量aik為1，相對偏移量mik為0。

1.2 單跳同步原理

如圖1所示，hi（t1）、hi（t4）、hi（t5）用來記錄參考節(jié)點(diǎn)的本地時(shí)間，hk（t2）、hk（t3）、hk（t6）用來記錄同步節(jié)點(diǎn)的本地時(shí)間。同步過程采用類似TPSN算法的雙向同步過程，假設(shè)同步節(jié)點(diǎn)與參考節(jié)點(diǎn)的時(shí)鐘關(guān)系采用時(shí)鐘恒定模型（這在現(xiàn)實(shí)中也是合理的），則hk（t）＝ρki·hi（t）＋mki。式中，hk（t）、hi（t）分別為同步節(jié)點(diǎn)與參考節(jié)點(diǎn)在本地時(shí)刻t的時(shí)鐘，ρki、mki分別為時(shí)鐘漂移量與偏移量。

圖1 雙向同步原理圖

假設(shè)傳播延遲為dki，因?yàn)樵跇O短的時(shí)間內(nèi)來回傳播延遲與節(jié)點(diǎn)時(shí)偏可假設(shè)相同。假設(shè)漂移量

則在理想情況下，ρki為1，即線段hi（t1）hk（t2）平行于線段hi（t5）hk（t6），此時(shí)不存在時(shí)鐘漂移[10]。如圖1所示，根據(jù)雙向同步原理與時(shí)鐘恒定模型可以得到：

由式（2）與式（3）得到：

則根據(jù)得到的ρBA、mBA修改同步節(jié)點(diǎn)的本地時(shí)鐘，就能實(shí)現(xiàn)與同步節(jié)點(diǎn)的時(shí)鐘同步。

1.3 多跳同步原理

假設(shè)節(jié)點(diǎn)A與其下一跳節(jié)點(diǎn)B已經(jīng)實(shí)現(xiàn)了時(shí)間同步，則可以得到：

由式（5）與式（6）可以得到：

同樣，假設(shè)節(jié)點(diǎn)B與下一跳節(jié)點(diǎn)C已經(jīng)實(shí)現(xiàn)了時(shí)間同步，同理可以得到：

顯然將式（7）帶入式（8）可以得到節(jié)點(diǎn)A與C之間的同步。

采用同樣的方法逐級迭代下去，就可以實(shí)現(xiàn)全網(wǎng)的時(shí)間同步。

1.4 理論誤差來源分析

由1.2節(jié)的分析可知，兩節(jié)點(diǎn)之間的時(shí)鐘關(guān)系為hk（t）＝ρki·hi（t）＋mki。如果兩個(gè)節(jié)點(diǎn)不存在時(shí)鐘頻偏的情況，ρki為1，即hi（t1）hk（t2）平行于邊hi（t5）hk（t6），則頻率偏移誤差：

假設(shè)不存在頻率偏移的情況下，即ρki為1，我們來計(jì)算時(shí)鐘偏移的誤差來源。根據(jù)圖1所示的發(fā)送-接收雙向消息同步過程，可以得到：

式中，hk（t3）、hi（t4）分別是t3、t4所對應(yīng)的同步節(jié)點(diǎn)和本地節(jié)點(diǎn)所測出的本地時(shí)間，Sk代表節(jié)點(diǎn)k的報(bào)文發(fā)送時(shí)間，Ak是發(fā)送報(bào)文的訪問時(shí)間，Pk→i是節(jié)點(diǎn)k傳播到節(jié)點(diǎn)i的時(shí)間，Ri是節(jié)點(diǎn)i的報(bào)文接收處理時(shí)間，Nkt是傳輸Nk個(gè)比特的總時(shí)間，Terror指傳輸比特的誤差，Rerror為打時(shí)標(biāo)過程存在的誤差，代表節(jié)點(diǎn)k與節(jié)點(diǎn)i在hk（t3）時(shí)刻的時(shí)偏。因?yàn)樵趯?shí)驗(yàn)中采用了MAC層的打時(shí)標(biāo)方法，這樣就可以消除發(fā)送時(shí)間與訪問時(shí)間對誤差的影響。于是式（11）就可以簡寫為：

由以上各式可以得到時(shí)偏：

式中，SUC＝Sk-Si，PUC＝Pk→i-Pi→k，RUC＝Ri-Rk。

2 算法性能分析

無線傳感器節(jié)點(diǎn)采用的是晶體振蕩器來計(jì)時(shí)節(jié)點(diǎn)的本地時(shí)鐘，由于成本的限制，只能采用一些低成本的晶振。硬件設(shè)備廠商一般都會給出晶振頻率變化范圍，一般時(shí)鐘漂移為[10，100]ppm。同步周期取20 s，在一個(gè)周期內(nèi)采樣4次，得到的結(jié)果如表1所列。相同情況下的多跳同步誤差如表2所列。

表1 兩種算法在一個(gè)周期內(nèi)同步精度隨采樣間隔的變化

表2 多跳同步誤差分析（均指平均誤差）

從表1中可以看出，在同一個(gè)周期內(nèi)，相比TPSN算法，CDCO算法誤差隨采樣間隔的增長明顯比TPSN慢，在相同的采樣間隔，誤差也明顯低于TPSN算法。因?yàn)橄啾扔赥PSN算法，本文考慮了時(shí)鐘漂移，因此可以在較長的時(shí)間內(nèi)保持同步。從表2可以看出，隨跳數(shù)增加，CDCO算法精度較高于TPSN算法。在相同的跳數(shù)內(nèi)，CDCO算法的誤差明顯低于TPSN算法，且隨著跳數(shù)增加，CDCO算法的同步誤差增加明顯低于TPSN算法。相對于TPSN算法，CDCO算法可以減小誤差多跳累加的影響。

結(jié) 語

本文基于發(fā)送方-接收方雙向同步算法的原理，設(shè)計(jì)了一種同時(shí)考慮時(shí)鐘偏移與漂移的同步補(bǔ)償機(jī)制（CDCO算法）。實(shí)驗(yàn)結(jié)果表明，相比傳統(tǒng)的發(fā)送方-接收方雙向同步算法，CDCO算法因?yàn)椴捎昧藭r(shí)鐘漂移補(bǔ)償技術(shù)，在同一個(gè)同步周期內(nèi)，同步誤差隨時(shí)間增加變化較??；而傳統(tǒng)的算法因?yàn)榇嬖跁r(shí)鐘漂移，在同一個(gè)周期內(nèi)誤差隨時(shí)間增大而變得越來越大。相對于TPSN算法，CDCO算法可以減小誤差多跳累加的影響。

[1]徐世武，王平，黃晞，等.無線傳感網(wǎng)絡(luò)時(shí)間同步研究進(jìn)展與分析[J].單片機(jī)與嵌入式系統(tǒng)應(yīng)用，2011，11（5）：4-7.

[2]李哲濤，李仁發(fā)，魏葉華.無線傳感器網(wǎng)絡(luò)中時(shí)間同步與測距協(xié)同算法[J].計(jì)算機(jī)研究與發(fā)展.2010，47（4）：638-644.

[3]Ganeriwal S，Kumar R，Srivastava M.Timing-sync Protocol for Sensor Networks[C]//In Proceedings of the 1st ACM Conference on Embedded Networked Sensor Systems，Los Angeles，ACM press，2003：138-149.

[4]Maroti M，Kusy B，Simon G，et al.The flooding time synchronization protocol[C]//In proceedings of the 2nd ACM Conference on Embedded Networked Sensor Systems，Baltimore ACM press，2004：39-49.

[5]Ping S.Delay measurement time synchronization for wireless sensor networks[R].Intel Research.Berkeley Lab，2003.

[6]Elson J，Girod L，Estrin D.Fine-grained Network Time Synchronization using Reference Broadcasts[C]//In Proceedings of the 5th Symposium on Operating Systems Design and Implementation，Boston，ACM press，2002：147-163.

[7]Hu A，Servetto S D.On the scalability of cooperative time synchronization in pulse-connected networks[J].IEEE Transactions on Information Theory，2006，52（6）：2725-2748.

[8]李立，劉勇攀，楊華中，等.無線傳感器網(wǎng)絡(luò)分布式一致時(shí)間同步協(xié)議的收斂分析及加速設(shè)計(jì)[J].電子與信息學(xué)報(bào)，2010，32（9）：2045-2050.

[9]王世軍，徐朝農(nóng)，安竹林，等.晶振頻率偏差補(bǔ)償?shù)臒o線傳感器網(wǎng)絡(luò)時(shí)間同步算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2008，29（11）：2055-2059.

[10]劉迪忻.無線傳感器網(wǎng)絡(luò)中基于時(shí)鐘漂移補(bǔ)償?shù)臅r(shí)間同步技術(shù)[J].時(shí)間頻率學(xué)報(bào)，2009，32（2）：120-127.