0 引言

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

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

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

1 LEACH協議的不足

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

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

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

　　(3)每一個簇中，簇頭位置未必最優，使簇內節點能耗不均衡。

2 二進制粒子群優化算法

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

　　式中，w是慣性因子，c1是個體學習因子，c2是全局學習因子，r1和r2是區間[0，1]上的隨機數，PB是粒子的個體最優值，GB是粒子群最優值。

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

3 BPSO-LEACH算法

　　針對LEACH協議的不足，提出了以下改進方案。

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

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

　　3.1 網絡模型

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

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

　　(3)基站知道WSN內節點的地理位置和初始能量，基站能根據節點發送的數據量估算節點的剩余能量。

　　(4)成員節點可以根據到簇頭的距離，調整自己的發射功率。

　　3.2 分簇數目的控制

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

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

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

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

　　3.3.1 粒子的編碼

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

　　3.3.2 適應值函數的設計

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

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

　　3.3.3 BPSO-LEACH的步驟

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

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

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

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

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

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

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

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

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

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

4 仿真實驗

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

　　4.1 仿真環境和算法參數

　　仿真參數如表1所示。

　　4.2 仿真結果

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

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

5 結束語

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

　　參考文獻

　　[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協議的算法[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.