SDN 中基于蟻群優(yōu)化的網(wǎng)絡(luò)測(cè)量節(jié)點(diǎn)選擇算法

葉和元，韓 俐，孫士民

（1.天津理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，天津 300384；2.天津工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300387）

0 概述

互聯(lián)網(wǎng)應(yīng)用呈現(xiàn)多樣化、精細(xì)化和快速化發(fā)展，同時(shí)網(wǎng)絡(luò)管理的難度也越來(lái)越大。隨著流量監(jiān)測(cè)技術(shù)的不斷提升，網(wǎng)絡(luò)測(cè)量從流量數(shù)據(jù)中分析用戶的行為特征［1］，為網(wǎng)絡(luò)管理提供依據(jù)。高清視頻、虛擬現(xiàn)實(shí)等應(yīng)用使網(wǎng)絡(luò)帶寬快速提升，直接導(dǎo)致網(wǎng)絡(luò)流量難以復(fù)現(xiàn)，為攻擊者隱藏惡意流量提供了便利。如果防護(hù)措施不規(guī)范，頻發(fā)的網(wǎng)絡(luò)安全事件嚴(yán)重威脅用戶隱私和社會(huì)經(jīng)濟(jì)安全［2］。網(wǎng)絡(luò)測(cè)量是網(wǎng)絡(luò)管理的基礎(chǔ)，細(xì)粒度的流量統(tǒng)計(jì)特征可以準(zhǔn)確反映潛在的網(wǎng)絡(luò)問(wèn)題，能夠有效地指導(dǎo)異常檢測(cè)工作。測(cè)量節(jié)點(diǎn)作為網(wǎng)絡(luò)測(cè)量的環(huán)境要素［3］，其主要采集流量的網(wǎng)絡(luò)節(jié)點(diǎn)，如軟件定義網(wǎng)絡(luò)（Software Defined Network，SDN）中的ΟpenFlow 交換機(jī)。測(cè)量節(jié)點(diǎn)選擇方法用于決策整個(gè)網(wǎng)絡(luò)中的測(cè)量節(jié)點(diǎn)，SDN 控制器可以在線查詢交換機(jī)上的流統(tǒng)計(jì)信息，然而查詢哪些ΟpenFlow 交換機(jī)獲取了細(xì)粒度流信息成為研究熱點(diǎn)［4］。

SDN 網(wǎng)絡(luò)的控制平面和數(shù)據(jù)平面是解耦合的，控制器能夠收集并管理網(wǎng)絡(luò)的全局狀態(tài)信息，包括測(cè)量節(jié)點(diǎn)選擇需要的流傳輸路徑。在一條流的傳輸路徑上，任意一個(gè)ΟpenFlow 交換機(jī)均記錄了該流的統(tǒng)計(jì)信息［5］。控制器每次選擇流信息最多的ΟpenFlow 交換機(jī)作為測(cè)量節(jié)點(diǎn)，直到獲取當(dāng)前網(wǎng)絡(luò)中全部流信息［6］。為避免攻擊者通過(guò)流傳輸路徑推斷敏感信息，在注重隱私保護(hù)的SDN 場(chǎng)景中，通常采取多路徑技術(shù)［7］防止機(jī)密信息泄露。如果獲取的流傳輸路徑不精確，那么SDN 網(wǎng)絡(luò)只能基于網(wǎng)絡(luò)拓?fù)涞闹行男灾笜?biāo)［8］進(jìn)行測(cè)量節(jié)點(diǎn)選擇，此時(shí)精度越高的流量測(cè)量耗費(fèi)的測(cè)量資源越多。單個(gè)中心性最高的測(cè)量節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)行為特征進(jìn)行估計(jì)，大幅降低了測(cè)量資源的開(kāi)銷，但是部分流統(tǒng)計(jì)信息監(jiān)測(cè)不準(zhǔn)確，使得估計(jì)誤差較大；選擇全部網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)行為特征進(jìn)行估計(jì)，不僅增加控制器輪詢?chǔ)痯enFlow 交換機(jī)的頻率，而且相鄰測(cè)量節(jié)點(diǎn)間的流統(tǒng)計(jì)存在較大重復(fù)的問(wèn)題。因此，采用最少測(cè)量節(jié)點(diǎn)覆蓋全部流信息是測(cè)量節(jié)點(diǎn)選擇的趨勢(shì)［9-10］，以實(shí)現(xiàn)測(cè)量資源和準(zhǔn)確性的平衡。

SDN 中基于網(wǎng)絡(luò)拓?fù)涞臏y(cè)量節(jié)點(diǎn)選擇問(wèn)題，可以抽象成最小頂點(diǎn)覆蓋模型，即尋找無(wú)向圖頂點(diǎn)集的最小子集，使其包含圖中任一條邊的至少一個(gè)端點(diǎn)。文獻(xiàn)［11］指出，最小頂點(diǎn)覆蓋模型是NP-Hard的，不可能在小于1.360 6 的復(fù)雜度因子內(nèi)近似求解，研究人員分別采用分支界限法［12］、貪心算法［13］、元啟發(fā)式算法［14］和局部搜索算法［15］對(duì)該抽象模型進(jìn)行求解。然而這些算法均存在一定不足。分支界限法能夠獲取模型的最優(yōu)解，但是其復(fù)雜度高使得算法在大規(guī)模無(wú)向圖中的運(yùn)行時(shí)間無(wú)法預(yù)估。貪心算法顯著降低問(wèn)題復(fù)雜度，但是局部的最優(yōu)決策不一定能夠達(dá)到全局最優(yōu)，并且誤差隨圖的規(guī)模逐漸增大。蟻群優(yōu)化（Ant Colony Οptimization，ACΟ）作為元啟發(fā)式算法之一，具有正反饋、貪心啟發(fā)兩種機(jī)制和較優(yōu)的魯棒性，但存在收斂過(guò)早、搜索時(shí)間長(zhǎng)等問(wèn)題。屬于局部搜索的鄰域搜索算法（Neighborhood Search，NS）目標(biāo)在于優(yōu)化某個(gè)特定頂點(diǎn)而不是整個(gè)無(wú)向圖，能夠有效縮短搜索時(shí)間，但前提是問(wèn)題的初始解較準(zhǔn)確。

現(xiàn)有SDN 測(cè)量節(jié)點(diǎn)選擇方案對(duì)測(cè)量節(jié)點(diǎn)狀態(tài)的考慮有所欠缺［16-17］，對(duì)不同位置的ΟpenFlow 交換機(jī)施加了不均勻的測(cè)量負(fù)載，最佳的測(cè)量結(jié)果可能導(dǎo)致不均勻的網(wǎng)絡(luò)負(fù)載分布。在真實(shí)環(huán)境中的網(wǎng)絡(luò)設(shè)備，同一時(shí)間運(yùn)行著多個(gè)測(cè)量任務(wù)，處理性能和內(nèi)存容量消耗較大，如果繼續(xù)向其下發(fā)測(cè)量任務(wù)，該設(shè)備的測(cè)量負(fù)載維持在較高水平，可能會(huì)出現(xiàn)宕機(jī)現(xiàn)象［18］。控制器利用ΟpenFlow 消息查詢?chǔ)痯enFlow 交換機(jī)的計(jì)數(shù)器，需要綜合考慮查詢頻率和測(cè)量精度。文獻(xiàn)［19］指出，CPU 吞吐量和三態(tài)內(nèi)容尋址存儲(chǔ)器（Ternary Content Addressable Memory，TCAM）容量是制約ΟpenFlow 交換機(jī)性能的兩大因素，在當(dāng)前高帶寬環(huán)境下尤為明顯。因此，測(cè)量節(jié)點(diǎn)的負(fù)載因素應(yīng)納入SDN 測(cè)量節(jié)點(diǎn)選擇問(wèn)題的范疇。

針對(duì)流路徑信息獲取受限的SDN 場(chǎng)景，本文提出一種基于蟻群優(yōu)化的網(wǎng)絡(luò)測(cè)量節(jié)點(diǎn)選擇算法。通過(guò)對(duì)ACΟ 算法的概率狀態(tài)轉(zhuǎn)移規(guī)則和信息素更新規(guī)則進(jìn)行優(yōu)化，利用ΟpenFlow 消息在線監(jiān)控測(cè)量節(jié)點(diǎn)的負(fù)載，使用鄰域搜索策略替換負(fù)載超過(guò)閾值的測(cè)量點(diǎn)，從而在保證準(zhǔn)確性的前提下提高ACΟ 算法的收斂度，縮短搜索時(shí)間。

1 相關(guān)工作

網(wǎng)絡(luò)測(cè)量節(jié)點(diǎn)選擇是網(wǎng)絡(luò)管理工作的基礎(chǔ)。隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，研究人員提出各種智能選擇算法，例如ACΟ 算法，但都局限于特定場(chǎng)景。

對(duì)于抽象的最小頂點(diǎn)覆蓋模型，ACΟ 算法能夠提高測(cè)量節(jié)點(diǎn)集合的準(zhǔn)確性，但也存在局部最優(yōu)、搜索時(shí)間長(zhǎng)等問(wèn)題，可以從概率狀態(tài)轉(zhuǎn)移和信息素更新2 個(gè)規(guī)則進(jìn)行優(yōu)化。此外，較優(yōu)的魯棒性使得ACΟ 算法可以結(jié)合其他算法的優(yōu)勢(shì)，彌補(bǔ)其自身不足［20］。

針對(duì)概率狀態(tài)轉(zhuǎn)移規(guī)則，文獻(xiàn)［21］使用輪盤賭的選擇方式構(gòu)造可行解，摒棄了傳統(tǒng)ACΟ 算法的α、β雙參數(shù)方案，使得計(jì)算復(fù)雜度降至Ο（1），避免了局部最優(yōu)現(xiàn)象的發(fā)生，然而降低信息素的重要程度可能導(dǎo)致算法收斂速度過(guò)慢。文獻(xiàn)［22］在概率狀態(tài)轉(zhuǎn)移規(guī)則中引入故障排除因子，盡可能避免選擇網(wǎng)絡(luò)中的故障節(jié)點(diǎn)，以增加可行解搜索的多樣性，從而提高算法的準(zhǔn)確度。文獻(xiàn)［23］提出現(xiàn)有概率狀態(tài)轉(zhuǎn)移規(guī)則容易導(dǎo)致局部最優(yōu)解，需要設(shè)置平衡參數(shù)進(jìn)行動(dòng)態(tài)調(diào)整：初始時(shí)平衡參數(shù)值較大，螞蟻傾向于選擇信息素濃度高的節(jié)點(diǎn)；迭代數(shù)次后降低平衡參數(shù)的值，螞蟻選擇信息素濃度低的節(jié)點(diǎn)，從而避免局部最優(yōu)；最后再次提高平衡參數(shù)的值，從而加快算法收斂過(guò)程。

針對(duì)信息素更新規(guī)則，文獻(xiàn)［24］表明，部分異常節(jié)點(diǎn)可能影響全局最優(yōu)解的質(zhì)量，提出一種排除異常節(jié)點(diǎn)的信息素更新規(guī)則，以篩選迭代最優(yōu)解中信息素異常的節(jié)點(diǎn)，后續(xù)迭代優(yōu)先選擇正常節(jié)點(diǎn)，從而將螞蟻引導(dǎo)到新的搜索區(qū)域。文獻(xiàn)［21］表明，當(dāng)信息素?fù)]發(fā)系數(shù)為常值時(shí)，算法對(duì)于信息素較低節(jié)點(diǎn)的搜索能力較低，因此提出一種信息素動(dòng)態(tài)揮發(fā)機(jī)制，每次迭代后，揮發(fā)系數(shù)根據(jù)信息素濃度動(dòng)態(tài)變化。文獻(xiàn)［25］構(gòu)建一種改進(jìn)最大最小螞蟻系統(tǒng)（Max-Min Ant System，MMAS），以避免結(jié)果陷入局部最優(yōu)解，將頂點(diǎn)信息素初始為最大值，在蟻群搜索過(guò)程中，信息素被嚴(yán)格限制在最值范圍內(nèi)，每次迭代后僅更新迭代最優(yōu)解或全局最優(yōu)解中頂點(diǎn)的信息素。然而這些信息素更新規(guī)則無(wú)法兼顧算法的準(zhǔn)確性和收斂性，在SDN 測(cè)量節(jié)點(diǎn)選擇問(wèn)題的應(yīng)用效果不佳。

現(xiàn)有SDN 測(cè)量方案中均考慮了測(cè)量節(jié)點(diǎn)選擇問(wèn)題，利用有限測(cè)量資源實(shí)現(xiàn)較優(yōu)的測(cè)量精度，但是尚未考慮測(cè)量節(jié)點(diǎn)的過(guò)載現(xiàn)象。文獻(xiàn)［26］將控制器作為測(cè)量節(jié)點(diǎn)，考慮部署多個(gè)測(cè)量節(jié)點(diǎn)來(lái)測(cè)量網(wǎng)絡(luò)參數(shù)的問(wèn)題，分析變量特征后轉(zhuǎn)換為0-1 線性規(guī)劃問(wèn)題，并提出一種基于拉格朗日松弛的動(dòng)態(tài)規(guī)劃算法。該算法能夠有效降低不同網(wǎng)絡(luò)拓?fù)湎碌臏y(cè)量成本和運(yùn)行時(shí)間。大多數(shù)SDN 測(cè)量方案從ΟpenFlow 交換機(jī)中采集流量信息，如果流路由信息獲取不受限制，文獻(xiàn)［5］提出5 種查詢策略，分別為流路徑上最后、均勻隨機(jī)、輪詢、非均勻隨機(jī)和負(fù)載最少的單個(gè)交換機(jī)，它們對(duì)網(wǎng)絡(luò)設(shè)備施加不均勻的負(fù)載且難以擴(kuò)展到大規(guī)模網(wǎng)絡(luò)。文獻(xiàn)［6］和文獻(xiàn)［27］均采用貪心策略選擇多個(gè)測(cè)量節(jié)點(diǎn)，其原理是第1 輪迭代選擇流數(shù)最多的一個(gè)節(jié)點(diǎn)，將第1 個(gè)測(cè)量節(jié)點(diǎn)關(guān)聯(lián)的流從流矩陣中刪除，后續(xù)迭代重復(fù)選擇點(diǎn)-刪流過(guò)程，直到流矩陣不包含任何流時(shí)停止，以得到1 個(gè)測(cè)量節(jié)點(diǎn)集合。然而在實(shí)際網(wǎng)絡(luò)環(huán)境中流的數(shù)量通常較大，如106條，使得持續(xù)統(tǒng)計(jì)并更新流矩陣的時(shí)間開(kāi)銷不可忽略。

在流路徑信息獲取受限的情況下，SDN 網(wǎng)絡(luò)測(cè)量節(jié)點(diǎn)選擇問(wèn)題只能依賴于網(wǎng)絡(luò)的物理拓?fù)洹Ｎ墨I(xiàn)［27］借助社交網(wǎng)絡(luò)的中心性指標(biāo)度量圖節(jié)點(diǎn)的重要性，提出3 種基于中心性的單個(gè)測(cè)量節(jié)點(diǎn)選擇方案：介數(shù)中心性，接近中心性和度中心性。然而單點(diǎn)測(cè)量能夠節(jié)約測(cè)量資源，但是測(cè)量準(zhǔn)確度低。因此，該文獻(xiàn)又提出一種基于擴(kuò)展中心性的多測(cè)量節(jié)點(diǎn)選擇算法。該算法基于介數(shù)中心性選擇第1 個(gè)測(cè)量節(jié)點(diǎn)，后續(xù)測(cè)量節(jié)點(diǎn)在其鄰接點(diǎn)中按照最短路徑重疊最少規(guī)則進(jìn)行選擇。

根據(jù)以上研究和分析，SDN 網(wǎng)絡(luò)下測(cè)量節(jié)點(diǎn)選擇算法存在以下問(wèn)題：1）隱私保護(hù)場(chǎng)景下流路徑信息獲取受限，基于流的測(cè)量節(jié)點(diǎn)選擇方案失效；2）單個(gè)測(cè)量點(diǎn)采集的流統(tǒng)計(jì)信息不全面，導(dǎo)致測(cè)量精度較低；3）基于擴(kuò)展中心性的多測(cè)量節(jié)點(diǎn)選擇算法未考慮測(cè)量點(diǎn)的負(fù)載因素，實(shí)際測(cè)量效果較差。因此，本文在SDN 網(wǎng)絡(luò)中基于網(wǎng)絡(luò)拓?fù)溥M(jìn)行測(cè)量節(jié)點(diǎn)選擇，改進(jìn)ACΟ 算法的概率狀態(tài)轉(zhuǎn)移規(guī)則和信息素更新規(guī)則，分別提高模型結(jié)果的準(zhǔn)確性和收斂性，增加一種基于NS 策略的過(guò)載處理機(jī)制局部調(diào)整滿足條件的測(cè)量節(jié)點(diǎn)，在不破壞鏈路覆蓋率的情況下，縮短過(guò)載處理時(shí)間。

2 SDN 中基于蟻群優(yōu)化的測(cè)量節(jié)點(diǎn)選擇算法

基于蟻群優(yōu)化的測(cè)量節(jié)點(diǎn)選擇算法的參數(shù)信息如表1 所示。

表1 基于蟻群優(yōu)化的測(cè)量節(jié)點(diǎn)選擇算法的參數(shù)信息Table 1 Parameters information of measurement node selection algorithm based on ant colony optimization

2.1 SDN 網(wǎng)絡(luò)中測(cè)量節(jié)點(diǎn)選擇方案

網(wǎng)絡(luò)測(cè)量節(jié)點(diǎn)選擇的SDN 架構(gòu)如圖1 所示。基于蟻群優(yōu)化的測(cè)量節(jié)點(diǎn)選擇方案部署在SDN 應(yīng)用層，包括拓?fù)浒l(fā)現(xiàn)、節(jié)點(diǎn)搜索、負(fù)載監(jiān)測(cè)和過(guò)載處理4 個(gè)模塊，同一模塊流向其他模塊的數(shù)據(jù)相同。

圖1 網(wǎng)絡(luò)測(cè)量節(jié)點(diǎn)選擇的SDN 架構(gòu)Fig.1 SDN framework for network measurement node selection

基于蟻群優(yōu)化的測(cè)量節(jié)點(diǎn)選擇方案的具體流程為：1）拓?fù)浒l(fā)現(xiàn)模塊通過(guò)鏈路發(fā)現(xiàn)機(jī)制的REST-API獲取模擬網(wǎng)絡(luò)的所有交換機(jī)和鏈路，匯總成網(wǎng)絡(luò)拓?fù)鋱D；2）節(jié)點(diǎn)搜索模塊利用改進(jìn)ACΟ 算法搜索graph 的初始測(cè)量集；3）負(fù)載監(jiān)測(cè)模塊通過(guò)Packet-in消息觸發(fā)機(jī)制和流表統(tǒng)計(jì)接口在線計(jì)算selects 中節(jié)點(diǎn)的負(fù)載，若監(jiān)測(cè)值超過(guò)閾值δ，該測(cè)量點(diǎn)被添加到過(guò)載測(cè)量集；4）過(guò)載處理模塊利用NS 策略將loads中滿足覆蓋條件的過(guò)載測(cè)量點(diǎn)從selects 中刪除，最終得到給定無(wú)向圖的優(yōu)化測(cè)量集updates。

2.2 ACO 算法的規(guī)則改進(jìn)

在無(wú)向圖G=(V,Ε)中，V和Ε分別表示頂點(diǎn)集和邊集，覆蓋Ε中每條邊的頂點(diǎn)集合是V的子集，最小頂點(diǎn)覆蓋M要求該子集包含的頂點(diǎn)最少。假設(shè)其中過(guò)載頂點(diǎn)的鄰接矩陣為S，附加負(fù)載的最小頂點(diǎn)覆蓋要求使得M包含最少數(shù)量的過(guò)載頂點(diǎn)。

ACΟ 算法的規(guī)則改進(jìn)是采用ACΟ-NS 算法求解附加負(fù)載因素的最小頂點(diǎn)覆蓋模型，首先ACΟ 算法從圖G中搜索出最小頂點(diǎn)覆蓋M，然后NS 算法結(jié)合鄰接矩陣S得到最小狀態(tài)頂點(diǎn)覆蓋M′，基于蟻群優(yōu)化的網(wǎng)絡(luò)測(cè)量節(jié)點(diǎn)選擇算法流程如圖2 所示。

圖2 基于蟻群優(yōu)化的網(wǎng)絡(luò)測(cè)量節(jié)點(diǎn)選擇算法流程Fig.2 Procedure of network measurement node selection algorithm based on ant colony optimization

對(duì)于ACΟ 算法，本文主要改進(jìn)概率狀態(tài)轉(zhuǎn)移過(guò)程中的候選集定義，對(duì)信息素更新過(guò)程的優(yōu)化體現(xiàn)在局部增強(qiáng)和全局揮發(fā)2 個(gè)子過(guò)程；而對(duì)NS 算法優(yōu)化主要分為構(gòu)造篩選、替換和冗余檢驗(yàn)3 個(gè)操作，處理測(cè)量節(jié)點(diǎn)的過(guò)載現(xiàn)象。

2.2.1 概率狀態(tài)轉(zhuǎn)移優(yōu)化

在概率狀態(tài)轉(zhuǎn)移過(guò)程中，候選集動(dòng)態(tài)減小為空，每次根據(jù)概率選擇一個(gè)頂點(diǎn)后，從候選集中刪除點(diǎn)和度均為0 的頂點(diǎn)。網(wǎng)絡(luò)拓?fù)漤旤c(diǎn)的度通常服從以下分布［28］：僅部分節(jié)點(diǎn)的度明顯較大，多數(shù)節(jié)點(diǎn)的度在3 附近。但是原始候選集更新策略還存在一定的不足：螞蟻不斷構(gòu)造初始測(cè)量集，所選頂點(diǎn)的鄰接點(diǎn)的度逐漸減小為1，在信息素和啟發(fā)信息的作用下，它們得不到及時(shí)處理。仿真結(jié)果表明，假設(shè)無(wú)向圖規(guī)模為n，度為1 頂點(diǎn)的數(shù)量隨著螞蟻搜索次數(shù)增加而增加。區(qū)間內(nèi)按正態(tài)曲線增大到，而區(qū)間內(nèi)以線性關(guān)系降低到0。因此，未處理的度為1 的頂點(diǎn)近似為，概率狀態(tài)計(jì)算的時(shí)間復(fù)雜度和空間復(fù)雜度均為Ο（n2）。

螞蟻每次選擇一個(gè)頂點(diǎn)后，新候選集更新策略在原始候選集更新策略的基礎(chǔ)上繼續(xù)刪除度為1 的頂點(diǎn)。假設(shè)當(dāng)前候選集用C表示，則新候選集更新策略的數(shù)學(xué)描述如式（1）所示：

其中：CP為上次更新后的候選集；s為所選頂點(diǎn)；V0為度為0的頂點(diǎn)構(gòu)成集合；集合V1包含所有度為1的頂點(diǎn)。

根據(jù)新候選集更新策略，ACΟ 算法的概率狀態(tài)轉(zhuǎn)移規(guī)則進(jìn)行了相應(yīng)調(diào)整。候選集劃分為優(yōu)選集和計(jì)算集。優(yōu)選集由度為1 頂點(diǎn)的鄰接點(diǎn)構(gòu)成的集合，計(jì)算集是當(dāng)前候選集中優(yōu)選集的補(bǔ)集，必須保證優(yōu)選集的優(yōu)先級(jí)。在某次迭代中，如果螞蟻先選擇計(jì)算集的頂點(diǎn)，由于會(huì)刪除關(guān)聯(lián)的邊，可能使優(yōu)選集中頂點(diǎn)的度為0，導(dǎo)致優(yōu)選集頂點(diǎn)被候選集更新策略刪除。度為1 的頂點(diǎn)與鄰接點(diǎn)的邊沒(méi)有被selects 覆蓋，進(jìn)而影響模型結(jié)果的準(zhǔn)確性。優(yōu)選集頂點(diǎn)的選擇概率恒定為1，而計(jì)算集頂點(diǎn)的選擇概率由信息素濃度和啟發(fā)信息值計(jì)算得到。假設(shè)優(yōu)選集、計(jì)算集分別為F和R，螞蟻k選擇頂點(diǎn)νi的概率為pki，則調(diào)整后的概率狀態(tài)轉(zhuǎn)移規(guī)則如式（2）所示：

其中：τi為頂點(diǎn)的信息素濃度，初始值設(shè)為1，不構(gòu)成頂點(diǎn)選擇的元素，其值隨蟻群的搜索逐漸增大；α為信息素指數(shù)，用于衡量信息素相對(duì)于啟發(fā)信息的重要程度，指數(shù)較傳統(tǒng)α、β雙因子方案平均降低了3.63；Ο（n2）數(shù)量級(jí)的度為1 頂點(diǎn)執(zhí)行概率狀態(tài)轉(zhuǎn)移規(guī)則的計(jì)算開(kāi)銷較大；ηi為頂點(diǎn)的啟發(fā)信息值。鄰接點(diǎn)被選擇使得頂點(diǎn)的度減少一個(gè)單位，實(shí)際上是頂點(diǎn)動(dòng)態(tài)變化的度，參數(shù)值的計(jì)算如式（3）所示：

當(dāng)計(jì)算集頂點(diǎn)和優(yōu)選集頂點(diǎn)的選擇概率相同時(shí)，螞蟻極有可能選擇計(jì)算集中的頂點(diǎn)，破壞規(guī)定的優(yōu)先級(jí)。通過(guò)將概率狀態(tài)轉(zhuǎn)移規(guī)則的分母增加1，使得計(jì)算集的概率狀態(tài)始終小于優(yōu)選集，以確保模型結(jié)果的準(zhǔn)確性。

2.2.2 信息素更新優(yōu)化

信息素是自然界螞蟻間交互的介質(zhì)，螞蟻經(jīng)過(guò)節(jié)點(diǎn)或路徑會(huì)釋放一定濃度的信息素，但是信息素濃度隨時(shí)間的增加不斷降低。因此，信息素更新因素包括信息素增強(qiáng)和信息素?fù)]發(fā)。由于信息素更新因素的觸發(fā)時(shí)機(jī)不同，因此構(gòu)成了不同的ACΟ 算法，正反饋機(jī)制強(qiáng)弱也存在一定的差異。全局更新和局部更新是信息素策略的典型執(zhí)行時(shí)機(jī)，局部更新指螞蟻構(gòu)造一個(gè)可行解結(jié)束后，全局更新則發(fā)生在蟻群搜索到迭代最優(yōu)解。結(jié)合信息素更新因素和觸發(fā)時(shí)機(jī)，本文提出一種信息素局部增強(qiáng)-全局揮發(fā)規(guī)則，增大可行解的信息素濃度，使得螞蟻趨向于局部最優(yōu)軌跡，以減少算法的迭代次數(shù)，從而有效解決蟻群搜索時(shí)間較長(zhǎng)的問(wèn)題。通過(guò)動(dòng)態(tài)降低迭代解的信息素，并適當(dāng)增加蟻群的搜索面，使得全局解與模型最優(yōu)解的偏差逐漸減小。

信息素局部增強(qiáng)發(fā)生在螞蟻構(gòu)造出一個(gè)可行解，無(wú)論可行解是否最優(yōu)，其相關(guān)節(jié)點(diǎn)的信息素均適當(dāng)增加。節(jié)點(diǎn)νi在第t+1 次迭代中信息素濃度如式（4）所示：

信息素局部增強(qiáng)為充分建立ACΟ 算法的正反饋機(jī)制，通過(guò)當(dāng)前螞蟻增強(qiáng)潛在最優(yōu)節(jié)點(diǎn)的信息素，指導(dǎo)蟻群中的其他螞蟻，以構(gòu)造較優(yōu)解。

每當(dāng)蟻群迭代出一個(gè)局部解時(shí)，執(zhí)行信息素全局揮發(fā)子策略。根據(jù)迭代解降低相關(guān)節(jié)點(diǎn)νj的信息素濃度，如式（5）所示：

2.3 測(cè)量點(diǎn)過(guò)載處理機(jī)制

2.3.1 OpenFlow 交換機(jī)負(fù)載監(jiān)測(cè)

測(cè)量點(diǎn)過(guò)載處理機(jī)制主要監(jiān)測(cè)selects 中測(cè)量點(diǎn)的負(fù)載，在實(shí)際SDN 環(huán)境中，在線獲取ΟpenFlow 交換機(jī)的負(fù)載。在不同場(chǎng)景下，交換機(jī)負(fù)載的定義和監(jiān)測(cè)方式有所不同，由于CPU 吞吐量和TCAM 容量是SDN 交換機(jī)的兩大性能瓶頸，ΟpenFlow 交換機(jī)的負(fù)載lload如式（6）所示：

其中：TCPU和UTCAM分別為測(cè)量點(diǎn)的CPU 吞吐率和TCAM 使用率。因此，測(cè)量點(diǎn)負(fù)載監(jiān)測(cè)分為統(tǒng)計(jì)CPU 吞吐率和TCAM 使用率。

在SDN 交換機(jī)中，CPU 主要用于處理各種ΟpenFlow 消息，其中Packet-in 消息參與多種報(bào)文處理機(jī)制。假設(shè)單個(gè)交換機(jī)單位時(shí)間內(nèi)發(fā)送的Packet-in消息數(shù)量為in_count，根據(jù)SDN 特性，該指標(biāo)是有限的。CPU 吞吐率計(jì)算的關(guān)鍵在于控制器統(tǒng)計(jì)單位時(shí)間內(nèi)指定交換機(jī)發(fā)送的Packet-in 消息數(shù)。控制器解析Packet-in 消息，獲取指定交換機(jī)對(duì)應(yīng)的dpid 標(biāo)識(shí)，進(jìn)而根據(jù)dpid 對(duì)Packet-in 消息進(jìn)行累加。截止統(tǒng)計(jì)時(shí)間，控制器輸出指定交換機(jī)的Packet-in 消息數(shù)in_count。因此，CPU 吞吐率由in_count 與in_max 比值計(jì)算得到，如式（7）所示：

在ΟpenFlow 交換機(jī)中，TCAM 用于存儲(chǔ)流表項(xiàng)，而流表項(xiàng)是交換節(jié)點(diǎn)處理數(shù)據(jù)包的依據(jù)。從成本和功耗兩個(gè)方面考慮，TCAM 存儲(chǔ)器支持的流表項(xiàng)數(shù)量有限，假設(shè)最大流表項(xiàng)數(shù)為entry_volumn。交換機(jī)當(dāng)前使用的流表項(xiàng)數(shù)在一定程度上反映了其負(fù)載狀態(tài)。

ΟpenFlow 協(xié)議提供流表統(tǒng)計(jì)機(jī)制，包括TableStatsRequest 和TableStatsReply 消息。控制器向交換機(jī)發(fā)送不包含數(shù)據(jù)的TableStatsRequest消息，交換機(jī)回復(fù)TableStatsReply 消息給控制器，TableStatsReply消息體結(jié)構(gòu)如下：

active_count 字段指示單個(gè)流表中活躍的流表項(xiàng)數(shù)，累加所有流表的active_count 字段值，可以得到整個(gè)交換機(jī)當(dāng)前占用流表項(xiàng)數(shù)entry_current。

因此，TCAM 使用率是當(dāng)前占用流表項(xiàng)數(shù)與最大流表項(xiàng)數(shù)的比值，如式（8）所示：

ΟpenFlow 交換機(jī)在線獲取測(cè)量節(jié)點(diǎn)的負(fù)載后，需要進(jìn)一步判斷該節(jié)點(diǎn)的狀態(tài)是否異常。假設(shè)負(fù)載閾值δ=0.8，若式（6）計(jì)算的負(fù)載大于δ，該測(cè)量節(jié)點(diǎn)不適合下發(fā)測(cè)量任務(wù)，添加到loads 后，等待過(guò)載處理模塊篩選并替換。

2.3.2 基于NS 的過(guò)載處理機(jī)制

測(cè)量點(diǎn)過(guò)載處理規(guī)則的相關(guān)假設(shè)是在短時(shí)間內(nèi)網(wǎng)絡(luò)拓?fù)洳粫?huì)發(fā)生大規(guī)模變化，并且負(fù)載主要發(fā)生在測(cè)量節(jié)點(diǎn)。隨著網(wǎng)絡(luò)測(cè)量持續(xù)運(yùn)行，測(cè)量節(jié)點(diǎn)可能出現(xiàn)過(guò)載現(xiàn)象，需要重新執(zhí)行ACΟ 算法等。然而全局搜索算法將耗費(fèi)大量資源，同時(shí)時(shí)間開(kāi)銷較大。NS 策略在初始解的基礎(chǔ)上執(zhí)行添加、刪除和交換等操作，以獲取最優(yōu)解。NS 策略存在平衡測(cè)量資源和時(shí)間的可能，應(yīng)用在最小頂點(diǎn)覆蓋模型時(shí)，還可以兼顧鏈路覆蓋率。

如果2 個(gè)過(guò)載測(cè)量點(diǎn)由一條邊連接，則定義這種邊為過(guò)載邊。過(guò)載節(jié)點(diǎn)可以集中替換的節(jié)點(diǎn)取決于過(guò)載邊的統(tǒng)計(jì)結(jié)果，如果沒(méi)有過(guò)載邊，則替換整個(gè)過(guò)載節(jié)點(diǎn)集；否則不斷篩選覆蓋最多過(guò)載邊的負(fù)載異常的測(cè)量節(jié)點(diǎn)，刪除已覆蓋過(guò)載邊，直到刪除完全，過(guò)載節(jié)點(diǎn)集中的剩余節(jié)點(diǎn)作為替換節(jié)點(diǎn)。

鏈路覆蓋率維持的關(guān)鍵是NS 策略的替換過(guò)程。基于網(wǎng)絡(luò)拓?fù)鋱D構(gòu)造每個(gè)替換測(cè)量點(diǎn)的鄰域，即所有鄰接點(diǎn)構(gòu)成的集合，若某個(gè)鄰接點(diǎn)不在selects 中，則將其添加到初始測(cè)量集。整個(gè)鄰域遍歷結(jié)束后，從初始測(cè)量集刪除對(duì)應(yīng)替換測(cè)量點(diǎn)。替換過(guò)程結(jié)束，selects 還需要進(jìn)一步處理。

冗余覆蓋檢驗(yàn)的目的在于降低模型結(jié)果的鏈路的冗余度。如果selects 中每個(gè)測(cè)量點(diǎn)鄰域被包含在更新的初始測(cè)量集中，說(shuō)明該測(cè)量點(diǎn)與所有鄰接點(diǎn)間的邊被重復(fù)覆蓋，直接將該測(cè)量點(diǎn)從初始測(cè)量集中刪除，在不影響鏈路覆蓋率的情況下，能夠降低模型結(jié)果的冗余度，從而優(yōu)化測(cè)量集。

測(cè)量點(diǎn)過(guò)載處理后的updates 包含最少數(shù)量的過(guò)載測(cè)量點(diǎn)，算法1 是鄰域搜索策略的偽代碼。

算法1鄰域搜索策略

算法1 的原理是1 個(gè)雙層循環(huán)結(jié)構(gòu)（步驟2～7），外層循環(huán)控制當(dāng)前訪問(wèn)的替換測(cè)量點(diǎn)，而內(nèi)層循環(huán)遍歷該替換測(cè)量點(diǎn)的鄰域，除selects 以外的鄰接點(diǎn)被添加到初始測(cè)量集，遍歷結(jié)束，再刪除該替換測(cè)量點(diǎn)。假設(shè)n表示替換測(cè)量點(diǎn)的數(shù)目，根據(jù)分析可得，算法的時(shí)間復(fù)雜度是Ο（n2），由于需要記錄每個(gè)替換測(cè)量點(diǎn)的鄰接點(diǎn)信息，算法的空間復(fù)雜度也是Ο（n2）。

3 實(shí)驗(yàn)與分析

本節(jié)從實(shí)驗(yàn)設(shè)置、規(guī)則優(yōu)化效果和仿真拓?fù)潋?yàn)證3 個(gè)方面對(duì)SDN 中基于蟻群優(yōu)化的網(wǎng)絡(luò)測(cè)量節(jié)點(diǎn)選擇算法進(jìn)行評(píng)估。

3.1 實(shí)驗(yàn)環(huán)境與基本參數(shù)

3.60GHz、16 GB RAM 的4核Windows 10主機(jī)作為硬件環(huán)境，SDN 平臺(tái)基于Ubuntu16.04 系統(tǒng)搭建，使用開(kāi)源控制器Ryu-4.32，拓?fù)浞抡嫫鞑捎肕ininet-2.3.0d6，軟件交換機(jī)為Οpen vSwitch-2.11.0，算法相關(guān)模塊由Python 語(yǔ)言實(shí)現(xiàn)。

算法輸入的3 種無(wú)向圖參數(shù)信息如表2 所示，最小測(cè)量數(shù)是無(wú)向圖可以部署測(cè)量節(jié)點(diǎn)的最少數(shù)量。

表2 不同規(guī)模無(wú)向圖的參數(shù)信息Table 2 Parameters information of undirected graphs with different scales

ACΟ 算法的參數(shù)空間比較復(fù)雜，參數(shù)取值與算法的驗(yàn)證結(jié)果相關(guān)，通過(guò)參考文獻(xiàn)或簡(jiǎn)單實(shí)驗(yàn)確定算法的參數(shù)，如表3 所示。其中：iterate 表示算法最大迭代次數(shù)；verge 表示算法的收斂條件，即模型解長(zhǎng)度不再減少的連續(xù)迭代次數(shù)；符號(hào)|V|表示無(wú)向圖的頂點(diǎn)數(shù)，算法中螞蟻數(shù)量隨無(wú)向圖規(guī)模發(fā)生變化。

表3 算法的參數(shù)值Table 3 Parameter values of algorithm

3.2 算法規(guī)則的優(yōu)化效果

3.2.1 實(shí)驗(yàn)與數(shù)據(jù)對(duì)比

在算法執(zhí)行過(guò)程中，平均測(cè)量數(shù)是指多個(gè)測(cè)量節(jié)點(diǎn)數(shù)的均值，命中頻數(shù)是命中對(duì)應(yīng)最小測(cè)量數(shù)的次數(shù)，兩者決定算法的準(zhǔn)確性。平均迭代次數(shù)是多次執(zhí)行迭代次數(shù)的均值，與算法收斂性相關(guān)。

第1 組對(duì)比實(shí)驗(yàn)用于驗(yàn)證新候選集定義對(duì)于ACΟ 算法準(zhǔn)確性的改進(jìn)效果，在基本參數(shù)保持一致的條件下，本文采用新候選集定義和原始候選集定義的ACΟ 算法在無(wú)向圖karate、jazz 和email 中進(jìn)行平均測(cè)量數(shù)、命中頻數(shù)和平均迭代數(shù)對(duì)比，各執(zhí)行10 次，結(jié)果如表4 所示。

表4 兩組對(duì)比實(shí)驗(yàn)的統(tǒng)計(jì)數(shù)據(jù)Table 4 Statistical datas of two groups of comparative experiments

第2 組對(duì)比實(shí)驗(yàn)用于驗(yàn)證信息素局部增強(qiáng)-全局揮發(fā)規(guī)則對(duì)ACΟ 算法收斂性的優(yōu)化效果，同理保持基本參數(shù)一致，本文采用信息素局部增強(qiáng)-全局揮發(fā)規(guī)則和MMAS 更新規(guī)則的ACΟ 算法分別在karate、jazz 和email 中執(zhí)行10 次，同樣將第2 組對(duì)比實(shí)驗(yàn)數(shù)據(jù)的結(jié)果統(tǒng)計(jì)到表4。

從表4 可以看出，對(duì)比ACΟ 算法中的典型策略，新候選集定義一定程度上提高了抽象模型的準(zhǔn)確性，而信息素局部增強(qiáng)-全局揮發(fā)規(guī)則主要優(yōu)化抽象模型的收斂性。過(guò)載處理機(jī)制執(zhí)行的前提是無(wú)向圖的初始測(cè)量集，為了保證實(shí)驗(yàn)環(huán)境相同，第3 組對(duì)比實(shí)驗(yàn)采用改進(jìn)ACΟ 算法獲取初始測(cè)量集。基本負(fù)載處理機(jī)制將負(fù)載作為概率狀態(tài)轉(zhuǎn)移規(guī)則的決策因素之一。第3 組對(duì)比實(shí)驗(yàn)中過(guò)載節(jié)點(diǎn)隨機(jī)產(chǎn)生，基本負(fù)載處理機(jī)制與測(cè)量點(diǎn)過(guò)載處理機(jī)制在3 種無(wú)向圖中各執(zhí)行10 次，主要用于驗(yàn)證過(guò)載處理機(jī)制對(duì)時(shí)間的優(yōu)化效果。

圖3 分別記錄2 種負(fù)載處理機(jī)制在無(wú)向圖karate、jazz和email運(yùn)行的測(cè)量節(jié)點(diǎn)數(shù)和運(yùn)行時(shí)間。num_aco、num_ns 分別表示基本負(fù)載處理和測(cè)量點(diǎn)過(guò)載處理機(jī)制的測(cè)量節(jié)點(diǎn)數(shù)；time_aco、time_ns 分別為采用2 種機(jī)制的運(yùn)行時(shí)間，由于jazz 和email圖下兩種負(fù)載處理機(jī)制的運(yùn)行時(shí)間差別很大，因此圖3（b）和圖3（c）中time_ns指標(biāo)非常接近于橫坐標(biāo)。

圖3 不同負(fù)載處理機(jī)制的測(cè)量節(jié)點(diǎn)數(shù)和運(yùn)行時(shí)間對(duì)比Fig.3 Measurement nodes and runtime comparison among different load handling mechanisms

3.2.2 數(shù)據(jù)分析與結(jié)果

本文定義3 種衡量算法的指標(biāo)：準(zhǔn)確性為命中頻數(shù)的平均數(shù)；收斂性是收斂條件與平均迭代數(shù)的比值；單位時(shí)間開(kāi)銷是平均運(yùn)行時(shí)間與無(wú)向圖頂點(diǎn)數(shù)的比值。

對(duì)于表4 中的統(tǒng)計(jì)數(shù)據(jù)，盡管無(wú)向圖規(guī)模不同，新候選集定義的平均測(cè)量數(shù)、平均迭代次數(shù)均小于或等于原始候選集定義，且命中頻數(shù)較大，結(jié)果更接近無(wú)向圖的最小測(cè)量數(shù)。相比MMAS 更新策略，雖然信息素局部增強(qiáng)-全局揮發(fā)規(guī)則增加了平均測(cè)量數(shù)，但是大幅降低了平均迭代數(shù)，在無(wú)向圖email 中更為明顯。從圖4 可以看出，測(cè)量點(diǎn)過(guò)載處理機(jī)制與基本負(fù)載處理機(jī)制的測(cè)量節(jié)點(diǎn)數(shù)比較接近，但是測(cè)量點(diǎn)過(guò)載處理機(jī)制的運(yùn)行時(shí)間具有2～3 個(gè)數(shù)量級(jí)的優(yōu)勢(shì)，并且隨著無(wú)向圖頂點(diǎn)數(shù)增多而增大，其原因?yàn)閷⒇?fù)載因素引入概率轉(zhuǎn)移狀態(tài)規(guī)則中，破壞信息素和啟發(fā)信息的指導(dǎo)作用，增加了算法的運(yùn)行時(shí)間。

因此，新候選集定義顯著提高了ACΟ 算法的準(zhǔn)確性，信息素局部增強(qiáng)-全局揮發(fā)規(guī)則集中改進(jìn)了收斂性，而測(cè)量點(diǎn)過(guò)載處理機(jī)制主要降低了算法的單位時(shí)間開(kāi)銷。若考慮3 種規(guī)則在準(zhǔn)確性、收斂性及單位時(shí)間開(kāi)銷的精確效果，ACΟ 算法與ACΟ-NS 算法的性能指標(biāo)對(duì)比如表5 所示。

表5 ACO 與ACO-NS 算法的性能指標(biāo)對(duì)比Table 5 Performance indexs comparison of ACO and ACO-NS algorithms

從表5 可以看出，相比ACΟ 算法，ACΟ-NS 算法的準(zhǔn)確度和收斂度分別提高了56.7 和28.2 個(gè)百分點(diǎn)，且在單位時(shí)間開(kāi)銷方面降低了79.8 個(gè)百分點(diǎn)。

3.3 SDN 網(wǎng)絡(luò)中不同測(cè)量節(jié)點(diǎn)選擇方案

本節(jié)在SDN 環(huán)境中使用Mininet 工具模擬歐洲光纖網(wǎng)核心拓?fù)洌鐖D4 所示。

圖4 仿真的歐洲光纖網(wǎng)核心拓?fù)銯ig.4 Simulated core topology of European optical fiber network

為評(píng)估單個(gè)中心測(cè)量點(diǎn)、基于擴(kuò)展中心性的多個(gè)測(cè)量點(diǎn)、ACΟ-NS 算法和全部節(jié)點(diǎn)4 種方案的覆蓋率和冗余度，本文定義鏈路的覆蓋率和冗余度。覆蓋率是指所選測(cè)量點(diǎn)覆蓋的鏈路占全部鏈路的比率，冗余度是指測(cè)量節(jié)點(diǎn)重復(fù)覆蓋的鏈路數(shù)量。

仿真的歐洲光纖網(wǎng)核心拓?fù)浒?6 個(gè)節(jié)點(diǎn)、23 條鏈路。假設(shè)單個(gè)中心測(cè)量點(diǎn)選擇度最大的節(jié)點(diǎn)，即single=｛6｝，擴(kuò)展中心性方案的測(cè)量點(diǎn)集合extend=｛11，6，7，4，3，1｝，ACΟ-NS 算法的測(cè)量點(diǎn)集合aco_ns=｛6，4，2，8，10，14，16，12｝，全部節(jié)點(diǎn)方案all 包含該網(wǎng)絡(luò)拓?fù)渲兴泄?jié)點(diǎn)。

不同方案的覆蓋率和冗余度如圖5所示。single方案的覆蓋率和冗余度都是最低的，但是網(wǎng)絡(luò)測(cè)量更關(guān)注覆蓋率，因此single 方案應(yīng)用效果最差。雖然aco_ns和all這2 種方案的覆蓋率均達(dá)到100%，但是all方案的冗余度過(guò)高，流量重復(fù)采集的概率較大。extend 方案能夠以較低的冗余度實(shí)現(xiàn)較高的覆蓋率，但仍存在優(yōu)化的空間，aco_ns方案的冗余度和覆蓋率均優(yōu)于extend方案。因此，ACΟ-NS 算法在基于網(wǎng)絡(luò)拓?fù)涞腟DN 場(chǎng)景下選擇測(cè)量節(jié)點(diǎn)的性能最佳。

圖5 不同方案的覆蓋率和冗余度對(duì)比Fig.5 Coverage and redundancy comparison among different schemes

4 結(jié)束語(yǔ)

本文提出一種基于蟻群優(yōu)化的網(wǎng)絡(luò)測(cè)量節(jié)點(diǎn)選擇算法ACΟ-NS，利用CPU 吞吐率和三態(tài)內(nèi)容尋址存儲(chǔ)器在線監(jiān)測(cè)測(cè)量交換機(jī)的負(fù)載，為SDN 環(huán)境中網(wǎng)絡(luò)測(cè)量節(jié)點(diǎn)選擇提供理論依據(jù)，通過(guò)優(yōu)化概率狀態(tài)轉(zhuǎn)移規(guī)則和信息素更新規(guī)則，提高測(cè)量集的收斂度，同時(shí)僅對(duì)過(guò)載的測(cè)量交換機(jī)進(jìn)行鄰域搜索，有效縮短調(diào)整負(fù)載的時(shí)間。實(shí)驗(yàn)結(jié)果表明，相比ACΟ 算法，ACΟ-NS 算法的準(zhǔn)確度提高了56.7個(gè)百分點(diǎn)，單位時(shí)間開(kāi)銷降低79.8個(gè)百分點(diǎn)，能夠有效提高SDN 控制器的工作效率，從而降低負(fù)載對(duì)網(wǎng)絡(luò)測(cè)量結(jié)果的影響。后續(xù)將基于不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分析測(cè)量點(diǎn)選擇與流長(zhǎng)分布估計(jì)的關(guān)系，進(jìn)一步優(yōu)化算法設(shè)計(jì)。