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

范 辰

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

0 引言

隨著虛擬場(chǎng)景數(shù)據(jù)量不斷增大，C/S-DVE 中服務(wù)器成為了“瓶頸”，因此P2P 在DVE 中的優(yōu)勢(shì)逐漸受到人們的重視。此外受限于視野范圍，化身在DVE 中只能觀察到局部場(chǎng)景，這就是用戶的當(dāng)前潛在可視場(chǎng)景集(CPVS, Current Potential Visible Scenes)；而用戶未來(lái)可能需要的場(chǎng)景就是未來(lái)潛在可視場(chǎng)景集(FPVS, Future Potential Visible Scenes)[1]。當(dāng)用戶已下載完CPVS 時(shí)，可通過預(yù)先判斷并預(yù)下載FPVS 使用戶的瀏覽體驗(yàn)更為順暢[1]。本文提出了適合P2P-DVE 的預(yù)下載方法，將化身和鄰居FPVS 都考慮在內(nèi)進(jìn)行預(yù)下載。

1 相關(guān)工作

傳統(tǒng)預(yù)下載策略分為基于歷史運(yùn)動(dòng)軌跡和基于領(lǐng)域擴(kuò)張的預(yù)下載[1]。

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

基于領(lǐng)域擴(kuò)張的預(yù)下載主要有SNP 和PBNP 算法。文獻(xiàn)[4]的SNP 通過預(yù)下載節(jié)點(diǎn)周圍的單元格來(lái)實(shí)現(xiàn)預(yù)下載，簡(jiǎn)單易實(shí)現(xiàn)但當(dāng)節(jié)點(diǎn)在幾個(gè)單元格間快速來(lái)回平移會(huì)降低性能，因此[5]提出了改進(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，要將自身和鄰居需求都考慮在內(nèi)，綜合計(jì)算自身和鄰居FPVS。

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

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

P2P-DVE 中任意兩點(diǎn)都能建立聯(lián)系，每一節(jié)點(diǎn)都可從任一節(jié)點(diǎn)處下載數(shù)據(jù)或向任一節(jié)點(diǎn)提供數(shù)據(jù)。因此本文認(rèn)為P2PDVE 預(yù)下載時(shí)應(yīng)：將自身及鄰居的FPVS 都考慮在內(nèi)。

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)景，因此本文在AOI 外圍定義了另一個(gè)圓，叫預(yù)下載區(qū)域(AOP, Area of Prefetching)，是以化身位置為圓心，R 為半徑的圓，其中r ＜ R，r 為AOI 半徑。

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

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

λ 表示在視覺關(guān)注度中物體距離視點(diǎn)距離因素占的比例，( )λ?1 則表示物體偏離視線角度所占比例。

如前所述，P2P-DVE 預(yù)下載時(shí)需將鄰居FPVS 考慮在內(nèi)。當(dāng)請(qǐng)求物體過多且順序失當(dāng)時(shí)，會(huì)使節(jié)點(diǎn)本身瀏覽不流暢且無(wú)法顧及其他節(jié)點(diǎn)。因此本文引入熱度的概念：在一定范圍內(nèi)對(duì)某一資源實(shí)體需求的總數(shù)。

假設(shè)有j 個(gè)節(jié)點(diǎn)需要物體Oi，則物體Oi 的熱度為：

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

若某數(shù)據(jù)只有自身需要，那對(duì)該數(shù)據(jù)只需計(jì)算視覺關(guān)注度V(Oi)即可；若只有鄰居需要那只需計(jì)算熱度H(Oi)；若自身及鄰居都需要，那兩個(gè)因素都要考慮。

由于重要的數(shù)據(jù)應(yīng)被優(yōu)先下載，因此V(Oi)及H(Oi)越高的場(chǎng)景應(yīng)被優(yōu)先下載，反之亦然。同時(shí)為歸一化，每個(gè)物體的V(Oi)和H(Oi)都應(yīng)分別除以它們的最大值后排名。

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

由此可知物體Oi 的優(yōu)先級(jí)排名計(jì)算公式為：

α 為視覺關(guān)注度在優(yōu)先級(jí)計(jì)算公式中占的比例。若Oi 只被節(jié)點(diǎn)自身關(guān)注那 1=α ，若只被鄰居關(guān)注則為0，否則為0.5。

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

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

圖1 場(chǎng)景下載節(jié)點(diǎ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ù)用度考慮在內(nèi)進(jìn)一步提高傳輸效率。

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

[2]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.

[3]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.

[4]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.

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

[6]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.

[7]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.