軟件定義物聯(lián)網(wǎng)中基于深度強(qiáng)化學(xué)習(xí)的路由優(yōu)化算法

王健，朱曉娟

（安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001）

0 引 言

近年來(lái)，物聯(lián)網(wǎng)（Internet of Things, IoT）被廣泛應(yīng)用于環(huán)境監(jiān)測(cè)、工業(yè)控制和國(guó)防軍事等領(lǐng)域，并逐漸成為全球科技戰(zhàn)略發(fā)展的焦點(diǎn)之一。隨著物聯(lián)網(wǎng)的快速發(fā)展，高速、海量數(shù)據(jù)通信向服務(wù)質(zhì)量保障機(jī)制提出了挑戰(zhàn)。于是，有學(xué)者提出了軟件定義網(wǎng)絡(luò)（software def ined network, SDN），用以優(yōu)化通信網(wǎng)絡(luò)。SDN是將控制平面和數(shù)據(jù)平面分離的框架，以便動(dòng)態(tài)管理和控制大量網(wǎng)絡(luò)設(shè)備、拓?fù)洹⒙酚?、QoS和數(shù)據(jù)包處理策略。SDN控制器通過(guò)在控制器內(nèi)運(yùn)行不同的模塊來(lái)執(zhí)行各種任務(wù)，從而提供面向應(yīng)用程序的服務(wù)。

強(qiáng)化學(xué)習(xí)作為可以優(yōu)化網(wǎng)絡(luò)決策的一種方案也被應(yīng)用到物聯(lián)網(wǎng)環(huán)境中。在一定的環(huán)境狀態(tài)中，智能體與環(huán)境交互，根據(jù)動(dòng)作來(lái)獲得獎(jiǎng)勵(lì)，并根據(jù)獎(jiǎng)勵(lì)情況確定下一步的動(dòng)作，循環(huán)往復(fù)，不斷提高自己的決策能力。Lillicrap等人提出的深度確定性策略梯度算法（Deep Deterministic Policy Gradient,DDPG）基于Actor-Critic框架解決連續(xù)狀態(tài)空間下的問(wèn)題。DDPG使用深度Q網(wǎng)絡(luò)逼近Q表，使用策略網(wǎng)絡(luò)直接產(chǎn)生確定的動(dòng)作，解決了DQN面對(duì)連續(xù)動(dòng)作時(shí)無(wú)法處理的問(wèn)題。

文獻(xiàn)[3-6]提出了基于SDN特性的路由解決方案，如可編程性、全局視圖、網(wǎng)絡(luò)傳輸和控制的解耦，以及邏輯集中控制。但是這些解決方案沒(méi)有使用強(qiáng)化學(xué)習(xí)的算法，在網(wǎng)絡(luò)狀態(tài)變化時(shí)容易導(dǎo)致?lián)砣?/p>

Muhammad Adil等人提出一種高效的混合路由方案（DCBSRP），利用自組織按需距離矢量（AODV）路由協(xié)議和低能耗自適應(yīng)集群層次結(jié)構(gòu)（LEACH）協(xié)議，在規(guī)定的時(shí)間間隔內(nèi)動(dòng)態(tài)形成簇頭節(jié)點(diǎn)。選擇能量高的節(jié)點(diǎn)充當(dāng)簇頭節(jié)點(diǎn)，平衡節(jié)點(diǎn)之間的負(fù)載。仿真結(jié)果表明，該方案不僅提高了網(wǎng)絡(luò)的壽命，而且在吞吐量、丟包率和能效方面都優(yōu)于其他方案。

文獻(xiàn)[8-10]基于傳統(tǒng)強(qiáng)化學(xué)習(xí)的思想解決路由優(yōu)化問(wèn)題。CHANGHE Y U等人使用深度強(qiáng)化學(xué)習(xí)（deep reinforcement learning, DRL）中的DDPG對(duì)路由進(jìn)行優(yōu)化。仿真實(shí)驗(yàn)表明，該算法實(shí)現(xiàn)了對(duì)網(wǎng)絡(luò)全局的智能控制和管理，具有良好的收斂性。針對(duì)DDPG訓(xùn)練過(guò)程會(huì)消耗較多網(wǎng)絡(luò)資源這一情況，周浩等人提出了“線下訓(xùn)練、線上運(yùn)行”的方法，但他們?cè)谠O(shè)計(jì)該方法時(shí)并沒(méi)有將復(fù)雜的網(wǎng)絡(luò)環(huán)境考慮在內(nèi)。

將SDN路由優(yōu)化看成一個(gè)決策問(wèn)題，運(yùn)用強(qiáng)化學(xué)習(xí)來(lái)優(yōu)化路由。將當(dāng)前的網(wǎng)絡(luò)環(huán)境視為強(qiáng)化學(xué)習(xí)中的初始狀態(tài)，通過(guò)改變網(wǎng)絡(luò)參數(shù)，將當(dāng)前網(wǎng)絡(luò)狀態(tài)下的網(wǎng)絡(luò)信息作為輸入，獎(jiǎng)勵(lì)值采用延遲、吞吐量等指標(biāo)，最后通過(guò)訓(xùn)練得到路由模型。當(dāng)網(wǎng)絡(luò)中有新流到達(dá)時(shí)，智能體可以快速計(jì)算出性能最優(yōu)的路由路徑。

本文在SDN架構(gòu)下，針對(duì)無(wú)線傳感器網(wǎng)絡(luò)環(huán)境流量信息復(fù)雜，容易致使路徑發(fā)生擁塞的問(wèn)題，采用RDIS算法使計(jì)算出的源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的路由路徑在全局下性能接近最優(yōu)，從而實(shí)現(xiàn)提高網(wǎng)絡(luò)性能的目的。根據(jù)SDN控制器提供的全局路由視圖，RDIS通過(guò)DRL代理與環(huán)境交互學(xué)習(xí)路由策略，該算法可以根據(jù)動(dòng)作和獲得的獎(jiǎng)勵(lì)找到性能接近最優(yōu)的路由路徑。

1 深度強(qiáng)化學(xué)習(xí)

1.1 DDPG算法

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

DDPG的參數(shù)更新過(guò)程主要分為兩個(gè)階段。actor模塊根據(jù)輸入的狀態(tài)輸出動(dòng)作，critic模塊將actor模塊輸出的動(dòng)作和當(dāng)前狀態(tài)輸入，最終輸出值。兩個(gè)模塊進(jìn)行參數(shù)的更新。式（1）表示策略更新的方法：

在critic模塊中，通過(guò)TD-error對(duì)神經(jīng)網(wǎng)絡(luò)參數(shù)進(jìn)行反向更新，如式（2）所示：

y是目標(biāo)網(wǎng)絡(luò)針對(duì)網(wǎng)絡(luò)環(huán)境狀態(tài)所采取的下一步動(dòng)作的值。該值的動(dòng)作來(lái)源于actor模塊中的目標(biāo)網(wǎng)絡(luò)。目標(biāo)網(wǎng)絡(luò)根據(jù)在線網(wǎng)絡(luò)傳送過(guò)來(lái)的參數(shù)信息′和下一步狀態(tài)所采取的動(dòng)作a進(jìn)行更新。y的具體更新過(guò)程如式（3）所示：

在網(wǎng)絡(luò)中，將值進(jìn)行參數(shù)化，可以針對(duì)現(xiàn)有狀態(tài)做出準(zhǔn)確的評(píng)估，選取最合適的動(dòng)作持續(xù)運(yùn)行。

在DDPG中，智能體從經(jīng)驗(yàn)池中對(duì)樣本“隨機(jī)采樣”，由于不同數(shù)據(jù)的重要性不同，這種方法容易導(dǎo)致學(xué)習(xí)效率低。本文基于優(yōu)先經(jīng)驗(yàn)回放，根據(jù)經(jīng)驗(yàn)重要性，希望價(jià)值越高的經(jīng)驗(yàn)被采樣到的概率越大，從而提高學(xué)習(xí)效率。通過(guò)概率方式抽取經(jīng)驗(yàn)，每個(gè)經(jīng)驗(yàn)的優(yōu)先值表達(dá)式如式（4）所示：

但是這種采樣方法引入了偏差，因?yàn)樗淖兞藬?shù)據(jù)的分布，進(jìn)而改變了期望值。因此，通過(guò)加上重要性采樣來(lái)修改權(quán)重，如式（5）所示：

其中，表示抽樣的批次大小，表示一個(gè)介于0和1之間的參數(shù)。在采樣時(shí)，使用重要性采樣參數(shù)來(lái)調(diào)整權(quán)重，根據(jù)樣本優(yōu)先級(jí)對(duì)樣本采樣。

1.2 路由算法RDIS

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

圖1 DDPG路由模型

最底下為數(shù)據(jù)平面， 由傳感器節(jié)點(diǎn)等硬件設(shè)備組成。數(shù)據(jù)平面的主要功能是在傳感器節(jié)點(diǎn)之間執(zhí)行數(shù)據(jù)的轉(zhuǎn)發(fā)。

控制平面擁有一個(gè)邏輯集中的控制器，確保用戶平面和數(shù)據(jù)平面之間的通信?？刂破矫鎯?nèi)包含四個(gè)模塊，分別為網(wǎng)絡(luò)鏈路模塊、拓?fù)浒l(fā)現(xiàn)模塊、生成流表模塊和智能模塊。

網(wǎng)絡(luò)鏈路模塊的作用是發(fā)現(xiàn)和維護(hù)整個(gè)網(wǎng)絡(luò)拓?fù)涞逆溌沸畔ⅰ＞W(wǎng)絡(luò)鏈路模塊將每個(gè)傳感器節(jié)點(diǎn)的相關(guān)信息上傳到控制器，存儲(chǔ)到控制器中為接下來(lái)的模塊做準(zhǔn)備。在SDN-WISE架構(gòu)下，使用report數(shù)據(jù)包獲取所需的鏈路信息，包括延遲、吞吐量等信息。拓?fù)浒l(fā)現(xiàn)模塊使用從網(wǎng)絡(luò)鏈路模塊獲取的節(jié)點(diǎn)信息生成和維持網(wǎng)絡(luò)拓?fù)?。生成流表模塊根據(jù)智能模塊計(jì)算好的路徑，將流表下發(fā)到數(shù)據(jù)平面，規(guī)劃路由路徑。

智能模塊學(xué)習(xí)網(wǎng)絡(luò)的行為，并利用RDIS代理計(jì)算路徑。它與控制平面交互，檢索鏈路狀態(tài)信息并下發(fā)計(jì)算好的流表。該模塊還包含拓?fù)湫畔⑹占K、RDIS代理和動(dòng)作翻譯模塊。拓?fù)湫畔⑹占K用于存放從控制平面收集的網(wǎng)絡(luò)狀態(tài)信息。動(dòng)作翻譯模塊將RDIS代理中的動(dòng)作翻譯成一組適當(dāng)?shù)膕ensor-openflow消息，從而更新流表。

用戶平面是SDN的最高級(jí)別層，在該平面中實(shí)現(xiàn)了面向應(yīng)用程序服務(wù)的概念。網(wǎng)絡(luò)狀態(tài)信息（例如路由信息）通過(guò)數(shù)據(jù)平面收集并被各種網(wǎng)絡(luò)應(yīng)用程序使用。

在RDIS中，將PER與DDPG相結(jié)合，以提高價(jià)值高的經(jīng)驗(yàn)被成功采樣的概率。PER處理過(guò)程為：

算法1：PER采樣過(guò)程。

（1）初始化經(jīng)驗(yàn)回放池。

（2）根據(jù)權(quán)重θ和θ初始化critic網(wǎng)絡(luò)（(，)|θ）和actor網(wǎng)絡(luò)（（s|θ））。

（3）根據(jù)權(quán)重θ←θ和θ ′←θ初始化目標(biāo)critic網(wǎng)絡(luò)(′(，)|θ)和目標(biāo)actor網(wǎng)絡(luò)（′（s|θ）。

（4）初始化狀態(tài)（），設(shè)置批次大小。

（5）將（s，r，a，s）存儲(chǔ)至經(jīng)驗(yàn)回放池，設(shè)置最大優(yōu)先級(jí)。

（6）For j=1 to T do:

（7）根據(jù)優(yōu)先級(jí)進(jìn)行樣本轉(zhuǎn)換：（s，r，a，s）。

（8）計(jì)算相應(yīng)的重要性采樣權(quán)重W和TD誤差δ。

（9）根據(jù)|δ|的值更新樣本優(yōu)先級(jí)。

（10）End for。

為了將DDPG應(yīng)用到路由問(wèn)題中，對(duì)算法的獎(jiǎng)勵(lì)函數(shù)、動(dòng)作空間和狀態(tài)空間進(jìn)行設(shè)計(jì)。下面介紹RDIS算法的獎(jiǎng)勵(lì)函數(shù)、狀態(tài)空間和動(dòng)作空間：

（1）獎(jiǎng)勵(lì)函數(shù)。獎(jiǎng)勵(lì)是智能體做出動(dòng)作后獲得的反饋，它可以是正面的，也可以是負(fù)面的。獎(jiǎng)勵(lì)在RDIS中非常重要，因?yàn)橄乱粋€(gè)動(dòng)作將根據(jù)獎(jiǎng)勵(lì)的值來(lái)確定。獎(jiǎng)勵(lì)函數(shù)的定義如式（6）所示，它與吞吐量成正比，與鏈路延遲成反比。值和∈[0，1]是可調(diào)的參數(shù)，可根據(jù)需要自動(dòng)調(diào)整權(quán)重。

為了防止在學(xué)習(xí)過(guò)程中存在某一個(gè)狀態(tài)指標(biāo)比其他指標(biāo)影響更大的情況，對(duì)方程（6）使用Min-Max技術(shù)進(jìn)行歸一化處理。它可以將參數(shù)范圍縮放到任意值區(qū)間。式（7）表示獎(jiǎng)勵(lì)函數(shù)的歸一化結(jié)果，其中和分別為吞吐量和鏈路延遲的歸一化值。

每個(gè)歸一化值（和）均由方程（8）得到。在這個(gè)方程中，′表示需要?dú)w一化的值，表示歸一化中使用的值集。

（2）狀態(tài)空間?？刂破鲹碛芯W(wǎng)絡(luò)拓?fù)涞娜忠晥D，通過(guò)控制器可以獲得所需的狀態(tài)空間信息。狀態(tài)空間中的每個(gè)狀態(tài)為在選擇下一跳節(jié)點(diǎn)后收集到的節(jié)點(diǎn)和鏈路狀態(tài)信息。對(duì)于傳感器節(jié)點(diǎn)v，∈{1，2，3，…，}，控制平面從數(shù)據(jù)平面收集帶寬、時(shí)延、丟包率loss和吞吐量等信息?？傮w來(lái)說(shuō)，狀態(tài)空間可以表示為：

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

（3）動(dòng)作空間。動(dòng)作空間表示對(duì)所有狀態(tài)采取動(dòng)作的合集?？捎梢韵鹿奖硎荆?/p>

a代表在節(jié)點(diǎn)采取的動(dòng)作，并且a={

a|j∈{1，2，3，…，}，≠}。a表示節(jié)點(diǎn)和節(jié)點(diǎn)之間的連接關(guān)系。若a=0，表示兩個(gè)節(jié)點(diǎn)之間不連通，a∈（0，1]表示從節(jié)點(diǎn)選擇下一跳節(jié)點(diǎn)為節(jié)點(diǎn)的權(quán)重。

使用上述狀態(tài)空間、動(dòng)作空間和獎(jiǎng)勵(lì)函數(shù)進(jìn)行路由優(yōu)化并使獎(jiǎng)勵(lì)最大化。以下是RDIS的訓(xùn)練過(guò)程：

算法2：RDIS訓(xùn)練過(guò)程

輸入：網(wǎng)絡(luò)狀態(tài)數(shù)據(jù)包括邊總數(shù)、頂點(diǎn)數(shù)、獎(jiǎng)勵(lì)函數(shù)、學(xué)習(xí)率等

輸出：路由路徑。

（1）初始化控制器。

（2）控制器發(fā)現(xiàn)鄰居節(jié)點(diǎn)，收集傳感器節(jié)點(diǎn)信息。

（3）建立網(wǎng)絡(luò)拓?fù)鋱D。

（4）For episode = 1 to M do。

（5） For t = 1 to T do。

（6） 根據(jù)重要性采樣從經(jīng)驗(yàn)回放池中采集樣本（s，r，a，s）。

（8） 最小化損失更新critic網(wǎng)絡(luò)：

（9） 通過(guò)采樣更新actor策略：

（10） 目標(biāo)網(wǎng)絡(luò)更新：

（11） End for

（12）End for

2 實(shí)驗(yàn)與性能評(píng)估

在實(shí)驗(yàn)中，使用Pytorch作為后端實(shí)現(xiàn)RDIS算法，Python版本為3.8。在接下來(lái)的內(nèi)容中，對(duì)RDIS的性能進(jìn)行了評(píng)估。實(shí)驗(yàn)結(jié)果分為兩個(gè)部分：（1）展示了RDIS在不同學(xué)習(xí)率情況下的收斂速度。（2）將提出的算法與RLSDWSN和DCBSRP算法進(jìn)行了性能對(duì)比。

2.1 實(shí)驗(yàn)設(shè)置

為了測(cè)試提出的RDIS算法，選擇一個(gè)含有30個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)。從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)之間有多條路徑可供選擇。實(shí)驗(yàn)參數(shù)的設(shè)置如表1所示。

表1 仿真參數(shù)表

圖2展示了不同學(xué)習(xí)率情況下RDIS算法的收斂速度。從圖中可以看出學(xué)習(xí)速率對(duì)收斂性能有影響，而當(dāng)學(xué)習(xí)速率為0.1時(shí)，RDIS的收斂速度最快。因此，在接下來(lái)的訓(xùn)練中，將學(xué)習(xí)率設(shè)置為0.1。

圖2 不同學(xué)習(xí)率下算法收斂速度

2.2 性能評(píng)估

為了評(píng)估RDIS的性能，選擇分組延遲和吞吐量作為網(wǎng)絡(luò)度量標(biāo)準(zhǔn)。在相同條件下，將RDIS算法與文獻(xiàn)[10]中的RL-SDWSN算法和文獻(xiàn)[7]中的DCBSRP算法進(jìn)行性能對(duì)比。

RL-SDWSN算法使用學(xué)習(xí)算法，考慮到能源效率和網(wǎng)絡(luò)服務(wù)質(zhì)量，根據(jù)獲得的獎(jiǎng)勵(lì)情況確定下一步的行動(dòng)，從而提高WSN的網(wǎng)絡(luò)性能。DCBSRP算法選擇不同的節(jié)點(diǎn)充當(dāng)簇頭節(jié)點(diǎn)，使用能量高的節(jié)點(diǎn)執(zhí)行收集和轉(zhuǎn)發(fā)任務(wù)，從而提高無(wú)線傳感器節(jié)點(diǎn)的壽命和性能。每個(gè)算法在同一實(shí)驗(yàn)環(huán)境下分別運(yùn)行了300輪。

從圖3中可以看出，隨著訓(xùn)練次數(shù)的增加，RDIS的分組延遲持續(xù)減小。在RDIS訓(xùn)練到69輪、RL-SDWSN訓(xùn)練到95輪后，二者的分組延遲都變化緩慢且趨于穩(wěn)定，RDIS的延遲更低。這是因?yàn)镽DIS可以根據(jù)流量大小動(dòng)態(tài)地選擇轉(zhuǎn)發(fā)路徑，并通過(guò)與環(huán)境的交互，找到近乎最優(yōu)的策略，不斷提高路由決策的水平。DCBSRP由于一開(kāi)始就確定了路由路徑，在后續(xù)流量增大的情況下，容易導(dǎo)致鏈路擁塞，分組延遲稍高于其他兩種算法。

圖3 分組延遲對(duì)比

圖4展示了同一環(huán)境下三種算法的吞吐量對(duì)比，吞吐量定義為控制器接收到的數(shù)據(jù)包總數(shù)。

圖4 吞吐量對(duì)比

從圖4中可以看出，一開(kāi)始與DCBSRP相比，RDIS和RLSDWSN沒(méi)有明顯的優(yōu)勢(shì)。這是因?yàn)榱髁枯^小時(shí)，網(wǎng)絡(luò)不會(huì)出現(xiàn)擁塞，DCBSRP計(jì)算的路徑對(duì)路由數(shù)據(jù)流非常有效。但是DCBSRP在高流量負(fù)載下會(huì)嚴(yán)重導(dǎo)致低效的帶寬分配。在流量逐漸變大的過(guò)程中，RDIS可獲得最大的網(wǎng)絡(luò)吞吐量，具有明顯的優(yōu)勢(shì)。RDIS的吞吐量高于RL-SDWSN下的吞吐量，性能更好。

3 結(jié) 論

本文提出了一種無(wú)線傳感器網(wǎng)絡(luò)中基于DDPG的智能路由算法，以便在應(yīng)用服務(wù)質(zhì)量要求提高的情況下，通過(guò)優(yōu)化路由路徑使整體網(wǎng)絡(luò)性能接近最優(yōu)。具體來(lái)說(shuō)，RDIS從控制器中獲得網(wǎng)絡(luò)流量信息，根據(jù)網(wǎng)絡(luò)需求和環(huán)境條件，提出了具有分組延遲和吞吐量的效用函數(shù)，通過(guò)不斷的迭代來(lái)優(yōu)化網(wǎng)絡(luò)性能，通過(guò)與網(wǎng)絡(luò)環(huán)境互動(dòng)，根據(jù)自己的經(jīng)驗(yàn)做出更好的控制決策，實(shí)現(xiàn)最佳網(wǎng)絡(luò)效用。RDIS通過(guò)提高吞吐量和降低分組延遲，實(shí)現(xiàn)了更好的網(wǎng)絡(luò)性能。