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

（東南大學(xué) 移動(dòng)通信國(guó)家重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210096）

1 引言

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

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

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

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

2 系統(tǒng)模型和網(wǎng)絡(luò)的邏輯結(jié)構(gòu)

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

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

圖1 系統(tǒng)模型

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

圖2 網(wǎng)絡(luò)的邏輯結(jié)構(gòu)

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

3 分簇及其管理

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

3.1 簇的分類

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

圖3 簇結(jié)構(gòu)示意

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

圖 3(b)所示為由 2種類型車輛成簇的一種情形，其他情形亦然。當(dāng)A類車與B、C、D類車形成簇時(shí)，通常選擇后者為簇頭。當(dāng)有多輛B、C、D類車在一個(gè)簇中或由B、C、D中2種形成這種簇時(shí)，需經(jīng)過(guò)選舉產(chǎn)生簇頭車輛。

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

3.2 簇頭選舉和維護(hù)

3.2.1 簇頭選舉原則

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

若簇的范圍過(guò)小，簇頭車輛的數(shù)目就會(huì)增加，網(wǎng)絡(luò)中的孤立車輛也會(huì)變多；若簇的范圍過(guò)大，簇成員車輛數(shù)量就會(huì)增加，簇頭車輛的負(fù)擔(dān)也會(huì)增大，從而使簇內(nèi)通信代價(jià)變大，同時(shí)簇頭車輛與鄰居簇頭之間的通信跳數(shù)也會(huì)增加。因此，對(duì)分簇的大小需要有一定的約束，在本文中，設(shè)每個(gè)簇中簇成員車輛與簇頭車輛之間的最大跳數(shù)為 k，每個(gè)簇中簇成員車輛數(shù)最大為。

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

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

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

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

3.2.2 簇頭選舉過(guò)程

簇頭選舉過(guò)程具體如下。

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

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

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

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

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

當(dāng)收到同一CluID的多個(gè)消息時(shí)，判斷它們的hop_cnt值，保留hop_cnt值小的信息。

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

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

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

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

重復(fù)該過(guò)程直至所有的車輛都成為簇頭或簇成員車輛。

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

3.2.3 簇的維護(hù)

分簇過(guò)程結(jié)束后，由于車輛的運(yùn)動(dòng)會(huì)造成簇結(jié)構(gòu)的變化，因此需要不斷對(duì)簇結(jié)構(gòu)進(jìn)行維護(hù)，直至車輛退出網(wǎng)絡(luò)或網(wǎng)絡(luò)消亡。

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

4 基于分簇的網(wǎng)絡(luò)路由協(xié)議

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

4.1 簇內(nèi)路由

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

假設(shè)自組網(wǎng)中每輛車的位置可以用坐標(biāo)(x, y)表示，則簇頭車輛為車輛I(xi, y i)選擇其下一跳車輛J(xj, yj)的標(biāo)準(zhǔn)為

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

4.2 簇間路由

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

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

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

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

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

3) 向目的車輛轉(zhuǎn)發(fā)路由申請(qǐng)并等待目的車輛的路由響應(yīng)RREP，同時(shí)轉(zhuǎn)至5)。

圖5 車輛自組網(wǎng)內(nèi)部通信路由獲取流程

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

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

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

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

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

4.3 簇成員與外界通信

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

收到外界通信請(qǐng)求的簇頭車輛將進(jìn)行如下處理。

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

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

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

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

5) 向鄰居簇頭車輛轉(zhuǎn)發(fā)路由申請(qǐng)并等待響應(yīng)。

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

7) 若超過(guò)重發(fā)次數(shù)限制rmax，則結(jié)束路由請(qǐng)求過(guò)程；否則根據(jù)本簇內(nèi)B、D類車情況選擇轉(zhuǎn)至4)或5)。

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

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

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

4.4 路由維護(hù)

當(dāng)路由建立后由于車輛的運(yùn)動(dòng)可能導(dǎo)致路由的斷鏈，此時(shí)，斷開(kāi)處的車輛會(huì)暫時(shí)存儲(chǔ)信息并以自己為源車輛向目的車輛重新發(fā)起路由申請(qǐng)，如路由建立成功則將信息發(fā)送至目的車輛，否則向源車輛發(fā)送傳輸失敗信息，由源車輛重新建立到目的車輛的路由。

5 仿真與結(jié)果分析

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

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

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

1) 簇結(jié)構(gòu)穩(wěn)定性：網(wǎng)絡(luò)中簇結(jié)構(gòu)的穩(wěn)定程度，可通過(guò)網(wǎng)絡(luò)中簇結(jié)構(gòu)的重組次數(shù)衡量，重組次數(shù)越低網(wǎng)絡(luò)中簇結(jié)構(gòu)越穩(wěn)定。

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

3) 路由開(kāi)銷：網(wǎng)絡(luò)中總路由分組分組大小與成功發(fā)送的總數(shù)據(jù)分組分組大小之比。

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

圖6 簇結(jié)構(gòu)重組次數(shù)隨時(shí)間變化關(guān)系

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

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

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

圖8 路由開(kāi)銷與車輛數(shù)關(guān)系

6 結(jié)束語(yǔ)

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

[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] 吳怡, 沈連豐, 邵震洪等. 基于探測(cè)信息的車輛自組織網(wǎng)絡(luò)功率控制算法[J]. 東南大學(xué)學(xué)報(bào)（自然科學(xué)版）, 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] 吳怡, 楊瓊, 吳慶祥等. 一種基于自組織映射神經(jīng)網(wǎng)絡(luò)的 VANET組網(wǎng)算法[J]. 通信學(xué)報(bào)，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.