V2X多節(jié)點(diǎn)協(xié)同分布式卸載策略

曹敦，張應(yīng)寶，鄒電，王進(jìn)，湯強(qiáng)，冀保峰

（1.長(zhǎng)沙理工大學(xué)計(jì)算機(jī)與通信工程學(xué)院，湖南 長(zhǎng)沙 410114；2.南京郵電大學(xué)寬帶無(wú)線通信與傳感網(wǎng)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210003；3.河南科技大學(xué)信息工程學(xué)院，河南 洛陽(yáng) 471023）

0 引言

在這個(gè)萬(wàn)物互聯(lián)的時(shí)代，人工智能和通信技術(shù)的快速發(fā)展能實(shí)現(xiàn)車輛與X（即車、人、網(wǎng)絡(luò)、基礎(chǔ)設(shè)施等）的通信[1]，并提升車輛的自動(dòng)駕駛能力，改善交通運(yùn)營(yíng)和服務(wù)智能化欠缺的現(xiàn)狀。同時(shí)新型車載終端的應(yīng)用也對(duì)通信質(zhì)量和服務(wù)智能化要求日益嚴(yán)苛[2-3]。移動(dòng)邊緣計(jì)算（MEC,mobile edge computing）的出現(xiàn)能夠有效地應(yīng)對(duì)這一挑戰(zhàn)。MEC是一種新型通信架構(gòu)，將具有存儲(chǔ)、計(jì)算、通信功能的服務(wù)平臺(tái)部署在網(wǎng)絡(luò)邊緣位置，幫助移動(dòng)終端用戶將服務(wù)任務(wù)就近卸載到邊緣節(jié)點(diǎn)上，進(jìn)行協(xié)同處理[4-5]，從而減輕通信鏈路的傳輸壓力，縮短服務(wù)的響應(yīng)時(shí)間，減少移動(dòng)設(shè)備的能耗和傳輸成本[6-7]。MEC 技術(shù)作為5G 移動(dòng)通信中開始應(yīng)用的一項(xiàng)重要技術(shù)，目前受到工業(yè)界和學(xué)術(shù)界的廣泛關(guān)注[8]。而其在車聯(lián)網(wǎng)中的應(yīng)用能提供低時(shí)延的計(jì)算智能，使用戶服務(wù)體驗(yàn)[9-10]有質(zhì)的改變。

車聯(lián)網(wǎng)服務(wù)類型可分為車載安全型、車載增強(qiáng)型和車載娛樂(lè)型三大類[11]。服務(wù)對(duì)時(shí)延、數(shù)據(jù)量、任務(wù)復(fù)雜度和子任務(wù)間耦合度等有不同的要求[12]。根據(jù)特征的不同，又可將任務(wù)分成不同的類型，如根據(jù)時(shí)延限制可分為時(shí)延敏感型和非時(shí)延敏感型，根據(jù)任務(wù)復(fù)雜度可分為計(jì)算資源密集型和稀疏型，根據(jù)子任務(wù)的耦合度分為可分離型和不可分離型[13]。時(shí)延敏感型的計(jì)算任務(wù)對(duì)數(shù)據(jù)的實(shí)時(shí)性要求極高，而計(jì)算密集型任務(wù)需要大量的存儲(chǔ)資源，但時(shí)延要求相對(duì)寬松[14]。依據(jù)Robertazzi的可分離任務(wù)理論[12]，可分離型任務(wù)可分成若干任意大小的子任務(wù)，每個(gè)子任務(wù)之間沒(méi)有依賴關(guān)系，可以按照任意順序進(jìn)行處理。而車載娛樂(lè)型服務(wù)中的視覺(jué)視頻剪輯和動(dòng)畫渲染等任務(wù)具有非時(shí)延敏感、數(shù)據(jù)量大、復(fù)雜度高、耦合度低的特點(diǎn)。在V2X（vehicle to everything）通信中，利用下沉到車輛及路側(cè)單元的計(jì)算資源設(shè)計(jì)一種任務(wù)可拆分、多節(jié)點(diǎn)協(xié)同的卸載決策，可滿足此類服務(wù)的服務(wù)質(zhì)量（QoS,quality of service）要求。

然而，任務(wù)可拆分、多節(jié)點(diǎn)協(xié)同的卸載決策需面對(duì)一系列問(wèn)題。在任務(wù)執(zhí)行周期內(nèi)，車載任務(wù)卸載環(huán)境是動(dòng)態(tài)不確定的，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及無(wú)線信道狀態(tài)會(huì)快速變化，如何選擇在任務(wù)執(zhí)行周期內(nèi)可用的協(xié)同節(jié)點(diǎn)是需要解決的問(wèn)題之一，且考慮協(xié)同節(jié)點(diǎn)通信和計(jì)算資源差異，如何進(jìn)行任務(wù)不等拆分，使任務(wù)分布式計(jì)算執(zhí)行時(shí)延最小化，以提高信道利用率是需解決的問(wèn)題之二。本文面對(duì)上述2 個(gè)問(wèn)題，提出了一種V2X多節(jié)點(diǎn)協(xié)同分布式卸載策略。本文主要的研究工作總結(jié)如下。

1) 本文構(gòu)建了V2X 下本地、MEC 和協(xié)同車輛多節(jié)點(diǎn)協(xié)同計(jì)算模型，它聯(lián)合了卸載策略和任務(wù)不等拆分問(wèn)題，通過(guò)預(yù)測(cè)車輛行駛軌跡，將協(xié)同卸載問(wèn)題建模成本地與協(xié)同節(jié)點(diǎn)分布式計(jì)算時(shí)間較大值最小化問(wèn)題。

2) 本文采用博弈論中的納什均衡來(lái)求解上述問(wèn)題中服務(wù)的卸載策略，并將串行卸載問(wèn)題公式化為帶約束的高維非線性優(yōu)化問(wèn)題。

3) 在卸載策略確定的情況下，本文采用序列二次規(guī)劃（SQP,sequential quadratic programming）算法求解上述優(yōu)化問(wèn)題，通過(guò)拉格朗日函數(shù)將原問(wèn)題轉(zhuǎn)化為二次規(guī)劃子問(wèn)題，從而確定任務(wù)的不等拆分比例，實(shí)現(xiàn)本地與卸載的工作時(shí)間均衡。

4) 實(shí)驗(yàn)結(jié)果表明，本文提出的算法具有良好的效能和優(yōu)越性。與其他4 種基準(zhǔn)算法相比，本文提出的算法能夠獲得更低的系統(tǒng)時(shí)延，并有良好的收斂性。

1 相關(guān)工作

國(guó)內(nèi)外學(xué)者針對(duì)移動(dòng)邊緣計(jì)算的任務(wù)卸載問(wèn)題開展了大量的研究。文獻(xiàn)[15]研究了靜止?fàn)顟B(tài)下的用戶卸載，考慮到MEC的車載無(wú)線網(wǎng)絡(luò)和計(jì)算能力有限的問(wèn)題，設(shè)計(jì)了一種無(wú)線和計(jì)算分配聯(lián)合優(yōu)化算法用來(lái)求解用戶的卸載決策。文獻(xiàn)[16]提出了LBB（linearization based branch and bound）和CRI（closest rounding integer）算法分別解決在用戶靜止和速度恒定狀態(tài)下的計(jì)算卸載策略，考慮到時(shí)變信道對(duì)任務(wù)卸載策略的影響，該研究提出了一種最接近四舍五入算法來(lái)解決固定時(shí)變頻譜效率問(wèn)題。文獻(xiàn)[17]提出了在加速度不變的條件下多用戶計(jì)算卸載決策，考慮到多個(gè)用戶設(shè)備同時(shí)通過(guò)無(wú)線信道卸載計(jì)算任務(wù)時(shí)的信道干擾問(wèn)題，設(shè)計(jì)了一種基于強(qiáng)化學(xué)習(xí)的進(jìn)化博弈算法。文獻(xiàn)[18]研究了車輛無(wú)線網(wǎng)絡(luò)的移動(dòng)感知計(jì)算卸載，考慮到車輛的隨機(jī)移動(dòng)和卸載過(guò)程中可能出現(xiàn)的越區(qū)切換問(wèn)題，該研究提出了一種分析模型用來(lái)計(jì)算卸載決策。文獻(xiàn)[19]提出了一種通過(guò)建立適用于移動(dòng)和普適計(jì)算場(chǎng)景的三層體系架構(gòu)來(lái)優(yōu)化用戶計(jì)算卸載決策的方法。

文獻(xiàn)[20]研究了服務(wù)請(qǐng)求車輛發(fā)送不可拆分?jǐn)?shù)據(jù)包時(shí)的平均上行局部時(shí)延，該研究利用最接近接收方模型確定單個(gè)邊緣節(jié)點(diǎn)。文獻(xiàn)[21]研究了每個(gè)用戶通過(guò)無(wú)線多址傳輸將計(jì)算任務(wù)卸載到多用戶協(xié)同計(jì)算，考慮到非正交多址接入（NOMA,non-orthogonal multiple access）的共信道干擾和MEC的計(jì)算任務(wù)均等拆分問(wèn)題，該研究提出了聯(lián)合最優(yōu)任務(wù)卸載和資源分配的算法求解卸載決策。文獻(xiàn)[22]通過(guò)研究多用戶多輸入多輸出預(yù)編碼和計(jì)算資源不等分配方法，提出了一種利用半定松弛法和舍入法優(yōu)化卸載決策。文獻(xiàn)[23]提出了基于多臂強(qiáng)盜理論進(jìn)行任務(wù)的不等拆分策略。文獻(xiàn)[24]提出了在動(dòng)態(tài)環(huán)境下基于自適應(yīng)學(xué)習(xí)的多車輛等分任務(wù)卸載策略，該研究以最小化平均卸載時(shí)延為目標(biāo)，提出了一種基于V2V 通信的多車任務(wù)卸載系統(tǒng)模型。

綜上所述，當(dāng)前已有的相關(guān)研究集中于以下2 個(gè)方面：1) 通過(guò)建立車輛的不同運(yùn)動(dòng)模型，優(yōu)化用戶的卸載決策問(wèn)題；2) 根據(jù)服務(wù)任務(wù)類型的差異，優(yōu)化卸載決策問(wèn)題。當(dāng)前關(guān)于協(xié)同卸載策略的研究工作雖然很多，但是聚集在車輛行駛軌跡預(yù)測(cè)下的不等任務(wù)拆分策略還較少。本文研究了V2X多節(jié)點(diǎn)協(xié)同串行卸載、分布式計(jì)算策略，聯(lián)合優(yōu)化了卸載決策和任務(wù)不等分配比例。

2 系統(tǒng)模型

本文主要考慮高速直行道路場(chǎng)景。因反向行駛車輛相對(duì)宿主車輛有較大反向相對(duì)速度，停留在宿主車輛通信范圍的時(shí)間較短，因此協(xié)同車輛僅考慮與宿主車輛同向行駛的車輛，并且考慮車輛變道、變加速等行駛行為。為充分利用計(jì)算資源和減少卸載計(jì)算時(shí)延，宿主車輛可以選擇部分任務(wù)在本地執(zhí)行，其余任務(wù)利用V2X 通信模式卸載到協(xié)同節(jié)點(diǎn)上協(xié)助處理。

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

網(wǎng)絡(luò)模型如圖1 所示?？商峁┻吘売?jì)算的路側(cè)單元（RSU,road side unit）標(biāo)記為v0，假設(shè)RSU 覆蓋范圍內(nèi)有N輛車呈泊松分布，表示為V={v1,v2,…,vi,…,v N},i∈[1,N]。假設(shè)車輛內(nèi)都裝有北斗衛(wèi)星導(dǎo)航系統(tǒng)等定位設(shè)備，可以實(shí)時(shí)獲取車輛的軌跡信息[25]。集合V中車輛終端的軌跡信息用集合S表示，，第α輛車在第t時(shí)刻的軌跡信息為，其中為速度，為第α輛車的位置坐標(biāo)。當(dāng)車輛vi為宿主車輛時(shí)，在卸載時(shí)延和通信范圍的約束下，vi有n∈[0,N]個(gè)可選擇的協(xié)同節(jié)點(diǎn)Mi={mi,0,mi,1,…,mi,j,…,mi,n},(i≠ 0,j≠i,j∈[0,n])，其中，mi,j表示宿主車輛vi的第j個(gè)協(xié)同節(jié)點(diǎn)，mi,0=v0表示RSU 可用。協(xié)同節(jié)點(diǎn)的卸載順序?yàn)镼i,j={qi,0,qi,1,…,qi,j,…,qi,n},(i≠0,j≠i,j∈[0,n])，其中，qi,j表示vi卸載到mi,j的卸載順序數(shù)，qi,j∈ {1,2,…,n+1}，例如qi,j=4 表示mi,j為第4 個(gè)執(zhí)行卸載的協(xié)同節(jié)點(diǎn)。宿主車輛vi的協(xié)同策略可通過(guò)協(xié)同節(jié)點(diǎn)集Mi根據(jù)Qi,j排序后獲得，表示為Ai=rank(M i,Qi,j)，rank(·) 表示將Mi中元素mi,j按Qi,j中對(duì)應(yīng)元素qi,j的值升序排列。

圖1 V2X多節(jié)點(diǎn)協(xié)同分布式卸載策略網(wǎng)絡(luò)模型

為了便于閱讀，本文中主要變量及含義如表1所示。

表1 主要變量及其含義

2.2 通信模型

本文各節(jié)點(diǎn)采用正交頻分多址（OFDMA,orthogonality frequency division multiple access）技術(shù)接入系統(tǒng)。任務(wù)車輛在執(zhí)行邊緣卸載時(shí)，通過(guò)V2R（vehicle to RSU）、V2V（vehicle to vehicle）通信模式將計(jì)算任務(wù)卸載到路側(cè)單元和協(xié)同車輛。本文假設(shè)多協(xié)同節(jié)點(diǎn)干擾已通過(guò)正交頻分多址技術(shù)消除，且車輛在任務(wù)上傳時(shí)間內(nèi)無(wú)線信道狀態(tài)保持穩(wěn)定[23]。不失一般性，假設(shè)V2V 通信模式復(fù)用V2R 通信模式的上行傳輸通道。根據(jù)香農(nóng)定律可得，數(shù)據(jù)的上傳速率為

其中，*可為v 或r，vw和rw分別表示V2V 和V2R信道帶寬；1p表示上傳鏈路信道衰落因子；p2表示路徑損耗因子；li,j表示從vi到mi,j的歐氏距離；0ρ表示通信內(nèi)部高斯噪聲密度；P為發(fā)射功率。

2.3 運(yùn)動(dòng)模型

本文構(gòu)建行駛軌跡預(yù)測(cè)模型，通過(guò)t時(shí)刻的位置信息預(yù)測(cè)t+Δt時(shí)刻的位置信息。假設(shè)本文的行駛軌跡預(yù)測(cè)模型目標(biāo)是估計(jì)用戶短時(shí)間 Δt內(nèi)的移動(dòng)軌跡。為方便描述，依據(jù)車輛行駛方向平行道路建立二維坐標(biāo)，第α輛車在t+Δt時(shí)刻的二維坐標(biāo)為

由L2 范數(shù)可獲得第α、β輛車在t+Δt時(shí)刻的距離為

即

2.4 計(jì)算模型

定義協(xié)同節(jié)點(diǎn)mi,j被分配的計(jì)算任務(wù)為其中，Di,j表示任務(wù)量大小，表示任務(wù)Di,j從vi卸載到mi,j的順序標(biāo)簽值，表示任務(wù)Zi,j所能容忍的最大時(shí)延。一些計(jì)算任務(wù)具有較高的復(fù)雜性，無(wú)法及時(shí)得到計(jì)算結(jié)果。因此，需要決策Zi,j中在本地及卸載計(jì)算的子任務(wù)量。

1) 本地計(jì)算

2) 卸載計(jì)算

卸載計(jì)算時(shí)延包括傳輸時(shí)延、計(jì)算時(shí)延和回傳時(shí)延，因任務(wù)完成結(jié)果的大小遠(yuǎn)小于任務(wù)的大小，并且考慮到傳輸?shù)南滦校ɑ貍鳎┧俣冗h(yuǎn)大于上行（傳輸）速度，所以本文忽略結(jié)果回傳的時(shí)延大小[22,26]，僅考慮上行傳輸時(shí)延和計(jì)算時(shí)延兩部分的影響。

協(xié)同節(jié)點(diǎn)mi,j的卸載計(jì)算時(shí)延為

本文研究的是非時(shí)延敏感型任務(wù)的協(xié)同計(jì)算，并考慮資源競(jìng)爭(zhēng)的公平性，宿主車輛使用單信道進(jìn)行任務(wù)串行卸載，同時(shí)為提高用戶服務(wù)質(zhì)量及無(wú)線資源的利用率、最小化系統(tǒng)時(shí)延，設(shè)計(jì)各協(xié)同節(jié)點(diǎn)接受任務(wù)后分布式執(zhí)行。在卸載過(guò)程中，上行傳輸時(shí)間與執(zhí)行時(shí)間存在一段重疊時(shí)間。因此卸載部分所用的時(shí)間取決于所有協(xié)同節(jié)點(diǎn)上傳時(shí)延之和，再加最后被卸載協(xié)同節(jié)點(diǎn)的計(jì)算時(shí)延，即

2.5 問(wèn)題形成

車聯(lián)網(wǎng)中利用MEC 進(jìn)行卸載計(jì)算，為提高通信及計(jì)算資源的利用率，期望最小化任務(wù)卸載的計(jì)算時(shí)延。但任務(wù)卸載計(jì)算期間，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及信道質(zhì)量因車輛的移動(dòng)發(fā)生變化。因此，需預(yù)測(cè)車輛軌跡，選擇時(shí)延容限內(nèi)可用的協(xié)同節(jié)點(diǎn)，并確定拆分任務(wù)方案、卸載節(jié)點(diǎn)及任務(wù)卸載順序。需解決的串行卸載、并行計(jì)算問(wèn)題為

因?yàn)槿蝿?wù)在本地和協(xié)同節(jié)點(diǎn)分布式執(zhí)行，所以任務(wù)執(zhí)行總時(shí)長(zhǎng)取決于本地或協(xié)同節(jié)點(diǎn)任務(wù)執(zhí)行時(shí)長(zhǎng)的較大值。約束條件1C 表示任務(wù)在本地和協(xié)同節(jié)點(diǎn)分布式執(zhí)行的約束邊界；C2表示在任務(wù)執(zhí)行期內(nèi)vi到mi,j之間的相對(duì)距離小于或等于通信范圍R；C3表示本地和卸載計(jì)算任務(wù)量之和等于總?cè)蝿?wù)量；C4表示當(dāng)前協(xié)同節(jié)點(diǎn)mi,j執(zhí)行卸載任務(wù)的計(jì)算時(shí)延必須小于還未分配計(jì)算任務(wù)的協(xié)同卸載計(jì)算時(shí)延之和，其目的在于保證最后一個(gè)協(xié)同節(jié)點(diǎn)將子任務(wù)的計(jì)算結(jié)果回傳到宿主車輛后，其余協(xié)同節(jié)點(diǎn)的計(jì)算結(jié)果均已完成回傳。

3 算法設(shè)計(jì)

為了解決式(8)描述的優(yōu)化問(wèn)題，本文提出了一種協(xié)同分布式卸載-SQP 策略（CDOS-SQP,cooperative distributed offloading strategy-SQP）。在CDOS-SQP 中，分別提出了一種基于博弈論的卸載策略和基于SQP 算法[27]的任務(wù)分配方法，前者確定計(jì)算任務(wù)的卸載策略集Ai，而后者根據(jù)Ai確定任務(wù)不等拆分集iD。

3.1 基于博弈論的卸載機(jī)制

本節(jié)確定宿主車輛協(xié)同卸載時(shí)可用的mi,j，可通過(guò)卸載順序集Qi,j獲得協(xié)同策略集Ai來(lái)解決此問(wèn)題。

在宿主車輛和協(xié)同節(jié)點(diǎn)的不斷移動(dòng)下，確定車輛vi為宿主車輛時(shí)的協(xié)同節(jié)點(diǎn)集Mi的準(zhǔn)則是：在任務(wù)執(zhí)行期內(nèi)協(xié)同車輛始終處于宿主車輛的通信范圍R內(nèi)。本文應(yīng)用博弈論中的重復(fù)剔除嚴(yán)格劣戰(zhàn)略來(lái)獲得Mi。

使用博弈論中的重復(fù)剔除嚴(yán)格劣戰(zhàn)略，將t+tΔ 時(shí)刻車輛間的距離大于通信范圍R定義為劣戰(zhàn)略，終止條件為此時(shí)刻集合Mi中不包含劣戰(zhàn)略。從而確定從t時(shí)刻到時(shí)刻始終處于R范圍內(nèi)的協(xié)同節(jié)點(diǎn)集Mi。下面使用博弈論中的納什均衡來(lái)確定最優(yōu)卸載順序集

首先，定義mi,j的為宿主車輛vi卸載到的上傳時(shí)延及在mi,j的計(jì)算時(shí)延之和，即

然后，使用博弈論中的納什均衡來(lái)確定協(xié)同節(jié)點(diǎn)執(zhí)行任務(wù)的卸載順序。策略博弈[28]Γ涉及3 個(gè)要素，分別為參與者M(jìn)i、策略Qi以及效用函數(shù)Ui，具體說(shuō)明如下。

1) 參與者。宿主車輛vi的n+1 個(gè)參與博弈的協(xié)同節(jié)點(diǎn)集Mi。

3) 效用函數(shù)。當(dāng)vi的協(xié)同節(jié)點(diǎn)集Mi選擇其串行卸載順序集為Qi,j時(shí)的代價(jià)函數(shù)為定義如式(11)所示。每個(gè)協(xié)同節(jié)點(diǎn)都希望選擇最優(yōu)卸載順序獲得最大效用。

納什均衡是指博弈中每個(gè)參與者都確信在其他參與者策略給定的情況下，自己選擇了最優(yōu)策略，從而使自己效用最大化。具體描述介紹如下。

算法1使用基于博弈論的卸載決策求解卸載策略集Ai

3.2 基于SQP 算法的任務(wù)分配

本節(jié)研究協(xié)同卸載下任務(wù)不等拆分集iD。現(xiàn)已通過(guò)卸載機(jī)制計(jì)算出Ai，已知式(8)中的約束條件C2僅影響策略集合Ai，則在本節(jié)計(jì)算需確立集合Di中任務(wù)的不等拆分比例，使任務(wù)執(zhí)行時(shí)延Tvec最小化時(shí)不考慮約束條件C2。由于集合Di中任務(wù)可在本地和協(xié)同節(jié)點(diǎn)并行計(jì)算，因此將式(8)轉(zhuǎn)化為本地和卸載這兩類并行執(zhí)行時(shí)間差值ΔTvec最小化問(wèn)題，即

因?yàn)閰f(xié)同策略集Ai中有多個(gè)協(xié)同節(jié)點(diǎn)，所以任務(wù)不等拆分時(shí)按照協(xié)同節(jié)點(diǎn)數(shù)將其拆分成多份不等任務(wù)，即式(12)的優(yōu)化問(wèn)題可描述為帶約束條件高維非線性優(yōu)化函數(shù)問(wèn)題。SQP 算法是求解此類最有效的優(yōu)化算法之一，具有收斂性較好、邊界搜索能力強(qiáng)、計(jì)算效率高等優(yōu)點(diǎn)。本文采用SQP 算法求解式(12)的優(yōu)化目標(biāo)問(wèn)題。

優(yōu)化問(wèn)題的數(shù)學(xué)模型簡(jiǎn)化為

其中，X為Rn中的一個(gè)非空多面體子集，即任務(wù)不等拆分集Di；ΔTvec(X)為優(yōu)化目標(biāo)函數(shù)，ΔTvec越接近0，分布式執(zhí)行程度越高，Tvec越??；約束條件中，優(yōu)化變量X取值范圍的最大值為，最小值為0；h(X)為式(12)中C2描述的等式約束；g(X)為式(12)中C3描述的不等式約束；Rn表示數(shù)值取自實(shí)數(shù)空間，因此可將式(12)中的優(yōu)化目標(biāo)函數(shù)問(wèn)題轉(zhuǎn)化成求解式(13)，拉格朗日函數(shù)為

其中，1λ和2λ為約束函數(shù)的加權(quán)因子。

在kX點(diǎn)根據(jù)二階泰勒公式近似展開為

其中，Sk為優(yōu)化問(wèn)題的搜索方向；[B] 為擬牛頓法近似構(gòu)造的海塞矩陣，符號(hào)?為梯度。拉格朗日函數(shù)的一階導(dǎo)數(shù)為

函數(shù)g(X)在Xk點(diǎn)展開的二階泰勒近似式為

活動(dòng)三：尋找能量傳遞的規(guī)律。教師引導(dǎo)學(xué)生結(jié)合書本102頁(yè)的知識(shí)，用彩色木棒標(biāo)識(shí)出主圖中能量的流動(dòng)途徑。此部分在高中會(huì)詳細(xì)學(xué)習(xí)，為了降低難度，教師提供下列提示：

等式約束h(X)=0在Xk點(diǎn)展開的二階泰勒近似式為

將式(15)～式(18)聯(lián)合計(jì)算代入式(12)，經(jīng)過(guò)整理得二次規(guī)劃子問(wèn)題為

求解上述二次規(guī)劃子問(wèn)題[29]，得到搜索方向Sk，沿搜索方向進(jìn)行一維搜索，?k為第k次搜索的下降方向Sk的最優(yōu)步長(zhǎng)，利用Wolfe 步長(zhǎng)規(guī)則獲取，按照式(20)進(jìn)行迭代更新，最終得到原問(wèn)題的最優(yōu)解為

其中，[B] 為L(zhǎng)agrange 函數(shù)的Hessian 矩陣正定擬牛頓近似，并通過(guò)稠密半定牛頓近似法 BFGS（Broyden-Fletcher-Goldfarb-Shanno）進(jìn)行計(jì)算，作為不斷更新的校正矩陣，搜索方向迭代更新矩陣Bk是的近似，更新式為

其中，Bk為n階對(duì)稱正定矩陣。

本文使用SQP 算法，利用擬牛頓法（變尺度法）來(lái)近似構(gòu)造海塞（Hessian）矩陣[B]，以建立二次規(guī)劃子問(wèn)題式(19)，又稱約束變尺度法。通過(guò)求解二次規(guī)劃子問(wèn)題得到迭代的搜索方向Sk，沿搜索方向進(jìn)行一維搜索，找到迭代的步長(zhǎng) ?k，利用式(21)更新修正Bk+1，最后按照迭代式(20)最終得到問(wèn)題的最優(yōu)解Di，式(14)～式(21)為SQP的一般方法。偽代碼如算法2 所示。

算法2基于SQP 算法求解任務(wù)不等拆分集Di

4 仿真結(jié)果及性能分析

本節(jié)將評(píng)估所提算法在車輛移動(dòng)下，通過(guò)SQP算法將任務(wù)不等拆分后在分布式協(xié)同執(zhí)行下的性能。使用各種度量來(lái)評(píng)估性能，如系統(tǒng)總時(shí)延、迭代次數(shù)，本文還研究了算法在不同參數(shù)設(shè)置下性能的表現(xiàn)。

4.1 仿真設(shè)置

本文采用V2X多節(jié)點(diǎn)分布式卸載策略，定義的道路場(chǎng)景如圖1 所示。在車輛數(shù)一定的情況下，道路上車輛服從泊松分布，主要實(shí)驗(yàn)參數(shù)如表2 所示。為了獲得方法的一般性能，本文采用蒙特卡羅方法進(jìn)行了1 000 次仿真，獲得平均性能以衡量方法的性能。車輛在直道上行駛的最大速度符合高速公路最大安全速度及車輛間安全行駛速度的規(guī)定，初始速度隨機(jī)在60 km/h 至最大速度之間選擇，并在單次仿真過(guò)程中保持不變。后述實(shí)驗(yàn)過(guò)程中在沒(méi)有特殊說(shuō)明情況下，均采用表2 中實(shí)驗(yàn)參數(shù)[30]。

表2 主要實(shí)驗(yàn)參數(shù)

4.2 仿真結(jié)果及分析

本節(jié)說(shuō)明使用上述及本文所提協(xié)同卸載模型，分別改變?nèi)蝿?wù)量、上傳功率、車輛密度和車輛初始速度范圍，獲得系統(tǒng)總時(shí)延，比較分析CDOS-SQP的優(yōu)越性。

車輛總數(shù)N固定為25 輛，任務(wù)量與系統(tǒng)時(shí)延關(guān)系如圖2 所示。隨著計(jì)算任務(wù)量增加，本文所提CDOS-SQP的系統(tǒng)時(shí)延均低于對(duì)比策略。在任務(wù)量最大時(shí)，CDOS-SQP 策略系統(tǒng)時(shí)延相對(duì)最劣對(duì)比策略減少67%，相對(duì)最優(yōu)對(duì)比策略減少8%。當(dāng)計(jì)算任務(wù)量較大時(shí)，CDOS-SQP的系統(tǒng)時(shí)延顯著優(yōu)于對(duì)比策略，并且隨著計(jì)算任務(wù)量的增加，CDOS-SQP增長(zhǎng)速度相比其他策略較緩。造成上述結(jié)果的原因是，隨著計(jì)算任務(wù)量的不斷增加，系統(tǒng)的最優(yōu)策略會(huì)傾向于在邊緣側(cè)和本地聯(lián)合計(jì)算。而CDOS-SQP 相比對(duì)比策略可選擇協(xié)同節(jié)點(diǎn)數(shù)最多，因此CDOS-SQP的優(yōu)勢(shì)隨著計(jì)算任務(wù)量的增加更加明顯。

圖2 任務(wù)量與系統(tǒng)時(shí)延關(guān)系

計(jì)算任務(wù)量固定為50 MB，上傳功率與系統(tǒng)時(shí)延關(guān)系如圖3 所示。從圖3 中可以看出，策略只需在本地計(jì)算，所以上傳功率對(duì)的系統(tǒng)時(shí)延大小并無(wú)影響，而其余策略的任務(wù)卸載執(zhí)行時(shí)延隨著上傳功率的增大而減小。這是因?yàn)樗拗鬈囕v上傳功率增加會(huì)提高信噪比，從而增加信道容量，使采用邊緣卸載的策略上傳時(shí)延減小。同時(shí)CDOS-SQP 相比對(duì)比策略可用的協(xié)同節(jié)點(diǎn)數(shù)最多，且多協(xié)同節(jié)點(diǎn)采用分布式卸載策略并計(jì)算任務(wù)，其系統(tǒng)時(shí)延是最小的。通過(guò)實(shí)驗(yàn)對(duì)比可知，本文策略優(yōu)于對(duì)比策略。

圖3 上傳功率與系統(tǒng)時(shí)延關(guān)系

相同計(jì)算任務(wù)下車輛密度的變化對(duì)系統(tǒng)時(shí)延的影響如圖4 所示。從圖4 可知，除外，其余策略隨著車輛密度的增加，系統(tǒng)時(shí)延不斷減小。造成上述現(xiàn)象的原因是：策略任務(wù)僅在本地執(zhí)行，車輛密度的變化對(duì)其沒(méi)有影響；而在其他卸載策略中，隨著車輛密度的不斷增大，可用的協(xié)同節(jié)點(diǎn)也隨著增多，由式(1)～式(6)可知，節(jié)點(diǎn)間歐氏距離越小，上傳時(shí)延也將越小，因此隨車密度增加，系統(tǒng)總時(shí)延減少。而CDOS-SQP 可用的協(xié)同節(jié)點(diǎn)最多，因此表現(xiàn)最優(yōu)。

圖4 車輛密度與系統(tǒng)時(shí)延關(guān)系

車輛密度為20 輛，總?cè)蝿?wù)量為50 MB，車輛初始速度變化范圍與系統(tǒng)時(shí)延的關(guān)系如圖5 所示。結(jié)果表明，隨著初始速度變化范圍的增加，計(jì)算任務(wù)的系統(tǒng)時(shí)延不斷增大。從圖5 中可看出，車輛的運(yùn)動(dòng)速度對(duì)沒(méi)有產(chǎn)生影響，而對(duì)的結(jié)果會(huì)產(chǎn)生較大的波動(dòng)。因?yàn)楫?dāng)車輛初始速度變化范圍越大時(shí)，宿主車輛與協(xié)同節(jié)點(diǎn)的連通時(shí)間將越短，使可用的協(xié)同節(jié)點(diǎn)數(shù)也將越少。所以對(duì)于和算法而言，全部任務(wù)只進(jìn)行卸載計(jì)算影響最明顯。CDOS-SQP 性能最優(yōu)的原因是，同時(shí)采用本地和協(xié)同節(jié)點(diǎn)分布式執(zhí)行，并且可利用多協(xié)同節(jié)點(diǎn)進(jìn)行并行計(jì)算執(zhí)行。

圖5 車輛初始速度變化范圍與時(shí)延關(guān)系

圖6給出了不同參數(shù)條件下迭代次數(shù)與收斂性的變化關(guān)系，展示了SQP 算法在不同參數(shù)下解決式(13)所示優(yōu)化問(wèn)題的迭代次數(shù)。通過(guò)圖6 可知，當(dāng)?shù)?4 次后實(shí)驗(yàn)結(jié)果趨于平穩(wěn)，即趨于目標(biāo)函數(shù)的最優(yōu)解。隨著迭代次數(shù)的增加，SQP 算法得到目標(biāo)函數(shù)的值越來(lái)越接近滿足約束條件的最優(yōu)解。這表明SQP 算法解決式(13)所示優(yōu)化問(wèn)題，具有迭代次數(shù)較少、收斂性較好的優(yōu)點(diǎn)。

圖6 迭代次數(shù)與收斂性的變化關(guān)系

5 結(jié)束語(yǔ)

本文對(duì)可拆分任務(wù)的V2X多節(jié)點(diǎn)分布式卸載策略進(jìn)行研究?？紤]車輛行駛軌跡和最大時(shí)延約束，建立了基于博弈論的卸載策略和基于SQP算法的任務(wù)分配模型。利用博弈論中的重復(fù)剔除嚴(yán)格劣戰(zhàn)略和納什均衡確定出協(xié)同策略集；將原問(wèn)題轉(zhuǎn)換為帶約束的高維非線性優(yōu)化問(wèn)題，根據(jù)SQP 算法將該問(wèn)題轉(zhuǎn)換為求解二次規(guī)劃子問(wèn)題，利用拉格朗日和BFGS 方法得到最優(yōu)解，并分析了算法的收斂性。仿真結(jié)果表明，本文所提CDOS-SQP 具有較好的收斂性和優(yōu)越性。下一步的工作將研究更普遍的道路結(jié)構(gòu)（如彎道、十字路口等多結(jié)構(gòu)復(fù)雜道路場(chǎng)景）和考慮更精準(zhǔn)的行駛軌跡預(yù)測(cè)的協(xié)同卸載問(wèn)題。