0 引言

　　LEACH協(xié)議[1]是無線傳感器網(wǎng)絡（Wireless Sensor Network,WSN）經(jīng)典的分層路由協(xié)議,，能有效地延長網(wǎng)絡生存時間,。但是由于LEACH協(xié)議采用由節(jié)點生成隨機數(shù)的方法選擇簇頭并成簇，使得每次成簇的數(shù)目相差較大,，簇頭在簇中的位置未必最優(yōu),，且對簇頭的剩余能量也未加考慮，因此LEACH協(xié)議還有可改進之處,。

　　文獻[2]在簇頭選舉時考慮了節(jié)點的能量因素，選擇剩余能量大的節(jié)點作簇頭,，但未對簇的數(shù)目和簇頭位置進行優(yōu)化,。文獻[3]在選擇簇頭時，考慮了候選簇頭及簇內(nèi)節(jié)點的能量和距離因素,，但對簇的數(shù)目和簇的大小未進行控制,。文獻[4]引入了簇門限數(shù)和合并極小簇的方法，對簇的規(guī)模和個數(shù)進行了優(yōu)化,，但對簇頭在簇中的位置未作考慮,。

　　針對LEACH協(xié)議的不足，本文基于LEACH提出了一種新的BPSO-LEACH（Binary Particle Swarm Optimization LEACH）算法。BPSO-LEACH首先在分簇過程中控制簇的數(shù)量,，使簇的個數(shù)最優(yōu)以減小全網(wǎng)的能量消耗,，然后對網(wǎng)絡中的每一個簇應用二進制粒子群算法重新選擇簇頭，使簇內(nèi)能量消耗之和最小且節(jié)點間能耗均衡,。

1 LEACH協(xié)議的不足

　　由文獻[1-4]可知,，LEACH協(xié)議存在以下不足：

　　(1)每一輪分簇時，簇的數(shù)目可能差別較大,。如果簇數(shù)太多,，會有較多的簇頭向基站傳輸數(shù)據(jù)，使全網(wǎng)的能耗過大,；如果簇數(shù)太少,，節(jié)點可能會離簇頭較遠，向簇頭傳輸數(shù)據(jù)時會因消耗過多能量而導致較早死亡,。

　　(2)選舉簇頭時,，由隨機數(shù)和閾值來決定一個節(jié)點是否成為簇頭，沒有考慮節(jié)點的剩余能量,，使剩余能量較小的節(jié)點有可能成為簇頭,，導致簇頭過早死亡。

　　(3)每一個簇中,，簇頭位置未必最優(yōu),，使簇內(nèi)節(jié)點能耗不均衡。

2 二進制粒子群優(yōu)化算法

　　設粒子在D維空間中尋優(yōu),，每個粒子有一個位置可用式（1）和式（2）表示：

　　式中,，w是慣性因子，c1是個體學習因子,，c2是全局學習因子,，r1和r2是區(qū)間[0，1]上的隨機數(shù),，PB是粒子的個體最優(yōu)值,，GB是粒子群最優(yōu)值。

　　二進制粒子群優(yōu)化算法BPSO[6](Binary Particle Swarm Optimization)的位置矢量是二進制空間,，粒子在每一維上的取值只能是0或1,，速度矢量仍然位于實數(shù)空間。BPSO速度矢量的更新公式仍用式（2）,，位置矢量改用式（3）描述：

3 BPSO-LEACH算法

　　針對LEACH協(xié)議的不足,，提出了以下改進方案。

　　(1)針對簇的個數(shù)不確定,，根據(jù)WSN的能量消耗模型,，計算出使整個網(wǎng)絡能耗最小的簇數(shù),，在分簇過程中控制簇的數(shù)量，使簇的個數(shù)最優(yōu),。

　　(2)針對能量較小的節(jié)點可能成為簇頭和簇頭位置不是最優(yōu),，在每個簇中遵循簇頭節(jié)點能量較大、簇內(nèi)成員節(jié)點能耗均衡的思想,，應用BPSO算法重新選擇簇頭,。

　　3.1 網(wǎng)絡模型

　　(1)基站位于WSN外部，能量不受限制,，計算能力不受限制,。

　　(2)節(jié)點隨機部署在一個正方形區(qū)域中，節(jié)點初始能量相等,，部署后不再移動,。

　　(3)基站知道WSN內(nèi)節(jié)點的地理位置和初始能量，基站能根據(jù)節(jié)點發(fā)送的數(shù)據(jù)量估算節(jié)點的剩余能量,。

　　(4)成員節(jié)點可以根據(jù)到簇頭的距離,，調(diào)整自己的發(fā)射功率。

　　3.2 分簇數(shù)目的控制

　　設WSN中有N個節(jié)點,，隨機分布在L×L的區(qū)域,，共分成K個簇，dHB是簇頭到基站的歐氏距離,，?著fs和?著mp是節(jié)點的無線通信能量消耗系數(shù),。由文獻[7]可知：當網(wǎng)絡分成K個簇時，總的能量消耗最小,，此時的K稱為KBest,。

　　在簇的形成階段，每一個成為簇頭的節(jié)點首先把自己成為簇頭的信息報告給基站而不是向全網(wǎng)廣播,，此時的簇頭稱為候選簇頭,。如果向基站報告的候選簇頭的個數(shù)超過KBest，則基站從中隨機挑選KBest個作為候選簇頭,，其余的作為普通節(jié)點,；如果候選簇頭個數(shù)不足KBest個，則基站線性增大閾值T(n)并告知全網(wǎng)節(jié)點,，重新啟動簇頭選舉,，直到產(chǎn)生KBest個候選簇頭。候選簇頭確定之后,，按照LEACH中的成簇方法把整個網(wǎng)絡分成KBest個簇。

　　3.3 應用BPSO算法確定最終簇頭

　　從所有節(jié)點中選出KBest個候選簇頭并成簇后,，候選簇頭在簇中的位置很可能不是最優(yōu),。下面應用BPSO-LEACH算法選擇每個簇最優(yōu)的簇頭,。

　　3.3.1 粒子的編碼

　　設簇中有M個節(jié)點，則粒子的搜索空間就是M維二進制空間,。粒子i在進化的第k代的位置矢量,，粒子每一維矢量的取值只能是0或1。若X=1,，則表示第k次迭代時第k個粒子對應的分簇方案中把第j個節(jié)點作為簇頭,；若X=0，則第j個節(jié)點作為簇中的成員,。

　　3.3.2 適應值函數(shù)的設計

　　應用BPSO-LEACH算法選擇簇頭時,，優(yōu)化目標是使簇中所有節(jié)點的能耗之和最小且均衡。定義適應值函數(shù)如式（4）所示：

　　式中：d是簇中第i個節(jié)點到候選簇頭距離的平方,，var(diH)是簇中第i個節(jié)點到候選簇頭距離的方差,， eH是候選簇頭的能量，?琢>0,，?茁>0,，?酌>0，?琢+?茁+?酌=1,。在WSN生命期的不同輪中,，可以使簇頭的選舉傾向于能耗最小或是能耗最為均衡。

　　3.3.3 BPSO-LEACH的步驟

　　對每一個簇分別應用BPSO-LEACH算法選擇簇頭,。

　　(1)初始化一個規(guī)模為Q的粒子群,，每個粒子的維數(shù)是M（簇中節(jié)點個數(shù)），確定參數(shù)c1,、c2,、w和迭代次數(shù)k。

　　(2)初始化粒子的位置和速度,。粒子的位置矢量由式（5）給出：

　　r(0,，1)是區(qū)間[0，1]上的隨機數(shù),，R是一個常數(shù),。粒子的速度矢量由式（6）給出：

　　其中：VMin和VMax分別是粒子速度的最小值和最大值。

　　(3)計算粒子的適應值,。對于每一個粒子,，如果X=1，表示第k次迭代時第i個粒子表示的分簇方案中第j個節(jié)點作為簇頭,，其他節(jié)點作為成員,，利用式（4）計算粒子的適應值。

　　(4)計算每個粒子的個體最優(yōu)值和整個種群的全局最優(yōu)值,。迭代過程中,，使適應值函數(shù)取得最小值的粒子的位置矢量是個體最優(yōu)值,，在所有的個體最優(yōu)值中求出全局最優(yōu)值。

　　(5)根據(jù)式(2)和式(3)更新粒子的速度和位置矢量,。

　　(6)重復步驟(3)～(5),，直到完成規(guī)定的迭代次數(shù)。

　　(7)對于最終全局最優(yōu)值所對應的粒子,，因其對應了若干種簇頭選擇方案（簇頭選擇方案總數(shù)等于值是1的矢量的維數(shù)之和）,。對每一個候選簇頭，應用式(4)求其適應值,，取適應值最小的候選簇頭作為最后的正式簇頭,。

4 仿真實驗

　　應用MATLAB軟件對LEACH和BPSO-LEACH進行仿真，各運行100次,，取平均值進行比較,。評價指標是：（1）網(wǎng)絡生存時間，從仿真開始到網(wǎng)絡中70%的節(jié)點還存活所經(jīng)歷的輪數(shù),。（2）網(wǎng)絡生存時間內(nèi)節(jié)點的總能量消耗,。

　　4.1 仿真環(huán)境和算法參數(shù)

　　仿真參數(shù)如表1所示。

　　4.2 仿真結(jié)果

　　圖1是LEACH和BPSO-LEACH的網(wǎng)絡生存時間仿真結(jié)果,。圖中的橫坐標表示分簇輪數(shù),，縱坐標表示存活節(jié)點數(shù)。從圖1可以看出,，LEACH在620輪左右即出現(xiàn)第一個死亡節(jié)點,，而BPSO-LEACH在870輪左右出現(xiàn)第一個死亡節(jié)點。LEACH的存活節(jié)點還剩下70%時的輪數(shù)約為1 300輪,，BPSO-LEACH約為1 930輪,。LEACH分簇的節(jié)點在大約2 900輪后全部死亡，而BPSO-LEACH約為4 500輪,。

　　圖2是LEACH和BPSO-LEACH總的能量消耗仿真結(jié)果,。圖中的橫坐標表示分簇輪數(shù)，縱坐標表示網(wǎng)絡中所有節(jié)點的剩余能量之和,。由圖2可以看出,，在網(wǎng)絡分簇的開始150輪，兩種算法的能量消耗相差不大,，隨著分簇輪數(shù)的增加,，BPSO-LEACH的能量消耗要明顯小于LEACH。

5 結(jié)束語

　　本文首先在分簇過程中按最優(yōu)簇數(shù)控制了簇的數(shù)量,。初步分簇過程按照LEACH協(xié)議的簇頭選舉方法選出候選簇頭,，成簇后再應用二進制粒子群方法重新選擇最終簇頭。粒子的編碼采用了簇頭為1,、節(jié)點為0的二進制編碼方案,，適應值函數(shù)的設計目標是簇中節(jié)點的能耗之和最小且能耗均衡,。迭代結(jié)束后取最優(yōu)粒子中適應值最小的候選簇頭作為最終的簇頭,。仿真結(jié)果表明,，BPSO-LEACH比LEACH可以節(jié)約30%的能量，延長約50%的網(wǎng)絡生存期,。

　　參考文獻

　　[1] HEINZELMAN W,，CHANDRAKASAN A，BALAKRISHAM H.Energy-efficient communication protocol for wireless microsensor networks[C].Proceedings of the 33rd Annual Hawaii International Conf.on System Sciences.[S.l.]：IEEE Computer Society,，2000：3005-3014.

　　[2] Chen Xuhui,，Yang Zhiming，Cheng Huiyan.Unequal cluste-ring mechanism of LEACH protocol for wireless sensor networks[C].2009 World Congress on Computer Science andInformation Engineering(CSIE 2009),，Los Angeles,，USA，March 2009

　　[3] HANDY M J,，HAASE M,，TIMMERMANN D.Low energy adaptive clustering hierachy with deterministic cluster-head selection[C].Proc.of the 4th IEEE Conf.on Mobile and Wireless Communication Networks.Stockolm：IEEE Communi-cations Society，2002：368-372.

　　[4] 呂濤,，朱清新,，張路橋.一種基于LEACH協(xié)議的算法[J].電子學報，2011,，39（6）：1405-1409.

　　[5] KENNEDY J,，EBERHART R C.Particle swarm optimization[C].IEEE International Conference on Neural Networks，IV.Pis-cataway,，NJ,，USA：IEEE Service Center，1995：1942-1948.

　　[6] KENNEDY J,，EBERHART R C.A discrete binary version of the particle swarm algorithm[C].The 1997 Conference onSystem,，Cybernetics and Informatics.Piscataway，NJ USA：IEEE Press,，1997：4104-4109.

　　[7] HESHAM A,，Yang S H.Dynamic cluster head for lifetime efficiency in WSN[J].International Journal of Automation and Computing，2009,，6(1)：48-54.