基于加權(quán)的具有相同移動特性的車載自組網(wǎng)分簇算法

李 雪, 南建國

(1.空軍工程大學研究生院，西安，710038；2.空軍工程大學航空工程學院，西安，710038)

隨著機動車、無線通信的不斷發(fā)展，車聯(lián)網(wǎng)也得到了迅猛發(fā)展。車載自組織網(wǎng)絡[1]作為車輛網(wǎng)的一個分支，應用于智能交通系統(tǒng)中的安全預警、協(xié)助駕駛中。在軍事應用方面，它可以很好地提升作戰(zhàn)車隊在通信、指揮控制和安全管理等方面的性能，提高作戰(zhàn)效率。

車載自組織網(wǎng)絡[2](Vehicular Ad-Hoc Network, VANET)是一種無中心、自組織、結(jié)構(gòu)開放的車輛間通信網(wǎng)絡。車載自組織網(wǎng)絡中的路由分為平面路由和分級路由[3-5]，分簇算法就是車載自組網(wǎng)實施分級路由采取的重要方法。目前，很多學者對分簇算法進行了改進。如文獻[6]將網(wǎng)絡中的節(jié)點分為不同等級，但簇頭的選舉只考慮了能量一個因素，未考慮簇頭節(jié)點與簇內(nèi)成員的移動性和距離因素。文獻[7]選擇鄰居節(jié)點多、與簇內(nèi)大部分成員運動方向相同且移動速度慢的節(jié)點作為簇頭，簇頭節(jié)點比較穩(wěn)定，若簇內(nèi)大多數(shù)成員移動速度較快會導致簇成員的離開非常頻繁。文獻[8]選舉簇頭時采用“相對典型節(jié)點度”來衡量節(jié)點的穩(wěn)定性，但沒有考慮節(jié)點之間的距離因素。文獻[9～10]在考慮簇頭節(jié)點與簇內(nèi)節(jié)點的距離因素時采用平均距離，這樣不能剔除部分極端節(jié)點。文獻[11～12]選舉簇頭時沒有考慮簇頭節(jié)點與簇內(nèi)成員的距離因素，可能造成簇頭節(jié)點與簇內(nèi)成員節(jié)點相距較遠。文獻[13]使用多普勒頻移計算節(jié)點間的相對移動速度，但在選擇簇首時只考慮了節(jié)點的鏈路維持時間。

針對上述問題，本研究考慮作戰(zhàn)車輛的移動特性問題，將具有速度相似度和距離相似度的作戰(zhàn)車輛劃分為一個簇，提高了簇結(jié)構(gòu)的穩(wěn)定性，防止因作戰(zhàn)車輛因速度、方向、距離等問題頻繁的離開或加入簇而帶來的廣播開銷，降低作戰(zhàn)效率。通過對節(jié)點的速度因子、距離因子和平均鏈路維持時間進行加權(quán)，選舉出權(quán)值最大的作戰(zhàn)車輛作為首要簇頭，權(quán)值第2大的作戰(zhàn)車輛作為次要簇頭。首要簇頭處于活躍狀態(tài)時，次要簇頭處于休眠狀態(tài)，屬于簇內(nèi)普通節(jié)點；當首要簇頭失效時，次要簇頭處于活躍狀態(tài)，充當首要簇頭，避免了因競爭簇頭帶來的時延差從而提高通信質(zhì)量。

1 分簇

在傳統(tǒng)的車載自組織網(wǎng)絡分簇算法中，一般用節(jié)點的速度差和平均速度來體現(xiàn)節(jié)點的移動特性，但只考慮這2個因素對移動特性的影響不夠合理。本文通過對移動節(jié)點的速度和方向進行計算，采用速度差的標準差來體現(xiàn)節(jié)點的移動特性。根據(jù)移動節(jié)點的速度相似度和距離相似度對區(qū)域內(nèi)的節(jié)點進行分簇，選擇具有相同移動特性且距離相近的節(jié)點作為一個分簇。若在一個分簇中簇成員過少，則網(wǎng)絡中的簇頭就會增加，孤立節(jié)點也會增多；若在一個分簇中簇成員過多，則簇頭節(jié)點的負擔會加大，且與相鄰簇頭進行信息傳遞時會增大跳數(shù)。因此，需要平衡每個分簇中簇成員的大小。本文規(guī)定每個分簇中的簇成員的最大閾值為nmax。

1.1 移動節(jié)點的速度相似度

節(jié)點i為節(jié)點j的一跳通信范圍內(nèi)的任意節(jié)點，則節(jié)點j與鄰居節(jié)點的速度相似度可以用速度差的標準差來反映。標準差[14]是節(jié)點j與鄰居節(jié)點速度平均值離散程度的一種衡量，標準差的值越大，表示大部分節(jié)點的速度和平均速度的差異越大，標準差的值越小，表示大部分節(jié)點的速度越接近速度的平均值。

目標節(jié)點的運動方向作為x軸，以x軸逆時針旋轉(zhuǎn)90°作為y軸。則節(jié)點i與節(jié)點j在x軸和y軸的速度差由下面的公式表示：

ΔVjx=Vjx-Vix=Vjcosβj-Vicosθi

(1)

ΔVjy=Vjy-Viy=Vjsinβj-Visinθi

(2)

式中：βj為節(jié)點j與x軸的夾角；θi為節(jié)點i與x軸的夾角。

設節(jié)點j一跳通信范圍內(nèi)的鄰居節(jié)點i有N個，則節(jié)點j與鄰居節(jié)點i在x軸和y軸上的平均速度差表示為：

(3)

(4)

節(jié)點j速度的相似度由節(jié)點j與鄰居節(jié)點i在x軸和y軸的速度差的標準差表示為：

(5)

(6)

由勾股定理可以求出節(jié)點j與鄰居節(jié)點i的速度差的標準差為：

(7)

若標準差δjv的值小于速度閾值q，則節(jié)點j與其鄰居節(jié)點具有運動速度和運動方向的相似性。

1.2 移動節(jié)點的距離相似度

節(jié)點i為節(jié)點j的一跳通信范圍內(nèi)的任意節(jié)點，則節(jié)點j與鄰居節(jié)點的距離相似度用距離差的標準差來反映。

(8)

式中：dji表示節(jié)點j與鄰居節(jié)點i通過GPS獲取的距離值。

(9)

若標準差的值δjd小于距離閾值p，則表明節(jié)點j與其鄰居節(jié)點的距離相近，即具有距離的相似性。

如果速度標準差大于速度閾值q，則需要舍棄與節(jié)點j速度差最大的鄰居節(jié)點i,若還大于q，依次類推進行舍棄直到滿足條件。同理，如果距離標準差大于距離閾值p,則需要舍棄與節(jié)點j距離差最大的鄰居節(jié)點i，若依然大于p，依次類推進行舍棄直到距離標準差小于p。只有當節(jié)點的速度標準差和距離標準差同時滿足小于速度閾值和距離閾值時，則節(jié)點j與其鄰居節(jié)點i才成為相似節(jié)點。若節(jié)點j與節(jié)點i是相似節(jié)點，節(jié)點i與節(jié)點s是相似節(jié)點，那么節(jié)點j與節(jié)點s也是相似節(jié)點，即相似節(jié)點具有傳遞性。所有的相似節(jié)點組成一個分簇，且每個簇的簇成員小于等于nmax。若簇成員大于nmax，則需要剔除與節(jié)點j速度差和距離差之和最大的鄰居節(jié)點，直到滿足簇內(nèi)成員節(jié)點數(shù)小于等于nmax。

2 選舉簇頭

在傳統(tǒng)的分簇算法中，一般選擇簇頭只是片面地考慮一個因素，且只是選舉一個相對最優(yōu)的節(jié)點作為簇頭，一旦選舉的簇頭因移動速度過快或其他因素離開該簇時，需要進行簇頭的重新選舉，這樣會因為延長數(shù)據(jù)傳輸?shù)臅r延而降低效率。文中對移動節(jié)點的速度相似度、距離相似度、平均鏈路維持率進行加權(quán)，選舉雙簇頭。

2.1 速度輔助因子

選舉簇頭的節(jié)點不僅要考慮它與周圍鄰居節(jié)點的速度是否相似，還應考慮該節(jié)點的加速度，選擇加速度相對較小即速度變化緩慢的節(jié)點作為簇頭。很多分簇算法在選舉簇頭時沒有考慮節(jié)點的加速度，導致簇頭移動速度變化很快而離開該簇，加大路由開銷。在軍事作戰(zhàn)時，簇頭的選舉舉足輕重，因此在本文中將速度與加速度結(jié)合作為選舉簇頭的一個權(quán)值。節(jié)點j加速度由下式表示：

(10)

式中：Vjt1、Vjt2分別表示節(jié)點j在t1、t2時刻通過GPS獲取的速度值。

移動節(jié)點j與鄰居節(jié)點i的速度差體現(xiàn)的是速度的相似性，標準差是為了剔除極端值，加速度是為了考慮節(jié)點在下一時刻的移動大小，經(jīng)過歸一化處理，速度輔助因子表示為:

(11)

2.2 距離輔助因子

在軍事作戰(zhàn)時還需要考慮節(jié)點j與目標節(jié)點的距離，這樣選舉的簇頭可以縮短時延，提高效率。經(jīng)過歸一化處理，距離輔助因子表示為：

H2=e-(δjd+dj-end)

(12)

式中：dj-end表示節(jié)點j與目標節(jié)點的距離。

2.3 平均鏈路維持率

ΔVx=Vicosα+Vj

(13)

ΔVy=Vi|sinα|

(14)

圖1 某時刻節(jié)點j與節(jié)點i的運動狀態(tài)

ΔVx=|Vicos|α-π|-Vj|

(15)

ΔVy=Visin|α-π|

(16)

勾股定理求得節(jié)點j與節(jié)點i的相對速度為：

(17)

假設Tji表示的是節(jié)點j與節(jié)點i的鏈路維持時間，則在鏈路維持時間內(nèi)兩節(jié)點在x軸和y軸方向上的相對移動距離表示為：

Δdx=ΔVxTji

(18)

Δdy=ΔVyTji

(19)

由勾股定理，可以求得2個節(jié)點的相對移動距離為：

(20)

由圖1可知，節(jié)點j與鄰居節(jié)點i維持在通信范圍內(nèi)距離差滿足：

(21)

式中：r為節(jié)點j的通信半徑。

因此，可求得節(jié)點j與鄰居節(jié)點i的最大鏈路維持時間，見式(22)：

(22)

根據(jù)上述方法可以求出節(jié)點j與鄰居節(jié)點的鏈路維持時間和最大鏈路維持時間，并取其平均值：

(23)

(24)

經(jīng)過歸一化處理，平均鏈路的維持率表示為：

(25)

2.4 聯(lián)合度量指標

由上述過程得到了節(jié)點j與鄰居節(jié)點i的速度輔助因子、距離輔助因子和平均鏈路維持率，對這3種因素進行加權(quán)求和。根據(jù)節(jié)點權(quán)重分簇算法(Weighted Clustering Aorithm,WCA)[15]綜合考慮這3個因素得到的復合權(quán)值如下：

Mi=ω1H1+ω2H2+ω3H3

(26)

式中：ω1、ω2、ω3的取值范圍在0和1之間，并且滿足ω1+ω2+ω3=1，具體大小根據(jù)實際情況取值。

依次計算簇內(nèi)所有節(jié)點與鄰居節(jié)點的Mi，取Mi值最大的作為首要簇頭，取Mi值第2大的作為次要簇頭。選取次要簇頭的目的是當首要簇頭失效時，次要簇頭立即充當首要簇頭，避免了因競爭簇頭帶來的時延差，且頻繁的簇頭輪換會產(chǎn)生額外的廣播開銷。

3 分簇算法及維護

3.1 分簇算法

本文在傳統(tǒng)分簇算法的基礎上，綜合考慮了作戰(zhàn)車輛的速度輔助因子、距離輔助因子和平均鏈路維持時間，并進行加權(quán)，選取權(quán)值最大的節(jié)點作為首要簇頭，權(quán)值第二大的作為次要簇頭。分簇算法的具體步驟如下所示：

步驟1網(wǎng)絡初始化階段，目標節(jié)點向作戰(zhàn)區(qū)域內(nèi)的所有節(jié)點廣播自己的hello(infor)包，infor是節(jié)點的基本信息，包含ID號、位置信息、方向角、速度等。所有節(jié)點周期性的向鄰居節(jié)點廣播自己的hello信息。節(jié)點得到鄰居節(jié)點的hello包，根據(jù)式(1)～(7)計算與相鄰節(jié)點的δjv值。若δjv小于閾值q，則該節(jié)點與所有鄰居節(jié)點具有速度相似度；反之剔除與該節(jié)點速度差最大的鄰居節(jié)點，重新計算直到滿足δjv小于閾值q。

步驟2根據(jù)式(8)～(9)計算與相鄰移動節(jié)點的距離相似度，若δjd小于閾值p，則該節(jié)點與所有鄰居節(jié)點具有距離相似度；反之剔除與與該節(jié)點距離差最大的鄰居節(jié)點，并重新計算δjd的值，直到小于閾值p。當該節(jié)點與鄰居節(jié)點同時滿足速度和距離的相似度時，則該節(jié)點與鄰居節(jié)點是關(guān)系節(jié)點，并將鄰居節(jié)點的信息存儲在自己的關(guān)系列表中。所有的關(guān)系節(jié)點就形成了一個分簇。

步驟3節(jié)點收集鄰居節(jié)點的hello信息，通過連續(xù)2次獲得的速度信息計算出鄰居節(jié)點的加速度，根據(jù)式(10)～(11)計算出節(jié)點的速度輔助因子。

步驟4節(jié)點通過接收目標節(jié)點發(fā)來的hello信息，并結(jié)合自身的位置信息計算出與目標節(jié)點的距離。通過式(12)得到該節(jié)點的距離輔助因子。

步驟5以該節(jié)點的運動方向作為x軸，并根據(jù)與鄰居節(jié)點的相對位置和運行方向通過式(13)～(25)得到該節(jié)點的平均鏈路維持率。

步驟6通過權(quán)重函數(shù)計算該節(jié)點的權(quán)重因子Mi，并與該簇內(nèi)所有節(jié)點的權(quán)重因子進行比較，選取權(quán)重因子最大的值作為PCH，權(quán)重因子第二大的值作為SCH。PCH為簇內(nèi)成員分配TDMA時隙，簇內(nèi)成員只在被分配的時隙內(nèi)將信息發(fā)送給簇頭節(jié)點，其余時間則處于休眠狀態(tài)。

步驟7重復步驟1～6，直到作戰(zhàn)區(qū)域內(nèi)的所有節(jié)點都確定了自己是普通節(jié)點或是簇頭節(jié)點為止。

3.2 簇維護機制

當作戰(zhàn)區(qū)域內(nèi)的所有車輛節(jié)點都完成分簇后，由于節(jié)點無規(guī)則且劇烈的運動，會造成移動節(jié)點加入新簇或離開原來的簇，甚至會使得首要簇頭或次要簇頭的更新，增大路由的開銷。因此，采取一種合理有效的簇維護機制[16]非常重要。網(wǎng)絡中節(jié)點的狀態(tài)有6個：孤立節(jié)點(Isolater Node，IN)、首要簇頭(Primary Cluster Head，PCH)、次要簇頭(Secondary Cluster Head，SCH)、簇成員(Cluster Member，CM)、偽孤立節(jié)點[17](Pseudo-Isolated Node，PIN)和網(wǎng)關(guān)節(jié)點(Gateway Node，GN)。當車載自組網(wǎng)的拓撲結(jié)構(gòu)發(fā)生變化時，采用下面4種規(guī)則進行重新分簇。

1)刪除簇內(nèi)節(jié)點。當簇內(nèi)的普通節(jié)點接收不到首要簇頭廣播的hello信息，或是首要簇頭接收不到該普通節(jié)點廣播的hello信息時，說明該節(jié)點已離開該簇。節(jié)點狀態(tài)由CM變?yōu)镻IN，若該節(jié)點長時間未回到該簇或加入其它簇，則狀態(tài)由PIN變?yōu)镮N。PIN狀態(tài)的設置是為了避免頻繁的簇維護加大路由開銷。最后首要簇頭將該節(jié)點從簇成員列表中刪除。

2)新節(jié)點的加入。未加入任何簇的孤立節(jié)點通過向周圍的鄰居節(jié)點發(fā)送自己的hello信息來獲得鄰居節(jié)點的hello信息，通過計算與鄰居節(jié)點的速度相似度和距離相似度，建立自己的關(guān)系節(jié)點列表。并向所有的關(guān)系節(jié)點發(fā)送信息來獲取關(guān)系節(jié)點所在簇的首要簇頭信息，再向這些首要簇頭發(fā)送信息獲取該節(jié)點與首要簇頭的速度差和距離差之和，選取值最小的首要簇頭且該簇的簇成員個數(shù)小于nmax，則加入該簇，該節(jié)點的狀態(tài)由IN變?yōu)镃M。最后首要簇頭將該節(jié)點加入到簇成員列表中。

3)簇頭的更換。當首要簇頭接收不到簇內(nèi)成員廣播的hello信息或是簇內(nèi)成員接收不到首要簇頭廣播的hello信息時，首要簇頭失效，狀態(tài)由PCH變?yōu)镃M。則次要簇頭成為首要簇頭，狀態(tài)由SCH變?yōu)镻CH，且簇內(nèi)成員節(jié)點通過競爭選取次要簇頭。

4)簇的合并。當2個簇的簇頭因為距離很近，且在一跳通信范圍內(nèi)時，其中一個簇的簇成員能夠聯(lián)系到另一個簇的首要簇頭，則該簇成員的狀態(tài)由CM變?yōu)镚N。首先判斷2個簇頭與簇內(nèi)成員是否為關(guān)系節(jié)點。若是關(guān)系節(jié)點則進行簇頭的競爭，選擇權(quán)重因子最大的值作為首要簇頭，權(quán)重因子第2大的值作為次要簇頭，競爭失敗的簇頭作為新簇頭的簇成員，狀態(tài)由PCH變?yōu)镃M，其余節(jié)點全部為簇成員，且簇成員的個數(shù)不得大于nmax；若不是關(guān)系節(jié)點，說明這2個簇的速度相似度差別較大，它們此時只是在距離上比較相近，很快就會遠離，當沒有任何一個簇成員可以同時聯(lián)系2個簇的首要簇頭時，則該簇成員的狀態(tài)由GN變?yōu)镃M。因此這2個分簇不能合并為1個簇，否則會加大路由開銷。

4 仿真與性能分析

采用NS-2軟件對本文的分簇算法進行性能分析，并與經(jīng)典的WCA算法和WBACA算法進行比較。仿真區(qū)域設為長寬各為300 m的矩形作戰(zhàn)區(qū)域，作戰(zhàn)車輛的運行速度為0～20 m/s，最大可接受的通信范圍為25 m，將50～300輛作戰(zhàn)車輛隨機布置在作戰(zhàn)區(qū)域內(nèi)，仿真時間為400 s，ω1、ω2、ω3的權(quán)重值分別為0.48、0.32、0.2，仿真結(jié)果見圖2～3。

圖2 節(jié)點數(shù)量-分簇的平均數(shù)量

圖2為不同節(jié)點數(shù)量下對應的分簇數(shù)量。WCA算法和WBACA算法在節(jié)點數(shù)為50時分簇的平均數(shù)量增長較快，本文算法在節(jié)點個數(shù)為200時分簇的平均數(shù)量增長迅速。當節(jié)點數(shù)量達到250時，本文算法的分簇平均數(shù)量與其它2種算法的差距最大。縱向來看，WBACA算法的分簇數(shù)量始終最少，而本文算法的分簇數(shù)量最多，因為本文為了平衡網(wǎng)絡減少擁塞，設置了每個分簇中簇成員的最高閾值，使得每個分簇的成員不會過高從而保證簇間的通信質(zhì)量。

圖3 節(jié)點數(shù)-簇頭節(jié)點更新數(shù)量

圖3顯示的是簇頭節(jié)點更新的數(shù)量。當節(jié)點數(shù)為50時，3種算法的簇頭更新數(shù)量相差不大，當節(jié)點數(shù)達到300時，本文算法的簇頭節(jié)點更新數(shù)量為56，WBACA算法的簇頭節(jié)點更新數(shù)量為89，WCA算法的簇頭節(jié)點更新數(shù)量為108。簇頭節(jié)點更新的數(shù)量越大，會造成簇結(jié)構(gòu)變化很快，使得信道資源被維護簇結(jié)構(gòu)所占用，降低信息傳輸?shù)男??？v向來看，本文的分簇算法簇頭節(jié)點更新的數(shù)量始終最少，簇結(jié)構(gòu)最穩(wěn)定。這是因為本文在選舉簇頭時，綜合考慮了速度因子、距離因子和鏈路的平均維持率，選擇與簇成員具有最大速度相似度、最大距離相似度，且與簇成員維持通信時間最長的節(jié)點作為簇頭，這樣的簇頭非常穩(wěn)定，不易失效。即使失效了，次要簇頭立即充當首要簇頭的角色，避免了重新選舉簇頭造成的時延，防止路由性能降低。

圖4顯示的是分組投遞率隨著節(jié)點密度的變化。當節(jié)點數(shù)為50時，3種算法的分組投遞率都較少且相差不大。當節(jié)點數(shù)為150時，3種算法的分組投遞率都達到最大，WCA算法達到78%，WBACA算法達到89%，本文算法達到90%。分組投遞率越高說明通信質(zhì)量越好，當節(jié)點數(shù)較少時車輛分布不均勻，運動不規(guī)律，丟包率較嚴重，所以分組投遞率都較低。隨著節(jié)點數(shù)增加，3種算法的分組投遞率都在增加。節(jié)點數(shù)增加到一定程度，即節(jié)點個數(shù)大于150時，分組投遞率隨之降低，這是因為節(jié)點數(shù)多了，網(wǎng)絡拓撲結(jié)構(gòu)變得復雜，且受到競爭、干擾等因素的影響，網(wǎng)絡擁塞也較嚴重，造成消息丟失的概率也增加，但本文算法的分組投遞率下降很緩慢，因為本文限制了簇成員的最大值，且簇頭給每個成員分配了TDMA時隙，降低了簇間信息的干擾。整體來看，本文提出的分簇算法的分組投遞率總是最高的，說明該算法的性能比另外2種算法優(yōu)越。

圖4 節(jié)點數(shù)-最大速度下的分組投遞率

5 結(jié)語

本文提出的基于加權(quán)的具有相同移動特性的車載自組網(wǎng)分簇算法通過將具有相同移動特性且距離相近的節(jié)點劃分為一個簇，提高了簇結(jié)構(gòu)的穩(wěn)定性。再通過對速度因子、距離因子和平均鏈路維持率進行加權(quán)選取首要簇頭和次要簇頭，主要簇頭給每個成員分配了TDMA時隙，提高了通信的質(zhì)量。但本文對路由分簇的考慮還不夠全面，比如當簇頭數(shù)量和簇覆蓋范圍具體為多少時路由性能最優(yōu)未考慮，下一步需要進行更深層次的研究。