基于虛擬服務(wù)的信息共享

基于虛擬服務(wù)的信息共享

1覆蓋節(jié)點(diǎn)的放置問(wèn)題覆蓋技術(shù)是一種沒(méi)有必要修改基本網(wǎng)絡(luò)的協(xié)議來(lái)支持新服務(wù)的有效方法。例如，qpm和mbone根據(jù)現(xiàn)有的internet基礎(chǔ)提供可靠的服務(wù)（qos）和集群傳輸（multiple）服務(wù)，這是一種沒(méi)有內(nèi)部劃分的有效方法。然而,為了在通用OSN上支持用戶對(duì)多樣服務(wù)的需求,首先需要研究根據(jù)什么樣的策略在基礎(chǔ)網(wǎng)絡(luò)層選擇合適的節(jié)點(diǎn)構(gòu)造覆蓋層,可以稱之為覆蓋節(jié)點(diǎn)的放置問(wèn)題(OverlayNodesPlacementProblems,ONPP),現(xiàn)有的研究文獻(xiàn)大都采取了“假定覆蓋節(jié)點(diǎn)都已經(jīng)由第3方按照一定的策略放置”在基礎(chǔ)網(wǎng)絡(luò)層之上,而沒(méi)有對(duì)ONPP問(wèn)題做進(jìn)一步的深入研究;為此,本文提出并展開(kāi)了對(duì)ONPP問(wèn)題的研究2節(jié)點(diǎn)放置位置覆蓋節(jié)點(diǎn)的放置問(wèn)題可以看作是一個(gè)選址問(wèn)題,即覆蓋節(jié)點(diǎn)應(yīng)該放置在基礎(chǔ)網(wǎng)絡(luò)層的哪些物理節(jié)點(diǎn)之上,才能使基礎(chǔ)網(wǎng)絡(luò)層的所有節(jié)點(diǎn)到離它們各自“最近”的覆蓋節(jié)點(diǎn)獲取所需服務(wù)的代價(jià)之和盡可能小,同時(shí)要考慮放置這些覆蓋節(jié)點(diǎn)的成本和每個(gè)覆蓋節(jié)點(diǎn)所能承受的負(fù)載。選取覆蓋節(jié)點(diǎn)的放置位置時(shí),需要考慮以下問(wèn)題:(1)放置覆蓋節(jié)點(diǎn)的建設(shè)代價(jià)和該節(jié)點(diǎn)承擔(dān)服務(wù)時(shí)的代價(jià);(2)每個(gè)覆蓋節(jié)點(diǎn)的負(fù)載能力;首先,我們給出Overlay網(wǎng)絡(luò)的基礎(chǔ)網(wǎng)絡(luò)層的形式化表示——帶權(quán)無(wú)向圖G=(V,E),V是基礎(chǔ)網(wǎng)絡(luò)層中節(jié)點(diǎn)的集合,E是物理鏈路集合(也稱為邊)。并設(shè):e:V×V→(,0∞),e(i,j)=e(j,i)為邊權(quán),可解釋為延遲、通信代價(jià)等;F?V為可以放置覆蓋節(jié)點(diǎn)的潛在集合,引入F是由于受基礎(chǔ)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)等因素的限制,使V中的某些節(jié)點(diǎn)不可能放置覆蓋節(jié)點(diǎn);c:F→(,0∞)表示放置覆蓋節(jié)點(diǎn)到F中某個(gè)節(jié)點(diǎn)時(shí)的代價(jià)(包括建設(shè)代價(jià)和該節(jié)點(diǎn)承擔(dān)服務(wù)時(shí)的服務(wù)代價(jià));u:F→Z于是,ONPP問(wèn)題可定義為如下的0-1規(guī)劃模型:其中,x給定模型(1)的一個(gè)解,覆蓋節(jié)點(diǎn)的放置策略可解釋如下:文獻(xiàn)3pp問(wèn)題的解決3.1基于系統(tǒng)道德策略的培養(yǎng)貪婪算法是基于當(dāng)前所得的信息,在每一步所選取的決策總是試圖使當(dāng)前的解得到最大的改進(jìn),或使相應(yīng)的目標(biāo)函數(shù)值盡可能地增大或減小。這里設(shè)計(jì)了求解ONPP問(wèn)題的貪婪算法,在集合F中選擇合適的節(jié)點(diǎn)構(gòu)造為主動(dòng)節(jié)點(diǎn)。第1步評(píng)價(jià)集合F中每一個(gè)潛在的位置,計(jì)算集合F中的每個(gè)元素對(duì)集合V-F中的每個(gè)節(jié)點(diǎn)服務(wù)的代價(jià),選擇代價(jià)最小的節(jié)點(diǎn)為第1個(gè)節(jié)點(diǎn)i。假設(shè)節(jié)點(diǎn)i的負(fù)載能力為u第2步在集合F中尋找與i相連的代價(jià)最小的節(jié)點(diǎn)j,將j選擇為第2個(gè)節(jié)點(diǎn),把與j相連的集合V中未分派的代價(jià)最小的u重復(fù)第2步,直到集合V-F中的節(jié)點(diǎn)都分派給了集合F中的節(jié)點(diǎn)。3.2隨機(jī)算法在F集合中隨機(jī)地選擇一個(gè)節(jié)點(diǎn)i為主動(dòng)節(jié)點(diǎn),在滿足負(fù)載能力u3.3松弛因子選擇問(wèn)題的迭代求解Lagrangian松弛方法的基本原理是,將造成問(wèn)題求解困難的約束吸收到目標(biāo)函數(shù)中,從而可以使用無(wú)約束規(guī)劃的一些經(jīng)典方法來(lái)求解,經(jīng)過(guò)適當(dāng)?shù)乃沙诩夹g(shù),往往可以將原優(yōu)化問(wèn)題轉(zhuǎn)化為對(duì)松弛因子的選擇問(wèn)題。后者可以用一些迭代方法求解,從而使原問(wèn)題的求解難度降低。Lagrangian松弛方法吸收約束到目標(biāo)函數(shù)后,原問(wèn)題的模型變?yōu)槠渲?(1)任選一個(gè)初始Lagrangian乘子矩陣tA=[λt,γt],t=0,矩陣的維數(shù)為|V|×2。(2)目標(biāo)函數(shù)對(duì)A采用以下方法來(lái)選擇C選擇CLagrangian松弛法是求問(wèn)題下界的一種方法,每個(gè)確定的Lagrangian乘子矩陣第1步置p=0,Lagrangian乘子初始值第2步如果θ第3步更新Lagrangian乘子第4步每條邊的費(fèi)用變?yōu)閑(i,j)+λ3.4實(shí)驗(yàn)網(wǎng)絡(luò)模型為了驗(yàn)證網(wǎng)絡(luò)仿真結(jié)果的有效性,使用了BRITE工具生成網(wǎng)絡(luò)的拓?fù)鋱D,使用隨機(jī)化的方法產(chǎn)生具有實(shí)際網(wǎng)絡(luò)特性的圖的模型,實(shí)驗(yàn)網(wǎng)絡(luò)的拓?fù)渖苫赪axman的拓?fù)渖伤惴ㄆ渲?p在本實(shí)驗(yàn)中,網(wǎng)絡(luò)有如下屬性:(1)邊的費(fèi)用在[10,200]上均勻分布。(2)主動(dòng)節(jié)點(diǎn)相關(guān)的費(fèi)用在4基于心問(wèn)題的覆蓋節(jié)點(diǎn)放置問(wèn)題覆蓋服務(wù)網(wǎng)絡(luò)(OSN)為支持新型服務(wù)提供了一種有效的方式。圍繞OSN的拓?fù)浣Y(jié)構(gòu)這一核心問(wèn)題,研究了覆蓋節(jié)點(diǎn)的放置策略或選擇問(wèn)題。本文分析了目前人們對(duì)于覆蓋網(wǎng)