常興華，陳春鵬

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

0 引言

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

1 相關(guān)研究

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

2 模型描述

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

2.1 基本定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 向量時(shí)鐘管理算法

3.1 基本思想

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

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

圖2 VCM算法的基本思想

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

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

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

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

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

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

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

3.3 算法

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

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

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

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

向量時(shí)鐘管理算法如下:

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

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

②當(dāng)節(jié)點(diǎn)i接收來(lái)自節(jié)點(diǎn)j發(fā)送的消息m時(shí):

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

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

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隊(duì)列;

Detect Waiting Queue.}

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

}

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

4 屬性分析

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

屬性1:沒(méi)有因果異常

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

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

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

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

屬性2:沒(méi)有死鎖

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

屬性3:并行

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

5 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

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

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

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

［11］付 沙，周航軍.廣域網(wǎng)分布式虛擬環(huán)境中的動(dòng)態(tài)因果消息序控制方法［J］.計(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.