0 引言

    近年來出現(xiàn)的車載自組織網(wǎng)絡(luò)(Vehicular Ad Hoc Networks，VANETs)是由一組運(yùn)動(dòng)的車輛所組成,，也可以包含一些固定的通信基礎(chǔ)設(shè)施,，支持車輛-車輛(Vehicular to Vehicular,，V2V)或者車輛-通信設(shè)施(Vehicle to Infrastructure，V2I)之間的通信^[1],。使用VANETs可以提供交通擁堵告警,、交通事故報(bào)警等服務(wù)，以提高通行效率,、增強(qiáng)駕乘人員的安全性,，還可以提供住宿餐飲、加油站信息以及駕乘人員的休閑娛樂等服務(wù),，正在受到汽車制造商,、政府和研究機(jī)構(gòu)等的廣泛關(guān)注^[2-5]。

    不同于移動(dòng)自組網(wǎng)(Mobile Ad Hoc Networks,，MANETs),，VANETs具有節(jié)點(diǎn)移動(dòng)速度更快，鏈路拓?fù)浣Y(jié)構(gòu)變化劇烈,，節(jié)點(diǎn)的網(wǎng)絡(luò)連接經(jīng)常處于斷開和分割狀態(tài),；信號傳播受到路旁建筑的阻擋而具有沿道路傳播等特點(diǎn)。

    目前,，關(guān)于VANETs路由算法的研究已經(jīng)取得了很多成果,，但是現(xiàn)有的VANETs路由算法很少考慮使用路旁設(shè)施輔助路由。路旁設(shè)施屬于智能交通系統(tǒng)和智慧城市的必要組成部分,，據(jù)美國ITS協(xié)會(huì)發(fā)布的車聯(lián)網(wǎng)指南預(yù)測,，美國30萬個(gè)信號控制路口將采用路旁設(shè)施運(yùn)行V2I應(yīng)用^[6]。利用路口設(shè)施中繼輔助可以大大提高VANETs路由算法的性能,。

    相關(guān)研究成果表明,，VAHDAT A等人提出的感染路由（Epidemic）算法^[7]在網(wǎng)絡(luò)負(fù)載較低的環(huán)境中表現(xiàn)出優(yōu)良的性能。但是在高網(wǎng)絡(luò)負(fù)載條件下,，Epidemic會(huì)產(chǎn)生較嚴(yán)重的信道競爭和沖突,，引起其性能的急劇惡化^[1，8-10],。因此出現(xiàn)了很多針對Epidemic算法的改進(jìn)方案,。

    所提出的路口設(shè)施輔助車載自組織網(wǎng)絡(luò)感染路由（Intersection-Relay-Assisted Epidemic Routing，IRAER）算法,，將車輛的鄰居節(jié)點(diǎn)按所在的道路方向的不同,，分別劃分為不同的區(qū)域，在每個(gè)區(qū)域選擇一個(gè)距離自己最遠(yuǎn)的鄰居節(jié)點(diǎn)感染消息,，直到將消息投遞給目標(biāo)節(jié)點(diǎn),。IRAER設(shè)計(jì)實(shí)現(xiàn)了區(qū)域貪婪感染方案、消息感染機(jī)制等。另外,，通過所建立的隨機(jī)模型,，將IRAER產(chǎn)生的副本數(shù)量與Epidemic算法進(jìn)行了對比分析，并通過實(shí)驗(yàn)進(jìn)行了驗(yàn)證,。

    由于現(xiàn)有的單副本單播路由算法均不能適用于目標(biāo)節(jié)點(diǎn)不停運(yùn)動(dòng)的場景,，故仿真實(shí)驗(yàn)選擇與低負(fù)載條件下路由性能最優(yōu)的Epidemic算法進(jìn)行對比。仿真結(jié)果表明,，所提出的IRAER算法在各種場景下實(shí)現(xiàn)的投遞成功率,、投遞時(shí)延性能均優(yōu)于Epidemic算法。即使在低負(fù)載條件下,，IRAER亦實(shí)現(xiàn)與Epidemic算法相當(dāng)?shù)穆酚尚阅堋?/p>

1 相關(guān)工作

    為了在不同節(jié)點(diǎn)密度以及負(fù)載情況下實(shí)現(xiàn)最優(yōu)的消息可達(dá)性,，研究工作者做了很多針對Epidemic算法的改進(jìn)工作。

    概率感染(Probabilistic Epidemic)路由算法^[11],，持有消息的節(jié)點(diǎn)僅以概率p感染鄰居節(jié)點(diǎn),，故可以在一定程度上減少副本數(shù)量，降低信道競爭和沖突,。(p,，q)Epidemic路由算法^[12]，源節(jié)點(diǎn)以概率p感染鄰居節(jié)點(diǎn),，其余節(jié)點(diǎn)以概率q感染。這兩種感染算法雖然也可適用于VANETs,，但均沒有結(jié)合的道路特點(diǎn),。為了降低高負(fù)載下的資源競爭，SAMOR^[13]使用了限制副本數(shù)量的策略,。此方案顯著降低了信道競爭,，但犧牲了消息的可達(dá)性。

    結(jié)合智慧交通和智慧城市的建設(shè)和發(fā)展,，有些文獻(xiàn)也引入了路旁設(shè)施輔助路由策略,。LEE W H等人假設(shè)城市道路的路口均安裝有路旁設(shè)施，用以估算路口之間的消息轉(zhuǎn)發(fā)時(shí)延^[14],。SADV^[8]同樣引入了路口設(shè)施,，當(dāng)在最優(yōu)方向的道路上沒有車輛可供轉(zhuǎn)發(fā)時(shí)，將消息轉(zhuǎn)發(fā)到路口設(shè)施緩存,。SRR^[9]則提出在部分路口使用路旁設(shè)施緩存消息,。但是，由于缺乏及時(shí)可靠的位置服務(wù)支持,，這些算法僅適用于目標(biāo)節(jié)點(diǎn)固定且已知的V2I通信,。

    區(qū)別于以上研究成果，本文所提出的IRAER算法一方面充分考慮了城市道路環(huán)境消息轉(zhuǎn)發(fā)的特點(diǎn)，另一方面大大降低了高負(fù)載場景下消息產(chǎn)生的副本數(shù)量,，進(jìn)而減少了對網(wǎng)絡(luò)帶寬等資源的競爭,，保證了高負(fù)載下的消息可達(dá)性。再者,，所提出的IRAER算法屬于感染路由算法,，可適用于目標(biāo)節(jié)點(diǎn)移動(dòng)且位置未知的V2V通信場景。

2 IRAER算法

2.1 假設(shè)條件

    IRAER假設(shè)城市道路的路口均安裝有路由輔助設(shè)施,。同時(shí)假設(shè)道路上的車輛均安裝了一套無線通信設(shè)施,，并通過這套設(shè)施與其他位于無線通信半徑R范圍內(nèi)的車輛以及路口設(shè)施進(jìn)行通信。車輛同時(shí)內(nèi)置電子地圖,，供路由計(jì)算使用,。車輛位置定位可通過車載GPS系統(tǒng)實(shí)現(xiàn)。

2.2 信標(biāo)消息

    與Epidemic算法以及其他類Epidemic算法相同,，IRAER同樣使用周期性廣播的信標(biāo)消息進(jìn)行鄰居發(fā)現(xiàn)和消息摘要矢量（Summary Vector,，SV）的交換。

    在信標(biāo)消息中包含節(jié)點(diǎn)ID,、當(dāng)前位置坐標(biāo)以及本地所緩存消息的SV,。IRAER的每個(gè)節(jié)點(diǎn)都維持一個(gè)鄰居列表，當(dāng)節(jié)點(diǎn)收到一個(gè)信標(biāo)消息后,，如果信標(biāo)消息攜帶的ID在鄰居列表中不存在,，表明一個(gè)新的鄰居進(jìn)入通信范圍，則將其ID,、位置坐標(biāo),、SV以及時(shí)間戳作為一個(gè)條目插入到鄰居列表中；如果信標(biāo)消息中的節(jié)點(diǎn)ID在鄰居列表中已經(jīng)存在,，則更新該ID對應(yīng)的條目,；如果超過一個(gè)信標(biāo)周期仍然沒有收到來自于某一鄰居車輛的信標(biāo)消息，則認(rèn)為該鄰居已經(jīng)離開通信范圍,，將其從鄰居列表中刪除,。

2.3 鄰居節(jié)點(diǎn)的區(qū)域劃分

    與其他感染算法不同，IRAER根據(jù)節(jié)點(diǎn)的鄰居所在的不同道路方向劃分為不同的區(qū)域,。位于兩個(gè)路口之間的道路上的節(jié)點(diǎn),，其鄰居節(jié)點(diǎn)可以劃分為兩個(gè)區(qū)域。位于路口的節(jié)點(diǎn)（包括路由輔助設(shè)施）,，由于在每個(gè)相鄰路口方向都可以進(jìn)行感染,，則位于該節(jié)點(diǎn)和每個(gè)相鄰路口之間的鄰居均為一個(gè)區(qū)域。

    在節(jié)點(diǎn)N的一個(gè)鄰居區(qū)域Z_i中,，距離它最遠(yuǎn)的一個(gè)節(jié)點(diǎn)稱為節(jié)點(diǎn)N在Zi的候感節(jié)點(diǎn),。

2.4 區(qū)域貪婪感染

    與其他感染算法不同,，IRAER使用貪婪感染機(jī)制，在每一個(gè)鄰居區(qū)域中選擇一個(gè)候感節(jié)點(diǎn)進(jìn)行感染,。這樣,，在一簇車輛節(jié)點(diǎn)中，對于新產(chǎn)生的消息,，該消息將以步長R逐一選擇候感節(jié)點(diǎn)進(jìn)行感染,。

    對于在節(jié)點(diǎn)本地所緩存的消息，通過與鄰居節(jié)點(diǎn)之間進(jìn)行SV交換,，獲取需要感染的消息集合并實(shí)現(xiàn)消息交換,。如果一個(gè)節(jié)點(diǎn)N所緩存的消息在它的鄰居區(qū)域中的某一個(gè)節(jié)點(diǎn)中緩存，由于該鄰居節(jié)點(diǎn)可以感染距離更遠(yuǎn)的節(jié)點(diǎn),，所以節(jié)點(diǎn)N不需要觸發(fā)感染,。

    假設(shè)ZSV_i為節(jié)點(diǎn)N的一個(gè)鄰居區(qū)域Z_i中的所有節(jié)點(diǎn)SV的集合，SV_N表示節(jié)點(diǎn)N的SV,，則在SV_N中緩存且在ZSV_i中沒有緩存的消息集合S_i,，節(jié)點(diǎn)N才可以將這些消息轉(zhuǎn)發(fā)給Z_i中的候感節(jié)點(diǎn)。

    ZSV_i可以表示為：

    為了使得消息在路口可以向其他路口方向感染,，消息必須感染位于路口的輔助設(shè)施,，而不能跨越路口。即,，節(jié)點(diǎn)N在Z_i中如果存在輔助設(shè)施節(jié)點(diǎn)A,，N在Z_i中的候感節(jié)點(diǎn)將被設(shè)置為A。IRAER算法的消息感染過程可以表示為圖1所示,。

    圖1中,，空心圓代表道路上的車輛，空心圓的編號代表車輛ID,，箭頭代表消息感染的方向，位于路口中央的空心圓代表路由輔助設(shè)施,。從道路左邊轉(zhuǎn)發(fā)過來的一個(gè)新的消息M的副本位于節(jié)點(diǎn)1,，節(jié)點(diǎn)1的鄰居區(qū)域中的候感節(jié)點(diǎn)為2，因此節(jié)點(diǎn)1將M的副本轉(zhuǎn)發(fā)給節(jié)點(diǎn)2,。由于節(jié)點(diǎn)A是路由輔助設(shè)施,，因此節(jié)點(diǎn)2會(huì)將M的副本轉(zhuǎn)發(fā)給節(jié)點(diǎn)A。由于節(jié)點(diǎn)A在路口的北向道路中只有一個(gè)鄰居車輛3,，故A將M的副本轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)3,。由于節(jié)點(diǎn)3同時(shí)在節(jié)點(diǎn)A的東向鄰居區(qū)域，故在節(jié)點(diǎn)A的東向鄰居區(qū)域ZSV中已經(jīng)包含了消息M的ID,，則節(jié)點(diǎn)A不向其東向鄰居區(qū)域感染其他鄰居節(jié)點(diǎn),，消息M由節(jié)點(diǎn)3感染節(jié)點(diǎn)4。由于節(jié)點(diǎn)5是節(jié)點(diǎn)A的南向鄰居區(qū)域的候感節(jié)點(diǎn)，故節(jié)點(diǎn)A將M的副本轉(zhuǎn)發(fā)節(jié)點(diǎn)5,。

2.5 感染機(jī)制

    由于IRAER算法中一個(gè)節(jié)點(diǎn)對自己是否為候感節(jié)點(diǎn)毫不知情,，故不能主動(dòng)請求消息集合S_i。因此與Epidemic算法不同,，IRAER適用于使用“推”機(jī)制觸發(fā)感染^[15],。

    Epidemic算法雖然采用的是“拉”機(jī)制進(jìn)行感染，但由于信標(biāo)消息的廣播是異步的,，故可以保證消息幾乎可以在產(chǎn)生之后及時(shí)感染其他節(jié)點(diǎn),。IRAER為了使得消息可以及時(shí)感染候感節(jié)點(diǎn)，故在節(jié)點(diǎn)N感染消息之后,，立即根據(jù)S_i將消息感染給候感節(jié)點(diǎn),。如果感染失敗，或者候感節(jié)點(diǎn)剛好離開了節(jié)點(diǎn)N的無線覆蓋范圍,，則在下一個(gè)廣播周期通過交換SV重新感染,。

3 IRAER副本數(shù)量分析隨機(jī)模型

    WISITPONGPHAN N等人^[16]和TIAN D X等人^[17]分別根據(jù)探測數(shù)進(jìn)行統(tǒng)計(jì)分析發(fā)現(xiàn)，在車輛密度較稀疏的情況下,，道路上的車輛間距分布符合指數(shù)分布規(guī)律,。利用此規(guī)律，可以對IRAER在感染過程中產(chǎn)生的副本數(shù)量與Epidemic進(jìn)行對比分析,。

    根據(jù)WISITPONGPHAN N等人的研究結(jié)果,，車輛簇的平均長度可表示為：

其中，λ_S為車輛間距指數(shù)分布的參數(shù),。假設(shè)地圖上道路的總長度為L,，節(jié)點(diǎn)的數(shù)量為K，則λ_S可表示為：

4 仿真

    現(xiàn)有的VANETs單副本單播路由算法如VADD^[1],、IBFP^[10],、GFAVR^[18]，以及路口設(shè)施輔助路由算法如SADV^[8],、SRR^[9]等,，由于缺乏及時(shí)可靠的位置服務(wù)，不能適應(yīng)于目標(biāo)節(jié)點(diǎn)不停運(yùn)動(dòng)的通信場景,。而IRAER不需要目標(biāo)節(jié)點(diǎn)的位置信息,。且眾多理論和仿真實(shí)驗(yàn)表明，Epidemic路由算法在低負(fù)載條件下的路由性能是最優(yōu)的^[1,，8-10],，因此仿真實(shí)驗(yàn)選擇了與Epidemic路由算法進(jìn)行對比。

4.1 仿真設(shè)置

    仿真實(shí)驗(yàn)平臺(tái)采用的是網(wǎng)絡(luò)協(xié)議仿真器NS-2^[19],，仿真實(shí)驗(yàn)地圖環(huán)境采用常用的曼哈頓網(wǎng)格地圖^[1,，20-22],。車輛運(yùn)動(dòng)數(shù)據(jù)集使用開源軟件VanetMobiSim^[23]所產(chǎn)生，道路設(shè)置為雙向兩車道,，限速為22 m/s(80 km/h),。

    仿真過程中，節(jié)點(diǎn)之間使用CBR應(yīng)用層協(xié)議進(jìn)行通信,，CBR的源和目標(biāo)都是隨機(jī)產(chǎn)生,。CBR的負(fù)載分別設(shè)置為50 B和600 B以評估不同消息負(fù)載下的協(xié)議性能。車輛數(shù)量為100~400,，以產(chǎn)生不同節(jié)點(diǎn)密度的道路環(huán)境,。仿真參數(shù)如表1所示。

4.2 投遞成功率

    投遞成功率定義為CBR消息在給定時(shí)間內(nèi)成功投遞到目標(biāo)節(jié)點(diǎn)的比例,。圖2所示為車輛數(shù)量為100,、CBR負(fù)載為50 B的低信道競爭網(wǎng)絡(luò)環(huán)境以及車輛數(shù)量為400、CBR負(fù)載為600 B高信道競爭網(wǎng)絡(luò)環(huán)境下的投遞成功率累積概率密度分布,。

    從圖中可以看出,，在Epidemic最適合的低信道競爭網(wǎng)絡(luò)環(huán)境下，IRAER實(shí)現(xiàn)的投遞成功率仍然優(yōu)于Epidemic,；而在信道競爭較大的網(wǎng)絡(luò)環(huán)境下,，IRAER的投遞成功率則大大高于Epidemic。

4.3 投遞時(shí)延

    投遞時(shí)延定義為消息投遞成功需要的平均時(shí)間,。圖3為兩種CBR負(fù)載（50 B,、600 B）分別在不同車輛密度條件下實(shí)現(xiàn)的平均投遞時(shí)延。

    從圖3可見,，IRAER在高車輛密度和高負(fù)載條件下實(shí)現(xiàn)的投遞時(shí)延大大低于Epidemic,，且IRAER受負(fù)載條件的影響更小。

4.4 副本數(shù)量

    副本數(shù)量定義為CBR消息投遞成功時(shí),，在網(wǎng)絡(luò)中所有節(jié)點(diǎn)中所緩存CBR副本數(shù)量的平均值,。IRAER與Epidemic在仿真過程中產(chǎn)生的副本數(shù)量比例與理論分析結(jié)果的對比如圖4所示。

    從圖4可知,，隨著車輛密度的增加,，IRAER與Epidemic產(chǎn)生的副本數(shù)量比例越接近于理論分析結(jié)果。其原因在于車輛密度增加后,，消息平均投遞時(shí)延較低，因而由于車輛簇成員的變化引起的感染數(shù)量也較低,。

5 結(jié)束語

    車載自組織網(wǎng)絡(luò)由于節(jié)點(diǎn)的運(yùn)動(dòng)速度快,，網(wǎng)絡(luò)連接經(jīng)常處于斷開狀態(tài)，因而消息的投遞時(shí)延較長,、性能較差,。在路口增加路由輔助設(shè)施則可以顯著提高消息投遞性能,。本文提出的IRAER算法利用路口設(shè)施輔助路由，同時(shí)分析并利用了車輛簇的特點(diǎn),，將鄰居節(jié)點(diǎn)劃分為不同的區(qū)域,，在每個(gè)鄰居區(qū)域中僅選擇一個(gè)距離最遠(yuǎn)的候感節(jié)點(diǎn)進(jìn)行感染，故而在車輛密度較大的場景下大大降低了感染所產(chǎn)生的副本數(shù)量,，進(jìn)而降低了對帶寬資源的競爭和沖突,，提高了路由性能。

    本文利用道路上車輛分布的統(tǒng)計(jì)規(guī)律,，分析了IRAER與Epidemic產(chǎn)生的副本數(shù)量的關(guān)系,，并通過仿真實(shí)驗(yàn)進(jìn)行了驗(yàn)證。仿真實(shí)驗(yàn)結(jié)果同時(shí)表明,，所提出的IRAER路由算法在高負(fù)載環(huán)境下實(shí)現(xiàn)的投遞成功率和投遞時(shí)延性能指標(biāo)均顯著高于Epidemic算法,，同時(shí)在Epidemic最適合的低負(fù)載環(huán)境下性能亦可相匹敵。

參考文獻(xiàn)

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

[2] HUANG C M,，LIN S Y.An early collision warning algorithm for vehicles based on V2V communication[J].International Journal of Communication Systems,，2012，25(6)：779-795.

[3] 李東穎.車聯(lián)網(wǎng)將成產(chǎn)業(yè)革命推動(dòng)力[N].北京青年報(bào),，2014-08-06(1).

[4] CUNHA F,，VILLAS L，BOUKERCHE A,，et al.Data communication in VANETs：Protocols,，applications and challenges[J].Ad Hoc Networks，2016,，44：90-103.

[5] AZEES M,，VIJAYAKUMAR P，DEBORAH L J.Comprehensive survey on security services in vehicular ad-hoc networks[J].IET Intelligent Transport Systems,，2016,，10(6)：379-388.

[6] BAYLESS S H，GUA A.Connected vehicle technical insights[EB/OL].(2015-07-27)[2016-10-11].http：//www.itsinternational.com/sections/nafta/features/its-america-publishes-connected-vehicle-guidance/.

[7] VAHDAT A,，BECKER D.Technical report CS-200006[R].Durham,，USA：Duke University，2000.

[8] DING Y,，XIAO L.SADV：Static-node-assisted adaptive data dissemination in vehicular networks[J].IEEE Transactions on Vehicular Technology,，2010，59(5)：2445-2455.

[9] TIAN R,，ZHANG B X,，LI C,，et al.Sparsely-deployed relay node assisted routing algorithm for vehicular ad hoc networks[J].Wireless Communications & Mobile Computing，2015,，15(9)：1309-1319.

[10] GUAN X,，HUANG Y，CAI Z P,，et al.Intersection-based forwarding protocol for vehicular ad hoc networks[J].Telecommunication Systems,，2016，62(1)：67-76.

[11] ZHANG X,，NEGLIA G,，KUROSE J，et al.Performance modeling of epidemic routing[J].Computer Networks,，2007,，51(10)：2867-2891.

[12] MATSUDA T，TAKINE T.(p,，q)-Epidemic routing for sparsely populated mobile ad hoc networks[J].IEEE Journal on Selected Areas in Communications,，2008，26(5)：783-793.

[13] 孫海峰,，羅光春,，秦科.社會(huì)感知多副本車載自組織網(wǎng)絡(luò)機(jī)會(huì)路由協(xié)議[J].計(jì)算機(jī)應(yīng)用研究，2014,，31(3)：857-859,，887.

[14] LEE W H，HWANG K P,，WU W B.An intersection-to-intersection travel time estimation and route suggestion approach using vehicular ad-hoc network[J].Ad Hoc Networks,，2016，43：71-81.

[15] AKDERE M,，BILGIN C C,，GERDANERI O，et al.A comparison of epidemic algorithms in wireless sensor networks[J].Computer Communications,，2006,，29(13-14)：2450-2457.

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

[17] TIAN D X,，LEUNG V C M.Analysis of broadcasting delays in vehicular ad hoc networks[J].Wireless Communications & Mobile Computing，2011，11(11)：1433-1445.

[18] BAZZI A,，ZANELLA A.Position based routing in crowd sensing vehicular networks[J].Ad Hoc Networks，2016,，36：409-424.

[19] NSNAM.Network Simulator(ns-2)[CP/OL].(2014-12-19)[2015-03-06].http：//nsnam.isi.edu/nsnam/index.php/Main_Page.

[20] WU T Y,，WANG Y B，LEE W T.Mixing greedy and predictive approaches to improve geographic routing for VANET[J].Wireless Communications & Mobile Computing,，2012,，12(4)：367-378.

[21] SUN H F，LUO G C,，CHEN H.JTAR：Junction-based traffic aware routing in sparse urban VANETs[J].IEICE Transactions on Communications,，2012，E95B(3)：1007-1010.

[22] JERBI M,，SENOUCI S-M,，RASHEED T，et al.Towards efficient geographic routing in urban vehicular networks[J].IEEE Transactions on Vehicular Technology,，2009,，58(9)：5048-5059.

[23] HARRI J，F(xiàn)IORE M,，F(xiàn)ILALI F,，et al.Vehicular mobility simulation with VanetMobiSim[J].Simulation，2009,，87(4)：275-300.