[發明專利]一種基于深度強化學習的時間敏感網絡通信流調度方法

有效

• 申請號: 202110257321.X
• 申請日: 2021-03-09
• 公開（公告）號: CN113285872B
• 公開（公告）日: 2022-09-23
• 發明（設計）人: 萬海;鐘春蒙;趙曦濱
• 申請（專利權）人: 清華大學
• 主分類號: H04L45/12
• 分類號: H04L45/12;H04L45/28;H04L45/00;H04L47/125;G06N3/04;G06N3/08
• 代理公司: 北京鴻元知識產權代理有限公司 11327
• 代理人: 陳英俊

1.一種基于深度強化學習的時間敏感網絡通信流調度方法，其特征在于，包括以下步驟：

步驟一：建立基于強化學習的神經網絡，在神經網絡中，定義x作為輸入x∈X^D，x是從真實分布中采樣得到的，使用f來表達一個激活函數，θ是神經網絡中可以訓練更新的參數集合，b是一個偏差項，還可以給f加上一個上標l表示神經網絡的某一層，然后用y來表示這一層的輸出，這樣，神經網絡第l層的輸出可以表示為y^l＝f^l(θx+b).，強化學習RL包含了主體和環境的交互，在t時間點，主體根據當前的狀態wt選擇合適的動作at，然后環境給出這個動作的獎勵值at并計算出下一個狀態wt+1，下一個狀態wt+1會返回給主體，這個過程可以形式化的表達為一個五元組，＜W，A，P，R，γ＞，其中w_t∈W，a_t∈A是t時間點的狀態和動作，R是獎勵值的分布情況，給定一個(狀態，動作)對(w_t，a_t)，r_t～R(·|ω_t，a_t)，獎勵值就可以被計算出來，用P表示狀態轉移可能性矩陣，w_t+1～P(·|ω_t，a_t)，用r表示一個衰減參數，這個參數的值一般接近1，策略pi，π：W→A指定了在狀態wt下選擇的動作，強化學習的目標就只要找到一個最優策略pi*，從而最大化累計衰減獎勵∑_t≥0γ^tr_t；

步驟二：系統建模，網絡拓撲被建模為一個有向圖，其中V表示節點的集合，每一個節點都是網絡中的一個交換機，E是鏈路的集合，每一個鏈路包含兩個節點，如果兩個節點vm和vn之間有一條物理鏈路，那么(v_m，v_n)，(v_n，v_m)∈E，一個節點對中的前一個節點代表鏈路的源節點，后一個節點代表鏈路的目標節點，所有的節點都可以作為TS流的源節點和目標節點，并且可以轉發報文，且TS通信需要使用流的概念來建模，一條流是一個周期性的單播消息，只有一個源節點和一個目標節點，使用S來表示所有TS流的集合，一個TS流s_k∈S使用一個五元組(X_k，Y_k，C_k，T_k，L_k)來表示，其中Xk和Yk表示TS流的源節點和目標節點，Ck，Tk，Lk分別表示以字節為單位的報文大小，以毫秒為單位的TS流周期和最大端到端時延，由于不同的TS流具有不同的周期，弘周期大于或者等于所有流的周期，弘周期使用Ts來表示，通過計算所有流周期的最小公倍數得到，將一條TS流從源節點到目標節點的路由表示為一個鏈路的集合{e₀，e₁，...，e_n}，其中鏈路e0的源節點是Xk，en的目標節點是Yk，而且ei和ei+1是相鄰的兩條鏈路，如果使用ei.src和ei.dst分別表示一條邊的源節點和目標節點的話，那么會得到如下約束：將一條TS流s_k∈S流經e_i∈E的第1個消息實例表示為其中是流sk流經ei的所有幀的集合，為了調度TS流，需要指定通過ei的時間，為了簡化問題，將一毫秒劃分為a個時隙，時隙用t表示，每一個時隙包含相等長度的時間，在一個弘周期內，一共包含了T_s×α個時隙，選擇其中一個時隙通過ei，將鏈路ei的第j個時隙tj的狀態表示為其中是ei的所有時隙的狀態，是一個整型數，表示使用時隙tj通過ei的幀的數量，一個時隙最多只能被一個幀占用，因此有如下約束：

將所有TS流的周期設定為2的倍數：T_k∈{4，8，16，32，64，128，256，512，1024，2048}系統模型有兩個基礎假設，首先是所有網絡節點都有分布式時間同步能力，其次所有設備都有實時轉發報文的能力，在靜態調度環境中，在調度開始時就能夠知道所有的TS流需求，并且這些需求不會變化，DRLS需要解決的動態調度問題中，TS流需求是會隨著時間變化的，DRLS逐一為這些TS流生成調度，新的流的調度計劃不能和已有流的調度計劃沖突；

步驟三：系統框架，DRLS可以被大致分為三個部分，狀態部分抓取TS流的當前信息以及網絡拓撲的整體信息，主體是一個決策者決定采取何種動作，而環境在一個動作被選取出來之后負責維護環境中的各種資源并且給出當前動作的獎勵，當調度開始時，狀態部分根據網絡資源信息和TS流信息計算出當前狀態w_t∈W，主體部分使用一個深度神經網絡得到路由決策，使用LD方法得到時隙決策，這兩部分共同構成了當前動作決策at，環境部分為主體部分根據調度目標計算出當前動作的獎勵值rt，并且在實施動作at維護網絡資源狀態后計算出下一個狀態wt+1，這個獎勵值和調度的時延和完成狀態有關，獎勵值用來持續的提高DNN的決策能力，并通過編碼神經網絡和策略神經網絡來實現DRLS的主體部分，編碼網絡提取網絡的全局信息以及每一條鏈路的編碼向量，策略網絡用來獲得動作決策；

步驟四：時隙選擇，選擇一個合適的時隙tj能夠讓邊ei承載更多的TS流，周期小的TS流比周期大的TS流占用更多的時隙，所有這些時隙必須是空閑的，如果一個時隙tj只能承載周期大的流，用一個函數G(e_i，t_j，T_k)表示一條邊ei的一個時隙tj是否可以承載一條周期為Tk的流，那么就有其中T_k∈T是一條TS流sk的周期，而Ts是所有流的弘周期，接下來就可以定義一個時隙的度ρ(e_i，t_j)：高度時隙無論大周期流還是小周期流都可以承載，而低度時隙只能承載大周期流，LD方法傾向于在可用的時隙中選擇一個度比較低的，這樣可以讓整個TSN網絡承載更多的流，時隙t2，t5，t6，t12，t14是已經被占用的，其他時隙是空閑的，時隙t3可以承載一個周期為4的TS流，因為這條流所需的全部時隙，t3，t7，t11，t15都是可用的，時隙t0不能承載這條流因為時隙t12是不可用的，如果用時隙t3來承載一個周期為8的流，那么網絡里面就沒有任何一個時隙可以承載一個周期為4的流，因此，LD時隙選擇方法就會傾向于選擇時隙t0來承載一個周期為8的TS流而非t3，使得端到端時延最短也是調度方法的重要目標，選擇一個早一點的時隙能夠降低時延，因此LD時隙選擇方法會在可用的低度時隙中選擇一個最早的；

步驟五：狀態建模，wt是主體選擇動作at是所需的全部信息，使用一個由實數組成的向量來實現wt，這個向量表示一條邊的信息，wt由以下六個部分組成：1)當前這條邊到目標節點Yk的距離，距離為0則表示這個報文已經到達了目標節點Yk，一般來說，邊與目標節點的距離越近越好，當前這條邊是不是上一個動作選擇的邊的鄰邊，或者是源節點所在的邊，TS流的報文，當前要么存儲在上一個動作選出的邊的目標節點中，要么存儲在源節點Xk中，因此，當前動作選出的邊一定要是上一個動作選出的邊的鄰邊，當前這條邊是否會和之前已經選中的邊構成環路，TS流的路由需要避免環路的出現，因為環路會浪費網絡資源并且導致時延變大，當前這條邊的擁擠程度，擁擠程度表示為空閑時隙數量與總時隙數量的比值，一般來說，選擇一個不那么擁擠的邊可以保證整個網絡的負載均衡，并且避免瓶頸鏈路的產生，當前這條邊是否含有至少一個可用的時隙，如果一條邊沒有可以承載當前TS流的時隙，那么這條邊就是不能被選中的，當前邊的所有可用時隙的度的最小值，度的定義如前所述，這是幫助DNN選擇合適邊的重要信息，除了wt，也會計算一個|E|×|E|×D矩陣M，這里的|E|表示邊的數量，而D表示任意兩條邊之間的最大距離，兩個邊的距離定義為它倆之間的最短路由包含的網絡節點數量，用Mijd表示M的(i，j，d)位置的元素，那么M的計算方式可以表達為：M_i，j，d＝1意味著如果邊ei和ej之間有一條包含d個節點的路由，wt在每一次做動作決策之前都會被重新計算，而M只會為一個網絡拓撲計算一次，Wt表示每一條單獨的鏈路的信息而M包含的是拓撲的全局信息，這些信息足夠主體租出正確的動作決策，同時也解決了前文提到的網絡狀態表達挑戰；

步驟六：動作建模，使用DRL解決調度問題時，由于可選路由的數量巨大，同時每一幀的發送時間也有太多的選擇，DRL的動作空間會非常大，DRLS通過將路由分解為連續的邊的組合來降低動作空間的大小，每一個動作只包含一個邊而不是整個路由，也就是說，一條流的調度計劃{(e₀，t₀)，(e₁，t₁)，...，(e_n，t_n)}被分成了多個動作，分解動作使得DRLS有良好的可擴展性，同時也解決了動態調度挑戰，一個動作是一個有邊ei和時隙tj組成的元組(e_i，t_j)；

步驟七：環境建模，當主體計算出動作A之后，環境部分就會計算出一個獎勵值R，獎勵值R用于更新DRLS的神經網絡的參數theta，Hk用來表示一個TS流sk是否被成功的調度了，成功的調度意味著調度方法找到了一個從Xk到Yk的合法路由以及相應的時隙，同時這個調度計劃的端到端時延是小于最大端到端時延Lk的，定義一個鏈路使用率Us，計算方法是所有邊被占用的時隙數量除以所有邊的總時隙數量，網絡整體的鏈路使用率U_s和單獨一條鏈路的使用率Uk定義如下：需要說明的是無論是整體鏈路使用率還是單獨一條鏈路的使用率都是在不斷變化的，這里定義的Us和Uk是在每一條流調度結束時計算的，鏈路使用率反應的是鏈路的擁擠程度，如果一條鏈路的使用率程度大于網絡整體的使用率，那么這一條鏈路就有可能成為瓶頸鏈路，綜合以上所有的因素，如果一個TS流的調度計劃是{(e₀，t₀)，(e₁，t₁)，...，(e_n，t_n)}，那么對于產生這個調度計劃的每一個動作，其獎勵

可以定義為：只有當一條流調度結束的時候才能判斷這條流是否調度成功了，所以，只有最后一個動作的獎勵值能夠按照等式11的方式來計算，而其他動作的獎勵值是m經過衰減后的值，從直覺上來講，越早的動作對于調度成功與否的影響越小；

步驟八：深度神經網絡，使用所有的邊作為輸入，然后輸出選擇沒一條邊的可能性，每一個動作(e_i，t_j)中的邊ei都是從DNN的輸出中獲取的，這個DNN有兩個部分，分別是編碼神經網絡和策略神經網絡，編碼網絡使用邊信息W和全局信息M構建一個編碼向量Vb，其中Ψ是編碼網絡，是用一個小的全連接網絡實現的，Md是一個|E|*|E|的矩陣表示距離為d的可達性信息，策略網絡X使用V^D_b作為輸入并且輸出選擇每一條邊的可能性Vp，在0～1范圍之間，擁有最高可能性的邊會被選中，結合選擇某一個動作的獎勵值R和DNN的參數theta，神經網絡的損失函數定義如下：Loss_θ＝-logχ_θ×R (15)，下面的公式用來更新神經網絡的參數θ，R表示的是更新的步長，而表示損失函數的梯度：

步驟九：實現，DNN的可靠性和穩定性很低，為了讓DRLS稱為一個可以信賴的調度方法，提出了控制門策略來篩除不合適的邊，一共有三種邊會被認為是不合適的：1)非鄰邊，如前所述，被選中的邊必須是上一個動作選擇的邊的鄰邊，2)構成環路的邊，環路會浪費網絡資源并且導致時延增大，3)沒有任何時隙可以調度當前TS流的邊，DNN會輸出選擇一條邊的概率，然后控制門會屏蔽掉所有不合適的邊，最后，主體會在所有的合適的邊里面選擇一個概率最大的，如前所示，其實和控制門相關的信息已經傳遞給DNN了，然而，由于訓練數據與測試數據的偏差，同時也會有訓練數據質量的問題，神經網絡有可能會忽略掉這些重要的信息，通過使用控制門技術，由于訓練不足導致的錯誤會被避免，而神經網絡的可導性和穩定性會得到提升；

步驟十：錯誤恢復，網絡節點和鏈路都有可能會宕機，這會導致網絡拓撲或者網絡資源的變化，最終影響到正在網絡中傳輸的TS流，一個鏈路故障會影響流經這條鏈路的所有TS流，而一個節點故障會導致所有以這個節點會源點或者終點邊都發生故障并且影響所有流經這個節點的TS流，故障的鏈路或者節點不能在被同來承載TS流，并且所有受影響的流都要被重新調度，錯誤恢復通過以下四個步驟完成，首先是記錄所有受影響的TS流的全部信息，也就是(X_k，Y_k，C_k，T_k，L_k)，在網絡恢復之后，這些流都需要被重新調度，然后釋放被這些受影響的流占用的網絡資源，例如時隙，第三步是重新計算網絡拓撲的全局信息M，因為這個時候網絡拓撲已經發生變化了，第四步是使用重新計算的全局信息M調度這些受影響的流；

步驟十一：實驗論證，在3種不同類型的網絡拓撲上驗證DRLS的性能，分別是用在空中客車A380飛機上的航空電子全雙工交換式以太網網絡拓撲，用在列車通訊中的梯形網絡拓撲和隨機生成的網絡拓撲，如前所述，一條TS流由一個五元組確定(X_k，Y_k，C_k，T_k，L_k)，用于訓練的流和用于測試的流都是不同的，但是都是隨機生成的，Xk和Yk是在所有的網絡節點中隨機選的，Ck是一個介于64-1518之間的隨機整數，為了簡便，假定所有物理鏈路的傳輸速度都是1Gbit/s并且將1個毫秒劃分為4個時隙，這樣的話，即使是最大報文也可以在1個時隙內傳輸通過一個邊，也就是說，任何幀都恰好占用一個時隙，TS流的周期Tk是在[16，32，64，128，256，512，1024，2048]范圍內隨機選取的，最大端到端時延Lk是一個介于64到256之間的隨機整數，為三種拓撲，AFDX拓撲，梯形拓撲和隨機拓撲分別訓練了一個模型，每個模型都使用對應的網絡拓撲和隨機生成的TS流需求進行訓練，測試時使用的網絡拓撲與訓練時相同，但是使用的TS流是不同的。