張鵬濤 周一青 劉 航 田 霖 石晶林

(*重慶郵電大學(xué)通信與信息工程學(xué)院 重慶 400065) (**中國科學(xué)院計算技術(shù)研究所移動計算與新型終端北京市重點實驗室 北京 100190)

?

基于圖著色理論的異構(gòu)車聯(lián)網(wǎng)時隙分配方案①

張鵬濤②*周一青**劉 航**田 霖**石晶林**

(*重慶郵電大學(xué)通信與信息工程學(xué)院 重慶 400065) (**中國科學(xué)院計算技術(shù)研究所移動計算與新型終端北京市重點實驗室 北京 100190)

針對異構(gòu)車聯(lián)網(wǎng)系統(tǒng)車輛較多導(dǎo)致時隙分配困難的問題，提出了一種基于圖著色理論的時隙分配方案。該方案以考慮兩跳內(nèi)節(jié)點的圖為模型，通過圖著色的方法分配時隙，有效降低了隱藏終端帶來的丟包；另外給出了一種高效實用的時隙重用分配算法。該算法根據(jù)度定義權(quán)值以確定車輛分配時隙數(shù)目，保證了公平性，提高了時隙重用，進(jìn)而提高了消息發(fā)送的可靠性，同時也適用于網(wǎng)絡(luò)拓?fù)涠嘧兊能嚶?lián)網(wǎng)場景。仿真結(jié)果表明，在車輛數(shù)為200、時隙數(shù)為100時，與傳統(tǒng)時隙分配方法相比，該方案的車輛平均收包率獲得大幅提升。此外，隨著時隙重用的增加，車輛間干擾增強(qiáng)，從而導(dǎo)致平均收包率降低。研究還發(fā)現(xiàn)，增加車輛發(fā)射功率時，由于接收端信干噪比先增加后趨于不變，所以平均收包率也先增加后趨于不變。

異構(gòu)車聯(lián)網(wǎng)， 圖著色， 時隙重用， 發(fā)射功率， 收包率

0 引 言

道路交通事故已成為全球第二大致人死亡因素。隨著道路上汽車的日益增多，道路狀況日趨復(fù)雜，道路安全形勢不容樂觀。車聯(lián)網(wǎng)系統(tǒng)的應(yīng)用，能夠顯著降低交通事故率。奔馳公司的研究表明，車聯(lián)網(wǎng)可通過車-車直接信息交互有效進(jìn)行危險預(yù)警，避免60%以上的事故。因而，車聯(lián)網(wǎng)系統(tǒng)得到了廣泛關(guān)注。同時，安全類應(yīng)用的低時延和高可靠性也對車聯(lián)網(wǎng)系統(tǒng)提出了極大的挑戰(zhàn)。

目前應(yīng)用較為廣泛的車聯(lián)網(wǎng)協(xié)議是專用短程通信(dedicated short rage communication，DSRC)協(xié)議,也稱無線接入車載環(huán)境(wireless access vehicular environment, WAVE)協(xié)議[1,2]。它繼承于802.11協(xié)議家族，采用CSMA/CA載波偵聽多路訪問/沖突避免的接入方式，方法簡單且成熟，適用于網(wǎng)絡(luò)拓?fù)涠嘧兊能囕v通信場景。另外，它采用車車直接通信的方式，使得通信時延縮短，有效保證了安全類應(yīng)用的要求。在美國，聯(lián)邦通信委員會(FCC)專門為該協(xié)議分配了75MHz的帶寬資源。但該協(xié)議也存在明顯的不足。由于采用競爭接入信道機(jī)制，缺乏有效的集中調(diào)度，在車輛數(shù)目較多時信道擁塞嚴(yán)重，信道利用率低。此外，該協(xié)議對于多播類消息支持較差。由于缺乏ACK和重傳機(jī)制信令設(shè)計，隱藏終端問題難以避免，同時多播類消息沖突嚴(yán)重。然而，值得注意的是，在車聯(lián)網(wǎng)系統(tǒng)中，大多數(shù)安全類消息都是多播類消息。文獻(xiàn)[3]的研究發(fā)現(xiàn)，在車輛密度較大的場景下，很多車輛發(fā)包會產(chǎn)生沖突，從而導(dǎo)致系統(tǒng)吞吐量下降，接入時延增大。車輛數(shù)目大于50時，時延將遠(yuǎn)大于100ms，無法滿足安全類消息的需求。

在公共無線通信方面，隨著蜂窩移動通信的迅速發(fā)展[4-7]而提出的高效可靠的通信技術(shù)，有望與車聯(lián)網(wǎng)需求結(jié)合，大幅提升車聯(lián)網(wǎng)性能[8]。其中3GPP的長期演進(jìn)(LTE)協(xié)議獲得廣泛支持，LTE商用網(wǎng)絡(luò)已經(jīng)在全球廣泛部署。LTE采用集中式控制架構(gòu)，具有帶寬靈活配置，支持高速運動等特點。但是LTE協(xié)議目前不支持車車直接通信，所用數(shù)據(jù)都需要經(jīng)過基站轉(zhuǎn)發(fā)，系統(tǒng)時延明顯增大。文獻(xiàn)[3]評估了LTE協(xié)議應(yīng)用于車聯(lián)網(wǎng)的性能。在車輛較少時，LTE網(wǎng)絡(luò)可以滿足車聯(lián)網(wǎng)眾多應(yīng)用的要求，且性能優(yōu)于DSRC，但當(dāng)車輛增多時，很多應(yīng)用的時延和可靠性都無法得到保障。為了綜合利用DSRC和LTE的優(yōu)勢，文獻(xiàn)[9-14]提出了融合DSRC和LTE的雙層異構(gòu)車聯(lián)網(wǎng)架構(gòu)。其中基于時分多址接入(TDMA)的異構(gòu)車聯(lián)網(wǎng)架構(gòu)通過LTE蜂窩網(wǎng)集中控制車輛接入DSRC的時隙，采用DSRC無線資源進(jìn)行車車直接通信。這樣既避免了CSMA/CA接入方式導(dǎo)致的信道擁塞，同時也保留了低時延的車車通信方式，降低了系統(tǒng)時延。然而，目前針對該系統(tǒng)的許多研究還不足，車輛接入機(jī)制設(shè)計和資源分配方案研究都亟待展開[12]。其中，文獻(xiàn)[15]以最大化長期獎勵為目標(biāo)針對車輛云計算系統(tǒng)提出了一種最優(yōu)計算資源的分配方案。針對時隙資源的分配方案研究不多，在系統(tǒng)車輛數(shù)目較多時，傳統(tǒng)無重用地為所有車輛分配不同時隙的方法會導(dǎo)致時隙不足的情況。本文針對這種情況研究異構(gòu)車聯(lián)網(wǎng)時隙接入管理機(jī)制，給出基于圖著色理論的時隙分配方案，提高資源利用率，提升系統(tǒng)性能。本文首先給出了基于TDMA的異構(gòu)車聯(lián)網(wǎng)系統(tǒng)模型，然后給出了時隙重用分配方案。該方案根據(jù)時隙重用范圍構(gòu)建兩跳內(nèi)節(jié)點的圖模型，采用時隙分配算法確定車輛分配時隙數(shù)目，并通過圖著色的方法為車輛分配時隙。最后，仿真驗證了本文提出方案的有效性。仿真表明平均收包率將隨著時隙重用率的升高而降低。隨著發(fā)射功率的增加，收包率會相應(yīng)增加，但當(dāng)功率增大到一定程度后，收包率不再有明顯的增加。

1 系統(tǒng)模型

考慮基站全覆蓋的郊區(qū)公路為研究場景，本文關(guān)注基于TDMA的異構(gòu)車聯(lián)網(wǎng)通信系統(tǒng)[13]中周期安全類消息的傳輸。周期安全類消息為車聯(lián)網(wǎng)安全應(yīng)用中至關(guān)重要的應(yīng)用，它由車輛周期產(chǎn)生并廣播其狀態(tài)信息(本文僅考慮車輛位置信息，假設(shè)車輛均安裝GPS裝置，可以準(zhǔn)確定位自己的位置)給周圍其他車輛來有效避免交通事故。廣播周期[2]不能超過100ms，本文采用均分100ms的方式劃分時隙。

如圖1所示，異構(gòu)車聯(lián)網(wǎng)系統(tǒng)包括LTE和DSRC網(wǎng)絡(luò)，其中LTE蜂窩網(wǎng)以高功率的基站為中心，覆蓋范圍較廣，基站間可共享信息。車輛發(fā)射功率較低，車車通信距離較短，車車通信基于DSRC協(xié)議進(jìn)行，采用TDMA多址接入。車輛采用直接接入和簇頭轉(zhuǎn)發(fā)接入LTE網(wǎng)絡(luò)的方式分別完成與基站的初次通信與后續(xù)通信。由于初次通信只發(fā)生在基站開機(jī)和車輛初始進(jìn)入基站覆蓋區(qū)域兩種情況下，而后續(xù)通信僅選取簇頭接入LTE系統(tǒng)，所以該方法可以有效降低LTE系統(tǒng)負(fù)荷?；靖鶕?jù)車輛實時位置信息對車輛分簇，同時覆蓋區(qū)域內(nèi)車輛采用簇頭轉(zhuǎn)發(fā)的方式上報實時位置信息給基站，即上述兩個過程相互依賴相互作用。

圖1 異構(gòu)車聯(lián)網(wǎng)模型

下面分別介紹兩個過程。初次或后續(xù)通信后，基站獲得車輛位置信息后的分簇具體過程如下：首先，基站根據(jù)車輛行駛方向和地理位置信息可以將車輛分成不同方向不同車道的集合；然后，以基站覆蓋道路的中心為中心，以DSRC傳輸距離[13]為覆蓋范圍，根據(jù)車輛位置信息，進(jìn)一步將集合內(nèi)車輛分成多個簇；最后，選取簇內(nèi)接近中心位置(如果沒有則選取接近簇內(nèi)1/4和3/4地理位置)且信號較強(qiáng)的車輛作為簇頭。本文以三個廣播周期(300ms)作為簇的生命周期，雖然車輛移動速度較快，但同車道同方向車輛的相對速度較小，所以可以認(rèn)為簇內(nèi)車輛位置拓?fù)浠緹o變化。覆蓋區(qū)域內(nèi)車輛完成分簇后，其經(jīng)簇頭轉(zhuǎn)發(fā)上報位置信息給基站的過程如下：簇中車輛根據(jù)分配的不同時隙接入DSRC網(wǎng)絡(luò)，廣播安全位置信息。圖2為以簇頭為中心，根據(jù)DSRC傳輸距離得到無線廣播信道連續(xù)三個周期時序圖。第N-1個廣播周期(100ms)內(nèi)，簇頭通過DSRC網(wǎng)絡(luò)收集得到簇內(nèi)其他車輛位置信息。第N個廣播周期開始到簇頭發(fā)送時隙之間，簇頭完成與基站的上下行通信。具體過程如下：簇頭通過LTE蜂窩網(wǎng)上報收集獲得的簇內(nèi)車輛位置信息給基站?；靖鶕?jù)得到的車輛位置拓?fù)洌锌刂拼_定第N+1個廣播周期(100ms)每輛車接入DSRC網(wǎng)絡(luò)的時隙和發(fā)送功率，并通過LTE蜂窩網(wǎng)發(fā)送給簇頭。簇頭在其廣播時隙上通過DSRC網(wǎng)絡(luò)，將時隙分配信息分發(fā)給簇內(nèi)其他車輛。最后，簇內(nèi)車輛在第N+1個廣播周期內(nèi)采用分配得到的時隙和發(fā)射功率，利用DSRC的無線資源廣播安全位置信息。假設(shè)簇頭通過LTE蜂窩網(wǎng)與基站的通信完全成功，且第N-1個廣播周期內(nèi)簇頭收集和第N個廣播周期內(nèi)簇頭分發(fā)控制信息過程也完全成功。

圖2 無線廣播信道時序圖

本文主要關(guān)注時隙重用方案對周期安全消息進(jìn)行車車通信性能的影響。車車通信的無線信道采用雙折線衰落模型[16-18]。該模型假設(shè)在臨界距離dc內(nèi)，衰落指數(shù)為γ1，如果傳播距離大于dc，衰落指數(shù)為γ2。因此，接收功率P可以表示如下：

P(d)=

(1)

m=-0.69ln(d)+4.929, m∈[0.5, 3.9]

(2)

表1 雙折線衰落模型參數(shù)

由異構(gòu)車聯(lián)網(wǎng)模型可知，車輛發(fā)送安全消息時，是基于DSRC在不同的時隙發(fā)送。傳統(tǒng)方法是正交地為所有車輛分配不同時隙，沒有考慮重用，當(dāng)車輛數(shù)目較大時，會導(dǎo)致許多車輛無法獲得發(fā)送時隙。事實上，由于車車直接基于DSRC的傳輸距離較短，當(dāng)時隙不足時，互相在一定距離外的車輛可以重用相同的時隙資源，有望大幅度提升時隙資源的利用率，讓更多車輛獲得接入時隙發(fā)送安全消息，從而提升行車安全?；谏鲜鏊枷?，本文研究了在給定時隙重用距離下的時隙重用分配方案。

2 時隙分配方案

以頂點表示車輛，以邊表示不能分配相同的時隙車輛對。研究區(qū)域中所有車輛可以構(gòu)成頂點集合V，所有不能分配相同時隙的車輛對可以構(gòu)成邊集合E。頂點集和邊集構(gòu)成無向圖G=(V,E)。以不同顏色代表不同時隙，可為車輛分配時隙的過程構(gòu)建成圖著色模型。

2.1 構(gòu)建圖著色模型

本小節(jié)以郊區(qū)公路為研究區(qū)域說明圖著色模型。由系統(tǒng)模型可知，第N-1個廣播周期內(nèi)，簇頭通過DSRC網(wǎng)絡(luò)收集得到車輛的位置信息，然后通過LTE蜂窩網(wǎng)上行鏈路發(fā)送給基站。基站可以得到每100ms車輛的位置分布圖(如圖3)，其中車輛用圓圈表示，所關(guān)注的公路區(qū)域用虛線框表示。于是，所有車輛構(gòu)成頂點集。

圖3 車輛位置分布例圖

在本文提出的可重用時隙機(jī)制下，基站分配時隙時，必須考慮到車輛會在分配的時隙內(nèi)利用DSRC頻帶資源廣播發(fā)送周期安全消息給周圍車輛。為避免嚴(yán)重干擾，在時隙重用距離內(nèi)的車輛采用不同的時隙接入DSRC網(wǎng)絡(luò)。因此，相互在時隙重用距離內(nèi)的車輛對加入邊集合(圖4中實線)。

圖4 時隙重用單跳例圖

如圖4所示，對于相互不在時隙重用距離內(nèi)的車輛(如1和4)，如果各自的重用范圍存在相同的其他車輛(如2和3)，若1和4采用相同的時隙發(fā)送安全消息，會出現(xiàn)其他車輛不能正確接收它們的安全消息的問題，即隱藏終端問題。因此，為了降低由于隱藏終端導(dǎo)致的丟包，兩跳連線的車輛節(jié)點也不能分配相同的時隙，于是也將兩跳連線的車輛對加入邊集合(圖5中虛連線)。

圖5 時隙重用兩跳例圖

最后，頂點集和所有邊集構(gòu)成無向圖模型。以不同顏色代表不同時隙，那么為車輛分配時隙的過程與對圖中節(jié)點著色的過程相同。基于圖著色的方法為車輛分配時隙，得到的一種分配結(jié)果如圖6所示。

由圖6可知，在同一研究區(qū)域中，相距較遠(yuǎn)的不同車輛可以重用相同的時隙，但同時也會帶來一定的相互干擾，干擾功率隨著可重用距離的增加呈指數(shù)級數(shù)下降。此外，圖著色問題存在最小顏色數(shù)，即最小所需時隙數(shù)目。當(dāng)系統(tǒng)可提供的時隙數(shù)目小于車輛數(shù)目但大于最小所需時隙數(shù)時，時隙重用的方法可以有效保證所有車輛獲得更多的接入時隙進(jìn)行通信。當(dāng)時隙數(shù)目小于最小所需時隙數(shù)目時，部分車輛會無法獲得接入時隙發(fā)送安全消息。定義系統(tǒng)等效時隙總數(shù)為所有車輛時隙數(shù)目總和。因此，當(dāng)系統(tǒng)正交時隙數(shù)目、網(wǎng)絡(luò)拓?fù)浯_定后，需要研究時隙分配算法，在保證公平性的前提下，盡可能地為每輛車分配更多的時隙，增大系統(tǒng)等效時隙總數(shù)。

2.2 時隙分配算法

本小節(jié)在圖著色模型的基礎(chǔ)上研究時隙分配算法，以確定每輛車可分配的時隙數(shù)目。首先，本文基于無向圖定義了車輛在分配時隙過程中的公平性，即車輛的地位與其處于無向圖的位置密切相關(guān)。對于一個由n點構(gòu)成的完全圖，定義圖中n個節(jié)點地位平等，即可以平等分配相同數(shù)量的時隙。對于非完全圖，定義圖中度較大的節(jié)點地位較低，即可分配的時隙數(shù)目較少。原因是度較大的節(jié)點多分得一個時隙，與該節(jié)點相連的更多節(jié)點少分配一個時隙。同時，基于公平性分配時隙也可以有效增加系統(tǒng)時隙重用(系統(tǒng)等效時隙總數(shù)更多)。另外，完全圖中的所有節(jié)點相互之間均不能分配相同的時隙，而非完全圖的節(jié)點包含于多個完全子圖中。因此，本文根據(jù)節(jié)點的度定義了權(quán)值，量化了公平性，并分別以完全圖或子圖為分配集合，根據(jù)權(quán)值比例確定每種集合中車輛獲得時隙的數(shù)目。最后，為保證所有分配集合不會出現(xiàn)接入時隙沖突，取其中最小值作為車輛分配的時隙數(shù)。

圖7 時隙分配例圖

系統(tǒng)可提供的正交時隙總數(shù)設(shè)為N，基于權(quán)值的時隙分配算法具體如下：

(1) 對于圖中任意的節(jié)點n，其度為deg(n), 存儲與該節(jié)點相連的所有節(jié)點得到節(jié)點集: Tn={m;m與n相連，m≠n}

(2) 對于圖中任意節(jié)點n, 定義其權(quán)值為: imp(n)=1/(deg(n)+1)；

3 仿真及結(jié)果

以4車道郊區(qū)公路為仿真區(qū)域，車輛總數(shù)為200，車輛均勻分布，車輛間距分為25m和10m兩種情況，對應(yīng)公路長度分別為5km和2km。安全類消息大小為300Byte，采用BPSK調(diào)制，時隙總數(shù)為100，均分100ms，即每個時隙1ms,帶寬為10M,載頻為5.850GHz,考慮全向天線，天線高度1.5m，忽略速度影響[19]。系統(tǒng)整體仿真配置參數(shù)見表2。

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

由系統(tǒng)模型可知，本文假設(shè)簇頭與基站通過LTE蜂窩網(wǎng)的通信完全成功，且簇頭收集車輛位置信息和分發(fā)控制信息的過程也完全成功。仿真采用簡化的基于權(quán)值時隙分配算法確定車輛分配時隙數(shù)目，根據(jù)圖著色模型隨機(jī)選擇接入時隙分配給車輛，時隙的優(yōu)先級等同。車輛以給定的發(fā)射功率,在分配時隙上接入DSRC網(wǎng)絡(luò)，并發(fā)送周期安全類包。經(jīng)過無線信道后，計算在接收端的SINR。其中接收端的背景噪聲為-104dBm[18]。如果SINR大于閾值[19]則認(rèn)為接收成功，否則丟包。

仿真分別研究了車輛平均收包率隨時隙重用范圍的變化，系統(tǒng)等效時隙總數(shù)隨時隙重用范圍的變化情況，以及發(fā)射功率對平均收包率的影響。

圖8所示為車輛發(fā)射功率為23dBm,統(tǒng)計范圍為0～300m時，時隙重用距離與收包成功率的關(guān)系。由于研究區(qū)域中車輛總數(shù)為200，而正交時隙只有100個，當(dāng)用傳統(tǒng)方法為所有車輛分配不同時隙時，會導(dǎo)致許多車輛無法獲得發(fā)送機(jī)會，在兩種車輛間距下，平均收包率均接近0.5。但采用本文提出的時隙重用方案，平均收包率可以獲得大幅度提升。重用距離越大，在相同時隙上發(fā)送安全消息的車輛相距越遠(yuǎn)，互干擾越低，平均收包率越高。但重用距離增大到一定程度時，會出現(xiàn)正交時隙數(shù)目小于最小所需時隙數(shù)目的情況，如圖中車輛間距為10m，時隙重用范圍大于400m時，會出現(xiàn)部分車輛無法獲得接入時隙發(fā)送消息的情況，且隨著重用距離的增加，無法分配獲得時隙的車輛增多，從而平均收包率會降低。車輛間距為25m時，由于車輛密度較小，在最大重用范圍600m時，最小所需時隙數(shù)目不會多于正交時隙數(shù)目，因此，車輛平均收包率沒有下降。另外，車輛間距越小，網(wǎng)絡(luò)拓?fù)湓矫芗?，車輛平均獲取時隙數(shù)目較少，從而時隙分布越稀疏，互干擾越小，所以在重用距離較小時，車輛間距為10m的收包率要高于25m間距的收包率。

圖8 平均收包率與重用距離的變化

系統(tǒng)等效時隙數(shù)目與重用距離的關(guān)系如圖9所示。從圖9看出，隨著時隙重用距離的增加，系統(tǒng)等效時隙數(shù)目降低。車輛間距為10m時，由于車輛密度較大，網(wǎng)絡(luò)拓?fù)鋱D密集，車輛獲取時隙數(shù)目較少，所以系統(tǒng)等效時隙數(shù)目少于車輛間距為25m的時隙數(shù)。車輛間距為10m，時隙重用距離為450m時，系統(tǒng)等效時隙總數(shù)低于車輛總數(shù)200，即出現(xiàn)部分車輛無法獲得發(fā)送時隙的情況，與圖8中正交時隙數(shù)目低于最小所需時隙數(shù)目的情況對應(yīng)。車輛間距為25m時，車輛密度較小，網(wǎng)絡(luò)拓?fù)湎∈?，等效系統(tǒng)時隙總數(shù)多于車輛總數(shù)200，即不會出現(xiàn)車輛無法獲得發(fā)送時隙的情況。

圖9 系統(tǒng)等效時隙數(shù)目隨重用距離的變化

圖10所示為不同發(fā)射功率，統(tǒng)計范圍為0～300m時，車輛間距為25m,時隙重用距離與平均收包率的關(guān)系。隨著發(fā)射功率的增加，平均收包率會相應(yīng)增加，但當(dāng)增加到一定程度后，平均收包率不再有明顯的增加。因為達(dá)到一定功率后，噪聲相對于干擾已經(jīng)可以忽略，車輛接收到信干噪比趨于不變，所以平均收包不再明顯增加。

圖10 不同發(fā)射功率，平均收包率隨重用距離的變化

4 結(jié) 論

本文研究了融合DSRC協(xié)議和LTE協(xié)議優(yōu)點形成的基于TDMA的異構(gòu)車聯(lián)網(wǎng)架構(gòu)下安全消息的發(fā)送機(jī)制。在車輛數(shù)目較多時，傳統(tǒng)的為所有車輛分配不同時隙的方法，會導(dǎo)致許多車輛無法獲得發(fā)送機(jī)會，從而降低了消息發(fā)送的可靠性。本文基于圖著色理論，提出了一種異構(gòu)車聯(lián)網(wǎng)時隙分配方案。該方案以兩跳節(jié)點構(gòu)建圖模型，有效降低了隱藏終端帶來的丟包，同時，提出了時隙分配算法，保證了車輛的公平性，提高了時隙重用，適用于網(wǎng)絡(luò)拓?fù)涠嘧兊能嚶?lián)網(wǎng)場景。仿真表明，在傳統(tǒng)方法分配時隙不足時，該方案保證了車輛獲得足夠的發(fā)送時隙，顯著提高了周期安全類信息可靠性。此外，仿真還得到了平均收包率隨著發(fā)射功率的增大而先升高后趨于不變的結(jié)論。

[1] Uzcategui R A, Marum G A. WAVE: a tutorial.IEEECommunicationsMagazine, 2012, 47(5): 126-133

[2] Karaginanis G, Altintas O, Ekici E, et al. Vehicular networking: A survey and tutorial on requirements, architectures, challenges, standards and solutions.IEEECommunicationSurveys&Tutorials, 2011, 13(4): 2036- 2040

[3] Mir Z H, Filali F. LTE and IEEE 802. 11p for vehicular networking: a performance evaluation.EURASIPJournalonWirelessCommunicationsandNetworking, 2014, 2014: 89

[4] Zhou Y, Liu H, Pan Z, et al. Spectral and energy efficient two-stage cooperative multicast for LTE-A and beyond.IEEEWirelessMagazine, 2014, 21(2): 34-41

[5] Liu L, Zhou Y Q, Tian L, et al. CPC-based backward compatible network access for LTE cognitive radio cellular networks.IEEECommunicationMagazine, 2015, 53(7): 93 -99

[6] Garcia V, Zhou Y Q, Shi J L. Coordinated multipoint transmission in dense cellular networks with user-centric adaptive clustering.IEEETransactionsonWirelessCommunication, 2014, 13(8):4297-4308

[7] Zhou Y Q, Liu H, Pan Z, et al. Two-stage cooperative multicast transmission with optimized power consumption and guaranteed coverage.IEEEJournalonSelectedAreasinCommunications, 2014, 32(2):274-284

[8] Liu H, Zhou Y Q, Tian L, et al. How can vehicular communication reduce rear-end collision probability on highway. In: Proceedings of the 2015 IEEE GLOBECOM, San Diego, USA, 2015. 1-6

[9] Yang Y, Wang P, Wang C, et al. An eMBMS based congestion control scheme in cellular-VANET heterogeneous networks. In: Proceedings of the 2014 IEEE 17th International Conference on Intelligent Transportation System, Qingdao, China, 2014. 1-5

[10] Rubin I, Baiocchi L Y Y A, Cuomo F, et al. Micro base station aided vehicular ad hoc networking. In: Proceedings of the 2014 International Conference on Computing, Networking and Communications, Honolulu, USA, 2014. 231-235

[11] Benslimane A, Taleb T, Sivaraj R. Dynamic clustering- based adaptive mobile gateway management in integrated VANET-3G heterogeneous wireless networks.SelectedAreasinCommunications, 2011, 29(3): 559-570

[12] Zheng K, Zheng Q, Xiang W, et al. Heterogenous vehicular networking: a survey on architecture, challenges, and sloutions.IEEECommunicationSurveys&Tutorials, 2015, 17(4): 2377-2396

[13] Taleb T, Benslimane A. Design guidelines for a network architecture integrating VANET with 3G & beyond networks. In: Proceedings of the 2010 IEEE Global Telecommunications Conference, Miami, USA, 2010. 1-5

[14] Zhou W, Ren C, Ma C, et al. Multicast/broadcast service in integrated VANET-cellular heterogeneous wireless networks. In: Proceedings of the 2013 International Conference on Wireless Communications & Signal Processing, Hangzhou, China, 2013. 1-6

[15] Zheng K, Meng H, Lei L, et al. An SMDP-based resource allocation in vehicular cloud computing systems.IEEETransactionsonIndustrialElectronics, 2015, 62(12): 7920- 7928

[16] Cheng L, Henty B E, Stancil D D, et al. Mobile vehicle- to-vehicle narrow-band channel measurement and characterization of the 5.9 GHz dedicated short rage communication (DSRC) frequency band.IEEEJournalonSelectedAreasinCommunications, 2007, 25(8): 1501-1506

[17] Cheng L, Henty B E, Bai F, et al. Highway and rural propagation channel modelling for vehicle-to-vehicle communications at 5.9 GHz. In: Proceedings of the 2008 IEEE Antennas and Propagation Society International Symposium, San Diego, USA, 2008.1-4

[18] Islam T, Hu Y, Boltjes D E. Realistic simulation of IEEE 802.11p channel in mobile vehicle to vehicle communication. In: Proceedings of the 13th Conference on Microwave Techniques COMITE 2013, Pardubice, CzechRepublic, 2013. 156-161

[19] Chen Q, Schmidt-Eisenlohr F, Jiang D. Network simulator ns-2. http://ww w.isi.edu/nsnam/ns/: WiKi, 2007

A scheme based on graph coloring theory for time slot allocation in integrated VANET-cellular heterogeneous networks

Zhang Pengtao*, Zhou Yiqing**, Liu Hang**, Tian Lin**, Shi Jinglin**

(*College of Communication and Information Engineering, Chongqing University of Posts and Telecommunications Communication, Chongqing 400065) (**Beijing Key Laboratory of Mobile Computing and Pervasive Device, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190)

To solve the problem that the time slots of integrated VANET-cellular heterogeneous networks are not easy to allocate when there are more vehicles on the road, a new time slot allocation scheme is proposed based on the graph coloring theory, and its time slot allocation algorithm is given. The scheme uses the nodes within two-hop to form the graph coloring model, and allocates time slots by using the graph coloring method to reduce the packet loss caused by hidden terminals. Through defining a weight coefficient based on the degree of node, the algorithm ensures the fairness, and improves the reuse of time slots, thus improving the reliability of message delivery. Moreover, it is efficiently and practically applicable to the vehicle networking scene whose topology changes rapidly. The simulation showed that, compared with the traditional method, the average packet reception increased greatly in the condition of 200 vehicles and 100 time slots. In addition, it showed a trade-off between the time slot reuse and the average packet reception rate. The study also found that the packet reception rate increased with the increasing of the transmit power until to a certain value when the SINR tends to a constant.

VANET-cellular heterogeneous networks, graph coloring theory, time slot reuse, transmit power, packet reception rate

10.3772/j.issn.1002-0470.2016.06.005

①國家自然科學(xué)基金(61331009)和科技創(chuàng)新基地培育與發(fā)展工程專項(Z15110000161503)資助項目。

2016-01-11)

②男，1989年生，碩士；研究方向：車聯(lián)網(wǎng)，寬帶無線通信，物理層基帶算法；聯(lián)系人，E-mail: zhangpengtao@ict.ac.cn