面向無線內容分發網絡的樹形拓撲生成算法*

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

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

1 引言

隨著移動互聯網的飛速發展，移動網絡對多媒體業務的需求大幅增加，從而導致網絡流量爆炸式增長。然而，傳統的架構和移動網絡的容量無法保證網絡服務質量，移動設備數量的激增導致帶寬消耗過大，容易產生網絡瓶頸，影響移動用戶的訪問體驗質量［1］。在網絡流量以超摩爾定律增長的情況下，不僅需要提升單個節點的性能，而且還要從網絡架構的角度優化網絡拓撲。在這種背景下，產生了移動內容分發網絡mCDN(mobile Content Distribution Network)。

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

本文研究的是集中式無線網絡設施下的mCDN。蜂窩網絡和Wi-Fi網絡是兩個典型的集中式無線網絡設施［4］。對于無線內容分發網絡，如果多個用戶從基站端獲取相同的內容，則可能浪費大量不必要的帶寬和能量。因此，可將內容分發問題視為最小生成樹問題，把無線內容分發網絡拓撲結構構建成以BS和AP為根的若干棵最小生成樹，由于移動設備的存儲能力、計算能力和電源續航能力有限，需要限制生成樹的深度和每個節點的最大度，使網絡拓撲呈扁平化。

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

無線內容分發網絡的樹形拓撲結構需要同時滿足度數約束以及深度限制，以上概述的兩種約束最小生成樹不適用于無線網絡環境。深度和度數約束最小生成樹DCBDMST(Depth Constrained Bounded Degree Minimum Spanning Tree)問題屬于NP完全問題［13］。文獻［13］首次研究了此問題，提出了基于克魯斯卡爾策略的深度和度數約束最小生成樹算法，該算法的局限是一次僅能生成一棵深度和度數約束的最小生成樹，不適用于網絡拓撲結構。

本文的主要貢獻如下:

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

(2)采用定制的禁忌搜索算法和模擬退火算法優化啟發式算法產生的初始近似解，并改進文獻［12］的基于BDMST問題的遺傳算法使之適用于DCBDMST問題。

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

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

2 問題描述

2．1 系統模型

在本文中，假設在動態無線網絡環境中所有移動設備的請求內容是一致的，因而移動設備從內容服務器接收的數據流是相同的。圖1展示了一個集中式無線網絡設施的架構，由網絡運營商或內容服務提供商管理的內容服務器負責定期收集用戶設備的狀態信息，執行內容分發算法，以及通過BS和AP協調設備的角色和傳送內容，智能地選擇設備作為服務性節點，其中移動設備的角色分為服務性節點和非服務性節點。首先BS和AP將遠程通信鏈路上的內容發送到服務性節點;然后每個服務性節點使用無線技術(Wi-Fi Direct或藍牙)將所接收的內容轉發到屬于其集群的非服務性節點。

如圖1所示的網絡架構確保每個設備和內容服務器之間存在路由，因此可以使用內容分發樹來表示無線內容分發網絡。由于本文希望最小化將內容傳遞到網絡中的每個移動設備所需的成本，成本越小網絡服務質量就越高，所以與最小生成樹的構建方法是相關的。生成樹中任意節點的度數對應于相鄰設備的數量，大的集群能夠使服務性節點過快地消耗電量，從而導致內容分發中斷。因此，需要限制節點的度數。生成樹的深度表示葉節點至BS和AP的最大跳數，跳數越長，從內容服務器接收數據流的延遲越大，所以需要相對嚴格的深度約束。

2．2DCBDMST問題數學模型

無向賦權圖G=(V，E，W)表示網絡，其中，V表示圖的頂點集，E表示圖的邊集，W表示圖的權值集。設當前生成樹為S，SV;設T為圖G的滿足度數以及深度約束的一棵生成樹的邊集，并使對應邊權重Wij之和為最小值。DT為T中各個節點的度數，PT為當前生成樹的深度。DCBDMST的數學模型可描述如下:

上述數學模型由 DCBDMST問題的優化目標函數及約束條件構成，其中:第1個約束為生成樹包含不同節點的n－1條邊;第2個約束表示當前生成樹無環路;第3個約束當xij=1時，節點vi、vj構成的邊是生成樹的一條邊，若xij=0，表示該邊未被選中;第4個約束為每個節點應滿足的度數約束條件，D為給定的度數約束;第5個約束為每個節點應滿足的深度約束條件，P為給定的深度限制;深度約束是直徑約束的特殊情況，其中生成樹的深度定義為從該節點到根節點的最短路徑的長度。

3 啟發式算法

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

算法1算法GREEDY

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

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

1．Begin

在算法GREEDY的形式化描述中，節點集合B表示若干的BS和AP，節點集合C表示一定數量的服務性設備，權值集合W表示節點間的距離，行2的集合U表示當前可供連接的節點。假設圖G中含有n個節點，其中m個節點是BS和AP，剩余n－m個節點為服務性設備。該算法的主要計算量是查找滿足約束條件的最小值，該步驟的時間復雜度在最壞情況下為O(n)，因為這一步需要執行n－m次，所以算法GREEDY的時間復雜度為O(n2)。

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

4 禁忌搜索算法

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

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

在生成若干棵DCBDMST的問題中，目標函數值為解碼樹的權值。解碼是基因型到表現型的映射，具體而言就是排列到生成樹的映射。解碼方式是類似于算法GREEDY的一個執行過程，略微有所不同的是不在待選節點集合中隨機選擇節點，而是按照排列的順序逐個選擇節點。按照排列的順序依次選擇節點加入當前生成樹。

在TS算法中，每一次的搜索都是基于當前解的候選解集。在本文中候選解集為領域的真子集，即只掃描領域的一部分來構成候選解集。領域是一種移動操作，移動是從當前解產生新解的途徑，從當前解可以進行的所有移動構成領域。在本文中采用任意交換兩個位置的移動規則來產生當前解的領域解，將當前狀態作為禁忌表中的禁忌對象。根據渴望水平來評價當前解的候選解集，目標函數值越小，表示候選解的質量越好。如果某個候選解的目標函數值優于歷史最優值，那么無論這個候選解是否處于被禁忌狀態，都會被接受，并更新當前解和歷史最優解，給定最大迭代步數作為停止準則，用于停止搜索。

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

5 模擬退火算法

模擬退火SA(Simulated Annealing)算法是一種隨機搜索算法，它模擬了物理退火過程，從一個給定的初始高溫開始，利用Metropolis準則進行隨機搜索，隨著溫度的緩慢下降循環抽樣過程，當溫度足夠低時得到問題的全局最優解［15］。

使用SA算法對生成多棵DCBDMST問題進行求解的設計如下所示:

(1)為了加快 SA算法的收斂，使用算法GREEDY產生一個優質的初始解，使用序列編碼的方式來表達狀態，目標函數值是解碼樹的權值。

(2)與TS算法相同，SA算法也是基于領域搜索的，SA算法修改當前解的狀態的方法與TS算法相同。所不同的是SA算法采用了一種特殊的Metropolis準則的領域移動方法，領域移動分為無條件移動和有條件移動。如果新解的目標函數值小于當前解的目標函數值，則進行無條件移動;否則，根據一定的概率進行有條件移動。

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

此外，對模擬退火算法進行兩方面改進。第一點改進是增加記憶功能。為避免搜索過程中由于執行概率接受環節而遺失當前遇到的最優解，可通過增加存儲功能，將歷史最優解的狀態記憶下來。第二點改進是增加重升溫過程。在算法進程的適當時機，將溫度適當提高，從而可激活各狀態的接受概率，以調整搜索進程中的當前狀態，避免算法在局部極小解處停滯不前。

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

6 實驗結果與分析

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

本文將網絡成本建模為所有發射機至接收機之間的距離之和，度量單位為m。因為比特率是通信距離的直接函數，因此最小化基于距離的成本度量可以映射到最大化速率。當節點的初始數量n≤64時，假定100×100的網格具有一個基站，當n＞64時，512×512的網格具有四個基站。此外，假設基站無線電范圍為300 m，Wi-Fi無線電范圍為25 m。本文參照文獻［16］按均勻隨機方式產生［1，25］的整數作為節點之間的距離。

根據多次實驗結果較好的值來設置算法EGA、GRTS的迭代次數。如圖4所示，在算法EGA中，種群的規模為100，交叉算子的交叉率為0．7，變異操作的變異率為 0．001，結果顯示算法EGA迭代30次趨于收斂;在算法GRTS中，候選解集的大小為12，禁忌表的大小設置為20，結果表明算法GRTS迭代40次趨于收斂。在算法GRSA中，初始高溫設置為100，終止溫度取0．01，降溫比例系數為0．98。表1是算法 GREEDY、GRSA 、GRTS和EGA的平均網絡成本和平均運行時間的實驗結果;表2是上述算法的最低網絡成本和最佳運行時間的實驗結果，其中度閾值D分別設置為6、8、10，深度閾值 P 分別取值為 2、3、4。網絡成本越小，表示算法求得的解的質量越高。

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

表2展示了在20次實驗中獲得的最低網絡成本(最優解)和最佳運行時間。表2表明:當P=3、D=8時，算法GRTS的最低網絡成本優于算法EGA的，最優解的改進幅度最大可達7%。當P=4、D=10時，算法GRTS的最低網絡成本依然優于算法EGA的，最優解的改進幅度最大可達18．5%。當P=3、D=6時，算法GRTS的最低網絡成本繼續優于算法EGA的，最優解的改進幅度最大可達7．4%。當P=2、D=10時，算法GRTS的最低網絡成本始終優于算法EGA的，最優解的改進幅度最大可達8．9%。算法GRSA在最低網絡成本方面仍略次于算法EGA。本文所提算法的最佳運行時間明顯優于算法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 算法在平均網絡成本、平均運行時間上的比較

Table 2 Performance comparison among the algorithms in lowest network cost and best running time表2 算法在最低網絡成本、最佳運行時間上的比較

實驗結果表明，本文所提算法GRTS在給定任意約束條件下，與算法EGA相比，均能更好更快地求解。這說明算法GRTS性能是穩定的，但是算法GRSA在解的質量方面略次于算法EGA。因為算法EGA用隨機初始種群作為遺傳算法的初始解，遺傳算法的精髓是遺傳算子，并不依賴于初始種群的優良，廣域搜索能力強;模擬退火算法全局搜索能力略顯不足且初值依賴性較弱;然而本文提出了啟發式算法能夠為禁忌搜索算法提供優質的初始解。

綜上，在生成多棵DCBDMST的問題上，算法GRTS能相對快速地求得較好解，這對于內容分發網絡而言是至關重要的，意味著能夠減少網絡延遲，提高用戶的訪問體驗質量。

7 結束語

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