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

范 辰

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

0 引言

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

正因為上述傳統(tǒng)預(yù)下載機制缺陷的存在，同時認識到P2P-DVE 中的預(yù)下載機制應(yīng)該利用P2P 網(wǎng)絡(luò)的特性，本文提出了一種全新的預(yù)下載方法。

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

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

正是基于以上考慮，本文認為在P2P-DVE 中預(yù)下載也應(yīng)該體現(xiàn)P2P“分享”的概念。P2P-DVE 系統(tǒng)中的節(jié)點進行預(yù)下載時，除考慮化身自身未來可能的運動趨勢外，也需要考慮周圍鄰居化身需要的FPVS。如此，基于P2P-DVE 系統(tǒng)的預(yù)下載機制的設(shè)計應(yīng)運而生。

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

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

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

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

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

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

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

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

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

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

若某一場景只有自身需要，那對該場景只需要計算“視覺關(guān)注度”即可；若某一場景只有周圍鄰居節(jié)點需要，那對該場景只需要計算“熱度”即可；若某一場景自身及鄰居都需要，那進行優(yōu)先級計算時既需要考慮“視覺關(guān)注度”，也需要考慮“熱度”。

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

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

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

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

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

3 實驗及結(jié)果

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

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

圖4.1 場景下載節(jié)點命中率折線圖

4 結(jié)論

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

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

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

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

[3]朱軍，龔建華，張建欽，吳嫻.“基于對等網(wǎng)絡(luò)結(jié)構(gòu)的分布式大規(guī)模地形實時漫游研究”.地理與地理信息科學(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/.