基于移動模型的水下傳感器網絡時間同步算法

王慧強，溫秀秀，林俊宇，馮光升，呂宏武

?

基于移動模型的水下傳感器網絡時間同步算法

王慧強，溫秀秀，林俊宇，馮光升，呂宏武

（哈爾濱工程大學計算機科學與技術學院，黑龍江哈爾濱 150001）

水下傳感器網絡具有高時延、移動性的特點?，F有時間同步算法在網絡移動性方面考慮不足，時間同步參數計算精度不高。針對該問題，首先分析網絡移動性對時間同步參數計算的影響，建立節點移動模型，并在此基礎上推導出時間同步參數計算方程；進而提出一種能夠應用于水下高時延網絡的時間同步算法MM-sync。實驗結果表明，與現有算法相比，MM-sync能夠在通信量較小的基礎上達到較高的精確度，適用于高密度快速運動的水下傳感器網絡。

傳感器網絡；水下環境；高時延網絡；時間同步；移動模型

1 引言

水下傳感器網絡是指將具有能耗低、較短通信距離的水下傳感器節點部署到指定海域中，采用水聲通信，利用節點的自組織能力自動建立的網絡[1]，具有網絡傳播時延大、移動性和能量有限的特點，是一種新型傳感器網絡。時間同步是網絡節點調度和網絡安全認證等算法的基礎[2~4]，是水下傳感器網絡的重要問題[5,6]。對于采用無線電波通信的傳感器網絡，已經出現了一些成熟的時間同步算法。例如，Tiny-sync算法、Mini-sync算法和LS(light weight tree-based synchronization)算法。這些算法往往忽略網絡傳播時延，不能適應水下的高時延環境[7]，尤其是水下傳感器網絡的移動特性會導致傳播時延始終處于動態變化狀態，進一步增加了時間同步算法的設計難度。

針對水下網絡的高時延特性，Affan等[8]首先提出了TSHL(time synchronization for high latency acoustic networks)算法，該算法通過2個階段的消息交換來估計節點時鐘間的相對漂移和相對偏移，算法過程簡單易行，但忽略了節點在通信過程中的移動性，不能適用于節點運動劇烈的環境。Nitthita等[9]在分析了影響時間同步精度的因素后，提出了MU-sync(time synchronization protocol for underwater mobile networks)算法，該算法通過增加雙向通信次數實現節點對時間同步，能夠達到較高精度，但需要消耗大量能量。Bong等[10]考慮了節點不能和時間參考節點直接通信的情況，提出了針對時延容忍網絡的分布式時間同步算法DCS(distributed asynchronous clock synchronization in delay tolerant networks)，該方法通過相鄰節點間歇性通信的方法提高時間同步的準確性，并使用加權系數衡量時間同步信息的精度以解決網絡時延對計算結果的影響。劉軍等[11]提出了Mobi-sync算法，該算法借鑒了洋流模型，節點首先估計自身運動趨勢，然后進行時間同步。該算法與具體環境結合緊密，為解決時間同步問題提供了新思路，但也限制了其應用范圍。

現有水下傳感器網絡時間同步算法以雙向通信為基礎，能夠適應水下網絡的高時延特性，卻忽略了網絡的移動特征，導致計算精度不足（移動特性會導致傳播時延始終處于動態變化狀態）；Mobi-sync等算法雖然考慮了水下網絡移動性的特點，提高了算法的計算精度，卻需要節點感知自身運動速度，限制了算法的應用范圍。針對這些問題，本文綜合考慮了水下網絡高時延和移動性特點，建立節點移動模型，并在此基礎上分析網絡傳播時延與節點位置的動態變化，得出時間同步參數方程，進而提出算法MM-sync，僅通過節點之間的單向通信和時間同步參數方程求解，即可得到時間同步所需的參數，實現節點間時間同步。與其他時間同步算法相比，MM-sync無需雙向通信，節點無需對自身的運動速度進行感知，能夠適應水下網絡高時延和移動特性，具有適用性強、計算精度較高、網絡能量消耗較小的特點，適用于近海區域的高密度水下傳感器網絡。

2 水下傳感器網絡時間同步模型

傳感器網絡中節點的本地時鐘是依靠對自身晶體振動中斷計數實現的[12]。每個晶體由于制作工藝等因素，震蕩頻率存在微小偏差。此外，不同節點的時鐘初始化時間也有可能不同。這些因素造成不同節點時鐘會存在差異。節點的時鐘與標準時間存在以下關系

時鐘頻偏和時鐘漂移的范圍是確定的。其中，傳感器節點時鐘頻偏的范圍由傳感器生產工藝確定，可以從傳感器的性能參數中得出。同時，時鐘初始化時間的不同是引起時鐘漂移不為0的主要原因，應小于相鄰節點傳輸信號的最大時延。

MM-sync算法的目標是計算普通傳感器節點的時鐘頻偏和時鐘漂移，完成普通傳感器節點和浮標節點的時間同步。下面首先介紹MM-sync算法的基礎——節點移動模型。

3 節點移動模型

節點移動模型是MM-sync算法的基礎。本節首先分析洋流對節點運動的影響；然后描述時間同步過程中信號傳輸時間與節點位置的動態變化關系，建立節點移動模型。

3.1 洋流對節點運動的影響

節點的運動受洋流影響。Brower在20世紀70年代提出了洋流模型

3.2 時間同步節點移動模型

網絡中有普通傳感器節點和浮標節點，的時鐘頻偏為，時鐘漂移為。網絡布置好后，發送時間同步數據分組。依次接收到數據分組。形成記錄列表。中記錄表示第個數據分組由在時刻發送，在其時鐘顯示時接收。這里浮標節點時間為參考時間，因此為標準時間，而對應的標準時間即修正時間為。

(4)

4 MM-sync原理

本節主要介紹MM-sync計算時間同步參數的原理。首先以節點移動模型(式(4))為基礎，建立時間同步參數方程組；然后分析時間同步參數方程組在具體應用過程中可能產生的誤差，以及其控制方法。MM-sync算法的具體流程將在第5節給出。

4.1 時間同步參數方程組

式(4)是一個二次方程，且包含了一些時間同步不關心的變量、、，可以采用變量替換的方法簡化運算，變量替換規則如下

(6)

(7)

將式(5)~式(7)代入式(4)，可得關于、、、、的五元一次方程

(9)

4.2 誤差控制

算法的誤差來源主要有2個：1) 極端天氣下水下節點的劇烈運動；2) 時間同步數據分組的處理和發送時延?？梢圆捎镁€性擬合、多浮標節點時間同步的方法降低第一種誤差；采用物理層加時間戳的方法降低第二種誤差，下面分別介紹各個誤差控制方法的原理。

4.2.1 線性擬合

降低假設節點做勻速直線運動的時間，進而結合線性擬合可以降低第一種誤差。具體來說，首先對方程組(9)進行變換，將、、作為中間變量，對參數計算方程組(9)中的任意4個方程進行變換，消去、、，得到和的線性關系如下

其中，系數、、的計算方法如下

(12)

(14)

(15)

4.2.2 多浮標節點同步

當網絡中存在多個浮標節點時，普通傳感器節點可以充分利用從多個浮標節點接收的時間同步數據分組來提高MM-sync算法的計算精度。然而，并不是所有浮標節點發送的數據都可靠，因此需要對每個浮標節點發送的數據進行篩選。

首先根據時鐘頻偏和時鐘漂移的大概范圍進行數據初步篩選。令、分別表示時鐘頻偏和時鐘漂移的最大可能偏差。4.2.1節提到將收集到的來自的數據每4個劃分為一組，并對每組數據應用式(12)~式(15)，得到關于和線性關系的系數。令、、表示第組系數，表示系數的組數。根據式(11)可以得到，進而得到不等式。由于，，因此可以得到、、應滿足的約束關系為

4.2.3 物理層加時間戳

針對第二種誤差來源，可以采用在物理層加時間戳的方法降低誤差。水聲網絡中數據分組延時主要由3部分組成：數據分組處理時延、信道接入時延、傳播時延[9]。水聲信號的傳輸速度大約為無線電波的傳輸速度的百萬分之一，傳播時延在秒級，因此傳播時延占數據分組時延的主要部分。其余2種時延可以使用在物理層加時間戳的方法降低其對時間同步的影響[9]。下面對MM-sync算法進行詳細介紹。

5 MM-sync算法

結合上面MM-sync計算時間同步參數的原理，提出一種能夠應用于水下高時延網絡的時間同步算法。首先給出MM-sync算法的具體流程；然后介紹時間同步數據分組的結構；最后分析算法的時間復雜度。

5.1 算法流程

MM-sync采用單向通信。浮標節點作為時間同步參考節點，開啟網絡時間同步，開始周期性地發送時間同步數據分組；普通傳感器節點收集時間同步數據分組，首先進行數據分組，然后建立線性方程組，并在此基礎上進行數據篩選，最后結合線性擬合方法計算時間同步所需的參數。MM-sync算法偽代碼如下。

算法：MM-sync

輸入：、、、、

輸出：、

開始

/*數據收集*/

2) 接收時間同步數據分組;

5) end while

6) for 每一個時間同步參考節點

8) while {lengh([])<4}

/*數據分組*/

/*線性方程建立*/

/*數據篩選*/

17) end if

19) end while

/*數據深度篩選*/

25) end for

26) end if

27) end for

28) 刪除、、中值為null的元素;

/*對標準型進行線性擬合*/

結束

對于存在不能和浮標節點直接通信節點的網絡，可以與網絡分簇機制相結合，采用逐步同步的方法。水下無線傳感器網絡為了便于管理，通常需要建立分簇結構[1]，每個簇里包含一個簇頭節點和若干成員節點，簇頭節點與其成員節點一跳可達，負責收集成員節點數據，并通過其他簇頭節點將數據發送到浮標節點。這里假設網絡已經采用文獻[14]所述的簇構建算法，為普通傳感器節點建立了簇結構。浮標節點作為初始時間同步參考節點開啟網絡時間同步，此時能夠與浮標節點直接通信的節點通過MM-sync完成時間同步；完成時間同步的簇頭節點進而成為臨時時間同步參考節點，周期性地發送時間同步數據分組個，進而使其成員節點和與其相鄰的簇頭節點能夠通過MM-sync完成時間同步；此過程一直繼續，直到所有簇頭節點都成為臨時時間同步參考節點，全網時間同步完畢。

5.2 時間同步數據分組格式

時間同步數據分組由發送節點序號、發送時間、接收時間3部分組成。

時間同步數據分組由時間同步參考節點發送。節點在應用層產生數據分組，并在數據分組上標記自身節點序號；在物理層標記數據分組發送時間。

時間同步數據分組由未完成時間同步的普通傳感器節點接收。節點在接收到時間同步數據分組后，在物理層將接收時間標記在數據分組上，并在應用層執行上面的時間同步算法。

5.3 時間復雜度分析

時間復雜度是衡量算法計算量的標準，本部分主要分析MM-sync算法的時間復雜度。MM-sync算法核心部分是第6）行~29）行，是一個二層循環結構。外層循環變量為時間同步參考節點的數量；對于每一個時間同步參考節點，內層循環次數為從該時間同步參考節點處接收數據分組的數量。因此總循環次數為數據分組的總數量，計算時間復雜度為，是一種簡單算法，能夠適用于計算能力低、電池能量有限的水下傳感器網絡節點設備。

6 實驗與分析

實驗環境為NS-2 (network simulator-2)，本文對NS-2進行了修改，添加了水下仿真模塊和時間同步算法，并在此基礎上從數據分組消耗量、時間同步精度兩方面對MM-sync算法、TSHL算法和MU-Sync算法進行比較。

6.1 實驗設置

表1 實驗參數設置

6.2 實驗分析

圖4所示為數據分組消耗量隨節點數量的變化情況。橫軸表示網絡中普通傳感器節點的數量，縱軸表示網絡完成同步所消耗數據分組的數量。從圖中可以看出，隨著節點數目增加，MM-sync算法的數據分組消耗量不變，TSHL算法與MU-sync算法數據分組消耗量增加，其中，MU-sync算法數據分組消耗量增加最為明顯。這是由于TSHL算法在第2階段需要時間同步參考節點與傳感器節點進行一次雙向通信，以計算節點時鐘漂移，因而數據分組消耗量曲線隨節點數量增加而緩慢上升。算法MU-sync為了達到更高的計算精度，增加了雙向通信的次數，當網絡節點較多時，消耗數據分組的數量迅速增加，遠遠超過了MM-sync算法和TSHL算法。而MM-sync算法無需雙向通信，原理與TSHL算法和MU-sync算法不同，普通傳感器節點不需要對時間同步數據分組進行應答。因而無論節點數目增加或減少，消耗數據分組的數量始終為常量。

圖11和圖12分別顯示多浮標節點條件下時鐘同步計算偏差隨洋流流過頻率的變化情況(可靠度門限，置信度，圖中MM-sync后面括號中的數字表示浮標節點的數量)。由圖可知，MM-sync(4)的計算精度優于其他算法。當洋流流過頻率較小時，網絡節點運動較為穩定，此時浮標節點數量(即時間參考節點的數量)對MM-sync算法計算精度的影響較小，MM-sync算法和MU-sync算法的計算精度相差不大；隨著洋流流過頻率的增加，網絡節點運動的不穩定性增強，各個算法的計算精度逐漸降低，由圖11和圖12可知，此時增加浮標節點的數量能夠保持MM-sync的計算精度，使MM-sync(4)和MM-sync(2)的計算精度優于MU- sync，因此增加浮標節點的數量能夠增強MM-sync應對洋流頻繁波動的能力。

7 結束語

水下傳感器網絡高時延、移動性和能量有限的特點增加了時間同步算法設計的難度。針對水下網絡的特性，本文首先建立節點移動模型，并以此為基礎，提出了一種時間同步算法MM-sync。MM-sync通過單向通信和時間同步參數方程求解的方法，完成時間同步所需參數的計算，并結合線性擬合的方法降低算法誤差。與已有時間同步算法相比，MM-sync算法避免了雙向通信，能夠有效地降低網絡負載，降低網絡能量消耗；節點無需感知自身速度，增加了算法的適用范圍。同時，由于在建模過程重點考慮了節點移動導致的網絡時延動態變化問題，因此在節點高速運動的環境下，仍能夠保證所需的計算精度。實驗結果表明，MM-sync算法在高密度運動穩定的水下環境中具有良好性能，且能夠適應各種鹽度與溫度的水域環境。但算法目前采用的移動模型僅適用于水流較為平穩的近海區域。在接下來的工作中將對移動模型進行改進，以擴大本算法的適用范圍。

[1] GUO Z W, LUO H J, HONG F, et al. Current progress and research issues in underwater sensor networks [J]. Journal of Computer Research and Development, 2010,47(3):377-389.

[2] SEUNGKU K, HUA B L, DOO S E. An independent sleep scheduling protocol for increasing energy efficiency in wireless body area networks[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2013, E96-A(5): 908- 915.

[3] QASIM M C. Simple and robust clock synchronization scheme[J]. IEEE Transactions on Communications, 2012,60(2):328 -332.

[4] JULIEN R, DARRY V, TIMOTHY B. The case for feed-forward clock synchronization[J]. IEEE/ACM Transactions on Networking, 2012, 20(1):231-242.

[5] FIKRET S, BULENT Y. Time synchronization in sensor networks: a survey[J]. IEEE Network,2004,18(4):45-50.

[6] SAURABH G, RAM K, MANI B S. Timing-sync protocol for sensor networks[C]//The 1st International Conference on Embedded Networked Sensor Systems. New York, c2003: 138-149.

[7] GUO Y, LIU Y T. Mobile counteracted time synchronization for underwater sensor networks[J]. Information Computing and Applications, 2012,307(1): 515-522.

[8] AFFAN A S, JOHN H. Time synchronization for high latency acoustic networks[C]//The 25th IEEE International Conference on Computer Communications. Barcelona, Spain, c2006: 1-12.

[9] NITTHITA C, WEE-SENG S, KEE C C. MU-sync: a time synchronization protocol for underwater mobile networks[C]//The Third ACM International Workshop on Underwater Networks. New York, c2008:35-42.

[10] CHOI B J, SHEN X M. DCS: distributed asynchronous clock synchronization in delay tolerant networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2012,23(3):491-504.

[11] LIU J, ZHOU Z, ZHENG P, et al. Mobi-Sync: efficient time synchronization for mobile underwater sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2013,24(2): 406-416.

[12] ZHOU X W, WEI W, QIN B P. Research on time synchronization in wireless sensor networks[J]. Chinese Journal of Sensors and Actuators, 2006,19(1):20-29.

[13] CARUSO A, PAPARELLA F, VIEIRA L F M, et al. The meandering current mobility model and its impact on underwater mobile sensor networks[C]//The 27th Conference on Computer Communications. San Francisco, CA, USA, c2008: 771-779.

[14] SUNDARAMEENA V, PRIYATHARISINI D. Acquaint based grid clustering algorithm for Underwater wireless sensor network[C]//2014 International Conference on Information Communication and Embedded Systems. Chennai, India, c2014: 1-4.

Time synchronization algorithm based on mobility model for underwater sensor networks

WANG Hui-qiang, WEN Xiu-xiu, LIN Jun-yu, FENG Guang-sheng, LYU Hong-wu

(College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China)

With the characteristics of high transmission delay and mobility, distributed time synchronization of underwater sensor networks can be very challenging. The existing works cannot get high accuracy, because most of them ignore the long transmission latency, or dynamic changing transmission delay caused by the mobility. A mobility model was built considering the effect of mobility and long transmission latency on time synchronization, and a time synchronization parameters equation was formed according to the mobility model. Thus, based on the equation, a time synchronization algorithm (MM-sync) was proposed. The experiment results show that MM-sync can reduce the consumption of energy, and can get higher accuracy than state-of-art solutions in high density underwater sensor networks with rapid movement.

sensor networks, underwater environment, high latency propagation networks, time synchronization, mobility model

TP393

A

10.11959/j.issn.1000-436x.2016001

2014-11-11；

2015-02-06

國家自然科學基金資助項目(No.61370212)；博士點基金優先發展領域基金資助項目（No.20122304130002）；教育部高等學校博士點基金資助項目（No.20102304120012）；黑龍江省自然科學重點基金資助項目（No.ZD201102）；中央高?；究蒲袠I務費專項基金資助項目（No.HEUCF100601, No.HEUCFZ1213）

The National Natural Science Foundation of China (No.61370212), The Research Fund for the Doctoral Program of Higher Education of China (Priority Development Area) (No.20122304130002), The Research Fund for the Doctoral Program of Higher Education of China (No.20102304120012), The Natural Science Foundation of Heilongjiang Province (No.ZD201102), The Fundamental Research Fund for the Central Universities (No.HEUCF100601, No.HEUCFZ1213)

王慧強（1960-），男, 河南周口人，哈爾濱工程大學教授、博士生導師，主要研究方向為云計算、信息安全、自律計算與可信計算、認知網絡。

溫秀秀（1989-），女，黑龍江牡丹江人，哈爾濱工程大學博士生，主要研究方向為傳感器網絡、未來網絡和認知網絡等。

林俊宇（1981-），男，廣西博白人，哈爾濱工程大學助理研究員，主要研究方向為自律計算、未來網絡和 QoS保障。

馮光升（1980-），男，山東德州人，哈爾濱工程大學講師，主要研究方向為認知網絡和QoS保障。

呂宏武（1983-），男，山東日照人，哈爾濱工程大學講師，主要研究方向為未來網絡、性能評價和進程代數。