基于SDN的網(wǎng)絡(luò)資源選擇多目標優(yōu)化算法

鮑楠，左加闊，胡晗，鮑煦

（1. 南京郵電大學(xué)物聯(lián)網(wǎng)學(xué)院，江蘇 南京 210023；2. 江蘇大學(xué)計算機科學(xué)與通信工程學(xué)院，江蘇 鎮(zhèn)江 212013）

1 引言

在人類需求和產(chǎn)業(yè)發(fā)展的共同激勵下，人們開始研究開發(fā)下一代無線通信網(wǎng)絡(luò)。新的無線通信技術(shù)和應(yīng)用，如認知無線電、設(shè)備到設(shè)備（D2D,device-to-device）、5G、物聯(lián)網(wǎng)等，都成為現(xiàn)階段各領(lǐng)域的研究熱點。新的研究趨勢表明下一階段的無線網(wǎng)絡(luò)結(jié)構(gòu)在現(xiàn)有基礎(chǔ)設(shè)施的基礎(chǔ)上會發(fā)展成為多層、異構(gòu)、密集的網(wǎng)絡(luò)結(jié)構(gòu)形式[1]。軟件定義網(wǎng)絡(luò)（SDN, software-defined network）就是這種新提出的網(wǎng)絡(luò)形式，它通過將控制平臺與數(shù)據(jù)平臺分離，提供高效的控制體系結(jié)構(gòu)[2]。在SDN環(huán)境中，用戶訪問、用戶接入點、不同的無線接入技術(shù)、訪問時間等數(shù)據(jù)，可以通過位于移動運營商或服務(wù)器上的SDN控制器（SDNC, SDN controller）獲得[3]。這說明SDNC能夠智能化和高效化地分配無線電資源[4]。然而多種無線接入技術(shù)共存和網(wǎng)絡(luò)用戶的增加可能會導(dǎo)致激烈的網(wǎng)絡(luò)資源競爭，如何權(quán)衡各方利益，增加獲取資源的機會，并有效利用網(wǎng)絡(luò)資源成為需要進一步解決的問題。

傳統(tǒng)的資源分配目標是網(wǎng)絡(luò)總能耗或總?cè)萘康淖顑?yōu)化[5-7]，或者偏重于用戶與網(wǎng)絡(luò)中一方的資源效用最優(yōu)化[8-9]。SDN環(huán)境中的資源管理研究可以通過負載均衡調(diào)整網(wǎng)絡(luò)資源分配[10]。文獻[11]通過優(yōu)化全網(wǎng)的信噪干擾尋找最優(yōu)的信道分配，從而提高用戶端信噪比，提高接入點的頻譜效率。這類資源分配一般是通過降低干擾和通信沖突進行網(wǎng)絡(luò)資源優(yōu)化[12-13]。另外，一些群智能算法也被應(yīng)用于基于 SDN的資源分配問題[14]，例如文獻[15]結(jié)合遺傳算法和粒子群算法得到最優(yōu)功率分配并最小化系統(tǒng)中斷概率。以上研究文獻的優(yōu)化方法和目的都不相同，卻都是利用SDN結(jié)構(gòu)獲取網(wǎng)絡(luò)資源狀態(tài)并通過資源分配算法提高網(wǎng)絡(luò)效用。但是這些網(wǎng)絡(luò)模型都沒有考慮多種有線或無線接入技術(shù)共存的情況，利用SDN統(tǒng)籌全網(wǎng)資源，在最優(yōu)化全網(wǎng)效用的過程中可能導(dǎo)致較大的個體收益差異。為了體現(xiàn)個體利益在全網(wǎng)資源優(yōu)化過程中的公平性，本文提出基于SDN的多目標優(yōu)化資源選擇算法。事實上在追求網(wǎng)絡(luò)效用的過程中，用戶與資源供給方之間、不同的資源供給方之間，互相沖突的優(yōu)化目標會使其各自的資源使其用決策相互影響。同時考察這些決策并優(yōu)化所有目標，研究SDN環(huán)境中資源分配的多目標優(yōu)化問題，可以在追求多方利益的過程中尋找到權(quán)衡點，協(xié)調(diào)資源使用和用戶需求的關(guān)系，將多網(wǎng)環(huán)境中犧牲個體利益追求全網(wǎng)效用的優(yōu)化過程轉(zhuǎn)變?yōu)樽非髠€體利益并達到全網(wǎng)均衡的結(jié)果。

本文在 SDN結(jié)構(gòu)中同時關(guān)注用戶對資源需求的優(yōu)化目標和資源供給方對資源使用的優(yōu)化目標，研究基于 SDN資源選擇的多目標優(yōu)化問題。本文主要工作如下。

1）根據(jù)用戶期望和預(yù)算，資源供給方的效用期望，分別建立用戶資源請求優(yōu)化模型和網(wǎng)絡(luò)資源效用優(yōu)化模型。

2）綜合考慮用戶申請資源的策略和資源供給方使用資源的策略，建立基于 SDN資源選擇的多目標優(yōu)化模型。

3）采用基于參考矢量的多目標優(yōu)化算法對構(gòu)建的模型進行求解，并與其他優(yōu)化算法的結(jié)果進行仿真對比。實驗結(jié)果表明，本文構(gòu)建的模型可以均衡 SDN資源的多目標優(yōu)化結(jié)果，且基于參考矢量的優(yōu)化算法相比其他優(yōu)化算法能夠更快地收斂到分布更均勻的非劣解集。

2 優(yōu)化目標

2.1 用戶訪問的最優(yōu)策略

對于一個希望通過網(wǎng)絡(luò)獲得服務(wù)的用戶來說，QoS（quality of service）始終是一個重要的考慮因素。不同于傳統(tǒng)網(wǎng)絡(luò)只提供單一資源服務(wù)，空閑遠程無線單元、移動用戶甚至虛擬中間商等現(xiàn)在都可以成為網(wǎng)絡(luò)資源提供者。這意味著用戶有更多的機會訪問網(wǎng)絡(luò)，因此，獲得混合資源的成本被認為是另一個重要的參考指標。此時用戶是否選擇網(wǎng)絡(luò)提供的服務(wù)不僅依賴于網(wǎng)絡(luò)服務(wù)的質(zhì)量，還取決于獲取資源要付出的成本。從用戶的角度來看，資源的效用需要最大化。用戶總是選擇提供更多資源并且花費成本更低的網(wǎng)絡(luò)。用戶最佳訪問策略建模如下。

其中，xij表示用戶所需的資源中來自資源供給方j(luò)的資源所占比例；Ri表示用戶i需求的資源量占所有用戶資源需求量的比例；pij表示用戶獲取資源的單價；Pi表示用戶的總預(yù)算；eij表示用戶獲取資源消耗的單位能量；Ei表示用戶i的總能量。

當(dāng)pij、eij已知時，用戶只需要決定從哪個資源供給方獲取多少資源來最大化收益，或者說最小化資源請求成本。

2.2 資源供給方的最優(yōu)策略

從小型資源供應(yīng)商到傳統(tǒng)網(wǎng)絡(luò)服務(wù)提供商，最重視的都是共享閑置資源得到的回報。因此，資源供給方的最優(yōu)選擇策略很簡單，即是否允許用戶的訪問，如何選擇用戶可以帶來更多的回報。資源供給方希望獲得更多回報的同時保留更多的可用資源，其優(yōu)化選擇策略模型如下。

其中，yij表示資源供給方j(luò)是否會選擇用戶i，yij=1表示“選擇”，否則相反；表示上一輪資源選擇后資源供給方j(luò)得到的回報。所有共享的資源不能超出資源供給方的資源儲備。

3 多目標優(yōu)化模型

大部分基于 SDN結(jié)構(gòu)的資源管理研究中，都會分開討論用戶或供應(yīng)商的最優(yōu)策略，并且在SDN控制器中以全網(wǎng)總資源效用最優(yōu)為優(yōu)化目標來分配資源。在此過程中個體利益可能面臨差異較大的實現(xiàn)程度，有些個體需求被超量滿足，有些個體需求則被拒絕。這些個體需求之間的沖突情況，可以建模為多目標優(yōu)化問題，求解多目標優(yōu)化模型可以在 SDN控制器中完成，利用個體間優(yōu)化目標的沖突性均衡全網(wǎng)資源分配。多目標優(yōu)化問題可以用數(shù)學(xué)模型表示，如式（10）～式（12）所示。

其中，x表示M維決策矢量。矢量x中每一個元素都有上下限的約束，由此構(gòu)成了決策矢量的決策空間。

在本文討論的網(wǎng)絡(luò)模型中，每個用戶和每個資源供給方都有其各自的優(yōu)化目標，這些優(yōu)化目標由 S3模型中的優(yōu)化目標函數(shù)fi（x）表示。用戶的優(yōu)化目標由 S1模型中的優(yōu)化目標函數(shù)表示，決策矢量由S1模型中的決策矢量表示。資源供給方的優(yōu)化目標由 S2模型中的優(yōu)化目標函數(shù)表示，決策矢量由S2模型中的決策矢量表示。這些優(yōu)化目標和決策矢量共同構(gòu)成了基于 SDN的網(wǎng)絡(luò)選擇和資源配置多目標優(yōu)化問題，用數(shù)學(xué)模型表示如下。

其中，z∈Rm，zi是每個目標函數(shù)fi（z）的決策矢量，每個決策矢量的元素個數(shù)為用戶個數(shù)或資源供給者的個數(shù)，將所有決策矢量展開后，約束式（14）等價于約束式（11）。

4 基于參考矢量的SDN資源選擇算法

求解多目標優(yōu)化問題時，通常的解決方法是將多目標優(yōu)化問題拆分為等價的多個單目標優(yōu)化子問題，通過求解加權(quán)求和的一組單目標優(yōu)化子問題或者聯(lián)合求解單目標優(yōu)化子問題，得到多目標優(yōu)化問題的最優(yōu)解[16-19]。因為優(yōu)化目標之間互相制約，很難找到一個最優(yōu)矢量z能滿足所有最優(yōu)化目標，但是不難找到一組非劣解，即可行解中不會出現(xiàn)比非劣解集更優(yōu)的解。所以本文采用文獻[20]的參考矢量算法來描述各個目標函數(shù)的折中變化過程，如算法1所示。

算法1基于參考矢量的SDN資源選擇算法

1）初始化決策矢量集合P0和單位參考矢量集合V0；

2）當(dāng)?shù)螖?shù)小于最大迭代次數(shù)（即t＜tmax）時；

3）生成當(dāng)前決策矢量集合Pt的子代矢量集合Qt；

4）將當(dāng)前決策矢量集合與子代矢量集合Qt合并；

5）根據(jù)參考矢量多目標優(yōu)化算法更新決策矢量集合Pt+1；

6）若有無效解，則對決策矢量進行約束懲罰，用修正解更新決策矢量集合；

7）進入下一輪迭代t=t+1；

8）當(dāng)?shù)螖?shù)等于最大迭代次數(shù)（即t=tmax）時，迭代結(jié)束。

4.1 初始化決策矢量和參考矢量

初始化決策矢量集合P0是一組隨機個體的集合，個體數(shù)量等于初始化的參考矢量數(shù)量Nvector，其中，個體是由用戶和資源供給方的策略矢量構(gòu)成的，即滿足式（14）～式（16）。初始化時，用戶的策略矢量為每個用戶選擇不同資源供給方的資源量占用戶需求資源量的百分比，取值區(qū)間為[0, 1]，定義為

其中，Nsupplier是資源供給方的數(shù)量。在每輪的迭代過程中，用戶策略中的元素值在[0, 1]之間變化。

資源供給方的策略矢量為選擇接受用戶接入請求的概率，定義為

其中，Nuser是用戶的數(shù)量；初始化時，yij=0或1，yij在每輪的迭代過程中會在取值區(qū)間[0, 1]中變化，表示資源供給方接受用戶概率的變化。在基于SDN的網(wǎng)絡(luò)環(huán)境中，為了保證空閑資源不會被浪費，資源供給方接受用戶的總概率必須大于0。

參考矢量vk是一組在第一象限內(nèi)均勻分布的單位矢量，根據(jù)規(guī)范單純形設(shè)計法生成[20-22]，如式（21）所示。

4.2 產(chǎn)生子代決策矢量

在當(dāng)前決策矢量集合中取2個最小適應(yīng)值函數(shù)對應(yīng)的決策矢量，采用經(jīng)典的模擬二元交叉[23]和多項式變異的方法生成子代決策矢量[24]。

4.3 基于參考矢量的多目標優(yōu)化算法

利用參考矢量將目標空間劃分為多個子空間，在每個子空間中分別進行最優(yōu)化資源選擇，最終得到多目標優(yōu)化的非劣解。具體的優(yōu)化選擇過程可以分為3個階段。

第一階段：適值函數(shù)轉(zhuǎn)換

因為初始化的參考矢量位于第一象限，所以需要將優(yōu)化目標的適值函數(shù)也轉(zhuǎn)換到第一象限。定義適值函數(shù)為當(dāng)前種群中的個體對應(yīng)的目標函數(shù)值集合，可以表示為

轉(zhuǎn)換后的適值函數(shù)為

第二階段：拆分

根據(jù)參考矢量將適值函數(shù)矢量分區(qū)，每個區(qū)間內(nèi)的適值函數(shù)矢量對應(yīng)的決策矢量構(gòu)成多個子集與相同參考矢量距離最近的適值函數(shù)矢量被分到同一個區(qū)間?？臻g中2個矢量的距離關(guān)系可以用夾角余弦關(guān)系來表示，矢量間的夾角余弦值越大，表示矢量之間越接近。矢量間的夾角余弦可以用式（24）計算。

其中，θt,k1,k2表示轉(zhuǎn)換后的目標函數(shù)矢量與參考矢量vt,k2的夾角。

第三階段：角度懲罰距離計算

在每一個參考矢量關(guān)聯(lián)的子集合中尋找使角度懲罰距離最小的適值函數(shù)矢量，并生成新的決策矢量集合。角度懲罰距離可以由式（25）計算[20]。

其中，γvt,k2是參考矢量vt,k2與其他參考矢量之間最小的夾角值，N是適值函數(shù)數(shù)量，tmax是最大迭代次數(shù)，α是調(diào)節(jié)g（θt,k1,k2）變化速度的參數(shù)。

基于參考矢量多目標優(yōu)化算法的具體過程如算法2所示。

算法2基于參考矢量多目標優(yōu)化算法

1）當(dāng)?shù)螖?shù)小于最大迭代次數(shù)（即t＜tmax）時；

2）根據(jù)式（22）與式（23）進行適值函數(shù)轉(zhuǎn)換；

3）根據(jù)式（24）尋找距離每個參考矢量最近的適值函數(shù)矢量，并對當(dāng)前決策矢量集合進行拆分；

4）在每個子集合中根據(jù)式（25）與式（26）計算角度懲罰距離dt,k1,k2，找到的優(yōu)秀個體It,k必須滿足

5）新的決策矢量集合由步驟 4）中找到的優(yōu)秀個體對應(yīng)的決策矢量組成；

6）進入下一輪迭代t=t+1。

算法2將插入到算法1中的步驟5）。

4.4 處理不規(guī)范的非劣解

在對用戶和資源供給方調(diào)節(jié)選擇策略的過程中，有些搜索域內(nèi)可能沒有解，或者不適合有解，所以不是每個參考矢量關(guān)聯(lián)的子集合中都至少有一個適值函數(shù)矢量。在這種情況下，隨機選擇一個適值函數(shù)矢量，作為新集合中的個體以維持集合的規(guī)模，甚至可以在當(dāng)前迭代輪回中的目標函數(shù)適應(yīng)值范圍內(nèi)，用隨機生成新的參考矢量來代替無關(guān)聯(lián)子集合的原參考矢量。

在迭代過程中還有可能出現(xiàn)超出單個目標函數(shù)約束的解，比如，用戶選擇網(wǎng)絡(luò)資源后需要消耗的能量超出了能量約束門限，或者資源供給方接收用戶的概率小于 0。本文設(shè)計一種個體約束懲罰算法對超出約束條件的解進行規(guī)范管理。S1～S3模型中的約束條件均可以用式（27）與式（28）表示。

其中，zik表示用戶或資源供給方的選擇策略，即S1模型和 S2 模型中的xij和yij；式（28）表示式（4）、式（5）與式（8）的等價約束條件。

個體約束懲罰算法的基本思想是：若新集合中的元素超出了上下邊界值0或1，則新的元素值就取邊界值0或1；若新的決策矢量不能滿足式（28），則對決策矢量進行約束懲罰，使更新后的個體能夠滿足約束條件。具體流程如在算法3所示。

算法3個體約束懲罰算法

1）對新集合中的所有個體矢量進行檢查

2）若個體元素超出了邊界值，則新元素取邊界值

3）若個體矢量不能滿足式（28），則對其進行約束懲罰

4）更新決策矢量集合

算法3將插入到算法1中的步驟6）。

4.5 算法復(fù)雜度

不考慮生成初始集合和初始參考矢量的計算復(fù)雜度，根據(jù)文獻[20]可知，每一輪迭代中最壞情況下算法1的計算復(fù)雜度為O（NNp2），其中，N是優(yōu)化目標的數(shù)量，Np是集合大小。

5 資源選擇算法性能仿真及結(jié)果分析

5.1 仿真場景

本節(jié)對基于參考矢量的 SDN資源選擇算法進行Matlab仿真分析，假設(shè)共有8個用戶和2個資源供給方加入SDN資源選擇過程，即共有10個優(yōu)化目標。同時也考察了基于遺傳算法的全網(wǎng)效用目標優(yōu)化算法和基于粒子群多目標優(yōu)化算法[25]應(yīng)用于本文網(wǎng)絡(luò)模型的效果。在基于遺傳算法的全網(wǎng)效用目標優(yōu)化算法中，資源選擇的目標是最小化所有參與者的優(yōu)化目標之和；在基于粒子群多目標優(yōu)化算法中的資源選擇目標和所提算法相似。仿真參數(shù)如表1所示。

5.2 各個參與者的優(yōu)化目標

圖1～圖3給出了各個優(yōu)化目標函數(shù)值在3種算法的歷次迭代過程中的變化情況。圖中將各個優(yōu)化目標的函數(shù)值連接起來是為了更好地顯示目標函數(shù)值的分布情況。如圖所示，3種算法中用戶間的目標函數(shù)值優(yōu)化結(jié)果差別并不明顯，資源供給方之間的目標函數(shù)值優(yōu)化結(jié)果差別也不大。所提算法和多目標粒子群算法的結(jié)果是一組向量集合，遺傳算法的結(jié)果是一個目標和，把該目標和對應(yīng)的各個優(yōu)化目標的函數(shù)值也在圖中標示出來。在本文所提算法中，因為參考矢量在多維空間中的均勻分布，導(dǎo)致得到的目標函數(shù)值分布也較為均勻，多目標粒子群算法得到的目標函數(shù)值分布較為集中。由此說明了在逼近優(yōu)化結(jié)果的區(qū)間上，本文所提方法可以得到均勻分布性較好的結(jié)果，為混合資源分配提供更多選擇。

表1 仿真參數(shù)

圖1 基于參考矢量算法的各目標函數(shù)值

圖2 基于粒子群算法的各目標函數(shù)值

圖3 基于遺傳算法的各目標函數(shù)值

圖4比較了3種算法中用戶1的目標函數(shù)值在每一輪迭代中的變化情況。比較結(jié)果說明，本文所提算法得到的結(jié)果在解空間分布上更加均勻，在迭代過程中較快地平穩(wěn)收斂，基于粒子群算法的結(jié)果在迭代過程中振蕩明顯，且分布較為集中，而基于遺傳算法的結(jié)果收斂效果不理想。因此，所提算法在求解結(jié)果的均勻分布性和收斂性方面表現(xiàn)較好。

圖4 用戶1的目標函數(shù)值變化情況

5.3 用戶接入率

用戶接入率主要體現(xiàn)用戶每次選擇資源供給方后成功接入網(wǎng)絡(luò)資源的概率，其計算式如式（29）所示。

因為不能保證所有用戶的需求都得到滿足，所以圖5～圖7中不是所有用戶的接入率都能達到1。由于網(wǎng)絡(luò)資源的匹配是在基于SDN的網(wǎng)絡(luò)環(huán)境下，因此可以通過集中調(diào)控避免單個優(yōu)化目標的貪婪收益，有可用資源的資源供給方不能拒絕所有用戶的接入請求，用戶的接入率至少都大于0。雖然圖5中的用戶接入率不是最高的，但是大部分會較快集中在0.5附近，而圖6和圖7中的數(shù)值則比較分散。

圖5 基于參考矢量算法的用戶接入率

圖6 基于粒子群算法的用戶接入率

圖7 基于遺傳算法的用戶接入率

5.4 資源請求的接受率

資源請求的接受率主要體現(xiàn)資源供給方接受一個用戶接入網(wǎng)絡(luò)資源的概率。為了保證不浪費可用網(wǎng)絡(luò)資源，資源請求的接受率必須大于 0，計算式如式（30）所示。

從圖8～圖10可以看出，3種算法的資源請求的接受率都在0.5左右，差別不大。圖9中基于粒子群算法的資源請求接受率稍微高一點，圖8中基于參考矢量算法的資源請求接受率最快收斂到最優(yōu)解區(qū)域，且2個資源供給方之間差異度較小。

圖8 基于參考矢量算法的資源請求接受率

圖9 基于粒子群算法的資源請求接受率

圖10 基于遺傳算法的資源請求接受率

5.5 資源匹配度

資源配置指標主要體現(xiàn)用戶的 QoS需求和實際獲取資源時得到的QoS之間的相似度，相似度高表明獲取的資源能夠貼近用戶的QoS需求，從而體現(xiàn)基于 SDN的資源配置優(yōu)勢，即為用戶定制貼合QoS需求的資源，而不會浪費寶貴的網(wǎng)絡(luò)資源。資源匹配度MDi可用式（31）表示。

其中，Qask表示用戶的QoS需求，Qget表示實際得到的QoS服務(wù)，Q={資源量，價格}。

本文研究 SDN環(huán)境中的資源選擇多目標優(yōu)化問題，主要是為了利用網(wǎng)絡(luò)中空閑的資源來滿足不同用戶需求，期望實現(xiàn)如下目標：1）用戶 QoS得到一定程度的滿足；2）不浪費空閑網(wǎng)絡(luò)資源；3）通過定制化的資源匹配將資源和需求有效地結(jié)合起來?？疾橘Y源選擇匹配度可以分析出算法是否達到了期望目標。圖11～圖13顯示出大部分用戶的匹配度都逼近1，說明用戶申請資源的各項期望指標（這里僅仿真了資源量和花費代價）與實際獲取資源的各項指標都比較接近。其中，基于參考矢量的算法和基于粒子群的算法得到的資源匹配度要好于基于遺傳算法的結(jié)果。從數(shù)據(jù)點的分布來看，基于參考矢量的算法數(shù)據(jù)更快地集中于一個小區(qū)間，并且匹配度都逼近 1，而基于粒子群算法的數(shù)據(jù)更多，且分布在一個較大的區(qū)間內(nèi)。

圖11 基于參考矢量算法的資源匹配度

6 結(jié)束語

本文通過考慮用戶申請資源決策和網(wǎng)絡(luò)提供資源決策的相互影響，首先建立了基于 SDN資源選擇多目標優(yōu)化模型，然后在此模型基礎(chǔ)上提出了基于參考矢量的SDN資源選擇優(yōu)化算法，

圖12 基于粒子群算法的資源匹配度

圖13 基于遺傳算法的資源匹配度

在仿真中進一步與基于遺傳算法的全網(wǎng)效用目標優(yōu)化算法和基于多目標粒子群優(yōu)化的資源選擇算法進行比較分析。仿真結(jié)果表明，所提算法與其他 2種算法相比，各個優(yōu)化目標的性能指標值集中在一個較小的區(qū)間內(nèi)，而且優(yōu)化目標之間的差異性較小，優(yōu)化目標值分布均勻，說明本文提出的算法收斂速度更快、非劣解的均勻分布性更好?；赟DN的網(wǎng)絡(luò)資源選擇多目標優(yōu)化模型經(jīng)過合適的算法設(shè)計，可以通過定制化的資源匹配方式，為用戶選擇資源、為網(wǎng)絡(luò)分配用戶，在不浪費網(wǎng)絡(luò)空閑資源的前提下可以在一定程度上滿足不同用戶的QoS需求。