0 引言

    隨著專用短程通信DSRC(Dedicated Short-Range Communications)標(biāo)準(zhǔn)的成熟,，車載網(wǎng)VANETs(Vehicle Ad hoc Networks)成為研究的焦點(diǎn)。VANETs網(wǎng)絡(luò)通過(guò)車間通信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)均收到此消息。然而,，這種簡(jiǎn)單的廣播策略會(huì)引起信道擁擠,，導(dǎo)致廣播風(fēng)暴^[4]。又由于無(wú)線信道的不穩(wěn)定性,，消息傳輸成功率低,。這些問(wèn)題給緊急消息的有效傳輸提出挑戰(zhàn)。

    由于無(wú)線信道的廣播特性,，網(wǎng)絡(luò)編碼技術(shù)受到廣泛關(guān)注,。Nguyen等^[5]分析了網(wǎng)絡(luò)編碼在單跳無(wú)線網(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)的競(jìng)爭(zhēng)接收狀態(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),。通過(guò)網(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ú)線通信的廣播特性，可利用網(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ù)包,。此外，可通過(guò)伽羅瓦域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è)變量，稱為競(jìng)爭(zhēng)權(quán)值CW,。節(jié)點(diǎn)j的競(jìng)爭(zhēng)權(quán)值CW(j)：

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

    源節(jié)點(diǎn)計(jì)算了所有鄰居節(jié)點(diǎn)的競(jìng)爭(zhēng)權(quán)值后,，比較鄰居節(jié)點(diǎn)的競(jìng)爭(zhēng)相對(duì)值,，并選擇兩個(gè)具有最大競(jìng)爭(zhēng)權(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₄),。通過(guò)鄰居節(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ù)包,，再?gòu)V播。一旦鄰居節(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ú)線鏈路的不穩(wěn)定性以及數(shù)據(jù)包碰撞等原因,，仍會(huì)丟失一些數(shù)據(jù)包。為了提高數(shù)據(jù)包接收率,，NCFMB協(xié)議規(guī)定：當(dāng)源節(jié)點(diǎn)在規(guī)定的時(shí)限內(nèi)沒有檢測(cè)到其廣播的數(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)生街道場(chǎng)景,。在仿真過(guò)程中,，車輛最大行駛速度為20 m/s。每個(gè)街道場(chǎng)景區(qū)域?yàn)? 700 m×1 700 m,，且由5條水平車道和5垂直車道組成,。兩個(gè)相鄰十字路口間距為400 m。

    在仿真過(guò)程中,，有兩個(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)未被檢測(cè)到,，發(fā)送節(jié)點(diǎn)就重傳此數(shù)據(jù)包，且限定了數(shù)據(jù)包被重傳的上限,。而Un-RE-FUZZBR協(xié)議是無(wú)重傳,，當(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í)延最高，它只采用了簡(jiǎn)單的重傳機(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èn)題，提出基于網(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.