陳靖宇，徐志林

(廣東工業(yè)大學 計算機學院，廣州 510006)

0 引言

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

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

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

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

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

3)提出了一種多層級的簇成員控制機制，其中每個層級的簇成員擔任著維護下一層級簇成員的任務，從而降低了簇首的通信開銷。同時該機制能夠對簇成員進行批量分離或合并，從而降低成簇開銷，提高了網絡的性能表現。

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

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

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

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

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

(1)

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

共享最近鄰指兩個樣本點xi和xj的K近鄰集合的交集，表達式如下：

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

(2)

K近鄰和共享最近鄰能夠反映數據點之間的相似性和關聯性，同時還能夠有效地減少噪聲和異常點對聚類結果的影響。

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

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

2 提出的SNNCA算法

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

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

2.1 網絡模型

2.1.1 網絡假設

本文對車載自組織網作了以下假設：(1)網絡節(jié)點基于WAVE協(xié)議棧進行數據報文交換，WAVE在MAC層使用IEEE P1609標準，在PHY層使用IEEE 802.11p標準[20]；(2)車輛配有 GPS 接收器，車輛可通過 GPS 實時獲取其當前位置、速度、加速度等信息；(3)車輛的時鐘同步。

2.1.2 節(jié)點類型

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

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

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

預備成簇節(jié)點(RN，ready node)：從簇中離開后，節(jié)點類型轉為RN。RN節(jié)點保留了上一次成簇的簇層級關系，便于節(jié)點快速恢復簇結構。

圖1 節(jié)點類型轉移圖示

2.1.3 控制報文

SNNCA算法定義了以下四種控制報文用于其成簇過程和簇維護過程。

1)HELLO報文：

網絡中的節(jié)點通過周期性地廣播HELLO報文來向其鄰居節(jié)點更新自身信息。HELLO報文的信息如表1所示。

表1 HELLO 報文信息

2)JOIN報文：

ON、RN類型節(jié)點或者簇首節(jié)點通過向CM節(jié)點發(fā)出JOIN報文，來請求加入該CM節(jié)點所屬的簇。JOIN報文的信息如表2所示。

表2 JOIN報文信息

3)APPROVE報文：

CM節(jié)點接收到入簇請求，若允許新節(jié)點加入簇，則通過APPROVE報文向新節(jié)點發(fā)出響應。APPROVE報文的信息如表3所示。

表3 APPROVE報文信息

4)CHANGE_STAT報文：

當節(jié)點的簇信息發(fā)生改變時，需要通過CHANGE_STAT報文來通知子節(jié)點對自身的簇信息做相應的更新。CHANGE_STAT報文的信息如表4所示。

表4 CHANGE_STAT報文信息

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

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

2.2.1 鏈路生存周期

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

對于車輛節(jié)點i，j，節(jié)點經過時間Δt后的位置為：

(3)

當節(jié)點i，j間的距離不超過通信范圍r時，節(jié)點間的通信可靠；兩節(jié)點的距離為r時所經歷的最大時間為節(jié)點間的鏈路生存周期，可表示為：

r2=(dn-d0)2

(4)

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

(5)

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

(6)

其中：

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

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

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

2.2.2 移動相似性

節(jié)點移動相似性是指在VANET網絡中，兩個節(jié)點在一段時間內的移動行為具有相似性或一致性的程度，可以通過節(jié)點的速度、加速度對節(jié)點移動相似性進行度量。對于節(jié)點xi和節(jié)點xj，兩個節(jié)點的移動相似性可表示為：

(7)

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

(8)

(9)

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

2.2.3 連接波動程度

連接波動程度考慮了鏈路生存周期和移動相似性對節(jié)點間通信的影響，能夠對節(jié)點間通信鏈路的穩(wěn)定程度進行評估：

(10)

連接波動程度越低，說明節(jié)點間的通信越穩(wěn)定。反之，連接波動程度越高，說明節(jié)點間出現連接異常的可能性較大，需要提前做好應對措施，保障網絡的正常運行。

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

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

圖2 簇的劃分過程

(11)

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

(12)

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

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

(13)

2.4 SNNCA算法流程

2.4.1 成簇過程

SNNCA算法的成簇過程如圖3所示，算法根據連接波動程度來計算節(jié)點的K近鄰，以節(jié)點間的共享最近鄰數量和備選所屬簇作為簇的劃分依據。具體的成簇步驟如下。

圖3 成簇過程流程圖

第一步：節(jié)點間周期性地互相發(fā)送HELLO報文，節(jié)點通過HELLO報文來獲取自身一跳鄰居節(jié)點的信息。初始化時，節(jié)點類型為ON。

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

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

第四步：ON節(jié)點向其一跳鄰居節(jié)點中的CM節(jié)點發(fā)出JOIN報文。若經過一定時間周期ON節(jié)點類型未改變，本節(jié)點將生成一個簇ID，成為新的簇，節(jié)點類型轉為CM，并立即廣播HELLO報文。

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

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

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

2.4.2 簇成員離開

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

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

圖4 簇成員離開流程圖

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

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

第三步：下一級簇成員接收到CHANGE_STAT報文，重復第二步。

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

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

2.4.3 簇成員加入

簇成員加入的處理過程如圖5所示。當節(jié)點的類型為RN或CM，且簇層級為0時，該節(jié)點會周期性地發(fā)出入簇請求，從而實現單個節(jié)點加入簇，或簇的合并，具體步驟如下。

圖5 簇成員加入流程圖

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

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

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

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

3 仿真分析

3.1 仿真場景和參數設置

本文采用Matlab R2020a軟件對所提分簇算法的性能進行評估，仿真區(qū)域為1 000×1 000 m的平面區(qū)域，節(jié)點的初始位置在區(qū)域內隨機產生，節(jié)點移動模型為Random Waypoint[21]。節(jié)點數量100個，移動速率為10～50 m/s，節(jié)點傳輸范圍為100～300 m。實驗模擬時間為100 s。仿真時，SNNCA算法的K近鄰數設為19，連接波動程度閾值為0.7。算法的評價指標如下。

1)簇數量Cn：實驗結束時網絡中存在的簇數量。若存在未加入簇的節(jié)點，則將該節(jié)點視為一個獨立的簇。在分簇網絡中，簇內通信的開銷和時延會優(yōu)于簇間通信，因此減少簇的數量能夠降低通信開銷，提升網絡性能。

2)簇成員平均最長壽命Cl：網絡節(jié)點在簇中的最長存在時間的平均值。簇成員壽命越高，說明節(jié)點進行簇重建的頻率越小，簇結構越穩(wěn)定。

3.2 仿真結果及分析

將SNNCA算法與文獻[18]所提出的分簇算法AC在不同實驗場景下進行仿真比較，實驗中每組數據由50次仿真結果的平均值得到。

實驗考察節(jié)點的傳輸范圍與移動速度對算法的影響，采用以下兩種實驗場景。場景一：節(jié)點移動速率為30 m/s，節(jié)點傳輸范圍為100～300 m；場景二：節(jié)點傳輸范圍為200 m，節(jié)點移動速率為10～50 m/s。

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

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

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

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

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

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

圖9 Cl隨節(jié)點移動速率的變化

3.3 不同K近鄰數下的網絡性能

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

表5 不同K近鄰數下的網絡性能

從表5中可以看出，在本實驗條件下，當K值處于15至23的范圍時，算法得到的簇數量較少，簇成員的壽命較長，此時網絡性能較穩(wěn)定。

網絡中的簇數量在K值小于等于23時穩(wěn)定在2～3個，而當K值超過23時，簇數量發(fā)生小幅度增加。簇成員壽命的峰值出現在K=19時，在K大于23時降低幅度增大。

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

4 結束語

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

經仿真測試，與AC算法相比，SNNCA算法得到的簇數量降低了74%，簇成員存活時間增加近1倍，基于該成簇方法得到的網絡穩(wěn)定性強，健壯性好。由于SNNCA中K近鄰的數目由經驗確定，過大或過小的K近鄰數會導致算法性能降低，因此如何確定合適的K近鄰數將是下一步的工作。