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

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

0 引 言

數(shù)據(jù)分發(fā)服務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ù)據(jù)[3]。在中小型分布式仿真系統(tǒng)得到良好應用，但當系統(tǒng)規(guī)模較大、數(shù)據(jù)交互較多時，SDP會造成網(wǎng)絡傳輸量高、內(nèi)存消耗大等問題。針對這一問題，文獻[4]提出SDPBloom(Bloom filter simple discovery protocol)自動發(fā)現(xiàn)算法，通過將端點描述信息存儲到Bloom過濾器中發(fā)送給其他參與者，可以減少網(wǎng)絡傳輸量與內(nèi)存消耗，但是該算法不支持元素刪除操作，且在運算過程中需要較多的哈希函數(shù)，時間消耗成本較大。文獻[5]提出一種單哈希閾值布隆過濾器DDS自動發(fā)現(xiàn)算法，通過調(diào)整閾值θ和判定閾值T進行端點信息的查詢匹配，降低了DDS在自動發(fā)現(xiàn)過程中的誤報以及網(wǎng)絡傳輸量。文獻[6]將可壓縮布隆過濾器應用到DDS自動發(fā)現(xiàn)算法中，在一定程度上降低了網(wǎng)絡傳輸量與內(nèi)存消耗。文獻[7]提出一種基于分層布隆過濾器的DDS自動發(fā)現(xiàn)算法，通過改進原有的鏈式儲存結構以及增加節(jié)點刪除操作，有效降低內(nèi)存消耗。

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

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

1.1 DDS

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

圖1 DDS的通信結構

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

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

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

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

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

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

2 OHCBF的設計與理論分析

2.1 OHCBF的設計

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

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

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

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

圖3 OHCBF結構

2.2 OHCBF的理論分析

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

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

(1)

(2)

(3)

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

(4)

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

2.2.2 OHCBF的獨立性約束

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

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

2.2.3 OHCBF的誤報分析

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

(5)

(6)

(7)

(8)

(9)

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

(10)

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

(11)

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

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

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

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

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

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

3.2 基于SDP_OHCBF的性能分析

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

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

(12)

(13)

(14)

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

MSDP=E

(15)

(16)

(17)

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

4 實驗驗證與結果分析

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

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

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

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

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

隨著參與者數(shù)量增加，端點數(shù)也增加，SDP、SDPBloom和SDP_OHCBF的內(nèi)存消耗也隨著參與者數(shù)量增加而發(fā)生變化，圖6與圖7分別為匹配端點率為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)絡傳輸量較SDPBloom和SDP_OHCBF大，且發(fā)送的信息數(shù)不隨端點匹配率ME的變化而變化，所以SDP需要更大的消耗內(nèi)存來存儲遠程端點信息；當端點匹配率越小，SDPBloom和SDP_OHCBF的優(yōu)勢就越明顯；

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

4.2 誤報率與查詢時間

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

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

表1 SDPBloom和SDP_OHCBF的誤報率

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

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

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

圖9 隨端點匹配率ME變化所需查詢時間

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

5 結束語

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