基于車輛邊緣計算的用戶能耗最小化資源分配研究

李世超，王秋云，寇為剛，賀國慶

(1.桂林電子科技大學信息與通信學院 廣西 桂林 541004；2.甘肅政法大學公安技術學院 蘭州 730070)

隨著無線通信與物聯網技術的發展，車輛因特網(Internet of vehicles, IoV)應運而生，IoV 可以為旅客提供許多新的服務，如語音識別、在線視頻以及虛擬現實游戲等[1-2]。這些新的服務需要消耗較多的計算資源并且具有嚴格的時延約束，但是用戶的終端設備往往計算能力有限，無法處理這些應用。為了解決車載用戶終端計算能力不足的問題，有學者提出了車輛邊緣計算(vehicular edge computing,VEC)，它可以根據業務的需求，靈活地分配資源。

VEC 在提高系統資源利用率的同時，還能夠有效提升計算密集業務的用戶體驗。但是與傳統的云服務器相比，當考慮到經濟成本以及部署的靈活性時，VEC 服務器的計算能力往往有限[3]。為了進一步提高系統的資源利用率需要一種新的動態資源分配策略。

目前，針對VEC 的資源管理主要有以下研究。為了同時最小化車輛和VEC 服務器的消耗，文獻[4]在車輛側提出了一種聯合任務遷移和本地計算資源分配策略。同時在VEC 側提出了一種聯合無線與計算資源分配策略。在智慧城市的車聯網中，為了支持更多的時延敏感業務，同時減少網絡的負載，文獻[5]提出了一種聯合無線與計算資源分配方案。文獻[6]在車聯網中研究了高能效的任務遷移問題，提出了一種基于交替方向乘子法的低復雜度分布式算法。以上所有研究都假設任務在遷移過程中信道狀態是固定不變的。但在實際中，任務的遷移時延與車輛信道的相干時間并不在同一個時間級別。例如，當車輛速度為100 km/h，載頻為1.8 GHz 時，信道的相干時間約為2.5 ms，而任務的遷移時延可達到數十毫秒至數百毫秒，對于某些時延不敏感的業務，任務的遷移時延可達到數秒。如果不考慮信道的快速時變特性，會使得資源利用率降低，任務的遷移時延也無法得到滿足[3-7]。因此，在VEC 系統中進行資源分配時需要考慮信道的時變特性。

信道的快速時變特性是車聯網的一個重要特點，本文主要研究在VEC 系統中，信道的快速時變特性對資源分配策略的影響。構建一個在系統計算資源和信道容量有限以及任務QoS 約束下的車載用戶終端能耗最小化問題。由于車聯網場景中多是視距場景，并且車輛的位置可以預測，因此可以利用路徑損耗信息替代信道狀態信息(channel state information, CSI)。通過利用李雅普諾夫隨機優化理論，可以將原問題轉化為兩個子問題。由于計算資源分配子問題是一個單變量的優化問題，因此很容易求解。而無線資源分配子問題是一個混合整數規劃問題，通過將該問題轉換為單變量的優化問題進行求解?；谝陨蟽蓚€子問題的結果，提出一種聯合無線與計算資源分配(joint radio and computation resource allocation, JRCRA)算法，并通過仿真結果驗證JRCRA 算法的有效性。

本文的主要貢獻包括以下3 點：

1) 本文在考慮車輛快速時變信道的特性下，提出一種聯合無線與計算資源分配算法來減少車載用戶的能量消耗。仿真結果顯示，當數據包平均到達速率從20 個/時隙增加到40 個/時隙時，提出的算法性能相較于傳統的貪婪算法能耗降低了48.85%。

2) 利用李雅普諾夫隨機優化理論，通過調整控制參數V，可以實現車載用戶能量消耗與任務處理時延的均衡。

3) 針對分解后的無線資源分配子問題，提出了一種有效算法來求解該混合整數規劃問題。

1 系統模型

本節首先給出VEC 的系統模型，接著給出任務的傳輸隊列和計算隊列。

1.1 網絡模型

式中，α為路徑損耗因子。由于小區的信道變化是可預測的，并且每個小區內的信道變化是對稱的，因此本文只需要研究半個小區內的資源分配策略[8]。

定義 P(t)為車載用戶終端在時刻的發射功率。此時，車輛與RSU 之間的無線傳輸速率為：

式中， W是系統帶寬。假設數據包的大小相同，均為 L比特，則鏈路容量可以定義為能夠傳輸的最大數據包數量為

1.2 動態隊列模型

在本文中，用兩類隊列模型來表示任務由車載用戶終端到VEC 服務器的處理過程。如圖1 所示，任務的處理過程被分為兩個階段，一是任務的傳輸階段，二是任務在VEC 服務器中的計算階段。這兩個階段可以分別被建模為任務的傳輸隊列和計算隊列。

對于任務傳輸隊列，車載用戶終端將K 個獨立的任務遷移至VEC 服務器。定義任務集合為K={1,2,···,K}。 定 義 H( t)=[H1(t),H2(t),···,Hk(t)]為傳輸隊列積壓向量，其中 Hk(t)為 第 k 個任務在t時刻的傳輸隊列積壓。

定 義 A( t)=[A1(t),A2(t),···,Ak(t)]為 任 務 所 產 生的數據包向量，其中 Ak(t)為 第 k 個任務在t時刻所產生的數據包。任務數據包的產生速度滿足均值為λk=E[Ak(t)]的 獨立同分布過程，并且第 k個任務在每一時隙所能產生的最大數據包為 Bk。定義ck(t)∈[0,Hk(t)]為 第 k 個任務在t時刻所遷移的數據包。因此，第k 個任務的傳輸隊列可以表示為：

為了保證任務的QoS 需求，從長期平均的角度來看，平均的遷移數據包不應小于 qk。計算。定義 Q( t)=[Q1(t),Q2(t),···,Qk(t)]為VEC 服務器的計算隊列積壓向量，其中 Qk(t)為 第 k個任務在t時刻的計算隊列積壓。定義 μk( t)∈[0,Qk(t)]為 第 k個任務在t時刻所計算的數據包。因此，第k 個任務的計算隊列可以表示為：

對于任務計算隊列，任務由VEC 服務器進行

2 問題建模與重構

本節首先在VEC 系統中構造一個聯合無線與計算資源分配問題，該問題是在保證任務QoS 要求下實現車載用戶終端能耗最小化。然后利用隨機動態優化理論對該問題進行重構。

2.1 隊列穩定與問題建模

為了避免丟包，所有的隊列應該保持穩定。對于任意變量z，定義長期平均期望為：

基于長期時間平均期望，隊列穩定需要滿足如下條件[10]：

基于以上隊列穩定的定義，聯合無線與計算資源分配的問題可以建模為：

式中， μtotal為VEC 服務器的總計算資源。約束式(6b)表示每個任務的QoS 要求；約束式(6c)確保隊列穩定；約束式(6d)為信道容量約束；約束式(6e)為VEC 服務器總計算資源約束；約束式(6f)和式(6g)分別表示遷移數據包和計算數據包約束。由于式(6)是一個非凸問題，難以求解，因此需要對該問題進行重構。

2.2 問題重構

由于式(6)存在時間平均，因此難以求解。本小節采用隨機動態優化理論將約束式(6b)重新構建為單個時間平均的函數[9]。引入虛擬隊列 Zk(t)，可以表示為：

其初始條件為 Zk( 0)=0。 對于虛擬隊列 Zk(t)，ck(t)可以看作是每個虛擬隊列所處理的數據包，qk可 以看作是虛擬隊列 Zk(t)的到達數據包。

基于虛擬隊列 Zk(t)，式(6)可以被重構為：

式(8)仍然難以求解，下一節利用動態隨機優化算法來求解該問題。

3 動態無線與計算資源分配算法

本節利用動態隨機優化理論來求解式(8)。首先，利用李雅普諾夫隨機優化理論將式(8)分解為兩個獨立的子問題。然后通過對兩個子問題進行求解，提出動態無線與計算資源分配算法。

3.1 李雅普諾夫漂移

定義 Z(t)為 虛擬隊列 Zk(t)所 組成的向量。 Θ(t)為虛擬隊列和實際隊列所組成的向量，可以表示為：

二階李雅普諾夫函數可以表示為：

李雅普諾夫漂移可以表示為：

由于 ?(Θ (t))難 以求解，因此下面對 ?(Θ (t))的上界進行分析。

定理 1在t 時刻，對于任意隊列狀態，在任意接入控制與資源分配策略下，Θ (t)應滿足以下不等式：

式中，

相關證明見文獻[11]。

3.2 問題分解

上一小節得到了李雅普諾夫漂移 ?(Θ (t))的上界。本小節利用漂移懲罰因子理論來最小化“漂移懲罰因子”，其表達式為：

根據李雅普諾夫隨機優化理論，問題目標是最小化李雅普諾夫漂移 ?(Θ (t))，可以通過在每一時隙最小化的右式來求得。右式可被分解為一系列子問題，可以在每一時隙利用實際隊列與虛擬隊列進行求解。對于式(15)，可以被分解為兩個獨立的子問題。

從式(15)中分解出 ck(t) 和 P(t)，可以得到無線資源分配子問題：

同理，從式(15)中分解出 μk(t)，可以得到計算資源分配子問題：

3.3 計算資源分配

3.4 無線資源分配

無線資源分配子問題可表示為：

由于 ck(t)是一個整數變量，式(19)是一個混合整數規劃問題，因此難以求解。接下來通過將式(19)轉換為一個單變量問題，提出一種無線資源分配策略。為了簡化方便，下面省略時間標號t。

從式(19a)中可以看出，如果 Hk+Zk?Qk，那么問題的最優解是 ck= 0， P= 0。

當 Hk+Zk>Qk時，首先忽略C 的整數特性，當取得最優的無線資源分配策略時，約束式(19b)可以寫為：

式(20)成立是因為對于任意的可行解 ck都可以通過減少C 和P 在滿足約束式(19b)、式(19c)的情況下進一步增大。對于式(20)，功率消耗可以表示為：

約束式(19c)可以進一步寫為：

其次，考慮C 的整數特性，無線資源分配的式(19)可以重新被構建為一個單變量優化問題：

式中，

為了求解式(23)，首先給出以下定理：

定理 2函數在 [0, f(K)]范圍內是關于C 的單峰函數。

基于定理2，提出一種無線資源分配算法如算法1 所示。

算法1 無線資源分配算法

1) 初始化 ck= 0；( 0)=0 ；C=0

2) 將任務按照 Hk+Zk?Qk降序排列，得到排列集合{k1,k2,···,kK}

3) for n=1 to K do

5) C:=C+1

then

9) 跳至步驟13)

10) end if

11) end for

12) end for

13) 通過式(21)，得到 P 和ck

3.5 聯合無線與計算資源分配算法

基于以上兩個獨立的子問題，本小節提出JRCRA算法如算法2 所示。首先初始化所有的系統參數，在每一時隙根據式(18)和算法1 求解計算資源分配和無線資源分配兩個子問題。在每一時隙結束時，隊列向量 Θ( t+1)通過式(3)，式(4)和式(7)來進行更新。在每一時隙重復該算法。

算法2 JRCRA 算法

1) 初始化系統參數；

2) while t ∈ [0,T] do

3) for k=1 to K do

4) 通過式(18)得到μk(t)

5) 通過求解子式(19)得到 ck(t) 和P(t)

6) 通過式(3)，式(4)和式(7)更新 Hk(t)，Qk(t)和 Zk(t)

7) end for

8) end while

4 仿真結果與分析

本節驗證提出的JRCRA 算法性能。仿真參數如表1 所示。

圖2 為不同控制參數V 對總平均功率消耗的影響。從該圖中可以看出，總平均功率消耗隨著參數V 的增加而下降，并且當V 足夠大時，會收斂至最優的功率消耗。圖3 為不同控制參數V 對總平均隊列積壓的影響。從該圖中可以看出，總平均隊列積壓隨著V 線性增加。從圖2 和圖3 可以看出，總平均功率消耗和隊列積壓可以通過調整控制參數V 以實現均衡。另外，隨著數據包到達速度的增加，平均功率消耗和隊列積壓都有明顯的增加。

表1 仿真參數

為了證明提出的JRCRA 算法的有效性，本文將JRCRA 算法與貪婪算法進行比較。貪婪算法是按順序一個接一個的處理任務，只有處理完一個任務才會處理下一個任務。

圖4 為不同算法下數據包平均到達速率對平均功率消耗的影響。所有的任務QoS 要求相同并且控制參數V 為200。從該圖中可以看出當數據包平均到達速率增大時，貪婪算法所消耗的功率大于JRCRA 算法所消耗的功率。當數據包平均到達速率從20 個/時隙增加到40 個/時隙時，提出的JRCRA算法相較于傳統的貪婪算法能耗降低了48.85%。這是因為對于貪婪算法來說，如果一個任務要被處理，那么必須要等該任務之前的所有任務都已處理完畢。這樣可能會導致在信道條件較差的情況下，有大量的數據包需要被遷移至服務器。為了確保任務的QoS 需求，用戶則需要增加發射功率。

5 結 束 語

本文在VEC 系統中研究了車輛快速時變信道對資源分配策略的影響。首先構建了一個聯合無線與計算資源分配使得車載用戶終端能量消耗最小化的問題，并利用車輛信道的可預測特性和李雅普諾夫隨機優化理論，將原問題分解為兩個子問題。然后通過對兩個子問題進行求解，提出了JRCRA 算法。最后仿真結果顯示，當數據包平均到達速率從20 個/時隙增加到40 個/時隙時，此算法性能相較于傳統的貪婪算法能耗降低了48.85%。

本文僅研究了一個VEC 服務器的遷移與資源分配問題。后續可以接著從多VEC 服務器選擇方面進行研究。當網絡中存在大量VEC 服務器時，車載用戶可以通過選擇計算資源更為豐富的VEC 服務器來進行遷移計算，進一步降低時延，減少能耗。

本文的研究還得到蘭州市科技局項目(2018-3-9)和甘肅政法學院校級科研項目(GSZF2018XQNLW10,GSZF2017XQNLW02)的支持，在此表示感謝！