黃洪濤,武繼剛,鄭露露,繆裕青
(1.廣東工業(yè)大學計算機學院,廣東廣州510006;2.桂林電子科技大學廣西高校圖像圖形智能處理重點實驗室,廣西桂林541004)
隨著移動互聯(lián)網(wǎng)的飛速發(fā)展,移動網(wǎng)絡(luò)對多媒體業(yè)務(wù)的需求大幅增加,從而導(dǎo)致網(wǎng)絡(luò)流量爆炸式增長。然而,傳統(tǒng)的架構(gòu)和移動網(wǎng)絡(luò)的容量無法保證網(wǎng)絡(luò)服務(wù)質(zhì)量,移動設(shè)備數(shù)量的激增導(dǎo)致帶寬消耗過大,容易產(chǎn)生網(wǎng)絡(luò)瓶頸,影響移動用戶的訪問體驗質(zhì)量[1]。在網(wǎng)絡(luò)流量以超摩爾定律增長的情況下,不僅需要提升單個節(jié)點的性能,而且還要從網(wǎng)絡(luò)架構(gòu)的角度優(yōu)化網(wǎng)絡(luò)拓撲。在這種背景下,產(chǎn)生了移動內(nèi)容分發(fā)網(wǎng)絡(luò)mCDN(mobile Content Distribution Network)。
雖然有關(guān)內(nèi)容分發(fā)網(wǎng)絡(luò)的研究很多,但mCDN的研究相當有限[2]。與傳統(tǒng)內(nèi)容分發(fā)網(wǎng)絡(luò)不同,mCDN網(wǎng)絡(luò)設(shè)施由有線網(wǎng)絡(luò)設(shè)施和無線網(wǎng)絡(luò)設(shè)施組成。其中,有線網(wǎng)絡(luò)設(shè)施是mCDN的骨干網(wǎng)絡(luò),負責源服務(wù)器與代理緩存服務(wù)器之間的連接以及代理緩存服務(wù)器與網(wǎng)絡(luò)組件之間的連接,網(wǎng)絡(luò)組件包括路由器、交換機、蜂窩基站BS(Base Stations)、Wi-Fi接入點 AP(Access Points)等[3]。無線網(wǎng)絡(luò)設(shè)施負責移動設(shè)備的通信和內(nèi)容分發(fā),以減輕骨干網(wǎng)絡(luò)的傳輸壓力。
本文研究的是集中式無線網(wǎng)絡(luò)設(shè)施下的mCDN。蜂窩網(wǎng)絡(luò)和Wi-Fi網(wǎng)絡(luò)是兩個典型的集中式無線網(wǎng)絡(luò)設(shè)施[4]。對于無線內(nèi)容分發(fā)網(wǎng)絡(luò),如果多個用戶從基站端獲取相同的內(nèi)容,則可能浪費大量不必要的帶寬和能量。因此,可將內(nèi)容分發(fā)問題視為最小生成樹問題,把無線內(nèi)容分發(fā)網(wǎng)絡(luò)拓撲結(jié)構(gòu)構(gòu)建成以BS和AP為根的若干棵最小生成樹,由于移動設(shè)備的存儲能力、計算能力和電源續(xù)航能力有限,需要限制生成樹的深度和每個節(jié)點的最大度,使網(wǎng)絡(luò)拓撲呈扁平化。
目前,研究主要集中于兩類約束最小生成樹問題。第一類問題是度數(shù)約束最小生成樹問題,其要求樹中的任意節(jié)點的度數(shù)不超過某一閾值。文獻[5]證明了該問題是NP難問題。求解這種問題的算法可以歸納為三類:(1)近似算法,如文獻[6]提出了一種基于拉格朗日二次性的近似算法;(2)啟發(fā)式算法,如文獻[7]提出了可變鄰域搜索的啟發(fā)式算法;(3)智能優(yōu)化算法,如遺傳算法[8]。第二類問題是直徑約束的最小生成樹BDMST(Bounded-Diameter Minimum Spanning Tree)問題,該問題要求在給定的圖中尋找滿足直徑約束的最小生成樹。當直徑約束不小于4且小于該最小生成樹的邊數(shù)時,此問題屬于NP難問題[5]。相比求解度數(shù)約束最小生成樹問題,目前的研究較少涉及求解直徑約束最小生成樹問題。求解這類問題的算法也可以分為三類:(1)精確算法,適用于小規(guī)模問題,如文獻[9]提出的基于0-1整數(shù)規(guī)劃的分支定界法;(2)快速算法[10],適用于大規(guī)模問題;(3)遺傳算法,比較典型的有基于邊集編碼的遺傳算法[11]和基于序列編碼的遺傳算法[12]。其中,深度限制最小生成樹是直徑受限最小生成樹問題的特殊情況,要求任何根節(jié)點到葉子節(jié)點的長度不超過給定的閾值。
無線內(nèi)容分發(fā)網(wǎng)絡(luò)的樹形拓撲結(jié)構(gòu)需要同時滿足度數(shù)約束以及深度限制,以上概述的兩種約束最小生成樹不適用于無線網(wǎng)絡(luò)環(huán)境。深度和度數(shù)約束最小生成樹DCBDMST(Depth Constrained Bounded Degree Minimum Spanning Tree)問題屬于NP完全問題[13]。文獻[13]首次研究了此問題,提出了基于克魯斯卡爾策略的深度和度數(shù)約束最小生成樹算法,該算法的局限是一次僅能生成一棵深度和度數(shù)約束的最小生成樹,不適用于網(wǎng)絡(luò)拓撲結(jié)構(gòu)。
本文的主要貢獻如下:
(1)提出了求解DCBDMST問題的啟發(fā)式算法,用于生成初始近似解。此算法將BS和AP作為根節(jié)點加入當前生成樹;從當前生成樹不違背深度以及度數(shù)約束的節(jié)點中,選擇與服務(wù)性節(jié)點相連并且權(quán)值最小的節(jié)點,將該服務(wù)性節(jié)點加入當前樹;直到所有服務(wù)性節(jié)點都加入了當前樹,形成以BS和AP為根的若干棵生成樹。
(2)采用定制的禁忌搜索算法和模擬退火算法優(yōu)化啟發(fā)式算法產(chǎn)生的初始近似解,并改進文獻[12]的基于BDMST問題的遺傳算法使之適用于DCBDMST問題。
(3)本文提出的啟發(fā)式算法、禁忌搜索算法、模擬退火算法和遺傳算法均能一次生成多棵深度和度數(shù)約束的最小生成樹,而現(xiàn)有相關(guān)算法僅能生成一棵生成樹。
(4)實驗結(jié)果表明,本文提出的禁忌搜索算法在解的質(zhì)量和運行速度方面均優(yōu)于文獻[12]的遺傳算法。在深度約束為4以及度數(shù)約束為10的條件下,解的質(zhì)量可提高18.5%,所提算法的運行速度與遺傳算法相比提高了10倍。
在本文中,假設(shè)在動態(tài)無線網(wǎng)絡(luò)環(huán)境中所有移動設(shè)備的請求內(nèi)容是一致的,因而移動設(shè)備從內(nèi)容服務(wù)器接收的數(shù)據(jù)流是相同的。圖1展示了一個集中式無線網(wǎng)絡(luò)設(shè)施的架構(gòu),由網(wǎng)絡(luò)運營商或內(nèi)容服務(wù)提供商管理的內(nèi)容服務(wù)器負責定期收集用戶設(shè)備的狀態(tài)信息,執(zhí)行內(nèi)容分發(fā)算法,以及通過BS和AP協(xié)調(diào)設(shè)備的角色和傳送內(nèi)容,智能地選擇設(shè)備作為服務(wù)性節(jié)點,其中移動設(shè)備的角色分為服務(wù)性節(jié)點和非服務(wù)性節(jié)點。首先BS和AP將遠程通信鏈路上的內(nèi)容發(fā)送到服務(wù)性節(jié)點;然后每個服務(wù)性節(jié)點使用無線技術(shù)(Wi-Fi Direct或藍牙)將所接收的內(nèi)容轉(zhuǎn)發(fā)到屬于其集群的非服務(wù)性節(jié)點。
如圖1所示的網(wǎng)絡(luò)架構(gòu)確保每個設(shè)備和內(nèi)容服務(wù)器之間存在路由,因此可以使用內(nèi)容分發(fā)樹來表示無線內(nèi)容分發(fā)網(wǎng)絡(luò)。由于本文希望最小化將內(nèi)容傳遞到網(wǎng)絡(luò)中的每個移動設(shè)備所需的成本,成本越小網(wǎng)絡(luò)服務(wù)質(zhì)量就越高,所以與最小生成樹的構(gòu)建方法是相關(guān)的。生成樹中任意節(jié)點的度數(shù)對應(yīng)于相鄰設(shè)備的數(shù)量,大的集群能夠使服務(wù)性節(jié)點過快地消耗電量,從而導(dǎo)致內(nèi)容分發(fā)中斷。因此,需要限制節(jié)點的度數(shù)。生成樹的深度表示葉節(jié)點至BS和AP的最大跳數(shù),跳數(shù)越長,從內(nèi)容服務(wù)器接收數(shù)據(jù)流的延遲越大,所以需要相對嚴格的深度約束。
無向賦權(quán)圖G=(V,E,W)表示網(wǎng)絡(luò),其中,V表示圖的頂點集,E表示圖的邊集,W表示圖的權(quán)值集。設(shè)當前生成樹為S,SV;設(shè)T為圖G的滿足度數(shù)以及深度約束的一棵生成樹的邊集,并使對應(yīng)邊權(quán)重Wij之和為最小值。DT為T中各個節(jié)點的度數(shù),PT為當前生成樹的深度。DCBDMST的數(shù)學模型可描述如下:
上述數(shù)學模型由 DCBDMST問題的優(yōu)化目標函數(shù)及約束條件構(gòu)成,其中:第1個約束為生成樹包含不同節(jié)點的n-1條邊;第2個約束表示當前生成樹無環(huán)路;第3個約束當xij=1時,節(jié)點vi、vj構(gòu)成的邊是生成樹的一條邊,若xij=0,表示該邊未被選中;第4個約束為每個節(jié)點應(yīng)滿足的度數(shù)約束條件,D為給定的度數(shù)約束;第5個約束為每個節(jié)點應(yīng)滿足的深度約束條件,P為給定的深度限制;深度約束是直徑約束的特殊情況,其中生成樹的深度定義為從該節(jié)點到根節(jié)點的最短路徑的長度。
針對在一個給定的圖中生成多棵DCBDMST的問題,本節(jié)提出了啟發(fā)式算法GREEDY來尋找一個優(yōu)質(zhì)近似解。算法GREEDY的基本思想是:首先選擇BS和AP作為根節(jié)點,加入當前生成樹中;然后循環(huán)以下過程:在剩余服務(wù)性節(jié)點中隨機選擇一個節(jié)點v,從當前生成樹不違背深度以及度數(shù)約束的節(jié)點中,選擇與節(jié)點v相連的邊權(quán)值最小的節(jié)點u,將節(jié)點v加入當前生成樹;直到服務(wù)性節(jié)點全部加入當前生成樹,則循環(huán)結(jié)束。輸出以BS和AP為根的若干棵深度和度數(shù)約束最小生成樹。該算法確保所有移動設(shè)備之間的連接都在假定的短距離無線技術(shù)的無線電范圍內(nèi)。算法的形式化描述如算法1所示。
算法1算法GREEDY
輸入:由BS、AP和服務(wù)性節(jié)點組成的圖G,G=(B∪C,(B×C)∪(C ×C),W)。
輸出:圖G的若干棵深度和度數(shù)約束最小生成樹的邊集τ,以及權(quán)值w。
1.Begin
在算法GREEDY的形式化描述中,節(jié)點集合B表示若干的BS和AP,節(jié)點集合C表示一定數(shù)量的服務(wù)性設(shè)備,權(quán)值集合W表示節(jié)點間的距離,行2的集合U表示當前可供連接的節(jié)點。假設(shè)圖G中含有n個節(jié)點,其中m個節(jié)點是BS和AP,剩余n-m個節(jié)點為服務(wù)性設(shè)備。該算法的主要計算量是查找滿足約束條件的最小值,該步驟的時間復(fù)雜度在最壞情況下為O(n),因為這一步需要執(zhí)行n-m次,所以算法GREEDY的時間復(fù)雜度為O(n2)。
給定無向賦權(quán)圖G,所提算法GREEDY能高效地找到圖G的多棵DCBDMST的較好近似解。算法GREEDY產(chǎn)生的初始解將作為禁忌搜索算法和模擬退火算法的輸入。
禁忌搜索TS(Tabu Search)算法是一種全局逐步尋優(yōu)算法。其求解的過程是從一個初始可行解出發(fā),然后采用鄰域選優(yōu)的方法,在搜索過程中將近期的歷史上的搜索過程存放在禁忌表中,只有不在禁忌表中的較好解,才被接受作為下一次迭代的初始解;使用禁忌表來封鎖剛搜索過的區(qū)域,以避免迂回搜索,同時赦免禁忌表中的一些優(yōu)良狀態(tài),進而保證搜索的多樣性,從而達到全局優(yōu)化[14]。
首先使用前節(jié)所述的算法GREEDY尋找一個較好的初始解。然后在TS算法的初始階段,采用序列編碼的方法對狀態(tài)進行表示。序列編碼是指用n位自然數(shù)唯一地表達出含有n個節(jié)點的生成樹,其中每個數(shù)字在1和n之間。例如,用(1,2,…,n)的一個排列來表示一個狀態(tài),即它的編碼方式。
在生成若干棵DCBDMST的問題中,目標函數(shù)值為解碼樹的權(quán)值。解碼是基因型到表現(xiàn)型的映射,具體而言就是排列到生成樹的映射。解碼方式是類似于算法GREEDY的一個執(zhí)行過程,略微有所不同的是不在待選節(jié)點集合中隨機選擇節(jié)點,而是按照排列的順序逐個選擇節(jié)點。按照排列的順序依次選擇節(jié)點加入當前生成樹。
在TS算法中,每一次的搜索都是基于當前解的候選解集。在本文中候選解集為領(lǐng)域的真子集,即只掃描領(lǐng)域的一部分來構(gòu)成候選解集。領(lǐng)域是一種移動操作,移動是從當前解產(chǎn)生新解的途徑,從當前解可以進行的所有移動構(gòu)成領(lǐng)域。在本文中采用任意交換兩個位置的移動規(guī)則來產(chǎn)生當前解的領(lǐng)域解,將當前狀態(tài)作為禁忌表中的禁忌對象。根據(jù)渴望水平來評價當前解的候選解集,目標函數(shù)值越小,表示候選解的質(zhì)量越好。如果某個候選解的目標函數(shù)值優(yōu)于歷史最優(yōu)值,那么無論這個候選解是否處于被禁忌狀態(tài),都會被接受,并更新當前解和歷史最優(yōu)解,給定最大迭代步數(shù)作為停止準則,用于停止搜索。
使用TS算法生成多棵DCBDMST的算法流程圖如圖2所示。
模擬退火SA(Simulated Annealing)算法是一種隨機搜索算法,它模擬了物理退火過程,從一個給定的初始高溫開始,利用Metropolis準則進行隨機搜索,隨著溫度的緩慢下降循環(huán)抽樣過程,當溫度足夠低時得到問題的全局最優(yōu)解[15]。
使用SA算法對生成多棵DCBDMST問題進行求解的設(shè)計如下所示:
(1)為了加快 SA算法的收斂,使用算法GREEDY產(chǎn)生一個優(yōu)質(zhì)的初始解,使用序列編碼的方式來表達狀態(tài),目標函數(shù)值是解碼樹的權(quán)值。
(2)與TS算法相同,SA算法也是基于領(lǐng)域搜索的,SA算法修改當前解的狀態(tài)的方法與TS算法相同。所不同的是SA算法采用了一種特殊的Metropolis準則的領(lǐng)域移動方法,領(lǐng)域移動分為無條件移動和有條件移動。如果新解的目標函數(shù)值小于當前解的目標函數(shù)值,則進行無條件移動;否則,根據(jù)一定的概率進行有條件移動。
(3)SA算法為了保證能夠到達平衡狀態(tài),在每一溫度,內(nèi)循環(huán)次數(shù)要足夠大且迭代相同的次數(shù),內(nèi)循環(huán)次數(shù)設(shè)置為一個常數(shù)。滿足內(nèi)循環(huán)次數(shù)后,SA算法降低一個溫度進入外循環(huán)過程。溫度的下降由降溫函數(shù)來控制。由于溫度的大小決定著SA算法進行全局搜索還是局部搜索,當溫度很高時,SA算法進行全局搜索;當溫度很低時,SA算法進行局部搜索。如果溫度下降過快則可能過早陷入局部最優(yōu),選擇理想的降溫函數(shù)能夠幫助提高SA算法的性能,本文使用降溫函數(shù)Tn+1=Tn·r,其中降溫系數(shù) r∈(0.95,0.99)。
此外,對模擬退火算法進行兩方面改進。第一點改進是增加記憶功能。為避免搜索過程中由于執(zhí)行概率接受環(huán)節(jié)而遺失當前遇到的最優(yōu)解,可通過增加存儲功能,將歷史最優(yōu)解的狀態(tài)記憶下來。第二點改進是增加重升溫過程。在算法進程的適當時機,將溫度適當提高,從而可激活各狀態(tài)的接受概率,以調(diào)整搜索進程中的當前狀態(tài),避免算法在局部極小解處停滯不前。
使用SA算法生成多棵DCBDMST的算法流程圖如圖3所示。
用本文算法GREEDY構(gòu)造的較好近似解,并用禁忌搜索算法和模擬退火算法對近似解進行優(yōu)化的算法在本文中分別記作GRTS(GREEDY-TS)和GRSA(GREEDY-SA)。本文在文獻[12]的基于BDMST問題的遺傳算法基礎(chǔ)上,改進該算法使之適用于DCBDMST問題,使用改進后的遺傳算法EGA(Improve-GA)與本文提出的算法GRTS和算法GRSA進行比較,以評估所提算法在反映服務(wù)質(zhì)量的網(wǎng)絡(luò)成本方面和反映計算復(fù)雜度的執(zhí)行時間方面的性能。實驗中所涉及的算法均在Intel(R)Core(TM)i7-6700 CPU 3.40 GHz RAM 8 GB 四核的機器上運行。
本文將網(wǎng)絡(luò)成本建模為所有發(fā)射機至接收機之間的距離之和,度量單位為m。因為比特率是通信距離的直接函數(shù),因此最小化基于距離的成本度量可以映射到最大化速率。當節(jié)點的初始數(shù)量n≤64時,假定100×100的網(wǎng)格具有一個基站,當n>64時,512×512的網(wǎng)格具有四個基站。此外,假設(shè)基站無線電范圍為300 m,Wi-Fi無線電范圍為25 m。本文參照文獻[16]按均勻隨機方式產(chǎn)生[1,25]的整數(shù)作為節(jié)點之間的距離。
根據(jù)多次實驗結(jié)果較好的值來設(shè)置算法EGA、GRTS的迭代次數(shù)。如圖4所示,在算法EGA中,種群的規(guī)模為100,交叉算子的交叉率為0.7,變異操作的變異率為 0.001,結(jié)果顯示算法EGA迭代30次趨于收斂;在算法GRTS中,候選解集的大小為12,禁忌表的大小設(shè)置為20,結(jié)果表明算法GRTS迭代40次趨于收斂。在算法GRSA中,初始高溫設(shè)置為100,終止溫度取0.01,降溫比例系數(shù)為0.98。表1是算法 GREEDY、GRSA 、GRTS和EGA的平均網(wǎng)絡(luò)成本和平均運行時間的實驗結(jié)果;表2是上述算法的最低網(wǎng)絡(luò)成本和最佳運行時間的實驗結(jié)果,其中度閾值D分別設(shè)置為6、8、10,深度閾值 P 分別取值為 2、3、4。網(wǎng)絡(luò)成本越小,表示算法求得的解的質(zhì)量越高。
表1展示了20次重復(fù)實驗中獲得的平均網(wǎng)絡(luò)成本(平均解)和平均運行時間。表1表明:當P=3、D=8時,算法GRTS的平均網(wǎng)絡(luò)成本優(yōu)于算法EGA的,平均解的質(zhì)量最大提高了10.3%。當P=3、D=6時,算法GRTS的平均網(wǎng)絡(luò)成本仍優(yōu)于算法EGA的,平均解的質(zhì)量最大提高了11.4%。當P=2、D=10時,算法GRTS的平均網(wǎng)絡(luò)成本持續(xù)優(yōu)于算法EGA的,平均解的質(zhì)量最大提高了10.4%。當P=2、D=10時,算法GRTS的平均網(wǎng)絡(luò)成本始終優(yōu)于算法EGA的,平均解的質(zhì)量最大提高了9.6%。算法GRSA在平均網(wǎng)絡(luò)成本方面略次于算法EGA的。本文所提算法的平均運行時間顯著優(yōu)于算法EGA的,GRTS的平均運行時間至少是EGA的1/10,GRSA的平均運行時間至少是EGA的1/20。
表2展示了在20次實驗中獲得的最低網(wǎng)絡(luò)成本(最優(yōu)解)和最佳運行時間。表2表明:當P=3、D=8時,算法GRTS的最低網(wǎng)絡(luò)成本優(yōu)于算法EGA的,最優(yōu)解的改進幅度最大可達7%。當P=4、D=10時,算法GRTS的最低網(wǎng)絡(luò)成本依然優(yōu)于算法EGA的,最優(yōu)解的改進幅度最大可達18.5%。當P=3、D=6時,算法GRTS的最低網(wǎng)絡(luò)成本繼續(xù)優(yōu)于算法EGA的,最優(yōu)解的改進幅度最大可達7.4%。當P=2、D=10時,算法GRTS的最低網(wǎng)絡(luò)成本始終優(yōu)于算法EGA的,最優(yōu)解的改進幅度最大可達8.9%。算法GRSA在最低網(wǎng)絡(luò)成本方面仍略次于算法EGA。本文所提算法的最佳運行時間明顯優(yōu)于算法EGA的,GRTS的最佳運行時間至少是EGA的1/10,GRSA的最佳運行時間至少是EGA的1/30。
Table 1 Performance comparison among the algorithms in average network cost and average running time表1 算法在平均網(wǎng)絡(luò)成本、平均運行時間上的比較
Table 2 Performance comparison among the algorithms in lowest network cost and best running time表2 算法在最低網(wǎng)絡(luò)成本、最佳運行時間上的比較
實驗結(jié)果表明,本文所提算法GRTS在給定任意約束條件下,與算法EGA相比,均能更好更快地求解。這說明算法GRTS性能是穩(wěn)定的,但是算法GRSA在解的質(zhì)量方面略次于算法EGA。因為算法EGA用隨機初始種群作為遺傳算法的初始解,遺傳算法的精髓是遺傳算子,并不依賴于初始種群的優(yōu)良,廣域搜索能力強;模擬退火算法全局搜索能力略顯不足且初值依賴性較弱;然而本文提出了啟發(fā)式算法能夠為禁忌搜索算法提供優(yōu)質(zhì)的初始解。
綜上,在生成多棵DCBDMST的問題上,算法GRTS能相對快速地求得較好解,這對于內(nèi)容分發(fā)網(wǎng)絡(luò)而言是至關(guān)重要的,意味著能夠減少網(wǎng)絡(luò)延遲,提高用戶的訪問體驗質(zhì)量。
本文針對無線內(nèi)容分發(fā)網(wǎng)絡(luò)中生成多棵深度和度數(shù)約束最小生成樹問題,提出了一種快速的啟發(fā)式算法GREEDY,并用定制的禁忌搜索算法和模擬退火算法對算法GREEDY求得的較好初始解進一步實施優(yōu)化。本文改進文獻[12]中的遺傳算法使之適用于深度以及度數(shù)約束最小生成樹問題,并與本文所提的算法進行比較。實驗結(jié)果表明,禁忌搜索算法有效提高了解的質(zhì)量和運行速度,在深度約束為4以及度數(shù)約束為10的條件下,解的改進幅度可達18.5%,所提算法的運行速度與遺傳算法相比提高了10倍。