面向無線內(nèi)容分發(fā)網(wǎng)絡(luò)的樹形拓撲生成算法*

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

(1．廣東工業(yè)大學計算機學院，廣東廣州510006;2．桂林電子科技大學廣西高校圖像圖形智能處理重點實驗室，廣西桂林541004)

1 引言

隨著移動互聯(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倍。

2 問題描述

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

在本文中，假設(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ù)流的延遲越大，所以需要相對嚴格的深度約束。

2．2DCBDMST問題數(shù)學模型

無向賦權(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é)點的最短路徑的長度。

3 啟發(fā)式算法

針對在一個給定的圖中生成多棵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)生的初始解將作為禁忌搜索算法和模擬退火算法的輸入。

4 禁忌搜索算法

禁忌搜索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所示。

5 模擬退火算法

模擬退火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所示。

6 實驗結(jié)果與分析

用本文算法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ì)量。

7 結(jié)束語

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