馮 浩，郭彩麗

（北京郵電大學信息與通信工程學院，北京 100876）

0 概述

目前，多數(shù)車輛上都安裝了攝像頭，用以采集海量的視頻數(shù)據(jù)，這些視頻數(shù)據(jù)可以幫助車輛感知周圍的環(huán)境信息，也可以通過對視頻數(shù)據(jù)進行分析從而完成車輛軌跡預測、協(xié)作駕駛、車輛檢測與跟蹤、VR（Virtual Reality）、AR（Augmented Reality）等業(yè)務［1］。視覺傳感器能夠為智能車輛提供最主要的信息，視覺感知不僅是環(huán)境感知與建模的基礎，也是實現(xiàn)SLAM（Simultaneous Localization and Mapping）的有力保障。此外，視覺傳感器因其檢測信息量大、可完成多類別任務、價格低廉等優(yōu)勢而受到用戶的青睞，視覺感知逐漸成為環(huán)境感知與建模最主要的發(fā)展方向［2］。視頻信號以一種高度間接的方式包含相關信息，且視覺感知需要復雜的機器視覺和圖像理解技術，因此，對視頻內容進行理解具有重要的現(xiàn)實意義［3］。

視頻內容理解任務是計算密集型任務，車輛端計算能力受限使得必須將視頻卸載到邊緣服務器或云服務器中進行處理，然后將分析結果返回車輛端。目前，計算卸載的優(yōu)化目標主要包括設備能耗［4］、時延以及用戶體驗質量（Quality of Experience，QoE）［5-6］，指導方式主要基于服務質量（Quality of Service，QoS）以及用戶體驗質量［7-8］，而并未優(yōu)化視頻內容理解的精度。

在車聯(lián)網(wǎng)計算卸載決策算法的研究中：文獻［9］采用基于Lyapunov 優(yōu)化的動態(tài)計算卸載決策與資源分配聯(lián)合優(yōu)化方法，其能夠最大化系統(tǒng)效用；文獻［10］考慮聯(lián)合車輛、多計算卸載節(jié)點、多任務場景下的計算卸載決策問題，設計基于改進遺傳算法與貪心策略的近似求解方法，該方法可以滿足用戶對于效用的需求；文獻［11］設計一種車聯(lián)網(wǎng)場景下基于內容感知分類的卸載決策算法，其利用拉格朗日松弛法將構造的非凸問題轉化為凸問題，結合次梯度投影法和貪婪算法獲得系統(tǒng)的最優(yōu)解；文獻［7］采用車聯(lián)網(wǎng)場景下基于MEC（Mobile Edge Computing）的LTE-V 網(wǎng)絡，定性分析各種車輛通信模式對任務卸載性能的影響，采用Q-learning 的方法，提出一種在給定時延約束下以卸載系統(tǒng)效用最大化為優(yōu)化目標的MEC 服務器確定和傳輸模式選擇方案。上述算法雖然能夠在一定程度上對系統(tǒng)的整體效用進行優(yōu)化，但是在任務量較大時存在復雜度過高以及收斂速度較慢的問題。

為了能夠更好地提取視頻內容信息，并使卸載后的視頻中包含更多的有效信息，本文考慮在車輛端利用關鍵幀的提取來預處理視頻內容，根據(jù)處理結果進行計算卸載決策，以優(yōu)化計算卸載決策系統(tǒng)的視頻內容理解精度與系統(tǒng)效用。具體地，本文提出一種內容驅動的QoC 計算卸載指導方式，通過對所采集視頻進行基于關鍵幀的預處理，使得更重要的任務獲得更優(yōu)的計算資源以及MEC，進而提高視頻內容理解任務的整體精度。同時，提出一種基于改進蒙特卡洛樹搜索（Monte Carlo Tree Search，MCTS）的計算卸載決策算法，并引入深度神經網(wǎng)絡（Deep Neural Network，DNN）預訓練先驗轉移概率，以提升算法的收斂速度并降低計算復雜度。

1 系統(tǒng)模型

1.1 車聯(lián)網(wǎng)計算卸載場景

本文采用的車聯(lián)網(wǎng)計算卸載場景如圖1 所示，其由車輛端、路邊單元RSU、多個MEC 以及集中的云計算平臺組成：車輛端負責視頻信息的采集與預處理以及部分任務的計算，對于需要卸載的任務，通過無線通信鏈路將視頻數(shù)據(jù)進行卸載；路邊單元負責其覆蓋范圍內的車輛計算卸載決策，并在接收到任務后按照一定的卸載決策將視頻分析業(yè)務經過有線傳輸?shù)姆绞絺鬏數(shù)竭吘壏掌骰蛳鄳脑品掌髦?，在服務器處理后將結果回傳到車輛端；MEC 與云數(shù)據(jù)平臺負責提供計算資源以對任務進行處理。由于單個MEC 服務器在為大量卸載用戶提供服務時可能超載，因此本文引導一些用戶從MEC 服務器卸載到相鄰服務器，以減輕該服務器的負擔［12］。

圖1 車聯(lián)網(wǎng)計算卸載場景Fig.1 Internet of vehicles computing offloading scenario

為了簡化問題，本文視頻分析業(yè)務無論是在MEC 服務器上執(zhí)行還是在車輛端進行處理，所需要的計算資源始終不變，并且假設每個視頻分析業(yè)務不能被拆分成多個子任務上傳到多個MEC 服務器進行處理，因此，單個視頻內容理解任務在處理過程中只能選擇在本地或上傳到某個邊緣服務器中進行處理。

1.2 時延模型

其中：Dn表示邊緣服務器處理的任務數(shù)據(jù)量表示邊緣服務器的處理頻率；Bn為需要傳輸?shù)囊曨l內容理解任務數(shù)據(jù)量；為上傳過程中的平均傳輸速率。

在車聯(lián)網(wǎng)環(huán)境下，上傳過程中的速率隨著車輛與RSU 之間的位置關系而不斷變化，本文假設車輛在行進過程中的到達率滿足泊松分布，用vi來表示，車輛的移動性使得車輛與RSU 之間的距離在逐漸變化，變化規(guī)律為：

其中：l表示車輛水平行駛過程中RSU 服務器與行駛水平線之間的垂直距離；r表示路邊服務器RSU 的覆蓋范圍。車輛和RSU 之間的通信方式為LTE-V2I 的直連無線通信，通信鏈路是平坦型快衰落的瑞利信道［14］，因此，根據(jù)香農公式，車輛在某一時刻的傳輸速率為：

其中：B表示上行傳輸信道帶寬；Pv表示車輛通信設備的發(fā)射功率；d-δ表示車輛與RSU 之間的路徑損耗；d表示車輛與RSU 覆蓋范圍中心之間的距離；δ表示路徑損耗因子［14］；h表示上行鏈路的信道衰落因子；σ2為高斯白噪聲功率。為了對問題進行簡化，本文采用平均傳輸速率來代替變化的傳輸速率：

其中：ti為車輛通過RSU 的時間。

1.3 能耗模型

計算卸載系統(tǒng)的運行能耗分為2 個部分：一部分為邊緣節(jié)點在通信過程中的能耗，其與傳輸功率有關；另一部分為計算過程中產生的能耗，其與分配的計算資源成二次相關［15］。因此，邊緣服務器的能耗的計算公式如下：

其中：ξ為芯片結構的有效電容系數(shù)；Hn為當前可用計算資源；Uc為單位比特數(shù)據(jù)量需要的計算周期；Tn為視頻內容理解任務量。

視頻內容理解任務卸載到邊緣節(jié)點時的傳輸能耗與傳輸速率成正比，如下：

其中：pn為傳輸功率。因此，視頻內容理解任務計算卸載的總能耗為：

2 優(yōu)化問題構建

2.1 車聯(lián)網(wǎng)計算卸載場景

視頻內容理解任務的精度一方面受到視頻處理算法的影響，另一方面也會受到邊緣服務器狀態(tài)的影響。本文主要考慮邊緣服務器的狀態(tài)對視頻內容理解任務的影響，以使得不同的視頻內容理解任務在不同的算法下都能獲得較高的收益。邊緣服務器的狀態(tài)分為邊緣服務器硬件的可靠性和邊緣服務器的運行狀態(tài)2 個部分。

目前，視頻內容理解任務主要基于DNN 進行訓練和推理，為了衡量邊緣服務器基于DNN 訓練時硬件的有效性，文獻［16］指出需要考慮的指標包括片外帶寬（Off-chip Bandwidth，OB）、區(qū)域效率（Area Efficiency，AE）、吞吐量（Throughput，TH）：OB 包括每個非零MAC 的訪問和MAC 的位寬區(qū)域效率；AE考慮內存（寄存器或SRAM）的尺寸、類型以及控制邏輯的量；TH 分析多種DNN 的運行時間，以考慮映射和內存帶寬的影響，其能提供比峰值吞吐量更有效且信息更豐富的指標。由于DNN 硬件性能對于服務器而言是靜態(tài)的，為了能夠表示這些因素對視頻內容理解精度的影響，本文參考文獻［17］中的基礎量化指標，量化DNN 訓練模型的硬件性能，通過DNN 擬合的方法獲得擬合曲線H(hop，mae，nth)并作為指導，其中，H(hop，mae，nth)表示每比特視頻內容理解任務在當前邊緣服務器下DNN 訓練模型的量化精度。

為了衡量邊緣服務器的運行狀態(tài)，文獻［18］主要考慮的指標包括服務器當前計算資源的可用量大小、邊緣服務器的最大可用線程數(shù)與總線程數(shù)。其中，服務器的可用計算資源量可以通過CPU 的轉數(shù)來進行量化，服務器的可用線程數(shù)與總線程數(shù)可以通過服務器的動態(tài)監(jiān)控來獲得。由于在本文中各個任務的計算所需資源大小固定，因此在考慮服務器狀態(tài)時，將計算資源的量作為約束條件，在考慮服務器并發(fā)線程數(shù)的影響時，服務器狀態(tài)用St來表示，由于并發(fā)線程數(shù)的影響符合邊際減弱效用，因此本文采用對數(shù)構造法，其簡化形式為：

其中：N表示服務器的并發(fā)線程數(shù)；lb(1+N)表示邊緣服務器運行狀態(tài)的量化影響。

由于服務器硬件狀態(tài)St與服務器運行狀態(tài)Tn均能影響視頻內容理解任務的最終精度，因此在考慮精度效用時，本文選擇將2 種沒有耦合性的因素相乘作為計算卸載目標服務器的選擇效用系數(shù)［15］，再與視頻內容理解任務的數(shù)據(jù)量Tn相乘作為最終的計算卸載服務器選擇產生的效用，即：

2.2 優(yōu)化目標

視頻內容理解任務卸載決策的主要目標是決定視頻內容理解任務卸載到當前車輛RSU 的哪一個可用邊緣服務器。本文中計算卸載決策的變量主要為卸載決策矩陣J，卸載決策Jn，m=1 表示任務n卸載到邊緣服務器m。

為了能夠在視頻內容理解任務的時延要求下最大化最終視頻內容理解精度并減少相應的能耗，在考慮計算卸載決策的系統(tǒng)效用時，本文針對計算密集型視頻內容理解任務，將系統(tǒng)效用函數(shù)描述為能耗效用和計算卸載服務器選擇效用的加權和［19］，如下：

其中：α和β分別表示能耗與精度2 種效用的權衡因子，取值范圍在0～1 之間，并且滿足α+β=1，兩者的具體取值根據(jù)不同場景對能耗和精度的側重以及不同類型的任務而變化。參考文獻［20］，為了權衡能耗和精度的影響，本文α與β均取0.5。

為提高最終的視頻內容理解精度，本文的優(yōu)化目標為所有任務的計算卸載平均效用最大化：

其中：Uaverage表示視頻內容理解任務的平均效用。約束條件如下：

其中：C1為任務與邊緣節(jié)點的卸載關系；aij=1 表示視頻內容理解任務i可以卸載到邊緣服務器j，aij=0表示無法將視頻內容理解任務i卸載到邊緣服務器j；C2為計算資源的相關限制，視頻內容分析業(yè)務無法卸載到計算資源已經不足的邊緣服務器上；C3為計算卸載的總處理時延，其不能大于任務的時延要求；C4為完成視頻內容理解任務計算卸載的總能耗，其不能大于任務卸載過程中的能耗限制；C5為車輛傳輸丟包率，其不能大于最大丟包率λmax。

上述所提計算卸載決策優(yōu)化問題包含了整數(shù)類型的參數(shù)，因此，可以將該問題轉化為混合整數(shù)線性規(guī)劃問題。該問題的最優(yōu)解需要涉及海量的狀態(tài)決策，MCTS 作為強化學習的一種算法，可以對多種狀態(tài)下的動作進行選擇，當系統(tǒng)的狀態(tài)數(shù)和動作數(shù)較多時，能夠高效地進行決策，因此，本文選用改進的MCTS 算法作為計算卸載決策算法。

3 基于改進MCTS 的計算卸載決策算法

相較于目前的強化學習方法，基于MCTS 的計算卸載決策算法在狀態(tài)選擇時更高效，且本文在MCTS 中引入上限置信區(qū)間（UCB）算法［21］，其可以在探索-利用（exploration-exploitation）之間取得平衡，是一種較為成功的策略學習方法。目前的強化學習算法需要進行大量的訓練才可以得到較優(yōu)的決策，并且需要大量的采樣，而基于MCTS 的算法可以高效地進行相應的決策。

本文基于MCTS 的計算卸載決策算法包括4 個過程，即選擇、擴展、評估、反向傳播：首先，構建MCTS 決策搜索樹，以環(huán)境狀態(tài)Q0作為MCTS 的輸入，Q0包含計算卸載任務集合T與邊緣服務器資源占用情況集合E，T包括視頻內容理解任務幀率、數(shù)據(jù)量大小以及處理時延，E包括邊緣服務器的可用計算資源量以及當前的可用線程總數(shù)；然后，重復執(zhí)行展開和選擇過程，直到搜索到達葉節(jié)點，從根節(jié)點到葉節(jié)點所選擇的路徑代表N個視頻內容理解任務的卸載決策A0：N-1，其中，葉節(jié)點是尚未搜索的邊緣服務器節(jié)點；接著，車輛根據(jù)卸載決策A0：N-1對視頻內容分析任務進行卸載，當所有任務完成時，將計算卸載效用值作為獎勵信號γ返回到MCTS 模塊，以測量動作的執(zhí)行情況［22］；最后，MCTS 備份獎勵γ以更新搜索策略。MCTS 可以構建具有一定數(shù)量且迭代的完整蒙特卡洛樹，經過一定次數(shù)的迭代，從中可以提取最佳策略作為最佳決策動作A0：N-1。基于MCTS的計算卸載決策算法流程如圖2 所示。

圖2 基于MCTS 的計算卸載決策算法流程Fig.2 Procedure of MCTS based computing offloading decision algorithm

基于MCTS 的計算卸載決策算法描述如算法1所示。

算法1基于MCTS 的計算卸載決策算法

首先，在Search 函數(shù)中，將MCTS 節(jié)點表示為v，將節(jié)點狀態(tài)表示為s。v0為初始系統(tǒng)狀態(tài)，表示節(jié)點v的內部信息；環(huán)境狀態(tài)S0是MCTS 的輸入，定義為S0=(T，E)。利 用DNN 生成的先驗概率為通過UpdatePolicy 函數(shù)充分展開節(jié)點v0的子節(jié)點隨后，再次調用UpdatePolicy 函數(shù)，根據(jù)式（12）從節(jié)點及其子節(jié)點中選擇最佳卸載節(jié)點v1：

其中：M(vi)是節(jié)點vi的累積獎勵值；N(vi)表示節(jié)點vi的訪問次數(shù)；C為比例因子，通過改變C的值，可以改變搜索和決策MCTS 的可能性。UpdatePolicy（vi，Mi）函數(shù)將狀態(tài)變化擴展到所有的可用節(jié)點，生成一組動作A和相應的評估γ，通過對評估值進行評價可以選擇相應的動作，MCTS 通過更新評估的累積獎勵M(v) 和訪問次數(shù)N(v) 來更新搜索策略。使用UpdatePolicy（vi，Mi）函數(shù)，利用由DNN 生成的先驗概率p(v0|s0)在節(jié)點v0的子節(jié)點中選擇最優(yōu)的節(jié)點vi進行擴展。通過Backup 函數(shù)中的回溯，對M(vi)和N(vi)進行更新：

其中：γ表示選擇節(jié)點vi作為計算卸載決策目標的效用值。在效用最大化后，可以從樹中得到狀態(tài)空間的最佳動作A0：N-1以及空間的概率分布π=。其中，是任務n狀態(tài)Sn的一組可行動作。為了加快MCTS 的收斂速度，本文選用DNN 對先驗概率進行預訓練［23］，其中，位于第i層的神經網(wǎng)絡節(jié)點vi=v(n·q+m)表示任務Tn在MCTS 中的第m個子決策，任務Tn對應的An={an，m}。邊緣服務器狀態(tài)變量Sl=(Tn，En)存儲在MCTS 樹的si=s(n·q+m)，因此，所有子節(jié)點的先驗概率為：

DNN 以服務器狀態(tài)以及卸載決策為輸入，輸出每個狀態(tài)對應的子動作的先驗概率。輸入層包含2 個神經元，輸出層包含n個神經元，隱藏層包含若干個神經元。一個輸入層、l個共享隱藏層以及q個子層來生成每個子動作的可能性。每一個子層由m個子隱藏層及其對應的輸出層組成。

其中：ξ‖θ‖2為避免過度學習而采用的正則化。

4 性能仿真

本文通過Matlab 工具來構建車聯(lián)網(wǎng)環(huán)境下計算卸載系統(tǒng)的仿真環(huán)境，并驗證基于改進MCTS 的計算卸載決策算法的性能。

4.1 仿真環(huán)境

為了模擬車聯(lián)網(wǎng)環(huán)境下的計算卸載場景，本文設定RSU 的覆蓋范圍為r=1000 m，車輛的行駛速度設定為v=40 km/h 且勻速運動，任意車輛i產生的視頻內容理解任務Ni不超過30 個，每個視頻內容理解任務包含300～1 000 幀的視頻，每個任務的時延要求為ti∈(100 ms，2 000 ms)。

在通信模型中，車輛發(fā)射功率為26 dBm，近地參考距離為d=5 m，路徑損失指數(shù)δ=4。車聯(lián)網(wǎng)無線通信的小尺度衰落模型借鑒文獻［25］所提的零均值復高斯隨機信道，其中，高斯白噪聲功率為-174 dBm。車聯(lián)網(wǎng)計算卸載場景下系統(tǒng)的總帶寬為B=10 MHz，丟包率上限λmax為0.01，傳輸?shù)哪芎南拗艵max為10 kJ/ms。在計算模型中，每比特視頻內容理解任務所需的計算次數(shù)為1 000，每個RSU 和車輛搭載多核CPU 處理器，假設單核CPU 的頻率為2.5 GHz［26］，計算調頻因子ξ=10-28［27］，各服務器的并發(fā)線程數(shù)分別為1、2、5、10，各服務器的計算資源占用情況隨機設置，其中，系統(tǒng)的總任務量為10～100，每個任務的數(shù)據(jù)計算量平均為Ti=3 Mb。

4.2 視頻預處理與計算卸載決策性能分析

首先對視頻進行預處理，采用的仿真視頻為加州理工大學行人數(shù)據(jù)集（Caltech Pedestrian Dataset）［28］，通過對不同視頻段中2 幀圖像進行差分，得到圖像的平均像素強度，以衡量2 幀圖像的變化大小。隨著視頻幀的不斷變化，幀間差值發(fā)生改變，在選取關鍵幀時，應當使得關鍵幀的選取具有代表性，不過分密集和稀疏，并將關鍵幀的幀率作為衡量視頻內容信息重要程度的指標。表1 所示為節(jié)選出的視頻片段的預處理結果。

表1 視頻預處理結果Table 1 Video preprocessing results

本次實驗選用行人目標識別場景，通過行人識別數(shù)量來衡量視頻內容理解的精度。

圖3 所示為時延約束下各指導方式的視頻內容理解任務計算卸載平均效用對比。從圖3 可以看出：隨著時延約束的提高，3 種指導方式下計算卸載平均效用均不斷提高，而QoC 指導方式下的系統(tǒng)總效用相較于QoE［29］與QoS［30］更 高，在時延約束為700 ms 時約為37%。

圖3 時延約束下不同指導方式的系統(tǒng)效用對比Fig.3 Comparison of system effectiveness of different guidance modes under time delay constraints

圖4 所示為不同時延約束下各指導方式的視頻內容理解任務平均精度對比。從圖4 可以看出，隨著時延約束的提高，視頻內容理解平均精度不斷提高，在時延約束為700 ms 時，相較于QoS 和QoE 這2 種計算卸載指導方式，QoC 指導方式下的視頻內容理解精度分別約提升5%和15%。

圖4 時延約束下不同指導方式的視頻內容理解精度對比Fig.4 Comparison of video content understanding accuracy of different guidance modes under time delay constraints

從圖5 可以看出：基于Q-learning 的計算卸載決策算法［7］在迭代50 次時收斂，而本文算法在迭代40 次時收斂，且本文算法的最終系統(tǒng)效用高于基于Q-learning 的算法，提升約10%；本文算法的收斂速度明顯大于基于模擬退火的算法，收斂速度提升約60%。因此，本文基于改進MCTS 的計算卸載決策算法具有較好的收斂性并且在收斂后任務平均效用更高。

圖5 不同計算卸載決策算法的系統(tǒng)效用與收斂性對比Fig.5 Comparison of system utility and convergence of different computing offloading decision algorithms

圖6 所示為任務數(shù)對視頻內容理解任務能耗的影響情況，從圖6 可以看出：隨著任務數(shù)的不斷增加，基于Q-learning 的算法與本文算法的系統(tǒng)能耗均逐漸提升，在達到一定的任務數(shù)后，能耗增加趨于平緩，并且隨著任務數(shù)的提升，由于計算資源的限制，能耗再次快速上升，在任務數(shù)大于120 后，本文算法的能耗低于基于Q-learning 的算法，在任務數(shù)為200時，降低約16%；基于模擬退火算法的計算卸載能耗隨著任務數(shù)的提升而逐漸平穩(wěn)上升，其能耗明顯高于本文算法。

圖6 任務數(shù)對視頻內容理解任務能耗的影響Fig.6 Effect of task number on energy consumption of video content understanding tasks

圖7 所示為任務數(shù)對視頻內容理解任務系統(tǒng)效用的影響情況，其中，MEC 服務器的數(shù)量N為10，每個任務的任務量大小Bi為3 Mb。從圖7 可以看出：隨著任務數(shù)的增加，本文算法的卸載策略系統(tǒng)效用的下降幅度遠小于基于Q-learning 的算法以及傳統(tǒng)搜索算法；基于Q-learning 的卸載策略在任務數(shù)小于100 時與本文算法的系統(tǒng)效用相差不大，但當任務數(shù)大于160 后，基于Q-learning 的算法系統(tǒng)效用迅速下降，遠低于本文算法；基于模擬退火的傳統(tǒng)搜索算法的卸載決策系統(tǒng)效用則一直低于本文算法。

圖7 任務數(shù)對視頻內容理解任務系統(tǒng)效用的影響Fig.7 Effect of task number on system utility of video content understanding tasks

5 結束語

本文分析不同視頻內容理解任務的優(yōu)先級，根據(jù)任務內容以及服務器狀態(tài)構建視頻內容理解任務的效用函數(shù)，在此基礎上，設計一種基于蒙特卡洛樹搜索的計算卸載決策算法。實驗結果表明，該算法能夠在有限次的迭代后收斂，并在時延與能耗的約束下獲得較優(yōu)的系統(tǒng)效用，符合目前車聯(lián)網(wǎng)場景對視頻內容理解任務精度的需求。下一步將考慮通信資源的動態(tài)變化以及車聯(lián)網(wǎng)場景下卸載方式的變化情況，采用DDPG等更適用于動態(tài)變化環(huán)境的深度強化學習方法，通過聯(lián)合優(yōu)化通信資源與緩存資源，以設計性能更優(yōu)的視頻內容理解任務計算卸載決策算法。