分布式VANETs 中車(chē)流自適應(yīng)的低沖突TDMA-MAC 協(xié)議*

程 凱，張信明

(中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥230026)

0 引言

車(chē)載自組織網(wǎng)絡(luò) (Vehicular Ad Hoc Networks，VANETs) 作為智能交通系統(tǒng)不可或缺的組成部分，自被提出以來(lái)就因其在車(chē)聯(lián)網(wǎng)領(lǐng)域的廣闊應(yīng)用前景而受到學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注[1]。它是一種在移動(dòng)車(chē)輛之間或車(chē)輛與路邊基礎(chǔ)設(shè)施之間通過(guò)短距離通信技術(shù)實(shí)現(xiàn)互連的專(zhuān)用網(wǎng)絡(luò)，能夠?yàn)榻煌▍⑴c者所需要的安全類(lèi)、服務(wù)類(lèi)、管理類(lèi)等豐富的上層應(yīng)用提供網(wǎng)絡(luò)支持[2]。

在分布式VANETs 中，車(chē)輛節(jié)點(diǎn)在控制信道上周期性廣播的基礎(chǔ)安全消息 （Basic Safety Message，BSM）是整體網(wǎng)絡(luò)高效、可靠運(yùn)行的重要一環(huán)[3]。一方面安全類(lèi)應(yīng)用可以據(jù)此進(jìn)行事故規(guī)避、風(fēng)險(xiǎn)評(píng)估以及駕駛輔助等諸多決策，另一方面依據(jù)該消息中車(chē)輛信息進(jìn)行上層協(xié)議的優(yōu)化也能提高非安全類(lèi)應(yīng)用的各項(xiàng)性能指標(biāo)[4]。因此如何在多節(jié)點(diǎn)之間合理、高效、低沖突地分配控制信道資源，實(shí)現(xiàn)BSM的可靠傳輸是分布式場(chǎng)景中媒體訪問(wèn)控制層（Medium Access Control，MAC）協(xié)議設(shè)計(jì)至關(guān)重要的問(wèn)題[5]。時(shí) 分多 址 （Time Division Multiple Access，TDMA）機(jī)制被認(rèn)為是一種能確保節(jié)點(diǎn)及時(shí)、可靠傳輸各類(lèi)消息的高效方案，尤其是在中高節(jié)點(diǎn)密度場(chǎng)景中表現(xiàn)突出，然而在VANETs 中，由于節(jié)點(diǎn)高速移動(dòng)、網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化等特性所導(dǎo)致的接入沖突與融入沖突，將影響沖突節(jié)點(diǎn)傳輸BSM 的時(shí)效性，進(jìn)而降低整體網(wǎng)絡(luò)的安全性與穩(wěn)定性[6]。

接入沖突是指一跳或兩跳鄰居節(jié)點(diǎn)之間由于彼此沒(méi)有優(yōu)先級(jí)區(qū)分，在同時(shí)預(yù)約相同時(shí)隙（slot）時(shí)產(chǎn)生碰撞[7]。融入沖突是指原本能夠復(fù)用slot 的節(jié)點(diǎn)由于網(wǎng)絡(luò)拓?fù)渥兓蔀閮商従雍螽a(chǎn)生的沖突[8]。發(fā)生融入沖突的節(jié)點(diǎn)需要重新預(yù)約slot，進(jìn)而增加接入沖突發(fā)生次數(shù)。為了降低由復(fù)用slot 的節(jié)點(diǎn)之間速度差異導(dǎo)致的融入沖突與后續(xù)接入沖突，學(xué)術(shù)界已經(jīng)提出了較多協(xié)議，主流方案是依據(jù)運(yùn)動(dòng)屬性對(duì)節(jié)點(diǎn)與幀內(nèi)slot 進(jìn)行分組。其中文獻(xiàn)[9]提出的VeMAC 協(xié)議依據(jù)運(yùn)動(dòng)方向劃分幀內(nèi)slot，節(jié)點(diǎn)按照行駛方向預(yù)約對(duì)應(yīng)分組內(nèi)slot，有效降低了不同方向節(jié)點(diǎn)隨機(jī)預(yù)約slot 導(dǎo)致的沖突。為了進(jìn)一步降低由同向節(jié)點(diǎn)速度差異導(dǎo)致的沖突，部分工作在VeMAC 的基礎(chǔ)上繼續(xù)細(xì)化節(jié)點(diǎn)運(yùn)動(dòng)屬性從而進(jìn)一步劃分slot 分組，例如文獻(xiàn)[10]提出的CFR-MAC協(xié)議將同向節(jié)點(diǎn)分為高、中、低速三類(lèi)。

但在實(shí)際應(yīng)用中，道路上的雙向車(chē)流往往是動(dòng)態(tài)變化的，兩個(gè)方向上的節(jié)點(diǎn)數(shù)目并不平衡。這在實(shí)際生活中也較為常見(jiàn)，例如早晚高峰路段，同時(shí)不同區(qū)域內(nèi)的車(chē)流分布也不完全相同。在分組長(zhǎng)度固定的方案中，當(dāng)一側(cè)方向上節(jié)點(diǎn)數(shù)目超出對(duì)應(yīng)分組的slot 負(fù)載時(shí)，節(jié)點(diǎn)只得借用其他分組內(nèi)slot，此時(shí)分組方案的優(yōu)勢(shì)被大大削弱，沖突發(fā)生的概率隨之增加[11]。為了緩解動(dòng)態(tài)車(chē)流對(duì)協(xié)議降低沖突效果的影響，文獻(xiàn)[12]提出依據(jù)節(jié)點(diǎn)視角內(nèi)兩側(cè)方向上鄰居節(jié)點(diǎn)數(shù)目與對(duì)應(yīng)分組內(nèi)slot 數(shù)目的關(guān)系進(jìn)行分組調(diào)整的A-VeMAC 協(xié)議，然而節(jié)點(diǎn)的左右兩跳鄰居之間由于超出沖突范圍被允許復(fù)用slot，使之存在過(guò)早調(diào)整與超出需求等局限性，反而會(huì)降低協(xié)議性能。

針對(duì)上述動(dòng)態(tài)變化的雙向車(chē)流帶來(lái)的挑戰(zhàn)以及現(xiàn)有工作的不足，本文提出一種車(chē)流自適應(yīng)、低沖 突 的TALC-MAC 協(xié) 議 （Traffic Adaptive and Low Collision MAC），主要貢獻(xiàn)在于：

（1）針對(duì)現(xiàn)有分組調(diào)整方案的局限性，T ALC-MAC使用slot 占用率作為分組調(diào)整的判斷依據(jù)，在滿足特定條件時(shí)對(duì)slot 占用率較高方向的分組長(zhǎng)度進(jìn)行逐幀擴(kuò)展或收縮，以適應(yīng)車(chē)流實(shí)際分布，減緩動(dòng)態(tài)變化的雙向車(chē)流對(duì)協(xié)議性能的影響。

（2）考慮到分組長(zhǎng)度調(diào)整方案中在雙向分組相交處發(fā)生沖突概率大的問(wèn)題，TALC-MAC 依據(jù)分組間相對(duì)速度關(guān)系設(shè)計(jì)幀內(nèi)slot 分組方案，安排具體分組位置，有效降低相對(duì)速度差異較大的節(jié)點(diǎn)復(fù)用slot 在分組長(zhǎng)度調(diào)整過(guò)程中發(fā)生沖突的概率。

（3）對(duì)于網(wǎng)絡(luò)中不可避免出現(xiàn)節(jié)點(diǎn)預(yù)約slot 時(shí)與其運(yùn)動(dòng)屬性對(duì)應(yīng)的分組中已無(wú)空閑slot 的情況，TALC-MAC 提供一種低沖突的slot 預(yù)約策略，節(jié)點(diǎn)綜合考慮自身運(yùn)動(dòng)屬性、速度劃分因子、各分組內(nèi)slot 占用情況以及分組調(diào)整條件，決定其預(yù)約slot的最終選擇。

1 系統(tǒng)模型與問(wèn)題描述

1.1 系統(tǒng)模型概述

如圖1 所示，網(wǎng)絡(luò)場(chǎng)景由一段雙向道路構(gòu)成，節(jié)點(diǎn)是以分布式形式組織的車(chē)輛，從道路的某個(gè)入口駛?cè)朐摱蔚缆凡⒔尤刖W(wǎng)絡(luò)，行駛一段時(shí)間后從某個(gè)出口駛離該段道路并離開(kāi)網(wǎng)絡(luò)，若其實(shí)際行駛方向有西向分量則定義為左向，否則為右向[9]。節(jié)點(diǎn)搭載半雙工收發(fā)器異步接收和發(fā)送各類(lèi)消息，同時(shí)搭載全球定位系統(tǒng) （Global Position System，GPS）信號(hào)接收設(shè)備同步全局時(shí)間與獲取車(chē)輛信息，包括自身位置、速度與方向等。

圖1 分布式VANETs 系統(tǒng)模型及兩類(lèi)沖突示意圖

節(jié)點(diǎn)在獲取到的slot 到達(dá)時(shí)廣播通告包，其中包含BSM，同時(shí)攜帶所有一跳鄰居（通信半徑為R）的slot 使用情況。在駛?cè)氲缆坊蛘叱霈F(xiàn)沖突需要接入網(wǎng)絡(luò)時(shí)，首先監(jiān)聽(tīng)一幀時(shí)長(zhǎng)的信道時(shí)間來(lái)收集并解析兩跳鄰居的slot 使用情況，按照協(xié)議選擇一個(gè)與兩跳范圍內(nèi)所有鄰居均不沖突的空閑slot 進(jìn)行預(yù)約，避免出現(xiàn)直接沖突，最后通過(guò)下一幀中所有鄰居的通告包確認(rèn)預(yù)約是否成功[13]。成功占用slot的節(jié)點(diǎn)僅在駛離道路或者出現(xiàn)沖突后才會(huì)釋放當(dāng)前占用的slot 資源。

圖1 中展示了兩類(lèi)沖突發(fā)生的情況，節(jié)點(diǎn)X 與節(jié)點(diǎn)Y 同時(shí)預(yù)約相同slot，在兩者的共同一跳鄰居A 處發(fā)生接入沖突。節(jié)點(diǎn)X 與節(jié)點(diǎn)Z 原本由于沒(méi)有公共鄰居而復(fù)用slot，當(dāng)相對(duì)位置發(fā)生變化后在公共鄰居B 處發(fā)生融入沖突。如圖2 所示，網(wǎng)絡(luò)中的時(shí)間被劃分為固定長(zhǎng)度為T(mén)F的時(shí)間幀，每個(gè)時(shí)間幀進(jìn)一步被劃分為S 個(gè)slot，分為左向SL與右向SR兩個(gè)分組。

圖2 網(wǎng)絡(luò)時(shí)間劃分示意圖

1.2 融入沖突概率與節(jié)點(diǎn)相對(duì)速度的關(guān)系

本小節(jié)描述兩節(jié)點(diǎn)發(fā)生融入沖突的概率與其相對(duì)速度的關(guān)系。規(guī)定速度、位置右向?yàn)檎僭O(shè)節(jié)點(diǎn)A 與節(jié)點(diǎn)B 占用了相同slot，速度分別為VA與VB。當(dāng)前為0 時(shí)刻，B 在A 右側(cè)，即兩者位置滿足PA＜PB。兩節(jié)點(diǎn)保持速度使位置越來(lái)越近，且發(fā)生融入沖突時(shí)兩者距離為DM，時(shí)刻為T(mén)M，易知在不考慮節(jié)點(diǎn)離開(kāi)網(wǎng)絡(luò)的前提下不論方向如何均有：

考慮節(jié)點(diǎn)會(huì)從某個(gè)路口離開(kāi)網(wǎng)絡(luò)，假設(shè)離開(kāi)網(wǎng)絡(luò)時(shí)刻分別為T(mén)A與TB，網(wǎng)絡(luò)最大持續(xù)時(shí)間為T(mén)max，定義事件F 為A 與B 發(fā)生融入沖突，顯然需要滿足TM＜TA且TM＜TB。固定TM，在 時(shí)間軸上隨機(jī)選擇TA與TB的位置，易知F 發(fā)生的概率為：

顯然兩節(jié)點(diǎn)速度差異越大，發(fā)生融入沖突的概率也就越大。該結(jié)果驗(yàn)證了分組長(zhǎng)度固定的方案在面對(duì)動(dòng)態(tài)變化的雙向車(chē)流時(shí)存在的問(wèn)題，即節(jié)點(diǎn)借用對(duì)向分組內(nèi)slot，使相對(duì)速度差異較大的節(jié)點(diǎn)之間復(fù)用slot，進(jìn)而增大P(F)。此外發(fā)生融入沖突的節(jié)點(diǎn)需要重新預(yù)約slot，進(jìn)而增大接入沖突發(fā)生概率，也即動(dòng)態(tài)變化的雙向車(chē)流影響了分組方案降低沖突的效果。

1.3 兩跳鄰居數(shù)目與占用slot 數(shù)目的關(guān)系

本小節(jié)描述節(jié)點(diǎn)X 視角內(nèi)兩跳鄰居數(shù)目與所占用slot 數(shù)目之間的關(guān)系。如圖3 所示，僅考慮單個(gè)方向（右向）與固定的進(jìn)入網(wǎng)絡(luò)順序，節(jié)點(diǎn)僅依據(jù)方向選擇對(duì)應(yīng)分組內(nèi)的空閑slot，不考慮沖突以及節(jié)點(diǎn)超出分組內(nèi)slot 閾值的情況。假設(shè)X 左右兩跳范圍內(nèi)均勻分布著4N 個(gè)與之同向的鄰居節(jié)點(diǎn)。節(jié)點(diǎn)依次進(jìn)入網(wǎng)絡(luò)，對(duì)于X 及其右側(cè)的2N+1 個(gè)節(jié)點(diǎn)，由于彼此位于兩跳范圍內(nèi)，必須預(yù)約互不相同的slot，因此X 接入網(wǎng)絡(luò)后SR(X)中被占用的slot 數(shù)目|SOR(X)|為2N+1。

圖3 節(jié)點(diǎn)X 兩跳鄰居與占用slot 分析示意圖

當(dāng)X 左側(cè)節(jié)點(diǎn)L1接入網(wǎng)絡(luò)時(shí)，由于R1超出兩跳范圍，因此在L1視角內(nèi)SR被占用了2N 個(gè)slot。定義事件F10與F11分別為L(zhǎng)1選擇了與R1相同和不同的slot，從而使得|SOR(X)|增加0 或1，易知兩者概率分別為：

易得由于L1加入網(wǎng)絡(luò)|SOR(X)|的期望變?yōu)椋?/p>

X 左側(cè)節(jié)點(diǎn)繼續(xù)加入網(wǎng)絡(luò)，不難發(fā)現(xiàn)當(dāng)編號(hào)為L(zhǎng)K的節(jié)點(diǎn)進(jìn)入網(wǎng)絡(luò)時(shí)，其預(yù)約完slot 使X 視角內(nèi)SR(X)被占用slot 數(shù)目增加了Q 個(gè)的事件FKQ概率為：

此時(shí)|SOR(X)|的期望變?yōu)椋?/p>

當(dāng)X 左側(cè)2N 個(gè)節(jié)點(diǎn)全部加入網(wǎng)絡(luò)后，期望變?yōu)椋?/p>

X 加上自身兩跳范圍內(nèi)共4N+1 個(gè)節(jié)點(diǎn)，因此兩跳鄰居數(shù)目與所占用的slot 數(shù)目之間存在差距，且節(jié)點(diǎn)密度越高時(shí)差距越大。這主要源于X 的左側(cè)和右側(cè)兩跳鄰居之間已經(jīng)超出沖突域范圍（2R），無(wú)法從自身一跳鄰居的通告包中感知到對(duì)方占用slot 的情況，因此被允許復(fù)用slot。若考慮出現(xiàn)沖突需要重新預(yù)約slot，顯然節(jié)點(diǎn)有更大概率與自身兩跳范圍外的節(jié)點(diǎn)復(fù)用slot。X 視角內(nèi)兩跳鄰居中左向與右向節(jié)點(diǎn)集合分別為NTL(X)與NTR(X)，車(chē)流平衡度定義由式（9）給出，顯然越不平衡的場(chǎng)景中上述差距越明顯。

A-VeMAC 依據(jù)TBRX與分組內(nèi)slot 數(shù)目的關(guān)系進(jìn)行分組調(diào)整[12]，會(huì)出現(xiàn)兩個(gè)問(wèn)題：（1）過(guò)早調(diào)整，達(dá)到閾值條件時(shí)單向分組內(nèi)仍有足量空閑slot；（2）超出需求，調(diào)整后節(jié)點(diǎn)密度較高方向的slot 數(shù)目超出實(shí)際需求。兩個(gè)問(wèn)題使得調(diào)整部分長(zhǎng)度無(wú)法控制，并不能適應(yīng)車(chē)流實(shí)際分布，重新預(yù)約該部分slot 的節(jié)點(diǎn)發(fā)生沖突概率大幅增加，反而會(huì)降低協(xié)議性能。

2 TALC-MAC 協(xié)議

基于上述系統(tǒng)模型與問(wèn)題描述，本節(jié)將詳細(xì)闡述TALC-MAC 的設(shè)計(jì)。首先提出一種基于slot 占用率的分組長(zhǎng)度自適應(yīng)調(diào)整方案；其次依據(jù)相對(duì)速度關(guān)系設(shè)計(jì)幀內(nèi)slot 分組方案，安排具體分組的位置；最后提供一種低沖突的slot 預(yù)約策略。

2.1 分組長(zhǎng)度自適應(yīng)調(diào)整方案

節(jié)點(diǎn)X 進(jìn)入網(wǎng)絡(luò)時(shí)|SL(X)|與|SR(X)|相等，在每一幀結(jié)束時(shí)更新得到左右兩個(gè)分組內(nèi)slot 占用率分別為：

slot 占用率與分組內(nèi)被占用slot 數(shù)目有關(guān)，占用率越高則剩余的空閑slot 數(shù)目越少，若該方向上節(jié)點(diǎn)繼續(xù)增加，X 預(yù)約slot 時(shí)將借用對(duì)向分組，此時(shí)需要進(jìn)行分組擴(kuò)展以適應(yīng)車(chē)流分布。給出如下參數(shù)定義：

（1）Hmax：分組擴(kuò)展時(shí)節(jié)點(diǎn)密度較高方向?qū)?yīng)分組中slot 占用率上限閾值。

（2）Lmax：分組擴(kuò)展時(shí)節(jié)點(diǎn)密度較低方向?qū)?yīng)分組中slot 占用率上限閾值。

（3）Umin：分組擴(kuò)展時(shí)節(jié)點(diǎn)密度較低方向?qū)?yīng)分組預(yù)留的slot 數(shù)目占整個(gè)幀長(zhǎng)的最小比值。

（4）RE：節(jié)點(diǎn)密度較高方向?qū)?yīng)分組擴(kuò)展的單位slot 數(shù)目占整個(gè)幀長(zhǎng)的比值。

假設(shè)當(dāng)前節(jié)點(diǎn)X 視角內(nèi)左側(cè)方向上節(jié)點(diǎn)密度較高，如圖4 所示在滿足式（12）條件時(shí)X 時(shí)間幀內(nèi)SL(X)將從兩分組相交處向SR(X)一側(cè)擴(kuò)展EX個(gè)slot。

圖4 分組長(zhǎng)度擴(kuò)展示意圖

條件1 規(guī)定所有節(jié)點(diǎn)僅能對(duì)節(jié)點(diǎn)密度較高方向分組進(jìn)行擴(kuò)展。條件2 規(guī)定節(jié)點(diǎn)提前進(jìn)行調(diào)整，防止多節(jié)點(diǎn)擴(kuò)展分組后同時(shí)預(yù)約slot 導(dǎo)致接入沖突。條件3 保護(hù)SR(X)在其slot 占用率較高時(shí)不接受來(lái)自對(duì)向的分組擴(kuò)展。遞增EX直至不滿足下式：

同樣為保護(hù)SR（X），需要使其在被收縮之后slot占用率仍不超過(guò)Lmax。其次為防止車(chē)流極度不平衡時(shí)SL（X）的擴(kuò)展一直持續(xù)至超出閾值，需要為右向節(jié)點(diǎn)預(yù)留定量slot。最后為避免1.3 節(jié)所述超出需求的問(wèn)題，協(xié)議限制了單個(gè)時(shí)間幀內(nèi)分組擴(kuò)展的最大長(zhǎng)度為：

式中依據(jù)兩分組slot 占用率比值進(jìn)行調(diào)整以適應(yīng) 雙 向 車(chē) 流 平 衡 度 的 動(dòng) 態(tài) 性。SL（X）相 比SR（X）而 言slot 占用率差距越明顯，則允許擴(kuò)展的長(zhǎng)度越大，否則越小。

綜上，在面對(duì)動(dòng)態(tài)的非平衡車(chē)流時(shí)，位于相近區(qū)域內(nèi)擁有相似視角的節(jié)點(diǎn)將依據(jù)上述方案同步進(jìn)行雙向分組長(zhǎng)度的調(diào)整，使SL（X）與SR（X）的長(zhǎng)度盡量滿足對(duì)應(yīng)方向上節(jié)點(diǎn)數(shù)目的實(shí)際需求。在后續(xù)重新預(yù)約slot 時(shí)依據(jù)新的分組調(diào)整預(yù)約策略，逐步使此區(qū)域內(nèi)節(jié)點(diǎn)占用slot 的情況與車(chē)流實(shí)際分布相適應(yīng)。

考慮到真實(shí)場(chǎng)景中雙向車(chē)流平衡度往往是動(dòng)態(tài)變化的，節(jié)點(diǎn)可能從左側(cè)方向上節(jié)點(diǎn)密度較高的區(qū)域行駛到右側(cè)節(jié)點(diǎn)密度較高的區(qū)域。也即在X的視角內(nèi)隨著網(wǎng)絡(luò)拓?fù)渥兓?，左?cè)方向上節(jié)點(diǎn)數(shù)目不斷降低，導(dǎo)致SL（X）內(nèi)slot 占用率也隨之降低，當(dāng)達(dá)到某一閾值后即可對(duì)SL（X）進(jìn)行收縮。給出如下參數(shù)補(bǔ)充：

（1）Dmax：分組收縮時(shí)節(jié)點(diǎn)密度較高方向?qū)?yīng)分組中slot 占用率上限閾值。

（2）RC：節(jié)點(diǎn)密度較高方向?qū)?yīng)分組收縮的單位slot 數(shù)目占整個(gè)幀長(zhǎng)的比值。

如圖5 所示在滿足式（15）條件時(shí)X 時(shí)間幀內(nèi)SL（X）將 從 兩 分 組 相 交 處 向SL（X）一 側(cè) 收 縮CX個(gè)slot。

圖5 分組長(zhǎng)度收縮示意圖

首先分組收縮的前提是SL（X）在之前的時(shí)間幀內(nèi)被擴(kuò)展，也即前文所述的分組擴(kuò)展僅從節(jié)點(diǎn)密度較高方向進(jìn)行。其次要求經(jīng)過(guò)網(wǎng)絡(luò)拓?fù)渥兓骃L（X）的slot 占用率降低到閾值Dmax。遞增CX直至不滿足下式：

SL（X）在收縮之后需要確保slot 占用率不超過(guò)Hmax，以避免數(shù)個(gè)時(shí)間幀內(nèi)該分組需要再進(jìn)行擴(kuò)展的情況發(fā)生。其次分組擴(kuò)展與收縮都是以節(jié)點(diǎn)密度較高方向?yàn)橹?，起始和終止條件均為雙向分組長(zhǎng)度相等。CX的最大長(zhǎng)度由下式給出：

此時(shí)依據(jù)雙向分組長(zhǎng)度的比值來(lái)調(diào)整，當(dāng)分組SL（X）需要收縮時(shí)其長(zhǎng)度相比SR（X）越長(zhǎng)則允許收縮的長(zhǎng)度也越大，反之越小。上述分組長(zhǎng)度自適應(yīng)調(diào)整過(guò)程在右側(cè)方向上節(jié)點(diǎn)密度較高時(shí)也可以進(jìn)行類(lèi)似操作。整體策略可以形式化為GLA （Group Length Adjustment）算法，偽代碼如下：

算法1：GLA

輸 入：SL（X），SR（X），Hmax等參數(shù)；

（1）if |SL（X）|≥|SR（X）|，執(zhí)行步驟（2）～（5）。

（2）if 式（12）成立，執(zhí)行步驟（3）。

（3）for i∈[1,max(EX)]，重復(fù)步驟（3.a）～（3.c）：

（3.c）if 式（13）不成立，break。

（4）if 式（15）成立，執(zhí)行步驟（5）。

（5）for i∈[1,max(CX)]，重復(fù)步驟（5.a）～（5.c）：

（5.c）if 式（16）不成立，break。

（6）if |SL（X）|≤|SR（X）|，重復(fù)步驟（2）～（5），修改對(duì)應(yīng)公式中的L與R。

2.2 幀內(nèi)slot 分組方案

細(xì)致的幀內(nèi)slot 分組方案在面對(duì)動(dòng)態(tài)變化的雙向車(chē)流時(shí)，將更容易出現(xiàn)分組內(nèi)slot 占用率超出閾值的情況，使得不同運(yùn)動(dòng)屬性的節(jié)點(diǎn)預(yù)約相同分組內(nèi)slot，反而會(huì)降低分組優(yōu)勢(shì)，此外在真實(shí)車(chē)流場(chǎng)景中往往無(wú)法確定合適的運(yùn)動(dòng)屬性劃分標(biāo)準(zhǔn)。因此如圖6 所示，TALC-MAC 僅考慮將單向分組進(jìn)一步劃分為等長(zhǎng)的兩個(gè)較小分組，分別表示相對(duì)高速與相對(duì)低速，四個(gè)較小分組分別命名為L(zhǎng)H、LL、RH 與RL。

圖6 幀內(nèi)分組方案示意圖

依據(jù)1.2 節(jié)分析，復(fù)用slot 的兩節(jié)點(diǎn)相對(duì)速度差異越大，發(fā)生融入沖突的概率越高。2.1 節(jié)中基于slot 占用率的分組調(diào)整方案在一定程度上緩解了動(dòng)態(tài)變化的雙向車(chē)流對(duì)協(xié)議性能的影響，但是在調(diào)整部分（EX與CX段）發(fā)生融入沖突的概率依舊較大，這是由節(jié)點(diǎn)使用slot 的行為特性決定的。

已有工作中幀內(nèi)較小分組位置安排完全相同[10]，而分組調(diào)整一般在雙向分組相交處開(kāi)展。若沿用此方案，則預(yù)約了相交處的兩個(gè)較小分組內(nèi)slot 的節(jié)點(diǎn)之間速度差異較大 （如LH 與RL），致使在適應(yīng)車(chē)流分布的過(guò)程中節(jié)點(diǎn)密度較高方向上預(yù)約了調(diào)整部分slot 的節(jié)點(diǎn)，與對(duì)向上在調(diào)整前已經(jīng)占用了相同slot 的節(jié)點(diǎn)之間發(fā)生沖突概率較大。

假設(shè)節(jié)點(diǎn)均勻分布，高速與低速節(jié)點(diǎn)的速度分別符合正態(tài)分布N（μH,）與N（μL,），μH＞μL。在不考慮分組內(nèi)無(wú)空閑slot 的情況下，預(yù)約了四個(gè)較小分組內(nèi)slot 的節(jié)點(diǎn)之間平均相對(duì)速度差異由大到小表示為：

（1）ΔV(LH,RH)=2μH；

（2）ΔV(LH,RL)=ΔV(LL,RH)=μH+μL；

（3）ΔV(LL,RL)=2μL；

（4）ΔV(LH,LL)=ΔV(RH,RL)=μH-μL。

TALC-MAC 依據(jù)上述相對(duì)速度關(guān)系安排幀內(nèi)具體分組的位置，使相對(duì)速度差異較大的分組之間盡量遠(yuǎn)離，從而降低相對(duì)速度差異較大的節(jié)點(diǎn)復(fù)用slot 的概率。也即將LH 與RH 兩個(gè)相對(duì)速度差異最大的分組安排在時(shí)間幀兩端，LL 與RL 兩個(gè)較低速分組安排在雙向分組相交處，此時(shí)在分組調(diào)整前后預(yù)約了調(diào)整部分slot 的節(jié)點(diǎn)均相對(duì)低速，從而降低了由分組調(diào)整導(dǎo)致的在分組相交處發(fā)生沖突的概率。

2.3 slot 預(yù)約策略

由于節(jié)點(diǎn)占用slot 的規(guī)則以及分組長(zhǎng)度自適應(yīng)調(diào)整方案的限制，在車(chē)流動(dòng)態(tài)變化的場(chǎng)景中，不可避免會(huì)出現(xiàn)節(jié)點(diǎn)預(yù)約slot 時(shí)與其運(yùn)動(dòng)屬性對(duì)應(yīng)的分組中無(wú)空閑slot 的情況。已有工作允許此類(lèi)節(jié)點(diǎn)隨機(jī)預(yù)約整個(gè)時(shí)間幀內(nèi)的空閑slot[10]，此時(shí)這些節(jié)點(diǎn)與其他節(jié)點(diǎn)之間速度差異較大，發(fā)生沖突的概率也較大，對(duì)此TALC-MAC 提供一種低沖突的slot 預(yù)約策略。

當(dāng)節(jié)點(diǎn)X 新加入網(wǎng)絡(luò)或者由于出現(xiàn)沖突需要重新預(yù)約slot 時(shí)，首先依據(jù)從GPS 獲得的自身速度方向決定其運(yùn)動(dòng)方向，即決定DX的取值為L(zhǎng) 或R。其次依據(jù)解析到的一跳鄰居通告包內(nèi)容，根據(jù)式（18）計(jì)算其與m 個(gè)同向節(jié)點(diǎn)之間的速度差異。

其中k 定義為速度劃分因子，其設(shè)置目標(biāo)是使節(jié)點(diǎn)有更大概率接入運(yùn)動(dòng)方向上的High 分組，從而使該方向Low 分組中盡可能預(yù)留出空閑slot，從而進(jìn)一步降低在分組相交處發(fā)生沖突的概率。X 依據(jù)當(dāng)前所在區(qū)域內(nèi)鄰居節(jié)點(diǎn)的速度分布，決定其是較高速節(jié)點(diǎn)還是較低速節(jié)點(diǎn)，即確定SX，若ΔV≥0，則SX取值為H，否則為L(zhǎng)。

定義E（DX,SX）為當(dāng)前時(shí)間幀內(nèi)方向?yàn)镈X、相對(duì)速度為SX的較小分組中所有空閑slot 編號(hào)構(gòu)成的集合。當(dāng)X 需要預(yù)約slot 時(shí)，若E（DX,SX）=?，即首選分組內(nèi)無(wú)空閑slot，則更新SX為｛H,L｝中另一個(gè)元素，借用同向另一個(gè)分組內(nèi)slot。

若此時(shí)E（DX,SX）=? 仍成立，即同向大分組內(nèi)無(wú)空閑slot，先進(jìn)行分組長(zhǎng)度調(diào)整的判斷，若達(dá)到2.1 節(jié)所述條件則調(diào)整后重新進(jìn)行預(yù)約。在不能進(jìn)行分組調(diào)整時(shí)更新DX為｛L,R｝中另一個(gè)元素，且SX為L(zhǎng)，即優(yōu)先借用對(duì)向低速分組內(nèi)slot。若仍無(wú)空閑slot 則更新SX為H，即最后才借用對(duì)向高速分組內(nèi)slot。當(dāng)上述過(guò)程中出現(xiàn)E（DX,SX）≠?，即可隨機(jī)選擇一個(gè)slot 預(yù)約，若最后仍無(wú)空閑slot 則本次預(yù)約失敗。

上述細(xì)化的slot 預(yù)約策略考慮了2.2 節(jié)所述分組的相對(duì)速度差異。在面對(duì)動(dòng)態(tài)變化的雙向車(chē)流時(shí)，節(jié)點(diǎn)將綜合考慮自身運(yùn)動(dòng)屬性、 各分組內(nèi)slot占用情況以及分組調(diào)整條件，決定其預(yù)約slot 的最終選擇，從而有效降低節(jié)點(diǎn)隨機(jī)預(yù)約整個(gè)時(shí)間幀內(nèi)空閑slot 所導(dǎo)致的沖突。

3 仿真實(shí)驗(yàn)

3.1 仿真環(huán)境與參數(shù)

本節(jié)在操作系統(tǒng)為Ubuntu18.04.5 的環(huán)境中進(jìn)行仿真實(shí)驗(yàn)，利用網(wǎng)絡(luò)仿真模擬器OMNeT++[14]與無(wú)線通信仿真框架Veins[15]搭建仿真環(huán)境，修改Veins 框架中的MAC 層代碼實(shí)現(xiàn)相關(guān)對(duì)比協(xié)議與所提TALC-MAC，同時(shí)使用城市移動(dòng)仿真軟件SUMO[16]生成真實(shí)運(yùn)動(dòng)車(chē)輛與道路模型，設(shè)計(jì)不同場(chǎng)景驗(yàn)證所提協(xié)議的性能表現(xiàn)。具體相關(guān)參數(shù)設(shè)置見(jiàn)表1。

表1 實(shí)驗(yàn)參數(shù)設(shè)置

為模擬真實(shí)場(chǎng)景，除道路兩端出入口外還在兩方向中間各設(shè)置一個(gè)出入口。各節(jié)點(diǎn)依據(jù)正態(tài)分布選擇初始速度，依據(jù)3 s 原則確定車(chē)距后加入網(wǎng)絡(luò)。節(jié)點(diǎn)到達(dá)道路中間等概率選擇繼續(xù)行駛或者離開(kāi)網(wǎng)絡(luò)，離開(kāi)節(jié)點(diǎn)將從中間位置入口再次加入網(wǎng)絡(luò)。到達(dá)終點(diǎn)的節(jié)點(diǎn)再返回出發(fā)點(diǎn)以維持節(jié)點(diǎn)總數(shù)不變。為模擬動(dòng)態(tài)變化的雙向車(chē)流，僅限制節(jié)點(diǎn)最大行駛速度，不限制加速、減速、出入口排隊(duì)等行為。以兩個(gè)方向上的節(jié)點(diǎn)總數(shù)比值設(shè)置平均車(chē)流平衡度（TBR）（左向節(jié)點(diǎn)較多），而不限制單個(gè)節(jié)點(diǎn)視角內(nèi)TBR。確定單向節(jié)點(diǎn)總數(shù)后安排各車(chē)道節(jié)點(diǎn)數(shù)目，車(chē)速越快的車(chē)道節(jié)點(diǎn)數(shù)越少。部分參數(shù)取值經(jīng)調(diào)優(yōu)確定，所有節(jié)點(diǎn)加入網(wǎng)絡(luò)后統(tǒng)計(jì)仿真時(shí)長(zhǎng)內(nèi)各項(xiàng) 指 標(biāo)，對(duì) 比 協(xié) 議 為VeMAC[9]、A-VeMAC[10]與CFR-MAC[12]。

3.2 仿真結(jié)果與性能分析

首先分析本文所提分組長(zhǎng)度自適應(yīng)調(diào)整方案（TALC-GLA）的性能表現(xiàn)，圖7 和圖8 分別展示了仿真時(shí)間內(nèi)不同協(xié)議在不同TBR 下兩種沖突率的對(duì)比，沖突率定義為平均單個(gè)時(shí)間幀內(nèi)沖突發(fā)生次數(shù)。TBR 為0.8，0.9 和1 時(shí)左向道路上并未出現(xiàn)明顯的節(jié)點(diǎn)數(shù)目超出閾值的情況，因此沖突率較為穩(wěn)定，將其平均值作為各協(xié)議基準(zhǔn)。當(dāng)TBR 繼續(xù)減小，左向節(jié)點(diǎn)數(shù)目不斷增加，VeMAC 中開(kāi)始大量出現(xiàn)借用右向分組內(nèi)slot 的情況，致使兩種沖突率顯著增加。例如TBR 為0.7 時(shí)融入沖突率較穩(wěn)定狀態(tài)僅增加5.7% ，而TBR 為0.1 時(shí)該指標(biāo)激增到124%。接入沖突率一般較小因此影響更為明顯，TBR 為0.7 時(shí)較穩(wěn)定狀態(tài)增加34.8%，但TBR 為0.1 時(shí)激增到穩(wěn)定狀態(tài)的16.6 倍。由此可見(jiàn)動(dòng)態(tài)變化的雙向車(chē)流對(duì)分組長(zhǎng)度固定的協(xié)議性能的巨大影響。

圖7 不同車(chē)流平衡度下接入沖突率

圖8 不同車(chē)流平衡度下融入沖突率

相比之下A-VeMAC 較好地適應(yīng)了雙向車(chē)流，但正如1.3 節(jié)所分析，該方案存在一定局限性?？紤]到右向節(jié)點(diǎn)的平均數(shù)目，在TBR 為0.4，0.5 與0.6 時(shí)過(guò)早調(diào)整與超出需求所帶來(lái)的影響最為明顯，接入沖突率較穩(wěn)定狀態(tài)分別增加了115%，82.8%與44.7%，而融入沖突率分別增加了36.1%，36.4%與24.9%，在TBR 為0.6 時(shí)融入沖突率甚至超過(guò)了VeMAC，由此可見(jiàn)A-VeMAC 存在的局限性影響了協(xié)議的性能。

TALC-GLA 中基于slot 占用率進(jìn)行分組長(zhǎng)度調(diào)整的方案很好地適應(yīng)了雙向車(chē)流的動(dòng)態(tài)變化，接入沖突率較穩(wěn)定狀態(tài)的增加率始終保持在20.0%以內(nèi)，最差情況在TBR 為0.4 時(shí)該指標(biāo)較A-VeMAC的115%而言降低了82.7%。在分組長(zhǎng)度調(diào)整過(guò)程中融入沖突的增加雖然無(wú)法避免，但最差情況在TBR 為0.1 時(shí)融入沖突率較穩(wěn)定狀態(tài)也僅增加19.3%。在A-VeMAC 出現(xiàn)顯著局限性的TBR 為0.4，0.5 和0.6 時(shí)，融入沖突率較A-VeMAC 分別降低了0.062，0.074 與0.046，可見(jiàn)所提方案在適應(yīng)雙向車(chē)流分布上的優(yōu)勢(shì)。

圖9 展示了不同參數(shù)下各協(xié)議通告包投遞率的對(duì)比，該指標(biāo)反映節(jié)點(diǎn)在控制信道上周期性廣播的通告包被鄰居節(jié)點(diǎn)成功接收的數(shù)量。由于仿真場(chǎng)景相同，因此影響投遞率的主要因素即為網(wǎng)絡(luò)整體沖突率。隨著TBR 的降低，VeMAC 中投遞率也不斷降低，例如從TBR 為1.0 降到0.1 時(shí)，投遞率降低了0.1%，而A-VeMAC 和TALC-GLA 分別降低了0.04% 和 0.03% 。同 樣，TBR 為 0.4 和 0.5 時(shí)，TALC-GLA 的投遞率相比于A-VeMAC 分別提升0.02%和0.01%。盡管該數(shù)值較小，但考慮到所有節(jié)點(diǎn)廣播通告包的周期很短 （0.1 s），而被成功接收的通告包越多，BSM 中的信息越及時(shí)，因此所提分組調(diào)整方案有效提升了整體網(wǎng)絡(luò)的安全與可靠。

圖9 不同車(chē)流平衡度下通告包投遞率

圖10 展示了不同參數(shù)下各協(xié)議兩種沖突率的對(duì)比，將僅按照相對(duì)速度進(jìn)行細(xì)化分組，但并未調(diào)整具體分組位置，也未優(yōu)化預(yù)約策略的對(duì)照協(xié)議稱(chēng)為T(mén)ALC-UNOP。CFR-MAC 與VeMAC 類(lèi) 似，隨 著TBR 不斷降低兩種沖突率顯著上升。而對(duì)于TALCMAC，最差情況下TBR 為0.1 時(shí)融入沖突率較穩(wěn)定狀態(tài)也僅增加20.8%，接入沖突率較穩(wěn)定狀態(tài)的增加率也始終保持在54.5%以內(nèi)。對(duì)于TALC-UNOP，在不同TBR 下融入沖突率相較于TALC-MAC 均有不同程度的增加，例如TBR 為0.5 時(shí)增加了0.005，為0.3 時(shí)增加了0.029，而為0.1 時(shí)增加了0.032。接入沖突由于整體發(fā)生次數(shù)較少，增加并不明顯。由此可見(jiàn)所提幀內(nèi)slot 分組方案與slot 預(yù)約策略進(jìn)一步降低了整體網(wǎng)絡(luò)的沖突率。

圖10 不同車(chē)流平衡度下沖突率

圖11 展示了不同參數(shù)下各協(xié)議接入時(shí)延的對(duì)比，由于未考慮數(shù)據(jù)包傳輸?shù)绕渌麜r(shí)延，因此僅考慮節(jié)點(diǎn)從預(yù)約slot 到成功占用slot 所經(jīng)歷的時(shí)延。隨著TBR 降低，VeMAC 與CFR-MAC 接入時(shí)延不斷提高，例 如VeMAC 在TBR 為0.1 時(shí) 相 比1.0 時(shí)增 加 了4.72 個(gè)slot，而CFR-MAC 增 加 了2.63個(gè)slot，可見(jiàn)分組固定方案的接入時(shí)延受到不平衡雙向車(chē)流的影響較大。而分組調(diào)整方案有效降低了接入時(shí)延，相比于A-VeMAC，在TBR為0.4 和0.5 時(shí)，TALC-MAC 接入時(shí)延分別降低了0.44 和0.55 個(gè)slot。由 此 可 見(jiàn)TALC-MAC在降低整體網(wǎng)絡(luò)接入時(shí)延，加快節(jié)點(diǎn)接入網(wǎng)絡(luò)的速度上仍然具有優(yōu)勢(shì)。

圖11 不同車(chē)流平衡度下接入時(shí)延

4 結(jié)論

本文針對(duì)分布式車(chē)載自組織網(wǎng)絡(luò)設(shè)計(jì)了一種 車(chē) 流 自 適 應(yīng)、 低 沖 突 的TALC-MAC 協(xié) 議，通過(guò)將slot 占用率作為判斷依據(jù)設(shè)計(jì)分組調(diào)整方案，同時(shí)優(yōu)化slot 分組方案與預(yù)約策略，使協(xié)議能有效適應(yīng)雙向車(chē)流的動(dòng)態(tài)變化，保持整體網(wǎng)絡(luò)低沖突的特性。仿真實(shí)驗(yàn)結(jié)果從沖突率、通告包投遞率、 接入時(shí)延等方面驗(yàn)證了TALC-MAC 協(xié)議具有較優(yōu)的性能表現(xiàn)。