基于模擬退火與網絡單純形法的通信網絡中設施選址優化算法

湯 定 一

(復旦大學軟件學院 上海 200433)

0 引 言

隨著互聯網行業的發展，在線視頻網站用戶數量和用戶時長快速增長，使用移動設備獲取視頻服務已成為眾多用戶的習慣。視頻內容需要消耗較多流量，影響用戶體驗的關鍵在于帶寬。視頻內容從視頻網站到用戶需要如下過程。首先，視頻存儲在視頻服務提供商的多個服務器中。當用戶請求視頻時，視頻服務提供商選擇城市通信網絡中距離用戶較近的服務器，通過鏈路將內容發送給用戶。最后，用戶收到視頻進行觀看。為了確保用戶在觀看視頻時不會經常卡頓，需要滿足用戶所需帶寬。

視頻服務提供商在提供視頻服務時，需要考慮服務器硬件成本、部署成本和帶寬租賃費用。在滿足所有用戶需求的前提下，選擇服務器部署節點集合、帶寬租賃方案，使得總成本最低。

在城市通信網絡中提供視頻服務在概念上與內容網絡類似。內容網絡通過在Internet上部署服務節點，并通過應用層協議將這些服務節點組織形成一個構建在IP網絡之上的覆蓋層，為用戶提供靈活高效的服務[1]。

服務節點部署一直是學術界和工業界研究的熱點問題。文獻[1]將服務節點部署歸納為選址問題，根據所需獲得的信息不同，分為三類：基于確定信息的選址、基于概率模型的選址和基于博弈論的選址模型。

這里重點討論與本文問題相關的基于確定信息的模型，即已知網絡拓撲和部署費用等信息。

基于確定信息的選址模型包括兩種設定：設施選址問題[2]和P中心問題[3]，它們的區別在于是否限定設施數量。如果候選地點建站成本允許不相等，那么稱為無容量限制設施選址問題(UFLP)，這時可用建站成本來擴展目標函數。在Mirchandani等[4]和ReVelle等[5]的文章中可以找到關于UFLP問題的廣泛研究。

Goldengorin等[6]提出了增強的分支界定算法解決無容量限制設施選址問題，最小化部署成本與距離組成的混合指標。Tcha等[7]提出了基于分支界定的方法解決多層無容量限制設施選址問題，適用于具有多層結構的內容網絡。這兩個工作都使用整數規劃類算法，在約束條件較少、模型較簡單時能夠計算出最優解。但是，實際應用場景中通常需要考慮的數據規模較大，約束條件也更為復雜，此時整數規劃類算法的時間復雜度劇增，難以滿足實際應用需求。

Radoslavov等[8]從考慮路由拓撲的角度使用貪心算法解決服務器選址問題，優化目標為平均延遲和網絡容量。Laoutaris等[9]使用分布式和可擴展的方式解決內容分發網絡中服務節點選址問題。脫立恒等[10]提出兩種貪心啟發式算法解決服務器節點部署問題，在保證平均轉發延遲的前提下最小化服務部署規模。史佩昌等[11]使用啟發式算法求解多維設施選址模型。Berman等[12]使用貪心啟發式算法解決網絡中位置覆蓋問題。這些工作使用貪心和啟發式算法，優點在于能在較短時間內給出較優解，不足之處在于貪心算法通常容易陷入局部最優解，而難以收斂到全局最優。

綜上所述，現有工作通常使用整數規劃類算法和啟發式算法。然而，對于通信網絡中提供視頻服務的問題，難點在于：(1) 網絡和節點規模較大；(2) 在考慮服務器節點部署和網絡帶寬費用的基礎上，加入了服務器檔次的選擇。現有的整數規劃類算法不能在短時間內得出結果，而現有的啟發式算法通常缺乏普適性難以高效地解決此問題。因此，本文提出一種兩層迭代算法對該問題進行高效求解：外層為設施選址問題，通過模擬退火方法迭代選址方案。內層在給定服務器部署方案的情況下通過將網絡中帶寬租賃問題建模為費用流問題，使用網絡單純形求解。通過迭代產生新的部署方案以及計算該方案的總費用，在滿足帶寬需求的前提下尋找更優的服務器部署和鏈路租賃方案。該模型采用模擬退火算法，解決了貪心算法過早收斂到局部最優解的問題。網絡單純形法能夠快速計算方案，使得整個算法在短時間內能夠通過大量迭代得到更優解。在采用模擬退火和網絡單純形算法的基礎上，本文創造性地提出分段迭代的方法。根據算法迭代前期和后期服務器位置和服務器檔次的選擇對于解的優劣的影響程度不同，將算法迭代分為粗調和精調兩個階段，使得算法能夠在短時間內得到更優解。仿真結果表明，模擬退火-網絡單純形方案與貪心-Dinic算法相比，能夠減少10%以上的總成本，且隨著數據規模的擴大，優勢更加明顯。

1 問題描述

考慮以下通信網絡的設施選址問題。城市的通信網絡由節點和鏈路構成，其中每個節點的地位是等同的，它們可以通過鏈路將收到的數據轉發給另一個節點。整個網絡可以看作一幅無向圖，即數據的傳輸沒有方向的限制。同時這個網絡也是連通圖，即圖中任意兩個不同的節點之間存在路徑。圖中的一些節點有視頻帶寬需求，即這些點與小區鄰近，需要滿足用戶的需求的視頻帶寬，稱這些節點為消費節點。需要在網絡中選擇一些節點部署服務器，視頻由服務器通過網絡推送給消費節點。目標是尋找最優的視頻服務器部署方案，在滿足所有消費節點的視頻帶寬需求的前提下，使得服務器部署成本與網絡帶寬租用成本之和最低。

2 模型建立

本模型旨在滿足所有消費節點的視頻帶寬需求的前提下，使得服務器硬件成本、部署服務器成本和網絡帶寬租賃的總成本最小。

2.1 模型假設

(1) 每條鏈路有帶寬上限，按照占用帶寬收取帶寬租賃費，不同鏈路的帶寬上限與單位帶寬租賃費可能不同。

(2) 同一條鏈路的上行、下行方向的帶寬上限相互獨立，且上下行帶寬上限與單位帶寬租賃費相同，如帶寬上限5 Gbit/s，若上行占用帶寬3 Gbit/s，下行可用帶寬仍為5 Gbit/s。

(3) 一臺服務器可以服務多個消費節點，一個消費節點也可以從多個服務器獲取視頻內容服務。

(4) 每個節點上最多只能部署1臺服務器。

(5) 每臺服務器能提供的視頻輸出能力有上限，分為若干檔，不同檔位服務器的輸出能力與硬件成本不同。隨著檔次的提升，擴充單位容量的費用單調遞增。如從1檔到2檔輸出能力提升25，硬件成本增加200，若從2檔到3檔輸出能力提升25，則硬件成本至少增加200。

(6) 對于每個節點，部署服務器需要部署成本，不同節點的部署成本可能不同。部署一臺服務器到一個節點的成本為硬件成本與部署成本之和。

(7) 不同消費節點的帶寬需求可能不同。

(8) 服務器可以直接部署在消費節點，對于消費節點來說，該節點上服務器提供的帶寬沒有鏈路租賃費用，但該服務器向其他消費節點提供的視頻輸出能力上限相應減少。

(9) 鏈路帶寬上限與單位帶寬租賃費、服務器硬件成本與輸出上限、每個節點的服務器部署費、消費節點的帶寬需求均為整數。

2.2 約束模型

(1) 決策。xi表示是否在節點i上部署服務器，yi表示節點i上部署服務器的檔位。

xi∈{0,1},yi∈{0,1,…,k}

(1)

(2) 目標函數。引入超級源點S和超級匯點T。S向所有部署了服務器的節點i(xi=1)連邊，容量為相應服務器檔位輸出能力cap(yi)，費用為0。所有消費節點i向T連邊，容量為需求的帶寬di，費用為0。

目標為最小化服務器部署費、鏈路帶寬租賃費與服務器硬件成本之和。

式中：deployi為在節點i部署服務器的費用；fij為節點i到節點j實際占用的帶寬。

(3) 約束條件。流量守恒，所有節點(除了S、T)的流入流量與流出流量相等。

流量上限，每條邊的流量不超過容量上限。

fij≤biji,j∈N

服務器輸出上限，每臺服務器輸出的流量不超過檔位對應的容量。

fSi≤bSii∈N

消費節點滿流，每個消費節點的帶寬需求都需要滿足。

fiT=biTi∈N

(4) 模型參數。N為通信網絡中節點集合。S為加入的超級源，T為加入的超級匯。hardware函數表示檔位對應硬件成本，cap函數表示檔位對應輸出能力。bij表示節點i到節點j的帶寬上限，根據模型中鏈路上下行帶寬上限相等假設，有bij=bji，i,j∈N。rij為節點i到節點j的單位帶寬租賃費。bSi為超級源S到節點i的帶寬上限，代表節點i上部署服務器的視頻輸出能力。biT為節點i到超級匯的帶寬上限，代表節點i的視頻帶寬需求。

(5) 變量。fij，i,j∈{N,S,T}代表節點i到j的鏈路實際占用帶寬。xi∈{0,1}代表節點i是否部署服務器。yi∈{0,1,…,k}代表節點i部署服務器的檔位，共k個檔位可供選擇，其中0檔代表沒有部署服務器。

3 算 法

本文將問題分為兩部分：1) 在網絡節點中選擇服務器部署節點集合與服務器檔位。2) 根據服務器部署方案求最小網絡租賃費。其中第一個問題由兩層NP難問題組成，第一層是在網絡節點中選取服務器部署點集，屬于設施選址類問題，屬于NP難問題；第二層是確定服務器的檔次，比如已經選擇在30個節點上部署服務器，服務器可選檔次共10檔，因此，即便確定了服務器的數量和部署點集，還需要考慮1030種可能檔位組合。第二個問題可用費用流在多項式時間求解。

如何高效快速地得到較優解面臨兩個挑戰：(1) 外層算法的選擇，需要在速度和全局優化能力之間進行權衡。(2) 內層費用流算法的選擇，由于已有多項式算法，需要速度足夠快。

對于第一個挑戰，有兩種類型的算法，遺傳算法維護一定數量的解，通過使用交叉、變異等算子進行迭代，推動種群的進化。其優點是全局優化能力強，但速度較慢。貪心算法從一個初始可行解出發，通過迭代優化當前解，優點是速度快，但容易陷入局部最優。我們使用模擬退火算法，具備貪心算法速度快的優點，同時又能通過策略跳出局部最優解。

對于第二個挑戰，主流的費用流算法分為增廣算法(如Dinic算法)與消圈算法(如網絡單純形)。網絡單純形算法在本文問題的費用流構圖中更快。

我們在采用模擬退火和網絡單純形算法的基礎上，提出分段迭代的方法進行優化。根據算法迭代前期和后期服務器位置和服務器檔次的選擇對于解的優劣的影響程度不同，將算法迭代分為粗調和精調兩個階段，使得算法能夠在短時間內得到更優解。

3.1 外層模擬退火

模擬退火算法[13]能有效地在一個大的搜索空間中尋找最優解。其包含兩個部分：Metropolis算法和退火過程。Metropolis算法用于跳出局部最優解，通過重要性采樣方法，以概率來接受新狀態。退火過程通過調節初始溫度與退火速率，確保目標函數能夠在有限的時間內收斂。

模擬退火算法的流程是首先構造一個初始可行解，然后不斷迭代“產生新解，計算目標函數，接受或放棄新解”這個過程。通過設置初始溫度與退火速率得到當前溫度T，然后根據新解相對當前解的代價函數增量計算接受新解的概率。當溫度低于給定值或程序運行時間達到預設值時停止迭代。

1) 初始解的構造。令xi∈{0,1}表示編號為i的節點是否部署服務器，yi∈{0,1,…,k}表示編號為i的節點部署服務器的檔次。初始解的構造方式為所有節點均部署最高檔次的服務器，顯然，如果圖中存在可行解，則初始解一定是可行解。

2) 新解產生策略。根據當前服務器的部署方案產生新的服務器部署方案，隨機采用以下6種策略：(1) 隨機選取1個沒有部署服務器的節點，在其上新增服務器；(2) 隨機選取1個已經部署服務器的節點，撤掉其服務器；(3) 隨機選取1個部署了服務器的節點，將其上部署的服務器移動到相鄰節點；(4) 隨機選取1個已經部署服務器的節點，將其服務器檔次提級；(5) 隨機選取1個已經部署服務器的節點，將其服務器檔次降低；(6) 隨機選取2個已經部署服務器的節點，交換兩個服務器的檔次。

3) 初始溫度與退火速度。初始溫度影響迭代的有效性和避免陷入局部最優解的能力，過高則增加迭代次數，過低會影響解的質量。采用初始解總成本乘以常數K，這里使用0.01。退火速率采用指數式下降方式：T(n)=λT(n-1),n=1,2,3,…。其中：T(n)為當前的溫度；λ為衰減速率；T(n-1)為上一步的溫度。

3.2 內層網絡單純形

在給定服務器部署方案時，網絡鏈路帶寬租用問題可以建模為費用流問題。

費用流，也稱最小費用最大流，是指在網絡流圖中，每條邊除了流量上限外，也有單位流量費用，求出一組可行解，使得滿足它是最大流的情況下，總的費用最小。

費用流建圖過程如下，首先，費用流圖中點集為通信網絡中所有節點。由于鏈路是無向邊，在建邊時將每條從節點s到節點t的鏈路拆分為2條邊：s到t的邊，流量為帶寬上限，費用為單位帶寬租賃費。t到s的邊，流量和費用與s到t的相同。加入超級源點S與T。其中：S與所有部署服務器的點建邊，流量為服務器輸出帶寬，費用為0。所有消費節點與超級匯點T建邊，流量為帶寬需求，費用為0。如果求得的最大流等于所有消費節點的帶寬需求之和，則為可行解。

網絡單純形法[14]采用消圈思想，首先構造一條從超級源S到T的邊，流量大于從S流出的所有邊的流量之和，也大于流入T的所有邊的流量之和。它的費用大于所有邊的費用之和。這時如果在原網絡中找到任意一條從S到T的路徑，將S到T的邊的流量導入這條路徑，總費用必然減小。求最小費用的過程是不斷地在網絡中尋找負環，直到找不到負環時得到最小費用。

3.3 分段迭代優化

在算法迭代的初始階段，服務器的位置選擇是影響總成本更重要的因素。而在算法迭代的后期，服務器檔次選擇為與服務器位置選擇同等重要。我們將模擬退火分為兩個階段：粗調階段和精調階段。

(2) 精調階段。在精調階段，模擬退火在構造新解時，同時考慮服務器位置與檔次的選擇。此時使用原本的費用流圖，即超級源連向服務器部署節點的邊，容量為cap(yi)，費用為0。在新解產生策略上，使用全部6種策略，特別是在隨機時更多選用后3種關于服務器檔次的策略。

4 仿真實驗

通過在兩種不同規模的網絡上進行實驗，在90 s內將模擬退火-網絡單純形算法給出的方案與貪心-Dinic算法得到的方案進行對比，說明模擬退火-網絡單純形方案能在給定時間內得到顯著優于貪心-Dinic算法的解。

4.1 數據集

在兩種規模的數據上進行實驗：

(1) 中等規模，節點數600，邊數2 000左右，消費節點240個。

(2) 大規模，節點數1 200，邊數6 000左右，消費節點480個。

其中鏈路總帶寬與網絡租用費為[0,100]的整數，視頻服務器檔次數不超過10個。視頻服務器輸出能力為不超過300的整數，節點部署服務器成本為不超過2 000的整數，消費節點的視頻帶寬需求為不超過200的整數。

圖1中，通信網絡包含50個節點，其編號從0開始。其中：黑色節點為消費節點，比如7號節點是消費節點，有帶寬需求；邊的粗細表示鏈路容量，較粗的邊比如左上角22號與23號之間的邊的可用帶寬上限較大，較細的邊比如8號到9號之間的邊容量較小。

圖1 通信網絡結構

4.2 對比實驗

在兩種規模的數據上各使用10組隨機數據進行對比。將模擬退火-網絡單純形算法在90 s以內給出的方案與貪心-Dinic方案進行對比。這里選擇貪心算法作為傳統啟發式算法的代表，選擇Dinic算法[15]作為通用的費用流算法進行實驗對比。

圖2展示的是中等規模數據上兩種算法在90秒以內給出的方案在總成本上的對比。在第一組數據中，本文算法給出的方案總成本為199 063，貪心-Dinic法得到的總成本為227 604,差距百分比12.5%。在所有的10組數據上，本文算法給出的方案相比貪心-Dinic法的總成本減少10.2%到16.9%，特別是第2組數據，本文算法相比貪心-Dinic法總成本減少了16.9%。

圖2 中等規模數據(總共10組數據)上模擬退火-網絡單純形方案與貪心-Dinic方案的總成本對比

圖3展示的是大規模數據上兩種算法在90 s以內給出的方案在總成本上的對比。在所有的10組數據上，本文算法給出的方案相比貪心-Dinic法總成本減少了19.3%到25.2%。對比中等規模數據與大規模數據上兩種算法的總成本差距百分比，可以得出結論，隨著數據規模的增加，模擬退火-網絡單純形法相比貪心-Dinic法的優勢更大。這主要是由于隨著數據規模的增加，解的空間指數級別增大，得到更優解的難度也隨之增加。這說明本文算法在不同規模的數據上具有高效性。

圖3 大規模數據(總共10組數據)上模擬退火-網絡單純形方案與貪心-Dinic方案的總成本對比

通過在兩種規模各10組數據上的對比實驗，說明本文方案可以在給定時間內得到總成本顯著優于貪心-Dinic法的方案。在實際應用場景中，我們能夠快速給出方案以對實際部署提供指導。

4.3 兩階段優化的有效性

下面通過兩種不同規模數據的實驗，說明兩階段模擬退火算法的有效性。

首先，以中等規模第一組數據舉例。如圖4所示，在粗調階段，在前1 000輪迭代內，總成本快速地從45萬(千元)下降到20萬(千元)，并在接下來的1 000次到8 000次迭代中在20萬(千元)左右持續優化。如圖5所示，在精調階段，在前5 000輪迭代內總成本快速從20萬(千元)優化到19萬(千元)，并在接下來的5 000到38 000次迭代中持續優化。

圖4 中等規模第一組數據在粗調階段總成本隨迭代次數變化曲線

圖5 中等規模第一組數據在精調階段總成本隨迭代次數變化曲線

然后，以大規模第一組數據舉例。如圖6所示，在粗調階段，在前1 000次迭代內，總成本快速從1百萬(千元)降低到40萬(千元)，并在1 000次到3 500次迭代中持續優化。如圖7所示，在精調階段，總成本在前5 000次迭代快速從40萬(千元)優化到39萬(千元)，并在5 000到10 100次迭代中持續優化。

圖6 大規模第一組數據在粗調階段總成本隨迭代次數變化曲線

圖7 大規模第一組數據在精調階段總成本隨迭代次數變化曲線

5 結 語

將通信網絡中服務器部署方案這一實際問題建模為服務器選址問題與費用流問題的整合。本文同時考慮服務器部署選址與服務器檔次選擇這兩個NP難問題的疊加。通過適合大規模組合優化問題的模擬退火算法與適合大規模網絡中快速求解費用流的網絡單純形算法結合，求解總成本更低的服務器部署方案。

本文創造性地運用兩階段模擬退火對問題進行求解。服務器部署方案的總費用由服務器硬件成本、部署服務器成本和網絡帶寬租賃費用組成。在滿足消費節點帶寬需求的前提下，得出總成本盡可能小的部署方案。通過在90 s的時間內，在兩種規模數據上對比模擬退火-網絡單純形算法給出的方案與貪心-Dinic算法給出的方案，本文算法能夠減少10%以上的總成本，且隨著數據規模的擴大，優勢更加明顯。

本文探索了引入檔次選擇的服務設施選址問題，同時兩階段模擬退火的設計也為這一類問題提供了參考解決方案。