趙志軍　金軍

摘 要：傳統(tǒng)的配網(wǎng)業(yè)務(wù)路由分配方法的鏈條占用率過高，導(dǎo)致丟包率較大。為此，設(shè)計(jì)了基于Q Learning算法的區(qū)域配網(wǎng)業(yè)務(wù)路由分配方法。按照傳統(tǒng)分類方式劃分業(yè)務(wù)路由中的性能指標(biāo)，根據(jù)路由約束條件計(jì)算指標(biāo)的約束值，從而確定業(yè)務(wù)路由的最優(yōu)傳輸路徑。結(jié)合Bellman Equation方法不斷計(jì)算并更新配網(wǎng)中的Q值，再綜合節(jié)點(diǎn)和網(wǎng)絡(luò)業(yè)務(wù)指標(biāo)，利用Q Learning算法計(jì)算得到區(qū)域配網(wǎng)中的風(fēng)險(xiǎn)均衡度。不斷變換VNFs的路由順序?qū)⑵滢D(zhuǎn)換為TSP路由問題，最終得到路由分配矩陣，實(shí)現(xiàn)區(qū)域配網(wǎng)業(yè)務(wù)路由的分配。實(shí)驗(yàn)結(jié)果表明：與傳統(tǒng)分配方法相比，基于Q Learning算法的分配方法的鏈條占用率低，有效減小了業(yè)務(wù)數(shù)據(jù)轉(zhuǎn)發(fā)過程的丟包率。

關(guān)鍵詞：Q Learning算法;業(yè)務(wù)路由;Bellman Equation方法;最優(yōu)傳輸路徑;風(fēng)險(xiǎn)均衡度;路由分配

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

Research on Route Allocation Method of Regional Distribution

Network Service Based on Q Learning Algorithm

ZHAO Zhi-jun1，JIN Jun2

（1.State Grid Jiaxing Electric Power Supply Company， Jiaxing， Zhejiang 314000，China;

2.Jiaxing Hengchuang Electric Power Group Co. Ltd.， Jiaxing， Zhejiang 314000，China）

Abstract： The traditional routing distribution method of distribution network has a high chain occupancy rate， which leads to a high packet loss rate. This study designed a routing distribution method for regional distribution network based on Q Learning algorithm. According to the traditional classification method， the performance index of the service route is divided， and the constraint value of the index is calculated according to the route constraint conditions， so as to determine the optimal transmission path of the service route. The Bellman Equation method is used to calculate and update the Q value in the distribution network， and then the node and network service indexes are integrated to calculate the risk equilibrium degree in the regional distribution network. The routing order of VNFs is constantly changed into TSP routing problem， and finally the routing distribution matrix is obtained to realize the routing distribution of regional distribution network. The experimental results show that compared with the traditional distribution method， the distribution method based on Q Learning algorithm has a low chain occupancy rate and effectively reduces the packet loss rate in the process of forwarding business data.

Key words：Q Learning algorithm; business routing; Bellman Equation method; optimal transmission path; risk balance; routing assignment

隨著智能電網(wǎng)技術(shù)的不斷發(fā)展，電力配網(wǎng)正逐步向數(shù)字化、綜合化、智能化、多業(yè)務(wù)化等方向演進(jìn)[1]。配網(wǎng)承擔(dān)著電力資源調(diào)度分配和信息化管理等業(yè)務(wù)需求，配網(wǎng)的安全可靠直接影響電力系統(tǒng)的安全與穩(wěn)定。

業(yè)務(wù)路由是一種可拓展的互聯(lián)網(wǎng)路由器，可以實(shí)現(xiàn)業(yè)務(wù)數(shù)據(jù)的遷移。在配網(wǎng)運(yùn)行過程中，業(yè)務(wù)路由分配關(guān)系到電力系統(tǒng)的可靠性和配電網(wǎng)運(yùn)行方式的優(yōu)化[2]。因此，配網(wǎng)業(yè)務(wù)路由分配的合理、可靠分配至關(guān)重要。文獻(xiàn)[3]中提出了一種基于頻譜位示圖的聯(lián)合優(yōu)化路由頻譜分配方法，利用預(yù)先計(jì)算控制模型、頻譜位示圖和最佳分配算法構(gòu)建業(yè)務(wù)請求數(shù)據(jù)庫，結(jié)合實(shí)時(shí)計(jì)算結(jié)果，進(jìn)行了路由頻譜分配。文獻(xiàn)[4]中提出了一種電力傳輸網(wǎng)絡(luò)的動態(tài)波道均衡路由分配方法，根據(jù)電力網(wǎng)絡(luò)拓?fù)浣Y(jié)果與業(yè)務(wù)請求狀態(tài)完成業(yè)務(wù)請求合并，對跨域業(yè)務(wù)進(jìn)行路由選擇，根據(jù)位置優(yōu)先級設(shè)定對業(yè)務(wù)請求優(yōu)先級進(jìn)行設(shè)置，結(jié)合分組波長分配算法實(shí)現(xiàn)業(yè)務(wù)路由的分配。然而，這兩種方法路由分配過程的鏈條占用率過高，導(dǎo)致業(yè)務(wù)數(shù)據(jù)轉(zhuǎn)發(fā)過程的丟包率較大，實(shí)用性較差。

Q Learning算法是強(qiáng)化學(xué)習(xí)算法中的一種，其中的Q值是在某一狀態(tài)下采取某種動作能夠獲得收益的期望，同時(shí)Q值會根據(jù)環(huán)境的狀態(tài)反饋相應(yīng)的操作信息。在Q Learning算法中，“狀態(tài)State”與“行為Action”是兩個(gè)重要的單位，需要完成的目標(biāo)為“狀態(tài)”，完成的路徑為“行為”，兩者構(gòu)建成一張Q-table來儲存Q值，依照Q值來選取能夠獲得最大收益的操作[5]。

為此，針對傳統(tǒng)方法的不足，引入Q Learning算法，設(shè)計(jì)一種區(qū)域配網(wǎng)業(yè)務(wù)路由分配方法，以期保護(hù)線路繼電業(yè)務(wù)、保障路由業(yè)務(wù)的服務(wù)質(zhì)量、降低配網(wǎng)風(fēng)險(xiǎn)，為區(qū)域配網(wǎng)業(yè)務(wù)的穩(wěn)定開展提供技術(shù)支持。

1 分配方法設(shè)計(jì)

1.1 業(yè)務(wù)路由最優(yōu)傳輸路徑的確定

在確定業(yè)務(wù)路由最優(yōu)傳輸路徑前，首先需劃分業(yè)務(wù)路由中的性能指標(biāo)。按照傳統(tǒng)的分類方形式對區(qū)域配網(wǎng)中的路由業(yè)務(wù)進(jìn)行劃分[6]，跟劃分結(jié)果將不同的配網(wǎng)運(yùn)行任務(wù)分配給不同業(yè)務(wù)路由，從而產(chǎn)生不同的傳輸性能指標(biāo)。劃分結(jié)果如表1所示。

為保證性能指標(biāo)劃分的準(zhǔn)確性，按照路由約束條件計(jì)算指標(biāo)的約束值。假設(shè)vi和vj為區(qū)域配網(wǎng)中的節(jié)點(diǎn)，eij為網(wǎng)絡(luò)中由節(jié)點(diǎn)vi到vj的鏈路，w（eij）表示鏈路eij的約束條件值。此時(shí)，路由的約束條件值計(jì)算方法如下所示：

w1=∑eij∈Pw（eij）w2=∏eij∈Pw（eij）w3=min eij∈Pw（eij） （1）

式（1）中，w1、w2、w3分別表示的是指標(biāo)的加性、乘性、凹性的約束條件，P表示路徑。對（1）式不斷取值，得到存在約束條件下性能指標(biāo)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，如圖1所示。

圖1中，括號內(nèi)的數(shù)據(jù)分別表示時(shí)延與可靠度，時(shí)延是在[1，9]中隨機(jī)取得的整數(shù)，可靠度是在[0.991，0.999]間隨機(jī)取得的小數(shù)。圓圈內(nèi)的數(shù)字表示配網(wǎng)業(yè)務(wù)路由。按照路由跳數(shù)排序，得到表1中指標(biāo)的具體數(shù)值。在此基礎(chǔ)上，使用圖1的拓?fù)浣Y(jié)構(gòu)來確定一條最優(yōu)路徑，利用Dijkstra算法計(jì)算業(yè)務(wù)權(quán)值，可得到：

ΨP=∑s，d∈Nf（s，d）2W∑s，d∈Nf（s，d）2（2）

式（2）中，ΨP表示業(yè)務(wù)權(quán)值，W表示傳輸流的數(shù)量， s表示傳輸時(shí)的出發(fā)節(jié)點(diǎn)，d為目的節(jié)點(diǎn)，表示數(shù)據(jù)包遞交率，N=1，2，3，…?；诖耍捎?jì)算得到如表2所示的業(yè)務(wù)路由及其度量的參數(shù)值。

使用表2中的各項(xiàng)參數(shù)，結(jié)合多約束路由算法計(jì)算路由約束條件，設(shè)定約束向量H→=[H1，H2，…，Hm]，若Hi是路徑約束值的下限（1≤j≤m，j≠i），則此時(shí)的路徑P對應(yīng)第i（1≤i≤m）種約束條件和路徑約束下限Hj，路徑P滿足以下約束條件[7-8]：

wi（P）≤Hi（1≤i≤m）wj（P）>Hj（1≤j≤m，j≠i）（3）

利用上述約束條件，計(jì)算得到最優(yōu)路徑對應(yīng)表2中的序號為2、3。在得到最優(yōu)路徑后，利用Q? Learning算法計(jì)算路徑所在網(wǎng)絡(luò)的風(fēng)險(xiǎn)均衡度，依照風(fēng)險(xiǎn)度值的大小，調(diào)整業(yè)務(wù)路由中的指標(biāo)，實(shí)現(xiàn)區(qū)域配網(wǎng)業(yè)務(wù)路由的分配。

1.2 利用Q Learning算法計(jì)算網(wǎng)絡(luò)風(fēng)險(xiǎn)均衡度

在利用Q learning算法計(jì)算網(wǎng)絡(luò)風(fēng)險(xiǎn)均衡度時(shí)，首先需計(jì)算Q值。在區(qū)域配網(wǎng)結(jié)構(gòu)下，隨機(jī)選取一條最優(yōu)路徑，將配網(wǎng)結(jié)構(gòu)初始化為0，按照最優(yōu)路徑規(guī)定的節(jié)點(diǎn)，每經(jīng)過一個(gè)節(jié)點(diǎn)（即執(zhí)行一次業(yè)務(wù)），都使用Bellman Equation方法更新一次 Q-table[9]。初始路徑節(jié)點(diǎn)表達(dá)式如下：

Q（K'，β'）=R+γmax Q（K，β）? （4）

其中，K代表當(dāng)前狀態(tài)，β代表當(dāng)前狀態(tài)下的執(zhí)行情況，K'代表行動引起的下一狀態(tài)，β'表示下的執(zhí)行情況，R表示獎勵，γ是算法中的discount因子。更新后的路徑會得到一個(gè)reward矩陣，如式（5）所示：

E=-10-10-1-100-1-10-1-1-10-1-1-100 （5）

將（5）式的初始Q-Table的值全設(shè)置為0，每一行代表一個(gè)風(fēng)險(xiǎn)狀態(tài)，每一列代表每個(gè)狀態(tài)的最優(yōu)路徑，然后將γ設(shè)置為0.8，假設(shè)此時(shí)從節(jié)點(diǎn)1開始傳輸，先將傳輸方向規(guī)定為向下，此時(shí)的節(jié)點(diǎn)傳輸?shù)搅斯?jié)點(diǎn)3，使用Bellman Equation計(jì)算方法更新此時(shí)的Q-Table，更新后得到的reward表為：

E'=-100000000001000000 （6）

重復(fù)上述計(jì)算過程，使更新后的reward值保持不變，直到得到最后的網(wǎng)絡(luò)風(fēng)險(xiǎn)的Q值[10]。綜合Q值、節(jié)點(diǎn)和網(wǎng)絡(luò)業(yè)務(wù)對風(fēng)險(xiǎn)均衡度的影響，計(jì)算風(fēng)險(xiǎn)均衡度，可得到：

RG=∑eij∈GR（eij）-R（e）avg∑vi∈GR（vi）-R（v）avg （7）

其中，RG表示網(wǎng)絡(luò)業(yè)務(wù)風(fēng)險(xiǎn)均衡度，R（eij）與R（e）avg分別表示鏈路eij的業(yè)務(wù)風(fēng)險(xiǎn)值與網(wǎng)絡(luò)所有鏈路均值，RG越小表示網(wǎng)絡(luò)風(fēng)險(xiǎn)越均衡，R（vi）與R（v）avg分別表示配網(wǎng)節(jié)點(diǎn)vi的業(yè)務(wù)風(fēng)險(xiǎn)值與經(jīng)過該節(jié)點(diǎn)的所有鏈路均值[11]。在計(jì)算兩種路徑的的業(yè)務(wù)風(fēng)險(xiǎn)均衡度后，依照風(fēng)險(xiǎn)均衡度，實(shí)現(xiàn)區(qū)域配網(wǎng)業(yè)務(wù)路由的分配。

1.3 區(qū)域配網(wǎng)業(yè)務(wù)路由分配的實(shí)現(xiàn)

首先考慮業(yè)務(wù)雙向通信場景，為避免發(fā)生過長排隊(duì)時(shí)延的情況，假設(shè)在業(yè)務(wù)物流分配時(shí)，分配請求流入、流出的數(shù)據(jù)速率均為v，讓業(yè)務(wù)路由在產(chǎn)生的數(shù)據(jù)速率變化的情況下，滿足相鄰的頻帶的要求，計(jì)算此時(shí)的頻帶需求：

g=min Cv（8）

其中，C代表頻帶數(shù)值，min 函數(shù)將返回兩個(gè)最優(yōu)路徑中的最小值。不同的最小值對應(yīng)著不同的HC-VNFs的路由順序，依照圖2所示的路由示意圖，確定路由分配順序。

由圖2所示，在路由分配時(shí)，需要訪問HC-VNFa， HC-VNFb和HC-VNFc三種分配到不同的Pods節(jié)點(diǎn)上的虛擬架構(gòu)[12]。在靈活的路由順序下，圖中的箭頭路徑分別表明不同的路由，根據(jù)公式（8）可以得出相鄰HC-VNFs分配時(shí)所需的頻帶需求[13]。

使用計(jì)算得到的頻帶，以頻帶開銷最小函數(shù)作為分配目標(biāo)函數(shù)，利用分支限界算法快速搜索頻帶最小路徑，將圖2的路由示意圖轉(zhuǎn)化為TSP路由問題[14-15]，轉(zhuǎn)化后的TSP路由問題如圖3所示。

圖3中圓圈點(diǎn)代表了區(qū)域配網(wǎng)中的各業(yè)務(wù)路由，節(jié)點(diǎn)1為出發(fā)路由，依次無重復(fù)的經(jīng)過2-5個(gè)節(jié)點(diǎn)，實(shí)現(xiàn)最終的路由分配。為避免分配后的路由路徑產(chǎn)生環(huán)路的現(xiàn)象，將路由分配結(jié)果作為輸入變量代入到分支限界算法中，最終由算法返回的路徑，即為實(shí)際的業(yè)務(wù)路由分配方法，最終實(shí)現(xiàn)了區(qū)域配網(wǎng)業(yè)務(wù)路由的分配。

2 仿真實(shí)驗(yàn)與結(jié)果分析

2.1 實(shí)驗(yàn)準(zhǔn)備

為驗(yàn)證基于Q Learning算法的區(qū)域配網(wǎng)業(yè)務(wù)路由分配方法的應(yīng)用性能，利用如下仿真實(shí)驗(yàn)進(jìn)行驗(yàn)證。仿真實(shí)驗(yàn)參數(shù)設(shè)置情況如表3所示。

實(shí)驗(yàn)指標(biāo)分別為配網(wǎng)業(yè)務(wù)數(shù)據(jù)轉(zhuǎn)發(fā)過程的鏈路占用率和平均丟包率。

為突出實(shí)驗(yàn)結(jié)果的對比性，將基于Q Learning算法的區(qū)域配網(wǎng)業(yè)務(wù)路由分配方法作為實(shí)驗(yàn)組，將文獻(xiàn)[3]中的基于頻譜位示圖的聯(lián)合優(yōu)化路由頻譜分配方法和文獻(xiàn)[4]中的電力傳輸網(wǎng)絡(luò)的動態(tài)波道均衡路由分配方法作為對比組，共同完成性能對比實(shí)驗(yàn)。

2.2 實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)及分析

將Q值設(shè)置為1，改變網(wǎng)絡(luò)中傳輸流的數(shù)量，觀察在傳輸流數(shù)量逐漸增加的情況下，三種分配方法的鏈路占用率，統(tǒng)計(jì)結(jié)果如圖4所示。

由圖4可知，三種分配方法的最大鏈路占用率會隨著網(wǎng)絡(luò)中的傳輸流數(shù)的增加而逐漸加加。這是因?yàn)榫W(wǎng)絡(luò)中的傳輸流數(shù)量越多，每條鏈路被占用的可能性越高，鏈路的最大占用率也就增大。由圖4實(shí)驗(yàn)結(jié)果圖可知，三種分配方法最大鏈路占用率相差很大，文獻(xiàn)[3]方法的鏈路平均最大占用率為0.45左右，文獻(xiàn)[4]方法的鏈路平均最大占用率為0.4左右，而本方法的鏈路最大占用率在0.35以下。由此可以證明，基于Q Learning算法的區(qū)域配網(wǎng)業(yè)務(wù)路由分配方法具有較低的鏈條占用率。

在此基礎(chǔ)上，保持與上述實(shí)驗(yàn)相同的傳輸流數(shù)量變化情況，比較三種分配方法下的信道丟包率，實(shí)驗(yàn)結(jié)果如表4所示。

從表5可以看出，隨著傳輸流數(shù)量的增加，三種分配方法在網(wǎng)絡(luò)中的平均丟包率也在逐漸變大。這是因?yàn)閭鬏斄髟黾訉?dǎo)致的網(wǎng)絡(luò)中鏈路之間干擾嚴(yán)重，使傳輸流丟包愈加嚴(yán)重。由表4實(shí)驗(yàn)結(jié)果圖可知，文獻(xiàn)[3]方法的最大丟包率為4.1%，文獻(xiàn)[4]方法的最大丟包率為3.6%，而本文方法的最大丟包率為2.4%。相比之下，本文方法的最大丟包率更小。

綜上所述：與兩種傳統(tǒng)分配方法相比，本文方法下的鏈路占用率小，配網(wǎng)業(yè)務(wù)數(shù)據(jù)轉(zhuǎn)發(fā)過程的信道丟包率也較小，可以在少占用配網(wǎng)中的鏈路情況下，減少網(wǎng)絡(luò)鏈路之間的干擾和傳輸流的丟包情況，有效實(shí)現(xiàn)區(qū)域配網(wǎng)中業(yè)務(wù)路由的分配。

3 結(jié) 論

在配網(wǎng)規(guī)模日益擴(kuò)大的同時(shí)，電力信息化的程度也日益加深，電網(wǎng)與電力通信之間的聯(lián)系越來越密切。研究基于Q Learning算法的區(qū)域配網(wǎng)業(yè)務(wù)路由分配方法，可以增提高配的工作效率，合理化分配業(yè)務(wù)路由、減少鏈路占用率，能夠有效避免在配網(wǎng)資源傳輸中出現(xiàn)丟包率過高的現(xiàn)象。因此，本研究提出的分配方法對研究區(qū)域配網(wǎng)業(yè)務(wù)路由分配問題有著進(jìn)步性的意義。

參考文獻(xiàn)

[1] 劉鈺，熊蘭，肖丹，等.基于業(yè)務(wù)重要度的電力通信路由系統(tǒng)可靠性分析[J].電測與儀表，2017，54（12）：34-41.

[2] 張樂平，金鑫，胡珊珊，等.基于動態(tài)Skyline計(jì)算的智能電網(wǎng)分布式路由算法[J].科技通報(bào)，2018，34（8）：135-139.

[3] 張曙光，李正賢，王偉.基于頻譜位示圖的聯(lián)合優(yōu)化路由頻譜分配算法[J].激光與光電子學(xué)進(jìn)展，2019，56（13）：48-52.

[4] 孫毅，周爽，陸俊，等.電力骨干光傳輸網(wǎng)絡(luò)的動態(tài)波道均衡路由波長分配算法[J].電力系統(tǒng)自動化，2016，40（13）：114-120.

[5] 薛俏，丁慧霞，張庚，等.基于Q Learning算法的電力通信業(yè)務(wù)路由規(guī)劃[J].光學(xué)與光電技術(shù)，2019，17（4）：51-56.

[6] 艾欣，譚騫，呂志鵬，等.VSG結(jié)合無源型能量路由器及其在微網(wǎng)中的應(yīng)用[J].華北電力大學(xué)學(xué)報(bào)（自然科學(xué)版），2018，45（3）：1-9.

[7] 王曉雷，陳云杰，王琛，等.基于Q-learning的虛擬網(wǎng)絡(luò)功能調(diào)度方法[J].計(jì)算機(jī)工程，2019，45（2）：64-69.

[8] 秦峰，曾浩，林開東.流量自適應(yīng)分配的多匯聚節(jié)點(diǎn)LLN路由協(xié)議[J].計(jì)算機(jī)工程與設(shè)計(jì)，2019，40（8）：2128-2133.

[9] 姚玉坤，劉江兵，李小勇，等.LLN中基于環(huán)路避免的高效路由修復(fù)算法[J].系統(tǒng)工程與電子技術(shù)，2018，40（5）：1135-1141.

[10]涂山山，于金亮，孟遠(yuǎn)，等.面向5G霧計(jì)算中基于Q-learning的安全中繼節(jié)點(diǎn)選擇方法[J].電信科學(xué)，2019，35（7）：60-68.

[11]耿海軍，尹霞.一種基于iSPF的下游路徑規(guī)則實(shí)現(xiàn)方法[J].計(jì)算機(jī)工程，2019，45（6）：103-107.

[12]孫方楠，梁后健，張課，等.基于改進(jìn)遺傳算法的電力通信網(wǎng)路由優(yōu)化研究[J].自動化與儀器儀表，2018（6）：25-28.

[13]萬謙，劉瑋，徐龍龍，等.基于Q-learning的不確定環(huán)境BDI Agent最優(yōu)策略規(guī)劃研究[J].計(jì)算機(jī)工程與科學(xué)，2019，41（1）：166-172.

[14]孫嚴(yán)智，劉旋，劉宇明，等.遺傳算法電力通信網(wǎng)關(guān)鍵業(yè)務(wù)備選路由配置[J].云南電力技術(shù)，2017，45（1）：113-117.

[15]王鵬輝，張寧，肖明明.基于節(jié)點(diǎn)重要度的路由選擇與頻譜分配算法[J].計(jì)算機(jī)工程與應(yīng)用，2019，55（13）：106-111.