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

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

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

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

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

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

本文的主要貢獻(xiàn)包括以下3 點(diǎn)：

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

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

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

1 系統(tǒng)模型

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

1.1 網(wǎng)絡(luò)模型

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

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

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

1.2 動(dòng)態(tài)隊(duì)列模型

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

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

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

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

對(duì)于任務(wù)計(jì)算隊(duì)列，任務(wù)由VEC 服務(wù)器進(jìn)行

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

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

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

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

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

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

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

2.2 問題重構(gòu)

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

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

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

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

3 動(dòng)態(tài)無線與計(jì)算資源分配算法

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

3.1 李雅普諾夫漂移

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

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

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

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

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

式中，

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

3.2 問題分解

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

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

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

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

3.3 計(jì)算資源分配

3.4 無線資源分配

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

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

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

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

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

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

其次，考慮C 的整數(shù)特性，無線資源分配的式(19)可以重新被構(gòu)建為一個(gè)單變量優(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) 將任務(wù)按照 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)合無線與計(jì)算資源分配算法

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

算法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é)驗(yàn)證提出的JRCRA 算法性能。仿真參數(shù)如表1 所示。

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

表1 仿真參數(shù)

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

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

5 結(jié) 束 語

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

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

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