范 辰

同濟(jì)大學(xué)軟件學(xué)院，上海 200092

0 引言

傳統(tǒng)虛擬現(xiàn)實(shí)系統(tǒng)都局限在本地使用，隨著互聯(lián)網(wǎng)發(fā)展分布式虛擬環(huán)境(Distributed Virtual Environments,DVE)[1]應(yīng)運(yùn)而生并得到廣泛使用，而隨著場(chǎng)景數(shù)據(jù)量不斷增大，C/S模式中服務(wù)器成為了系統(tǒng)的“瓶頸”，因此P2P 在DVE 中的優(yōu)勢(shì)逐漸受到研究人員的重視[3]。

此外受限于視野范圍，化身在DVE 中只能觀(guān)察到局部場(chǎng)景，這就是用戶(hù)的當(dāng)前潛在可視場(chǎng)景集(CPVS,Current Potential Visible Scenes)；而用戶(hù)未來(lái)可能需要的場(chǎng)景就是未來(lái)潛在可視場(chǎng)景集(FPVS,Future Potential Visible Scenes)[2]。因此當(dāng)用戶(hù)已經(jīng)下載完CPVS 時(shí)，可通過(guò)預(yù)先判斷并預(yù)下載FPVS 使用戶(hù)的瀏覽體驗(yàn)變得更為順暢[2]。

本文提出了適合P2P-DVE 的預(yù)下載方法，將化身和鄰居的FPVS 都考慮在內(nèi)并進(jìn)行預(yù)下載。

1 相關(guān)工作

DVE 中節(jié)點(diǎn)在CPVS 已下載后可提前下載FPVS，這樣當(dāng)視點(diǎn)移動(dòng)到下一位置時(shí)CPVS 就有可能已被下載了。傳統(tǒng)預(yù)下載策略分為基于歷史運(yùn)動(dòng)軌跡和基于領(lǐng)域擴(kuò)張的預(yù)下載[2]。

基于歷史運(yùn)動(dòng)軌跡的預(yù)下載主要有算術(shù)平均法、窗口法以及指數(shù)加權(quán)平移平均法、MLM 法。文獻(xiàn)[5]介紹了算術(shù)平均法和窗口法，它們都只是簡(jiǎn)單計(jì)算歷史向量的算術(shù)平均值，同時(shí)該文還提出了指數(shù)加權(quán)平移平均法EWMA，考慮了不同時(shí)刻的平移向量對(duì)預(yù)測(cè)的影響。文獻(xiàn)[9]提到MLM 預(yù)下載方法，假設(shè)只通過(guò)鼠標(biāo)來(lái)控制并通過(guò)預(yù)測(cè)鼠標(biāo)位置來(lái)間接預(yù)測(cè)化身位置。

基于領(lǐng)域擴(kuò)張的預(yù)下載主要有SNP 和PBNP 算法。文獻(xiàn)[6]提出了SNP 法，通過(guò)預(yù)下載節(jié)點(diǎn)周?chē)膯卧駚?lái)實(shí)現(xiàn)預(yù)下載，其簡(jiǎn)單易實(shí)現(xiàn)但當(dāng)節(jié)點(diǎn)在幾個(gè)單元格間快速來(lái)回平移則會(huì)降低性能，因此[7]提出了改進(jìn)算法PBNP，在更小范圍內(nèi)預(yù)下載，雖然效率更高但原理與SNP 一樣，仍會(huì)一定程度地影響性能。

綜上所述，現(xiàn)有DVE 預(yù)下載機(jī)制均基于集中式DVE，只考慮自身的運(yùn)動(dòng)軌跡或趨勢(shì)。但P2P-DVE 在預(yù)下載時(shí)還應(yīng)考慮鄰居的FPVS，因此要設(shè)計(jì)一種將自身和鄰居需求都考慮在內(nèi)的方法，綜合計(jì)算自身和鄰居的FPVS。

2 基于P2P-DVE 的預(yù)下載機(jī)制

2.1 P2P-DVE 預(yù)下載的基本思想

正因?yàn)樯鲜鰝鹘y(tǒng)預(yù)下載機(jī)制缺陷的存在，同時(shí)認(rèn)識(shí)到P2P-DVE 中的預(yù)下載機(jī)制應(yīng)該利用P2P 網(wǎng)絡(luò)的特性，本文提出了一種全新的預(yù)下載方法。

現(xiàn)有預(yù)下載機(jī)制都是基于集中式DVE 系統(tǒng)設(shè)計(jì)的。在集中式DVE 系統(tǒng)中每個(gè)節(jié)點(diǎn)都只與服務(wù)器建立聯(lián)系，不會(huì)與其它節(jié)點(diǎn)進(jìn)行通信。因此在這種系統(tǒng)中，所有節(jié)點(diǎn)都只需向服務(wù)器請(qǐng)求下載自己當(dāng)前需要的數(shù)據(jù)，在網(wǎng)絡(luò)空閑時(shí)再下載未來(lái)可能需要的數(shù)據(jù)即可，因此也僅需要“自私”地計(jì)算自身未來(lái)的運(yùn)動(dòng)趨勢(shì)就能達(dá)到預(yù)下載的要求。

但在P2P-DVE 中的情況完全不同。成熟的P2P-DVE 系統(tǒng)需要盡可能弱化服務(wù)器在場(chǎng)景部署中的作用，DVE 系統(tǒng)中的任意兩個(gè)節(jié)點(diǎn)都能建立聯(lián)系，每一個(gè)節(jié)點(diǎn)都能從任一節(jié)點(diǎn)處下載場(chǎng)景數(shù)據(jù)或者向任一節(jié)點(diǎn)提供場(chǎng)景數(shù)據(jù)。在P2P-DVE 系統(tǒng)中體現(xiàn)的是“分享”的思想。

正是基于以上考慮，本文認(rèn)為在P2P-DVE 中預(yù)下載也應(yīng)該體現(xiàn)P2P“分享”的概念。P2P-DVE 系統(tǒng)中的節(jié)點(diǎn)進(jìn)行預(yù)下載時(shí)，除考慮化身自身未來(lái)可能的運(yùn)動(dòng)趨勢(shì)外，也需要考慮周?chē)従踊硇枰腇PVS。如此，基于P2P-DVE 系統(tǒng)的預(yù)下載機(jī)制的設(shè)計(jì)應(yīng)運(yùn)而生。

2.2 P2P-DVE 預(yù)下載算法的設(shè)計(jì)

2.2.1 預(yù)下載區(qū)域(AOP)

預(yù)下載時(shí)AOI 內(nèi)數(shù)據(jù)（即CPVS）已獲取完畢，需要關(guān)注的是比AOI 更大范圍的場(chǎng)景，因此本文在A(yíng)OI 外圍定義了另一個(gè)圓，叫預(yù)下載區(qū)域(AOP,Area of Prefetching)，是以化身位置為圓心，R 為半徑的圓，其中r ＜ R，r 為AOI 半徑。

2.2.2 視覺(jué)關(guān)注度及熱度的計(jì)算方法

視覺(jué)關(guān)注度代表了物體對(duì)于節(jié)點(diǎn)的視覺(jué)重要度。設(shè)物體為Oi，Oi 到化身視點(diǎn)距離為Di，Oi 偏離視線(xiàn)角度設(shè)為Ai，化身AOP 的半徑為RAOP，這樣就可得到計(jì)算視覺(jué)關(guān)注度V(Oi)的公式[4]：

λ表示在視覺(jué)關(guān)注度中物體距離視點(diǎn)距離因素占的比例，(1-)λ表示在視覺(jué)關(guān)注度中物體偏離視線(xiàn)角度的因素所占比例，總結(jié)來(lái)說(shuō)λ決定了視覺(jué)關(guān)注度中距離和角度各占的比例。從公式 3-1 可以看出，一個(gè)物體離視點(diǎn)越近、偏離視線(xiàn)的角度越小，那么該物體對(duì)節(jié)點(diǎn)化身的視覺(jué)感官更重要，相對(duì)該視點(diǎn)來(lái)說(shuō)視覺(jué)關(guān)注度也就越高。

如前所述，在P2P-DVE 中，需要時(shí)刻體現(xiàn)“分享”的概念，所以在進(jìn)行預(yù)下載時(shí)，也要將其他節(jié)點(diǎn)需要的FPVS 場(chǎng)景集考慮在預(yù)下載列表內(nèi)。但當(dāng)需要請(qǐng)求的物體過(guò)多時(shí)，若請(qǐng)求順序失當(dāng)，就會(huì)產(chǎn)生化身本身的瀏覽體驗(yàn)不流暢以及無(wú)法顧及其他節(jié)點(diǎn)的需求等等問(wèn)題。因此，本文引入熱度的概念：在一定空間范圍內(nèi)的所有資源請(qǐng)求者，對(duì)于某一資源實(shí)體需求的總數(shù)。

假設(shè)在一定空間范圍S 內(nèi)有m 個(gè)化身，分別為A1，A2，…，Am(m ≥1)，對(duì)于某一物體Oi，假設(shè)需要物體Oi 的節(jié)點(diǎn)有j 個(gè)，分別為Op1，Op2，…，Opj(j ≤m)，則物體Oi 在S 內(nèi)的熱度為：

在當(dāng)前的預(yù)下載問(wèn)題中，某個(gè)物體的熱度就是指在一定空間范圍內(nèi)需要該物體的用戶(hù)個(gè)數(shù)。

2.2.3 確定預(yù)下載優(yōu)先級(jí)

若某一場(chǎng)景只有自身需要，那對(duì)該場(chǎng)景只需要計(jì)算“視覺(jué)關(guān)注度”即可；若某一場(chǎng)景只有周?chē)従庸?jié)點(diǎn)需要，那對(duì)該場(chǎng)景只需要計(jì)算“熱度”即可；若某一場(chǎng)景自身及鄰居都需要，那進(jìn)行優(yōu)先級(jí)計(jì)算時(shí)既需要考慮“視覺(jué)關(guān)注度”，也需要考慮“熱度”。

由于在整個(gè)場(chǎng)景預(yù)下載列表中，較重要的應(yīng)該被優(yōu)先下載，而較次要的則應(yīng)該被適當(dāng)延后下載，所以當(dāng)計(jì)算出各個(gè)場(chǎng)景的“視覺(jué)關(guān)注度”和“熱度”后，需要根據(jù)重要程度進(jìn)行優(yōu)先級(jí)排名。簡(jiǎn)單來(lái)說(shuō)，在整個(gè)預(yù)下載列表中“視覺(jué)關(guān)注度”越高，“熱度”越高的場(chǎng)景重要性也越高，反之亦然。所以每一個(gè)場(chǎng)景的“視覺(jué)關(guān)注度”或者“熱度”都需要分別除以列表中“視覺(jué)關(guān)注度”或“熱度”的最大值進(jìn)行歸一化，再依次進(jìn)行排名。

假設(shè)“視覺(jué)關(guān)注度”列表中最大的值為Vmax，“熱度”列表中最大的值為Hmax。則某一物體Oi 的“視覺(jué)關(guān)注度”和“熱度”系數(shù)分別為：

所以將公式 3-3 和公式 3-4 代入，就可以得到對(duì)于物體Oi 的優(yōu)先級(jí)排名的計(jì)算公式為：

其中，α為“視覺(jué)關(guān)注度”在優(yōu)先級(jí)計(jì)算公式中占的比例，(1-α)為“熱度”在優(yōu)先級(jí)計(jì)算公式中占的比例。若某物體Oi 只被預(yù)下載的節(jié)點(diǎn)自身所關(guān)注則α=1，若只被周?chē)従庸?jié)點(diǎn)所關(guān)注則α=0，否則為0.5。

從公式 3-5 可知，物體Oi 的“視覺(jué)關(guān)注度”和“熱度”越高，那優(yōu)先級(jí)也越高。

3 實(shí)驗(yàn)及結(jié)果

本文設(shè)計(jì)的P2P-DVE 預(yù)下載機(jī)制是在開(kāi)源仿真平臺(tái)FLoD[8][11]中實(shí)現(xiàn)運(yùn)行。原始FLoD 未實(shí)現(xiàn)預(yù)下載，因此本文的預(yù)下載是針對(duì)FLoD 進(jìn)行對(duì)比測(cè)試的。

圖4.1 為下載場(chǎng)景的節(jié)點(diǎn)命中率，可看出P2P-DVE 的預(yù)下載機(jī)制有效幫助系統(tǒng)提高了數(shù)據(jù)請(qǐng)求命中率，提升了系統(tǒng)的整體性能。

圖4.1 場(chǎng)景下載節(jié)點(diǎn)命中率折線(xiàn)圖

4 結(jié)論

本文提出了基于P2P-DVE 的預(yù)下載機(jī)制，將自身和鄰居需求都考慮在內(nèi)，實(shí)驗(yàn)結(jié)果也表明該機(jī)制提高了命中率，提升了系統(tǒng)性能。

限于時(shí)間與能力，本文設(shè)計(jì)的算法還未將P2P 優(yōu)勢(shì)完全發(fā)掘，還應(yīng)將物體的模型復(fù)用度[10]考慮在內(nèi)進(jìn)一步提高傳輸效率。

[1]潘志庚，姜曉紅，張明敏，等.“分布式虛擬環(huán)境綜述”.軟件學(xué)報(bào)，2000，4，11：461-467.

[2]王偉，賈金原，張晨曦，江崟.“大規(guī)模虛擬場(chǎng)景漸進(jìn)式傳輸?shù)难芯窟M(jìn)展”.計(jì)算機(jī)科學(xué)，2010，37，2 (2010)：38-43.

[3]朱軍，龔建華，張建欽，吳嫻.“基于對(duì)等網(wǎng)絡(luò)結(jié)構(gòu)的分布式大規(guī)模地形實(shí)時(shí)漫游研究”.地理與地理信息科學(xué)，2006，22，1：40-43.

[4]Wang,W.,Jia,J.-Y.,Yu,Y.,and Hu,S.-Y.“Progressive Cache Replacement for Massive Peer-to-Peer WebVR Worlds”.In Proc.of Annu.Workshop Netw.Syst.Support Games,NetGames(2010).

[5]Chim,J.,Lau,R.W.H.,Leong,V.,et.al.“CyberWalk:a web-based distributed virtual walkthrough environment”.IEEE Transactions on Multimedia 5，4(2003)，503-515.

[6]Koltun，V.，Chrysanthou，Y.，and Cohen-Or Dl.“Hardware-accelerated from-region visibility using a dual ray space”.In Proc.of EGWR’01 (2001)，204-214.

[7]Zheng,Z.，Chan，T.K.Y.“Optimized neighbor prefetch and Cache for client-server based walkthrough”.In Proc.of Cyberworlds’03 (2003)，143-150.

[8]Hu，S.Y.，Huang,T.H.，Chang,S.C.，Sung,W.L.,Jiang，J.R.，and Chen，B.Y.“FLoD:A Framework for Peer-to-Peer 3D Streaming”.In Proc.of IEEE INFOCOM(2008),2047-2055.

[9]Li，T.Y.，Hsu，W.H.“A data management scheme for effective walkthrough in large-scale virtual environments”.Visual Computer 20,10 (2004),626-634.

[10]Wen L，Jia J，Gao Y.Lightweight Web3D modeling by finding and reusing repeated components[C]//Proceedings of the 10th International Conference on Virtual Reality[10]Continuum and Its Applications in Industry.ACM，2011:533-540.

[11]http://ascend.sourceforge.net/.