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

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

0 引 言

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

網絡層的路由技術在無線傳感網中起著關鍵作用，從網絡拓撲結構的角度可將其分為平面路由和分簇路由兩種[2]。

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

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

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

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

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

1 AP算法

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

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

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

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

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

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

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

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

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

(1)

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

(2)

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

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

(3)

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

(4)

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

2 EAPCP算法

2.1 優(yōu)化簡介

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

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

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

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

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

(5)

(6)

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

2.2 基于能量的簇頭選擇

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

(7)

S(i,i)=pi

(8)

(9)

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

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

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

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

(10)

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

(11)

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

(12)

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

2Rc

(13)

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

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

(14)

結合式(13)、式(14)可以進一步縮小Kopt的范圍，在此范圍內進行進一步的篩選，即可得出網絡的最優(yōu)簇頭數。

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

無線傳感網中應當盡可能延長節(jié)點的使用時間，使節(jié)點盡可能在同一時間死亡，盡可能的將網絡消耗的能量平攤到每個節(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)

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

(16)

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

(17)

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

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

2.5 算法運行過程

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

(2) 計算參數z。根據式(12)-式(14)計算Kopt的范圍，調整z使簇數目在這個范圍之內，在所有符合條件的z中選擇一個使網絡能耗最小的z。具體的數據見3.1節(jié)。

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

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

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

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

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

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

3 仿真及分析

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

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

表1 仿真參數

3.1 調整參數z

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

圖1 參數z的選擇

3.2 性能分析

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

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

圖2 EAPCP某輪成簇圖

圖3 HEED某輪成簇圖

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

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

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

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

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

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

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

圖6 兩種算法網絡剩余能量比較

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

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

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

4 結 語

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

參 考 文 獻

[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] 鐘偉民,王月琴,梁毅,等.基于改進近鄰傳播聚類的異構無線傳感器網絡分簇算法[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] 尹安,汪秉文,戴志誠,等.無線傳感器網絡HEED分簇協(xié)議的研究與改進[J].小型微型計算機系統(tǒng),2010,31(10):2002-2006.

[6] 黃建清,王衛(wèi)星,胡月明,等.近鄰傳播聚類無線傳感器網絡分簇路由算法[J].計算機工程與設計,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].信息技術與信息化,2015(2):138-142.

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