一種基于障礙距離的興趣管理方法

楊琳琳　劉厚泉　趙志凱

1(中國礦業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院　江蘇 徐州 221116)2(中國礦業(yè)大學(xué)物聯(lián)網(wǎng)感知礦山研究中心　江蘇 徐州 221008)

?

一種基于障礙距離的興趣管理方法

楊琳琳1劉厚泉1趙志凱2

1(中國礦業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院江蘇 徐州 221116)2(中國礦業(yè)大學(xué)物聯(lián)網(wǎng)感知礦山研究中心江蘇 徐州 221008)

興趣管理是提高協(xié)同虛擬環(huán)境擴展性的一種常用技術(shù)?，F(xiàn)有的興趣管理方法大多采用理想歐式距離進行興趣匹配，沒有考慮虛擬空間中存在障礙物的情況。針對現(xiàn)有方法的不足提出一種基于障礙距離的興趣管理方法。該方法在混合法的基礎(chǔ)上，對虛擬環(huán)境中的障礙物進行多邊形建模。首先采用網(wǎng)格劃分虛擬空間，縮小實體的興趣匹配范圍，然后使用障礙距離進行興趣匹配。實驗結(jié)果表明，該方法可以進一步減少系統(tǒng)中不必要的網(wǎng)絡(luò)開銷，提高協(xié)同虛擬環(huán)境的擴展性。

興趣管理障礙距離協(xié)同虛擬環(huán)境混合法網(wǎng)格

0　引　言

協(xié)同虛擬環(huán)境CVE[1]是一種支持位于不同地理位置的多個用戶進行協(xié)同工作的分布式虛擬環(huán)境。近年來，CVE系統(tǒng)廣泛應(yīng)用于軍事仿真、網(wǎng)絡(luò)游戲、虛擬實驗[2]、遠(yuǎn)程教育等領(lǐng)域。協(xié)同虛擬環(huán)境作為共享的虛擬空間，要求各個客戶端的虛擬場景必須保持高度的一致。參與虛擬環(huán)境的實體通過實時地向其他實體發(fā)送自己的狀態(tài)更新信息同時接收其他實體的狀態(tài)更新信息來維持客戶端場景的一致性。維護虛擬場景的一致性帶來大量的通信開銷，隨著系統(tǒng)規(guī)模的增大，協(xié)同虛擬環(huán)境面臨著規(guī)模擴展性問題，即如何在大量用戶參與的情況下控制數(shù)據(jù)傳輸，保證用戶之間進行有效通信。

興趣管理IM是一種常用的數(shù)據(jù)過濾技術(shù)，其基本思想是讓所有用戶只接收他們感興趣的數(shù)據(jù)，通過在虛擬環(huán)境中過濾不相關(guān)信息來減少網(wǎng)絡(luò)開銷，同時降低用戶的處理開銷，從而提高系統(tǒng)的擴展性?，F(xiàn)有的興趣管理方法基本上可分為以下五類：區(qū)域法、氛圍法、基于類別的方法、基于可見性的方法和混合法[3]。這些方法各有其優(yōu)缺點，但大多沒有考慮虛擬環(huán)境中存在障礙物的情況，直接使用歐式距離進行興趣匹配?；诳梢娦缘姆椒m然考慮了障礙物，但是其一般通過三角剖分[4]劃分虛擬空間，構(gòu)造三角網(wǎng)格的空間復(fù)雜度較高，而且大小不等的三角網(wǎng)格并不能精確描述用戶的興趣范圍。本文對現(xiàn)有的興趣管理方法進行了研究，提出一種新的基于障礙距離的興趣管理方法，在混合法的基礎(chǔ)上采用障礙距離進行興趣匹配。該算法可以更加精確地描述用戶的興趣范圍，進一步減少系統(tǒng)的網(wǎng)絡(luò)開銷，達(dá)到提高系統(tǒng)擴展性的目的。

1　相關(guān)工作

興趣管理技術(shù)是隨著虛擬現(xiàn)實技術(shù)和計算機網(wǎng)絡(luò)技術(shù)的蓬勃發(fā)展而逐漸成熟起來的，本節(jié)對現(xiàn)有的5種主要興趣管理方法進行簡要介紹。

區(qū)域法[5]通過某種方式將虛擬空間劃分成若干區(qū)域(region，可以是矩形、正六邊形或其他形狀)，每個region分配一個組播地址，將用戶的信息交互限制在region內(nèi)，以此減少系統(tǒng)中的信息傳輸。網(wǎng)格法[6]是一種特殊的區(qū)域法，其將虛擬空間劃分成一組大小相等的正方形網(wǎng)格，將實體映射到它的所屬網(wǎng)格，然后采用組播技術(shù)實現(xiàn)數(shù)據(jù)過濾。區(qū)域法簡單、容易實現(xiàn)、匹配復(fù)雜度低，但是過濾效果比較差，系統(tǒng)中包含很多不相關(guān)信息的傳輸。

氛圍法使用aura表示每個仿真實體的興趣域，aura有時也稱作nimbus、AOI(AreaofInterest)或awarenessarea[7]，它定義了實體的感知區(qū)域。當(dāng)兩個實體的aura相交時，它們之間就建立通信連接。氛圍法過濾效果比區(qū)域法好很多，但是它要對虛擬環(huán)境中的每對實體都進行興趣匹配，這導(dǎo)致大量的計算開銷，影響了興趣管理的效率。

類別法[8]源于HLA(HighLevelArchitecture)中的數(shù)據(jù)分發(fā)管理服務(wù)，采用基于類別/屬性的過濾機制。仿真實體通過聲明管理服務(wù)來發(fā)布/訂閱數(shù)據(jù)，只要實體所訂閱類的任何對象屬性發(fā)生改變，該實體就會收到通知。這種方法靜態(tài)地表示對象的興趣域，實體只與特定類的對象建立通信關(guān)系，不適于描述協(xié)同虛擬環(huán)境中不斷變化的實體興趣域。

基于可見性的方法根據(jù)仿真實體實際的可視范圍進行興趣匹配。如果某個實體被障礙物遮擋住，即使它離用戶很近，用戶也不可能看到它。在這種情況下認(rèn)為用戶對該實體不感興趣，用戶不需要接收該實體的狀態(tài)更新信息。例如文獻[9]中采用Delaunay三角剖分劃分虛擬空間能夠較好地隔離障礙物，過濾精度高；但是構(gòu)造Delaunay圖的代價較高，而且使用一組三角形區(qū)域并不能完全覆蓋實體的興趣域。

針對區(qū)域法和氛圍法的優(yōu)點與不足，一些研究者提出混合法[10]，采用區(qū)域法減少氛圍法中的興趣匹配次數(shù)，在保證過濾效果的同時降低計算開銷?；旌戏軌蛟跀?shù)據(jù)過濾精度和算法匹配效率之間取得較好的平衡，但是未考慮虛擬環(huán)境中存在障礙物的情況。在障礙空間中，實體的興趣域并不是簡單的以實體位置為中心的圓形AOI，當(dāng)兩個實體之間存在障礙物時，它們可能看不到彼此，也就不必向彼此發(fā)送位置等狀態(tài)更新信息。

針對上述方法存在的問題，我們結(jié)合混合法，提出對虛擬空間中任意形狀的障礙物進行多邊形建模[11]，在此基礎(chǔ)上計算仿真實體之間的障礙距離，從而進行興趣匹配。

2　基于障礙距離的興趣管理方法

2.1基本思想

本文方法綜合了區(qū)域法和氛圍法的混合方法，采用以實體位置為中心、感知半徑r為半徑的圓形區(qū)域作為實體的初始AOI，對虛擬空間中的障礙物進行多邊形建模，采用一組障礙邊表示某個障礙物。首先對虛擬空間進行網(wǎng)格劃分，將實體映射到其所屬網(wǎng)格，根據(jù)所屬網(wǎng)格計算其鄰居網(wǎng)格，將實體興趣匹配的范圍縮小在鄰居網(wǎng)格內(nèi)。然后在興趣匹配的過程中對鄰居實體連線和障礙邊進行相交測試，只要與其中任何一條障礙邊相交，則該鄰居實體就不可見。障礙空間中實體的實際AOI為圖1所示的淺灰色區(qū)域。為方便描述，同時又不失一般性，整個虛擬空間在二維平面討論。

圖1　障礙空間中的實體AOI

2.2相關(guān)定義

虛擬空間：記為S。設(shè)三維空間R3∈S，二維空間R2∈S，定義三維空間R3到二維空間R2的映射函數(shù)f={(x,y,z)}→{(x,y)}。

實體集：U={u1,u2,…,un}，n表示虛擬環(huán)境中的仿真實體個數(shù)。仿真實體ui的興趣實體集合為IU(ui)={u1,u2,…,um}，其中m表示實體的興趣實體個數(shù)。

障礙集：O={o1,o2,…,ok}，k表示虛擬空間中有效障礙物的個數(shù)，虛擬空間中的障礙物大小不一，一些比較小的障礙物并不會對實體的可視范圍造成影響。在對障礙物進行建模前先進行預(yù)處理，剔除一些不必要的障礙物，得到障礙集。每個障礙物用一個多邊形表示，記為G=(V,E)，V={v1,v2,…,vr}是障礙物的頂點集，E={e1,e2,…,en}是障礙物對應(yīng)的障礙邊集。障礙頂點用其在二維空間中的位置坐標(biāo)表示，即v=(x,y)。每條障礙邊用一對障礙頂點表示，即e=(v1,v2)，v1表示障礙邊的第一個頂點，v2表示障礙邊的另一個頂點。

障礙距離：實體ui、uj之間的障礙距離用OD(ui,uj)表示。當(dāng)ui、uj之間的連線不與任何障礙邊相交時，ui與uj是可見的，OD(ui,uj)為直接歐式距離；當(dāng)ui、uj之間的連線與某個障礙邊相交時，ui與uj是不可見的，障礙距離可視為無限大，記為OD(ui,uj)=∞。實體的興趣實體即為與其障礙距離小于感知半徑r的所有其他實體。

網(wǎng)格：每個網(wǎng)格用其在x維和y維投影的上下限表示，并賦予唯一標(biāo)識，記為cell=(xlow,xupper,ylow,yupper)，網(wǎng)格邊長用l表示。

2.3算法描述

在描述算法之前，先討論劃分虛擬空間時一個很關(guān)鍵的問題：網(wǎng)格邊長l的選取。選擇最優(yōu)的l比較困難，l較大，單個網(wǎng)格中包含的實體較多，需要執(zhí)行的興趣匹配次數(shù)就會增多，帶來很多不必要的計算開銷；l較小，興趣匹配次數(shù)相應(yīng)減少，計算開銷少，但是網(wǎng)格越小，劃分的網(wǎng)格數(shù)目就越多，導(dǎo)致空間復(fù)雜度增大。維護虛擬空間的空間復(fù)雜度與網(wǎng)格數(shù)量緊密相關(guān)，但其仍然是常量級的，無論參與的實體數(shù)有多少都保持不變，所以考慮選取的網(wǎng)格邊長l盡可能小。同時根據(jù)算法的基本思想，需要將實體的興趣匹配范圍限制在鄰居網(wǎng)格內(nèi)，即鄰居網(wǎng)格必須能夠包圍實體的AOI，則必須滿足l≥r，故l的最佳取值為感知半徑r。

根據(jù)基本思想，本文方法的算法流程包括兩個子過程：一是興趣匹配算法流程，二是計算障礙距離的算法流程。算法的具體描述如下：

算法1興趣匹配算法

算法輸入：實體p，感知半徑r，障礙邊集edges

算法輸出：實體p的興趣實體集IU(p)

Begin

IU(p)←? ;

//初始化興趣集

Calculatercell(p);

//計算實體p的所屬網(wǎng)格

Calculatencell(p);

//計算實體p的鄰居網(wǎng)格

Foreachcell∈ncell(p)

Foreachu∈(cell)

If(OD(p,u,edges)≤r)

IU(p).add(u);

//將所求障礙距離小于r的鄰居實體加入興趣集

EndIf

EndFor

EndFor

ReturnIU(p);

End

算法2計算障礙距離

算法輸入：實體p、q，障礙邊集edges

算法輸出：實體p、q之間的障礙距離OD(p,q)

Begin

Definev1asthepositionofpinR2;

//v1為實體p在二維空間中的位置坐標(biāo)點

Definev2asthepositionofqinR2;

//v2為實體q在二維空間中的位置坐標(biāo)點

DefineuVector;

//線段(v1,v2)對應(yīng)的向量為uVector

Foreache ∈ edges

DefineoVector;

//障礙邊e對應(yīng)的向量為oVector

If(uVector與oVector相交)

//與障礙邊進行相交測試

OD(p,q)←∞;

ReturnOD(p,q);

EndIf

EndFor

OD(p,q)←dist(p,q);

ReturnOD(p,q);

End

3　實驗分析

實驗環(huán)境：Intel2.93GHz雙核處理器、2GB內(nèi)存、Windows7、MicrosoftVisualStudio2010、Unity4.6。仿真系統(tǒng)采用C#語言編寫，對障礙空間中的仿真實體進行興趣管理。

基于本文方法，我們實現(xiàn)了一個虛擬漫游系統(tǒng)。將所提算法運用到服務(wù)器端，系統(tǒng)客戶端使用Unity3D引擎實現(xiàn)虛擬場景的繪制，設(shè)置場景的地形大小為1000×1000，在虛擬場景中創(chuàng)建了50個障礙物，共包含130條障礙邊，感知半徑r為100，興趣域更新的時間間隔設(shè)為1秒。

興趣管理算法主要有兩個性能指標(biāo)：過濾效果和計算效率。過濾效果通過實體接收的信息總量(ReceivedCount)和相關(guān)信息接收率(RelatedRate)表示。在相同實驗條件下，ReceivedCount越小說明過濾掉的信息越多，系統(tǒng)整體的網(wǎng)絡(luò)開銷就越低，但這樣還不能充分說明過濾效果良好。過濾掉的數(shù)據(jù)可能包含無關(guān)信息和相關(guān)信息，為驗證方法有效性，還需要評估相關(guān)信息接收率。相關(guān)信息接收率定義為：RelatedRate=相關(guān)信息接收量/需要接收的相關(guān)信息量。RelatedRate越高，說明過濾掉的相關(guān)信息越少，過濾掉的無關(guān)信息越多，系統(tǒng)降低的網(wǎng)絡(luò)開銷確實是不必要的，能夠充分說明過濾效果良好。計算效率通過興趣匹配算法的執(zhí)行時間T表示，T越小表示興趣匹配的效率越高。

為驗證本文算法的性能，我們進行了對比實驗，對比混合法和本文方法在過濾效果和計算效率方面的差異。分別向虛擬環(huán)境中投入10、20、40、60、80、100個仿真實體，實體進入虛擬環(huán)境后自動移動兩分鐘，監(jiān)測兩分鐘內(nèi)實體接收的信息總量、相關(guān)信息接收率以及算法執(zhí)行時間的變化。實驗結(jié)果如圖2-圖4所示。

圖2　實體接收的信息總量(bytes)曲線圖

圖4　算法執(zhí)行時間(ms)曲線圖

從圖2看出，在相同的實驗條件下，采用本文方法實體接收的信息總量較少；而圖3顯示，采用本文方法的相關(guān)信息接收率和混合法一樣均在90%以上波動。這說明實體接收了絕大部分的相關(guān)信息，減少的信息總量基本上是無關(guān)信息。由圖2、圖3可知，本文方法能夠比混合法過濾掉更多的無關(guān)信息。

圖4表明本文方法的執(zhí)行時間比混合法略高，但總體時間差別不大。這是因為本文方法采用障礙距離進行興趣匹配，計算障礙距離與直接使用歐式距離相比增加了一定的計算開銷。由于虛擬空間中的障礙物是固定的，增加的計算機開銷是常量級的，只與障礙集的規(guī)模有關(guān)。隨著仿真實體增多，該方法仍然能夠保證較高的效率。

通過以上實驗分析證明基于障礙距離的興趣管理方法和混合法相比能夠進一步減少系統(tǒng)的網(wǎng)絡(luò)開銷，算法效率穩(wěn)定，有助于提高協(xié)同虛擬環(huán)境的可擴展性。

4　結(jié)　語

本文提出了一種基于障礙距離的興趣管理方法。該方法考慮了虛擬環(huán)境中存在多個不規(guī)則障礙物的情況，對虛擬環(huán)境中的障礙物進行多邊形建模，使用障礙頂點和障礙邊表示障礙物；對傳統(tǒng)混合法的興趣匹配過程進行了改進，通過與障礙邊進行相交測試計算實體間的障礙距離，基于障礙距離計算興趣域，進一步減少不相關(guān)信息的傳輸。實驗結(jié)果表明，該方法能夠比混合法取得更好的過濾效果。本文的下一步工作是如何在此基礎(chǔ)上降低算法的計算開銷，進一步提高算法的整體性能。

[1]MontoyaMM,MasseyAP,LockwoodNS.3Dcollaborativevirtualenvironments:exploringthelinkbetweencollaborativebehaviorsandteamperformance[J].DecisionSciences,2011,42(2):451-476.

[2] 甘茂華,阮麗娜,李昌國,等.多人協(xié)作虛擬實驗室綜述[J].計算機應(yīng)用與軟件,2010,27(5):130-132,143.

[3]LiuES,TheodoropoulosGK.Interestmanagementfordistributedvirtualenvironments:Asurvey[J].ACMComputingSurveys(CSUR),2014,46(4):51.

[4] 周佳文,薛之昕,萬施.三角剖分綜述[J].計算機與現(xiàn)代化,2010(7):75-78.

[5]LiuES,TheodoropoulosGK.Aparallelinterestmatchingalgorithmfordistributed-memorysystems[C]//DistributedSimulationandRealTimeApplications(DS-RT),2011IEEE/ACM15thInternationalSymposiumon.IEEE,2011:36-43.

[6]LiY,FujimotoR,HunterM,etal.Aninterestmanagementschemeformobilepeer-to-peersystems[C]//Proceedingsofthe2011WinterSimulationConference(WSC).IEEE,2011:2747-2759.

[7]YahyaviA,KemmeB.Peer-to-peerarchitecturesformassivelymultiplayeronlinegames:Asurvey[J].ACMComputingSurveys(CSUR),2013,46(1):9.

[8] 梁洪波,朱衛(wèi)國,姚益平,等.一種面向大規(guī)模HLA仿真的并行區(qū)域匹配算法[J].國防科技大學(xué)學(xué)報,2013,35(3):84-91.

[9]DenaultA,CaasC,KienzleJ,etal.Triangle-basedobstacle-awareloadbalancingformassivelymultiplayergames[C]//NetworkandSystemsSupportforGames(NetGames),2011 10thAnnualWorkshopon.IEEE,2011:1-6.

[10]PanK,CaiWT,TangXY,etal.Ahybridinterestmanagementmechanismforpeer-to-peernetworkedvirtualenvironments[C]//ParallelandDistributedProcessing(IPDPS),2010IEEEInternationalSymposiumon.IEEE,2010:1-12.

[11] 王小樂,劉青寶,陸昌輝,等.一種處理障礙約束的聚類算法[J].計算機應(yīng)用,2009,29(2):406-408,411.

ANINTERESTMANAGEMENTSCHEMEBASEDONOBSTACLEDISTANCE

YangLinlin1LiuHouquan1ZhaoZhikai2

1(SchoolofComputerScienceandTechnology,ChinaUniversityofMiningandTechnology,Xuzhou221116,Jiangsu,China)2(IoTPerceptionMineResearchCenter,ChinaUniversityofMiningandTechnology,Xuzhou221008,Jiangsu,China)

Interestmanagementisacommontechnologytoimprovethescalabilityofcollaborativevirtualenvironments.ExistingmethodsmostlyuseidealEuclideandistanceforinterestmatchingwithoutconsideringthepresenceofobstaclesinvirtualspace.Aimingattheshortcomingsofexistingmethods,weproposeanobstacledistance-basedinterestmanagementscheme.Onthebasisofthehybridmethod,thisschememodelstheobstaclesinvirtualenvironmentbypolygons.Firstitdividesthevirtualspacebygridstolessentheinterestmatchingareaofentities.Thenitadoptsobstacledistancetomatchinterests.Experimentalresultsshowthatthisschemecanfurtherreduceunnecessarynetworkoverheadinthesystemandimprovethescalabilityofthecollaborativevirtualenvironment.

InterestmanagementObstacledistanceCollaborativevirtualenvironmentHybridmethodGrid

2015-08-15。中央高?；究蒲袠I(yè)務(wù)費專項資金項目(2014QNB45)；江蘇省自然科學(xué)基金青年基金項目(BK20140216)。楊琳琳，碩士生，主研領(lǐng)域：協(xié)同虛擬環(huán)境，興趣管理。劉厚泉，教授。趙志凱，助理研究員。

TP

ADOI:10.3969/j.issn.1000-386x.2016.10.019