文獻(xiàn)標(biāo)識碼： A
DOI：10.16157/j.issn.0258-7998.171576
中文引用格式： 孫海峰，宋麗麗. 路口設(shè)施中繼輔助車載自組織網(wǎng)絡(luò)感染路由算法[J].電子技術(shù)應(yīng)用，2017，43(11)：90-94.
英文引用格式： Sun Haifeng，Song Lili. Intersection-relay-assisted epidemic routing in VANETs[J].Application of Electronic Technique，2017，43(11)：90-94.
0 引言
近年來出現(xiàn)的車載自組織網(wǎng)絡(luò)(Vehicular Ad Hoc Networks，VANETs)是由一組運動的車輛所組成，也可以包含一些固定的通信基礎(chǔ)設(shè)施，支持車輛-車輛(Vehicular to Vehicular，V2V)或者車輛-通信設(shè)施(Vehicle to Infrastructure，V2I)之間的通信[1]。使用VANETs可以提供交通擁堵告警、交通事故報警等服務(wù)，以提高通行效率、增強駕乘人員的安全性，還可以提供住宿餐飲、加油站信息以及駕乘人員的休閑娛樂等服務(wù)，正在受到汽車制造商、政府和研究機構(gòu)等的廣泛關(guān)注[2-5]。
不同于移動自組網(wǎng)(Mobile Ad Hoc Networks，MANETs)，VANETs具有節(jié)點移動速度更快，鏈路拓?fù)浣Y(jié)構(gòu)變化劇烈，節(jié)點的網(wǎng)絡(luò)連接經(jīng)常處于斷開和分割狀態(tài)；信號傳播受到路旁建筑的阻擋而具有沿道路傳播等特點。
目前，關(guān)于VANETs路由算法的研究已經(jīng)取得了很多成果，但是現(xiàn)有的VANETs路由算法很少考慮使用路旁設(shè)施輔助路由。路旁設(shè)施屬于智能交通系統(tǒng)和智慧城市的必要組成部分，據(jù)美國ITS協(xié)會發(fā)布的車聯(lián)網(wǎng)指南預(yù)測，美國30萬個信號控制路口將采用路旁設(shè)施運行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會產(chǎn)生較嚴(yán)重的信道競爭和沖突，引起其性能的急劇惡化[1，8-10]。因此出現(xiàn)了很多針對Epidemic算法的改進(jìn)方案。
所提出的路口設(shè)施輔助車載自組織網(wǎng)絡(luò)感染路由（Intersection-Relay-Assisted Epidemic Routing，IRAER）算法，將車輛的鄰居節(jié)點按所在的道路方向的不同，分別劃分為不同的區(qū)域，在每個區(qū)域選擇一個距離自己最遠(yuǎn)的鄰居節(jié)點感染消息，直到將消息投遞給目標(biāo)節(jié)點。IRAER設(shè)計實現(xiàn)了區(qū)域貪婪感染方案、消息感染機制等。另外，通過所建立的隨機模型，將IRAER產(chǎn)生的副本數(shù)量與Epidemic算法進(jìn)行了對比分析，并通過實驗進(jìn)行了驗證。
由于現(xiàn)有的單副本單播路由算法均不能適用于目標(biāo)節(jié)點不停運動的場景，故仿真實驗選擇與低負(fù)載條件下路由性能最優(yōu)的Epidemic算法進(jìn)行對比。仿真結(jié)果表明，所提出的IRAER算法在各種場景下實現(xiàn)的投遞成功率、投遞時延性能均優(yōu)于Epidemic算法。即使在低負(fù)載條件下，IRAER亦實現(xiàn)與Epidemic算法相當(dāng)?shù)穆酚尚阅堋?/p>
1 相關(guān)工作
為了在不同節(jié)點密度以及負(fù)載情況下實現(xiàn)最優(yōu)的消息可達(dá)性，研究工作者做了很多針對Epidemic算法的改進(jìn)工作。
概率感染(Probabilistic Epidemic)路由算法[11]，持有消息的節(jié)點僅以概率p感染鄰居節(jié)點，故可以在一定程度上減少副本數(shù)量，降低信道競爭和沖突。(p，q)Epidemic路由算法[12]，源節(jié)點以概率p感染鄰居節(jié)點，其余節(jié)點以概率q感染。這兩種感染算法雖然也可適用于VANETs，但均沒有結(jié)合的道路特點。為了降低高負(fù)載下的資源競爭，SAMOR[13]使用了限制副本數(shù)量的策略。此方案顯著降低了信道競爭，但犧牲了消息的可達(dá)性。
結(jié)合智慧交通和智慧城市的建設(shè)和發(fā)展，有些文獻(xiàn)也引入了路旁設(shè)施輔助路由策略。LEE W H等人假設(shè)城市道路的路口均安裝有路旁設(shè)施，用以估算路口之間的消息轉(zhuǎn)發(fā)時延[14]。SADV[8]同樣引入了路口設(shè)施，當(dāng)在最優(yōu)方向的道路上沒有車輛可供轉(zhuǎn)發(fā)時，將消息轉(zhuǎn)發(fā)到路口設(shè)施緩存。SRR[9]則提出在部分路口使用路旁設(shè)施緩存消息。但是，由于缺乏及時可靠的位置服務(wù)支持，這些算法僅適用于目標(biāo)節(jié)點固定且已知的V2I通信。
區(qū)別于以上研究成果，本文所提出的IRAER算法一方面充分考慮了城市道路環(huán)境消息轉(zhuǎn)發(fā)的特點，另一方面大大降低了高負(fù)載場景下消息產(chǎn)生的副本數(shù)量，進(jìn)而減少了對網(wǎng)絡(luò)帶寬等資源的競爭，保證了高負(fù)載下的消息可達(dá)性。再者，所提出的IRAER算法屬于感染路由算法，可適用于目標(biāo)節(jié)點移動且位置未知的V2V通信場景。
2 IRAER算法
2.1 假設(shè)條件
IRAER假設(shè)城市道路的路口均安裝有路由輔助設(shè)施。同時假設(shè)道路上的車輛均安裝了一套無線通信設(shè)施，并通過這套設(shè)施與其他位于無線通信半徑R范圍內(nèi)的車輛以及路口設(shè)施進(jìn)行通信。車輛同時內(nèi)置電子地圖，供路由計算使用。車輛位置定位可通過車載GPS系統(tǒng)實現(xiàn)。
2.2 信標(biāo)消息
與Epidemic算法以及其他類Epidemic算法相同，IRAER同樣使用周期性廣播的信標(biāo)消息進(jìn)行鄰居發(fā)現(xiàn)和消息摘要矢量（Summary Vector，SV）的交換。
在信標(biāo)消息中包含節(jié)點ID、當(dāng)前位置坐標(biāo)以及本地所緩存消息的SV。IRAER的每個節(jié)點都維持一個鄰居列表，當(dāng)節(jié)點收到一個信標(biāo)消息后，如果信標(biāo)消息攜帶的ID在鄰居列表中不存在，表明一個新的鄰居進(jìn)入通信范圍，則將其ID、位置坐標(biāo)、SV以及時間戳作為一個條目插入到鄰居列表中；如果信標(biāo)消息中的節(jié)點ID在鄰居列表中已經(jīng)存在，則更新該ID對應(yīng)的條目；如果超過一個信標(biāo)周期仍然沒有收到來自于某一鄰居車輛的信標(biāo)消息，則認(rèn)為該鄰居已經(jīng)離開通信范圍，將其從鄰居列表中刪除。
2.3 鄰居節(jié)點的區(qū)域劃分
與其他感染算法不同，IRAER根據(jù)節(jié)點的鄰居所在的不同道路方向劃分為不同的區(qū)域。位于兩個路口之間的道路上的節(jié)點，其鄰居節(jié)點可以劃分為兩個區(qū)域。位于路口的節(jié)點（包括路由輔助設(shè)施），由于在每個相鄰路口方向都可以進(jìn)行感染，則位于該節(jié)點和每個相鄰路口之間的鄰居均為一個區(qū)域。
在節(jié)點N的一個鄰居區(qū)域Zi中，距離它最遠(yuǎn)的一個節(jié)點稱為節(jié)點N在Zi的候感節(jié)點。
2.4 區(qū)域貪婪感染
與其他感染算法不同，IRAER使用貪婪感染機制，在每一個鄰居區(qū)域中選擇一個候感節(jié)點進(jìn)行感染。這樣，在一簇車輛節(jié)點中，對于新產(chǎn)生的消息，該消息將以步長R逐一選擇候感節(jié)點進(jìn)行感染。
對于在節(jié)點本地所緩存的消息，通過與鄰居節(jié)點之間進(jìn)行SV交換，獲取需要感染的消息集合并實現(xiàn)消息交換。如果一個節(jié)點N所緩存的消息在它的鄰居區(qū)域中的某一個節(jié)點中緩存，由于該鄰居節(jié)點可以感染距離更遠(yuǎn)的節(jié)點，所以節(jié)點N不需要觸發(fā)感染。
假設(shè)ZSVi為節(jié)點N的一個鄰居區(qū)域Zi中的所有節(jié)點SV的集合，SVN表示節(jié)點N的SV，則在SVN中緩存且在ZSVi中沒有緩存的消息集合Si，節(jié)點N才可以將這些消息轉(zhuǎn)發(fā)給Zi中的候感節(jié)點。
ZSVi可以表示為：
為了使得消息在路口可以向其他路口方向感染，消息必須感染位于路口的輔助設(shè)施，而不能跨越路口。即，節(jié)點N在Zi中如果存在輔助設(shè)施節(jié)點A，N在Zi中的候感節(jié)點將被設(shè)置為A。IRAER算法的消息感染過程可以表示為圖1所示。
圖1中，空心圓代表道路上的車輛，空心圓的編號代表車輛ID，箭頭代表消息感染的方向，位于路口中央的空心圓代表路由輔助設(shè)施。從道路左邊轉(zhuǎn)發(fā)過來的一個新的消息M的副本位于節(jié)點1，節(jié)點1的鄰居區(qū)域中的候感節(jié)點為2，因此節(jié)點1將M的副本轉(zhuǎn)發(fā)給節(jié)點2。由于節(jié)點A是路由輔助設(shè)施，因此節(jié)點2會將M的副本轉(zhuǎn)發(fā)給節(jié)點A。由于節(jié)點A在路口的北向道路中只有一個鄰居車輛3，故A將M的副本轉(zhuǎn)發(fā)給鄰居節(jié)點3。由于節(jié)點3同時在節(jié)點A的東向鄰居區(qū)域，故在節(jié)點A的東向鄰居區(qū)域ZSV中已經(jīng)包含了消息M的ID，則節(jié)點A不向其東向鄰居區(qū)域感染其他鄰居節(jié)點，消息M由節(jié)點3感染節(jié)點4。由于節(jié)點5是節(jié)點A的南向鄰居區(qū)域的候感節(jié)點，故節(jié)點A將M的副本轉(zhuǎn)發(fā)節(jié)點5。
2.5 感染機制
由于IRAER算法中一個節(jié)點對自己是否為候感節(jié)點毫不知情，故不能主動請求消息集合Si。因此與Epidemic算法不同，IRAER適用于使用“推”機制觸發(fā)感染[15]。
Epidemic算法雖然采用的是“拉”機制進(jìn)行感染，但由于信標(biāo)消息的廣播是異步的，故可以保證消息幾乎可以在產(chǎn)生之后及時感染其他節(jié)點。IRAER為了使得消息可以及時感染候感節(jié)點，故在節(jié)點N感染消息之后，立即根據(jù)Si將消息感染給候感節(jié)點。如果感染失敗，或者候感節(jié)點剛好離開了節(jié)點N的無線覆蓋范圍，則在下一個廣播周期通過交換SV重新感染。
3 IRAER副本數(shù)量分析隨機模型
WISITPONGPHAN N等人[16]和TIAN D X等人[17]分別根據(jù)探測數(shù)進(jìn)行統(tǒng)計分析發(fā)現(xiàn)，在車輛密度較稀疏的情況下，道路上的車輛間距分布符合指數(shù)分布規(guī)律。利用此規(guī)律，可以對IRAER在感染過程中產(chǎn)生的副本數(shù)量與Epidemic進(jìn)行對比分析。
根據(jù)WISITPONGPHAN N等人的研究結(jié)果，車輛簇的平均長度可表示為：
其中，λS為車輛間距指數(shù)分布的參數(shù)。假設(shè)地圖上道路的總長度為L，節(jié)點的數(shù)量為K，則λS可表示為：
4 仿真
現(xiàn)有的VANETs單副本單播路由算法如VADD[1]、IBFP[10]、GFAVR[18]，以及路口設(shè)施輔助路由算法如SADV[8]、SRR[9]等，由于缺乏及時可靠的位置服務(wù)，不能適應(yīng)于目標(biāo)節(jié)點不停運動的通信場景。而IRAER不需要目標(biāo)節(jié)點的位置信息。且眾多理論和仿真實驗表明，Epidemic路由算法在低負(fù)載條件下的路由性能是最優(yōu)的[1，8-10]，因此仿真實驗選擇了與Epidemic路由算法進(jìn)行對比。
4.1 仿真設(shè)置
仿真實驗平臺采用的是網(wǎng)絡(luò)協(xié)議仿真器NS-2[19]，仿真實驗地圖環(huán)境采用常用的曼哈頓網(wǎng)格地圖[1，20-22]。車輛運動數(shù)據(jù)集使用開源軟件VanetMobiSim[23]所產(chǎn)生，道路設(shè)置為雙向兩車道，限速為22 m/s(80 km/h)。
仿真過程中，節(jié)點之間使用CBR應(yīng)用層協(xié)議進(jìn)行通信，CBR的源和目標(biāo)都是隨機產(chǎn)生。CBR的負(fù)載分別設(shè)置為50 B和600 B以評估不同消息負(fù)載下的協(xié)議性能。車輛數(shù)量為100~400，以產(chǎn)生不同節(jié)點密度的道路環(huán)境。仿真參數(shù)如表1所示。
4.2 投遞成功率
投遞成功率定義為CBR消息在給定時間內(nèi)成功投遞到目標(biāo)節(jié)點的比例。圖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實現(xiàn)的投遞成功率仍然優(yōu)于Epidemic；而在信道競爭較大的網(wǎng)絡(luò)環(huán)境下，IRAER的投遞成功率則大大高于Epidemic。
4.3 投遞時延
投遞時延定義為消息投遞成功需要的平均時間。圖3為兩種CBR負(fù)載（50 B、600 B）分別在不同車輛密度條件下實現(xiàn)的平均投遞時延。
從圖3可見，IRAER在高車輛密度和高負(fù)載條件下實現(xiàn)的投遞時延大大低于Epidemic，且IRAER受負(fù)載條件的影響更小。
4.4 副本數(shù)量
副本數(shù)量定義為CBR消息投遞成功時，在網(wǎng)絡(luò)中所有節(jié)點中所緩存CBR副本數(shù)量的平均值。IRAER與Epidemic在仿真過程中產(chǎn)生的副本數(shù)量比例與理論分析結(jié)果的對比如圖4所示。
從圖4可知，隨著車輛密度的增加，IRAER與Epidemic產(chǎn)生的副本數(shù)量比例越接近于理論分析結(jié)果。其原因在于車輛密度增加后，消息平均投遞時延較低，因而由于車輛簇成員的變化引起的感染數(shù)量也較低。
5 結(jié)束語
車載自組織網(wǎng)絡(luò)由于節(jié)點的運動速度快，網(wǎng)絡(luò)連接經(jīng)常處于斷開狀態(tài)，因而消息的投遞時延較長、性能較差。在路口增加路由輔助設(shè)施則可以顯著提高消息投遞性能。本文提出的IRAER算法利用路口設(shè)施輔助路由，同時分析并利用了車輛簇的特點，將鄰居節(jié)點劃分為不同的區(qū)域，在每個鄰居區(qū)域中僅選擇一個距離最遠(yuǎn)的候感節(jié)點進(jìn)行感染，故而在車輛密度較大的場景下大大降低了感染所產(chǎn)生的副本數(shù)量，進(jìn)而降低了對帶寬資源的競爭和沖突，提高了路由性能。
本文利用道路上車輛分布的統(tǒng)計規(guī)律，分析了IRAER與Epidemic產(chǎn)生的副本數(shù)量的關(guān)系，并通過仿真實驗進(jìn)行了驗證。仿真實驗結(jié)果同時表明，所提出的IRAER路由算法在高負(fù)載環(huán)境下實現(xiàn)的投遞成功率和投遞時延性能指標(biāo)均顯著高于Epidemic算法，同時在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è)革命推動力[N].北京青年報，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] 孫海峰，羅光春，秦科.社會感知多副本車載自組織網(wǎng)絡(luò)機會路由協(xié)議[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.