基于遺傳特征的車載網(wǎng)絡(luò)分簇路由算法研究

路 婷，王 偉

(西安工程大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710048)

0 引 言

車載自組織網(wǎng)絡(luò)(vehicular ad hoc network，VANET)又稱車載網(wǎng)絡(luò)，是移動自組織網(wǎng)絡(luò)(mobile ad hoc network，MANET)在汽車行業(yè)的實(shí)際應(yīng)用，也是智能交通系統(tǒng)中尤為重要的組成部分。車載網(wǎng)絡(luò)以安裝有無線通信設(shè)備的高移動性車輛和路邊單元等作為網(wǎng)絡(luò)節(jié)點(diǎn)，構(gòu)建車輛與車輛(vehicle to vehicle，V2V)、車輛與網(wǎng)絡(luò)(vehicle to network，V2N)、車輛與基礎(chǔ)設(shè)施(vehicle to infrastructure，V2I)、車輛與行人(vehicle to pedestrian，V2P)等V2X網(wǎng)絡(luò)互聯(lián)，實(shí)現(xiàn)車載網(wǎng)絡(luò)信息共享。典型的車載網(wǎng)絡(luò)應(yīng)用包括娛樂服務(wù)和安全預(yù)警。娛樂服務(wù)類應(yīng)用主要包括音樂或視頻文件請求、語音交互等功能，具有一定的時延容忍特性；而安全性應(yīng)用是智能交通的重要應(yīng)用，是網(wǎng)絡(luò)性能要求較高的一類應(yīng)用，具體應(yīng)用場景包括車輛變道或變速預(yù)警、車輛碰撞預(yù)警等，要求保證信息實(shí)時、可靠、安全傳輸。

傳統(tǒng)的車載網(wǎng)絡(luò)路由算法主要分為基于拓?fù)涞穆酚伤惴╗1-2]和基于位置的路由算法[3-7]，但由于車載網(wǎng)絡(luò)拓?fù)洳粩嘧兓椅恢毛@取方式易受環(huán)境影響，所以這兩種方法都存在弊端。因此，有學(xué)者提出將群智算法引入車載路由算法的研究思路，從而對傳統(tǒng)算法進(jìn)行改進(jìn)，提高網(wǎng)絡(luò)鏈路穩(wěn)定性和數(shù)據(jù)轉(zhuǎn)發(fā)效率。但現(xiàn)有的路由算法大多缺乏對車輛節(jié)點(diǎn)密度、網(wǎng)絡(luò)無線鏈路變化及節(jié)點(diǎn)剩余能量等因素的考慮，在復(fù)雜環(huán)境下數(shù)據(jù)包轉(zhuǎn)發(fā)不具穩(wěn)健性，難以適用于車輛安全預(yù)警應(yīng)用。

因此，基于車載網(wǎng)絡(luò)安全預(yù)警應(yīng)用對于網(wǎng)絡(luò)無線鏈路穩(wěn)定性、網(wǎng)絡(luò)實(shí)時性和數(shù)據(jù)包高效轉(zhuǎn)發(fā)等需求，文中提出了一種自適應(yīng)的基于遺傳特征的分簇路由算法。

1 相關(guān)工作

常見的車載網(wǎng)絡(luò)路由算法主要包括傳統(tǒng)車載網(wǎng)絡(luò)路由算法和基于群智算法的車載網(wǎng)絡(luò)路由算法。

1.1 傳統(tǒng)車載網(wǎng)絡(luò)路由算法

傳統(tǒng)的車載路由算法是在移動自組織網(wǎng)絡(luò)路由算法的基礎(chǔ)上發(fā)展而來的。移動自組織網(wǎng)絡(luò)中，常用的經(jīng)典路由協(xié)議包括主動式路由協(xié)議[8]和反應(yīng)式路由協(xié)議[9-11]，但其路由開銷較大，無法適用于節(jié)點(diǎn)數(shù)量很大的車載網(wǎng)絡(luò)環(huán)境。基于此，很多學(xué)者提出適用于車載網(wǎng)絡(luò)的改進(jìn)算法。如表1所示，車載網(wǎng)絡(luò)路由算法可分為基于拓?fù)?topology based)的路由算法和基于位置(position based)的路由算法。

表1 傳統(tǒng)車載網(wǎng)絡(luò)路由算法對比

針對以上路由算法的缺陷，Soni. V等人[2]通過建立模糊規(guī)則庫減少網(wǎng)絡(luò)拓?fù)渥兓瘜β酚砂l(fā)現(xiàn)的影響，一定程度上增加了網(wǎng)絡(luò)鏈路的穩(wěn)定性，但規(guī)則庫數(shù)據(jù)存儲也將帶來更多的網(wǎng)絡(luò)帶寬消耗，增加了傳輸延遲。Luo等人[6]提出了一種基于位置和集群的CBR路由算法，將區(qū)域劃分為一系列邏輯網(wǎng)格，并在每個網(wǎng)格內(nèi)選擇簇標(biāo)頭，通過選擇最優(yōu)鄰居簇標(biāo)頭進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)直至到達(dá)目標(biāo)節(jié)點(diǎn)，無需路由發(fā)現(xiàn)和保存路由表，一定程度上減少了內(nèi)存開銷，提高了數(shù)據(jù)包投遞率，但提高了算法復(fù)雜度，增加了網(wǎng)絡(luò)時延，算法所使用的車載GPS設(shè)備數(shù)據(jù)易受周圍環(huán)境的影響，信號不穩(wěn)定、定位靜態(tài)漂移等現(xiàn)象導(dǎo)致GPS信息不準(zhǔn)確。

1.2 基于群智算法的車載網(wǎng)絡(luò)路由算法

此外，文獻(xiàn)[12-16]分別將蜂窩算法、狼群算法和社交屬性等群智算法引入傳統(tǒng)車載網(wǎng)絡(luò)路由算法，通過節(jié)點(diǎn)集優(yōu)化策略進(jìn)行自適應(yīng)全局隨機(jī)尋優(yōu)，一定程度上優(yōu)化了轉(zhuǎn)發(fā)節(jié)點(diǎn)，提高了網(wǎng)絡(luò)性能和轉(zhuǎn)發(fā)率。Tian等人[12]提出了基于生物啟發(fā)的車載網(wǎng)絡(luò)機(jī)會路由算法。該算法利用蜂窩吸引子選擇下一跳，并采用多屬性策略優(yōu)化候選節(jié)點(diǎn)，減少冗余。

Yu等人[13]提出了一種基于狼群算法的聚類路由算法。算法通過求解近似最優(yōu)解進(jìn)行節(jié)點(diǎn)整體規(guī)劃；引入邊緣度概念優(yōu)化異構(gòu)節(jié)點(diǎn)部署，有效提高了網(wǎng)絡(luò)穩(wěn)定性，延長了網(wǎng)絡(luò)壽命。

余玲飛[14]提出了一種基于社會貢獻(xiàn)的路由算法。該算法引入社會貢獻(xiàn)率的概念進(jìn)行下一跳節(jié)點(diǎn)的決策，采用激勵機(jī)制增強(qiáng)節(jié)點(diǎn)轉(zhuǎn)發(fā)意愿，提高了消息遞交率。

綜上所述，雖然基于群智算法的車載網(wǎng)絡(luò)路由算法得到了改進(jìn)，但其收斂時間較長，缺乏節(jié)點(diǎn)局部信息的有效利用，存在節(jié)點(diǎn)評價不全面、網(wǎng)絡(luò)開銷較大、數(shù)據(jù)傳輸缺乏穩(wěn)定性等缺陷，這也是車載網(wǎng)絡(luò)路由協(xié)議研究中一項(xiàng)具有挑戰(zhàn)性的工作?；诖?，文中利用遺傳算法自適應(yīng)、擇優(yōu)等特性，對分簇路由算法進(jìn)行優(yōu)化。

2 網(wǎng)絡(luò)模型

本節(jié)將對文中提出的路由算法網(wǎng)絡(luò)模型做出如下假設(shè)：(1)車載網(wǎng)絡(luò)物理層和MAC層的通信標(biāo)準(zhǔn)采用IEEE802.11p協(xié)議，支持無線多信道接入。上層采用IEEE 1609.4協(xié)議標(biāo)準(zhǔn)，以利于上層實(shí)體調(diào)用802.11p功能；(2)車載網(wǎng)絡(luò)環(huán)境下的車輛包括小轎車、貨車、公交車等，文中在此不作任何區(qū)分，默認(rèn)其轉(zhuǎn)發(fā)半徑、數(shù)據(jù)發(fā)送速率相同；(3)車載網(wǎng)絡(luò)場景下的車輛均安裝有GPS定位系統(tǒng)和城市電子地圖，通過車輛智能系統(tǒng)獲取車輛位置等重要車輛信息。類似的假設(shè)也出現(xiàn)在文獻(xiàn)[13]中。

假設(shè)車輛行駛環(huán)境為經(jīng)典的曼哈頓式街區(qū)，車輛節(jié)點(diǎn)具有高速移動性，其行駛方向沿著道路的延伸方向。因此，車載網(wǎng)絡(luò)下車輛節(jié)點(diǎn)的運(yùn)動具有一定的規(guī)律性，道路上車輛節(jié)點(diǎn)分布和車輛連通性也具有一定的可預(yù)測性。

3 基于遺傳特征的分簇路由算法

基于以上網(wǎng)絡(luò)模型假設(shè)，本節(jié)提出了一種基于遺傳特征的分簇路由(genetic-characteristics-based clustering routing，GCCR)算法。該算法框架如圖1所示。

圖1 GCCR算法框架

(1)下一跳路段的選擇。該過程主要解決交通路口面臨左轉(zhuǎn)、直行和右轉(zhuǎn)多個數(shù)據(jù)傳輸方向時，如何通過可量化指標(biāo)來評估各個路段，選擇合適的下一跳路段。因此，就涉及到下一跳路段的選擇問題。

(2)下一跳節(jié)點(diǎn)的選擇。該過程首先通過分簇算法對車輛節(jié)點(diǎn)進(jìn)行分簇并隨機(jī)選取簇頭節(jié)點(diǎn)；再利用遺傳算法對服務(wù)節(jié)點(diǎn)集進(jìn)行優(yōu)化，建立選定路段上的最優(yōu)前向轉(zhuǎn)發(fā)路徑。

3.1 下一跳路段的選擇

街道交通路口通常出現(xiàn)四個道路延伸方向，即車輛在交通路口將面臨左轉(zhuǎn)、直行和右轉(zhuǎn)三個行駛方向的選擇。因此，車輛在道路行駛過程中就涉及到了下一路段的選擇問題。下一跳路段選擇策略主要取決于以下四個參數(shù)：路段車輛分布密度、路段出口與目標(biāo)節(jié)點(diǎn)的歸一化距離、路段的無線連通率和路段無線連通穩(wěn)定性。假設(shè)選定范圍內(nèi)車輛節(jié)點(diǎn)集合表示為{X1,X2,…,Xi,…,XM}(1

(1)路段車輛分布密度。

路段車輛分布密度與網(wǎng)絡(luò)傳輸效率有關(guān)。假設(shè)該路段Oi的長度為LOi，包含的車輛節(jié)點(diǎn)數(shù)為SXi，利用路邊基礎(chǔ)設(shè)施采集車輛節(jié)點(diǎn)數(shù)量數(shù)據(jù)并以fXi的頻率定時更新，則路段Oi車輛分布密度ρi可表示為：

(1)

為避免路段車輛密度太小導(dǎo)致車距大于網(wǎng)絡(luò)傳輸半徑，從而影響數(shù)據(jù)轉(zhuǎn)發(fā)效率；或者車輛密度太大造成網(wǎng)絡(luò)時延，車輛分布密度應(yīng)保持在一個穩(wěn)定區(qū)間ρOi。

(2)

(2)路段出口與目標(biāo)節(jié)點(diǎn)的歸一化距離。

數(shù)據(jù)包總是向更靠近目標(biāo)節(jié)點(diǎn)的方向進(jìn)行傳遞，路段出口與目標(biāo)節(jié)點(diǎn)的歸一化距離越近，表示數(shù)據(jù)包越靠近目標(biāo)節(jié)點(diǎn)。假設(shè)源節(jié)點(diǎn)Xi坐標(biāo)為(x1,y1)，目標(biāo)節(jié)點(diǎn)XM坐標(biāo)為(x2,y2)，該路段出口點(diǎn)XOi坐標(biāo)為(xi,yi)，則路段出口與目標(biāo)節(jié)點(diǎn)的歸一化距離βOi可表示為：

(3)

(3)路段的無線連通率。

路段的無線連通率反映了該路段網(wǎng)絡(luò)通信質(zhì)量。連通率的高低一般取決于以下兩個因素：一是道路車輛分布密度ρOi；二是無線通信的傳輸半徑ξ。當(dāng)且僅當(dāng)每兩個相鄰車輛可實(shí)現(xiàn)無線鏈路連通，整個路段才可連通。雙車道無線連通分為兩種情況：一是單向車道上相鄰車輛之間的距離小于無線傳輸半徑；二是對向車道存在有效的車輛節(jié)點(diǎn)可進(jìn)行單向車道無線連通條件的補(bǔ)充，文中將其稱為鏈路修復(fù)現(xiàn)象。設(shè)LCi表示路段無線連通長度，ξ為無線傳輸半徑，則其無線連通概率POi可表示為：

(4)

假設(shè)Lk,k+1、Lk,i分別表示節(jié)點(diǎn)k到k+1和k到i的距離，ρk表示單向車道的車輛密度，Pk為單向車道中斷概率，PRi為雙向車道的無線鏈路修復(fù)概率，則：

Pk=P{Lk,k+1>ξ}=e-ρkξ

(5)

PRi=P(Lk,i<ξ)+P(Li,k+1<ξ)=1-e-2(ρOi-ρk)ξ

(6)

(4)路段無線連通穩(wěn)定性。

路段無線連通穩(wěn)定性是路段通信性能評估中非常重要的一項(xiàng)指標(biāo)，體現(xiàn)了無線鏈路穩(wěn)定傳輸情況。文中所提出的路段無線連通穩(wěn)定性SOi可表示為：

(7)

綜上，將路段車輛分布密度ρOi、路段出口與目標(biāo)節(jié)點(diǎn)的歸一化距離βOi、路段的無線連通率POi及路段無線連通穩(wěn)定性SOi這四個參數(shù)引入下一跳路段評估函數(shù)EOi中：

EOi=ω1ρOi+ω2(1-βOi)+ω3POi+ω4(1-SOi)

(8)

3.2 下一跳節(jié)點(diǎn)的選擇

下一跳節(jié)點(diǎn)選擇采用基于遺傳特征的分簇路由算法，包括以下兩個步驟：一是對路段所有車輛節(jié)點(diǎn)分簇，隨機(jī)選擇簇頭節(jié)點(diǎn)；二是建立適應(yīng)度函數(shù)，通過遺傳算法的選擇、交叉和變異操作，選擇一條高效的數(shù)據(jù)轉(zhuǎn)發(fā)路徑。

3.2.1 選擇簇頭節(jié)點(diǎn)

文中采用隨機(jī)選取簇頭的方法。首先，每個節(jié)點(diǎn)生成隨機(jī)數(shù)τ，滿足τ∈(0,1)。定義閾值T(i)，如式(9)所示，若τ

(9)

其中，R表示簇頭節(jié)點(diǎn)數(shù)與節(jié)點(diǎn)總數(shù)的比值，R=w/SXi；c表示簇頭選擇次數(shù)；G表示當(dāng)前還沒有被選為簇頭節(jié)點(diǎn)的集合，這一參數(shù)有助于簇頭節(jié)點(diǎn)的能量負(fù)載均衡。

考慮到簇的大小對數(shù)據(jù)轉(zhuǎn)發(fā)效率的影響，文中設(shè)定雙向路段一跳范圍內(nèi)的所有車輛為一簇，以此類推，將路段內(nèi)所有車輛劃分至不同的簇。假設(shè)該路段的車輛節(jié)點(diǎn)共劃分為w個簇，每一個簇Qi所對應(yīng)的簇頭節(jié)點(diǎn)分別為{X11,X21,…,Xi1,…,Xw1}(0

3.2.2 選擇最佳數(shù)據(jù)轉(zhuǎn)發(fā)路徑

基于遺傳特征優(yōu)化服務(wù)節(jié)點(diǎn)，選擇最佳數(shù)據(jù)轉(zhuǎn)發(fā)路徑。遺傳算法的主要優(yōu)點(diǎn)是可以通過全局可行解隨機(jī)迭代更新達(dá)到高度收斂，防止陷入局部最優(yōu)。

(1)編碼和產(chǎn)生初始群體。

文中將每個節(jié)點(diǎn)看作一個基因，多個基因排列組成一個染色體，代表著路段Oi的一條數(shù)據(jù)轉(zhuǎn)發(fā)路由，可表示為：G={g1,…,gi,…,gm}(1

SDi=Loc(Xi)-Loc(X0)

(10)

根據(jù)式(10)選擇跳距SDi≤ξ的簇頭節(jié)點(diǎn)作為服務(wù)節(jié)點(diǎn)。若節(jié)點(diǎn)Xi被選為服務(wù)節(jié)點(diǎn)時，將其所在基因設(shè)為1，否則為0，即：

(11)

(2)建立適應(yīng)度函數(shù)。

適應(yīng)度函數(shù)的建立主要考慮以下兩個參數(shù)：無線鏈路信道質(zhì)量和節(jié)點(diǎn)剩余能量。

(a)無線鏈路信道質(zhì)量。

下一跳節(jié)點(diǎn)的優(yōu)劣并不能完全取決于跳距的大小，跳距大的節(jié)點(diǎn)可能具有較低的無線鏈路信道質(zhì)量。因此，文中引入無線鏈路質(zhì)量。信噪比是度量網(wǎng)絡(luò)鏈路信道質(zhì)量的一個主要技術(shù)指標(biāo)。設(shè)網(wǎng)絡(luò)無線帶寬為B，信道增益為G，PRi和PTi分別為接收和發(fā)送無線信號的有效功率，PSi為高斯噪聲的功率頻譜密度，則路段無線鏈路質(zhì)量LQi的計(jì)算公式為：

(12)

(b)節(jié)點(diǎn)剩余能量。

節(jié)點(diǎn)剩余能量是評估節(jié)點(diǎn)的另一個參數(shù)。為了延長車載網(wǎng)絡(luò)生存期，應(yīng)選擇剩余能量高的節(jié)點(diǎn)傳輸數(shù)據(jù)。假設(shè)每個節(jié)點(diǎn)具有相同的初始能量，表示為E0，當(dāng)剩余能量小于閾值時，就不再將其選為服務(wù)節(jié)點(diǎn)。若節(jié)點(diǎn)能量消耗為ECi，則節(jié)點(diǎn)剩余能量DEi可表示為：

DEi=E0-ECi

(13)

為便于研究，文中將忽略簇內(nèi)短距離無線信道微觀的多經(jīng)衰落現(xiàn)象。設(shè)Numi表示節(jié)點(diǎn)i所在簇的總節(jié)點(diǎn)數(shù)，ld表示數(shù)據(jù)包長度，EBit表示每比特?cái)?shù)據(jù)傳輸所消耗的能量，εmfp表示多經(jīng)衰落信道模式下的功率放大常數(shù)，εfsp表示自由空間信道模式下的功率放大常數(shù)，Ecol表示融合一比特?cái)?shù)據(jù)所消耗的能量，則簇頭服務(wù)節(jié)點(diǎn)能量消耗ECch和簇內(nèi)其他節(jié)點(diǎn)能量消耗ECco分別為：

ECch=2(Numi-1)ldEBit+ldEcol+

ldεmfpLength2(Xi,XM)

(14)

ECco=ldEBit+ldεfspLength4(Xi,Xij)

(15)

因此，節(jié)點(diǎn)的能量消耗ECi可表示為：

(16)

根據(jù)節(jié)點(diǎn)評估參數(shù)建立適應(yīng)度函數(shù)Fi，其計(jì)算公式如下：

(17)

其中，γ1+γ2=1。

(3)選擇、交叉、變異操作。

選擇操作是將適應(yīng)度函數(shù)值較大的服務(wù)節(jié)點(diǎn)保留下來，將其隨機(jī)組合成為一種可能的數(shù)據(jù)轉(zhuǎn)發(fā)鏈路，并作為遺傳過程中的父類個體樣本；交叉操作是對選擇操作的結(jié)果按照一定的交叉概率進(jìn)行變換，形成不同的路由選取方案，使算法具有全局搜索能力；變異操作是在數(shù)據(jù)轉(zhuǎn)發(fā)鏈路中，以一定的變異概率進(jìn)行服務(wù)節(jié)點(diǎn)的更改，這在很大程度上防止算法陷入局部最優(yōu)。算法偽碼如圖2所示。

圖2 GCCR算法偽碼

4 算法分析

4.1 計(jì)算復(fù)雜度

文中主要考慮算法的時間復(fù)雜度。設(shè)n表示節(jié)點(diǎn)數(shù)，則選擇下一跳路段和下一跳節(jié)點(diǎn)計(jì)算復(fù)雜度分別為O(1)和O(n)，因此GCCR算法的計(jì)算復(fù)雜度為O(n)。GCCR算法的計(jì)算復(fù)雜度主要與服務(wù)節(jié)點(diǎn)個數(shù)、車輛密度、網(wǎng)絡(luò)傳輸半徑等有關(guān)。在網(wǎng)絡(luò)傳輸半徑一定的情況下，文中將道路車輛密度引入下一跳路段的評價指標(biāo)中，并通過下一跳節(jié)點(diǎn)的跳距作為收斂條件，減少服務(wù)節(jié)點(diǎn)的冗余，有效降低了其算法復(fù)雜度。

4.2 網(wǎng)絡(luò)開銷

GCCR算法網(wǎng)絡(luò)負(fù)載開銷即數(shù)據(jù)轉(zhuǎn)發(fā)過程中收發(fā)數(shù)據(jù)包的多少。GCCR算法的網(wǎng)絡(luò)負(fù)載開銷主要集中于下一跳路段和下一跳節(jié)點(diǎn)的選擇過程。假設(shè)節(jié)點(diǎn)通過查詢-響應(yīng)機(jī)制獲取其他節(jié)點(diǎn)的信息，區(qū)域內(nèi)共N條路段，某路段Oi車輛密度為ρ，節(jié)點(diǎn)傳輸半徑為ξ，則選擇下一跳路段和下一跳節(jié)點(diǎn)的網(wǎng)絡(luò)負(fù)載開銷分別為?N/2」×「N/2?和ρπξ2。因此，執(zhí)行一次完整的GCCR算法所需的網(wǎng)絡(luò)負(fù)載開銷ONoh如下：

ONoh=?N/2」×「N/2?+ρπξ2

(18)

5 仿真結(jié)果及其分析

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

文中實(shí)驗(yàn)使用VMware虛擬機(jī)及Ubuntu16.04操作系統(tǒng)，模擬軟件為NS2.35(https://www.isi.edu/nsnam/ns/ns-build.html)。依據(jù)車載網(wǎng)絡(luò)安全預(yù)警應(yīng)用對網(wǎng)絡(luò)傳輸時延和無線鏈路穩(wěn)定性的要求，選取ω1=0.2，ω2=0.3，ω3=0.2，ω4=0.3，γ1=0.2，γ2=0.5，γ3=0.3。遺傳算法中交叉概率范圍一般選擇在0.6～1.0之間；變異概率通常選擇不大于0.1，本實(shí)驗(yàn)中交叉和變異概率分別設(shè)為0.8和0.1，此時算法表現(xiàn)最佳。實(shí)驗(yàn)中其他參數(shù)設(shè)置如表2所示。

表2 參數(shù)設(shè)置

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

為了驗(yàn)證GCCR算法的有效性，將其與經(jīng)典AODV貪婪路由算法和LEACH分簇路由算法進(jìn)行實(shí)驗(yàn)對比，其數(shù)據(jù)包投遞率、網(wǎng)絡(luò)傳輸時延和網(wǎng)絡(luò)開銷等對比如圖3～圖5所示。

圖3 數(shù)據(jù)包投遞率對比

圖4 網(wǎng)絡(luò)傳輸時延對比

圖5 網(wǎng)絡(luò)開銷對比

數(shù)據(jù)包投遞率指仿真時間內(nèi)目的節(jié)點(diǎn)接收到來自于源節(jié)點(diǎn)數(shù)據(jù)包總數(shù)與源節(jié)點(diǎn)發(fā)送數(shù)據(jù)包總數(shù)的比值。圖3顯示，節(jié)點(diǎn)數(shù)量一定時，數(shù)據(jù)包轉(zhuǎn)發(fā)投遞率與節(jié)點(diǎn)速率成反比。當(dāng)節(jié)點(diǎn)速率大于60 km/h時，以上算法投遞率下降加快，主要原因是節(jié)點(diǎn)速率較大時，能夠建立通信鏈路窗口期較短，節(jié)點(diǎn)間連通性變差。但GCCR算法相較于傳統(tǒng)路由算法具有更高投遞率，這主要與節(jié)點(diǎn)密度和網(wǎng)絡(luò)傳輸半徑等有關(guān)。當(dāng)網(wǎng)絡(luò)傳輸半徑一定時，文中將節(jié)點(diǎn)密度引入下一跳路段的評價指標(biāo)中，保證節(jié)點(diǎn)速率過快鏈路斷裂也仍能發(fā)現(xiàn)可替代中繼節(jié)點(diǎn)，加快路由修復(fù)，通信鏈路更加穩(wěn)定，投遞率也更高。網(wǎng)絡(luò)傳輸時延指數(shù)據(jù)包從源節(jié)點(diǎn)到目的節(jié)點(diǎn)所消耗的時間。圖4顯示，網(wǎng)絡(luò)傳輸時延隨節(jié)點(diǎn)速率增加呈上升趨勢，原因是當(dāng)節(jié)點(diǎn)速率增大時，鏈路穩(wěn)定性降低。由圖4可知，在任意速度下，GCCR算法傳輸時延均為最小，而以上三種路由算法計(jì)算復(fù)雜度均為O(n)，所以其主要原因是GCCR算法具有較少的冗余節(jié)點(diǎn)。文中所提出的節(jié)點(diǎn)密度閾值概念以下一跳節(jié)點(diǎn)跳距為收斂條件，減少了服務(wù)節(jié)點(diǎn)的冗余，收斂性表現(xiàn)良好，有效降低了網(wǎng)絡(luò)傳輸時延。

隨著節(jié)點(diǎn)速率增加，數(shù)據(jù)傳輸所需帶寬增加，如圖5所示，網(wǎng)絡(luò)開銷也逐漸增加。由式(18)可知，在節(jié)點(diǎn)傳輸半徑和數(shù)據(jù)包大小一定時，GCCR算法網(wǎng)絡(luò)開銷與路段車輛節(jié)點(diǎn)密度有關(guān)。算法設(shè)定車輛密度閾值選擇最佳路段，綜合考慮路段無線連通率和無線連通穩(wěn)定性，保證數(shù)據(jù)傳輸路段的網(wǎng)絡(luò)通信質(zhì)量，減少傳輸鏈路中轉(zhuǎn)發(fā)信息冗余，從而減少網(wǎng)絡(luò)開銷。綜上所述，GCCR算法在保證較高投遞率的情況下有效降低了網(wǎng)絡(luò)數(shù)據(jù)包傳輸時延和網(wǎng)絡(luò)開銷，滿足車載網(wǎng)絡(luò)安全預(yù)警應(yīng)用鏈路穩(wěn)定性、網(wǎng)絡(luò)實(shí)時性和數(shù)據(jù)包高效轉(zhuǎn)發(fā)等需求。

6 結(jié)束語

文中對傳統(tǒng)車載網(wǎng)絡(luò)路由算法進(jìn)行比較分析，在分簇路由算法的基礎(chǔ)上引入遺傳算法的思想，對數(shù)據(jù)包傳輸鏈路進(jìn)行優(yōu)化，最終提出一種基于遺傳特征的分簇路由算法。文中的創(chuàng)新點(diǎn)在于將車輛密度、節(jié)點(diǎn)剩余能量等參數(shù)引入下一跳路段或節(jié)點(diǎn)的選擇過程中，針對車輛高速行駛導(dǎo)致的網(wǎng)絡(luò)鏈路頻繁中斷和抖動、震蕩現(xiàn)象采取了平滑處理，更大程度上滿足安全預(yù)警應(yīng)用對網(wǎng)絡(luò)時延和穩(wěn)定性的較高要求。實(shí)驗(yàn)數(shù)據(jù)表明，該路由算法在數(shù)據(jù)包投遞率、網(wǎng)絡(luò)傳輸時延、網(wǎng)絡(luò)開銷方面均優(yōu)于傳統(tǒng)算法。

但文中算法在遺傳算法的實(shí)現(xiàn)過程中缺乏對車輛行駛速度、方向等參數(shù)的考慮，因此對于車輛高速行駛場景中的車輛數(shù)據(jù)不夠全面，缺乏魯棒性；當(dāng)車輛密度較小如交叉路口的行駛場景中，未考慮服務(wù)節(jié)點(diǎn)數(shù)據(jù)轉(zhuǎn)發(fā)受限的問題，而攜帶轉(zhuǎn)發(fā)又會導(dǎo)致傳輸時延增加，這一問題也是課題組未來進(jìn)一步研究的重點(diǎn)。