基于DQN 的車載邊緣網絡任務分發卸載算法

趙海濤，張唐偉，陳躍，趙厚麟 ，朱洪波

（1.南京郵電大學教育部泛在網絡健康服務系統工程研究中心，江蘇 南京 210003；2.南京郵電大學江蘇省無線通信重點實驗室，江蘇 南京 210003；3.南京郵電大學通信與信息工程學院，江蘇 南京 210003）

1 引言

作為5G 移動通信代表性應用場景之一，車聯網及自動駕駛已經成為熱點研究領域，在未來將會經歷前所未有的發展[1]。隨著車聯網等技術的快速發展及數據量的日益龐大，大量對計算資源高需求的車載應用任務隨之出現，如自動駕駛、智能識別、實時路況等[2]。這些車載應用任務不僅需要大量的存儲與計算資源，同時對于任務執行時延的要求非常嚴格，給現有車載設備的通信能力、計算能力帶來了很大的挑戰[3]。為了解決車輛終端與車載應用任務之間的矛盾，融合移動邊緣計算（MEC,mobile edge computing）的協同通信技術被引入車聯網中[4]。車輛終端攜帶的計算任務可以卸載到路邊單元（RSU,road side unit）配置的MEC 服務器上，在車輛終端旁邊就能夠完成任務的計算及分析，有效緩解了車輛終端計算、存儲資源不足的困境，減小了計算任務的處理時延與車輛終端能耗[5]。針對任務遷移和資源調度問題，國內外進行了大量相關研究。文獻[6]對通信與計算融合技術的機遇與挑戰做了大量的介紹，并針對“邊緣智能”提出了具體的實施方案。然而，動態的車聯網場景給MEC 技術的大規模應用帶來了許多問題，車輛終端的高速移動及通信參數的變化導致計算任務卸載決策復雜化[7]。

目前車聯網場景下計算任務卸載決策主要解決車載應用任務是否需要卸載及卸載多少的問題。卸載決策的主要優化目標有任務執行時延、能耗及時延與能耗的權衡等[8]。文獻[9]提出了一種面向5G的邊緣計算多用戶卸載方案，將問題轉換為多重背包問題，有效降低了任務執行時延。文獻[10-12]基于各種數值優化算法，提出了一系列計算卸載決策及資源配置方案。基于馬爾可夫決策過程理論（MDP,Markov decision process）的強化學習方法，如Q 學習算法、深度強化學習（DRL,deep reinforcement learning）方法如深度Q 網絡（DQN,deep Q nework）也被研究人員用來解決卸載問題。文獻[13]構建了馬爾可夫決策過程函數，解決了車輛終端由于MEC 服務器服務范圍不足而導致的服務中斷問題，解決了單純基于距離進行卸載服務的不足，但是該方法在卸載過程中沒有對服務方的時延、能耗等成本進行合理的評估。文獻[14]提出了一種基于DQN 的多用戶單小區計算卸載與資源分配算法，聯合優化任務執行時延與能耗的加權和，實現了任務總成本的下降。與其他方法明顯不同的是，DQN 可以在沒有任何先驗信息的前提下與環境進行交互，從中學習并調整卸載策略以達到最佳的長期回報[15-16]，這對于動態時變的車聯網環境來說尤其重要。

上述方法都沒有針對不同車輛終端進行任務優先級劃分，從而不能實現處理程序的優化。同時這些方法需要實時準確的信道狀態消息，算法復雜度高、迭代步驟長，難以滿足時延敏感型的車聯網通信系統。針對以上研究中存在的問題，本文通過引入移動邊緣計算，根據車輛終端任務屬性的不同進行優先級劃分，使車輛終端攜帶的計算任務能夠直接在邊緣節點進行處理；在車輛終端，基于DQN研究了計算速率最優的任務卸載策略，在信道條件時變的環境中能夠根據過去的經驗實現卸載策略的自我更新，從而有效降低任務執行時延、提高車聯網車輛終端用戶的使用體驗。

2 系統模型

本文選取車輛終端、RSU 與其連接的MEC 服務器所構成的網絡通信模型。由于車輛終端的快速移動，車聯網絡拓撲架構會產生動態變化。為了滿足時延要求，車輛終端將其攜帶的計算任務遷移至RSU 連接的MEC 服務器中。這產生了2 個問題，具體如下。

1) 卸載決策的制定問題。由于計算任務的類型、信道增益均不相同，如果將計算任務統一卸載到MEC 服務器，在信道增益很差的情況下會造成非常嚴重的傳輸時延問題，同時車輛終端計算資源也得不到充分利用，導致計算資源浪費。因此本文根據車輛終端信道實時狀態制定卸載決策，將部分車輛終端的計算任務卸載至邊緣側服務器，從而降低計算任務處理時延、提高計算資源利用率。

2) 計算資源分配問題。系統會根據業務類型分配優先級，但是相同類型業務由于其屬性的不同，也可能具有不同的優先級需求，因此，必須在計算資源分配之前根據計算任務屬性的不同進行預處理，否則相同的卸載決策會導致MEC 服務器不能合理分配計算資源，影響用戶使用體驗。

車聯網環境下的計算任務卸載模型架構如圖1所示。在該模型架構中，受限于較弱的計算能力，部分車輛終端會將自身攜帶的計算任務通過無線網絡卸載到RSU 連接的MEC 服務器進行處理。首先，車輛終端會將自身攜帶的計算任務信息如最大可容忍時延、數據量大小、計算復雜度等上傳至RSU。RSU 通過計算得到計算任務優先級，然后根據MEC 服務器的計算任務調度算法決定將哪些車輛終端的計算任務卸載至服務器。車輛終端隨后接受RSU 的調度信息，開始卸載或執行計算任務。假設在計算任務執行過程中，一旦執行時間超過其最大容忍時延，就判定當前計算任務執行失敗，并將當前計算任務執行時間設置為最大值。

圖1 計算任務卸載模型架構

本文假設RSU 覆蓋范圍內有K個車輛終端，車輛終端攜帶的計算任務表示為Ck=(Vk,Dk,Γk,Pk)，其中，Dk表示計算任務的數據大小，單位為bit；Vk表示計算任務計算復雜度，單位為round/bit；Γk表示計算任務最大可容忍時延，單位為ms；Pk表示計算任務的優先級，由RSU計算后得出。假設計算任務無論是在車輛終端執行還是卸載到MEC 服務器執行，以上參數均保持不變。RSU 覆蓋范圍內的所有車輛終端的計算任務表示為M={M1,M2,…,Mk}，其中k∈K。

3 車載邊緣網絡計算任務分發卸載方案

3.1 計算任務優先級劃分

車輛終端將攜帶的計算任務卸載到MEC 服務器時，由于計算任務類型的不同導致所需要的計算資源也不同。層次分析法（AHP,analytic hierarrchy process）指將與決策總是有關的元素分解成目標層、準則層、方案層等層次，并在此基礎之上進行定性和定量分析的決策方法，是一個多標準決策/多屬性決策模型，非常適用于權重分配的計算任務調度應用場景[17]。本文通過AHP 算法可以給容忍時延小、計算復雜度高的計算任務分配相對高一些的權重系數，為MEC 服務器的計算資源調度過程提供更合理的依據，提高車輛終端計算任務的卸載執行成功率。

當確定計算任務的權重系數時，本文主要考慮計算任務的計算復雜度、數據總量和最大容忍時延這3 個評價因素，其中，計算復雜度的重要程度最高，數據總量次之，最大容忍時延最低。本文將計算任務目標層的因素進行兩兩比較，構造出評價因素判斷矩陣A=(aij)3×3，以及目標層相對于準則層的判斷矩陣B1,B2,…,B3=(aij)K×K。其中，

根據方根法求得判斷矩陣Bk對應的權重向量元素，如式(2)所示。

其中，k表示第k個終端車輛，i表示第k個終端車輛所攜帶任務的第i個評價因素，可以得到所有車輛終端計算任務的權重矢量矩陣為

根據同樣的方法求得評價因素判斷矩陣A的權重向量Δ=[Δ1,Δ2,Δ3]，其權重元素為

權重元素通過一致性檢驗后，得到所有計算任務的權重向量W，其中每一個元素分別代表對應車輛終端計算任務的權重，如式(5)所示。

3.2 卸載決策制定問題的建模

車輛終端攜帶的計算任務分為車輛終端計算模式和卸載計算模式。車輛終端用于執行計算任務的總能耗Econstraint為額定值，當前計算任務執行能耗Ecurrent表示為

其中，pk為車輛終端發射功率，kk為能量效率系數，fk為車輛終端處理器頻率，tk為計算任務傳輸時間或車輛終端執行時間。

其中，Bk為當前車輛終端傳輸帶寬，其中最大傳輸帶寬為BHz，N0為信道傳輸噪聲。基于LTE-V2X（long term evolution-vehicle to X）技術，本文假設無線信道增益gk、車輛終端發射功率pk及傳輸帶寬Bk在對應的時間段內均是時變的，并且基于分布式方式下的SPS（semi persistent scheduling）資源分配算法[19]對RSU 覆蓋范圍下的車輛終端進行統一控制。本文以最大化計算任務處理速率為優化目標，以車輛終端能耗與傳輸帶寬為約束，在求得計算任務處理速率最大加權和之后，可求得對應的計算任務最小執行時延。同時，基于式(5)得出的計算任務權重wk，對于優先級別更高的計算任務可以分配更多的計算資源，使其執行時間小于計算任務最大容忍時延，保證計算任務卸載過程成功進行。本文的優化目標為

其中，xk表示為卸載決策向量元素，xk=0 表示車輛終端計算模式，xk=1 表示卸載計算模式；約束條件C2 和C3 分別表示計算任務執行能耗和車輛終端傳輸帶寬不能超過額定值。

通過求出卸載決策向量的最優值可以求解式(8)所示優化問題。然而該問題是一個非凸問題，隨著車輛終端數量及計算任務大小的增加，該問題的計算復雜度也會迅速增加。

3.3 AHP-DQN 任務分發卸載算法

面對上述挑戰，傳統的數值優化方法效率較低。本文提出了一種AHP-DQN 任務分發卸載算法，其核心思想是將Q 網絡作為策略評判標準，通過Q網絡遍歷當前狀態下的各種動作與環境進行實時交互，其動作、狀態值、獎勵值存放于回訪記憶單元通過Q 學習算法經歷多個迭代過程來反復訓練Q網絡，最后得到最佳卸載策略。與文獻[14]算法不同的是，本文算法通過引入層次分析法對車輛終端計算任務進行預處理，提高MEC 服務器對計算資源的合理分配能力。同時重新定義了Q 網絡中的獎勵函數，以加權后的計算任務處理速率和為優化目標，減小算法迭代過程中的計算復雜度，加快算法收斂速度。本文的卸載決策算法致力于設計一個卸載策略函數，當MEC 服務器收到車輛終端的計算任務信息并得出計算任務對應的權重時，能夠根據當前車輛終端的無線信道增益情況，快速調整深度學習網絡參數θt，并生成計算任務卸載策略，策略函數可以表示為π:g→x。該策略函數的產生可以分為兩步，具體如下。

1) 卸載決策動作的產生。當MEC 服務器收到車輛終端當前的信道增益信息后，深度學習網絡根據當前觀測到的狀態st得到卸載動作向量Xt=[x1,x2,…,xK]，并根據式(7)生成獎勵值rt。同時本文的動作狀態函數Q(st,xt,θt)由深度學習網絡確定，深度學習網絡激活函數為ReLu 函數，網絡輸出函數為Sigmoid 函數，其對應卸載動作的概率值。

2)卸載決策動作的更新。根據式(9)實現動作狀態函數的更新。

其中，αk與γ分別為學習速率與折扣因子，s'為第k次迭代過程中執行動作xt后的狀態觀測值，x'為狀態s′下獎勵值最大的動作，Ek為迭代過程中的累積獎勵值。對于第k次迭代過程而言，通過最小化式(10)目標函數，可以更新網絡參數θ，從而實現卸載決策動作的更新。

重復上述2 個步驟得到t時刻最佳狀態對后，將該狀態?動作對(gt,)放入經驗池，作為新的訓練樣本。當經驗池容量足夠后，新生成的狀態?動作對會代替舊的數據樣本。深度學習網絡反復學習最佳狀態對(gt,)，并隨著時間的推移生成更好的卸載決策輸出。在存儲空間有限的約束下，DNN 僅從最新生成的數據樣本中進行學習，這種閉環強化學習機制會不斷改善其卸載策略，直到收斂。本文算法偽代碼如算法1 所示。

算法1AHP-DQN 計算任務分發卸載算法

輸入計算任務的計算復雜度Vk、數據總量Dk及最大容忍時延Γk。根據式(1)～式(5)得到每個計算任務的優先級Pk，即計算任務的計算資源分配權重

輸出車輛終端攜帶任務的最終卸載決策X=[x1,x2,…,xK]

4 仿真結果與分析

本節通過Python 編程語言對本文算法進行仿真以評估算法性能。本文仿真場景為IEEE 802.11p 標準規定下的車聯網場景，仿真實驗參數根據文獻[20]及移動邊緣計算白皮書相關約束進行假設。在車聯網場景下，每個RSU 的覆蓋范圍為1 000 m，車輛終端速度假設為40 km/h，每個車輛終端計算能力為108round/s，車載車輛終端計算功率為3 W，發射功率為0.3 W。攜帶的計算任務數據（以kbit 為單位）服從[300,500]的均勻分布，計算任務復雜度（以兆輪為單位）服從[9 000,11 000]的均勻分布。下面將本文算法分別與全部車輛終端計算、Q 學習算法、DQN[14]進行比較。

本文算法收斂過程如圖2 所示。縱軸分別表示訓練過程中所有車輛終端的歸一化計算速率及損失函數值。根據經驗風險最小化的知識，收斂概率與網絡復雜度負相關，結合應用場景的實際維度情況，本文選擇了兩層DNN 結構，同時在時延要求較高的車載邊緣網絡中并不注重未來的潛在回報，因此本文設置了一個較小的折扣因子γ。在樣本不多的初期采用較高的學習速率αk，隨著經驗池樣本增加，逐漸減小αk，避免損失函數過于震蕩。在設計Q函數與獎勵值時，一方面盡量使收斂過程中Q的均值為0，另一方面使獎勵值的正反饋稍大些，保證初期獎勵值的負反饋過程中能夠采取人工干預提升正回報，加速收斂過程。從圖2 可以看出，在車輛終端數目為10 的情況下，本文算法經過50 次迭代后，DQN 已經逐漸收斂到最優解。與Q 學習算法的收斂結果相比較，本文算法得到的優化目標具有更好的效果。從圖2 還可以看出，盡管設置了較大的經驗回放池尺度，由于貪婪概率ε的存在，收斂曲線存在些許波動，但不影響算法總體的收斂性。

圖2 3 種算法的收斂過程

圖3 中，在車輛終端數目為10 的情況下，將本文算法與全部車輛終端計算、Q 學習算法[14]進行比較。從圖3 可以看到，隨著計算任務復雜度的增加，3 種算法的計算任務執行成功率都在下降。當計算任務復雜度最高時，全部車輛終端計算的計算任務執行成功率只有24%，Q 學習算法的執行成功率由81%下降到了64%。與之相對應的是，本文算法的執行成功率保持了一個相對穩定的狀態。與Q 學習算法一樣，本文算法只對能耗及傳輸帶寬做了相應的約束，但是隨著計算任務復雜度的上升，計算任務的差異度變大，基于AHP 算法對計算任務做的預處理能夠使MEC 服務器更加合理地調度計算資源，從而提高計算任務卸載執行成功率。

圖3 計算任務執行成功率與計算復雜度的關系

在計算任務復雜度不變的情況下，將本文算法與全部車輛終端計算、Q 學習算法、DQN 進行比較，如圖4 所示。從圖4 可以看到，隨著車輛終端數的增加，計算任務量變大，計算任務執行時延都隨之上升。當車輛終端數目小于10 時，本文算法與Q學習算法、DQN 的執行時延幾乎沒有不同。當車輛終端數目超過10 時，本文算法的計算任務平均執行時延相比全部車輛終端計算的時延減少了95 ms，相比Q 學習算法減少了24 ms，相比于DQN 有些許提升。隨著計算任務數目的增加，相比全部車輛終端計算與Q 學習算法，本文算法的卸載方案能夠根據信道實際情況進行學習，從而做出更合適的卸載決策，使計算任務執行時延更小。但是在仿真實驗中，僅改變車輛終端數目，車輛終端計算任務的計算復雜度、數據量大小等屬性保持不變，基于AHP算法對計算任務做出的預處理產生的效果有限，因此本文算法與Q 學習算法的效果提升有限。

圖4 任務平均時延與車輛終端數目的關系

在車輛終端數目為10 的情況下，隨著一半的車輛終端計算任務計算復雜度的增加，4 種算法的計算任務平均執行時延都在增加，如圖5 所示。從圖5 中可以看出，在計算任務復雜度最高時，本文算法的計算任務執行時延與全部車輛終端計算相比減少了219 ms，與Q 學習算法相比減少了64 ms，與DQN 相比減少了24 ms。比較圖4 與圖5 可以看出，在計算任務差異度越大的應用場景中，本文算法優勢越明顯。隨著計算復雜度的上升，不同車輛終端的計算任務差異度越大，MEC 服務器計算資源的分配權重也隨之變化。與Q 學習算法和DQN 不同的是，本文算法對所有車輛終端的計算任務做了自適應優先級預處理，給優先級更高的計算任務分配了更多的計算資源，使計算任務執行成功概率更高，從而提高卸載決策正確率，有效減小了計算任務執行時延。

圖5 任務平均時延與計算任務復雜度的關系

5 結束語

面向車聯網環境中車輛終端受最大容忍時延及最大能耗約束的情況，本文提出了一種基于深度Q 網絡的計算任務分發卸載算法。車輛終端首先根據自身計算任務大小、計算復雜度及最大容忍時延等因素對計算任務優先級進行合理劃分，并根據車輛終端實時信道增益進行自主卸載決策部署，以找到最優策略。通過對該算法的大量仿真分析及數值驗證，本文提出的AHP-DQN 任務分發卸載算法在不同的系統參數下都具有較好的性能。今后的研究將會考慮對DQN 的訓練算法及神經網絡結構進行持續優化改進，同時對無線電干擾等復雜環境因素也會加以考慮。