0 引言

    隨著專用短程通信DSRC(Dedicated Short-Range Communications)標準的成熟，車載網VANETs(Vehicle Ad hoc Networks)成為研究的焦點。VANETs網絡通過車間通信V2V(Vehicle-to-Vehicle)實現消息的傳遞。車輛間傳遞的消息分為兩類：緊急消息(Emergency Message)和非緊急消息。當前方車輛發現交通事故、路面有障礙物等緊急情況，需向周圍車輛發布這一情況，即緊急消息，提醒周圍車輛采取必要的措施^[1-3]。

    由于緊急消息對時間相當敏感，必須快速、可靠地傳輸，否則就失去意義。目前，常采用廣播機制傳遞緊急消息，如城市多跳廣播^[3]，是一個有效傳遞緊急消息的方案。當出現緊急情況，源節點(第一個發現該緊急情況的車輛)向鄰居節點廣播消息，接收節點再重播，直到所有相關的節點均收到此消息。然而，這種簡單的廣播策略會引起信道擁擠，導致廣播風暴^[4]。又由于無線信道的不穩定性，消息傳輸成功率低。這些問題給緊急消息的有效傳輸提出挑戰。

    由于無線信道的廣播特性，網絡編碼技術受到廣泛關注。Nguyen等^[5]分析了網絡編碼在單跳無線網絡的應用特性。隨后，Li等^[6]提出基于網絡編碼的廣播協議。在多跳網絡中，利用鄰居節點間的協作提高網絡傳輸性能，但是文獻[5-6]并沒有考慮這點。此外，文獻[7]提出面向VANET的基于秩的網絡編碼算法，節點依據鄰居節點的競爭接收狀態，自適應地向網絡輸入數據包。文獻[8]也提出隨機編碼方案。然而，這些基于網絡編碼方案并不是針對多跳廣播應用，它們均沒有考慮節點間的協作性。

    為此，針對VANETs多跳廣播，提出基于網絡編碼的轉發節點協作廣播協議NCFMB(Network Coding-based cooperative Forwarding Multi-hop Broadcasting protocol)。首先，源節點利用節點距離、方向以及局部密度信息，選擇下一跳轉發節點，然后，將要傳輸的數據包進行線性編碼。網絡編碼以2個數據包為一批。因此，源節點需選擇兩個轉發節點。通過網絡編碼和轉發節點間的協作，提高數據包傳輸成功率，并降低了數據包傳輸時延。

1 預備知識

    線性網絡編碼就是在數據發送前對其進行線性變換^[9]。由于無線通信的廣播特性，可利用網絡編碼技術降低數據包被傳輸的次數，減少系統開銷。

    假定發送節點有m個原始數據包（未編碼），需要發送至多個接收節點。假定X=(x₁，x₂，…，x_m)^T表示這m個原始數據包。發送節點利用Y=CX對數據包進行編碼：

其中C表示編碼矢量。當接收了m個或以上的線性編碼數據包時，接收節點就能夠恢復原始數據包。此外，可通過伽羅瓦域GF（Galois Field）選擇編碼矢量C。如果該域足夠大，可隨機選擇m個獨立的組合。

2 NCFMB協議

2.1 轉發節點的選擇

    為了縮短傳輸時延和縮短傳輸跳數，引用貪婪地理思想，將離發送節點的距離作為選擇下一跳轉發節點的指標之一。假定節點i為源節點，節點j為其鄰居節點，那么節點i與節點j的距離因子

其中θ_j表示節點i與節點j的連線與水平方向上的夾角，如圖1所示。

    依據角度計算公式，可得θ_j值：

    其中d表示節點j離水平線的距離。

    最終，將距離因子、方向因子以及密度因子融合在一個變量，稱為競爭權值CW。節點j的競爭權值CW(j)：

其中α、β、γ分別為距離因子、方向因子、密度因子的權值系數，其取決于不同的環境。

    源節點計算了所有鄰居節點的競爭權值后，比較鄰居節點的競爭相對值，并選擇兩個具有最大競爭權值的節點作為消息的轉發節點。  

2.2 編碼矢量

    NCFMB協議選擇的編碼矢量C：

    由于第一輪產生的只有兩個數據包，只需從編碼矢量C中選擇任何兩個元素對數據包進行編碼。使用這些編碼矢量的優勢在于：可將任何已編碼的數據包轉換成其他兩個編碼數據包。例如，從(y₁，y₂)可得(y₃，y₄)。通過鄰居節點間的協作，這個優勢可極大地提高數據包傳輸率，原因在于：每個節點只需接收任意兩個編碼數據包就能解碼，進而獲取原始數據包。此外，所有的節點共享相同的編碼矢量C。

2.3 編碼規則

    源節點首先依據2.1節的轉發節點選擇算法產生兩個轉發節點，然后將兩個原始數據包a、b進行編碼，得到兩個編碼數據包，再廣播。一旦鄰居節點接收這兩個編碼包，就可解碼，得到原始包。若只成功接收了一個編碼包，則廣播自己所接收的數據包。

    如圖2所示，源節點S首先對原始數據包(a，b)進行編碼，得到線性編碼組合(a+a，a+2b)。然后，從鄰居節點中選擇兩個轉發節點r1和R1。假定由于信道原因，節點r1僅接收了a+b，而R1僅接收了a+2b。在這種情況下，節點r1和R1重播自己接收的數據包，那么，節點r1和R1就能夠從對方接收到一個編碼數據包，最終能夠解碼，得到原始數據包。

2.4 重傳機制

    盡管利用網絡編碼技術能夠提高下一跳的數據包接收率，但是由于無線鏈路的不穩定性以及數據包碰撞等原因，仍會丟失一些數據包。為了提高數據包接收率，NCFMB協議規定：當源節點在規定的時限內沒有檢測到其廣播的數據包被轉發，就重播之前的數據包。預設的時限T=40 ms。這不同于其他的重播機制，傳統的重播算法只重播丟失的數據包，而NCFMB協議重播新的編碼包。如圖3所示，源節點S第一次轉播了兩個編碼包a+b、a+2b。若編碼包a+2b丟失，源節點S就重播新的編碼包2a+3b，其不同于a+b、a+2b。假定節點r1只接收了編碼包a+b，未能接收到a+2b。由于源節點S重播新的編碼包2a+3b，節點r1可利用a+b和2a+3b兩個編碼包解碼，獲取原始包。因此，在重播之前，對數據包進行編碼，NCFMB協議比傳統的重播協議降低了傳輸次數，也提高了數據包接收率。

3 系統仿真以及性能分析

3.1 仿真參數

    采用微觀的交通仿真軟件SUMO^[10]和TraNS^[11]兩個仿真軟件產生街道場景。在仿真過程中，車輛最大行駛速度為20 m/s。每個街道場景區域為1 700 m×1 700 m，且由5條水平車道和5垂直車道組成。兩個相鄰十字路口間距為400 m。

    在仿真過程中，有兩個源節點，且為相鄰節點，它們每秒產生15個數據包。仿真目的在于：考查兩個鄰居節點同時發送數據包的環境下的路由性能。每次實驗獨立重復100次，取平均值作為最終的實驗數據。此外，本文假定距離因子與密度因子具有同等的權重系數，而方向因子的權重較小，即α、β、γ分別為0.4 、0.2、 0.4。具體的仿真參數如表1所示。

    同時選擇FUZZBR^[12]和Un-RE-FUZZBR協議，與NCFMB進行同步仿真，并進行性能比較。與其他協議相比，如Weighted p-persistence^[13]和MPR broadcast^[14]以及Flooding相比，FUZZBR協議具有好的性能。在FUZZBR中，當轉發節點轉發的數據包在預定的時間內未被檢測到，發送節點就重傳此數據包，且限定了數據包被重傳的上限。而Un-RE-FUZZBR協議是無重傳，當數據包被丟失后，發送節點不再重傳。

3.2 仿真數值分析

3.2.1 重傳次數

    圖4顯示了每個數據包被重傳次數。從圖可知，FUZZBR協議的重傳次數隨著源節點數的增加而增加，原因在于：源節點增加，信道中傳輸的數據包也隨之增加，加大了數據包碰撞的概率，使得多個數據包被重傳。而Un-RE-FUZZBR協議和NCFMB協議具有較低的重傳次數。Un-RE-FUZZBR協議沒有重傳機制，即使數據包丟失了，也不進行重傳，即以數據包丟失率換取低的重傳次數。而提出的NCFMB協議利用網絡編碼技術，降低了重傳次數，減少了系統開銷。

3.2.2 數據包傳輸成功率

    圖5顯示了3個算法的數據包傳輸成功率。從圖5可知，提出的NCFMB協議具有高的傳輸成功率，遠高于FUZZBR協議。這主要是因為NCFMB協議的重傳次數遠低于FUZZBR協議，極大地降低了數據包被碰撞的概率。而Un-RE-FUZZBR協議的數據包傳輸率最低。原因在于它沒有重傳機制，即使數據包丟失也不重傳。結合圖4和圖5可知，NCFMB協議與Un-RE-FUZZBR協議的重傳次數相近，但是傳輸成功率相差甚大，進一步網絡編碼能夠有效地提高傳輸成功率。

3.2.3 端到端傳輸時延

    3個協議的端到端傳輸時延如圖6所示。從圖可知，隨著源節點數的增加，3個協議的傳輸時延也隨之增加，這主要是因為源節點數增加，意味著有更多的數據包需要傳輸，這必然加大了數據包碰撞的概率，從而提高了傳輸時延。正如預料，FUZZBR協議的傳輸時延最高，它只采用了簡單的重傳機制，一旦數據包丟失就重傳，肯定加大了傳輸時延。而Un-RE-FUZZBR協議的傳輸時延最低，但是它的數據包傳輸成功也是最低了。提出的NCFMB協議利用網絡編碼技術以及轉發節點間的協作，在保證較高的數據包傳輸成功率時，傳輸時延也得到極好的限制。

4 總結

    本文針對車載網的多跳廣播協議的數據包傳輸率低的問題，提出基于網絡編碼的轉發節點協作的多跳廣播NCFMB協議。NCFMB協議充分利用網絡編碼特性，提高降低數據包重傳次數。首先，依據節點的距離、移動方向以及局部密度信息，選擇轉發節點。然后，再利用線性編碼，將需轉發的數據進行編碼。仿真數據驗證表明，提出的NCFMB協議能夠有效地降低傳輸時延，提高了數據包傳輸成功率。

參考文獻

[1] KENNEY J B.Dedicated short-range communications(DSRC) standards in the United States[J].Proceedings of the IEEE，2011，99(7)：1162-1182.

[2] RAZVAN C，HAMZA A，HUANG F.Fast and reliable broadcasting in VANETs using SNR with ACK decoupling[C].IEEE ICC 2014-Ad-hoc and Sensor Networking Symposium，2014：574-579.

[3] KESTING A，TREIBER M，HELBING D.Connectivity statistics of storeand-forward intervehicle communication[J].IEEE Trans.Intell.Transp.Syst.，2010，11(1)：172-181.

[4] WU C，SATOSHI O.Joint fuzzy relays and network-coding-based forwarding for multihop broadcasting in VANETs[J].IEEE Transactions on Intelligent Transportations Systems，2015，16(3)：1415-1428.

[5] NGUYEN D，TRAN T，NGUYEN T，et al.Wireless broadcast using network coding[J].IEEE Trans.Veh.Technol.，2009，58(2)：914-925.

[6] LI L，RAMJEE R，BUDDHIKOT M，et al.Network coding-based broadcast in mobile ad hoc networks[C].in Proc. IEEE INFOCOM，2014：1739-1747.

[7] YU T X，YI C W，TSAO S L.Rank-based network coding for content distribution in vehicular networks[J].IEEE Wireless Commun.Lett.，2012，1(4)：368-371.

[8] LEE U，PARK J S，YEH J，et al.VANETCODE：Network coding to enhance cooperative downloading in vehicular ad-hoc networks[C].in Proc.IWCMC，2006：1-5.

[9] LI S，YEUNG R，CAI N.Linear network coding[J].IEEE Trans.Inf.Theory，2013，49(2)：371-381.

[10] KRAJZEWICZ D，HERTKORN G，ROSSEL C，et al.SUMO(Simulation of Urban MObility)：An open-source traffic simulation[C].In Proc.4th MESM，2012：183-187.

[11] TraNS(Traffic and Network Simulation Environment)，Accessed on Oct.15，2012.[Online].Available：http：//trans.epfl.ch/.

[12] WU C，OHZAHATA S，KATO T.VANET broadcast protocol based on fuzzy logic and lightweight retransmission mechanism[J].IEICE Trans.Commun.，2012(2)：415-425.

[13] WISITPONGPHAN N，TONGUZ K O.Broadcast storm mitigation techniques in vehicular ad hoc networks[J].IEEE Wireless Commun.，2007，14(6)：84-94.

[14] WU C，KUMEKAWA K，KATO T.A novel multi-hop broadcast protocol for vehicular safety applications[J].J.Inf.Process.，2010(18)：110-124.