車(chē)輛自組織網(wǎng)絡(luò)中的車(chē)輛路由算法研究

1車(chē)輛網(wǎng)內(nèi)路由隨著經(jīng)濟(jì)的發(fā)展和車(chē)輛的普及，車(chē)輛自組織網(wǎng)絡(luò)（val）成為人們關(guān)注的焦點(diǎn)。早在2003年,美國(guó)聯(lián)邦通信委員會(huì)(FCC,FederalCommunicationsCommission)就為車(chē)輛間通信劃分了專(zhuān)用頻段,并制訂了第一個(gè)車(chē)輛自組織網(wǎng)絡(luò)通信標(biāo)準(zhǔn)DSRC(dedicatedshortrangecommunications);2009年IEEE從802.11標(biāo)準(zhǔn)中擴(kuò)充了主要用于車(chē)輛通信的新標(biāo)準(zhǔn)IEEE802.11p。車(chē)輛自組織網(wǎng)絡(luò)通常簡(jiǎn)稱(chēng)為車(chē)聯(lián)網(wǎng),已成為近期的研究熱點(diǎn),其信息的可靠傳輸受到特別的重視。文獻(xiàn)推導(dǎo)出了城市環(huán)境下借助于路邊輔助設(shè)施,車(chē)聯(lián)網(wǎng)中上行和下行的連通性概率。文獻(xiàn)運(yùn)用分布式學(xué)習(xí)算法動(dòng)態(tài)地改變相鄰車(chē)輛間的傳輸速率使數(shù)據(jù)能被更好地接收和聚合。文獻(xiàn)提出了一種DSRC控制信道的分布式跨層設(shè)計(jì)方法以保證VANET中安全信息的快速可靠傳輸。文獻(xiàn)設(shè)計(jì)了基于車(chē)輛探測(cè)消息的功率控制算法,車(chē)輛節(jié)點(diǎn)周期性地發(fā)送探測(cè)信息,分析網(wǎng)絡(luò)中車(chē)輛數(shù)目及連通狀態(tài),繼而自動(dòng)調(diào)整發(fā)射功率來(lái)改變網(wǎng)絡(luò)擁塞狀況。當(dāng)車(chē)輛較多且沒(méi)有可供使用的公眾通信網(wǎng)絡(luò)時(shí),車(chē)輛構(gòu)成自組織網(wǎng)絡(luò)具有重要的意義,成員間的信息交互通常通過(guò)網(wǎng)內(nèi)的多跳傳輸來(lái)實(shí)現(xiàn),因此VANET路由協(xié)議一直備受關(guān)注。文獻(xiàn)提出了2種路由算法RBVT-R(road-basedusingvehiculatraffic-reactive)和RBVT-P(road-basedusingvehiculartraffic-proactive),RBVT-R中車(chē)輛收到源車(chē)輛發(fā)起的路由請(qǐng)求后將其存儲(chǔ)一段時(shí)間,在存儲(chǔ)時(shí)間內(nèi)如果沒(méi)有收到其他車(chē)輛的轉(zhuǎn)發(fā)信息再進(jìn)行轉(zhuǎn)發(fā),存儲(chǔ)時(shí)間與其距源車(chē)輛的距離成反比,以此來(lái)確保距源車(chē)輛越遠(yuǎn)的節(jié)點(diǎn)越早轉(zhuǎn)發(fā);RBVT-P中每輛車(chē)周期性地收集道路上所有車(chē)輛信息并存儲(chǔ),源車(chē)輛根據(jù)存儲(chǔ)內(nèi)容進(jìn)行路由選擇。文獻(xiàn)根據(jù)環(huán)境中車(chē)輛速度和密度的高低不同分別提出了CBRF(connection-basedrestrictedforwarding)和CLGF(connectionlessgeographicforwarding)算法,在算法中確定了一個(gè)小于通信范圍的距離r,小于r范圍的車(chē)輛不參與下一跳路由尋找。文獻(xiàn)利用城市中的路邊基礎(chǔ)設(shè)施,車(chē)輛定時(shí)向路邊單元發(fā)送信息,當(dāng)需要通信時(shí)由路邊單元負(fù)責(zé)進(jìn)行路由選擇。隨著車(chē)聯(lián)網(wǎng)結(jié)構(gòu)的不斷擴(kuò)大,分簇路由因其具有拓?fù)涔芾矸奖愕忍攸c(diǎn)吸引了很多研究者。在CBRP(clusterbasedroutingprotocol)的基礎(chǔ)上,人們從不同的研究角度考慮提出了越來(lái)越多的分簇路由算法[8~13]。文獻(xiàn)將自組織映射神經(jīng)網(wǎng)絡(luò)算法應(yīng)用到VANET中,利用行駛車(chē)輛的參數(shù)選擇合適的車(chē)輛組網(wǎng)。文獻(xiàn)中將VANET網(wǎng)絡(luò)研究背景在地理上分割成統(tǒng)一大小的方格,每個(gè)方格內(nèi)形成一個(gè)簇,該算法為了使簇頭和簇頭可以直接通信而將網(wǎng)格劃分較小,導(dǎo)致網(wǎng)絡(luò)中簇頭數(shù)目過(guò)多。文獻(xiàn)和文獻(xiàn)增加考慮駕駛?cè)说鸟{車(chē)習(xí)慣和興趣等因素,增加了網(wǎng)絡(luò)中車(chē)輛的相關(guān)性,提高了網(wǎng)絡(luò)生存時(shí)間。文獻(xiàn)研究了城市環(huán)境下的VANET和3G網(wǎng)絡(luò)的融合,根據(jù)車(chē)輛的移動(dòng)方向、3G網(wǎng)絡(luò)的信號(hào)強(qiáng)度和VANET裝置的通信距離將網(wǎng)絡(luò)分割成不同的區(qū)域,選擇靠近區(qū)域中心位置的車(chē)輛為簇頭車(chē)輛,當(dāng)有車(chē)輛需要對(duì)外通信時(shí),根據(jù)每個(gè)簇的簇頭車(chē)輛速度、信號(hào)強(qiáng)度和鏈路穩(wěn)定性選擇網(wǎng)關(guān)車(chē)輛。文獻(xiàn)中為避免沖突延時(shí)將分簇大小約定為k輛車(chē),每輛車(chē)使用一個(gè)單獨(dú)的信道。到目前為止研究人員都只是將VANET的研究背景鎖定在城市或高速公路等人們經(jīng)常活動(dòng)的地方,伴隨著經(jīng)濟(jì)的不斷發(fā)展,人們的活動(dòng)范圍已逐漸延伸至沙漠、戈壁等人煙稀少的荒漠地區(qū)。這些地區(qū)路況極不規(guī)則,又缺乏固定的通信設(shè)施,給車(chē)輛的安全行駛帶來(lái)嚴(yán)峻的考驗(yàn)甚至威脅人們的生命安全。雖然現(xiàn)在可用衛(wèi)星或地面移動(dòng)通信等方式解決車(chē)輛間的信息交互問(wèn)題,但衛(wèi)星通信價(jià)格昂貴、帶寬受限,而地面移動(dòng)通信系統(tǒng)又難以覆蓋到這些荒漠地區(qū),因此,對(duì)于沙漠等場(chǎng)景下車(chē)輛自組織網(wǎng)絡(luò)的研究具有重要意義。本文提出一種適用于沙漠、戈壁等荒漠環(huán)境的車(chē)輛自組織網(wǎng)絡(luò)分簇路由算法,該算法可以提供穩(wěn)定的分簇結(jié)構(gòu),在源車(chē)輛與目的車(chē)輛之間建立可靠的路由,同時(shí)可以充分利用自組網(wǎng)內(nèi)部裝備了衛(wèi)星通信終端和地面移動(dòng)終端的車(chē)輛建立自組織網(wǎng)絡(luò)內(nèi)部車(chē)輛與外部的通信。2車(chē)聯(lián)網(wǎng)的整體模型本文研究的車(chē)聯(lián)網(wǎng)應(yīng)用場(chǎng)景是在沙漠、戈壁等荒漠環(huán)境,與城市環(huán)境不同的是:沒(méi)有道路、交通標(biāo)志和建筑物等約束,車(chē)輛的運(yùn)動(dòng)呈不規(guī)則性;信息傳輸沒(méi)有可供利用的基礎(chǔ)設(shè)施。在本文的系統(tǒng)模型中做如下設(shè)計(jì):每輛車(chē)都裝備車(chē)聯(lián)網(wǎng)通信終端,車(chē)輛可以通過(guò)該終端與其通信范圍內(nèi)的其他車(chē)輛進(jìn)行通信,但無(wú)法與VANET外界進(jìn)行信息交互;部分車(chē)上裝備地面移動(dòng)通信終端可以通過(guò)地面公共通信設(shè)施與外界網(wǎng)絡(luò)(包括Internet)連接;少量車(chē)上還裝備衛(wèi)星通信終端可以直接與衛(wèi)星進(jìn)行通信;極少量車(chē)上會(huì)同時(shí)裝備這2種終端。所提車(chē)聯(lián)網(wǎng)的系統(tǒng)模型如圖1所示。由圖1可見(jiàn),網(wǎng)絡(luò)中車(chē)輛分割成不同的簇,每個(gè)簇中擁有一個(gè)簇頭車(chē)輛和若干個(gè)簇成員車(chē)輛,簇成員與簇頭間最遠(yuǎn)距離為k跳通信范圍,簇頭車(chē)輛負(fù)責(zé)協(xié)調(diào)和管理簇內(nèi)所有其他車(chē)輛;簇間車(chē)輛的信息傳輸可由簇頭通過(guò)多跳傳輸來(lái)完成。為了方便網(wǎng)內(nèi)車(chē)輛與外界進(jìn)行通信,在簇頭選舉時(shí)優(yōu)先選擇裝備了衛(wèi)星通信終端或地面移動(dòng)通信終端的車(chē)輛。這樣,那些僅裝備了車(chē)聯(lián)網(wǎng)通信終端的車(chē)輛就可以借助于本簇或鄰簇簇頭車(chē)輛的轉(zhuǎn)發(fā)與外界構(gòu)成通信鏈路?？蓪D1的系統(tǒng)模型在邏輯上分為3層,形成該種網(wǎng)絡(luò)的邏輯結(jié)構(gòu)如圖2所示。由圖2可見(jiàn):最底層為每個(gè)簇的簇頭車(chē)輛與其簇成員構(gòu)成的簇內(nèi)通信網(wǎng)絡(luò);第2層為簇頭車(chē)輛之間形成的VANET骨干網(wǎng)絡(luò);第3層由裝備衛(wèi)星通信終端或地面移動(dòng)通信終端的簇頭車(chē)輛組成,可以與衛(wèi)星或地面移動(dòng)通信基礎(chǔ)設(shè)施等外界網(wǎng)絡(luò)通信,稱(chēng)為外接網(wǎng)絡(luò)層。3打造高效的打造通路簇是本文模型的基礎(chǔ),簇頭收集簇成員信息。當(dāng)需要傳輸信息時(shí),簇成員將信息發(fā)送至本簇的簇頭車(chē)輛,簇頭通過(guò)相鄰簇頭的多跳轉(zhuǎn)發(fā)將信息送至目的車(chē)輛所在簇的簇頭,最后由該簇頭將信息轉(zhuǎn)發(fā)至目的車(chē)輛。為此首先討論簇的分類(lèi),然后討論簇頭的產(chǎn)生及維護(hù)。3.1打造多車(chē)輛成簇如前所述,本文研究的車(chē)聯(lián)網(wǎng)共有4種不同類(lèi)型的車(chē)輛:僅裝備車(chē)聯(lián)網(wǎng)通信終端、裝備車(chē)聯(lián)網(wǎng)通信終端及地面移動(dòng)通信終端、裝備車(chē)聯(lián)網(wǎng)通信終端及衛(wèi)星通信終端、裝備3種通信終端。為方便敘述,依次分別將它們稱(chēng)為A、B、C、D類(lèi)車(chē)。除A類(lèi)車(chē)外,其他幾類(lèi)車(chē)在一定條件下均可直接與外界通信。根據(jù)簇內(nèi)車(chē)輛的種類(lèi)數(shù)量可將簇結(jié)構(gòu)分為4種,如圖3所示。圖3(a)所示為單一車(chē)輛組成的簇,圖中僅給出A類(lèi)車(chē)輛形成的簇,其他車(chē)輛成簇情況亦然。因?yàn)榇刂兴熊?chē)輛類(lèi)型相同,所以它們必須經(jīng)過(guò)選舉產(chǎn)生簇頭。如果該簇處于遠(yuǎn)離VANET中其他簇所在的位置,B、C、D類(lèi)車(chē)仍可借助本身裝備的地面移動(dòng)通信終端或衛(wèi)星終端與網(wǎng)中其他車(chē)輛或與外界取得聯(lián)系,而A類(lèi)車(chē)則只能處于失去聯(lián)系的狀態(tài)。圖3(b)所示為由2種類(lèi)型車(chē)輛成簇的一種情形,其他情形亦然。當(dāng)A類(lèi)車(chē)與B、C、D類(lèi)車(chē)形成簇時(shí),通常選擇后者為簇頭。當(dāng)有多輛B、C、D類(lèi)車(chē)在一個(gè)簇中或由B、C、D中2種形成這種簇時(shí),需經(jīng)過(guò)選舉產(chǎn)生簇頭車(chē)輛。圖3(c)和圖3(d)所示分別為由3種、4種車(chē)輛成簇的一種情形,其他情形亦然。這2種情況都需要進(jìn)行選舉產(chǎn)生簇頭車(chē)輛。3.2領(lǐng)導(dǎo)人的選舉和維護(hù)3.2.1簇頭車(chē)輛的運(yùn)動(dòng)方向和邊界車(chē)輛在本系統(tǒng)中,依車(chē)載通信終端進(jìn)行簇頭選舉時(shí)的優(yōu)先級(jí)Pi為:衛(wèi)星通信終端、地面通信終端、車(chē)聯(lián)網(wǎng)通信終端。若一輛車(chē)上同時(shí)裝備多種通信終端則以?xún)?yōu)先級(jí)最高的為準(zhǔn)。在簇頭選舉時(shí)做如下假設(shè):(1)每輛車(chē)都擁有一個(gè)全網(wǎng)唯一的ID號(hào);(2)每輛車(chē)上都裝備了GPS或其他衛(wèi)星定位設(shè)備,可以通過(guò)周期性采集位置信息計(jì)算出其速度大小和方向;(3)網(wǎng)絡(luò)中每輛車(chē)的最大速度大小為Vmax。若簇的范圍過(guò)小,簇頭車(chē)輛的數(shù)目就會(huì)增加,網(wǎng)絡(luò)中的孤立車(chē)輛也會(huì)變多;若簇的范圍過(guò)大,簇成員車(chē)輛數(shù)量就會(huì)增加,簇頭車(chē)輛的負(fù)擔(dān)也會(huì)增大,從而使簇內(nèi)通信代價(jià)變大,同時(shí)簇頭車(chē)輛與鄰居簇頭之間的通信跳數(shù)也會(huì)增加。因此,對(duì)分簇的大小需要有一定的約束,在本文中,設(shè)每個(gè)簇中簇成員車(chē)輛與簇頭車(chē)輛之間的最大跳數(shù)為k,每個(gè)簇中簇成員車(chē)輛數(shù)最大為Nmax。在荒漠環(huán)境中,車(chē)輛的運(yùn)動(dòng)方向是不規(guī)則的。若簇頭車(chē)輛與簇內(nèi)大部分車(chē)輛的運(yùn)動(dòng)方向相反或相差較大,將會(huì)導(dǎo)致簇成員車(chē)輛很快離開(kāi)本簇范圍加入其他簇,這樣就會(huì)增加簇維護(hù)開(kāi)銷(xiāo)。因此,在選取簇頭時(shí)需要將車(chē)輛的運(yùn)動(dòng)方向考慮在內(nèi),盡量選擇與大部分車(chē)輛行駛方向相近的車(chē)為簇頭。同時(shí)車(chē)輛的速度大小也是重要的考慮因素,為了避免頻繁的簇結(jié)構(gòu)變化,成為簇頭的車(chē)輛應(yīng)該是那些運(yùn)動(dòng)速率相對(duì)較低的車(chē)輛?；谏鲜隹紤],將每輛車(chē)成為簇頭車(chē)輛的權(quán)值表示為在邏輯結(jié)構(gòu)中,簇頭與鄰居簇頭之間可以直接通信,但在物理結(jié)構(gòu)中鄰居簇頭車(chē)輛并不一定在本簇頭車(chē)輛的通信范圍之內(nèi),需要借助簇成員車(chē)輛的轉(zhuǎn)發(fā)才行。因此,在分簇過(guò)程中不僅需要選舉出簇頭車(chē)輛,還需要產(chǎn)生出邊界車(chē)輛,相鄰簇間的通信將經(jīng)由邊界車(chē)輛。如圖4所示,在由簇頭車(chē)輛B1、C1形成的2個(gè)相鄰簇中,A6、A7即為它們的邊界車(chē)輛,B1與C1間的通信需由它們轉(zhuǎn)發(fā)。3.2.2簇頭車(chē)輛id-i簇頭選舉過(guò)程具體如下。1)每輛車(chē)周期性地廣播HELLO(msg,hop_cnt)消息并轉(zhuǎn)發(fā)其他車(chē)輛的HELLO消息,以此獲得其k跳范圍內(nèi)所有鄰居車(chē)輛的信息。其中,msg為本車(chē)的基本信息,包括ID號(hào)、簇頭選舉優(yōu)先級(jí)Prior、位置信息loc、速度;hop_cnt為跳數(shù),在廣播消息時(shí)將其置0。每輛車(chē)在接收到其他車(chē)輛的HELLO消息后將msg信息保存,然后判斷hop_cnt,如為k則不再做任何處理,否則將hop_cnt值加1后轉(zhuǎn)發(fā)。經(jīng)過(guò)一段時(shí)間的交互后,每輛車(chē)都收集了其k跳范圍內(nèi)的鄰居車(chē)輛信息。2)收集完信息后,每輛車(chē)根據(jù)式(1)計(jì)算自己的Wi值。若中任一式滿(mǎn)足車(chē)輛I時(shí),則它將自己升級(jí)為簇頭車(chē)輛。其中:Pi為車(chē)輛I的優(yōu)先級(jí),NID-i為車(chē)輛I的ID編號(hào)。即k跳內(nèi)優(yōu)先級(jí)最高的車(chē)輛成為簇頭車(chē)輛;若有優(yōu)先級(jí)相同的則Wi值高的成為簇頭車(chē)輛;若仍有相同的則ID號(hào)小的成為簇頭車(chē)輛。3)車(chē)輛升級(jí)為簇頭車(chē)輛后向外廣播簇頭消息HEAD(CluID,head_msg,way_car,hop_cnt),其中,CluID為簇標(biāo)號(hào),head_msg為簇頭車(chē)輛信息,way_car為經(jīng)過(guò)的路由車(chē)輛信息,hop_cnt為跳數(shù)。在初始發(fā)送時(shí)way_car設(shè)置為空,hop_cnt設(shè)為0。收到HEAD消息的車(chē)輛將所有信息保存下來(lái),然后判斷hop_cnt的值,若為k,則不做任何處理;否則將本車(chē)的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中簇頭車(chē)輛的信息,保留優(yōu)先級(jí)高的;若優(yōu)先級(jí)相同,保留hop_cnt值小的;若仍有相同,則比較head_msg的速度信息,保留運(yùn)動(dòng)方向最接近的信息。4)車(chē)輛向第3)步中選出的簇頭車(chē)輛發(fā)送入簇申請(qǐng)消息APPLY(CluID,msg,way_car,hop_cnt),其中,CluID為簇標(biāo)號(hào),msg為本車(chē)信息,way_car為路由車(chē)輛信息,hop_cnt為跳數(shù)。收到APPLY消息的其他車(chē)輛將自己的msg信息加入way_car中,將hop_cnt值加1后向簇頭車(chē)輛轉(zhuǎn)發(fā)。5)簇頭車(chē)輛收到APPLY消息后,判斷本簇成員數(shù)量是否小于Nmax,如果小于則將該成員車(chē)輛的msg信息及hop_cnt保存至成員列表中,同時(shí)回發(fā)ACCP消息;否則直接回發(fā)RFUS消息拒絕加入。6)車(chē)輛收到簇頭回復(fù)的ACCP消息后確認(rèn)自己成功入簇,廣播MEMR(CluID,msg,way_car,dis_cnt,hop_cnt)消息,不再參與分簇過(guò)程。其中,dis_cnt為其距簇頭車(chē)輛的跳數(shù)。重復(fù)該過(guò)程直至所有的車(chē)輛都成為簇頭或簇成員車(chē)輛。分簇結(jié)束后,每輛車(chē)根據(jù)第6)收到的MEMR消息判斷自己的一跳鄰居節(jié)點(diǎn)中是否有其他簇的成員,如果有則將自己升級(jí)為邊界車(chē)輛,同時(shí)向所在簇簇頭車(chē)輛發(fā)送BUND(msg,way_car,dis_cnt,hop_cnt)消息。3.2.3簇成員保障機(jī)制分簇過(guò)程結(jié)束后,由于車(chē)輛的運(yùn)動(dòng)會(huì)造成簇結(jié)構(gòu)的變化,因此需要不斷對(duì)簇結(jié)構(gòu)進(jìn)行維護(hù),直至車(chē)輛退出網(wǎng)絡(luò)或網(wǎng)絡(luò)消亡。維護(hù)過(guò)程主要通過(guò)周期性檢查鄰居車(chē)輛列表和鄰居簇列表狀態(tài)實(shí)現(xiàn),當(dāng)普通簇成員車(chē)輛離開(kāi)所在簇和加入新簇時(shí)并不會(huì)對(duì)簇結(jié)構(gòu)產(chǎn)生影響,僅需在簇頭車(chē)輛中修改簇成員列表即可。當(dāng)邊界車(chē)輛離開(kāi)所在簇時(shí),簇頭車(chē)輛需重新選擇新的邊界車(chē)輛,選擇條件與分簇過(guò)程中類(lèi)似。當(dāng)兩輛簇頭車(chē)輛由于運(yùn)動(dòng)靠近時(shí)導(dǎo)致簇的融合,此時(shí)會(huì)觸發(fā)簇頭競(jìng)爭(zhēng),競(jìng)爭(zhēng)選舉的條件與分簇過(guò)程中類(lèi)似,競(jìng)爭(zhēng)失敗的簇頭車(chē)輛發(fā)送簇消亡消息通知本簇成員更新簇頭。當(dāng)簇頭車(chē)輛由于故障等失效時(shí),簇內(nèi)成員會(huì)重新選舉產(chǎn)生新的簇頭,選舉過(guò)程與分簇過(guò)程中一致。4基于分簇的vep協(xié)議將車(chē)聯(lián)網(wǎng)的通信分為網(wǎng)內(nèi)車(chē)輛間和網(wǎng)中車(chē)輛與外界2種情況,而前者又可分為同簇和不同簇間2種情況,為此提出一種基于分簇的VANET路由協(xié)議(CBVRP,clusterbasedVANETroutingprotocol),為便于比較,又將其稱(chēng)為CBVRP算法。下面分別對(duì)車(chē)聯(lián)網(wǎng)的3種通信情況討論該算法。4.1由最佳路由轉(zhuǎn)發(fā)至目的車(chē)輛當(dāng)簇成員車(chē)輛需要通信時(shí),首先向本簇簇頭車(chē)輛發(fā)出申請(qǐng),簇頭車(chē)輛收到申請(qǐng)后判斷是網(wǎng)內(nèi)通信請(qǐng)求,便首先在本簇簇成員列表中尋找目的車(chē)輛,若找到就根據(jù)存儲(chǔ)的簇成員位置信息為源車(chē)輛和目的車(chē)輛選擇一條最佳路由。若該路由需經(jīng)過(guò)簇頭車(chē)輛轉(zhuǎn)發(fā)(如圖4中的A1車(chē)與A4車(chē)之間的通信),則簇頭車(chē)輛將路由申請(qǐng)轉(zhuǎn)發(fā)至目的車(chē)輛;否則將最佳路由發(fā)至源車(chē)輛,源車(chē)輛與目的車(chē)輛間通過(guò)該路由進(jìn)行通信,例如圖4中的A1車(chē)與A3車(chē),可直接經(jīng)過(guò)A2車(chē)的轉(zhuǎn)發(fā)進(jìn)行通信而無(wú)需通過(guò)簇頭車(chē)輛。假設(shè)自組網(wǎng)中每輛車(chē)的位置可以用坐標(biāo)(x,y)表示,則簇頭車(chē)輛為車(chē)輛I(xi,yi)選擇其下一跳車(chē)輛J(xj,yj)的標(biāo)準(zhǔn)為式中:L為車(chē)輛的通信距離,(xd,yd)為目的車(chē)輛的位置,(xk,yk)為滿(mǎn)足式(7)的任意車(chē)輛的位置。4.2路由尋找過(guò)程當(dāng)簇頭車(chē)輛在本簇成員列表中尋找不到目的車(chē)輛時(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)求簇頭車(chē)輛下游處的鄰居簇頭車(chē)輛才會(huì)參與路由尋找的過(guò)程。此處下游簇頭是指比請(qǐng)求簇頭距目的車(chē)輛的距離更近的簇頭車(chē)輛。因此鄰居簇頭在收到RREQ消息后首先判斷自己是否位于請(qǐng)求簇頭的下游,若不是則拋棄該請(qǐng)求,否則進(jìn)行如下處理。1)檢查是否曾經(jīng)收到過(guò)該請(qǐng)求,若收到則拋棄不繼續(xù)處理。2)檢查目的車(chē)輛是否在本簇,若不在則轉(zhuǎn)至4)。3)向目的車(chē)輛轉(zhuǎn)發(fā)路由申請(qǐng)并等待目的車(chē)輛的路由響應(yīng)RREP,同時(shí)轉(zhuǎn)至5)。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ù)目的車(chē)輛是否在本簇中選擇轉(zhuǎn)至3)或4)。7)若收到多個(gè)路由響應(yīng),則從中選擇一個(gè)距目的車(chē)輛跳數(shù)最少的路由并將自己的msg信息添加至RREP消息,同時(shí)將該消息轉(zhuǎn)發(fā)至上游簇頭車(chē)輛。如果路由請(qǐng)求失敗,可能是由于目的車(chē)輛所在簇與源車(chē)輛所在簇相距較遠(yuǎn),無(wú)法僅通過(guò)車(chē)聯(lián)網(wǎng)通信終端建立路由,此時(shí)可通過(guò)衛(wèi)星通信終端或地面移動(dòng)通信終端發(fā)起跨地區(qū)的路由尋找。如果仍然找不到,則發(fā)送REER通知源車(chē)輛路由尋找失敗。4.3打造新型路由回收系統(tǒng)在本文給出的車(chē)聯(lián)網(wǎng)模型中,僅有裝備衛(wèi)星通信設(shè)備的C、D類(lèi)車(chē)可以始終與外界進(jìn)行通信;在可以連接地面公共通信網(wǎng)絡(luò)時(shí),B類(lèi)亦然,而D類(lèi)亦優(yōu)先使用地面公共通信網(wǎng)絡(luò)。因此,如果需要與外界通信的簇成員車(chē)輛(即源車(chē)輛)是這3類(lèi)中的一種,則最佳情況是可使用地面公共通信網(wǎng)絡(luò)進(jìn)行直接通信,而當(dāng)沒(méi)有地面公共通信網(wǎng)絡(luò)可供使用時(shí)C、D類(lèi)將通過(guò)衛(wèi)星進(jìn)行通信。否則,源車(chē)輛需要發(fā)起路由尋找,通過(guò)其他車(chē)輛的轉(zhuǎn)發(fā)而建立與外界的路由。這種情況下源簇頭車(chē)輛和鄰居簇頭車(chē)輛的路由獲取過(guò)程相同。該路由尋找過(guò)程相當(dāng)于在網(wǎng)絡(luò)中泛洪尋找可以建鏈的B、C、D類(lèi)車(chē)輛,因此所有的鄰居簇頭車(chē)輛均需參與路由尋找。收到外界通信請(qǐng)求的簇頭車(chē)輛將進(jìn)行如下處理。1)檢查是否曾經(jīng)收到過(guò)該請(qǐng)求,若收到則拋棄不繼續(xù)處理。2)檢查自己裝備的通信終端,若簇頭車(chē)輛自己為A類(lèi)車(chē),則轉(zhuǎn)至5)。3)檢查自己車(chē)輛上的地面移動(dòng)通信終端是否可用,如果可以轉(zhuǎn)至9)。4)檢查本簇中是否有空閑可用的B、D類(lèi)車(chē),如果有向它們轉(zhuǎn)發(fā)路由申請(qǐng)并等待響應(yīng),且轉(zhuǎn)至6)。5)向鄰居簇頭車(chē)輛轉(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類(lèi)車(chē)情況選擇轉(zhuǎn)至4)或5)。8)若收到多個(gè)路由響應(yīng),則從中選擇一個(gè)距源車(chē)輛跳數(shù)最少的路由響應(yīng)。9)將本車(chē)的msg信息加入到路由響應(yīng)中并向源車(chē)輛發(fā)送該路由響應(yīng)。若在該過(guò)程中未找到可用的裝備地面移動(dòng)通信終端的車(chē)輛,則源車(chē)輛發(fā)起對(duì)裝備衛(wèi)星通信終端車(chē)輛的尋找,尋找過(guò)程與上述類(lèi)似。如果仍未找到則返回REER表明無(wú)法與外界進(jìn)行通信。4.4重新發(fā)起路由當(dāng)路由建立后由于車(chē)輛的運(yùn)動(dòng)可能導(dǎo)致路由的斷鏈,此時(shí),斷開(kāi)處的車(chē)輛會(huì)暫時(shí)存儲(chǔ)信息并以自己為源車(chē)輛向目的車(chē)輛重新發(fā)起路由申請(qǐng),如路由建立成功則將信息發(fā)送至目的車(chē)輛,否則向源車(chē)輛發(fā)送傳輸失敗信息,由源車(chē)輛重新建立到目的車(chē)輛的路由。5數(shù)據(jù)組分及路由開(kāi)裂本節(jié)通過(guò)仿真將本文提出的CBVRP算法和CBRP算法進(jìn)行性能比較。仿真中假設(shè)場(chǎng)景中每輛車(chē)的初始位置是隨機(jī)的,初始速度大小和方向也是隨機(jī)的,同時(shí)車(chē)輛的運(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ù)Nmax=10,簇頭選舉中權(quán)重a=0.4、b=0.3、c=0.3。本節(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ù)傳輸成功率:目的車(chē)輛收到的數(shù)據(jù)分組與源車(chē)輛發(fā)送的數(shù)據(jù)分組之比。3)路由開(kāi)銷(xiāo):網(wǎng)絡(luò)中總路由分組分組大小與成功發(fā)送的總數(shù)據(jù)分組分組大小之比。圖6所示為網(wǎng)絡(luò)中車(chē)輛數(shù)100時(shí),車(chē)輛自組網(wǎng)中簇結(jié)構(gòu)重組次數(shù)隨時(shí)間的變化情況。由圖可見(jiàn),CBRP的簇結(jié)構(gòu)穩(wěn)定性較差,這是因?yàn)镃BRP算法中僅僅以車(chē)輛的ID號(hào)為依據(jù)進(jìn)行簇頭選舉,選舉ID最小的簇頭,在車(chē)輛高速運(yùn)動(dòng)的情況下會(huì)導(dǎo)致簇頭的頻繁沖突變化,而CBVRP在簇頭選舉時(shí)增加了對(duì)車(chē)輛移動(dòng)性和鄰居車(chē)輛數(shù)量的考慮,降低了簇結(jié)構(gòu)變化的可能,因此具有較高的穩(wěn)定性。當(dāng)網(wǎng)絡(luò)中的車(chē)輛數(shù)從20變化至200時(shí),網(wǎng)絡(luò)中數(shù)據(jù)傳輸成功率與車(chē)輛數(shù)的關(guān)系如圖7所示。由圖可見(jiàn),CBVRP的數(shù)據(jù)傳輸成功率比CBRP要高,這也是因?yàn)镃BRP產(chǎn)生的簇結(jié)構(gòu)不穩(wěn)定重新分簇頻繁導(dǎo)致的。從圖中還可以看出,在車(chē)輛數(shù)較少時(shí)2種算法的數(shù)據(jù)傳輸成功率都較低,這是由于在仿真中假設(shè)車(chē)輛在環(huán)境中的位