基于機(jī)器學(xué)習(xí)的骨干網(wǎng)路由參數(shù)模型構(gòu)建方法

郝錚，李曉良，趙培，尹長(zhǎng)川

（1.北京郵電大學(xué)信息與通信工程學(xué)院，北京 100876；2.中國(guó)移動(dòng)通信集團(tuán)設(shè)計(jì)院有限公司，北京 100080）

1 引言

以WDM（Wavelength Division Multiplexing，波分復(fù)用）/OTN（Optical Transport Network，光傳送網(wǎng)）為主導(dǎo)的光傳送網(wǎng)作為基礎(chǔ)承載網(wǎng)絡(luò)，為大顆粒業(yè)務(wù)、數(shù)據(jù)網(wǎng)和移動(dòng)網(wǎng)提供了透明靈活的承載平臺(tái)。隨著國(guó)家“寬帶中國(guó)”戰(zhàn)略工程及戰(zhàn)略方案的逐步推進(jìn)實(shí)施，我國(guó)寬帶網(wǎng)絡(luò)基礎(chǔ)設(shè)施建設(shè)已進(jìn)入高速發(fā)展時(shí)期，骨干網(wǎng)規(guī)模呈幾何級(jí)數(shù)增長(zhǎng)。傳統(tǒng)的網(wǎng)絡(luò)設(shè)計(jì)是以CAD和EXCEL表格為基礎(chǔ)的。CAD數(shù)據(jù)是非結(jié)構(gòu)化的，受幅面影響，表達(dá)內(nèi)容有限，難以查詢(xún)和統(tǒng)計(jì)；EXCEL數(shù)據(jù)不規(guī)范，難以統(tǒng)一管理，易錯(cuò)難審校，且數(shù)據(jù)間的關(guān)聯(lián)關(guān)系通過(guò)公式和引用實(shí)現(xiàn)，易錯(cuò)且效率低下。隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，網(wǎng)絡(luò)資源數(shù)據(jù)的不斷增長(zhǎng)，以人工方式對(duì)網(wǎng)絡(luò)進(jìn)行規(guī)劃優(yōu)化和運(yùn)營(yíng)維護(hù)的速度和效率已經(jīng)陷入瓶頸，網(wǎng)絡(luò)規(guī)劃設(shè)計(jì)工作的軟件化、工具化和自動(dòng)化已經(jīng)勢(shì)在必行。

但是，傳送網(wǎng)規(guī)劃，尤其是WDM/OTN的路由選擇和資源分配工作，需要針對(duì)網(wǎng)絡(luò)整體做多目標(biāo)設(shè)計(jì)，要根據(jù)網(wǎng)絡(luò)資源、業(yè)務(wù)情況靈活地配置。如何能讓不具備通信方面的專(zhuān)家級(jí)知識(shí)、缺乏網(wǎng)絡(luò)規(guī)劃經(jīng)驗(yàn)的計(jì)算機(jī)程序設(shè)計(jì)人員編寫(xiě)出能夠緊密結(jié)合業(yè)務(wù)與網(wǎng)絡(luò)發(fā)展情況，充分考慮網(wǎng)絡(luò)規(guī)劃整體思路、工作流程與業(yè)務(wù)需求的網(wǎng)絡(luò)規(guī)劃工具軟件，是一個(gè)非常具有實(shí)際應(yīng)用價(jià)值并且富有挑戰(zhàn)的問(wèn)題。

2 骨干傳送網(wǎng)路由規(guī)劃簡(jiǎn)析

骨干傳送網(wǎng)規(guī)劃通常是在多約束、多需求的條件下的決策過(guò)程。規(guī)劃工作的約束性體現(xiàn)在，網(wǎng)絡(luò)的傳輸技術(shù)、現(xiàn)網(wǎng)拓?fù)浣Y(jié)構(gòu)、容量限制等會(huì)對(duì)業(yè)務(wù)電路的配置起到制約和限制作用；需求性體現(xiàn)在，網(wǎng)絡(luò)規(guī)劃建設(shè)是業(yè)務(wù)驅(qū)動(dòng)的，電路規(guī)劃的根本目的是要滿(mǎn)足承載用戶(hù)的需求。如圖1所示，如果將規(guī)劃過(guò)程看做一個(gè)決策函數(shù)，那么網(wǎng)絡(luò)的約束和業(yè)務(wù)的需求都可以作為輸入?yún)?shù)傳入，而決策函數(shù)的輸出即是優(yōu)化或最優(yōu)的網(wǎng)絡(luò)規(guī)劃。

圖1 網(wǎng)絡(luò)規(guī)劃決策函數(shù)

一般來(lái)說(shuō)，規(guī)劃過(guò)程約束因素主要有：技術(shù)約束、現(xiàn)網(wǎng)拓?fù)浼s束、物理約束、經(jīng)濟(jì)和政策約束等。另外，網(wǎng)絡(luò)規(guī)劃還會(huì)受業(yè)務(wù)的實(shí)際需求影響，主要包括：帶寬需求、保護(hù)方式和QoS等。

在路由選擇和資源分配中，通常使用網(wǎng)絡(luò)費(fèi)用或其他性能參數(shù)（例如可擴(kuò)展性、可靠性等）作為目標(biāo)函數(shù)，最終做出的路由規(guī)劃決策應(yīng)當(dāng)是在給定約束下以最小代價(jià)滿(mǎn)足傳輸需求。不過(guò)，有時(shí)難以量化所有的技術(shù)標(biāo)準(zhǔn)和設(shè)計(jì)約束，對(duì)于一個(gè)結(jié)構(gòu)復(fù)雜的網(wǎng)絡(luò)，過(guò)于理想化的自動(dòng)規(guī)劃設(shè)計(jì)方案，往往會(huì)使規(guī)劃問(wèn)題得到多個(gè)滿(mǎn)足條件的解。另外，實(shí)際的路由規(guī)劃決策往往依賴(lài)于設(shè)計(jì)人員的經(jīng)驗(yàn)，其決策過(guò)程很難準(zhǔn)確詳實(shí)地傳達(dá)給軟件開(kāi)發(fā)人員，也很難被抽象為邏輯程序，所以在此類(lèi)軟件的設(shè)計(jì)研發(fā)過(guò)程中，難免會(huì)遇到設(shè)計(jì)決策難以軟件化的情況，軟件開(kāi)發(fā)人員與網(wǎng)絡(luò)設(shè)計(jì)人員之間存在著“信息鴻溝”。

針對(duì)這種問(wèn)題，本文提出以機(jī)器學(xué)習(xí)分類(lèi)算法為工具，從歷史設(shè)計(jì)決策中提煉各約束因素權(quán)重系數(shù)，構(gòu)建路由參數(shù)模型，從而實(shí)現(xiàn)路由選擇的智能化。

3 骨干傳送網(wǎng)的資源數(shù)據(jù)和歷史路由數(shù)據(jù)

一般來(lái)說(shuō)，骨干傳送網(wǎng)的資源數(shù)據(jù)可以分為三個(gè)層級(jí)：傳輸局站層、復(fù)用段層、波長(zhǎng)層，其關(guān)系如圖2所示：

圖2 骨干傳送網(wǎng)資源數(shù)據(jù)層級(jí)

除了基礎(chǔ)資源數(shù)據(jù)，還需要建立一套用于描述業(yè)務(wù)需求與規(guī)劃結(jié)果的數(shù)據(jù)結(jié)構(gòu)，至少應(yīng)包括以下幾部分：

（1）業(yè)務(wù)光通路需求。即骨干網(wǎng)中大業(yè)務(wù)顆粒的光通道業(yè)務(wù)需求，主要包含光通道編號(hào)、起始節(jié)點(diǎn)局站、帶寬需求、保護(hù)方式和業(yè)務(wù)類(lèi)型等屬性。

（2）路由。一個(gè)路由對(duì)象對(duì)應(yīng)了一條完整的規(guī)劃好的鏈路，但它不描述具體的路由鏈路內(nèi)容，只描述路由的基本信息，主要包括所屬光通道是工作路由還是保護(hù)路由等屬性。

（3）路由鏈路段。描述一條路由中的一段鏈路，主要包括所屬路由、鏈路序號(hào)和使用波道等屬性。

4 網(wǎng)絡(luò)數(shù)據(jù)的預(yù)處理

為了使網(wǎng)絡(luò)的資源數(shù)據(jù)、需求數(shù)據(jù)和規(guī)劃結(jié)果數(shù)據(jù)轉(zhuǎn)變?yōu)檫m合機(jī)器學(xué)習(xí)的樣本，需要對(duì)其進(jìn)行預(yù)處理工作。如圖3所示，本文提出利用原始數(shù)據(jù)，生成兩類(lèi)樣本數(shù)據(jù)：拓?fù)溆绊憳颖竞唾Y源影響樣本。

圖3 樣本數(shù)據(jù)的組成

其中，拓?fù)溆绊憳颖局饕枋隽随溌烽L(zhǎng)度、自然地形等拓?fù)涮匦詫?duì)決策的影響，以拓?fù)涮卣髯鳛閷傩?，以選擇結(jié)果作為分類(lèi)標(biāo)簽。形象地講，拓?fù)溆绊懣梢灶?lèi)比為道路交通中的道路方向、長(zhǎng)度、坡度等特性，即“朝什么地方走”。

資源影響樣本主要描述了鏈路中帶寬、空閑波道占比、設(shè)備轉(zhuǎn)接難度、跨域成本和是否需要拆分波道等資源特性對(duì)決策的影響，以資源特征為屬性，以選擇結(jié)果為分類(lèi)標(biāo)簽。資源影響也可以與道路交通類(lèi)比，它相當(dāng)于在選定了“朝什么方向走”后，該選擇什么樣的交通方式走過(guò)去，即“該怎么走”。

基于上述分類(lèi)原理，結(jié)合將規(guī)劃人員路由決策參數(shù)化這一指導(dǎo)思想，本課題提出按照以下思路進(jìn)行數(shù)據(jù)預(yù)處理：

（1）歷史路由的每一條鏈路的光纖復(fù)用段對(duì)應(yīng)一組樣本數(shù)據(jù)，該樣本包含了此決策的業(yè)務(wù)需求數(shù)據(jù)以及該光纖復(fù)用段的資源信息，并以此作為資源影響樣本的屬性，由于該光纖復(fù)用段是被最終選定用于路由的，所以分類(lèi)標(biāo)簽置為1。

（2）對(duì)于同局站段下沒(méi)被選擇的每條復(fù)用段，也將其整理成為一組資源影響樣本，其分類(lèi)標(biāo)簽置為0，表示未被選擇。

（3）歷史路由的每一條鏈路的局站段對(duì)應(yīng)于一組樣本數(shù)據(jù)，該樣本包含了此決策的業(yè)務(wù)需求數(shù)據(jù)以及該鏈路的拓?fù)湫畔?，并以此作為分?lèi)樣本的屬性。由于該局站是最終選定用于路由的，所以分類(lèi)標(biāo)簽置為1。

（4）設(shè)（3）中所述被選中的局站段起始端局站為A站，終止端為B站，則路由行至A站時(shí)會(huì)有一條或多條局站段可以選作下一跳鏈路，沒(méi)被選擇的每一條局站段即可生成一組拓?fù)溆绊憳颖荆浞诸?lèi)標(biāo)簽置為0。

以中國(guó)移動(dòng)十一期工程網(wǎng)絡(luò)數(shù)據(jù)為例，選取若干比較典型的影響因素進(jìn)行數(shù)據(jù)預(yù)處理，拓?fù)溆绊憳颖九c資源影響樣本的表結(jié)構(gòu)如表1和表2所示：

表1 拓?fù)溆绊憳颖臼纠?/p>

表2 資源影響樣本示例

5 機(jī)器學(xué)習(xí)分類(lèi)模型仿真及性能分析

5.1 樸素貝葉斯分類(lèi)器基本原理及模型構(gòu)建

貝葉斯分類(lèi)器（Bayes classifier）是一種基于貝葉斯決策論的分類(lèi)器，是概率框架下實(shí)施決策的一種典型算法。其基本思想是基于樣本和分類(lèi)標(biāo)簽，利用貝葉斯定理求解使后驗(yàn)概率最大化的參數(shù)模型。

假設(shè)有N種可能的分類(lèi)標(biāo)簽，記為Υ={c1, c2, ……,cN}，樣本記為x，則令后驗(yàn)概率最大化的貝葉斯分類(lèi)器為：

在實(shí)際應(yīng)用中，常常假定樣本具有“屬性獨(dú)立性”，從而可以將聯(lián)合條件概率的求解簡(jiǎn)化為每個(gè)屬性條件概率的乘積，這就是樸素貝葉斯分類(lèi)器。

基于樸素貝葉斯分類(lèi)器，可以構(gòu)建波長(zhǎng)路由的拓?fù)錄Q策和資源決策概率參數(shù)模型。采用無(wú)監(jiān)督的等深分箱法將連續(xù)型數(shù)據(jù)離散化，然后將樣本數(shù)據(jù)采用樸素貝葉斯分類(lèi)算法進(jìn)行分類(lèi)器參數(shù)計(jì)算，可以得到對(duì)應(yīng)于所有屬性及分類(lèi)標(biāo)簽，即P(xi|c)及P(c)。表3展示了距離比（DIST_RATIO）這一拓?fù)溆绊懸蛩氐膮?shù)模型：

表3 距離比（DIST_RATIO）的樸素貝葉斯分類(lèi)器參數(shù)模型

可以看出，隨著距離比的增大，P(xi|c=0)呈現(xiàn)下降趨勢(shì)，而P(xi|c=1)呈現(xiàn)減小趨勢(shì)，這也與實(shí)際的規(guī)劃思路相吻合：如果下一跳決策使得路由朝著離業(yè)務(wù)通路終點(diǎn)很遠(yuǎn)的地方行進(jìn)，那么這個(gè)決策很有可能是不合理的，不被采用的。同理，其他屬性也可以按照同樣思路分析，從而構(gòu)建出完整的概率參數(shù)模型。

5.2 決策樹(shù)基本原理及模型構(gòu)建

決策樹(shù)算法是以樣本示例為基礎(chǔ)的歸納學(xué)習(xí)算法，它從一個(gè)無(wú)序的樣本集合中歸納出一組基于樹(shù)結(jié)構(gòu)表示的分類(lèi)規(guī)則。決策樹(shù)的每個(gè)非葉子結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)屬性測(cè)試，每個(gè)子結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)分類(lèi)結(jié)果。每個(gè)非葉子結(jié)點(diǎn)包含的樣本集合根據(jù)這個(gè)結(jié)點(diǎn)的測(cè)試判定結(jié)果，將樣本集合劃分到相應(yīng)的子結(jié)點(diǎn)中。典型的決策樹(shù)算法有ID3、C4.5和CART。

基于決策樹(shù)算法，集成后剪枝算法，可以構(gòu)建波長(zhǎng)路由的拓?fù)錄Q策和資源決策的決策樹(shù)模型，如圖4所示：

圖4 決策樹(shù)參數(shù)模型

5.3 Logistic回歸分類(lèi)器基本原理及模型構(gòu)建

Logistic回歸分類(lèi)器屬于廣義線(xiàn)性回歸模型，雖然名稱(chēng)中含有“回歸”兩字，但其本質(zhì)是一種二分類(lèi)算法。Logistic回歸分類(lèi)器具有十分簡(jiǎn)潔的算法表達(dá)式：

對(duì)于一組樣本x，將其輸入分類(lèi)函數(shù)hθ(x)，若輸出大于0.5，則將該樣本分類(lèi)為1，否則分類(lèi)為0。Logistic回歸分類(lèi)器的構(gòu)造方法就是求出特征參數(shù)向量θ。

基于Logistic回歸算法，采用梯度下降法求取特征參數(shù)向量θ，可以構(gòu)建波長(zhǎng)路由的拓?fù)錄Q策和資源決策的Logistic回歸分類(lèi)器模型，如表4所示。

該參數(shù)模型即資源影響的特征參數(shù)向量θr。通過(guò)上表可以明顯看出，需要設(shè)備轉(zhuǎn)接、需要拆分波長(zhǎng)以及低波道空閑率等因素的θ值均為負(fù)數(shù)，說(shuō)明如果這些屬性值為1，則對(duì)分類(lèi)為0有幫助。對(duì)應(yīng)于實(shí)際的工程選路，這些因素都會(huì)造成額外的設(shè)備成本，規(guī)劃設(shè)計(jì)人員會(huì)盡量避免這種情況發(fā)生。

表4 Logistic回歸分類(lèi)器參數(shù)模型

表5 三種分類(lèi)算法特點(diǎn)比較分析

5.4 算法性能分析

三種分類(lèi)算法自身的優(yōu)劣勢(shì)以及與骨干傳送網(wǎng)路由規(guī)劃的契合度如表5所示。

另外，經(jīng)平臺(tái)仿真計(jì)算，三種分類(lèi)器在資源影響樣本和拓?fù)溆绊憳颖旧系男阅苋绫?所示：

表6 三種分類(lèi)算法性能比較

由以上結(jié)果可知，雖然決策樹(shù)整體性能比其余兩種算法好，但決策樹(shù)算法自身與骨干傳送網(wǎng)路由規(guī)劃算法的契合度不高，所以不宜采用。雖然Logistic回歸分類(lèi)模型在中國(guó)移動(dòng)十一期工程的網(wǎng)絡(luò)數(shù)據(jù)較樸素貝葉斯分類(lèi)模型有著一定的優(yōu)勢(shì)，但二者差距不大，在選型時(shí)可針對(duì)實(shí)際性能進(jìn)行靈活地選擇。

6 參數(shù)模型測(cè)試及結(jié)果

6.1 參數(shù)模型的運(yùn)用

參數(shù)模型構(gòu)建完成后，可運(yùn)用參數(shù)模型，基于概率或邊權(quán)重進(jìn)行路由規(guī)劃和資源分配。例如，構(gòu)建Logistic回歸分類(lèi)器參數(shù)模型，然后利用拓?fù)溆绊憛?shù)，基于KSP算法計(jì)算出若干備選路由，再利用拓?fù)溆绊憛?shù)和資源影響參數(shù)，針對(duì)每一條路由求取目標(biāo)函數(shù)總和，從而選擇使函數(shù)最大化的路由作為結(jié)果路由。

6.2 測(cè)試方法及結(jié)果

在實(shí)際網(wǎng)絡(luò)數(shù)據(jù)下，利用上述建模方案構(gòu)建參數(shù)模型，完全模擬前期工程網(wǎng)絡(luò)環(huán)境和需求環(huán)境，進(jìn)行歷史路由重排，所得結(jié)果與歷史真實(shí)選路結(jié)果進(jìn)行比對(duì)驗(yàn)證，主要以路徑重合率和資源命中率兩個(gè)指標(biāo)對(duì)驗(yàn)證結(jié)果進(jìn)行評(píng)估。

路徑重合率的定義為：

式(3)中，NL∩L'表示軟件選路結(jié)果與歷史路由重合的局站鏈路段數(shù)量，NL表示系統(tǒng)選路結(jié)果局站鏈路段數(shù)量。

資源命中率Rr的定義為：

式(4)中，NR∩R'表示重合局站段中的資源命中數(shù)量，NL∩L'表示重合局站段數(shù)量。

基于中國(guó)移動(dòng)九到十一期骨干傳送網(wǎng)工程數(shù)據(jù)，依照本文所述參數(shù)模型構(gòu)建方法，結(jié)合有效路由算法，通過(guò)以上驗(yàn)證方式得到的結(jié)果如圖5所示：

圖5 歷史路由重排準(zhǔn)確率

7 結(jié)束語(yǔ)

本文針對(duì)WDM/OTN骨干傳送網(wǎng)路由規(guī)劃設(shè)計(jì)軟件平臺(tái)在開(kāi)發(fā)過(guò)程中遭遇的參數(shù)化困難問(wèn)題，提出了一種基于機(jī)器學(xué)習(xí)分類(lèi)算法的路由參數(shù)模型構(gòu)建方法。經(jīng)實(shí)際工程數(shù)據(jù)驗(yàn)證，結(jié)合專(zhuān)業(yè)設(shè)計(jì)人員分析評(píng)價(jià)，該方法實(shí)現(xiàn)了軟件路由規(guī)劃邏輯與設(shè)計(jì)人員決策過(guò)程的高度擬合，基本可以替代傳統(tǒng)人工選路工作，大幅提升了網(wǎng)絡(luò)規(guī)劃工作的效率。并且，考慮到機(jī)器學(xué)習(xí)可以使參數(shù)模型不斷迭代優(yōu)化這一特性，該方法有助于提升規(guī)劃軟件平臺(tái)的智能化和開(kāi)發(fā)過(guò)程的高效化。

[1] 黃善國(guó). 光網(wǎng)絡(luò)規(guī)劃的與優(yōu)化[M]. 北京: 人民郵電出版,2011.

[2] 王健等. 光傳送網(wǎng)（OTN）技術(shù)、設(shè)備及工程應(yīng)用[M].北京: 人民郵電出版社, 2016.

[3] 史培明,周奎翰. OTN規(guī)劃探討[J]. 電信技術(shù), 2017(8):65-68.

[3] 劉海濤,楊斌. OTN網(wǎng)絡(luò)建設(shè)規(guī)劃[J]. 電信工程技術(shù)與標(biāo)準(zhǔn)化, 2010,23(4): 58-61.

[4] 吳春祥,孫立矗. 我國(guó)OTN標(biāo)準(zhǔn)化現(xiàn)狀及發(fā)展趨勢(shì)[J]. 硅谷, 2011(22): 23.

[5] 李勇. OTN技術(shù)在長(zhǎng)途傳輸網(wǎng)中的應(yīng)用探討[J]. 郵電設(shè)計(jì)技術(shù), 2012(12): 71-75.

[6] Alwayn V. Optical network design and implementation[M].Cisco Press, 2004.

[7] H Holler, S Vosz. A heuristic approach for combined equipment-planning and routing in multi-layer SDH/WDM networks. Feature Cluster: Heuristic and Stochastic Methods in Optimization[J]. European Journal of Operational Research, 2006.

[8] 徐海峰. OTN系統(tǒng)規(guī)劃和應(yīng)用探討[J]. 中國(guó)新通信,2017,19(10): 72-73.

[9] 李萌. OTN的規(guī)劃與設(shè)計(jì)[J]. 郵電設(shè)計(jì)技術(shù), 2013(6):63-66.

[10] 周志華. 機(jī)器學(xué)習(xí)[M]. 北京: 清華大學(xué)出版社, 2016. ★