軟件定義物聯網中基于深度強化學習的路由優化算法

王健，朱曉娟

（安徽理工大學 計算機科學與工程學院，安徽 淮南 232001）

0 引 言

近年來，物聯網（Internet of Things, IoT）被廣泛應用于環境監測、工業控制和國防軍事等領域，并逐漸成為全球科技戰略發展的焦點之一。隨著物聯網的快速發展，高速、海量數據通信向服務質量保障機制提出了挑戰。于是，有學者提出了軟件定義網絡（software def ined network, SDN），用以優化通信網絡。SDN是將控制平面和數據平面分離的框架，以便動態管理和控制大量網絡設備、拓撲、路由、QoS和數據包處理策略。SDN控制器通過在控制器內運行不同的模塊來執行各種任務，從而提供面向應用程序的服務。

強化學習作為可以優化網絡決策的一種方案也被應用到物聯網環境中。在一定的環境狀態中，智能體與環境交互，根據動作來獲得獎勵，并根據獎勵情況確定下一步的動作，循環往復，不斷提高自己的決策能力。Lillicrap等人提出的深度確定性策略梯度算法（Deep Deterministic Policy Gradient,DDPG）基于Actor-Critic框架解決連續狀態空間下的問題。DDPG使用深度Q網絡逼近Q表，使用策略網絡直接產生確定的動作，解決了DQN面對連續動作時無法處理的問題。

文獻[3-6]提出了基于SDN特性的路由解決方案，如可編程性、全局視圖、網絡傳輸和控制的解耦，以及邏輯集中控制。但是這些解決方案沒有使用強化學習的算法，在網絡狀態變化時容易導致擁塞。

Muhammad Adil等人提出一種高效的混合路由方案（DCBSRP），利用自組織按需距離矢量（AODV）路由協議和低能耗自適應集群層次結構（LEACH）協議，在規定的時間間隔內動態形成簇頭節點。選擇能量高的節點充當簇頭節點，平衡節點之間的負載。仿真結果表明，該方案不僅提高了網絡的壽命，而且在吞吐量、丟包率和能效方面都優于其他方案。

文獻[8-10]基于傳統強化學習的思想解決路由優化問題。CHANGHE Y U等人使用深度強化學習（deep reinforcement learning, DRL）中的DDPG對路由進行優化。仿真實驗表明，該算法實現了對網絡全局的智能控制和管理，具有良好的收斂性。針對DDPG訓練過程會消耗較多網絡資源這一情況，周浩等人提出了“線下訓練、線上運行”的方法，但他們在設計該方法時并沒有將復雜的網絡環境考慮在內。

將SDN路由優化看成一個決策問題，運用強化學習來優化路由。將當前的網絡環境視為強化學習中的初始狀態，通過改變網絡參數，將當前網絡狀態下的網絡信息作為輸入，獎勵值采用延遲、吞吐量等指標，最后通過訓練得到路由模型。當網絡中有新流到達時，智能體可以快速計算出性能最優的路由路徑。

本文在SDN架構下，針對無線傳感器網絡環境流量信息復雜，容易致使路徑發生擁塞的問題，采用RDIS算法使計算出的源節點與目標節點之間的路由路徑在全局下性能接近最優，從而實現提高網絡性能的目的。根據SDN控制器提供的全局路由視圖，RDIS通過DRL代理與環境交互學習路由策略，該算法可以根據動作和獲得的獎勵找到性能接近最優的路由路徑。

1 深度強化學習

1.1 DDPG算法

DDPG可以基于確定性策略梯度算法（Deterministic Policy Gradient, DPG）完成具有連續狀態空間和動作空間的任務。在每一輪的訓練過程中，DDPG將獲得的狀態轉換信息(sras)作為經驗存儲在一個經驗回放池中。DDPG使用深度神經網絡去逼近策略函數，直接輸出一個確定的動作。DDPG由一個actor模塊和一個critic模塊組成，每個模塊擁有兩個網絡，分別是actor模塊中的策略網絡（（s|θ））和目標策略網絡（′（s|θ））以及critic模塊中的網絡（（，）|θ）和目標網絡（′（，）|θ）。在神經網絡訓練的過程中，DDPG在經驗回放池中對樣本進行隨機抽樣訓練，所抽取的樣本用來更新每個模塊中的神經網絡參數，最后得到網絡模型。

DDPG的參數更新過程主要分為兩個階段。actor模塊根據輸入的狀態輸出動作，critic模塊將actor模塊輸出的動作和當前狀態輸入，最終輸出值。兩個模塊進行參數的更新。式（1）表示策略更新的方法：

在critic模塊中，通過TD-error對神經網絡參數進行反向更新，如式（2）所示：

y是目標網絡針對網絡環境狀態所采取的下一步動作的值。該值的動作來源于actor模塊中的目標網絡。目標網絡根據在線網絡傳送過來的參數信息′和下一步狀態所采取的動作a進行更新。y的具體更新過程如式（3）所示：

在網絡中，將值進行參數化，可以針對現有狀態做出準確的評估，選取最合適的動作持續運行。

在DDPG中，智能體從經驗池中對樣本“隨機采樣”，由于不同數據的重要性不同，這種方法容易導致學習效率低。本文基于優先經驗回放，根據經驗重要性，希望價值越高的經驗被采樣到的概率越大，從而提高學習效率。通過概率方式抽取經驗，每個經驗的優先值表達式如式（4）所示：

但是這種采樣方法引入了偏差，因為它改變了數據的分布，進而改變了期望值。因此，通過加上重要性采樣來修改權重，如式（5）所示：

其中，表示抽樣的批次大小，表示一個介于0和1之間的參數。在采樣時，使用重要性采樣參數來調整權重，根據樣本優先級對樣本采樣。

1.2 路由算法RDIS

本文所提出的路由算法RDIS(Routing optimization algorithm based on deep reinforcement learning in software def ined Internet of things, RDIS)，是在SDN下將DDPG應用到路由問題中實現的。相較于傳統的WSN，RDIS具有可編程性、靈活性和集中式管理等優點。本文的模型以SDNWISE架構為基礎，如圖1所示。

圖1 DDPG路由模型

最底下為數據平面， 由傳感器節點等硬件設備組成。數據平面的主要功能是在傳感器節點之間執行數據的轉發。

控制平面擁有一個邏輯集中的控制器，確保用戶平面和數據平面之間的通信。控制平面內包含四個模塊，分別為網絡鏈路模塊、拓撲發現模塊、生成流表模塊和智能模塊。

網絡鏈路模塊的作用是發現和維護整個網絡拓撲的鏈路信息。網絡鏈路模塊將每個傳感器節點的相關信息上傳到控制器，存儲到控制器中為接下來的模塊做準備。在SDN-WISE架構下，使用report數據包獲取所需的鏈路信息，包括延遲、吞吐量等信息。拓撲發現模塊使用從網絡鏈路模塊獲取的節點信息生成和維持網絡拓撲。生成流表模塊根據智能模塊計算好的路徑，將流表下發到數據平面，規劃路由路徑。

智能模塊學習網絡的行為，并利用RDIS代理計算路徑。它與控制平面交互，檢索鏈路狀態信息并下發計算好的流表。該模塊還包含拓撲信息收集模塊、RDIS代理和動作翻譯模塊。拓撲信息收集模塊用于存放從控制平面收集的網絡狀態信息。動作翻譯模塊將RDIS代理中的動作翻譯成一組適當的sensor-openflow消息，從而更新流表。

用戶平面是SDN的最高級別層，在該平面中實現了面向應用程序服務的概念。網絡狀態信息（例如路由信息）通過數據平面收集并被各種網絡應用程序使用。

在RDIS中，將PER與DDPG相結合，以提高價值高的經驗被成功采樣的概率。PER處理過程為：

算法1：PER采樣過程。

（1）初始化經驗回放池。

（2）根據權重θ和θ初始化critic網絡（(，)|θ）和actor網絡（（s|θ））。

（3）根據權重θ←θ和θ ′←θ初始化目標critic網絡(′(，)|θ)和目標actor網絡（′（s|θ）。

（4）初始化狀態（），設置批次大小。

（5）將（s，r，a，s）存儲至經驗回放池，設置最大優先級。

（6）For j=1 to T do:

（7）根據優先級進行樣本轉換：（s，r，a，s）。

（8）計算相應的重要性采樣權重W和TD誤差δ。

（9）根據|δ|的值更新樣本優先級。

（10）End for。

為了將DDPG應用到路由問題中，對算法的獎勵函數、動作空間和狀態空間進行設計。下面介紹RDIS算法的獎勵函數、狀態空間和動作空間：

（1）獎勵函數。獎勵是智能體做出動作后獲得的反饋，它可以是正面的，也可以是負面的。獎勵在RDIS中非常重要，因為下一個動作將根據獎勵的值來確定。獎勵函數的定義如式（6）所示，它與吞吐量成正比，與鏈路延遲成反比。值和∈[0，1]是可調的參數，可根據需要自動調整權重。

為了防止在學習過程中存在某一個狀態指標比其他指標影響更大的情況，對方程（6）使用Min-Max技術進行歸一化處理。它可以將參數范圍縮放到任意值區間。式（7）表示獎勵函數的歸一化結果，其中和分別為吞吐量和鏈路延遲的歸一化值。

每個歸一化值（和）均由方程（8）得到。在這個方程中，′表示需要歸一化的值，表示歸一化中使用的值集。

（2）狀態空間。控制器擁有網絡拓撲的全局視圖，通過控制器可以獲得所需的狀態空間信息。狀態空間中的每個狀態為在選擇下一跳節點后收集到的節點和鏈路狀態信息。對于傳感器節點v，∈{1，2，3，…，}，控制平面從數據平面收集帶寬、時延、丟包率loss和吞吐量等信息。總體來說，狀態空間可以表示為：

其中，∈{1，2，3，…，}，s表示所有狀態中的任意一個狀態，在每一個狀態中，收集鏈路中的信息。

（3）動作空間。動作空間表示對所有狀態采取動作的合集。可由以下公式表示：

a代表在節點采取的動作，并且a={

a|j∈{1，2，3，…，}，≠}。a表示節點和節點之間的連接關系。若a=0，表示兩個節點之間不連通，a∈（0，1]表示從節點選擇下一跳節點為節點的權重。

使用上述狀態空間、動作空間和獎勵函數進行路由優化并使獎勵最大化。以下是RDIS的訓練過程：

算法2：RDIS訓練過程

輸入：網絡狀態數據包括邊總數、頂點數、獎勵函數、學習率等

輸出：路由路徑。

（1）初始化控制器。

（2）控制器發現鄰居節點，收集傳感器節點信息。

（3）建立網絡拓撲圖。

（4）For episode = 1 to M do。

（5） For t = 1 to T do。

（6） 根據重要性采樣從經驗回放池中采集樣本（s，r，a，s）。

（8） 最小化損失更新critic網絡：

（9） 通過采樣更新actor策略：

（10） 目標網絡更新：

（11） End for

（12）End for

2 實驗與性能評估

在實驗中，使用Pytorch作為后端實現RDIS算法，Python版本為3.8。在接下來的內容中，對RDIS的性能進行了評估。實驗結果分為兩個部分：（1）展示了RDIS在不同學習率情況下的收斂速度。（2）將提出的算法與RLSDWSN和DCBSRP算法進行了性能對比。

2.1 實驗設置

為了測試提出的RDIS算法，選擇一個含有30個節點的網絡。從源節點到目標節點之間有多條路徑可供選擇。實驗參數的設置如表1所示。

表1 仿真參數表

圖2展示了不同學習率情況下RDIS算法的收斂速度。從圖中可以看出學習速率對收斂性能有影響，而當學習速率為0.1時，RDIS的收斂速度最快。因此，在接下來的訓練中，將學習率設置為0.1。

圖2 不同學習率下算法收斂速度

2.2 性能評估

為了評估RDIS的性能，選擇分組延遲和吞吐量作為網絡度量標準。在相同條件下，將RDIS算法與文獻[10]中的RL-SDWSN算法和文獻[7]中的DCBSRP算法進行性能對比。

RL-SDWSN算法使用學習算法，考慮到能源效率和網絡服務質量，根據獲得的獎勵情況確定下一步的行動，從而提高WSN的網絡性能。DCBSRP算法選擇不同的節點充當簇頭節點，使用能量高的節點執行收集和轉發任務，從而提高無線傳感器節點的壽命和性能。每個算法在同一實驗環境下分別運行了300輪。

從圖3中可以看出，隨著訓練次數的增加，RDIS的分組延遲持續減小。在RDIS訓練到69輪、RL-SDWSN訓練到95輪后，二者的分組延遲都變化緩慢且趨于穩定，RDIS的延遲更低。這是因為RDIS可以根據流量大小動態地選擇轉發路徑，并通過與環境的交互，找到近乎最優的策略，不斷提高路由決策的水平。DCBSRP由于一開始就確定了路由路徑，在后續流量增大的情況下，容易導致鏈路擁塞，分組延遲稍高于其他兩種算法。

圖3 分組延遲對比

圖4展示了同一環境下三種算法的吞吐量對比，吞吐量定義為控制器接收到的數據包總數。

圖4 吞吐量對比

從圖4中可以看出，一開始與DCBSRP相比，RDIS和RLSDWSN沒有明顯的優勢。這是因為流量較小時，網絡不會出現擁塞，DCBSRP計算的路徑對路由數據流非常有效。但是DCBSRP在高流量負載下會嚴重導致低效的帶寬分配。在流量逐漸變大的過程中，RDIS可獲得最大的網絡吞吐量，具有明顯的優勢。RDIS的吞吐量高于RL-SDWSN下的吞吐量，性能更好。

3 結 論

本文提出了一種無線傳感器網絡中基于DDPG的智能路由算法，以便在應用服務質量要求提高的情況下，通過優化路由路徑使整體網絡性能接近最優。具體來說，RDIS從控制器中獲得網絡流量信息，根據網絡需求和環境條件，提出了具有分組延遲和吞吐量的效用函數，通過不斷的迭代來優化網絡性能，通過與網絡環境互動，根據自己的經驗做出更好的控制決策，實現最佳網絡效用。RDIS通過提高吞吐量和降低分組延遲，實現了更好的網絡性能。