基于單哈希計(jì)數(shù)布隆的DDS自動發(fā)現(xiàn)算法

樊智勇，張 同，劉哲旭，李伯寧

(1.中國民航大學(xué) 工程訓(xùn)練中心，天津 300300； 2.中國民航大學(xué) 電子信息與自動化學(xué)院，天津 300300)

0 引 言

數(shù)據(jù)分發(fā)服務(wù)DDS(data distribute service)[1,2]是由對象管理組織OMG(object management group)制定的以數(shù)據(jù)為中心的發(fā)布/訂閱通信模型規(guī)范，其采用簡單發(fā)現(xiàn)協(xié)議SDP(simple discovery protocol)來交換Publisher與Subscriber之間的實(shí)體數(shù)據(jù)[3]。在中小型分布式仿真系統(tǒng)得到良好應(yīng)用，但當(dāng)系統(tǒng)規(guī)模較大、數(shù)據(jù)交互較多時，SDP會造成網(wǎng)絡(luò)傳輸量高、內(nèi)存消耗大等問題。針對這一問題，文獻(xiàn)[4]提出SDPBloom(Bloom filter simple discovery protocol)自動發(fā)現(xiàn)算法，通過將端點(diǎn)描述信息存儲到Bloom過濾器中發(fā)送給其他參與者，可以減少網(wǎng)絡(luò)傳輸量與內(nèi)存消耗，但是該算法不支持元素刪除操作，且在運(yùn)算過程中需要較多的哈希函數(shù)，時間消耗成本較大。文獻(xiàn)[5]提出一種單哈希閾值布隆過濾器DDS自動發(fā)現(xiàn)算法，通過調(diào)整閾值θ和判定閾值T進(jìn)行端點(diǎn)信息的查詢匹配，降低了DDS在自動發(fā)現(xiàn)過程中的誤報(bào)以及網(wǎng)絡(luò)傳輸量。文獻(xiàn)[6]將可壓縮布隆過濾器應(yīng)用到DDS自動發(fā)現(xiàn)算法中，在一定程度上降低了網(wǎng)絡(luò)傳輸量與內(nèi)存消耗。文獻(xiàn)[7]提出一種基于分層布隆過濾器的DDS自動發(fā)現(xiàn)算法，通過改進(jìn)原有的鏈?zhǔn)絻Υ娼Y(jié)構(gòu)以及增加節(jié)點(diǎn)刪除操作，有效降低內(nèi)存消耗。

在以上研究基礎(chǔ)上，本文提出一種基于單哈希計(jì)數(shù)布隆過濾器的自動發(fā)現(xiàn)算法(simple discovery protocol_one hash counting Bloom filter，SDP_OHCBF)，該算法通過使用計(jì)數(shù)布隆過濾器[8]來支持元素刪除操作，同時使用單個哈希和取模運(yùn)算來代替標(biāo)準(zhǔn)布隆過濾器中的多個哈希函數(shù)，減少哈希運(yùn)算成本，從而加快DDS的自動發(fā)現(xiàn)過程，實(shí)現(xiàn)對分布式仿真系統(tǒng)的實(shí)時性優(yōu)化。

1 基于DDS的簡單發(fā)現(xiàn)協(xié)議

1.1 DDS

DDS中的域是指在邏輯上將應(yīng)用系統(tǒng)進(jìn)行隔離的通信網(wǎng)絡(luò)，其不受其它應(yīng)用程序的影響，域參與者(domain participant)作為域中數(shù)據(jù)通信互動的進(jìn)入點(diǎn)，主要包括發(fā)布者(publisher)、訂閱者(subscriber)和主題(topic)，它們又包括數(shù)據(jù)寫入者(data writer)和數(shù)據(jù)讀取者(data reader)[9]。只有在同一個域中的參與者，且當(dāng)數(shù)據(jù)的主題名稱、主題類型相同且QoS策略相互兼容時，數(shù)據(jù)寫入者與數(shù)據(jù)讀取者才可以相互通信，其中全局?jǐn)?shù)據(jù)空間GDS主要負(fù)責(zé)完成發(fā)布者與訂閱者、主題與QoS策略的管理與匹配工作，即自動地將發(fā)布者發(fā)布的數(shù)據(jù)有效地傳送給感興趣的訂閱者[10,11]，DDS的通信結(jié)構(gòu)如圖1所示。

圖1 DDS的通信結(jié)構(gòu)

1.2 簡單發(fā)現(xiàn)協(xié)議

DDS通過匹配主題信息以及QoS策略是否兼容，從而將發(fā)布者發(fā)布的信息發(fā)送到訂閱者，這一過程的實(shí)現(xiàn)需要復(fù)雜的內(nèi)部數(shù)據(jù)結(jié)構(gòu)、高效的發(fā)布/訂閱匹配技術(shù)以及自動發(fā)現(xiàn)算法做支撐，其中簡單發(fā)現(xiàn)協(xié)議是DDS的核心技術(shù)，其可以分為兩個階段：簡單參與者發(fā)現(xiàn)協(xié)議階段(simple participant discovery protocol，SPDP)和簡單端點(diǎn)發(fā)現(xiàn)協(xié)議階段(simple endpoint discovery protocol，SEDP)[12]。

簡單參與者發(fā)現(xiàn)階段：主要負(fù)責(zé)完成同一域中的本地參與者與遠(yuǎn)程參與者的自動發(fā)現(xiàn)。本地域參與者通過DDS內(nèi)置的數(shù)據(jù)寫入者將參與者數(shù)據(jù)包發(fā)送給其遠(yuǎn)程域參與者，同時通過內(nèi)置的數(shù)據(jù)讀取者接收其他遠(yuǎn)程參與者的數(shù)據(jù)包，這個參與者數(shù)據(jù)包包含域參與者的唯一標(biāo)識號GUID、地址、端口號以及QoS策略等信息，這些信息通過高效(best effort)組播方式進(jìn)行傳輸。

簡單端點(diǎn)發(fā)現(xiàn)階段：在參與者相互發(fā)現(xiàn)的基礎(chǔ)上，主要負(fù)責(zé)交換本地參與者與遠(yuǎn)程參與者的數(shù)據(jù)寫入者的發(fā)布端點(diǎn)描述信息與數(shù)據(jù)讀取者的訂閱端點(diǎn)描述信息，這些端點(diǎn)描述信息包括設(shè)置的標(biāo)識號GUID、QoS策略等，經(jīng)DDS全局?jǐn)?shù)據(jù)空間進(jìn)行匹配，若匹配成功，則通過可靠(reliable)傳輸方式進(jìn)行端點(diǎn)之間的發(fā)布和訂閱，DDS的簡單發(fā)現(xiàn)協(xié)議過程如圖2所示。

圖2 SDP自動發(fā)現(xiàn)過程

在DDS簡單發(fā)現(xiàn)協(xié)議過程中，每個參與者都需要將自己所有的發(fā)布/訂閱端點(diǎn)信息發(fā)送給域中其他參與者，同時也要接收其他參與者發(fā)送的所有發(fā)布/訂閱端點(diǎn)信息，然而參與者只關(guān)心與自己主題相關(guān)以及QoS策略相互兼容的發(fā)布/訂閱端點(diǎn)信息，這就造成網(wǎng)絡(luò)傳輸量高、內(nèi)存消耗大的問題，故本文提出一種基于單哈希計(jì)數(shù)布隆過濾器的DDS自動發(fā)現(xiàn)算法。

2 OHCBF的設(shè)計(jì)與理論分析

2.1 OHCBF的設(shè)計(jì)

OHCBF將散列映射過程分為兩個階段[15]：

哈希階段：通過使用單哈希函數(shù)h(x)將集合U中的元素xi映射成機(jī)器字W；

取模運(yùn)算階段：通過取模運(yùn)算 |T|(h(x) modmi) 將機(jī)器字W映射成向量組中的目標(biāo)元素T，同時將該分區(qū)內(nèi)相應(yīng)位置的計(jì)數(shù)器加1。

OHCBF的結(jié)構(gòu)如圖3所示，其中假設(shè)k=3，n=3，m1=5，m2=7，m3=11，即3個元素 (x1，x2，x3) 通過單個哈希函數(shù)h(x)映射和取模運(yùn)算存儲到布隆過濾器OHCBF中。當(dāng)存儲元素x1時，首先應(yīng)用哈希函數(shù)h(x)將其映射成機(jī)器字，設(shè)h(x1)=1987， 然后對其進(jìn)行取模運(yùn)算，g1(x1)=h(x1)modm1=2，g2(x1)=h(x1)modm2=3，g3(x1)=h(x1)modm3=4， 則向量組中對應(yīng)分區(qū)的第2位，第3位，第4位計(jì)數(shù)器加1，同理元素x2，x3的插入過程類似。

圖3 OHCBF結(jié)構(gòu)

2.2 OHCBF的理論分析

2.2.1 OHCBF的計(jì)數(shù)器大小設(shè)定

OHCBF通過多占用存儲空間給Bloom過濾器增加了元素刪除操作，但為使占用空間最小，需要計(jì)算出OHCBF中的計(jì)數(shù)器大小[16]。設(shè)OHCBF中的計(jì)數(shù)器大小為j，則第i個計(jì)數(shù)器被映射j次的概率為P(c(i)=j)， 其中

(1)

(2)

(3)

當(dāng)j=16，即計(jì)數(shù)器為4位時，計(jì)數(shù)器會溢出，其概率為

(4)

這個概率值很小，所以當(dāng)計(jì)數(shù)器位數(shù)為4時，對大多數(shù)程序來說足夠使用。

2.2.2 OHCBF的獨(dú)立性約束

在OHCBF中，k個哈希值全都來自于同一個哈希函數(shù)以及取模運(yùn)算，大大減少了哈希計(jì)算時間，但為了使OHCBF和SDPBloom產(chǎn)生相同的誤報(bào)效果，保證哈希函數(shù)的原有性能，需要保證OHCBF中的單哈希函數(shù)在散列過程中生成的k個哈希值和在標(biāo)準(zhǔn)布隆過濾器中由k個哈希函數(shù)映射生成的k個哈希值具有相同的獨(dú)立性，即在OHCBF中，需要保證每個分區(qū)大小為互質(zhì)，這樣才會產(chǎn)生獨(dú)立的取模結(jié)果，更確切地來說，讓gi(x)=h(x)modmi， 1≤i≤k， 如果 (mi，mj)=1， 1≤i

若每個分區(qū)大小不是相對素?cái)?shù)，則在取模運(yùn)算階段會產(chǎn)生一定的相關(guān)性。如在OHCBF中設(shè)其有兩個分區(qū)，其大小分別為m1=4，m2=6，則經(jīng)過哈希映射和取模運(yùn)算后，發(fā)現(xiàn)當(dāng)g2(x)=0或2時，g1(x)=0， 當(dāng)g2(x)=1或3時，g1(x)=1， 即g1(x) 與g2(x) 具有一定的關(guān)聯(lián)性，這將達(dá)不到獨(dú)立的取模效果。

2.2.3 OHCBF的誤報(bào)分析

在標(biāo)準(zhǔn)布隆過濾器中，通過使用k個哈希函數(shù)將集合U中的n個元素映射到m位數(shù)組中時，某一位數(shù)組仍為0的概率為[17]

(5)

(6)

(7)

(8)

(9)

同理可得取模余數(shù)發(fā)生碰撞導(dǎo)致的誤報(bào)率為

(10)

通常情況下由于機(jī)器字的空間范圍要遠(yuǎn)遠(yuǎn)大于位向量，即2L?m， 所以只要機(jī)器字的存儲空間足夠大，則機(jī)器字發(fā)生碰撞的概率會很小，在實(shí)際操作過程中P(A)近似為零，因此，OHCBF的誤報(bào)率近似為

(11)

3 用于數(shù)據(jù)分發(fā)服務(wù)的SDP_OHCBF

3.1 基于SDP_OHCBF的自動發(fā)現(xiàn)過程

本文將OHCBF應(yīng)用到DDS的自動發(fā)現(xiàn)過程中，以遠(yuǎn)程參與者B向本地參與者A訂閱端點(diǎn)信息為例，具體說明DDS的自動發(fā)現(xiàn)過程，如圖4所示。

圖4 SDP_OHCBF的自動發(fā)現(xiàn)過程

在SDP_OHCBF的參與者發(fā)現(xiàn)階段，本地參與者A和遠(yuǎn)程參與者B創(chuàng)建OHCBF向量；將端口變量數(shù)據(jù)的端點(diǎn)描述信息經(jīng)過單個哈希函數(shù)和取模運(yùn)算映射到k個不均勻分區(qū)的mi(1≤i≤k) 位OHCBF中，其中k個位置的位向量計(jì)數(shù)器加1，如果該位置被多次映射，則進(jìn)行累加，將自己所包含的端點(diǎn)描述信息存儲到OHCBF向量中；本地參與者A的端點(diǎn)描述信息通過參與者數(shù)據(jù)包一起發(fā)送給遠(yuǎn)程參與者B，用來宣布本身存在信息，同時接收遠(yuǎn)程參與者B發(fā)送的包含端點(diǎn)描述信息的OHCBF向量，本文使用主題名稱作為參與者端點(diǎn)描述信息的唯一標(biāo)識符，從而進(jìn)行端點(diǎn)信息匹配；當(dāng)遠(yuǎn)程參與者B獲取到包含本地參與者A端點(diǎn)描述信息的OHCBF向量時，通過單個哈希函數(shù)和取模運(yùn)算進(jìn)行數(shù)據(jù)查詢，判斷k個位置的位向量是否為非0，若為非0，判斷該元素在本地參與者A中，則將OHCBF添加到本地信息庫中，進(jìn)入到端點(diǎn)發(fā)現(xiàn)階段，否則忽略該信息；同理，當(dāng)本地參與者A獲得遠(yuǎn)程參與者B的信息時，執(zhí)行相同步驟。至此，本地參與者A與遠(yuǎn)程參與者B交換了彼此的端點(diǎn)描述信息并對其進(jìn)行存儲，完成了參與者發(fā)現(xiàn)過程。

在端點(diǎn)發(fā)現(xiàn)階段，遠(yuǎn)程參與者B通過對存儲的本地參與者A端點(diǎn)描述信息的OHCBF向量進(jìn)行查詢，這一階段通過參與者創(chuàng)建的數(shù)據(jù)寫入者與數(shù)據(jù)讀取者分別進(jìn)行匹配，遠(yuǎn)程參與者B將獲得的本地參與者A發(fā)布的端點(diǎn)描述信息與自身需要訂閱的端點(diǎn)信息進(jìn)行匹配，若匹配成功，則向本地參與者A發(fā)送訂閱請求；本地參與者A將被訂閱的包含主題以及QoS服務(wù)質(zhì)量的端點(diǎn)具體信息發(fā)送到遠(yuǎn)程參與者B進(jìn)行再匹配；若匹配成功，則遠(yuǎn)程參與者B的訂閱端點(diǎn)與本地參與者A的發(fā)布端點(diǎn)建立數(shù)據(jù)通信，若匹配不成功，則發(fā)生誤報(bào)，向遠(yuǎn)程參與者B的訂閱端點(diǎn)發(fā)送“本地沒有相關(guān)端點(diǎn)信息”。通過此種方式改變了DDS參與者之間的對話方式，即不需將自己擁有的所有信息全部發(fā)送給其他參與者，只需告訴其他參與者自己擁有哪些信息即可。

3.2 基于SDP_OHCBF的性能分析

將端點(diǎn)描述信息存儲在OHCBF向量中，設(shè)置主題名稱進(jìn)行參與者之間的通信，假定域中參與者個數(shù)為P，其包含的端點(diǎn)總數(shù)為E，默認(rèn)在每個參與者中擁有同樣多的端點(diǎn)數(shù)，即每個參與者均有E/P個端點(diǎn)，且不考慮心跳機(jī)制。定義ME(match endpoint)為Bloom過濾器中每個參與者匹配的端點(diǎn)數(shù)與端點(diǎn)總數(shù)的平均比率，MEBF為SDPBloom中匹配的端點(diǎn)總數(shù)，MEOHCBF為SDP_OHCBF中匹配的端點(diǎn)總數(shù)，MEBF和MEOHCBF決定了參與者在端點(diǎn)發(fā)現(xiàn)階段需要發(fā)送和接收的端點(diǎn)信息數(shù)。由于在SDP中每個參與者需要向其他參與者發(fā)送自己所有的發(fā)布/訂閱端點(diǎn)信息，所以其發(fā)送的消息數(shù)為E，而在SDPBloom與SDP_OHCBF中，每個參與者通過將端點(diǎn)描述信息存儲到BF和OHCBF向量中，可以篩選掉因主題不匹配的端點(diǎn)信息，所以E遠(yuǎn)大于MEBF和MEOHCBF。

在不使用多播情況下，SDP、SDPBloom、SDP_OHCBF這3種算法中每一個參與者需要發(fā)送和接收的端點(diǎn)消息為

(12)

(13)

(14)

在SDP過程中，每一個參與者需要存儲域中其他參與者的所有端點(diǎn)信息，而在SDPBloom、SDP_OHCBF中，每一個參與者不僅需要保存本身自帶的端點(diǎn)信息和在參與者發(fā)現(xiàn)階段附帶的過濾器向量信息，還要存儲通過布隆過濾器向量匹配上的端點(diǎn)信息，所以在這3種自動發(fā)現(xiàn)算法中，每個參與者所占用的消耗內(nèi)存為

MSDP=E

(15)

(16)

(17)

由式(15)～式(17)可知，SDPBloom、SDP_OHCBF與SDP相比，通過使用布隆過濾器可以大大減少自動發(fā)現(xiàn)過程中的網(wǎng)絡(luò)傳輸量與內(nèi)存消耗，同時SDPBloom和SDP_OHCBF的網(wǎng)絡(luò)傳輸量與消耗內(nèi)存與端點(diǎn)匹配數(shù)相關(guān)。

4 實(shí)驗(yàn)驗(yàn)證與結(jié)果分析

基于RTI_DDS的分布式仿真平臺具有10個仿真節(jié)點(diǎn)，同時含有利用Matlab/Simulink、AMESim、Flightsim、C/C++等專業(yè)仿真軟件建立的仿真模型。在該平臺上將本文提出的改進(jìn)算法SDP_OHCBF與SDP、SDPBloom算法在網(wǎng)絡(luò)傳輸量、內(nèi)存消耗、誤報(bào)率以及查詢時間4個方面進(jìn)行仿真實(shí)驗(yàn)驗(yàn)證。

4.1 網(wǎng)絡(luò)傳輸量與內(nèi)存消耗

在本實(shí)驗(yàn)中，一個仿真模型作為一個參與者，一共有P個參與者，每個仿真模型有100個模型端口變量(端點(diǎn))，一共有100*P個端點(diǎn)。每個端點(diǎn)信息為6000字節(jié)，端點(diǎn)描述信息為4字節(jié)，在SDPBloom與SDP_OHCBF中，用來存儲端點(diǎn)描述信息的布隆過濾器位向量為64字節(jié)。

在端點(diǎn)發(fā)現(xiàn)階段，當(dāng)端點(diǎn)匹配率為ME=0.1、ME=0.2、ME=0.5時，SDP、SDPBloom和SDP_OHCBF的網(wǎng)絡(luò)傳輸量隨參與者數(shù)量的變化情況如圖5所示。

圖5 網(wǎng)絡(luò)傳輸量

隨著參與者數(shù)量增加，端點(diǎn)數(shù)也增加，SDP、SDPBloom和SDP_OHCBF的內(nèi)存消耗也隨著參與者數(shù)量增加而發(fā)生變化，圖6與圖7分別為匹配端點(diǎn)率為ME=0.1、ME=0.2的內(nèi)存消耗變化情況。

圖6 ME=0.1的內(nèi)存消耗

圖7 ME=0.2的內(nèi)存消耗

從圖5～圖7可以看出：

(1)SDP在整個自動發(fā)現(xiàn)過程中的網(wǎng)絡(luò)傳輸量較SDPBloom和SDP_OHCBF大，且發(fā)送的信息數(shù)不隨端點(diǎn)匹配率ME的變化而變化，所以SDP需要更大的消耗內(nèi)存來存儲遠(yuǎn)程端點(diǎn)信息；當(dāng)端點(diǎn)匹配率越小，SDPBloom和SDP_OHCBF的優(yōu)勢就越明顯；

(2)無論端點(diǎn)匹配率ME如何變化，SDPBloom和SDP_OHCBF的內(nèi)存消耗都近似相同且遠(yuǎn)遠(yuǎn)小于SDP，說明通過使用布隆過濾器可以大大減少端點(diǎn)存儲信息，減少不必要的內(nèi)存消耗。

4.2 誤報(bào)率與查詢時間

本實(shí)驗(yàn)負(fù)責(zé)對SDPBloom與SDP_OHCBF的誤報(bào)率與查詢時間進(jìn)行仿真驗(yàn)證，與以上實(shí)驗(yàn)條件相同，每個參與者都有100個端點(diǎn)描述信息映射到SDPBloom和SDP_OHCBF向量中，每個端點(diǎn)描述信息為4字節(jié)。令n=100，k=3，mt為SDPBloom的位向量長度，ms為SDP_OHCBF的位向量長度，其中SDP_OHCBF的哈希函數(shù)設(shè)置為MD2，SDPBloom的哈希函數(shù)設(shè)置為MD5、MD2和SHA-1，表1為SDPBloom和SDP_OHCBF的誤報(bào)率。

由表1可得，隨著布隆過濾器位向量m的變化，SDP_OHCBF的誤報(bào)率與SDPBloom的誤報(bào)率近似相等，且隨著m逐漸增大，SDPBloom與SDP_OHCBF的誤報(bào)率越來越小。

表1 SDPBloom和SDP_OHCBF的誤報(bào)率

當(dāng)SDPBloom與SDP_OHCBF查詢100個成員元素，端點(diǎn)匹配率ME=0.5時，隨著布隆過濾器位向量m長度變化，其所需查詢時間如圖8所示。

圖8 隨m位向量變化所需查詢時間

當(dāng)SDPBloom位向量長度m為1000，SDP_OHCBF位向量長度m為1009時，隨著100個元素中端點(diǎn)匹配率ME從0到1的變化，SDPBloom與SDP_OHCBF所需查詢時間對比如圖9所示。

圖9 隨端點(diǎn)匹配率ME變化所需查詢時間

由圖8、圖9可以看出，無論是隨著布隆過濾器的位向量大小變化還是查詢成員與非成員的比例變化，SDP_OHCBF與SDPBloom相比，都花費(fèi)較少的哈希運(yùn)算時間，因此SDP_OHCBF具有更好的實(shí)時性，這大大提高了DDS自動發(fā)布/訂閱的過程。

5 結(jié)束語

本文在對DDS的自動發(fā)現(xiàn)算法SDP以及常規(guī)改進(jìn)算法SDPBloom的研究基礎(chǔ)上，提出一種DDS自動發(fā)現(xiàn)算法SDP_OHCBF，通過將標(biāo)準(zhǔn)布隆過濾器升級為計(jì)數(shù)布隆過濾器，使之無需重新構(gòu)建布隆過濾器以支持元素刪除操作，同時使用單個哈希函數(shù)以及簡單取模運(yùn)算代替標(biāo)準(zhǔn)布隆過濾器中的多個哈希運(yùn)算。通過仿真實(shí)驗(yàn)驗(yàn)證，SDP_OHCBF與SDPBloom在網(wǎng)絡(luò)傳輸量、內(nèi)存消耗以及誤報(bào)率基本保持一致的情況下，大大減少了哈希運(yùn)算時間，提高了DDS自動發(fā)現(xiàn)過程的實(shí)時性。該算法在多電飛機(jī)分布式仿真系統(tǒng)中得到良好應(yīng)用，加快了機(jī)電系統(tǒng)模型分布式仿真的數(shù)據(jù)交互過程，為接下來優(yōu)化飛機(jī)機(jī)電系統(tǒng)分布式協(xié)同仿真提供了良好的實(shí)時性。但是該算法目前沒有將QoS考慮進(jìn)去，無法預(yù)先在參與者發(fā)現(xiàn)階段完成對QoS的判斷，接下來將深入研究如何在SDP_OHCBF的基礎(chǔ)上加上對QoS的判斷，進(jìn)一步提高其應(yīng)用價(jià)值。