基于改進近鄰傳播算法的無線傳感網(wǎng)分簇與節(jié)能

衛(wèi)嵐寧 林 海 王 磊

(武漢大學國際軟件學院 湖北 武漢 430000)

0 引 言

無線傳感器網(wǎng)絡(luò)WSN由一定量具有感知、計算和無線通信能力的節(jié)點組成，這些傳感器采集周圍的數(shù)據(jù)，并將信息發(fā)送給基站。節(jié)點具有一定的能量，信息的采集、計算，通信偵聽，發(fā)送都需要消耗能量，能量耗盡則節(jié)點死亡，對數(shù)據(jù)采集有很大的影響。因此無線傳感網(wǎng)的節(jié)能控制一直是無線傳感網(wǎng)的核心問題[1]。

網(wǎng)絡(luò)層的路由技術(shù)在無線傳感網(wǎng)中起著關(guān)鍵作用，從網(wǎng)絡(luò)拓撲結(jié)構(gòu)的角度可將其分為平面路由和分簇路由兩種[2]。

在分簇路由中：網(wǎng)絡(luò)被劃分成簇，每個簇都有自己的簇頭和多個普通成員。低一級網(wǎng)絡(luò)的簇頭是高一級網(wǎng)絡(luò)中的簇內(nèi)成員，由最高層的簇頭與基站BS通信[2]。

聚類過程大致分為三個階段：簇頭的產(chǎn)生、簇的形成和穩(wěn)定運行階段。簇頭應(yīng)該盡可能在簇的中央以提高簇的內(nèi)聚度，相鄰簇之間的覆蓋應(yīng)該盡可能小以減小簇的耦合度。LEACH( Low Energy Adaptive Clustering Hierarchy)協(xié)議[3]假設(shè)所有的節(jié)點之間都可以相互通信，通過一定的概率來隨機循環(huán)產(chǎn)生簇頭，其余的非簇頭節(jié)點選擇一個最近的簇頭，加入該簇。分布式的LEACH有利于網(wǎng)絡(luò)的擴展，但是這種隨機選舉簇頭的方式會導致簇的結(jié)構(gòu)不合理，簇頭分布不均，并且沒有考慮到能量因素，簇頭很快就會死亡。LEACH-C[3]是集中式的LEACH算法，由基站指定能量較高節(jié)點作為簇頭。這種方式保證簇頭節(jié)點不會過快死亡，但是仍是要求節(jié)點之間可以直接通信。

HEED(A Hybrid Energy-Efficient Distributed Clustering Approach)協(xié)議[4]是可用于大型異構(gòu)分布式網(wǎng)絡(luò)的算法，針對LEACH算法簇頭分布不均的問題進行了改良。算法有兩個參數(shù)[5]：參數(shù)AMRP是簇內(nèi)成員節(jié)點和簇頭通信消耗的平均能量；參數(shù)CHprob的值和節(jié)點自身能量有關(guān)，能量高的節(jié)點CHprob值也大，成為臨時簇頭的可能性也更大，簇重疊區(qū)域的節(jié)點根據(jù)AMRP值選擇簇加入。

CPAP(Clustering Based on P-Changed Affinity Propagation)[2]算法中提出修改參考度p來使網(wǎng)絡(luò)達到預(yù)計的最優(yōu)簇頭數(shù)目。每次信息采集完后由基站重新規(guī)劃新的簇，但是新簇的能量開銷太大，且文中并未明確指出選舉間隔。APCRA(Affinity Propagation Clustering Routing Algorithm)算法[6]中提出，由基站規(guī)劃初始簇和簇頭，隨后每次新的簇頭由上一任簇頭根據(jù)節(jié)點的剩余能量和位置決定。這種方法減小了新簇產(chǎn)生時的開銷，但是文中采用的是小型網(wǎng)絡(luò)，節(jié)點之間通信沒有距離限制，不適用于大型網(wǎng)絡(luò)。

基于上述問題，本文在原始AP算法的基礎(chǔ)上提出新的改進方法 EAPCP。針對大型網(wǎng)絡(luò)，對分簇方法進行優(yōu)化，提高網(wǎng)絡(luò)能量利用率；針對網(wǎng)絡(luò)中通信距離的限制，對AP算法中的數(shù)據(jù)交換對象進行篩選；對參考度p進行修改，綜合考慮網(wǎng)絡(luò)整體的能耗、節(jié)點的剩余能量、節(jié)點的分布情況和最優(yōu)簇頭數(shù)的大小，并計算分簇完成后網(wǎng)絡(luò)穩(wěn)定運行輪數(shù)。

1 AP算法

近鄰傳播聚類算法[7]AP(Affinity Propagation)于2007年由Frey等在《Science》上提出，該算法一經(jīng)提出一直受到各個研究領(lǐng)域的廣泛關(guān)注，特別是在無線傳感網(wǎng)領(lǐng)域有著很大的研究價值。

AP算法是一種聚類算法，其本質(zhì)是一種基于因子圖的信念傳播和最大化算法[8]，最初是用于數(shù)據(jù)挖掘和統(tǒng)計。和其他需要指定初始簇頭并進行優(yōu)化的聚類算法不同[9]，AP算法不需要事先指定聚類數(shù)目，而是將所有的數(shù)據(jù)點都作為潛在的聚類中心。

假設(shè)有x1到xn，n個數(shù)據(jù)節(jié)點，節(jié)點之間的結(jié)構(gòu)是隨機的，定義S(i,k)為節(jié)點xi和節(jié)點xk之間的相似度并且S的值由節(jié)點之間的歐氏距離決定，即S(i,k)=-‖xi-xk‖2，所有節(jié)點之間的S值可以構(gòu)成一個矩陣，稱為相似矩陣。

矩陣對角線上的值S(i,i)表示的是一個節(jié)點成為簇頭的可能性，也稱為參考度p，p值越大，表明該節(jié)點成為簇頭的可能性越大。p值決定了簇的數(shù)目，p值越大，簇的數(shù)目越多，一般p值取所有節(jié)點之間相似度的平均值。

算法的運行主要包括傳遞兩種類型的消息來更新兩個矩陣：

1) 由r消息(responsibility)構(gòu)成的R矩陣：r(i,k)表示候選節(jié)點xk作為節(jié)點xi的簇頭的合適程度。

2) 由a消息(availability)構(gòu)成的A矩陣：a(i,k)表示節(jié)點xi選候選節(jié)點xk作為它的簇頭的合適程度。

兩個矩陣初始值都為0，算法更新過程如下：

1) 首先，節(jié)點之間更新交換r消息：

(1)

2) 然后根據(jù)r消息來更新交換a消息：

(2)

3) 對矩陣A和R進行迭代，直到兩個矩陣的數(shù)值保持不變或者達到指定的迭代次數(shù)，迭代過程更新公式如下：

Ri=(1-λ)Ri+λRi-1

(3)

Ai=(1-λ)Ai+λAi-1

(4)

4) 根據(jù)a(k,k)+r(k,k)的值選出簇頭，非簇頭節(jié)點選擇最近的簇頭，加入該簇。

2 EAPCP算法

2.1 優(yōu)化簡介

原始的AP算法中只是一種聚類算法，無線傳感網(wǎng)中節(jié)點有通信距離和能量的限制，所以對原始的AP算法做了改進。

1) 基于能量的簇頭選擇：p值體現(xiàn)了節(jié)點成為簇頭的能力，通過調(diào)整p值選擇一個能量較高的節(jié)點作為簇頭，這樣能夠有效延長網(wǎng)絡(luò)壽命。

2) 最優(yōu)簇數(shù)目的選擇：分簇結(jié)果的好壞關(guān)系到網(wǎng)絡(luò)壽命，選擇一個合理的簇的個數(shù)能夠有效延長網(wǎng)絡(luò)壽命。LEACH中簇頭可以直接和基站通信，在大型網(wǎng)絡(luò)中簇頭通過簇間路由將數(shù)據(jù)包發(fā)送至基站，基于此優(yōu)化LEACH中提出的最優(yōu)簇個數(shù)算法。

3) 穩(wěn)定運行輪數(shù)的計算：聚類的第三部分是穩(wěn)定運行階段，簇建立階段和穩(wěn)定運行階段所持續(xù)的時間總和為一個周期，網(wǎng)絡(luò)需要定期重新選舉以保證節(jié)點不會很快死亡。為了減少協(xié)議開銷，穩(wěn)定運行階段的持續(xù)時間要比選舉過程長。根據(jù)當前簇頭的能耗計算網(wǎng)絡(luò)此次的穩(wěn)定運行輪數(shù)，合理利用節(jié)點能量。

4)a、r消息的改進：原始的a、r消息需要計算本節(jié)點和其他所有節(jié)點之間的數(shù)值，但是在傳感網(wǎng)中節(jié)點有通信距離限制，消息只是在鄰居之間傳播，因此將之優(yōu)化為：

(5)

(6)

式中：用N(i)表示i的鄰居集合。

2.2 基于能量的簇頭選擇

參考度p體現(xiàn)了節(jié)點成為簇頭的能力，在原始的AP算法中，參考度p的取值通常為S矩陣的均值，并且所有節(jié)點都相同，這就表明所有節(jié)點成為簇頭的能力相同。但是在無線傳感網(wǎng)中，通常選擇能量較高的節(jié)點作為簇頭，這樣能延長網(wǎng)絡(luò)壽命。因此將能量因素加入其中，同時考慮網(wǎng)絡(luò)的密度，選取的簇頭數(shù)達預(yù)計最優(yōu)，減少網(wǎng)絡(luò)能耗。其中：

(7)

S(i,i)=pi

(8)

(9)

2.3 最優(yōu)簇數(shù)目的選擇

簇個數(shù)對網(wǎng)絡(luò)能量消耗有很重要的作用，簇數(shù)太多會導致數(shù)據(jù)融合效率低，冗余數(shù)據(jù)消耗能量；簇數(shù)目過少則簇內(nèi)成員過多，簇頭接收數(shù)據(jù)包消耗的能量也增多，能量消耗快容易導致網(wǎng)絡(luò)提前崩潰。

簇內(nèi)的成員只需要將采集的信息發(fā)送給簇頭，簇頭整合后發(fā)送給匯聚節(jié)點(Sink)。

假定在M×M區(qū)域內(nèi)均勻分布N個節(jié)點，網(wǎng)絡(luò)的最優(yōu)簇頭數(shù)為Kopt，用Heinzelman提出的一階無線通信模型[3]來模擬節(jié)點通信。則整個網(wǎng)絡(luò)的能量消耗為：

(10)

式中：l是數(shù)據(jù)包的長度，Eelec是收發(fā)1 bit數(shù)據(jù)消耗的能量，EDA是數(shù)據(jù)融合時消耗的能量，k是簇個數(shù),dCH-CH表示的是兩個簇頭間的平均距離,dtoCH是簇內(nèi)成員到簇頭的平均距離，Rc表示簇內(nèi)通信距離，Rr表示簇間通信距離。因為節(jié)點是均勻分布的，所以：

(11)

將式(11)代入式(10)，對k求偏導數(shù)，并令該偏導數(shù)為零，則最優(yōu)簇頭數(shù)Kopt：

(12)

因為簇頭間的距離必須小于簇間通信范圍，即dCH-CH2Rc，那么可以得到：

2Rc

(13)

根據(jù)式(13)可以求得最優(yōu)簇頭數(shù)Kopt的范圍，但是這個范圍很大，需要進行進一步的縮小。

簇內(nèi)通信距離Rc有一定限制，假定簇形成的圓之間均不重合，為了保證所有的節(jié)點都能分到簇內(nèi)，Kopt需要滿足：

(14)

結(jié)合式(13)、式(14)可以進一步縮小Kopt的范圍，在此范圍內(nèi)進行進一步的篩選，即可得出網(wǎng)絡(luò)的最優(yōu)簇頭數(shù)。

2.4 簇的穩(wěn)定運行輪數(shù)

無線傳感網(wǎng)中應(yīng)當盡可能延長節(jié)點的使用時間，使節(jié)點盡可能在同一時間死亡，盡可能的將網(wǎng)絡(luò)消耗的能量平攤到每個節(jié)點身上。節(jié)點有兩種狀態(tài)，一種是簇頭狀態(tài)，另一種是非簇頭狀態(tài)。兩種狀態(tài)下消耗的所有的能量就是節(jié)點的初始能量。

假定節(jié)點當前剩余能量為Ei，節(jié)點成為簇頭時每輪消耗的能量為ECH,節(jié)點不是簇頭時，每輪消耗的能量是EnonCH。從當前狀態(tài)一直到節(jié)點死亡，節(jié)點作為簇頭會運行m輪，作為非簇頭會運行n輪，則：

mECH+nEnonCH=Ei

(15)

網(wǎng)絡(luò)的預(yù)期運行輪數(shù)是m+n，每輪預(yù)期的簇頭數(shù)是k，則共需(m+n)×k個簇頭，均分到每個節(jié)點身上則每個節(jié)點成為簇頭的輪數(shù)m應(yīng)當為：

(16)

由式(15)，式(16)得到了m的預(yù)估值：

(17)

因為每次分簇的結(jié)果不同，每個節(jié)點的ECH和EnonCH值會和上次分簇結(jié)果中的數(shù)值有偏差。

如果根據(jù)某一次的分簇結(jié)果確定了m的值，并且在之后的過程中不再改變，那么將無法達到最優(yōu)的情況，節(jié)點無法合理利用。在每次分簇完之后，根據(jù)式(17)計算本次的穩(wěn)定運行輪數(shù)，只有這樣才能更好地利用和分配能量。

2.5 算法運行過程

(1) 設(shè)置S矩陣。計算任意兩點之間的S(i,j)。

(2) 計算參數(shù)z。根據(jù)式(12)-式(14)計算Kopt的范圍，調(diào)整z使簇數(shù)目在這個范圍之內(nèi)，在所有符合條件的z中選擇一個使網(wǎng)絡(luò)能耗最小的z。具體的數(shù)據(jù)見3.1節(jié)。

(3) 根據(jù)式(7)、式(8)計算S矩陣的對角線值。

(4) 根據(jù)式(5)、式(6)計算r矩陣和a矩陣。

(5) 迭代產(chǎn)生新的簇。根據(jù)式(3)、式(4)進行迭代直到數(shù)值不再發(fā)生改變，此時新一輪的簇已經(jīng)形成。

(6) 計算本次穩(wěn)定運行輪數(shù)m。根據(jù)當前網(wǎng)絡(luò)能量情況選舉出新的簇，根據(jù)式(17)得到簇的穩(wěn)定運行輪數(shù)m；根據(jù)文獻[1]的數(shù)據(jù)，HEED的穩(wěn)定運行輪數(shù)設(shè)為60輪。

(7) 穩(wěn)定運行。在AP算法運行m輪之后，重新進行步驟(4)-步驟(6)，直至計算中網(wǎng)絡(luò)死亡。

(8) 信息分發(fā)。通過平面路由，sink將每次分簇時步驟(5)中簇的信息和步驟(6)中m信息整合為一個數(shù)據(jù)包，通過平面路由的方式路由給每個節(jié)點。

3 仿真及分析

在MATLAB平臺上進行仿真，模擬一個300 m×300 m的一個區(qū)域，內(nèi)有1 000個節(jié)點隨機分布。假定基站在該區(qū)域的中心，在一輪的運行中，節(jié)點將數(shù)據(jù)包發(fā)送給簇頭，簇頭整合之后路由給基站。

將改進的AP算法與HEED算法進行對比，忽略無用偵聽、數(shù)據(jù)包丟失、形成簇頭時交換的數(shù)據(jù)包，具體參數(shù)如表1所示。

表1 仿真參數(shù)

3.1 調(diào)整參數(shù)z

由式(12)-式(14)得最優(yōu)簇數(shù)目是452時，簇頭數(shù)穩(wěn)定在60左右，且一輪的能量消耗基本相同，故本文取z=2.5來計算。

圖1 參數(shù)z的選擇

3.2 性能分析

性能分析基于六個標準：分簇的情況、存活節(jié)點數(shù)量、網(wǎng)絡(luò)剩余能量、每輪網(wǎng)絡(luò)的消耗能量、選舉過程能耗,網(wǎng)絡(luò)規(guī)模。

(1) 網(wǎng)絡(luò)成簇比較 取一次成簇結(jié)果進行比較，如圖2、圖3所示，可見EAPCP的簇頭數(shù)較少，且簇的內(nèi)聚度高，耦合度低，簇頭都在簇的中央位置。而HEED的分簇結(jié)果并不如EAPCP理想，簇間耦合度較高，且簇頭位置并不如前者選擇的恰當，說明單從分簇結(jié)果上EAPCP算法的分簇方法還是優(yōu)于HEED算法。

圖2 EAPCP某輪成簇圖

圖3 HEED某輪成簇圖

(2) 存活節(jié)點數(shù)量 在無線傳感器網(wǎng)絡(luò)中，第一個死亡節(jié)點出現(xiàn)的時間是衡量網(wǎng)絡(luò)壽命的一個重要參數(shù)，為了提高網(wǎng)絡(luò)性能，應(yīng)該盡量推遲第一個死亡節(jié)點出現(xiàn)的時間[10]，要使所有節(jié)點接近同時死亡。

如圖4所示，經(jīng)測試，在給定的條件下，EAPCP算法在3 000輪時候出現(xiàn)第一個死亡節(jié)點，此時網(wǎng)絡(luò)的能量消耗了72%，在4 600輪時全部節(jié)點能量耗盡。HEED算法800輪左右出現(xiàn)第一個死亡節(jié)點，1 500輪時一半的節(jié)點死亡，證明EAPCP算法可以有效地推遲節(jié)點的死亡時間出現(xiàn)。

圖4 兩種算法存活節(jié)點數(shù)量比較

(3) 每輪能量消耗 每輪能量消耗體現(xiàn)的是分簇結(jié)果的好壞，分簇合理時，每輪能耗自然會比較小，大型網(wǎng)絡(luò)的每輪能耗比小型網(wǎng)絡(luò)每輪能耗大。由于HEED算法選舉簇時需要消耗能量，此處計算的每輪能耗只考慮簇形成之后傳輸數(shù)據(jù)包的能耗，不考慮簇形成的能耗。

如圖5所示，在1 500輪之前，HEED的每輪能耗要比EAPCP大很多，說明EAPCP算法在分簇上更優(yōu)。在1 500輪之后因為HEED算法中節(jié)點死亡過半而能耗減少，EAPCP算法中節(jié)點尚未死亡，自然能耗要比HEED大。

圖5 兩種算法每輪能量消耗比較

(4) 剩余能量 網(wǎng)絡(luò)剩余能量體現(xiàn)的是網(wǎng)絡(luò)能量消耗的速度，不同于分析(3)，這條分析是把HEED中選舉簇頭的能量也考慮在內(nèi)。如圖6所示，因為分簇結(jié)果不佳，HEED前期網(wǎng)絡(luò)能耗增加，曲線斜率很大，1 500輪之后因為網(wǎng)絡(luò)規(guī)模減小，消耗能量少，斜率降低。EAPCP算法在前3 000輪每輪能耗基本相同，因此曲線趨于一條直線。3 000輪之后因為節(jié)點數(shù)目減小，每輪能耗降低，因此曲線的斜率逐漸下降。在3 800輪左右兩個網(wǎng)絡(luò)的剩余能量相同，因為EAPCP算法始終以穩(wěn)定的較低的能量運行，而HEED算法先是因分簇效果不佳而能耗高，后因節(jié)點數(shù)量少而較低，因而兩者會在此處能量相同。

圖6 兩種算法網(wǎng)絡(luò)剩余能量比較

(5) 選舉能量消耗比較 HEED利用節(jié)點間相互通信選舉生成每輪的簇，整個網(wǎng)絡(luò)選舉時消耗的能量是150 J，EAPAP算法第8步中消耗的能量是2.970 4 J，由此可見， 集中式的EAPCP算法要比分布式的HEED算法要好。

(6) 不同網(wǎng)絡(luò)規(guī)模比較 HEED算法隨著網(wǎng)絡(luò)規(guī)模的擴大，簇的個數(shù)無法控制，過多的簇導致信息采集效率不高，能量利用率低，網(wǎng)絡(luò)的死亡時間不斷推前。如圖7所示。

圖7 不同網(wǎng)絡(luò)規(guī)模下兩種算法的比較

4 結(jié) 語

本文提出了一種考慮能量的改進近鄰傳播聚類算法，并且給出了簇選定之后的穩(wěn)定運行輪數(shù)的計算方法。經(jīng)仿真檢測，該算法在以上兩個方面具有較好的性能。盡管在分簇時考慮了能量因素，但是最終的簇內(nèi)，簇頭的能量可能仍然偏低，如何在成簇之后綜合考慮簇頭位置和簇的能量，對簇頭節(jié)點進行調(diào)整，將是下一步的工作。

參 考 文 獻

[1] Lin Hai,Wang Lusheng,Kong Ruoshan.Energy efficient clustering protocol for large-scale sensor networks[J].IEEE Sensors Journal,2015,15(12):7150-7160.

[2] 鐘偉民,王月琴,梁毅,等.基于改進近鄰傳播聚類的異構(gòu)無線傳感器網(wǎng)絡(luò)分簇算法[J].江南大學學報:自然科學版,2012,11 (4):423-427.

[3] Heinzelman W B,Chandrakasan A P,Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications,2002,1(4):660-670.

[4] Younis O,Fahmy S.HEED:A Hybrid, energy-efficient,distributed clustering approach for Ad Hoc sensor networks[J].IEEE Transactions on Mobile Computing,2004,3(4):366-379.

[5] 尹安,汪秉文,戴志誠,等.無線傳感器網(wǎng)絡(luò)HEED分簇協(xié)議的研究與改進[J].小型微型計算機系統(tǒng),2010,31(10):2002-2006.

[6] 黃建清,王衛(wèi)星,胡月明,等.近鄰傳播聚類無線傳感器網(wǎng)絡(luò)分簇路由算法[J].計算機工程與設(shè)計,2014,35(2):406-410.

[7] Fery B J,Dueck D.Clustering by passing messages between data points[J].Science,2007,315(5814):972-976.

[8] 甘月松,陳秀宏,陳曉暉.一種AP算法的改進:M-AP聚類算法[J].計算機科學,2015,42(1):232-235.

[9] 朱蘭,張曉焱.基于近鄰傳播算法的K-means聚類優(yōu)化算法[J].信息技術(shù)與信息化,2015(2):138-142.

[10] 陳靜,張曉敏.無線傳感器網(wǎng)絡(luò)簇頭優(yōu)化分簇算法及其性能仿真[J].計算機應(yīng)用,2006,26(12):2787-2788.