SDN 中基于蟻群優化的網絡測量節點選擇算法

葉和元，韓 俐，孫士民

（1.天津理工大學 計算機科學與工程學院，天津 300384；2.天津工業大學 計算機科學與技術學院，天津 300387）

0 概述

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

SDN 網絡的控制平面和數據平面是解耦合的，控制器能夠收集并管理網絡的全局狀態信息，包括測量節點選擇需要的流傳輸路徑。在一條流的傳輸路徑上，任意一個ΟpenFlow 交換機均記錄了該流的統計信息［5］。控制器每次選擇流信息最多的ΟpenFlow 交換機作為測量節點，直到獲取當前網絡中全部流信息［6］。為避免攻擊者通過流傳輸路徑推斷敏感信息，在注重隱私保護的SDN 場景中，通常采取多路徑技術［7］防止機密信息泄露。如果獲取的流傳輸路徑不精確，那么SDN 網絡只能基于網絡拓撲的中心性指標［8］進行測量節點選擇，此時精度越高的流量測量耗費的測量資源越多。單個中心性最高的測量節點對網絡行為特征進行估計，大幅降低了測量資源的開銷，但是部分流統計信息監測不準確，使得估計誤差較大；選擇全部網絡節點對網絡行為特征進行估計，不僅增加控制器輪詢ΟpenFlow 交換機的頻率，而且相鄰測量節點間的流統計存在較大重復的問題。因此，采用最少測量節點覆蓋全部流信息是測量節點選擇的趨勢［9-10］，以實現測量資源和準確性的平衡。

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

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

針對流路徑信息獲取受限的SDN 場景，本文提出一種基于蟻群優化的網絡測量節點選擇算法。通過對ACΟ 算法的概率狀態轉移規則和信息素更新規則進行優化，利用ΟpenFlow 消息在線監控測量節點的負載，使用鄰域搜索策略替換負載超過閾值的測量點，從而在保證準確性的前提下提高ACΟ 算法的收斂度，縮短搜索時間。

1 相關工作

網絡測量節點選擇是網絡管理工作的基礎。隨著網絡技術的發展，研究人員提出各種智能選擇算法，例如ACΟ 算法，但都局限于特定場景。

對于抽象的最小頂點覆蓋模型，ACΟ 算法能夠提高測量節點集合的準確性，但也存在局部最優、搜索時間長等問題，可以從概率狀態轉移和信息素更新2 個規則進行優化。此外，較優的魯棒性使得ACΟ 算法可以結合其他算法的優勢，彌補其自身不足［20］。

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

針對信息素更新規則，文獻［24］表明，部分異常節點可能影響全局最優解的質量，提出一種排除異常節點的信息素更新規則，以篩選迭代最優解中信息素異常的節點，后續迭代優先選擇正常節點，從而將螞蟻引導到新的搜索區域。文獻［21］表明，當信息素揮發系數為常值時，算法對于信息素較低節點的搜索能力較低，因此提出一種信息素動態揮發機制，每次迭代后，揮發系數根據信息素濃度動態變化。文獻［25］構建一種改進最大最小螞蟻系統（Max-Min Ant System，MMAS），以避免結果陷入局部最優解，將頂點信息素初始為最大值，在蟻群搜索過程中，信息素被嚴格限制在最值范圍內，每次迭代后僅更新迭代最優解或全局最優解中頂點的信息素。然而這些信息素更新規則無法兼顧算法的準確性和收斂性，在SDN 測量節點選擇問題的應用效果不佳。

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

在流路徑信息獲取受限的情況下，SDN 網絡測量節點選擇問題只能依賴于網絡的物理拓撲。文獻［27］借助社交網絡的中心性指標度量圖節點的重要性，提出3 種基于中心性的單個測量節點選擇方案：介數中心性，接近中心性和度中心性。然而單點測量能夠節約測量資源，但是測量準確度低。因此，該文獻又提出一種基于擴展中心性的多測量節點選擇算法。該算法基于介數中心性選擇第1 個測量節點，后續測量節點在其鄰接點中按照最短路徑重疊最少規則進行選擇。

根據以上研究和分析，SDN 網絡下測量節點選擇算法存在以下問題：1）隱私保護場景下流路徑信息獲取受限，基于流的測量節點選擇方案失效；2）單個測量點采集的流統計信息不全面，導致測量精度較低；3）基于擴展中心性的多測量節點選擇算法未考慮測量點的負載因素，實際測量效果較差。因此，本文在SDN 網絡中基于網絡拓撲進行測量節點選擇，改進ACΟ 算法的概率狀態轉移規則和信息素更新規則，分別提高模型結果的準確性和收斂性，增加一種基于NS 策略的過載處理機制局部調整滿足條件的測量節點，在不破壞鏈路覆蓋率的情況下，縮短過載處理時間。

2 SDN 中基于蟻群優化的測量節點選擇算法

基于蟻群優化的測量節點選擇算法的參數信息如表1 所示。

表1 基于蟻群優化的測量節點選擇算法的參數信息Table 1 Parameters information of measurement node selection algorithm based on ant colony optimization

2.1 SDN 網絡中測量節點選擇方案

網絡測量節點選擇的SDN 架構如圖1 所示。基于蟻群優化的測量節點選擇方案部署在SDN 應用層，包括拓撲發現、節點搜索、負載監測和過載處理4 個模塊，同一模塊流向其他模塊的數據相同。

圖1 網絡測量節點選擇的SDN 架構Fig.1 SDN framework for network measurement node selection

基于蟻群優化的測量節點選擇方案的具體流程為：1）拓撲發現模塊通過鏈路發現機制的REST-API獲取模擬網絡的所有交換機和鏈路，匯總成網絡拓撲圖；2）節點搜索模塊利用改進ACΟ 算法搜索graph 的初始測量集；3）負載監測模塊通過Packet-in消息觸發機制和流表統計接口在線計算selects 中節點的負載，若監測值超過閾值δ，該測量點被添加到過載測量集；4）過載處理模塊利用NS 策略將loads中滿足覆蓋條件的過載測量點從selects 中刪除，最終得到給定無向圖的優化測量集updates。

2.2 ACO 算法的規則改進

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

ACΟ 算法的規則改進是采用ACΟ-NS 算法求解附加負載因素的最小頂點覆蓋模型，首先ACΟ 算法從圖G中搜索出最小頂點覆蓋M，然后NS 算法結合鄰接矩陣S得到最小狀態頂點覆蓋M′，基于蟻群優化的網絡測量節點選擇算法流程如圖2 所示。

圖2 基于蟻群優化的網絡測量節點選擇算法流程Fig.2 Procedure of network measurement node selection algorithm based on ant colony optimization

對于ACΟ 算法，本文主要改進概率狀態轉移過程中的候選集定義，對信息素更新過程的優化體現在局部增強和全局揮發2 個子過程；而對NS 算法優化主要分為構造篩選、替換和冗余檢驗3 個操作，處理測量節點的過載現象。

2.2.1 概率狀態轉移優化

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

螞蟻每次選擇一個頂點后，新候選集更新策略在原始候選集更新策略的基礎上繼續刪除度為1 的頂點。假設當前候選集用C表示，則新候選集更新策略的數學描述如式（1）所示：

其中：CP為上次更新后的候選集；s為所選頂點；V0為度為0的頂點構成集合；集合V1包含所有度為1的頂點。

根據新候選集更新策略，ACΟ 算法的概率狀態轉移規則進行了相應調整。候選集劃分為優選集和計算集。優選集由度為1 頂點的鄰接點構成的集合，計算集是當前候選集中優選集的補集，必須保證優選集的優先級。在某次迭代中，如果螞蟻先選擇計算集的頂點，由于會刪除關聯的邊，可能使優選集中頂點的度為0，導致優選集頂點被候選集更新策略刪除。度為1 的頂點與鄰接點的邊沒有被selects 覆蓋，進而影響模型結果的準確性。優選集頂點的選擇概率恒定為1，而計算集頂點的選擇概率由信息素濃度和啟發信息值計算得到。假設優選集、計算集分別為F和R，螞蟻k選擇頂點νi的概率為pki，則調整后的概率狀態轉移規則如式（2）所示：

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

當計算集頂點和優選集頂點的選擇概率相同時，螞蟻極有可能選擇計算集中的頂點，破壞規定的優先級。通過將概率狀態轉移規則的分母增加1，使得計算集的概率狀態始終小于優選集，以確保模型結果的準確性。

2.2.2 信息素更新優化

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

信息素局部增強發生在螞蟻構造出一個可行解，無論可行解是否最優，其相關節點的信息素均適當增加。節點νi在第t+1 次迭代中信息素濃度如式（4）所示：

信息素局部增強為充分建立ACΟ 算法的正反饋機制，通過當前螞蟻增強潛在最優節點的信息素，指導蟻群中的其他螞蟻，以構造較優解。

每當蟻群迭代出一個局部解時，執行信息素全局揮發子策略。根據迭代解降低相關節點νj的信息素濃度，如式（5）所示：

2.3 測量點過載處理機制

2.3.1 OpenFlow 交換機負載監測

測量點過載處理機制主要監測selects 中測量點的負載，在實際SDN 環境中，在線獲取ΟpenFlow 交換機的負載。在不同場景下，交換機負載的定義和監測方式有所不同，由于CPU 吞吐量和TCAM 容量是SDN 交換機的兩大性能瓶頸，ΟpenFlow 交換機的負載lload如式（6）所示：

其中：TCPU和UTCAM分別為測量點的CPU 吞吐率和TCAM 使用率。因此，測量點負載監測分為統計CPU 吞吐率和TCAM 使用率。

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

在ΟpenFlow 交換機中，TCAM 用于存儲流表項，而流表項是交換節點處理數據包的依據。從成本和功耗兩個方面考慮，TCAM 存儲器支持的流表項數量有限，假設最大流表項數為entry_volumn。交換機當前使用的流表項數在一定程度上反映了其負載狀態。

ΟpenFlow 協議提供流表統計機制，包括TableStatsRequest 和TableStatsReply 消息。控制器向交換機發送不包含數據的TableStatsRequest消息，交換機回復TableStatsReply 消息給控制器，TableStatsReply消息體結構如下：

active_count 字段指示單個流表中活躍的流表項數，累加所有流表的active_count 字段值，可以得到整個交換機當前占用流表項數entry_current。

因此，TCAM 使用率是當前占用流表項數與最大流表項數的比值，如式（8）所示：

ΟpenFlow 交換機在線獲取測量節點的負載后，需要進一步判斷該節點的狀態是否異常。假設負載閾值δ=0.8，若式（6）計算的負載大于δ，該測量節點不適合下發測量任務，添加到loads 后，等待過載處理模塊篩選并替換。

2.3.2 基于NS 的過載處理機制

測量點過載處理規則的相關假設是在短時間內網絡拓撲不會發生大規模變化，并且負載主要發生在測量節點。隨著網絡測量持續運行，測量節點可能出現過載現象，需要重新執行ACΟ 算法等。然而全局搜索算法將耗費大量資源，同時時間開銷較大。NS 策略在初始解的基礎上執行添加、刪除和交換等操作，以獲取最優解。NS 策略存在平衡測量資源和時間的可能，應用在最小頂點覆蓋模型時，還可以兼顧鏈路覆蓋率。

如果2 個過載測量點由一條邊連接，則定義這種邊為過載邊。過載節點可以集中替換的節點取決于過載邊的統計結果，如果沒有過載邊，則替換整個過載節點集；否則不斷篩選覆蓋最多過載邊的負載異常的測量節點，刪除已覆蓋過載邊，直到刪除完全，過載節點集中的剩余節點作為替換節點。

鏈路覆蓋率維持的關鍵是NS 策略的替換過程。基于網絡拓撲圖構造每個替換測量點的鄰域，即所有鄰接點構成的集合，若某個鄰接點不在selects 中，則將其添加到初始測量集。整個鄰域遍歷結束后，從初始測量集刪除對應替換測量點。替換過程結束，selects 還需要進一步處理。

冗余覆蓋檢驗的目的在于降低模型結果的鏈路的冗余度。如果selects 中每個測量點鄰域被包含在更新的初始測量集中，說明該測量點與所有鄰接點間的邊被重復覆蓋，直接將該測量點從初始測量集中刪除，在不影響鏈路覆蓋率的情況下，能夠降低模型結果的冗余度，從而優化測量集。

測量點過載處理后的updates 包含最少數量的過載測量點，算法1 是鄰域搜索策略的偽代碼。

算法1鄰域搜索策略

算法1 的原理是1 個雙層循環結構（步驟2～7），外層循環控制當前訪問的替換測量點，而內層循環遍歷該替換測量點的鄰域，除selects 以外的鄰接點被添加到初始測量集，遍歷結束，再刪除該替換測量點。假設n表示替換測量點的數目，根據分析可得，算法的時間復雜度是Ο（n2），由于需要記錄每個替換測量點的鄰接點信息，算法的空間復雜度也是Ο（n2）。

3 實驗與分析

本節從實驗設置、規則優化效果和仿真拓撲驗證3 個方面對SDN 中基于蟻群優化的網絡測量節點選擇算法進行評估。

3.1 實驗環境與基本參數

3.60GHz、16 GB RAM 的4核Windows 10主機作為硬件環境，SDN 平臺基于Ubuntu16.04 系統搭建，使用開源控制器Ryu-4.32，拓撲仿真器采用Mininet-2.3.0d6，軟件交換機為Οpen vSwitch-2.11.0，算法相關模塊由Python 語言實現。

算法輸入的3 種無向圖參數信息如表2 所示，最小測量數是無向圖可以部署測量節點的最少數量。

表2 不同規模無向圖的參數信息Table 2 Parameters information of undirected graphs with different scales

ACΟ 算法的參數空間比較復雜，參數取值與算法的驗證結果相關，通過參考文獻或簡單實驗確定算法的參數，如表3 所示。其中：iterate 表示算法最大迭代次數；verge 表示算法的收斂條件，即模型解長度不再減少的連續迭代次數；符號|V|表示無向圖的頂點數，算法中螞蟻數量隨無向圖規模發生變化。

表3 算法的參數值Table 3 Parameter values of algorithm

3.2 算法規則的優化效果

3.2.1 實驗與數據對比

在算法執行過程中，平均測量數是指多個測量節點數的均值，命中頻數是命中對應最小測量數的次數，兩者決定算法的準確性。平均迭代次數是多次執行迭代次數的均值，與算法收斂性相關。

第1 組對比實驗用于驗證新候選集定義對于ACΟ 算法準確性的改進效果，在基本參數保持一致的條件下，本文采用新候選集定義和原始候選集定義的ACΟ 算法在無向圖karate、jazz 和email 中進行平均測量數、命中頻數和平均迭代數對比，各執行10 次，結果如表4 所示。

表4 兩組對比實驗的統計數據Table 4 Statistical datas of two groups of comparative experiments

第2 組對比實驗用于驗證信息素局部增強-全局揮發規則對ACΟ 算法收斂性的優化效果，同理保持基本參數一致，本文采用信息素局部增強-全局揮發規則和MMAS 更新規則的ACΟ 算法分別在karate、jazz 和email 中執行10 次，同樣將第2 組對比實驗數據的結果統計到表4。

從表4 可以看出，對比ACΟ 算法中的典型策略，新候選集定義一定程度上提高了抽象模型的準確性，而信息素局部增強-全局揮發規則主要優化抽象模型的收斂性。過載處理機制執行的前提是無向圖的初始測量集，為了保證實驗環境相同，第3 組對比實驗采用改進ACΟ 算法獲取初始測量集。基本負載處理機制將負載作為概率狀態轉移規則的決策因素之一。第3 組對比實驗中過載節點隨機產生，基本負載處理機制與測量點過載處理機制在3 種無向圖中各執行10 次，主要用于驗證過載處理機制對時間的優化效果。

圖3 分別記錄2 種負載處理機制在無向圖karate、jazz和email運行的測量節點數和運行時間。num_aco、num_ns 分別表示基本負載處理和測量點過載處理機制的測量節點數；time_aco、time_ns 分別為采用2 種機制的運行時間，由于jazz 和email圖下兩種負載處理機制的運行時間差別很大，因此圖3（b）和圖3（c）中time_ns指標非常接近于橫坐標。

圖3 不同負載處理機制的測量節點數和運行時間對比Fig.3 Measurement nodes and runtime comparison among different load handling mechanisms

3.2.2 數據分析與結果

本文定義3 種衡量算法的指標：準確性為命中頻數的平均數；收斂性是收斂條件與平均迭代數的比值；單位時間開銷是平均運行時間與無向圖頂點數的比值。

對于表4 中的統計數據，盡管無向圖規模不同，新候選集定義的平均測量數、平均迭代次數均小于或等于原始候選集定義，且命中頻數較大，結果更接近無向圖的最小測量數。相比MMAS 更新策略，雖然信息素局部增強-全局揮發規則增加了平均測量數，但是大幅降低了平均迭代數，在無向圖email 中更為明顯。從圖4 可以看出，測量點過載處理機制與基本負載處理機制的測量節點數比較接近，但是測量點過載處理機制的運行時間具有2～3 個數量級的優勢，并且隨著無向圖頂點數增多而增大，其原因為將負載因素引入概率轉移狀態規則中，破壞信息素和啟發信息的指導作用，增加了算法的運行時間。

因此，新候選集定義顯著提高了ACΟ 算法的準確性，信息素局部增強-全局揮發規則集中改進了收斂性，而測量點過載處理機制主要降低了算法的單位時間開銷。若考慮3 種規則在準確性、收斂性及單位時間開銷的精確效果，ACΟ 算法與ACΟ-NS 算法的性能指標對比如表5 所示。

表5 ACO 與ACO-NS 算法的性能指標對比Table 5 Performance indexs comparison of ACO and ACO-NS algorithms

從表5 可以看出，相比ACΟ 算法，ACΟ-NS 算法的準確度和收斂度分別提高了56.7 和28.2 個百分點，且在單位時間開銷方面降低了79.8 個百分點。

3.3 SDN 網絡中不同測量節點選擇方案

本節在SDN 環境中使用Mininet 工具模擬歐洲光纖網核心拓撲，如圖4 所示。

圖4 仿真的歐洲光纖網核心拓撲Fig.4 Simulated core topology of European optical fiber network

為評估單個中心測量點、基于擴展中心性的多個測量點、ACΟ-NS 算法和全部節點4 種方案的覆蓋率和冗余度，本文定義鏈路的覆蓋率和冗余度。覆蓋率是指所選測量點覆蓋的鏈路占全部鏈路的比率，冗余度是指測量節點重復覆蓋的鏈路數量。

仿真的歐洲光纖網核心拓撲包括16 個節點、23 條鏈路。假設單個中心測量點選擇度最大的節點，即single=｛6｝，擴展中心性方案的測量點集合extend=｛11，6，7，4，3，1｝，ACΟ-NS 算法的測量點集合aco_ns=｛6，4，2，8，10，14，16，12｝，全部節點方案all 包含該網絡拓撲中所有節點。

不同方案的覆蓋率和冗余度如圖5所示。single方案的覆蓋率和冗余度都是最低的，但是網絡測量更關注覆蓋率，因此single 方案應用效果最差。雖然aco_ns和all這2 種方案的覆蓋率均達到100%，但是all方案的冗余度過高，流量重復采集的概率較大。extend 方案能夠以較低的冗余度實現較高的覆蓋率，但仍存在優化的空間，aco_ns方案的冗余度和覆蓋率均優于extend方案。因此，ACΟ-NS 算法在基于網絡拓撲的SDN 場景下選擇測量節點的性能最佳。

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

4 結束語

本文提出一種基于蟻群優化的網絡測量節點選擇算法ACΟ-NS，利用CPU 吞吐率和三態內容尋址存儲器在線監測測量交換機的負載，為SDN 環境中網絡測量節點選擇提供理論依據，通過優化概率狀態轉移規則和信息素更新規則，提高測量集的收斂度，同時僅對過載的測量交換機進行鄰域搜索，有效縮短調整負載的時間。實驗結果表明，相比ACΟ 算法，ACΟ-NS 算法的準確度提高了56.7個百分點，單位時間開銷降低79.8個百分點，能夠有效提高SDN 控制器的工作效率，從而降低負載對網絡測量結果的影響。后續將基于不同網絡拓撲結構分析測量點選擇與流長分布估計的關系，進一步優化算法設計。