面向智能網(wǎng)聯(lián)汽車邊緣網(wǎng)絡(luò)的分布式端-邊協(xié)同算法

朱凱男，朱永東，趙志峰，劉云濤，張 園

(1.之江實(shí)驗(yàn)室,浙江 杭州 311121；2．中國(guó)電信研究院新興技術(shù)研究所,上海 200000)

0 引言

車聯(lián)網(wǎng)技術(shù)通過(guò)無(wú)線接入技術(shù)讓道路上安裝了車載設(shè)備單元(On Board Unit，OBU)的車輛可以與行人、相鄰的智能網(wǎng)聯(lián)汽車、路側(cè)設(shè)備單元(Road Side Unit，RSU)或者基站等實(shí)體便捷地進(jìn)行各種信息的交換和傳播[1-2]。通過(guò)這種方式，智能網(wǎng)聯(lián)汽車可以獲取碰撞預(yù)警等信息，從而及時(shí)采取相應(yīng)的措施，進(jìn)而降低交通事故的發(fā)生率、提升自動(dòng)駕駛車輛的安全性[3-4]。道路管理者可以利用車聯(lián)網(wǎng)技術(shù)實(shí)時(shí)獲取交通信息，通過(guò)車速引導(dǎo)等方式緩解城市交通的擁堵?tīng)顩r，并達(dá)到車輛節(jié)能減排的目的[5-6]。

車聯(lián)網(wǎng)高級(jí)安全服務(wù)中，智能網(wǎng)聯(lián)車輛配備了攝像頭，可以拍攝周圍的視頻，用于安全、交通監(jiān)控和監(jiān)視等目的[7]。車輛將獲取的視頻上傳到邊緣計(jì)算節(jié)點(diǎn)后，可以對(duì)視頻進(jìn)行分析和備份，以滿足不同的安全駕駛需求?，F(xiàn)有研究顯示，如果將車輛獲取的視頻及時(shí)傳輸?shù)竭吘売?jì)算節(jié)點(diǎn)進(jìn)行視頻分析和備份，可以極大地提高公共安全性[8-9]。然而，海量的視頻內(nèi)容上傳會(huì)給當(dāng)前的車聯(lián)網(wǎng)增加巨大的流量，導(dǎo)致大量的帶寬和能量消耗[10]。

為了解決上述問(wèn)題，現(xiàn)有的學(xué)術(shù)工作主要關(guān)注內(nèi)容下載[11-13]。E.Evdokimova[11]等人提出了一個(gè)分析框架，該框架通過(guò)多維馬爾可夫過(guò)程對(duì)直通車聯(lián)網(wǎng)場(chǎng)景中的下行鏈路流量進(jìn)行建模：將RSU緩沖區(qū)中的數(shù)據(jù)包到達(dá)構(gòu)建為泊松過(guò)程，并且傳輸時(shí)間呈指數(shù)分布。考慮到與多維馬爾可夫過(guò)程相關(guān)的狀態(tài)空間爆炸問(wèn)題，該文使用迭代擾動(dòng)技術(shù)來(lái)計(jì)算馬爾可夫鏈的平穩(wěn)分布。L.Yang等人[12]研究了混合數(shù)據(jù)傳播問(wèn)題，即優(yōu)化確定數(shù)據(jù)傳輸?shù)臅r(shí)間和目的車輛，以及車輛是直接從邊緣還是從附近的車輛獲取所需數(shù)據(jù)，目的是最小化邊緣的流量成本并滿足獲取數(shù)據(jù)的時(shí)延要求；文中提出了一種新的數(shù)據(jù)傳播算法，稱為混合數(shù)據(jù)傳播離線算法，該算法優(yōu)先尋找最有益的車到車廣播，然后選擇可行的車到基站傳播方式。J.He等人[13]通過(guò)權(quán)衡交付延遲和保管箱部署成本二者之間的關(guān)系來(lái)研究如何以最佳方式部署保管箱，為了解決該問(wèn)題，首先提供了一個(gè)理論框架來(lái)準(zhǔn)確估計(jì)交付延遲；然后，基于維度擴(kuò)大和動(dòng)態(tài)規(guī)劃的思想，設(shè)計(jì)了一種新穎的最優(yōu)保管箱部署算法(ODDA)以獲得最優(yōu)部署策略。在內(nèi)容上傳方面，L.Cui等人[10]提議在公交車站部署專用接入點(diǎn) (AP) 以促進(jìn)視頻上傳來(lái)研究移動(dòng)公交車的視頻上傳問(wèn)題，提出了一種注水放置算法，旨在平衡分配給每條總線的聚合帶寬，通過(guò)建立排隊(duì)模型來(lái)分析視頻內(nèi)容的上傳延遲，并進(jìn)一步采用機(jī)器學(xué)習(xí)模型將公交路線的影響納入排隊(duì)模型中。

本文提出一種面向智能網(wǎng)聯(lián)汽車邊緣網(wǎng)絡(luò)的分布式端(智能網(wǎng)聯(lián)汽車)-邊(邊緣計(jì)算節(jié)點(diǎn))協(xié)同算法。針對(duì)車聯(lián)網(wǎng)高可靠低時(shí)延內(nèi)容傳輸?shù)奶攸c(diǎn)，引入有限塊長(zhǎng)度機(jī)制[14]。同時(shí)，引入車輛視頻信息源的壓縮編碼功率消耗，建立車輛能耗模型。根據(jù)車輛視頻信息源的視頻質(zhì)量要求，通過(guò)調(diào)整視頻編碼碼率、信息源傳輸速率，以及對(duì)車輛多路徑路由的選擇，提出一種完全分布式的優(yōu)化算法，提高網(wǎng)絡(luò)資源利用率，并保證單個(gè)車輛的能耗公平性。

1 系統(tǒng)模型

圖1 智能網(wǎng)聯(lián)汽車邊緣網(wǎng)絡(luò)邊-端協(xié)同系統(tǒng)Fig.1 End-to-edge collaboration system for edge network of intelligent connected vehicles

1.1 視頻失真率模型

在智能網(wǎng)聯(lián)汽車邊緣網(wǎng)絡(luò)邊-端協(xié)同系統(tǒng)中，視頻上傳的端到端失真大小包括兩個(gè)不相關(guān)的部分[15]：① 由視頻壓縮引起的壓縮編碼失真Dc；② 由通信傳輸引起的傳輸失真Dt。數(shù)學(xué)上，端到端失真大小D可以表示為：D=Dc+Dt。

(1)

式中，σ2為平均視頻輸入方差，e為自然對(duì)數(shù)函數(shù)的底數(shù)，γ為與編碼效率相關(guān)的參數(shù)。根據(jù)失真率模型，如圖2所示，在給定視頻壓縮編碼失真大小的情況下，信息源編碼后數(shù)據(jù)速率越大，則視頻壓縮編碼功率消耗越??；在給定信息源編碼后數(shù)據(jù)速率的情況下，視頻質(zhì)量(表示為失真大小)越好，則視頻壓縮編碼功率消耗越大。

圖2 給定參數(shù)下(σ2=3 500，γ=55.54)功耗-速率- 失真大小的分析模型示例圖Fig.2 Illustration of the power-rate-distortion model with given parameters (σ2=3 500，γ=55.54)

另一方面，S.Pudlewski等人[17]的研究表明在設(shè)定合適的目標(biāo)誤碼率前提下，由通信傳輸引起的傳輸失真相較于由視頻壓縮引起的壓縮編碼失真而言，可以忽略不計(jì)。因此，總視頻失真大小僅考慮由視頻壓縮引起的壓縮編碼失真。

1.2 傳輸信道模型

由于多媒體數(shù)據(jù)傳輸?shù)膫鬏斞舆t要求短，傳統(tǒng)的香農(nóng)容量不再適合表征給定塊錯(cuò)誤概率的最大可實(shí)現(xiàn)數(shù)據(jù)傳輸速率。為此，有限塊長(zhǎng)度編碼技術(shù)已被開發(fā)用于可靠的多媒體移動(dòng)無(wú)線網(wǎng)絡(luò)[19]。假設(shè)完美的信道狀態(tài)信息條件下，給定信息比特長(zhǎng)度L和信噪比γl，則有限塊長(zhǎng)度編碼技術(shù)中可取得的最大編碼速率可以表示為：

(2)

(3)

式中，Bl是鏈路l的傳輸帶寬，通信鏈路l上的數(shù)據(jù)傳輸流量fl需小于最大有效傳輸速率cl，數(shù)學(xué)上表示為：

(4)

1.3 網(wǎng)絡(luò)數(shù)據(jù)流平衡模型

對(duì)于智能網(wǎng)聯(lián)汽車邊緣網(wǎng)絡(luò)中的任一節(jié)點(diǎn)(智能網(wǎng)聯(lián)汽車、基站與邊緣網(wǎng)關(guān))而言，流出該節(jié)點(diǎn)的數(shù)據(jù)信息流量需等于流入該節(jié)點(diǎn)的數(shù)據(jù)信息流量與該節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)信息流量之和。因此，網(wǎng)絡(luò)流平衡模型可以表示為：

(5)

對(duì)于智能網(wǎng)聯(lián)汽車而言，節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)信息流量為視頻信息源編碼后數(shù)據(jù)速率；基站與邊緣網(wǎng)關(guān)是智能網(wǎng)聯(lián)汽車信息傳輸?shù)膮R聚點(diǎn)，其數(shù)據(jù)信息流量為所有智能網(wǎng)聯(lián)汽車數(shù)據(jù)信息流量之和的負(fù)數(shù)。因此，智能網(wǎng)聯(lián)汽車或基站與邊緣網(wǎng)關(guān)i的信息源編碼后數(shù)據(jù)速率R(i)可以表示為：

(6)

1.4 能量消耗模型

(7)

(8)

利用上述數(shù)學(xué)模型，智能網(wǎng)聯(lián)汽車i的視頻壓縮和通信總能耗模型表示為：

(9)

式中，由于εl為給定數(shù)值參數(shù)，因此可以將1-εl視為常數(shù)。在以下分析中，為了便于閱讀，將1-εl在式(9)中進(jìn)行省略。

2 優(yōu)化問(wèn)題建模

約束條件：

對(duì)上述4個(gè)約束條件的解釋如下：

① 規(guī)定了網(wǎng)絡(luò)流平衡條件；

④ 規(guī)定了通信鏈路l上的數(shù)據(jù)傳輸流量fl需小于最大有效傳輸速率cl；

⑤ 規(guī)定了變量智能網(wǎng)聯(lián)汽車的能耗大小Pi、信息源編碼后數(shù)據(jù)速率R(i)、通信鏈路l上的數(shù)據(jù)傳輸流量fl的取值需不為負(fù)數(shù)。

3 分布式優(yōu)化算法

(10)

經(jīng)過(guò)上述改動(dòng)，優(yōu)化問(wèn)題P1可以改寫為優(yōu)化問(wèn)題P2：

約束條件：

容易證明上述優(yōu)化問(wèn)題P2是凸優(yōu)化問(wèn)題。為了提供一種完全分布式的優(yōu)化算法，利用拉格朗日松弛約束條件，得到優(yōu)化問(wèn)題P2的拉格朗日對(duì)偶函數(shù)：

其中，λi、θi、μi和φl(shuí)是拉格朗日乘子或?qū)ε甲兞?；R、f、Pc和P是原始變量。

利用次梯度算法[20]，將對(duì)偶變量進(jìn)行迭代逐步更新達(dá)到最優(yōu)。用k表示迭代次數(shù)，α(k)表示迭代步長(zhǎng)，則對(duì)偶變量的更新公式為：

(11)

(12)

(13)

(14)

其中，{·}+表示取正值運(yùn)算(也可以表示為x=max{0,x})。

原始變量的更新公式為：

(15)

(16)

(17)

(18)

算法1 基于次梯度算法的分布式邊-端協(xié)同算法初始化網(wǎng)絡(luò)信息:設(shè)置迭代次數(shù)k=0,設(shè)置節(jié)點(diǎn)和通信鏈路存儲(chǔ)器中的變量初始值R(i)(0)、P(i)c(0)、Pi(0)、fl(0)、λi(0)、θi(0)、μi(0)、φl(shuí)(0)為任一非負(fù)值。循環(huán): 1:針對(duì)通信鏈路l或通信鏈路(i,j),根據(jù)式(14)和式(16)分別更新φl(shuí)(k)和fl(k); 2:針對(duì)智能網(wǎng)聯(lián)汽車?i∈ ,根據(jù)式(11)～式(13)分別更新對(duì)偶變量λi(k)、θi(k)和μi(k); 3:針對(duì)智能網(wǎng)聯(lián)汽車?i∈ ,根據(jù)式(15)、(17)和(18)分別更新原始變量R(i)(k)、P(i)c(k)和Pi(k); 4:完成原始和對(duì)偶變量更新后,通信鏈路l將更新后的φl(shuí)(k+1)和fl(k+1)廣播給其對(duì)應(yīng)的流出、流入節(jié)點(diǎn);終端設(shè)備將更新后的λ -1(l)(k)、λ -1(l)(k)、θ -1(l)(k)、θ -1(l)(k)廣播給相應(yīng)的通信鏈路發(fā)送節(jié)點(diǎn); 5:迭代次數(shù)更新為k=k+1; 重復(fù)上述步驟1～5,直到算法收斂;結(jié)束循環(huán)

4 仿真實(shí)驗(yàn)和分析

表1 具體參數(shù)設(shè)置

圖3和圖4分別顯示了提出的算法對(duì)于智能網(wǎng)聯(lián)汽車視頻壓縮和通信總能耗、編碼后數(shù)據(jù)速率的迭代性能，由圖可知，大約在200次迭代后達(dá)到最優(yōu)。因此，本算法能在較短的時(shí)間內(nèi)達(dá)到性能穩(wěn)定狀態(tài)，能夠滿足車聯(lián)網(wǎng)場(chǎng)景下拓?fù)浣Y(jié)構(gòu)快速變化的需求。同時(shí)，針對(duì)優(yōu)化目標(biāo)，即保證單個(gè)車輛的能耗公平性，圖3中的仿真結(jié)果顯示，在迭代達(dá)到最優(yōu)狀態(tài)時(shí)，每輛智能網(wǎng)聯(lián)汽車的視頻壓縮和通信總能耗非常接近(如表2所示)。因此，本算法能夠達(dá)到保證單個(gè)車輛的能耗公平性的目標(biāo)。

圖3 智能網(wǎng)聯(lián)汽車視頻壓縮和通信總能耗的迭代性能Fig.3 Iteration performance of the total power consumption due to video compression and communications of intelligent connected vehicles

圖4 智能網(wǎng)聯(lián)汽車編碼后數(shù)據(jù)速率的迭代性能Fig.4 Iteration performance of the encoding data rate of intelligent connected vehicles

表2 算法收斂后每輛智能網(wǎng)聯(lián)汽車的視頻壓縮和通信 總能耗

圖4還表明承擔(dān)中繼數(shù)據(jù)任務(wù)較重的車輛會(huì)使用較低的視頻壓縮能耗(由視頻失真率模型式(1)可知，因此該車輛編碼后數(shù)據(jù)速率較大)，由此利用較多的能耗用于數(shù)據(jù)接收與傳輸。

為了比較提出算法的性能，將其與每輛智能網(wǎng)聯(lián)汽車直接與基站通信機(jī)制下的性能進(jìn)行對(duì)比，結(jié)果如圖5所示。在智能網(wǎng)聯(lián)汽車直接與基站通信的機(jī)制下，每輛智能網(wǎng)聯(lián)汽車的視頻壓縮和通信總能耗差別較大，即距離基站較近的智能網(wǎng)聯(lián)汽車的視頻壓縮和通信總能耗較小。這是因?yàn)榫嚯x基站較近的智能網(wǎng)聯(lián)汽車具有較好的傳輸信道信噪比，可以利用更少的通信能耗支持更大的數(shù)據(jù)傳輸速率。同時(shí)，根據(jù)視頻失真率模型式(1)，在視頻質(zhì)量要求相同的情況下，更大的數(shù)據(jù)速率需要的視頻壓縮能耗更小。

將圖5中的結(jié)果進(jìn)行對(duì)比，在智能網(wǎng)聯(lián)汽車距離基站較近的情況下(如車輛7～10的結(jié)果所示)，車到基站直連傳輸機(jī)制所需的視頻壓縮和通信總能耗比本文得到的視頻壓縮和通信總能耗更小。本文算法考慮邊-端協(xié)同機(jī)制，距離基站較近的智能網(wǎng)聯(lián)汽車以數(shù)據(jù)中繼的方式協(xié)助距離基站較遠(yuǎn)的智能網(wǎng)聯(lián)汽車進(jìn)行數(shù)據(jù)傳輸，因此導(dǎo)致了更多的能耗。如圖5所示，對(duì)于距離基站較遠(yuǎn)的智能網(wǎng)聯(lián)汽車(如車輛1～6)，大大降低了其視頻壓縮和通信總能耗。因此，本文算法能夠通過(guò)邊-端協(xié)同，保證單個(gè)車輛的能耗公平性。

圖5 本文算法與車到基站直連傳輸機(jī)制總能耗對(duì)比Fig.5 Comparison on total power consumption of intelligent connected vehicles due to video compression and communications by the proposed algorithm

在本文算法的邊-端協(xié)同機(jī)制下，部分距離基站較遠(yuǎn)的智能網(wǎng)聯(lián)汽車不與基站直接通信，而是利用其他智能網(wǎng)聯(lián)汽車，通過(guò)多路徑多跳路由的方式進(jìn)行數(shù)據(jù)傳輸。因此，本算法還可以減少車到基站直連通信的鏈路數(shù)量，從而節(jié)省通信帶寬資源(一般而言，車到車通信鏈路的帶寬資源可以進(jìn)行復(fù)用)。

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

本文提出了一種基于次梯度算法的分布式邊-端協(xié)同算法，通過(guò)調(diào)整視頻編碼碼率、信息源傳輸速率，以及車輛多路徑路由決策，實(shí)現(xiàn)資源分配策略。該算法可以部署在每輛智能網(wǎng)聯(lián)汽車中執(zhí)行，并且只需要與其相鄰節(jié)點(diǎn)(智能網(wǎng)聯(lián)汽車或基站)交換少量信息。

仿真實(shí)驗(yàn)結(jié)果和分析表明，本算法能在較短的時(shí)間內(nèi)達(dá)到性能穩(wěn)定狀態(tài)，能夠滿足車聯(lián)網(wǎng)場(chǎng)景下拓?fù)浣Y(jié)構(gòu)快速變化的需求；同時(shí)，相比于每輛智能網(wǎng)聯(lián)汽車直接與基站通信的機(jī)制，本算法能保證單個(gè)車輛的能耗公平性，并提高網(wǎng)絡(luò)資源利用率。