0 引言

　　LEACH協(xié)議[1]是無(wú)線傳感器網(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]引入了簇門(mén)限數(shù)和合并極小簇的方法，對(duì)簇的規(guī)模和個(gè)數(shù)進(jìn)行了優(yōu)化，但對(duì)簇頭在簇中的位置未作考慮。

　　針對(duì)LEACH協(xié)議的不足，本文基于LEACH提出了一種新的BPSO-LEACH（Binary Particle Swarm Optimization LEACH）算法。BPSO-LEACH首先在分簇過(guò)程中控制簇的數(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)的能耗過(guò)大；如果簇?cái)?shù)太少，節(jié)點(diǎn)可能會(huì)離簇頭較遠(yuǎn)，向簇頭傳輸數(shù)據(jù)時(shí)會(huì)因消耗過(guò)多能量而導(dǎo)致較早死亡。

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

　　(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ù)，在分簇過(guò)程中控制簇的數(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)的無(wú)線通信能量消耗系數(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ù)超過(guò)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)值。迭代過(guò)程中，使適應(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í)間，從仿真開(kāi)始到網(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)，而B(niǎo)PSO-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輪后全部死亡，而B(niǎo)PSO-LEACH約為4 500輪。

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

5 結(jié)束語(yǔ)

　　本文首先在分簇過(guò)程中按最優(yōu)簇?cái)?shù)控制了簇的數(shù)量。初步分簇過(guò)程按照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.