摘要：通過對已有的基于簇的自組織路由算法和簇頭選擇機制的分析比較，發(fā)現(xiàn)經(jīng)典LEACH算法在選取簇頭節(jié)點時具有不合理性，提出了一種基于PSO模型的簇頭選擇機制。以網(wǎng)絡(luò)總體能量消耗最小為原則，綜合考慮節(jié)點剩余能量和網(wǎng)絡(luò)當前平均能量，較好地平衡了無線傳感器網(wǎng)絡(luò)中的能量負載，延長了網(wǎng)絡(luò)的生命周期。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；微粒群算法；能量平衡；簇頭選擇

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2014）25-5905-04

Cluster Head Selection Mechanism for WSN Based on Energy Balance

ZHENG Lei

（Department of Computer Science， Nanjing University of Science & Technology Zijin College， Nanjing 210046， China）

Abstract： Through analysis and comparison of the existing self-organizing cluster-based routing algorithms and the cluster head selection mechanism， this paper finds that classical LEACH algorithm is unreasonable in the election of cluster head nodes， and proposes a PSO-based cluster head selection mechanism. Following the principle of the overall network energy minimization， and considering both of the residual energy of each node and the average energy of current network， the improved algorithm is better able to balance the energy burden in wireless sensor networks， and extend the network life cycle.

Key words： wireless sensor networks； PSO； energy balance； cluster head selection

1 概述

無線傳感器網(wǎng)絡(luò)是一種自組織網(wǎng)絡(luò)，網(wǎng)絡(luò)的形成與運行在很大程度上是由多個傳感器節(jié)點自主完成的，并不需要人工配置[1]。因此，在網(wǎng)絡(luò)建立的初始階段，需要采取一定的拓撲控制機制，自適應(yīng)地將一定數(shù)目的節(jié)點組成一個互聯(lián)網(wǎng)絡(luò)。

目前，無線傳感器網(wǎng)絡(luò)中拓撲控制可以分為兩類：功率控制和層次拓撲結(jié)構(gòu)控制[2]。功率控制機制調(diào)整網(wǎng)絡(luò)中每個節(jié)點的發(fā)射功率，在均衡節(jié)點直接鄰居數(shù)目（單跳可到達的鄰居數(shù)目）的同時，可降低節(jié)點通信干擾，提高網(wǎng)絡(luò)吞吐量。層次拓撲控制是利用分簇的思想，按照一定的規(guī)則使網(wǎng)絡(luò)中的部分節(jié)點處于激活狀態(tài)，并且成為簇頭節(jié)點，這些簇頭節(jié)點構(gòu)成一個聯(lián)通的網(wǎng)絡(luò)，對網(wǎng)絡(luò)內(nèi)的數(shù)據(jù)進行融合與傳輸；其他節(jié)點則處于休眠狀態(tài)以降低其能量消耗，并且定期地重新選擇簇頭節(jié)點以均衡網(wǎng)絡(luò)中節(jié)點的能量消耗。與傳統(tǒng)的無線自組織網(wǎng)絡(luò)相比，WSN部署的環(huán)境更為復(fù)雜，多采用電池供電，能量更為有限，節(jié)點數(shù)目眾多，節(jié)點部署更密集，網(wǎng)絡(luò)拓撲變化更為頻繁（由于節(jié)點的失效或者是新節(jié)點的加入）。因此，對于如何節(jié)省網(wǎng)絡(luò)能耗來說，采用層次型拓撲結(jié)構(gòu)顯然是一種較為高效的方法。基于簇的WSN作為一種層次型網(wǎng)絡(luò)拓撲結(jié)構(gòu)，被認為是一種可以組織大量傳感器節(jié)點的有效的結(jié)構(gòu)，在很多方面都表現(xiàn)出了其良好的性能，有利于分布式算法的實現(xiàn)，特別適合于部署較大規(guī)模的無線傳感器網(wǎng)絡(luò)[3]。由此可見，如何對無線傳感器網(wǎng)絡(luò)進行合理的分簇已成為當前亟待解決的一個重要問題。

2 基于LEACH協(xié)議的簇頭選擇機制

分簇作為層次型拓撲結(jié)構(gòu)的關(guān)鍵技術(shù)之一，其核心技術(shù)在于簇頭的選擇。目前，國內(nèi)外許多學(xué)者紛紛對其進行了相關(guān)的研究工作。LEACH（Low-Energy Adaptive Clustering Hierarchy）協(xié)議[4]是一種低功耗自適應(yīng)分簇協(xié)議，它以循環(huán)的方式選擇簇頭節(jié)點，將整個網(wǎng)絡(luò)的能量負載平均分配到每個傳感器節(jié)點中，能夠有效地降低網(wǎng)絡(luò)的能源消耗并提高網(wǎng)絡(luò)的整體生存時間。

2.1 經(jīng)典LEACH協(xié)議分析

LEACH協(xié)議是由MIT的Chandrakasan等人為無線傳感器網(wǎng)絡(luò)設(shè)計的一種周期性執(zhí)行的低功耗自適應(yīng)分簇拓撲算法，它的基本思想是以循環(huán)的方式隨機選擇簇頭節(jié)點，將整個網(wǎng)絡(luò)的能量負載平均分配到每個傳感器節(jié)點中，從而達到降低網(wǎng)絡(luò)能量消耗、提高網(wǎng)絡(luò)整體生存時間的目的。在LEACH算法中，相鄰的節(jié)點動態(tài)形成簇，并由簇中的某個節(jié)點擔(dān)任簇頭。所有非簇頭節(jié)點把數(shù)據(jù)發(fā)送到簇頭，簇頭對接收到的數(shù)據(jù)進行處理（數(shù)據(jù)融合）后把結(jié)果發(fā)送到匯聚節(jié)點（例如基站）。

LEACH在運行過程中不斷地循環(huán)執(zhí)行簇的重構(gòu)過程，每一次的執(zhí)行過程可以用“輪（round）”的概念來描述。每輪可以分為兩個階段：簇的建立階段（set-up）和傳輸數(shù)據(jù)的穩(wěn)態(tài)階段（stead-state）。在建立階段，節(jié)點被分為若干個簇，并且產(chǎn)生相應(yīng)的簇頭；在穩(wěn)態(tài)階段，簇內(nèi)的成員節(jié)點將收集到的數(shù)據(jù)發(fā)送給簇頭，這些數(shù)據(jù)在簇頭節(jié)點上通過處理后，發(fā)送到匯聚節(jié)點，如圖1所示。為了使時間冗余化最小，通常穩(wěn)態(tài)階段的持續(xù)時間要大于建立階段的持續(xù)時間。

圖1 LEACH的運行方式

LEACH算法希望在每輪執(zhí)行過程中形成[k]個簇，如何合理有效地選擇簇頭節(jié)點則成為LEACH算法的關(guān)鍵。一個節(jié)點能否成為簇頭是由網(wǎng)絡(luò)中所需要的簇頭節(jié)點的總數(shù)和每個節(jié)點已累計成為簇頭的次數(shù)來決定的。對于每一個傳感器節(jié)點，為其隨機選擇一個[0～1]之間的隨機值，如果這個選定的值小于某一個閾值[T（n）]，那么這個節(jié)點就成為簇頭節(jié)點。

在節(jié)點確定自己成為簇頭后，采用非持續(xù)CSMA的MAC協(xié)議廣播一個ADV消息。網(wǎng)絡(luò)中的其他節(jié)點在接收到周圍簇頭節(jié)點的ADV消息后，根據(jù)接收信號強度決定從屬的簇，并通知相應(yīng)的簇頭節(jié)點，完成簇的建立。最后，簇頭節(jié)點采用TDMA方法為簇中的每個節(jié)點分配向其傳送數(shù)據(jù)的時間片。

穩(wěn)態(tài)階段被分成時間長度相等的時隙，簇內(nèi)成員節(jié)點只能在特定的時隙內(nèi)向簇頭節(jié)點發(fā)送數(shù)據(jù)。簇頭節(jié)點在收到簇內(nèi)成員節(jié)點所采集的數(shù)據(jù)后，對其進行數(shù)據(jù)融合，去除冗余數(shù)據(jù)信息，提取關(guān)鍵信息，然后將結(jié)果發(fā)送給匯聚節(jié)點[5]。穩(wěn)態(tài)階段持續(xù)一段時間后，網(wǎng)絡(luò)重新進入簇的建立階段，進行下一輪的簇的重構(gòu)過程，不斷循環(huán)。

2.2 LEACH算法的優(yōu)化

從上一節(jié)的分析中可以看出，在簇的建立階段，LEACH算法在選擇簇頭節(jié)點的時候具有很大的隨機性，很容易出現(xiàn)部分節(jié)點剩余能量較低但仍被選為簇頭節(jié)點的情況，這樣會導(dǎo)致部分節(jié)點因能量被提前耗盡而過早“死亡”，不利于延長整個網(wǎng)絡(luò)的生命周期。而且，LEACH協(xié)議是通過采用數(shù)據(jù)壓縮的方法來減少傳輸?shù)交竟?jié)點的數(shù)據(jù)量，數(shù)據(jù)壓縮的過程使得節(jié)點必須額外消耗較多的能量。另外，LEACH協(xié)議是通過隨機方式選擇簇頭節(jié)點的，在選擇過程中沒有考慮到節(jié)點自身的剩余能量，一旦剩余能量較少的節(jié)點成為簇頭，可能會導(dǎo)致這些節(jié)點因能量耗盡而過早死亡，降低整個網(wǎng)絡(luò)的壽命。同時，LEACH協(xié)議在選舉簇頭時不能保證簇頭節(jié)點均勻分布在監(jiān)測區(qū)域內(nèi)，可能會造成部分區(qū)域簇頭分布較密集，部分區(qū)域簇頭稀疏甚至沒有產(chǎn)生任何簇頭，從而造成網(wǎng)絡(luò)的不完全連通。針對LEACH協(xié)議的不足之處，該文提出了一種基于能量均衡的簇頭選擇機制，將微粒群算法（PSO）引入到無線傳感器網(wǎng)絡(luò)簇頭選舉的優(yōu)化過程中，綜合考慮每個節(jié)點的剩余能量和當前網(wǎng)絡(luò)的平均能量，并且融入了簇頭最優(yōu)個數(shù)的解決方案，用以優(yōu)化網(wǎng)絡(luò)的拓撲結(jié)構(gòu)。通過對LEACH算法進行改進，較好地平衡了網(wǎng)絡(luò)之中的能量消耗，有效地避免部分節(jié)點的過早死亡，有效地延長了整個網(wǎng)絡(luò)的生命周期。

3 基于能量均衡的簇頭選擇機制

針對經(jīng)典LEACH協(xié)議在選舉簇頭節(jié)點時的不足，該文提出了一種新的簇頭選擇機制，在經(jīng)典LEACH協(xié)議的基礎(chǔ)上，運用PSO算法在并行尋優(yōu)方面的優(yōu)勢，避免使能量低的節(jié)點成為簇頭，盡量讓剩余能量高于當前網(wǎng)絡(luò)平均能量的節(jié)點優(yōu)先成為簇頭節(jié)點。

3.1 基于PSO的簇頭選擇機制

無線傳感器網(wǎng)絡(luò)的生命周期是衡量網(wǎng)絡(luò)拓撲結(jié)構(gòu)的一個重要指標[6]。通常網(wǎng)絡(luò)的生命周期取決于網(wǎng)絡(luò)中第一個節(jié)點失效（或者電源耗盡）的時間，因此應(yīng)產(chǎn)生一個合理的簇頭選擇機制，將簇頭的能量負載平均分布到網(wǎng)絡(luò)中的所有節(jié)點上，避免造成部分節(jié)點因成為簇頭而過早耗盡能量的情況，從而達到延長網(wǎng)絡(luò)生命周期的目的。

本文在簇頭選擇時所采用的思想可描述為：首先，將簇內(nèi)每個節(jié)點的當前剩余能量與網(wǎng)絡(luò)平均能量進行比較，如若節(jié)點的當前剩余能量大于網(wǎng)絡(luò)平均能量，則將該節(jié)點放入候選節(jié)點集中，使之成為簇頭候選節(jié)點。然后，在候選節(jié)點集中，運用PSO算法來選取最優(yōu)簇頭，使當前剩余能量最多的節(jié)點成為最優(yōu)簇頭。

本文依舊采用LEACH算法中的能量消耗模型[7]。假設(shè)無線傳感器網(wǎng)絡(luò)中有[N]個傳感器節(jié)點，每個節(jié)點的初始能量為[Einitial]；節(jié)點[i]的當前剩余能量為[Eicurrent]。通過引入判別函數(shù)[F（i）]來判斷節(jié)點[i]能否成為簇頭候選節(jié)點：如果[F（i）≥0]，則節(jié)點[i]能夠成為簇頭候選節(jié)點；反之，則不能。

分析此式可以看出，在網(wǎng)絡(luò)正常運行期間，節(jié)點總是需要消耗能量的。因此，在任何時刻節(jié)點的剩余能量總是小于其初始能量的，該判別函數(shù)在實際應(yīng)用時嚴重缺乏可操作性。針對這一現(xiàn)象，該文對判別函數(shù)[F（i）]進行了改進，綜合考慮節(jié)點剩余能量和網(wǎng)絡(luò)當前平均能量這兩個因素。

其中：[Eavg]表示網(wǎng)絡(luò)當前平均能量。當[F（i）≥0]時，節(jié)點[i]的剩余能量高于網(wǎng)絡(luò)平均能量，節(jié)點[i]成為簇頭候選節(jié)點；反之，節(jié)點[i]的剩余能量低于網(wǎng)絡(luò)平均能量，為節(jié)省能耗，節(jié)點[i]只能作為簇內(nèi)成員節(jié)點。這樣一來，既保證在每一輪中可以優(yōu)先選擇剩余能量較多的節(jié)點成為簇頭節(jié)點，又降低了剩余能量較少的節(jié)點成為簇頭節(jié)點的可能性。

當簇頭候選集產(chǎn)生之后，該文采用PSO算法來選擇最優(yōu)簇頭節(jié)點。PSO算法是一種群體智能算法，來源于對一個簡化社會模型的模擬，在解決最優(yōu)化問題時具有顯著的優(yōu)勢。種群中每一個微粒代表問題的一個可行解，每個微粒根據(jù)其自身所經(jīng)歷的最好位置和全局的最優(yōu)位置，來動態(tài)調(diào)整其飛行速度和方向，直至找到最優(yōu)解或者達到最大迭代次數(shù)為止[8]。

在選擇最優(yōu)簇頭節(jié)點的過程中，將簇頭候選集中的節(jié)點作為種群中的初始微粒，通過適應(yīng)值函數(shù)和迭代搜索，找到種群的全局最優(yōu)解，該最優(yōu)解所對應(yīng)的微粒就是該輪中的最優(yōu)簇頭節(jié)點。

此外，在網(wǎng)絡(luò)的分簇過程中，簇頭的數(shù)量也是影響網(wǎng)絡(luò)生命周期的一個重要因素?？紤]到與距離較遠的簇頭節(jié)點通信時成本較高，所以沒有簇頭的操作會降低能量效率。無論增加的簇頭會為數(shù)據(jù)融合帶來多少額外的工作，增加幾個簇頭都會迅速地提高網(wǎng)絡(luò)整體的能量效率。但是當再進一步增加簇頭時，分簇的優(yōu)點會慢慢消失。在最極端的情況下，每個節(jié)點本身就是簇頭，沒有任何融合的優(yōu)勢。該文采用文獻[5]中的方法來確定最優(yōu)簇頭的個數(shù)。

[K=SN×εamp2π（N×Estat+εamp×d2adv）] （5）

其中：[S]是無線傳感器網(wǎng)絡(luò)監(jiān)測區(qū)域的面積，[N]是傳感器節(jié)點的數(shù)量，[εamp]是信號放大器的放大倍數(shù)，[Estat]是節(jié)點每傳輸1[bit]數(shù)據(jù)所消耗的能量，[dadv]是簇頭節(jié)點的最遠覆蓋距離。

3.2 簇頭選擇機制的實現(xiàn)過程

基于PSO算法的簇頭選擇機制的具體實現(xiàn)步驟如下：

1） 在簇的建立階段，根據(jù)最優(yōu)簇頭個數(shù)公式（5） ，得到分簇的數(shù)目[K]。

2） 計算每個節(jié)點的當前剩余能量和網(wǎng)絡(luò)的平均能量。

3） 分別將每個節(jié)點的當前剩余能量與網(wǎng)絡(luò)平均能量進行比較，如果節(jié)點剩余能量高于網(wǎng)絡(luò)平均能量，則該節(jié)點有資格成為簇頭候選節(jié)點；否則，該節(jié)點只能等待簇頭廣播信息。

4） 在簇頭候選集中，通過PSO算法優(yōu)化簇頭選擇，使剩余能量最多的節(jié)點成為最優(yōu)簇頭，其余節(jié)點變?yōu)槌蓡T節(jié)點等待簇頭發(fā)送廣播信息。此時，簇頭選擇階段結(jié)束。

5） 簇頭節(jié)點以一定的功率發(fā)送簇頭廣播信息，并等待成員節(jié)點的加入。

6） 成員節(jié)點根據(jù)接收到的ADV消息的信號強弱來選擇一個信號強的簇頭節(jié)點，向其發(fā)送一個請求加入的消息，并等待簇頭節(jié)點分配TDMA時隙，避免成員節(jié)點與簇頭節(jié)點通信時產(chǎn)生沖突。

7） 簇建立好后，無線傳感器網(wǎng)絡(luò)進入穩(wěn)態(tài)運行階段。成員節(jié)點按照給定的規(guī)則在自己的TDMA時隙內(nèi)向簇頭節(jié)點發(fā)送收集到的信息，簇頭節(jié)點對這些信息進行數(shù)據(jù)融合，通過簇間通信傳送至匯聚節(jié)點（或者基站）。當簇頭節(jié)點的剩余能量低于閾值時，本輪結(jié)束，開始下一輪的分簇過程。

具體算法流程如圖2所示。

4 結(jié)束語

本文首先介紹了拓撲控制的相關(guān)知識，指出合理的分簇對于提高WSN生命周期的重要性。然后對經(jīng)典LEACH分簇協(xié)議進行了具體的分析，并針對LEACH協(xié)議在選舉簇頭節(jié)點時存在的不足，對LEACH算法進行優(yōu)化，提出了基于PSO的簇頭選擇機制。在優(yōu)化的過程中，以網(wǎng)絡(luò)總體能量消耗最小為原則，綜合考慮節(jié)點剩余能量和網(wǎng)絡(luò)當前平均能量，更好地平衡了無線傳感器網(wǎng)絡(luò)中的能量負載，優(yōu)化了網(wǎng)絡(luò)拓撲結(jié)構(gòu)。

參考文獻：

[1] 王舒，閻毓杰.無線傳感器網(wǎng)絡(luò)的理論及應(yīng)用[M].北京：北京航空航天大學(xué)出版社，2007：12-13.

[2] Bao L，Garcia-Luna-Aceves J J.Topology Management in Ad Hoc Network[C].In Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking & Computing，2003：129-140.

[3] 汪學(xué)清，楊永田.一種基于虛擬菱形網(wǎng)格的傳感器節(jié)點布置算法[J].計算機應(yīng)用，2006，26（7）：1554-1556.

[4] Heinzelman W.Chandrakasan A，Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Transactions on Wireless Communications，2002，1（4）：660-670.

[5] 周利民，楊科華，周攀.基于魚群算法的無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化策略[J].計算機應(yīng)用研究，2010，27（6）：2276-2280.

[6] Efthymiou C，Nikoletseas S，Rolim J.Energy balanced data propagation in wireless sensor networks[C].Proceedings of 18th International Parallel and Distributed Processing Symposium，CA：IEEE Computer Society，2004：225-232.

[7] Li Fangmin，Xv Wenjun，Liu Xinhua，et al.A real-time energy-aware cluster-based routing protocol for wirelsee sensor and actor networks[J].Journal of Computer Research and Development，2008，45（1）：26-33.

[8] 曾建潮，介婧，崔志華.微粒群算法[M].北京：科學(xué)出版社，2004：5-8.