[發明專利]一種基于歷史經驗的謂詞索引匹配方法

在審

• 申請號: 201410318951.3
• 申請日: 2014-07-05
• 公開（公告）號: CN104036052A
• 公開（公告）日: 2014-09-10
• 發明（設計）人: 王海波;吳昱斌;宋俊平;呂品
• 申請（專利權）人: 中國科學院軟件研究所
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F17/27
• 代理公司: 北京科迪生專利代理有限責任公司 11251
• 代理人: 成金玉;孟卜娟

技術領域

本發明屬于分布交互式仿真技術領域，具體涉及一種基于歷史經驗的謂詞索引匹配算法。

背景技術

在分布交互式仿真系統中，地處不同位置上的各種仿真實體通過網絡相連，相互協作以完成某項仿真任務。而在大規模的分布交互式仿真系統中，參與仿真的節點數量以千百計，每個節點模擬實現現實世界中多個實體的狀態和行為，這些仿真節點共處于一個龐大的虛擬環境中每時每刻都在產生大量的仿真數據，如何將這些仿真數據以高效的方式分發給各個仿真節點是關系到系統能否高效運行的關鍵問題。

對于傳統的數據分發方式：單播方式(一對一)、廣播方式(一對全部)，應用到大規模仿真數據分發時，都存在一定的問題。單播方式下，節點向指定的節點發送仿真數據，接收來自其他節點的仿真數據。隨著客戶端數量的增加，節點間一對一的數據交互將極大地增加網絡負載和系統耦合性。廣播方式下，節點將每一份仿真數據都發送給系統中的所有節點，而實際上很多節點并不需要該數據，給網絡帶寬造成很大的浪費，也增加了節點的處理負擔。

相比而言，發布/訂閱方式更能滿足大規模分布式仿真系統對于數據分發效率的要求。在發布/訂閱系統中，節點作為訂閱者向其他節點發送訂閱條件，表達自己對數據的個性化需求，當有節點生成仿真數據(即事件)后，會將數據與訂閱條件進行匹配，將數據分發給真正需要的節點。發布/訂閱方式具有更好的靈活性，實現了發送者與接收者的解耦，增強了系統的可擴展性，也減少了網絡冗余數據，進而提高了數據傳輸效率，因而在大規模數據分發中得到廣泛應用。

發布/訂閱系統是一類中間件系統，系統中的各方之間通過發布/訂閱方式實現交互。

在這一系統中，信息的需求方稱為訂閱者，信息的生產方稱為發布者。訂閱者將其需求的信息發送給中間件，發布者將其生產的信息發送給中間件，由中間件進行信息間的匹配，并將發布者生產的信息準確、及時地發送給對該信息感興趣的訂閱者。

在發布/訂閱系統中，發布者發布的信息稱為事件，每個事件由一個或多個事件謂詞組成；訂閱者發布的需求信息稱為訂閱條件，每個訂閱條件由一個或多個訂閱條件謂詞組成。謂詞可以分為事件謂詞和訂閱條件謂詞，事件謂詞即<屬性，類型，值>三元組，訂閱條件謂詞即<屬性，類型，操作符，值>四元組。事件謂詞之所以沒有操作符這一元素，是因為事件謂詞默認操作符為“＝”(等于)。屬性根據發布/訂閱系統應用背景的不同可有不同的定義，如在一個股票系統中，屬性可以是股票的名稱、股票的價格、股票的交易量等。類型可以是枚舉類型、布爾類型、整數類型、浮點類型、字符類型等。操作符包括了“＝”(等于)、“！＝”(不等于)、“>”(大于)、“<”(小于)等。

在采用發布/訂閱方式的大規模分布式仿真系統中，能否高效地進行數據分發是影響系統運行和管理乃至最終仿真目標能否實現的關鍵問題之一。特別是在“大數據”仿真的情況下，面對海量的信息資源，數據互操作過程卻難以準確獲取所需的信息，存在著信息規模巨大和用戶難以有效獲取之間的矛盾。匹配算法，是解決數據匹配問題的關鍵，它負責快速、準確地找到與給定事件相匹配的全部訂閱條件。

目前現有主流的匹配方法，根據數據結構劃分，大致可以分為三類，一類是以搜索樹、并行搜索樹為代表的樹結構匹配諒法；另一類是以暴力方法、謂詞索引為代表的表結構匹配方法；還有一類是以二叉判定圖為代表的圖結構匹配方法。接下來對這幾類算法進行詳細介紹：

(1)基于樹結構的匹配方法

基于樹結構的匹配方法將訂閱條件組織成樹形結構，樹形結構的每一個非葉子節點代表了對訂閱條件謂詞的判斷，從根節點到葉子節點的一條路徑代表了一個或多個訂閱條件。具有代表性的樹形結構匹配算法有搜索樹匹配算法和并行搜索樹匹配算法。