區(qū)間樹在DDM區(qū)域匹配中的應(yīng)用

東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，黑龍江 大慶 163318

東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，黑龍江 大慶 163318

1 引言

現(xiàn)代仿真應(yīng)用已經(jīng)從集中式仿真發(fā)展到了分布式交互仿真，分布式仿真技術(shù)作為一種重要的研究手段正廣泛地應(yīng)用于軍事以及國(guó)民經(jīng)濟(jì)的各個(gè)領(lǐng)域[1]，為了實(shí)現(xiàn)仿真應(yīng)用的互操作性和資源的可重用性，美國(guó)防部提出了高層體系結(jié)構(gòu)（HLA）仿真框架[2]，HLA體系結(jié)構(gòu)主要由3部分組成：HLA規(guī)則、HLA接口規(guī)范、HLA對(duì)象模型模板[3]。接口規(guī)范說(shuō)明是對(duì)HLA的運(yùn)行時(shí)間支撐系統(tǒng)RTI（Runtime Infrastructure）的接口規(guī)范的描述。RTI提供了一個(gè)通用的、相對(duì)獨(dú)立的支撐服務(wù)程序，將仿真應(yīng)用與底層的支撐環(huán)境分開，從而使各部分可以相對(duì)獨(dú)立地進(jìn)行開發(fā)。

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

目前，比較常用的匹配算法有基于區(qū)域的完全匹配法。該算法采用區(qū)域直接匹配的方法，即每個(gè)公布區(qū)域必須和所有的訂購(gòu)區(qū)域進(jìn)行匹配，判斷區(qū)域是否相交。一旦公布區(qū)域或訂購(gòu)區(qū)域改變，RTI將重新進(jìn)行區(qū)域匹配。該算法優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，匹配精確，但是不適合大規(guī)模復(fù)雜系統(tǒng)中更新和訂購(gòu)區(qū)域數(shù)量都很大的情況[7]?；诰W(wǎng)格的DDM算法是將路徑空間均勻分隔成由格子組成的網(wǎng)格，每個(gè)格子的維數(shù)即路徑空間的維數(shù)。訂購(gòu)與公布區(qū)域的匹配不是直接進(jìn)行，而是通過(guò)每個(gè)成員將其公布和訂購(gòu)區(qū)域映射到路徑空間的網(wǎng)格上，通過(guò)判斷公布與訂購(gòu)區(qū)域是否覆蓋了同一個(gè)網(wǎng)格來(lái)確定哪些區(qū)域是重疊的。該算法過(guò)濾計(jì)算開銷低，但是會(huì)產(chǎn)生虛假連接以及冗余連接問題。而基于排序的匹配算法通過(guò)有序表的建立一次性將公布區(qū)域和訂購(gòu)區(qū)域的重疊區(qū)域匹配完，匹配精度高。但缺點(diǎn)是一旦更新區(qū)域時(shí)，都需要重新建立有序表，匹配效率降低。

2 DDM數(shù)據(jù)過(guò)濾流程

DDM的過(guò)濾流程主要包括以下四個(gè)步驟：

區(qū)域聲明：在預(yù)先定義好的路徑空間中，數(shù)據(jù)公布者在其中創(chuàng)建區(qū)域，利用數(shù)據(jù)分發(fā)管理提供的服務(wù)，向聯(lián)邦聲明產(chǎn)生數(shù)據(jù)的區(qū)域；數(shù)據(jù)訂購(gòu)者則創(chuàng)建區(qū)域，聲明它需要的數(shù)據(jù)所在區(qū)域。

區(qū)域匹配：RTI根據(jù)公布者和訂購(gòu)者各自聲明的區(qū)域，按規(guī)則進(jìn)行匹配。一個(gè)訂購(gòu)區(qū)域和一個(gè)公布區(qū)域匹配成功，需要兩個(gè)區(qū)域在每一維上的范圍都有重疊時(shí)，整個(gè)區(qū)域才稱為重疊，區(qū)域才能匹配成功。

建立連接：區(qū)域匹配成功后，根據(jù)區(qū)域匹配結(jié)果，在發(fā)送方和接收方之間建立數(shù)據(jù)連接，分配組播地址。

數(shù)據(jù)發(fā)送：將公布平臺(tái)產(chǎn)生的信息通過(guò)網(wǎng)絡(luò)傳輸給合適的接收成員，同時(shí)盡可能使冗余信息減少。

數(shù)據(jù)分發(fā)的四個(gè)步驟中，區(qū)域匹配算法直接影響著數(shù)據(jù)分發(fā)管理的過(guò)濾效率。而DDM過(guò)濾機(jī)制所要解決的問題就是如何對(duì)動(dòng)態(tài)變化的公布區(qū)域和訂購(gòu)區(qū)域進(jìn)行匹配計(jì)算，找出相重疊區(qū)域，以及如何高效地將重疊區(qū)域的數(shù)據(jù)分發(fā)到訂購(gòu)方。

3 基于區(qū)間樹的DDM匹配算法

3.1 區(qū)間樹的結(jié)構(gòu)

區(qū)間樹是一種擴(kuò)展紅黑樹，紅黑樹是一種二叉查找樹，但在每個(gè)結(jié)點(diǎn)上增加一個(gè)存儲(chǔ)位表示結(jié)點(diǎn)的顏色可以是RED或BLACK。樹中每個(gè)結(jié)點(diǎn)包含五個(gè)域：color，key，left，right，p。color為紅黑狀態(tài)，key為結(jié)點(diǎn)的關(guān)鍵字，left，right，p則分別指向結(jié)點(diǎn)的左兒子，右兒子及父結(jié)點(diǎn)。如果某結(jié)點(diǎn)沒有一個(gè)子結(jié)點(diǎn)或父結(jié)點(diǎn)，則該結(jié)點(diǎn)相應(yīng)的指針（p）域包含值為NULL，視為外結(jié)點(diǎn)，而把帶關(guān)鍵字的結(jié)點(diǎn)視為樹的內(nèi)結(jié)點(diǎn)。

紅黑樹具有如下性質(zhì)：

（1）每個(gè)結(jié)點(diǎn)或是紅的，或是黑的。

（2）根結(jié)點(diǎn)是黑的。

（3）每個(gè)葉結(jié)點(diǎn)（NULL）是黑的。

（4）如果一個(gè)結(jié)點(diǎn)是紅的，則它的兩個(gè)兒子都是黑的。

（5）對(duì)每個(gè)結(jié)點(diǎn)，從該結(jié)點(diǎn)到其子孫結(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑結(jié)點(diǎn)。

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

圖1 一棵區(qū)間樹

區(qū)間樹是一種完全動(dòng)態(tài)的空間索引數(shù)據(jù)結(jié)構(gòu)，插入、刪除和查詢可同時(shí)進(jìn)行，并且不需要周期性的索引重組。區(qū)間樹支持由區(qū)間構(gòu)成的動(dòng)態(tài)集合的操作，它能保證在最壞的情況下，時(shí)間為O(lgn)。

3.2 區(qū)間樹的DDM區(qū)域匹配算法實(shí)現(xiàn)

DDM匹配算法的核心問題是判斷公布域和訂購(gòu)域是否重疊，其實(shí)質(zhì)是矩形的相交問題。區(qū)間樹是一種基于多維的空間索引技術(shù)，最早是為了提高空間數(shù)據(jù)庫(kù)的查詢效率。多維空間結(jié)構(gòu)的匹配（相交）查詢是其基本服務(wù)之一，這就為DDM匹配算法的實(shí)現(xiàn)提供了理論基礎(chǔ)。

3.2.1 ITBM算法原理

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

圖2 二維坐標(biāo)系統(tǒng)中區(qū)域分布示意圖

如圖2，在二維坐標(biāo)系統(tǒng)的路徑空間中，公布區(qū)域?yàn)榉謩eP1，P2，訂購(gòu)區(qū)域分別為S1，S2。在X維上，公布區(qū)域范圍分別為 P1（5，12），P2（16，28），訂購(gòu)區(qū)域的范圍分別為S1（14，21），S2（26，34）；在Y維上，公布區(qū)域的范圍分別為P1（10，22），P2（14，20），訂購(gòu)區(qū)域的范圍分別為S1（6，16），S2（4，12）。首先將區(qū)域范圍映射到區(qū)間集上。圖3為X維上范圍映射的區(qū)間集。根據(jù)公布區(qū)域的區(qū)間集構(gòu)建公布區(qū)域的區(qū)間樹。

圖3 公布區(qū)域與訂購(gòu)區(qū)域的區(qū)間集

3.2.2 區(qū)間樹的操作

ITBM算法要完成路徑空間的映射，區(qū)間樹的建立、更新及搜索。初始時(shí)，建立一棵空區(qū)間樹，然后將公布區(qū)域或訂購(gòu)區(qū)域的區(qū)間集逐一地加入到此區(qū)間樹中，仿真運(yùn)行過(guò)程中，動(dòng)態(tài)地對(duì)區(qū)間樹進(jìn)行維護(hù)，刪除無(wú)效的區(qū)域，插入更新的區(qū)域，并在區(qū)間樹中搜索出相匹配的公布區(qū)域和訂購(gòu)區(qū)域。

在對(duì)區(qū)間樹進(jìn)行操作時(shí)，樹的結(jié)構(gòu)會(huì)發(fā)生變化，為了保持區(qū)間樹的紅黑性質(zhì)，就要改變樹中的某些結(jié)點(diǎn)的顏色以及指針結(jié)構(gòu)。

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

（1）區(qū)間樹的旋轉(zhuǎn)（RotateValtree（））

樹中的指針結(jié)構(gòu)的修改是通過(guò)旋轉(zhuǎn)來(lái)完成的，這是一種能保持二叉查找樹性質(zhì)的查找樹局部操作。圖4給出了兩種旋轉(zhuǎn)：左旋和右旋。

圖4 區(qū)間樹的旋轉(zhuǎn)操作

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

（2）區(qū)間樹的插入（InsertValtree（））

在區(qū)域的動(dòng)態(tài)匹配過(guò)程中，區(qū)域可能會(huì)隨時(shí)間而變化，此時(shí)，其所映射的區(qū)間也同時(shí)發(fā)生了變化，要將新的區(qū)間結(jié)點(diǎn)加入到區(qū)間樹中，任何一個(gè)即將插入到已有區(qū)間樹的新結(jié)點(diǎn)的初始顏色都應(yīng)為紅色。因?yàn)椴迦牒邳c(diǎn)會(huì)增加某條路徑上黑結(jié)點(diǎn)的數(shù)目，從而導(dǎo)致整棵樹黑高度的不平衡。但如果新結(jié)點(diǎn)父結(jié)點(diǎn)為紅色時(shí)，將會(huì)違反紅黑樹性質(zhì)：一條路徑上不能出現(xiàn)相鄰的兩個(gè)紅色結(jié)點(diǎn)。這時(shí)就需要根據(jù)以下幾種情況，通過(guò)一系列旋轉(zhuǎn)操作來(lái)使紅黑樹保持平衡。插入操作分為以下幾種情況：

情況1：新結(jié)點(diǎn)位于樹的根上，沒有父結(jié)點(diǎn)。

情況2：新結(jié)點(diǎn)的父結(jié)點(diǎn)是黑色。

情況3：新結(jié)點(diǎn)的父結(jié)點(diǎn)及其叔叔結(jié)點(diǎn)都為紅色。

情況4：父結(jié)點(diǎn)是紅色，叔叔結(jié)點(diǎn)是黑色或葉結(jié)點(diǎn)。

情況5：父結(jié)點(diǎn)是紅色，而叔父結(jié)點(diǎn)是黑色或者是葉結(jié)點(diǎn)。

含n個(gè)結(jié)點(diǎn)的區(qū)間樹的高度為O(lgn)，因而區(qū)間樹的插入要花O(lgn)時(shí)間。

（3）區(qū)間樹的刪除（DeleteValtree（））

DDM仿真系統(tǒng)中的公布區(qū)域和訂購(gòu)區(qū)域是不斷變化的，所以需要?jiǎng)h除區(qū)間樹原有的無(wú)效區(qū)域，動(dòng)態(tài)地對(duì)區(qū)間樹進(jìn)行維護(hù)。刪除操作中真正被刪除的必定是只有一個(gè)紅色孩子或沒有孩子的結(jié)點(diǎn)。如果真正的刪除點(diǎn)是一個(gè)紅色結(jié)點(diǎn)，則它必定是一個(gè)葉子結(jié)點(diǎn)。和區(qū)間樹的插入操作一樣，對(duì)區(qū)間樹中的一個(gè)結(jié)點(diǎn)的刪除要花O(lgn)時(shí)間。

（4）區(qū)間樹的匹配搜索（SearchValtree（））

動(dòng)態(tài)區(qū)間樹的匹配搜索是在區(qū)間樹中搜索出公布區(qū)域與訂購(gòu)區(qū)域中相重疊的區(qū)域。匹配搜索的步驟為從根結(jié)點(diǎn)開始，逐步下降。將搜索區(qū)間的低端點(diǎn)與區(qū)間樹中的結(jié)點(diǎn)的關(guān)鍵字比較，如果小于結(jié)點(diǎn)關(guān)鍵字，則需搜索左孩子結(jié)點(diǎn)與右孩子結(jié)點(diǎn)，如果大于結(jié)點(diǎn)關(guān)鍵字，則只搜索右孩子結(jié)點(diǎn)即可。當(dāng)找到一個(gè)重疊區(qū)域后，將其存儲(chǔ)，并沿著此結(jié)點(diǎn)繼續(xù)搜索至葉子結(jié)點(diǎn)，最后查找出相匹配的所有公布區(qū)域。因?yàn)榛狙h(huán)的每次迭代要花O(1)時(shí)間，又含n個(gè)結(jié)點(diǎn)的紅黑樹的高度為O(lgn)，所以區(qū)間樹的搜索過(guò)程的時(shí)間為O(lgn)。搜索算法從根結(jié)點(diǎn)向下搜索公布區(qū)域的區(qū)間樹，根據(jù)匹配的結(jié)果，結(jié)點(diǎn)下的子樹可能需要被搜索，在任意結(jié)點(diǎn)上，如果不重疊，則搜索總是沿著一個(gè)安全的方向前進(jìn)的：如果樹中確有重疊的區(qū)間，則該區(qū)間必定會(huì)被找到。因此，通過(guò)對(duì)區(qū)間樹的動(dòng)態(tài)維護(hù)，算法總體的搜索速度與性能都是良好的。

4 仿真實(shí)驗(yàn)及結(jié)果分析

4.1 仿真實(shí)驗(yàn)

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

在匹配算法中，限域總數(shù)與重疊率變化的情況下，基于區(qū)域的完全匹配法沒有一種有效的方式對(duì)聯(lián)邦中的公布區(qū)域和訂購(gòu)區(qū)域進(jìn)行組織管理。雖然排序法和網(wǎng)格法具有良好的總體性能，特別是當(dāng)重疊率提高的情況下，排序法的效率下降得比較平緩。但是網(wǎng)格法中對(duì)于網(wǎng)格的劃分卻是項(xiàng)非常困難的工作，特別是當(dāng)矩形在空間中分布不均的情況下，如果根據(jù)網(wǎng)格分配組播組，將導(dǎo)致網(wǎng)絡(luò)流量傳輸?shù)脟?yán)重不穩(wěn)定。排序法雖然在各種情況下性能最為穩(wěn)定，但它的動(dòng)態(tài)維護(hù)代價(jià)較高，僅適用于靜態(tài)DDM。而區(qū)間樹法正好克服了上述幾種方法的缺陷，可以保證目標(biāo)數(shù)據(jù)對(duì)象在樹結(jié)點(diǎn)中的均衡分配，同時(shí)具有較高的動(dòng)態(tài)維護(hù)性能。

在仿真實(shí)驗(yàn)中，通過(guò)區(qū)域數(shù)目和重疊率的變化考察了ITBM算法的插入、匹配、動(dòng)態(tài)維護(hù)等性能。圖5為區(qū)間樹構(gòu)造時(shí)間隨重疊率的變化趨勢(shì)圖。圖6為平均搜索時(shí)間隨重疊率的變化趨勢(shì)圖。

圖5 構(gòu)造時(shí)間隨重疊率的變化趨勢(shì)

圖6 平均搜索時(shí)間隨重疊率的變化趨勢(shì)

仿真實(shí)驗(yàn)在Windows XP平臺(tái)上進(jìn)行，CPU 2.5 GHz，內(nèi)存為1 GB。在1 024×1 024的二維路徑空間中，隨機(jī)生成500，1 000，2 500，5 000，10 000個(gè)矩形區(qū)域，根據(jù)映射區(qū)間構(gòu)建動(dòng)態(tài)的區(qū)間樹。由于排序算法穩(wěn)定，所以，選定了排序匹配算法與ITBM算法分別從構(gòu)造時(shí)間和搜索匹配速度進(jìn)行了比較。排序法的具體步驟參見文獻(xiàn)[10]。

圖7為基于排序的區(qū)域匹配算法與ITBM算法的構(gòu)造時(shí)間的比較。圖8為兩者的平均搜索時(shí)間的比較。

圖7 排序法和區(qū)間樹法構(gòu)造時(shí)間的比較

圖8 排序法和區(qū)間樹法平均搜索時(shí)間的比較

4.2 實(shí)驗(yàn)結(jié)果分析

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

公布域的修改是由區(qū)間樹的插入和刪除操作共同完成的。插入操作的性能可由圖5中區(qū)間樹的構(gòu)造時(shí)間考察。同時(shí)，對(duì)矩形的刪除性能也做了相關(guān)實(shí)驗(yàn)，雖然刪除矩形的平均時(shí)間波動(dòng)較大，但是平均刪除時(shí)間不超過(guò)3 ms，因此，可以滿足實(shí)際仿真應(yīng)用中的需求。

從圖7中可以看出，排序法的構(gòu)造時(shí)間隨著區(qū)域數(shù)量的增加而上升，且上升趨勢(shì)明顯高于ITBM算法的構(gòu)造時(shí)間。排序法雖然在各種情況下性能最為穩(wěn)定，但其動(dòng)態(tài)維護(hù)代價(jià)較高，每次區(qū)域更新都需要重新建立有序表，且構(gòu)建的代價(jià)又是巨大的，而ITBM算法只需動(dòng)態(tài)地插入或刪除更新區(qū)域的結(jié)點(diǎn)即可。在圖8中，排序法的匹配搜索時(shí)間隨著區(qū)域數(shù)量的增加逐漸上升，而ITBM算法的搜索匹配在區(qū)域數(shù)量達(dá)5 000之后開始趨于平穩(wěn)，因此ITBM相對(duì)于排序法來(lái)說(shuō)，在構(gòu)建及動(dòng)態(tài)維護(hù)上，都要優(yōu)于排序法，且更適合大規(guī)模的仿真演練。

5 小結(jié)

影響DDM效率的關(guān)鍵問題是匹配算法的實(shí)現(xiàn)。本文提出了一種動(dòng)態(tài)的基于區(qū)間樹的DDM區(qū)域匹配算法，研究了算法的基本原理和實(shí)現(xiàn)方法，通過(guò)區(qū)間樹的建立及更新實(shí)現(xiàn)對(duì)區(qū)域的動(dòng)態(tài)組織管理，并通過(guò)實(shí)驗(yàn)驗(yàn)證了其優(yōu)于傳統(tǒng)區(qū)域匹配算法排序法的性能。結(jié)果表明ITBM算法是一種高效的動(dòng)態(tài)匹配算法。以此為基礎(chǔ)，會(huì)進(jìn)一步研究分布式環(huán)境下的ITBM算法的實(shí)現(xiàn)和優(yōu)化策略。

[1]張貴生，張霞，李德玉.基于權(quán)重函數(shù)的混合DDM算法[J].計(jì)算機(jī)工程與設(shè)計(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仿真程序設(shè)計(jì)[M].北京：電子工業(yè)出版社，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]王磊，張慧慧，李開生，等.基于動(dòng)態(tài)R_樹結(jié)構(gòu)的DDM區(qū)域匹配算法[J].計(jì)算機(jī)工程，2008，34（3）.

[7]張霞，黃莎白.高層體系結(jié)構(gòu)中DDM實(shí)現(xiàn)方法的研究[J].系統(tǒng)仿真學(xué)報(bào)，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.

區(qū)間樹在DDM區(qū)域匹配中的應(yīng)用

尚福華，張海波，解紅濤

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

數(shù)據(jù)分發(fā)管理（DDM）是降低網(wǎng)絡(luò)冗余數(shù)據(jù)的有效手段，區(qū)域匹配算法又是數(shù)據(jù)分發(fā)管理實(shí)現(xiàn)的關(guān)鍵。當(dāng)前的多種匹配算法如直接匹配法、網(wǎng)格法、排序法等效率都不夠理想，或者過(guò)濾效果不佳，或者耗時(shí)較長(zhǎng)。通過(guò)對(duì)數(shù)據(jù)過(guò)濾機(jī)制的深入研究，提出了基于區(qū)間樹的區(qū)域匹配算法——ITBM算法，該算法將范圍的上下界映射到一個(gè)區(qū)間內(nèi)，使用區(qū)間樹來(lái)存儲(chǔ)區(qū)域范圍，通過(guò)對(duì)區(qū)間樹的直接操作來(lái)完成匹配工作。結(jié)果表明，ITBM算法大大減少了匹配計(jì)算的時(shí)間，有效地減少了動(dòng)態(tài)DDM的維護(hù)開銷。

數(shù)據(jù)分發(fā)管理；區(qū)域匹配；區(qū)間樹

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.

國(guó)家自然科學(xué)基金（No.61170132）。

尚福華（1962—），男，教授，研究方向?yàn)槿斯ぶ悄?、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、虛擬現(xiàn)實(shí)、圖像處理等。

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