基于模擬退火與網(wǎng)絡(luò)單純形法的通信網(wǎng)絡(luò)中設(shè)施選址優(yōu)化算法

湯 定 一

(復(fù)旦大學(xué)軟件學(xué)院 上海 200433)

0 引 言

隨著互聯(lián)網(wǎng)行業(yè)的發(fā)展，在線視頻網(wǎng)站用戶數(shù)量和用戶時(shí)長快速增長，使用移動(dòng)設(shè)備獲取視頻服務(wù)已成為眾多用戶的習(xí)慣。視頻內(nèi)容需要消耗較多流量，影響用戶體驗(yàn)的關(guān)鍵在于帶寬。視頻內(nèi)容從視頻網(wǎng)站到用戶需要如下過程。首先，視頻存儲(chǔ)在視頻服務(wù)提供商的多個(gè)服務(wù)器中。當(dāng)用戶請求視頻時(shí)，視頻服務(wù)提供商選擇城市通信網(wǎng)絡(luò)中距離用戶較近的服務(wù)器，通過鏈路將內(nèi)容發(fā)送給用戶。最后，用戶收到視頻進(jìn)行觀看。為了確保用戶在觀看視頻時(shí)不會(huì)經(jīng)常卡頓，需要滿足用戶所需帶寬。

視頻服務(wù)提供商在提供視頻服務(wù)時(shí)，需要考慮服務(wù)器硬件成本、部署成本和帶寬租賃費(fèi)用。在滿足所有用戶需求的前提下，選擇服務(wù)器部署節(jié)點(diǎn)集合、帶寬租賃方案，使得總成本最低。

在城市通信網(wǎng)絡(luò)中提供視頻服務(wù)在概念上與內(nèi)容網(wǎng)絡(luò)類似。內(nèi)容網(wǎng)絡(luò)通過在Internet上部署服務(wù)節(jié)點(diǎn)，并通過應(yīng)用層協(xié)議將這些服務(wù)節(jié)點(diǎn)組織形成一個(gè)構(gòu)建在IP網(wǎng)絡(luò)之上的覆蓋層，為用戶提供靈活高效的服務(wù)[1]。

服務(wù)節(jié)點(diǎn)部署一直是學(xué)術(shù)界和工業(yè)界研究的熱點(diǎn)問題。文獻(xiàn)[1]將服務(wù)節(jié)點(diǎn)部署歸納為選址問題，根據(jù)所需獲得的信息不同，分為三類：基于確定信息的選址、基于概率模型的選址和基于博弈論的選址模型。

這里重點(diǎn)討論與本文問題相關(guān)的基于確定信息的模型，即已知網(wǎng)絡(luò)拓?fù)浜筒渴鹳M(fèi)用等信息。

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

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

Radoslavov等[8]從考慮路由拓?fù)涞慕嵌仁褂秘澬乃惴ń鉀Q服務(wù)器選址問題，優(yōu)化目標(biāo)為平均延遲和網(wǎng)絡(luò)容量。Laoutaris等[9]使用分布式和可擴(kuò)展的方式解決內(nèi)容分發(fā)網(wǎng)絡(luò)中服務(wù)節(jié)點(diǎn)選址問題。脫立恒等[10]提出兩種貪心啟發(fā)式算法解決服務(wù)器節(jié)點(diǎn)部署問題，在保證平均轉(zhuǎn)發(fā)延遲的前提下最小化服務(wù)部署規(guī)模。史佩昌等[11]使用啟發(fā)式算法求解多維設(shè)施選址模型。Berman等[12]使用貪心啟發(fā)式算法解決網(wǎng)絡(luò)中位置覆蓋問題。這些工作使用貪心和啟發(fā)式算法，優(yōu)點(diǎn)在于能在較短時(shí)間內(nèi)給出較優(yōu)解，不足之處在于貪心算法通常容易陷入局部最優(yōu)解，而難以收斂到全局最優(yōu)。

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

1 問題描述

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

2 模型建立

本模型旨在滿足所有消費(fèi)節(jié)點(diǎn)的視頻帶寬需求的前提下，使得服務(wù)器硬件成本、部署服務(wù)器成本和網(wǎng)絡(luò)帶寬租賃的總成本最小。

2.1 模型假設(shè)

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

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

(3) 一臺服務(wù)器可以服務(wù)多個(gè)消費(fèi)節(jié)點(diǎn)，一個(gè)消費(fèi)節(jié)點(diǎn)也可以從多個(gè)服務(wù)器獲取視頻內(nèi)容服務(wù)。

(4) 每個(gè)節(jié)點(diǎn)上最多只能部署1臺服務(wù)器。

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

(6) 對于每個(gè)節(jié)點(diǎn)，部署服務(wù)器需要部署成本，不同節(jié)點(diǎn)的部署成本可能不同。部署一臺服務(wù)器到一個(gè)節(jié)點(diǎn)的成本為硬件成本與部署成本之和。

(7) 不同消費(fèi)節(jié)點(diǎn)的帶寬需求可能不同。

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

(9) 鏈路帶寬上限與單位帶寬租賃費(fèi)、服務(wù)器硬件成本與輸出上限、每個(gè)節(jié)點(diǎn)的服務(wù)器部署費(fèi)、消費(fèi)節(jié)點(diǎn)的帶寬需求均為整數(shù)。

2.2 約束模型

(1) 決策。xi表示是否在節(jié)點(diǎn)i上部署服務(wù)器，yi表示節(jié)點(diǎn)i上部署服務(wù)器的檔位。

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

(1)

(2) 目標(biāo)函數(shù)。引入超級源點(diǎn)S和超級匯點(diǎn)T。S向所有部署了服務(wù)器的節(jié)點(diǎn)i(xi=1)連邊，容量為相應(yīng)服務(wù)器檔位輸出能力cap(yi)，費(fèi)用為0。所有消費(fèi)節(jié)點(diǎn)i向T連邊，容量為需求的帶寬di，費(fèi)用為0。

目標(biāo)為最小化服務(wù)器部署費(fèi)、鏈路帶寬租賃費(fèi)與服務(wù)器硬件成本之和。

式中：deployi為在節(jié)點(diǎn)i部署服務(wù)器的費(fèi)用；fij為節(jié)點(diǎn)i到節(jié)點(diǎn)j實(shí)際占用的帶寬。

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

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

fij≤biji,j∈N

服務(wù)器輸出上限，每臺服務(wù)器輸出的流量不超過檔位對應(yīng)的容量。

fSi≤bSii∈N

消費(fèi)節(jié)點(diǎn)滿流，每個(gè)消費(fèi)節(jié)點(diǎn)的帶寬需求都需要滿足。

fiT=biTi∈N

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

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

3 算 法

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

如何高效快速地得到較優(yōu)解面臨兩個(gè)挑戰(zhàn)：(1) 外層算法的選擇，需要在速度和全局優(yōu)化能力之間進(jìn)行權(quán)衡。(2) 內(nèi)層費(fèi)用流算法的選擇，由于已有多項(xiàng)式算法，需要速度足夠快。

對于第一個(gè)挑戰(zhàn)，有兩種類型的算法，遺傳算法維護(hù)一定數(shù)量的解，通過使用交叉、變異等算子進(jìn)行迭代，推動(dòng)種群的進(jìn)化。其優(yōu)點(diǎn)是全局優(yōu)化能力強(qiáng)，但速度較慢。貪心算法從一個(gè)初始可行解出發(fā)，通過迭代優(yōu)化當(dāng)前解，優(yōu)點(diǎn)是速度快，但容易陷入局部最優(yōu)。我們使用模擬退火算法，具備貪心算法速度快的優(yōu)點(diǎn)，同時(shí)又能通過策略跳出局部最優(yōu)解。

對于第二個(gè)挑戰(zhàn)，主流的費(fèi)用流算法分為增廣算法(如Dinic算法)與消圈算法(如網(wǎng)絡(luò)單純形)。網(wǎng)絡(luò)單純形算法在本文問題的費(fèi)用流構(gòu)圖中更快。

我們在采用模擬退火和網(wǎng)絡(luò)單純形算法的基礎(chǔ)上，提出分段迭代的方法進(jìn)行優(yōu)化。根據(jù)算法迭代前期和后期服務(wù)器位置和服務(wù)器檔次的選擇對于解的優(yōu)劣的影響程度不同，將算法迭代分為粗調(diào)和精調(diào)兩個(gè)階段，使得算法能夠在短時(shí)間內(nèi)得到更優(yōu)解。

3.1 外層模擬退火

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

模擬退火算法的流程是首先構(gòu)造一個(gè)初始可行解，然后不斷迭代“產(chǎn)生新解，計(jì)算目標(biāo)函數(shù)，接受或放棄新解”這個(gè)過程。通過設(shè)置初始溫度與退火速率得到當(dāng)前溫度T，然后根據(jù)新解相對當(dāng)前解的代價(jià)函數(shù)增量計(jì)算接受新解的概率。當(dāng)溫度低于給定值或程序運(yùn)行時(shí)間達(dá)到預(yù)設(shè)值時(shí)停止迭代。

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

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

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

3.2 內(nèi)層網(wǎng)絡(luò)單純形

在給定服務(wù)器部署方案時(shí)，網(wǎng)絡(luò)鏈路帶寬租用問題可以建模為費(fèi)用流問題。

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

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

網(wǎng)絡(luò)單純形法[14]采用消圈思想，首先構(gòu)造一條從超級源S到T的邊，流量大于從S流出的所有邊的流量之和，也大于流入T的所有邊的流量之和。它的費(fèi)用大于所有邊的費(fèi)用之和。這時(shí)如果在原網(wǎng)絡(luò)中找到任意一條從S到T的路徑，將S到T的邊的流量導(dǎo)入這條路徑，總費(fèi)用必然減小。求最小費(fèi)用的過程是不斷地在網(wǎng)絡(luò)中尋找負(fù)環(huán)，直到找不到負(fù)環(huán)時(shí)得到最小費(fèi)用。

3.3 分段迭代優(yōu)化

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

(2) 精調(diào)階段。在精調(diào)階段，模擬退火在構(gòu)造新解時(shí)，同時(shí)考慮服務(wù)器位置與檔次的選擇。此時(shí)使用原本的費(fèi)用流圖，即超級源連向服務(wù)器部署節(jié)點(diǎn)的邊，容量為cap(yi)，費(fèi)用為0。在新解產(chǎn)生策略上，使用全部6種策略，特別是在隨機(jī)時(shí)更多選用后3種關(guān)于服務(wù)器檔次的策略。

4 仿真實(shí)驗(yàn)

通過在兩種不同規(guī)模的網(wǎng)絡(luò)上進(jìn)行實(shí)驗(yàn)，在90 s內(nèi)將模擬退火-網(wǎng)絡(luò)單純形算法給出的方案與貪心-Dinic算法得到的方案進(jìn)行對比，說明模擬退火-網(wǎng)絡(luò)單純形方案能在給定時(shí)間內(nèi)得到顯著優(yōu)于貪心-Dinic算法的解。

4.1 數(shù)據(jù)集

在兩種規(guī)模的數(shù)據(jù)上進(jìn)行實(shí)驗(yàn)：

(1) 中等規(guī)模，節(jié)點(diǎn)數(shù)600，邊數(shù)2 000左右，消費(fèi)節(jié)點(diǎn)240個(gè)。

(2) 大規(guī)模，節(jié)點(diǎn)數(shù)1 200，邊數(shù)6 000左右，消費(fèi)節(jié)點(diǎn)480個(gè)。

其中鏈路總帶寬與網(wǎng)絡(luò)租用費(fèi)為[0,100]的整數(shù)，視頻服務(wù)器檔次數(shù)不超過10個(gè)。視頻服務(wù)器輸出能力為不超過300的整數(shù)，節(jié)點(diǎn)部署服務(wù)器成本為不超過2 000的整數(shù)，消費(fèi)節(jié)點(diǎn)的視頻帶寬需求為不超過200的整數(shù)。

圖1中，通信網(wǎng)絡(luò)包含50個(gè)節(jié)點(diǎn)，其編號從0開始。其中：黑色節(jié)點(diǎn)為消費(fèi)節(jié)點(diǎn)，比如7號節(jié)點(diǎn)是消費(fèi)節(jié)點(diǎn)，有帶寬需求；邊的粗細(xì)表示鏈路容量，較粗的邊比如左上角22號與23號之間的邊的可用帶寬上限較大，較細(xì)的邊比如8號到9號之間的邊容量較小。

圖1 通信網(wǎng)絡(luò)結(jié)構(gòu)

4.2 對比實(shí)驗(yàn)

在兩種規(guī)模的數(shù)據(jù)上各使用10組隨機(jī)數(shù)據(jù)進(jìn)行對比。將模擬退火-網(wǎng)絡(luò)單純形算法在90 s以內(nèi)給出的方案與貪心-Dinic方案進(jìn)行對比。這里選擇貪心算法作為傳統(tǒng)啟發(fā)式算法的代表，選擇Dinic算法[15]作為通用的費(fèi)用流算法進(jìn)行實(shí)驗(yàn)對比。

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

圖2 中等規(guī)模數(shù)據(jù)(總共10組數(shù)據(jù))上模擬退火-網(wǎng)絡(luò)單純形方案與貪心-Dinic方案的總成本對比

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

圖3 大規(guī)模數(shù)據(jù)(總共10組數(shù)據(jù))上模擬退火-網(wǎng)絡(luò)單純形方案與貪心-Dinic方案的總成本對比

通過在兩種規(guī)模各10組數(shù)據(jù)上的對比實(shí)驗(yàn)，說明本文方案可以在給定時(shí)間內(nèi)得到總成本顯著優(yōu)于貪心-Dinic法的方案。在實(shí)際應(yīng)用場景中，我們能夠快速給出方案以對實(shí)際部署提供指導(dǎo)。

4.3 兩階段優(yōu)化的有效性

下面通過兩種不同規(guī)模數(shù)據(jù)的實(shí)驗(yàn)，說明兩階段模擬退火算法的有效性。

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

圖4 中等規(guī)模第一組數(shù)據(jù)在粗調(diào)階段總成本隨迭代次數(shù)變化曲線

圖5 中等規(guī)模第一組數(shù)據(jù)在精調(diào)階段總成本隨迭代次數(shù)變化曲線

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

圖6 大規(guī)模第一組數(shù)據(jù)在粗調(diào)階段總成本隨迭代次數(shù)變化曲線

圖7 大規(guī)模第一組數(shù)據(jù)在精調(diào)階段總成本隨迭代次數(shù)變化曲線

5 結(jié) 語

將通信網(wǎng)絡(luò)中服務(wù)器部署方案這一實(shí)際問題建模為服務(wù)器選址問題與費(fèi)用流問題的整合。本文同時(shí)考慮服務(wù)器部署選址與服務(wù)器檔次選擇這兩個(gè)NP難問題的疊加。通過適合大規(guī)模組合優(yōu)化問題的模擬退火算法與適合大規(guī)模網(wǎng)絡(luò)中快速求解費(fèi)用流的網(wǎng)絡(luò)單純形算法結(jié)合，求解總成本更低的服務(wù)器部署方案。

本文創(chuàng)造性地運(yùn)用兩階段模擬退火對問題進(jìn)行求解。服務(wù)器部署方案的總費(fèi)用由服務(wù)器硬件成本、部署服務(wù)器成本和網(wǎng)絡(luò)帶寬租賃費(fèi)用組成。在滿足消費(fèi)節(jié)點(diǎn)帶寬需求的前提下，得出總成本盡可能小的部署方案。通過在90 s的時(shí)間內(nèi)，在兩種規(guī)模數(shù)據(jù)上對比模擬退火-網(wǎng)絡(luò)單純形算法給出的方案與貪心-Dinic算法給出的方案，本文算法能夠減少10%以上的總成本，且隨著數(shù)據(jù)規(guī)模的擴(kuò)大，優(yōu)勢更加明顯。

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