基于被動分簇的時間同步容錯技術研究

王 盼，劉廣鐘

(上海海事大學 信息工程學院，上海 201306)

0 引 言

近年來，隨著水聲傳感器網(wǎng)絡技術的發(fā)展，水聲傳感器網(wǎng)絡的應用越來越廣泛，水聲傳感器網(wǎng)絡憑借其分布性、低成本等優(yōu)點被廣泛應用于海洋監(jiān)測、污染監(jiān)控、資源開采、海難搜救等眾多領域[1]。但是，由于水聲傳感器網(wǎng)絡中受自身計算、通信、存儲等能力的硬件限制和水聲通道高延遲、低帶寬、多路徑等特性[2]，水聲傳感器網(wǎng)絡時間同步過程中容易受到攻擊，因此對水聲傳感器網(wǎng)絡時間同步過程中容錯技術的研究是必不可少的。

因為水聲傳感器網(wǎng)絡的環(huán)境惡劣，對每一節(jié)點都進行同等的要求是不現(xiàn)實的。出于節(jié)能和高效的考慮，多采用分簇的層次網(wǎng)絡拓撲結構[3]，重點是每一個節(jié)點時間同步的調(diào)整有一個上限。在無線傳感器網(wǎng)絡中，相比于葉子節(jié)點，簇頭節(jié)點的計算、通信、存儲等能力是較高的[4]。所以該方案中簇間節(jié)點可以直接通過廣播的方式與其他節(jié)點進行交流，在每一次的時間同步中，只有一個節(jié)點作為同步器來發(fā)送同步信息，這樣就避免了信息碰撞的問題。在簇頭節(jié)點自身的時鐘調(diào)整也有一個上限，從而提高節(jié)點的利用率。

1 容錯時鐘同步模型

時鐘同步模型[5-8]如下所示，文中出現(xiàn)的符號及其含義如表1所示。

表1 符號及其含義

首先對絕對時間和時鐘時間做了比較。絕對時間是一種精確的時間，時鐘時間是一種可以在傳感器節(jié)點的時鐘上看到的時間。用小寫字母表示和絕對時間有關的變量和常量，用大寫字母表示和時鐘時間有關的變量和常量。

(1)

由公式λ=ρ(2+ρ)(1+ρ)可以得到任意兩個正常節(jié)點間的漂移率是有界限的，且漂移率會少于2ρ。傳感器節(jié)點中通常包含廉價的晶體振蕩器，時鐘漂移率在幾十微秒左右。如果一個節(jié)點可以正確執(zhí)行給定的時鐘同步算法就稱為正常節(jié)點。假設時鐘同步是循環(huán)執(zhí)行的，每一輪包括R個時間單位。對于兩個正常節(jié)點，在時間段[begf,endf]內(nèi)存在最大時鐘漂移率δ，則有：

δ=2ρ(endf+1-endf)

(2)

(3)

其中，ε=(1+ρ)φ是時鐘讀數(shù)錯誤的上限，包括最大的傳輸時延和在時延中的時鐘漂移率。

假設在開始時間t0，正常節(jié)點i和j之間的時鐘差異小于δ0，即有：

|Fi(t0)-Fj(t0)|<δ0

(3) 在塔-線體系導地線和桿塔同時發(fā)生共振時,同階共振的兩個相鄰單塔會出現(xiàn)共振方向相同和相反兩種振型形式.在同階情況下,與單塔模態(tài)頻率相比,塔-線體系中的單塔共振頻率值要小,而且垂直向要比水平向更加明顯.

(4)

(1)在節(jié)點數(shù)量為n1的簇中，對于任意兩個節(jié)點i和j,任意時刻的絕對時間對應的時鐘時間有一個上限，對于所有的t∈[begf,begf+1]，存在：

|Fi(t)-Fj(t)|≤(2km1+1)Δ+m1δ+2ρε

(2)如果一個節(jié)點在t時刻對它自身的時鐘進行調(diào)整，則存在一個上限，即|F+(t)-F(t)|≤kΔ。

2 簇間容錯時鐘同步方案

容錯時鐘同步主要分為兩個過程：拓撲建立和時間同步。

2.1 拓撲建立

拓撲建立的方式有很多種，例如基于簇樹混合的分簇方法[9]、自組織分簇休眠方法[10]等等。基于簇樹混合的分簇方法首先進行分簇，確定簇首節(jié)點和簇成員節(jié)點，然后再以基站節(jié)點為根，以樹型結構把所有的簇首節(jié)點連接起來。此方法考慮能耗均衡的問題，需要周期性地建立網(wǎng)絡拓撲結構，通信能耗較高。自組織分簇休眠方法是節(jié)點自行進行分簇，根據(jù)節(jié)點是否被激活判斷是否加入簇中。此方法雖然將節(jié)點是否被激活考慮進來，但是準確率不高，導致節(jié)點的閑置，造成不必要的浪費。文中則采用基于被動分簇的分簇方式進行分簇，由于被動分簇是在其他算法進行泛洪的時候進行，使得通信能耗減少，提高了節(jié)點的利用率。

在被動式分簇[11-14]方案建立簇的過程中，網(wǎng)絡中的節(jié)點可能處于6種不同的狀態(tài)，分別是初始化、預備簇首、簇首、一般簇成員、預備網(wǎng)關和網(wǎng)關。基于被動分簇的層次型網(wǎng)絡結構如圖1所示。

2.2 容錯時鐘同步算法

這部分主要介紹簇間的容錯時鐘同步，被網(wǎng)關節(jié)點連接的簇間節(jié)點彼此之間可以通過廣播的形式進行通信，而且簇間節(jié)點之間時鐘的調(diào)整有一個上限。假設每一個簇中的節(jié)點輪流擔任同步器，通過廣播的方式與其他節(jié)點進行信息交流，此時的同步器同時擔任簇首節(jié)點。假設f為同步的輪數(shù)，每一輪包括R個時間單位，同步器每變換一次，f的值就增加1，并與其他簇的簇首節(jié)點進行信息交換。

圖1 基于被動分簇的層次型網(wǎng)絡

假設對于一個網(wǎng)關節(jié)點連接的任意兩個簇首節(jié)點l1和l2，在進行時鐘同步時,任意時刻的絕對時間對應的時鐘時間滿足被動分簇下時間同步容錯算法(fault-tolerant clock synchronization based on passive clustering，SP)：

|Fl1(t)-Fl2(t)|≤(2km+1)Δ+mδ+2ρε+kΔ

令：x=(2km+1)Δ+mδ+2ρε+kΔ

證明：使用反證法。假設對于任意的簇首節(jié)點l1和l2，當t∈[begf,begf+1]時，有|Fl1(t)-Fl2(t)|>(2km+1)Δ+mδ+2ρε+kΔ。根據(jù)式1和式2，正常同步器之間最大的時鐘差是δ+ε(1+6ρ)。根據(jù)條件1，一個惡意節(jié)點在簇間可以增大的最大時鐘差最多為2kΔ+δ，所以只有當惡意節(jié)點的數(shù)量最少為m1+1時，最大時鐘差距才大于m1(2kΔ+δ)+δ+(1+6ρ)ε。因為惡意節(jié)點的數(shù)量最大為m1，只有當一個惡意節(jié)點作為兩次同步器的時候以上假設才會成立。

所以，有(n1-m1)(k-1)Δ≤(2km1+1)Δ+m1δ+2ρε，顯然之前的假設不成立，得到：

|Fl1(t)-Fl2(t)|≤(2km+1)Δ+mδ+2ρε+kΔ

具體算法描述如下：

(1)當節(jié)點在同步過程中自身時鐘為T時接收到同步消息，如果此時Tf×R+x，節(jié)點就要把信息丟棄。

(2)當節(jié)點在同步過程中自身時鐘為T時接收到同步消息，如果T∈[f×R-x,f×R+x]，就計算時鐘差Θ=f×R-T,并且做以下調(diào)整：如果|Θ|

(3)當節(jié)點沒有接收到同步消息，則改變同步器進行下一輪同步。

3 仿真實驗

文中采用NS-2網(wǎng)絡平臺[15-18]下的水聲傳感網(wǎng)絡模擬器作為容錯算法的仿真工具。仿真過程重點對比HSSD[19]時間同步協(xié)議與文中提出的SR容錯算法的節(jié)點利用率。

仿真實驗中重要討論容錯算法對節(jié)點利用率的影響。采用的部分參數(shù)如下：每2分鐘被同步一次，時鐘漂移率ρ=106，最大時鐘讀數(shù)誤差是0.000 1 s。惡意節(jié)點的數(shù)量在仿真中給出，仿真環(huán)境為水聲環(huán)境。

為了弄清楚在現(xiàn)實中最大時鐘差是如何達到的，做了一系列模擬實驗。用100 000個不同的節(jié)點進行測試，取n=24，圖2顯示了理論和現(xiàn)實的最大時鐘差的差異。實驗結果顯示，無論是理論值還是測試值，最大時鐘差都會隨惡意節(jié)點的增多而增大,而且最大時鐘差的理論值總是比實際測量值要大，即文中提出的最大時鐘差理論上是不會達到的。

圖2 最大時鐘差對比

圖3 算法結果對比

圖3是HSSD算法和SP算法的對比圖。與SP算法不同的是，HSSD算法在進行時間同步時采用單播的形式進行信息交流，在惡意節(jié)點存在的情況下，HSSD算法每一輪的信息量是不變的，這就為時間同步容錯技術帶來阻礙。而SP算法時間同步采用廣播的形式，雖然信息量會隨著惡意節(jié)點碰撞次數(shù)的增多而增多，但這也為容錯技術的實施奠定了基礎，使得在最大時鐘差范圍之內(nèi)的惡意節(jié)點重新恢復正常節(jié)點的身份，提高了整個網(wǎng)絡節(jié)點的利用率。

圖4給出了SP算法和HSSD算法在惡意節(jié)點存在時的節(jié)點利用率。根據(jù)實驗可以得出，當只進行時間同步而不容錯的情況下，節(jié)點利用率呈下降趨勢；而使用SP容錯算法可以使一部分惡意節(jié)點恢復正常節(jié)點身份，大約可以讓4%左右的節(jié)點被重新利用，大大提高了節(jié)點的利用率。

圖4 利用率對比

4 結束語

集群式時間同步容錯技術考慮的是簇內(nèi)節(jié)點之間的時間同步，文中在集群式時間同步容錯的基礎上提出了基于被動分簇的時間同容錯技術。該方案由于使用被動分簇，節(jié)省了開銷。容錯算法針對的是簇間時間同步，相對于只考慮簇內(nèi)時間同步容錯技術，該方案的容錯范圍相對來說比較廣。仿真結果表明，在惡意節(jié)點存在的情況下，時間同步過程中使用SP算法可以提高節(jié)點的利用率。

未來的工作應著力于惡意節(jié)點自身的研究，不斷優(yōu)化算法，在提高節(jié)點利用率的基礎上，改進節(jié)點的能耗的使用，延長節(jié)點的使用壽命。