虛擬試驗中基于匹配特性融合的內(nèi)容網(wǎng)絡(luò)匹配算法

吳鋒，高麗敏，楊彩瓊，冷林濤，李曉瑜，陸超

(1.西北工業(yè)大學(xué)動力與能源學(xué)院 西安 710000；2.中國航發(fā)四川燃?xì)鉁u輪研究院 四川綿陽 621000；3.電子科技大學(xué)信息與軟件工程學(xué)院 成都 610054)

“虛實結(jié)合”的虛擬試驗系統(tǒng)往往采用分布式的子系統(tǒng)部署[1]。實際工作過程中，子系統(tǒng)之間通訊的高效和穩(wěn)定是整個虛擬試驗系統(tǒng)的關(guān)鍵。發(fā)布/訂閱模型是屬于分布式環(huán)境中應(yīng)用程序之間通信模型的一種，能夠適應(yīng)動態(tài)多變的分布式系統(tǒng)的需求[2]。此模型讓分布式系統(tǒng)中各程序發(fā)生交互時使用其特有的發(fā)布/訂閱的方式。從訂閱語言的角度來看，可以將發(fā)布/訂閱系統(tǒng)分為基于主題的和基于內(nèi)容兩類[3]。在內(nèi)容發(fā)布/訂閱系統(tǒng)中，約束條件通過事件內(nèi)容來體現(xiàn)，以增強訂閱的靈活性。當(dāng)用戶發(fā)布一個事件時，需要系統(tǒng)將每個約束條件與對應(yīng)的事件進行匹配。但由于系統(tǒng)中每個訂閱都需要較大數(shù)目的約束條件，所以事件匹配效率也需要有所提高[4]。目前主流的基于內(nèi)容的發(fā)布訂閱匹配算法中，對于匹配過程的精簡算法主要有兩種方法：以匹配網(wǎng)絡(luò)等數(shù)據(jù)結(jié)構(gòu)為代表的剪枝法和以索引列表為代表的精確定位法[5]。這兩種方法在特定情形下表現(xiàn)都不穩(wěn)定，無法滿足變化多端的應(yīng)用環(huán)境需求。

目前主要的匹配算法都可以歸為兩個類別：基于索引的和基于樹的[6]。這些算法可進一步按照是否基于關(guān)鍵字進行分類，基于關(guān)鍵字代表選擇一組謂詞作為表達式的表示符。索引方法的主要目的是通過對所有分離的謂詞構(gòu)建逆序的索引順序，以盡量減少謂詞的評估數(shù)量[7]。基于樹的匹配方法的主要目的則是通過樹形結(jié)構(gòu)對訂閱條件建立索引，從而提高匹配效率。而針對這些匹配算法在匹配過程中進行的優(yōu)化方式主要有以下兩個特性。

1)利用訂閱間存在的覆蓋關(guān)系形成偏序樹結(jié)構(gòu)，當(dāng)遇到不匹配的訂閱時，可知其覆蓋的所有訂閱都不符合匹配規(guī)則，從而對其進行剪枝操作，以達到減少訂閱規(guī)模的目的。如Siena[6]系統(tǒng)中的偏序樹匹配算法，這種方法對訂閱之間的關(guān)系要求較高，如果訂閱之間存在大量的覆蓋關(guān)系，則效果較好；如果訂閱間很少存在覆蓋關(guān)系或幾乎不存在覆蓋關(guān)系，例如存在大量事件屬性，則會退化為暴力匹配的方式，嚴(yán)重影響匹配性能。還有一種對偏序樹結(jié)構(gòu)進行剪枝的方式是對特定屬性部分剪枝，這種方式將訂閱組織為匹配網(wǎng)絡(luò)，保留匹配過程中的所有信息，能夠充分利用謂詞間的相關(guān)性，匹配時利用過往匹配信息進行大量的迅速的剪枝，匹配效率較高，但結(jié)構(gòu)較復(fù)雜，難以支持動態(tài)訂閱變更[8]。文獻[5]提到了一種基于樹的匹配算法，在原本樹的結(jié)構(gòu)上添加了一條額外的出邊，該邊可以檢測出與該節(jié)點謂詞測試結(jié)果無關(guān)的訂閱，并且使用該方法后匹配事件的復(fù)雜度與訂閱數(shù)線性相關(guān)。但是由于其取消和添加訂閱的處理方式是以改變量為主，因此當(dāng)用戶更新訂閱時得不到及時的反饋。

2)將訂閱的屬性分離，利用哈希算法迅速定位屬性位置，再利用區(qū)間樹、有序表等方式較快地查找到匹配屬性。這樣做可以大量減少無關(guān)屬性的檢測，并且由于屬性的分離特性，對原訂閱的結(jié)構(gòu)無要求，當(dāng)事件屬性數(shù)目增加時，匹配速度由于屬性的查找是哈希的原因，反而會提高。但訂閱屬性的分離也破壞了訂閱之間的關(guān)系信息，從而無法利用訂閱之間的覆蓋關(guān)系來進行匹配優(yōu)化，并且由于訂閱和屬性之間失去關(guān)聯(lián)，會造成大量的無意義匹配[9]。在謂詞索引方面，對于等值謂詞，可以使用哈希表的存儲方式達到高效率的查找，對于區(qū)間謂詞，可以考慮使用區(qū)間樹或有序表的方式加以存儲[10]。而對謂詞進行索引的相關(guān)算法的主要代表有計數(shù)算法：對所有謂詞進行測試，建立一個映射表，該表包含的兩個元素分別是謂詞和訂閱，開始進行匹配時，將表中的該訂閱所對應(yīng)的謂詞數(shù)與該訂閱原本含有的謂詞數(shù)進行比較，相等即可得出事件與訂閱相匹配。漢森算法通過測試淘汰一部分訂閱，接著從剩下的這些訂閱中測試，這樣可以讓效率進一步提高。CEEM 算法[5]以構(gòu)建謂詞表對謂詞族進行劃分，其索引的構(gòu)建方式采用的是排序或哈希表，能夠以更高的效率對謂詞進行匹配；并且可以依靠謂詞之間所具有的關(guān)聯(lián)性進一步提高匹配速度。這類算法雖然能夠支持動態(tài)訂閱，但只考慮了謂詞間的關(guān)聯(lián)關(guān)系，不能高效地完成事件匹配[11]。

還有一些算法欲將這兩個特性相結(jié)合，如BETree 和PRBT-Tree[12]。BE-Tree 用屬性來進行聚類集合，用值進行分類集合，通過劃分小集團的方法來提高匹配效率，當(dāng)屬性維度較高且訂閱之間相關(guān)性較小時表現(xiàn)較好[13]。PRBT-Tree 利用謂詞的區(qū)間性質(zhì)建立同時存在覆蓋和偏序關(guān)系的樹結(jié)構(gòu)，但由于仍然無法避免屬性分離的限制，最終只是單屬性查找時的剪枝而不是大粒度的整體剪枝[14]。由于訂閱覆蓋和屬性分離在本質(zhì)上是矛盾的，因此，這些方法最終淪落為在分離的屬性上進行覆蓋檢測的方式。

綜上所述，考慮到訂閱匹配時的不同特性，如果能夠?qū)⒕邆洳煌匦缘挠嗛営行У胤蛛x開，分別使用不同的適合其特性的匹配方法，便可以大大地提高匹配效率。本文在對已有事件匹配算法進行分析的基礎(chǔ)上，提出了一種基于匹配特性融合的內(nèi)容網(wǎng)絡(luò)匹配算法(hybrid matching algorithm for contentbased delivery,HMACD)，提供了高效的匹配性能，并通過實驗和性能分析驗證了該匹配算法的優(yōu)越性。

1 混合事件匹配算法

1.1 相關(guān)定義

定義1事件，謂詞，訂閱。事件E作為實體交互單元出現(xiàn)在發(fā)布/訂閱系統(tǒng)中，包含了屬性a的序列[a1,a2,···,an]。一個屬性值v的記錄[v1,v2,···,vn]叫做事件實例e。基于典型的條件變量P::=acv，訂閱謂詞可以描述為P::=acv的形式，即關(guān)于事件屬性的一系列限制。由基本的謂詞可以構(gòu)成不同的訂閱(條件)Φ::=Φ∧P|Φ∨P|P。

定義2偏序關(guān)系。如果訂閱間存在覆蓋關(guān)系，則稱它們之間的關(guān)聯(lián)為偏序關(guān)系，偏序關(guān)系可以用偏序樹來存儲。

定義3無偏關(guān)系。如果訂閱間不存在覆蓋關(guān)系，則稱它們之間的關(guān)聯(lián)為無偏關(guān)系。圖1 虛框和虛線之間的訂閱關(guān)系為無偏關(guān)系。

圖1 無偏關(guān)系及最大無偏關(guān)系示意圖

定義4最大無偏關(guān)系訂閱列表。在所有訂閱中，滿足無偏關(guān)系的所有訂閱組成了最大無偏關(guān)系訂閱列表。圖1 中，虛線連接的4 個訂閱組成了一個最大無偏關(guān)系訂閱列表。

1.2 算法的數(shù)據(jù)結(jié)構(gòu)

算法的數(shù)據(jù)結(jié)構(gòu)主要分為兩部分：樹形結(jié)構(gòu)部分和索引結(jié)構(gòu)部分[15]。對于樹形結(jié)構(gòu)部分，采用Siena 中的基于poset 的偏序樹結(jié)構(gòu)，這是因為其高效的剪枝策略避免了許多不必要的匹配過程。對于索引結(jié)構(gòu)部分，采用相比較其他算法而言效率出色的區(qū)間樹索引和哈希表結(jié)合的結(jié)構(gòu)。區(qū)間樹是一種元素為區(qū)間的操作樹，每個節(jié)點的關(guān)鍵值與每個區(qū)間的左端點相對應(yīng)[16]。這樣的結(jié)構(gòu)可以讓其元素在無論是查找或插入的情況下都可以將時間復(fù)雜度保持在O(lgn)內(nèi)，而哈希表的定位復(fù)雜度為O(1)。

數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵是決定何時將偏序樹中“溢出”的訂閱加入到索引結(jié)構(gòu)中[17]。通過分析偏序樹中的結(jié)構(gòu)，得出兩種結(jié)論：1)過多的游離根節(jié)點可以加入?yún)^(qū)間樹結(jié)構(gòu)；2)具有過多兄弟節(jié)點的葉子節(jié)點可以加入?yún)^(qū)間樹結(jié)構(gòu)。下面是算法中主要的數(shù)據(jù)結(jié)構(gòu)。

偏序樹(poset-tree)：將訂閱項組織成偏序森林，偏序關(guān)系為上覆蓋下，即如果訂閱條件滿足下層的條件，那么它一定也滿足所有上層的條件；如果上層條件不滿足，那么其所有后繼一定不滿足事件條件，無需繼續(xù)遍歷[18]，越往下條件越嚴(yán)格。這種整體的偏序結(jié)構(gòu)在事件匹配時平均效率較高，無需遍歷所有訂閱，可以在匹配的過程中淘汰相當(dāng)一部分的訂閱條件。但如果給出的訂閱之間不存在覆蓋關(guān)系或者覆蓋關(guān)系較少，則這種偏序森林的結(jié)構(gòu)會退化為單一節(jié)點的結(jié)構(gòu)，匹配效率也會退化為和暴力匹配相當(dāng)?shù)乃健?/p>

在實際應(yīng)用過程中，無偏關(guān)系通常存在于偏序樹中同父的葉子節(jié)點之間，本文規(guī)定當(dāng)無偏訂閱的數(shù)量達到一定限度時，將其存入?yún)^(qū)間樹索引結(jié)構(gòu)中去。

區(qū)間樹索引(interval tree-index)：將訂閱進行各個屬性的分離，按屬性及操作符建立更加細(xì)粒度的索引結(jié)構(gòu)。索引結(jié)構(gòu)采用具備多級索引的區(qū)間樹和哈希列表相結(jié)合的方式[19]。以屬性名稱建立第一級索引，對于等值謂詞加入相應(yīng)屬性的值為鍵值的哈希列表中，對于區(qū)間謂詞，加入相應(yīng)屬性的區(qū)間樹中。

混合結(jié)構(gòu)：將兩種結(jié)構(gòu)結(jié)合起來，對于到來的訂閱，首先將其加入到偏序樹結(jié)構(gòu)中，如果新加入的訂閱滿足最大無偏關(guān)系，則加入到索引訂閱列表中，如圖2 所示。

圖2 混合事件匹配算法數(shù)據(jù)結(jié)構(gòu)

匹配桶：用于索引結(jié)構(gòu)匹配時存儲暫時符合若干條件的訂閱。匹配是根據(jù)到來事件的值逐條進行的，有些訂閱達到了部分條件，但還沒有完全達到可以發(fā)送的條件，便暫時存儲到匹配桶中，防止匹配信息的丟失[20]。匹配桶是set 的結(jié)構(gòu)，即只允許加入不同的訂閱，當(dāng)執(zhí)行加入匹配桶中已存在的訂閱時，該執(zhí)行失敗。

接口列表和訂閱列表：所有加入謂詞表的訂閱都會被存儲登記在訂閱列表中，其記錄內(nèi)容為該訂閱謂詞集合中的第一個謂詞的指針，這樣做的目的是可以方便訪問所有位于謂詞表中的謂詞。接口是指事件的傳送方向。一個連接的訂閱信息僅對應(yīng)一個接口，每個連接可以有多個訂閱，通過訂閱列表和接口列表將所有的訂閱組織在一起[21]。接口列表和訂閱列表都是針對索引結(jié)構(gòu)的，對于偏序樹結(jié)構(gòu)而言，訂閱信息和接口信息都存儲在節(jié)點中。

1.3 訂閱處理流程

當(dāng)接收到新的訂閱后，需要將該訂閱加入到相應(yīng)的數(shù)據(jù)結(jié)構(gòu)中。算法的關(guān)鍵是決定在何種情況下將訂閱加入哪個集合，判別方法首先將訂閱加入樹結(jié)構(gòu)的偏序集中，如果新加入的節(jié)點滿足最大無偏關(guān)系，則將其移入索引結(jié)構(gòu)中的索引訂閱列表中[13]。

訂閱過程：

1)將訂閱s加入到樹形結(jié)構(gòu)poset-trees 中；

2)如果s在poset-trees 中是單獨的根節(jié)點并且超出了獨立根節(jié)點的上限個數(shù)，則將其移入到index-tables 中；

3)如果s在poset-trees 中是葉節(jié)點并且超出了當(dāng)前同前驅(qū)葉節(jié)點的上限個數(shù)，則將其移入到index-tables 中。

當(dāng)需要取消某訂閱時，需要分別在兩種結(jié)構(gòu)中查找該訂閱。在索引集中，可以直接查找訂閱集合；在樹結(jié)構(gòu)偏序集中需要遍歷整個樹結(jié)構(gòu)，查找到該訂閱執(zhí)行刪除操作。

取消訂閱過程：

1)在索引結(jié)構(gòu)的訂閱列表中查找要取消的訂閱，找到之后，將其所鏈接的所有屬性節(jié)點在相應(yīng)的哈希表或區(qū)間樹中刪除，如果是在區(qū)間樹中刪除的話則需重新調(diào)整區(qū)間樹。最后在訂閱列表中刪除該訂閱。如果沒有找到，則進行步驟2)；

2)在poset-trees 中從根節(jié)點開始遍歷各個節(jié)點，直到找到包含要取消的訂閱節(jié)點為止。找到之后，如果要取消的節(jié)點是該節(jié)點所包含的唯一節(jié)點，則直接刪除該訂閱；如果不是，則需要刪除該節(jié)點并將該節(jié)點的所有前驅(qū)、后繼節(jié)點相連。

1.4 事件匹配流程

當(dāng)事件到來時，由于滿足該事件的訂閱在兩種集合中都存在，因此需要分別遍歷偏序集和索引結(jié)構(gòu)這兩個集合來找到匹配事件的所有訂閱。

匹配過程：

1)在樹形結(jié)構(gòu)內(nèi)進行匹配。首先創(chuàng)建匹配候選集Sa和匹配成功集Sm，將所有偏序樹的根節(jié)點加入匹配候選集中；接著依次對匹配候選集中的所有根節(jié)點進行遍歷，判斷其每一個根節(jié)點是否與當(dāng)前事件匹配；如果匹配，則將該根節(jié)點的后繼節(jié)點加入到匹配候選集中，同時，將該節(jié)點加入到匹配成功集中，然后繼續(xù)進行匹配；如果匹配不成功，則將其從匹配候選集移除，直到該集合為空時，遍歷結(jié)束，返回最終存有與該事件相匹配的所有訂閱的匹配成功集Sm。

2)在索引結(jié)構(gòu)中進行匹配。分解事件的謂詞，創(chuàng)建存有匹配當(dāng)前事件的所有訂閱集合result，以及匹配桶bucket，先在哈希列表中找到對應(yīng)該謂詞屬性的列表，接著在該列表中找到該謂詞的值的條目，將該條目對應(yīng)的所有訂閱加入到匹配桶中；然后在區(qū)間森林中找到對應(yīng)該謂詞屬性的區(qū)間樹，在該區(qū)間樹中定位到該值對應(yīng)的節(jié)點，將該節(jié)點上的條目所對應(yīng)的所有訂閱加入到匹配桶中。當(dāng)處理完一個屬性的謂詞后，需要對匹配桶中的所有訂閱執(zhí)行匹配屬性加一的操作。然后檢查匹配中的內(nèi)容，如果匹配桶中存在達到匹配要求的操作，便將該節(jié)點對應(yīng)的訂閱加入到result 集合中，并在匹配桶中移除該訂閱。然后檢查事件的下一個屬性，執(zhí)行同樣的操作。當(dāng)該事件的所有謂詞處理完成時，清空匹配桶，以備下一次事件到來時使用。此時的result 集合中已經(jīng)包含了所有匹配當(dāng)前事件的訂閱，作為最終算法輸出結(jié)果返回，以進行下一步的轉(zhuǎn)發(fā)動作。

算法1 在偏序集中匹配

算法2 在索引結(jié)構(gòu)中匹配

1.5 算法分析

訂閱 Φ與事件e的匹配過程不僅與事件參數(shù)相關(guān)，還跟時間t相關(guān)，看作Φ(e,t)。假設(shè)某訂閱進程Pi的訂閱為 Φi，Pi的訂閱只在t0時刻變更，在Φi上發(fā)生的事件匹配是確定的。即：?e,?t≥t0,Φi(e,t)成立，或?t≥t0?Φi(e,t)成立。

活性定義為：若Φi(e,t0)在時間t0后發(fā)布的事件e被進程Pi匹配。訂閱的活性指訂閱更新的延遲對訂閱匹配的影響。訂閱過程中，訂閱變更初始時刻位為t0，訂閱變更結(jié)束時刻為tf。通常tf?t0不做限制，只通過減小其差值的方式提高系統(tǒng)活性。該混合事件匹配算法降低了訂閱變更的時間，即減小tf?t0的值，使事件過濾更加精細(xì)，進而提高系統(tǒng)活性。

在具有混合結(jié)構(gòu)的事件匹配復(fù)雜度方面，假設(shè)訂閱數(shù)為S，屬性數(shù)目為A。在索引結(jié)構(gòu)中的屬性索引表中查找屬性的復(fù)雜度為O(1)，哈希查找的復(fù)雜度為O(1)，區(qū)間樹查找的復(fù)雜度為O(logM)，事件e所含屬性數(shù)目為j，其中M為區(qū)間樹中包含的所有節(jié)點數(shù)目，M的最大值為S，因此在索引結(jié)構(gòu)中查找單個屬性的復(fù)雜度為O(logS)。最壞的情況下需要查找所有屬性，所以綜合復(fù)雜度為O(AlogS)；在Poset 結(jié)構(gòu)中，由于偏序結(jié)構(gòu)的存在，只需遍歷根節(jié)點和部分后繼節(jié)點即可。最壞的情況下，即事件不會匹配任何訂閱時，需要遍歷所有節(jié)點，此時的復(fù)雜度為O(AS)。但是這種情況很少會發(fā)生，一方面是因為很少會出現(xiàn)無意義的事件，另一方面是由于有著最大無偏的設(shè)定，過多的游離節(jié)點已經(jīng)被加入到索引結(jié)構(gòu)中。這里的偏序結(jié)構(gòu)規(guī)模是有限的，因此可以認(rèn)為復(fù)雜度為常數(shù)。因此，綜合來看，總的復(fù)雜度為O(logS)。

2 實驗與結(jié)果

2.1 實驗設(shè)計與規(guī)則

為了對比混合匹配算法、基于索引的匹配算法和基于樹結(jié)構(gòu)的匹配算法的效率差異，本文選取了以Poset 為基礎(chǔ)的Siena 匹配方法以及基于索引的counting 算法進行對比。實驗環(huán)境方面選取1 臺路由服務(wù)器和9 臺主機，其中服務(wù)器用于運行各匹配算法，3 臺主機用于發(fā)布，6 臺主機用于訂閱。以某武器系統(tǒng)的對抗試驗在HLA 仿真系統(tǒng)中測試為例，定義其訂閱實體和發(fā)布實體分別為戰(zhàn)術(shù)雷達和戰(zhàn)斗機。并采用以下數(shù)據(jù)產(chǎn)生規(guī)則。

數(shù)據(jù)類型(value type)：int float bool string

屬性名稱(value name)：數(shù)據(jù)屬性的名稱，首先隨機生成若干長度為5 的字符串，屬性名在其中隨機選取。

操作符(operator)：對于int float 而言，支持>,<,=,≤,≥這5 種操作符。對于bool string 而言，支持=操作符。具體實驗數(shù)據(jù)如表1 所示。

表1 實驗的參數(shù)設(shè)置

2.2 實驗結(jié)果與分析

實驗中，根據(jù)表1 中的兩組參數(shù)，設(shè)置實驗樣本數(shù)為50000，取樣間隔設(shè)置為5000，記錄下每次取樣后訂閱插入以及匹配200 個事件的時間損耗。

兩組實驗結(jié)果如圖3 和圖4 所示。可以看出，在事件匹配的效率比較方面，隨著訂閱數(shù)量不斷增加，其匹配時間也隨之線性增長，這在3 種算法中都得到了體現(xiàn)。但是由于HMACD 算法訂閱中不同的匹配特性采取了不同的匹配策略，其斜率遠(yuǎn)遠(yuǎn)小于另外兩種算法，即在訂閱數(shù)量一致時，與另外兩種匹配算法相比，HMACD 算法的匹配效率更加出色。以兩圖中訂閱數(shù)量為10000 時的匹配時間為例，HMACD 算法的匹配時間耗時僅為基于Poset 的Siena 算法和Couting 算法的54%和45%。并且在事件匹配總體效果方面，通常情況下，隨著訂閱數(shù)目的增加，Poset 的偏序關(guān)系越發(fā)明顯，匹配效果也會變好，而Counting 算法隨著訂閱數(shù)目的增加，單個屬性謂詞的查找效率會降低，因而匹配效果越來越差。HMACD 算法綜合了兩種算法的優(yōu)點，匹配效果始終維持在一個相對不錯的水準(zhǔn)。

圖3 實驗1 匹配時間

圖4 實驗2 匹配時間

可見，相對于其他算法，HMACD 算法在保持不錯的匹配效果的情況下有效的提高了事件匹配的效率。

3 結(jié)束語

隨著算法交易和分布虛擬環(huán)境等新應(yīng)用的不斷涌現(xiàn)，對系統(tǒng)底層的事件匹配算法提出更加高效的處理要求。本文融合了偏序結(jié)構(gòu)和索引結(jié)構(gòu)的不同匹配特性，提出了一種混合的事件匹配算法。算法將具備不同特性的訂閱組織分別組織到不同的數(shù)據(jù)結(jié)構(gòu)中，并采用不同的匹配方法，充分利用了不同訂閱的特點，提升了匹配效率。實驗表明，與同類算法相比，該算法的匹配效率更高，能夠滿足相關(guān)應(yīng)用需求。下一步工作準(zhǔn)備從路由算法、訂閱表達方式方面進行研究，以提高系統(tǒng)性能為主，從而能夠廣泛適用于更多的應(yīng)用需求。