無線傳感器網絡LEACH協議的二進制粒子群改進算法*

曹欲曉，徐金寶，徐夢溪，彭煥峰

（南京工程學院 計算機工程學院，江蘇 南京211167）

無線傳感器網絡LEACH協議的二進制粒子群改進算法*

曹欲曉，徐金寶，徐夢溪，彭煥峰

（南京工程學院 計算機工程學院，江蘇 南京211167）

針對無線傳感器網絡LEACH協議分簇時，能量較低的節點可能會成為簇頭，簇頭在簇中的位置未必最優的問題，提出了一種基于二進制粒子群的LEACH協議優化算法。首先在成簇過程中使簇的個數最優，然后應用二進制粒子群算法在每個簇中選擇最優簇頭。仿真證明，二進制粒子群優化的LEACH協議較原始LEACH協議有效降低了總的能量消耗，延長了網絡的生命期。

無線傳感器網絡；分簇；LEACH協議；二進制粒子群算法；粒子編碼

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 二進制粒子群優化算法

式中，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 分簇數目的控制

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

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

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

3.3.1 粒子的編碼

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

3.3.2 適應值函數的設計

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

3.3.3 BPSO-LEACH的步驟

“三師”工作由學校馬克思主義學院負責組織實施，為馬克思主義學院的“一號工程”“一把手工程”。實施之前必先制定具體工作方案，經全體教師討論，通過后再實施。每個月收集一次“三師”工作材料并及時通報，以督促進度，強化過程管理，防止弄虛作假?！叭龓煛惫ぷ髯?017年秋季展開后，經過一個學期的實踐，發現存在以下問題：

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

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

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

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

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

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

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

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

4 仿真實驗

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

4.1 仿真環境和算法參數

仿真參數如表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輪。

圖1 LEACH和BPSO-LEACH的生存時間

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

圖2 LEACH和BPSO-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 clustering mechanism of LEACH protocol for wireless sensor networks[C].2009 World Congress on Computer Science and Information Engineering(CSIE 2009)，Los Angeles，USA，March 2009

[3]HANDY M J，HAASE M，TIMMERMANN D.Low energy adaptive clustering hierachy with deterministic cluster-headselection[C].Proc.of the 4th IEEE Conf.on Mobile and Wireless Communication Networks.Stockolm：IEEE Communications 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.Piscataway，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 on System，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.

Improved binary particle swarm optimization algrothrim of LEACH protocol for wireless sensor network

Cao Yuxiao，Xu Jinbao，Xu Mengxi，Peng Huanfeng
(School of Computer Engineering,Nanjing Institute of Technology,Nanjing 211167，China)

This paper brings forth one kind of algrothrim based on binary particle swarm optimization(BPSO)which is used to sovle the problem described as follows.One problem is that node of wireless sensor network(WSN)with low energy probably could become cluster head.The other problem is that cluster head could have unreasonable position when WSN is divided into several clusters.Firstly，the number of clusters is managed to the best value.Secondly，BPSO is used to select the best node in each cluster as cluster head.Finally，it is proved by simulation experiment that LEACH protocol optimized by binary particle swarm can lower total energy consumption of WSN and prolong lifetime of WSN compared to LEACH protocol.

wireless sensor network；cluster；LEACH protocol；binary particle swarm optimization；particle code

TP393

A

0258-7998(2015)04-0091-03

10.16157/j.issn.0258-7998.2015.04.021

2014-11-02)

曹欲曉（1971-），男，碩士，講師，主要研究方向：智能算法、無線傳感器網絡。

徐金寶（1970-），男，碩士，副教授，主要研究方向：智能算法、數據挖掘。

徐夢溪（1983-），女，博士研究生，講師，主要研究方向：圖像處理、模式識別。

江蘇省高校自然科學研究面上項目（13KJB520009）