基于自組織算法的發(fā)布/訂閱系統(tǒng)的研究

董 飚

(南京工業(yè)職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)與軟件學(xué)院，江蘇 南京 210023)

基于自組織算法的發(fā)布/訂閱系統(tǒng)的研究

董 飚

(南京工業(yè)職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)與軟件學(xué)院，江蘇 南京 210023)

通過(guò)重組織覆蓋網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，提出了一種高效的發(fā)布/訂閱系統(tǒng)。自組織算法把匹配相同事件的事件代理直接相連來(lái)實(shí)現(xiàn)重組織拓?fù)浣Y(jié)構(gòu)。結(jié)果表明，由于減少了事件發(fā)布過(guò)程中的事件代理的數(shù)量，從而降低了系統(tǒng)開(kāi)銷(xiāo)。

發(fā)布/訂閱；覆蓋網(wǎng)絡(luò)；自組織

目前，許多分布式系統(tǒng)采用基于發(fā)布/訂閱(Publish/Subscribe，簡(jiǎn)稱(chēng)P/S)的架構(gòu)。發(fā)布者是信息的生產(chǎn)者，訂閱者是信息的消費(fèi)者。事件是信息的載體，發(fā)布者產(chǎn)生事件，訂閱者消費(fèi)事件，他們通過(guò)訂閱語(yǔ)言描述消費(fèi)的事件類(lèi)型。發(fā)布者和訂閱者通常分布在網(wǎng)絡(luò)不同的節(jié)點(diǎn)上，因此P/S系統(tǒng)本質(zhì)上是由事件代理框架構(gòu)成的網(wǎng)絡(luò)，事件代理負(fù)責(zé)事件的匹配和路由。P/S系統(tǒng)如圖1所示。

圖1 發(fā)布/訂閱系統(tǒng)模型

圖1中Pi表示發(fā)布者，Ci表示訂閱者，Bi表示訂閱者，虛線矩形表示事件通知服務(wù)。事件通知服務(wù)充當(dāng)發(fā)布者和訂閱者間的媒介，由一組互連的事件代理組成。相鄰的事件代理之間通過(guò)接口(或稱(chēng)鏈路)相連，和發(fā)布者相連的事件代理稱(chēng)為發(fā)布結(jié)點(diǎn)，和訂閱者相連的事件代理稱(chēng)為訂閱結(jié)點(diǎn)，其它路由器稱(chēng)為內(nèi)部結(jié)點(diǎn)。發(fā)布者從它的發(fā)布結(jié)點(diǎn)發(fā)布事件，訂閱結(jié)點(diǎn)把通告?zhèn)鬟f給訂閱者。圖中Bi分別表示發(fā)布結(jié)點(diǎn)、訂閱結(jié)點(diǎn)和內(nèi)部結(jié)點(diǎn)，通常，不予區(qū)分，均稱(chēng)之為代理。

P/S系統(tǒng)可以分為兩大類(lèi)：基于主題的P/S系統(tǒng)，如TIB/Rendezvous，SCRIBE和BAYEUX等；基于內(nèi)容的P/S系統(tǒng)，如SIENA，JEDI，HERMERS，Gryphon和REBECA等[1-3]?；谥黝}的P/S系統(tǒng)通過(guò)一組預(yù)先定義的主題來(lái)交換信息，每一個(gè)主題代表了不同的多對(duì)多的邏輯通道。基于內(nèi)容的P/S系統(tǒng)更適合靈活地訂閱相關(guān)的信息，每個(gè)信息項(xiàng)的組合可以看成一個(gè)動(dòng)態(tài)邏輯通道。由于這種系統(tǒng)要建立和維護(hù)數(shù)量巨大的組播樹(shù)，因此，實(shí)現(xiàn)高效的基于組播樹(shù)的事件傳播是不可行的[4]。目前，基于主題和基于內(nèi)容的P/S系統(tǒng)都是基于靜態(tài)環(huán)境下的覆蓋網(wǎng)絡(luò)，主要考慮如何設(shè)計(jì)事件分發(fā)算法，避免在事件分發(fā)過(guò)程中出現(xiàn)泛洪現(xiàn)象[5]。與上述系統(tǒng)相比，本文提出了在動(dòng)態(tài)重組織覆蓋網(wǎng)絡(luò)結(jié)構(gòu)環(huán)境下的一個(gè)協(xié)同、互補(bǔ)的自組織算法，同時(shí)把P/S系統(tǒng)重組織的開(kāi)銷(xiāo)控制在一個(gè)合理的范圍，具體考慮三方面的內(nèi)容：

ZK13-02-03

(1) 定義兩個(gè)代理之間的相似度；

(2) 只利用本地代理中的信息，自組織覆蓋網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)；

(3) 在不破壞初始網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特性，如帶寬、網(wǎng)絡(luò)延時(shí)等度量的同時(shí)，把P/S系統(tǒng)重組織的開(kāi)銷(xiāo)控制在一個(gè)合理的范圍。

1 自組織覆蓋網(wǎng)絡(luò)

本文重組織覆蓋網(wǎng)絡(luò)的基本思想是：在覆蓋網(wǎng)絡(luò)中創(chuàng)建代理聚集。創(chuàng)建代理聚集的依據(jù)是在最近的一段未來(lái)時(shí)間，代理聚集中的代理有相同的訂閱目標(biāo)。在這種情況下，一個(gè)事件沿一條路徑到各代理，而不是沿多條路徑來(lái)分發(fā)事件到目標(biāo)代理。

圖2所示為P1發(fā)布事件e的過(guò)程，箭頭表示事件e在覆蓋網(wǎng)絡(luò)中發(fā)布的方向，有兩個(gè)訂閱者B9和B5訂閱事件e。在最小開(kāi)銷(xiāo)的情況下，事件e到達(dá)B9和B5共需6跳。

圖2 P1發(fā)布事件e到B9和B5

圖3所示為假設(shè)B9和B5屬于同一個(gè)代理聚集，B9和B5直接相連，事件e到達(dá)B9和B5只需3跳。

圖3 P1由代理聚集發(fā)布事件e

定義1(事件) 事件e由一組屬性集合{a1，…，an}組成。其中，屬性是一個(gè)三元組，type指屬性的數(shù)據(jù)類(lèi)型，其屬于一組預(yù)先規(guī)定的原始數(shù)據(jù)類(lèi)型，可以是一般的編程語(yǔ)言所支持的類(lèi)型，如int，bool，float，string等簡(jiǎn)單數(shù)據(jù)類(lèi)型，或者是由簡(jiǎn)單數(shù)據(jù)類(lèi)型構(gòu)成的復(fù)合數(shù)據(jù)類(lèi)型，如數(shù)組、集合等。name是屬性的名稱(chēng)，它是一個(gè)string類(lèi)型。value是屬性的值，它的值域就是該屬性的數(shù)據(jù)類(lèi)型所能表示的范圍。

定義2(相似度) 對(duì)于一段給定的時(shí)間，設(shè)mi是與代理Bi匹配的最后Qi個(gè)事件的一組屬性的集合，代理Bi和Bj之間的相似度：

其中SBj是存儲(chǔ)在代理Bj上的訂閱的集合，M(e，s)表示事件e與訂閱s匹配。

ai，j是一個(gè)概率，表明一個(gè)事件如果與代理Bi的訂閱相匹配，那么，該事件與代理Bj的訂閱匹配的概率，反之，也成立。當(dāng)ai，j接近1時(shí)，表明幾乎所有最后的Qi個(gè)事件同時(shí)與代理Bj和Bj的訂閱相匹配。如果ai，j=0，表明代理Bj和Bj是斷開(kāi)的，或者最后Qi個(gè)與代理Bj的訂閱匹配的事件不能與代理Bj的訂閱匹配。ai，j只與已匹配的過(guò)去的事件有相，并且隨著事件和訂閱的變化而動(dòng)態(tài)調(diào)整，不需要先期的知識(shí)。

2 自組織算法

代理B的興趣域是B的訂閱表中所有訂閱的并集，記為Z(B)。與鏈接l相連接的所有代理的興趣域的并集，稱(chēng)為鏈接l的興趣域，記為Z(l)。在P/S系統(tǒng)中，當(dāng)代理Bi通過(guò)鏈接li，j收到一個(gè)事件e后，完成兩項(xiàng)工作：

(1) 把事件e與其訂閱表匹配。

(2) 如果e與Z(li，k)(k≠j)匹配，通過(guò)所有l(wèi)i，k(k≠j)向前分發(fā)事件e，這確保事件e只經(jīng)過(guò)一些能引導(dǎo)該事件到達(dá)訂閱該事件的代理的鏈接。

自組織算法的目標(biāo)是：設(shè)在覆蓋網(wǎng)絡(luò)中兩個(gè)代理Bi和Bl，它們之間沒(méi)有直接相連。若Bi到Bl的路徑上存在一條鏈接lp，q，使得ai，l>ap，q，則在Bi和Bl之間建立一條鏈接li，j，而且，為了保持覆蓋網(wǎng)絡(luò)是無(wú)環(huán)的結(jié)構(gòu)，自組織算法必須斷開(kāi)鏈接lp，q。自組織算法分為4個(gè)階段：觸發(fā)階段、發(fā)現(xiàn)代理階段、斷開(kāi)鏈接階段和修復(fù)覆蓋網(wǎng)絡(luò)階段。

(1) 觸發(fā)階段。對(duì)于代理Bi的每一條鏈接，激活條件AC(Bi，j)：ai，j(mi)>ai，j，其中ai，j(mi)是mi中與Z(li，j)匹配的事件數(shù)除以Q。用來(lái)計(jì)算ai，j的集合Z(Bj)是Z(li，j)的子集，能被直接推導(dǎo)，不需要在Bi和Bj之間互換任何消息。代理B每接收到δ個(gè)事件，自組織算法被觸發(fā)執(zhí)行，代理B檢測(cè)AC(Bi，j)，如果AC(Bi，j)=false，那么，自組織算法結(jié)束運(yùn)行；否則，代理執(zhí)行自組織算法的代理發(fā)現(xiàn)過(guò)程。

(2) 發(fā)現(xiàn)代理階段。設(shè)元組(broker_id，weight)，令HS(Bx，By)=<(Bx,0)(Bx+1),w(lx,x+1)),…,(By,w(ly-1,y))>表示連接代理Bx和By的一個(gè)跳序列。代理Bi通過(guò)它的一條鏈接發(fā)送請(qǐng)求消息DREQ，該消息包括mi的一個(gè)HS。由Bi發(fā)出的包括DREQ消息的跳序列的初始值是{(Bi，0)}。DREQ消息隨著mi的大小和HS的長(zhǎng)度增大。

當(dāng)一個(gè)代理Bj在它的一條鏈接lk，j上接收到DREQ，Bj完成三件工作：①計(jì)算ai，j；②在HS中加入(Bj，w(lj，k))；③計(jì)算向前分發(fā)事件的條件FP：?lj，h≠lj，k：ai，j(mi)>ai，j。如果FP為真，表示鏈接lj，h后存在代理，該代理與Bi的相似度大于ai，j，那么，代理Bj把DREQ發(fā)送到鏈接lj，h。如果不存在鏈接使得FP為真，那么，代理Bj沿著HS的路徑返回給Bi一個(gè)回答消息DREP。

(3) 斷開(kāi)鏈接階段。這一階段的任務(wù)是選擇一條用來(lái)在修復(fù)覆蓋網(wǎng)絡(luò)階段斷開(kāi)的鏈接ltd。這階段的工作過(guò)程如下：設(shè)DREP是沿著li，j發(fā)出的對(duì)DREQ消息的回答，該回答消息包含Bl，這里的Bl與Bi有最大的相似度，DREP存儲(chǔ)HS(Bi，Bl)。lnew表示在Bi和Bl之間創(chuàng)建的一條鏈接。如果all=0∧ali=0；不能創(chuàng)建鏈接lnew，因?yàn)锽i和Bl間沒(méi)有可用的鏈接。否則，有兩種情況：①all>0∧ali>0：表示為Bi和Bl之間有可用的鏈接，因此，可以在它們之間建立新的鏈接。②all=0∧ali>0(或者all>0∧ali=0)；ltd是Bl-1與Bl之間的鏈接(ltd是Bi與Bi+1之間的鏈接)。

(4) 修復(fù)覆蓋網(wǎng)絡(luò)階段。設(shè)lnew=li，j，ltd=lp，q，為了避免網(wǎng)絡(luò)被劃分，或者變成有環(huán)的結(jié)構(gòu)，必須確保在斷開(kāi)ltd時(shí)，HS(Bi，Bl)中的其他鏈接不被斷開(kāi)。我們用鎖機(jī)制來(lái)實(shí)現(xiàn)：Bi沿著朝向Bl的路徑上的代理發(fā)一條LOCK消息，這條路徑上的代理B執(zhí)行下面的算法：

① 當(dāng)通過(guò)鏈接l接到一條LOCK消息。分三種情況：如果l沒(méi)有鎖，并且B≠Bl，則鎖住l，并且把LOCK消息分發(fā)到指向Bl的路徑上的下一個(gè)代理。如果l沒(méi)有鎖，并且B=Bl，則鎖住l，并且把ACK消息分發(fā)到指向Bl的路徑上的下一個(gè)代理。如果l被鎖，或者Bl經(jīng)過(guò)HS(Bi，Bl)不再可達(dá)，則向Bi發(fā)送NACK消息。

② 當(dāng)接收到一條ACK消息。B向指向Bl的路徑上的下一個(gè)代理發(fā)送ACK消息。

③ 當(dāng)接收到一條NACK消息。分兩種情況：如果B≠Bl，在這條鏈接上移除LOCK，并且向指向Bl的路徑上的下一個(gè)代理發(fā)送NACK消息。如果B=Bl，則停止自組織算法。

3 仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)估計(jì)自組織算法的性能和可用性，我們基于SIENA實(shí)現(xiàn)了自組織算法。事件的匹配率EP定義為一個(gè)事件與代理匹配的概率。實(shí)驗(yàn)中事件服從均勻分布，覆蓋網(wǎng)絡(luò)中有300個(gè)代理，設(shè)置五個(gè)場(chǎng)景Si(EP)(1≤i≤5)，分別為S1(1.7%)，S2(5.4)，S3(10.1)，S4(24.5)，S5(50.9)。圖4所示為在事件服從均勻分布的情況下，覆蓋網(wǎng)絡(luò)中代理重組織的數(shù)量。

圖4 在事件服從均勻分布的情況下，代理重組織的數(shù)量

從圖4可見(jiàn)，重組織代理的數(shù)量被控制在可接受的范圍，表明了自組織算法的可用性。

4 結(jié)論

高效率的P/S系統(tǒng)是目前重要的研究方向，自組織算法通過(guò)衡量代理之間的相似度，只利用本地代理中的信息，在不破壞初始網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特性的前提下，把P/S系統(tǒng)自組織的開(kāi)銷(xiāo)控制在一個(gè)合理的范圍。

[1]Jokela P，Zahemszky A，Esteve Rothenberg C，et al.LIPSIN：line speed publish/subscribe inter-networking[C]//ACM SIGCOMM Computer Communication Review.ACM，2009，39(4)：195-206.

[2]Fotiou N，Trossen D，Polyzos G C.Illustrating a publish-subscribe internet architecture[J].Telecommunication Systems，2012，51(4)：233-245.

[3]Lagutin D，Visala K，Tarkoma S.Publish/Subscribe for Internet：PSIRP Perspective[C]//Future Internet Assembly.2010：75-84.

[4]董飚，陳金輝，阮峰，等.基于P2P網(wǎng)絡(luò)的大規(guī)模發(fā)布/訂閱系統(tǒng)[J].信息與控制，2009，38(5)：513-518.

[5]鄭嘯，羅軍舟，曹玖新，等.基于發(fā)布/訂閱機(jī)制的Web服務(wù)QoS信息分發(fā)模型[J].計(jì)算機(jī)研究與發(fā)展，2010(06)：1088-1097.

(責(zé)任編輯 周曉蕓)

ResearchonPublish/SubscribeSystemBasedonSelf-OrganizingAlgorithm

DONGBiao

(NanjingInstituteofIndustryTechnology，Nanjing210023，China)

In this paper we propose an efficient publish/subscribe system by reorganizing the overlay network topology.This reorganization is done through a self-organizing algorithm executed by event brokers whose aim is to directly connect，through overlay links，pairs of brokers matching same events.The results show that the number of brokers involved in an event dissemination decreases，thus，reducing its cost.

publish/subscribe； overlay networks； self-organization

2013-11-10

董飚(1969-)，男，南京工業(yè)職業(yè)技術(shù)學(xué)院副教授，工學(xué)博士，研究方向：分布式計(jì)算，傳感器網(wǎng)絡(luò)軟件技術(shù)。

TP393.2

A

1671-4644(2014)02-0036-04