湯星峰，徐卿欽，馬世緯

（移動通信技術(shù)重慶市市級重點(diǎn)實(shí)驗(yàn)室（重慶郵電大學(xué)通信與信息工程學(xué)院），重慶 400065）

（?通信作者電子郵箱S170101085@stu.cqupt.edu.cn）

0 引言

車載自組網(wǎng)（Vehicular Ad-hoc NETwork，VANET）是一種新興技術(shù)，它將新一代無線網(wǎng)絡(luò)集成到車輛中，旨在實(shí)現(xiàn)車輛之間的通信，以改善道路安全和提供必要的服務(wù)［1］。車載自組網(wǎng)作為一種特殊的移動自組網(wǎng)，在智能交通和智慧城市的發(fā)展中發(fā)揮著重要的作用［2］。車載自組網(wǎng)主要包含兩種類型的應(yīng)用：安全預(yù)警和娛樂服務(wù)。安全預(yù)警消息，比如碰撞警告、前車變速預(yù)警等，是以廣播的形式進(jìn)行傳播，對時延有很高的要求。而娛樂服務(wù)，比如文件共享、對特定路段的視頻請求等，是通過多跳單播路由來實(shí)現(xiàn)的，具有一定的時延容忍特性。本文所提出的算法是應(yīng)用在車輛間娛樂服務(wù)的多跳單播路由中。

在車載自組網(wǎng)多跳單播路由算法中，基于地理位置轉(zhuǎn)發(fā)的路由算法在車載自組網(wǎng)環(huán)境中具有更好的性能。文獻(xiàn)［3-5］通過預(yù)測車輛的運(yùn)動以及設(shè)定路口中繼車輛的方式來轉(zhuǎn)發(fā)數(shù)據(jù)包，雖然減小了車輛間鏈路的斷開概率，但在頻繁變化的拓?fù)渲?，通過預(yù)測的方式選擇下一跳轉(zhuǎn)發(fā)車輛具有較高的計算復(fù)雜度，對數(shù)據(jù)包的傳輸時延也有較大的影響。文獻(xiàn)［6-8］中將車輛速度、密度等作為參數(shù)，計算出各個路段的權(quán)重值。結(jié)合地理信息和城市拓?fù)?，使用Dijkstra算法計算從源車輛到目的車輛的最短路徑，然后使用貪婪轉(zhuǎn)發(fā)的方式將數(shù)據(jù)包發(fā)送到目的車輛。雖然算法中考慮了城市車輛的密度，避免數(shù)據(jù)包在車輛稀疏的道路中傳輸，但這類算法沒有考慮車輛密度變化的實(shí)時性，缺少對道路中車輛密度的實(shí)時反饋。文獻(xiàn)［9-10］提出了車輛與車輛和車輛與路邊單元的混合路由方式，車輛通過路邊單元轉(zhuǎn)發(fā)能很好地適應(yīng)車輛拓?fù)涞淖兓?，降低發(fā)送時延，但路邊單元的部署和成本問題以及可擴(kuò)展性問題是該路由算法的難點(diǎn)。

為了提高數(shù)據(jù)包的到達(dá)率，降低數(shù)據(jù)包端到端時延。本文在以上研究成果的基礎(chǔ)上提出了基于路徑探索的車載自組網(wǎng)貪婪路由算法（Vehicular ad-hoc network Greedy routing algorithm based on Path Exploration，VGPE）。本文所提算法將數(shù)據(jù)路由分為路徑探索和限制貪婪轉(zhuǎn)發(fā)兩個過程，充分考慮城市環(huán)境的特殊性，在快速變換的車輛拓?fù)浣Y(jié)構(gòu)中具有很好的適應(yīng)性和可擴(kuò)展性。

本文的主要工作如下：1）結(jié)合數(shù)字地圖規(guī)劃出的多條路由路徑，提出了基于人工蜂群算法的路徑探索策略，以找到時延最小的路由路徑轉(zhuǎn)發(fā)數(shù)據(jù)包。2）在車輛的信標(biāo)消息中加入速度、車輛所在路段ID 等字段，以便在選擇轉(zhuǎn)發(fā)車輛時能確保數(shù)據(jù)傳輸穩(wěn)定，且使得整個路由跳數(shù)最少。3）在貪婪轉(zhuǎn)發(fā)數(shù)據(jù)包時使用限制性策略，避免數(shù)據(jù)包轉(zhuǎn)發(fā)到陷入路由空洞的車輛。

1 問題引出

在介紹本文路由算法之前，先對城市道路中的車輛作如下假設(shè)：

1）城市道路上的每輛車都安裝了全球定位系統(tǒng)（Global Positioning System，GPS）導(dǎo)航系統(tǒng)和所在城市的數(shù)字地圖，車輛可以通過GPS和數(shù)字地圖獲得當(dāng)前車輛所在道路的編號和位置坐標(biāo)。

2）車輛之間的傳輸信號無法穿過城市道路兩邊的建筑物，所以不同道路上的車輛想要傳輸信息必須通過在交叉路口車輛的轉(zhuǎn)發(fā)。

3）不同類型的車輛，比如出租車、公交車、大貨車等在轉(zhuǎn)發(fā)數(shù)據(jù)時都不作區(qū)分，擁有相同的轉(zhuǎn)發(fā)半徑、數(shù)據(jù)發(fā)送速率等參數(shù)。

車輛在城市中以基于地理位置的貪婪方式轉(zhuǎn)發(fā)數(shù)據(jù)包時，可能會形成如圖1中所示的情況。源車輛S根據(jù)貪婪轉(zhuǎn)發(fā)的方式將數(shù)據(jù)包發(fā)送給在源車輛S 通信范圍內(nèi)離目的車輛D最近的車輛A。而車輛A 在以相同的方式轉(zhuǎn)發(fā)數(shù)據(jù)包時，因?yàn)榈缆穬蛇吔ㄖ锏恼趽?，車輛A 接收不到車輛E 的位置消息，在車輛A 的鄰居列表中車輛B 離目的車輛D 最近，所以車輛A 將數(shù)據(jù)包發(fā)送給車輛B。但車輛B 所在的路段中的車輛無法將數(shù)據(jù)包轉(zhuǎn)發(fā)給目的車輛，且車輛B 所在路段中的車輛與目的車輛的距離都比車輛B 與目的車輛的距離大，所以數(shù)據(jù)的發(fā)送會進(jìn)入恢復(fù)模式。根據(jù)恢復(fù)模式的規(guī)則，車輛B 會把數(shù)據(jù)發(fā)送給車輛C，車輛C 再把數(shù)據(jù)發(fā)送給車輛E，車輛E與目的車輛的距離小于車輛B，從而繼續(xù)貪婪轉(zhuǎn)發(fā)。由此可以看出，基于地理位置的貪婪路由算法可能因城市場景的特殊性，無法將數(shù)據(jù)發(fā)送到正確的路徑上，從而造成路由跳數(shù)的增多，增大了數(shù)據(jù)路由的時延和丟包率。

在城市場景中使用基于地理位置的貪婪方式轉(zhuǎn)發(fā)數(shù)據(jù)包時，最短路徑并不一定就是最優(yōu)路徑，有可能在最短路徑上車輛稀疏，連接性不好，路由時延和丟包率反而更大。因此本文先使用人工蜂群算法對數(shù)據(jù)包路由路徑進(jìn)行探索，再對數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)。

圖1 貪婪轉(zhuǎn)發(fā)局限性示意圖Fig.1 Schematic diagram of greedy forwarding limitation

2 基于人工蜂群算法的路由路徑探索策略

2.1 人工蜂群算法介紹

人工蜂群（Artificial Bee Colony，ABC）算法是一種模仿蜜蜂采蜜的群智能優(yōu)化算法［11］。人工蜂群算法初始化后包含三個階段：雇傭蜂階段、跟隨蜂階段和偵查蜂階段。

1）雇傭蜂階段。在雇傭蜂階段，雇傭蜂通過式（1）來尋找蜜源［12］。

其中：φ是在[-1，1]中取值的隨機(jī)數(shù)；xij是初始化時產(chǎn)生的蜜源，xkj代表在初始蜜源中與xij不相等的蜜源，i代表蜜源的編號，j代表蜜源的維度。一個蜜源就表示一個解。在雇傭蜂找到新的蜜源后，比較vij和xij適應(yīng)度的值，選擇具有更優(yōu)適應(yīng)度值的蜜源作為本次尋找的結(jié)果。適應(yīng)度的值為蜜源花粉的數(shù)量。

2）跟隨蜂階段。在雇傭蜂確定要開采蜜源后，雇傭蜂返回蜂巢通過舞蹈分享蜜源信息。跟隨蜂采用輪盤賭的方法選擇雇傭蜂所找到的蜜源來開采。輪盤賭的方法是：通過（其中fiti是蜜源i的適應(yīng)度的值，N是初始化時蜜源的個數(shù)）所得出的數(shù)比在［0，1］產(chǎn)生的一個均勻分布的隨機(jī)數(shù)大，則跟隨蜂就去開采這個雇傭蜂所找的蜜源，否則不開采。

3）偵查蜂階段。在搜索過程中，如果一個蜜源經(jīng)過多次迭代，在達(dá)到閾值limit前沒有找到更優(yōu)適應(yīng)度值的蜜源，則這個蜜源將會被拋棄，雇傭蜂將會變成偵查蜂，通過式（2）產(chǎn)生一個新的蜜源來代替被拋棄的蜜源。

其中，xmin_j和xmax_j分別表示解中第j維的最小值和最大值。

2.2 人工蜂群算法在路由路徑探索中的應(yīng)用

將人工蜂群算法查找最優(yōu)值的過程應(yīng)用在車載自組網(wǎng)數(shù)據(jù)路由路徑探索中，以應(yīng)對城市環(huán)境中車輛拓?fù)涞目焖僮兓?。在城市環(huán)境中，把一條從源車輛到目的車輛的路由路徑作為人工蜂群算法中的一個蜜源，人工蜂群算法的每次迭代都要找出所有蜜源中適應(yīng)度值最大的蜜源作為跟隨蜂的開采蜜源，也就是數(shù)據(jù)包轉(zhuǎn)發(fā)的路徑。而適應(yīng)度的值就是雇傭蜂發(fā)現(xiàn)的蜜源的花粉數(shù)量，在本文中就是探測包在各個路徑上的傳輸時延，傳輸時延越少說明適應(yīng)度的值越大。適應(yīng)度的值如式（3）所示：

其中，τSD是探測包從源車輛通過路徑中車輛的多跳轉(zhuǎn)發(fā)到達(dá)目的車輛的時延。

步驟一 初始化階段。在初始化階段要確定蜜源的個數(shù)，即備選路徑集。如圖2 所示，圖中In是各個路口的編號。當(dāng)源車輛響應(yīng)目的車輛的數(shù)據(jù)請求，向目的車輛發(fā)送數(shù)據(jù)包之前，源車輛先通過車載的城市道路的數(shù)字地圖，找到經(jīng)過最少路口數(shù)到達(dá)目的車輛的路徑，在圖2 中，就是最短路徑L1。本文規(guī)定，從源車輛到目的車輛的路徑中，只要經(jīng)過的路口數(shù)小于等于最短路徑路口數(shù)的2 倍，都加入車輛發(fā)送路徑探索包的備選路徑集中，在圖2 中就有路徑L2、L3，從而路徑集｛L1，L2，L3｝就是初始化的蜜源集。

圖2 路徑探索示意圖Fig.2 Schematic diagram of path exploration

步驟二 雇傭蜂階段。源車輛分別向初始化階段所產(chǎn)生的路徑集中的所有路徑發(fā)送路徑探索消息（Routing Path Exploration Message，RPEM），即雇傭蜂。路由路徑探索消息的格式如圖3所示。

圖3 路徑探索消息格式Fig.3 Path exploration message format

1）類型：表示不同的數(shù)據(jù)包類型。其值為1 時，表示路徑探索包；值為2時，表示目的車輛回復(fù)包。

2）路徑條數(shù)：記錄初始化時路徑集中的路徑條數(shù)，也就是探索包的發(fā)送個數(shù)，以便目的車輛對接收到的探索包個數(shù)進(jìn)行驗(yàn)證。

3）所要經(jīng)過路段的ID 序列：規(guī)定路徑探索包所要經(jīng)過路段的ID序列，包括源車輛和目的車輛所在路段。

4）探索包發(fā)送時間：記錄探索包發(fā)送時間，以便在探索包到達(dá)目的車輛后計算路徑的傳輸時延。

5）多跳轉(zhuǎn)發(fā)跳數(shù)計數(shù)器：記錄探索包從源車輛到目的車輛被轉(zhuǎn)發(fā)的跳數(shù)。

路由路徑探索消息通過第3 章中的限制性貪婪路由策略以多跳的形式轉(zhuǎn)發(fā)到目的車輛。當(dāng)目的車輛收到源車輛的路徑探索消息時，比較各個路徑探索消息的適應(yīng)度值，適應(yīng)度越大說明這條路徑連接性越好、時延越少，因此目的車輛按具有最大適應(yīng)度值的路徑向源車輛回送一個應(yīng)答消息（Routing Path Exploration Response Message，RPERM）。應(yīng)答消息的格式如圖3 中所示，和路徑探索消息的格式一樣，只不過在應(yīng)答消息中類型值為2，所經(jīng)過的路段ID 序列為所選定的路徑中各路段的ID號。

步驟三 跟隨蜂階段，即數(shù)據(jù)發(fā)送階段。當(dāng)源車輛接收到目的車輛的應(yīng)答消息后，記錄選定路徑的轉(zhuǎn)發(fā)時延，即蜜源適應(yīng)度的值，將路徑的路段ID 序列寫入數(shù)據(jù)包的包頭，發(fā)送數(shù)據(jù)包。數(shù)據(jù)包就會根據(jù)選定的路徑通過多跳的方式轉(zhuǎn)發(fā)數(shù)據(jù)包。

步驟四 偵查蜂階段。當(dāng)目的車輛每次收到數(shù)據(jù)包后都會通過所選路徑向源車輛發(fā)送應(yīng)答消息。源車輛收到應(yīng)答消息后計算適應(yīng)度的值，當(dāng)有其他路徑適應(yīng)度的值連續(xù)三次大于當(dāng)前路徑適應(yīng)度的值時，將適應(yīng)度值最大的路徑中各路段的ID 寫入數(shù)據(jù)包頭部，切換數(shù)據(jù)包轉(zhuǎn)發(fā)路徑，以適應(yīng)路徑中車輛拓?fù)涞淖兓?/p>

3 車輛間消息轉(zhuǎn)發(fā)的限制性貪婪轉(zhuǎn)發(fā)策略

3.1 車輛間的信標(biāo)消息

在傳統(tǒng)的貪婪周邊無狀態(tài)路由（Greedy Perimeter Stateless Routing，GPSR）協(xié)議中，車輛間的信標(biāo)消息是用來交換位置信息的。在本文算法中，給車輛間的信標(biāo)消息增加了幾個字段，以傳遞更多有用的信息。信標(biāo)消息的格式如圖4所示。

圖4 信標(biāo)消息的格式Fig.4 Beacon message format

1）車輛的行駛方向：表示為一個路口號對（車輛駛離的路口號，車輛駛向的路口號）。

2）車輛所在路段的ID：可以結(jié)合車輛上的數(shù)字地圖和GPS定位來獲得，如果車輛在交叉路口上，則車輛所在路段的ID就是車輛所在交叉路口的編號。

3）車輛是否在交叉路口處：如果是，值為1；如果不是，值為0。當(dāng)車輛在路段上行駛時，由于城市兩邊建筑的限制，車輛不能接收到其他路段上車輛的信標(biāo)消息。當(dāng)車輛接收到的信標(biāo)消息中，路段ID數(shù)大于等于3時，說明車輛處在交叉路口上，則將信標(biāo)消息的這個字段置為1。

4）在相同/相反行駛方向上車輛是否有下一跳：是為了避免將數(shù)據(jù)包發(fā)送給陷入路由空洞的車輛。

3.2 數(shù)據(jù)包的限制性貪婪轉(zhuǎn)發(fā)

數(shù)據(jù)包的限制性貪婪轉(zhuǎn)發(fā)優(yōu)化了基于地理位置貪婪轉(zhuǎn)發(fā)中的三個問題。

3.2.1 優(yōu)化問題一

如圖5 所示，傳統(tǒng)的基于地理位置的貪婪轉(zhuǎn)發(fā)路由協(xié)議，每次轉(zhuǎn)發(fā)都是以離目的車輛最近的鄰居車輛作為下一跳轉(zhuǎn)發(fā)車輛，這樣容易將數(shù)據(jù)包發(fā)送給陷入路由空洞的車輛，從而進(jìn)入恢復(fù)模式，增加了路由的跳數(shù)。

為了解決這個問題，本文在車輛的信標(biāo)消息中加入了“在相同/相反行駛方向上車輛是否有下一跳”這樣兩個字段。在車輛轉(zhuǎn)發(fā)數(shù)據(jù)包之前，先查看收到的鄰居車輛的信標(biāo)消息中這兩個字段是否都等于1，只有在這兩個字段的值都為1 時，才能確定要轉(zhuǎn)發(fā)的下一跳車輛沒有陷入路由空洞中，從而將數(shù)據(jù)包轉(zhuǎn)發(fā)給選定的下一跳車輛。從圖5 中可以看出，因?yàn)樵谲囕vC 的鄰居中沒有比車輛C 更接近目的車輛D 的下一跳車輛，所以車輛C 的是否有下一跳車輛這個字段置0，從而車輛S 就不會因?yàn)檐囕vC 距離目的車輛更近而把數(shù)據(jù)包發(fā)送給車輛C，而是把數(shù)據(jù)包發(fā)送給下一跳車輛字段置1 的車輛B。所以在數(shù)據(jù)每次轉(zhuǎn)發(fā)時并不是以離目的車輛最近作為轉(zhuǎn)發(fā)車輛選擇標(biāo)準(zhǔn)，還要借助“在相同/相反行駛方向上車輛是否有下一跳”這兩個字段進(jìn)行篩選。

圖5 傳統(tǒng)貪婪轉(zhuǎn)發(fā)Fig.5 Traditional greedy forwarding

3.2.2 優(yōu)化問題二

由于城市道路中車輛的高度動態(tài)性，所以在傳輸數(shù)據(jù)的過程中，接收車輛可能離開發(fā)送車輛的傳輸范圍造成鏈路中斷，導(dǎo)致數(shù)據(jù)傳輸失敗。

為了盡量避免車輛在傳輸數(shù)據(jù)時鏈路斷開，在數(shù)據(jù)傳輸方向上滿足下一跳車輛字段為1 的鄰居車輛中，本文使用信標(biāo)消息中的車輛速度字段記錄的車輛實(shí)時速度計算出每一個鄰居車輛與數(shù)據(jù)包攜帶車輛的速度差，從而計算出接收車輛和鄰居車輛的鏈路連接時間，也稱為連接窗口時間。如果在鄰居車輛中有窗口時間大于數(shù)據(jù)包發(fā)送時間的鄰居車輛，就在這些鄰居車輛中選擇擁有最小的窗口時間的車輛作為轉(zhuǎn)發(fā)車輛；如果鄰居車輛的窗口時間都是小于數(shù)據(jù)包發(fā)送時間的，就選擇擁有最大窗口時間的鄰居車輛作為轉(zhuǎn)發(fā)車輛。當(dāng)接收車輛和發(fā)送車輛之間的距離越來越大時，車輛之間鏈路連接時間Tlink的計算式如式（4）所示。

式中：Sni，ni+1為發(fā)送車輛ni和接收車輛ni+1之間的距離；250是指設(shè)定的車輛的通信半徑為250 m；Vni和Vni+1分別是發(fā)送車輛ni和接收車輛ni+1的速度。表示發(fā)送車輛ni和接收車輛ni+1的速度方向相同，表示發(fā)送車輛ni和接收車輛ni+1的速度方向相反。

如果接收車輛和發(fā)送車輛之間的距離越來越小時，就認(rèn)為車輛之間鏈路的連接時間Tlink為∞。

數(shù)據(jù)包的發(fā)送時間tdata由式（5）計算得出。

式中：xdata表示數(shù)據(jù)包的大??；vdata表示數(shù)據(jù)包的發(fā)送速率；αt表示數(shù)據(jù)發(fā)送時的排隊(duì)時延；γt是信道爭用時間。

3.2.3 優(yōu)化問題三

在城市環(huán)境中，當(dāng)數(shù)據(jù)包轉(zhuǎn)發(fā)到交叉路口附近時，因?yàn)榈缆穬膳缘慕ㄖ锏恼趽?，發(fā)送車輛的鄰居表中可能沒有要轉(zhuǎn)發(fā)道路上的下一跳車輛，所以一般的解決方法是以交叉路口的車輛作為中轉(zhuǎn)車輛，進(jìn)行數(shù)據(jù)包的轉(zhuǎn)發(fā)；但這樣可能會增加整個路由的轉(zhuǎn)發(fā)跳數(shù)。如圖6 所示，數(shù)據(jù)包轉(zhuǎn)發(fā)到車輛S，而下一個轉(zhuǎn)發(fā)路段與車輛S 所在路段同方向。車輛D 在車輛S的通信范圍內(nèi)，車輛S 可以直接將數(shù)據(jù)包發(fā)送給車輛D，如果先將數(shù)據(jù)包發(fā)送給路口車輛A，再由A 轉(zhuǎn)發(fā)，則就會增加轉(zhuǎn)發(fā)跳數(shù)，從而增加轉(zhuǎn)發(fā)時延。

圖6 接收車輛和轉(zhuǎn)發(fā)車輛在同方向路段Fig.6 Receiving vehicles and forwarding vehicles in same direction

本文的優(yōu)化方法是：車輛在轉(zhuǎn)發(fā)數(shù)據(jù)包前，通過查找數(shù)據(jù)包頭部字段“所經(jīng)過路段的ID序列”，找到當(dāng)前路段ID的下一個路段ID，然后查找當(dāng)前車輛的鄰居列表中所有車輛所在路段的ID是否有與下一個路段ID相同的車輛，如果有就加入備選轉(zhuǎn)發(fā)車輛集，如果沒有再將字段車輛是否處于交叉路口置1的車輛加入備選轉(zhuǎn)發(fā)車輛集。

數(shù)據(jù)包貪婪轉(zhuǎn)發(fā)策略偽代碼如下所示。

4 實(shí)驗(yàn)仿真與結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)置

使用NS3 和SUMO 軟件對本文所提出的路由算法（VGPE）進(jìn)行了仿真，并將該算法與傳統(tǒng)路由算法GPSR［13］和改進(jìn)的路由算法最大持續(xù)時間最小角的GPSR（Maxduration-Minangle GPSR，MM-GPSR）進(jìn)行了對比。為了使仿真能反映更加真實(shí)的場景，本文使用OpenStreetMap 在北京市提取了一個2 000 m*3 000 m 的仿真區(qū)域，然后使用SUMO 將地圖文件生成城市道路文件，如圖7 所示，并在城市主干道路中生成車輛的移動軌跡文件，以便在后續(xù)仿真中使用。

圖7 城市道路圖Fig.7 City road map

NS3 網(wǎng)絡(luò)模擬器用于路由實(shí)現(xiàn)和性能評估，實(shí)驗(yàn)中仿真參數(shù)的設(shè)置如表1所示。

表1 參數(shù)設(shè)置Tab.1 Parameter settings

4.2 評價指標(biāo)

為了量化路由算法的性能，本文以下面三個評價指標(biāo)對路由算法的性能進(jìn)行分析，每個指標(biāo)都進(jìn)行了10 次實(shí)驗(yàn)，取10次實(shí)驗(yàn)的平均值以消除誤差。

4.2.1 數(shù)據(jù)包到達(dá)率

數(shù)據(jù)包到達(dá)率（Packet Delivery Ratio，PDR）：仿真時間內(nèi)網(wǎng)絡(luò)中目的車輛接收到的數(shù)據(jù)包的總數(shù)Prcvd與源車輛發(fā)送的數(shù)據(jù)包的總數(shù)的Psend的比值，計算式如式（6）所示。

4.2.2 平均端到端時延

平均端到端時延（Average end To end Delay，ATD）：數(shù)據(jù)包i從源車輛到目的車輛所經(jīng)過的時間Ti與目的車輛接收到的數(shù)據(jù)包總數(shù)的比值，計算式如式（7）所示。

4.2.3 平均端到端跳數(shù)

平均端到端跳數(shù)（Average end-To-end Hops，ATH）：數(shù)據(jù)包i從源車輛到目的車輛所經(jīng)過的跳數(shù)xi與目的車輛接收到的數(shù)據(jù)包總數(shù)的比值，計算式如式（8）所示。

4.3 結(jié)果分析

圖8（a）中源車輛的發(fā)送速率為每秒4 個數(shù)據(jù)包，在這樣的數(shù)據(jù)包發(fā)送速率下比較了在道路中不同車輛數(shù)情況下，通過三種不同路由算法到達(dá)目的車輛的數(shù)據(jù)包到達(dá)率。從圖8（a）中可以看出，隨著道路中車輛數(shù)的增加，三種路由算法的數(shù)據(jù)包到達(dá)率都呈上升趨勢。本文所提路由算法（VGPE）因?yàn)橐?guī)劃了數(shù)據(jù)傳播路徑，并優(yōu)化了數(shù)據(jù)在十字路口的轉(zhuǎn)發(fā)，所以本文算法在道路中不同車輛數(shù)情況下，數(shù)據(jù)包到達(dá)率皆優(yōu)于對比算法。在車輛數(shù)為400 時，本文算法的數(shù)據(jù)包到達(dá)率相較GPSR 路由算法提高了13.81%，相較MM-GPSR 路由算法提高了9.64%。

圖8（b）是在每秒8 個數(shù)據(jù)包的發(fā)送速率下，道路中不同車輛數(shù)的數(shù)據(jù)包到達(dá)率。從圖8 中可以看出，圖（b）三種路由算法的數(shù)據(jù)包到達(dá)率的趨勢和圖（a）基本相同，但在相同車輛數(shù)情況下，圖（b）與圖（a）相比，同一路由算法的數(shù)據(jù)包到達(dá)率有所下降，本文所提路由算法（VGPE）優(yōu)勢減弱。在車輛數(shù)為400 時，本文算法的數(shù)據(jù)包到達(dá)率相較GPSR 路由算法提高了9.86%，相較MM-GPSR路由算法提高了7.35%。

圖8（c）是在每秒16個數(shù)據(jù)包的發(fā)送速率下，道路中不同車輛數(shù)的數(shù)據(jù)包到達(dá)率。從圖8（c）中可以看出，因?yàn)樵窜囕v每秒發(fā)送的數(shù)據(jù)包數(shù)大于車輛一次緩存的數(shù)據(jù)包數(shù)量，必然有些數(shù)據(jù)包會因?yàn)榫彌_區(qū)溢出而被丟棄，所以三種路由算法的數(shù)據(jù)包到達(dá)率都有大幅的降低。因?yàn)楸疚穆酚伤惴ㄒM(jìn)行路徑探索，在發(fā)送數(shù)據(jù)包過程中還要對路徑進(jìn)行調(diào)整，所以在每秒16 個數(shù)據(jù)包的發(fā)送速率下，本文路由算法的數(shù)據(jù)包到達(dá)率低于GPSR 路由算法。綜上可以得出，本文路由算法適用于在每秒數(shù)據(jù)包發(fā)送速率低于車輛緩存數(shù)量的情況。

圖9（a）是在每秒發(fā)送4個數(shù)據(jù)包的發(fā)包速率和改變道路中車輛數(shù)情況下，通過三種不同路由算法到達(dá)目的車輛的平均端到端時延。由圖9（a）中可以看出，隨著道路中車輛數(shù)的增加，發(fā)送車輛更容易找到下一跳車輛進(jìn)行轉(zhuǎn)發(fā)，所以三種路由算法的平均端到端時延都呈下降趨勢。但GPSR 路由算法由于可能將數(shù)據(jù)包發(fā)送到遠(yuǎn)離目的車輛的路段從而進(jìn)入恢復(fù)模式，增加了時延，所以在三個算法中GPSR 路由算法的時延最多。在車輛數(shù)為400 時，本文路由算法的時延相較GPSR、MM-GPSR降低了61.91%、27.28%。

圖9（b）、（c）是在每秒發(fā)送8、16 個數(shù)據(jù)包的發(fā)包速率和改變道路中車輛數(shù)情況下，通過三種不同路由算法到達(dá)目的車輛的平均端到端時延。計算端到端時延是通過目的車輛收到數(shù)據(jù)包的時延除以收到數(shù)據(jù)包的個數(shù)來求得的，因?yàn)檫^快的發(fā)包速率而被丟棄的溢出緩沖區(qū)的數(shù)據(jù)包無法到達(dá)目的車輛，因而不會被計入收到的數(shù)據(jù)包個數(shù)中，所以從圖9（b）、（c）中可以看出，數(shù)據(jù)包的發(fā)送速率對數(shù)據(jù)包的端到端時延影響并不大，三種路由算法的平局端到端時延總體趨勢不變。在圖9（b）中，車輛數(shù)為400時，本文路由算法的時延相較GPSR、MM-GPSR 降低了30.77%、14.29%。在圖9（c）中，車輛數(shù)為400 時，本文路由算法的時延相較GPSR、MM-GPSR 降低了22.22%、3.92%。

圖10（a）、（b）、（c）分別是以每秒4、8、16 個數(shù)據(jù)包的發(fā)送速率，并在道路中不同車輛數(shù)情況下，通過三種不同路由算法到達(dá)目的車輛的平均端到端跳數(shù)。從圖10 中可以看出，不同的數(shù)據(jù)包發(fā)送速率對平均端到端跳數(shù)影響不是很大，因?yàn)楸疚穆酚伤惴▽Ω鞣N可能出現(xiàn)冗余跳數(shù)的情況進(jìn)行了優(yōu)化，所以在不同數(shù)據(jù)包發(fā)送速率和不同車輛數(shù)情況下，本文算法的轉(zhuǎn)發(fā)跳數(shù)相對來說是最少的。GPSR 路由算法由于在恢復(fù)模式下轉(zhuǎn)發(fā)跳數(shù)的不確定性，所以平均端到端跳數(shù)不穩(wěn)定。

圖8 不同數(shù)據(jù)包發(fā)送速率條件下包到達(dá)率比較Fig.8 Comparison of packet arrival rates under different data packet transmission rate conditions

圖9 不同數(shù)據(jù)包發(fā)送速率條件下平均端到端時延比較Fig.9 Comparison of average end-to-end delays under different data packet transmission rate conditions

5 結(jié)語

本文分析了城市環(huán)境的特殊性，以及傳統(tǒng)的基于地理位置轉(zhuǎn)發(fā)的貪婪路由算法在城市環(huán)境中的局限性，提出了基于路徑探索的貪婪路由算法。通過將人工蜂群算法運(yùn)用到城市道路中選擇路由路徑，優(yōu)化轉(zhuǎn)發(fā)車輛的選擇方法，使得路由算法能感知道路中車輛的變化，并作出相應(yīng)的調(diào)整。實(shí)驗(yàn)結(jié)果表明，本文提出的路由算法相較于傳統(tǒng)的和其他改進(jìn)的地理位置路由算法具有較好的性能。

但是本文的路由算法應(yīng)用在相距較遠(yuǎn)的車輛之間進(jìn)行數(shù)據(jù)路由時，會因?yàn)榈缆返膹?fù)雜性使得路徑探索的復(fù)雜度和時延增加，從而造成整體路由性能下降。將路邊靜態(tài)節(jié)點(diǎn)作為中繼，轉(zhuǎn)發(fā)數(shù)據(jù)包，是克服車輛之間數(shù)據(jù)轉(zhuǎn)發(fā)距離過長而造成的性能下降的可行方法，接下來可在這些方面進(jìn)行研究。