V2V通信中基于超圖理論的資源分配算法

張家波，吳昌玉，袁 凱

(重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065)

0 引 言

車與車(vehicle to vehicle，V2V)通信在改善交通安全性，交通效率和道路服務(wù)質(zhì)量等方面發(fā)揮了重要作用[1]。在動態(tài)且密集的交通環(huán)境下，車輛周期性地向鄰近車輛廣播合作意識消息(cooperative awareness message，CAM)，例如車輛的轉(zhuǎn)向、位置、速度等，提高了車輛之間相互感知的能力，并在很大程度上減少了因駕駛?cè)藛T的視線盲區(qū)所造成的安全隱患，從而避免交通事故的發(fā)生[2]。

干擾是無線通信系統(tǒng)中的固有現(xiàn)象[3]。由于無線信道的廣播特性，每當(dāng)多個(gè)發(fā)射機(jī)在同一頻帶中同時(shí)廣播時(shí)，就會對其它接收機(jī)產(chǎn)生干擾。目前基于長期演進(jìn)車對車(long term evolution-vehicle to vehicle，LTE-V2V)下的資源分配研究還存在不足[4]。在文獻(xiàn)[5]中，作者通過車輛聚類將資源分配問題轉(zhuǎn)換為二分圖的最大權(quán)重匹配問題以最大化系統(tǒng)總?cè)萘?。文獻(xiàn)[6]為限制累積干擾，提出了基于矩陣譜半徑估計(jì)理論的資源分配方案，該方案將可靠性要求轉(zhuǎn)換為矩陣譜半徑的約束，最大化同時(shí)傳輸?shù)逆溌窋?shù)量。文獻(xiàn)[7]提出了基于車輛地理位置的資源分配方案，該方案將小區(qū)的覆蓋區(qū)域劃分若干區(qū)域，并為每個(gè)區(qū)域分配一組專用資源，從而實(shí)現(xiàn)資源的重用。在文獻(xiàn)[8]中，作者首先根據(jù)車輛行駛方向劃分資源池，然后基于能量感知在給定的資源池里選擇傳輸資源，減少了資源沖突和帶內(nèi)發(fā)射對車輛間的潛在干擾。文獻(xiàn)[9]提出了基于動態(tài)地理的資源選擇算法，通過資源池的劃分提高資源的利用率，然而該方案需要許多參數(shù)設(shè)置，其影響尚未在文獻(xiàn)中得到很好的研究。

針對現(xiàn)有文獻(xiàn)中V2V廣播通信中集中式資源調(diào)度算法較少考慮半雙工約束和累積干擾的問題，提出了一種低復(fù)雜度的超圖著色資源分配算法。仿真結(jié)果表明，該算法能進(jìn)一步減少更新時(shí)延，并提高數(shù)據(jù)包接收率。

1 系統(tǒng)模型及問題描述

1.1 系統(tǒng)模型

在城市道路場景下，車輛周期性(100 ms)生成CAM消息，并發(fā)送給鄰居車輛,如圖1所示。

圖1 V2V廣播通信場景

為確保安全信息傳輸?shù)目煽啃?，V2V通信使用專用資源池進(jìn)行資源分配[10]。專用資源池在時(shí)域上分為100個(gè)子幀(每個(gè)子幀1 ms)，頻域上分為50個(gè)資源塊(resource block，RB)，每個(gè)數(shù)據(jù)包所占用的RB數(shù)量由傳輸?shù)恼{(diào)制與編碼策略(modulation and coding scheme，MCS)決定[2]。如圖2所示，資源池中資源主要被用于傳輸CAM數(shù)據(jù)包以及調(diào)度分配(scheduling assignment，SA)信息，CAM數(shù)據(jù)包傳輸所用資源主要通過SA進(jìn)行傳輸。如果車輛在一個(gè)子幀中充當(dāng)接收車輛(RX)，則不能在該子幀中充當(dāng)發(fā)送車輛(TX)[3]。

圖2 資源池

在密集的網(wǎng)絡(luò)拓?fù)渲校饕嬖趦蓚€(gè)問題：①頻率復(fù)用帶來的干擾，當(dāng)多個(gè)TX在發(fā)送數(shù)據(jù)包時(shí)選擇相同資源時(shí)，會對共有的一跳鄰居車輛產(chǎn)生嚴(yán)重干擾，例如圖1的TX1和TX2對RX1/RX2的干擾。②半雙工約束[11]，彼此處于一跳范圍內(nèi)的車輛預(yù)定在相同的子幀里進(jìn)行廣播，如圖1中TXj和TXk在同一子幀下廣播消息，則彼此間接收不到對方的消息。

1.2 問題描述

RXm在第 (t,f) 個(gè)時(shí)頻資源中從TXj處接收到的信干噪比(signal to interference plus noise ratio，SINR)表示為

(1)

本數(shù)據(jù)包的數(shù)量，一個(gè)傳輸周期內(nèi)成功解碼數(shù)據(jù)包的數(shù)量表示為

(2)

(3)

(4)

(5)

(6)

式中：dj,j′表示TXj與TXj′的距離，式(4)表示由于半雙工的性質(zhì)，彼此通信范圍的內(nèi)的任何車輛不能同時(shí)在一個(gè)子幀內(nèi)作為TX，式(5)表示車輛只能占用一個(gè)時(shí)頻資源。

2 資源分配算法

式(3)中給出的優(yōu)化問題是NP難組合優(yōu)化問題，窮舉法是解決優(yōu)化問題的直接方法，但是該算法具有很高的計(jì)算復(fù)雜度，為了在計(jì)算復(fù)雜度與數(shù)據(jù)包接收率之間實(shí)現(xiàn)適當(dāng)?shù)钠胶?，本文基于超圖著色算法對其進(jìn)行求解，以實(shí)現(xiàn)次優(yōu)解。

2.1 干擾超圖的建立

在傳統(tǒng)的動態(tài)調(diào)度中，資源分配可能導(dǎo)致顯著的延遲，因?yàn)橛脩粜枰槍γ總€(gè)數(shù)據(jù)包向基站發(fā)送資源請求消息。為了減少UL等待時(shí)間以及減輕基站負(fù)載，基站進(jìn)行集中式的半靜態(tài)調(diào)度(semi-persistent scheduling，SPS)?；驹谝粋€(gè)或多個(gè)傳輸周期組成的每個(gè)SPS周期的開始處將預(yù)定義的資源分配給用戶，資源分配方案在SPS周期的每個(gè)傳輸周期內(nèi)保持不變[13]。為了充分利用基站獲得的全局位置信息，基站在每個(gè)SPS周期的開始處構(gòu)建干擾超圖，并確定TX-RX在資源池的分配。

為了減輕頻率復(fù)用帶來的干擾，必須要讓復(fù)用相同資源且傳輸不同數(shù)據(jù)包的發(fā)送車輛相距一定的距離。當(dāng)不同的TX之間選擇相同資源發(fā)送數(shù)據(jù)包時(shí)，主要干擾是TX對其余V2V鏈路的RX的干擾，如圖3所示。

圖3 V2V廣播群距離

為降低計(jì)算復(fù)雜度，本文進(jìn)行簡化分析，僅考慮距離損耗對信號傳輸?shù)挠绊慬3]，考慮最差的情況，即在傳輸范圍內(nèi)發(fā)送車輛前方與之具有最小信道增益的接收車輛，以及在發(fā)送車輛后方與之具有最小信道增益的接收車輛，將其與發(fā)送車輛視為兩個(gè)V2V通信組。

傳統(tǒng)圖的構(gòu)建中，連接兩個(gè)頂點(diǎn)的邊緣不足以模擬無線網(wǎng)絡(luò)中的干擾，因?yàn)橐恍┤醺蓴_源可能構(gòu)成強(qiáng)烈的累積干擾源以影響鏈路質(zhì)量。因此，本文通過超圖原理進(jìn)行干擾建模，關(guān)于超圖的相關(guān)概念可以參見文獻(xiàn)[14]。

干擾超圖的建立主要分為以下3個(gè)步驟：

(1)相鄰車輛列表。因?yàn)閮商鴤鬏敺秶鷥?nèi)的車輛如果復(fù)用同一資源會對共有的一跳鄰居車輛產(chǎn)生嚴(yán)重干擾，所以車輛i兩跳傳輸范圍內(nèi)的車輛都會進(jìn)入其相鄰車輛列表，在兩跳傳輸范圍以外，車輛j會進(jìn)入車輛i的相鄰車輛列表,如果滿足式(7)或者式(8)

(7)

(8)

式中：η1是車輛i選擇相鄰車輛的門限值，這一步主要是為了排除對車輛i的干擾完全可以忽略的車輛，具體如圖4(a)所示。其中Hi,k1和Hi,k2分別表示第i個(gè)廣播群中TX在發(fā)送范圍內(nèi)與兩個(gè)接收車輛k1和k2之間的信道增益，Hj,k1和Hj,k2分別表示第j個(gè)廣播群TX到第i個(gè)廣播群的第k1個(gè)和第k2個(gè)接收車輛的信道增益。

(2)獨(dú)立干擾者。在鄰近車輛列表中尋找獨(dú)立干擾者，車輛i兩跳傳輸范圍以內(nèi)的車輛都作為其獨(dú)立干擾者構(gòu)建普通邊，車輛i兩跳傳輸范圍以外的相鄰車輛會作為車輛i的獨(dú)立干擾者，如果滿足式(9)或者式(10)

(9)

(10)

式中：η2是超圖構(gòu)建普通邊的門限值，這一步的主要作用是為了構(gòu)建對車輛i有過大干擾的車輛。一跳鄰居用實(shí)線連接，一跳鄰居外用虛線連接，如圖4(b)所示。并把與i構(gòu)建普通邊的車輛在i的相鄰車輛列表中去除。

(3)累加干擾者。在剩余的相鄰列表中尋找累加干擾者并構(gòu)建超邊，剩余的相鄰車輛會作為車輛i的累加干擾者，如果滿足式(11)或者式(12)

(11)

(12)

式中：η3表示累加干擾的門限值，為了簡化，Nm值取2，也就是只考慮3個(gè)頂點(diǎn)的超邊,如圖4(c)所示。最后形成的干擾超圖如圖4(d)所示，具體算法見表1。

圖4 干擾超圖構(gòu)建

表1 超圖構(gòu)建算法

2.2 超圖著色

2.2.1 二重著色

在上述構(gòu)建的干擾超圖中，考慮以下兩種通信干擾：

(1)直接沖突：一跳鄰居范圍內(nèi)的TX分配了相同的子幀。(半雙工約束)

(2)間接沖突：在彼此干擾范圍內(nèi)TX分配了相同的子幀和子信道。

為TX分配信道和子幀的問題可以轉(zhuǎn)換成圖頂點(diǎn)著色問題，將為頂點(diǎn)分配時(shí)頻資源看作為分配兩種顏色，從而將資源分配問題轉(zhuǎn)化為頂點(diǎn)二重著色問題，對應(yīng)關(guān)系見表2[15]。

為定量描述著色沖突，V={v1,v2,…,vN} 表示N個(gè)頂點(diǎn)，ti表示vi選擇的主色，fi表示vi選擇的副色，si=(ti,fi) 是頂點(diǎn)vi的著色方案，S={si|i=1,2,…,N} 表示整個(gè)頂點(diǎn)干擾圖的著色方案。如圖5所示，單跳鄰居范圍內(nèi)的車輛由實(shí)線相連，相互干擾范圍內(nèi)車輛由虛線相連。將每個(gè)頂點(diǎn)分成兩半，左邊表示主色，代表為發(fā)送車輛分配的子幀，右邊表示副色，代表為發(fā)送車輛分配的子信道。為干擾超圖分配顏色時(shí)，由實(shí)線連接的兩頂點(diǎn)必須主色不同，虛線連接的兩頂點(diǎn)則必須主色或副色不同[3]。

表2 子幀和信道的分配與頂點(diǎn)二重著色問題的對應(yīng)關(guān)系

圖5 信道子幀分配示例

2.2.2 基于超圖的二重著色算法

超圖構(gòu)建后，為超圖H著色，處于同一超邊的頂點(diǎn)至少有兩個(gè)頂點(diǎn)被分配不同的顏色，以這種方式減輕累積干擾，算法中相關(guān)名詞定義請參見文獻(xiàn)[14]。算法的基本思路：首先根據(jù)圖中頂點(diǎn)的mono-degree將超圖H分解，然后從分解的H中得到頂點(diǎn)的排序，最后基于點(diǎn)排序的相反順序?yàn)閷?yīng)頂點(diǎn)著色。區(qū)別于貪心算法的求最小顏色數(shù)，根據(jù)調(diào)度方式以及信標(biāo)消息的周期性，時(shí)頻資源的數(shù)量是固定的，因此為了使每個(gè)資源能得到合理的使用，從可用的顏色集合里隨機(jī)選擇一個(gè)顏色進(jìn)行著色，在最差的情況下，如果沒有可用的顏色，則選擇這樣的一個(gè)顏色，在這個(gè)顏色上，待分配節(jié)點(diǎn)離正在使用這個(gè)顏色的最近節(jié)點(diǎn)的距離最大，如式(13)所示

C(i)=argmaxk(minj∈NkDij)

(13)

式中：C(i) 表示節(jié)點(diǎn)i的資源選擇，Dij表示車輛i與車輛j之間的距離，這個(gè)資源給出了它和其它共享該資源的對等體之間最好的距離，具體算法見表3，基站半靜態(tài)資源調(diào)度見表4。

3 仿 真

使用文獻(xiàn)[16]設(shè)計(jì)的LTEV2Vsim模擬器進(jìn)行仿真，并考慮文獻(xiàn)[17]中定義的道路模型，如圖6所示。現(xiàn)有的資源管理方案將可靠性要求直接轉(zhuǎn)換成SINR約束，即SINR應(yīng)該大于給定的目標(biāo)值。在LTE中的不同的MCS下，保證可靠性要求的SINR閾值也是不同的。本文分別就MCS=4，8時(shí)進(jìn)行仿真分析，仿真參數(shù)見表5和表6，RB-C表示傳輸一個(gè)CAM消息需要的RB數(shù)量，NR表示一個(gè)周期內(nèi)的資源數(shù)量。

表3 基于超圖的二重著色資源分配算法

表4 基站半靜態(tài)資源調(diào)度

圖6 道路撒點(diǎn)模型

通過將本文提出的基于超圖理論的二重著色算法(hypergraph based)與基于矩陣譜半徑算法(matrix spectral radius)和基于地理位置算法(geographic based)對比。為了評估CAM傳輸時(shí)的通信質(zhì)量，主要考慮以下兩個(gè)參數(shù)：

表5 系統(tǒng)仿真配置

表6 LTE-V調(diào)制和編碼方案及相應(yīng)的值

(1)數(shù)據(jù)包接收率：場景中所有接收節(jié)點(diǎn)從數(shù)據(jù)源節(jié)點(diǎn)正確接收數(shù)據(jù)包的數(shù)量，與所有發(fā)送節(jié)點(diǎn)發(fā)送數(shù)據(jù)包的比值。具體表示為

(14)

式中：PRR表示數(shù)據(jù)包接收率，Nneighbors表示場景中所有車輛的鄰居數(shù)量之和。Nsuccess表示場景中車輛節(jié)點(diǎn)成功接收數(shù)據(jù)包的數(shù)量。

(2)數(shù)據(jù)包更新時(shí)延：車輛節(jié)點(diǎn)正確接收信標(biāo)的時(shí)間差，具體表示為

tu=tn+1-tn

(15)

式中：tu表示更新時(shí)延，tn+1表示車輛節(jié)點(diǎn)第n+1次正確接收數(shù)據(jù)包的時(shí)刻，tn表示車輛節(jié)點(diǎn)第n次正確接收數(shù)據(jù)包的時(shí)刻。通過更新時(shí)延的累積分布函數(shù)(cumulative distribution function，CDF)評估通信等待時(shí)間。

圖7和圖8分別就MCS=4，MCS=8時(shí)，比較了3種算法中發(fā)送車輛傳輸距離之間的關(guān)系與數(shù)據(jù)包接收率的關(guān)系。從圖7和圖8中可以看出，MCS=8時(shí)的PRR相比MCS=4時(shí)的PRR更高，因?yàn)樵诓煌腗CS下，可分配的資源數(shù)以及保證可靠性要求的SINR閾值也是不同的。當(dāng)MCS的值固定時(shí)，隨著TX傳輸距離的逐漸增加，收發(fā)車輛傳輸范圍內(nèi)會有越來越多的其它TX對RX產(chǎn)生干擾，從而導(dǎo)致數(shù)據(jù)包接收率也逐漸降低，因此可以推出在MCS值固定時(shí)，距離對數(shù)據(jù)包接收率帶來負(fù)向的影響。分析以上仿真結(jié)果，在所有情況下，Geographic算法基于車輛的地理位置復(fù)用，未充分考慮用戶間的干擾影響，數(shù)據(jù)包接收率最低。Matrix spectral radius算法可以改善系統(tǒng)PRR性能，但是Hypergraph算法的數(shù)據(jù)包接收率大于Matrix spectral radius算法，因?yàn)镠ypergraph算法相較于Matrix spectral radius算法在考慮累積干擾的同時(shí)，還考慮了半雙工約束帶來的數(shù)據(jù)包丟失。

圖7 當(dāng)MCS=4時(shí)，數(shù)據(jù)包接收率對比

圖8 當(dāng)MCS=8時(shí)，數(shù)據(jù)包接收率對比

圖9和圖10比較了MCS=4，MCS=8時(shí)，r=100 m時(shí)3種算法的數(shù)據(jù)包更新時(shí)延的CDF，從圖中可以看出，MCS=4時(shí)，Hypergraph算法的更新時(shí)延在0.2 s以內(nèi)已經(jīng)達(dá)到99%，保證了較低的通信延遲。Matrix spectral radius算法在0.7 s達(dá)到了99%，Geographic在0.8 s內(nèi)達(dá)到了99%。MCS=8時(shí)，Hypergraph算法依舊保證了較低的通信延遲，更新時(shí)延在0.2 s以內(nèi)已經(jīng)達(dá)到99%，Matrix spectral radius算法在0.5 s達(dá)到了99%，Geographic在 0.7 s 內(nèi)達(dá)到了99%。這些結(jié)果表明了Hypergraph算法保證了較低的連續(xù)錯(cuò)誤發(fā)生的概率。

圖9 更新時(shí)延的CDF(MCS=4，r=100 m)

圖10 更新時(shí)延的CDF(MCS=8，r=100 m)

4 結(jié)束語

本文主要針對高密度的交通環(huán)境下資源分配問題，提出了一種基于超圖理論的資源分配算法。該算法中將超圖理論和二重著色結(jié)合，降低了累積干擾帶來的影響，并減少了半雙工約束導(dǎo)致的數(shù)據(jù)包丟失。仿真結(jié)果表明，基于超圖理論的算法可以在通信范圍內(nèi)提高數(shù)據(jù)包的接收率，并保證了較低的連續(xù)錯(cuò)誤發(fā)生的概率。

本文研究是基于單小區(qū)場景下的資源分配，在多小區(qū)場景下，為了避免基站覆蓋范圍邊緣車輛受到干擾，鄰近基站需要知道彼此的資源分配結(jié)果，通過基站之間的協(xié)調(diào)從而更加合理的利用資源。