改進的VANET分布式自適應時分多址分配機制①

王夢雪,徐哲鑫,吳 怡,林 瀟

(福建師范大學 光電與信息工程學院,福州 350007)

1 引言

車載自組織網(Vehicular Ad-hoc Network,VANET)[1]具有節點高移動性、拓撲高動態性及節點軌跡規律性等特點,使得介質訪問控制(Medium Access Control,MAC)協議成為VANET研究的重點之一[2–4].目前,車載自組織網MAC協議主要分成基于“競爭”的、基于“非競爭”的[5].基于“競爭”的MAC協議以CSMA/CA(Carrier Sense Multiple Access with Collision Avoidance)為基礎,其中最為經典的是IEEE 802.11p協議[6–8].IEEE 802.11p協議被批準成為VANET 標準MAC協議之一,但是其隨機性的信道接入機制導致接入延遲無界,難以精確預估.另外,當車輛節點密度高時,信道沖突急劇增加,導致吞吐量和傳輸延遲性能嚴重惡化[9].基于“非競爭”的MAC協議[10,11]中,車輛節點依照一定規則有序使用信道資源,其中以時分多址(Time Division Multiple Access,TDMA)機制應用最為廣泛.TDMA[12]機制將頻率信道從時間維度上劃分為連續時間幀,每一個時間幀又分割成若干個固定時長的時隙,節點以時隙為信道接入的基本單位.TDMA機制主要分為集中式和分布式兩大類[13].相比于集中式TDMA需要中心控制器集中分配時隙,分布式 TDMA 無需中心控制器,節點以一定的秩序自主分配時隙的機制顯然更加靈活,更加適應于拓撲高度變化的VANET.

ADHOC MAC協議[14]是經典的分布式TDMA MAC協議,以RR-ALOHA協議[15]為基礎.車輛節點間通過交互幀信息(Frame Information,FI),其中包含一跳鄰居節點時隙占用信息,獲知其兩跳范圍內鄰居節點的時隙占用信息,并隨機選擇一個空閑時隙競爭接入信道.ADHOC MAC協議解決了隱藏節點的問題,但在拓撲變化較頻繁和節點密度較高的場景下,信道接入沖突較為嚴重.其后續改進的版本[16,17]主要解決ADHOC MAC協議時隙利用率較低的問題,并沒有解決密集場景下信道沖突嚴重的問題.

VeMAC協議[18]在ADHOC MAC協議的基礎上,為不同行駛方向的車輛節點與路邊基礎設施(Road-Side Unit,RSU)分配不同的時隙集LRF,降低對向行駛的車輛節點間信道沖突的可能性,提高通信鏈路生存期.VeMAC協議存在的問題是同向車輛節點間仍然隨機地選擇空閑時隙來競爭接入信道,當節點密度較高時,由于時隙集的劃分導致節點可用空閑時隙范圍變小,信道接入性能嚴重惡化.

文獻[19]提出分布式自適應TDMA調度策略(Decentralized Adaptive TDMA Scheduling strategy,DATS).DATS協議車輛節點根據自己與最近車輛節點的相對位置關系競爭對應的空閑時隙.DATS協議利用車輛節點行駛方向與地理位置的差異性,有效緩解VeMAC協議隨機選擇空閑時隙造成的信道沖突嚴重的問題.但由于車輛節點的運動受限于道路環境和交通法規,當多個地理位置接近的車輛節點同時進入網絡時,DATS協議通過對時隙子集中剩余空閑時隙均分后隨機獲取完成新加入節點時隙分配,然而這種隨機性在高節點密度時將導致嚴重的沖突.此外,DATS協議根據實時車輛密度變化,動態調整不同行駛方向車輛節點左右時隙集時隙數的節點協商機制較為復雜,不適應于拓撲快速變化的VANET.

為了解決DATS協議中多節點同時接入信道時的競爭沖突問題,本文提出改進的分布式自適應時分多址分配機制(Modified Decentralized Adaptive TDMA Scheduling mechanism,MDATS).MDATS主要借鑒空分多址(Space Division Multiple Access,SDMA)的思想,根據可用空閑時隙數將同向最近已接入信道節點的通信區域均分為若干邏輯區段.車輛節點根據自己的地理位置信息,以及邏輯區段與空閑時隙的映射關系選擇對應的空閑時隙競爭接入信道.MDATS協議通過邏輯區段與空閑時隙的映射關系,將位置接近且同時接入網絡的車輛節點競爭的時隙在空間上分散化,達到提高信道接入成功率和降低信道接入延遲的目的.同時,MDATS協議摒棄了DATS協議中復雜的左右時隙集時隙數協商調整機制.MDATS協議中,當節點發現可用空閑時隙集為空,即無空閑時隙可用時,允許該節點將對向道路對應的空閑時隙集作為自己的可用空閑時隙集,達到擴展可用空閑時隙集,提高時隙利用率的目的.

2 系統模型

2.1 場景設定

道路上每隔一定距離鋪設路邊基礎設施(Road-Side Unit,RSU),為其覆蓋范圍內的車輛節點周期性地廣播道路基本信息、幀結構信息、網絡基本信息等.每個車輛節點均配備車載通信單元(Onboard Unit,OBU)、全球定位系統(Global Positioning System,GPS)等設備.車輛節點通過GPS定位系統周期性獲取精確的地理位置信息,判斷行駛方向,同時通過GPS模塊提供的1PPS信號實現車輛節點間的時鐘同步.

本文主要考慮雙向四車道的城市道路場景.為了降低對向行駛的車輛節點間的信道沖突的概率,本文將每幀的時隙劃分為左時隙集SL和右時隙集SR,分配給不同行駛方向的車輛節點.如圖1所示,車輛行駛方向定義如下:以南北方向線為基準,車輛節點行駛方向位于其左邊定義其行駛方向為左;車輛節點行駛方向位于其右邊的定義其行駛方向為右,如圖1所示.因此,左時隙集SL和右時隙集SR分別分配給左行駛方向R的車輛節點和右行駛方向DR的車輛節點進行信道接入.

圖1 時隙規劃圖

車輛節點僅接收通信半徑R范圍內的鄰居節點(即一跳鄰居節點)發送的信號,通信范圍之外節點的信號默認無法接收.但隱藏節點的問題仍然存在,導致節點同時接收通信范圍內多個鄰居節點發送的信號而無法正確解析信號,造成信道沖突.

2.2 幀信息FI

為了保證道路環境的安全性,每個車輛節點必須周期性地廣播自己的位置、速度、方向信息為安全應用提供服務.此外,為了保證車輛節點能夠獲知其兩跳鄰居節點的時隙占用信息,每個車輛節點還必須周期性地發送幀信息[14],其中包含節點自己及其一跳鄰居節點的時隙占用信息.

對于每個節點而言,空閑時隙定義為未被其兩跳鄰居節點占用的時隙.同時,MDATS協議中定義新加入節點為初始接入網絡,還未成功占用時隙的節點;成功節點定義為已成功占用時隙的節點.一旦節點成功占用一個時隙,即無沖突地接入信道,則在接下來的每幀里該節點都將占用相同的時隙,直至發生信道沖突或該節點無通訊需求時才釋放該時隙.

圖2 MDATS協議總體流程

MDATS協議針對節點X定義以下5類相關集合:

list(X):節點X的一跳鄰居節點運動狀態信息列表,具體內容包括其一跳鄰居節點的ID、位置信息、速度、行駛方向以及所占用的時隙號.

TL(X):節點X兩跳鄰居節點中行駛方向為左的節點所占用的時隙號.

TR(X):節點X兩跳鄰居節點中行駛方向為右的節點所占用的時隙號.

IL(X):左時隙集SL中節點X可用空閑時隙號.

IR(X):右時隙集SR中節點X可用空閑時隙號.

3 MDATS時隙分配機制

MDATS時隙分配機制可分為初始化過程、邏輯區段-空閑時隙映射過程、時隙分配過程和可用空閑時隙集擴展的過程,其詳細的機制流程如圖2所示.

3.1 初始化過程

新加入節點X根據GPS定位系統獲得自己的位置信息(x,y),判斷其行駛方向dr.當節點X 初始接入網絡時,首先偵聽信道一幀的時長,接收其一跳鄰居節點發送的運動狀態信息與FI消息.節點X根據一跳鄰居節點的運動狀態信息,維護運動狀態信息列表list(X)={(id1,x1,y1,v1,dr1,s1),···,(idn,xn,yn,vn,drn,sn)},其中idi、xi、yi、vi、dri、si(i=1,2,…,n)分別為節點X的一跳鄰居節點i的ID、位置坐標、速度、行駛方向以及所占用的時隙號.同時,節點X根據一跳鄰居節點廣播的FI 消息,收集其兩跳鄰居節點的時隙占用信息TL(X)、TR(X),從而可計算出左空閑時隙集和右空閑時隙集,且分別定義IL(X)、IR(X)對應的空閑時隙數分別為NLI(X)、NRI(X).

節點X根據自己的行駛方向dr選擇對應的空閑時隙集IL(X)或IR(X)作為可用空閑時隙集.節點X檢查list(X)是否為空集,即節點X是否有一跳鄰居節點.若list(X)為空集,則節點X從可用空閑時隙集IL(X)或IR(X)中隨機選擇一個空閑時隙進行信道接入;若list(X)不為空集,則節點X根據list(X)計算距離自己最近的同向成功節點,計算公式如下:

其中,(x′,y′)為節點X相同行駛方向上的一跳鄰居節點的位置信息,即(x′,y′)∈list(X)且dr′=dr.

若節點X根據公式(1)得到多個距離相等的最近同向成功節點,即節點X位于最近同向成功節點的中間.節點X選擇占用時隙號最小的最近同向成功節點作為參考節點.

3.2 邏輯區段-空閑時隙映射過程

假設節點X的參考節點為Y,則將節點Y通信區域均分為M個邏輯區段.當 X ∈DL時,M=NLI(X);當X∈DR時,M=NRI(X).其中邏輯區段1～M沿節點所在車道行駛方向連續排列,空閑時隙依照時隙號由小到大,且沿車道行駛方向排列,逐一對應于相應的邏輯區段,形成邏輯區段-空閑時隙映射表.

3.3 時隙分配過程

節點X判斷自己位于參考節點的第m個邏輯區段,則根據邏輯區段-空閑時隙映射表選擇在邏輯區段m對應的空閑時隙tm競爭接入信道,其中m∈ {1,2,3,···,M}.節點X的一跳鄰居節點在時隙tm成功接收到節點X發送的數據后,將自己FI消息中時隙tm標識為節點X的ID.若節點X在接下來一幀時長內接收的所有的FI消息中時隙tm均標識為節點X的ID,則表示節點X成功占用時隙tm.否則表示節點X未成功占用時隙tm,與其他車輛節點發生信道沖突,則當下一幀到來時,節點X從對應空閑時隙子集中隨機選擇一個空閑時隙競爭信道.

若節點X成功占用時隙tm,則在接下來的每幀中都使用該時隙,直至發生信道沖突或該節點無通訊需求時,才釋放該時隙.

3.4 可用空閑時隙集擴展過程

節點X發現其可用空閑時隙集為空,即無空閑時隙可用,則節點X可將另一個行駛方向對應的空閑時隙集擴展為自己可用的空閑時隙集,并從中隨機選擇一個空閑時隙競爭接入信道.

圖3表示了MDATS協議詳細的時隙分配示意圖,車輛節點A、E、F、G為成功節點且分別占用時隙7、時隙2、時隙3、時隙4.假設車輛節點B、C、D為右行駛方向上的新加入節點且同時準備接入網絡.為了更加簡潔明了地介紹MDATS時隙分配過程,首先以車輛節點B為例詳細分析時隙占用過程.

車輛節點B根據GPS定位系統獲得地理位置信息,判斷自己的行駛方向為右.當車輛節點準備接入網絡時,首先在信道上偵聽一幀的時長,通過接收車輛節點A、E、F、G的FI消息,獲知TL(B)={2,3,4},TR(B)={7},故而能夠計算出IL(B)={1,5},IR(B)={6,8,9,10}.由于車輛節點B其行駛方向為右,故選擇空閑時隙集IR(B)作為可用空閑時隙集,可用空閑時隙數NRI=4.同時,根據公式(1)計算得知其同向最近的成功節點為車輛節點A,則將車輛節點A通信區域沿著道路方向劃分為4個相等的邏輯區段,將邏輯區段與IR(B)的空閑時隙號進行一一映射,形成邏輯區段-空閑時隙映射表.車輛節點B判斷自己位于邏輯區段1,則根據邏輯區段-空閑時隙映射表選擇與邏輯區段1對應的空閑時隙6來競爭接入信道.同理,由于車輛節點C、D與車輛節點B同時接入網絡,根據公式(1)計算同向最近的成功節點也是車輛節點A,故邏輯區段-空閑時隙映射表與車輛節點B的相同.車輛節點C、D判斷自己的行駛方向為右,分別位于邏輯區段3與邏輯區段4,故車輛節點C選擇競爭接入時隙9,車輛節點D選擇競爭接入時隙10.

4 性能仿真與分析

本文利用交通流仿真軟件SUMO(Simulation of Urban Mobility)[20]和Matlab工具構建VANET仿真環境.SUMO是一個微觀的、多模態的、空間連續的、時間離散的交通流仿真平臺,通過道路環境和車輛行駛模型的設定生成相應交通流數據.仿真過程中,首先利用SUMO工具生成交通流數據,將其導入Matlab中構建VANET的通信環境,仿真VAENT MAC協議.本文所選的對比對象為DATS協議[19]、VeMAC協議[18]、ADHOC MAC協議[14].仿真參數如表1所示,仿真場景示意圖如圖4所示,本文采用3 km×3 km曼哈頓網格為道路拓撲形狀,雙向四車道的道路場景如圖3.

圖3 MDATS時隙分配示意圖

圖4 仿真場景

表1 網絡性能仿真參數設置

假設,每幀時長為Tframe,幀數為n,每幀的時隙數量為N,新加入節點數為K.圖5表示n幀內所有新加入節點成功獲得時隙的概率.當N=20,K=20時,若要保證9 5%以上的新加入節點成功獲得時隙,MDATS協議和DATS協議都需要4個幀長,即時延τ=4·Tframe;VeMAC協議需要 5個幀長,時延τ=5·Tframe;ADHOC MAC協議需要6個幀長,時延τ=6·Tframe.當N=64,K=50時,若要保證95%以上的新加入節點成功獲得時隙,MDATS協議和DATS協議都需要3個幀長,即時延 τ=3·Tframe;VeMAC協議需要4個幀長,時延 τ=4·Tframe;ADHOC MAC協議需要4個幀長,時延 τ=4·Tframe.MDATS協議相比于DATS協議,雖然整體時延相近,但在相同時間維度時,MDATS協議有更多數量的節點成功獲得時隙.因為MDATS協議將地理位置相近且同時接入網絡的新加入節點選擇的空閑時隙分散化,降低信道沖突的概率.MDATS協議相對于VeMAC協議至少能減少20%的接入時延,而比ADHOC MAC協議至少能減少30%的接入時延.

圖6表示每個幀成功獲取時隙節點的平均數目,即平均成功節點數.由圖6可以看出,當N=100,K=100時,MDATS協議在5幀內就能夠讓所有新加入節點都成功接入信道,而DATS協議需要6幀,VeMAC協議與ADHOC MAC協議則需要12幀.當N=100,K=50時,MDATS協議在3幀內就能夠讓所有新加入節點都成功接入信道,而DATS協議需要4幀,VeMAC協議與ADHOC MAC協議則需要5幀.因此,當N＞K時,MDATS協議能夠使車輛節點相比于其他三類MAC協議更加快速地接入信道,且平均成功節點數更多.當N=K時,MDATS協議的優勢就更為明顯.

圖5 n幀內所有節點成功獲得時隙的概率

圖6 平均成功節點數

圖7則是比較了不同節點密度下,MDATS、DATS、VeMAC、ADHOC MAC四種MAC協議在沖突節點數上的對比.相同節點密度的場景下,MDATS協議比DATS協議降低至少40%的沖突節點數,比VeMAC協議降低至少50%的沖突節點數,比

ADHOC MAC協議降低至少60%的沖突節點數.其原因在于,MDATS協議通過借鑒空分多址的概念,將新加入節點競爭的空閑時隙在空間上分散化,降低信道沖突的概率.而DATS協議僅是將相對位置和行駛方向作為新加入節點競爭的空閑時隙的依據,競爭時隙選擇范圍較小,比MDATS協議更易發生信道沖突.VeMAC協議和ADHOC MAC協議則是完全隨機地選擇空閑時隙來競爭接入信道,信道沖突概率比DATS協議更高.

圖7 沖突節點數

5 結束語

本文針對VANET環境下,為了解決DATS協議中多節點同時接入信道時的競爭沖突問題,提出改進的分布式自適應時分多址分配機制.MDATS協議借鑒空分多址的概念,新加入節點根據可用空閑時隙集的空閑時隙數將同向最近成功節點的通信區域劃分為若干邏輯區域,并形成邏輯區域與空閑時隙的映射關系.新加入節點根據邏輯區域-空閑時隙映射關系,則競爭接入相應的空閑時隙.MDATS協議將位置接近且同時接入網絡的新加入節點所競爭的時隙分散化,緩解信道沖突嚴重的情況.同時,在MDATS協議利用可用空閑時隙擴展過程代替了DATS協議復雜的左右時隙比例協商調整機制,當節點發現自己的可用空閑時隙集為空,即無空閑時隙可用時,可將對向道路空閑時隙集作為自己的擴展可用空閑時隙集使用,以提高時隙利用率.由仿真結果可得,MDATS協議中的車輛節點相比于DATS協議接入時延更小,節點能夠更加快速地接入信道,信道沖突率更低;當節點密度相同時,MDATS協議相比于DATS協議降低至少40%的沖突節點數;MDATS協議與VeMAC協議、ADHOC MAC協議相比,網絡性能提升更為顯著.