人工蜂與K-means混合算法在VANETs的應(yīng)用*

黃 欣，余思東，趙志剛

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

0 引言

車載自組織網(wǎng)(Vehicular Ad Hoc Networks，VANETs)是指由路邊單元、車輛之間構(gòu)成的一種移動自組織網(wǎng)絡(luò)，旨在提高交通安全系數(shù)，是智能交通的重要組成成分[1]。VANETs具有車輛高速移動的動態(tài)變化特點，容易造成其通信鏈路斷裂而通信質(zhì)量不佳?？煽慷€(wěn)定的成簇算法可以實時傳輸數(shù)據(jù)，減少網(wǎng)絡(luò)通信延遲，為智能交通系統(tǒng)奠定技術(shù)基礎(chǔ)。

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

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

1 材料與方法

1.1 人工蜂算法

人工蜂算法是Karaboga等[15]提出的一種新穎的全局優(yōu)化算法，其靈感來源于蜂群的采蜜過程，蜜蜂各司其職，具有獨特的正反饋機制，蜂群之間能夠?qū)崿F(xiàn)信息交互，進而快速尋找到最優(yōu)解。標準的人工蜂算法[16]包括蜜源、采蜜蜂(跟隨蜂)、引領(lǐng)蜂和偵察蜂，算法的目的是盡可能找到量多的蜜源?；镜娜斯し淙核惴ň唧w步驟如下：

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

(1)

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

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

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

(2)

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

且k≠i；

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

(3)

其中，fiti表示第i個蜜源對應(yīng)的適應(yīng)度值；

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

Step 6: 偵察蜂的轉(zhuǎn)換機制，假設(shè)某個蜜源經(jīng)過limit次迭代后適應(yīng)度值仍然保持不變，說明可能陷入局部最優(yōu)解，與此蜜源對應(yīng)的引領(lǐng)蜂將放棄此蜜源并轉(zhuǎn)變?yōu)閭刹旆?，然后用?1)隨機生成新蜜源，偵察蜂開始對這個新蜜源進行搜索并再次轉(zhuǎn)變?yōu)橐I(lǐng)蜂；

Step 7：記錄最優(yōu)蜜源gbest；

Step 8：判斷是否達到算法最大迭代次數(shù)，如否，則轉(zhuǎn)到Step 3，如是，則運行結(jié)束。

1.2 K-means算法

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

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

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

Step 3：重新計算類內(nèi)所有數(shù)據(jù)對象的均值作為各個新形成聚類的聚類中心；

Step 4：重復(fù)執(zhí)行Step 2-Step 3，直到聚類中心不發(fā)生變化，則算法結(jié)束。

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

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

1.3.1 蜜源編碼方式

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

1.3.2 適應(yīng)度函數(shù)設(shè)計

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

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

(4)

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

(5)

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

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

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

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

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

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

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

1.3.5 簇的形成

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

1.3.6 簇頭的選擇

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

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

(6)

1.3.7 簇的維護

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

1.4 實驗環(huán)境及參數(shù)設(shè)置

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

2 結(jié)果與分析

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

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

表1 集群簇頭選擇

Table 1 Cluster head selection

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

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

圖1 簇頭節(jié)點持續(xù)時間變化曲線圖

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

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

圖2 平均簇頭變化次數(shù)曲線圖

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

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

3 結(jié)論

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