荒漠場景應用的車聯(lián)網及其分簇路由算法

默罕莫德·默森，許凱凱，夏瑋瑋，吳怡，沈連豐

（東南大學 移動通信國家重點實驗室，江蘇 南京 210096）

1 引言

隨著經濟的發(fā)展和汽車的普及，車輛自組織網絡（VANET, vehicular ad hoc networks）已成為人們關注的焦點。早在 2003年，美國聯(lián)邦通信委員會（FCC, Federal Communications Commission）就為車輛間通信劃分了專用頻段，并制訂了第一個車輛自組織網絡通信標準DSRC（dedicated short range communications）；2009年IEEE從802.11標準中擴充了主要用于車輛通信的新標準IEEE 802.11p。車輛自組織網絡通常簡稱為車聯(lián)網，已成為近期的研究熱點，其信息的可靠傳輸受到特別的重視。文獻[1]推導出了城市環(huán)境下借助于路邊輔助設施，車聯(lián)網中上行和下行的連通性概率。文獻[2]運用分布式學習算法動態(tài)地改變相鄰車輛間的傳輸速率使數(shù)據能被更好地接收和聚合。文獻[3]提出了一種DSRC控制信道的分布式跨層設計方法以保證VANET中安全信息的快速可靠傳輸。文獻[4]設計了基于車輛探測消息的功率控制算法，車輛節(jié)點周期性地發(fā)送探測信息，分析網絡中車輛數(shù)目及連通狀態(tài)，繼而自動調整發(fā)射功率來改變網絡擁塞狀況。當車輛較多且沒有可供使用的公眾通信網絡時，車輛構成自組織網絡具有重要的意義，成員間的信息交互通常通過網內的多跳傳輸來實現(xiàn)，因此VANET路由協(xié)議一直備受關注。文獻[5]提出了 2種路由算法 RBVT-R（road-based using vehicular traffic-reactive）和 RBVT-P（road-based using vehicular traffic-proactive），RBVT-R中車輛收到源車輛發(fā)起的路由請求后將其存儲一段時間，在存儲時間內如果沒有收到其他車輛的轉發(fā)信息再進行轉發(fā)，存儲時間與其距源車輛的距離成反比，以此來確保距源車輛越遠的節(jié)點越早轉發(fā)；RBVT-P中每輛車周期性地收集道路上所有車輛信息并存儲，源車輛根據存儲內容進行路由選擇。文獻[6]根據環(huán)境中車輛速度和密度的高低不同分別提出了CBRF（connection-based restricted forwarding）和CLGF（connectionless geographic forwarding）算法，在算法中確定了一個小于通信范圍的距離 r，小于 r范圍的車輛不參與下一跳路由尋找。文獻[7]利用城市中的路邊基礎設施，車輛定時向路邊單元發(fā)送信息，當需要通信時由路邊單元負責進行路由選擇。

隨著車聯(lián)網結構的不斷擴大，分簇路由因其具有拓撲管理方便等特點吸引了很多研究者。在CBRP（cluster based routing protocol）的基礎上，人們從不同的研究角度考慮提出了越來越多的分簇路由算法[8～13]。文獻[8]將自組織映射神經網絡算法應用到VANET中，利用行駛車輛的參數(shù)選擇合適的車輛組網。文獻[9]中將VANET網絡研究背景在地理上分割成統(tǒng)一大小的方格，每個方格內形成一個簇，該算法為了使簇頭和簇頭可以直接通信而將網格劃分較小，導致網絡中簇頭數(shù)目過多。文獻[10]和文獻[11]增加考慮駕駛人的駕車習慣和興趣等因素，增加了網絡中車輛的相關性，提高了網絡生存時間。文獻[12]研究了城市環(huán)境下的 VANET和3G網絡的融合，根據車輛的移動方向、3G網絡的信號強度和VANET裝置的通信距離將網絡分割成不同的區(qū)域，選擇靠近區(qū)域中心位置的車輛為簇頭車輛，當有車輛需要對外通信時，根據每個簇的簇頭車輛速度、信號強度和鏈路穩(wěn)定性選擇網關車輛。文獻[13]中為避免沖突延時將分簇大小約定為k輛車，每輛車使用一個單獨的信道。

到目前為止研究人員都只是將VANET的研究背景鎖定在城市或高速公路等人們經?；顒拥牡胤剑殡S著經濟的不斷發(fā)展，人們的活動范圍已逐漸延伸至沙漠、戈壁等人煙稀少的荒漠地區(qū)。這些地區(qū)路況極不規(guī)則，又缺乏固定的通信設施，給車輛的安全行駛帶來嚴峻的考驗甚至威脅人們的生命安全。雖然現(xiàn)在可用衛(wèi)星或地面移動通信等方式解決車輛間的信息交互問題，但衛(wèi)星通信價格昂貴、帶寬受限，而地面移動通信系統(tǒng)又難以覆蓋到這些荒漠地區(qū)，因此，對于沙漠等場景下車輛自組織網絡的研究具有重要意義。

本文提出一種適用于沙漠、戈壁等荒漠環(huán)境的車輛自組織網絡分簇路由算法，該算法可以提供穩(wěn)定的分簇結構，在源車輛與目的車輛之間建立可靠的路由，同時可以充分利用自組網內部裝備了衛(wèi)星通信終端和地面移動終端的車輛建立自組織網絡內部車輛與外部的通信。

2 系統(tǒng)模型和網絡的邏輯結構

本文研究的車聯(lián)網應用場景是在沙漠、戈壁等荒漠環(huán)境，與城市環(huán)境不同的是：沒有道路、交通標志和建筑物等約束，車輛的運動呈不規(guī)則性；信息傳輸沒有可供利用的基礎設施。在本文的系統(tǒng)模型中做如下設計：每輛車都裝備車聯(lián)網通信終端，車輛可以通過該終端與其通信范圍內的其他車輛進行通信，但無法與VANET外界進行信息交互；部分車上裝備地面移動通信終端可以通過地面公共通信設施與外界網絡（包括Internet）連接；少量車上還裝備衛(wèi)星通信終端可以直接與衛(wèi)星進行通信；極少量車上會同時裝備這2種終端。所提車聯(lián)網的系統(tǒng)模型如圖1所示。

由圖1可見，網絡中車輛分割成不同的簇，每個簇中擁有一個簇頭車輛和若干個簇成員車輛，簇成員與簇頭間最遠距離為k跳通信范圍，簇頭車輛負責協(xié)調和管理簇內所有其他車輛；簇間車輛的信息傳輸可由簇頭通過多跳傳輸來完成。為了方便網內車輛與外界進行通信，在簇頭選舉時優(yōu)先選擇裝備了衛(wèi)星通信終端或地面移動通信終端的車輛。這樣，那些僅裝備了車聯(lián)網通信終端的車輛就可以借助于本簇或鄰簇簇頭車輛的轉發(fā)與外界構成通信鏈路。

圖1 系統(tǒng)模型

可將圖1的系統(tǒng)模型在邏輯上分為3層，形成該種網絡的邏輯結構如圖2所示。

圖2 網絡的邏輯結構

由圖2可見：最底層為每個簇的簇頭車輛與其簇成員構成的簇內通信網絡；第2層為簇頭車輛之間形成的VANET骨干網絡；第3層由裝備衛(wèi)星通信終端或地面移動通信終端的簇頭車輛組成，可以與衛(wèi)星或地面移動通信基礎設施等外界網絡通信，稱為外接網絡層。

3 分簇及其管理

簇是本文模型的基礎，簇頭收集簇成員信息。當需要傳輸信息時，簇成員將信息發(fā)送至本簇的簇頭車輛，簇頭通過相鄰簇頭的多跳轉發(fā)將信息送至目的車輛所在簇的簇頭，最后由該簇頭將信息轉發(fā)至目的車輛。為此首先討論簇的分類，然后討論簇頭的產生及維護。

3.1 簇的分類

如前所述，本文研究的車聯(lián)網共有4種不同類型的車輛：僅裝備車聯(lián)網通信終端、裝備車聯(lián)網通信終端及地面移動通信終端、裝備車聯(lián)網通信終端及衛(wèi)星通信終端、裝備3種通信終端。為方便敘述，依次分別將它們稱為A、B、C、D類車。除A類車外，其他幾類車在一定條件下均可直接與外界通信。根據簇內車輛的種類數(shù)量可將簇結構分為4種，如圖3所示。

圖3 簇結構示意

圖3(a)所示為單一車輛組成的簇，圖中僅給出A類車輛形成的簇，其他車輛成簇情況亦然。因為簇中所有車輛類型相同，所以它們必須經過選舉產生簇頭。如果該簇處于遠離VANET中其他簇所在的位置，B、C、D類車仍可借助本身裝備的地面移動通信終端或衛(wèi)星終端與網中其他車輛或與外界取得聯(lián)系，而A類車則只能處于失去聯(lián)系的狀態(tài)。

圖 3(b)所示為由 2種類型車輛成簇的一種情形，其他情形亦然。當A類車與B、C、D類車形成簇時，通常選擇后者為簇頭。當有多輛B、C、D類車在一個簇中或由B、C、D中2種形成這種簇時，需經過選舉產生簇頭車輛。

圖3(c)和圖3(d)所示分別為由3種、4種車輛成簇的一種情形，其他情形亦然。這2種情況都需要進行選舉產生簇頭車輛。

3.2 簇頭選舉和維護

3.2.1 簇頭選舉原則

在本系統(tǒng)中，依車載通信終端進行簇頭選舉時的優(yōu)先級iP為：衛(wèi)星通信終端、地面通信終端、車聯(lián)網通信終端。若一輛車上同時裝備多種通信終端則以優(yōu)先級最高的為準。在簇頭選舉時做如下假設：①每輛車都擁有一個全網唯一的 ID號；②每輛車上都裝備了GPS或其他衛(wèi)星定位設備，可以通過周期性采集位置信息計算出其速度大小和方向；③網絡中每輛車的最大速度大小為。

若簇的范圍過小，簇頭車輛的數(shù)目就會增加，網絡中的孤立車輛也會變多；若簇的范圍過大，簇成員車輛數(shù)量就會增加，簇頭車輛的負擔也會增大，從而使簇內通信代價變大，同時簇頭車輛與鄰居簇頭之間的通信跳數(shù)也會增加。因此，對分簇的大小需要有一定的約束，在本文中，設每個簇中簇成員車輛與簇頭車輛之間的最大跳數(shù)為 k，每個簇中簇成員車輛數(shù)最大為。

在荒漠環(huán)境中，車輛的運動方向是不規(guī)則的。若簇頭車輛與簇內大部分車輛的運動方向相反或相差較大，將會導致簇成員車輛很快離開本簇范圍加入其他簇，這樣就會增加簇維護開銷。因此，在選取簇頭時需要將車輛的運動方向考慮在內，盡量選擇與大部分車輛行駛方向相近的車為簇頭。同時車輛的速度大小也是重要的考慮因素，為了避免頻繁的簇結構變化，成為簇頭的車輛應該是那些運動速率相對較低的車輛。基于上述考慮，將每輛車成為簇頭車輛的權值表示為

其中，N i為車輛I在k跳范圍內的鄰居車輛數(shù)，N max為本文限定的每個簇中最大的簇成員數(shù)，為車輛I的車速，?輛 I的 k跳范圍內的鄰居車輛 J的車速，m ax為本文限定的車輛的最大速度，Φ為車輛I的k跳鄰居車輛集合，a、b與c均在0與1之間取值，且其關系為

在邏輯結構中，簇頭與鄰居簇頭之間可以直接通信，但在物理結構中鄰居簇頭車輛并不一定在本簇頭車輛的通信范圍之內，需要借助簇成員車輛的轉發(fā)才行。因此，在分簇過程中不僅需要選舉出簇頭車輛，還需要產生出邊界車輛，相鄰簇間的通信將經由邊界車輛。如圖4所示，在由簇頭車輛B1、C1形成的2個相鄰簇中，A6、A7即為它們的邊界車輛，B1與C1間的通信需由它們轉發(fā)。

圖4 相鄰簇間通信的物理鏈路

3.2.2 簇頭選舉過程

簇頭選舉過程具體如下。

1) 每輛車周期性地廣播 HELLO（msg，hop_cnt）消息并轉發(fā)其他車輛的HELLO消息，以此獲得其k跳范圍內所有鄰居車輛的信息。其中，msg為本車的基本信息，包括 ID號、簇頭選舉優(yōu)先級Prior、位置信息loc、速度為跳數(shù)，在廣播消息時將其置 0。每輛車在接收到其他車輛的 HELLO消息后將 msg信息保存，然后判斷hop_cnt，如為k則不再做任何處理，否則將hop_cnt值加1后轉發(fā)。經過一段時間的交互后，每輛車都收集了其k跳范圍內的鄰居車輛信息。

2) 收集完信息后，每輛車根據式(1)計算自己的 iW值。若

中任一式滿足車輛I時，則它將自己升級為簇頭車輛。其中： iP為車輛I的優(yōu)先級， ID-iN 為車輛I的ID編號。即k跳內優(yōu)先級最高的車輛成為簇頭車輛；若有優(yōu)先級相同的則 iW值高的成為簇頭車輛；若仍有相同的則ID號小的成為簇頭車輛。

3) 車輛升級為簇頭車輛后向外廣播簇頭消息HEAD（CluID，head_msg，way_car，hop_cnt），其中，CluID為簇標號，head_msg為簇頭車輛信息，way_car為經過的路由車輛信息，hop_cnt為跳數(shù)。在初始發(fā)送時way_car設置為空，hop_cnt設為0。

收到HEAD消息的車輛將所有信息保存下來，然后判斷hop_cnt的值，若為k，則不做任何處理；否則將本車的msg信息加入way_car中，將hop_cnt值加1后轉發(fā)。

當收到同一CluID的多個消息時，判斷它們的hop_cnt值，保留hop_cnt值小的信息。

當收到來自不同 CluID的消息時，分析head_msg中簇頭車輛的信息，保留優(yōu)先級高的；若優(yōu)先級相同，保留hop_cnt值小的；若仍有相同，則比較 head_msg的速度信息，保留運動方向最接近的信息。

4) 車輛向第 3)步中選出的簇頭車輛發(fā)送入簇申請消息 APPLY（CluID，msg，way_car，hop_cnt），其中，CluID為簇標號，msg為本車信息，way_car為路由車輛信息，hop_cnt為跳數(shù)。收到APPLY消息的其他車輛將自己的msg信息加入way_car中，將hop_cnt值加1后向簇頭車輛轉發(fā)。

5) 簇頭車輛收到APPLY消息后，判斷本簇成員數(shù)量是否小于Nmax，如果小于則將該成員車輛的msg信息及hop_cnt保存至成員列表中，同時回發(fā)ACCP消息；否則直接回發(fā)RFUS消息拒絕加入。

6) 車輛收到簇頭回復的 ACCP消息后確認自己成功入簇，廣播MEMR（CluID，msg，way_car，dis_cnt，hop_cnt）消息，不再參與分簇過程。其中，dis_cnt為其距簇頭車輛的跳數(shù)。

重復該過程直至所有的車輛都成為簇頭或簇成員車輛。

分簇結束后，每輛車根據第6)收到的MEMR消息判斷自己的一跳鄰居節(jié)點中是否有其他簇的成員，如果有則將自己升級為邊界車輛，同時向所在簇簇頭車輛發(fā)送 BUND（msg，way_car，dis_cnt，hop_cnt）消息。

3.2.3 簇的維護

分簇過程結束后，由于車輛的運動會造成簇結構的變化，因此需要不斷對簇結構進行維護，直至車輛退出網絡或網絡消亡。

維護過程主要通過周期性檢查鄰居車輛列表和鄰居簇列表狀態(tài)實現(xiàn)，當普通簇成員車輛離開所在簇和加入新簇時并不會對簇結構產生影響，僅需在簇頭車輛中修改簇成員列表即可。當邊界車輛離開所在簇時，簇頭車輛需重新選擇新的邊界車輛，選擇條件與分簇過程中類似。當兩輛簇頭車輛由于運動靠近時導致簇的融合，此時會觸發(fā)簇頭競爭，競爭選舉的條件與分簇過程中類似，競爭失敗的簇頭車輛發(fā)送簇消亡消息通知本簇成員更新簇頭。當簇頭車輛由于故障等失效時，簇內成員會重新選舉產生新的簇頭，選舉過程與分簇過程中一致。

4 基于分簇的網絡路由協(xié)議

將車聯(lián)網的通信分為網內車輛間和網中車輛與外界2種情況，而前者又可分為同簇和不同簇間2種情況，為此提出一種基于分簇的VANET路由協(xié)議（CBVRP，cluster based VANET routing protocol），為便于比較，又將其稱為CBVRP算法。下面分別對車聯(lián)網的3種通信情況討論該算法。

4.1 簇內路由

當簇成員車輛需要通信時，首先向本簇簇頭車輛發(fā)出申請，簇頭車輛收到申請后判斷是網內通信請求，便首先在本簇簇成員列表中尋找目的車輛，若找到就根據存儲的簇成員位置信息為源車輛和目的車輛選擇一條最佳路由。若該路由需經過簇頭車輛轉發(fā)（如圖4中的A1車與A4車之間的通信），則簇頭車輛將路由申請轉發(fā)至目的車輛；否則將最佳路由發(fā)至源車輛，源車輛與目的車輛間通過該路由進行通信，例如圖4中的A1車與A3車，可直接經過A2車的轉發(fā)進行通信而無需通過簇頭車輛。

假設自組網中每輛車的位置可以用坐標(x, y)表示，則簇頭車輛為車輛I(xi, y i)選擇其下一跳車輛J(xj, yj)的標準為

式中：L為車輛的通信距離，(xd , yd )為目的車輛的位置，(xk , yk )為滿足式(7)的任意車輛的位置。

4.2 簇間路由

當簇頭車輛在本簇成員列表中尋找不到目的車輛時，便向鄰居簇頭發(fā)起路由請求RREQ并等待路由響應，如果在等待時間閾值tr內還未收到路由響應便重新發(fā)送RREQ，若重發(fā)次數(shù)超過最大重發(fā)限制rmax則結束路由尋找過程，如圖5(a)所示。

鄰居簇頭的路由獲取過程如圖5(b)所示。為減少網絡中的信息擁堵，并非所有收到RREQ的鄰居簇都進行處理，只有那些位于路由請求簇頭車輛下游處的鄰居簇頭車輛才會參與路由尋找的過程。此處下游簇頭是指比請求簇頭距目的車輛的距離更近的簇頭車輛。

因此鄰居簇頭在收到RREQ消息后首先判斷自己是否位于請求簇頭的下游，若不是則拋棄該請求，否則進行如下處理。

1) 檢查是否曾經收到過該請求，若收到則拋棄不繼續(xù)處理。

2) 檢查目的車輛是否在本簇，若不在則轉至4)。

3) 向目的車輛轉發(fā)路由申請并等待目的車輛的路由響應RREP，同時轉至5)。

圖5 車輛自組網內部通信路由獲取流程

4) 將自己的msg信息添加至REEQ消息中，并將該消息繼續(xù)向自己下游的鄰居簇頭轉發(fā)并等待下游的路由響應。

5) 若等待時間 tr到達后若仍未收到路由響應則將重發(fā)次數(shù)加1，否則轉至7)。

6) 若超過重發(fā)次數(shù)限制rmax，則結束路由請求過程；否則根據目的車輛是否在本簇中選擇轉至3)或4)。

7) 若收到多個路由響應，則從中選擇一個距目的車輛跳數(shù)最少的路由并將自己的msg信息添加至RREP消息，同時將該消息轉發(fā)至上游簇頭車輛。

如果路由請求失敗，可能是由于目的車輛所在簇與源車輛所在簇相距較遠，無法僅通過車聯(lián)網通信終端建立路由，此時可通過衛(wèi)星通信終端或地面移動通信終端發(fā)起跨地區(qū)的路由尋找。如果仍然找不到，則發(fā)送REER通知源車輛路由尋找失敗。

4.3 簇成員與外界通信

在本文給出的車聯(lián)網模型中，僅有裝備衛(wèi)星通信設備的C、D類車可以始終與外界進行通信；在可以連接地面公共通信網絡時，B類亦然，而D類亦優(yōu)先使用地面公共通信網絡。因此，如果需要與外界通信的簇成員車輛（即源車輛）是這3類中的一種，則最佳情況是可使用地面公共通信網絡進行直接通信，而當沒有地面公共通信網絡可供使用時C、D類將通過衛(wèi)星進行通信。否則，源車輛需要發(fā)起路由尋找，通過其他車輛的轉發(fā)而建立與外界的路由。這種情況下源簇頭車輛和鄰居簇頭車輛的路由獲取過程相同。該路由尋找過程相當于在網絡中泛洪尋找可以建鏈的 B、C、D類車輛，因此所有的鄰居簇頭車輛均需參與路由尋找。

收到外界通信請求的簇頭車輛將進行如下處理。

1) 檢查是否曾經收到過該請求，若收到則拋棄不繼續(xù)處理。

2) 檢查自己裝備的通信終端，若簇頭車輛自己為A類車，則轉至5)。

3) 檢查自己車輛上的地面移動通信終端是否可用，如果可以轉至9)。

4) 檢查本簇中是否有空閑可用的 B、D類車，如果有向它們轉發(fā)路由申請并等待響應，且轉至6)。

5) 向鄰居簇頭車輛轉發(fā)路由申請并等待響應。

6) 若等待時間 tr到達后若仍未收到路由響應則將重發(fā)次數(shù)加1，否則轉至8)。

7) 若超過重發(fā)次數(shù)限制rmax，則結束路由請求過程；否則根據本簇內B、D類車情況選擇轉至4)或5)。

8) 若收到多個路由響應，則從中選擇一個距源車輛跳數(shù)最少的路由響應。

9) 將本車的 msg信息加入到路由響應中并向源車輛發(fā)送該路由響應。

若在該過程中未找到可用的裝備地面移動通信終端的車輛，則源車輛發(fā)起對裝備衛(wèi)星通信終端車輛的尋找，尋找過程與上述類似。如果仍未找到則返回REER表明無法與外界進行通信。

4.4 路由維護

當路由建立后由于車輛的運動可能導致路由的斷鏈，此時，斷開處的車輛會暫時存儲信息并以自己為源車輛向目的車輛重新發(fā)起路由申請，如路由建立成功則將信息發(fā)送至目的車輛，否則向源車輛發(fā)送傳輸失敗信息，由源車輛重新建立到目的車輛的路由。

5 仿真與結果分析

本節(jié)通過仿真將本文提出的 CBVRP算法和CBRP算法進行性能比較。仿真中假設場景中每輛車的初始位置是隨機的，初始速度大小和方向也是隨機的，同時車輛的運動模型為隨機運動模型，即在到達目的點后不停留就立刻以一個新的隨機大小和方向的速度向下一個目的點運動。仿真的場景參數(shù)如表1所示。CBVRP算法中的系數(shù)設置為：簇成員與簇頭間最大跳數(shù) k=2，一個簇中的最大簇成員數(shù) maxN =10，簇頭選舉中權重 a=0.4、b=0.3、c=0.3。

表1 仿真場景參數(shù)

本節(jié)中仿真的性能指標如下。

1) 簇結構穩(wěn)定性：網絡中簇結構的穩(wěn)定程度，可通過網絡中簇結構的重組次數(shù)衡量，重組次數(shù)越低網絡中簇結構越穩(wěn)定。

2) 數(shù)據傳輸成功率：目的車輛收到的數(shù)據分組與源車輛發(fā)送的數(shù)據分組之比。

3) 路由開銷：網絡中總路由分組分組大小與成功發(fā)送的總數(shù)據分組分組大小之比。

圖6所示為網絡中車輛數(shù)100時，車輛自組網中簇結構重組次數(shù)隨時間的變化情況。由圖可見，CBRP的簇結構穩(wěn)定性較差，這是因為CBRP算法中僅僅以車輛的 ID號為依據進行簇頭選舉，選舉ID最小的簇頭，在車輛高速運動的情況下會導致簇頭的頻繁沖突變化，而CBVRP在簇頭選舉時增加了對車輛移動性和鄰居車輛數(shù)量的考慮，降低了簇結構變化的可能，因此具有較高的穩(wěn)定性。

圖6 簇結構重組次數(shù)隨時間變化關系

圖7 數(shù)據傳輸成功率與車輛數(shù)關系

當網絡中的車輛數(shù)從20變化至200時，網絡中數(shù)據傳輸成功率與車輛數(shù)的關系如圖7所示。由圖可見，CBVRP的數(shù)據傳輸成功率比CBRP要高，這也是因為CBRP產生的簇結構不穩(wěn)定重新分簇頻繁導致的。從圖中還可以看出，在車輛數(shù)較少時 2種算法的數(shù)據傳輸成功率都較低，這是由于在仿真中假設車輛在環(huán)境中的位置和運動都是隨機的，在車輛較少時，會出現(xiàn)車輛分布較遠超出其通信范圍的情況，因此會增加分組丟失率。但在本文提出的CBVRP算法中引入了衛(wèi)星和地面移動通信終端的幫助，在車輛間無法直接通信時可以通過衛(wèi)星和地面移動裝置取得聯(lián)系，因此還是可以獲得相對較高的數(shù)據傳輸成功率。在車輛數(shù)較多的情況下，2種算法的傳輸率也呈現(xiàn)下降的趨勢，這是因為隨著車輛數(shù)的增加，路由的平均跳數(shù)增多，路由情況變得復雜，導致分組丟失情況也就隨之變多。

圖8所示為路由開銷隨車輛數(shù)變化關系。在車輛數(shù)增加的情況下CBVRP和CBRP的路由開銷都變大，這是因為車輛數(shù)的增加使得平均路由跳數(shù)增多，路由擁塞情況增多，路由情況變得復雜，因此路由控制報文增多導致了路由開銷的增加。在車輛數(shù)較小時，CBVRP的路由開銷比CBRP大，這是因為CBVRP算法比CBRP復雜，交互信息較多增加了路由開銷，但在車輛數(shù)增加時這一影響變小。同時由于CBRP在路由發(fā)現(xiàn)時采用的是“泛洪”的方式，而CBVRP在簇頭轉發(fā)時考慮了車輛的位置情況，僅在請求簇頭車輛下游的簇頭車輛才會參與路由過程，因此CBVRP的路由開銷要比CBRP小。

圖8 路由開銷與車輛數(shù)關系

6 結束語

本文提出一種適用于沙漠、戈壁等荒漠場景的車聯(lián)網結構及其分簇和路由算法 CBVRP。算法根據網絡中車輛所裝備的通信終端類型和車輛定時發(fā)出的位置、速度和行駛方向等信息對車輛進行分簇并劃為4種類型；在簇內通信和簇間通信時，簇頭車輛為簇成員車輛選擇最合適的路由；在與外界通信時，簇頭車輛為簇成員車輛泛洪尋找能夠建立與外部通信的車輛，即首先選擇最近且可與外部聯(lián)接的地面移動通信終端車輛進行轉發(fā)，在沒有地面公共通信系統(tǒng)可供使用時則選擇最近的裝備有衛(wèi)星通信終端的車輛。仿真結果表明，該算法與傳統(tǒng)的分簇路由算法相比，具有更高的簇結構穩(wěn)定性、更高的數(shù)據傳輸成功率以及更低的路由開銷。

[1] ZHANG W, CHEN Y, YANG Y, et al. Multi-hop connectivity probability in infrastructure-based vehicular networks[J]. IEEE Journal on Selected Areas in Communications, 2012, 30(4)： 740-747.

[2] YU B, XU C, GUO M. Adaptive forwarding delay control for VANET data aggregation[J]. IEEE Transactions on Parallel and Distributed Systems, 2012, 23(1)： 11-18.

[3] MA X, ZHANG J, YIN X, et al. Design and analysis of a robust broadcast scheme for VANET safety-related service[J]. IEEE Transactions on Vehicular Technology, 2012, 61(1)： 46-61.

[4] 吳怡, 沈連豐, 邵震洪等. 基于探測信息的車輛自組織網絡功率控制算法[J]. 東南大學學報（自然科學版）, 2011, 41(4)： 659-664.WU Y, SHEN L F, SHAO Z H, et al. Power control algorithm based on probe message in vehicular ad hoc network[J]. Journal of Southeast University (Natural Science Edition), 2011, 41(4)： 659-664.

[5] NZOUONTA J, RAJGURE N, WANG G, et al. VANET routing on city roads using real-time vehicular traffic information[J]. IEEE Transactions on Vehicular Technology, 2009, 58(7)： 3609-3626.

[6] WANG W, XIE F, CHATTERJEE M. Small-scale and large-scale routing in vehicular ad hoc networks[J]. IEEE Transactions on Vehicular Technology, 2009, 58(9)： 5200-5213.

[7] SALEET H, LANGAR R, NAIK K, et al. Intersection-based geographical routing protocol for VANETs： a proposal and analysis[J].IEEE Transactions on Vehicular Technology, 2011, 60(9)： 4560-4575.

[8] 吳怡, 楊瓊, 吳慶祥等. 一種基于自組織映射神經網絡的 VANET組網算法[J]. 通信學報，2011，32(12)： 136-145.WU Y, YANG Q, WU Q X, et al. A networking algorithm based on self-organizing map neural network for VANET[J]. Journal on Communications, 2011, 32(12)： 136-145.

[9] SONG T, XIA W, SONG T, et al. A cluster-based directional routing protocol in VANET[A]. Proceedings of the 12th IEEE International Conference on Communication Technology[C]. 2010. 1172-1175.

[10] LI Y, ZHAO M, WANG W. Intermittently connected vehicle-to-vehicle networks： detection and analysis[A]. IEEE Global Telecommunications Conference (GLOBECOM 2011)[C]. 2011. 1-6.

[11] CHENG S, HORNG G, CHOU C. Using cellular automata to form car society in vehicular ad hoc networks[J]. IEEE Transactions on Intelligent Transportation Systems, 2011, 12(4)： 1374-1384.

[12] BENSLIMANE A, TALEB T, SIVARAJ R. Dynamic clustering-based adaptive mobile gateway management in integrated VANET-3G heterogeneous wireless networks[J]. IEEE Journal on Selected Areas in Communications, 2011, 29(3)： 559-570.

[13] LAI Y, LIN P, LIAO W, et al. A region-based clustering mechanism for channel access in vehicular ad hoc networks[J]. IEEE Journal on Selected Areas in Communications, 2011, 29(1)： 83-93.