0 引言

　　車聯網VANET(Vehicular Ad Hoc Network)是自組織網(Ad Hoc Network)的特例。VANET中的車輛可與鄰近的車輛或路邊設施(Road Side Units，RSU)通信。為此，VANET的通信可分為車間通信(Vehicle-to-Vehicle，V2V)和車與基礎設施通信(Vehicle-to-Infrastructure，V2I)。在V2V通信中，車輛采用短距離無線技術實現車輛間信息的交換，如Wi-Fi 和WAVE[1]。車輛通過特殊的電子設備使其能接收、發送消息。在V2I通信中，道路上的車輛能與鄰近的RSU進行連接并交互信息。本文，主要針對V2V通信展開分析。

　　在V2V中，車輛通過車載單元向其他車輛傳遞消息。車輛的快速移動和其分布的不均勻，為VANET的路由提出了挑戰。首先，鏈路的使用壽命受車輛移動的影響；其次由于網絡拓撲動態變化，每個車輛的路由表需不斷的更新，這將會增加額外通信負擔，甚至會引起堵塞[2-3]，使得數據包的傳輸變得更為艱難。為此，本文，提出多路徑路由算法。

　　依據路由策略，路由可分為5類[4]：(1)基于拓撲路由(Topology-Based Routing)；(2)基于位置路由(Position-based Routing)；(3)分簇路由(Cluster-based Routing)；(4)廣播路由(Broadcast Routing)；(5)組播路由(Geocast Routing)。在拓撲路由中，用表存儲拓撲信息并通過請求更新，如AODV[5]。在位置路由中，車輛通過系統獲取車輛的位置信息決策路由，如GPSR[6]。分簇路由[7]是將節點分簇，構成虛擬網絡結構。地理區域被劃分為網格，并在網格內選取節點作為簇首(Cluster Head)。簇首負責簇間以及簇內的協調工作。廣播路由就是通過廣播分發數據包，如BROADCOMM[8]。組播路由在地理區域內傳遞數據，并限制區域內泛洪，如IVG[9]。每類路由具有各自的獨立的特點。本文提出的算法引用拓撲和基于位置路由兩種策略理念。

　　VANET的路由可描述成單路徑、存儲轉發路徑和多路徑路由。現存有大量的多路徑路由，如按需多路徑距離矢量路由[10](Ad hoc On-Demand Multi-path Distance Vector，AOMDV)，S-AOMDV[11]，AODVM[12]。這些路由是基于AODV的改進版，屬于反應式路由，不具有可擴展性。例如，S-AOMDV通過額外的數據提高路由發現效率以及修復路由失敗，這會引起通信擁塞，降低帶寬利用率。

　　移動自組織網的研究工作[13-14]表明，受昆蟲激勵的自然啟發算法被成功地引入路由機制，如基于蟻群優化(Ant Colony based Optimization，ACO)。與其他算法[15-16]相比，此類算法表現良好的性能。如：通過共享局部信息，減少路由負擔；提供多路徑路由，以防路由失敗。

　　目前，面向VANET的移動感知的蟻群優化算法[17](Mobility-Aware Aant Colony Optimization，MARDYMO)是唯一受自然啟發的路由算法。該算法屬于反應式路由，采用廣播機制向網絡內車輛傳遞消息，這將占用大量的帶寬，且不具有可擴展性。

　　本文提出了混合式的ACO算法。該算法將充分有效利用帶寬，并具有可擴展性，對鏈路斷裂具有強健性。將車輛歸入區域，每個車輛屬于一個或兩個重疊區域。在區域內通過先應式算法尋找路由。在區域間通過存儲于每個區域內的局部信息，并采用反應式算法尋找路由。通過這種方式，減少廣播和擁塞。充分利用車輛的移動模型、車輛密度和車輛速度去構建多路徑算法，即(Mobility Aware Zone based Ant Colony Optimization Routing for VANET，MAZACORNET)。

　　車輛的移動使得車輛在短時間內遠離彼此的通信范圍。為此，在設計路由時，必須對車輛的位置以及車輛間連接進行管理。在MAZACORNET中，通過全球定位系統(Global Positioning System，GPS)獲取位置和速度信息。通過車輛間連接管理提高路由的穩定性，通過車輛的位置、速度信息可計算鏈路的穩定性。

1 蟻群優化算法

　　從自然界得到解決問題的方法被稱為群體智慧(Swarm intelligence，SI)。作為群體智慧之一的蟻群優化算法就是被廣泛應用于解決靜態和動態問題[18]。

　　Goss[19]研究了螞蟻的行為，研究結果表明，螞蟻能夠從食物源到自己巢穴之間找到最短路徑，而且能夠輕巧避開障礙物。螞蟻在通往食物路徑上存儲化學物質，將這種物質稱為信息素。后續的螞蟻依據信息素沿著路徑移動。螞蟻通常向信息素多的地方靠攏。沿著信息素多的地方移動，就能以最短路徑找到食物。這個過程就是間接通信的示例。

2 MAZACORNET

　　2.1 鏈路的穩定性

　　位置管理和連接管理對路由算法的性能起到非常關鍵的作用。通常，通過GPS獲取車輛的位置和速度信息。連接管理用于維持路由的穩定性。

　　假定行駛道路上的兩個車輛i、j，通過GPS獲取的初始位置分別為(Xi0，Yi0)和(Xj0，Yj0)，初始速度分別為Vi0和Vj0。如果兩個車輛在同一個通信范圍內，則認為它們是鄰居。用D表示兩車間的距離，R表示通信范圍。如果D>R，鏈路斷裂。車輛i、j間的鏈路的使用壽命?駐t表示從鏈路建立時t0到當D=R時t1時間差，即?駐t=t1-t0。如果給定車輛的位置以及速度，鏈路的使用壽命?駐t可通過式(1)進行計算[20]。

　　車輛i、j間的鏈路的穩定性LS(Link Stability)可通過式(2)進行計算[21]：

　　其中，tmax為常數，表示路由表的有效期。在本文提出的算法中，鏈路穩定性將被用于決策路由。

　　2.2 面向VANET的ACO模型

　　信息素是ACO算法中最為關鍵的參數。在蟻群中，信息素被存儲于地面上，從而吸引更多的螞蟻沿著由信息素構成的路由移動。對于VANET，聚集在鏈路上的信息素的增加和減弱均表征了該鏈路的質量。為了獲取高質量的鏈路，應尋找沿途沉積信息素大的路徑，即優質鏈路。假定從源節點至目的節點鏈路Lij，沉積的信息素量可表示為式(3):

　　其中，LS表示鏈路的質量，可由式(2)進行計算，PR表示成功接受消息的概率。

　　成功接受消息的概率PR取決于在同一個通信范圍內車輛間的距離，可通過Nakagami Fading Model[22]進行估計。該模型結合了VANET的高速、城市環境的特點，如式(4)所示。

　　其中，m表示衰減參數。例如，當m=3，表示快速衰減環境。

　　通過式(3)和(4)，沉積在鏈路Lij上的信息素可通過式(5)進行計算：

　　在ACO算法中，信息素的蒸發率通常設定為常數[23]。然而，在本文提出的算法中，針對每條不同的鏈路，的值不同。每條鏈路Lij的蒸發率可通過式(6)計算。

　　其中，k表示鏈路上至少沉積的信息素。為蒸發時限的倒數。

　　以上分析了面向VANET的ACO路由算法，接下來將分析基于蟻群優化的混合式移動感知路由算法。該算法具有可擴展性，并結合了反應式和先應式路由的優點。

　　2.3 基于蟻群的區域算法

　　在本文算法中，網絡劃分為區域。在區域內通過先應式算法傳輸數據包，區域與區域間采用反應式算法。通信跳數決定區域的尺寸大小。車輛可處于兩個重疊區域，區域尺寸也可變動。依據車輛所處區域的位置，可將車輛分為區內車輛(Interior Vehicle)、區邊車輛(Boundary Vehicle)和區外車輛(Exterior Vehicle)。如圖1所示，源節點S，區域半徑為2跳，車輛A、D、F處于邊界上，稱為區邊車輛。車輛B、C、E是區內車輛，其他的車輛屬區外車輛。

　　路由過程主要分為兩個階段：路由發現和路由維護。本文算法采用兩類路由表：區內路由表(Intra Zone Routing)和區間路由表(Inter Zone Routing)。區內路由表實時更新區域內信息，而區間路由表按需追蹤區間信息。在路由發現和路由維護階段，使用五類蟻群，分別為區內轉發蟻群(Internal Forward Ants)、區外轉發蟻群(External Forward Ants)、后向蟻群(Backward Ants)、通告蟻群(Notification Ants)以及錯誤蟻群(Error Ants)。

　　螞蟻用的數據表示格式如表1所示。

　　其中，Source表示源節點地址。Destination表示目的節點地址，對于區內轉發的蟻群，該區域為空。Sequence number表示每個螞蟻附身的序列號。Type用于標識不同類的螞蟻，區內轉發蟻群、區外轉發蟻群、后向蟻群、通告蟻群以及錯誤蟻群分別用0、1、2、3、4表示。Hop表示節點與區域內所有其他節點間的跳數。該區域的值用于辨別節點是屬于區內節點或非區內節點。Speed表示該節點的速度。Position表示該節點當前的位置。Path表示由一系列節點構成的源節點至目的節點的路徑。

　　(1)區域內的路由發現

　　區內路由表用于區域內的路由發現階段。該表包含了區域內所有車輛的信息。區內轉發的蟻群周期地更新表中的車輛信息。表中的列表示區域內所有車輛，而行表示離其他車輛一跳距離的車輛。在路由表中，通過式(5)和式(6)增加和減弱信息素識別路由。當源節點需要向目的節點發送信息時，首先查詢區內路由表的列，如果目的節點在它的區域，路由發現階段就完成了，否則，就在區域間進行路由發現，如下文所示。

　　(2)區域間的路由發現階段

　　當車輛在其區域內不能找到目的節點時，區域間路由表就開始發揮作用。通過區域間路由表尋找區邊車輛，以構建新的路由。區外轉發蟻群向區邊節點靠攏，直到發現目的節點。一旦發現了目的節點，后向蟻群將向源節點遍歷返回路線。然而，如果沒有發現目的節點或路徑的有效期已過期，則從當前區域使用區邊節點重復進行路由發現，直到發現目的節點。

　　(3)路由維護

　　由于網絡拓撲動態變化，路由可能斷裂。如果是在區域內路由斷裂，則按先應式算法原則周期地修復。若是在區域間路由斷裂，則該路由的上游車輛存儲數據包并選擇備用路由。如果存在備用路由，則啟動備用路由并更新。如果不存在，則通過錯誤蟻群向源節點發送路由失敗消息。

3 系統仿真及分析

　　3.1 仿真場景建立

　　使用隨機街道的都市場景進行仿真。初始仿真區域為500 m×500 m的區域，車輛數為25，交通燈數為10。隨后，區域變為1 500 m×1 500 m，車輛數增加至100。構建NS2仿真參數如下：

　　(1)仿真時間設定為2 000 s，車輛于t=0 s時刻移動，于t=100 s開始傳輸；

　　(2)車輛數目被設定為25、50、75、100；

　　(3)數據包大小為512 B；

　　(4)采用PriQuenue隊列；

　　(5)采用IEEE 802.11pw作為MAC協議；

　　(6)采用Nagakami傳播模型；

　　(7)仿真的協議為：MAZCORNET、AODV、AMODV、GPSR。

　　3.2 仿真結果

　　本小節分析MAZCORNET的路由性能，并與其他路由協議比較。

　　3.2.1 車輛數目對端到端傳輸時延的影響

　　圖2 顯示了車輛數目對端到端傳輸時延的影響曲線。與AODV、AMODV和GPSR相比，MAZCORNET的端到端傳輸時延最低。這主要歸功于MAZCORNET采用了區域架構、區內路由表和區間路由表。在區域內，通過先應式路由維護區內路由表，而在區間存有由蟻群存儲的路徑。通過這些預先準備的路徑信息有助于提高數據包端到端的快速傳輸。使用式(6)調整鏈路上信息素的減弱率，導致斷裂鏈路能及時被蟻群發現并丟棄。通過這些措施減輕了MAZACORNET端到端傳輸時延。

　　3.2.2 車輛數目對數據包傳遞率的影響

　　圖3顯示了MAZACORNET以及其他路由算法AODV、AMODV、GPSR的數據包傳遞率。從圖3可知，當車輛數目較少時，MAZCORNET并不具有良好的數據包傳遞率。這主要是由于沉積在鏈路上的信息素很少，區邊車輛不能傳遞數據包。在這種情況下，上游車輛緩存所有的數據包，并啟動修復程序，尋找通往目的節點的其他路徑。一旦發現了新的路徑，將告知源節點。同時，緩存的數據包就依據這條新發現的路徑傳遞到目的節點。從圖3可知，當節點數目的增加，MAZACORNET數據包傳遞率優于其他路由算法。這主要是因為MAZACORNET具有多條路徑選擇，而AODV和GPSR的路徑選擇是單一的。

　　3.2.3 車輛數目對數據吞吐量的影響

　　吞吐量性能曲線如圖4所示。當車輛數目增加，MAZACORNET的吞吐量性能最好。這是因為隨著車輛數目的增加，區域內車輛數也隨之增加，這會提高區域內車輛的連接率，增加了路徑數，從而使數據傳輸更為流暢，降低了數據包的丟失率，提高了數據包的傳輸率，如圖3所示。

　　3.2.4 車輛數目對路由開銷的影響

　　圖5顯示了MAZACORNET以及其他路由算法AODV、AOMDV、GPSR的路由開銷性能曲線。由于AODV和AOMDV是屬于反應式路由，無區域概念。而MAZACORNET在區域內使用了先應式路由理念。通過周期地發送控制包維護區域內路由，這是MAZACORNET路由開銷的主要來源。

　　本節，通過仿真結果分析了文中提出算法的性能。結果表明，MAZACORNET更適合城市場景即密集網絡。當網絡密集時，該算法能獲取較高的數據傳遞率和較低的端到端傳輸時延，與其他路由算法相比，由于MAZACORNET能夠提供多條路徑，維持較高的通信連接率，因此表現出更好的性能。

4 結論

　　針對VANET的路由問題，提出MAZACORNET路由方案。該方案是基于先應式和反應式兩種路由理念的混合多路徑路由算法。在路由決策過程中，不廣播消息，并提供多條可選路徑。將網絡區域劃分為不同的區域。在區域內通過先應式路由方案建立路徑，而在區域間采用反應式路由方案尋找路由，從而減少控制包廣播的次數，降低了網絡擁塞率。仿真結果表明，提出的MAZACORNET在密集車輛區域表現出了良好的性能，有效地提高了數據包傳輸率，降低了端到端傳輸時延。

參考文獻

　　[1] Xiang Weidong，Shan Dan，Yuan Jiaqi，et al.A full func-tional wireless access for vehicular environments(WAVE) prototype upon the IEEE 802.11p standard for vehicular communications and networks. In Proceedings of IEEE Consumer Communications and Networking Conference[C], Las Vegas, NV, USA 2012：58-59.

　　[2] 王海鳳，何之棟，黃文君.故障安全通信系統的研究與設計[J].電子技術應用，2014(1)：115-119.

　　[3] KAKARLA J，SATHYA S S，GOVINDA B，et al.A survey on routing protocols and its issues in VANET[J].InternationalJournal of Computer Applications，2011，28(4)：38-44.

　　[4] JOHNSON D B，MALTZ D A.Dynamic source routing in ad hoc wireless networks[J].Kluwer Academic Publishers，Boston，1996，5(353)：153-181.

　　[5] Pei Guangyu，GERLA Mario，Tsu-Wei Chen.Fisheye state routing：a routing scheme for ad hoc wireless networks[C].In Proceedings of IEEE International Conference on Comm-unications，New Orleans，USA，2000：70-74.

　　[6] KARP B，KUNG H T.GPSR：Greedy Perimeter Stateless Routing for wireless networks[C].In Proceedings of the 6th Annual ACM International Conference on Mobile Computingand Networking, Boston, Massachusetts, United States, Aug.2000：243-254.

　　[7] LIN C R，GERLA M.Adaptive clustering for mobile wirelessnetworks[J].IEEE Journal on Selected Areas in Communi-cations, 1997,15(7)：1265-1275.

　　[8] DURRESI M，DURRESI A，BAROLLI L.Emergency broad-cast protocol for inter-vehicle communications[C].In Pro-ceedings of 11th International Conference on Parallel and Distributed Systems,  2011，2(3)：402-406.

　　[9] BACHIR A，BENSLIMANE A.A multicast protocol in ad hoc networks inter-vehicle geocast[C].In Proceedings of 57th IEEE Semiannual Conference on Vehicular Technology, April 2013,4(4)：2456-2460.

　　[10] MARINA M K，DAS S R.On-demand multipath distance vector routing in ad hoc networks[C].In Proceedings of 9thIEEE International Conference on Network Protocols, pages14-23, California, USA, Nov. 2001.

　　[11] Chen Yufeng，Xiang Zhengtao，Wei Jian，et al.An improvedAOMDV routing protocol for V2V communication[C]. In Proceedings of the IEEE Intelligent Vehicles Symposium, 2011：1115-1120.

　　[12] Ye Zhenqiang，KRISHNAMURTHY S V，TRIPATHI S K.A framework for reliable routing in mobile ad hoc net-works[C]. In Proceedings of the 22nd IEEE International Conference on Computer Communications), pages 270-280, San Francisco, USA, Mar. 2003：270-280.

　　[13] SCHOONDERWOERD Ruud，BRUTEN J L，HOLLAND O E，et al.Ant-based load balancing in telecommunications  networks[J].Adaptive Behavior, 1996,5(2):169-207.

　　[14] PRASAD Sunita，SINGH Y P，RAI C S.Swarm based routing for MANETs[J]. International Journal of Recent Trends in Engineering,2011,1(1)：153-158.

　　[15] CLAUSEN T H，JACQUET P.Optimized link state routing  protocol(OLSR).Technical report, INRIA, Oct.2003.

　　[16] PERKINS C，ROYER E M.Ad-hoc on-demand distance vector routing[C].In Proceedings of 2nd IEEE Conference on Mobile Computing Systems and Applications, February 1999:90-100.

　　[17] LUIS Sergio，CORREIA O B，CELESTINO Joaquim，et al.Mobility-aware ant colony optimization routing for vehicularad hoc networks[C]. In Proceedings of IEEE Conference 2011:1125-1130.

　　[18] BONABEAU E，DORIGO M，THERAULAZ Guy.Swarm

　　Intelligence:From Natural to Artificial Systems[J].Oxford University Press, USA, Sep.1999:123-128.