改進(jìn)的基于排序的DDM算法

張霞,延耀威

(山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院,山西 太原 030006)

0 引言

HLA是用來(lái)構(gòu)建大型復(fù)雜仿真系統(tǒng)的新型的分布式仿真技術(shù),該技術(shù)通過(guò)仿真運(yùn)行平臺(tái)將多個(gè)分布在不同地理位置的聯(lián)邦成員關(guān)聯(lián)起構(gòu)成復(fù)雜的仿真系統(tǒng)支持聯(lián)邦成員之間的交互,可以實(shí)現(xiàn)仿真成員的即插即用,滿足分布式仿真系統(tǒng)要求的可擴(kuò)縮性和可重用性[1]。HLA 的運(yùn)行支撐環(huán)境將復(fù)雜的上層仿真系統(tǒng)與底層通信系統(tǒng)分離,它由聯(lián)邦/聯(lián)邦成員規(guī)則、對(duì)象模型模版、接口規(guī)范、運(yùn)行支撐環(huán)境等組成[2-3]。其中運(yùn)行支撐環(huán)境接口規(guī)范包含聯(lián)邦管理、時(shí)間管理、聲明管理、所有權(quán)管理、對(duì)象管理和數(shù)據(jù)分發(fā)管理[4-5]6個(gè)方面的內(nèi)容。

1 DDM算法概述

DDM是HLA的重要管理服務(wù)之一,是支撐運(yùn)行環(huán)境在聲明管理服務(wù)實(shí)現(xiàn)基于類的數(shù)據(jù)過(guò)濾后,再對(duì)區(qū)域發(fā)布的數(shù)據(jù)值進(jìn)行過(guò)濾,其目的是為了減少在大規(guī)模分布式仿真中大量不必要數(shù)據(jù)和冗余數(shù)據(jù)的發(fā)送與接收。DDM算法的關(guān)鍵是判斷仿真成員發(fā)布區(qū)域和訂購(gòu)區(qū)域是否存在交疊區(qū)域,如存在,則發(fā)布邦員將發(fā)布數(shù)據(jù)發(fā)送給指定的訂購(gòu)邦員。在大規(guī)模的仿真實(shí)驗(yàn)中,仿真實(shí)體之間的交互數(shù)據(jù)量非常龐大,這會(huì)占據(jù)大量的網(wǎng)絡(luò)資源,所以管理仿真實(shí)體之間的數(shù)據(jù)流量交互,減少冗余數(shù)據(jù)的分發(fā),對(duì)于解決網(wǎng)絡(luò)資源擁堵,降低仿真延遲,增強(qiáng)仿真的可擴(kuò)縮性具有重大的意義。

DDM數(shù)據(jù)分發(fā)管理算法的本質(zhì)是判斷存在重疊的發(fā)布區(qū)域和訂購(gòu)區(qū)域,確定發(fā)布者和訂購(gòu)者之間的供求關(guān)系,其匹配算法的時(shí)空復(fù)雜度直接決定著分布式仿真系統(tǒng)的穩(wěn)定性和可擴(kuò)縮性。經(jīng)典區(qū)域匹配算法有直接區(qū)域匹配算法、基于排序算法、基于網(wǎng)格算法[6-7]。

直接區(qū)域匹配算法是在定義好的路徑空間上建立多維坐標(biāo)系統(tǒng),在相交區(qū)域匹配過(guò)程中,通過(guò)遍歷每一個(gè)發(fā)布區(qū)域與所有的訂購(gòu)區(qū)域進(jìn)行區(qū)域匹配,若發(fā)布區(qū)域與訂購(gòu)區(qū)域有相交區(qū)域,則認(rèn)為仿真實(shí)體之間存在數(shù)據(jù)交互,為精確匹配。但是隨著仿真復(fù)雜度的不斷擴(kuò)大,實(shí)現(xiàn)直接區(qū)域匹配算法時(shí)需要的區(qū)域匹配的計(jì)算量也將會(huì)十分龐大,耗時(shí)會(huì)呈指數(shù)級(jí)增長(zhǎng)。若有n個(gè)訂購(gòu)邦員與n個(gè)發(fā)布邦員進(jìn)行仿真實(shí)驗(yàn),則所需的匹配時(shí)間為0(n2),算法的可擴(kuò)縮性差。

基于網(wǎng)格的方法提供了一種間接的區(qū)域匹配方法,多維路徑空間被分割成為邊長(zhǎng)大小相同的網(wǎng)格,若訂購(gòu)區(qū)域與發(fā)布區(qū)域覆蓋了相同的網(wǎng)格,則認(rèn)為相應(yīng)的仿真實(shí)體之間存在數(shù)據(jù)交互,以此確定哪些仿真實(shí)體之間是有數(shù)據(jù)交互,避免發(fā)送冗余數(shù)據(jù)?；诰W(wǎng)格的方法易于實(shí)現(xiàn),且具有較好的可擴(kuò)縮性,但是,存在發(fā)布區(qū)域與訂購(gòu)區(qū)域覆蓋同一個(gè)網(wǎng)格但沒(méi)有交集的情況,即虛假連接;若發(fā)布區(qū)域與訂購(gòu)區(qū)域同時(shí)覆蓋了多個(gè)相同的網(wǎng)格,數(shù)據(jù)會(huì)重復(fù)發(fā)送,即存在冗余連接[8-12]?；诰W(wǎng)格算法的匹配時(shí)間與網(wǎng)格的密度有很大關(guān)系,網(wǎng)格密度越大,匹配精確度越高,但匹配時(shí)間越長(zhǎng),虛假連接少;網(wǎng)格密度越小,匹配精度越低,虛假連接多。

基于排序的算法是將發(fā)布區(qū)域和訂購(gòu)區(qū)域的高低坐標(biāo)值投影在路徑空間的坐標(biāo)系統(tǒng)上,若發(fā)布區(qū)域高低坐標(biāo)范圍和訂購(gòu)區(qū)域的高低坐標(biāo)范圍在路徑空間上所有維度都有重疊,則認(rèn)為發(fā)布區(qū)域和訂購(gòu)區(qū)域相交,算法是精確匹配。假設(shè)在d維路徑空間上共有n個(gè)訂購(gòu)區(qū)域與n個(gè)發(fā)布區(qū)域進(jìn)行仿真實(shí)驗(yàn),則所需的匹配時(shí)間為O(d×nlogn)。因而,在大規(guī)模仿真中區(qū)域匹配算法依然具有較好的擴(kuò)充性和健壯性。但是,基于排序的DDM算法[13-17]在進(jìn)行匹配的過(guò)程中,要判斷每一個(gè)邊界值的信息,包括該邊界值是訂購(gòu)區(qū)域還是發(fā)布區(qū)域、上邊界還是下邊界,并且需要消耗存儲(chǔ)空間將掃描到的邊界值存儲(chǔ)在集合中,算法的時(shí)空開(kāi)銷大。

2 改進(jìn)的DDM排序算法

在原始的排序算法中,每一維的交互信息都需要一個(gè)對(duì)應(yīng)的矩陣來(lái)存儲(chǔ),即需要大量的存儲(chǔ)空間,而且需要大量時(shí)間對(duì)邊界類型進(jìn)行判斷,而改進(jìn)的排序算法在映射基礎(chǔ)上,將發(fā)布區(qū)域與訂購(gòu)區(qū)域的邊界值分開(kāi)存儲(chǔ)并排序,并通過(guò)判斷訂購(gòu)區(qū)域中的邊界值是否處于發(fā)布區(qū)域上下邊界值的區(qū)間內(nèi),如果處于區(qū)間內(nèi),則訂購(gòu)區(qū)域與發(fā)布區(qū)域相交。

初始時(shí),將區(qū)域的各維信息分別存儲(chǔ)在各自對(duì)應(yīng)的集合中,并將發(fā)布區(qū)域與訂購(gòu)區(qū)域的邊界信息分開(kāi)存儲(chǔ)。然后,將訂購(gòu)區(qū)域的邊界信息集合進(jìn)行排序,通過(guò)遍歷發(fā)布區(qū)域,與所有訂購(gòu)區(qū)域依次進(jìn)行匹配,假設(shè)發(fā)布區(qū)域與訂購(gòu)區(qū)域數(shù)量相等且都為n,那么將區(qū)域的重疊信息記錄在一個(gè)初始化為0的n×n的矩陣中,它的行列號(hào)分別代表訂購(gòu)區(qū)域與發(fā)布區(qū)域。在對(duì)當(dāng)前維度上的相交信息存儲(chǔ)時(shí),只需對(duì)存儲(chǔ)矩陣中與之前匹配過(guò)的維數(shù)相等的元素值所對(duì)應(yīng)的區(qū)域信息進(jìn)行處理,如果當(dāng)前維度有重疊則將矩陣中對(duì)應(yīng)的元素加1。對(duì)路徑空間中的所有維度重復(fù)上述步驟,如果最后矩陣中的元素值與維數(shù)相等,則認(rèn)為該元素值對(duì)應(yīng)的發(fā)布區(qū)域和訂購(gòu)區(qū)域就有交疊。

圖1是一個(gè)二維路徑空間的示意圖,路徑空間中有兩個(gè)聯(lián)邦成員F1={(P1),(S1)},F2={(P2),(S2)}。由圖可知,將發(fā)布區(qū)域在X軸上的高低坐標(biāo)值表示為(XSi,X1Si)在Y軸上的高低坐標(biāo)值表示為(YSi,Y1Si)。

Fig.1 Two-dimension spatial schematic diagram圖1 二維空間示意圖

改進(jìn)后的排序算法實(shí)現(xiàn)過(guò)程如下:

(1)在X維、Y維插入集合時(shí),把訂購(gòu)區(qū)域與發(fā)布區(qū)域分開(kāi)存儲(chǔ):

X維訂購(gòu)區(qū)域:{XS1，X’S1，XS2，X’S2}

X維發(fā)布區(qū)域:{XP1，X’P1，XP2，X’P2}

Y維訂購(gòu)區(qū)域:{YS1，Y’S1，YS2，Y’S2}}

Y維發(fā)布區(qū)域:{YP1，Y’P1，YP2，Y’P2}

(2)將X維、Y維訂購(gòu)區(qū)域的坐標(biāo)點(diǎn)按值的大小由小到大分開(kāi)排序

X維:{XS1，XS2，X’S2，X’S1}

Y維:{YS2，Y’S2，YS1，Y’S1}

同時(shí)為存儲(chǔ)交叉信息建立一個(gè)2*2矩陣,矩陣的行列數(shù)與發(fā)布區(qū)域和訂購(gòu)區(qū)域相同,分別用來(lái)存儲(chǔ)各維相交信息的結(jié)果,矩陣初始化為0。

(3)首先對(duì)X維進(jìn)行處理,將發(fā)布區(qū)域集合中的值,依次與訂購(gòu)區(qū)域中的值進(jìn)行比較。

1>XP2:P2的低邊界點(diǎn),將XP2與訂購(gòu)區(qū)域中的值比較,若XP2的值大于訂購(gòu)區(qū)域的邊界值,即XP2>XS1,則將P2的高邊界點(diǎn)X’P2從XS1開(kāi)始與訂購(gòu)區(qū)域中的值依次相比較,若X’P2的值大于訂購(gòu)區(qū)域中的邊界值,即X’P2>X’S2,則停止比較。

2>則在1>中與發(fā)布區(qū)域上下邊界都比較過(guò)的訂購(gòu)區(qū)域,就認(rèn)為與該發(fā)布區(qū)域在X維上有交集。

3>將發(fā)布區(qū)域集合中所有的邊界點(diǎn)都做該比較。獲得X維的矩陣相交信息為:

S1S2P1P20011

(4)同理,將Y維中的邊界信息也進(jìn)行如步驟(2)中的匹配,得到的相交矩陣信息為

S1S2P1P20021

這種改進(jìn)的基于排序的DDM算法是利用高低邊界值投影在坐標(biāo)軸上,然后根據(jù)值的大小所覆蓋范圍的相交信息判定各區(qū)域之間的匹配關(guān)系。算法將各維度的訂購(gòu)區(qū)域的上下邊界值分開(kāi)存儲(chǔ)進(jìn)行排序,然后利用發(fā)布區(qū)域的邊界值信息掃描訂購(gòu)區(qū)域的有序表,并進(jìn)行比較,在存儲(chǔ)矩陣中填入相交信息。在后續(xù)維度的匹配中,相交信息只需要對(duì)該矩陣中的元素值進(jìn)行修改,有交疊區(qū)域則將對(duì)應(yīng)的值加1,降低了算法的空間復(fù)雜度,而且在匹配坐標(biāo)值過(guò)程中減少了判斷次數(shù),從而減少了匹配時(shí)間。

3 仿真實(shí)驗(yàn)數(shù)據(jù)分析

本文參考了相關(guān)文獻(xiàn)設(shè)計(jì)了仿真實(shí)驗(yàn)[18],用計(jì)算機(jī)模擬隨機(jī)產(chǎn)生數(shù)量不同的仿真區(qū)域,通過(guò)DDM算法判斷發(fā)布區(qū)域與訂購(gòu)區(qū)域之間是否存在交疊區(qū)域,仿真平臺(tái)為Windows7旗艦版64位系統(tǒng),運(yùn)行內(nèi)存為2GB,CPU為單核3.0 GHz。在空間路徑坐標(biāo)系中隨機(jī)產(chǎn)生1 000,2 000,3 000,4 000,…,9 000個(gè)大小不同的矩形區(qū)域,每個(gè)聯(lián)邦成員中包含的區(qū)域的數(shù)目分別選用1,10,2,則仿真節(jié)點(diǎn)數(shù)量的范圍是從1 000到9 000之間變化,限域邊長(zhǎng)采用10,150,200。由于不同限域的實(shí)驗(yàn)結(jié)果差別較小且類似,所以圖2(a),圖2(b),圖2(c)分別給出在路徑空間為二維、三維、四維情況下,限域邊長(zhǎng)選擇150時(shí)所產(chǎn)生的實(shí)驗(yàn)結(jié)果。

Fig.2 Comparison of execution time in 2-dimension,3-dimension and 4-dimension圖2 執(zhí)行時(shí)間在二維、三維、四維下的比較

由實(shí)驗(yàn)結(jié)果圖可以看出,改進(jìn)的排序算法在仿真規(guī)模較小,區(qū)域數(shù)目較少(少于4 000)時(shí),算法的時(shí)間執(zhí)行效率并沒(méi)有明顯優(yōu)于經(jīng)典的排序算法;而隨著仿真規(guī)模的不斷擴(kuò)大,區(qū)域數(shù)目大于4 000且不斷增大時(shí),改進(jìn)算法的與經(jīng)典算法時(shí)間執(zhí)行效率的差別逐漸顯現(xiàn)。而且,仿真的系統(tǒng)維度越多越復(fù)雜,改進(jìn)算法在時(shí)間執(zhí)行效率上越優(yōu)于經(jīng)典算法。

從以上分析可以得出,隨著仿真節(jié)點(diǎn)以及區(qū)域數(shù)目的增加,改進(jìn)算法的執(zhí)行時(shí)間與空間都優(yōu)于原始算法,算法在仿真交互數(shù)據(jù)達(dá)到一定數(shù)量時(shí),算法執(zhí)行時(shí)間提高比例穩(wěn)定在9%左右。

4 結(jié)論

本文在區(qū)域映射到路徑空間的基礎(chǔ)上,將發(fā)布區(qū)域與訂購(gòu)區(qū)域的上下邊界值分開(kāi)存儲(chǔ),并通過(guò)判斷訂購(gòu)區(qū)域中的邊界值是否處于發(fā)布區(qū)域上下邊界值的區(qū)間內(nèi)來(lái)確定是否相交,提高區(qū)域匹配的運(yùn)行效率;并通過(guò)只對(duì)一個(gè)存儲(chǔ)相交信息矩陣的修改,降低了算法空間復(fù)雜度。在仿真實(shí)驗(yàn)中考察了算法在區(qū)域數(shù)目、限域數(shù)目、聯(lián)邦數(shù)目情況下的平均匹配時(shí)間,實(shí)驗(yàn)結(jié)果表明改進(jìn)算法在時(shí)間效率和空間效率上都具有優(yōu)勢(shì),隨著區(qū)域數(shù)目的不斷增加,在仿真數(shù)據(jù)達(dá)到一定規(guī)模時(shí),改進(jìn)的排序算法執(zhí)行時(shí)間提高比例穩(wěn)定在9%,對(duì)大規(guī)模仿真系統(tǒng)的可擴(kuò)縮性有很好的支持。