基于SDN的網絡資源選擇多目標優化算法

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

（1. 南京郵電大學物聯網學院，江蘇 南京 210023；2. 江蘇大學計算機科學與通信工程學院，江蘇 鎮江 212013）

1 引言

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

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

本文在 SDN結構中同時關注用戶對資源需求的優化目標和資源供給方對資源使用的優化目標，研究基于 SDN資源選擇的多目標優化問題。本文主要工作如下。

1）根據用戶期望和預算，資源供給方的效用期望，分別建立用戶資源請求優化模型和網絡資源效用優化模型。

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

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

2 優化目標

2.1 用戶訪問的最優策略

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

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

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

2.2 資源供給方的最優策略

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

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

3 多目標優化模型

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

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

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

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

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

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

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

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

2）當迭代次數小于最大迭代次數（即t＜tmax）時；

3）生成當前決策矢量集合Pt的子代矢量集合Qt；

4）將當前決策矢量集合與子代矢量集合Qt合并；

5）根據參考矢量多目標優化算法更新決策矢量集合Pt+1；

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

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

8）當迭代次數等于最大迭代次數（即t=tmax）時，迭代結束。

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

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

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

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

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

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

4.2 產生子代決策矢量

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

4.3 基于參考矢量的多目標優化算法

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

第一階段：適值函數轉換

因為初始化的參考矢量位于第一象限，所以需要將優化目標的適值函數也轉換到第一象限。定義適值函數為當前種群中的個體對應的目標函數值集合，可以表示為

轉換后的適值函數為

第二階段：拆分

根據參考矢量將適值函數矢量分區，每個區間內的適值函數矢量對應的決策矢量構成多個子集與相同參考矢量距離最近的適值函數矢量被分到同一個區間。空間中2個矢量的距離關系可以用夾角余弦關系來表示，矢量間的夾角余弦值越大，表示矢量之間越接近。矢量間的夾角余弦可以用式（24）計算。

其中，θt,k1,k2表示轉換后的目標函數矢量與參考矢量vt,k2的夾角。

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

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

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

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

算法2基于參考矢量多目標優化算法

1）當迭代次數小于最大迭代次數（即t＜tmax）時；

2）根據式（22）與式（23）進行適值函數轉換；

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

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

5）新的決策矢量集合由步驟 4）中找到的優秀個體對應的決策矢量組成；

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

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

4.4 處理不規范的非劣解

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

在迭代過程中還有可能出現超出單個目標函數約束的解，比如，用戶選擇網絡資源后需要消耗的能量超出了能量約束門限，或者資源供給方接收用戶的概率小于 0。本文設計一種個體約束懲罰算法對超出約束條件的解進行規范管理。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 算法復雜度

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

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

5.1 仿真場景

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

5.2 各個參與者的優化目標

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

表1 仿真參數

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

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

圖3 基于遺傳算法的各目標函數值

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

圖4 用戶1的目標函數值變化情況

5.3 用戶接入率

用戶接入率主要體現用戶每次選擇資源供給方后成功接入網絡資源的概率，其計算式如式（29）所示。

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

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

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

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

5.4 資源請求的接受率

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

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

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

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

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

5.5 資源匹配度

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

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

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

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

6 結束語

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

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

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

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