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