基于P2P-DVE的預下載機制

范 辰

同濟大學軟件學院，上海 200092

0 引言

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

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

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

1 相關工作

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

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

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

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

2 基于P2P-DVE 的預下載機制

2.1 P2P-DVE 預下載的基本思想

正因為上述傳統預下載機制缺陷的存在，同時認識到P2P-DVE 中的預下載機制應該利用P2P 網絡的特性，本文提出了一種全新的預下載方法。

現有預下載機制都是基于集中式DVE 系統設計的。在集中式DVE 系統中每個節點都只與服務器建立聯系，不會與其它節點進行通信。因此在這種系統中，所有節點都只需向服務器請求下載自己當前需要的數據，在網絡空閑時再下載未來可能需要的數據即可，因此也僅需要“自私”地計算自身未來的運動趨勢就能達到預下載的要求。

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

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

2.2 P2P-DVE 預下載算法的設計

2.2.1 預下載區域(AOP)

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

2.2.2 視覺關注度及熱度的計算方法

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

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

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

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

在當前的預下載問題中，某個物體的熱度就是指在一定空間范圍內需要該物體的用戶個數。

2.2.3 確定預下載優先級

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

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

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

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

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

從公式 3-5 可知，物體Oi 的“視覺關注度”和“熱度”越高，那優先級也越高。

3 實驗及結果

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

圖4.1 為下載場景的節點命中率，可看出P2P-DVE 的預下載機制有效幫助系統提高了數據請求命中率，提升了系統的整體性能。

圖4.1 場景下載節點命中率折線圖

4 結論

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

限于時間與能力，本文設計的算法還未將P2P 優勢完全發掘，還應將物體的模型復用度[10]考慮在內進一步提高傳輸效率。

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

[2]王偉，賈金原，張晨曦，江崟.“大規模虛擬場景漸進式傳輸的研究進展”.計算機科學，2010，37，2 (2010)：38-43.

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