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

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

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

1.1 系統(tǒng)模型

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

圖1 V2V廣播通信場景

為確保安全信息傳輸?shù)目煽啃?，V2V通信使用專用資源池進行資源分配[10]。專用資源池在時域上分為100個子幀(每個子幀1 ms)，頻域上分為50個資源塊(resource block，RB)，每個數(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進行傳輸。如果車輛在一個子幀中充當(dāng)接收車輛(RX)，則不能在該子幀中充當(dāng)發(fā)送車輛(TX)[3]。

圖2 資源池

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

1.2 問題描述

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

(1)

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

(2)

(3)

(4)

(5)

(6)

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

2 資源分配算法

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

2.1 干擾超圖的建立

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

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

圖3 V2V廣播群距離

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

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

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

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

(7)

(8)

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

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

(9)

(10)

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

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

(11)

(12)

式中：η3表示累加干擾的門限值，為了簡化，Nm值取2，也就是只考慮3個頂點的超邊,如圖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)換成圖頂點著色問題，將為頂點分配時頻資源看作為分配兩種顏色，從而將資源分配問題轉(zhuǎn)化為頂點二重著色問題，對應(yīng)關(guān)系見表2[15]。

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

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

圖5 信道子幀分配示例

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

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

C(i)=argmaxk(minj∈NkDij)

(13)

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

3 仿 真

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

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

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

圖6 道路撒點模型

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

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

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

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

(14)

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

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

tu=tn+1-tn

(15)

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

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

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

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

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

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

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

4 結(jié)束語

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

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