樊智勇 騰 達(dá) 劉哲旭

1(中國(guó)民航大學(xué)工程技術(shù)訓(xùn)練中心 天津 300300) 2(中國(guó)民航大學(xué)電子信息與自動(dòng)化學(xué)院 天津 300300)

0 引 言

數(shù)據(jù)分發(fā)服務(wù)DDS是一種高性能的中間件，能夠以較小的開銷實(shí)現(xiàn)可預(yù)測(cè)的數(shù)據(jù)分發(fā)。對(duì)象管理組織(Object Management Group, OMG)先后頒布了Version1.0、Version1.1和Version1.2規(guī)范[1-3]。該規(guī)范定義了一個(gè)與用戶具體使用的平臺(tái)、語言、所處位置都不相關(guān)且可擴(kuò)展的基礎(chǔ)服務(wù)模型[4]。DDS采用以數(shù)據(jù)為中心的發(fā)布/訂閱通信模式，使分布式系統(tǒng)能夠?qū)崿F(xiàn)數(shù)據(jù)高效、可靠的發(fā)布與訂閱[5]。目前，DDS已經(jīng)被成功應(yīng)用于海軍作戰(zhàn)管理、空中交通管制和船舶等系統(tǒng)[6]。

針對(duì)DDS自動(dòng)發(fā)現(xiàn)過程，RTI(Real-time Innovations)提出了基于簡(jiǎn)單發(fā)現(xiàn)協(xié)議的自動(dòng)發(fā)現(xiàn)算法SDP_ADA(Simple discovery protocol automatic discovery algorithm)[7]。該算法在中小型實(shí)時(shí)系統(tǒng)中取得了良好的效果，但當(dāng)系統(tǒng)的規(guī)模增大時(shí)，大量的數(shù)據(jù)需要頻繁地交換，會(huì)產(chǎn)生網(wǎng)絡(luò)數(shù)據(jù)傳輸量和內(nèi)存消耗較高的問題。文獻(xiàn)[8]將DDS簡(jiǎn)單發(fā)現(xiàn)協(xié)議和標(biāo)準(zhǔn)布隆過濾器Bloom結(jié)合，提出了一種自動(dòng)發(fā)現(xiàn)算法SDPBloom。在自動(dòng)發(fā)現(xiàn)過程中，SDPBloom通過Bloom存儲(chǔ)端點(diǎn)描述信息，有效地解決了 SDP_ADA中存在的高內(nèi)存消耗和高網(wǎng)絡(luò)數(shù)據(jù)傳輸量等問題，增強(qiáng)了DDS的可拓展性。但是SDPBloom的實(shí)現(xiàn)需要大量的哈希函數(shù)運(yùn)算，導(dǎo)致CPU資源消耗過多，并在分布式系統(tǒng)中產(chǎn)生了一定的延遲。為解決這一問題，本文提出了一種基于單哈希多維布隆過濾器的自動(dòng)發(fā)現(xiàn)算法。該算法中的OMBF通過一個(gè)哈希函數(shù)和取模運(yùn)算代替SDPBloom中多個(gè)哈希函數(shù)，降低了參與者端點(diǎn)匹配過程的計(jì)算量。

1 DDS簡(jiǎn)單發(fā)現(xiàn)協(xié)議

域是一個(gè)虛擬網(wǎng)絡(luò)概念，它有助于隔離和優(yōu)化分布式應(yīng)用程序之間的通信。只有同一個(gè)域中的域參與者才能相互通信[10]。域參與者由發(fā)布者和訂閱者組成，每個(gè)發(fā)布者和訂閱者分別管理一個(gè)或多個(gè)數(shù)據(jù)寫入者和數(shù)據(jù)讀取者。本文將數(shù)據(jù)寫入者和數(shù)據(jù)讀取者統(tǒng)稱為端點(diǎn)。只有數(shù)據(jù)寫入者和數(shù)據(jù)讀取者具有相同的主題時(shí)，域參與者才能建立通信。域參與者之間的數(shù)據(jù)傳輸通過自動(dòng)發(fā)現(xiàn)協(xié)議完成。

DDS簡(jiǎn)單發(fā)現(xiàn)協(xié)議可以分為簡(jiǎn)單參與者發(fā)現(xiàn)階段和端點(diǎn)發(fā)現(xiàn)階段[11]，兩個(gè)階段的發(fā)布/訂閱關(guān)系如圖2所示。

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

簡(jiǎn)單參與者發(fā)現(xiàn)階段：域參與者之間進(jìn)行相互發(fā)現(xiàn)。本地域參與者通過數(shù)據(jù)寫入者向其他域參與者發(fā)送數(shù)據(jù)包，同時(shí)也會(huì)通過數(shù)據(jù)讀取者讀取其他域參與者發(fā)送的數(shù)據(jù)包。

簡(jiǎn)單端點(diǎn)發(fā)現(xiàn)階段：本地域參與者與其他域參與者進(jìn)行相互匹配。它們相互交換包含主題名稱、主題類型和服務(wù)質(zhì)量策略等信息的數(shù)據(jù)包。

在DDS簡(jiǎn)單發(fā)現(xiàn)協(xié)議中，每個(gè)本地域參與者需要將自己所有的端點(diǎn)信息發(fā)送給其他域參與者，同時(shí)也會(huì)接收其他域參與者發(fā)送的所有的端點(diǎn)信息，這會(huì)產(chǎn)生大量的內(nèi)存消耗和網(wǎng)絡(luò)傳輸量。事實(shí)上，每個(gè)域參與者只關(guān)心與自己訂閱主題相關(guān)的端點(diǎn)信息。因此，本文提出了基于單哈希多維布隆過濾器的自動(dòng)發(fā)現(xiàn)算法。

2 算法設(shè)計(jì)

為降低標(biāo)準(zhǔn)Bloom的哈希計(jì)算量，本文提出了一種新型布隆過濾器OMBF。為降低DDS自動(dòng)發(fā)現(xiàn)過程中的內(nèi)存消耗和數(shù)據(jù)傳輸，本文將OMBF與DDS簡(jiǎn)單發(fā)現(xiàn)協(xié)議結(jié)合，提出了自動(dòng)發(fā)現(xiàn)算法SDP_OMBF。

2015年9月，沙特阿拉伯和巴林簽署價(jià)值約3億美元的新輸油管道鋪設(shè)合同。該管道由沙特阿美石油公司和巴林石油公司共同管理，將把原油從沙特阿美公司位于沙特東部的布蓋格煉油廠輸送到巴林石油公司煉油廠。

2.1 OMBF

OMBF是一種高效率的空間隨機(jī)數(shù)據(jù)結(jié)構(gòu)，它用位數(shù)組簡(jiǎn)潔地表示一個(gè)集合，并可以判斷一個(gè)元素是否屬于這個(gè)集合。OMBF是一個(gè)多維向量，每一維向量分為k個(gè)分區(qū)且初始值為0。向量維數(shù)用t表示，每一維向量分區(qū)i的大小用mi(1≤i≤k)表示。

OMBF的哈希函數(shù)計(jì)算過程分為以下三個(gè)階段：

(1) 哈希階段：A→B。A是將要存儲(chǔ)或查詢的集合中的元素，B是經(jīng)過哈希函數(shù)映射之后的機(jī)器字。

(2) 選維階段：B→C。C是OMBF向量某一維，通過對(duì)B取模得到，即|B|(h(x)modt)。每次取模的結(jié)果選中OMBF向量某一維。

(3) 取模階段：B→D。D是OMBF向量某一維中的位置，通過對(duì)B取模得到，即|B|(h(x)modmi)。每次取模的結(jié)果使OMBF向量某一分區(qū)中某一位置為1。

如果每維向量中每個(gè)分區(qū)大小為互質(zhì)，那么OMBF中這種不均勻的分區(qū)方法將會(huì)產(chǎn)生相互獨(dú)立的取模結(jié)果。更確切地，如果gi(x)=h(x) modmi，每個(gè)分區(qū)滿足條件(mi,mj)=1,1≤i≤j≤k，即mi、mj為相對(duì)素?cái)?shù)，那么g1(x)、g2(x)、…、gk(x)相互獨(dú)立。

圖3表示OMBF的結(jié)構(gòu)，其中假設(shè)k=3，集合S{x1，x2}中的元素通過一個(gè)哈希函數(shù)h(x)和取模運(yùn)算存儲(chǔ)在OMBF中。

通過實(shí)例說明OMBF的工作原理。假設(shè)m1=11、m2=13、m3=19。當(dāng)存儲(chǔ)元素x1時(shí)，首先，在哈希階段通過哈希函數(shù)h(x)轉(zhuǎn)換成機(jī)器字h(x1)，設(shè)h(x1)=9 655；然后，在選維階段d=h(x1) modt，即將元素x1映射到OMBF向量中第d維；最后，在取模階段機(jī)器字h(x1)分別對(duì)各分區(qū)進(jìn)行取模。g1(x1)=h(x1) modm1=8，g2(x1)=h(x1) modm2=9，g3(x1)=h(x1) modm3=3，即第d維三個(gè)分區(qū)對(duì)應(yīng)第8位、第9位、第3位。當(dāng)查詢某一元素是否屬于集合S時(shí)，將待查詢?cè)亟?jīng)過3個(gè)階段運(yùn)算之后，檢查相應(yīng)3個(gè)位置是否為1，如果是，則判定該元素屬于集合S。

2.2 OMBF性能分析

OMBF和Bloom一樣，在元素查詢過程中也會(huì)發(fā)生誤報(bào)。OMBF誤報(bào)由兩個(gè)因素導(dǎo)致：(1) 在哈希階段，由機(jī)器字沖突發(fā)生的誤報(bào)，用a表示；(2) 在取模階段，在機(jī)器字不發(fā)生沖突的情況下，機(jī)器字取模余數(shù)發(fā)生沖突導(dǎo)致的誤報(bào)，用b表示。OMBF總的誤報(bào)率用FOMBF表示，計(jì)算如下：

FOMBE=P(f)=P(f|a)P(a)+P(f|b)P(b)=

P(a)+P(f|b)(1-P(a))

(1)

(2)

同理，可以得到機(jī)器字取模余數(shù)發(fā)生沖突導(dǎo)致的誤報(bào)率為：

(3)

通常機(jī)器字的長(zhǎng)度遠(yuǎn)大于OMBF向量，所以P(a)接近于0。OMBF的誤報(bào)率可以簡(jiǎn)化為：

(4)

由于SDPBloom中的哈希函數(shù)數(shù)量等于SDP_OMBF中每一維的分區(qū)數(shù)，即哈希函數(shù)數(shù)量為k，其誤報(bào)率FSBF為[12]：

(5)

(6)

2.3 SDP_OMBF

在OMBF和簡(jiǎn)單發(fā)現(xiàn)協(xié)議SDP的基礎(chǔ)上，本文提出了一種新的自動(dòng)發(fā)現(xiàn)算法SDP_OMBF。SDP和SDP_OMBF的自動(dòng)發(fā)現(xiàn)執(zhí)行過程如圖4所示。

(a) SDP執(zhí)行過程

圖4用兩個(gè)節(jié)點(diǎn)通信的實(shí)例說明SDP和SDP_OMBF執(zhí)行過程，實(shí)例中本地參與者A向遠(yuǎn)程參與者B發(fā)送端點(diǎn)信息。SDP_OMBF的執(zhí)行過程如圖4(b)所示。在參與者發(fā)現(xiàn)階段，將本地參與者端點(diǎn)描述信息生成OMBF向量，然后和本地參與者數(shù)據(jù)包一塊發(fā)送至遠(yuǎn)程參與者。參與者端點(diǎn)描述信息使用參與者端點(diǎn)信息唯一標(biāo)識(shí)符，本文使用主題名作為唯一標(biāo)識(shí)符。在端點(diǎn)發(fā)現(xiàn)階段，遠(yuǎn)程參與者根據(jù)自身訂閱的主題對(duì)OMBF進(jìn)行查詢。如果存在訂閱主題，則向本地參與者發(fā)送訂閱信息，本地參與者將被訂閱的主題數(shù)據(jù)包及服務(wù)質(zhì)量發(fā)送至遠(yuǎn)程參與者進(jìn)行下一步匹配，如果匹配成功，兩參與者建立通信。而在圖4(a)所示的SDP的執(zhí)行過程中，遠(yuǎn)程參與者將會(huì)訂閱和接收本地參與者所有的端點(diǎn)信息。本文提出的SDP_OMBF將大量的端點(diǎn)信息減少為一條OMBF向量信息，因此，可以有效地減少自動(dòng)發(fā)現(xiàn)過程中的內(nèi)存消耗和網(wǎng)絡(luò)傳輸量。

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

本節(jié)通過仿真和實(shí)驗(yàn)驗(yàn)證SDP_OMBF的有效性。本文將SDP_OMBF與使用較廣的DDS改進(jìn)自動(dòng)發(fā)現(xiàn)算法SDPBloom進(jìn)行對(duì)比，驗(yàn)證SDP_OMBF網(wǎng)絡(luò)傳輸量和內(nèi)存消耗、主題查詢時(shí)間和誤報(bào)率。實(shí)驗(yàn)平臺(tái)為Intel(R)CPU Core(TM) i5-3210、12 GB DDR 3(1 600 MHz)存儲(chǔ)器和4核×2線程(2.5 GHz)，軟件環(huán)境為DDS分布式互聯(lián)架構(gòu)平臺(tái)。

3.1 網(wǎng)絡(luò)傳輸量和內(nèi)存消耗驗(yàn)證

實(shí)驗(yàn)設(shè)置了1 000個(gè)參與者，每個(gè)參與者發(fā)布100個(gè)主題，每個(gè)主題信息是6 800字節(jié)，主題關(guān)鍵字為4字節(jié)。在SDPBloom和SDP_OMBF中，存儲(chǔ)主題關(guān)鍵字的向量為72字節(jié)。在端點(diǎn)發(fā)現(xiàn)階段，當(dāng)查詢主題關(guān)鍵字中成員元素的比例從10%到90%變化時(shí)，SDP_OMBF和SDPBloom的網(wǎng)絡(luò)傳輸量和內(nèi)存消耗如圖5和圖6所示。

圖5 SDPBloom和SDP_OMBF的網(wǎng)絡(luò)傳輸量

圖6 SDPBloom和SDP_OMBF的內(nèi)存消耗

可以看出，當(dāng)端點(diǎn)匹配逐漸增大時(shí)，SDPBloom和SDP_OMBF中的網(wǎng)絡(luò)數(shù)據(jù)傳輸量和內(nèi)存消耗也逐漸增大。無論端點(diǎn)匹配率如何變化，兩者網(wǎng)絡(luò)數(shù)據(jù)傳輸量和內(nèi)存消耗都近似相等。

3.2 主題查詢時(shí)間和誤報(bào)率驗(yàn)證

本文實(shí)驗(yàn)中，參與者端點(diǎn)信息的每個(gè)主題關(guān)鍵字大小為4字節(jié)。在SDP_OMBF中，本地參與者n個(gè)主題關(guān)鍵字映射到OMBF向量中。遠(yuǎn)程參與者查詢主題關(guān)鍵字成員元素比例在10%至90%之間變化。令m=150、n=100、k=3、t=3。SDP_OMBF中的哈希函數(shù)為MD5，SDPBloom中的哈希函數(shù)為MD5、MD2和SHA-1。

當(dāng)m變化時(shí)，進(jìn)行了100組實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表1、表2所示。

表1 m=561時(shí)，SDPBloom和SDP_OMBF誤報(bào)率和計(jì)算時(shí)間對(duì)比

表2 m=1 413時(shí)，SDPBloom和SDP_OMBF誤報(bào)率和計(jì)算時(shí)間對(duì)比

續(xù)表2

從表1和表2可以看出，當(dāng)m較小時(shí)，SDP_OMBF的誤報(bào)率略大于SDPBloom；當(dāng)m增大時(shí)，兩者誤報(bào)率近似相等。然而，SDP_OMBF的運(yùn)算時(shí)間始終低于SDPBloom約3 000 ms。

4 結(jié) 語

本文對(duì) DDS 中SDP_ADA和SDPBloom自動(dòng)發(fā)現(xiàn)算法進(jìn)行了深入研究, 在分布式仿真系統(tǒng)規(guī)模較大時(shí)，針對(duì)數(shù)據(jù)傳輸過程中SDPBloom自動(dòng)發(fā)現(xiàn)算法存在哈希函數(shù)運(yùn)算量大的問題，提出一種新型的自動(dòng)發(fā)現(xiàn)算法SDP_OMBF。通過實(shí)驗(yàn)驗(yàn)證了該算法的有效性。與SDPBloom算法相比，該算法在保證網(wǎng)絡(luò)數(shù)據(jù)傳輸量和內(nèi)存消耗基本不變的條件下，將哈希函數(shù)運(yùn)算時(shí)間降低約78%，從而降低自動(dòng)發(fā)現(xiàn)過程中參與者端點(diǎn)之間發(fā)布/訂閱信息的時(shí)間，提高了分布式仿真系統(tǒng)的實(shí)時(shí)性。