黃洪濤，武繼剛，鄭露露，繆裕青

(1．廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，廣東廣州510006;2．桂林電子科技大學(xué)廣西高校圖像圖形智能處理重點(diǎn)實(shí)驗(yàn)室，廣西桂林541004)

1 引言

隨著移動(dòng)互聯(lián)網(wǎng)的飛速發(fā)展，移動(dòng)網(wǎng)絡(luò)對(duì)多媒體業(yè)務(wù)的需求大幅增加，從而導(dǎo)致網(wǎng)絡(luò)流量爆炸式增長(zhǎng)。然而，傳統(tǒng)的架構(gòu)和移動(dòng)網(wǎng)絡(luò)的容量無(wú)法保證網(wǎng)絡(luò)服務(wù)質(zhì)量，移動(dòng)設(shè)備數(shù)量的激增導(dǎo)致帶寬消耗過(guò)大，容易產(chǎn)生網(wǎng)絡(luò)瓶頸，影響移動(dòng)用戶的訪問(wèn)體驗(yàn)質(zhì)量［1］。在網(wǎng)絡(luò)流量以超摩爾定律增長(zhǎng)的情況下，不僅需要提升單個(gè)節(jié)點(diǎn)的性能，而且還要從網(wǎng)絡(luò)架構(gòu)的角度優(yōu)化網(wǎng)絡(luò)拓?fù)洹Ｔ谶@種背景下，產(chǎn)生了移動(dòng)內(nèi)容分發(fā)網(wǎng)絡(luò)mCDN(mobile Content Distribution Network)。

雖然有關(guān)內(nèi)容分發(fā)網(wǎng)絡(luò)的研究很多，但mCDN的研究相當(dāng)有限［2］。與傳統(tǒng)內(nèi)容分發(fā)網(wǎng)絡(luò)不同，mCDN網(wǎng)絡(luò)設(shè)施由有線網(wǎng)絡(luò)設(shè)施和無(wú)線網(wǎng)絡(luò)設(shè)施組成。其中，有線網(wǎng)絡(luò)設(shè)施是mCDN的骨干網(wǎng)絡(luò)，負(fù)責(zé)源服務(wù)器與代理緩存服務(wù)器之間的連接以及代理緩存服務(wù)器與網(wǎng)絡(luò)組件之間的連接，網(wǎng)絡(luò)組件包括路由器、交換機(jī)、蜂窩基站BS(Base Stations)、Wi-Fi接入點(diǎn) AP(Access Points)等［3］。無(wú)線網(wǎng)絡(luò)設(shè)施負(fù)責(zé)移動(dòng)設(shè)備的通信和內(nèi)容分發(fā)，以減輕骨干網(wǎng)絡(luò)的傳輸壓力。

本文研究的是集中式無(wú)線網(wǎng)絡(luò)設(shè)施下的mCDN。蜂窩網(wǎng)絡(luò)和Wi-Fi網(wǎng)絡(luò)是兩個(gè)典型的集中式無(wú)線網(wǎng)絡(luò)設(shè)施［4］。對(duì)于無(wú)線內(nèi)容分發(fā)網(wǎng)絡(luò)，如果多個(gè)用戶從基站端獲取相同的內(nèi)容，則可能浪費(fèi)大量不必要的帶寬和能量。因此，可將內(nèi)容分發(fā)問(wèn)題視為最小生成樹(shù)問(wèn)題，把無(wú)線內(nèi)容分發(fā)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)構(gòu)建成以BS和AP為根的若干棵最小生成樹(shù)，由于移動(dòng)設(shè)備的存儲(chǔ)能力、計(jì)算能力和電源續(xù)航能力有限，需要限制生成樹(shù)的深度和每個(gè)節(jié)點(diǎn)的最大度，使網(wǎng)絡(luò)拓?fù)涑时馄交?/p>

目前，研究主要集中于兩類約束最小生成樹(shù)問(wèn)題。第一類問(wèn)題是度數(shù)約束最小生成樹(shù)問(wèn)題，其要求樹(shù)中的任意節(jié)點(diǎn)的度數(shù)不超過(guò)某一閾值。文獻(xiàn)［5］證明了該問(wèn)題是NP難問(wèn)題。求解這種問(wèn)題的算法可以歸納為三類:(1)近似算法，如文獻(xiàn)［6］提出了一種基于拉格朗日二次性的近似算法;(2)啟發(fā)式算法，如文獻(xiàn)［7］提出了可變鄰域搜索的啟發(fā)式算法;(3)智能優(yōu)化算法，如遺傳算法［8］。第二類問(wèn)題是直徑約束的最小生成樹(shù)BDMST(Bounded-Diameter Minimum Spanning Tree)問(wèn)題，該問(wèn)題要求在給定的圖中尋找滿足直徑約束的最小生成樹(shù)。當(dāng)直徑約束不小于4且小于該最小生成樹(shù)的邊數(shù)時(shí)，此問(wèn)題屬于NP難問(wèn)題［5］。相比求解度數(shù)約束最小生成樹(shù)問(wèn)題，目前的研究較少涉及求解直徑約束最小生成樹(shù)問(wèn)題。求解這類問(wèn)題的算法也可以分為三類:(1)精確算法，適用于小規(guī)模問(wèn)題，如文獻(xiàn)［9］提出的基于0-1整數(shù)規(guī)劃的分支定界法;(2)快速算法［10］，適用于大規(guī)模問(wèn)題;(3)遺傳算法，比較典型的有基于邊集編碼的遺傳算法［11］和基于序列編碼的遺傳算法［12］。其中，深度限制最小生成樹(shù)是直徑受限最小生成樹(shù)問(wèn)題的特殊情況，要求任何根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的長(zhǎng)度不超過(guò)給定的閾值。

無(wú)線內(nèi)容分發(fā)網(wǎng)絡(luò)的樹(shù)形拓?fù)浣Y(jié)構(gòu)需要同時(shí)滿足度數(shù)約束以及深度限制，以上概述的兩種約束最小生成樹(shù)不適用于無(wú)線網(wǎng)絡(luò)環(huán)境。深度和度數(shù)約束最小生成樹(shù)DCBDMST(Depth Constrained Bounded Degree Minimum Spanning Tree)問(wèn)題屬于NP完全問(wèn)題［13］。文獻(xiàn)［13］首次研究了此問(wèn)題，提出了基于克魯斯卡爾策略的深度和度數(shù)約束最小生成樹(shù)算法，該算法的局限是一次僅能生成一棵深度和度數(shù)約束的最小生成樹(shù)，不適用于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

本文的主要貢獻(xiàn)如下:

(1)提出了求解DCBDMST問(wèn)題的啟發(fā)式算法，用于生成初始近似解。此算法將BS和AP作為根節(jié)點(diǎn)加入當(dāng)前生成樹(shù);從當(dāng)前生成樹(shù)不違背深度以及度數(shù)約束的節(jié)點(diǎn)中，選擇與服務(wù)性節(jié)點(diǎn)相連并且權(quán)值最小的節(jié)點(diǎn)，將該服務(wù)性節(jié)點(diǎn)加入當(dāng)前樹(shù);直到所有服務(wù)性節(jié)點(diǎn)都加入了當(dāng)前樹(shù)，形成以BS和AP為根的若干棵生成樹(shù)。

(2)采用定制的禁忌搜索算法和模擬退火算法優(yōu)化啟發(fā)式算法產(chǎn)生的初始近似解，并改進(jìn)文獻(xiàn)［12］的基于BDMST問(wèn)題的遺傳算法使之適用于DCBDMST問(wèn)題。

(3)本文提出的啟發(fā)式算法、禁忌搜索算法、模擬退火算法和遺傳算法均能一次生成多棵深度和度數(shù)約束的最小生成樹(shù)，而現(xiàn)有相關(guān)算法僅能生成一棵生成樹(shù)。

(4)實(shí)驗(yàn)結(jié)果表明，本文提出的禁忌搜索算法在解的質(zhì)量和運(yùn)行速度方面均優(yōu)于文獻(xiàn)［12］的遺傳算法。在深度約束為4以及度數(shù)約束為10的條件下，解的質(zhì)量可提高18．5%，所提算法的運(yùn)行速度與遺傳算法相比提高了10倍。

2 問(wèn)題描述

2．1 系統(tǒng)模型

在本文中，假設(shè)在動(dòng)態(tài)無(wú)線網(wǎng)絡(luò)環(huán)境中所有移動(dòng)設(shè)備的請(qǐng)求內(nèi)容是一致的，因而移動(dòng)設(shè)備從內(nèi)容服務(wù)器接收的數(shù)據(jù)流是相同的。圖1展示了一個(gè)集中式無(wú)線網(wǎng)絡(luò)設(shè)施的架構(gòu)，由網(wǎng)絡(luò)運(yùn)營(yíng)商或內(nèi)容服務(wù)提供商管理的內(nèi)容服務(wù)器負(fù)責(zé)定期收集用戶設(shè)備的狀態(tài)信息，執(zhí)行內(nèi)容分發(fā)算法，以及通過(guò)BS和AP協(xié)調(diào)設(shè)備的角色和傳送內(nèi)容，智能地選擇設(shè)備作為服務(wù)性節(jié)點(diǎn)，其中移動(dòng)設(shè)備的角色分為服務(wù)性節(jié)點(diǎn)和非服務(wù)性節(jié)點(diǎn)。首先BS和AP將遠(yuǎn)程通信鏈路上的內(nèi)容發(fā)送到服務(wù)性節(jié)點(diǎn);然后每個(gè)服務(wù)性節(jié)點(diǎn)使用無(wú)線技術(shù)(Wi-Fi Direct或藍(lán)牙)將所接收的內(nèi)容轉(zhuǎn)發(fā)到屬于其集群的非服務(wù)性節(jié)點(diǎn)。

如圖1所示的網(wǎng)絡(luò)架構(gòu)確保每個(gè)設(shè)備和內(nèi)容服務(wù)器之間存在路由，因此可以使用內(nèi)容分發(fā)樹(shù)來(lái)表示無(wú)線內(nèi)容分發(fā)網(wǎng)絡(luò)。由于本文希望最小化將內(nèi)容傳遞到網(wǎng)絡(luò)中的每個(gè)移動(dòng)設(shè)備所需的成本，成本越小網(wǎng)絡(luò)服務(wù)質(zhì)量就越高，所以與最小生成樹(shù)的構(gòu)建方法是相關(guān)的。生成樹(shù)中任意節(jié)點(diǎn)的度數(shù)對(duì)應(yīng)于相鄰設(shè)備的數(shù)量，大的集群能夠使服務(wù)性節(jié)點(diǎn)過(guò)快地消耗電量，從而導(dǎo)致內(nèi)容分發(fā)中斷。因此，需要限制節(jié)點(diǎn)的度數(shù)。生成樹(shù)的深度表示葉節(jié)點(diǎn)至BS和AP的最大跳數(shù)，跳數(shù)越長(zhǎng)，從內(nèi)容服務(wù)器接收數(shù)據(jù)流的延遲越大，所以需要相對(duì)嚴(yán)格的深度約束。

2．2DCBDMST問(wèn)題數(shù)學(xué)模型

無(wú)向賦權(quán)圖G=(V，E，W)表示網(wǎng)絡(luò)，其中，V表示圖的頂點(diǎn)集，E表示圖的邊集，W表示圖的權(quán)值集。設(shè)當(dāng)前生成樹(shù)為S，SV;設(shè)T為圖G的滿足度數(shù)以及深度約束的一棵生成樹(shù)的邊集，并使對(duì)應(yīng)邊權(quán)重Wij之和為最小值。DT為T(mén)中各個(gè)節(jié)點(diǎn)的度數(shù)，PT為當(dāng)前生成樹(shù)的深度。DCBDMST的數(shù)學(xué)模型可描述如下:

上述數(shù)學(xué)模型由 DCBDMST問(wèn)題的優(yōu)化目標(biāo)函數(shù)及約束條件構(gòu)成，其中:第1個(gè)約束為生成樹(shù)包含不同節(jié)點(diǎn)的n－1條邊;第2個(gè)約束表示當(dāng)前生成樹(shù)無(wú)環(huán)路;第3個(gè)約束當(dāng)xij=1時(shí)，節(jié)點(diǎn)vi、vj構(gòu)成的邊是生成樹(shù)的一條邊，若xij=0，表示該邊未被選中;第4個(gè)約束為每個(gè)節(jié)點(diǎn)應(yīng)滿足的度數(shù)約束條件，D為給定的度數(shù)約束;第5個(gè)約束為每個(gè)節(jié)點(diǎn)應(yīng)滿足的深度約束條件，P為給定的深度限制;深度約束是直徑約束的特殊情況，其中生成樹(shù)的深度定義為從該節(jié)點(diǎn)到根節(jié)點(diǎn)的最短路徑的長(zhǎng)度。

3 啟發(fā)式算法

針對(duì)在一個(gè)給定的圖中生成多棵DCBDMST的問(wèn)題，本節(jié)提出了啟發(fā)式算法GREEDY來(lái)尋找一個(gè)優(yōu)質(zhì)近似解。算法GREEDY的基本思想是:首先選擇BS和AP作為根節(jié)點(diǎn)，加入當(dāng)前生成樹(shù)中;然后循環(huán)以下過(guò)程:在剩余服務(wù)性節(jié)點(diǎn)中隨機(jī)選擇一個(gè)節(jié)點(diǎn)v，從當(dāng)前生成樹(shù)不違背深度以及度數(shù)約束的節(jié)點(diǎn)中，選擇與節(jié)點(diǎn)v相連的邊權(quán)值最小的節(jié)點(diǎn)u，將節(jié)點(diǎn)v加入當(dāng)前生成樹(shù);直到服務(wù)性節(jié)點(diǎn)全部加入當(dāng)前生成樹(shù)，則循環(huán)結(jié)束。輸出以BS和AP為根的若干棵深度和度數(shù)約束最小生成樹(shù)。該算法確保所有移動(dòng)設(shè)備之間的連接都在假定的短距離無(wú)線技術(shù)的無(wú)線電范圍內(nèi)。算法的形式化描述如算法1所示。

算法1算法GREEDY

輸入:由BS、AP和服務(wù)性節(jié)點(diǎn)組成的圖G，G=(B∪C，(B×C)∪(C ×C)，W)。

輸出:圖G的若干棵深度和度數(shù)約束最小生成樹(shù)的邊集τ，以及權(quán)值w。

1．Begin

在算法GREEDY的形式化描述中，節(jié)點(diǎn)集合B表示若干的BS和AP，節(jié)點(diǎn)集合C表示一定數(shù)量的服務(wù)性設(shè)備，權(quán)值集合W表示節(jié)點(diǎn)間的距離，行2的集合U表示當(dāng)前可供連接的節(jié)點(diǎn)。假設(shè)圖G中含有n個(gè)節(jié)點(diǎn)，其中m個(gè)節(jié)點(diǎn)是BS和AP，剩余n－m個(gè)節(jié)點(diǎn)為服務(wù)性設(shè)備。該算法的主要計(jì)算量是查找滿足約束條件的最小值，該步驟的時(shí)間復(fù)雜度在最壞情況下為O(n)，因?yàn)檫@一步需要執(zhí)行n－m次，所以算法GREEDY的時(shí)間復(fù)雜度為O(n2)。

給定無(wú)向賦權(quán)圖G，所提算法GREEDY能高效地找到圖G的多棵DCBDMST的較好近似解。算法GREEDY產(chǎn)生的初始解將作為禁忌搜索算法和模擬退火算法的輸入。

4 禁忌搜索算法

禁忌搜索TS(Tabu Search)算法是一種全局逐步尋優(yōu)算法。其求解的過(guò)程是從一個(gè)初始可行解出發(fā)，然后采用鄰域選優(yōu)的方法，在搜索過(guò)程中將近期的歷史上的搜索過(guò)程存放在禁忌表中，只有不在禁忌表中的較好解，才被接受作為下一次迭代的初始解;使用禁忌表來(lái)封鎖剛搜索過(guò)的區(qū)域，以避免迂回搜索，同時(shí)赦免禁忌表中的一些優(yōu)良狀態(tài)，進(jìn)而保證搜索的多樣性，從而達(dá)到全局優(yōu)化［14］。

首先使用前節(jié)所述的算法GREEDY尋找一個(gè)較好的初始解。然后在TS算法的初始階段，采用序列編碼的方法對(duì)狀態(tài)進(jìn)行表示。序列編碼是指用n位自然數(shù)唯一地表達(dá)出含有n個(gè)節(jié)點(diǎn)的生成樹(shù)，其中每個(gè)數(shù)字在1和n之間。例如，用(1，2，…，n)的一個(gè)排列來(lái)表示一個(gè)狀態(tài)，即它的編碼方式。

在生成若干棵DCBDMST的問(wèn)題中，目標(biāo)函數(shù)值為解碼樹(shù)的權(quán)值。解碼是基因型到表現(xiàn)型的映射，具體而言就是排列到生成樹(shù)的映射。解碼方式是類似于算法GREEDY的一個(gè)執(zhí)行過(guò)程，略微有所不同的是不在待選節(jié)點(diǎn)集合中隨機(jī)選擇節(jié)點(diǎn)，而是按照排列的順序逐個(gè)選擇節(jié)點(diǎn)。按照排列的順序依次選擇節(jié)點(diǎn)加入當(dāng)前生成樹(shù)。

在TS算法中，每一次的搜索都是基于當(dāng)前解的候選解集。在本文中候選解集為領(lǐng)域的真子集，即只掃描領(lǐng)域的一部分來(lái)構(gòu)成候選解集。領(lǐng)域是一種移動(dòng)操作，移動(dòng)是從當(dāng)前解產(chǎn)生新解的途徑，從當(dāng)前解可以進(jìn)行的所有移動(dòng)構(gòu)成領(lǐng)域。在本文中采用任意交換兩個(gè)位置的移動(dòng)規(guī)則來(lái)產(chǎn)生當(dāng)前解的領(lǐng)域解，將當(dāng)前狀態(tài)作為禁忌表中的禁忌對(duì)象。根據(jù)渴望水平來(lái)評(píng)價(jià)當(dāng)前解的候選解集，目標(biāo)函數(shù)值越小，表示候選解的質(zhì)量越好。如果某個(gè)候選解的目標(biāo)函數(shù)值優(yōu)于歷史最優(yōu)值，那么無(wú)論這個(gè)候選解是否處于被禁忌狀態(tài)，都會(huì)被接受，并更新當(dāng)前解和歷史最優(yōu)解，給定最大迭代步數(shù)作為停止準(zhǔn)則，用于停止搜索。

使用TS算法生成多棵DCBDMST的算法流程圖如圖2所示。

5 模擬退火算法

模擬退火SA(Simulated Annealing)算法是一種隨機(jī)搜索算法，它模擬了物理退火過(guò)程，從一個(gè)給定的初始高溫開(kāi)始，利用Metropolis準(zhǔn)則進(jìn)行隨機(jī)搜索，隨著溫度的緩慢下降循環(huán)抽樣過(guò)程，當(dāng)溫度足夠低時(shí)得到問(wèn)題的全局最優(yōu)解［15］。

使用SA算法對(duì)生成多棵DCBDMST問(wèn)題進(jìn)行求解的設(shè)計(jì)如下所示:

(1)為了加快 SA算法的收斂，使用算法GREEDY產(chǎn)生一個(gè)優(yōu)質(zhì)的初始解，使用序列編碼的方式來(lái)表達(dá)狀態(tài)，目標(biāo)函數(shù)值是解碼樹(shù)的權(quán)值。

(2)與TS算法相同，SA算法也是基于領(lǐng)域搜索的，SA算法修改當(dāng)前解的狀態(tài)的方法與TS算法相同。所不同的是SA算法采用了一種特殊的Metropolis準(zhǔn)則的領(lǐng)域移動(dòng)方法，領(lǐng)域移動(dòng)分為無(wú)條件移動(dòng)和有條件移動(dòng)。如果新解的目標(biāo)函數(shù)值小于當(dāng)前解的目標(biāo)函數(shù)值，則進(jìn)行無(wú)條件移動(dòng);否則，根據(jù)一定的概率進(jìn)行有條件移動(dòng)。

(3)SA算法為了保證能夠到達(dá)平衡狀態(tài)，在每一溫度，內(nèi)循環(huán)次數(shù)要足夠大且迭代相同的次數(shù)，內(nèi)循環(huán)次數(shù)設(shè)置為一個(gè)常數(shù)。滿足內(nèi)循環(huán)次數(shù)后，SA算法降低一個(gè)溫度進(jìn)入外循環(huán)過(guò)程。溫度的下降由降溫函數(shù)來(lái)控制。由于溫度的大小決定著SA算法進(jìn)行全局搜索還是局部搜索，當(dāng)溫度很高時(shí)，SA算法進(jìn)行全局搜索;當(dāng)溫度很低時(shí)，SA算法進(jìn)行局部搜索。如果溫度下降過(guò)快則可能過(guò)早陷入局部最優(yōu)，選擇理想的降溫函數(shù)能夠幫助提高SA算法的性能，本文使用降溫函數(shù)Tn+1=Tn·r，其中降溫系數(shù) r∈(0．95，0．99)。

此外，對(duì)模擬退火算法進(jìn)行兩方面改進(jìn)。第一點(diǎn)改進(jìn)是增加記憶功能。為避免搜索過(guò)程中由于執(zhí)行概率接受環(huán)節(jié)而遺失當(dāng)前遇到的最優(yōu)解，可通過(guò)增加存儲(chǔ)功能，將歷史最優(yōu)解的狀態(tài)記憶下來(lái)。第二點(diǎn)改進(jìn)是增加重升溫過(guò)程。在算法進(jìn)程的適當(dāng)時(shí)機(jī)，將溫度適當(dāng)提高，從而可激活各狀態(tài)的接受概率，以調(diào)整搜索進(jìn)程中的當(dāng)前狀態(tài)，避免算法在局部極小解處停滯不前。

使用SA算法生成多棵DCBDMST的算法流程圖如圖3所示。

6 實(shí)驗(yàn)結(jié)果與分析

用本文算法GREEDY構(gòu)造的較好近似解，并用禁忌搜索算法和模擬退火算法對(duì)近似解進(jìn)行優(yōu)化的算法在本文中分別記作GRTS(GREEDY-TS)和GRSA(GREEDY-SA)。本文在文獻(xiàn)［12］的基于BDMST問(wèn)題的遺傳算法基礎(chǔ)上，改進(jìn)該算法使之適用于DCBDMST問(wèn)題，使用改進(jìn)后的遺傳算法EGA(Improve-GA)與本文提出的算法GRTS和算法GRSA進(jìn)行比較，以評(píng)估所提算法在反映服務(wù)質(zhì)量的網(wǎng)絡(luò)成本方面和反映計(jì)算復(fù)雜度的執(zhí)行時(shí)間方面的性能。實(shí)驗(yàn)中所涉及的算法均在Intel(R)Core(TM)i7-6700 CPU 3．40 GHz RAM 8 GB 四核的機(jī)器上運(yùn)行。

本文將網(wǎng)絡(luò)成本建模為所有發(fā)射機(jī)至接收機(jī)之間的距離之和，度量單位為m。因?yàn)楸忍芈适峭ㄐ啪嚯x的直接函數(shù)，因此最小化基于距離的成本度量可以映射到最大化速率。當(dāng)節(jié)點(diǎn)的初始數(shù)量n≤64時(shí)，假定100×100的網(wǎng)格具有一個(gè)基站，當(dāng)n＞64時(shí)，512×512的網(wǎng)格具有四個(gè)基站。此外，假設(shè)基站無(wú)線電范圍為300 m，Wi-Fi無(wú)線電范圍為25 m。本文參照文獻(xiàn)［16］按均勻隨機(jī)方式產(chǎn)生［1，25］的整數(shù)作為節(jié)點(diǎn)之間的距離。

根據(jù)多次實(shí)驗(yàn)結(jié)果較好的值來(lái)設(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ò)成本和平均運(yùn)行時(shí)間的實(shí)驗(yàn)結(jié)果;表2是上述算法的最低網(wǎng)絡(luò)成本和最佳運(yùn)行時(shí)間的實(shí)驗(yàn)結(jié)果，其中度閾值D分別設(shè)置為6、8、10，深度閾值 P 分別取值為 2、3、4。網(wǎng)絡(luò)成本越小，表示算法求得的解的質(zhì)量越高。

表1展示了20次重復(fù)實(shí)驗(yàn)中獲得的平均網(wǎng)絡(luò)成本(平均解)和平均運(yùn)行時(shí)間。表1表明:當(dāng)P=3、D=8時(shí)，算法GRTS的平均網(wǎng)絡(luò)成本優(yōu)于算法EGA的，平均解的質(zhì)量最大提高了10．3%。當(dāng)P=3、D=6時(shí)，算法GRTS的平均網(wǎng)絡(luò)成本仍優(yōu)于算法EGA的，平均解的質(zhì)量最大提高了11．4%。當(dāng)P=2、D=10時(shí)，算法GRTS的平均網(wǎng)絡(luò)成本持續(xù)優(yōu)于算法EGA的，平均解的質(zhì)量最大提高了10．4%。當(dāng)P=2、D=10時(shí)，算法GRTS的平均網(wǎng)絡(luò)成本始終優(yōu)于算法EGA的，平均解的質(zhì)量最大提高了9．6%。算法GRSA在平均網(wǎng)絡(luò)成本方面略次于算法EGA的。本文所提算法的平均運(yùn)行時(shí)間顯著優(yōu)于算法EGA的，GRTS的平均運(yùn)行時(shí)間至少是EGA的1/10，GRSA的平均運(yùn)行時(shí)間至少是EGA的1/20。

表2展示了在20次實(shí)驗(yàn)中獲得的最低網(wǎng)絡(luò)成本(最優(yōu)解)和最佳運(yùn)行時(shí)間。表2表明:當(dāng)P=3、D=8時(shí)，算法GRTS的最低網(wǎng)絡(luò)成本優(yōu)于算法EGA的，最優(yōu)解的改進(jìn)幅度最大可達(dá)7%。當(dāng)P=4、D=10時(shí)，算法GRTS的最低網(wǎng)絡(luò)成本依然優(yōu)于算法EGA的，最優(yōu)解的改進(jìn)幅度最大可達(dá)18．5%。當(dāng)P=3、D=6時(shí)，算法GRTS的最低網(wǎng)絡(luò)成本繼續(xù)優(yōu)于算法EGA的，最優(yōu)解的改進(jìn)幅度最大可達(dá)7．4%。當(dāng)P=2、D=10時(shí)，算法GRTS的最低網(wǎng)絡(luò)成本始終優(yōu)于算法EGA的，最優(yōu)解的改進(jìn)幅度最大可達(dá)8．9%。算法GRSA在最低網(wǎng)絡(luò)成本方面仍略次于算法EGA。本文所提算法的最佳運(yùn)行時(shí)間明顯優(yōu)于算法EGA的，GRTS的最佳運(yùn)行時(shí)間至少是EGA的1/10，GRSA的最佳運(yùn)行時(shí)間至少是EGA的1/30。

Table 1 Performance comparison among the algorithms in average network cost and average running time表1 算法在平均網(wǎng)絡(luò)成本、平均運(yùn)行時(shí)間上的比較

Table 2 Performance comparison among the algorithms in lowest network cost and best running time表2 算法在最低網(wǎng)絡(luò)成本、最佳運(yùn)行時(shí)間上的比較

實(shí)驗(yàn)結(jié)果表明，本文所提算法GRTS在給定任意約束條件下，與算法EGA相比，均能更好更快地求解。這說(shuō)明算法GRTS性能是穩(wěn)定的，但是算法GRSA在解的質(zhì)量方面略次于算法EGA。因?yàn)樗惴‥GA用隨機(jī)初始種群作為遺傳算法的初始解，遺傳算法的精髓是遺傳算子，并不依賴于初始種群的優(yōu)良，廣域搜索能力強(qiáng);模擬退火算法全局搜索能力略顯不足且初值依賴性較弱;然而本文提出了啟發(fā)式算法能夠?yàn)榻伤阉魉惴ㄌ峁﹥?yōu)質(zhì)的初始解。

綜上，在生成多棵DCBDMST的問(wèn)題上，算法GRTS能相對(duì)快速地求得較好解，這對(duì)于內(nèi)容分發(fā)網(wǎng)絡(luò)而言是至關(guān)重要的，意味著能夠減少網(wǎng)絡(luò)延遲，提高用戶的訪問(wèn)體驗(yàn)質(zhì)量。

7 結(jié)束語(yǔ)

本文針對(duì)無(wú)線內(nèi)容分發(fā)網(wǎng)絡(luò)中生成多棵深度和度數(shù)約束最小生成樹(shù)問(wèn)題，提出了一種快速的啟發(fā)式算法GREEDY，并用定制的禁忌搜索算法和模擬退火算法對(duì)算法GREEDY求得的較好初始解進(jìn)一步實(shí)施優(yōu)化。本文改進(jìn)文獻(xiàn)［12］中的遺傳算法使之適用于深度以及度數(shù)約束最小生成樹(shù)問(wèn)題，并與本文所提的算法進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明，禁忌搜索算法有效提高了解的質(zhì)量和運(yùn)行速度，在深度約束為4以及度數(shù)約束為10的條件下，解的改進(jìn)幅度可達(dá)18．5%，所提算法的運(yùn)行速度與遺傳算法相比提高了10倍。