基于圖著色和三維匹配的車聯網資源分配算法

許耀華, 王慧平, 王貴竹, 朱成龍, 丁夢琴, 蔣 芳, 王 翊

(安徽大學集成電路學院, 安徽 合肥 230601)

0 引 言

近年來,互聯網和蜂窩通信技術在智能交通系統中的應用越來越廣泛,多數車輛都配備了傳感器,可以根據服務類型的不同將數據傳輸到其他車輛或基礎設施。在車輛密集地區,為了能在短時間內建立穩定可靠的連接,車輛對頻譜資源的需求越來越大[1],但頻譜資源是有限的,故需要對車聯網中的頻譜資源進行合理分配。在頻譜資源分配的底層模式下,車輛對一切(vehicle to everything, V2X)用戶可以通過資源分配[2]復用蜂窩用戶(cellular user,CU)的頻譜。但由于同時接入,V2X用戶不可避免地會對CU造成同頻干擾,故需要對頻譜資源進行合理管理,使V2X用戶在保證CU服務質量的前提下接入授權頻譜[3]。因此,如何利用資源分配來降低干擾是車聯網中一個亟需解決的問題。

在現有的車聯網資源分配研究中,文獻[4-5]的解決方案是對基站進行無線資源管理,無線資源管理在基站的介質訪問控制層執行,并在時域中為CU和V2X用戶分配頻譜資源,以此來最小化 CU和V2X用戶之間發生沖突的概率,并提高頻譜效率和網絡吞吐量;文獻[6]提出一種基于地理的頻譜資源調度方案,車輛根據其位置和在道路上的排序來自主選擇頻譜資源,其目標是通過協調車輛之間的子信道選擇來降低數據包的沖突,所提方案顯著改善了由于數據包沖突而導致的數據丟失問題;文獻[7]研究了CU和V2X 用戶在未授權頻譜上的共存問題;文獻[8-10]考慮了CU和V2X用戶的一對一復用,在此復用模式下,V2X用戶對CU造成的干擾較低,但是頻譜利用率不高;在文獻[11-12]中,單個CU的頻譜資源可以同時被多個V2X用戶復用,此時的頻譜利用率較高,但僅僅考慮了CU和V2X用戶之間的信道匹配,并未考慮到CU、V2X用戶以及資源塊(resource block, RB)這三者之間的信道分配;文獻[13]考慮到了車輛對基礎設施(vehicle to infrastructure, V2I)鏈路、車輛對車輛(vehicle to vehicle, V2V)鏈路以及RB這三者之間的信道分配,該文獻將互干擾嚴重的V2V鏈路劃分成簇并通過三維匹配算法進行了無線資源匹配,從而獲得了網絡吞吐量最大的資源分配方案。但該方案在V2V簇劃分過程中,對簇內首條V2V鏈路的選擇是隨機的,這導致V2V簇劃分不穩定,嚴重影響分配方案的最終結果。將圖著色法用于分簇問題在文獻[14]中已經被證明是可用的,使用圖著色法進行V2V鏈路分簇可以解決上述問題。

本文在文獻[13]的研究基礎上提出一種基于圖著色和三維匹配的車聯網資源分配算法,建立以最大化V2I鏈路總和速率、保障V2I服務質量要求為目標的分配優化問題。所提算法利用圖著色法對V2V鏈路進行分簇,并使用三維匹配算法進行信道分配,在保證V2I鏈路服務質量和V2V鏈路接入率相對平衡的前提下提升了V2I鏈路總和速率,并使系統在迭代次數相對較少的情況下收斂到最優。

1 系統模型

考慮一個支持設備到設備(device to device, D2D)的車聯網通信場景,其中存在M輛進行V2I通信的車輛和N對以D2D通信形式進行本地數據交換的V2V通信鏈路,如圖1所示。為了簡化系統,假設所有的車輛在同一時間只能進行V2I通信或V2V通信。將V2I鏈路集表示為M={1,2,…,M},V2V鏈路集表示為N={1,2,…,N},其中M?N。假設頻譜資源被分成F個RB,表示為F={1,2,…,F},且M=F。為了提高頻譜利用率,分配給V2I鏈路的上行資源被V2V鏈路正交復用,且多個V2V鏈路可以同時復用同一V2I鏈路的頻譜資源。為了控制干擾,每個V2I鏈路只能正交占用一個RB。

圖1 系統模型Fig.1 System model

車輛的快速移動使得系統模型中的小尺度衰落參數發生變化,如果將小尺度衰落參數傳送給基站,會造成信息開銷增大和時延增加,故在高速移動場景中捕捉瞬時的信道狀態信息是不切實際的。本文假定基站能夠獲得變化緩慢的大尺度衰落參數和小尺度衰落參數的統計特性。

(1)

表1 信道增益符號表

(2)

(3)

(4)

(5)

2 問題建模

給定一組可用RB,以V2I鏈路的總和速率最大化為目標,同時保證V2I鏈路的最低通信服務質量和V2V鏈路的可靠性,將車輛通信問題建模為一個優化問題:

(6)

(6a)

(6b)

(6c)

(6d)

(6e)

(6f)

(6g)

(6h)

3 基于圖著色和三維匹配的資源分配算法

基于圖著色和三維匹配的資源分配算法由3個步驟實現。第1步,V2V鏈路分簇;第2步,功率控制;第3步,三維匹配算法。具體流程如圖2所示。

通過構建干擾圖來表示通信鏈路之間的干擾。首先,通過干擾圖得到鏈路之間的干擾情況,利用圖著色法對V2V鏈路進行分簇,得到V2V鏈路簇集;其次,對V2I鏈路和V2V鏈路進行功率控制,得到相對較佳的發射功率;最后,利用三維匹配算法解決V2I鏈路、V2V鏈路簇集、RB三者之間的信道分配問題。

圖2 算法流程圖Fig.2 Algorithm flowchart

3.1 V2V鏈路分簇

本文算法通過V2V鏈路之間的干擾構建干擾圖G=(V,E),頂點集V包括每個V2V鏈路(每個V2V鏈路代表一個頂點,頂點位置位于V2V鏈路連接發射端和接收端的中點),v={vj,j=1,2,…,N}。E(G)表示使用相同頻譜資源時圖G中頂點之間的干擾邊矩陣,表示為N×N的矩陣,E(G)={ei, j,i=1,2,…,N;j=1,2,…,N},ei, j∈{0,1},其中ei, j=1表示第i條V2V鏈路vi和第j條V2V鏈路vj之間存在不可忽略的干擾且兩頂點之間存在相連的邊。在這種情況下,vj是vi的鄰居,并將vi、vj分別加入vj和vi的鄰居集interfi、interfj中。由于強干擾,同一RB不能分配給兩個相鄰的通信鏈路。這類似于頂點著色問題,其中由同一條邊連接的兩頂點不能著相同顏色。因此,當一組頂點被涂上相同顏色時,表示允許使用相同的RB。

3.1.1 干擾圖的建立

步驟 1初始化干擾圖,隨機放置N條V2V鏈路;

3.1.2 V2V對的分簇

按照上述方法,可以將V2V鏈路間的干擾關系映射為干擾圖,基于此,可以將V2V鏈路分為若干個不相交的簇。本文采用圖著色法對V2V鏈路進行分簇。具體算法如算法1所示。

算法1 基于圖著色的分簇算法1:初始化:根據第3.1.1節構建干擾圖,并計算每個頂點的飽和度;2:頂點著色While 存在未被染色的頂點 for count=1:f if 頂點vi的飽和度∑Nj=1ei,j的值最大 vi=count if vj?interfi vj=count else count=count+1 end if end if end for end while

由以上兩步得到V2V鏈路分簇結果,將劃分到同一簇的V2V鏈路看作一個整體,不同簇間復用不同的頻譜資源,故不在同一簇的V2V鏈路之間將不會產生干擾。

3.2 功率控制

為了實現更高的V2I鏈路總和速率以及保證V2V鏈路的服務質量,需要合理控制V2I鏈路及V2V鏈路的發射功率。

假設分配給第m條V2I鏈路的頻譜資源f被第k個V2V鏈路簇集Ck復用,故目標函數式(6)變為由式(7)組成的方程組:

(7)

(7a)

(7b)

(7c)

式(7a)化簡得到

(8)

假設所有V2V鏈路都滿足信道要求,將式(8)取等號得到

(9)

(10)

(11)

3.3 信道分配

圖3 三維匹配圖Fig.3 Three-dimensional matching map

在上述 V2I-RB-V2V鏈路簇集的加權三維匹配算法求解過程中,構建三維均勻超圖的時間復雜度為O(M3),加權三維匹配算法的時間復雜度為O(M5logM)。此外,基于著色的V2V鏈路分簇的時間復雜度為O(N2)。因此,本文所提算法的總的時間復雜度為O(c(NM3+M4N+M6NlogM)),其中c為迭代次數。此外,基于迭代的頻譜分配算法的時間復雜度為O(c(M2N2+M3N+M4N)),文獻[13]所提算法的時間復雜度為O(c(M2N2+M4N+M6NlogM))。

4 仿真結果及分析

4.1 實驗條件和仿真設置

本文利用Matlab仿真平臺對上述提出的基于圖著色和三維匹配的資源分配算法進行仿真。仿真環境根據第三代合作伙伴計劃(3rd generation partnership project, 3GPP)組織的TR36.885設置。具體參數見表2。

仿真針對圖1所示的公路場景,假設車輛的到達服從泊松分布,車輛之間的平均距離為2.5倍車速。信道模型為基于WINNER Ⅱ信道模型建立的V2V和V2I信道模型,基站位于蜂窩區域的中心,來進行消息的接收和發送。

表2 仿真參數

4.2 仿真結果及分析

基于表2的參數設置進行仿真,本文將基于圖著色和三維匹配的資源分配算法與基于迭代的頻譜分配算法、文獻[13]中基于三維匹配的隨機頻譜分配算法進行對比,關注V2I鏈路總和速率、V2V鏈路接入率等性能指標,對比不同發射功率、車輛速度、V2V鏈路數量和迭代次數下的V2I鏈路總和速率。

圖4展示了活躍V2V鏈路數量對V2I鏈路總和速率的影響。從圖4中可以看到,隨著V2V鏈路數量的增加,3種算法的V2I鏈路總和速率都會降低。這是因為,隨著V2V鏈路的增加,復用相同鏈路資源的V2V鏈路數量增加,這將對V2I鏈路產生更多干擾,進一步降低了V2I鏈路的接收信干噪比。此外,從容量曲線的陡峭斜率可以看出,對比算法對V2V鏈路的增加非常敏感,而基于圖著色和三維匹配的資源分配算法的容量曲線斜率相對平緩。分析原因可知,在這些情況下,V2V鏈路對V2I鏈路產生的干擾非常嚴重,并且V2I鏈路總和速率受到很大影響,從而性能降低。而在V2V鏈路數量較多時,本文所提算法通過犧牲V2V鏈路的接入率換取信干噪比允許范圍內V2V鏈路的可靠性,對V2I鏈路總和速率的影響相對較低。

圖5展示了不同迭代次數下基于圖著色和三維匹配的資源分配算法和對比算法的V2I鏈路總和速率性能,其中迭代次數不斷增加,以更新V2V聚類。從圖5可以看出,本文所提算法迅速收斂到次優解,并且不會隨著迭代次數的增加而改善,而對比算法則在本文所提算法達到次優解時還保持增長,最終收斂到穩定的解決方案。這表明所提出的算法能在較少的迭代次數下提升性能并最終收斂到次優解。這是因為文獻[13]算法在對V2V鏈路進行簇劃分的過程中,簇內的第一條V2V鏈路是隨機選擇的,而基于迭代的頻譜分配算法的RB是隨機分配的,需要經過較多次迭代才能達到穩定。

圖4 V2I鏈路總和速率與V2V鏈路數量的關系Fig.4 Relationship between the sum rate of V2I links and the number of V2V links

圖5 V2I鏈路總和速率與迭代次數的關系Fig.5 Relationship between the sum rate of V2I links and the number of iterations

圖6表示不同發射功率下的V2I鏈路總和速率與汽車速度之間的關系。如圖6所示,隨著車速的加快,3種算法的V2I鏈路總和速率都在下降,這是由于車速的增大使得車輛之間的安全距離增大,為了保證V2V鏈路的可靠性,負責V2V通信的車載終端只能增加發射功率來提高V2V鏈路的可靠性,V2V鏈路功率增加導致V2V鏈路對V2I鏈路的干擾增加,使得V2I鏈路的速率減小,最終造成V2I鏈路總和速率下降。本文所提算法的性能優于其他兩種算法,這是由于使用三維匹配算法帶來了更優的匹配靈活性。

圖7為3種算法的V2V鏈路成功接入率。文獻[13]算法和基于迭代的頻譜分配算法的V2V鏈路接入率始終為100%,而本文所提算法的V2V鏈路接入率隨著V2V鏈路的增加而降低。這是因為兩種對比算法只簡單地考慮了所有V2V鏈路都能復用V2I鏈路頻譜資源的情況,并未考慮到當一些信道條件較差的V2V鏈路復用V2I鏈路頻譜資源時,會降低V2I鏈路的服務質量。而本文所提算法更好地平衡了V2I鏈路服務質量和V2V鏈路接入率。

圖6 V2I鏈路總和速率與車輛速度的關系Fig.6 Relationship between V2I link sum rate and vehicle speed

圖7 V2V鏈路成功接入率與V2V鏈路數量的關系Fig.7 Relationship between the successful access rate of V2V links and the number of V2V links

圖4～圖6對比了各資源分配算法的V2I鏈路總和速率。由對比結果可以發現,所提算法的V2I鏈路總和速率明顯優于基于迭代的頻譜分配算法和文獻[13]所提出的算法,但在網絡中V2V鏈路數量較多時,本文所提算法的V2V鏈路接入率略差。

5 結 論

本文考慮到車聯網通信場景中上行通信鏈路的資源分配問題,為了優化V2I鏈路的總和速率,解決V2V鏈路復用V2I鏈路產生的干擾,提出一種基于圖著色和三維匹配的車聯網資源分配算法。該算法通過圖著色法對V2V鏈路進行分簇,通過求解V2I鏈路和V2V鏈路的發射功率,將優化問題轉化為V2I鏈路、V2V簇和RB之間的三維匹配問題,并利用三維匹配算法進行求解。理論分析及仿真結果表明,該算法在很大程度上提高了V2I鏈路總和速率,并加速了算法收斂性。后續研究重點在于如何在提高V2I鏈路總和速率的同時,保持V2V鏈路的百分百接入率。