彭澤武 蔡雄 楊秋勇 蘇華權

摘 要：第五代網(wǎng)絡技術條件下配電通信網(wǎng)互聯(lián)可構成大規(guī)模光傳送網(wǎng)。為解決路由選擇、子載波數(shù)分配、各子載波調制階數(shù)分配的聯(lián)合優(yōu)化問題，結合最短k路由算法，提出一種近優(yōu)算法。為了檢驗該近優(yōu)方法的有效性，以一個中等規(guī)模網(wǎng)絡為例，將其與基于路由窮舉的最優(yōu)方法對比，結果表明，所提出的近優(yōu)方法以較小的k值就可以求得聯(lián)合優(yōu)化問題的最優(yōu)解，而計算時間較基于路由窮舉的聯(lián)合優(yōu)化最優(yōu)算法有顯著降低。

關鍵詞：配電網(wǎng);光正交頻分復用;子載波分配;軟件定義網(wǎng)絡;k最短路

中圖分類號：TN253 ? ? ? 文獻標識碼：A

隨著綠色發(fā)展的需要及第5代移動通信網(wǎng)絡（the fifth generation network， 5G）的實施，配網(wǎng)通信網(wǎng)面臨擴容和跨縣區(qū)互聯(lián)問題。擴容的首選是將光傳送網(wǎng)（optical transfer network， OTN）的有關技術移植到配網(wǎng)通信網(wǎng)。而多個互聯(lián)互通的地（縣）配網(wǎng)通信網(wǎng)整體上就構成一個大規(guī)模的光通信網(wǎng)絡。過去十年里，OTN經(jīng)歷了前所未有的技術進步[1-2]。從最初的固定線速到隨后的混合線速再到當前倡導的彈性光網(wǎng)絡（Elastic optical network， EON），網(wǎng)絡傳輸?shù)墓芾砗涂刂谱兊酶m合于具有突發(fā)性的數(shù)據(jù)業(yè)務[3-4]。EON的核心技術是光正交頻分復用（Optical orthogonal frequency multiple address， O-OFDMA）[4-5]。采用OFDMA使頻譜利用率明顯提高，因而單根光纖的傳輸容量也明顯提高[6]。此外，EON允許根據(jù)網(wǎng)絡負荷動態(tài)調整子載波數(shù)量及路由，可以從物理層支持軟定義網(wǎng)絡（software defined network， SDN）。

端到端路由、子載波及其調制階數(shù)分配是影響EON性能的主要因素。文獻[7]通過排序依據(jù) 各源-目的端的流量需求及路由選用調制方式，性能欠佳。文獻[8]運用線性整數(shù)規(guī)劃方法，節(jié)能效果優(yōu)于文獻[7]。文獻[9]建立了路由與子載波數(shù)及其調制階數(shù)分配聯(lián)合優(yōu)化方法，可得到最優(yōu)節(jié)能效果。但該方法需要的決策變量太多，無法運用到大規(guī)模EON中。

為此，提出一種新的路由與子載波及其調制階數(shù)聯(lián)合優(yōu)化分配方法，以期在復雜性和最優(yōu)性間作出均衡。

1 聯(lián)合優(yōu)化模型

1.1 無環(huán)k最短路由算法

所考慮的網(wǎng)絡中，每一條鏈路都是雙向對稱的，因此有關路由的討論都基于無向圖。k最短路由是指：對于給定的網(wǎng)絡中的指定源節(jié)點S和目的節(jié)點D，存在多條路由，其中第一短、第二短、…、第k短的路由構成所謂的最短k路由。[10]是較為經(jīng)典的研究k最短路的文獻，其計算復雜性相對較高。文獻[11]提出了一種基于回溯的k最短路算法，算法復雜性較文獻[10]有明顯降低，但由于它容許有環(huán)的存在，使得它在路由與子載波及其調制階數(shù)分配聯(lián)合優(yōu)化問題中不適用，因此先對文獻[11]所提出的算法進行改進，算法能給出任意一對指定節(jié)點對S-D間的無環(huán)k最短路由。

算法分為兩個階段。第一階段：運用Dijstra最短路算法計算出對于指定源節(jié)點S時，網(wǎng)絡中所有其他各節(jié)點到s的最短路及其相應最短距離，任一節(jié)點v到s的最短距離用d（s，v）表示。第二階段：從指定目的節(jié)點D通過回溯，得到S到D間的k條最短無環(huán)路。第2階段的流程見圖1?；厮葑阅康墓?jié)點D開始，回溯過程是一個迭代過程。設當前節(jié)點為c，則回溯的下一節(jié)點需要從遞增序列sq種挑選一個與回溯路徑上已經(jīng)歷節(jié)點不構成環(huán)且節(jié)點增量值IN（v）最小的節(jié)點。IN（v）的定義參照文獻[11]，是假定從當前回溯節(jié)點c經(jīng)其鄰節(jié)點v后沿S到v的最短路回溯到S的情況下該回溯路徑的總代價相對于最短路徑的總代價的增加量。迭代的每一步，需要從遞增序列sq中選取IN值最小的節(jié)點作為回溯的下一節(jié)點，這有兩種情況：一、當前回溯節(jié)點還不是S，被挑選的回溯下一跳會是當前回溯節(jié)點的一個與已經(jīng)歷的部分回溯路徑不構成環(huán)的子節(jié)點;二、當前回溯節(jié)點已是S，回溯已到達回溯樹的葉子節(jié)點，那接下來就是尋求另一條由D到S的回溯路徑，此時就需從遞增序列sq中挑選IN（）值最小的節(jié)點作為新的當前回溯節(jié)點，從整個回溯樹的構造上看，這個新的當前回溯節(jié)點最高可能是根節(jié)點D的某個鄰居，最低可能是剛回溯到的S（葉子節(jié)點）的父節(jié)點。為了維持回溯樹的可追溯性，遞增序列sq存儲的每個元素是回溯樹上的節(jié)點，它需要包含至少三個屬性：網(wǎng)絡節(jié)點標識、節(jié)點的IN（）值、回溯樹上的父節(jié)點標識。此外，由于對sq的添加或取出操作始終保持了其按IN（）值增序存放，因此每次取出sq序列中IN（）值最小的元素其實就是取出該序列的最前面那個元素。

1.2 路由子載波及其調制階數(shù)分配聯(lián)合優(yōu)化

EON采用O-OFDM，每個光收發(fā)器可使用若干連續(xù)子載波，每個子載波通?？蛇x用6種調制方式之一，其傳輸速率是12.5 Gbps的1到6倍。隨著調制階數(shù)的升高，各子載波所需的功耗近似線性增長而相應的最大傳輸距離按指數(shù)率衰減。文獻[9]對路由、子載波及其調制階數(shù)分配聯(lián)合優(yōu)化問題進行了研究，由于該文方法基于路由窮舉，將每個源-目的端間可能的路由都納入決策變量，因此可以給出聯(lián)合優(yōu)化的最優(yōu)解，但隨著網(wǎng)絡規(guī)模擴大，可能的路由數(shù)接近指數(shù)率增長，使得該文方法不能用于較大規(guī)模的網(wǎng)絡。作者在此提出基于k最短路由的路由與子載波及其調制階數(shù)的聯(lián)合優(yōu)化，以增強聯(lián)合優(yōu)化算法的實用性。

類似于文獻[8-9]，光傳輸網(wǎng)的傳送流量需求被認為是對稱的，因此問題建模及求解都只需考慮單個方向。節(jié)點對間的流量的方向及鏈路的正向約定與文獻[8-9]一致。

用M表示EON網(wǎng)絡中調制方式的最高階數(shù)，有流量需求的節(jié)點對數(shù)目用NT表示，網(wǎng)絡中的鏈路數(shù)用NL表示。按1.1節(jié)所述的路由算法為每個流量對找出k條路由，并為每個可能路由分配子載波及其調制階數(shù)。于是，為該第i個端到端流量對進行子載波數(shù)及調制階數(shù)分配的變量組合可擴展為一個含k×M個元素的向量。即Xi=（ni11，ni12，…，ni1M， ni21，ni22，…，ni2M， …， nik1，nik2，…，nikM），其中nijm表示第i通信對的第j路由使用第m類調制方式的載波數(shù)量，i∈{1，2，…，NT}，j∈{1，2，…，k}， m∈{1，2，…，M}。

綜上所述， 本節(jié)將EON網(wǎng)絡中路由與子載波數(shù)量及調制方式分配聯(lián)合優(yōu)化問題表示為以通信鏈路消耗總功率最小化為目標、受流量需求約束、鏈路容量約束、子載波總數(shù)約束及載波連續(xù)性約束的整數(shù)線性規(guī)劃問題。

1.3 聯(lián)合優(yōu)化問題求解

整數(shù)線性規(guī)劃問題是運籌學中一類較常見的問題，該類問題的典型求解方法是結合單純形法和割平面法，此外，還有分支-定界法[12]。可以采用數(shù)學工具軟件MATLAB R2014中的專用函數(shù)求解該問題。限于篇幅，該專用函數(shù)的算法流程不再贅述。

2 計算實例

仍以文獻[8-9]中所給的南方某省電網(wǎng)通信骨干網(wǎng)為例，給出按文中所提出的聯(lián)合優(yōu)化方法所得的結果。該網(wǎng)絡含有31個節(jié)點、41對雙向鏈路、58對節(jié)點間存在雙向對稱流量需求，單向流量需求最小為10 Gbps，最大為140 Gbps。其中絕大多數(shù)節(jié)點間距離小于125km，其最高可用調制階數(shù)均能達64-QAM（單載波最大容量75 Gbps）;只有極少量節(jié)點間跨距大于125km 但小于250km，在不使用光中繼的情況下這種鏈路可用的最高調制階數(shù)為32QAM（單載波最大容量62.5 Gbps）。

根據(jù)上述網(wǎng)絡拓撲、鏈路容量和流量需求，我們先按1.1節(jié)所述算法計算出在給定k值條件下每個流量需求對間的k條最短路由，隨后按1.2節(jié)所述方法在MATLAB R2016b上編寫路由子載波及其調制方式聯(lián)合優(yōu)化程序，運用intlinprog（）函數(shù)求解線性整數(shù)規(guī)劃問題，得到較高精度的子載波及其調制方式分配的近優(yōu)解，并將計算結果及計算時間與文獻[9]進行對比。我們分別二者的對比見表3。

從表1可以看出，上節(jié)所提出的基于k最短路由的路由子載波及其調制方式分配聯(lián)合優(yōu)化算法，其給出的網(wǎng)絡鏈路總功耗及所需的計算時間都與k的取值有很大關系。當k取1時，所用的路由僅一條最短路由，此時近優(yōu)方法給出的結果及計算時間與文獻[8]相同。隨著k取值逐漸增大，每對源-目的端間可同時使用的路由數(shù)量增加，路由選擇子載波及其調制階數(shù)分配聯(lián)合優(yōu)化的效果增強，當k取3時，總功耗為24895 瓦，與文獻[9]所給的最優(yōu)值相等，此后繼續(xù)增加k值，總功耗不再降低，可見當k取值足夠大時，基于k最短路由的聯(lián)合優(yōu)化算法能給出最優(yōu)解，而同時，根據(jù)表1的結果還能看出，基于k最短路由的聯(lián)合優(yōu)化算法在能給出最優(yōu)解的同時，所用的計算時間不到文獻[9]的十分之一。本節(jié)所用的算例里，是一個省級電網(wǎng)通信網(wǎng)，只能算一個中小規(guī)模的網(wǎng)絡，對于真正的大型網(wǎng)絡，由于存儲空間需求和計算復雜性限制，文獻[9]提出的基于路由窮舉的聯(lián)合優(yōu)化方法將無法在單臺計算機上使用，而近優(yōu)求解方法的存儲空間需求和計算復雜度都與所選的k值有關，通過將k控制在一個合理范圍，可以使所求得的分配方案接近最優(yōu)解，而計算時間和空間復雜度卻在當前普通臺式機可以承受的范圍內(nèi)。

可見，基于k最短路的路由子載波及調制方式分配聯(lián)合優(yōu)化算法，是一種兼顧存儲空間需求、算法時間復雜度和結果近優(yōu)性的算法，可適用于求解大規(guī)模EON骨干網(wǎng)的路由與子載波及其調制階數(shù)分配聯(lián)合優(yōu)化問題。

3 實 施

第2節(jié)所提出的有關路由子載波及其調制方式聯(lián)合優(yōu)化分配近優(yōu)算法，考慮到在配網(wǎng)通信網(wǎng)的實際條件下，絕大多數(shù)流量局限于屬于同一地（縣）的供電局或變電站等節(jié)點間，因此最短路由數(shù)可以取得較小，因而計算時間較短。上述算法可以在具有軟件定義網(wǎng)絡（SDN）的框架下實現(xiàn)。

首先，為了支持SDN，首先需要解決IP網(wǎng)絡與光傳送網(wǎng)的跨層融合問題。解決辦法是在開源網(wǎng)絡操作系統(tǒng)ONOS基礎上建立一個通用的控制器模型，重點是拓展一個通用混合框架，使其不僅適用于單個網(wǎng)絡節(jié)點，還能適用于一個采用同種傳輸技術的網(wǎng)絡域[13]。其次，按照SDN的規(guī)則，將網(wǎng)絡劃分為應用面、控制面和數(shù)據(jù)面;其中控制面掌握網(wǎng)絡全局信息，是SDN的核心部分，在以EON為基礎的配網(wǎng)通信中，數(shù)據(jù)面的主題就是EON傳送網(wǎng);經(jīng)過IP網(wǎng)絡與EON光網(wǎng)絡融合后，控制面與數(shù)據(jù)面間通過OpenFlow協(xié)議交換有關信息，第2節(jié)所述的路由協(xié)議及資源分配聯(lián)合優(yōu)化的計算由控制面完成，而資源分配的落實與實施最終由數(shù)據(jù)面即光傳送網(wǎng)進行。

4 結 論

通過對未來配網(wǎng)通信網(wǎng)的演化趨勢進行分析，引出了大規(guī)模彈性光網(wǎng)絡中路由與子載波及其調制階數(shù)分配聯(lián)合優(yōu)化問題，提出了一種結合最短路的路由子載波及調制方式分配聯(lián)合優(yōu)化方法。建立了以降低通信鏈路總功耗為目標、以鏈路容量限制、流量需求限制和子載波總數(shù)限制附帶波長連續(xù)性限制等多約束條件的路由子載波及調制方式分配聯(lián)合優(yōu)化問題的線性整數(shù)規(guī)劃模型。以一個省級電力通信網(wǎng)為例，對于中小型網(wǎng)絡，設定較小的k值就能求得最優(yōu)解。因此，對于大規(guī)模網(wǎng)絡，運用本算法，通過合理增大k值，可以獲得路由子載波及其調制階數(shù)的近優(yōu)解。文末，對在軟件定義網(wǎng)絡中實施基于k最短路的路由子載波及調制方式分配聯(lián)合優(yōu)化核心算法的途徑進行了探討。

參考文獻

[1] TANIMURA T， HOSHIDA T， KATO T， el al. Data analytics based optical performance monitoring technique for optical transport networks [A].DOVERSPIKE ?R D. Proceedings of Optical Fiber Communications Conference and Exposition [C].San Diego， California： OSA， 2018，1-15：1-3.

[2] FIORANI M， TOMBAZ S， MARTENSSON J， et al. Modeling energy performance of C-RAN with optical transport in 5G network scenarios [J]. IEEE/OSA Journal of Optical Communication and Networking， 2016， 8（11）： B21-B34.

[3] SONG M， PINCEMIN E， JOSTEN A， et al. Flexible optical cross-connects for high bit rate elastic photonic transport networks [J]. IEEE/OSA Journal of Optical Communication and Networking， 2016， 8（7）：A126-A140.

[4] FALLAHPOUR A， BEYRANVAND H， SALEHI J. Energy efficient manycast routing and spectrum assignment in elastic optical networks for cloud computing environment [J]. Journal of Lightwave Technology， 2015， 33（19）：4008-4018.

[5] WEINSTEIN S B. The history of orthogonal frequency-division multiplexing [J]. IEEE Communications Magazine， 2009， 11：26-35.

[6] CHRISTODOULOPOULOS K， TOMKOS I， VARVARIGOS E. Elastic bandwidth allocation in fexible OFDM-based optical networks [J]. IEEE J. Lightw. Technol.， 2011， 29（9）： 1354-1366.

[7] ZHONG M C， GONG L， LI D， et al. Optical trapping of core-shell magnetic microparticles by cylindrical vector beams [J]. Applied Physics Letters， 2014， 105（18）：869-874.

[8] 陳振輝，陳輝煌.電力通信光傳送網(wǎng)子載波調制方式優(yōu)化分配方法[J].光通信技術，2019，43（2）： 4-17.

[9] 許世納，施展.光傳送網(wǎng)中路由與子載波調制方式分配聯(lián)合優(yōu)化方法[J].光通信技術，2019，43（5）： 54-57.

[10]CARLYLE ? W M， WOOD ?R K.Near-shortest and k-shortest simple paths [J].Networks， 2005， 46（2）： 98-109.

[11]李成江.新的 k 最短路算法[J].山東大學學報（理學版），2006，41（4）： 40-43.

[12]馬仲蕃.線性整數(shù)規(guī)劃的數(shù)學基礎[M].北京：科學出版社，2017.

[13]周宇.面向IP及光網(wǎng)絡融合的控制技術研究 [D].北京： 北京郵電大學，2018.