基于GPSR協議的一種改進車載網路由協議

張 好， 鄭世慧， 楊 榆(北京郵電大學信息安全中心，北京100876)

0 引言

車載自組網(Vehicular Ad Hoc Network，VANET)是一種特殊的無線自組網。基本思想是在一定通信范圍內的車輛自動地相互連接建立起一個移動的網絡，用于交換各自信息(如車速、位置等)和車載傳感器感知的數據。車載自組織網絡在事故預警、保障交通安全、智能駕駛、收費站繳費、乘客辦公與娛樂化及電子商務等很多方面有著良好的應用前景。近年來，隨著車輛的飛速普及，車載網已經引起了越來越多的研究者，其路由協議也成為一個研究的熱點。

通過改進傳統的GPSR車載網路由協議，獲得一種新的連通率較高，適應不同道路情況的新車載網路由協議。仿真測試表明，新協議能很好的適應車載網中車輛節點高速移動的特性，降低道路間障礙物對數據傳輸的影響，并且能夠根據車流密度自動調節數據包的流向，從而提高路由協議的連通率。同時，新的路由協議也能夠自動區分鄉村高速公路、城市路況等不同的道路環境，并依據不同的路況采用不同的策略進行數據的傳輸。

1 GPSR協議

1．1 GPSR協議簡介

GPSR(Greedy Perimeter Stateless Routing)路由協議是一種地理位置輔助路由協議。該協議中，每個節點需要在一定周期T內向一跳范圍內的節點廣播自己的位置信息，這樣每個節點就知道自己和自己一跳范圍內所有鄰居節點的位置。節點在發送數據前不尋找路由，不保存路由表，移動節點直接根據包括自己、鄰節點以及目的節點的位置信息制定數據轉發決策，其數據轉發模式有貪婪模式和周邊模式兩種。當一個節點收到數據分組時，首先采用的是貪婪模式轉發，如果貪婪模式失敗則轉為周邊模式轉發。

圖1所示為貪婪轉發示意圖。圖中以節點x為中心的圓代表x的一跳通信范圍，以節點z為中心的圓代表z的一跳通信范圍。x收到一個要轉發至z的數據包，首先查找鄰居節點表中距離自身最遠(即最接近目的節點)的鄰居節點，發現y是滿足條件的節點，因此將數據包轉發給y。y重復貪婪轉發模式直至數據包到達z。

圖1 GPSR協議的貪婪模式

周邊轉發模式是指這樣一種情況，當節點查找鄰居節點表發現沒有比自身更接近目的節點的鄰居節點時，就按照右手規則轉發分組。右手規則是指數據分組沿著路徑轉發，目的節點始終在轉發路徑的右側。在圖2中，由于x在其通信范圍內的鄰居節點中沒有發現比它自身更接近于目的節點z的節點，貪婪轉發失敗，因此采用右手規則轉發數據分組，其分組發送的路徑是x-＞a-＞b-＞c-＞z。

圖2 GPSR協議的周邊模式

1．2 GPSR協議性能分析

在VANET中，通信節點處于高速移動狀態，一條鏈路的有效時間非常短，所以一旦存儲路由表，就必須不停地更新路由表，才能保證鏈路的有效性，這種方式在通信量和通信時間上的開銷非常大，而GPSR協議采用邊發包邊找路的策略就能很好地避免上述問題，這使由于位置改變帶來的丟包現象的可能性大大縮小。

但是，同時GPSR協議也存在著適用性不強、連通率不高的缺點。原因如下:

(1)GPSR協議將地圖信息簡單的當做一個二維圖進行處理，而忽視三維空間中的道路間障礙物對數據傳輸的阻礙。

(2)GPSR協議根據存儲在節點本地位置信息表的位置信息選擇一跳范圍內的最優節點作為數據傳輸的下一跳節點。每一個節點只能根據每隔T時間接收的廣播信息記錄一跳范圍內其他位置節點的信息，也就是說S節點只能獲取處于自己一跳范圍內R節點T，2T，3T，…，NT時刻的位置信息。如果在NT+t(0＜t＜T)時刻S節點收到數據包，它只能根據NT時刻記錄的位置信息選取一跳范圍內的最優節點R，但是，如果S和R處于高速移動狀態，那么NT+t時刻，最優節點R很有可能已經移出S節點的通信范圍，在這種情況下S節點發出的數據包必定無法傳送到R節點。

(3)在原始的GPSR協議中，一旦節點發現周圍一跳范圍內沒有合適的的節點作為數據的下一跳，那么節點將會直接丟棄數據，從而導致數據的傳輸失敗。

2 改進的GPSR協議

GPSR協議存在著適用性不強、連通率不高缺點。因此，為進一步提高協議的適用性，保證協議能夠在各種道路環境下運行良好，提高協議的連通率，保證數據傳輸過程中的完整性，對GPSR路由協議進行改進，稱新協議為NGPSR。

2．1 NGPSR路由協議

NGPSR協議流程如下:

角色:發送者 S、經過的路口節點 C1，C2，…，Ct、參與轉發的車輛 N1，N2，…，Ns、接收者 R。

第一步:所有車輛節點產生一個記錄自己位置信息和自身標示(如車牌號等)的廣播數據包，每隔時間T向一跳范圍內的車輛節點廣播該數據包;節點收到一跳范圍內的其他節點廣播的位置信息后，將一跳范圍內所有節點的標示信息和位置信息記錄在本地位置信息表中。

第二步:發送者S產生一個數據包，通過GPS獲取接收者R的位置信息，并從本地位置信息表中獲取一跳范圍內的所有節點信息。S節點判斷自己一跳范圍內是否存在目的節點(此時S節點并不是直接以位置信息表中的位置信息作為判斷依據，而是先對一跳范圍內的所有車輛節點進行位置預測，然后以預測的位置信息作為判斷依據，文中所有的位置判斷操作過程都是指先位置預測再判斷)。若存在，則將數據發送給目的節點R;若不存在，S節點判斷自己一跳范圍內是否存在路口節點。若存在，則將數據發送給路口節點C1;若不存在，S節點判斷自己一跳范圍內是否存在比自己更接近目的節點的車輛節點。若存在，則用貪婪模式將數據轉發給自己一跳范圍內的車輛節點N1;若不存在，則用周邊轉發模式將數據轉發給自己一跳范圍內的車輛節點N1。

第三步:路口節點Ci(1≤i≤t)收到數據包后，Ci節點判斷自己一跳范圍內是否存在目的節點R，若存在，則將數據發送給目的節點R;若不存在，Ci節點通過GPS獲得離目標節點R最近的路口節點的信息，判斷自己是不是離目標節點R最近的路口節點。若Ci節點是離目的節點R最近的路口節點，則將數據轉發給行駛在自己和目標節點所處路上離路口節點Ci一跳范圍內的車輛節點Nj(1≤j≤s);若Ci節點不是離目標節點R最近的路口節點，Ci獲取自己所處的幾條道路的車流密度信息，判斷幾條道路離目的節點R的距離。綜合這2個信息，選擇一條道路，并將數據轉發到選定的這條道路上處在Ci節點一條范圍內的車輛節點 Nj(1≤j≤s)。

第四步:車輛節點Nj(1≤j≤s)收到數據包后，Nj節點判斷自己一跳范圍內是否存在目的節點R。若存在，則將數據發送給目的節點R;若不存在，Nj節點判斷自己一跳范圍內是否存在路口節點。若存在，則將數據發送給路口節點Ci+1;若不存在，Nj節點自己一跳范圍內是否存在比自己更接近目的節點的車輛節點。若存在，則用貪婪模式將數據轉發給自己一跳范圍內的車輛節點Nj+1;若不存在，則用周邊轉發模式將數據轉發給自己一跳范圍內的車輛節點Nj+1。

第五步:接收者R收到發送者S發送的數據。有以下幾種情況。

在第一步的操作中就R收到數據，此時t=0，s=0，沒有參與轉發的路口節點和參與轉發的中間車輛節點，S直接將數據發送給R;

在第二步的操作中就R收到數據，此時t≥1，s≥0，路口節點參與數據的轉發，目標節點在路口節點Ct一跳范圍內;

在第三步的操作中就R收到數據，此時t＞0，s＞=1，車輛節點參與數據的轉發，數據經過多跳到達接收者R節點。

圖3和圖4是具體的NGPSR協議流程圖。

圖3 模式一車輛節點協議流程

圖4 模式二路口節點協議流程

2．2 NGPSR協議的改進

相對于原始GPSR協議，新協議有4個方面的改進。

(1)增加位置預測功能。可以通過節點存儲在本地位置信息表中的數據預測節點在t時刻的位置。S節點選取接收到的R節點最近兩次的廣播信息，獲取R節點T時刻前和2T時刻前的位置信息:(x1，y1)，(x2，y2)。通過這兩個位置信息，S節點可以計算R節點的速度

運動方向是

因此，節點S可以利用公式獲取R節點t時間后的位置信息

以此類推，節點S可以預判其通信范圍內所有節點的運動方向及與節點S的距離，進而做出更加可靠有效的轉發節點選擇。

(2)引入路口節點，使路由協議由無中心的轉發模式升級為分層次的無中心轉發模式。路口節點負責將一條道路上的數據轉發至相鄰的道路，起數據中轉站的作用，保證數據只在一條路上進行傳輸，避免數據由一條路直接向另一條路傳輸時由于路口障礙物的阻擋導致的連通率下降的情況。

(3)考慮車流密度對連通率的影響。NGPSR在路口節點處統計車流密度，并根據車流密度選擇數據的傳輸路徑，避免數據包被轉發到封閉的小網絡中，從而提高連通率。

采用下面的方法統計車流密度:處于一條路兩端的兩個路口節點A，B彼此定期(間隔時間T)向對方發送一個特殊格式數據包，這條路上的車輛節點收到這種格式的數據包后，把自己存儲在本地的鄰節點的信息添加到這個特殊格式數據包的數據段部分，然后再通過GPSR協議轉發數據包，直至數據包發送到目的地。當A節點收到B節點發來的數據包，A統計該數據包數據段中的節點信息(出現多少個不同的車輛節點)。

(4)NGPSR協議對傳輸數據進行緩存。一旦節點A發現自己一條范圍內沒有任何節點可以傳輸數據，那么就在本地緩存該數據;T時間后，A節點再次在本地位置信息表中選擇合適的節點作為下一個傳輸節點，若仍然沒有合適的節點，就繼續緩存該數據;若直到3T時間后仍然沒有將數據傳輸出去，則丟棄數據包。在拓撲高速變化的車載網中，數據緩存能夠有效地降低數據丟包的概率。

3 仿真結果

圖5 實驗所用的城市地圖信息

圖6 實驗所用的鄉村高速地圖信息

圖5中有12條道路和4個路口，每一條道路的長度為5 KM;在每一個路口處都有一個路口節點;圖6中有一條長度為10 KM的道路。

在NS2軟件中分別模擬城市道路和鄉村高速公路進行5個實驗，前2個實驗分析制約GPSR協議性能的幾個因素，后3個實驗比較GPSR協議和NGPSR協議的性能。

3．1 速度對連通率的影響

實驗過程:在鄉村高速公路的環境下，針對GPSR協議，分別測量在不同車速情況下(10 m/s，20 m/s，30 m/s，40 m/s)下的連通率。實驗結果如圖7所示。

圖7 鄉村高速公路情況下不同速度下的連通率

圖7可以看出，隨著節點移動速度的增加，車載網連通率不斷下降。這是由于隨著速度的增大，目標節點R在傳輸時間內移出發送者S的通信范圍的概率也逐漸增大，從而導致連通率隨著速度的增加而下降。從實驗中可以看出車輛節點的高移動性是GPSR協議性能的一個重要制約因素。

3．2 路口障礙物對連通率的影響

實驗過程:在鄉村高速公路和城市道路的環境下，針對 GPSR協議，分別測量在不同車速情況下(10 m/s，20 m/s，30 m/s，40 m/s)下的連通率。實驗結果如圖8所示。

圖8 兩種道路環境下不同車速的連通率對比

從圖8中可以看出，在同樣的車流密度和速度的前提下，鄉村高速公路的連通率明顯高于城市道路道路時的連通率。通過測試得到的數據和對GPSR路由協議的分析發現，在這兩種情況下連通率出現差異的主要原因在于在城市道路上，數據的傳輸會出現換路。而在換路的過程中，由于路與路之間存在著大量的障礙物，導致傳輸受到阻礙，在這種情況下很有可能出現丟包。因此，實驗中可以看出路口障礙物是GPSR協議性能的重要制約因素。

3．3 鄉村道路下兩種協議連通率比較

圖9 鄉村高速公路GPSR和NGPSR算法的連通率

實驗過程:在鄉村高速公路的環境下，針對原始算法GPSR和改進算法NGPSR這兩個算法，分別測量在不同車速情況下(10 m/s，20 m/s，30 m/s，40 m/s)下的連通率。實驗結果如圖9所示。

從圖9可以看出，NGPSR協議的連通率不管在哪種速度條件下都要高于GPSR協議，并且隨著車輛節點速度的增大這種趨勢也越來越明顯。同時，隨著車速的加快，兩種算法的連通率都會下降，但是NGPSR算法下降的較為緩慢，GPSR算法則下降得較快。這是因為，在引入位置預測功能和數據緩存功能后，即使出現目標接收節點不在通信范圍內的情況，NGPSR協議也能在保證連通率的情況下處理數據，而GPSR協議在這些情況下直接導致數據的丟包，因此NGPSR協議的連通率較高;而隨著速度的加快，接收者跑出發送者一跳范圍的概率隨之增大，所以GPSR算法的連通率下降得很快;另一方面隨著速度的加快，對車輛位置的預測的準確性也隨之下降，所以NGPSR算法的連通率也緩慢下降。因此可以看出，引入位置預測功能和數據緩存功能后，能夠在一定程度上提高協議的連通率。

3．4 城市道路下兩種協議連通率比較

(1)實驗過程:在車流密度適中的城市道路環境下，針對GPSR和NGPSR這兩個協議，分別測量在不同車速情況下(10 m/s，20 m/s，30 m/s，40 m/s)下的連通率。實驗結果如圖10所示。

圖10 城市道路GPSR和NGPSR算法的連通率

在車流密度適中的情況下，在城市道路中，GPSR和NGPSR的主要區別在于:在這種情況下，NGPSR協議通過引入路口節點避免了一條路上的車輛節點直接向另一條路上的車輛節點發送數據而導致傳輸被路口障礙物中斷的情況出現。從圖10可以看出，NGPSR協議的連通率明顯高于GPSR協議。因此可以看出，引入路口節點后，能夠在一定程度上提高協議的連通率。

(2)實驗過程:在道路1上選取一個車輛節點作為發送者，在道路12上選取一個車輛節點作為接收者(確保數據包經過路口節點1，并在道路2和道路8之間做出選擇)。分別調整道路8的車流密度為每5000 m距離有(10/20/30/40)輛車，測出NGPSR協議和GPSR協議在這些不同的情況下的連通率。實驗結果如圖11所示。

圖11 不同車流密度下GPSR和NGPSR連通率對比

通過圖11發現，NGPSR連通率總是保持在一個很高額水準上，而GPSR的連通率則隨著道路8的車流密度的增大而上升。這是因為，改進協議在選路策略中考慮了車流密度這一因素，因而總能確保數據包向車流密度較大的道路2進行轉發，而道路2的車流密度適中，能夠確保數據包的良好轉發;而原始協議，當數據包被轉發至臨近路口節點1的車輛節點時，通過貪婪模式和周邊模式選取離目的節點更近的道路8中的車輛節點作為轉發節點，當道路8的車流密度為每5000 m距離有10輛車時，難以保證每一個車輛節點通信范圍內存在其他車輛節點，因此連通率極低，隨著道路8車流密度的增大，連通率上升。因此說明改進協議能夠避免數據包進入車流密度比較小的道路，從而實現連通率的提升。

從實驗中可以看到不管是在鄉村高速公路環境下還是在城市道路環境下，NGPSR協議的性能都要明顯優于GPSR協議，而且還分析了NGPSR協議性能優于GPSR協議的原因，這也進一步從理論上證明NGPSR協議的優越性。

4 結束語

通過對比分析現有的VANET路由協議的優缺點，選擇了通信量小、通信時間短、無需建立路由GPSR的路由協議作為基礎，通過理論分析和實驗，找出車輛節點的高移動性、數據在傳輸的過程中換路、車流密度這些制約GPSR協議性能的因素，并針對這幾個制約因素對GPSR協議進行改進，在GPSR協議的基礎上添加位置預測功能和數據緩存功能，并引入路口節點、考慮車流密度，提出一種新的適應性強、連通率高的NGPSR協議，最后通過大量的實驗數據證明NGPSR協議不管實在城市道路環境下還是在鄉村高速公路環境下的性能都明顯優于GPSR。

［1］ KARPB，KUNGHT.GPSR:greedy perimeter stateless routing for wireless networks［C］.MobiCom:Proceedings of the 6th Annual International Conference Oil Mobile Computing And Networking.New York，USA，2000.

［2］ Tsu-Wei Chen.Global State Routing:A new routing scheme for Ad-hoc wireless networks［C］.Proc IEEE ICC’98.1998.

［3］ C.E.PERKINS，BHAGWAT P.Highly Damie Destination-Sequenced Distance-Vector Routing(DSDV)for Mobile Computers［C］.In:Proceedings of the ACM SIGCOMM＇94 Conference on Communications Architectures，Protocols and Applications，London，UK，August 1994:234-244.

［4］ Johnson D B，Maltz D A.Dynamic source routing in Ad Hoc wireless networks［C］.Proc of The International Series in Engineering and Computer Science.New York:Kluwer Academic Publishers，1996:153-181.

［5］ Perkins C，Belding-Royer E，Das.Ad Hoc On-Demand Distance Vector(AODV)Routing［C］.IETF RFC 3561，2003.

［6］ 戴其進.車載網的路由協議研究［D］.北京:北京郵電大學，2013.

［7］ 張帆.城市場景下車載自組網中GPSR路由協議的研究［D］.長春:吉林大學，2011.

［8］ 朱二華.一種自適應的城市場景VANET路由協議［D］.廣州:廣州華南師范大學，2010.

［9］ 劉江永，張洋祥，韓鵬.不同場景中VANET路由協議的仿真研究［J］.計算機工程與應用，2009(18).

［10］ 王健，劉衍珩，焦玉.VANETs信任傳播建模［J］.北京郵電大學學報，2009(S1).

［11］ 常促宇，向勇，史美林.車載自組網的現狀與發展［J］.通信學報，2007(11).