楊彩霞，　高　麗，　路　暢（蘭州交通大學(xué)電子與信息工程學(xué)院，甘肅 蘭州 730070）

WSN中一種平衡節(jié)點(diǎn)能耗的分簇算法研究①

楊彩霞，高麗，路暢
（蘭州交通大學(xué)電子與信息工程學(xué)院，甘肅 蘭州 730070）

針對(duì)無(wú)線傳感器網(wǎng)絡(luò)（WSN）中能量消耗和節(jié)點(diǎn)死亡過(guò)高的問(wèn)題，在分析LEACH-C集中式分簇算法的基礎(chǔ)上，提出了一種基于量子行為粒子群優(yōu)化的WSN分簇算法.考慮到模擬退火算法在執(zhí)行算法過(guò)程中的復(fù)雜性，利用具有全局搜索能力和收斂速度快等特點(diǎn)的量子行為粒子群優(yōu)化算法，代替模擬退火算法對(duì)LEACH-C分簇算法中簇頭的選取進(jìn)行優(yōu)化.通過(guò)MATLAB仿真分析，改進(jìn)后的算法有效延長(zhǎng)了傳感器節(jié)點(diǎn)的生命，平衡了各節(jié)點(diǎn)的能量，提高了WSN的整體性能.

無(wú)線傳感器網(wǎng)絡(luò)；LEACH-C；分簇算法；量子行為粒子群優(yōu)化算法；節(jié)點(diǎn)死亡

0　引言

LEACH-C分簇算法［1］是 Heinzelman繼LEACH算法之后于2002年提出的集中式分簇路由算法.文獻(xiàn)［2］對(duì)LEACH-C算法改進(jìn)，提出了一種LEACH-m算法，針對(duì)過(guò)度依賴(lài)基站的問(wèn)題，引入副簇頭，并且降低簇頭的能耗，提高簇的生存能力.文獻(xiàn)［3］對(duì)LEACH-C算法中簇頭選取使用的模擬退火算法進(jìn)行了改進(jìn)，文獻(xiàn)［4］引用SUSAN算子對(duì)LEACH-C算法進(jìn)行了改進(jìn).文獻(xiàn)［5］利用固定和非固定相結(jié)合的方式，進(jìn)行分簇，提出了LEACH-C分簇算法.本文在LEACH-C的基礎(chǔ)上，提出了一種基于量子行為粒子群的LEACH-C分簇算法.

1　基于量子行為粒子群的LEACHC分簇算法

1.1LEACH-C分簇算法

在LEACH-C算法每個(gè)周期的開(kāi)始時(shí)間，基站用來(lái)接收所有節(jié)點(diǎn)的位置信息和剩余能量值，并且在收？到節(jié)點(diǎn)的信息后，計(jì)算所有節(jié)點(diǎn)的平均能量值，備選節(jié)點(diǎn)是能量大于平均能量值的節(jié)點(diǎn).然后使用模擬退火算法從備選節(jié)點(diǎn)中找出簇頭集，選出簇頭節(jié)點(diǎn)，最后把這個(gè)簇頭集合廣播給網(wǎng)絡(luò)中的所有節(jié)點(diǎn).如果一個(gè)節(jié)點(diǎn)收到的簇頭集合中包含有自己的信息，那么這個(gè)節(jié)點(diǎn)就作為其中的一個(gè)簇頭；否則，節(jié)點(diǎn)直接與相應(yīng)的簇頭建立聯(lián)系，并等候相應(yīng)的時(shí)分復(fù)用（TDMA）時(shí)隙的到來(lái)，最后向簇頭傳輸數(shù)據(jù)，在這個(gè)過(guò)程中，簇頭完成了TDMA中時(shí)隙的分配.

1.2量子行為粒子群優(yōu)化算法

量子行為粒子群優(yōu)化算法［6］（Quantum-behaved Particle Swarm Optimization，QPSO）是Sun J等人在粒子群優(yōu)化算法的基礎(chǔ)上，結(jié)合量子理論，提出的一種具有全局搜索特點(diǎn)的算法.相對(duì)于粒子群優(yōu)化算法（PSO），QPSO算法的進(jìn)化方程簡(jiǎn)單，不需要粒子的速度信息，并且收斂速度快，控制參數(shù)少，運(yùn)算比較方便.QPSO算法中，束縛狀態(tài)的粒子通過(guò)概率密度函數(shù)描述，能夠根據(jù)一定概率出現(xiàn)在整個(gè)可行搜索空間的任何一個(gè)位置，也可能出現(xiàn)在一個(gè)遠(yuǎn)離局部吸引子的位置上，因此可以有效增加群體多樣性，從而達(dá)到全局搜索.此外，QPSO算法的另一個(gè)亮點(diǎn)是引入平均最佳位置，粒子之間能夠在迭代進(jìn)化過(guò)程中互相等待，粒子之間的協(xié)作能力和全局搜索能力得到了提高.

在量子力學(xué)中，粒子的狀態(tài)用波函數(shù)φ（X，t）描述，它是坐標(biāo)和時(shí)間的復(fù)函數(shù).其中X（x，y，z）為粒子在三維空間中的位置向量.波函數(shù)的物理意義是：波函數(shù)模的平方是粒子在t時(shí)刻出現(xiàn)在空間某一點(diǎn)X的概率密度.即：

把概率密度函數(shù)歸一化可以得到：

引入平均最好位置mbest，定義為全部粒子個(gè)體最優(yōu)位置的平均，即

其中pbest為粒子個(gè)體最優(yōu).（3）式被叫做量子行為粒子群優(yōu)化算法.

1.3無(wú)線網(wǎng)絡(luò)能量消耗模型

對(duì)于改進(jìn)的分簇算法，給出在二維區(qū)域內(nèi)的的無(wú)線網(wǎng)絡(luò)模型：（1）基站位置固定；（2）每個(gè)傳感器節(jié)點(diǎn)初始能量相同或相近，并且都擁有唯一的ID標(biāo)志；（3）所有節(jié)點(diǎn)部署后不再移動(dòng)，節(jié)點(diǎn)之間等效通信；（4）所有節(jié)點(diǎn)都有定位能力.

能量模型采用和文獻(xiàn)［5］中相同的能量模型.若傳輸mbit的信息經(jīng)過(guò)距離d，此時(shí)發(fā)送端的能量消耗為：

如果數(shù)據(jù)的傳輸距離小于閾值d0時(shí)，功率放大消耗采用自由空間模型，如果數(shù)據(jù)的傳輸距離大于等于d0時(shí)，采用多路徑衰減模型.其中Eelec，表示發(fā)射電路所要消耗的能量；εfs，εmp分別表示自由空間模型和多路徑衰減模型中的信號(hào)衰減因子；d0表示發(fā)送方和接收方之間的通信距離.

1.4 基于量子行為粒子群優(yōu)化的LEACH-C分簇算法

量子行為粒子群優(yōu)化算法（QPSO）作為一種隨機(jī)優(yōu)化算法，在搜索能力，收斂速度以及解的精度等方面都體現(xiàn)了較好的性能.在LEACH-C算法中，簇頭相比簇內(nèi)節(jié)點(diǎn)來(lái)說(shuō)，本身消耗了更多能量；根據(jù)簇頭距基站的距離來(lái)說(shuō)，簇頭距基站的距離決定了通信能耗的大??；分析考慮到分簇的重要性，本論文擬結(jié)合QPSO算法，對(duì)簇頭選取進(jìn)行優(yōu)化.

傳統(tǒng)的LEACH-C分簇算法中，簇頭的選擇使用模擬退火算法.在模擬退火算法中，隨機(jī)產(chǎn)生一個(gè)初始解，并且算法執(zhí)行過(guò)程中的隨機(jī)擾動(dòng)都在一定程度上使得算法執(zhí)行的效率比較低，并且消耗了更多的時(shí)間，影響了網(wǎng)絡(luò)的整體性能.而且理想的退火算法需要溫度值非常緩慢地連續(xù)下降，這個(gè)過(guò)程一般不容易做到，這也是模擬退火算法在執(zhí)行算法時(shí)效率不高的原因之一.模擬退火算法在選舉簇頭的過(guò)程中，盡管減小了整個(gè)WSN網(wǎng)絡(luò)的傳輸代價(jià)，但是增加了節(jié)點(diǎn)的能量.因此，本文在原來(lái)算法的基礎(chǔ)上，針對(duì)簇頭的選取，根據(jù)QPSO算法的步驟，提出了一種改進(jìn)的算法.

在改進(jìn)的算法的簇的建立階段，首先基站獲得各節(jié)點(diǎn)的位置信息，然后根據(jù)QPSO算法選取簇頭，選取簇頭的主要步驟如下：

步驟1首先對(duì)節(jié)點(diǎn)進(jìn)行初始化.設(shè)傳感器節(jié)點(diǎn)均勻分布在一定的區(qū)域內(nèi)，對(duì)于在這個(gè)區(qū)域內(nèi)給定的粒子群，隨機(jī)產(chǎn)生服從均勻分布的粒子的向量，計(jì)算粒子群的個(gè)體最好位置，也就是計(jì)算該區(qū)域節(jié)點(diǎn)的個(gè)體最好位置.節(jié)點(diǎn)的的個(gè)體最好位置的計(jì)算依然采用Sun J等人提出的下列公式：

步驟2計(jì)算每個(gè)節(jié)點(diǎn)的適應(yīng)度函數(shù)值，并將適應(yīng)度函數(shù)最優(yōu)的節(jié)點(diǎn)設(shè)置為全局最優(yōu).

步驟3根據(jù)（3）式更新節(jié)點(diǎn)的平均最優(yōu)位置.

步驟4通過(guò)（1）式更新節(jié)點(diǎn)的位置.

步驟5將節(jié)點(diǎn)的當(dāng)前適應(yīng)度函數(shù)值和個(gè)體最優(yōu)pbest適應(yīng)度函數(shù)值進(jìn)行對(duì)比，若是前者優(yōu)于后者，則取代為個(gè)體最優(yōu)pbest.

步驟6和步驟5類(lèi)似，將節(jié)點(diǎn)的當(dāng)前適應(yīng)度函數(shù)值和全局最優(yōu)gbset適應(yīng)度函數(shù)值進(jìn)行比較，如果前者優(yōu)于后者，則取代為全局最優(yōu)gbest.全局最優(yōu)采用以下公式計(jì)算［8］：

步驟7如果沒(méi)有達(dá)到終止條件，重復(fù)步驟2 到6，直至滿足要求，全局最優(yōu)節(jié)點(diǎn)則為當(dāng)選簇頭，得到簇頭集合.

最后，基站把這個(gè)簇頭集合廣播給網(wǎng)絡(luò)中的所有節(jié)點(diǎn).節(jié)點(diǎn)進(jìn)行判斷，自己的信息是否與簇頭集合中包含的信息一致，完成數(shù)據(jù)的穩(wěn)定傳輸.

2　仿真分析

算法的仿真在MATLAB上進(jìn)行.為了驗(yàn)證算法的正確性，將改進(jìn)的算法和LEACH-C算法以及LEACH算法進(jìn)行比較.首先設(shè)定基站的坐標(biāo)為（50，50），位置是固定不變的，仿真場(chǎng)景設(shè)置為200m*200m的區(qū)域，并且在區(qū)域內(nèi)均勻分布100個(gè)傳感器節(jié)點(diǎn)，算法可執(zhí)行的最大時(shí)間輪數(shù)是5000輪.具體的仿真環(huán)境參數(shù)如表1所示.仿真實(shí)驗(yàn)通過(guò)對(duì)節(jié)點(diǎn)的存活個(gè)數(shù)，以及網(wǎng)絡(luò)能量消耗進(jìn)行評(píng)價(jià).

表1　仿真環(huán)境參數(shù)

圖1　節(jié)點(diǎn)存活個(gè)數(shù)對(duì)比圖

圖1是在傳感器節(jié)點(diǎn)存活個(gè)數(shù)和時(shí)間運(yùn)行輪數(shù)之間的關(guān)系圖.取時(shí)間運(yùn)行100輪的結(jié)果圖進(jìn)行分析，從圖中可以看出，LEACH算法和LEACH-C算法的第一個(gè)死亡節(jié)點(diǎn)在算法運(yùn)行開(kāi)始階段就出現(xiàn)了，改進(jìn)的算法的節(jié)點(diǎn)死亡時(shí)間比LEACH算法和LEACH-C算法提前了.從程序運(yùn)行結(jié)束來(lái)看，LEACH算法和LEACH-C算法在大約40輪和60輪之間節(jié)點(diǎn)全部死亡，而改進(jìn)的算法在大約68輪左右節(jié)點(diǎn)全部死亡.改進(jìn)后的算法相對(duì)于原算法，明顯提高了傳感器節(jié)點(diǎn)的存活時(shí)間.

圖2　網(wǎng)絡(luò)能量消耗對(duì)比圖

圖2是網(wǎng)絡(luò)能量消耗對(duì)比圖.橫坐標(biāo)設(shè)置為時(shí)間運(yùn)行輪數(shù)，縱坐標(biāo)為節(jié)點(diǎn)的能量消耗，單位為焦耳.從圖中可以看出，改進(jìn)后的算法相比LEACH算法和LEACH-C算法，能量消耗曲線呈平緩變化，有效延長(zhǎng)了傳感器網(wǎng)絡(luò)的壽命.

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

本文在分析了LEACH-C算法的基礎(chǔ)上，結(jié)合量子行為粒子群優(yōu)化算法對(duì)LEACH-C分簇算法中簇頭的選取進(jìn)行了優(yōu)化，并在MATLAB上進(jìn)行了仿真分析.從仿真結(jié)果可以看出，改進(jìn)后的算法有效延長(zhǎng)了節(jié)點(diǎn)的死亡時(shí)間，使傳感器節(jié)點(diǎn)的存活率更高，并且進(jìn)一步減少了算法中存在的能量損耗，提高了傳感器網(wǎng)絡(luò)的整體性能.但改進(jìn)的算法還是適用于規(guī)模小的網(wǎng)絡(luò)，具有一定的局限性，如果將算法應(yīng)用于實(shí)際環(huán)境中，考慮的因素會(huì)更多，這都是下一步要進(jìn)行的研究方向.

［1］Heinzelman W R，Chandrakasan A P，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks［C］.MITUSA：IEEE Transactions on Wireless Communications，2002：660-670.

［2］何傳波.無(wú)線傳感器網(wǎng)絡(luò)關(guān)鍵技術(shù)的研究［D］.武漢：武漢理工大學(xué)，2014.

［3］ 牛偉偉，高鐵杠.LEACH-C協(xié)議中模擬退火算法的改進(jìn)［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2011，32（6）：1869-1872.

［4］ 唐啟濤，劉蓉，張燕等.基于SUSAN算子的LEACH-C路由算法［J］.微計(jì)算機(jī)信息，2012，10：200.

［5］蔣華，劉偉強(qiáng)，王鑫.無(wú)線傳感器網(wǎng)絡(luò)中Leach-c路由協(xié)議的研究與改進(jìn)［J］.微電子學(xué)與計(jì)算機(jī)，2014，12（31）：43-47.

［6］孫俊，方偉，吳小俊，須文波.量子行為粒子群優(yōu)化：原理及其應(yīng)用［M］.北京：清華大學(xué)出版社，2011：1-50.

［7］盛歆漪，孫俊，周頔，等.自學(xué)習(xí)的量子粒子群優(yōu)化算法改進(jìn)［J］.計(jì)算機(jī)工程與應(yīng)用，2014，50（20）：24-29.

［8］Sun J，Wu X，Palade V，et al.Convergence analysis and improvements of quantum-behaved particle swarm optimization ［J］.Information Sciences，2012，193：81-103.

Research on the Clustering Algorithm of a Balanced Energy Consumption of Nodes for WSN

YANG Cai-xia， GAO Li， LU Chang
（School of Electronic&information Engineering，Lanzhou Jiaotong University，Lanzhou 730070，China）

Aiming at the problem that the energy consumption and node death are too high for wireless sensor networks（WSN），on the basis of analyzing the LEACH-C centralized clustering algorithm，the paper proposed a WSN clustering algorithm based on quantum-behaved particle swarm optimization.The complexity of simulated annealing algorithm in the implementation of the algorithm was taken into account.A quantum behaved particle swarm optimization algorithm with global searching ability and fast convergence rate，and replaced the simulated annealing algorithm was used to optimize the selection of cluster head in LEACH-C clustering algorithm.Through MATLAB simulation analysis，the improved algorithm can effectively prolong the life of sensor nodes，balance the energy of each node，and improve the overall performance of WSN.

WSN；LEACH-C；Clustering Algorithm；QPSO；Node death

TP393

A

1008-1402（2015）06-0925-04

2015-10-26

國(guó)家自然科學(xué)基金（61261029）.

楊彩霞（1989-），女，甘肅武威人，碩士研究生，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)，通訊作者：高麗（1974-），女，副教授，研究生導(dǎo)師，主要研究方向?yàn)橹悄苄畔⑻幚砝碚摷皯?yīng)用技術(shù).