基于城市道路的穩(wěn)定車載網(wǎng)分簇路由策略

衛(wèi)鵬偉++何加銘++曾興斌

1 引言

車載自組網(wǎng)[1]（VANET，Vehicular Ad-Hoc Network）是一種特殊形式的移動自組網(wǎng)（MANET，Mobile Ad Hoc Networks），通過車輛裝載的無線通信設備，在車輛和車輛間、車輛與路邊基礎設施間有效地形成一種高動態(tài)的網(wǎng)絡系統(tǒng)。

VANET具有節(jié)點移動速度快且分布不均勻、無線鏈路不穩(wěn)定、網(wǎng)絡拓撲變化頻繁等特點。根據(jù)文獻[2-4]可知，由車載網(wǎng)絡轉(zhuǎn)發(fā)策略的不同，可以將車載網(wǎng)路由協(xié)議分為基于拓撲的路由協(xié)議（TBR）、基于地理位置的路由協(xié)議（PBR）以及分級路由協(xié)議（HRP）?；诜旨壍穆酚蓞f(xié)議可以將整個無中心控制的高動態(tài)網(wǎng)絡轉(zhuǎn)變?yōu)橐粋€受中心控制的高動態(tài)網(wǎng)絡，能夠有效地增強網(wǎng)絡管理性，降低路由開銷；但在分級路由協(xié)議，高速移動車輛節(jié)點的簇結(jié)構(gòu)比較不穩(wěn)定，需要頻繁地進行簇結(jié)構(gòu)的維護，而這樣容易造成節(jié)點的數(shù)據(jù)傳輸受到嚴重影響。

針對上述分層路由協(xié)議存在的問題，并結(jié)合文獻[5-7]的觀點，本文提出了一種基于車輛運動方向和地理位置的穩(wěn)定的分簇路由協(xié)議（SCR）。SCR協(xié)議繼承了基于地理位置的路由協(xié)議和分級路由協(xié)議的優(yōu)點，通過改善成簇算法，增強了簇結(jié)構(gòu)的穩(wěn)定性；利用相對速度理論，結(jié)合車輛位置服務系統(tǒng)，將車輛通過速度和方向估算聚集成簇，進而有效地提高整體網(wǎng)絡的性能。通過分析文獻[8]中路由策略的可行性，發(fā)現(xiàn)其在一定道路條件受限，通過改進其路由算法，有效地解決了岔路口路由冗余問題，使得SCR更好地適應于VANET。

2 SCR協(xié)議

假設條件：

a：車輛均裝載GPS設備，可以隨時準確地知道自己的地理位置坐標；

b：車輛均可快速地通過速度儀表確定當前行駛速度；

c：車輛均裝載全向無線傳輸設備，可接受任何方向信號；

d：車輛通信半徑為R。

整個SCR協(xié)議由成簇路由協(xié)議和路由轉(zhuǎn)發(fā)協(xié)議這2部分構(gòu)成，下面將對各部分進行具體論述。

2.1 成簇路由協(xié)議

在SCR協(xié)議中，節(jié)點包括：簇頭節(jié)點、輔簇頭節(jié)點、簇成員節(jié)點和網(wǎng)關。簇頭的職責在于對簇內(nèi)成員的管理、簇間路由的維護以及簇間數(shù)據(jù)的傳輸；輔簇頭是簇內(nèi)的備用簇頭節(jié)點，在簇頭有效期內(nèi)發(fā)生突變或離簇時，主動廣播自身節(jié)點成為簇頭；簇成員負責簇內(nèi)路由的維護；不同簇的相交節(jié)點形成網(wǎng)關，實現(xiàn)簇間互連及通信。

SCR的成簇路由協(xié)議具有2項工作：簇的構(gòu)建和簇的維護。簇的構(gòu)建主要負責簇頭、簇成員、網(wǎng)關的確定和簇的形成；簇的維護工作主要負責簇成員的入簇和離簇、簇頭突變時輔簇頭的選取建立以及簇內(nèi)成員節(jié)點信息的管理。

（1）簇的構(gòu)建

在道路環(huán)境下，為了提高簇結(jié)構(gòu)的穩(wěn)定性，根據(jù)車輛節(jié)點的位置信息、行駛方向及速度將車輛節(jié)點分離聚合成多個簇。成簇模型如圖1所示：

圖1 成簇模型

由圖1可知，道路車輛節(jié)點被分隔為多個簇，簇內(nèi)節(jié)點數(shù)量受限于車輛地理位置及行駛速度。

在SCR協(xié)議中，臨時簇頭通過節(jié)點權值大小選擇，節(jié)點通過周期廣播節(jié)點信息得到鄰居節(jié)點狀態(tài)信息，若節(jié)點自身行駛速度趨于最接近鄰居車輛節(jié)點的平均速度，則確認自己成為臨時簇頭；若同時存在多個相同狀態(tài)的節(jié)點，則最靠近鄰居車輛中心位置的車輛成為臨時簇頭（標記為CH0）。節(jié)點權值計算公式如下：

（1）

其中，vmax為車道車輛最大限速；vi為此節(jié)點速度；vj為鄰居節(jié)點速度；Ni為鄰居節(jié)點數(shù)量。

（2）簇頭的選舉與維護

選擇盡量遠離前進方向的岔路口節(jié)點作為簇頭的節(jié)點，避免簇頭的岔路口轉(zhuǎn)向造成簇的重組。整個選舉過程如下：

1）臨時簇頭CH0向鄰居節(jié)點廣播Lead0（c，loc，D，V，

）數(shù)據(jù)包，其中c表示簇標號，loc表示地理位置坐標，D表示行駛方向，V表示速度值，表示鄰居節(jié)點平均速度。

2）時間t0內(nèi)如果CH0收到來自其它鄰居節(jié)點B的Reply（loc，D，V）數(shù)據(jù)包，則表示節(jié)點B更適合成為簇頭，CH0自動放棄簇頭競選，并記錄B信息到簇頭路由表中；否則，CH0向全網(wǎng)廣播自己成為簇頭CH，向全網(wǎng)廣播Lead（c，loc，D，V）數(shù)據(jù)包，此時簇頭的同向鄰居節(jié)點依據(jù)自身運動狀態(tài)加入到簇內(nèi)成為簇成員，簇頭通過簇成員協(xié)調(diào)獲取鄰簇頭信息并記錄于簇頭路由表中。

3）某節(jié)點A長時間未收到Lead數(shù)據(jù)包或Lead0數(shù)據(jù)包，則它向全網(wǎng)廣播Apply（locA，D，V）消息，時間t內(nèi)如果收到任何簇頭CH的相應信息Lead（c，loc，D，V），則節(jié)點A加入到CH中，并將簇頭信息記錄路由表中；否則，它考慮自己成為臨簇頭，重復步驟1）。

4）當簇頭CH離開時，如果此時路段為非交叉路段，它將通過查詢路由表獲取式（1）中權值最優(yōu)節(jié)點ECH（輔簇頭），向ECH發(fā)送路由表信息，并向全網(wǎng)廣播Leave0（c，loc，D，V）消息。ECH收到消息后代替CH地位自動成為簇頭，并將收到的路由信息記錄自己路由表中；簇成員收到Leave0消息后自動更新路由信息，標記ECH為簇頭。如果此路段為交叉路段，則簇頭CH將直接廣播Leave（c，loc）信息，簇內(nèi)節(jié)點收到消息后直接進行簇的重建。

簇頭選舉結(jié)束后，每個簇頭均擁有自己所處簇信息、簇成員信息以及鄰居簇頭信息，簇成員節(jié)點記憶所屬簇信息及該簇內(nèi)簇頭信息。

2.2 路由轉(zhuǎn)發(fā)協(xié)議

如果源節(jié)點S需要發(fā)送數(shù)據(jù)包到目的節(jié)點D，S首先通過路由表查詢確認D是否為自己臨節(jié)點，如果是則S直接發(fā)送數(shù)據(jù)包到D；否則，S向自身所在簇內(nèi)簇頭詢問節(jié)點D是否為簇內(nèi)成員，如果是則通過簇頭轉(zhuǎn)發(fā)數(shù)據(jù)到D；否則，S進行簇間路由發(fā)現(xiàn)過程，發(fā)送RREQ請求數(shù)據(jù)包到簇頭，簇頭根據(jù)發(fā)送數(shù)據(jù)包方向定義方向矢量DSD，并根據(jù)DSD選擇最優(yōu)鄰簇頭，進行簇間數(shù)據(jù)轉(zhuǎn)發(fā)。endprint

在簇間數(shù)據(jù)轉(zhuǎn)發(fā)階段，為避免受道路周邊建筑影響在路由選擇中發(fā)生路由環(huán)路和路由冗余現(xiàn)象，簇首首先檢查自己的地理位置，如果位于岔路口，則通過改進的受限貪婪轉(zhuǎn)發(fā)算法進行下一跳鄰簇頭的選擇；否則，節(jié)點將根據(jù)矢量方向通過貪婪算法轉(zhuǎn)發(fā)數(shù)據(jù)。當下一跳簇頭接收到數(shù)據(jù)包后，檢查D是否為簇內(nèi)節(jié)點，如果是則直接將數(shù)據(jù)包轉(zhuǎn)發(fā)到D；否則，簇頭將數(shù)據(jù)包存儲路由中，并重復上述步驟尋找下一跳路由，直到TTL（路由轉(zhuǎn)發(fā)有效時間）為0時丟棄。

在數(shù)據(jù)轉(zhuǎn)發(fā)過程中，由于車輛節(jié)點的高速運動，造成數(shù)據(jù)包轉(zhuǎn)發(fā)至目的節(jié)點所處地理位置時，目的節(jié)點可能已經(jīng)離開源節(jié)點獲取的原有地理位置。假設目的節(jié)點前向簇頭節(jié)點（即路由最后一跳發(fā)起者）為a，此時a根據(jù)目的節(jié)點的移動方向，進行不大于2跳的小范圍洪泛。通過此方法，可使數(shù)據(jù)包有效地發(fā)送至目的節(jié)點。

為了降低路由開銷，減少數(shù)據(jù)轉(zhuǎn)發(fā)所需時間，下一跳鄰簇頭的選擇十分重要，可利用路段場景和交叉路口場景下的不同特點，結(jié)合矢量DSD，通過分析貪婪算法，對貪婪轉(zhuǎn)發(fā)算法進行改進。具體如下：

（1）傳統(tǒng)的貪婪轉(zhuǎn)發(fā)算法

傳統(tǒng)的貪婪轉(zhuǎn)發(fā)算法在一定場景模式下，容易造成路由路徑的冗余[8-9]，如圖2所示。假設圖中節(jié)點均代表各個簇頭節(jié)點，當簇間信息轉(zhuǎn)發(fā)時，節(jié)點u需要將數(shù)據(jù)發(fā)送到節(jié)點d。由貪婪算法可得，節(jié)點u將選擇距離d較近的1a作為下一跳，之后1a又轉(zhuǎn)發(fā)給b，此時出現(xiàn)局部最優(yōu)現(xiàn)象，b發(fā)現(xiàn)相對鄰簇頭其距離目的節(jié)點更近，此時轉(zhuǎn)發(fā)模式轉(zhuǎn)換為周邊轉(zhuǎn)發(fā)，選擇節(jié)點2a作為下一跳，再次通過貪婪算法選擇節(jié)點c，最后轉(zhuǎn)發(fā)到目的節(jié)點d。如果源節(jié)點u直接選擇2a作為下一跳，將避免后續(xù)的冗余路由。

（2）改進的貪婪轉(zhuǎn)發(fā)算法

新協(xié)議中提出了一種受限的貪婪轉(zhuǎn)發(fā)算法，路段場景下仍采用傳統(tǒng)的貪婪算法，而岔路口場景下節(jié)點優(yōu)先選擇岔路中位置節(jié)點作為下一跳，然后此節(jié)點優(yōu)先決定路由轉(zhuǎn)發(fā)的路段方向，再在此方向路段尋找最優(yōu)下一跳節(jié)點。

下一跳節(jié)點收到轉(zhuǎn)發(fā)數(shù)據(jù)包，首先判斷其與目的節(jié)點的地理位置，若處于同一方向路段，則進行貪婪轉(zhuǎn)發(fā)，不再刻意選擇岔路口節(jié)點，如圖3（a）所示。假設圖中節(jié)點均代表簇頭節(jié)點，簇頭u向目的簇頭d轉(zhuǎn)發(fā)數(shù)據(jù)包，u根據(jù)位置服務可知其與d位于同一方向路段，此時直接跳過岔路口節(jié)點進行數(shù)據(jù)包轉(zhuǎn)發(fā)，通過貪婪轉(zhuǎn)發(fā)數(shù)據(jù)包至節(jié)點a，直到目的簇頭節(jié)點d收到信息；否則，優(yōu)先將數(shù)據(jù)包轉(zhuǎn)發(fā)到岔路中節(jié)點，在此節(jié)點先進行支路方向選擇，再選擇下一跳路由。

在岔路口路由選擇時，考慮到車輛運動軌跡受限、行駛速度快、運動狀態(tài)可預判等因素，因此將方向作為路由選擇條件來降低路由跳數(shù)，實際場景如圖3（b）所示。假設圖中節(jié)點均代表簇頭節(jié)點，簇頭u向目的簇頭d轉(zhuǎn)發(fā)數(shù)據(jù)包，u通過判斷發(fā)現(xiàn)與d不在同一方向路段，其簇頭路由表中存在a1、a2等節(jié)點，而a1為岔路口節(jié)點，此時即使a2距離目的簇頭節(jié)點更近，也不選擇其作為下一跳，而選擇岔路口節(jié)點a1作為下一跳，此時a1通過與目的節(jié)點坐標結(jié)合，在不同岔路方向映射節(jié)點a1和a1，通過位置服務判斷與d方向路段一致或距離更近的映射節(jié)點岔路方向為最優(yōu)路段，再通過貪婪算法在此路段進行下一跳節(jié)點選擇，重復上述步驟直到數(shù)據(jù)包轉(zhuǎn)發(fā)至d。

新協(xié)議的完整路由策略是：當數(shù)據(jù)包轉(zhuǎn)發(fā)至岔路口節(jié)點時，先檢查目的節(jié)點是否存在其鄰居表內(nèi)，如果存在則直接轉(zhuǎn)發(fā)目的節(jié)點；否則，判斷目標節(jié)點是否與自己處于同一方向路段，如果處于同一方向路段，則直接通過貪婪轉(zhuǎn)發(fā)尋找距離目的節(jié)點最近節(jié)點作為下一跳；如果通過位置服務判斷自身節(jié)點與目的節(jié)點不在同一路段，則優(yōu)先將數(shù)據(jù)包轉(zhuǎn)發(fā)給岔路中節(jié)點，通過岔路中節(jié)點與目的節(jié)點的地理位置信息，在不同岔路口方向進行基于目的節(jié)點的節(jié)點位置映射，優(yōu)先選擇映射節(jié)點與目的節(jié)點在同一方向路段或距離最近的路段作為最優(yōu)轉(zhuǎn)發(fā)支路，然后在此支路方向選擇適當?shù)南乱惶酚?，重復上述步驟直到數(shù)據(jù)包轉(zhuǎn)發(fā)至目的節(jié)點。當進行數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點在其通信范圍內(nèi)找不到合適下一跳節(jié)點時，暫時緩存數(shù)據(jù)分組，發(fā)現(xiàn)合適下一跳節(jié)點后再將數(shù)據(jù)轉(zhuǎn)發(fā)。這一策略不同于其它路由策略，在岔路口必須優(yōu)先進行最優(yōu)支路選擇，再進行最近節(jié)點選擇，這樣可有效地避免路由冗余，縮短路由跳數(shù)，提高路由效率。

（a）直線路段轉(zhuǎn)發(fā)模式 （b）交叉路段轉(zhuǎn)發(fā)模式

圖3 SCR路由轉(zhuǎn)發(fā)模式

3 仿真結(jié)果及分析

3.1 仿真環(huán)境

該仿真由仿真軟件VanetMobiSim[10]和NS-2.35[11]組成，在4條縱橫交錯道路場景下進行，大小為2 400m*2 400m，各道路中車輛節(jié)點隨機分布，節(jié)點通信半徑為250m。

3.2 仿真結(jié)果分析

為了觀察SCR路由協(xié)議的性能，本仿真通過與AODV[12]、GPRS[13-14]這2種典型的車載網(wǎng)路由協(xié)議進行對比分析。為了評估SCR路由策略對車輛節(jié)點密度的適應性，在仿真場景分別設置30～80個節(jié)點進行仿真。同樣地，為了評估SCR路由策略對節(jié)點運行速度的適應性，節(jié)點速度選取20～50m/s。所有實驗數(shù)據(jù)以10次重復仿真測試后的平均值為準。

圖4展現(xiàn)了節(jié)點數(shù)量變化和網(wǎng)絡的分組投遞率的關系。節(jié)點數(shù)量的增加導致路由控制信息的大幅增加，這勢必造成大量數(shù)據(jù)分組因超時遭到丟棄，從而影響整個網(wǎng)絡的分組投遞率。在AODV協(xié)議中，受到節(jié)點周期的路由維護修復策略，一定程度可使得分組投遞率提高，但同時也造成網(wǎng)絡開銷的加劇。在GPSR協(xié)議中，由于路由選擇過程并不考慮路徑連通性，且在岔路口容易造成環(huán)路現(xiàn)象，所以分組投遞率較低。在SCR協(xié)議中，由于岔路口路由選擇會優(yōu)先進行最佳方向路段選擇，再選取下一跳節(jié)點，且節(jié)點的數(shù)據(jù)暫存有效解決了網(wǎng)絡局部優(yōu)化帶來的問題，所以SCR協(xié)議的網(wǎng)絡分組投遞率相對其它2種路由協(xié)議有較好的效果。

圖4 節(jié)點的分組投遞率（v=30m/s）

圖5展現(xiàn)了節(jié)點速度變化與網(wǎng)絡的分組投遞率的關系。AODV協(xié)議通過修復和重新建立路由，一定程度可使得分組投遞率得到提升。GPSR協(xié)議的路由策略由貪婪算法、邊界轉(zhuǎn)發(fā)模式來傳輸數(shù)據(jù)分組，不完善的路由策略使得傳輸路徑斷裂狀況下，數(shù)據(jù)分組頻繁被拋棄，導致網(wǎng)絡分組投遞率下降。SCR協(xié)議岔路口路段方向預測和局部優(yōu)化時的數(shù)據(jù)暫存策略，增強了網(wǎng)絡連通性，提升了分組投遞率。endprint

圖5 50個節(jié)點分組投遞率

圖6展現(xiàn)了節(jié)點數(shù)量變化對網(wǎng)絡的平均時延的影響。當節(jié)點數(shù)量較小時，網(wǎng)絡鏈路容易斷鏈，導致數(shù)據(jù)延時較高；當節(jié)點數(shù)量較多時，路由控制信息的大幅增加影響數(shù)據(jù)傳輸效率，致使數(shù)據(jù)轉(zhuǎn)發(fā)時延增加。AODV協(xié)議中，需要進行路由發(fā)現(xiàn)和路由維護工作，確認路徑后才進行數(shù)據(jù)轉(zhuǎn)發(fā)，導致網(wǎng)絡的平均延時較高。GPSR路由協(xié)議與SCR路由協(xié)議中，節(jié)點只需要根據(jù)鄰節(jié)點和目的節(jié)點位置信息進行路由決策，邊發(fā)現(xiàn)邊轉(zhuǎn)發(fā)的路由策略可有效降低網(wǎng)絡時延。但是在岔路口路段，GPSR協(xié)議容易造成路由冗余，而SCR協(xié)議優(yōu)先進行方向路段選擇，再進行路由下一跳選擇，降低了路由冗余現(xiàn)象的發(fā)生概率，所以SCR路由性能更好。

圖6 平均延時

圖7展現(xiàn)了路由跳數(shù)隨著傳輸距離增加的變化情況。在傳輸距離較短時，由于SCR基于簇頭進行數(shù)據(jù)轉(zhuǎn)發(fā)，不同簇間需要經(jīng)過簇頭傳輸后才能到達，路由跳數(shù)相對其它2種協(xié)議較高。當傳輸距離增加時，3種路由協(xié)議的路由跳數(shù)均相應增加。隨著傳輸距離的增加，GPSR協(xié)議在岔路口數(shù)據(jù)轉(zhuǎn)發(fā)時容易造成路由冗余，導致路由跳數(shù)大幅增加。SCR協(xié)議通過新的路由策略降低了路由冗余，使得路由跳數(shù)相應降低。AODV協(xié)議中，在數(shù)據(jù)傳輸時才進行路由發(fā)現(xiàn)，并將第一條響應鏈路作為數(shù)據(jù)傳輸路徑來保證路由跳數(shù)最少，所以平均路由跳數(shù)較少。

圖7 平均路由跳數(shù)

4 結(jié)束語

本文通過分析VANET一些典型路由協(xié)議存在的問題，結(jié)合城市道路特點，提出了一種新的適用于城市道路車載網(wǎng)的穩(wěn)定分簇路由策略SCR。SCR協(xié)議通過節(jié)點的運動特征進行分簇，并通過提出的輔簇頭設計理念，避免簇頭在有效期內(nèi)離簇后簇重組帶來的數(shù)據(jù)傳輸問題。根據(jù)節(jié)點的地理位置服務信息和運動可預測性，提出了一種適用于車載網(wǎng)中岔路口數(shù)據(jù)轉(zhuǎn)發(fā)的路由策略。通過實驗仿真表明，SCR協(xié)議可使得簇結(jié)構(gòu)的穩(wěn)定性得到增強，局部優(yōu)化現(xiàn)象帶來的路由冗余問題得到有效減少，端到端平均時延得到降低，分組投遞率得到提升，并有效地控制了路由跳數(shù)，能較好地適應VANET，尤其適用于城市場景中岔路口較多的道路環(huán)境。

參考文獻：

[1] 王芳. 車載自織網(wǎng)路由算法的研究[D]. 桂林： 廣西師范大學， 2012.

[2] Bijan Paul， Md Ibrahim. Md Abu Naser Bikas. VANET Routing Protocols： Pros and Cons[J]. International Journal of Computer Applications， 2011，20（3）： 28-34.

[3] 王昭然，謝顯中，趙鼎新. 車載自組織網(wǎng)絡關鍵技術[J]. 電信學報， 2011（1）： 44-51.

[4] Sherali Zeadally， Ray Hunt. Vehicular Ad-hoc Networks （VANETS）： Status， Results， and Challenges[J]. Tele Communication Systems， 2012，50： 217-241.

[5] Chou Chenming， Lan Kunchan. On the Formation of Vehicle Clusters[A]. 2012 12th International Conference on ITS Telecommunications[C]. Piscataway： IEEE Press， 2012： 574-578.

[6] K Naveen， Komathy Karuppanan. Mobile Cluster Assisted Routing for Urban VANET[A]. Chennai， Recent Trends in Information Technology （ICRTIT）， 2011 International Conference on[C]. Piscataway： IEEE Press， 2011： 296-300.

[7] Song TaoXia Weiwei. A Cluster-Based Directional Routing Protocol in VANET[A]. Nanjing， Communication Technology （ICCT）， 2010 12th IEEE International Conference on[C]. Piscataway： IEEE Press， 2010： 1172-1175.

[8] 陳軍，徐笛，李式巨，等. 一種穩(wěn)健的城市場景車載Ad Hoc路由策略[J]. 電子與信息學報， 2007，29（11）： 2555-2559.

[9] 胡淼，李劍峰. 車載自組織網(wǎng)絡中基于貪婪算法的地理位置路由[J]. 中興通訊技術， 2011，17（3）： 24-28.

[10] Harri J， Filali F， Bonnet C. VanetMobiSim： Generating Realistic Mobility Patterns for VANETs[A]. Proceedings of the 3rd International Workshop on Vehicular Ad Hoc Networks[C]. 2006.

[11] 于斌，孫斌，溫暖，等. NS2與網(wǎng)絡模擬[M]. 北京： 人民郵電出版社， 2007.

[12] Yu Xi， Guo Huaqun， Wong Waichoong. A Reliable Routing Protocol for VANET Communications[A]. Istanbul， Wireless Communications and Mobile Computing Conference （IWCMC）， 2011 7th International[C]. Piscataway： IEEE Press， 2011： 1748-1753.

[13] Karp B， Kung H T. GPSR： Greedy Perimeter Stateless Routing for Wireless Networks[A]. Proe of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking[C]. 2000.

[14] Hu Lili， Ding Zhizhong， Shi Huijing. An Improved GPSR Routing Strategy in VANETs[A]. Shanghai， Wireless Communications， Networking and Mobile Computing （WiCOM）， 2012 8th International Conference on[C]. Piscataway： IEEE Press， 2012： 1-4.endprint