人工蜂與K-means混合算法在VANETs的應用*

黃 欣，余思東，趙志剛

(1.廣西農業職業技術學院信息與機電工程系，廣西南寧 530007; 2.廣西大學計算機與電子信息學院,廣西南寧 530004)

0 引言

車載自組織網(Vehicular Ad Hoc Networks，VANETs)是指由路邊單元、車輛之間構成的一種移動自組織網絡，旨在提高交通安全系數，是智能交通的重要組成成分[1]。VANETs具有車輛高速移動的動態變化特點，容易造成其通信鏈路斷裂而通信質量不佳。可靠而穩定的成簇算法可以實時傳輸數據，減少網絡通信延遲，為智能交通系統奠定技術基礎。

為提高VANETs通信的可靠性以及穩定性，如何將VANETs更為準確地劃分成簇，使得計算成本最小化和網絡壽命周期最大化之間平衡，一些研究者將成簇算法用于VANETs中[2]。Gerla等[3]針對VANETs成簇的穩定性，提出一種基于節點的空間位置的最小ID成簇算法，給所有的節點標識唯一ID，將最小ID標識設置為簇頭。該算法實現簡單，計算成本低，但是犧牲了節點的負載均衡，不適用于高速移動的場景。Basu等[4]基于節點移動的差異提出最小相對移動成簇算法，該算法通過比較一個節點與其他節點的移動差異的方差來選擇簇頭，有效地提高了成簇的穩定性，但是也不適用于高速移動的場景。Chatterjee等[5]基于節點的移動特性、車輛流量以及節點能量提出一種按需加權的成簇算法，該算法較為全面地考慮了節點的特性，但是算法的計算成本也大大增加。許力文等[6]基于車輛的平均速度、位置和方向等信息，提出一種改進的K-means分簇算法，該算法利用改進的K-means算法劃分成簇，再利用改進的Floyd-Warshall算法選擇簇投，從而提高VANETs通信鏈路的穩定性。李炳圻等[7]考慮車輛的速度、位置和方向以及節點間的QoS提出了一種SQ-WCA成簇算法，實驗表明該算法在VANETs中具有穩定性和可靠性。

K-means算法[8]是基于劃分的常見聚類算法之一，具有實現簡單、較強的局部搜索能力、時間復雜度接近線性等優點，但是也存在一些不足，如對初始聚類中心依賴、容易出現“早熟”現象等。所以，有學者將群智能優化算法與K-means算法結合一起，例如粒子群優化算法[9-10]、人工蜂算法(Artificial Bee Colony,ABC)[11]等。作為一種新穎的群智能優化算法，人工蜂算法是于2005年通過模擬蜂群的采摘蜂蜜過程而被提出，目前已經成功應用于入侵檢測[12]、圖像分割[13]、組合優化問題[14]等多個領域。這里提出一種基于改進人工蜂的 K-means 優化聚類算法，并將其應用到VANETs分簇中。 通過改進人工蜂算法中蜂群的迭代搜索獲取全局最優的K個聚類中心，在此基礎上執行 K-means 算法劃分聚類，充分利用人工蜂算法的勘探能力和 K-means 算法的開發能力，避免過早陷入局部最優，消除 K-means 算法對初始聚類中心選取的依賴性，獲取近似全局最優的聚類劃分，提高算法的收斂速度以及改善聚類結果的質量。

1 材料與方法

1.1 人工蜂算法

人工蜂算法是Karaboga等[15]提出的一種新穎的全局優化算法，其靈感來源于蜂群的采蜜過程，蜜蜂各司其職，具有獨特的正反饋機制，蜂群之間能夠實現信息交互，進而快速尋找到最優解。標準的人工蜂算法[16]包括蜜源、采蜜蜂(跟隨蜂)、引領蜂和偵察蜂，算法的目的是盡可能找到量多的蜜源。基本的人工蜂群算法具體步驟如下：

Step 1：初始化算法基本參數，算法的最大迭代次數MaxIter，蜜源的最大迭代次數Limit，以式(1)方式產生SN個初始蜜源(采蜂蜜)xid；

(1)

Step 2：計算各個蜜源的適應度值fit，記錄各個蜜源的最好適應度值fit_pbest、所有蜜源中最好適應度值fit_gbest以及對應的蜜源；

Step 3：引領蜂通過式(2)的方式產生新蜜源x'id。若新蜜源的fit大于fit_pbest則引領蜂保留新蜜源，否則不更新；

x'id=xid+r(-1,1)(xid-xkd),

(2)

其中，xkd表示相鄰蜜源，k∈(1,2,…,SN)，

且k≠i；

Step 4：算法根據公式(3)計算每個蜜源的適應度值在所有蜜源的適應度值之和中所占的比重pi：

(3)

其中，fiti表示第i個蜜源對應的適應度值；

Step 5：跟隨蜂通過輪盤賭的選擇方式選擇蜜源，利用公式(2)進行更新操作，若新蜜源的fit大于fit_pbest則跟隨蜂保留新蜜源，否則不更新；

Step 6: 偵察蜂的轉換機制，假設某個蜜源經過limit次迭代后適應度值仍然保持不變，說明可能陷入局部最優解，與此蜜源對應的引領蜂將放棄此蜜源并轉變為偵察蜂，然后用式(1)隨機生成新蜜源，偵察蜂開始對這個新蜜源進行搜索并再次轉變為引領蜂；

Step 7：記錄最優蜜源gbest；

Step 8：判斷是否達到算法最大迭代次數，如否，則轉到Step 3，如是，則運行結束。

1.2 K-means算法

K-means算法是根據相似性原則計算平方誤差函數來作為評判標準，將一組數據X={x1,x2,…,xn}劃分到K個類簇C={c1,c2，…，ck}中，滿足簇間數據相似最小化，簇內數據相似最大化的要求。

算法的運行過程如下[10]：

Step 2：分別計算每個數據對象xi與 所有類中心的距離d(xi,cj)，并根據最近鄰原則將其劃分；

Step 3：重新計算類內所有數據對象的均值作為各個新形成聚類的聚類中心；

Step 4：重復執行Step 2-Step 3，直到聚類中心不發生變化，則算法結束。

1.3 人工蜂與K-means混合算法在VANETs分簇中的應用

人工蜂與K-means混合算法解決VANETs的分簇問題需要解決蜜源編碼以及適應度函數設計兩個問題。

1.3.1 蜜源編碼方式

根據數據集xi，劃分簇數K和特征數m，搜索空間解可表示為K*m的向量：即(c11,c12,c1m,…,cK1,cK2,cKm)。

1.3.2 適應度函數設計

一般而言，將平方誤差I作為評價聚類質量的標準，但是在ABC中的目的是搜索花蜜量最大的蜜源，聚類算法中I越小說明聚類效果越好，人工蜂與K-means混合算法適應度函數設計如公式(4)(5)所示，蜜源位置對應聚類中心位置：

在大多數生產型企業中，都設有專門的采購部門，管理工作也在逐漸完善。但是有些企業采購部門的管理工作依然存在不規范的現象，對采購工作的順利高效完成造成不利影響。具體包括：

(4)

f(x)=1/(1+I)。

(5)

1.3.3 人工蜂與K-means混合算法原理

K-means算法是基于劃分的常見聚類算法之一，人工蜂群算法是一種新穎的全局優化算法，綜合兩者，提出一種基于改進人工蜂的 K-means 優化聚類算法，通過改進人工蜂算法中蜂群的迭代搜索獲取全局最優的K個聚類中心，在此基礎上執行 K-means 算法劃分聚類，充分利用人工蜂算法的勘探能力和 K-means 算法的開發能力，避免過早陷入局部最優，消除 K-means 算法對初始聚類中心選取的依賴性，加快收斂速度。將 ABC的適應度函數fit設定為與 K-means聚類的衡量準則函數相關的函數，經過不斷地迭代返回適應度最優的蜜源，聚類中心點集就是使 K-means聚類的類內距離和最小的解，然后以這組聚類中心進行 K-means聚類得到最優的聚類效果。

1.3.4 人工蜂與K-means混合算法偽代碼

綜上，人工蜂與K-means混合算法實現過程如下：

Step 1：從數據集X中隨機選擇K個中心點，將其作為蜜源xi初值；

Step 2：執行ABC算法進行迭代搜索(見人工蜂算法實現流程)；

Step 3：執行K-means算法，按照類輸出即最終的聚類結果(見K-means算法實現流程)。

1.3.5 簇的形成

結合十字路口VANETs的場景，車輛在交通規則限定下以非勻速前進，利用人工蜂與K-means混合算法應用于其分簇，可以提高車輛之間的通信質量。簇的形成通過人工蜂算法進行，其主要思想是代替K-means獲取車輛節點分類的聚類點。

1.3.6 簇頭的選擇

在簇頭選取階段，僅僅把混合算法最終輸出的車輛劃分類的質心作為簇頭，只是依據位置來選擇而未考慮到速度，簇內計算所有 VANETs車輛的最短距離，將具有到其余車輛的最小平均距離且具有最小速度方差的車輛選擇為簇頭。參照文獻[6]，利用位置以及速度方差進行簇頭的選擇，根據黃金比例，速度方差VAR給予w1(0.618)的權重，平均距離AD給予w2(0.382)的權重。具有最小的合計分值(Total Score,TS)的車輛節點將被選擇為簇頭的候選。其計算方式是

TSi=count(w1VAR(Vi)+w2AD(Vi))。

(6)

1.3.7 簇的維護

在簇的維護階段，當最優節點的簇頭有變化時，次優節點被入選臨時簇頭，直至最優節點代替次優節點再次更新簇頭信息。

1.4 實驗環境及參數設置

實驗環境是MATLAB 2015Ra，Inter(R) Xeon(R) CPU E5-1620 v3 @3.5 GHz，win8操作系統。人工蜂與K-means混合算法的各個參數取值如下：ABC算法蜜源個數SN=20，種群規模NP=40；算法的最大迭代次數MaxIter=500，蜜源的最大迭代次數Limit=20，算法運行30次。十字路口的場景設置為每個車輛可以在1 000 m內運動，速度為60-120 km/h，車輛節點數目是10-100，通過比較分析人工蜂與K-means混合算法、PSO與K-means混合算法[17]、K-means算法[6]，主要從成簇的穩定性、端到端時延評價算法的性能。

2 結果與分析

根據公式(6)，TS越小，簇頭的穩定性越好。表1是其中一個簇內選擇簇頭的過程。

根據表1可知，車輛ID 4具有最小的TS值，因此適合作為簇頭。而僅僅以距離來衡量車輛的簇頭穩定性是不全面的，如表1中，車輛ID 6 具有最小的平均距離(AD)，但與其他車輛的速度差很大，如果選作簇頭，較大的速度差將影響簇頭的持續時間和平均距離。

表1 集群簇頭選擇

Table 1 Cluster head selection

ID平均距離AD (m)速度方差VAR (m)TS1116846.232145136.873436455.984164332.695448770.57699461.537961948.418572738.469635658.6710446959.45

3種算法的簇頭節點持續時間車輛速度變化如圖1所示。隨著速度的增大，3種算法的簇頭持續時間整體減少，這是因為速度增大，網絡拓撲結構頻繁變化。簇頭持續時間減少，導致通信鏈路變差，算法的穩定性就越差。而在相同的速度下，人工蜂與K-means混合算法簇頭持續時間是最長的，因為該算法不僅考慮了速度，還考慮了位置的因素，使得形成的簇比較穩定，通信鏈路也比較穩定。

圖1 簇頭節點持續時間變化曲線圖

圖2顯示3種算法在不同速度下平均簇頭變化次數變化情況。隨著速度的增大，3種算法的平均簇頭平均變化次數逐漸增大，與簇頭持續時間呈反比，說明簇頭持續時間越長，通信質量越穩定，簇頭平均變化次數越少。在相同速度下，人工蜂與K-means混合算法的平均簇頭變化次數是最小的，說明該算法比其他2種算法穩定。

圖3是3種算法有關車輛節點與端到端時延的變化情況。隨著車輛節點數目增大，會增加3種算法的端到端時延。車輛密度會影響車輛節點端到端時延。較穩定的簇頭兼具有較好的信道質量，可以降低端到端時延，加快通信鏈路的傳輸。在相同的車輛節點數目下，人工蜂-K-means混合算法具有最低的端到端時延，說明該算法對通信質量的提升程度比其他2種算法更佳。

圖2 平均簇頭變化次數曲線圖

圖3 端到端時延變化曲線圖

綜上，用人工蜂與K-means混合算法求解VANETs分簇問題是可行有效的，且比PSO與K-means混合算法、K-means算法性能更佳，主要原因有：(1)K-means算法過度依賴于初始聚類中心的選擇，而人工蜂與K-means混合算法利用人工蜂算法作為尋找初始聚類中心的搜索策略，再利用K-means算法進行聚類輸出最終結果，消除依賴性。(2)相比PSO和K-means混合算法，人工蜂與K-means混合算法具有更強大的全局搜索能力，使得該算法更快速尋找到最優解。(3)相對于其他2種算法，人工蜂與K-means混合算法充分考慮位置和速度影響因素，更加全面地說明該算法的可靠性。

3 結論

VANETs的車輛節點具有動態的特性，網絡拓撲結構頻繁變化導致通信鏈路不穩定。這里將人工蜂與K-means混合算法用于VANETs分簇中，即把場景內的車輛節點通過人工蜂算法分成不同集群，在利用K-means算法進行聚類結果的輸出。通過改進人工蜂算法中蜂群的迭代搜索獲取全局最優的K個聚類中心，在此基礎上執行K-means 算法劃分聚類，充分利用人工蜂算法的勘探能力和K-means 算法的開發能力，避免過早陷入局部最優，消除K-means算法對初始聚類中心選取的依賴性，加快收斂速度。分簇的穩定性影響集群通信鏈路的通信質量，穩定的簇頭可以更好地維持分簇的形狀以及簇頭持續時間。在以后的工作中，應對VANETs進行更深入的研究，嘗試將其他智能算法與K-means結合，并應用于VANETs中。