程晗晗，樊秀梅

(1. 天津科技大學(xué)計算機(jī)科學(xué)與信息工程學(xué)院，天津 300222；2. 北京理工大學(xué)計算機(jī)學(xué)院，北京 100081)

在車間通信(inter-vehicle communication，IVC)系統(tǒng)中，車輛間依靠廣播共享緊急事變、交通狀況、天氣和道路數(shù)據(jù)以及傳播廣告和通知．然而，車輛移動的高速度減少了可以進(jìn)行信息交換的時間，并引起快速和頻繁的拓?fù)渥兓瑢?dǎo)致無線信道的更加不穩(wěn)定．因此，能夠適應(yīng) VANET(vehicular Ad hoc network)基本特征、滿足駕乘人員需求的交通信息廣播協(xié)議需要具備以下條件[1]：支持節(jié)點的高速移動；保證信息分發(fā)的實時性、可靠性和可達(dá)性；具有較高的資源利用率；適應(yīng)無線網(wǎng)絡(luò)惡劣信道環(huán)境；具有較強(qiáng)的可擴(kuò)展性和魯棒性；為多種應(yīng)用信息提供資源公平共享機(jī)會．

MANET(mobile Ad hoc network)已開發(fā)出大量的單播路由協(xié)議．然而，這些協(xié)議有其獨特的特點，在VANET中不能被有效地利用．研究人員已經(jīng)針對VANET開發(fā)了單播路由協(xié)議[2–6]．這些協(xié)議中的大部分使用基于位置的貪婪方法來實現(xiàn)車與車之間的通信．基于位置的方法是利用節(jié)點的坐標(biāo)或與相對位置有關(guān)的信息，通過網(wǎng)絡(luò)來生成一個有效的路由[2–3]．在稀疏的車載網(wǎng)中，以路由數(shù)據(jù)包為目的協(xié)議被稱為延遲–容忍路由協(xié)議．在一些特定的網(wǎng)絡(luò)環(huán)境下，如星際網(wǎng)絡(luò)、軍事 Ad hoc網(wǎng)絡(luò)、傳感器網(wǎng)絡(luò)、車輛 Ad hoc網(wǎng)絡(luò)會經(jīng)常出現(xiàn)網(wǎng)絡(luò)斷開的現(xiàn)象，導(dǎo)致報文在傳輸過程中不能確保端到端的路徑，這類網(wǎng)絡(luò)被稱為容遲網(wǎng)絡(luò)或DTN．在這種情況下，建立端到端的路由也許是不可能的，因此文獻(xiàn)[6]和文獻(xiàn)[7]使用攜帶轉(zhuǎn)發(fā)的方法來實現(xiàn)節(jié)點間的重新愈合．

大多數(shù)車載自組網(wǎng)研究專注于高密度網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下廣播風(fēng)暴問題的協(xié)議算法，這些研究都是基于VANET網(wǎng)絡(luò)連接良好的情形下進(jìn)行的．文獻(xiàn)[8]根據(jù)加利福尼亞州 I-80高速公路上的車輛交通數(shù)據(jù)得出，在 100%的設(shè)備配備率下(即所有的車輛都配備了無線通信功能)，深夜公路上的網(wǎng)絡(luò)斷開概率達(dá)到35%；而在網(wǎng)絡(luò)連接良好的上下班高峰期，即使使用大的設(shè)備配備率，也可以觀察到網(wǎng)絡(luò)斷開現(xiàn)象．可見，網(wǎng)絡(luò)斷開問題是一個重要的研究內(nèi)容，因此需要開發(fā)一個可靠高效的路由協(xié)議，以支持高度多樣化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)．

針對車聯(lián)網(wǎng)中存在的網(wǎng)絡(luò)斷開問題，旨在縮短節(jié)點間的重新愈合時間，本文在已有攜帶轉(zhuǎn)發(fā)機(jī)制的基礎(chǔ)上，提出基于路邊設(shè)施(road side units，RSU)的廣播協(xié)議．

1 常用攜帶轉(zhuǎn)發(fā)機(jī)制

1.1 SCF(store-carry-forward)機(jī)制

SCF[9–10]機(jī)制利用反方向行駛的車輛作為轉(zhuǎn)發(fā)者將消息傳遞給下一簇(在相同方向上行駛并且只能以單跳或多跳的方式彼此通信的車輛屬于同一簇)內(nèi)的車輛，然而只能傳遞給下一簇內(nèi)的第 1輛車．當(dāng)DSRC(dedicated short-range communications)設(shè)備的普及率很低時斷開節(jié)點的數(shù)量就會增加，由反方向轉(zhuǎn)發(fā)者執(zhí)行的 SCF機(jī)制的操作數(shù)量增加，從而導(dǎo)致SCF開銷增大．

1.2 SCB(store-carry-broadcast)機(jī)制

為了減少 SCF開銷，當(dāng)一個轉(zhuǎn)發(fā)者能夠在連續(xù)的斷開節(jié)點間執(zhí)行多次 SCF操作時，就需要避免分派多個轉(zhuǎn)發(fā)者，因此提出 SCB[9]機(jī)制，S與隨后的節(jié)點 V1斷開，SCB操作為(圖 1)：S將消息發(fā)送給X(反向轉(zhuǎn)發(fā)者)→V1，…，Vk(2,R廣播范圍內(nèi)的節(jié)點)→X 檢查是否有鄰節(jié)點 X′距離 Vk+1較近，若存在 X′就成為新的轉(zhuǎn)發(fā)者；若不存在 X保持．Vk+1與Vk斷開，那么轉(zhuǎn)發(fā)者就會對從 Vk+1開始的下一簇廣播消息→當(dāng)轉(zhuǎn)發(fā)者發(fā)現(xiàn)廣播范圍外的第 1輛車與它前面的車輛保持連接，那么它就會丟掉此消息．

圖1 SCB機(jī)制示意圖Fig.1 Schema of SCB

以上 2種機(jī)制都無法保證簇尾車輛遇到反方向轉(zhuǎn)發(fā)者的等待時間，尤其是在 DSRC設(shè)備的普及率較低時就會有更長的時間延遲．

2 基于RSU的廣播協(xié)議模型

當(dāng)研究VANET中的數(shù)據(jù)包傳送問題時，需要區(qū)分開以下 2種情形：(1)向后方車輛廣播安全消息，即源車輛檢測到事故后產(chǎn)生1個警告信息，并將其傳播給后方車輛，后方車輛在到達(dá)潛在危險區(qū)之前能夠得到此警告信息；(2)當(dāng)目標(biāo)節(jié)點離源車輛較遠(yuǎn)時，將消息發(fā)送到遠(yuǎn)方的特定節(jié)點，這時數(shù)據(jù)包到達(dá)目的地所需跳數(shù)取決于多種因素，如發(fā)送者與目的地之間的距離和傳遞數(shù)據(jù)包的路徑．

2.1 向后方車輛廣播安全消息及其重新愈合時間計算

對于向后方傳遞安全信息的情況，基于以下6個規(guī)則可以將固定設(shè)施RSU應(yīng)用于廣播協(xié)議模型：

(1)當(dāng)源車輛V0檢測到危險或事故，它向簇內(nèi)的下一鄰節(jié)點廣播安全消息，鄰節(jié)點可能是部署在公路上的RSU或者與V0同方向行駛的后方車輛(V0方向作為目的地方向)．

(2)如果RSU接收到安全信息，將定期向行駛而來的車輛廣播安全消息．通過 RSU廣播安全消息，可以減少大量廣播負(fù)載量．

(3)當(dāng)消息不再是必要的，RSU將丟棄消息，停止廣播，放棄安全警告．

(4)如果 V0的簇內(nèi)未部署 RSU，車輛 Vk(即 V0簇的尾車輛)將承擔(dān)指定消息傳遞轉(zhuǎn)發(fā)者的責(zé)任．

(5)行駛在與 Vk相反方向中的相鄰車輛被選擇為轉(zhuǎn)發(fā)器．

(6)轉(zhuǎn)發(fā)器接收了安全信息后將攜帶消息，然后傳遞到一個重新愈合節(jié)點(RSU或斷開車輛 Vk+1)．通過此規(guī)則可以減少重新愈合的跳數(shù)，這對于減少VANET中車輛密度較高區(qū)域的廣播分支是非常重要的．

事故發(fā)生后，源車輛生成并向后方車輛傳遞安全信息，根據(jù)車輛與 RSU的位置，可以分為路邊設(shè)備在源車輛簇的傳輸范圍內(nèi)和不在其傳輸范圍內(nèi) 2種情況進(jìn)行討論．

2.1.1 路邊設(shè)備在源車輛簇的傳輸范圍內(nèi)

因為 RSU(U1)在源車輛簇的傳輸范圍內(nèi)，所以當(dāng)交通安全消息由源車輛 V0發(fā)出后，該消息可以通過簇內(nèi)的節(jié)點傳遞到U1，如圖2所示．需要注意的是車輛Vn不需要是簇內(nèi)最后一輛車．

圖2 路邊設(shè)備在源車輛簇的傳輸范圍內(nèi)Fig.2 Illustration and diagram of RSU in the transmission range of source vehicle cluster

根據(jù)文獻(xiàn)[11]的實驗數(shù)據(jù)可知，車輛密度服從指數(shù)分布．沿公路上東行線行進(jìn)的兩輛車間的距離可以用車輛密度eλ計算．位于間隔Ur(源車輛到后方第1個 RSU間的距離)中車輛的數(shù)目eU()N r 服從泊松分布

假設(shè)間隔Ur中有n輛車，第i－1輛車與第i輛車

之間的距離為iw，根據(jù)泊松分布的遞增方式，n輛車均勻分布在Ur范圍內(nèi)，因此基于文獻(xiàn)[12–13]中區(qū)間的隨機(jī)劃分結(jié)果，得到

下一個RSU在源車輛的傳輸范圍內(nèi)的概率為

式中：UD為兩個相鄰RSU之間的距離；為Ur的密度函數(shù)．

2.1.2 路邊設(shè)備不在源車輛簇的傳輸范圍內(nèi)

當(dāng)U1不在源車輛簇的傳輸范圍內(nèi)，即U1與源車輛簇的最后一輛車 Vk之間的距離大于 R時(圖3(a))，交通安全消息被存儲并轉(zhuǎn)發(fā)到在相反方向上移動的車輛X，由X將該消息中繼到U1或下一簇中的第1輛車Vk+1．

圖3 路邊設(shè)備不在源車輛簇傳輸范圍內(nèi)Fig.3 Illustration and diagram of RSU not in the transmission range of source vehicle cluster

當(dāng)下一個節(jié)點是 RSU 時(圖 3(b))，隨后的 U1為重新愈合節(jié)點，U1和車輛 X之間的距離為此時，將安全消息傳送到下一個節(jié)點的重新愈合時間U[]Et 近似為

式中：wx為車輛 X與源簇中最后一輛車的覆蓋范圍之間的距離；西行道中車輛之間的距離wλ是西行道上的車輛密度．在間隔cr中車輛V0—Vk均緊密相連(即連續(xù)兩車的間距都小于 R)，此情況概率為c()Wr．在這種情況下，如果 V0后方?jīng)]有連接的車輛(k＝0)，則rc=0，概率為如果V0后面至少有1個連接的車輛(即0wR＜)，則rc＞0，概率為因此

下一節(jié)點是 Vk+1時(圖 3(c))，Vk+1是重新愈合節(jié)點，Vk與Vk+1間距離kw ＞R，X和Vk+1之間的距離是車輛 X和 Vk+1的速度分別為 ve和 vw，假設(shè)可得此時將安全消息傳送到下一節(jié)點的重新愈合時間V[]Et 為

結(jié)合式(5)、式(6)，安全消息傳遞到愈合節(jié)點的重新愈合時間為

式(7)所得結(jié)果為重新愈合時間的上限．

2.2 發(fā)送消息至特定節(jié)點

當(dāng)車輛 VA需要發(fā)送 1個數(shù)據(jù)包到車輛 VD，若VD在 VA的附近區(qū)域，VA將數(shù)據(jù)包廣播到 VD；若不在，VA發(fā)送該數(shù)據(jù)包到其最近的 RSU(U1)．如果 U1具有 VD(表示 VD在 U1的周邊)的位置，則將數(shù)據(jù)包發(fā)送到 VD，如果 U1沒有 VD的位置，它會向所有RSU的鄰居發(fā)送包含 VD的位置查詢數(shù)據(jù)包，如果U1的鄰居 RSU之一(U2)具有的 VD的位置，它發(fā)送1個確認(rèn)字符ACK到U1，U1將數(shù)據(jù)包轉(zhuǎn)發(fā)到U2，由U2發(fā)送到 VD．如果 U1在一定時限 T內(nèi)沒有收到ACK，它向 2跳之外的所有RSU發(fā)送位置查詢報文(即 RSU鄰居的所有 RSU鄰居)，然后 3跳外的RSU，并依此類推．該操作繼續(xù)進(jìn)行，直到 U1接收到有關(guān)VD位置的ACK或者檢查過所有的RSU．

RSU將數(shù)據(jù)包發(fā)送到車輛，首先需要預(yù)測車輛的位置．如圖4所示，RSU(U)根據(jù)得到的車輛V的位置、平均速度和最后一次發(fā)送信標(biāo)的方向來預(yù)測V接收到數(shù)據(jù)包P時的位置．

圖4 車輛位置預(yù)測原理Fig.4 Diagram of estimating the distance of vehicle from RSU

假設(shè)U最后一次接收到V發(fā)來的信標(biāo)顯示，U、V 間的距離為1d、時間戳為1t、并以速度1v向左行駛．經(jīng)過時間ct后，V行駛的距離為(ds為考慮安全而設(shè)的附加距離)，U、V 間距為若V背離U行駛，則間距為，又由(其中 r為 U的傳輸范圍，0t為兩個鄰節(jié)點間的平均傳輸時間，dt和d?分別為車輛攜帶數(shù)據(jù)包的平均時間和平均距離，st為安全時間)，因此P發(fā)送途中V行駛的距離接收到P時距U的距離為V行駛的總距離為然后根據(jù)此距離推測 P可能被發(fā)送到的區(qū)域 Ae，若 V行駛的路段沒有交叉路口，則將 Ae定義為以 V接收 P的預(yù)測坐標(biāo)為圓心，d的誤差因子(可設(shè)為 0.3,d)為半徑的圓；若 V 的行駛路段內(nèi)有交叉路口，則將Ae定義為以路口坐標(biāo)為圓心，ar為半徑的圓．U將數(shù)據(jù)包傳送給 Ae區(qū)域內(nèi)的車輛，然后再轉(zhuǎn)發(fā)給V．

3 仿真實驗

在Qualnet實驗環(huán)境中對SCF、SCB以及本文提出的方法進(jìn)行仿真測試．實驗場景中的 Pathloss model 配置為使用 Street microcell模型．

Mobility And Placement 配置如下：

Node-position-file Opportunity.nodes

Mobility files NONE

Mobility-position-granularity 1.0

節(jié)點無線子網(wǎng)和網(wǎng)絡(luò)接口參數(shù)格式配置如下：

Subnet N8-169.0.0.0 {0 thru 40} default

[N8-169.0.0.0] PHY-RX-model PHY802.11b

NETWORK-PROTOCOL IP

其他參數(shù)設(shè)置：路段長度為 300,km；車輛速度范圍為 10～40,km/h；節(jié)點數(shù)量為 100；Hello消息間隔為10,s；MAC協(xié)議采用802.11b．

在所有車輛都配備 DSRC設(shè)備條件下，不同的RSU數(shù)量、車輛密度時采用本文方法的仿真結(jié)果見圖 5(a)；在 DSRC設(shè)備配備率ρ分別為 10%、50%、100%的情況下測試SCF、SCB機(jī)制的重新愈合時間，仿真結(jié)果見圖5(b)．

由圖 5(a)可以看出：重新愈合時間隨著車輛密度λe和λw的增加而減少；當(dāng)輛/km時，重新愈合時間＜0.1,s．這是因為：對于 RSU 數(shù)量在大多數(shù)情況下交通安全信息可以被傳遞到1個RSU；對于UN＝0，如果eλ和wλ足夠大，也可以使得在高速公路上大多數(shù)車輛相連接，所以重新愈合時間均較短．對比本文方法與 SCB、SCF可知，本文方法的重新愈合時間最短，以車輛密度 λ＝10輛/km為例，SCF的重新愈合時間為 4～6,s，SCB約為20,s，而應(yīng)用 RSU 的重新愈合時間小于 1,s，當(dāng)車輛密度更小時本文方法的優(yōu)勢更加明顯．

圖5 仿真結(jié)果Fig.5 Results of simulation

4 結(jié) 語

本文針對車聯(lián)網(wǎng)中存在的網(wǎng)絡(luò)斷開問題，通過對攜帶轉(zhuǎn)發(fā)機(jī)制的分析，提出將固定設(shè)施 RSU應(yīng)用于廣播協(xié)議．仿真表明，部署 RSU之后很大程度上降低了 VANET的傳輸時延，且路段上的行駛車輛越多，重新愈合時間就越短，考慮到城市區(qū)域的車輛密度較高，可以借助路邊設(shè)施來減小市區(qū) VANET的廣播風(fēng)暴問題．雖然部署 RSU的密度可以控制在一定范圍內(nèi)，但由于 RSU的成本較高，無法廣泛部署，因此對于RSU的部署方案還需進(jìn)一步研究．

［1］ 李麗君，劉鴻飛，楊祖元. 車用自組網(wǎng)信息廣播[J]. 軟件學(xué)報，2010，21(7)：1620–1634.

［2］ Lochert C，Hartenstein H，Tian J，et al. A routing strategy for vehicular ad hoc networks in city environments[C]//Proceedings of the IEEE Intelligent Vehicles Symposium.Piscataway：IEEE，2003：156–161.

［3］ Lochert C，Mauve M，F(xiàn)ü?ler H，et al. Geographic routing in city scenarios[J]. ACM SIGMOBILE Mobile Computing and Communications Review，2005，9(1)：69–72.

［4］ Mo Z，Zhu H，Makki K，et al. MURU：A multi-hop routing protocol for urban vehicular ad hoc networks[C]//Proceedings of the 3rd IEEE International Conference on Mobile and Ubiquitous Systems Workshops. Piscataway：IEEE，2006：1–8.

［5］ Naumov V，Gross T R. Connectivity-aware routing(CAR)in vehicular ad-hoc networks[C]//Proceedings of the 26th IEEE International Conference on Computer Communications. Piscataway：IEEE，2007：1919–1927.

［6］ Zhao J，Cao G. VADD：Vehicle-assisted data delivery in vehicular ad hoc networks[J]. IEEE Transactions on Vehicular Technology，2008，57(3)：1910–1922.

［7］ Ding Y，Wang C，Xiao L. A static-node assisted adaptive routing protocol in vehicular networks[C]//Proceedings of the 4th ACM International Workshop On Vehicular Ad Hoc Networks(VANET’07). New York：ACM，2007：59–68.

［8］ Wisitpongphan N，Tonguz O，Bai F，et al. On the routing problem in disconnected vehicular ad-hoc networks[C]//Proceedings of the 26th IEEE International Conference on Computer Communications. Piscataway：IEEE，2007：2291–2295.

［9］ Sou S，Lee Y. SCB：Store-Carry-Broadcast scheme for message dissemination in sparse VANET[C]// Proceedings of the 75th IEEE Vehicular Technology Conference.Piscataway：IEEE，2012：1–5.

［10］ 王美琛，唐倫，陳前斌. 基于自適應(yīng)選路策略的VANETs路由協(xié)議[J]. 計算機(jī)應(yīng)用與軟件，2013，30(3)：62–66.

［11］ Wisitpongphan N，Bai F，Mudalige P，et al. Routing in sparse vehicular ad hoc wireless networks[J]. IEEE Journal on Selected Areas in Communications，2007，25(8)：1538–1556.

［12］ David H A ，Nagaraja H N. Order Statistics[M].Hoboken，NJ：John Wiley & Sons Inc，2003.

［13］ Darling D A. On a class of problems related to the random division of an interval[J]. The Annals of Mathematical Statistics，1953，24(2)：239–253.