0 引言

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

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

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

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

1 預(yù)備知識(shí)

    線性網(wǎng)絡(luò)編碼就是在數(shù)據(jù)發(fā)送前對(duì)其進(jìn)行線性變換^[9]。由于無線通信的廣播特性，可利用網(wǎng)絡(luò)編碼技術(shù)降低數(shù)據(jù)包被傳輸?shù)拇螖?shù)，減少系統(tǒng)開銷。

    假定發(fā)送節(jié)點(diǎn)有m個(gè)原始數(shù)據(jù)包（未編碼），需要發(fā)送至多個(gè)接收節(jié)點(diǎn)。假定X=(x₁，x₂，…，x_m)^T表示這m個(gè)原始數(shù)據(jù)包。發(fā)送節(jié)點(diǎn)利用Y=CX對(duì)數(shù)據(jù)包進(jìn)行編碼：

其中C表示編碼矢量。當(dāng)接收了m個(gè)或以上的線性編碼數(shù)據(jù)包時(shí)，接收節(jié)點(diǎn)就能夠恢復(fù)原始數(shù)據(jù)包。此外，可通過伽羅瓦域GF（Galois Field）選擇編碼矢量C。如果該域足夠大，可隨機(jī)選擇m個(gè)獨(dú)立的組合。

2 NCFMB協(xié)議

2.1 轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇

    為了縮短傳輸時(shí)延和縮短傳輸跳數(shù)，引用貪婪地理思想，將離發(fā)送節(jié)點(diǎn)的距離作為選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)的指標(biāo)之一。假定節(jié)點(diǎn)i為源節(jié)點(diǎn)，節(jié)點(diǎn)j為其鄰居節(jié)點(diǎn)，那么節(jié)點(diǎn)i與節(jié)點(diǎn)j的距離因子

其中θ_j表示節(jié)點(diǎn)i與節(jié)點(diǎn)j的連線與水平方向上的夾角，如圖1所示。

    依據(jù)角度計(jì)算公式，可得θ_j值：

    其中d表示節(jié)點(diǎn)j離水平線的距離。

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

其中α、β、γ分別為距離因子、方向因子、密度因子的權(quán)值系數(shù)，其取決于不同的環(huán)境。

    源節(jié)點(diǎn)計(jì)算了所有鄰居節(jié)點(diǎn)的競爭權(quán)值后，比較鄰居節(jié)點(diǎn)的競爭相對(duì)值，并選擇兩個(gè)具有最大競爭權(quán)值的節(jié)點(diǎn)作為消息的轉(zhuǎn)發(fā)節(jié)點(diǎn)。  

2.2 編碼矢量

    NCFMB協(xié)議選擇的編碼矢量C：

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

2.3 編碼規(guī)則

    源節(jié)點(diǎn)首先依據(jù)2.1節(jié)的轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇算法產(chǎn)生兩個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)，然后將兩個(gè)原始數(shù)據(jù)包a、b進(jìn)行編碼，得到兩個(gè)編碼數(shù)據(jù)包，再廣播。一旦鄰居節(jié)點(diǎn)接收這兩個(gè)編碼包，就可解碼，得到原始包。若只成功接收了一個(gè)編碼包，則廣播自己所接收的數(shù)據(jù)包。

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

2.4 重傳機(jī)制

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

3 系統(tǒng)仿真以及性能分析

3.1 仿真參數(shù)

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

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

    同時(shí)選擇FUZZBR^[12]和Un-RE-FUZZBR協(xié)議，與NCFMB進(jìn)行同步仿真，并進(jìn)行性能比較。與其他協(xié)議相比，如Weighted p-persistence^[13]和MPR broadcast^[14]以及Flooding相比，F(xiàn)UZZBR協(xié)議具有好的性能。在FUZZBR中，當(dāng)轉(zhuǎn)發(fā)節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)包在預(yù)定的時(shí)間內(nèi)未被檢測到，發(fā)送節(jié)點(diǎn)就重傳此數(shù)據(jù)包，且限定了數(shù)據(jù)包被重傳的上限。而Un-RE-FUZZBR協(xié)議是無重傳，當(dāng)數(shù)據(jù)包被丟失后，發(fā)送節(jié)點(diǎn)不再重傳。

3.2 仿真數(shù)值分析

3.2.1 重傳次數(shù)

    圖4顯示了每個(gè)數(shù)據(jù)包被重傳次數(shù)。從圖可知，F(xiàn)UZZBR協(xié)議的重傳次數(shù)隨著源節(jié)點(diǎn)數(shù)的增加而增加，原因在于：源節(jié)點(diǎn)增加，信道中傳輸?shù)臄?shù)據(jù)包也隨之增加，加大了數(shù)據(jù)包碰撞的概率，使得多個(gè)數(shù)據(jù)包被重傳。而Un-RE-FUZZBR協(xié)議和NCFMB協(xié)議具有較低的重傳次數(shù)。Un-RE-FUZZBR協(xié)議沒有重傳機(jī)制，即使數(shù)據(jù)包丟失了，也不進(jìn)行重傳，即以數(shù)據(jù)包丟失率換取低的重傳次數(shù)。而提出的NCFMB協(xié)議利用網(wǎng)絡(luò)編碼技術(shù)，降低了重傳次數(shù)，減少了系統(tǒng)開銷。

3.2.2 數(shù)據(jù)包傳輸成功率

    圖5顯示了3個(gè)算法的數(shù)據(jù)包傳輸成功率。從圖5可知，提出的NCFMB協(xié)議具有高的傳輸成功率，遠(yuǎn)高于FUZZBR協(xié)議。這主要是因?yàn)镹CFMB協(xié)議的重傳次數(shù)遠(yuǎn)低于FUZZBR協(xié)議，極大地降低了數(shù)據(jù)包被碰撞的概率。而Un-RE-FUZZBR協(xié)議的數(shù)據(jù)包傳輸率最低。原因在于它沒有重傳機(jī)制，即使數(shù)據(jù)包丟失也不重傳。結(jié)合圖4和圖5可知，NCFMB協(xié)議與Un-RE-FUZZBR協(xié)議的重傳次數(shù)相近，但是傳輸成功率相差甚大，進(jìn)一步網(wǎng)絡(luò)編碼能夠有效地提高傳輸成功率。

3.2.3 端到端傳輸時(shí)延

    3個(gè)協(xié)議的端到端傳輸時(shí)延如圖6所示。從圖可知，隨著源節(jié)點(diǎn)數(shù)的增加，3個(gè)協(xié)議的傳輸時(shí)延也隨之增加，這主要是因?yàn)樵垂?jié)點(diǎn)數(shù)增加，意味著有更多的數(shù)據(jù)包需要傳輸，這必然加大了數(shù)據(jù)包碰撞的概率，從而提高了傳輸時(shí)延。正如預(yù)料，F(xiàn)UZZBR協(xié)議的傳輸時(shí)延最高，它只采用了簡單的重傳機(jī)制，一旦數(shù)據(jù)包丟失就重傳，肯定加大了傳輸時(shí)延。而Un-RE-FUZZBR協(xié)議的傳輸時(shí)延最低，但是它的數(shù)據(jù)包傳輸成功也是最低了。提出的NCFMB協(xié)議利用網(wǎng)絡(luò)編碼技術(shù)以及轉(zhuǎn)發(fā)節(jié)點(diǎn)間的協(xié)作，在保證較高的數(shù)據(jù)包傳輸成功率時(shí)，傳輸時(shí)延也得到極好的限制。

4 總結(jié)

    本文針對(duì)車載網(wǎng)的多跳廣播協(xié)議的數(shù)據(jù)包傳輸率低的問題，提出基于網(wǎng)絡(luò)編碼的轉(zhuǎn)發(fā)節(jié)點(diǎn)協(xié)作的多跳廣播NCFMB協(xié)議。NCFMB協(xié)議充分利用網(wǎng)絡(luò)編碼特性，提高降低數(shù)據(jù)包重傳次數(shù)。首先，依據(jù)節(jié)點(diǎn)的距離、移動(dòng)方向以及局部密度信息，選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)。然后，再利用線性編碼，將需轉(zhuǎn)發(fā)的數(shù)據(jù)進(jìn)行編碼。仿真數(shù)據(jù)驗(yàn)證表明，提出的NCFMB協(xié)議能夠有效地降低傳輸時(shí)延，提高了數(shù)據(jù)包傳輸成功率。

參考文獻(xiàn)

[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.