V2V中基于競爭轉發的路由協議改進

于淼淼，于璐巍

(1.許昌學院 信息化管理中心，河南 許昌 461000；2.北京理工大學 信息與電子學院，北京100000)

Ad hoc網絡[1]以其無中心，自組織網絡的特點應用于車聯網(Internet of Vehicles，IoV)的V2V(Vehicle to Vehicle)中，自組織車聯網的路由協議得到了廣泛的研究，旨在提高數據傳輸的到達率，減少數據傳輸延時和路由開銷.

改進了車載自組網通信的探測交通擁堵探測方法CoTEC[2](Coperative Traffic congestion detECtion)，Si-CoTEC采取的CBF(Contention-based Forwarding)競爭轉發機制，提出DCBF基于雙次競爭的轉發路由機制.DCBF采取兩次競爭轉發，一次競爭中考慮的是車輛節點的移動方向和最小連接控制集[3]CDS成員，經過一次競爭成功的節點將參與二次競爭.二次競爭將根據車輛節點的行駛速度以及車輛節點的位置信息設置定時器.DCBF不僅在簡單連接或低密度場景中可以有效構建CDS成員，也適用于復雜連接或高密度場景，且在端到端時延和傳輸成功率均有所提高.

1 信息轉發機制

在消息轉發中，一次競爭首先判斷節點的方向，若與發送節點同向的節點，通過設置最小連接控制集CDS，最小化每個組中所有鄰居的轉播節點的覆蓋數量，最小化遞送到網絡中的大多數節點的重傳次數.消息轉發競爭機制流程如圖1所示.

中繼車輛向所有鄰居廣播CTE消息，接收到該消息的車輛通過啟動定時器進行轉發，定時器的持續時間與它們到前一個轉發節點的距離成和自身速度成反比(高速遠距離的車輛在重新發送消息之前等待較短時間)來安排消息的重新傳輸.當定時器時間結束時就可以轉發Data消息.

1.1 最小連接控制集

車輛行駛時是非均勻分布，密度動態分布.例如，在暢通的高速路上，密度非常稀疏，但在城市十字路口的中部，節點堆積密集.為了使算法適應不同的環境.本文通過選擇具有最高數量的1跳鄰居的節點來限制廣播分組，因為它可以最小化接收到的節點數量，同時最小化重播節點，并且對于每個場景中的所有大小的分組都有效,因此，DCBF使用1跳鄰居數作為算法的主要條件，具有1跳鄰居節點最多的節點是CDS成員，如圖2所示.

確定CDS成員重要的條件是具備網關條件[4].網關節點具有至少一個鄰居，即不被一對網關節點的鄰居覆蓋，并且這兩個鄰居也是彼此的鄰居.例如，判斷節點A是否為網關節點，A需要具有至少一個鄰居D，即不被一對連接的鄰居B和C覆蓋.如果A是網關節點，則鄰居D不被B或C覆蓋.因此，NA不是B或C的鄰居.令NA是一組節點A的鄰居，NB是一組節點B的鄰居，和NC一組節點C的鄰居.B和C是節點A的鄰居.如果節點A同時滿足以下公式，則將其從CDS中消除.

圖1 消息轉發競爭機制流程圖

圖2 最小連接控制集(CDS)

{B,C}∈NA，

(1)

{C}∈NB，

(2)

{B}∈NC，

(3)

NA?NB∪NC.

(4)

因此，CDS中的節點只是覆蓋組中其他節點的必需節點.協議中的節點自己決定是否是CDS成員.如果是CDS成員，收到廣播包后，隨機設置非常短的退避延遲(<10 ms).延遲到期后，它立即重新播送數據包.不是CDS成員的節點將其等待的超時設置為比CDS成員更長的周期.當等待超時不會過期時，他們正在從其他節點接收轉播.如果他們接收到在等待列表中重新播放相同的數據包，即從等待列表中刪除該數據包，以避免冗余重傳.

1.2 傳輸場景

傳輸場景主要包括正常廣播場景和間歇性連接場景，如圖3所示.圖3(a)顯示了正常的廣播情況.S是源節點.令C為具有最高局部密度的節點，因此C將成為CDS成員.當S廣播分組時，A、B和C接收廣播分組.A和B計算他們的等待超時，并等待從CDS成員轉播.C作為CDS成員，在重新播放數據包之前將設置轉發定時器，參與二次競爭.在C正確重播數據包的情況下，A和B將取消其等待超時，以避免冗余重傳.另一方面，如果C不轉播該分組，則具有最短等待超時的A或B將重新廣播分組.若B具有最短的等待超時，所以B重新廣播數據包而不是C.A將取消其等待的超時，不會導致冗余重傳.轉發過程持續到組中的所有節點接收到數據包或直到數據包過期為止.

在間歇連接情況中，節點需要在組間重傳數據包,情景如圖3(b)所示.節點A，B和C已經從S接收到廣播分組.當B超過其他車輛時，它離開舊的組并加入新組.新組中的節點是D，E和F他們從未接收到來自S的廣播分組.B可以通過來自D，E和F的數據確認檢測丟失的分組.B將設置其等待超時，并將其轉發到其他節點.當D，E和F接收到數據包時，它們將作為正常的廣播情況.CDS的成員立即重新播送數據包，而其他成員設置的時間比CDS成員長，直到所有節點接收到數據包或數據包過期.

圖3 傳輸場景

1.3 消息轉發定時器

中繼車輛向所有鄰居廣播CTE消息.接收到該消息的車輛，在一次競爭成功后，通過啟動定時器進行二次競爭轉發.定時器的持續時間與它們到前一個轉發節點的距離、速度最大值、當前速度等有關.通過定時器來安排消息的下一步傳輸.當定時器時間結束時就可以轉發Data消息.按公式(5)計算自身的定時器的等待值.

(5)

Tmax是最大的轉發延時，rradio是廣播直徑.Tmax和rradio均為定值.v為節點的移動速度大小，vmax為所有車輛節點的最大移動速度，T為定時器的等待時間.T越小越容易在競爭中勝出.dis是擁堵位置與本車的距離，因此越大越好，即距離擁堵位置越遠且速度越大的節點越容易二次競爭成功，優先轉發.

2 等待超時機制

等待超時[5]是分布式系統中廣播沖突的解決方案.節點將隨機設置等待超時作為轉播延遲.在兩種情況下啟動等待超時機制.一種情況是非CDS的成員節點接收到廣播數據包時.他們將數據包添加到廣播列表并設置等待超時.這些節點必須接收其鄰居中CDS成員的轉播.如果等待超時結束，并且沒有CDS成員轉播該分組，則具有最短等待超時的節點將重新廣播分組.另一種是當節點從鄰居節點中檢測到丟失的數據包時.他們將數據包添加到廣播列表，并將等待超時設置與第一種情況相同，然后，具有最短等待超時的節點將丟失的分組重新廣播到其鄰居.

等待超時的缺點是它會延遲整個系統.現有的研究多為計算他們的等待超時與1跳鄰居數成反比關系.目的是通過使用具有1跳鄰居最多的節點，使每次重傳中傳遞的節點數量最大，不過這也會觸發競爭問題.由于當節點處于密集區域時，用反比關系函數計算出很短的延遲范圍，所以它在高密度場景中會使冗余重傳增加.因此，同一區域中的大多數節點將具有相同的等待超時.然后他們同時轉播造成沖突.為了防止這種情況，協議使用1跳鄰居的數量來調整等待超時功能的變化.通過設置定向函數防止在極高密度情況下的碰撞.等待超時由公式(6)計算.

W(n)=Random[nτ，(2τ+nβτ)].

(6)

τ表示網絡延遲，即數據包被傳送到接收器為止.n是多個1跳鄰居.β是用于擴展最小等待超時和最大等待超時之間的范圍的常數值.最優狀態下β值可以顯著減少密集區域的碰撞事件，同時只增加較小的延遲.等待超時的最小項表示從MAC層中的數據排隊的延遲可能性.所以最小項將等于所有鄰居的數據發送時間的總延遲.等待超時的最大期限由兩個部分組成.第一項2τ，即網絡延遲的兩倍.這是因為在節點具有一個鄰居的情況下，它們有可能等待來自鄰居的一個數據和來自轉播的另一個網絡延遲.第二項，nβτ是從MAC層中的數據排隊的可能性延遲，即乘以擴展值β.β用于擴展最小項和最大項之間的范圍.

3 擁堵信息數據結構

V2V中車輛之間擁堵消息傳遞采用的是廣播泛洪的方式，擁堵信息的結構[6]在一定程度上影響信息的冗余度，信息傳遞的丟包率，傳輸安全和成功率.故需設計擁堵信息的結構，使接收方在收到信息快速的辨別出有效信息，并且降低信息冗余度，提高信息傳遞成功率.

在DCBF中合作擁堵識別是依靠車輛間信息的傳遞完成的，其中傳遞的消息類型有三種，分別是Beacon、Data、CTE消息.其中Beacon消息用于自身擁堵判別，傳輸車輛的位置、速度等信息，Data消息用于檢測到擁堵后開啟合作檢測，CTE消息用于合作檢測結束后向后車傳遞檢測的擁堵級別.

車輛之間通過周期性地發送Beacon消息來判斷彼此是否能建立通信連接.Beacon消息一般需要包含如下信息：車輛的ID、位置、速度、消息類型、消息有效時間、擁堵程度、排隊長度、安全優先等級等.格式為如圖4所示，其中，Node ID為車輛節點的ID號，Grade安全優先等級，Posi為位置信息，Vel表示車速，Type為消息類型，Length表示擁堵長度，Direction為行車方向，TTL為消息的有效時間.Beacon消息被存儲在車輛節點的歷史消息列表中.消息發布節點或訂閱節點以固定時間間隔τ廣播發送Beacon消息，獲知k跳鄰居節點，通過建立局部網絡拓撲視圖，節點與周圍車輛建立k跳中繼連接.消息發布節點以一定的時間間隔τ廣播發送Beacon消息，獲知k跳鄰居節點.

圖4 Beacon數據結構

DCBF中的節點使用Data消息發現1跳鄰居并交換其本地信息.Data消息報頭包括：源標識符，1跳鄰居數，1跳鄰居標識符列表和仍未過期的接收報文列表，擁堵判別信息.接收到的分組的列表包含發送源的標識符和分組的標識符.此列表用于檢測丟失的信息.在沒有1跳鄰居和接收到的數據包的情況下，數據大小將至少為5個字節.數據大小將為每個1跳鄰居增加4個字節，并為每個接收到的數據包增加5個字節.為了減少數據的數量，如圖5所示.當它們具有重播分組時，節點用廣播分組背對數據頭，然后下一個數據將被推遲到下一個數據間隔.

圖5 Data、CTE數據結構

4 仿真結果和分析

為了評估DCBF算法在監控交通擁堵的應用性，進行仿真驗證，重點分析了端到端時延數據包投遞率和路由開銷.使用交通模擬器SUMO產生逼真的車輛運動軌跡.在NS3中進行模擬仿真.表1為參數配置.

表1 交通仿真參數設置

4.1 數據包投遞率

Si-CoTEC可以實時的評估車輛四周的密度信息，并且利用估算的密度信息和行駛速度對當前的路況進行評級.圖6顯示了DCBF和Si-CoTEC在不同的車輛節點場景中，數據包投遞率變化情況.從圖中能夠看出：隨著車輛節點數目的增多，DCBF、Si-CoTEC的數據包的投遞率也隨之提高，投遞率均在0.5以上，并且當節點數目增多時，在車輛數達到100以上時，DCBF投遞率高達90%，Si-CoTEC為80%.此外，DCBF比Si-CoTEC協議數據包的投遞率提高得更快.由于車輛節點數目較少的車聯網的連通性不好，很容易造成網絡分割最終導致路由的失敗，所以車輛節點數目較少的時候DCBF和Si-CoTEC的數據包投遞率均不是很高.而隨著車輛節點數目的增多，車聯網的連通性有所改善，因而數據包的投遞率也會隨之提高.同時也可以看出在車輛節點數目相同的情況下，所提出的DCBF數據包的投遞率比Si-CoTEC要高，說明本文提出的DCBF的丟包率更小.

4.2 路由開銷

圖7顯示了DCBF和Si-CoTEC在100個車輛節點的城市場景中，不同車速下的路由開銷.從圖中能夠看出：DCBF數據包的路由開銷大于Si-CoTEC，這是由于DCBF在采用了兩次競爭，在選擇最小控制集成員時會產生開銷，但隨著車輛節點速度的增大，DCBF的開銷并未受到太大的影響，均在2*104左右，Si-CoTEC則會因為速度的變化路由開銷逐漸增大，在速度為30 m/s的時候，Si-CoTEC的路由開銷跟DCBF相近.

圖6 數據包投遞率

圖7 路由開銷

5 結語

主要介紹了V2V中擁堵信息的轉發過程.在車載Ad-hoc無中心，自組織的多跳背景下，消息轉發的泛洪問題也是影響V2V在智能交通系統中發展的原因.介紹了DCBF為了平衡有限的帶寬和通信資源及龐大的節點發送需求之間的沖突，提高消息的傳遞率，改進了CoTEC，Si-CoTEC采取的CBF競爭轉發機制，將原本的位置轉發競爭機制改進為兩次競爭.一次競爭中在方向同向的競爭后添加了最小連接控制集成員的競爭條件，介紹了最小連接控制集為競爭條件的優勢以及方法.二次競爭中將Si-CoTEC采取的距離發送節點最遠等待時間最短的條件改進為考慮速度和距離雙重因素來設置定時器，更能適應與車輛的動態環境，使DCBF無論是在節點密集的城市和節點稀疏的高速路，均能更好的傳遞信息，降低廣播風暴.