從繼成，張韌志

(黃淮學院 a.動畫學院;b.信息工程學院，河南 駐馬店463000)

作為智能交通系統(tǒng)的最有前景應用技術之一，車聯(lián)網(wǎng)VANETs(Vehicular Ad Hoc Networks)的相關技術成為研究焦點［1－2］。VANETs 提供了車間通信和車與基礎設施的通信平臺，便捷了車間信息的交互。行駛中的車輛通過相互共享實時的交通信息，提高行駛安全。車輛是VANETs 網(wǎng)絡的重要組成部分，然而車輛的快速移動導致VANETs 網(wǎng)絡拓撲動態(tài)變化，給數(shù)據(jù)傳輸提出了挑戰(zhàn)。據(jù)此，VANETs 的路由技術成為研究熱點。依據(jù)數(shù)據(jù)包的目的節(jié)點數(shù)的不同，可將VANETs 路由協(xié)議分為單播路由(Unicast Routing)、廣播路由以及多播路由［3］，其中地域性多播路由GR(Geocast Routing)是屬于多播路由的一個子類。在單播路由協(xié)議中，數(shù)據(jù)包的目的節(jié)點僅一個。而地域性多播路由中數(shù)據(jù)包的目的節(jié)點數(shù)是多個，將多個目的節(jié)點所在的位置稱為目標區(qū)域。換而言之，目標區(qū)域由多個車輛構成，而非某單一車輛。當前方車輛發(fā)現(xiàn)事故，需將這一緊急消息傳遞后方車輛，那么后方所有車輛均是緊急消息傳輸?shù)哪繕?。這些車輛所在位置便構成了消息傳輸?shù)哪繕藚^(qū)域。

IVG(Inter Vehicle Geocast)［4］屬于典型的GR 協(xié)議，依據(jù)車輛的行駛方向和位置設定目標區(qū)域。IVG 協(xié)議利用泛洪機制向目標區(qū)域轉發(fā)數(shù)據(jù)包，并采用傳輸時延防止數(shù)據(jù)包重傳。若在給定的時間間隔內，某一節(jié)點收到一個數(shù)據(jù)包的復本，表明此數(shù)據(jù)包已被其他節(jié)點轉發(fā)了，因此該節(jié)點就不再重轉。通過這種防止重傳數(shù)據(jù)包的機制，減少數(shù)據(jù)傳輸開銷。然而利用泛洪轉發(fā)數(shù)據(jù)包，仍大大增加了系統(tǒng)開銷。

此外，文獻［5］提出了分布式魯棒多播DRG(Distributed Robust Geocast)協(xié)議。它利用快速、可靠方式轉發(fā)消息，減少了傳輸?shù)目刂瓢鼣?shù)量，進而降低了網(wǎng)絡開銷。然而，DRG 路由仍采用了泛洪機制，無法避免因泛洪而引起的開銷，特別是在密集的城市環(huán)境。

文獻［6］提出了基于空間信息的GR 路由。該路由采用了存儲－轉發(fā)，并利用車輛的歷史軌跡構建移動模型。盡管降低了路由開銷，但是實時獲取車輛的軌跡是非常復雜的，特別是在車輛高速移動的環(huán)境下，這降低了數(shù)據(jù)包傳輸速率。

傳統(tǒng)的GR 路由常引用泛洪機制，這極大地增加了開銷，特別是當源節(jié)點與目標區(qū)域相距較遠時，泛洪機制會極大增加傳輸開銷。這些開銷降低了系統(tǒng)的吞吐量。此外，車輛的高速移動，對數(shù)據(jù)包傳輸率提出了挑戰(zhàn)。

為此，本文基于單播和無比率編碼的地域性多播路由URC－GR(Unicast and Rateless Coding based Geocast Routing)協(xié)議。URC－GR 協(xié)議仍屬GR 協(xié)議，但是在向目標區(qū)域轉發(fā)數(shù)據(jù)包時不再使用泛洪機制，而是利用AODV 協(xié)議的單播機制，降低路由開銷。同時，為了解決低的數(shù)據(jù)包傳遞率，引用了無比率編碼。當源節(jié)點向目標區(qū)域傳輸數(shù)據(jù)時，就對這些數(shù)據(jù)進行無比率編碼，增加了對不穩(wěn)定路由的魯棒性，提高數(shù)據(jù)包傳輸率。

1 約束條件

提出URC－GR 協(xié)議主要基于以下假設條件:

1)所有車輛均有全球定位系統(tǒng)GPS(Global Positioning System)，車輛知道自己的位置。同時，每個車輛周期性向鄰居車輛廣播beacon 消息;

2)對于無比率編碼，假定產生已編碼數(shù)據(jù)包的數(shù)據(jù)塊足夠大，致使產生完全相同的編碼數(shù)據(jù)包的概率非常小;

3)在目的區(qū)域，至少有一個車輛接收消息;

4)由于消息在目標區(qū)域廣播，如果目標區(qū)域內有一條消息被接收，那么區(qū)域內所有車輛均能接收此消息;

5)車間通信采用DSRC(Dedicated Short Range Communication)標準。

2 URC－GR 協(xié)議

在VANET 的地域性多播路由GR 協(xié)議中，路由開銷和數(shù)據(jù)包傳遞率是兩個非常重要的參數(shù)，特別是當目標區(qū)域遠離源節(jié)點時，保持低開銷和高數(shù)據(jù)包傳遞率是非常具有挑戰(zhàn)性的工作。為此，提出的URC－GR 協(xié)議從兩個方面解決了問題。引用單播的AODV 的路由發(fā)現(xiàn)機制，降低開銷，再利用無比率編碼提高數(shù)據(jù)包傳遞率。

2.1 消息轉發(fā)

為了減少開銷，提出的URC－GR 協(xié)議利用AODV 路由發(fā)現(xiàn)機制，實施向目標區(qū)域的單播傳輸。當源節(jié)點需要向目標區(qū)域傳輸一個數(shù)據(jù)包時，首先利用AODV 路由協(xié)議產生一個路由請求RREQ(Route Request)包，并在網(wǎng)絡內泛洪。RREQ包含有源節(jié)點地址、數(shù)據(jù)包ID 以及目標區(qū)域以及轉發(fā)了RREQ 數(shù)據(jù)包的節(jié)點，如圖1 所示，其中List_Forward 表示轉發(fā)RREQ 包節(jié)點ID。

圖1 RREQ 消息格式

鄰居節(jié)節(jié)點接收了RREQ 包后，首先檢測是否是第一次接收RREQ 包，若是，則自己的ID 號加入List_Forward，否則丟棄RREQ 包。

經(jīng)過多個節(jié)點轉發(fā)，RREQ 包能夠傳遞至目標區(qū)域。當目標區(qū)域內有節(jié)點接收了RREQ 包，就沿著傳輸RREQ 的路徑向源節(jié)點傳遞路由回復RREP(Route Reply)包。如圖2 所示。

圖2 數(shù)據(jù)傳輸路徑的選擇

如圖2a 所示，源節(jié)點先在傳輸范圍內廣播RREQ 包，鄰居節(jié)點接收后，再轉發(fā)，直至目標區(qū)域。一旦目標區(qū)域內有節(jié)點接收了RREQ 包，就沿著傳輸RREQ 包的路徑回復RREP，如圖2b 所示。采用單播機制向源節(jié)點傳輸RREP。一旦接收了RREP，源節(jié)點就沿著傳遞RREP 路徑發(fā)送數(shù)據(jù)包，如圖2c 所示。利用這種方式傳輸數(shù)據(jù)，一旦目標區(qū)域內的某一節(jié)點接收了數(shù)據(jù)包，就在目標區(qū)內泛洪，從而保證目標區(qū)域內所有節(jié)點均能接收到數(shù)據(jù)包。利用這種方式，可降低路由開銷。

2.2 無比率編碼

在VANET 中，車輛的快速移動，導致拓撲動態(tài)變化，降低了數(shù)據(jù)包傳遞率。為此，提出的URC－GR 協(xié)議利用無比率編碼提高數(shù)據(jù)包傳遞率。在容錯編碼中，無比率編碼因易編碼、解碼的特性，被廣泛應用于具有不可預知信道特性的網(wǎng)絡。

無比率編碼是一種特殊信道冗余編碼，其編碼規(guī)則為:將原始數(shù)據(jù)轉換成無限多個不重復編碼的數(shù)據(jù)單元［7］。無比率編碼特性在于:不論接收節(jié)點何時開始接收編碼數(shù)據(jù)單元，其收到的每個數(shù)據(jù)包都是有用的，并且無需考慮接收數(shù)據(jù)單元的順序。此外，無比率編碼不易受網(wǎng)絡帶寬條件的限制而導致部分數(shù)據(jù)包丟失情況的影響［8］。簡之，無比率編碼具有如下特性:1)源節(jié)點無需掌握信道先驗知識;2)接收節(jié)點可以在任何時刻接收，無需考慮所接收的編碼數(shù)據(jù)單元的順序，只要所收集的編碼數(shù)據(jù)單元數(shù)量足夠重構原始信息就行。

無比率編碼原理如圖3 所示。假定源節(jié)點有一消息數(shù)據(jù)F 待傳輸。首先將其劃分成n 個相等尺寸的消息塊(Blocks)B1，B2，…，Bn。然后，對消息塊進行按位異或運算，產生相應的編碼數(shù)據(jù)單元。例如，編碼數(shù)據(jù)單元e2由B1和B2進行異或運算得到，則e2=B1⊕B2，編碼數(shù)據(jù)單元e2的度數(shù)為2。度數(shù)表示參與異或運算的消息塊數(shù)量。經(jīng)過編碼后，原消息數(shù)據(jù)F 就由一系列的編碼數(shù)據(jù)單元構成。這些編碼數(shù)據(jù)單元經(jīng)有損信道傳輸至接收端。接收端接收了這些數(shù)據(jù)單元后，經(jīng)反復迭代運算恢復消息數(shù)據(jù)。

圖3 無比率編碼數(shù)據(jù)原理

無比率編碼的效率η 滿足

其中，ε 取決于具體糾錯編碼。

當接收端接收了K 個編碼數(shù)據(jù)單元，若滿足式(2)便可解碼。

目前流行的無比率編碼有Tornado［8］、LT 編碼等［9］。本文引用LT 編碼。源節(jié)點首先將原始數(shù)據(jù)分成n 個同尺寸的數(shù)據(jù)塊D1，D2，…，Dn。然后編碼器再按預設的“度數(shù)分布”函數(shù)為每個編碼數(shù)據(jù)EDi隨機地產生度數(shù)di。當明確了度數(shù)后，便等概率地從n 個數(shù)據(jù)塊中隨機地選擇di個數(shù)據(jù)塊進行按位求和運算，便可得到第i 個編碼數(shù)據(jù)單元。LT 編碼原理如圖4 所示。

圖4 LT 編碼示意圖

2.3 數(shù)據(jù)傳輸流程

本小節(jié)的數(shù)據(jù)傳輸流程是從接收了編碼數(shù)據(jù)的車輛i 的角度分析。當車輛i 接收了編碼數(shù)據(jù)后，首先檢測是否在目標區(qū)域內，如果是，則存儲編碼數(shù)據(jù)。否則就沿著單播路徑轉發(fā)。然后再檢測存儲的編碼數(shù)據(jù)是否滿足式(2)。若滿足，則解碼，并向源節(jié)點回復ACK 確認消息，同時將解碼后的數(shù)據(jù)在目標區(qū)域內廣播，致使目標區(qū)域內的車輛均能收到消息。若不滿足，則廣播編碼數(shù)據(jù)包，流程圖如圖5 所示。

圖5 數(shù)據(jù)包傳輸流程

3 仿真分析

3.1 仿真環(huán)境及性能指標

利用SUMO(Simulation of Urban Mobility)［10］模擬車輛移動，SUMO 的輸出就是車輛的移動軌跡，然后將SUMO 的輸出作為NS2 的輸入，進而利用NS2 仿真網(wǎng)絡性能。表1 列舉了仿真參數(shù)，仿真區(qū)域面積為2.05 km×1.4 km，由4 條垂直、2條水平方向的雙向車道構成。在每個交叉口設有交通燈。

同時，選擇IVG 和DRG 協(xié)議進行同步仿真，并從數(shù)據(jù)包傳遞率PDR(Packet Delivery Ratio)、路開銷、平均端到端傳輸時延E2E(Average End to End Delay)3 方面分析協(xié)議性能。

表1 仿真參數(shù)

3.2 實驗一

本次實驗考察數(shù)據(jù)包傳輸速率對各性能指標的影響。數(shù)據(jù)包傳輸速率從32 ～512 kbit/s 變化，大小為1 500 byte。

3 個協(xié)議的PDR 變化曲線如圖6 所示。從圖6 可知，提出的URC－GR 協(xié)議的PDR 性能最優(yōu)，分別比IVG 提高了近10%、比DRG 提高了15%。此外，URC－GR 協(xié)議隨數(shù)據(jù)包傳輸速率變化的波動性小，具有穩(wěn)定的數(shù)據(jù)包傳遞率。URCGR 協(xié)議的這些優(yōu)勢歸功于引用了無比率編碼，提高了數(shù)據(jù)傳輸效率。

圖6 數(shù)據(jù)包傳遞率(實驗一)

圖7 分析了3 個協(xié)議的端到端傳輸時延。從圖7 可知，URC－GR 協(xié)議的端到端傳輸時延最低，原因在于URC－GR 協(xié)議在向目標區(qū)域轉發(fā)消息時，并非采用泛洪機制，降低因泛洪而引起的廣播風暴的發(fā)生概率，提高了數(shù)據(jù)傳輸?shù)牧鲿承浴?/p>

3.3 實驗二

本次實驗考查了數(shù)據(jù)包的大小對路由協(xié)議的性能影響。數(shù)據(jù)包大小在500 ～3 000 變化，而數(shù)據(jù)傳輸速率為128 kbit/s。

圖8 描述了數(shù)據(jù)包傳遞率隨數(shù)據(jù)包尺寸的變化曲線。從圖8 可知，URC－GR 協(xié)議的數(shù)據(jù)包傳遞率性能最高，并且隨數(shù)據(jù)包尺寸的變化波動小。而IVG 和DRG 協(xié)議的數(shù)據(jù)包傳遞率隨數(shù)據(jù)包尺寸的增加而下降，這主要因為大的數(shù)據(jù)包是分散傳輸，任一分組數(shù)據(jù)包的傳輸失效，都可能導致整個數(shù)據(jù)包傳輸?shù)氖?。而IVG 和DRG 協(xié)議并沒有數(shù)據(jù)進行容錯編碼。

圖7 平均端到端傳輸時延(實驗一)

圖8 數(shù)據(jù)包傳遞率(實驗二)

最后，分析了IVG 和DRG 以及URC－GR 協(xié)議由端到端傳輸時延，如圖9 所示。從圖9 可知，URC－GR 協(xié)議的端到端傳輸時延并不隨數(shù)據(jù)包尺寸變化的影響，在整個數(shù)據(jù)包尺寸變化區(qū)間，時延均在0.001 s 鄰近。與IVG 和DRG 協(xié)議相比，URC－GR 協(xié)議的端到端傳輸時延性能分別提高了近在3倍、1 倍。

圖9 平均端到端傳輸時延(實驗二)

3.4 實驗三

本次實驗主要考查URC－GR 協(xié)議在路由開銷方面的性能。在仿真區(qū)域內，車輛數(shù)目在25 ～100 變化，數(shù)據(jù)包大小為800 byte，而數(shù)據(jù)傳輸速率為128 kbit/s。仿真結果如圖10所示。

圖10 路由開銷

從圖10 可知，URC－GR 協(xié)議開銷最少，遠低于IVG 和DRG。原因在于URC－GR 協(xié)議在向目標區(qū)域轉發(fā)數(shù)據(jù)包時，沒有采用泛洪，而是利用單播機制。同時，URC－GR 協(xié)議引用無比率編碼，降低了數(shù)據(jù)包重傳概率，減少了控制包的重傳次數(shù)，進而降低了開銷。

4 結論

針對車聯(lián)網(wǎng)VANETs 的地域性多播路由協(xié)議，展開分析，討述了傳統(tǒng)地域性多播路由在路由開銷及數(shù)據(jù)包傳遞率的不足，并提出了URC－GR 協(xié)議。URC－GR 協(xié)議引用了兩個機制解決高的路由開銷以及低的數(shù)據(jù)包傳遞率的不足。首先利用單播機制向目標區(qū)域轉發(fā)數(shù)據(jù)，避免了應泛洪機制而導致額外的路由開銷，其次，利用無比率編碼機制，增加了協(xié)議對不穩(wěn)定鏈路的魯棒性，提高了數(shù)據(jù)包傳遞率。仿真結果表明，提出的URC－GR 協(xié)議能夠有效地降低路由開銷，并提高了數(shù)據(jù)包傳遞率。

［1］THILAGAVATHE V，DURAISWAMY K.Prediction based reliability estimation in MANETs with Weibull nodes［J］.Eur.J.Sci.Res.，2011，64(2):325－329.

［2］SONG C，ZHANG W，ZHANG Y M.Analysis of access and connectivity probabilities in vehicular relay networks［J］.IEEE Trans. Information Forensics and Security，2011，29(1):140－150.

［3］于海寧，張宏莉.VANETs 路由協(xié)議的研究進展［J］.電子學報，2011，39(12):2868－2880.

［4］BACHIR A，BENSLIMANE A. A multicast protocol in ad hoc networks inter－vehicle geocast［C］//Proc.IEEE Vehicular Technology Conference.［S.l.］:IEEE Press，2013:2456－2460.

［5］JOSHI H P.Distributed robust geocast:a multicast protocol for intervehicle communication［J］.IEEE Trans. Information Forensics and Security，2014，29(1):140－150.

［6］趙鑫.P2PI 流媒體內容分發(fā)的關鍵技術研究［D］.北京:北京郵電大學，2010.

［7］葉暉.機會網(wǎng)絡數(shù)據(jù)分發(fā)關鍵技術研究［D］.長沙:中南大學，2010.

［8］JUNG Y H，LI Q C.Short dynamic group signature scheme supporting controllable link ability［J］.IEEE Trans. Information Forensics and Security，2013，32(6):1－14.

［9］STAMPOULIS A，CHAI Z. Survey of security in vehicular networks［J］.Project CPSC 534，2011，2(3):12－20.

［10］KRAJZEWICZ D，ERDMANN J，BEHRISCH M. Recent development and applications of SUMO－simulation of urban mobility［J］.International Journal on Advances in Systems and Measurements，2013，3(5):128－138.