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

劉玉潔,陸佃杰,張桂娟

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

2(山東省分布式計算機軟件新技術重點實驗室,濟南 250014)

1 引 言

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

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

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

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

2 相關工作

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

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

3 網(wǎng)絡模型

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

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

3.1 CCDN的組成框架

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

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

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

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

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

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

4 算 法

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

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

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

4.1 關鍵節(jié)點選取算法

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

算法1.關鍵節(jié)點個數(shù)k確定算法 K-Canopy

輸入:CCDN網(wǎng)絡中所有節(jié)點的地理坐標集合R

輸出:關鍵節(jié)點個數(shù)k

BEGIN

1T2←R中所有點的平均距離,T1←2×T2

2 k←0

3 WHILER不為空

4 k←k+1

5 從R中隨機選取一個點r0作為中心,并將r0從R中移除

6 FOR ALL r INR

7 d←r到r0的距離

8 IF d

9 將 r歸到以r0為中心的類中,并將r從R中移除

10 ELSE IF d

11 將r歸到以r0為中心的類中

12 END IF

13 END FOR

14 END WHILE

END

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

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

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

輸入:CCDN網(wǎng)絡中所有節(jié)點的地理坐標集合R,關鍵節(jié)點個數(shù)k

輸出:網(wǎng)絡的關鍵節(jié)點集合M

BEGIN

1 對于R中的節(jié)點,用嵌入的聚類算法將其劃分成k個簇Ri(1≤i≤k)

2 FOREACHRi

3 (x0,y0)←Ri中所有節(jié)點坐標的均值

4d0←∞

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

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

7 IFdj

8d0←dj

9Mi←rj

10 END IF

11 END FOREACH

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

12 END FOREACH

END

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

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

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

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

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

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

BEGIN

2 將自己加入到node sequence

3 HopCount←HopCount+1

4 Dist←當前節(jié)點到上一跳節(jié)點的距離

5 Path length←Path length+Dist

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

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

8 NodeSourceDist←當前節(jié)點到源節(jié)點距離

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

10 IF SenderSourceDist < NodeSourceDist

11 IF u收到過該發(fā)送節(jié)點發(fā)送來的信息

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

發(fā)送RREP_J

13 ELSE

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

15 END IF

16 END IF

17 END IF

END

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

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

5 實驗分析

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

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

BEGIN

1 FOR ALL u(u被k對成員節(jié)點共享)

2 選擇一對成員節(jié)點(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é)點)

8 IF w是PHi

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

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

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

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

13 END IF

14 END IF

15 END FOR

END

5.1 聚類算法對樹長的影響

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

圖6 聚類算法對樹長的影響Fig.6 Influence of clustering algorithm on tree length

5.2 樹長分析

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

圖7 樹長比較Fig.7 Tree length comparison

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

5.3 能耗分析

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

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

P=T×(La+mb)

(1)

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

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

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

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

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

6 總 結

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

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