對等網(wǎng)絡(luò)中向量時鐘管理算法

常興華，陳春鵬

(中國人民解放軍91404部隊，河北秦皇島066000)

0 引言

隨著信息時代的到來，戰(zhàn)爭手段不斷更新，傳感器網(wǎng)絡(luò)在戰(zhàn)爭中發(fā)揮了越來越重要的作用，例如美國的“狼群”系統(tǒng)即是針對電子戰(zhàn)的傳感器網(wǎng)絡(luò)。因此，傳感器網(wǎng)絡(luò)的研究方興未艾［1，2］，為滿足節(jié)點間的協(xié)調(diào)和信息共享，傳感器網(wǎng)絡(luò)的時間同步成為當(dāng)前一個新的研究熱點［3－7］。傳感器網(wǎng)絡(luò)是一種分布式自組織網(wǎng)絡(luò)，特別是在無基站或者利用動態(tài)基站收集數(shù)據(jù)的網(wǎng)絡(luò)中，節(jié)點與節(jié)點之間組成對等(P2P)網(wǎng)絡(luò)，節(jié)點之間進(jìn)行對等數(shù)據(jù)傳輸。P2P網(wǎng)絡(luò)是基于Internet之上構(gòu)建的一個完全位于應(yīng)用層的對等網(wǎng)絡(luò)，節(jié)點間具有很強(qiáng)的對等性、匿名性、開放性和松耦合性等特點。P2P的技術(shù)優(yōu)勢有助于解決傳感器網(wǎng)絡(luò)中的關(guān)鍵技術(shù)問題［8］。通過研究對等網(wǎng)絡(luò)中的時鐘管理方法，解決傳感器網(wǎng)絡(luò)中傳輸消息的因果關(guān)系問題。

1 相關(guān)研究

因果性問題作為分布式系統(tǒng)中的重要問題被廣泛關(guān)注。在分布式系統(tǒng)的時間同步研究中，Lamport首先提出了邏輯時間的思想［9］，但不能捕獲所有并發(fā);Fidge和 Mattern分別提出了向量時鐘的概念［10，11］，但存儲、通信和處理時間的額外耗費隨著系統(tǒng)大小N線性增長;Medal等提出一種降低額外消耗的時鐘策略［12］，但是它僅僅用于判斷消息之間的因果關(guān)系。目前，在許多應(yīng)用中采用了改良的向量時鐘，例如:為了降低額外消耗，Lee等提出增量向量時鐘的技術(shù)，僅僅對消息附加改變的向量時鐘［13］;Anh提出了懶向量時鐘協(xié)議，提供向量時鐘的覆蓋范圍和可擴(kuò)展性之間的折中［14］。同時，在分布式虛擬環(huán)境應(yīng)用中也對時間同步進(jìn)行了深入研究。

2 模型描述

在P2P結(jié)構(gòu)中，每個節(jié)點具有完全的自治性，只能通過網(wǎng)絡(luò)傳輸信息而相互通信。為了使研究簡化，假定通信協(xié)議是面向連接的，并且節(jié)點的拓?fù)浣Y(jié)構(gòu)圖包含所有可能傳輸信息的連接，是靜態(tài)的和已知的。對P2P網(wǎng)絡(luò)進(jìn)行如下建模:對等網(wǎng)絡(luò)G=(V，E，M)是一個互連的有向圖，其中V是通信節(jié)點的集合，E是邊的集合，表示節(jié)點對之間可能的互連，M是節(jié)點間傳輸?shù)南⒌募稀?/p>

2.1 基本定義

定義1:在對等網(wǎng)絡(luò)中，有從節(jié)點u到節(jié)點v的邊，稱為直接連接，記作:(u，v)。如果從節(jié)點u到節(jié)點v存在一條長度大于1的路徑，則稱間接連接，記作:［u，v］。

在對等網(wǎng)絡(luò)中，如果沒有消息發(fā)出，一個節(jié)點中的事件對于其他節(jié)點來說是不可知的。消息的發(fā)送和接收意味著節(jié)點之間的信息流動，并且建立了發(fā)送節(jié)點和接收節(jié)點之間的因果依賴關(guān)系。

定義2:節(jié)點i接收消息m表示消息m被送達(dá)到節(jié)點i。節(jié)點i提交消息m表示消息m被節(jié)點i處理。

在任何節(jié)點，對消息的接收沒有任何限制，但必須保證消息按照因果關(guān)系提交。

定義3:對于消息m1和m2，若它們從同一個節(jié)點發(fā)出m2是m1的下一個消息，若它們從不同的節(jié)點發(fā)出m2是m1提交后的下一個消息，稱m1和m2之間存在直接因果關(guān)系，記作:m1→m2。如果m1→m2，m2→m3，…，mn－1→mn(n＞1，n∈Nat)，則稱m1和mn之間存在因果關(guān)系，記作:m1mn。

可以說，m2是m1的結(jié)果消息，m1是m2的原因消息。很明顯，因果關(guān)系是反自反、反對稱和傳遞的。

定義4:如果m1m2且m2先于m1提交，稱為因果異常發(fā)生，記作:A(m2，m1，v)。

2.2 結(jié)構(gòu)分析

這里，用抽象的觀點研究為什么因果異常可能發(fā)生的問題，如圖1所示。在對等網(wǎng)絡(luò)G=(V，E，M)中，u，v，w∈V，m1，m2∈M，m1→m2，因為邊(w，v)和邊(u，v)不同而網(wǎng)絡(luò)中的消息延遲是可變的和不可預(yù)測的，所以A(m2，m1，v)有可能發(fā)生。

圖1 對等網(wǎng)絡(luò)中因果異常結(jié)構(gòu)分析

在解決問題前，聲明一些有用的假定，這些假定表示使用理論所應(yīng)滿足的條件。

假定1:任一連接都是可靠、有序的，消息的接收順序與發(fā)送順序一致。

網(wǎng)絡(luò)系統(tǒng)首要考慮的是節(jié)點間消息通道的屬性，這樣的通信協(xié)議隨處可見，例如:廣泛使用的TCP/IP。

假定2:從同一節(jié)點發(fā)出的消息必須遵循時間進(jìn)化的遞增順序。

該假定保持同一節(jié)點發(fā)送消息的相對順序，是防止系統(tǒng)運行中發(fā)生因果異常的基本要求。該假定保證了消息有序發(fā)出，是邏輯時鐘推進(jìn)過程中通用的假定［9－11］。

定理1:源自同一節(jié)點的因果消息不會在系統(tǒng)中引發(fā)因果異常。

基于假定1和假定2，該定理明顯成立。

定理 2:對等網(wǎng)絡(luò)G=(V，E，M)，u，v∈V，m1從u發(fā)出，如果因果異常A(m2，m1，v)發(fā)生，則(u，v)∈E且?［u，v］。

定理2描述了因果異常可能發(fā)生的基本結(jié)構(gòu)，即在對等網(wǎng)絡(luò)中，原因消息發(fā)送節(jié)點和因果異常發(fā)生節(jié)點之間同時存在1個直接連接與1個或多個間接連接。

3 向量時鐘管理算法

3.1 基本思想

向量時鐘管理(VCM)算法需要在正常的系統(tǒng)運行前維護(hù)各節(jié)點的初始時鐘信息，并且需要針對各節(jié)點確定可能向其發(fā)送原因消息的節(jié)點集合和可能向其發(fā)送結(jié)果消息的節(jié)點集合。在VCM算法中的每個節(jié)點都維護(hù)著2個隊列，一個是FIFO隊列，該隊列中的消息保持先入先出(FIFO)原則，其中的消息可以直接提交節(jié)點，因此將消息放在FIFO隊列中就意味著將該消息提交節(jié)點了;另一個是Waiting隊列，用于存儲先接收的結(jié)果消息，這些消息在該隊列中等待其后到達(dá)的原因消息。

該算法的基本思想如圖2所示。節(jié)點接收消息后，根據(jù)消息的來源節(jié)點和時標(biāo)，判斷該消息能否立刻提交。當(dāng)從結(jié)果路徑收到消息時，節(jié)點判斷消息的時標(biāo)與其本身向量時鐘之間的關(guān)系，確定是否存在帶有更小時標(biāo)的原因消息仍在傳送過程中。如果是，確定該消息是先于原因消息收到的結(jié)果消息，則將該結(jié)果消息放在Waiting隊列中延遲提交。否則，該消息不可能在該節(jié)點引發(fā)因果異常，可以立即放入FIFO隊列中。如果有消息被放入到FIFO隊列中，則節(jié)點的向量時鐘推進(jìn)，然后根據(jù)新的向量時鐘檢測Waiting隊列中的消息。

圖2 VCM算法的基本思想

3.2 數(shù)據(jù)結(jié)構(gòu)

在VCM算法中，每個消息m帶有時標(biāo)VTm，而每個節(jié)點i維護(hù)如下數(shù)據(jù)結(jié)構(gòu):

①VTi:節(jié)點i的向量時鐘。節(jié)點i提交消息m的更新規(guī)則為:VTi=sup(VTi，VTm)，sup(u，v)=w:w［i］=max(u［i］，v［i］)，?i;

②Joined(i):有邊到節(jié)點i的節(jié)點的集合;

③EffectSet(i):可能發(fā)送結(jié)果消息給i的節(jié)點的集合;

④CauseSet(i):可能發(fā)送原因消息給i的節(jié)點的集合;

⑤d:邏輯時鐘可能推進(jìn)的步長，d＞0。

3.3 算法

定理3:假定分布式系統(tǒng)G=(V，E，M)，當(dāng)發(fā)送自節(jié)點j的消息m在節(jié)點i接收時，若VTm［j］≤VTi［j］，則?m1已經(jīng)被i接收并提交，且mm1。

由于VTi［j］表示節(jié)點i對節(jié)點j進(jìn)展的了解，根據(jù)向量時鐘的更新規(guī)則，該定理明顯成立。

定理4:假定分布式系統(tǒng)G=(V，E，M)，對于m∈M是從節(jié)點j發(fā)送由節(jié)點i接收并提交的消息，m1∈M是從節(jié)點k發(fā)送由節(jié)點i接收并提交的消息，如果因果異常A(m，m1，i)發(fā)生，則j∈EffectSet(i)且當(dāng)m被提交時VTi［k］＜VTm［k］。

定理4表明，如果消息m不是來自結(jié)果節(jié)點，或者對于所有k∈Joined(i)且k≠j VTm［k］≤VTi［k］，則不會引發(fā)因果異常。所以在向量時鐘管理算法中首先判斷消息的發(fā)送節(jié)點，然后在消息被接收后通過比較向量時間來避免因果異常。

向量時鐘管理算法如下:

①當(dāng)節(jié)點i發(fā)送消息m時:

VTi［i］∶ =VTi［i］+d;i的當(dāng)前時鐘附加到m，即，VTm∶ =VTi.

②當(dāng)節(jié)點i接收來自節(jié)點j發(fā)送的消息m時:

If(j?EffectSet(i)∧j?CauseSet(i))

{VTi［i］∶ =VTi［i］+d;VTi∶ =sup(VTi，VTm);將m放入FIFO隊列}

Else

{If(j?EffectSet(i)∨for all(k∈Joined(i)∧k≠j)VTm［k］≤VTi［k］)

{VTi［i］∶ =VTi［i］+d;

VTi∶ =sup(VTi，VTm);

將m放入FIFO隊列;

Detect Waiting Queue.}

Else將(m，j)放入Waiting隊列.

}

Detect Waiting Queue是一個遞歸函數(shù)，用來判斷Waiting隊列中的消息是否可以轉(zhuǎn)移到FIFO隊列中。

4 屬性分析

首先，對一些簡單的網(wǎng)絡(luò)拓?fù)湎逻M(jìn)行算法性能分析，例如:線型、星型樹型和層次三角型。對于這些拓?fù)渚W(wǎng)絡(luò)，在初始化階段，可以得到任何節(jié)點i的EffectSet(i)都是空集。所以在整個系統(tǒng)運行過程中，只要消息到達(dá)就可以提交。在這些簡單拓?fù)涞木W(wǎng)絡(luò)中，VCM的性能與沒有使用時鐘的系統(tǒng)性能相差不多。然后，討論VCM算法的通用屬性。

屬性1:沒有因果異常

很明顯，P2P網(wǎng)絡(luò)使用VCM算法維護(hù)時鐘推進(jìn)，能夠滿足避免因果異常的需求。

定理5:假定分布式系統(tǒng)G=(V，E，M)，對于同一節(jié)點i接收的消息m1，m2∈M，使用向量時鐘管理算法維護(hù)時鐘推進(jìn)，若m1→m2，則VTm1＜VTm2。

定理6:假定分布式系統(tǒng)G=(V，E，M)，對于同一節(jié)點i接收的消息m1，m2∈M，使用向量時鐘管理算法維護(hù)時鐘推進(jìn)，則m1m2iff VTm1＜VTm2。

定理6的結(jié)果與標(biāo)準(zhǔn)向量時鐘協(xié)議正確地捕獲分布式系統(tǒng)事件間的因果關(guān)系的結(jié)論一致［13，14］。

屬性2:沒有死鎖

假定在節(jié)點i發(fā)生死鎖，那么i必然處于無限等待狀態(tài)。但是在VCM算法中如果i處于等待狀態(tài)，它必然是首先接收到結(jié)果消息m2，而需要等待原因消息m1。并且m1m2，則m1必然已經(jīng)被發(fā)送而且正處在向i傳送的過程中。所以基于通信通道可靠的假定，消息m1必定在將來某時刻被接收，這樣節(jié)點i的等待狀態(tài)截至。所以在節(jié)點i不可能發(fā)生死鎖。

屬性3:并行

VCM算法通過開拓消息間的“發(fā)生在先”關(guān)系，沒有因果相關(guān)的消息可以在各個節(jié)點按任意順序提交，在保證消息按因果序提交的前提下最大化了節(jié)點間的并行性。

5 結(jié)束語

在確定P2P網(wǎng)絡(luò)中拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上，對網(wǎng)絡(luò)中可能引發(fā)因果異常的條件進(jìn)行了深入分析，基于愛因斯坦—閔可夫斯基的相對論時空觀，利用向量描述表示消息間因果關(guān)系的時間，將嚴(yán)格的時序關(guān)系弱化，提出了向量時鐘管理算法。該算法采用預(yù)測—延遲技術(shù)，并給每個消息標(biāo)記時標(biāo)，消息間潛在的因果關(guān)系通過比較消息的時標(biāo)與接收節(jié)點的時鐘確定，節(jié)點對其中可能發(fā)生因果異常的消息進(jìn)行監(jiān)控，并對先收到的結(jié)果消息進(jìn)行緩存，直到其所有原因消息都被提交給節(jié)點后才提交該結(jié)果消息。經(jīng)分析驗證，該算法既可以避免因果異常，又可以增加并發(fā)、提高性能。該向量時鐘管理算法的應(yīng)用推廣將是下一步的工作。

［1］閆會芹，何加銘，鄭紫微，等.無線傳感器網(wǎng)絡(luò)模糊邏輯分簇路由協(xié)議［J］.無線電通信技術(shù)，2013，39(6):18－21.

［2］張緒昌，何加銘，謝志軍，等.無線傳感網(wǎng)絡(luò)移動分簇路由策略［J］.無線電通信技術(shù)，2012，38(5):6 －8.

［3］楊遜豪，何加銘，董義旺，等.基于無線傳感器網(wǎng)絡(luò)時間同步MAC協(xié)議研究［J］.無線電通信技術(shù)，2012，38(6):15－19.

［4］戴亞文，李小強(qiáng)，邱 航.結(jié)構(gòu)健康監(jiān)測無線傳感網(wǎng)絡(luò)同步采集研究［J］.無線電工程，2010，40(9):1 －4.

［5］常光強(qiáng)，樊曉平，劉少強(qiáng).基于時間同步的無線傳感器網(wǎng)絡(luò)覆蓋控制優(yōu)化算法［J］.計算機(jī)應(yīng)用研究，2012(1):35－37.

［6］李 立.無線傳感器網(wǎng)絡(luò)時間同步算法研究［D］.北京:清華大學(xué)博士學(xué)位論文，2010.

［7］王義君.面向物聯(lián)網(wǎng)的無線傳感器網(wǎng)絡(luò)時間同步與尋址策略研究［D］.長春:吉林大學(xué)博士學(xué)位論文，2012.

［8］羅 樵，陳 靖，郭一辰，等.大規(guī)模無線傳感器網(wǎng)絡(luò)中基于P2P的路由模型研究［J］.計算機(jī)科學(xué)，2012(2):122－125.

［9］周航軍，張紅雷.一種DVE中通用的因果消息序時間管理分布式中間件［J］.計算機(jī)工程與科學(xué)，2012(3):80－85.

［10］周航軍.分布式大規(guī)模虛擬環(huán)境消息序一致性時間管理技術(shù)研究［D］.長沙:國防科學(xué)技術(shù)大學(xué)博士學(xué)位論文，2011.

［11］付 沙，周航軍.廣域網(wǎng)分布式虛擬環(huán)境中的動態(tài)因果消息序控制方法［J］.計算機(jī)應(yīng)用，2012(4):1 013－1 016.

［12］LAMPORTL.Time，Clocks，and the Ordering of Events in a Distributed System ［J］.Communications of the ACM，1978，21(7):558 －565.

［13］FIDGEC J.Timestamps in Message-passing Systems that Preserve the Partial Ordering［C］∥ in Proc.11th Australian Comp.Sci.Conf.，1988:56 － 66.

［14］MATTERNF.Virtual Time and Global States of Distributed Systems［C］∥in Proceedings of the International Workshop on Parallel and Distributed Algorithms，M.Cosnard et al.Eds.，Amsterdam，Elsevier Science Publishers，1989:215－226.