車載自組織網絡中基于競爭的時分多址MAC 協議

張本宏，吳浩浩，俞 磊

（1.合肥工業大學 計算機與信息學院，合肥 230601；2.安徽中醫藥大學 醫藥信息工程學院，合肥 230012）

0 概述

智能交通系統（Intelligent Transport System，ITS）是將先進的信息技術、通信技術、傳感技術以及計算機技術等有效地綜合運用于整個交通運輸管理體系，在緩解交通阻塞、減少交通事故中發揮著日益突出的作用，成為當前研究熱點之一。而車載自組織網絡（Vehicular Ad Hoc Networks，VANETs）作為ITS 的信息承載平臺，更是受到了人們的廣泛關注。車載自組織網絡是由裝載在車上的車載單元（On-Board Unit，OBU）、路邊的通信基礎設施等組成的自組織無線多跳網絡。在車載自組織網絡中，車輛需要周期性地交換狀態信息以及安全信息等，但是車輛行駛時車速過快、網絡拓撲變化頻繁和無中心等特性［1］造成了車聯網中車與車之間（Vehicle to Vehicle，V2V）和車輛與路邊單元之間（Vehicle to Roadside Unit，V2R）數據傳輸的不可靠。因此，可靠有效的介質訪問控制（Medium Access Control，MAC）協議是人們研究的重點。

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

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

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

1 系統模型和問題描述

1.1 系統模型

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

1.2 問題描述

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

2 CTDMAC 協議

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

圖1 道路分段Fig.1 Road segmentation

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

圖2 時隙集與道路的對應關系Fig.2 Correspondence between time slot set and road

時隙組和道路段根據下面的規則進行映射：

1）如果i%3==1，則xi和S1相關聯。

2）如果i%3==2，則xi和S2相關聯。

3）如果i%3==0，則xi和S3相關聯。采用上述方式，可以保證相鄰道路段之間發送數據時不會發生沖突。

2.1 協議幀格式

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

圖3 幀信息結構Fig.3 Frame information structure

動態段的數據包結構如圖4 所示，其中，V_id 表示車輛號，ts表示車輛在靜態段內想要占用的靜態段發送時隙。

圖4 競爭時隙數據包結構Fig.4 Contention time slot data package structure

靜態段數據包結構如圖5 所示。

圖5 發送時隙數據包結構Fig.5 Transmission time slot data package structure

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

當車輛成功占用一個時隙后，將一直使用此時隙直到其離開該區域。如果一輛車成功占用一個時隙，無論它是否需要在服務信道上傳輸數據，都需要在該時隙內發送時隙占用信息和標志F信息。

2.2 CTDMAC 協議機制

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

算法1競爭時隙過程

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

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

為了在下一幀能得到更多的可用時隙，減少訪問沖突發生的次數，車輛在離開當前區域之前，將標志F設置為1，以指示在下一幀釋放占用的時隙。

3 訪問沖突分析

假設道路的長度為L，在道路段xi內有m輛新加入的車輛，動態段內競爭時隙的個數為n，則在動態段內成功發送的概率為：

在靜態段內成功占用發送時隙的概率為：

其中，Nscheduled表示上一幀中已經被分配好時隙的車輛的個數，αi、βi分別表示道路段xi對應的第一個發送時隙和最后一個發送時隙，則在動態段內成功競爭時隙的車輛數Succtp為：

則未成功占用時隙的車輛數為：

在動態段內沒成功占用時隙的車輛將會在靜態段內再次占用時隙，則此時其可用時隙為：

因此：

其中，pij表示車輛在道路段xi內一輛車成功占用發送時隙j概率。

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

4 仿真結果與分析

本文使用MATLAB 作為仿真工具對所提出的協議進行仿真驗證，基于以下4 個方面對仿真結果進行評估：

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

2）訪問沖突率，每個時隙每個區域的平均訪問沖突數。

3）數據包丟失率，未成功發送的信息總數與總的發送信息數的比值。

4）系統吞吐量，成功占用時隙的車輛總數與可用時隙總數的比值。

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

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

表1 仿真參數設置Table 1 Simulation parameter setting

4.1 新加入車輛成功預留時隙的速度

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

圖6 n 幀內時隙的平均節點數Fig.6 Average number of time slots in n frames

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

4.2 訪問沖突率

圖7 所示為兩種調度方案在不同車輛密度下的訪問沖突概率。CTDMAC 的訪問沖突率遠小于DTMAC 的訪問沖突率，特別是當車輛密度大于0.5時。當車流量達到0.9 時，CTDMAC 的訪問沖突率是3.222%，但是，DTMAC 的訪問沖突率達到了9.595%，大約減少了1/3。上述結果表明，CTDMAC減少訪問沖突率明顯優于DTMAC。因為CTDMAC在每一個時隙組前增加了動態段供新加入的車輛競爭空閑時隙，所以在靜態段內產生的沖突明顯減少。

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

4.3 數據包丟失率

圖8 所示為不同車輛密度下兩種不同的調度數據包丟失率。仿真結果顯示，CTDMAC 在相同的車流量密度下數據包的丟失率明顯比DTMAC 小。在相同的車輛密度下，兩種調度需要發送的數據包總量是相同的，因為CTDMAC 在每一個時隙組前加入了可以使加入的車輛競爭發送時隙的動態段，而且本文增加了車輛是否離開當前區域的判定，減少了對總數據包的錯誤計算，故CTDMAC 的數據包丟失率比DTMAC 小。

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

4.4 系統吞吐量

圖9 所示為不同車輛密度下兩種調度方案的系統吞吐量。隨著車輛密度的增加，兩種調度方案的系統吞吐量都是增加的，這是因為在一個幀中，隨著車輛密度的增加，成功占用時隙的車輛數也在增加。從圖9 可以看出，由于在每一組時隙之前加入了動態段用于新加入的車輛競爭發送時隙，CTDMAC 的系統吞吐量優于DTMAC，而且兩者之間的差異變得越來越大。當車輛密度達到0.8 時，DTMAC 的系統吞吐量只有0.527，而CTDMAC 的系統吞吐量達到了0.693。

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

5 結束語

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