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

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

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

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

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

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

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

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

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

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

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

1 系統(tǒng)模型

本節(jié)首先給出VEC 的系統(tǒng)模型，接著給出任務的傳輸隊列和計算隊列。

1.1 網(wǎng)絡模型

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

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

式中， W是系統(tǒng)帶寬。假設數(shù)據(jù)包的大小相同，均為 L比特，則鏈路容量可以定義為能夠傳輸?shù)淖畲髷?shù)據(jù)包數(shù)量為

1.2 動態(tài)隊列模型

在本文中，用兩類隊列模型來表示任務由車載用戶終端到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)]為 任 務 所 產(chǎn) 生的數(shù)據(jù)包向量，其中 Ak(t)為 第 k 個任務在t時刻所產(chǎn)生的數(shù)據(jù)包。任務數(shù)據(jù)包的產(chǎn)生速度滿足均值為λk=E[Ak(t)]的 獨立同分布過程，并且第 k個任務在每一時隙所能產(chǎn)生的最大數(shù)據(jù)包為 Bk。定義ck(t)∈[0,Hk(t)]為 第 k 個任務在t時刻所遷移的數(shù)據(jù)包。因此，第k 個任務的傳輸隊列可以表示為：

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

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

2 問題建模與重構(gòu)

本節(jié)首先在VEC 系統(tǒng)中構(gòu)造一個聯(lián)合無線與計算資源分配問題，該問題是在保證任務QoS 要求下實現(xiàn)車載用戶終端能耗最小化。然后利用隨機動態(tài)優(yōu)化理論對該問題進行重構(gòu)。

2.1 隊列穩(wěn)定與問題建模

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

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

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

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

2.2 問題重構(gòu)

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

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

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

式(8)仍然難以求解，下一節(jié)利用動態(tài)隨機優(yōu)化算法來求解該問題。

3 動態(tài)無線與計算資源分配算法

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

3.1 李雅普諾夫漂移

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

二階李雅普諾夫函數(shù)可以表示為：

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

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

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

式中，

相關(guān)證明見文獻[11]。

3.2 問題分解

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

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

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

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

3.3 計算資源分配

3.4 無線資源分配

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

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

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

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

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

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

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

式中，

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

定理 2函數(shù)在 [0, f(K)]范圍內(nèi)是關(guān)于C 的單峰函數(shù)。

基于定理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 聯(lián)合無線與計算資源分配算法

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

算法2 JRCRA 算法

1) 初始化系統(tǒng)參數(shù)；

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 仿真結(jié)果與分析

本節(jié)驗證提出的JRCRA 算法性能。仿真參數(shù)如表1 所示。

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

表1 仿真參數(shù)

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

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

5 結(jié) 束 語

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

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

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