VANET隨機(jī)部署環(huán)境下基于改進(jìn)型共享最近鄰密度峰聚類的快速分簇算法

陳靖宇，徐志林

(廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣州 510006)

0 引言

隨著車輛數(shù)量的快速增長(zhǎng)，城市交通擁堵和交通安全的問題嚴(yán)峻，智能交通系統(tǒng)(ITS，intelligent transportation system)在這樣的背景下產(chǎn)生[1]。ITS提供的服務(wù)包括城市交通智能調(diào)度[2]，輔助駕駛[3]，交通預(yù)警等。ITS的應(yīng)用能夠有效緩解交通擁堵、減少交通事故發(fā)生，提高交通系統(tǒng)安全性[4]。車載自組織網(wǎng)絡(luò)(VANET，vehicular ad hoc network)作為ITS的核心部分，在實(shí)現(xiàn)有效的路側(cè)通信和數(shù)據(jù)傳輸過(guò)程中發(fā)揮著重要作用[5-6]。車載自組織網(wǎng)絡(luò)是一種分布式的無(wú)線網(wǎng)絡(luò)系統(tǒng)，該網(wǎng)絡(luò)系統(tǒng)由網(wǎng)絡(luò)節(jié)點(diǎn)間的動(dòng)態(tài)鏈接形成，不需要依賴既存的網(wǎng)絡(luò)架構(gòu)。VANET中的節(jié)點(diǎn)移動(dòng)速率較大導(dǎo)致網(wǎng)絡(luò)拓?fù)渥兓^大[7]，采用分簇機(jī)制能夠有效實(shí)現(xiàn)網(wǎng)絡(luò)的快速部署及動(dòng)態(tài)重建，提高網(wǎng)絡(luò)的可擴(kuò)展性[8]。分簇是指對(duì)VANET中的網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行分組，每個(gè)組稱為一個(gè)簇。每個(gè)簇至少擁有一個(gè)簇首(CH，cluster head)，簇中的其余節(jié)點(diǎn)為簇成員(CM，cluster member)。簇首能夠協(xié)調(diào)簇成員進(jìn)行簇內(nèi)及簇間通信。根據(jù)CH與CM間的距離，分簇算法可以分為單跳分簇和多跳分簇。單跳分簇中的CM節(jié)點(diǎn)處在CH的一跳通信范圍，CM與CH能夠直接通信，如文獻(xiàn)[9-10]。在多跳分簇中，由于CM節(jié)點(diǎn)不一定處在CH的一跳通信范圍，因此CM不一定直接與CH進(jìn)行通信，而是通過(guò)其他簇成員進(jìn)行轉(zhuǎn)發(fā)來(lái)實(shí)現(xiàn)與簇首的通信，如文獻(xiàn)[11-12]。VANET分簇算法一般包括簇首選取、成簇形成和簇維護(hù)三個(gè)過(guò)程。目前各學(xué)者在VANET分簇算法上已經(jīng)做了大量的工作，主要圍繞分簇算法的三個(gè)基本過(guò)程進(jìn)行研究，目的是提高成簇效率及簇的穩(wěn)定性[13]。

文獻(xiàn)[14]以節(jié)點(diǎn)的移動(dòng)速度、相對(duì)位置為依據(jù)，提出了一種移動(dòng)性指標(biāo)計(jì)算方法。該算法規(guī)定網(wǎng)絡(luò)通信的最大跳數(shù)為D跳，節(jié)點(diǎn)以移動(dòng)性指標(biāo)和節(jié)點(diǎn)連通度作為簇首選擇的依據(jù)，從其D跳鄰居中選擇符合條件的節(jié)點(diǎn)作為備用簇首，并維護(hù)一個(gè)長(zhǎng)度為D的備用簇首列表。節(jié)點(diǎn)與原簇首通信中斷時(shí)優(yōu)先使用備用簇首，從而降低成簇開銷。該方法通過(guò)備用簇首的策略在一定程度上降低了簇重構(gòu)的頻率，但由于備用簇首的選擇是在成簇階段完成的，并未考慮節(jié)點(diǎn)運(yùn)動(dòng)過(guò)程中網(wǎng)絡(luò)拓?fù)渥兓瘜?dǎo)致的備用簇首失效問題，因此該方法仍存在簇重構(gòu)頻率較大的問題。文獻(xiàn)[15]通過(guò)判斷節(jié)點(diǎn)所處區(qū)域的節(jié)點(diǎn)密度大小，使處于密度中心的節(jié)點(diǎn)向鄰居節(jié)點(diǎn)發(fā)出入簇邀請(qǐng)，從而將處于密度較高區(qū)域的節(jié)點(diǎn)分為同一個(gè)簇。此外該方法以節(jié)點(diǎn)的相對(duì)位置、速度和加速度為依據(jù)提出了一個(gè)移動(dòng)性指標(biāo)，用于簇首選擇。當(dāng)簇首離開簇時(shí)，簇內(nèi)成員將根據(jù)當(dāng)前節(jié)點(diǎn)的移動(dòng)性指標(biāo)推選出新的簇首。該方法能夠降低簇重構(gòu)的頻率，改善在高速移動(dòng)場(chǎng)景下節(jié)點(diǎn)狀態(tài)變化頻率較大的問題。但由于該方法僅根據(jù)節(jié)點(diǎn)的空間位置進(jìn)行簇的劃分，未考慮節(jié)點(diǎn)間通信的穩(wěn)定性，因此節(jié)點(diǎn)狀態(tài)變化頻率較大的問題仍然存在。文獻(xiàn)[16]提出了一種雙簇首策略，該方法在推選出主簇首后，由主簇首在其簇成員中選擇一個(gè)合適的節(jié)點(diǎn)作為副簇首。當(dāng)簇成員與主簇首的通信中斷時(shí)，由副簇首暫時(shí)承擔(dān)主簇首的功能。該方法以節(jié)點(diǎn)間的相對(duì)位置、相對(duì)速度、平均鏈路壽命、平均信號(hào)質(zhì)量為依據(jù)提出一種合適性指標(biāo)，將合適性指標(biāo)值的較大者作為簇首。文獻(xiàn)[17]以節(jié)點(diǎn)與鄰居節(jié)點(diǎn)間的平均距離、平均相對(duì)速度、平均相對(duì)加速度為依據(jù)，提出一種節(jié)點(diǎn)分?jǐn)?shù)指標(biāo)，將分?jǐn)?shù)較高者推選為簇首。該指標(biāo)考慮了節(jié)點(diǎn)與鄰居節(jié)點(diǎn)間的移動(dòng)相關(guān)性，能夠選擇移動(dòng)較穩(wěn)定的節(jié)點(diǎn)作為簇首，提高了簇首的穩(wěn)定性。該方法在完成簇首推選后，會(huì)周期性地在其簇成員中推選一個(gè)備用簇首；當(dāng)原簇首離開簇時(shí)，備用簇首將成為新的簇首。文獻(xiàn)[18]以節(jié)點(diǎn)間的通信質(zhì)量、節(jié)點(diǎn)連接壽命、一跳鄰居數(shù)量為依據(jù)，提出一種節(jié)點(diǎn)等級(jí)指標(biāo)，將節(jié)點(diǎn)通信范圍內(nèi)等級(jí)最高的節(jié)點(diǎn)推選為簇首，簇成員中等級(jí)最高的節(jié)點(diǎn)作為備用簇首。文獻(xiàn)[15-18]均采用了由簇首選擇備用簇首這一策略來(lái)降低簇重構(gòu)發(fā)生的頻率，但并未考慮簇首和備用簇首同時(shí)離開簇的情況，以及簇首在選擇備用簇首前就離開簇的情況。此外在文獻(xiàn)[15-18]的分簇方法中，簇首只能在本節(jié)點(diǎn)的通信范圍內(nèi)進(jìn)行選擇，簇的規(guī)模被節(jié)點(diǎn)通信范圍限制，因此以上方法的成簇規(guī)模較小，生成的簇?cái)?shù)量較多。

針對(duì)以上問題，提出一種基于改進(jìn)的共享最近鄰密度峰聚類[19]的VANET分簇算法(SNNCA，shared nearest neighbor clustering algorithm)，詳細(xì)的創(chuàng)新點(diǎn)概括如下：

1)將共享最近鄰的算法思想應(yīng)用于VANET分簇過(guò)程中，以兩節(jié)點(diǎn)的共同鄰居數(shù)量作為節(jié)點(diǎn)分簇的依據(jù)。該分簇方法能夠考慮節(jié)點(diǎn)間鄰居網(wǎng)絡(luò)的相似程度，從而達(dá)到延長(zhǎng)網(wǎng)絡(luò)穩(wěn)定周期的目的。

2)針對(duì)節(jié)點(diǎn)間連接穩(wěn)定性的問題，設(shè)計(jì)了一種基于節(jié)點(diǎn)鏈路生存周期和移動(dòng)相似性的綜合評(píng)估方法，并將該評(píng)估方法應(yīng)用于節(jié)點(diǎn)的共享最近鄰的計(jì)算，以得到劃分合理的分簇結(jié)果。

3)提出了一種多層級(jí)的簇成員控制機(jī)制，其中每個(gè)層級(jí)的簇成員擔(dān)任著維護(hù)下一層級(jí)簇成員的任務(wù)，從而降低了簇首的通信開銷。同時(shí)該機(jī)制能夠?qū)Υ爻蓡T進(jìn)行批量分離或合并，從而降低成簇開銷，提高了網(wǎng)絡(luò)的性能表現(xiàn)。

1 共享最近鄰密度峰聚類算法

共享最近鄰密度峰聚類(SNN-DPC，shared-nearest-neighbor-based clustering by fast search and find of density peaks)算法是一種基于密度峰點(diǎn)的聚類算法，它可以自動(dòng)地將數(shù)據(jù)集劃分成若干個(gè)簇。

共享最近鄰的成簇基于這樣的假設(shè)：兩個(gè)樣本點(diǎn)的共同鄰居總數(shù)越大，則它們更相似。SNN-DPC算法的基本思想是利用每個(gè)樣本點(diǎn)的局部密度和樣本點(diǎn)與其鄰居的距離來(lái)判斷該樣本點(diǎn)是否為簇中心，以及該點(diǎn)所屬的簇。該算法提出了K近鄰和共享最近鄰這兩個(gè)基本概念，用于參與聚類的過(guò)程。

其中，K近鄰指樣本點(diǎn)xi(xi∈X)與其他樣本點(diǎn)相似度最大的k個(gè)點(diǎn)，表達(dá)式如下：

Γ(i)={xj∈X|indexsim(xi，xj)≤k}

(1)

式中，index_sim(xi，xj)指樣本點(diǎn)xi與其他點(diǎn)xj的相似度在降序后的索引值。

共享最近鄰指兩個(gè)樣本點(diǎn)xi和xj的K近鄰集合的交集，表達(dá)式如下：

SNN(i，j)=Γ(i)∩Γ(j)

(2)

K近鄰和共享最近鄰能夠反映數(shù)據(jù)點(diǎn)之間的相似性和關(guān)聯(lián)性，同時(shí)還能夠有效地減少噪聲和異常點(diǎn)對(duì)聚類結(jié)果的影響。

在SNN-DPC算法中，首先需要構(gòu)建每個(gè)點(diǎn)的共享最近鄰圖(shared nearest neighbor graph，SNN)，然后根據(jù)每個(gè)點(diǎn)的局部密度和距離計(jì)算出各點(diǎn)的SNN密度和SNN距離，接著再將各點(diǎn)的SNN密度和SNN距離作為坐標(biāo)，畫出SNN密度圖，并找出其中的密度峰點(diǎn)。對(duì)于每個(gè)密度峰點(diǎn)，選擇其SNN密度大于一定閾值的最近鄰點(diǎn)作為該點(diǎn)的鄰居，并將這些鄰居點(diǎn)分配到該密度峰點(diǎn)所代表的簇中。如果鄰居點(diǎn)已經(jīng)被分配到其它簇中，則將該密度峰點(diǎn)與其它簇合并。不斷迭代該過(guò)程，直到所有點(diǎn)都被分配到簇中。最后輸出所有的簇結(jié)果。

SNN-DPC算法適用于處理大規(guī)模、高維度、復(fù)雜結(jié)構(gòu)的數(shù)據(jù)集，對(duì)于不同形狀和大小的簇的識(shí)別效果較好。該算法可以自動(dòng)確定簇的個(gè)數(shù)，同時(shí)對(duì)噪聲點(diǎn)有很好的容忍性。但是，該算法中K值的設(shè)置對(duì)聚類結(jié)果有較大的影響，需要根據(jù)具體問題進(jìn)行調(diào)整。

2 提出的SNNCA算法

道路環(huán)境上的車輛節(jié)點(diǎn)存在分布不均勻、移動(dòng)速度快的特點(diǎn)。SNN-DPC算法能夠有效識(shí)別具有不規(guī)則形狀的簇，但是在節(jié)點(diǎn)移動(dòng)的情況下無(wú)法進(jìn)行簇的劃分。因此，本文提出一種基于改進(jìn)的共享最近鄰密度峰聚類的VANET分簇算法SNNCA。

SNNCA算法考慮了節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)的連接穩(wěn)定性，將穩(wěn)定性相似的節(jié)點(diǎn)劃分為同一簇。本研究還提出了一種節(jié)點(diǎn)類型控制策略，能夠快速分離部分簇節(jié)點(diǎn)或合并多個(gè)簇，從而降低了簇重構(gòu)的成本。在本方法中，簇成員能夠根據(jù)鄰居節(jié)點(diǎn)情況自主維護(hù)簇信息，進(jìn)行簇成員的合并或分離操作。簇首的作用被削弱，對(duì)簇的劃分結(jié)果影響較小，因此本方法中簇首的選擇采用隨機(jī)選擇的方式。

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

2.1.1 網(wǎng)絡(luò)假設(shè)

本文對(duì)車載自組織網(wǎng)作了以下假設(shè)：(1)網(wǎng)絡(luò)節(jié)點(diǎn)基于WAVE協(xié)議棧進(jìn)行數(shù)據(jù)報(bào)文交換，WAVE在MAC層使用IEEE P1609標(biāo)準(zhǔn)，在PHY層使用IEEE 802.11p標(biāo)準(zhǔn)[20]；(2)車輛配有 GPS 接收器，車輛可通過(guò) GPS 實(shí)時(shí)獲取其當(dāng)前位置、速度、加速度等信息；(3)車輛的時(shí)鐘同步。

2.1.2 節(jié)點(diǎn)類型

SNNCA算法規(guī)定了三種節(jié)點(diǎn)類型，每種節(jié)點(diǎn)類型的具體介紹如下。

普通節(jié)點(diǎn)(ON，orphan node)：節(jié)點(diǎn)的初始類型；網(wǎng)絡(luò)中的節(jié)點(diǎn)從ON類型轉(zhuǎn)為其他類型后，不能再轉(zhuǎn)為ON類型。

簇成員(CM，cluster member)：節(jié)點(diǎn)加入簇后的狀態(tài)。本成簇方法形成的簇結(jié)構(gòu)為樹形結(jié)構(gòu)，簇層級(jí)從0開始記起，處于第0層的簇成員只有一個(gè)，稱為簇首(CH，cluster head)。

預(yù)備成簇節(jié)點(diǎn)(RN，ready node)：從簇中離開后，節(jié)點(diǎn)類型轉(zhuǎn)為RN。RN節(jié)點(diǎn)保留了上一次成簇的簇層級(jí)關(guān)系，便于節(jié)點(diǎn)快速恢復(fù)簇結(jié)構(gòu)。

圖1 節(jié)點(diǎn)類型轉(zhuǎn)移圖示

2.1.3 控制報(bào)文

SNNCA算法定義了以下四種控制報(bào)文用于其成簇過(guò)程和簇維護(hù)過(guò)程。

1)HELLO報(bào)文：

網(wǎng)絡(luò)中的節(jié)點(diǎn)通過(guò)周期性地廣播HELLO報(bào)文來(lái)向其鄰居節(jié)點(diǎn)更新自身信息。HELLO報(bào)文的信息如表1所示。

表1 HELLO 報(bào)文信息

2)JOIN報(bào)文：

ON、RN類型節(jié)點(diǎn)或者簇首節(jié)點(diǎn)通過(guò)向CM節(jié)點(diǎn)發(fā)出JOIN報(bào)文，來(lái)請(qǐng)求加入該CM節(jié)點(diǎn)所屬的簇。JOIN報(bào)文的信息如表2所示。

表2 JOIN報(bào)文信息

3)APPROVE報(bào)文：

CM節(jié)點(diǎn)接收到入簇請(qǐng)求，若允許新節(jié)點(diǎn)加入簇，則通過(guò)APPROVE報(bào)文向新節(jié)點(diǎn)發(fā)出響應(yīng)。APPROVE報(bào)文的信息如表3所示。

表3 APPROVE報(bào)文信息

4)CHANGE_STAT報(bào)文：

當(dāng)節(jié)點(diǎn)的簇信息發(fā)生改變時(shí)，需要通過(guò)CHANGE_STAT報(bào)文來(lái)通知子節(jié)點(diǎn)對(duì)自身的簇信息做相應(yīng)的更新。CHANGE_STAT報(bào)文的信息如表4所示。

表4 CHANGE_STAT報(bào)文信息

2.2 連接穩(wěn)定程度評(píng)估

車輛的位置坐標(biāo)、速度以及加速度可以通過(guò) GPS 獲得。設(shè)車輛節(jié)點(diǎn)一跳的傳輸范圍為r，節(jié)點(diǎn)i的速度為vi，加速度為ai，位置為(xi，yi)，速度方向與標(biāo)準(zhǔn)坐標(biāo)系的夾角為θi，加速度方向與標(biāo)準(zhǔn)坐標(biāo)系的夾角為φi。

2.2.1 鏈路生存周期

鏈路生存周期T(i，j)指兩節(jié)點(diǎn)i，j在彼此的通信范圍內(nèi)所能保持通信的最長(zhǎng)時(shí)間。根據(jù)車輛節(jié)點(diǎn)的瞬時(shí)速度、加速度、位置，以及節(jié)點(diǎn)通信范圍，可以預(yù)測(cè)節(jié)點(diǎn)間通信鏈路的生存周期。

對(duì)于車輛節(jié)點(diǎn)i，j，節(jié)點(diǎn)經(jīng)過(guò)時(shí)間Δt后的位置為：

(3)

當(dāng)節(jié)點(diǎn)i，j間的距離不超過(guò)通信范圍r時(shí)，節(jié)點(diǎn)間的通信可靠；兩節(jié)點(diǎn)的距離為r時(shí)所經(jīng)歷的最大時(shí)間為節(jié)點(diǎn)間的鏈路生存周期，可表示為：

r2=(dn-d0)2

(4)

其中：d0和dn分別為節(jié)點(diǎn)i，j在t0時(shí)刻和tn時(shí)刻下的歐氏距離。將式(4)變形后，得到方程：

(5)

以dn作為未知數(shù)，求解方程(5)，可以得到dn的值。接著，將dn的值代入以下方程，可以解得tn：

(6)

其中：

B=vj×cosθj-vi×cosθi

D=vj×sinθj-vi×sinθi

tn值最大的解即為節(jié)點(diǎn)間的鏈路生存周期。鏈路生存周期可以反映兩個(gè)節(jié)點(diǎn)之間通信連接的質(zhì)量和可靠性。鏈路生存周期越長(zhǎng)，說(shuō)明節(jié)點(diǎn)之間的通信連接越穩(wěn)定，可以更可靠地傳輸數(shù)據(jù)和信息。因此，鏈路生存周期對(duì)于VANET網(wǎng)絡(luò)中節(jié)點(diǎn)之間通信連接的評(píng)估和優(yōu)化具有重要意義。

2.2.2 移動(dòng)相似性

節(jié)點(diǎn)移動(dòng)相似性是指在VANET網(wǎng)絡(luò)中，兩個(gè)節(jié)點(diǎn)在一段時(shí)間內(nèi)的移動(dòng)行為具有相似性或一致性的程度，可以通過(guò)節(jié)點(diǎn)的速度、加速度對(duì)節(jié)點(diǎn)移動(dòng)相似性進(jìn)行度量。對(duì)于節(jié)點(diǎn)xi和節(jié)點(diǎn)xj，兩個(gè)節(jié)點(diǎn)的移動(dòng)相似性可表示為：

(7)

節(jié)點(diǎn)的移動(dòng)相似性由速度相似性和加速度相似性加權(quán)求和得出。式(7)中，Sv(i，j)為節(jié)點(diǎn)間的速度相似性，Sa(i，j)為節(jié)點(diǎn)間的加速度相似性，分別表示為：

(8)

(9)

將移動(dòng)相似性較高的節(jié)點(diǎn)劃分為同一簇，可以使得網(wǎng)絡(luò)中節(jié)點(diǎn)的移動(dòng)更加協(xié)同，提高網(wǎng)絡(luò)性能。同時(shí)，可以減少因節(jié)點(diǎn)頻繁移動(dòng)導(dǎo)致的鏈路斷開的情況，從而提高網(wǎng)絡(luò)的穩(wěn)定性和可靠性。

2.2.3 連接波動(dòng)程度

連接波動(dòng)程度考慮了鏈路生存周期和移動(dòng)相似性對(duì)節(jié)點(diǎn)間通信的影響，能夠?qū)?jié)點(diǎn)間通信鏈路的穩(wěn)定程度進(jìn)行評(píng)估：

(10)

連接波動(dòng)程度越低，說(shuō)明節(jié)點(diǎn)間的通信越穩(wěn)定。反之，連接波動(dòng)程度越高，說(shuō)明節(jié)點(diǎn)間出現(xiàn)連接異常的可能性較大，需要提前做好應(yīng)對(duì)措施，保障網(wǎng)絡(luò)的正常運(yùn)行。

2.3 基于共享最近鄰的簇劃分

基于共享最近鄰的簇劃分過(guò)程如圖2所示。首先設(shè)置車輛的最近鄰數(shù)為K，以車輛間的連接波動(dòng)程度作為相似度函數(shù)，計(jì)算車輛節(jié)點(diǎn)xi和xj的K近鄰。接著，基于節(jié)點(diǎn)xi和xj的K近鄰計(jì)算兩節(jié)點(diǎn)的共享最近鄰SNN(i，j)。

圖2 簇的劃分過(guò)程

(11)

則說(shuō)明xi和xj擁有較多連接穩(wěn)定的共同鄰居，兩節(jié)點(diǎn)的網(wǎng)絡(luò)情況相似，因此可直接劃分為同一簇。此時(shí)稱節(jié)點(diǎn)xj為節(jié)點(diǎn)xi的必然從屬點(diǎn)。

(12)

則說(shuō)明xi和xj擁有的連接穩(wěn)定的共同鄰居數(shù)量較少，需要對(duì)xi和xj的關(guān)系做進(jìn)一步判斷，才能確定xj是否從屬于xi所在的簇。此時(shí)稱節(jié)點(diǎn)xj為節(jié)點(diǎn)xi的可能從屬點(diǎn)。

為實(shí)現(xiàn)節(jié)點(diǎn)的分布式成簇，本文所提出的SNNCA算法未采用SNN-DPC算法中對(duì)可能從屬點(diǎn)的再分配步驟，轉(zhuǎn)而使用備選所屬簇作為簇的劃分依據(jù)。節(jié)點(diǎn)的備選所屬簇是指在該節(jié)點(diǎn)的K近鄰點(diǎn)中，出現(xiàn)次數(shù)最多的一個(gè)簇。假設(shè)簇的總數(shù)為m，則節(jié)點(diǎn)的備選所屬簇可表示為：

(13)

2.4 SNNCA算法流程

2.4.1 成簇過(guò)程

SNNCA算法的成簇過(guò)程如圖3所示，算法根據(jù)連接波動(dòng)程度來(lái)計(jì)算節(jié)點(diǎn)的K近鄰，以節(jié)點(diǎn)間的共享最近鄰數(shù)量和備選所屬簇作為簇的劃分依據(jù)。具體的成簇步驟如下。

圖3 成簇過(guò)程流程圖

第一步：節(jié)點(diǎn)間周期性地互相發(fā)送HELLO報(bào)文，節(jié)點(diǎn)通過(guò)HELLO報(bào)文來(lái)獲取自身一跳鄰居節(jié)點(diǎn)的信息。初始化時(shí)，節(jié)點(diǎn)類型為ON。

第二步：過(guò)濾鄰居節(jié)點(diǎn)，更新鄰居表。根據(jù)HELLO報(bào)文中提供的鄰居節(jié)點(diǎn)信息，進(jìn)行連接波動(dòng)程度F的計(jì)算，將F值小于設(shè)定閾值的鄰居節(jié)點(diǎn)加入鄰居表。同時(shí)，當(dāng)本節(jié)點(diǎn)與鄰居節(jié)點(diǎn)互相為父級(jí)節(jié)點(diǎn)時(shí)，會(huì)將該鄰居記錄移除，以避免形成環(huán)路，造成簇首缺失的問題。

第三步：以節(jié)點(diǎn)間的連接波動(dòng)程度作為節(jié)點(diǎn)間相似度的依據(jù)，連接波動(dòng)程度越小，相似度越大。計(jì)算本節(jié)點(diǎn)的K近鄰節(jié)點(diǎn)，將K 近鄰信息置于“HELLO”報(bào)文中廣播。

第四步：ON節(jié)點(diǎn)向其一跳鄰居節(jié)點(diǎn)中的CM節(jié)點(diǎn)發(fā)出JOIN報(bào)文。若經(jīng)過(guò)一定時(shí)間周期ON節(jié)點(diǎn)類型未改變，本節(jié)點(diǎn)將生成一個(gè)簇ID，成為新的簇，節(jié)點(diǎn)類型轉(zhuǎn)為CM，并立即廣播HELLO報(bào)文。

第五步：CM接收處理JOIN報(bào)文，為滿足條件的JOIN報(bào)文響應(yīng)允許入簇的APPROVE報(bào)文。若發(fā)出JOIN報(bào)文的節(jié)點(diǎn)與本CM節(jié)點(diǎn)屬于同一個(gè)簇，則將該報(bào)文丟棄，以避免簇內(nèi)節(jié)點(diǎn)形成環(huán)路。根據(jù)JOIN報(bào)文中的K近鄰信息判斷請(qǐng)求節(jié)點(diǎn)是否滿足必然從屬點(diǎn)的條件，若滿足則允許入簇。若僅滿足可能從屬點(diǎn)的條件，則判斷JOIN報(bào)文中的備選所屬簇是否與本節(jié)點(diǎn)的所屬簇相同，若相同則允許入簇。

第六步：ON接收到APPROVE報(bào)文后，節(jié)點(diǎn)類型轉(zhuǎn)為CM，并立即發(fā)出HELLO報(bào)文更新自身狀態(tài)。

在網(wǎng)絡(luò)初始化階段，多個(gè)節(jié)點(diǎn)可能同時(shí)啟動(dòng)成簇過(guò)程，從而在短時(shí)間內(nèi)形成多個(gè)簇。為了解決這個(gè)問題，本研究提出了一種簇維護(hù)方法，該方法能夠識(shí)別運(yùn)動(dòng)規(guī)律相似的多個(gè)簇，并將它們合并成一個(gè)簇，從而得到穩(wěn)定且合理的簇結(jié)構(gòu)。

2.4.2 簇成員離開

車載自組織網(wǎng)絡(luò)由于其拓?fù)渥兓l繁，容易導(dǎo)致車輛節(jié)點(diǎn)之間鏈路的中斷和重連。通過(guò)執(zhí)行簇維護(hù)過(guò)程，可以降低簇重構(gòu)的頻率，提高簇的穩(wěn)定性。簇維護(hù)過(guò)程涉及到簇成員的加入和離開兩種情況。在SNNCA算法中，簇成員的父級(jí)節(jié)點(diǎn)和孩子節(jié)點(diǎn)均為其一跳鄰居，因此節(jié)點(diǎn)可以根據(jù)其鄰居表信息確定其父級(jí)節(jié)點(diǎn)和孩子節(jié)點(diǎn)的信息。

簇中的非簇首節(jié)點(diǎn)會(huì)周期性地檢查其鄰居表中是否存在其父級(jí)節(jié)點(diǎn)。若不存在，則說(shuō)明本節(jié)點(diǎn)與父級(jí)節(jié)點(diǎn)的連接已斷開，需要執(zhí)行簇成員分離策略，從而將當(dāng)前節(jié)點(diǎn)及其子節(jié)點(diǎn)從簇中分離，避免因節(jié)點(diǎn)的簇信息不一致而導(dǎo)致成簇結(jié)果不穩(wěn)定。簇成員離開的處理過(guò)程如圖4所示，具體步驟如下。

圖4 簇成員離開流程圖

第一步：判斷當(dāng)前鄰居表中是否存在與本節(jié)點(diǎn)所屬簇相同且簇層級(jí)高于本節(jié)點(diǎn)的鄰居節(jié)點(diǎn)。若存在滿足條件的節(jié)點(diǎn)，則本節(jié)點(diǎn)向這些鄰居節(jié)點(diǎn)發(fā)出JOIN報(bào)文，等待響應(yīng)。若不存在滿足條件的節(jié)點(diǎn)，則將本節(jié)點(diǎn)類型轉(zhuǎn)為RN，節(jié)點(diǎn)層級(jí)重置為0，并立即發(fā)出CHANGE_STAT報(bào)文，通知其子節(jié)點(diǎn)更新簇信息。

第二步：節(jié)點(diǎn)接收到CHANGE_STAT報(bào)文，判斷源節(jié)點(diǎn)IP是否與其父節(jié)點(diǎn)IP相同，若相同，則更新節(jié)點(diǎn)類型為RN，自身簇層級(jí)設(shè)置為源節(jié)點(diǎn)簇層級(jí)加1，并立即發(fā)出CHANGE_STAT報(bào)文給其下一級(jí)簇成員。

第三步：下一級(jí)簇成員接收到CHANGE_STAT報(bào)文，重復(fù)第二步。

需要注意的是，RN類型的節(jié)點(diǎn)不能主動(dòng)發(fā)出或處理APPROVE報(bào)文，需要等待其父級(jí)節(jié)點(diǎn)發(fā)出狀態(tài)改變通知，使其重新轉(zhuǎn)為CM類型。若RN節(jié)點(diǎn)與其父節(jié)點(diǎn)通信斷開，則將本節(jié)點(diǎn)的層級(jí)重置為0，并立即向其孩子節(jié)點(diǎn)發(fā)出CHANGE_STAT報(bào)文。

SNNCA的簇成員分離策略可以將簇中的一組節(jié)點(diǎn)分離，并保留這組節(jié)點(diǎn)的簇層級(jí)關(guān)系。這種方法便于節(jié)點(diǎn)簇信息的快速更新，降低了成簇開銷。

2.4.3 簇成員加入

簇成員加入的處理過(guò)程如圖5所示。當(dāng)節(jié)點(diǎn)的類型為RN或CM，且簇層級(jí)為0時(shí)，該節(jié)點(diǎn)會(huì)周期性地發(fā)出入簇請(qǐng)求，從而實(shí)現(xiàn)單個(gè)節(jié)點(diǎn)加入簇，或簇的合并，具體步驟如下。

圖5 簇成員加入流程圖

第一步：若節(jié)點(diǎn)類型為RN，節(jié)點(diǎn)將周期性地向其一跳鄰居中的CM節(jié)點(diǎn)發(fā)出JOIN報(bào)文，并等待響應(yīng)。若節(jié)點(diǎn)類型為CM，則當(dāng)節(jié)點(diǎn)的備選所屬簇與節(jié)點(diǎn)當(dāng)前所屬簇不同時(shí)，才向其鄰居中的一跳CM節(jié)點(diǎn)發(fā)出JOIN報(bào)文。

第二步：若節(jié)點(diǎn)得到APPROVE報(bào)文響應(yīng)，則更新本節(jié)點(diǎn)的簇信息。若節(jié)點(diǎn)接收到多個(gè)APPROVE 報(bào)文，則優(yōu)先選擇與本節(jié)點(diǎn)的備選所屬簇相同，且源節(jié)點(diǎn)與本節(jié)點(diǎn)連接波動(dòng)程度最小的報(bào)文。若RN節(jié)點(diǎn)未得到APPROVE報(bào)文響應(yīng)，則該節(jié)點(diǎn)在經(jīng)過(guò)一段時(shí)間后將自動(dòng)轉(zhuǎn)為簇首，生成新的簇。

第三步：當(dāng)節(jié)點(diǎn)的簇信息發(fā)生變化時(shí)，會(huì)向連接穩(wěn)定度沒有超過(guò)設(shè)定閾值的子節(jié)點(diǎn)發(fā)送CHANGE_STAT報(bào)文。該報(bào)文將通知子節(jié)點(diǎn)更新它們的簇信息，以便與其它節(jié)點(diǎn)進(jìn)行同步。

在處理簇成員加入的過(guò)程中，步驟三可以幫助節(jié)點(diǎn)在執(zhí)行簇合并操作之前，提前將與其連接不穩(wěn)定的子節(jié)點(diǎn)分離，從而降低簇重建的頻率。如果本節(jié)點(diǎn)與子節(jié)點(diǎn)的連接穩(wěn)定度低于設(shè)定閾值，說(shuō)明該子節(jié)點(diǎn)與本節(jié)點(diǎn)通信的可靠性可能較低，因此不必再維護(hù)它們之間的關(guān)系。

3 仿真分析

3.1 仿真場(chǎng)景和參數(shù)設(shè)置

本文采用Matlab R2020a軟件對(duì)所提分簇算法的性能進(jìn)行評(píng)估，仿真區(qū)域?yàn)? 000×1 000 m的平面區(qū)域，節(jié)點(diǎn)的初始位置在區(qū)域內(nèi)隨機(jī)產(chǎn)生，節(jié)點(diǎn)移動(dòng)模型為Random Waypoint[21]。節(jié)點(diǎn)數(shù)量100個(gè)，移動(dòng)速率為10～50 m/s，節(jié)點(diǎn)傳輸范圍為100～300 m。實(shí)驗(yàn)?zāi)M時(shí)間為100 s。仿真時(shí)，SNNCA算法的K近鄰數(shù)設(shè)為19，連接波動(dòng)程度閾值為0.7。算法的評(píng)價(jià)指標(biāo)如下。

1)簇?cái)?shù)量Cn：實(shí)驗(yàn)結(jié)束時(shí)網(wǎng)絡(luò)中存在的簇?cái)?shù)量。若存在未加入簇的節(jié)點(diǎn)，則將該節(jié)點(diǎn)視為一個(gè)獨(dú)立的簇。在分簇網(wǎng)絡(luò)中，簇內(nèi)通信的開銷和時(shí)延會(huì)優(yōu)于簇間通信，因此減少簇的數(shù)量能夠降低通信開銷，提升網(wǎng)絡(luò)性能。

2)簇成員平均最長(zhǎng)壽命Cl：網(wǎng)絡(luò)節(jié)點(diǎn)在簇中的最長(zhǎng)存在時(shí)間的平均值。簇成員壽命越高，說(shuō)明節(jié)點(diǎn)進(jìn)行簇重建的頻率越小，簇結(jié)構(gòu)越穩(wěn)定。

3.2 仿真結(jié)果及分析

將SNNCA算法與文獻(xiàn)[18]所提出的分簇算法AC在不同實(shí)驗(yàn)場(chǎng)景下進(jìn)行仿真比較，實(shí)驗(yàn)中每組數(shù)據(jù)由50次仿真結(jié)果的平均值得到。

實(shí)驗(yàn)考察節(jié)點(diǎn)的傳輸范圍與移動(dòng)速度對(duì)算法的影響，采用以下兩種實(shí)驗(yàn)場(chǎng)景。場(chǎng)景一：節(jié)點(diǎn)移動(dòng)速率為30 m/s，節(jié)點(diǎn)傳輸范圍為100～300 m；場(chǎng)景二：節(jié)點(diǎn)傳輸范圍為200 m，節(jié)點(diǎn)移動(dòng)速率為10～50 m/s。

在實(shí)驗(yàn)中，隨著節(jié)點(diǎn)傳輸范圍的增大，網(wǎng)絡(luò)中的簇?cái)?shù)量逐漸減少。如圖6所示，當(dāng)傳輸范圍超過(guò)200 m時(shí)，SNNCA的簇?cái)?shù)量減少趨勢(shì)變緩，并穩(wěn)定在1個(gè)。與AC算法相比，SNNCA算法生成的簇?cái)?shù)量明顯較少。在傳輸范圍偏小的情況下，兩種算法生成的簇?cái)?shù)量都較大。AC算法屬于單跳分簇算法，當(dāng)傳輸范圍較小時(shí)，節(jié)點(diǎn)一跳鄰居的數(shù)量減少，因此簇的規(guī)模較小，簇?cái)?shù)量較多。SNNCA算法以兩節(jié)點(diǎn)的共享最近鄰作為分類依據(jù)，節(jié)點(diǎn)傳輸范圍的減小意味著共享最近鄰數(shù)較少，用于成簇決策的鄰居節(jié)點(diǎn)信息較少，導(dǎo)致算法傾向于將節(jié)點(diǎn)分為不同類，從而增加簇?cái)?shù)量。

圖6 Cn隨節(jié)點(diǎn)傳輸范圍的變化

如圖7所示，SNNCA算法和AC算法下的簇成員平均最長(zhǎng)壽命隨節(jié)點(diǎn)傳輸范圍的增大逐漸上升。在AC算法中，節(jié)點(diǎn)的等級(jí)指標(biāo)是根據(jù)其一跳鄰居的信息計(jì)算得到的，提高傳輸范圍有利于節(jié)點(diǎn)獲取更多鄰居信息，從而得到符合節(jié)點(diǎn)所處網(wǎng)絡(luò)情況的等級(jí)值。較準(zhǔn)確的等級(jí)值有助于算法選擇合適的簇首，以降低簇重構(gòu)的頻率，提高簇成員壽命。此外傳輸范圍的提高也能夠增大簇首與簇成員間的連接時(shí)間。在SNNCA算法中，傳輸范圍的增大有利于提高節(jié)點(diǎn)K近鄰信息的完整性和正確性，從而提高算法分類的準(zhǔn)確性，降低簇重建頻率，使簇成員壽命增加。然而當(dāng)傳輸范圍超過(guò)一定值時(shí)，節(jié)點(diǎn)已經(jīng)獲取到足夠的K近鄰信息用于分類，因此分類結(jié)果趨于穩(wěn)定，簇成員壽命穩(wěn)定。

圖7 Cl隨節(jié)點(diǎn)傳輸范圍的變化

網(wǎng)絡(luò)中的簇?cái)?shù)量隨節(jié)點(diǎn)移動(dòng)速率的變化如圖8所示。AC算法在節(jié)點(diǎn)移動(dòng)速率較小及較大的情況下生成的簇?cái)?shù)量較多。SNNCA算法中的簇?cái)?shù)量隨節(jié)點(diǎn)移動(dòng)速率的增加，變化穩(wěn)定，且簇?cái)?shù)量較少。當(dāng)移動(dòng)速率較小時(shí)，節(jié)點(diǎn)在一段時(shí)間內(nèi)的移動(dòng)范圍較小，網(wǎng)絡(luò)中的節(jié)點(diǎn)位置分散，此時(shí)AC算法中得到的簇?cái)?shù)量較多。當(dāng)節(jié)點(diǎn)的移動(dòng)速率較大時(shí)，節(jié)點(diǎn)的移動(dòng)規(guī)律差異變大，此時(shí)AC算法難以推選出一致的簇首節(jié)點(diǎn)，因此簇的數(shù)量增加。SNNCA算法擁有簇合并策略，在節(jié)點(diǎn)移動(dòng)過(guò)程中，簇首節(jié)點(diǎn)會(huì)根據(jù)周圍網(wǎng)絡(luò)情況組織簇成員加入其他簇，因此網(wǎng)絡(luò)中的簇?cái)?shù)量穩(wěn)定在較小范圍。

如圖9所示，兩種算法中的簇成員平均最長(zhǎng)壽命都隨著節(jié)點(diǎn)移動(dòng)速率的增加逐漸減少。AC算法為單跳分簇算法，當(dāng)節(jié)點(diǎn)移動(dòng)速率增大時(shí)，簇成員離開簇首通信范圍的時(shí)間縮短，因此簇成員壽命減少。SNNCA算法在移動(dòng)速率小于30 m/s時(shí)，簇成員壽命變化穩(wěn)定；在移動(dòng)速率大于30 m/s時(shí)，簇成員壽命下降幅度增大。在SNNCA算法中，當(dāng)簇成員與其父節(jié)點(diǎn)的連接中斷時(shí)，簇成員將啟動(dòng)合并策略，優(yōu)先加入簇類型相同，且層級(jí)不小于其父級(jí)的合適節(jié)點(diǎn)。這種簇維護(hù)方式使簇結(jié)構(gòu)能根據(jù)節(jié)點(diǎn)的運(yùn)動(dòng)情況進(jìn)行主動(dòng)優(yōu)化，使節(jié)點(diǎn)在簇中的停留時(shí)間增加，從而提高了簇成員壽命。但當(dāng)節(jié)點(diǎn)移動(dòng)速率過(guò)大時(shí)，節(jié)點(diǎn)的移動(dòng)規(guī)律變化較大，節(jié)點(diǎn)難以保持在同一個(gè)簇中，因此簇成員壽命減少。

圖9 Cl隨節(jié)點(diǎn)移動(dòng)速率的變化

3.3 不同K近鄰數(shù)下的網(wǎng)絡(luò)性能

在SNNCA算法中，簇成員的確定需要節(jié)點(diǎn)的K近鄰參與計(jì)算，因此K近鄰數(shù)的選取會(huì)影響成簇的結(jié)果?，F(xiàn)對(duì)不同K近鄰數(shù)下的SNNCA算法進(jìn)行仿真對(duì)比。仿真環(huán)境中的參數(shù)設(shè)定為：節(jié)點(diǎn)移動(dòng)速率為30 m/s，節(jié)點(diǎn)傳輸范圍為200 m，其他條件不變。仿真結(jié)果如表5所示。

表5 不同K近鄰數(shù)下的網(wǎng)絡(luò)性能

從表5中可以看出，在本實(shí)驗(yàn)條件下，當(dāng)K值處于15至23的范圍時(shí)，算法得到的簇?cái)?shù)量較少，簇成員的壽命較長(zhǎng)，此時(shí)網(wǎng)絡(luò)性能較穩(wěn)定。

網(wǎng)絡(luò)中的簇?cái)?shù)量在K值小于等于23時(shí)穩(wěn)定在2～3個(gè)，而當(dāng)K值超過(guò)23時(shí)，簇?cái)?shù)量發(fā)生小幅度增加。簇成員壽命的峰值出現(xiàn)在K=19時(shí)，在K大于23時(shí)降低幅度增大。

SNNCA算法中K近鄰的設(shè)置是為了篩選出與節(jié)點(diǎn)連接相對(duì)穩(wěn)定的鄰居節(jié)點(diǎn)，是判斷兩節(jié)點(diǎn)的鄰居網(wǎng)絡(luò)相似程度的依據(jù)。K的取值過(guò)小會(huì)導(dǎo)致K近鄰的數(shù)量不足以提供足夠的鄰居網(wǎng)絡(luò)信息進(jìn)行分類。當(dāng)K值過(guò)大時(shí)，K近鄰成員包含了節(jié)點(diǎn)的大部分鄰居，失去了篩選鄰居節(jié)點(diǎn)的作用。因此，過(guò)小或過(guò)大的K值會(huì)導(dǎo)致算法分簇的準(zhǔn)確性降低，增加簇重建的發(fā)生頻率，造成網(wǎng)絡(luò)中的簇?cái)?shù)量增大，簇成員壽命減少。

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

針對(duì)VANET網(wǎng)絡(luò)拓?fù)渥兓l繁而導(dǎo)致的分簇結(jié)果不穩(wěn)定的問題，提出了適合隨機(jī)部署場(chǎng)景的快速成簇算法SNNCA。該算法引入了連接波動(dòng)程度指標(biāo)來(lái)評(píng)估節(jié)點(diǎn)間連接的穩(wěn)定性，并且基于共享最近鄰思想進(jìn)行成簇操作。SNNCA算法考慮了節(jié)點(diǎn)之間網(wǎng)絡(luò)情況的相似性，將具有相似一跳鄰居網(wǎng)絡(luò)情況的節(jié)點(diǎn)分為同一簇，提高了簇成員在簇內(nèi)的存活時(shí)間。此外，本研究還提出了一種簇維護(hù)策略，通過(guò)周期性地檢查節(jié)點(diǎn)間連接的情況，對(duì)節(jié)點(diǎn)進(jìn)行簇的分離與合并操作，以構(gòu)建層級(jí)合理、穩(wěn)定的簇結(jié)構(gòu)，同時(shí)降低了簇的數(shù)量。針對(duì)節(jié)點(diǎn)數(shù)量多和成簇開銷大的問題，引入了預(yù)備成簇節(jié)點(diǎn)類型，使節(jié)點(diǎn)在離開簇后能夠保留上一次的簇層級(jí)信息，方便節(jié)點(diǎn)快速成簇，從而降低了成簇開銷。

經(jīng)仿真測(cè)試，與AC算法相比，SNNCA算法得到的簇?cái)?shù)量降低了74%，簇成員存活時(shí)間增加近1倍，基于該成簇方法得到的網(wǎng)絡(luò)穩(wěn)定性強(qiáng)，健壯性好。由于SNNCA中K近鄰的數(shù)目由經(jīng)驗(yàn)確定，過(guò)大或過(guò)小的K近鄰數(shù)會(huì)導(dǎo)致算法性能降低，因此如何確定合適的K近鄰數(shù)將是下一步的工作。