基于車載自組網(wǎng)通信終端和運(yùn)動(dòng)信息的容忍時(shí)延網(wǎng)絡(luò)分簇路由算法

和 何，李琳琳，路云飛

(火箭軍工程大學(xué)，信息工程系，西安 710025)

0 引言

隨著智能交通系統(tǒng)[1]的發(fā)展，車載自組網(wǎng)(Vehicular Ad Hoc NETwork, VANET)作為一種新型通信網(wǎng)絡(luò)應(yīng)運(yùn)而生，美國(guó)聯(lián)邦通信委員會(huì)為其制定了通信標(biāo)準(zhǔn)IEEE802.11p。由于VANET是容忍時(shí)延網(wǎng)絡(luò)(Delay Tolerant Network, DTN)的一種典型應(yīng)用[2], 其基于傳統(tǒng)分簇路由(Cluster Based Routing Protocal, CBRP)算法[3]的改進(jìn)型算法已成為近年來(lái)DTN的一個(gè)新的研究熱點(diǎn)。文獻(xiàn)[4]提出一種雙層結(jié)構(gòu)的分簇算法，首先基于權(quán)重的通信質(zhì)量進(jìn)行分簇，其次將分簇后的車載節(jié)點(diǎn)劃分為自組織層和對(duì)等層，自組織層使用普通的車輛通信方式進(jìn)行通信，對(duì)等層則用3G網(wǎng)絡(luò)、LTE(Long Term Evolution)網(wǎng)絡(luò)為代表的更可靠的通信方式進(jìn)行通信；文獻(xiàn)[5]提出的一種基于介質(zhì)訪問控制層(Media Access Control, MAC)層時(shí)延上限的自適應(yīng)(MAC upper band Delay Based Adaptive, MDBA)分簇算法，利用車輛節(jié)點(diǎn)的速度、加速度、位置和目的地設(shè)計(jì)簇頭選擇算法；通過簇維護(hù)自適應(yīng)調(diào)整分簇網(wǎng)絡(luò)拓?fù)涞淖兓?。文獻(xiàn)[6]提出的一種基于分簇的多信道車載網(wǎng)MAC協(xié)議，簇內(nèi)采用非競(jìng)爭(zhēng)的時(shí)分多址(Time Division Multiple Access, TDMA)機(jī)制通信，異簇采用具有競(jìng)爭(zhēng)性的載波偵聽多路訪問/沖突避免(Carrier Sense Multiple Access with Collision Detection, CSMA-CA)機(jī)制，得到一種拓?fù)湎鄬?duì)穩(wěn)定的車輛分簇算法。此外，文獻(xiàn)[7]將VANET分簇應(yīng)用于車輛碰撞警告信息傳輸中，文獻(xiàn)[8]研究了一種基于分布式的VANET分簇路由機(jī)制，文獻(xiàn)[9]運(yùn)用灰色系統(tǒng)理論實(shí)現(xiàn)了VANET的分簇算法。文獻(xiàn)[10]根據(jù)車輛所裝備的地面移動(dòng)通信終端和衛(wèi)星通信終端，提出一種包括簇內(nèi)、簇間和簇成員與外界的分簇網(wǎng)絡(luò)路由協(xié)議。文獻(xiàn)[11]基于位置的貪婪路由算法、基于錨節(jié)點(diǎn)路由算法、基于街道集路由算法和基于簇路由算法，著重于這些特點(diǎn)設(shè)計(jì)每類算法。文獻(xiàn)[12]提出了一種利用車輛的位置和移動(dòng)方向的基于自動(dòng)分簇的數(shù)據(jù)傳輸方案。自動(dòng)分簇在網(wǎng)絡(luò)中配置多個(gè)簇且只有管理簇的簇頭才能存儲(chǔ)數(shù)據(jù)包。不管何時(shí)與新簇相遇，原簇的簇頭基于自身位置、目的節(jié)點(diǎn)的位置以及簇的移動(dòng)方向決定是否應(yīng)該將數(shù)據(jù)包轉(zhuǎn)發(fā)給新簇。文獻(xiàn)[13]提出一種關(guān)于VANET的新型多跳分簇方案，該方案通過車輛之間的鄰里關(guān)系來(lái)產(chǎn)生簇頭。其基于一個(gè)合理的假設(shè)：車輛不能確定多跳鄰居中的哪輛車最適合作其簇頭，但可以很容易地掌握一跳鄰居內(nèi)哪輛車最適合作其簇頭。因此，車輛可以通過最穩(wěn)定的車輛來(lái)選擇其簇頭，兩車間基于歷史跟蹤信息的相對(duì)流動(dòng)性使車輛能夠選擇要跟隨的目標(biāo)。文獻(xiàn)[14]分析了簇式車載傳感器網(wǎng)絡(luò)的性能，利用層次化分散檢測(cè)方案對(duì)一種可觀察到的空間恒定現(xiàn)象的狀態(tài)進(jìn)行了估計(jì)。簇式處理效率更高，架構(gòu)可伸縮。文獻(xiàn)[15]提出一種用于車輛專用網(wǎng)絡(luò)的基于傳輸功率的分簇算法，并應(yīng)用于緊急消息廣播技術(shù)。當(dāng)VANET受到不同類型的攻擊時(shí)，完成諸如消息保密、可靠性和驗(yàn)證等保護(hù)需求。文獻(xiàn)[16]提出了一種新的車輛云架構(gòu)，利用分簇技術(shù)對(duì)資源進(jìn)行分組，協(xié)同提供資源，解決了資源限制問題。更具體地說(shuō)，在簇頭選舉過程中引入模糊邏輯，實(shí)現(xiàn)了簇結(jié)構(gòu)的靈活性。文獻(xiàn)[17]提出了一種基于移動(dòng)網(wǎng)絡(luò)的分簇算法，該算法以分布式的關(guān)聯(lián)傳播算法來(lái)形成簇。該算法考慮了在簇形成過程中的節(jié)點(diǎn)遷移率，產(chǎn)生了高穩(wěn)定性的簇。

近年來(lái)面向挑戰(zhàn)網(wǎng)絡(luò)諸如戰(zhàn)場(chǎng)和災(zāi)難搜救環(huán)境下對(duì)DTN路由算法的研究也是一個(gè)研究熱點(diǎn)。文獻(xiàn)[18]針對(duì)戰(zhàn)場(chǎng)毀傷條件下MANET普通路由算法性能下降的問題，融合了普通MANET路由和DTN路由設(shè)計(jì)，提出一種混合網(wǎng)絡(luò)的抗毀路由(Survival Target Hybrid Routing, STHR)，并且為了降低網(wǎng)絡(luò)負(fù)載和沖突，設(shè)計(jì)了STHR中抗毀增強(qiáng)節(jié)點(diǎn)的選取算法；文獻(xiàn)[19]首先通過基于時(shí)間表的集結(jié)—展開移動(dòng)模型(Aggregation and Spread Mobility Model, ASMM)集結(jié)展開戰(zhàn)場(chǎng)車隊(duì)的移動(dòng)模型，然后利用戰(zhàn)場(chǎng)車輛行動(dòng)計(jì)劃時(shí)間表預(yù)測(cè)節(jié)點(diǎn)之間的相遇機(jī)會(huì)，提出一種符合戰(zhàn)場(chǎng)車隊(duì)移動(dòng)模式和業(yè)務(wù)特點(diǎn)的基于時(shí)間表的DTN機(jī)會(huì)預(yù)測(cè)路由算法GenericSpray；文獻(xiàn)[20]結(jié)合戰(zhàn)場(chǎng)實(shí)際，為了提高專門用于戰(zhàn)場(chǎng)的DTN路由算法效率并滿足區(qū)分消息優(yōu)先級(jí)的需要，在部隊(duì)整體作戰(zhàn)性能和網(wǎng)絡(luò)通信質(zhì)量之間做出了合理權(quán)衡，提出基于多級(jí)隊(duì)列和改進(jìn)的橢圓區(qū)域轉(zhuǎn)發(fā)(Elliptical Zone Forwarding, EZF)路由算法。此外，文獻(xiàn)[21]提出一種基于網(wǎng)絡(luò)分簇和信息擺渡的無(wú)線自組應(yīng)急通信網(wǎng)服務(wù)增強(qiáng)方案，文獻(xiàn)[22]提出一種機(jī)械化步兵野戰(zhàn)環(huán)境中DTN的安全信道模型；文獻(xiàn)[23]提出一種戰(zhàn)場(chǎng)環(huán)境中考慮相遇頻率的概率路由機(jī)制；文獻(xiàn)[24]提出一種在戰(zhàn)場(chǎng)環(huán)境中使用DTN的信息交付方案；文獻(xiàn)[25]提出一種在DTN災(zāi)難環(huán)境下災(zāi)害消息的傳輸方式。

本文將VANET分簇的研究背景延伸到復(fù)雜戰(zhàn)場(chǎng)環(huán)境下。戰(zhàn)場(chǎng)環(huán)境下，作戰(zhàn)車輛間雖然可以通過衛(wèi)星和短波等超視距通信手段完成輔助通信，但由于衛(wèi)星通信存在以下缺點(diǎn)：1)傳輸時(shí)延大；2)回聲效應(yīng)明顯；3)存在通信盲區(qū)；4)存在日凌中斷、星蝕和雨衰現(xiàn)象。而短波通信則存在穩(wěn)定性較差、噪聲較大等不足?；诔杀敬鷥r(jià)，一般情況下只會(huì)選擇少數(shù)作戰(zhàn)車輛裝備衛(wèi)星或短波通信終端。因此在復(fù)雜戰(zhàn)場(chǎng)環(huán)境下，研究一種基于VANET通信終端的DTN分簇路由機(jī)制具有重要意義。

本文提出的分簇路由算法，首先通過VANET通信終端和運(yùn)動(dòng)信息完成了簇頭選舉及分簇過程；其次基于此分簇算法，提出了一種路由機(jī)制：根據(jù)跳數(shù)、轉(zhuǎn)發(fā)方式和地理位置信息實(shí)現(xiàn)簇內(nèi)路由；引入等待時(shí)間閾值、重發(fā)次數(shù)閾值和下游簇頭實(shí)現(xiàn)異簇路由；通過VANET通信終端實(shí)現(xiàn)與上級(jí)指揮所的通信。

1 分簇算法

假設(shè)將作戰(zhàn)車輛分成如圖1所示的簇模型，每個(gè)簇中有一個(gè)簇頭和若干個(gè)簇成員，存在4種不同類型的車輛：A：僅裝備VANET通信終端；B：加裝短波通信終端；C：加裝衛(wèi)星通信終端；D：裝備3種通信終端。

圖1 戰(zhàn)場(chǎng)車隊(duì)模型 Fig. 1 Model of battlefield fleet

假設(shè)每一個(gè)作戰(zhàn)車輛都裝備有VANET通信終端；小部分車輛可以通過加裝的短波或衛(wèi)星終端實(shí)現(xiàn)超視距通信；另有極小部分車輛同時(shí)裝備著上述三種通信終端。

1.1 簇頭的選舉算法

選舉簇頭的兩個(gè)要素為：1)簇的范圍；2)車輛的運(yùn)動(dòng)信息。

1)簇的范圍。如果簇成員過少，則分簇時(shí)簇?cái)?shù)量過多，導(dǎo)致簇頭過多，簇頭的緩存遠(yuǎn)遠(yuǎn)沒有達(dá)到飽和值；反之，如果簇成員過多，則簇頭過少，簇頭的緩存負(fù)擔(dān)過大，導(dǎo)致網(wǎng)絡(luò)擁塞。為了選擇一個(gè)合理的簇范圍，設(shè)置簇成員與簇頭間的最大跳數(shù)為κ=2(簡(jiǎn)單多跳路由)，最大簇成員數(shù)Nmax=10[20]。簇范圍的量化標(biāo)準(zhǔn)用We表示。

2)車輛的運(yùn)動(dòng)信息。為了避免頻繁發(fā)生簇結(jié)構(gòu)變化導(dǎo)致簇維護(hù)開銷的增加，根據(jù)局部性原理，為了保證未來(lái)時(shí)段簇頭與簇成員仍處在通信范圍，本時(shí)刻應(yīng)盡量選取與大部分車輛運(yùn)動(dòng)方向相近的車作為簇頭，運(yùn)動(dòng)方向的量化標(biāo)準(zhǔn)用Wl表示；同理，應(yīng)盡量選取速率較小的車作為簇頭，速率的量化標(biāo)準(zhǔn)用Wv表示。用Wi表示每輛車被選舉為簇頭的可能性大小，如式(1)所示：

Wi=a×We+b×Wl+c×Wv=

(1)

(2)

其中：Ni為車輛i在κ跳內(nèi)的鄰居車輛數(shù)，Vi為車輛i的車速，Vj為車輛i在κ跳內(nèi)的鄰居車輛j的車速，Vmax為車輛速率的最大值，Φi為車輛i在κ跳內(nèi)的鄰居車輛的集合，其中a,b,c為選舉簇頭的三個(gè)要素的權(quán)值，且：

(3)

設(shè)置a=0.4，b=0.3，c=0.3，將在3.3節(jié)給出關(guān)于此參數(shù)取值的實(shí)驗(yàn)分析。

選舉簇頭首先要確保簇頭的傳輸帶寬以及可靠性。文獻(xiàn)[26]已說(shuō)明衛(wèi)星通信在傳輸帶寬及質(zhì)量方面均優(yōu)于短波通信；文獻(xiàn)[27]指出軍用通信衛(wèi)星已被譽(yù)為現(xiàn)代戰(zhàn)爭(zhēng)的生命線，戰(zhàn)場(chǎng)上70%以上的通信是靠軍用通信衛(wèi)星來(lái)完成。因此裝備不同類型通信終端的車輛被選舉為簇頭的優(yōu)先級(jí)順序Pi為：D類車>C類車>B類車>A類車，D類車優(yōu)先使用C類車的衛(wèi)星通信，如無(wú)法連接到衛(wèi)星通信，再使用短波通信。簇頭選舉時(shí)，作以下假設(shè)：1)每輛車都有能唯一識(shí)別其身份的全網(wǎng)ID；2)每輛車通過北斗定位導(dǎo)航設(shè)備獲得其運(yùn)動(dòng)方向；3)每輛車通過車載速率傳感器獲得其速率。

設(shè)置探測(cè)簇頭信號(hào)DetHead，如果在2 min(因北斗定位信息1 min獲取一次)內(nèi)收不到簇頭回復(fù)，說(shuō)明簇頭已被摧毀或失效，則重新選舉簇頭。

1.2 分簇算法和維護(hù)

1.2.1 分簇算法

分簇算法的具體步驟如下：

1)每輛車都收集κ跳以內(nèi)鄰居車輛信息。每輛車周期性廣播hello(info,hnum)消息并轉(zhuǎn)發(fā)κ跳以內(nèi)其他車輛的hello消息。info為本車基本信息，包括全網(wǎng)ID號(hào)、優(yōu)先級(jí)Pi、地理位置信息pos、速度信息Vi；hnum為跳數(shù)，其初始值為0。當(dāng)收到其他車輛的hello消息時(shí)，首先判斷hnum的大小，如hnum<κ，則將hnum加1后轉(zhuǎn)發(fā)給其他車輛；反之無(wú)任何操作。

2)確定簇頭。若:

Pi>Pj; ?j∈Φi

(4)

(5)

如滿足式(4)，即：選舉裝備最高優(yōu)先級(jí)的通信終端類型的車輛作為簇頭；如滿足式(5)，即：當(dāng)Pi相同時(shí)，選舉Wi值高的作為簇頭。

3)廣播簇頭消息。簇頭需向全網(wǎng)廣播簇頭消息head(CluID,head_info,routing,hnum)，其中：CluID為簇標(biāo)號(hào)，head_info為簇頭信息，routing為轉(zhuǎn)發(fā)路徑車輛信息。

當(dāng)收到head消息時(shí)，首先將簇標(biāo)號(hào)、簇頭信息、轉(zhuǎn)發(fā)路徑車輛信息保存下來(lái)，如hnum<κ，則將info加入到routing中，將hnum加1后轉(zhuǎn)發(fā)給其他車輛；反之無(wú)任何操作。

當(dāng)收到同一CluID的不同head消息時(shí)，選舉最小hnum值的消息加以保存；當(dāng)收到不同CluID的head消息時(shí)，分析簇頭信息head_info，按照高優(yōu)先級(jí)Pi、小hunum值、速度方向最接近的先后順序保留消息。

4)車輛向簇頭發(fā)送入簇申請(qǐng)消息apply(CluID,info,routing,hnum)。當(dāng)收到其他車輛的apply消息時(shí)，如hnum<κ，則將info加入到routing中，將hnum加1后轉(zhuǎn)發(fā)給簇頭；反之無(wú)任何操作。

5)簇頭回發(fā)接收或拒絕信號(hào)。當(dāng)簇頭收到某車輛的apply消息時(shí)，如果本簇成員的數(shù)量小于Nmax，則將info和hnum信息存儲(chǔ)到簇成員信息表中，同時(shí)回發(fā)接收信號(hào)ACK；否則回發(fā)REJT信號(hào)表示拒絕此車輛加入到本簇中。

6)如車輛收到簇頭的ACK信號(hào)，則表明此車輛已成功入簇，廣播已成功入簇消息join(CluID,info,routing,head_num,hnum)，不再參與分簇過程，其中，head_num為此車輛距簇頭的跳數(shù)。

遞歸1)至6)，直到所有的車輛成為簇頭或簇成員為止，完成分簇。

1.2.2 簇的維護(hù)

VANET完成分簇后，因車輛無(wú)規(guī)則運(yùn)動(dòng)導(dǎo)致簇動(dòng)態(tài)更新，因此，簇結(jié)構(gòu)的不斷維護(hù)就十分必要。維護(hù)過程隨著掃描周期τ的到來(lái)而開始檢查鄰居車輛列表和鄰居簇列表狀態(tài)，直至VANET消亡或車輛退出VANET。對(duì)如下三種情況進(jìn)行簇維護(hù)：

1)簇成員車輛離開原簇加入新簇→在該簇成員的簇頭中修改簇成員列表；

2)兩個(gè)簇頭由于距離相近導(dǎo)致簇頭融合，引發(fā)簇頭競(jìng)爭(zhēng)→按1.2.1節(jié)分簇算法重新選舉新簇頭，競(jìng)爭(zhēng)失敗的簇頭成為新簇頭下屬的簇成員，并發(fā)送簇頭消亡消息通知其原下屬的簇成員重新更新簇頭；

3)簇頭突發(fā)故障而失效→簇成員按1.2.1節(jié)分簇算法重新選舉簇頭。

2 路由機(jī)制

本文提出的基于VANET通信終端和運(yùn)動(dòng)信息的DTN分簇路由算法——CVCTM(Cluster based on VANET Communication Terminals and Motion information)，分為簇內(nèi)、異簇以及簇成員與上級(jí)指揮所3種通信方式。在最重要且距離最大(一般超出VANET的通信范圍)的與上級(jí)指揮所通信中，通過在鏈路中尋找可建鏈的B、C、D類車來(lái)實(shí)現(xiàn)；異簇路由中用VANET進(jìn)行路由尋找，如異簇間距離超出VANET通信范圍時(shí)，再通過B、C、D類車發(fā)起跨地區(qū)的路由尋找；由于簇內(nèi)通信距離相隔很近，簇內(nèi)路由僅用VANET進(jìn)行通信，避免占用B、C、D類車信道資源。

在異簇和與上級(jí)指揮所通信時(shí)，B、C、D類車的優(yōu)先級(jí)順序與選舉簇頭時(shí)的Pi相同。

2.1 簇內(nèi)路由

當(dāng)同簇成員之間通信時(shí)，源車輛首先向簇頭發(fā)送申請(qǐng)，簇頭根據(jù)接收到的申請(qǐng)消息，確定簇成員中的目的車輛，然后根據(jù)車輛基本信息info中的地理位置信息pos為源車輛和目的車輛之間選擇最佳路由。

簇頭根據(jù)車輛的鏈路帶寬為源車輛選舉下一跳，鏈路帶寬越大的說(shuō)明處理數(shù)據(jù)能力強(qiáng)，信道鏈路質(zhì)量越高，鏈路發(fā)生消息擁塞的可能性越小，因此優(yōu)先選擇鏈路帶寬大的節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。根據(jù)此標(biāo)準(zhǔn)得出候選路由。如候選路由有多個(gè)，則根據(jù)式(6)、(7)、(8)依次選舉直至得到最佳路由為止。

hopr1

(6)

(7)

如滿足式(6)，即：直接選擇跳數(shù)最少的路徑；如滿足式(7)，即：當(dāng)最少跳數(shù)相同時(shí)，選擇無(wú)需經(jīng)過簇頭轉(zhuǎn)發(fā)的路徑，減輕簇頭的負(fù)擔(dān)。如圖2所示，假設(shè)A2為源車輛，A5為目的車輛，A2到A5的兩條路徑：A2→A3→A4→A5、A2→B1→A6→A5(其中A2→B1→A3→A4→A5因跳數(shù)多而不考慮)，兩者的跳數(shù)是一樣的，選擇無(wú)需簇頭轉(zhuǎn)發(fā)的前者作為最佳路徑進(jìn)行通信。

圖2 簇內(nèi)路由 Fig. 2 Intra-cluster routing

確定簇內(nèi)路由的方式后，如果出現(xiàn)選舉出的路由仍為多個(gè)時(shí)(跳數(shù)一樣且是否經(jīng)簇頭轉(zhuǎn)發(fā)情況一樣)，需研究中繼節(jié)點(diǎn)的選舉標(biāo)準(zhǔn)，根據(jù)地理位置信息，簇頭為某車輛A(xi,yi)選擇下一跳車輛B(xj,yj)的標(biāo)準(zhǔn)為：

(8)

(9)

(10)

其中：(xi,yi)為車輛i的坐標(biāo)位置，(xj,yj)為車輛j的坐標(biāo)位置，(xd,yd)為目的車輛的坐標(biāo)位置，(xk,yk)為滿足式(8)的任意車輛的坐標(biāo)位置，L為車輛間的通信距離。

2.2 異簇路由

當(dāng)簇頭在本簇查找不到目標(biāo)車輛時(shí)，此時(shí)本簇頭向鄰居簇頭發(fā)送路由申請(qǐng)(Routing ASK, RASK)并等待回應(yīng)。設(shè)置兩個(gè)閾值：1)等待時(shí)間閾值twait，若等待時(shí)間超出了twait，則重新發(fā)送RASK；2)重發(fā)次數(shù)閾值lretr，若重新發(fā)送RASK的次數(shù)超過了lretr，則結(jié)束路由尋址過程。源簇頭的工作流程如圖3所示。

圖3 異簇路由的源簇頭工作流程 Fig. 3 Working process of inter-cluster source cluster head

定義1 下游簇頭。指比源簇頭在距離上更靠近目的車輛的鄰居簇頭。只有下游簇頭在接收到源簇頭RASK請(qǐng)求消息后才會(huì)進(jìn)行路由尋址，否則刪除此請(qǐng)求報(bào)文，結(jié)束運(yùn)行。鄰居簇頭工作流程的具體步驟如圖4所示。

圖4 異簇路由的鄰居簇頭工作流程 Fig. 4 Working process of inter-cluster neighbor cluster head

鄰居簇頭在收到RASK后首先判斷自己是不是下游簇頭，若不是則拋棄該請(qǐng)求，否則處理流程如下：

1)首先檢查是否曾經(jīng)收到過此請(qǐng)求，若收到則拋棄該請(qǐng)求。

2)如目的車輛不在本簇，則轉(zhuǎn)4)。

3)向目的車輛轉(zhuǎn)發(fā)路由申請(qǐng)并等待目的車輛的路由響應(yīng)(Routing ANSwer, RANS)，轉(zhuǎn)5)。

4)將自己的info信息添加到RASK消息中，并將新更新的RASK消息繼續(xù)向自己的下游簇頭轉(zhuǎn)發(fā)并等待響應(yīng)。

5)若超過等待時(shí)間閾值twait仍未收到路由響應(yīng)則將重發(fā)次數(shù)加1，否則轉(zhuǎn)7)。

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

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

以上僅考慮VANET中的異簇路由。如果上述路由請(qǐng)求失敗，很可能是由于源車輛和目的車輛間的距離已經(jīng)超出VANET通信范圍。此時(shí)源車輛通過VANET通信范圍(500 m)內(nèi)的D、C、B類車發(fā)起500 m以外的路由尋找。如仍無(wú)法收到路由響應(yīng)，則反饋路由尋址失敗消息(Routing addressing FAIlure, RFAI)給源車輛。

最佳路由即為跳數(shù)hnum最少的路由。

2.3 簇成員與上級(jí)指揮所通信

上級(jí)指揮所一般遠(yuǎn)離戰(zhàn)場(chǎng)中心，超出了VANET的通信范圍，上級(jí)指揮所配備了最為齊全的各種通信方式終端。簇中的源車輛如需與上級(jí)指揮所通信，分如下兩種情況討論：

1)源車輛為D、C、B類車。源車輛直接與上級(jí)指揮所進(jìn)行通信；

2)源車輛為A類車。源簇頭收到源車輛發(fā)起的與上級(jí)指揮所通信請(qǐng)求后的處理步驟為：

①源簇頭如已收到過該請(qǐng)求，則直接刪除該請(qǐng)求報(bào)文，結(jié)束處理；否則轉(zhuǎn)②。

②簇頭為A類車(根據(jù)1.2.1節(jié)的簇頭選舉公式，簇成員也必為A類車)；否則轉(zhuǎn)⑧。

③向鄰居簇頭發(fā)起路由請(qǐng)求并等待響應(yīng)。

④如等待時(shí)間超過twait仍無(wú)響應(yīng)，則重新發(fā)送RASK，并將重發(fā)次數(shù)加1；否則轉(zhuǎn)⑥。

⑤若重新發(fā)送RASK的次數(shù)超過了lretr，則結(jié)束路由請(qǐng)求。

⑥選擇與源簇頭距離最近的路由響應(yīng)。

⑦如路由響應(yīng)的鄰居簇頭為A類車，則重復(fù)③；否則轉(zhuǎn)⑧。

⑧簇頭如為D、C類車，則向源車輛發(fā)送路由響應(yīng)，源車輛通過簇頭與上級(jí)指揮所通信；否則轉(zhuǎn)⑨。

⑨檢查本簇成員中是否有空閑可用的D、C類車，如有，則通過簇頭向源車輛發(fā)送路由響應(yīng)，源車輛通過該簇成員車輛與上級(jí)指揮所通信；否則轉(zhuǎn)⑩。

⑩簇頭為B類車，則向源車輛發(fā)送路由響應(yīng)，源車輛通過簇頭與上級(jí)指揮所通信。

3 仿真分析

3.1 實(shí)驗(yàn)設(shè)置

本文運(yùn)用ONE仿真工具對(duì)實(shí)驗(yàn)場(chǎng)景進(jìn)行模擬仿真。場(chǎng)景中設(shè)置2類節(jié)點(diǎn)。第1類節(jié)點(diǎn)為車輛節(jié)點(diǎn)，為了符合戰(zhàn)場(chǎng)車輛的無(wú)規(guī)則運(yùn)動(dòng)性，設(shè)置移動(dòng)模型為Random Waypoint：節(jié)點(diǎn)以恒定速度運(yùn)動(dòng)到隨機(jī)產(chǎn)生的目的位置后停留一段隨機(jī)時(shí)間，然后以隨機(jī)生成的速度恒速向下一個(gè)隨機(jī)產(chǎn)生的目的節(jié)點(diǎn)繼續(xù)移動(dòng)，以此往復(fù)；1種固定節(jié)點(diǎn)為上級(jí)指揮所。

CVCTM的仿真場(chǎng)景參數(shù)如表1所示。假定作戰(zhàn)時(shí)車輛節(jié)點(diǎn)較為分散，20到200輛車隨機(jī)分布在5 000 m×5 000 m的場(chǎng)地中，以不超過100 km/h的速度移動(dòng)(由于在參考文獻(xiàn)[2]的仿真實(shí)驗(yàn)中的節(jié)點(diǎn)數(shù)變化為30～150，采樣個(gè)數(shù)為5，為了更好地與CBRP進(jìn)行實(shí)驗(yàn)對(duì)比，且在此基礎(chǔ)上增加采樣個(gè)數(shù)增加仿真結(jié)果說(shuō)服力，為此在本實(shí)驗(yàn)中將節(jié)點(diǎn)數(shù)進(jìn)行了擴(kuò)展，從30～150調(diào)整到20～200)。各車輛節(jié)點(diǎn)間在通信范圍內(nèi)可相互通信，每臺(tái)車每隔15 s隨機(jī)向其他車輛發(fā)送消息，以實(shí)時(shí)溝通戰(zhàn)場(chǎng)態(tài)勢(shì)。對(duì)CVCTM算法與CBRP算法進(jìn)行性能比較。

表1 仿真場(chǎng)景參數(shù)Tab. 1 Simulation scenario parameters

本文中的仿真評(píng)估指標(biāo)如下：

1)簇結(jié)構(gòu)重組次數(shù)。評(píng)價(jià)簇結(jié)構(gòu)穩(wěn)定程度的指標(biāo)。重組次數(shù)越大，簇結(jié)構(gòu)越不穩(wěn)定。

2)消息投遞率。目的車輛接收的消息數(shù)據(jù)包個(gè)數(shù)/源車輛發(fā)送的數(shù)據(jù)包個(gè)數(shù)。

3)歸一化網(wǎng)絡(luò)開銷。每發(fā)送1個(gè)數(shù)據(jù)分組到目的節(jié)點(diǎn)所需發(fā)送的路由分組的數(shù)量。

3.2 實(shí)驗(yàn)結(jié)果分析

如圖5所示為網(wǎng)絡(luò)中車輛節(jié)點(diǎn)總數(shù)為100時(shí)簇結(jié)構(gòu)重組次數(shù)隨時(shí)間變化關(guān)系。由圖可見，CBRP和動(dòng)態(tài)源路由協(xié)議(Dynamic Source Routing, DSR)的簇結(jié)構(gòu)穩(wěn)定性較差，其主要原因是：CBRP僅僅通過選舉最小的全網(wǎng)ID作為簇頭。當(dāng)車輛以較高速度運(yùn)動(dòng)時(shí)，簇結(jié)構(gòu)的變化頻率也會(huì)加快。而DSR源節(jié)點(diǎn)路由中每個(gè)消息數(shù)據(jù)包首部都要存儲(chǔ)包括源節(jié)點(diǎn)和所有中繼節(jié)點(diǎn)的全部路由信息以達(dá)到同時(shí)返回到達(dá)目的節(jié)點(diǎn)的多條路由，車輛節(jié)點(diǎn)的無(wú)規(guī)則運(yùn)動(dòng)必然會(huì)導(dǎo)致DSR中消息的存儲(chǔ)信息發(fā)生大幅度改變，導(dǎo)致簇結(jié)構(gòu)穩(wěn)定性較差。而無(wú)線自組網(wǎng)按需平面距離向量路由協(xié)議(Ad Hoc On-demand Distance Vector routing, AODV)中源節(jié)點(diǎn)和中繼節(jié)點(diǎn)都僅存儲(chǔ)消息的下一跳信息，因此簇結(jié)構(gòu)穩(wěn)定性好于DSR。

圖5 簇結(jié)構(gòu)重組次數(shù)隨時(shí)間變化關(guān)系 Fig. 5 Recombination times of cluster structure changed with time

作戰(zhàn)車輛由于不規(guī)則運(yùn)動(dòng)將導(dǎo)致簇頭和簇的不斷更新，針對(duì)這種情況，CVCTM增加了對(duì)車輛運(yùn)動(dòng)信息、鄰居車輛信息和簇大小的考慮，減少了簇結(jié)構(gòu)重組的可能，提高了網(wǎng)絡(luò)的穩(wěn)定性。

如圖6所示為消息投遞率隨車輛數(shù)的變化關(guān)系?？梢杂^察出隨著車輛數(shù)的增加，CVCTM的消息投遞率始終都在87.5%之上，車輛數(shù)的增加對(duì)其影響甚微的原因在于此算法的高效率和簇結(jié)構(gòu)的高穩(wěn)定性，當(dāng)車輛間無(wú)法通過VANET終端進(jìn)行通信時(shí)，可以借助于衛(wèi)星通信終端和短波通信終端獲得聯(lián)系，因此CVCTM算法極大地避免了消息的丟失，所以即便是在車輛數(shù)為20的稀疏網(wǎng)絡(luò)中，CVCTM的消息投遞率仍比CBRP和DSR多出約10%。CBRP和DSR的消息投遞率小于CVCTM和AODV的原因與圖4的分析相同。AODV的消息投遞率小于CVCTM的原因?yàn)椋篈ODV的節(jié)點(diǎn)都需要通過路由表存儲(chǔ)路由以完成到目的節(jié)點(diǎn)的路由發(fā)現(xiàn)過程，除此之外還存在內(nèi)置的路由維護(hù)(Routing Maintenance, RM)屬性，當(dāng)出現(xiàn)路由故障時(shí)，AODV中的路由機(jī)制需要為每個(gè)請(qǐng)求搜索一條新路由。而相比CBRP和DSR，AODV使用RM節(jié)省了路由重新發(fā)現(xiàn)的泛洪流量，提高了消息投遞率。

在曲線剛開始時(shí)消息投遞率都普遍較低的原因?yàn)橛捎诜抡娉绦虺跏蓟瘯r(shí)具有隨機(jī)性，導(dǎo)致車輛趨于不規(guī)則運(yùn)動(dòng)，進(jìn)而導(dǎo)致在車輛數(shù)較少時(shí)，車輛的分布不太均勻，某些車輛之間超出通信范圍，因此消息丟失率較高。在車輛數(shù)目較多的情況下，四種協(xié)議的消息投遞率都出現(xiàn)下降，其主要原因是車輛數(shù)目增多，導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變得越來(lái)越復(fù)雜，路由尋址的跳數(shù)也越來(lái)越大，網(wǎng)絡(luò)擁塞越來(lái)越嚴(yán)重，導(dǎo)致消息丟失率越來(lái)越高。

圖6 消息投遞率隨車輛數(shù)變化關(guān)系 Fig. 6 Message delivery ratio changed with the number of vehicles

如圖7所示為網(wǎng)絡(luò)開銷隨車輛數(shù)的變化關(guān)系。觀察出四種協(xié)議的網(wǎng)絡(luò)開銷都隨車輛數(shù)的增加而增加，其主要原因是：車輛數(shù)的增加，導(dǎo)致路由跳數(shù)的增加，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變得更加復(fù)雜，導(dǎo)致車輛的消息緩存隊(duì)列發(fā)生擁塞甚至“溢出”，待轉(zhuǎn)發(fā)消息得不到及時(shí)傳送，使得網(wǎng)絡(luò)中成功發(fā)送的消息數(shù)據(jù)包個(gè)數(shù)減少，因此增大了網(wǎng)絡(luò)開銷。當(dāng)車輛數(shù)為20～30時(shí)，CVCTM的網(wǎng)絡(luò)開銷最大，主要是因?yàn)镃VCTM路由尋址過程的初始化非常復(fù)雜。AODV的問題是，當(dāng)源序列存在時(shí)間過長(zhǎng)且中間節(jié)點(diǎn)有較多的、而不是最新的目標(biāo)序列數(shù)時(shí)，中間節(jié)點(diǎn)的增加會(huì)導(dǎo)致不一致的路由，因此其網(wǎng)絡(luò)開銷比CVCTM大。當(dāng)車輛數(shù)超過30時(shí)，CBRP和DSR的網(wǎng)絡(luò)開銷一直高于CVCTM，其原因?yàn)椋篊BRP和DSR在路由尋址時(shí)采用“洪泛”機(jī)制，而CVCTM在異簇路由尋址時(shí)只考慮下游簇頭。

3.3 相關(guān)參數(shù)討論

如圖8所示，為了得到a，b，c的最佳取值，得到簇結(jié)構(gòu)重組次數(shù)與權(quán)值Wi、We、Wl和Wv的變化關(guān)系?？捎^察出Wl和Wv對(duì)簇結(jié)構(gòu)重組次數(shù)的影響大致相同，所以設(shè)置b=c，為了得到a與b、c間的權(quán)值差關(guān)系，用式(9)進(jìn)行采樣(圖5～7中樣本個(gè)數(shù)為12)計(jì)算：

(11)

ai表示W(wǎng)e的樣本，bi表示W(wǎng)l的樣本。式(9)的計(jì)算結(jié)果為0.1，即a=b+0.1，又a+b+c=1且b=c，所以a=0.4，b=0.3，c=0.3。

圖7 網(wǎng)絡(luò)開銷隨車輛數(shù)變化關(guān)系 Fig. 7 Overhead changed with the number of vehicles

圖8 簇結(jié)構(gòu)重組次數(shù)與不同權(quán)值的關(guān)系 Fig. 8 Recombination times of cluster structure changed with different weights

4 結(jié)語(yǔ)

本文的主要工作：

1)通過分析VANET中車輛裝備的通信終端的優(yōu)缺點(diǎn)，確定了裝備不同類型通信終端的車輛被選舉為簇頭的優(yōu)先級(jí)順序；

2)綜合簇的范圍、車輛運(yùn)動(dòng)方向和車輛運(yùn)動(dòng)速率，確定了每輛車被選舉為簇頭的可能性大小；

3)綜合1)～2)，得出分簇算法和簇維護(hù)策略；

4)分簇后，確定了路由機(jī)制。

下一步主要研究工作：

針對(duì)CVCTM算法中簇頭要同時(shí)擔(dān)負(fù)簇內(nèi)、簇間及與上級(jí)指揮所通信，簇頭的緩存空間可能發(fā)生擁塞的問題，提出基于簇頭緩存空間的排隊(duì)機(jī)制和丟棄策略，從而更好地實(shí)現(xiàn)網(wǎng)絡(luò)資源調(diào)度。

參考文獻(xiàn)(References)

[1] 趙娜，袁家斌，徐晗.智能交通系統(tǒng)綜述[J]. 計(jì)算機(jī)科學(xué)，2014，41(11)：7-11.(ZHAO N, YUAN J B, XU H. Survey on intelligent transportation system [J]. Computer Science, 2014，41(11)：7-11.)

[2] LAHDE S, DOERING M, P?TTNER W-B, et al. A practical analysis of communication characteristics for mobile and distributed pollution measurements on the road [J]. Wireless Communications and Mobile Computing, 2007, 7(10): 1209-1218.

[3] 倪梁方，陳建建.基于NS2的CBRP協(xié)議構(gòu)建與仿真研究[J].安徽工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版)，2014，31(3)：309-313.(NI L F, CHEN J J. Research on construction and simulation of NS2-based CBRP protocol for Ad Hoc networks [J]. Journal of Anhui University of Technology (Natural Science), 2014，31(3)：309-313.)

[4] 任建軍，邵蘇杰，郭少勇，等.一種雙層結(jié)構(gòu)的分簇算法在VANET中的應(yīng)用[J]. 北京郵電大學(xué)學(xué)報(bào)，2016，39(B06)：23-26.(REN J J, SHAO S J, GUO S Y, et al. A clustering algorithm with two-tier structure applied in VANET network [J]. Journal of Beijing University of Posts and Telecommunications, 2016，39(B06): 23-26.)

[5] 楊瓊，邢松，夏瑋瑋，等. 一種基于MAC層時(shí)延上限的VANET自適應(yīng)分簇算法[J]. 東南大學(xué)學(xué)報(bào)(自然科學(xué)版)，2016，46(1)：1-6.(YANG Q, XING S, XIA W W, et al. MAC upper band delay based adaptive clustering algorithm for VANET [J]. Journal of Southeast University (Natural Science Edition), 2016，46(1)：1-6.)

[6] 何鵬，閻保平，李志，等. CM-MAC：一種基于分簇的多信道車載網(wǎng)MAC協(xié)議[J]. 計(jì)算機(jī)研究與發(fā)展，2014，51(3)：502-510.(HE P, YAN B P, LI Z, et al. CM-MAC: a cluster-based multi-channel MAC protocol for VANET [J]. Journal of Computer Research and Development, 2014，51(3)：502-510.)

[7] 陳振，韓江洪，劉征宇. 基于VANET分簇的車輛碰撞警告信息傳輸[J]. 電子測(cè)量與儀器學(xué)報(bào)，2013，27(5): 396-402. (CHEN Z, HAN J H, LIU Z Y. Collision-warning-messages transmission based on VANET clustering [J]. Journal of Electronic Measurement and Instrument, 2013，27(5)：396-402.)

[8] 鄭鑫，徐慧娟. VANET中基于分布式的分簇的路由機(jī)制[J]. 現(xiàn)代電子技術(shù)，2016，39(4)：16-20. (ZHENG X, XU H J. A distributed clustering based routing mechanism in VANET[J]. Modern Electronics Technique, 2016，39(4)：16-20.)

[9] 帥建平.VANET中基于灰色系統(tǒng)理論的分簇算法[J]. 激光雜志，2015，36(8)：124-130.(SHUAI J P. Clustering algorithm based on gray system theory in vehicular Ad Hoc network [J]. Laser Journal, 2015，36(8)：124-130.)

[10] 默罕默德·默森，許凱凱，夏瑋瑋，等.荒漠場(chǎng)景應(yīng)用的車聯(lián)網(wǎng)及其分簇路由算法[J].通信學(xué)報(bào)，2012，33(10)：166-174. (MOHAMED M, XU K K, XIA W W, et al. Vehicular Ad Hoc networks and clustering routing algorithm applied in wilderness scenarios[J]. Journal on Communications, 2012，33(10)：166-174.)

[11] 吳振華，胡鵬.VANET中路由協(xié)議分析[J].通信學(xué)報(bào)，2015，36(Z1)：75-84.(WU Z H, HU P. Analysis on VANET routing protocols[J]. Journal on Communications, 2015，36(Z1)：75-84.)

[12] OHTA Y, OHTA T, KAKUDA Y. A data transfer scheme based on autonomous clustering with positions and moving direction of vehicles for VANETs [J]. IEICE Transactions on Communications, 2012, E95-B(9): 2728-2739.

[13] CHEN Y Z, FANG M Y, SHI S, et al. Distributed multi-hop clustering algorithm for VANETs based on neighborhood follow [J]. EURASIP Journal on Wireless Communications and Networking, 2015, 2015(1): 1-12.

[14] GORRIERI A, MARTALO M, BUSANELLI S, et al. Clustering and sensing with decentralized detection in vehicular Ad Hoc networks [J]. Ad Hoc Networks, 2016, 36(2): 450-464.

[15] RAMAKRISHNAN B, SELVI M, NISHANTH R B, et al. An emergency message broadcasting technique using transmission power based clustering algorithm for vehicular Ad Hoc network [J]. Wireless Personal Communications, 2017, 94(4): 3197-3216.

[16] ARKIAN H R, ATANI R E, DIYANAT A, et al. A cluster-based vehicular cloud architecture with learning-based resource management [J]. The Journal of Supercomputing, 2015, 71(4): 1401-1426.

[17] HASSANABADI B, SHEA C, ZHANG L, et al. Clustering in vehicular Ad Hoc networks using affinity propagation [J]. Ad Hoc Networks, 2014, 13(B): 535-548.

[18] 馬馳，孟錦，張宏. 抗毀的混合移動(dòng)自組織網(wǎng)路由策略[J]. 計(jì)算機(jī)應(yīng)用，2011，31(11)：2883-2886. (MA C, MENG J, ZHANG H. Integrated routing strategy with high survivability for mobile Ad Hoc network [J]. Journal of Computer Applications, 2011，31(11)：2883-2886.)

[19] 王海濤，宋麗華，張國(guó)敏，等. 戰(zhàn)場(chǎng)環(huán)境下基于時(shí)間表的DTN機(jī)會(huì)預(yù)測(cè)路由算法[EB/OL]. [2017- 05- 06]. http://kns.cnki.net/kcms/detail/32.1430.N.20170414.1754.006.html.(WANG H T, SONG L H, ZHANG G M, et al. DTN opportunistic routing algorithm based on timetable in battle environments [EB/OL]. [2017- 05- 06]. http://kns.cnki.net/kcms/detail/32.1430.N.20170414.1754.006.html.)

[20] 謝凌杰，韓學(xué)東. 戰(zhàn)場(chǎng)環(huán)境下的DTN路由算法研究 [J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2014，35(2)：376-380.(XIE L J, HAN X D. DTN routing protocol research in battle environments [J]. Computer Engineering and Design, 2014，35(2)：376-380.)

[21] 王海濤，宋麗華，李建州，等. 基于網(wǎng)絡(luò)分簇和信息擺渡的無(wú)線自組應(yīng)急通信網(wǎng)服務(wù)增強(qiáng)方案[J]. 電信科學(xué)，2012，28(4)：38-43. (WANG H T, SONG L H, LI J Z, et al. Service enhancement schemes of wireless self-organizing emergency communication network based on network clustering and information ferry [J]. Telecommunications Science, 2012，28(4)：38-43.)

[22] 戚湧，李千目，倪辰辰，等. 機(jī)械化步兵野戰(zhàn)環(huán)境中容忍時(shí)延網(wǎng)絡(luò)的安全信道模型[J]. 兵工學(xué)報(bào)，2014，35(1)：122-128. (QI Y, LI Q M, NI C C, et al. Safe delay-tolerant communications model of tactical battlefield [J]. Acta Armamentarii, 2014，35(1)：122-128.)

[23] LEE J， KANG K， CHO Y J. A probabilistic routing mechanism considering the encounter frequency in the battlefield environment [J]. Journal of the Korea Institute of Military Science and Technology，2013，16(3)：332-339.

[24] KIM Y A. Information delivery scheme by using DTN in battlefield environment [J]. The Journal of Korean Institute of Communications and Information Sciences，2011，36(3B)：260-267.

[25] SHIBATA Y, UCHIDA N. Delay tolerant network for disaster information transmission in challenged network environment [J]. IEICE Transactions on Communications, 2015,E100-B(1)：11-16.

[26] 陳永華，肖毅. 我國(guó)短波通信技術(shù)的發(fā)展及方向探究[J]. 電子技術(shù)與軟件工程，2015(7)：43. (CHEN Y H, XIAO Y. The development and direction of short-wave communication technology in China [J]. Electronic Technology & Software Engineering, 2015(7)：43.)

[27] 天兵. 美國(guó)軍用通信衛(wèi)星更新?lián)Q代 [EB/OL]. [2017- 04- 12]. http://www.360doc.com/content/15/0427/08/19670888_466274226.shtml.(TIAN B. U.S. military communications satellites are upgraded[EB/OL]. [2017- 04- 12]. http://www.360doc.com/content/15/0427/08/19670888_466274226.shtml.)

This work is partially supported by the National High Technology Research and Development Program (863 Program) of China (2012AA7010213).

HEHe, born in 1993, M. S. candidate. His research interests include routing algorithm for delay tolerant networks, congestion control.

LILinlin, born in 1974, Ph. D., associate professor. Her research interests include battlefield command network.

LUYunfei, born in 1992, M. S. candidate. His research interests include command information network.