基于節(jié)點加權(quán)的網(wǎng)絡(luò)流量測量點選擇算法

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

北京郵電大學(xué)網(wǎng)絡(luò)技術(shù)研究院，北京100876

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

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

綜上所述，目前需要一種網(wǎng)絡(luò)流量測量點選擇方法，使其能夠在滿足測量需求的情況下，盡可能少地選擇測量點，并且優(yōu)先選擇關(guān)鍵節(jié)點。

1 相關(guān)工作

節(jié)點關(guān)鍵度的作用是衡量復(fù)雜網(wǎng)絡(luò)中節(jié)點重要性。研究中已經(jīng)指出，大規(guī)模計算機系統(tǒng)屬于復(fù)雜網(wǎng)絡(luò)，因此對于復(fù)雜網(wǎng)絡(luò)適用的節(jié)點關(guān)鍵度評價指標(biāo)同樣適用于計算機網(wǎng)絡(luò)拓撲。研究中給出了復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點評估模型，其中包含2個因素：評價指標(biāo)及相應(yīng)的評估策略[9]。評價指標(biāo)指的是評估過程中選取的度量標(biāo)準(zhǔn)，即通過某種量化標(biāo)準(zhǔn)定量計算網(wǎng)絡(luò)中節(jié)點的關(guān)鍵度；評價策略指的是如何使用評價指標(biāo)進行測度，通常情況下，對于評估過程中網(wǎng)絡(luò)拓撲結(jié)構(gòu)無變化的情況，直接使用評價指標(biāo)對節(jié)點關(guān)鍵度進行衡量即可。以下給出2種常見的節(jié)點關(guān)鍵度評價指標(biāo)：

1)節(jié)點度

網(wǎng)絡(luò)中某個節(jié)點的節(jié)點度被定義為直接與該節(jié)點相連的鄰居節(jié)點的個數(shù)（或與其直接相連的邊的數(shù)量）。節(jié)點度計算方式簡單、復(fù)雜度低，但只能在某種程度上反映節(jié)點的關(guān)鍵度，不夠準(zhǔn)確。

2)介數(shù)

在無向無權(quán)網(wǎng)絡(luò)中，使用經(jīng)過某個節(jié)點的最短路徑數(shù)量來計算該節(jié)點的介數(shù)。介數(shù)的計算方法如下：

式中：nst指的是從節(jié)點s到節(jié)點t的最短路徑數(shù)量；指的是這些最短路徑中經(jīng)過節(jié)點i的數(shù)量。介數(shù)刻畫了網(wǎng)絡(luò)中某個節(jié)點對于網(wǎng)絡(luò)信息沿著最短路徑傳輸?shù)目刂颇芰?。?dāng)一個節(jié)點的介數(shù)越高，對網(wǎng)絡(luò)中信息傳輸?shù)闹匾栽礁摺Ｓ纱丝梢?，介?shù)能夠很好地區(qū)分網(wǎng)絡(luò)中不同節(jié)點對流量傳輸重要性的不同。對于AS級網(wǎng)絡(luò)，文獻[10]中給出了AS網(wǎng)絡(luò)節(jié)點關(guān)鍵度計算方法。

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

1）選擇一個包含鏈路數(shù)量最多的節(jié)點，記做v1；

2）在關(guān)聯(lián)矩陣中刪除v1對應(yīng)的行以及該行中元素1所對應(yīng)的列；

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

4）重復(fù)以上步驟，直到關(guān)聯(lián)矩陣中所有元素都被刪除。

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

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

1)初始化

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

2)選擇節(jié)點

每只螞蟻根據(jù)狀態(tài)轉(zhuǎn)移概率公式進行節(jié)點的選擇，該公式的具體計算方式如下：

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

3)信息素更新

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

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

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

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

2 基于節(jié)點加權(quán)的網(wǎng)絡(luò)流量測量點選擇算法

2.1 問題描述及模型定義

節(jié)點加權(quán)的情況與之類似，仍然是要求得網(wǎng)絡(luò)拓撲的一個最小弱頂點覆蓋集；與之不同的是，該問題的求解目標(biāo)發(fā)生了變化，變?yōu)樵诟采w所有鏈路的情況下，所選測量點的權(quán)重之和最小。由此，將基于節(jié)點加權(quán)的網(wǎng)絡(luò)流量測量點選擇問題轉(zhuǎn)換為節(jié)點加權(quán)的最小弱頂點覆蓋問題。

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

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

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

要解決基于節(jié)點加權(quán)的網(wǎng)絡(luò)流量測量點選擇問題，就是要求得上述節(jié)點加權(quán)的最小弱頂點覆蓋集。式（5）就是該問題的求解目標(biāo)。能夠看出，與無權(quán)無向圖中的最小弱頂點覆蓋問題相類似，該問題也屬于一個NP難題。

2.2 算法實現(xiàn)

本文提出的基于節(jié)點加權(quán)的網(wǎng)絡(luò)流量測量點選擇算法將在蟻群算法的基礎(chǔ)上對其進行改進，使其能夠適應(yīng)大規(guī)模網(wǎng)絡(luò)中節(jié)點加權(quán)的情況。算法主要分為節(jié)點權(quán)重分配、使用基于關(guān)聯(lián)矩陣的近似算法計算初始解集、使用改進后的蟻群算法求得最終解等3個步驟。

2.2.1 權(quán)重分配

為了區(qū)分網(wǎng)絡(luò)中不同節(jié)點對流量傳輸?shù)牟煌匾?，本算法將根?jù)節(jié)點關(guān)鍵度為節(jié)點進行權(quán)重分配。根據(jù)關(guān)鍵節(jié)點對流量傳輸?shù)闹匾?，我們認為，與該關(guān)鍵節(jié)點相關(guān)聯(lián)的所有鏈路都值得被優(yōu)先覆蓋。而一條鏈路既可以被該節(jié)點覆蓋，也可以被它的鄰居節(jié)點覆蓋。因此，在選擇測量節(jié)點時，關(guān)鍵節(jié)點的鄰居節(jié)點也應(yīng)當(dāng)具有較高的優(yōu)先級。

根據(jù)節(jié)點加權(quán)的最小弱頂點覆蓋問題的求解目標(biāo)可知，節(jié)點的權(quán)重越小，優(yōu)先被選擇的可能性越大。依照以上權(quán)重分配的思路，結(jié)合求解目標(biāo)對權(quán)重的約束，給出權(quán)重計算方法：

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

2.2.2 初始解計算

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

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

為了使基于關(guān)聯(lián)矩陣的近似算法適用于節(jié)點加權(quán)的情況，對測量點的選擇方法進行改進。在測量點的選擇過程中，節(jié)點權(quán)重越小，代表該節(jié)點對流量傳輸?shù)闹匾栽礁?，被?yōu)先選擇的可能性越大；與該節(jié)點相關(guān)聯(lián)的鏈路數(shù)量越多，代表該節(jié)點對鏈路的覆蓋范圍越廣，被優(yōu)先選擇的可能性越大。綜合考慮這兩個影響測量點選擇的因素，結(jié)合問題的求解目標(biāo)，給出如下計算公式：

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

2.2.3 基于節(jié)點加權(quán)的增強蟻群算法

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

1)信息素初始化

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

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

a)信息素初始值與節(jié)點權(quán)重成反比；

b)信息素初始值大小能反映權(quán)重的大??；

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

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

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

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

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

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

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

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

結(jié)合基本蟻群算法的步驟，給出了基于節(jié)點加權(quán)的增強蟻群算法的具體程序步驟：

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

repeat

for蟻群中的每只螞蟻

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

構(gòu)造自己的候選點集合

while候選點集合不為空

每只螞蟻根據(jù)公式（12）計算期望啟發(fā)信息值

每只螞蟻根據(jù)公式（1）計算狀態(tài)轉(zhuǎn)移概率，選擇概率最大的節(jié)點加入最小弱頂點覆蓋集

end while

end for

保留循環(huán)最優(yōu)解

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

until最優(yōu)解被找到或完成最大循環(huán)次數(shù)

保存全局最優(yōu)解

其中，每只螞蟻構(gòu)造自己的候選集合可以使用基于關(guān)聯(lián)矩陣的思路。

3 實驗評估

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

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

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

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

根據(jù)2個初始解集的規(guī)模，分別取n=10、50、100、500、1000、3000，計算節(jié)點加權(quán)和未加權(quán)2種情況下的評估指標(biāo)。評估指標(biāo)計算結(jié)果及對比如圖1所示。

圖1 2種算法評估指標(biāo)對比

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

為了評估節(jié)點加權(quán)對算法性能的影響，對二者的運行時間、搜索最優(yōu)解的循環(huán)次數(shù)進行了比較。比較結(jié)果如表1所示。

表1 基本蟻群算法與節(jié)點加權(quán)的增強蟻群算法性能比較

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

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

4 結(jié)論

為了能夠區(qū)分網(wǎng)絡(luò)中不同節(jié)點對網(wǎng)絡(luò)流量傳輸?shù)牟煌匾?，本文提出了一種基于節(jié)點加權(quán)的網(wǎng)絡(luò)流量測量點選擇算法。該算法主要分為權(quán)重分配、初始解集計算、使用基于節(jié)點加權(quán)的蟻群算法進行最終解計算三大部分。其中，基于節(jié)點加權(quán)的蟻群算法是通過對基本蟻群算法中的信息素初始化以及期望啟發(fā)信息值的計算進行改進形成的。

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

本文提出的算法還有需要研究的地方，如蟻群算法中的參數(shù)設(shè)置對算法性能的影響；不同節(jié)點關(guān)鍵度計算方式對不同粒度網(wǎng)絡(luò)選點效果的影響；降低時間復(fù)雜度的方式等，將在未來對這些問題進行進一步研究和優(yōu)化。