車聯(lián)網(wǎng)下基于RSU輔助AODV路由協(xié)議改進

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

關鍵詞：VANET網(wǎng)絡；AODV路由協(xié)議；ARSU-AODV

1 研究背景及研究現(xiàn)狀：

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

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

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

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

2 AODV路由協(xié)議

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

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

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

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

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

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

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

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

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

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

RREQ控制包數(shù)據(jù)格式：

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

RREP控制包數(shù)據(jù)格式：

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

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

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

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

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

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

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

4 仿真結果

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

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

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

由于端到端的延遲與節(jié)點的移動速度有關，圖3給出是兩種路由下不同速度下6組節(jié)點的平均延遲。可看出速度越大，兩種路由協(xié)議下延遲都會變大，這是由于節(jié)點速度越大，網(wǎng)絡越不穩(wěn)定，就會使鏈路中斷，導致重新發(fā)起路由查找，加大延遲。比較二者可看出，改進后的路由ARSU-AODV，在RSU存在的情況下，RSU可作為數(shù)據(jù)轉發(fā)的中間節(jié)點，或者可以快速的輔助建立新的路由，這都使端到端的延遲降低。

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

5 結論

在本文中，針對VANET實際場景，我們對原有AODV提出了基于RSU輔助AODV路由協(xié)議（ARSU-AODV）改進。它將路側單元考慮進來，以便快速的建立穩(wěn)定的路由。仿真結果表明，ARSU-AODV路由協(xié)議，除了路由開銷較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.