一种基于障碍距离的兴趣管理方法

杨琳琳　刘厚泉　赵志凯

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