基于圖著色和三維匹配的車聯(lián)網(wǎng)資源分配算法

許耀華, 王慧平, 王貴竹, 朱成龍, 丁夢(mèng)琴, 蔣 芳, 王 翊

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

0 引 言

近年來(lái),互聯(lián)網(wǎng)和蜂窩通信技術(shù)在智能交通系統(tǒng)中的應(yīng)用越來(lái)越廣泛,多數(shù)車輛都配備了傳感器,可以根據(jù)服務(wù)類型的不同將數(shù)據(jù)傳輸?shù)狡渌囕v或基礎(chǔ)設(shè)施。在車輛密集地區(qū),為了能在短時(shí)間內(nèi)建立穩(wěn)定可靠的連接,車輛對(duì)頻譜資源的需求越來(lái)越大[1],但頻譜資源是有限的,故需要對(duì)車聯(lián)網(wǎng)中的頻譜資源進(jìn)行合理分配。在頻譜資源分配的底層模式下,車輛對(duì)一切(vehicle to everything, V2X)用戶可以通過(guò)資源分配[2]復(fù)用蜂窩用戶(cellular user,CU)的頻譜。但由于同時(shí)接入,V2X用戶不可避免地會(huì)對(duì)CU造成同頻干擾,故需要對(duì)頻譜資源進(jìn)行合理管理,使V2X用戶在保證CU服務(wù)質(zhì)量的前提下接入授權(quán)頻譜[3]。因此,如何利用資源分配來(lái)降低干擾是車聯(lián)網(wǎng)中一個(gè)亟需解決的問(wèn)題。

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

本文在文獻(xiàn)[13]的研究基礎(chǔ)上提出一種基于圖著色和三維匹配的車聯(lián)網(wǎng)資源分配算法,建立以最大化V2I鏈路總和速率、保障V2I服務(wù)質(zhì)量要求為目標(biāo)的分配優(yōu)化問(wèn)題。所提算法利用圖著色法對(duì)V2V鏈路進(jìn)行分簇,并使用三維匹配算法進(jìn)行信道分配,在保證V2I鏈路服務(wù)質(zhì)量和V2V鏈路接入率相對(duì)平衡的前提下提升了V2I鏈路總和速率,并使系統(tǒng)在迭代次數(shù)相對(duì)較少的情況下收斂到最優(yōu)。

1 系統(tǒng)模型

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

圖1 系統(tǒng)模型Fig.1 System model

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

(1)

表1 信道增益符號(hào)表

(2)

(3)

(4)

(5)

2 問(wèn)題建模

給定一組可用RB,以V2I鏈路的總和速率最大化為目標(biāo),同時(shí)保證V2I鏈路的最低通信服務(wù)質(zhì)量和V2V鏈路的可靠性,將車輛通信問(wèn)題建模為一個(gè)優(yōu)化問(wèn)題:

(6)

(6a)

(6b)

(6c)

(6d)

(6e)

(6f)

(6g)

(6h)

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

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

通過(guò)構(gòu)建干擾圖來(lái)表示通信鏈路之間的干擾。首先,通過(guò)干擾圖得到鏈路之間的干擾情況,利用圖著色法對(duì)V2V鏈路進(jìn)行分簇,得到V2V鏈路簇集;其次,對(duì)V2I鏈路和V2V鏈路進(jìn)行功率控制,得到相對(duì)較佳的發(fā)射功率;最后,利用三維匹配算法解決V2I鏈路、V2V鏈路簇集、RB三者之間的信道分配問(wèn)題。

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

3.1 V2V鏈路分簇

本文算法通過(guò)V2V鏈路之間的干擾構(gòu)建干擾圖G=(V,E),頂點(diǎn)集V包括每個(gè)V2V鏈路(每個(gè)V2V鏈路代表一個(gè)頂點(diǎn),頂點(diǎn)位置位于V2V鏈路連接發(fā)射端和接收端的中點(diǎn)),v={vj,j=1,2,…,N}。E(G)表示使用相同頻譜資源時(shí)圖G中頂點(diǎn)之間的干擾邊矩陣,表示為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之間存在不可忽略的干擾且兩頂點(diǎn)之間存在相連的邊。在這種情況下,vj是vi的鄰居,并將vi、vj分別加入vj和vi的鄰居集interfi、interfj中。由于強(qiáng)干擾,同一RB不能分配給兩個(gè)相鄰的通信鏈路。這類似于頂點(diǎn)著色問(wèn)題,其中由同一條邊連接的兩頂點(diǎn)不能著相同顏色。因此,當(dāng)一組頂點(diǎn)被涂上相同顏色時(shí),表示允許使用相同的RB。

3.1.1 干擾圖的建立

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

3.1.2 V2V對(duì)的分簇

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

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

由以上兩步得到V2V鏈路分簇結(jié)果,將劃分到同一簇的V2V鏈路看作一個(gè)整體,不同簇間復(fù)用不同的頻譜資源,故不在同一簇的V2V鏈路之間將不會(huì)產(chǎn)生干擾。

3.2 功率控制

為了實(shí)現(xiàn)更高的V2I鏈路總和速率以及保證V2V鏈路的服務(wù)質(zhì)量,需要合理控制V2I鏈路及V2V鏈路的發(fā)射功率。

假設(shè)分配給第m條V2I鏈路的頻譜資源f被第k個(gè)V2V鏈路簇集Ck復(fù)用,故目標(biāo)函數(shù)式(6)變?yōu)橛墒?7)組成的方程組:

(7)

(7a)

(7b)

(7c)

式(7a)化簡(jiǎn)得到

(8)

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

(9)

(10)

(11)

3.3 信道分配

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

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

4 仿真結(jié)果及分析

4.1 實(shí)驗(yàn)條件和仿真設(shè)置

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

仿真針對(duì)圖1所示的公路場(chǎng)景,假設(shè)車輛的到達(dá)服從泊松分布,車輛之間的平均距離為2.5倍車速。信道模型為基于WINNER Ⅱ信道模型建立的V2V和V2I信道模型,基站位于蜂窩區(qū)域的中心,來(lái)進(jìn)行消息的接收和發(fā)送。

表2 仿真參數(shù)

4.2 仿真結(jié)果及分析

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

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

圖5展示了不同迭代次數(shù)下基于圖著色和三維匹配的資源分配算法和對(duì)比算法的V2I鏈路總和速率性能,其中迭代次數(shù)不斷增加,以更新V2V聚類。從圖5可以看出,本文所提算法迅速收斂到次優(yōu)解,并且不會(huì)隨著迭代次數(shù)的增加而改善,而對(duì)比算法則在本文所提算法達(dá)到次優(yōu)解時(shí)還保持增長(zhǎng),最終收斂到穩(wěn)定的解決方案。這表明所提出的算法能在較少的迭代次數(shù)下提升性能并最終收斂到次優(yōu)解。這是因?yàn)槲墨I(xiàn)[13]算法在對(duì)V2V鏈路進(jìn)行簇劃分的過(guò)程中,簇內(nèi)的第一條V2V鏈路是隨機(jī)選擇的,而基于迭代的頻譜分配算法的RB是隨機(jī)分配的,需要經(jīng)過(guò)較多次迭代才能達(dá)到穩(wěn)定。

圖4 V2I鏈路總和速率與V2V鏈路數(shù)量的關(guān)系Fig.4 Relationship between the sum rate of V2I links and the number of V2V links

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

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

圖7為3種算法的V2V鏈路成功接入率。文獻(xiàn)[13]算法和基于迭代的頻譜分配算法的V2V鏈路接入率始終為100%,而本文所提算法的V2V鏈路接入率隨著V2V鏈路的增加而降低。這是因?yàn)閮煞N對(duì)比算法只簡(jiǎn)單地考慮了所有V2V鏈路都能復(fù)用V2I鏈路頻譜資源的情況,并未考慮到當(dāng)一些信道條件較差的V2V鏈路復(fù)用V2I鏈路頻譜資源時(shí),會(huì)降低V2I鏈路的服務(wù)質(zhì)量。而本文所提算法更好地平衡了V2I鏈路服務(wù)質(zhì)量和V2V鏈路接入率。

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

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

圖4～圖6對(duì)比了各資源分配算法的V2I鏈路總和速率。由對(duì)比結(jié)果可以發(fā)現(xiàn),所提算法的V2I鏈路總和速率明顯優(yōu)于基于迭代的頻譜分配算法和文獻(xiàn)[13]所提出的算法,但在網(wǎng)絡(luò)中V2V鏈路數(shù)量較多時(shí),本文所提算法的V2V鏈路接入率略差。

5 結(jié) 論

本文考慮到車聯(lián)網(wǎng)通信場(chǎng)景中上行通信鏈路的資源分配問(wèn)題,為了優(yōu)化V2I鏈路的總和速率,解決V2V鏈路復(fù)用V2I鏈路產(chǎn)生的干擾,提出一種基于圖著色和三維匹配的車聯(lián)網(wǎng)資源分配算法。該算法通過(guò)圖著色法對(duì)V2V鏈路進(jìn)行分簇,通過(guò)求解V2I鏈路和V2V鏈路的發(fā)射功率,將優(yōu)化問(wèn)題轉(zhuǎn)化為V2I鏈路、V2V簇和RB之間的三維匹配問(wèn)題,并利用三維匹配算法進(jìn)行求解。理論分析及仿真結(jié)果表明,該算法在很大程度上提高了V2I鏈路總和速率,并加速了算法收斂性。后續(xù)研究重點(diǎn)在于如何在提高V2I鏈路總和速率的同時(shí),保持V2V鏈路的百分百接入率。