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

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

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

1 引言

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

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

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

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

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

2 系統(tǒng)模型

2.1 場景設定

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

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

圖1 時隙規(guī)劃圖

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

2.2 幀信息FI

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

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

圖2 MDATS協(xié)議總體流程

MDATS協(xié)議針對節(jié)點X定義以下5類相關(guān)集合:

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

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

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

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

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

3 MDATS時隙分配機制

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

3.1 初始化過程

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

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

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

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

3.2 邏輯區(qū)段-空閑時隙映射過程

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

3.3 時隙分配過程

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

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

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

節(jié)點X發(fā)現(xiàn)其可用空閑時隙集為空,即無空閑時隙可用,則節(jié)點X可將另一個行駛方向?qū)目臻e時隙集擴展為自己可用的空閑時隙集,并從中隨機選擇一個空閑時隙競爭接入信道.

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

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

4 性能仿真與分析

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

圖3 MDATS時隙分配示意圖

圖4 仿真場景

表1 網(wǎng)絡性能仿真參數(shù)設置

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

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

圖5 n幀內(nèi)所有節(jié)點成功獲得時隙的概率

圖6 平均成功節(jié)點數(shù)

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

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

圖7 沖突節(jié)點數(shù)

5 結(jié)束語

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