張本宏，吳浩浩，俞 磊

（1.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，合肥 230601；2.安徽中醫(yī)藥大學(xué) 醫(yī)藥信息工程學(xué)院，合肥 230012）

0 概述

智能交通系統(tǒng)（Intelligent Transport System，ITS）是將先進(jìn)的信息技術(shù)、通信技術(shù)、傳感技術(shù)以及計(jì)算機(jī)技術(shù)等有效地綜合運(yùn)用于整個交通運(yùn)輸管理體系，在緩解交通阻塞、減少交通事故中發(fā)揮著日益突出的作用，成為當(dāng)前研究熱點(diǎn)之一。而車載自組織網(wǎng)絡(luò)（Vehicular Ad Hoc Networks，VANETs）作為ITS 的信息承載平臺，更是受到了人們的廣泛關(guān)注。車載自組織網(wǎng)絡(luò)是由裝載在車上的車載單元（On-Board Unit，OBU）、路邊的通信基礎(chǔ)設(shè)施等組成的自組織無線多跳網(wǎng)絡(luò)。在車載自組織網(wǎng)絡(luò)中，車輛需要周期性地交換狀態(tài)信息以及安全信息等，但是車輛行駛時車速過快、網(wǎng)絡(luò)拓?fù)渥兓l繁和無中心等特性［1］造成了車聯(lián)網(wǎng)中車與車之間（Vehicle to Vehicle，V2V）和車輛與路邊單元之間（Vehicle to Roadside Unit，V2R）數(shù)據(jù)傳輸?shù)牟豢煽?。因此，可靠有效的介質(zhì)訪問控制（Medium Access Control，MAC）協(xié)議是人們研究的重點(diǎn)。

MAC 協(xié)議通常分為基于競爭方式和基于非競爭方式［2］。競爭方式在車輛密度較大時引起的沖突難以滿足安全應(yīng)用的時延要求，而在非競爭方式中，根據(jù)通信資源的分配方式又分為集中式和分布式兩種。在集中式方式中，通常會借助路邊單元（Road Side Unit，RSU）來進(jìn)行通信資源分配，以減低沖突的產(chǎn)生，提高通信效率。根據(jù)不同服務(wù)質(zhì)量（Quality of Service，QoS）的要求，研究人員提出了不同的方法。文獻(xiàn)［3］提出的基于無干擾圖TDMA 調(diào)度（IGTDMA）協(xié)議，通過收集其通信范圍內(nèi)的車輛信息并基于車輛位置和預(yù)設(shè)的無干擾閾值構(gòu)建無干擾圖，再使用通信鏈路選擇算法決定節(jié)點(diǎn)發(fā)送的時隙。文獻(xiàn)［4］將通信幀分為時間幀管理周期（TMP）、自由傳輸周期（FTP）和競爭周期（CP）。在TMP 期間，RSU估算和預(yù)測其通信范圍內(nèi)的車輛數(shù)，自適應(yīng)地確定FTP 和CP 的時間。文獻(xiàn)［5］提出一種QoS 感知集中式混合MAC（QCHMAC）協(xié)議，將訪問時間分為預(yù)留周期（RP）和傳輸周期（TP），在RP 內(nèi)，新加入的車輛根據(jù)其優(yōu)先級由RSU 分配TP 內(nèi)的時隙，而在TP內(nèi)由RP 內(nèi)預(yù)留成功的車輛進(jìn)行通信。文獻(xiàn)［6］提出基于捕獲感知的TDMA MAC（CT-MAC）協(xié)議，RSU根據(jù)其通信范圍內(nèi)競爭車輛的估計(jì)數(shù)，優(yōu)化每一個通信幀的長度。文獻(xiàn)［7］提出了碰撞預(yù)測TDMA MAC（CPTM）協(xié)議，RSU 根據(jù)預(yù)測即將到來的時隙中的合并沖突，適當(dāng)?shù)卣{(diào)整車輛的時隙分配，再根據(jù)車輛密度比率為不同方向的車輛重新分配時隙。文獻(xiàn)［8］提出一種考慮實(shí)際環(huán)境條件的TDMA MAC（VCAR-MAC）協(xié)議，在控制信道上，RSU 可以根據(jù)實(shí)際環(huán)境快速識別覆蓋范圍內(nèi)的車輛數(shù)，確定車輛競爭的最佳時隙數(shù)以最小化碰撞的概率。文獻(xiàn)［9］提出的多信道MAC（RMM）協(xié)議，借助RSU 的協(xié)調(diào)使得車輛在控制信道上對服務(wù)信道進(jìn)行預(yù)約，實(shí)現(xiàn)了服務(wù)信道無競爭的傳輸。

上述方法需要在路旁安置大量的RSU 來進(jìn)行通信協(xié)調(diào)，一方面加大了開銷，另一方面由于車輛的高速移動的特性，導(dǎo)致車輛與RSU 之間頻繁切換，還可能提高沖突發(fā)生的概率，因此，許多研究開始關(guān)注于分布式方式MAC 協(xié)議。文獻(xiàn)［10］提出一種自適應(yīng)Ad Hoc（A-ADHOC）協(xié)議，各個節(jié)點(diǎn)根據(jù)車輛密度調(diào)整每一幀的時隙數(shù)。文獻(xiàn)［11］提出的VeMAC 協(xié)議通過在控制信道上提供的廣播服務(wù)，為在相反方向移動的車輛和RSU 分配不相交的時隙集以減少傳輸沖突。文獻(xiàn)［12］提出的移動性感知TDMA MAC（MoMAC）協(xié)議，則在考慮到車輛移動性的情況下，根據(jù)基礎(chǔ)道路拓?fù)浜蛙嚨婪植紴檐囕v分配時隙。文獻(xiàn)［13］則在VeMAC 協(xié)議基礎(chǔ)上，提出無沖突預(yù)留的MAC（CFR）協(xié)議，該協(xié)議根據(jù)當(dāng)前的交通流量動態(tài)地調(diào)整每個方向和速度級別的時隙數(shù)。文獻(xiàn)［14-15］提出一種基于博弈論的TDMA MAC 協(xié)議。文獻(xiàn)［16］提出基于自適應(yīng)幀結(jié)構(gòu)的分布式多通道MAC 協(xié)議，將控制信道分為基于TDMA 的廣播周期和基于退避機(jī)制的協(xié)商周期，車輛可以在廣播周期內(nèi)定期廣播消息，而協(xié)商周期內(nèi)則是車輛之間協(xié)商使用服務(wù)信道的權(quán)利。文獻(xiàn)［17］提出一種將TDMA 和SDMA（Space Division Multiple Access）相結(jié)合的改進(jìn)分布式自適應(yīng)時分多址分配機(jī)制（MDATS）。文獻(xiàn)［18］提出的適用于時隙共享的MAC（ASTSMAC）協(xié)議，允許在彼此通信范圍內(nèi)的車輛共享同一時隙。文獻(xiàn)［19］提出一種基于位置的分布式DTMAC 協(xié)議，將道路分成若干段，時隙在區(qū)域之間重復(fù)使用，使得不同相鄰區(qū)域中的車輛可以同時訪問信道而不發(fā)生沖突。針對DTMAC 中存在的問題即每輛車包含的ID 字段（IDF）與每一幀的時隙數(shù)相同從而導(dǎo)致大量的開銷，文獻(xiàn)［20］提出了CTMAC（Cooperative TDMA MAC）協(xié)議，通過共享鄰居車輛感測到的時隙狀態(tài)信息，有效減少了數(shù)據(jù)的負(fù)載。

本文提出一種具有競爭和時分復(fù)用特點(diǎn)的基于競爭的時分多址協(xié)議（Contention-based TDMA MAC protocol，CTDMAC）。將道路按照通信半徑分成若干段，每段道路對應(yīng)幀的一部分，而每部分又分為靜態(tài)段和動態(tài)段，在同一路段的車輛，在靜態(tài)段使用時分復(fù)用的方式進(jìn)行通信，新進(jìn)入的車輛在動態(tài)段以競爭的方式確定發(fā)送時隙，該協(xié)議采用分布式方式，具有較大的靈活性。

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

1.1 系統(tǒng)模型

本文系統(tǒng)研究的場景是高速公路。每輛車都有唯一編號，由于車輛是在高速公路上行駛，在一個較短的時間內(nèi)，可假設(shè)車輛的速度恒定。車輛都裝有GPS 裝置，每輛車通過GPS 獲得自己的行駛方向、行駛速度和地理位置等，車輛之間同步使用GPS 接收器提供的1PPS 信號，每輛車通過安裝在車上的OBU進(jìn)行短距離的廣播。對于車輛之間的無線通信采用圓盤模型，即兩輛車能進(jìn)行通信當(dāng)且僅當(dāng)兩輛車之間的歐氏距離小于通信半徑。

1.2 問題描述

在車聯(lián)網(wǎng)中，存在合并沖突和訪問沖突［1］兩種沖突。一方面，不在兩跳通信范圍內(nèi)使用相同時隙發(fā)送數(shù)據(jù)的車輛由于車輛的移動變成兩跳鄰居，會發(fā)生合并沖突。另一方面，當(dāng)處在相同兩跳通信范圍內(nèi)的車輛試圖占用一個時隙時會發(fā)生訪問沖突。為了能夠更好地以分布式方式分配時隙，減少沖突的發(fā)生，在下一幀中車輛v需要知道鄰居節(jié)點(diǎn)的信息，其中包括車輛v可以使用時隙集合A(v)和車輛v一跳鄰居車輛的集合N（v）。

2 CTDMAC 協(xié)議

本文將道路分成固定的區(qū)域，每個區(qū)域的長度為車輛通信的半徑，區(qū)域用xi(i=1，2，…，θ)表示，如圖1 所示。

圖1 道路分段Fig.1 Road segmentation

在時間軸上，每一幀分成3 個時隙組，分別用S1、S2、S3表示，每個時隙組分別對應(yīng)高速公路上的各個道路段，如圖2 所示。

圖2 時隙集與道路的對應(yīng)關(guān)系Fig.2 Correspondence between time slot set and road

時隙組和道路段根據(jù)下面的規(guī)則進(jìn)行映射：

1）如果i%3==1，則xi和S1相關(guān)聯(lián)。

2）如果i%3==2，則xi和S2相關(guān)聯(lián)。

3）如果i%3==0，則xi和S3相關(guān)聯(lián)。采用上述方式，可以保證相鄰道路段之間發(fā)送數(shù)據(jù)時不會發(fā)生沖突。

2.1 協(xié)議幀格式

幀信息結(jié)構(gòu)如圖3 所示，每個幀包括3 個時隙組，每組時隙包括動態(tài)段和靜態(tài)段。動態(tài)段由長度較小的競爭時隙組成，用于新加入的車輛競爭靜態(tài)段中的空閑時隙。靜態(tài)段由長度相對較大的發(fā)送時隙組成，用于交換時隙占用信息和車輛信息。

圖3 幀信息結(jié)構(gòu)Fig.3 Frame information structure

動態(tài)段的數(shù)據(jù)包結(jié)構(gòu)如圖4 所示，其中，V_id 表示車輛號，ts表示車輛在靜態(tài)段內(nèi)想要占用的靜態(tài)段發(fā)送時隙。

圖4 競爭時隙數(shù)據(jù)包結(jié)構(gòu)Fig.4 Contention time slot data package structure

靜態(tài)段數(shù)據(jù)包結(jié)構(gòu)如圖5 所示。

圖5 發(fā)送時隙數(shù)據(jù)包結(jié)構(gòu)Fig.5 Transmission time slot data package structure

在圖5 中，ssj表示時隙j的狀態(tài)，分別是沖突、空閑或被占用的車輛ID，F(xiàn)表示在區(qū)域xi中，占用當(dāng)前時隙的車輛在下一幀開始時是否駛離當(dāng)前區(qū)域，其值為二值變量，含義為：

當(dāng)車輛成功占用一個時隙后，將一直使用此時隙直到其離開該區(qū)域。如果一輛車成功占用一個時隙，無論它是否需要在服務(wù)信道上傳輸數(shù)據(jù)，都需要在該時隙內(nèi)發(fā)送時隙占用信息和標(biāo)志F信息。

2.2 CTDMAC 協(xié)議機(jī)制

當(dāng)一輛車啟動時，需要盡快得到一個發(fā)送時隙發(fā)送其數(shù)據(jù)。任何車輛v進(jìn)入到一個新的區(qū)域xi時，為防止它搶占其他車輛已經(jīng)成功占用的時隙，需要在靜態(tài)段內(nèi)偵聽鄰居車輛發(fā)送的數(shù)據(jù)，來收集其他鄰居車輛的信息。通過偵聽，車輛v得到xi內(nèi)對應(yīng)的可用時隙集合A(v)。偵聽結(jié)束后，所有新加入的車輛開始通過動態(tài)段內(nèi)的競爭時隙競爭靜態(tài)段內(nèi)的發(fā)送時隙。

算法1競爭時隙過程

算法1 所示為新加入車輛競爭靜態(tài)時隙過程的偽代碼。車輛v在其所對應(yīng)的動態(tài)段內(nèi)隨機(jī)選取一個競爭時隙s發(fā)送數(shù)據(jù)包，并將靜態(tài)段內(nèi)的發(fā)送時隙j的狀態(tài)變?yōu)檎加?。新加入的車輛在動態(tài)段發(fā)送的數(shù)據(jù)包將會被已經(jīng)分配好時隙的車輛偵聽到。因此，v車輛在動態(tài)段內(nèi)發(fā)送的預(yù)留請求是否成功，將會由這些車輛發(fā)送給車輛v。若其他車輛發(fā)送的數(shù)據(jù)包中含有車輛v的預(yù)留請求信息，則車輛v將會在時隙j發(fā)送數(shù)據(jù)，否則，車輛v將釋放發(fā)送時隙j。

在動態(tài)段內(nèi)尚未預(yù)留成功的車輛將會在靜態(tài)段內(nèi)重新隨機(jī)占用空閑發(fā)送時隙。如果在xi內(nèi)只有車輛v發(fā)送預(yù)留時隙請求，則不會發(fā)生沖突。此時，車輛v的所有鄰居節(jié)點(diǎn)u∈N(v)都將其添加到自己的鄰居節(jié)點(diǎn)中，并記錄時隙被其占用。當(dāng)有多輛車同時發(fā)送預(yù)留時隙請求時，則發(fā)生沖突。車輛v將會繼續(xù)發(fā)送請求，直到其成功預(yù)留一個時隙。

為了在下一幀能得到更多的可用時隙，減少訪問沖突發(fā)生的次數(shù)，車輛在離開當(dāng)前區(qū)域之前，將標(biāo)志F設(shè)置為1，以指示在下一幀釋放占用的時隙。

3 訪問沖突分析

假設(shè)道路的長度為L，在道路段xi內(nèi)有m輛新加入的車輛，動態(tài)段內(nèi)競爭時隙的個數(shù)為n，則在動態(tài)段內(nèi)成功發(fā)送的概率為：

在靜態(tài)段內(nèi)成功占用發(fā)送時隙的概率為：

其中，Nscheduled表示上一幀中已經(jīng)被分配好時隙的車輛的個數(shù)，αi、βi分別表示道路段xi對應(yīng)的第一個發(fā)送時隙和最后一個發(fā)送時隙，則在動態(tài)段內(nèi)成功競爭時隙的車輛數(shù)Succtp為：

則未成功占用時隙的車輛數(shù)為：

在動態(tài)段內(nèi)沒成功占用時隙的車輛將會在靜態(tài)段內(nèi)再次占用時隙，則此時其可用時隙為：

因此：

其中，pij表示車輛在道路段xi內(nèi)一輛車成功占用發(fā)送時隙j概率。

其中，Ptotal-ac表示總的訪問沖突的概率，Pno-ac表示車輛沒有發(fā)生沖突的概率，則各個道路段平均發(fā)生沖突的概率為：

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

本文使用MATLAB 作為仿真工具對所提出的協(xié)議進(jìn)行仿真驗(yàn)證，基于以下4 個方面對仿真結(jié)果進(jìn)行評估：

1）新加入車輛成功預(yù)留時隙的速度，表征為訪問延遲。

2）訪問沖突率，每個時隙每個區(qū)域的平均訪問沖突數(shù)。

3）數(shù)據(jù)包丟失率，未成功發(fā)送的信息總數(shù)與總的發(fā)送信息數(shù)的比值。

4）系統(tǒng)吞吐量，成功占用時隙的車輛總數(shù)與可用時隙總數(shù)的比值。

本文使用車輛密度作為衡量道路車輛多少的度量單位［17］，其值為，其中，M為車輛總數(shù)，R為車輛通信半徑，L為道路長度，Ts為當(dāng)前道路段內(nèi)的發(fā)送時隙數(shù)。

在本文的仿真中，一幀的時間為100 ms，其中，包含靜態(tài)段內(nèi)99 個時長1 ms 的發(fā)送時隙和動態(tài)段內(nèi)時長100 個0.01 ms 的競爭時隙。S1、S2分別使用33 個發(fā)送時隙和33 個競爭時隙，剩下的一個競爭時隙不使用。所有車輛的消息都是周期性的，車輛密度變化范圍為0.1～0.9，實(shí)驗(yàn)中使用的仿真參數(shù)如表1 所示。

表1 仿真參數(shù)設(shè)置Table 1 Simulation parameter setting

4.1 新加入車輛成功預(yù)留時隙的速度

本文比較了在不同可用時隙個數(shù)和新加入車輛的情況下的預(yù)留速度，結(jié)果如圖6 所示。其中，N為可用時隙的個數(shù)，K為競爭時隙的車輛數(shù)，n為幀的個數(shù)，實(shí)線表示CTDMAC 的結(jié)果，虛線表示DTMAC 的結(jié)果。

圖6 n 幀內(nèi)時隙的平均節(jié)點(diǎn)數(shù)Fig.6 Average number of time slots in n frames

從圖6 可以看出，當(dāng)參與競爭時隙的車輛數(shù)與可用時隙數(shù)相差過大時（如K=5，N=15 或者K=7，N=20），兩種協(xié)議之間的差異并不大。但是當(dāng)參與競爭時隙的車輛數(shù)與可用時隙數(shù)相差較小時（如K=15，N=15 或者K=17，N=20），因在每一組發(fā)送時隙之前加入了用于協(xié)商的競爭時隙，CTDMAC 在新加入車輛預(yù)留速度上表現(xiàn)了很好的性能，其預(yù)留發(fā)送時隙的時間減少了3 個幀。當(dāng)車輛密度較大時，產(chǎn)生沖突的車輛數(shù)將會增多，沖突率將會變大，而在DTMAC 中沒有競爭時隙機(jī)制，故CTDMAC 可以更快地使新加入的車輛得到時隙，更加適合車輛密度較大的情況。

4.2 訪問沖突率

圖7 所示為兩種調(diào)度方案在不同車輛密度下的訪問沖突概率。CTDMAC 的訪問沖突率遠(yuǎn)小于DTMAC 的訪問沖突率，特別是當(dāng)車輛密度大于0.5時。當(dāng)車流量達(dá)到0.9 時，CTDMAC 的訪問沖突率是3.222%，但是，DTMAC 的訪問沖突率達(dá)到了9.595%，大約減少了1/3。上述結(jié)果表明，CTDMAC減少訪問沖突率明顯優(yōu)于DTMAC。因?yàn)镃TDMAC在每一個時隙組前增加了動態(tài)段供新加入的車輛競爭空閑時隙，所以在靜態(tài)段內(nèi)產(chǎn)生的沖突明顯減少。

圖7 不同車輛密度下訪問沖突的概率Fig.7 Probability of access conflicts under different vehicle densities

4.3 數(shù)據(jù)包丟失率

圖8 所示為不同車輛密度下兩種不同的調(diào)度數(shù)據(jù)包丟失率。仿真結(jié)果顯示，CTDMAC 在相同的車流量密度下數(shù)據(jù)包的丟失率明顯比DTMAC 小。在相同的車輛密度下，兩種調(diào)度需要發(fā)送的數(shù)據(jù)包總量是相同的，因?yàn)镃TDMAC 在每一個時隙組前加入了可以使加入的車輛競爭發(fā)送時隙的動態(tài)段，而且本文增加了車輛是否離開當(dāng)前區(qū)域的判定，減少了對總數(shù)據(jù)包的錯誤計(jì)算，故CTDMAC 的數(shù)據(jù)包丟失率比DTMAC 小。

圖8 不同車流量下數(shù)據(jù)包丟失率Fig.8 Data packet loss rate under different vehicle densities

4.4 系統(tǒng)吞吐量

圖9 所示為不同車輛密度下兩種調(diào)度方案的系統(tǒng)吞吐量。隨著車輛密度的增加，兩種調(diào)度方案的系統(tǒng)吞吐量都是增加的，這是因?yàn)樵谝粋€幀中，隨著車輛密度的增加，成功占用時隙的車輛數(shù)也在增加。從圖9 可以看出，由于在每一組時隙之前加入了動態(tài)段用于新加入的車輛競爭發(fā)送時隙，CTDMAC 的系統(tǒng)吞吐量優(yōu)于DTMAC，而且兩者之間的差異變得越來越大。當(dāng)車輛密度達(dá)到0.8 時，DTMAC 的系統(tǒng)吞吐量只有0.527，而CTDMAC 的系統(tǒng)吞吐量達(dá)到了0.693。

圖9 不同車流量下的系統(tǒng)吞吐量Fig.9 System throughput under different vehicle densities

5 結(jié)束語

本文提出一種基于競爭的時分多址協(xié)議。該協(xié)議將通信幀分為動態(tài)段和靜態(tài)段，新加入的車輛在動態(tài)段中競爭靜態(tài)段內(nèi)的發(fā)送時隙，而在靜態(tài)段內(nèi)發(fā)送數(shù)據(jù)。仿真結(jié)果表明，當(dāng)車輛密度較大時，CTDMAC 能夠明顯降低訪問沖突及網(wǎng)絡(luò)的丟包率，增加系統(tǒng)的吞吐量。本文只考慮控制信道而沒有考慮服務(wù)信道，后續(xù)將繼續(xù)研究MAC 協(xié)議，進(jìn)一步提高信道資源的利用率，避免車輛數(shù)據(jù)發(fā)生沖突。