0 引言

    隨著自組織無線通信和車輛技術的快速發展，在不久的將來，交通信息方向將發生重大轉變。未來，將采用分布式的移動探測點(Probes)收集和分布實時的交通信息，不再引用嵌入基于基礎系統中的固定傳感節點。車輛的分布式網絡，即車聯網VANETs(Vehicular ad hoc networks)^[1-2]成為無基礎設施、自組織的交通信息系統。在VANET中，每個車輛就是一個移動傳感節點，承擔收集、分發交通信息的角色。

    分發交通信息是VANETs中最根本的問題。相比于Internet內的單播數據，交通信息通常具有定向廣播(Broadcast-oriented)特性。換而言之，交通信息是公共利益(Public interest)，受益的是一群車輛，而不是某個體車輛。因此，與單播協議相比，廣播方案更適合于VANETs。廣播方案的主要優勢在于車輛不需要目的地址，而單播協議需要準確的目的地址，這就避免了路由發現、地址解析以及拓撲管理等復雜環節^[3-4]。 為此，本文著重分析VANETs的廣播方案。目前，研究人員已提出許多廣播方案，這些方案可分為單跳廣播和多跳廣播。

    在多路廣播方案中，通過網絡泛洪方式傳輸數據包。通常，當源車輛廣播了信息數據包后，位于源車輛鄰近區域的車輛就變成下一跳轉發車輛(節點)，并扮演著通過重播轉發數據包的任務。類似地，后續的車輛繼續轉發數據包。通過這種方式，能夠將源節點的數據包傳輸至遠距離的車輛。

    目前，研究人員已提出眾多的基于多跳的廣播協議，如圖1所示。本文針對這些多跳廣播協議進行分析，解析它們的特點。

1 多跳廣播協議

    多跳廣播協議是通過泛洪方式傳遞數據包。然而，在VANETs使用純(Pure)泛洪方案是不足夠的，原因有兩點：可擴展性和數據包碰撞。隨著網絡密度的增加，導致相同的數據包在網絡內反復重傳，這將引起信道帶寬的浪費，這就說明純泛洪方案不適應于密集網絡，不具有可擴展性。此外，在密集網絡，由于在同一個區域大量數據包同時廣播，不可避免會引起數據包碰撞，即廣播風暴問題^[5]。為此，一個優質的多跳廣播協議必須要解決這兩個問題。

    目前，解決擴展性和碰撞兩個問題的常用方法就是降低冗余重傳數據包的數量。換而言之，只選擇部分車輛重傳數據包。依據現在多跳廣播協議特性，可分為基于時延、基于概率和基于網絡編碼的多跳廣播方案。

1.1 基于時延多跳廣播

    所謂基于時延多跳廣播就是每個接收了數據包的車輛在轉發數據包之前，設定不同的延時等待，只有延時完畢，再轉發數據包，具有最短延時等待的車輛具有重播數據包的最高優先權，此外，為了避免冗余，一旦監聽到其他車輛已重播了數據包，車輛放棄等待。通常，延時時間是關于車輛與傳輸數據包的源車輛間的距離函數，一般距離越遠，延時時間越短，成為下一跳重播節點的幾率越大。接下來，分析幾種典型的基于時延多跳廣播方案的特性。

1.1.1 城市多跳廣播UMB方案^[6]

    UMB(Urban Multi-Broadcast)方案目的在于解決廣播風暴、節點隱藏以及多跳廣播中的可靠性問題。UMB方案首先將源節點傳輸范圍內的道路劃分幾個區域(Segments)，位于最遠Segments內的車輛具有優先轉發數據包的權力。此外，UMB方案引用定向-廣播(directional broadcast)和十字路口廣播(Intersection broadcast)兩種模式。

    在定向-廣播(directional broadcast)模式中，當車輛i需要發送數據包時，i首先傳輸請求廣播控制包RTB(Request -to-Broadcast)，其包含了自己的位置和數據包傳輸方向。位于車輛i傳輸范圍內的車輛一旦收到RTB，它們就開始傳輸被稱為Black-burst的干擾信號(Jamming Signal)。Black-burst的時長L是關于車輛i與接收RTB的車輛間的距離d的函數，如式(1)所示。

    其中R表示車輛的傳輸范圍、S表示時隙的時長。從式(1)可知 ，距離d越遠，時長L越長。

    車輛(假定車輛j)傳輸了Black-burst后，車輛j繼續監聽信道。如果發現信道忙，則表明有其他車輛正在傳輸Black-burst。在這種情況下，車輛j將放棄轉發數據包的權力。轉發數據包的任務由其他車輛完成。反之，若信道是空閑的，車輛j向車輛i回復被稱為消除廣播的數據包CTB(Clear-to-Broadcast)。成功傳輸了CTB的車輛被選為轉發數據包的下一跳車輛。

    一旦車輛i接收到CTB，車輛i就開始傳輸DATA數據包。當車輛j收到DATA數據包后，車輛j向車輛i回復確認數據包ACK。如果在規定時間內，車輛i未能收到ACK控制包，那么整個過程重新開始。

    然而，UMB方案并非是免碰撞的協議。當一個segment內有多個車輛時，它們可能會同時傳輸CTB，這就會引用碰撞。

1.1.2 智能廣播SB^[7]

    由上述分析可知，UMB方案中下一跳的轉發車輛需要等待很長的時間才能轉發數據包。為此，文獻[18]提出智能廣播SB(Smart Broadcast)方案，通過為下一跳轉發車輛設定短的等待時間解決這個問題。

    SB方案的數據包轉發過程如下所示。當車輛(仍假定車輛i)需要發送數據包，首先車輛i傳輸RTB，其包含位置、傳輸方向和競爭窗口尺寸(Contention window size)等信息。位于車輛i傳輸范圍內的車輛將接收到RTB，它們從RTB提取車輛i的位置信息，并決定自己的“sector”。最后，它們再依據自己所屬的sector，選擇競爭時延。

    依據文獻[7]，UMB方案設定了N_S個sector。位于第r個sector內的車輛可從式(2)所示的時延集內隨機地選擇自己的競爭時延W_r：

其中r=1，2，…，N_S，并且r=1表示最遠的sector。c_ω是競爭時延的時長。如式(2)所示，位于最遠sector內的車輛(r=1)等待的時延最短。

    當等待時延計時完畢，車輛(仍假定車輛j)就向車輛i傳輸CTB包。若成功接收了CTB包，車輛i就傳輸數據包DATA。

    文獻[7]對SB和UMB方案的性能進行了對比分析。結果表明SB方案在數據包傳輸率方面優于UMB方案，主要原因在于：UMB方案的數據包碰撞率隨著車輛密度的增加而提升。而SB方案的數據包傳輸率趨于一常數，不隨車輛密度變化而波動。

1.1.3 有效定向廣播EDB^[8]

    文獻[8]提出了基于時延的多跳廣播協議，其工作流程與UMB和SB方案類似。然而，EDB(Efficient Directional Broadcast)方案未引用RTB和CTB控制數據包。此外，EDB方案引用了定向天線，每個車輛裝有兩個定向天線，波束寬度為30度。

    與UMB方案類似，EDM方案依據車輛所處的位置不同，定義兩類數據包：道路上數據包和十字路口數據包。位于道路上的車輛，若它(假定車輛i)需要傳輸數據包，車輛i直接傳輸數據包，其后面的車輛跟著轉發。為了減少冗余重傳數據包，車輛在轉發數據包之前設定不同的延時等待。延時的時長是關于離源車輛(車輛i)的距離函數，如式(3)所示。

其中R表示傳輸范圍、d表示車輛離源車輛i的距離。max_WT表示最長的等待時間。

    如式(3)可知，離源車輛i越遠的車輛具有越高的轉發權。一旦延時等待完畢，車輛就立即傳輸ACK確定包。其他車輛監聽到ACK包，表明有車輛具有比自己更高的轉發權，自己就放棄這次競爭轉發權任務。當源車輛i收到ACK，車輛i就傳輸數據包DATA。此外，為了提高可靠性，如果在max_WT內沒有車輛轉發數據包，車輛將周期地廣播數據包。

1.1.4 Slotted 1-Persistence Broadcasting^[9]

    文獻[9]提出Slotted 1-Persistence廣播方案，其類似于其他的基于時延多跳廣播方案。離源車輛i越遠的車輛，具有越高的數據包轉發權。當接收到數據包，車輛就依據給定的時隙(Time slot)轉發數據包。時隙是關于車輛離源車輛的距離函數。假定車輛給定的時隙：

其中D_ij表示車輛j離源車輛i的距離、R為傳輸范圍、N_S表示預定的時隙數。

    與Slotted 1-Persistence廣播方案類似，文獻[13]提出基于車輛密度的緊急廣播VDEB(Vehicle-density-based Emergency Broadcasting)方案。VDEB方案也采用等待時隙，其是關于距離的函數。與Slotted 1-Persistence不同的是，VDEB方案考慮了車輛密度信息，并依據該信息決定合適的時隙數。

1.1.5 分發安全消息的可靠RMDSI方案

    文獻[10]針對網絡不連接問題，提出RMDSI(Reliable Method for Disseminating safety information)方案，從而提高通信的可靠性。RMDSI方案利用延時給每個車輛配置不同的轉發數據包的優先權。與EDB類似，當接收到了數據包，車輛就依據式(3)計算等待時延，當時延計時完畢，就轉發數據包。在等待過程中，車輛一直監聽信道，一旦發現其他車輛已轉發了數據包，就取消自己轉發數據包的任務。

    RMDSI方案的另一個特性就是引用了解決網絡斷裂的機制。每個轉發車輛都保存它已轉發數據包的副本，直到它監聽到來自下一跳轉發節點發送的副本(Duplicate)或者數據包的有效期已過。如果沒有監聽到來自下一跳轉發節點發送的副本，則表明網絡可能斷裂。在這種情況下，轉發車輛就繼續重播，直到它監聽到來自下一跳轉發節點發送的副本。通過這種機制應對網絡斷裂，提高數據包傳輸成功率。

1.1.6 多跳車輛廣播MHVB

    文獻[11]提出多跳車輛廣播MHVB(Multi-Hop Vehicular Broadcast)方案。與其他基于時延廣播方案一樣，MHVB方案引用了轉發數據包進行時延等待機制，時延的時長是關于距離函數。然而，不足的是：文獻[11]中并沒有給出計算時延時長的具體函數。

    與其他基于時延廣播方案不同，MHVB方案采用了交通擁擠檢測機制。交通擁擠，意味著車輛密度高，在這種環境下，每個車輛廣播自己消息的間隔應增大?；谶@個原理，MHVB方案利用鄰居數和行駛速度信息對交通擁擠進行檢測。當車輛發現自己的鄰居數大于門限值X，并且自己的行駛速度低于門限值V_max，表明交通擁擠，在這種情況下，車輛將增加廣播間隔。

1.1.7 RBLSM

    文獻[12]提出RBLSM(Reliable Broadcasting of life safety messages)方案。RBLSM方案也采用時延等待機制：車輛在轉發數據包之前，進行時延等待，直到時延計時完畢，才轉發數據包。與其他時延等待方案不同的在于：RBLSM方案不再將離源車輛遠的車輛給予最高的轉發數據包權，反而，就離源車輛最近的車輛，給予最高的轉發權。此外，RBLSM方案也采用了RTB、CTB控制包。

    與RBLSM方案類似，文獻[14]提出基于鏈路的分布式多跳廣播LDMB(Link-based Distributed Multi-hop Broadcast)方案。與RBLSM方案不同，LDMB方案中車輛在計算等待時延時，不僅考慮離源車輛的距離，還融入了交通密度、傳輸范圍以及數據包傳輸率。

1.2 基于概率的多跳廣播

    所謂基于概率的多跳廣播就是指每個車輛設定轉發數據包的概率，如文獻[15-17]。由于不是所有的車輛都能夠轉發數據包，冗余數據包的數量和數據包碰撞率得到有效的下降?；诟怕实亩嗵鴱V播方案最關鍵的因素在于如何設置數據包轉發概率。接下來，分析一些典型的基于概率的多跳廣播方案。

1.2.1 Weighted p-Persistence

    文獻[9]采用Weighted p-Persistence策略計算數據包轉發概率。車輛在轉發數據包之前，先依據離源車輛的距離計算轉發概率：

其中D_ij表示車輛j離源車輛i的距離、R為傳輸范圍。依據式(6)可知，離源車輛越遠，具有轉發數據包優先權的概率越大。然而，這個概率函數并沒有考慮車輛密度信息，因此，如果網絡密集，轉發的數據包數量仍然很大。此外，文獻[32]提出與Weighted p-Persistence類似的方案，轉發概率正比于離源車輛的距離。

1.2.2 優化的自適應概率廣播OAPB

    文獻[15]提出了優化的自適應概率廣播OAPB(Optimized Adaptive Probabilistic Broadcast)方案。OAPB方案依據局部的車輛密度計算數據包轉發概率。每個車輛通過交互HELLO數據包，計算自己的局部車輛密度信息。假定車輛j收到數據包，其轉發數據包的概率φ_j：

其中，N₁、N₂和N₃分別表示車輛j的一跳鄰居數、二跳鄰居數和三跳鄰居數。

    此外，為了進一步減少被轉發的數據包數量，具有相同轉發概率φ的車輛設定不同的時延：

    仿真結果表明OAPB方案在廣播開銷和數據包傳輸率方面優于DB(Deterministic Broadcast)。原因在于OAPB能夠依據網絡特性自適應地調整轉發概率。

1.2.3 AutoCast

    文獻[16]采用了AutoCast廣播方案，依據車輛一跳鄰居數計算轉發概率p：

其中N_h表示一跳鄰居數。從式(9)可知，轉發概率隨著一跳鄰居數的增加而下降。然而，顯然，AutoCast廣播方案能夠正常工作是以N_h大于或等于5為前提的。但是，文獻[16]并沒有描述在N_h小于5時，AutoCast廣播如何計算轉發概率。

    此外，為了提高覆蓋率和可靠性，AutoCast廣播方案采用了周期性重播機制。重播間隔t：

    與MILE和按需MILE相比，AutoCast廣播方案的性能有顯著提高。MILE方案只是一個簡單的周期廣播協議，節點周期性轉發接收到的數據包。而按需MILE方案是基于MILE的優化版，降低轉發的數據包數量。仿真結果證實了AutoCast廣播方案在數據包傳輸率和傳輸速度方面均優于MILE和按需MILE方案。原因在于AutoCast方案考慮了車輛密度信息計算轉發概率，這有助于降低數據包碰撞概率和增加數據包傳輸率。

1.2.4 不可靠轉發IF

    文獻[17]提出了不可靠轉發IF(Irresponsible Forwarding)方案。IF方案依據離源車輛距離和車輛密度信息計算轉發概率p，如式(11)所示。

其中ρ_s表示車輛密度、z表示傳輸范圍、d為車輛離源車輛的距離。c為形狀參數shaping parameter，且c≥1。注意到式(11)，其不同于傳統的轉發概率函數。傳統的轉發概率函數是關于距離的線性函數。從式(11)可知，轉發概率p隨著距離d的增加而提高，隨著網絡密度ρ_s的增加而下降。

    文獻[17]進一步分析證實：可通過形狀參數c控制轉發的數據包的數量。此外，IF方案維持轉發數據包的數量趨于常數，即使是在車輛密集區域，這點說明，IF方案具有可擴展性。

1.3 基于網絡編碼的多跳廣播

    網絡編碼是一種新穎消息分發方式，其能夠有效地提高網絡吞吐量^[18]。如圖2所示?？紤]一個簡單的場景(如圖2(a))，節點C位于節點A、B之間，并且節點A、B不能直接相連接。假定A需要向節點B傳輸一個數據包，同樣，節點B也需要向節點A傳輸一個數據包。由于節點A、B不能直接相連接，它們只能借助于節點C轉發。具體而言，節點A先將數據包轉發給C，然后C再轉發給B。類似地，節點B將數據包轉發C，然后由C轉發給A。顯然，這種簡單的方式，發生四次數據包轉發。

    若采用網絡編碼，如圖2(b)所示，首先，節點A向C發送數據包，然后，節點B也向C發送數據包。接下來，節點C利用異或XOR操作，對接收到的兩個數據進行編碼，編碼后，再廣播。最后，節點A、B接收到編碼后的數據包，再進行XOR操作就能夠得到自己所需的數據包，這個過程只需要三次數據包轉發。

    上述分析可知，通過網絡編碼分發消息能夠有效地降低數據包轉發的次數，提高了寬帶利用率。接下來，分析典型的基于網絡編碼的廣播方案。

1.3.1 COPE

    文獻[19]采用了基于網絡編碼的協議COPE。在實施過程中，COPE主要分為三步：(1)機會監聽(Opportunistic listening)；(2)機會編碼(Opportunistic listening)；(3)鄰居學習(Neighbor state learning)。機會監聽充分利用無線廣播媒介探聽的優勢，每個節點將自己監聽到的數據包存于自己緩沖區，但僅存一段時間。當機會來臨時，將這些數據包進行編碼。機會編碼就是指節點利用一些規則對數據進行編碼，然后再向外傳輸，但是，需要保證接收節點能夠正確地對已編碼的數據包進行解碼。鄰居學習就是接收哪個鄰居節點所發送的數據包。為此，每個節點周期地向鄰居節點廣播自己緩存區域內的數據包。

1.3.2 CODEB

    文獻[20]提出CODEB方案，其將COPE擴展到自組織網絡。與COPE類似，CODEB方案引用機會監聽。此外，每個節點周期地廣播自己的一跳鄰居清單。這樣，每個節點能夠構成兩跳的鄰居清單，從而形成廣播主線。

    基于概率廣播方案中，利用概率選擇下一跳轉發節點。與基于概率廣播方案不同，CODEB方案從鄰居節點中選擇一些節點構成子集，該子集內的節點轉發數據包。每個節點利用PDP(Partial Dominant Pruning)算法構建自己的子集。

    仿真結果表明CODEB方案在數據包傳輸率、數據包傳輸次數方面的性能優于僅采用PDP算法未利用網絡編碼的方案。原因在于網絡編碼能夠減少數據包傳輸的次數。

1.3.3 EBCD方案

    文獻[21]提出基于EBCD(Efficient Broadcasting Using Network Coding and Directional Antennas)方案。EBCD方案結合了網絡編碼和定向天線的優勢。與CODEB方案類似，EBCD方案利用DDCDS(Dynamic Directional Connected Dominating Set)算法構建轉發節點集。與CODEB不同之處在于：EBCD方案中網絡編碼應用到定向天線的每個sector區域。仿真結果證實EBCD方案能夠有效地降低數據包傳輸次數。

1.3.4 DifCODE

    文獻[22]提出DifCODE方案。與CODEB方案類似，DifCODE方案利用多點轉發MPR(Multi-point relay)算法計算數據包轉發節點集。與CODEB方案不同之處在于機會編碼策略。在CODEB方案中，源車輛的所有鄰居車輛都需要能夠立即解碼所接收到的數據包。這限制了編碼機會。而DifCODE方案釋放了這個限制性，允許節點緩存那些不能立即解碼的數據包。仿真結果表明，與基于概率方案相比，DifCODE方案具有低的冗余率。

2 性能指標

    目前，研究人員采用眾多的方法評估多跳廣播方案的性能指標。為此，依據每個性能指標的特性，所有性能指標分為三類：頻率、空間、時間，如表1所示。頻率類的性能指標主要涉及到計數，如數據包的數量和車輛數量。空間類的性能指標主要涉及到距離的測量，而時間類的性能指標是關于時間的測量。

    表1的第2列給每個性能指標進行編號。表1的第3列列舉每個性能指標，從表1可知，有些性能指標是非常類似的。第4列描述了計算每個性能指標公式，第5列描述了性能指標的單位，第6列表示該性能指標的使用頻率。

3 多跳廣播方案的性能比較

    第1節已分析了各類典型的多跳廣播方案的特性，為了更充分地分析各方案的特點，表2還從評估模型、仿真平臺以及使用的性能進行總結。

4 總結與展望

    針對VANET網絡內的消息分發方案進行了分析和總結。依據特性的不同，將現有方案分為三類：基于時延、基于概率和基于網絡編碼的多跳廣播方案。隨后，總結了評估多跳廣播方案的性能指標。

    盡管研究人員提出眾多的多跳廣播方案，但仍存在需要亟待解決問題。

    (1)理論性能分析的缺失

    從表2可知，目前僅少數多跳廣播方案進行理論性能分析，多數方案僅采用仿真。因此，通用于分析多跳廣播方案的基礎理論模型值得研究。理論模型首先應該包含車輛移動模型，這直接影響到網絡拓撲和網絡連接。其次，應該能夠包含數據包轉發模型。

    (2)真實場景測試的缺失

    現有多數廣播方案均是采用簡單直線道路場景進行測試。然而，分發交通信息的多數場景是發生于城市交通，而城市交通的道路結構是非常復雜，不再是簡單的直線道路場景。因此，廣播方案應該需要在一個復雜的，逼近真實城市交通場景中進行測試。

參考文獻

[1] 于海寧，張宏莉.VANETs路由協議的研究進展[J].電子學報，2011，39(12)：2868-2880.

[2] ABBOUD K，ZHUANG W.Analysis of communication link lifetime using stochastic microscopic vehicular mobility model[C]//IEEE Globecom，Atlanta，GA，USA，Dec.2013：405-410.

[3] CHENG H T，SHAN H，ZHUANG W.Infotainment and road safety service support in vehicular networking: From a communication perspective[J].Mech.Syst.Signal Process.，2011，25(6)：2020-2038.

[4] ALASMARY W，ZHUANG W.Mobility impact in IEEE802.11p infrastructureless vehicular networks[J].Ad Hoc Netw.，2012，10(2)：222-230.

[5] 李元振，廖建新，李彤紅，等．城市場景車載Ad Hoc網絡競爭轉發關鍵參數分析[J]．電子學報，2011，38(5)：1154-l158．

6-22略