面向調(diào)度數(shù)據(jù)網(wǎng)的探針部署優(yōu)化算法研究

劉宇明，田 豐

（云南電力調(diào)度控制中心，云南 昆明 650011）

面向調(diào)度數(shù)據(jù)網(wǎng)的探針部署優(yōu)化算法研究

劉宇明，田 豐

（云南電力調(diào)度控制中心，云南 昆明 650011）

文章對大規(guī)模電力通信數(shù)據(jù)網(wǎng)的網(wǎng)絡(luò)層業(yè)務(wù)流量監(jiān)控問題進行了研究，提出了一種基于最小弱頂點覆蓋的探針部署方法。該方法在最小頂點覆蓋的基礎(chǔ)上引入了流量守恒機制，保證了在可以得到每一條鏈路流量的條件下，流量監(jiān)測數(shù)目的最小化。仿真結(jié)果表明，與最小頂點覆蓋問題相比較，文章提出的方法所使用的探針數(shù)目更少，算法復(fù)雜度較低，具有較高的網(wǎng)絡(luò)性能。

電力通信數(shù)據(jù)網(wǎng)；探針部署；頂點覆蓋

電力通信數(shù)據(jù)網(wǎng)是面向電力系統(tǒng)的數(shù)據(jù)專網(wǎng)，也是保障電力系統(tǒng)業(yè)務(wù)穩(wěn)定運行的重要基礎(chǔ)設(shè)施，因此電力通信數(shù)據(jù)網(wǎng)的網(wǎng)絡(luò)層業(yè)務(wù)管理日益重要。近年來隨著電力工業(yè)的快速發(fā)展以及電力系統(tǒng)自動信息化水平的不斷提升，電力系統(tǒng)的數(shù)據(jù)網(wǎng)網(wǎng)絡(luò)層業(yè)務(wù)量日益增多，電力通信數(shù)據(jù)網(wǎng)承載的業(yè)務(wù)和功能越來越復(fù)雜，電力通信數(shù)據(jù)網(wǎng)網(wǎng)絡(luò)層業(yè)務(wù)的探針覆蓋問題，隨著網(wǎng)絡(luò)規(guī)模的擴大也日益復(fù)雜[1-4]。如何在現(xiàn)有的電力通信數(shù)據(jù)網(wǎng)的通信設(shè)備基礎(chǔ)上進行科學(xué)有效的管理，利用較少的探針部署實現(xiàn)有效的電力通信網(wǎng)絡(luò)層業(yè)務(wù)管理，是現(xiàn)在的電力網(wǎng)絡(luò)管理部門必須要解決的問題。

針對大規(guī)模網(wǎng)絡(luò)流量監(jiān)測的業(yè)務(wù)需求，通常采用NetFlow的探測方式，該方法在網(wǎng)絡(luò)中某一節(jié)點設(shè)置探針，以此得到與這一節(jié)點相聯(lián)的所有鏈路上的流量。因此，為了得到網(wǎng)絡(luò)中所有鏈路的網(wǎng)絡(luò)流量，一般可以通過在某些交換節(jié)點（路由器）配置監(jiān)測器實現(xiàn)。大規(guī)模電力通信網(wǎng)的網(wǎng)絡(luò)流量探測問題，就是要解決在大規(guī)模網(wǎng)絡(luò)中的哪些節(jié)點上設(shè)置監(jiān)測器，部署探針，才能使得在可以得到每一條鏈路流量的條件下，所需流量監(jiān)測器數(shù)目最小[5-7]。

1 問題描述

在大規(guī)模電力通信網(wǎng)絡(luò)中，通過在網(wǎng)絡(luò)中部署探針可以實現(xiàn)數(shù)據(jù)網(wǎng)的網(wǎng)絡(luò)層對業(yè)務(wù)的全面監(jiān)測。目前的研究中[8-10]，要實現(xiàn)對大規(guī)模網(wǎng)絡(luò)的全覆蓋，采用在網(wǎng)絡(luò)中的節(jié)點上部署探針的方法，來監(jiān)測網(wǎng)絡(luò)流量。全覆蓋的方法不僅成本開銷大，而且在測量時也會產(chǎn)生大量的測量數(shù)據(jù)，造成噪聲。假設(shè)在一個由n個網(wǎng)元組成的網(wǎng)絡(luò)中，測量k個網(wǎng)元間的流量特征，需要從n個網(wǎng)元中挑選出k個網(wǎng)元，此外，考慮到網(wǎng)絡(luò)流向問題，還需考慮k個節(jié)點的排列組合，因此，網(wǎng)絡(luò)流量測量方案就需要對C(n, k), P(k, k)個網(wǎng)元選取方案進行優(yōu)化判斷。在目前的研究中，如果要實現(xiàn)全覆蓋的測量方式和方案，產(chǎn)生的時間復(fù)雜度是階乘級的，空間復(fù)雜度也異常龐大。本文圍繞著業(yè)務(wù)監(jiān)測的實際需要，研究了如何部署適量的探針以滿足不同的業(yè)務(wù)監(jiān)測需求，以解決部署位置和部署容量的問題。

2 本文方法

要求解決的部署實例為“某數(shù)據(jù)網(wǎng)拓撲圖”，如圖1所示。為了說明本文要解決的問題和所提出的方法，作出如下假設(shè)。

假設(shè)問題中的數(shù)據(jù)網(wǎng)內(nèi)的鏈路權(quán)值都相等，設(shè)定為1；假設(shè)問題中網(wǎng)元間的通信路由規(guī)則采用最短路算法；在最小弱頂點覆蓋模型中，假設(shè)一個網(wǎng)元可以監(jiān)測與其直接相關(guān)的所有鏈路的流量，且滿足流量守恒；在最小集合覆蓋模型中，假設(shè)任意兩網(wǎng)元可以通過通信監(jiān)測其路徑上的所有鏈路的狀態(tài)，網(wǎng)絡(luò)監(jiān)測命令發(fā)生在探針與探針之間；由于網(wǎng)絡(luò)邊緣節(jié)點的度數(shù)通常較小，若把探測站點的位置選定在網(wǎng)絡(luò)的邊緣處，那么從該探測站點發(fā)送出的探測的數(shù)目以及探測的能力就會收到相應(yīng)的限制，因而假設(shè)探針位置不會在網(wǎng)絡(luò)的邊緣。

圖1 某數(shù)據(jù)網(wǎng)拓撲圖

要解決在網(wǎng)絡(luò)哪些節(jié)點上設(shè)置監(jiān)測器，才能使得在可以得到每一條鏈路流量的條件下，所需流量監(jiān)測器數(shù)目最小?，F(xiàn)有研究通常使用最小頂點覆蓋可以解決這一問題。頂點覆蓋問題已被證明是NP完全的，只能用近似算法算出近似最優(yōu)解。本文對最小頂點覆蓋問題的貪心算法進行改進，通過分支限定法的貪心策略實現(xiàn)探針部署問題。本文所提方法在考慮到網(wǎng)絡(luò)監(jiān)測方式的同時，增加了流量守恒的約束，使用最小弱頂點覆蓋能夠部署更少的探針來實現(xiàn)整個網(wǎng)絡(luò)的網(wǎng)絡(luò)流量監(jiān)測。最小弱頂點覆蓋問題也已被證明NP是完全的，只能使用近似算法求近似最優(yōu)解。評估本文所提流量監(jiān)測方法的測試評估指標是：部署的探針的個數(shù)、鏈路覆蓋率。

圖2是需要部署探針的網(wǎng)絡(luò)圖，需要把它轉(zhuǎn)化為無向圖G(V，E)，其中V=（v1，v2，…，vn）為網(wǎng)絡(luò)節(jié)點集（在IP網(wǎng)絡(luò)中可看作為路由器），E=（e1，e2，…，em）為網(wǎng)絡(luò)中的鏈路集合。其中，n=|V|，m=|E|分別表示G中節(jié)點和鏈路的數(shù)目。用ek= （vi,vj）表示ek是連接節(jié)點vi和vj的一條鏈路。用Degree（v）表示節(jié)點v的鏈路數(shù)，即節(jié)點v的度。

把圖1的所有路由器，交換機等設(shè)備按照1，2，……的順序進行標號，然后統(tǒng)計所有的鏈路信息，將該圖轉(zhuǎn)化為無向圖。如圖2所示（每個節(jié)點名稱前面有一個紅色標號）有160個節(jié)點，185條鏈路。該圖是一個稀疏圖（邊的條數(shù)m遠小于n2的圖），可以用鄰接鏈表來表示無向圖，但是考慮一般情況，為了能夠解決各種圖，使用鄰接矩陣來表示無向圖。

圖2 編號后的網(wǎng)絡(luò)拓撲圖

首先，本文對基于最小頂點覆蓋的探針部署方法進行了描述。為了描述該方法，本文進行了如下定義。

定義1：給定無向圖G(V，E)，其中V是頂點集，E是邊集，S是V的子集，若根據(jù)與S中頂點相關(guān)聯(lián)的各條邊的流量，可以確定E中任意邊的流量，則稱S是圖G關(guān)于流量的測量集。

有效測量問題的目標就是求給定圖G關(guān)于流量的最小測量集?？梢赞D(zhuǎn)換為求定義2中圖G的最小頂點覆蓋問題。

定義2（最小頂點覆蓋問題）：指給定一個無向圖G(V，E)，求頂點集V的一個最小子集S，使得e=(u,v)∈E，且u∈S或v∈S，即E中的任一邊至少含有此子集中的一個點作為頂點，也就是說S中的頂點覆蓋了邊集E。

其數(shù)學(xué)描述為：

其中c=[1，1，…，1]和x=[x1，x2，…，xn]都是長為n的向量，（aij）n×n是圖的鄰接矩陣，并且具有約束條件：

最小頂點覆蓋問題已被證明是NP完全的，到目前為止還不存在多項式時間算法來求解，可以用貪心算法去求出近似最優(yōu)解，即每次迭代都選取度最大的節(jié)點作為探針，然后所有與其相連的節(jié)點都可以排除掉，滿足每次選取探針都是當下情況的最優(yōu)情況，但是考慮到每次的最優(yōu)并不一定能得到整體上的最優(yōu)，為了找到更小的解，通過下面的限定策略，對貪心算法進行了改進，通過分支界限法來得到更優(yōu)解。

對所有節(jié)點的度從大到小排序，取前k個節(jié)點，滿足如下公式3的條件時，是可能滿足頂點覆蓋的界限。

通過上述約束，在使用貪心算法之前，先求出一個最小可能的最優(yōu)解k，將問題轉(zhuǎn)化為判定無向圖中是否存在k個節(jié)點滿足最小頂點覆蓋。通過貪心策略和限定策略去判定，若滿足則k是最優(yōu)解，若不滿足則將k加1，繼續(xù)進行判定。

在介紹具體的判定過程之前，首先使用最優(yōu)隊列和空間樹來建立模型，用一個優(yōu)先隊列維護當前可行的節(jié)點，每個節(jié)點維護著該節(jié)點情況下還可以選擇的頂點數(shù)目k1、需要覆蓋的剩余邊數(shù)e、頂點的狀態(tài)state、頂點的邊數(shù)Degree等信息，這些節(jié)點的排序遵循貪心策略，按頂點的邊數(shù)從大到小排序。對于頂點的狀態(tài)。該策略中頂點有3種狀態(tài)，分別為已經(jīng)選擇了的狀態(tài)S1，不選擇的狀態(tài)S2，可以選擇的狀態(tài)S3。其中，已經(jīng)選擇了的狀態(tài)S1對應(yīng)解空間樹數(shù)中的左節(jié)點，選擇該節(jié)點，然后設(shè)置該節(jié)點為已經(jīng)選擇狀態(tài)S1；不選擇的狀態(tài)S2對應(yīng)解空間樹中的右節(jié)點，不選擇該節(jié)點，然后設(shè)置該節(jié)點為不選擇狀態(tài)S2?？梢赃x擇的狀態(tài)S3對應(yīng)解空間樹中的父節(jié)點，選擇該節(jié)點，然后設(shè)置該節(jié)點為可以選擇狀態(tài)S3。S1和S2都是已經(jīng)確定的狀態(tài)，節(jié)點的選取只能從S3中選取。

取出最優(yōu)隊列里的第一個節(jié)點進行擴展：

將該節(jié)點設(shè)置為S1，同時按照公式4修改該節(jié)點的信息，然后把該節(jié)點放入空間樹的左節(jié)點；再將該節(jié)點設(shè)置為S2，不用修改其他節(jié)點信息直接放入空間樹的右節(jié)點。

對上面步驟的迭代就是具體的判定過程。相應(yīng)的流程如圖3所示。

本文在基于最小頂點覆蓋的探針部署算法的基礎(chǔ)上加以改進，提出了基于最小弱頂點覆蓋的探針部署算法：

在定義1的基礎(chǔ)上，由于探針設(shè)置在路由器或交換機等交換設(shè)備上，根據(jù)流量守恒，那么圖G還滿足以下兩條約束條件：

條件1。對圖G的頂點集V中的任意頂點v，其度Degree （v）≥2；

條件2。對圖G的頂點集V中的任意頂點v，滿足流守恒方程，即流進=流出。

圖3 基于最小頂點覆蓋的探針部署算法流程圖

盡管以下原因會將導(dǎo)致流守恒方程的失真，如：交換設(shè)備是數(shù)據(jù)的源或匯，而不僅僅是數(shù)據(jù)轉(zhuǎn)發(fā)器；多播導(dǎo)致輸出端口的數(shù)據(jù)復(fù)制；交換設(shè)備本身的數(shù)據(jù)包延遲或丟失。但是若干研究表明，流守恒方程所具有的相對誤差小于0.05%。

定義3（弱頂點覆蓋）：假定無向圖G(V，E)，目滿足對任意v∈V有Degree（v）≥2，稱S?V是圖G的弱頂點覆蓋集，當且僅當執(zhí)行以下操作能使E中所有的邊都可以被標記。

（1）標記所有與S中頂點相關(guān)聯(lián)的邊；（2）若某個頂點v 的Degree（v）-1條相關(guān)聯(lián)的邊己被標記，則標記剩下的那條相關(guān)聯(lián)的邊；（3）重復(fù)第（2）步，直到不能再標記新的邊為止。

顯然，由此弱頂點覆蓋S就可以得到圖G中各鏈路的流量。本文利用關(guān)聯(lián)矩陣的概念建立求解弱頂點覆蓋問題的模型，為此先給出以下定義。

定義4（關(guān)聯(lián)關(guān)系）：在無向圖G(V，E)中，若v∈V是e∈E的頂點之一，則稱v與e之間存在著關(guān)聯(lián)關(guān)系，記為vRe。

定義5（關(guān)聯(lián)矩陣）：圖G(V，E)的關(guān)聯(lián)矩陣A=（aij）是指如下定義的n×m矩陣：

根據(jù)關(guān)聯(lián)矩陣的定義，可知V的一個子集構(gòu)成圖G的一個覆蓋，當且僅當在它包含的節(jié)點所對應(yīng)的關(guān)聯(lián)矩陣的行中每列至少存在一個1。

根據(jù)以上分析，采用貪心算法可以對弱頂點覆蓋問題進

圖4 基于最小弱頂點覆蓋的算法流程圖

3 實驗驗證

本章節(jié)對所提算法進行了實驗驗證。本文實驗中圖5為對比實驗算法獲取的探針部署圖。圖6—7為本文所提算法獲得了探針部署圖。從圖7可以看出本文所提出的采用更少的探針算法能夠?qū)崿F(xiàn)對網(wǎng)絡(luò)的全覆蓋。

如圖5所示，所有紅色標注的路由器都是探針部署位置，共有43個。能夠覆蓋到圖中的所有路徑。即基于最小頂點覆蓋的探針部署方案如圖部署43個探針就可以實現(xiàn)該圖全圖各條邊的流量監(jiān)測。

圖5 基于最小頂點覆蓋的探針部署圖

表1表明了基于最小頂點覆蓋的方法在網(wǎng)絡(luò)節(jié)點為160個時，采用43個探針能夠?qū)崿F(xiàn)對網(wǎng)絡(luò)的全覆蓋。

表1 評價指標

需要指出的是，盡管分支限定法能求得最小頂點覆蓋的最優(yōu)解，但其計算復(fù)雜度高，花費時間長，并不能應(yīng)用于大規(guī)模問題。而且最小頂點覆蓋的最優(yōu)解并不一定是網(wǎng)絡(luò)流量監(jiān)測探針部署的最優(yōu)解，所以為了找到算法更簡便、耗時更短而且使用探針數(shù)更少的部署方案，下面將結(jié)合網(wǎng)絡(luò)流量守恒的性質(zhì)通過最小弱頂點覆蓋來部署探針。

如圖6所示，為基于最小弱頂點覆蓋的探針部署圖。該圖中所有紅色標注的路由器都是探針部署位置，共有32個。

圖6 基于最小弱頂點覆蓋的探針部署圖

圖7是該部署情況的驗證情況，圖中藍色路徑（共171條）表示該邊網(wǎng)絡(luò)流量可以直接監(jiān)測，橘色路徑（共14條）表示該邊網(wǎng)絡(luò)流量可以通過流量守恒算出。在按圖7所示部署32探針后所有的路徑都被橘色或藍色覆蓋，即可以監(jiān)測到整個路徑的網(wǎng)絡(luò)流量，具體的評價指標如表2所示。

圖7 探針部署驗證圖

表2 評價指標

與基于最小頂點覆蓋的部署方案相比，本方案使用的探針數(shù)更少，而且算法更簡單，耗時更短，是一種更優(yōu)秀的網(wǎng)絡(luò)流量監(jiān)測探針部署方案。但是這兩種探針部署防案都是被動測試，能夠利用端口鏡像，多路轉(zhuǎn)發(fā)以用鏈路串接等方式收集網(wǎng)絡(luò)中本身傳輸?shù)臄?shù)據(jù)包，包括業(yè)務(wù)數(shù)據(jù)包、信令數(shù)據(jù)包和管理信息數(shù)據(jù)包等，分析網(wǎng)絡(luò)性能，被動地監(jiān)測網(wǎng)絡(luò)性能，有著不增加額外流量，對網(wǎng)絡(luò)影響很小的優(yōu)點。

4 結(jié)語

本文研究了電力通信數(shù)據(jù)網(wǎng)的網(wǎng)絡(luò)層業(yè)務(wù)，在基于最小頂點覆蓋問題的貪心算法的基礎(chǔ)上，對其進行了改進，提出了一種基于最小弱頂點覆蓋的探針部署方法。該方法保證了在可以得到每一條鏈路流量的條件下，流量監(jiān)測數(shù)目的最小。仿真結(jié)果表明，本文所提方法使用的探針數(shù)目更少，網(wǎng)絡(luò)開銷和時間開銷更優(yōu)。

[1]GONG X, WANG K, GUO S, et al.Fault location algorithm based on probe in Electric Power Data Network[J].Network Operations and Management Symposium, 2015（12）：30-36.

[2]常晶.大規(guī)模網(wǎng)絡(luò)虛擬化監(jiān)測方法的研究與實現(xiàn)[D].北京：北京郵電大學(xué)，2014.

[3]王瑤，權(quán)楠，徐艷紅，等.IPv6技術(shù)在電力通信網(wǎng)的部署策略[C].北京：中國通信學(xué)會信息通信網(wǎng)絡(luò)技術(shù)委員會年會，2013.

[4]郭振興，黎文偉.分布式網(wǎng)絡(luò)故障監(jiān)測的探針部署方法[J].計算機系統(tǒng)應(yīng)用，2011（11）：59-62.

[5]汪玉成，楊陽，稂龍亞，等.基于改進貪心算法的電力數(shù)據(jù)網(wǎng)探針部署優(yōu)化算法[J].無線互聯(lián)科技，2016（5）：72-74.

[6]邢寧哲，紀雨彤.基于分布式探針的電力數(shù)據(jù)通信網(wǎng)綜合監(jiān)測方法[J].電力信息與通信技術(shù)，2016（1）：38-43.

[7]陳寶仁，吳贊紅.電力公網(wǎng)通信資源在線監(jiān)測技術(shù)方案探討[J].電力勘測設(shè)計，2012（6）：63-69.

[8]趙繼軍，白巍，馮楠，等.基于網(wǎng)絡(luò)編碼的PON中編碼機制優(yōu)化設(shè)計[J].光通信研究，2014（3）：38-41.

[9]王德麾，馮軍帥，宋海亮，等.基于無線傳感器網(wǎng)絡(luò)和3G/4G的遠程環(huán)境監(jiān)測系統(tǒng)研究[J].物聯(lián)網(wǎng)技術(shù)，2015（3）：17-18.

[10]孫蕊.一個面向IPv6的流量監(jiān)測原型系統(tǒng)的設(shè)計與實現(xiàn)[D].沈陽：東北大學(xué)，2010.

An optimization algorithm for probe deployment in power dispatching data network

Liu Yuming, Tian Feng
（Power Dispatching and Control Center of Yunnan Power Grid, Kunming 650011, China）

Network layer flow monitoring of large scale power communication data network problem is studied in this paper, and a method based on vertex cover and weak vertex cover is proposed in this paper. Based on the minimum vertex cover, flow conservation mechanism is introduced in the method, which can minimize the number of traffic monitoring under the conditions of obtaining every link flow. The simulation results show that compared with the minimum vertex cover problem, this paper puts forward a method of using less probe, with lower computational complexity and higher network performance.

electric power communication data network; probe deployment; vertex cover

云南電網(wǎng)有限責任公司科技項目；項目名稱：云南電力調(diào)度數(shù)據(jù)網(wǎng)分布式業(yè)務(wù)測量技術(shù)研究及應(yīng)用；項目編號：YNKJ00000094。

劉宇明（1975— ），男，云南昆明；研究方向：電力通信。