程晗晗，樊秀梅

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

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

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

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

針對(duì)車(chē)聯(lián)網(wǎng)中存在的網(wǎng)絡(luò)斷開(kāi)問(wèn)題，旨在縮短節(jié)點(diǎn)間的重新愈合時(shí)間，本文在已有攜帶轉(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ī)制利用反方向行駛的車(chē)輛作為轉(zhuǎn)發(fā)者將消息傳遞給下一簇(在相同方向上行駛并且只能以單跳或多跳的方式彼此通信的車(chē)輛屬于同一簇)內(nèi)的車(chē)輛，然而只能傳遞給下一簇內(nèi)的第 1輛車(chē)．當(dāng)DSRC(dedicated short-range communications)設(shè)備的普及率很低時(shí)斷開(kāi)節(jié)點(diǎn)的數(shù)量就會(huì)增加，由反方向轉(zhuǎn)發(fā)者執(zhí)行的 SCF機(jī)制的操作數(shù)量增加，從而導(dǎo)致SCF開(kāi)銷(xiāo)增大．

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

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

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

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

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

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

2.1 向后方車(chē)輛廣播安全消息及其重新愈合時(shí)間計(jì)算

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

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

Mobility And Placement 配置如下：

Node-position-file Opportunity.nodes

Mobility files NONE

Mobility-position-granularity 1.0

節(jié)點(diǎn)無(wú)線子網(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è)置：路段長(zhǎng)度為 300,km；車(chē)輛速度范圍為 10～40,km/h；節(jié)點(diǎn)數(shù)量為 100；Hello消息間隔為10,s；MAC協(xié)議采用802.11b．

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

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

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

4 結(jié) 語(yǔ)

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

［1］ 李麗君，劉鴻飛，楊祖元. 車(chē)用自組網(wǎng)信息廣播[J]. 軟件學(xué)報(bào)，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ì)算機(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.