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

楊琳琳　劉厚泉　趙志凱

1(中國礦業大學計算機科學與技術學院　江蘇 徐州 221116)2(中國礦業大學物聯網感知礦山研究中心　江蘇 徐州 221008)

?

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

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

1(中國礦業大學計算機科學與技術學院江蘇 徐州 221116)2(中國礦業大學物聯網感知礦山研究中心江蘇 徐州 221008)

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

興趣管理障礙距離協同虛擬環境混合法網格

0　引　言

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

興趣管理IM是一種常用的數據過濾技術，其基本思想是讓所有用戶只接收他們感興趣的數據，通過在虛擬環境中過濾不相關信息來減少網絡開銷，同時降低用戶的處理開銷，從而提高系統的擴展性。現有的興趣管理方法基本上可分為以下五類：區域法、氛圍法、基于類別的方法、基于可見性的方法和混合法[3]。這些方法各有其優缺點，但大多沒有考慮虛擬環境中存在障礙物的情況，直接使用歐式距離進行興趣匹配。基于可見性的方法雖然考慮了障礙物，但是其一般通過三角剖分[4]劃分虛擬空間，構造三角網格的空間復雜度較高，而且大小不等的三角網格并不能精確描述用戶的興趣范圍。本文對現有的興趣管理方法進行了研究，提出一種新的基于障礙距離的興趣管理方法，在混合法的基礎上采用障礙距離進行興趣匹配。該算法可以更加精確地描述用戶的興趣范圍，進一步減少系統的網絡開銷，達到提高系統擴展性的目的。

1　相關工作

興趣管理技術是隨著虛擬現實技術和計算機網絡技術的蓬勃發展而逐漸成熟起來的，本節對現有的5種主要興趣管理方法進行簡要介紹。

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

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

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

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

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

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

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

2.1基本思想

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

圖1　障礙空間中的實體AOI

2.2相關定義

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

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

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

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

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

2.3算法描述

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

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

算法1興趣匹配算法

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

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

Begin

IU(p)←? ;

//初始化興趣集

Calculatercell(p);

//計算實體p的所屬網格

Calculatencell(p);

//計算實體p的鄰居網格

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在二維空間中的位置坐標點

Definev2asthepositionofqinR2;

//v2為實體q在二維空間中的位置坐標點

DefineuVector;

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

Foreache ∈ edges

DefineoVector;

//障礙邊e對應的向量為oVector

If(uVector與oVector相交)

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

OD(p,q)←∞;

ReturnOD(p,q);

EndIf

EndFor

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

ReturnOD(p,q);

End

3　實驗分析

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

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

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

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

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

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

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

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

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

4　結　語

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

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

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

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

[4] 周佳文,薛之昕,萬施.三角剖分綜述[J].計算機與現代化,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] 梁洪波,朱衛國,姚益平,等.一種面向大規模HLA仿真的并行區域匹配算法[J].國防科技大學學報,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].計算機應用,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。中央高校基本科研業務費專項資金項目(2014QNB45)；江蘇省自然科學基金青年基金項目(BK20140216)。楊琳琳，碩士生，主研領域：協同虛擬環境，興趣管理。劉厚泉，教授。趙志凱，助理研究員。

TP

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