異構(gòu)邊緣網(wǎng)絡(luò)中內(nèi)容擴散策略及優(yōu)化

薛寒星，尤佳莉，王勁林

(1.中國科學(xué)院聲學(xué)研究所國家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心,北京 100190； 2.中國科學(xué)院大學(xué),北京 100190)

0 引 言

邊緣網(wǎng)絡(luò)作為骨干網(wǎng)絡(luò)的補充，如何利用其中海量終端設(shè)備的空閑資源來緩解骨干網(wǎng)絡(luò)的壓力得到了廣泛關(guān)注。因為網(wǎng)絡(luò)中大部分的流量集中在少部分熱門內(nèi)容上[1]，通過內(nèi)容擴散系統(tǒng)[2]將少部分熱門內(nèi)容的副本部署在邊緣網(wǎng)絡(luò)中。用戶直接從終端中獲取低時延的內(nèi)容服務(wù)的同時，骨干網(wǎng)絡(luò)的負(fù)載壓力也會得到極大的緩解。例如在智能路由器[3-5]或蜂窩網(wǎng)絡(luò)中的用戶設(shè)備(UE)[6-7]中部署內(nèi)容副本。網(wǎng)絡(luò)邊緣擁有多種類型的終端設(shè)備，它們可能擁有不同的處理能力和存儲空間,設(shè)備的可用帶寬和設(shè)備間的鏈路狀態(tài)(時延、丟包率等)也會存在差異[8]；同時，CNNIC的統(tǒng)計報告[9]表明不同地理區(qū)域、不同職業(yè)、不同年齡和不同文化程度的用戶對內(nèi)容的訪問都存在差異；所以邊緣網(wǎng)絡(luò)是一個由能力、帶寬和興趣異構(gòu)的邊緣設(shè)備構(gòu)建的網(wǎng)絡(luò)。在邊緣網(wǎng)絡(luò)構(gòu)建和內(nèi)容擴散中如果對所有的設(shè)備一視同仁，忽略它們之間的異構(gòu)性，很容易造成內(nèi)容服務(wù)的瓶頸。因此，異構(gòu)邊緣網(wǎng)絡(luò)中，如何合理地構(gòu)建網(wǎng)絡(luò)拓?fù)洳⒏鶕?jù)用戶興趣實現(xiàn)針對性的內(nèi)容擴散對邊緣網(wǎng)絡(luò)的性能有很大的影響。

本文對異構(gòu)邊緣網(wǎng)絡(luò)中的內(nèi)容擴散策略進(jìn)行研究，主要貢獻(xiàn)包括：

1)提出一種基于節(jié)點簇的分層網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和基于內(nèi)容流行度的覆蓋率需求。在此基礎(chǔ)上設(shè)計一種去中心化的內(nèi)容擴散策略，充分利用邊緣設(shè)備的資源實現(xiàn)熱門內(nèi)容副本的快速擴散。

2)針對邊緣設(shè)備的異構(gòu)性，從擴散目標(biāo)、緩存節(jié)點選擇、傳輸策略這3個方面對內(nèi)容擴散策略進(jìn)行優(yōu)化。首先提出基于指數(shù)的時間衰減的方式刻畫設(shè)備興趣，進(jìn)一步提出基于簇的興趣特征的自適應(yīng)覆蓋率調(diào)整策略。基于該策略擴散完成后的邊緣網(wǎng)絡(luò)可以在設(shè)備興趣異構(gòu)的場景下提供穩(wěn)定的內(nèi)容服務(wù)。然后，綜合考慮設(shè)備能力、興趣和服務(wù)負(fù)載，提出一種啟發(fā)式的緩存節(jié)點選擇策略，均衡設(shè)備服務(wù)負(fù)載差異的同時，提高設(shè)備在本地獲取內(nèi)容服務(wù)的概率。最后，數(shù)據(jù)傳輸部分，提出覆蓋率感知的傳輸內(nèi)容選擇策略和傳輸負(fù)載感知的接收節(jié)點選擇策略，減少系統(tǒng)完成擴散所需的時間。

1 相關(guān)工作

本文研究異構(gòu)的邊緣網(wǎng)絡(luò)中內(nèi)容的擴散，包括節(jié)點能力、帶寬異構(gòu)下的內(nèi)容擴散、用戶興趣的刻畫、基于用戶興趣的分發(fā)和預(yù)取等。

針對節(jié)點能力的異構(gòu)，已有學(xué)者在不同場景下提出針對能力異構(gòu)的網(wǎng)絡(luò)拓?fù)錁?gòu)建的策略。Srivatsa等人[10]設(shè)計了分層的網(wǎng)絡(luò)拓?fù)洌瑢⒛芰^高的節(jié)點部署在上層網(wǎng)絡(luò)。Fesci-Sayit等人[11]在構(gòu)建組播樹的過程中將高帶寬的節(jié)點放在更高的數(shù)據(jù)層來接收低時延的視頻流。Fortuna等人[12]提出了節(jié)點優(yōu)先與高帶寬和低時延的節(jié)點建立連接。所以，網(wǎng)絡(luò)拓?fù)錁?gòu)建中針對設(shè)備能力異構(gòu)的主要思路是將高能力節(jié)點放置在網(wǎng)絡(luò)中更重要的位置。本文在選擇簇的管理節(jié)點時也會優(yōu)先選取帶寬較高和能力較強的節(jié)點。

很多學(xué)者在節(jié)點帶寬異構(gòu)的情況下對內(nèi)容的快速擴散進(jìn)行了研究。Langer等人[13]在帶寬異構(gòu)下研究數(shù)據(jù)分塊策略來加速內(nèi)容傳輸速率。Meng等人[14]在流傳輸模型下，通過分割節(jié)點的高帶寬來減少多文件的擴散所需時間。Ku等人[15]在完全二叉樹中選擇擁有更高比例的未緩存內(nèi)容的子節(jié)點優(yōu)先接收內(nèi)容。Bhat等人[16]在廣播和多播中提出了優(yōu)先選擇最快的節(jié)點(Fast Node First, FNF)來接收數(shù)據(jù)。Silva等人[17]提出了一種帶寬感知(Bandwidth Aware Scheduler, BAS)的節(jié)點選擇策略，節(jié)點被選擇來接收內(nèi)容的概率正比于節(jié)點的帶寬。Abeni等人[18]修正了ELp[19]策略，加入帶寬特征來選擇合適的接收節(jié)點。Wang等人[20]提出了綜合節(jié)點的帶寬和內(nèi)容的稀有情況來選擇合適的接收節(jié)點?？梢园l(fā)現(xiàn)相關(guān)研究的主要思路即以較大的概率優(yōu)先選擇帶寬較高的節(jié)點進(jìn)行內(nèi)容擴散，盡早利用這部分節(jié)點的帶寬資源。然而這些策略都忽略了節(jié)點傳輸?shù)呢?fù)載，可能會導(dǎo)致部分帶寬略低的節(jié)點資源的浪費，所以本文提出優(yōu)化的基于節(jié)點傳輸負(fù)載的接收節(jié)點選擇策略。

針對用戶興趣異構(gòu)的內(nèi)容服務(wù)研究主要包括2個部分：用戶興趣的刻畫和基于興趣的內(nèi)容預(yù)取和緩存管理。在興趣刻畫和挖掘方面，第一種策略是基于用戶設(shè)備已緩存的內(nèi)容刻畫興趣，主要為語義網(wǎng)絡(luò)的構(gòu)建。Voulgaris等人[21]根據(jù)節(jié)點間擁有內(nèi)容的相似性來構(gòu)建語義網(wǎng)絡(luò)，提高檢索的成功率。另一種方式是通過用戶的歷史訪問(檢索)記錄刻畫用戶的興趣，進(jìn)而進(jìn)行內(nèi)容的推薦和預(yù)取。在推薦系統(tǒng)中，Ding等人[22]提出了指數(shù)衰減的加權(quán)模型為不同時刻的用戶行為賦予不同的權(quán)重，并基于用戶的興趣來預(yù)取內(nèi)容。Shen等人[23]在社交網(wǎng)絡(luò)中提出了基于興趣的數(shù)據(jù)塊預(yù)取，降低用戶觀看視頻的啟動時延。Xu等人[24]通過分析觀看記錄刻畫用戶的興趣，進(jìn)一步通過協(xié)同過濾方法來選出預(yù)取內(nèi)容。不同于已有的研究，本文的內(nèi)容擴散策略的本質(zhì)是熱門內(nèi)容的擴散，節(jié)點間的鄰居關(guān)系更側(cè)重于相似的網(wǎng)絡(luò)狀態(tài)和較近的網(wǎng)絡(luò)距離來提供低時延的內(nèi)容服務(wù)。所以本文僅基于用戶的興趣來指導(dǎo)內(nèi)容擴散中的副本數(shù)量和放置位置。

2 興趣刻畫和異構(gòu)邊緣設(shè)備組網(wǎng)策略

2.1 用戶興趣刻畫

因為邊緣設(shè)備有內(nèi)容感知的特性，可以獲取并記錄用戶請求的相關(guān)信息。假設(shè)網(wǎng)絡(luò)中存在的內(nèi)容種類集合為M，RNi,j,x表示節(jié)點i對j類內(nèi)容在距離當(dāng)前時刻x天的請求數(shù)量。設(shè)備會記錄并定時更新前k天中的每類內(nèi)容在每天的請求數(shù)量，見公式(1)。矩陣中的每一行代表一天中節(jié)點i對每類內(nèi)容的請求數(shù)量，不同的行代表不同天的請求情況。同時，研究表明用戶的興趣可能會隨時間而改變[22]。所以基于用戶對不同內(nèi)容的請求數(shù)量，本文提出一種基于指數(shù)的時間衰減的方式來刻畫用戶的興趣，具體計算見公式(2)。其中，Ii,j表示節(jié)點i對內(nèi)容j的興趣系數(shù)，可以看出x越大，距離當(dāng)前時刻越遠(yuǎn)，相應(yīng)的請求情況對興趣系數(shù)的影響越小。通過歸一化計算，節(jié)點i對j類內(nèi)容的興趣系數(shù)為NIi,j，見公式(3)。節(jié)點將定期更新每類內(nèi)容的的興趣特征，具體形式為{NIi,1,…,NIi,j,…,NIi,m}。

(1)

(2)

(3)

2.2 異構(gòu)邊緣設(shè)備的組網(wǎng)策略

相對于扁平的覆蓋網(wǎng)絡(luò)，層次化的網(wǎng)絡(luò)具有更好的擴展性，因此本文使用層次式的覆蓋網(wǎng)絡(luò)來組織異構(gòu)的邊緣設(shè)備。因為在內(nèi)容擴散策略中，節(jié)點的帶寬對內(nèi)容擴散的速率和最終的服務(wù)性能有非常大的影響，所以本文在網(wǎng)絡(luò)構(gòu)建中以節(jié)點帶寬能力的異構(gòu)為主。具體的網(wǎng)絡(luò)拓?fù)錁?gòu)建流程為：

1)設(shè)備根據(jù)物理拓?fù)涞慕菩赃M(jìn)行分簇，防止出現(xiàn)邏輯邊緣網(wǎng)絡(luò)與物理網(wǎng)絡(luò)失配的問題。簇內(nèi)的邊緣設(shè)備之間建立全連接的無結(jié)構(gòu)網(wǎng)絡(luò)。

2)每個簇選取帶寬最高的節(jié)點作為管理節(jié)點，其余為普通節(jié)點。在多個設(shè)備擁有相同帶寬時，優(yōu)先選擇擁有更強處理能力的設(shè)備。管理節(jié)點維護(hù)簇內(nèi)所有邊緣設(shè)備的信息，包括設(shè)備的帶寬、興趣和已緩存副本。管理節(jié)點基于簇內(nèi)節(jié)點的興趣特征計算簇的興趣特征，CNIC,j表示簇C對j類內(nèi)容的興趣系數(shù)，計算過程見公式(4)：

(4)

3)不同簇的管理節(jié)點之間構(gòu)建無結(jié)構(gòu)的簇間連接網(wǎng)絡(luò)。圖1中展示了分層網(wǎng)絡(luò)結(jié)構(gòu)的示例。

圖1 分層的網(wǎng)絡(luò)結(jié)構(gòu)

3 去中心化的內(nèi)容擴散及優(yōu)化策略

3.1 層次式網(wǎng)絡(luò)中的去中心化擴散

3.1.1 內(nèi)容擴散目標(biāo)

內(nèi)容擴散策略的擴散目標(biāo)是將熱門內(nèi)容的副本擴散在每個簇內(nèi)，使得節(jié)點可以在簇內(nèi)直接獲取熱門內(nèi)容的服務(wù)。本文首先將簇C在t時刻對內(nèi)容j的覆蓋率CC,j(t)定義為簇內(nèi)j的副本數(shù)量與簇中所有節(jié)點數(shù)量的比值，計算見公式(5)。其中，xi,j(t)表示節(jié)點i在t時刻是否緩存了j，已緩存則xi,j(t)=1，否則xi,j(t)=0。管理服務(wù)器根據(jù)全局的內(nèi)容請求情況為不同的內(nèi)容設(shè)定相應(yīng)的覆蓋率需求，計算見公式(6)。其中，Cd(j)表示內(nèi)容j的需求覆蓋率，NRj表示內(nèi)容j的請求數(shù)量，F(xiàn)表示系統(tǒng)中所有內(nèi)容的集合?？梢约僭O(shè)當(dāng)內(nèi)容在簇內(nèi)的覆蓋率大于需求覆蓋率時，簇中該內(nèi)容的副本數(shù)量足以向簇內(nèi)節(jié)點提供就近的內(nèi)容服務(wù)。

(5)

(6)

3.1.2 層次式網(wǎng)絡(luò)中的去中心化內(nèi)容擴散

針對分層網(wǎng)絡(luò)拓?fù)浜蛿U散目標(biāo)，本文提出一種去中心化的內(nèi)容擴散策略，具體擴散流程如下：

1)管理服務(wù)器隨機選擇某個簇的管理節(jié)點作為擴散內(nèi)容j的種子節(jié)點，種子節(jié)點通過簇間覆蓋網(wǎng)絡(luò)將j的消息廣播至所有簇的管理節(jié)點。

2)收到關(guān)于j的消息的管理節(jié)點確定的j覆蓋率需求，根據(jù)「Cd(j)×|C|?確定簇內(nèi)需要擴散的j的副本數(shù)量。根據(jù)緩存節(jié)點選擇策略，管理節(jié)點在簇內(nèi)選擇相應(yīng)數(shù)量的節(jié)點來緩存副本，同時告知已緩存j副本的源節(jié)點地址。

3)被選擇的節(jié)點向已緩存j的內(nèi)容源節(jié)點請求數(shù)據(jù)。內(nèi)容源節(jié)點通過選擇傳輸?shù)膬?nèi)容和接收的節(jié)點來完成數(shù)據(jù)傳輸。在所有簇都滿足擴散內(nèi)容的覆蓋率需求后，去中心化的內(nèi)容擴散即完成。

圖2 層次式網(wǎng)絡(luò)內(nèi)容擴散的實例

圖2中展示了一個層次式網(wǎng)絡(luò)中的內(nèi)容擴散實例。覆蓋率需求為0.2的內(nèi)容的副本從簇1的管理節(jié)點擴散到4個簇中。

3.2 內(nèi)容擴散的優(yōu)化策略

3.2.1 擴散目標(biāo)優(yōu)化策略

如前文所述，不同的用戶擁有不同的喜好，局部請求情況可能會與全局請求情況存在顯著差異。所以根據(jù)全局請求情況設(shè)定的內(nèi)容覆蓋率需求與單個簇內(nèi)的需求可能并不相同。因為管理節(jié)點維護(hù)了整個簇的興趣情況，在簇內(nèi)的內(nèi)容擴散過程中，可以基于簇的興趣情況對全局的覆蓋率需求進(jìn)行自適應(yīng)的調(diào)整。本文提出一種基于興趣的覆蓋率調(diào)整策略(Interest-based Adjustment of Coverage, IAC)，具體見公式(7)，其中，Cd(C,j)表示調(diào)整后的簇C對內(nèi)容j的覆蓋率需求。內(nèi)容j屬于類別x，CNIC,x×|M|的數(shù)值反映的是簇C內(nèi)節(jié)點對x類內(nèi)容的平均喜好情況。CNIC,x×|M|>1表示簇內(nèi)節(jié)點對x類內(nèi)容的喜好超出平均值，所以適當(dāng)上調(diào)覆蓋率需求。反之則降低覆蓋率需求。

Cd(C,j)=Cd(j)×CNIC,x×|M|

(7)

3.2.2 緩存節(jié)點選擇策略優(yōu)化

因為節(jié)點的帶寬存在差異，相應(yīng)提供服務(wù)的能力也不同?？梢赃m當(dāng)?shù)卦谀芰^高的節(jié)點上部署較多內(nèi)容的副本來充分利用節(jié)點的帶寬資源。同時，不同用戶的興趣也存在差異，在選擇緩存節(jié)點時也需要考慮節(jié)點的興趣特征。通過綜合考慮節(jié)點的帶寬、服務(wù)負(fù)載和興趣，本文提出優(yōu)化的綜合緩存節(jié)點選擇策略。

設(shè)BWmin表示向一個節(jié)點提供穩(wěn)定視頻服務(wù)的最小上行帶寬。節(jié)點i的帶寬等級BWLi的計算見公式(8)，實質(zhì)是節(jié)點帶寬與最小帶寬的比值的取整，反映了節(jié)點可以同時向多少個鄰居節(jié)點提供服務(wù)。帶寬等級越高表示節(jié)點的能力越強。本文將節(jié)點的服務(wù)負(fù)載NLi定義為節(jié)點帶寬等級和節(jié)點緩存副本數(shù)量的比值，計算見公式(9)，其中，xi(t)表示節(jié)點i在t時刻已緩存副本數(shù)。NLi反映了每個副本能分到的節(jié)點帶寬，數(shù)值越大代表每個副本分到的帶寬越多，節(jié)點的負(fù)載越??；反之則負(fù)載較大。

(8)

(9)

設(shè)NBWLi和NNLi分別表示歸一化后的帶寬等級和服務(wù)負(fù)載，歸一化方式見公式(10)和公式(11)。定義每個節(jié)點對于內(nèi)容j的綜合指標(biāo)為CIi,j，計算見公式(12)，其中，wBW、wNL和wI分別為節(jié)點帶寬、服務(wù)負(fù)載和興趣的權(quán)重。管理節(jié)點在選擇節(jié)點緩存副本時，計算簇內(nèi)所有節(jié)點對j的綜合指標(biāo)，并根據(jù)CIi,j的數(shù)值對節(jié)點進(jìn)行降序排序，優(yōu)先選擇CIi,j數(shù)值較高的節(jié)點來緩存內(nèi)容的副本。

(10)

(11)

CIi,j=wBW×NBWLi+wNL×NNLi+wI×NIi,j

(12)

3.2.3 數(shù)據(jù)傳輸策略優(yōu)化

在設(shè)計的內(nèi)容擴散策略中，每個節(jié)點可能會緩存多個內(nèi)容的副本。相應(yīng)地，緩存多個內(nèi)容副本的節(jié)點會作為多個內(nèi)容的源節(jié)點，會收到來自不同節(jié)點關(guān)于不同內(nèi)容的請求。因為不同的節(jié)點擁有不同的帶寬，內(nèi)容源節(jié)點優(yōu)先處理哪個內(nèi)容的請求，并選擇哪個節(jié)點來接收內(nèi)容對擴散的速率和完成的時間可能會有很大的影響。因此，本文對傳輸內(nèi)容和接收節(jié)點的選擇策略進(jìn)行優(yōu)化。

在擴散完成后，內(nèi)容的副本數(shù)量與其覆蓋率需求成正比。覆蓋率需求越高，內(nèi)容的副本數(shù)量會越多，相應(yīng)的擴散次數(shù)也更多。所以本文提出一種覆蓋率感知(Coverage rate Aware, CA)的傳輸內(nèi)容選擇策略，即內(nèi)容被選擇傳輸?shù)母怕收扔谄涓采w率需求。設(shè)CQNi,j表示向節(jié)點i請求內(nèi)容j的節(jié)點集合，CCi(t)表示節(jié)點i在時刻t已緩存的內(nèi)容集合，CSi表示節(jié)點i已完成緩存，并且當(dāng)前傳輸請求數(shù)量大于零的內(nèi)容集合，見公式(13)。節(jié)點i從已緩存的內(nèi)容中選擇內(nèi)容j傳輸?shù)母怕室姽?14)，節(jié)點會大概率選擇覆蓋率需求更高的內(nèi)容優(yōu)先傳輸。

CSi={x|x∈CCi(t),|CQNi,x|>0}

(13)

(14)

相比于上傳帶寬較低的節(jié)點，上傳帶寬較高的節(jié)點對內(nèi)容擴散的速率有更大影響。但是每個節(jié)點完成內(nèi)容的緩存后也需要處理傳輸請求繼續(xù)進(jìn)行擴散，把過多的副本全部優(yōu)先推送到高帶寬節(jié)點上可能會超出它們帶寬的能力范疇，部分擁有相對較低帶寬的節(jié)點的資源卻在空閑。因此，本文提出傳輸負(fù)載感知(Transmission Load Aware, TLA)的接收節(jié)點選擇策略。節(jié)點的傳輸負(fù)載TLi定義為節(jié)點在當(dāng)前時刻待處理的傳輸請求數(shù)量和節(jié)點帶寬等級的比值，計算見公式(15)，其中，節(jié)點i在t時刻可以處理的傳輸請求是所有請求中已經(jīng)完成緩存的內(nèi)容的請求，即集合CSi中內(nèi)容的請求。TLi數(shù)值越大，表示相對于節(jié)點的帶寬，節(jié)點當(dāng)前時刻需要處理的傳輸請求會更多，因此節(jié)點的傳輸負(fù)載越大。相應(yīng)地，數(shù)值越小表示節(jié)點的傳輸負(fù)載越小。因此，在選擇接收節(jié)點時，優(yōu)先選擇TLi數(shù)值較小的節(jié)點來傳輸內(nèi)容，可以更充分地利用節(jié)點資源。

(15)

4 實驗與分析

4.1 實驗設(shè)計

本文在Peersim[25]仿真平臺下實現(xiàn)整個異構(gòu)網(wǎng)絡(luò)中的內(nèi)容擴散策略。仿真實驗中，邊緣網(wǎng)絡(luò)的規(guī)模固定為2000，每個簇的規(guī)模大小限制在[50，100]范圍內(nèi)。其中，邊緣設(shè)備的存儲空間為8 GB。假設(shè)網(wǎng)絡(luò)中共有10000個內(nèi)容，每個文件大小為200 MB，對應(yīng)的請求數(shù)量服從Zipf分布(α=1.0)。系統(tǒng)將在邊緣網(wǎng)絡(luò)中擴散最熱門的100個文件，每個文件的覆蓋率需求可以根據(jù)公式(6)計算得出。管理服務(wù)器的上行帶寬為20 Mbps，為每一個擴散文件隨機選擇一個簇的管理節(jié)點作為種子節(jié)點，按照順序依次將100個待擴散文件傳輸至各自的種子節(jié)點。

因為設(shè)備的上行帶寬對內(nèi)容擴散的速率有重要的影響，實驗中所有設(shè)備的上行帶寬分為3檔，分別為1 Mbps、2 Mbps、4 Mbps，相應(yīng)的設(shè)備數(shù)量分別占設(shè)備總數(shù)的比例為70%、20%、10%。BWmin的取值為0.85 Mbps，設(shè)備會采用先到先服務(wù)的策略，拒絕超出帶寬能力的服務(wù)請求。實驗中所有的內(nèi)容被隨機分為5個不同的類別。為了模擬用戶的歷史請求情況，根據(jù)內(nèi)容的流行度排名和Zipf分布生成多輪請求，將所有的請求行為隨機分發(fā)至網(wǎng)絡(luò)中的設(shè)備。邊緣設(shè)備根據(jù)請求情況，基于公式(3)和公式(4)計算對應(yīng)的用戶和簇的興趣特征。

4.2 實驗評估

本文設(shè)計的內(nèi)容擴散策略與已有策略的區(qū)別在于：1)擴散對象不同，不同于已有的CDN網(wǎng)絡(luò)或P2P網(wǎng)絡(luò)中的擴散，本文設(shè)計的策略是在用戶側(cè)的智能終端構(gòu)建的邊緣網(wǎng)絡(luò)中進(jìn)行擴散；2)擴散目標(biāo)不同，已有擴散策略是將熱門內(nèi)容的副本部署在CDN的邊緣服務(wù)器，或?qū)⒂脩粽埱蟮膬?nèi)容擴散至終端設(shè)備，本文設(shè)計的策略是在設(shè)備的鄰域內(nèi)預(yù)部署熱門內(nèi)容的副本；3)擴散方式不同，本文設(shè)計的策略采用主動推送的方式將內(nèi)容的消息擴散至網(wǎng)絡(luò)，進(jìn)一步采用拉取的方式進(jìn)行數(shù)據(jù)的傳輸，整個擴散過程采用的是去中心化的方式實現(xiàn)快速的擴散。所以本文的擴散策略與已有策略存在較大區(qū)別，很難找到較為相近的策略或方法進(jìn)行定量的比較，在實驗評估部分使用優(yōu)化后的策略與初始策略進(jìn)行比較。

4.2.1 覆蓋率調(diào)整策略評估

實驗在擴散完成后會模擬用戶請求峰值情況，即所有用戶同時發(fā)起請求。其中，不同內(nèi)容的請求數(shù)量服從Zipf分布。本文定義邊緣網(wǎng)絡(luò)的服務(wù)成功率為節(jié)點從簇內(nèi)成功獲取內(nèi)容服務(wù)的請求數(shù)量與總的請求數(shù)量的比值，數(shù)值越高表示用戶有更高的概率直接從簇內(nèi)獲取低時延的內(nèi)容服務(wù)。因為實驗中隨機模擬用戶的興趣，本文在同等條件下進(jìn)行了5次實驗。圖3展示了5次擴散完成后邊緣網(wǎng)絡(luò)的服務(wù)成功率，Default表示未調(diào)整的默認(rèn)覆蓋率。Upper Limit表示成功率的上限，即所有請求中關(guān)于已擴散內(nèi)容的請求數(shù)量占的比例。由圖3可知，基于IAC的邊緣網(wǎng)絡(luò)擴散完成后可以提供穩(wěn)定的服務(wù)，并且服務(wù)成功率非常接近理論上限。覆蓋率不調(diào)整的網(wǎng)絡(luò)的服務(wù)成功率則在0.43～0.5之間波動。原因在于相對于全局的請求分布，在隨機分配用戶請求行為的場景中，局部請求情況可能與全局請求情況存在較大差異。部分簇對最熱門的內(nèi)容可能會擁有很高的請求比例，而其余簇對最熱門的內(nèi)容的請求比例可能并不高。所以在第4次實驗中，當(dāng)局部請求情況都很接近全局請求情況時，擴散不調(diào)整覆蓋率需求也可以獲取較高的服務(wù)成功率。但是在內(nèi)容請求的分布不均的場景下，不調(diào)整覆蓋率擴散的服務(wù)成功率會出現(xiàn)不同程度的下降。

圖3 不同覆蓋率需求下邊緣網(wǎng)絡(luò)的服務(wù)成功率

圖4展示了5次實驗完成后網(wǎng)絡(luò)中的副本總數(shù)。未調(diào)整覆蓋率時，多次擴散完成后的副本總數(shù)相同。但是基于IAC擴散完成后的內(nèi)容副本數(shù)會出現(xiàn)小范圍波動，同時比未調(diào)整要略高約1.3%。這是因為IAC是基于初始覆蓋率需求進(jìn)行調(diào)整，除了初始覆蓋率需求較高的最流行的內(nèi)容，其余內(nèi)容的覆蓋率調(diào)整幅度都很小。而且因為最流行的內(nèi)容請求相對較多，整體調(diào)整后的覆蓋率需求會略微上浮。圖5展示了2個簇調(diào)整后的覆蓋率需求和默認(rèn)的覆蓋率需求。圖中可以明顯地看出流行度排名靠前的內(nèi)容的覆蓋率波動較大，流行度排名靠后的內(nèi)容的覆蓋率需求波動幅度較小。較為流行的內(nèi)容整體的覆蓋率需求會略微增加。

圖4 擴散完成后的副本總數(shù)

圖5 調(diào)整后的覆蓋率需求

4.2.2 緩存節(jié)點選擇策略評估

在自適應(yīng)調(diào)整覆蓋率的基礎(chǔ)上，本節(jié)對不同的緩存節(jié)點選擇策略進(jìn)行了比較，包括：隨機選擇(Random)、基于帶寬和負(fù)載的選擇策略(Bandwidth and Load， BL)、本文提出的基于帶寬、負(fù)載和興趣的選擇策略(Bandwidth, Load and Interest， BLI)。BLI策略基于公式(12)，BL策略為公式(12)去除興趣特征NIi,j。在實驗中，不同特征的權(quán)重取值均相同。

本節(jié)將節(jié)點間的服務(wù)差異定義為節(jié)點緩存副本數(shù)和帶寬等級的比值(NLi的倒數(shù))的標(biāo)準(zhǔn)差，相應(yīng)的數(shù)值越大表示節(jié)點間的負(fù)載越不均衡。表1展示了基于不同緩存節(jié)點選擇策略的擴散完成后的性能。在服務(wù)成功率部分，不同的節(jié)點選擇策略影響很小，因為相應(yīng)的覆蓋率需求設(shè)計使得對應(yīng)的副本數(shù)量足以滿足簇內(nèi)節(jié)點的請求。但是在服務(wù)負(fù)載差異方面，隨機策略要明顯大于BL和BLI，這是因為隨機策略在選擇節(jié)點時不會考慮節(jié)點的帶寬能力，將所有的節(jié)點同構(gòu)化，導(dǎo)致?lián)碛休^高上傳帶寬的節(jié)點不會緩存較多的副本來提供服務(wù)，導(dǎo)致這些節(jié)點間的副本分布和能力分布不匹配。相反，BL和BLI策略在選擇時會綜合考慮節(jié)點的帶寬和緩存的副本數(shù)，擴散副本時會盡可能將副本的數(shù)量正比于節(jié)點的服務(wù)能力，節(jié)點間的服務(wù)負(fù)載會比較均衡。

表1 不同緩存節(jié)點選擇策略的服務(wù)性能

指標(biāo)上限RandomBLBLI服務(wù)成功率0.530.5210.5220.52服務(wù)負(fù)載差異-0.6230.1470.167

圖6展示了邊緣網(wǎng)絡(luò)成功服務(wù)中，節(jié)點在本地獲取內(nèi)容服務(wù)(0Hip)和1跳鄰居獲取服務(wù)(1Hip)的各自占比。由圖可知，BL策略和隨機策略的分布基本相同，約15%～17.4%的服務(wù)由本地節(jié)點直接提供，82.6%～85%的服務(wù)由鄰居提供。BLI策略增加了用戶的興趣特征后，將本地提供服務(wù)的比例顯著提高了約25.5%。這是因為在多個候選節(jié)點擁有相同的加權(quán)帶寬和負(fù)載的情況下，考慮用戶的興趣特征會優(yōu)先將副本放置在更容易請求該內(nèi)容的節(jié)點上，所以BLI算法的本地服務(wù)成功率會明顯更高。

圖6 邊緣網(wǎng)絡(luò)成功服務(wù)中不同跳數(shù)的比例

4.2.3 數(shù)據(jù)傳輸策略優(yōu)化評估

本節(jié)使用擴散完成所需時間來評估提出的覆蓋率感知的傳輸內(nèi)容選擇策略(CA)和傳輸負(fù)載感知的接收節(jié)點選擇策略(TLA)。首先固定接收節(jié)點選擇策略為TLA，與CA比較的傳輸內(nèi)容選擇策略包括：輪詢策略(Polling)和隨機策略(Random)。因為擴散過程中不同內(nèi)容擴散的副本數(shù)不同，相應(yīng)的稀缺程度不能反映副本的真實稀缺情況，所以未與文獻(xiàn)[16]和文獻(xiàn)[18]中的算法進(jìn)行比較。表2展示了在不同傳輸內(nèi)容選擇策略下的擴散完成時間。由表中數(shù)據(jù)可知，相對于輪詢策略和隨機策略，CA策略能以更短的時間完成擴散，減少了約7.6%的時間。因為不同內(nèi)容的覆蓋率需求不同，相應(yīng)的擴散副本數(shù)量不同?；诟采w率感知的選擇策略在傳輸過程中，可以將有限的帶寬資源按照比例賦予不同的內(nèi)容，所以可以在較短的時間內(nèi)完成擴散。因為輪詢策略和隨機策略都是盡可能均衡地選擇不同的傳輸內(nèi)容，所以使得部分副本數(shù)量不是很多的內(nèi)容優(yōu)先被擴散，傳輸任務(wù)較重的內(nèi)容較后被擴散，擴散完成時間會相對較長。但是因為整體的內(nèi)容擴散可以實現(xiàn)高效的資源利用，所以不同策略的擴散完成時間差距不大。

表2 不同傳輸內(nèi)容選擇策略下的擴散完成時間

指標(biāo)PollingRandomCA擴散完成時間/h5.785.895.44

固定傳輸內(nèi)容選擇策略為CA，與TLA比較的接收節(jié)點選擇策略為相關(guān)工作中提到的FNF[16]和BAS[17]。表3展示了在不同接收節(jié)點選擇策略下的擴散完成時間。由表中數(shù)據(jù)可知，F(xiàn)NF擴散完成時間最長，BAS次之，TLA最短。FNF在選擇接收節(jié)點時只考慮節(jié)點帶寬，將所有的內(nèi)容副本都優(yōu)先傳送到高帶寬的節(jié)點上。這使得高帶寬節(jié)點上累積了大量超出傳輸能力的副本，而帶寬相對較低的節(jié)點的帶寬資源卻在空閑。同時，根據(jù)緩存節(jié)點選擇策略，流行度較低的內(nèi)容往往最后會被放置在帶寬較低的節(jié)點上，這部分內(nèi)容擴散完成的時間對整個網(wǎng)絡(luò)擴散完成的時間有重要的影響，所以FNF有最長的擴散完成時間。BAS將節(jié)點選擇概率正比于節(jié)點帶寬，改善了FNF中的缺陷，帶寬較少的節(jié)點也會以一定的概率被選擇，在一定程度上減少了擴散完成的時間。TLA進(jìn)一步通過定義的傳輸負(fù)載來量化節(jié)點帶寬和等待傳輸?shù)恼埱笄闆r，通過更準(zhǔn)確地衡量接收節(jié)點當(dāng)前的傳輸負(fù)載來尋找當(dāng)前負(fù)載最小的節(jié)點優(yōu)先接收，實現(xiàn)了較優(yōu)的數(shù)據(jù)擴散，減少了約9.3%的擴散完成所需時間。

表3 不同接收節(jié)點選擇策略下的擴散完成時間

指標(biāo)FNFBASTLA擴散完成時間/h6.336.05.44

5 結(jié)束語

針對邊緣設(shè)備能力和所屬用戶興趣的異構(gòu)性，本文首先提出了分層的邊緣網(wǎng)絡(luò)拓?fù)錁?gòu)建，基于內(nèi)容的請求頻率設(shè)計了覆蓋率需求和去中心化的內(nèi)容擴散策略，實現(xiàn)了熱門內(nèi)容副本的快速擴散。進(jìn)一步考慮設(shè)備能力和興趣異構(gòu)性，從擴散目標(biāo)、緩存節(jié)點選擇和數(shù)據(jù)傳輸策略方面對擴散策略進(jìn)行優(yōu)化，提出了基于用戶興趣的覆蓋率需求自適應(yīng)調(diào)整策略，使得邊緣網(wǎng)絡(luò)在用戶請求分布不均的情況下可以提供穩(wěn)定的服務(wù)。進(jìn)一步綜合考慮設(shè)備的帶寬、負(fù)載和興趣優(yōu)化緩存節(jié)點選擇策略，提高了約25.5%的用戶在本地直接獲取服務(wù)的比例。最后通過提出覆蓋率感知的傳輸內(nèi)容選擇策略和傳輸負(fù)載感知的接收節(jié)點選擇策略，減少了約7.6%的完成擴散所需時間。