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

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

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