hla中數(shù)據(jù)分發(fā)管理的探究

1、hla中數(shù)據(jù)分發(fā)管理的探究hla中數(shù)據(jù)分發(fā)管理的探究摘要hla已成為了現(xiàn)代分布式仿真應用的通用技術框架的核心，而作 為其六大服務之一的數(shù)據(jù)分發(fā)管理則提供了有效的信息交互和傳送 機制以滿足系統(tǒng)可擴縮性的要求。文章介紹了 hla中數(shù)據(jù)分發(fā)管理 ddm的過濾原理；研究并分析了目前幾種實現(xiàn)ddm過濾機制的方法。 關鍵詞高層體系結構hla；數(shù)據(jù)分發(fā)管理ddm；數(shù)據(jù)過濾；適應性算 法引言現(xiàn)代仿真應用已經(jīng)從集中式仿真發(fā)展到分布式交互仿真，高層體系結 構hla (highlevelarchitecture)也已成為了其通用技術框架的核 心。而隨著分布交互仿真系統(tǒng)規(guī)模和復雜度的增加，數(shù)據(jù)分發(fā)管理 ddm (da

2、tadis tri blit ionmanagement)有效地減少了系統(tǒng)中的數(shù)據(jù)通信 量，節(jié)省了網(wǎng)絡帶寬和處理機資源，同時也提高了系統(tǒng)的可擴縮性。 文章介紹了目前常用的ddm匹配算法和一些啟發(fā)式規(guī)則；重點分析了 基于排序的ddm算法并用一些新的標準來衡量和比較它們，利用這些 標準有效地選取最適應的算法；最后總結了全文。1hla屮的ddm數(shù)據(jù)過濾原理hla是1995年美國國防部建模與仿真主計劃msld中開發(fā)建模和仿真 通用技術框架中的首要內(nèi)容，其主要目的是促進仿真應用的互操作性 和仿真資源的可重用性，并于2000年通過ieee標準。hla主要包括 規(guī)則定義(rules) 對象模型模板(obje

3、ctmodeltemplate),接口規(guī)范 說明(interfacespecification)三部分內(nèi)容1。數(shù)據(jù)分發(fā)管理ddm 是hla/rti最重要的功能之一，是根據(jù)仿真實體之間的數(shù)據(jù)供求關系 實現(xiàn)的基于組播通信的數(shù)據(jù)過濾技術，為系統(tǒng)的可擴縮性提供了可 能。實現(xiàn)ddm主要考慮的問題有：區(qū)域匹配問題，組播分配和組播實 現(xiàn)問題，區(qū)域動態(tài)變化問題和降低區(qū)域匹配的損耗問題等，hla引進 了路徑空間rs (routingspace)的概念1來描述這種限制條件。一個 路徑空間是一個多維的坐標系統(tǒng),是聯(lián)邦屮屬性值構成的數(shù)據(jù)空間。 rs包括以下幾個概念：維(dimension) 范圍(range) 限域(

4、extent) 區(qū)域(region)。其中區(qū)域是路徑空間的子集可分為兩種區(qū)域:更新區(qū) 域(updateregion)和訂購區(qū)域(subscriberegion)。區(qū)域是數(shù)據(jù)分發(fā) 管理的核心概念。2實現(xiàn)ddm的兒種方法2. 1基于區(qū)域的方法(region-based)在基于區(qū)域的數(shù)據(jù)分發(fā)管理中發(fā)布-訂購對是以-種隨機的順序建立 起來的，計算每對的交互情況直到非空交互被找到。這是一種最基本 的方法，優(yōu)點是應用直觀且匹配精確，缺點是其性能隨著非空交互出 現(xiàn)的幾率大小有著極其明顯的變化。當所有的更新區(qū)域與所有的訂購 區(qū)域都有交互時，此方法是最有效的。但當根本沒有交互時則其復雜 度將變?yōu)槠椒郊墶Ｋ惴旧?/p>

5、存在著實現(xiàn)上的可擴展(scalability)問 題，即當系統(tǒng)中仿真對象類數(shù)為n時，ddm中的更新區(qū)域和訂購區(qū)域 的匹配比較次數(shù)將與n平方成正比，即匹配次數(shù)的增長規(guī)模為0(n2)。 該方法不適合大規(guī)模復雜系統(tǒng)中更新區(qū)域和訂購區(qū)域數(shù)量都很大的 情況。2. 2表格劃分法(grid-based)基于網(wǎng)格的方法提供了一種相對簡單的區(qū)域匹配和確定網(wǎng)絡連接的 方法。路徑空間都被分隔成網(wǎng)格，每個格了的維數(shù)等于路徑空間的維 數(shù)。訂購區(qū)域與更新區(qū)域的比較不是直接進行，而是通過每個成員將 其更新和訂購區(qū)域映射到路徑空間的網(wǎng)格上，通過判斷區(qū)域是否覆蓋 了同一個網(wǎng)格來確定哪些訂購區(qū)域和更新區(qū)域是相重疊的。對于重疊 計

6、算過程中產(chǎn)生冗余和虛假連接可以通過優(yōu)化網(wǎng)格的尺寸g來獲得 更好的效果4。2. 3基于排序的算法(sort-based)在基于排序的方法中首先把區(qū)域投影到每個坐標軸上并單獨計算重 疊情況，若在所有的坐標方向上均有重疊則此發(fā)布-訂購對重疊。算 法將應用兩個集合來存儲信息：前訂購域集合subscript ionsetbef ore用來存儲位于當前所處理的發(fā)布域坐標位置 z前的定購域信息；后訂購域集合subscriptionsetafter則用來存 儲位于當前所處理的發(fā)布域坐標位置z后的定購域信息。首先，把每 個域的上界和下界在每個坐標方向上排序。當掃描排序的列表時，就 可能得到當前點的前定購域集合和

7、后訂購域集合。因此，就能確切了 解，對于每個更新區(qū)域是哪些訂購區(qū)域在給定的坐標上與之匹配。 初始條件下，由于還沒有任何掃描動作，假定所有的定購域信息均被 存儲與 subscriptionafter 集合中，所以 subscriptionbefore 集合 為空集而subscriptionafter集合為全集。當處理到某一定購域的下 界點時，說明其坐標位置肯定不能位于下一發(fā)布域之后，因此將之從 subscriptionsetafter集合屮取出,當處理到某一定購域的上界點 吋，說明其坐標位置肯定位于下一發(fā)布域之前，因此將之插入倒 subscriptionsetbefore集合中。當處理到某個發(fā)布

8、域的端點時，與 此發(fā)布域的不重疊信息存儲于subscriptionsetafter集合或 subscriptionsetbefore 集合中。例如圖3所示，一系列點表示了在區(qū)域在x軸上投影后的邊界情況。 算法從左到右掃描列表并執(zhí)行下列操作：對于每個在路徑空間中的限域ri作如下操作： 把ri的下界點插入到列表l把ri的上界點插入到列表l列表l進行排序定購域前集 subscriptionsetbefore=把所有的定購域均插入定購域后集subscriptionsetafter對于列表l中的所有點pi作下列循環(huán)ri二點pi所屬域的標識if（ri是訂購域） if（pi點是ri的下界點）從 subscr

9、iptionsetafter 中移去 ri else把 ri 插入到 subscriptionsetbefore 中 else（ri是更新域） if（pi點是ri的下界點）則subscriptionsetbefore中的所有域均不與ri交互 else則subscriptionsetafter中的所有域均不與ri交互可以對基于排序的算法進行一些有效的改進，例如可以用二進制向量 來代替當前定購域集合，這樣可以極大的降低每個更新域的匹配操作 復雜度3。此算法的一個顯著特性是其性能沒有隨著重疊率及限域 數(shù)目的變化而顯著變化。而且，在重疊率不是特別低、區(qū)域內(nèi)所含限 域數(shù)目不是特別多吋其性能較其他算法而言

10、是最優(yōu)的3。重疊率很 低時，網(wǎng)格劃分法要優(yōu)于排序的算法；而當重疊率很高且區(qū)域內(nèi)含有 的限域數(shù)目很大時，基于區(qū)域的算法的性能就會優(yōu)于排序算法2。24其它的啟發(fā)式規(guī)則邊界區(qū)域（boundingboxes）:此方法是計算每個域的邊界區(qū)域是否有 重疊，如果交互為空則無須再計算邊界框內(nèi)的域的重疊，反之，再在 邊界框區(qū)域內(nèi)重新計算域間的重疊情況。暫時連續(xù)性 （temporalcoherence）:這一規(guī)則充分利用了在許多仿真中事物是逐 漸變化的規(guī)則，即在仿真中兩個相鄰吋間狀態(tài)下很多區(qū)域并不會有明 顯的移動2。從而進一步減少區(qū)域匹配的次數(shù)。3 適應性算法（adapt iveapproach）3. 1問題的特

11、性ddm屮最顯著的屬性是域的數(shù)量情況。但z前所分析的各種算法和一 些啟發(fā)式規(guī)則的效率隨著區(qū)域在路徑空間中的不同的分布有較大的 變化，所以必須在給定的路徑空間中更準確地定義域的分布情況。有 兩個首要的因素需要考慮，首先是重疊率（overlappingrate）：描述 了域間重疊的可能性，是一個影響ddm算法效率的重要因素，定義為:其次是每個區(qū)域內(nèi)的限域的數(shù)目，因為ddm關心的是區(qū)域間的重疊而 不是限域間的重疊情況。在實際情況下當面對大量的限域時，在整個 空間中使用平均的重疊率是不現(xiàn)實的，很有可能在同一路徑空間中存 在重疊率高的區(qū)域，中等的區(qū)域以及重疊率很低的區(qū)域，且這些特性 都是動態(tài)變化的值，d

12、dm具體算法的選取需要計算和跟蹤這些重要的 屬性。有兩種方法可供選取：第一，首先把路徑空間做初步的劃分， 當然為了達到某一局部重疊率的要求可以嵌套劃分一直達到某一規(guī) 定重疊率值或劃分的網(wǎng)格數(shù)達到某要求為止。笫二，用排序的方法。 檢測排序后的列表時就可以直接得到每個初始劃分部分在此坐標方 向上的局部重疊率情況，在每維上做同樣的檢測則可得到空間中的域 是較平均分布的還是有聚集和稀疏的不均勻分布。3. 2算法的選取重疊率的取值范圍較大并且算法的選擇不需要精確的重疊率值（重疊 率接近某一閾值吋，選取不同的算法對ddm性能無明顯影響），因此 在大多數(shù)情況下對其作粗略估計即可。在不知道待解問題的具體特性

13、時，一般選取基于排序的ddm算法2,通常情況下此算法效率較高 并且除匹配操作以外對問題分析和預操作的復雜度（0（）較低3。 除此之外，一些啟發(fā)式規(guī)則也可應用到系統(tǒng)中來，但需要一種機制來 針對路徑空間中的不同區(qū)域優(yōu)選具體的算法。細劃分的基于網(wǎng)格的算 法適用于限域重疊率較低（重疊率為0. 01或者更低）的情況2?；?于區(qū)域的算法則適用于重疊率較高的情況。其他情況通常選取基于排 序的ddm算法。但是當限域在路徑空間中移動時，問題的屬性會發(fā)生 變化，可以在平均重疊率超過某一閾值時重新計算劃分并在局部范圍 內(nèi)重新選區(qū)ddm算法。另外，對于路徑空間內(nèi)區(qū)域重疊率不是均勻分 布的情況可以通過多種ddm算法的綜

14、合使用從一定程度上得以解決。 如：先對路徑空間作一簡單的劃分，再針對每個網(wǎng)格內(nèi)的具體情況選 取適當?shù)膁dm算法，則可以達到更好的數(shù)據(jù)過濾的效果。4結論高層體系結構hla中的ddm適應大規(guī)模復雜仿真系統(tǒng)的要求實現(xiàn)了進 一步的數(shù)據(jù)過濾，滿足了系統(tǒng)可擴縮性的要求。本文探討了目前兒種 流行的ddm數(shù)據(jù)過濾機制并用一些新的標準(如overlaprate等)對 其進行了比較，分析了如何利用這些標準動態(tài)地選出ddm適應性算 法，對于ddm最優(yōu)算法的研究具有一定的積極意義。參考文獻1dms0. highlevelarchitecturelnterfacespecificationver3,2e b/ol ht

15、tp:/www. dmso. mil/2jraczyc. , yuj. , tang. , tays. c., andayanir. adaptivedatadistrib utionmanagementforhlarti. inproceedingsof2002ein、opeansimulat ioninteroperabi1ityworkshop(london, uk). june20023 comeraczy, garys il tan, junyu. asort-basedddmmatchingalgori thmforhla. acmtrans. model. comput. simul. 15(1) :14-38(2005)4 azzedineboukerche, kaiyuanlu:optimizeddynamicgrid-baseddd mprotocolforlarge-scaledistributedsimulationsystems ipdps20 055 pettym. d. andk. l. morse thecomputationalcomplexityofthellig hlevelarchitecturedatadistributionmanagementmatchingandconn ectingprocesses, simulationmo