基于服務(wù)力向量的發(fā)布/訂閱自動(dòng)發(fā)現(xiàn)算法

翟海波,莊 毅,霍 瑛

(南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,南京210016)

基于服務(wù)力向量的發(fā)布/訂閱自動(dòng)發(fā)現(xiàn)算法

翟海波,莊 毅,霍 瑛

(南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,南京210016)

由于SDPBloom自動(dòng)發(fā)現(xiàn)算法無(wú)法預(yù)先在參與者發(fā)現(xiàn)階段對(duì)端點(diǎn)QoS策略的兼容性進(jìn)行判斷,使得各節(jié)點(diǎn)和網(wǎng)絡(luò)中均出現(xiàn)大量QoS不兼容的端點(diǎn)信息,從而消耗過(guò)多的內(nèi)存和網(wǎng)絡(luò)資源。為解決該問(wèn)題,提出一種基于服務(wù)力向量(SAV)的發(fā)布/訂閱自動(dòng)發(fā)現(xiàn)算法,利用布隆過(guò)濾器向量和SAV對(duì)端點(diǎn)主題名、主題類(lèi)型以及QoS策略進(jìn)行匹配,以減少不必要信息的傳輸和存儲(chǔ)。實(shí)驗(yàn)結(jié)果表明,與SDP_ADA和SDPBloom算法相比,該算法具有更低的網(wǎng)絡(luò)負(fù)載和內(nèi)存消耗。

服務(wù)力向量;發(fā)布/訂閱;數(shù)據(jù)分發(fā)服務(wù);自動(dòng)發(fā)現(xiàn)算法;布隆過(guò)濾器;服務(wù)質(zhì)量

1 概述

數(shù)據(jù)分發(fā)服務(wù)(Data Distribution Service, DDS)是一種以數(shù)據(jù)為中心的高性能網(wǎng)絡(luò)數(shù)據(jù)交換中間件。國(guó)際對(duì)象管理組織(Object Management Group,OMG)先后在 2004年、2005年、2007年頒布了數(shù)據(jù)分發(fā)服務(wù) Version 1.0[1], Version1.1[2]以及 Version1.2[3]規(guī)范。該規(guī)范為DDS中間件的設(shè)計(jì)提供了指南,以及為實(shí)現(xiàn)不同平臺(tái)之間的信息交互提供了標(biāo)準(zhǔn)。DDS實(shí)體通信采用發(fā)布-訂閱通信模式,該模式實(shí)現(xiàn)了時(shí)間、空間和同步關(guān)系3個(gè)方面的完全解耦,使得它成為現(xiàn)代分布式計(jì)算環(huán)境的理想選擇[4]。目前,該技術(shù)已經(jīng)被成功應(yīng)用到航空控制系統(tǒng)、海軍作戰(zhàn)管理系統(tǒng)、自動(dòng)股票交易系統(tǒng)、工業(yè)控制系統(tǒng)以及監(jiān)測(cè)控制與數(shù)據(jù)采集系統(tǒng)[5]中。

為了支持在分布式系統(tǒng)中各節(jié)點(diǎn)能夠動(dòng)態(tài)加入和退出且不影響其他節(jié)點(diǎn)功能的特性,DDS中參與通信的所有實(shí)體間需要能夠動(dòng)態(tài)地發(fā)現(xiàn)對(duì)方,然后根據(jù)主題、數(shù)據(jù)類(lèi)型以及服務(wù)質(zhì)量(Quality of Service,QoS)策略進(jìn)行匹配,只有匹配成功后才會(huì)建立通信連接[6-7]。本文重點(diǎn)研究和分析了發(fā)布/訂閱自動(dòng)發(fā)現(xiàn)過(guò)程,并提出一種新的自動(dòng)發(fā)現(xiàn)算法。

2 相關(guān)研究工作

針對(duì)動(dòng)態(tài)自動(dòng)發(fā)現(xiàn)過(guò)程,國(guó)內(nèi)外已相繼提出大量自動(dòng)發(fā)現(xiàn)算法。該動(dòng)態(tài)發(fā)現(xiàn)過(guò)程既可以在網(wǎng)絡(luò)層上完成,也可以在更高的應(yīng)用層上完成。在網(wǎng)絡(luò)層上完成該過(guò)程的主要有基于SLP,SSDP以及DNSSD等協(xié)議的自動(dòng)發(fā)現(xiàn)算法[8]。近年來(lái),更多的自動(dòng)發(fā)現(xiàn)過(guò)程都是在應(yīng)用層完成的,如文獻(xiàn)[8]提出的一種基于普適發(fā)現(xiàn)協(xié)議(Pervasive Discovery Protocol, PDP)的自動(dòng)發(fā)現(xiàn)算法,該算法集成了“推”和“拉”2種模型去發(fā)現(xiàn)對(duì)方。2010年 RTI(Real-time Innovations)根據(jù)RTPS標(biāo)準(zhǔn)2.1版本[9]給出了一種基于簡(jiǎn)單發(fā)現(xiàn)協(xié)議(Simple Discovery Protocol,SDP)的自動(dòng)發(fā)現(xiàn)算法[10]。為了方便后續(xù)說(shuō)明,本文用SDP_ADA(Simple Discovery Protocol Automatic Discovery Algorithms)表示該算法。SDP_ADA算法執(zhí)行過(guò)程分為2個(gè)階段:簡(jiǎn)單參與者發(fā)現(xiàn)階段和簡(jiǎn)單端點(diǎn)發(fā)現(xiàn)階段。簡(jiǎn)單參與者發(fā)現(xiàn)階段實(shí)現(xiàn)參與者之間的相互學(xué)習(xí),簡(jiǎn)單端點(diǎn)發(fā)現(xiàn)階段實(shí)現(xiàn)數(shù)據(jù)寫(xiě)入者和數(shù)據(jù)讀取者的信息匹配。文獻(xiàn)[5]指出SDP_ ADA算法只適合中小型網(wǎng)絡(luò),存在可擴(kuò)展性差等問(wèn)題,并提出一種基于布隆過(guò)濾器的自動(dòng)發(fā)現(xiàn)算法SDPBloom。該算法依然遵循SDP協(xié)議的階段模型,但是該算法在參與者發(fā)現(xiàn)階段將各個(gè)參與者包含的端點(diǎn)描述信息放到布隆過(guò)濾器向量(Bloom Filter Vector,BFV)中并通過(guò)參與者數(shù)據(jù)包一起發(fā)給其他遠(yuǎn)程參與者,這些端點(diǎn)描述信息主要包括端點(diǎn)的主題相關(guān)信息,但是不包括 QoS信息。由于SDPBloom算法將端點(diǎn)匹配部分操作提前,即在參與者階段完成,因此一旦發(fā)現(xiàn)本地端點(diǎn)描述信息與遠(yuǎn)程端點(diǎn)信息不匹配,就不需要再將本地端點(diǎn)具體信息發(fā)送給遠(yuǎn)程參與者,從而減少網(wǎng)絡(luò)負(fù)載和內(nèi)存消耗。

綜上所述,DDS是一種以數(shù)據(jù)為中心的網(wǎng)絡(luò)中間件,一個(gè)很重要的特點(diǎn)是有豐富的QoS策略支持。然而,基于PDP協(xié)議的自動(dòng)發(fā)現(xiàn)算法是一種完全分布式的服務(wù)發(fā)現(xiàn)協(xié)議,更多的適用于以服務(wù)為中心的移動(dòng)自組網(wǎng)絡(luò)。盡管SDP_ADA算法可實(shí)現(xiàn)DDS中發(fā)布-訂閱者的自動(dòng)發(fā)現(xiàn),但如文獻(xiàn)[5]所述SDP_ ADA自動(dòng)發(fā)現(xiàn)算法的可擴(kuò)展性較差,只適用于中小型網(wǎng)絡(luò)。然而,SDPBloom算法雖然在可擴(kuò)展性方面做了一些改進(jìn),但是SDPBloom算法在參與者發(fā)現(xiàn)階段完全不考慮QoS,會(huì)帶來(lái)一些不必要信息的傳送,造成網(wǎng)絡(luò)負(fù)載的增加。

3 ISDPBQ_ADA算法

數(shù)據(jù)分發(fā)服務(wù)(DDS)中發(fā)布/訂閱通信雙方除了需要主題匹配外,QoS的相互兼容也是雙方建立通信的必要條件之一。針對(duì)SDPBloom算法無(wú)法在參與者發(fā)現(xiàn)階段對(duì)端點(diǎn)QoS的兼容性進(jìn)行判斷所引起的較高網(wǎng)絡(luò)負(fù)載和內(nèi)存消耗,在該算法的基礎(chǔ)上提出一種新的算法:ISDPBQ_ADA,該算法能夠在參與者發(fā)現(xiàn)階段對(duì)端點(diǎn)QoS的兼容性進(jìn)行粗判,從而進(jìn)一步減少網(wǎng)絡(luò)負(fù)載和內(nèi)存消耗。

3.1 布隆過(guò)濾器

Bloom Filter[11]是由Bloom在1970年提出的二進(jìn)制向量數(shù)據(jù)結(jié)構(gòu),是一種節(jié)省空間的高效數(shù)據(jù)表示和查詢(xún)過(guò)濾器。它利用位數(shù)組簡(jiǎn)潔地表示一個(gè)集合,并能以很高的概率判斷一個(gè)元素是否屬于這個(gè)集合。Bloom Filter利用K個(gè)相互獨(dú)立的哈希函數(shù)Hi(key)(其中,0＜i≤k),將集合S={x1,x2,…,xn}中的元素映射到一個(gè)m位的數(shù)組向量BFV中;開(kāi)始時(shí)BFV中的元素被初始化為0,當(dāng)Hi(xj)=Ri(0＜i≤k,0≤Ri≤m-1)時(shí),那么BFV中第Ri位被置為1[12]。自從Bloom在20世紀(jì)70年代提出 Bloom Filter后,Bloom Filter就被廣泛用于拼寫(xiě)檢查和數(shù)據(jù)庫(kù)系統(tǒng)中,主要應(yīng)用于能夠容忍低錯(cuò)誤率的場(chǎng)合。

與經(jīng)典哈希函數(shù)相比,Bloom Filter最大的優(yōu)勢(shì)是它的空間效率,另一方面,由于Bloom Filter不用處理碰撞,無(wú)論集合中元素有多少,也無(wú)論多少集合元素已經(jīng)加入到位向量中,Bloom Filter在增加或查找集合元素時(shí)所用的時(shí)間都為哈希函數(shù)的計(jì)算時(shí)間。但是,Bloom Filter在判斷某一元素Xi是否屬于集合S時(shí)可能會(huì)把不屬于S中的元素誤認(rèn)為屬于S,這種情況稱(chēng)為誤報(bào)率(False Positive, FP),因此不適合那些零錯(cuò)誤的應(yīng)用場(chǎng)合。在標(biāo)準(zhǔn)的Bloom Filter中對(duì)于使用k個(gè)哈希函數(shù),向m位長(zhǎng)的Bloom Filter中裝入n個(gè)元素后,誤報(bào)率可以由式(1)[5]估算得到:

3.2 服務(wù)力向量

在ISDPBQ_ADA算法的設(shè)計(jì)過(guò)程中,為了能夠在參與者發(fā)現(xiàn)階段對(duì)端點(diǎn)QoS的兼容性進(jìn)行粗判,本文引入服務(wù)力(Service Ability,SA)的概念。

定義1 在Request vs Offered(RxO)模式中,只有當(dāng)offered類(lèi)型值大于等于requested類(lèi)型值,請(qǐng)求方與提供方才能建立通信連接。將[requested類(lèi)型值,offered類(lèi)型值]區(qū)間長(zhǎng)度定義為服務(wù)力,其中, SA越大表示服務(wù)力越強(qiáng)。

根據(jù)定義1,將所有需要滿(mǎn)足RxO模式的QoS策略的服務(wù)力SA所構(gòu)成的集合定義為服務(wù)力向量(Service Ability Vector,SAV)。文獻(xiàn)[1-3]指出需要滿(mǎn)足RxO的QoS策略少于16種,因此,只需給SAV分配2個(gè)字節(jié)(16位)的大小空間,每一位標(biāo)記端點(diǎn)相關(guān)QoS服務(wù)力,初始化時(shí)將這2個(gè)字節(jié)的16位全部置為0。然后,同樣定義一個(gè)哈希函數(shù)并給各個(gè)需要滿(mǎn)足RxO模式的QoS策略賦予唯一的關(guān)鍵值。當(dāng)用戶(hù)試圖減弱端點(diǎn)某些QoS時(shí),即對(duì)于發(fā)布方來(lái)說(shuō)意味著offered類(lèi)型值減小,對(duì)于訂閱方來(lái)說(shuō)意味著requested類(lèi)型值增大,將這些QoS對(duì)應(yīng)的哈希地址置為1;同理,當(dāng)用戶(hù)試圖加強(qiáng)端點(diǎn)某些QoS時(shí),即對(duì)于發(fā)布方來(lái)說(shuō)意味著offered類(lèi)型值增大,對(duì)于訂閱方來(lái)說(shuō)意味著requested類(lèi)型值減小,就將這些QoS對(duì)應(yīng)的哈希地址重新置0。因此,當(dāng)本地參與者收到遠(yuǎn)程參與者數(shù)據(jù)包時(shí),得到最后2個(gè)字節(jié)與本地參與者數(shù)據(jù)包最后2個(gè)字節(jié)段進(jìn)行邏輯“與”操作,結(jié)果不為0表示本地端點(diǎn)與該遠(yuǎn)程端點(diǎn)QoS不兼容,那么該本地端點(diǎn)信息就不需要在網(wǎng)路上進(jìn)行傳播,也就不會(huì)在遠(yuǎn)程節(jié)點(diǎn)上進(jìn)行存儲(chǔ),從而減少內(nèi)存消耗和降低網(wǎng)絡(luò)負(fù)載。

3.3 ISDPBQ_ADA算法描述

由于SDPBloom算法無(wú)法預(yù)先在參與者發(fā)現(xiàn)階段完成對(duì)端點(diǎn)QoS策略兼容性的判斷問(wèn)題,因此可能使得各節(jié)點(diǎn)和網(wǎng)絡(luò)中都出現(xiàn)大量QoS不兼容的端點(diǎn)信息,從而造成不必要的內(nèi)存浪費(fèi)和網(wǎng)絡(luò)傳輸。為了能夠進(jìn)一步減少內(nèi)存消耗和降低網(wǎng)絡(luò)負(fù)載,本文提出一種改進(jìn)的自動(dòng)發(fā)現(xiàn)算法: ISDPBQ_ADA。該算法的主要設(shè)計(jì)思想是在SDPBloom算法的參與者數(shù)據(jù)包后面加上一個(gè)服務(wù)力向量,利用BFV和SAV向量對(duì)端點(diǎn)主題名、主題類(lèi)型以及QoS進(jìn)行匹配。BFV和SAV的構(gòu)造過(guò)程如圖1所示,其中,E表示一個(gè)端點(diǎn);T0,T1,…,Tk表示該端點(diǎn)上的主題;X1,X2,…,Xm表示主題名、主題類(lèi)型等;Q表示主題的服務(wù)質(zhì)量集,集合中的每一個(gè)元素q1,q2,…,qn表示需要滿(mǎn)足RxO模式的QoS(少于16種)。

圖1 BFV與SAV的構(gòu)建過(guò)程

ISDPBQ_ADA算法的參與者發(fā)現(xiàn)階段具體步驟如下:

Step1 構(gòu)建Bloom Filter向量(BFV)以及服務(wù)力向量(SAV)。

Step2 將所有本地端點(diǎn)描述信息加入到BFV和SAV中;BFV存放相關(guān)端點(diǎn)的主題名和主題類(lèi)型的描述信息,SAV存放端點(diǎn)的QoS標(biāo)記。

Step3 向所有遠(yuǎn)程參與者發(fā)送本地參與者數(shù)據(jù)包,同時(shí)接收遠(yuǎn)程參與者發(fā)來(lái)的數(shù)據(jù)包信息。

Step4 當(dāng)收到遠(yuǎn)程參與者發(fā)來(lái)的數(shù)據(jù)包時(shí),獲取BFV和SAV字段,與本地端點(diǎn)信息進(jìn)行比較;若與本地端點(diǎn)相匹配,則將該遠(yuǎn)程參與者信息加入到本地信息庫(kù),并進(jìn)入到端點(diǎn)發(fā)現(xiàn)階段。

Step5 整個(gè)參與者發(fā)現(xiàn)過(guò)程中,當(dāng)參與者或參與者創(chuàng)建的端點(diǎn)信息發(fā)生變化時(shí),將轉(zhuǎn)到Step3繼續(xù)執(zhí)行。

從上述執(zhí)行步驟來(lái)看,參與者發(fā)現(xiàn)階段主要完成本地參與者數(shù)據(jù)包的發(fā)送和遠(yuǎn)程參與者數(shù)據(jù)包的接收。與SDP_ADA和SDPBLoom算法不同之處主要在于參與者數(shù)據(jù)包的變化,它既包含端點(diǎn)的主題信息又包含QoS標(biāo)記信息,其主要目的是為了減少不必要的數(shù)據(jù)傳輸和存儲(chǔ)。

ISDPBQ_ADA算法的端點(diǎn)發(fā)現(xiàn)階段具體步驟如下:

Step1 當(dāng)發(fā)現(xiàn)過(guò)程進(jìn)入端點(diǎn)發(fā)現(xiàn)階段后,向所有本地信息庫(kù)中的遠(yuǎn)程參與者發(fā)送本地端點(diǎn)數(shù)據(jù)包,并接收遠(yuǎn)程端點(diǎn)數(shù)據(jù)包。

Step2 當(dāng)本地參與者接收到遠(yuǎn)程端點(diǎn)數(shù)據(jù)包后,將與本地端點(diǎn)信息進(jìn)行再匹配;如果匹配成功則執(zhí)行Step3,否則執(zhí)行Step4。

Step3 將遠(yuǎn)程端點(diǎn)信息加入到本地信息庫(kù),建立雙方之間的數(shù)據(jù)通信。

Step4 向遠(yuǎn)程參與者發(fā)送類(lèi)似于“本地沒(méi)有相關(guān)的端點(diǎn)”的信息,說(shuō)明發(fā)生誤報(bào)情況。

從上述步驟可以看出,端點(diǎn)發(fā)現(xiàn)階段主要完成對(duì)端點(diǎn)具體信息的再匹配。由于BFV本身存在誤報(bào)率的問(wèn)題,以及SAV無(wú)法檢測(cè)發(fā)布方和訂閱方服務(wù)力同時(shí)加強(qiáng)或減弱的情況,因此為了防止漏報(bào),本文針對(duì)端點(diǎn)QoS服務(wù)力同時(shí)加強(qiáng)或減弱,認(rèn)為雙方的QoS仍是相互兼容的,所以,存在誤報(bào)率的問(wèn)題。

為了便于實(shí)驗(yàn)驗(yàn)證和分析改進(jìn)后的ISDPBQ_ ADA算法在網(wǎng)絡(luò)負(fù)載和內(nèi)存消耗方面的性能,本文引入2個(gè)概念:主題匹配率(Topic Match Ratio, TMR)和 QoS兼容率(QoS Compatibility Ratio, QCR),定義如下:

定義2 主題匹配率是指在系統(tǒng)中實(shí)際主題名、主題類(lèi)型相匹配的端點(diǎn)數(shù)占總體端點(diǎn)數(shù)量的比率,可由式(2)得到:其中,SucMTname,type(E)表示主題名和主題類(lèi)型都匹配成功的事件;Sum(E)表示系統(tǒng)中所有的端點(diǎn)數(shù)量。

定義3 QoS兼容率是指在主題名、主題類(lèi)型都匹配的情況下,主題QoS相互匹配的端點(diǎn)占所有端點(diǎn)數(shù)量的比率,可由式(3)得到:

其中,SucMTname,type(E)表示主題名和主題類(lèi)型都匹配成功的事件;SucMTQoS(E)表示系統(tǒng)中主題QoS成功匹配的事件。

4 仿真實(shí)驗(yàn)與分析

本文實(shí)驗(yàn)應(yīng)用場(chǎng)景如表1所示,分為4組實(shí)驗(yàn),每組實(shí)驗(yàn)中有5個(gè)應(yīng)用程序,每個(gè)應(yīng)用程序上分布10個(gè)端點(diǎn),共50個(gè)端點(diǎn)數(shù)。TM表示主題名和主題類(lèi)型匹配成功的端點(diǎn)個(gè)數(shù),QC表示QoS相互兼容的端點(diǎn)個(gè)數(shù),TMR表示主題匹配率,QCR表示QoS兼容率。如第1組中設(shè)置10個(gè)主題相匹配的端點(diǎn),即TM=10、TMR=0.2,在匹配成功的10個(gè)主題中,只有2個(gè)端點(diǎn)的主題QoS相互兼容,即QC=2、QCR=0.2。實(shí)驗(yàn)結(jié)果如圖2所示。

表1 實(shí)驗(yàn)應(yīng)用場(chǎng)景設(shè)置

圖2 3種發(fā)現(xiàn)算法對(duì)比結(jié)果

圖3給出SDP_ADA,SDPBloom以及ISDPBQ_ ADA 3種自動(dòng)發(fā)現(xiàn)算法在發(fā)現(xiàn)過(guò)程中發(fā)送的數(shù)據(jù)包個(gè)數(shù)在TMR∈[0,1]上的變化趨勢(shì),以及理論值與實(shí)驗(yàn)值的對(duì)比,其中虛線(xiàn)表示理論值。

從圖2、圖3可以看出:

(1)SDP_ADA算法在整個(gè)發(fā)現(xiàn)過(guò)程中發(fā)送的發(fā)現(xiàn)數(shù)據(jù)包數(shù)據(jù)量較SDPBloom和ISDPBQ_ADA算法大,且發(fā)送的發(fā)現(xiàn)數(shù)據(jù)包不隨TMR的變化而變化。因此,SDP_ADA算法較后2種算法需要較大的內(nèi)存來(lái)存儲(chǔ)遠(yuǎn)程端點(diǎn)信息,且系統(tǒng)具有較高的網(wǎng)絡(luò)負(fù)載。TMR越小,SDPBloom和ISDPBQ_ADA算法的優(yōu)勢(shì)越明顯。

(2)ISDPBQ_ADA和SDPBloom算法發(fā)送的數(shù)據(jù)包會(huì)隨著TMR的減小而減小,由于TMR減小表示本地端點(diǎn)與遠(yuǎn)程端點(diǎn)匹配變少,因此需要發(fā)送的本地端點(diǎn)數(shù)據(jù)包就會(huì)較少,且 ISDPBQ_ADA較SDPBloom算法在網(wǎng)絡(luò)中需要傳輸?shù)臄?shù)據(jù)包更少,因此該算法具有更低的網(wǎng)絡(luò)負(fù)載和內(nèi)存消耗。QCR越小,ISDPBQ_ADA算法較SDPBloom算法的優(yōu)勢(shì)越明顯。

(3)通過(guò)實(shí)驗(yàn)可以看出,SDPBloom和ISDPBQ_ ADA算法實(shí)際發(fā)送的發(fā)現(xiàn)數(shù)據(jù)包數(shù)量較理論值低,主要是因?yàn)檫@2個(gè)算法都存在誤報(bào)情況,TMR和QCR都是在忽略誤報(bào)率的情況下得到的,所以端點(diǎn)的實(shí)際匹配率較TMR和QCR值都要高。因此,實(shí)際傳輸數(shù)據(jù)量要大于理論值,而如何縮小實(shí)際值與理論值的差值是進(jìn)一步研究的重點(diǎn)。

圖3 算法隨主題匹配率的變化趨勢(shì)

5 結(jié)束語(yǔ)

本文針對(duì)DDS中相關(guān)自動(dòng)發(fā)現(xiàn)算法進(jìn)行研究,提出一種改進(jìn)的自動(dòng)發(fā)現(xiàn)算法ISDPBQ_ADA,該算法能夠在參與者發(fā)現(xiàn)階段對(duì)端點(diǎn)的服務(wù)質(zhì)量的兼容性進(jìn)行判斷。通過(guò)實(shí)驗(yàn)驗(yàn)證了該算法的正確性和有效性,并且在同等條件下,與 SDP_ADA和SDPBloom算法相比,本文算法具有更低的網(wǎng)絡(luò)傳輸量和內(nèi)存消耗。下一步將研究降低或消除誤報(bào)率,使得實(shí)際發(fā)送的網(wǎng)絡(luò)數(shù)據(jù)包個(gè)數(shù)趨于理論值,從而進(jìn)一步降低網(wǎng)絡(luò)負(fù)載和內(nèi)存消耗。

[1] Object Management Group.Data Distribution Service for Real-time Systems Specification Version1.0[EB/OL]. (2004-11-07).http://www.omg.org/spec/DDS/1.0.

[2] Object Management Group.Data Distribution Service for Real-time Systems Specification Version1.1[EB/OL]. (2005-12-04).http://www.omg.org/spec/DDS/1.1.

[3] Object Management Group.Data Distribution Service for Real-time Systems Specification Version1.2[EB/OL]. (2007-01-12).http://www.omg.org/spec/DDS/1.2.

[4] 劉旭軍,馬 躍.發(fā)布/訂閱通信模式的實(shí)時(shí)性能分析與評(píng)估[J].計(jì)算機(jī)工程,2010,36(20):229-231.

[5] 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 Distri-buted Computing,2011,71(10):1305-1317.

[6] 歐陽(yáng)軍,蔡志明,王希敏.基于DDS中間件的性能測(cè)試[J].艦船電子工程,2011,31(11):136-139.

[7] 張 珺,尹遜和.基于RTI DDS的數(shù)據(jù)分發(fā)中間件的升級(jí)設(shè)計(jì)[J].北京交通大學(xué)學(xué)報(bào),2011,35(5):31-37.

[8] Campo C,García-Rubio C,Lopez A M,et al.PDP:A Lightweight Discovery Protocol for Local-scope Interactions in Wireless Ad Hoc Networks[J].Computer Networks,2006,50(17):3264-3283.

[9] Object Management Group.The Real-time Publishsubscribe WireProtocolDDS Interoperability Wire Protocol Specification Version 2.1[EB/OL].(2009-01-05).http://www.omg.org/spec/DDSI/2.1.

[10] Real-time Innovations,Inc..RTI Connext Core Libraries and Utilities User's Manual Version 5.0[EB/OL]. (2012-08-10).https://support.rti.com/.

[11] Bloom B H.Space/time Trade-offs in Hash Coding with Allowable Errors[J].Communications of the ACM, 1970,13(7):422-426.

[12] Ahmadi M,Wong S.A Memory-optimized Bloom Filter Using an Additional Hashing Function[C]//Proceedings of Global Telecommunications Conference.New Orleans, USA:IEEE Press,2008:1-5.

編輯 陸燕菲

Publish/Subscribe Automatic Discovery Algorithm Based on Service Ability Vector

ZHAI Hai-bo,ZHUANG Yi,HUO Ying
(College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China)

The SDPBloom automatic discovery algorithm can not judge Quality of Service(QoS)compatibility of endpoints in the participants discovery phase in advance,and it makes probably a large number of QoS incompatible endpoints information on the each node and the network,which consumes too much memory and network resources.To solve this problem,this paper proposes an automatic discovery algorithm based on Service Ability Vector(SAV),which can judge whether the topic name and type of endpoints are matched and QoS compatibility by the Bloom Filter Vector

(BFV)and SAV to reduce unnecessary information transmission and storage.Experimental results show that the algorithm has lower memory resource and network transmission consumption than SDP_ADA algorithm and SDPBloom algorithm.

Service Ability Vector(SAV);publish/subscribe;Data Distribution Service(DDS);automatic discovery algorithm;Bloom filter;Quality of Service(QoS)

1000-3428(2014)09-0051-04

A

TP393

10.3969/j.issn.1000-3428.2014.09.011

航空科學(xué)基金資助項(xiàng)目(2010ZC13012);江蘇省普通高校研究生科研創(chuàng)新計(jì)劃基金資助項(xiàng)目(CXZZ13_0171)。

翟海波(1987-),男,碩士研究生,主研方向:分布式計(jì)算,并行計(jì)算;莊 毅,教授、博士生導(dǎo)師;霍 瑛,博士研究生。

2013-09-26

2013-10-25E-mail:zhb_2011_nuaa@126.com