基于索引布隆過(guò)濾器的DDS自動(dòng)發(fā)現(xiàn)算法

摘" 要： 數(shù)據(jù)分發(fā)服務(wù)（DDS）被廣泛用于分布式系統(tǒng)的網(wǎng)絡(luò)搭建，其中自動(dòng)發(fā)現(xiàn)機(jī)制是DDS的關(guān)鍵部分。現(xiàn)有的DDS自動(dòng)發(fā)現(xiàn)機(jī)制大都采用簡(jiǎn)單發(fā)現(xiàn)協(xié)議（SDP），但這種協(xié)議在大規(guī)模分布式系統(tǒng)的網(wǎng)絡(luò)環(huán)境中會(huì)產(chǎn)生網(wǎng)絡(luò)負(fù)載過(guò)高、匹配效率低下等問(wèn)題。針對(duì)這些問(wèn)題，提出一種基于索引布隆過(guò)濾器的輕量級(jí)DDS自動(dòng)發(fā)現(xiàn)算法。該算法基于多維向量結(jié)構(gòu)和索引值間的位操作設(shè)計(jì)一種索引布隆過(guò)濾器，用于壓縮分布式系統(tǒng)網(wǎng)絡(luò)節(jié)點(diǎn)間的傳輸信息，同時(shí)提供比標(biāo)準(zhǔn)布隆過(guò)濾器更低的誤判率。結(jié)合索引布隆過(guò)濾器與SDP，能夠減少DDS自動(dòng)發(fā)現(xiàn)過(guò)程中的資源消耗并提高匹配效率。實(shí)驗(yàn)結(jié)果表明，在節(jié)點(diǎn)匹配率為10%的情況下，所提出的DDS自動(dòng)發(fā)現(xiàn)算法相比基于標(biāo)準(zhǔn)布隆過(guò)濾器的SDPBloom算法，發(fā)現(xiàn)過(guò)程的數(shù)據(jù)包數(shù)量減少了46.39%，匹配時(shí)間縮短了73.30%。

關(guān)鍵詞： 數(shù)據(jù)分發(fā)服務(wù)； 自動(dòng)發(fā)現(xiàn)算法； 布隆過(guò)濾器； 分布式系統(tǒng)； 簡(jiǎn)單發(fā)現(xiàn)協(xié)議； 多維向量； 誤判率

中圖分類號(hào)： TN713?34" " " " " " " " " " " " " " 文獻(xiàn)標(biāo)識(shí)碼： A" " " " " " " " " " " "文章編號(hào)： 1004?373X（2024）24?0047?08

DDS automatic discovery algorithm based on index BF

LIU Huangbiao1， 2， YANG Fan2， SONG Ge2， WANG Fengjun2， ZHANG Qi1， ZHANG Xiaobei1

（1. School of Communication amp; Information Engineering， Shanghai University， Shanghai 200444， China;

2. COMAC Shanghai Aircraft Design amp; Research Institute， Shanghai 201210， China）

Abstract： Data distribution server （DDS） is extensively utilized in the network construction of distributed systems， and the automatic discovery mechanism is a key part of DDS. The simple discovery protocol （SDP） is used in most of the existing DDS automatic discovery mechanisms， which can cause problems such as high network load and low matching efficiency in large?scale distributed system network environment. On this basis， a lightweight DDS automatic discovery algorithm based on index bloom filter （BF） is proposed. Based on the multi?dimensional vector structure and the bit operation between index values， an index BF is designed to compress the information transmitted between nodes in the distributed system network and provide a lower misjudgment rate than the standard BF. The combination of index BF and SDP can reduce the resource consumption in DDS automatic discovery process and improve the matching efficiency. The experimental results demonstrate that when the node matching rate is 10%， the proposed DDS automatic discovery algorithm significantly can reduce the number of data packets by 46.39% and shorten the matching time by 73.30% compared with the SDPBloom algorithm based on the standard BF.

Keywords： data distribution services; automatic discovery algorithm; bloom filter; distributed system; simple discovery protocol; multidimensional vector; misjudgment rate

0" 引" 言

當(dāng)今飛機(jī)、汽車和火車系統(tǒng)設(shè)計(jì)的規(guī)模日益增大，系統(tǒng)復(fù)雜性大大增加，分布式系統(tǒng)的應(yīng)用[1?2]變得越來(lái)越重要。數(shù)據(jù)分發(fā)服務(wù)（Data Distribution Server， DDS）中間件[3]作為一種可靠的數(shù)據(jù)通信技術(shù)，在分布式環(huán)境中能夠?qū)崿F(xiàn)高性能、實(shí)時(shí)的數(shù)據(jù)傳輸[4]，提供通信、消息傳遞和協(xié)議適配等功能[5]，以及協(xié)調(diào)和管理分布式系統(tǒng)的各個(gè)部分[6]。在DDS的通信過(guò)程中，節(jié)點(diǎn)發(fā)現(xiàn)機(jī)制[7]幫助分布式系統(tǒng)中的節(jié)點(diǎn)相互發(fā)現(xiàn)和建立通信關(guān)系，它允許 DDS系統(tǒng)中的節(jié)點(diǎn)自動(dòng)地發(fā)現(xiàn)其他節(jié)點(diǎn)，并獲取這些節(jié)點(diǎn)的有關(guān)信息，如可用性、QoS（Quality of Service）要求等。通過(guò)節(jié)點(diǎn)發(fā)現(xiàn)機(jī)制，節(jié)點(diǎn)能夠動(dòng)態(tài)地加入或離開DDS系統(tǒng)，而無(wú)需手動(dòng)配置或靜態(tài)預(yù)定義節(jié)點(diǎn)的信息。

為了在不同的DDS實(shí)現(xiàn)之間提供互操作性和透明度，OMG標(biāo)準(zhǔn)化了DDS互操作性有線協(xié)議（DDS Interoperability Wire Protocol）[8]，其規(guī)定任何兼容的DDS?RTPS的實(shí)現(xiàn)必須至少支持SDP（Simple Discovery Protocol）。然而該協(xié)議僅能夠滿足中小型系統(tǒng)的通信需求[9]，對(duì)于民用飛機(jī)等大規(guī)模分布式系統(tǒng)設(shè)計(jì)來(lái)說(shuō)，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量龐多、發(fā)現(xiàn)協(xié)議數(shù)據(jù)包成倍增加、交換頻率大大上升[10]，這會(huì)導(dǎo)致SDP的匹配效率低下，匹配時(shí)間過(guò)長(zhǎng)和高帶寬消耗問(wèn)題凸顯，無(wú)法較好地滿足大規(guī)模的數(shù)據(jù)傳輸需求。

布隆過(guò)濾器（Bloom Filter， BF）是一種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)[11]，主要作用是快速判斷一個(gè)元素是否屬于某個(gè)集合，而無(wú)需實(shí)際存儲(chǔ)這個(gè)集合中的所有元素，具有高效的查詢速度和低內(nèi)存消耗的特點(diǎn)，在分布式系統(tǒng)中應(yīng)用廣泛[12]。在DDS中，BF可以應(yīng)用于節(jié)點(diǎn)發(fā)現(xiàn)過(guò)程中的信息壓縮和快速匹配[13]。通過(guò)使用BF，DDS系統(tǒng)可以在節(jié)點(diǎn)之間交換和存儲(chǔ)經(jīng)過(guò)哈希計(jì)算后的信息，而無(wú)需傳輸和存儲(chǔ)原始的大量數(shù)據(jù)，這樣可以大大減少網(wǎng)絡(luò)負(fù)載和節(jié)點(diǎn)資源消耗，提高節(jié)點(diǎn)發(fā)現(xiàn)的效率和性能。需要注意的是，BF在判斷一個(gè)元素是否存在于集合中時(shí)，可能會(huì)存在誤判[14] 。一般而言，BF的誤判率和它的大小以及所使用的哈希函數(shù)數(shù)量相關(guān)，BF的誤判率和哈希函數(shù)數(shù)量都直接影響節(jié)點(diǎn)發(fā)現(xiàn)過(guò)程的效率和帶寬，因此基于BF的DDS自動(dòng)發(fā)現(xiàn)算法研究也大都建立在BF的改良之上[15?18]，例如符號(hào)布隆過(guò)濾器（Symbol Bloom Filter， SBF）[19]和單哈希多維布隆過(guò)濾器（Onehash Manydimensions Bloom Filter， OMBF）[20]，前者通過(guò)增加符號(hào)向量來(lái)降低誤判率，但增加了查詢和插入操作的復(fù)雜性；后者使用單個(gè)哈希函數(shù)，通過(guò)多維不同分區(qū)位向量的映射操作保證哈希函數(shù)的均勻性和隨機(jī)性，用一定的誤判率換取更快的查詢時(shí)間。然而這種單一性能的改善對(duì)于DDS自動(dòng)發(fā)現(xiàn)算法的提升有限，隨著網(wǎng)絡(luò)規(guī)模的增大，另一性能的短板也會(huì)影響到發(fā)現(xiàn)算法的匹配效率，需要提出一種更加全面的BF來(lái)進(jìn)行DDS自動(dòng)發(fā)現(xiàn)算法的改進(jìn)。

本文詳細(xì)分析了SBF和OMBF的特點(diǎn)和不足之處，提出了一種用于大規(guī)模分布式系統(tǒng)的索引布隆過(guò)濾器（Index Bloom Filter， IBF），并結(jié)合SDP實(shí)現(xiàn)了基于該過(guò)濾器的DDS自動(dòng)發(fā)現(xiàn)算法。在多維位圖的基礎(chǔ)上，將標(biāo)準(zhǔn)BF中存儲(chǔ)信息的位向量替換成根據(jù)端點(diǎn)信息生成的索引向量，并通過(guò)索引間的異或操作來(lái)進(jìn)行元素的插入和查找，這種方式僅需要2個(gè)哈希函數(shù)就可以保證可接受的誤判率，同時(shí)還能保證快速的查找時(shí)間，從而提高自動(dòng)發(fā)現(xiàn)的匹配效率和速度，滿足類似機(jī)載信息系統(tǒng)這種大規(guī)模分布式系統(tǒng)的通信需求。

1" 相關(guān)工作

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

OMG DDS標(biāo)準(zhǔn)[21]定義了分布式系統(tǒng)的發(fā)布/訂閱通信模型，其中描述了DDS中的實(shí)體概念，包括域、域參與者、主題、發(fā)布者、訂閱者、數(shù)據(jù)寫入器、數(shù)據(jù)讀取器[22]等，分布式系統(tǒng)之間的通信正是由這些實(shí)體之間的行為所實(shí)現(xiàn)的。DDS實(shí)體通信模型如圖1所示。其中域代表一個(gè)單獨(dú)的通信網(wǎng)絡(luò)，屬于相同域的不同參與者通過(guò)發(fā)布者和訂閱者進(jìn)行通信，寫入器和讀取器作為發(fā)布者或訂閱者實(shí)際發(fā)送和接收消息的端點(diǎn)，主題定義了不同端點(diǎn)之間通信的數(shù)據(jù)類型和數(shù)據(jù)名稱，多個(gè)主題構(gòu)成不同參與者之間通信的邏輯通道。

DDS可以描述為一種覆蓋式點(diǎn)對(duì)點(diǎn)結(jié)構(gòu)，其中給定主題的發(fā)布者通過(guò)全局?jǐn)?shù)據(jù)空間（Global Data Space， GDS）鏈接到同一主題的所有訂閱者。DDS通過(guò)節(jié)點(diǎn)發(fā)現(xiàn)機(jī)制為發(fā)布者和訂閱者之間建立通信，節(jié)點(diǎn)發(fā)現(xiàn)機(jī)制實(shí)現(xiàn)了發(fā)布者和訂閱者之間所有信息的透明和可互操作的即插即用傳播。根據(jù)DDS互操作性協(xié)議，任何發(fā)現(xiàn)協(xié)議都必須分為兩個(gè)連續(xù)的階段：參與者發(fā)現(xiàn)階段（Participant Discovery Phase， PDP）和端點(diǎn)發(fā)現(xiàn)階段（Endpoint Discovery Phase， EDP）。DDS發(fā)現(xiàn)協(xié)議如圖2所示。其中PDP為參與者之間的發(fā)現(xiàn)階段，本地域參與者通過(guò)內(nèi)建數(shù)據(jù)寫入器向其他域參與者發(fā)送數(shù)據(jù)包，同時(shí)也會(huì)通過(guò)數(shù)據(jù)讀取器讀取其他域參與者發(fā)送的數(shù)據(jù)包。每當(dāng)有新的參與者互相匹配時(shí)，就會(huì)觸發(fā)EDP階段，兩個(gè)域參與者之間交換本地和遠(yuǎn)程端點(diǎn)信息，包括主題名稱、主題類型、QoS策略信息等。

1.2" 基于布隆過(guò)濾器的DDS自動(dòng)發(fā)現(xiàn)協(xié)議

由1.1小節(jié)可知，EDP數(shù)據(jù)包包含了節(jié)點(diǎn)建立通信所需要的主要信息，而PDP數(shù)據(jù)包主要用于公布節(jié)點(diǎn)的存在情況。SDP自動(dòng)發(fā)現(xiàn)流程如圖3所示，由圖可知，在SDP中本地節(jié)點(diǎn)通過(guò)PDP階段獲取網(wǎng)絡(luò)中所有節(jié)點(diǎn)的存在信息，之后便直接進(jìn)入EDP階段，不論是否與該節(jié)點(diǎn)建立通信。為了盡量減少SDP中冗余EDP數(shù)據(jù)包對(duì)于帶寬資源的浪費(fèi)，引入了布隆過(guò)濾器算法來(lái)改進(jìn)DDS簡(jiǎn)單發(fā)現(xiàn)協(xié)議。其主要原理是：在進(jìn)入EDP階段之前，通過(guò)BF進(jìn)行一次篩選，檢查遠(yuǎn)程節(jié)點(diǎn)是否存在本地節(jié)點(diǎn)所感興趣的端點(diǎn)信息，從而減少不必要的EDP階段。加入BF后的SDP自動(dòng)發(fā)現(xiàn)流程如圖4所示，通過(guò)BF的過(guò)濾作用挑選出有必要進(jìn)一步匹配的參與者節(jié)點(diǎn)，從而減少不必要的EDP匹配過(guò)程，這種方式能夠有效降低節(jié)點(diǎn)在發(fā)現(xiàn)過(guò)程中的網(wǎng)絡(luò)資源消耗。

盡管SDPBloom算法在一定程度上減少了SDP在大規(guī)模分布式系統(tǒng)中的發(fā)現(xiàn)流量，但標(biāo)準(zhǔn)BF存在的誤判率問(wèn)題和哈希運(yùn)算量仍然影響DDS自動(dòng)發(fā)現(xiàn)算法的匹配效率和時(shí)間。為此，本文在標(biāo)準(zhǔn)BF基礎(chǔ)上進(jìn)行改進(jìn)，構(gòu)建了一種多維分區(qū)的索引向量位圖，代替標(biāo)準(zhǔn)BF中的單維位圖，用于保存過(guò)濾器中元素的存在信息，通過(guò)不同索引之間的差異性降低標(biāo)準(zhǔn)BF的誤判率。這種過(guò)濾器僅需使用2個(gè)哈希函數(shù)（一個(gè)用于生成索引值，另一個(gè)用于鎖定映射位置）就可以擁有比標(biāo)準(zhǔn)BF更低的誤判率，能夠更好地適應(yīng)大規(guī)模分布式系統(tǒng)的通信需求。

2" 基于索引布隆過(guò)濾器的DDS自動(dòng)發(fā)現(xiàn)算法

2.1" 索引布隆過(guò)濾器結(jié)構(gòu)和原理

索引布隆過(guò)濾器是一種改進(jìn)型的布隆過(guò)濾器。為了降低誤判率，標(biāo)準(zhǔn)BF往往通過(guò)增加所使用的哈希函數(shù)數(shù)量來(lái)減少哈希沖突[23]，故所選擇的哈希函數(shù)往往比較復(fù)雜[24]，且計(jì)算量較大，如混沌哈希函數(shù)、MD5、SHA?2等。為了降低哈希函數(shù)計(jì)算量，索引布隆過(guò)濾器將標(biāo)準(zhǔn)布隆過(guò)濾器中存儲(chǔ)元素存在信息的位向量拓展為多維向量，并對(duì)每個(gè)維度進(jìn)行分區(qū)。IBF的多維分區(qū)結(jié)構(gòu)如圖5所示，為一個(gè)[t]維位向量，其中每一維有3個(gè)分區(qū)，大小分別為[m1]、[m2]、[m3]。為了保證元素映射位置的相互獨(dú)立性，分區(qū)大小一般設(shè)置為互不相同的質(zhì)數(shù)。元素插入時(shí)，主要經(jīng)過(guò)兩次哈希運(yùn)算與多次取模運(yùn)算，其中兩次哈希運(yùn)算分別產(chǎn)生一個(gè)映射值和一個(gè)索引值，再對(duì)映射值進(jìn)行第一次取模運(yùn)算，選取元素映射的向量維度，最后與每個(gè)分區(qū)大小進(jìn)行多次取模，以確定元素在每個(gè)分區(qū)中的映射位置。

IBF的算法處理流程如下。

1） 分區(qū)階段：通過(guò)計(jì)算的方式將給定的[m]大小的位向量盡可能地分成[t]個(gè)大小不一的區(qū)域，即[{m1，m2，…，mk}]。為盡可能保證映射的隨機(jī)性和均勻性，不同分區(qū)大小應(yīng)設(shè)置為質(zhì)數(shù)，分區(qū)中的每個(gè)位置是一個(gè)[z]位的索引，用于記錄元素的存在信息。

2） 哈希階段：將待插入元素[x]通過(guò)第1個(gè)哈希函數(shù)[h1（x）]映射為機(jī)器字，用于后續(xù)的取模操作，從而確定元素在各個(gè)分區(qū)中的映射位置。

3） 取模階段：利用之前定義的[t]個(gè)不同分區(qū)的大小對(duì)哈希階段生成的機(jī)器字進(jìn)行取模運(yùn)算，所得到的結(jié)果用于指示元素[x]在每個(gè)分區(qū)中的具體映射位置。由于分區(qū)大小都是質(zhì)數(shù)，能夠在一定程度上保持哈希映射的隨機(jī)性和均勻性。

4） 索引映射：通過(guò)第2個(gè)哈希函數(shù)[h2（x）]計(jì)算元素[x]的索引值，并利用[z]對(duì)其取模，從而得到該元素對(duì)應(yīng)的索引值；再將步驟3）中所有位置的值與該值進(jìn)行或操作，更新每個(gè)位置的索引值。

通過(guò)將單維位向量擴(kuò)展到多維，能夠減少相當(dāng)一部分的哈希計(jì)算量，但對(duì)于標(biāo)準(zhǔn)BF來(lái)說(shuō)，這種位圖結(jié)構(gòu)所得到的哈希映射結(jié)果并沒(méi)有表現(xiàn)出更好的均勻性和隨機(jī)性。為了解決這個(gè)問(wèn)題，IBF添加了索引映射操作來(lái)剔除部分哈希沖突所造成的誤判情況，從而在多維位向量中獲得更好的誤判率表現(xiàn)。在元素存儲(chǔ)信息的表示中，標(biāo)準(zhǔn)BF基于位向量每個(gè)比特位的取值來(lái)表示元素的存在與否；而在索引布隆過(guò)濾器中，每個(gè)表示位被替換成一個(gè)多比特位組合表示的索引，用于區(qū)分來(lái)自不同元素的映射。初始情況下，多維位向量中所有的位都置為0。當(dāng)多個(gè)索引被映射到同一位置時(shí)，通過(guò)對(duì)每個(gè)位置分別進(jìn)行或操作來(lái)保存多個(gè)元素的存在信息。IBF插入和查找原理圖如圖6所示。

查詢?cè)貢r(shí)，將對(duì)所有映射位置的索引值進(jìn)行與操作，若與結(jié)果不為0，則表示多個(gè)映射位置可能存在同一索引，判定元素存在，否則不存在。在圖6中，標(biāo)準(zhǔn)BF位向量中[x2]對(duì)應(yīng)的映射位置都會(huì)被置為1，導(dǎo)致最終在元素查詢時(shí)發(fā)生誤判。而在IBF中，不同映射位置對(duì)應(yīng)的索引值與結(jié)果為0，說(shuō)明這幾個(gè)位置的索引來(lái)自不同元素，因此判定該元素不存在，這種方式剔除了標(biāo)準(zhǔn)BF中由于哈希沖突導(dǎo)致誤判的部分情形，從而降低了誤判率。

2.2" 索引布隆過(guò)濾器性能分析

本文將索引布隆過(guò)濾器的誤判率與標(biāo)準(zhǔn)布隆過(guò)濾器進(jìn)行對(duì)比。IBF產(chǎn)生誤判的原因有兩個(gè)：多維分區(qū)映射階段產(chǎn)生的映射位置沖突和映射位置對(duì)應(yīng)的索引沖突，這兩種情況同時(shí)發(fā)生時(shí)就會(huì)產(chǎn)生誤判。兩種沖突概率分別用[P1]和[P2]表示，則索引布隆過(guò)濾器的誤判率可表示為：

[PFPR=P1·P2] （1）

映射位置沖突的產(chǎn)生原因也分兩種：一種是哈希階段所獲取的映射值機(jī)器字沖突，用[a]表示；另一種則是映射值機(jī)器字不沖突的情況下，在取模階段發(fā)生的余數(shù)沖突，用[b]表示。則映射位置沖突概率可表示為：

[P1=P1a·Pa+P1b·Pb=Pa+P1b·1-Pa] （2）

假設(shè)機(jī)器字為[L]位，IBF中有[t]維位向量，每一維向量的分區(qū)數(shù)為[k]，[n]個(gè)元素均勻插入[t]維位向量中，則映射值機(jī)器字沖突概率為：

[Pa=1-1-12Ln] （3）

同理，余數(shù)沖突的誤報(bào)率為：

[P1b=i=1k1-1-1mint≈i=1k1-e-nt·mi] （4）

通常情況下[2L?mi]，即[Pa≈0]。故有：

[PFPR≈P1b·P2≈i=1k1-1-1mint·P2≤1-i=1k1-1mintkk·P2≈1-i=1ke-nt·mikk·P2] （5）

標(biāo)準(zhǔn)布隆過(guò)濾器誤判率[25]公式如下：

[PFPRBF=1-1-1mknk≈1-e-knmk] （6）

由式（5）、式（6）可知，每個(gè)分區(qū)的大小[mi]越接近[mt·k]時(shí)，[P1]越接近[PFPRBF]；對(duì)于不同的索引集合，[P2]的值也不同，例如索引集合[{1，2，4，8}]對(duì)應(yīng)的[P2]為0.25，即誤判率降低為原來(lái)的[14]。

通過(guò)以上分析可知：索引布隆過(guò)濾器的誤判率提升主要依靠索引集合的設(shè)置，對(duì)于任何索引集合，都有[P2≤1]；當(dāng)分區(qū)的均勻性越好、索引集合的位沖突概率越小時(shí)，IBF性能越好。

2.3" 基于索引布隆過(guò)濾器的DDS自動(dòng)發(fā)現(xiàn)算法實(shí)現(xiàn)

索引布隆過(guò)濾器的插入和查詢算法偽代碼分別如算法1和算法2所示，插入時(shí)，首先通過(guò)一個(gè)哈希運(yùn)算和多次取模運(yùn)算得到索引的全部映射位置，并依次對(duì)每個(gè)位置的索引值做或操作；查詢時(shí)，只需判斷查詢?cè)赜成湮恢脤?duì)應(yīng)的索引值與結(jié)果是否為0，即可判斷元素是否存在。

算法1：索引布隆過(guò)濾器插入算法

輸入：key為待插入的字符串密鑰

Function：insert（key）

[dim←h1（key）%t]；" " " " " " " " " " " " " " " " //計(jì)算映射維度

for [i]：[1 2 … k" "]do

/*計(jì)算索引在每個(gè)分區(qū)中的映射位置*/

[position←dim×mi+j=1imj-mi+h1（key）%mi]；

/*計(jì)算元素索引并與對(duì)應(yīng)位置索引做或操作*/

[mposition=mposition | h2（key）]；

end for

算法2：索引布隆過(guò)濾器查詢算法

輸入：key為待查詢的字符串密鑰

輸出：表示待查詢?cè)卮嬖谇闆r的布爾值

Function：query（key）

[dim←h1（key）%t]；" " " " " " " " " " " " " " nbsp; " //計(jì)算映射維度

[res←0xFF]；

for [i]：[1 2 … k" "]do

/*計(jì)算索引在每個(gè)分區(qū)中的映射位置*/

[position←dim×mi+j=1imj-mi+h1（key）%mi]；

/*計(jì)算所有位置索引與結(jié)果*/

[res=mpositionres]；

end for

return res==0

基于索引布隆過(guò)濾器的DDS自動(dòng)發(fā)現(xiàn)算法偽代碼如算法3所示，本地參與者在使能時(shí)構(gòu)建對(duì)應(yīng)的IBF和感興趣的端點(diǎn)密鑰集，將存儲(chǔ)端點(diǎn)存在信息的位向量打包到PDP數(shù)據(jù)包中并發(fā)送；當(dāng)接收到遠(yuǎn)程參與者的 PDP數(shù)據(jù)包時(shí)，提取出里面的位向量信息，構(gòu)建對(duì)應(yīng) IBF并對(duì)感興趣的端點(diǎn)密鑰集合進(jìn)行查詢，若查詢到感興趣的端點(diǎn)存在信息，則進(jìn)入EDP階段，向該遠(yuǎn)程參與者節(jié)點(diǎn)發(fā)送PDP數(shù)據(jù)包，從而提高不同參與者節(jié)點(diǎn)間的匹配效率。

算法3：基于索引布隆過(guò)濾器的DDS自動(dòng)發(fā)現(xiàn)算法

Function：local_endpoint_enabled（EP）

/*將端點(diǎn)信息轉(zhuǎn)換成字符串密鑰*/

[key←getEndpointKey（EP）]；

[IBF.insert（key）]；

Add IBF to PDP_packet；

Send PDP_packet to all remote Participant；

Function：remote_pdp_received（PDP_packet）

/*提取PDP數(shù)據(jù)包中IBF信息進(jìn)行查詢*/

[IBF←get_IBF（PDP_packet）]；

for all local_matched_Ek do

if IBF.query（Ek）gt; 0 then

Send PDP_packet to this remote Participant；

Enter EDP phase；

break

end if

end for

3" 對(duì)比實(shí)驗(yàn)及結(jié)果分析

本節(jié)將IBF與SBF、OMBF和BF進(jìn)行對(duì)比，通過(guò)兩部分實(shí)驗(yàn)驗(yàn)證SDP_IBF自動(dòng)發(fā)現(xiàn)算法的性能，第一部分比較4種布隆過(guò)濾器的誤判率和查找時(shí)間，第二部分將4種過(guò)濾器算法整合到自動(dòng)發(fā)現(xiàn)協(xié)議中，對(duì)比SDPBloom、SDP_SBF、SDP_OMBF、SDP_IBF四種DDS自動(dòng)發(fā)現(xiàn)協(xié)議在實(shí)際網(wǎng)絡(luò)中的性能表現(xiàn)。實(shí)驗(yàn)平臺(tái)為Intel[?] CoreTM i5?12500H 2.50 GHz、機(jī)帶RAM 16.0 GB，軟件環(huán)境為DDS分布式互連架構(gòu)平臺(tái)。

實(shí)驗(yàn)共設(shè)計(jì)不同的主題數(shù)200 000個(gè)，布隆過(guò)濾器的參數(shù)m=5 000，哈希函數(shù)采用自定義的混合哈希函數(shù)，4種過(guò)濾器k值均為4，在OMBF和IBF中，k值表示每一維度向量的分區(qū)數(shù)，設(shè)置維度t為4，每一維度分為k個(gè)分區(qū)，大小分別為239、241、257、263。

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

向每個(gè)布隆過(guò)濾器插入非重復(fù)主題1 500個(gè)，并設(shè)計(jì)了一組函數(shù)，對(duì)插入主題字符串進(jìn)行重復(fù)、反轉(zhuǎn)、大小寫轉(zhuǎn)換等操作，生成具體的錯(cuò)誤集合；再將錯(cuò)誤集合和插入主題集合按照不同的比例組合成測(cè)試集合，使得存在成員比例從5%～90%變化，測(cè)試不同成員比例下4種過(guò)濾器所消耗的查詢時(shí)間以及誤判率表現(xiàn)，結(jié)果分別如圖7、圖8所示。

從圖7和圖8可以看出：4種過(guò)濾器中，SBF的誤判率相比標(biāo)準(zhǔn)布隆過(guò)濾器略有提升，但犧牲了一定的查詢時(shí)間，這是由于SBF每次查詢都要同時(shí)查詢數(shù)據(jù)向量和符號(hào)向量所造成的；OMBF在查詢時(shí)間方面提升較大，但單個(gè)哈希函數(shù)無(wú)法保證散列的均勻性和隨機(jī)性，從而造成誤判率上升。本文提出的IBF在查詢時(shí)間上相較標(biāo)準(zhǔn)BF提升了近20%，降低了18%左右的誤判率，具有良好的查詢性能。

3.2" 網(wǎng)絡(luò)傳輸量及匹配消耗時(shí)間驗(yàn)證

將4種布隆過(guò)濾器結(jié)合到自動(dòng)發(fā)現(xiàn)算法中，設(shè)計(jì)不同的網(wǎng)絡(luò)節(jié)點(diǎn)50個(gè)，每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)上配置500個(gè)具有不同主題的發(fā)布和接收端點(diǎn)，在網(wǎng)絡(luò)穩(wěn)定后加入一個(gè)新節(jié)點(diǎn)，新節(jié)點(diǎn)在網(wǎng)絡(luò)中的節(jié)點(diǎn)匹配率從10%～50%變化，監(jiān)測(cè)在此過(guò)程中的數(shù)據(jù)包數(shù)量以及節(jié)點(diǎn)匹配所消耗的時(shí)間。4種自動(dòng)發(fā)現(xiàn)算法的發(fā)現(xiàn)階段數(shù)據(jù)包數(shù)量和節(jié)點(diǎn)匹配時(shí)間分別如圖9、圖10所示。

從圖9和圖10可以看出：當(dāng)節(jié)點(diǎn)的匹配率逐漸增大時(shí)，發(fā)現(xiàn)階段的數(shù)據(jù)包和節(jié)點(diǎn)匹配消耗時(shí)間都在逐步增大；SDPBloom和SDP_SBF在實(shí)際發(fā)現(xiàn)過(guò)程中區(qū)別不大，而SDP_OMBF在同等過(guò)濾器參數(shù)下產(chǎn)生了大量的數(shù)據(jù)包，同時(shí)也消耗了更長(zhǎng)的節(jié)點(diǎn)匹配時(shí)間，這是因?yàn)樵谧詣?dòng)發(fā)現(xiàn)協(xié)議中，具體的發(fā)現(xiàn)性能與過(guò)濾器的誤判率和查找時(shí)間有關(guān)，OMBF中較高的誤判率意味著多余EDP階段的增加。在機(jī)載信息系統(tǒng)中，節(jié)點(diǎn)匹配率大都在10%上下浮動(dòng)，此時(shí)SDPBloom的發(fā)現(xiàn)階段數(shù)據(jù)包數(shù)量為5 450個(gè)，匹配時(shí)間為191 s；而SDP_IBF的發(fā)現(xiàn)階段數(shù)據(jù)包數(shù)量為2 922個(gè)，匹配時(shí)間為51 s。相較于SDPBloom，SDP_IBF的發(fā)現(xiàn)階段數(shù)據(jù)包數(shù)量減少了 46.39%，匹配時(shí)間縮短了73.30%。在其余匹配率下，SDP_IBF也表現(xiàn)出較好的性能。

4" 結(jié)" 論

本文提出了一種用于大規(guī)模分布式系統(tǒng)網(wǎng)絡(luò)節(jié)點(diǎn)發(fā)現(xiàn)機(jī)制的輕量級(jí)DDS自動(dòng)發(fā)現(xiàn)算法。在標(biāo)準(zhǔn)布隆過(guò)濾器的基礎(chǔ)上，提出了一種新的索引布隆過(guò)濾器，用于壓縮分布式計(jì)算節(jié)點(diǎn)之間的信息；然后將它與SDP結(jié)合，組成一個(gè)新的DDS自動(dòng)發(fā)現(xiàn)算法——SDP_IBF。此外，還討論了4種基于不同過(guò)濾器的DDS自動(dòng)發(fā)現(xiàn)算法的性能，實(shí)驗(yàn)結(jié)果表明，SDP_IBF可以通過(guò)降低誤判率和查詢時(shí)間來(lái)顯著減少DDS自動(dòng)發(fā)現(xiàn)算法的發(fā)現(xiàn)階段數(shù)據(jù)包冗余，加快新參與者網(wǎng)絡(luò)節(jié)點(diǎn)的匹配速度，能夠更好地滿足大規(guī)模分布式系統(tǒng)的通信需求。

注：本文通訊作者為宋歌。

參考文獻(xiàn)

[1] SCHNEIDER S. The future of iiot software in manufacturing： a guide to understanding and using data distribution service （DDS）， time?sensitive networking （TSN）， and OPC unified architecture （OPCUA） for advanced manufacturing applications [J]. Control engineering， 2019， 66（1）： 16?19.

[2] SADJINA S， KYLLINGSTAD L T， RINDARY M， et al. Distributed co?simulation of maritime systems and operations [J]. Journal of offshore mechanics and arctic engineering， 2019， 141（1）： 011302.

[3] LIU Z， ZHAO Z. Distributed co?simulation computing based on DDS for large?scale aircraft mechatronic system [C]// Proceedings of the Fifth International Conference on Mechatronics and Computer Technology Engineering. Rome， Italy： ACM， 2022： 167?176.

[4] AGARWAL T， NIKNEJAD P， BARZEGARAN M， et al. Multi?level time?sensitive networking （TSN） using the data distribution services （DDS） for synchronized three?phase measurement data transfer [J]. IEEE access， 2019， 7： 13407?13417.

[5] 趙斌，郝紅旗.網(wǎng)絡(luò)中間件在分布式仿真系統(tǒng)中的應(yīng)用[J].計(jì)算機(jī)仿真，2009，26（12）：100?102.

[6] 王鵬，楊妹，彭勇，等.DDS在分布式仿真系統(tǒng)中的應(yīng)用研究[C]//中國(guó)計(jì)算機(jī)用戶協(xié)會(huì)仿真應(yīng)用分會(huì)全國(guó)仿真技術(shù)學(xué)術(shù)會(huì)議論文集.北京：《計(jì)算機(jī)仿真》雜志社，2021：254?259.

[7] KAUSHIK S， POONIA R C， KHATRI S K. Comparative study of various protocols of DDS [J]. Journal of statistics and management systems， 2017， 20（4）： 647?658.

[8] Object Management Group. The real?time publish?subscribe protocol DDS interoperability wire protocol （DDSI?RTPS） specification version 2.5 [EB/OL]. [2022?04?01]. https：//www.omg.org/spec/DDSI?RTPS/2.5.

[9] 朱曉攀，陳實(shí).基于DDS的像質(zhì)處理提升仿真系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].系統(tǒng)工程與電子技術(shù)，2018，40（8）：1881?1888.

[10] AHMED R， LIMAM N， XIAO J， et al. Resource and service discovery in large?scale multi?domain networks [J]. IEEE communications surveys amp; tutorials， 2007， 9（4）： 2?30.

[11] LUO L， GUO D， MA R T， et al. Optimizing bloom filter： challenges， solutions， and comparisons [J]. IEEE communications surveys amp; tutorials， 2018， 21（2）： 1912?1949.

[12] TARKOMA S， ROTHENBERG C E， LAGERSPETZ E. Theory and practice of bloom filters for distributed systems [J]. IEEE communications surveys amp; tutorials， 2011， 14（1）： 131?155.

[13] SANCHEZ?MONEDERO J， POVEDANO?MOLINA J， LOPEZ?VEGA J M， et al. Bloom filter?based discovery protocol for DDS middleware [J]. Journal of parallel and distributed computing， 2011， 71（10）： 1305?1317.

[14] 李卓宇，夏必勝，馬樂(lè)榮.布隆過(guò)濾器算法誤判率的分析與應(yīng)用[J].延安大學(xué)學(xué)報(bào)（自然科學(xué)版），2021，40（1）：68?71.

[15] MITZENMACHER M. Compressed bloom filters [J]. Networ?king IEEE/ACM transactions on， 2001， 10（5）： 604?612.

[16] LIU P， JIANG C， ZHANG X， et al. Compressed bloom filter method of DDS middleware based on FPGA [C]// Proceedings of the 2021 7th International Conference on Computer and Communications. Tianjin： IEEE， 2021： 27?34.

[17] JANG S， BYUN H， LIM H. Dynamically allocated bloom filter?based PIT architectures [J]. IEEE access， 2022， 10： 28165?28179.

[18] NWADIUGWU W P， CHA J H， KIM D S. Enhanced SDP?dynamic bloom filters for a DDS node discovery in real?time distributed systems [C]// Emerging Technologies and Factory Automation. [S.l.]： IEEE， 2017： 767.

[19] LIU Z， ZHAO Z. Data distribution service based on symbol bloom filter for large?scale distributed computing [C]// 2022 7th International Conference on Cloud Computing and Big Data Analytics. [S.l.]： IEEE， 2022： 112?116.

[20] 樊智勇，騰達(dá)，劉哲旭.基于單哈希多維布隆過(guò)濾器的DDS自動(dòng)發(fā)現(xiàn)算法[J].計(jì)算機(jī)應(yīng)用與軟件，2021，38（10）：273?277.

[21] Object Management Group. OMG data distribution service （DDS） version 1.4 [EB/OL]. [2015?04?10]. https：//www.omg.org/spec/DDS/1.4.

[22] TEKINERDOGAN B， ?ELIK T， K?KSAL ?. Generation of feasible deployment configuration alternatives for data distribution Service based systems [J]. Computer standards amp; interfaces， 2018， 58： 126?145.

[23] BLOOM B H. Space/time trade?offs in hash coding with allowable errors [J]. Communications of the ACM， 1970， 13（7）： 422?426.

[24] CHRISTENSEN K， ROGINSKY A， JIMENO M. A new analysis of the 1 positive rate of a bloom filter [J]. Information processing letters， 2010， 110（21）： 944?949.

[25] 華文鏑，高原，呂萌，等.布隆過(guò)濾器研究綜述[J].計(jì)算機(jī)應(yīng)用，2022，42（6）：1729?1747.

[26] 張曉敏.基于布隆過(guò)濾器屬性基的多關(guān)鍵詞可搜索方案[J]. 計(jì)算機(jī)與現(xiàn)代化，2021（8）：104?111.

作者簡(jiǎn)介：劉黃彪（1998—），男，湖北黃石人，碩士研究生，主要研究方向?yàn)槊裼蔑w機(jī)航電系統(tǒng)設(shè)計(jì)。

楊" 凡（1996—），男，安徽和縣人，碩士研究生，主要研究方向?yàn)槊裼蔑w機(jī)航電系統(tǒng)設(shè)計(jì)。

宋" 歌（1986—），男，河南洛陽(yáng)人，碩士研究生，研究員，主要研究方向?yàn)槊裼蔑w機(jī)航電系統(tǒng)設(shè)計(jì)。

王峰?。?968—），男，江西南昌人，研究員，主要研究方向?yàn)槊駲C(jī)機(jī)載軟件、IMA、航電數(shù)據(jù)網(wǎng)絡(luò)。

張" 琦（1993—），男，河南漯河人，博士研究生，講師，主要研究方向?yàn)楣怆娦畔⒓夹g(shù)。

張小貝（1982—），男，湖北宜城人，博士研究生，教授，主要研究方向?yàn)楣怆娦畔⒓夹g(shù)。