螢火蟲模型在水下傳感器網絡時間同步中的新應用

金彥亮,方昌立,張曉帥,姚 彬

螢火蟲模型在水下傳感器網絡時間同步中的新應用

金彥亮,方昌立,張曉帥,姚 彬

(上海大學通信與信息工程學院,上海200444)

時間同步是傳感器網絡的基本需求,但在復雜的水下環境中,水下無線傳感器網絡(underwater wireless sensor networks,UWSNs)的時間同步面臨著兩大挑戰:長傳播時延和節點的移動性.將螢火蟲同步算法模型應用于水下,提出了水下螢火蟲算法機制,利用其良好的相位補償特點,結合新的動態分簇機制,有效地提高了同步效率,縮短了同步時間.同時,巧妙結合Chirp擴頻信號具有較強抗多普勒能力的特點,進一步提高了水下無線傳感器網絡的同步精度.通過仿真實驗,驗證了水下螢火蟲同步算法的優異性能.

水下無線傳感器網絡;螢火蟲模型;Chirp信號;時間同步;多普勒效應

水下無線傳感器網絡(underwater wireless sensor networks,UWSNs)的時間同步在海洋軍事網絡系統、生態采集系統、監測航道運輸系統、勘測海底能源等領域有著廣泛的應用[1].許多學者提出了一些具有較高精確度的水下時間同步算法.早期有考慮水下廣播機制和節點移動性的TSHL[2]和MU-Sync[3]算法,后來進一步發展出把多普勒因素也考慮到水下環境中的D-Sync[4]和Mobi-Sync[5]算法.本工作首次將螢火蟲同步算法模型應用于水下無線傳感器網絡,根據其分布式和相位補償特點,提出新的動態分簇機制,以優化和縮短網絡系統的同步時間.同時,由于水下節點具有移動性,節點間會存在多普勒效應,為了更好地估計長傳播時延,本工作創新地設計出結合Chirp信號的物理幀結構,利用Chirp擴頻技術克服水下多普勒效應,以獲取更高的同步精度.

1 相關工作

1.1 螢火蟲同步算法模型

首先,介紹經典的螢火蟲算法的M&S模型和RFA(reachback f i ref l y algorithm)模型.然后,在此基礎上為了克服水下多普勒效應及信道衰減而引入Chirp擴頻技術,較好地解決了水下傳感器網絡面臨的長傳播時延和節點移動性問題.

1.1.1 M&S模型及RFA模型

1990年,Mirollo等[6]提出一種實用的脈沖耦合振蕩器模型——M&S模型,該模型奠定了螢火蟲算法的基礎.在此模型中,振蕩器依然使用狀態變量x來描述,x的變化服從函數f(φ)(相位-狀態方程),其中f是[0,0]到[0,1]上的平滑單調遞增凸函數:式中,b是消散因子且b＞0,它和曲線的彎曲程度成正比.當b→0時,f(φ)=φ(線性相位-狀態方程),φ是相位變量且滿足dφ/dt=1/T(T是同步周期).盡管M&S模型完美證明了全連通網絡中耦合脈沖對的同步可能性,但是該模型的缺點是所有的振蕩器有相同的晶振頻率,且網絡必須是全連接的,耦合過程節點間的時延忽略不計.

針對這些局限性,Tyrrell等[7]給出了RFA模型.相比于M&S模型,RFA模型在本輪同步周期中節點的相位不受同步報文的影響,還較好地解決了報文傳輸延時問題.圖1可以反映出這兩個同步模型間的差別.

圖1 M&S和RFA同步模型Fig.1 M&S and RFA synchronization model

在圖1(a)中,當節點監聽到鄰居節點激發時會及時增加自身增量;在圖1(b)中,節點在監聽到鄰居節點激發后并沒有立刻作出反饋,而是把下一輪的節點起始時間設置成上個周期積累的相位增量和.這些特點都為RFA模型應用于水下傳感器網絡創造了條件.

1.1.2 同步時域不應期

在螢火蟲模型中,為了解決當時延存在時出現的“回聲”現象,可以使耦合脈沖對在一定時間段內對收到的同步信息不作回應,這個時間段稱為不應期,其大小應滿足

式中,maxvij是節點網絡中相距最遠的節點傳輸信號的延時,而兩倍的最大延時表示一個同步信號從發射點到原點的往返延時,不應期時間內須忽略掉該時間內接到任意同步信號作用.根據RFA螢火蟲同步算法相位補償優勢及同步時域不應期的特點,可將其應用于水下所需解決的同步問題.考慮到本工作中節點都是動態的,需要研究移動節點間的多普勒效應的影響,故引入了Chirp擴頻技術.

1.2 Chirp信號

Chirp信號也可稱作線性調頻信號(正弦信號),在一定時間內其頻率隨時間線性增大或減小.由于Chirp擴頻具有較大時間帶寬積,抗多普勒性能較好,因此可以利用多普勒效應來減小同步誤差.Chirp信號表達式如下:

式中,f0為信號中心頻率,rect(t/T)為矩形窗函數,

因為Chirp信號具有很尖的脈沖并且容易被檢測到,所以可以在一個噪聲信道里面被捕獲到.根據這個特點,在水下復雜環境中設計出結合Chirp信號的水下螢火蟲同步算法數據幀結構,能夠得到更加可靠的數據報文,以更加精確的方式來估計多普勒因子,計算出長傳播時延.

1.3 時鐘相位和時鐘頻偏

時鐘模型是用來進行時間同步協議性能失效性分析的常用數學模型.定義傳感器節點i在某個物理時刻t的本地時間為

式中,ai和bi分別為節點i的時鐘偏移和時鐘頻偏,每個節點都有一個起始時間并形成一個時鐘模型.時鐘偏移和時鐘頻偏是導致同步誤差的主要因素,而時鐘偏移會引起獨立于時間的常數誤差,然而時鐘相位則會導致隨時間而增加的誤差.為了得到較好的同步性能,要同時考慮這兩個因素.

2 水下螢火蟲同步算法模型

水下螢火蟲算法模型是一個跨層的時間同步研究方法.根據螢火蟲算法具有的分布式和RFA模型的相位補償特性,本工作提出水下螢火蟲動態分簇新機制,從物理層提出快速實現簇內和簇間同步的方法,同時可以較好地解決報文的傳輸時延問題,以獲取更加可靠的報文數據來計算長傳播時延.在設計物理幀結構時,巧妙結合Chirp擴頻信號,提出用分段多普勒估計方法來估計多普勒規模因子;然后在應用層,利用從物理層獲取的時間戳信息,結合估算出來的多普勒規模因子,通過數學處理可以計算出傳播時延.

2.1 水下螢火蟲動態分簇機制

水下螢火蟲同步模型如圖2所示,海平面上有信標節點,水下有很多無線傳感器網絡節點,圖中紅色的圓圈表示信標節點,可以獲取來自水面接收站從同步衛星傳過來的GPS授時,藍色的圓圈表示普通待同步節點.

圖2 水下螢火蟲同步模型Fig.2 Model of underwater f i ref l y synchronization

Sun等[8]提出的無線傳感器網絡的分簇策略是基于相位排序實現完全的等間距分簇.這種依據間隔的分簇方式可以達到較好的同步效果,但為了實現更快速的同步,本工作提出了一種基于鄰近相位的快速排序方法.本工作動態分簇的核心思想是:在一定的節點范圍內,以最快的速度實現同步為出發點,把節點按照相位最相近的原則分到一個簇,然后依次劃分出若干個簇.相位越近,需要調整的間隙越小,簇內相位調節以實現同步的速度越快,時間越短.從理論上可以完成上述相位分簇,針對實際中存在相近相位也不一定在鄰近范圍的情況,可以按照一定的概率原則,每簇選取盡可能相近的相位,但不排除在每簇中存在個別相位差異較大的節點.此處假設所有的節點均可參與同步,網絡為全連通的,暫不考慮節點在同步過程中出現失效以及毀壞的情形.

假設網絡中每個節點i均為相同的脈沖振蕩器,每個節點觸發Firing時間的頻率為ω,周期長度為T=1/ω.在標準化處理各個節點之后,用ψi(t)來表示節點當前的一個狀態,即狀態函數ψi(t)為每個節點的相位,且滿足ψi(t)∈θ,θ=[0,1],1≤i≤K,每個節點在T時間內從0勻速增加到1,其增長率為dψi(t)/dt=1/T.當某一時間t0≥0滿足

則認為網絡達到了同步狀態.

2.1.1 簇內同步

在分簇前,需要初始化網絡中的參數,節點數K=n,周期時長為T0,系統隨機分配初始相位,定義Q為相位從0到閾值的最大度量.

初始化各節點的相位后按大小進行排序:

再根據最大、最小相位的差值得出最大相位差

可以推導出分簇的數目

接下來是最重要的部分,即把最相近的相位節點分在同一簇中,然后按照這個規則依次劃分.首先把網絡中相位最小的一組標記為第一簇,然后倒數第二小的標記為第二簇,依次排列出N簇,每一簇的節點數目為n/N:

這樣分簇后,簇內節點的相位在較小的差異下,依據RFA同步模型進行最優化分簇,各節點只與本簇節點產生信息交換,依據螢火蟲同步節點的平級特點,所有簇內節點均被視為“簇頭”.這樣能更快地實現簇內同步,更好地滿足水下傳感器網絡的同步要求.

2.1.2 簇間同步

因為簇間同步需要一段時間,網絡系統會設置一個合適的等待時間,以保證簇的同步完全完成.依照RFA同步模型規律,此時網絡是由一些異步節點逐步調整成N個獨立的節點.隨后這N個獨立節點相互耦合相互影響,最后完成簇間的同步.簇間同步機制的詳細過程將在2.3節結合水下螢火蟲公式進行分析.

2.2 多普勒規模因子估計

為了估計多普勒規模因子,已有學者提出模糊度函數法[9],但是這種方法的最大缺點是需要大量的自相關器,從而導致較大的運算量和硬件復雜度.本工作引入一種更加實用且有效的方法,稱為分段多普勒估計法.圖3為本工作提出的分段幀結構,在該幀結構中,傳輸的螢火蟲同步信號是由兩個線性調頻(linear modulated frequency,LMF)的Chirp信號結合在一起,中間兩段空白作為保護間隔.

圖3 結合LMF Chirp信號的幀結構Fig.3 Frame structure combining LMF Chirp signal

根據Chirp同步信號的特點,本工作采用匹配濾波器法檢測同步信號,其流程如圖4所示.首先對時間窗內截取的同步信號進行匹配濾波,檢測匹配輸出信號的峰值,然后獲取輸出信號的峰值點位置,根據峰值點位置的偏移量計算信號的同步時刻.

圖4 Chirp信號匹配相關的同步信號檢測流程圖Fig.4 Matching related detection f l ow chart of synchronization signal of Chirp signal

定義傳輸輸入信號數據包的時間為Γtp,當匹配濾波器接收到數據時,可以測量出位置偏移量為Γrp,也就是接收一個數據幀的過程,

式中,?為多普勒規模因子.這樣就能精確得到多普勒規模因子的數值,從而獲得節點間的相對移動速度.在不同的水下環境里,水聲速度是一個變化的值.影響水聲速度的因素有很多,比如海水的溫度、深度、鹽度以及水壓.本工作把水聲傳播的速度認為是常量C=1 500 m/s,根據對應的物理關系,節點相對速度的估計公式為

在真實的水下環境中,節點在往返程的多普勒影響是不同的,這也導致節點間往返程的相對速度也是不同的.根據本工作的信息機制,可以推導出

式中,?1,?2分別代表去程和回程的多普勒規模因子的大小,υ1,υ2分別代表去程和回程節點的相對估計速度.

2.3 同步信息交換機制

在時間同步研究領域里,有許多典型的信息交換機制,例如單發送方式、發送-接收方式以及接收-接收方式等.泛洪時鐘同步協議(f l ooding time synchronization protocol,FTSP)[10]是典型的單發送方式,該機制能量消耗大,同步精度也不夠;參考廣播同步(reference broadcast synchronization,RBS)[11]協議,Mobi-Sync和D-Sync均采用發送-接收方式,這種方式的時間同步精度較高.本工作信息交換機制采用發送-接收機制(見圖5),以獲取較高的同步精度.

選取某一個簇內的兩個節點,A為參考節點,可以獲取來自水面接收站傳送的標準時間,B為普通待同步節點.參考節點A廣播其帶有時間戳TA1[1]的信息給鄰近節點B,節點B在TA1[1]+γ[1]接收到參考信息,經過處理后,節點B將回傳帶有時間戳TB2[1]的信息給參考節點.兩節點間進行物理層的相位補償,經過多次信息交換,按照本工作提出的水下螢火蟲動態分簇機制最終達到整個簇內的同步.

但是,水下的節點并不是固定不變的,會隨著洋流以及其他因素發生位置變化.這里假設兩個節點在一維的直線上,無論節點是相互靠近還是遠離都是可計算的模型.下面介紹假定普通節點遠離參考節點的傳播時延估計過程.

圖5 信息交換機制Fig.5 Message exchange scheme

選取第一個信息交換回程:TA1[1]→TB1[1]→TB2[1]→TA2[1].首先定義:

式中,Δγ為往返傳播時延的差值.根據信息交換機制可以推導出

在本工作提出的水下螢火蟲同步模型中,假定普通節點和參考節點的相對速度是線性增長的.Δd表示從TB1[1]到TA2[1]的相對距離,可以估計出

考慮到整個時間同步過程,假定Δl為從TA1[1]到TA2[1]的相對距離.更進一步可以得到

同時可以用運動學方程來建立等式:

為了簡化計算,忽略傳播時延γ2[1],并作如下數學處理:

再結合式(17),(18),(20)和(21),可以分別計算出傳播時延γ[1]和γ[2]:

至此,已經推導出傳播時延的計算公式.依據上述簇間同步的RFA模型,定義脈沖發射時間為τsend,接收到的本地時間為τreceive,狀態方程需滿足

式(24)中,Tp[i]為節點間傳播時延,T為同步周期長度,由于γ[i]=Tp[i],a=φsend,依據式(22)和(23),可以建立等式分別求出傳播時延γ[1],γ[2].反代入式(24),(25)和(26)可求出節點相應的相位狀態φsend.

此處求解傳播時延的方案不同于傳統的線性擬合,傳統方案是通過一組數據進行線性回歸處理來估計傳播時延,這就需要采集大量的數據才能滿足必要的同步需求,同時在線性回歸處理時,也是通過近似方法來實現的,進一步帶來了誤差.而本工作則運用螢火蟲同步算法模型的特點,與所提出的多普勒估計方法巧妙結合直接求出變量,具有更高的準確性,并減少了同步誤差.

3 仿真

本工作提出的水下螢火蟲同步算法中的誤差主要來源于以下兩個方面:一是帶有Chirp信號的參考節點從開始發送信息到接收的整個過程所受到的多普勒頻移,導致兩個自相關的主峰之間產生時滯,誤差近似為

二是節點在相互的信息交換機制間的誤差,這主要是由于在螢火蟲同步期間信道隨機噪聲帶來的影響.本工作近似地把噪聲ξ看作是高斯隨機誤差,得到的總的同步誤差表達式如下:

對于水下傳感器網絡同步而言,最大的挑戰是如何減少算法的同步誤差.為了更加科學地研究水下螢火蟲模型并驗證其準確性,本工作進行了1 000次的仿真實驗獲取平均值.根據水下環境的特點,本工作首先選取了合適的仿真參數(見表1).

表1 水下螢火蟲同步算法仿真參數Table 1 Simulation parameters of the underwater f i ref l y synchronization algorithm

首先研究經典的同步算法和水下螢火蟲同步算法同步速度的關系.如圖6所示,在仿真中對同步時間進行歸一化處理,得出時間同步關系.可以看出,水下螢火蟲同步算法最先達到同步.D-Sync和Mobi-Sync的同步速度大體相當,而TSHL(time synchronization for high latency)算法則表現出較差的同步性能,基本上在其他的同步算法達到同步很長一段時間內才逐步達到同步.這是由于水下螢火蟲模型動態分簇新機制的良好特性能夠更快地實現同步,而TSHL節點不具有動態特性,更沒有考慮多普勒效應的影響,因此導致同步性能最差.

圖6 幾種算法同步時間比較Fig.6 Comparison of several algorithms for synchronization time

接著比較幾種典型的水下同步算法在水下螢火蟲環境下的性能.同樣經過多次大量的仿真,求取平均值,可得如圖7所示結果.從圖7中的總體趨勢可以看出,達到同步后隨著同步時間的增加,所有同步機制的同步誤差都在變大,幾乎是以指數趨勢增長.Mobi-Sync的性能明顯要優于TSHL,實際上通過仿真可以得出,TSHL在水下環境中的性能表現甚至比沒有同步的情況都要差,主要原因是TSHL節點是靜止的,傳播時延也是按照常數來計算的,這樣必然導致估計時鐘相位非常不準確.D-Sync的性能要優于Mobi-Sync,Mobi-Sync算法盡管詳細考慮了節點的移動性問題,但是卻忽略了水下多普勒因素對移動節點具有較大影響;D-Sync算法是基于多普勒的時間同步算法,有較大的克服多普勒效應的能力.而本工作提出的水下螢火蟲同步算法結合Chirp信號的物理層結構,更好地克服了多普勒效應;同時利用螢火蟲模型良好的相位補償優勢,使得同步后的誤差維持在一個非常低的水平,最終獲得了非常好的同步性能.

圖7 同步后時間與同步誤差的關系Fig.7 Time vs.error after synchronization

從圖8中可以明顯看出,動態分簇新機制對同步時間起重要作用.在具有動態分簇新機制和不具有動態分簇兩種情況下,動態分簇使同步速度得到非常大的提升,可見動態分簇新機制對于改善水下傳感器網絡的時間同步速度具有重大意義.

圖8 動態分簇新機制和非動態分簇機制對比Fig.8 Dynamic clustering machanism vs.non-dynamic clustering machanism

由于上述仿真均在5次信息交換下得出結果,顯然同步信息交換的次數對于同步誤差也有很大的影響.下面進行了在不同信息交換次數下的仿真,驗證同步誤差隨著同步信息交換次數增加的變化(見圖9).可以看出,隨著信息交換次數的增加,同步誤差逐步減小,這也符合實際情況.當一個同步周期內信息交換次數增加了,必然是相位不斷得到調整,從而使得同步誤差處于較低的水平.而對于沒有時間同步的情況,隨著時間的增加,必然導致誤差的積累,由仿真結果可知,同步誤差趨勢呈近似線性增長.

圖9 信息交換次數與同步誤差關系Fig.9 Message exchange times vs.synchoronization error

4 總結與展望

本工作是將螢火蟲算法模型應用到水下傳感器網絡時間同步中.為了更好地將螢火蟲算法應用于水下,發揮其良好的相位補償優勢,首先提出了基于動態分簇的新機制,以最相近的相位劃分為簇的原則,極大地提高了同步速度;然后針對水下移動節點存在的多普勒效應,巧妙提出了結合Chirp擴頻技術的方法,設計出可以克服多普勒效應的物理幀結構;再利用分段多普勒估計方法以及RFA同步模型,計算出傳播時延和其對應的相位狀態.同時,本工作較好地解決了水下傳感器網絡中的同步模型簇內同步和簇間異步的問題,在螢火蟲同步模型原則下,簇內通過動態分簇完成同步,簇間則通過相互異步的獨立節點,在Firing的影響下逐步實現簇間的同步,最終達到整個網絡的同步.

但是影響水下環境的時間同步有諸多因素,本工作僅從節點的動態性以及多普勒效應角度去考慮同步問題,另外水下環境中還存在嚴重的多徑效應、信道衰落等方面問題,下一步本工作將重點關注這些影響因素.

[1]鐘海東,鄔春學,孔若英.無線傳感器網絡時間同步算法誤差分析[J].微計算機信息,2008,24(4):157-158.

[2]SYED A A,HEIDEMANN J S.Time synchronization for high latency acoustic networks[C]//INFOCOM.2006.

[3]CHIRDCHOO N,SOH W S,CHUA K C.MU-Sync:a time synchronization protocol for underwater mobile networks[C]//Proceedings of the Third ACM International Workshop on Underwater Networks.2008:35-42.

[4]LU F,MIRZA D,SCHURGERS C.D-sync:doppler-based time synchronization for mobile underwater sensor networks[C]//Proceedings of the Fifth ACM International Workshop on Under-water Networks.2010:3.

[5]LIU J,ZHOU Z,PENG Z,et al.Mobi-Sync:efficient time synchronization for mobile underwater sensor networks[J].IEEE Trans Parall Distr Syst,2013,24(2):406-416.

[6]MIROLLO R E,STROGATZ S H.Synchronization of pulse-coupled biological oscillators[J].SIAM Journal on Applied Mathematics,1990,50(6):1645-1662.

[7]TYRRELL A,AUER G,BETTSTETTER C.Firef l ies as role models for synchronization in ad hoc networks[C]//Proceedings of the 1st International Conference on Bio Inspired Models of Network,Information and Computing Systems.2006:4.

[8]SUN Y,JIANG Q,ZHANG K.A clustering scheme for reachback f i ref l y synchronicity in wireless sensor networks[C]//2012 3rd IEEE International Conference on Network Infrastructure and Digital Content.2012.

[9]SHARIF B S,NEASHAM J,HINTON O R,et al.A computationally efficient Doppler compensation system for underwater acoustic communications[J].IEEE Journal of Oceanic Engineering,2000,25(1):52-61.

[10]MAR′OTI M,KUSY B,SIMON G,et al.The f l ooding time synchronization protocol[C]//Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems.2004:39-49.

[11]ELSON J,GIROD L,ESTRIN D.Fine-grained network time synchronization using reference broadcasts[J].ACM SIGOPS Operating Systems Review,2002,36(1):147-163.

New application of f i ref l y synchronization model in time synchronization of underwater wireless sensor networks

JIN Yanliang,FANG Changli,ZHANG Xiaoshuai,YAO Bin
(School of Communication and Information Engineering,Shanghai University,Shanghai 200444,China)

Time synchronization is a basic demand for a sensor network.However,in a complex underwater environment,underwater wireless sensor networks(UWSNs)face two challenges:long propagation delay and mobility of nodes.This paper uses a f i ref l y synchronization model to underwater,and proposes an underwater f i ref l y algorithm.It makes use of good characteristics of distribution and phase compensation to ef f ectively improve the ef f ectiveness of time synchronization and shorten synchronization time.A chirp signal is combined with the model since the chirp has strong of anti-Doppler ability.This also contributes more synchronization precision for underwater wireless sensor networks.Good performance of the underwater f i ref l y algorithm model is verif i ed by simulation.

underwater wireless sensor networks(UWSNs);f i ref l y model;Chirp signal;time synchronization;Doppler ef f ect

TN 301.6

A

1007-2861(2017)05-0647-11

10.12066/j.issn.1007-2861.1765

2015-12-23

上海市科委重點資助項目(12511503303,14511105602,14511105902);上海大學特種光纖與光接入網重點實驗室開放課題資助項目(SKLSFO2012-04);上海市教委基金資助項目;上海微系統所無線通信與傳感器網絡重點實驗室開放課題資助項目

金彥亮(1973—),男,副教授,博士,研究方向為無線傳感網、移動通信、無線通信等.

E-mail:jinyanliang@staf f.shu.edu.cn

本文彩色版可登陸本刊網站查詢:http://www.journal.shu.edu.cn