大規模水下傳感器網絡時間同步研究

郭 瑛 張 震

?

大規模水下傳感器網絡時間同步研究

郭 瑛*張 震

(青島科技大學 青島 266061)

該文針對大規模水下傳感器網絡，對信標節點覆蓋內的節點，設計了基于靜態信標節點的時間同步算法；對信標節點覆蓋范圍外的節點，設計了動態節點輔助的時間同步算法。減少了節點移動對同步精度的影響。同時，根據水下聲速變化規律，設計了水下傳感器網絡分層時間同步機制，有效克服了已有算法在處理大規模水下傳感器網絡時間同步問題上的不足。仿真結果表明，該方法的同步效果明顯好于現有的算法。

水下傳感器網絡；時間同步；信標節點；動態節點；分層

1 引言

海洋在人類生活中所起的作用日益顯著，水下傳感器網絡得到人們越來越多的關注，并廣泛應用在海洋環境監測、污染監控、資源勘測、目標探測、跟蹤定位等領域[1,2]。時間同步是水下傳感器網絡的關鍵技術之一，傳感器節點采集的數據和時間信息匹配才有意義，它也是實現網絡協同工作、協同休眠等技術的基礎[3]。

現階段，研究者們已經取得了大量陸地傳感器網絡時間同步算法的研究成果[4,5]，傳感器網絡時間同步算法按數據包交換方式的不同可分為3類：基于“接收者-接收者”的算法，基于“發送者-接收者”的雙向算法和基于“發送者-接收者”的單向算法。參考廣播同步(Reference Broadcast Synchronization, RBS)[6]算法是一個典型的基于“接收者-接收者”的同步算法。節點間通過交換接收時間戳，對比本地時鐘，經過計算實現接收節點時間的彼此同步。基于“發送者-接收者”的雙向時間同步協議(Timing-sync Protocol for Sensor Networks, TPSN)[7]采用逐層同步方式實現全網的時間同步，文獻[8]提出通過犧牲一定精度來減少能量開銷的時間同步算法(Light Weight Tree-based Synchronization, LTS)。為了避免往返傳輸時間估計，減少交換消息的數量，產生了基于“發送者-接收者”的單向時間同步機制，洪泛時間同步協議(Flooding Time Synchronization Protocol, FTSP)[9]利用節點間交換時鐘信息和線性衰減來實現同步。文獻[10]提出全局同步算法(Global Clock Synchronization)，每個節點周期性地向其鄰居節點廣播包含它當前時間信息的數據包，接收者計算出這些時間的平均值并發送到其鄰居節點，再將該值當作新的時間值，如此循環直到達到整個網絡的同步。

由于沒有考慮水下傳輸的特殊性，陸地傳感器網絡時間同步算法不能直接用于水下環境。水下傳感器網絡采用水聲通信，與采用無線電通信的陸地傳感器網絡有許多不同之處。水聲通信的傳播速度比較低，聲音在水中的速度約為1500 m/s，比無線電相差5個數量級。而且聲速在水中受溫度、深度和鹽度等因素的影響，具有動態變化的特點，使傳播延遲難以準確預測和計算。在海流等因素的作用下，傳感器節點具有一定的移動性[11]。節點的移動導致節點間的距離發生變化，還會產生多普勒頻移效應[12]，也增加了傳播延遲的估計難度。此外，水聲通信的可用帶寬窄，數據率低，誤碼率高，受海洋內波、背景噪音、信號多徑傳播、多普勒頻移等因素影響，信號不穩定，具有高度時空多變性。

針對水下傳感器網絡時間同步問題，研究者們做了一系列的研究，并取得了一些成果[13]。Syed等人[14]提出了高延遲網絡時間同步協議(Time Synchronization for High Latency networks, TSHL)。Tian等人[15]借鑒了RBS算法中的漂移率建模的思想和TPSN算法中的MAC層打時間戳以減小抖動的思想，提出一種輕量級、高延遲傳感器網絡時間同步算法。但是它們假設網絡中的節點是靜止不動的，節點間的傳播延遲固定不變，而水下節點會受海流的影響而移動，導致時間同步的誤差比較大。MU-Sync[16]采用分簇的方法實現簇首和簇內節點之間的時間同步，但需要較多的信標節點均勻部署在網絡中作為簇首節點，導致節點部署成本高，部署方案容易受水下環境的影響。用于層次水下傳感器網絡的Mobi-Sync[17]通過節點間的幾何關系消除節點移動的影響，其要求自定位的浮漂節點和能量充足的超級節點，并要在計算中使用節點的位置關系。D-Sync[18]利用多普勒頻移來進行時間同步，但是需要用多普勒頻移測量值和節點的速度推算傳播延遲。

這些水下傳感器網絡時間同步算法都是基于“成對節點”(pair wise)的同步方式，主要研究具有標準時間的信標節點和單個待同步節點之間的關系，而沒有考慮水下傳感器網絡的部署規模。對于大規模部署的水下傳感器網絡，具有標準時間的信標節點難以覆蓋整個部署區域，而且水聲通信傳播延時長，速率低，易受環境影響，簡單地把“成對節點”的時間同步算法擴展到整個網絡，必然降低時間同步的精度。

本文針對大規模水下傳感器網絡，系統地研究了基于信標節點的同步算法，以及對于信標節點覆蓋范圍外的節點，利用已經同步的動態節點輔助同步的方法，并基于水聲的傳播規律，設計了水下傳感器網絡分層同步機制，以保障時間同步算法的有效性。本文主要內容如下：(1)設計基于靜態信標節點的移動水下傳感器網絡時間同步算法。(2)研究水下信息傳輸和節點移動的規律，設計動態節點輔助的時間同步算法，同步信標節點覆蓋范圍外的節點。(3)分析水聲速度變化特點，設計分層的水下傳感器網絡時間同步機制，進一步提高時間同步精度。

2 算法設計

本節首先介紹水下傳感器網絡時間同步的基本思想，然后針對大規模水下傳感器網絡，設計基于靜態信標節點和動態節點的時間同步算法。

2.1 時間同步基本思想

傳感器節點的時間由內部時鐘控制，而內部時鐘與振蕩器的頻率有關，由于硬件、制作工藝等方面的原因，不同節點有不同的頻率變化，因而有不同的內部時鐘，導致不同節點的時間不同步。節點的本地時間和標準時間之間關系為

式中代表節點編號，T代表標準時間，t代表節點的當地時間，a為時鐘漂移，b為時鐘偏移。

時間同步的基本思想是節點通過數據交換的方式，估計時鐘漂移和偏移，修正本地時鐘，使得本地時鐘和標準時鐘保持同步。

2.2 靜態信標同步算法

為了減少節點移動對時間同步精度的影響，避免節點移動帶來的誤差，在時間同步的過程中，具有標準時間的信標節點在同步過程中保持靜止狀態，這種基于靜態信標同步(Beacon Node based Clock Synchronization)算法簡稱為B-Sync。

如圖1所示，節點是信標節點，具有標準時間，它在同步的過程中不移動位置。節點是待同步的普通節點，隨海流等因素而運動。為了提高精度，同步數據包中的時間信息是來自MAC層的時間戳。

圖 1 靜態信標同步示意圖

信標節點發送同步信息，該信息包含其發送時間T1，經過時間1后，信息到達待同步節點，其記錄下該信息到達的本地時間T1。然后，待同步節點立即向信標節點發送同步信息，信息中包含其發送時間T2。由于待同步節點在接收到同步信息后，立即發送新的信息，兩個信息間的時間間隔只有短短的幾微秒，節點的移動能力有限，在如此短的時間內，其移動距離可以忽略，而信標節點的位置保持不變，因此，假設該信息從待同步節點到達信標節點的時間也是1。此信息到達信標節點后，信標節點記錄下到達時間T2。可以得到

接下來，信標節點在T3再次發送同步信息，由于水下信息傳播速度慢，傳播延遲長，信息傳播需要幾十毫秒甚至幾百毫秒的時間，待同步節點在這段時間里的移動不可忽略，該信息到達待同步節點所經過的時間不再是1，而是2，這也是許多時間同步算法在設計過程中忽略的問題。該信息到達待同步節點后，待同步節點記錄下該信息到達的本地時間T3。待同步節點立即向信標節點發送同步信息并含發送時間T4。信息經過時間2后到達信標節點，信標節點記錄下該信息到達時間T2。可以得到

聯立式(2)~式(5)，即可得到如式(6)的節點的時鐘漂移和時鐘偏移。

由于信息傳播過程中，傳播延遲具有時變性，會影響時間同步精度，可以用線性擬合的方式提高同步精度。根據式(4)和式(5)，可以得到如式(7)的時鐘漂移和時鐘偏移函數：

2.3 動態節點同步算法

在大規模水下傳感器網絡中，信標節點的傳播范圍有限，不能達到所有節點。此時，需要由已經同步的節點作為新的參考節點，輔助時間同步算法的運行，直到所有節點都完成同步。但是，這些已同步的節點與信標節點不同，它們不能保持靜止，而是隨水流移動。故適用于靜態信標節點的時間同步算法不能直接應用在動態節點輔助同步的過程中。因此，設計了動態節點輔助的時間同步(Dynamic Node assisted Clock Synchronization)算法D-Sync。

如圖2所示，動態節點是一個已經同步的普通水下節點，作為新的參考節點；節點是待同步的普通節點，兩節點都隨海流等因素運動。

圖2 動態節點同步示意圖

節點發送同步信息，其發送時間為T1，經過時間1后，該信息到達待同步節點，節點記錄下信息到達的本地時間T1。然后，節點向節點發送同步信息，信息中包含其發送時間T2。由于節點的移動在信息傳播過程中不可忽略，信息經過時間2后到達節點，而不再是時間1。節點記錄下到達時間T2。可以得到

假設，節點的移動速度為1，節點的移動速度為2，水下信息的傳播速度為V，可以得到

即

其中，節點的移動速度可以通過攜帶的硬件設備(比如：多普勒速度計)測量得到，也可以利用一些較成熟的算法[19]計算得到。

節點在時間T3再次發送同步信息，該信息經過時間3后，到達節點，到達的當地時間為T3，可以得到

其中

同理可得

其中

對于動態節點，同樣可以針對多組數據，采用線性擬合的方法，提高同步精度。此時，時鐘漂移和時鐘偏移的函數為

在上述算法中，沒有考慮水聲傳播速度V變化的影響。水聲傳播速度與水下環境密切相關，只有滿足一定條件時，才可將其視為常量，該問題將在下節詳細討論。

3 水下分層時間同步

在上一節的算法設計中，假設信息的傳播速度保持不變，但在實際情況下，水下聲音傳播速度受到多種因素的影響，具有動態變化的特點。本節通過對水聲速度變化規律的分析，針對大規模海洋傳感器網絡，設計分層的時間同步方式L-Sync (Layering Clock Synchronization)，減少水聲速度變化對算法的影響，進一步提高同步精度。

3.1 水聲傳播規律

與陸地傳感器網絡不同，水聲的速度不是固定值，而是有規律的變量。海洋中的聲速V(m/s)隨溫度(℃)，鹽度(‰)和壓力(kg/cm2)的增加而增大[20]。目前，應用較多的經驗公式是威爾遜公式：

式中

海水中鹽度變化不大，典型值為35‰，同層海水的溫度變化也不大，經常用深度替代靜壓力，每下降10 m水深近似增加1個大氣壓的壓力，也就是說海水中的聲速具有垂直分層特性，聲速近似為水平分層變化。這種水平分層變化規律對動態節點時間同步算法具有重要影響，應保證信息傳輸盡可能的發生在相同的水平面。

3.2 分層同步

為了使函數式(19)中的水聲傳播速度V近似常量，同步節點應在同一水平面。本文采用分層的方式進行時間同步，而不是簡單的選擇相鄰節點進行時間同步。

如圖3所示，把水下部署區域按照深度劃分層次。在時間同步過程中，僅同層節點之間進行時間同步，不同層次的節點不互相發送同步信息，不參與彼此的時間同步計算。這種分層同步的方式需要每層都有至少一個具有標準時間的信標節點，或者一個具有自主移動能力的信標節點，它可以移動到不同的層面并保持靜止，逐層實現時間同步。

圖3 分層時間同步

在第1層上，具有標準時間的信標節點首先同步其傳播范圍內的節點1。節點1同步完成后作為新的參考節點，同步其傳播范圍內的節點2，依次類推，節點2同步節點3和節點4，節點4再同步節點5。在第2層和第3層上，也按照相同的方式同步全部節點。

這種時間同步方式會帶來累積誤差，也就是說待同步節點離信標節點的距離越遠，誤差越大。這是由于采用已經同步的動態節點輔助時間同步的時候，該節點會把自己的時間偏差代入到新的同步過程中，帶來更大的時間偏差，這個偏差隨著同步節點的增加而逐漸積累。

有很多方法可以減少累積誤差，比如采用具有移動能力的信標節點，在多個不同的位置發起時間同步，或者在每層都部署多個信標節點。待同步節點以其到不同信標節點的跳數作為權重，距離信標節點越近，權值越大，取各個同步運算結果的加權平均值作為最終結果，以降低累積誤差的影響。

4 仿真及結果分析

本節對B-Sync, D-Sync和L-Sync算法進行模擬仿真分析，并與時間同步算法TSHL[14], MU-Sync[16]和Global[10]進行比較。

仿真中，待同步節點擁有不同的內部時鐘，其移動速度在0.1 m/s~1 m/s之間。信標節點發送消息包的時間間隔1 s，時鐘粒度1 μs。TSHL和MU-Sync采用25個參考信息包用于線性回歸運算。仿真中使用的時間均來自MAC層時間戳。

首先，研究B-Sync和D-Sync算法的精度。圖4顯示的是采用靜態信標節點進行時間同步，經過一段時間后，本地時鐘偏差的變化趨勢。從圖中可以看出，B-Sync算法的誤差小于TSHL和MU-Sync。TSHL假設每次信息傳播延遲相同，對于移動水下傳感器網絡，節點移動使得節點間相對位置改變，從而產生不同的信息傳播延遲。MU-Sync在第1次線性回歸估計過程中，沒有考慮到傳播延遲，引入較大的誤差。

圖5是采用動態節點作為標準時間節點，運行不同的時間同步算法一段時間后的時間偏差。D-Sync算法明顯好于TSHL和MU-Sync，這是由于后兩種算法沒有考慮標準時間節點移動的影響。

然后，研究B-Sync和D-Sync算法的能耗。由于仿真中采用相同的傳輸協議和時間格式，不同算法發送的數據包長度相同，為了簡化計算，采用數據包數目來衡量算法能耗。圖6展示了時間同步100次，TSHL, MU-Sync, B-Sync和D-Sync需要的數據包數目。TSHL和MU-Sync需要一定數量的數據包才能滿足運算要求，能耗較高。而B-Sync和D-Sync計算所需要的數據包數目大幅度降低。其中，B-Sync不必考慮信標節點移動帶來的影響，比D-Sync更加節省能量。

接下來分析L-Sync算法的精度和能耗。假設水中均勻部署100個節點，每個節點具有不同的內部時鐘，且只能和一跳內的鄰居通信，把L-Sync和同樣考慮全局時間同步的Global進行比較。圖7顯示了時間同步完成一段時間后，L-Sync和Global的時間偏差，圖8顯示了時間同步10次，L-Sync和Global的能耗。由于Global沒有考慮傳播延遲和節點移動的影響，其精度低于L-Sync, Global需要和全部鄰居節點交換時間，比L-Sync需要更多的數據包。

仿真結果表明，在大規模水下傳感器網絡中，本文的時間同步方案精度高、能耗低，其效果好于現有的時間同步算法。

5 結束語

本文針對大規模水下傳感器網絡，設計了基于信標節點的水下傳感器網絡時間同步算法；對于信標節點覆蓋范圍外的節點，采用動態節點輔助時間同步；結合水下聲速的變化規律，設計了分層的水下傳感器網絡時間同步機制。在今后的工作中，要進一步研究水聲信道的特點，分析算法對不同環境的適應性，并通過海洋實驗驗證算法性能。

圖4 靜態時間同步后的時鐘偏差變化

圖5 動態時間同步后的時鐘偏差變化

圖6 時間同步所需數據包數目

圖7 大范圍時間同步后的時鐘偏差變化

圖8 大范圍時間同步所需數據包數目

[1] Gkikopouli A, Nikolakopoulos G, and Manesis S. A survey on underwater wireless sensor networks and applications[C]. Proceedings of 20th Mediterranean Conference on Control & Automation (MED), Barcelona, Spain, 2012: 1147-1154.

[2] Wang Yi-fan, Zhang Zai-chen, and Bi Guang-guo. An overview on underwater acoustic sensor networks[C]. Proceedings of 17th International Conference on Telecommunications, Doha, Qatar, 2010: 779-783.

[3] Davis A and Hwa Chang. Underwater wireless sensor networks[C]. Proceedings of Oceans, Virginia, USA, 2012: 1-5.

[4] Zennaro Davide, Ahmad Aitzaz, Vangelista Lorenzo,.. Network-wide clock synchronization via message passing with exponentially distributed link delays[J]., 2013, 61(5): 2012-2024.

[5] Maggs M K, O’Keefe S G, and Thiel D V. Consensus clock synchronization for wireless sensor networks[J]., 2012, 12(6): 2269-2277.

[6] Elson J, Girod L, and Estrin D. Fine-grained network time synchronization using reference broadcasts[C]. Proceedings of OSDI 2002, Boston, MA, USA, 2002: 147-163.

[7] Saurabh G, Ram K, and Mani B S. Timing-Sync protocol for sensor networks[C]. Proceedings of International Conference on Embedded Networked Sensor Systems, Los Angeles, California, USA, 2003: 138-149.

[8] Greunen J and Rabaey J. Lightweight time synchronization for sensor networks[C]. Proceedings of ACM International Conference on Wireless Sensor Networks and Applications, San Diego, CA, USA, 2003: 11-19.

[9] Maroti M, Kusy B, and Simon G. The flooding time synchronization protocol[C]. Proceedings of WCNC2004, Atlanta, GA, 2004: 39-49.

[10] Li Qun and Rus Daniela. Global clock synchronization in sensor networks[C]. Proceedings of IEEE INFOCOM, Hong Kong, 2004: 19-28.

[11] Guo Ying, Cui Hai-wei and Si Wen. Large delay underwater sensor networks clock synchronization with mobile beacon[C]. Proceedings of Wireless Communications and Networking Conference Workshops (WCNCW), Shanghai, China, 2013: 211-215.

[12] Liu J, Wang, Z, Zuba M,.. DA-Sync: a doppler assisted time synchronization scheme for mobile underwater sensor networks[J]., 2013, DOI: 10.1109/TMC.2013.13.

[13] Zennaro D, Tomasi B, Vangelista L,.. Light-Sync: a low overhead synchronization algorithm for underwater acoustic networks[C]. Proceedings of OCEANS, VA, USA, 2012: 1-7.

[14] Syed A A and Heidemann J. Time synchronization for high latency acoustic networks[C]. Proceedings of 25th IEEE International Conference on Computer Communications, Barcelona, Catalunya, Spain, 2006: 1-12.

[15] Tian Chen, Jiang Hong-bo, Liu Xue,.. Light-weight time synchronization protocol for high resource-constrained networks[C]. Proceedings of IEEE International Communications (ICC), Dresden, Germany, 2009: 14-18.

[16] Chirdchoo N, Soh W S, and Chua K C. MU-Sync: a time synchronization protocol for underwater mobile networks[C]. Proceedings of WUWNet’08, San Francisco, California, USA, 2008: 35-42.

[17] Liu Jun, Zhou Zhong, Peng Zheng,.. Mobi-Sync: efficient time synchronization for mobile underwater sensor networks[C]. Proceedings of IEEE GLOBECOM 2010, Florida, USA, 2010: 1-5.

[18] Lu Feng, Mirza Diba, and Schurger Curt. D-Sync: doppler-based time synchronization for mobile underwater sensor networks[C]. Proceedings of the Fifth ACM International Workshop on Underwater Networks (WUWNET), Woods Hole, Massachusetts, USA, 2010: 1-8.

[19] Zhou Z, Cui J and Bagtzoglou A. Scalable localization with mobility prediction for underwater sensor networks[C]. Proceedings of the Annual IEEE International Conference on Computer Communications, Washington, 2008: 2198-2206.

[20] Guo Ying. Energy attenuation-based time synchronization for mobile underwater sensor networks [J]., 2012, 19(Suppl.): 57-64.

郭 瑛： 女，1981年生，博士，講師，研究方向為傳感器網絡、物聯網.

張 震： 男，1989年生，碩士生，研究方向為傳感器網絡.

Clock Synchronization Study for Large Scale Underwater Sensor Networks

Guo Ying Zhang Zhen

(&,266061,)

For large scale underwater sensor networks, the characteristics of underwater acoustic channel are investigated. A static beacon node based clock synchronization algorithm is presented for the nodes inside the beacon node’s coverage area, and a dynamic node assisted clock synchronization algorithm is designed for the nodes outside the beacon node’s coverage area. These methods reduce the effect of node mobility. A layering clock synchronization mechanism based on the feature of underwater sound velocity is proposed, which solves the clock synchronization problem of large scale underwater sensor networks. The simulation results show that, the proposed synchronization method is obviously better than existing algorithms.

Underwater sensor network; Clock synchronization; Mobile beacon; Dynamic node; Layering

TP393

A

1009-5896(2014)06-1498-06

10.3724/SP.J.1146.2013.01128

郭瑛 guoying@qust.edu.cn

2013-07-30收到，2013-11-15改回

青島市科技計劃項目(12-1-4-3-(16)-jch)，國家自然科學基金(61103196, 61170258)和山東省優秀中青年科學家科研獎勵基金(BS2012DX011)資助課題