0 引言

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

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

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

1 LEACH協(xié)議的不足

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

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

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

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

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

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

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

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

3 BPSO-LEACH算法

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

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

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

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

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

　　(2)節(jié)點(diǎn)隨機(jī)部署在一個(gè)正方形區(qū)域中，節(jié)點(diǎn)初始能量相等,，部署后不再移動(dòng),。

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

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

　　3.2 分簇?cái)?shù)目的控制

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

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

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

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

　　3.3.1 粒子的編碼

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

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

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

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

　　3.3.3 BPSO-LEACH的步驟

　　對(duì)每一個(gè)簇分別應(yīng)用BPSO-LEACH算法選擇簇頭,。

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

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

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

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)

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

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

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

　　4.2 仿真結(jié)果

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

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

5 結(jié)束語

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

　　參考文獻(xiàn)

　　[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].電子學(xué)報(bào),，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.