0 引言

　　LEACH協(xié)議[1]是無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network,WSN）經(jīng)典的分層路由協(xié)議，能有效地延長網(wǎng)絡(luò)生存時間。但是由于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)絡(luò)中的每一個簇應(yī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)化算法

　　設(shè)粒子在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)絡(luò)能耗最小的簇數(shù)，在分簇過程中控制簇的數(shù)量，使簇的個數(shù)最優(yōu)。

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

　　3.1 網(wǎng)絡(luò)模型

　　(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ù)目的控制

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

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

　　3.3 應(yīng)用BPSO算法確定最終簇頭

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

　　3.3.1 粒子的編碼

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

　　3.3.2 適應(yīng)值函數(shù)的設(shè)計

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

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

　　3.3.3 BPSO-LEACH的步驟

　　對每一個簇分別應(yīng)用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)計算粒子的適應(yīng)值。對于每一個粒子，如果X=1，表示第k次迭代時第i個粒子表示的分簇方案中第j個節(jié)點作為簇頭，其他節(jié)點作為成員，利用式（4）計算粒子的適應(yīng)值。

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

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

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

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

4 仿真實驗

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

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

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

　　4.2 仿真結(jié)果

　　圖1是LEACH和BPSO-LEACH的網(wǎng)絡(luò)生存時間仿真結(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)絡(luò)中所有節(jié)點的剩余能量之和。由圖2可以看出，在網(wǎng)絡(luò)分簇的開始150輪，兩種算法的能量消耗相差不大，隨著分簇輪數(shù)的增加，BPSO-LEACH的能量消耗要明顯小于LEACH。

5 結(jié)束語

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

　　參考文獻

　　[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.