面向流媒體基于蟻群的副本選擇算法①

楊 戈,劉智鵬

(北京大學(xué)深圳研究生院,深圳物聯(lián)網(wǎng)智能感知技術(shù)工程實驗室,深圳 518055)

1 引言

流媒體網(wǎng)站的注冊用戶自2008年起連續(xù)不斷地增加,從2009年到2017年,中國的流媒體用戶數(shù)量一直以15%-20%的速率不斷增加,固然在用戶規(guī)模的增加速率在近幾年有所放緩,但是用戶規(guī)模依然平穩(wěn)上升.

如今的網(wǎng)絡(luò)上網(wǎng)絡(luò)傳輸?shù)姆绞接泻芏喾N,但是多半是以C/S模式還有P2P模式,C/S模式是由兩個機器組成的,一個為服務(wù)器,另外一個是用戶端.他們之間相互發(fā)送數(shù)據(jù),C/S模式有一個致命的缺點就是要求服務(wù)器的集群性能非常高,這個缺點隨著人戶基數(shù)的增加,越明顯的表現(xiàn)出來.

P2P模式是可以通過直接互換來獲取本身所須要的資源,在對等網(wǎng)絡(luò)里每一臺主機都是同等的,都可以信息共享,即充任用戶機也可以充任服務(wù)器.較原來所有的C/S模型效率提升很多,提高了可靠性與可用性,但是如果在用戶數(shù)量不多的前提下,P2P模式下觀看的流媒體,不會因為傳輸數(shù)率而影響到了用戶的觀看的感受.但是如果人數(shù)迅速增加或者在達到一定數(shù)量時,其服務(wù)質(zhì)量則難以保證.在P2P模式中,用戶數(shù)量不斷增長,流媒體的系統(tǒng)會變得難以管理.

本文將引入一種新的儲存方式Cloud-P2P來解決流媒體文件的儲存問題,Cloud-P2P的儲存結(jié)構(gòu)是一種比較新的儲存方式,它將與傳統(tǒng)傳輸模式P2P,和現(xiàn)代較新的技術(shù)云計算相結(jié)合起來,將云計算上的優(yōu)點與P2P上的優(yōu)點相結(jié)合.Cloud-P2P儲存方式是通過云服務(wù)中心和P2P儲存節(jié)點組成的.

由于在云環(huán)境下的流媒體的副本數(shù)量很大,且不同的副本選擇,會導(dǎo)致副本所在虛擬服務(wù)器的負載不同,一個號的副本選擇策略會使虛擬服務(wù)器的負載達到一個比較理想的值,所以本文提出基于蟻群算法的Cloud-P2P副本選擇算法(C2P2RSA2),來對副本進行選擇.

2 相關(guān)工作

2.1 Cloud-P2P

文獻[1]中Cloud-P2P儲存結(jié)構(gòu)是由云服務(wù)中心和P2P儲存節(jié)點組成的,云服務(wù)中心利用流媒體的提供商的眾多服務(wù)器組成,利用多個物理服務(wù)器,通過云計算平臺整合成一個大的資源池,在從資源池里虛擬出多個虛擬服務(wù)器,在每個不同時間里,用戶的請求量是不同的,在一些不繁忙的時間段,虛擬服務(wù)器可以從資源池里獲取少量的資源,就能夠滿足響應(yīng)用戶的請求.在一些繁忙時間段里,有大量的用戶請求,虛擬服務(wù)器可以從資源池里調(diào)度大量的資源,使得短時間內(nèi)虛擬服務(wù)器的處理能力大大的提升,快速響應(yīng)用戶的請求.虛擬服務(wù)器不僅可以為用戶提供服務(wù),而且還能管理P2P里的儲存節(jié)點,查看節(jié)點的在線情況以及監(jiān)控節(jié)點的負載等等的信息.

用戶端的程序可以充當(dāng)P2P節(jié)點,多個P2P節(jié)點就能組成一個很大的儲存空間,如果服務(wù)器發(fā)生了故障,在儲存空間上的數(shù)據(jù)也能維持給用戶使用,并且儲存節(jié)點上的可以修復(fù)服務(wù)器.

現(xiàn)在的云存儲系統(tǒng)結(jié)構(gòu)主要是(Master/Slave)結(jié)構(gòu)的GFS、HDFS,文獻[2]提出一種對等云結(jié)構(gòu)的云存儲系統(tǒng)Ming Cloud,并且通過構(gòu)建原型系統(tǒng),使Ming Cloud能實現(xiàn)數(shù)據(jù)的存儲、讀取、刪除、搜索等功能.

2.2 副本選擇算法

在流媒體系統(tǒng)中,要想用戶獲得較好的觀看質(zhì)量,系統(tǒng)會復(fù)制多份副本出來,在眾多的副本中,哪一個副本適合用戶,使用戶獲得較好的觀看質(zhì)量,這個就是副本選擇的問題,在某些情況下并非副本響應(yīng)時間最短就是最佳的副本節(jié)點,還要看用戶使用的需求,所以提出QoS偏好感知的副本選擇策略,即QOS的優(yōu)化.還有一些仿生的算法如粒子群算法、遺傳算法等等.

文獻[3]提出了在某些情況下并非副本響應(yīng)時間最短就是最佳的副本節(jié)點,還要看用戶使用的需求,所以提出QoS偏好感知的副本選擇策略,即QOS的優(yōu)化.

文獻[4]資源的合理配置能有效地提高非結(jié)構(gòu)化P2P網(wǎng)絡(luò)的查詢性能,提高資源的可用性.目前的研究報告的副本,資源多集中在各類定量分析的副本和分布式資源分配策略的配置,節(jié)點獨立地選擇資源配置,沒有考慮P2P網(wǎng)絡(luò)節(jié)點配置的節(jié)點之間的相互作用僅保持連接數(shù)和鄰居節(jié)點,掌握該本地信息,所以在交互過程可視為有限理性節(jié)點.在查詢性能分析和資源分配節(jié)點基于結(jié)構(gòu)查詢節(jié)點性能相關(guān)的收益函數(shù)的關(guān)系節(jié)點,資源分配問題轉(zhuǎn)化為一個進化的博弈,可以在資源配置過程中的節(jié)點和查詢性能的有效互動分析可以通過進化的方法得到說明.仿實驗結(jié)果表明,資源配置模式可以獲得更高的查詢成功率和最優(yōu)跳數(shù)的平均數(shù),并保持相對較低的冗余.

文獻[5]提出根據(jù)數(shù)據(jù)節(jié)點和網(wǎng)絡(luò)鏈路的可靠性因子分析,云存儲系統(tǒng)的一個數(shù)據(jù)副本服務(wù)可靠性模型.根據(jù)訪問的可靠性和數(shù)據(jù)之間的副本數(shù)量,用戶訪問,設(shè)計的數(shù)據(jù)業(yè)務(wù)的可靠性,復(fù)制產(chǎn)生時間和存儲節(jié)點選擇方法來確定副本分布和刪除算法,并在云存儲系統(tǒng)的ERS-Cloud進行了一系列的實驗.結(jié)果表明,可以有效地保護數(shù)據(jù)服務(wù)的可靠性的方法,進一步降低冗余存儲的份數(shù).

文獻[6]提出了在無線網(wǎng)絡(luò),由于無線網(wǎng)絡(luò)的不穩(wěn)定性,導(dǎo)致流媒體的傳輸受到影響,所以有一種基于跨層碼率適配和差錯控制的流媒體無線傳輸方法.文獻[7]提出了隨著云計算的普及使用,很多的數(shù)據(jù)都使用云存儲技術(shù),將數(shù)據(jù)或者副本上傳到云上,所以如何在云存儲環(huán)境下進行對副本的選擇也成為了人們研究的一個方向,通過優(yōu)化后的粒子群算法,對副本進行選擇.

2.3 蟻群算法

在1992年的時候,Dorigo和Maniezzo第一次提出了蟻群算法(Ant Colony Optimization,ACO).在1997年的時候,Dorigo提出了精英策略的蟻群算法(Ant System with elitist strategy,ASelitist).在1997年的時候X Bullnheimer B和Hartl RF提出了基于排序的蟻群算法(Ant System based in rank,ASrank).在2000年的時候,Stutzle T和Hoos HH提出了最小最大蟻群算法(Max-Min Ant System,MMAS).

文獻[8]提出從仿生角度出發(fā)提出一種全新的網(wǎng)絡(luò)聚類算法——基于隨機游走的蟻群算法RWACO.該算法將蟻群算法的框架作為RWACO的基本框架,對每一代,馬爾可夫隨機游走模型作為啟發(fā)式規(guī)則的基礎(chǔ)上,集成學(xué)習(xí)的思想,螞蟻局部解決方案融入全局解決方案,和更新的信息素矩陣.通過加強內(nèi)部集群連接,削弱了跨集群連接“這一進化策略,逐漸顯現(xiàn)集群網(wǎng)絡(luò)結(jié)構(gòu),實驗結(jié)果表明,對一些典型的計算機生成網(wǎng)絡(luò)和真實網(wǎng)絡(luò),該算法能夠準(zhǔn)確地探索網(wǎng)絡(luò)來衡量的真實數(shù)量集群,與一些有代表性的算法具有較高的聚類準(zhǔn)確率比[9,10].

如今很多的數(shù)據(jù)副本等都放置在云上,所以在云上如何對副本你的選擇也成為了一個問題,文獻[11]提出了一種基于云儲存的副本選擇算法(Pheromone-base Ant colony Replica adaptive Selection Algorithm in cloud storage,PARSA).PARSA算法是對存儲在云上的副本進行選擇的,如果使用此算法在Cloud-P2P的儲存上,由于云副本節(jié)點由于處于一個比較良好的網(wǎng)絡(luò)環(huán)境下,這樣會造成云副本節(jié)點會被用戶大量的使用,這樣會對服務(wù)提供商增加運營成本[12],所以本文算法對此進行優(yōu)化修改,使優(yōu)化后的算法可以在Cloud-P2P下使用,優(yōu)化過后副本節(jié)點會優(yōu)先使用P2P上的副本節(jié)點,在P2P的副本節(jié)點的負載率到達一定程度時,云副本節(jié)點會被用戶開始使用,使用戶獲得正常的觀看質(zhì)量.

3 C2P2RSA2算法

為了提高用戶觀看流媒體的時候,有流暢的觀看感受和良好的觀看質(zhì)量,服務(wù)提供商會增加副本的數(shù)量,給用戶使用.但在眾多的副本中,找到適合用戶所需要的副本.蟻群算法使一種適合分布式系統(tǒng)的算法,而且蟻群算法擁有正反饋,系統(tǒng)可以根據(jù)反饋不停改變系統(tǒng)的副本,使用戶獲得更好的觀看感受.本文算法優(yōu)化了蟻群算法,會優(yōu)先選擇P2P上的副本節(jié)點,減少云副本節(jié)點的使用,使服務(wù)商的成本降低.

(1)利用初始化公式對其初始化,影響副本的選擇的參數(shù)有很多,例如副本讀取的時間、網(wǎng)絡(luò)的帶寬、網(wǎng)絡(luò)延遲、副本節(jié)點的負載完成率和是否為云副本節(jié)點等等,通過這些參數(shù)利用初始化公式使每個副本都有各自的初始信息素數(shù)值.

信息素數(shù)值: 初始的信息素數(shù)值是通過副本節(jié)點的網(wǎng)絡(luò)環(huán)境進行初始的,并且通過副本節(jié)點網(wǎng)絡(luò)環(huán)境和處理能力進行動態(tài)調(diào)整.

Tdja(e): 表示用戶a到副本j的路徑e的副本節(jié)點的副本讀取時間,某一時刻d的副本讀取時間,記為wd,最大副本的讀取時間為wmax.

delayja(e): 表示用戶a到副本j的路徑e的網(wǎng)絡(luò)延遲,本文中的網(wǎng)絡(luò)延遲是指網(wǎng)絡(luò)跳數(shù),最大網(wǎng)絡(luò)延遲為mmax,最小網(wǎng)絡(luò)延遲為mmin.

bwja(e): 表示用戶a到副本j的路徑e的網(wǎng)絡(luò)帶寬,某時刻d副本路徑的網(wǎng)絡(luò)帶寬記為nd.

lrja(e): 表示用戶a到副本j的路徑e上副本節(jié)點的負載完成率,某時刻d副本節(jié)點的已處理完的副本數(shù)記為yd,副本節(jié)點總的處理任務(wù)數(shù)為y0.

式(1)是對副本j進行信息素的初始化,f_size為副本文件的大小,Tdaj(e)為用戶a到副本j的讀取時間,γj為初始化信息素數(shù)值.

式(2)中為副本j的初始的總信息素數(shù)值,由五個參數(shù)組成的,即:

式(2)中的幾個參數(shù)分別由下列的式(3)、式(4)、式(5)、式(6)中進行初始化得到的.

iscloud: 表示是否為云副本節(jié)點,如果P2P副本節(jié)點的負載率到達一個指定的值,此參數(shù)會將云副本節(jié)點的信息素濃度增高,使用戶可以使用云副本節(jié)點,不會使用戶觀看的質(zhì)量下降.

(2)利用式(7)計算副本選擇概率:

τj(t): 表示在t時刻,副本j的信息素濃度.

?j: 表示副本j初始的信息素數(shù)值.

α、β: 分別表示在t時刻,信息素濃度的重要性以及副本初始信息素數(shù)值的重要性.

(3)信息素更新,式(8)是副本被成功選擇或者選擇失敗是,信息素都會改變的,這是就會通過該式進行修改.式(9)是當(dāng)副本被選出來的時候,對副本的信息素濃度進行更新

τj: 表示為信息素的改變量;

ρ: 表示信息素的殘留系數(shù);

φ: 表示為擴大系數(shù),如果有適合的副本的時候,該系數(shù)可以使信息素快速的增加.

圖1中為算法的流程圖,下面是算法的流程:

(1)對每個副本節(jié)點進行第一次的信息素濃度初始化,可以依據(jù)初始化信息素公式.

(2)依據(jù)概率公式對每個副本節(jié)點的選擇概率進行計算.

(3)利用概率匹配的原則,選出副本節(jié)點.

(4)經(jīng)過一輪選擇以后,一些被螞蟻選出來的副本,利用獎勵公式將其的副本信息素濃度進行更新,一些沒有被選擇到的副本節(jié)點,則使用懲罰公式將其副本信息素濃度進行更新.

(5)依據(jù)終止條件,如果符合了條件,就輸出副本選擇的結(jié)果,如果不滿足的,則重新回到步驟(2)繼續(xù)下一輪的迭代.

4 實驗結(jié)果及分析

本次實驗所使用的仿真環(huán)境如表1,利用Visual Studio 2012 Ultimate對仿真環(huán)境的生成,并且對實驗中要生成的多個副本節(jié)點中的副本讀取的時間、網(wǎng)絡(luò)延遲、網(wǎng)絡(luò)帶寬都是隨機產(chǎn)生的,隨機數(shù)服從均勻分布,均勻分布是指在范圍內(nèi)的數(shù)字出現(xiàn)的機率相等.

圖1 C2P2RSA2算法流程

表1 仿真實驗的軟硬件參數(shù)

副本讀取時間的取值范圍: 10-120 M/s;網(wǎng)絡(luò)延遲的范圍(網(wǎng)絡(luò)跳數(shù)的范圍): 1-255;網(wǎng)絡(luò)帶寬的范圍:1-100 M.

利用以上隨機生成的數(shù)據(jù)生成出副本節(jié)點來,可以模擬出現(xiàn)實環(huán)境中的不同網(wǎng)絡(luò)環(huán)境的副本節(jié)點[1].

本實驗從選擇Cloud-P2P網(wǎng)絡(luò)中副本節(jié)點的平均訪問時間進行了分析,通過與最佳副本選擇算法[1]與PARSA算法進行比較,得出了結(jié)論,證明了本文的C2P2RSA2算法的可行性和優(yōu)點,本文利用平均訪問時間、云副本節(jié)點的負載率作為評價的標(biāo)準(zhǔn),每個實驗重復(fù)做3次,取平均值.

平均訪問時間: 是指每個用戶從提出請求開始,副本節(jié)點響應(yīng),傳輸給用戶,并且用戶完全接受后,總共的時長.

云副本節(jié)點的負載率: 云副本節(jié)點上的平均資源的使用率.

圖2為當(dāng)副本節(jié)點有10個的時候,本文算法與PARSA算法和最佳副本選擇算法的平均訪問時間的對比,由圖上可以看到當(dāng)副本節(jié)點少的時候,三種算法的平均訪問時間都差不多,但總體本文算法比最佳副本選擇算法少,但是比PARSA算法多2.1%.

圖2 副本節(jié)點為10的平均訪問時間對比圖

圖3為當(dāng)副本節(jié)點的數(shù)量為20的時候,本文算法與PARSA算法和最佳副本選擇算法的平均訪問時間的對比,由圖上可以看到當(dāng)副本節(jié)點增加了后,最佳副本選擇算法與本文算法和PARSA算法的平均訪問時間差別開始增大,本文算法比最佳副本選擇算法少,但是比PARSA算法多4.3%.

圖4為副本的平均訪問時間的對比,剛開始由于副本數(shù)量不多,所以平均訪問時間都差不多,隨著副本的數(shù)量增加,差距開始增大,由圖上可以看到最佳副本選擇算法比本文算法C2P2RSA2與PARSA的平均訪問時間都要多,C2P2RSA2與PARSA相比,前者比后者的平均訪問時間增加2%-5%.

圖3 副本節(jié)點為20的平均訪問時間對比圖

圖4 副本平均訪問時間對比

圖5為本文的 C2P2RSA2算法與PARSA、最佳副本選擇算法的云副本節(jié)點的負載率對照圖,本文設(shè)置的云副本節(jié)點為5個節(jié)點,較少的云副本節(jié)點當(dāng)用戶選擇的副本不是云副本節(jié)點的時候,可以從云副本平均負載率快速反映出來,固定云副本節(jié)點數(shù)量,可以通過改變P2P副本節(jié)點的數(shù)量,可以觀察出不同的算法的云副本負載率不一樣,剛開始由于沒有P2P的副本節(jié)點,所以所有的副本都有云副本節(jié)點來提供,隨著P2P上的副本節(jié)點增加,因為最佳副本選擇算法沒有動態(tài)調(diào)整的機制,所以云副本負載率沒有降低,而PARSA算法通過動態(tài)調(diào)整,使云副本節(jié)點的負載率有微小降低,但由于云副本節(jié)點的網(wǎng)絡(luò)環(huán)境方面都很好,所以在用戶選擇副本的時候,還是會對云副本節(jié)點進行優(yōu)先選擇,而本文的 C2P2RSA2有動態(tài)調(diào)整機制,并且會對P2P副本節(jié)點進行優(yōu)先選擇,所以當(dāng)副本節(jié)點開始增加的時候,云副本節(jié)點的負載率降低,并且隨著P2P副本節(jié)點的數(shù)量增加而逐漸下降.

通過圖2至圖5上的數(shù)據(jù)可知,本文 C2P2RSA2算法的平均訪問時間小于最佳副本選擇算法,最佳副本選擇算法也是通過結(jié)合了網(wǎng)絡(luò)延遲、網(wǎng)絡(luò)帶寬、副本節(jié)點的可靠性等計算出最小代價副本,而本文的C2P2RSA2算法則是根據(jù)副本節(jié)點的副本讀取時間、網(wǎng)絡(luò)延遲、網(wǎng)絡(luò)帶寬、服務(wù)器的負載率等因素綜合起來,而且不斷動態(tài)調(diào)整,然后對副本進行選擇的,所以通過實驗證明了本文的 C2P2RSA2算法優(yōu)于最佳副本選擇算法,本文的 C2P2RSA2算法能在平均訪問時間上與PARSA算法上的時間相差2%-5%,但是在負載率上可以看到,本文的 C2P2RSA2算法能降低云副本的負載率15%-25%,提高P2P副本節(jié)點的負載率,優(yōu)先對P2P副本節(jié)點進行使用,降低云副本節(jié)點的負載率.

圖5 云副本節(jié)點的負載率對比

5 總結(jié)

為了能滿足人們可以觀看流媒體,本文使用的Cloud-P2P的存儲模式是通過云中心與P2P節(jié)點進行結(jié)合,使用云的靈活性、按需付費的特性與P2P的可擴展性相結(jié)合.為了能對Cloud-P2P的存儲模式進行副本選擇,本文提出了基于蟻群算法的C2P2RSA2.客戶使用本算法進行對副本選擇的時候,優(yōu)先使用P2P副本節(jié)點,對云副本節(jié)點的負載率降低,在云副本節(jié)點的負載率降低到一定程度可以減少云副本的節(jié)點,在P2P副本節(jié)點不能使新的用戶正常使用的時候,可以增加云副本節(jié)點使用戶的觀看質(zhì)量不會下降,通過云計算的靈活性可以做到這一點.在后續(xù)的工作中,由于蟻群算法要經(jīng)過多次迭代才能獲得最優(yōu)的結(jié)果,這樣計算速度很慢,下一步工作可以對迭代次數(shù)進行優(yōu)化,減少迭代次數(shù),能快速獲得最優(yōu)結(jié)果,并且在云副本節(jié)點的負載率降低到一定程度的時候,對云副本節(jié)點進行選擇性的減少,減少云上的開銷.