基于Q Learning算法的區(qū)域配網業(yè)務路由分配方法研究

趙志軍　金軍

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

關鍵詞：Q Learning算法;業(yè)務路由;Bellman Equation方法;最優(yōu)傳輸路徑;風險均衡度;路由分配

中圖分類號：TN915????? 文獻標識碼：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

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

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

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

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

1 分配方法設計

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

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

為保證性能指標劃分的準確性，按照路由約束條件計算指標的約束值。假設vi和vj為區(qū)域配網中的節(jié)點，eij為網絡中由節(jié)點vi到vj的鏈路，w（eij）表示鏈路eij的約束條件值。此時，路由的約束條件值計算方法如下所示：

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

式（1）中，w1、w2、w3分別表示的是指標的加性、乘性、凹性的約束條件，P表示路徑。對（1）式不斷取值，得到存在約束條件下性能指標的網絡拓撲結構，如圖1所示。

圖1中，括號內的數據分別表示時延與可靠度，時延是在[1，9]中隨機取得的整數，可靠度是在[0.991，0.999]間隨機取得的小數。圓圈內的數字表示配網業(yè)務路由。按照路由跳數排序，得到表1中指標的具體數值。在此基礎上，使用圖1的拓撲結構來確定一條最優(yōu)路徑，利用Dijkstra算法計算業(yè)務權值，可得到：

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

式（2）中，ΨP表示業(yè)務權值，W表示傳輸流的數量， s表示傳輸時的出發(fā)節(jié)點，d為目的節(jié)點，表示數據包遞交率，N=1，2，3，…。基于此，可計算得到如表2所示的業(yè)務路由及其度量的參數值。

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

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

利用上述約束條件，計算得到最優(yōu)路徑對應表2中的序號為2、3。在得到最優(yōu)路徑后，利用Q? Learning算法計算路徑所在網絡的風險均衡度，依照風險度值的大小，調整業(yè)務路由中的指標，實現區(qū)域配網業(yè)務路由的分配。

1.2 利用Q Learning算法計算網絡風險均衡度

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

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

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

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

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

E'=-100000000001000000 （6）

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

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

其中，RG表示網絡業(yè)務風險均衡度，R（eij）與R（e）avg分別表示鏈路eij的業(yè)務風險值與網絡所有鏈路均值，RG越小表示網絡風險越均衡，R（vi）與R（v）avg分別表示配網節(jié)點vi的業(yè)務風險值與經過該節(jié)點的所有鏈路均值[11]。在計算兩種路徑的的業(yè)務風險均衡度后，依照風險均衡度，實現區(qū)域配網業(yè)務路由的分配。

1.3 區(qū)域配網業(yè)務路由分配的實現

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

g=min Cv（8）

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

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

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

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

2 仿真實驗與結果分析

2.1 實驗準備

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

實驗指標分別為配網業(yè)務數據轉發(fā)過程的鏈路占用率和平均丟包率。

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

2.2 實驗結果統計及分析

將Q值設置為1，改變網絡中傳輸流的數量，觀察在傳輸流數量逐漸增加的情況下，三種分配方法的鏈路占用率，統計結果如圖4所示。

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

在此基礎上，保持與上述實驗相同的傳輸流數量變化情況，比較三種分配方法下的信道丟包率，實驗結果如表4所示。

從表5可以看出，隨著傳輸流數量的增加，三種分配方法在網絡中的平均丟包率也在逐漸變大。這是因為傳輸流增加導致的網絡中鏈路之間干擾嚴重，使傳輸流丟包愈加嚴重。由表4實驗結果圖可知，文獻[3]方法的最大丟包率為4.1%，文獻[4]方法的最大丟包率為3.6%，而本文方法的最大丟包率為2.4%。相比之下，本文方法的最大丟包率更小。

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

3 結 論

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

參考文獻

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

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

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

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

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

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

[7] 王曉雷，陳云杰，王琛，等.基于Q-learning的虛擬網絡功能調度方法[J].計算機工程，2019，45（2）：64-69.

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

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

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

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

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

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

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

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