基于拓撲勢的傳送網(wǎng)匯聚節(jié)點評估方法研究＊

（湖南中移通信技術(shù)工程有限公司，長沙 410003）

基于拓撲勢的傳送網(wǎng)匯聚節(jié)點評估方法研究＊

陸聿，吳笛，姜艷紅，夏志朗

（湖南中移通信技術(shù)工程有限公司，長沙 410003）

本文從一個全新的視角去研究匯聚節(jié)點的拓撲特性，首次利用拓撲勢在城域傳送網(wǎng)絡(luò)下評估匯聚節(jié)點。結(jié)果顯示具有較高的精確性，為設(shè)計人員在選擇新的匯聚節(jié)點上提供了新的思路，且對現(xiàn)網(wǎng)已有匯聚節(jié)點合理性的后評估存在參考價值。

城域傳送網(wǎng)；匯聚節(jié)點；拓撲勢

1 引言

城域傳送網(wǎng)[1]分為城域骨干傳送網(wǎng)和有線接入網(wǎng)，其中城域骨干傳送網(wǎng)定位為綜合的承載平臺，主要包含核心節(jié)點、匯聚節(jié)點之間的一系列傳送實體，一般分為核心層和匯聚層，為滿足業(yè)務(wù)匯聚及疏導(dǎo)需求，帶寬顆粒較大，組網(wǎng)簡潔。有線接入網(wǎng)是城域傳送網(wǎng)的重要組成部分，是實現(xiàn)企業(yè)網(wǎng)絡(luò)和業(yè)務(wù)長期可持續(xù)發(fā)展的重要基礎(chǔ)保障之一，它是城域網(wǎng)中直接面對客戶需求的網(wǎng)絡(luò)，其網(wǎng)絡(luò)能力和網(wǎng)絡(luò)質(zhì)量直接影響業(yè)務(wù)的發(fā)展。

匯聚節(jié)點[2]是所有城域傳送網(wǎng)絡(luò)結(jié)構(gòu)中的必須組成部分，在各種各樣的移動傳輸進程中起著無可替代的作用。復(fù)雜網(wǎng)絡(luò)[3～5]的小世界、無標度、社區(qū)結(jié)構(gòu)等特性，也決定了網(wǎng)絡(luò)中每個節(jié)點的重要性是不同的。因此，如何有效地評估和度量網(wǎng)絡(luò)中各節(jié)點的重要性，不僅是網(wǎng)絡(luò)化數(shù)據(jù)挖掘研究要面臨的首要問題，也是復(fù)雜網(wǎng)絡(luò)、生物網(wǎng)絡(luò)[6]、社會網(wǎng)分析等領(lǐng)域的研究熱點，具有廣泛的應(yīng)用價值。

現(xiàn)階段新增匯聚節(jié)點的選擇都是設(shè)計人員基于現(xiàn)網(wǎng)的局部業(yè)務(wù)發(fā)展需求和光纜路由走向而選定的，相對于整個網(wǎng)絡(luò)的總體結(jié)構(gòu)，這種方式存在一定不精確性。這里，我們將城域傳送網(wǎng)看做一個物理系統(tǒng)，計算每一個節(jié)點的拓撲勢用于判別其在網(wǎng)絡(luò)中的重要程度，然后我們基于每個節(jié)點拓撲勢值的大小對所有的節(jié)點進行排序，選擇前5%的節(jié)點對其重要性進行分析識別。結(jié)果表明匯聚節(jié)點在城域傳送網(wǎng)中擁有較強的拓撲勢特征，基于拓撲勢的方法評估節(jié)點重要性能有效幫助設(shè)計人員縮小選擇新增匯聚節(jié)點的范圍，提高匯聚節(jié)點新增的精確性和合理性，且對現(xiàn)網(wǎng)已有匯聚節(jié)點合理性的后評估存在參考價值。

2 方法

受物理場的思想啟發(fā)，我們把城域傳送網(wǎng)看做一個包含n個節(jié)點及相互作用的物理系統(tǒng)。已知一個城域傳送網(wǎng)表示所有節(jié)點的集合，表示節(jié)點相互作用的集合，每一個節(jié)點周圍存在一個虛擬的作用場，位于場內(nèi)的節(jié)點都將受到其他節(jié)點的聯(lián)合作用。基于城域傳送網(wǎng)的聚類特性和模塊化，我們更傾向于采用代表短程場且具有良好數(shù)學(xué)性質(zhì)的高斯勢函數(shù)來描述節(jié)點之間的相互作用，并稱相應(yīng)的場為拓撲勢場。在這個拓撲勢場中，節(jié)點間的相互作用具有局部特性，每個節(jié)點的影響能力都會隨著網(wǎng)絡(luò)距離的增加而快速衰減。

給定一個的網(wǎng)絡(luò)G (V， E)，任一節(jié)點vi∈V的拓撲勢可表示為：

其中，dij表示節(jié)點vi和vi之間的網(wǎng)絡(luò)距離，本文采用最短路徑長度來度量；影響因子σ用于控制節(jié)點vi的影響范圍； mi≥0表示在節(jié)點vi影響范圍內(nèi)節(jié)點vi( j=1，…n)的質(zhì)量，用于描述每個節(jié)點的固有屬性。

在公式(1)中，節(jié)點vi的影響范圍被定義為受影響因子σ的控制，因此σ的取值將會很大程度上影響到拓撲勢場的分布，進而影響到每個節(jié)點在網(wǎng)絡(luò)中的重要性排序。通常，復(fù)雜網(wǎng)絡(luò)中最優(yōu)影響因子σ的選取是基于勢熵的計算獲得，而勢熵的計算公式如下：

根據(jù)表1的計算方式，我們計算了不同σ取值后的勢熵值，基于高斯函數(shù)數(shù)學(xué)性質(zhì)的最小化問題，我們認定本文影響因子σ的最優(yōu)取值為1.414。

表1 σ在不同取值區(qū)間的節(jié)點拓撲勢的計算方式

以圖1為例，當我們計算節(jié)點1（紅色節(jié)點）的拓撲勢時，綠色節(jié)點為節(jié)點1的直接鄰居節(jié)點，黃色節(jié)點為其間接鄰居節(jié)點，藍色節(jié)點我們認為是節(jié)點1的3跳節(jié)點，灰色節(jié)點為其4跳節(jié)點。

圖1 一個簡單網(wǎng)絡(luò)的拓撲勢分析

除了影響因子σ之外，mi和dij的取值都會對拓撲勢的值存在影響。在本文，我們默認mi和dij為1。基于拓撲勢定義，一個節(jié)點的重要性由它的拓撲勢取值決定，對于一個城域傳送網(wǎng)內(nèi)節(jié)點，其拓撲勢的值越大，則它越傾向于是匯聚的，我們認為其是匯聚節(jié)點的可能性越大。

3 實驗分析

為了說明拓撲勢是一種評估匯聚節(jié)點的有效方法，我們在城域傳送網(wǎng)中計算了每個節(jié)點的拓撲勢值。本文所有的實驗都是基于懷化市鶴城區(qū)城域傳送網(wǎng)和其城域匯聚節(jié)點數(shù)據(jù)集下進行的，我們對所有的實驗結(jié)果進行了統(tǒng)計分析。

3.1 數(shù)據(jù)來源

基于懷化市現(xiàn)有本地網(wǎng)網(wǎng)管信息，采用懷化市鶴城區(qū)城域傳送網(wǎng)做為實驗數(shù)據(jù)進行實驗。懷化市鶴城區(qū)城域傳送網(wǎng)包含中興、華為兩個平面，共包含272個節(jié)點和405條邊。

3.2 拓撲勢的可行性分析

幾十年來，一些研究人員陸續(xù)提出來了一系列基于網(wǎng)絡(luò)拓撲特性評估節(jié)點重要性的方法，如度中心性（DC）、介數(shù)中心性（BC）、接近度中心性（CC）、子圖中心性（SC）、特征向量中心性（EC）、信息中心性（IC）等。在上述的拓撲方法中，度中心性是最直接簡單的，它表示與節(jié)點直接相連的鄰居節(jié)點的個數(shù)。如果在城域傳送網(wǎng)中節(jié)點的度中心性值越大，則它更傾向于是匯聚節(jié)點。介數(shù)中心性被定義為網(wǎng)絡(luò)中所有最短路徑中經(jīng)過該節(jié)點的數(shù)目占所有最短路徑數(shù)的比例。節(jié)點的接近度中心性反比于該節(jié)點到網(wǎng)絡(luò)中其他所有節(jié)點的最短路徑之和。子圖中心性表示該節(jié)點參與網(wǎng)絡(luò)閉合回路的總數(shù)，它反映節(jié)點參與網(wǎng)絡(luò)模塊結(jié)構(gòu)的比重。節(jié)點特征向量中心性的值是基于城域傳送網(wǎng)的鄰接矩陣所計算的，節(jié)點u的特征向量中心性的值被定義為網(wǎng)絡(luò)鄰接矩陣的主特征向量的第u個分量，其基本思想是匯聚節(jié)點通常它的鄰居節(jié)點也是關(guān)鍵的。節(jié)點的信息中心性本質(zhì)上是測量以該節(jié)點為端點的路徑的調(diào)和平均長度。

為了驗證拓撲勢在評估匯聚節(jié)點上的性能，我們基于拓撲勢、子圖中心性、介數(shù)中心性、信息向量中心性、信息中心性、接近度中心性和度中心性分別計算了每個節(jié)點的重要性。與以前的處理過程類似，我們對所有節(jié)點按照拓撲勢值的大小做了降序排列，并選擇排序后的前5%的節(jié)點做為候選匯聚節(jié)點。我們之所以只取到前5%(13)的節(jié)點做為候選匯聚節(jié)點，是因為懷化市鶴城區(qū)城域傳送網(wǎng)現(xiàn)網(wǎng)的匯聚節(jié)點的個數(shù)僅為13個。

如圖2所示，拓撲勢同其它的方法一樣，當選擇前5%的節(jié)點作為候選匯聚節(jié)點時，能有效的識別真正的匯聚節(jié)點。但區(qū)別于僅依賴網(wǎng)絡(luò)本身拓撲特性的方法（子圖中心性、介數(shù)中心性、信息向量中心性、信息中心性、接近度中心性和度中心性），拓撲勢基于節(jié)點固有屬性和兩個節(jié)點之間的路徑權(quán)值 可以通過引入傳送網(wǎng)具體節(jié)點信息來完善其識別和評估匯聚節(jié)點的合理性。因此，拓撲勢是一種有效的評估匯聚節(jié)點的方法。

圖2 拓撲勢與其它方法的識別結(jié)果分析

3.3 拓撲勢的結(jié)果分析

圖3 拓撲勢識別匯聚節(jié)點精確性分析

如圖3所示，拓撲勢的結(jié)果在識別匯聚節(jié)點上具有較高的精度。當選擇前5%的節(jié)點做為候選匯聚節(jié)點時，我們發(fā)現(xiàn)其識別真正匯聚節(jié)點的數(shù)量達到10個，比例為76.92%。而通過對剩余的3個候選節(jié)點進行分析，我們發(fā)現(xiàn)這些節(jié)點都是現(xiàn)網(wǎng)匯聚節(jié)點的一階鄰居節(jié)點，且都是鶴城區(qū)核心節(jié)點的一階鄰居節(jié)點。

另外，對于拓撲勢在前5%的候選匯聚節(jié)點中無法找到的現(xiàn)網(wǎng)匯聚節(jié)點，我們同樣也對該些節(jié)點的各方面展開了分析，綜合發(fā)現(xiàn)這3個節(jié)點的地理位置都偏向于城郊或者待開發(fā)區(qū)域，其附近的接入節(jié)點較其它匯聚節(jié)點明顯偏少，該類匯聚節(jié)點設(shè)置的目的是為了更好整合附近傳輸資源以方便后期業(yè)務(wù)的發(fā)展。故基于傳送網(wǎng)本身拓撲特性，這類節(jié)點在設(shè)置后我們可以通過拓撲勢對其進行重新評估。

由此，基于拓撲勢的方法評估節(jié)點關(guān)鍵性能夠有效幫助設(shè)計人員縮小新增匯聚節(jié)點的范圍，提高識別新增匯聚節(jié)點的精確性和合理性，且對現(xiàn)網(wǎng)已有匯聚節(jié)點合理性的后評估存在參考價值。

4 總結(jié)與討論

復(fù)雜網(wǎng)絡(luò)中識別關(guān)鍵節(jié)點的研究一直是網(wǎng)絡(luò)拓撲結(jié)構(gòu)分析的一個熱點。在本文，我們從一個全新的視角去評估城域傳送網(wǎng)絡(luò)的匯聚節(jié)點，通過懷化鶴城區(qū)城域傳送網(wǎng)的實驗結(jié)果表明，匯聚節(jié)點在城域傳送網(wǎng)絡(luò)中有著很強的拓撲勢特征，拓撲勢方法在評估匯聚節(jié)點性能上精確度較高。

作為一個有效的分析網(wǎng)絡(luò)節(jié)點重要性的方法，拓撲勢同樣能應(yīng)用于其他復(fù)雜網(wǎng)絡(luò)的節(jié)點重要性分析，比如社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、PON網(wǎng)絡(luò)、數(shù)據(jù)承載網(wǎng)等。此外，對于現(xiàn)在各地區(qū)綜合業(yè)務(wù)區(qū)的劃分，從網(wǎng)絡(luò)拓撲結(jié)構(gòu)特性去分析也是一個新的思路。

在本文，我們默認各節(jié)點的固有屬性和最短路徑長度為1。然而，過去的一些研究表明，一些復(fù)雜網(wǎng)絡(luò)的特性同樣能被用來做為節(jié)點的固有屬性去計算拓撲勢的值，比如在傳送網(wǎng)中，每個節(jié)點的峰值流量信息，承載的業(yè)務(wù)量多少、匯聚節(jié)點的層級重要性等。將來的工作將會是進一步整合這些信息，再結(jié)合拓撲勢的特性去做一些研究。

[1] 陳曉鋒. 城域傳輸網(wǎng)網(wǎng)絡(luò)結(jié)構(gòu)的演進[J]. 現(xiàn)代電信科技，2003(8)：52-52.

[2] 王義濤， 郭曉非， 袁秀森. PTN 承載LTE業(yè)務(wù)適應(yīng)性分析[J].郵電設(shè)計技術(shù)， 2012(8)：57-62.

[3] 周濤， 柏文潔， 汪秉宏， 等. 復(fù)雜網(wǎng)絡(luò)研究概述[J]. 物理，2005，34(01)：0-0.

[4] 姚靜， 趙彤洲. 復(fù)雜社會網(wǎng)絡(luò)節(jié)點重要性研究[J]. 計算機與數(shù)字工程 44.1 (2016)：80-82.

[5] 白宇清， 李海健， 蔡青松. 移動P2P社會網(wǎng)絡(luò)中關(guān)鍵節(jié)點發(fā)現(xiàn)方法. 計算機科學(xué)與探索(3)，350-362.

[6] 陸聿. 基于拓撲勢的關(guān)鍵蛋白質(zhì)識別方法研究[D]. 長沙：中南大學(xué)， 2014.

A new method for evaluating convergent nodes based on topology potential of transmission network

LU Yu, WU Di, JIANG Yan-hong, XIA Zhi-lang
(Hunan Zhongyi Communication Technology Engineering Co., Ltd., Changsha 410003, China)

This paper is the first time that topology potential is used to evaluate convergent nodes from MAN transmission network. The experiment results show that the method for evaluating convergent nodes has high accuracy, it also provides a new train of thought for designers to choose a new convergent node. In addition, there is a great reference value based on the post-evaluation for the rationality of existing convergent nodes in present network.

MAN transmission network; convergent nodes; topology potential

TN915

A

1008-5599（2017）03-0083-04

2016-10-12

國家自然科學(xué)基金資助項目（No. 61370024）。