基于遺傳算法的SDN 網(wǎng)絡裝箱問題研究*

何利文 張幸寧

（南京郵電大學 南京 210023）

1 引言

為了應對用戶對于復雜網(wǎng)絡環(huán)境下日益增多的請求，運營商對網(wǎng)絡業(yè)務路徑的部署提出了更高的要求。因此在有限網(wǎng)絡資源中盡可能裝載更多業(yè)務流量成為了當前評判網(wǎng)絡狀態(tài)的一個重要指標。當前運營商正處于向新型網(wǎng)絡架構(gòu)SDN 邁進的階段，SDN 網(wǎng)路和傳統(tǒng)IP 網(wǎng)絡不同，其核心思想是將轉(zhuǎn)發(fā)平面與控制平面相分離［1］。這使得SDN網(wǎng)絡在流量監(jiān)控和調(diào)度上比傳統(tǒng)網(wǎng)絡更有優(yōu)勢，并且更大程度實現(xiàn)網(wǎng)絡自動化和虛擬化。這些特性使得新型網(wǎng)絡架構(gòu)SDN 在掌控網(wǎng)絡流量以及負載均衡優(yōu)化上有很大的優(yōu)勢［2～3］。

圖1展示了一個基本的網(wǎng)絡裝箱場景［4］。先后部署了兩條業(yè)務，第一條5M 業(yè)務是從A 到E，部署的鏈路為A-C-D-E。第二條10M 業(yè)務是從B到E，發(fā)現(xiàn)第二條業(yè)務無法部署。但整體網(wǎng)絡帶寬資源滿足這兩個業(yè)務所需帶寬，此時需要對之前部署的第一條業(yè)務路徑進行調(diào)整，使新增業(yè)務得以部署在網(wǎng)絡中。調(diào)整方法是：業(yè)務1 的路徑改為A-C-E，業(yè)務二的路徑為B-C-D-E。

為了能夠在大規(guī)模的網(wǎng)絡中解決上述問題，引入了SDN網(wǎng)絡裝箱問題，調(diào)整已有的業(yè)務所在的通信鏈路，實現(xiàn)網(wǎng)絡中帶寬利用率的負載均衡的同時，部署新的業(yè)務，并且達到對原有網(wǎng)絡中的擾動最小的目標。裝箱問題是個多目標優(yōu)化的NP-hard 問題，其求解是極為困難的，由于其目標解的搜索涉及解空間的組合爆炸［5～6］，傳統(tǒng)優(yōu)化方法難以求最優(yōu)解的NP-hard 問題，因此本文采用遺傳算法這類啟發(fā)式算法求其近似解。

圖1 簡單網(wǎng)絡裝箱場景示意圖

2 SDN網(wǎng)絡下網(wǎng)絡裝箱問題建模

定義網(wǎng)絡的拓撲模型，用G=(V，E，C) 抽象描述網(wǎng)絡拓撲。V是網(wǎng)絡節(jié)點的集合，E是網(wǎng)絡鏈路的集合。集合C則是E的帶寬以及其他的一些等約束條件的集合，這里簡記為帶寬C。集合A代表網(wǎng)絡中的請求路徑的業(yè)務，A={a1，…，ak，…，am}，設網(wǎng)絡中已有m個業(yè)務。對任意k∈m，用三元組(sk，dk，bk)表示，其中sk，dk分別為業(yè)務k的起始節(jié)點和目的節(jié)點，bk表示業(yè)務k的帶寬需求。的值為0或者1，表示業(yè)務k是否經(jīng)過鏈路(i，j)，(i，j)∈E，hk為業(yè)務k的最大跳數(shù)限制，Cij表示鏈路(i，j)的容量，ω表示網(wǎng)絡中的最大鏈路利用率。

優(yōu)化目標：

其中式（1）以使最大鏈路利用率最小化以及擾動最小為優(yōu)化目標，這樣可以實現(xiàn)裝箱問題的尋優(yōu)；式（2）～（3）是限制條件；式（2）是鏈路上的最大負載限制；式（3）是對起始節(jié)點到目的節(jié)點的路徑最大跳數(shù)限制；式（4）是對的整數(shù)限制，以及對ω的非負條件限制。

其中f1=ω表示網(wǎng)絡中的最大鏈路利用率，f2=θ表示受到擾動的業(yè)務個數(shù)β占之前業(yè)務總數(shù)m的比例。將業(yè)務k所有滿足路徑約束條件的路由組成的集合稱為業(yè)務k的備用路由集。當前網(wǎng)絡中現(xiàn)有業(yè)務個數(shù)為m，記第k個業(yè)務的備用路徑集為為第k條業(yè)務擁有的備用路徑集元素的個數(shù)，表示業(yè)務k的第i條備用路由。用集合X表示網(wǎng)絡中新增的φ個業(yè)務，其中，同理，根據(jù)每一個新增業(yè)務xf計算出的備用路經(jīng)集為第f條業(yè)務擁有的備用路徑集元素的個數(shù)，可以將裝箱問題轉(zhuǎn)化為求解最優(yōu)化路由集：，滿足式（1）優(yōu)化目標，設其為方案p。用l表示鏈路(i，j)，Cl為鏈路(i，j)的帶寬。

則方案p中某一鏈路段l的負載γp(l)和方案p鏈路利用率ωp(l)可分別由式（6）和式（7）計算得出。

在這種情況下，通過遺傳算法可以求解出既滿足負載均衡，又能滿足新增業(yè)務部署的解決方案。上述優(yōu)化問題本質(zhì)上是從每一個多選擇域（Qk）中選擇正確的變量（pk），即多選擇指派問題［7］，它是NP-hard 問題，人們通常采用啟發(fā)式算法來求解現(xiàn)實生活中的NP完全問題。上述優(yōu)化問題的特點是搜索空間大，所以我們考慮采用基于全局搜索能力強的遺傳算法進行求解。

3 基于改進遺傳算法的網(wǎng)絡裝箱求解

遺傳算法（Genetic Algorithm，GA）是一類借鑒生物界自然選擇和自然遺傳機制的生物進化過程的模型，是一種通過模擬自然進化過程對解空間搜索最優(yōu)解的方法［8～9］。遺傳算法包括三個基本遺傳算子：選擇，交叉，變異。選擇操作使得種群中優(yōu)良個體得以保留，體現(xiàn)出“優(yōu)勝劣汰，適者生存”。交叉可以創(chuàng)造出新的染色體解，避免遺傳算法陷入局部最優(yōu)解。變異操作模擬生物在自然界發(fā)生的基因突變，它以很小的概率隨機地改變遺傳基因值，使得遺傳算法可以在初始組合之外的空間搜索，擴大了解空間［10］，也避免了陷入局部最優(yōu)解。

3.1 適應度函數(shù)

裝箱算法中，要求能夠求同時控制整體網(wǎng)絡的負載均衡以及受擾動業(yè)務個數(shù)，因此選取如下適應度函數(shù)：

式中，a 和 b 為權(quán)值，ω是帶寬利用率，θ是業(yè)務受到的擾動率。將多目標的問題通過權(quán)重轉(zhuǎn)化為單目標進行求解是解決多目標優(yōu)化的一個有效途徑。但是對于不同網(wǎng)絡環(huán)境場景中，權(quán)重比例是不同的，為了能夠?qū)崿F(xiàn)比例系數(shù)的自適應變化，采用如下公式確定系數(shù)：

式中，p是種群規(guī)模大小，γ為負載率與擾動率二者的比例系數(shù)。為了避免個別較差或者較優(yōu)的個體對最小帶寬利用率以及擾動率帶來的影響，求取γ時，采取去掉最好和最差的個體結(jié)果的策略。

3.2 染色體編碼

遺傳算法首先要解決的問題是把解空間的解編碼成遺傳解空間中由基因組成的染色體。本文采用自然數(shù)編碼，編碼長度只與業(yè)務個數(shù)相關，與業(yè)務的備用路徑集中路徑個數(shù)無關。一條染色體的基因是由各個業(yè)務的備用路徑集隨機選一條路徑構(gòu)成的。比如業(yè)務k 選擇的備用集中的第i個路由，記為Rk，作為第k個業(yè)務選擇的路由路徑。則一條染色體由（R1，R2，…Rk，…，Rm）組成的。

3.3 選擇操作

從種群中選擇優(yōu)勝的個體，淘汰適應度差的劣質(zhì)個體的操作稱為選擇。選擇為遺傳算法向有前途的解空間搜索提供了動力［11～12］。本文采取的錦標賽方法具有收斂速度快的優(yōu)勢，可以在較短的時間內(nèi)得到結(jié)果。設置比賽規(guī)模為2，每次從種群中隨機選擇兩個個體構(gòu)成一組，根據(jù)這個兩個個體的適應度值，將適應度高的個體取出入選子代的范圍，重復上述步驟，直到得到的個體數(shù)量滿足新一代種群的規(guī)模［13］。

3.4 交叉和變異操作

自然界生物進化過程中核心的部分就是遺傳基因的交叉變異。一般交叉概率在0.4～0.6 之間，變異概率在0.001～0.01 之間［14］，單純采用固定的交叉和變異概率并不能根據(jù)種群狀態(tài)變化而做出適時的改變，因此需采取自適應的交叉算子來保證上述要求。種群迭代前期，應適當加大交叉變異概率，有利于增加種群多樣性，迭代后期交叉變異概率適當降低，增強種群收斂效率。此外為了保證種群多樣性以及刺激表現(xiàn)差的個體，采用自適應的方法對表現(xiàn)差的個體施加更大的基因重組變異概率，表現(xiàn)好的個體給予保護，相應降低其發(fā)生交差和突變的概率。根據(jù)自適應規(guī)則，和分別代表個體i的交叉概率和變異概率，其自適應公式如下：

其中，pc1和pm1代表著交叉和變異的初始概率，gen 代表當前種群代數(shù)，maxgen 代表最大種群迭代個數(shù)，fi代表著個體i 的適應度值，c1和c1代表交叉率和變異率的比例系數(shù)，確保交叉率和變異率非負。隨著代數(shù)增加，交叉變異的概率在降低，擁有更高適應度值的個體發(fā)生重組變異的概率也更低，在保護種群優(yōu)秀個體的同時，保證了種群的多樣性［15～16］。

改進遺傳算法求解網(wǎng)絡裝箱的算法步驟如圖2所示。

圖2 網(wǎng)絡裝箱遺傳算法流程圖

4 算例仿真與分析

為了測試網(wǎng)絡裝箱遺傳算法的有效性，模擬測試了在當前運營商主流的網(wǎng)絡環(huán)境。通過配置不同網(wǎng)絡規(guī)模，不同節(jié)點個數(shù)，不同業(yè)務個數(shù)等參數(shù)，并與其他主流啟發(fā)式算法進行對比測試，驗證本論文所提算法針對網(wǎng)絡裝箱問題的有效性。

在500節(jié)點網(wǎng)格網(wǎng)絡中，網(wǎng)絡規(guī)模為1910條鏈路，鏈路帶寬在5G，6G，7G 中隨機生成，請求業(yè)務的帶寬分別為1M～200M 之間，分別測試了50 條業(yè)務、100 條業(yè)務、250 條業(yè)務、500 條業(yè)務以及 1000條業(yè)務情況下的裝箱算法測試，設置遺傳算法最大代數(shù)為100代。

圖3 不同業(yè)務數(shù)量情況下三種算法耗時對比

從圖3 實驗數(shù)據(jù)可以看出，隨著網(wǎng)絡中承載的業(yè)務個數(shù)逐漸增加，算法執(zhí)行所消耗的時間從整體上看也在增加，但從柱狀圖中可以看出在相同網(wǎng)絡環(huán)境中，遺傳算法耗費時間更少。

圖4 不同業(yè)務數(shù)量情況下三種算法負載對比

從圖4 可知，通過實驗結(jié)果對比，可以得出在完成相同裝箱任務的前提下，改進的遺傳算法在負載均衡方面表現(xiàn)均優(yōu)于蟻群算法和粒子群算法的結(jié)論。

圖5 不同算法對網(wǎng)絡裝箱業(yè)務擾動比例的影響

圖5 是基于1000 條業(yè)務，迭代5000 次獲得的結(jié)果，可以看出遺傳算法是這三種算法中收斂最快，優(yōu)化效果最好的算法，其次是蟻群算法，最后是粒子群算法。

本文還模擬了在IPRAN 網(wǎng)絡環(huán)境下的測試。IPRAN目前運營商廣泛支持的一種網(wǎng)絡，采取端到端的IP 化方式，使得運營商網(wǎng)絡扁平化，簡易化。省級IPRAN 由核心層，匯聚層，接入層組成。為檢驗在該網(wǎng)絡環(huán)境下，多目標網(wǎng)絡裝箱算法的效果，構(gòu)造出一個有5個核心環(huán)，100個匯聚環(huán)，1000個接入環(huán)的 IPRAN 場景，共 8280 個節(jié)點，18800 條鏈路的網(wǎng)絡，裝入500 條業(yè)務。每條鏈路帶寬在5G，6G，7G 之間隨機生成，每個請求業(yè)務的帶寬在50M～5G之間隨機生成。

表1 仿真結(jié)果統(tǒng)計表

在采用改進的遺傳算法對省級IPRAN 進行網(wǎng)絡裝箱優(yōu)化后，與其他啟發(fā)式算法相比，所耗時間幾乎減少一半，擾動率也下降了約83%。在相同收斂速度的情況下，遺傳算法保持更高的優(yōu)化效率。實驗表明，無論是在小規(guī)模的網(wǎng)格網(wǎng)絡中，還是大規(guī)模的省級IPRAN 網(wǎng)絡中，本論文提出的網(wǎng)絡裝箱算法均能夠保持較好的表現(xiàn)，成功實現(xiàn)了在部署新增網(wǎng)絡業(yè)務的同時，也很好地控制了網(wǎng)絡負載均衡問題。

5 結(jié)語

本論文是基于SDN網(wǎng)絡，圍繞在復雜網(wǎng)絡環(huán)境下如何合理部署業(yè)務路徑問題展開的。以網(wǎng)絡裝箱中擾動業(yè)務比例和負載均衡為目標建立數(shù)學模型，提出基于改進的遺傳算法解決網(wǎng)絡裝箱問題的解決方案，通過對遺傳算法的交叉變異算子進行自適應調(diào)整，提高了算法對多指派域問題優(yōu)化的效果。實驗結(jié)果證明，該方案與其同級別啟發(fā)式算法相比，無論是在運算耗時上還是在優(yōu)化負載和擾動率上，均表現(xiàn)出色。本論文所提方案能夠為運營商提供更加便捷，高效的網(wǎng)絡業(yè)務部署方案，從而降低運維成本，實現(xiàn)提高收益的同時，保障了企業(yè)和用戶在復雜網(wǎng)絡環(huán)境下的服務和需求。