DVE中基于興趣層次的動態(tài)更新調(diào)度策略

摘 要：在大規(guī)模分布式虛擬環(huán)境中，網(wǎng)絡(luò)帶寬是一個(gè)瓶頸。為有效減少數(shù)據(jù)發(fā)送量且不明顯降低虛擬顯示效果，將興趣作為劃分仿真實(shí)體層次的依據(jù)進(jìn)行數(shù)據(jù)過濾。不同層次的實(shí)體賦予不同的優(yōu)先級，以優(yōu)先級輪詢調(diào)度方式組織數(shù)據(jù)更新，實(shí)現(xiàn)以不同的頻率發(fā)送不同層次實(shí)體的數(shù)據(jù)更新。

關(guān)鍵詞：分布式虛擬環(huán)境；興趣層次；優(yōu)先級輪詢調(diào)度

中圖分類號：TP302

興趣在大規(guī)模分布式虛擬環(huán)境中是一種重要的數(shù)據(jù)過濾手段，它利用了每個(gè)仿真實(shí)體只對一定范圍內(nèi)的事物感興趣的特點(diǎn)，對減小網(wǎng)絡(luò)帶寬需求具有重要的作用。何連躍等初步提出了分級興趣管理技術(shù)[1]，建立了基于實(shí)體間距離和實(shí)體類型屬性的簡單興趣分層模型。文獻(xiàn)[2]提出了基于HLA的興趣層次（Layer of Interest，LoI）的概念。Zhou等提出了一種“效用模型”（Utility Model）[3]，對所有仿真實(shí)體都計(jì)算“效用”值，進(jìn)而確定各實(shí)體的重要性及其數(shù)據(jù)更新頻率。對于給定優(yōu)先級的數(shù)據(jù)更新調(diào)度策略，文獻(xiàn)[4]采用了固定優(yōu)先級與固定頻率的簡單調(diào)度方式。

因此本文探討基于興趣分層的數(shù)據(jù)過濾技術(shù)，以及動態(tài)調(diào)度策略。

1 興趣層次模型

興趣層次的劃分一般是根據(jù)與某一實(shí)體的距離或其它屬性來確定其余實(shí)體的重要性。一般來說，興趣與距離負(fù)相關(guān)，即觀察者對其感知范圍內(nèi)的事物比較感興趣，距離越近興趣越高，距離越遠(yuǎn)興趣越低。這種現(xiàn)象在以計(jì)算機(jī)成像為基礎(chǔ)的虛擬環(huán)境中表現(xiàn)得更明顯。

因此，我們以客戶機(jī)用戶視點(diǎn)為中心，把虛擬空間等距離分層，level1、level2直到最后一層levelp，如圖1所示，進(jìn)而可以定義用戶對某一實(shí)體的興趣度DoI（Degree of Interest）。

圖1 仿真實(shí)體按照興趣度分層

在實(shí)際的仿真中，我們注意到某種實(shí)體可能對一種實(shí)體很感興趣，而對別的實(shí)體不感興趣，比如：對地攻擊機(jī)對地面目標(biāo)很感興趣，而對空中其他飛機(jī)不很感興趣。所以，用戶對各種實(shí)體的興趣度也與實(shí)體類型有關(guān)。把所有的實(shí)體分成m類，屬于每個(gè)類別的實(shí)體數(shù)量分別為n1，n2，…，nm，這樣總的實(shí)體個(gè)數(shù) ，每一類與用戶的關(guān)系度為C1，C2，…，Cm，Cj∈[0，1]，j=1，2，...，m。

在單位時(shí)間內(nèi)，運(yùn)動速度快、距離用戶遠(yuǎn)的實(shí)體與距離近、運(yùn)動速度較慢的的實(shí)體，在觀察平面上產(chǎn)生的長度也具有可比性。因此，人們一般對較遠(yuǎn)處、速度快的物體比近處相對較慢的物體較為感興趣。因此可以重新定義興趣度，這里只考慮速度的大小。

定義：任一位于以用戶位置為圓心，半徑為ri（i>1）的圓環(huán)內(nèi)的速度大小為v的屬于Cj類別的實(shí)體，相對于用戶的興趣度為：

DoI=Cir1/ri*v/v1 （1）

其中v1為距離用戶最小半徑r1內(nèi)的實(shí)體的平均速度值，因?yàn)檫@個(gè)速度值可能為零，所以規(guī)定如果小于某個(gè)接近于零的值，按照該實(shí)體一般情況下的平均速度值計(jì)算，比如坦克的平均速度值可以規(guī)定為45千米/小時(shí)。由于v/v1仍然可能很大，因此我們規(guī)定當(dāng)DoI大于1時(shí)，等于1。這樣。DoI∈[0，1]

2 動態(tài)調(diào)度策略

按照關(guān)于用戶的興趣度對仿真實(shí)體分層，對實(shí)體數(shù)據(jù)更新進(jìn)行調(diào)度需要滿足以下幾個(gè)條件：

（1）調(diào)度方法應(yīng)該比較容易實(shí)現(xiàn)，并且每層數(shù)據(jù)都必須能夠更新；

（2）興趣度大的實(shí)體數(shù)據(jù)更新頻率應(yīng)該更快；

（3）分屬各層的實(shí)體數(shù)據(jù)更新頻率應(yīng)該可以根據(jù)調(diào)度策略的變化而變化。

結(jié)合這三條要求，提出了一種輪詢調(diào)度與優(yōu)先級調(diào)度相結(jié)合的方式對實(shí)體更新數(shù)據(jù)進(jìn)行更新。

首先把所有實(shí)體根據(jù)興趣度分層，只取其中的p層，半徑r1內(nèi)的實(shí)體的興趣度最高，規(guī)定為level1，其余各層leveli按照如下公式進(jìn)行計(jì)算：

i=[1/DoI] （2）

由式（1）中的興趣度的定義及式（2）可以發(fā)現(xiàn)，興趣度實(shí)際上是以與用戶的距離為基本依據(jù)對仿真實(shí)體分層，興趣度大的給予高優(yōu)先級，小的給予低優(yōu)先級，而實(shí)體的類型與速度使得實(shí)體的優(yōu)先級大小會有所調(diào)整。所有p層覆蓋的總范圍與距離用戶最小半徑r1正相關(guān)。

圖2 優(yōu)先級輪詢調(diào)度

由于距離用戶最近的一層是用戶興趣度最高的、最敏感的數(shù)據(jù)，因此需要最高的數(shù)據(jù)更新頻率，設(shè)為f，因此這些數(shù)據(jù)每一幀都發(fā)送。根據(jù)（2）式，規(guī)定i層實(shí)體的更新頻率為f/i，i=1，2，…，p。

根據(jù)上述分析，如圖2，結(jié)合優(yōu)先級的輪詢調(diào)度方法具體實(shí)現(xiàn)方式為：

（1）把每層實(shí)體給予相應(yīng)的優(yōu)先級，按照優(yōu)先級調(diào)度方式，優(yōu)先級高的實(shí)體層次給予高更新頻率；

（2）i層實(shí)體平均分成i組，i=1，2，…，p，數(shù)量不足則分成盡量多的組；不能分成整數(shù)組的，最后一組數(shù)量可以少于其它分組；

（3）按照輪詢調(diào)度方式，從每一層依次取出一組，組成一幀數(shù)據(jù)；每層取到最后一組之后再從第一組開始；

（4）選出的數(shù)據(jù)作為這一幀的數(shù)據(jù)在幀時(shí)間段內(nèi)發(fā)送完畢。

從圖2中以及實(shí)現(xiàn)方式可以看出，只要控制了每層實(shí)體所分的組數(shù)，即可控制數(shù)據(jù)更新頻率，進(jìn)而可以控制每幀的數(shù)據(jù)量。因而可以根據(jù)每幀的更新頻率控制帶寬。由于每個(gè)實(shí)體的更新數(shù)據(jù)所占字節(jié)數(shù)相差不多，并且每層的實(shí)體數(shù)都平均分成i組，每幀在每一層都取出一組實(shí)體，這樣每幀數(shù)據(jù)量相差不大，所占帶寬基本穩(wěn)定。

3 結(jié)束語

本文從虛擬現(xiàn)實(shí)場景中透視投影的角度分析了影響興趣度的幾種因素，建立了興趣度的數(shù)學(xué)模型，對場景中的實(shí)體劃分層次，進(jìn)而在此理論基礎(chǔ)上確定了各層次數(shù)據(jù)更新發(fā)送頻率，結(jié)合基于優(yōu)先級的輪詢調(diào)度方式，在較少影響視覺效果的基礎(chǔ)上盡可能解決網(wǎng)絡(luò)擁塞。

參考文獻(xiàn)：

[1]何連躍，李思昆，曾亮.大規(guī)模分布虛擬環(huán)境的分級興趣管理[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2000，12（09）：711-714.

[2]Zhou Zhong，Zhao Qinping，Extend HLA with Layered Priority， in Proc. of the Spring Simulation Interoperability Workshop.2003：Orlando. p. 11.

[3]Zhou Suiping.，et al.，A utility model for timely state update in distributed wargame simulations， in Parallel and Distributed Simulation， 2004.PADS 2004. 18th Workshop on.2004. p.105-111.

[4]Chow， Y.， R. Pose and M. Regan， A Priority Updating Communications Model for Networked Virtual Environments. IADIS International Journal on Computer Science and Information Systems，2006.1（1）：p. 1-14.

作者簡介：曹坤（1980-），女，講師，主要研究方向：分布式仿真，數(shù)據(jù)挖掘；劉述田，男，講師；武書閣，男，副教授。

作者單位：大連工人大學(xué) 計(jì)算機(jī)系，遼寧大連 116011；海軍航空兵學(xué)院 飛行理論系，遼寧葫蘆島 125001