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

張家波，吳昌玉，袁 凱

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

0 引 言

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

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

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

1 系統模型及問題描述

1.1 系統模型

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

圖1 V2V廣播通信場景

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

圖2 資源池

在密集的網絡拓撲中，主要存在兩個問題：①頻率復用帶來的干擾，當多個TX在發送數據包時選擇相同資源時，會對共有的一跳鄰居車輛產生嚴重干擾，例如圖1的TX1和TX2對RX1/RX2的干擾。②半雙工約束[11]，彼此處于一跳范圍內的車輛預定在相同的子幀里進行廣播，如圖1中TXj和TXk在同一子幀下廣播消息，則彼此間接收不到對方的消息。

1.2 問題描述

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

(1)

本數據包的數量，一個傳輸周期內成功解碼數據包的數量表示為

(2)

(3)

(4)

(5)

(6)

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

2 資源分配算法

式(3)中給出的優化問題是NP難組合優化問題，窮舉法是解決優化問題的直接方法，但是該算法具有很高的計算復雜度，為了在計算復雜度與數據包接收率之間實現適當的平衡，本文基于超圖著色算法對其進行求解，以實現次優解。

2.1 干擾超圖的建立

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

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

圖3 V2V廣播群距離

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

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

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

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

(7)

(8)

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

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

(9)

(10)

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

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

(11)

(12)

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

圖4 干擾超圖構建

表1 超圖構建算法

2.2 超圖著色

2.2.1 二重著色

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

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

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

為TX分配信道和子幀的問題可以轉換成圖頂點著色問題，將為頂點分配時頻資源看作為分配兩種顏色，從而將資源分配問題轉化為頂點二重著色問題，對應關系見表2[15]。

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

表2 子幀和信道的分配與頂點二重著色問題的對應關系

圖5 信道子幀分配示例

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

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

C(i)=argmaxk(minj∈NkDij)

(13)

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

3 仿 真

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

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

表4 基站半靜態資源調度

圖6 道路撒點模型

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

表5 系統仿真配置

表6 LTE-V調制和編碼方案及相應的值

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

(14)

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

(2)數據包更新時延：車輛節點正確接收信標的時間差，具體表示為

tu=tn+1-tn

(15)

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

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

圖7 當MCS=4時，數據包接收率對比

圖8 當MCS=8時，數據包接收率對比

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

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

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

4 結束語

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

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