一種能耗優(yōu)化的云內(nèi)容分發(fā)網(wǎng)絡(luò)

劉玉潔,陸佃杰,張桂娟

1(山東師范大學(xué) 信息科學(xué)與工程學(xué)院,濟(jì)南 250014)

2(山東省分布式計(jì)算機(jī)軟件新技術(shù)重點(diǎn)實(shí)驗(yàn)室,濟(jì)南 250014)

1 引 言

隨著互聯(lián)網(wǎng)的不斷發(fā)展,互聯(lián)網(wǎng)用戶規(guī)模的快速增長(zhǎng),有限的網(wǎng)絡(luò)資源與日益增長(zhǎng)的用戶需求之間的矛盾日益突出.CDN是解決這類(lèi)問(wèn)題的一個(gè)主要途徑.不同于其他的網(wǎng)絡(luò),(如無(wú)線傳感網(wǎng)絡(luò)[1]),CDN通過(guò)在用戶與源服務(wù)器之間部署一層邊緣服務(wù)器,使用戶可以從距離較近的邊緣服務(wù)器獲得所需內(nèi)容,緩解了網(wǎng)絡(luò)擁塞情況,同時(shí)減少了用戶的訪問(wèn)延遲.但是,對(duì)于中小規(guī)模的內(nèi)容提供商來(lái)說(shuō),部署大型服務(wù)器來(lái)提供內(nèi)容分發(fā)服務(wù)在經(jīng)濟(jì)上是不可行的.新興云儲(chǔ)存供應(yīng)商,如亞馬遜S3,能夠?qū)崿F(xiàn)低成本的基于云的內(nèi)容分發(fā)網(wǎng)絡(luò),使中小型內(nèi)容提供商部署內(nèi)容分發(fā)網(wǎng)絡(luò)成為可能.

當(dāng)CCDN中某一服務(wù)器節(jié)點(diǎn)有新內(nèi)容發(fā)布或者有內(nèi)容更新的時(shí)候,該源節(jié)點(diǎn)需要發(fā)起一個(gè)復(fù)制請(qǐng)求,把新內(nèi)容發(fā)布到其他節(jié)點(diǎn)上.對(duì)于這種CCDN內(nèi)容副本放置問(wèn)題,要在保證用戶QoS的同時(shí)最大程度的降低系統(tǒng)的能耗開(kāi)銷(xiāo)被證明是NP難的.對(duì)于內(nèi)容副本放置問(wèn)題,如果源節(jié)點(diǎn)與每個(gè)其他節(jié)點(diǎn)建立一個(gè)單播連接,能耗開(kāi)銷(xiāo)較大且擴(kuò)展性不好.目前大多數(shù)內(nèi)容分發(fā)都采用多播樹(shù)型結(jié)構(gòu),多播樹(shù)型結(jié)構(gòu)具有良好的擴(kuò)展性且有利于降低能耗開(kāi)銷(xiāo).Bauguion Pierre等[2]提出適用于傳統(tǒng)內(nèi)容分發(fā)問(wèn)題的樹(shù)型網(wǎng)絡(luò)構(gòu)建算法,并設(shè)計(jì)出一套根據(jù)副本熱度部分更新的內(nèi)容替換策略,該方法具有良好的擴(kuò)展性.SPIDER[3]假設(shè)Internet核心網(wǎng)絡(luò)中有專(zhuān)門(mén)的高帶寬轉(zhuǎn)發(fā)節(jié)點(diǎn),然后利用這些額外的節(jié)點(diǎn)來(lái)構(gòu)建多個(gè)樹(shù)參與復(fù)制.但是實(shí)際Internet中,部署這些專(zhuān)門(mén)轉(zhuǎn)發(fā)節(jié)點(diǎn)的代價(jià)是很高的.Zaman和Pallis[4,5]等人針對(duì)拓?fù)浣Y(jié)構(gòu)提出啟發(fā)式算法,提出用戶找到最近副本服務(wù)器的一種構(gòu)想,通過(guò)實(shí)驗(yàn)證明了這一算法的可行性.葉雙[6]等人介紹一種應(yīng)用于視頻監(jiān)控系統(tǒng)的混合內(nèi)容分發(fā)網(wǎng)絡(luò),該網(wǎng)絡(luò)既克服了樹(shù)狀拓?fù)浣Y(jié)構(gòu)中節(jié)點(diǎn)動(dòng)態(tài)性帶來(lái)的數(shù)據(jù)傳輸延遲大的缺點(diǎn),又較隨機(jī)拓?fù)浣Y(jié)構(gòu)減少了控制開(kāi)銷(xiāo).Gong[7]等人提出一種基于斯坦納樹(shù)問(wèn)題的多播樹(shù)構(gòu)建方法,使用一種簡(jiǎn)單的分發(fā)模式來(lái)構(gòu)建多播樹(shù),實(shí)現(xiàn)了低成本、低能耗.然而,已有的通過(guò)構(gòu)建樹(shù)型結(jié)構(gòu)向給定目的節(jié)點(diǎn)發(fā)送內(nèi)容的方式不能很好的解決云內(nèi)容分發(fā)網(wǎng)絡(luò)的內(nèi)容副本放置優(yōu)化問(wèn)題.云內(nèi)容分發(fā)網(wǎng)絡(luò)往往擁有大量的的代理云站點(diǎn),如何在眾多站點(diǎn)中找到一個(gè)能耗優(yōu)化的內(nèi)容放置方案同時(shí)滿足整個(gè)網(wǎng)絡(luò)中終端用戶的服務(wù)質(zhì)量是亟待解決的問(wèn)題.

本文提出一種基于能耗優(yōu)化的云內(nèi)容分發(fā)模型,首先通過(guò)關(guān)鍵節(jié)點(diǎn)選取,使副本分發(fā)盡可能覆蓋整個(gè)網(wǎng)絡(luò).然后通過(guò)最小化分發(fā)代價(jià)的副本放置多播路由選擇算法構(gòu)建連接所有關(guān)鍵節(jié)點(diǎn)的分發(fā)樹(shù),以此來(lái)減少數(shù)據(jù)分發(fā)的路徑長(zhǎng)度.當(dāng)用戶請(qǐng)求數(shù)據(jù)內(nèi)容時(shí),可以就近選擇存儲(chǔ)有該內(nèi)容的代理云站點(diǎn)為自己提供服務(wù),而不需向源服務(wù)器發(fā)送數(shù)據(jù)請(qǐng)求,從而從整體上減少了內(nèi)容分發(fā)的路徑長(zhǎng)度,降低了能耗.

下面介紹本文的組織結(jié)構(gòu):第二節(jié)主要描述了相關(guān)工作;第三節(jié)介紹了傳統(tǒng)的CDN模型與CCDN模型,并提出了一種能耗優(yōu)化分發(fā)模型;第四節(jié)展示了關(guān)鍵節(jié)點(diǎn)選取以及分發(fā)樹(shù)構(gòu)建算法;第五節(jié)進(jìn)行了性能分析;第六節(jié)對(duì)本文進(jìn)行總結(jié).

2 相關(guān)工作

為了有效部署CDN中的副本,許多學(xué)者已經(jīng)做了大量的研究,Sahoo[8]以及Kolisch[9]等針對(duì)CDN網(wǎng)絡(luò)中的內(nèi)容部署問(wèn)題提出了最佳解決方案,使檢索成本最小化.意大利都靈理工大學(xué)的Chiaraviglio[10]提出一種通過(guò)動(dòng)態(tài)提供CDN服務(wù)器和網(wǎng)絡(luò)元素的方案,能夠優(yōu)化內(nèi)容供應(yīng)商和互聯(lián)網(wǎng)服務(wù)提供商的能耗.Aram[11]等人研究了城市內(nèi)容分發(fā)網(wǎng)絡(luò)中最優(yōu)副本服務(wù)器部署和內(nèi)容放置問(wèn)題,提出了一種優(yōu)化設(shè)計(jì),使服務(wù)器部署成本最小化.Wendell[12]等人提出了一種可以有效平衡邊緣服務(wù)器之間的負(fù)載的分布式服務(wù)器選擇機(jī)制.胡海洋[13]等人通過(guò)分析面向內(nèi)容分發(fā)完成時(shí)間的兩種優(yōu)化策略,制定了優(yōu)化的內(nèi)容分發(fā)機(jī)制.Alzoubi[14]等人通過(guò)提出負(fù)載感知IP任播CDN架構(gòu),重新評(píng)估CDN的IP任播,該架構(gòu)利用路由控制機(jī)制來(lái)考慮服務(wù)器和網(wǎng)絡(luò)負(fù)載,實(shí)現(xiàn)負(fù)載感知任播.然而以上方法都要求部署大量的邊緣服務(wù)器,成本較高,擴(kuò)展性差,很難推廣應(yīng)用.

隨著云計(jì)算的快速發(fā)展,云存儲(chǔ)提供商提供了快速讀寫(xiě)能力以及低成本的可擴(kuò)展性、可以幫助內(nèi)容提供商應(yīng)對(duì)突然的網(wǎng)絡(luò)帶寬擁擠以及可預(yù)期的增長(zhǎng)需求.從使用成本與性能方面考慮,以現(xiàn)有的“云存儲(chǔ)”結(jié)構(gòu)進(jìn)行CDN 服務(wù)與將大量投資花在建立自己擁有的內(nèi)容分發(fā)平臺(tái)或者租用類(lèi)似Akamai這樣的現(xiàn)有CDN相比是十分劃算的.文獻(xiàn)[15]提出了一種基于云的優(yōu)化的視頻分發(fā)服務(wù)部署方案,并深入研究了運(yùn)營(yíng)開(kāi)銷(xiāo)以及用戶體驗(yàn)之間權(quán)衡問(wèn)題.Salahuddin等[16]和Lin等[17],設(shè)計(jì)并實(shí)施了基于云存儲(chǔ)的內(nèi)容分發(fā)框架來(lái)協(xié)助副本放置,以便在多樣化需求下實(shí)現(xiàn)云上的最佳內(nèi)容分發(fā).Zeng等[18]提出了一種基于QoS的貪婪啟發(fā)式算法使云存儲(chǔ)內(nèi)容分發(fā)網(wǎng)絡(luò)的副本放置最優(yōu)化.但是到目前為止,云存儲(chǔ)內(nèi)容分發(fā)網(wǎng)絡(luò)仍然沒(méi)有找到很好的方法使副本放置路徑最優(yōu)且能夠優(yōu)化系統(tǒng)的整體能耗.本文在云分發(fā)網(wǎng)絡(luò)的基礎(chǔ)上建立基于多播的能耗優(yōu)化分發(fā)模型,通過(guò)減少分發(fā)路徑長(zhǎng)度實(shí)現(xiàn)能耗優(yōu)化.

3 網(wǎng)絡(luò)模型

傳統(tǒng)的CDN網(wǎng)絡(luò)架構(gòu)由用戶、源服務(wù)器和邊緣服務(wù)器組成.如圖1所示,源服務(wù)器將數(shù)據(jù)副本發(fā)送給邊緣服務(wù)器,當(dāng)用戶訪問(wèn)數(shù)據(jù)內(nèi)容時(shí),離用戶近的邊緣服務(wù)器優(yōu)先為用戶提供數(shù)據(jù)內(nèi)容.但部署代理服務(wù)器費(fèi)用高,當(dāng)大量用戶同時(shí)訪問(wèn)服務(wù)器時(shí)容易產(chǎn)生網(wǎng)絡(luò)擁塞,并且可擴(kuò)展性差.相反,租用云資源,建立云存儲(chǔ)站點(diǎn),經(jīng)濟(jì)費(fèi)用低,可實(shí)現(xiàn)站點(diǎn)動(dòng)態(tài)部署,并且可以定期的更新資源.

圖1 傳統(tǒng)CDN網(wǎng)絡(luò)架構(gòu)Fig.1 Traditional CDN network architecture

3.1 CCDN的組成框架

CCDN網(wǎng)絡(luò)架構(gòu)由CCDN源服務(wù)器站點(diǎn)以及代理云站點(diǎn)組成.其中,源服務(wù)器站點(diǎn)存儲(chǔ)原始數(shù)據(jù),而代理云站點(diǎn)可以根據(jù)用戶需求動(dòng)態(tài)靈活地部署.本文將代理云站點(diǎn)分為關(guān)鍵云站點(diǎn)和其他云站點(diǎn).關(guān)鍵云站點(diǎn)即分發(fā)的目的站點(diǎn),接收源站點(diǎn)發(fā)來(lái)的數(shù)據(jù);其他云站點(diǎn)是指代理云站點(diǎn)中除關(guān)鍵云站點(diǎn)以外的其他站點(diǎn),由于其他云站點(diǎn)可作為中繼站點(diǎn)參加到副本分發(fā)的過(guò)程中,因此也稱(chēng)為中繼云站點(diǎn).如圖2所示,CCDN內(nèi)容運(yùn)營(yíng)商將內(nèi)容放置到源服務(wù)器站點(diǎn),源服務(wù)站點(diǎn)負(fù)責(zé)將數(shù)據(jù)副本發(fā)送到關(guān)鍵云站點(diǎn),而從源服務(wù)器站點(diǎn)到關(guān)鍵云站點(diǎn)的副本放置過(guò)程中,我們?cè)试S中繼云站點(diǎn)的加入以使分發(fā)路徑最優(yōu)從而獲得較低的能耗開(kāi)銷(xiāo).

圖2 CCDN網(wǎng)絡(luò)架構(gòu)Fig.2 CCDN network architecture

3.2 能耗優(yōu)化分發(fā)模型

本文將網(wǎng)絡(luò)中的云存儲(chǔ)站點(diǎn)看成節(jié)點(diǎn),用R(R1,R2,…,Rn)表示包含網(wǎng)絡(luò)中的所有節(jié)點(diǎn)的集合.在能耗優(yōu)化分發(fā)模型中,文章首先通過(guò)K-Canopy算法確定最優(yōu)關(guān)鍵節(jié)點(diǎn)個(gè)數(shù)k,然后通過(guò)K-Means聚類(lèi)算法將整個(gè)網(wǎng)絡(luò)分成k個(gè)簇,對(duì)于每個(gè)簇選出一個(gè)節(jié)點(diǎn)作為代表這個(gè)簇的關(guān)鍵節(jié)點(diǎn),用集合M(M0,M1,M2,…,Mk)表示所有的關(guān)鍵節(jié)點(diǎn).其中M0為源服務(wù)器節(jié)點(diǎn),M1到Mk為每個(gè)簇中選出的關(guān)鍵節(jié)點(diǎn).

圖3 能耗優(yōu)化分發(fā)模型整體流程圖Fig.3 Overall flow chart of energy efficient delivery model

確定好關(guān)鍵節(jié)點(diǎn)之后,本文根據(jù)最小化分發(fā)代價(jià)的副本放置多播路由選擇算法建立一棵連接所有關(guān)鍵節(jié)點(diǎn)的分發(fā)樹(shù).此過(guò)程中,M0為該分發(fā)樹(shù)的組長(zhǎng)節(jié)點(diǎn),M中每個(gè)簇的關(guān)鍵節(jié)點(diǎn)作為多播成員節(jié)點(diǎn),通過(guò)為每一個(gè)成員節(jié)點(diǎn)建立一條連接到其最近鄰居成員節(jié)點(diǎn)的方式,建立一棵連接所有多播組成員節(jié)點(diǎn)并且允許中繼節(jié)點(diǎn)加入的分發(fā)樹(shù).在實(shí)際副本分發(fā)過(guò)程中,我們只需將原始數(shù)據(jù)副本上傳至多播組組長(zhǎng)節(jié)點(diǎn),由組長(zhǎng)節(jié)點(diǎn)沿著已經(jīng)構(gòu)造好的分發(fā)樹(shù)向網(wǎng)絡(luò)中的所有關(guān)鍵節(jié)點(diǎn)發(fā)送數(shù)據(jù).整個(gè)模型的整體流程圖如圖3所示.

4 算 法

本章將詳細(xì)介紹關(guān)鍵節(jié)點(diǎn)個(gè)數(shù)k確定算法K-Canopy、基于最小距離的關(guān)鍵節(jié)點(diǎn)選擇算法、多播路由選擇算法以及環(huán)路消除算法.如圖4所示,是一棵連接所有多播組成員節(jié)點(diǎn)并且有中繼節(jié)點(diǎn)加入的分發(fā)樹(shù).其中S標(biāo)記的點(diǎn)代表源服務(wù)器節(jié)點(diǎn)M0,數(shù)據(jù)內(nèi)容最初只存放在源服務(wù)器節(jié)點(diǎn)中;較大的點(diǎn)代表多播組成員節(jié)點(diǎn),數(shù)據(jù)內(nèi)容需要分發(fā)給所有的多播組成員節(jié)點(diǎn);其他較小的點(diǎn)代表網(wǎng)路中的其他代理節(jié)點(diǎn),分發(fā)過(guò)程中可作為中繼節(jié)點(diǎn);圖中實(shí)線代表內(nèi)容分發(fā)路徑;虛線代表多余的分發(fā)路徑,如圖5所示,本文通過(guò)刪除該路徑來(lái)消除環(huán)路.

圖4 有環(huán)路的分發(fā)樹(shù)Fig.4 Distribution tree with a loop

圖5 取消環(huán)路后的分發(fā)樹(shù)Fig.5 Distribution tree without loop

4.1 關(guān)鍵節(jié)點(diǎn)選取算法

為了使所選取的節(jié)點(diǎn)能夠盡可能的覆蓋整個(gè)網(wǎng)絡(luò),避免關(guān)鍵節(jié)點(diǎn)分布不均,從而使得當(dāng)有用戶發(fā)送數(shù)據(jù)請(qǐng)求時(shí),可以就近的選擇合適的存儲(chǔ)有該用戶所需數(shù)據(jù)的云站點(diǎn)為用戶提供服務(wù),我們需要計(jì)算出網(wǎng)絡(luò)的最優(yōu)區(qū)域劃分?jǐn)?shù)量,并為每個(gè)區(qū)域找出一個(gè)關(guān)鍵節(jié)點(diǎn)構(gòu)建關(guān)鍵節(jié)點(diǎn)集合M.算法1為關(guān)鍵節(jié)點(diǎn)個(gè)數(shù)k確定算法,算法1設(shè)置了兩個(gè)閾值T1、T2(T1>T2),每次從R中隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為一個(gè)類(lèi)的中心,并將該點(diǎn)從R中移除,計(jì)算R中剩余點(diǎn)到該中心的距離,將距離小于T1的點(diǎn)歸到該類(lèi)中,將距離小于T2的點(diǎn)從R中移除.如此循環(huán),直到R為空,這樣就找到了整個(gè)網(wǎng)絡(luò)最合適的區(qū)域劃分個(gè)數(shù)k.

算法1.關(guān)鍵節(jié)點(diǎn)個(gè)數(shù)k確定算法 K-Canopy

輸入:CCDN網(wǎng)絡(luò)中所有節(jié)點(diǎn)的地理坐標(biāo)集合R

輸出:關(guān)鍵節(jié)點(diǎn)個(gè)數(shù)k

BEGIN

1T2←R中所有點(diǎn)的平均距離,T1←2×T2

2 k←0

3 WHILER不為空

4 k←k+1

5 從R中隨機(jī)選取一個(gè)點(diǎn)r0作為中心,并將r0從R中移除

6 FOR ALL r INR

7 d←r到r0的距離

8 IF d

9 將 r歸到以r0為中心的類(lèi)中,并將r從R中移除

10 ELSE IF d

11 將r歸到以r0為中心的類(lèi)中

12 END IF

13 END FOR

14 END WHILE

END

接下來(lái)通過(guò)K-Means聚類(lèi)算法,將網(wǎng)絡(luò)分成k個(gè)簇,通過(guò)算法2為每一個(gè)簇選取一個(gè)關(guān)鍵節(jié)點(diǎn),并儲(chǔ)存在集合M(M1,M2,…,Mk)中,選取出的關(guān)鍵節(jié)點(diǎn)作為下一步的多播組成員節(jié)點(diǎn),參與數(shù)據(jù)的分發(fā).

算法2中,Ri表示第i個(gè)簇的節(jié)點(diǎn)集合,(x0,y0)表示集合Ri中所有節(jié)點(diǎn)坐標(biāo)的平均值,rj表示集合Ri中的第j個(gè)元素,|Ri|表示集合Ri的元素個(gè)數(shù).算法2選擇離(x0,y0)歐氏距離最近的節(jié)點(diǎn)作為每個(gè)簇的關(guān)鍵節(jié)點(diǎn).

算法2.基于最小距離的關(guān)鍵節(jié)點(diǎn)選擇算法

輸入:CCDN網(wǎng)絡(luò)中所有節(jié)點(diǎn)的地理坐標(biāo)集合R,關(guān)鍵節(jié)點(diǎn)個(gè)數(shù)k

輸出:網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)集合M

BEGIN

1 對(duì)于R中的節(jié)點(diǎn),用嵌入的聚類(lèi)算法將其劃分成k個(gè)簇Ri(1≤i≤k)

2 FOREACHRi

3 (x0,y0)←Ri中所有節(jié)點(diǎn)坐標(biāo)的均值

4d0←∞

5 FOREACHrj(1≤j≤|Ri|) inRi

6dj←rj到(x0,y0)的距離

7 IFdj

8d0←dj

9Mi←rj

10 END IF

11 END FOREACH

參照《國(guó)土資源環(huán)境承載力評(píng)價(jià)技術(shù)要求(試行)》，計(jì)算基礎(chǔ)評(píng)價(jià)系統(tǒng)中各項(xiàng)指標(biāo)及指數(shù)值(表2)。根據(jù)相關(guān)技術(shù)規(guī)定，當(dāng)D1>0時(shí)，建設(shè)開(kāi)發(fā)壓力大，為超載；當(dāng)D1=0時(shí)，建設(shè)開(kāi)發(fā)狀態(tài)為臨界；當(dāng)D1<0時(shí)，建設(shè)開(kāi)發(fā)壓力小，為可載。耕地開(kāi)發(fā)壓力狀態(tài)指數(shù)D2>0時(shí)，耕地開(kāi)發(fā)利用為可載；D2=0時(shí)，耕地開(kāi)發(fā)利用為臨界；D2<0時(shí)，耕地開(kāi)發(fā)利用為超載。

12 END FOREACH

END

4.2 副本放置多播路由選擇算法

開(kāi)始時(shí),副本只存放在組長(zhǎng)節(jié)點(diǎn)M0中,該節(jié)點(diǎn)攜帶其他節(jié)點(diǎn)的位置信息.組長(zhǎng)節(jié)點(diǎn)發(fā)送廣播消息激活多播組中其他的成員節(jié)點(diǎn).接收到該消息的節(jié)點(diǎn)如果是成員節(jié)點(diǎn),則更新自己的多播路由表,將組地址設(shè)置為該多播組的組地址,將多播組組長(zhǎng)地址設(shè)置為該多播組的組長(zhǎng)地址.如果不是成員節(jié)點(diǎn),則繼續(xù)轉(zhuǎn)發(fā)該報(bào)文,直到所有多播組成員節(jié)點(diǎn)都被激活.接下來(lái),連接組長(zhǎng)節(jié)點(diǎn)以及所有的多播組成員節(jié)點(diǎn).

第一步,每個(gè)多播組成員節(jié)點(diǎn)作為發(fā)送節(jié)點(diǎn)廣播RREQ_JOIN請(qǐng)求報(bào)文.RREQ_JOIN報(bào)文格式為.如算法3所示,節(jié)點(diǎn)收到RREQ_JOIN報(bào)文作如下處理:更新path length將跳數(shù)加1,將自身加入節(jié)點(diǎn)序列繼續(xù)轉(zhuǎn)發(fā)該報(bào)文,并檢查自身的多播路由表判斷自身是否是發(fā)送節(jié)點(diǎn)想要加入的多播組的組成員節(jié)點(diǎn).如果收到RREQ_JOIN報(bào)文的節(jié)點(diǎn)是該多播組的成員節(jié)點(diǎn),且自身到源節(jié)點(diǎn)的距離比發(fā)送節(jié)點(diǎn)到源節(jié)點(diǎn)的距離小,則檢查自身是否收到過(guò)相同發(fā)送節(jié)點(diǎn)發(fā)送來(lái)的RREQ_JOIN報(bào)文,如果收到過(guò)該報(bào)文就進(jìn)行擇優(yōu)處理.選擇path length最短和跳數(shù)最小的RREQ_JOIN.節(jié)點(diǎn)擇優(yōu)處理完畢后,進(jìn)入下一步.

第二步,收到RREQ_JOIN報(bào)文的節(jié)點(diǎn)按照RREQ_JOIN報(bào)文所攜帶的反向路由信息向發(fā)送節(jié)點(diǎn)發(fā)送RREP_J報(bào)文.RREP_J報(bào)文格式為.發(fā)送節(jié)點(diǎn)在廣播RREQ_JOIN報(bào)文一段時(shí)間后,等待接收RREP_J報(bào)文.如果接收到的RREP_J報(bào)文數(shù)量大于等于1,則發(fā)送節(jié)點(diǎn)就需要對(duì)路由進(jìn)行擇優(yōu)處理,選擇歐氏距離最短的多播組成員節(jié)點(diǎn)發(fā)送來(lái)的RREP_J報(bào)文.在擇優(yōu)處理過(guò)程中,如果沒(méi)有成員節(jié)點(diǎn)到源節(jié)點(diǎn)的距離比發(fā)送節(jié)點(diǎn)到源節(jié)點(diǎn)的距離小,那么該發(fā)送節(jié)點(diǎn)直接與源節(jié)點(diǎn)建立連接.

擇優(yōu)處理過(guò)程完成后進(jìn)入下一步,由于第二步中發(fā)送節(jié)點(diǎn)通過(guò)擇優(yōu)處理選定了到達(dá)多播組的路徑.第三步發(fā)送節(jié)點(diǎn)則按逆向路由向離自己最近的多播成員節(jié)點(diǎn)發(fā)送MACT_Confirm消息,收到消息的多播成員節(jié)點(diǎn)發(fā)送MACT路由激活信息激活一條從該成員節(jié)點(diǎn)到發(fā)送節(jié)點(diǎn)的路徑.收到MACT信息的鄰居節(jié)點(diǎn)在單播路由表內(nèi)添加一欄信息,Mj1,Mj2表示該對(duì)多播成員節(jié)點(diǎn),PHj,NHj表示該鄰居節(jié)點(diǎn)的上一跳及下一跳.于此同時(shí)將MACT沿路徑發(fā)送給下一跳節(jié)點(diǎn),激活了一條從多播組成員節(jié)點(diǎn)到達(dá)該發(fā)送節(jié)點(diǎn)的路徑.當(dāng)所有多播組成員節(jié)點(diǎn)找到了一條連接到其它成員節(jié)點(diǎn)的路徑,就構(gòu)建了一棵連接所有節(jié)點(diǎn)的分發(fā)樹(shù).

算法3.多播路由選擇算法

BEGIN

2 將自己加入到node sequence

3 HopCount←HopCount+1

4 Dist←當(dāng)前節(jié)點(diǎn)到上一跳節(jié)點(diǎn)的距離

5 Path length←Path length+Dist

6 繼續(xù)轉(zhuǎn)發(fā)RREEQ_JOIN消息

7 IF 是多播組成員節(jié)點(diǎn)

8 NodeSourceDist←當(dāng)前節(jié)點(diǎn)到源節(jié)點(diǎn)距離

9 SenderSourceDist←發(fā)送節(jié)點(diǎn)到源節(jié)點(diǎn)距離

10 IF SenderSourceDist < NodeSourceDist

11 IF u收到過(guò)該發(fā)送節(jié)點(diǎn)發(fā)送來(lái)的信息

12 選擇HopCount最小,Path length最短的一條路徑

發(fā)送RREP_J

13 ELSE

14 沿該消息的反向路由信息向發(fā)送節(jié)點(diǎn)發(fā)送RREP_J

15 END IF

16 END IF

17 END IF

END

在構(gòu)建分發(fā)樹(shù)過(guò)程中,由于有其他中繼節(jié)點(diǎn)的加入,可能導(dǎo)致有環(huán)路產(chǎn)生.如一個(gè)中繼節(jié)點(diǎn)被不同的成員節(jié)點(diǎn)對(duì)共享,這個(gè)中繼節(jié)點(diǎn)則有可能收到多余的消息,也就意味著有環(huán)產(chǎn)生.這一階段檢查是否存在這樣的環(huán),并取消環(huán)路.

算法4描述了如何消除環(huán)路.如果中繼節(jié)點(diǎn)u是k組接收節(jié)點(diǎn)對(duì)的中繼,這些節(jié)點(diǎn)對(duì)表示為(M11,M12),(M21,M22),…,(Mk1,Mk2).假設(shè)Mi1是比Mi2(1≤i≤k)離源節(jié)點(diǎn)更近的多播組成員節(jié)點(diǎn),中繼節(jié)點(diǎn)記錄了從Mi1到Mi2的路徑中它的上一跳和下一跳,分別用PHi和NHi表示,算法4隨機(jī)選擇一組接收節(jié)點(diǎn)對(duì)(Mj1,Mj2),并保持其信息(Mj1,Mj2,PHj,NHj)不變,對(duì)于其他的節(jié)點(diǎn)對(duì)(Mi1,Mi2),當(dāng)Mi1≠M(fèi)j1,中繼節(jié)點(diǎn)將信息修改為(Mj1,Mi2,PHj,NHi).最后發(fā)送MACT_Eliminate消息,這樣就會(huì)刪除多余的邊.

5 實(shí)驗(yàn)分析

本文通過(guò)仿真實(shí)驗(yàn),對(duì)提出的EEDM模型進(jìn)行性能分析.首先比較了不同聚類(lèi)算法對(duì)樹(shù)長(zhǎng)的影響,其次將本文提出的EEDM模型構(gòu)造的分發(fā)樹(shù)樹(shù)長(zhǎng)與斯坦納樹(shù)樹(shù)長(zhǎng)進(jìn)行比較,最后比較了使用EEDM模型與使用廣播以及使用基于鄰居信息廣播算法(Neighbor Knowledge-Based Broadcast,NKB)[20]進(jìn)行副本分發(fā)的能耗消耗.

算法4.環(huán)路消除算法

BEGIN

1 FOR ALL u(u被k對(duì)成員節(jié)點(diǎn)共享)

2 選擇一對(duì)成員節(jié)點(diǎn)(Mj1,Mj2)(1≤j≤k)

3 FOR ALL i(1≤i≤k且i≠j)

4 發(fā)送MACT_Eliminate消息

5 END FOR

6 END FOR

7 FOR ALL w(收到MACT_Eliminate消息的節(jié)點(diǎn))

8 IF w是PHi

9 IF w不是多播成員節(jié)點(diǎn)

10PHi←Mi1到Mi2路徑中w的上一跳

11 發(fā)送MACT_Eliminate消息給上一跳

12 刪除單播路由表中該節(jié)點(diǎn)的路由信息

13 END IF

14 END IF

15 END FOR

END

5.1 聚類(lèi)算法對(duì)樹(shù)長(zhǎng)的影響

為了驗(yàn)證EEDM模型是否具有良好的魯棒性,本文比較了兩種聚類(lèi)算法K-Means以及基于距離的層次聚類(lèi)(Hierarchical clustering)對(duì)樹(shù)長(zhǎng)的影響.本文中用n表示網(wǎng)絡(luò)大小即網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目.文章改變網(wǎng)絡(luò)大小使之從100-800變化,通過(guò)算法1計(jì)算得到的關(guān)鍵節(jié)點(diǎn)個(gè)數(shù)為:12,13,15,13,12,12,13,14.如圖6所示,分別使用K-Means以及基于距離的層次聚類(lèi)算法,從圖中可以看出,兩種聚類(lèi)算法得到的結(jié)果很接近,但K-Means聚類(lèi)算法得到的樹(shù)長(zhǎng)比基于距離的層次聚類(lèi)稍短一些.

圖6 聚類(lèi)算法對(duì)樹(shù)長(zhǎng)的影響Fig.6 Influence of clustering algorithm on tree length

5.2 樹(shù)長(zhǎng)分析

最小生成樹(shù)是在給定的點(diǎn)集和邊中尋求最短網(wǎng)絡(luò)使所有點(diǎn)連通.而最小斯坦納樹(shù)允許在給定點(diǎn)外增加額外的點(diǎn),使生成的最短網(wǎng)絡(luò)開(kāi)銷(xiāo)最小.然而,與最小生成樹(shù)相比,斯坦納樹(shù)可以僅僅通過(guò)一個(gè)常量比率來(lái)最優(yōu)化樹(shù)長(zhǎng).本文得到的分發(fā)樹(shù)長(zhǎng)度和斯坦納樹(shù)的長(zhǎng)度同序,他們之間的近似比不大于10.

圖7 樹(shù)長(zhǎng)比較Fig.7 Tree length comparison

圖7描述了當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)服從正態(tài)分布,聚類(lèi)算法采用K-Means時(shí),斯坦納樹(shù)的長(zhǎng)度以及EEDM模型構(gòu)造的分發(fā)樹(shù)的長(zhǎng)度隨著網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)個(gè)數(shù)變化而變化的曲線圖,從圖中可以看出,本文構(gòu)造的分發(fā)樹(shù)樹(shù)長(zhǎng)與斯坦納樹(shù)樹(shù)長(zhǎng)非常接近.

5.3 能耗分析

云存儲(chǔ)內(nèi)容分發(fā)網(wǎng)絡(luò)中,能源消耗是需要考慮的重要問(wèn)題,能耗是減少網(wǎng)絡(luò)擁堵,提高網(wǎng)絡(luò)性能,保障用戶的QoS的關(guān)鍵,而減少節(jié)點(diǎn)間交換消息的數(shù)量能夠減少消息復(fù)雜度,從而降低能源消耗.

云存儲(chǔ)內(nèi)容分發(fā)網(wǎng)絡(luò)中數(shù)據(jù)分發(fā)的能耗主要由分發(fā)樹(shù)樹(shù)長(zhǎng)以及構(gòu)建分發(fā)樹(shù)時(shí)交換消息的數(shù)量決定,且能耗花費(fèi)與分發(fā)樹(shù)樹(shù)長(zhǎng)、交換消息數(shù)量成正比.本文建立CCDN數(shù)據(jù)分發(fā)的能耗公式,表示為:

P=T×(La+mb)

(1)

其中P代表分發(fā)單位數(shù)據(jù)所產(chǎn)生的總能耗,單位是J;T是發(fā)送的數(shù)據(jù)包個(gè)數(shù);L是構(gòu)建的分發(fā)樹(shù)的總長(zhǎng);m是數(shù)據(jù)分發(fā)過(guò)程中交換信息的總數(shù)量;a和b是功耗參數(shù),分別代表發(fā)送單位長(zhǎng)度數(shù)據(jù)和交換一條信息所需能耗.本文假設(shè)節(jié)點(diǎn)分布在100×100的平方區(qū)域內(nèi),設(shè)置當(dāng)前分發(fā)任務(wù)為T(mén)=103個(gè)數(shù)據(jù)包,每個(gè)數(shù)據(jù)包大小為20k,并設(shè)置a=b=50nJ/bit[19].

本文將EEDM模型副本分發(fā)時(shí)的能耗分別與使用廣播以及使用NKB算法進(jìn)行副本分發(fā)的能耗比較.在NKB算法中,如果節(jié)點(diǎn)ni的未覆蓋鄰居比率較大,說(shuō)明ni需要更大的概率來(lái)轉(zhuǎn)發(fā)消息,相反,如果未覆蓋鄰居比率較小那么要適當(dāng)降低轉(zhuǎn)發(fā)概率以減少冗余消息.然而當(dāng)一個(gè)節(jié)點(diǎn)的未覆蓋鄰居比率較小,但是未覆蓋鄰居絕對(duì)數(shù)量較大時(shí),也需要較大的概率來(lái)轉(zhuǎn)發(fā)消息.同時(shí)當(dāng)節(jié)點(diǎn)處在密度大的區(qū)域則需要較小的轉(zhuǎn)發(fā)概率,相反稀疏區(qū)域需要較大的轉(zhuǎn)發(fā)概率.因此NKB算法是基于未覆蓋鄰居比、絕對(duì)數(shù)量的未覆蓋鄰居因子以及密度因子等鄰居信息來(lái)動(dòng)態(tài)調(diào)整轉(zhuǎn)發(fā)概率的[20].

使用廣播以及NKB算法進(jìn)行副本分發(fā)時(shí),我們已知源節(jié)點(diǎn)以及目的節(jié)點(diǎn),源節(jié)點(diǎn)發(fā)送廣播消息,將數(shù)據(jù)發(fā)送到所有的目的節(jié)點(diǎn).使用廣播以及NKB算法進(jìn)行數(shù)據(jù)分發(fā)的分發(fā)樹(shù)長(zhǎng)為從源節(jié)點(diǎn)到達(dá)所有目的節(jié)點(diǎn)時(shí)所經(jīng)歷的路徑長(zhǎng)度,交換消息數(shù)量為從源節(jié)點(diǎn)到達(dá)所有目的節(jié)點(diǎn)時(shí)所有節(jié)點(diǎn)廣播消息的數(shù)量.

圖8 能耗比較Fig.8 Comparison of energy consumption

圖8為當(dāng)節(jié)點(diǎn)服從正態(tài)分布,聚類(lèi)算法采用K-Means時(shí),EEDM模型進(jìn)行副本分發(fā)時(shí)的能耗花費(fèi)與使用廣播和使用NKB算法進(jìn)行副本分發(fā)能耗花費(fèi)的比較,從圖中可以看出,EEDM模型的能耗花費(fèi)要遠(yuǎn)遠(yuǎn)低于使用其他兩種方式進(jìn)行副本分發(fā)的能耗.

6 總 結(jié)

本文針對(duì)云存儲(chǔ)內(nèi)容分發(fā)網(wǎng)絡(luò)高能耗問(wèn)題,提出了一種基于云存儲(chǔ)內(nèi)容分發(fā)網(wǎng)絡(luò)的能耗優(yōu)化分發(fā)模型.主要工作有一下幾個(gè)方面:首先提出了在云存儲(chǔ)內(nèi)容分發(fā)網(wǎng)絡(luò)中能耗優(yōu)化分發(fā)模型,然后介紹了該模型用到的主要算法,包括確定關(guān)鍵節(jié)點(diǎn)個(gè)數(shù),通過(guò)聚類(lèi)找出關(guān)鍵節(jié)點(diǎn),然后根據(jù)最小化分發(fā)代價(jià)的副本放置多播路由選擇算法構(gòu)建包含所有接收節(jié)點(diǎn)的分發(fā)樹(shù),最后進(jìn)行仿真實(shí)驗(yàn).

實(shí)驗(yàn)結(jié)果表明,本文構(gòu)建的分發(fā)樹(shù)與斯坦納樹(shù)近似,且具有較低的能量消耗,驗(yàn)證了本文提出的能耗優(yōu)化分發(fā)模型能夠有效的節(jié)約能耗.下一步的工作是研究在用戶隨機(jī)到達(dá)的條件下,如何滿足每個(gè)用戶響應(yīng)時(shí)間和服務(wù)成本QoS需求的CCDN能耗優(yōu)化方法.