區間樹在DDM區域匹配中的應用

東北石油大學 計算機與信息技術學院，黑龍江 大慶 163318

東北石油大學 計算機與信息技術學院，黑龍江 大慶 163318

1 引言

現代仿真應用已經從集中式仿真發展到了分布式交互仿真，分布式仿真技術作為一種重要的研究手段正廣泛地應用于軍事以及國民經濟的各個領域[1]，為了實現仿真應用的互操作性和資源的可重用性，美國防部提出了高層體系結構（HLA）仿真框架[2]，HLA體系結構主要由3部分組成：HLA規則、HLA接口規范、HLA對象模型模板[3]。接口規范說明是對HLA的運行時間支撐系統RTI（Runtime Infrastructure）的接口規范的描述。RTI提供了一個通用的、相對獨立的支撐服務程序，將仿真應用與底層的支撐環境分開，從而使各部分可以相對獨立地進行開發。

數據分發管理DDM是RTI提供的六大服務之一[4]，是RTI所提供的一類很重要的服務，其功能是實現數據的過濾，盡可能地減少不相關數據的產生，以減少網絡帶寬的占用，同時降低仿真接收冗余數據時引起的處理開銷[5]。它是實現HLA/RTl的關鍵技術，也是實現大規模分布式交互仿真的可擴展性的重要手段。數據分發管理運用維（dimension）和區域（region）對數據進行過濾。更新成員利用一系列區域組成的更新區域集聲明它要公布的信息，訂購成員利用訂購區域集來聲明它感興趣接收的數據，通過對公布區域集和訂購區域集的匹配計算，RTI決定是否在發送者和接收者之間建立連接并傳送數據，而且公布區域和訂購區域都是動態變化的。因此，如何對公布區域集和訂購區域集進行有效的組織管理是提高DDM過濾效率的有效途徑[6]。

目前，比較常用的匹配算法有基于區域的完全匹配法。該算法采用區域直接匹配的方法，即每個公布區域必須和所有的訂購區域進行匹配，判斷區域是否相交。一旦公布區域或訂購區域改變，RTI將重新進行區域匹配。該算法優點是實現簡單，匹配精確，但是不適合大規模復雜系統中更新和訂購區域數量都很大的情況[7]。基于網格的DDM算法是將路徑空間均勻分隔成由格子組成的網格，每個格子的維數即路徑空間的維數。訂購與公布區域的匹配不是直接進行，而是通過每個成員將其公布和訂購區域映射到路徑空間的網格上，通過判斷公布與訂購區域是否覆蓋了同一個網格來確定哪些區域是重疊的。該算法過濾計算開銷低，但是會產生虛假連接以及冗余連接問題。而基于排序的匹配算法通過有序表的建立一次性將公布區域和訂購區域的重疊區域匹配完，匹配精度高。但缺點是一旦更新區域時，都需要重新建立有序表，匹配效率降低。

2 DDM數據過濾流程

DDM的過濾流程主要包括以下四個步驟：

區域聲明：在預先定義好的路徑空間中，數據公布者在其中創建區域，利用數據分發管理提供的服務，向聯邦聲明產生數據的區域；數據訂購者則創建區域，聲明它需要的數據所在區域。

區域匹配：RTI根據公布者和訂購者各自聲明的區域，按規則進行匹配。一個訂購區域和一個公布區域匹配成功，需要兩個區域在每一維上的范圍都有重疊時，整個區域才稱為重疊，區域才能匹配成功。

建立連接：區域匹配成功后，根據區域匹配結果，在發送方和接收方之間建立數據連接，分配組播地址。

數據發送：將公布平臺產生的信息通過網絡傳輸給合適的接收成員，同時盡可能使冗余信息減少。

數據分發的四個步驟中，區域匹配算法直接影響著數據分發管理的過濾效率。而DDM過濾機制所要解決的問題就是如何對動態變化的公布區域和訂購區域進行匹配計算，找出相重疊區域，以及如何高效地將重疊區域的數據分發到訂購方。

3 基于區間樹的DDM匹配算法

3.1 區間樹的結構

區間樹是一種擴展紅黑樹，紅黑樹是一種二叉查找樹，但在每個結點上增加一個存儲位表示結點的顏色可以是RED或BLACK。樹中每個結點包含五個域：color，key，left，right，p。color為紅黑狀態，key為結點的關鍵字，left，right，p則分別指向結點的左兒子，右兒子及父結點。如果某結點沒有一個子結點或父結點，則該結點相應的指針（p）域包含值為NULL，視為外結點，而把帶關鍵字的結點視為樹的內結點。

紅黑樹具有如下性質：

（1）每個結點或是紅的，或是黑的。

（2）根結點是黑的。

（3）每個葉結點（NULL）是黑的。

（4）如果一個結點是紅的，則它的兩個兒子都是黑的。

（5）對每個結點，從該結點到其子孫結點的所有路徑上包含相同數目的黑結點。

區間樹定義：設 Σ為n個半開區間的集合，并設這n個區間的邊界值取自集合U={x1＜x2＜…＜xv}，即 Σ={[li，ri)，其中 li，ri∈U，li＜ri，1≤i≤n}。關鍵字為區間的低端點 li。基于U對Σ構造的區間樹是一棵平衡二叉樹T[8]，T中有V個葉結點以及一些雙向鏈表。每個葉結點代表來自U的一個元素。所有非葉結點u用一個分裂值max（u）進行標記，若某查詢到達該點，max（u）就作為一個判別值，以判斷查找應沿結點的哪個分支繼續。圖1說明了區間樹是如何表示一個區間集合的。

圖1 一棵區間樹

區間樹是一種完全動態的空間索引數據結構，插入、刪除和查詢可同時進行，并且不需要周期性的索引重組。區間樹支持由區間構成的動態集合的操作，它能保證在最壞的情況下，時間為O(lgn)。

3.2 區間樹的DDM區域匹配算法實現

DDM匹配算法的核心問題是判斷公布域和訂購域是否重疊，其實質是矩形的相交問題。區間樹是一種基于多維的空間索引技術，最早是為了提高空間數據庫的查詢效率。多維空間結構的匹配（相交）查詢是其基本服務之一，這就為DDM匹配算法的實現提供了理論基礎。

3.2.1 ITBM算法原理

算法的基本思想是：在定義好的路徑空間上，經過映射，建立多維坐標系統，將公布區域集合與訂購區域集合的相同維的坐標值，按照從小到大的順序排列，區域的低邊界與高邊界構成一個區間，在同維坐標系統中，形成區間集。從此區間集中選擇公布區域區間構建公布區間樹，在區間樹上進行搜索匹配，找出公布區域和訂購區域重疊的區間結點。若存在公布與訂購區域在所有公共維上都發生重疊，則此公布區域與訂購區域有相交部分，匹配成功，否則公布區域與訂購區域沒有相交部分，匹配失敗。以圖2舉例說明。

圖2 二維坐標系統中區域分布示意圖

如圖2，在二維坐標系統的路徑空間中，公布區域為分別P1，P2，訂購區域分別為S1，S2。在X維上，公布區域范圍分別為 P1（5，12），P2（16，28），訂購區域的范圍分別為S1（14，21），S2（26，34）；在Y維上，公布區域的范圍分別為P1（10，22），P2（14，20），訂購區域的范圍分別為S1（6，16），S2（4，12）。首先將區域范圍映射到區間集上。圖3為X維上范圍映射的區間集。根據公布區域的區間集構建公布區域的區間樹。

圖3 公布區域與訂購區域的區間集

3.2.2 區間樹的操作

ITBM算法要完成路徑空間的映射，區間樹的建立、更新及搜索。初始時，建立一棵空區間樹，然后將公布區域或訂購區域的區間集逐一地加入到此區間樹中，仿真運行過程中，動態地對區間樹進行維護，刪除無效的區域，插入更新的區域，并在區間樹中搜索出相匹配的公布區域和訂購區域。

在對區間樹進行操作時，樹的結構會發生變化，為了保持區間樹的紅黑性質，就要改變樹中的某些結點的顏色以及指針結構。

區間樹的區域匹配算法操作主要有以下幾種：

（1）區間樹的旋轉（RotateValtree（））

樹中的指針結構的修改是通過旋轉來完成的，這是一種能保持二叉查找樹性質的查找樹局部操作。圖4給出了兩種旋轉：左旋和右旋。

圖4 區間樹的旋轉操作

如圖4所示，左旋操作 LEFT-ROTATE（T，x）通過改變常數個指針來將左邊兩個結點的結構轉變成右邊的結構。右邊的結構可以使用相反的操作右旋RIGHT-ROTATE（T，y）來轉變左邊的結構。字母α，β以及γ代表任意的子樹。旋轉操作保留二叉查找樹的屬性；α的關鍵字在key[x]之前，key[x]又在β的關鍵字之前，β的關鍵字在key[y]之前，key[y]在γ的關鍵字之前。左旋和右旋都是在O（1）時間內執行。在旋轉時只有指針被改變，而結點中的所有其他域都保持不變。

（2）區間樹的插入（InsertValtree（））

在區域的動態匹配過程中，區域可能會隨時間而變化，此時，其所映射的區間也同時發生了變化，要將新的區間結點加入到區間樹中，任何一個即將插入到已有區間樹的新結點的初始顏色都應為紅色。因為插入黑點會增加某條路徑上黑結點的數目，從而導致整棵樹黑高度的不平衡。但如果新結點父結點為紅色時，將會違反紅黑樹性質：一條路徑上不能出現相鄰的兩個紅色結點。這時就需要根據以下幾種情況，通過一系列旋轉操作來使紅黑樹保持平衡。插入操作分為以下幾種情況：

情況1：新結點位于樹的根上，沒有父結點。

情況2：新結點的父結點是黑色。

情況3：新結點的父結點及其叔叔結點都為紅色。

情況4：父結點是紅色，叔叔結點是黑色或葉結點。

情況5：父結點是紅色，而叔父結點是黑色或者是葉結點。

含n個結點的區間樹的高度為O(lgn)，因而區間樹的插入要花O(lgn)時間。

（3）區間樹的刪除（DeleteValtree（））

DDM仿真系統中的公布區域和訂購區域是不斷變化的，所以需要刪除區間樹原有的無效區域，動態地對區間樹進行維護。刪除操作中真正被刪除的必定是只有一個紅色孩子或沒有孩子的結點。如果真正的刪除點是一個紅色結點，則它必定是一個葉子結點。和區間樹的插入操作一樣，對區間樹中的一個結點的刪除要花O(lgn)時間。

（4）區間樹的匹配搜索（SearchValtree（））

動態區間樹的匹配搜索是在區間樹中搜索出公布區域與訂購區域中相重疊的區域。匹配搜索的步驟為從根結點開始，逐步下降。將搜索區間的低端點與區間樹中的結點的關鍵字比較，如果小于結點關鍵字，則需搜索左孩子結點與右孩子結點，如果大于結點關鍵字，則只搜索右孩子結點即可。當找到一個重疊區域后，將其存儲，并沿著此結點繼續搜索至葉子結點，最后查找出相匹配的所有公布區域。因為基本循環的每次迭代要花O(1)時間，又含n個結點的紅黑樹的高度為O(lgn)，所以區間樹的搜索過程的時間為O(lgn)。搜索算法從根結點向下搜索公布區域的區間樹，根據匹配的結果，結點下的子樹可能需要被搜索，在任意結點上，如果不重疊，則搜索總是沿著一個安全的方向前進的：如果樹中確有重疊的區間，則該區間必定會被找到。因此，通過對區間樹的動態維護，算法總體的搜索速度與性能都是良好的。

4 仿真實驗及結果分析

4.1 仿真實驗

影響DDM匹配算法效率的主要因素有限域的總數、區域的平均限域數和區域重疊率[9]。區域的數目又決定了限域的總數，因此，區域的數目在仿真效率中起著重要的作用。而重疊率與限域的數量以及限域的平均尺度有關，重疊率的大小直接決定著與給定矩形相交的矩形數量的多少。

在匹配算法中，限域總數與重疊率變化的情況下，基于區域的完全匹配法沒有一種有效的方式對聯邦中的公布區域和訂購區域進行組織管理。雖然排序法和網格法具有良好的總體性能，特別是當重疊率提高的情況下，排序法的效率下降得比較平緩。但是網格法中對于網格的劃分卻是項非常困難的工作，特別是當矩形在空間中分布不均的情況下，如果根據網格分配組播組，將導致網絡流量傳輸得嚴重不穩定。排序法雖然在各種情況下性能最為穩定，但它的動態維護代價較高，僅適用于靜態DDM。而區間樹法正好克服了上述幾種方法的缺陷，可以保證目標數據對象在樹結點中的均衡分配，同時具有較高的動態維護性能。

在仿真實驗中，通過區域數目和重疊率的變化考察了ITBM算法的插入、匹配、動態維護等性能。圖5為區間樹構造時間隨重疊率的變化趨勢圖。圖6為平均搜索時間隨重疊率的變化趨勢圖。

圖5 構造時間隨重疊率的變化趨勢

圖6 平均搜索時間隨重疊率的變化趨勢

仿真實驗在Windows XP平臺上進行，CPU 2.5 GHz，內存為1 GB。在1 024×1 024的二維路徑空間中，隨機生成500，1 000，2 500，5 000，10 000個矩形區域，根據映射區間構建動態的區間樹。由于排序算法穩定，所以，選定了排序匹配算法與ITBM算法分別從構造時間和搜索匹配速度進行了比較。排序法的具體步驟參見文獻[10]。

圖7為基于排序的區域匹配算法與ITBM算法的構造時間的比較。圖8為兩者的平均搜索時間的比較。

圖7 排序法和區間樹法構造時間的比較

圖8 排序法和區間樹法平均搜索時間的比較

4.2 實驗結果分析

決定匹配算法效率的關鍵因素中的重疊率，其直接決定因素是矩形的邊長和公布域矩形的數量。如圖5和圖6所示。圖中矩形邊長在一定范圍內隨機產生，如圖中的橫坐標“1～10”是指矩形邊長在坐標空間邊長中的比例在1%～10%之間。平均搜索時間為隨機生成的1 000個訂購矩形的平均搜索時間值。由圖5可知，給定公布域，ITBM的構造時間受矩形邊長的影響不大；由圖6可知，平均搜索時間隨邊長的增加而增大，但是矩形邊長為40%～50%的20 000個公布矩形構成的區間樹的平均搜索時間不到3 ms，可見ITBM算法在重疊率和公布矩形數量很大的情況下同樣具有較好的匹配效率。

公布域的修改是由區間樹的插入和刪除操作共同完成的。插入操作的性能可由圖5中區間樹的構造時間考察。同時，對矩形的刪除性能也做了相關實驗，雖然刪除矩形的平均時間波動較大，但是平均刪除時間不超過3 ms，因此，可以滿足實際仿真應用中的需求。

從圖7中可以看出，排序法的構造時間隨著區域數量的增加而上升，且上升趨勢明顯高于ITBM算法的構造時間。排序法雖然在各種情況下性能最為穩定，但其動態維護代價較高，每次區域更新都需要重新建立有序表，且構建的代價又是巨大的，而ITBM算法只需動態地插入或刪除更新區域的結點即可。在圖8中，排序法的匹配搜索時間隨著區域數量的增加逐漸上升，而ITBM算法的搜索匹配在區域數量達5 000之后開始趨于平穩，因此ITBM相對于排序法來說，在構建及動態維護上，都要優于排序法，且更適合大規模的仿真演練。

5 小結

影響DDM效率的關鍵問題是匹配算法的實現。本文提出了一種動態的基于區間樹的DDM區域匹配算法，研究了算法的基本原理和實現方法，通過區間樹的建立及更新實現對區域的動態組織管理，并通過實驗驗證了其優于傳統區域匹配算法排序法的性能。結果表明ITBM算法是一種高效的動態匹配算法。以此為基礎，會進一步研究分布式環境下的ITBM算法的實現和優化策略。

[1]張貴生，張霞，李德玉.基于權重函數的混合DDM算法[J].計算機工程與設計，2008，29（4）：797-799.

[2]Boukerche A，Dzermajko C.Scalability and performance evaluation of an aggregation/disaggregation scheme for data distribution managementin large-scale distributed interactive systems[C]//Proceeding of the 37th Annual Simulation Symposium.Washington，DC，USA：IEEE Computer Society，2004：238-244.

[3]周彥，戴劍偉，蔣曉原.HIA仿真程序設計[M].北京：電子工業出版社，2002.

[4]Petty M D，Paterson D J.Data distribution management issues for HLA implementations[C]//Proceedings of the Spring 2000 Simulation Interoperability Workshop.Orlando FL：SISO，2000.

[5]Lu Tainchi，Lee Chungnan，Hsia Wenyang，et al.Supporting large-scale distributed simulation using HLA[J].ACM Transactions on Modeling and Computer Simulation，2000，10（3）：268-294.

[6]王磊，張慧慧，李開生，等.基于動態R_樹結構的DDM區域匹配算法[J].計算機工程，2008，34（3）.

[7]張霞，黃莎白.高層體系結構中DDM實現方法的研究[J].系統仿真學報，2003，15（5）：670-673.

[8]Manolopoalos Y，Theodoridis Y，Tsotras V J.Advanced database indexing[M].Boston：Kluwer Academic Publishers，1999：61-81.

[9]Petty M D，Mukherjee A.Experimental comparison of d-rectangle intersection algorithms applied to HLA data distribution[C]// Proceedings of the 1997 Distributed Simulation Symposium，Orlando FL，1997：13-26.

[10]Yu Jun，Raczy C，Tan G.Evaluation of sort-based matching algorithm for the DDM[C]//The 16th Workshop on Parallel and Distributed Simulation，Washington，USA，2002.

區間樹在DDM區域匹配中的應用

尚福華，張海波，解紅濤

SHANG Fuhua,ZHANG Haibo,XIE Hongtao

School of Computer and Information Technology,Northeast Petroleum University,Daqing,Heilongjiang 163318,China

Data Distributed Management（DDM）is the effective method to reduce network redundant data,region matching algorithm is the key of data distributed management.The current variety of matching algorithms such as direct matching method,the grid method,sorting method are insufficient ideal because of the poor filtration or long time-consuming.Through the fully research of data filtering mechanism,the region matching algorithm based on interval-tree—ITBM is proposed,which is mapped range to an interval,uses the interval trees to store the area range,through the direct operation of interval-tree to complete matching work.The results show that ITBM can greatly reduce the time of matching calculations,effectively save the cost of matching process of dynamic DDM.

data distributed management;region matching;interval-tree

數據分發管理（DDM）是降低網絡冗余數據的有效手段，區域匹配算法又是數據分發管理實現的關鍵。當前的多種匹配算法如直接匹配法、網格法、排序法等效率都不夠理想，或者過濾效果不佳，或者耗時較長。通過對數據過濾機制的深入研究，提出了基于區間樹的區域匹配算法——ITBM算法，該算法將范圍的上下界映射到一個區間內，使用區間樹來存儲區域范圍，通過對區間樹的直接操作來完成匹配工作。結果表明，ITBM算法大大減少了匹配計算的時間，有效地減少了動態DDM的維護開銷。

數據分發管理；區域匹配；區間樹

A

TP391.9

10.3778/j.issn.1002-8331.1110-0299

SHANG Fuhua,ZHANG Haibo,XIE Hongtao.Application of interval-tree in region matching for DDM.Computer Engineering and Applications,2013,49（11）：110-113.

國家自然科學基金（No.61170132）。

尚福華（1962—），男，教授，研究方向為人工智能、機器學習、數據挖掘、虛擬現實、圖像處理等。

2011-10-17

2012-01-16

1002-8331（2013）11-0110-04

CNKI出版日期：2012-03-08 http://www.cnki.net/kcms/detail/11.2127.TP.20120308.1521.047.html