一種基于P2P內(nèi)容分發(fā)系統(tǒng)帶寬分配算法研究

張旋　李銘　李曉強　曹建民

摘 要：針對如何使混合型架構(gòu)流媒體內(nèi)容分發(fā)系統(tǒng)服務(wù)容量最大的問題，文章按照多文件分發(fā)的服務(wù)容量模型將帶寬分配問題映射為背包問題，提出了利用遺傳算法進(jìn)行服務(wù)器帶寬分配的方法，通過構(gòu)造修復(fù)算子保證了解的可行性。仿真實驗證明了該算法可快速提高系統(tǒng)服務(wù)容量。

關(guān)鍵詞：內(nèi)容分發(fā)；流媒體；帶寬分配；遺傳算法

近年來的研究和實踐表明，結(jié)合傳統(tǒng)內(nèi)容分發(fā)網(wǎng)絡(luò)（Content Delivery Network，CDN）和對等網(wǎng)絡(luò)（Peer to Peer，P2P）流媒體技術(shù)的混合式分發(fā)框架在可靠性和擴(kuò)展性方面發(fā)揮二者的技術(shù)互補性，逐漸成為研究的熱點?；旌峡蚣苤械姆?wù)器帶寬分配問題是影響系統(tǒng)服務(wù)容量的決定性因素之一，Banerjee等[1]提出的雙層拓?fù)浞职l(fā)方案OMNI，Chawathe等[2提出的預(yù)部署Proxy的Scattercast方案，以及Dongyan Xu等[3]結(jié)合了CDN和P2P流媒體分發(fā)技術(shù)提出的混合結(jié)構(gòu)流媒體點播方案，通過優(yōu)化骨干分發(fā)網(wǎng)絡(luò)的組播樹以降低源到端的分發(fā)時延，但在服務(wù)器帶寬分配問題上普遍缺乏有效的機制。本文采用文獻(xiàn)中提出的CDN與P2P混合分發(fā)系統(tǒng)通用模型，分析了區(qū)分冷熱度多文件點播系統(tǒng)的系統(tǒng)服務(wù)容量[4]，將服務(wù)器帶寬資源分配問題映射為背包問題，提出了基于遺傳算法的帶寬分配算法（Genetic Algorithm-Bandwidth Distribution Algorithm，GA-BDA），仿真實驗證明該算法在執(zhí)行效率上優(yōu)于盡力服務(wù)的調(diào)度算法（Best Effort Based Bandwidth Distribution Algorithm，BEB-BDA）。

1 系統(tǒng)服務(wù)容量模型

設(shè)CDN服務(wù)器上可供點播的視頻文件總數(shù)為F，視頻文件fi，i∈[1，F(xiàn)]。CDN服務(wù)器以fi的編碼率bi作為該文件的最小帶寬分配單位，分配給fi的流數(shù)據(jù)頻道數(shù)以xi表示，fi點播服從概率為δi的ZIPF概率分布，點播請求得到響應(yīng)的概率為φi，于是單個文件fi的請求服務(wù)容納率表示為wi=λδiφi，全局請求服務(wù)容納率。

多文件分發(fā)時CDN服務(wù)器的帶寬資源分配問題，可轉(zhuǎn)換成無限的背包問題（Unbounded Knapsack Problem，UKP）。由于UKP是NP-Completed問題，其求解過程是一個NP-Hard問題。鑒于人工智能里的啟發(fā)式算法對解決此類問題具有相當(dāng)?shù)膬?yōu)勢，故引入遺傳算法解決服務(wù)器帶寬分配問題。

2 基于遺傳算法的帶寬分配算法

對于上述提出的帶寬分配問題設(shè)計如下的染色體編碼方案：用位二進(jìn)制串來表示UKP問題中的一個變量xi，將待求解的染色體表示為長為的二進(jìn)制編碼串S。

目標(biāo)函數(shù)：maximizewixij

約束函數(shù)：subject to bixij≤B，xi=0或1，（i=1，2，…n）

適應(yīng)度函數(shù)，其中，qm=wm

2.1 遺傳算子

（1）選擇：分別從總體中隨機抽取的T個個體構(gòu)造兩類個體池，再從兩個池中分別選出適應(yīng)度最大的兩個個體作為雙親。

（2）交叉：使用均勻交叉算子作為默認(rèn)的交叉算子。在均勻交叉算子中，兩個雙親只有一個孩子。孩子解中的每一位都是通過拷貝雙親一方相對應(yīng)的位而來，選擇兩個雙親里的哪一個是由一個二進(jìn)制的隨機變量決定第一位雙親還是第二位雙親。

（3）變異：隨機的選定孩子解中的幾位，使該位的值改變。本文變異概率設(shè)置為0.01。

2.2 修正算子和初始種群

本文定義的適應(yīng)度函數(shù)的前提是只在可行解的解空間內(nèi)進(jìn)行搜索，為了保證經(jīng)過交叉、變異操作后產(chǎn)生的解具有可行性，現(xiàn)引入基于簡單貪心算法的啟發(fā)性算子，稱為修正算子。定義物品的收益率為qi/wi，根據(jù)貪心思想，物品的收益率越大，算法產(chǎn)生的解中該物品相對應(yīng)的那一位變量為1的概率就越大，修正算子依據(jù)收益率決定孩子解中的每個變量的取值。修正算子由兩部分操作組成，第一步是Drop操作，按物品收益率遞增的順序遍歷每個變量，一旦發(fā)現(xiàn)該解不可行但變量為1，置該位變量為0。第二步是Add操作，按收益率遞減的順序遍歷每個變量，如果發(fā)現(xiàn)該解可行但變量為0，置該位變量為1。Drop操作的目的是從不可行解中獲取可行的解，Add操作的目的是提高可行解的適應(yīng)度。為使修正算子達(dá)到較高的運行效率，一般需要對每個問題做預(yù)處理，本算法采取按照物品收益率做降序排序，顯然此排序的時間復(fù)雜度為O（n2），且作為預(yù)處理只需運行一次，不影響迭代運算的時間復(fù)雜度。

為了獲得足夠的多樣性，初始種群為隨機產(chǎn)生，初始種群的大小設(shè)為N=100。每個初始的可行解是這樣構(gòu)造的，隨機選擇一個變量，如果該解是可行的，將該變量置為1，直到選中的變量不能加入到解中。

3 仿真實驗

采用C++編程給出了BEB-BDA算法和GA-BDA算法的性能仿真，其中仿真參數(shù)設(shè)定為：P2P系統(tǒng)中Peer節(jié)點總數(shù)M為300 000個，視頻文件總數(shù)為F為100，視頻文件編碼率為300 kbps、400 kbps和500 kbps的視頻文件分別占30%、30%和40%。視頻播放時長均為4 800 s，Peer節(jié)點平均上傳帶寬為512 kbps，CDN服務(wù)器的服務(wù)帶寬B為100 Mbps，Peer節(jié)點進(jìn)入系統(tǒng)的到達(dá)率為λ為20個/s，并且開始點播。將文件的訪問熱度按照降序進(jìn)行排列，第i個文件ID為i。

Peer節(jié)點按概率δi選中所點播的視頻文件fi，，α=可視為Peer節(jié)點上傳帶寬的期望值，本文取值為0.7。

以服務(wù)器盡力服務(wù)的帶寬分配算法（BEB-BDA）與本文提出的GA-BDA算法進(jìn)行比較，仿真結(jié)果為重復(fù)試驗10次之后的平均值。

圖1為GA-BDA算法和BEB-BDA算法對全局服務(wù)容納率的比較。從圖1可以看出，在時間刻度t=7時，GA-BDA算法的全局服務(wù)容納率達(dá)到了9.8。與BEB-BDA算法相比較，GA-BDA算法提高了P2P系統(tǒng)服務(wù)請求接受能力。對于BEB-BDA分配算法，由于其不考慮不同冷熱度視頻文件的訪問對P2P系統(tǒng)總體服務(wù)能力的影響，具有較高訪問熱度的文件由于其對應(yīng)的服務(wù)容量不能快速增加，導(dǎo)致在初始時間刻度t上保持較低的全局服務(wù)容納率并且增長速度較慢，在t=15時才達(dá)到最大的值。從仿真結(jié)果可知，GA-BDA算法根據(jù)不同視頻文件熱度的帶寬分配方法可快速增加系統(tǒng)的總體服務(wù)能力。

4 結(jié)語

在深入分析混合框架點播系統(tǒng)服務(wù)容量模型的基礎(chǔ)上，通過利用遺傳算法的尋優(yōu)特性，設(shè)計了適用于P2P系統(tǒng)服務(wù)器帶寬分配問題的遺傳編碼方案和遺傳算子，提出了基于遺傳算法的帶寬分配算法（GA-BDA），該算法能夠提高系統(tǒng)全局容納率。對于點播熱度不同的節(jié)目，該算法克服了服務(wù)器負(fù)載和網(wǎng)絡(luò)帶寬需求瓶頸等問題。通過仿真實驗對不同訪問熱度模式下多文件P2P系統(tǒng)全局請求服務(wù)容納率進(jìn)行了對比試驗，實驗結(jié)果表明與BEB-BDA算法相比較，GA-BDA算法可快速提高系統(tǒng)服務(wù)容量，并且該算法簡單、運行可靠，可以增強P2P系統(tǒng)的服務(wù)能力。

[參考文獻(xiàn)]

[1]BANERJEE S，KOMMAREDDY C，KAR K，et al. Construction of an efficient overlay multicast infrastructure for real-time applications[J].Proceedings of IEEE Infocom Apr，2003（3）：1521-1531.

[2]K SELGUK CANDAN，YUSUF AKCA，AND WEN SYAN LI .An architecture for internet content distribution as an infrastructure service[J].Web Content Delivery，2017（10）：215-216.

[3]XU D，CHAI H K，ROSENBERG C，et al. Analysis of a hybrid architecture for cost-effective streaming media distribution[C].Electronic Imaging，2003.

[4]段翰聰，盧顯良.P2P流媒體分發(fā)技術(shù)研究[D].成都：電子科技大學(xué)，2007.