基于混沌粒子群優化的無線傳感器網絡分簇協議*

劉志坤，劉 忠，李朝旭

(海軍工程大學電子工程學院，武漢 430033)

無線傳感器網絡(WSN)作為一種新型的信息采集、傳輸、處理系統，在軍事和民用領域得到了廣泛的應用［1－2］。WSN的一個顯著特征是節點能量有限，通常難以進行能量補充。因此，如何節約節點的能量消耗，延長網絡的存活周期，就成為WSN領域研究的一個熱點問題。分簇路由協議是解決該問題的一種有效方法。它將WSN劃分為若干個簇組織，從而可以有效地管理網絡數據，提高網絡效能，延長網絡存活時間。

LEACH(Low-Energy Adaptive Clustering Hierarchy)是最早提出的分簇協議［3］，它以等概率對簇首進行周期隨機選擇，將整個網絡的負載均勻分布到每個傳感器節點，從而達到降低網絡能耗，延長網絡壽命的目的。該算法最大的缺陷是忽略了節點能量的因素，造成網絡能量消耗的不均衡，導致局部節點過早死亡。此后的研究者大都注意到了這一缺陷，并作了改進。文獻［4］在簇頭選擇的過程中引入節點的剩余能量，使剩余能量較多的節點當選為簇頭的可能性增加，降低了組簇失敗的可能性。文獻［5］中的LEACH-C算法，進一步要求當選簇頭節點的能量高于網絡節點的平均剩余能量。文獻［6］提出了DF-LEACH算法，考慮到距離基站較遠的簇頭通信能耗較大這一因素，避免了距離基站較遠的簇頭節點較早死亡。文獻［7］給出的算法將所有節點分為固定的簇，簇內節點根據所處簇的半徑自適應地進行簇頭選擇。簇頭選舉是一個NP難解問題，智能優化算法解這類問題具有獨特的優勢。文獻［5］中的LEACH-C算法在基站采用模擬退火算法(Simulated Annealing Algorithm)完成分簇;文獻［8］給出了一種基于蟻群優化的分簇算法，但是只適用于小規模網絡;文獻［9］采用粒子群優化(PSO)分簇算法，提出了均勻分簇(每個簇的節點數量及候選簇頭數量相等)的思想，但是該算法不適用于網絡節點分布不均勻的情況;文獻［10］提出了一種基于最優簇數的分簇策略，采用PSO進行分簇優化，但是沒有考慮簇頭到基站距離這一因素。

根據最優化理論領域的NFL(No Free Lunch Theorem)定理［11］，沒有一種算法對任何問題都能做到解最優。因此，需要針對某一實際問題，融合不同算法的各自優勢，構造出適應該問題的新算法。本文正是根據這一思路，將混沌理論引入PSO算法，有效避免了PSO算法易陷入局部最優解的缺陷，提出了一種應用混沌粒子群優化的分簇協議，新協議對剩余能量、簇頭距匯聚節點距離以及簇范圍的選擇作了綜合考慮，延長了網絡生存周期。

1 系統模型

1.1 網絡模型

本文采用分簇層次網絡拓撲結構，如圖1所示。

圖1 網絡拓撲結構圖

網絡由簇成員節點(Cluster member node)，簇頭節點(Cluster head node)和匯聚節點(Sink node)組成。分簇算法將網絡節點分為多個簇，每個簇包含一個簇頭節點和多個簇成員節點，簇成員節點將采集到的數據傳送到簇頭節點，簇頭節點除了自身采集數據外，還要接收其成員節點發送來的數據，并對這些數據進行融合，而后將處理的結果發送至匯聚節點。匯聚節點具有足夠的能量，其處理能力、存儲能力和通信能力較強，起到連接無線傳感器網絡與外部網絡的作用。除匯聚節點外，對網絡節點模型的具體要求如下:

(1)節點屬于同構節點，具有相同的初始能量、信息處理能力、探測半徑和通信半徑，并且通信半徑遠大于探測半徑;

(2)發射功率在允許范圍內可調;

(3)節點的位置固定，其自身的位置信息已知，可以通過GPS設備或者節點自定位算法獲得，本文不討論WSN節點自定位問題;

(4)匯聚節點唯一且位置固定，各網絡節點距離匯聚節點的距離已知，可以通過節點與匯聚節點的信息交換獲取。

1.2 能耗模型

節點的能量消耗主要來自數據收發和處理，與之相比，偵聽和休眠狀態消耗的能量微不足道。因此，本文僅考慮數據收發和處理的能耗。為了便于與LEACH算法進行仿真比較，采用與文獻［3］相同的無線通信模型，網絡節點發送kbit數據傳輸dm距離消耗的能量ETx為

節點接收kbit數據所需要的能量ERx為

節點處理kbit數據所需的能量Eda-fus為

其中，Eelec是發送電路和接收電路的能量消耗;Eda是處理數據的能量消耗;εfs和εmp分別是自由空間模型和多徑衰減模型中功率放大器的能量消耗，d0是傳輸距離門限，決定了衰減模式。

2 混沌粒子群算法

PSO算法是一種基于種群搜索策略的全局優化算法［12］，它在搜索空間中初始化一群隨機粒子，每個粒子代表解空間內的一個隨機解，粒子在搜索空間內飛行，根據其自身經驗和整個群體的經驗動態調整自己的速度，通過迭代找到最優解，每個粒子根據如下的公式來更新自己的速度和位置:

其中，vk是粒子的速度向量;xk是當前粒子的位置;pbestk表示粒子本身所找到的最優解的位置;gbestk表示整個種群目前找到的最優解的位置;c0表示慣性權重，當它取較大值時，有利于跳出局部極值，當它取較小值時，有利于算法收斂，一般取介于(0，1)之間的隨機數，c1、c2表示加速常數，其值低時允許粒子在目標區域外徘徊，高的值則導致粒子突然沖向或超過目標區域，一般取(0，2)之間的隨機數。

粒子群算法很容易陷入局部最優解［13］，為了解決該問題，將混沌理論引入PSO算法，完成算法改進。混沌是存在于非線性系統中的一種貌似隨機的運動形式，是確定性系統內在隨機性的表現，它具有隨機性，遍歷性和規律性三個特點［14］。混沌的這些特征，十分有利于PSO的優化和改進:隨機性有利于算法獲得大范圍搜索能力，遍歷性使得最終解有能力逼近最優解，規律性可以保證算法使用固定的迭代方程，從而便于編程計算。改進后的算法思路是:首先初始化種群，設定好參數。而后計算每個粒子的適應度，選出個體極值和全局極值，利用式(4)、式(5)開始迭代尋優過程。運算到預先設定的次數后，啟動混沌搜索，對當前最優解gbest施加混沌擾動，獲得新的最優解g'best，計算其適應值fitness'并與gbest的適應值 fitness進行比較，如果 fitness'＜fitness(即加入混沌擾動后的最優解優于當前最優解)，則選取g'best作為新的全局最優解繼續迭代計算。

以往的研究通常使用logistic映射產生混沌擾動，但是根據文獻［15］的結論，Tent映射的遍歷均勻性優于logistic映射，可以獲得更高的搜索尋優效率，因此本文采用Tent映射作為混沌擾動產生器，它的表達式如下:

產生混沌點列的過程如下:

步驟1設粒子的n維位置向量為xi=(xi1，xi2，…，xin)，根據式(7)將其映射到［0，1］區間上

其中，［ak，bk］是第k維變量xik的定義域。

步驟2由式(6)迭代產生混沌序列

步驟3由式(8)將混沌序列中的點映射回原空間，得到xi經過Tent映射后的混沌點列:

3 分簇協議描述

3.1 分簇原則

本文的分簇協議主要遵循以下原則:

(1)簇頭節點的剩余能量較多 這點是經典的LEACH分簇協議沒有考慮到的。因為簇頭節點要擔負更多的管理和通信任務，消耗的能量也相應的更多，如果當選的簇頭節點能量不足，會造成簇組織的維持時間縮短，造成任務無法完成。

(2)簇頭節點與匯聚節點的距離相對較近 簇頭節點根據簇成員節點匯報的信息進行初步的處理后，要將結果發送給匯聚節點，如果簇頭距離匯聚節點過遠，信號的發送將消耗大量的能量，簇頭會很快死亡。

(3)簇頭節點激活的范圍要適當 所謂適當，就是指簇的規模不能太大，這會造成簇邊界成員與簇頭的通信距離過遠，此外，過多的成員節點與簇頭信息交互有可能造成不必要的數據沖突;簇的規模又不能太小，這會造成簇的工作范圍減小，激活節點的數目不夠，滿足不了任務要求。因此，需要通過強制手段限定簇范圍，達到確保簇具有局部性的目的。

前兩條原則，本文通過混沌粒子群算法中適應度的合理設置來滿足，第(3)條原則，則通過對接收指示信號強度設定閥值獲得，將給出一種簇范圍確定方法。

3.2 基于CPSO的分簇算法(CPSOCH)

在設計時權衡節點剩余能量及節點與匯聚節點的距離兩個因素。適應度的計算公式為:

其中，α1、α2是影響因素的權重，滿足 α1+α2=1;qi是網絡中第i個節點的剩余能量，qk是第k個當選簇頭節點的剩余能量，f1是能量評價因子，等于網絡中所有節點能量之和除以所有當選簇頭節點的能量之和;li是第個節點距離匯聚節點的距離，lk是第k個當選簇頭節點距離匯聚節點的距離;f2是距離評價因子，等于網絡中所有節點到匯聚節點的距離之和除以所有當選簇頭節點到匯聚節點的距離之和。這對應了之前對簇頭選擇的要求:節點的剩余能量越多，距離匯聚節點越近，越有可能當選為簇頭。通過調節α1、α2達到調節各方面因素權重的目的。

首輪選舉時，假設網絡剛部署完畢，各節點剩余能量幾乎相同，因此仍采用LEACH算法的簇頭選舉方式。確定最優簇數K，根據文獻［5］的結論

其中，N、Efs、Eelec、εmp的意義如前文所述，l是簇頭到匯聚節點的距離，D網絡區域的邊長，計算時通常取監測區域的中心或者所有節點平均坐標到匯聚節點的距離。

從第二輪選舉開始，各節點剩余能量不同，此時匯聚節點采用本文基于CPSO的選舉方法確定簇頭。

基于CPSO的簇頭選舉算法具體步驟如下:

步驟1初始化M個粒子，每個粒子代表一種分簇可能，包含K個簇頭候選節點;

步驟2通過式(9)～式(11)計算每個粒子的適應值，記錄個體最優解和種群最優解;

步驟3通過式(4)、式(5)更新粒子的速度和位置;

步驟4搜索一定次數后通過式(6)～式(8)產生混沌擾動，計算擾動后每個粒子的適應值，記錄個體最優解和種群最優解;

步驟5重復步驟2、3、4直到達到預定的循環次數，輸出結果。

步驟6發布簇頭信息。

確定簇頭節點后，它要選擇適當數目的成員節點參與任務，以往的選擇方法往往無法保證簇的局部性，不利于節省能量。因此，本文根據接收指示信號強度閥值的方法來確定簇成員。簇頭應用CSMA(Carrier-sense Multiple Access)MAC層協議向非簇頭節點廣播當選消息(ADV，Advertisement Message)，消息發送能量強度相同。如果節點接收到的ADV信號強度大于事先設定的閥值S0，則向該簇頭發送請求加入消息Join-REQ，申請成為該簇頭的成員節點。如果某節點同時收到多個能量大于S0的ADV消息，它將選擇ADV強度最大的簇頭。因為信號能量越強，說明節點距離該簇頭的距離越近，可以有效地節省通信消耗。閥值S0的設定可根據網絡具體執行任務的不同要求設定。

4 算法仿真及性能評估

為了對本文提出的分簇算法性能進行評估，在相同條件下對本文算法和LEACH算法進行仿真比較。實驗中取200 m×200 m的區域，區域頂點的坐標分別為(0，0)、(200，0)、(200，200)，(0，200)。隨機部署的節點的數為200個，匯聚節點的位置為(100，300)，根據式(12)可算出，簇頭數量K的值取6。根據文獻［3］，q0取 2J，Eelec取 50 nJ/bit，εfs取 10 pJ/bit/m2，εmp取 0.001 3 pJ/bit/m4，d0取 75 m，Eda取5 pJ/bit，數據包取2 000 bit。CPSO的參數設置為:初始化粒子數為 20，c0、c1、c2及最大速度vmax是在規定范圍內通過多次實驗確定的經驗值，其中，c0取0.729 8，c1、c2取為 1.496 2，vmax=5，最大迭代次數設為1 000次，運算600次之后加入混沌搜索。對于影響因素權重α1、α2設置的考慮是:首先，節點必須擁有足夠多的能量，這是其順利運行的前提，如果能量不足，即使距離匯聚節點較近，也不應該被選為簇頭;其次，如果距離權重α2取值過大，必然會導致當選簇頭的范圍集中在距離匯聚節點較近的小范圍內，不利于目標跟蹤等任務的完成。結合實驗分析，本文將 α1、α2分別取為0.7、0.3。

選用網絡生命周期和能耗兩個技術指標來評價算法的性能［4］。其中生命周期的評估用3個時間來描述:第1個節點的死亡時間(First Node Die，FND)，一半節點死亡時間(Half of Nodes Die，HND)，最后一個(全部)節點死亡時間(Last Node Die，LND)。能耗用從網絡啟動到所有節點能量耗盡所用的時間來表示。仿真結果取10次運行的平均值。

從圖2可以看出，較之LEACH協議，新協議的FND，HND，LND 的時間分別延長了 115.82%，34.53%，38.65%，明顯延長了網絡的生命周期。特別是極大地延緩了第一個死亡節點的出現時刻，說明新協議較好了均衡了網絡能量消耗，避免了個別節點的快速死亡。

圖2 網絡生命周期對比

從圖3可以看出，LEACH協議運行了533輪后能量全部消耗完畢，而CPSOCH協議則在運行了739輪后才消耗完所有的能量。LEACH的曲線斜率變化較大，說明在不同時間內存在簇頭選擇不合理造成能量消耗較大的情況，而CPSOCH曲線斜率相對平穩，說明簇頭選擇相對更合理?？梢娫谀芎姆矫鍯PSOCH協議也優于LEACH協議。

圖3 能耗對比

5 結論

本文提出了一種WSN分簇協議，利用了智能算法在處理NP難解問題上的優越性，將結合了混沌理論和粒子群算法的混沌粒子群算法應用于分簇問題的優化，在簇頭選擇時考慮到了節點能量和匯聚節點距離等因素，在成員節點劃分時，給出了一種基于信號能量閥值的簇范圍劃分方法，從而達到了節省能量，延長網絡生存壽命的目的。下一步的工作應針對不同應用場景(目標跟蹤、環境監測等)，對該算法的具體應用進行研究。

［1］李建中，高宏.無線傳感器網絡的研究進展［J］.計算機研究與發展，2008，45(1):1－15.

［2］孟凡勇，熊慶旭.基于應用任務的無線傳感器網絡MAC協議［J］.傳感技術學報，2010，23(1):98－103.

［3］Heinzelman W，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks［C］//Proc.of the 33rd Annual Hawaii International Conf.on System Younis Sciences.Maui:IEEE Computer Society，2000:3005－3014.

［4］Handy M J，Haase M，Timmerrnann M D.Low Energy Adaptive Clustering Hierarchy with Deterministic Cluster-Head Selection［C］//Proc.of the 4th IEEE Conf.on Mobile and Wireless Communications Networks.Stockholm:IEEE Communications Society，2002:368－372.

［5］Heinzelman W，Chandrakasan A，Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Microsensor Networks［J］.IEEE Trans on Wireless Communications，2002，1(4):660－670.

［6］陳磊，趙寶華.低能耗自適應分簇的面向數據融合的路由協議［J］.北京郵電大學學報，2009，32(5):71－74.

［7］胡星華，駱堅，譚珊珊.固定簇的LEACH半徑自適應簇頭改進算法［J］.傳感技術學報，2011，24(1):79－82.

［8］張榮博，曹建福.利用蟻群優化的非均勻分簇無線傳感器網絡路由算法［J］.西安交通大學學報，2010，44(6):33－38.

［9］Tillett J，Rao R，Sahin F.Cluster-Head Identification in ad-hoc Sensor Networks Using Particle Swarm Optimization［C］//Proc.of IEEE International Conf.on Personal Wireless Communications.New Delhi，India，，2002:201－205.

［10］郭劍，孫力娟，王汝傳.基于最佳簇數的無線傳感器網絡粒子群分簇協議［J］.南京郵電大學學報(自然科學版)，2010，30(2):36－40.

［11］Wolpert D H，Macready W G.No Free Lunch Theorems for Optimization［J］.IEEE Trans.on Evolutionary Computation，1997，1(1):67－82.

［12］Kennedy J，Eberhart R.Particle Swarm Optimization［C］//Proc.of IEEE International Conf.on Neural Networks，Perth，1995:1942－1948.

［13］Zhang C S，Sun J G.An Alternate Two Phases Particle Swarm Optimization Algorithm for Flow Shop Scheduling Problem［J］.Expert System with Applications，2009，36(3):5162－5167.

［14］Tavazoei M S，Haeri M.An Optimization Algorithm Based on Chaotic Behavior and Fractal Nature［J］.Journal of Computational and Applied Mathematics，2007，206(2):1070－1081.

［15］單良，強浩，李軍.基于Tent影射的混沌優化算法［J］.控制與決策，2005，20(2):179－182.