車聯網下基于RSU輔助AODV路由協議改進

摘 要：目前，VANET網絡中，針對AODV協議的改進僅僅考慮車載單元（OBU），沒有將作為接入Internet起到網關作用的路側單元（RSU）考慮進來。在本文中，我們針對這一實際情況，提出了基于RSU輔助AODV路由協議（ARSU-AODV）改進，以快速建立到目的節點的穩定路由。仿真結果表明，基于RSU輔助AODV路由協議改進降低了丟包率、端到端的延遲，具有一定的可行性。

關鍵詞：VANET網絡；AODV路由協議；ARSU-AODV

1 研究背景及研究現狀：

進入21世紀，經濟全球化進程加快。人類社會進入了一個科學技術迅猛發展的歷史時期，智能交通系統（Intelligent Transportation System，ITS）應運而生。智能交通系統是人們在較完善的交通基礎設施上，把通信、計算機、信息、自動控制和系統集成等技術加以運用，建立的一個集安全、高效、便捷、舒適、環保的綜合系統。智能交通系統可用來加強交通設施、載體和用戶之間的聯系，保證系統內運行的可控性和有序性，提高運行效率，減少事故，降低污染。21世紀將是公路交通智能化的世紀，人們將要采用這一先進的一體化的交通綜合管理系統，對道路、車輛的行蹤進行實時監控、調度[1]。

車載自組織網絡（Vehicle Ad hoc Network，VANET）在智能交通系統中起著重要作用。VANET是在傳統的移動自組織網絡（MANET）基礎上發展起來的，是一種特殊的移動自組織網--是一種由裝備了無線通信收發裝置的車輛，組成的一個臨時性的多跳自組織網絡。VANET作為智能交通系統的基礎部分，具有極高的研究價值和應用前景。概括來說，車載自組織網絡（VANET）通過車間通信和車與路側單元通信，能夠提供兩大類應用。一類是安全應用，主要為解決行車安全、舒適，比如前方事故預警、提示道路阻塞、提醒限速、為司機選擇最佳行車路線或免費緊急通道；另一類是用戶應用，主要是提供增值業務，為乘客在車內提供娛樂功能。比如天氣情況；Internet連接以分享音樂、看電影、聊天、玩游戲；對附近旅游景點、酒店、加油站進行篩選；對產品、服務進行內容、價格、位置的查詢；商業結構也可以通過VANET進行發布商業廣告。

如圖1所示，在VANET中，行駛在路面的車輛作為網絡節點是重要組成部分，每一輛車都配有車載單元（也稱OBU）用來提供無線通信。路側單元（也稱RSU）作為靜止的基礎設施被統一的部署在公路兩側，在車輛進入通信范圍內提供無線接入的端口。所有的RSU都通過有線線路（像光纖）或其他線路接入到高寬帶、低延遲、低錯誤率的主干網絡。主干網絡可以通過Internet與中心網絡進行相連。因此RSU可以簡單、快捷、準確地通過主干網絡、中心網絡相互之間進行交換信息或同步信息。

目前，由于VANET在解決道路安全、交通擁堵、協助駕駛、道路資源共享等方面上的優勢，引起了世界各國研究人員和科研機構、汽車制造商的密切關注[2-5]。近年來，各國政府、大型汽車制造商針對VANET開展了深入而有效的工作：積極開展車載自主網絡環境下相關通信協議、標準等熱點問題的研究，并啟動了一系列的相關科研項目。盡管對車載自組織網絡的研究，已經取得了一些可觀成果。但正如文獻[6]所描述的，仍面臨著一系列的理論難題和技術瓶頸。車載自組網的應用主要包括兩個方面：一是道路安全方面；二是快速發展的商業服務。而車輛之間的信息交互是這兩個方面實現的前提，可靠的信息交互必然建立在穩定的路由之上，那路由協議研究就成為VANET領域不可或缺的部分。目前，在VANET網絡中并沒有具體標準的路由協議。不過國內外學者針對VANET各類場景提出了大量路由機制[7-9]，其中大多都是根據傳統的MANET中可靠路由機制改進得來，包括基于拓撲的、基于位置的、基于概率的等。其中基于拓撲的泛洪式路由協議AODV協議是其中的典型代表，它是一種按需路由，其在數據需要發送時，找到相關路徑。在AODV協議的基礎上，針對VANET移動快、拓撲變化頻繁等實際情況，研究學者們提出了很多基于AODV的改進方案。文獻[10]中，Marina MK和Das SR提出了AOMDV協議：路由發現時，不在僅僅保存一條路徑，而是保存源節點和目的節點間建立多條路由，以備一條路徑斷裂，快速啟用備用路徑，繼續進行數據傳輸；G.Quddus，R.Khan和R.Iablald 等人在文獻[11]中提出了改進的AODV-RFC協議，文中指出利用利用路由失敗系數作為度量穩定性，建立更加可靠穩定的路由協議。文獻[12][13]，提出利用車輛的移動信息（比如速度、位置）進行移動預測，以選擇一條穩定的路由。文獻[14]，利用節點列隊占用情況，利用跨層協作進行選擇性轉發控制包，得到改善網絡吞吐量和提高業務公平性的目的。論文[15]中提出了改進版的SAODV用來提高AODV的安全性，文中利用數字標簽技術鑒定非關鍵域，利用哈希鏈表鑒定RREQ和RREP控制包的跳數等信息域。

2 AODV路由協議

AODV協議是Perkins和Royer針對基于距離矢量路由算法（DSDV）的改進而提出的。AODV路由協議是反應式路由的典型代表。它是一種完全按需、多跳式的路由協議。AODV避免了每個節點時刻保持活躍狀態、不斷更新路由列表信息的弊端；只有在兩個節點進行通信時，才啟動路由發現和路由維護工作。AODV集DSDV和DSR共同的優點于一身，即使用了DSDV的目的序列號機制保持路由的最新狀態，避免路由環路，同時也使用DSR按需路由的思想，以一種高效的方式選路，降低網絡負荷。

AODV協議包括四種控制包——RREQ包（路由請求包）、RREP包（路由回復包）、RERR包（路由錯誤包）和HELLO包，并通過這些控制包達到路由發現過程和路由維護過程兩大重要過程。

路由尋找：當源節點要向目的節點發送數據時，首先查看本地路由表看是否有到目的節點的路由。有則直接按照現有路由發送數據；沒有就發起路由尋找。路由尋找初始階段，源節點向周邊鄰居節點廣播RREQ控制包。中間節點收到RREQ，通過<源節點IP地址，RREQ ID>查看是否已經收到同樣的包，如果收到，立即丟棄。如果沒有收到，緩存該數據包信息，同時查看路由表是否有到源節點的反向路由。如果沒有，直接建立一條到源節點的反向路由。有的話，比較反向路由的序列號和RREQ中的源節點序列號，若RREQ中序列號較大，用RREQ更新反向路由。建立反向路由后，檢查路由表是否有到目的節點的最新路由（即路由表的目的序列號不小于RREQ包中的目的序列號），如果沒有直接轉發該RREQ控制包。直到該RREQ被轉發至目的節點或有到目的節點最新路由的中間節點。這些節點收到RREQ，就沿著已經建立的反向路由向源節點回復RREP。中間節點收到RREP后，在路由表里建立或更新到目的節點的正向路由。然后轉發RREP，直到轉發至源節點。源節點收到RREP，建立至目的節點的正向路由。這樣整個路由尋找功能就實現了。

路由維護：AODV協議通過周期性發送HELLO控制包進行鏈路檢測、本地鏈路修復和鏈路斷裂后向其他相關節點發送RERR控制包三種方式共同達到路由維護的目的。網絡中，移動節點周期性向通信半徑內所有鄰居發送HELLO包，用來檢測鄰居節點的存活狀況、與鄰居節點間鏈路的有效性。如果鄰居節點在一定時間內沒有再次收到鄰居發送的HELLO包，就認為鄰居節點已經離開該節點的通信半徑，認為與該鄰居的鏈路無效。這時，鏈路斷裂處的上游節點就會進行本地路由修復。發起本地修復的節點，向目的節點廣播到目的節點的RREQ包，并等待目的節點的RREP回復包。整個RREQ和RREP的處理流程同路由尋找過程一樣。如果一定時間內，該節點收到RREP包，則本地修復成功，重新建立了一條到達目的節點的路由。如果沒有收到，則認為修復失敗，該節點就會將該鄰居節點和以該鄰居節點作為下一跳的路由表中的目的節點均認為不可到達節點，并創建一個不可到達列表，同時會發送關于不可到達節點的RERR包。中間節點收到RERR后，將路由表里將不可到達節點作為目的節點的路由條目中的目的序列號設置為無效，同時向源節點轉發RERR包，源節點收到RERR后重新啟動到目的節點的路由尋找過程。

3 改進的AODV路由算法ARSU-AODV

在實際VANET中，節點會快速移動，導致節點間的鏈路維持時間將縮短，鏈路斷裂的風險也會加大。一旦節點間鏈路斷裂，將導致整條路由的失效，從而大大降低AODV路由協議的可靠性。現在針對AODV路由協議的改進方案，大多只考慮車載單元，沒有把路側單元考慮進來。針對VANET這一實際情況，我們把RSU考慮進來，提出了對AODV改進方案，即基于RSU輔助建立AODV路由協議（ARSU-AODV）。

在改進的基于RSU（路側單元）輔助建立路由的算法里，我們假設所有節點都能夠通過GPS獲得自身地理位置信息、速度，并且把信息封裝到HELLO包里，通過HELLO包，自身相關信息也可被鄰居節點獲知。同時我們把RSU當成速度為零、地理位置一定的‘OBU’（車載單元），并且每個RSU維護一張信息表：

AODV中，OBU會周期性的向周圍鄰居廣播HELLO包。當OBU進入RSU的覆蓋范圍，OBU周期廣播的HELLO包，被RSU監聽到。RSU查看所維護的信息表中OBU節點列表部分。如果該OBU不在列表里，意味著OBU第一次駛入該RSU范圍內或者很久以前駛入過，但信息已過期被刪除信息記錄。將該OBU的相關信息添加到信息列表中，并且向該節點以單播的形式發送通知包到該節點。通知包包含該RSU自身信息（例如RSU ID、地理位置、IP地址等）以及鄰居RSU列表等相關信息。OBU將通知包里的信息添加到自身維護路由表里，這樣OBU就知道最近一次所接入RSU及下次可能接入的RSU的相關信息，以便后面的路由尋找時使用。RSU告知OBU其鄰居RSU列表的目的是：無論OBU朝哪個方向行駛，其進入的下一個RSU范圍一定是鄰居RSU列表中的一員，當然OBU也可能不進入他們的任意一個RSU的范圍。

每一個RSU都會定期的更新維護自身信息表，可以看出信息表里RSU自身信息、鄰居RSU列表是永遠不會變化的，只有OBU節點列表信息會發生變化。對于RSU覆蓋范圍內的所有OBU節點（即RSU信息表中OBU列表里所屬RSU ID設置為自身ID的OBU節點），若一定時間范圍（由于HELLO包廣播的周期為1s，這里設置為大約2s）內沒有再次收到某一節點廣播的HELLO包，RSU便認為該OBU已經駛出RSU的覆蓋范圍了，直接刪除OBU列表里該RSU信息。對于最近被用來通信且屬于其他RSU范圍的中間節點的OBU，在使用完之后，設置一定的預留時間（Reserved Time），以便近期再次使用。若是在預留時間內沒有再次啟用，同樣直接刪除；若是再次啟用，可直接快速定位到所屬RSU。通信時，節點根據信息表里該OBU節點所屬RSU，先與定位到的RSU通信，RSU再在自己范圍內尋找這個中間節點OBU，并借助該OBU完成通信。當然，通信時作為中間節點的OBU可能已經駛離其所屬RSU范圍。若是這種情況，按照下面的路由尋找重新找路；若是沒有駛離，按照原有路由記錄方式進行通信。通信完成后，重新設置預留時間。

路由尋找過程：（1）在考慮RSU情況下，源OBU節點和目的OBU節點通信可以分為四種情況：兩節點都在RSU覆蓋范圍內；兩節點均不在RSU覆蓋范圍內；源節點在、目的節點不在RSU覆蓋范圍內；源節點不在、目的節點在RSU覆蓋范圍內；這里到RSU發送的RREQ和RREP在原來AODV的數據格式進行稍微改動。

RREQ控制包數據格式：

注：RREQ包數據格式基本上和原AODV的類似，只是標志位，原AODV的標志位分：J|R|G|D|U，這里改進的算法里，再在標志位里加上CR：表示OBU請求建立與RSU之間的路由，該種請求包只有RSU能處理，OBU接收到只能轉發；

RREP控制包數據格式：

注：RREP包數據格式基本上和原AODV相同，原AODV標志位為：R|A，這里新的算法，再在標志位加上RR：表示RSU回復的控制包。

當源OBU節點向目的OBU節點發送數據時，首先檢查內核路由表，如果有到目的節點的路由，則直接按該路發送數據；如果沒有則啟動路由尋找：

（1）源OBU節點首先檢查路由表內最近所屬RSU是否為空（默認設置為NULL）：如果為NULL，說明源OBU節點近期內沒有和RSU交互，就以AODV的方式廣播到附近RSU的RREQ請求包，RREQ的標志位設置為CR，請求到附近RSU的路由。當附近的RSU收到RREQ請求包時，沿已經建立反向路由回復標志位設為RR的RREP控制包，整個過程類似于AODV源節點到目的節點路由尋找的過程。源OBU節點，等待ALLOWED_CONNECT_TIME后，如果沒有收到RSU的回復，則認為距離RSU較遠，借助RSU建立路由的方式適合于當前情景，直接啟動傳統的AODV路由尋找機制。

（2）如果OBU節點當前路由表里最近所屬RSU不為NULL，則向最近所屬RSU和鄰居RSU列表里的所有鄰居RSU發送到目的OBU節點的RREQ路由尋找；或者最近所屬RSU是否為空，但是通過（1）收到了附近RSU回復的RREP包，建立了到附近RSU的路由，則向該附近RSU發送到目的OBU節點的RREQ路由尋找。RSU收到RREQ請求包，檢查自身信息表，同時通過外部主干網查詢所有RSU信息表，查看是否包含目的OBU節點IP信息。如果包含，說明目的OBU節點現屬于某一RSU的覆蓋范圍或者某一RSU有到目的節點的最新路由，這時源節點就可以首先通過向RSU發送數據，然后RSU通過主干網或者根據已有最新路由向目的OBU節點轉發數據的方式，進行通信。

（3）如果所有RSU信息表中都不包含目的OBU節點的IP地址，說明目的OBU不在RSU通信范圍內。所有的RSU向附近OBU節點以原AODV路由尋找方式，轉發RREQ請求包。但是RREQ請求包的跳數在轉發前被設置為2，即RSU只向2跳范圍內的OBU尋找目的節點，這樣能夠避免多跳轉發引起的全網網絡阻塞。

（4）RSU轉發RREQ后，設置等待時間為ASSISTED_CONNECT_TIME，若這段時間內，收到目的節點回復的RREP包，則把RREP生存時間設置為MY_ROUTE_TIMEOUT，同時把該RREP按照以建立的反向路由回復給源OBU節點；如果規定時間內沒有收到回復的RREP包，說明目的節點距離任意一個RSU的范圍都較遠，不利于借助RSU建立路由。在等待時間末，回復給源OBU節點一個到目的OBU節點的生存時間為0的RREP回復包。

（5）若是源節點收到一個RREP包的生存時間為0，說明此時場景不適合通過RSU輔助建立路由，則自動啟動傳統AODV的路由尋找。

4 仿真結果

我們采用當前比較流行的網絡仿真軟件NS2軟件，分別對AODV和改進后的ARSU-AODV協議進行了分析，通過6組源節點到目的節點數據通信的仿真分別對二種路由丟包率、端到端的延遲、協議開銷等進行比較，衡量二者的性能。仿真參數設置如下：

其中RSU沿道路兩旁，按照泊松分布進行部署，大于每千米部署8個RSU。OBU和RSU的通信范圍均設置為250m。

丟包率=（發送包數量-接收包數量）/發送包數量。它反應了路由的穩定性和網絡的擁塞程度。由圖2可以看出原AODV和改進后的ARSU-AODV協議的丟包率都不高，都低于20%。但從整體上可以看出ARSU-AODV的丟包率更低。這是由于在RSU存在的情況下，可以更加快速的尋找到目的節點的路由。同時通過RSU輔助建立路由，在依靠RSU發送數據時，由于RSU和RSU通過高寬帶、低延遲、低錯誤率的主干網絡相連，保證了數據的可靠傳輸。

由于端到端的延遲與節點的移動速度有關，圖3給出是兩種路由下不同速度下6組節點的平均延遲?？煽闯鏊俣仍酱螅瑑煞N路由協議下延遲都會變大，這是由于節點速度越大，網絡越不穩定，就會使鏈路中斷，導致重新發起路由查找，加大延遲。比較二者可看出，改進后的路由ARSU-AODV，在RSU存在的情況下，RSU可作為數據轉發的中間節點，或者可以快速的輔助建立新的路由，這都使端到端的延遲降低。

路由開銷=（發送總包數-應用層總包數）/發送總包數，它是源節點往目的節點發送數據時，建立路由和維護路由所付出的網絡代價，它包括4種控制包HELLO包、RREQ包、RREP包和RERR包。通過圖4可看出，兩種路由歇息路由開銷的比重都比較大，而且隨著速度的增大開銷也會變大。這是由于節點速度增大后，拓撲變化劇烈，鏈路斷裂的概率變大，這勢必造成路由開銷變大。由于基于RSU輔助建立的AODV路由，節點會與RSU交互，發送數據包會增多，使ARSU-AODV開銷略大。

5 結論

在本文中，針對VANET實際場景，我們對原有AODV提出了基于RSU輔助AODV路由協議（ARSU-AODV）改進。它將路側單元考慮進來，以便快速的建立穩定的路由。仿真結果表明，ARSU-AODV路由協議，除了路由開銷較AODV稍大之外，能一定程度上降低端到端的延遲和丟包率。

[參考文獻]

[1]ITS_百度百科：http：//baike.baidu.com/view/39610.htm.

[2]LuoJ，Hubaux JP.A survey of Inter-vehicle communication. Technical Report，Switzerland：EPFL，IC（informatique Communications），2004.

[3]BlumJJ，Eskandarian A，Hoffman LJ.Challenges of intervehicle ad hoc networks.IEEE Trans.On Intelligent Transportation System，2004，347—351.

[4]2006.http：//www.sigrnobile.org/workshops/vanet2006/index.html

[5]BlumJJ，Eskandarian A，Hoffman LJ.Challenges of intervehicle ad hoc networks.IEEE Trans.On Intelligent Transportation System，2004，347—351.

[6]J.Lou，J-P.Hubaux，\"A Survey of Inter-Vehicle Communication\"， Technical Report，School of Computer and Communication Science， EPFL， Switzerland， 2004.

[7]D.Johnson et al.，“Dynamic Source Routing for Mobile Ad Hoc Networks”，IEFT MANET Draft，April 2003.

[8]S.Jaap，M.Bechler，L.Wolf.“Evaluation of routing protocols for vehicular ad hoc networks in city traffic scenarios”， 11th EUNICE Open European Summer School on Networked Applications，Spain，July’05.

[9]Royer et al.，“A review of current routing protocols for ad hoc mobile wireless networks”，IEEE Personal Communications， Apr’99.

[10]Marina MK，Das SR.Ad hoc on-demand multipath distance vector routing[C]，Proceedings of 9th IEEE International Conference on Network Protocols（ICNP），2001.

[11]Quddus G，Khan R，Iqbal R.et al.Finding a stable routethrough AODV by using ro ute fragility coefficient as metric[C].Proceedings of the 2006 IEEE International Conference on Networking and Services，2006：107-112

[12]S.-J.Lee，W. Su，and M. Gerla，“Ad hoc Wireless Multicast with Mobility Prediction”，Proceeding of IEEE ICCCN'99， Boston，MA，1999，pp.4-9.

[13]W.Su，“Motion Prediction in Mobile/Wireless Networks”， PhD Dissertation，UCLA Computer Science Department，Los Angeles， CA，1999.

[14]Romdhani L，Bonnet C.A cross-layer feature for an efficient forw arding strategy in w ireless Ad Hoc networks//Proceedings of the 20th International Conference on Advanced Information Networking and Applications.Vienna， Austria，2006， 1：741-746.

[15]M.Zapata and N.Asokan，“Securing Ad-hoc Routing Protocols，”in Proc.of ACM Workshop on Wireless Security （WiSe），Atlanta，GA，Sept.2002.