基于單播和無比率編碼的地域性多播路由協(xié)議

從繼成，張韌志

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

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

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

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

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

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

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

1 約束條件

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

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

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

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

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

5)車間通信采用DSRC(Dedicated Short Range Communication)標(biāo)準(zhǔn)。

2 URC－GR 協(xié)議

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

2.1 消息轉(zhuǎn)發(fā)

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

圖1 RREQ 消息格式

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

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

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

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

2.2 無比率編碼

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

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

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

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

無比率編碼的效率η 滿足

其中，ε 取決于具體糾錯(cuò)編碼。

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

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

圖4 LT 編碼示意圖

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

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

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

3 仿真分析

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

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

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

表1 仿真參數(shù)

3.2 實(shí)驗(yàn)一

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

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

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

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

3.3 實(shí)驗(yàn)二

本次實(shí)驗(yàn)考查了數(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ù)包尺寸的變化波動(dòng)小。而IVG 和DRG 協(xié)議的數(shù)據(jù)包傳遞率隨數(shù)據(jù)包尺寸的增加而下降，這主要因?yàn)榇蟮臄?shù)據(jù)包是分散傳輸，任一分組數(shù)據(jù)包的傳輸失效，都可能導(dǎo)致整個(gè)數(shù)據(jù)包傳輸?shù)氖?。而IVG 和DRG 協(xié)議并沒有數(shù)據(jù)進(jìn)行容錯(cuò)編碼。

圖7 平均端到端傳輸時(shí)延(實(shí)驗(yàn)一)

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

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

圖9 平均端到端傳輸時(shí)延(實(shí)驗(yàn)二)

3.4 實(shí)驗(yàn)三

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

圖10 路由開銷

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

4 結(jié)論

針對車聯(lián)網(wǎng)VANETs 的地域性多播路由協(xié)議，展開分析，討述了傳統(tǒng)地域性多播路由在路由開銷及數(shù)據(jù)包傳遞率的不足，并提出了URC－GR 協(xié)議。URC－GR 協(xié)議引用了兩個(gè)機(jī)制解決高的路由開銷以及低的數(shù)據(jù)包傳遞率的不足。首先利用單播機(jī)制向目標(biāo)區(qū)域轉(zhuǎn)發(fā)數(shù)據(jù)，避免了應(yīng)泛洪機(jī)制而導(dǎo)致額外的路由開銷，其次，利用無比率編碼機(jī)制，增加了協(xié)議對不穩(wěn)定鏈路的魯棒性，提高了數(shù)據(jù)包傳遞率。仿真結(jié)果表明，提出的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ìn)展［J］.電子學(xué)報(bào)，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 流媒體內(nèi)容分發(fā)的關(guān)鍵技術(shù)研究［D］.北京:北京郵電大學(xué)，2010.

［7］葉暉.機(jī)會(huì)網(wǎng)絡(luò)數(shù)據(jù)分發(fā)關(guān)鍵技術(shù)研究［D］.長沙:中南大學(xué)，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.