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

從繼成，張韌志

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

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

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

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

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

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

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

1 約束條件

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

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

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

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

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

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

2 URC－GR 協議

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

2.1 消息轉發

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

圖1 RREQ 消息格式

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

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

圖2 數據傳輸路徑的選擇

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

2.2 無比率編碼

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

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

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

圖3 無比率編碼數據原理

無比率編碼的效率η 滿足

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

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

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

圖4 LT 編碼示意圖

2.3 數據傳輸流程

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

圖5 數據包傳輸流程

3 仿真分析

3.1 仿真環境及性能指標

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

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

表1 仿真參數

3.2 實驗一

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

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

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

圖7 分析了3 個協議的端到端傳輸時延。從圖7 可知，URC－GR 協議的端到端傳輸時延最低，原因在于URC－GR 協議在向目標區域轉發消息時，并非采用泛洪機制，降低因泛洪而引起的廣播風暴的發生概率，提高了數據傳輸的流暢性。

3.3 實驗二

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

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

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

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

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

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

3.4 實驗三

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

圖10 路由開銷

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

4 結論

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

［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 路由協議的研究進展［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 流媒體內容分發的關鍵技術研究［D］.北京:北京郵電大學，2010.

［7］葉暉.機會網絡數據分發關鍵技術研究［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.