基于節點加權的網絡流量測量點選擇算法

翟羽娟，羅浩，吳志剛，張樹壯

北京郵電大學網絡技術研究院，北京100876

隨著網絡規模不斷擴大，網絡結構也愈發復雜化。為了保證高質量的網絡通信和網絡資源的利用率，需要對網絡結構進行合理優化。網絡流量測量對流量建模分析[1]、網絡性能監測及優化具有重要作用，能夠為流量工程提供測量數據，更好地滿足網絡服務質量的要求[2]。在網絡規模不大，網絡中流量負載較低的情況下，管理員可以在網絡中的所有節點上都部署探針，已達到監測全網的目的。但對于規模龐大的網絡來說，此方法不僅會造成測量節點部署、維護的開銷過大，帶來巨大的軟硬件資源消耗，還可能會造成網絡中測量流量較高，從而影響網絡中正常的通信和服務。因此，對于大規模網絡，選擇合理有效的測量點，即通過選擇一部分節點部署探針就能達到監測全網的目的，成為網絡流量測量中的關鍵。

對于這一問題，國內外已有諸多研究。在算法模型方面，基于流守恒的網絡測量問題被映射為最小弱頂點覆蓋問題[3]，并指出該問題屬于NP難題。文獻[4]提出了一種求解弱頂點覆蓋集的貪婪算法；文獻[5]利用關聯矩陣和線性規劃的概念，提出了一種求解最小弱頂點覆蓋集的近似算法；文獻[6]基于蟻群優化算法和禁忌搜索策略解決了測量點選擇問題；文獻[7]同樣基于蟻群算法，提出了一種適用于分布式網絡的測量節點的智能選擇算法。但在目前的研究中，網絡中所有節點對流量傳輸的作用被視為完全等同的，這與實際情況并不相符。文獻[8]中指出，網絡中的流量行為具有以下重要屬性：輸出流量集中在極少數活動IP中，而輸入流量則較為分散。由此可知，網絡中的不同節點對承擔流量傳輸任務具有不同的重要性。因此，優先在關鍵節點上部署探針對獲取網絡重要流量數據、掌握流量分布情況具有重要意義。在資源有限，導致在網絡中可部署的探針數量有限的情況下，優先選擇關鍵節點尤為重要。

綜上所述，目前需要一種網絡流量測量點選擇方法，使其能夠在滿足測量需求的情況下，盡可能少地選擇測量點，并且優先選擇關鍵節點。

1 相關工作

節點關鍵度的作用是衡量復雜網絡中節點重要性。研究中已經指出，大規模計算機系統屬于復雜網絡，因此對于復雜網絡適用的節點關鍵度評價指標同樣適用于計算機網絡拓撲。研究中給出了復雜網絡關鍵節點評估模型，其中包含2個因素：評價指標及相應的評估策略[9]。評價指標指的是評估過程中選取的度量標準，即通過某種量化標準定量計算網絡中節點的關鍵度；評價策略指的是如何使用評價指標進行測度，通常情況下，對于評估過程中網絡拓撲結構無變化的情況，直接使用評價指標對節點關鍵度進行衡量即可。以下給出2種常見的節點關鍵度評價指標：

1)節點度

網絡中某個節點的節點度被定義為直接與該節點相連的鄰居節點的個數（或與其直接相連的邊的數量）。節點度計算方式簡單、復雜度低，但只能在某種程度上反映節點的關鍵度，不夠準確。

2)介數

在無向無權網絡中，使用經過某個節點的最短路徑數量來計算該節點的介數。介數的計算方法如下：

式中：nst指的是從節點s到節點t的最短路徑數量；指的是這些最短路徑中經過節點i的數量。介數刻畫了網絡中某個節點對于網絡信息沿著最短路徑傳輸的控制能力。當一個節點的介數越高，對網絡中信息傳輸的重要性越高。由此可見，介數能夠很好地區分網絡中不同節點對流量傳輸重要性的不同。對于AS級網絡，文獻[10]中給出了AS網絡節點關鍵度計算方法。

網絡流量測量點的選擇問題可以轉換為圖論中的最小弱頂點覆蓋問題。研究中已經指出，最小弱頂點覆蓋問題是一個NP難題，通常使用近似算法求解。文獻[5]中提出了一種基于關聯矩陣的近似算法，該算法的思路如下：

1）選擇一個包含鏈路數量最多的節點，記做v1；

2）在關聯矩陣中刪除v1對應的行以及該行中元素1所對應的列；

3）在剩下的關聯矩陣中依次刪除所有行元素之和不超過1的其他行以及這些行中元素1所在列，重復此步驟直到不能再刪除新行為止；

4）重復以上步驟，直到關聯矩陣中所有元素都被刪除。

該算法的正確性已經過理論及實驗驗證，并且與傳統的貪心算法相比，能夠得到規模更小的弱頂點覆蓋集。但是對于大規模問題，該算法求解最優解的能力仍顯不足。因此有學者使用蟻群算法來進行測量點的求解。

蟻群算法[11]是一種受到真實螞蟻的自然優化機制所啟發的元啟發式算法，具有分布式計算、正反饋、自組織以及貪心啟發等特點。相比于其他求解NP難題的近似算法，蟻群算法具有搜索速度快、搜索較優解能力強等優點，在解決旅行商問題、子集類問題中都表現出色。網絡流量測量點選擇問題被轉換為圖論中的最小弱頂點覆蓋問題，是NP難題，使用蟻群算法作為基本選擇算法能夠較好地解決。參考文獻[7]、[11]、[12]給出蟻群算法的基本步驟，并對其中的關鍵步驟進行說明。

1)初始化

在初始化時，需要為圖中每個節點設置初始化信息素值。通常情況下，為了避免在算法運行過程中各個節點上的信息素強度相差過大，算法采 用 最 大 最 小 螞 蟻 系 統 （max-min ant system，MMAS）的信息素更新規則。在整個算法運行過程中，信息素強度會被限制在[τmin，τmax]范圍內，其中τmin和τmax通常根據問題人為設定為常數。初始值通常被設定為τmax。

2)選擇節點

每只螞蟻根據狀態轉移概率公式進行節點的選擇，該公式的具體計算方式如下：

式中：Ck表示候選頂點集；τi表示頂點vi上的信息素軌跡強度；ηi表示頂點vi上的期望啟發信息值，在現有的使用蟻群算法作為測量點選擇算法的研究中，期望其發信息值只使用節點度表示；α和β分別表示信息啟發因子和期望啟發信息因子，這2個值都是常數，通常根據經驗人為指定。

3)信息素更新

在每次循環過程完成后，即所有螞蟻得到自己的最小弱頂點集并比較得到循環最優解后，使用MMAS的信息素更新規則進行信息素更新。信息素更新包括信息素的揮發和增。信息素的揮發按照式（2）進行：

式中ρ代表信息素揮發系數，取值范圍被限定在[0，1]，由人為指定。

信息素的增加按照式（3）進行：

式中：Q為信息素增量系數；cMVC為循環最優解，某次循環中蟻群找到的包含頂點數最少的弱頂點覆蓋集；gMVC為全局最優解，自算法運行以來蟻群找到的包含頂點數最少的弱頂點覆蓋集。

2 基于節點加權的網絡流量測量點選擇算法

2.1 問題描述及模型定義

節點加權的情況與之類似，仍然是要求得網絡拓撲的一個最小弱頂點覆蓋集；與之不同的是，該問題的求解目標發生了變化，變為在覆蓋所有鏈路的情況下，所選測量點的權重之和最小。由此，將基于節點加權的網絡流量測量點選擇問題轉換為節點加權的最小弱頂點覆蓋問題。

我們將節點加權的網絡拓撲表示為一個三元組G=(V,E,W)， 其中 V=(v1,v2,v3...vm)表示網絡中所有節點的集合； E=(e1,e2,e3...en)表示網絡中所有鏈路的集合； W=(w1,w2,w3...wm)表示網絡中所有節點的權重。為了給出節點加權的最小弱頂點覆蓋問題的數學模型定義，令：

式中S表示圖G的一個弱頂點覆蓋集。

對于圖中的每一個節點，我們按照式（4）計算其xi的值。當滿足式（5）的條件時，我們認為S是圖G一個節點加權的最小弱頂點覆蓋集。

要解決基于節點加權的網絡流量測量點選擇問題，就是要求得上述節點加權的最小弱頂點覆蓋集。式（5）就是該問題的求解目標。能夠看出，與無權無向圖中的最小弱頂點覆蓋問題相類似，該問題也屬于一個NP難題。

2.2 算法實現

本文提出的基于節點加權的網絡流量測量點選擇算法將在蟻群算法的基礎上對其進行改進，使其能夠適應大規模網絡中節點加權的情況。算法主要分為節點權重分配、使用基于關聯矩陣的近似算法計算初始解集、使用改進后的蟻群算法求得最終解等3個步驟。

2.2.1 權重分配

為了區分網絡中不同節點對流量傳輸的不同重要性，本算法將根據節點關鍵度為節點進行權重分配。根據關鍵節點對流量傳輸的重要性，我們認為，與該關鍵節點相關聯的所有鏈路都值得被優先覆蓋。而一條鏈路既可以被該節點覆蓋，也可以被它的鄰居節點覆蓋。因此，在選擇測量節點時，關鍵節點的鄰居節點也應當具有較高的優先級。

根據節點加權的最小弱頂點覆蓋問題的求解目標可知，節點的權重越小，優先被選擇的可能性越大。依照以上權重分配的思路，結合求解目標對權重的約束，給出權重計算方法：

式中： N(i)表示節點vi及其所有鄰居節點組成的集合；cj表示節點vj的關鍵度。這種權重計算方法即考慮節點自身的關鍵度，也考慮了所有鄰居節點的關鍵度，且計算簡單。當某個節點的權重越小時∑，則意味著該節點及其鄰居節點的關鍵度越大。該值的大小取決于單個鄰居節點關鍵度的大小以及鄰居節點的個數。前者意味著連接該節點與鄰居節點的鏈路優先被覆蓋的可能性；后者意味著該節點能夠覆蓋鏈路的數量。綜合二者計算權重，可以評價一個節點在測量點選擇過程中被優先選擇的可能性。

2.2.2 初始解計算

為了讓算法在處理大規模問題時搜索速度更快，需要先使用基于關聯矩陣的近似算法對問題求出一個近似解，作為蟻群算法的初始解集，即螞蟻將從該解集中選擇節點作為自己搜索的起始節點。

對于圖 G=(V,E,W)，先忽略節點權重，可以將其抽象為一個m×n大小的聯矩陣為矩陣中的元素，它的計算方式如下：

為了使基于關聯矩陣的近似算法適用于節點加權的情況，對測量點的選擇方法進行改進。在測量點的選擇過程中，節點權重越小，代表該節點對流量傳輸的重要性越高，被優先選擇的可能性越大；與該節點相關聯的鏈路數量越多，代表該節點對鏈路的覆蓋范圍越廣，被優先選擇的可能性越大。綜合考慮這兩個影響測量點選擇的因素，結合問題的求解目標，給出如下計算公式：

式中：pi表示節點的綜合權重表示矩陣中行元素之和。在算法運行過程中，需要根據當前矩陣的狀態動態計算，即該值始終表示的是與節點vi相關聯但還未被覆蓋的鏈路數量。對于圖中的每個節點，在每次進行節點選擇之前，按照式（7）計算pi的值，并且每次選擇pi最小的節點加入測量點集合。

2.2.3 基于節點加權的增強蟻群算法

要讓基本蟻群算法適用于節點加權的情況，需要對其中的信息素初始化以及期望信息啟發值的計算方法進行改進，形成基于節點加權的增強蟻群算法。

1)信息素初始化

在基本蟻群算法中，通常會采用最大最小螞蟻系統（MMAS）的信息素更新規則進行信息素更新。在該規則中，信息素的值被限制在[τmin，τmax]范圍內，τmin和τmax的取值通常是根據問題人為設定為常數，而各個節點的信息素初始值通常被設置為τmax。但是對于節點加權的情況，不同的節點對于流量測量具有不同的重要性，信息素初始值能夠根據節點權重的不同而變化，才能更好地區分節點，也更有利于之后蟻群的搜索。

在根據權重對節點進行信息素初始化時，我們希望各個節點的信息素初始值能夠根據權重大小合理地分散在[τmin，τmax]的范圍內。結合權重越小代表優先被選擇的可能性越大，信息素值越大被優先選擇的可能性越大這一條件，信息素初始值的分配要滿足以下3個條件：

a)信息素初始值與節點權重成反比；

b)信息素初始值大小能反映權重的大?。?/p>

c)信息素初始值范圍在[τmin，τmax]內。

根據以上條件，給出信息素初始值的分配方法如下：首先對信息素值的取值區間進行反比例變換，得到新區間；其次將權重取值區間映射到新區間，得到一個中間結果；最后對該中間結果進行反比例變換得到最終的信息素初始值。根據式（8）和（9）對信息素區間進行反比例變換。

我們給出節點權重的取值范圍為[wmin，wmax]，其中wmin和wmax分別是節點權重的最小值和最大值。接下來，根據式（10）將權重區間[wmin,wmax]映射到新區間得到一個中間值τ′。

為了避免τmin和τmax取值不合理導致在進行映射后節點權重的差異被過度縮小，信息素初始值對節點的區分作用不明顯，給出一種計算τmin和τmax取值的方法。為了準確體現節點權重之間的差異，新區間的上下界可以通過直接對權重區間的上下界進行向上取整和向下取整操作得到。在得到新區間的上下界后對其進行反比例計算即可得到τmin和τmax的取值。若計算得到的結果顯示二者的值相差過大，為了避免算法陷入停滯，可以人為調整取值。

2)期望啟發信息值的計算

在蟻群算法中，期望啟發信息值的計算通常根據求解問題的不同，選擇不同的計算方式。目前，其計算方式通常有以下3種：人為設定常數、節點未被覆蓋的鏈路數量以及所有鄰居節點未被覆蓋的鏈路數量之和與該節點未被覆蓋的鏈路數量之比。第一種方式屬于靜態計算方法，對于大規模問題，會失去對蟻群搜索的指導意義；第二種方式動態計算，但只考慮了單個節點，不夠全面；第三種方式也屬于動態計算，但沒有考慮節點加權的情況，此，本文提出一種適用于節點加權的期望啟發信息值的動態計算方法，以達到指導蟻群優先選擇關鍵節點的目的。

根據公式（1）可以發現，當一個節點的期望啟發信息值越大時，該節點被選擇的概率就越大?？紤]節點的關鍵度與節點被選擇概率之間的關系：節點關鍵度越高，被選擇的概率就越大。因此，期望啟發信息值應當與節點關鍵度成正比關系。參考節點權重計算公式的推導思路，一個節點被選擇的可能性會受到它所有鄰居節點關鍵度的影響，因此，一個節點的期望啟發信息值應當與該節點及其所有鄰居節點都有關。為了實現問題的求解目標，除了節點關鍵度之外，還要考慮該節點相關聯的鏈路數量。為了讓節點的期望啟發信息值具有更好的指導價值，需要隨著蟻群的搜索過程動態變化。綜合以上各項考量，提出一種期望啟發信息值的動態計算方法：

式中：|vi|指的是節點vi當前還未被覆蓋的鏈路數量，該值隨著蟻群的搜索過程變化；Ni指的是節點vi及其所有還未被覆蓋的鄰居節點的集合。

結合基本蟻群算法的步驟，給出了基于節點加權的增強蟻群算法的具體程序步驟：

初始化，根據公式（6）至公式（9）計算各個節點的信息素初始值

repeat

for蟻群中的每只螞蟻

隨機選擇一個初始解集中的節點作為搜索的起始節點，并將其加入自己的覆蓋集中

構造自己的候選點集合

while候選點集合不為空

每只螞蟻根據公式（12）計算期望啟發信息值

每只螞蟻根據公式（1）計算狀態轉移概率，選擇概率最大的節點加入最小弱頂點覆蓋集

end while

end for

保留循環最優解

根據計算出的 τmin和 τmax以及式（2）和（3）更新信息素

until最優解被找到或完成最大循環次數

保存全局最優解

其中，每只螞蟻構造自己的候選集合可以使用基于關聯矩陣的思路。

3 實驗評估

由于網絡拓撲結構在宏觀上具有自相似性，因此本文使用全球AS級網絡拓撲對算法進行驗證。本文從RouteViews項目公開數據集中下載了2018.2.1的BGP路由表數據，在此基礎上使用Gao提出的域間關系推斷算法[13]構建出帶有域間關系的AS級網絡拓撲，并計算每個節點的客戶錐[14]大小作為節點關鍵度。將構建出的拓撲中節點度為1的節點刪除之后，該拓撲共具有共包含39026個節點，262522條邊。

對于節點加權和未加權的情況，分別使用基本蟻群算法以及本文提出的算法進行實驗。蟻群算法中的參數設置參考相關研究和文獻給出，不再詳述。本次實驗選擇的參數為α=1，β=2，螞蟻數量為100。對于節點加權的情況，使用本章給出的信息素計算方式得到τmin=0.1、τmax=34；對于節點未加權的情況，人為設置 τmin=0.1、τmax=10。同時，為了判斷蟻群是否找到最優解，增加了一個參數m，標識在搜索過程中，最優解規模連續m次沒有發生變化。此時認為最優解已經找到，循環終止，設置m=10。實驗結果表明，節點未加權情況下，測量點數量為3001；節點加權情況下，測量點數量為3213。

對于本文所研究的問題，已有研究中并未給出相關的實驗結果評估指標。因此，為了更加準確地評估算法的效果，本文定義2個評估指標：鏈路覆蓋比以及關鍵度占比。鏈路覆蓋比指的是n個測量點所覆蓋的鏈路數量與全部鏈路數量之比，主要描述測量點對鏈路的覆蓋能力；關鍵度占比指的是n個測量點的關鍵度之和占全部節點關鍵度之和的比例，主要衡量的是測量點的關鍵度是否更高。二者計算方式為：

式中R(i)表示測量點集合。

根據2個初始解集的規模，分別取n=10、50、100、500、1000、3000，計算節點加權和未加權2種情況下的評估指標。評估指標計算結果及對比如圖1所示。

圖1 2種算法評估指標對比

由圖1可以看出，2種算法得到的測量點的鏈路覆蓋比相差無幾，圖中曲線基本重合。這表明，本文提出的基于節點加權的蟻群算法搜索到的最優解對鏈路覆蓋能力強。從關鍵度占比曲線中可以看出，基于節點加權的蟻群算法能夠優先選擇關鍵度較大的節點，在測量點數量為50時，節點未加權情況下的關鍵度占比為0.4521，節點加權情況下關鍵度占比為0.5802，提升了大約28%。由此可見，在測量點數量較少的情況下，本文提出的算法能夠在保證鏈路覆蓋率的情況下，大幅提升關鍵度占比，優先選擇關鍵度更高的節點；在測量點數量較多，尤其對鏈路覆蓋率超過50%后，二者結果相差不大。

為了評估節點加權對算法性能的影響，對二者的運行時間、搜索最優解的循環次數進行了比較。比較結果如表1所示。

表1 基本蟻群算法與節點加權的增強蟻群算法性能比較

通過表1可以看出，本文中的算法在每計算狀態轉移概率時，都需要對期望啟發信息值進行重新計算；因此，單只螞蟻搜索解的平均時間要長，時間增長了約20.06%，且找到全局最優解的平均循環次數也有所增加。對比基本蟻群算法，節點加權的蟻群算法在收斂速度以及計算性能上有所下降。

綜合算法測量點選擇效果以及算法性能可以看出，本文中的算法雖然計算性能稍遜一籌，但選擇的測量點關鍵度高、選點效果好。在實際情況中，測量點選擇算法只需運行一次即可選出測量點，無需多次運行，因此，算法在時間上消耗帶來的開銷要遠小于不合理測量點進行測量帶來的開銷。綜上所述，針對節點加權的情況，本文中的算法能夠高效地選出關鍵度更高的節點，是一種合理性和實用性更好的算法。

4 結論

為了能夠區分網絡中不同節點對網絡流量傳輸的不同重要性，本文提出了一種基于節點加權的網絡流量測量點選擇算法。該算法主要分為權重分配、初始解集計算、使用基于節點加權的蟻群算法進行最終解計算三大部分。其中，基于節點加權的蟻群算法是通過對基本蟻群算法中的信息素初始化以及期望啟發信息值的計算進行改進形成的。

實驗結果表明，本文提出的算法能夠在保證鏈路覆蓋率的情況下，優先選擇對流量傳輸更重要的節點。但由于算法中需要進行動態計算的部分較多，算法的時間開銷有所增加。

本文提出的算法還有需要研究的地方，如蟻群算法中的參數設置對算法性能的影響；不同節點關鍵度計算方式對不同粒度網絡選點效果的影響；降低時間復雜度的方式等，將在未來對這些問題進行進一步研究和優化。