車載通信網(wǎng)中地理位置路由策略的改進(jìn)方法

馬志欣　劉海英　李鑫　謝顯中

摘要：VANET是一種具有高度移動(dòng)性的無(wú)線ad hoc網(wǎng)絡(luò)，將在公共通信安全和商業(yè)運(yùn)用中扮演重要角色。由于高速變化的拓?fù)浣Y(jié)構(gòu)和車輛的移動(dòng)性，傳統(tǒng)的MANET（mobile AD hoc network）路由協(xié)議無(wú)法完全解決車輛網(wǎng)絡(luò)的這種特殊性問(wèn)題。該文中，我們提出了基于位置路由的貪婪路由算法，即在傳輸距離有限范圍內(nèi)，把轉(zhuǎn)發(fā)節(jié)點(diǎn)到朝著目標(biāo)方向的邊緣節(jié)點(diǎn)作為最適合下一跳來(lái)轉(zhuǎn)發(fā)數(shù)據(jù)包。仿真結(jié)果表明，與現(xiàn)在的VANET路由協(xié)議相比，在數(shù)據(jù)包傳輸中端到端的傳輸時(shí)延大大減小。

關(guān)鍵詞：車載通信網(wǎng)絡(luò)；地理位置路由；貪婪邊界無(wú)狀態(tài)路由GPSR

中圖分類號(hào)：TP 393.09 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）17-4159-05

An Improved Geographic Location Routing Strategy Method in VANET

MA Zhi-xin1， LIU Hai-ying1， LI Xin1， XIE Xian-zhong2

（1.Computer Engineering Department， Changji Institute， Changji 831100， China； 2.Institute of Broadband Access Network， Chongqing University of Posts and Telecommunications， Chongqing 400065， China）

Abstract： VANET is a highly mobile wireless ad hoc networks， and will play an important role in public communication security and commercial use. Due to the high speed change topology and the mobility of vehicles，the traditional MANET （mobile ad-hoc network） routing protocol can not completely solve the special problem of the vehicle network. In this article， we put forward the greedy routing algorithm based on location routing， namely within the scope of the limited transmission distance，the forwarding nodes toward the direction of the target edge nodes as the most suitable for the next jump to forward packets .The simulation results show that compared with the present VANET routing protocols， that end-to-end delay in Data packets transmission is greatly reduced.

Key words： vehicle communication network； Location routing； Greedy Perimeter Stateless Routing

1 概述

Vehicular Ad hoc Network （VANET）是應(yīng)用在短距離道路通信、道路安全以及信息交流。預(yù)計(jì)在不久的將來(lái)更多的車輛將安裝計(jì)算機(jī)和無(wú)線通信設(shè)備。文中假定車輛安裝了無(wú)線通信設(shè)備、GPS、數(shù)字地圖來(lái)報(bào)告車輛的狀態(tài)，車輛與其他車輛和路邊的基礎(chǔ)設(shè)施通信時(shí)要在無(wú)線傳輸范圍之內(nèi)。一個(gè)車輛網(wǎng)絡(luò)是一個(gè)移動(dòng)ad hoc網(wǎng)絡(luò)，它的特點(diǎn)可以高度概括為高動(dòng)態(tài)性、流動(dòng)性約束、移動(dòng)預(yù)測(cè)性、大規(guī)模性和能量性約束不高，因?yàn)槊總€(gè)車輛都有一個(gè)足夠大容量的電池；較高的計(jì)算能力：運(yùn)行車輛可以負(fù)擔(dān)大量計(jì)算、通信和傳感能力。一種可行的VANET 移動(dòng)模型可以使訪真結(jié)果更準(zhǔn)確，在MANET中運(yùn)用的節(jié)點(diǎn)隨機(jī)移動(dòng)模型用來(lái)分析VANET中的路由是不合適的。

2 與VANET相關(guān)的路由協(xié)議

1）MANET的路由協(xié)議

MANET的路由協(xié)議可以根據(jù)屬性分類，可分為主動(dòng)和被動(dòng)。主動(dòng)路由是使用表驅(qū)動(dòng)的方法。它們保留所在網(wǎng)絡(luò)中的路由信息，主要缺點(diǎn)是：未使用的路由信息可能成為可用帶寬的重要組成部分，如果網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化頻繁將不好維護(hù)。被動(dòng)路由是基于實(shí)際需求，它們僅保留現(xiàn)在所使用的路由，從而減少了網(wǎng)絡(luò)的負(fù)荷，在任何時(shí)間，僅保留一小部分高度利用的路由信息。VANET是高動(dòng)態(tài)的，這種被動(dòng)性更符合VANET路由協(xié)議。路由協(xié)議還可以分為基于拓?fù)涞暮突谖恢玫姆桨??；谕負(fù)渎酚蓛H考慮拓?fù)渲械慕Y(jié)點(diǎn)連接，其缺點(diǎn)是延遲大。基于位置路由需要獲得加入結(jié)點(diǎn)的物理位置信息，路由選擇是建立在目的地位置和轉(zhuǎn)發(fā)結(jié)點(diǎn)位置的基礎(chǔ)上的基于位置的路由，不需要路線的建立和維護(hù)。

2） 用于VANET的路由協(xié)議路由算法

GSR（Geographic Source Routing 地理源路由協(xié)議）：是基于位置的路由拓?fù)湫畔⒌?。這種方法應(yīng)用貪婪轉(zhuǎn)發(fā)，沿著事先選定的最短路徑。[1]仿真結(jié)果表明GSR在數(shù)據(jù)包投遞率和延遲方面要優(yōu)于AODV和DSR。但這種方法忽視了在交通密度低時(shí)沒(méi)有足夠結(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包的情況。低交通密度將很難找到一條預(yù)先選定的路徑來(lái)建立端到端的連接。

GPCR（Greedy Perimeter Coordinator Routing 貪婪周邊協(xié)調(diào)員路由）：為了應(yīng)對(duì)城市場(chǎng)景的挑戰(zhàn)，文獻(xiàn)2中采用一個(gè)限制性沿著預(yù)先路徑的貪婪轉(zhuǎn)發(fā)算法，當(dāng)選擇下一跳時(shí)，一個(gè)協(xié)調(diào)員（在路口節(jié)點(diǎn)）是首選的一個(gè)非協(xié)調(diào)員節(jié)點(diǎn)，即使它不是地理上最接近目的地的結(jié)點(diǎn)。GPCR 通過(guò)路口節(jié)點(diǎn)優(yōu)先轉(zhuǎn)發(fā)機(jī)制較好的解決了障礙物引起的信號(hào)屏蔽問(wèn)題，可有效地獲取移動(dòng)節(jié)點(diǎn)更多的當(dāng)前狀態(tài)。和GSR相似，GPCR同樣忽視了低交通密度的情況。

A-STAR（Anchor-based Street and Traffic Aware Routing錨-基于街道與交通感知路由）：為了保證即使在低密度車輛交通網(wǎng)絡(luò)狀況下端到端的連接，Seet.B.C 提出了A-STAR，[3] A-STAR利用城市公交路線信息，以（識(shí)別）確定一個(gè)錨路徑與高連接道路的包交付。通過(guò)使用一個(gè)錨的路徑，A-STAR 確保找到一個(gè)端到端的連接，即使在交通密度低的情況。這個(gè)基于位置的方法也采用了路由恢復(fù)策略，也就是說(shuō)當(dāng)數(shù)據(jù)包路由到局部最大時(shí)計(jì)算新的錨路徑促使局部路徑最優(yōu)。仿真結(jié)果表明：A-STAR與GSR 和 GPSR相比，實(shí)現(xiàn)了網(wǎng)絡(luò)性能的提高。但是，路由路徑可能不是最優(yōu)的，因?yàn)樗劐^路徑結(jié)果導(dǎo)致較大時(shí)延。

MDDV（Mobility-Centric Data Dissemination Algorithm for Vehicular Networks 移動(dòng)為中心的車輛網(wǎng)絡(luò)數(shù)據(jù)傳播算法）：為了實(shí)現(xiàn)可靠和有效的路由，Wu.H 提出了MDDV，[4]結(jié)合機(jī)會(huì)轉(zhuǎn)發(fā)、地理轉(zhuǎn)發(fā)和軌跡的轉(zhuǎn)發(fā)。MDDV考慮到交通密度。指定一個(gè)轉(zhuǎn)發(fā)軌跡從源頭延伸到目的地（軌跡的轉(zhuǎn)發(fā)），消息將被移動(dòng)到地理上更接近的目的地（地理轉(zhuǎn)發(fā)）。轉(zhuǎn)發(fā)軌跡的選擇使用地理信息和交通密度。MDDV假定是靜態(tài)的交通密度。信息的轉(zhuǎn)發(fā)是通過(guò)中間的結(jié)點(diǎn)沿著轉(zhuǎn)發(fā)軌跡存儲(chǔ)轉(zhuǎn)發(fā)信息。如果交通密度按時(shí)間而變化，這個(gè)基于軌跡的轉(zhuǎn)發(fā)將導(dǎo)致大量轉(zhuǎn)發(fā)延遲。

VADD（Vehicle-Assisted Data Delivery 車載輔助數(shù)據(jù)交付）：為了保證在一個(gè)稀疏網(wǎng)絡(luò)中在可容忍時(shí)延范圍內(nèi)的端到終端的連接，文獻(xiàn)5中通過(guò)使用可預(yù)測(cè)的移動(dòng)性稀疏網(wǎng)絡(luò)特點(diǎn)，提出了VADD，基于攜帶和轉(zhuǎn)發(fā)的思想。路由不是沿著預(yù)先選擇的道路，VADD選擇最接近目的的下一跳是基于最高預(yù)先定義的優(yōu)先方向。仿真結(jié)果表明在分組投遞率，數(shù)據(jù)包延遲和交通開(kāi)銷方面VADD優(yōu)于GPSR。這種方法預(yù)測(cè)了車輛的運(yùn)動(dòng)方向。但這不能預(yù)測(cè)未來(lái)環(huán)境的變化。

PDGR（（Predictive Directional Greedy Routing 預(yù)測(cè)定向貪婪路由）：定向貪婪路由轉(zhuǎn)發(fā)數(shù)據(jù)包是基于車輛的位置和移動(dòng)方向。加權(quán)值的計(jì)算就是基于這個(gè)方面的信息，選擇計(jì)算值最高的結(jié)點(diǎn)作為下一跳。如果沒(méi)有可選的最好下一跳，傳送轉(zhuǎn)發(fā)方法也同樣在這個(gè)路由協(xié)議中運(yùn)用。該方法可以降低數(shù)據(jù)包交付的延遲。在文獻(xiàn)6所提出的PDGR協(xié)議中，從當(dāng)前的鄰居和未來(lái)可能的攜帶包的鄰居中計(jì)算出加權(quán)值。 隨著預(yù)測(cè)DGR，下兩跳的結(jié)點(diǎn)的加權(quán)數(shù)提前計(jì)算出來(lái)。這里的下一跳是通過(guò)預(yù)測(cè)完成的，并不是在所有情況下都可靠。由于車輛的高動(dòng)態(tài)性，它不能保證數(shù)據(jù)包在邊緣區(qū)域中被轉(zhuǎn)發(fā)到最適合的下一跳。

文獻(xiàn)[7]為了克服GPSR 由于不受限的貪婪轉(zhuǎn)發(fā)和路網(wǎng)的平面化處理以及因?yàn)槁房诘慕ㄖ镄盘?hào)遮擋和拓?fù)浣Y(jié)構(gòu)的快速變化造成貪婪轉(zhuǎn)發(fā)失敗而轉(zhuǎn)為周邊路由轉(zhuǎn)發(fā)而造成丟包的問(wèn)題。引入交叉路口固定節(jié)點(diǎn)參與路由轉(zhuǎn)發(fā)，但該算法可提高城市場(chǎng)景下的網(wǎng)絡(luò)傳輸性能，沒(méi)有考慮稀疏節(jié)點(diǎn)的路由問(wèn)題。

3 所提出的路由算法

該算法是一個(gè)基于邊緣節(jié)點(diǎn)的貪婪路由算法，有三個(gè)基本功能單元。首先是鄰居節(jié)點(diǎn)標(biāo)識(shí)（NNI）算法，第二是節(jié)點(diǎn)方向識(shí)別（NDI）算法，第三是邊緣節(jié)點(diǎn)選擇算法ENS。NNI算法是負(fù)責(zé)來(lái)收集在任何時(shí)間在傳輸范圍內(nèi)的源結(jié)點(diǎn)或轉(zhuǎn)發(fā)結(jié)點(diǎn)的信息。NDI算法是負(fù)責(zé)確定正在向目的地移動(dòng)的結(jié)點(diǎn)的方向。ENS算法是在有限的傳輸范圍內(nèi)負(fù)責(zé)為某一數(shù)據(jù)包選擇做進(jìn)一步轉(zhuǎn)發(fā)的具體邊緣結(jié)點(diǎn)。假設(shè)所有節(jié)點(diǎn)都配備了GPS接收機(jī)，數(shù)字地圖，可選的傳感器和單元。所有車輛的位置或節(jié)點(diǎn)信息可以借助全球定位系統(tǒng)GPS識(shí)別。唯一可用的通信路線是通過(guò)ad-hoc網(wǎng)絡(luò)，沒(méi)有其他通信基礎(chǔ)設(shè)施。節(jié)點(diǎn)功率不是設(shè)計(jì)的限制因素。通信是面向消息。每個(gè)結(jié)點(diǎn)的最大傳輸范圍是250米。

1）鄰居節(jié)點(diǎn)識(shí)別算法

鄰居節(jié)點(diǎn)標(biāo)識(shí)的過(guò)程，是在一個(gè)汽車/節(jié)點(diǎn)的傳輸范圍內(nèi)確定其目前的鄰居。對(duì)于一個(gè)特定的車輛，在傳輸范圍內(nèi)的其他任何車輛都稱作鄰居。所有車輛都擁有其鄰居的信息。由于所有車輛可能都在移動(dòng)，一個(gè)特定移動(dòng)結(jié)點(diǎn)的鄰居總是在變的。鄰居表是動(dòng)態(tài)的且需要頻繁更新。一般而言，鄰居節(jié)點(diǎn)的識(shí)別是通過(guò)使用周期性信標(biāo)消息實(shí)現(xiàn)的。信標(biāo)消息由節(jié)點(diǎn)ID，節(jié)點(diǎn)位置和時(shí)間戳組成。每個(gè)結(jié)點(diǎn)通過(guò)定期的發(fā)送標(biāo)識(shí)信息來(lái)通知其它結(jié)點(diǎn)自己的存在。

每μ秒發(fā)送一個(gè)信標(biāo)信息來(lái)通知所有在傳輸范圍內(nèi)的源結(jié)點(diǎn)/轉(zhuǎn)發(fā)結(jié)點(diǎn)宣布自己的存在。 接到信標(biāo)信息以后，每個(gè)結(jié)點(diǎn)都會(huì)更新自己的鄰居表。如果一個(gè)結(jié)點(diǎn)位置變化了，那么它將通過(guò)發(fā)送信標(biāo)信號(hào)向所有鄰居更新其位置。如果一個(gè)已知的鄰居，超時(shí)a *μ秒后沒(méi)有收到一信標(biāo)信息（a是一個(gè)結(jié)點(diǎn)允許丟失的信標(biāo)數(shù)）那么這個(gè)鄰居將從鄰居表中刪除。

2）結(jié)點(diǎn)方向識(shí)別算法

在結(jié)點(diǎn)識(shí)別算法中，目前在有限的傳輸范圍內(nèi)的源節(jié)點(diǎn)或包轉(zhuǎn)發(fā)節(jié)點(diǎn)的預(yù)測(cè)數(shù)值（PS）被計(jì)算出來(lái)。計(jì)算出來(lái)的預(yù)測(cè)數(shù)值用來(lái)識(shí)別結(jié)點(diǎn)移動(dòng)方向。擁有最大預(yù)測(cè)數(shù)值的合適邊緣結(jié)點(diǎn)將被考慮是朝向目的地結(jié)點(diǎn)D方向運(yùn)動(dòng)的，是往目的結(jié)點(diǎn)D轉(zhuǎn)發(fā)的下一跳結(jié)點(diǎn)。預(yù)測(cè)數(shù)值通過(guò)以下式子的數(shù)學(xué)模型計(jì)算出來(lái)的。

[psi=ρ×（1-DiDc）+ω×cos（vvll，d）]

式中：psi 表示結(jié)點(diǎn)i的預(yù)測(cè)數(shù)值；ρ、ω是兩個(gè)預(yù)測(cè)因子，ρ+ω=1并且ρ>ω，可以在轉(zhuǎn)發(fā)時(shí)的位置和方向之間權(quán)衡；Di 表示從邊緣結(jié)點(diǎn)i到目的地D的最短距離；Dc表示從數(shù)據(jù)包轉(zhuǎn)發(fā)結(jié)點(diǎn)c到目的地D的最短距離；Di/Dc表示鄰近的下一跳；[vi]表示邊緣結(jié)點(diǎn)i的速度向量；[ll，d]表示邊緣結(jié)點(diǎn)i位置到目的地D的位置的向量；[cos（vl，ll，d）]表示兩個(gè)向量夾角的余弦值。

3）邊緣結(jié)點(diǎn)選擇算法

在邊緣結(jié)點(diǎn)選擇算法中，被選中的邊緣節(jié)點(diǎn)用來(lái)轉(zhuǎn)發(fā)數(shù)據(jù)包。在有限的傳輸范圍RL內(nèi)和其它結(jié)點(diǎn)相比，邊緣結(jié)點(diǎn)是到目的結(jié)點(diǎn)距離最短的結(jié)點(diǎn)。RL被認(rèn)為是在數(shù)據(jù)包傳向邊緣結(jié)點(diǎn)期間避免數(shù)據(jù)丟失的范圍。一個(gè)邊緣節(jié)點(diǎn)負(fù)責(zé)將接收到的數(shù)據(jù)保存到轉(zhuǎn)發(fā)表里，當(dāng)這些結(jié)點(diǎn)有新的鄰居時(shí)稍后轉(zhuǎn)發(fā)。以下的算法的總體目標(biāo)是盡快的轉(zhuǎn)發(fā)數(shù)據(jù)來(lái)最小化端到端的延時(shí)和避免數(shù)據(jù)丟失。

一個(gè)車輛/結(jié)點(diǎn)的最大傳輸距離MTR是250米。有限的傳輸距離要小于250米。有限的傳輸范圍中包括不同的層次：1級(jí)的傳輸范圍RL1=200m；2級(jí)的傳輸范圍RL2=150m；3級(jí)的傳輸范圍RL3=100m；4級(jí)的傳輸范圍RL4=50m，為了便于描述算法，我們做如下約定：

Currentnode=當(dāng)前數(shù)據(jù)包攜帶結(jié)點(diǎn)；Locc=當(dāng)前結(jié)點(diǎn)的位置； [vc]=當(dāng)前結(jié)點(diǎn)的速度矢量；Dest=數(shù)據(jù)包的目的地； Locd =目的地的位置；nextHop=被選為下一跳的結(jié)點(diǎn)；Neighi =第i個(gè)鄰居；

Loci =第i個(gè)鄰居的位置；[vi]=第i個(gè)鄰居的速度矢量；

本算法描述如下：

1. Locc ← 獲取當(dāng)前結(jié)點(diǎn)位置

2. [vc]←獲取當(dāng)前結(jié)點(diǎn)速度

3. Locd←獲取目的結(jié)點(diǎn)位置

4. Dc=距離（Locc，Locd）

5. [lc，d]= Locd - Locc

6. 預(yù)測(cè)數(shù)值ps = ω×cos（[vc]，[lc，d]）

7. 下一跳 = 當(dāng)前結(jié)點(diǎn)

8. For all當(dāng)前結(jié)點(diǎn)的所有鄰居 do

9. Loci ← 獲取位置（第i個(gè)鄰居）

10. [vi] ← 獲取速度（第i個(gè)鄰居）

11. Di=距離（目的結(jié)點(diǎn)，第i個(gè)鄰居節(jié)點(diǎn)）

12. Dci = 距離（當(dāng)前結(jié)點(diǎn)，第i個(gè)鄰居節(jié)點(diǎn)）

13. for all Dci內(nèi)的當(dāng)前所有鄰居結(jié)點(diǎn)

14. if （Dci< RL1 and Dci> RL2）

15. [ll，d]= Locd — Loci

16. PSi=ρ×（1-Di/Dc）+cos（[vi]，[ll，d]）

17. For 有著更高的預(yù)測(cè)數(shù)值的第i個(gè)鄰居 do

18. PS = PSi

19. 下一跳=第i個(gè)鄰居

20. end for

21. else if （Dci< RL2 and Dci> RL3）

22. [ll，d]= Locd — Loci

23. PSi=ρ×（1-Di/Dc）+cos（[vi]，[ll，d]）

24. For 有著更高的預(yù)測(cè)數(shù)值的第i個(gè)鄰居 do

25. PS = PSi

26. 下一跳=第i個(gè)鄰居

27. end for

28. else if （Dci< RL3 and Dci> RL4）

29. [ll，d]= Locd — Loci

30. PSi=ρ×（1-Di/Dc）+cos（[vi]，[ll，d]）

31. For 有著更高的預(yù)測(cè)數(shù)值的第i個(gè)鄰居 do

32. PS = PSi

33. 下一跳=第i個(gè)鄰居

34. end for

35. else if （Dci< RL4）

36. [ll，d]= Locd — Loci

37. PSi=ρ×（1-Di/Dc）+cos（[vi]，[ll，d]）

38. For 有著更高的預(yù)測(cè)數(shù)值的第i個(gè)鄰居 do

39. PS = PSi

40. 下一跳=第i個(gè)鄰居

41 end for

42. else

43. 數(shù)據(jù)包→當(dāng)前節(jié)點(diǎn)

44. end if

45. end for

46 end for

距離當(dāng)前結(jié)點(diǎn)距離150米到200米的鄰居結(jié)點(diǎn)在RL1 和 RL2之間。所有在RL1 和 RL2傳輸距離之間的結(jié)點(diǎn)的預(yù)測(cè)數(shù)值（PS）被計(jì)算出來(lái)。擁有預(yù)測(cè)數(shù)值最高的結(jié)點(diǎn)被認(rèn)為是RL1的邊緣結(jié)點(diǎn)。所以數(shù)據(jù)包從當(dāng)前結(jié)點(diǎn)轉(zhuǎn)發(fā)到那個(gè)指定的邊緣結(jié)點(diǎn)。如果在 RL1 和 RL2之間沒(méi)有結(jié)點(diǎn)，那么就考慮RL2和RL3之間。

距離當(dāng)前結(jié)點(diǎn)距離150米到100米的鄰居結(jié)點(diǎn)在RL2 和 RL3之間。所有在RL2 和 RL3傳輸距離之間的結(jié)點(diǎn)的預(yù)測(cè)數(shù)值（PS）被計(jì)算出來(lái)。擁有預(yù)測(cè)數(shù)值最高的結(jié)點(diǎn)被認(rèn)為是RL2的邊緣結(jié)點(diǎn)。所以數(shù)據(jù)包從當(dāng)前結(jié)點(diǎn)轉(zhuǎn)發(fā)到那個(gè)指定的邊緣結(jié)點(diǎn)。如果在 RL2 和 RL3之間沒(méi)有結(jié)點(diǎn)，那么就考慮RL3和RL4之間。

距離當(dāng)前結(jié)點(diǎn)距離50米到100米的鄰居結(jié)點(diǎn)在RL3 和 RL4之間。所有在RL3 和 RL4傳輸距離之間的結(jié)點(diǎn)的預(yù)測(cè)數(shù)值（PS）被計(jì)算出來(lái)。擁有預(yù)測(cè)數(shù)值最高的結(jié)點(diǎn)被認(rèn)為是RL3的邊緣結(jié)點(diǎn)。所以數(shù)據(jù)包從當(dāng)前結(jié)點(diǎn)轉(zhuǎn)發(fā)到那個(gè)指定的邊緣結(jié)點(diǎn)。如果在 RL3 和 RL4之間沒(méi)有結(jié)點(diǎn)，那么就考慮RL4。

距離當(dāng)前結(jié)點(diǎn)距離在50內(nèi)的鄰居結(jié)點(diǎn)落在RL4里。所有在RL4傳輸距離內(nèi)的結(jié)點(diǎn)的預(yù)測(cè)數(shù)值（PS）被計(jì)算出來(lái)。擁有預(yù)測(cè)數(shù)值最高的結(jié)點(diǎn)被認(rèn)為是RL4的邊緣結(jié)點(diǎn)。所以數(shù)據(jù)包從當(dāng)前結(jié)點(diǎn)轉(zhuǎn)發(fā)到那個(gè)指定的邊緣結(jié)點(diǎn)。如果在RL4內(nèi)沒(méi)有結(jié)點(diǎn)，那么數(shù)據(jù)包就由當(dāng)前結(jié)點(diǎn)攜帶。如果在以上提到的范圍內(nèi)都沒(méi)有結(jié)點(diǎn)，那么當(dāng)前結(jié)點(diǎn)就把數(shù)據(jù)包儲(chǔ)存起來(lái)直到它發(fā)現(xiàn)傳輸范圍內(nèi)的其他結(jié)點(diǎn)。

4 仿真結(jié)果及分析

在前述的路由協(xié)議中，我們選擇GPSR，PDGR和本文所提出的協(xié)議作比較，使用曼哈頓移動(dòng)模型來(lái)模擬移動(dòng)在街道或在地圖中定義配備了GPS的車輛的運(yùn)動(dòng)模式。道路是由一些橫向和縱向組成的高速公路，該移動(dòng)節(jié)點(diǎn)可以沿著橫向和縱向的街道網(wǎng)格移動(dòng)。在一個(gè)水平和垂直路口，車輛可左轉(zhuǎn)，右轉(zhuǎn)或以一定的概率直行，直行的概率5%，左、右行概率各占0.25%。仿真使用NCTUns 5.0網(wǎng)絡(luò)模擬器。通過(guò)改變節(jié)點(diǎn)的數(shù)目進(jìn)行仿真。

NCTUns 5.0是一個(gè)網(wǎng)絡(luò)仿真器，[8]它包括提供交通車輛的仿真，是開(kāi)源的并在Linux上運(yùn)行。它能直接使用Linux的TCP / IP協(xié)議簇，確保高保真的模擬結(jié)果。現(xiàn)在的5.0版本中可實(shí)現(xiàn)IEEE 802.11p標(biāo)準(zhǔn)定義的無(wú)線車載自組織網(wǎng)絡(luò)。它可以直接使用UNIX應(yīng)用程序作為通信量發(fā)生器。能使用UNIX網(wǎng)絡(luò)測(cè)試和監(jiān)控工具，節(jié)約實(shí)驗(yàn)時(shí)間。利用圖形用戶界面（GUI）完成網(wǎng)絡(luò)拓?fù)錁?gòu)建，GUI支持所期望的路網(wǎng)構(gòu)建、可將道路信息存儲(chǔ)在路網(wǎng)文件中；車輛的運(yùn)動(dòng)通過(guò)設(shè)置車輛的移動(dòng)和與存儲(chǔ)在節(jié)點(diǎn)運(yùn)動(dòng)場(chǎng)景配置文件中有關(guān)信息來(lái)控制。針對(duì)不同數(shù)量的節(jié)點(diǎn)與特定的參數(shù)對(duì)每個(gè)路由協(xié)議進(jìn)行了仿真。介質(zhì)訪問(wèn)控制協(xié)議采用IEEE 802.11DCF。如表1所示仿真進(jìn)行了70秒。數(shù)據(jù)包大小固定為512字節(jié)。最初的節(jié)點(diǎn)被放置在某些特定地點(diǎn)，然后結(jié)點(diǎn)以不同的速度移向新的位置。節(jié)點(diǎn)移動(dòng)的速度從5至25米/秒。仿真參數(shù)具體見(jiàn)表1。

表1 仿真參數(shù)

[參數(shù)＼&量值＼&仿真場(chǎng)景＼&1000m * 1000m＼&車輛數(shù)目＼&0 - 120＼&車輛的平均車速（米/秒）＼&5-25＼&傳輸范圍＼&250米＼&恒定比特率（包/秒）＼&2＼&數(shù)據(jù)包大?。ㄗ止?jié)）＼&512＼&車輛信標(biāo)間隔（秒）＼&0.25 0.50 1.0＼&MAC協(xié)議＼&802.11 DCF＼&車輛移動(dòng)模型＼&曼哈頓移動(dòng)模型＼&]

我們采用端到端的延遲來(lái)評(píng)價(jià)車載通信網(wǎng)路由協(xié)議性能。端到端延遲表示從源節(jié)點(diǎn)發(fā)送數(shù)據(jù)包到目的地收到所經(jīng)歷的時(shí)間。如圖1 所示，節(jié)點(diǎn)的數(shù)量隨著固定CBR率而變化。開(kāi)始時(shí)端到端延遲是在所有路由方案中都比較大。這主要是由于較低的分組遞交率。當(dāng)有更多的網(wǎng)絡(luò)節(jié)點(diǎn)，數(shù)據(jù)包投遞率增加了，并且端到端的延遲也越來(lái)越小。GPSR的終端到端到的時(shí)延比其它協(xié)議要大的多。當(dāng)沒(méi)有可用的節(jié)點(diǎn)時(shí)，GPSR切換到周邊模式，它增加了數(shù)據(jù)包的傳輸時(shí)延。當(dāng)結(jié)點(diǎn)多時(shí)，與GPSR相比，PDGR端到端的延遲相對(duì)要小。這是因?yàn)楫?dāng)有更多的節(jié)點(diǎn)存在時(shí)更容易轉(zhuǎn)發(fā)數(shù)據(jù)包，而下一跳的選擇是預(yù)測(cè)而得，并沒(méi)有在所有情況下都可靠。當(dāng)車輛密度足夠高（n=120）本算法協(xié)議的端至端延遲相對(duì)于PDGR要小。更多的網(wǎng)絡(luò)節(jié)點(diǎn)將提供更多的機(jī)會(huì)找到一些合適的結(jié)點(diǎn)，更高效的轉(zhuǎn)發(fā)數(shù)據(jù)包。隨著結(jié)點(diǎn)群密度增高，與 PDGR 和GPSR相比，所提出的協(xié)議（modified）傳輸延遲大大減小了。

5 總結(jié)

在本文中，首先總結(jié)研究了基于地理位置的VANET的路由問(wèn)題。提出了一個(gè)新的基于地理位置的貪婪路由方法。仿真結(jié)果表明在減少端到端的數(shù)據(jù)包的傳輸時(shí)延方面，所提出的路由算法優(yōu)于其他的路由協(xié)議。今后的工作需要進(jìn)一步考慮城市環(huán)境特點(diǎn)和車輛的分布情況，使改進(jìn)的算法更適合于車載通信網(wǎng)。

參考文獻(xiàn)：

[1] C. Lochert，H. Hartenstein，J. Tian，D. Herrmann，H. Fubler，M. Mauve.A Routing Strategy for Vehicular Ad Hoc Networks in City Environments[J].IEEE Intelligent Vehicles Symposium （IV2003）.

[2] C. Lochert，M. Mauve，H. Fler，H. Hartenstein.Geographic Routing in City Scenarios[J].ACM SIGMOBILE Mobile Computing and Communications Review （MC2R），2005，9（1）：69–72.

[3] B.-C. Seet，G. Liu， B.-S. Lee， C. H. Foh， K. J. Wong， K.-K. Lee.ASTAR： A Mobile Ad Hoc Routing Strategy for Metropolis Vehicular Communications[J].NETWORKING，2004.

[4] H. Wu， R. Fujimoto，R. Guensler and M. Hunter.MDDV： A Mobility-Centric Data Dissemination Algorithm for Vehicular Networks[J].ACM VANET，2004-10-01：47-56.

[5] J. Zhao and G. Cao.VADD： Vehicle-Assisted Data Delivery in Vehicular Ad Hoc Networks[J].Vehicular Technology， May 2008，57（3）：1910-1922.

[6] Jiayu Gong，Cheng-Zhong Xu and James Holle.Predictive Directional Greedy Routing in Vehicular Ad hoc Networks[J].Distributed Computing Systems Workshops，2007.ICDCSW '07. 27th International Conference on.

[7] 鄭敏，沈永增，張先平.一種城市環(huán)境下的地理位置路由策略改進(jìn)方法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2013，22（9）.

[8] 王雷.NCTUns：一種新的網(wǎng)絡(luò)模擬技術(shù)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2008，18（7）：80-82.