彭澤武 蔡雄 楊秋勇 蘇華權(quán)

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

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

中圖分類號(hào)：TN253 ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 計(jì)算實(shí)例

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

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

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

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

3 實(shí) 施

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

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

4 結(jié) 論

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

參考文獻(xiàn)

[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)子載波調(diào)制方式優(yōu)化分配方法[J].光通信技術(shù)，2019，43（2）： 4-17.

[9] 許世納，施展.光傳送網(wǎng)中路由與子載波調(diào)制方式分配聯(lián)合優(yōu)化方法[J].光通信技術(shù)，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].山東大學(xué)學(xué)報(bào)（理學(xué)版），2006，41（4）： 40-43.

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

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