張 俊， 王 楊， 張聰聰， 許閃閃

(蕪湖職業(yè)技術學院 網絡工程學院,安徽 蕪湖 241003；2.安徽師范大學 計算機與信息學院，安徽 蕪湖 241003)

引 言

隨著通信和計算技術的迅猛發(fā)展，新興的5G應用程序(例如，增強現(xiàn)實、自動駕駛等)不僅給車輛終端的處理能力帶來了巨大壓力，又給無線接入網帶來了很大的負擔。針對車輛終端處理能力不足的問題，采用車載邊緣計算模式是一種有效的解決方案。通常情況下，主要有兩種車載邊緣計算的解決思路：廣泛部署輕量級的服務器和挖掘附近車輛未充分利用的資源。第一種方案需要大量的資金投入，而且在非高峰時期會存在資源過剩的情況。因此，該方案面臨的問題是如何尋求適中的成本來調節(jié)不斷增長的任務需求。第二種方案不需要部署額外的服務器，利用附近的車輛提供大量的計算資源來緩解高峰時段的網絡擁塞。未來的智能汽車將配備更強大的CPU、更大容量的數(shù)據(jù)存儲單元和更先進的通信技術，以滿足用戶更高的需求。這意味著，第二種方法更加容易實施，任務不需要經過基站，進而減少傳輸時延。

盡管車載邊緣計算(Vehicle Edge Computing，VEC)具有上述優(yōu)勢，大面積部署仍然面臨著關鍵的挑戰(zhàn)：(1)缺乏激勵機制來刺激附近車輛提供有效的資源。自私理性的車輛如果沒有收益一般不會提供服務資源，另外，基站無法獲取車輛的私有信息。因此，在信息不對稱的情形下，建立一種有效優(yōu)化服務提供商的機制尤為重要。(2)缺乏低復雜度的任務卸載機制。每輛車都是獨立的實體，只有對所有的車輛進行合理地分配，才能最小化網絡總時延，達到更為理想的執(zhí)行效果。

這些挑戰(zhàn)促使我們尋找一種合適的博弈策略來鼓勵車輛參與任務卸載。在VEC執(zhí)行任務卸載中，服務提供者和請求者都參與其中，通過合理分配自身的資源，實現(xiàn)系統(tǒng)效用最大化。若參與者沒有單方面偏離當前策略，則稱這種狀態(tài)為納什均衡。因此，通過尋找任務卸載博弈的納什均衡來確定最優(yōu)定價的卸載策略。

在所有的博弈模型中，Stackelberg博弈被廣泛用于解決定價問題。Stackelberg博弈的基本策略是領導者有權采取第一個行動，追隨者觀察領導者的行動，并據(jù)此做出自己的行動。利用Stackelberg博弈的主要優(yōu)勢如下：(1)能夠準確地描述了服務提供者和請求者之間的交互；(2)領導者與跟隨者的關系符合服務提供者與請求者的不平等地位；(3)如果Stackelberg均衡存在，則它可以為服務提供者和請求者提供最優(yōu)價格和卸載比例。

因此，本文提出了一種基于stackelberg博弈的任務卸載策略，該策略能夠獲得最優(yōu)價格和卸載比例，以便服務提供者向請求者提供服務。Stackelberg博弈用于服務提供者和請求者之間的信息交互，接著推導出納什均衡狀態(tài)，并提出了一種最優(yōu)定價的任務卸載算法。大量的仿真實驗結果表明，該算法能夠有效地減少任務的總時延，同時最大限度地提高整體效用。

1 相關工作

隨著無線通信、人工智能和云計算技術的飛速發(fā)展，許多學者認為智能社區(qū)汽車(the Intelligent Community Vehicle,ICV)是傳統(tǒng)車輛的未來發(fā)展趨勢。ICV配備了先進的車載傳感器、控制器、執(zhí)行器等設備，可以實現(xiàn)V2X[1]的智能信息共享。利用IoV中的通信技術將任務傳輸?shù)骄哂胸S富計算資源的其他基礎結構是實現(xiàn)自動駕駛的一個關鍵步驟[2]。

下面從優(yōu)化目標的角度將IoV的任務卸載問題大致分為四類。

⑴以降低時延為目標的任務卸載。在[3]中提出了一種綜合優(yōu)化算法的資源分配模型，該模型考慮邊緣服務器的計算能力在不同時間段發(fā)生變化，實現(xiàn)車輛總任務卸載時延最小。在[4]中主要考慮車輛之間的任務卸載，提出了基于在線學習的分布式計算卸載算法，以達到對平均卸載時延的最小化。在[5]中根據(jù)最優(yōu)節(jié)點選取理論設計了一種任務卸載方案，實現(xiàn)了任務卸載全過程中耗時更少。在[6]中提出了一種啟發(fā)式搜索算法，通過優(yōu)化候選對象選擇、轉移排序和任務分配來解決任務卸載問題，權衡了時延和可靠性。

⑵以降低能耗為目標的卸載決策。在[7]中提出了一種車載終端設備的節(jié)能VEC框架，并開發(fā)了基于ADMM的節(jié)能資源配置算法。在[8]中將卸載問題表述為NP難問題，提出了一種啟發(fā)式算法來逐步解決卸載問題，設計了一種預測性組合傳動模式，并為計算設施建立深度學習模型，以達到車輛能耗最小化。在[9]中提出了一種基于共識ADMM的分布式任務卸載方案，將具有耦合變量的原始問題轉換為可分離目標的等效一般共識問題，從而降低終端車輛的能耗。

⑶以權衡能耗和時延為目標的卸載決策。在[10]中，提出了基于半馬爾可夫決策的集中式任務分配算法，在綜合考慮任務時延和移動設備能耗的前提下，使系統(tǒng)平均成本最小化。在[11]中提出了一種混合NOMA的第三種策略，通過應用幾何規(guī)劃(GP)獲得了最優(yōu)時間和功率分配的閉式表達式。在[12]中提出了一種具有混合能源供應的F-RAN的時延感知能效計算卸載方案，利用綠色電源來支持從移動用戶的計算卸載，在延遲和網絡約束下以最大程度地減少不可再生電網的能耗。

⑷以權衡時延和成本為目標的卸載決策。在[13]和[14]中，提出了兩種基于云的車輛邊緣計算卸載框架，分別采用運籌學理論和Stackelberg博弈論方法，使MEC服務器和車輛的效益最大化。在[15]中提出了一種基于凸凹過程的合同優(yōu)化算法以激勵服務車輛提供服務，設計了基于定價的任務卸載機制，在信息不對稱的情況下實現(xiàn)服務提供商的期望效用最大化。在[16]中引入附近備份服務器來補充資源，提出Stackelberg博弈的卸載方案以實現(xiàn)改善服務提供商效用的目標。在[17]中，考慮計算任務的時間消耗和車輛的移動性，提出一種預測組合模式的卸載方案，減少計算卸載的停留時延和傳輸成本。

然而，較少有論文考慮到車輛的移動性。事實上，信道傳輸?shù)臄?shù)據(jù)速率和有效的通信時間都受到數(shù)據(jù)傳輸距離的影響。在本文中，針對VEC系統(tǒng)的優(yōu)點，提出任務卸載方案，旨在最小化任務完成的平均卸載時延，而主要考慮任務完成的時延和車輛的移動性。

2 系統(tǒng)模型

2.1 VEC模型

服務車SV(Service Vehicle)：SV是擁有空閑計算資源的車輛，可以幫助請求車執(zhí)行任務。請求車表示為SV={p,εsr,fs,vs,Ps}，其中p表示SV提供的任務卸載成本，εsr表示通信成本，fs表示SV的計算強度，vs和Ps分別表示SV的速度和瞬時位置。

請求車RV(Request Vehicle)：RV是需要卸載任務的車輛，表示為RV={λ,Dt,fr,vr,Pr}，其中λ表示卸載百分比，Dt表示任務數(shù)據(jù)的大小，fr表示RV的計算強度，vr表示RV的速度，Pr表示RV的瞬時位置。

如圖1所示，我們設想了一個VEC網絡場景，蜂窩網絡的基站均部署在路邊，通過電線連接到互聯(lián)網上的服務器。所有車輛都配備有兩個無線接口：蜂窩網絡接口和IEEE802.11p網絡接口。因此，車輛可以使用4G協(xié)議連接到蜂窩網絡，也可以使用IEEE 802.11p協(xié)議互相通信。SDN控制器用于管理任務的卸載，也可以與蜂窩網絡、車輛和內容服務器通信。SDN控制器充當車輛和內容服務器之間的中介。

如果RV想卸載內容，需要通過蜂窩網絡向SDN控制器發(fā)送請求。然后，SDN控制器發(fā)回一組SV和關于請求內容的信息。與RV行駛方向相同的臨近車輛若具有所請求任務的副本，則這些車輛是SV。同時，SDN控制器向所有SV發(fā)送一條消息，請他們參加博弈。接下來，SV將自己的信息發(fā)送給RV。最后，RV根據(jù)最低價格選擇最終的SV進行任務卸載。如果所有SV提供的卸載價格過高，客戶將直接在本地執(zhí)行。在考慮的時間段內，車輛的身份是穩(wěn)定的。提出的基本假設如下:

1)在卸載過程中每輛車的速度和方向保持不變。

2)在通信范圍內每個RV只能將任務卸載給一個SV，每個SV可以向多個RV提供服務。

3)僅考慮V2V的任務卸載，如果RV僅有一個通信鏈接，RV的任務只能被卸載到它的一跳鄰居。

2.2 系統(tǒng)模型

(1)

每一對RV和SV只有在通信范圍R內才有機會進行通信，即RV和SV之間的距離(需要滿足不等式)||PRVi(t)-PSVj(t)||R。假設RVi在t0=0時刻有一個計算密集型任務，第Δt時刻的RVi與SVj之間的歐式距離為

(2)

有幾項工作表明停留時延服從伽馬分布[18]。通常來說,伽馬分布的概率密度函數(shù)Ga(△t,dij(△t),θ)和伽馬函數(shù)Γ(dij(△t))分別表示為

(3)

(4)

其中，θ是比例參數(shù)，其值是由道路段的實際情況決定的[19]。SVj的停留時延為

(5)

2.2.2 計算模型 任務完成的時間包括三個過程所消耗的時間:1)任務內容的交付;2)任務執(zhí)行;3)任務結果反饋?？紤]計算密集型任務，如果RVi決定任務在本地執(zhí)行的時間為

(6)

(7)

由于RV和SV都是移動的車輛，卸載任務的總計算時間應該小于RV和SV之間的相互接觸時間,即

(8)

2.2.3 信任模型 在具有多個SV的系統(tǒng)中，一些SV很受歡迎，RV想要卸載任務給它們，而其他不受歡迎的SV，可能少數(shù)RV對它們感興趣。我們根據(jù)歷史信任值和現(xiàn)有觀察值對SV未來行為進行預測，由RV確定是否將任務卸載給SV。根據(jù)RV對SV的信任分布來建模SV的受歡迎程度。而信任值是兩個相鄰車輛直接交互過程中對SV行為的評價值。根據(jù)文獻[20]可知信任關系為

(9)

2.3 Stackelberg模型

2.3.1 效用函數(shù) RV的效用函數(shù)是通過卸載節(jié)省的時間與獲取數(shù)據(jù)成本之間的差值。RV的效用函數(shù)定義為

(10)

其中，α1+α2=1,0≤α1≤1和0≤α2≤1，α1和α2是權重。

SV的策略是通過定價來最大化收益。SV的效用函數(shù)包含三部分內容：1)輔助RV執(zhí)行任務獲得的利潤；2)因信任度的提升而獲得的利潤；3)由于任務傳輸而消耗的通信成本。因此，SV的效用函數(shù)可以定義為

(11)

其中，β1+β2=1,0≤β1≤1和0≤β2≤1，β1和β2是權重。

3 基于Stackelberg博弈的任務卸載策略

3.1 問題描述

將RV的任務請求和SV的價格建模為非合作的Stackelberg博弈，SV是領導者，RV是跟隨者。Stackelberg博弈包括兩個階段：在第一階段，每個候選SV都提供成本p；在第二階段，RV根據(jù)價格p確定從每個SV獲取任務的卸載比例λ。 最后，RV選擇提供最低價格p的SV進行任務卸載。在博弈中，每一方都是追求最大效用。因此，任務卸載問題可以表述為：

(12)

s.t.εsrppmax

(13)

其中，pmax表示SV提供的最大價格。

3.2 納什均衡解

(14)

(15)

(16)

ur(λ)對λ求一階導和二階導得到

(17)

(18)

(19)

綜上所述，RV的最優(yōu)策略λ*的表達式為

(20)

(21)

(22)

3.3 算法的設計與實現(xiàn)

設計了一種基于Stackelberg(Stackelberg Game Based Task Offloading Algorithm)博弈的任務卸載算法，用于從SV候選集合中選擇價格最低的SV執(zhí)行任務卸載。RV向SV發(fā)出請求后，查詢是否有車輛提供任務卸載服務。如果有，則執(zhí)行SGTO算法。

SGTO算法的時間復雜度為O(n)。因此，在移動車輛上實現(xiàn)SGTO算法是可行的。此外，要運行算法SGTO，RV必須有SV實時輸入所需數(shù)據(jù)項的信息。有關SV所需數(shù)據(jù)項的信息可以從APP程序和SDN控制器獲得，SDN控制器將有關數(shù)據(jù)項的信息返回給RV。然后，每個SV將自己的信息發(fā)送給RV。

4 仿真實驗分析

4.1 仿真參數(shù)設置

圖2 含有交通信號燈的城市道路仿真場景Fig.2 Urban road simulation scene with traftic lights

采用SUMO來評估基于真實道路的SGTO算法。從OpenStreetMap中提取真實場景的特征信息，并使用JOSM對數(shù)字地圖進行處理。然后將這些數(shù)字地圖數(shù)據(jù)導入SUMO進行處理，其中根據(jù)特定的道路拓撲生成車輛流量。通過對SUMO界面的預先定義，可以在仿真過程中獲得車輛的速度和相應的時間等關鍵參數(shù)。這里考慮的場景是一個有交通信號燈的城市道路，只考慮交通信號燈對車輛行駛速度的影響。我們以安徽省蕪湖市的花津南路(大工山路-文昌西路)作為依據(jù)。其仿真場景為圖2所示。

為了獲得模擬結果，通過Matlab 2016b進行了1000次蒙特卡羅模擬。其參數(shù)設置為表1。

將該算法與文獻中最近提出的兩種方法[21-22]進行比較:

基于梯度迭代(GBI)[21]:該算法用于獲得三方Stackelberg博弈均衡，其中三方為停放車輛、RSU和移動車輛。

先到先得(FCFS)[22]:一個用戶訪問服務車，車輛選擇第一個進行卸載。

5.2 仿真結果分析

圖3描述的是在不同通信成本εsr的條件下，不同效用函數(shù)和計算強度fr的關系。從圖3(a)可以看出，在同一通信成本εsr條件下，隨著計算強度fr的增加，效用函數(shù)ur逐漸減少；這是因為fr的值較小時，RV處理任務需要的時間較長；隨著fr的值逐漸增加，RV處理任務的時間逐漸縮短。同時，在同一計算強度fr的條件下，隨著通信成本εsr的增加，RV的效用函數(shù)ur減少。從圖3(b)可以看出，在同一通信成本εsr條件下，隨著計算強度fr的增加，效用函數(shù)us逐漸減少；這是因計算強度fr增加時，任務卸載給SV的數(shù)據(jù)量減少，從而造成了SV的效用函數(shù)us的減少；而在同一計算強度下，隨著通信成本εsr的增加，效用函數(shù)us逐漸減少。

表1 實驗參數(shù)

圖4描述的是不同算法的效用函數(shù)與計算強度fr的關系。從圖4(a)可以看出，對于FCFS算法，效用函數(shù)ur的值總是為零，這意味著FCFS不能優(yōu)化RV的效用；而且當計算強度fr達到一定的值時，GBI算法的效用函數(shù)ur的值也為零，這說明GBI算法優(yōu)化RV效用的效果受計算強度fr的值影響；同時SGTO算法的效用函數(shù)ur的值也隨著計算強度fr的增大而減小。由圖4(b)可以看出，在同一計算強度fr下，SGTO算法和GBI算法的效用函數(shù)us的值總是小于FCFS算法，這是因為FCFS算法的任務處理時間比較短，不考慮RV的效用函數(shù)；而且當計算強度fr達到一定的值時，GBI算法的效用函數(shù)us的值為零；結合圖4(a)可知，F(xiàn)CFS算法不能同時優(yōu)化兩個效用函數(shù)；而且GBI算法優(yōu)化兩個效用函數(shù)的效果沒有SGTO算法好，GBI算法受計算強度fr的值影響較大。

圖5描述的是不同計算強度fr的效用函數(shù)和通信成本εsr的關系。由圖5(a)可知，在同一通信成本εsr的條件下，計算強度fr越大，效用函數(shù)ur的值反而越小，且在同一計算強度fr的條件下，隨著通信成本εsr的增加，效用函數(shù)ur逐漸降低。這是因為通信成本的增加，使得需要支付的通信成本更大。從圖5(b)可以看出，在同一計算強度fr的條件下，隨著通信成本εsr的增加，SV效用函數(shù)us逐漸減少。且在同一通信成本εsr的條件下，隨著計算強度fr的增加，效用函數(shù)us也會減少。

圖6描述的是不同算法的效用函數(shù)與通信成本εsr的關系。從圖6(a)可以看出，對于FCFS算法，不管通信成本εsr的值為多少，效用函數(shù)ur的值總是趨近于零；而當通信成本us達到一定的值時，GBI算法的效用函數(shù)ur的值也為零；同時SGTO算法的效用函數(shù)ur的值也隨著通信成本εsr的增大而減?。坏窃谕煌ㄐ懦杀睛舠r條件下，SGTO算法的效用函數(shù)ur的值總是大于FCFS算法和GBI算法的值。由圖6(b)可以看出，SGTO算法和GBI算法的效用函數(shù)隨通信成本εsr的變化幅度不大，而FCFS算法的效用函數(shù)us雖然值較大，但RV的參與度不高，會使得SV的收益不佳。

圖7描述的是不同通信成本εsr的卸載價格p和計算強度fr的關系。從圖7(a)可以看出，在同一通信成本εsr下，隨著計算強度fr的增加，任務卸載的價格p逐漸降低。這是因為隨著計算強度fr的增加，RV出于經濟考慮會降低任務卸載率，進一步影響到任務卸載的購買性能的降低。因此，SV會做出降低價格的措施應對這一變化。從圖7(b)可以看出，在同一通信成本εsr下，隨著計算強度fr的增加，任務卸載節(jié)省的時間逐漸減少。這是因為任務在RV上執(zhí)行的時間隨著計算強度fr的增加而減少。

圖8描述的是不同算法的卸載價格p和計算強度fr的關系。從圖8(a)可以看出，算法SGTO相對于GBI和FCFS算法，任務卸載的成本是最低的。在仿真中，任務卸載的成本SV選擇最大值pmax。從圖8(b)可以看出，SGTO算法比GBI算法節(jié)省的時間更多。這是因為SGTO算法可以產生比GBI更好的優(yōu)化結果。

(a)效用函數(shù)ur與計算強度fr的關系 (b)效用函數(shù)us與計算強度fr的關系圖3 不同通信成本εsr的效用函數(shù)和計算強度fr的關系Fig.3 The relationship between the caculated strength of εsr and fr

(a) 效用函數(shù)ur與計算強度fr的關系 (b)效用函數(shù)us與計算強度fr的關系圖4 不同算法的效用函數(shù)與計算強度fr的關系Fig.4 The relationship between utility function and fr

(a)效用函數(shù)ur與通信成本εsr的關系 (b)效用函數(shù)us與通信成本εsr的關系圖5 不同計算強度fr的效用函數(shù)和通信成本εsr的關系Fig.5 The relationship between fr and εsr

(a)效用函數(shù)ur與通信成本εsr的關系 (b)效用函數(shù)us與通信成本εsr的關系圖6 不同算法的效用函數(shù)和通信成本εsr的關系Fig.6 The relationship utility function and εsr

(a)任務卸載價格與計算強度fr的關系 (b)任務卸載時延與計算強度fr的關系圖7 不同通信成本εsr的卸載價格和計算強度fr的關系Fig.7 The relationship between εsr and fr

(a)任務卸載價格與計算強度fr的關系 (b)任務卸載時延與計算強度fr的關系圖8 不同算法的卸載價格和計算強度fr的關系Fig.8 The relationship between offload price and fr

5 總結

本文提出了一種基于Stackelberg博弈的任務卸載方案。該方案考慮了車輛的移動性和計算成本，建立了RV和SV之間效用最大化的交互模型；并在Stackelberg納什均衡解的基礎上，提出了一種SV收益與RV成本均衡的任務卸載模型，以實現(xiàn)邊緣計算環(huán)境中IoV的任務卸載。實驗結果與已有研究提出的GBI算法和FCFS算法相比較，在不同計算強度和通信成本的條件下，SGTO優(yōu)化效用函數(shù)的效果總是優(yōu)于FCFS、GBI算法，該方案不僅滿足了RV和SV的需求，也有效地降低了任務卸載時延。但是由于實驗參數(shù)設置不具有普遍性和代表性，日后研究中需考慮不同道路狀況和突發(fā)事件下，SGTO算法結果受車輛移動性實時改變的影響。